1 //! An iterator over the type substructure.
2 //! WARNING: this does not keep track of the region depth.
4 use crate::ty::subst::{GenericArg, GenericArgKind};
5 use crate::ty::{self, TyCtxt};
6 use rustc_data_structures::sso::SsoHashSet;
7 use smallvec::{self, SmallVec};
9 // The TypeWalker's stack is hot enough that it's worth going to some effort to
10 // avoid heap allocations.
11 type TypeWalkerStack<'tcx> = SmallVec<[GenericArg<'tcx>; 8]>;
13 pub struct TypeWalker<'tcx> {
14 expose_default_const_substs: Option<TyCtxt<'tcx>>,
15 stack: TypeWalkerStack<'tcx>,
17 pub visited: SsoHashSet<GenericArg<'tcx>>,
20 /// An iterator for walking the type tree.
22 /// It's very easy to produce a deeply
23 /// nested type tree with a lot of
24 /// identical subtrees. In order to work efficiently
25 /// in this situation walker only visits each type once.
26 /// It maintains a set of visited types and
27 /// skips any types that are already there.
28 impl<'tcx> TypeWalker<'tcx> {
29 fn new(expose_default_const_substs: Option<TyCtxt<'tcx>>, root: GenericArg<'tcx>) -> Self {
31 expose_default_const_substs,
32 stack: smallvec![root],
34 visited: SsoHashSet::new(),
38 /// Skips the subtree corresponding to the last type
39 /// returned by `next()`.
41 /// Example: Imagine you are walking `Foo<Bar<i32>, usize>`.
44 /// let mut iter: TypeWalker = ...;
45 /// iter.next(); // yields Foo
46 /// iter.next(); // yields Bar<i32>
47 /// iter.skip_current_subtree(); // skips i32
48 /// iter.next(); // yields usize
50 pub fn skip_current_subtree(&mut self) {
51 self.stack.truncate(self.last_subtree);
55 impl<'tcx> Iterator for TypeWalker<'tcx> {
56 type Item = GenericArg<'tcx>;
58 fn next(&mut self) -> Option<GenericArg<'tcx>> {
59 debug!("next(): stack={:?}", self.stack);
61 let next = self.stack.pop()?;
62 self.last_subtree = self.stack.len();
63 if self.visited.insert(next) {
64 push_inner(self.expose_default_const_substs, &mut self.stack, next);
65 debug!("next: stack={:?}", self.stack);
72 impl<'tcx> GenericArg<'tcx> {
73 /// Iterator that walks `self` and any types reachable from
74 /// `self`, in depth-first order. Note that just walks the types
75 /// that appear in `self`, it does not descend into the fields of
76 /// structs or variants. For example:
79 /// isize => { isize }
80 /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
81 /// [isize] => { [isize], isize }
83 pub fn walk(self, tcx: TyCtxt<'tcx>) -> TypeWalker<'tcx> {
84 TypeWalker::new(Some(tcx), self)
87 /// Iterator that walks the immediate children of `self`. Hence
88 /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]`
89 /// (but not `i32`, like `walk`).
91 /// Iterator only walks items once.
92 /// It accepts visited set, updates it with all visited types
93 /// and skips any types that are already there.
97 visited: &mut SsoHashSet<GenericArg<'tcx>>,
98 ) -> impl Iterator<Item = GenericArg<'tcx>> {
99 let mut stack = SmallVec::new();
100 push_inner(Some(tcx), &mut stack, self);
101 stack.retain(|a| visited.insert(*a));
106 impl<'tcx> super::TyS<'tcx> {
107 pub fn walk_ignoring_default_const_substs(&'tcx self) -> TypeWalker<'tcx> {
108 TypeWalker::new(None, self.into())
111 /// Iterator that walks `self` and any types reachable from
112 /// `self`, in depth-first order. Note that just walks the types
113 /// that appear in `self`, it does not descend into the fields of
114 /// structs or variants. For example:
117 /// isize => { isize }
118 /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
119 /// [isize] => { [isize], isize }
121 pub fn walk(&'tcx self, tcx: TyCtxt<'tcx>) -> TypeWalker<'tcx> {
122 TypeWalker::new(Some(tcx), self.into())
126 /// We push `GenericArg`s on the stack in reverse order so as to
127 /// maintain a pre-order traversal. As of the time of this
128 /// writing, the fact that the traversal is pre-order is not
129 /// known to be significant to any code, but it seems like the
130 /// natural order one would expect (basically, the order of the
131 /// types as they are written).
133 expose_default_const_substs: Option<TyCtxt<'tcx>>,
134 stack: &mut TypeWalkerStack<'tcx>,
135 parent: GenericArg<'tcx>,
137 match parent.unpack() {
138 GenericArgKind::Type(parent_ty) => match *parent_ty.kind() {
149 | ty::Placeholder(..)
151 | ty::Foreign(..) => {}
153 ty::Array(ty, len) => {
154 stack.push(len.into());
155 stack.push(ty.into());
158 stack.push(ty.into());
161 stack.push(mt.ty.into());
163 ty::Ref(lt, ty, _) => {
164 stack.push(ty.into());
165 stack.push(lt.into());
167 ty::Projection(data) => {
168 stack.extend(data.substs.iter().rev());
170 ty::Dynamic(obj, lt) => {
171 stack.push(lt.into());
172 stack.extend(obj.iter().rev().flat_map(|predicate| {
173 let (substs, opt_ty) = match predicate.skip_binder() {
174 ty::ExistentialPredicate::Trait(tr) => (tr.substs, None),
175 ty::ExistentialPredicate::Projection(p) => (p.substs, Some(p.ty)),
176 ty::ExistentialPredicate::AutoTrait(_) =>
179 (ty::InternalSubsts::empty(), None)
183 substs.iter().rev().chain(opt_ty.map(|ty| ty.into()))
187 | ty::Opaque(_, substs)
188 | ty::Closure(_, substs)
189 | ty::Generator(_, substs, _)
191 | ty::FnDef(_, substs) => {
192 stack.extend(substs.iter().rev());
194 ty::GeneratorWitness(ts) => {
195 stack.extend(ts.skip_binder().iter().rev().map(|ty| ty.into()));
198 stack.push(sig.skip_binder().output().into());
199 stack.extend(sig.skip_binder().inputs().iter().copied().rev().map(|ty| ty.into()));
202 GenericArgKind::Lifetime(_) => {}
203 GenericArgKind::Const(parent_ct) => {
204 stack.push(parent_ct.ty.into());
205 match parent_ct.val {
206 ty::ConstKind::Infer(_)
207 | ty::ConstKind::Param(_)
208 | ty::ConstKind::Placeholder(_)
209 | ty::ConstKind::Bound(..)
210 | ty::ConstKind::Value(_)
211 | ty::ConstKind::Error(_) => {}
213 ty::ConstKind::Unevaluated(ct) => {
214 if let Some(tcx) = expose_default_const_substs {
215 stack.extend(ct.substs(tcx).iter().rev());
216 } else if let Some(substs) = ct.substs_ {
217 stack.extend(substs.iter().rev());