Turn type inhabitedness into a query

4 files changed, 60 insertions, 27 deletions

diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index 1e836d0a842..418ae2ddfc7 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -1308,6 +1308,15 @@ rustc_queries! {
             eval_always
             desc { |tcx| "computing visibility of `{}`", tcx.def_path_str(def_id) }
         }
+
+        /// 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>>
+        ) -> Arc<ty::inhabitedness::DefIdForest> {
+            desc { "computing the inhabitedness of `{:?}`", key }
+        }
     }
 
     Other {
diff --git a/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs b/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs
index d9aebfc8293..50fcd51b78c 100644
--- a/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs
+++ b/compiler/rustc_middle/src/ty/inhabitedness/def_id_forest.rs
@@ -11,7 +11,7 @@ use std::mem;
 ///
 /// This is used to represent a set of modules in which a type is visibly
 /// uninhabited.
-#[derive(Clone)]
+#[derive(Clone, HashStable)]
 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
@@ -72,6 +72,9 @@ impl<'tcx> DefIdForest {
                 break;
             }
 
+            // `next_ret` and `old_ret` are empty here.
+            // We keep the elements in `ret` that are also in `next_forest`. Those that aren't are
+            // put back in `ret` via `old_ret`.
             for id in ret.root_ids.drain(..) {
                 if next_forest.contains(tcx, id) {
                     next_ret.push(id);
@@ -81,7 +84,13 @@ impl<'tcx> DefIdForest {
             }
             ret.root_ids.extend(old_ret.drain(..));
 
+            // We keep the elements in `next_forest` that are also in `ret`.
+            // You'd think this is not needed because `next_ret` already contains `ret \inter
+            // next_forest`. But those aren't just sets of things. If `ret = [a]`, `next_forest =
+            // [b]` and `b` is a submodule of `a`, then `b` belongs in the intersection but we
+            // didn't catch it in the loop above.
             next_ret.extend(next_forest.root_ids.into_iter().filter(|&id| ret.contains(tcx, id)));
+            // `next_ret` now contains the intersection of the original `ret` and `next_forest`.
 
             mem::swap(&mut next_ret, &mut ret.root_ids);
             next_ret.drain(..);
diff --git a/compiler/rustc_middle/src/ty/inhabitedness/mod.rs b/compiler/rustc_middle/src/ty/inhabitedness/mod.rs
index 2f7707b9498..9dc309e2ab5 100644
--- a/compiler/rustc_middle/src/ty/inhabitedness/mod.rs
+++ b/compiler/rustc_middle/src/ty/inhabitedness/mod.rs
@@ -6,7 +6,8 @@ use crate::ty::TyKind::*;
 use crate::ty::{AdtDef, FieldDef, Ty, TyS, VariantDef};
 use crate::ty::{AdtKind, Visibility};
 use crate::ty::{DefId, SubstsRef};
-use rustc_data_structures::stack::ensure_sufficient_stack;
+
+use std::sync::Arc;
 
 mod def_id_forest;
 
@@ -187,34 +188,47 @@ impl<'tcx> FieldDef {
 
 impl<'tcx> TyS<'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 {
-        match *self.kind() {
-            Adt(def, substs) => {
-                ensure_sufficient_stack(|| def.uninhabited_from(tcx, substs, param_env))
-            }
+    fn uninhabited_from(
+        &'tcx self,
+        tcx: TyCtxt<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+    ) -> DefIdForest {
+        tcx.type_uninhabited_from(param_env.and(self)).as_ref().clone()
+    }
+}
 
-            Never => DefIdForest::full(tcx),
+// Query provider for `type_uninhabited_from`.
+pub(crate) fn type_uninhabited_from<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    key: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
+) -> Arc<DefIdForest> {
+    let ty = key.value;
+    let param_env = key.param_env;
+    let forest = match *ty.kind() {
+        Adt(def, substs) => def.uninhabited_from(tcx, substs, param_env),
 
-            Tuple(ref tys) => DefIdForest::union(
-                tcx,
-                tys.iter().map(|ty| ty.expect_ty().uninhabited_from(tcx, param_env)),
-            ),
+        Never => DefIdForest::full(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),
-            },
+        Tuple(ref tys) => DefIdForest::union(
+            tcx,
+            tys.iter().map(|ty| ty.expect_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(),
+        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),
+        },
 
-            _ => DefIdForest::empty(),
-        }
-    }
+        // 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(),
+    };
+    Arc::new(forest)
 }
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index 94186d490c3..b2448571b31 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -3146,6 +3146,7 @@ pub fn provide(providers: &mut ty::query::Providers) {
     *providers = ty::query::Providers {
         trait_impls_of: trait_def::trait_impls_of_provider,
         all_local_trait_impls: trait_def::all_local_trait_impls,
+        type_uninhabited_from: inhabitedness::type_uninhabited_from,
         ..*providers
     };
 }