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 ty::{self, Ty};
  15 use std::iter::Iterator;
  16 use std::vec::IntoIter;
  17
  18 pub struct TypeWalker<'tcx> {
  19     stack: Vec<Ty<'tcx>>,
  20     last_subtree: usize,
  21 }
  22
  23 impl<'tcx> TypeWalker<'tcx> {
  24     pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
  25         TypeWalker { stack: vec!(ty), last_subtree: 1, }
  26     }
  27
  28     /// Skips the subtree of types corresponding to the last type
  29     /// returned by `next()`.
  30     ///
  31     /// Example: Imagine you are walking `Foo<Bar<int>, usize>`.
  32     ///
  33     /// ```
  34     /// let mut iter: TypeWalker = ...;
  35     /// iter.next(); // yields Foo
  36     /// iter.next(); // yields Bar<int>
  37     /// iter.skip_current_subtree(); // skips int
  38     /// iter.next(); // yields usize
  39     /// ```
  40     pub fn skip_current_subtree(&mut self) {
  41         self.stack.truncate(self.last_subtree);
  42     }
  43 }
  44
  45 impl<'tcx> Iterator for TypeWalker<'tcx> {
  46     type Item = Ty<'tcx>;
  47
  48     fn next(&mut self) -> Option<Ty<'tcx>> {
  49         debug!("next(): stack={:?}", self.stack);
  50         match self.stack.pop() {
  51             None => {
  52                 return None;
  53             }
  54             Some(ty) => {
  55                 self.last_subtree = self.stack.len();
  56                 push_subtypes(&mut self.stack, ty);
  57                 debug!("next: stack={:?}", self.stack);
  58                 Some(ty)
  59             }
  60         }
  61     }
  62 }
  63
  64 pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> IntoIter<Ty<'tcx>> {
  65     let mut stack = vec![];
  66     push_subtypes(&mut stack, ty);
  67     stack.into_iter()
  68 }
  69
  70 fn push_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, parent_ty: Ty<'tcx>) {
  71     match parent_ty.sty {
  72         ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
  73         ty::TyStr | ty::TyInfer(_) | ty::TyParam(_) | ty::TyError => {
  74         }
  75         ty::TyBox(ty) | ty::TyArray(ty, _) | ty::TySlice(ty) => {
  76             stack.push(ty);
  77         }
  78         ty::TyRawPtr(ref mt) | ty::TyRef(_, ref mt) => {
  79             stack.push(mt.ty);
  80         }
  81         ty::TyProjection(ref data) => {
  82             push_reversed(stack, data.trait_ref.substs.types.as_slice());
  83         }
  84         ty::TyTrait(box ty::TraitTy { ref principal, ref bounds }) => {
  85             push_reversed(stack, principal.substs().types.as_slice());
  86             push_reversed(stack, &bounds.projection_bounds.iter().map(|pred| {
  87                 pred.0.ty
  88             }).collect::<Vec<_>>());
  89         }
  90         ty::TyEnum(_, ref substs) |
  91         ty::TyStruct(_, ref substs) => {
  92             push_reversed(stack, substs.types.as_slice());
  93         }
  94         ty::TyClosure(_, ref substs) => {
  95             push_reversed(stack, substs.func_substs.types.as_slice());
  96             push_reversed(stack, &substs.upvar_tys);
  97         }
  98         ty::TyTuple(ref ts) => {
  99             push_reversed(stack, ts);
 100         }
 101         ty::TyFnDef(_, substs, ref ft) => {
 102             push_reversed(stack, substs.types.as_slice());
 103             push_sig_subtypes(stack, &ft.sig);
 104         }
 105         ty::TyFnPtr(ref ft) => {
 106             push_sig_subtypes(stack, &ft.sig);
 107         }
 108     }
 109 }
 110
 111 fn push_sig_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, sig: &ty::PolyFnSig<'tcx>) {
 112     match sig.0.output {
 113         ty::FnConverging(output) => { stack.push(output); }
 114         ty::FnDiverging => { }
 115     }
 116     push_reversed(stack, &sig.0.inputs);
 117 }
 118
 119 fn push_reversed<'tcx>(stack: &mut Vec<Ty<'tcx>>, tys: &[Ty<'tcx>]) {
 120     // We push slices on the stack in reverse order so as to
 121     // maintain a pre-order traversal. As of the time of this
 122     // writing, the fact that the traversal is pre-order is not
 123     // known to be significant to any code, but it seems like the
 124     // natural order one would expect (basically, the order of the
 125     // types as they are written).
 126     for &ty in tys.iter().rev() {
 127         stack.push(ty);
 128     }
 129 }