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