src/librustc/infer/region_constraints/mod.rs

   1 // Copyright 2012-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 //! See README.md
  12
  13 use self::UndoLogEntry::*;
  14 use self::CombineMapType::*;
  15
  16 use super::{MiscVariable, RegionVariableOrigin, SubregionOrigin};
  17 use super::unify_key;
  18
  19 use rustc_data_structures::indexed_vec::IndexVec;
  20 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  21 use rustc_data_structures::unify as ut;
  22 use ty::{self, Ty, TyCtxt};
  23 use ty::{Region, RegionVid};
  24 use ty::ReStatic;
  25 use ty::{BrFresh, ReLateBound, ReVar};
  26
  27 use std::collections::BTreeMap;
  28 use std::{cmp, fmt, mem, u32};
  29
  30 mod taint;
  31
  32 pub struct RegionConstraintCollector<'tcx> {
  33     /// For each `RegionVid`, the corresponding `RegionVariableOrigin`.
  34     var_infos: IndexVec<RegionVid, RegionVariableInfo>,
  35
  36     data: RegionConstraintData<'tcx>,
  37
  38     /// For a given pair of regions (R1, R2), maps to a region R3 that
  39     /// is designated as their LUB (edges R1 <= R3 and R2 <= R3
  40     /// exist). This prevents us from making many such regions.
  41     lubs: CombineMap<'tcx>,
  42
  43     /// For a given pair of regions (R1, R2), maps to a region R3 that
  44     /// is designated as their GLB (edges R3 <= R1 and R3 <= R2
  45     /// exist). This prevents us from making many such regions.
  46     glbs: CombineMap<'tcx>,
  47
  48     /// Global counter used during the GLB algorithm to create unique
  49     /// names for fresh bound regions
  50     bound_count: u32,
  51
  52     /// The undo log records actions that might later be undone.
  53     ///
  54     /// Note: when the undo_log is empty, we are not actively
  55     /// snapshotting. When the `start_snapshot()` method is called, we
  56     /// push an OpenSnapshot entry onto the list to indicate that we
  57     /// are now actively snapshotting. The reason for this is that
  58     /// otherwise we end up adding entries for things like the lower
  59     /// bound on a variable and so forth, which can never be rolled
  60     /// back.
  61     undo_log: Vec<UndoLogEntry<'tcx>>,
  62
  63     /// When we add a R1 == R2 constriant, we currently add (a) edges
  64     /// R1 <= R2 and R2 <= R1 and (b) we unify the two regions in this
  65     /// table. You can then call `opportunistic_resolve_var` early
  66     /// which will map R1 and R2 to some common region (i.e., either
  67     /// R1 or R2). This is important when dropck and other such code
  68     /// is iterating to a fixed point, because otherwise we sometimes
  69     /// would wind up with a fresh stream of region variables that
  70     /// have been equated but appear distinct.
  71     unification_table: ut::UnificationTable<ut::InPlace<ty::RegionVid>>,
  72
  73     /// a flag set to true when we perform any unifications; this is used
  74     /// to micro-optimize `take_and_reset_data`
  75     any_unifications: bool,
  76 }
  77
  78 pub type VarInfos = IndexVec<RegionVid, RegionVariableInfo>;
  79
  80 /// The full set of region constraints gathered up by the collector.
  81 /// Describes constraints between the region variables and other
  82 /// regions, as well as other conditions that must be verified, or
  83 /// assumptions that can be made.
  84 #[derive(Debug, Default, Clone)]
  85 pub struct RegionConstraintData<'tcx> {
  86     /// Constraints of the form `A <= B`, where either `A` or `B` can
  87     /// be a region variable (or neither, as it happens).
  88     pub constraints: BTreeMap<Constraint<'tcx>, SubregionOrigin<'tcx>>,
  89
  90     /// A "verify" is something that we need to verify after inference
  91     /// is done, but which does not directly affect inference in any
  92     /// way.
  93     ///
  94     /// An example is a `A <= B` where neither `A` nor `B` are
  95     /// inference variables.
  96     pub verifys: Vec<Verify<'tcx>>,
  97
  98     /// A "given" is a relationship that is known to hold. In
  99     /// particular, we often know from closure fn signatures that a
 100     /// particular free region must be a subregion of a region
 101     /// variable:
 102     ///
 103     ///    foo.iter().filter(<'a> |x: &'a &'b T| ...)
 104     ///
 105     /// In situations like this, `'b` is in fact a region variable
 106     /// introduced by the call to `iter()`, and `'a` is a bound region
 107     /// on the closure (as indicated by the `<'a>` prefix). If we are
 108     /// naive, we wind up inferring that `'b` must be `'static`,
 109     /// because we require that it be greater than `'a` and we do not
 110     /// know what `'a` is precisely.
 111     ///
 112     /// This hashmap is used to avoid that naive scenario. Basically
 113     /// we record the fact that `'a <= 'b` is implied by the fn
 114     /// signature, and then ignore the constraint when solving
 115     /// equations. This is a bit of a hack but seems to work.
 116     pub givens: FxHashSet<(Region<'tcx>, ty::RegionVid)>,
 117 }
 118
 119 /// A constraint that influences the inference process.
 120 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)]
 121 pub enum Constraint<'tcx> {
 122     /// One region variable is subregion of another
 123     VarSubVar(RegionVid, RegionVid),
 124
 125     /// Concrete region is subregion of region variable
 126     RegSubVar(Region<'tcx>, RegionVid),
 127
 128     /// Region variable is subregion of concrete region. This does not
 129     /// directly affect inference, but instead is checked after
 130     /// inference is complete.
 131     VarSubReg(RegionVid, Region<'tcx>),
 132
 133     /// A constraint where neither side is a variable. This does not
 134     /// directly affect inference, but instead is checked after
 135     /// inference is complete.
 136     RegSubReg(Region<'tcx>, Region<'tcx>),
 137 }
 138
 139 /// VerifyGenericBound(T, _, R, RS): The parameter type `T` (or
 140 /// associated type) must outlive the region `R`. `T` is known to
 141 /// outlive `RS`. Therefore verify that `R <= RS[i]` for some
 142 /// `i`. Inference variables may be involved (but this verification
 143 /// step doesn't influence inference).
 144 #[derive(Debug, Clone)]
 145 pub struct Verify<'tcx> {
 146     pub kind: GenericKind<'tcx>,
 147     pub origin: SubregionOrigin<'tcx>,
 148     pub region: Region<'tcx>,
 149     pub bound: VerifyBound<'tcx>,
 150 }
 151
 152 #[derive(Copy, Clone, PartialEq, Eq)]
 153 pub enum GenericKind<'tcx> {
 154     Param(ty::ParamTy),
 155     Projection(ty::ProjectionTy<'tcx>),
 156 }
 157
 158 EnumTypeFoldableImpl! {
 159     impl<'tcx> TypeFoldable<'tcx> for GenericKind<'tcx> {
 160         (GenericKind::Param)(a),
 161         (GenericKind::Projection)(a),
 162     }
 163 }
 164
 165 /// Describes the things that some `GenericKind` value G is known to
 166 /// outlive. Each variant of `VerifyBound` can be thought of as a
 167 /// function:
 168 ///
 169 ///     fn(min: Region) -> bool { .. }
 170 ///
 171 /// where `true` means that the region `min` meets that `G: min`.
 172 /// (False means nothing.)
 173 ///
 174 /// So, for example, if we have the type `T` and we have in scope that
 175 /// `T: 'a` and `T: 'b`, then the verify bound might be:
 176 ///
 177 ///     fn(min: Region) -> bool {
 178 ///        ('a: min) || ('b: min)
 179 ///     }
 180 ///
 181 /// This is described with a `AnyRegion('a, 'b)` node.
 182 #[derive(Debug, Clone)]
 183 pub enum VerifyBound<'tcx> {
 184     /// Given a kind K and a bound B, expands to a function like the
 185     /// following, where `G` is the generic for which this verify
 186     /// bound was created:
 187     ///
 188     ///     fn(min) -> bool {
 189     ///       if G == K {
 190     ///         B(min)
 191     ///       } else {
 192     ///         false
 193     ///       }
 194     ///     }
 195     ///
 196     /// In other words, if the generic `G` that we are checking is
 197     /// equal to `K`, then check the associated verify bound
 198     /// (otherwise, false).
 199     ///
 200     /// This is used when we have something in the environment that
 201     /// may or may not be relevant, depending on the region inference
 202     /// results. For example, we may have `where <T as
 203     /// Trait<'a>>::Item: 'b` in our where clauses. If we are
 204     /// generating the verify-bound for `<T as Trait<'0>>::Item`, then
 205     /// this where-clause is only relevant if `'0` winds up inferred
 206     /// to `'a`.
 207     ///
 208     /// So we would compile to a verify-bound like
 209     ///
 210     ///     IfEq(<T as Trait<'a>>::Item, AnyRegion('a))
 211     ///
 212     /// meaning, if the subject G is equal to `<T as Trait<'a>>::Item`
 213     /// (after inference), and `'a: min`, then `G: min`.
 214     IfEq(Ty<'tcx>, Box<VerifyBound<'tcx>>),
 215
 216     /// Given a region `R`, expands to the function:
 217     ///
 218     ///     fn(min) -> bool {
 219     ///       R: min
 220     ///     }
 221     ///
 222     /// This is used when we can establish that `G: R` -- therefore,
 223     /// if `R: min`, then by transitivity `G: min`.
 224     OutlivedBy(Region<'tcx>),
 225
 226     /// Given a set of bounds `B`, expands to the function:
 227     ///
 228     ///     fn(min) -> bool {
 229     ///       exists (b in B) { b(min) }
 230     ///     }
 231     ///
 232     /// In other words, if we meet some bound in `B`, that suffices.
 233     /// This is used when all the bounds in `B` are known to apply to
 234     /// G.
 235     AnyBound(Vec<VerifyBound<'tcx>>),
 236
 237     /// Given a set of bounds `B`, expands to the function:
 238     ///
 239     ///     fn(min) -> bool {
 240     ///       forall (b in B) { b(min) }
 241     ///     }
 242     ///
 243     /// In other words, if we meet *all* bounds in `B`, that suffices.
 244     /// This is used when *some* bound in `B` is known to suffice, but
 245     /// we don't know which.
 246     AllBounds(Vec<VerifyBound<'tcx>>),
 247 }
 248
 249 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 250 struct TwoRegions<'tcx> {
 251     a: Region<'tcx>,
 252     b: Region<'tcx>,
 253 }
 254
 255 #[derive(Copy, Clone, PartialEq)]
 256 enum UndoLogEntry<'tcx> {
 257     /// Pushed when we start a snapshot.
 258     OpenSnapshot,
 259
 260     /// Replaces an `OpenSnapshot` when a snapshot is committed, but
 261     /// that snapshot is not the root. If the root snapshot is
 262     /// unrolled, all nested snapshots must be committed.
 263     CommitedSnapshot,
 264
 265     /// We added `RegionVid`
 266     AddVar(RegionVid),
 267
 268     /// We added the given `constraint`
 269     AddConstraint(Constraint<'tcx>),
 270
 271     /// We added the given `verify`
 272     AddVerify(usize),
 273
 274     /// We added the given `given`
 275     AddGiven(Region<'tcx>, ty::RegionVid),
 276
 277     /// We added a GLB/LUB "combination variable"
 278     AddCombination(CombineMapType, TwoRegions<'tcx>),
 279
 280     /// During skolemization, we sometimes purge entries from the undo
 281     /// log in a kind of minisnapshot (unlike other snapshots, this
 282     /// purging actually takes place *on success*). In that case, we
 283     /// replace the corresponding entry with `Noop` so as to avoid the
 284     /// need to do a bunch of swapping. (We can't use `swap_remove` as
 285     /// the order of the vector is important.)
 286     Purged,
 287 }
 288
 289 #[derive(Copy, Clone, PartialEq)]
 290 enum CombineMapType {
 291     Lub,
 292     Glb,
 293 }
 294
 295 type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>;
 296
 297 #[derive(Debug, Clone, Copy)]
 298 pub struct RegionVariableInfo {
 299     pub origin: RegionVariableOrigin,
 300     pub universe: ty::UniverseIndex,
 301 }
 302
 303 pub struct RegionSnapshot {
 304     length: usize,
 305     region_snapshot: ut::Snapshot<ut::InPlace<ty::RegionVid>>,
 306     any_unifications: bool,
 307 }
 308
 309 /// When working with skolemized regions, we often wish to find all of
 310 /// the regions that are either reachable from a skolemized region, or
 311 /// which can reach a skolemized region, or both. We call such regions
 312 /// *tained* regions.  This struct allows you to decide what set of
 313 /// tainted regions you want.
 314 #[derive(Debug)]
 315 pub struct TaintDirections {
 316     incoming: bool,
 317     outgoing: bool,
 318 }
 319
 320 impl TaintDirections {
 321     pub fn incoming() -> Self {
 322         TaintDirections {
 323             incoming: true,
 324             outgoing: false,
 325         }
 326     }
 327
 328     pub fn outgoing() -> Self {
 329         TaintDirections {
 330             incoming: false,
 331             outgoing: true,
 332         }
 333     }
 334
 335     pub fn both() -> Self {
 336         TaintDirections {
 337             incoming: true,
 338             outgoing: true,
 339         }
 340     }
 341 }
 342
 343 impl<'tcx> RegionConstraintCollector<'tcx> {
 344     pub fn new() -> RegionConstraintCollector<'tcx> {
 345         RegionConstraintCollector {
 346             var_infos: VarInfos::default(),
 347             data: RegionConstraintData::default(),
 348             lubs: FxHashMap(),
 349             glbs: FxHashMap(),
 350             bound_count: 0,
 351             undo_log: Vec::new(),
 352             unification_table: ut::UnificationTable::new(),
 353             any_unifications: false,
 354         }
 355     }
 356
 357     pub fn num_region_vars(&self) -> usize {
 358         self.var_infos.len()
 359     }
 360
 361     pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> {
 362         &self.data
 363     }
 364
 365     /// Once all the constraints have been gathered, extract out the final data.
 366     ///
 367     /// Not legal during a snapshot.
 368     pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) {
 369         assert!(!self.in_snapshot());
 370         (self.var_infos, self.data)
 371     }
 372
 373     /// Takes (and clears) the current set of constraints. Note that
 374     /// the set of variables remains intact, but all relationships
 375     /// between them are reset.  This is used during NLL checking to
 376     /// grab the set of constraints that arose from a particular
 377     /// operation.
 378     ///
 379     /// We don't want to leak relationships between variables between
 380     /// points because just because (say) `r1 == r2` was true at some
 381     /// point P in the graph doesn't imply that it will be true at
 382     /// some other point Q, in NLL.
 383     ///
 384     /// Not legal during a snapshot.
 385     pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> {
 386         assert!(!self.in_snapshot());
 387
 388         // If you add a new field to `RegionConstraintCollector`, you
 389         // should think carefully about whether it needs to be cleared
 390         // or updated in some way.
 391         let RegionConstraintCollector {
 392             var_infos: _,
 393             data,
 394             lubs,
 395             glbs,
 396             bound_count: _,
 397             undo_log: _,
 398             unification_table,
 399             any_unifications,
 400         } = self;
 401
 402         // Clear the tables of (lubs, glbs), so that we will create
 403         // fresh regions if we do a LUB operation. As it happens,
 404         // LUB/GLB are not performed by the MIR type-checker, which is
 405         // the one that uses this method, but it's good to be correct.
 406         lubs.clear();
 407         glbs.clear();
 408
 409         // Clear all unifications and recreate the variables a "now
 410         // un-unified" state. Note that when we unify `a` and `b`, we
 411         // also insert `a <= b` and a `b <= a` edges, so the
 412         // `RegionConstraintData` contains the relationship here.
 413         if *any_unifications {
 414             unification_table.reset_unifications(|vid| unify_key::RegionVidKey { min_vid: vid });
 415             *any_unifications = false;
 416         }
 417
 418         mem::replace(data, RegionConstraintData::default())
 419     }
 420
 421     pub fn data(&self) -> &RegionConstraintData<'tcx> {
 422         &self.data
 423     }
 424
 425     fn in_snapshot(&self) -> bool {
 426         !self.undo_log.is_empty()
 427     }
 428
 429     pub fn start_snapshot(&mut self) -> RegionSnapshot {
 430         let length = self.undo_log.len();
 431         debug!("RegionConstraintCollector: start_snapshot({})", length);
 432         self.undo_log.push(OpenSnapshot);
 433         RegionSnapshot {
 434             length,
 435             region_snapshot: self.unification_table.snapshot(),
 436             any_unifications: self.any_unifications,
 437         }
 438     }
 439
 440     pub fn commit(&mut self, snapshot: RegionSnapshot) {
 441         debug!("RegionConstraintCollector: commit({})", snapshot.length);
 442         assert!(self.undo_log.len() > snapshot.length);
 443         assert!(self.undo_log[snapshot.length] == OpenSnapshot);
 444
 445         if snapshot.length == 0 {
 446             self.undo_log.truncate(0);
 447         } else {
 448             (*self.undo_log)[snapshot.length] = CommitedSnapshot;
 449         }
 450         self.unification_table.commit(snapshot.region_snapshot);
 451     }
 452
 453     pub fn rollback_to(&mut self, snapshot: RegionSnapshot) {
 454         debug!("RegionConstraintCollector: rollback_to({:?})", snapshot);
 455         assert!(self.undo_log.len() > snapshot.length);
 456         assert!(self.undo_log[snapshot.length] == OpenSnapshot);
 457         while self.undo_log.len() > snapshot.length + 1 {
 458             let undo_entry = self.undo_log.pop().unwrap();
 459             self.rollback_undo_entry(undo_entry);
 460         }
 461         let c = self.undo_log.pop().unwrap();
 462         assert!(c == OpenSnapshot);
 463         self.unification_table.rollback_to(snapshot.region_snapshot);
 464         self.any_unifications = snapshot.any_unifications;
 465     }
 466
 467     fn rollback_undo_entry(&mut self, undo_entry: UndoLogEntry<'tcx>) {
 468         match undo_entry {
 469             OpenSnapshot => {
 470                 panic!("Failure to observe stack discipline");
 471             }
 472             Purged | CommitedSnapshot => {
 473                 // nothing to do here
 474             }
 475             AddVar(vid) => {
 476                 self.var_infos.pop().unwrap();
 477                 assert_eq!(self.var_infos.len(), vid.index() as usize);
 478             }
 479             AddConstraint(ref constraint) => {
 480                 self.data.constraints.remove(constraint);
 481             }
 482             AddVerify(index) => {
 483                 self.data.verifys.pop();
 484                 assert_eq!(self.data.verifys.len(), index);
 485             }
 486             AddGiven(sub, sup) => {
 487                 self.data.givens.remove(&(sub, sup));
 488             }
 489             AddCombination(Glb, ref regions) => {
 490                 self.glbs.remove(regions);
 491             }
 492             AddCombination(Lub, ref regions) => {
 493                 self.lubs.remove(regions);
 494             }
 495         }
 496     }
 497
 498     pub fn new_region_var(&mut self,
 499                           universe: ty::UniverseIndex,
 500                           origin: RegionVariableOrigin) -> RegionVid {
 501         let vid = self.var_infos.push(RegionVariableInfo {
 502             origin,
 503             universe,
 504         });
 505
 506         let u_vid = self.unification_table
 507             .new_key(unify_key::RegionVidKey { min_vid: vid });
 508         assert_eq!(vid, u_vid);
 509         if self.in_snapshot() {
 510             self.undo_log.push(AddVar(vid));
 511         }
 512         debug!(
 513             "created new region variable {:?} with origin {:?}",
 514             vid,
 515             origin
 516         );
 517         return vid;
 518     }
 519
 520     /// Returns the universe for the given variable.
 521     pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex {
 522         self.var_infos[vid].universe
 523     }
 524
 525     /// Returns the origin for the given variable.
 526     pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin {
 527         self.var_infos[vid].origin
 528     }
 529
 530     /// Removes all the edges to/from the skolemized regions that are
 531     /// in `skols`. This is used after a higher-ranked operation
 532     /// completes to remove all trace of the skolemized regions
 533     /// created in that time.
 534     pub fn pop_skolemized(
 535         &mut self,
 536         skolemization_count: ty::UniverseIndex,
 537         skols: &FxHashSet<ty::Region<'tcx>>,
 538         snapshot: &RegionSnapshot,
 539     ) {
 540         debug!("pop_skolemized_regions(skols={:?})", skols);
 541
 542         assert!(self.in_snapshot());
 543         assert!(self.undo_log[snapshot.length] == OpenSnapshot);
 544         assert!(
 545             skolemization_count.as_usize() >= skols.len(),
 546             "popping more skolemized variables than actually exist, \
 547              sc now = {:?}, skols.len = {:?}",
 548             skolemization_count,
 549             skols.len()
 550         );
 551
 552         let last_to_pop = skolemization_count.subuniverse();
 553         let first_to_pop = ty::UniverseIndex::from(last_to_pop.as_u32() - skols.len() as u32);
 554
 555         debug_assert! {
 556             skols.iter()
 557                  .all(|&k| match *k {
 558                      ty::ReSkolemized(universe, _) =>
 559                          universe >= first_to_pop &&
 560                          universe < last_to_pop,
 561                      _ =>
 562                          false
 563                  }),
 564             "invalid skolemization keys or keys out of range ({:?}..{:?}): {:?}",
 565             first_to_pop,
 566             last_to_pop,
 567             skols
 568         }
 569
 570         let constraints_to_kill: Vec<usize> = self.undo_log
 571             .iter()
 572             .enumerate()
 573             .rev()
 574             .filter(|&(_, undo_entry)| kill_constraint(skols, undo_entry))
 575             .map(|(index, _)| index)
 576             .collect();
 577
 578         for index in constraints_to_kill {
 579             let undo_entry = mem::replace(&mut self.undo_log[index], Purged);
 580             self.rollback_undo_entry(undo_entry);
 581         }
 582
 583         return;
 584
 585         fn kill_constraint<'tcx>(
 586             skols: &FxHashSet<ty::Region<'tcx>>,
 587             undo_entry: &UndoLogEntry<'tcx>,
 588         ) -> bool {
 589             match undo_entry {
 590                 &AddConstraint(Constraint::VarSubVar(..)) => false,
 591                 &AddConstraint(Constraint::RegSubVar(a, _)) => skols.contains(&a),
 592                 &AddConstraint(Constraint::VarSubReg(_, b)) => skols.contains(&b),
 593                 &AddConstraint(Constraint::RegSubReg(a, b)) => {
 594                     skols.contains(&a) || skols.contains(&b)
 595                 }
 596                 &AddGiven(..) => false,
 597                 &AddVerify(_) => false,
 598                 &AddCombination(_, ref two_regions) => {
 599                     skols.contains(&two_regions.a) || skols.contains(&two_regions.b)
 600                 }
 601                 &AddVar(..) | &OpenSnapshot | &Purged | &CommitedSnapshot => false,
 602             }
 603         }
 604     }
 605
 606     pub fn new_bound(
 607         &mut self,
 608         tcx: TyCtxt<'_, '_, 'tcx>,
 609         debruijn: ty::DebruijnIndex,
 610     ) -> Region<'tcx> {
 611         // Creates a fresh bound variable for use in GLB computations.
 612         // See discussion of GLB computation in the large comment at
 613         // the top of this file for more details.
 614         //
 615         // This computation is potentially wrong in the face of
 616         // rollover.  It's conceivable, if unlikely, that one might
 617         // wind up with accidental capture for nested functions in
 618         // that case, if the outer function had bound regions created
 619         // a very long time before and the inner function somehow
 620         // wound up rolling over such that supposedly fresh
 621         // identifiers were in fact shadowed. For now, we just assert
 622         // that there is no rollover -- eventually we should try to be
 623         // robust against this possibility, either by checking the set
 624         // of bound identifiers that appear in a given expression and
 625         // ensure that we generate one that is distinct, or by
 626         // changing the representation of bound regions in a fn
 627         // declaration
 628
 629         let sc = self.bound_count;
 630         self.bound_count = sc + 1;
 631
 632         if sc >= self.bound_count {
 633             bug!("rollover in RegionInference new_bound()");
 634         }
 635
 636         tcx.mk_region(ReLateBound(debruijn, BrFresh(sc)))
 637     }
 638
 639     fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) {
 640         // cannot add constraints once regions are resolved
 641         debug!(
 642             "RegionConstraintCollector: add_constraint({:?})",
 643             constraint
 644         );
 645
 646         // never overwrite an existing (constraint, origin) - only insert one if it isn't
 647         // present in the map yet. This prevents origins from outside the snapshot being
 648         // replaced with "less informative" origins e.g. during calls to `can_eq`
 649         let in_snapshot = self.in_snapshot();
 650         let undo_log = &mut self.undo_log;
 651         self.data.constraints.entry(constraint).or_insert_with(|| {
 652             if in_snapshot {
 653                 undo_log.push(AddConstraint(constraint));
 654             }
 655             origin
 656         });
 657     }
 658
 659     fn add_verify(&mut self, verify: Verify<'tcx>) {
 660         // cannot add verifys once regions are resolved
 661         debug!("RegionConstraintCollector: add_verify({:?})", verify);
 662
 663         // skip no-op cases known to be satisfied
 664         match verify.bound {
 665             VerifyBound::AllBounds(ref bs) if bs.len() == 0 => {
 666                 return;
 667             }
 668             _ => {}
 669         }
 670
 671         let index = self.data.verifys.len();
 672         self.data.verifys.push(verify);
 673         if self.in_snapshot() {
 674             self.undo_log.push(AddVerify(index));
 675         }
 676     }
 677
 678     pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) {
 679         // cannot add givens once regions are resolved
 680         if self.data.givens.insert((sub, sup)) {
 681             debug!("add_given({:?} <= {:?})", sub, sup);
 682
 683             if self.in_snapshot() {
 684                 self.undo_log.push(AddGiven(sub, sup));
 685             }
 686         }
 687     }
 688
 689     pub fn make_eqregion(
 690         &mut self,
 691         origin: SubregionOrigin<'tcx>,
 692         sub: Region<'tcx>,
 693         sup: Region<'tcx>,
 694     ) {
 695         if sub != sup {
 696             // Eventually, it would be nice to add direct support for
 697             // equating regions.
 698             self.make_subregion(origin.clone(), sub, sup);
 699             self.make_subregion(origin, sup, sub);
 700
 701             if let (ty::ReVar(sub), ty::ReVar(sup)) = (*sub, *sup) {
 702                 self.unification_table.union(sub, sup);
 703                 self.any_unifications = true;
 704             }
 705         }
 706     }
 707
 708     pub fn make_subregion(
 709         &mut self,
 710         origin: SubregionOrigin<'tcx>,
 711         sub: Region<'tcx>,
 712         sup: Region<'tcx>,
 713     ) {
 714         // cannot add constraints once regions are resolved
 715         debug!(
 716             "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}",
 717             sub,
 718             sup,
 719             origin
 720         );
 721
 722         match (sub, sup) {
 723             (&ReLateBound(..), _) | (_, &ReLateBound(..)) => {
 724                 span_bug!(
 725                     origin.span(),
 726                     "cannot relate bound region: {:?} <= {:?}",
 727                     sub,
 728                     sup
 729                 );
 730             }
 731             (_, &ReStatic) => {
 732                 // all regions are subregions of static, so we can ignore this
 733             }
 734             (&ReVar(sub_id), &ReVar(sup_id)) => {
 735                 self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin);
 736             }
 737             (_, &ReVar(sup_id)) => {
 738                 self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin);
 739             }
 740             (&ReVar(sub_id), _) => {
 741                 self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin);
 742             }
 743             _ => {
 744                 self.add_constraint(Constraint::RegSubReg(sub, sup), origin);
 745             }
 746         }
 747     }
 748
 749     /// See `Verify::VerifyGenericBound`
 750     pub fn verify_generic_bound(
 751         &mut self,
 752         origin: SubregionOrigin<'tcx>,
 753         kind: GenericKind<'tcx>,
 754         sub: Region<'tcx>,
 755         bound: VerifyBound<'tcx>,
 756     ) {
 757         self.add_verify(Verify {
 758             kind,
 759             origin,
 760             region: sub,
 761             bound,
 762         });
 763     }
 764
 765     pub fn lub_regions(
 766         &mut self,
 767         tcx: TyCtxt<'_, '_, 'tcx>,
 768         origin: SubregionOrigin<'tcx>,
 769         a: Region<'tcx>,
 770         b: Region<'tcx>,
 771     ) -> Region<'tcx> {
 772         // cannot add constraints once regions are resolved
 773         debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b);
 774         match (a, b) {
 775             (r @ &ReStatic, _) | (_, r @ &ReStatic) => {
 776                 r // nothing lives longer than static
 777             }
 778
 779             _ if a == b => {
 780                 a // LUB(a,a) = a
 781             }
 782
 783             _ => self.combine_vars(tcx, Lub, a, b, origin.clone()),
 784         }
 785     }
 786
 787     pub fn glb_regions(
 788         &mut self,
 789         tcx: TyCtxt<'_, '_, 'tcx>,
 790         origin: SubregionOrigin<'tcx>,
 791         a: Region<'tcx>,
 792         b: Region<'tcx>,
 793     ) -> Region<'tcx> {
 794         // cannot add constraints once regions are resolved
 795         debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b);
 796         match (a, b) {
 797             (&ReStatic, r) | (r, &ReStatic) => {
 798                 r // static lives longer than everything else
 799             }
 800
 801             _ if a == b => {
 802                 a // GLB(a,a) = a
 803             }
 804
 805             _ => self.combine_vars(tcx, Glb, a, b, origin.clone()),
 806         }
 807     }
 808
 809     pub fn opportunistic_resolve_var(
 810         &mut self,
 811         tcx: TyCtxt<'_, '_, 'tcx>,
 812         rid: RegionVid,
 813     ) -> ty::Region<'tcx> {
 814         let vid = self.unification_table.probe_value(rid).min_vid;
 815         tcx.mk_region(ty::ReVar(vid))
 816     }
 817
 818     fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> {
 819         match t {
 820             Glb => &mut self.glbs,
 821             Lub => &mut self.lubs,
 822         }
 823     }
 824
 825     fn combine_vars(
 826         &mut self,
 827         tcx: TyCtxt<'_, '_, 'tcx>,
 828         t: CombineMapType,
 829         a: Region<'tcx>,
 830         b: Region<'tcx>,
 831         origin: SubregionOrigin<'tcx>,
 832     ) -> Region<'tcx> {
 833         let vars = TwoRegions { a: a, b: b };
 834         if let Some(&c) = self.combine_map(t).get(&vars) {
 835             return tcx.mk_region(ReVar(c));
 836         }
 837         let a_universe = self.universe(a);
 838         let b_universe = self.universe(b);
 839         let c_universe = cmp::max(a_universe, b_universe);
 840         let c = self.new_region_var(c_universe, MiscVariable(origin.span()));
 841         self.combine_map(t).insert(vars, c);
 842         if self.in_snapshot() {
 843             self.undo_log.push(AddCombination(t, vars));
 844         }
 845         let new_r = tcx.mk_region(ReVar(c));
 846         for &old_r in &[a, b] {
 847             match t {
 848                 Glb => self.make_subregion(origin.clone(), new_r, old_r),
 849                 Lub => self.make_subregion(origin.clone(), old_r, new_r),
 850             }
 851         }
 852         debug!("combine_vars() c={:?}", c);
 853         new_r
 854     }
 855
 856     fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex {
 857         match *region {
 858             ty::ReScope(..) |
 859             ty::ReStatic |
 860             ty::ReEmpty |
 861             ty::ReErased |
 862             ty::ReFree(..) |
 863             ty::ReEarlyBound(..) => ty::UniverseIndex::ROOT,
 864             ty::ReSkolemized(universe, _) => universe,
 865             ty::ReClosureBound(vid) |
 866             ty::ReVar(vid) => self.var_universe(vid),
 867             ty::ReLateBound(..) =>
 868                 bug!("universe(): encountered bound region {:?}", region),
 869             ty::ReCanonical(..) =>
 870                 bug!("region_universe(): encountered canonical region {:?}", region),
 871         }
 872     }
 873
 874     pub fn vars_created_since_snapshot(&self, mark: &RegionSnapshot) -> Vec<RegionVid> {
 875         self.undo_log[mark.length..]
 876             .iter()
 877             .filter_map(|&elt| match elt {
 878                 AddVar(vid) => Some(vid),
 879                 _ => None,
 880             })
 881             .collect()
 882     }
 883
 884     /// Computes all regions that have been related to `r0` since the
 885     /// mark `mark` was made---`r0` itself will be the first
 886     /// entry. The `directions` parameter controls what kind of
 887     /// relations are considered. For example, one can say that only
 888     /// "incoming" edges to `r0` are desired, in which case one will
 889     /// get the set of regions `{r|r <= r0}`. This is used when
 890     /// checking whether skolemized regions are being improperly
 891     /// related to other regions.
 892     pub fn tainted(
 893         &self,
 894         tcx: TyCtxt<'_, '_, 'tcx>,
 895         mark: &RegionSnapshot,
 896         r0: Region<'tcx>,
 897         directions: TaintDirections,
 898     ) -> FxHashSet<ty::Region<'tcx>> {
 899         debug!(
 900             "tainted(mark={:?}, r0={:?}, directions={:?})",
 901             mark,
 902             r0,
 903             directions
 904         );
 905
 906         // `result_set` acts as a worklist: we explore all outgoing
 907         // edges and add any new regions we find to result_set.  This
 908         // is not a terribly efficient implementation.
 909         let mut taint_set = taint::TaintSet::new(directions, r0);
 910         taint_set.fixed_point(tcx, &self.undo_log[mark.length..], &self.data.verifys);
 911         debug!("tainted: result={:?}", taint_set);
 912         return taint_set.into_set();
 913     }
 914 }
 915
 916 impl fmt::Debug for RegionSnapshot {
 917     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 918         write!(f, "RegionSnapshot(length={})", self.length)
 919     }
 920 }
 921
 922 impl<'tcx> fmt::Debug for GenericKind<'tcx> {
 923     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 924         match *self {
 925             GenericKind::Param(ref p) => write!(f, "{:?}", p),
 926             GenericKind::Projection(ref p) => write!(f, "{:?}", p),
 927         }
 928     }
 929 }
 930
 931 impl<'tcx> fmt::Display for GenericKind<'tcx> {
 932     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 933         match *self {
 934             GenericKind::Param(ref p) => write!(f, "{}", p),
 935             GenericKind::Projection(ref p) => write!(f, "{}", p),
 936         }
 937     }
 938 }
 939
 940 impl<'a, 'gcx, 'tcx> GenericKind<'tcx> {
 941     pub fn to_ty(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Ty<'tcx> {
 942         match *self {
 943             GenericKind::Param(ref p) => p.to_ty(tcx),
 944             GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs),
 945         }
 946     }
 947 }
 948
 949 impl<'a, 'gcx, 'tcx> VerifyBound<'tcx> {
 950     pub fn must_hold(&self) -> bool {
 951         match self {
 952             VerifyBound::IfEq(..) => false,
 953             VerifyBound::OutlivedBy(ty::ReStatic) => true,
 954             VerifyBound::OutlivedBy(_) => false,
 955             VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()),
 956             VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()),
 957         }
 958     }
 959
 960     pub fn cannot_hold(&self) -> bool {
 961         match self {
 962             VerifyBound::IfEq(_, b) => b.cannot_hold(),
 963             VerifyBound::OutlivedBy(ty::ReEmpty) => true,
 964             VerifyBound::OutlivedBy(_) => false,
 965             VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()),
 966             VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()),
 967         }
 968     }
 969
 970     pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
 971         if self.must_hold() || vb.cannot_hold() {
 972             self
 973         } else if self.cannot_hold() || vb.must_hold() {
 974             vb
 975         } else {
 976             VerifyBound::AnyBound(vec![self, vb])
 977         }
 978     }
 979
 980     pub fn and(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
 981         if self.must_hold() && vb.must_hold() {
 982             self
 983         } else if self.cannot_hold() && vb.cannot_hold() {
 984             self
 985         } else {
 986             VerifyBound::AllBounds(vec![self, vb])
 987         }
 988     }
 989 }
 990
 991 impl<'tcx> RegionConstraintData<'tcx> {
 992     /// True if this region constraint data contains no constraints.
 993     pub fn is_empty(&self) -> bool {
 994         let RegionConstraintData {
 995             constraints,
 996             verifys,
 997             givens,
 998         } = self;
 999         constraints.is_empty() && verifys.is_empty() && givens.is_empty()
1000     }
1001 }