Rollup merge of #70535 - jonas-schievink:graph-refactor, r=nikomatsakis

Track the finalizing node in the specialization graph

Fixes https://github.com/rust-lang/rust/issues/70419
Fixes https://github.com/rust-lang/rust/issues/70442

r? @eddyb

9 files changed, 149 insertions, 121 deletions

diff --git a/src/librustc_middle/traits/specialization_graph.rs b/src/librustc_middle/traits/specialization_graph.rs
index 1847326a742..a2793f98050 100644
--- a/src/librustc_middle/traits/specialization_graph.rs
+++ b/src/librustc_middle/traits/specialization_graph.rs
@@ -154,14 +154,44 @@ impl Iterator for Ancestors<'_> {
     }
 }
 
-pub struct NodeItem<T> {
-    pub node: Node,
-    pub item: T,
+/// Information about the most specialized definition of an associated item.
+pub struct LeafDef {
+    /// The associated item described by this `LeafDef`.
+    pub item: ty::AssocItem,
+
+    /// The node in the specialization graph containing the definition of `item`.
+    pub defining_node: Node,
+
+    /// The "top-most" (ie. least specialized) specialization graph node that finalized the
+    /// definition of `item`.
+    ///
+    /// Example:
+    ///
+    /// ```
+    /// trait Tr {
+    ///     fn assoc(&self);
+    /// }
+    ///
+    /// impl<T> Tr for T {
+    ///     default fn assoc(&self) {}
+    /// }
+    ///
+    /// impl Tr for u8 {}
+    /// ```
+    ///
+    /// If we start the leaf definition search at `impl Tr for u8`, that impl will be the
+    /// `finalizing_node`, while `defining_node` will be the generic impl.
+    ///
+    /// If the leaf definition search is started at the generic impl, `finalizing_node` will be
+    /// `None`, since the most specialized impl we found still allows overriding the method
+    /// (doesn't finalize it).
+    pub finalizing_node: Option<Node>,
 }
 
-impl<T> NodeItem<T> {
-    pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> NodeItem<U> {
-        NodeItem { node: self.node, item: f(self.item) }
+impl LeafDef {
+    /// Returns whether this definition is known to not be further specializable.
+    pub fn is_final(&self) -> bool {
+        self.finalizing_node.is_some()
     }
 }
 
@@ -173,18 +203,36 @@ impl<'tcx> Ancestors<'tcx> {
         tcx: TyCtxt<'tcx>,
         trait_item_name: Ident,
         trait_item_kind: ty::AssocKind,
-    ) -> Option<NodeItem<ty::AssocItem>> {
+    ) -> Option<LeafDef> {
         let trait_def_id = self.trait_def_id;
+        let mut finalizing_node = None;
+
         self.find_map(|node| {
-            node.item(tcx, trait_item_name, trait_item_kind, trait_def_id)
-                .map(|item| NodeItem { node, item })
+            if let Some(item) = node.item(tcx, trait_item_name, trait_item_kind, trait_def_id) {
+                if finalizing_node.is_none() {
+                    let is_specializable = item.defaultness.is_default()
+                        || tcx.impl_defaultness(node.def_id()).is_default();
+
+                    if !is_specializable {
+                        finalizing_node = Some(node);
+                    }
+                }
+
+                Some(LeafDef { item, defining_node: node, finalizing_node })
+            } else {
+                // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor.
+                finalizing_node = Some(node);
+                None
+            }
         })
     }
 }
 
 /// Walk up the specialization ancestors of a given impl, starting with that
-/// impl itself. Returns `None` if an error was reported while building the
-/// specialization graph.
+/// impl itself.
+///
+/// Returns `Err` if an error was reported while building the specialization
+/// graph.
 pub fn ancestors(
     tcx: TyCtxt<'tcx>,
     trait_def_id: DefId,
diff --git a/src/librustc_trait_selection/traits/mod.rs b/src/librustc_trait_selection/traits/mod.rs
index 3ef44a19841..5f988506330 100644
--- a/src/librustc_trait_selection/traits/mod.rs
+++ b/src/librustc_trait_selection/traits/mod.rs
@@ -54,7 +54,6 @@ pub use self::project::{
 };
 pub use self::select::{EvaluationCache, SelectionCache, SelectionContext};
 pub use self::select::{EvaluationResult, IntercrateAmbiguityCause, OverflowError};
-pub use self::specialize::find_associated_item;
 pub use self::specialize::specialization_graph::FutureCompatOverlapError;
 pub use self::specialize::specialization_graph::FutureCompatOverlapErrorKind;
 pub use self::specialize::{specialization_graph, translate_substs, OverlapError};
@@ -64,8 +63,7 @@ pub use self::structural_match::NonStructuralMatchTy;
 pub use self::util::{elaborate_predicates, elaborate_trait_ref, elaborate_trait_refs};
 pub use self::util::{expand_trait_aliases, TraitAliasExpander};
 pub use self::util::{
-    get_vtable_index_of_object_method, impl_is_default, impl_item_is_final,
-    predicate_for_trait_def, upcast_choices,
+    get_vtable_index_of_object_method, impl_item_is_final, predicate_for_trait_def, upcast_choices,
 };
 pub use self::util::{
     supertrait_def_ids, supertraits, transitive_bounds, SupertraitDefIds, Supertraits,
diff --git a/src/librustc_trait_selection/traits/project.rs b/src/librustc_trait_selection/traits/project.rs
index 2eb63b8f590..aae0d467563 100644
--- a/src/librustc_trait_selection/traits/project.rs
+++ b/src/librustc_trait_selection/traits/project.rs
@@ -1015,49 +1015,21 @@ fn assemble_candidates_from_impls<'cx, 'tcx>(
                     assoc_ty_def(selcx, impl_data.impl_def_id, obligation.predicate.item_def_id)
                         .map_err(|ErrorReported| ())?;
 
-                let is_default = if node_item.node.is_from_trait() {
-                    // If true, the impl inherited a `type Foo = Bar`
-                    // given in the trait, which is implicitly default.
-                    // Otherwise, the impl did not specify `type` and
-                    // neither did the trait:
-                    //
-                    // ```rust
-                    // trait Foo { type T; }
-                    // impl Foo for Bar { }
-                    // ```
-                    //
-                    // This is an error, but it will be
-                    // reported in `check_impl_items_against_trait`.
-                    // We accept it here but will flag it as
-                    // an error when we confirm the candidate
-                    // (which will ultimately lead to `normalize_to_error`
-                    // being invoked).
-                    false
+                if node_item.is_final() {
+                    // Non-specializable items are always projectable.
+                    true
                 } else {
-                    // If we're looking at a trait *impl*, the item is
-                    // specializable if the impl or the item are marked
-                    // `default`.
-                    node_item.item.defaultness.is_default()
-                        || super::util::impl_is_default(selcx.tcx(), node_item.node.def_id())
-                };
-
-                match is_default {
-                    // Non-specializable items are always projectable
-                    false => true,
-
                     // Only reveal a specializable default if we're past type-checking
                     // and the obligation is monomorphic, otherwise passes such as
                     // transmute checking and polymorphic MIR optimizations could
                     // get a result which isn't correct for all monomorphizations.
-                    true if obligation.param_env.reveal == Reveal::All => {
+                    if obligation.param_env.reveal == Reveal::All {
                         // NOTE(eddyb) inference variables can resolve to parameters, so
                         // assume `poly_trait_ref` isn't monomorphic, if it contains any.
                         let poly_trait_ref =
                             selcx.infcx().resolve_vars_if_possible(&poly_trait_ref);
                         !poly_trait_ref.needs_infer() && !poly_trait_ref.needs_subst()
-                    }
-
-                    true => {
+                    } else {
                         debug!(
                             "assemble_candidates_from_impls: not eligible due to default: \
                              assoc_ty={} predicate={}",
@@ -1422,7 +1394,8 @@ fn confirm_impl_candidate<'cx, 'tcx>(
         return Progress { ty: tcx.types.err, obligations: nested };
     }
     let substs = obligation.predicate.substs.rebase_onto(tcx, trait_def_id, substs);
-    let substs = translate_substs(selcx.infcx(), param_env, impl_def_id, substs, assoc_ty.node);
+    let substs =
+        translate_substs(selcx.infcx(), param_env, impl_def_id, substs, assoc_ty.defining_node);
     let ty = if let ty::AssocKind::OpaqueTy = assoc_ty.item.kind {
         let item_substs = InternalSubsts::identity_for_item(tcx, assoc_ty.item.def_id);
         tcx.mk_opaque(assoc_ty.item.def_id, item_substs)
@@ -1447,7 +1420,7 @@ fn assoc_ty_def(
     selcx: &SelectionContext<'_, '_>,
     impl_def_id: DefId,
     assoc_ty_def_id: DefId,
-) -> Result<specialization_graph::NodeItem<ty::AssocItem>, ErrorReported> {
+) -> Result<specialization_graph::LeafDef, ErrorReported> {
     let tcx = selcx.tcx();
     let assoc_ty_name = tcx.associated_item(assoc_ty_def_id).ident;
     let trait_def_id = tcx.impl_trait_ref(impl_def_id).unwrap().def_id;
@@ -1464,9 +1437,10 @@ fn assoc_ty_def(
         if matches!(item.kind, ty::AssocKind::Type | ty::AssocKind::OpaqueTy)
             && tcx.hygienic_eq(item.ident, assoc_ty_name, trait_def_id)
         {
-            return Ok(specialization_graph::NodeItem {
-                node: specialization_graph::Node::Impl(impl_def_id),
+            return Ok(specialization_graph::LeafDef {
                 item: *item,
+                defining_node: impl_node,
+                finalizing_node: if item.defaultness.is_default() { None } else { Some(impl_node) },
             });
         }
     }
diff --git a/src/librustc_trait_selection/traits/specialize/mod.rs b/src/librustc_trait_selection/traits/specialize/mod.rs
index edf02d75ee6..fabd8c89b72 100644
--- a/src/librustc_trait_selection/traits/specialize/mod.rs
+++ b/src/librustc_trait_selection/traits/specialize/mod.rs
@@ -20,7 +20,7 @@ use rustc_errors::struct_span_err;
 use rustc_hir::def_id::DefId;
 use rustc_middle::lint::LintDiagnosticBuilder;
 use rustc_middle::ty::subst::{InternalSubsts, Subst, SubstsRef};
-use rustc_middle::ty::{self, TyCtxt, TypeFoldable};
+use rustc_middle::ty::{self, TyCtxt};
 use rustc_session::lint::builtin::COHERENCE_LEAK_CHECK;
 use rustc_session::lint::builtin::ORDER_DEPENDENT_TRAIT_OBJECTS;
 use rustc_span::DUMMY_SP;
@@ -112,48 +112,6 @@ pub fn translate_substs<'a, 'tcx>(
     source_substs.rebase_onto(infcx.tcx, source_impl, target_substs)
 }
 
-/// Given a selected impl described by `impl_data`, returns the
-/// definition and substitutions for the method with the name `name`
-/// the kind `kind`, and trait method substitutions `substs`, in
-/// that impl, a less specialized impl, or the trait default,
-/// whichever applies.
-pub fn find_associated_item<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    param_env: ty::ParamEnv<'tcx>,
-    item: &ty::AssocItem,
-    substs: SubstsRef<'tcx>,
-    impl_data: &super::VtableImplData<'tcx, ()>,
-) -> (DefId, SubstsRef<'tcx>) {
-    debug!("find_associated_item({:?}, {:?}, {:?}, {:?})", param_env, item, substs, impl_data);
-    assert!(!substs.needs_infer());
-
-    let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap();
-    let trait_def = tcx.trait_def(trait_def_id);
-
-    if let Ok(ancestors) = trait_def.ancestors(tcx, impl_data.impl_def_id) {
-        match ancestors.leaf_def(tcx, item.ident, item.kind) {
-            Some(node_item) => {
-                let substs = tcx.infer_ctxt().enter(|infcx| {
-                    let param_env = param_env.with_reveal_all();
-                    let substs = substs.rebase_onto(tcx, trait_def_id, impl_data.substs);
-                    let substs = translate_substs(
-                        &infcx,
-                        param_env,
-                        impl_data.impl_def_id,
-                        substs,
-                        node_item.node,
-                    );
-                    infcx.tcx.erase_regions(&substs)
-                });
-                (node_item.item.def_id, substs)
-            }
-            None => bug!("{:?} not found in {:?}", item, impl_data.impl_def_id),
-        }
-    } else {
-        (item.def_id, substs)
-    }
-}
-
 /// Is `impl1` a specialization of `impl2`?
 ///
 /// Specialization is determined by the sets of types to which the impls apply;
diff --git a/src/librustc_trait_selection/traits/util.rs b/src/librustc_trait_selection/traits/util.rs
index 6eeac2f676c..6348673dab8 100644
--- a/src/librustc_trait_selection/traits/util.rs
+++ b/src/librustc_trait_selection/traits/util.rs
@@ -4,7 +4,6 @@ use smallvec::smallvec;
 use smallvec::SmallVec;
 
 use rustc_data_structures::fx::FxHashSet;
-use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
 use rustc_middle::ty::outlives::Component;
 use rustc_middle::ty::subst::{GenericArg, Subst, SubstsRef};
@@ -651,22 +650,8 @@ pub fn generator_trait_ref_and_outputs(
     ty::Binder::bind((trait_ref, sig.skip_binder().yield_ty, sig.skip_binder().return_ty))
 }
 
-pub fn impl_is_default(tcx: TyCtxt<'_>, node_item_def_id: DefId) -> bool {
-    match tcx.hir().as_local_hir_id(node_item_def_id) {
-        Some(hir_id) => {
-            let item = tcx.hir().expect_item(hir_id);
-            if let hir::ItemKind::Impl { defaultness, .. } = item.kind {
-                defaultness.is_default()
-            } else {
-                false
-            }
-        }
-        None => tcx.impl_defaultness(node_item_def_id).is_default(),
-    }
-}
-
 pub fn impl_item_is_final(tcx: TyCtxt<'_>, assoc_item: &ty::AssocItem) -> bool {
-    assoc_item.defaultness.is_final() && !impl_is_default(tcx, assoc_item.container.id())
+    assoc_item.defaultness.is_final() && tcx.impl_defaultness(assoc_item.container.id()).is_final()
 }
 
 pub enum TupleArgumentsFlag {
diff --git a/src/librustc_ty/instance.rs b/src/librustc_ty/instance.rs
index 447c49e40fb..47c4b1c41cd 100644
--- a/src/librustc_ty/instance.rs
+++ b/src/librustc_ty/instance.rs
@@ -1,9 +1,11 @@
 use rustc_hir::def_id::DefId;
+use rustc_infer::infer::TyCtxtInferExt;
 use rustc_middle::ty::subst::SubstsRef;
 use rustc_middle::ty::{self, Instance, TyCtxt, TypeFoldable};
 use rustc_span::sym;
 use rustc_target::spec::abi::Abi;
 use rustc_trait_selection::traits;
+use traits::{translate_substs, Reveal};
 
 use log::debug;
 
@@ -82,21 +84,50 @@ fn resolve_associated_item<'tcx>(
     // the actual function:
     match vtbl {
         traits::VtableImpl(impl_data) => {
-            let (def_id, substs) =
-                traits::find_associated_item(tcx, param_env, trait_item, rcvr_substs, &impl_data);
-
-            let resolved_item = tcx.associated_item(def_id);
+            debug!(
+                "resolving VtableImpl: {:?}, {:?}, {:?}, {:?}",
+                param_env, trait_item, rcvr_substs, impl_data
+            );
+            assert!(!rcvr_substs.needs_infer());
+            assert!(!trait_ref.needs_infer());
+
+            let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap();
+            let trait_def = tcx.trait_def(trait_def_id);
+            let leaf_def = trait_def
+                .ancestors(tcx, impl_data.impl_def_id)
+                .ok()?
+                .leaf_def(tcx, trait_item.ident, trait_item.kind)
+                .unwrap_or_else(|| {
+                    bug!("{:?} not found in {:?}", trait_item, impl_data.impl_def_id);
+                });
+            let def_id = leaf_def.item.def_id;
+
+            let substs = tcx.infer_ctxt().enter(|infcx| {
+                let param_env = param_env.with_reveal_all();
+                let substs = rcvr_substs.rebase_onto(tcx, trait_def_id, impl_data.substs);
+                let substs = translate_substs(
+                    &infcx,
+                    param_env,
+                    impl_data.impl_def_id,
+                    substs,
+                    leaf_def.defining_node,
+                );
+                infcx.tcx.erase_regions(&substs)
+            });
 
             // Since this is a trait item, we need to see if the item is either a trait default item
             // or a specialization because we can't resolve those unless we can `Reveal::All`.
             // NOTE: This should be kept in sync with the similar code in
             // `rustc_middle::traits::project::assemble_candidates_from_impls()`.
-            let eligible = if !resolved_item.defaultness.is_default() {
+            let eligible = if leaf_def.is_final() {
+                // Non-specializable items are always projectable.
                 true
-            } else if param_env.reveal == traits::Reveal::All {
-                !trait_ref.needs_subst()
             } else {
-                false
+                // Only reveal a specializable default if we're past type-checking
+                // and the obligation is monomorphic, otherwise passes such as
+                // transmute checking and polymorphic MIR optimizations could
+                // get a result which isn't correct for all monomorphizations.
+                if param_env.reveal == Reveal::All { !trait_ref.needs_subst() } else { false }
             };
 
             if !eligible {
diff --git a/src/librustc_ty/ty.rs b/src/librustc_ty/ty.rs
index 9d28447e212..aefe61f60b8 100644
--- a/src/librustc_ty/ty.rs
+++ b/src/librustc_ty/ty.rs
@@ -165,6 +165,16 @@ fn associated_item(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItem {
     )
 }
 
+fn impl_defaultness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::Defaultness {
+    let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
+    let item = tcx.hir().expect_item(hir_id);
+    if let hir::ItemKind::Impl { defaultness, .. } = item.kind {
+        defaultness
+    } else {
+        bug!("`impl_defaultness` called on {:?}", item);
+    }
+}
+
 /// Calculates the `Sized` constraint.
 ///
 /// In fact, there are only a few options for the types in the constraint:
@@ -371,6 +381,7 @@ pub fn provide(providers: &mut ty::query::Providers<'_>) {
         crate_hash,
         instance_def_size_estimate,
         issue33140_self_ty,
+        impl_defaultness,
         ..*providers
     };
 }
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 6249e1d4977..3823efe9d92 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1942,7 +1942,7 @@ fn check_specialization_validity<'tcx>(
             // grandparent. In that case, if parent is a `default impl`, inherited items use the
             // "defaultness" from the grandparent, else they are final.
             None => {
-                if traits::impl_is_default(tcx, parent_impl.def_id()) {
+                if tcx.impl_defaultness(parent_impl.def_id()).is_default() {
                     None
                 } else {
                     Some(Err(parent_impl.def_id()))
@@ -2114,10 +2114,10 @@ fn check_impl_items_against_trait<'tcx>(
         for trait_item in tcx.associated_items(impl_trait_ref.def_id).in_definition_order() {
             let is_implemented = ancestors
                 .leaf_def(tcx, trait_item.ident, trait_item.kind)
-                .map(|node_item| !node_item.node.is_from_trait())
+                .map(|node_item| !node_item.defining_node.is_from_trait())
                 .unwrap_or(false);
 
-            if !is_implemented && !traits::impl_is_default(tcx, impl_id) {
+            if !is_implemented && tcx.impl_defaultness(impl_id).is_final() {
                 if !trait_item.defaultness.has_value() {
                     missing_items.push(*trait_item);
                 }
diff --git a/src/test/ui/specialization/issue-70442.rs b/src/test/ui/specialization/issue-70442.rs
new file mode 100644
index 00000000000..4371dd2e167
--- /dev/null
+++ b/src/test/ui/specialization/issue-70442.rs
@@ -0,0 +1,23 @@
+#![feature(specialization)]
+
+// check-pass
+
+trait Trait {
+    type Assoc;
+}
+
+impl<T> Trait for T {
+    default type Assoc = bool;
+}
+
+// This impl inherits the `Assoc` definition from above and "locks it in", or finalizes it, making
+// child impls unable to further specialize it. However, since the specialization graph didn't
+// correctly track this, we would refuse to project `Assoc` from this impl, even though that should
+// happen for items that are final.
+impl Trait for () {}
+
+fn foo<X: Trait<Assoc=bool>>() {}
+
+fn main() {
+    foo::<()>();  // `<() as Trait>::Assoc` is normalized to `bool` correctly
+}