Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

2 files changed, 926 insertions, 0 deletions

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<String>,
+    pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause>,
+    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<T, U> Foo for (T, U) { ... }  // target impl
+/// impl<V> 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<I>
+///    where I: Iterator<Item = &'a T>, 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<SubstsRef<'tcx>, ()> {
+    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 = <dyn TraitEngine<'tcx>>::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<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: 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<FutureCompatOverlapErrorKind>,
+    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<G: EmissionGuarantee>(
+        tcx: TyCtxt<'_>,
+        overlap: OverlapError,
+        used_to_be_allowed: Option<FutureCompatOverlapErrorKind>,
+        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<String> {
+    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::<Vec<_>>()
+                .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<FutureCompatOverlapError>),
+
+    /// The impl should replace existing impls [X1, ..], because the impl specializes X1, X2, etc.
+    ReplaceChildren(Vec<DefId>),
+
+    /// 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<SimplifiedType>,
+        overlap_mode: OverlapMode,
+    ) -> Result<Inserted, OverlapError>;
+}
+
+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<DefId>;
+        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<SimplifiedType>,
+        overlap_mode: OverlapMode,
+    ) -> Result<Inserted, OverlapError> {
+        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<Item = DefId> + '_ {
+    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<Item = DefId> + '_ {
+    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<I, J>
+where
+    I: Iterator<Item = DefId>,
+    J: Iterator<Item = DefId>,
+{
+    Unfiltered(I),
+    Filtered(J),
+}
+
+impl<I, J> Iterator for PotentialSiblings<I, J>
+where
+    I: Iterator<Item = DefId>,
+    J: Iterator<Item = DefId>,
+{
+    type Item = DefId;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        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<Option<FutureCompatOverlapError>, 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<Option<FutureCompatOverlapError>, 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);
+    }
+}