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