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