diff options
Diffstat (limited to 'compiler/rustc_middle')
| -rw-r--r-- | compiler/rustc_middle/src/arena.rs | 1 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/consts.rs | 15 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/context.rs | 10 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/flags.rs | 359 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/generic_args.rs | 15 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/list.rs | 8 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/mod.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/pattern.rs | 47 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/sty.rs | 15 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/walk.rs | 217 |
10 files changed, 93 insertions, 596 deletions
diff --git a/compiler/rustc_middle/src/arena.rs b/compiler/rustc_middle/src/arena.rs index 98273a05446..d1bbb0598fe 100644 --- a/compiler/rustc_middle/src/arena.rs +++ b/compiler/rustc_middle/src/arena.rs @@ -89,7 +89,6 @@ macro_rules! arena_types { [] name_set: rustc_data_structures::unord::UnordSet<rustc_span::Symbol>, [] autodiff_item: rustc_ast::expand::autodiff_attrs::AutoDiffItem, [] ordered_name_set: rustc_data_structures::fx::FxIndexSet<rustc_span::Symbol>, - [] pats: rustc_middle::ty::PatternKind<'tcx>, [] valtree: rustc_middle::ty::ValTreeKind<'tcx>, // Note that this deliberately duplicates items in the `rustc_hir::arena`, diff --git a/compiler/rustc_middle/src/ty/consts.rs b/compiler/rustc_middle/src/ty/consts.rs index ae1c6c670cb..dc5fe2d8f8b 100644 --- a/compiler/rustc_middle/src/ty/consts.rs +++ b/compiler/rustc_middle/src/ty/consts.rs @@ -3,6 +3,7 @@ use std::borrow::Cow; use rustc_data_structures::intern::Interned; use rustc_error_messages::MultiSpan; use rustc_macros::HashStable; +use rustc_type_ir::walk::TypeWalker; use rustc_type_ir::{self as ir, TypeFlags, WithCachedTypeInfo}; use crate::ty::{self, Ty, TyCtxt}; @@ -243,4 +244,18 @@ impl<'tcx> Const<'tcx> { pub fn is_ct_infer(self) -> bool { matches!(self.kind(), ty::ConstKind::Infer(_)) } + + /// Iterator that walks `self` and any types reachable from + /// `self`, in depth-first order. Note that just walks the types + /// that appear in `self`, it does not descend into the fields of + /// structs or variants. For example: + /// + /// ```text + /// isize => { isize } + /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } + /// [isize] => { [isize], isize } + /// ``` + pub fn walk(self) -> TypeWalker<TyCtxt<'tcx>> { + TypeWalker::new(self.into()) + } } diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs index abf6cbbcd87..6e5ac13bd2c 100644 --- a/compiler/rustc_middle/src/ty/context.rs +++ b/compiler/rustc_middle/src/ty/context.rs @@ -870,7 +870,7 @@ impl<'tcx> CtxtInterners<'tcx> { Ty(Interned::new_unchecked( self.type_ .intern(kind, |kind| { - let flags = super::flags::FlagComputation::for_kind(&kind); + let flags = ty::FlagComputation::<TyCtxt<'tcx>>::for_kind(&kind); let stable_hash = self.stable_hash(&flags, sess, untracked, &kind); InternedInSet(self.arena.alloc(WithCachedTypeInfo { @@ -896,7 +896,7 @@ impl<'tcx> CtxtInterners<'tcx> { Const(Interned::new_unchecked( self.const_ .intern(kind, |kind: ty::ConstKind<'_>| { - let flags = super::flags::FlagComputation::for_const_kind(&kind); + let flags = ty::FlagComputation::<TyCtxt<'tcx>>::for_const_kind(&kind); let stable_hash = self.stable_hash(&flags, sess, untracked, &kind); InternedInSet(self.arena.alloc(WithCachedTypeInfo { @@ -912,7 +912,7 @@ impl<'tcx> CtxtInterners<'tcx> { fn stable_hash<'a, T: HashStable<StableHashingContext<'a>>>( &self, - flags: &ty::flags::FlagComputation, + flags: &ty::FlagComputation<TyCtxt<'tcx>>, sess: &'a Session, untracked: &'a Untracked, val: &T, @@ -940,7 +940,7 @@ impl<'tcx> CtxtInterners<'tcx> { Predicate(Interned::new_unchecked( self.predicate .intern(kind, |kind| { - let flags = super::flags::FlagComputation::for_predicate(kind); + let flags = ty::FlagComputation::<TyCtxt<'tcx>>::for_predicate(kind); let stable_hash = self.stable_hash(&flags, sess, untracked, &kind); @@ -961,7 +961,7 @@ impl<'tcx> CtxtInterners<'tcx> { } else { self.clauses .intern_ref(clauses, || { - let flags = super::flags::FlagComputation::for_clauses(clauses); + let flags = ty::FlagComputation::<TyCtxt<'tcx>>::for_clauses(clauses); InternedInSet(ListWithCachedTypeInfo::from_arena( &*self.arena, diff --git a/compiler/rustc_middle/src/ty/flags.rs b/compiler/rustc_middle/src/ty/flags.rs deleted file mode 100644 index 2424923fb78..00000000000 --- a/compiler/rustc_middle/src/ty/flags.rs +++ /dev/null @@ -1,359 +0,0 @@ -use std::slice; - -use crate::ty::{self, GenericArg, GenericArgKind, InferConst, Ty, TypeFlags}; - -#[derive(Debug)] -pub struct FlagComputation { - pub flags: TypeFlags, - - /// see `Ty::outer_exclusive_binder` for details - pub outer_exclusive_binder: ty::DebruijnIndex, -} - -impl FlagComputation { - fn new() -> FlagComputation { - FlagComputation { flags: TypeFlags::empty(), outer_exclusive_binder: ty::INNERMOST } - } - - #[allow(rustc::usage_of_ty_tykind)] - pub fn for_kind(kind: &ty::TyKind<'_>) -> FlagComputation { - let mut result = FlagComputation::new(); - result.add_kind(kind); - result - } - - pub fn for_predicate(binder: ty::Binder<'_, ty::PredicateKind<'_>>) -> FlagComputation { - let mut result = FlagComputation::new(); - result.add_predicate(binder); - result - } - - pub fn for_const_kind(kind: &ty::ConstKind<'_>) -> FlagComputation { - let mut result = FlagComputation::new(); - result.add_const_kind(kind); - result - } - - pub fn for_clauses(clauses: &[ty::Clause<'_>]) -> FlagComputation { - let mut result = FlagComputation::new(); - for c in clauses { - result.add_flags(c.as_predicate().flags()); - result.add_exclusive_binder(c.as_predicate().outer_exclusive_binder()); - } - result - } - - fn add_flags(&mut self, flags: TypeFlags) { - self.flags = self.flags | flags; - } - - /// indicates that `self` refers to something at binding level `binder` - fn add_bound_var(&mut self, binder: ty::DebruijnIndex) { - let exclusive_binder = binder.shifted_in(1); - self.add_exclusive_binder(exclusive_binder); - } - - /// indicates that `self` refers to something *inside* binding - /// level `binder` -- not bound by `binder`, but bound by the next - /// binder internal to it - fn add_exclusive_binder(&mut self, exclusive_binder: ty::DebruijnIndex) { - self.outer_exclusive_binder = self.outer_exclusive_binder.max(exclusive_binder); - } - - /// Adds the flags/depth from a set of types that appear within the current type, but within a - /// region binder. - fn bound_computation<T, F>(&mut self, value: ty::Binder<'_, T>, f: F) - where - F: FnOnce(&mut Self, T), - { - let mut computation = FlagComputation::new(); - - if !value.bound_vars().is_empty() { - computation.add_flags(TypeFlags::HAS_BINDER_VARS); - } - - f(&mut computation, value.skip_binder()); - - self.add_flags(computation.flags); - - // The types that contributed to `computation` occurred within - // a region binder, so subtract one from the region depth - // within when adding the depth to `self`. - let outer_exclusive_binder = computation.outer_exclusive_binder; - if outer_exclusive_binder > ty::INNERMOST { - self.add_exclusive_binder(outer_exclusive_binder.shifted_out(1)); - } // otherwise, this binder captures nothing - } - - #[allow(rustc::usage_of_ty_tykind)] - fn add_kind(&mut self, kind: &ty::TyKind<'_>) { - match kind { - &ty::Bool - | &ty::Char - | &ty::Int(_) - | &ty::Float(_) - | &ty::Uint(_) - | &ty::Never - | &ty::Str - | &ty::Foreign(..) => {} - - &ty::Error(_) => self.add_flags(TypeFlags::HAS_ERROR), - - &ty::Param(_) => { - self.add_flags(TypeFlags::HAS_TY_PARAM); - } - - &ty::Closure(_, args) - | &ty::Coroutine(_, args) - | &ty::CoroutineClosure(_, args) - | &ty::CoroutineWitness(_, args) => { - self.add_args(args); - } - - &ty::Bound(debruijn, _) => { - self.add_bound_var(debruijn); - self.add_flags(TypeFlags::HAS_TY_BOUND); - } - - &ty::Placeholder(..) => { - self.add_flags(TypeFlags::HAS_TY_PLACEHOLDER); - } - - &ty::Infer(infer) => match infer { - ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => { - self.add_flags(TypeFlags::HAS_TY_FRESH) - } - - ty::TyVar(_) | ty::IntVar(_) | ty::FloatVar(_) => { - self.add_flags(TypeFlags::HAS_TY_INFER) - } - }, - - &ty::Adt(_, args) => { - self.add_args(args); - } - - &ty::Alias(kind, data) => { - self.add_flags(match kind { - ty::Projection => TypeFlags::HAS_TY_PROJECTION, - ty::Weak => TypeFlags::HAS_TY_WEAK, - ty::Opaque => TypeFlags::HAS_TY_OPAQUE, - ty::Inherent => TypeFlags::HAS_TY_INHERENT, - }); - - self.add_alias_ty(data); - } - - &ty::Dynamic(obj, r, _) => { - for predicate in obj.iter() { - self.bound_computation(predicate, |computation, predicate| match predicate { - ty::ExistentialPredicate::Trait(tr) => computation.add_args(tr.args), - ty::ExistentialPredicate::Projection(p) => { - computation.add_existential_projection(&p); - } - ty::ExistentialPredicate::AutoTrait(_) => {} - }); - } - - self.add_region(r); - } - - &ty::Array(tt, len) => { - self.add_ty(tt); - self.add_const(len); - } - - &ty::Pat(ty, pat) => { - self.add_ty(ty); - match *pat { - ty::PatternKind::Range { start, end } => { - self.add_const(start); - self.add_const(end); - } - } - } - - &ty::Slice(tt) => self.add_ty(tt), - - &ty::RawPtr(ty, _) => { - self.add_ty(ty); - } - - &ty::Ref(r, ty, _) => { - self.add_region(r); - self.add_ty(ty); - } - - &ty::Tuple(types) => { - self.add_tys(types); - } - - &ty::FnDef(_, args) => { - self.add_args(args); - } - - &ty::FnPtr(sig_tys, _) => self.bound_computation(sig_tys, |computation, sig_tys| { - computation.add_tys(sig_tys.inputs_and_output); - }), - - &ty::UnsafeBinder(bound_ty) => { - self.bound_computation(bound_ty.into(), |computation, ty| { - computation.add_ty(ty); - }) - } - } - } - - fn add_predicate(&mut self, binder: ty::Binder<'_, ty::PredicateKind<'_>>) { - self.bound_computation(binder, |computation, atom| computation.add_predicate_atom(atom)); - } - - fn add_predicate_atom(&mut self, atom: ty::PredicateKind<'_>) { - match atom { - ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_pred)) => { - self.add_args(trait_pred.trait_ref.args); - } - ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(ty::HostEffectPredicate { - trait_ref, - constness: _, - })) => { - self.add_args(trait_ref.args); - } - ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(ty::OutlivesPredicate( - a, - b, - ))) => { - self.add_region(a); - self.add_region(b); - } - ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate( - ty, - region, - ))) => { - self.add_ty(ty); - self.add_region(region); - } - ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => { - self.add_const(ct); - self.add_ty(ty); - } - ty::PredicateKind::Subtype(ty::SubtypePredicate { a_is_expected: _, a, b }) => { - self.add_ty(a); - self.add_ty(b); - } - ty::PredicateKind::Coerce(ty::CoercePredicate { a, b }) => { - self.add_ty(a); - self.add_ty(b); - } - ty::PredicateKind::Clause(ty::ClauseKind::Projection(ty::ProjectionPredicate { - projection_term, - term, - })) => { - self.add_alias_term(projection_term); - self.add_term(term); - } - ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(arg)) => { - self.add_args(slice::from_ref(&arg)); - } - ty::PredicateKind::DynCompatible(_def_id) => {} - ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(uv)) => { - self.add_const(uv); - } - ty::PredicateKind::ConstEquate(expected, found) => { - self.add_const(expected); - self.add_const(found); - } - ty::PredicateKind::Ambiguous => {} - ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term }) => { - self.add_alias_term(alias); - self.add_term(term); - } - ty::PredicateKind::AliasRelate(t1, t2, _) => { - self.add_term(t1); - self.add_term(t2); - } - } - } - - fn add_ty(&mut self, ty: Ty<'_>) { - self.add_flags(ty.flags()); - self.add_exclusive_binder(ty.outer_exclusive_binder()); - } - - fn add_tys(&mut self, tys: &[Ty<'_>]) { - for &ty in tys { - self.add_ty(ty); - } - } - - fn add_region(&mut self, r: ty::Region<'_>) { - self.add_flags(r.type_flags()); - if let ty::ReBound(debruijn, _) = r.kind() { - self.add_bound_var(debruijn); - } - } - - fn add_const(&mut self, c: ty::Const<'_>) { - self.add_flags(c.flags()); - self.add_exclusive_binder(c.outer_exclusive_binder()); - } - - fn add_const_kind(&mut self, c: &ty::ConstKind<'_>) { - match *c { - ty::ConstKind::Unevaluated(uv) => { - self.add_args(uv.args); - self.add_flags(TypeFlags::HAS_CT_PROJECTION); - } - ty::ConstKind::Infer(infer) => match infer { - InferConst::Fresh(_) => self.add_flags(TypeFlags::HAS_CT_FRESH), - InferConst::Var(_) => self.add_flags(TypeFlags::HAS_CT_INFER), - }, - ty::ConstKind::Bound(debruijn, _) => { - self.add_bound_var(debruijn); - self.add_flags(TypeFlags::HAS_CT_BOUND); - } - ty::ConstKind::Param(_) => { - self.add_flags(TypeFlags::HAS_CT_PARAM); - } - ty::ConstKind::Placeholder(_) => { - self.add_flags(TypeFlags::HAS_CT_PLACEHOLDER); - } - ty::ConstKind::Value(cv) => self.add_ty(cv.ty), - ty::ConstKind::Expr(e) => self.add_args(e.args()), - ty::ConstKind::Error(_) => self.add_flags(TypeFlags::HAS_ERROR), - } - } - - fn add_existential_projection(&mut self, projection: &ty::ExistentialProjection<'_>) { - self.add_args(projection.args); - match projection.term.unpack() { - ty::TermKind::Ty(ty) => self.add_ty(ty), - ty::TermKind::Const(ct) => self.add_const(ct), - } - } - - fn add_alias_ty(&mut self, alias_ty: ty::AliasTy<'_>) { - self.add_args(alias_ty.args); - } - - fn add_alias_term(&mut self, alias_term: ty::AliasTerm<'_>) { - self.add_args(alias_term.args); - } - - fn add_args(&mut self, args: &[GenericArg<'_>]) { - for kind in args { - match kind.unpack() { - GenericArgKind::Type(ty) => self.add_ty(ty), - GenericArgKind::Lifetime(lt) => self.add_region(lt), - GenericArgKind::Const(ct) => self.add_const(ct), - } - } - } - - fn add_term(&mut self, term: ty::Term<'_>) { - match term.unpack() { - ty::TermKind::Ty(ty) => self.add_ty(ty), - ty::TermKind::Const(ct) => self.add_const(ct), - } - } -} diff --git a/compiler/rustc_middle/src/ty/generic_args.rs b/compiler/rustc_middle/src/ty/generic_args.rs index 9c1ff134f0f..1f04937232d 100644 --- a/compiler/rustc_middle/src/ty/generic_args.rs +++ b/compiler/rustc_middle/src/ty/generic_args.rs @@ -11,6 +11,7 @@ use rustc_hir::def_id::DefId; use rustc_macros::{HashStable, TyDecodable, TyEncodable, extension}; use rustc_serialize::{Decodable, Encodable}; use rustc_type_ir::WithCachedTypeInfo; +use rustc_type_ir::walk::TypeWalker; use smallvec::SmallVec; use crate::ty::codec::{TyDecoder, TyEncoder}; @@ -297,6 +298,20 @@ impl<'tcx> GenericArg<'tcx> { GenericArgKind::Const(ct) => ct.is_ct_infer(), } } + + /// Iterator that walks `self` and any types reachable from + /// `self`, in depth-first order. Note that just walks the types + /// that appear in `self`, it does not descend into the fields of + /// structs or variants. For example: + /// + /// ```text + /// isize => { isize } + /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } + /// [isize] => { [isize], isize } + /// ``` + pub fn walk(self) -> TypeWalker<TyCtxt<'tcx>> { + TypeWalker::new(self) + } } impl<'a, 'tcx> Lift<TyCtxt<'tcx>> for GenericArg<'a> { diff --git a/compiler/rustc_middle/src/ty/list.rs b/compiler/rustc_middle/src/ty/list.rs index 0fd370a5619..0cf5820959e 100644 --- a/compiler/rustc_middle/src/ty/list.rs +++ b/compiler/rustc_middle/src/ty/list.rs @@ -7,9 +7,9 @@ use std::{fmt, iter, mem, ptr, slice}; use rustc_data_structures::aligned::{Aligned, align_of}; use rustc_data_structures::sync::DynSync; use rustc_serialize::{Encodable, Encoder}; +use rustc_type_ir::FlagComputation; -use super::flags::FlagComputation; -use super::{DebruijnIndex, TypeFlags}; +use super::{DebruijnIndex, TyCtxt, TypeFlags}; use crate::arena::Arena; /// `List<T>` is a bit like `&[T]`, but with some critical differences. @@ -299,8 +299,8 @@ impl TypeInfo { } } -impl From<FlagComputation> for TypeInfo { - fn from(computation: FlagComputation) -> TypeInfo { +impl<'tcx> From<FlagComputation<TyCtxt<'tcx>>> for TypeInfo { + fn from(computation: FlagComputation<TyCtxt<'tcx>>) -> TypeInfo { TypeInfo { flags: computation.flags, outer_exclusive_binder: computation.outer_exclusive_binder, diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs index a2b3acac3f2..61e869f5de4 100644 --- a/compiler/rustc_middle/src/ty/mod.rs +++ b/compiler/rustc_middle/src/ty/mod.rs @@ -117,7 +117,6 @@ pub mod cast; pub mod codec; pub mod error; pub mod fast_reject; -pub mod flags; pub mod inhabitedness; pub mod layout; pub mod normalize_erasing_regions; @@ -128,7 +127,6 @@ pub mod significant_drop_order; pub mod trait_def; pub mod util; pub mod vtable; -pub mod walk; mod adt; mod assoc; diff --git a/compiler/rustc_middle/src/ty/pattern.rs b/compiler/rustc_middle/src/ty/pattern.rs index 4cad1ab2099..758adc42e3e 100644 --- a/compiler/rustc_middle/src/ty/pattern.rs +++ b/compiler/rustc_middle/src/ty/pattern.rs @@ -1,14 +1,40 @@ use std::fmt; use rustc_data_structures::intern::Interned; -use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable}; +use rustc_macros::HashStable; +use rustc_type_ir::ir_print::IrPrint; +use rustc_type_ir::{ + FlagComputation, Flags, {self as ir}, +}; +use super::TyCtxt; use crate::ty; +pub type PatternKind<'tcx> = ir::PatternKind<TyCtxt<'tcx>>; + #[derive(Copy, Clone, PartialEq, Eq, Hash, HashStable)] #[rustc_pass_by_value] pub struct Pattern<'tcx>(pub Interned<'tcx, PatternKind<'tcx>>); +impl<'tcx> Flags for Pattern<'tcx> { + fn flags(&self) -> rustc_type_ir::TypeFlags { + match &**self { + ty::PatternKind::Range { start, end } => { + FlagComputation::for_const_kind(&start.kind()).flags + | FlagComputation::for_const_kind(&end.kind()).flags + } + } + } + + fn outer_exclusive_binder(&self) -> rustc_type_ir::DebruijnIndex { + match &**self { + ty::PatternKind::Range { start, end } => { + start.outer_exclusive_binder().max(end.outer_exclusive_binder()) + } + } + } +} + impl<'tcx> std::ops::Deref for Pattern<'tcx> { type Target = PatternKind<'tcx>; @@ -23,9 +49,9 @@ impl<'tcx> fmt::Debug for Pattern<'tcx> { } } -impl<'tcx> fmt::Debug for PatternKind<'tcx> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - match *self { +impl<'tcx> IrPrint<PatternKind<'tcx>> for TyCtxt<'tcx> { + fn print(t: &PatternKind<'tcx>, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *t { PatternKind::Range { start, end } => { write!(f, "{start}")?; @@ -53,10 +79,15 @@ impl<'tcx> fmt::Debug for PatternKind<'tcx> { } } } + + fn print_debug(t: &PatternKind<'tcx>, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + Self::print(t, fmt) + } } -#[derive(Clone, PartialEq, Eq, Hash)] -#[derive(HashStable, TyEncodable, TyDecodable, TypeVisitable, TypeFoldable)] -pub enum PatternKind<'tcx> { - Range { start: ty::Const<'tcx>, end: ty::Const<'tcx> }, +impl<'tcx> rustc_type_ir::inherent::IntoKind for Pattern<'tcx> { + type Kind = PatternKind<'tcx>; + fn kind(self) -> Self::Kind { + *self + } } diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs index 27ee363f1c1..d9a65ae57a0 100644 --- a/compiler/rustc_middle/src/ty/sty.rs +++ b/compiler/rustc_middle/src/ty/sty.rs @@ -16,6 +16,7 @@ use rustc_hir::def_id::DefId; use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, extension}; use rustc_span::{DUMMY_SP, Span, Symbol, sym}; use rustc_type_ir::TyKind::*; +use rustc_type_ir::walk::TypeWalker; use rustc_type_ir::{self as ir, BoundVar, CollectAndApply, DynKind, TypeVisitableExt, elaborate}; use tracing::instrument; use ty::util::{AsyncDropGlueMorphology, IntTypeExt}; @@ -2029,6 +2030,20 @@ impl<'tcx> Ty<'tcx> { pub fn is_known_rigid(self) -> bool { self.kind().is_known_rigid() } + + /// Iterator that walks `self` and any types reachable from + /// `self`, in depth-first order. Note that just walks the types + /// that appear in `self`, it does not descend into the fields of + /// structs or variants. For example: + /// + /// ```text + /// isize => { isize } + /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } + /// [isize] => { [isize], isize } + /// ``` + pub fn walk(self) -> TypeWalker<TyCtxt<'tcx>> { + TypeWalker::new(self.into()) + } } impl<'tcx> rustc_type_ir::inherent::Tys<TyCtxt<'tcx>> for &'tcx ty::List<Ty<'tcx>> { diff --git a/compiler/rustc_middle/src/ty/walk.rs b/compiler/rustc_middle/src/ty/walk.rs deleted file mode 100644 index a23316ae6fc..00000000000 --- a/compiler/rustc_middle/src/ty/walk.rs +++ /dev/null @@ -1,217 +0,0 @@ -//! An iterator over the type substructure. -//! WARNING: this does not keep track of the region depth. - -use rustc_data_structures::sso::SsoHashSet; -use smallvec::{SmallVec, smallvec}; -use tracing::debug; - -use crate::ty::{self, GenericArg, GenericArgKind, Ty}; - -// The TypeWalker's stack is hot enough that it's worth going to some effort to -// avoid heap allocations. -type TypeWalkerStack<'tcx> = SmallVec<[GenericArg<'tcx>; 8]>; - -pub struct TypeWalker<'tcx> { - stack: TypeWalkerStack<'tcx>, - last_subtree: usize, - pub visited: SsoHashSet<GenericArg<'tcx>>, -} - -/// An iterator for walking the type tree. -/// -/// It's very easy to produce a deeply -/// nested type tree with a lot of -/// identical subtrees. In order to work efficiently -/// in this situation walker only visits each type once. -/// It maintains a set of visited types and -/// skips any types that are already there. -impl<'tcx> TypeWalker<'tcx> { - pub fn new(root: GenericArg<'tcx>) -> Self { - Self { stack: smallvec![root], last_subtree: 1, visited: SsoHashSet::new() } - } - - /// Skips the subtree corresponding to the last type - /// returned by `next()`. - /// - /// Example: Imagine you are walking `Foo<Bar<i32>, usize>`. - /// - /// ```ignore (illustrative) - /// let mut iter: TypeWalker = ...; - /// iter.next(); // yields Foo - /// iter.next(); // yields Bar<i32> - /// iter.skip_current_subtree(); // skips i32 - /// iter.next(); // yields usize - /// ``` - pub fn skip_current_subtree(&mut self) { - self.stack.truncate(self.last_subtree); - } -} - -impl<'tcx> Iterator for TypeWalker<'tcx> { - type Item = GenericArg<'tcx>; - - fn next(&mut self) -> Option<GenericArg<'tcx>> { - debug!("next(): stack={:?}", self.stack); - loop { - let next = self.stack.pop()?; - self.last_subtree = self.stack.len(); - if self.visited.insert(next) { - push_inner(&mut self.stack, next); - debug!("next: stack={:?}", self.stack); - return Some(next); - } - } - } -} - -impl<'tcx> GenericArg<'tcx> { - /// Iterator that walks `self` and any types reachable from - /// `self`, in depth-first order. Note that just walks the types - /// that appear in `self`, it does not descend into the fields of - /// structs or variants. For example: - /// - /// ```text - /// isize => { isize } - /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } - /// [isize] => { [isize], isize } - /// ``` - pub fn walk(self) -> TypeWalker<'tcx> { - TypeWalker::new(self) - } -} - -impl<'tcx> Ty<'tcx> { - /// Iterator that walks `self` and any types reachable from - /// `self`, in depth-first order. Note that just walks the types - /// that appear in `self`, it does not descend into the fields of - /// structs or variants. For example: - /// - /// ```text - /// isize => { isize } - /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } - /// [isize] => { [isize], isize } - /// ``` - pub fn walk(self) -> TypeWalker<'tcx> { - TypeWalker::new(self.into()) - } -} - -impl<'tcx> ty::Const<'tcx> { - /// Iterator that walks `self` and any types reachable from - /// `self`, in depth-first order. Note that just walks the types - /// that appear in `self`, it does not descend into the fields of - /// structs or variants. For example: - /// - /// ```text - /// isize => { isize } - /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } - /// [isize] => { [isize], isize } - /// ``` - pub fn walk(self) -> TypeWalker<'tcx> { - TypeWalker::new(self.into()) - } -} - -/// We push `GenericArg`s on the stack in reverse order so as to -/// maintain a pre-order traversal. As of the time of this -/// writing, the fact that the traversal is pre-order is not -/// known to be significant to any code, but it seems like the -/// natural order one would expect (basically, the order of the -/// types as they are written). -fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>) { - match parent.unpack() { - GenericArgKind::Type(parent_ty) => match *parent_ty.kind() { - ty::Bool - | ty::Char - | ty::Int(_) - | ty::Uint(_) - | ty::Float(_) - | ty::Str - | ty::Infer(_) - | ty::Param(_) - | ty::Never - | ty::Error(_) - | ty::Placeholder(..) - | ty::Bound(..) - | ty::Foreign(..) => {} - - ty::Pat(ty, pat) => { - match *pat { - ty::PatternKind::Range { start, end } => { - stack.push(end.into()); - stack.push(start.into()); - } - } - stack.push(ty.into()); - } - ty::Array(ty, len) => { - stack.push(len.into()); - stack.push(ty.into()); - } - ty::Slice(ty) => { - stack.push(ty.into()); - } - ty::RawPtr(ty, _) => { - stack.push(ty.into()); - } - ty::Ref(lt, ty, _) => { - stack.push(ty.into()); - stack.push(lt.into()); - } - ty::Alias(_, data) => { - stack.extend(data.args.iter().rev()); - } - ty::Dynamic(obj, lt, _) => { - stack.push(lt.into()); - stack.extend(obj.iter().rev().flat_map(|predicate| { - let (args, opt_ty) = match predicate.skip_binder() { - ty::ExistentialPredicate::Trait(tr) => (tr.args, None), - ty::ExistentialPredicate::Projection(p) => (p.args, Some(p.term)), - ty::ExistentialPredicate::AutoTrait(_) => - // Empty iterator - { - (ty::GenericArgs::empty(), None) - } - }; - - args.iter().rev().chain(opt_ty.map(|term| match term.unpack() { - ty::TermKind::Ty(ty) => ty.into(), - ty::TermKind::Const(ct) => ct.into(), - })) - })); - } - ty::Adt(_, args) - | ty::Closure(_, args) - | ty::CoroutineClosure(_, args) - | ty::Coroutine(_, args) - | ty::CoroutineWitness(_, args) - | ty::FnDef(_, args) => { - stack.extend(args.iter().rev()); - } - ty::Tuple(ts) => stack.extend(ts.iter().rev().map(GenericArg::from)), - ty::FnPtr(sig_tys, _hdr) => { - stack.extend( - sig_tys.skip_binder().inputs_and_output.iter().rev().map(|ty| ty.into()), - ); - } - ty::UnsafeBinder(bound_ty) => { - stack.push(bound_ty.skip_binder().into()); - } - }, - GenericArgKind::Lifetime(_) => {} - GenericArgKind::Const(parent_ct) => match parent_ct.kind() { - ty::ConstKind::Infer(_) - | ty::ConstKind::Param(_) - | ty::ConstKind::Placeholder(_) - | ty::ConstKind::Bound(..) - | ty::ConstKind::Error(_) => {} - - ty::ConstKind::Value(cv) => stack.push(cv.ty.into()), - - ty::ConstKind::Expr(expr) => stack.extend(expr.args().iter().rev()), - ty::ConstKind::Unevaluated(ct) => { - stack.extend(ct.args.iter().rev()); - } - }, - } -} |