diff options
Diffstat (limited to 'compiler/rustc_middle/src/ty/fold.rs')
| -rw-r--r-- | compiler/rustc_middle/src/ty/fold.rs | 281 |
1 files changed, 38 insertions, 243 deletions
diff --git a/compiler/rustc_middle/src/ty/fold.rs b/compiler/rustc_middle/src/ty/fold.rs index 6b9a37d84..d66f436f9 100644 --- a/compiler/rustc_middle/src/ty/fold.rs +++ b/compiler/rustc_middle/src/ty/fold.rs @@ -1,210 +1,10 @@ -//! A folding traversal mechanism for complex data structures that contain type -//! information. -//! -//! This is a modifying traversal. It consumes the data structure, producing a -//! (possibly) modified version of it. Both fallible and infallible versions are -//! available. The name is potentially confusing, because this traversal is more -//! like `Iterator::map` than `Iterator::fold`. -//! -//! This traversal has limited flexibility. Only a small number of "types of -//! interest" within the complex data structures can receive custom -//! modification. These are the ones containing the most important type-related -//! information, such as `Ty`, `Predicate`, `Region`, and `Const`. -//! -//! There are three groups of traits involved in each traversal. -//! - `TypeFoldable`. This is implemented once for many types, including: -//! - Types of interest, for which the methods delegate to the folder. -//! - All other types, including generic containers like `Vec` and `Option`. -//! It defines a "skeleton" of how they should be folded. -//! - `TypeSuperFoldable`. This is implemented only for each type of interest, -//! and defines the folding "skeleton" for these types. -//! - `TypeFolder`/`FallibleTypeFolder. One of these is implemented for each -//! folder. This defines how types of interest are folded. -//! -//! This means each fold is a mixture of (a) generic folding operations, and (b) -//! custom fold operations that are specific to the folder. -//! - The `TypeFoldable` impls handle most of the traversal, and call into -//! `TypeFolder`/`FallibleTypeFolder` when they encounter a type of interest. -//! - A `TypeFolder`/`FallibleTypeFolder` may call into another `TypeFoldable` -//! impl, because some of the types of interest are recursive and can contain -//! other types of interest. -//! - A `TypeFolder`/`FallibleTypeFolder` may also call into a `TypeSuperFoldable` -//! impl, because each folder might provide custom handling only for some types -//! of interest, or only for some variants of each type of interest, and then -//! use default traversal for the remaining cases. -//! -//! For example, if you have `struct S(Ty, U)` where `S: TypeFoldable` and `U: -//! TypeFoldable`, and an instance `s = S(ty, u)`, it would be folded like so: -//! ```text -//! s.fold_with(folder) calls -//! - ty.fold_with(folder) calls -//! - folder.fold_ty(ty) may call -//! - ty.super_fold_with(folder) -//! - u.fold_with(folder) -//! ``` -use crate::ty::{self, Binder, BoundTy, Ty, TyCtxt, TypeVisitable}; +use crate::ty::{self, Binder, BoundTy, Ty, TyCtxt, TypeVisitableExt}; use rustc_data_structures::fx::FxIndexMap; use rustc_hir::def_id::DefId; use std::collections::BTreeMap; -/// This trait is implemented for every type that can be folded, -/// providing the skeleton of the traversal. -/// -/// To implement this conveniently, use the derive macro located in -/// `rustc_macros`. -pub trait TypeFoldable<'tcx>: TypeVisitable<'tcx> { - /// The entry point for folding. To fold a value `t` with a folder `f` - /// call: `t.try_fold_with(f)`. - /// - /// For most types, this just traverses the value, calling `try_fold_with` - /// on each field/element. - /// - /// For types of interest (such as `Ty`), the implementation of method - /// calls a folder method specifically for that type (such as - /// `F::try_fold_ty`). This is where control transfers from `TypeFoldable` - /// to `TypeFolder`. - fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error>; - - /// A convenient alternative to `try_fold_with` for use with infallible - /// folders. Do not override this method, to ensure coherence with - /// `try_fold_with`. - fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self { - self.try_fold_with(folder).into_ok() - } -} - -// This trait is implemented for types of interest. -pub trait TypeSuperFoldable<'tcx>: TypeFoldable<'tcx> { - /// Provides a default fold for a type of interest. This should only be - /// called within `TypeFolder` methods, when a non-custom traversal is - /// desired for the value of the type of interest passed to that method. - /// For example, in `MyFolder::try_fold_ty(ty)`, it is valid to call - /// `ty.try_super_fold_with(self)`, but any other folding should be done - /// with `xyz.try_fold_with(self)`. - fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>( - self, - folder: &mut F, - ) -> Result<Self, F::Error>; - - /// A convenient alternative to `try_super_fold_with` for use with - /// infallible folders. Do not override this method, to ensure coherence - /// with `try_super_fold_with`. - fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self { - self.try_super_fold_with(folder).into_ok() - } -} - -/// This trait is implemented for every infallible folding traversal. There is -/// a fold method defined for every type of interest. Each such method has a -/// default that does an "identity" fold. Implementations of these methods -/// often fall back to a `super_fold_with` method if the primary argument -/// doesn't satisfy a particular condition. -/// -/// A blanket implementation of [`FallibleTypeFolder`] will defer to -/// the infallible methods of this trait to ensure that the two APIs -/// are coherent. -pub trait TypeFolder<'tcx>: FallibleTypeFolder<'tcx, Error = !> { - fn tcx<'a>(&'a self) -> TyCtxt<'tcx>; - - fn fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Binder<'tcx, T> - where - T: TypeFoldable<'tcx>, - { - t.super_fold_with(self) - } - - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - t.super_fold_with(self) - } - - fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - r.super_fold_with(self) - } - - fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { - c.super_fold_with(self) - } - - fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { - p.super_fold_with(self) - } -} - -/// This trait is implemented for every folding traversal. There is a fold -/// method defined for every type of interest. Each such method has a default -/// that does an "identity" fold. -/// -/// A blanket implementation of this trait (that defers to the relevant -/// method of [`TypeFolder`]) is provided for all infallible folders in -/// order to ensure the two APIs are coherent. -pub trait FallibleTypeFolder<'tcx>: Sized { - type Error; - - fn tcx<'a>(&'a self) -> TyCtxt<'tcx>; - - fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, Self::Error> - where - T: TypeFoldable<'tcx>, - { - t.try_super_fold_with(self) - } - - fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> { - t.try_super_fold_with(self) - } - - fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> { - r.try_super_fold_with(self) - } - - fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> { - c.try_super_fold_with(self) - } - - fn try_fold_predicate( - &mut self, - p: ty::Predicate<'tcx>, - ) -> Result<ty::Predicate<'tcx>, Self::Error> { - p.try_super_fold_with(self) - } -} - -// This blanket implementation of the fallible trait for infallible folders -// delegates to infallible methods to ensure coherence. -impl<'tcx, F> FallibleTypeFolder<'tcx> for F -where - F: TypeFolder<'tcx>, -{ - type Error = !; - - fn tcx<'a>(&'a self) -> TyCtxt<'tcx> { - TypeFolder::tcx(self) - } - - fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, !> - where - T: TypeFoldable<'tcx>, - { - Ok(self.fold_binder(t)) - } - - fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, !> { - Ok(self.fold_ty(t)) - } - - fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, !> { - Ok(self.fold_region(r)) - } - - fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, !> { - Ok(self.fold_const(c)) - } - - fn try_fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> Result<ty::Predicate<'tcx>, !> { - Ok(self.fold_predicate(p)) - } -} +pub use rustc_type_ir::fold::{FallibleTypeFolder, TypeFoldable, TypeFolder, TypeSuperFoldable}; /////////////////////////////////////////////////////////////////////////// // Some sample folders @@ -221,13 +21,13 @@ where pub ct_op: H, } -impl<'tcx, F, G, H> TypeFolder<'tcx> for BottomUpFolder<'tcx, F, G, H> +impl<'tcx, F, G, H> TypeFolder<TyCtxt<'tcx>> for BottomUpFolder<'tcx, F, G, H> where F: FnMut(Ty<'tcx>) -> Ty<'tcx>, G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>, H: FnMut(ty::Const<'tcx>) -> ty::Const<'tcx>, { - fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { self.tcx } @@ -260,7 +60,7 @@ impl<'tcx> TyCtxt<'tcx> { mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, ) -> T where - T: TypeFoldable<'tcx>, + T: TypeFoldable<TyCtxt<'tcx>>, { value.fold_with(&mut RegionFolder::new(self, &mut f)) } @@ -271,7 +71,7 @@ impl<'tcx> TyCtxt<'tcx> { mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, ) -> T where - T: TypeSuperFoldable<'tcx>, + T: TypeSuperFoldable<TyCtxt<'tcx>>, { value.super_fold_with(&mut RegionFolder::new(self, &mut f)) } @@ -311,12 +111,12 @@ impl<'a, 'tcx> RegionFolder<'a, 'tcx> { } } -impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> { - fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { +impl<'a, 'tcx> TypeFolder<TyCtxt<'tcx>> for RegionFolder<'a, 'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { self.tcx } - fn fold_binder<T: TypeFoldable<'tcx>>( + fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( &mut self, t: ty::Binder<'tcx, T>, ) -> ty::Binder<'tcx, T> { @@ -385,15 +185,15 @@ impl<'tcx, D: BoundVarReplacerDelegate<'tcx>> BoundVarReplacer<'tcx, D> { } } -impl<'tcx, D> TypeFolder<'tcx> for BoundVarReplacer<'tcx, D> +impl<'tcx, D> TypeFolder<TyCtxt<'tcx>> for BoundVarReplacer<'tcx, D> where D: BoundVarReplacerDelegate<'tcx>, { - fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { self.tcx } - fn fold_binder<T: TypeFoldable<'tcx>>( + fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( &mut self, t: ty::Binder<'tcx, T>, ) -> ty::Binder<'tcx, T> { @@ -425,7 +225,7 @@ where // debruijn index. Then we adjust it to the // correct depth. assert_eq!(debruijn1, ty::INNERMOST); - self.tcx.reuse_or_mk_region(region, ty::ReLateBound(debruijn, br)) + self.tcx.mk_re_late_bound(debruijn, br) } else { region } @@ -471,7 +271,7 @@ impl<'tcx> TyCtxt<'tcx> { ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>) where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, - T: TypeFoldable<'tcx>, + T: TypeFoldable<TyCtxt<'tcx>>, { let mut region_map = BTreeMap::new(); let real_fld_r = |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br)); @@ -486,7 +286,7 @@ impl<'tcx> TyCtxt<'tcx> { ) -> T where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, - T: TypeFoldable<'tcx>, + T: TypeFoldable<TyCtxt<'tcx>>, { let value = value.skip_binder(); if !value.has_escaping_bound_vars() { @@ -505,7 +305,7 @@ impl<'tcx> TyCtxt<'tcx> { /// Replaces all escaping bound vars. The `fld_r` closure replaces escaping /// bound regions; the `fld_t` closure replaces escaping bound types and the `fld_c` /// closure replaces escaping bound consts. - pub fn replace_escaping_bound_vars_uncached<T: TypeFoldable<'tcx>>( + pub fn replace_escaping_bound_vars_uncached<T: TypeFoldable<TyCtxt<'tcx>>>( self, value: T, delegate: impl BoundVarReplacerDelegate<'tcx>, @@ -521,7 +321,7 @@ impl<'tcx> TyCtxt<'tcx> { /// Replaces all types or regions bound by the given `Binder`. The `fld_r` /// closure replaces bound regions, the `fld_t` closure replaces bound /// types, and `fld_c` replaces bound constants. - pub fn replace_bound_vars_uncached<T: TypeFoldable<'tcx>>( + pub fn replace_bound_vars_uncached<T: TypeFoldable<TyCtxt<'tcx>>>( self, value: Binder<'tcx, T>, delegate: impl BoundVarReplacerDelegate<'tcx>, @@ -537,35 +337,29 @@ impl<'tcx> TyCtxt<'tcx> { value: ty::Binder<'tcx, T>, ) -> T where - T: TypeFoldable<'tcx>, + T: TypeFoldable<TyCtxt<'tcx>>, { self.replace_late_bound_regions_uncached(value, |br| { - self.mk_region(ty::ReFree(ty::FreeRegion { - scope: all_outlive_scope, - bound_region: br.kind, - })) + self.mk_re_free(all_outlive_scope, br.kind) }) } pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T where - T: TypeFoldable<'tcx>, + T: TypeFoldable<TyCtxt<'tcx>>, { let shift_bv = |bv: ty::BoundVar| ty::BoundVar::from_usize(bv.as_usize() + bound_vars); self.replace_escaping_bound_vars_uncached( value, FnMutDelegate { regions: &mut |r: ty::BoundRegion| { - self.mk_region(ty::ReLateBound( + self.mk_re_late_bound( ty::INNERMOST, ty::BoundRegion { var: shift_bv(r.var), kind: r.kind }, - )) + ) }, types: &mut |t: ty::BoundTy| { - self.mk_ty(ty::Bound( - ty::INNERMOST, - ty::BoundTy { var: shift_bv(t.var), kind: t.kind }, - )) + self.mk_bound(ty::INNERMOST, ty::BoundTy { var: shift_bv(t.var), kind: t.kind }) }, consts: &mut |c, ty: Ty<'tcx>| { self.mk_const(ty::ConstKind::Bound(ty::INNERMOST, shift_bv(c)), ty) @@ -578,7 +372,7 @@ impl<'tcx> TyCtxt<'tcx> { /// method lookup and a few other places where precise region relationships are not required. pub fn erase_late_bound_regions<T>(self, value: Binder<'tcx, T>) -> T where - T: TypeFoldable<'tcx>, + T: TypeFoldable<TyCtxt<'tcx>>, { self.replace_late_bound_regions(value, |_| self.lifetimes.re_erased).0 } @@ -586,7 +380,7 @@ impl<'tcx> TyCtxt<'tcx> { /// Anonymize all bound variables in `value`, this is mostly used to improve caching. pub fn anonymize_bound_vars<T>(self, value: Binder<'tcx, T>) -> Binder<'tcx, T> where - T: TypeFoldable<'tcx>, + T: TypeFoldable<TyCtxt<'tcx>>, { struct Anonymize<'a, 'tcx> { tcx: TyCtxt<'tcx>, @@ -603,16 +397,18 @@ impl<'tcx> TyCtxt<'tcx> { }) .expect_region(); let br = ty::BoundRegion { var, kind }; - self.tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)) + self.tcx.mk_re_late_bound(ty::INNERMOST, br) } fn replace_ty(&mut self, bt: ty::BoundTy) -> Ty<'tcx> { let entry = self.map.entry(bt.var); let index = entry.index(); let var = ty::BoundVar::from_usize(index); let kind = entry - .or_insert_with(|| ty::BoundVariableKind::Ty(ty::BoundTyKind::Anon)) + .or_insert_with(|| { + ty::BoundVariableKind::Ty(ty::BoundTyKind::Anon(index as u32)) + }) .expect_ty(); - self.tcx.mk_ty(ty::Bound(ty::INNERMOST, BoundTy { var, kind })) + self.tcx.mk_bound(ty::INNERMOST, BoundTy { var, kind }) } fn replace_const(&mut self, bv: ty::BoundVar, ty: Ty<'tcx>) -> ty::Const<'tcx> { let entry = self.map.entry(bv); @@ -626,7 +422,7 @@ impl<'tcx> TyCtxt<'tcx> { let mut map = Default::default(); let delegate = Anonymize { tcx: self, map: &mut map }; let inner = self.replace_escaping_bound_vars_uncached(value.skip_binder(), delegate); - let bound_vars = self.mk_bound_variable_kinds(map.into_values()); + let bound_vars = self.mk_bound_variable_kinds_from_iter(map.into_values()); Binder::bind_with_vars(inner, bound_vars) } } @@ -652,12 +448,12 @@ impl<'tcx> Shifter<'tcx> { } } -impl<'tcx> TypeFolder<'tcx> for Shifter<'tcx> { - fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { +impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Shifter<'tcx> { + fn interner(&self) -> TyCtxt<'tcx> { self.tcx } - fn fold_binder<T: TypeFoldable<'tcx>>( + fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>( &mut self, t: ty::Binder<'tcx, T>, ) -> ty::Binder<'tcx, T> { @@ -671,8 +467,7 @@ impl<'tcx> TypeFolder<'tcx> for Shifter<'tcx> { match *r { ty::ReLateBound(debruijn, br) if debruijn >= self.current_index => { let debruijn = debruijn.shifted_in(self.amount); - let shifted = ty::ReLateBound(debruijn, br); - self.tcx.mk_region(shifted) + self.tcx.mk_re_late_bound(debruijn, br) } _ => r, } @@ -682,7 +477,7 @@ impl<'tcx> TypeFolder<'tcx> for Shifter<'tcx> { match *ty.kind() { ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => { let debruijn = debruijn.shifted_in(self.amount); - self.tcx.mk_ty(ty::Bound(debruijn, bound_ty)) + self.tcx.mk_bound(debruijn, bound_ty) } _ if ty.has_vars_bound_at_or_above(self.current_index) => ty.super_fold_with(self), @@ -713,7 +508,7 @@ pub fn shift_region<'tcx>( ) -> ty::Region<'tcx> { match *region { ty::ReLateBound(debruijn, br) if amount > 0 => { - tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), br)) + tcx.mk_re_late_bound(debruijn.shifted_in(amount), br) } _ => region, } @@ -721,7 +516,7 @@ pub fn shift_region<'tcx>( pub fn shift_vars<'tcx, T>(tcx: TyCtxt<'tcx>, value: T, amount: u32) -> T where - T: TypeFoldable<'tcx>, + T: TypeFoldable<TyCtxt<'tcx>>, { debug!("shift_vars(value={:?}, amount={})", value, amount); |