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