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