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.
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.
11 //! Helper routines for higher-ranked things. See the `doc` module at
12 //! the end of the file for details.
14 use super::{CombinedSnapshot,
19 use super::combine::CombineFields;
20 use super::region_constraints::{TaintDirections};
22 use ty::{self, TyCtxt, Binder, TypeFoldable};
23 use ty::error::TypeError;
24 use ty::relate::{Relate, RelateResult, TypeRelation};
26 use util::nodemap::{FxHashMap, FxHashSet};
28 pub struct HrMatchResult<U> {
32 impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
33 pub fn higher_ranked_sub<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool)
34 -> RelateResult<'tcx, Binder<T>>
37 debug!("higher_ranked_sub(a={:?}, b={:?})",
40 // Rather than checking the subtype relationship between `a` and `b`
41 // as-is, we need to do some extra work here in order to make sure
42 // that function subtyping works correctly with respect to regions
44 // Note: this is a subtle algorithm. For a full explanation,
45 // please see the large comment at the end of the file in the (inlined) module
48 // Start a snapshot so we can examine "all bindings that were
49 // created as part of this type comparison".
50 return self.infcx.commit_if_ok(|snapshot| {
51 let span = self.trace.cause.span;
53 // First, we instantiate each bound region in the supertype with a
54 // fresh placeholder region.
55 let (b_prime, placeholder_map) =
56 self.infcx.replace_bound_vars_with_placeholders(b);
58 // Next, we instantiate each bound region in the subtype
59 // with a fresh region variable. These region variables --
60 // but no other pre-existing region variables -- can name
62 let (a_prime, _) = self.infcx.replace_bound_vars_with_fresh_vars(
68 debug!("a_prime={:?}", a_prime);
69 debug!("b_prime={:?}", b_prime);
71 // Compare types now that bound regions have been replaced.
72 let result = self.sub(a_is_expected).relate(&a_prime, &b_prime)?;
74 // Presuming type comparison succeeds, we need to check
75 // that the placeholder regions do not "leak".
76 self.infcx.leak_check(!a_is_expected, span, &placeholder_map, snapshot)?;
78 // We are finished with the placeholder regions now so pop
80 self.infcx.pop_placeholders(placeholder_map, snapshot);
82 debug!("higher_ranked_sub: OK result={:?}", result);
84 Ok(ty::Binder::bind(result))
88 /// The value consists of a pair `(t, u)` where `t` is the
89 /// *matcher* and `u` is a *value*. The idea is to find a
90 /// substitution `S` such that `S(t) == b`, and then return
91 /// `S(u)`. In other words, find values for the late-bound regions
92 /// in `a` that can make `t == b` and then replace the LBR in `u`
93 /// with those values.
95 /// This routine is (as of this writing) used in trait matching,
96 /// particularly projection.
98 /// NB. It should not happen that there are LBR appearing in `U`
99 /// that do not appear in `T`. If that happens, those regions are
100 /// unconstrained, and this routine replaces them with `'static`.
101 pub fn higher_ranked_match<T, U>(&mut self,
102 a_pair: &Binder<(T, U)>,
105 -> RelateResult<'tcx, HrMatchResult<U>>
106 where T: Relate<'tcx>,
107 U: TypeFoldable<'tcx>
109 debug!("higher_ranked_match(a={:?}, b={:?})",
112 // Start a snapshot so we can examine "all bindings that were
113 // created as part of this type comparison".
114 return self.infcx.commit_if_ok(|snapshot| {
115 // First, we instantiate each bound region in the matcher
116 // with a placeholder region.
117 let ((a_match, a_value), placeholder_map) =
118 self.infcx.replace_bound_vars_with_placeholders(a_pair);
120 debug!("higher_ranked_match: a_match={:?}", a_match);
121 debug!("higher_ranked_match: placeholder_map={:?}", placeholder_map);
123 // Equate types now that bound regions have been replaced.
124 self.equate(a_is_expected).relate(&a_match, &b_match)?;
126 // Map each placeholder region to a vector of other regions that it
127 // must be equated with. (Note that this vector may include other
128 // placeholder regions from `placeholder_map`.)
129 let placeholder_resolution_map: FxHashMap<_, _> =
132 .map(|(&br, &placeholder)| {
133 let tainted_regions =
134 self.infcx.tainted_regions(snapshot,
136 TaintDirections::incoming()); // [1]
138 // [1] this routine executes after the placeholder
139 // regions have been *equated* with something
140 // else, so examining the incoming edges ought to
141 // be enough to collect all constraints
143 (placeholder, (br, tainted_regions))
147 // For each placeholder region, pick a representative -- which can
148 // be any region from the sets above, except for other members of
149 // `placeholder_map`. There should always be a representative if things
150 // are properly well-formed.
151 let placeholder_representatives: FxHashMap<_, _> =
152 placeholder_resolution_map
154 .map(|(&placeholder, &(_, ref regions))| {
157 .filter(|&&r| !placeholder_resolution_map.contains_key(r))
161 bug!("no representative region for `{:?}` in `{:?}`",
162 placeholder, regions)
165 (placeholder, representative)
169 // Equate all the members of each placeholder set with the
171 for (placeholder, &(_br, ref regions)) in &placeholder_resolution_map {
172 let representative = &placeholder_representatives[placeholder];
173 debug!("higher_ranked_match: \
174 placeholder={:?} representative={:?} regions={:?}",
175 placeholder, representative, regions);
176 for region in regions.iter()
177 .filter(|&r| !placeholder_resolution_map.contains_key(r))
178 .filter(|&r| r != representative)
180 let origin = SubregionOrigin::Subtype(self.trace.clone());
181 self.infcx.borrow_region_constraints()
182 .make_eqregion(origin,
188 // Replace the placeholder regions appearing in value with
189 // their representatives
194 |r, _| placeholder_representatives.get(&r).cloned().unwrap_or(r));
196 debug!("higher_ranked_match: value={:?}", a_value);
198 // We are now done with these placeholder variables.
199 self.infcx.pop_placeholders(placeholder_map, snapshot);
201 Ok(HrMatchResult { value: a_value })
206 fn fold_regions_in<'a, 'gcx, 'tcx, T, F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
210 where T: TypeFoldable<'tcx>,
211 F: FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
213 tcx.fold_regions(unbound_value, &mut false, |region, current_depth| {
214 // we should only be encountering "escaping" late-bound regions here,
215 // because the ones at the current level should have been replaced
216 // with fresh variables
217 assert!(match *region {
218 ty::ReLateBound(..) => false,
222 fldr(region, current_depth)
226 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
227 fn tainted_regions(&self,
228 snapshot: &CombinedSnapshot<'a, 'tcx>,
230 directions: TaintDirections)
231 -> FxHashSet<ty::Region<'tcx>> {
232 self.borrow_region_constraints().tainted(
234 &snapshot.region_constraints_snapshot,
239 fn region_vars_confined_to_snapshot(&self,
240 snapshot: &CombinedSnapshot<'a, 'tcx>)
241 -> Vec<ty::RegionVid>
244 * Returns the set of region variables that do not affect any
245 * types/regions which existed before `snapshot` was
246 * started. This is used in the sub/lub/glb computations. The
247 * idea here is that when we are computing lub/glb of two
248 * regions, we sometimes create intermediate region variables.
249 * Those region variables may touch some of the placeholder or
250 * other "forbidden" regions we created to replace bound
251 * regions, but they don't really represent an "external"
254 * However, sometimes fresh variables are created for other
255 * purposes too, and those *may* represent an external
256 * constraint. In particular, when a type variable is
257 * instantiated, we create region variables for all the
258 * regions that appear within, and if that type variable
259 * pre-existed the snapshot, then those region variables
260 * represent external constraints.
262 * An example appears in the unit test
263 * `sub_free_bound_false_infer`. In this test, we want to
267 * fn(_#0t) <: for<'a> fn(&'a int)
270 * Note that the subtype has a type variable. Because the type
271 * variable can't be instantiated with a region that is bound
272 * in the fn signature, this comparison ought to fail. But if
273 * we're not careful, it will succeed.
275 * The reason is that when we walk through the subtyping
276 * algorithm, we begin by replacing `'a` with a placeholder
277 * variable `'1`. We then have `fn(_#0t) <: fn(&'1 int)`. This
278 * can be made true by unifying `_#0t` with `&'1 int`. In the
279 * process, we create a fresh variable for the placeholder
280 * region, `'$2`, and hence we have that `_#0t == &'$2
281 * int`. However, because `'$2` was created during the sub
282 * computation, if we're not careful we will erroneously
283 * assume it is one of the transient region variables
284 * representing a lub/glb internally. Not good.
286 * To prevent this, we check for type variables which were
287 * unified during the snapshot, and say that any region
288 * variable created during the snapshot but which finds its
289 * way into a type variable is considered to "escape" the
293 let mut region_vars =
294 self.borrow_region_constraints().vars_created_since_snapshot(
295 &snapshot.region_constraints_snapshot);
298 self.type_variables.borrow_mut().types_escaping_snapshot(&snapshot.type_snapshot);
300 let mut escaping_region_vars = FxHashSet::default();
301 for ty in &escaping_types {
302 self.tcx.collect_regions(ty, &mut escaping_region_vars);
305 region_vars.retain(|®ion_vid| {
306 let r = ty::ReVar(region_vid);
307 !escaping_region_vars.contains(&r)
310 debug!("region_vars_confined_to_snapshot: region_vars={:?} escaping_types={:?}",
317 /// Replace all regions (resp. types) bound by `binder` with placeholder
318 /// regions (resp. types) and return a map indicating which bound-region
319 /// was replaced with what placeholder region. This is the first step of
320 /// checking subtyping when higher-ranked things are involved.
322 /// **Important:** you must call this function from within a snapshot.
323 /// Moreover, before committing the snapshot, you must eventually call
324 /// either `plug_leaks` or `pop_placeholders` to remove the placeholder
325 /// regions. If you rollback the snapshot (or are using a probe), then
326 /// the pop occurs as part of the rollback, so an explicit call is not
327 /// needed (but is also permitted).
329 /// For more information about how placeholders and HRTBs work, see
330 /// the [rustc guide].
332 /// [rustc guide]: https://rust-lang.github.io/rustc-guide/traits/hrtb.html
333 pub fn replace_bound_vars_with_placeholders<T>(
335 binder: &ty::Binder<T>
336 ) -> (T, PlaceholderMap<'tcx>)
338 T: TypeFoldable<'tcx>
340 let next_universe = self.create_next_universe();
343 self.tcx.mk_region(ty::RePlaceholder(ty::PlaceholderRegion {
344 universe: next_universe,
349 let fld_t = |bound_ty: ty::BoundTy| {
350 self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
351 universe: next_universe,
356 let (result, map) = self.tcx.replace_bound_vars(binder, fld_r, fld_t);
359 "replace_bound_vars_with_placeholders(binder={:?}, result={:?}, map={:?})",
368 /// Searches the region constraints created since `snapshot` was started
369 /// and checks to determine whether any of the placeholder regions created
370 /// in `placeholder_map` would "escape" -- meaning that they are related to
371 /// other regions in some way. If so, the higher-ranked subtyping doesn't
372 /// hold. See `README.md` for more details.
373 pub fn leak_check(&self,
374 overly_polymorphic: bool,
376 placeholder_map: &PlaceholderMap<'tcx>,
377 snapshot: &CombinedSnapshot<'a, 'tcx>)
378 -> RelateResult<'tcx, ()>
380 debug!("leak_check: placeholder_map={:?}",
383 // If the user gave `-Zno-leak-check`, then skip the leak
384 // check completely. This is wildly unsound and also not
385 // unlikely to cause an ICE or two. It is intended for use
386 // only during a transition period, in which the MIR typeck
387 // uses the "universe-style" check, and the rest of typeck
388 // uses the more conservative leak check. Since the leak
389 // check is more conservative, we can't test the
390 // universe-style check without disabling it.
391 if self.tcx.sess.opts.debugging_opts.no_leak_check {
395 let new_vars = self.region_vars_confined_to_snapshot(snapshot);
396 for (&placeholder_br, &placeholder) in placeholder_map {
397 // The inputs to a placeholder variable can only
398 // be itself or other new variables.
399 let incoming_taints = self.tainted_regions(snapshot,
401 TaintDirections::both());
402 for &tainted_region in &incoming_taints {
403 // Each placeholder should only be relatable to itself
405 match *tainted_region {
407 if new_vars.contains(&vid) {
412 if tainted_region == placeholder { continue; }
416 debug!("{:?} (which replaced {:?}) is tainted by {:?}",
421 return Err(if overly_polymorphic {
422 debug!("Overly polymorphic!");
423 TypeError::RegionsOverlyPolymorphic(placeholder_br, tainted_region)
425 debug!("Not as polymorphic!");
426 TypeError::RegionsInsufficientlyPolymorphic(placeholder_br, tainted_region)
434 /// This code converts from placeholder regions back to late-bound
435 /// regions. It works by replacing each region in the taint set of a
436 /// placeholder region with a bound-region. The bound region will be bound
437 /// by the outer-most binder in `value`; the caller must ensure that there is
438 /// such a binder and it is the right place.
440 /// This routine is only intended to be used when the leak-check has
441 /// passed; currently, it's used in the trait matching code to create
442 /// a set of nested obligations from an impl that matches against
443 /// something higher-ranked. More details can be found in
444 /// `librustc/middle/traits/README.md`.
446 /// As a brief example, consider the obligation `for<'a> Fn(&'a int)
447 /// -> &'a int`, and the impl:
449 /// impl<A,R> Fn<A,R> for SomethingOrOther
453 /// Here we will have replaced `'a` with a placeholder region
454 /// `'0`. This means that our substitution will be `{A=>&'0
455 /// int, R=>&'0 int}`.
457 /// When we apply the substitution to the bounds, we will wind up with
458 /// `&'0 int : Clone` as a predicate. As a last step, we then go and
459 /// replace `'0` with a late-bound region `'a`. The depth is matched
460 /// to the depth of the predicate, in this case 1, so that the final
461 /// predicate is `for<'a> &'a int : Clone`.
462 pub fn plug_leaks<T>(&self,
463 placeholder_map: PlaceholderMap<'tcx>,
464 snapshot: &CombinedSnapshot<'a, 'tcx>,
466 where T : TypeFoldable<'tcx>
468 debug!("plug_leaks(placeholder_map={:?}, value={:?})",
472 if placeholder_map.is_empty() {
476 // Compute a mapping from the "taint set" of each placeholder
477 // region back to the `ty::BoundRegion` that it originally
478 // represented. Because `leak_check` passed, we know that
479 // these taint sets are mutually disjoint.
480 let inv_placeholder_map: FxHashMap<ty::Region<'tcx>, ty::BoundRegion> =
483 .flat_map(|(&placeholder_br, &placeholder)| {
484 self.tainted_regions(snapshot, placeholder, TaintDirections::both())
486 .map(move |tainted_region| (tainted_region, placeholder_br))
490 debug!("plug_leaks: inv_placeholder_map={:?}",
491 inv_placeholder_map);
493 // Remove any instantiated type variables from `value`; those can hide
494 // references to regions from the `fold_regions` code below.
495 let value = self.resolve_type_vars_if_possible(&value);
497 // Map any placeholder byproducts back to a late-bound
498 // region. Put that late-bound region at whatever the outermost
499 // binder is that we encountered in `value`. The caller is
500 // responsible for ensuring that (a) `value` contains at least one
501 // binder and (b) that binder is the one we want to use.
502 let result = self.tcx.fold_regions(&value, &mut false, |r, current_depth| {
503 match inv_placeholder_map.get(&r) {
506 // It is the responsibility of the caller to ensure
507 // that each placeholder region appears within a
508 // binder. In practice, this routine is only used by
509 // trait checking, and all of the placeholder regions
510 // appear inside predicates, which always have
511 // binders, so this assert is satisfied.
512 assert!(current_depth > ty::INNERMOST);
514 // since leak-check passed, this placeholder region
515 // should only have incoming edges from variables
516 // (which ought not to escape the snapshot, but we
517 // don't check that) or itself
520 ty::ReVar(_) => true,
521 ty::RePlaceholder(index) => index.name == *br,
524 "leak-check would have us replace {:?} with {:?}",
527 self.tcx.mk_region(ty::ReLateBound(
528 current_depth.shifted_out(1),
535 self.pop_placeholders(placeholder_map, snapshot);
537 debug!("plug_leaks: result={:?}", result);
542 /// Pops the placeholder regions found in `placeholder_map` from the region
543 /// inference context. Whenever you create placeholder regions via
544 /// `replace_bound_vars_with_placeholders`, they must be popped before you
545 /// commit the enclosing snapshot (if you do not commit, e.g. within a
546 /// probe or as a result of an error, then this is not necessary, as
547 /// popping happens as part of the rollback).
549 /// Note: popping also occurs implicitly as part of `leak_check`.
550 pub fn pop_placeholders(
552 placeholder_map: PlaceholderMap<'tcx>,
553 snapshot: &CombinedSnapshot<'a, 'tcx>,
555 debug!("pop_placeholders({:?})", placeholder_map);
556 let placeholder_regions: FxHashSet<_> = placeholder_map.values().cloned().collect();
557 self.borrow_region_constraints().pop_placeholders(&placeholder_regions);
558 self.universe.set(snapshot.universe);
559 if !placeholder_map.is_empty() {
560 self.projection_cache.borrow_mut().rollback_placeholder(
561 &snapshot.projection_cache_snapshot);