]>
Commit | Line | Data |
---|---|---|
ba9703b0 XL |
1 | //! An iterator over the type substructure. |
2 | //! WARNING: this does not keep track of the region depth. | |
3 | ||
5099ac24 | 4 | use crate::ty::{self, Ty}; |
add651ee | 5 | use crate::ty::{GenericArg, GenericArgKind}; |
29967ef6 | 6 | use rustc_data_structures::sso::SsoHashSet; |
31ef2f64 FG |
7 | use smallvec::{smallvec, SmallVec}; |
8 | use tracing::debug; | |
ba9703b0 XL |
9 | |
10 | // The TypeWalker's stack is hot enough that it's worth going to some effort to | |
11 | // avoid heap allocations. | |
12 | type TypeWalkerStack<'tcx> = SmallVec<[GenericArg<'tcx>; 8]>; | |
13 | ||
14 | pub struct TypeWalker<'tcx> { | |
15 | stack: TypeWalkerStack<'tcx>, | |
16 | last_subtree: usize, | |
6a06907d | 17 | pub visited: SsoHashSet<GenericArg<'tcx>>, |
ba9703b0 XL |
18 | } |
19 | ||
6c58768f XL |
20 | /// An iterator for walking the type tree. |
21 | /// | |
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. | |
ba9703b0 | 28 | impl<'tcx> TypeWalker<'tcx> { |
5099ac24 FG |
29 | pub fn new(root: GenericArg<'tcx>) -> Self { |
30 | Self { stack: smallvec![root], last_subtree: 1, visited: SsoHashSet::new() } | |
ba9703b0 XL |
31 | } |
32 | ||
33 | /// Skips the subtree corresponding to the last type | |
34 | /// returned by `next()`. | |
35 | /// | |
f035d41b | 36 | /// Example: Imagine you are walking `Foo<Bar<i32>, usize>`. |
ba9703b0 | 37 | /// |
04454e1e | 38 | /// ```ignore (illustrative) |
ba9703b0 XL |
39 | /// let mut iter: TypeWalker = ...; |
40 | /// iter.next(); // yields Foo | |
f035d41b XL |
41 | /// iter.next(); // yields Bar<i32> |
42 | /// iter.skip_current_subtree(); // skips i32 | |
ba9703b0 XL |
43 | /// iter.next(); // yields usize |
44 | /// ``` | |
45 | pub fn skip_current_subtree(&mut self) { | |
46 | self.stack.truncate(self.last_subtree); | |
47 | } | |
48 | } | |
49 | ||
50 | impl<'tcx> Iterator for TypeWalker<'tcx> { | |
51 | type Item = GenericArg<'tcx>; | |
52 | ||
53 | fn next(&mut self) -> Option<GenericArg<'tcx>> { | |
54 | debug!("next(): stack={:?}", self.stack); | |
6c58768f XL |
55 | loop { |
56 | let next = self.stack.pop()?; | |
57 | self.last_subtree = self.stack.len(); | |
58 | if self.visited.insert(next) { | |
5099ac24 | 59 | push_inner(&mut self.stack, next); |
6c58768f XL |
60 | debug!("next: stack={:?}", self.stack); |
61 | return Some(next); | |
62 | } | |
63 | } | |
ba9703b0 XL |
64 | } |
65 | } | |
66 | ||
a2a8927a | 67 | impl<'tcx> GenericArg<'tcx> { |
ba9703b0 XL |
68 | /// Iterator that walks `self` and any types reachable from |
69 | /// `self`, in depth-first order. Note that just walks the types | |
70 | /// that appear in `self`, it does not descend into the fields of | |
71 | /// structs or variants. For example: | |
72 | /// | |
1b1a35ee | 73 | /// ```text |
ba9703b0 XL |
74 | /// isize => { isize } |
75 | /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } | |
76 | /// [isize] => { [isize], isize } | |
77 | /// ``` | |
5099ac24 FG |
78 | pub fn walk(self) -> TypeWalker<'tcx> { |
79 | TypeWalker::new(self) | |
ba9703b0 XL |
80 | } |
81 | ||
82 | /// Iterator that walks the immediate children of `self`. Hence | |
83 | /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]` | |
84 | /// (but not `i32`, like `walk`). | |
6c58768f XL |
85 | /// |
86 | /// Iterator only walks items once. | |
87 | /// It accepts visited set, updates it with all visited types | |
88 | /// and skips any types that are already there. | |
89 | pub fn walk_shallow( | |
90 | self, | |
29967ef6 | 91 | visited: &mut SsoHashSet<GenericArg<'tcx>>, |
6c58768f | 92 | ) -> impl Iterator<Item = GenericArg<'tcx>> { |
ba9703b0 | 93 | let mut stack = SmallVec::new(); |
5099ac24 | 94 | push_inner(&mut stack, self); |
6c58768f | 95 | stack.retain(|a| visited.insert(*a)); |
ba9703b0 XL |
96 | stack.into_iter() |
97 | } | |
98 | } | |
99 | ||
5099ac24 | 100 | impl<'tcx> Ty<'tcx> { |
ba9703b0 | 101 | /// Iterator that walks `self` and any types reachable from |
2b03887a FG |
102 | /// `self`, in depth-first order. Note that just walks the types |
103 | /// that appear in `self`, it does not descend into the fields of | |
104 | /// structs or variants. For example: | |
105 | /// | |
106 | /// ```text | |
107 | /// isize => { isize } | |
108 | /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } | |
109 | /// [isize] => { [isize], isize } | |
110 | /// ``` | |
111 | pub fn walk(self) -> TypeWalker<'tcx> { | |
112 | TypeWalker::new(self.into()) | |
113 | } | |
114 | } | |
115 | ||
116 | impl<'tcx> ty::Const<'tcx> { | |
117 | /// Iterator that walks `self` and any types reachable from | |
ba9703b0 XL |
118 | /// `self`, in depth-first order. Note that just walks the types |
119 | /// that appear in `self`, it does not descend into the fields of | |
120 | /// structs or variants. For example: | |
121 | /// | |
1b1a35ee | 122 | /// ```text |
ba9703b0 XL |
123 | /// isize => { isize } |
124 | /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize } | |
125 | /// [isize] => { [isize], isize } | |
126 | /// ``` | |
5099ac24 FG |
127 | pub fn walk(self) -> TypeWalker<'tcx> { |
128 | TypeWalker::new(self.into()) | |
ba9703b0 XL |
129 | } |
130 | } | |
131 | ||
94222f64 XL |
132 | /// We push `GenericArg`s on the stack in reverse order so as to |
133 | /// maintain a pre-order traversal. As of the time of this | |
134 | /// writing, the fact that the traversal is pre-order is not | |
135 | /// known to be significant to any code, but it seems like the | |
136 | /// natural order one would expect (basically, the order of the | |
137 | /// types as they are written). | |
5099ac24 | 138 | fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>) { |
ba9703b0 | 139 | match parent.unpack() { |
1b1a35ee | 140 | GenericArgKind::Type(parent_ty) => match *parent_ty.kind() { |
ba9703b0 XL |
141 | ty::Bool |
142 | | ty::Char | |
143 | | ty::Int(_) | |
144 | | ty::Uint(_) | |
145 | | ty::Float(_) | |
146 | | ty::Str | |
147 | | ty::Infer(_) | |
148 | | ty::Param(_) | |
149 | | ty::Never | |
f035d41b | 150 | | ty::Error(_) |
ba9703b0 XL |
151 | | ty::Placeholder(..) |
152 | | ty::Bound(..) | |
153 | | ty::Foreign(..) => {} | |
154 | ||
e8be2606 FG |
155 | ty::Pat(ty, pat) => { |
156 | match *pat { | |
157 | ty::PatternKind::Range { start, end, include_end: _ } => { | |
158 | stack.extend(end.map(Into::into)); | |
159 | stack.extend(start.map(Into::into)); | |
160 | } | |
161 | } | |
162 | stack.push(ty.into()); | |
163 | } | |
ba9703b0 XL |
164 | ty::Array(ty, len) => { |
165 | stack.push(len.into()); | |
166 | stack.push(ty.into()); | |
167 | } | |
168 | ty::Slice(ty) => { | |
169 | stack.push(ty.into()); | |
170 | } | |
e8be2606 FG |
171 | ty::RawPtr(ty, _) => { |
172 | stack.push(ty.into()); | |
ba9703b0 XL |
173 | } |
174 | ty::Ref(lt, ty, _) => { | |
175 | stack.push(ty.into()); | |
176 | stack.push(lt.into()); | |
177 | } | |
9c376795 | 178 | ty::Alias(_, data) => { |
add651ee | 179 | stack.extend(data.args.iter().rev()); |
ba9703b0 | 180 | } |
f2b60f7d | 181 | ty::Dynamic(obj, lt, _) => { |
ba9703b0 XL |
182 | stack.push(lt.into()); |
183 | stack.extend(obj.iter().rev().flat_map(|predicate| { | |
add651ee FG |
184 | let (args, opt_ty) = match predicate.skip_binder() { |
185 | ty::ExistentialPredicate::Trait(tr) => (tr.args, None), | |
186 | ty::ExistentialPredicate::Projection(p) => (p.args, Some(p.term)), | |
ba9703b0 XL |
187 | ty::ExistentialPredicate::AutoTrait(_) => |
188 | // Empty iterator | |
189 | { | |
add651ee | 190 | (ty::GenericArgs::empty(), None) |
ba9703b0 XL |
191 | } |
192 | }; | |
193 | ||
add651ee | 194 | args.iter().rev().chain(opt_ty.map(|term| match term.unpack() { |
f2b60f7d FG |
195 | ty::TermKind::Ty(ty) => ty.into(), |
196 | ty::TermKind::Const(ct) => ct.into(), | |
5099ac24 | 197 | })) |
ba9703b0 XL |
198 | })); |
199 | } | |
add651ee FG |
200 | ty::Adt(_, args) |
201 | | ty::Closure(_, args) | |
c620b35d | 202 | | ty::CoroutineClosure(_, args) |
c0240ec0 | 203 | | ty::Coroutine(_, args) |
ed00b5ec | 204 | | ty::CoroutineWitness(_, args) |
add651ee FG |
205 | | ty::FnDef(_, args) => { |
206 | stack.extend(args.iter().rev()); | |
ba9703b0 | 207 | } |
49aad941 | 208 | ty::Tuple(ts) => stack.extend(ts.iter().rev().map(GenericArg::from)), |
ba9703b0 XL |
209 | ty::FnPtr(sig) => { |
210 | stack.push(sig.skip_binder().output().into()); | |
f9f354fc | 211 | stack.extend(sig.skip_binder().inputs().iter().copied().rev().map(|ty| ty.into())); |
ba9703b0 XL |
212 | } |
213 | }, | |
214 | GenericArgKind::Lifetime(_) => {} | |
31ef2f64 FG |
215 | GenericArgKind::Const(parent_ct) => match parent_ct.kind() { |
216 | ty::ConstKind::Infer(_) | |
217 | | ty::ConstKind::Param(_) | |
218 | | ty::ConstKind::Placeholder(_) | |
219 | | ty::ConstKind::Bound(..) | |
220 | | ty::ConstKind::Error(_) => {} | |
221 | ||
222 | ty::ConstKind::Value(ty, _) => stack.push(ty.into()), | |
223 | ||
224 | ty::ConstKind::Expr(expr) => stack.extend(expr.args().iter().rev()), | |
225 | ty::ConstKind::Unevaluated(ct) => { | |
226 | stack.extend(ct.args.iter().rev()); | |
ba9703b0 | 227 | } |
31ef2f64 | 228 | }, |
ba9703b0 XL |
229 | } |
230 | } |