src/librustc/infer/region_constraints/mod.rs

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