From 17d40c6057c88f4c432b0d7bac88e1b84cb7e67f Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:03:36 +0200 Subject: Adding upstream version 1.65.0+dfsg1. Signed-off-by: Daniel Baumann --- .../src/infer/lexical_region_resolve/mod.rs | 307 ++++++++++++++++----- 1 file changed, 241 insertions(+), 66 deletions(-) (limited to 'compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs') diff --git a/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs b/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs index 3783cfb4c..5f13b2b3d 100644 --- a/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs +++ b/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs @@ -15,8 +15,9 @@ use rustc_data_structures::graph::implementation::{ 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; @@ -51,6 +52,13 @@ pub struct LexicalRegionResolutions<'tcx> { #[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, } @@ -117,7 +125,7 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { &mut self, errors: &mut Vec>, ) -> 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(); @@ -137,13 +145,12 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { /// 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(), ), @@ -189,20 +196,131 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { } } + /// Gets the LUb of a given region and the empty region + fn lub_empty(&self, a_region: Region<'tcx>) -> Result, 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(..) => { @@ -210,18 +328,6 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { // 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)); - } - } } } @@ -242,6 +348,10 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { } } + /// 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>, @@ -263,14 +373,28 @@ impl<'cx, 'tcx> LexicalResolver<'cx, '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 { @@ -300,6 +424,78 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { } } + /// 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 { @@ -333,9 +529,9 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { /// /// 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); } @@ -355,37 +551,6 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { 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) } @@ -399,11 +564,7 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { self.tcx().lifetimes.re_static } } - }; - - debug!("lub_concrete_regions({:?}, {:?}) = {:?}", a, b, r); - - r + } } /// After expansion is complete, go and check upper bounds (i.e., @@ -512,7 +673,7 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { 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. @@ -833,12 +994,25 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> { } 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)) @@ -880,6 +1054,7 @@ impl<'tcx> LexicalRegionResolutions<'tcx> { ) -> 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, }, -- cgit v1.2.3