]>
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; |
54a0048b | 12 | use infer::{InferCtxt, InferOk}; |
5bcae85e SL |
13 | use ty::{self, Ty, TypeFoldable, ToPolyTraitRef, TyCtxt, ToPredicate}; |
14 | use ty::subst::{Substs, Subst}; | |
a7813a04 XL |
15 | use rustc_data_structures::obligation_forest::{ObligationForest, Error}; |
16 | use rustc_data_structures::obligation_forest::{ForestObligation, ObligationProcessor}; | |
17 | use std::marker::PhantomData; | |
18 | use std::mem; | |
1a4d82fc JJ |
19 | use syntax::ast; |
20 | use util::common::ErrorReported; | |
a7813a04 | 21 | use util::nodemap::{FnvHashSet, NodeMap}; |
1a4d82fc JJ |
22 | |
23 | use super::CodeAmbiguity; | |
24 | use super::CodeProjectionError; | |
25 | use super::CodeSelectionError; | |
5bcae85e SL |
26 | use super::{FulfillmentError, FulfillmentErrorCode, SelectionError}; |
27 | use super::{ObligationCause, BuiltinDerivedObligation}; | |
28 | use super::{PredicateObligation, TraitObligation, Obligation}; | |
1a4d82fc JJ |
29 | use super::project; |
30 | use super::select::SelectionContext; | |
31 | use super::Unimplemented; | |
a7813a04 XL |
32 | |
33 | impl<'tcx> ForestObligation for PendingPredicateObligation<'tcx> { | |
34 | type Predicate = ty::Predicate<'tcx>; | |
35 | ||
36 | fn as_predicate(&self) -> &Self::Predicate { &self.obligation.predicate } | |
37 | } | |
1a4d82fc | 38 | |
7453a54e SL |
39 | pub struct GlobalFulfilledPredicates<'tcx> { |
40 | set: FnvHashSet<ty::PolyTraitPredicate<'tcx>>, | |
41 | dep_graph: DepGraph, | |
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. | |
5bcae85e | 54 | |
1a4d82fc | 55 | pub struct FulfillmentContext<'tcx> { |
1a4d82fc JJ |
56 | // A list of all obligations that have been registered with this |
57 | // fulfillment context. | |
a7813a04 XL |
58 | predicates: ObligationForest<PendingPredicateObligation<'tcx>>, |
59 | ||
60 | // A list of new obligations due to RFC1592. | |
61 | rfc1592_obligations: Vec<PredicateObligation<'tcx>>, | |
1a4d82fc JJ |
62 | |
63 | // A set of constraints that regionck must validate. Each | |
64 | // constraint has the form `T:'a`, meaning "some type `T` must | |
65 | // outlive the lifetime 'a". These constraints derive from | |
66 | // instantiated type parameters. So if you had a struct defined | |
67 | // like | |
68 | // | |
69 | // struct Foo<T:'static> { ... } | |
70 | // | |
71 | // then in some expression `let x = Foo { ... }` it will | |
72 | // instantiate the type parameter `T` with a fresh type `$0`. At | |
73 | // the same time, it will record a region obligation of | |
74 | // `$0:'static`. This will get checked later by regionck. (We | |
75 | // can't generally check these things right away because we have | |
76 | // to wait until types are resolved.) | |
77 | // | |
78 | // These are stored in a map keyed to the id of the innermost | |
79 | // enclosing fn body / static initializer expression. This is | |
80 | // because the location where the obligation was incurred can be | |
81 | // relevant with respect to which sublifetime assumptions are in | |
82 | // place. The reason that we store under the fn-id, and not | |
83 | // something more fine-grained, is so that it is easier for | |
84 | // regionck to be sure that it has found *all* the region | |
85 | // obligations (otherwise, it's easy to fail to walk to a | |
86 | // particular node-id). | |
87 | region_obligations: NodeMap<Vec<RegionObligation<'tcx>>>, | |
5bcae85e SL |
88 | |
89 | // A list of obligations that need to be deferred to | |
90 | // a later time for them to be properly fulfilled. | |
91 | deferred_obligations: Vec<DeferredObligation<'tcx>>, | |
1a4d82fc JJ |
92 | } |
93 | ||
85aaf69f | 94 | #[derive(Clone)] |
1a4d82fc JJ |
95 | pub struct RegionObligation<'tcx> { |
96 | pub sub_region: ty::Region, | |
97 | pub sup_type: Ty<'tcx>, | |
98 | pub cause: ObligationCause<'tcx>, | |
99 | } | |
100 | ||
7453a54e SL |
101 | #[derive(Clone, Debug)] |
102 | pub struct PendingPredicateObligation<'tcx> { | |
103 | pub obligation: PredicateObligation<'tcx>, | |
104 | pub stalled_on: Vec<Ty<'tcx>>, | |
105 | } | |
106 | ||
5bcae85e SL |
107 | /// An obligation which cannot be fulfilled in the context |
108 | /// it was registered in, such as auto trait obligations on | |
109 | /// `impl Trait`, which require the concrete type to be | |
110 | /// available, only guaranteed after finishing type-checking. | |
111 | #[derive(Clone, Debug)] | |
112 | pub struct DeferredObligation<'tcx> { | |
113 | pub predicate: ty::PolyTraitPredicate<'tcx>, | |
114 | pub cause: ObligationCause<'tcx> | |
115 | } | |
116 | ||
117 | impl<'a, 'gcx, 'tcx> DeferredObligation<'tcx> { | |
118 | /// If possible, create a `DeferredObligation` from | |
119 | /// a trait predicate which had failed selection, | |
120 | /// but could succeed later. | |
121 | pub fn from_select_error(tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
122 | obligation: &TraitObligation<'tcx>, | |
123 | selection_err: &SelectionError<'tcx>) | |
124 | -> Option<DeferredObligation<'tcx>> { | |
125 | if let Unimplemented = *selection_err { | |
126 | if DeferredObligation::must_defer(tcx, &obligation.predicate) { | |
127 | return Some(DeferredObligation { | |
128 | predicate: obligation.predicate.clone(), | |
129 | cause: obligation.cause.clone() | |
130 | }); | |
131 | } | |
132 | } | |
133 | ||
134 | None | |
135 | } | |
136 | ||
137 | /// Returns true if the given trait predicate can be | |
138 | /// fulfilled at a later time. | |
139 | pub fn must_defer(tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
140 | predicate: &ty::PolyTraitPredicate<'tcx>) | |
141 | -> bool { | |
142 | // Auto trait obligations on `impl Trait`. | |
143 | if tcx.trait_has_default_impl(predicate.def_id()) { | |
144 | let substs = predicate.skip_binder().trait_ref.substs; | |
145 | if substs.types.as_slice().len() == 1 && substs.regions.is_empty() { | |
146 | if let ty::TyAnon(..) = predicate.skip_binder().self_ty().sty { | |
147 | return true; | |
148 | } | |
149 | } | |
150 | } | |
151 | ||
152 | false | |
153 | } | |
154 | ||
155 | /// If possible, return the nested obligations required | |
156 | /// to fulfill this obligation. | |
157 | pub fn try_select(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) | |
158 | -> Option<Vec<PredicateObligation<'tcx>>> { | |
159 | if let ty::TyAnon(def_id, substs) = self.predicate.skip_binder().self_ty().sty { | |
160 | // We can resolve the `impl Trait` to its concrete type. | |
161 | if let Some(ty_scheme) = tcx.opt_lookup_item_type(def_id) { | |
162 | let concrete_ty = ty_scheme.ty.subst(tcx, substs); | |
163 | let concrete_substs = Substs::new_trait(vec![], vec![], concrete_ty); | |
164 | let predicate = ty::TraitRef { | |
165 | def_id: self.predicate.def_id(), | |
166 | substs: tcx.mk_substs(concrete_substs) | |
167 | }.to_predicate(); | |
168 | ||
169 | let original_obligation = Obligation::new(self.cause.clone(), | |
170 | self.predicate.clone()); | |
171 | let cause = original_obligation.derived_cause(BuiltinDerivedObligation); | |
172 | return Some(vec![Obligation::new(cause, predicate)]); | |
173 | } | |
174 | } | |
175 | ||
176 | None | |
177 | } | |
178 | ||
179 | /// Return the `PredicateObligation` this was created from. | |
180 | pub fn to_obligation(&self) -> PredicateObligation<'tcx> { | |
181 | let predicate = ty::Predicate::Trait(self.predicate.clone()); | |
182 | Obligation::new(self.cause.clone(), predicate) | |
183 | } | |
184 | ||
185 | /// Return an error as if this obligation had failed. | |
186 | pub fn to_error(&self) -> FulfillmentError<'tcx> { | |
187 | FulfillmentError::new(self.to_obligation(), CodeSelectionError(Unimplemented)) | |
188 | } | |
189 | } | |
190 | ||
a7813a04 | 191 | impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> { |
62682a34 | 192 | /// Creates a new fulfillment context. |
7453a54e | 193 | pub fn new() -> FulfillmentContext<'tcx> { |
1a4d82fc | 194 | FulfillmentContext { |
7453a54e | 195 | predicates: ObligationForest::new(), |
a7813a04 | 196 | rfc1592_obligations: Vec::new(), |
85aaf69f | 197 | region_obligations: NodeMap(), |
5bcae85e | 198 | deferred_obligations: vec![], |
1a4d82fc JJ |
199 | } |
200 | } | |
201 | ||
202 | /// "Normalize" a projection type `<SomeType as SomeTrait>::X` by | |
203 | /// creating a fresh type variable `$0` as well as a projection | |
204 | /// predicate `<SomeType as SomeTrait>::X == $0`. When the | |
205 | /// inference engine runs, it will attempt to find an impl of | |
206 | /// `SomeTrait` or a where clause that lets us unify `$0` with | |
207 | /// something concrete. If this fails, we'll unify `$0` with | |
208 | /// `projection_ty` again. | |
a7813a04 XL |
209 | pub fn normalize_projection_type(&mut self, |
210 | infcx: &InferCtxt<'a, 'gcx, 'tcx>, | |
211 | projection_ty: ty::ProjectionTy<'tcx>, | |
212 | cause: ObligationCause<'tcx>) | |
213 | -> Ty<'tcx> | |
1a4d82fc | 214 | { |
7453a54e | 215 | debug!("normalize_projection_type(projection_ty={:?})", |
62682a34 | 216 | projection_ty); |
1a4d82fc JJ |
217 | |
218 | assert!(!projection_ty.has_escaping_regions()); | |
219 | ||
220 | // FIXME(#20304) -- cache | |
221 | ||
c1a9b12d | 222 | let mut selcx = SelectionContext::new(infcx); |
1a4d82fc JJ |
223 | let normalized = project::normalize_projection_type(&mut selcx, projection_ty, cause, 0); |
224 | ||
85aaf69f | 225 | for obligation in normalized.obligations { |
1a4d82fc JJ |
226 | self.register_predicate_obligation(infcx, obligation); |
227 | } | |
228 | ||
7453a54e | 229 | debug!("normalize_projection_type: result={:?}", normalized.value); |
1a4d82fc JJ |
230 | |
231 | normalized.value | |
232 | } | |
233 | ||
a7813a04 XL |
234 | pub fn register_builtin_bound(&mut self, |
235 | infcx: &InferCtxt<'a, 'gcx, 'tcx>, | |
236 | ty: Ty<'tcx>, | |
237 | builtin_bound: ty::BuiltinBound, | |
238 | cause: ObligationCause<'tcx>) | |
1a4d82fc | 239 | { |
a7813a04 | 240 | match infcx.tcx.predicate_for_builtin_bound(cause, builtin_bound, 0, ty) { |
1a4d82fc JJ |
241 | Ok(predicate) => { |
242 | self.register_predicate_obligation(infcx, predicate); | |
243 | } | |
244 | Err(ErrorReported) => { } | |
245 | } | |
246 | } | |
247 | ||
a7813a04 XL |
248 | pub fn register_region_obligation(&mut self, |
249 | t_a: Ty<'tcx>, | |
250 | r_b: ty::Region, | |
251 | cause: ObligationCause<'tcx>) | |
1a4d82fc | 252 | { |
62682a34 | 253 | register_region_obligation(t_a, r_b, cause, &mut self.region_obligations); |
1a4d82fc JJ |
254 | } |
255 | ||
a7813a04 XL |
256 | pub fn register_predicate_obligation(&mut self, |
257 | infcx: &InferCtxt<'a, 'gcx, 'tcx>, | |
258 | obligation: PredicateObligation<'tcx>) | |
1a4d82fc JJ |
259 | { |
260 | // this helps to reduce duplicate errors, as well as making | |
261 | // debug output much nicer to read and so on. | |
262 | let obligation = infcx.resolve_type_vars_if_possible(&obligation); | |
263 | ||
3157f602 XL |
264 | debug!("register_predicate_obligation(obligation={:?})", obligation); |
265 | ||
266 | infcx.obligations_in_snapshot.set(true); | |
267 | ||
268 | if infcx.tcx.fulfilled_predicates.borrow().check_duplicate(&obligation.predicate) { | |
269 | debug!("register_predicate_obligation: duplicate"); | |
a7813a04 | 270 | return |
1a4d82fc JJ |
271 | } |
272 | ||
a7813a04 | 273 | self.predicates.register_obligation(PendingPredicateObligation { |
7453a54e SL |
274 | obligation: obligation, |
275 | stalled_on: vec![] | |
a7813a04 XL |
276 | }); |
277 | } | |
278 | ||
279 | pub fn register_rfc1592_obligation(&mut self, | |
280 | _infcx: &InferCtxt<'a, 'gcx, 'tcx>, | |
281 | obligation: PredicateObligation<'tcx>) | |
282 | { | |
283 | self.rfc1592_obligations.push(obligation); | |
1a4d82fc JJ |
284 | } |
285 | ||
286 | pub fn region_obligations(&self, | |
287 | body_id: ast::NodeId) | |
288 | -> &[RegionObligation<'tcx>] | |
289 | { | |
290 | match self.region_obligations.get(&body_id) { | |
291 | None => Default::default(), | |
85aaf69f | 292 | Some(vec) => vec, |
1a4d82fc JJ |
293 | } |
294 | } | |
295 | ||
a7813a04 XL |
296 | pub fn select_rfc1592_obligations(&mut self, |
297 | infcx: &InferCtxt<'a, 'gcx, 'tcx>) | |
298 | -> Result<(),Vec<FulfillmentError<'tcx>>> | |
299 | { | |
300 | while !self.rfc1592_obligations.is_empty() { | |
301 | for obligation in mem::replace(&mut self.rfc1592_obligations, Vec::new()) { | |
302 | self.register_predicate_obligation(infcx, obligation); | |
303 | } | |
304 | ||
305 | self.select_all_or_error(infcx)?; | |
306 | } | |
307 | ||
308 | Ok(()) | |
309 | } | |
310 | ||
311 | pub fn select_all_or_error(&mut self, | |
312 | infcx: &InferCtxt<'a, 'gcx, 'tcx>) | |
313 | -> Result<(),Vec<FulfillmentError<'tcx>>> | |
1a4d82fc | 314 | { |
54a0048b | 315 | self.select_where_possible(infcx)?; |
a7813a04 | 316 | |
5bcae85e SL |
317 | // Fail all of the deferred obligations that haven't |
318 | // been otherwise removed from the context. | |
319 | let deferred_errors = self.deferred_obligations.iter() | |
320 | .map(|d| d.to_error()); | |
321 | ||
7453a54e SL |
322 | let errors: Vec<_> = |
323 | self.predicates.to_errors(CodeAmbiguity) | |
324 | .into_iter() | |
325 | .map(|e| to_fulfillment_error(e)) | |
5bcae85e | 326 | .chain(deferred_errors) |
7453a54e | 327 | .collect(); |
1a4d82fc JJ |
328 | if errors.is_empty() { |
329 | Ok(()) | |
330 | } else { | |
331 | Err(errors) | |
332 | } | |
333 | } | |
334 | ||
a7813a04 XL |
335 | pub fn select_where_possible(&mut self, |
336 | infcx: &InferCtxt<'a, 'gcx, 'tcx>) | |
337 | -> Result<(),Vec<FulfillmentError<'tcx>>> | |
1a4d82fc | 338 | { |
c1a9b12d | 339 | let mut selcx = SelectionContext::new(infcx); |
7453a54e | 340 | self.select(&mut selcx) |
1a4d82fc JJ |
341 | } |
342 | ||
7453a54e SL |
343 | pub fn pending_obligations(&self) -> Vec<PendingPredicateObligation<'tcx>> { |
344 | self.predicates.pending_obligations() | |
1a4d82fc JJ |
345 | } |
346 | ||
5bcae85e SL |
347 | pub fn take_deferred_obligations(&mut self) -> Vec<DeferredObligation<'tcx>> { |
348 | mem::replace(&mut self.deferred_obligations, vec![]) | |
349 | } | |
350 | ||
1a4d82fc JJ |
351 | /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it |
352 | /// only attempts to select obligations that haven't been seen before. | |
a7813a04 XL |
353 | fn select(&mut self, selcx: &mut SelectionContext<'a, 'gcx, 'tcx>) |
354 | -> Result<(),Vec<FulfillmentError<'tcx>>> { | |
7453a54e | 355 | debug!("select(obligation-forest-size={})", self.predicates.len()); |
1a4d82fc JJ |
356 | |
357 | let mut errors = Vec::new(); | |
358 | ||
359 | loop { | |
7453a54e | 360 | debug!("select: starting another iteration"); |
1a4d82fc | 361 | |
7453a54e | 362 | // Process pending obligations. |
a7813a04 | 363 | let outcome = self.predicates.process_obligations(&mut FulfillProcessor { |
5bcae85e SL |
364 | selcx: selcx, |
365 | region_obligations: &mut self.region_obligations, | |
366 | rfc1592_obligations: &mut self.rfc1592_obligations, | |
367 | deferred_obligations: &mut self.deferred_obligations | |
a7813a04 | 368 | }); |
7453a54e SL |
369 | debug!("select: outcome={:?}", outcome); |
370 | ||
371 | // these are obligations that were proven to be true. | |
372 | for pending_obligation in outcome.completed { | |
373 | let predicate = &pending_obligation.obligation.predicate; | |
a7813a04 XL |
374 | selcx.tcx().fulfilled_predicates.borrow_mut() |
375 | .add_if_global(selcx.tcx(), predicate); | |
1a4d82fc JJ |
376 | } |
377 | ||
7453a54e SL |
378 | errors.extend( |
379 | outcome.errors.into_iter() | |
380 | .map(|e| to_fulfillment_error(e))); | |
1a4d82fc | 381 | |
7453a54e SL |
382 | // If nothing new was added, no need to keep looping. |
383 | if outcome.stalled { | |
1a4d82fc JJ |
384 | break; |
385 | } | |
1a4d82fc JJ |
386 | } |
387 | ||
7453a54e SL |
388 | debug!("select({} predicates remaining, {} errors) done", |
389 | self.predicates.len(), errors.len()); | |
1a4d82fc | 390 | |
9346a6ac | 391 | if errors.is_empty() { |
1a4d82fc JJ |
392 | Ok(()) |
393 | } else { | |
394 | Err(errors) | |
395 | } | |
396 | } | |
397 | } | |
398 | ||
a7813a04 XL |
399 | struct FulfillProcessor<'a, 'b: 'a, 'gcx: 'tcx, 'tcx: 'b> { |
400 | selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>, | |
401 | region_obligations: &'a mut NodeMap<Vec<RegionObligation<'tcx>>>, | |
5bcae85e SL |
402 | rfc1592_obligations: &'a mut Vec<PredicateObligation<'tcx>>, |
403 | deferred_obligations: &'a mut Vec<DeferredObligation<'tcx>> | |
54a0048b SL |
404 | } |
405 | ||
a7813a04 XL |
406 | impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx, 'tcx> { |
407 | type Obligation = PendingPredicateObligation<'tcx>; | |
408 | type Error = FulfillmentErrorCode<'tcx>; | |
7453a54e | 409 | |
a7813a04 XL |
410 | fn process_obligation(&mut self, |
411 | obligation: &mut Self::Obligation) | |
412 | -> Result<Option<Vec<Self::Obligation>>, Self::Error> | |
413 | { | |
414 | process_predicate(self.selcx, | |
415 | obligation, | |
416 | self.region_obligations, | |
5bcae85e SL |
417 | self.rfc1592_obligations, |
418 | self.deferred_obligations) | |
a7813a04 XL |
419 | .map(|os| os.map(|os| os.into_iter().map(|o| PendingPredicateObligation { |
420 | obligation: o, | |
421 | stalled_on: vec![] | |
422 | }).collect())) | |
7453a54e | 423 | } |
7453a54e | 424 | |
a7813a04 XL |
425 | fn process_backedge<'c, I>(&mut self, cycle: I, |
426 | _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>) | |
427 | where I: Clone + Iterator<Item=&'c PendingPredicateObligation<'tcx>>, | |
428 | { | |
429 | if coinductive_match(self.selcx, cycle.clone()) { | |
430 | debug!("process_child_obligations: coinductive match"); | |
431 | } else { | |
432 | let cycle : Vec<_> = cycle.map(|c| c.obligation.clone()).collect(); | |
433 | self.selcx.infcx().report_overflow_error_cycle(&cycle); | |
54a0048b | 434 | } |
54a0048b SL |
435 | } |
436 | } | |
7453a54e SL |
437 | |
438 | /// Return the set of type variables contained in a trait ref | |
a7813a04 XL |
439 | fn trait_ref_type_vars<'a, 'gcx, 'tcx>(selcx: &mut SelectionContext<'a, 'gcx, 'tcx>, |
440 | t: ty::PolyTraitRef<'tcx>) -> Vec<Ty<'tcx>> | |
7453a54e SL |
441 | { |
442 | t.skip_binder() // ok b/c this check doesn't care about regions | |
443 | .input_types() | |
444 | .iter() | |
445 | .map(|t| selcx.infcx().resolve_type_vars_if_possible(t)) | |
446 | .filter(|t| t.has_infer_types()) | |
447 | .flat_map(|t| t.walk()) | |
448 | .filter(|t| match t.sty { ty::TyInfer(_) => true, _ => false }) | |
449 | .collect() | |
450 | } | |
451 | ||
452 | /// Processes a predicate obligation and returns either: | |
453 | /// - `Ok(Some(v))` if the predicate is true, presuming that `v` are also true | |
454 | /// - `Ok(None)` if we don't have enough info to be sure | |
455 | /// - `Err` if the predicate does not hold | |
a7813a04 XL |
456 | fn process_predicate<'a, 'gcx, 'tcx>( |
457 | selcx: &mut SelectionContext<'a, 'gcx, 'tcx>, | |
458 | pending_obligation: &mut PendingPredicateObligation<'tcx>, | |
459 | region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>, | |
5bcae85e SL |
460 | rfc1592_obligations: &mut Vec<PredicateObligation<'tcx>>, |
461 | deferred_obligations: &mut Vec<DeferredObligation<'tcx>>) | |
a7813a04 XL |
462 | -> Result<Option<Vec<PredicateObligation<'tcx>>>, |
463 | FulfillmentErrorCode<'tcx>> | |
7453a54e SL |
464 | { |
465 | // if we were stalled on some unresolved variables, first check | |
466 | // whether any of them have been resolved; if not, don't bother | |
467 | // doing more work yet | |
468 | if !pending_obligation.stalled_on.is_empty() { | |
469 | if pending_obligation.stalled_on.iter().all(|&ty| { | |
470 | let resolved_ty = selcx.infcx().shallow_resolve(&ty); | |
471 | resolved_ty == ty // nothing changed here | |
472 | }) { | |
473 | debug!("process_predicate: pending obligation {:?} still stalled on {:?}", | |
474 | selcx.infcx().resolve_type_vars_if_possible(&pending_obligation.obligation), | |
475 | pending_obligation.stalled_on); | |
476 | return Ok(None); | |
477 | } | |
478 | pending_obligation.stalled_on = vec![]; | |
479 | } | |
480 | ||
481 | let obligation = &mut pending_obligation.obligation; | |
482 | ||
7453a54e SL |
483 | if obligation.predicate.has_infer_types() { |
484 | obligation.predicate = selcx.infcx().resolve_type_vars_if_possible(&obligation.predicate); | |
485 | } | |
1a4d82fc | 486 | |
1a4d82fc JJ |
487 | match obligation.predicate { |
488 | ty::Predicate::Trait(ref data) => { | |
7453a54e SL |
489 | if selcx.tcx().fulfilled_predicates.borrow().check_duplicate_trait(data) { |
490 | return Ok(Some(vec![])); | |
491 | } | |
492 | ||
1a4d82fc JJ |
493 | let trait_obligation = obligation.with(data.clone()); |
494 | match selcx.select(&trait_obligation) { | |
7453a54e | 495 | Ok(Some(vtable)) => { |
a7813a04 | 496 | debug!("selecting trait `{:?}` at depth {} yielded Ok(Some)", |
7453a54e SL |
497 | data, obligation.recursion_depth); |
498 | Ok(Some(vtable.nested_obligations())) | |
1a4d82fc | 499 | } |
7453a54e | 500 | Ok(None) => { |
a7813a04 | 501 | debug!("selecting trait `{:?}` at depth {} yielded Ok(None)", |
7453a54e SL |
502 | data, obligation.recursion_depth); |
503 | ||
504 | // This is a bit subtle: for the most part, the | |
505 | // only reason we can fail to make progress on | |
506 | // trait selection is because we don't have enough | |
507 | // information about the types in the trait. One | |
508 | // exception is that we sometimes haven't decided | |
509 | // what kind of closure a closure is. *But*, in | |
510 | // that case, it turns out, the type of the | |
511 | // closure will also change, because the closure | |
512 | // also includes references to its upvars as part | |
513 | // of its type, and those types are resolved at | |
514 | // the same time. | |
3157f602 XL |
515 | // |
516 | // FIXME(#32286) logic seems false if no upvars | |
7453a54e SL |
517 | pending_obligation.stalled_on = |
518 | trait_ref_type_vars(selcx, data.to_poly_trait_ref()); | |
519 | ||
520 | debug!("process_predicate: pending obligation {:?} now stalled on {:?}", | |
521 | selcx.infcx().resolve_type_vars_if_possible(obligation), | |
522 | pending_obligation.stalled_on); | |
523 | ||
524 | Ok(None) | |
1a4d82fc JJ |
525 | } |
526 | Err(selection_err) => { | |
7453a54e SL |
527 | info!("selecting trait `{:?}` at depth {} yielded Err", |
528 | data, obligation.recursion_depth); | |
5bcae85e SL |
529 | |
530 | let defer = DeferredObligation::from_select_error(selcx.tcx(), | |
531 | &trait_obligation, | |
532 | &selection_err); | |
533 | if let Some(deferred_obligation) = defer { | |
534 | if let Some(nested) = deferred_obligation.try_select(selcx.tcx()) { | |
535 | Ok(Some(nested)) | |
536 | } else { | |
537 | // Pretend that the obligation succeeded, | |
538 | // but record it for later. | |
539 | deferred_obligations.push(deferred_obligation); | |
540 | Ok(Some(vec![])) | |
541 | } | |
542 | } else { | |
543 | Err(CodeSelectionError(selection_err)) | |
544 | } | |
1a4d82fc JJ |
545 | } |
546 | } | |
547 | } | |
548 | ||
549 | ty::Predicate::Equate(ref binder) => { | |
550 | match selcx.infcx().equality_predicate(obligation.cause.span, binder) { | |
54a0048b SL |
551 | Ok(InferOk { obligations, .. }) => { |
552 | // FIXME(#32730) propagate obligations | |
553 | assert!(obligations.is_empty()); | |
554 | Ok(Some(Vec::new())) | |
555 | }, | |
7453a54e | 556 | Err(_) => Err(CodeSelectionError(Unimplemented)), |
1a4d82fc | 557 | } |
1a4d82fc JJ |
558 | } |
559 | ||
560 | ty::Predicate::RegionOutlives(ref binder) => { | |
561 | match selcx.infcx().region_outlives_predicate(obligation.cause.span, binder) { | |
7453a54e SL |
562 | Ok(()) => Ok(Some(Vec::new())), |
563 | Err(_) => Err(CodeSelectionError(Unimplemented)), | |
1a4d82fc | 564 | } |
1a4d82fc JJ |
565 | } |
566 | ||
567 | ty::Predicate::TypeOutlives(ref binder) => { | |
c1a9b12d SL |
568 | // Check if there are higher-ranked regions. |
569 | match selcx.tcx().no_late_bound_regions(binder) { | |
570 | // If there are, inspect the underlying type further. | |
571 | None => { | |
572 | // Convert from `Binder<OutlivesPredicate<Ty, Region>>` to `Binder<Ty>`. | |
573 | let binder = binder.map_bound_ref(|pred| pred.0); | |
574 | ||
575 | // Check if the type has any bound regions. | |
576 | match selcx.tcx().no_late_bound_regions(&binder) { | |
577 | // If so, this obligation is an error (for now). Eventually we should be | |
578 | // able to support additional cases here, like `for<'a> &'a str: 'a`. | |
579 | None => { | |
7453a54e | 580 | Err(CodeSelectionError(Unimplemented)) |
c1a9b12d SL |
581 | } |
582 | // Otherwise, we have something of the form | |
583 | // `for<'a> T: 'a where 'a not in T`, which we can treat as `T: 'static`. | |
584 | Some(t_a) => { | |
585 | register_region_obligation(t_a, ty::ReStatic, | |
586 | obligation.cause.clone(), | |
587 | region_obligations); | |
7453a54e | 588 | Ok(Some(vec![])) |
c1a9b12d SL |
589 | } |
590 | } | |
591 | } | |
592 | // If there aren't, register the obligation. | |
593 | Some(ty::OutlivesPredicate(t_a, r_b)) => { | |
594 | register_region_obligation(t_a, r_b, | |
595 | obligation.cause.clone(), | |
596 | region_obligations); | |
7453a54e | 597 | Ok(Some(vec![])) |
c1a9b12d | 598 | } |
1a4d82fc | 599 | } |
1a4d82fc JJ |
600 | } |
601 | ||
602 | ty::Predicate::Projection(ref data) => { | |
603 | let project_obligation = obligation.with(data.clone()); | |
7453a54e | 604 | match project::poly_project_and_unify_type(selcx, &project_obligation) { |
1a4d82fc | 605 | Ok(None) => { |
7453a54e SL |
606 | pending_obligation.stalled_on = |
607 | trait_ref_type_vars(selcx, data.to_poly_trait_ref()); | |
608 | Ok(None) | |
1a4d82fc | 609 | } |
7453a54e SL |
610 | Ok(v) => Ok(v), |
611 | Err(e) => Err(CodeProjectionError(e)) | |
1a4d82fc JJ |
612 | } |
613 | } | |
1a4d82fc | 614 | |
e9174d1e | 615 | ty::Predicate::ObjectSafe(trait_def_id) => { |
a7813a04 | 616 | if !selcx.tcx().is_object_safe(trait_def_id) { |
7453a54e SL |
617 | Err(CodeSelectionError(Unimplemented)) |
618 | } else { | |
619 | Ok(Some(Vec::new())) | |
e9174d1e | 620 | } |
e9174d1e SL |
621 | } |
622 | ||
a7813a04 XL |
623 | ty::Predicate::ClosureKind(closure_def_id, kind) => { |
624 | match selcx.infcx().closure_kind(closure_def_id) { | |
625 | Some(closure_kind) => { | |
626 | if closure_kind.extends(kind) { | |
627 | Ok(Some(vec![])) | |
628 | } else { | |
629 | Err(CodeSelectionError(Unimplemented)) | |
630 | } | |
631 | } | |
632 | None => { | |
633 | Ok(None) | |
634 | } | |
635 | } | |
636 | } | |
637 | ||
e9174d1e | 638 | ty::Predicate::WellFormed(ty) => { |
e9174d1e | 639 | match ty::wf::obligations(selcx.infcx(), obligation.cause.body_id, |
9cc50fc6 | 640 | ty, obligation.cause.span) { |
e9174d1e | 641 | None => { |
7453a54e SL |
642 | pending_obligation.stalled_on = vec![ty]; |
643 | Ok(None) | |
e9174d1e | 644 | } |
7453a54e | 645 | s => Ok(s) |
e9174d1e SL |
646 | } |
647 | } | |
a7813a04 XL |
648 | |
649 | ty::Predicate::Rfc1592(ref inner) => { | |
650 | rfc1592_obligations.push(PredicateObligation { | |
651 | predicate: ty::Predicate::clone(inner), | |
652 | ..obligation.clone() | |
653 | }); | |
654 | Ok(Some(vec![])) | |
655 | } | |
1a4d82fc JJ |
656 | } |
657 | } | |
658 | ||
7453a54e SL |
659 | /// For defaulted traits, we use a co-inductive strategy to solve, so |
660 | /// that recursion is ok. This routine returns true if the top of the | |
54a0048b | 661 | /// stack (`cycle[0]`): |
7453a54e SL |
662 | /// - is a defaulted trait, and |
663 | /// - it also appears in the backtrace at some position `X`; and, | |
664 | /// - all the predicates at positions `X..` between `X` an the top are | |
665 | /// also defaulted traits. | |
a7813a04 XL |
666 | fn coinductive_match<'a,'c,'gcx,'tcx,I>(selcx: &mut SelectionContext<'a,'gcx,'tcx>, |
667 | cycle: I) -> bool | |
668 | where I: Iterator<Item=&'c PendingPredicateObligation<'tcx>>, | |
669 | 'tcx: 'c | |
7453a54e | 670 | { |
a7813a04 XL |
671 | let mut cycle = cycle; |
672 | cycle | |
54a0048b | 673 | .all(|bt_obligation| { |
a7813a04 | 674 | let result = coinductive_obligation(selcx, &bt_obligation.obligation); |
54a0048b SL |
675 | debug!("coinductive_match: bt_obligation={:?} coinductive={}", |
676 | bt_obligation, result); | |
677 | result | |
678 | }) | |
7453a54e SL |
679 | } |
680 | ||
a7813a04 XL |
681 | fn coinductive_obligation<'a,'gcx,'tcx>(selcx: &SelectionContext<'a,'gcx,'tcx>, |
682 | obligation: &PredicateObligation<'tcx>) | |
683 | -> bool { | |
54a0048b SL |
684 | match obligation.predicate { |
685 | ty::Predicate::Trait(ref data) => { | |
686 | selcx.tcx().trait_has_default_impl(data.def_id()) | |
687 | } | |
688 | _ => { | |
689 | false | |
7453a54e SL |
690 | } |
691 | } | |
7453a54e SL |
692 | } |
693 | ||
62682a34 | 694 | fn register_region_obligation<'tcx>(t_a: Ty<'tcx>, |
1a4d82fc JJ |
695 | r_b: ty::Region, |
696 | cause: ObligationCause<'tcx>, | |
697 | region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>) | |
698 | { | |
699 | let region_obligation = RegionObligation { sup_type: t_a, | |
700 | sub_region: r_b, | |
701 | cause: cause }; | |
702 | ||
e9174d1e SL |
703 | debug!("register_region_obligation({:?}, cause={:?})", |
704 | region_obligation, region_obligation.cause); | |
1a4d82fc | 705 | |
e9174d1e SL |
706 | region_obligations.entry(region_obligation.cause.body_id) |
707 | .or_insert(vec![]) | |
708 | .push(region_obligation); | |
1a4d82fc JJ |
709 | |
710 | } | |
62682a34 | 711 | |
a7813a04 XL |
712 | impl<'a, 'gcx, 'tcx> GlobalFulfilledPredicates<'gcx> { |
713 | pub fn new(dep_graph: DepGraph) -> GlobalFulfilledPredicates<'gcx> { | |
7453a54e SL |
714 | GlobalFulfilledPredicates { |
715 | set: FnvHashSet(), | |
716 | dep_graph: dep_graph, | |
717 | } | |
718 | } | |
719 | ||
720 | pub fn check_duplicate(&self, key: &ty::Predicate<'tcx>) -> bool { | |
721 | if let ty::Predicate::Trait(ref data) = *key { | |
722 | self.check_duplicate_trait(data) | |
723 | } else { | |
724 | false | |
725 | } | |
726 | } | |
727 | ||
728 | pub fn check_duplicate_trait(&self, data: &ty::PolyTraitPredicate<'tcx>) -> bool { | |
729 | // For the global predicate registry, when we find a match, it | |
730 | // may have been computed by some other task, so we want to | |
731 | // add a read from the node corresponding to the predicate | |
732 | // processing to make sure we get the transitive dependencies. | |
733 | if self.set.contains(data) { | |
734 | debug_assert!(data.is_global()); | |
735 | self.dep_graph.read(data.dep_node()); | |
736 | debug!("check_duplicate: global predicate `{:?}` already proved elsewhere", data); | |
737 | ||
7453a54e SL |
738 | true |
739 | } else { | |
740 | false | |
741 | } | |
742 | } | |
743 | ||
a7813a04 | 744 | fn add_if_global(&mut self, tcx: TyCtxt<'a, 'gcx, 'tcx>, key: &ty::Predicate<'tcx>) { |
7453a54e SL |
745 | if let ty::Predicate::Trait(ref data) = *key { |
746 | // We only add things to the global predicate registry | |
747 | // after the current task has proved them, and hence | |
748 | // already has the required read edges, so we don't need | |
749 | // to add any more edges here. | |
750 | if data.is_global() { | |
5bcae85e SL |
751 | // Don't cache predicates which were fulfilled |
752 | // by deferring them for later fulfillment. | |
753 | if DeferredObligation::must_defer(tcx, data) { | |
754 | return; | |
755 | } | |
756 | ||
a7813a04 XL |
757 | if let Some(data) = tcx.lift_to_global(data) { |
758 | if self.set.insert(data.clone()) { | |
759 | debug!("add_if_global: global predicate `{:?}` added", data); | |
760 | } | |
7453a54e SL |
761 | } |
762 | } | |
763 | } | |
764 | } | |
765 | } | |
766 | ||
767 | fn to_fulfillment_error<'tcx>( | |
768 | error: Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>) | |
769 | -> FulfillmentError<'tcx> | |
770 | { | |
771 | let obligation = error.backtrace.into_iter().next().unwrap().obligation; | |
772 | FulfillmentError::new(obligation, error.error) | |
773 | } |