[rustc.git] / src / librustc_trait_selection / traits / structural_match.rs

use crate::infer::{InferCtxt, TyCtxtInferExt};
use crate::traits::ObligationCause;
use crate::traits::{self, TraitEngine};

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, AdtDef, Ty, TyCtxt, TypeFoldable, TypeVisitor};
use rustc_span::Span;

#[derive(Debug)]
pub enum NonStructuralMatchTy<'tcx> {
    Adt(&'tcx AdtDef),
    Param,
    Dynamic,
    Foreign,
    Opaque,
    Generator,
    Projection,
    Closure,
}

/// 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>(
    _id: hir::HirId,
    span: Span,
    tcx: TyCtxt<'tcx>,
    ty: Ty<'tcx>,
) -> Option<NonStructuralMatchTy<'tcx>> {
    // FIXME: we should instead pass in an `infcx` from the outside.
    tcx.infer_ctxt().enter(|infcx| {
        let mut search = Search { infcx, span, found: None, seen: FxHashSet::default() };
        ty.visit_with(&mut search);
        search.found
    })
}

/// 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(
    infcx: &InferCtxt<'_, 'tcx>,
    adt_ty: Ty<'tcx>,
    cause: ObligationCause<'tcx>,
) -> bool {
    let mut fulfillment_cx = traits::FulfillmentContext::new();
    // 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_ok()
}

/// 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<'a, 'tcx> {
    span: Span,

    infcx: InferCtxt<'a, 'tcx>,

    /// Records first ADT that does not implement a structural-match trait.
    found: Option<NonStructuralMatchTy<'tcx>>,

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

impl Search<'a, 'tcx> {
    fn tcx(&self) -> TyCtxt<'tcx> {
        self.infcx.tcx
    }

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

impl<'a, 'tcx> TypeVisitor<'tcx> for Search<'a, 'tcx> {
    fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
        debug!("Search visiting ty: {:?}", ty);

        let (adt_def, substs) = match ty.kind {
            ty::Adt(adt_def, substs) => (adt_def, substs),
            ty::Param(_) => {
                self.found = Some(NonStructuralMatchTy::Param);
                return true; // Stop visiting.
            }
            ty::Dynamic(..) => {
                self.found = Some(NonStructuralMatchTy::Dynamic);
                return true; // Stop visiting.
            }
            ty::Foreign(_) => {
                self.found = Some(NonStructuralMatchTy::Foreign);
                return true; // Stop visiting.
            }
            ty::Opaque(..) => {
                self.found = Some(NonStructuralMatchTy::Opaque);
                return true; // Stop visiting.
            }
            ty::Projection(..) => {
                self.found = Some(NonStructuralMatchTy::Projection);
                return true; // Stop visiting.
            }
            ty::Generator(..) | ty::GeneratorWitness(..) => {
                self.found = Some(NonStructuralMatchTy::Generator);
                return true; // Stop visiting.
            }
            ty::Closure(..) => {
                self.found = Some(NonStructuralMatchTy::Closure);
                return true; // Stop visiting.
            }
            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.

                // (But still tell the caller to continue search.)
                return false;
            }
            ty::FnDef(..) | ty::FnPtr(..) => {
                // Types of formals and return in `fn(_) -> _` are also irrelevant;
                // so we do not recur into them via `super_visit_with`
                //
                // (But still tell the caller to continue search.)
                return false;
            }
            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.
                //
                // (But still tell the caller to continue search.)
                return false;
            }
            ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) | 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.
                //
                // (But still tell the caller to continue search.)
                return false;
            }

            ty::Array(..) | ty::Slice(_) | ty::Ref(..) | ty::Tuple(..) => {
                // First check all contained types and then tell the caller to continue searching.
                ty.super_visit_with(self);
                return false;
            }
            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.
                //
                // So we continue searching here.
                return false;
            }
        };

        if !self.seen.insert(adt_def.did) {
            debug!("Search already seen adt_def: {:?}", adt_def);
            // Let caller continue its search.
            return false;
        }

        if !self.type_marked_structural(ty) {
            debug!("Search found ty: {:?}", ty);
            self.found = Some(NonStructuralMatchTy::Adt(&adt_def));
            return true; // Halt visiting!
        }

        // 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();
        for field_ty in adt_def.all_fields().map(|field| field.ty(tcx, substs)) {
            let ty = self.tcx().normalize_erasing_regions(ty::ParamEnv::empty(), field_ty);
            debug!("structural-match ADT: field_ty={:?}, ty={:?}", field_ty, ty);

            if ty.visit_with(self) {
                // found an ADT without structural-match; halt visiting!
                assert!(self.found.is_some());
                return true;
            }
        }

        // Even though we do not want to recur on substs, we do
        // want our caller to continue its own search.
        false
    }
}

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)
        })
    };
}
Commit	Line	Data
74b04a01 XL	1	use crate::infer::{InferCtxt, TyCtxtInferExt};
74b04a01 XL	2	use crate::traits::ObligationCause;
f035d41b	3	use crate::traits::{self, TraitEngine};
dfeec247	4
dfeec247 XL	5	use rustc_data_structures::fx::FxHashSet;
dfeec247 XL	6	use rustc_hir as hir;
3dfed10e	7	use rustc_hir::lang_items::LangItem;
f035d41b	8	use rustc_middle::ty::query::Providers;
ba9703b0	9	use rustc_middle::ty::{self, AdtDef, Ty, TyCtxt, TypeFoldable, TypeVisitor};
dfeec247	10	use rustc_span::Span;
e74abb32 XL	11
	12	#[derive(Debug)]
	13	pub enum NonStructuralMatchTy<'tcx> {
	14	Adt(&'tcx AdtDef),
	15	Param,
f9f354fc XL	16	Dynamic,
	17	Foreign,
	18	Opaque,
	19	Generator,
	20	Projection,
f035d41b	21	Closure,
e74abb32 XL	22	}
	23
	24	/// This method traverses the structure of `ty`, trying to find an
ba9703b0 XL	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).
e74abb32 XL	28	///
	29	/// The "structure of a type" includes all components that would be
	30	/// considered when doing a pattern match on a constant of that
	31	/// type.
	32	///
	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`
	35	///
	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>`.
	39	///
	40	/// The reason we do this search is Rust currently require all ADTs
ba9703b0 XL	41	/// reachable from a constant's type to implement the
ba9703b0 XL	42	/// structural-match traits, which essentially say that
e74abb32 XL	43	/// the implementation of `PartialEq::eq` behaves equivalently to a
	44	/// comparison against the unfolded structure.
	45	///
	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>(
f035d41b	50	_id: hir::HirId,
e74abb32 XL	51	span: Span,
	52	tcx: TyCtxt<'tcx>,
	53	ty: Ty<'tcx>,
	54	) -> Option<NonStructuralMatchTy<'tcx>> {
	55	// FIXME: we should instead pass in an `infcx` from the outside.
	56	tcx.infer_ctxt().enter(\|infcx\| {
f035d41b	57	let mut search = Search { infcx, span, found: None, seen: FxHashSet::default() };
e74abb32 XL	58	ty.visit_with(&mut search);
	59	search.found
	60	})
	61	}
	62
	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)]`).
	67	///
	68	/// Note that this does not recursively check if the substructure of `adt_ty`
	69	/// implements the traits.
f035d41b	70	fn type_marked_structural(
dfeec247 XL	71	infcx: &InferCtxt<'_, 'tcx>,
dfeec247 XL	72	adt_ty: Ty<'tcx>,
f035d41b	73	cause: ObligationCause<'tcx>,
dfeec247	74	) -> bool {
e74abb32	75	let mut fulfillment_cx = traits::FulfillmentContext::new();
e74abb32	76	// require `#[derive(PartialEq)]`
f035d41b	77	let structural_peq_def_id =
3dfed10e	78	infcx.tcx.require_lang_item(LangItem::StructuralPeq, Some(cause.span));
e74abb32	79	fulfillment_cx.register_bound(
dfeec247 XL	80	infcx,
	81	ty::ParamEnv::empty(),
	82	adt_ty,
	83	structural_peq_def_id,
f035d41b	84	cause.clone(),
dfeec247	85	);
e74abb32 XL	86	// for now, require `#[derive(Eq)]`. (Doing so is a hack to work around
e74abb32 XL	87	// the type `for<'a> fn(&'a ())` failing to implement `Eq` itself.)
f035d41b	88	let structural_teq_def_id =
3dfed10e	89	infcx.tcx.require_lang_item(LangItem::StructuralTeq, Some(cause.span));
e74abb32	90	fulfillment_cx.register_bound(
dfeec247 XL	91	infcx,
	92	ty::ParamEnv::empty(),
	93	adt_ty,
	94	structural_teq_def_id,
	95	cause,
	96	);
e74abb32 XL	97
	98	// We deliberately skip reporting fulfillment errors (via
	99	// `report_fulfillment_errors`), for two reasons:
	100	//
	101	// 1. The error messages would mention `std::marker::StructuralPartialEq`
	102	// (a trait which is solely meant as an implementation detail
	103	// for now), and
	104	//
	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()
	108	}
	109
	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> {
e74abb32 XL	114	span: Span,
	115
	116	infcx: InferCtxt<'a, 'tcx>,
	117
	118	/// Records first ADT that does not implement a structural-match trait.
	119	found: Option<NonStructuralMatchTy<'tcx>>,
	120
	121	/// Tracks ADTs previously encountered during search, so that
	122	/// we will not recur on them again.
	123	seen: FxHashSet<hir::def_id::DefId>,
	124	}
	125
	126	impl Search<'a, 'tcx> {
	127	fn tcx(&self) -> TyCtxt<'tcx> {
	128	self.infcx.tcx
	129	}
	130
	131	fn type_marked_structural(&self, adt_ty: Ty<'tcx>) -> bool {
f035d41b	132	adt_ty.is_structural_eq_shallow(self.tcx())
e74abb32 XL	133	}
	134	}
	135
	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);
	139
	140	let (adt_def, substs) = match ty.kind {
	141	ty::Adt(adt_def, substs) => (adt_def, substs),
	142	ty::Param(_) => {
	143	self.found = Some(NonStructuralMatchTy::Param);
	144	return true; // Stop visiting.
	145	}
f9f354fc XL	146	ty::Dynamic(..) => {
	147	self.found = Some(NonStructuralMatchTy::Dynamic);
	148	return true; // Stop visiting.
	149	}
	150	ty::Foreign(_) => {
	151	self.found = Some(NonStructuralMatchTy::Foreign);
	152	return true; // Stop visiting.
	153	}
	154	ty::Opaque(..) => {
	155	self.found = Some(NonStructuralMatchTy::Opaque);
	156	return true; // Stop visiting.
	157	}
	158	ty::Projection(..) => {
	159	self.found = Some(NonStructuralMatchTy::Projection);
	160	return true; // Stop visiting.
	161	}
	162	ty::Generator(..) \| ty::GeneratorWitness(..) => {
	163	self.found = Some(NonStructuralMatchTy::Generator);
	164	return true; // Stop visiting.
	165	}
f035d41b XL	166	ty::Closure(..) => {
	167	self.found = Some(NonStructuralMatchTy::Closure);
	168	return true; // Stop visiting.
	169	}
e74abb32 XL	170	ty::RawPtr(..) => {
	171	// structural-match ignores substructure of
	172	// `const _`/`mut _`, so skip `super_visit_with`.
	173	//
	174	// For example, if you have:
	175	// ```
	176	// struct NonStructural;
	177	// #[derive(PartialEq, Eq)]
	178	// struct T(*const NonStructural);
	179	// const C: T = T(std::ptr::null());
	180	// ```
	181	//
	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.
	185
f9f354fc	186	// (But still tell the caller to continue search.)
e74abb32 XL	187	return false;
	188	}
	189	ty::FnDef(..) \| ty::FnPtr(..) => {
f9f354fc	190	// Types of formals and return in `fn(_) -> _` are also irrelevant;
e74abb32 XL	191	// so we do not recur into them via `super_visit_with`
e74abb32 XL	192	//
f9f354fc	193	// (But still tell the caller to continue search.)
e74abb32 XL	194	return false;
e74abb32 XL	195	}
dfeec247 XL	196	ty::Array(_, n)
	197	if { n.try_eval_usize(self.tcx(), ty::ParamEnv::reveal_all()) == Some(0) } =>
	198	{
e74abb32 XL	199	// rust-lang/rust#62336: ignore type of contents
e74abb32 XL	200	// for empty array.
f9f354fc XL	201	//
f9f354fc XL	202	// (But still tell the caller to continue search.)
e74abb32 XL	203	return false;
e74abb32 XL	204	}
f9f354fc XL	205	ty::Bool \| ty::Char \| ty::Int(_) \| ty::Uint(_) \| ty::Float(_) \| ty::Str \| ty::Never => {
	206	// These primitive types are always structural match.
	207	//
	208	// `Never` is kind of special here, but as it is not inhabitable, this should be fine.
	209	//
	210	// (But still tell the caller to continue search.)
	211	return false;
	212	}
	213
	214	ty::Array(..) \| ty::Slice(_) \| ty::Ref(..) \| ty::Tuple(..) => {
	215	// First check all contained types and then tell the caller to continue searching.
e74abb32 XL	216	ty.super_visit_with(self);
	217	return false;
	218	}
f035d41b	219	ty::Infer(_) \| ty::Placeholder(_) \| ty::Bound(..) => {
f9f354fc XL	220	bug!("unexpected type during structural-match checking: {:?}", ty);
f9f354fc XL	221	}
f035d41b	222	ty::Error(_) => {
f9f354fc XL	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.
	226	//
	227	// So we continue searching here.
	228	return false;
	229	}
e74abb32 XL	230	};
	231
	232	if !self.seen.insert(adt_def.did) {
	233	debug!("Search already seen adt_def: {:?}", adt_def);
f9f354fc	234	// Let caller continue its search.
e74abb32 XL	235	return false;
	236	}
	237
	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!
	242	}
	243
	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.
	248	//
	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`.)
	253
	254	// even though we skip super_visit_with, we must recur on
	255	// fields of ADT.
	256	let tcx = self.tcx();
	257	for field_ty in adt_def.all_fields().map(\|field\| field.ty(tcx, substs)) {
f9f354fc XL	258	let ty = self.tcx().normalize_erasing_regions(ty::ParamEnv::empty(), field_ty);
	259	debug!("structural-match ADT: field_ty={:?}, ty={:?}", field_ty, ty);
	260
	261	if ty.visit_with(self) {
e74abb32 XL	262	// found an ADT without structural-match; halt visiting!
	263	assert!(self.found.is_some());
	264	return true;
	265	}
	266	}
	267
	268	// Even though we do not want to recur on substs, we do
	269	// want our caller to continue its own search.
	270	false
	271	}
	272	}
f035d41b XL	273
	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)
	279	})
	280	};
	281	}