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::{mod, Ty};
  14 use std::iter::Iterator;
  15
  16 pub struct TypeWalker<'tcx> {
  17     stack: Vec<Ty<'tcx>>,
  18     last_subtree: uint,
  19 }
  20
  21 impl<'tcx> TypeWalker<'tcx> {
  22     pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
  23         TypeWalker { stack: vec!(ty), last_subtree: 1, }
  24     }
  25
  26     fn push_subtypes(&mut self, parent_ty: Ty<'tcx>) {
  27         match parent_ty.sty {
  28             ty::ty_bool | ty::ty_char | ty::ty_int(_) | ty::ty_uint(_) | ty::ty_float(_) |
  29             ty::ty_str | ty::ty_infer(_) | ty::ty_param(_) | ty::ty_err => {
  30             }
  31             ty::ty_uniq(ty) | ty::ty_vec(ty, _) | ty::ty_open(ty) => {
  32                 self.stack.push(ty);
  33             }
  34             ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => {
  35                 self.stack.push(mt.ty);
  36             }
  37             ty::ty_projection(ref data) => {
  38                 self.push_reversed(data.trait_ref.substs.types.as_slice());
  39             }
  40             ty::ty_trait(box ty::TyTrait { ref principal, .. }) => {
  41                 self.push_reversed(principal.substs().types.as_slice());
  42             }
  43             ty::ty_enum(_, ref substs) |
  44             ty::ty_struct(_, ref substs) |
  45             ty::ty_unboxed_closure(_, _, ref substs) => {
  46                 self.push_reversed(substs.types.as_slice());
  47             }
  48             ty::ty_tup(ref ts) => {
  49                 self.push_reversed(ts.as_slice());
  50             }
  51             ty::ty_bare_fn(_, ref ft) => {
  52                 self.push_sig_subtypes(&ft.sig);
  53             }
  54             ty::ty_closure(ref ft) => {
  55                 self.push_sig_subtypes(&ft.sig);
  56             }
  57         }
  58     }
  59
  60     fn push_sig_subtypes(&mut self, sig: &ty::PolyFnSig<'tcx>) {
  61         match sig.0.output {
  62             ty::FnConverging(output) => { self.stack.push(output); }
  63             ty::FnDiverging => { }
  64         }
  65         self.push_reversed(sig.0.inputs.as_slice());
  66     }
  67
  68     fn push_reversed(&mut self, tys: &[Ty<'tcx>]) {
  69         // We push slices on the stack in reverse order so as to
  70         // maintain a pre-order traversal. As of the time of this
  71         // writing, the fact that the traversal is pre-order is not
  72         // known to be significant to any code, but it seems like the
  73         // natural order one would expect (basically, the order of the
  74         // types as they are written).
  75         for &ty in tys.iter().rev() {
  76             self.stack.push(ty);
  77         }
  78     }
  79
  80     /// Skips the subtree of types corresponding to the last type
  81     /// returned by `next()`.
  82     ///
  83     /// Example: Imagine you are walking `Foo<Bar<int>, uint>`.
  84     ///
  85     /// ```rust
  86     /// let mut iter: TypeWalker = ...;
  87     /// iter.next(); // yields Foo
  88     /// iter.next(); // yields Bar<int>
  89     /// iter.skip_current_subtree(); // skips int
  90     /// iter.next(); // yields uint
  91     /// ```
  92     pub fn skip_current_subtree(&mut self) {
  93         self.stack.truncate(self.last_subtree);
  94     }
  95 }
  96
  97 impl<'tcx> Iterator for TypeWalker<'tcx> {
  98     type Item = Ty<'tcx>;
  99
 100     fn next(&mut self) -> Option<Ty<'tcx>> {
 101         debug!("next(): stack={}", self.stack);
 102         match self.stack.pop() {
 103             None => {
 104                 return None;
 105             }
 106             Some(ty) => {
 107                 self.last_subtree = self.stack.len();
 108                 self.push_subtypes(ty);
 109                 debug!("next: stack={}", self.stack);
 110                 Some(ty)
 111             }
 112         }
 113     }
 114 }