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.
14 use middle::const_val::{ConstVal, ConstAggregate};
16 use rustc_data_structures::small_vec::SmallVec;
17 use rustc_data_structures::accumulate_vec::IntoIter as AccIntoIter;
19 // The TypeWalker's stack is hot enough that it's worth going to some effort to
20 // avoid heap allocations.
21 pub type TypeWalkerArray<'tcx> = [Ty<'tcx>; 8];
22 pub type TypeWalkerStack<'tcx> = SmallVec<TypeWalkerArray<'tcx>>;
24 pub struct TypeWalker<'tcx> {
25 stack: TypeWalkerStack<'tcx>,
29 impl<'tcx> TypeWalker<'tcx> {
30 pub fn new(ty: Ty<'tcx>) -> TypeWalker<'tcx> {
31 TypeWalker { stack: SmallVec::one(ty), last_subtree: 1, }
34 /// Skips the subtree of types corresponding to the last type
35 /// returned by `next()`.
37 /// Example: Imagine you are walking `Foo<Bar<int>, usize>`.
40 /// let mut iter: TypeWalker = ...;
41 /// iter.next(); // yields Foo
42 /// iter.next(); // yields Bar<int>
43 /// iter.skip_current_subtree(); // skips int
44 /// iter.next(); // yields usize
46 pub fn skip_current_subtree(&mut self) {
47 self.stack.truncate(self.last_subtree);
51 impl<'tcx> Iterator for TypeWalker<'tcx> {
54 fn next(&mut self) -> Option<Ty<'tcx>> {
55 debug!("next(): stack={:?}", self.stack);
56 match self.stack.pop() {
61 self.last_subtree = self.stack.len();
62 push_subtypes(&mut self.stack, ty);
63 debug!("next: stack={:?}", self.stack);
70 pub fn walk_shallow<'tcx>(ty: Ty<'tcx>) -> AccIntoIter<TypeWalkerArray<'tcx>> {
71 let mut stack = SmallVec::new();
72 push_subtypes(&mut stack, ty);
76 // We push types on the stack in reverse order so as to
77 // maintain a pre-order traversal. As of the time of this
78 // writing, the fact that the traversal is pre-order is not
79 // known to be significant to any code, but it seems like the
80 // natural order one would expect (basically, the order of the
81 // types as they are written).
82 fn push_subtypes<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent_ty: Ty<'tcx>) {
84 ty::TyBool | ty::TyChar | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) |
85 ty::TyStr | ty::TyInfer(_) | ty::TyParam(_) | ty::TyNever | ty::TyError |
86 ty::TyForeign(..) => {
88 ty::TyArray(ty, len) => {
89 push_const(stack, len);
95 ty::TyRawPtr(ref mt) | ty::TyRef(_, ref mt) => {
98 ty::TyProjection(ref data) => {
99 stack.extend(data.substs.types().rev());
101 ty::TyDynamic(ref obj, ..) => {
102 stack.extend(obj.iter().rev().flat_map(|predicate| {
103 let (substs, opt_ty) = match *predicate.skip_binder() {
104 ty::ExistentialPredicate::Trait(tr) => (tr.substs, None),
105 ty::ExistentialPredicate::Projection(p) =>
106 (p.substs, Some(p.ty)),
107 ty::ExistentialPredicate::AutoTrait(_) =>
109 (ty::Substs::empty(), None),
112 substs.types().rev().chain(opt_ty)
115 ty::TyAdt(_, substs) | ty::TyAnon(_, substs) => {
116 stack.extend(substs.types().rev());
118 ty::TyClosure(_, ref substs) => {
119 stack.extend(substs.substs.types().rev());
121 ty::TyGenerator(_, ref substs, ref interior) => {
122 stack.extend(substs.substs.types().rev());
123 stack.push(interior.witness);
125 ty::TyTuple(ts, _) => {
126 stack.extend(ts.iter().cloned().rev());
128 ty::TyFnDef(_, substs) => {
129 stack.extend(substs.types().rev());
131 ty::TyFnPtr(sig) => {
132 stack.push(sig.skip_binder().output());
133 stack.extend(sig.skip_binder().inputs().iter().cloned().rev());
138 fn push_const<'tcx>(stack: &mut TypeWalkerStack<'tcx>, constant: &'tcx ty::Const<'tcx>) {
140 ConstVal::Integral(_) |
143 ConstVal::ByteStr(_) |
146 ConstVal::Variant(_) => {}
147 ConstVal::Function(_, substs) => {
148 stack.extend(substs.types().rev());
150 ConstVal::Aggregate(ConstAggregate::Struct(fields)) => {
151 for &(_, v) in fields.iter().rev() {
152 push_const(stack, v);
155 ConstVal::Aggregate(ConstAggregate::Tuple(fields)) |
156 ConstVal::Aggregate(ConstAggregate::Array(fields)) => {
157 for v in fields.iter().rev() {
158 push_const(stack, v);
161 ConstVal::Aggregate(ConstAggregate::Repeat(v, _)) => {
162 push_const(stack, v);
164 ConstVal::Unevaluated(_, substs) => {
165 stack.extend(substs.types().rev());
168 stack.push(constant.ty);