diff options
| -rw-r--r-- | compiler/rustc_lint/src/builtin.rs | 46 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/query/mod.rs | 15 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs | 145 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/inhabitedness/inhabited_predicate.rs | 204 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/inhabitedness/mod.rs | 258 | ||||
| -rw-r--r-- | compiler/rustc_middle/src/ty/mod.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_build/src/build/matches/simplify.rs | 12 | ||||
| -rw-r--r-- | compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs | 10 |
8 files changed, 338 insertions, 354 deletions
diff --git a/compiler/rustc_lint/src/builtin.rs b/compiler/rustc_lint/src/builtin.rs index 886e25f2d78..9117db19073 100644 --- a/compiler/rustc_lint/src/builtin.rs +++ b/compiler/rustc_lint/src/builtin.rs @@ -2467,42 +2467,6 @@ impl<'tcx> LateLintPass<'tcx> for InvalidValue { None } - /// Determines whether the given type is inhabited. `None` means that we don't know. - fn ty_inhabited<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<bool> { - use rustc_type_ir::sty::TyKind::*; - if !cx.tcx.type_uninhabited_from(cx.param_env.and(ty)).is_empty() { - // This is definitely uninhabited from some module. - return Some(false); - } - match ty.kind() { - Never => Some(false), - Int(_) | Uint(_) | Float(_) | Bool | Char | RawPtr(_) => Some(true), - // Fallback for more complicated types. (Note that `&!` might be considered - // uninhabited so references are "complicated", too.) - _ => None, - } - } - /// Determines whether a product type formed from a list of types is inhabited. - fn tys_inhabited<'tcx>( - cx: &LateContext<'tcx>, - tys: impl Iterator<Item = Ty<'tcx>>, - ) -> Option<bool> { - let mut definitely_inhabited = true; // with no fields, we are definitely inhabited. - for ty in tys { - match ty_inhabited(cx, ty) { - // If any type is uninhabited, the product is uninhabited. - Some(false) => return Some(false), - // Otherwise go searching for a `None`. - None => { - // We don't know. - definitely_inhabited = false; - } - Some(true) => {} - } - } - if definitely_inhabited { Some(true) } else { None } - } - fn variant_find_init_error<'tcx>( cx: &LateContext<'tcx>, variant: &VariantDef, @@ -2599,11 +2563,11 @@ impl<'tcx> LateLintPass<'tcx> for InvalidValue { // And now, enums. let span = cx.tcx.def_span(adt_def.did()); let mut potential_variants = adt_def.variants().iter().filter_map(|variant| { - let inhabited = tys_inhabited( - cx, - variant.fields.iter().map(|field| field.ty(cx.tcx, substs)), - ); - let definitely_inhabited = match inhabited { + let definitely_inhabited = match variant + .inhabited_predicate(cx.tcx, *adt_def) + .subst(cx.tcx, substs) + .apply_any_module(cx.tcx, cx.param_env) + { // Entirely skip uninhbaited variants. Some(false) => return None, // Forward the others, but remember which ones are definitely inhabited. diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs index ea81d4465fb..6ef17d51036 100644 --- a/compiler/rustc_middle/src/query/mod.rs +++ b/compiler/rustc_middle/src/query/mod.rs @@ -1653,14 +1653,13 @@ rustc_queries! { separate_provide_extern } - /// Computes the set of modules from which this type is visibly uninhabited. - /// To check whether a type is uninhabited at all (not just from a given module), you could - /// check whether the forest is empty. - query type_uninhabited_from( - key: ty::ParamEnvAnd<'tcx, Ty<'tcx>> - ) -> ty::inhabitedness::DefIdForest<'tcx> { - desc { "computing the inhabitedness of `{}`", key.value } - remap_env_constness + query inhabited_predicate_adt(key: DefId) -> ty::inhabitedness::InhabitedPredicate<'tcx> { + desc { "computing the uninhabited predicate of `{:?}`", key } + } + + /// Do not call this query directly: invoke `Ty::inhabited_predicate` instead. + query inhabited_predicate_type(key: Ty<'tcx>) -> ty::inhabitedness::InhabitedPredicate<'tcx> { + desc { "computing the uninhabited predicate of `{}`", key } } query dep_kind(_: CrateNum) -> CrateDepKind { diff --git a/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs b/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs deleted file mode 100644 index c4ad698ba76..00000000000 --- a/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs +++ /dev/null @@ -1,145 +0,0 @@ -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<Item = DefId> + '_ { - 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<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest<'tcx> - where - I: IntoIterator<Item = DefIdForest<'tcx>>, - { - 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<I>(tcx: TyCtxt<'tcx>, iter: I) -> DefIdForest<'tcx> - where - I: IntoIterator<Item = DefIdForest<'tcx>>, - { - 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/inhabited_predicate.rs b/compiler/rustc_middle/src/ty/inhabitedness/inhabited_predicate.rs new file mode 100644 index 00000000000..b7aa455727d --- /dev/null +++ b/compiler/rustc_middle/src/ty/inhabitedness/inhabited_predicate.rs @@ -0,0 +1,204 @@ +use crate::ty::context::TyCtxt; +use crate::ty::{self, DefId, DefIdTree, ParamEnv, Ty}; + +/// Represents whether some type is inhabited in a given context. +/// Examples of uninhabited types are `!`, `enum Void {}`, or a struct +/// containing either of those types. +/// A type's inhabitedness may depend on the `ParamEnv` as well as what types +/// are visible in the current module. +#[derive(Clone, Copy, Debug, PartialEq, HashStable)] +pub enum InhabitedPredicate<'tcx> { + /// Inhabited + True, + /// Uninhabited + False, + /// Uninhabited when a const value is non-zero. This occurs when there is an + /// array of uninhabited items, but the array is inhabited if it is empty. + ConstIsZero(ty::Const<'tcx>), + /// Uninhabited if within a certain module. This occurs when an uninhabited + /// type has restricted visibility. + NotInModule(DefId), + /// Inhabited if some generic type is inhabited. + /// These are replaced by calling [`Self::subst`]. + GenericType(Ty<'tcx>), + /// A AND B + And(&'tcx [InhabitedPredicate<'tcx>; 2]), + /// A OR B + Or(&'tcx [InhabitedPredicate<'tcx>; 2]), +} + +impl<'tcx> InhabitedPredicate<'tcx> { + /// Returns true if the corresponding type is inhabited in the given + /// `ParamEnv` and module + pub fn apply(self, tcx: TyCtxt<'tcx>, param_env: ParamEnv<'tcx>, module_def_id: DefId) -> bool { + let Ok(result) = self + .apply_inner::<!>(tcx, param_env, &|id| Ok(tcx.is_descendant_of(module_def_id, id))); + result + } + + /// Same as `apply`, but returns `None` if self contains a module predicate + pub fn apply_any_module(self, tcx: TyCtxt<'tcx>, param_env: ParamEnv<'tcx>) -> Option<bool> { + self.apply_inner(tcx, param_env, &|_| Err(())).ok() + } + + fn apply_inner<E>( + self, + tcx: TyCtxt<'tcx>, + param_env: ParamEnv<'tcx>, + in_module: &impl Fn(DefId) -> Result<bool, E>, + ) -> Result<bool, E> { + match self { + Self::False => Ok(false), + Self::True => Ok(true), + Self::ConstIsZero(const_) => match const_.try_eval_usize(tcx, param_env) { + None | Some(0) => Ok(true), + Some(1..) => Ok(false), + }, + Self::NotInModule(id) => in_module(id).map(|in_mod| !in_mod), + Self::GenericType(_) => Ok(true), + Self::And([a, b]) => try_and(a, b, |x| x.apply_inner(tcx, param_env, in_module)), + Self::Or([a, b]) => try_or(a, b, |x| x.apply_inner(tcx, param_env, in_module)), + } + } + + pub fn and(self, tcx: TyCtxt<'tcx>, other: Self) -> Self { + self.reduce_and(tcx, other).unwrap_or_else(|| Self::And(tcx.arena.alloc([self, other]))) + } + + pub fn or(self, tcx: TyCtxt<'tcx>, other: Self) -> Self { + self.reduce_or(tcx, other).unwrap_or_else(|| Self::Or(tcx.arena.alloc([self, other]))) + } + + pub fn all(tcx: TyCtxt<'tcx>, iter: impl IntoIterator<Item = Self>) -> Self { + let mut result = Self::True; + for pred in iter { + if matches!(pred, Self::False) { + return Self::False; + } + result = result.and(tcx, pred); + } + result + } + + pub fn any(tcx: TyCtxt<'tcx>, iter: impl IntoIterator<Item = Self>) -> Self { + let mut result = Self::False; + for pred in iter { + if matches!(pred, Self::True) { + return Self::True; + } + result = result.or(tcx, pred); + } + result + } + + fn reduce_and(self, tcx: TyCtxt<'tcx>, other: Self) -> Option<Self> { + match (self, other) { + (Self::True, a) | (a, Self::True) => Some(a), + (Self::False, _) | (_, Self::False) => Some(Self::False), + (Self::ConstIsZero(a), Self::ConstIsZero(b)) if a == b => Some(Self::ConstIsZero(a)), + (Self::NotInModule(a), Self::NotInModule(b)) if a == b => Some(Self::NotInModule(a)), + (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(a, b) => { + Some(Self::NotInModule(b)) + } + (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(b, a) => { + Some(Self::NotInModule(a)) + } + (Self::GenericType(a), Self::GenericType(b)) if a == b => Some(Self::GenericType(a)), + (Self::And(&[a, b]), c) | (c, Self::And(&[a, b])) => { + if let Some(ac) = a.reduce_and(tcx, c) { + Some(ac.and(tcx, b)) + } else if let Some(bc) = b.reduce_and(tcx, c) { + Some(Self::And(tcx.arena.alloc([a, bc]))) + } else { + None + } + } + _ => None, + } + } + + fn reduce_or(self, tcx: TyCtxt<'tcx>, other: Self) -> Option<Self> { + match (self, other) { + (Self::True, _) | (_, Self::True) => Some(Self::True), + (Self::False, a) | (a, Self::False) => Some(a), + (Self::ConstIsZero(a), Self::ConstIsZero(b)) if a == b => Some(Self::ConstIsZero(a)), + (Self::NotInModule(a), Self::NotInModule(b)) if a == b => Some(Self::NotInModule(a)), + (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(a, b) => { + Some(Self::NotInModule(a)) + } + (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(b, a) => { + Some(Self::NotInModule(b)) + } + (Self::GenericType(a), Self::GenericType(b)) if a == b => Some(Self::GenericType(a)), + (Self::Or(&[a, b]), c) | (c, Self::Or(&[a, b])) => { + if let Some(ac) = a.reduce_or(tcx, c) { + Some(ac.or(tcx, b)) + } else if let Some(bc) = b.reduce_or(tcx, c) { + Some(Self::Or(tcx.arena.alloc([a, bc]))) + } else { + None + } + } + _ => None, + } + } + + /// Replaces generic types with its corresponding predicate + pub fn subst(self, tcx: TyCtxt<'tcx>, substs: ty::SubstsRef<'tcx>) -> Self { + self.subst_opt(tcx, substs).unwrap_or(self) + } + + fn subst_opt(self, tcx: TyCtxt<'tcx>, substs: ty::SubstsRef<'tcx>) -> Option<Self> { + match self { + Self::ConstIsZero(c) => { + let c = ty::EarlyBinder(c).subst(tcx, substs); + let pred = match c.kind().try_to_machine_usize(tcx) { + Some(0) => Self::True, + Some(1..) => Self::False, + None => Self::ConstIsZero(c), + }; + Some(pred) + } + Self::GenericType(t) => { + Some(ty::EarlyBinder(t).subst(tcx, substs).inhabited_predicate(tcx)) + } + Self::And(&[a, b]) => match a.subst_opt(tcx, substs) { + None => b.subst_opt(tcx, substs).map(|b| a.and(tcx, b)), + Some(InhabitedPredicate::False) => Some(InhabitedPredicate::False), + Some(a) => Some(a.and(tcx, b.subst_opt(tcx, substs).unwrap_or(b))), + }, + Self::Or(&[a, b]) => match a.subst_opt(tcx, substs) { + None => b.subst_opt(tcx, substs).map(|b| a.or(tcx, b)), + Some(InhabitedPredicate::True) => Some(InhabitedPredicate::True), + Some(a) => Some(a.or(tcx, b.subst_opt(tcx, substs).unwrap_or(b))), + }, + _ => None, + } + } +} + +// this is basically like `f(a)? && f(b)?` but different in the case of +// `Ok(false) && Err(_) -> Ok(false)` +fn try_and<T, E>(a: T, b: T, f: impl Fn(T) -> Result<bool, E>) -> Result<bool, E> { + let a = f(a); + if matches!(a, Ok(false)) { + return Ok(false); + } + match (a, f(b)) { + (_, Ok(false)) | (Ok(false), _) => Ok(false), + (Ok(true), Ok(true)) => Ok(true), + (Err(e), _) | (_, Err(e)) => Err(e), + } +} + +fn try_or<T, E>(a: T, b: T, f: impl Fn(T) -> Result<bool, E>) -> Result<bool, E> { + let a = f(a); + if matches!(a, Ok(true)) { + return Ok(true); + } + match (a, f(b)) { + (_, Ok(true)) | (Ok(true), _) => Ok(true), + (Ok(false), Ok(false)) => Ok(false), + (Err(e), _) | (_, Err(e)) => Err(e), + } +} diff --git a/compiler/rustc_middle/src/ty/inhabitedness/mod.rs b/compiler/rustc_middle/src/ty/inhabitedness/mod.rs index aaa66deb2a3..279a728ea39 100644 --- a/compiler/rustc_middle/src/ty/inhabitedness/mod.rs +++ b/compiler/rustc_middle/src/ty/inhabitedness/mod.rs @@ -1,57 +1,60 @@ -pub use self::def_id_forest::DefIdForest; +//! This module contains logic for determining whether a type is inhabited or +//! uninhabited. The [`InhabitedPredicate`] type captures the minimum +//! information needed to determine whether a type is inhabited given a +//! `ParamEnv` and module ID. +//! +//! # 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_predicate` on `Foo` will +//! return `NotInModule(b) AND NotInModule(c)`. +//! +//! We need this information for pattern-matching on `Foo` or types that contain +//! `Foo`. +//! +//! # Example +//! ```rust +//! let foo_result: Result<T, Foo> = ... ; +//! let Ok(t) = foo_result; +//! ``` +//! This code should only compile in modules where the uninhabitedness of `Foo` +//! is visible. -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 crate::ty::{self, DefId, Ty, VariantDef, Visibility}; use rustc_type_ir::sty::TyKind::*; -mod def_id_forest; +pub mod inhabited_predicate; -// 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<T, Foo> = ... ; -// let Ok(t) = foo_result; -// ``` -// This code should only compile in modules where the uninhabitedness of `Foo` is -// visible. +pub use inhabited_predicate::InhabitedPredicate; + +pub(crate) fn provide(providers: &mut ty::query::Providers) { + *providers = + ty::query::Providers { inhabited_predicate_adt, inhabited_predicate_type, ..*providers }; +} impl<'tcx> TyCtxt<'tcx> { /// Checks whether a type is visibly uninhabited from a particular module. @@ -100,131 +103,92 @@ impl<'tcx> TyCtxt<'tcx> { 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) + !ty.inhabited_predicate(self).apply(self, param_env, 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)), - ) +/// Returns an `InhabitedPredicate` that is generic over type parameters and +/// requires calling [`InhabitedPredicate::subst`] +fn inhabited_predicate_adt(tcx: TyCtxt<'_>, def_id: DefId) -> InhabitedPredicate<'_> { + if let Some(def_id) = def_id.as_local() { + if matches!(tcx.representability(def_id), ty::Representability::Infinite) { + return InhabitedPredicate::True; } } + let adt = tcx.adt_def(def_id); + InhabitedPredicate::any( + tcx, + adt.variants().iter().map(|variant| variant.inhabited_predicate(tcx, adt)), + ) } impl<'tcx> VariantDef { /// Calculates the forest of `DefId`s from which this variant is visibly uninhabited. - pub fn uninhabited_from( + pub fn inhabited_predicate( &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. + adt: ty::AdtDef<'_>, + ) -> InhabitedPredicate<'tcx> { + debug_assert!(!adt.is_union()); 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)), - ) + // Non-exhaustive variants from other crates are always considered inhabited. + return InhabitedPredicate::True; } - } -} - -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); - if is_enum { - data_uninhabitedness() - } else { - match self.vis { - Visibility::Restricted(from) => { - let forest = DefIdForest::from_id(from); - let iter = Some(forest).into_iter().chain(Some(data_uninhabitedness())); - DefIdForest::intersection(tcx, iter) + InhabitedPredicate::all( + tcx, + self.fields.iter().map(|field| { + let pred = tcx.type_of(field.did).inhabited_predicate(tcx); + if adt.is_enum() { + return pred; } - Visibility::Public => data_uninhabitedness(), - } - } + match field.vis { + Visibility::Public => pred, + Visibility::Restricted(from) => { + pred.or(tcx, InhabitedPredicate::NotInModule(from)) + } + } + }), + ) } } 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)) + pub fn inhabited_predicate(self, tcx: TyCtxt<'tcx>) -> InhabitedPredicate<'tcx> { + match self.kind() { + // For now, union`s are always considered inhabited + Adt(adt, _) if adt.is_union() => InhabitedPredicate::True, + // Non-exhaustive ADTs from other crates are always considered inhabited + Adt(adt, _) if adt.is_variant_list_non_exhaustive() && !adt.did().is_local() => { + InhabitedPredicate::True + } + Never => InhabitedPredicate::False, + Param(_) | Projection(_) => InhabitedPredicate::GenericType(self), + Tuple(tys) if tys.is_empty() => InhabitedPredicate::True, + // use a query for more complex cases + Adt(..) | Array(..) | Tuple(_) => tcx.inhabited_predicate_type(self), + // references and other types are inhabited + _ => InhabitedPredicate::True, + } } } -// 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; +/// N.B. this query should only be called through `Ty::inhabited_predicate` +fn inhabited_predicate_type<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> InhabitedPredicate<'tcx> { match *ty.kind() { - Adt(def, substs) => def.uninhabited_from(tcx, substs, param_env), + Adt(adt, substs) => tcx.inhabited_predicate_adt(adt.did()).subst(tcx, substs), - Never => DefIdForest::full(), - - Tuple(ref tys) => { - DefIdForest::union(tcx, tys.iter().map(|ty| ty.uninhabited_from(tcx, param_env))) + Tuple(tys) => { + InhabitedPredicate::all(tcx, tys.iter().map(|ty| ty.inhabited_predicate(tcx))) } - 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), + // If we can evaluate the array length before having a `ParamEnv`, then + // we can simplify the predicate. This is an optimization. + Array(ty, len) => match len.kind().try_to_machine_usize(tcx) { + Some(0) => InhabitedPredicate::True, + Some(1..) => ty.inhabited_predicate(tcx), + None => ty.inhabited_predicate(tcx).or(tcx, InhabitedPredicate::ConstIsZero(len)), }, - // 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(), + _ => bug!("unexpected TyKind, use `Ty::inhabited_predicate`"), } } diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs index a92bb0f2e55..c5407c57588 100644 --- a/compiler/rustc_middle/src/ty/mod.rs +++ b/compiler/rustc_middle/src/ty/mod.rs @@ -2694,6 +2694,7 @@ pub fn provide(providers: &mut ty::query::Providers) { closure::provide(providers); context::provide(providers); erase_regions::provide(providers); + inhabitedness::provide(providers); util::provide(providers); print::provide(providers); super::util::bug::provide(providers); @@ -2701,7 +2702,6 @@ pub fn provide(providers: &mut ty::query::Providers) { *providers = ty::query::Providers { trait_impls_of: trait_def::trait_impls_of_provider, incoherent_impls: trait_def::incoherent_impls_provider, - type_uninhabited_from: inhabitedness::type_uninhabited_from, const_param_default: consts::const_param_default, vtable_allocation: vtable::vtable_allocation_provider, ..*providers diff --git a/compiler/rustc_mir_build/src/build/matches/simplify.rs b/compiler/rustc_mir_build/src/build/matches/simplify.rs index 828f32db361..924d2f555b9 100644 --- a/compiler/rustc_mir_build/src/build/matches/simplify.rs +++ b/compiler/rustc_mir_build/src/build/matches/simplify.rs @@ -264,14 +264,10 @@ impl<'a, 'tcx> Builder<'a, 'tcx> { let irrefutable = adt_def.variants().iter_enumerated().all(|(i, v)| { i == variant_index || { self.tcx.features().exhaustive_patterns - && !v - .uninhabited_from( - self.tcx, - substs, - adt_def.adt_kind(), - self.param_env, - ) - .is_empty() + && v.inhabited_predicate(self.tcx, adt_def) + .subst(self.tcx, substs) + .apply_any_module(self.tcx, self.param_env) + != Some(true) } }) && (adt_def.did().is_local() || !adt_def.is_variant_list_non_exhaustive()); diff --git a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs index 91ecfccdb5f..595abc8f668 100644 --- a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs +++ b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs @@ -988,10 +988,12 @@ impl<'tcx> SplitWildcard<'tcx> { .filter(|(_, v)| { // If `exhaustive_patterns` is enabled, we exclude variants known to be // uninhabited. - let is_uninhabited = is_exhaustive_pat_feature - && v.uninhabited_from(cx.tcx, substs, def.adt_kind(), cx.param_env) - .contains(cx.tcx, cx.module); - !is_uninhabited + !is_exhaustive_pat_feature + || v.inhabited_predicate(cx.tcx, *def).subst(cx.tcx, substs).apply( + cx.tcx, + cx.param_env, + cx.module, + ) }) .map(|(idx, _)| Variant(idx)) .collect(); |