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