1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
use middle::ty::{self, Ty};
use std::iter::Iterator;
use std::vec::IntoIter;
pub struct TypeWalker<'tcx> {
stack: Vec<Ty<'tcx>>,
last_subtree: usize,
}
impl<'tcx> TypeWalker<'tcx> {
pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
TypeWalker { stack: vec!(ty), last_subtree: 1, }
}
pub fn skip_current_subtree(&mut self) {
self.stack.truncate(self.last_subtree);
}
}
impl<'tcx> Iterator for TypeWalker<'tcx> {
type Item = Ty<'tcx>;
fn next(&mut self) -> Option<Ty<'tcx>> {
debug!("next(): stack={:?}", self.stack);
match self.stack.pop() {
None => {
return None;
}
Some(ty) => {
self.last_subtree = self.stack.len();
push_subtypes(&mut self.stack, ty);
debug!("next: stack={:?}", self.stack);
Some(ty)
}
}
}
}
pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> IntoIter<Ty<'tcx>> {
let mut stack = vec![];
push_subtypes(&mut stack, ty);
stack.into_iter()
}
fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) {
match parent_ty.sty {
ty::ty_bool | ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) | ty::ty_float(_) |
ty::ty_str | ty::ty_infer(_) | ty::ty_param(_) | ty::ty_err => {
}
ty::ty_uniq(ty) | ty::ty_vec(ty, _) => {
stack.push(ty);
}
ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => {
stack.push(mt.ty);
}
ty::ty_projection(ref data) => {
push_reversed(stack, data.trait_ref.substs.types.as_slice());
}
ty::ty_trait(box ty::TyTrait { ref principal, ref bounds }) => {
push_reversed(stack, principal.substs().types.as_slice());
push_reversed(stack, &bounds.projection_bounds.iter().map(|pred| {
pred.0.ty
}).collect::<Vec<_>>());
}
ty::ty_enum(_, ref substs) |
ty::ty_struct(_, ref substs) |
ty::ty_closure(_, ref substs) => {
push_reversed(stack, substs.types.as_slice());
}
ty::ty_tup(ref ts) => {
push_reversed(stack, ts);
}
ty::ty_bare_fn(_, ref ft) => {
push_sig_subtypes(stack, &ft.sig);
}
}
}
fn push_sig_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, sig: &ty::PolyFnSig<'tcx>) {
match sig.0.output {
ty::FnConverging(output) => { stack.push(output); }
ty::FnDiverging => { }
}
push_reversed(stack, &sig.0.inputs);
}
fn push_reversed<'tcx>(stack: &mut Vec<Ty<'tcx>>, tys: &[Ty<'tcx>]) {
for &ty in tys.iter().rev() {
stack.push(ty);
}
}