Merging upstream version 1.66.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 315 insertions, 292 deletions

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 c4ad698ba..000000000
--- 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 000000000..b7aa45572
--- /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 aaa66deb2..279a728ea 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`"),
     }
 }