From bd4bd59ad7946f0717f1babb38a971b608fe4f3b Mon Sep 17 00:00:00 2001 From: Dylan MacKenzie Date: Wed, 13 May 2020 13:40:22 -0700 Subject: [PATCH] Helper method for whether type has structural equality This helper method works for all types, falling back to a query for `TyKind::Adt`s to determine whether the implement the `{Partial,}StructuralEq` traits. --- src/librustc_middle/query/mod.rs | 11 ++++ src/librustc_middle/ty/util.rs | 51 +++++++++++++++++++ .../transform/check_consts/qualifs.rs | 6 +-- .../hair/pattern/const_to_pat.rs | 2 +- src/librustc_trait_selection/traits/mod.rs | 1 + .../traits/structural_match.rs | 32 +++++++----- 6 files changed, 85 insertions(+), 18 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 @@ fn describe_as_module(def_id: DefId, tcx: TyCtxt<'_>) -> String { 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..252a11129be 100644 --- a/src/librustc_middle/ty/util.rs +++ b/src/librustc_middle/ty/util.rs @@ -778,6 +778,57 @@ pub fn needs_drop(&'tcx self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) } } + /// Returns `true` if equality for this type is both total and structural. + /// + /// Total 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 @@ fn in_adt_inherently( 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 @@ fn search_for_structural_match_violation( } 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..225bbfeb262 100644 --- a/src/librustc_trait_selection/traits/mod.rs +++ b/src/librustc_trait_selection/traits/mod.rs @@ -553,6 +553,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..d01163a29d5 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> { // 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 }) @@ -66,26 +67,25 @@ 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, 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 @@ fn tcx(&self) -> TyCtxt<'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 @@ fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool { 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) + }) + }; +} -- 2.44.0