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