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, Ty};
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 stack: TypeWalkerStack<'tcx>,
16 pub visited: SsoHashSet<GenericArg<'tcx>>,
19 /// An iterator for walking the type tree.
21 /// It's very easy to produce a deeply
22 /// nested type tree with a lot of
23 /// identical subtrees. In order to work efficiently
24 /// in this situation walker only visits each type once.
25 /// It maintains a set of visited types and
26 /// skips any types that are already there.
27 impl<'tcx> TypeWalker<'tcx> {
28 pub fn new(root: GenericArg<'tcx>) -> Self {
29 Self { stack: smallvec![root], last_subtree: 1, visited: SsoHashSet::new() }
32 /// Skips the subtree corresponding to the last type
33 /// returned by `next()`.
35 /// Example: Imagine you are walking `Foo<Bar<i32>, usize>`.
37 /// ```ignore (illustrative)
38 /// let mut iter: TypeWalker = ...;
39 /// iter.next(); // yields Foo
40 /// iter.next(); // yields Bar<i32>
41 /// iter.skip_current_subtree(); // skips i32
42 /// iter.next(); // yields usize
44 pub fn skip_current_subtree(&mut self) {
45 self.stack.truncate(self.last_subtree);
49 impl<'tcx> Iterator for TypeWalker<'tcx> {
50 type Item = GenericArg<'tcx>;
52 fn next(&mut self) -> Option<GenericArg<'tcx>> {
53 debug!("next(): stack={:?}", self.stack);
55 let next = self.stack.pop()?;
56 self.last_subtree = self.stack.len();
57 if self.visited.insert(next) {
58 push_inner(&mut self.stack, next);
59 debug!("next: stack={:?}", self.stack);
66 impl<'tcx> GenericArg<'tcx> {
67 /// Iterator that walks `self` and any types reachable from
68 /// `self`, in depth-first order. Note that just walks the types
69 /// that appear in `self`, it does not descend into the fields of
70 /// structs or variants. For example:
73 /// isize => { isize }
74 /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
75 /// [isize] => { [isize], isize }
77 pub fn walk(self) -> TypeWalker<'tcx> {
81 /// Iterator that walks the immediate children of `self`. Hence
82 /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]`
83 /// (but not `i32`, like `walk`).
85 /// Iterator only walks items once.
86 /// It accepts visited set, updates it with all visited types
87 /// and skips any types that are already there.
90 visited: &mut SsoHashSet<GenericArg<'tcx>>,
91 ) -> impl Iterator<Item = GenericArg<'tcx>> {
92 let mut stack = SmallVec::new();
93 push_inner(&mut stack, self);
94 stack.retain(|a| visited.insert(*a));
100 /// Iterator that walks `self` and any types reachable from
101 /// `self`, in depth-first order. Note that just walks the types
102 /// that appear in `self`, it does not descend into the fields of
103 /// structs or variants. For example:
106 /// isize => { isize }
107 /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
108 /// [isize] => { [isize], isize }
110 pub fn walk(self) -> TypeWalker<'tcx> {
111 TypeWalker::new(self.into())
115 impl<'tcx> ty::Const<'tcx> {
116 /// Iterator that walks `self` and any types reachable from
117 /// `self`, in depth-first order. Note that just walks the types
118 /// that appear in `self`, it does not descend into the fields of
119 /// structs or variants. For example:
122 /// isize => { isize }
123 /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
124 /// [isize] => { [isize], isize }
126 pub fn walk(self) -> TypeWalker<'tcx> {
127 TypeWalker::new(self.into())
131 /// We push `GenericArg`s on the stack in reverse order so as to
132 /// maintain a pre-order traversal. As of the time of this
133 /// writing, the fact that the traversal is pre-order is not
134 /// known to be significant to any code, but it seems like the
135 /// natural order one would expect (basically, the order of the
136 /// types as they are written).
137 fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>) {
138 match parent.unpack() {
139 GenericArgKind::Type(parent_ty) => match *parent_ty.kind() {
150 | ty::Placeholder(..)
152 | ty::Foreign(..) => {}
154 ty::Array(ty, len) => {
155 stack.push(len.into());
156 stack.push(ty.into());
159 stack.push(ty.into());
162 stack.push(mt.ty.into());
164 ty::Ref(lt, ty, _) => {
165 stack.push(ty.into());
166 stack.push(lt.into());
168 ty::Projection(data) => {
169 stack.extend(data.substs.iter().rev());
171 ty::Dynamic(obj, lt, _) => {
172 stack.push(lt.into());
173 stack.extend(obj.iter().rev().flat_map(|predicate| {
174 let (substs, opt_ty) = match predicate.skip_binder() {
175 ty::ExistentialPredicate::Trait(tr) => (tr.substs, None),
176 ty::ExistentialPredicate::Projection(p) => (p.substs, Some(p.term)),
177 ty::ExistentialPredicate::AutoTrait(_) =>
180 (ty::InternalSubsts::empty(), None)
184 substs.iter().rev().chain(opt_ty.map(|term| match term.unpack() {
185 ty::TermKind::Ty(ty) => ty.into(),
186 ty::TermKind::Const(ct) => ct.into(),
191 | ty::Opaque(_, substs)
192 | ty::Closure(_, substs)
193 | ty::Generator(_, substs, _)
194 | ty::FnDef(_, substs) => {
195 stack.extend(substs.iter().rev());
197 ty::Tuple(ts) => stack.extend(ts.as_substs().iter().rev()),
198 ty::GeneratorWitness(ts) => {
199 stack.extend(ts.skip_binder().iter().rev().map(|ty| ty.into()));
202 stack.push(sig.skip_binder().output().into());
203 stack.extend(sig.skip_binder().inputs().iter().copied().rev().map(|ty| ty.into()));
206 GenericArgKind::Lifetime(_) => {}
207 GenericArgKind::Const(parent_ct) => {
208 stack.push(parent_ct.ty().into());
209 match parent_ct.kind() {
210 ty::ConstKind::Infer(_)
211 | ty::ConstKind::Param(_)
212 | ty::ConstKind::Placeholder(_)
213 | ty::ConstKind::Bound(..)
214 | ty::ConstKind::Value(_)
215 | ty::ConstKind::Error(_) => {}
217 ty::ConstKind::Unevaluated(ct) => {
218 stack.extend(ct.substs.iter().rev());