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