]>
Commit | Line | Data |
---|---|---|
1a4d82fc | 1 | //! An iterator over the type substructure. |
c1a9b12d | 2 | //! WARNING: this does not keep track of the region depth. |
1a4d82fc | 3 | |
9fa01778 | 4 | use crate::ty::{self, Ty}; |
b7449926 | 5 | use smallvec::{self, SmallVec}; |
532ac7d7 | 6 | use crate::mir::interpret::ConstValue; |
476ff2be SL |
7 | |
8 | // The TypeWalker's stack is hot enough that it's worth going to some effort to | |
9 | // avoid heap allocations. | |
10 | pub type TypeWalkerArray<'tcx> = [Ty<'tcx>; 8]; | |
11 | pub type TypeWalkerStack<'tcx> = SmallVec<TypeWalkerArray<'tcx>>; | |
1a4d82fc JJ |
12 | |
13 | pub struct TypeWalker<'tcx> { | |
476ff2be | 14 | stack: TypeWalkerStack<'tcx>, |
c34b1796 | 15 | last_subtree: usize, |
1a4d82fc JJ |
16 | } |
17 | ||
18 | impl<'tcx> TypeWalker<'tcx> { | |
19 | pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> { | |
b7449926 | 20 | TypeWalker { stack: smallvec![ty], last_subtree: 1, } |
1a4d82fc JJ |
21 | } |
22 | ||
1a4d82fc JJ |
23 | /// Skips the subtree of types corresponding to the last type |
24 | /// returned by `next()`. | |
25 | /// | |
c34b1796 | 26 | /// Example: Imagine you are walking `Foo<Bar<int>, usize>`. |
1a4d82fc | 27 | /// |
c34b1796 | 28 | /// ``` |
1a4d82fc JJ |
29 | /// let mut iter: TypeWalker = ...; |
30 | /// iter.next(); // yields Foo | |
31 | /// iter.next(); // yields Bar<int> | |
32 | /// iter.skip_current_subtree(); // skips int | |
c34b1796 | 33 | /// iter.next(); // yields usize |
1a4d82fc JJ |
34 | /// ``` |
35 | pub fn skip_current_subtree(&mut self) { | |
36 | self.stack.truncate(self.last_subtree); | |
37 | } | |
38 | } | |
39 | ||
40 | impl<'tcx> Iterator for TypeWalker<'tcx> { | |
41 | type Item = Ty<'tcx>; | |
42 | ||
43 | fn next(&mut self) -> Option<Ty<'tcx>> { | |
44 | debug!("next(): stack={:?}", self.stack); | |
45 | match self.stack.pop() { | |
46 | None => { | |
0bf4aa26 | 47 | None |
1a4d82fc JJ |
48 | } |
49 | Some(ty) => { | |
50 | self.last_subtree = self.stack.len(); | |
c34b1796 | 51 | push_subtypes(&mut self.stack, ty); |
1a4d82fc JJ |
52 | debug!("next: stack={:?}", self.stack); |
53 | Some(ty) | |
54 | } | |
55 | } | |
56 | } | |
57 | } | |
c34b1796 | 58 | |
b7449926 | 59 | pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> smallvec::IntoIter<TypeWalkerArray<'tcx>> { |
476ff2be | 60 | let mut stack = SmallVec::new(); |
c34b1796 AL |
61 | push_subtypes(&mut stack, ty); |
62 | stack.into_iter() | |
63 | } | |
64 | ||
9e0c209e SL |
65 | // We push types on the stack in reverse order so as to |
66 | // maintain a pre-order traversal. As of the time of this | |
67 | // writing, the fact that the traversal is pre-order is not | |
68 | // known to be significant to any code, but it seems like the | |
69 | // natural order one would expect (basically, the order of the | |
70 | // types as they are written). | |
476ff2be | 71 | fn push_subtypes<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent_ty: Ty<'tcx>) { |
c34b1796 | 72 | match parent_ty.sty { |
b7449926 XL |
73 | ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) | |
74 | ty::Str | ty::Infer(_) | ty::Param(_) | ty::Never | ty::Error | | |
a1dfa0c6 | 75 | ty::Placeholder(..) | ty::Bound(..) | ty::Foreign(..) => { |
c34b1796 | 76 | } |
b7449926 | 77 | ty::Array(ty, len) => { |
532ac7d7 | 78 | if let ConstValue::Unevaluated(_, substs) = len.val { |
0731742a XL |
79 | stack.extend(substs.types().rev()); |
80 | } | |
532ac7d7 | 81 | stack.push(len.ty); |
ea8adc8c XL |
82 | stack.push(ty); |
83 | } | |
b7449926 | 84 | ty::Slice(ty) => { |
c34b1796 AL |
85 | stack.push(ty); |
86 | } | |
b7449926 | 87 | ty::RawPtr(ref mt) => { |
c34b1796 AL |
88 | stack.push(mt.ty); |
89 | } | |
b7449926 | 90 | ty::Ref(_, ty, _) => { |
94b46f34 XL |
91 | stack.push(ty); |
92 | } | |
0bf4aa26 | 93 | ty::Projection(ref data) | ty::UnnormalizedProjection(ref data) => { |
041b39d2 | 94 | stack.extend(data.substs.types().rev()); |
c34b1796 | 95 | } |
b7449926 | 96 | ty::Dynamic(ref obj, ..) => { |
476ff2be SL |
97 | stack.extend(obj.iter().rev().flat_map(|predicate| { |
98 | let (substs, opt_ty) = match *predicate.skip_binder() { | |
99 | ty::ExistentialPredicate::Trait(tr) => (tr.substs, None), | |
100 | ty::ExistentialPredicate::Projection(p) => | |
041b39d2 | 101 | (p.substs, Some(p.ty)), |
476ff2be SL |
102 | ty::ExistentialPredicate::AutoTrait(_) => |
103 | // Empty iterator | |
532ac7d7 | 104 | (ty::InternalSubsts::empty(), None), |
476ff2be SL |
105 | }; |
106 | ||
107 | substs.types().rev().chain(opt_ty) | |
108 | })); | |
c34b1796 | 109 | } |
b7449926 | 110 | ty::Adt(_, substs) | ty::Opaque(_, substs) => { |
9e0c209e | 111 | stack.extend(substs.types().rev()); |
c34b1796 | 112 | } |
b7449926 | 113 | ty::Closure(_, ref substs) => { |
476ff2be | 114 | stack.extend(substs.substs.types().rev()); |
c1a9b12d | 115 | } |
b7449926 | 116 | ty::Generator(_, ref substs, _) => { |
2c00a5a8 XL |
117 | stack.extend(substs.substs.types().rev()); |
118 | } | |
b7449926 | 119 | ty::GeneratorWitness(ts) => { |
2c00a5a8 | 120 | stack.extend(ts.skip_binder().iter().cloned().rev()); |
ea8adc8c | 121 | } |
b7449926 | 122 | ty::Tuple(ts) => { |
48663c56 | 123 | stack.extend(ts.iter().map(|k| k.expect_ty()).rev()); |
c34b1796 | 124 | } |
b7449926 | 125 | ty::FnDef(_, substs) => { |
9e0c209e | 126 | stack.extend(substs.types().rev()); |
54a0048b | 127 | } |
b7449926 | 128 | ty::FnPtr(sig) => { |
ea8adc8c XL |
129 | stack.push(sig.skip_binder().output()); |
130 | stack.extend(sig.skip_binder().inputs().iter().cloned().rev()); | |
c34b1796 AL |
131 | } |
132 | } | |
133 | } |