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

use rustc_data_structures::fx::FxHashSet;
use rustc_hir as hir;
use rustc_middle::ty::{self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor};
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>(
    tcx: TyCtxt<'tcx>,
    ty: Ty<'tcx>,
) -> Option<Ty<'tcx>> {
    ty.visit_with(&mut Search { tcx, seen: FxHashSet::default() }).break_value()
}

/// 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
/// `StructuralPartialEq`.
struct Search<'tcx> {
    tcx: TyCtxt<'tcx>,

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

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<TyCtxt<'tcx>> for Search<'tcx> {
    type Result = ControlFlow<Ty<'tcx>>;

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

        let (adt_def, args) = match *ty.kind() {
            ty::Adt(adt_def, args) => (adt_def, args),
            ty::Param(_) => {
                return ControlFlow::Break(ty);
            }
            ty::Dynamic(..) => {
                return ControlFlow::Break(ty);
            }
            ty::Foreign(_) => {
                return ControlFlow::Break(ty);
            }
            ty::Alias(..) => {
                return ControlFlow::Break(ty);
            }
            ty::Closure(..) => {
                return ControlFlow::Break(ty);
            }
            ty::CoroutineClosure(..) => {
                return ControlFlow::Break(ty);
            }
            ty::Coroutine(..) | ty::CoroutineWitness(..) => {
                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_target_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(..) => {
                return ControlFlow::Continue(());
            }

            ty::RawPtr(..) => {
                // 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(());
            }

            ty::Float(_) => {
                return ControlFlow::Continue(());
            }

            ty::Pat(..) | 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(_) => {
                // 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 args for `PhantomData<T>` cf
        // rust-lang/rust#55028 and rust-lang/rust#55837; but also
        // want to skip args 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, args)).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)
        })
    }
}