src/librustc/ty/walk.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! An iterator over the type substructure.
  12 //! WARNING: this does not keep track of the region depth.
  13
  14 use middle::const_val::ConstVal;
  15 use ty::{self, Ty};
  16 use rustc_data_structures::small_vec::SmallVec;
  17 use rustc_data_structures::accumulate_vec::IntoIter as AccIntoIter;
  18
  19 // The TypeWalker's stack is hot enough that it's worth going to some effort to
  20 // avoid heap allocations.
  21 pub type TypeWalkerArray<'tcx> = [Ty<'tcx>; 8];
  22 pub type TypeWalkerStack<'tcx> = SmallVec<TypeWalkerArray<'tcx>>;
  23
  24 pub struct TypeWalker<'tcx> {
  25     stack: TypeWalkerStack<'tcx>,
  26     last_subtree: usize,
  27 }
  28
  29 impl<'tcx> TypeWalker<'tcx> {
  30     pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
  31         TypeWalker { stack: SmallVec::one(ty), last_subtree: 1, }
  32     }
  33
  34     /// Skips the subtree of types corresponding to the last type
  35     /// returned by `next()`.
  36     ///
  37     /// Example: Imagine you are walking `Foo<Bar<int>, usize>`.
  38     ///
  39     /// ```
  40     /// let mut iter: TypeWalker = ...;
  41     /// iter.next(); // yields Foo
  42     /// iter.next(); // yields Bar<int>
  43     /// iter.skip_current_subtree(); // skips int
  44     /// iter.next(); // yields usize
  45     /// ```
  46     pub fn skip_current_subtree(&mut self) {
  47         self.stack.truncate(self.last_subtree);
  48     }
  49 }
  50
  51 impl<'tcx> Iterator for TypeWalker<'tcx> {
  52     type Item = Ty<'tcx>;
  53
  54     fn next(&mut self) -> Option<Ty<'tcx>> {
  55         debug!("next(): stack={:?}", self.stack);
  56         match self.stack.pop() {
  57             None => {
  58                 return None;
  59             }
  60             Some(ty) => {
  61                 self.last_subtree = self.stack.len();
  62                 push_subtypes(&mut self.stack, ty);
  63                 debug!("next: stack={:?}", self.stack);
  64                 Some(ty)
  65             }
  66         }
  67     }
  68 }
  69
  70 pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> AccIntoIter<TypeWalkerArray<'tcx>> {
  71     let mut stack = SmallVec::new();
  72     push_subtypes(&mut stack, ty);
  73     stack.into_iter()
  74 }
  75
  76 // We push types on the stack in reverse order so as to
  77 // maintain a pre-order traversal. As of the time of this
  78 // writing, the fact that the traversal is pre-order is not
  79 // known to be significant to any code, but it seems like the
  80 // natural order one would expect (basically, the order of the
  81 // types as they are written).
  82 fn push_subtypes<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent_ty: Ty<'tcx>) {
  83     match parent_ty.sty {
  84         ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
  85         ty::TyStr | ty::TyInfer(_) | ty::TyParam(_) | ty::TyNever | ty::TyError |
  86         ty::TyForeign(..) => {
  87         }
  88         ty::TyArray(ty, len) => {
  89             push_const(stack, len);
  90             stack.push(ty);
  91         }
  92         ty::TySlice(ty) => {
  93             stack.push(ty);
  94         }
  95         ty::TyRawPtr(ref mt) | ty::TyRef(_, ref mt) => {
  96             stack.push(mt.ty);
  97         }
  98         ty::TyProjection(ref data) => {
  99             stack.extend(data.substs.types().rev());
 100         }
 101         ty::TyDynamic(ref obj, ..) => {
 102             stack.extend(obj.iter().rev().flat_map(|predicate| {
 103                 let (substs, opt_ty) = match *predicate.skip_binder() {
 104                     ty::ExistentialPredicate::Trait(tr) => (tr.substs, None),
 105                     ty::ExistentialPredicate::Projection(p) =>
 106                         (p.substs, Some(p.ty)),
 107                     ty::ExistentialPredicate::AutoTrait(_) =>
 108                         // Empty iterator
 109                         (ty::Substs::empty(), None),
 110                 };
 111
 112                 substs.types().rev().chain(opt_ty)
 113             }));
 114         }
 115         ty::TyAdt(_, substs) | ty::TyAnon(_, substs) => {
 116             stack.extend(substs.types().rev());
 117         }
 118         ty::TyClosure(_, ref substs) => {
 119             stack.extend(substs.substs.types().rev());
 120         }
 121         ty::TyGenerator(_, ref substs, ref interior) => {
 122             stack.push(interior.witness);
 123             stack.extend(substs.substs.types().rev());
 124         }
 125         ty::TyGeneratorWitness(ts) => {
 126             stack.extend(ts.skip_binder().iter().cloned().rev());
 127         }
 128         ty::TyTuple(ts, _) => {
 129             stack.extend(ts.iter().cloned().rev());
 130         }
 131         ty::TyFnDef(_, substs) => {
 132             stack.extend(substs.types().rev());
 133         }
 134         ty::TyFnPtr(sig) => {
 135             stack.push(sig.skip_binder().output());
 136             stack.extend(sig.skip_binder().inputs().iter().cloned().rev());
 137         }
 138     }
 139 }
 140
 141 fn push_const<'tcx>(stack: &mut TypeWalkerStack<'tcx>, constant: &'tcx ty::Const<'tcx>) {
 142     match constant.val {
 143         ConstVal::Value(_) => {}
 144         ConstVal::Unevaluated(_, substs) => {
 145             stack.extend(substs.types().rev());
 146         }
 147     }
 148     stack.push(constant.ty);
 149 }