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}
;
11 use std
::ops
::ControlFlow
;
14 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 ty
.visit_with(&mut Search { infcx, span, seen: FxHashSet::default() }
).break_value()
61 /// This method returns true if and only if `adt_ty` itself has been marked as
62 /// eligible for structural-match: namely, if it implements both
63 /// `StructuralPartialEq` and `StructuralEq` (which are respectively injected by
64 /// `#[derive(PartialEq)]` and `#[derive(Eq)]`).
66 /// Note that this does *not* recursively check if the substructure of `adt_ty`
67 /// implements the traits.
68 fn type_marked_structural(
69 infcx
: &InferCtxt
<'_
, 'tcx
>,
71 cause
: ObligationCause
<'tcx
>,
73 let mut fulfillment_cx
= traits
::FulfillmentContext
::new();
74 // require `#[derive(PartialEq)]`
75 let structural_peq_def_id
=
76 infcx
.tcx
.require_lang_item(LangItem
::StructuralPeq
, Some(cause
.span
));
77 fulfillment_cx
.register_bound(
79 ty
::ParamEnv
::empty(),
81 structural_peq_def_id
,
84 // for now, require `#[derive(Eq)]`. (Doing so is a hack to work around
85 // the type `for<'a> fn(&'a ())` failing to implement `Eq` itself.)
86 let structural_teq_def_id
=
87 infcx
.tcx
.require_lang_item(LangItem
::StructuralTeq
, Some(cause
.span
));
88 fulfillment_cx
.register_bound(
90 ty
::ParamEnv
::empty(),
92 structural_teq_def_id
,
96 // We deliberately skip *reporting* fulfillment errors (via
97 // `report_fulfillment_errors`), for two reasons:
99 // 1. The error messages would mention `std::marker::StructuralPartialEq`
100 // (a trait which is solely meant as an implementation detail
103 // 2. We are sometimes doing future-incompatibility lints for
104 // now, so we do not want unconditional errors here.
105 fulfillment_cx
.select_all_or_error(infcx
).is_ok()
108 /// This implements the traversal over the structure of a given type to try to
109 /// find instances of ADTs (specifically structs or enums) that do not implement
110 /// the structural-match traits (`StructuralPartialEq` and `StructuralEq`).
111 struct Search
<'a
, 'tcx
> {
114 infcx
: InferCtxt
<'a
, '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 adt_ty
.is_structural_eq_shallow(self.tcx())
131 impl<'a
, 'tcx
> TypeVisitor
<'tcx
> for Search
<'a
, 'tcx
> {
132 type BreakTy
= NonStructuralMatchTy
<'tcx
>;
133 fn tcx_for_anon_const_substs(&self) -> Option
<TyCtxt
<'tcx
>> {
137 fn visit_ty(&mut self, ty
: Ty
<'tcx
>) -> ControlFlow
<Self::BreakTy
> {
138 debug
!("Search visiting ty: {:?}", ty
);
140 let (adt_def
, substs
) = match *ty
.kind() {
141 ty
::Adt(adt_def
, substs
) => (adt_def
, substs
),
143 return ControlFlow
::Break(NonStructuralMatchTy
::Param
);
146 return ControlFlow
::Break(NonStructuralMatchTy
::Dynamic
);
149 return ControlFlow
::Break(NonStructuralMatchTy
::Foreign
);
152 return ControlFlow
::Break(NonStructuralMatchTy
::Opaque
);
154 ty
::Projection(..) => {
155 return ControlFlow
::Break(NonStructuralMatchTy
::Projection
);
157 ty
::Generator(..) | ty
::GeneratorWitness(..) => {
158 return ControlFlow
::Break(NonStructuralMatchTy
::Generator
);
161 // structural-match ignores substructure of
162 // `*const _`/`*mut _`, so skip `super_visit_with`.
164 // For example, if you have:
166 // struct NonStructural;
167 // #[derive(PartialEq, Eq)]
168 // struct T(*const NonStructural);
169 // const C: T = T(std::ptr::null());
172 // Even though `NonStructural` does not implement `PartialEq`,
173 // structural equality on `T` does not recur into the raw
174 // pointer. Therefore, one can still use `C` in a pattern.
175 return ControlFlow
::CONTINUE
;
177 ty
::FnDef(..) | ty
::FnPtr(..) => {
178 // Types of formals and return in `fn(_) -> _` are also irrelevant;
179 // so we do not recur into them via `super_visit_with`
180 return ControlFlow
::CONTINUE
;
183 if { n.try_eval_usize(self.tcx(), ty::ParamEnv::reveal_all()) == Some(0) }
=>
185 // rust-lang/rust#62336: ignore type of contents
187 return ControlFlow
::CONTINUE
;
189 ty
::Bool
| ty
::Char
| ty
::Int(_
) | ty
::Uint(_
) | ty
::Float(_
) | ty
::Str
| ty
::Never
=> {
190 // These primitive types are always structural match.
192 // `Never` is kind of special here, but as it is not inhabitable, this should be fine.
193 return ControlFlow
::CONTINUE
;
196 ty
::Array(..) | ty
::Slice(_
) | ty
::Ref(..) | ty
::Tuple(..) => {
197 // First check all contained types and then tell the caller to continue searching.
198 return ty
.super_visit_with(self);
200 ty
::Closure(..) | ty
::Infer(_
) | ty
::Placeholder(_
) | ty
::Bound(..) => {
201 bug
!("unexpected type during structural-match checking: {:?}", ty
);
204 self.tcx().sess
.delay_span_bug(self.span
, "ty::Error in structural-match check");
205 // We still want to check other types after encountering an error,
206 // as this may still emit relevant errors.
207 return ControlFlow
::CONTINUE
;
211 if !self.seen
.insert(adt_def
.did
) {
212 debug
!("Search already seen adt_def: {:?}", adt_def
);
213 return ControlFlow
::CONTINUE
;
216 if !self.type_marked_structural(ty
) {
217 debug
!("Search found ty: {:?}", ty
);
218 return ControlFlow
::Break(NonStructuralMatchTy
::Adt(&adt_def
));
221 // structural-match does not care about the
222 // instantiation of the generics in an ADT (it
223 // instead looks directly at its fields outside
224 // this match), so we skip super_visit_with.
226 // (Must not recur on substs for `PhantomData<T>` cf
227 // rust-lang/rust#55028 and rust-lang/rust#55837; but also
228 // want to skip substs when only uses of generic are
229 // behind unsafe pointers `*const T`/`*mut T`.)
231 // even though we skip super_visit_with, we must recur on
233 let tcx
= self.tcx();
234 adt_def
.all_fields().map(|field
| field
.ty(tcx
, substs
)).try_for_each(|field_ty
| {
235 let ty
= self.tcx().normalize_erasing_regions(ty
::ParamEnv
::empty(), field_ty
);
236 debug
!("structural-match ADT: field_ty={:?}, ty={:?}", field_ty
, ty
);
242 pub fn provide(providers
: &mut Providers
) {
243 providers
.has_structural_eq_impls
= |tcx
, ty
| {
244 tcx
.infer_ctxt().enter(|infcx
| {
245 let cause
= ObligationCause
::dummy();
246 type_marked_structural(&infcx
, ty
, cause
)