]>
Commit | Line | Data |
---|---|---|
ba9703b0 XL |
1 | //! An iterator over the type substructure. |
2 | //! WARNING: this does not keep track of the region depth. | |
3 | ||
ba9703b0 | 4 | use crate::ty::subst::{GenericArg, GenericArgKind}; |
5099ac24 | 5 | use crate::ty::{self, Ty}; |
29967ef6 | 6 | use rustc_data_structures::sso::SsoHashSet; |
ba9703b0 XL |
7 | use smallvec::{self, SmallVec}; |
8 | ||
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]>; | |
12 | ||
13 | pub struct TypeWalker<'tcx> { | |
14 | stack: TypeWalkerStack<'tcx>, | |
15 | last_subtree: usize, | |
6a06907d | 16 | pub visited: SsoHashSet<GenericArg<'tcx>>, |
ba9703b0 XL |
17 | } |
18 | ||
6c58768f XL |
19 | /// An iterator for walking the type tree. |
20 | /// | |
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. | |
ba9703b0 | 27 | impl<'tcx> TypeWalker<'tcx> { |
5099ac24 FG |
28 | pub fn new(root: GenericArg<'tcx>) -> Self { |
29 | Self { stack: smallvec![root], last_subtree: 1, visited: SsoHashSet::new() } | |
ba9703b0 XL |
30 | } |
31 | ||
32 | /// Skips the subtree corresponding to the last type | |
33 | /// returned by `next()`. | |
34 | /// | |
f035d41b | 35 | /// Example: Imagine you are walking `Foo<Bar<i32>, usize>`. |
ba9703b0 XL |
36 | /// |
37 | /// ``` | |
38 | /// let mut iter: TypeWalker = ...; | |
39 | /// iter.next(); // yields Foo | |
f035d41b XL |
40 | /// iter.next(); // yields Bar<i32> |
41 | /// iter.skip_current_subtree(); // skips i32 | |
ba9703b0 XL |
42 | /// iter.next(); // yields usize |
43 | /// ``` | |
44 | pub fn skip_current_subtree(&mut self) { | |
45 | self.stack.truncate(self.last_subtree); | |
46 | } | |
47 | } | |
48 | ||
49 | impl<'tcx> Iterator for TypeWalker<'tcx> { | |
50 | type Item = GenericArg<'tcx>; | |
51 | ||
52 | fn next(&mut self) -> Option<GenericArg<'tcx>> { | |
53 | debug!("next(): stack={:?}", self.stack); | |
6c58768f XL |
54 | loop { |
55 | let next = self.stack.pop()?; | |
56 | self.last_subtree = self.stack.len(); | |
57 | if self.visited.insert(next) { | |
5099ac24 | 58 | push_inner(&mut self.stack, next); |
6c58768f XL |
59 | debug!("next: stack={:?}", self.stack); |
60 | return Some(next); | |
61 | } | |
62 | } | |
ba9703b0 XL |
63 | } |
64 | } | |
65 | ||
a2a8927a | 66 | impl<'tcx> GenericArg<'tcx> { |
ba9703b0 XL |
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: | |
71 | /// | |
1b1a35ee | 72 | /// ```text |
ba9703b0 XL |
73 | /// isize => { isize } |
74 | /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } | |
75 | /// [isize] => { [isize], isize } | |
76 | /// ``` | |
5099ac24 FG |
77 | pub fn walk(self) -> TypeWalker<'tcx> { |
78 | TypeWalker::new(self) | |
ba9703b0 XL |
79 | } |
80 | ||
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`). | |
6c58768f XL |
84 | /// |
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. | |
88 | pub fn walk_shallow( | |
89 | self, | |
29967ef6 | 90 | visited: &mut SsoHashSet<GenericArg<'tcx>>, |
6c58768f | 91 | ) -> impl Iterator<Item = GenericArg<'tcx>> { |
ba9703b0 | 92 | let mut stack = SmallVec::new(); |
5099ac24 | 93 | push_inner(&mut stack, self); |
6c58768f | 94 | stack.retain(|a| visited.insert(*a)); |
ba9703b0 XL |
95 | stack.into_iter() |
96 | } | |
97 | } | |
98 | ||
5099ac24 | 99 | impl<'tcx> Ty<'tcx> { |
ba9703b0 XL |
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: | |
104 | /// | |
1b1a35ee | 105 | /// ```text |
ba9703b0 XL |
106 | /// isize => { isize } |
107 | /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } | |
108 | /// [isize] => { [isize], isize } | |
109 | /// ``` | |
5099ac24 FG |
110 | pub fn walk(self) -> TypeWalker<'tcx> { |
111 | TypeWalker::new(self.into()) | |
ba9703b0 XL |
112 | } |
113 | } | |
114 | ||
94222f64 XL |
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). | |
5099ac24 | 121 | fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>) { |
ba9703b0 | 122 | match parent.unpack() { |
1b1a35ee | 123 | GenericArgKind::Type(parent_ty) => match *parent_ty.kind() { |
ba9703b0 XL |
124 | ty::Bool |
125 | | ty::Char | |
126 | | ty::Int(_) | |
127 | | ty::Uint(_) | |
128 | | ty::Float(_) | |
129 | | ty::Str | |
130 | | ty::Infer(_) | |
131 | | ty::Param(_) | |
132 | | ty::Never | |
f035d41b | 133 | | ty::Error(_) |
ba9703b0 XL |
134 | | ty::Placeholder(..) |
135 | | ty::Bound(..) | |
136 | | ty::Foreign(..) => {} | |
137 | ||
138 | ty::Array(ty, len) => { | |
139 | stack.push(len.into()); | |
140 | stack.push(ty.into()); | |
141 | } | |
142 | ty::Slice(ty) => { | |
143 | stack.push(ty.into()); | |
144 | } | |
145 | ty::RawPtr(mt) => { | |
146 | stack.push(mt.ty.into()); | |
147 | } | |
148 | ty::Ref(lt, ty, _) => { | |
149 | stack.push(ty.into()); | |
150 | stack.push(lt.into()); | |
151 | } | |
f9f354fc XL |
152 | ty::Projection(data) => { |
153 | stack.extend(data.substs.iter().rev()); | |
ba9703b0 XL |
154 | } |
155 | ty::Dynamic(obj, lt) => { | |
156 | stack.push(lt.into()); | |
157 | stack.extend(obj.iter().rev().flat_map(|predicate| { | |
f035d41b | 158 | let (substs, opt_ty) = match predicate.skip_binder() { |
ba9703b0 | 159 | ty::ExistentialPredicate::Trait(tr) => (tr.substs, None), |
5099ac24 | 160 | ty::ExistentialPredicate::Projection(p) => (p.substs, Some(p.term)), |
ba9703b0 XL |
161 | ty::ExistentialPredicate::AutoTrait(_) => |
162 | // Empty iterator | |
163 | { | |
164 | (ty::InternalSubsts::empty(), None) | |
165 | } | |
166 | }; | |
167 | ||
5099ac24 FG |
168 | substs.iter().rev().chain(opt_ty.map(|term| match term { |
169 | ty::Term::Ty(ty) => ty.into(), | |
170 | ty::Term::Const(ct) => ct.into(), | |
171 | })) | |
ba9703b0 XL |
172 | })); |
173 | } | |
174 | ty::Adt(_, substs) | |
175 | | ty::Opaque(_, substs) | |
176 | | ty::Closure(_, substs) | |
177 | | ty::Generator(_, substs, _) | |
ba9703b0 | 178 | | ty::FnDef(_, substs) => { |
f9f354fc | 179 | stack.extend(substs.iter().rev()); |
ba9703b0 | 180 | } |
ee023bcb | 181 | ty::Tuple(ts) => stack.extend(ts.as_substs().iter().rev()), |
ba9703b0 | 182 | ty::GeneratorWitness(ts) => { |
f9f354fc | 183 | stack.extend(ts.skip_binder().iter().rev().map(|ty| ty.into())); |
ba9703b0 XL |
184 | } |
185 | ty::FnPtr(sig) => { | |
186 | stack.push(sig.skip_binder().output().into()); | |
f9f354fc | 187 | stack.extend(sig.skip_binder().inputs().iter().copied().rev().map(|ty| ty.into())); |
ba9703b0 XL |
188 | } |
189 | }, | |
190 | GenericArgKind::Lifetime(_) => {} | |
191 | GenericArgKind::Const(parent_ct) => { | |
5099ac24 FG |
192 | stack.push(parent_ct.ty().into()); |
193 | match parent_ct.val() { | |
ba9703b0 XL |
194 | ty::ConstKind::Infer(_) |
195 | | ty::ConstKind::Param(_) | |
196 | | ty::ConstKind::Placeholder(_) | |
197 | | ty::ConstKind::Bound(..) | |
198 | | ty::ConstKind::Value(_) | |
f035d41b | 199 | | ty::ConstKind::Error(_) => {} |
ba9703b0 | 200 | |
cdc7bbd5 | 201 | ty::ConstKind::Unevaluated(ct) => { |
5099ac24 | 202 | stack.extend(ct.substs.iter().rev()); |
ba9703b0 XL |
203 | } |
204 | } | |
205 | } | |
206 | } | |
207 | } |