Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

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

2 files changed, 379 insertions, 0 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
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<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/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<T, Foo> = ... ;
+// 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<T, Foo> = ... ;
+    /// 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(),
+    }
+}