pub mod specialization_graph;
use rustc_infer::infer::DefineOpaqueTypes;
use specialization_graph::GraphExt;
use crate::errors::NegativePositiveConflict;
use crate::infer::{InferCtxt, InferOk, TyCtxtInferExt};
use crate::traits::select::IntercrateAmbiguityCause;
use crate::traits::{
self, coherence, FutureCompatOverlapErrorKind, ObligationCause, ObligationCtxt,
};
use rustc_data_structures::fx::FxIndexSet;
use rustc_errors::{error_code, DelayDm, Diagnostic};
use rustc_hir::def_id::{DefId, LocalDefId};
use rustc_middle::ty::{self, ImplSubject, Ty, TyCtxt, TypeVisitableExt};
use rustc_middle::ty::{GenericArgs, GenericArgsRef};
use rustc_session::lint::builtin::COHERENCE_LEAK_CHECK;
use rustc_session::lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS;
use rustc_span::{Span, DUMMY_SP};
use super::util;
use super::SelectionContext;
#[derive(Debug)]
pub struct OverlapError<'tcx> {
pub with_impl: DefId,
pub trait_ref: ty::TraitRef<'tcx>,
pub self_ty: Option<Ty<'tcx>>,
pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause>,
pub involves_placeholder: bool,
}
pub fn translate_args<'tcx>(
infcx: &InferCtxt<'tcx>,
param_env: ty::ParamEnv<'tcx>,
source_impl: DefId,
source_args: GenericArgsRef<'tcx>,
target_node: specialization_graph::Node,
) -> GenericArgsRef<'tcx> {
translate_args_with_cause(infcx, param_env, source_impl, source_args, target_node, |_, _| {
ObligationCause::dummy()
})
}
pub fn translate_args_with_cause<'tcx>(
infcx: &InferCtxt<'tcx>,
param_env: ty::ParamEnv<'tcx>,
source_impl: DefId,
source_args: GenericArgsRef<'tcx>,
target_node: specialization_graph::Node,
cause: impl Fn(usize, Span) -> ObligationCause<'tcx>,
) -> GenericArgsRef<'tcx> {
debug!(
"translate_args({:?}, {:?}, {:?}, {:?})",
param_env, source_impl, source_args, target_node
);
let source_trait_ref =
infcx.tcx.impl_trait_ref(source_impl).unwrap().instantiate(infcx.tcx, &source_args);
let target_args = match target_node {
specialization_graph::Node::Impl(target_impl) => {
if source_impl == target_impl {
return source_args;
}
fulfill_implication(infcx, param_env, source_trait_ref, source_impl, target_impl, cause)
.unwrap_or_else(|()| {
bug!(
"When translating substitutions from {source_impl:?} to {target_impl:?}, \
the expected specialization failed to hold"
)
})
}
specialization_graph::Node::Trait(..) => source_trait_ref.args,
};
source_args.rebase_onto(infcx.tcx, source_impl, target_args)
}
#[instrument(skip(tcx), level = "debug")]
pub(super) fn specializes(tcx: TyCtxt<'_>, (impl1_def_id, impl2_def_id): (DefId, DefId)) -> bool {
let features = tcx.features();
let specialization_enabled = features.specialization || features.min_specialization;
if !specialization_enabled && (impl1_def_id.is_local() || impl2_def_id.is_local()) {
return false;
}
if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
return false;
}
let penv = tcx.param_env(impl1_def_id);
let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap().instantiate_identity();
let infcx = tcx.infer_ctxt().build();
fulfill_implication(&infcx, penv, impl1_trait_ref, impl1_def_id, impl2_def_id, |_, _| {
ObligationCause::dummy()
})
.is_ok()
}
fn fulfill_implication<'tcx>(
infcx: &InferCtxt<'tcx>,
param_env: ty::ParamEnv<'tcx>,
source_trait_ref: ty::TraitRef<'tcx>,
source_impl: DefId,
target_impl: DefId,
error_cause: impl Fn(usize, Span) -> ObligationCause<'tcx>,
) -> Result<GenericArgsRef<'tcx>, ()> {
debug!(
"fulfill_implication({:?}, trait_ref={:?} |- {:?} applies)",
param_env, source_trait_ref, target_impl
);
let source_trait_ref = match traits::fully_normalize(
&infcx,
ObligationCause::dummy(),
param_env,
source_trait_ref,
) {
Ok(source_trait_ref) => source_trait_ref,
Err(_errors) => {
infcx.tcx.sess.delay_span_bug(
infcx.tcx.def_span(source_impl),
format!("failed to fully normalize {source_trait_ref}"),
);
source_trait_ref
}
};
let source_trait = ImplSubject::Trait(source_trait_ref);
let selcx = &mut SelectionContext::new(&infcx);
let target_args = infcx.fresh_args_for_item(DUMMY_SP, target_impl);
let (target_trait, obligations) =
util::impl_subject_and_oblig(selcx, param_env, target_impl, target_args, error_cause);
let Ok(InferOk { obligations: more_obligations, .. }) = infcx
.at(&ObligationCause::dummy(), param_env)
.eq(DefineOpaqueTypes::No, source_trait, target_trait)
else {
debug!("fulfill_implication: {:?} does not unify with {:?}", source_trait, target_trait);
return Err(());
};
let ocx = ObligationCtxt::new(infcx);
ocx.register_obligations(obligations.chain(more_obligations));
let errors = ocx.select_all_or_error();
if !errors.is_empty() {
debug!(
"fulfill_implication: for impls on {:?} and {:?}, \
could not fulfill: {:?} given {:?}",
source_trait,
target_trait,
errors,
param_env.caller_bounds()
);
return Err(());
}
debug!("fulfill_implication: an impl for {:?} specializes {:?}", source_trait, target_trait);
Ok(infcx.resolve_vars_if_possible(target_args))
}
pub(super) fn specialization_graph_provider(
tcx: TyCtxt<'_>,
trait_id: DefId,
) -> specialization_graph::Graph {
let mut sg = specialization_graph::Graph::new();
let overlap_mode = specialization_graph::OverlapMode::get(tcx, trait_id);
let mut trait_impls: Vec<_> = tcx.all_impls(trait_id).collect();
trait_impls
.sort_unstable_by_key(|def_id| (-(def_id.krate.as_u32() as i64), def_id.index.index()));
for impl_def_id in trait_impls {
if let Some(impl_def_id) = impl_def_id.as_local() {
let insert_result = sg.insert(tcx, impl_def_id.to_def_id(), overlap_mode);
let (overlap, used_to_be_allowed) = match insert_result {
Err(overlap) => (Some(overlap), None),
Ok(Some(overlap)) => (Some(overlap.error), Some(overlap.kind)),
Ok(None) => (None, None),
};
if let Some(overlap) = overlap {
report_overlap_conflict(tcx, overlap, impl_def_id, used_to_be_allowed, &mut sg);
}
} else {
let parent = tcx.impl_parent(impl_def_id).unwrap_or(trait_id);
sg.record_impl_from_cstore(tcx, parent, impl_def_id)
}
}
sg
}
#[cold]
#[inline(never)]
fn report_overlap_conflict<'tcx>(
tcx: TyCtxt<'tcx>,
overlap: OverlapError<'tcx>,
impl_def_id: LocalDefId,
used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
sg: &mut specialization_graph::Graph,
) {
let impl_polarity = tcx.impl_polarity(impl_def_id.to_def_id());
let other_polarity = tcx.impl_polarity(overlap.with_impl);
match (impl_polarity, other_polarity) {
(ty::ImplPolarity::Negative, ty::ImplPolarity::Positive) => {
report_negative_positive_conflict(
tcx,
&overlap,
impl_def_id,
impl_def_id.to_def_id(),
overlap.with_impl,
sg,
);
}
(ty::ImplPolarity::Positive, ty::ImplPolarity::Negative) => {
report_negative_positive_conflict(
tcx,
&overlap,
impl_def_id,
overlap.with_impl,
impl_def_id.to_def_id(),
sg,
);
}
_ => {
report_conflicting_impls(tcx, overlap, impl_def_id, used_to_be_allowed, sg);
}
}
}
fn report_negative_positive_conflict<'tcx>(
tcx: TyCtxt<'tcx>,
overlap: &OverlapError<'tcx>,
local_impl_def_id: LocalDefId,
negative_impl_def_id: DefId,
positive_impl_def_id: DefId,
sg: &mut specialization_graph::Graph,
) {
let mut err = tcx.sess.create_err(NegativePositiveConflict {
impl_span: tcx.def_span(local_impl_def_id),
trait_desc: overlap.trait_ref,
self_ty: overlap.self_ty,
negative_impl_span: tcx.span_of_impl(negative_impl_def_id),
positive_impl_span: tcx.span_of_impl(positive_impl_def_id),
});
sg.has_errored = Some(err.emit());
}
fn report_conflicting_impls<'tcx>(
tcx: TyCtxt<'tcx>,
overlap: OverlapError<'tcx>,
impl_def_id: LocalDefId,
used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
sg: &mut specialization_graph::Graph,
) {
let impl_span = tcx.def_span(impl_def_id);
fn decorate<'tcx>(
tcx: TyCtxt<'tcx>,
overlap: &OverlapError<'tcx>,
impl_span: Span,
err: &mut Diagnostic,
) {
if (overlap.trait_ref, overlap.self_ty).references_error() {
err.downgrade_to_delayed_bug();
}
match tcx.span_of_impl(overlap.with_impl) {
Ok(span) => {
err.span_label(span, "first implementation here");
err.span_label(
impl_span,
format!(
"conflicting implementation{}",
overlap.self_ty.map_or_else(String::new, |ty| format!(" for `{ty}`"))
),
);
}
Err(cname) => {
let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
Some(s) => {
format!("conflicting implementation in crate `{cname}`:\n- {s}")
}
None => format!("conflicting implementation in crate `{cname}`"),
};
err.note(msg);
}
}
for cause in &overlap.intercrate_ambiguity_causes {
cause.add_intercrate_ambiguity_hint(err);
}
if overlap.involves_placeholder {
coherence::add_placeholder_note(err);
}
}
let msg = DelayDm(|| {
format!(
"conflicting implementations of trait `{}`{}{}",
overlap.trait_ref.print_only_trait_path(),
overlap.self_ty.map_or_else(String::new, |ty| format!(" for type `{ty}`")),
match used_to_be_allowed {
Some(FutureCompatOverlapErrorKind::Issue33140) => ": (E0119)",
_ => "",
}
)
});
match used_to_be_allowed {
None => {
let reported = if overlap.with_impl.is_local()
|| tcx.orphan_check_impl(impl_def_id).is_ok()
{
let mut err = tcx.sess.struct_span_err(impl_span, msg);
err.code(error_code!(E0119));
decorate(tcx, &overlap, impl_span, &mut err);
Some(err.emit())
} else {
Some(tcx.sess.delay_span_bug(impl_span, "impl should have failed the orphan check"))
};
sg.has_errored = reported;
}
Some(kind) => {
let lint = match kind {
FutureCompatOverlapErrorKind::Issue33140 => ORDER_DEPENDENT_TRAIT_OBJECTS,
FutureCompatOverlapErrorKind::LeakCheck => COHERENCE_LEAK_CHECK,
};
tcx.struct_span_lint_hir(
lint,
tcx.hir().local_def_id_to_hir_id(impl_def_id),
impl_span,
msg,
|err| {
decorate(tcx, &overlap, impl_span, err);
err
},
);
}
};
}
pub(crate) fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option<String> {
use std::fmt::Write;
let trait_ref = tcx.impl_trait_ref(impl_def_id)?.instantiate_identity();
let mut w = "impl".to_owned();
let args = GenericArgs::identity_for_item(tcx, impl_def_id);
let mut types_without_default_bounds = FxIndexSet::default();
let sized_trait = tcx.lang_items().sized_trait();
let arg_names = args.iter().map(|k| k.to_string()).filter(|k| k != "'_").collect::<Vec<_>>();
if !arg_names.is_empty() {
types_without_default_bounds.extend(args.types());
w.push('<');
w.push_str(&arg_names.join(", "));
w.push('>');
}
write!(
w,
" {} for {}",
trait_ref.print_only_trait_path(),
tcx.type_of(impl_def_id).instantiate_identity()
)
.unwrap();
let predicates = tcx.predicates_of(impl_def_id).predicates;
let mut pretty_predicates =
Vec::with_capacity(predicates.len() + types_without_default_bounds.len());
for (p, _) in predicates {
if let Some(poly_trait_ref) = p.as_trait_clause() {
if Some(poly_trait_ref.def_id()) == sized_trait {
types_without_default_bounds.remove(&poly_trait_ref.self_ty().skip_binder());
continue;
}
}
pretty_predicates.push(p.to_string());
}
pretty_predicates.extend(types_without_default_bounds.iter().map(|ty| format!("{ty}: ?Sized")));
if !pretty_predicates.is_empty() {
write!(w, "\n where {}", pretty_predicates.join(", ")).unwrap();
}
w.push(';');
Some(w)
}