1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
use std::mem;
use rustc_data_structures::small_vec::SmallVec;
use syntax::ast::CRATE_NODE_ID;
use ty::context::TyCtxt;
use ty::{DefId, DefIdTree};
#[derive(Clone)]
pub struct DefIdForest {
root_ids: SmallVec<[DefId; 1]>,
}
impl<'a, 'gcx, 'tcx> DefIdForest {
pub fn empty() -> DefIdForest {
DefIdForest {
root_ids: SmallVec::new(),
}
}
#[inline]
pub fn full(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest {
let crate_id = tcx.hir.local_def_id(CRATE_NODE_ID);
DefIdForest::from_id(crate_id)
}
pub fn from_id(id: DefId) -> DefIdForest {
let mut root_ids = SmallVec::new();
root_ids.push(id);
DefIdForest {
root_ids: root_ids,
}
}
pub fn is_empty(&self) -> bool {
self.root_ids.is_empty()
}
pub fn contains(&self,
tcx: TyCtxt<'a, 'gcx, 'tcx>,
id: DefId) -> bool
{
for root_id in self.root_ids.iter() {
if tcx.is_descendant_of(id, *root_id) {
return true;
}
}
false
}
pub fn intersection<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
iter: I) -> DefIdForest
where I: IntoIterator<Item=DefIdForest>
{
let mut ret = DefIdForest::full(tcx);
let mut next_ret = SmallVec::new();
let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new();
for next_forest in iter {
for id in ret.root_ids.drain(..) {
if next_forest.contains(tcx, id) {
next_ret.push(id);
} else {
old_ret.push(id);
}
}
ret.root_ids.extend(old_ret.drain(..));
for id in next_forest.root_ids {
if ret.contains(tcx, id) {
next_ret.push(id);
}
}
mem::swap(&mut next_ret, &mut ret.root_ids);
next_ret.drain(..);
}
ret
}
pub fn union<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
iter: I) -> DefIdForest
where I: IntoIterator<Item=DefIdForest>
{
let mut ret = DefIdForest::empty();
let mut next_ret = SmallVec::new();
for next_forest in iter {
for id in ret.root_ids.drain(..) {
if !next_forest.contains(tcx, id) {
next_ret.push(id);
}
}
for id in next_forest.root_ids {
if !next_ret.contains(&id) {
next_ret.push(id);
}
}
mem::swap(&mut next_ret, &mut ret.root_ids);
next_ret.drain(..);
}
ret
}
}