]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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. | |
c1a9b12d | 12 | //! WARNING: this does not keep track of the region depth. |
1a4d82fc JJ |
13 | |
14 | use middle::ty::{self, Ty}; | |
15 | use std::iter::Iterator; | |
c34b1796 | 16 | use std::vec::IntoIter; |
1a4d82fc JJ |
17 | |
18 | pub struct TypeWalker<'tcx> { | |
19 | stack: Vec<Ty<'tcx>>, | |
c34b1796 | 20 | last_subtree: usize, |
1a4d82fc JJ |
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 | ||
1a4d82fc JJ |
28 | /// Skips the subtree of types corresponding to the last type |
29 | /// returned by `next()`. | |
30 | /// | |
c34b1796 | 31 | /// Example: Imagine you are walking `Foo<Bar<int>, usize>`. |
1a4d82fc | 32 | /// |
c34b1796 | 33 | /// ``` |
1a4d82fc JJ |
34 | /// let mut iter: TypeWalker = ...; |
35 | /// iter.next(); // yields Foo | |
36 | /// iter.next(); // yields Bar<int> | |
37 | /// iter.skip_current_subtree(); // skips int | |
c34b1796 | 38 | /// iter.next(); // yields usize |
1a4d82fc JJ |
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(); | |
c34b1796 | 56 | push_subtypes(&mut self.stack, ty); |
1a4d82fc JJ |
57 | debug!("next: stack={:?}", self.stack); |
58 | Some(ty) | |
59 | } | |
60 | } | |
61 | } | |
62 | } | |
c34b1796 AL |
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 { | |
62682a34 SL |
72 | ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) | |
73 | ty::TyStr | ty::TyInfer(_) | ty::TyParam(_) | ty::TyError => { | |
c34b1796 | 74 | } |
62682a34 | 75 | ty::TyBox(ty) | ty::TyArray(ty, _) | ty::TySlice(ty) => { |
c34b1796 AL |
76 | stack.push(ty); |
77 | } | |
62682a34 | 78 | ty::TyRawPtr(ref mt) | ty::TyRef(_, ref mt) => { |
c34b1796 AL |
79 | stack.push(mt.ty); |
80 | } | |
62682a34 | 81 | ty::TyProjection(ref data) => { |
c34b1796 AL |
82 | push_reversed(stack, data.trait_ref.substs.types.as_slice()); |
83 | } | |
62682a34 | 84 | ty::TyTrait(box ty::TraitTy { ref principal, ref bounds }) => { |
c34b1796 AL |
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 | } | |
62682a34 | 90 | ty::TyEnum(_, ref substs) | |
c1a9b12d | 91 | ty::TyStruct(_, ref substs) => { |
c34b1796 AL |
92 | push_reversed(stack, substs.types.as_slice()); |
93 | } | |
c1a9b12d SL |
94 | ty::TyClosure(_, ref substs) => { |
95 | push_reversed(stack, substs.func_substs.types.as_slice()); | |
96 | push_reversed(stack, &substs.upvar_tys); | |
97 | } | |
62682a34 | 98 | ty::TyTuple(ref ts) => { |
c34b1796 AL |
99 | push_reversed(stack, ts); |
100 | } | |
62682a34 | 101 | ty::TyBareFn(_, ref ft) => { |
c34b1796 AL |
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 | } |