]>
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 | ||
c34b1796 | 11 | use middle::infer::InferCtxt; |
1a4d82fc JJ |
12 | use middle::ty::{self, RegionEscape, Ty}; |
13 | use std::collections::HashSet; | |
1a4d82fc JJ |
14 | use std::default::Default; |
15 | use syntax::ast; | |
16 | use util::common::ErrorReported; | |
17 | use util::ppaux::Repr; | |
18 | use util::nodemap::NodeMap; | |
19 | ||
20 | use super::CodeAmbiguity; | |
21 | use super::CodeProjectionError; | |
22 | use super::CodeSelectionError; | |
23 | use super::FulfillmentError; | |
24 | use super::ObligationCause; | |
25 | use super::PredicateObligation; | |
26 | use super::project; | |
27 | use super::select::SelectionContext; | |
28 | use super::Unimplemented; | |
29 | use super::util::predicate_for_builtin_bound; | |
30 | ||
31 | /// The fulfillment context is used to drive trait resolution. It | |
32 | /// consists of a list of obligations that must be (eventually) | |
33 | /// satisfied. The job is to track which are satisfied, which yielded | |
34 | /// errors, and which are still pending. At any point, users can call | |
35 | /// `select_where_possible`, and the fulfilment context will try to do | |
36 | /// selection, retaining only those obligations that remain | |
37 | /// ambiguous. This may be helpful in pushing type inference | |
38 | /// along. Once all type inference constraints have been generated, the | |
39 | /// method `select_all_or_error` can be used to report any remaining | |
40 | /// ambiguous cases as errors. | |
41 | pub struct FulfillmentContext<'tcx> { | |
42 | // a simple cache that aims to cache *exact duplicate obligations* | |
43 | // and avoid adding them twice. This serves a different purpose | |
44 | // than the `SelectionCache`: it avoids duplicate errors and | |
45 | // permits recursive obligations, which are often generated from | |
46 | // traits like `Send` et al. | |
47 | duplicate_set: HashSet<ty::Predicate<'tcx>>, | |
48 | ||
49 | // A list of all obligations that have been registered with this | |
50 | // fulfillment context. | |
51 | predicates: Vec<PredicateObligation<'tcx>>, | |
52 | ||
53 | // Remembers the count of trait obligations that we have already | |
54 | // attempted to select. This is used to avoid repeating work | |
55 | // when `select_new_obligations` is called. | |
c34b1796 | 56 | attempted_mark: usize, |
1a4d82fc JJ |
57 | |
58 | // A set of constraints that regionck must validate. Each | |
59 | // constraint has the form `T:'a`, meaning "some type `T` must | |
60 | // outlive the lifetime 'a". These constraints derive from | |
61 | // instantiated type parameters. So if you had a struct defined | |
62 | // like | |
63 | // | |
64 | // struct Foo<T:'static> { ... } | |
65 | // | |
66 | // then in some expression `let x = Foo { ... }` it will | |
67 | // instantiate the type parameter `T` with a fresh type `$0`. At | |
68 | // the same time, it will record a region obligation of | |
69 | // `$0:'static`. This will get checked later by regionck. (We | |
70 | // can't generally check these things right away because we have | |
71 | // to wait until types are resolved.) | |
72 | // | |
73 | // These are stored in a map keyed to the id of the innermost | |
74 | // enclosing fn body / static initializer expression. This is | |
75 | // because the location where the obligation was incurred can be | |
76 | // relevant with respect to which sublifetime assumptions are in | |
77 | // place. The reason that we store under the fn-id, and not | |
78 | // something more fine-grained, is so that it is easier for | |
79 | // regionck to be sure that it has found *all* the region | |
80 | // obligations (otherwise, it's easy to fail to walk to a | |
81 | // particular node-id). | |
82 | region_obligations: NodeMap<Vec<RegionObligation<'tcx>>>, | |
83 | } | |
84 | ||
85aaf69f | 85 | #[derive(Clone)] |
1a4d82fc JJ |
86 | pub struct RegionObligation<'tcx> { |
87 | pub sub_region: ty::Region, | |
88 | pub sup_type: Ty<'tcx>, | |
89 | pub cause: ObligationCause<'tcx>, | |
90 | } | |
91 | ||
92 | impl<'tcx> FulfillmentContext<'tcx> { | |
93 | pub fn new() -> FulfillmentContext<'tcx> { | |
94 | FulfillmentContext { | |
95 | duplicate_set: HashSet::new(), | |
96 | predicates: Vec::new(), | |
97 | attempted_mark: 0, | |
85aaf69f | 98 | region_obligations: NodeMap(), |
1a4d82fc JJ |
99 | } |
100 | } | |
101 | ||
102 | /// "Normalize" a projection type `<SomeType as SomeTrait>::X` by | |
103 | /// creating a fresh type variable `$0` as well as a projection | |
104 | /// predicate `<SomeType as SomeTrait>::X == $0`. When the | |
105 | /// inference engine runs, it will attempt to find an impl of | |
106 | /// `SomeTrait` or a where clause that lets us unify `$0` with | |
107 | /// something concrete. If this fails, we'll unify `$0` with | |
108 | /// `projection_ty` again. | |
109 | pub fn normalize_projection_type<'a>(&mut self, | |
110 | infcx: &InferCtxt<'a,'tcx>, | |
85aaf69f | 111 | typer: &ty::ClosureTyper<'tcx>, |
1a4d82fc JJ |
112 | projection_ty: ty::ProjectionTy<'tcx>, |
113 | cause: ObligationCause<'tcx>) | |
114 | -> Ty<'tcx> | |
115 | { | |
116 | debug!("normalize_associated_type(projection_ty={})", | |
117 | projection_ty.repr(infcx.tcx)); | |
118 | ||
119 | assert!(!projection_ty.has_escaping_regions()); | |
120 | ||
121 | // FIXME(#20304) -- cache | |
122 | ||
123 | let mut selcx = SelectionContext::new(infcx, typer); | |
124 | let normalized = project::normalize_projection_type(&mut selcx, projection_ty, cause, 0); | |
125 | ||
85aaf69f | 126 | for obligation in normalized.obligations { |
1a4d82fc JJ |
127 | self.register_predicate_obligation(infcx, obligation); |
128 | } | |
129 | ||
130 | debug!("normalize_associated_type: result={}", normalized.value.repr(infcx.tcx)); | |
131 | ||
132 | normalized.value | |
133 | } | |
134 | ||
135 | pub fn register_builtin_bound<'a>(&mut self, | |
136 | infcx: &InferCtxt<'a,'tcx>, | |
137 | ty: Ty<'tcx>, | |
138 | builtin_bound: ty::BuiltinBound, | |
139 | cause: ObligationCause<'tcx>) | |
140 | { | |
141 | match predicate_for_builtin_bound(infcx.tcx, cause, builtin_bound, 0, ty) { | |
142 | Ok(predicate) => { | |
143 | self.register_predicate_obligation(infcx, predicate); | |
144 | } | |
145 | Err(ErrorReported) => { } | |
146 | } | |
147 | } | |
148 | ||
149 | pub fn register_region_obligation<'a>(&mut self, | |
150 | infcx: &InferCtxt<'a,'tcx>, | |
151 | t_a: Ty<'tcx>, | |
152 | r_b: ty::Region, | |
153 | cause: ObligationCause<'tcx>) | |
154 | { | |
155 | register_region_obligation(infcx.tcx, t_a, r_b, cause, &mut self.region_obligations); | |
156 | } | |
157 | ||
158 | pub fn register_predicate_obligation<'a>(&mut self, | |
159 | infcx: &InferCtxt<'a,'tcx>, | |
160 | obligation: PredicateObligation<'tcx>) | |
161 | { | |
162 | // this helps to reduce duplicate errors, as well as making | |
163 | // debug output much nicer to read and so on. | |
164 | let obligation = infcx.resolve_type_vars_if_possible(&obligation); | |
165 | ||
c34b1796 AL |
166 | assert!(!obligation.has_escaping_regions()); |
167 | ||
1a4d82fc JJ |
168 | if !self.duplicate_set.insert(obligation.predicate.clone()) { |
169 | debug!("register_predicate({}) -- already seen, skip", obligation.repr(infcx.tcx)); | |
170 | return; | |
171 | } | |
172 | ||
173 | debug!("register_predicate({})", obligation.repr(infcx.tcx)); | |
174 | self.predicates.push(obligation); | |
175 | } | |
176 | ||
177 | pub fn region_obligations(&self, | |
178 | body_id: ast::NodeId) | |
179 | -> &[RegionObligation<'tcx>] | |
180 | { | |
181 | match self.region_obligations.get(&body_id) { | |
182 | None => Default::default(), | |
85aaf69f | 183 | Some(vec) => vec, |
1a4d82fc JJ |
184 | } |
185 | } | |
186 | ||
187 | pub fn select_all_or_error<'a>(&mut self, | |
188 | infcx: &InferCtxt<'a,'tcx>, | |
85aaf69f | 189 | typer: &ty::ClosureTyper<'tcx>) |
1a4d82fc JJ |
190 | -> Result<(),Vec<FulfillmentError<'tcx>>> |
191 | { | |
192 | try!(self.select_where_possible(infcx, typer)); | |
193 | ||
194 | // Anything left is ambiguous. | |
195 | let errors: Vec<FulfillmentError> = | |
196 | self.predicates | |
197 | .iter() | |
198 | .map(|o| FulfillmentError::new((*o).clone(), CodeAmbiguity)) | |
199 | .collect(); | |
200 | ||
201 | if errors.is_empty() { | |
202 | Ok(()) | |
203 | } else { | |
204 | Err(errors) | |
205 | } | |
206 | } | |
207 | ||
208 | /// Attempts to select obligations that were registered since the call to a selection routine. | |
209 | /// This is used by the type checker to eagerly attempt to resolve obligations in hopes of | |
210 | /// gaining type information. It'd be equally valid to use `select_where_possible` but it | |
211 | /// results in `O(n^2)` performance (#18208). | |
212 | pub fn select_new_obligations<'a>(&mut self, | |
213 | infcx: &InferCtxt<'a,'tcx>, | |
85aaf69f | 214 | typer: &ty::ClosureTyper<'tcx>) |
1a4d82fc JJ |
215 | -> Result<(),Vec<FulfillmentError<'tcx>>> |
216 | { | |
217 | let mut selcx = SelectionContext::new(infcx, typer); | |
218 | self.select(&mut selcx, true) | |
219 | } | |
220 | ||
221 | pub fn select_where_possible<'a>(&mut self, | |
222 | infcx: &InferCtxt<'a,'tcx>, | |
85aaf69f | 223 | typer: &ty::ClosureTyper<'tcx>) |
1a4d82fc JJ |
224 | -> Result<(),Vec<FulfillmentError<'tcx>>> |
225 | { | |
226 | let mut selcx = SelectionContext::new(infcx, typer); | |
227 | self.select(&mut selcx, false) | |
228 | } | |
229 | ||
230 | pub fn pending_obligations(&self) -> &[PredicateObligation<'tcx>] { | |
c34b1796 | 231 | &self.predicates |
1a4d82fc JJ |
232 | } |
233 | ||
234 | /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it | |
235 | /// only attempts to select obligations that haven't been seen before. | |
236 | fn select<'a>(&mut self, | |
237 | selcx: &mut SelectionContext<'a, 'tcx>, | |
238 | only_new_obligations: bool) | |
239 | -> Result<(),Vec<FulfillmentError<'tcx>>> | |
240 | { | |
241 | debug!("select({} obligations, only_new_obligations={}) start", | |
242 | self.predicates.len(), | |
243 | only_new_obligations); | |
244 | ||
245 | let mut errors = Vec::new(); | |
246 | ||
247 | loop { | |
248 | let count = self.predicates.len(); | |
249 | ||
250 | debug!("select_where_possible({} obligations) iteration", | |
251 | count); | |
252 | ||
253 | let mut new_obligations = Vec::new(); | |
254 | ||
255 | // If we are only attempting obligations we haven't seen yet, | |
256 | // then set `skip` to the number of obligations we've already | |
257 | // seen. | |
258 | let mut skip = if only_new_obligations { | |
259 | self.attempted_mark | |
260 | } else { | |
261 | 0 | |
262 | }; | |
263 | ||
264 | // First pass: walk each obligation, retaining | |
265 | // only those that we cannot yet process. | |
266 | { | |
267 | let region_obligations = &mut self.region_obligations; | |
268 | self.predicates.retain(|predicate| { | |
269 | // Hack: Retain does not pass in the index, but we want | |
270 | // to avoid processing the first `start_count` entries. | |
271 | let processed = | |
272 | if skip == 0 { | |
273 | process_predicate(selcx, predicate, | |
274 | &mut new_obligations, &mut errors, region_obligations) | |
275 | } else { | |
276 | skip -= 1; | |
277 | false | |
278 | }; | |
279 | !processed | |
280 | }); | |
281 | } | |
282 | ||
283 | self.attempted_mark = self.predicates.len(); | |
284 | ||
285 | if self.predicates.len() == count { | |
286 | // Nothing changed. | |
287 | break; | |
288 | } | |
289 | ||
290 | // Now go through all the successful ones, | |
291 | // registering any nested obligations for the future. | |
85aaf69f | 292 | for new_obligation in new_obligations { |
1a4d82fc JJ |
293 | self.register_predicate_obligation(selcx.infcx(), new_obligation); |
294 | } | |
295 | } | |
296 | ||
297 | debug!("select({} obligations, {} errors) done", | |
298 | self.predicates.len(), | |
299 | errors.len()); | |
300 | ||
9346a6ac | 301 | if errors.is_empty() { |
1a4d82fc JJ |
302 | Ok(()) |
303 | } else { | |
304 | Err(errors) | |
305 | } | |
306 | } | |
307 | } | |
308 | ||
309 | fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>, | |
310 | obligation: &PredicateObligation<'tcx>, | |
311 | new_obligations: &mut Vec<PredicateObligation<'tcx>>, | |
312 | errors: &mut Vec<FulfillmentError<'tcx>>, | |
313 | region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>) | |
314 | -> bool | |
315 | { | |
316 | /*! | |
317 | * Processes a predicate obligation and modifies the appropriate | |
318 | * output array with the successful/error result. Returns `false` | |
319 | * if the predicate could not be processed due to insufficient | |
320 | * type inference. | |
321 | */ | |
322 | ||
323 | let tcx = selcx.tcx(); | |
324 | match obligation.predicate { | |
325 | ty::Predicate::Trait(ref data) => { | |
326 | let trait_obligation = obligation.with(data.clone()); | |
327 | match selcx.select(&trait_obligation) { | |
328 | Ok(None) => { | |
329 | false | |
330 | } | |
331 | Ok(Some(s)) => { | |
332 | s.map_move_nested(|p| new_obligations.push(p)); | |
333 | true | |
334 | } | |
335 | Err(selection_err) => { | |
336 | debug!("predicate: {} error: {}", | |
337 | obligation.repr(tcx), | |
338 | selection_err.repr(tcx)); | |
339 | errors.push( | |
340 | FulfillmentError::new( | |
341 | obligation.clone(), | |
342 | CodeSelectionError(selection_err))); | |
343 | true | |
344 | } | |
345 | } | |
346 | } | |
347 | ||
348 | ty::Predicate::Equate(ref binder) => { | |
349 | match selcx.infcx().equality_predicate(obligation.cause.span, binder) { | |
350 | Ok(()) => { } | |
351 | Err(_) => { | |
352 | errors.push( | |
353 | FulfillmentError::new( | |
354 | obligation.clone(), | |
355 | CodeSelectionError(Unimplemented))); | |
356 | } | |
357 | } | |
358 | true | |
359 | } | |
360 | ||
361 | ty::Predicate::RegionOutlives(ref binder) => { | |
362 | match selcx.infcx().region_outlives_predicate(obligation.cause.span, binder) { | |
363 | Ok(()) => { } | |
364 | Err(_) => { | |
365 | errors.push( | |
366 | FulfillmentError::new( | |
367 | obligation.clone(), | |
368 | CodeSelectionError(Unimplemented))); | |
369 | } | |
370 | } | |
371 | ||
372 | true | |
373 | } | |
374 | ||
375 | ty::Predicate::TypeOutlives(ref binder) => { | |
376 | // For now, we just check that there are no higher-ranked | |
377 | // regions. If there are, we will call this obligation an | |
378 | // error. Eventually we should be able to support some | |
379 | // cases here, I imagine (e.g., `for<'a> int : 'a`). | |
380 | if ty::count_late_bound_regions(selcx.tcx(), binder) != 0 { | |
381 | errors.push( | |
382 | FulfillmentError::new( | |
383 | obligation.clone(), | |
384 | CodeSelectionError(Unimplemented))); | |
385 | } else { | |
386 | let ty::OutlivesPredicate(t_a, r_b) = binder.0; | |
387 | register_region_obligation(tcx, t_a, r_b, | |
388 | obligation.cause.clone(), | |
389 | region_obligations); | |
390 | } | |
391 | true | |
392 | } | |
393 | ||
394 | ty::Predicate::Projection(ref data) => { | |
395 | let project_obligation = obligation.with(data.clone()); | |
396 | let result = project::poly_project_and_unify_type(selcx, &project_obligation); | |
85aaf69f | 397 | debug!("process_predicate: poly_project_and_unify_type({}) returned {}", |
1a4d82fc JJ |
398 | project_obligation.repr(tcx), |
399 | result.repr(tcx)); | |
400 | match result { | |
401 | Ok(Some(obligations)) => { | |
402 | new_obligations.extend(obligations.into_iter()); | |
403 | true | |
404 | } | |
405 | Ok(None) => { | |
406 | false | |
407 | } | |
408 | Err(err) => { | |
409 | errors.push( | |
410 | FulfillmentError::new( | |
411 | obligation.clone(), | |
412 | CodeProjectionError(err))); | |
413 | true | |
414 | } | |
415 | } | |
416 | } | |
417 | } | |
418 | } | |
419 | ||
420 | impl<'tcx> Repr<'tcx> for RegionObligation<'tcx> { | |
421 | fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String { | |
422 | format!("RegionObligation(sub_region={}, sup_type={})", | |
423 | self.sub_region.repr(tcx), | |
424 | self.sup_type.repr(tcx)) | |
425 | } | |
426 | } | |
427 | ||
428 | fn register_region_obligation<'tcx>(tcx: &ty::ctxt<'tcx>, | |
429 | t_a: Ty<'tcx>, | |
430 | r_b: ty::Region, | |
431 | cause: ObligationCause<'tcx>, | |
432 | region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>) | |
433 | { | |
434 | let region_obligation = RegionObligation { sup_type: t_a, | |
435 | sub_region: r_b, | |
436 | cause: cause }; | |
437 | ||
438 | debug!("register_region_obligation({})", | |
439 | region_obligation.repr(tcx)); | |
440 | ||
c34b1796 AL |
441 | region_obligations.entry(region_obligation.cause.body_id).or_insert(vec![]) |
442 | .push(region_obligation); | |
1a4d82fc JJ |
443 | |
444 | } |