use rustc_data_structures::intern::Interned;
use rustc_index::vec::{Idx, IndexVec};
use rustc_middle::ty::fold::TypeFoldable;
+use rustc_middle::ty::PlaceholderRegion;
use rustc_middle::ty::{self, Ty, TyCtxt};
-use rustc_middle::ty::{ReEarlyBound, ReEmpty, ReErased, ReFree, ReStatic};
+use rustc_middle::ty::{ReEarlyBound, ReErased, ReFree, ReStatic};
use rustc_middle::ty::{ReLateBound, RePlaceholder, ReVar};
use rustc_middle::ty::{Region, RegionVid};
use rustc_span::Span;
#[derive(Copy, Clone, Debug)]
pub(crate) enum VarValue<'tcx> {
+ /// Empty lifetime is for data that is never accessed. We tag the
+ /// empty lifetime with a universe -- the idea is that we don't
+ /// want `exists<'a> { forall<'b> { 'b: 'a } }` to be satisfiable.
+ /// Therefore, the `'empty` in a universe `U` is less than all
+ /// regions visible from `U`, but not less than regions not visible
+ /// from `U`.
+ Empty(ty::UniverseIndex),
Value(Region<'tcx>),
ErrorValue,
}
&mut self,
errors: &mut Vec<RegionResolutionError<'tcx>>,
) -> LexicalRegionResolutions<'tcx> {
- let mut var_data = self.construct_var_data(self.tcx());
+ let mut var_data = self.construct_var_data();
if cfg!(debug_assertions) {
self.dump_constraints();
/// Initially, the value for all variables is set to `'empty`, the
/// empty region. The `expansion` phase will grow this larger.
- fn construct_var_data(&self, tcx: TyCtxt<'tcx>) -> LexicalRegionResolutions<'tcx> {
+ fn construct_var_data(&self) -> LexicalRegionResolutions<'tcx> {
LexicalRegionResolutions {
values: IndexVec::from_fn_n(
|vid| {
let vid_universe = self.var_infos[vid].universe;
- let re_empty = tcx.mk_region(ty::ReEmpty(vid_universe));
- VarValue::Value(re_empty)
+ VarValue::Empty(vid_universe)
},
self.num_vars(),
),
}
}
+ /// Gets the LUb of a given region and the empty region
+ fn lub_empty(&self, a_region: Region<'tcx>) -> Result<Region<'tcx>, PlaceholderRegion> {
+ match *a_region {
+ ReLateBound(..) | ReErased => {
+ bug!("cannot relate region: {:?}", a_region);
+ }
+
+ ReVar(v_id) => {
+ span_bug!(
+ self.var_infos[v_id].origin.span(),
+ "lub invoked with non-concrete regions: {:?}",
+ a_region,
+ );
+ }
+
+ ReStatic => {
+ // nothing lives longer than `'static`
+ Ok(self.tcx().lifetimes.re_static)
+ }
+
+ ReEarlyBound(_) | ReFree(_) => {
+ // All empty regions are less than early-bound, free,
+ // and scope regions.
+ Ok(a_region)
+ }
+
+ RePlaceholder(placeholder) => Err(placeholder),
+ }
+ }
+
fn expansion(&self, var_values: &mut LexicalRegionResolutions<'tcx>) {
+ // In the first pass, we expand region vids according to constraints we
+ // have previously found. In the second pass, we loop through the region
+ // vids we expanded and expand *across* region vids (effectively
+ // "expanding" new `RegSubVar` constraints).
+
+ // Tracks the `VarSubVar` constraints generated for each region vid. We
+ // later use this to expand across vids.
let mut constraints = IndexVec::from_elem_n(Vec::new(), var_values.values.len());
+ // Tracks the changed region vids.
let mut changes = Vec::new();
for constraint in self.data.constraints.keys() {
- let (a_vid, a_region, b_vid, b_data) = match *constraint {
+ match *constraint {
Constraint::RegSubVar(a_region, b_vid) => {
let b_data = var_values.value_mut(b_vid);
- (None, a_region, b_vid, b_data)
+
+ if self.expand_node(a_region, b_vid, b_data) {
+ changes.push(b_vid);
+ }
}
Constraint::VarSubVar(a_vid, b_vid) => match *var_values.value(a_vid) {
VarValue::ErrorValue => continue,
+ VarValue::Empty(a_universe) => {
+ let b_data = var_values.value_mut(b_vid);
+
+ let changed = (|| match *b_data {
+ VarValue::Empty(b_universe) => {
+ // Empty regions are ordered according to the universe
+ // they are associated with.
+ let ui = a_universe.min(b_universe);
+
+ debug!(
+ "Expanding value of {:?} \
+ from empty lifetime with universe {:?} \
+ to empty lifetime with universe {:?}",
+ b_vid, b_universe, ui
+ );
+
+ *b_data = VarValue::Empty(ui);
+ true
+ }
+ VarValue::Value(cur_region) => {
+ let lub = match self.lub_empty(cur_region) {
+ Ok(r) => r,
+ // If the empty and placeholder regions are in the same universe,
+ // then the LUB is the Placeholder region (which is the cur_region).
+ // If they are not in the same universe, the LUB is the Static lifetime.
+ Err(placeholder) if a_universe == placeholder.universe => {
+ cur_region
+ }
+ Err(_) => self.tcx().lifetimes.re_static,
+ };
+
+ if lub == cur_region {
+ return false;
+ }
+
+ debug!(
+ "Expanding value of {:?} from {:?} to {:?}",
+ b_vid, cur_region, lub
+ );
+
+ *b_data = VarValue::Value(lub);
+ true
+ }
+
+ VarValue::ErrorValue => false,
+ })();
+
+ if changed {
+ changes.push(b_vid);
+ }
+ match b_data {
+ VarValue::Value(Region(Interned(ReStatic, _)))
+ | VarValue::ErrorValue => (),
+ _ => {
+ constraints[a_vid].push((a_vid, b_vid));
+ constraints[b_vid].push((a_vid, b_vid));
+ }
+ }
+ }
VarValue::Value(a_region) => {
let b_data = var_values.value_mut(b_vid);
- (Some(a_vid), a_region, b_vid, b_data)
+
+ if self.expand_node(a_region, b_vid, b_data) {
+ changes.push(b_vid);
+ }
+ match b_data {
+ VarValue::Value(Region(Interned(ReStatic, _)))
+ | VarValue::ErrorValue => (),
+ _ => {
+ constraints[a_vid].push((a_vid, b_vid));
+ constraints[b_vid].push((a_vid, b_vid));
+ }
+ }
}
},
Constraint::RegSubReg(..) | Constraint::VarSubReg(..) => {
// is done, in `collect_errors`.
continue;
}
- };
- if self.expand_node(a_region, b_vid, b_data) {
- changes.push(b_vid);
- }
- if let Some(a_vid) = a_vid {
- match b_data {
- VarValue::Value(Region(Interned(ReStatic, _))) | VarValue::ErrorValue => (),
- _ => {
- constraints[a_vid].push((a_vid, b_vid));
- constraints[b_vid].push((a_vid, b_vid));
- }
- }
}
}
}
}
+ /// Expands the value of the region represented with `b_vid` with current
+ /// value `b_data` to the lub of `b_data` and `a_region`. The corresponds
+ /// with the constraint `'?b: 'a` (`'a <: '?b`), where `'a` is some known
+ /// region and `'?b` is some region variable.
fn expand_node(
&self,
a_region: Region<'tcx>,
}
match *b_data {
+ VarValue::Empty(empty_ui) => {
+ let lub = match self.lub_empty(a_region) {
+ Ok(r) => r,
+ // If this empty region is from a universe that can
+ // name the placeholder, then the placeholder is
+ // larger; otherwise, the only ancestor is `'static`.
+ Err(placeholder) if empty_ui.can_name(placeholder.universe) => {
+ self.tcx().mk_region(RePlaceholder(placeholder))
+ }
+ Err(_) => self.tcx().lifetimes.re_static,
+ };
+
+ debug!("Expanding value of {:?} from empty lifetime to {:?}", b_vid, lub);
+
+ *b_data = VarValue::Value(lub);
+ true
+ }
VarValue::Value(cur_region) => {
// This is a specialized version of the `lub_concrete_regions`
// check below for a common case, here purely as an
// optimization.
let b_universe = self.var_infos[b_vid].universe;
- if let ReEmpty(a_universe) = *a_region && a_universe == b_universe {
- return false;
- }
let mut lub = self.lub_concrete_regions(a_region, cur_region);
if lub == cur_region {
}
}
+ /// True if `a <= b`.
+ fn sub_region_values(&self, a: VarValue<'tcx>, b: VarValue<'tcx>) -> bool {
+ match (a, b) {
+ // Error region is `'static`
+ (VarValue::ErrorValue, _) | (_, VarValue::ErrorValue) => return true,
+ (VarValue::Empty(a_ui), VarValue::Empty(b_ui)) => {
+ // Empty regions are ordered according to the universe
+ // they are associated with.
+ a_ui.min(b_ui) == b_ui
+ }
+ (VarValue::Value(a), VarValue::Empty(_)) => {
+ match *a {
+ ReLateBound(..) | ReErased => {
+ bug!("cannot relate region: {:?}", a);
+ }
+
+ ReVar(v_id) => {
+ span_bug!(
+ self.var_infos[v_id].origin.span(),
+ "lub_concrete_regions invoked with non-concrete region: {:?}",
+ a
+ );
+ }
+
+ ReStatic | ReEarlyBound(_) | ReFree(_) => {
+ // nothing lives longer than `'static`
+
+ // All empty regions are less than early-bound, free,
+ // and scope regions.
+
+ false
+ }
+
+ RePlaceholder(_) => {
+ // The LUB is either `a` or `'static`
+ false
+ }
+ }
+ }
+ (VarValue::Empty(a_ui), VarValue::Value(b)) => {
+ match *b {
+ ReLateBound(..) | ReErased => {
+ bug!("cannot relate region: {:?}", b);
+ }
+
+ ReVar(v_id) => {
+ span_bug!(
+ self.var_infos[v_id].origin.span(),
+ "lub_concrete_regions invoked with non-concrete regions: {:?}",
+ b
+ );
+ }
+
+ ReStatic | ReEarlyBound(_) | ReFree(_) => {
+ // nothing lives longer than `'static`
+ // All empty regions are less than early-bound, free,
+ // and scope regions.
+ true
+ }
+
+ RePlaceholder(placeholder) => {
+ // If this empty region is from a universe that can
+ // name the placeholder, then the placeholder is
+ // larger; otherwise, the only ancestor is `'static`.
+ if a_ui.can_name(placeholder.universe) { true } else { false }
+ }
+ }
+ }
+ (VarValue::Value(a), VarValue::Value(b)) => self.sub_concrete_regions(a, b),
+ }
+ }
+
/// True if `a <= b`, but not defined over inference variables.
#[instrument(level = "trace", skip(self))]
fn sub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> bool {
///
/// Neither `a` nor `b` may be an inference variable (hence the
/// term "concrete regions").
- #[instrument(level = "trace", skip(self))]
+ #[instrument(level = "trace", skip(self), ret)]
fn lub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> Region<'tcx> {
- let r = match (*a, *b) {
+ match (*a, *b) {
(ReLateBound(..), _) | (_, ReLateBound(..)) | (ReErased, _) | (_, ReErased) => {
bug!("cannot relate region: LUB({:?}, {:?})", a, b);
}
self.tcx().lifetimes.re_static
}
- (ReEmpty(_), ReEarlyBound(_) | ReFree(_)) => {
- // All empty regions are less than early-bound, free,
- // and scope regions.
- b
- }
-
- (ReEarlyBound(_) | ReFree(_), ReEmpty(_)) => {
- // All empty regions are less than early-bound, free,
- // and scope regions.
- a
- }
-
- (ReEmpty(a_ui), ReEmpty(b_ui)) => {
- // Empty regions are ordered according to the universe
- // they are associated with.
- let ui = a_ui.min(b_ui);
- self.tcx().mk_region(ReEmpty(ui))
- }
-
- (ReEmpty(empty_ui), RePlaceholder(placeholder))
- | (RePlaceholder(placeholder), ReEmpty(empty_ui)) => {
- // If this empty region is from a universe that can
- // name the placeholder, then the placeholder is
- // larger; otherwise, the only ancestor is `'static`.
- if empty_ui.can_name(placeholder.universe) {
- self.tcx().mk_region(RePlaceholder(placeholder))
- } else {
- self.tcx().lifetimes.re_static
- }
- }
-
(ReEarlyBound(_) | ReFree(_), ReEarlyBound(_) | ReFree(_)) => {
self.region_rels.lub_free_regions(a, b)
}
self.tcx().lifetimes.re_static
}
}
- };
-
- debug!("lub_concrete_regions({:?}, {:?}) = {:?}", a, b, r);
-
- r
+ }
}
/// After expansion is complete, go and check upper bounds (i.e.,
for (node_vid, value) in var_data.values.iter_enumerated() {
match *value {
- VarValue::Value(_) => { /* Inference successful */ }
+ VarValue::Empty(_) | VarValue::Value(_) => { /* Inference successful */ }
VarValue::ErrorValue => {
// Inference impossible: this value contains
// inconsistent constraints.
}
VerifyBound::OutlivedBy(r) => {
- self.sub_concrete_regions(min, var_values.normalize(self.tcx(), *r))
+ let a = match *min {
+ ty::ReVar(rid) => var_values.values[rid],
+ _ => VarValue::Value(min),
+ };
+ let b = match **r {
+ ty::ReVar(rid) => var_values.values[rid],
+ _ => VarValue::Value(*r),
+ };
+ self.sub_region_values(a, b)
}
- VerifyBound::IsEmpty => {
- matches!(*min, ty::ReEmpty(_))
- }
+ VerifyBound::IsEmpty => match *min {
+ ty::ReVar(rid) => match var_values.values[rid] {
+ VarValue::ErrorValue => false,
+ VarValue::Empty(_) => true,
+ VarValue::Value(_) => false,
+ },
+ _ => false,
+ },
VerifyBound::AnyBound(bs) => {
bs.iter().any(|b| self.bound_is_met(b, var_values, generic_ty, min))
) -> ty::Region<'tcx> {
let result = match *r {
ty::ReVar(rid) => match self.values[rid] {
+ VarValue::Empty(_) => r,
VarValue::Value(r) => r,
VarValue::ErrorValue => tcx.lifetimes.re_static,
},
projects / rustc.git / blobdiff