1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
use crate::infer::{InferCtxt, TyCtxtInferExt};
use crate::traits::ObligationCause;
use crate::traits::{TraitEngine, TraitEngineExt};

use rustc_data_structures::fx::FxHashSet;
use rustc_hir as hir;
use rustc_hir::lang_items::LangItem;
use rustc_middle::ty::query::Providers;
use rustc_middle::ty::{self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor};
use rustc_span::Span;
use std::ops::ControlFlow;

/// This method traverses the structure of `ty`, trying to find an
/// instance of an ADT (i.e. struct or enum) that doesn't implement
/// the structural-match traits, or a generic type parameter
/// (which cannot be determined to be structural-match).
///
/// The "structure of a type" includes all components that would be
/// considered when doing a pattern match on a constant of that
/// type.
///
///  * This means this method descends into fields of structs/enums,
///    and also descends into the inner type `T` of `&T` and `&mut T`
///
///  * The traversal doesn't dereference unsafe pointers (`*const T`,
///    `*mut T`), and it does not visit the type arguments of an
///    instantiated generic like `PhantomData<T>`.
///
/// The reason we do this search is Rust currently require all ADTs
/// reachable from a constant's type to implement the
/// structural-match traits, which essentially say that
/// the implementation of `PartialEq::eq` behaves *equivalently* to a
/// comparison against the unfolded structure.
///
/// For more background on why Rust has this requirement, and issues
/// that arose when the requirement was not enforced completely, see
/// Rust RFC 1445, rust-lang/rust#61188, and rust-lang/rust#62307.
pub fn search_for_structural_match_violation<'tcx>(
    span: Span,
    tcx: TyCtxt<'tcx>,
    ty: Ty<'tcx>,
) -> Option<Ty<'tcx>> {
    ty.visit_with(&mut Search { tcx, span, seen: FxHashSet::default(), adt_const_param: false })
        .break_value()
}

/// This method traverses the structure of `ty`, trying to find any
/// types that are not allowed to be used in a const generic.
///
/// This is either because the type does not implement `StructuralEq`
/// and `StructuralPartialEq`, or because the type is intentionally
/// not supported in const generics (such as floats and raw pointers,
/// which are allowed in match blocks).
pub fn search_for_adt_const_param_violation<'tcx>(
    span: Span,
    tcx: TyCtxt<'tcx>,
    ty: Ty<'tcx>,
) -> Option<Ty<'tcx>> {
    ty.visit_with(&mut Search { tcx, span, seen: FxHashSet::default(), adt_const_param: true })
        .break_value()
}

/// This method returns true if and only if `adt_ty` itself has been marked as
/// eligible for structural-match: namely, if it implements both
/// `StructuralPartialEq` and `StructuralEq` (which are respectively injected by
/// `#[derive(PartialEq)]` and `#[derive(Eq)]`).
///
/// Note that this does *not* recursively check if the substructure of `adt_ty`
/// implements the traits.
fn type_marked_structural<'tcx>(
    infcx: &InferCtxt<'_, 'tcx>,
    adt_ty: Ty<'tcx>,
    cause: ObligationCause<'tcx>,
) -> bool {
    let mut fulfillment_cx = <dyn TraitEngine<'tcx>>::new(infcx.tcx);
    // require `#[derive(PartialEq)]`
    let structural_peq_def_id =
        infcx.tcx.require_lang_item(LangItem::StructuralPeq, Some(cause.span));
    fulfillment_cx.register_bound(
        infcx,
        ty::ParamEnv::empty(),
        adt_ty,
        structural_peq_def_id,
        cause.clone(),
    );
    // for now, require `#[derive(Eq)]`. (Doing so is a hack to work around
    // the type `for<'a> fn(&'a ())` failing to implement `Eq` itself.)
    let structural_teq_def_id =
        infcx.tcx.require_lang_item(LangItem::StructuralTeq, Some(cause.span));
    fulfillment_cx.register_bound(
        infcx,
        ty::ParamEnv::empty(),
        adt_ty,
        structural_teq_def_id,
        cause,
    );

    // We deliberately skip *reporting* fulfillment errors (via
    // `report_fulfillment_errors`), for two reasons:
    //
    // 1. The error messages would mention `std::marker::StructuralPartialEq`
    //    (a trait which is solely meant as an implementation detail
    //    for now), and
    //
    // 2. We are sometimes doing future-incompatibility lints for
    //    now, so we do not want unconditional errors here.
    fulfillment_cx.select_all_or_error(infcx).is_empty()
}

/// This implements the traversal over the structure of a given type to try to
/// find instances of ADTs (specifically structs or enums) that do not implement
/// the structural-match traits (`StructuralPartialEq` and `StructuralEq`).
struct Search<'tcx> {
    span: Span,

    tcx: TyCtxt<'tcx>,

    /// Tracks ADTs previously encountered during search, so that
    /// we will not recur on them again.
    seen: FxHashSet<hir::def_id::DefId>,

    // Additionally deny things that have been allowed in patterns,
    // but are not allowed in adt const params, such as floats and
    // fn ptrs.
    adt_const_param: bool,
}

impl<'tcx> Search<'tcx> {
    fn type_marked_structural(&self, adt_ty: Ty<'tcx>) -> bool {
        adt_ty.is_structural_eq_shallow(self.tcx)
    }
}

impl<'tcx> TypeVisitor<'tcx> for Search<'tcx> {
    type BreakTy = Ty<'tcx>;

    fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
        debug!("Search visiting ty: {:?}", ty);

        let (adt_def, substs) = match *ty.kind() {
            ty::Adt(adt_def, substs) => (adt_def, substs),
            ty::Param(_) => {
                return ControlFlow::Break(ty);
            }
            ty::Dynamic(..) => {
                return ControlFlow::Break(ty);
            }
            ty::Foreign(_) => {
                return ControlFlow::Break(ty);
            }
            ty::Opaque(..) => {
                return ControlFlow::Break(ty);
            }
            ty::Projection(..) => {
                return ControlFlow::Break(ty);
            }
            ty::Closure(..) => {
                return ControlFlow::Break(ty);
            }
            ty::Generator(..) | ty::GeneratorWitness(..) => {
                return ControlFlow::Break(ty);
            }
            ty::FnDef(..) => {
                // Types of formals and return in `fn(_) -> _` are also irrelevant;
                // so we do not recur into them via `super_visit_with`
                return ControlFlow::CONTINUE;
            }
            ty::Array(_, n)
                if { n.try_eval_usize(self.tcx, ty::ParamEnv::reveal_all()) == Some(0) } =>
            {
                // rust-lang/rust#62336: ignore type of contents
                // for empty array.
                return ControlFlow::CONTINUE;
            }
            ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Str | ty::Never => {
                // These primitive types are always structural match.
                //
                // `Never` is kind of special here, but as it is not inhabitable, this should be fine.
                return ControlFlow::CONTINUE;
            }

            ty::FnPtr(..) => {
                if !self.adt_const_param {
                    return ControlFlow::CONTINUE;
                } else {
                    return ControlFlow::Break(ty);
                }
            }

            ty::RawPtr(..) => {
                if !self.adt_const_param {
                    // structural-match ignores substructure of
                    // `*const _`/`*mut _`, so skip `super_visit_with`.
                    //
                    // For example, if you have:
                    // ```
                    // struct NonStructural;
                    // #[derive(PartialEq, Eq)]
                    // struct T(*const NonStructural);
                    // const C: T = T(std::ptr::null());
                    // ```
                    //
                    // Even though `NonStructural` does not implement `PartialEq`,
                    // structural equality on `T` does not recur into the raw
                    // pointer. Therefore, one can still use `C` in a pattern.
                    return ControlFlow::CONTINUE;
                } else {
                    return ControlFlow::Break(ty);
                }
            }

            ty::Float(_) => {
                if !self.adt_const_param {
                    return ControlFlow::CONTINUE;
                } else {
                    return ControlFlow::Break(ty);
                }
            }

            ty::Array(..) | ty::Slice(_) | ty::Ref(..) | ty::Tuple(..) => {
                // First check all contained types and then tell the caller to continue searching.
                return ty.super_visit_with(self);
            }
            ty::Infer(_) | ty::Placeholder(_) | ty::Bound(..) => {
                bug!("unexpected type during structural-match checking: {:?}", ty);
            }
            ty::Error(_) => {
                self.tcx.sess.delay_span_bug(self.span, "ty::Error in structural-match check");
                // We still want to check other types after encountering an error,
                // as this may still emit relevant errors.
                return ControlFlow::CONTINUE;
            }
        };

        if !self.seen.insert(adt_def.did()) {
            debug!("Search already seen adt_def: {:?}", adt_def);
            return ControlFlow::CONTINUE;
        }

        if !self.type_marked_structural(ty) {
            debug!("Search found ty: {:?}", ty);
            return ControlFlow::Break(ty);
        }

        // structural-match does not care about the
        // instantiation of the generics in an ADT (it
        // instead looks directly at its fields outside
        // this match), so we skip super_visit_with.
        //
        // (Must not recur on substs for `PhantomData<T>` cf
        // rust-lang/rust#55028 and rust-lang/rust#55837; but also
        // want to skip substs when only uses of generic are
        // behind unsafe pointers `*const T`/`*mut T`.)

        // even though we skip super_visit_with, we must recur on
        // fields of ADT.
        let tcx = self.tcx;
        adt_def.all_fields().map(|field| field.ty(tcx, substs)).try_for_each(|field_ty| {
            let ty = self.tcx.normalize_erasing_regions(ty::ParamEnv::empty(), field_ty);
            debug!("structural-match ADT: field_ty={:?}, ty={:?}", field_ty, ty);
            ty.visit_with(self)
        })
    }
}

pub fn provide(providers: &mut Providers) {
    providers.has_structural_eq_impls = |tcx, ty| {
        tcx.infer_ctxt().enter(|infcx| {
            let cause = ObligationCause::dummy();
            type_marked_structural(&infcx, ty, cause)
        })
    };
}