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 use crate::mir::interpret::ConstValue;
   7
   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>>;
  12
  13 pub struct TypeWalker<'tcx> {
  14     stack: TypeWalkerStack<'tcx>,
  15     last_subtree: usize,
  16 }
  17
  18 impl<'tcx> TypeWalker<'tcx> {
  19     pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
  20         TypeWalker { stack: smallvec![ty], last_subtree: 1, }
  21     }
  22
  23     /// Skips the subtree of types corresponding to the last type
  24     /// returned by `next()`.
  25     ///
  26     /// Example: Imagine you are walking `Foo<Bar<int>, usize>`.
  27     ///
  28     /// ```
  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
  34     /// ```
  35     pub fn skip_current_subtree(&mut self) {
  36         self.stack.truncate(self.last_subtree);
  37     }
  38 }
  39
  40 impl<'tcx> Iterator for TypeWalker<'tcx> {
  41     type Item = Ty<'tcx>;
  42
  43     fn next(&mut self) -> Option<Ty<'tcx>> {
  44         debug!("next(): stack={:?}", self.stack);
  45         match self.stack.pop() {
  46             None => {
  47                 None
  48             }
  49             Some(ty) => {
  50                 self.last_subtree = self.stack.len();
  51                 push_subtypes(&mut self.stack, ty);
  52                 debug!("next: stack={:?}", self.stack);
  53                 Some(ty)
  54             }
  55         }
  56     }
  57 }
  58
  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);
  62     stack.into_iter()
  63 }
  64
  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>) {
  72     match parent_ty.sty {
  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(..) => {
  76         }
  77         ty::Array(ty, len) => {
  78             if let ConstValue::Unevaluated(_, substs) = len.val {
  79                 stack.extend(substs.types().rev());
  80             }
  81             stack.push(len.ty);
  82             stack.push(ty);
  83         }
  84         ty::Slice(ty) => {
  85             stack.push(ty);
  86         }
  87         ty::RawPtr(ref mt) => {
  88             stack.push(mt.ty);
  89         }
  90         ty::Ref(_, ty, _) => {
  91             stack.push(ty);
  92         }
  93         ty::Projection(ref data) | ty::UnnormalizedProjection(ref data) => {
  94             stack.extend(data.substs.types().rev());
  95         }
  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(_) =>
 103                         // Empty iterator
 104                         (ty::InternalSubsts::empty(), None),
 105                 };
 106
 107                 substs.types().rev().chain(opt_ty)
 108             }));
 109         }
 110         ty::Adt(_, substs) | ty::Opaque(_, substs) => {
 111             stack.extend(substs.types().rev());
 112         }
 113         ty::Closure(_, ref substs) => {
 114             stack.extend(substs.substs.types().rev());
 115         }
 116         ty::Generator(_, ref substs, _) => {
 117             stack.extend(substs.substs.types().rev());
 118         }
 119         ty::GeneratorWitness(ts) => {
 120             stack.extend(ts.skip_binder().iter().cloned().rev());
 121         }
 122         ty::Tuple(ts) => {
 123             stack.extend(ts.iter().map(|k| k.expect_ty()).rev());
 124         }
 125         ty::FnDef(_, substs) => {
 126             stack.extend(substs.types().rev());
 127         }
 128         ty::FnPtr(sig) => {
 129             stack.push(sig.skip_binder().output());
 130             stack.extend(sig.skip_binder().inputs().iter().cloned().rev());
 131         }
 132     }
 133 }