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::sync::Lrc;
  12 use rustc_data_structures::undo_log::UndoLogs;
  13 use rustc_data_structures::unify as ut;
  14 use rustc_hir::def_id::DefId;
  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(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 constriant, 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 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 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: FxHashSet<(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)]
 168 pub enum GenericKind<'tcx> {
 169     Param(ty::ParamTy),
 170     Projection(ty::ProjectionTy<'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 ///
 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 ///
 185 ///     fn(min: Region) -> bool {
 186 ///        ('a: min) || ('b: min)
 187 ///     }
 188 ///
 189 /// This is described with a `AnyRegion('a, 'b)` node.
 190 #[derive(Debug, Clone)]
 191 pub enum VerifyBound<'tcx> {
 192     /// Given a kind K and a bound B, expands to a function like the
 193     /// following, where `G` is the generic for which this verify
 194     /// bound was created:
 195     ///
 196     /// ```rust
 197     /// fn(min) -> bool {
 198     ///     if G == K {
 199     ///         B(min)
 200     ///     } else {
 201     ///         false
 202     ///     }
 203     /// }
 204     /// ```
 205     ///
 206     /// In other words, if the generic `G` that we are checking is
 207     /// equal to `K`, then check the associated verify bound
 208     /// (otherwise, false).
 209     ///
 210     /// This is used when we have something in the environment that
 211     /// may or may not be relevant, depending on the region inference
 212     /// results. For example, we may have `where <T as
 213     /// Trait<'a>>::Item: 'b` in our where-clauses. If we are
 214     /// generating the verify-bound for `<T as Trait<'0>>::Item`, then
 215     /// this where-clause is only relevant if `'0` winds up inferred
 216     /// to `'a`.
 217     ///
 218     /// So we would compile to a verify-bound like
 219     ///
 220     /// ```
 221     /// IfEq(<T as Trait<'a>>::Item, AnyRegion('a))
 222     /// ```
 223     ///
 224     /// meaning, if the subject G is equal to `<T as Trait<'a>>::Item`
 225     /// (after inference), and `'a: min`, then `G: min`.
 226     IfEq(Ty<'tcx>, Box<VerifyBound<'tcx>>),
 227
 228     /// Given a region `R`, expands to the function:
 229     ///
 230     /// ```
 231     /// fn(min) -> bool {
 232     ///     R: min
 233     /// }
 234     /// ```
 235     ///
 236     /// This is used when we can establish that `G: R` -- therefore,
 237     /// if `R: min`, then by transitivity `G: min`.
 238     OutlivedBy(Region<'tcx>),
 239
 240     /// Given a region `R`, true if it is `'empty`.
 241     IsEmpty,
 242
 243     /// Given a set of bounds `B`, expands to the function:
 244     ///
 245     /// ```rust
 246     /// fn(min) -> bool {
 247     ///     exists (b in B) { b(min) }
 248     /// }
 249     /// ```
 250     ///
 251     /// In other words, if we meet some bound in `B`, that suffices.
 252     /// This is used when all the bounds in `B` are known to apply to `G`.
 253     AnyBound(Vec<VerifyBound<'tcx>>),
 254
 255     /// Given a set of bounds `B`, expands to the function:
 256     ///
 257     /// ```rust
 258     /// fn(min) -> bool {
 259     ///     forall (b in B) { b(min) }
 260     /// }
 261     /// ```
 262     ///
 263     /// In other words, if we meet *all* bounds in `B`, that suffices.
 264     /// This is used when *some* bound in `B` is known to suffice, but
 265     /// we don't know which.
 266     AllBounds(Vec<VerifyBound<'tcx>>),
 267 }
 268
 269 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 270 pub(crate) struct TwoRegions<'tcx> {
 271     a: Region<'tcx>,
 272     b: Region<'tcx>,
 273 }
 274
 275 #[derive(Copy, Clone, PartialEq)]
 276 pub(crate) enum UndoLog<'tcx> {
 277     /// We added `RegionVid`.
 278     AddVar(RegionVid),
 279
 280     /// We added the given `constraint`.
 281     AddConstraint(Constraint<'tcx>),
 282
 283     /// We added the given `verify`.
 284     AddVerify(usize),
 285
 286     /// We added the given `given`.
 287     AddGiven(Region<'tcx>, ty::RegionVid),
 288
 289     /// We added a GLB/LUB "combination variable".
 290     AddCombination(CombineMapType, TwoRegions<'tcx>),
 291 }
 292
 293 #[derive(Copy, Clone, PartialEq)]
 294 pub(crate) enum CombineMapType {
 295     Lub,
 296     Glb,
 297 }
 298
 299 type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>;
 300
 301 #[derive(Debug, Clone, Copy)]
 302 pub struct RegionVariableInfo {
 303     pub origin: RegionVariableOrigin,
 304     pub universe: ty::UniverseIndex,
 305 }
 306
 307 pub struct RegionSnapshot {
 308     any_unifications: bool,
 309 }
 310
 311 impl<'tcx> RegionConstraintStorage<'tcx> {
 312     pub fn new() -> Self {
 313         Self::default()
 314     }
 315
 316     #[inline]
 317     pub(crate) fn with_log<'a>(
 318         &'a mut self,
 319         undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
 320     ) -> RegionConstraintCollector<'a, 'tcx> {
 321         RegionConstraintCollector { storage: self, undo_log }
 322     }
 323
 324     fn rollback_undo_entry(&mut self, undo_entry: UndoLog<'tcx>) {
 325         match undo_entry {
 326             AddVar(vid) => {
 327                 self.var_infos.pop().unwrap();
 328                 assert_eq!(self.var_infos.len(), vid.index() as usize);
 329             }
 330             AddConstraint(ref constraint) => {
 331                 self.data.constraints.remove(constraint);
 332             }
 333             AddVerify(index) => {
 334                 self.data.verifys.pop();
 335                 assert_eq!(self.data.verifys.len(), index);
 336             }
 337             AddGiven(sub, sup) => {
 338                 self.data.givens.remove(&(sub, sup));
 339             }
 340             AddCombination(Glb, ref regions) => {
 341                 self.glbs.remove(regions);
 342             }
 343             AddCombination(Lub, ref regions) => {
 344                 self.lubs.remove(regions);
 345             }
 346         }
 347     }
 348 }
 349
 350 impl<'tcx> RegionConstraintCollector<'_, 'tcx> {
 351     pub fn num_region_vars(&self) -> usize {
 352         self.var_infos.len()
 353     }
 354
 355     pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> {
 356         &self.data
 357     }
 358
 359     /// Once all the constraints have been gathered, extract out the final data.
 360     ///
 361     /// Not legal during a snapshot.
 362     pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) {
 363         assert!(!UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log));
 364         (mem::take(&mut self.storage.var_infos), mem::take(&mut self.storage.data))
 365     }
 366
 367     /// Takes (and clears) the current set of constraints. Note that
 368     /// the set of variables remains intact, but all relationships
 369     /// between them are reset. This is used during NLL checking to
 370     /// grab the set of constraints that arose from a particular
 371     /// operation.
 372     ///
 373     /// We don't want to leak relationships between variables between
 374     /// points because just because (say) `r1 == r2` was true at some
 375     /// point P in the graph doesn't imply that it will be true at
 376     /// some other point Q, in NLL.
 377     ///
 378     /// Not legal during a snapshot.
 379     pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> {
 380         assert!(!UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log));
 381
 382         // If you add a new field to `RegionConstraintCollector`, you
 383         // should think carefully about whether it needs to be cleared
 384         // or updated in some way.
 385         let RegionConstraintStorage {
 386             var_infos: _,
 387             data,
 388             lubs,
 389             glbs,
 390             unification_table: _,
 391             any_unifications,
 392         } = self.storage;
 393
 394         // Clear the tables of (lubs, glbs), so that we will create
 395         // fresh regions if we do a LUB operation. As it happens,
 396         // LUB/GLB are not performed by the MIR type-checker, which is
 397         // the one that uses this method, but it's good to be correct.
 398         lubs.clear();
 399         glbs.clear();
 400
 401         let data = mem::take(data);
 402
 403         // Clear all unifications and recreate the variables a "now
 404         // un-unified" state. Note that when we unify `a` and `b`, we
 405         // also insert `a <= b` and a `b <= a` edges, so the
 406         // `RegionConstraintData` contains the relationship here.
 407         if *any_unifications {
 408             *any_unifications = false;
 409             self.unification_table().reset_unifications(|_| UnifiedRegion(None));
 410         }
 411
 412         data
 413     }
 414
 415     pub fn data(&self) -> &RegionConstraintData<'tcx> {
 416         &self.data
 417     }
 418
 419     pub fn start_snapshot(&mut self) -> RegionSnapshot {
 420         debug!("RegionConstraintCollector: start_snapshot");
 421         RegionSnapshot { any_unifications: self.any_unifications }
 422     }
 423
 424     pub fn rollback_to(&mut self, snapshot: RegionSnapshot) {
 425         debug!("RegionConstraintCollector: rollback_to({:?})", snapshot);
 426         self.any_unifications = snapshot.any_unifications;
 427     }
 428
 429     pub fn new_region_var(
 430         &mut self,
 431         universe: ty::UniverseIndex,
 432         origin: RegionVariableOrigin,
 433     ) -> RegionVid {
 434         let vid = self.var_infos.push(RegionVariableInfo { origin, universe });
 435
 436         let u_vid = self.unification_table().new_key(UnifiedRegion(None));
 437         assert_eq!(vid, u_vid.vid);
 438         self.undo_log.push(AddVar(vid));
 439         debug!("created new region variable {:?} in {:?} with origin {:?}", vid, universe, origin);
 440         vid
 441     }
 442
 443     /// Returns the universe for the given variable.
 444     pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex {
 445         self.var_infos[vid].universe
 446     }
 447
 448     fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) {
 449         // cannot add constraints once regions are resolved
 450         debug!("RegionConstraintCollector: add_constraint({:?})", constraint);
 451
 452         // never overwrite an existing (constraint, origin) - only insert one if it isn't
 453         // present in the map yet. This prevents origins from outside the snapshot being
 454         // replaced with "less informative" origins e.g., during calls to `can_eq`
 455         let undo_log = &mut self.undo_log;
 456         self.storage.data.constraints.entry(constraint).or_insert_with(|| {
 457             undo_log.push(AddConstraint(constraint));
 458             origin
 459         });
 460     }
 461
 462     fn add_verify(&mut self, verify: Verify<'tcx>) {
 463         // cannot add verifys once regions are resolved
 464         debug!("RegionConstraintCollector: add_verify({:?})", verify);
 465
 466         // skip no-op cases known to be satisfied
 467         if let VerifyBound::AllBounds(ref bs) = verify.bound {
 468             if bs.is_empty() {
 469                 return;
 470             }
 471         }
 472
 473         let index = self.data.verifys.len();
 474         self.data.verifys.push(verify);
 475         self.undo_log.push(AddVerify(index));
 476     }
 477
 478     pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) {
 479         // cannot add givens once regions are resolved
 480         if self.data.givens.insert((sub, sup)) {
 481             debug!("add_given({:?} <= {:?})", sub, sup);
 482
 483             self.undo_log.push(AddGiven(sub, sup));
 484         }
 485     }
 486
 487     pub fn make_eqregion(
 488         &mut self,
 489         origin: SubregionOrigin<'tcx>,
 490         sub: Region<'tcx>,
 491         sup: Region<'tcx>,
 492     ) {
 493         if sub != sup {
 494             // Eventually, it would be nice to add direct support for
 495             // equating regions.
 496             self.make_subregion(origin.clone(), sub, sup);
 497             self.make_subregion(origin, sup, sub);
 498
 499             match (sub, sup) {
 500                 (&ty::ReVar(sub), &ty::ReVar(sup)) => {
 501                     debug!("make_eqregion: unifying {:?} with {:?}", sub, sup);
 502                     self.unification_table().union(sub, sup);
 503                     self.any_unifications = true;
 504                 }
 505                 (&ty::ReVar(vid), value) | (value, &ty::ReVar(vid)) => {
 506                     debug!("make_eqregion: unifying {:?} with {:?}", vid, value);
 507                     self.unification_table().union_value(vid, UnifiedRegion(Some(value)));
 508                     self.any_unifications = true;
 509                 }
 510                 (_, _) => {}
 511             }
 512         }
 513     }
 514
 515     pub fn member_constraint(
 516         &mut self,
 517         opaque_type_def_id: DefId,
 518         definition_span: Span,
 519         hidden_ty: Ty<'tcx>,
 520         member_region: ty::Region<'tcx>,
 521         choice_regions: &Lrc<Vec<ty::Region<'tcx>>>,
 522     ) {
 523         debug!("member_constraint({:?} in {:#?})", member_region, choice_regions);
 524
 525         if choice_regions.iter().any(|&r| r == member_region) {
 526             return;
 527         }
 528
 529         self.data.member_constraints.push(MemberConstraint {
 530             opaque_type_def_id,
 531             definition_span,
 532             hidden_ty,
 533             member_region,
 534             choice_regions: choice_regions.clone(),
 535         });
 536     }
 537
 538     pub fn make_subregion(
 539         &mut self,
 540         origin: SubregionOrigin<'tcx>,
 541         sub: Region<'tcx>,
 542         sup: Region<'tcx>,
 543     ) {
 544         // cannot add constraints once regions are resolved
 545         debug!(
 546             "RegionConstraintCollector: make_subregion({:?}, {:?}) due to {:?}",
 547             sub, sup, origin
 548         );
 549
 550         match (sub, sup) {
 551             (&ReLateBound(..), _) | (_, &ReLateBound(..)) => {
 552                 span_bug!(origin.span(), "cannot relate bound region: {:?} <= {:?}", sub, sup);
 553             }
 554             (_, &ReStatic) => {
 555                 // all regions are subregions of static, so we can ignore this
 556             }
 557             (&ReVar(sub_id), &ReVar(sup_id)) => {
 558                 self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin);
 559             }
 560             (_, &ReVar(sup_id)) => {
 561                 self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin);
 562             }
 563             (&ReVar(sub_id), _) => {
 564                 self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin);
 565             }
 566             _ => {
 567                 self.add_constraint(Constraint::RegSubReg(sub, sup), origin);
 568             }
 569         }
 570     }
 571
 572     pub fn verify_generic_bound(
 573         &mut self,
 574         origin: SubregionOrigin<'tcx>,
 575         kind: GenericKind<'tcx>,
 576         sub: Region<'tcx>,
 577         bound: VerifyBound<'tcx>,
 578     ) {
 579         self.add_verify(Verify { kind, origin, region: sub, bound });
 580     }
 581
 582     pub fn lub_regions(
 583         &mut self,
 584         tcx: TyCtxt<'tcx>,
 585         origin: SubregionOrigin<'tcx>,
 586         a: Region<'tcx>,
 587         b: Region<'tcx>,
 588     ) -> Region<'tcx> {
 589         // cannot add constraints once regions are resolved
 590         debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b);
 591         match (a, b) {
 592             (r @ &ReStatic, _) | (_, r @ &ReStatic) => {
 593                 r // nothing lives longer than static
 594             }
 595
 596             _ if a == b => {
 597                 a // LUB(a,a) = a
 598             }
 599
 600             _ => self.combine_vars(tcx, Lub, a, b, origin),
 601         }
 602     }
 603
 604     pub fn glb_regions(
 605         &mut self,
 606         tcx: TyCtxt<'tcx>,
 607         origin: SubregionOrigin<'tcx>,
 608         a: Region<'tcx>,
 609         b: Region<'tcx>,
 610     ) -> Region<'tcx> {
 611         // cannot add constraints once regions are resolved
 612         debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b);
 613         match (a, b) {
 614             (&ReStatic, r) | (r, &ReStatic) => {
 615                 r // static lives longer than everything else
 616             }
 617
 618             _ if a == b => {
 619                 a // GLB(a,a) = a
 620             }
 621
 622             _ => self.combine_vars(tcx, Glb, a, b, origin),
 623         }
 624     }
 625
 626     /// Resolves the passed RegionVid to the root RegionVid in the unification table
 627     pub fn opportunistic_resolve_var(&mut self, rid: ty::RegionVid) -> ty::RegionVid {
 628         self.unification_table().find(rid).vid
 629     }
 630
 631     /// If the Region is a `ReVar`, then resolves it either to the root value in
 632     /// the unification table, if it exists, or to the root `ReVar` in the table.
 633     /// If the Region is not a `ReVar`, just returns the Region itself.
 634     pub fn opportunistic_resolve_region(
 635         &mut self,
 636         tcx: TyCtxt<'tcx>,
 637         region: ty::Region<'tcx>,
 638     ) -> ty::Region<'tcx> {
 639         match region {
 640             ty::ReVar(rid) => {
 641                 let unified_region = self.unification_table().probe_value(*rid);
 642                 unified_region.0.unwrap_or_else(|| {
 643                     let root = self.unification_table().find(*rid).vid;
 644                     tcx.reuse_or_mk_region(region, ty::ReVar(root))
 645                 })
 646             }
 647             _ => region,
 648         }
 649     }
 650
 651     fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> {
 652         match t {
 653             Glb => &mut self.glbs,
 654             Lub => &mut self.lubs,
 655         }
 656     }
 657
 658     fn combine_vars(
 659         &mut self,
 660         tcx: TyCtxt<'tcx>,
 661         t: CombineMapType,
 662         a: Region<'tcx>,
 663         b: Region<'tcx>,
 664         origin: SubregionOrigin<'tcx>,
 665     ) -> Region<'tcx> {
 666         let vars = TwoRegions { a, b };
 667         if let Some(&c) = self.combine_map(t).get(&vars) {
 668             return tcx.mk_region(ReVar(c));
 669         }
 670         let a_universe = self.universe(a);
 671         let b_universe = self.universe(b);
 672         let c_universe = cmp::max(a_universe, b_universe);
 673         let c = self.new_region_var(c_universe, MiscVariable(origin.span()));
 674         self.combine_map(t).insert(vars, c);
 675         self.undo_log.push(AddCombination(t, vars));
 676         let new_r = tcx.mk_region(ReVar(c));
 677         for &old_r in &[a, b] {
 678             match t {
 679                 Glb => self.make_subregion(origin.clone(), new_r, old_r),
 680                 Lub => self.make_subregion(origin.clone(), old_r, new_r),
 681             }
 682         }
 683         debug!("combine_vars() c={:?}", c);
 684         new_r
 685     }
 686
 687     pub fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex {
 688         match *region {
 689             ty::ReStatic | ty::ReErased | ty::ReFree(..) | ty::ReEarlyBound(..) => {
 690                 ty::UniverseIndex::ROOT
 691             }
 692             ty::ReEmpty(ui) => ui,
 693             ty::RePlaceholder(placeholder) => placeholder.universe,
 694             ty::ReVar(vid) => self.var_universe(vid),
 695             ty::ReLateBound(..) => bug!("universe(): encountered bound region {:?}", region),
 696         }
 697     }
 698
 699     pub fn vars_since_snapshot(
 700         &self,
 701         value_count: usize,
 702     ) -> (Range<RegionVid>, Vec<RegionVariableOrigin>) {
 703         let range = RegionVid::from(value_count)..RegionVid::from(self.unification_table.len());
 704         (
 705             range.clone(),
 706             (range.start.index()..range.end.index())
 707                 .map(|index| self.var_infos[ty::RegionVid::from(index)].origin)
 708                 .collect(),
 709         )
 710     }
 711
 712     /// See `InferCtxt::region_constraints_added_in_snapshot`.
 713     pub fn region_constraints_added_in_snapshot(&self, mark: &Snapshot<'tcx>) -> Option<bool> {
 714         self.undo_log
 715             .region_constraints_in_snapshot(mark)
 716             .map(|&elt| match elt {
 717                 AddConstraint(constraint) => Some(constraint.involves_placeholders()),
 718                 _ => None,
 719             })
 720             .max()
 721             .unwrap_or(None)
 722     }
 723
 724     #[inline]
 725     fn unification_table(&mut self) -> super::UnificationTable<'_, 'tcx, RegionVidKey<'tcx>> {
 726         ut::UnificationTable::with_log(&mut self.storage.unification_table, self.undo_log)
 727     }
 728 }
 729
 730 impl fmt::Debug for RegionSnapshot {
 731     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 732         write!(f, "RegionSnapshot")
 733     }
 734 }
 735
 736 impl<'tcx> fmt::Debug for GenericKind<'tcx> {
 737     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 738         match *self {
 739             GenericKind::Param(ref p) => write!(f, "{:?}", p),
 740             GenericKind::Projection(ref p) => write!(f, "{:?}", p),
 741         }
 742     }
 743 }
 744
 745 impl<'tcx> fmt::Display for GenericKind<'tcx> {
 746     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 747         match *self {
 748             GenericKind::Param(ref p) => write!(f, "{}", p),
 749             GenericKind::Projection(ref p) => write!(f, "{}", p),
 750         }
 751     }
 752 }
 753
 754 impl<'tcx> GenericKind<'tcx> {
 755     pub fn to_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
 756         match *self {
 757             GenericKind::Param(ref p) => p.to_ty(tcx),
 758             GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs),
 759         }
 760     }
 761 }
 762
 763 impl<'tcx> VerifyBound<'tcx> {
 764     pub fn must_hold(&self) -> bool {
 765         match self {
 766             VerifyBound::IfEq(..) => false,
 767             VerifyBound::OutlivedBy(ty::ReStatic) => true,
 768             VerifyBound::OutlivedBy(_) => false,
 769             VerifyBound::IsEmpty => false,
 770             VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()),
 771             VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()),
 772         }
 773     }
 774
 775     pub fn cannot_hold(&self) -> bool {
 776         match self {
 777             VerifyBound::IfEq(_, b) => b.cannot_hold(),
 778             VerifyBound::IsEmpty => false,
 779             VerifyBound::OutlivedBy(_) => false,
 780             VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()),
 781             VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()),
 782         }
 783     }
 784
 785     pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
 786         if self.must_hold() || vb.cannot_hold() {
 787             self
 788         } else if self.cannot_hold() || vb.must_hold() {
 789             vb
 790         } else {
 791             VerifyBound::AnyBound(vec![self, vb])
 792         }
 793     }
 794 }
 795
 796 impl<'tcx> RegionConstraintData<'tcx> {
 797     /// Returns `true` if this region constraint data contains no constraints, and `false`
 798     /// otherwise.
 799     pub fn is_empty(&self) -> bool {
 800         let RegionConstraintData { constraints, member_constraints, verifys, givens } = self;
 801         constraints.is_empty()
 802             && member_constraints.is_empty()
 803             && verifys.is_empty()
 804             && givens.is_empty()
 805     }
 806 }
 807
 808 impl<'tcx> Rollback<UndoLog<'tcx>> for RegionConstraintStorage<'tcx> {
 809     fn reverse(&mut self, undo: UndoLog<'tcx>) {
 810         self.rollback_undo_entry(undo)
 811     }
 812 }