compiler/rustc_infer/src/infer/region_constraints/mod.rs

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