src/librustc/infer/region_constraints/mod.rs

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