src/librustc/traits/structural_match.rs

   1 use crate::ty::fold::{TypeFoldable, TypeVisitor};
   2 use crate::ty::{self, AdtDef, Ty, TyCtxt};
   3
   4 use rustc::infer::InferCtxt;
   5 use rustc::traits::ObligationCause;
   6 use rustc::traits::{self, ConstPatternStructural, TraitEngine};
   7 use rustc_data_structures::fx::FxHashSet;
   8 use rustc_hir as hir;
   9 use rustc_span::Span;
  10
  11 #[derive(Debug)]
  12 pub enum NonStructuralMatchTy<'tcx> {
  13     Adt(&'tcx AdtDef),
  14     Param,
  15 }
  16
  17 /// This method traverses the structure of `ty`, trying to find an
  18 /// instance of an ADT (i.e. struct or enum) that was declared without
  19 /// the `#[structural_match]` attribute, or a generic type parameter
  20 /// (which cannot be determined to be `structural_match`).
  21 ///
  22 /// The "structure of a type" includes all components that would be
  23 /// considered when doing a pattern match on a constant of that
  24 /// type.
  25 ///
  26 ///  * This means this method descends into fields of structs/enums,
  27 ///    and also descends into the inner type `T` of `&T` and `&mut T`
  28 ///
  29 ///  * The traversal doesn't dereference unsafe pointers (`*const T`,
  30 ///    `*mut T`), and it does not visit the type arguments of an
  31 ///    instantiated generic like `PhantomData<T>`.
  32 ///
  33 /// The reason we do this search is Rust currently require all ADTs
  34 /// reachable from a constant's type to be annotated with
  35 /// `#[structural_match]`, an attribute which essentially says that
  36 /// the implementation of `PartialEq::eq` behaves *equivalently* to a
  37 /// comparison against the unfolded structure.
  38 ///
  39 /// For more background on why Rust has this requirement, and issues
  40 /// that arose when the requirement was not enforced completely, see
  41 /// Rust RFC 1445, rust-lang/rust#61188, and rust-lang/rust#62307.
  42 pub fn search_for_structural_match_violation<'tcx>(
  43     id: hir::HirId,
  44     span: Span,
  45     tcx: TyCtxt<'tcx>,
  46     ty: Ty<'tcx>,
  47 ) -> Option<NonStructuralMatchTy<'tcx>> {
  48     // FIXME: we should instead pass in an `infcx` from the outside.
  49     tcx.infer_ctxt().enter(|infcx| {
  50         let mut search = Search { id, span, infcx, found: None, seen: FxHashSet::default() };
  51         ty.visit_with(&mut search);
  52         search.found
  53     })
  54 }
  55
  56 /// This method returns true if and only if `adt_ty` itself has been marked as
  57 /// eligible for structural-match: namely, if it implements both
  58 /// `StructuralPartialEq` and `StructuralEq` (which are respectively injected by
  59 /// `#[derive(PartialEq)]` and `#[derive(Eq)]`).
  60 ///
  61 /// Note that this does *not* recursively check if the substructure of `adt_ty`
  62 /// implements the traits.
  63 pub fn type_marked_structural(
  64     id: hir::HirId,
  65     span: Span,
  66     infcx: &InferCtxt<'_, 'tcx>,
  67     adt_ty: Ty<'tcx>,
  68 ) -> bool {
  69     let mut fulfillment_cx = traits::FulfillmentContext::new();
  70     let cause = ObligationCause::new(span, id, ConstPatternStructural);
  71     // require `#[derive(PartialEq)]`
  72     let structural_peq_def_id = infcx.tcx.lang_items().structural_peq_trait().unwrap();
  73     fulfillment_cx.register_bound(
  74         infcx,
  75         ty::ParamEnv::empty(),
  76         adt_ty,
  77         structural_peq_def_id,
  78         cause,
  79     );
  80     // for now, require `#[derive(Eq)]`. (Doing so is a hack to work around
  81     // the type `for<'a> fn(&'a ())` failing to implement `Eq` itself.)
  82     let cause = ObligationCause::new(span, id, ConstPatternStructural);
  83     let structural_teq_def_id = infcx.tcx.lang_items().structural_teq_trait().unwrap();
  84     fulfillment_cx.register_bound(
  85         infcx,
  86         ty::ParamEnv::empty(),
  87         adt_ty,
  88         structural_teq_def_id,
  89         cause,
  90     );
  91
  92     // We deliberately skip *reporting* fulfillment errors (via
  93     // `report_fulfillment_errors`), for two reasons:
  94     //
  95     // 1. The error messages would mention `std::marker::StructuralPartialEq`
  96     //    (a trait which is solely meant as an implementation detail
  97     //    for now), and
  98     //
  99     // 2. We are sometimes doing future-incompatibility lints for
 100     //    now, so we do not want unconditional errors here.
 101     fulfillment_cx.select_all_or_error(infcx).is_ok()
 102 }
 103
 104 /// This implements the traversal over the structure of a given type to try to
 105 /// find instances of ADTs (specifically structs or enums) that do not implement
 106 /// the structural-match traits (`StructuralPartialEq` and `StructuralEq`).
 107 struct Search<'a, 'tcx> {
 108     id: hir::HirId,
 109     span: Span,
 110
 111     infcx: InferCtxt<'a, 'tcx>,
 112
 113     /// Records first ADT that does not implement a structural-match trait.
 114     found: Option<NonStructuralMatchTy<'tcx>>,
 115
 116     /// Tracks ADTs previously encountered during search, so that
 117     /// we will not recur on them again.
 118     seen: FxHashSet<hir::def_id::DefId>,
 119 }
 120
 121 impl Search<'a, 'tcx> {
 122     fn tcx(&self) -> TyCtxt<'tcx> {
 123         self.infcx.tcx
 124     }
 125
 126     fn type_marked_structural(&self, adt_ty: Ty<'tcx>) -> bool {
 127         type_marked_structural(self.id, self.span, &self.infcx, adt_ty)
 128     }
 129 }
 130
 131 impl<'a, 'tcx> TypeVisitor<'tcx> for Search<'a, 'tcx> {
 132     fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 133         debug!("Search visiting ty: {:?}", ty);
 134
 135         let (adt_def, substs) = match ty.kind {
 136             ty::Adt(adt_def, substs) => (adt_def, substs),
 137             ty::Param(_) => {
 138                 self.found = Some(NonStructuralMatchTy::Param);
 139                 return true; // Stop visiting.
 140             }
 141             ty::RawPtr(..) => {
 142                 // structural-match ignores substructure of
 143                 // `*const _`/`*mut _`, so skip `super_visit_with`.
 144                 //
 145                 // For example, if you have:
 146                 // ```
 147                 // struct NonStructural;
 148                 // #[derive(PartialEq, Eq)]
 149                 // struct T(*const NonStructural);
 150                 // const C: T = T(std::ptr::null());
 151                 // ```
 152                 //
 153                 // Even though `NonStructural` does not implement `PartialEq`,
 154                 // structural equality on `T` does not recur into the raw
 155                 // pointer. Therefore, one can still use `C` in a pattern.
 156
 157                 // (But still tell caller to continue search.)
 158                 return false;
 159             }
 160             ty::FnDef(..) | ty::FnPtr(..) => {
 161                 // types of formals and return in `fn(_) -> _` are also irrelevant;
 162                 // so we do not recur into them via `super_visit_with`
 163                 //
 164                 // (But still tell caller to continue search.)
 165                 return false;
 166             }
 167             ty::Array(_, n)
 168                 if { n.try_eval_usize(self.tcx(), ty::ParamEnv::reveal_all()) == Some(0) } =>
 169             {
 170                 // rust-lang/rust#62336: ignore type of contents
 171                 // for empty array.
 172                 return false;
 173             }
 174             _ => {
 175                 ty.super_visit_with(self);
 176                 return false;
 177             }
 178         };
 179
 180         if !self.seen.insert(adt_def.did) {
 181             debug!("Search already seen adt_def: {:?}", adt_def);
 182             // let caller continue its search
 183             return false;
 184         }
 185
 186         if !self.type_marked_structural(ty) {
 187             debug!("Search found ty: {:?}", ty);
 188             self.found = Some(NonStructuralMatchTy::Adt(&adt_def));
 189             return true; // Halt visiting!
 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         for field_ty in adt_def.all_fields().map(|field| field.ty(tcx, substs)) {
 206             if field_ty.visit_with(self) {
 207                 // found an ADT without structural-match; halt visiting!
 208                 assert!(self.found.is_some());
 209                 return true;
 210             }
 211         }
 212
 213         // Even though we do not want to recur on substs, we do
 214         // want our caller to continue its own search.
 215         false
 216     }
 217 }