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,
  15             InferCtxt,
  16             LateBoundRegion,
  17             HigherRankedType,
  18             SubregionOrigin,
  19             SkolemizationMap};
  20 use super::combine::CombineFields;
  21 use super::region_inference::{TaintDirections};
  22
  23 use ty::{self, TyCtxt, Binder, TypeFoldable};
  24 use ty::error::TypeError;
  25 use ty::relate::{Relate, RelateResult, TypeRelation};
  26 use syntax_pos::Span;
  27 use util::nodemap::{FxHashMap, FxHashSet};
  28
  29 pub struct HrMatchResult<U> {
  30     pub value: U,
  31
  32     /// Normally, when we do a higher-ranked match operation, we
  33     /// expect all higher-ranked regions to be constrained as part of
  34     /// the match operation. However, in the transition period for
  35     /// #32330, it can happen that we sometimes have unconstrained
  36     /// regions that get instantiated with fresh variables. In that
  37     /// case, we collect the set of unconstrained bound regions here
  38     /// and replace them with fresh variables.
  39     pub unconstrained_regions: Vec<ty::BoundRegion>,
  40 }
  41
  42 impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
  43     pub fn higher_ranked_sub<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool)
  44                                 -> RelateResult<'tcx, Binder<T>>
  45         where T: Relate<'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             let span = self.trace.cause.span;
  62
  63             // First, we instantiate each bound region in the subtype with a fresh
  64             // region variable.
  65             let (a_prime, _) =
  66                 self.infcx.replace_late_bound_regions_with_fresh_var(
  67                     span,
  68                     HigherRankedType,
  69                     a);
  70
  71             // Second, we instantiate each bound region in the supertype with a
  72             // fresh concrete region.
  73             let (b_prime, skol_map) =
  74                 self.infcx.skolemize_late_bound_regions(b, snapshot);
  75
  76             debug!("a_prime={:?}", a_prime);
  77             debug!("b_prime={:?}", b_prime);
  78
  79             // Compare types now that bound regions have been replaced.
  80             let result = self.sub(a_is_expected).relate(&a_prime, &b_prime)?;
  81
  82             // Presuming type comparison succeeds, we need to check
  83             // that the skolemized regions do not "leak".
  84             self.infcx.leak_check(!a_is_expected, span, &skol_map, snapshot)?;
  85
  86             // We are finished with the skolemized regions now so pop
  87             // them off.
  88             self.infcx.pop_skolemized(skol_map, snapshot);
  89
  90             debug!("higher_ranked_sub: OK result={:?}", result);
  91
  92             Ok(ty::Binder(result))
  93         });
  94     }
  95
  96     /// The value consists of a pair `(t, u)` where `t` is the
  97     /// *matcher* and `u` is a *value*. The idea is to find a
  98     /// substitution `S` such that `S(t) == b`, and then return
  99     /// `S(u)`. In other words, find values for the late-bound regions
 100     /// in `a` that can make `t == b` and then replace the LBR in `u`
 101     /// with those values.
 102     ///
 103     /// This routine is (as of this writing) used in trait matching,
 104     /// particularly projection.
 105     ///
 106     /// NB. It should not happen that there are LBR appearing in `U`
 107     /// that do not appear in `T`. If that happens, those regions are
 108     /// unconstrained, and this routine replaces them with `'static`.
 109     pub fn higher_ranked_match<T, U>(&mut self,
 110                                      span: Span,
 111                                      a_pair: &Binder<(T, U)>,
 112                                      b_match: &T,
 113                                      a_is_expected: bool)
 114                                      -> RelateResult<'tcx, HrMatchResult<U>>
 115         where T: Relate<'tcx>,
 116               U: TypeFoldable<'tcx>
 117     {
 118         debug!("higher_ranked_match(a={:?}, b={:?})",
 119                a_pair, b_match);
 120
 121         // Start a snapshot so we can examine "all bindings that were
 122         // created as part of this type comparison".
 123         return self.infcx.commit_if_ok(|snapshot| {
 124             // First, we instantiate each bound region in the matcher
 125             // with a skolemized region.
 126             let ((a_match, a_value), skol_map) =
 127                 self.infcx.skolemize_late_bound_regions(a_pair, snapshot);
 128
 129             debug!("higher_ranked_match: a_match={:?}", a_match);
 130             debug!("higher_ranked_match: skol_map={:?}", skol_map);
 131
 132             // Equate types now that bound regions have been replaced.
 133             self.equate(a_is_expected).relate(&a_match, &b_match)?;
 134
 135             // Map each skolemized region to a vector of other regions that it
 136             // must be equated with. (Note that this vector may include other
 137             // skolemized regions from `skol_map`.)
 138             let skol_resolution_map: FxHashMap<_, _> =
 139                 skol_map
 140                 .iter()
 141                 .map(|(&br, &skol)| {
 142                     let tainted_regions =
 143                         self.infcx.tainted_regions(snapshot,
 144                                                    skol,
 145                                                    TaintDirections::incoming()); // [1]
 146
 147                     // [1] this routine executes after the skolemized
 148                     // regions have been *equated* with something
 149                     // else, so examining the incoming edges ought to
 150                     // be enough to collect all constraints
 151
 152                     (skol, (br, tainted_regions))
 153                 })
 154                 .collect();
 155
 156             // For each skolemized region, pick a representative -- which can
 157             // be any region from the sets above, except for other members of
 158             // `skol_map`. There should always be a representative if things
 159             // are properly well-formed.
 160             let mut unconstrained_regions = vec![];
 161             let skol_representatives: FxHashMap<_, _> =
 162                 skol_resolution_map
 163                 .iter()
 164                 .map(|(&skol, &(br, ref regions))| {
 165                     let representative =
 166                         regions.iter()
 167                                .filter(|&&r| !skol_resolution_map.contains_key(r))
 168                                .cloned()
 169                                .next()
 170                                .unwrap_or_else(|| { // [1]
 171                                    unconstrained_regions.push(br);
 172                                    self.infcx.next_region_var(
 173                                        LateBoundRegion(span, br, HigherRankedType))
 174                                });
 175
 176                     // [1] There should always be a representative,
 177                     // unless the higher-ranked region did not appear
 178                     // in the values being matched. We should reject
 179                     // as ill-formed cases that can lead to this, but
 180                     // right now we sometimes issue warnings (see
 181                     // #32330).
 182
 183                     (skol, representative)
 184                 })
 185                 .collect();
 186
 187             // Equate all the members of each skolemization set with the
 188             // representative.
 189             for (skol, &(_br, ref regions)) in &skol_resolution_map {
 190                 let representative = &skol_representatives[skol];
 191                 debug!("higher_ranked_match: \
 192                         skol={:?} representative={:?} regions={:?}",
 193                        skol, representative, regions);
 194                 for region in regions.iter()
 195                                      .filter(|&r| !skol_resolution_map.contains_key(r))
 196                                      .filter(|&r| r != representative)
 197                 {
 198                     let origin = SubregionOrigin::Subtype(self.trace.clone());
 199                     self.infcx.region_vars.make_eqregion(origin,
 200                                                          *representative,
 201                                                          *region);
 202                 }
 203             }
 204
 205             // Replace the skolemized regions appearing in value with
 206             // their representatives
 207             let a_value =
 208                 fold_regions_in(
 209                     self.tcx(),
 210                     &a_value,
 211                     |r, _| skol_representatives.get(&r).cloned().unwrap_or(r));
 212
 213             debug!("higher_ranked_match: value={:?}", a_value);
 214
 215             // We are now done with these skolemized variables.
 216             self.infcx.pop_skolemized(skol_map, snapshot);
 217
 218             Ok(HrMatchResult {
 219                 value: a_value,
 220                 unconstrained_regions: unconstrained_regions,
 221             })
 222         });
 223     }
 224
 225     pub fn higher_ranked_lub<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool)
 226                                 -> RelateResult<'tcx, Binder<T>>
 227         where T: Relate<'tcx>
 228     {
 229         // Start a snapshot so we can examine "all bindings that were
 230         // created as part of this type comparison".
 231         return self.infcx.commit_if_ok(|snapshot| {
 232             // Instantiate each bound region with a fresh region variable.
 233             let span = self.trace.cause.span;
 234             let (a_with_fresh, a_map) =
 235                 self.infcx.replace_late_bound_regions_with_fresh_var(
 236                     span, HigherRankedType, a);
 237             let (b_with_fresh, _) =
 238                 self.infcx.replace_late_bound_regions_with_fresh_var(
 239                     span, HigherRankedType, b);
 240
 241             // Collect constraints.
 242             let result0 =
 243                 self.lub(a_is_expected).relate(&a_with_fresh, &b_with_fresh)?;
 244             let result0 =
 245                 self.infcx.resolve_type_vars_if_possible(&result0);
 246             debug!("lub result0 = {:?}", result0);
 247
 248             // Generalize the regions appearing in result0 if possible
 249             let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot);
 250             let span = self.trace.cause.span;
 251             let result1 =
 252                 fold_regions_in(
 253                     self.tcx(),
 254                     &result0,
 255                     |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn,
 256                                                     &new_vars, &a_map, r));
 257
 258             debug!("lub({:?},{:?}) = {:?}",
 259                    a,
 260                    b,
 261                    result1);
 262
 263             Ok(ty::Binder(result1))
 264         });
 265
 266         fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 267                                              span: Span,
 268                                              snapshot: &CombinedSnapshot,
 269                                              debruijn: ty::DebruijnIndex,
 270                                              new_vars: &[ty::RegionVid],
 271                                              a_map: &FxHashMap<ty::BoundRegion, &'tcx ty::Region>,
 272                                              r0: &'tcx ty::Region)
 273                                              -> &'tcx ty::Region {
 274             // Regions that pre-dated the LUB computation stay as they are.
 275             if !is_var_in_set(new_vars, r0) {
 276                 assert!(!r0.is_bound());
 277                 debug!("generalize_region(r0={:?}): not new variable", r0);
 278                 return r0;
 279             }
 280
 281             let tainted = infcx.tainted_regions(snapshot, r0, TaintDirections::both());
 282
 283             // Variables created during LUB computation which are
 284             // *related* to regions that pre-date the LUB computation
 285             // stay as they are.
 286             if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) {
 287                 debug!("generalize_region(r0={:?}): \
 288                         non-new-variables found in {:?}",
 289                        r0, tainted);
 290                 assert!(!r0.is_bound());
 291                 return r0;
 292             }
 293
 294             // Otherwise, the variable must be associated with at
 295             // least one of the variables representing bound regions
 296             // in both A and B.  Replace the variable with the "first"
 297             // bound region from A that we find it to be associated
 298             // with.
 299             for (a_br, a_r) in a_map {
 300                 if tainted.iter().any(|x| x == a_r) {
 301                     debug!("generalize_region(r0={:?}): \
 302                             replacing with {:?}, tainted={:?}",
 303                            r0, *a_br, tainted);
 304                     return infcx.tcx.mk_region(ty::ReLateBound(debruijn, *a_br));
 305                 }
 306             }
 307
 308             span_bug!(
 309                 span,
 310                 "region {:?} is not associated with any bound region from A!",
 311                 r0)
 312         }
 313     }
 314
 315     pub fn higher_ranked_glb<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool)
 316                                 -> RelateResult<'tcx, Binder<T>>
 317         where T: Relate<'tcx>
 318     {
 319         debug!("higher_ranked_glb({:?}, {:?})",
 320                a, b);
 321
 322         // Make a snapshot so we can examine "all bindings that were
 323         // created as part of this type comparison".
 324         return self.infcx.commit_if_ok(|snapshot| {
 325             // Instantiate each bound region with a fresh region variable.
 326             let (a_with_fresh, a_map) =
 327                 self.infcx.replace_late_bound_regions_with_fresh_var(
 328                     self.trace.cause.span, HigherRankedType, a);
 329             let (b_with_fresh, b_map) =
 330                 self.infcx.replace_late_bound_regions_with_fresh_var(
 331                     self.trace.cause.span, HigherRankedType, b);
 332             let a_vars = var_ids(self, &a_map);
 333             let b_vars = var_ids(self, &b_map);
 334
 335             // Collect constraints.
 336             let result0 =
 337                 self.glb(a_is_expected).relate(&a_with_fresh, &b_with_fresh)?;
 338             let result0 =
 339                 self.infcx.resolve_type_vars_if_possible(&result0);
 340             debug!("glb result0 = {:?}", result0);
 341
 342             // Generalize the regions appearing in result0 if possible
 343             let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot);
 344             let span = self.trace.cause.span;
 345             let result1 =
 346                 fold_regions_in(
 347                     self.tcx(),
 348                     &result0,
 349                     |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn,
 350                                                     &new_vars,
 351                                                     &a_map, &a_vars, &b_vars,
 352                                                     r));
 353
 354             debug!("glb({:?},{:?}) = {:?}",
 355                    a,
 356                    b,
 357                    result1);
 358
 359             Ok(ty::Binder(result1))
 360         });
 361
 362         fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 363                                              span: Span,
 364                                              snapshot: &CombinedSnapshot,
 365                                              debruijn: ty::DebruijnIndex,
 366                                              new_vars: &[ty::RegionVid],
 367                                              a_map: &FxHashMap<ty::BoundRegion, &'tcx ty::Region>,
 368                                              a_vars: &[ty::RegionVid],
 369                                              b_vars: &[ty::RegionVid],
 370                                              r0: &'tcx ty::Region)
 371                                              -> &'tcx ty::Region {
 372             if !is_var_in_set(new_vars, r0) {
 373                 assert!(!r0.is_bound());
 374                 return r0;
 375             }
 376
 377             let tainted = infcx.tainted_regions(snapshot, r0, TaintDirections::both());
 378
 379             let mut a_r = None;
 380             let mut b_r = None;
 381             let mut only_new_vars = true;
 382             for r in &tainted {
 383                 if is_var_in_set(a_vars, *r) {
 384                     if a_r.is_some() {
 385                         return fresh_bound_variable(infcx, debruijn);
 386                     } else {
 387                         a_r = Some(*r);
 388                     }
 389                 } else if is_var_in_set(b_vars, *r) {
 390                     if b_r.is_some() {
 391                         return fresh_bound_variable(infcx, debruijn);
 392                     } else {
 393                         b_r = Some(*r);
 394                     }
 395                 } else if !is_var_in_set(new_vars, *r) {
 396                     only_new_vars = false;
 397                 }
 398             }
 399
 400             // NB---I do not believe this algorithm computes
 401             // (necessarily) the GLB.  As written it can
 402             // spuriously fail. In particular, if there is a case
 403             // like: |fn(&a)| and fn(fn(&b)), where a and b are
 404             // free, it will return fn(&c) where c = GLB(a,b).  If
 405             // however this GLB is not defined, then the result is
 406             // an error, even though something like
 407             // "fn<X>(fn(&X))" where X is bound would be a
 408             // subtype of both of those.
 409             //
 410             // The problem is that if we were to return a bound
 411             // variable, we'd be computing a lower-bound, but not
 412             // necessarily the *greatest* lower-bound.
 413             //
 414             // Unfortunately, this problem is non-trivial to solve,
 415             // because we do not know at the time of computing the GLB
 416             // whether a GLB(a,b) exists or not, because we haven't
 417             // run region inference (or indeed, even fully computed
 418             // the region hierarchy!). The current algorithm seems to
 419             // works ok in practice.
 420
 421             if a_r.is_some() && b_r.is_some() && only_new_vars {
 422                 // Related to exactly one bound variable from each fn:
 423                 return rev_lookup(infcx, span, a_map, a_r.unwrap());
 424             } else if a_r.is_none() && b_r.is_none() {
 425                 // Not related to bound variables from either fn:
 426                 assert!(!r0.is_bound());
 427                 return r0;
 428             } else {
 429                 // Other:
 430                 return fresh_bound_variable(infcx, debruijn);
 431             }
 432         }
 433
 434         fn rev_lookup<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 435                                       span: Span,
 436                                       a_map: &FxHashMap<ty::BoundRegion, &'tcx ty::Region>,
 437                                       r: &'tcx ty::Region) -> &'tcx ty::Region
 438         {
 439             for (a_br, a_r) in a_map {
 440                 if *a_r == r {
 441                     return infcx.tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1), *a_br));
 442                 }
 443             }
 444             span_bug!(
 445                 span,
 446                 "could not find original bound region for {:?}",
 447                 r);
 448         }
 449
 450         fn fresh_bound_variable<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 451                                                 debruijn: ty::DebruijnIndex)
 452                                                 -> &'tcx ty::Region {
 453             infcx.region_vars.new_bound(debruijn)
 454         }
 455     }
 456 }
 457
 458 fn var_ids<'a, 'gcx, 'tcx>(fields: &CombineFields<'a, 'gcx, 'tcx>,
 459                            map: &FxHashMap<ty::BoundRegion, &'tcx ty::Region>)
 460                            -> Vec<ty::RegionVid> {
 461     map.iter()
 462        .map(|(_, &r)| match *r {
 463            ty::ReVar(r) => { r }
 464            _ => {
 465                span_bug!(
 466                    fields.trace.cause.span,
 467                    "found non-region-vid: {:?}",
 468                    r);
 469            }
 470        })
 471        .collect()
 472 }
 473
 474 fn is_var_in_set(new_vars: &[ty::RegionVid], r: &ty::Region) -> bool {
 475     match *r {
 476         ty::ReVar(ref v) => new_vars.iter().any(|x| x == v),
 477         _ => false
 478     }
 479 }
 480
 481 fn fold_regions_in<'a, 'gcx, 'tcx, T, F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 482                                          unbound_value: &T,
 483                                          mut fldr: F)
 484                                          -> T
 485     where T: TypeFoldable<'tcx>,
 486           F: FnMut(&'tcx ty::Region, ty::DebruijnIndex) -> &'tcx ty::Region,
 487 {
 488     tcx.fold_regions(unbound_value, &mut false, |region, current_depth| {
 489         // we should only be encountering "escaping" late-bound regions here,
 490         // because the ones at the current level should have been replaced
 491         // with fresh variables
 492         assert!(match *region {
 493             ty::ReLateBound(..) => false,
 494             _ => true
 495         });
 496
 497         fldr(region, ty::DebruijnIndex::new(current_depth))
 498     })
 499 }
 500
 501 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 502     fn tainted_regions(&self,
 503                        snapshot: &CombinedSnapshot,
 504                        r: &'tcx ty::Region,
 505                        directions: TaintDirections)
 506                        -> FxHashSet<&'tcx ty::Region> {
 507         self.region_vars.tainted(&snapshot.region_vars_snapshot, r, directions)
 508     }
 509
 510     fn region_vars_confined_to_snapshot(&self,
 511                                         snapshot: &CombinedSnapshot)
 512                                         -> Vec<ty::RegionVid>
 513     {
 514         /*!
 515          * Returns the set of region variables that do not affect any
 516          * types/regions which existed before `snapshot` was
 517          * started. This is used in the sub/lub/glb computations. The
 518          * idea here is that when we are computing lub/glb of two
 519          * regions, we sometimes create intermediate region variables.
 520          * Those region variables may touch some of the skolemized or
 521          * other "forbidden" regions we created to replace bound
 522          * regions, but they don't really represent an "external"
 523          * constraint.
 524          *
 525          * However, sometimes fresh variables are created for other
 526          * purposes too, and those *may* represent an external
 527          * constraint. In particular, when a type variable is
 528          * instantiated, we create region variables for all the
 529          * regions that appear within, and if that type variable
 530          * pre-existed the snapshot, then those region variables
 531          * represent external constraints.
 532          *
 533          * An example appears in the unit test
 534          * `sub_free_bound_false_infer`.  In this test, we want to
 535          * know whether
 536          *
 537          * ```rust
 538          * fn(_#0t) <: for<'a> fn(&'a int)
 539          * ```
 540          *
 541          * Note that the subtype has a type variable. Because the type
 542          * variable can't be instantiated with a region that is bound
 543          * in the fn signature, this comparison ought to fail. But if
 544          * we're not careful, it will succeed.
 545          *
 546          * The reason is that when we walk through the subtyping
 547          * algorith, we begin by replacing `'a` with a skolemized
 548          * variable `'1`. We then have `fn(_#0t) <: fn(&'1 int)`. This
 549          * can be made true by unifying `_#0t` with `&'1 int`. In the
 550          * process, we create a fresh variable for the skolemized
 551          * region, `'$2`, and hence we have that `_#0t == &'$2
 552          * int`. However, because `'$2` was created during the sub
 553          * computation, if we're not careful we will erroneously
 554          * assume it is one of the transient region variables
 555          * representing a lub/glb internally. Not good.
 556          *
 557          * To prevent this, we check for type variables which were
 558          * unified during the snapshot, and say that any region
 559          * variable created during the snapshot but which finds its
 560          * way into a type variable is considered to "escape" the
 561          * snapshot.
 562          */
 563
 564         let mut region_vars =
 565             self.region_vars.vars_created_since_snapshot(&snapshot.region_vars_snapshot);
 566
 567         let escaping_types =
 568             self.type_variables.borrow_mut().types_escaping_snapshot(&snapshot.type_snapshot);
 569
 570         let mut escaping_region_vars = FxHashSet();
 571         for ty in &escaping_types {
 572             self.tcx.collect_regions(ty, &mut escaping_region_vars);
 573         }
 574
 575         region_vars.retain(|&region_vid| {
 576             let r = ty::ReVar(region_vid);
 577             !escaping_region_vars.contains(&r)
 578         });
 579
 580         debug!("region_vars_confined_to_snapshot: region_vars={:?} escaping_types={:?}",
 581                region_vars,
 582                escaping_types);
 583
 584         region_vars
 585     }
 586
 587     /// Replace all regions bound by `binder` with skolemized regions and
 588     /// return a map indicating which bound-region was replaced with what
 589     /// skolemized region. This is the first step of checking subtyping
 590     /// when higher-ranked things are involved.
 591     ///
 592     /// **Important:** you must call this function from within a snapshot.
 593     /// Moreover, before committing the snapshot, you must eventually call
 594     /// either `plug_leaks` or `pop_skolemized` to remove the skolemized
 595     /// regions. If you rollback the snapshot (or are using a probe), then
 596     /// the pop occurs as part of the rollback, so an explicit call is not
 597     /// needed (but is also permitted).
 598     ///
 599     /// See `README.md` for more details.
 600     pub fn skolemize_late_bound_regions<T>(&self,
 601                                            binder: &ty::Binder<T>,
 602                                            snapshot: &CombinedSnapshot)
 603                                            -> (T, SkolemizationMap<'tcx>)
 604         where T : TypeFoldable<'tcx>
 605     {
 606         let (result, map) = self.tcx.replace_late_bound_regions(binder, |br| {
 607             self.region_vars.push_skolemized(br, &snapshot.region_vars_snapshot)
 608         });
 609
 610         debug!("skolemize_bound_regions(binder={:?}, result={:?}, map={:?})",
 611                binder,
 612                result,
 613                map);
 614
 615         (result, map)
 616     }
 617
 618     /// Searches the region constriants created since `snapshot` was started
 619     /// and checks to determine whether any of the skolemized regions created
 620     /// in `skol_map` would "escape" -- meaning that they are related to
 621     /// other regions in some way. If so, the higher-ranked subtyping doesn't
 622     /// hold. See `README.md` for more details.
 623     pub fn leak_check(&self,
 624                       overly_polymorphic: bool,
 625                       span: Span,
 626                       skol_map: &SkolemizationMap<'tcx>,
 627                       snapshot: &CombinedSnapshot)
 628                       -> RelateResult<'tcx, ()>
 629     {
 630         debug!("leak_check: skol_map={:?}",
 631                skol_map);
 632
 633         // ## Issue #32330 warnings
 634         //
 635         // When Issue #32330 is fixed, a certain number of late-bound
 636         // regions (LBR) will become early-bound. We wish to issue
 637         // warnings when the result of `leak_check` relies on such LBR, as
 638         // that means that compilation will likely start to fail.
 639         //
 640         // Recall that when we do a "HR subtype" check, we replace all
 641         // late-bound regions (LBR) in the subtype with fresh variables,
 642         // and skolemize the late-bound regions in the supertype. If those
 643         // skolemized regions from the supertype wind up being
 644         // super-regions (directly or indirectly) of either
 645         //
 646         // - another skolemized region; or,
 647         // - some region that pre-exists the HR subtype check
 648         //   - e.g., a region variable that is not one of those created
 649         //     to represent bound regions in the subtype
 650         //
 651         // then leak-check (and hence the subtype check) fails.
 652         //
 653         // What will change when we fix #32330 is that some of the LBR in the
 654         // subtype may become early-bound. In that case, they would no longer be in
 655         // the "permitted set" of variables that can be related to a skolemized
 656         // type.
 657         //
 658         // So the foundation for this warning is to collect variables that we found
 659         // to be related to a skolemized type. For each of them, we have a
 660         // `BoundRegion` which carries a `Issue32330` flag. We check whether any of
 661         // those flags indicate that this variable was created from a lifetime
 662         // that will change from late- to early-bound. If so, we issue a warning
 663         // indicating that the results of compilation may change.
 664         //
 665         // This is imperfect, since there are other kinds of code that will not
 666         // compile once #32330 is fixed. However, it fixes the errors observed in
 667         // practice on crater runs.
 668         let mut warnings = vec![];
 669
 670         let new_vars = self.region_vars_confined_to_snapshot(snapshot);
 671         for (&skol_br, &skol) in skol_map {
 672             // The inputs to a skolemized variable can only
 673             // be itself or other new variables.
 674             let incoming_taints = self.tainted_regions(snapshot,
 675                                                        skol,
 676                                                        TaintDirections::both());
 677             for &tainted_region in &incoming_taints {
 678                 // Each skolemized should only be relatable to itself
 679                 // or new variables:
 680                 match *tainted_region {
 681                     ty::ReVar(vid) => {
 682                         if new_vars.contains(&vid) {
 683                             warnings.extend(
 684                                 match self.region_vars.var_origin(vid) {
 685                                     LateBoundRegion(_,
 686                                                     ty::BrNamed(.., wc),
 687                                                     _) => Some(wc),
 688                                     _ => None,
 689                                 });
 690                             continue;
 691                         }
 692                     }
 693                     _ => {
 694                         if tainted_region == skol { continue; }
 695                     }
 696                 };
 697
 698                 debug!("{:?} (which replaced {:?}) is tainted by {:?}",
 699                        skol,
 700                        skol_br,
 701                        tainted_region);
 702
 703                 if overly_polymorphic {
 704                     debug!("Overly polymorphic!");
 705                     return Err(TypeError::RegionsOverlyPolymorphic(skol_br,
 706                                                                    tainted_region));
 707                 } else {
 708                     debug!("Not as polymorphic!");
 709                     return Err(TypeError::RegionsInsufficientlyPolymorphic(skol_br,
 710                                                                            tainted_region));
 711                 }
 712             }
 713         }
 714
 715         self.issue_32330_warnings(span, &warnings);
 716
 717         Ok(())
 718     }
 719
 720     /// This code converts from skolemized regions back to late-bound
 721     /// regions. It works by replacing each region in the taint set of a
 722     /// skolemized region with a bound-region. The bound region will be bound
 723     /// by the outer-most binder in `value`; the caller must ensure that there is
 724     /// such a binder and it is the right place.
 725     ///
 726     /// This routine is only intended to be used when the leak-check has
 727     /// passed; currently, it's used in the trait matching code to create
 728     /// a set of nested obligations frmo an impl that matches against
 729     /// something higher-ranked.  More details can be found in
 730     /// `librustc/middle/traits/README.md`.
 731     ///
 732     /// As a brief example, consider the obligation `for<'a> Fn(&'a int)
 733     /// -> &'a int`, and the impl:
 734     ///
 735     ///     impl<A,R> Fn<A,R> for SomethingOrOther
 736     ///         where A : Clone
 737     ///     { ... }
 738     ///
 739     /// Here we will have replaced `'a` with a skolemized region
 740     /// `'0`. This means that our substitution will be `{A=>&'0
 741     /// int, R=>&'0 int}`.
 742     ///
 743     /// When we apply the substitution to the bounds, we will wind up with
 744     /// `&'0 int : Clone` as a predicate. As a last step, we then go and
 745     /// replace `'0` with a late-bound region `'a`.  The depth is matched
 746     /// to the depth of the predicate, in this case 1, so that the final
 747     /// predicate is `for<'a> &'a int : Clone`.
 748     pub fn plug_leaks<T>(&self,
 749                          skol_map: SkolemizationMap<'tcx>,
 750                          snapshot: &CombinedSnapshot,
 751                          value: T) -> T
 752         where T : TypeFoldable<'tcx>
 753     {
 754         debug!("plug_leaks(skol_map={:?}, value={:?})",
 755                skol_map,
 756                value);
 757
 758         if skol_map.is_empty() {
 759             return value;
 760         }
 761
 762         // Compute a mapping from the "taint set" of each skolemized
 763         // region back to the `ty::BoundRegion` that it originally
 764         // represented. Because `leak_check` passed, we know that
 765         // these taint sets are mutually disjoint.
 766         let inv_skol_map: FxHashMap<&'tcx ty::Region, ty::BoundRegion> =
 767             skol_map
 768             .iter()
 769             .flat_map(|(&skol_br, &skol)| {
 770                 self.tainted_regions(snapshot, skol, TaintDirections::both())
 771                     .into_iter()
 772                     .map(move |tainted_region| (tainted_region, skol_br))
 773             })
 774             .collect();
 775
 776         debug!("plug_leaks: inv_skol_map={:?}",
 777                inv_skol_map);
 778
 779         // Remove any instantiated type variables from `value`; those can hide
 780         // references to regions from the `fold_regions` code below.
 781         let value = self.resolve_type_vars_if_possible(&value);
 782
 783         // Map any skolemization byproducts back to a late-bound
 784         // region. Put that late-bound region at whatever the outermost
 785         // binder is that we encountered in `value`. The caller is
 786         // responsible for ensuring that (a) `value` contains at least one
 787         // binder and (b) that binder is the one we want to use.
 788         let result = self.tcx.fold_regions(&value, &mut false, |r, current_depth| {
 789             match inv_skol_map.get(&r) {
 790                 None => r,
 791                 Some(br) => {
 792                     // It is the responsibility of the caller to ensure
 793                     // that each skolemized region appears within a
 794                     // binder. In practice, this routine is only used by
 795                     // trait checking, and all of the skolemized regions
 796                     // appear inside predicates, which always have
 797                     // binders, so this assert is satisfied.
 798                     assert!(current_depth > 1);
 799
 800                     // since leak-check passed, this skolemized region
 801                     // should only have incoming edges from variables
 802                     // (which ought not to escape the snapshot, but we
 803                     // don't check that) or itself
 804                     assert!(
 805                         match *r {
 806                             ty::ReVar(_) => true,
 807                             ty::ReSkolemized(_, ref br1) => br == br1,
 808                             _ => false,
 809                         },
 810                         "leak-check would have us replace {:?} with {:?}",
 811                         r, br);
 812
 813                     self.tcx.mk_region(ty::ReLateBound(
 814                         ty::DebruijnIndex::new(current_depth - 1), br.clone()))
 815                 }
 816             }
 817         });
 818
 819         self.pop_skolemized(skol_map, snapshot);
 820
 821         debug!("plug_leaks: result={:?}", result);
 822
 823         result
 824     }
 825
 826     /// Pops the skolemized regions found in `skol_map` from the region
 827     /// inference context. Whenever you create skolemized regions via
 828     /// `skolemize_late_bound_regions`, they must be popped before you
 829     /// commit the enclosing snapshot (if you do not commit, e.g. within a
 830     /// probe or as a result of an error, then this is not necessary, as
 831     /// popping happens as part of the rollback).
 832     ///
 833     /// Note: popping also occurs implicitly as part of `leak_check`.
 834     pub fn pop_skolemized(&self,
 835                           skol_map: SkolemizationMap<'tcx>,
 836                           snapshot: &CombinedSnapshot)
 837     {
 838         debug!("pop_skolemized({:?})", skol_map);
 839         let skol_regions: FxHashSet<_> = skol_map.values().cloned().collect();
 840         self.region_vars.pop_skolemized(&skol_regions, &snapshot.region_vars_snapshot);
 841         if !skol_map.is_empty() {
 842             self.projection_cache.borrow_mut().rollback_skolemized(
 843                 &snapshot.projection_cache_snapshot);
 844         }
 845     }
 846 }