src/librustc/ty/inhabitedness/def_id_forest.rs

   1 use std::mem;
   2 use smallvec::SmallVec;
   3 use rustc::hir::CRATE_HIR_ID;
   4 use crate::ty::context::TyCtxt;
   5 use crate::ty::{DefId, DefIdTree};
   6
   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
  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 `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.
  21     root_ids: SmallVec<[DefId; 1]>,
  22 }
  23
  24 impl<'tcx> DefIdForest {
  25     /// Creates an empty forest.
  26     pub fn empty() -> DefIdForest {
  27         DefIdForest {
  28             root_ids: SmallVec::new(),
  29         }
  30     }
  31
  32     /// Creates a forest consisting of a single tree representing the entire
  33     /// crate.
  34     #[inline]
  35     pub fn full(tcx: TyCtxt<'tcx>) -> DefIdForest {
  36         let crate_id = tcx.hir().local_def_id(CRATE_HIR_ID);
  37         DefIdForest::from_id(crate_id)
  38     }
  39
  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();
  43         root_ids.push(id);
  44         DefIdForest {
  45             root_ids,
  46         }
  47     }
  48
  49     /// Tests whether the forest is empty.
  50     pub fn is_empty(&self) -> bool {
  51         self.root_ids.is_empty()
  52     }
  53
  54     /// Tests whether the forest contains a given DefId.
  55     pub fn contains(&self, tcx: TyCtxt<'tcx>, id: DefId) -> bool {
  56         self.root_ids.iter().any(|root_id| tcx.is_descendant_of(id, *root_id))
  57     }
  58
  59     /// Calculate the intersection of a collection of forests.
  60     pub fn intersection<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest
  61     where
  62         I: IntoIterator<Item = DefIdForest>,
  63     {
  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
  71         let mut next_ret = SmallVec::new();
  72         let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new();
  73         for next_forest in iter {
  74             // No need to continue if the intersection is already empty.
  75             if ret.is_empty() {
  76                 break;
  77             }
  78
  79             for id in ret.root_ids.drain(..) {
  80                 if next_forest.contains(tcx, id) {
  81                     next_ret.push(id);
  82                 } else {
  83                     old_ret.push(id);
  84                 }
  85             }
  86             ret.root_ids.extend(old_ret.drain(..));
  87
  88             next_ret.extend(next_forest.root_ids.into_iter().filter(|&id| ret.contains(tcx, id)));
  89
  90             mem::swap(&mut next_ret, &mut ret.root_ids);
  91             next_ret.drain(..);
  92         }
  93         ret
  94     }
  95
  96     /// Calculate the union of a collection of forests.
  97     pub fn union<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest
  98     where
  99         I: IntoIterator<Item = DefIdForest>,
 100     {
 101         let mut ret = DefIdForest::empty();
 102         let mut next_ret = SmallVec::new();
 103         for next_forest in iter {
 104             next_ret.extend(ret.root_ids.drain(..).filter(|&id| !next_forest.contains(tcx, id)));
 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);
 113             next_ret.drain(..);
 114         }
 115         ret
 116     }
 117 }