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