src/librustc/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::{self, Ty};
   5 use smallvec::{self, SmallVec};
   6
   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>>;
  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(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
  19         TypeWalker { stack: smallvec![ty], last_subtree: 1 }
  20     }
  21
  22     /// Skips the subtree of types 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 = Ty<'tcx>;
  41
  42     fn next(&mut self) -> Option<Ty<'tcx>> {
  43         debug!("next(): stack={:?}", self.stack);
  44         match self.stack.pop() {
  45             None => None,
  46             Some(ty) => {
  47                 self.last_subtree = self.stack.len();
  48                 push_subtypes(&mut self.stack, ty);
  49                 debug!("next: stack={:?}", self.stack);
  50                 Some(ty)
  51             }
  52         }
  53     }
  54 }
  55
  56 pub fn walk_shallow(ty: Ty<'_>) -> smallvec::IntoIter<TypeWalkerArray<'_>> {
  57     let mut stack = SmallVec::new();
  58     push_subtypes(&mut stack, ty);
  59     stack.into_iter()
  60 }
  61
  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 {
  70         ty::Bool
  71         | ty::Char
  72         | ty::Int(_)
  73         | ty::Uint(_)
  74         | ty::Float(_)
  75         | ty::Str
  76         | ty::Infer(_)
  77         | ty::Param(_)
  78         | ty::Never
  79         | ty::Error
  80         | ty::Placeholder(..)
  81         | ty::Bound(..)
  82         | ty::Foreign(..) => {}
  83         ty::Array(ty, len) => {
  84             if let ty::ConstKind::Unevaluated(_, substs) = len.val {
  85                 stack.extend(substs.types().rev());
  86             }
  87             stack.push(len.ty);
  88             stack.push(ty);
  89         }
  90         ty::Slice(ty) => {
  91             stack.push(ty);
  92         }
  93         ty::RawPtr(ref mt) => {
  94             stack.push(mt.ty);
  95         }
  96         ty::Ref(_, ty, _) => {
  97             stack.push(ty);
  98         }
  99         ty::Projection(ref data) | ty::UnnormalizedProjection(ref data) => {
 100             stack.extend(data.substs.types().rev());
 101         }
 102         ty::Dynamic(ref obj, ..) => {
 103             stack.extend(obj.iter().rev().flat_map(|predicate| {
 104                 let (substs, opt_ty) = match *predicate.skip_binder() {
 105                     ty::ExistentialPredicate::Trait(tr) => (tr.substs, None),
 106                     ty::ExistentialPredicate::Projection(p) => (p.substs, Some(p.ty)),
 107                     ty::ExistentialPredicate::AutoTrait(_) =>
 108                     // Empty iterator
 109                     {
 110                         (ty::InternalSubsts::empty(), None)
 111                     }
 112                 };
 113
 114                 substs.types().rev().chain(opt_ty)
 115             }));
 116         }
 117         ty::Adt(_, substs) | ty::Opaque(_, substs) => {
 118             stack.extend(substs.types().rev());
 119         }
 120         ty::Closure(_, ref substs) | ty::Generator(_, ref substs, _) => {
 121             stack.extend(substs.types().rev());
 122         }
 123         ty::GeneratorWitness(ts) => {
 124             stack.extend(ts.skip_binder().iter().cloned().rev());
 125         }
 126         ty::Tuple(..) => {
 127             stack.extend(parent_ty.tuple_fields().rev());
 128         }
 129         ty::FnDef(_, substs) => {
 130             stack.extend(substs.types().rev());
 131         }
 132         ty::FnPtr(sig) => {
 133             stack.push(sig.skip_binder().output());
 134             stack.extend(sig.skip_binder().inputs().iter().cloned().rev());
 135         }
 136     }
 137 }