]>
Commit | Line | Data |
---|---|---|
32a655c1 | 1 | use std::mem; |
b7449926 | 2 | use smallvec::SmallVec; |
dc9dc135 | 3 | use rustc::hir::CRATE_HIR_ID; |
9fa01778 XL |
4 | use crate::ty::context::TyCtxt; |
5 | use crate::ty::{DefId, DefIdTree}; | |
32a655c1 | 6 | |
e1599b0c XL |
7 | /// Represents a forest of `DefId`s closed under the ancestor relation. That is, |
8 | /// if a `DefId` representing a module is contained in the forest then all | |
9 | /// `DefId`s defined in that module or submodules are also implicitly contained | |
32a655c1 SL |
10 | /// in the forest. |
11 | /// | |
12 | /// This is used to represent a set of modules in which a type is visibly | |
13 | /// uninhabited. | |
14 | #[derive(Clone)] | |
15 | pub struct DefIdForest { | |
e1599b0c XL |
16 | /// The minimal set of `DefId`s required to represent the whole set. |
17 | /// If A and B are DefIds in the `DefIdForest`, and A is a descendant | |
18 | /// of B, then only B will be in `root_ids`. | |
19 | /// We use a `SmallVec` here because (for its use for caching inhabitedness) | |
20 | /// its rare that this will contain even two IDs. | |
32a655c1 SL |
21 | root_ids: SmallVec<[DefId; 1]>, |
22 | } | |
23 | ||
dc9dc135 | 24 | impl<'tcx> DefIdForest { |
9fa01778 | 25 | /// Creates an empty forest. |
32a655c1 SL |
26 | pub fn empty() -> DefIdForest { |
27 | DefIdForest { | |
28 | root_ids: SmallVec::new(), | |
29 | } | |
30 | } | |
31 | ||
9fa01778 | 32 | /// Creates a forest consisting of a single tree representing the entire |
32a655c1 SL |
33 | /// crate. |
34 | #[inline] | |
dc9dc135 | 35 | pub fn full(tcx: TyCtxt<'tcx>) -> DefIdForest { |
416331ca | 36 | let crate_id = tcx.hir().local_def_id(CRATE_HIR_ID); |
32a655c1 SL |
37 | DefIdForest::from_id(crate_id) |
38 | } | |
39 | ||
e1599b0c | 40 | /// Creates a forest containing a `DefId` and all its descendants. |
32a655c1 SL |
41 | pub fn from_id(id: DefId) -> DefIdForest { |
42 | let mut root_ids = SmallVec::new(); | |
43 | root_ids.push(id); | |
44 | DefIdForest { | |
041b39d2 | 45 | root_ids, |
32a655c1 SL |
46 | } |
47 | } | |
48 | ||
9fa01778 | 49 | /// Tests whether the forest is empty. |
32a655c1 SL |
50 | pub fn is_empty(&self) -> bool { |
51 | self.root_ids.is_empty() | |
52 | } | |
53 | ||
9fa01778 | 54 | /// Tests whether the forest contains a given DefId. |
dc9dc135 | 55 | pub fn contains(&self, tcx: TyCtxt<'tcx>, id: DefId) -> bool { |
0bf4aa26 | 56 | self.root_ids.iter().any(|root_id| tcx.is_descendant_of(id, *root_id)) |
32a655c1 SL |
57 | } |
58 | ||
59 | /// Calculate the intersection of a collection of forests. | |
dc9dc135 XL |
60 | pub fn intersection<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest |
61 | where | |
62 | I: IntoIterator<Item = DefIdForest>, | |
32a655c1 | 63 | { |
0731742a XL |
64 | let mut iter = iter.into_iter(); |
65 | let mut ret = if let Some(first) = iter.next() { | |
66 | first | |
67 | } else { | |
68 | return DefIdForest::full(tcx); | |
69 | }; | |
70 | ||
32a655c1 SL |
71 | let mut next_ret = SmallVec::new(); |
72 | let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new(); | |
73 | for next_forest in iter { | |
0731742a XL |
74 | // No need to continue if the intersection is already empty. |
75 | if ret.is_empty() { | |
76 | break; | |
77 | } | |
78 | ||
60c5eb7d | 79 | for id in ret.root_ids.drain(..) { |
32a655c1 SL |
80 | if next_forest.contains(tcx, id) { |
81 | next_ret.push(id); | |
82 | } else { | |
83 | old_ret.push(id); | |
84 | } | |
85 | } | |
60c5eb7d | 86 | ret.root_ids.extend(old_ret.drain(..)); |
32a655c1 | 87 | |
0bf4aa26 | 88 | next_ret.extend(next_forest.root_ids.into_iter().filter(|&id| ret.contains(tcx, id))); |
32a655c1 SL |
89 | |
90 | mem::swap(&mut next_ret, &mut ret.root_ids); | |
60c5eb7d | 91 | next_ret.drain(..); |
32a655c1 SL |
92 | } |
93 | ret | |
94 | } | |
95 | ||
96 | /// Calculate the union of a collection of forests. | |
dc9dc135 XL |
97 | pub fn union<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest |
98 | where | |
99 | I: IntoIterator<Item = DefIdForest>, | |
32a655c1 SL |
100 | { |
101 | let mut ret = DefIdForest::empty(); | |
102 | let mut next_ret = SmallVec::new(); | |
103 | for next_forest in iter { | |
60c5eb7d | 104 | next_ret.extend(ret.root_ids.drain(..).filter(|&id| !next_forest.contains(tcx, id))); |
32a655c1 SL |
105 | |
106 | for id in next_forest.root_ids { | |
107 | if !next_ret.contains(&id) { | |
108 | next_ret.push(id); | |
109 | } | |
110 | } | |
111 | ||
112 | mem::swap(&mut next_ret, &mut ret.root_ids); | |
60c5eb7d | 113 | next_ret.drain(..); |
32a655c1 SL |
114 | } |
115 | ret | |
116 | } | |
117 | } |