]>
Commit | Line | Data |
---|---|---|
9fa01778 XL |
1 | use crate::ty::context::TyCtxt; |
2 | use crate::ty::{DefId, DefIdTree}; | |
dfeec247 XL |
3 | use rustc_hir::CRATE_HIR_ID; |
4 | use smallvec::SmallVec; | |
5 | use std::mem; | |
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) | |
fc512014 | 20 | /// it's 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 | 26 | pub fn empty() -> DefIdForest { |
dfeec247 | 27 | DefIdForest { root_ids: SmallVec::new() } |
32a655c1 SL |
28 | } |
29 | ||
9fa01778 | 30 | /// Creates a forest consisting of a single tree representing the entire |
32a655c1 SL |
31 | /// crate. |
32 | #[inline] | |
dc9dc135 | 33 | pub fn full(tcx: TyCtxt<'tcx>) -> DefIdForest { |
416331ca | 34 | let crate_id = tcx.hir().local_def_id(CRATE_HIR_ID); |
f9f354fc | 35 | DefIdForest::from_id(crate_id.to_def_id()) |
32a655c1 SL |
36 | } |
37 | ||
e1599b0c | 38 | /// Creates a forest containing a `DefId` and all its descendants. |
32a655c1 SL |
39 | pub fn from_id(id: DefId) -> DefIdForest { |
40 | let mut root_ids = SmallVec::new(); | |
41 | root_ids.push(id); | |
dfeec247 | 42 | DefIdForest { root_ids } |
32a655c1 SL |
43 | } |
44 | ||
9fa01778 | 45 | /// Tests whether the forest is empty. |
32a655c1 SL |
46 | pub fn is_empty(&self) -> bool { |
47 | self.root_ids.is_empty() | |
48 | } | |
49 | ||
9fa01778 | 50 | /// Tests whether the forest contains a given DefId. |
dc9dc135 | 51 | pub fn contains(&self, tcx: TyCtxt<'tcx>, id: DefId) -> bool { |
0bf4aa26 | 52 | self.root_ids.iter().any(|root_id| tcx.is_descendant_of(id, *root_id)) |
32a655c1 SL |
53 | } |
54 | ||
55 | /// Calculate the intersection of a collection of forests. | |
dc9dc135 XL |
56 | pub fn intersection<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest |
57 | where | |
58 | I: IntoIterator<Item = DefIdForest>, | |
32a655c1 | 59 | { |
0731742a XL |
60 | let mut iter = iter.into_iter(); |
61 | let mut ret = if let Some(first) = iter.next() { | |
62 | first | |
63 | } else { | |
64 | return DefIdForest::full(tcx); | |
65 | }; | |
66 | ||
32a655c1 SL |
67 | let mut next_ret = SmallVec::new(); |
68 | let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new(); | |
69 | for next_forest in iter { | |
0731742a XL |
70 | // No need to continue if the intersection is already empty. |
71 | if ret.is_empty() { | |
72 | break; | |
73 | } | |
74 | ||
60c5eb7d | 75 | for id in ret.root_ids.drain(..) { |
32a655c1 SL |
76 | if next_forest.contains(tcx, id) { |
77 | next_ret.push(id); | |
78 | } else { | |
79 | old_ret.push(id); | |
80 | } | |
81 | } | |
60c5eb7d | 82 | ret.root_ids.extend(old_ret.drain(..)); |
32a655c1 | 83 | |
0bf4aa26 | 84 | next_ret.extend(next_forest.root_ids.into_iter().filter(|&id| ret.contains(tcx, id))); |
32a655c1 SL |
85 | |
86 | mem::swap(&mut next_ret, &mut ret.root_ids); | |
60c5eb7d | 87 | next_ret.drain(..); |
32a655c1 SL |
88 | } |
89 | ret | |
90 | } | |
91 | ||
92 | /// Calculate the union of a collection of forests. | |
dc9dc135 XL |
93 | pub fn union<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest |
94 | where | |
95 | I: IntoIterator<Item = DefIdForest>, | |
32a655c1 SL |
96 | { |
97 | let mut ret = DefIdForest::empty(); | |
98 | let mut next_ret = SmallVec::new(); | |
99 | for next_forest in iter { | |
60c5eb7d | 100 | next_ret.extend(ret.root_ids.drain(..).filter(|&id| !next_forest.contains(tcx, id))); |
32a655c1 SL |
101 | |
102 | for id in next_forest.root_ids { | |
103 | if !next_ret.contains(&id) { | |
104 | next_ret.push(id); | |
105 | } | |
106 | } | |
107 | ||
108 | mem::swap(&mut next_ret, &mut ret.root_ids); | |
60c5eb7d | 109 | next_ret.drain(..); |
32a655c1 SL |
110 | } |
111 | ret | |
112 | } | |
113 | } |