diff options
| -rw-r--r-- | compiler/rustc_trait_selection/src/traits/project.rs | 268 | ||||
| -rw-r--r-- | compiler/rustc_trait_selection/src/traits/query/normalize.rs | 29 |
2 files changed, 193 insertions, 104 deletions
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs index 8433b4ecb0a..4f74f86564d 100644 --- a/compiler/rustc_trait_selection/src/traits/project.rs +++ b/compiler/rustc_trait_selection/src/traits/project.rs @@ -298,6 +298,7 @@ struct AssocTypeNormalizer<'a, 'b, 'tcx> { cause: ObligationCause<'tcx>, obligations: &'a mut Vec<PredicateObligation<'tcx>>, depth: usize, + universes: Vec<Option<ty::UniverseIndex>>, } impl<'a, 'b, 'tcx> AssocTypeNormalizer<'a, 'b, 'tcx> { @@ -308,12 +309,16 @@ impl<'a, 'b, 'tcx> AssocTypeNormalizer<'a, 'b, 'tcx> { depth: usize, obligations: &'a mut Vec<PredicateObligation<'tcx>>, ) -> AssocTypeNormalizer<'a, 'b, 'tcx> { - AssocTypeNormalizer { selcx, param_env, cause, obligations, depth } + AssocTypeNormalizer { selcx, param_env, cause, obligations, depth, universes: vec![] } } fn fold<T: TypeFoldable<'tcx>>(&mut self, value: T) -> T { let value = self.selcx.infcx().resolve_vars_if_possible(value); + if value.has_escaping_bound_vars() { + bug!("Normalizing without wrapping in a `Binder`"); + } + if !value.has_projections() { value } else { value.fold_with(self) } } } @@ -323,6 +328,16 @@ impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> { self.selcx.tcx() } + fn fold_binder<T: TypeFoldable<'tcx>>( + &mut self, + t: ty::Binder<'tcx, T>, + ) -> ty::Binder<'tcx, T> { + self.universes.push(None); + let t = t.super_fold_with(self); + self.universes.pop(); + t + } + fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { if !ty.has_projections() { return ty; @@ -412,37 +427,40 @@ impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> { // give up and fall back to pretending like we never tried! let infcx = self.selcx.infcx(); - let (data, mapped_regions, mapped_types, mapped_consts, universe_map) = - BoundVarReplacer::replace_bound_vars(infcx, data); - - let normalized_ty = opt_normalize_projection_type( - self.selcx, - self.param_env, - data, - self.cause.clone(), - self.depth, - &mut self.obligations, - ) - .ok() - .flatten() - .unwrap_or_else(|| ty); - - let normalized_ty = PlaceholderReplacer::replace_placeholders( - infcx, - mapped_regions, - mapped_types, - mapped_consts, - universe_map, - normalized_ty, - ); - debug!( - ?self.depth, - ?ty, - ?normalized_ty, - obligations.len = ?self.obligations.len(), - "AssocTypeNormalizer: normalized type" - ); - normalized_ty + let replaced = + BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data); + if let Some((data, mapped_regions, mapped_types, mapped_consts)) = replaced { + let normalized_ty = opt_normalize_projection_type( + self.selcx, + self.param_env, + data, + self.cause.clone(), + self.depth, + &mut self.obligations, + ) + .ok() + .flatten() + .unwrap_or_else(|| ty); + + let normalized_ty = PlaceholderReplacer::replace_placeholders( + infcx, + mapped_regions, + mapped_types, + mapped_consts, + &self.universes, + normalized_ty, + ); + debug!( + ?self.depth, + ?ty, + ?normalized_ty, + obligations.len = ?self.obligations.len(), + "AssocTypeNormalizer: normalized type" + ); + normalized_ty + } else { + ty + } } _ => ty, @@ -460,26 +478,42 @@ impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> { } pub struct BoundVarReplacer<'me, 'tcx> { - pub infcx: &'me InferCtxt<'me, 'tcx>, - pub mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, - pub mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, - pub mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>, - pub universes: BTreeMap<ty::DebruijnIndex, ty::UniverseIndex>, - pub universes_inverse: BTreeMap<ty::UniverseIndex, ty::DebruijnIndex>, - pub current_index: ty::DebruijnIndex, + infcx: &'me InferCtxt<'me, 'tcx>, + // These three maps track the bound variable that were replaced by placeholders. It might be + // nice to remove these since we already have the `kind` in the placeholder; we really just need + // the `var` (but we *could* bring that into scope if we were to track them as we pass them). + mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, + mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, + mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>, + // The current depth relative to *this* folding, *not* the entire normalization. In other words, + // the depth of binders we've passed here. + current_index: ty::DebruijnIndex, + // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy: + // we don't actually create a universe until we see a bound var we have to replace. + universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>, + // FIXME: So, this is a less-than-ideal solution to a problem we want to solve eventually. Ideally, we + // shouldn't need to worry about bound vars for which we haven't passed (`self.current_index`) + // or that we don't explicitly know about (`self.universe_indices`). This is true for + // `AssocTypeNormalizer` but not `QueryNormalizer` currently. When we can always know about + // any binding levels above us, we can remove this. (The alternative would be + // `outer_exclusive_binder`, but that only exists on `Ty`. Otherwise, we would have to visit + // through the `T`, which we specifically want to avoid not being lazy.) + failed: bool, } impl<'me, 'tcx> BoundVarReplacer<'me, 'tcx> { + /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that + /// use a binding level above `universe_indices.len()`, we fail. pub fn replace_bound_vars<T: TypeFoldable<'tcx>>( infcx: &'me InferCtxt<'me, 'tcx>, + universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>, value: T, - ) -> ( + ) -> Option<( T, BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, BTreeMap<ty::PlaceholderType, ty::BoundTy>, BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>, - BTreeMap<ty::UniverseIndex, ty::DebruijnIndex>, - ) { + )> { let mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion> = BTreeMap::new(); let mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy> = BTreeMap::new(); let mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar> = BTreeMap::new(); @@ -489,20 +523,16 @@ impl<'me, 'tcx> BoundVarReplacer<'me, 'tcx> { mapped_regions, mapped_types, mapped_consts, - universes: BTreeMap::new(), - universes_inverse: BTreeMap::new(), current_index: ty::INNERMOST, + universe_indices, + failed: false, }; let value = value.super_fold_with(&mut replacer); - ( - value, - replacer.mapped_regions, - replacer.mapped_types, - replacer.mapped_consts, - replacer.universes_inverse, - ) + (!replacer.failed).then(|| { + (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts) + }) } } @@ -523,15 +553,24 @@ impl TypeFolder<'tcx> for BoundVarReplacer<'_, 'tcx> { fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { match *r { - ty::ReLateBound(debruijn, br) => { + ty::ReLateBound(debruijn, _) + if debruijn.as_usize() + 1 + > self.current_index.as_usize() + self.universe_indices.len() => + { + self.failed = true; + r + } + ty::ReLateBound(debruijn, br) if debruijn >= self.current_index => { let infcx = self.infcx; - let placeholder_db_index = - ty::DebruijnIndex::from_u32(self.current_index.as_u32() - debruijn.as_u32()); - let universe = *self - .universes - .entry(placeholder_db_index) - .or_insert_with(|| infcx.create_next_universe()); - self.universes_inverse.insert(universe, placeholder_db_index); + let index = self.universe_indices.len() - debruijn.as_usize() + + self.current_index.as_usize() + - 1; + let universe = self.universe_indices[index].unwrap_or_else(|| { + for i in self.universe_indices.iter_mut().take(index + 1) { + *i = i.or_else(|| Some(infcx.create_next_universe())) + } + self.universe_indices[index].unwrap() + }); let p = ty::PlaceholderRegion { universe, name: br.kind }; self.mapped_regions.insert(p.clone(), br); self.infcx.tcx.mk_region(ty::RePlaceholder(p)) @@ -542,15 +581,24 @@ impl TypeFolder<'tcx> for BoundVarReplacer<'_, 'tcx> { fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { match *t.kind() { - ty::Bound(debruijn, bound_ty) => { + ty::Bound(debruijn, _) + if debruijn.as_usize() + 1 + > self.current_index.as_usize() + self.universe_indices.len() => + { + self.failed = true; + t + } + ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => { let infcx = self.infcx; - let placeholder_db_index = - ty::DebruijnIndex::from_u32(self.current_index.as_u32() - debruijn.as_u32()); - let universe = *self - .universes - .entry(placeholder_db_index) - .or_insert_with(|| infcx.create_next_universe()); - self.universes_inverse.insert(universe, placeholder_db_index); + let index = self.universe_indices.len() - debruijn.as_usize() + + self.current_index.as_usize() + - 1; + let universe = self.universe_indices[index].unwrap_or_else(|| { + for i in self.universe_indices.iter_mut().take(index + 1) { + *i = i.or_else(|| Some(infcx.create_next_universe())) + } + self.universe_indices[index].unwrap() + }); let p = ty::PlaceholderType { universe, name: bound_ty.var }; self.mapped_types.insert(p.clone(), bound_ty); self.infcx.tcx.mk_ty(ty::Placeholder(p)) @@ -562,15 +610,26 @@ impl TypeFolder<'tcx> for BoundVarReplacer<'_, 'tcx> { fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { match *ct { - ty::Const { val: ty::ConstKind::Bound(debruijn, bound_const), ty } => { + ty::Const { val: ty::ConstKind::Bound(debruijn, _), ty: _ } + if debruijn.as_usize() + 1 + > self.current_index.as_usize() + self.universe_indices.len() => + { + self.failed = true; + ct + } + ty::Const { val: ty::ConstKind::Bound(debruijn, bound_const), ty } + if debruijn >= self.current_index => + { let infcx = self.infcx; - let placeholder_db_index = - ty::DebruijnIndex::from_u32(self.current_index.as_u32() - debruijn.as_u32()); - let universe = *self - .universes - .entry(placeholder_db_index) - .or_insert_with(|| infcx.create_next_universe()); - self.universes_inverse.insert(universe, placeholder_db_index); + let index = self.universe_indices.len() - debruijn.as_usize() + + self.current_index.as_usize() + - 1; + let universe = self.universe_indices[index].unwrap_or_else(|| { + for i in self.universe_indices.iter_mut().take(index + 1) { + *i = i.or_else(|| Some(infcx.create_next_universe())) + } + self.universe_indices[index].unwrap() + }); let p = ty::PlaceholderConst { universe, name: ty::BoundConst { var: bound_const, ty }, @@ -584,13 +643,14 @@ impl TypeFolder<'tcx> for BoundVarReplacer<'_, 'tcx> { } } +// The inverse of `BoundVarReplacer`: replaces placeholders with the bound vars from which they came. pub struct PlaceholderReplacer<'me, 'tcx> { - pub infcx: &'me InferCtxt<'me, 'tcx>, - pub mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, - pub mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, - pub mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>, - pub universes_inverse: BTreeMap<ty::UniverseIndex, ty::DebruijnIndex>, - pub current_index: ty::DebruijnIndex, + infcx: &'me InferCtxt<'me, 'tcx>, + mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, + mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, + mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>, + universe_indices: &'me Vec<Option<ty::UniverseIndex>>, + current_index: ty::DebruijnIndex, } impl<'me, 'tcx> PlaceholderReplacer<'me, 'tcx> { @@ -599,7 +659,7 @@ impl<'me, 'tcx> PlaceholderReplacer<'me, 'tcx> { mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>, - universes_inverse: BTreeMap<ty::UniverseIndex, ty::DebruijnIndex>, + universe_indices: &'me Vec<Option<ty::UniverseIndex>>, value: T, ) -> T { let mut replacer = PlaceholderReplacer { @@ -607,7 +667,7 @@ impl<'me, 'tcx> PlaceholderReplacer<'me, 'tcx> { mapped_regions, mapped_types, mapped_consts, - universes_inverse, + universe_indices, current_index: ty::INNERMOST, }; value.super_fold_with(&mut replacer) @@ -648,13 +708,15 @@ impl TypeFolder<'tcx> for PlaceholderReplacer<'_, 'tcx> { let replace_var = self.mapped_regions.get(&p); match replace_var { Some(replace_var) => { - let db = self - .universes_inverse - .get(&p.universe) + let index = self + .universe_indices + .iter() + .position(|u| matches!(u, Some(pu) if *pu == p.universe)) .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); - let index = - ty::DebruijnIndex::from_u32(db.as_u32() + self.current_index.as_u32()); - self.tcx().mk_region(ty::ReLateBound(index, *replace_var)) + let db = ty::DebruijnIndex::from_usize( + self.universe_indices.len() - index + self.current_index.as_usize() - 1, + ); + self.tcx().mk_region(ty::ReLateBound(db, *replace_var)) } None => r1, } @@ -673,13 +735,15 @@ impl TypeFolder<'tcx> for PlaceholderReplacer<'_, 'tcx> { let replace_var = self.mapped_types.get(&p); match replace_var { Some(replace_var) => { - let db = self - .universes_inverse - .get(&p.universe) + let index = self + .universe_indices + .iter() + .position(|u| matches!(u, Some(pu) if *pu == p.universe)) .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); - let index = - ty::DebruijnIndex::from_u32(db.as_u32() + self.current_index.as_u32()); - self.tcx().mk_ty(ty::Bound(index, *replace_var)) + let db = ty::DebruijnIndex::from_usize( + self.universe_indices.len() - index + self.current_index.as_usize() - 1, + ); + self.tcx().mk_ty(ty::Bound(db, *replace_var)) } None => ty, } @@ -695,14 +759,16 @@ impl TypeFolder<'tcx> for PlaceholderReplacer<'_, 'tcx> { let replace_var = self.mapped_consts.get(&p); match replace_var { Some(replace_var) => { - let db = self - .universes_inverse - .get(&p.universe) + let index = self + .universe_indices + .iter() + .position(|u| matches!(u, Some(pu) if *pu == p.universe)) .unwrap_or_else(|| bug!("Unexpected placeholder universe.")); - let index = - ty::DebruijnIndex::from_u32(db.as_u32() + self.current_index.as_u32()); + let db = ty::DebruijnIndex::from_usize( + self.universe_indices.len() - index + self.current_index.as_usize() - 1, + ); self.tcx() - .mk_const(ty::Const { val: ty::ConstKind::Bound(index, *replace_var), ty }) + .mk_const(ty::Const { val: ty::ConstKind::Bound(db, *replace_var), ty }) } None => ct, } diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs index 004372dd8b7..1f0f4a88a73 100644 --- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs +++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs @@ -61,6 +61,7 @@ impl<'cx, 'tcx> AtExt<'tcx> for At<'cx, 'tcx> { error: false, cache: SsoHashMap::new(), anon_depth: 0, + universes: vec![], }; let result = value.fold_with(&mut normalizer); @@ -91,6 +92,7 @@ struct QueryNormalizer<'cx, 'tcx> { cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>, error: bool, anon_depth: usize, + universes: Vec<Option<ty::UniverseIndex>>, } impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> { @@ -98,6 +100,16 @@ impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> { self.infcx.tcx } + fn fold_binder<T: TypeFoldable<'tcx>>( + &mut self, + t: ty::Binder<'tcx, T>, + ) -> ty::Binder<'tcx, T> { + self.universes.push(None); + let t = t.super_fold_with(self); + self.universes.pop(); + t + } + #[instrument(level = "debug", skip(self))] fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { if !ty.has_projections() { @@ -216,8 +228,19 @@ impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> { let tcx = self.infcx.tcx; let infcx = self.infcx; - let (data, mapped_regions, mapped_types, mapped_consts, universe_map) = - crate::traits::project::BoundVarReplacer::replace_bound_vars(infcx, data); + let replaced = crate::traits::project::BoundVarReplacer::replace_bound_vars( + infcx, + &mut self.universes, + data, + ); + let (data, mapped_regions, mapped_types, mapped_consts) = match replaced { + Some(r) => r, + None => { + bug!("{:?} {:?}", data, self.universes); + //self.error = true; + //return ty.super_fold_with(self); + } + }; let data = data.super_fold_with(self); let mut orig_values = OriginalQueryValues::default(); @@ -263,7 +286,7 @@ impl<'cx, 'tcx> TypeFolder<'tcx> for QueryNormalizer<'cx, 'tcx> { mapped_regions, mapped_types, mapped_consts, - universe_map, + &self.universes, normalized_ty, ) } |