2 use smallvec::SmallVec;
3 use syntax::ast::CRATE_NODE_ID;
4 use crate::ty::context::TyCtxt;
5 use crate::ty::{DefId, DefIdTree};
7 /// Represents a forest of DefIds closed under the ancestor relation. That is,
8 /// if a DefId representing a module is contained in the forest then all
9 /// DefIds defined in that module or submodules are also implicitly contained
12 /// This is used to represent a set of modules in which a type is visibly
15 pub struct DefIdForest {
16 /// The minimal set of DefIds 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.
21 root_ids: SmallVec<[DefId; 1]>,
24 impl<'a, 'gcx, 'tcx> DefIdForest {
25 /// Creates an empty forest.
26 pub fn empty() -> DefIdForest {
28 root_ids: SmallVec::new(),
32 /// Creates a forest consisting of a single tree representing the entire
35 pub fn full(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest {
36 let crate_id = tcx.hir().local_def_id(CRATE_NODE_ID);
37 DefIdForest::from_id(crate_id)
40 /// Creates a forest containing a DefId and all its descendants.
41 pub fn from_id(id: DefId) -> DefIdForest {
42 let mut root_ids = SmallVec::new();
49 /// Tests whether the forest is empty.
50 pub fn is_empty(&self) -> bool {
51 self.root_ids.is_empty()
54 /// Tests whether the forest contains a given DefId.
55 pub fn contains(&self,
56 tcx: TyCtxt<'a, 'gcx, 'tcx>,
59 self.root_ids.iter().any(|root_id| tcx.is_descendant_of(id, *root_id))
62 /// Calculate the intersection of a collection of forests.
63 pub fn intersection<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
64 iter: I) -> DefIdForest
65 where I: IntoIterator<Item=DefIdForest>
67 let mut iter = iter.into_iter();
68 let mut ret = if let Some(first) = iter.next() {
71 return DefIdForest::full(tcx);
74 let mut next_ret = SmallVec::new();
75 let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new();
76 for next_forest in iter {
77 // No need to continue if the intersection is already empty.
82 for id in ret.root_ids.drain() {
83 if next_forest.contains(tcx, id) {
89 ret.root_ids.extend(old_ret.drain());
91 next_ret.extend(next_forest.root_ids.into_iter().filter(|&id| ret.contains(tcx, id)));
93 mem::swap(&mut next_ret, &mut ret.root_ids);
99 /// Calculate the union of a collection of forests.
100 pub fn union<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
101 iter: I) -> DefIdForest
102 where I: IntoIterator<Item=DefIdForest>
104 let mut ret = DefIdForest::empty();
105 let mut next_ret = SmallVec::new();
106 for next_forest in iter {
107 next_ret.extend(ret.root_ids.drain().filter(|&id| !next_forest.contains(tcx, id)));
109 for id in next_forest.root_ids {
110 if !next_ret.contains(&id) {
115 mem::swap(&mut next_ret, &mut ret.root_ids);