From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- .../src/ty/inhabitedness/def_id_forest.rs | 145 +++++++++++++ compiler/rustc_middle/src/ty/inhabitedness/mod.rs | 234 +++++++++++++++++++++ 2 files changed, 379 insertions(+) create mode 100644 compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs create mode 100644 compiler/rustc_middle/src/ty/inhabitedness/mod.rs (limited to 'compiler/rustc_middle/src/ty/inhabitedness') diff --git a/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs b/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs new file mode 100644 index 000000000..c4ad698ba --- /dev/null +++ b/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs @@ -0,0 +1,145 @@ +use crate::ty::context::TyCtxt; +use crate::ty::{DefId, DefIdTree}; +use rustc_span::def_id::CRATE_DEF_ID; +use smallvec::SmallVec; +use std::mem; + +use DefIdForest::*; + +/// 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. +/// +/// We store the minimal set of `DefId`s required to represent the whole set. If A and B are +/// `DefId`s in the `DefIdForest`, and A is a parent of B, then only A will be stored. When this is +/// used with `type_uninhabited_from`, there will very rarely be more than one `DefId` stored. +#[derive(Copy, Clone, HashStable, Debug)] +pub enum DefIdForest<'a> { + Empty, + Single(DefId), + /// This variant is very rare. + /// Invariant: >1 elements + Multiple(&'a [DefId]), +} + +/// Tests whether a slice of roots contains a given DefId. +#[inline] +fn slice_contains<'tcx>(tcx: TyCtxt<'tcx>, slice: &[DefId], id: DefId) -> bool { + slice.iter().any(|root_id| tcx.is_descendant_of(id, *root_id)) +} + +impl<'tcx> DefIdForest<'tcx> { + /// Creates an empty forest. + pub fn empty() -> DefIdForest<'tcx> { + DefIdForest::Empty + } + + /// Creates a forest consisting of a single tree representing the entire + /// crate. + #[inline] + pub fn full() -> DefIdForest<'tcx> { + DefIdForest::from_id(CRATE_DEF_ID.to_def_id()) + } + + /// Creates a forest containing a `DefId` and all its descendants. + pub fn from_id(id: DefId) -> DefIdForest<'tcx> { + DefIdForest::Single(id) + } + + fn as_slice(&self) -> &[DefId] { + match self { + Empty => &[], + Single(id) => std::slice::from_ref(id), + Multiple(root_ids) => root_ids, + } + } + + // Only allocates in the rare `Multiple` case. + fn from_vec(tcx: TyCtxt<'tcx>, root_ids: SmallVec<[DefId; 1]>) -> DefIdForest<'tcx> { + match &root_ids[..] { + [] => Empty, + [id] => Single(*id), + _ => DefIdForest::Multiple(tcx.arena.alloc_from_iter(root_ids)), + } + } + + /// Tests whether the forest is empty. + pub fn is_empty(&self) -> bool { + match self { + Empty => true, + Single(..) | Multiple(..) => false, + } + } + + /// Iterate over the set of roots. + fn iter(&self) -> impl Iterator + '_ { + self.as_slice().iter().copied() + } + + /// Tests whether the forest contains a given DefId. + pub fn contains(&self, tcx: TyCtxt<'tcx>, id: DefId) -> bool { + slice_contains(tcx, self.as_slice(), id) + } + + /// Calculate the intersection of a collection of forests. + pub fn intersection(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest<'tcx> + where + I: IntoIterator>, + { + let mut iter = iter.into_iter(); + let mut ret: SmallVec<[_; 1]> = if let Some(first) = iter.next() { + SmallVec::from_slice(first.as_slice()) + } else { + return DefIdForest::full(); + }; + + let mut next_ret: SmallVec<[_; 1]> = SmallVec::new(); + for next_forest in iter { + // No need to continue if the intersection is already empty. + if ret.is_empty() || next_forest.is_empty() { + return DefIdForest::empty(); + } + + // We keep the elements in `ret` that are also in `next_forest`. + next_ret.extend(ret.iter().copied().filter(|&id| next_forest.contains(tcx, id))); + // We keep the elements in `next_forest` that are also in `ret`. + next_ret.extend(next_forest.iter().filter(|&id| slice_contains(tcx, &ret, id))); + + mem::swap(&mut next_ret, &mut ret); + next_ret.clear(); + } + DefIdForest::from_vec(tcx, ret) + } + + /// Calculate the union of a collection of forests. + pub fn union(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest<'tcx> + where + I: IntoIterator>, + { + let mut ret: SmallVec<[_; 1]> = SmallVec::new(); + let mut next_ret: SmallVec<[_; 1]> = SmallVec::new(); + for next_forest in iter { + // Union with the empty set is a no-op. + if next_forest.is_empty() { + continue; + } + + // We add everything in `ret` that is not in `next_forest`. + next_ret.extend(ret.iter().copied().filter(|&id| !next_forest.contains(tcx, id))); + // We add everything in `next_forest` that we haven't added yet. + for id in next_forest.iter() { + if !slice_contains(tcx, &next_ret, id) { + next_ret.push(id); + } + } + + mem::swap(&mut next_ret, &mut ret); + next_ret.clear(); + } + DefIdForest::from_vec(tcx, ret) + } +} diff --git a/compiler/rustc_middle/src/ty/inhabitedness/mod.rs b/compiler/rustc_middle/src/ty/inhabitedness/mod.rs new file mode 100644 index 000000000..3d22f5a04 --- /dev/null +++ b/compiler/rustc_middle/src/ty/inhabitedness/mod.rs @@ -0,0 +1,234 @@ +pub use self::def_id_forest::DefIdForest; + +use crate::ty; +use crate::ty::context::TyCtxt; +use crate::ty::{AdtDef, FieldDef, Ty, VariantDef}; +use crate::ty::{AdtKind, Visibility}; +use crate::ty::{DefId, SubstsRef}; + +use rustc_type_ir::sty::TyKind::*; + +mod def_id_forest; + +// The methods in this module calculate `DefIdForest`s of modules in which an +// `AdtDef`/`VariantDef`/`FieldDef` is visibly uninhabited. +// +// # Example +// ```rust +// enum Void {} +// mod a { +// pub mod b { +// pub struct SecretlyUninhabited { +// _priv: !, +// } +// } +// } +// +// mod c { +// pub struct AlsoSecretlyUninhabited { +// _priv: Void, +// } +// mod d { +// } +// } +// +// struct Foo { +// x: a::b::SecretlyUninhabited, +// y: c::AlsoSecretlyUninhabited, +// } +// ``` +// In this code, the type `Foo` will only be visibly uninhabited inside the +// modules `b`, `c` and `d`. Calling `uninhabited_from` on `Foo` or its `AdtDef` will +// return the forest of modules {`b`, `c`->`d`} (represented in a `DefIdForest` by the +// set {`b`, `c`}). +// +// We need this information for pattern-matching on `Foo` or types that contain +// `Foo`. +// +// # Example +// ```rust +// let foo_result: Result = ... ; +// let Ok(t) = foo_result; +// ``` +// This code should only compile in modules where the uninhabitedness of `Foo` is +// visible. + +impl<'tcx> TyCtxt<'tcx> { + /// Checks whether a type is visibly uninhabited from a particular module. + /// + /// # Example + /// ``` + /// #![feature(never_type)] + /// # fn main() {} + /// enum Void {} + /// mod a { + /// pub mod b { + /// pub struct SecretlyUninhabited { + /// _priv: !, + /// } + /// } + /// } + /// + /// mod c { + /// use super::Void; + /// pub struct AlsoSecretlyUninhabited { + /// _priv: Void, + /// } + /// mod d { + /// } + /// } + /// + /// struct Foo { + /// x: a::b::SecretlyUninhabited, + /// y: c::AlsoSecretlyUninhabited, + /// } + /// ``` + /// In this code, the type `Foo` will only be visibly uninhabited inside the + /// modules b, c and d. This effects pattern-matching on `Foo` or types that + /// contain `Foo`. + /// + /// # Example + /// ```ignore (illustrative) + /// let foo_result: Result = ... ; + /// let Ok(t) = foo_result; + /// ``` + /// This code should only compile in modules where the uninhabitedness of Foo is + /// visible. + pub fn is_ty_uninhabited_from( + self, + module: DefId, + ty: Ty<'tcx>, + param_env: ty::ParamEnv<'tcx>, + ) -> bool { + // To check whether this type is uninhabited at all (not just from the + // given node), you could check whether the forest is empty. + // ``` + // forest.is_empty() + // ``` + ty.uninhabited_from(self, param_env).contains(self, module) + } +} + +impl<'tcx> AdtDef<'tcx> { + /// Calculates the forest of `DefId`s from which this ADT is visibly uninhabited. + fn uninhabited_from( + self, + tcx: TyCtxt<'tcx>, + substs: SubstsRef<'tcx>, + param_env: ty::ParamEnv<'tcx>, + ) -> DefIdForest<'tcx> { + // Non-exhaustive ADTs from other crates are always considered inhabited. + if self.is_variant_list_non_exhaustive() && !self.did().is_local() { + DefIdForest::empty() + } else { + DefIdForest::intersection( + tcx, + self.variants() + .iter() + .map(|v| v.uninhabited_from(tcx, substs, self.adt_kind(), param_env)), + ) + } + } +} + +impl<'tcx> VariantDef { + /// Calculates the forest of `DefId`s from which this variant is visibly uninhabited. + pub fn uninhabited_from( + &self, + tcx: TyCtxt<'tcx>, + substs: SubstsRef<'tcx>, + adt_kind: AdtKind, + param_env: ty::ParamEnv<'tcx>, + ) -> DefIdForest<'tcx> { + let is_enum = match adt_kind { + // For now, `union`s are never considered uninhabited. + // The precise semantics of inhabitedness with respect to unions is currently undecided. + AdtKind::Union => return DefIdForest::empty(), + AdtKind::Enum => true, + AdtKind::Struct => false, + }; + // Non-exhaustive variants from other crates are always considered inhabited. + if self.is_field_list_non_exhaustive() && !self.def_id.is_local() { + DefIdForest::empty() + } else { + DefIdForest::union( + tcx, + self.fields.iter().map(|f| f.uninhabited_from(tcx, substs, is_enum, param_env)), + ) + } + } +} + +impl<'tcx> FieldDef { + /// Calculates the forest of `DefId`s from which this field is visibly uninhabited. + fn uninhabited_from( + &self, + tcx: TyCtxt<'tcx>, + substs: SubstsRef<'tcx>, + is_enum: bool, + param_env: ty::ParamEnv<'tcx>, + ) -> DefIdForest<'tcx> { + let data_uninhabitedness = move || self.ty(tcx, substs).uninhabited_from(tcx, param_env); + // FIXME(canndrew): Currently enum fields are (incorrectly) stored with + // `Visibility::Invisible` so we need to override `self.vis` if we're + // dealing with an enum. + if is_enum { + data_uninhabitedness() + } else { + match self.vis { + Visibility::Invisible => DefIdForest::empty(), + Visibility::Restricted(from) => { + let forest = DefIdForest::from_id(from); + let iter = Some(forest).into_iter().chain(Some(data_uninhabitedness())); + DefIdForest::intersection(tcx, iter) + } + Visibility::Public => data_uninhabitedness(), + } + } + } +} + +impl<'tcx> Ty<'tcx> { + /// Calculates the forest of `DefId`s from which this type is visibly uninhabited. + fn uninhabited_from( + self, + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + ) -> DefIdForest<'tcx> { + tcx.type_uninhabited_from(param_env.and(self)) + } +} + +// Query provider for `type_uninhabited_from`. +pub(crate) fn type_uninhabited_from<'tcx>( + tcx: TyCtxt<'tcx>, + key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>, +) -> DefIdForest<'tcx> { + let ty = key.value; + let param_env = key.param_env; + match *ty.kind() { + Adt(def, substs) => def.uninhabited_from(tcx, substs, param_env), + + Never => DefIdForest::full(), + + Tuple(ref tys) => { + DefIdForest::union(tcx, tys.iter().map(|ty| ty.uninhabited_from(tcx, param_env))) + } + + Array(ty, len) => match len.try_eval_usize(tcx, param_env) { + Some(0) | None => DefIdForest::empty(), + // If the array is definitely non-empty, it's uninhabited if + // the type of its elements is uninhabited. + Some(1..) => ty.uninhabited_from(tcx, param_env), + }, + + // References to uninitialised memory are valid for any type, including + // uninhabited types, in unsafe code, so we treat all references as + // inhabited. + // The precise semantics of inhabitedness with respect to references is currently + // undecided. + Ref(..) => DefIdForest::empty(), + + _ => DefIdForest::empty(), + } +} -- cgit v1.2.3