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};
7 // The TypeWalker's stack is hot enough that it's worth going to some effort to
8 // avoid heap allocations.
9 pub type TypeWalkerArray<'tcx> = [Ty<'tcx>; 8];
10 pub type TypeWalkerStack<'tcx> = SmallVec<TypeWalkerArray<'tcx>>;
12 pub struct TypeWalker<'tcx> {
13 stack: TypeWalkerStack<'tcx>,
17 impl<'tcx> TypeWalker<'tcx> {
18 pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
19 TypeWalker { stack: smallvec![ty], last_subtree: 1 }
22 /// Skips the subtree of types corresponding to the last type
23 /// returned by `next()`.
25 /// Example: Imagine you are walking `Foo<Bar<int>, usize>`.
28 /// let mut iter: TypeWalker = ...;
29 /// iter.next(); // yields Foo
30 /// iter.next(); // yields Bar<int>
31 /// iter.skip_current_subtree(); // skips int
32 /// iter.next(); // yields usize
34 pub fn skip_current_subtree(&mut self) {
35 self.stack.truncate(self.last_subtree);
39 impl<'tcx> Iterator for TypeWalker<'tcx> {
42 fn next(&mut self) -> Option<Ty<'tcx>> {
43 debug!("next(): stack={:?}", self.stack);
44 match self.stack.pop() {
47 self.last_subtree = self.stack.len();
48 push_subtypes(&mut self.stack, ty);
49 debug!("next: stack={:?}", self.stack);
56 pub fn walk_shallow(ty: Ty<'_>) -> smallvec::IntoIter<TypeWalkerArray<'_>> {
57 let mut stack = SmallVec::new();
58 push_subtypes(&mut stack, ty);
62 // We push types on the stack in reverse order so as to
63 // maintain a pre-order traversal. As of the time of this
64 // writing, the fact that the traversal is pre-order is not
65 // known to be significant to any code, but it seems like the
66 // natural order one would expect (basically, the order of the
67 // types as they are written).
68 fn push_subtypes<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent_ty: Ty<'tcx>) {
69 match parent_ty.kind {
82 | ty::Foreign(..) => {}
83 ty::Array(ty, len) => {
84 if let ty::ConstKind::Unevaluated(_, substs, promoted) = len.val {
85 assert!(promoted.is_none());
86 stack.extend(substs.types().rev());
94 ty::RawPtr(ref mt) => {
97 ty::Ref(_, ty, _) => {
100 ty::Projection(ref data) | ty::UnnormalizedProjection(ref data) => {
101 stack.extend(data.substs.types().rev());
103 ty::Dynamic(ref obj, ..) => {
104 stack.extend(obj.iter().rev().flat_map(|predicate| {
105 let (substs, opt_ty) = match *predicate.skip_binder() {
106 ty::ExistentialPredicate::Trait(tr) => (tr.substs, None),
107 ty::ExistentialPredicate::Projection(p) => (p.substs, Some(p.ty)),
108 ty::ExistentialPredicate::AutoTrait(_) =>
111 (ty::InternalSubsts::empty(), None)
115 substs.types().rev().chain(opt_ty)
118 ty::Adt(_, substs) | ty::Opaque(_, substs) => {
119 stack.extend(substs.types().rev());
121 ty::Closure(_, ref substs) | ty::Generator(_, ref substs, _) => {
122 stack.extend(substs.types().rev());
124 ty::GeneratorWitness(ts) => {
125 stack.extend(ts.skip_binder().iter().cloned().rev());
128 stack.extend(parent_ty.tuple_fields().rev());
130 ty::FnDef(_, substs) => {
131 stack.extend(substs.types().rev());
134 stack.push(sig.skip_binder().output());
135 stack.extend(sig.skip_binder().inputs().iter().cloned().rev());