src/librustc_infer/traits/structural_match.rs

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