1 use crate::infer
::{InferCtxt, TyCtxtInferExt}
;
2 use crate::traits
::ObligationCause
;
3 use crate::traits
::{self, TraitEngine}
;
5 use rustc_data_structures
::fx
::FxHashSet
;
7 use rustc_hir
::lang_items
::LangItem
;
8 use rustc_middle
::ty
::query
::Providers
;
9 use rustc_middle
::ty
::{self, AdtDef, Ty, TyCtxt, TypeFoldable, TypeVisitor}
;
13 pub enum NonStructuralMatchTy
<'tcx
> {
24 /// This method traverses the structure of `ty`, trying to find an
25 /// instance of an ADT (i.e. struct or enum) that doesn't implement
26 /// the structural-match traits, or a generic type parameter
27 /// (which cannot be determined to be structural-match).
29 /// The "structure of a type" includes all components that would be
30 /// considered when doing a pattern match on a constant of that
33 /// * This means this method descends into fields of structs/enums,
34 /// and also descends into the inner type `T` of `&T` and `&mut T`
36 /// * The traversal doesn't dereference unsafe pointers (`*const T`,
37 /// `*mut T`), and it does not visit the type arguments of an
38 /// instantiated generic like `PhantomData<T>`.
40 /// The reason we do this search is Rust currently require all ADTs
41 /// reachable from a constant's type to implement the
42 /// structural-match traits, which essentially say that
43 /// the implementation of `PartialEq::eq` behaves *equivalently* to a
44 /// comparison against the unfolded structure.
46 /// For more background on why Rust has this requirement, and issues
47 /// that arose when the requirement was not enforced completely, see
48 /// Rust RFC 1445, rust-lang/rust#61188, and rust-lang/rust#62307.
49 pub fn search_for_structural_match_violation
<'tcx
>(
54 ) -> Option
<NonStructuralMatchTy
<'tcx
>> {
55 // FIXME: we should instead pass in an `infcx` from the outside.
56 tcx
.infer_ctxt().enter(|infcx
| {
57 let mut search
= Search { infcx, span, found: None, seen: FxHashSet::default() }
;
58 ty
.visit_with(&mut search
);
63 /// This method returns true if and only if `adt_ty` itself has been marked as
64 /// eligible for structural-match: namely, if it implements both
65 /// `StructuralPartialEq` and `StructuralEq` (which are respectively injected by
66 /// `#[derive(PartialEq)]` and `#[derive(Eq)]`).
68 /// Note that this does *not* recursively check if the substructure of `adt_ty`
69 /// implements the traits.
70 fn type_marked_structural(
71 infcx
: &InferCtxt
<'_
, 'tcx
>,
73 cause
: ObligationCause
<'tcx
>,
75 let mut fulfillment_cx
= traits
::FulfillmentContext
::new();
76 // require `#[derive(PartialEq)]`
77 let structural_peq_def_id
=
78 infcx
.tcx
.require_lang_item(LangItem
::StructuralPeq
, Some(cause
.span
));
79 fulfillment_cx
.register_bound(
81 ty
::ParamEnv
::empty(),
83 structural_peq_def_id
,
86 // for now, require `#[derive(Eq)]`. (Doing so is a hack to work around
87 // the type `for<'a> fn(&'a ())` failing to implement `Eq` itself.)
88 let structural_teq_def_id
=
89 infcx
.tcx
.require_lang_item(LangItem
::StructuralTeq
, Some(cause
.span
));
90 fulfillment_cx
.register_bound(
92 ty
::ParamEnv
::empty(),
94 structural_teq_def_id
,
98 // We deliberately skip *reporting* fulfillment errors (via
99 // `report_fulfillment_errors`), for two reasons:
101 // 1. The error messages would mention `std::marker::StructuralPartialEq`
102 // (a trait which is solely meant as an implementation detail
105 // 2. We are sometimes doing future-incompatibility lints for
106 // now, so we do not want unconditional errors here.
107 fulfillment_cx
.select_all_or_error(infcx
).is_ok()
110 /// This implements the traversal over the structure of a given type to try to
111 /// find instances of ADTs (specifically structs or enums) that do not implement
112 /// the structural-match traits (`StructuralPartialEq` and `StructuralEq`).
113 struct Search
<'a
, 'tcx
> {
116 infcx
: InferCtxt
<'a
, 'tcx
>,
118 /// Records first ADT that does not implement a structural-match trait.
119 found
: Option
<NonStructuralMatchTy
<'tcx
>>,
121 /// Tracks ADTs previously encountered during search, so that
122 /// we will not recur on them again.
123 seen
: FxHashSet
<hir
::def_id
::DefId
>,
126 impl Search
<'a
, 'tcx
> {
127 fn tcx(&self) -> TyCtxt
<'tcx
> {
131 fn type_marked_structural(&self, adt_ty
: Ty
<'tcx
>) -> bool
{
132 adt_ty
.is_structural_eq_shallow(self.tcx())
136 impl<'a
, 'tcx
> TypeVisitor
<'tcx
> for Search
<'a
, 'tcx
> {
137 fn visit_ty(&mut self, ty
: Ty
<'tcx
>) -> bool
{
138 debug
!("Search visiting ty: {:?}", ty
);
140 let (adt_def
, substs
) = match ty
.kind
{
141 ty
::Adt(adt_def
, substs
) => (adt_def
, substs
),
143 self.found
= Some(NonStructuralMatchTy
::Param
);
144 return true; // Stop visiting.
147 self.found
= Some(NonStructuralMatchTy
::Dynamic
);
148 return true; // Stop visiting.
151 self.found
= Some(NonStructuralMatchTy
::Foreign
);
152 return true; // Stop visiting.
155 self.found
= Some(NonStructuralMatchTy
::Opaque
);
156 return true; // Stop visiting.
158 ty
::Projection(..) => {
159 self.found
= Some(NonStructuralMatchTy
::Projection
);
160 return true; // Stop visiting.
162 ty
::Generator(..) | ty
::GeneratorWitness(..) => {
163 self.found
= Some(NonStructuralMatchTy
::Generator
);
164 return true; // Stop visiting.
167 self.found
= Some(NonStructuralMatchTy
::Closure
);
168 return true; // Stop visiting.
171 // structural-match ignores substructure of
172 // `*const _`/`*mut _`, so skip `super_visit_with`.
174 // For example, if you have:
176 // struct NonStructural;
177 // #[derive(PartialEq, Eq)]
178 // struct T(*const NonStructural);
179 // const C: T = T(std::ptr::null());
182 // Even though `NonStructural` does not implement `PartialEq`,
183 // structural equality on `T` does not recur into the raw
184 // pointer. Therefore, one can still use `C` in a pattern.
186 // (But still tell the caller to continue search.)
189 ty
::FnDef(..) | ty
::FnPtr(..) => {
190 // Types of formals and return in `fn(_) -> _` are also irrelevant;
191 // so we do not recur into them via `super_visit_with`
193 // (But still tell the caller to continue search.)
197 if { n.try_eval_usize(self.tcx(), ty::ParamEnv::reveal_all()) == Some(0) }
=>
199 // rust-lang/rust#62336: ignore type of contents
202 // (But still tell the caller to continue search.)
205 ty
::Bool
| ty
::Char
| ty
::Int(_
) | ty
::Uint(_
) | ty
::Float(_
) | ty
::Str
| ty
::Never
=> {
206 // These primitive types are always structural match.
208 // `Never` is kind of special here, but as it is not inhabitable, this should be fine.
210 // (But still tell the caller to continue search.)
214 ty
::Array(..) | ty
::Slice(_
) | ty
::Ref(..) | ty
::Tuple(..) => {
215 // First check all contained types and then tell the caller to continue searching.
216 ty
.super_visit_with(self);
219 ty
::Infer(_
) | ty
::Placeholder(_
) | ty
::Bound(..) => {
220 bug
!("unexpected type during structural-match checking: {:?}", ty
);
223 self.tcx().sess
.delay_span_bug(self.span
, "ty::Error in structural-match check");
224 // We still want to check other types after encountering an error,
225 // as this may still emit relevant errors.
227 // So we continue searching here.
232 if !self.seen
.insert(adt_def
.did
) {
233 debug
!("Search already seen adt_def: {:?}", adt_def
);
234 // Let caller continue its search.
238 if !self.type_marked_structural(ty
) {
239 debug
!("Search found ty: {:?}", ty
);
240 self.found
= Some(NonStructuralMatchTy
::Adt(&adt_def
));
241 return true; // Halt visiting!
244 // structural-match does not care about the
245 // instantiation of the generics in an ADT (it
246 // instead looks directly at its fields outside
247 // this match), so we skip super_visit_with.
249 // (Must not recur on substs for `PhantomData<T>` cf
250 // rust-lang/rust#55028 and rust-lang/rust#55837; but also
251 // want to skip substs when only uses of generic are
252 // behind unsafe pointers `*const T`/`*mut T`.)
254 // even though we skip super_visit_with, we must recur on
256 let tcx
= self.tcx();
257 for field_ty
in adt_def
.all_fields().map(|field
| field
.ty(tcx
, substs
)) {
258 let ty
= self.tcx().normalize_erasing_regions(ty
::ParamEnv
::empty(), field_ty
);
259 debug
!("structural-match ADT: field_ty={:?}, ty={:?}", field_ty
, ty
);
261 if ty
.visit_with(self) {
262 // found an ADT without structural-match; halt visiting!
263 assert
!(self.found
.is_some());
268 // Even though we do not want to recur on substs, we do
269 // want our caller to continue its own search.
274 pub fn provide(providers
: &mut Providers
) {
275 providers
.has_structural_eq_impls
= |tcx
, ty
| {
276 tcx
.infer_ctxt().enter(|infcx
| {
277 let cause
= ObligationCause
::dummy();
278 type_marked_structural(&infcx
, ty
, cause
)