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::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)
})
}
}