1 use crate::infer::{InferCtxt, TyCtxtInferExt};
2 use crate::traits::{ObligationCause, ObligationCtxt};
4 use rustc_data_structures::fx::FxHashSet;
6 use rustc_hir::lang_items::LangItem;
7 use rustc_middle::ty::query::Providers;
8 use rustc_middle::ty::{self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor};
10 use std::ops::ControlFlow;
12 /// This method traverses the structure of `ty`, trying to find an
13 /// instance of an ADT (i.e. struct or enum) that doesn't implement
14 /// the structural-match traits, or a generic type parameter
15 /// (which cannot be determined to be structural-match).
17 /// The "structure of a type" includes all components that would be
18 /// considered when doing a pattern match on a constant of that
21 /// * This means this method descends into fields of structs/enums,
22 /// and also descends into the inner type `T` of `&T` and `&mut T`
24 /// * The traversal doesn't dereference unsafe pointers (`*const T`,
25 /// `*mut T`), and it does not visit the type arguments of an
26 /// instantiated generic like `PhantomData<T>`.
28 /// The reason we do this search is Rust currently require all ADTs
29 /// reachable from a constant's type to implement the
30 /// structural-match traits, which essentially say that
31 /// the implementation of `PartialEq::eq` behaves *equivalently* to a
32 /// comparison against the unfolded structure.
34 /// For more background on why Rust has this requirement, and issues
35 /// that arose when the requirement was not enforced completely, see
36 /// Rust RFC 1445, rust-lang/rust#61188, and rust-lang/rust#62307.
37 pub fn search_for_structural_match_violation<'tcx>(
41 ) -> Option<Ty<'tcx>> {
42 ty.visit_with(&mut Search { tcx, span, seen: FxHashSet::default(), adt_const_param: false })
46 /// This method traverses the structure of `ty`, trying to find any
47 /// types that are not allowed to be used in a const generic.
49 /// This is either because the type does not implement `StructuralEq`
50 /// and `StructuralPartialEq`, or because the type is intentionally
51 /// not supported in const generics (such as floats and raw pointers,
52 /// which are allowed in match blocks).
53 pub fn search_for_adt_const_param_violation<'tcx>(
57 ) -> Option<Ty<'tcx>> {
58 ty.visit_with(&mut Search { tcx, span, seen: FxHashSet::default(), adt_const_param: true })
62 /// This method returns true if and only if `adt_ty` itself has been marked as
63 /// eligible for structural-match: namely, if it implements both
64 /// `StructuralPartialEq` and `StructuralEq` (which are respectively injected by
65 /// `#[derive(PartialEq)]` and `#[derive(Eq)]`).
67 /// Note that this does *not* recursively check if the substructure of `adt_ty`
68 /// implements the traits.
69 fn type_marked_structural<'tcx>(
70 infcx: &InferCtxt<'tcx>,
72 cause: ObligationCause<'tcx>,
74 let ocx = ObligationCtxt::new(infcx);
75 // require `#[derive(PartialEq)]`
76 let structural_peq_def_id =
77 infcx.tcx.require_lang_item(LangItem::StructuralPeq, Some(cause.span));
78 ocx.register_bound(cause.clone(), ty::ParamEnv::empty(), adt_ty, structural_peq_def_id);
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 structural_teq_def_id =
82 infcx.tcx.require_lang_item(LangItem::StructuralTeq, Some(cause.span));
83 ocx.register_bound(cause, ty::ParamEnv::empty(), adt_ty, structural_teq_def_id);
85 // We deliberately skip *reporting* fulfillment errors (via
86 // `report_fulfillment_errors`), for two reasons:
88 // 1. The error messages would mention `std::marker::StructuralPartialEq`
89 // (a trait which is solely meant as an implementation detail
92 // 2. We are sometimes doing future-incompatibility lints for
93 // now, so we do not want unconditional errors here.
94 ocx.select_all_or_error().is_empty()
97 /// This implements the traversal over the structure of a given type to try to
98 /// find instances of ADTs (specifically structs or enums) that do not implement
99 /// the structural-match traits (`StructuralPartialEq` and `StructuralEq`).
100 struct Search<'tcx> {
105 /// Tracks ADTs previously encountered during search, so that
106 /// we will not recur on them again.
107 seen: FxHashSet<hir::def_id::DefId>,
109 // Additionally deny things that have been allowed in patterns,
110 // but are not allowed in adt const params, such as floats and
112 adt_const_param: bool,
115 impl<'tcx> Search<'tcx> {
116 fn type_marked_structural(&self, adt_ty: Ty<'tcx>) -> bool {
117 adt_ty.is_structural_eq_shallow(self.tcx)
121 impl<'tcx> TypeVisitor<'tcx> for Search<'tcx> {
122 type BreakTy = Ty<'tcx>;
124 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
125 debug!("Search visiting ty: {:?}", ty);
127 let (adt_def, substs) = match *ty.kind() {
128 ty::Adt(adt_def, substs) => (adt_def, substs),
130 return ControlFlow::Break(ty);
133 return ControlFlow::Break(ty);
136 return ControlFlow::Break(ty);
139 return ControlFlow::Break(ty);
141 ty::Projection(..) => {
142 return ControlFlow::Break(ty);
145 return ControlFlow::Break(ty);
147 ty::Generator(..) | ty::GeneratorWitness(..) => {
148 return ControlFlow::Break(ty);
151 // Types of formals and return in `fn(_) -> _` are also irrelevant;
152 // so we do not recur into them via `super_visit_with`
153 return ControlFlow::CONTINUE;
156 if { n.try_eval_usize(self.tcx, ty::ParamEnv::reveal_all()) == Some(0) } =>
158 // rust-lang/rust#62336: ignore type of contents
160 return ControlFlow::CONTINUE;
162 ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Str | ty::Never => {
163 // These primitive types are always structural match.
165 // `Never` is kind of special here, but as it is not inhabitable, this should be fine.
166 return ControlFlow::CONTINUE;
170 if !self.adt_const_param {
171 return ControlFlow::CONTINUE;
173 return ControlFlow::Break(ty);
178 if !self.adt_const_param {
179 // structural-match ignores substructure of
180 // `*const _`/`*mut _`, so skip `super_visit_with`.
182 // For example, if you have:
184 // struct NonStructural;
185 // #[derive(PartialEq, Eq)]
186 // struct T(*const NonStructural);
187 // const C: T = T(std::ptr::null());
190 // Even though `NonStructural` does not implement `PartialEq`,
191 // structural equality on `T` does not recur into the raw
192 // pointer. Therefore, one can still use `C` in a pattern.
193 return ControlFlow::CONTINUE;
195 return ControlFlow::Break(ty);
200 if !self.adt_const_param {
201 return ControlFlow::CONTINUE;
203 return ControlFlow::Break(ty);
207 ty::Array(..) | ty::Slice(_) | ty::Ref(..) | ty::Tuple(..) => {
208 // First check all contained types and then tell the caller to continue searching.
209 return ty.super_visit_with(self);
211 ty::Infer(_) | ty::Placeholder(_) | ty::Bound(..) => {
212 bug!("unexpected type during structural-match checking: {:?}", ty);
215 self.tcx.sess.delay_span_bug(self.span, "ty::Error in structural-match check");
216 // We still want to check other types after encountering an error,
217 // as this may still emit relevant errors.
218 return ControlFlow::CONTINUE;
222 if !self.seen.insert(adt_def.did()) {
223 debug!("Search already seen adt_def: {:?}", adt_def);
224 return ControlFlow::CONTINUE;
227 if !self.type_marked_structural(ty) {
228 debug!("Search found ty: {:?}", ty);
229 return ControlFlow::Break(ty);
232 // structural-match does not care about the
233 // instantiation of the generics in an ADT (it
234 // instead looks directly at its fields outside
235 // this match), so we skip super_visit_with.
237 // (Must not recur on substs for `PhantomData<T>` cf
238 // rust-lang/rust#55028 and rust-lang/rust#55837; but also
239 // want to skip substs when only uses of generic are
240 // behind unsafe pointers `*const T`/`*mut T`.)
242 // even though we skip super_visit_with, we must recur on
245 adt_def.all_fields().map(|field| field.ty(tcx, substs)).try_for_each(|field_ty| {
246 let ty = self.tcx.normalize_erasing_regions(ty::ParamEnv::empty(), field_ty);
247 debug!("structural-match ADT: field_ty={:?}, ty={:?}", field_ty, ty);
253 pub fn provide(providers: &mut Providers) {
254 providers.has_structural_eq_impls = |tcx, ty| {
255 let infcx = tcx.infer_ctxt().build();
256 let cause = ObligationCause::dummy();
257 type_marked_structural(&infcx, ty, cause)