Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 1271 insertions, 0 deletions

diff --git a/compiler/rustc_infer/src/infer/region_constraints/README.md b/compiler/rustc_infer/src/infer/region_constraints/README.md
new file mode 100644
index 000000000..0231dd066
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/region_constraints/README.md
@@ -0,0 +1,3 @@
+For info on how the current borrowck works, see the [rustc dev guide].
+
+[rustc dev guide]: https://rustc-dev-guide.rust-lang.org/borrow_check.html
diff --git a/compiler/rustc_infer/src/infer/region_constraints/leak_check.rs b/compiler/rustc_infer/src/infer/region_constraints/leak_check.rs
new file mode 100644
index 000000000..397efe6ee
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/region_constraints/leak_check.rs
@@ -0,0 +1,447 @@
+use super::*;
+use crate::infer::CombinedSnapshot;
+use rustc_data_structures::{
+    graph::{scc::Sccs, vec_graph::VecGraph},
+    undo_log::UndoLogs,
+};
+use rustc_index::vec::Idx;
+use rustc_middle::ty::error::TypeError;
+use rustc_middle::ty::relate::RelateResult;
+
+impl<'tcx> RegionConstraintCollector<'_, 'tcx> {
+    /// Searches new universes created during `snapshot`, looking for
+    /// placeholders that may "leak" out from the universes they are contained
+    /// in. If any leaking placeholders are found, then an `Err` is returned
+    /// (typically leading to the snapshot being reversed).
+    ///
+    /// The leak check *used* to be the only way we had to handle higher-ranked
+    /// obligations. Now that we have integrated universes into the region
+    /// solvers, this is no longer the case, but we retain the leak check for
+    /// backwards compatibility purposes. In particular, it lets us make "early"
+    /// decisions about whether a region error will be reported that are used in
+    /// coherence and elsewhere -- see #56105 and #59490 for more details. The
+    /// eventual fate of the leak checker is not yet settled.
+    ///
+    /// The leak checker works by searching for the following error patterns:
+    ///
+    /// * P1: P2, where P1 != P2
+    /// * P1: R, where R is in some universe that cannot name P1
+    ///
+    /// The idea here is that each of these patterns represents something that
+    /// the region solver would eventually report as an error, so we can detect
+    /// the error early. There is a fly in the ointment, though, in that this is
+    /// not entirely true. In particular, in the future, we may extend the
+    /// environment with implied bounds or other info about how placeholders
+    /// relate to regions in outer universes. In that case, `P1: R` for example
+    /// might become solvable.
+    ///
+    /// # Summary of the implementation
+    ///
+    /// The leak checks as follows. First, we construct a graph where `R2: R1`
+    /// implies `R2 -> R1`, and we compute the SCCs.
+    ///
+    /// For each SCC S, we compute:
+    ///
+    /// * what placeholder P it must be equal to, if any
+    ///   * if there are multiple placeholders that must be equal, report an error because `P1: P2`
+    /// * the minimum universe of its constituents
+    ///
+    /// Then we walk the SCCs in dependency order and compute
+    ///
+    /// * what placeholder they must outlive transitively
+    ///   * if they must also be equal to a placeholder, report an error because `P1: P2`
+    /// * minimum universe U of all SCCs they must outlive
+    ///   * if they must also be equal to a placeholder P, and U cannot name P, report an error, as that
+    ///     indicates `P: R` and `R` is in an incompatible universe
+    ///
+    /// # Historical note
+    ///
+    /// Older variants of the leak check used to report errors for these
+    /// patterns, but we no longer do:
+    ///
+    /// * R: P1, even if R cannot name P1, because R = 'static is a valid sol'n
+    /// * R: P1, R: P2, as above
+    pub fn leak_check(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+        overly_polymorphic: bool,
+        max_universe: ty::UniverseIndex,
+        snapshot: &CombinedSnapshot<'_, 'tcx>,
+    ) -> RelateResult<'tcx, ()> {
+        debug!(
+            "leak_check(max_universe={:?}, snapshot.universe={:?}, overly_polymorphic={:?})",
+            max_universe, snapshot.universe, overly_polymorphic
+        );
+
+        assert!(UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log));
+
+        let universe_at_start_of_snapshot = snapshot.universe;
+        if universe_at_start_of_snapshot == max_universe {
+            return Ok(());
+        }
+
+        let mini_graph =
+            &MiniGraph::new(tcx, self.undo_log.region_constraints(), &self.storage.data.verifys);
+
+        let mut leak_check = LeakCheck::new(
+            tcx,
+            universe_at_start_of_snapshot,
+            max_universe,
+            overly_polymorphic,
+            mini_graph,
+            self,
+        );
+        leak_check.assign_placeholder_values()?;
+        leak_check.propagate_scc_value()?;
+        Ok(())
+    }
+}
+
+struct LeakCheck<'me, 'tcx> {
+    tcx: TyCtxt<'tcx>,
+    universe_at_start_of_snapshot: ty::UniverseIndex,
+    /// Only used when reporting region errors.
+    overly_polymorphic: bool,
+    mini_graph: &'me MiniGraph<'tcx>,
+    rcc: &'me RegionConstraintCollector<'me, 'tcx>,
+
+    // Initially, for each SCC S, stores a placeholder `P` such that `S = P`
+    // must hold.
+    //
+    // Later, during the [`LeakCheck::propagate_scc_value`] function, this array
+    // is repurposed to store some placeholder `P` such that the weaker
+    // condition `S: P` must hold. (This is true if `S: S1` transitively and `S1
+    // = P`.)
+    scc_placeholders: IndexVec<LeakCheckScc, Option<ty::PlaceholderRegion>>,
+
+    // For each SCC S, track the minimum universe that flows into it. Note that
+    // this is both the minimum of the universes for every region that is a
+    // member of the SCC, but also if you have `R1: R2`, then the universe of
+    // `R2` must be less than the universe of `R1` (i.e., `R1` flows `R2`). To
+    // see that, imagine that you have `P1: R` -- in that case, `R` must be
+    // either the placeholder `P1` or the empty region in that same universe.
+    //
+    // To detect errors, we look for an SCC S where the values in
+    // `scc_values[S]` (if any) cannot be stored into `scc_universes[S]`.
+    scc_universes: IndexVec<LeakCheckScc, SccUniverse<'tcx>>,
+}
+
+impl<'me, 'tcx> LeakCheck<'me, 'tcx> {
+    fn new(
+        tcx: TyCtxt<'tcx>,
+        universe_at_start_of_snapshot: ty::UniverseIndex,
+        max_universe: ty::UniverseIndex,
+        overly_polymorphic: bool,
+        mini_graph: &'me MiniGraph<'tcx>,
+        rcc: &'me RegionConstraintCollector<'me, 'tcx>,
+    ) -> Self {
+        let dummy_scc_universe = SccUniverse { universe: max_universe, region: None };
+        Self {
+            tcx,
+            universe_at_start_of_snapshot,
+            overly_polymorphic,
+            mini_graph,
+            rcc,
+            scc_placeholders: IndexVec::from_elem_n(None, mini_graph.sccs.num_sccs()),
+            scc_universes: IndexVec::from_elem_n(dummy_scc_universe, mini_graph.sccs.num_sccs()),
+        }
+    }
+
+    /// Compute what placeholders (if any) each SCC must be equal to.
+    /// Also compute the minimum universe of all the regions in each SCC.
+    fn assign_placeholder_values(&mut self) -> RelateResult<'tcx, ()> {
+        // First walk: find each placeholder that is from a newly created universe.
+        for (region, leak_check_node) in &self.mini_graph.nodes {
+            let scc = self.mini_graph.sccs.scc(*leak_check_node);
+
+            // Set the universe of each SCC to be the minimum of its constituent universes
+            let universe = self.rcc.universe(*region);
+            debug!(
+                "assign_placeholder_values: scc={:?} universe={:?} region={:?}",
+                scc, universe, region
+            );
+            self.scc_universes[scc].take_min(universe, *region);
+
+            // Detect those SCCs that directly contain a placeholder
+            if let ty::RePlaceholder(placeholder) = **region {
+                if self.universe_at_start_of_snapshot.cannot_name(placeholder.universe) {
+                    self.assign_scc_value(scc, placeholder)?;
+                }
+            }
+        }
+
+        Ok(())
+    }
+
+    // assign_scc_value(S, P): Update `scc_values` to account for the fact that `P: S` must hold.
+    // This may create an error.
+    fn assign_scc_value(
+        &mut self,
+        scc: LeakCheckScc,
+        placeholder: ty::PlaceholderRegion,
+    ) -> RelateResult<'tcx, ()> {
+        match self.scc_placeholders[scc] {
+            Some(p) => {
+                assert_ne!(p, placeholder);
+                return Err(self.placeholder_error(p, placeholder));
+            }
+            None => {
+                self.scc_placeholders[scc] = Some(placeholder);
+            }
+        };
+
+        Ok(())
+    }
+
+    /// For each SCC S, iterate over each successor S1 where `S: S1`:
+    ///
+    /// * Compute
+    /// Iterate over each SCC `S` and ensure that, for each `S1` where `S1: S`,
+    /// `universe(S) <= universe(S1)`. This executes after
+    /// `assign_placeholder_values`, so `universe(S)` is already the minimum
+    /// universe of any of its direct constituents.
+    fn propagate_scc_value(&mut self) -> RelateResult<'tcx, ()> {
+        // Loop invariants:
+        //
+        // On start of the loop iteration for `scc1`:
+        //
+        // * `scc_universes[scc1]` contains the minimum universe of the
+        //   constituents of `scc1`
+        // * `scc_placeholder[scc1]` stores the placeholder that `scc1` must
+        //   be equal to (if any)
+        //
+        // For each successor `scc2` where `scc1: scc2`:
+        //
+        // * `scc_placeholder[scc2]` stores some placeholder `P` where
+        //   `scc2: P` (if any)
+        // * `scc_universes[scc2]` contains the minimum universe of the
+        //   constituents of `scc2` and any of its successors
+        for scc1 in self.mini_graph.sccs.all_sccs() {
+            debug!(
+                "propagate_scc_value: scc={:?} with universe {:?}",
+                scc1, self.scc_universes[scc1]
+            );
+
+            // Walk over each `scc2` such that `scc1: scc2` and compute:
+            //
+            // * `scc1_universe`: the minimum universe of `scc2` and the constituents of `scc1`
+            // * `succ_bound`: placeholder `P` that the successors must outlive, if any (if there are multiple,
+            //   we pick one arbitrarily)
+            let mut scc1_universe = self.scc_universes[scc1];
+            let mut succ_bound = None;
+            for &scc2 in self.mini_graph.sccs.successors(scc1) {
+                let SccUniverse { universe: scc2_universe, region: scc2_region } =
+                    self.scc_universes[scc2];
+
+                scc1_universe.take_min(scc2_universe, scc2_region.unwrap());
+
+                if let Some(b) = self.scc_placeholders[scc2] {
+                    succ_bound = Some(b);
+                }
+            }
+
+            // Update minimum universe of scc1.
+            self.scc_universes[scc1] = scc1_universe;
+
+            // At this point, `scc_placeholders[scc1]` stores the placeholder that
+            // `scc1` must be equal to, if any.
+            if let Some(scc1_placeholder) = self.scc_placeholders[scc1] {
+                debug!(
+                    "propagate_scc_value: scc1={:?} placeholder={:?} scc1_universe={:?}",
+                    scc1, scc1_placeholder, scc1_universe
+                );
+
+                // Check if `P1: R` for some `R` in a universe that cannot name
+                // P1. That's an error.
+                if scc1_universe.universe.cannot_name(scc1_placeholder.universe) {
+                    return Err(self.error(scc1_placeholder, scc1_universe.region.unwrap()));
+                }
+
+                // Check if we have some placeholder where `S: P2`
+                // (transitively). In that case, since `S = P1`, that implies
+                // `P1: P2`, which is an error condition.
+                if let Some(scc2_placeholder) = succ_bound {
+                    assert_ne!(scc1_placeholder, scc2_placeholder);
+                    return Err(self.placeholder_error(scc1_placeholder, scc2_placeholder));
+                }
+            } else {
+                // Otherwise, we can reach a placeholder if some successor can.
+                self.scc_placeholders[scc1] = succ_bound;
+            }
+
+            // At this point, `scc_placeholder[scc1]` stores some placeholder that `scc1` must outlive (if any).
+        }
+        Ok(())
+    }
+
+    fn placeholder_error(
+        &self,
+        placeholder1: ty::PlaceholderRegion,
+        placeholder2: ty::PlaceholderRegion,
+    ) -> TypeError<'tcx> {
+        self.error(placeholder1, self.tcx.mk_region(ty::RePlaceholder(placeholder2)))
+    }
+
+    fn error(
+        &self,
+        placeholder: ty::PlaceholderRegion,
+        other_region: ty::Region<'tcx>,
+    ) -> TypeError<'tcx> {
+        debug!("error: placeholder={:?}, other_region={:?}", placeholder, other_region);
+        if self.overly_polymorphic {
+            TypeError::RegionsOverlyPolymorphic(placeholder.name, other_region)
+        } else {
+            TypeError::RegionsInsufficientlyPolymorphic(placeholder.name, other_region)
+        }
+    }
+}
+
+// States we need to distinguish:
+//
+// * must be equal to a placeholder (i.e., a placeholder is in the SCC)
+//     * it could conflict with some other regions in the SCC in different universes
+//     * or a different placeholder
+// * `P1: S` and `S` must be equal to a placeholder
+// * `P1: S` and `S` is in an incompatible universe
+//
+// So if we
+//
+// (a) compute which placeholder (if any) each SCC must be equal to
+// (b) compute its minimum universe
+// (c) compute *some* placeholder where `S: P1` (any one will do)
+//
+// then we get an error if:
+//
+// - it must be equal to a placeholder `P1` and minimum universe cannot name `P1`
+// - `S: P1` and minimum universe cannot name `P1`
+// - `S: P1` and we must be equal to `P2`
+//
+// So we want to track:
+//
+// * Equal placeholder (if any)
+// * Some bounding placeholder (if any)
+// * Minimum universe
+//
+// * We compute equal placeholder + minimum universe of constituents in first pass
+// * Then we walk in order and compute from our dependencies `S1` where `S: S1` (`S -> S1`)
+//   * bounding placeholder (if any)
+//   * minimum universe
+// * And if we must be equal to a placeholder then we check it against
+//   * minimum universe
+//   * no bounding placeholder
+
+/// Tracks the "minimum universe" for each SCC, along with some region that
+/// caused it to change.
+#[derive(Copy, Clone, Debug)]
+struct SccUniverse<'tcx> {
+    /// For some SCC S, the minimum universe of:
+    ///
+    /// * each region R in S
+    /// * each SCC S1 such that S: S1
+    universe: ty::UniverseIndex,
+
+    /// Some region that caused `universe` to be what it is.
+    region: Option<ty::Region<'tcx>>,
+}
+
+impl<'tcx> SccUniverse<'tcx> {
+    /// If `universe` is less than our current universe, then update
+    /// `self.universe` and `self.region`.
+    fn take_min(&mut self, universe: ty::UniverseIndex, region: ty::Region<'tcx>) {
+        if universe < self.universe || self.region.is_none() {
+            self.universe = universe;
+            self.region = Some(region);
+        }
+    }
+}
+
+rustc_index::newtype_index! {
+    struct LeakCheckNode {
+        DEBUG_FORMAT = "LeakCheckNode({})"
+    }
+}
+
+rustc_index::newtype_index! {
+    struct LeakCheckScc {
+        DEBUG_FORMAT = "LeakCheckScc({})"
+    }
+}
+
+/// Represents the graph of constraints. For each `R1: R2` constraint we create
+/// an edge `R1 -> R2` in the graph.
+struct MiniGraph<'tcx> {
+    /// Map from a region to the index of the node in the graph.
+    nodes: FxHashMap<ty::Region<'tcx>, LeakCheckNode>,
+
+    /// Map from node index to SCC, and stores the successors of each SCC. All
+    /// the regions in the same SCC are equal to one another, and if `S1 -> S2`,
+    /// then `S1: S2`.
+    sccs: Sccs<LeakCheckNode, LeakCheckScc>,
+}
+
+impl<'tcx> MiniGraph<'tcx> {
+    fn new<'a>(
+        tcx: TyCtxt<'tcx>,
+        undo_log: impl Iterator<Item = &'a UndoLog<'tcx>>,
+        verifys: &[Verify<'tcx>],
+    ) -> Self
+    where
+        'tcx: 'a,
+    {
+        let mut nodes = FxHashMap::default();
+        let mut edges = Vec::new();
+
+        // Note that if `R2: R1`, we get a callback `r1, r2`, so `target` is first parameter.
+        Self::iterate_undo_log(tcx, undo_log, verifys, |target, source| {
+            let source_node = Self::add_node(&mut nodes, source);
+            let target_node = Self::add_node(&mut nodes, target);
+            edges.push((source_node, target_node));
+        });
+        let graph = VecGraph::new(nodes.len(), edges);
+        let sccs = Sccs::new(&graph);
+        Self { nodes, sccs }
+    }
+
+    /// Invokes `each_edge(R1, R2)` for each edge where `R2: R1`
+    fn iterate_undo_log<'a>(
+        tcx: TyCtxt<'tcx>,
+        undo_log: impl Iterator<Item = &'a UndoLog<'tcx>>,
+        verifys: &[Verify<'tcx>],
+        mut each_edge: impl FnMut(ty::Region<'tcx>, ty::Region<'tcx>),
+    ) where
+        'tcx: 'a,
+    {
+        for undo_entry in undo_log {
+            match undo_entry {
+                &AddConstraint(Constraint::VarSubVar(a, b)) => {
+                    each_edge(tcx.mk_region(ReVar(a)), tcx.mk_region(ReVar(b)));
+                }
+                &AddConstraint(Constraint::RegSubVar(a, b)) => {
+                    each_edge(a, tcx.mk_region(ReVar(b)));
+                }
+                &AddConstraint(Constraint::VarSubReg(a, b)) => {
+                    each_edge(tcx.mk_region(ReVar(a)), b);
+                }
+                &AddConstraint(Constraint::RegSubReg(a, b)) => {
+                    each_edge(a, b);
+                }
+                &AddGiven(a, b) => {
+                    each_edge(a, tcx.mk_region(ReVar(b)));
+                }
+                &AddVerify(i) => span_bug!(
+                    verifys[i].origin.span(),
+                    "we never add verifications while doing higher-ranked things",
+                ),
+                &AddCombination(..) | &AddVar(..) => {}
+            }
+        }
+    }
+
+    fn add_node(
+        nodes: &mut FxHashMap<ty::Region<'tcx>, LeakCheckNode>,
+        r: ty::Region<'tcx>,
+    ) -> LeakCheckNode {
+        let l = nodes.len();
+        *nodes.entry(r).or_insert(LeakCheckNode::new(l))
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/region_constraints/mod.rs b/compiler/rustc_infer/src/infer/region_constraints/mod.rs
new file mode 100644
index 000000000..0d4472a1c
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/region_constraints/mod.rs
@@ -0,0 +1,821 @@
+//! See `README.md`.
+
+use self::CombineMapType::*;
+use self::UndoLog::*;
+
+use super::{
+    InferCtxtUndoLogs, MiscVariable, RegionVariableOrigin, Rollback, Snapshot, SubregionOrigin,
+};
+
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::intern::Interned;
+use rustc_data_structures::sync::Lrc;
+use rustc_data_structures::undo_log::UndoLogs;
+use rustc_data_structures::unify as ut;
+use rustc_index::vec::IndexVec;
+use rustc_middle::infer::unify_key::{RegionVidKey, UnifiedRegion};
+use rustc_middle::ty::ReStatic;
+use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_middle::ty::{ReLateBound, ReVar};
+use rustc_middle::ty::{Region, RegionVid};
+use rustc_span::Span;
+
+use std::collections::BTreeMap;
+use std::ops::Range;
+use std::{cmp, fmt, mem};
+
+mod leak_check;
+
+pub use rustc_middle::infer::MemberConstraint;
+
+#[derive(Clone, Default)]
+pub struct RegionConstraintStorage<'tcx> {
+    /// For each `RegionVid`, the corresponding `RegionVariableOrigin`.
+    var_infos: IndexVec<RegionVid, RegionVariableInfo>,
+
+    data: RegionConstraintData<'tcx>,
+
+    /// For a given pair of regions (R1, R2), maps to a region R3 that
+    /// is designated as their LUB (edges R1 <= R3 and R2 <= R3
+    /// exist). This prevents us from making many such regions.
+    lubs: CombineMap<'tcx>,
+
+    /// For a given pair of regions (R1, R2), maps to a region R3 that
+    /// is designated as their GLB (edges R3 <= R1 and R3 <= R2
+    /// exist). This prevents us from making many such regions.
+    glbs: CombineMap<'tcx>,
+
+    /// When we add a R1 == R2 constraint, we currently add (a) edges
+    /// R1 <= R2 and R2 <= R1 and (b) we unify the two regions in this
+    /// table. You can then call `opportunistic_resolve_var` early
+    /// which will map R1 and R2 to some common region (i.e., either
+    /// R1 or R2). This is important when fulfillment, dropck and other such
+    /// code is iterating to a fixed point, because otherwise we sometimes
+    /// would wind up with a fresh stream of region variables that have been
+    /// equated but appear distinct.
+    pub(super) unification_table: ut::UnificationTableStorage<RegionVidKey<'tcx>>,
+
+    /// a flag set to true when we perform any unifications; this is used
+    /// to micro-optimize `take_and_reset_data`
+    any_unifications: bool,
+}
+
+pub struct RegionConstraintCollector<'a, 'tcx> {
+    storage: &'a mut RegionConstraintStorage<'tcx>,
+    undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
+}
+
+impl<'tcx> std::ops::Deref for RegionConstraintCollector<'_, 'tcx> {
+    type Target = RegionConstraintStorage<'tcx>;
+    #[inline]
+    fn deref(&self) -> &RegionConstraintStorage<'tcx> {
+        self.storage
+    }
+}
+
+impl<'tcx> std::ops::DerefMut for RegionConstraintCollector<'_, 'tcx> {
+    #[inline]
+    fn deref_mut(&mut self) -> &mut RegionConstraintStorage<'tcx> {
+        self.storage
+    }
+}
+
+pub type VarInfos = IndexVec<RegionVid, RegionVariableInfo>;
+
+/// The full set of region constraints gathered up by the collector.
+/// Describes constraints between the region variables and other
+/// regions, as well as other conditions that must be verified, or
+/// assumptions that can be made.
+#[derive(Debug, Default, Clone)]
+pub struct RegionConstraintData<'tcx> {
+    /// Constraints of the form `A <= B`, where either `A` or `B` can
+    /// be a region variable (or neither, as it happens).
+    pub constraints: BTreeMap<Constraint<'tcx>, SubregionOrigin<'tcx>>,
+
+    /// Constraints of the form `R0 member of [R1, ..., Rn]`, meaning that
+    /// `R0` must be equal to one of the regions `R1..Rn`. These occur
+    /// with `impl Trait` quite frequently.
+    pub member_constraints: Vec<MemberConstraint<'tcx>>,
+
+    /// A "verify" is something that we need to verify after inference
+    /// is done, but which does not directly affect inference in any
+    /// way.
+    ///
+    /// An example is a `A <= B` where neither `A` nor `B` are
+    /// inference variables.
+    pub verifys: Vec<Verify<'tcx>>,
+
+    /// A "given" is a relationship that is known to hold. In
+    /// particular, we often know from closure fn signatures that a
+    /// particular free region must be a subregion of a region
+    /// variable:
+    ///
+    ///    foo.iter().filter(<'a> |x: &'a &'b T| ...)
+    ///
+    /// In situations like this, `'b` is in fact a region variable
+    /// introduced by the call to `iter()`, and `'a` is a bound region
+    /// on the closure (as indicated by the `<'a>` prefix). If we are
+    /// naive, we wind up inferring that `'b` must be `'static`,
+    /// because we require that it be greater than `'a` and we do not
+    /// know what `'a` is precisely.
+    ///
+    /// This hashmap is used to avoid that naive scenario. Basically
+    /// we record the fact that `'a <= 'b` is implied by the fn
+    /// signature, and then ignore the constraint when solving
+    /// equations. This is a bit of a hack but seems to work.
+    pub givens: FxHashSet<(Region<'tcx>, ty::RegionVid)>,
+}
+
+/// Represents a constraint that influences the inference process.
+#[derive(Clone, Copy, PartialEq, Eq, Debug, PartialOrd, Ord)]
+pub enum Constraint<'tcx> {
+    /// A region variable is a subregion of another.
+    VarSubVar(RegionVid, RegionVid),
+
+    /// A concrete region is a subregion of region variable.
+    RegSubVar(Region<'tcx>, RegionVid),
+
+    /// A region variable is a subregion of a concrete region. This does not
+    /// directly affect inference, but instead is checked after
+    /// inference is complete.
+    VarSubReg(RegionVid, Region<'tcx>),
+
+    /// A constraint where neither side is a variable. This does not
+    /// directly affect inference, but instead is checked after
+    /// inference is complete.
+    RegSubReg(Region<'tcx>, Region<'tcx>),
+}
+
+impl Constraint<'_> {
+    pub fn involves_placeholders(&self) -> bool {
+        match self {
+            Constraint::VarSubVar(_, _) => false,
+            Constraint::VarSubReg(_, r) | Constraint::RegSubVar(r, _) => r.is_placeholder(),
+            Constraint::RegSubReg(r, s) => r.is_placeholder() || s.is_placeholder(),
+        }
+    }
+}
+
+#[derive(Debug, Clone)]
+pub struct Verify<'tcx> {
+    pub kind: GenericKind<'tcx>,
+    pub origin: SubregionOrigin<'tcx>,
+    pub region: Region<'tcx>,
+    pub bound: VerifyBound<'tcx>,
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)]
+pub enum GenericKind<'tcx> {
+    Param(ty::ParamTy),
+    Projection(ty::ProjectionTy<'tcx>),
+}
+
+/// Describes the things that some `GenericKind` value `G` is known to
+/// outlive. Each variant of `VerifyBound` can be thought of as a
+/// function:
+/// ```ignore (pseudo-rust)
+/// fn(min: Region) -> bool { .. }
+/// ```
+/// where `true` means that the region `min` meets that `G: min`.
+/// (False means nothing.)
+///
+/// So, for example, if we have the type `T` and we have in scope that
+/// `T: 'a` and `T: 'b`, then the verify bound might be:
+/// ```ignore (pseudo-rust)
+/// fn(min: Region) -> bool {
+///    ('a: min) || ('b: min)
+/// }
+/// ```
+/// This is described with an `AnyRegion('a, 'b)` node.
+#[derive(Debug, Clone)]
+pub enum VerifyBound<'tcx> {
+    /// See [`VerifyIfEq`] docs
+    IfEq(ty::Binder<'tcx, VerifyIfEq<'tcx>>),
+
+    /// Given a region `R`, expands to the function:
+    ///
+    /// ```ignore (pseudo-rust)
+    /// fn(min) -> bool {
+    ///     R: min
+    /// }
+    /// ```
+    ///
+    /// This is used when we can establish that `G: R` -- therefore,
+    /// if `R: min`, then by transitivity `G: min`.
+    OutlivedBy(Region<'tcx>),
+
+    /// Given a region `R`, true if it is `'empty`.
+    IsEmpty,
+
+    /// Given a set of bounds `B`, expands to the function:
+    ///
+    /// ```ignore (pseudo-rust)
+    /// fn(min) -> bool {
+    ///     exists (b in B) { b(min) }
+    /// }
+    /// ```
+    ///
+    /// In other words, if we meet some bound in `B`, that suffices.
+    /// This is used when all the bounds in `B` are known to apply to `G`.
+    AnyBound(Vec<VerifyBound<'tcx>>),
+
+    /// Given a set of bounds `B`, expands to the function:
+    ///
+    /// ```ignore (pseudo-rust)
+    /// fn(min) -> bool {
+    ///     forall (b in B) { b(min) }
+    /// }
+    /// ```
+    ///
+    /// In other words, if we meet *all* bounds in `B`, that suffices.
+    /// This is used when *some* bound in `B` is known to suffice, but
+    /// we don't know which.
+    AllBounds(Vec<VerifyBound<'tcx>>),
+}
+
+/// This is a "conditional bound" that checks the result of inference
+/// and supplies a bound if it ended up being relevant. It's used in situations
+/// like this:
+///
+/// ```rust
+/// fn foo<'a, 'b, T: SomeTrait<'a>>
+/// where
+///    <T as SomeTrait<'a>>::Item: 'b
+/// ```
+///
+/// If we have an obligation like `<T as SomeTrait<'?x>>::Item: 'c`, then
+/// we don't know yet whether it suffices to show that `'b: 'c`. If `'?x` winds
+/// up being equal to `'a`, then the where-clauses on function applies, and
+/// in that case we can show `'b: 'c`. But if `'?x` winds up being something
+/// else, the bound isn't relevant.
+///
+/// In the [`VerifyBound`], this struct is enclosed in `Binder to account
+/// for cases like
+///
+/// ```rust
+/// where for<'a> <T as SomeTrait<'a>::Item: 'a
+/// ```
+///
+/// The idea is that we have to find some instantiation of `'a` that can
+/// make `<T as SomeTrait<'a>>::Item` equal to the final value of `G`,
+/// the generic we are checking.
+///
+/// ```ignore (pseudo-rust)
+/// fn(min) -> bool {
+///     exists<'a> {
+///         if G == K {
+///             B(min)
+///         } else {
+///             false
+///         }
+///     }
+/// }
+/// ```
+#[derive(Debug, Copy, Clone, TypeFoldable, TypeVisitable)]
+pub struct VerifyIfEq<'tcx> {
+    /// Type which must match the generic `G`
+    pub ty: Ty<'tcx>,
+
+    /// Bound that applies if `ty` is equal.
+    pub bound: Region<'tcx>,
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash)]
+pub(crate) struct TwoRegions<'tcx> {
+    a: Region<'tcx>,
+    b: Region<'tcx>,
+}
+
+#[derive(Copy, Clone, PartialEq)]
+pub(crate) enum UndoLog<'tcx> {
+    /// We added `RegionVid`.
+    AddVar(RegionVid),
+
+    /// We added the given `constraint`.
+    AddConstraint(Constraint<'tcx>),
+
+    /// We added the given `verify`.
+    AddVerify(usize),
+
+    /// We added the given `given`.
+    AddGiven(Region<'tcx>, ty::RegionVid),
+
+    /// We added a GLB/LUB "combination variable".
+    AddCombination(CombineMapType, TwoRegions<'tcx>),
+}
+
+#[derive(Copy, Clone, PartialEq)]
+pub(crate) enum CombineMapType {
+    Lub,
+    Glb,
+}
+
+type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>;
+
+#[derive(Debug, Clone, Copy)]
+pub struct RegionVariableInfo {
+    pub origin: RegionVariableOrigin,
+    pub universe: ty::UniverseIndex,
+}
+
+pub struct RegionSnapshot {
+    any_unifications: bool,
+}
+
+impl<'tcx> RegionConstraintStorage<'tcx> {
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    #[inline]
+    pub(crate) fn with_log<'a>(
+        &'a mut self,
+        undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
+    ) -> RegionConstraintCollector<'a, 'tcx> {
+        RegionConstraintCollector { storage: self, undo_log }
+    }
+
+    fn rollback_undo_entry(&mut self, undo_entry: UndoLog<'tcx>) {
+        match undo_entry {
+            AddVar(vid) => {
+                self.var_infos.pop().unwrap();
+                assert_eq!(self.var_infos.len(), vid.index() as usize);
+            }
+            AddConstraint(ref constraint) => {
+                self.data.constraints.remove(constraint);
+            }
+            AddVerify(index) => {
+                self.data.verifys.pop();
+                assert_eq!(self.data.verifys.len(), index);
+            }
+            AddGiven(sub, sup) => {
+                self.data.givens.remove(&(sub, sup));
+            }
+            AddCombination(Glb, ref regions) => {
+                self.glbs.remove(regions);
+            }
+            AddCombination(Lub, ref regions) => {
+                self.lubs.remove(regions);
+            }
+        }
+    }
+}
+
+impl<'tcx> RegionConstraintCollector<'_, 'tcx> {
+    pub fn num_region_vars(&self) -> usize {
+        self.var_infos.len()
+    }
+
+    pub fn region_constraint_data(&self) -> &RegionConstraintData<'tcx> {
+        &self.data
+    }
+
+    /// Once all the constraints have been gathered, extract out the final data.
+    ///
+    /// Not legal during a snapshot.
+    pub fn into_infos_and_data(self) -> (VarInfos, RegionConstraintData<'tcx>) {
+        assert!(!UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log));
+        (mem::take(&mut self.storage.var_infos), mem::take(&mut self.storage.data))
+    }
+
+    /// Takes (and clears) the current set of constraints. Note that
+    /// the set of variables remains intact, but all relationships
+    /// between them are reset. This is used during NLL checking to
+    /// grab the set of constraints that arose from a particular
+    /// operation.
+    ///
+    /// We don't want to leak relationships between variables between
+    /// points because just because (say) `r1 == r2` was true at some
+    /// point P in the graph doesn't imply that it will be true at
+    /// some other point Q, in NLL.
+    ///
+    /// Not legal during a snapshot.
+    pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> {
+        assert!(!UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log));
+
+        // If you add a new field to `RegionConstraintCollector`, you
+        // should think carefully about whether it needs to be cleared
+        // or updated in some way.
+        let RegionConstraintStorage {
+            var_infos: _,
+            data,
+            lubs,
+            glbs,
+            unification_table: _,
+            any_unifications,
+        } = self.storage;
+
+        // Clear the tables of (lubs, glbs), so that we will create
+        // fresh regions if we do a LUB operation. As it happens,
+        // LUB/GLB are not performed by the MIR type-checker, which is
+        // the one that uses this method, but it's good to be correct.
+        lubs.clear();
+        glbs.clear();
+
+        let data = mem::take(data);
+
+        // Clear all unifications and recreate the variables a "now
+        // un-unified" state. Note that when we unify `a` and `b`, we
+        // also insert `a <= b` and a `b <= a` edges, so the
+        // `RegionConstraintData` contains the relationship here.
+        if *any_unifications {
+            *any_unifications = false;
+            self.unification_table().reset_unifications(|_| UnifiedRegion(None));
+        }
+
+        data
+    }
+
+    pub fn data(&self) -> &RegionConstraintData<'tcx> {
+        &self.data
+    }
+
+    pub fn start_snapshot(&mut self) -> RegionSnapshot {
+        debug!("RegionConstraintCollector: start_snapshot");
+        RegionSnapshot { any_unifications: self.any_unifications }
+    }
+
+    pub fn rollback_to(&mut self, snapshot: RegionSnapshot) {
+        debug!("RegionConstraintCollector: rollback_to({:?})", snapshot);
+        self.any_unifications = snapshot.any_unifications;
+    }
+
+    pub fn new_region_var(
+        &mut self,
+        universe: ty::UniverseIndex,
+        origin: RegionVariableOrigin,
+    ) -> RegionVid {
+        let vid = self.var_infos.push(RegionVariableInfo { origin, universe });
+
+        let u_vid = self.unification_table().new_key(UnifiedRegion(None));
+        assert_eq!(vid, u_vid.vid);
+        self.undo_log.push(AddVar(vid));
+        debug!("created new region variable {:?} in {:?} with origin {:?}", vid, universe, origin);
+        vid
+    }
+
+    /// Returns the universe for the given variable.
+    pub fn var_universe(&self, vid: RegionVid) -> ty::UniverseIndex {
+        self.var_infos[vid].universe
+    }
+
+    /// Returns the origin for the given variable.
+    pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin {
+        self.var_infos[vid].origin
+    }
+
+    fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) {
+        // cannot add constraints once regions are resolved
+        debug!("RegionConstraintCollector: add_constraint({:?})", constraint);
+
+        // never overwrite an existing (constraint, origin) - only insert one if it isn't
+        // present in the map yet. This prevents origins from outside the snapshot being
+        // replaced with "less informative" origins e.g., during calls to `can_eq`
+        let undo_log = &mut self.undo_log;
+        self.storage.data.constraints.entry(constraint).or_insert_with(|| {
+            undo_log.push(AddConstraint(constraint));
+            origin
+        });
+    }
+
+    fn add_verify(&mut self, verify: Verify<'tcx>) {
+        // cannot add verifys once regions are resolved
+        debug!("RegionConstraintCollector: add_verify({:?})", verify);
+
+        // skip no-op cases known to be satisfied
+        if let VerifyBound::AllBounds(ref bs) = verify.bound && bs.is_empty() {
+            return;
+        }
+
+        let index = self.data.verifys.len();
+        self.data.verifys.push(verify);
+        self.undo_log.push(AddVerify(index));
+    }
+
+    pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) {
+        // cannot add givens once regions are resolved
+        if self.data.givens.insert((sub, sup)) {
+            debug!("add_given({:?} <= {:?})", sub, sup);
+
+            self.undo_log.push(AddGiven(sub, sup));
+        }
+    }
+
+    pub fn make_eqregion(
+        &mut self,
+        origin: SubregionOrigin<'tcx>,
+        sub: Region<'tcx>,
+        sup: Region<'tcx>,
+    ) {
+        if sub != sup {
+            // Eventually, it would be nice to add direct support for
+            // equating regions.
+            self.make_subregion(origin.clone(), sub, sup);
+            self.make_subregion(origin, sup, sub);
+
+            match (sub, sup) {
+                (Region(Interned(ReVar(sub), _)), Region(Interned(ReVar(sup), _))) => {
+                    debug!("make_eqregion: unifying {:?} with {:?}", sub, sup);
+                    self.unification_table().union(*sub, *sup);
+                    self.any_unifications = true;
+                }
+                (Region(Interned(ReVar(vid), _)), value)
+                | (value, Region(Interned(ReVar(vid), _))) => {
+                    debug!("make_eqregion: unifying {:?} with {:?}", vid, value);
+                    self.unification_table().union_value(*vid, UnifiedRegion(Some(value)));
+                    self.any_unifications = true;
+                }
+                (_, _) => {}
+            }
+        }
+    }
+
+    pub fn member_constraint(
+        &mut self,
+        key: ty::OpaqueTypeKey<'tcx>,
+        definition_span: Span,
+        hidden_ty: Ty<'tcx>,
+        member_region: ty::Region<'tcx>,
+        choice_regions: &Lrc<Vec<ty::Region<'tcx>>>,
+    ) {
+        debug!("member_constraint({:?} in {:#?})", member_region, choice_regions);
+
+        if choice_regions.iter().any(|&r| r == member_region) {
+            return;
+        }
+
+        self.data.member_constraints.push(MemberConstraint {
+            key,
+            definition_span,
+            hidden_ty,
+            member_region,
+            choice_regions: choice_regions.clone(),
+        });
+    }
+
+    #[instrument(skip(self, origin), level = "debug")]
+    pub fn make_subregion(
+        &mut self,
+        origin: SubregionOrigin<'tcx>,
+        sub: Region<'tcx>,
+        sup: Region<'tcx>,
+    ) {
+        // cannot add constraints once regions are resolved
+        debug!("origin = {:#?}", origin);
+
+        match (*sub, *sup) {
+            (ReLateBound(..), _) | (_, ReLateBound(..)) => {
+                span_bug!(origin.span(), "cannot relate bound region: {:?} <= {:?}", sub, sup);
+            }
+            (_, ReStatic) => {
+                // all regions are subregions of static, so we can ignore this
+            }
+            (ReVar(sub_id), ReVar(sup_id)) => {
+                self.add_constraint(Constraint::VarSubVar(sub_id, sup_id), origin);
+            }
+            (_, ReVar(sup_id)) => {
+                self.add_constraint(Constraint::RegSubVar(sub, sup_id), origin);
+            }
+            (ReVar(sub_id), _) => {
+                self.add_constraint(Constraint::VarSubReg(sub_id, sup), origin);
+            }
+            _ => {
+                self.add_constraint(Constraint::RegSubReg(sub, sup), origin);
+            }
+        }
+    }
+
+    pub fn verify_generic_bound(
+        &mut self,
+        origin: SubregionOrigin<'tcx>,
+        kind: GenericKind<'tcx>,
+        sub: Region<'tcx>,
+        bound: VerifyBound<'tcx>,
+    ) {
+        self.add_verify(Verify { kind, origin, region: sub, bound });
+    }
+
+    pub fn lub_regions(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+        origin: SubregionOrigin<'tcx>,
+        a: Region<'tcx>,
+        b: Region<'tcx>,
+    ) -> Region<'tcx> {
+        // cannot add constraints once regions are resolved
+        debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b);
+        if a.is_static() || b.is_static() {
+            a // nothing lives longer than static
+        } else if a == b {
+            a // LUB(a,a) = a
+        } else {
+            self.combine_vars(tcx, Lub, a, b, origin)
+        }
+    }
+
+    pub fn glb_regions(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+        origin: SubregionOrigin<'tcx>,
+        a: Region<'tcx>,
+        b: Region<'tcx>,
+    ) -> Region<'tcx> {
+        // cannot add constraints once regions are resolved
+        debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b);
+        if a.is_static() {
+            b // static lives longer than everything else
+        } else if b.is_static() {
+            a // static lives longer than everything else
+        } else if a == b {
+            a // GLB(a,a) = a
+        } else {
+            self.combine_vars(tcx, Glb, a, b, origin)
+        }
+    }
+
+    /// Resolves the passed RegionVid to the root RegionVid in the unification table
+    pub fn opportunistic_resolve_var(&mut self, rid: ty::RegionVid) -> ty::RegionVid {
+        self.unification_table().find(rid).vid
+    }
+
+    /// If the Region is a `ReVar`, then resolves it either to the root value in
+    /// the unification table, if it exists, or to the root `ReVar` in the table.
+    /// If the Region is not a `ReVar`, just returns the Region itself.
+    pub fn opportunistic_resolve_region(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+        region: ty::Region<'tcx>,
+    ) -> ty::Region<'tcx> {
+        match *region {
+            ty::ReVar(rid) => {
+                let unified_region = self.unification_table().probe_value(rid);
+                unified_region.0.unwrap_or_else(|| {
+                    let root = self.unification_table().find(rid).vid;
+                    tcx.reuse_or_mk_region(region, ty::ReVar(root))
+                })
+            }
+            _ => region,
+        }
+    }
+
+    fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> {
+        match t {
+            Glb => &mut self.glbs,
+            Lub => &mut self.lubs,
+        }
+    }
+
+    fn combine_vars(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+        t: CombineMapType,
+        a: Region<'tcx>,
+        b: Region<'tcx>,
+        origin: SubregionOrigin<'tcx>,
+    ) -> Region<'tcx> {
+        let vars = TwoRegions { a, b };
+        if let Some(&c) = self.combine_map(t).get(&vars) {
+            return tcx.mk_region(ReVar(c));
+        }
+        let a_universe = self.universe(a);
+        let b_universe = self.universe(b);
+        let c_universe = cmp::max(a_universe, b_universe);
+        let c = self.new_region_var(c_universe, MiscVariable(origin.span()));
+        self.combine_map(t).insert(vars, c);
+        self.undo_log.push(AddCombination(t, vars));
+        let new_r = tcx.mk_region(ReVar(c));
+        for old_r in [a, b] {
+            match t {
+                Glb => self.make_subregion(origin.clone(), new_r, old_r),
+                Lub => self.make_subregion(origin.clone(), old_r, new_r),
+            }
+        }
+        debug!("combine_vars() c={:?}", c);
+        new_r
+    }
+
+    pub fn universe(&self, region: Region<'tcx>) -> ty::UniverseIndex {
+        match *region {
+            ty::ReStatic | ty::ReErased | ty::ReFree(..) | ty::ReEarlyBound(..) => {
+                ty::UniverseIndex::ROOT
+            }
+            ty::ReEmpty(ui) => ui,
+            ty::RePlaceholder(placeholder) => placeholder.universe,
+            ty::ReVar(vid) => self.var_universe(vid),
+            ty::ReLateBound(..) => bug!("universe(): encountered bound region {:?}", region),
+        }
+    }
+
+    pub fn vars_since_snapshot(
+        &self,
+        value_count: usize,
+    ) -> (Range<RegionVid>, Vec<RegionVariableOrigin>) {
+        let range = RegionVid::from(value_count)..RegionVid::from(self.unification_table.len());
+        (
+            range.clone(),
+            (range.start.index()..range.end.index())
+                .map(|index| self.var_infos[ty::RegionVid::from(index)].origin)
+                .collect(),
+        )
+    }
+
+    /// See `InferCtxt::region_constraints_added_in_snapshot`.
+    pub fn region_constraints_added_in_snapshot(&self, mark: &Snapshot<'tcx>) -> Option<bool> {
+        self.undo_log
+            .region_constraints_in_snapshot(mark)
+            .map(|&elt| match elt {
+                AddConstraint(constraint) => Some(constraint.involves_placeholders()),
+                _ => None,
+            })
+            .max()
+            .unwrap_or(None)
+    }
+
+    #[inline]
+    fn unification_table(&mut self) -> super::UnificationTable<'_, 'tcx, RegionVidKey<'tcx>> {
+        ut::UnificationTable::with_log(&mut self.storage.unification_table, self.undo_log)
+    }
+}
+
+impl fmt::Debug for RegionSnapshot {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "RegionSnapshot")
+    }
+}
+
+impl<'tcx> fmt::Debug for GenericKind<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match *self {
+            GenericKind::Param(ref p) => write!(f, "{:?}", p),
+            GenericKind::Projection(ref p) => write!(f, "{:?}", p),
+        }
+    }
+}
+
+impl<'tcx> fmt::Display for GenericKind<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match *self {
+            GenericKind::Param(ref p) => write!(f, "{}", p),
+            GenericKind::Projection(ref p) => write!(f, "{}", p),
+        }
+    }
+}
+
+impl<'tcx> GenericKind<'tcx> {
+    pub fn to_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
+        match *self {
+            GenericKind::Param(ref p) => p.to_ty(tcx),
+            GenericKind::Projection(ref p) => tcx.mk_projection(p.item_def_id, p.substs),
+        }
+    }
+}
+
+impl<'tcx> VerifyBound<'tcx> {
+    pub fn must_hold(&self) -> bool {
+        match self {
+            VerifyBound::IfEq(..) => false,
+            VerifyBound::OutlivedBy(re) => re.is_static(),
+            VerifyBound::IsEmpty => false,
+            VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()),
+            VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()),
+        }
+    }
+
+    pub fn cannot_hold(&self) -> bool {
+        match self {
+            VerifyBound::IfEq(..) => false,
+            VerifyBound::IsEmpty => false,
+            VerifyBound::OutlivedBy(_) => false,
+            VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()),
+            VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()),
+        }
+    }
+
+    pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
+        if self.must_hold() || vb.cannot_hold() {
+            self
+        } else if self.cannot_hold() || vb.must_hold() {
+            vb
+        } else {
+            VerifyBound::AnyBound(vec![self, vb])
+        }
+    }
+}
+
+impl<'tcx> RegionConstraintData<'tcx> {
+    /// Returns `true` if this region constraint data contains no constraints, and `false`
+    /// otherwise.
+    pub fn is_empty(&self) -> bool {
+        let RegionConstraintData { constraints, member_constraints, verifys, givens } = self;
+        constraints.is_empty()
+            && member_constraints.is_empty()
+            && verifys.is_empty()
+            && givens.is_empty()
+    }
+}
+
+impl<'tcx> Rollback<UndoLog<'tcx>> for RegionConstraintStorage<'tcx> {
+    fn reverse(&mut self, undo: UndoLog<'tcx>) {
+        self.rollback_undo_entry(undo)
+    }
+}