compiler/rustc_trait_selection/src/traits/structural_match.rs

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