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