1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use dep_graph
::DepGraph
;
12 use infer
::{InferCtxt, InferOk}
;
13 use ty
::{self, Ty, TyCtxt, TypeFoldable, ToPolyTraitRef}
;
14 use rustc_data_structures
::obligation_forest
::{Backtrace, ObligationForest, Error}
;
17 use util
::common
::ErrorReported
;
18 use util
::nodemap
::{FnvHashMap, FnvHashSet, NodeMap}
;
20 use super::CodeAmbiguity
;
21 use super::CodeProjectionError
;
22 use super::CodeSelectionError
;
23 use super::is_object_safe
;
24 use super::FulfillmentError
;
25 use super::FulfillmentErrorCode
;
26 use super::ObligationCause
;
27 use super::PredicateObligation
;
29 use super::report_overflow_error_cycle
;
30 use super::select
::SelectionContext
;
31 use super::Unimplemented
;
32 use super::util
::predicate_for_builtin_bound
;
34 pub struct GlobalFulfilledPredicates
<'tcx
> {
35 set
: FnvHashSet
<ty
::PolyTraitPredicate
<'tcx
>>,
40 pub struct LocalFulfilledPredicates
<'tcx
> {
41 set
: FnvHashSet
<ty
::Predicate
<'tcx
>>
44 /// The fulfillment context is used to drive trait resolution. It
45 /// consists of a list of obligations that must be (eventually)
46 /// satisfied. The job is to track which are satisfied, which yielded
47 /// errors, and which are still pending. At any point, users can call
48 /// `select_where_possible`, and the fulfilment context will try to do
49 /// selection, retaining only those obligations that remain
50 /// ambiguous. This may be helpful in pushing type inference
51 /// along. Once all type inference constraints have been generated, the
52 /// method `select_all_or_error` can be used to report any remaining
53 /// ambiguous cases as errors.
54 pub struct FulfillmentContext
<'tcx
> {
55 // a simple cache that aims to cache *exact duplicate obligations*
56 // and avoid adding them twice. This serves a different purpose
57 // than the `SelectionCache`: it avoids duplicate errors and
58 // permits recursive obligations, which are often generated from
59 // traits like `Send` et al.
61 // Note that because of type inference, a predicate can still
62 // occur twice in the predicates list, for example when 2
63 // initially-distinct type variables are unified after being
64 // inserted. Deduplicating the predicate set on selection had a
65 // significant performance cost the last time I checked.
66 duplicate_set
: LocalFulfilledPredicates
<'tcx
>,
68 // A list of all obligations that have been registered with this
69 // fulfillment context.
70 predicates
: ObligationForest
<PendingPredicateObligation
<'tcx
>,
71 LocalFulfilledPredicates
<'tcx
>>,
73 // A set of constraints that regionck must validate. Each
74 // constraint has the form `T:'a`, meaning "some type `T` must
75 // outlive the lifetime 'a". These constraints derive from
76 // instantiated type parameters. So if you had a struct defined
79 // struct Foo<T:'static> { ... }
81 // then in some expression `let x = Foo { ... }` it will
82 // instantiate the type parameter `T` with a fresh type `$0`. At
83 // the same time, it will record a region obligation of
84 // `$0:'static`. This will get checked later by regionck. (We
85 // can't generally check these things right away because we have
86 // to wait until types are resolved.)
88 // These are stored in a map keyed to the id of the innermost
89 // enclosing fn body / static initializer expression. This is
90 // because the location where the obligation was incurred can be
91 // relevant with respect to which sublifetime assumptions are in
92 // place. The reason that we store under the fn-id, and not
93 // something more fine-grained, is so that it is easier for
94 // regionck to be sure that it has found *all* the region
95 // obligations (otherwise, it's easy to fail to walk to a
96 // particular node-id).
97 region_obligations
: NodeMap
<Vec
<RegionObligation
<'tcx
>>>,
101 pub struct RegionObligation
<'tcx
> {
102 pub sub_region
: ty
::Region
,
103 pub sup_type
: Ty
<'tcx
>,
104 pub cause
: ObligationCause
<'tcx
>,
107 #[derive(Clone, Debug)]
108 pub struct PendingPredicateObligation
<'tcx
> {
109 pub obligation
: PredicateObligation
<'tcx
>,
110 pub stalled_on
: Vec
<Ty
<'tcx
>>,
113 impl<'tcx
> FulfillmentContext
<'tcx
> {
114 /// Creates a new fulfillment context.
115 pub fn new() -> FulfillmentContext
<'tcx
> {
117 duplicate_set
: LocalFulfilledPredicates
::new(),
118 predicates
: ObligationForest
::new(),
119 region_obligations
: NodeMap(),
123 /// "Normalize" a projection type `<SomeType as SomeTrait>::X` by
124 /// creating a fresh type variable `$0` as well as a projection
125 /// predicate `<SomeType as SomeTrait>::X == $0`. When the
126 /// inference engine runs, it will attempt to find an impl of
127 /// `SomeTrait` or a where clause that lets us unify `$0` with
128 /// something concrete. If this fails, we'll unify `$0` with
129 /// `projection_ty` again.
130 pub fn normalize_projection_type
<'a
>(&mut self,
131 infcx
: &InferCtxt
<'a
,'tcx
>,
132 projection_ty
: ty
::ProjectionTy
<'tcx
>,
133 cause
: ObligationCause
<'tcx
>)
136 debug
!("normalize_projection_type(projection_ty={:?})",
139 assert
!(!projection_ty
.has_escaping_regions());
141 // FIXME(#20304) -- cache
143 let mut selcx
= SelectionContext
::new(infcx
);
144 let normalized
= project
::normalize_projection_type(&mut selcx
, projection_ty
, cause
, 0);
146 for obligation
in normalized
.obligations
{
147 self.register_predicate_obligation(infcx
, obligation
);
150 debug
!("normalize_projection_type: result={:?}", normalized
.value
);
155 pub fn register_builtin_bound
<'a
>(&mut self,
156 infcx
: &InferCtxt
<'a
,'tcx
>,
158 builtin_bound
: ty
::BuiltinBound
,
159 cause
: ObligationCause
<'tcx
>)
161 match predicate_for_builtin_bound(infcx
.tcx
, cause
, builtin_bound
, 0, ty
) {
163 self.register_predicate_obligation(infcx
, predicate
);
165 Err(ErrorReported
) => { }
169 pub fn register_region_obligation
<'a
>(&mut self,
172 cause
: ObligationCause
<'tcx
>)
174 register_region_obligation(t_a
, r_b
, cause
, &mut self.region_obligations
);
177 pub fn register_predicate_obligation
<'a
>(&mut self,
178 infcx
: &InferCtxt
<'a
,'tcx
>,
179 obligation
: PredicateObligation
<'tcx
>)
181 // this helps to reduce duplicate errors, as well as making
182 // debug output much nicer to read and so on.
183 let obligation
= infcx
.resolve_type_vars_if_possible(&obligation
);
185 assert
!(!obligation
.has_escaping_regions());
187 if self.is_duplicate_or_add(infcx
.tcx
, &obligation
.predicate
) {
188 debug
!("register_predicate_obligation({:?}) -- already seen, skip", obligation
);
192 debug
!("register_predicate_obligation({:?})", obligation
);
193 let obligation
= PendingPredicateObligation
{
194 obligation
: obligation
,
197 self.predicates
.push_tree(obligation
, LocalFulfilledPredicates
::new());
200 pub fn region_obligations(&self,
201 body_id
: ast
::NodeId
)
202 -> &[RegionObligation
<'tcx
>]
204 match self.region_obligations
.get(&body_id
) {
205 None
=> Default
::default(),
210 pub fn select_all_or_error
<'a
>(&mut self,
211 infcx
: &InferCtxt
<'a
,'tcx
>)
212 -> Result
<(),Vec
<FulfillmentError
<'tcx
>>>
214 self.select_where_possible(infcx
)?
;
216 self.predicates
.to_errors(CodeAmbiguity
)
218 .map(|e
| to_fulfillment_error(e
))
220 if errors
.is_empty() {
227 pub fn select_where_possible
<'a
>(&mut self,
228 infcx
: &InferCtxt
<'a
,'tcx
>)
229 -> Result
<(),Vec
<FulfillmentError
<'tcx
>>>
231 let mut selcx
= SelectionContext
::new(infcx
);
232 self.select(&mut selcx
)
235 pub fn pending_obligations(&self) -> Vec
<PendingPredicateObligation
<'tcx
>> {
236 self.predicates
.pending_obligations()
239 fn is_duplicate_or_add(&mut self,
241 predicate
: &ty
::Predicate
<'tcx
>)
243 // For "global" predicates -- that is, predicates that don't
244 // involve type parameters, inference variables, or regions
245 // other than 'static -- we can check the cache in the tcx,
246 // which allows us to leverage work from other threads. Note
247 // that we don't add anything to this cache yet (unlike the
248 // local cache). This is because the tcx cache maintains the
249 // invariant that it only contains things that have been
250 // proven, and we have not yet proven that `predicate` holds.
251 if tcx
.fulfilled_predicates
.borrow().check_duplicate(predicate
) {
255 // If `predicate` is not global, or not present in the tcx
256 // cache, we can still check for it in our local cache and add
257 // it if not present. Note that if we find this predicate in
258 // the local cache we can stop immediately, without reporting
259 // any errors, even though we don't know yet if it is
260 // true. This is because, while we don't yet know if the
261 // predicate holds, we know that this same fulfillment context
262 // already is in the process of finding out.
263 self.duplicate_set
.is_duplicate_or_add(predicate
)
266 /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it
267 /// only attempts to select obligations that haven't been seen before.
268 fn select
<'a
>(&mut self,
269 selcx
: &mut SelectionContext
<'a
, 'tcx
>)
270 -> Result
<(),Vec
<FulfillmentError
<'tcx
>>>
272 debug
!("select(obligation-forest-size={})", self.predicates
.len());
274 let mut errors
= Vec
::new();
277 debug
!("select: starting another iteration");
279 // Process pending obligations.
281 let region_obligations
= &mut self.region_obligations
;
282 self.predicates
.process_obligations(
283 |obligation
, tree
, backtrace
| process_predicate(selcx
,
290 debug
!("select: outcome={:?}", outcome
);
292 // these are obligations that were proven to be true.
293 for pending_obligation
in outcome
.completed
{
294 let predicate
= &pending_obligation
.obligation
.predicate
;
295 selcx
.tcx().fulfilled_predicates
.borrow_mut().add_if_global(predicate
);
299 outcome
.errors
.into_iter()
300 .map(|e
| to_fulfillment_error(e
)));
302 // If nothing new was added, no need to keep looping.
308 debug
!("select({} predicates remaining, {} errors) done",
309 self.predicates
.len(), errors
.len());
311 if errors
.is_empty() {
319 /// Like `process_predicate1`, but wrap result into a pending predicate.
320 fn process_predicate
<'a
,'tcx
>(selcx
: &mut SelectionContext
<'a
,'tcx
>,
321 tree_cache
: &mut LocalFulfilledPredicates
<'tcx
>,
322 pending_obligation
: &mut PendingPredicateObligation
<'tcx
>,
323 backtrace
: Backtrace
<PendingPredicateObligation
<'tcx
>>,
324 region_obligations
: &mut NodeMap
<Vec
<RegionObligation
<'tcx
>>>)
325 -> Result
<Option
<Vec
<PendingPredicateObligation
<'tcx
>>>,
326 FulfillmentErrorCode
<'tcx
>>
328 match process_predicate1(selcx
, pending_obligation
, region_obligations
) {
329 Ok(Some(v
)) => process_child_obligations(selcx
,
331 &pending_obligation
.obligation
,
334 Ok(None
) => Ok(None
),
339 fn process_child_obligations
<'a
,'tcx
>(
340 selcx
: &mut SelectionContext
<'a
,'tcx
>,
341 tree_cache
: &mut LocalFulfilledPredicates
<'tcx
>,
342 pending_obligation
: &PredicateObligation
<'tcx
>,
343 backtrace
: Backtrace
<PendingPredicateObligation
<'tcx
>>,
344 child_obligations
: Vec
<PredicateObligation
<'tcx
>>)
345 -> Result
<Option
<Vec
<PendingPredicateObligation
<'tcx
>>>,
346 FulfillmentErrorCode
<'tcx
>>
348 // FIXME(#30977) The code below is designed to detect (and
349 // permit) DAGs, while still ensuring that the reasoning
350 // is acyclic. However, it does a few things
351 // suboptimally. For example, it refreshes type variables
352 // a lot, probably more than needed, but also less than
355 // - more than needed: I want to be very sure we don't
356 // accidentally treat a cycle as a DAG, so I am
357 // refreshing type variables as we walk the ancestors;
358 // but we are going to repeat this a lot, which is
359 // sort of silly, and it would be nicer to refresh
360 // them *in place* so that later predicate processing
361 // can benefit from the same work;
362 // - less than you might want: we only add items in the cache here,
363 // but maybe we learn more about type variables and could add them into
364 // the cache later on.
366 let tcx
= selcx
.tcx();
368 let mut ancestor_set
= AncestorSet
::new(&backtrace
);
370 let pending_predicate_obligations
: Vec
<_
> =
373 .filter_map(|obligation
| {
374 // Probably silly, but remove any inference
375 // variables. This is actually crucial to the ancestor
376 // check marked (*) below, but it's not clear that it
377 // makes sense to ALWAYS do it.
378 let obligation
= selcx
.infcx().resolve_type_vars_if_possible(&obligation
);
380 // Screen out obligations that we know globally
382 if tcx
.fulfilled_predicates
.borrow().check_duplicate(&obligation
.predicate
) {
386 // Check whether this obligation appears
387 // somewhere else in the tree. If not, we have to
388 // process it for sure.
389 if !tree_cache
.is_duplicate_or_add(&obligation
.predicate
) {
390 return Some(PendingPredicateObligation
{
391 obligation
: obligation
,
396 debug
!("process_child_obligations: duplicate={:?}",
397 obligation
.predicate
);
399 // OK, the obligation appears elsewhere in the tree.
400 // This is either a fatal error or else something we can
401 // ignore. If the obligation appears in our *ancestors*
402 // (rather than some more distant relative), that
403 // indicates a cycle. Cycles are either considered
404 // resolved (if this is a coinductive case) or a fatal
406 if let Some(index
) = ancestor_set
.has(selcx
.infcx(), &obligation
.predicate
) {
408 debug
!("process_child_obligations: cycle index = {}", index
);
410 let backtrace
= backtrace
.clone();
412 iter
::once(&obligation
)
413 .chain(Some(pending_obligation
))
414 .chain(backtrace
.take(index
+ 1).map(|p
| &p
.obligation
))
417 if coinductive_match(selcx
, &cycle
) {
418 debug
!("process_child_obligations: coinductive match");
421 report_overflow_error_cycle(selcx
.infcx(), &cycle
);
424 // Not a cycle. Just ignore this obligation then,
425 // we're already in the process of proving it.
426 debug
!("process_child_obligations: not a cycle");
432 Ok(Some(pending_predicate_obligations
))
435 struct AncestorSet
<'b
, 'tcx
: 'b
> {
437 cache
: FnvHashMap
<ty
::Predicate
<'tcx
>, usize>,
438 backtrace
: Backtrace
<'b
, PendingPredicateObligation
<'tcx
>>,
441 impl<'b
, 'tcx
> AncestorSet
<'b
, 'tcx
> {
442 fn new(backtrace
: &Backtrace
<'b
, PendingPredicateObligation
<'tcx
>>) -> Self {
446 backtrace
: backtrace
.clone(),
450 /// Checks whether any of the ancestors in the backtrace are equal
451 /// to `predicate` (`predicate` is assumed to be fully
452 /// type-resolved). Returns `None` if not; otherwise, returns
453 /// `Some` with the index within the backtrace.
454 fn has
<'a
>(&mut self,
455 infcx
: &InferCtxt
<'a
, 'tcx
>,
456 predicate
: &ty
::Predicate
<'tcx
>)
458 // the first time, we have to populate the cache
460 let backtrace
= self.backtrace
.clone();
461 for (index
, ancestor
) in backtrace
.enumerate() {
462 // Ugh. This just feels ridiculously
463 // inefficient. But we need to compare
464 // predicates without being concerned about
465 // the vagaries of type inference, so for now
466 // just ensure that they are always
467 // up-to-date. (I suppose we could just use a
468 // snapshot and check if they are unifiable?)
469 let resolved_predicate
=
470 infcx
.resolve_type_vars_if_possible(
471 &ancestor
.obligation
.predicate
);
473 // Though we try to avoid it, it can happen that a
474 // cycle already exists in the predecessors. This
475 // happens if the type variables were not fully known
476 // at the time that the ancestors were pushed. We'll
477 // just ignore such cycles for now, on the premise
478 // that they will repeat themselves and we'll deal
479 // with them properly then.
480 self.cache
.entry(resolved_predicate
)
483 self.populated
= true;
486 self.cache
.get(predicate
).cloned()
490 /// Return the set of type variables contained in a trait ref
491 fn trait_ref_type_vars
<'a
, 'tcx
>(selcx
: &mut SelectionContext
<'a
, 'tcx
>,
492 t
: ty
::PolyTraitRef
<'tcx
>) -> Vec
<Ty
<'tcx
>>
494 t
.skip_binder() // ok b/c this check doesn't care about regions
497 .map(|t
| selcx
.infcx().resolve_type_vars_if_possible(t
))
498 .filter(|t
| t
.has_infer_types())
499 .flat_map(|t
| t
.walk())
500 .filter(|t
| match t
.sty { ty::TyInfer(_) => true, _ => false }
)
504 /// Processes a predicate obligation and returns either:
505 /// - `Ok(Some(v))` if the predicate is true, presuming that `v` are also true
506 /// - `Ok(None)` if we don't have enough info to be sure
507 /// - `Err` if the predicate does not hold
508 fn process_predicate1
<'a
,'tcx
>(selcx
: &mut SelectionContext
<'a
,'tcx
>,
509 pending_obligation
: &mut PendingPredicateObligation
<'tcx
>,
510 region_obligations
: &mut NodeMap
<Vec
<RegionObligation
<'tcx
>>>)
511 -> Result
<Option
<Vec
<PredicateObligation
<'tcx
>>>,
512 FulfillmentErrorCode
<'tcx
>>
514 // if we were stalled on some unresolved variables, first check
515 // whether any of them have been resolved; if not, don't bother
516 // doing more work yet
517 if !pending_obligation
.stalled_on
.is_empty() {
518 if pending_obligation
.stalled_on
.iter().all(|&ty
| {
519 let resolved_ty
= selcx
.infcx().shallow_resolve(&ty
);
520 resolved_ty
== ty
// nothing changed here
522 debug
!("process_predicate: pending obligation {:?} still stalled on {:?}",
523 selcx
.infcx().resolve_type_vars_if_possible(&pending_obligation
.obligation
),
524 pending_obligation
.stalled_on
);
527 pending_obligation
.stalled_on
= vec
![];
530 let obligation
= &mut pending_obligation
.obligation
;
532 if obligation
.predicate
.has_infer_types() {
533 obligation
.predicate
= selcx
.infcx().resolve_type_vars_if_possible(&obligation
.predicate
);
536 match obligation
.predicate
{
537 ty
::Predicate
::Trait(ref data
) => {
538 if selcx
.tcx().fulfilled_predicates
.borrow().check_duplicate_trait(data
) {
539 return Ok(Some(vec
![]));
542 let trait_obligation
= obligation
.with(data
.clone());
543 match selcx
.select(&trait_obligation
) {
544 Ok(Some(vtable
)) => {
545 info
!("selecting trait `{:?}` at depth {} yielded Ok(Some)",
546 data
, obligation
.recursion_depth
);
547 Ok(Some(vtable
.nested_obligations()))
550 info
!("selecting trait `{:?}` at depth {} yielded Ok(None)",
551 data
, obligation
.recursion_depth
);
553 // This is a bit subtle: for the most part, the
554 // only reason we can fail to make progress on
555 // trait selection is because we don't have enough
556 // information about the types in the trait. One
557 // exception is that we sometimes haven't decided
558 // what kind of closure a closure is. *But*, in
559 // that case, it turns out, the type of the
560 // closure will also change, because the closure
561 // also includes references to its upvars as part
562 // of its type, and those types are resolved at
564 pending_obligation
.stalled_on
=
565 trait_ref_type_vars(selcx
, data
.to_poly_trait_ref());
567 debug
!("process_predicate: pending obligation {:?} now stalled on {:?}",
568 selcx
.infcx().resolve_type_vars_if_possible(obligation
),
569 pending_obligation
.stalled_on
);
573 Err(selection_err
) => {
574 info
!("selecting trait `{:?}` at depth {} yielded Err",
575 data
, obligation
.recursion_depth
);
576 Err(CodeSelectionError(selection_err
))
581 ty
::Predicate
::Equate(ref binder
) => {
582 match selcx
.infcx().equality_predicate(obligation
.cause
.span
, binder
) {
583 Ok(InferOk { obligations, .. }
) => {
584 // FIXME(#32730) propagate obligations
585 assert
!(obligations
.is_empty());
588 Err(_
) => Err(CodeSelectionError(Unimplemented
)),
592 ty
::Predicate
::RegionOutlives(ref binder
) => {
593 match selcx
.infcx().region_outlives_predicate(obligation
.cause
.span
, binder
) {
594 Ok(()) => Ok(Some(Vec
::new())),
595 Err(_
) => Err(CodeSelectionError(Unimplemented
)),
599 ty
::Predicate
::TypeOutlives(ref binder
) => {
600 // Check if there are higher-ranked regions.
601 match selcx
.tcx().no_late_bound_regions(binder
) {
602 // If there are, inspect the underlying type further.
604 // Convert from `Binder<OutlivesPredicate<Ty, Region>>` to `Binder<Ty>`.
605 let binder
= binder
.map_bound_ref(|pred
| pred
.0);
607 // Check if the type has any bound regions.
608 match selcx
.tcx().no_late_bound_regions(&binder
) {
609 // If so, this obligation is an error (for now). Eventually we should be
610 // able to support additional cases here, like `for<'a> &'a str: 'a`.
612 Err(CodeSelectionError(Unimplemented
))
614 // Otherwise, we have something of the form
615 // `for<'a> T: 'a where 'a not in T`, which we can treat as `T: 'static`.
617 register_region_obligation(t_a
, ty
::ReStatic
,
618 obligation
.cause
.clone(),
624 // If there aren't, register the obligation.
625 Some(ty
::OutlivesPredicate(t_a
, r_b
)) => {
626 register_region_obligation(t_a
, r_b
,
627 obligation
.cause
.clone(),
634 ty
::Predicate
::Projection(ref data
) => {
635 let project_obligation
= obligation
.with(data
.clone());
636 match project
::poly_project_and_unify_type(selcx
, &project_obligation
) {
638 pending_obligation
.stalled_on
=
639 trait_ref_type_vars(selcx
, data
.to_poly_trait_ref());
643 Err(e
) => Err(CodeProjectionError(e
))
647 ty
::Predicate
::ObjectSafe(trait_def_id
) => {
648 if !is_object_safe(selcx
.tcx(), trait_def_id
) {
649 Err(CodeSelectionError(Unimplemented
))
655 ty
::Predicate
::WellFormed(ty
) => {
656 match ty
::wf
::obligations(selcx
.infcx(), obligation
.cause
.body_id
,
657 ty
, obligation
.cause
.span
) {
659 pending_obligation
.stalled_on
= vec
![ty
];
668 /// For defaulted traits, we use a co-inductive strategy to solve, so
669 /// that recursion is ok. This routine returns true if the top of the
670 /// stack (`cycle[0]`):
671 /// - is a defaulted trait, and
672 /// - it also appears in the backtrace at some position `X`; and,
673 /// - all the predicates at positions `X..` between `X` an the top are
674 /// also defaulted traits.
675 fn coinductive_match
<'a
,'tcx
>(selcx
: &mut SelectionContext
<'a
,'tcx
>,
676 cycle
: &[PredicateObligation
<'tcx
>])
679 let len
= cycle
.len();
681 assert_eq
!(cycle
[0].predicate
, cycle
[len
- 1].predicate
);
685 .all(|bt_obligation
| {
686 let result
= coinductive_obligation(selcx
, bt_obligation
);
687 debug
!("coinductive_match: bt_obligation={:?} coinductive={}",
688 bt_obligation
, result
);
693 fn coinductive_obligation
<'a
, 'tcx
>(selcx
: &SelectionContext
<'a
, 'tcx
>,
694 obligation
: &PredicateObligation
<'tcx
>)
696 match obligation
.predicate
{
697 ty
::Predicate
::Trait(ref data
) => {
698 selcx
.tcx().trait_has_default_impl(data
.def_id())
706 fn register_region_obligation
<'tcx
>(t_a
: Ty
<'tcx
>,
708 cause
: ObligationCause
<'tcx
>,
709 region_obligations
: &mut NodeMap
<Vec
<RegionObligation
<'tcx
>>>)
711 let region_obligation
= RegionObligation
{ sup_type
: t_a
,
715 debug
!("register_region_obligation({:?}, cause={:?})",
716 region_obligation
, region_obligation
.cause
);
718 region_obligations
.entry(region_obligation
.cause
.body_id
)
720 .push(region_obligation
);
724 impl<'tcx
> LocalFulfilledPredicates
<'tcx
> {
725 pub fn new() -> LocalFulfilledPredicates
<'tcx
> {
726 LocalFulfilledPredicates
{
731 fn is_duplicate_or_add(&mut self, key
: &ty
::Predicate
<'tcx
>) -> bool
{
732 // For a `LocalFulfilledPredicates`, if we find a match, we
733 // don't need to add a read edge to the dep-graph. This is
734 // because it means that the predicate has already been
735 // considered by this `FulfillmentContext`, and hence the
736 // containing task will already have an edge. (Here we are
737 // assuming each `FulfillmentContext` only gets used from one
738 // task; but to do otherwise makes no sense)
739 !self.set
.insert(key
.clone())
743 impl<'tcx
> GlobalFulfilledPredicates
<'tcx
> {
744 pub fn new(dep_graph
: DepGraph
) -> GlobalFulfilledPredicates
<'tcx
> {
745 GlobalFulfilledPredicates
{
747 dep_graph
: dep_graph
,
751 pub fn check_duplicate(&self, key
: &ty
::Predicate
<'tcx
>) -> bool
{
752 if let ty
::Predicate
::Trait(ref data
) = *key
{
753 self.check_duplicate_trait(data
)
759 pub fn check_duplicate_trait(&self, data
: &ty
::PolyTraitPredicate
<'tcx
>) -> bool
{
760 // For the global predicate registry, when we find a match, it
761 // may have been computed by some other task, so we want to
762 // add a read from the node corresponding to the predicate
763 // processing to make sure we get the transitive dependencies.
764 if self.set
.contains(data
) {
765 debug_assert
!(data
.is_global());
766 self.dep_graph
.read(data
.dep_node());
767 debug
!("check_duplicate: global predicate `{:?}` already proved elsewhere", data
);
769 info
!("check_duplicate_trait hit: `{:?}`", data
);
777 fn add_if_global(&mut self, key
: &ty
::Predicate
<'tcx
>) {
778 if let ty
::Predicate
::Trait(ref data
) = *key
{
779 // We only add things to the global predicate registry
780 // after the current task has proved them, and hence
781 // already has the required read edges, so we don't need
782 // to add any more edges here.
783 if data
.is_global() {
784 if self.set
.insert(data
.clone()) {
785 debug
!("add_if_global: global predicate `{:?}` added", data
);
786 info
!("check_duplicate_trait entry: `{:?}`", data
);
793 fn to_fulfillment_error
<'tcx
>(
794 error
: Error
<PendingPredicateObligation
<'tcx
>, FulfillmentErrorCode
<'tcx
>>)
795 -> FulfillmentError
<'tcx
>
797 let obligation
= error
.backtrace
.into_iter().next().unwrap().obligation
;
798 FulfillmentError
::new(obligation
, error
.error
)