]> git.proxmox.com Git - rustc.git/blame - src/librustc/ty/inhabitedness/def_id_forest.rs
New upstream version 1.41.1+dfsg1
[rustc.git] / src / librustc / ty / inhabitedness / def_id_forest.rs
CommitLineData
32a655c1 1use std::mem;
b7449926 2use smallvec::SmallVec;
dc9dc135 3use rustc::hir::CRATE_HIR_ID;
9fa01778
XL
4use crate::ty::context::TyCtxt;
5use 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)]
15pub 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 24impl<'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}