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.
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.
11 //! An iterator over the type substructure.
12 //! WARNING: this does not keep track of the region depth.
15 use std
::iter
::Iterator
;
16 use std
::vec
::IntoIter
;
18 pub struct TypeWalker
<'tcx
> {
23 impl<'tcx
> TypeWalker
<'tcx
> {
24 pub fn new(ty
: Ty
<'tcx
>) -> TypeWalker
<'tcx
> {
25 TypeWalker { stack: vec!(ty), last_subtree: 1, }
28 /// Skips the subtree of types corresponding to the last type
29 /// returned by `next()`.
31 /// Example: Imagine you are walking `Foo<Bar<int>, usize>`.
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
40 pub fn skip_current_subtree(&mut self) {
41 self.stack
.truncate(self.last_subtree
);
45 impl<'tcx
> Iterator
for TypeWalker
<'tcx
> {
48 fn next(&mut self) -> Option
<Ty
<'tcx
>> {
49 debug
!("next(): stack={:?}", self.stack
);
50 match self.stack
.pop() {
55 self.last_subtree
= self.stack
.len();
56 push_subtypes(&mut self.stack
, ty
);
57 debug
!("next: stack={:?}", self.stack
);
64 pub fn walk_shallow
<'tcx
>(ty
: Ty
<'tcx
>) -> IntoIter
<Ty
<'tcx
>> {
65 let mut stack
= vec
![];
66 push_subtypes(&mut stack
, ty
);
70 fn push_subtypes
<'tcx
>(stack
: &mut Vec
<Ty
<'tcx
>>, parent_ty
: Ty
<'tcx
>) {
72 ty
::TyBool
| ty
::TyChar
| ty
::TyInt(_
) | ty
::TyUint(_
) | ty
::TyFloat(_
) |
73 ty
::TyStr
| ty
::TyInfer(_
) | ty
::TyParam(_
) | ty
::TyError
=> {
75 ty
::TyBox(ty
) | ty
::TyArray(ty
, _
) | ty
::TySlice(ty
) => {
78 ty
::TyRawPtr(ref mt
) | ty
::TyRef(_
, ref mt
) => {
81 ty
::TyProjection(ref data
) => {
82 push_reversed(stack
, data
.trait_ref
.substs
.types
.as_slice());
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
| {
88 }).collect
::<Vec
<_
>>());
90 ty
::TyEnum(_
, ref substs
) |
91 ty
::TyStruct(_
, ref substs
) => {
92 push_reversed(stack
, substs
.types
.as_slice());
94 ty
::TyClosure(_
, ref substs
) => {
95 push_reversed(stack
, substs
.func_substs
.types
.as_slice());
96 push_reversed(stack
, &substs
.upvar_tys
);
98 ty
::TyTuple(ref ts
) => {
99 push_reversed(stack
, ts
);
101 ty
::TyFnDef(_
, substs
, ref ft
) => {
102 push_reversed(stack
, substs
.types
.as_slice());
103 push_sig_subtypes(stack
, &ft
.sig
);
105 ty
::TyFnPtr(ref ft
) => {
106 push_sig_subtypes(stack
, &ft
.sig
);
111 fn push_sig_subtypes
<'tcx
>(stack
: &mut Vec
<Ty
<'tcx
>>, sig
: &ty
::PolyFnSig
<'tcx
>) {
113 ty
::FnConverging(output
) => { stack.push(output); }
114 ty
::FnDiverging
=> { }
116 push_reversed(stack
, &sig
.0.inputs
);
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() {