1 use crate::ty::fold::{TypeFoldable, TypeVisitor};
2 use crate::ty::{self, AdtDef, Ty, TyCtxt};
4 use rustc::infer::InferCtxt;
5 use rustc::traits::ObligationCause;
6 use rustc::traits::{self, ConstPatternStructural, TraitEngine};
7 use rustc_data_structures::fx::FxHashSet;
12 pub enum NonStructuralMatchTy<'tcx> {
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`).
22 /// The "structure of a type" includes all components that would be
23 /// considered when doing a pattern match on a constant of that
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`
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>`.
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.
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>(
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);
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)]`).
61 /// Note that this does *not* recursively check if the substructure of `adt_ty`
62 /// implements the traits.
63 pub fn type_marked_structural(
66 infcx: &InferCtxt<'_, 'tcx>,
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(
75 ty::ParamEnv::empty(),
77 structural_peq_def_id,
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(
86 ty::ParamEnv::empty(),
88 structural_teq_def_id,
92 // We deliberately skip *reporting* fulfillment errors (via
93 // `report_fulfillment_errors`), for two reasons:
95 // 1. The error messages would mention `std::marker::StructuralPartialEq`
96 // (a trait which is solely meant as an implementation detail
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()
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> {
111 infcx: InferCtxt<'a, 'tcx>,
113 /// Records first ADT that does not implement a structural-match trait.
114 found: Option<NonStructuralMatchTy<'tcx>>,
116 /// Tracks ADTs previously encountered during search, so that
117 /// we will not recur on them again.
118 seen: FxHashSet<hir::def_id::DefId>,
121 impl Search<'a, 'tcx> {
122 fn tcx(&self) -> TyCtxt<'tcx> {
126 fn type_marked_structural(&self, adt_ty: Ty<'tcx>) -> bool {
127 type_marked_structural(self.id, self.span, &self.infcx, adt_ty)
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);
135 let (adt_def, substs) = match ty.kind {
136 ty::Adt(adt_def, substs) => (adt_def, substs),
138 self.found = Some(NonStructuralMatchTy::Param);
139 return true; // Stop visiting.
142 // structural-match ignores substructure of
143 // `*const _`/`*mut _`, so skip `super_visit_with`.
145 // For example, if you have:
147 // struct NonStructural;
148 // #[derive(PartialEq, Eq)]
149 // struct T(*const NonStructural);
150 // const C: T = T(std::ptr::null());
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.
157 // (But still tell caller to continue search.)
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`
164 // (But still tell caller to continue search.)
168 if { n.try_eval_usize(self.tcx(), ty::ParamEnv::reveal_all()) == Some(0) } =>
170 // rust-lang/rust#62336: ignore type of contents
175 ty.super_visit_with(self);
180 if !self.seen.insert(adt_def.did) {
181 debug!("Search already seen adt_def: {:?}", adt_def);
182 // let caller continue its search
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!
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.
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`.)
202 // even though we skip super_visit_with, we must recur on
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());
213 // Even though we do not want to recur on substs, we do
214 // want our caller to continue its own search.