diff options
Diffstat (limited to 'compiler/rustc_borrowck/src/region_infer')
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/dump_mir.rs | 93 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/graphviz.rs | 140 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/mod.rs | 2365 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/opaque_types.rs | 662 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs | 68 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/values.rs | 488 |
6 files changed, 3816 insertions, 0 deletions
diff --git a/compiler/rustc_borrowck/src/region_infer/dump_mir.rs b/compiler/rustc_borrowck/src/region_infer/dump_mir.rs new file mode 100644 index 000000000..fe5193102 --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/dump_mir.rs @@ -0,0 +1,93 @@ +//! As part of generating the regions, if you enable `-Zdump-mir=nll`, +//! we will generate an annotated copy of the MIR that includes the +//! state of region inference. This code handles emitting the region +//! context internal state. + +use super::{OutlivesConstraint, RegionInferenceContext}; +use crate::type_check::Locations; +use rustc_infer::infer::NllRegionVariableOrigin; +use rustc_middle::ty::TyCtxt; +use std::io::{self, Write}; + +// Room for "'_#NNNNr" before things get misaligned. +// Easy enough to fix if this ever doesn't seem like +// enough. +const REGION_WIDTH: usize = 8; + +impl<'tcx> RegionInferenceContext<'tcx> { + /// Write out our state into the `.mir` files. + pub(crate) fn dump_mir(&self, tcx: TyCtxt<'tcx>, out: &mut dyn Write) -> io::Result<()> { + writeln!(out, "| Free Region Mapping")?; + + for region in self.regions() { + if let NllRegionVariableOrigin::FreeRegion = self.definitions[region].origin { + let classification = self.universal_regions.region_classification(region).unwrap(); + let outlived_by = self.universal_region_relations.regions_outlived_by(region); + writeln!( + out, + "| {r:rw$?} | {c:cw$?} | {ob:?}", + r = region, + rw = REGION_WIDTH, + c = classification, + cw = 8, // "External" at most + ob = outlived_by + )?; + } + } + + writeln!(out, "|")?; + writeln!(out, "| Inferred Region Values")?; + for region in self.regions() { + writeln!( + out, + "| {r:rw$?} | {ui:4?} | {v}", + r = region, + rw = REGION_WIDTH, + ui = self.region_universe(region), + v = self.region_value_str(region), + )?; + } + + writeln!(out, "|")?; + writeln!(out, "| Inference Constraints")?; + self.for_each_constraint(tcx, &mut |msg| writeln!(out, "| {}", msg))?; + + Ok(()) + } + + /// Debugging aid: Invokes the `with_msg` callback repeatedly with + /// our internal region constraints. These are dumped into the + /// -Zdump-mir file so that we can figure out why the region + /// inference resulted in the values that it did when debugging. + fn for_each_constraint( + &self, + tcx: TyCtxt<'tcx>, + with_msg: &mut dyn FnMut(&str) -> io::Result<()>, + ) -> io::Result<()> { + for region in self.definitions.indices() { + let value = self.liveness_constraints.region_value_str(region); + if value != "{}" { + with_msg(&format!("{:?} live at {}", region, value))?; + } + } + + let mut constraints: Vec<_> = self.constraints.outlives().iter().collect(); + constraints.sort_by_key(|c| (c.sup, c.sub)); + for constraint in &constraints { + let OutlivesConstraint { sup, sub, locations, category, span, variance_info: _ } = + constraint; + let (name, arg) = match locations { + Locations::All(span) => { + ("All", tcx.sess.source_map().span_to_embeddable_string(*span)) + } + Locations::Single(loc) => ("Single", format!("{:?}", loc)), + }; + with_msg(&format!( + "{:?}: {:?} due to {:?} at {}({}) ({:?}", + sup, sub, category, name, arg, span + ))?; + } + + Ok(()) + } +} diff --git a/compiler/rustc_borrowck/src/region_infer/graphviz.rs b/compiler/rustc_borrowck/src/region_infer/graphviz.rs new file mode 100644 index 000000000..f31ccd74c --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/graphviz.rs @@ -0,0 +1,140 @@ +//! This module provides linkage between RegionInferenceContext and +//! `rustc_graphviz` traits, specialized to attaching borrowck analysis +//! data to rendered labels. + +use std::borrow::Cow; +use std::io::{self, Write}; + +use super::*; +use crate::constraints::OutlivesConstraint; +use rustc_graphviz as dot; + +impl<'tcx> RegionInferenceContext<'tcx> { + /// Write out the region constraint graph. + pub(crate) fn dump_graphviz_raw_constraints(&self, mut w: &mut dyn Write) -> io::Result<()> { + dot::render(&RawConstraints { regioncx: self }, &mut w) + } + + /// Write out the region constraint graph. + pub(crate) fn dump_graphviz_scc_constraints(&self, mut w: &mut dyn Write) -> io::Result<()> { + let mut nodes_per_scc: IndexVec<ConstraintSccIndex, _> = + self.constraint_sccs.all_sccs().map(|_| Vec::new()).collect(); + + for region in self.definitions.indices() { + let scc = self.constraint_sccs.scc(region); + nodes_per_scc[scc].push(region); + } + + dot::render(&SccConstraints { regioncx: self, nodes_per_scc }, &mut w) + } +} + +struct RawConstraints<'a, 'tcx> { + regioncx: &'a RegionInferenceContext<'tcx>, +} + +impl<'a, 'this, 'tcx> dot::Labeller<'this> for RawConstraints<'a, 'tcx> { + type Node = RegionVid; + type Edge = OutlivesConstraint<'tcx>; + + fn graph_id(&'this self) -> dot::Id<'this> { + dot::Id::new("RegionInferenceContext").unwrap() + } + fn node_id(&'this self, n: &RegionVid) -> dot::Id<'this> { + dot::Id::new(format!("r{}", n.index())).unwrap() + } + fn node_shape(&'this self, _node: &RegionVid) -> Option<dot::LabelText<'this>> { + Some(dot::LabelText::LabelStr(Cow::Borrowed("box"))) + } + fn node_label(&'this self, n: &RegionVid) -> dot::LabelText<'this> { + dot::LabelText::LabelStr(format!("{:?}", n).into()) + } + fn edge_label(&'this self, e: &OutlivesConstraint<'tcx>) -> dot::LabelText<'this> { + dot::LabelText::LabelStr(format!("{:?}", e.locations).into()) + } +} + +impl<'a, 'this, 'tcx> dot::GraphWalk<'this> for RawConstraints<'a, 'tcx> { + type Node = RegionVid; + type Edge = OutlivesConstraint<'tcx>; + + fn nodes(&'this self) -> dot::Nodes<'this, RegionVid> { + let vids: Vec<RegionVid> = self.regioncx.definitions.indices().collect(); + vids.into() + } + fn edges(&'this self) -> dot::Edges<'this, OutlivesConstraint<'tcx>> { + (&self.regioncx.constraints.outlives().raw[..]).into() + } + + // Render `a: b` as `a -> b`, indicating the flow + // of data during inference. + + fn source(&'this self, edge: &OutlivesConstraint<'tcx>) -> RegionVid { + edge.sup + } + + fn target(&'this self, edge: &OutlivesConstraint<'tcx>) -> RegionVid { + edge.sub + } +} + +struct SccConstraints<'a, 'tcx> { + regioncx: &'a RegionInferenceContext<'tcx>, + nodes_per_scc: IndexVec<ConstraintSccIndex, Vec<RegionVid>>, +} + +impl<'a, 'this, 'tcx> dot::Labeller<'this> for SccConstraints<'a, 'tcx> { + type Node = ConstraintSccIndex; + type Edge = (ConstraintSccIndex, ConstraintSccIndex); + + fn graph_id(&'this self) -> dot::Id<'this> { + dot::Id::new("RegionInferenceContext".to_string()).unwrap() + } + fn node_id(&'this self, n: &ConstraintSccIndex) -> dot::Id<'this> { + dot::Id::new(format!("r{}", n.index())).unwrap() + } + fn node_shape(&'this self, _node: &ConstraintSccIndex) -> Option<dot::LabelText<'this>> { + Some(dot::LabelText::LabelStr(Cow::Borrowed("box"))) + } + fn node_label(&'this self, n: &ConstraintSccIndex) -> dot::LabelText<'this> { + let nodes = &self.nodes_per_scc[*n]; + dot::LabelText::LabelStr(format!("{:?} = {:?}", n, nodes).into()) + } +} + +impl<'a, 'this, 'tcx> dot::GraphWalk<'this> for SccConstraints<'a, 'tcx> { + type Node = ConstraintSccIndex; + type Edge = (ConstraintSccIndex, ConstraintSccIndex); + + fn nodes(&'this self) -> dot::Nodes<'this, ConstraintSccIndex> { + let vids: Vec<ConstraintSccIndex> = self.regioncx.constraint_sccs.all_sccs().collect(); + vids.into() + } + fn edges(&'this self) -> dot::Edges<'this, (ConstraintSccIndex, ConstraintSccIndex)> { + let edges: Vec<_> = self + .regioncx + .constraint_sccs + .all_sccs() + .flat_map(|scc_a| { + self.regioncx + .constraint_sccs + .successors(scc_a) + .iter() + .map(move |&scc_b| (scc_a, scc_b)) + }) + .collect(); + + edges.into() + } + + // Render `a: b` as `a -> b`, indicating the flow + // of data during inference. + + fn source(&'this self, edge: &(ConstraintSccIndex, ConstraintSccIndex)) -> ConstraintSccIndex { + edge.0 + } + + fn target(&'this self, edge: &(ConstraintSccIndex, ConstraintSccIndex)) -> ConstraintSccIndex { + edge.1 + } +} diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs new file mode 100644 index 000000000..2894c6d29 --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/mod.rs @@ -0,0 +1,2365 @@ +use std::collections::VecDeque; +use std::rc::Rc; + +use rustc_data_structures::binary_search_util; +use rustc_data_structures::frozen::Frozen; +use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use rustc_data_structures::graph::scc::Sccs; +use rustc_errors::Diagnostic; +use rustc_hir::def_id::{DefId, CRATE_DEF_ID}; +use rustc_hir::CRATE_HIR_ID; +use rustc_index::vec::IndexVec; +use rustc_infer::infer::canonical::QueryOutlivesConstraint; +use rustc_infer::infer::outlives::test_type_match; +use rustc_infer::infer::region_constraints::{GenericKind, VarInfos, VerifyBound, VerifyIfEq}; +use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin, RegionVariableOrigin}; +use rustc_middle::mir::{ + Body, ClosureOutlivesRequirement, ClosureOutlivesSubject, ClosureRegionRequirements, + ConstraintCategory, Local, Location, ReturnConstraint, +}; +use rustc_middle::traits::ObligationCause; +use rustc_middle::traits::ObligationCauseCode; +use rustc_middle::ty::{ + self, subst::SubstsRef, RegionVid, Ty, TyCtxt, TypeFoldable, TypeVisitable, +}; +use rustc_span::Span; + +use crate::{ + constraints::{ + graph::NormalConstraintGraph, ConstraintSccIndex, OutlivesConstraint, OutlivesConstraintSet, + }, + diagnostics::{RegionErrorKind, RegionErrors, UniverseInfo}, + member_constraints::{MemberConstraintSet, NllMemberConstraintIndex}, + nll::{PoloniusOutput, ToRegionVid}, + region_infer::reverse_sccs::ReverseSccGraph, + region_infer::values::{ + LivenessValues, PlaceholderIndices, RegionElement, RegionValueElements, RegionValues, + ToElementIndex, + }, + type_check::{free_region_relations::UniversalRegionRelations, Locations}, + universal_regions::UniversalRegions, +}; + +mod dump_mir; +mod graphviz; +mod opaque_types; +mod reverse_sccs; + +pub mod values; + +pub struct RegionInferenceContext<'tcx> { + pub var_infos: VarInfos, + + /// Contains the definition for every region variable. Region + /// variables are identified by their index (`RegionVid`). The + /// definition contains information about where the region came + /// from as well as its final inferred value. + definitions: IndexVec<RegionVid, RegionDefinition<'tcx>>, + + /// The liveness constraints added to each region. For most + /// regions, these start out empty and steadily grow, though for + /// each universally quantified region R they start out containing + /// the entire CFG and `end(R)`. + liveness_constraints: LivenessValues<RegionVid>, + + /// The outlives constraints computed by the type-check. + constraints: Frozen<OutlivesConstraintSet<'tcx>>, + + /// The constraint-set, but in graph form, making it easy to traverse + /// the constraints adjacent to a particular region. Used to construct + /// the SCC (see `constraint_sccs`) and for error reporting. + constraint_graph: Frozen<NormalConstraintGraph>, + + /// The SCC computed from `constraints` and the constraint + /// graph. We have an edge from SCC A to SCC B if `A: B`. Used to + /// compute the values of each region. + constraint_sccs: Rc<Sccs<RegionVid, ConstraintSccIndex>>, + + /// Reverse of the SCC constraint graph -- i.e., an edge `A -> B` exists if + /// `B: A`. This is used to compute the universal regions that are required + /// to outlive a given SCC. Computed lazily. + rev_scc_graph: Option<Rc<ReverseSccGraph>>, + + /// The "R0 member of [R1..Rn]" constraints, indexed by SCC. + member_constraints: Rc<MemberConstraintSet<'tcx, ConstraintSccIndex>>, + + /// Records the member constraints that we applied to each scc. + /// This is useful for error reporting. Once constraint + /// propagation is done, this vector is sorted according to + /// `member_region_scc`. + member_constraints_applied: Vec<AppliedMemberConstraint>, + + /// Map closure bounds to a `Span` that should be used for error reporting. + closure_bounds_mapping: + FxHashMap<Location, FxHashMap<(RegionVid, RegionVid), (ConstraintCategory<'tcx>, Span)>>, + + /// Map universe indexes to information on why we created it. + universe_causes: FxHashMap<ty::UniverseIndex, UniverseInfo<'tcx>>, + + /// Contains the minimum universe of any variable within the same + /// SCC. We will ensure that no SCC contains values that are not + /// visible from this index. + scc_universes: IndexVec<ConstraintSccIndex, ty::UniverseIndex>, + + /// Contains a "representative" from each SCC. This will be the + /// minimal RegionVid belonging to that universe. It is used as a + /// kind of hacky way to manage checking outlives relationships, + /// since we can 'canonicalize' each region to the representative + /// of its SCC and be sure that -- if they have the same repr -- + /// they *must* be equal (though not having the same repr does not + /// mean they are unequal). + scc_representatives: IndexVec<ConstraintSccIndex, ty::RegionVid>, + + /// The final inferred values of the region variables; we compute + /// one value per SCC. To get the value for any given *region*, + /// you first find which scc it is a part of. + scc_values: RegionValues<ConstraintSccIndex>, + + /// Type constraints that we check after solving. + type_tests: Vec<TypeTest<'tcx>>, + + /// Information about the universally quantified regions in scope + /// on this function. + universal_regions: Rc<UniversalRegions<'tcx>>, + + /// Information about how the universally quantified regions in + /// scope on this function relate to one another. + universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, +} + +/// Each time that `apply_member_constraint` is successful, it appends +/// one of these structs to the `member_constraints_applied` field. +/// This is used in error reporting to trace out what happened. +/// +/// The way that `apply_member_constraint` works is that it effectively +/// adds a new lower bound to the SCC it is analyzing: so you wind up +/// with `'R: 'O` where `'R` is the pick-region and `'O` is the +/// minimal viable option. +#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)] +pub(crate) struct AppliedMemberConstraint { + /// The SCC that was affected. (The "member region".) + /// + /// The vector if `AppliedMemberConstraint` elements is kept sorted + /// by this field. + pub(crate) member_region_scc: ConstraintSccIndex, + + /// The "best option" that `apply_member_constraint` found -- this was + /// added as an "ad-hoc" lower-bound to `member_region_scc`. + pub(crate) min_choice: ty::RegionVid, + + /// The "member constraint index" -- we can find out details about + /// the constraint from + /// `set.member_constraints[member_constraint_index]`. + pub(crate) member_constraint_index: NllMemberConstraintIndex, +} + +pub(crate) struct RegionDefinition<'tcx> { + /// What kind of variable is this -- a free region? existential + /// variable? etc. (See the `NllRegionVariableOrigin` for more + /// info.) + pub(crate) origin: NllRegionVariableOrigin, + + /// Which universe is this region variable defined in? This is + /// most often `ty::UniverseIndex::ROOT`, but when we encounter + /// forall-quantifiers like `for<'a> { 'a = 'b }`, we would create + /// the variable for `'a` in a fresh universe that extends ROOT. + pub(crate) universe: ty::UniverseIndex, + + /// If this is 'static or an early-bound region, then this is + /// `Some(X)` where `X` is the name of the region. + pub(crate) external_name: Option<ty::Region<'tcx>>, +} + +/// N.B., the variants in `Cause` are intentionally ordered. Lower +/// values are preferred when it comes to error messages. Do not +/// reorder willy nilly. +#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)] +pub(crate) enum Cause { + /// point inserted because Local was live at the given Location + LiveVar(Local, Location), + + /// point inserted because Local was dropped at the given Location + DropVar(Local, Location), +} + +/// A "type test" corresponds to an outlives constraint between a type +/// and a lifetime, like `T: 'x` or `<T as Foo>::Bar: 'x`. They are +/// translated from the `Verify` region constraints in the ordinary +/// inference context. +/// +/// These sorts of constraints are handled differently than ordinary +/// constraints, at least at present. During type checking, the +/// `InferCtxt::process_registered_region_obligations` method will +/// attempt to convert a type test like `T: 'x` into an ordinary +/// outlives constraint when possible (for example, `&'a T: 'b` will +/// be converted into `'a: 'b` and registered as a `Constraint`). +/// +/// In some cases, however, there are outlives relationships that are +/// not converted into a region constraint, but rather into one of +/// these "type tests". The distinction is that a type test does not +/// influence the inference result, but instead just examines the +/// values that we ultimately inferred for each region variable and +/// checks that they meet certain extra criteria. If not, an error +/// can be issued. +/// +/// One reason for this is that these type tests typically boil down +/// to a check like `'a: 'x` where `'a` is a universally quantified +/// region -- and therefore not one whose value is really meant to be +/// *inferred*, precisely (this is not always the case: one can have a +/// type test like `<Foo as Trait<'?0>>::Bar: 'x`, where `'?0` is an +/// inference variable). Another reason is that these type tests can +/// involve *disjunction* -- that is, they can be satisfied in more +/// than one way. +/// +/// For more information about this translation, see +/// `InferCtxt::process_registered_region_obligations` and +/// `InferCtxt::type_must_outlive` in `rustc_infer::infer::InferCtxt`. +#[derive(Clone, Debug)] +pub struct TypeTest<'tcx> { + /// The type `T` that must outlive the region. + pub generic_kind: GenericKind<'tcx>, + + /// The region `'x` that the type must outlive. + pub lower_bound: RegionVid, + + /// Where did this constraint arise and why? + pub locations: Locations, + + /// A test which, if met by the region `'x`, proves that this type + /// constraint is satisfied. + pub verify_bound: VerifyBound<'tcx>, +} + +/// When we have an unmet lifetime constraint, we try to propagate it outward (e.g. to a closure +/// environment). If we can't, it is an error. +#[derive(Clone, Copy, Debug, Eq, PartialEq)] +enum RegionRelationCheckResult { + Ok, + Propagated, + Error, +} + +#[derive(Clone, PartialEq, Eq, Debug)] +enum Trace<'tcx> { + StartRegion, + FromOutlivesConstraint(OutlivesConstraint<'tcx>), + NotVisited, +} + +impl<'tcx> RegionInferenceContext<'tcx> { + /// Creates a new region inference context with a total of + /// `num_region_variables` valid inference variables; the first N + /// of those will be constant regions representing the free + /// regions defined in `universal_regions`. + /// + /// The `outlives_constraints` and `type_tests` are an initial set + /// of constraints produced by the MIR type check. + pub(crate) fn new( + var_infos: VarInfos, + universal_regions: Rc<UniversalRegions<'tcx>>, + placeholder_indices: Rc<PlaceholderIndices>, + universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>, + outlives_constraints: OutlivesConstraintSet<'tcx>, + member_constraints_in: MemberConstraintSet<'tcx, RegionVid>, + closure_bounds_mapping: FxHashMap< + Location, + FxHashMap<(RegionVid, RegionVid), (ConstraintCategory<'tcx>, Span)>, + >, + universe_causes: FxHashMap<ty::UniverseIndex, UniverseInfo<'tcx>>, + type_tests: Vec<TypeTest<'tcx>>, + liveness_constraints: LivenessValues<RegionVid>, + elements: &Rc<RegionValueElements>, + ) -> Self { + // Create a RegionDefinition for each inference variable. + let definitions: IndexVec<_, _> = var_infos + .iter() + .map(|info| RegionDefinition::new(info.universe, info.origin)) + .collect(); + + let constraints = Frozen::freeze(outlives_constraints); + let constraint_graph = Frozen::freeze(constraints.graph(definitions.len())); + let fr_static = universal_regions.fr_static; + let constraint_sccs = Rc::new(constraints.compute_sccs(&constraint_graph, fr_static)); + + let mut scc_values = + RegionValues::new(elements, universal_regions.len(), &placeholder_indices); + + for region in liveness_constraints.rows() { + let scc = constraint_sccs.scc(region); + scc_values.merge_liveness(scc, region, &liveness_constraints); + } + + let scc_universes = Self::compute_scc_universes(&constraint_sccs, &definitions); + + let scc_representatives = Self::compute_scc_representatives(&constraint_sccs, &definitions); + + let member_constraints = + Rc::new(member_constraints_in.into_mapped(|r| constraint_sccs.scc(r))); + + let mut result = Self { + var_infos, + definitions, + liveness_constraints, + constraints, + constraint_graph, + constraint_sccs, + rev_scc_graph: None, + member_constraints, + member_constraints_applied: Vec::new(), + closure_bounds_mapping, + universe_causes, + scc_universes, + scc_representatives, + scc_values, + type_tests, + universal_regions, + universal_region_relations, + }; + + result.init_free_and_bound_regions(); + + result + } + + /// Each SCC is the combination of many region variables which + /// have been equated. Therefore, we can associate a universe with + /// each SCC which is minimum of all the universes of its + /// constituent regions -- this is because whatever value the SCC + /// takes on must be a value that each of the regions within the + /// SCC could have as well. This implies that the SCC must have + /// the minimum, or narrowest, universe. + fn compute_scc_universes( + constraint_sccs: &Sccs<RegionVid, ConstraintSccIndex>, + definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>, + ) -> IndexVec<ConstraintSccIndex, ty::UniverseIndex> { + let num_sccs = constraint_sccs.num_sccs(); + let mut scc_universes = IndexVec::from_elem_n(ty::UniverseIndex::MAX, num_sccs); + + debug!("compute_scc_universes()"); + + // For each region R in universe U, ensure that the universe for the SCC + // that contains R is "no bigger" than U. This effectively sets the universe + // for each SCC to be the minimum of the regions within. + for (region_vid, region_definition) in definitions.iter_enumerated() { + let scc = constraint_sccs.scc(region_vid); + let scc_universe = &mut scc_universes[scc]; + let scc_min = std::cmp::min(region_definition.universe, *scc_universe); + if scc_min != *scc_universe { + *scc_universe = scc_min; + debug!( + "compute_scc_universes: lowered universe of {scc:?} to {scc_min:?} \ + because it contains {region_vid:?} in {region_universe:?}", + scc = scc, + scc_min = scc_min, + region_vid = region_vid, + region_universe = region_definition.universe, + ); + } + } + + // Walk each SCC `A` and `B` such that `A: B` + // and ensure that universe(A) can see universe(B). + // + // This serves to enforce the 'empty/placeholder' hierarchy + // (described in more detail on `RegionKind`): + // + // ``` + // static -----+ + // | | + // empty(U0) placeholder(U1) + // | / + // empty(U1) + // ``` + // + // In particular, imagine we have variables R0 in U0 and R1 + // created in U1, and constraints like this; + // + // ``` + // R1: !1 // R1 outlives the placeholder in U1 + // R1: R0 // R1 outlives R0 + // ``` + // + // Here, we wish for R1 to be `'static`, because it + // cannot outlive `placeholder(U1)` and `empty(U0)` any other way. + // + // Thanks to this loop, what happens is that the `R1: R0` + // constraint lowers the universe of `R1` to `U0`, which in turn + // means that the `R1: !1` constraint will (later) cause + // `R1` to become `'static`. + for scc_a in constraint_sccs.all_sccs() { + for &scc_b in constraint_sccs.successors(scc_a) { + let scc_universe_a = scc_universes[scc_a]; + let scc_universe_b = scc_universes[scc_b]; + let scc_universe_min = std::cmp::min(scc_universe_a, scc_universe_b); + if scc_universe_a != scc_universe_min { + scc_universes[scc_a] = scc_universe_min; + + debug!( + "compute_scc_universes: lowered universe of {scc_a:?} to {scc_universe_min:?} \ + because {scc_a:?}: {scc_b:?} and {scc_b:?} is in universe {scc_universe_b:?}", + scc_a = scc_a, + scc_b = scc_b, + scc_universe_min = scc_universe_min, + scc_universe_b = scc_universe_b + ); + } + } + } + + debug!("compute_scc_universes: scc_universe = {:#?}", scc_universes); + + scc_universes + } + + /// For each SCC, we compute a unique `RegionVid` (in fact, the + /// minimal one that belongs to the SCC). See + /// `scc_representatives` field of `RegionInferenceContext` for + /// more details. + fn compute_scc_representatives( + constraints_scc: &Sccs<RegionVid, ConstraintSccIndex>, + definitions: &IndexVec<RegionVid, RegionDefinition<'tcx>>, + ) -> IndexVec<ConstraintSccIndex, ty::RegionVid> { + let num_sccs = constraints_scc.num_sccs(); + let next_region_vid = definitions.next_index(); + let mut scc_representatives = IndexVec::from_elem_n(next_region_vid, num_sccs); + + for region_vid in definitions.indices() { + let scc = constraints_scc.scc(region_vid); + let prev_min = scc_representatives[scc]; + scc_representatives[scc] = region_vid.min(prev_min); + } + + scc_representatives + } + + /// Initializes the region variables for each universally + /// quantified region (lifetime parameter). The first N variables + /// always correspond to the regions appearing in the function + /// signature (both named and anonymous) and where-clauses. This + /// function iterates over those regions and initializes them with + /// minimum values. + /// + /// For example: + /// ``` + /// fn foo<'a, 'b>( /* ... */ ) where 'a: 'b { /* ... */ } + /// ``` + /// would initialize two variables like so: + /// ```ignore (illustrative) + /// R0 = { CFG, R0 } // 'a + /// R1 = { CFG, R0, R1 } // 'b + /// ``` + /// Here, R0 represents `'a`, and it contains (a) the entire CFG + /// and (b) any universally quantified regions that it outlives, + /// which in this case is just itself. R1 (`'b`) in contrast also + /// outlives `'a` and hence contains R0 and R1. + fn init_free_and_bound_regions(&mut self) { + // Update the names (if any) + for (external_name, variable) in self.universal_regions.named_universal_regions() { + debug!( + "init_universal_regions: region {:?} has external name {:?}", + variable, external_name + ); + self.definitions[variable].external_name = Some(external_name); + } + + for variable in self.definitions.indices() { + let scc = self.constraint_sccs.scc(variable); + + match self.definitions[variable].origin { + NllRegionVariableOrigin::FreeRegion => { + // For each free, universally quantified region X: + + // Add all nodes in the CFG to liveness constraints + self.liveness_constraints.add_all_points(variable); + self.scc_values.add_all_points(scc); + + // Add `end(X)` into the set for X. + self.scc_values.add_element(scc, variable); + } + + NllRegionVariableOrigin::Placeholder(placeholder) => { + // Each placeholder region is only visible from + // its universe `ui` and its extensions. So we + // can't just add it into `scc` unless the + // universe of the scc can name this region. + let scc_universe = self.scc_universes[scc]; + if scc_universe.can_name(placeholder.universe) { + self.scc_values.add_element(scc, placeholder); + } else { + debug!( + "init_free_and_bound_regions: placeholder {:?} is \ + not compatible with universe {:?} of its SCC {:?}", + placeholder, scc_universe, scc, + ); + self.add_incompatible_universe(scc); + } + } + + NllRegionVariableOrigin::Existential { .. } => { + // For existential, regions, nothing to do. + } + } + } + } + + /// Returns an iterator over all the region indices. + pub fn regions(&self) -> impl Iterator<Item = RegionVid> + 'tcx { + self.definitions.indices() + } + + /// Given a universal region in scope on the MIR, returns the + /// corresponding index. + /// + /// (Panics if `r` is not a registered universal region.) + pub fn to_region_vid(&self, r: ty::Region<'tcx>) -> RegionVid { + self.universal_regions.to_region_vid(r) + } + + /// Adds annotations for `#[rustc_regions]`; see `UniversalRegions::annotate`. + pub(crate) fn annotate(&self, tcx: TyCtxt<'tcx>, err: &mut Diagnostic) { + self.universal_regions.annotate(tcx, err) + } + + /// Returns `true` if the region `r` contains the point `p`. + /// + /// Panics if called before `solve()` executes, + pub(crate) fn region_contains(&self, r: impl ToRegionVid, p: impl ToElementIndex) -> bool { + let scc = self.constraint_sccs.scc(r.to_region_vid()); + self.scc_values.contains(scc, p) + } + + /// Returns access to the value of `r` for debugging purposes. + pub(crate) fn region_value_str(&self, r: RegionVid) -> String { + let scc = self.constraint_sccs.scc(r.to_region_vid()); + self.scc_values.region_value_str(scc) + } + + /// Returns access to the value of `r` for debugging purposes. + pub(crate) fn region_universe(&self, r: RegionVid) -> ty::UniverseIndex { + let scc = self.constraint_sccs.scc(r.to_region_vid()); + self.scc_universes[scc] + } + + /// Once region solving has completed, this function will return + /// the member constraints that were applied to the value of a given + /// region `r`. See `AppliedMemberConstraint`. + pub(crate) fn applied_member_constraints( + &self, + r: impl ToRegionVid, + ) -> &[AppliedMemberConstraint] { + let scc = self.constraint_sccs.scc(r.to_region_vid()); + binary_search_util::binary_search_slice( + &self.member_constraints_applied, + |applied| applied.member_region_scc, + &scc, + ) + } + + /// Performs region inference and report errors if we see any + /// unsatisfiable constraints. If this is a closure, returns the + /// region requirements to propagate to our creator, if any. + #[instrument(skip(self, infcx, body, polonius_output), level = "debug")] + pub(super) fn solve( + &mut self, + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + body: &Body<'tcx>, + polonius_output: Option<Rc<PoloniusOutput>>, + ) -> (Option<ClosureRegionRequirements<'tcx>>, RegionErrors<'tcx>) { + let mir_def_id = body.source.def_id(); + self.propagate_constraints(body); + + let mut errors_buffer = RegionErrors::new(); + + // If this is a closure, we can propagate unsatisfied + // `outlives_requirements` to our creator, so create a vector + // to store those. Otherwise, we'll pass in `None` to the + // functions below, which will trigger them to report errors + // eagerly. + let mut outlives_requirements = infcx.tcx.is_typeck_child(mir_def_id).then(Vec::new); + + self.check_type_tests( + infcx, + param_env, + body, + outlives_requirements.as_mut(), + &mut errors_buffer, + ); + + // In Polonius mode, the errors about missing universal region relations are in the output + // and need to be emitted or propagated. Otherwise, we need to check whether the + // constraints were too strong, and if so, emit or propagate those errors. + if infcx.tcx.sess.opts.unstable_opts.polonius { + self.check_polonius_subset_errors( + body, + outlives_requirements.as_mut(), + &mut errors_buffer, + polonius_output.expect("Polonius output is unavailable despite `-Z polonius`"), + ); + } else { + self.check_universal_regions(body, outlives_requirements.as_mut(), &mut errors_buffer); + } + + if errors_buffer.is_empty() { + self.check_member_constraints(infcx, &mut errors_buffer); + } + + let outlives_requirements = outlives_requirements.unwrap_or_default(); + + if outlives_requirements.is_empty() { + (None, errors_buffer) + } else { + let num_external_vids = self.universal_regions.num_global_and_external_regions(); + ( + Some(ClosureRegionRequirements { num_external_vids, outlives_requirements }), + errors_buffer, + ) + } + } + + /// Propagate the region constraints: this will grow the values + /// for each region variable until all the constraints are + /// satisfied. Note that some values may grow **too** large to be + /// feasible, but we check this later. + #[instrument(skip(self, _body), level = "debug")] + fn propagate_constraints(&mut self, _body: &Body<'tcx>) { + debug!("constraints={:#?}", { + let mut constraints: Vec<_> = self.constraints.outlives().iter().collect(); + constraints.sort_by_key(|c| (c.sup, c.sub)); + constraints + .into_iter() + .map(|c| (c, self.constraint_sccs.scc(c.sup), self.constraint_sccs.scc(c.sub))) + .collect::<Vec<_>>() + }); + + // To propagate constraints, we walk the DAG induced by the + // SCC. For each SCC, we visit its successors and compute + // their values, then we union all those values to get our + // own. + let constraint_sccs = self.constraint_sccs.clone(); + for scc in constraint_sccs.all_sccs() { + self.compute_value_for_scc(scc); + } + + // Sort the applied member constraints so we can binary search + // through them later. + self.member_constraints_applied.sort_by_key(|applied| applied.member_region_scc); + } + + /// Computes the value of the SCC `scc_a`, which has not yet been + /// computed, by unioning the values of its successors. + /// Assumes that all successors have been computed already + /// (which is assured by iterating over SCCs in dependency order). + #[instrument(skip(self), level = "debug")] + fn compute_value_for_scc(&mut self, scc_a: ConstraintSccIndex) { + let constraint_sccs = self.constraint_sccs.clone(); + + // Walk each SCC `B` such that `A: B`... + for &scc_b in constraint_sccs.successors(scc_a) { + debug!(?scc_b); + + // ...and add elements from `B` into `A`. One complication + // arises because of universes: If `B` contains something + // that `A` cannot name, then `A` can only contain `B` if + // it outlives static. + if self.universe_compatible(scc_b, scc_a) { + // `A` can name everything that is in `B`, so just + // merge the bits. + self.scc_values.add_region(scc_a, scc_b); + } else { + self.add_incompatible_universe(scc_a); + } + } + + // Now take member constraints into account. + let member_constraints = self.member_constraints.clone(); + for m_c_i in member_constraints.indices(scc_a) { + self.apply_member_constraint(scc_a, m_c_i, member_constraints.choice_regions(m_c_i)); + } + + debug!(value = ?self.scc_values.region_value_str(scc_a)); + } + + /// Invoked for each `R0 member of [R1..Rn]` constraint. + /// + /// `scc` is the SCC containing R0, and `choice_regions` are the + /// `R1..Rn` regions -- they are always known to be universal + /// regions (and if that's not true, we just don't attempt to + /// enforce the constraint). + /// + /// The current value of `scc` at the time the method is invoked + /// is considered a *lower bound*. If possible, we will modify + /// the constraint to set it equal to one of the option regions. + /// If we make any changes, returns true, else false. + #[instrument(skip(self, member_constraint_index), level = "debug")] + fn apply_member_constraint( + &mut self, + scc: ConstraintSccIndex, + member_constraint_index: NllMemberConstraintIndex, + choice_regions: &[ty::RegionVid], + ) -> bool { + // Create a mutable vector of the options. We'll try to winnow + // them down. + let mut choice_regions: Vec<ty::RegionVid> = choice_regions.to_vec(); + + // Convert to the SCC representative: sometimes we have inference + // variables in the member constraint that wind up equated with + // universal regions. The scc representative is the minimal numbered + // one from the corresponding scc so it will be the universal region + // if one exists. + for c_r in &mut choice_regions { + let scc = self.constraint_sccs.scc(*c_r); + *c_r = self.scc_representatives[scc]; + } + + // The 'member region' in a member constraint is part of the + // hidden type, which must be in the root universe. Therefore, + // it cannot have any placeholders in its value. + assert!(self.scc_universes[scc] == ty::UniverseIndex::ROOT); + debug_assert!( + self.scc_values.placeholders_contained_in(scc).next().is_none(), + "scc {:?} in a member constraint has placeholder value: {:?}", + scc, + self.scc_values.region_value_str(scc), + ); + + // The existing value for `scc` is a lower-bound. This will + // consist of some set `{P} + {LB}` of points `{P}` and + // lower-bound free regions `{LB}`. As each choice region `O` + // is a free region, it will outlive the points. But we can + // only consider the option `O` if `O: LB`. + choice_regions.retain(|&o_r| { + self.scc_values + .universal_regions_outlived_by(scc) + .all(|lb| self.universal_region_relations.outlives(o_r, lb)) + }); + debug!(?choice_regions, "after lb"); + + // Now find all the *upper bounds* -- that is, each UB is a + // free region that must outlive the member region `R0` (`UB: + // R0`). Therefore, we need only keep an option `O` if `UB: O` + // for all UB. + let rev_scc_graph = self.reverse_scc_graph(); + let universal_region_relations = &self.universal_region_relations; + for ub in rev_scc_graph.upper_bounds(scc) { + debug!(?ub); + choice_regions.retain(|&o_r| universal_region_relations.outlives(ub, o_r)); + } + debug!(?choice_regions, "after ub"); + + // If we ruled everything out, we're done. + if choice_regions.is_empty() { + return false; + } + + // Otherwise, we need to find the minimum remaining choice, if + // any, and take that. + debug!("choice_regions remaining are {:#?}", choice_regions); + let min = |r1: ty::RegionVid, r2: ty::RegionVid| -> Option<ty::RegionVid> { + let r1_outlives_r2 = self.universal_region_relations.outlives(r1, r2); + let r2_outlives_r1 = self.universal_region_relations.outlives(r2, r1); + match (r1_outlives_r2, r2_outlives_r1) { + (true, true) => Some(r1.min(r2)), + (true, false) => Some(r2), + (false, true) => Some(r1), + (false, false) => None, + } + }; + let mut min_choice = choice_regions[0]; + for &other_option in &choice_regions[1..] { + debug!(?min_choice, ?other_option,); + match min(min_choice, other_option) { + Some(m) => min_choice = m, + None => { + debug!(?min_choice, ?other_option, "incomparable; no min choice",); + return false; + } + } + } + + let min_choice_scc = self.constraint_sccs.scc(min_choice); + debug!(?min_choice, ?min_choice_scc); + if self.scc_values.add_region(scc, min_choice_scc) { + self.member_constraints_applied.push(AppliedMemberConstraint { + member_region_scc: scc, + min_choice, + member_constraint_index, + }); + + true + } else { + false + } + } + + /// Returns `true` if all the elements in the value of `scc_b` are nameable + /// in `scc_a`. Used during constraint propagation, and only once + /// the value of `scc_b` has been computed. + fn universe_compatible(&self, scc_b: ConstraintSccIndex, scc_a: ConstraintSccIndex) -> bool { + let universe_a = self.scc_universes[scc_a]; + + // Quick check: if scc_b's declared universe is a subset of + // scc_a's declared universe (typically, both are ROOT), then + // it cannot contain any problematic universe elements. + if universe_a.can_name(self.scc_universes[scc_b]) { + return true; + } + + // Otherwise, we have to iterate over the universe elements in + // B's value, and check whether all of them are nameable + // from universe_a + self.scc_values.placeholders_contained_in(scc_b).all(|p| universe_a.can_name(p.universe)) + } + + /// Extend `scc` so that it can outlive some placeholder region + /// from a universe it can't name; at present, the only way for + /// this to be true is if `scc` outlives `'static`. This is + /// actually stricter than necessary: ideally, we'd support bounds + /// like `for<'a: 'b`>` that might then allow us to approximate + /// `'a` with `'b` and not `'static`. But it will have to do for + /// now. + fn add_incompatible_universe(&mut self, scc: ConstraintSccIndex) { + debug!("add_incompatible_universe(scc={:?})", scc); + + let fr_static = self.universal_regions.fr_static; + self.scc_values.add_all_points(scc); + self.scc_values.add_element(scc, fr_static); + } + + /// Once regions have been propagated, this method is used to see + /// whether the "type tests" produced by typeck were satisfied; + /// type tests encode type-outlives relationships like `T: + /// 'a`. See `TypeTest` for more details. + fn check_type_tests( + &self, + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + body: &Body<'tcx>, + mut propagated_outlives_requirements: Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, + errors_buffer: &mut RegionErrors<'tcx>, + ) { + let tcx = infcx.tcx; + + // Sometimes we register equivalent type-tests that would + // result in basically the exact same error being reported to + // the user. Avoid that. + let mut deduplicate_errors = FxHashSet::default(); + + for type_test in &self.type_tests { + debug!("check_type_test: {:?}", type_test); + + let generic_ty = type_test.generic_kind.to_ty(tcx); + if self.eval_verify_bound( + infcx, + param_env, + body, + generic_ty, + type_test.lower_bound, + &type_test.verify_bound, + ) { + continue; + } + + if let Some(propagated_outlives_requirements) = &mut propagated_outlives_requirements { + if self.try_promote_type_test( + infcx, + param_env, + body, + type_test, + propagated_outlives_requirements, + ) { + continue; + } + } + + // Type-test failed. Report the error. + let erased_generic_kind = infcx.tcx.erase_regions(type_test.generic_kind); + + // Skip duplicate-ish errors. + if deduplicate_errors.insert(( + erased_generic_kind, + type_test.lower_bound, + type_test.locations, + )) { + debug!( + "check_type_test: reporting error for erased_generic_kind={:?}, \ + lower_bound_region={:?}, \ + type_test.locations={:?}", + erased_generic_kind, type_test.lower_bound, type_test.locations, + ); + + errors_buffer.push(RegionErrorKind::TypeTestError { type_test: type_test.clone() }); + } + } + } + + /// Invoked when we have some type-test (e.g., `T: 'X`) that we cannot + /// prove to be satisfied. If this is a closure, we will attempt to + /// "promote" this type-test into our `ClosureRegionRequirements` and + /// hence pass it up the creator. To do this, we have to phrase the + /// type-test in terms of external free regions, as local free + /// regions are not nameable by the closure's creator. + /// + /// Promotion works as follows: we first check that the type `T` + /// contains only regions that the creator knows about. If this is + /// true, then -- as a consequence -- we know that all regions in + /// the type `T` are free regions that outlive the closure body. If + /// false, then promotion fails. + /// + /// Once we've promoted T, we have to "promote" `'X` to some region + /// that is "external" to the closure. Generally speaking, a region + /// may be the union of some points in the closure body as well as + /// various free lifetimes. We can ignore the points in the closure + /// body: if the type T can be expressed in terms of external regions, + /// we know it outlives the points in the closure body. That + /// just leaves the free regions. + /// + /// The idea then is to lower the `T: 'X` constraint into multiple + /// bounds -- e.g., if `'X` is the union of two free lifetimes, + /// `'1` and `'2`, then we would create `T: '1` and `T: '2`. + #[instrument(level = "debug", skip(self, infcx, propagated_outlives_requirements))] + fn try_promote_type_test( + &self, + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + body: &Body<'tcx>, + type_test: &TypeTest<'tcx>, + propagated_outlives_requirements: &mut Vec<ClosureOutlivesRequirement<'tcx>>, + ) -> bool { + let tcx = infcx.tcx; + + let TypeTest { generic_kind, lower_bound, locations, verify_bound: _ } = type_test; + + let generic_ty = generic_kind.to_ty(tcx); + let Some(subject) = self.try_promote_type_test_subject(infcx, generic_ty) else { + return false; + }; + + debug!("subject = {:?}", subject); + + let r_scc = self.constraint_sccs.scc(*lower_bound); + + debug!( + "lower_bound = {:?} r_scc={:?} universe={:?}", + lower_bound, r_scc, self.scc_universes[r_scc] + ); + + // If the type test requires that `T: 'a` where `'a` is a + // placeholder from another universe, that effectively requires + // `T: 'static`, so we have to propagate that requirement. + // + // It doesn't matter *what* universe because the promoted `T` will + // always be in the root universe. + if let Some(p) = self.scc_values.placeholders_contained_in(r_scc).next() { + debug!("encountered placeholder in higher universe: {:?}, requiring 'static", p); + let static_r = self.universal_regions.fr_static; + propagated_outlives_requirements.push(ClosureOutlivesRequirement { + subject, + outlived_free_region: static_r, + blame_span: locations.span(body), + category: ConstraintCategory::Boring, + }); + + // we can return here -- the code below might push add'l constraints + // but they would all be weaker than this one. + return true; + } + + // For each region outlived by lower_bound find a non-local, + // universal region (it may be the same region) and add it to + // `ClosureOutlivesRequirement`. + for ur in self.scc_values.universal_regions_outlived_by(r_scc) { + debug!("universal_region_outlived_by ur={:?}", ur); + // Check whether we can already prove that the "subject" outlives `ur`. + // If so, we don't have to propagate this requirement to our caller. + // + // To continue the example from the function, if we are trying to promote + // a requirement that `T: 'X`, and we know that `'X = '1 + '2` (i.e., the union + // `'1` and `'2`), then in this loop `ur` will be `'1` (and `'2`). So here + // we check whether `T: '1` is something we *can* prove. If so, no need + // to propagate that requirement. + // + // This is needed because -- particularly in the case + // where `ur` is a local bound -- we are sometimes in a + // position to prove things that our caller cannot. See + // #53570 for an example. + if self.eval_verify_bound( + infcx, + param_env, + body, + generic_ty, + ur, + &type_test.verify_bound, + ) { + continue; + } + + let non_local_ub = self.universal_region_relations.non_local_upper_bounds(ur); + debug!("try_promote_type_test: non_local_ub={:?}", non_local_ub); + + // This is slightly too conservative. To show T: '1, given `'2: '1` + // and `'3: '1` we only need to prove that T: '2 *or* T: '3, but to + // avoid potential non-determinism we approximate this by requiring + // T: '1 and T: '2. + for upper_bound in non_local_ub { + debug_assert!(self.universal_regions.is_universal_region(upper_bound)); + debug_assert!(!self.universal_regions.is_local_free_region(upper_bound)); + + let requirement = ClosureOutlivesRequirement { + subject, + outlived_free_region: upper_bound, + blame_span: locations.span(body), + category: ConstraintCategory::Boring, + }; + debug!("try_promote_type_test: pushing {:#?}", requirement); + propagated_outlives_requirements.push(requirement); + } + } + true + } + + /// When we promote a type test `T: 'r`, we have to convert the + /// type `T` into something we can store in a query result (so + /// something allocated for `'tcx`). This is problematic if `ty` + /// contains regions. During the course of NLL region checking, we + /// will have replaced all of those regions with fresh inference + /// variables. To create a test subject, we want to replace those + /// inference variables with some region from the closure + /// signature -- this is not always possible, so this is a + /// fallible process. Presuming we do find a suitable region, we + /// will use it's *external name*, which will be a `RegionKind` + /// variant that can be used in query responses such as + /// `ReEarlyBound`. + #[instrument(level = "debug", skip(self, infcx))] + fn try_promote_type_test_subject( + &self, + infcx: &InferCtxt<'_, 'tcx>, + ty: Ty<'tcx>, + ) -> Option<ClosureOutlivesSubject<'tcx>> { + let tcx = infcx.tcx; + + let ty = tcx.fold_regions(ty, |r, _depth| { + let region_vid = self.to_region_vid(r); + + // The challenge if this. We have some region variable `r` + // whose value is a set of CFG points and universal + // regions. We want to find if that set is *equivalent* to + // any of the named regions found in the closure. + // + // To do so, we compute the + // `non_local_universal_upper_bound`. This will be a + // non-local, universal region that is greater than `r`. + // However, it might not be *contained* within `r`, so + // then we further check whether this bound is contained + // in `r`. If so, we can say that `r` is equivalent to the + // bound. + // + // Let's work through a few examples. For these, imagine + // that we have 3 non-local regions (I'll denote them as + // `'static`, `'a`, and `'b`, though of course in the code + // they would be represented with indices) where: + // + // - `'static: 'a` + // - `'static: 'b` + // + // First, let's assume that `r` is some existential + // variable with an inferred value `{'a, 'static}` (plus + // some CFG nodes). In this case, the non-local upper + // bound is `'static`, since that outlives `'a`. `'static` + // is also a member of `r` and hence we consider `r` + // equivalent to `'static` (and replace it with + // `'static`). + // + // Now let's consider the inferred value `{'a, 'b}`. This + // means `r` is effectively `'a | 'b`. I'm not sure if + // this can come about, actually, but assuming it did, we + // would get a non-local upper bound of `'static`. Since + // `'static` is not contained in `r`, we would fail to + // find an equivalent. + let upper_bound = self.non_local_universal_upper_bound(region_vid); + if self.region_contains(region_vid, upper_bound) { + self.definitions[upper_bound].external_name.unwrap_or(r) + } else { + // In the case of a failure, use a `ReVar` result. This will + // cause the `needs_infer` later on to return `None`. + r + } + }); + + debug!("try_promote_type_test_subject: folded ty = {:?}", ty); + + // `needs_infer` will only be true if we failed to promote some region. + if ty.needs_infer() { + return None; + } + + Some(ClosureOutlivesSubject::Ty(ty)) + } + + /// Given some universal or existential region `r`, finds a + /// non-local, universal region `r+` that outlives `r` at entry to (and + /// exit from) the closure. In the worst case, this will be + /// `'static`. + /// + /// This is used for two purposes. First, if we are propagated + /// some requirement `T: r`, we can use this method to enlarge `r` + /// to something we can encode for our creator (which only knows + /// about non-local, universal regions). It is also used when + /// encoding `T` as part of `try_promote_type_test_subject` (see + /// that fn for details). + /// + /// This is based on the result `'y` of `universal_upper_bound`, + /// except that it converts further takes the non-local upper + /// bound of `'y`, so that the final result is non-local. + fn non_local_universal_upper_bound(&self, r: RegionVid) -> RegionVid { + debug!("non_local_universal_upper_bound(r={:?}={})", r, self.region_value_str(r)); + + let lub = self.universal_upper_bound(r); + + // Grow further to get smallest universal region known to + // creator. + let non_local_lub = self.universal_region_relations.non_local_upper_bound(lub); + + debug!("non_local_universal_upper_bound: non_local_lub={:?}", non_local_lub); + + non_local_lub + } + + /// Returns a universally quantified region that outlives the + /// value of `r` (`r` may be existentially or universally + /// quantified). + /// + /// Since `r` is (potentially) an existential region, it has some + /// value which may include (a) any number of points in the CFG + /// and (b) any number of `end('x)` elements of universally + /// quantified regions. To convert this into a single universal + /// region we do as follows: + /// + /// - Ignore the CFG points in `'r`. All universally quantified regions + /// include the CFG anyhow. + /// - For each `end('x)` element in `'r`, compute the mutual LUB, yielding + /// a result `'y`. + #[instrument(skip(self), level = "debug")] + pub(crate) fn universal_upper_bound(&self, r: RegionVid) -> RegionVid { + debug!(r = %self.region_value_str(r)); + + // Find the smallest universal region that contains all other + // universal regions within `region`. + let mut lub = self.universal_regions.fr_fn_body; + let r_scc = self.constraint_sccs.scc(r); + for ur in self.scc_values.universal_regions_outlived_by(r_scc) { + lub = self.universal_region_relations.postdom_upper_bound(lub, ur); + } + + debug!(?lub); + + lub + } + + /// Like `universal_upper_bound`, but returns an approximation more suitable + /// for diagnostics. If `r` contains multiple disjoint universal regions + /// (e.g. 'a and 'b in `fn foo<'a, 'b> { ... }`, we pick the lower-numbered region. + /// This corresponds to picking named regions over unnamed regions + /// (e.g. picking early-bound regions over a closure late-bound region). + /// + /// This means that the returned value may not be a true upper bound, since + /// only 'static is known to outlive disjoint universal regions. + /// Therefore, this method should only be used in diagnostic code, + /// where displaying *some* named universal region is better than + /// falling back to 'static. + pub(crate) fn approx_universal_upper_bound(&self, r: RegionVid) -> RegionVid { + debug!("approx_universal_upper_bound(r={:?}={})", r, self.region_value_str(r)); + + // Find the smallest universal region that contains all other + // universal regions within `region`. + let mut lub = self.universal_regions.fr_fn_body; + let r_scc = self.constraint_sccs.scc(r); + let static_r = self.universal_regions.fr_static; + for ur in self.scc_values.universal_regions_outlived_by(r_scc) { + let new_lub = self.universal_region_relations.postdom_upper_bound(lub, ur); + debug!("approx_universal_upper_bound: ur={:?} lub={:?} new_lub={:?}", ur, lub, new_lub); + // The upper bound of two non-static regions is static: this + // means we know nothing about the relationship between these + // two regions. Pick a 'better' one to use when constructing + // a diagnostic + if ur != static_r && lub != static_r && new_lub == static_r { + // Prefer the region with an `external_name` - this + // indicates that the region is early-bound, so working with + // it can produce a nicer error. + if self.region_definition(ur).external_name.is_some() { + lub = ur; + } else if self.region_definition(lub).external_name.is_some() { + // Leave lub unchanged + } else { + // If we get here, we don't have any reason to prefer + // one region over the other. Just pick the + // one with the lower index for now. + lub = std::cmp::min(ur, lub); + } + } else { + lub = new_lub; + } + } + + debug!("approx_universal_upper_bound: r={:?} lub={:?}", r, lub); + + lub + } + + /// Tests if `test` is true when applied to `lower_bound` at + /// `point`. + fn eval_verify_bound( + &self, + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + body: &Body<'tcx>, + generic_ty: Ty<'tcx>, + lower_bound: RegionVid, + verify_bound: &VerifyBound<'tcx>, + ) -> bool { + debug!("eval_verify_bound(lower_bound={:?}, verify_bound={:?})", lower_bound, verify_bound); + + match verify_bound { + VerifyBound::IfEq(verify_if_eq_b) => { + self.eval_if_eq(infcx, param_env, generic_ty, lower_bound, *verify_if_eq_b) + } + + VerifyBound::IsEmpty => { + let lower_bound_scc = self.constraint_sccs.scc(lower_bound); + self.scc_values.elements_contained_in(lower_bound_scc).next().is_none() + } + + VerifyBound::OutlivedBy(r) => { + let r_vid = self.to_region_vid(*r); + self.eval_outlives(r_vid, lower_bound) + } + + VerifyBound::AnyBound(verify_bounds) => verify_bounds.iter().any(|verify_bound| { + self.eval_verify_bound( + infcx, + param_env, + body, + generic_ty, + lower_bound, + verify_bound, + ) + }), + + VerifyBound::AllBounds(verify_bounds) => verify_bounds.iter().all(|verify_bound| { + self.eval_verify_bound( + infcx, + param_env, + body, + generic_ty, + lower_bound, + verify_bound, + ) + }), + } + } + + fn eval_if_eq( + &self, + infcx: &InferCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + generic_ty: Ty<'tcx>, + lower_bound: RegionVid, + verify_if_eq_b: ty::Binder<'tcx, VerifyIfEq<'tcx>>, + ) -> bool { + let generic_ty = self.normalize_to_scc_representatives(infcx.tcx, generic_ty); + let verify_if_eq_b = self.normalize_to_scc_representatives(infcx.tcx, verify_if_eq_b); + match test_type_match::extract_verify_if_eq( + infcx.tcx, + param_env, + &verify_if_eq_b, + generic_ty, + ) { + Some(r) => { + let r_vid = self.to_region_vid(r); + self.eval_outlives(r_vid, lower_bound) + } + None => false, + } + } + + /// This is a conservative normalization procedure. It takes every + /// free region in `value` and replaces it with the + /// "representative" of its SCC (see `scc_representatives` field). + /// We are guaranteed that if two values normalize to the same + /// thing, then they are equal; this is a conservative check in + /// that they could still be equal even if they normalize to + /// different results. (For example, there might be two regions + /// with the same value that are not in the same SCC). + /// + /// N.B., this is not an ideal approach and I would like to revisit + /// it. However, it works pretty well in practice. In particular, + /// this is needed to deal with projection outlives bounds like + /// + /// ```text + /// <T as Foo<'0>>::Item: '1 + /// ``` + /// + /// In particular, this routine winds up being important when + /// there are bounds like `where <T as Foo<'a>>::Item: 'b` in the + /// environment. In this case, if we can show that `'0 == 'a`, + /// and that `'b: '1`, then we know that the clause is + /// satisfied. In such cases, particularly due to limitations of + /// the trait solver =), we usually wind up with a where-clause like + /// `T: Foo<'a>` in scope, which thus forces `'0 == 'a` to be added as + /// a constraint, and thus ensures that they are in the same SCC. + /// + /// So why can't we do a more correct routine? Well, we could + /// *almost* use the `relate_tys` code, but the way it is + /// currently setup it creates inference variables to deal with + /// higher-ranked things and so forth, and right now the inference + /// context is not permitted to make more inference variables. So + /// we use this kind of hacky solution. + fn normalize_to_scc_representatives<T>(&self, tcx: TyCtxt<'tcx>, value: T) -> T + where + T: TypeFoldable<'tcx>, + { + tcx.fold_regions(value, |r, _db| { + let vid = self.to_region_vid(r); + let scc = self.constraint_sccs.scc(vid); + let repr = self.scc_representatives[scc]; + tcx.mk_region(ty::ReVar(repr)) + }) + } + + // Evaluate whether `sup_region == sub_region`. + fn eval_equal(&self, r1: RegionVid, r2: RegionVid) -> bool { + self.eval_outlives(r1, r2) && self.eval_outlives(r2, r1) + } + + // Evaluate whether `sup_region: sub_region`. + #[instrument(skip(self), level = "debug")] + fn eval_outlives(&self, sup_region: RegionVid, sub_region: RegionVid) -> bool { + debug!( + "eval_outlives: sup_region's value = {:?} universal={:?}", + self.region_value_str(sup_region), + self.universal_regions.is_universal_region(sup_region), + ); + debug!( + "eval_outlives: sub_region's value = {:?} universal={:?}", + self.region_value_str(sub_region), + self.universal_regions.is_universal_region(sub_region), + ); + + let sub_region_scc = self.constraint_sccs.scc(sub_region); + let sup_region_scc = self.constraint_sccs.scc(sup_region); + + // If we are checking that `'sup: 'sub`, and `'sub` contains + // some placeholder that `'sup` cannot name, then this is only + // true if `'sup` outlives static. + if !self.universe_compatible(sub_region_scc, sup_region_scc) { + debug!( + "eval_outlives: sub universe `{sub_region_scc:?}` is not nameable \ + by super `{sup_region_scc:?}`, promoting to static", + ); + + return self.eval_outlives(sup_region, self.universal_regions.fr_static); + } + + // Both the `sub_region` and `sup_region` consist of the union + // of some number of universal regions (along with the union + // of various points in the CFG; ignore those points for + // now). Therefore, the sup-region outlives the sub-region if, + // for each universal region R1 in the sub-region, there + // exists some region R2 in the sup-region that outlives R1. + let universal_outlives = + self.scc_values.universal_regions_outlived_by(sub_region_scc).all(|r1| { + self.scc_values + .universal_regions_outlived_by(sup_region_scc) + .any(|r2| self.universal_region_relations.outlives(r2, r1)) + }); + + if !universal_outlives { + debug!( + "eval_outlives: returning false because sub region contains a universal region not present in super" + ); + return false; + } + + // Now we have to compare all the points in the sub region and make + // sure they exist in the sup region. + + if self.universal_regions.is_universal_region(sup_region) { + // Micro-opt: universal regions contain all points. + debug!( + "eval_outlives: returning true because super is universal and hence contains all points" + ); + return true; + } + + let result = self.scc_values.contains_points(sup_region_scc, sub_region_scc); + debug!("returning {} because of comparison between points in sup/sub", result); + result + } + + /// Once regions have been propagated, this method is used to see + /// whether any of the constraints were too strong. In particular, + /// we want to check for a case where a universally quantified + /// region exceeded its bounds. Consider: + /// ```compile_fail,E0312 + /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x } + /// ``` + /// In this case, returning `x` requires `&'a u32 <: &'b u32` + /// and hence we establish (transitively) a constraint that + /// `'a: 'b`. The `propagate_constraints` code above will + /// therefore add `end('a)` into the region for `'b` -- but we + /// have no evidence that `'b` outlives `'a`, so we want to report + /// an error. + /// + /// If `propagated_outlives_requirements` is `Some`, then we will + /// push unsatisfied obligations into there. Otherwise, we'll + /// report them as errors. + fn check_universal_regions( + &self, + body: &Body<'tcx>, + mut propagated_outlives_requirements: Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, + errors_buffer: &mut RegionErrors<'tcx>, + ) { + for (fr, fr_definition) in self.definitions.iter_enumerated() { + match fr_definition.origin { + NllRegionVariableOrigin::FreeRegion => { + // Go through each of the universal regions `fr` and check that + // they did not grow too large, accumulating any requirements + // for our caller into the `outlives_requirements` vector. + self.check_universal_region( + body, + fr, + &mut propagated_outlives_requirements, + errors_buffer, + ); + } + + NllRegionVariableOrigin::Placeholder(placeholder) => { + self.check_bound_universal_region(fr, placeholder, errors_buffer); + } + + NllRegionVariableOrigin::Existential { .. } => { + // nothing to check here + } + } + } + } + + /// Checks if Polonius has found any unexpected free region relations. + /// + /// In Polonius terms, a "subset error" (or "illegal subset relation error") is the equivalent + /// of NLL's "checking if any region constraints were too strong": a placeholder origin `'a` + /// was unexpectedly found to be a subset of another placeholder origin `'b`, and means in NLL + /// terms that the "longer free region" `'a` outlived the "shorter free region" `'b`. + /// + /// More details can be found in this blog post by Niko: + /// <https://smallcultfollowing.com/babysteps/blog/2019/01/17/polonius-and-region-errors/> + /// + /// In the canonical example + /// ```compile_fail,E0312 + /// fn foo<'a, 'b>(x: &'a u32) -> &'b u32 { x } + /// ``` + /// returning `x` requires `&'a u32 <: &'b u32` and hence we establish (transitively) a + /// constraint that `'a: 'b`. It is an error that we have no evidence that this + /// constraint holds. + /// + /// If `propagated_outlives_requirements` is `Some`, then we will + /// push unsatisfied obligations into there. Otherwise, we'll + /// report them as errors. + fn check_polonius_subset_errors( + &self, + body: &Body<'tcx>, + mut propagated_outlives_requirements: Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, + errors_buffer: &mut RegionErrors<'tcx>, + polonius_output: Rc<PoloniusOutput>, + ) { + debug!( + "check_polonius_subset_errors: {} subset_errors", + polonius_output.subset_errors.len() + ); + + // Similarly to `check_universal_regions`: a free region relation, which was not explicitly + // declared ("known") was found by Polonius, so emit an error, or propagate the + // requirements for our caller into the `propagated_outlives_requirements` vector. + // + // Polonius doesn't model regions ("origins") as CFG-subsets or durations, but the + // `longer_fr` and `shorter_fr` terminology will still be used here, for consistency with + // the rest of the NLL infrastructure. The "subset origin" is the "longer free region", + // and the "superset origin" is the outlived "shorter free region". + // + // Note: Polonius will produce a subset error at every point where the unexpected + // `longer_fr`'s "placeholder loan" is contained in the `shorter_fr`. This can be helpful + // for diagnostics in the future, e.g. to point more precisely at the key locations + // requiring this constraint to hold. However, the error and diagnostics code downstream + // expects that these errors are not duplicated (and that they are in a certain order). + // Otherwise, diagnostics messages such as the ones giving names like `'1` to elided or + // anonymous lifetimes for example, could give these names differently, while others like + // the outlives suggestions or the debug output from `#[rustc_regions]` would be + // duplicated. The polonius subset errors are deduplicated here, while keeping the + // CFG-location ordering. + let mut subset_errors: Vec<_> = polonius_output + .subset_errors + .iter() + .flat_map(|(_location, subset_errors)| subset_errors.iter()) + .collect(); + subset_errors.sort(); + subset_errors.dedup(); + + for (longer_fr, shorter_fr) in subset_errors.into_iter() { + debug!( + "check_polonius_subset_errors: subset_error longer_fr={:?},\ + shorter_fr={:?}", + longer_fr, shorter_fr + ); + + let propagated = self.try_propagate_universal_region_error( + *longer_fr, + *shorter_fr, + body, + &mut propagated_outlives_requirements, + ); + if propagated == RegionRelationCheckResult::Error { + errors_buffer.push(RegionErrorKind::RegionError { + longer_fr: *longer_fr, + shorter_fr: *shorter_fr, + fr_origin: NllRegionVariableOrigin::FreeRegion, + is_reported: true, + }); + } + } + + // Handle the placeholder errors as usual, until the chalk-rustc-polonius triumvirate has + // a more complete picture on how to separate this responsibility. + for (fr, fr_definition) in self.definitions.iter_enumerated() { + match fr_definition.origin { + NllRegionVariableOrigin::FreeRegion => { + // handled by polonius above + } + + NllRegionVariableOrigin::Placeholder(placeholder) => { + self.check_bound_universal_region(fr, placeholder, errors_buffer); + } + + NllRegionVariableOrigin::Existential { .. } => { + // nothing to check here + } + } + } + } + + /// Checks the final value for the free region `fr` to see if it + /// grew too large. In particular, examine what `end(X)` points + /// wound up in `fr`'s final value; for each `end(X)` where `X != + /// fr`, we want to check that `fr: X`. If not, that's either an + /// error, or something we have to propagate to our creator. + /// + /// Things that are to be propagated are accumulated into the + /// `outlives_requirements` vector. + #[instrument( + skip(self, body, propagated_outlives_requirements, errors_buffer), + level = "debug" + )] + fn check_universal_region( + &self, + body: &Body<'tcx>, + longer_fr: RegionVid, + propagated_outlives_requirements: &mut Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, + errors_buffer: &mut RegionErrors<'tcx>, + ) { + let longer_fr_scc = self.constraint_sccs.scc(longer_fr); + + // Because this free region must be in the ROOT universe, we + // know it cannot contain any bound universes. + assert!(self.scc_universes[longer_fr_scc] == ty::UniverseIndex::ROOT); + debug_assert!(self.scc_values.placeholders_contained_in(longer_fr_scc).next().is_none()); + + // Only check all of the relations for the main representative of each + // SCC, otherwise just check that we outlive said representative. This + // reduces the number of redundant relations propagated out of + // closures. + // Note that the representative will be a universal region if there is + // one in this SCC, so we will always check the representative here. + let representative = self.scc_representatives[longer_fr_scc]; + if representative != longer_fr { + if let RegionRelationCheckResult::Error = self.check_universal_region_relation( + longer_fr, + representative, + body, + propagated_outlives_requirements, + ) { + errors_buffer.push(RegionErrorKind::RegionError { + longer_fr, + shorter_fr: representative, + fr_origin: NllRegionVariableOrigin::FreeRegion, + is_reported: true, + }); + } + return; + } + + // Find every region `o` such that `fr: o` + // (because `fr` includes `end(o)`). + let mut error_reported = false; + for shorter_fr in self.scc_values.universal_regions_outlived_by(longer_fr_scc) { + if let RegionRelationCheckResult::Error = self.check_universal_region_relation( + longer_fr, + shorter_fr, + body, + propagated_outlives_requirements, + ) { + // We only report the first region error. Subsequent errors are hidden so as + // not to overwhelm the user, but we do record them so as to potentially print + // better diagnostics elsewhere... + errors_buffer.push(RegionErrorKind::RegionError { + longer_fr, + shorter_fr, + fr_origin: NllRegionVariableOrigin::FreeRegion, + is_reported: !error_reported, + }); + + error_reported = true; + } + } + } + + /// Checks that we can prove that `longer_fr: shorter_fr`. If we can't we attempt to propagate + /// the constraint outward (e.g. to a closure environment), but if that fails, there is an + /// error. + fn check_universal_region_relation( + &self, + longer_fr: RegionVid, + shorter_fr: RegionVid, + body: &Body<'tcx>, + propagated_outlives_requirements: &mut Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, + ) -> RegionRelationCheckResult { + // If it is known that `fr: o`, carry on. + if self.universal_region_relations.outlives(longer_fr, shorter_fr) { + RegionRelationCheckResult::Ok + } else { + // If we are not in a context where we can't propagate errors, or we + // could not shrink `fr` to something smaller, then just report an + // error. + // + // Note: in this case, we use the unapproximated regions to report the + // error. This gives better error messages in some cases. + self.try_propagate_universal_region_error( + longer_fr, + shorter_fr, + body, + propagated_outlives_requirements, + ) + } + } + + /// Attempt to propagate a region error (e.g. `'a: 'b`) that is not met to a closure's + /// creator. If we cannot, then the caller should report an error to the user. + fn try_propagate_universal_region_error( + &self, + longer_fr: RegionVid, + shorter_fr: RegionVid, + body: &Body<'tcx>, + propagated_outlives_requirements: &mut Option<&mut Vec<ClosureOutlivesRequirement<'tcx>>>, + ) -> RegionRelationCheckResult { + if let Some(propagated_outlives_requirements) = propagated_outlives_requirements { + // Shrink `longer_fr` until we find a non-local region (if we do). + // We'll call it `fr-` -- it's ever so slightly smaller than + // `longer_fr`. + if let Some(fr_minus) = self.universal_region_relations.non_local_lower_bound(longer_fr) + { + debug!("try_propagate_universal_region_error: fr_minus={:?}", fr_minus); + + let blame_span_category = self.find_outlives_blame_span( + body, + longer_fr, + NllRegionVariableOrigin::FreeRegion, + shorter_fr, + ); + + // Grow `shorter_fr` until we find some non-local regions. (We + // always will.) We'll call them `shorter_fr+` -- they're ever + // so slightly larger than `shorter_fr`. + let shorter_fr_plus = + self.universal_region_relations.non_local_upper_bounds(shorter_fr); + debug!( + "try_propagate_universal_region_error: shorter_fr_plus={:?}", + shorter_fr_plus + ); + for fr in shorter_fr_plus { + // Push the constraint `fr-: shorter_fr+` + propagated_outlives_requirements.push(ClosureOutlivesRequirement { + subject: ClosureOutlivesSubject::Region(fr_minus), + outlived_free_region: fr, + blame_span: blame_span_category.1.span, + category: blame_span_category.0, + }); + } + return RegionRelationCheckResult::Propagated; + } + } + + RegionRelationCheckResult::Error + } + + fn check_bound_universal_region( + &self, + longer_fr: RegionVid, + placeholder: ty::PlaceholderRegion, + errors_buffer: &mut RegionErrors<'tcx>, + ) { + debug!("check_bound_universal_region(fr={:?}, placeholder={:?})", longer_fr, placeholder,); + + let longer_fr_scc = self.constraint_sccs.scc(longer_fr); + debug!("check_bound_universal_region: longer_fr_scc={:?}", longer_fr_scc,); + + // If we have some bound universal region `'a`, then the only + // elements it can contain is itself -- we don't know anything + // else about it! + let Some(error_element) = ({ + self.scc_values.elements_contained_in(longer_fr_scc).find(|element| match element { + RegionElement::Location(_) => true, + RegionElement::RootUniversalRegion(_) => true, + RegionElement::PlaceholderRegion(placeholder1) => placeholder != *placeholder1, + }) + }) else { + return; + }; + debug!("check_bound_universal_region: error_element = {:?}", error_element); + + // Find the region that introduced this `error_element`. + errors_buffer.push(RegionErrorKind::BoundUniversalRegionError { + longer_fr, + error_element, + placeholder, + }); + } + + fn check_member_constraints( + &self, + infcx: &InferCtxt<'_, 'tcx>, + errors_buffer: &mut RegionErrors<'tcx>, + ) { + let member_constraints = self.member_constraints.clone(); + for m_c_i in member_constraints.all_indices() { + debug!("check_member_constraint(m_c_i={:?})", m_c_i); + let m_c = &member_constraints[m_c_i]; + let member_region_vid = m_c.member_region_vid; + debug!( + "check_member_constraint: member_region_vid={:?} with value {}", + member_region_vid, + self.region_value_str(member_region_vid), + ); + let choice_regions = member_constraints.choice_regions(m_c_i); + debug!("check_member_constraint: choice_regions={:?}", choice_regions); + + // Did the member region wind up equal to any of the option regions? + if let Some(o) = + choice_regions.iter().find(|&&o_r| self.eval_equal(o_r, m_c.member_region_vid)) + { + debug!("check_member_constraint: evaluated as equal to {:?}", o); + continue; + } + + // If not, report an error. + let member_region = infcx.tcx.mk_region(ty::ReVar(member_region_vid)); + errors_buffer.push(RegionErrorKind::UnexpectedHiddenRegion { + span: m_c.definition_span, + hidden_ty: m_c.hidden_ty, + key: m_c.key, + member_region, + }); + } + } + + /// We have a constraint `fr1: fr2` that is not satisfied, where + /// `fr2` represents some universal region. Here, `r` is some + /// region where we know that `fr1: r` and this function has the + /// job of determining whether `r` is "to blame" for the fact that + /// `fr1: fr2` is required. + /// + /// This is true under two conditions: + /// + /// - `r == fr2` + /// - `fr2` is `'static` and `r` is some placeholder in a universe + /// that cannot be named by `fr1`; in that case, we will require + /// that `fr1: 'static` because it is the only way to `fr1: r` to + /// be satisfied. (See `add_incompatible_universe`.) + pub(crate) fn provides_universal_region( + &self, + r: RegionVid, + fr1: RegionVid, + fr2: RegionVid, + ) -> bool { + debug!("provides_universal_region(r={:?}, fr1={:?}, fr2={:?})", r, fr1, fr2); + let result = { + r == fr2 || { + fr2 == self.universal_regions.fr_static && self.cannot_name_placeholder(fr1, r) + } + }; + debug!("provides_universal_region: result = {:?}", result); + result + } + + /// If `r2` represents a placeholder region, then this returns + /// `true` if `r1` cannot name that placeholder in its + /// value; otherwise, returns `false`. + pub(crate) fn cannot_name_placeholder(&self, r1: RegionVid, r2: RegionVid) -> bool { + debug!("cannot_name_value_of(r1={:?}, r2={:?})", r1, r2); + + match self.definitions[r2].origin { + NllRegionVariableOrigin::Placeholder(placeholder) => { + let universe1 = self.definitions[r1].universe; + debug!( + "cannot_name_value_of: universe1={:?} placeholder={:?}", + universe1, placeholder + ); + universe1.cannot_name(placeholder.universe) + } + + NllRegionVariableOrigin::FreeRegion | NllRegionVariableOrigin::Existential { .. } => { + false + } + } + } + + pub(crate) fn retrieve_closure_constraint_info( + &self, + _body: &Body<'tcx>, + constraint: &OutlivesConstraint<'tcx>, + ) -> BlameConstraint<'tcx> { + let loc = match constraint.locations { + Locations::All(span) => { + return BlameConstraint { + category: constraint.category, + from_closure: false, + cause: ObligationCause::dummy_with_span(span), + variance_info: constraint.variance_info, + }; + } + Locations::Single(loc) => loc, + }; + + let opt_span_category = + self.closure_bounds_mapping[&loc].get(&(constraint.sup, constraint.sub)); + opt_span_category + .map(|&(category, span)| BlameConstraint { + category, + from_closure: true, + cause: ObligationCause::dummy_with_span(span), + variance_info: constraint.variance_info, + }) + .unwrap_or(BlameConstraint { + category: constraint.category, + from_closure: false, + cause: ObligationCause::dummy_with_span(constraint.span), + variance_info: constraint.variance_info, + }) + } + + /// Finds a good `ObligationCause` to blame for the fact that `fr1` outlives `fr2`. + pub(crate) fn find_outlives_blame_span( + &self, + body: &Body<'tcx>, + fr1: RegionVid, + fr1_origin: NllRegionVariableOrigin, + fr2: RegionVid, + ) -> (ConstraintCategory<'tcx>, ObligationCause<'tcx>) { + let BlameConstraint { category, cause, .. } = + self.best_blame_constraint(body, fr1, fr1_origin, |r| { + self.provides_universal_region(r, fr1, fr2) + }); + (category, cause) + } + + /// Walks the graph of constraints (where `'a: 'b` is considered + /// an edge `'a -> 'b`) to find all paths from `from_region` to + /// `to_region`. The paths are accumulated into the vector + /// `results`. The paths are stored as a series of + /// `ConstraintIndex` values -- in other words, a list of *edges*. + /// + /// Returns: a series of constraints as well as the region `R` + /// that passed the target test. + pub(crate) fn find_constraint_paths_between_regions( + &self, + from_region: RegionVid, + target_test: impl Fn(RegionVid) -> bool, + ) -> Option<(Vec<OutlivesConstraint<'tcx>>, RegionVid)> { + let mut context = IndexVec::from_elem(Trace::NotVisited, &self.definitions); + context[from_region] = Trace::StartRegion; + + // Use a deque so that we do a breadth-first search. We will + // stop at the first match, which ought to be the shortest + // path (fewest constraints). + let mut deque = VecDeque::new(); + deque.push_back(from_region); + + while let Some(r) = deque.pop_front() { + debug!( + "find_constraint_paths_between_regions: from_region={:?} r={:?} value={}", + from_region, + r, + self.region_value_str(r), + ); + + // Check if we reached the region we were looking for. If so, + // we can reconstruct the path that led to it and return it. + if target_test(r) { + let mut result = vec![]; + let mut p = r; + loop { + match context[p].clone() { + Trace::NotVisited => { + bug!("found unvisited region {:?} on path to {:?}", p, r) + } + + Trace::FromOutlivesConstraint(c) => { + p = c.sup; + result.push(c); + } + + Trace::StartRegion => { + result.reverse(); + return Some((result, r)); + } + } + } + } + + // Otherwise, walk over the outgoing constraints and + // enqueue any regions we find, keeping track of how we + // reached them. + + // A constraint like `'r: 'x` can come from our constraint + // graph. + let fr_static = self.universal_regions.fr_static; + let outgoing_edges_from_graph = + self.constraint_graph.outgoing_edges(r, &self.constraints, fr_static); + + // Always inline this closure because it can be hot. + let mut handle_constraint = #[inline(always)] + |constraint: OutlivesConstraint<'tcx>| { + debug_assert_eq!(constraint.sup, r); + let sub_region = constraint.sub; + if let Trace::NotVisited = context[sub_region] { + context[sub_region] = Trace::FromOutlivesConstraint(constraint); + deque.push_back(sub_region); + } + }; + + // This loop can be hot. + for constraint in outgoing_edges_from_graph { + handle_constraint(constraint); + } + + // Member constraints can also give rise to `'r: 'x` edges that + // were not part of the graph initially, so watch out for those. + // (But they are extremely rare; this loop is very cold.) + for constraint in self.applied_member_constraints(r) { + let p_c = &self.member_constraints[constraint.member_constraint_index]; + let constraint = OutlivesConstraint { + sup: r, + sub: constraint.min_choice, + locations: Locations::All(p_c.definition_span), + span: p_c.definition_span, + category: ConstraintCategory::OpaqueType, + variance_info: ty::VarianceDiagInfo::default(), + }; + handle_constraint(constraint); + } + } + + None + } + + /// Finds some region R such that `fr1: R` and `R` is live at `elem`. + #[instrument(skip(self), level = "trace")] + pub(crate) fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid { + trace!(scc = ?self.constraint_sccs.scc(fr1)); + trace!(universe = ?self.scc_universes[self.constraint_sccs.scc(fr1)]); + self.find_constraint_paths_between_regions(fr1, |r| { + // First look for some `r` such that `fr1: r` and `r` is live at `elem` + trace!(?r, liveness_constraints=?self.liveness_constraints.region_value_str(r)); + self.liveness_constraints.contains(r, elem) + }) + .or_else(|| { + // If we fail to find that, we may find some `r` such that + // `fr1: r` and `r` is a placeholder from some universe + // `fr1` cannot name. This would force `fr1` to be + // `'static`. + self.find_constraint_paths_between_regions(fr1, |r| { + self.cannot_name_placeholder(fr1, r) + }) + }) + .or_else(|| { + // If we fail to find THAT, it may be that `fr1` is a + // placeholder that cannot "fit" into its SCC. In that + // case, there should be some `r` where `fr1: r` and `fr1` is a + // placeholder that `r` cannot name. We can blame that + // edge. + // + // Remember that if `R1: R2`, then the universe of R1 + // must be able to name the universe of R2, because R2 will + // be at least `'empty(Universe(R2))`, and `R1` must be at + // larger than that. + self.find_constraint_paths_between_regions(fr1, |r| { + self.cannot_name_placeholder(r, fr1) + }) + }) + .map(|(_path, r)| r) + .unwrap() + } + + /// Get the region outlived by `longer_fr` and live at `element`. + pub(crate) fn region_from_element( + &self, + longer_fr: RegionVid, + element: &RegionElement, + ) -> RegionVid { + match *element { + RegionElement::Location(l) => self.find_sub_region_live_at(longer_fr, l), + RegionElement::RootUniversalRegion(r) => r, + RegionElement::PlaceholderRegion(error_placeholder) => self + .definitions + .iter_enumerated() + .find_map(|(r, definition)| match definition.origin { + NllRegionVariableOrigin::Placeholder(p) if p == error_placeholder => Some(r), + _ => None, + }) + .unwrap(), + } + } + + /// Get the region definition of `r`. + pub(crate) fn region_definition(&self, r: RegionVid) -> &RegionDefinition<'tcx> { + &self.definitions[r] + } + + /// Check if the SCC of `r` contains `upper`. + pub(crate) fn upper_bound_in_region_scc(&self, r: RegionVid, upper: RegionVid) -> bool { + let r_scc = self.constraint_sccs.scc(r); + self.scc_values.contains(r_scc, upper) + } + + pub(crate) fn universal_regions(&self) -> &UniversalRegions<'tcx> { + self.universal_regions.as_ref() + } + + /// Tries to find the best constraint to blame for the fact that + /// `R: from_region`, where `R` is some region that meets + /// `target_test`. This works by following the constraint graph, + /// creating a constraint path that forces `R` to outlive + /// `from_region`, and then finding the best choices within that + /// path to blame. + pub(crate) fn best_blame_constraint( + &self, + body: &Body<'tcx>, + from_region: RegionVid, + from_region_origin: NllRegionVariableOrigin, + target_test: impl Fn(RegionVid) -> bool, + ) -> BlameConstraint<'tcx> { + debug!( + "best_blame_constraint(from_region={:?}, from_region_origin={:?})", + from_region, from_region_origin + ); + + // Find all paths + let (path, target_region) = + self.find_constraint_paths_between_regions(from_region, target_test).unwrap(); + debug!( + "best_blame_constraint: path={:#?}", + path.iter() + .map(|c| format!( + "{:?} ({:?}: {:?})", + c, + self.constraint_sccs.scc(c.sup), + self.constraint_sccs.scc(c.sub), + )) + .collect::<Vec<_>>() + ); + + // We try to avoid reporting a `ConstraintCategory::Predicate` as our best constraint. + // Instead, we use it to produce an improved `ObligationCauseCode`. + // FIXME - determine what we should do if we encounter multiple `ConstraintCategory::Predicate` + // constraints. Currently, we just pick the first one. + let cause_code = path + .iter() + .find_map(|constraint| { + if let ConstraintCategory::Predicate(predicate_span) = constraint.category { + // We currently do not store the `DefId` in the `ConstraintCategory` + // for performances reasons. The error reporting code used by NLL only + // uses the span, so this doesn't cause any problems at the moment. + Some(ObligationCauseCode::BindingObligation( + CRATE_DEF_ID.to_def_id(), + predicate_span, + )) + } else { + None + } + }) + .unwrap_or_else(|| ObligationCauseCode::MiscObligation); + + // Classify each of the constraints along the path. + let mut categorized_path: Vec<BlameConstraint<'tcx>> = path + .iter() + .map(|constraint| { + if constraint.category == ConstraintCategory::ClosureBounds { + self.retrieve_closure_constraint_info(body, &constraint) + } else { + BlameConstraint { + category: constraint.category, + from_closure: false, + cause: ObligationCause::new( + constraint.span, + CRATE_HIR_ID, + cause_code.clone(), + ), + variance_info: constraint.variance_info, + } + } + }) + .collect(); + debug!("best_blame_constraint: categorized_path={:#?}", categorized_path); + + // To find the best span to cite, we first try to look for the + // final constraint that is interesting and where the `sup` is + // not unified with the ultimate target region. The reason + // for this is that we have a chain of constraints that lead + // from the source to the target region, something like: + // + // '0: '1 ('0 is the source) + // '1: '2 + // '2: '3 + // '3: '4 + // '4: '5 + // '5: '6 ('6 is the target) + // + // Some of those regions are unified with `'6` (in the same + // SCC). We want to screen those out. After that point, the + // "closest" constraint we have to the end is going to be the + // most likely to be the point where the value escapes -- but + // we still want to screen for an "interesting" point to + // highlight (e.g., a call site or something). + let target_scc = self.constraint_sccs.scc(target_region); + let mut range = 0..path.len(); + + // As noted above, when reporting an error, there is typically a chain of constraints + // leading from some "source" region which must outlive some "target" region. + // In most cases, we prefer to "blame" the constraints closer to the target -- + // but there is one exception. When constraints arise from higher-ranked subtyping, + // we generally prefer to blame the source value, + // as the "target" in this case tends to be some type annotation that the user gave. + // Therefore, if we find that the region origin is some instantiation + // of a higher-ranked region, we start our search from the "source" point + // rather than the "target", and we also tweak a few other things. + // + // An example might be this bit of Rust code: + // + // ```rust + // let x: fn(&'static ()) = |_| {}; + // let y: for<'a> fn(&'a ()) = x; + // ``` + // + // In MIR, this will be converted into a combination of assignments and type ascriptions. + // In particular, the 'static is imposed through a type ascription: + // + // ```rust + // x = ...; + // AscribeUserType(x, fn(&'static ()) + // y = x; + // ``` + // + // We wind up ultimately with constraints like + // + // ```rust + // !a: 'temp1 // from the `y = x` statement + // 'temp1: 'temp2 + // 'temp2: 'static // from the AscribeUserType + // ``` + // + // and here we prefer to blame the source (the y = x statement). + let blame_source = match from_region_origin { + NllRegionVariableOrigin::FreeRegion + | NllRegionVariableOrigin::Existential { from_forall: false } => true, + NllRegionVariableOrigin::Placeholder(_) + | NllRegionVariableOrigin::Existential { from_forall: true } => false, + }; + + let find_region = |i: &usize| { + let constraint = &path[*i]; + + let constraint_sup_scc = self.constraint_sccs.scc(constraint.sup); + + if blame_source { + match categorized_path[*i].category { + ConstraintCategory::OpaqueType + | ConstraintCategory::Boring + | ConstraintCategory::BoringNoLocation + | ConstraintCategory::Internal + | ConstraintCategory::Predicate(_) => false, + ConstraintCategory::TypeAnnotation + | ConstraintCategory::Return(_) + | ConstraintCategory::Yield => true, + _ => constraint_sup_scc != target_scc, + } + } else { + !matches!( + categorized_path[*i].category, + ConstraintCategory::OpaqueType + | ConstraintCategory::Boring + | ConstraintCategory::BoringNoLocation + | ConstraintCategory::Internal + | ConstraintCategory::Predicate(_) + ) + } + }; + + let best_choice = + if blame_source { range.rev().find(find_region) } else { range.find(find_region) }; + + debug!( + "best_blame_constraint: best_choice={:?} blame_source={}", + best_choice, blame_source + ); + + if let Some(i) = best_choice { + if let Some(next) = categorized_path.get(i + 1) { + if matches!(categorized_path[i].category, ConstraintCategory::Return(_)) + && next.category == ConstraintCategory::OpaqueType + { + // The return expression is being influenced by the return type being + // impl Trait, point at the return type and not the return expr. + return next.clone(); + } + } + + if categorized_path[i].category == ConstraintCategory::Return(ReturnConstraint::Normal) + { + let field = categorized_path.iter().find_map(|p| { + if let ConstraintCategory::ClosureUpvar(f) = p.category { + Some(f) + } else { + None + } + }); + + if let Some(field) = field { + categorized_path[i].category = + ConstraintCategory::Return(ReturnConstraint::ClosureUpvar(field)); + } + } + + return categorized_path[i].clone(); + } + + // If that search fails, that is.. unusual. Maybe everything + // is in the same SCC or something. In that case, find what + // appears to be the most interesting point to report to the + // user via an even more ad-hoc guess. + categorized_path.sort_by(|p0, p1| p0.category.cmp(&p1.category)); + debug!("best_blame_constraint: sorted_path={:#?}", categorized_path); + + categorized_path.remove(0) + } + + pub(crate) fn universe_info(&self, universe: ty::UniverseIndex) -> UniverseInfo<'tcx> { + self.universe_causes[&universe].clone() + } +} + +impl<'tcx> RegionDefinition<'tcx> { + fn new(universe: ty::UniverseIndex, rv_origin: RegionVariableOrigin) -> Self { + // Create a new region definition. Note that, for free + // regions, the `external_name` field gets updated later in + // `init_universal_regions`. + + let origin = match rv_origin { + RegionVariableOrigin::Nll(origin) => origin, + _ => NllRegionVariableOrigin::Existential { from_forall: false }, + }; + + Self { origin, universe, external_name: None } + } +} + +pub trait ClosureRegionRequirementsExt<'tcx> { + fn apply_requirements( + &self, + tcx: TyCtxt<'tcx>, + closure_def_id: DefId, + closure_substs: SubstsRef<'tcx>, + ) -> Vec<QueryOutlivesConstraint<'tcx>>; +} + +impl<'tcx> ClosureRegionRequirementsExt<'tcx> for ClosureRegionRequirements<'tcx> { + /// Given an instance T of the closure type, this method + /// instantiates the "extra" requirements that we computed for the + /// closure into the inference context. This has the effect of + /// adding new outlives obligations to existing variables. + /// + /// As described on `ClosureRegionRequirements`, the extra + /// requirements are expressed in terms of regionvids that index + /// into the free regions that appear on the closure type. So, to + /// do this, we first copy those regions out from the type T into + /// a vector. Then we can just index into that vector to extract + /// out the corresponding region from T and apply the + /// requirements. + fn apply_requirements( + &self, + tcx: TyCtxt<'tcx>, + closure_def_id: DefId, + closure_substs: SubstsRef<'tcx>, + ) -> Vec<QueryOutlivesConstraint<'tcx>> { + debug!( + "apply_requirements(closure_def_id={:?}, closure_substs={:?})", + closure_def_id, closure_substs + ); + + // Extract the values of the free regions in `closure_substs` + // into a vector. These are the regions that we will be + // relating to one another. + let closure_mapping = &UniversalRegions::closure_mapping( + tcx, + closure_substs, + self.num_external_vids, + tcx.typeck_root_def_id(closure_def_id), + ); + debug!("apply_requirements: closure_mapping={:?}", closure_mapping); + + // Create the predicates. + self.outlives_requirements + .iter() + .map(|outlives_requirement| { + let outlived_region = closure_mapping[outlives_requirement.outlived_free_region]; + + match outlives_requirement.subject { + ClosureOutlivesSubject::Region(region) => { + let region = closure_mapping[region]; + debug!( + "apply_requirements: region={:?} \ + outlived_region={:?} \ + outlives_requirement={:?}", + region, outlived_region, outlives_requirement, + ); + ty::Binder::dummy(ty::OutlivesPredicate(region.into(), outlived_region)) + } + + ClosureOutlivesSubject::Ty(ty) => { + debug!( + "apply_requirements: ty={:?} \ + outlived_region={:?} \ + outlives_requirement={:?}", + ty, outlived_region, outlives_requirement, + ); + ty::Binder::dummy(ty::OutlivesPredicate(ty.into(), outlived_region)) + } + } + }) + .collect() + } +} + +#[derive(Clone, Debug)] +pub struct BlameConstraint<'tcx> { + pub category: ConstraintCategory<'tcx>, + pub from_closure: bool, + pub cause: ObligationCause<'tcx>, + pub variance_info: ty::VarianceDiagInfo<'tcx>, +} diff --git a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs new file mode 100644 index 000000000..d6712b6a4 --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs @@ -0,0 +1,662 @@ +use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::vec_map::VecMap; +use rustc_hir::def_id::LocalDefId; +use rustc_hir::OpaqueTyOrigin; +use rustc_infer::infer::error_reporting::unexpected_hidden_region_diagnostic; +use rustc_infer::infer::TyCtxtInferExt as _; +use rustc_infer::infer::{DefiningAnchor, InferCtxt}; +use rustc_infer::traits::{Obligation, ObligationCause, TraitEngine}; +use rustc_middle::ty::fold::{TypeFolder, TypeSuperFoldable}; +use rustc_middle::ty::subst::{GenericArg, GenericArgKind, InternalSubsts}; +use rustc_middle::ty::visit::TypeVisitable; +use rustc_middle::ty::{ + self, OpaqueHiddenType, OpaqueTypeKey, ToPredicate, Ty, TyCtxt, TypeFoldable, +}; +use rustc_span::Span; +use rustc_trait_selection::traits::error_reporting::InferCtxtExt as _; +use rustc_trait_selection::traits::TraitEngineExt as _; + +use super::RegionInferenceContext; + +impl<'tcx> RegionInferenceContext<'tcx> { + /// Resolve any opaque types that were encountered while borrow checking + /// this item. This is then used to get the type in the `type_of` query. + /// + /// For example consider `fn f<'a>(x: &'a i32) -> impl Sized + 'a { x }`. + /// This is lowered to give HIR something like + /// + /// type f<'a>::_Return<'_a> = impl Sized + '_a; + /// fn f<'a>(x: &'a i32) -> f<'static>::_Return<'a> { x } + /// + /// When checking the return type record the type from the return and the + /// type used in the return value. In this case they might be `_Return<'1>` + /// and `&'2 i32` respectively. + /// + /// Once we to this method, we have completed region inference and want to + /// call `infer_opaque_definition_from_instantiation` to get the inferred + /// type of `_Return<'_a>`. `infer_opaque_definition_from_instantiation` + /// compares lifetimes directly, so we need to map the inference variables + /// back to concrete lifetimes: `'static`, `ReEarlyBound` or `ReFree`. + /// + /// First we map all the lifetimes in the concrete type to an equal + /// universal region that occurs in the concrete type's substs, in this case + /// this would result in `&'1 i32`. We only consider regions in the substs + /// in case there is an equal region that does not. For example, this should + /// be allowed: + /// `fn f<'a: 'b, 'b: 'a>(x: *mut &'b i32) -> impl Sized + 'a { x }` + /// + /// Then we map the regions in both the type and the subst to their + /// `external_name` giving `concrete_type = &'a i32`, + /// `substs = ['static, 'a]`. This will then allow + /// `infer_opaque_definition_from_instantiation` to determine that + /// `_Return<'_a> = &'_a i32`. + /// + /// There's a slight complication around closures. Given + /// `fn f<'a: 'a>() { || {} }` the closure's type is something like + /// `f::<'a>::{{closure}}`. The region parameter from f is essentially + /// ignored by type checking so ends up being inferred to an empty region. + /// Calling `universal_upper_bound` for such a region gives `fr_fn_body`, + /// which has no `external_name` in which case we use `'empty` as the + /// region to pass to `infer_opaque_definition_from_instantiation`. + #[instrument(level = "debug", skip(self, infcx))] + pub(crate) fn infer_opaque_types( + &self, + infcx: &InferCtxt<'_, 'tcx>, + opaque_ty_decls: VecMap<OpaqueTypeKey<'tcx>, (OpaqueHiddenType<'tcx>, OpaqueTyOrigin)>, + ) -> VecMap<LocalDefId, OpaqueHiddenType<'tcx>> { + let mut result: VecMap<LocalDefId, OpaqueHiddenType<'tcx>> = VecMap::new(); + for (opaque_type_key, (concrete_type, origin)) in opaque_ty_decls { + let substs = opaque_type_key.substs; + debug!(?concrete_type, ?substs); + + let mut subst_regions = vec![self.universal_regions.fr_static]; + let universal_substs = infcx.tcx.fold_regions(substs, |region, _| { + if let ty::RePlaceholder(..) = region.kind() { + // Higher kinded regions don't need remapping, they don't refer to anything outside of this the substs. + return region; + } + let vid = self.to_region_vid(region); + trace!(?vid); + let scc = self.constraint_sccs.scc(vid); + trace!(?scc); + match self.scc_values.universal_regions_outlived_by(scc).find_map(|lb| { + self.eval_equal(vid, lb).then_some(self.definitions[lb].external_name?) + }) { + Some(region) => { + let vid = self.universal_regions.to_region_vid(region); + subst_regions.push(vid); + region + } + None => { + subst_regions.push(vid); + infcx.tcx.sess.delay_span_bug( + concrete_type.span, + "opaque type with non-universal region substs", + ); + infcx.tcx.lifetimes.re_static + } + } + }); + + subst_regions.sort(); + subst_regions.dedup(); + + let universal_concrete_type = + infcx.tcx.fold_regions(concrete_type, |region, _| match *region { + ty::ReVar(vid) => subst_regions + .iter() + .find(|ur_vid| self.eval_equal(vid, **ur_vid)) + .and_then(|ur_vid| self.definitions[*ur_vid].external_name) + .unwrap_or(infcx.tcx.lifetimes.re_root_empty), + _ => region, + }); + + debug!(?universal_concrete_type, ?universal_substs); + + let opaque_type_key = + OpaqueTypeKey { def_id: opaque_type_key.def_id, substs: universal_substs }; + let ty = infcx.infer_opaque_definition_from_instantiation( + opaque_type_key, + universal_concrete_type, + origin, + ); + // Sometimes two opaque types are the same only after we remap the generic parameters + // back to the opaque type definition. E.g. we may have `OpaqueType<X, Y>` mapped to `(X, Y)` + // and `OpaqueType<Y, X>` mapped to `(Y, X)`, and those are the same, but we only know that + // once we convert the generic parameters to those of the opaque type. + if let Some(prev) = result.get_mut(&opaque_type_key.def_id) { + if prev.ty != ty { + if !ty.references_error() { + prev.report_mismatch( + &OpaqueHiddenType { ty, span: concrete_type.span }, + infcx.tcx, + ); + } + prev.ty = infcx.tcx.ty_error(); + } + // Pick a better span if there is one. + // FIXME(oli-obk): collect multiple spans for better diagnostics down the road. + prev.span = prev.span.substitute_dummy(concrete_type.span); + } else { + result.insert( + opaque_type_key.def_id, + OpaqueHiddenType { ty, span: concrete_type.span }, + ); + } + } + result + } + + /// Map the regions in the type to named regions. This is similar to what + /// `infer_opaque_types` does, but can infer any universal region, not only + /// ones from the substs for the opaque type. It also doesn't double check + /// that the regions produced are in fact equal to the named region they are + /// replaced with. This is fine because this function is only to improve the + /// region names in error messages. + pub(crate) fn name_regions<T>(&self, tcx: TyCtxt<'tcx>, ty: T) -> T + where + T: TypeFoldable<'tcx>, + { + tcx.fold_regions(ty, |region, _| match *region { + ty::ReVar(vid) => { + // Find something that we can name + let upper_bound = self.approx_universal_upper_bound(vid); + let upper_bound = &self.definitions[upper_bound]; + match upper_bound.external_name { + Some(reg) => reg, + None => { + // Nothing exact found, so we pick the first one that we find. + let scc = self.constraint_sccs.scc(vid); + for vid in self.rev_scc_graph.as_ref().unwrap().upper_bounds(scc) { + match self.definitions[vid].external_name { + None => {} + Some(region) if region.is_static() => {} + Some(region) => return region, + } + } + region + } + } + } + _ => region, + }) + } +} + +pub trait InferCtxtExt<'tcx> { + fn infer_opaque_definition_from_instantiation( + &self, + opaque_type_key: OpaqueTypeKey<'tcx>, + instantiated_ty: OpaqueHiddenType<'tcx>, + origin: OpaqueTyOrigin, + ) -> Ty<'tcx>; +} + +impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> { + /// Given the fully resolved, instantiated type for an opaque + /// type, i.e., the value of an inference variable like C1 or C2 + /// (*), computes the "definition type" for an opaque type + /// definition -- that is, the inferred value of `Foo1<'x>` or + /// `Foo2<'x>` that we would conceptually use in its definition: + /// ```ignore (illustrative) + /// type Foo1<'x> = impl Bar<'x> = AAA; // <-- this type AAA + /// type Foo2<'x> = impl Bar<'x> = BBB; // <-- or this type BBB + /// fn foo<'a, 'b>(..) -> (Foo1<'a>, Foo2<'b>) { .. } + /// ``` + /// Note that these values are defined in terms of a distinct set of + /// generic parameters (`'x` instead of `'a`) from C1 or C2. The main + /// purpose of this function is to do that translation. + /// + /// (*) C1 and C2 were introduced in the comments on + /// `register_member_constraints`. Read that comment for more context. + /// + /// # Parameters + /// + /// - `def_id`, the `impl Trait` type + /// - `substs`, the substs used to instantiate this opaque type + /// - `instantiated_ty`, the inferred type C1 -- fully resolved, lifted version of + /// `opaque_defn.concrete_ty` + #[instrument(level = "debug", skip(self))] + fn infer_opaque_definition_from_instantiation( + &self, + opaque_type_key: OpaqueTypeKey<'tcx>, + instantiated_ty: OpaqueHiddenType<'tcx>, + origin: OpaqueTyOrigin, + ) -> Ty<'tcx> { + if self.is_tainted_by_errors() { + return self.tcx.ty_error(); + } + + let OpaqueTypeKey { def_id, substs } = opaque_type_key; + + // Use substs to build up a reverse map from regions to their + // identity mappings. This is necessary because of `impl + // Trait` lifetimes are computed by replacing existing + // lifetimes with 'static and remapping only those used in the + // `impl Trait` return type, resulting in the parameters + // shifting. + let id_substs = InternalSubsts::identity_for_item(self.tcx, def_id.to_def_id()); + debug!(?id_substs); + let map: FxHashMap<GenericArg<'tcx>, GenericArg<'tcx>> = + substs.iter().enumerate().map(|(index, subst)| (subst, id_substs[index])).collect(); + debug!("map = {:#?}", map); + + // Convert the type from the function into a type valid outside + // the function, by replacing invalid regions with 'static, + // after producing an error for each of them. + let definition_ty = instantiated_ty.ty.fold_with(&mut ReverseMapper::new( + self.tcx, + opaque_type_key, + map, + instantiated_ty.ty, + instantiated_ty.span, + )); + debug!(?definition_ty); + + if !check_opaque_type_parameter_valid( + self.tcx, + opaque_type_key, + origin, + instantiated_ty.span, + ) { + return self.tcx.ty_error(); + } + + // Only check this for TAIT. RPIT already supports `src/test/ui/impl-trait/nested-return-type2.rs` + // on stable and we'd break that. + if let OpaqueTyOrigin::TyAlias = origin { + // This logic duplicates most of `check_opaque_meets_bounds`. + // FIXME(oli-obk): Also do region checks here and then consider removing `check_opaque_meets_bounds` entirely. + let param_env = self.tcx.param_env(def_id); + let body_id = self.tcx.local_def_id_to_hir_id(def_id); + // HACK This bubble is required for this tests to pass: + // type-alias-impl-trait/issue-67844-nested-opaque.rs + self.tcx.infer_ctxt().with_opaque_type_inference(DefiningAnchor::Bubble).enter( + move |infcx| { + // Require the hidden type to be well-formed with only the generics of the opaque type. + // Defining use functions may have more bounds than the opaque type, which is ok, as long as the + // hidden type is well formed even without those bounds. + let predicate = + ty::Binder::dummy(ty::PredicateKind::WellFormed(definition_ty.into())) + .to_predicate(infcx.tcx); + let mut fulfillment_cx = <dyn TraitEngine<'tcx>>::new(infcx.tcx); + + // Require that the hidden type actually fulfills all the bounds of the opaque type, even without + // the bounds that the function supplies. + match infcx.register_hidden_type( + OpaqueTypeKey { def_id, substs: id_substs }, + ObligationCause::misc(instantiated_ty.span, body_id), + param_env, + definition_ty, + origin, + ) { + Ok(infer_ok) => { + for obligation in infer_ok.obligations { + fulfillment_cx.register_predicate_obligation(&infcx, obligation); + } + } + Err(err) => { + infcx + .report_mismatched_types( + &ObligationCause::misc(instantiated_ty.span, body_id), + self.tcx.mk_opaque(def_id.to_def_id(), id_substs), + definition_ty, + err, + ) + .emit(); + } + } + + fulfillment_cx.register_predicate_obligation( + &infcx, + Obligation::misc(instantiated_ty.span, body_id, param_env, predicate), + ); + + // Check that all obligations are satisfied by the implementation's + // version. + let errors = fulfillment_cx.select_all_or_error(&infcx); + + // This is still required for many(half of the tests in ui/type-alias-impl-trait) + // tests to pass + let _ = infcx.inner.borrow_mut().opaque_type_storage.take_opaque_types(); + + if errors.is_empty() { + definition_ty + } else { + infcx.report_fulfillment_errors(&errors, None, false); + self.tcx.ty_error() + } + }, + ) + } else { + definition_ty + } + } +} + +fn check_opaque_type_parameter_valid( + tcx: TyCtxt<'_>, + opaque_type_key: OpaqueTypeKey<'_>, + origin: OpaqueTyOrigin, + span: Span, +) -> bool { + match origin { + // No need to check return position impl trait (RPIT) + // because for type and const parameters they are correct + // by construction: we convert + // + // fn foo<P0..Pn>() -> impl Trait + // + // into + // + // type Foo<P0...Pn> + // fn foo<P0..Pn>() -> Foo<P0...Pn>. + // + // For lifetime parameters we convert + // + // fn foo<'l0..'ln>() -> impl Trait<'l0..'lm> + // + // into + // + // type foo::<'p0..'pn>::Foo<'q0..'qm> + // fn foo<l0..'ln>() -> foo::<'static..'static>::Foo<'l0..'lm>. + // + // which would error here on all of the `'static` args. + OpaqueTyOrigin::FnReturn(..) | OpaqueTyOrigin::AsyncFn(..) => return true, + // Check these + OpaqueTyOrigin::TyAlias => {} + } + let opaque_generics = tcx.generics_of(opaque_type_key.def_id); + let mut seen_params: FxHashMap<_, Vec<_>> = FxHashMap::default(); + for (i, arg) in opaque_type_key.substs.iter().enumerate() { + let arg_is_param = match arg.unpack() { + GenericArgKind::Type(ty) => matches!(ty.kind(), ty::Param(_)), + GenericArgKind::Lifetime(lt) if lt.is_static() => { + tcx.sess + .struct_span_err(span, "non-defining opaque type use in defining scope") + .span_label( + tcx.def_span(opaque_generics.param_at(i, tcx).def_id), + "cannot use static lifetime; use a bound lifetime \ + instead or remove the lifetime parameter from the \ + opaque type", + ) + .emit(); + return false; + } + GenericArgKind::Lifetime(lt) => { + matches!(*lt, ty::ReEarlyBound(_) | ty::ReFree(_)) + } + GenericArgKind::Const(ct) => matches!(ct.kind(), ty::ConstKind::Param(_)), + }; + + if arg_is_param { + seen_params.entry(arg).or_default().push(i); + } else { + // Prevent `fn foo() -> Foo<u32>` from being defining. + let opaque_param = opaque_generics.param_at(i, tcx); + tcx.sess + .struct_span_err(span, "non-defining opaque type use in defining scope") + .span_note( + tcx.def_span(opaque_param.def_id), + &format!( + "used non-generic {} `{}` for generic parameter", + opaque_param.kind.descr(), + arg, + ), + ) + .emit(); + return false; + } + } + + for (_, indices) in seen_params { + if indices.len() > 1 { + let descr = opaque_generics.param_at(indices[0], tcx).kind.descr(); + let spans: Vec<_> = indices + .into_iter() + .map(|i| tcx.def_span(opaque_generics.param_at(i, tcx).def_id)) + .collect(); + tcx.sess + .struct_span_err(span, "non-defining opaque type use in defining scope") + .span_note(spans, &format!("{} used multiple times", descr)) + .emit(); + return false; + } + } + true +} + +struct ReverseMapper<'tcx> { + tcx: TyCtxt<'tcx>, + + key: ty::OpaqueTypeKey<'tcx>, + map: FxHashMap<GenericArg<'tcx>, GenericArg<'tcx>>, + map_missing_regions_to_empty: bool, + + /// initially `Some`, set to `None` once error has been reported + hidden_ty: Option<Ty<'tcx>>, + + /// Span of function being checked. + span: Span, +} + +impl<'tcx> ReverseMapper<'tcx> { + fn new( + tcx: TyCtxt<'tcx>, + key: ty::OpaqueTypeKey<'tcx>, + map: FxHashMap<GenericArg<'tcx>, GenericArg<'tcx>>, + hidden_ty: Ty<'tcx>, + span: Span, + ) -> Self { + Self { + tcx, + key, + map, + map_missing_regions_to_empty: false, + hidden_ty: Some(hidden_ty), + span, + } + } + + fn fold_kind_mapping_missing_regions_to_empty( + &mut self, + kind: GenericArg<'tcx>, + ) -> GenericArg<'tcx> { + assert!(!self.map_missing_regions_to_empty); + self.map_missing_regions_to_empty = true; + let kind = kind.fold_with(self); + self.map_missing_regions_to_empty = false; + kind + } + + fn fold_kind_normally(&mut self, kind: GenericArg<'tcx>) -> GenericArg<'tcx> { + assert!(!self.map_missing_regions_to_empty); + kind.fold_with(self) + } +} + +impl<'tcx> TypeFolder<'tcx> for ReverseMapper<'tcx> { + fn tcx(&self) -> TyCtxt<'tcx> { + self.tcx + } + + #[instrument(skip(self), level = "debug")] + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + match *r { + // Ignore bound regions and `'static` regions that appear in the + // type, we only need to remap regions that reference lifetimes + // from the function declaration. + // This would ignore `'r` in a type like `for<'r> fn(&'r u32)`. + ty::ReLateBound(..) | ty::ReStatic => return r, + + // If regions have been erased (by writeback), don't try to unerase + // them. + ty::ReErased => return r, + + // The regions that we expect from borrow checking. + ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReEmpty(ty::UniverseIndex::ROOT) => {} + + ty::ReEmpty(_) | ty::RePlaceholder(_) | ty::ReVar(_) => { + // All of the regions in the type should either have been + // erased by writeback, or mapped back to named regions by + // borrow checking. + bug!("unexpected region kind in opaque type: {:?}", r); + } + } + + let generics = self.tcx().generics_of(self.key.def_id); + match self.map.get(&r.into()).map(|k| k.unpack()) { + Some(GenericArgKind::Lifetime(r1)) => r1, + Some(u) => panic!("region mapped to unexpected kind: {:?}", u), + None if self.map_missing_regions_to_empty => self.tcx.lifetimes.re_root_empty, + None if generics.parent.is_some() => { + if let Some(hidden_ty) = self.hidden_ty.take() { + unexpected_hidden_region_diagnostic( + self.tcx, + self.tcx.def_span(self.key.def_id), + hidden_ty, + r, + self.key, + ) + .emit(); + } + self.tcx.lifetimes.re_root_empty + } + None => { + self.tcx + .sess + .struct_span_err(self.span, "non-defining opaque type use in defining scope") + .span_label( + self.span, + format!( + "lifetime `{}` is part of concrete type but not used in \ + parameter list of the `impl Trait` type alias", + r + ), + ) + .emit(); + + self.tcx().lifetimes.re_static + } + } + } + + fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { + match *ty.kind() { + ty::Closure(def_id, substs) => { + // I am a horrible monster and I pray for death. When + // we encounter a closure here, it is always a closure + // from within the function that we are currently + // type-checking -- one that is now being encapsulated + // in an opaque type. Ideally, we would + // go through the types/lifetimes that it references + // and treat them just like we would any other type, + // which means we would error out if we find any + // reference to a type/region that is not in the + // "reverse map". + // + // **However,** in the case of closures, there is a + // somewhat subtle (read: hacky) consideration. The + // problem is that our closure types currently include + // all the lifetime parameters declared on the + // enclosing function, even if they are unused by the + // closure itself. We can't readily filter them out, + // so here we replace those values with `'empty`. This + // can't really make a difference to the rest of the + // compiler; those regions are ignored for the + // outlives relation, and hence don't affect trait + // selection or auto traits, and they are erased + // during codegen. + + let generics = self.tcx.generics_of(def_id); + let substs = self.tcx.mk_substs(substs.iter().enumerate().map(|(index, kind)| { + if index < generics.parent_count { + // Accommodate missing regions in the parent kinds... + self.fold_kind_mapping_missing_regions_to_empty(kind) + } else { + // ...but not elsewhere. + self.fold_kind_normally(kind) + } + })); + + self.tcx.mk_closure(def_id, substs) + } + + ty::Generator(def_id, substs, movability) => { + let generics = self.tcx.generics_of(def_id); + let substs = self.tcx.mk_substs(substs.iter().enumerate().map(|(index, kind)| { + if index < generics.parent_count { + // Accommodate missing regions in the parent kinds... + self.fold_kind_mapping_missing_regions_to_empty(kind) + } else { + // ...but not elsewhere. + self.fold_kind_normally(kind) + } + })); + + self.tcx.mk_generator(def_id, substs, movability) + } + + ty::Param(param) => { + // Look it up in the substitution list. + match self.map.get(&ty.into()).map(|k| k.unpack()) { + // Found it in the substitution list; replace with the parameter from the + // opaque type. + Some(GenericArgKind::Type(t1)) => t1, + Some(u) => panic!("type mapped to unexpected kind: {:?}", u), + None => { + debug!(?param, ?self.map); + self.tcx + .sess + .struct_span_err( + self.span, + &format!( + "type parameter `{}` is part of concrete type but not \ + used in parameter list for the `impl Trait` type alias", + ty + ), + ) + .emit(); + + self.tcx().ty_error() + } + } + } + + _ => ty.super_fold_with(self), + } + } + + fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { + trace!("checking const {:?}", ct); + // Find a const parameter + match ct.kind() { + ty::ConstKind::Param(..) => { + // Look it up in the substitution list. + match self.map.get(&ct.into()).map(|k| k.unpack()) { + // Found it in the substitution list, replace with the parameter from the + // opaque type. + Some(GenericArgKind::Const(c1)) => c1, + Some(u) => panic!("const mapped to unexpected kind: {:?}", u), + None => { + self.tcx + .sess + .struct_span_err( + self.span, + &format!( + "const parameter `{}` is part of concrete type but not \ + used in parameter list for the `impl Trait` type alias", + ct + ), + ) + .emit(); + + self.tcx().const_error(ct.ty()) + } + } + } + + _ => ct, + } + } +} diff --git a/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs b/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs new file mode 100644 index 000000000..1e6798eee --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/reverse_sccs.rs @@ -0,0 +1,68 @@ +use crate::constraints::ConstraintSccIndex; +use crate::RegionInferenceContext; +use itertools::Itertools; +use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use rustc_data_structures::graph::vec_graph::VecGraph; +use rustc_data_structures::graph::WithSuccessors; +use rustc_middle::ty::RegionVid; +use std::ops::Range; +use std::rc::Rc; + +pub(crate) struct ReverseSccGraph { + graph: VecGraph<ConstraintSccIndex>, + /// For each SCC, the range of `universal_regions` that use that SCC as + /// their value. + scc_regions: FxHashMap<ConstraintSccIndex, Range<usize>>, + /// All of the universal regions, in grouped so that `scc_regions` can + /// index into here. + universal_regions: Vec<RegionVid>, +} + +impl ReverseSccGraph { + /// Find all universal regions that are required to outlive the given SCC. + pub(super) fn upper_bounds<'a>( + &'a self, + scc0: ConstraintSccIndex, + ) -> impl Iterator<Item = RegionVid> + 'a { + let mut duplicates = FxHashSet::default(); + self.graph + .depth_first_search(scc0) + .flat_map(move |scc1| { + self.scc_regions + .get(&scc1) + .map_or(&[][..], |range| &self.universal_regions[range.clone()]) + }) + .copied() + .filter(move |r| duplicates.insert(*r)) + } +} + +impl RegionInferenceContext<'_> { + /// Compute and return the reverse SCC-based constraint graph (lazily). + pub(super) fn reverse_scc_graph(&mut self) -> Rc<ReverseSccGraph> { + if let Some(g) = &self.rev_scc_graph { + return g.clone(); + } + + let graph = self.constraint_sccs.reverse(); + let mut paired_scc_regions = self + .universal_regions + .universal_regions() + .map(|region| (self.constraint_sccs.scc(region), region)) + .collect_vec(); + paired_scc_regions.sort(); + let universal_regions = paired_scc_regions.iter().map(|&(_, region)| region).collect(); + + let mut scc_regions = FxHashMap::default(); + let mut start = 0; + for (scc, group) in &paired_scc_regions.into_iter().group_by(|(scc, _)| *scc) { + let group_size = group.count(); + scc_regions.insert(scc, start..start + group_size); + start += group_size; + } + + let rev_graph = Rc::new(ReverseSccGraph { graph, scc_regions, universal_regions }); + self.rev_scc_graph = Some(rev_graph.clone()); + rev_graph + } +} diff --git a/compiler/rustc_borrowck/src/region_infer/values.rs b/compiler/rustc_borrowck/src/region_infer/values.rs new file mode 100644 index 000000000..c81ef10f7 --- /dev/null +++ b/compiler/rustc_borrowck/src/region_infer/values.rs @@ -0,0 +1,488 @@ +use rustc_data_structures::fx::FxIndexSet; +use rustc_index::bit_set::SparseBitMatrix; +use rustc_index::interval::IntervalSet; +use rustc_index::interval::SparseIntervalMatrix; +use rustc_index::vec::Idx; +use rustc_index::vec::IndexVec; +use rustc_middle::mir::{BasicBlock, Body, Location}; +use rustc_middle::ty::{self, RegionVid}; +use std::fmt::Debug; +use std::rc::Rc; + +/// Maps between a `Location` and a `PointIndex` (and vice versa). +pub(crate) struct RegionValueElements { + /// For each basic block, how many points are contained within? + statements_before_block: IndexVec<BasicBlock, usize>, + + /// Map backward from each point to the basic block that it + /// belongs to. + basic_blocks: IndexVec<PointIndex, BasicBlock>, + + num_points: usize, +} + +impl RegionValueElements { + pub(crate) fn new(body: &Body<'_>) -> Self { + let mut num_points = 0; + let statements_before_block: IndexVec<BasicBlock, usize> = body + .basic_blocks() + .iter() + .map(|block_data| { + let v = num_points; + num_points += block_data.statements.len() + 1; + v + }) + .collect(); + debug!("RegionValueElements: statements_before_block={:#?}", statements_before_block); + debug!("RegionValueElements: num_points={:#?}", num_points); + + let mut basic_blocks = IndexVec::with_capacity(num_points); + for (bb, bb_data) in body.basic_blocks().iter_enumerated() { + basic_blocks.extend((0..=bb_data.statements.len()).map(|_| bb)); + } + + Self { statements_before_block, basic_blocks, num_points } + } + + /// Total number of point indices + pub(crate) fn num_points(&self) -> usize { + self.num_points + } + + /// Converts a `Location` into a `PointIndex`. O(1). + pub(crate) fn point_from_location(&self, location: Location) -> PointIndex { + let Location { block, statement_index } = location; + let start_index = self.statements_before_block[block]; + PointIndex::new(start_index + statement_index) + } + + /// Converts a `Location` into a `PointIndex`. O(1). + pub(crate) fn entry_point(&self, block: BasicBlock) -> PointIndex { + let start_index = self.statements_before_block[block]; + PointIndex::new(start_index) + } + + /// Return the PointIndex for the block start of this index. + pub(crate) fn to_block_start(&self, index: PointIndex) -> PointIndex { + PointIndex::new(self.statements_before_block[self.basic_blocks[index]]) + } + + /// Converts a `PointIndex` back to a location. O(1). + pub(crate) fn to_location(&self, index: PointIndex) -> Location { + assert!(index.index() < self.num_points); + let block = self.basic_blocks[index]; + let start_index = self.statements_before_block[block]; + let statement_index = index.index() - start_index; + Location { block, statement_index } + } + + /// Sometimes we get point-indices back from bitsets that may be + /// out of range (because they round up to the nearest 2^N number + /// of bits). Use this function to filter such points out if you + /// like. + pub(crate) fn point_in_range(&self, index: PointIndex) -> bool { + index.index() < self.num_points + } +} + +rustc_index::newtype_index! { + /// A single integer representing a `Location` in the MIR control-flow + /// graph. Constructed efficiently from `RegionValueElements`. + pub struct PointIndex { DEBUG_FORMAT = "PointIndex({})" } +} + +rustc_index::newtype_index! { + /// A single integer representing a `ty::Placeholder`. + pub struct PlaceholderIndex { DEBUG_FORMAT = "PlaceholderIndex({})" } +} + +/// An individual element in a region value -- the value of a +/// particular region variable consists of a set of these elements. +#[derive(Debug, Clone)] +pub(crate) enum RegionElement { + /// A point in the control-flow graph. + Location(Location), + + /// A universally quantified region from the root universe (e.g., + /// a lifetime parameter). + RootUniversalRegion(RegionVid), + + /// A placeholder (e.g., instantiated from a `for<'a> fn(&'a u32)` + /// type). + PlaceholderRegion(ty::PlaceholderRegion), +} + +/// When we initially compute liveness, we use an interval matrix storing +/// liveness ranges for each region-vid. +pub(crate) struct LivenessValues<N: Idx> { + elements: Rc<RegionValueElements>, + points: SparseIntervalMatrix<N, PointIndex>, +} + +impl<N: Idx> LivenessValues<N> { + /// Creates a new set of "region values" that tracks causal information. + /// Each of the regions in num_region_variables will be initialized with an + /// empty set of points and no causal information. + pub(crate) fn new(elements: Rc<RegionValueElements>) -> Self { + Self { points: SparseIntervalMatrix::new(elements.num_points), elements } + } + + /// Iterate through each region that has a value in this set. + pub(crate) fn rows(&self) -> impl Iterator<Item = N> { + self.points.rows() + } + + /// Adds the given element to the value for the given region. Returns whether + /// the element is newly added (i.e., was not already present). + pub(crate) fn add_element(&mut self, row: N, location: Location) -> bool { + debug!("LivenessValues::add(r={:?}, location={:?})", row, location); + let index = self.elements.point_from_location(location); + self.points.insert(row, index) + } + + /// Adds all the elements in the given bit array into the given + /// region. Returns whether any of them are newly added. + pub(crate) fn add_elements(&mut self, row: N, locations: &IntervalSet<PointIndex>) -> bool { + debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations); + self.points.union_row(row, locations) + } + + /// Adds all the control-flow points to the values for `r`. + pub(crate) fn add_all_points(&mut self, row: N) { + self.points.insert_all_into_row(row); + } + + /// Returns `true` if the region `r` contains the given element. + pub(crate) fn contains(&self, row: N, location: Location) -> bool { + let index = self.elements.point_from_location(location); + self.points.row(row).map_or(false, |r| r.contains(index)) + } + + /// Returns an iterator of all the elements contained by the region `r` + pub(crate) fn get_elements(&self, row: N) -> impl Iterator<Item = Location> + '_ { + self.points + .row(row) + .into_iter() + .flat_map(|set| set.iter()) + .take_while(move |&p| self.elements.point_in_range(p)) + .map(move |p| self.elements.to_location(p)) + } + + /// Returns a "pretty" string value of the region. Meant for debugging. + pub(crate) fn region_value_str(&self, r: N) -> String { + region_value_str(self.get_elements(r).map(RegionElement::Location)) + } +} + +/// Maps from `ty::PlaceholderRegion` values that are used in the rest of +/// rustc to the internal `PlaceholderIndex` values that are used in +/// NLL. +#[derive(Default)] +pub(crate) struct PlaceholderIndices { + indices: FxIndexSet<ty::PlaceholderRegion>, +} + +impl PlaceholderIndices { + pub(crate) fn insert(&mut self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex { + let (index, _) = self.indices.insert_full(placeholder); + index.into() + } + + pub(crate) fn lookup_index(&self, placeholder: ty::PlaceholderRegion) -> PlaceholderIndex { + self.indices.get_index_of(&placeholder).unwrap().into() + } + + pub(crate) fn lookup_placeholder( + &self, + placeholder: PlaceholderIndex, + ) -> ty::PlaceholderRegion { + self.indices[placeholder.index()] + } + + pub(crate) fn len(&self) -> usize { + self.indices.len() + } +} + +/// Stores the full values for a set of regions (in contrast to +/// `LivenessValues`, which only stores those points in the where a +/// region is live). The full value for a region may contain points in +/// the CFG, but also free regions as well as bound universe +/// placeholders. +/// +/// Example: +/// +/// ```text +/// fn foo(x: &'a u32) -> &'a u32 { +/// let y: &'0 u32 = x; // let's call this `'0` +/// y +/// } +/// ``` +/// +/// Here, the variable `'0` would contain the free region `'a`, +/// because (since it is returned) it must live for at least `'a`. But +/// it would also contain various points from within the function. +#[derive(Clone)] +pub(crate) struct RegionValues<N: Idx> { + elements: Rc<RegionValueElements>, + placeholder_indices: Rc<PlaceholderIndices>, + points: SparseIntervalMatrix<N, PointIndex>, + free_regions: SparseBitMatrix<N, RegionVid>, + + /// Placeholders represent bound regions -- so something like `'a` + /// in for<'a> fn(&'a u32)`. + placeholders: SparseBitMatrix<N, PlaceholderIndex>, +} + +impl<N: Idx> RegionValues<N> { + /// Creates a new set of "region values" that tracks causal information. + /// Each of the regions in num_region_variables will be initialized with an + /// empty set of points and no causal information. + pub(crate) fn new( + elements: &Rc<RegionValueElements>, + num_universal_regions: usize, + placeholder_indices: &Rc<PlaceholderIndices>, + ) -> Self { + let num_placeholders = placeholder_indices.len(); + Self { + elements: elements.clone(), + points: SparseIntervalMatrix::new(elements.num_points), + placeholder_indices: placeholder_indices.clone(), + free_regions: SparseBitMatrix::new(num_universal_regions), + placeholders: SparseBitMatrix::new(num_placeholders), + } + } + + /// Adds the given element to the value for the given region. Returns whether + /// the element is newly added (i.e., was not already present). + pub(crate) fn add_element(&mut self, r: N, elem: impl ToElementIndex) -> bool { + debug!("add(r={:?}, elem={:?})", r, elem); + elem.add_to_row(self, r) + } + + /// Adds all the control-flow points to the values for `r`. + pub(crate) fn add_all_points(&mut self, r: N) { + self.points.insert_all_into_row(r); + } + + /// Adds all elements in `r_from` to `r_to` (because e.g., `r_to: + /// r_from`). + pub(crate) fn add_region(&mut self, r_to: N, r_from: N) -> bool { + self.points.union_rows(r_from, r_to) + | self.free_regions.union_rows(r_from, r_to) + | self.placeholders.union_rows(r_from, r_to) + } + + /// Returns `true` if the region `r` contains the given element. + pub(crate) fn contains(&self, r: N, elem: impl ToElementIndex) -> bool { + elem.contained_in_row(self, r) + } + + /// `self[to] |= values[from]`, essentially: that is, take all the + /// elements for the region `from` from `values` and add them to + /// the region `to` in `self`. + pub(crate) fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) { + if let Some(set) = values.points.row(from) { + self.points.union_row(to, set); + } + } + + /// Returns `true` if `sup_region` contains all the CFG points that + /// `sub_region` contains. Ignores universal regions. + pub(crate) fn contains_points(&self, sup_region: N, sub_region: N) -> bool { + if let Some(sub_row) = self.points.row(sub_region) { + if let Some(sup_row) = self.points.row(sup_region) { + sup_row.superset(sub_row) + } else { + // sup row is empty, so sub row must be empty + sub_row.is_empty() + } + } else { + // sub row is empty, always true + true + } + } + + /// Returns the locations contained within a given region `r`. + pub(crate) fn locations_outlived_by<'a>(&'a self, r: N) -> impl Iterator<Item = Location> + 'a { + self.points.row(r).into_iter().flat_map(move |set| { + set.iter() + .take_while(move |&p| self.elements.point_in_range(p)) + .map(move |p| self.elements.to_location(p)) + }) + } + + /// Returns just the universal regions that are contained in a given region's value. + pub(crate) fn universal_regions_outlived_by<'a>( + &'a self, + r: N, + ) -> impl Iterator<Item = RegionVid> + 'a { + self.free_regions.row(r).into_iter().flat_map(|set| set.iter()) + } + + /// Returns all the elements contained in a given region's value. + pub(crate) fn placeholders_contained_in<'a>( + &'a self, + r: N, + ) -> impl Iterator<Item = ty::PlaceholderRegion> + 'a { + self.placeholders + .row(r) + .into_iter() + .flat_map(|set| set.iter()) + .map(move |p| self.placeholder_indices.lookup_placeholder(p)) + } + + /// Returns all the elements contained in a given region's value. + pub(crate) fn elements_contained_in<'a>( + &'a self, + r: N, + ) -> impl Iterator<Item = RegionElement> + 'a { + let points_iter = self.locations_outlived_by(r).map(RegionElement::Location); + + let free_regions_iter = + self.universal_regions_outlived_by(r).map(RegionElement::RootUniversalRegion); + + let placeholder_universes_iter = + self.placeholders_contained_in(r).map(RegionElement::PlaceholderRegion); + + points_iter.chain(free_regions_iter).chain(placeholder_universes_iter) + } + + /// Returns a "pretty" string value of the region. Meant for debugging. + pub(crate) fn region_value_str(&self, r: N) -> String { + region_value_str(self.elements_contained_in(r)) + } +} + +pub(crate) trait ToElementIndex: Debug + Copy { + fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool; + + fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool; +} + +impl ToElementIndex for Location { + fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool { + let index = values.elements.point_from_location(self); + values.points.insert(row, index) + } + + fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool { + let index = values.elements.point_from_location(self); + values.points.contains(row, index) + } +} + +impl ToElementIndex for RegionVid { + fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool { + values.free_regions.insert(row, self) + } + + fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool { + values.free_regions.contains(row, self) + } +} + +impl ToElementIndex for ty::PlaceholderRegion { + fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool { + let index = values.placeholder_indices.lookup_index(self); + values.placeholders.insert(row, index) + } + + fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool { + let index = values.placeholder_indices.lookup_index(self); + values.placeholders.contains(row, index) + } +} + +pub(crate) fn location_set_str( + elements: &RegionValueElements, + points: impl IntoIterator<Item = PointIndex>, +) -> String { + region_value_str( + points + .into_iter() + .take_while(|&p| elements.point_in_range(p)) + .map(|p| elements.to_location(p)) + .map(RegionElement::Location), + ) +} + +fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String { + let mut result = String::new(); + result.push('{'); + + // Set to Some(l1, l2) when we have observed all the locations + // from l1..=l2 (inclusive) but not yet printed them. This + // gets extended if we then see l3 where l3 is the successor + // to l2. + let mut open_location: Option<(Location, Location)> = None; + + let mut sep = ""; + let mut push_sep = |s: &mut String| { + s.push_str(sep); + sep = ", "; + }; + + for element in elements { + match element { + RegionElement::Location(l) => { + if let Some((location1, location2)) = open_location { + if location2.block == l.block + && location2.statement_index == l.statement_index - 1 + { + open_location = Some((location1, l)); + continue; + } + + push_sep(&mut result); + push_location_range(&mut result, location1, location2); + } + + open_location = Some((l, l)); + } + + RegionElement::RootUniversalRegion(fr) => { + if let Some((location1, location2)) = open_location { + push_sep(&mut result); + push_location_range(&mut result, location1, location2); + open_location = None; + } + + push_sep(&mut result); + result.push_str(&format!("{:?}", fr)); + } + + RegionElement::PlaceholderRegion(placeholder) => { + if let Some((location1, location2)) = open_location { + push_sep(&mut result); + push_location_range(&mut result, location1, location2); + open_location = None; + } + + push_sep(&mut result); + result.push_str(&format!("{:?}", placeholder)); + } + } + } + + if let Some((location1, location2)) = open_location { + push_sep(&mut result); + push_location_range(&mut result, location1, location2); + } + + result.push('}'); + + return result; + + fn push_location_range(str: &mut String, location1: Location, location2: Location) { + if location1 == location2 { + str.push_str(&format!("{:?}", location1)); + } else { + assert_eq!(location1.block, location2.block); + str.push_str(&format!( + "{:?}[{}..={}]", + location1.block, location1.statement_index, location2.statement_index + )); + } + } +} |