From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- .../src/infer/region_constraints/README.md | 3 + .../src/infer/region_constraints/leak_check.rs | 447 +++++++++++ .../src/infer/region_constraints/mod.rs | 821 +++++++++++++++++++++ 3 files changed, 1271 insertions(+) create mode 100644 compiler/rustc_infer/src/infer/region_constraints/README.md create mode 100644 compiler/rustc_infer/src/infer/region_constraints/leak_check.rs create mode 100644 compiler/rustc_infer/src/infer/region_constraints/mod.rs (limited to 'compiler/rustc_infer/src/infer/region_constraints') 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::>::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>, + + // 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>, +} + +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>, +} + +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, 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, +} + +impl<'tcx> MiniGraph<'tcx> { + fn new<'a>( + tcx: TyCtxt<'tcx>, + undo_log: impl Iterator>, + 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>, + 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, 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, + + 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>, + + /// 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; + +/// 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, 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>, + + /// 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>, + + /// 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>), + + /// 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>), +} + +/// 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 +/// >::Item: 'b +/// ``` +/// +/// If we have an obligation like `>::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> ::Item: 'a +/// ``` +/// +/// The idea is that we have to find some instantiation of `'a` that can +/// make `>::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, 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::>::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::>::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>>, + ) { + 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, Vec) { + 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 { + 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> for RegionConstraintStorage<'tcx> { + fn reverse(&mut self, undo: UndoLog<'tcx>) { + self.rollback_undo_entry(undo) + } +} -- cgit v1.2.3