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 --- .../src/traits/specialize/mod.rs | 531 +++++++++++++++++++++ .../src/traits/specialize/specialization_graph.rs | 395 +++++++++++++++ 2 files changed, 926 insertions(+) create mode 100644 compiler/rustc_trait_selection/src/traits/specialize/mod.rs create mode 100644 compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs (limited to 'compiler/rustc_trait_selection/src/traits/specialize') diff --git a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs new file mode 100644 index 000000000..6223c5ea3 --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs @@ -0,0 +1,531 @@ +//! Logic and data structures related to impl specialization, explained in +//! greater detail below. +//! +//! At the moment, this implementation support only the simple "chain" rule: +//! If any two impls overlap, one must be a strict subset of the other. +//! +//! See the [rustc dev guide] for a bit more detail on how specialization +//! fits together with the rest of the trait machinery. +//! +//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/specialization.html + +pub mod specialization_graph; +use specialization_graph::GraphExt; + +use crate::infer::{InferCtxt, InferOk, TyCtxtInferExt}; +use crate::traits::select::IntercrateAmbiguityCause; +use crate::traits::{ + self, coherence, FutureCompatOverlapErrorKind, ObligationCause, TraitEngine, TraitEngineExt, +}; +use rustc_data_structures::fx::{FxHashSet, FxIndexSet}; +use rustc_errors::{struct_span_err, EmissionGuarantee, LintDiagnosticBuilder}; +use rustc_hir::def_id::{DefId, LocalDefId}; +use rustc_middle::ty::subst::{InternalSubsts, Subst, SubstsRef}; +use rustc_middle::ty::{self, ImplSubject, TyCtxt}; +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::SelectionContext; +use super::{util, FulfillmentContext}; + +/// Information pertinent to an overlapping impl error. +#[derive(Debug)] +pub struct OverlapError { + pub with_impl: DefId, + pub trait_desc: String, + pub self_desc: Option, + pub intercrate_ambiguity_causes: FxIndexSet, + pub involves_placeholder: bool, +} + +/// Given a subst for the requested impl, translate it to a subst +/// appropriate for the actual item definition (whether it be in that impl, +/// a parent impl, or the trait). +/// +/// When we have selected one impl, but are actually using item definitions from +/// a parent impl providing a default, we need a way to translate between the +/// type parameters of the two impls. Here the `source_impl` is the one we've +/// selected, and `source_substs` is a substitution of its generics. +/// And `target_node` is the impl/trait we're actually going to get the +/// definition from. The resulting substitution will map from `target_node`'s +/// generics to `source_impl`'s generics as instantiated by `source_subst`. +/// +/// For example, consider the following scenario: +/// +/// ```ignore (illustrative) +/// trait Foo { ... } +/// impl Foo for (T, U) { ... } // target impl +/// impl Foo for (V, V) { ... } // source impl +/// ``` +/// +/// Suppose we have selected "source impl" with `V` instantiated with `u32`. +/// This function will produce a substitution with `T` and `U` both mapping to `u32`. +/// +/// where-clauses add some trickiness here, because they can be used to "define" +/// an argument indirectly: +/// +/// ```ignore (illustrative) +/// impl<'a, I, T: 'a> Iterator for Cloned +/// where I: Iterator, T: Clone +/// ``` +/// +/// In a case like this, the substitution for `T` is determined indirectly, +/// through associated type projection. We deal with such cases by using +/// *fulfillment* to relate the two impls, requiring that all projections are +/// resolved. +pub fn translate_substs<'a, 'tcx>( + infcx: &InferCtxt<'a, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + source_impl: DefId, + source_substs: SubstsRef<'tcx>, + target_node: specialization_graph::Node, +) -> SubstsRef<'tcx> { + debug!( + "translate_substs({:?}, {:?}, {:?}, {:?})", + param_env, source_impl, source_substs, target_node + ); + let source_trait_ref = + infcx.tcx.bound_impl_trait_ref(source_impl).unwrap().subst(infcx.tcx, &source_substs); + + // translate the Self and Param parts of the substitution, since those + // vary across impls + let target_substs = match target_node { + specialization_graph::Node::Impl(target_impl) => { + // no need to translate if we're targeting the impl we started with + if source_impl == target_impl { + return source_substs; + } + + fulfill_implication(infcx, param_env, source_trait_ref, target_impl).unwrap_or_else( + |_| { + bug!( + "When translating substitutions for specialization, the expected \ + specialization failed to hold" + ) + }, + ) + } + specialization_graph::Node::Trait(..) => source_trait_ref.substs, + }; + + // directly inherent the method generics, since those do not vary across impls + source_substs.rebase_onto(infcx.tcx, source_impl, target_substs) +} + +/// Is `impl1` a specialization of `impl2`? +/// +/// Specialization is determined by the sets of types to which the impls apply; +/// `impl1` specializes `impl2` if it applies to a subset of the types `impl2` applies +/// to. +#[instrument(skip(tcx), level = "debug")] +pub(super) fn specializes(tcx: TyCtxt<'_>, (impl1_def_id, impl2_def_id): (DefId, DefId)) -> bool { + // The feature gate should prevent introducing new specializations, but not + // taking advantage of upstream ones. + 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; + } + + // We determine whether there's a subset relationship by: + // + // - replacing bound vars with placeholders in impl1, + // - assuming the where clauses for impl1, + // - instantiating impl2 with fresh inference variables, + // - unifying, + // - attempting to prove the where clauses for impl2 + // + // The last three steps are encapsulated in `fulfill_implication`. + // + // See RFC 1210 for more details and justification. + + // Currently we do not allow e.g., a negative impl to specialize a positive one + if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) { + return false; + } + + // create a parameter environment corresponding to a (placeholder) instantiation of impl1 + let penv = tcx.param_env(impl1_def_id); + let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap(); + + // Create an infcx, taking the predicates of impl1 as assumptions: + tcx.infer_ctxt().enter(|infcx| { + let impl1_trait_ref = match traits::fully_normalize( + &infcx, + FulfillmentContext::new(), + ObligationCause::dummy(), + penv, + impl1_trait_ref, + ) { + Ok(impl1_trait_ref) => impl1_trait_ref, + Err(_errors) => { + tcx.sess.delay_span_bug( + tcx.def_span(impl1_def_id), + format!("failed to fully normalize {impl1_trait_ref}"), + ); + impl1_trait_ref + } + }; + + // Attempt to prove that impl2 applies, given all of the above. + fulfill_implication(&infcx, penv, impl1_trait_ref, impl2_def_id).is_ok() + }) +} + +/// Attempt to fulfill all obligations of `target_impl` after unification with +/// `source_trait_ref`. If successful, returns a substitution for *all* the +/// generics of `target_impl`, including both those needed to unify with +/// `source_trait_ref` and those whose identity is determined via a where +/// clause in the impl. +fn fulfill_implication<'a, 'tcx>( + infcx: &InferCtxt<'a, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + source_trait_ref: ty::TraitRef<'tcx>, + target_impl: DefId, +) -> Result, ()> { + debug!( + "fulfill_implication({:?}, trait_ref={:?} |- {:?} applies)", + param_env, source_trait_ref, target_impl + ); + + let source_trait = ImplSubject::Trait(source_trait_ref); + + let selcx = &mut SelectionContext::new(&infcx); + let target_substs = infcx.fresh_substs_for_item(DUMMY_SP, target_impl); + let (target_trait, obligations) = + util::impl_subject_and_oblig(selcx, param_env, target_impl, target_substs); + + // do the impls unify? If not, no specialization. + let Ok(InferOk { obligations: more_obligations, .. }) = + infcx.at(&ObligationCause::dummy(), param_env).eq(source_trait, target_trait) + else { + debug!( + "fulfill_implication: {:?} does not unify with {:?}", + source_trait, target_trait + ); + return Err(()); + }; + + // attempt to prove all of the predicates for impl2 given those for impl1 + // (which are packed up in penv) + + infcx.save_and_restore_in_snapshot_flag(|infcx| { + let mut fulfill_cx = >::new(infcx.tcx); + for oblig in obligations.chain(more_obligations) { + fulfill_cx.register_predicate_obligation(&infcx, oblig); + } + match fulfill_cx.select_all_or_error(infcx).as_slice() { + [] => { + debug!( + "fulfill_implication: an impl for {:?} specializes {:?}", + source_trait, target_trait + ); + + // Now resolve the *substitution* we built for the target earlier, replacing + // the inference variables inside with whatever we got from fulfillment. + Ok(infcx.resolve_vars_if_possible(target_substs)) + } + errors => { + // no dice! + debug!( + "fulfill_implication: for impls on {:?} and {:?}, \ + could not fulfill: {:?} given {:?}", + source_trait, + target_trait, + errors, + param_env.caller_bounds() + ); + Err(()) + } + } + }) +} + +// Query provider for `specialization_graph_of`. +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(); + + // The coherence checking implementation seems to rely on impls being + // iterated over (roughly) in definition order, so we are sorting by + // negated `CrateNum` (so remote definitions are visited first) and then + // by a flattened version of the `DefIndex`. + 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() { + // This is where impl overlap checking happens: + let insert_result = sg.insert(tcx, impl_def_id.to_def_id(), overlap_mode); + // Report error if there was one. + 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 +} + +// This function is only used when +// encountering errors and inlining +// it negatively impacts perf. +#[cold] +#[inline(never)] +fn report_overlap_conflict( + tcx: TyCtxt<'_>, + overlap: OverlapError, + impl_def_id: LocalDefId, + used_to_be_allowed: Option, + 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: TyCtxt<'_>, + overlap: &OverlapError, + local_impl_def_id: LocalDefId, + negative_impl_def_id: DefId, + positive_impl_def_id: DefId, + sg: &mut specialization_graph::Graph, +) { + let impl_span = tcx.def_span(local_impl_def_id); + + let mut err = struct_span_err!( + tcx.sess, + impl_span, + E0751, + "found both positive and negative implementation of trait `{}`{}:", + overlap.trait_desc, + overlap.self_desc.clone().map_or_else(String::new, |ty| format!(" for type `{}`", ty)) + ); + + match tcx.span_of_impl(negative_impl_def_id) { + Ok(span) => { + err.span_label(span, "negative implementation here"); + } + Err(cname) => { + err.note(&format!("negative implementation in crate `{}`", cname)); + } + } + + match tcx.span_of_impl(positive_impl_def_id) { + Ok(span) => { + err.span_label(span, "positive implementation here"); + } + Err(cname) => { + err.note(&format!("positive implementation in crate `{}`", cname)); + } + } + + sg.has_errored = Some(err.emit()); +} + +fn report_conflicting_impls( + tcx: TyCtxt<'_>, + overlap: OverlapError, + impl_def_id: LocalDefId, + used_to_be_allowed: Option, + sg: &mut specialization_graph::Graph, +) { + let impl_span = tcx.def_span(impl_def_id); + + // Work to be done after we've built the DiagnosticBuilder. We have to define it + // now because the struct_lint methods don't return back the DiagnosticBuilder + // that's passed in. + fn decorate( + tcx: TyCtxt<'_>, + overlap: OverlapError, + used_to_be_allowed: Option, + impl_span: Span, + err: LintDiagnosticBuilder<'_, G>, + ) -> G { + let msg = format!( + "conflicting implementations of trait `{}`{}{}", + overlap.trait_desc, + overlap + .self_desc + .clone() + .map_or_else(String::new, |ty| { format!(" for type `{}`", ty) }), + match used_to_be_allowed { + Some(FutureCompatOverlapErrorKind::Issue33140) => ": (E0119)", + _ => "", + } + ); + let mut err = err.build(&msg); + 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_desc.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 `{}`:\n- {}", cname, s), + None => format!("conflicting implementation in crate `{}`", cname), + }; + err.note(&msg); + } + } + + for cause in &overlap.intercrate_ambiguity_causes { + cause.add_intercrate_ambiguity_hint(&mut err); + } + + if overlap.involves_placeholder { + coherence::add_placeholder_note(&mut err); + } + err.emit() + } + + match used_to_be_allowed { + None => { + let reported = if overlap.with_impl.is_local() + || tcx.orphan_check_impl(impl_def_id).is_ok() + { + let err = struct_span_err!(tcx.sess, impl_span, E0119, ""); + Some(decorate( + tcx, + overlap, + used_to_be_allowed, + impl_span, + LintDiagnosticBuilder::new(err), + )) + } 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, + |ldb| { + decorate(tcx, overlap, used_to_be_allowed, impl_span, ldb); + }, + ); + } + }; +} + +/// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a +/// string. +pub(crate) fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Option { + use std::fmt::Write; + + let trait_ref = tcx.impl_trait_ref(impl_def_id)?; + let mut w = "impl".to_owned(); + + let substs = InternalSubsts::identity_for_item(tcx, impl_def_id); + + // FIXME: Currently only handles ?Sized. + // Needs to support ?Move and ?DynSized when they are implemented. + let mut types_without_default_bounds = FxHashSet::default(); + let sized_trait = tcx.lang_items().sized_trait(); + + if !substs.is_empty() { + types_without_default_bounds.extend(substs.types()); + w.push('<'); + w.push_str( + &substs + .iter() + .map(|k| k.to_string()) + .filter(|k| k != "'_") + .collect::>() + .join(", "), + ); + w.push('>'); + } + + write!(w, " {} for {}", trait_ref.print_only_trait_path(), tcx.type_of(impl_def_id)).unwrap(); + + // The predicates will contain default bounds like `T: Sized`. We need to + // remove these bounds, and add `T: ?Sized` to any untouched type parameters. + let predicates = tcx.predicates_of(impl_def_id).predicates; + let mut pretty_predicates = + Vec::with_capacity(predicates.len() + types_without_default_bounds.len()); + + for (mut p, _) in predicates { + if let Some(poly_trait_ref) = p.to_opt_poly_trait_pred() { + if Some(poly_trait_ref.def_id()) == sized_trait { + types_without_default_bounds.remove(&poly_trait_ref.self_ty().skip_binder()); + continue; + } + + if ty::BoundConstness::ConstIfConst == poly_trait_ref.skip_binder().constness { + let new_trait_pred = poly_trait_ref.map_bound(|mut trait_pred| { + trait_pred.constness = ty::BoundConstness::NotConst; + trait_pred + }); + + p = tcx.mk_predicate(new_trait_pred.map_bound(ty::PredicateKind::Trait)) + } + } + pretty_predicates.push(p.to_string()); + } + + pretty_predicates + .extend(types_without_default_bounds.iter().map(|ty| format!("{}: ?Sized", ty))); + + if !pretty_predicates.is_empty() { + write!(w, "\n where {}", pretty_predicates.join(", ")).unwrap(); + } + + w.push(';'); + Some(w) +} diff --git a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs new file mode 100644 index 000000000..fcb73b43f --- /dev/null +++ b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs @@ -0,0 +1,395 @@ +use super::OverlapError; + +use crate::traits; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams}; +use rustc_middle::ty::print::with_no_trimmed_paths; +use rustc_middle::ty::{self, TyCtxt, TypeVisitable}; + +pub use rustc_middle::traits::specialization_graph::*; + +#[derive(Copy, Clone, Debug)] +pub enum FutureCompatOverlapErrorKind { + Issue33140, + LeakCheck, +} + +#[derive(Debug)] +pub struct FutureCompatOverlapError { + pub error: OverlapError, + pub kind: FutureCompatOverlapErrorKind, +} + +/// The result of attempting to insert an impl into a group of children. +enum Inserted { + /// The impl was inserted as a new child in this group of children. + BecameNewSibling(Option), + + /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc. + ReplaceChildren(Vec), + + /// The impl is a specialization of an existing child. + ShouldRecurseOn(DefId), +} + +trait ChildrenExt<'tcx> { + fn insert_blindly(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId); + fn remove_existing(&mut self, tcx: TyCtxt<'tcx>, impl_def_id: DefId); + + fn insert( + &mut self, + tcx: TyCtxt<'tcx>, + impl_def_id: DefId, + simplified_self: Option, + overlap_mode: OverlapMode, + ) -> Result; +} + +impl ChildrenExt<'_> for Children { + /// Insert an impl into this set of children without comparing to any existing impls. + fn insert_blindly(&mut self, tcx: TyCtxt<'_>, impl_def_id: DefId) { + let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer) + { + debug!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id, st); + self.non_blanket_impls.entry(st).or_default().push(impl_def_id) + } else { + debug!("insert_blindly: impl_def_id={:?} st=None", impl_def_id); + self.blanket_impls.push(impl_def_id) + } + } + + /// Removes an impl from this set of children. Used when replacing + /// an impl with a parent. The impl must be present in the list of + /// children already. + fn remove_existing(&mut self, tcx: TyCtxt<'_>, impl_def_id: DefId) { + let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + let vec: &mut Vec; + if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer) + { + debug!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id, st); + vec = self.non_blanket_impls.get_mut(&st).unwrap(); + } else { + debug!("remove_existing: impl_def_id={:?} st=None", impl_def_id); + vec = &mut self.blanket_impls; + } + + let index = vec.iter().position(|d| *d == impl_def_id).unwrap(); + vec.remove(index); + } + + /// Attempt to insert an impl into this set of children, while comparing for + /// specialization relationships. + fn insert( + &mut self, + tcx: TyCtxt<'_>, + impl_def_id: DefId, + simplified_self: Option, + overlap_mode: OverlapMode, + ) -> Result { + let mut last_lint = None; + let mut replace_children = Vec::new(); + + debug!("insert(impl_def_id={:?}, simplified_self={:?})", impl_def_id, simplified_self,); + + let possible_siblings = match simplified_self { + Some(st) => PotentialSiblings::Filtered(filtered_children(self, st)), + None => PotentialSiblings::Unfiltered(iter_children(self)), + }; + + for possible_sibling in possible_siblings { + debug!( + "insert: impl_def_id={:?}, simplified_self={:?}, possible_sibling={:?}", + impl_def_id, simplified_self, possible_sibling, + ); + + let create_overlap_error = |overlap: traits::coherence::OverlapResult<'_>| { + let trait_ref = overlap.impl_header.trait_ref.unwrap(); + let self_ty = trait_ref.self_ty(); + + // FIXME: should postpone string formatting until we decide to actually emit. + with_no_trimmed_paths!({ + OverlapError { + with_impl: possible_sibling, + trait_desc: trait_ref.print_only_trait_path().to_string(), + // Only report the `Self` type if it has at least + // some outer concrete shell; otherwise, it's + // not adding much information. + self_desc: if self_ty.has_concrete_skeleton() { + Some(self_ty.to_string()) + } else { + None + }, + intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes, + involves_placeholder: overlap.involves_placeholder, + } + }) + }; + + let report_overlap_error = |overlap: traits::coherence::OverlapResult<'_>, + last_lint: &mut _| { + // Found overlap, but no specialization; error out or report future-compat warning. + + // Do we *still* get overlap if we disable the future-incompatible modes? + let should_err = traits::overlapping_impls( + tcx, + possible_sibling, + impl_def_id, + traits::SkipLeakCheck::default(), + overlap_mode, + |_| true, + || false, + ); + + let error = create_overlap_error(overlap); + + if should_err { + Err(error) + } else { + *last_lint = Some(FutureCompatOverlapError { + error, + kind: FutureCompatOverlapErrorKind::LeakCheck, + }); + + Ok((false, false)) + } + }; + + let last_lint_mut = &mut last_lint; + let (le, ge) = traits::overlapping_impls( + tcx, + possible_sibling, + impl_def_id, + traits::SkipLeakCheck::Yes, + overlap_mode, + |overlap| { + if let Some(overlap_kind) = + tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) + { + match overlap_kind { + ty::ImplOverlapKind::Permitted { marker: _ } => {} + ty::ImplOverlapKind::Issue33140 => { + *last_lint_mut = Some(FutureCompatOverlapError { + error: create_overlap_error(overlap), + kind: FutureCompatOverlapErrorKind::Issue33140, + }); + } + } + + return Ok((false, false)); + } + + let le = tcx.specializes((impl_def_id, possible_sibling)); + let ge = tcx.specializes((possible_sibling, impl_def_id)); + + if le == ge { + report_overlap_error(overlap, last_lint_mut) + } else { + Ok((le, ge)) + } + }, + || Ok((false, false)), + )?; + + if le && !ge { + debug!( + "descending as child of TraitRef {:?}", + tcx.impl_trait_ref(possible_sibling).unwrap() + ); + + // The impl specializes `possible_sibling`. + return Ok(Inserted::ShouldRecurseOn(possible_sibling)); + } else if ge && !le { + debug!( + "placing as parent of TraitRef {:?}", + tcx.impl_trait_ref(possible_sibling).unwrap() + ); + + replace_children.push(possible_sibling); + } else { + // Either there's no overlap, or the overlap was already reported by + // `overlap_error`. + } + } + + if !replace_children.is_empty() { + return Ok(Inserted::ReplaceChildren(replace_children)); + } + + // No overlap with any potential siblings, so add as a new sibling. + debug!("placing as new sibling"); + self.insert_blindly(tcx, impl_def_id); + Ok(Inserted::BecameNewSibling(last_lint)) + } +} + +fn iter_children(children: &mut Children) -> impl Iterator + '_ { + let nonblanket = children.non_blanket_impls.iter().flat_map(|(_, v)| v.iter()); + children.blanket_impls.iter().chain(nonblanket).cloned() +} + +fn filtered_children( + children: &mut Children, + st: SimplifiedType, +) -> impl Iterator + '_ { + let nonblanket = children.non_blanket_impls.entry(st).or_default().iter(); + children.blanket_impls.iter().chain(nonblanket).cloned() +} + +// A custom iterator used by Children::insert +enum PotentialSiblings +where + I: Iterator, + J: Iterator, +{ + Unfiltered(I), + Filtered(J), +} + +impl Iterator for PotentialSiblings +where + I: Iterator, + J: Iterator, +{ + type Item = DefId; + + fn next(&mut self) -> Option { + match *self { + PotentialSiblings::Unfiltered(ref mut iter) => iter.next(), + PotentialSiblings::Filtered(ref mut iter) => iter.next(), + } + } +} + +pub trait GraphExt { + /// Insert a local impl into the specialization graph. If an existing impl + /// conflicts with it (has overlap, but neither specializes the other), + /// information about the area of overlap is returned in the `Err`. + fn insert( + &mut self, + tcx: TyCtxt<'_>, + impl_def_id: DefId, + overlap_mode: OverlapMode, + ) -> Result, OverlapError>; + + /// Insert cached metadata mapping from a child impl back to its parent. + fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'_>, parent: DefId, child: DefId); +} + +impl GraphExt for Graph { + /// Insert a local impl into the specialization graph. If an existing impl + /// conflicts with it (has overlap, but neither specializes the other), + /// information about the area of overlap is returned in the `Err`. + fn insert( + &mut self, + tcx: TyCtxt<'_>, + impl_def_id: DefId, + overlap_mode: OverlapMode, + ) -> Result, OverlapError> { + assert!(impl_def_id.is_local()); + + let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + let trait_def_id = trait_ref.def_id; + + debug!( + "insert({:?}): inserting TraitRef {:?} into specialization graph", + impl_def_id, trait_ref + ); + + // If the reference itself contains an earlier error (e.g., due to a + // resolution failure), then we just insert the impl at the top level of + // the graph and claim that there's no overlap (in order to suppress + // bogus errors). + if trait_ref.references_error() { + debug!( + "insert: inserting dummy node for erroneous TraitRef {:?}, \ + impl_def_id={:?}, trait_def_id={:?}", + trait_ref, impl_def_id, trait_def_id + ); + + self.parent.insert(impl_def_id, trait_def_id); + self.children.entry(trait_def_id).or_default().insert_blindly(tcx, impl_def_id); + return Ok(None); + } + + let mut parent = trait_def_id; + let mut last_lint = None; + let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsInfer); + + // Descend the specialization tree, where `parent` is the current parent node. + loop { + use self::Inserted::*; + + let insert_result = self.children.entry(parent).or_default().insert( + tcx, + impl_def_id, + simplified, + overlap_mode, + )?; + + match insert_result { + BecameNewSibling(opt_lint) => { + last_lint = opt_lint; + break; + } + ReplaceChildren(grand_children_to_be) => { + // We currently have + // + // P + // | + // G + // + // and we are inserting the impl N. We want to make it: + // + // P + // | + // N + // | + // G + + // Adjust P's list of children: remove G and then add N. + { + let siblings = self.children.get_mut(&parent).unwrap(); + for &grand_child_to_be in &grand_children_to_be { + siblings.remove_existing(tcx, grand_child_to_be); + } + siblings.insert_blindly(tcx, impl_def_id); + } + + // Set G's parent to N and N's parent to P. + for &grand_child_to_be in &grand_children_to_be { + self.parent.insert(grand_child_to_be, impl_def_id); + } + self.parent.insert(impl_def_id, parent); + + // Add G as N's child. + for &grand_child_to_be in &grand_children_to_be { + self.children + .entry(impl_def_id) + .or_default() + .insert_blindly(tcx, grand_child_to_be); + } + break; + } + ShouldRecurseOn(new_parent) => { + parent = new_parent; + } + } + } + + self.parent.insert(impl_def_id, parent); + Ok(last_lint) + } + + /// Insert cached metadata mapping from a child impl back to its parent. + fn record_impl_from_cstore(&mut self, tcx: TyCtxt<'_>, parent: DefId, child: DefId) { + if self.parent.insert(child, parent).is_some() { + bug!( + "When recording an impl from the crate store, information about its parent \ + was already present." + ); + } + + self.children.entry(parent).or_default().insert_blindly(tcx, child); + } +} -- cgit v1.2.3