| // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
| // file at the top-level directory of this distribution and at |
| // http://rust-lang.org/COPYRIGHT. |
| // |
| // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
| // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your |
| // option. This file may not be copied, modified, or distributed |
| // except according to those terms. |
| |
| //! Helper routines for higher-ranked things. See the `doc` module at |
| //! the end of the file for details. |
| |
| use super::{CombinedSnapshot, |
| InferCtxt, |
| LateBoundRegion, |
| HigherRankedType, |
| SubregionOrigin, |
| SkolemizationMap}; |
| use super::combine::CombineFields; |
| use super::region_inference::{TaintDirections}; |
| |
| use ty::{self, TyCtxt, Binder, TypeFoldable}; |
| use ty::error::TypeError; |
| use ty::relate::{Relate, RelateResult, TypeRelation}; |
| use syntax_pos::Span; |
| use util::nodemap::{FnvHashMap, FnvHashSet}; |
| |
| pub struct HrMatchResult<U> { |
| pub value: U, |
| |
| /// Normally, when we do a higher-ranked match operation, we |
| /// expect all higher-ranked regions to be constrained as part of |
| /// the match operation. However, in the transition period for |
| /// #32330, it can happen that we sometimes have unconstrained |
| /// regions that get instantiated with fresh variables. In that |
| /// case, we collect the set of unconstrained bound regions here |
| /// and replace them with fresh variables. |
| pub unconstrained_regions: Vec<ty::BoundRegion>, |
| } |
| |
| impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> { |
| pub fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>) |
| -> RelateResult<'tcx, Binder<T>> |
| where T: Relate<'tcx> |
| { |
| debug!("higher_ranked_sub(a={:?}, b={:?})", |
| a, b); |
| |
| // Rather than checking the subtype relationship between `a` and `b` |
| // as-is, we need to do some extra work here in order to make sure |
| // that function subtyping works correctly with respect to regions |
| // |
| // Note: this is a subtle algorithm. For a full explanation, |
| // please see the large comment at the end of the file in the (inlined) module |
| // `doc`. |
| |
| // Start a snapshot so we can examine "all bindings that were |
| // created as part of this type comparison". |
| return self.infcx.commit_if_ok(|snapshot| { |
| let span = self.trace.origin.span(); |
| |
| // First, we instantiate each bound region in the subtype with a fresh |
| // region variable. |
| let (a_prime, _) = |
| self.infcx.replace_late_bound_regions_with_fresh_var( |
| span, |
| HigherRankedType, |
| a); |
| |
| // Second, we instantiate each bound region in the supertype with a |
| // fresh concrete region. |
| let (b_prime, skol_map) = |
| self.infcx.skolemize_late_bound_regions(b, snapshot); |
| |
| debug!("a_prime={:?}", a_prime); |
| debug!("b_prime={:?}", b_prime); |
| |
| // Compare types now that bound regions have been replaced. |
| let result = self.sub().relate(&a_prime, &b_prime)?; |
| |
| // Presuming type comparison succeeds, we need to check |
| // that the skolemized regions do not "leak". |
| self.infcx.leak_check(!self.a_is_expected, span, &skol_map, snapshot)?; |
| |
| // We are finished with the skolemized regions now so pop |
| // them off. |
| self.infcx.pop_skolemized(skol_map, snapshot); |
| |
| debug!("higher_ranked_sub: OK result={:?}", result); |
| |
| Ok(ty::Binder(result)) |
| }); |
| } |
| |
| /// The value consists of a pair `(t, u)` where `t` is the |
| /// *matcher* and `u` is a *value*. The idea is to find a |
| /// substitution `S` such that `S(t) == b`, and then return |
| /// `S(u)`. In other words, find values for the late-bound regions |
| /// in `a` that can make `t == b` and then replace the LBR in `u` |
| /// with those values. |
| /// |
| /// This routine is (as of this writing) used in trait matching, |
| /// particularly projection. |
| /// |
| /// NB. It should not happen that there are LBR appearing in `U` |
| /// that do not appear in `T`. If that happens, those regions are |
| /// unconstrained, and this routine replaces them with `'static`. |
| pub fn higher_ranked_match<T, U>(&self, |
| span: Span, |
| a_pair: &Binder<(T, U)>, |
| b_match: &T) |
| -> RelateResult<'tcx, HrMatchResult<U>> |
| where T: Relate<'tcx>, |
| U: TypeFoldable<'tcx> |
| { |
| debug!("higher_ranked_match(a={:?}, b={:?})", |
| a_pair, b_match); |
| |
| // Start a snapshot so we can examine "all bindings that were |
| // created as part of this type comparison". |
| return self.infcx.commit_if_ok(|snapshot| { |
| // First, we instantiate each bound region in the matcher |
| // with a skolemized region. |
| let ((a_match, a_value), skol_map) = |
| self.infcx.skolemize_late_bound_regions(a_pair, snapshot); |
| |
| debug!("higher_ranked_match: a_match={:?}", a_match); |
| debug!("higher_ranked_match: skol_map={:?}", skol_map); |
| |
| // Equate types now that bound regions have been replaced. |
| try!(self.equate().relate(&a_match, &b_match)); |
| |
| // Map each skolemized region to a vector of other regions that it |
| // must be equated with. (Note that this vector may include other |
| // skolemized regions from `skol_map`.) |
| let skol_resolution_map: FnvHashMap<_, _> = |
| skol_map |
| .iter() |
| .map(|(&br, &skol)| { |
| let tainted_regions = |
| self.infcx.tainted_regions(snapshot, |
| skol, |
| TaintDirections::incoming()); // [1] |
| |
| // [1] this routine executes after the skolemized |
| // regions have been *equated* with something |
| // else, so examining the incoming edges ought to |
| // be enough to collect all constraints |
| |
| (skol, (br, tainted_regions)) |
| }) |
| .collect(); |
| |
| // For each skolemized region, pick a representative -- which can |
| // be any region from the sets above, except for other members of |
| // `skol_map`. There should always be a representative if things |
| // are properly well-formed. |
| let mut unconstrained_regions = vec![]; |
| let skol_representatives: FnvHashMap<_, _> = |
| skol_resolution_map |
| .iter() |
| .map(|(&skol, &(br, ref regions))| { |
| let representative = |
| regions.iter() |
| .filter(|r| !skol_resolution_map.contains_key(r)) |
| .cloned() |
| .next() |
| .unwrap_or_else(|| { // [1] |
| unconstrained_regions.push(br); |
| self.infcx.next_region_var( |
| LateBoundRegion(span, br, HigherRankedType)) |
| }); |
| |
| // [1] There should always be a representative, |
| // unless the higher-ranked region did not appear |
| // in the values being matched. We should reject |
| // as ill-formed cases that can lead to this, but |
| // right now we sometimes issue warnings (see |
| // #32330). |
| |
| (skol, representative) |
| }) |
| .collect(); |
| |
| // Equate all the members of each skolemization set with the |
| // representative. |
| for (skol, &(_br, ref regions)) in &skol_resolution_map { |
| let representative = &skol_representatives[skol]; |
| debug!("higher_ranked_match: \ |
| skol={:?} representative={:?} regions={:?}", |
| skol, representative, regions); |
| for region in regions.iter() |
| .filter(|&r| !skol_resolution_map.contains_key(r)) |
| .filter(|&r| r != representative) |
| { |
| let origin = SubregionOrigin::Subtype(self.trace.clone()); |
| self.infcx.region_vars.make_eqregion(origin, |
| *representative, |
| *region); |
| } |
| } |
| |
| // Replace the skolemized regions appearing in value with |
| // their representatives |
| let a_value = |
| fold_regions_in( |
| self.tcx(), |
| &a_value, |
| |r, _| skol_representatives.get(&r).cloned().unwrap_or(r)); |
| |
| debug!("higher_ranked_match: value={:?}", a_value); |
| |
| // We are now done with these skolemized variables. |
| self.infcx.pop_skolemized(skol_map, snapshot); |
| |
| Ok(HrMatchResult { |
| value: a_value, |
| unconstrained_regions: unconstrained_regions, |
| }) |
| }); |
| } |
| |
| pub fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) |
| -> RelateResult<'tcx, Binder<T>> |
| where T: Relate<'tcx> |
| { |
| // Start a snapshot so we can examine "all bindings that were |
| // created as part of this type comparison". |
| return self.infcx.commit_if_ok(|snapshot| { |
| // Instantiate each bound region with a fresh region variable. |
| let span = self.trace.origin.span(); |
| let (a_with_fresh, a_map) = |
| self.infcx.replace_late_bound_regions_with_fresh_var( |
| span, HigherRankedType, a); |
| let (b_with_fresh, _) = |
| self.infcx.replace_late_bound_regions_with_fresh_var( |
| span, HigherRankedType, b); |
| |
| // Collect constraints. |
| let result0 = |
| self.lub().relate(&a_with_fresh, &b_with_fresh)?; |
| let result0 = |
| self.infcx.resolve_type_vars_if_possible(&result0); |
| debug!("lub result0 = {:?}", result0); |
| |
| // Generalize the regions appearing in result0 if possible |
| let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot); |
| let span = self.trace.origin.span(); |
| let result1 = |
| fold_regions_in( |
| self.tcx(), |
| &result0, |
| |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn, |
| &new_vars, &a_map, r)); |
| |
| debug!("lub({:?},{:?}) = {:?}", |
| a, |
| b, |
| result1); |
| |
| Ok(ty::Binder(result1)) |
| }); |
| |
| fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>, |
| span: Span, |
| snapshot: &CombinedSnapshot, |
| debruijn: ty::DebruijnIndex, |
| new_vars: &[ty::RegionVid], |
| a_map: &FnvHashMap<ty::BoundRegion, ty::Region>, |
| r0: ty::Region) |
| -> ty::Region { |
| // Regions that pre-dated the LUB computation stay as they are. |
| if !is_var_in_set(new_vars, r0) { |
| assert!(!r0.is_bound()); |
| debug!("generalize_region(r0={:?}): not new variable", r0); |
| return r0; |
| } |
| |
| let tainted = infcx.tainted_regions(snapshot, r0, TaintDirections::both()); |
| |
| // Variables created during LUB computation which are |
| // *related* to regions that pre-date the LUB computation |
| // stay as they are. |
| if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) { |
| debug!("generalize_region(r0={:?}): \ |
| non-new-variables found in {:?}", |
| r0, tainted); |
| assert!(!r0.is_bound()); |
| return r0; |
| } |
| |
| // Otherwise, the variable must be associated with at |
| // least one of the variables representing bound regions |
| // in both A and B. Replace the variable with the "first" |
| // bound region from A that we find it to be associated |
| // with. |
| for (a_br, a_r) in a_map { |
| if tainted.iter().any(|x| x == a_r) { |
| debug!("generalize_region(r0={:?}): \ |
| replacing with {:?}, tainted={:?}", |
| r0, *a_br, tainted); |
| return ty::ReLateBound(debruijn, *a_br); |
| } |
| } |
| |
| span_bug!( |
| span, |
| "region {:?} is not associated with any bound region from A!", |
| r0) |
| } |
| } |
| |
| pub fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) |
| -> RelateResult<'tcx, Binder<T>> |
| where T: Relate<'tcx> |
| { |
| debug!("higher_ranked_glb({:?}, {:?})", |
| a, b); |
| |
| // Make a snapshot so we can examine "all bindings that were |
| // created as part of this type comparison". |
| return self.infcx.commit_if_ok(|snapshot| { |
| // Instantiate each bound region with a fresh region variable. |
| let (a_with_fresh, a_map) = |
| self.infcx.replace_late_bound_regions_with_fresh_var( |
| self.trace.origin.span(), HigherRankedType, a); |
| let (b_with_fresh, b_map) = |
| self.infcx.replace_late_bound_regions_with_fresh_var( |
| self.trace.origin.span(), HigherRankedType, b); |
| let a_vars = var_ids(self, &a_map); |
| let b_vars = var_ids(self, &b_map); |
| |
| // Collect constraints. |
| let result0 = |
| self.glb().relate(&a_with_fresh, &b_with_fresh)?; |
| let result0 = |
| self.infcx.resolve_type_vars_if_possible(&result0); |
| debug!("glb result0 = {:?}", result0); |
| |
| // Generalize the regions appearing in result0 if possible |
| let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot); |
| let span = self.trace.origin.span(); |
| let result1 = |
| fold_regions_in( |
| self.tcx(), |
| &result0, |
| |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn, |
| &new_vars, |
| &a_map, &a_vars, &b_vars, |
| r)); |
| |
| debug!("glb({:?},{:?}) = {:?}", |
| a, |
| b, |
| result1); |
| |
| Ok(ty::Binder(result1)) |
| }); |
| |
| fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>, |
| span: Span, |
| snapshot: &CombinedSnapshot, |
| debruijn: ty::DebruijnIndex, |
| new_vars: &[ty::RegionVid], |
| a_map: &FnvHashMap<ty::BoundRegion, ty::Region>, |
| a_vars: &[ty::RegionVid], |
| b_vars: &[ty::RegionVid], |
| r0: ty::Region) -> ty::Region { |
| if !is_var_in_set(new_vars, r0) { |
| assert!(!r0.is_bound()); |
| return r0; |
| } |
| |
| let tainted = infcx.tainted_regions(snapshot, r0, TaintDirections::both()); |
| |
| let mut a_r = None; |
| let mut b_r = None; |
| let mut only_new_vars = true; |
| for r in &tainted { |
| if is_var_in_set(a_vars, *r) { |
| if a_r.is_some() { |
| return fresh_bound_variable(infcx, debruijn); |
| } else { |
| a_r = Some(*r); |
| } |
| } else if is_var_in_set(b_vars, *r) { |
| if b_r.is_some() { |
| return fresh_bound_variable(infcx, debruijn); |
| } else { |
| b_r = Some(*r); |
| } |
| } else if !is_var_in_set(new_vars, *r) { |
| only_new_vars = false; |
| } |
| } |
| |
| // NB---I do not believe this algorithm computes |
| // (necessarily) the GLB. As written it can |
| // spuriously fail. In particular, if there is a case |
| // like: |fn(&a)| and fn(fn(&b)), where a and b are |
| // free, it will return fn(&c) where c = GLB(a,b). If |
| // however this GLB is not defined, then the result is |
| // an error, even though something like |
| // "fn<X>(fn(&X))" where X is bound would be a |
| // subtype of both of those. |
| // |
| // The problem is that if we were to return a bound |
| // variable, we'd be computing a lower-bound, but not |
| // necessarily the *greatest* lower-bound. |
| // |
| // Unfortunately, this problem is non-trivial to solve, |
| // because we do not know at the time of computing the GLB |
| // whether a GLB(a,b) exists or not, because we haven't |
| // run region inference (or indeed, even fully computed |
| // the region hierarchy!). The current algorithm seems to |
| // works ok in practice. |
| |
| if a_r.is_some() && b_r.is_some() && only_new_vars { |
| // Related to exactly one bound variable from each fn: |
| return rev_lookup(span, a_map, a_r.unwrap()); |
| } else if a_r.is_none() && b_r.is_none() { |
| // Not related to bound variables from either fn: |
| assert!(!r0.is_bound()); |
| return r0; |
| } else { |
| // Other: |
| return fresh_bound_variable(infcx, debruijn); |
| } |
| } |
| |
| fn rev_lookup(span: Span, |
| a_map: &FnvHashMap<ty::BoundRegion, ty::Region>, |
| r: ty::Region) -> ty::Region |
| { |
| for (a_br, a_r) in a_map { |
| if *a_r == r { |
| return ty::ReLateBound(ty::DebruijnIndex::new(1), *a_br); |
| } |
| } |
| span_bug!( |
| span, |
| "could not find original bound region for {:?}", |
| r); |
| } |
| |
| fn fresh_bound_variable(infcx: &InferCtxt, debruijn: ty::DebruijnIndex) -> ty::Region { |
| infcx.region_vars.new_bound(debruijn) |
| } |
| } |
| } |
| |
| fn var_ids<'a, 'gcx, 'tcx>(fields: &CombineFields<'a, 'gcx, 'tcx>, |
| map: &FnvHashMap<ty::BoundRegion, ty::Region>) |
| -> Vec<ty::RegionVid> { |
| map.iter() |
| .map(|(_, r)| match *r { |
| ty::ReVar(r) => { r } |
| r => { |
| span_bug!( |
| fields.trace.origin.span(), |
| "found non-region-vid: {:?}", |
| r); |
| } |
| }) |
| .collect() |
| } |
| |
| fn is_var_in_set(new_vars: &[ty::RegionVid], r: ty::Region) -> bool { |
| match r { |
| ty::ReVar(ref v) => new_vars.iter().any(|x| x == v), |
| _ => false |
| } |
| } |
| |
| fn fold_regions_in<'a, 'gcx, 'tcx, T, F>(tcx: TyCtxt<'a, 'gcx, 'tcx>, |
| unbound_value: &T, |
| mut fldr: F) |
| -> T |
| where T: TypeFoldable<'tcx>, |
| F: FnMut(ty::Region, ty::DebruijnIndex) -> ty::Region, |
| { |
| tcx.fold_regions(unbound_value, &mut false, |region, current_depth| { |
| // we should only be encountering "escaping" late-bound regions here, |
| // because the ones at the current level should have been replaced |
| // with fresh variables |
| assert!(match region { |
| ty::ReLateBound(..) => false, |
| _ => true |
| }); |
| |
| fldr(region, ty::DebruijnIndex::new(current_depth)) |
| }) |
| } |
| |
| impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> { |
| fn tainted_regions(&self, |
| snapshot: &CombinedSnapshot, |
| r: ty::Region, |
| directions: TaintDirections) |
| -> FnvHashSet<ty::Region> { |
| self.region_vars.tainted(&snapshot.region_vars_snapshot, r, directions) |
| } |
| |
| fn region_vars_confined_to_snapshot(&self, |
| snapshot: &CombinedSnapshot) |
| -> Vec<ty::RegionVid> |
| { |
| /*! |
| * Returns the set of region variables that do not affect any |
| * types/regions which existed before `snapshot` was |
| * started. This is used in the sub/lub/glb computations. The |
| * idea here is that when we are computing lub/glb of two |
| * regions, we sometimes create intermediate region variables. |
| * Those region variables may touch some of the skolemized or |
| * other "forbidden" regions we created to replace bound |
| * regions, but they don't really represent an "external" |
| * constraint. |
| * |
| * However, sometimes fresh variables are created for other |
| * purposes too, and those *may* represent an external |
| * constraint. In particular, when a type variable is |
| * instantiated, we create region variables for all the |
| * regions that appear within, and if that type variable |
| * pre-existed the snapshot, then those region variables |
| * represent external constraints. |
| * |
| * An example appears in the unit test |
| * `sub_free_bound_false_infer`. In this test, we want to |
| * know whether |
| * |
| * ```rust |
| * fn(_#0t) <: for<'a> fn(&'a int) |
| * ``` |
| * |
| * Note that the subtype has a type variable. Because the type |
| * variable can't be instantiated with a region that is bound |
| * in the fn signature, this comparison ought to fail. But if |
| * we're not careful, it will succeed. |
| * |
| * The reason is that when we walk through the subtyping |
| * algorith, we begin by replacing `'a` with a skolemized |
| * variable `'1`. We then have `fn(_#0t) <: fn(&'1 int)`. This |
| * can be made true by unifying `_#0t` with `&'1 int`. In the |
| * process, we create a fresh variable for the skolemized |
| * region, `'$2`, and hence we have that `_#0t == &'$2 |
| * int`. However, because `'$2` was created during the sub |
| * computation, if we're not careful we will erroneously |
| * assume it is one of the transient region variables |
| * representing a lub/glb internally. Not good. |
| * |
| * To prevent this, we check for type variables which were |
| * unified during the snapshot, and say that any region |
| * variable created during the snapshot but which finds its |
| * way into a type variable is considered to "escape" the |
| * snapshot. |
| */ |
| |
| let mut region_vars = |
| self.region_vars.vars_created_since_snapshot(&snapshot.region_vars_snapshot); |
| |
| let escaping_types = |
| self.type_variables.borrow_mut().types_escaping_snapshot(&snapshot.type_snapshot); |
| |
| let mut escaping_region_vars = FnvHashSet(); |
| for ty in &escaping_types { |
| self.tcx.collect_regions(ty, &mut escaping_region_vars); |
| } |
| |
| region_vars.retain(|®ion_vid| { |
| let r = ty::ReVar(region_vid); |
| !escaping_region_vars.contains(&r) |
| }); |
| |
| debug!("region_vars_confined_to_snapshot: region_vars={:?} escaping_types={:?}", |
| region_vars, |
| escaping_types); |
| |
| region_vars |
| } |
| |
| /// Replace all regions bound by `binder` with skolemized regions and |
| /// return a map indicating which bound-region was replaced with what |
| /// skolemized region. This is the first step of checking subtyping |
| /// when higher-ranked things are involved. |
| /// |
| /// **Important:** you must call this function from within a snapshot. |
| /// Moreover, before committing the snapshot, you must eventually call |
| /// either `plug_leaks` or `pop_skolemized` to remove the skolemized |
| /// regions. If you rollback the snapshot (or are using a probe), then |
| /// the pop occurs as part of the rollback, so an explicit call is not |
| /// needed (but is also permitted). |
| /// |
| /// See `README.md` for more details. |
| pub fn skolemize_late_bound_regions<T>(&self, |
| binder: &ty::Binder<T>, |
| snapshot: &CombinedSnapshot) |
| -> (T, SkolemizationMap) |
| where T : TypeFoldable<'tcx> |
| { |
| let (result, map) = self.tcx.replace_late_bound_regions(binder, |br| { |
| self.region_vars.push_skolemized(br, &snapshot.region_vars_snapshot) |
| }); |
| |
| debug!("skolemize_bound_regions(binder={:?}, result={:?}, map={:?})", |
| binder, |
| result, |
| map); |
| |
| (result, map) |
| } |
| |
| /// Searches the region constriants created since `snapshot` was started |
| /// and checks to determine whether any of the skolemized regions created |
| /// in `skol_map` would "escape" -- meaning that they are related to |
| /// other regions in some way. If so, the higher-ranked subtyping doesn't |
| /// hold. See `README.md` for more details. |
| pub fn leak_check(&self, |
| overly_polymorphic: bool, |
| span: Span, |
| skol_map: &SkolemizationMap, |
| snapshot: &CombinedSnapshot) |
| -> RelateResult<'tcx, ()> |
| { |
| debug!("leak_check: skol_map={:?}", |
| skol_map); |
| |
| // ## Issue #32330 warnings |
| // |
| // When Issue #32330 is fixed, a certain number of late-bound |
| // regions (LBR) will become early-bound. We wish to issue |
| // warnings when the result of `leak_check` relies on such LBR, as |
| // that means that compilation will likely start to fail. |
| // |
| // Recall that when we do a "HR subtype" check, we replace all |
| // late-bound regions (LBR) in the subtype with fresh variables, |
| // and skolemize the late-bound regions in the supertype. If those |
| // skolemized regions from the supertype wind up being |
| // super-regions (directly or indirectly) of either |
| // |
| // - another skolemized region; or, |
| // - some region that pre-exists the HR subtype check |
| // - e.g., a region variable that is not one of those created |
| // to represent bound regions in the subtype |
| // |
| // then leak-check (and hence the subtype check) fails. |
| // |
| // What will change when we fix #32330 is that some of the LBR in the |
| // subtype may become early-bound. In that case, they would no longer be in |
| // the "permitted set" of variables that can be related to a skolemized |
| // type. |
| // |
| // So the foundation for this warning is to collect variables that we found |
| // to be related to a skolemized type. For each of them, we have a |
| // `BoundRegion` which carries a `Issue32330` flag. We check whether any of |
| // those flags indicate that this variable was created from a lifetime |
| // that will change from late- to early-bound. If so, we issue a warning |
| // indicating that the results of compilation may change. |
| // |
| // This is imperfect, since there are other kinds of code that will not |
| // compile once #32330 is fixed. However, it fixes the errors observed in |
| // practice on crater runs. |
| let mut warnings = vec![]; |
| |
| let new_vars = self.region_vars_confined_to_snapshot(snapshot); |
| for (&skol_br, &skol) in skol_map { |
| // The inputs to a skolemized variable can only |
| // be itself or other new variables. |
| let incoming_taints = self.tainted_regions(snapshot, |
| skol, |
| TaintDirections::both()); |
| for &tainted_region in &incoming_taints { |
| // Each skolemized should only be relatable to itself |
| // or new variables: |
| match tainted_region { |
| ty::ReVar(vid) => { |
| if new_vars.contains(&vid) { |
| warnings.extend( |
| match self.region_vars.var_origin(vid) { |
| LateBoundRegion(_, |
| ty::BrNamed(_, _, wc), |
| _) => Some(wc), |
| _ => None, |
| }); |
| continue; |
| } |
| } |
| _ => { |
| if tainted_region == skol { continue; } |
| } |
| }; |
| |
| debug!("{:?} (which replaced {:?}) is tainted by {:?}", |
| skol, |
| skol_br, |
| tainted_region); |
| |
| if overly_polymorphic { |
| debug!("Overly polymorphic!"); |
| return Err(TypeError::RegionsOverlyPolymorphic(skol_br, |
| tainted_region)); |
| } else { |
| debug!("Not as polymorphic!"); |
| return Err(TypeError::RegionsInsufficientlyPolymorphic(skol_br, |
| tainted_region)); |
| } |
| } |
| } |
| |
| self.issue_32330_warnings(span, &warnings); |
| |
| Ok(()) |
| } |
| |
| /// This code converts from skolemized regions back to late-bound |
| /// regions. It works by replacing each region in the taint set of a |
| /// skolemized region with a bound-region. The bound region will be bound |
| /// by the outer-most binder in `value`; the caller must ensure that there is |
| /// such a binder and it is the right place. |
| /// |
| /// This routine is only intended to be used when the leak-check has |
| /// passed; currently, it's used in the trait matching code to create |
| /// a set of nested obligations frmo an impl that matches against |
| /// something higher-ranked. More details can be found in |
| /// `librustc/middle/traits/README.md`. |
| /// |
| /// As a brief example, consider the obligation `for<'a> Fn(&'a int) |
| /// -> &'a int`, and the impl: |
| /// |
| /// impl<A,R> Fn<A,R> for SomethingOrOther |
| /// where A : Clone |
| /// { ... } |
| /// |
| /// Here we will have replaced `'a` with a skolemized region |
| /// `'0`. This means that our substitution will be `{A=>&'0 |
| /// int, R=>&'0 int}`. |
| /// |
| /// When we apply the substitution to the bounds, we will wind up with |
| /// `&'0 int : Clone` as a predicate. As a last step, we then go and |
| /// replace `'0` with a late-bound region `'a`. The depth is matched |
| /// to the depth of the predicate, in this case 1, so that the final |
| /// predicate is `for<'a> &'a int : Clone`. |
| pub fn plug_leaks<T>(&self, |
| skol_map: SkolemizationMap, |
| snapshot: &CombinedSnapshot, |
| value: &T) -> T |
| where T : TypeFoldable<'tcx> |
| { |
| debug!("plug_leaks(skol_map={:?}, value={:?})", |
| skol_map, |
| value); |
| |
| // Compute a mapping from the "taint set" of each skolemized |
| // region back to the `ty::BoundRegion` that it originally |
| // represented. Because `leak_check` passed, we know that |
| // these taint sets are mutually disjoint. |
| let inv_skol_map: FnvHashMap<ty::Region, ty::BoundRegion> = |
| skol_map |
| .iter() |
| .flat_map(|(&skol_br, &skol)| { |
| self.tainted_regions(snapshot, skol, TaintDirections::both()) |
| .into_iter() |
| .map(move |tainted_region| (tainted_region, skol_br)) |
| }) |
| .collect(); |
| |
| debug!("plug_leaks: inv_skol_map={:?}", |
| inv_skol_map); |
| |
| // Remove any instantiated type variables from `value`; those can hide |
| // references to regions from the `fold_regions` code below. |
| let value = self.resolve_type_vars_if_possible(value); |
| |
| // Map any skolemization byproducts back to a late-bound |
| // region. Put that late-bound region at whatever the outermost |
| // binder is that we encountered in `value`. The caller is |
| // responsible for ensuring that (a) `value` contains at least one |
| // binder and (b) that binder is the one we want to use. |
| let result = self.tcx.fold_regions(&value, &mut false, |r, current_depth| { |
| match inv_skol_map.get(&r) { |
| None => r, |
| Some(br) => { |
| // It is the responsibility of the caller to ensure |
| // that each skolemized region appears within a |
| // binder. In practice, this routine is only used by |
| // trait checking, and all of the skolemized regions |
| // appear inside predicates, which always have |
| // binders, so this assert is satisfied. |
| assert!(current_depth > 1); |
| |
| // since leak-check passed, this skolemized region |
| // should only have incoming edges from variables |
| // (which ought not to escape the snapshot, but we |
| // don't check that) or itself |
| assert!( |
| match r { |
| ty::ReVar(_) => true, |
| ty::ReSkolemized(_, ref br1) => br == br1, |
| _ => false, |
| }, |
| "leak-check would have us replace {:?} with {:?}", |
| r, br); |
| |
| ty::ReLateBound(ty::DebruijnIndex::new(current_depth - 1), br.clone()) |
| } |
| } |
| }); |
| |
| debug!("plug_leaks: result={:?}", |
| result); |
| |
| self.pop_skolemized(skol_map, snapshot); |
| |
| debug!("plug_leaks: result={:?}", result); |
| |
| result |
| } |
| |
| /// Pops the skolemized regions found in `skol_map` from the region |
| /// inference context. Whenever you create skolemized regions via |
| /// `skolemize_late_bound_regions`, they must be popped before you |
| /// commit the enclosing snapshot (if you do not commit, e.g. within a |
| /// probe or as a result of an error, then this is not necessary, as |
| /// popping happens as part of the rollback). |
| /// |
| /// Note: popping also occurs implicitly as part of `leak_check`. |
| pub fn pop_skolemized(&self, |
| skol_map: SkolemizationMap, |
| snapshot: &CombinedSnapshot) |
| { |
| debug!("pop_skolemized({:?})", skol_map); |
| let skol_regions: FnvHashSet<_> = skol_map.values().cloned().collect(); |
| self.region_vars.pop_skolemized(&skol_regions, &snapshot.region_vars_snapshot); |
| } |
| } |
