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::Alias(..) => {
  99                 return ControlFlow::Break(ty);
 100             }
 101             ty::Closure(..) => {
 102                 return ControlFlow::Break(ty);
 103             }
 104             ty::Generator(..) | ty::GeneratorWitness(..) | ty::GeneratorWitnessMIR(..) => {
 105                 return ControlFlow::Break(ty);
 106             }
 107             ty::FnDef(..) => {
 108                 // Types of formals and return in `fn(_) -> _` are also irrelevant;
 109                 // so we do not recur into them via `super_visit_with`
 110                 return ControlFlow::Continue(());
 111             }
 112             ty::Array(_, n)
 113                 if { n.try_eval_usize(self.tcx, ty::ParamEnv::reveal_all()) == Some(0) } =>
 114             {
 115                 // rust-lang/rust#62336: ignore type of contents
 116                 // for empty array.
 117                 return ControlFlow::Continue(());
 118             }
 119             ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Str | ty::Never => {
 120                 // These primitive types are always structural match.
 121                 //
 122                 // `Never` is kind of special here, but as it is not inhabitable, this should be fine.
 123                 return ControlFlow::Continue(());
 124             }
 125
 126             ty::FnPtr(..) => {
 127                 if !self.adt_const_param {
 128                     return ControlFlow::Continue(());
 129                 } else {
 130                     return ControlFlow::Break(ty);
 131                 }
 132             }
 133
 134             ty::RawPtr(..) => {
 135                 if !self.adt_const_param {
 136                     // structural-match ignores substructure of
 137                     // `*const _`/`*mut _`, so skip `super_visit_with`.
 138                     //
 139                     // For example, if you have:
 140                     // ```
 141                     // struct NonStructural;
 142                     // #[derive(PartialEq, Eq)]
 143                     // struct T(*const NonStructural);
 144                     // const C: T = T(std::ptr::null());
 145                     // ```
 146                     //
 147                     // Even though `NonStructural` does not implement `PartialEq`,
 148                     // structural equality on `T` does not recur into the raw
 149                     // pointer. Therefore, one can still use `C` in a pattern.
 150                     return ControlFlow::Continue(());
 151                 } else {
 152                     return ControlFlow::Break(ty);
 153                 }
 154             }
 155
 156             ty::Float(_) => {
 157                 if !self.adt_const_param {
 158                     return ControlFlow::Continue(());
 159                 } else {
 160                     return ControlFlow::Break(ty);
 161                 }
 162             }
 163
 164             ty::Array(..) | ty::Slice(_) | ty::Ref(..) | ty::Tuple(..) => {
 165                 // First check all contained types and then tell the caller to continue searching.
 166                 return ty.super_visit_with(self);
 167             }
 168             ty::Infer(_) | ty::Placeholder(_) | ty::Bound(..) => {
 169                 bug!("unexpected type during structural-match checking: {:?}", ty);
 170             }
 171             ty::Error(_) => {
 172                 self.tcx.sess.delay_span_bug(self.span, "ty::Error in structural-match check");
 173                 // We still want to check other types after encountering an error,
 174                 // as this may still emit relevant errors.
 175                 return ControlFlow::Continue(());
 176             }
 177         };
 178
 179         if !self.seen.insert(adt_def.did()) {
 180             debug!("Search already seen adt_def: {:?}", adt_def);
 181             return ControlFlow::Continue(());
 182         }
 183
 184         if !self.type_marked_structural(ty) {
 185             debug!("Search found ty: {:?}", ty);
 186             return ControlFlow::Break(ty);
 187         }
 188
 189         // structural-match does not care about the
 190         // instantiation of the generics in an ADT (it
 191         // instead looks directly at its fields outside
 192         // this match), so we skip super_visit_with.
 193         //
 194         // (Must not recur on substs for `PhantomData<T>` cf
 195         // rust-lang/rust#55028 and rust-lang/rust#55837; but also
 196         // want to skip substs when only uses of generic are
 197         // behind unsafe pointers `*const T`/`*mut T`.)
 198
 199         // even though we skip super_visit_with, we must recur on
 200         // fields of ADT.
 201         let tcx = self.tcx;
 202         adt_def.all_fields().map(|field| field.ty(tcx, substs)).try_for_each(|field_ty| {
 203             let ty = self.tcx.normalize_erasing_regions(ty::ParamEnv::empty(), field_ty);
 204             debug!("structural-match ADT: field_ty={:?}, ty={:?}", field_ty, ty);
 205             ty.visit_with(self)
 206         })
 207     }
 208 }