| use std::mem; |
| use smallvec::SmallVec; |
| use rustc::hir::CRATE_HIR_ID; |
| use crate::ty::context::TyCtxt; |
| use crate::ty::{DefId, DefIdTree}; |
| |
| /// Represents a forest of `DefId`s closed under the ancestor relation. That is, |
| /// if a `DefId` representing a module is contained in the forest then all |
| /// `DefId`s defined in that module or submodules are also implicitly contained |
| /// in the forest. |
| /// |
| /// This is used to represent a set of modules in which a type is visibly |
| /// uninhabited. |
| #[derive(Clone)] |
| pub struct DefIdForest { |
| /// The minimal set of `DefId`s required to represent the whole set. |
| /// If A and B are DefIds in the `DefIdForest`, and A is a descendant |
| /// of B, then only B will be in `root_ids`. |
| /// We use a `SmallVec` here because (for its use for caching inhabitedness) |
| /// its rare that this will contain even two IDs. |
| root_ids: SmallVec<[DefId; 1]>, |
| } |
| |
| impl<'tcx> DefIdForest { |
| /// Creates an empty forest. |
| pub fn empty() -> DefIdForest { |
| DefIdForest { |
| root_ids: SmallVec::new(), |
| } |
| } |
| |
| /// Creates a forest consisting of a single tree representing the entire |
| /// crate. |
| #[inline] |
| pub fn full(tcx: TyCtxt<'tcx>) -> DefIdForest { |
| let crate_id = tcx.hir().local_def_id(CRATE_HIR_ID); |
| DefIdForest::from_id(crate_id) |
| } |
| |
| /// Creates a forest containing a `DefId` and all its descendants. |
| pub fn from_id(id: DefId) -> DefIdForest { |
| let mut root_ids = SmallVec::new(); |
| root_ids.push(id); |
| DefIdForest { |
| root_ids, |
| } |
| } |
| |
| /// Tests whether the forest is empty. |
| pub fn is_empty(&self) -> bool { |
| self.root_ids.is_empty() |
| } |
| |
| /// Tests whether the forest contains a given DefId. |
| pub fn contains(&self, tcx: TyCtxt<'tcx>, id: DefId) -> bool { |
| self.root_ids.iter().any(|root_id| tcx.is_descendant_of(id, *root_id)) |
| } |
| |
| /// Calculate the intersection of a collection of forests. |
| pub fn intersection<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest |
| where |
| I: IntoIterator<Item = DefIdForest>, |
| { |
| let mut iter = iter.into_iter(); |
| let mut ret = if let Some(first) = iter.next() { |
| first |
| } else { |
| return DefIdForest::full(tcx); |
| }; |
| |
| let mut next_ret = SmallVec::new(); |
| let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new(); |
| for next_forest in iter { |
| // No need to continue if the intersection is already empty. |
| if ret.is_empty() { |
| break; |
| } |
| |
| for id in ret.root_ids.drain() { |
| if next_forest.contains(tcx, id) { |
| next_ret.push(id); |
| } else { |
| old_ret.push(id); |
| } |
| } |
| ret.root_ids.extend(old_ret.drain()); |
| |
| next_ret.extend(next_forest.root_ids.into_iter().filter(|&id| ret.contains(tcx, id))); |
| |
| mem::swap(&mut next_ret, &mut ret.root_ids); |
| next_ret.drain(); |
| } |
| ret |
| } |
| |
| /// Calculate the union of a collection of forests. |
| pub fn union<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest |
| where |
| I: IntoIterator<Item = DefIdForest>, |
| { |
| let mut ret = DefIdForest::empty(); |
| let mut next_ret = SmallVec::new(); |
| for next_forest in iter { |
| next_ret.extend(ret.root_ids.drain().filter(|&id| !next_forest.contains(tcx, id))); |
| |
| for id in next_forest.root_ids { |
| if !next_ret.contains(&id) { |
| next_ret.push(id); |
| } |
| } |
| |
| mem::swap(&mut next_ret, &mut ret.root_ids); |
| next_ret.drain(); |
| } |
| ret |
| } |
| } |