]>
Commit | Line | Data |
---|---|---|
32a655c1 SL |
1 | // Copyright 2012-2015 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 | use std::mem; | |
12 | use rustc_data_structures::small_vec::SmallVec; | |
13 | use syntax::ast::CRATE_NODE_ID; | |
14 | use ty::context::TyCtxt; | |
15 | use ty::{DefId, DefIdTree}; | |
16 | ||
17 | /// Represents a forest of DefIds closed under the ancestor relation. That is, | |
18 | /// if a DefId representing a module is contained in the forest then all | |
19 | /// DefIds defined in that module or submodules are also implicitly contained | |
20 | /// in the forest. | |
21 | /// | |
22 | /// This is used to represent a set of modules in which a type is visibly | |
23 | /// uninhabited. | |
24 | #[derive(Clone)] | |
25 | pub struct DefIdForest { | |
26 | /// The minimal set of DefIds required to represent the whole set. | |
27 | /// If A and B are DefIds in the DefIdForest, and A is a desecendant | |
28 | /// of B, then only B will be in root_ids. | |
29 | /// We use a SmallVec here because (for its use for cacheing inhabitedness) | |
30 | /// its rare that this will contain even two ids. | |
31 | root_ids: SmallVec<[DefId; 1]>, | |
32 | } | |
33 | ||
34 | impl<'a, 'gcx, 'tcx> DefIdForest { | |
35 | /// Create an empty forest. | |
36 | pub fn empty() -> DefIdForest { | |
37 | DefIdForest { | |
38 | root_ids: SmallVec::new(), | |
39 | } | |
40 | } | |
41 | ||
42 | /// Create a forest consisting of a single tree representing the entire | |
43 | /// crate. | |
44 | #[inline] | |
45 | pub fn full(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest { | |
46 | let crate_id = tcx.hir.local_def_id(CRATE_NODE_ID); | |
47 | DefIdForest::from_id(crate_id) | |
48 | } | |
49 | ||
50 | /// Create a forest containing a DefId and all its descendants. | |
51 | pub fn from_id(id: DefId) -> DefIdForest { | |
52 | let mut root_ids = SmallVec::new(); | |
53 | root_ids.push(id); | |
54 | DefIdForest { | |
041b39d2 | 55 | root_ids, |
32a655c1 SL |
56 | } |
57 | } | |
58 | ||
59 | /// Test whether the forest is empty. | |
60 | pub fn is_empty(&self) -> bool { | |
61 | self.root_ids.is_empty() | |
62 | } | |
63 | ||
64 | /// Test whether the forest conains a given DefId. | |
65 | pub fn contains(&self, | |
66 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
67 | id: DefId) -> bool | |
68 | { | |
69 | for root_id in self.root_ids.iter() { | |
70 | if tcx.is_descendant_of(id, *root_id) { | |
71 | return true; | |
72 | } | |
73 | } | |
74 | false | |
75 | } | |
76 | ||
77 | /// Calculate the intersection of a collection of forests. | |
78 | pub fn intersection<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
79 | iter: I) -> DefIdForest | |
80 | where I: IntoIterator<Item=DefIdForest> | |
81 | { | |
82 | let mut ret = DefIdForest::full(tcx); | |
83 | let mut next_ret = SmallVec::new(); | |
84 | let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new(); | |
85 | for next_forest in iter { | |
86 | for id in ret.root_ids.drain(..) { | |
87 | if next_forest.contains(tcx, id) { | |
88 | next_ret.push(id); | |
89 | } else { | |
90 | old_ret.push(id); | |
91 | } | |
92 | } | |
93 | ret.root_ids.extend(old_ret.drain(..)); | |
94 | ||
95 | for id in next_forest.root_ids { | |
96 | if ret.contains(tcx, id) { | |
97 | next_ret.push(id); | |
98 | } | |
99 | } | |
100 | ||
101 | mem::swap(&mut next_ret, &mut ret.root_ids); | |
102 | next_ret.drain(..); | |
103 | } | |
104 | ret | |
105 | } | |
106 | ||
107 | /// Calculate the union of a collection of forests. | |
108 | pub fn union<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
109 | iter: I) -> DefIdForest | |
110 | where I: IntoIterator<Item=DefIdForest> | |
111 | { | |
112 | let mut ret = DefIdForest::empty(); | |
113 | let mut next_ret = SmallVec::new(); | |
114 | for next_forest in iter { | |
115 | for id in ret.root_ids.drain(..) { | |
116 | if !next_forest.contains(tcx, id) { | |
117 | next_ret.push(id); | |
118 | } | |
119 | } | |
120 | ||
121 | for id in next_forest.root_ids { | |
122 | if !next_ret.contains(&id) { | |
123 | next_ret.push(id); | |
124 | } | |
125 | } | |
126 | ||
127 | mem::swap(&mut next_ret, &mut ret.root_ids); | |
128 | next_ret.drain(..); | |
129 | } | |
130 | ret | |
131 | } | |
132 | } | |
133 |