src/librustc_infer/infer/region_constraints/mod.rs

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