src/librustc_trait_selection/traits/structural_match.rs

   1 use crate::infer::{InferCtxt, TyCtxtInferExt};
   2 use crate::traits::ObligationCause;
   3 use crate::traits::{self, TraitEngine};
   4
   5 use rustc_data_structures::fx::FxHashSet;
   6 use rustc_hir as hir;
   7 use rustc_hir::lang_items::{StructuralPeqTraitLangItem, StructuralTeqTraitLangItem};
   8 use rustc_middle::ty::query::Providers;
   9 use rustc_middle::ty::{self, AdtDef, Ty, TyCtxt, TypeFoldable, TypeVisitor};
  10 use rustc_span::Span;
  11
  12 #[derive(Debug)]
  13 pub enum NonStructuralMatchTy<'tcx> {
  14     Adt(&'tcx AdtDef),
  15     Param,
  16     Dynamic,
  17     Foreign,
  18     Opaque,
  19     Generator,
  20     Projection,
  21     Closure,
  22 }
  23
  24 /// This method traverses the structure of `ty`, trying to find an
  25 /// instance of an ADT (i.e. struct or enum) that doesn't implement
  26 /// the structural-match traits, or a generic type parameter
  27 /// (which cannot be determined to be structural-match).
  28 ///
  29 /// The "structure of a type" includes all components that would be
  30 /// considered when doing a pattern match on a constant of that
  31 /// type.
  32 ///
  33 ///  * This means this method descends into fields of structs/enums,
  34 ///    and also descends into the inner type `T` of `&T` and `&mut T`
  35 ///
  36 ///  * The traversal doesn't dereference unsafe pointers (`*const T`,
  37 ///    `*mut T`), and it does not visit the type arguments of an
  38 ///    instantiated generic like `PhantomData<T>`.
  39 ///
  40 /// The reason we do this search is Rust currently require all ADTs
  41 /// reachable from a constant's type to implement the
  42 /// structural-match traits, which essentially say that
  43 /// the implementation of `PartialEq::eq` behaves *equivalently* to a
  44 /// comparison against the unfolded structure.
  45 ///
  46 /// For more background on why Rust has this requirement, and issues
  47 /// that arose when the requirement was not enforced completely, see
  48 /// Rust RFC 1445, rust-lang/rust#61188, and rust-lang/rust#62307.
  49 pub fn search_for_structural_match_violation<'tcx>(
  50     _id: hir::HirId,
  51     span: Span,
  52     tcx: TyCtxt<'tcx>,
  53     ty: Ty<'tcx>,
  54 ) -> Option<NonStructuralMatchTy<'tcx>> {
  55     // FIXME: we should instead pass in an `infcx` from the outside.
  56     tcx.infer_ctxt().enter(|infcx| {
  57         let mut search = Search { infcx, span, found: None, seen: FxHashSet::default() };
  58         ty.visit_with(&mut search);
  59         search.found
  60     })
  61 }
  62
  63 /// This method returns true if and only if `adt_ty` itself has been marked as
  64 /// eligible for structural-match: namely, if it implements both
  65 /// `StructuralPartialEq` and `StructuralEq` (which are respectively injected by
  66 /// `#[derive(PartialEq)]` and `#[derive(Eq)]`).
  67 ///
  68 /// Note that this does *not* recursively check if the substructure of `adt_ty`
  69 /// implements the traits.
  70 fn type_marked_structural(
  71     infcx: &InferCtxt<'_, 'tcx>,
  72     adt_ty: Ty<'tcx>,
  73     cause: ObligationCause<'tcx>,
  74 ) -> bool {
  75     let mut fulfillment_cx = traits::FulfillmentContext::new();
  76     // require `#[derive(PartialEq)]`
  77     let structural_peq_def_id =
  78         infcx.tcx.require_lang_item(StructuralPeqTraitLangItem, Some(cause.span));
  79     fulfillment_cx.register_bound(
  80         infcx,
  81         ty::ParamEnv::empty(),
  82         adt_ty,
  83         structural_peq_def_id,
  84         cause.clone(),
  85     );
  86     // for now, require `#[derive(Eq)]`. (Doing so is a hack to work around
  87     // the type `for<'a> fn(&'a ())` failing to implement `Eq` itself.)
  88     let structural_teq_def_id =
  89         infcx.tcx.require_lang_item(StructuralTeqTraitLangItem, Some(cause.span));
  90     fulfillment_cx.register_bound(
  91         infcx,
  92         ty::ParamEnv::empty(),
  93         adt_ty,
  94         structural_teq_def_id,
  95         cause,
  96     );
  97
  98     // We deliberately skip *reporting* fulfillment errors (via
  99     // `report_fulfillment_errors`), for two reasons:
 100     //
 101     // 1. The error messages would mention `std::marker::StructuralPartialEq`
 102     //    (a trait which is solely meant as an implementation detail
 103     //    for now), and
 104     //
 105     // 2. We are sometimes doing future-incompatibility lints for
 106     //    now, so we do not want unconditional errors here.
 107     fulfillment_cx.select_all_or_error(infcx).is_ok()
 108 }
 109
 110 /// This implements the traversal over the structure of a given type to try to
 111 /// find instances of ADTs (specifically structs or enums) that do not implement
 112 /// the structural-match traits (`StructuralPartialEq` and `StructuralEq`).
 113 struct Search<'a, 'tcx> {
 114     span: Span,
 115
 116     infcx: InferCtxt<'a, 'tcx>,
 117
 118     /// Records first ADT that does not implement a structural-match trait.
 119     found: Option<NonStructuralMatchTy<'tcx>>,
 120
 121     /// Tracks ADTs previously encountered during search, so that
 122     /// we will not recur on them again.
 123     seen: FxHashSet<hir::def_id::DefId>,
 124 }
 125
 126 impl Search<'a, 'tcx> {
 127     fn tcx(&self) -> TyCtxt<'tcx> {
 128         self.infcx.tcx
 129     }
 130
 131     fn type_marked_structural(&self, adt_ty: Ty<'tcx>) -> bool {
 132         adt_ty.is_structural_eq_shallow(self.tcx())
 133     }
 134 }
 135
 136 impl<'a, 'tcx> TypeVisitor<'tcx> for Search<'a, 'tcx> {
 137     fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 138         debug!("Search visiting ty: {:?}", ty);
 139
 140         let (adt_def, substs) = match ty.kind {
 141             ty::Adt(adt_def, substs) => (adt_def, substs),
 142             ty::Param(_) => {
 143                 self.found = Some(NonStructuralMatchTy::Param);
 144                 return true; // Stop visiting.
 145             }
 146             ty::Dynamic(..) => {
 147                 self.found = Some(NonStructuralMatchTy::Dynamic);
 148                 return true; // Stop visiting.
 149             }
 150             ty::Foreign(_) => {
 151                 self.found = Some(NonStructuralMatchTy::Foreign);
 152                 return true; // Stop visiting.
 153             }
 154             ty::Opaque(..) => {
 155                 self.found = Some(NonStructuralMatchTy::Opaque);
 156                 return true; // Stop visiting.
 157             }
 158             ty::Projection(..) => {
 159                 self.found = Some(NonStructuralMatchTy::Projection);
 160                 return true; // Stop visiting.
 161             }
 162             ty::Generator(..) | ty::GeneratorWitness(..) => {
 163                 self.found = Some(NonStructuralMatchTy::Generator);
 164                 return true; // Stop visiting.
 165             }
 166             ty::Closure(..) => {
 167                 self.found = Some(NonStructuralMatchTy::Closure);
 168                 return true; // Stop visiting.
 169             }
 170             ty::RawPtr(..) => {
 171                 // structural-match ignores substructure of
 172                 // `*const _`/`*mut _`, so skip `super_visit_with`.
 173                 //
 174                 // For example, if you have:
 175                 // ```
 176                 // struct NonStructural;
 177                 // #[derive(PartialEq, Eq)]
 178                 // struct T(*const NonStructural);
 179                 // const C: T = T(std::ptr::null());
 180                 // ```
 181                 //
 182                 // Even though `NonStructural` does not implement `PartialEq`,
 183                 // structural equality on `T` does not recur into the raw
 184                 // pointer. Therefore, one can still use `C` in a pattern.
 185
 186                 // (But still tell the caller to continue search.)
 187                 return false;
 188             }
 189             ty::FnDef(..) | ty::FnPtr(..) => {
 190                 // Types of formals and return in `fn(_) -> _` are also irrelevant;
 191                 // so we do not recur into them via `super_visit_with`
 192                 //
 193                 // (But still tell the caller to continue search.)
 194                 return false;
 195             }
 196             ty::Array(_, n)
 197                 if { n.try_eval_usize(self.tcx(), ty::ParamEnv::reveal_all()) == Some(0) } =>
 198             {
 199                 // rust-lang/rust#62336: ignore type of contents
 200                 // for empty array.
 201                 //
 202                 // (But still tell the caller to continue search.)
 203                 return false;
 204             }
 205             ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Str | ty::Never => {
 206                 // These primitive types are always structural match.
 207                 //
 208                 // `Never` is kind of special here, but as it is not inhabitable, this should be fine.
 209                 //
 210                 // (But still tell the caller to continue search.)
 211                 return false;
 212             }
 213
 214             ty::Array(..) | ty::Slice(_) | ty::Ref(..) | ty::Tuple(..) => {
 215                 // First check all contained types and then tell the caller to continue searching.
 216                 ty.super_visit_with(self);
 217                 return false;
 218             }
 219             ty::Infer(_) | ty::Placeholder(_) | ty::Bound(..) => {
 220                 bug!("unexpected type during structural-match checking: {:?}", ty);
 221             }
 222             ty::Error(_) => {
 223                 self.tcx().sess.delay_span_bug(self.span, "ty::Error in structural-match check");
 224                 // We still want to check other types after encountering an error,
 225                 // as this may still emit relevant errors.
 226                 //
 227                 // So we continue searching here.
 228                 return false;
 229             }
 230         };
 231
 232         if !self.seen.insert(adt_def.did) {
 233             debug!("Search already seen adt_def: {:?}", adt_def);
 234             // Let caller continue its search.
 235             return false;
 236         }
 237
 238         if !self.type_marked_structural(ty) {
 239             debug!("Search found ty: {:?}", ty);
 240             self.found = Some(NonStructuralMatchTy::Adt(&adt_def));
 241             return true; // Halt visiting!
 242         }
 243
 244         // structural-match does not care about the
 245         // instantiation of the generics in an ADT (it
 246         // instead looks directly at its fields outside
 247         // this match), so we skip super_visit_with.
 248         //
 249         // (Must not recur on substs for `PhantomData<T>` cf
 250         // rust-lang/rust#55028 and rust-lang/rust#55837; but also
 251         // want to skip substs when only uses of generic are
 252         // behind unsafe pointers `*const T`/`*mut T`.)
 253
 254         // even though we skip super_visit_with, we must recur on
 255         // fields of ADT.
 256         let tcx = self.tcx();
 257         for field_ty in adt_def.all_fields().map(|field| field.ty(tcx, substs)) {
 258             let ty = self.tcx().normalize_erasing_regions(ty::ParamEnv::empty(), field_ty);
 259             debug!("structural-match ADT: field_ty={:?}, ty={:?}", field_ty, ty);
 260
 261             if ty.visit_with(self) {
 262                 // found an ADT without structural-match; halt visiting!
 263                 assert!(self.found.is_some());
 264                 return true;
 265             }
 266         }
 267
 268         // Even though we do not want to recur on substs, we do
 269         // want our caller to continue its own search.
 270         false
 271     }
 272 }
 273
 274 pub fn provide(providers: &mut Providers) {
 275     providers.has_structural_eq_impls = |tcx, ty| {
 276         tcx.infer_ctxt().enter(|infcx| {
 277             let cause = ObligationCause::dummy();
 278             type_marked_structural(&infcx, ty, cause)
 279         })
 280     };
 281 }