]> git.proxmox.com Git - rustc.git/blob - src/librustc/ty/walk.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / 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 }