]> git.proxmox.com Git - rustc.git/blob - src/librustc/infer/higher_ranked/mod.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc / infer / higher_ranked / mod.rs
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
11 //! Helper routines for higher-ranked things. See the `doc` module at
12 //! the end of the file for details.
13
14 use super::{CombinedSnapshot, InferCtxt, HigherRankedType, SkolemizationMap};
15 use super::combine::CombineFields;
16
17 use ty::{self, TyCtxt, Binder, TypeFoldable};
18 use ty::error::TypeError;
19 use ty::relate::{Relate, RelateResult, TypeRelation};
20 use syntax::codemap::Span;
21 use util::nodemap::{FnvHashMap, FnvHashSet};
22
23 pub trait HigherRankedRelations<'a,'tcx> {
24 fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
25 where T: Relate<'a,'tcx>;
26
27 fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
28 where T: Relate<'a,'tcx>;
29
30 fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
31 where T: Relate<'a,'tcx>;
32 }
33
34 trait InferCtxtExt {
35 fn tainted_regions(&self, snapshot: &CombinedSnapshot, r: ty::Region) -> Vec<ty::Region>;
36
37 fn region_vars_confined_to_snapshot(&self,
38 snapshot: &CombinedSnapshot)
39 -> Vec<ty::RegionVid>;
40 }
41
42 impl<'a,'tcx> HigherRankedRelations<'a,'tcx> for CombineFields<'a,'tcx> {
43 fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>)
44 -> RelateResult<'tcx, Binder<T>>
45 where T: Relate<'a,'tcx>
46 {
47 debug!("higher_ranked_sub(a={:?}, b={:?})",
48 a, b);
49
50 // Rather than checking the subtype relationship between `a` and `b`
51 // as-is, we need to do some extra work here in order to make sure
52 // that function subtyping works correctly with respect to regions
53 //
54 // Note: this is a subtle algorithm. For a full explanation,
55 // please see the large comment at the end of the file in the (inlined) module
56 // `doc`.
57
58 // Start a snapshot so we can examine "all bindings that were
59 // created as part of this type comparison".
60 return self.infcx.commit_if_ok(|snapshot| {
61 // First, we instantiate each bound region in the subtype with a fresh
62 // region variable.
63 let (a_prime, _) =
64 self.infcx.replace_late_bound_regions_with_fresh_var(
65 self.trace.origin.span(),
66 HigherRankedType,
67 a);
68
69 // Second, we instantiate each bound region in the supertype with a
70 // fresh concrete region.
71 let (b_prime, skol_map) =
72 self.infcx.skolemize_late_bound_regions(b, snapshot);
73
74 debug!("a_prime={:?}", a_prime);
75 debug!("b_prime={:?}", b_prime);
76
77 // Compare types now that bound regions have been replaced.
78 let result = self.sub().relate(&a_prime, &b_prime)?;
79
80 // Presuming type comparison succeeds, we need to check
81 // that the skolemized regions do not "leak".
82 match leak_check(self.infcx, &skol_map, snapshot) {
83 Ok(()) => { }
84 Err((skol_br, tainted_region)) => {
85 if self.a_is_expected {
86 debug!("Not as polymorphic!");
87 return Err(TypeError::RegionsInsufficientlyPolymorphic(skol_br,
88 tainted_region));
89 } else {
90 debug!("Overly polymorphic!");
91 return Err(TypeError::RegionsOverlyPolymorphic(skol_br,
92 tainted_region));
93 }
94 }
95 }
96
97 debug!("higher_ranked_sub: OK result={:?}",
98 result);
99
100 Ok(ty::Binder(result))
101 });
102 }
103
104 fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
105 where T: Relate<'a,'tcx>
106 {
107 // Start a snapshot so we can examine "all bindings that were
108 // created as part of this type comparison".
109 return self.infcx.commit_if_ok(|snapshot| {
110 // Instantiate each bound region with a fresh region variable.
111 let span = self.trace.origin.span();
112 let (a_with_fresh, a_map) =
113 self.infcx.replace_late_bound_regions_with_fresh_var(
114 span, HigherRankedType, a);
115 let (b_with_fresh, _) =
116 self.infcx.replace_late_bound_regions_with_fresh_var(
117 span, HigherRankedType, b);
118
119 // Collect constraints.
120 let result0 =
121 self.lub().relate(&a_with_fresh, &b_with_fresh)?;
122 let result0 =
123 self.infcx.resolve_type_vars_if_possible(&result0);
124 debug!("lub result0 = {:?}", result0);
125
126 // Generalize the regions appearing in result0 if possible
127 let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot);
128 let span = self.trace.origin.span();
129 let result1 =
130 fold_regions_in(
131 self.tcx(),
132 &result0,
133 |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn,
134 &new_vars, &a_map, r));
135
136 debug!("lub({:?},{:?}) = {:?}",
137 a,
138 b,
139 result1);
140
141 Ok(ty::Binder(result1))
142 });
143
144 fn generalize_region(infcx: &InferCtxt,
145 span: Span,
146 snapshot: &CombinedSnapshot,
147 debruijn: ty::DebruijnIndex,
148 new_vars: &[ty::RegionVid],
149 a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
150 r0: ty::Region)
151 -> ty::Region {
152 // Regions that pre-dated the LUB computation stay as they are.
153 if !is_var_in_set(new_vars, r0) {
154 assert!(!r0.is_bound());
155 debug!("generalize_region(r0={:?}): not new variable", r0);
156 return r0;
157 }
158
159 let tainted = infcx.tainted_regions(snapshot, r0);
160
161 // Variables created during LUB computation which are
162 // *related* to regions that pre-date the LUB computation
163 // stay as they are.
164 if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) {
165 debug!("generalize_region(r0={:?}): \
166 non-new-variables found in {:?}",
167 r0, tainted);
168 assert!(!r0.is_bound());
169 return r0;
170 }
171
172 // Otherwise, the variable must be associated with at
173 // least one of the variables representing bound regions
174 // in both A and B. Replace the variable with the "first"
175 // bound region from A that we find it to be associated
176 // with.
177 for (a_br, a_r) in a_map {
178 if tainted.iter().any(|x| x == a_r) {
179 debug!("generalize_region(r0={:?}): \
180 replacing with {:?}, tainted={:?}",
181 r0, *a_br, tainted);
182 return ty::ReLateBound(debruijn, *a_br);
183 }
184 }
185
186 span_bug!(
187 span,
188 "region {:?} is not associated with any bound region from A!",
189 r0)
190 }
191 }
192
193 fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>>
194 where T: Relate<'a,'tcx>
195 {
196 debug!("higher_ranked_glb({:?}, {:?})",
197 a, b);
198
199 // Make a snapshot so we can examine "all bindings that were
200 // created as part of this type comparison".
201 return self.infcx.commit_if_ok(|snapshot| {
202 // Instantiate each bound region with a fresh region variable.
203 let (a_with_fresh, a_map) =
204 self.infcx.replace_late_bound_regions_with_fresh_var(
205 self.trace.origin.span(), HigherRankedType, a);
206 let (b_with_fresh, b_map) =
207 self.infcx.replace_late_bound_regions_with_fresh_var(
208 self.trace.origin.span(), HigherRankedType, b);
209 let a_vars = var_ids(self, &a_map);
210 let b_vars = var_ids(self, &b_map);
211
212 // Collect constraints.
213 let result0 =
214 self.glb().relate(&a_with_fresh, &b_with_fresh)?;
215 let result0 =
216 self.infcx.resolve_type_vars_if_possible(&result0);
217 debug!("glb result0 = {:?}", result0);
218
219 // Generalize the regions appearing in result0 if possible
220 let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot);
221 let span = self.trace.origin.span();
222 let result1 =
223 fold_regions_in(
224 self.tcx(),
225 &result0,
226 |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn,
227 &new_vars,
228 &a_map, &a_vars, &b_vars,
229 r));
230
231 debug!("glb({:?},{:?}) = {:?}",
232 a,
233 b,
234 result1);
235
236 Ok(ty::Binder(result1))
237 });
238
239 fn generalize_region(infcx: &InferCtxt,
240 span: Span,
241 snapshot: &CombinedSnapshot,
242 debruijn: ty::DebruijnIndex,
243 new_vars: &[ty::RegionVid],
244 a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
245 a_vars: &[ty::RegionVid],
246 b_vars: &[ty::RegionVid],
247 r0: ty::Region) -> ty::Region {
248 if !is_var_in_set(new_vars, r0) {
249 assert!(!r0.is_bound());
250 return r0;
251 }
252
253 let tainted = infcx.tainted_regions(snapshot, r0);
254
255 let mut a_r = None;
256 let mut b_r = None;
257 let mut only_new_vars = true;
258 for r in &tainted {
259 if is_var_in_set(a_vars, *r) {
260 if a_r.is_some() {
261 return fresh_bound_variable(infcx, debruijn);
262 } else {
263 a_r = Some(*r);
264 }
265 } else if is_var_in_set(b_vars, *r) {
266 if b_r.is_some() {
267 return fresh_bound_variable(infcx, debruijn);
268 } else {
269 b_r = Some(*r);
270 }
271 } else if !is_var_in_set(new_vars, *r) {
272 only_new_vars = false;
273 }
274 }
275
276 // NB---I do not believe this algorithm computes
277 // (necessarily) the GLB. As written it can
278 // spuriously fail. In particular, if there is a case
279 // like: |fn(&a)| and fn(fn(&b)), where a and b are
280 // free, it will return fn(&c) where c = GLB(a,b). If
281 // however this GLB is not defined, then the result is
282 // an error, even though something like
283 // "fn<X>(fn(&X))" where X is bound would be a
284 // subtype of both of those.
285 //
286 // The problem is that if we were to return a bound
287 // variable, we'd be computing a lower-bound, but not
288 // necessarily the *greatest* lower-bound.
289 //
290 // Unfortunately, this problem is non-trivial to solve,
291 // because we do not know at the time of computing the GLB
292 // whether a GLB(a,b) exists or not, because we haven't
293 // run region inference (or indeed, even fully computed
294 // the region hierarchy!). The current algorithm seems to
295 // works ok in practice.
296
297 if a_r.is_some() && b_r.is_some() && only_new_vars {
298 // Related to exactly one bound variable from each fn:
299 return rev_lookup(span, a_map, a_r.unwrap());
300 } else if a_r.is_none() && b_r.is_none() {
301 // Not related to bound variables from either fn:
302 assert!(!r0.is_bound());
303 return r0;
304 } else {
305 // Other:
306 return fresh_bound_variable(infcx, debruijn);
307 }
308 }
309
310 fn rev_lookup(span: Span,
311 a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
312 r: ty::Region) -> ty::Region
313 {
314 for (a_br, a_r) in a_map {
315 if *a_r == r {
316 return ty::ReLateBound(ty::DebruijnIndex::new(1), *a_br);
317 }
318 }
319 span_bug!(
320 span,
321 "could not find original bound region for {:?}",
322 r);
323 }
324
325 fn fresh_bound_variable(infcx: &InferCtxt, debruijn: ty::DebruijnIndex) -> ty::Region {
326 infcx.region_vars.new_bound(debruijn)
327 }
328 }
329 }
330
331 fn var_ids<'a, 'tcx>(fields: &CombineFields<'a, 'tcx>,
332 map: &FnvHashMap<ty::BoundRegion, ty::Region>)
333 -> Vec<ty::RegionVid> {
334 map.iter()
335 .map(|(_, r)| match *r {
336 ty::ReVar(r) => { r }
337 r => {
338 span_bug!(
339 fields.trace.origin.span(),
340 "found non-region-vid: {:?}",
341 r);
342 }
343 })
344 .collect()
345 }
346
347 fn is_var_in_set(new_vars: &[ty::RegionVid], r: ty::Region) -> bool {
348 match r {
349 ty::ReVar(ref v) => new_vars.iter().any(|x| x == v),
350 _ => false
351 }
352 }
353
354 fn fold_regions_in<'tcx, T, F>(tcx: &TyCtxt<'tcx>,
355 unbound_value: &T,
356 mut fldr: F)
357 -> T
358 where T: TypeFoldable<'tcx>,
359 F: FnMut(ty::Region, ty::DebruijnIndex) -> ty::Region,
360 {
361 tcx.fold_regions(unbound_value, &mut false, |region, current_depth| {
362 // we should only be encountering "escaping" late-bound regions here,
363 // because the ones at the current level should have been replaced
364 // with fresh variables
365 assert!(match region {
366 ty::ReLateBound(..) => false,
367 _ => true
368 });
369
370 fldr(region, ty::DebruijnIndex::new(current_depth))
371 })
372 }
373
374 impl<'a,'tcx> InferCtxtExt for InferCtxt<'a,'tcx> {
375 fn tainted_regions(&self, snapshot: &CombinedSnapshot, r: ty::Region) -> Vec<ty::Region> {
376 self.region_vars.tainted(&snapshot.region_vars_snapshot, r)
377 }
378
379 fn region_vars_confined_to_snapshot(&self,
380 snapshot: &CombinedSnapshot)
381 -> Vec<ty::RegionVid>
382 {
383 /*!
384 * Returns the set of region variables that do not affect any
385 * types/regions which existed before `snapshot` was
386 * started. This is used in the sub/lub/glb computations. The
387 * idea here is that when we are computing lub/glb of two
388 * regions, we sometimes create intermediate region variables.
389 * Those region variables may touch some of the skolemized or
390 * other "forbidden" regions we created to replace bound
391 * regions, but they don't really represent an "external"
392 * constraint.
393 *
394 * However, sometimes fresh variables are created for other
395 * purposes too, and those *may* represent an external
396 * constraint. In particular, when a type variable is
397 * instantiated, we create region variables for all the
398 * regions that appear within, and if that type variable
399 * pre-existed the snapshot, then those region variables
400 * represent external constraints.
401 *
402 * An example appears in the unit test
403 * `sub_free_bound_false_infer`. In this test, we want to
404 * know whether
405 *
406 * ```rust
407 * fn(_#0t) <: for<'a> fn(&'a int)
408 * ```
409 *
410 * Note that the subtype has a type variable. Because the type
411 * variable can't be instantiated with a region that is bound
412 * in the fn signature, this comparison ought to fail. But if
413 * we're not careful, it will succeed.
414 *
415 * The reason is that when we walk through the subtyping
416 * algorith, we begin by replacing `'a` with a skolemized
417 * variable `'1`. We then have `fn(_#0t) <: fn(&'1 int)`. This
418 * can be made true by unifying `_#0t` with `&'1 int`. In the
419 * process, we create a fresh variable for the skolemized
420 * region, `'$2`, and hence we have that `_#0t == &'$2
421 * int`. However, because `'$2` was created during the sub
422 * computation, if we're not careful we will erroneously
423 * assume it is one of the transient region variables
424 * representing a lub/glb internally. Not good.
425 *
426 * To prevent this, we check for type variables which were
427 * unified during the snapshot, and say that any region
428 * variable created during the snapshot but which finds its
429 * way into a type variable is considered to "escape" the
430 * snapshot.
431 */
432
433 let mut region_vars =
434 self.region_vars.vars_created_since_snapshot(&snapshot.region_vars_snapshot);
435
436 let escaping_types =
437 self.type_variables.borrow_mut().types_escaping_snapshot(&snapshot.type_snapshot);
438
439 let mut escaping_region_vars = FnvHashSet();
440 for ty in &escaping_types {
441 self.tcx.collect_regions(ty, &mut escaping_region_vars);
442 }
443
444 region_vars.retain(|&region_vid| {
445 let r = ty::ReVar(region_vid);
446 !escaping_region_vars.contains(&r)
447 });
448
449 debug!("region_vars_confined_to_snapshot: region_vars={:?} escaping_types={:?}",
450 region_vars,
451 escaping_types);
452
453 region_vars
454 }
455 }
456
457 pub fn skolemize_late_bound_regions<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>,
458 binder: &ty::Binder<T>,
459 snapshot: &CombinedSnapshot)
460 -> (T, SkolemizationMap)
461 where T : TypeFoldable<'tcx>
462 {
463 /*!
464 * Replace all regions bound by `binder` with skolemized regions and
465 * return a map indicating which bound-region was replaced with what
466 * skolemized region. This is the first step of checking subtyping
467 * when higher-ranked things are involved. See `README.md` for more
468 * details.
469 */
470
471 let (result, map) = infcx.tcx.replace_late_bound_regions(binder, |br| {
472 infcx.region_vars.new_skolemized(br, &snapshot.region_vars_snapshot)
473 });
474
475 debug!("skolemize_bound_regions(binder={:?}, result={:?}, map={:?})",
476 binder,
477 result,
478 map);
479
480 (result, map)
481 }
482
483 pub fn leak_check<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
484 skol_map: &SkolemizationMap,
485 snapshot: &CombinedSnapshot)
486 -> Result<(),(ty::BoundRegion,ty::Region)>
487 {
488 /*!
489 * Searches the region constriants created since `snapshot` was started
490 * and checks to determine whether any of the skolemized regions created
491 * in `skol_map` would "escape" -- meaning that they are related to
492 * other regions in some way. If so, the higher-ranked subtyping doesn't
493 * hold. See `README.md` for more details.
494 */
495
496 debug!("leak_check: skol_map={:?}",
497 skol_map);
498
499 let new_vars = infcx.region_vars_confined_to_snapshot(snapshot);
500 for (&skol_br, &skol) in skol_map {
501 let tainted = infcx.tainted_regions(snapshot, skol);
502 for &tainted_region in &tainted {
503 // Each skolemized should only be relatable to itself
504 // or new variables:
505 match tainted_region {
506 ty::ReVar(vid) => {
507 if new_vars.iter().any(|&x| x == vid) { continue; }
508 }
509 _ => {
510 if tainted_region == skol { continue; }
511 }
512 };
513
514 debug!("{:?} (which replaced {:?}) is tainted by {:?}",
515 skol,
516 skol_br,
517 tainted_region);
518
519 // A is not as polymorphic as B:
520 return Err((skol_br, tainted_region));
521 }
522 }
523 Ok(())
524 }
525
526 /// This code converts from skolemized regions back to late-bound
527 /// regions. It works by replacing each region in the taint set of a
528 /// skolemized region with a bound-region. The bound region will be bound
529 /// by the outer-most binder in `value`; the caller must ensure that there is
530 /// such a binder and it is the right place.
531 ///
532 /// This routine is only intended to be used when the leak-check has
533 /// passed; currently, it's used in the trait matching code to create
534 /// a set of nested obligations frmo an impl that matches against
535 /// something higher-ranked. More details can be found in
536 /// `librustc/middle/traits/README.md`.
537 ///
538 /// As a brief example, consider the obligation `for<'a> Fn(&'a int)
539 /// -> &'a int`, and the impl:
540 ///
541 /// impl<A,R> Fn<A,R> for SomethingOrOther
542 /// where A : Clone
543 /// { ... }
544 ///
545 /// Here we will have replaced `'a` with a skolemized region
546 /// `'0`. This means that our substitution will be `{A=>&'0
547 /// int, R=>&'0 int}`.
548 ///
549 /// When we apply the substitution to the bounds, we will wind up with
550 /// `&'0 int : Clone` as a predicate. As a last step, we then go and
551 /// replace `'0` with a late-bound region `'a`. The depth is matched
552 /// to the depth of the predicate, in this case 1, so that the final
553 /// predicate is `for<'a> &'a int : Clone`.
554 pub fn plug_leaks<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>,
555 skol_map: SkolemizationMap,
556 snapshot: &CombinedSnapshot,
557 value: &T)
558 -> T
559 where T : TypeFoldable<'tcx>
560 {
561 debug_assert!(leak_check(infcx, &skol_map, snapshot).is_ok());
562
563 debug!("plug_leaks(skol_map={:?}, value={:?})",
564 skol_map,
565 value);
566
567 // Compute a mapping from the "taint set" of each skolemized
568 // region back to the `ty::BoundRegion` that it originally
569 // represented. Because `leak_check` passed, we know that
570 // these taint sets are mutually disjoint.
571 let inv_skol_map: FnvHashMap<ty::Region, ty::BoundRegion> =
572 skol_map
573 .into_iter()
574 .flat_map(|(skol_br, skol)| {
575 infcx.tainted_regions(snapshot, skol)
576 .into_iter()
577 .map(move |tainted_region| (tainted_region, skol_br))
578 })
579 .collect();
580
581 debug!("plug_leaks: inv_skol_map={:?}",
582 inv_skol_map);
583
584 // Remove any instantiated type variables from `value`; those can hide
585 // references to regions from the `fold_regions` code below.
586 let value = infcx.resolve_type_vars_if_possible(value);
587
588 // Map any skolemization byproducts back to a late-bound
589 // region. Put that late-bound region at whatever the outermost
590 // binder is that we encountered in `value`. The caller is
591 // responsible for ensuring that (a) `value` contains at least one
592 // binder and (b) that binder is the one we want to use.
593 let result = infcx.tcx.fold_regions(&value, &mut false, |r, current_depth| {
594 match inv_skol_map.get(&r) {
595 None => r,
596 Some(br) => {
597 // It is the responsibility of the caller to ensure
598 // that each skolemized region appears within a
599 // binder. In practice, this routine is only used by
600 // trait checking, and all of the skolemized regions
601 // appear inside predicates, which always have
602 // binders, so this assert is satisfied.
603 assert!(current_depth > 1);
604
605 ty::ReLateBound(ty::DebruijnIndex::new(current_depth - 1), br.clone())
606 }
607 }
608 });
609
610 debug!("plug_leaks: result={:?}",
611 result);
612
613 result
614 }