src/librustc/ty/inhabitedness/def_id_forest.rs

   1 use std::mem;
   2 use smallvec::SmallVec;
   3 use syntax::ast::CRATE_NODE_ID;
   4 use ty::context::TyCtxt;
   5 use ty::{DefId, DefIdTree};
   6
   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
  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 {
  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]>,
  22 }
  23
  24 impl<'a, 'gcx, 'tcx> DefIdForest {
  25     /// Create an empty forest.
  26     pub fn empty() -> DefIdForest {
  27         DefIdForest {
  28             root_ids: SmallVec::new(),
  29         }
  30     }
  31
  32     /// Create a forest consisting of a single tree representing the entire
  33     /// crate.
  34     #[inline]
  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)
  38     }
  39
  40     /// Create a forest containing a DefId and all its descendants.
  41     pub fn from_id(id: DefId) -> DefIdForest {
  42         let mut root_ids = SmallVec::new();
  43         root_ids.push(id);
  44         DefIdForest {
  45             root_ids,
  46         }
  47     }
  48
  49     /// Test whether the forest is empty.
  50     pub fn is_empty(&self) -> bool {
  51         self.root_ids.is_empty()
  52     }
  53
  54     /// Test whether the forest contains a given DefId.
  55     pub fn contains(&self,
  56                     tcx: TyCtxt<'a, 'gcx, 'tcx>,
  57                     id: DefId) -> bool
  58     {
  59         self.root_ids.iter().any(|root_id| tcx.is_descendant_of(id, *root_id))
  60     }
  61
  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>
  66     {
  67         let mut iter = iter.into_iter();
  68         let mut ret = if let Some(first) = iter.next() {
  69             first
  70         } else {
  71             return DefIdForest::full(tcx);
  72         };
  73
  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.
  78             if ret.is_empty() {
  79                 break;
  80             }
  81
  82             for id in ret.root_ids.drain() {
  83                 if next_forest.contains(tcx, id) {
  84                     next_ret.push(id);
  85                 } else {
  86                     old_ret.push(id);
  87                 }
  88             }
  89             ret.root_ids.extend(old_ret.drain());
  90
  91             next_ret.extend(next_forest.root_ids.into_iter().filter(|&id| ret.contains(tcx, id)));
  92
  93             mem::swap(&mut next_ret, &mut ret.root_ids);
  94             next_ret.drain();
  95         }
  96         ret
  97     }
  98
  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>
 103     {
 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)));
 108
 109             for id in next_forest.root_ids {
 110                 if !next_ret.contains(&id) {
 111                     next_ret.push(id);
 112                 }
 113             }
 114
 115             mem::swap(&mut next_ret, &mut ret.root_ids);
 116             next_ret.drain();
 117         }
 118         ret
 119     }
 120 }
 121