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_span::def_id::CRATE_DEF_ID;
   4 use smallvec::SmallVec;
   5 use std::mem;
   6
   7 use DefIdForest::*;
   8
   9 /// Represents a forest of `DefId`s closed under the ancestor relation. That is,
  10 /// if a `DefId` representing a module is contained in the forest then all
  11 /// `DefId`s defined in that module or submodules are also implicitly contained
  12 /// in the forest.
  13 ///
  14 /// This is used to represent a set of modules in which a type is visibly
  15 /// uninhabited.
  16 ///
  17 /// We store the minimal set of `DefId`s required to represent the whole set. If A and B are
  18 /// `DefId`s in the `DefIdForest`, and A is a parent of B, then only A will be stored. When this is
  19 /// used with `type_uninhabited_from`, there will very rarely be more than one `DefId` stored.
  20 #[derive(Copy, Clone, HashStable, Debug)]
  21 pub enum DefIdForest<'a> {
  22     Empty,
  23     Single(DefId),
  24     /// This variant is very rare.
  25     /// Invariant: >1 elements
  26     Multiple(&'a [DefId]),
  27 }
  28
  29 /// Tests whether a slice of roots contains a given DefId.
  30 #[inline]
  31 fn slice_contains<'tcx>(tcx: TyCtxt<'tcx>, slice: &[DefId], id: DefId) -> bool {
  32     slice.iter().any(|root_id| tcx.is_descendant_of(id, *root_id))
  33 }
  34
  35 impl<'tcx> DefIdForest<'tcx> {
  36     /// Creates an empty forest.
  37     pub fn empty() -> DefIdForest<'tcx> {
  38         DefIdForest::Empty
  39     }
  40
  41     /// Creates a forest consisting of a single tree representing the entire
  42     /// crate.
  43     #[inline]
  44     pub fn full() -> DefIdForest<'tcx> {
  45         DefIdForest::from_id(CRATE_DEF_ID.to_def_id())
  46     }
  47
  48     /// Creates a forest containing a `DefId` and all its descendants.
  49     pub fn from_id(id: DefId) -> DefIdForest<'tcx> {
  50         DefIdForest::Single(id)
  51     }
  52
  53     fn as_slice(&self) -> &[DefId] {
  54         match self {
  55             Empty => &[],
  56             Single(id) => std::slice::from_ref(id),
  57             Multiple(root_ids) => root_ids,
  58         }
  59     }
  60
  61     // Only allocates in the rare `Multiple` case.
  62     fn from_vec(tcx: TyCtxt<'tcx>, root_ids: SmallVec<[DefId; 1]>) -> DefIdForest<'tcx> {
  63         match &root_ids[..] {
  64             [] => Empty,
  65             [id] => Single(*id),
  66             _ => DefIdForest::Multiple(tcx.arena.alloc_from_iter(root_ids)),
  67         }
  68     }
  69
  70     /// Tests whether the forest is empty.
  71     pub fn is_empty(&self) -> bool {
  72         match self {
  73             Empty => true,
  74             Single(..) | Multiple(..) => false,
  75         }
  76     }
  77
  78     /// Iterate over the set of roots.
  79     fn iter(&self) -> impl Iterator<Item = DefId> + '_ {
  80         self.as_slice().iter().copied()
  81     }
  82
  83     /// Tests whether the forest contains a given DefId.
  84     pub fn contains(&self, tcx: TyCtxt<'tcx>, id: DefId) -> bool {
  85         slice_contains(tcx, self.as_slice(), id)
  86     }
  87
  88     /// Calculate the intersection of a collection of forests.
  89     pub fn intersection<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest<'tcx>
  90     where
  91         I: IntoIterator<Item = DefIdForest<'tcx>>,
  92     {
  93         let mut iter = iter.into_iter();
  94         let mut ret: SmallVec<[_; 1]> = if let Some(first) = iter.next() {
  95             SmallVec::from_slice(first.as_slice())
  96         } else {
  97             return DefIdForest::full();
  98         };
  99
 100         let mut next_ret: SmallVec<[_; 1]> = SmallVec::new();
 101         for next_forest in iter {
 102             // No need to continue if the intersection is already empty.
 103             if ret.is_empty() || next_forest.is_empty() {
 104                 return DefIdForest::empty();
 105             }
 106
 107             // We keep the elements in `ret` that are also in `next_forest`.
 108             next_ret.extend(ret.iter().copied().filter(|&id| next_forest.contains(tcx, id)));
 109             // We keep the elements in `next_forest` that are also in `ret`.
 110             next_ret.extend(next_forest.iter().filter(|&id| slice_contains(tcx, &ret, id)));
 111
 112             mem::swap(&mut next_ret, &mut ret);
 113             next_ret.clear();
 114         }
 115         DefIdForest::from_vec(tcx, ret)
 116     }
 117
 118     /// Calculate the union of a collection of forests.
 119     pub fn union<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest<'tcx>
 120     where
 121         I: IntoIterator<Item = DefIdForest<'tcx>>,
 122     {
 123         let mut ret: SmallVec<[_; 1]> = SmallVec::new();
 124         let mut next_ret: SmallVec<[_; 1]> = SmallVec::new();
 125         for next_forest in iter {
 126             // Union with the empty set is a no-op.
 127             if next_forest.is_empty() {
 128                 continue;
 129             }
 130
 131             // We add everything in `ret` that is not in `next_forest`.
 132             next_ret.extend(ret.iter().copied().filter(|&id| !next_forest.contains(tcx, id)));
 133             // We add everything in `next_forest` that we haven't added yet.
 134             for id in next_forest.iter() {
 135                 if !slice_contains(tcx, &next_ret, id) {
 136                     next_ret.push(id);
 137                 }
 138             }
 139
 140             mem::swap(&mut next_ret, &mut ret);
 141             next_ret.clear();
 142         }
 143         DefIdForest::from_vec(tcx, ret)
 144     }
 145 }