]>
Commit | Line | Data |
---|---|---|
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 | 11 | use dep_graph::DepGraph; |
c34b1796 | 12 | use middle::infer::InferCtxt; |
7453a54e SL |
13 | use middle::ty::{self, Ty, TypeFoldable, ToPolyTraitRef}; |
14 | use rustc_data_structures::obligation_forest::{Backtrace, ObligationForest, Error}; | |
15 | use std::iter; | |
1a4d82fc JJ |
16 | use syntax::ast; |
17 | use util::common::ErrorReported; | |
7453a54e | 18 | use util::nodemap::{FnvHashMap, FnvHashSet, NodeMap}; |
1a4d82fc JJ |
19 | |
20 | use super::CodeAmbiguity; | |
21 | use super::CodeProjectionError; | |
22 | use super::CodeSelectionError; | |
e9174d1e | 23 | use super::is_object_safe; |
1a4d82fc | 24 | use super::FulfillmentError; |
7453a54e | 25 | use super::FulfillmentErrorCode; |
1a4d82fc JJ |
26 | use super::ObligationCause; |
27 | use super::PredicateObligation; | |
28 | use super::project; | |
7453a54e | 29 | use super::report_overflow_error_cycle; |
1a4d82fc JJ |
30 | use super::select::SelectionContext; |
31 | use super::Unimplemented; | |
32 | use super::util::predicate_for_builtin_bound; | |
33 | ||
7453a54e SL |
34 | pub struct GlobalFulfilledPredicates<'tcx> { |
35 | set: FnvHashSet<ty::PolyTraitPredicate<'tcx>>, | |
36 | dep_graph: DepGraph, | |
37 | } | |
38 | ||
39 | #[derive(Debug)] | |
40 | pub 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. | |
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. | |
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 |
101 | pub 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)] |
108 | pub struct PendingPredicateObligation<'tcx> { | |
109 | pub obligation: PredicateObligation<'tcx>, | |
110 | pub stalled_on: Vec<Ty<'tcx>>, | |
111 | } | |
112 | ||
1a4d82fc | 113 | impl<'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 | 320 | fn 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 | |
422 | fn 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 | |
439 | fn 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. | |
617 | fn 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 | ||
650 | fn 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 | 671 | fn 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 |
689 | impl<'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 | |
708 | impl<'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 | ||
758 | fn 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 | } |