compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs

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