1 //! An iterator over the type substructure.
2 //! WARNING: this does not keep track of the region depth.
5 use crate::ty
::subst
::{GenericArg, GenericArgKind}
;
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>`.
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 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
));
99 impl<'tcx
> super::TyS
<'tcx
> {
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(&'tcx
self) -> TypeWalker
<'tcx
> {
111 TypeWalker
::new(self.into())
115 // We push `GenericArg`s on the stack in reverse order so as to
116 // maintain a pre-order traversal. As of the time of this
117 // writing, the fact that the traversal is pre-order is not
118 // known to be significant to any code, but it seems like the
119 // natural order one would expect (basically, the order of the
120 // types as they are written).
121 fn push_inner
<'tcx
>(stack
: &mut TypeWalkerStack
<'tcx
>, parent
: GenericArg
<'tcx
>) {
122 match parent
.unpack() {
123 GenericArgKind
::Type(parent_ty
) => match *parent_ty
.kind() {
134 | ty
::Placeholder(..)
136 | ty
::Foreign(..) => {}
138 ty
::Array(ty
, len
) => {
139 stack
.push(len
.into());
140 stack
.push(ty
.into());
143 stack
.push(ty
.into());
146 stack
.push(mt
.ty
.into());
148 ty
::Ref(lt
, ty
, _
) => {
149 stack
.push(ty
.into());
150 stack
.push(lt
.into());
152 ty
::Projection(data
) => {
153 stack
.extend(data
.substs
.iter().rev());
155 ty
::Dynamic(obj
, lt
) => {
156 stack
.push(lt
.into());
157 stack
.extend(obj
.iter().rev().flat_map(|predicate
| {
158 let (substs
, opt_ty
) = match predicate
.skip_binder() {
159 ty
::ExistentialPredicate
::Trait(tr
) => (tr
.substs
, None
),
160 ty
::ExistentialPredicate
::Projection(p
) => (p
.substs
, Some(p
.ty
)),
161 ty
::ExistentialPredicate
::AutoTrait(_
) =>
164 (ty
::InternalSubsts
::empty(), None
)
168 substs
.iter().rev().chain(opt_ty
.map(|ty
| ty
.into()))
172 | ty
::Opaque(_
, substs
)
173 | ty
::Closure(_
, substs
)
174 | ty
::Generator(_
, substs
, _
)
176 | ty
::FnDef(_
, substs
) => {
177 stack
.extend(substs
.iter().rev());
179 ty
::GeneratorWitness(ts
) => {
180 stack
.extend(ts
.skip_binder().iter().rev().map(|ty
| ty
.into()));
183 stack
.push(sig
.skip_binder().output().into());
184 stack
.extend(sig
.skip_binder().inputs().iter().copied().rev().map(|ty
| ty
.into()));
187 GenericArgKind
::Lifetime(_
) => {}
188 GenericArgKind
::Const(parent_ct
) => {
189 stack
.push(parent_ct
.ty
.into());
190 match parent_ct
.val
{
191 ty
::ConstKind
::Infer(_
)
192 | ty
::ConstKind
::Param(_
)
193 | ty
::ConstKind
::Placeholder(_
)
194 | ty
::ConstKind
::Bound(..)
195 | ty
::ConstKind
::Value(_
)
196 | ty
::ConstKind
::Error(_
) => {}
198 ty
::ConstKind
::Unevaluated(_
, substs
, _
) => {
199 stack
.extend(substs
.iter().rev());