]> git.proxmox.com Git - rustc.git/blame - src/librustc/middle/traits/fulfill.rs
Imported Upstream version 1.8.0+dfsg1
[rustc.git] / src / librustc / middle / traits / fulfill.rs
CommitLineData
1a4d82fc
JJ
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.
4//
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.
10
7453a54e 11use dep_graph::DepGraph;
c34b1796 12use middle::infer::InferCtxt;
7453a54e
SL
13use middle::ty::{self, Ty, TypeFoldable, ToPolyTraitRef};
14use rustc_data_structures::obligation_forest::{Backtrace, ObligationForest, Error};
15use std::iter;
1a4d82fc
JJ
16use syntax::ast;
17use util::common::ErrorReported;
7453a54e 18use util::nodemap::{FnvHashMap, FnvHashSet, NodeMap};
1a4d82fc
JJ
19
20use super::CodeAmbiguity;
21use super::CodeProjectionError;
22use super::CodeSelectionError;
e9174d1e 23use super::is_object_safe;
1a4d82fc 24use super::FulfillmentError;
7453a54e 25use super::FulfillmentErrorCode;
1a4d82fc
JJ
26use super::ObligationCause;
27use super::PredicateObligation;
28use super::project;
7453a54e 29use super::report_overflow_error_cycle;
1a4d82fc
JJ
30use super::select::SelectionContext;
31use super::Unimplemented;
32use super::util::predicate_for_builtin_bound;
33
7453a54e
SL
34pub struct GlobalFulfilledPredicates<'tcx> {
35 set: FnvHashSet<ty::PolyTraitPredicate<'tcx>>,
36 dep_graph: DepGraph,
37}
38
39#[derive(Debug)]
40pub struct LocalFulfilledPredicates<'tcx> {
9cc50fc6 41 set: FnvHashSet<ty::Predicate<'tcx>>
62682a34
SL
42}
43
1a4d82fc
JJ
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.
54pub 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.
e9174d1e
SL
60 //
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.
7453a54e 66 duplicate_set: LocalFulfilledPredicates<'tcx>,
1a4d82fc
JJ
67
68 // A list of all obligations that have been registered with this
69 // fulfillment context.
7453a54e
SL
70 predicates: ObligationForest<PendingPredicateObligation<'tcx>,
71 LocalFulfilledPredicates<'tcx>>,
1a4d82fc
JJ
72
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
77 // like
78 //
79 // struct Foo<T:'static> { ... }
80 //
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.)
87 //
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>>>,
98}
99
85aaf69f 100#[derive(Clone)]
1a4d82fc
JJ
101pub struct RegionObligation<'tcx> {
102 pub sub_region: ty::Region,
103 pub sup_type: Ty<'tcx>,
104 pub cause: ObligationCause<'tcx>,
105}
106
7453a54e
SL
107#[derive(Clone, Debug)]
108pub struct PendingPredicateObligation<'tcx> {
109 pub obligation: PredicateObligation<'tcx>,
110 pub stalled_on: Vec<Ty<'tcx>>,
111}
112
1a4d82fc 113impl<'tcx> FulfillmentContext<'tcx> {
62682a34 114 /// Creates a new fulfillment context.
7453a54e 115 pub fn new() -> FulfillmentContext<'tcx> {
1a4d82fc 116 FulfillmentContext {
7453a54e
SL
117 duplicate_set: LocalFulfilledPredicates::new(),
118 predicates: ObligationForest::new(),
85aaf69f 119 region_obligations: NodeMap(),
1a4d82fc
JJ
120 }
121 }
122
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>,
1a4d82fc
JJ
132 projection_ty: ty::ProjectionTy<'tcx>,
133 cause: ObligationCause<'tcx>)
134 -> Ty<'tcx>
135 {
7453a54e 136 debug!("normalize_projection_type(projection_ty={:?})",
62682a34 137 projection_ty);
1a4d82fc
JJ
138
139 assert!(!projection_ty.has_escaping_regions());
140
141 // FIXME(#20304) -- cache
142
c1a9b12d 143 let mut selcx = SelectionContext::new(infcx);
1a4d82fc
JJ
144 let normalized = project::normalize_projection_type(&mut selcx, projection_ty, cause, 0);
145
85aaf69f 146 for obligation in normalized.obligations {
1a4d82fc
JJ
147 self.register_predicate_obligation(infcx, obligation);
148 }
149
7453a54e 150 debug!("normalize_projection_type: result={:?}", normalized.value);
1a4d82fc
JJ
151
152 normalized.value
153 }
154
155 pub fn register_builtin_bound<'a>(&mut self,
156 infcx: &InferCtxt<'a,'tcx>,
157 ty: Ty<'tcx>,
158 builtin_bound: ty::BuiltinBound,
159 cause: ObligationCause<'tcx>)
160 {
161 match predicate_for_builtin_bound(infcx.tcx, cause, builtin_bound, 0, ty) {
162 Ok(predicate) => {
163 self.register_predicate_obligation(infcx, predicate);
164 }
165 Err(ErrorReported) => { }
166 }
167 }
168
169 pub fn register_region_obligation<'a>(&mut self,
1a4d82fc
JJ
170 t_a: Ty<'tcx>,
171 r_b: ty::Region,
172 cause: ObligationCause<'tcx>)
173 {
62682a34 174 register_region_obligation(t_a, r_b, cause, &mut self.region_obligations);
1a4d82fc
JJ
175 }
176
177 pub fn register_predicate_obligation<'a>(&mut self,
178 infcx: &InferCtxt<'a,'tcx>,
179 obligation: PredicateObligation<'tcx>)
180 {
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);
184
c34b1796
AL
185 assert!(!obligation.has_escaping_regions());
186
9cc50fc6 187 if self.is_duplicate_or_add(infcx.tcx, &obligation.predicate) {
7453a54e 188 debug!("register_predicate_obligation({:?}) -- already seen, skip", obligation);
1a4d82fc
JJ
189 return;
190 }
191
7453a54e
SL
192 debug!("register_predicate_obligation({:?})", obligation);
193 let obligation = PendingPredicateObligation {
194 obligation: obligation,
195 stalled_on: vec![]
196 };
197 self.predicates.push_tree(obligation, LocalFulfilledPredicates::new());
1a4d82fc
JJ
198 }
199
200 pub fn region_obligations(&self,
201 body_id: ast::NodeId)
202 -> &[RegionObligation<'tcx>]
203 {
204 match self.region_obligations.get(&body_id) {
205 None => Default::default(),
85aaf69f 206 Some(vec) => vec,
1a4d82fc
JJ
207 }
208 }
209
210 pub fn select_all_or_error<'a>(&mut self,
c1a9b12d 211 infcx: &InferCtxt<'a,'tcx>)
1a4d82fc
JJ
212 -> Result<(),Vec<FulfillmentError<'tcx>>>
213 {
c1a9b12d 214 try!(self.select_where_possible(infcx));
7453a54e
SL
215 let errors: Vec<_> =
216 self.predicates.to_errors(CodeAmbiguity)
217 .into_iter()
218 .map(|e| to_fulfillment_error(e))
219 .collect();
1a4d82fc
JJ
220 if errors.is_empty() {
221 Ok(())
222 } else {
223 Err(errors)
224 }
225 }
226
1a4d82fc 227 pub fn select_where_possible<'a>(&mut self,
c1a9b12d 228 infcx: &InferCtxt<'a,'tcx>)
1a4d82fc
JJ
229 -> Result<(),Vec<FulfillmentError<'tcx>>>
230 {
c1a9b12d 231 let mut selcx = SelectionContext::new(infcx);
7453a54e 232 self.select(&mut selcx)
1a4d82fc
JJ
233 }
234
7453a54e
SL
235 pub fn pending_obligations(&self) -> Vec<PendingPredicateObligation<'tcx>> {
236 self.predicates.pending_obligations()
1a4d82fc
JJ
237 }
238
e9174d1e
SL
239 fn is_duplicate_or_add(&mut self,
240 tcx: &ty::ctxt<'tcx>,
62682a34
SL
241 predicate: &ty::Predicate<'tcx>)
242 -> bool {
7453a54e
SL
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) {
252 return true;
62682a34 253 }
7453a54e
SL
254
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)
62682a34
SL
264 }
265
1a4d82fc
JJ
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,
7453a54e 269 selcx: &mut SelectionContext<'a, 'tcx>)
1a4d82fc
JJ
270 -> Result<(),Vec<FulfillmentError<'tcx>>>
271 {
7453a54e 272 debug!("select(obligation-forest-size={})", self.predicates.len());
1a4d82fc
JJ
273
274 let mut errors = Vec::new();
275
276 loop {
7453a54e 277 debug!("select: starting another iteration");
1a4d82fc 278
7453a54e
SL
279 // Process pending obligations.
280 let outcome = {
281 let region_obligations = &mut self.region_obligations;
282 self.predicates.process_obligations(
283 |obligation, tree, backtrace| process_predicate(selcx,
284 tree,
285 obligation,
286 backtrace,
287 region_obligations))
1a4d82fc
JJ
288 };
289
7453a54e
SL
290 debug!("select: outcome={:?}", outcome);
291
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);
1a4d82fc
JJ
296 }
297
7453a54e
SL
298 errors.extend(
299 outcome.errors.into_iter()
300 .map(|e| to_fulfillment_error(e)));
1a4d82fc 301
7453a54e
SL
302 // If nothing new was added, no need to keep looping.
303 if outcome.stalled {
1a4d82fc
JJ
304 break;
305 }
1a4d82fc
JJ
306 }
307
7453a54e
SL
308 debug!("select({} predicates remaining, {} errors) done",
309 self.predicates.len(), errors.len());
1a4d82fc 310
9346a6ac 311 if errors.is_empty() {
1a4d82fc
JJ
312 Ok(())
313 } else {
314 Err(errors)
315 }
316 }
317}
318
7453a54e 319/// Like `process_predicate1`, but wrap result into a pending predicate.
1a4d82fc 320fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
7453a54e
SL
321 tree_cache: &mut LocalFulfilledPredicates<'tcx>,
322 pending_obligation: &mut PendingPredicateObligation<'tcx>,
323 mut backtrace: Backtrace<PendingPredicateObligation<'tcx>>,
1a4d82fc 324 region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
7453a54e
SL
325 -> Result<Option<Vec<PendingPredicateObligation<'tcx>>>,
326 FulfillmentErrorCode<'tcx>>
1a4d82fc 327{
7453a54e
SL
328 match process_predicate1(selcx, pending_obligation, backtrace.clone(), region_obligations) {
329 Ok(Some(v)) => {
330 // FIXME(#30977) The code below is designed to detect (and
331 // permit) DAGs, while still ensuring that the reasoning
332 // is acyclic. However, it does a few things
333 // suboptimally. For example, it refreshes type variables
334 // a lot, probably more than needed, but also less than
335 // you might want.
336 //
337 // - more than needed: I want to be very sure we don't
338 // accidentally treat a cycle as a DAG, so I am
339 // refreshing type variables as we walk the ancestors;
340 // but we are going to repeat this a lot, which is
341 // sort of silly, and it would be nicer to refresh
342 // them *in place* so that later predicate processing
343 // can benefit from the same work;
344 // - less than you might want: we only add items in the cache here,
345 // but maybe we learn more about type variables and could add them into
346 // the cache later on.
347
348 let tcx = selcx.tcx();
349
350 // Compute a little FnvHashSet for the ancestors. We only
351 // do this the first time that we care.
352 let mut cache = None;
353 let mut is_ancestor = |predicate: &ty::Predicate<'tcx>| {
354 if cache.is_none() {
355 let mut c = FnvHashSet();
356 for ancestor in backtrace.by_ref() {
357 // Ugh. This just feels ridiculously
358 // inefficient. But we need to compare
359 // predicates without being concerned about
360 // the vagaries of type inference, so for now
361 // just ensure that they are always
362 // up-to-date. (I suppose we could just use a
363 // snapshot and check if they are unifiable?)
364 let resolved_predicate =
365 selcx.infcx().resolve_type_vars_if_possible(
366 &ancestor.obligation.predicate);
367 c.insert(resolved_predicate);
368 }
369 cache = Some(c);
370 }
371
372 cache.as_ref().unwrap().contains(predicate)
373 };
374
375 let pending_predicate_obligations: Vec<_> =
376 v.into_iter()
377 .filter_map(|obligation| {
378 // Probably silly, but remove any inference
379 // variables. This is actually crucial to the
380 // ancestor check below, but it's not clear that
381 // it makes sense to ALWAYS do it.
382 let obligation = selcx.infcx().resolve_type_vars_if_possible(&obligation);
383
384 // Screen out obligations that we know globally
385 // are true. This should really be the DAG check
386 // mentioned above.
387 if tcx.fulfilled_predicates.borrow().check_duplicate(&obligation.predicate) {
388 return None;
389 }
390
391 // Check whether this obligation appears somewhere else in the tree.
392 if tree_cache.is_duplicate_or_add(&obligation.predicate) {
393 // If the obligation appears as a parent,
394 // allow it, because that is a cycle.
395 // Otherwise though we can just ignore
396 // it. Note that we have to be careful around
397 // inference variables here -- for the
398 // purposes of the ancestor check, we retain
399 // the invariant that all type variables are
400 // fully refreshed.
401 if !(&mut is_ancestor)(&obligation.predicate) {
402 return None;
403 }
404 }
405
406 Some(PendingPredicateObligation {
407 obligation: obligation,
408 stalled_on: vec![]
409 })
410 })
411 .collect();
412
413 Ok(Some(pending_predicate_obligations))
414 }
415 Ok(None) => Ok(None),
416 Err(e) => Err(e)
417 }
418}
419
420
421/// Return the set of type variables contained in a trait ref
422fn trait_ref_type_vars<'a, 'tcx>(selcx: &mut SelectionContext<'a, 'tcx>,
423 t: ty::PolyTraitRef<'tcx>) -> Vec<Ty<'tcx>>
424{
425 t.skip_binder() // ok b/c this check doesn't care about regions
426 .input_types()
427 .iter()
428 .map(|t| selcx.infcx().resolve_type_vars_if_possible(t))
429 .filter(|t| t.has_infer_types())
430 .flat_map(|t| t.walk())
431 .filter(|t| match t.sty { ty::TyInfer(_) => true, _ => false })
432 .collect()
433}
434
435/// Processes a predicate obligation and returns either:
436/// - `Ok(Some(v))` if the predicate is true, presuming that `v` are also true
437/// - `Ok(None)` if we don't have enough info to be sure
438/// - `Err` if the predicate does not hold
439fn process_predicate1<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
440 pending_obligation: &mut PendingPredicateObligation<'tcx>,
441 backtrace: Backtrace<PendingPredicateObligation<'tcx>>,
442 region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
443 -> Result<Option<Vec<PredicateObligation<'tcx>>>,
444 FulfillmentErrorCode<'tcx>>
445{
446 // if we were stalled on some unresolved variables, first check
447 // whether any of them have been resolved; if not, don't bother
448 // doing more work yet
449 if !pending_obligation.stalled_on.is_empty() {
450 if pending_obligation.stalled_on.iter().all(|&ty| {
451 let resolved_ty = selcx.infcx().shallow_resolve(&ty);
452 resolved_ty == ty // nothing changed here
453 }) {
454 debug!("process_predicate: pending obligation {:?} still stalled on {:?}",
455 selcx.infcx().resolve_type_vars_if_possible(&pending_obligation.obligation),
456 pending_obligation.stalled_on);
457 return Ok(None);
458 }
459 pending_obligation.stalled_on = vec![];
460 }
461
462 let obligation = &mut pending_obligation.obligation;
463
464 // If we exceed the recursion limit, take a moment to look for a
465 // cycle so we can give a better error report from here, where we
466 // have more context.
467 let recursion_limit = selcx.tcx().sess.recursion_limit.get();
468 if obligation.recursion_depth >= recursion_limit {
469 if let Some(cycle) = scan_for_cycle(obligation, &backtrace) {
470 report_overflow_error_cycle(selcx.infcx(), &cycle);
471 }
472 }
473
474 if obligation.predicate.has_infer_types() {
475 obligation.predicate = selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate);
476 }
1a4d82fc 477
1a4d82fc
JJ
478 match obligation.predicate {
479 ty::Predicate::Trait(ref data) => {
7453a54e
SL
480 if selcx.tcx().fulfilled_predicates.borrow().check_duplicate_trait(data) {
481 return Ok(Some(vec![]));
482 }
483
484 if coinductive_match(selcx, obligation, data, &backtrace) {
485 return Ok(Some(vec![]));
486 }
487
1a4d82fc
JJ
488 let trait_obligation = obligation.with(data.clone());
489 match selcx.select(&trait_obligation) {
7453a54e
SL
490 Ok(Some(vtable)) => {
491 info!("selecting trait `{:?}` at depth {} yielded Ok(Some)",
492 data, obligation.recursion_depth);
493 Ok(Some(vtable.nested_obligations()))
1a4d82fc 494 }
7453a54e
SL
495 Ok(None) => {
496 info!("selecting trait `{:?}` at depth {} yielded Ok(None)",
497 data, obligation.recursion_depth);
498
499 // This is a bit subtle: for the most part, the
500 // only reason we can fail to make progress on
501 // trait selection is because we don't have enough
502 // information about the types in the trait. One
503 // exception is that we sometimes haven't decided
504 // what kind of closure a closure is. *But*, in
505 // that case, it turns out, the type of the
506 // closure will also change, because the closure
507 // also includes references to its upvars as part
508 // of its type, and those types are resolved at
509 // the same time.
510 pending_obligation.stalled_on =
511 trait_ref_type_vars(selcx, data.to_poly_trait_ref());
512
513 debug!("process_predicate: pending obligation {:?} now stalled on {:?}",
514 selcx.infcx().resolve_type_vars_if_possible(obligation),
515 pending_obligation.stalled_on);
516
517 Ok(None)
1a4d82fc
JJ
518 }
519 Err(selection_err) => {
7453a54e
SL
520 info!("selecting trait `{:?}` at depth {} yielded Err",
521 data, obligation.recursion_depth);
522 Err(CodeSelectionError(selection_err))
1a4d82fc
JJ
523 }
524 }
525 }
526
527 ty::Predicate::Equate(ref binder) => {
528 match selcx.infcx().equality_predicate(obligation.cause.span, binder) {
7453a54e
SL
529 Ok(()) => Ok(Some(Vec::new())),
530 Err(_) => Err(CodeSelectionError(Unimplemented)),
1a4d82fc 531 }
1a4d82fc
JJ
532 }
533
534 ty::Predicate::RegionOutlives(ref binder) => {
535 match selcx.infcx().region_outlives_predicate(obligation.cause.span, binder) {
7453a54e
SL
536 Ok(()) => Ok(Some(Vec::new())),
537 Err(_) => Err(CodeSelectionError(Unimplemented)),
1a4d82fc 538 }
1a4d82fc
JJ
539 }
540
541 ty::Predicate::TypeOutlives(ref binder) => {
c1a9b12d
SL
542 // Check if there are higher-ranked regions.
543 match selcx.tcx().no_late_bound_regions(binder) {
544 // If there are, inspect the underlying type further.
545 None => {
546 // Convert from `Binder<OutlivesPredicate<Ty, Region>>` to `Binder<Ty>`.
547 let binder = binder.map_bound_ref(|pred| pred.0);
548
549 // Check if the type has any bound regions.
550 match selcx.tcx().no_late_bound_regions(&binder) {
551 // If so, this obligation is an error (for now). Eventually we should be
552 // able to support additional cases here, like `for<'a> &'a str: 'a`.
553 None => {
7453a54e 554 Err(CodeSelectionError(Unimplemented))
c1a9b12d
SL
555 }
556 // Otherwise, we have something of the form
557 // `for<'a> T: 'a where 'a not in T`, which we can treat as `T: 'static`.
558 Some(t_a) => {
559 register_region_obligation(t_a, ty::ReStatic,
560 obligation.cause.clone(),
561 region_obligations);
7453a54e 562 Ok(Some(vec![]))
c1a9b12d
SL
563 }
564 }
565 }
566 // If there aren't, register the obligation.
567 Some(ty::OutlivesPredicate(t_a, r_b)) => {
568 register_region_obligation(t_a, r_b,
569 obligation.cause.clone(),
570 region_obligations);
7453a54e 571 Ok(Some(vec![]))
c1a9b12d 572 }
1a4d82fc 573 }
1a4d82fc
JJ
574 }
575
576 ty::Predicate::Projection(ref data) => {
577 let project_obligation = obligation.with(data.clone());
7453a54e 578 match project::poly_project_and_unify_type(selcx, &project_obligation) {
1a4d82fc 579 Ok(None) => {
7453a54e
SL
580 pending_obligation.stalled_on =
581 trait_ref_type_vars(selcx, data.to_poly_trait_ref());
582 Ok(None)
1a4d82fc 583 }
7453a54e
SL
584 Ok(v) => Ok(v),
585 Err(e) => Err(CodeProjectionError(e))
1a4d82fc
JJ
586 }
587 }
1a4d82fc 588
e9174d1e
SL
589 ty::Predicate::ObjectSafe(trait_def_id) => {
590 if !is_object_safe(selcx.tcx(), trait_def_id) {
7453a54e
SL
591 Err(CodeSelectionError(Unimplemented))
592 } else {
593 Ok(Some(Vec::new()))
e9174d1e 594 }
e9174d1e
SL
595 }
596
597 ty::Predicate::WellFormed(ty) => {
e9174d1e 598 match ty::wf::obligations(selcx.infcx(), obligation.cause.body_id,
9cc50fc6 599 ty, obligation.cause.span) {
e9174d1e 600 None => {
7453a54e
SL
601 pending_obligation.stalled_on = vec![ty];
602 Ok(None)
e9174d1e 603 }
7453a54e 604 s => Ok(s)
e9174d1e
SL
605 }
606 }
1a4d82fc
JJ
607 }
608}
609
7453a54e
SL
610/// For defaulted traits, we use a co-inductive strategy to solve, so
611/// that recursion is ok. This routine returns true if the top of the
612/// stack (`top_obligation` and `top_data`):
613/// - is a defaulted trait, and
614/// - it also appears in the backtrace at some position `X`; and,
615/// - all the predicates at positions `X..` between `X` an the top are
616/// also defaulted traits.
617fn coinductive_match<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
618 top_obligation: &PredicateObligation<'tcx>,
619 top_data: &ty::PolyTraitPredicate<'tcx>,
620 backtrace: &Backtrace<PendingPredicateObligation<'tcx>>)
621 -> bool
622{
623 if selcx.tcx().trait_has_default_impl(top_data.def_id()) {
624 debug!("coinductive_match: top_data={:?}", top_data);
625 for bt_obligation in backtrace.clone() {
626 debug!("coinductive_match: bt_obligation={:?}", bt_obligation);
627
628 // *Everything* in the backtrace must be a defaulted trait.
629 match bt_obligation.obligation.predicate {
630 ty::Predicate::Trait(ref data) => {
631 if !selcx.tcx().trait_has_default_impl(data.def_id()) {
632 debug!("coinductive_match: trait does not have default impl");
633 break;
634 }
635 }
636 _ => { break; }
637 }
638
639 // And we must find a recursive match.
640 if bt_obligation.obligation.predicate == top_obligation.predicate {
641 debug!("coinductive_match: found a match in the backtrace");
642 return true;
643 }
644 }
645 }
646
647 false
648}
649
650fn scan_for_cycle<'a,'tcx>(top_obligation: &PredicateObligation<'tcx>,
651 backtrace: &Backtrace<PendingPredicateObligation<'tcx>>)
652 -> Option<Vec<PredicateObligation<'tcx>>>
653{
654 let mut map = FnvHashMap();
655 let all_obligations =
656 || iter::once(top_obligation)
657 .chain(backtrace.clone()
658 .map(|p| &p.obligation));
659 for (index, bt_obligation) in all_obligations().enumerate() {
660 if let Some(&start) = map.get(&bt_obligation.predicate) {
661 // Found a cycle starting at position `start` and running
662 // until the current position (`index`).
663 return Some(all_obligations().skip(start).take(index - start + 1).cloned().collect());
664 } else {
665 map.insert(bt_obligation.predicate.clone(), index);
666 }
667 }
668 None
669}
670
62682a34 671fn register_region_obligation<'tcx>(t_a: Ty<'tcx>,
1a4d82fc
JJ
672 r_b: ty::Region,
673 cause: ObligationCause<'tcx>,
674 region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>)
675{
676 let region_obligation = RegionObligation { sup_type: t_a,
677 sub_region: r_b,
678 cause: cause };
679
e9174d1e
SL
680 debug!("register_region_obligation({:?}, cause={:?})",
681 region_obligation, region_obligation.cause);
1a4d82fc 682
e9174d1e
SL
683 region_obligations.entry(region_obligation.cause.body_id)
684 .or_insert(vec![])
685 .push(region_obligation);
1a4d82fc
JJ
686
687}
62682a34 688
7453a54e
SL
689impl<'tcx> LocalFulfilledPredicates<'tcx> {
690 pub fn new() -> LocalFulfilledPredicates<'tcx> {
691 LocalFulfilledPredicates {
e9174d1e 692 set: FnvHashSet()
62682a34
SL
693 }
694 }
695
9cc50fc6 696 fn is_duplicate_or_add(&mut self, key: &ty::Predicate<'tcx>) -> bool {
7453a54e
SL
697 // For a `LocalFulfilledPredicates`, if we find a match, we
698 // don't need to add a read edge to the dep-graph. This is
699 // because it means that the predicate has already been
700 // considered by this `FulfillmentContext`, and hence the
701 // containing task will already have an edge. (Here we are
702 // assuming each `FulfillmentContext` only gets used from one
703 // task; but to do otherwise makes no sense)
9cc50fc6 704 !self.set.insert(key.clone())
62682a34
SL
705 }
706}
7453a54e
SL
707
708impl<'tcx> GlobalFulfilledPredicates<'tcx> {
709 pub fn new(dep_graph: DepGraph) -> GlobalFulfilledPredicates<'tcx> {
710 GlobalFulfilledPredicates {
711 set: FnvHashSet(),
712 dep_graph: dep_graph,
713 }
714 }
715
716 pub fn check_duplicate(&self, key: &ty::Predicate<'tcx>) -> bool {
717 if let ty::Predicate::Trait(ref data) = *key {
718 self.check_duplicate_trait(data)
719 } else {
720 false
721 }
722 }
723
724 pub fn check_duplicate_trait(&self, data: &ty::PolyTraitPredicate<'tcx>) -> bool {
725 // For the global predicate registry, when we find a match, it
726 // may have been computed by some other task, so we want to
727 // add a read from the node corresponding to the predicate
728 // processing to make sure we get the transitive dependencies.
729 if self.set.contains(data) {
730 debug_assert!(data.is_global());
731 self.dep_graph.read(data.dep_node());
732 debug!("check_duplicate: global predicate `{:?}` already proved elsewhere", data);
733
734 info!("check_duplicate_trait hit: `{:?}`", data);
735
736 true
737 } else {
738 false
739 }
740 }
741
742 fn add_if_global(&mut self, key: &ty::Predicate<'tcx>) {
743 if let ty::Predicate::Trait(ref data) = *key {
744 // We only add things to the global predicate registry
745 // after the current task has proved them, and hence
746 // already has the required read edges, so we don't need
747 // to add any more edges here.
748 if data.is_global() {
749 if self.set.insert(data.clone()) {
750 debug!("add_if_global: global predicate `{:?}` added", data);
751 info!("check_duplicate_trait entry: `{:?}`", data);
752 }
753 }
754 }
755 }
756}
757
758fn to_fulfillment_error<'tcx>(
759 error: Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>)
760 -> FulfillmentError<'tcx>
761{
762 let obligation = error.backtrace.into_iter().next().unwrap().obligation;
763 FulfillmentError::new(obligation, error.error)
764}