1 //! An iterator over the type substructure.
2 //! WARNING: this does not keep track of the region depth.
4 use crate::ty
::{self, Ty}
;
5 use smallvec
::{self, SmallVec}
;
6 use crate::mir
::interpret
::ConstValue
;
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
>>;
13 pub struct TypeWalker
<'tcx
> {
14 stack
: TypeWalkerStack
<'tcx
>,
18 impl<'tcx
> TypeWalker
<'tcx
> {
19 pub fn new(ty
: Ty
<'tcx
>) -> TypeWalker
<'tcx
> {
20 TypeWalker { stack: smallvec![ty], last_subtree: 1, }
23 /// Skips the subtree of types corresponding to the last type
24 /// returned by `next()`.
26 /// Example: Imagine you are walking `Foo<Bar<int>, usize>`.
29 /// let mut iter: TypeWalker = ...;
30 /// iter.next(); // yields Foo
31 /// iter.next(); // yields Bar<int>
32 /// iter.skip_current_subtree(); // skips int
33 /// iter.next(); // yields usize
35 pub fn skip_current_subtree(&mut self) {
36 self.stack
.truncate(self.last_subtree
);
40 impl<'tcx
> Iterator
for TypeWalker
<'tcx
> {
43 fn next(&mut self) -> Option
<Ty
<'tcx
>> {
44 debug
!("next(): stack={:?}", self.stack
);
45 match self.stack
.pop() {
50 self.last_subtree
= self.stack
.len();
51 push_subtypes(&mut self.stack
, ty
);
52 debug
!("next: stack={:?}", self.stack
);
59 pub fn walk_shallow
<'tcx
>(ty
: Ty
<'tcx
>) -> smallvec
::IntoIter
<TypeWalkerArray
<'tcx
>> {
60 let mut stack
= SmallVec
::new();
61 push_subtypes(&mut stack
, ty
);
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).
71 fn push_subtypes
<'tcx
>(stack
: &mut TypeWalkerStack
<'tcx
>, parent_ty
: Ty
<'tcx
>) {
73 ty
::Bool
| ty
::Char
| ty
::Int(_
) | ty
::Uint(_
) | ty
::Float(_
) |
74 ty
::Str
| ty
::Infer(_
) | ty
::Param(_
) | ty
::Never
| ty
::Error
|
75 ty
::Placeholder(..) | ty
::Bound(..) | ty
::Foreign(..) => {
77 ty
::Array(ty
, len
) => {
78 if let ConstValue
::Unevaluated(_
, substs
) = len
.val
{
79 stack
.extend(substs
.types().rev());
87 ty
::RawPtr(ref mt
) => {
90 ty
::Ref(_
, ty
, _
) => {
93 ty
::Projection(ref data
) | ty
::UnnormalizedProjection(ref data
) => {
94 stack
.extend(data
.substs
.types().rev());
96 ty
::Dynamic(ref obj
, ..) => {
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
) =>
101 (p
.substs
, Some(p
.ty
)),
102 ty
::ExistentialPredicate
::AutoTrait(_
) =>
104 (ty
::InternalSubsts
::empty(), None
),
107 substs
.types().rev().chain(opt_ty
)
110 ty
::Adt(_
, substs
) | ty
::Opaque(_
, substs
) => {
111 stack
.extend(substs
.types().rev());
113 ty
::Closure(_
, ref substs
) => {
114 stack
.extend(substs
.substs
.types().rev());
116 ty
::Generator(_
, ref substs
, _
) => {
117 stack
.extend(substs
.substs
.types().rev());
119 ty
::GeneratorWitness(ts
) => {
120 stack
.extend(ts
.skip_binder().iter().cloned().rev());
123 stack
.extend(ts
.iter().map(|k
| k
.expect_ty()).rev());
125 ty
::FnDef(_
, substs
) => {
126 stack
.extend(substs
.types().rev());
129 stack
.push(sig
.skip_binder().output());
130 stack
.extend(sig
.skip_binder().inputs().iter().cloned().rev());