compiler/rustc_trait_selection/src/traits/structural_match.rs

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