Rollup merge of #73066 - ecstatic-morse:query-structural-eq2, r=pnkfelix

Querify whether a type has structural equality (Take 2)

Alternative to #72177.

Unlike in #72177, this helper method works for all types, falling back to a query for `TyKind::Adt`s that determines whether the `{Partial,}StructuralEq` traits are implemented.

This is my preferred interface for this method. I think this is better than just documenting that the helper only works for ADTs. If others disagree, we can just merge #72177 with the fixes applied. This has already taken far too long.

6 files changed, 86 insertions, 20 deletions

diff --git a/src/librustc_middle/query/mod.rs b/src/librustc_middle/query/mod.rs
index 4d7e7882e42..be15e6c576f 100644
--- a/src/librustc_middle/query/mod.rs
+++ b/src/librustc_middle/query/mod.rs
@@ -789,6 +789,17 @@ rustc_queries! {
             desc { "computing whether `{}` needs drop", env.value }
         }
 
+        /// Query backing `TyS::is_structural_eq_shallow`.
+        ///
+        /// This is only correct for ADTs. Call `is_structural_eq_shallow` to handle all types
+        /// correctly.
+        query has_structural_eq_impls(ty: Ty<'tcx>) -> bool {
+            desc {
+                "computing whether `{:?}` implements `PartialStructuralEq` and `StructuralEq`",
+                ty
+            }
+        }
+
         /// A list of types where the ADT requires drop if and only if any of
         /// those types require drop. If the ADT is known to always need drop
         /// then `Err(AlwaysRequiresDrop)` is returned.
diff --git a/src/librustc_middle/ty/util.rs b/src/librustc_middle/ty/util.rs
index c2b794ca4bd..c61e27528ce 100644
--- a/src/librustc_middle/ty/util.rs
+++ b/src/librustc_middle/ty/util.rs
@@ -778,6 +778,57 @@ impl<'tcx> ty::TyS<'tcx> {
         }
     }
 
+    /// Returns `true` if equality for this type is both reflexive and structural.
+    ///
+    /// Reflexive equality for a type is indicated by an `Eq` impl for that type.
+    ///
+    /// Primitive types (`u32`, `str`) have structural equality by definition. For composite data
+    /// types, equality for the type as a whole is structural when it is the same as equality
+    /// between all components (fields, array elements, etc.) of that type. For ADTs, structural
+    /// equality is indicated by an implementation of `PartialStructuralEq` and `StructuralEq` for
+    /// that type.
+    ///
+    /// This function is "shallow" because it may return `true` for a composite type whose fields
+    /// are not `StructuralEq`. For example, `[T; 4]` has structural equality regardless of `T`
+    /// because equality for arrays is determined by the equality of each array element. If you
+    /// want to know whether a given call to `PartialEq::eq` will proceed structurally all the way
+    /// down, you will need to use a type visitor.
+    #[inline]
+    pub fn is_structural_eq_shallow(&'tcx self, tcx: TyCtxt<'tcx>) -> bool {
+        match self.kind {
+            // Look for an impl of both `PartialStructuralEq` and `StructuralEq`.
+            Adt(..) => tcx.has_structural_eq_impls(self),
+
+            // Primitive types that satisfy `Eq`.
+            Bool | Char | Int(_) | Uint(_) | Str | Never => true,
+
+            // Composite types that satisfy `Eq` when all of their fields do.
+            //
+            // Because this function is "shallow", we return `true` for these composites regardless
+            // of the type(s) contained within.
+            Ref(..) | Array(..) | Slice(_) | Tuple(..) => true,
+
+            // Raw pointers use bitwise comparison.
+            RawPtr(_) | FnPtr(_) => true,
+
+            // Floating point numbers are not `Eq`.
+            Float(_) => false,
+
+            // Conservatively return `false` for all others...
+
+            // Anonymous function types
+            FnDef(..) | Closure(..) | Dynamic(..) | Generator(..) => false,
+
+            // Generic or inferred types
+            //
+            // FIXME(ecstaticmorse): Maybe we should `bug` here? This should probably only be
+            // called for known, fully-monomorphized types.
+            Projection(_) | Opaque(..) | Param(_) | Bound(..) | Placeholder(_) | Infer(_) => false,
+
+            Foreign(_) | GeneratorWitness(..) | Error => false,
+        }
+    }
+
     pub fn same_type(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
         match (&a.kind, &b.kind) {
             (&Adt(did_a, substs_a), &Adt(did_b, substs_b)) => {
diff --git a/src/librustc_mir/transform/check_consts/qualifs.rs b/src/librustc_mir/transform/check_consts/qualifs.rs
index 5d604d8e3d7..936c1a84e14 100644
--- a/src/librustc_mir/transform/check_consts/qualifs.rs
+++ b/src/librustc_mir/transform/check_consts/qualifs.rs
@@ -2,7 +2,6 @@
 //!
 //! See the `Qualif` trait for more info.
 
-use rustc_infer::infer::TyCtxtInferExt;
 use rustc_middle::mir::*;
 use rustc_middle::ty::{self, subst::SubstsRef, AdtDef, Ty};
 use rustc_span::DUMMY_SP;
@@ -137,10 +136,7 @@ impl Qualif for CustomEq {
         substs: SubstsRef<'tcx>,
     ) -> bool {
         let ty = cx.tcx.mk_ty(ty::Adt(adt, substs));
-        let id = cx.tcx.hir().local_def_id_to_hir_id(cx.def_id.as_local().unwrap());
-        cx.tcx
-            .infer_ctxt()
-            .enter(|infcx| !traits::type_marked_structural(id, cx.body.span, &infcx, ty))
+        !ty.is_structural_eq_shallow(cx.tcx)
     }
 }
 
diff --git a/src/librustc_mir_build/hair/pattern/const_to_pat.rs b/src/librustc_mir_build/hair/pattern/const_to_pat.rs
index 9e3f75fdc07..46b687d76e5 100644
--- a/src/librustc_mir_build/hair/pattern/const_to_pat.rs
+++ b/src/librustc_mir_build/hair/pattern/const_to_pat.rs
@@ -80,7 +80,7 @@ impl<'a, 'tcx> ConstToPat<'a, 'tcx> {
     }
 
     fn type_marked_structural(&self, ty: Ty<'tcx>) -> bool {
-        traits::type_marked_structural(self.id, self.span, &self.infcx, ty)
+        ty.is_structural_eq_shallow(self.infcx.tcx)
     }
 
     fn to_pat(
diff --git a/src/librustc_trait_selection/traits/mod.rs b/src/librustc_trait_selection/traits/mod.rs
index 6abea18ee29..9ab87e6b6ca 100644
--- a/src/librustc_trait_selection/traits/mod.rs
+++ b/src/librustc_trait_selection/traits/mod.rs
@@ -60,7 +60,6 @@ pub use self::specialize::specialization_graph::FutureCompatOverlapError;
 pub use self::specialize::specialization_graph::FutureCompatOverlapErrorKind;
 pub use self::specialize::{specialization_graph, translate_substs, OverlapError};
 pub use self::structural_match::search_for_structural_match_violation;
-pub use self::structural_match::type_marked_structural;
 pub use self::structural_match::NonStructuralMatchTy;
 pub use self::util::{elaborate_predicates, elaborate_trait_ref, elaborate_trait_refs};
 pub use self::util::{expand_trait_aliases, TraitAliasExpander};
@@ -553,6 +552,7 @@ fn type_implements_trait<'tcx>(
 
 pub fn provide(providers: &mut ty::query::Providers<'_>) {
     object_safety::provide(providers);
+    structural_match::provide(providers);
     *providers = ty::query::Providers {
         specialization_graph_of: specialize::specialization_graph_provider,
         specializes: specialize::specializes,
diff --git a/src/librustc_trait_selection/traits/structural_match.rs b/src/librustc_trait_selection/traits/structural_match.rs
index 87ff667b6a0..e59fbd313c8 100644
--- a/src/librustc_trait_selection/traits/structural_match.rs
+++ b/src/librustc_trait_selection/traits/structural_match.rs
@@ -1,10 +1,11 @@
 use crate::infer::{InferCtxt, TyCtxtInferExt};
 use crate::traits::ObligationCause;
-use crate::traits::{self, ConstPatternStructural, TraitEngine};
+use crate::traits::{self, TraitEngine};
 
 use rustc_data_structures::fx::FxHashSet;
 use rustc_hir as hir;
 use rustc_hir::lang_items::{StructuralPeqTraitLangItem, StructuralTeqTraitLangItem};
+use rustc_middle::ty::query::Providers;
 use rustc_middle::ty::{self, AdtDef, Ty, TyCtxt, TypeFoldable, TypeVisitor};
 use rustc_span::Span;
 
@@ -45,14 +46,14 @@ pub enum NonStructuralMatchTy<'tcx> {
 /// that arose when the requirement was not enforced completely, see
 /// Rust RFC 1445, rust-lang/rust#61188, and rust-lang/rust#62307.
 pub fn search_for_structural_match_violation<'tcx>(
-    id: hir::HirId,
+    _id: hir::HirId,
     span: Span,
     tcx: TyCtxt<'tcx>,
     ty: Ty<'tcx>,
 ) -> Option<NonStructuralMatchTy<'tcx>> {
     // FIXME: we should instead pass in an `infcx` from the outside.
     tcx.infer_ctxt().enter(|infcx| {
-        let mut search = Search { id, span, infcx, found: None, seen: FxHashSet::default() };
+        let mut search = Search { infcx, span, found: None, seen: FxHashSet::default() };
         ty.visit_with(&mut search);
         search.found
     })
@@ -65,27 +66,26 @@ pub fn search_for_structural_match_violation<'tcx>(
 ///
 /// Note that this does *not* recursively check if the substructure of `adt_ty`
 /// implements the traits.
-pub fn type_marked_structural(
-    id: hir::HirId,
-    span: Span,
+fn type_marked_structural(
     infcx: &InferCtxt<'_, 'tcx>,
     adt_ty: Ty<'tcx>,
+    cause: ObligationCause<'tcx>,
 ) -> bool {
     let mut fulfillment_cx = traits::FulfillmentContext::new();
-    let cause = ObligationCause::new(span, id, ConstPatternStructural);
     // require `#[derive(PartialEq)]`
-    let structural_peq_def_id = infcx.tcx.require_lang_item(StructuralPeqTraitLangItem, Some(span));
+    let structural_peq_def_id =
+        infcx.tcx.require_lang_item(StructuralPeqTraitLangItem, Some(cause.span));
     fulfillment_cx.register_bound(
         infcx,
         ty::ParamEnv::empty(),
         adt_ty,
         structural_peq_def_id,
-        cause,
+        cause.clone(),
     );
     // for now, require `#[derive(Eq)]`. (Doing so is a hack to work around
     // the type `for<'a> fn(&'a ())` failing to implement `Eq` itself.)
-    let cause = ObligationCause::new(span, id, ConstPatternStructural);
-    let structural_teq_def_id = infcx.tcx.require_lang_item(StructuralTeqTraitLangItem, Some(span));
+    let structural_teq_def_id =
+        infcx.tcx.require_lang_item(StructuralTeqTraitLangItem, Some(cause.span));
     fulfillment_cx.register_bound(
         infcx,
         ty::ParamEnv::empty(),
@@ -110,7 +110,6 @@ pub fn type_marked_structural(
 /// find instances of ADTs (specifically structs or enums) that do not implement
 /// the structural-match traits (`StructuralPartialEq` and `StructuralEq`).
 struct Search<'a, 'tcx> {
-    id: hir::HirId,
     span: Span,
 
     infcx: InferCtxt<'a, 'tcx>,
@@ -129,7 +128,7 @@ impl Search<'a, 'tcx> {
     }
 
     fn type_marked_structural(&self, adt_ty: Ty<'tcx>) -> bool {
-        type_marked_structural(self.id, self.span, &self.infcx, adt_ty)
+        adt_ty.is_structural_eq_shallow(self.tcx())
     }
 }
 
@@ -266,3 +265,12 @@ impl<'a, 'tcx> TypeVisitor<'tcx> for Search<'a, 'tcx> {
         false
     }
 }
+
+pub fn provide(providers: &mut Providers<'_>) {
+    providers.has_structural_eq_impls = |tcx, ty| {
+        tcx.infer_ctxt().enter(|infcx| {
+            let cause = ObligationCause::dummy();
+            type_marked_structural(&infcx, ty, cause)
+        })
+    };
+}