src/librustc/middle/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::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::TyBareFn(_, ref ft) => {
 102             push_sig_subtypes(stack, &ft.sig);
 103         }
 104     }
 105 }
 106
 107 fn push_sig_subtypes<'tcx>(stack: &mut Vec<Ty<'tcx>>, sig: &ty::PolyFnSig<'tcx>) {
 108     match sig.0.output {
 109         ty::FnConverging(output) => { stack.push(output); }
 110         ty::FnDiverging => { }
 111     }
 112     push_reversed(stack, &sig.0.inputs);
 113 }
 114
 115 fn push_reversed<'tcx>(stack: &mut Vec<Ty<'tcx>>, tys: &[Ty<'tcx>]) {
 116     // We push slices on the stack in reverse order so as to
 117     // maintain a pre-order traversal. As of the time of this
 118     // writing, the fact that the traversal is pre-order is not
 119     // known to be significant to any code, but it seems like the
 120     // natural order one would expect (basically, the order of the
 121     // types as they are written).
 122     for &ty in tys.iter().rev() {
 123         stack.push(ty);
 124     }
 125 }