src/librustc_middle/ty/walk.rs

   1 //! An iterator over the type substructure.
   2 //! WARNING: this does not keep track of the region depth.
   3
   4 use crate::ty;
   5 use crate::ty::subst::{GenericArg, GenericArgKind};
   6 use smallvec::{self, SmallVec};
   7
   8 // The TypeWalker's stack is hot enough that it's worth going to some effort to
   9 // avoid heap allocations.
  10 type TypeWalkerStack<'tcx> = SmallVec<[GenericArg<'tcx>; 8]>;
  11
  12 pub struct TypeWalker<'tcx> {
  13     stack: TypeWalkerStack<'tcx>,
  14     last_subtree: usize,
  15 }
  16
  17 impl<'tcx> TypeWalker<'tcx> {
  18     pub fn new(root: GenericArg<'tcx>) -> TypeWalker<'tcx> {
  19         TypeWalker { stack: smallvec![root], last_subtree: 1 }
  20     }
  21
  22     /// Skips the subtree corresponding to the last type
  23     /// returned by `next()`.
  24     ///
  25     /// Example: Imagine you are walking `Foo<Bar<int>, usize>`.
  26     ///
  27     /// ```
  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
  33     /// ```
  34     pub fn skip_current_subtree(&mut self) {
  35         self.stack.truncate(self.last_subtree);
  36     }
  37 }
  38
  39 impl<'tcx> Iterator for TypeWalker<'tcx> {
  40     type Item = GenericArg<'tcx>;
  41
  42     fn next(&mut self) -> Option<GenericArg<'tcx>> {
  43         debug!("next(): stack={:?}", self.stack);
  44         let next = self.stack.pop()?;
  45         self.last_subtree = self.stack.len();
  46         push_inner(&mut self.stack, next);
  47         debug!("next: stack={:?}", self.stack);
  48         Some(next)
  49     }
  50 }
  51
  52 impl GenericArg<'tcx> {
  53     /// Iterator that walks `self` and any types reachable from
  54     /// `self`, in depth-first order. Note that just walks the types
  55     /// that appear in `self`, it does not descend into the fields of
  56     /// structs or variants. For example:
  57     ///
  58     /// ```notrust
  59     /// isize => { isize }
  60     /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
  61     /// [isize] => { [isize], isize }
  62     /// ```
  63     pub fn walk(self) -> TypeWalker<'tcx> {
  64         TypeWalker::new(self)
  65     }
  66
  67     /// Iterator that walks the immediate children of `self`. Hence
  68     /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]`
  69     /// (but not `i32`, like `walk`).
  70     pub fn walk_shallow(self) -> impl Iterator<Item = GenericArg<'tcx>> {
  71         let mut stack = SmallVec::new();
  72         push_inner(&mut stack, self);
  73         stack.into_iter()
  74     }
  75 }
  76
  77 impl<'tcx> super::TyS<'tcx> {
  78     /// Iterator that walks `self` and any types reachable from
  79     /// `self`, in depth-first order. Note that just walks the types
  80     /// that appear in `self`, it does not descend into the fields of
  81     /// structs or variants. For example:
  82     ///
  83     /// ```notrust
  84     /// isize => { isize }
  85     /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
  86     /// [isize] => { [isize], isize }
  87     /// ```
  88     pub fn walk(&'tcx self) -> TypeWalker<'tcx> {
  89         TypeWalker::new(self.into())
  90     }
  91 }
  92
  93 // We push `GenericArg`s on the stack in reverse order so as to
  94 // maintain a pre-order traversal. As of the time of this
  95 // writing, the fact that the traversal is pre-order is not
  96 // known to be significant to any code, but it seems like the
  97 // natural order one would expect (basically, the order of the
  98 // types as they are written).
  99 fn push_inner<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent: GenericArg<'tcx>) {
 100     match parent.unpack() {
 101         GenericArgKind::Type(parent_ty) => match parent_ty.kind {
 102             ty::Bool
 103             | ty::Char
 104             | ty::Int(_)
 105             | ty::Uint(_)
 106             | ty::Float(_)
 107             | ty::Str
 108             | ty::Infer(_)
 109             | ty::Param(_)
 110             | ty::Never
 111             | ty::Error
 112             | ty::Placeholder(..)
 113             | ty::Bound(..)
 114             | ty::Foreign(..) => {}
 115
 116             ty::Array(ty, len) => {
 117                 stack.push(len.into());
 118                 stack.push(ty.into());
 119             }
 120             ty::Slice(ty) => {
 121                 stack.push(ty.into());
 122             }
 123             ty::RawPtr(mt) => {
 124                 stack.push(mt.ty.into());
 125             }
 126             ty::Ref(lt, ty, _) => {
 127                 stack.push(ty.into());
 128                 stack.push(lt.into());
 129             }
 130             ty::Projection(data) | ty::UnnormalizedProjection(data) => {
 131                 stack.extend(data.substs.iter().copied().rev());
 132             }
 133             ty::Dynamic(obj, lt) => {
 134                 stack.push(lt.into());
 135                 stack.extend(obj.iter().rev().flat_map(|predicate| {
 136                     let (substs, opt_ty) = match *predicate.skip_binder() {
 137                         ty::ExistentialPredicate::Trait(tr) => (tr.substs, None),
 138                         ty::ExistentialPredicate::Projection(p) => (p.substs, Some(p.ty)),
 139                         ty::ExistentialPredicate::AutoTrait(_) =>
 140                         // Empty iterator
 141                         {
 142                             (ty::InternalSubsts::empty(), None)
 143                         }
 144                     };
 145
 146                     substs.iter().copied().rev().chain(opt_ty.map(|ty| ty.into()))
 147                 }));
 148             }
 149             ty::Adt(_, substs)
 150             | ty::Opaque(_, substs)
 151             | ty::Closure(_, substs)
 152             | ty::Generator(_, substs, _)
 153             | ty::Tuple(substs)
 154             | ty::FnDef(_, substs) => {
 155                 stack.extend(substs.iter().copied().rev());
 156             }
 157             ty::GeneratorWitness(ts) => {
 158                 stack.extend(ts.skip_binder().iter().cloned().rev().map(|ty| ty.into()));
 159             }
 160             ty::FnPtr(sig) => {
 161                 stack.push(sig.skip_binder().output().into());
 162                 stack.extend(sig.skip_binder().inputs().iter().cloned().rev().map(|ty| ty.into()));
 163             }
 164         },
 165         GenericArgKind::Lifetime(_) => {}
 166         GenericArgKind::Const(parent_ct) => {
 167             stack.push(parent_ct.ty.into());
 168             match parent_ct.val {
 169                 ty::ConstKind::Infer(_)
 170                 | ty::ConstKind::Param(_)
 171                 | ty::ConstKind::Placeholder(_)
 172                 | ty::ConstKind::Bound(..)
 173                 | ty::ConstKind::Value(_)
 174                 | ty::ConstKind::Error => {}
 175
 176                 ty::ConstKind::Unevaluated(_, substs, _) => {
 177                     stack.extend(substs.iter().copied().rev());
 178                 }
 179             }
 180         }
 181     }
 182 }