From 142359c2204f8be1d1efbf9ae8558bf7135a1618 Mon Sep 17 00:00:00 2001 From: scalexm Date: Wed, 24 Oct 2018 23:41:40 +0200 Subject: [PATCH] Extend `ty::fold::RegionReplacer` to `ty::fold::BoundVarReplacer` Use the new `BoundVarReplacer` to perform canonical substitutions. --- src/librustc/infer/canonical/substitute.rs | 89 ++------- src/librustc/ty/fold.rs | 200 ++++++++++++++------- 2 files changed, 149 insertions(+), 140 deletions(-) diff --git a/src/librustc/infer/canonical/substitute.rs b/src/librustc/infer/canonical/substitute.rs index 7839c892266..3fd86f9c6a1 100644 --- a/src/librustc/infer/canonical/substitute.rs +++ b/src/librustc/infer/canonical/substitute.rs @@ -17,9 +17,9 @@ //! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html use infer::canonical::{Canonical, CanonicalVarValues}; -use ty::fold::{TypeFoldable, TypeFolder}; +use ty::fold::TypeFoldable; use ty::subst::UnpackedKind; -use ty::{self, Ty, TyCtxt}; +use ty::{self, TyCtxt}; impl<'tcx, V> Canonical<'tcx, V> { /// Instantiate the wrapped value, replacing each canonical value @@ -65,82 +65,21 @@ pub(super) fn substitute_value<'a, 'tcx, T>( { if var_values.var_values.is_empty() { value.clone() - } else if !value.has_escaping_bound_vars() { - // There are no bound vars to substitute. - value.clone() } else { - value.fold_with(&mut CanonicalVarValuesSubst { - tcx, - var_values, - binder_index: ty::INNERMOST, - }) - } -} - -struct CanonicalVarValuesSubst<'cx, 'gcx: 'tcx, 'tcx: 'cx> { - tcx: TyCtxt<'cx, 'gcx, 'tcx>, - var_values: &'cx CanonicalVarValues<'tcx>, - binder_index: ty::DebruijnIndex, -} - -impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for CanonicalVarValuesSubst<'cx, 'gcx, 'tcx> { - fn tcx(&self) -> TyCtxt<'_, 'gcx, 'tcx> { - self.tcx - } - - fn fold_binder(&mut self, t: &ty::Binder) -> ty::Binder - where T: TypeFoldable<'tcx> - { - self.binder_index.shift_in(1); - let t = t.super_fold_with(self); - self.binder_index.shift_out(1); - t - } - - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - match t.sty { - ty::Bound(b) => { - if b.index == self.binder_index { - match self.var_values.var_values[b.var].unpack() { - UnpackedKind::Type(ty) => ty::fold::shift_vars( - self.tcx, - &ty, - self.binder_index.index() as u32 - ), - r => bug!("{:?} is a type but value is {:?}", b, r), - } - } else { - t - } + let fld_r = |br: ty::BoundRegion| { + match var_values.var_values[br.as_bound_var()].unpack() { + UnpackedKind::Lifetime(l) => l, + r => bug!("{:?} is a region but value is {:?}", br, r), } - _ => { - if !t.has_vars_bound_at_or_above(self.binder_index) { - // Nothing more to substitute. - t - } else { - t.super_fold_with(self) - } - } - } - } + }; - fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - match r { - ty::RegionKind::ReLateBound(index, br) => { - if *index == self.binder_index { - match self.var_values.var_values[br.as_bound_var()].unpack() { - UnpackedKind::Lifetime(l) => ty::fold::shift_region( - self.tcx, - l, - self.binder_index.index() as u32, - ), - r => bug!("{:?} is a region but value is {:?}", br, r), - } - } else { - r - } + let fld_t = |bound_ty: ty::BoundTy| { + match var_values.var_values[bound_ty.var].unpack() { + UnpackedKind::Type(ty) => ty, + r => bug!("{:?} is a type but value is {:?}", bound_ty, r), } - _ => r.super_fold_with(self), - } + }; + + tcx.replace_escaping_bound_vars(value, fld_r, fld_t) } } diff --git a/src/librustc/ty/fold.rs b/src/librustc/ty/fold.rs index 31542582f94..06cc316f788 100644 --- a/src/librustc/ty/fold.rs +++ b/src/librustc/ty/fold.rs @@ -416,11 +416,10 @@ fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { } /////////////////////////////////////////////////////////////////////////// -// Late-bound region replacer +// Bound vars replacer -// Replaces the escaping regions in a type. - -struct RegionReplacer<'a, 'gcx: 'a+'tcx, 'tcx: 'a> { +/// Replaces the escaping bound vars (late bound regions or bound types) in a type. +struct BoundVarReplacer<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> { tcx: TyCtxt<'a, 'gcx, 'tcx>, /// As with `RegionFolder`, represents the index of a binder *just outside* @@ -428,7 +427,82 @@ struct RegionReplacer<'a, 'gcx: 'a+'tcx, 'tcx: 'a> { current_index: ty::DebruijnIndex, fld_r: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a), - map: BTreeMap> + fld_t: &'a mut (dyn FnMut(ty::BoundTy) -> ty::Ty<'tcx> + 'a), +} + +impl<'a, 'gcx, 'tcx> BoundVarReplacer<'a, 'gcx, 'tcx> { + fn new( + tcx: TyCtxt<'a, 'gcx, 'tcx>, + fld_r: &'a mut F, + fld_t: &'a mut G + ) -> Self + where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, + G: FnMut(ty::BoundTy) -> ty::Ty<'tcx> + { + BoundVarReplacer { + tcx, + current_index: ty::INNERMOST, + fld_r, + fld_t, + } + } +} + +impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for BoundVarReplacer<'a, 'gcx, 'tcx> { + fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx } + + fn fold_binder>(&mut self, t: &ty::Binder) -> ty::Binder { + self.current_index.shift_in(1); + let t = t.super_fold_with(self); + self.current_index.shift_out(1); + t + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + match t.sty { + ty::Bound(bound_ty) => { + if bound_ty.index == self.current_index { + let fld_t = &mut self.fld_t; + let ty = fld_t(bound_ty); + ty::fold::shift_vars( + self.tcx, + &ty, + self.current_index.as_u32() + ) + } else { + t + } + } + _ => { + if !t.has_vars_bound_at_or_above(self.current_index) { + // Nothing more to substitute. + t + } else { + t.super_fold_with(self) + } + } + } + } + + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + match *r { + ty::ReLateBound(debruijn, br) if debruijn == self.current_index => { + let fld_r = &mut self.fld_r; + let region = fld_r(br); + if let ty::ReLateBound(debruijn1, br) = *region { + // If the callback returns a late-bound region, + // that region should always use the INNERMOST + // debruijn index. Then we adjust it to the + // correct depth. + assert_eq!(debruijn1, ty::INNERMOST); + self.tcx.mk_region(ty::ReLateBound(debruijn, br)) + } else { + region + } + } + _ => r + } + } } impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { @@ -440,16 +514,65 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { /// same `BoundRegion` will reuse the previous result. A map is /// returned at the end with each bound region and the free region /// that replaced it. - pub fn replace_late_bound_regions(self, + /// + /// This method only replaces late bound regions and the result may still + /// contain escaping bound types. + pub fn replace_late_bound_regions( + self, value: &Binder, - mut f: F) - -> (T, BTreeMap>) - where F : FnMut(ty::BoundRegion) -> ty::Region<'tcx>, - T : TypeFoldable<'tcx>, + mut fld_r: F + ) -> (T, BTreeMap>) + where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, + T: TypeFoldable<'tcx> { - let mut replacer = RegionReplacer::new(self, &mut f); + let mut map = BTreeMap::new(); + let mut real_fldr = |br| { + *map.entry(br).or_insert_with(|| fld_r(br)) + }; + + // identity for bound types + let mut fld_t = |bound_ty| self.mk_ty(ty::Bound(bound_ty)); + + let mut replacer = BoundVarReplacer::new(self, &mut real_fldr, &mut fld_t); let result = value.skip_binder().fold_with(&mut replacer); - (result, replacer.map) + (result, map) + } + + /// Replace all escaping bound vars. The `fld_r` closure replaces escaping + /// bound regions while the `flr_t` closure replaces escaping bound types. + pub fn replace_escaping_bound_vars( + self, + value: &T, + mut fld_r: F, + mut fld_t: G + ) -> T + where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, + G: FnMut(ty::BoundTy) -> ty::Ty<'tcx>, + T: TypeFoldable<'tcx> + { + if !value.has_escaping_bound_vars() { + value.clone() + } else { + let mut replacer = BoundVarReplacer::new(self, &mut fld_r, &mut fld_t); + let result = value.fold_with(&mut replacer); + result + } + } + + /// Replace all types or regions bound by the given `Binder`. The `fld_r` + /// closure replaces bound regions while the `flr_t` closure replaces bound + /// types. + pub fn replace_bound_vars( + self, + value: &Binder, + fld_r: F, + fld_t: G + ) -> T + where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, + G: FnMut(ty::BoundTy) -> ty::Ty<'tcx>, + T: TypeFoldable<'tcx> + { + self.replace_escaping_bound_vars(value.skip_binder(), fld_r, fld_t) } /// Replace any late-bound regions bound in `value` with @@ -549,59 +672,6 @@ pub fn anonymize_late_bound_regions(self, sig: &Binder) -> Binder } } -impl<'a, 'gcx, 'tcx> RegionReplacer<'a, 'gcx, 'tcx> { - fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>, fld_r: &'a mut F) - -> RegionReplacer<'a, 'gcx, 'tcx> - where F : FnMut(ty::BoundRegion) -> ty::Region<'tcx> - { - RegionReplacer { - tcx, - current_index: ty::INNERMOST, - fld_r, - map: BTreeMap::default() - } - } -} - -impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> { - fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx } - - fn fold_binder>(&mut self, t: &ty::Binder) -> ty::Binder { - self.current_index.shift_in(1); - let t = t.super_fold_with(self); - self.current_index.shift_out(1); - t - } - - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - if !t.has_vars_bound_at_or_above(self.current_index) { - return t; - } - - t.super_fold_with(self) - } - - fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - match *r { - ty::ReLateBound(debruijn, br) if debruijn == self.current_index => { - let fld_r = &mut self.fld_r; - let region = *self.map.entry(br).or_insert_with(|| fld_r(br)); - if let ty::ReLateBound(debruijn1, br) = *region { - // If the callback returns a late-bound region, - // that region should always use the INNERMOST - // debruijn index. Then we adjust it to the - // correct depth. - assert_eq!(debruijn1, ty::INNERMOST); - self.tcx.mk_region(ty::ReLateBound(debruijn, br)) - } else { - region - } - } - _ => r - } - } -} - /////////////////////////////////////////////////////////////////////////// // Shifter // -- 2.44.0