From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_typeck/src/coherence/builtin.rs | 603 +++++++++++++++++++++ .../rustc_typeck/src/coherence/inherent_impls.rs | 249 +++++++++ .../src/coherence/inherent_impls_overlap.rs | 307 +++++++++++ compiler/rustc_typeck/src/coherence/mod.rs | 237 ++++++++ compiler/rustc_typeck/src/coherence/orphan.rs | 507 +++++++++++++++++ compiler/rustc_typeck/src/coherence/unsafety.rs | 66 +++ 6 files changed, 1969 insertions(+) create mode 100644 compiler/rustc_typeck/src/coherence/builtin.rs create mode 100644 compiler/rustc_typeck/src/coherence/inherent_impls.rs create mode 100644 compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs create mode 100644 compiler/rustc_typeck/src/coherence/mod.rs create mode 100644 compiler/rustc_typeck/src/coherence/orphan.rs create mode 100644 compiler/rustc_typeck/src/coherence/unsafety.rs (limited to 'compiler/rustc_typeck/src/coherence') diff --git a/compiler/rustc_typeck/src/coherence/builtin.rs b/compiler/rustc_typeck/src/coherence/builtin.rs new file mode 100644 index 000000000..50946cc1d --- /dev/null +++ b/compiler/rustc_typeck/src/coherence/builtin.rs @@ -0,0 +1,603 @@ +//! Check properties that are required by built-in traits and set +//! up data structures required by type-checking/codegen. + +use crate::errors::{CopyImplOnNonAdt, CopyImplOnTypeWithDtor, DropImplOnWrongItem}; +use rustc_errors::{struct_span_err, MultiSpan}; +use rustc_hir as hir; +use rustc_hir::def_id::{DefId, LocalDefId}; +use rustc_hir::lang_items::LangItem; +use rustc_hir::ItemKind; +use rustc_infer::infer; +use rustc_infer::infer::outlives::env::OutlivesEnvironment; +use rustc_infer::infer::TyCtxtInferExt; +use rustc_middle::ty::adjustment::CoerceUnsizedInfo; +use rustc_middle::ty::{self, suggest_constraining_type_params, Ty, TyCtxt, TypeVisitable}; +use rustc_trait_selection::traits::error_reporting::InferCtxtExt; +use rustc_trait_selection::traits::misc::{can_type_implement_copy, CopyImplementationError}; +use rustc_trait_selection::traits::predicate_for_trait_def; +use rustc_trait_selection::traits::{self, ObligationCause, TraitEngine, TraitEngineExt}; +use std::collections::BTreeMap; + +pub fn check_trait(tcx: TyCtxt<'_>, trait_def_id: DefId) { + let lang_items = tcx.lang_items(); + Checker { tcx, trait_def_id } + .check(lang_items.drop_trait(), visit_implementation_of_drop) + .check(lang_items.copy_trait(), visit_implementation_of_copy) + .check(lang_items.coerce_unsized_trait(), visit_implementation_of_coerce_unsized) + .check(lang_items.dispatch_from_dyn_trait(), visit_implementation_of_dispatch_from_dyn); +} + +struct Checker<'tcx> { + tcx: TyCtxt<'tcx>, + trait_def_id: DefId, +} + +impl<'tcx> Checker<'tcx> { + fn check(&self, trait_def_id: Option, mut f: F) -> &Self + where + F: FnMut(TyCtxt<'tcx>, LocalDefId), + { + if Some(self.trait_def_id) == trait_def_id { + for &impl_def_id in self.tcx.hir().trait_impls(self.trait_def_id) { + f(self.tcx, impl_def_id); + } + } + self + } +} + +fn visit_implementation_of_drop(tcx: TyCtxt<'_>, impl_did: LocalDefId) { + // Destructors only work on nominal types. + if let ty::Adt(..) | ty::Error(_) = tcx.type_of(impl_did).kind() { + return; + } + + let sp = match tcx.hir().expect_item(impl_did).kind { + ItemKind::Impl(ref impl_) => impl_.self_ty.span, + _ => bug!("expected Drop impl item"), + }; + + tcx.sess.emit_err(DropImplOnWrongItem { span: sp }); +} + +fn visit_implementation_of_copy(tcx: TyCtxt<'_>, impl_did: LocalDefId) { + debug!("visit_implementation_of_copy: impl_did={:?}", impl_did); + + let impl_hir_id = tcx.hir().local_def_id_to_hir_id(impl_did); + + let self_type = tcx.type_of(impl_did); + debug!("visit_implementation_of_copy: self_type={:?} (bound)", self_type); + + let span = tcx.hir().span(impl_hir_id); + let param_env = tcx.param_env(impl_did); + assert!(!self_type.has_escaping_bound_vars()); + + debug!("visit_implementation_of_copy: self_type={:?} (free)", self_type); + + let cause = traits::ObligationCause::misc(span, impl_hir_id); + match can_type_implement_copy(tcx, param_env, self_type, cause) { + Ok(()) => {} + Err(CopyImplementationError::InfrigingFields(fields)) => { + let item = tcx.hir().expect_item(impl_did); + let span = if let ItemKind::Impl(hir::Impl { of_trait: Some(ref tr), .. }) = item.kind { + tr.path.span + } else { + span + }; + + let mut err = struct_span_err!( + tcx.sess, + span, + E0204, + "the trait `Copy` may not be implemented for this type" + ); + + // We'll try to suggest constraining type parameters to fulfill the requirements of + // their `Copy` implementation. + let mut errors: BTreeMap<_, Vec<_>> = Default::default(); + let mut bounds = vec![]; + + for (field, ty) in fields { + let field_span = tcx.def_span(field.did); + let field_ty_span = match tcx.hir().get_if_local(field.did) { + Some(hir::Node::Field(field_def)) => field_def.ty.span, + _ => field_span, + }; + err.span_label(field_span, "this field does not implement `Copy`"); + // Spin up a new FulfillmentContext, so we can get the _precise_ reason + // why this field does not implement Copy. This is useful because sometimes + // it is not immediately clear why Copy is not implemented for a field, since + // all we point at is the field itself. + tcx.infer_ctxt().ignoring_regions().enter(|infcx| { + let mut fulfill_cx = >::new(tcx); + fulfill_cx.register_bound( + &infcx, + param_env, + ty, + tcx.lang_items().copy_trait().unwrap(), + traits::ObligationCause::dummy_with_span(field_ty_span), + ); + for error in fulfill_cx.select_all_or_error(&infcx) { + let error_predicate = error.obligation.predicate; + // Only note if it's not the root obligation, otherwise it's trivial and + // should be self-explanatory (i.e. a field literally doesn't implement Copy). + + // FIXME: This error could be more descriptive, especially if the error_predicate + // contains a foreign type or if it's a deeply nested type... + if error_predicate != error.root_obligation.predicate { + errors + .entry((ty.to_string(), error_predicate.to_string())) + .or_default() + .push(error.obligation.cause.span); + } + if let ty::PredicateKind::Trait(ty::TraitPredicate { + trait_ref, + polarity: ty::ImplPolarity::Positive, + .. + }) = error_predicate.kind().skip_binder() + { + let ty = trait_ref.self_ty(); + if let ty::Param(_) = ty.kind() { + bounds.push(( + format!("{ty}"), + trait_ref.print_only_trait_path().to_string(), + Some(trait_ref.def_id), + )); + } + } + } + }); + } + for ((ty, error_predicate), spans) in errors { + let span: MultiSpan = spans.into(); + err.span_note( + span, + &format!("the `Copy` impl for `{}` requires that `{}`", ty, error_predicate), + ); + } + suggest_constraining_type_params( + tcx, + tcx.hir().get_generics(impl_did).expect("impls always have generics"), + &mut err, + bounds.iter().map(|(param, constraint, def_id)| { + (param.as_str(), constraint.as_str(), *def_id) + }), + ); + err.emit(); + } + Err(CopyImplementationError::NotAnAdt) => { + let item = tcx.hir().expect_item(impl_did); + let span = + if let ItemKind::Impl(ref impl_) = item.kind { impl_.self_ty.span } else { span }; + + tcx.sess.emit_err(CopyImplOnNonAdt { span }); + } + Err(CopyImplementationError::HasDestructor) => { + tcx.sess.emit_err(CopyImplOnTypeWithDtor { span }); + } + } +} + +fn visit_implementation_of_coerce_unsized<'tcx>(tcx: TyCtxt<'tcx>, impl_did: LocalDefId) { + debug!("visit_implementation_of_coerce_unsized: impl_did={:?}", impl_did); + + // Just compute this for the side-effects, in particular reporting + // errors; other parts of the code may demand it for the info of + // course. + let span = tcx.def_span(impl_did); + tcx.at(span).coerce_unsized_info(impl_did); +} + +fn visit_implementation_of_dispatch_from_dyn<'tcx>(tcx: TyCtxt<'tcx>, impl_did: LocalDefId) { + debug!("visit_implementation_of_dispatch_from_dyn: impl_did={:?}", impl_did); + + let impl_hir_id = tcx.hir().local_def_id_to_hir_id(impl_did); + let span = tcx.hir().span(impl_hir_id); + + let dispatch_from_dyn_trait = tcx.require_lang_item(LangItem::DispatchFromDyn, Some(span)); + + let source = tcx.type_of(impl_did); + assert!(!source.has_escaping_bound_vars()); + let target = { + let trait_ref = tcx.impl_trait_ref(impl_did).unwrap(); + assert_eq!(trait_ref.def_id, dispatch_from_dyn_trait); + + trait_ref.substs.type_at(1) + }; + + debug!("visit_implementation_of_dispatch_from_dyn: {:?} -> {:?}", source, target); + + let param_env = tcx.param_env(impl_did); + + let create_err = |msg: &str| struct_span_err!(tcx.sess, span, E0378, "{}", msg); + + tcx.infer_ctxt().enter(|infcx| { + let cause = ObligationCause::misc(span, impl_hir_id); + + use rustc_type_ir::sty::TyKind::*; + match (source.kind(), target.kind()) { + (&Ref(r_a, _, mutbl_a), Ref(r_b, _, mutbl_b)) + if infcx.at(&cause, param_env).eq(r_a, *r_b).is_ok() && mutbl_a == *mutbl_b => {} + (&RawPtr(tm_a), &RawPtr(tm_b)) if tm_a.mutbl == tm_b.mutbl => (), + (&Adt(def_a, substs_a), &Adt(def_b, substs_b)) + if def_a.is_struct() && def_b.is_struct() => + { + if def_a != def_b { + let source_path = tcx.def_path_str(def_a.did()); + let target_path = tcx.def_path_str(def_b.did()); + + create_err(&format!( + "the trait `DispatchFromDyn` may only be implemented \ + for a coercion between structures with the same \ + definition; expected `{}`, found `{}`", + source_path, target_path, + )) + .emit(); + + return; + } + + if def_a.repr().c() || def_a.repr().packed() { + create_err( + "structs implementing `DispatchFromDyn` may not have \ + `#[repr(packed)]` or `#[repr(C)]`", + ) + .emit(); + } + + let fields = &def_a.non_enum_variant().fields; + + let coerced_fields = fields + .iter() + .filter(|field| { + let ty_a = field.ty(tcx, substs_a); + let ty_b = field.ty(tcx, substs_b); + + if let Ok(layout) = tcx.layout_of(param_env.and(ty_a)) { + if layout.is_zst() && layout.align.abi.bytes() == 1 { + // ignore ZST fields with alignment of 1 byte + return false; + } + } + + if let Ok(ok) = infcx.at(&cause, param_env).eq(ty_a, ty_b) { + if ok.obligations.is_empty() { + create_err( + "the trait `DispatchFromDyn` may only be implemented \ + for structs containing the field being coerced, \ + ZST fields with 1 byte alignment, and nothing else", + ) + .note(&format!( + "extra field `{}` of type `{}` is not allowed", + field.name, ty_a, + )) + .emit(); + + return false; + } + } + + return true; + }) + .collect::>(); + + if coerced_fields.is_empty() { + create_err( + "the trait `DispatchFromDyn` may only be implemented \ + for a coercion between structures with a single field \ + being coerced, none found", + ) + .emit(); + } else if coerced_fields.len() > 1 { + create_err( + "implementing the `DispatchFromDyn` trait requires multiple coercions", + ) + .note( + "the trait `DispatchFromDyn` may only be implemented \ + for a coercion between structures with a single field \ + being coerced", + ) + .note(&format!( + "currently, {} fields need coercions: {}", + coerced_fields.len(), + coerced_fields + .iter() + .map(|field| { + format!( + "`{}` (`{}` to `{}`)", + field.name, + field.ty(tcx, substs_a), + field.ty(tcx, substs_b), + ) + }) + .collect::>() + .join(", ") + )) + .emit(); + } else { + let mut fulfill_cx = >::new(infcx.tcx); + + for field in coerced_fields { + let predicate = predicate_for_trait_def( + tcx, + param_env, + cause.clone(), + dispatch_from_dyn_trait, + 0, + field.ty(tcx, substs_a), + &[field.ty(tcx, substs_b).into()], + ); + + fulfill_cx.register_predicate_obligation(&infcx, predicate); + } + + // Check that all transitive obligations are satisfied. + let errors = fulfill_cx.select_all_or_error(&infcx); + if !errors.is_empty() { + infcx.report_fulfillment_errors(&errors, None, false); + } + + // Finally, resolve all regions. + let outlives_env = OutlivesEnvironment::new(param_env); + infcx.check_region_obligations_and_report_errors(impl_did, &outlives_env); + } + } + _ => { + create_err( + "the trait `DispatchFromDyn` may only be implemented \ + for a coercion between structures", + ) + .emit(); + } + } + }) +} + +pub fn coerce_unsized_info<'tcx>(tcx: TyCtxt<'tcx>, impl_did: DefId) -> CoerceUnsizedInfo { + debug!("compute_coerce_unsized_info(impl_did={:?})", impl_did); + + // this provider should only get invoked for local def-ids + let impl_did = impl_did.expect_local(); + let span = tcx.def_span(impl_did); + + let coerce_unsized_trait = tcx.require_lang_item(LangItem::CoerceUnsized, Some(span)); + + let unsize_trait = tcx.lang_items().require(LangItem::Unsize).unwrap_or_else(|err| { + tcx.sess.fatal(&format!("`CoerceUnsized` implementation {}", err)); + }); + + let source = tcx.type_of(impl_did); + let trait_ref = tcx.impl_trait_ref(impl_did).unwrap(); + assert_eq!(trait_ref.def_id, coerce_unsized_trait); + let target = trait_ref.substs.type_at(1); + debug!("visit_implementation_of_coerce_unsized: {:?} -> {:?} (bound)", source, target); + + let param_env = tcx.param_env(impl_did); + assert!(!source.has_escaping_bound_vars()); + + let err_info = CoerceUnsizedInfo { custom_kind: None }; + + debug!("visit_implementation_of_coerce_unsized: {:?} -> {:?} (free)", source, target); + + tcx.infer_ctxt().enter(|infcx| { + let impl_hir_id = tcx.hir().local_def_id_to_hir_id(impl_did); + let cause = ObligationCause::misc(span, impl_hir_id); + let check_mutbl = |mt_a: ty::TypeAndMut<'tcx>, + mt_b: ty::TypeAndMut<'tcx>, + mk_ptr: &dyn Fn(Ty<'tcx>) -> Ty<'tcx>| { + if (mt_a.mutbl, mt_b.mutbl) == (hir::Mutability::Not, hir::Mutability::Mut) { + infcx + .report_mismatched_types( + &cause, + mk_ptr(mt_b.ty), + target, + ty::error::TypeError::Mutability, + ) + .emit(); + } + (mt_a.ty, mt_b.ty, unsize_trait, None) + }; + let (source, target, trait_def_id, kind) = match (source.kind(), target.kind()) { + (&ty::Ref(r_a, ty_a, mutbl_a), &ty::Ref(r_b, ty_b, mutbl_b)) => { + infcx.sub_regions(infer::RelateObjectBound(span), r_b, r_a); + let mt_a = ty::TypeAndMut { ty: ty_a, mutbl: mutbl_a }; + let mt_b = ty::TypeAndMut { ty: ty_b, mutbl: mutbl_b }; + check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ref(r_b, ty)) + } + + (&ty::Ref(_, ty_a, mutbl_a), &ty::RawPtr(mt_b)) => { + let mt_a = ty::TypeAndMut { ty: ty_a, mutbl: mutbl_a }; + check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ptr(ty)) + } + + (&ty::RawPtr(mt_a), &ty::RawPtr(mt_b)) => { + check_mutbl(mt_a, mt_b, &|ty| tcx.mk_imm_ptr(ty)) + } + + (&ty::Adt(def_a, substs_a), &ty::Adt(def_b, substs_b)) + if def_a.is_struct() && def_b.is_struct() => + { + if def_a != def_b { + let source_path = tcx.def_path_str(def_a.did()); + let target_path = tcx.def_path_str(def_b.did()); + struct_span_err!( + tcx.sess, + span, + E0377, + "the trait `CoerceUnsized` may only be implemented \ + for a coercion between structures with the same \ + definition; expected `{}`, found `{}`", + source_path, + target_path + ) + .emit(); + return err_info; + } + + // Here we are considering a case of converting + // `S` to S`. As an example, let's imagine a struct `Foo`, + // which acts like a pointer to `U`, but carries along some extra data of type `T`: + // + // struct Foo { + // extra: T, + // ptr: *mut U, + // } + // + // We might have an impl that allows (e.g.) `Foo` to be unsized + // to `Foo`. That impl would look like: + // + // impl, V> CoerceUnsized> for Foo {} + // + // Here `U = [i32; 3]` and `V = [i32]`. At runtime, + // when this coercion occurs, we would be changing the + // field `ptr` from a thin pointer of type `*mut [i32; + // 3]` to a fat pointer of type `*mut [i32]` (with + // extra data `3`). **The purpose of this check is to + // make sure that we know how to do this conversion.** + // + // To check if this impl is legal, we would walk down + // the fields of `Foo` and consider their types with + // both substitutes. We are looking to find that + // exactly one (non-phantom) field has changed its + // type, which we will expect to be the pointer that + // is becoming fat (we could probably generalize this + // to multiple thin pointers of the same type becoming + // fat, but we don't). In this case: + // + // - `extra` has type `T` before and type `T` after + // - `ptr` has type `*mut U` before and type `*mut V` after + // + // Since just one field changed, we would then check + // that `*mut U: CoerceUnsized<*mut V>` is implemented + // (in other words, that we know how to do this + // conversion). This will work out because `U: + // Unsize`, and we have a builtin rule that `*mut + // U` can be coerced to `*mut V` if `U: Unsize`. + let fields = &def_a.non_enum_variant().fields; + let diff_fields = fields + .iter() + .enumerate() + .filter_map(|(i, f)| { + let (a, b) = (f.ty(tcx, substs_a), f.ty(tcx, substs_b)); + + if tcx.type_of(f.did).is_phantom_data() { + // Ignore PhantomData fields + return None; + } + + // Ignore fields that aren't changed; it may + // be that we could get away with subtyping or + // something more accepting, but we use + // equality because we want to be able to + // perform this check without computing + // variance where possible. (This is because + // we may have to evaluate constraint + // expressions in the course of execution.) + // See e.g., #41936. + if let Ok(ok) = infcx.at(&cause, param_env).eq(a, b) { + if ok.obligations.is_empty() { + return None; + } + } + + // Collect up all fields that were significantly changed + // i.e., those that contain T in coerce_unsized T -> U + Some((i, a, b)) + }) + .collect::>(); + + if diff_fields.is_empty() { + struct_span_err!( + tcx.sess, + span, + E0374, + "the trait `CoerceUnsized` may only be implemented \ + for a coercion between structures with one field \ + being coerced, none found" + ) + .emit(); + return err_info; + } else if diff_fields.len() > 1 { + let item = tcx.hir().expect_item(impl_did); + let span = if let ItemKind::Impl(hir::Impl { of_trait: Some(ref t), .. }) = + item.kind + { + t.path.span + } else { + tcx.def_span(impl_did) + }; + + struct_span_err!( + tcx.sess, + span, + E0375, + "implementing the trait \ + `CoerceUnsized` requires multiple \ + coercions" + ) + .note( + "`CoerceUnsized` may only be implemented for \ + a coercion between structures with one field being coerced", + ) + .note(&format!( + "currently, {} fields need coercions: {}", + diff_fields.len(), + diff_fields + .iter() + .map(|&(i, a, b)| { + format!("`{}` (`{}` to `{}`)", fields[i].name, a, b) + }) + .collect::>() + .join(", ") + )) + .span_label(span, "requires multiple coercions") + .emit(); + return err_info; + } + + let (i, a, b) = diff_fields[0]; + let kind = ty::adjustment::CustomCoerceUnsized::Struct(i); + (a, b, coerce_unsized_trait, Some(kind)) + } + + _ => { + struct_span_err!( + tcx.sess, + span, + E0376, + "the trait `CoerceUnsized` may only be implemented \ + for a coercion between structures" + ) + .emit(); + return err_info; + } + }; + + let mut fulfill_cx = >::new(infcx.tcx); + + // Register an obligation for `A: Trait`. + let cause = traits::ObligationCause::misc(span, impl_hir_id); + let predicate = predicate_for_trait_def( + tcx, + param_env, + cause, + trait_def_id, + 0, + source, + &[target.into()], + ); + fulfill_cx.register_predicate_obligation(&infcx, predicate); + + // Check that all transitive obligations are satisfied. + let errors = fulfill_cx.select_all_or_error(&infcx); + if !errors.is_empty() { + infcx.report_fulfillment_errors(&errors, None, false); + } + + // Finally, resolve all regions. + let outlives_env = OutlivesEnvironment::new(param_env); + infcx.check_region_obligations_and_report_errors(impl_did, &outlives_env); + + CoerceUnsizedInfo { custom_kind: kind } + }) +} diff --git a/compiler/rustc_typeck/src/coherence/inherent_impls.rs b/compiler/rustc_typeck/src/coherence/inherent_impls.rs new file mode 100644 index 000000000..52aad636f --- /dev/null +++ b/compiler/rustc_typeck/src/coherence/inherent_impls.rs @@ -0,0 +1,249 @@ +//! The code in this module gathers up all of the inherent impls in +//! the current crate and organizes them in a map. It winds up +//! touching the whole crate and thus must be recomputed completely +//! for any change, but it is very cheap to compute. In practice, most +//! code in the compiler never *directly* requests this map. Instead, +//! it requests the inherent impls specific to some type (via +//! `tcx.inherent_impls(def_id)`). That value, however, +//! is computed by selecting an idea from this table. + +use rustc_errors::struct_span_err; +use rustc_hir as hir; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::{CrateNum, DefId, LocalDefId}; +use rustc_middle::ty::fast_reject::{simplify_type, SimplifiedType, TreatParams}; +use rustc_middle::ty::{self, CrateInherentImpls, Ty, TyCtxt}; +use rustc_span::symbol::sym; +use rustc_span::Span; + +/// On-demand query: yields a map containing all types mapped to their inherent impls. +pub fn crate_inherent_impls(tcx: TyCtxt<'_>, (): ()) -> CrateInherentImpls { + let mut collect = InherentCollect { tcx, impls_map: Default::default() }; + for id in tcx.hir().items() { + collect.check_item(id); + } + collect.impls_map +} + +pub fn crate_incoherent_impls(tcx: TyCtxt<'_>, (_, simp): (CrateNum, SimplifiedType)) -> &[DefId] { + let crate_map = tcx.crate_inherent_impls(()); + tcx.arena.alloc_from_iter( + crate_map.incoherent_impls.get(&simp).unwrap_or(&Vec::new()).iter().map(|d| d.to_def_id()), + ) +} + +/// On-demand query: yields a vector of the inherent impls for a specific type. +pub fn inherent_impls(tcx: TyCtxt<'_>, ty_def_id: DefId) -> &[DefId] { + let ty_def_id = ty_def_id.expect_local(); + + let crate_map = tcx.crate_inherent_impls(()); + match crate_map.inherent_impls.get(&ty_def_id) { + Some(v) => &v[..], + None => &[], + } +} + +struct InherentCollect<'tcx> { + tcx: TyCtxt<'tcx>, + impls_map: CrateInherentImpls, +} + +const INTO_CORE: &str = "consider moving this inherent impl into `core` if possible"; +const INTO_DEFINING_CRATE: &str = + "consider moving this inherent impl into the crate defining the type if possible"; +const ADD_ATTR_TO_TY: &str = "alternatively add `#[rustc_has_incoherent_inherent_impls]` to the type \ + and `#[rustc_allow_incoherent_impl]` to the relevant impl items"; +const ADD_ATTR: &str = + "alternatively add `#[rustc_allow_incoherent_impl]` to the relevant impl items"; + +impl<'tcx> InherentCollect<'tcx> { + fn check_def_id(&mut self, item: &hir::Item<'_>, self_ty: Ty<'tcx>, def_id: DefId) { + let impl_def_id = item.def_id; + if let Some(def_id) = def_id.as_local() { + // Add the implementation to the mapping from implementation to base + // type def ID, if there is a base type for this implementation and + // the implementation does not have any associated traits. + let vec = self.impls_map.inherent_impls.entry(def_id).or_default(); + vec.push(impl_def_id.to_def_id()); + return; + } + + if self.tcx.features().rustc_attrs { + let hir::ItemKind::Impl(&hir::Impl { items, .. }) = item.kind else { + bug!("expected `impl` item: {:?}", item); + }; + + if !self.tcx.has_attr(def_id, sym::rustc_has_incoherent_inherent_impls) { + struct_span_err!( + self.tcx.sess, + item.span, + E0390, + "cannot define inherent `impl` for a type outside of the crate where the type is defined", + ) + .help(INTO_DEFINING_CRATE) + .span_help(item.span, ADD_ATTR_TO_TY) + .emit(); + return; + } + + for impl_item in items { + if !self + .tcx + .has_attr(impl_item.id.def_id.to_def_id(), sym::rustc_allow_incoherent_impl) + { + struct_span_err!( + self.tcx.sess, + item.span, + E0390, + "cannot define inherent `impl` for a type outside of the crate where the type is defined", + ) + .help(INTO_DEFINING_CRATE) + .span_help(impl_item.span, ADD_ATTR) + .emit(); + return; + } + } + + if let Some(simp) = simplify_type(self.tcx, self_ty, TreatParams::AsInfer) { + self.impls_map.incoherent_impls.entry(simp).or_default().push(impl_def_id); + } else { + bug!("unexpected self type: {:?}", self_ty); + } + } else { + struct_span_err!( + self.tcx.sess, + item.span, + E0116, + "cannot define inherent `impl` for a type outside of the crate \ + where the type is defined" + ) + .span_label(item.span, "impl for type defined outside of crate.") + .note("define and implement a trait or new type instead") + .emit(); + } + } + + fn check_primitive_impl( + &mut self, + impl_def_id: LocalDefId, + ty: Ty<'tcx>, + items: &[hir::ImplItemRef], + span: Span, + ) { + if !self.tcx.hir().rustc_coherence_is_core() { + if self.tcx.features().rustc_attrs { + for item in items { + if !self + .tcx + .has_attr(item.id.def_id.to_def_id(), sym::rustc_allow_incoherent_impl) + { + struct_span_err!( + self.tcx.sess, + span, + E0390, + "cannot define inherent `impl` for primitive types outside of `core`", + ) + .help(INTO_CORE) + .span_help(item.span, ADD_ATTR) + .emit(); + return; + } + } + } else { + let mut err = struct_span_err!( + self.tcx.sess, + span, + E0390, + "cannot define inherent `impl` for primitive types", + ); + err.help("consider using an extension trait instead"); + if let ty::Ref(_, subty, _) = ty.kind() { + err.note(&format!( + "you could also try moving the reference to \ + uses of `{}` (such as `self`) within the implementation", + subty + )); + } + err.emit(); + return; + } + } + + if let Some(simp) = simplify_type(self.tcx, ty, TreatParams::AsInfer) { + self.impls_map.incoherent_impls.entry(simp).or_default().push(impl_def_id); + } else { + bug!("unexpected primitive type: {:?}", ty); + } + } + + fn check_item(&mut self, id: hir::ItemId) { + if !matches!(self.tcx.def_kind(id.def_id), DefKind::Impl) { + return; + } + + let item = self.tcx.hir().item(id); + let hir::ItemKind::Impl(hir::Impl { of_trait: None, self_ty: ty, ref items, .. }) = item.kind else { + return; + }; + + let self_ty = self.tcx.type_of(item.def_id); + match *self_ty.kind() { + ty::Adt(def, _) => { + self.check_def_id(item, self_ty, def.did()); + } + ty::Foreign(did) => { + self.check_def_id(item, self_ty, did); + } + ty::Dynamic(data, ..) if data.principal_def_id().is_some() => { + self.check_def_id(item, self_ty, data.principal_def_id().unwrap()); + } + ty::Dynamic(..) => { + struct_span_err!( + self.tcx.sess, + ty.span, + E0785, + "cannot define inherent `impl` for a dyn auto trait" + ) + .span_label(ty.span, "impl requires at least one non-auto trait") + .note("define and implement a new trait or type instead") + .emit(); + } + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Str + | ty::Array(..) + | ty::Slice(_) + | ty::RawPtr(_) + | ty::Ref(..) + | ty::Never + | ty::FnPtr(_) + | ty::Tuple(..) => self.check_primitive_impl(item.def_id, self_ty, items, ty.span), + ty::Projection(..) | ty::Opaque(..) | ty::Param(_) => { + let mut err = struct_span_err!( + self.tcx.sess, + ty.span, + E0118, + "no nominal type found for inherent implementation" + ); + + err.span_label(ty.span, "impl requires a nominal type") + .note("either implement a trait on it or create a newtype to wrap it instead"); + + err.emit(); + } + ty::FnDef(..) + | ty::Closure(..) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::Bound(..) + | ty::Placeholder(_) + | ty::Infer(_) => { + bug!("unexpected impl self type of impl: {:?} {:?}", item.def_id, self_ty); + } + ty::Error(_) => {} + } + } +} diff --git a/compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs b/compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs new file mode 100644 index 000000000..03e076bf5 --- /dev/null +++ b/compiler/rustc_typeck/src/coherence/inherent_impls_overlap.rs @@ -0,0 +1,307 @@ +use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use rustc_errors::struct_span_err; +use rustc_hir as hir; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::DefId; +use rustc_index::vec::IndexVec; +use rustc_middle::traits::specialization_graph::OverlapMode; +use rustc_middle::ty::{self, TyCtxt}; +use rustc_span::Symbol; +use rustc_trait_selection::traits::{self, SkipLeakCheck}; +use smallvec::SmallVec; +use std::collections::hash_map::Entry; + +pub fn crate_inherent_impls_overlap_check(tcx: TyCtxt<'_>, (): ()) { + let mut inherent_overlap_checker = InherentOverlapChecker { tcx }; + for id in tcx.hir().items() { + inherent_overlap_checker.check_item(id); + } +} + +struct InherentOverlapChecker<'tcx> { + tcx: TyCtxt<'tcx>, +} + +impl<'tcx> InherentOverlapChecker<'tcx> { + /// Checks whether any associated items in impls 1 and 2 share the same identifier and + /// namespace. + fn impls_have_common_items( + &self, + impl_items1: &ty::AssocItems<'_>, + impl_items2: &ty::AssocItems<'_>, + ) -> bool { + let mut impl_items1 = &impl_items1; + let mut impl_items2 = &impl_items2; + + // Performance optimization: iterate over the smaller list + if impl_items1.len() > impl_items2.len() { + std::mem::swap(&mut impl_items1, &mut impl_items2); + } + + for item1 in impl_items1.in_definition_order() { + let collision = impl_items2 + .filter_by_name_unhygienic(item1.name) + .any(|item2| self.compare_hygienically(item1, item2)); + + if collision { + return true; + } + } + + false + } + + fn compare_hygienically(&self, item1: &ty::AssocItem, item2: &ty::AssocItem) -> bool { + // Symbols and namespace match, compare hygienically. + item1.kind.namespace() == item2.kind.namespace() + && item1.ident(self.tcx).normalize_to_macros_2_0() + == item2.ident(self.tcx).normalize_to_macros_2_0() + } + + fn check_for_common_items_in_impls( + &self, + impl1: DefId, + impl2: DefId, + overlap: traits::OverlapResult<'_>, + ) { + let impl_items1 = self.tcx.associated_items(impl1); + let impl_items2 = self.tcx.associated_items(impl2); + + for item1 in impl_items1.in_definition_order() { + let collision = impl_items2 + .filter_by_name_unhygienic(item1.name) + .find(|item2| self.compare_hygienically(item1, item2)); + + if let Some(item2) = collision { + let name = item1.ident(self.tcx).normalize_to_macros_2_0(); + let mut err = struct_span_err!( + self.tcx.sess, + self.tcx.def_span(item1.def_id), + E0592, + "duplicate definitions with name `{}`", + name + ); + err.span_label( + self.tcx.def_span(item1.def_id), + format!("duplicate definitions for `{}`", name), + ); + err.span_label( + self.tcx.def_span(item2.def_id), + format!("other definition for `{}`", name), + ); + + for cause in &overlap.intercrate_ambiguity_causes { + cause.add_intercrate_ambiguity_hint(&mut err); + } + + if overlap.involves_placeholder { + traits::add_placeholder_note(&mut err); + } + + err.emit(); + } + } + } + + fn check_for_overlapping_inherent_impls( + &self, + overlap_mode: OverlapMode, + impl1_def_id: DefId, + impl2_def_id: DefId, + ) { + traits::overlapping_impls( + self.tcx, + impl1_def_id, + impl2_def_id, + // We go ahead and just skip the leak check for + // inherent impls without warning. + SkipLeakCheck::Yes, + overlap_mode, + |overlap| { + self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id, overlap); + false + }, + || true, + ); + } + + fn check_item(&mut self, id: hir::ItemId) { + let def_kind = self.tcx.def_kind(id.def_id); + if !matches!(def_kind, DefKind::Enum | DefKind::Struct | DefKind::Trait | DefKind::Union) { + return; + } + + let impls = self.tcx.inherent_impls(id.def_id); + + // If there is only one inherent impl block, + // there is nothing to overlap check it with + if impls.len() <= 1 { + return; + } + + let overlap_mode = OverlapMode::get(self.tcx, id.def_id.to_def_id()); + + let impls_items = impls + .iter() + .map(|impl_def_id| (impl_def_id, self.tcx.associated_items(*impl_def_id))) + .collect::>(); + + // Perform a O(n^2) algorithm for small n, + // otherwise switch to an allocating algorithm with + // faster asymptotic runtime. + const ALLOCATING_ALGO_THRESHOLD: usize = 500; + if impls.len() < ALLOCATING_ALGO_THRESHOLD { + for (i, &(&impl1_def_id, impl_items1)) in impls_items.iter().enumerate() { + for &(&impl2_def_id, impl_items2) in &impls_items[(i + 1)..] { + if self.impls_have_common_items(impl_items1, impl_items2) { + self.check_for_overlapping_inherent_impls( + overlap_mode, + impl1_def_id, + impl2_def_id, + ); + } + } + } + } else { + // Build a set of connected regions of impl blocks. + // Two impl blocks are regarded as connected if they share + // an item with the same unhygienic identifier. + // After we have assembled the connected regions, + // run the O(n^2) algorithm on each connected region. + // This is advantageous to running the algorithm over the + // entire graph when there are many connected regions. + + rustc_index::newtype_index! { + pub struct RegionId { + ENCODABLE = custom + } + } + struct ConnectedRegion { + idents: SmallVec<[Symbol; 8]>, + impl_blocks: FxHashSet, + } + let mut connected_regions: IndexVec = Default::default(); + // Reverse map from the Symbol to the connected region id. + let mut connected_region_ids = FxHashMap::default(); + + for (i, &(&_impl_def_id, impl_items)) in impls_items.iter().enumerate() { + if impl_items.len() == 0 { + continue; + } + // First obtain a list of existing connected region ids + let mut idents_to_add = SmallVec::<[Symbol; 8]>::new(); + let mut ids = impl_items + .in_definition_order() + .filter_map(|item| { + let entry = connected_region_ids.entry(item.name); + if let Entry::Occupied(e) = &entry { + Some(*e.get()) + } else { + idents_to_add.push(item.name); + None + } + }) + .collect::>(); + // Sort the id list so that the algorithm is deterministic + ids.sort_unstable(); + ids.dedup(); + let ids = ids; + match &ids[..] { + // Create a new connected region + [] => { + let id_to_set = connected_regions.next_index(); + // Update the connected region ids + for ident in &idents_to_add { + connected_region_ids.insert(*ident, id_to_set); + } + connected_regions.insert( + id_to_set, + ConnectedRegion { + idents: idents_to_add, + impl_blocks: std::iter::once(i).collect(), + }, + ); + } + // Take the only id inside the list + &[id_to_set] => { + let region = connected_regions[id_to_set].as_mut().unwrap(); + region.impl_blocks.insert(i); + region.idents.extend_from_slice(&idents_to_add); + // Update the connected region ids + for ident in &idents_to_add { + connected_region_ids.insert(*ident, id_to_set); + } + } + // We have multiple connected regions to merge. + // In the worst case this might add impl blocks + // one by one and can thus be O(n^2) in the size + // of the resulting final connected region, but + // this is no issue as the final step to check + // for overlaps runs in O(n^2) as well. + &[id_to_set, ..] => { + let mut region = connected_regions.remove(id_to_set).unwrap(); + region.impl_blocks.insert(i); + region.idents.extend_from_slice(&idents_to_add); + // Update the connected region ids + for ident in &idents_to_add { + connected_region_ids.insert(*ident, id_to_set); + } + + // Remove other regions from ids. + for &id in ids.iter() { + if id == id_to_set { + continue; + } + let r = connected_regions.remove(id).unwrap(); + for ident in r.idents.iter() { + connected_region_ids.insert(*ident, id_to_set); + } + region.idents.extend_from_slice(&r.idents); + region.impl_blocks.extend(r.impl_blocks); + } + + connected_regions.insert(id_to_set, region); + } + } + } + + debug!( + "churning through {} components (sum={}, avg={}, var={}, max={})", + connected_regions.len(), + impls.len(), + impls.len() / connected_regions.len(), + { + let avg = impls.len() / connected_regions.len(); + let s = connected_regions + .iter() + .flatten() + .map(|r| r.impl_blocks.len() as isize - avg as isize) + .map(|v| v.abs() as usize) + .sum::(); + s / connected_regions.len() + }, + connected_regions.iter().flatten().map(|r| r.impl_blocks.len()).max().unwrap() + ); + // List of connected regions is built. Now, run the overlap check + // for each pair of impl blocks in the same connected region. + for region in connected_regions.into_iter().flatten() { + let mut impl_blocks = + region.impl_blocks.into_iter().collect::>(); + impl_blocks.sort_unstable(); + for (i, &impl1_items_idx) in impl_blocks.iter().enumerate() { + let &(&impl1_def_id, impl_items1) = &impls_items[impl1_items_idx]; + for &impl2_items_idx in impl_blocks[(i + 1)..].iter() { + let &(&impl2_def_id, impl_items2) = &impls_items[impl2_items_idx]; + if self.impls_have_common_items(impl_items1, impl_items2) { + self.check_for_overlapping_inherent_impls( + overlap_mode, + impl1_def_id, + impl2_def_id, + ); + } + } + } + } + } + } +} diff --git a/compiler/rustc_typeck/src/coherence/mod.rs b/compiler/rustc_typeck/src/coherence/mod.rs new file mode 100644 index 000000000..ae9ebe590 --- /dev/null +++ b/compiler/rustc_typeck/src/coherence/mod.rs @@ -0,0 +1,237 @@ +// Coherence phase +// +// The job of the coherence phase of typechecking is to ensure that +// each trait has at most one implementation for each type. This is +// done by the orphan and overlap modules. Then we build up various +// mappings. That mapping code resides here. + +use rustc_errors::struct_span_err; +use rustc_hir::def_id::{DefId, LocalDefId}; +use rustc_middle::ty::query::Providers; +use rustc_middle::ty::{self, TyCtxt, TypeVisitable}; +use rustc_trait_selection::traits; + +mod builtin; +mod inherent_impls; +mod inherent_impls_overlap; +mod orphan; +mod unsafety; + +fn check_impl(tcx: TyCtxt<'_>, impl_def_id: LocalDefId, trait_ref: ty::TraitRef<'_>) { + debug!( + "(checking implementation) adding impl for trait '{:?}', item '{}'", + trait_ref, + tcx.def_path_str(impl_def_id.to_def_id()) + ); + + // Skip impls where one of the self type is an error type. + // This occurs with e.g., resolve failures (#30589). + if trait_ref.references_error() { + return; + } + + enforce_trait_manually_implementable(tcx, impl_def_id, trait_ref.def_id); + enforce_empty_impls_for_marker_traits(tcx, impl_def_id, trait_ref.def_id); +} + +fn enforce_trait_manually_implementable( + tcx: TyCtxt<'_>, + impl_def_id: LocalDefId, + trait_def_id: DefId, +) { + let did = Some(trait_def_id); + let li = tcx.lang_items(); + let impl_header_span = tcx.def_span(impl_def_id); + + // Disallow *all* explicit impls of `Pointee`, `DiscriminantKind`, `Sized` and `Unsize` for now. + if did == li.pointee_trait() { + struct_span_err!( + tcx.sess, + impl_header_span, + E0322, + "explicit impls for the `Pointee` trait are not permitted" + ) + .span_label(impl_header_span, "impl of `Pointee` not allowed") + .emit(); + return; + } + + if did == li.discriminant_kind_trait() { + struct_span_err!( + tcx.sess, + impl_header_span, + E0322, + "explicit impls for the `DiscriminantKind` trait are not permitted" + ) + .span_label(impl_header_span, "impl of `DiscriminantKind` not allowed") + .emit(); + return; + } + + if did == li.sized_trait() { + struct_span_err!( + tcx.sess, + impl_header_span, + E0322, + "explicit impls for the `Sized` trait are not permitted" + ) + .span_label(impl_header_span, "impl of `Sized` not allowed") + .emit(); + return; + } + + if did == li.unsize_trait() { + struct_span_err!( + tcx.sess, + impl_header_span, + E0328, + "explicit impls for the `Unsize` trait are not permitted" + ) + .span_label(impl_header_span, "impl of `Unsize` not allowed") + .emit(); + return; + } + + if tcx.features().unboxed_closures { + // the feature gate allows all Fn traits + return; + } + + if let ty::trait_def::TraitSpecializationKind::AlwaysApplicable = + tcx.trait_def(trait_def_id).specialization_kind + { + if !tcx.features().specialization && !tcx.features().min_specialization { + tcx.sess + .struct_span_err( + impl_header_span, + "implementing `rustc_specialization_trait` traits is unstable", + ) + .help("add `#![feature(min_specialization)]` to the crate attributes to enable") + .emit(); + return; + } + } +} + +/// We allow impls of marker traits to overlap, so they can't override impls +/// as that could make it ambiguous which associated item to use. +fn enforce_empty_impls_for_marker_traits( + tcx: TyCtxt<'_>, + impl_def_id: LocalDefId, + trait_def_id: DefId, +) { + if !tcx.trait_def(trait_def_id).is_marker { + return; + } + + if tcx.associated_item_def_ids(trait_def_id).is_empty() { + return; + } + + struct_span_err!( + tcx.sess, + tcx.def_span(impl_def_id), + E0715, + "impls for marker traits cannot contain items" + ) + .emit(); +} + +pub fn provide(providers: &mut Providers) { + use self::builtin::coerce_unsized_info; + use self::inherent_impls::{crate_incoherent_impls, crate_inherent_impls, inherent_impls}; + use self::inherent_impls_overlap::crate_inherent_impls_overlap_check; + use self::orphan::orphan_check_impl; + + *providers = Providers { + coherent_trait, + crate_inherent_impls, + crate_incoherent_impls, + inherent_impls, + crate_inherent_impls_overlap_check, + coerce_unsized_info, + orphan_check_impl, + ..*providers + }; +} + +fn coherent_trait(tcx: TyCtxt<'_>, def_id: DefId) { + // Trigger building the specialization graph for the trait. This will detect and report any + // overlap errors. + tcx.ensure().specialization_graph_of(def_id); + + let impls = tcx.hir().trait_impls(def_id); + for &impl_def_id in impls { + let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + + check_impl(tcx, impl_def_id, trait_ref); + check_object_overlap(tcx, impl_def_id, trait_ref); + + tcx.sess.time("unsafety_checking", || unsafety::check_item(tcx, impl_def_id)); + tcx.sess.time("orphan_checking", || tcx.ensure().orphan_check_impl(impl_def_id)); + } + + builtin::check_trait(tcx, def_id); +} + +/// Checks whether an impl overlaps with the automatic `impl Trait for dyn Trait`. +fn check_object_overlap<'tcx>( + tcx: TyCtxt<'tcx>, + impl_def_id: LocalDefId, + trait_ref: ty::TraitRef<'tcx>, +) { + let trait_def_id = trait_ref.def_id; + + if trait_ref.references_error() { + debug!("coherence: skipping impl {:?} with error {:?}", impl_def_id, trait_ref); + return; + } + + // check for overlap with the automatic `impl Trait for dyn Trait` + if let ty::Dynamic(data, ..) = trait_ref.self_ty().kind() { + // This is something like impl Trait1 for Trait2. Illegal + // if Trait1 is a supertrait of Trait2 or Trait2 is not object safe. + + let component_def_ids = data.iter().flat_map(|predicate| { + match predicate.skip_binder() { + ty::ExistentialPredicate::Trait(tr) => Some(tr.def_id), + ty::ExistentialPredicate::AutoTrait(def_id) => Some(def_id), + // An associated type projection necessarily comes with + // an additional `Trait` requirement. + ty::ExistentialPredicate::Projection(..) => None, + } + }); + + for component_def_id in component_def_ids { + if !tcx.is_object_safe(component_def_id) { + // Without the 'object_safe_for_dispatch' feature this is an error + // which will be reported by wfcheck. Ignore it here. + // This is tested by `coherence-impl-trait-for-trait-object-safe.rs`. + // With the feature enabled, the trait is not implemented automatically, + // so this is valid. + } else { + let mut supertrait_def_ids = traits::supertrait_def_ids(tcx, component_def_id); + if supertrait_def_ids.any(|d| d == trait_def_id) { + let span = tcx.def_span(impl_def_id); + struct_span_err!( + tcx.sess, + span, + E0371, + "the object type `{}` automatically implements the trait `{}`", + trait_ref.self_ty(), + tcx.def_path_str(trait_def_id) + ) + .span_label( + span, + format!( + "`{}` automatically implements trait `{}`", + trait_ref.self_ty(), + tcx.def_path_str(trait_def_id) + ), + ) + .emit(); + } + } + } + } +} diff --git a/compiler/rustc_typeck/src/coherence/orphan.rs b/compiler/rustc_typeck/src/coherence/orphan.rs new file mode 100644 index 000000000..1608550aa --- /dev/null +++ b/compiler/rustc_typeck/src/coherence/orphan.rs @@ -0,0 +1,507 @@ +//! Orphan checker: every impl either implements a trait defined in this +//! crate or pertains to a type defined in this crate. + +use rustc_data_structures::fx::FxHashSet; +use rustc_errors::struct_span_err; +use rustc_errors::{Diagnostic, ErrorGuaranteed}; +use rustc_hir as hir; +use rustc_infer::infer::TyCtxtInferExt; +use rustc_middle::ty::subst::GenericArgKind; +use rustc_middle::ty::subst::InternalSubsts; +use rustc_middle::ty::util::IgnoreRegions; +use rustc_middle::ty::{ + self, ImplPolarity, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor, +}; +use rustc_session::lint; +use rustc_span::def_id::{DefId, LocalDefId}; +use rustc_span::Span; +use rustc_trait_selection::traits; +use std::ops::ControlFlow; + +#[instrument(skip(tcx), level = "debug")] +pub(crate) fn orphan_check_impl( + tcx: TyCtxt<'_>, + impl_def_id: LocalDefId, +) -> Result<(), ErrorGuaranteed> { + let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + if let Some(err) = trait_ref.error_reported() { + return Err(err); + } + + let ret = do_orphan_check_impl(tcx, trait_ref, impl_def_id); + if tcx.trait_is_auto(trait_ref.def_id) { + lint_auto_trait_impl(tcx, trait_ref, impl_def_id); + } + + ret +} + +fn do_orphan_check_impl<'tcx>( + tcx: TyCtxt<'tcx>, + trait_ref: ty::TraitRef<'tcx>, + def_id: LocalDefId, +) -> Result<(), ErrorGuaranteed> { + let trait_def_id = trait_ref.def_id; + + let item = tcx.hir().item(hir::ItemId { def_id }); + let hir::ItemKind::Impl(ref impl_) = item.kind else { + bug!("{:?} is not an impl: {:?}", def_id, item); + }; + let sp = tcx.def_span(def_id); + let tr = impl_.of_trait.as_ref().unwrap(); + + // Ensure no opaque types are present in this impl header. See issues #76202 and #86411 for examples, + // and #84660 where it would otherwise allow unsoundness. + if trait_ref.has_opaque_types() { + trace!("{:#?}", item); + // First we find the opaque type in question. + for ty in trait_ref.substs { + for ty in ty.walk() { + let ty::subst::GenericArgKind::Type(ty) = ty.unpack() else { continue }; + let ty::Opaque(def_id, _) = *ty.kind() else { continue }; + trace!(?def_id); + + // Then we search for mentions of the opaque type's type alias in the HIR + struct SpanFinder<'tcx> { + sp: Span, + def_id: DefId, + tcx: TyCtxt<'tcx>, + } + impl<'v, 'tcx> hir::intravisit::Visitor<'v> for SpanFinder<'tcx> { + #[instrument(level = "trace", skip(self, _id))] + fn visit_path(&mut self, path: &'v hir::Path<'v>, _id: hir::HirId) { + // You can't mention an opaque type directly, so we look for type aliases + if let hir::def::Res::Def(hir::def::DefKind::TyAlias, def_id) = path.res { + // And check if that type alias's type contains the opaque type we're looking for + for arg in self.tcx.type_of(def_id).walk() { + if let GenericArgKind::Type(ty) = arg.unpack() { + if let ty::Opaque(def_id, _) = *ty.kind() { + if def_id == self.def_id { + // Finally we update the span to the mention of the type alias + self.sp = path.span; + return; + } + } + } + } + } + hir::intravisit::walk_path(self, path) + } + } + + let mut visitor = SpanFinder { sp, def_id, tcx }; + hir::intravisit::walk_item(&mut visitor, item); + let reported = tcx + .sess + .struct_span_err(visitor.sp, "cannot implement trait on type alias impl trait") + .span_note(tcx.def_span(def_id), "type alias impl trait defined here") + .emit(); + return Err(reported); + } + } + span_bug!(sp, "opaque type not found, but `has_opaque_types` is set") + } + + match traits::orphan_check(tcx, item.def_id.to_def_id()) { + Ok(()) => {} + Err(err) => emit_orphan_check_error( + tcx, + sp, + item.span, + tr.path.span, + trait_ref.self_ty(), + impl_.self_ty.span, + &impl_.generics, + err, + )?, + } + + // In addition to the above rules, we restrict impls of auto traits + // so that they can only be implemented on nominal types, such as structs, + // enums or foreign types. To see why this restriction exists, consider the + // following example (#22978). Imagine that crate A defines an auto trait + // `Foo` and a fn that operates on pairs of types: + // + // ``` + // // Crate A + // auto trait Foo { } + // fn two_foos(..) { + // one_foo::<(A,B)>(..) + // } + // fn one_foo(..) { .. } + // ``` + // + // This type-checks fine; in particular the fn + // `two_foos` is able to conclude that `(A,B):Foo` + // because `A:Foo` and `B:Foo`. + // + // Now imagine that crate B comes along and does the following: + // + // ``` + // struct A { } + // struct B { } + // impl Foo for A { } + // impl Foo for B { } + // impl !Send for (A, B) { } + // ``` + // + // This final impl is legal according to the orphan + // rules, but it invalidates the reasoning from + // `two_foos` above. + debug!( + "trait_ref={:?} trait_def_id={:?} trait_is_auto={}", + trait_ref, + trait_def_id, + tcx.trait_is_auto(trait_def_id) + ); + + if tcx.trait_is_auto(trait_def_id) && !trait_def_id.is_local() { + let self_ty = trait_ref.self_ty(); + let opt_self_def_id = match *self_ty.kind() { + ty::Adt(self_def, _) => Some(self_def.did()), + ty::Foreign(did) => Some(did), + _ => None, + }; + + let msg = match opt_self_def_id { + // We only want to permit nominal types, but not *all* nominal types. + // They must be local to the current crate, so that people + // can't do `unsafe impl Send for Rc` or + // `impl !Send for Box`. + Some(self_def_id) => { + if self_def_id.is_local() { + None + } else { + Some(( + format!( + "cross-crate traits with a default impl, like `{}`, \ + can only be implemented for a struct/enum type \ + defined in the current crate", + tcx.def_path_str(trait_def_id) + ), + "can't implement cross-crate trait for type in another crate", + )) + } + } + _ => Some(( + format!( + "cross-crate traits with a default impl, like `{}`, can \ + only be implemented for a struct/enum type, not `{}`", + tcx.def_path_str(trait_def_id), + self_ty + ), + "can't implement cross-crate trait with a default impl for \ + non-struct/enum type", + )), + }; + + if let Some((msg, label)) = msg { + let reported = + struct_span_err!(tcx.sess, sp, E0321, "{}", msg).span_label(sp, label).emit(); + return Err(reported); + } + } + + Ok(()) +} + +fn emit_orphan_check_error<'tcx>( + tcx: TyCtxt<'tcx>, + sp: Span, + full_impl_span: Span, + trait_span: Span, + self_ty: Ty<'tcx>, + self_ty_span: Span, + generics: &hir::Generics<'tcx>, + err: traits::OrphanCheckErr<'tcx>, +) -> Result { + Err(match err { + traits::OrphanCheckErr::NonLocalInputType(tys) => { + let msg = match self_ty.kind() { + ty::Adt(..) => "can be implemented for types defined outside of the crate", + _ if self_ty.is_primitive() => "can be implemented for primitive types", + _ => "can be implemented for arbitrary types", + }; + let mut err = struct_span_err!( + tcx.sess, + sp, + E0117, + "only traits defined in the current crate {msg}" + ); + err.span_label(sp, "impl doesn't use only types from inside the current crate"); + for (ty, is_target_ty) in &tys { + let mut ty = *ty; + tcx.infer_ctxt().enter(|infcx| { + // Remove the lifetimes unnecessary for this error. + ty = infcx.freshen(ty); + }); + ty = match ty.kind() { + // Remove the type arguments from the output, as they are not relevant. + // You can think of this as the reverse of `resolve_vars_if_possible`. + // That way if we had `Vec`, we will properly attribute the + // problem to `Vec` and avoid confusing the user if they were to see + // `MyType` in the error. + ty::Adt(def, _) => tcx.mk_adt(*def, ty::List::empty()), + _ => ty, + }; + let this = "this".to_string(); + let (ty, postfix) = match &ty.kind() { + ty::Slice(_) => (this, " because slices are always foreign"), + ty::Array(..) => (this, " because arrays are always foreign"), + ty::Tuple(..) => (this, " because tuples are always foreign"), + ty::RawPtr(ptr_ty) => { + emit_newtype_suggestion_for_raw_ptr( + full_impl_span, + self_ty, + self_ty_span, + ptr_ty, + &mut err, + ); + + (format!("`{}`", ty), " because raw pointers are always foreign") + } + _ => (format!("`{}`", ty), ""), + }; + + let msg = format!("{} is not defined in the current crate{}", ty, postfix); + if *is_target_ty { + // Point at `D` in `impl for C in D` + err.span_label(self_ty_span, &msg); + } else { + // Point at `C` in `impl for C in D` + err.span_label(trait_span, &msg); + } + } + err.note("define and implement a trait or new type instead"); + err.emit() + } + traits::OrphanCheckErr::UncoveredTy(param_ty, local_type) => { + let mut sp = sp; + for param in generics.params { + if param.name.ident().to_string() == param_ty.to_string() { + sp = param.span; + } + } + + match local_type { + Some(local_type) => struct_span_err!( + tcx.sess, + sp, + E0210, + "type parameter `{}` must be covered by another type \ + when it appears before the first local type (`{}`)", + param_ty, + local_type + ) + .span_label( + sp, + format!( + "type parameter `{}` must be covered by another type \ + when it appears before the first local type (`{}`)", + param_ty, local_type + ), + ) + .note( + "implementing a foreign trait is only possible if at \ + least one of the types for which it is implemented is local, \ + and no uncovered type parameters appear before that first \ + local type", + ) + .note( + "in this case, 'before' refers to the following order: \ + `impl<..> ForeignTrait for T0`, \ + where `T0` is the first and `Tn` is the last", + ) + .emit(), + None => struct_span_err!( + tcx.sess, + sp, + E0210, + "type parameter `{}` must be used as the type parameter for some \ + local type (e.g., `MyStruct<{}>`)", + param_ty, + param_ty + ) + .span_label( + sp, + format!( + "type parameter `{}` must be used as the type parameter for some \ + local type", + param_ty, + ), + ) + .note( + "implementing a foreign trait is only possible if at \ + least one of the types for which it is implemented is local", + ) + .note( + "only traits defined in the current crate can be \ + implemented for a type parameter", + ) + .emit(), + } + } + }) +} + +fn emit_newtype_suggestion_for_raw_ptr( + full_impl_span: Span, + self_ty: Ty<'_>, + self_ty_span: Span, + ptr_ty: &ty::TypeAndMut<'_>, + diag: &mut Diagnostic, +) { + if !self_ty.needs_subst() { + let mut_key = if ptr_ty.mutbl == rustc_middle::mir::Mutability::Mut { "mut " } else { "" }; + let msg_sugg = "consider introducing a new wrapper type".to_owned(); + let sugg = vec![ + ( + full_impl_span.shrink_to_lo(), + format!("struct WrapperType(*{}{});\n\n", mut_key, ptr_ty.ty), + ), + (self_ty_span, "WrapperType".to_owned()), + ]; + diag.multipart_suggestion(msg_sugg, sugg, rustc_errors::Applicability::MaybeIncorrect); + } +} + +/// Lint impls of auto traits if they are likely to have +/// unsound or surprising effects on auto impls. +fn lint_auto_trait_impl<'tcx>( + tcx: TyCtxt<'tcx>, + trait_ref: ty::TraitRef<'tcx>, + impl_def_id: LocalDefId, +) { + if tcx.impl_polarity(impl_def_id) != ImplPolarity::Positive { + return; + } + + assert_eq!(trait_ref.substs.len(), 1); + let self_ty = trait_ref.self_ty(); + let (self_type_did, substs) = match self_ty.kind() { + ty::Adt(def, substs) => (def.did(), substs), + _ => { + // FIXME: should also lint for stuff like `&i32` but + // considering that auto traits are unstable, that + // isn't too important for now as this only affects + // crates using `nightly`, and std. + return; + } + }; + + // Impls which completely cover a given root type are fine as they + // disable auto impls entirely. So only lint if the substs + // are not a permutation of the identity substs. + let Err(arg) = tcx.uses_unique_generic_params(substs, IgnoreRegions::Yes) else { + // ok + return; + }; + + // Ideally: + // + // - compute the requirements for the auto impl candidate + // - check whether these are implied by the non covering impls + // - if not, emit the lint + // + // What we do here is a bit simpler: + // + // - badly check if an auto impl candidate definitely does not apply + // for the given simplified type + // - if so, do not lint + if fast_reject_auto_impl(tcx, trait_ref.def_id, self_ty) { + // ok + return; + } + + tcx.struct_span_lint_hir( + lint::builtin::SUSPICIOUS_AUTO_TRAIT_IMPLS, + tcx.hir().local_def_id_to_hir_id(impl_def_id), + tcx.def_span(impl_def_id), + |err| { + let item_span = tcx.def_span(self_type_did); + let self_descr = tcx.def_kind(self_type_did).descr(self_type_did); + let mut err = err.build(&format!( + "cross-crate traits with a default impl, like `{}`, \ + should not be specialized", + tcx.def_path_str(trait_ref.def_id), + )); + match arg { + ty::util::NotUniqueParam::DuplicateParam(arg) => { + err.note(&format!("`{}` is mentioned multiple times", arg)); + } + ty::util::NotUniqueParam::NotParam(arg) => { + err.note(&format!("`{}` is not a generic parameter", arg)); + } + } + err.span_note( + item_span, + &format!( + "try using the same sequence of generic parameters as the {} definition", + self_descr, + ), + ); + err.emit(); + }, + ); +} + +fn fast_reject_auto_impl<'tcx>(tcx: TyCtxt<'tcx>, trait_def_id: DefId, self_ty: Ty<'tcx>) -> bool { + struct DisableAutoTraitVisitor<'tcx> { + tcx: TyCtxt<'tcx>, + trait_def_id: DefId, + self_ty_root: Ty<'tcx>, + seen: FxHashSet, + } + + impl<'tcx> TypeVisitor<'tcx> for DisableAutoTraitVisitor<'tcx> { + type BreakTy = (); + fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow { + let tcx = self.tcx; + if t != self.self_ty_root { + for impl_def_id in tcx.non_blanket_impls_for_ty(self.trait_def_id, t) { + match tcx.impl_polarity(impl_def_id) { + ImplPolarity::Negative => return ControlFlow::BREAK, + ImplPolarity::Reservation => {} + // FIXME(@lcnr): That's probably not good enough, idk + // + // We might just want to take the rustdoc code and somehow avoid + // explicit impls for `Self`. + ImplPolarity::Positive => return ControlFlow::CONTINUE, + } + } + } + + match t.kind() { + ty::Adt(def, substs) if def.is_phantom_data() => substs.visit_with(self), + ty::Adt(def, substs) => { + // @lcnr: This is the only place where cycles can happen. We avoid this + // by only visiting each `DefId` once. + // + // This will be is incorrect in subtle cases, but I don't care :) + if self.seen.insert(def.did()) { + for ty in def.all_fields().map(|field| field.ty(tcx, substs)) { + ty.visit_with(self)?; + } + } + + ControlFlow::CONTINUE + } + _ => t.super_visit_with(self), + } + } + } + + let self_ty_root = match self_ty.kind() { + ty::Adt(def, _) => tcx.mk_adt(*def, InternalSubsts::identity_for_item(tcx, def.did())), + _ => unimplemented!("unexpected self ty {:?}", self_ty), + }; + + self_ty_root + .visit_with(&mut DisableAutoTraitVisitor { + tcx, + self_ty_root, + trait_def_id, + seen: FxHashSet::default(), + }) + .is_break() +} diff --git a/compiler/rustc_typeck/src/coherence/unsafety.rs b/compiler/rustc_typeck/src/coherence/unsafety.rs new file mode 100644 index 000000000..e45fb5fe4 --- /dev/null +++ b/compiler/rustc_typeck/src/coherence/unsafety.rs @@ -0,0 +1,66 @@ +//! Unsafety checker: every impl either implements a trait defined in this +//! crate or pertains to a type defined in this crate. + +use rustc_errors::struct_span_err; +use rustc_hir as hir; +use rustc_hir::def::DefKind; +use rustc_hir::Unsafety; +use rustc_middle::ty::TyCtxt; +use rustc_span::def_id::LocalDefId; + +pub(super) fn check_item(tcx: TyCtxt<'_>, def_id: LocalDefId) { + debug_assert!(matches!(tcx.def_kind(def_id), DefKind::Impl)); + let item = tcx.hir().expect_item(def_id); + let hir::ItemKind::Impl(ref impl_) = item.kind else { bug!() }; + + if let Some(trait_ref) = tcx.impl_trait_ref(item.def_id) { + let trait_def = tcx.trait_def(trait_ref.def_id); + let unsafe_attr = + impl_.generics.params.iter().find(|p| p.pure_wrt_drop).map(|_| "may_dangle"); + match (trait_def.unsafety, unsafe_attr, impl_.unsafety, impl_.polarity) { + (Unsafety::Normal, None, Unsafety::Unsafe, hir::ImplPolarity::Positive) => { + struct_span_err!( + tcx.sess, + item.span, + E0199, + "implementing the trait `{}` is not unsafe", + trait_ref.print_only_trait_path() + ) + .emit(); + } + + (Unsafety::Unsafe, _, Unsafety::Normal, hir::ImplPolarity::Positive) => { + struct_span_err!( + tcx.sess, + item.span, + E0200, + "the trait `{}` requires an `unsafe impl` declaration", + trait_ref.print_only_trait_path() + ) + .emit(); + } + + (Unsafety::Normal, Some(attr_name), Unsafety::Normal, hir::ImplPolarity::Positive) => { + struct_span_err!( + tcx.sess, + item.span, + E0569, + "requires an `unsafe impl` declaration due to `#[{}]` attribute", + attr_name + ) + .emit(); + } + + (_, _, Unsafety::Unsafe, hir::ImplPolarity::Negative(_)) => { + // Reported in AST validation + tcx.sess.delay_span_bug(item.span, "unsafe negative impl"); + } + (_, _, Unsafety::Normal, hir::ImplPolarity::Negative(_)) + | (Unsafety::Unsafe, _, Unsafety::Unsafe, hir::ImplPolarity::Positive) + | (Unsafety::Normal, Some(_), Unsafety::Unsafe, hir::ImplPolarity::Positive) + | (Unsafety::Normal, None, Unsafety::Normal, _) => { + // OK + } + } + } +} -- cgit v1.2.3