Type-directed probing for inherent associated types

2 files changed, 369 insertions, 54 deletions

diff --git a/compiler/rustc_hir_analysis/src/astconv/errors.rs b/compiler/rustc_hir_analysis/src/astconv/errors.rs
index 232ef2079d6..191f4f0f910 100644
--- a/compiler/rustc_hir_analysis/src/astconv/errors.rs
+++ b/compiler/rustc_hir_analysis/src/astconv/errors.rs
@@ -1,10 +1,10 @@
 use crate::astconv::AstConv;
 use crate::errors::{ManualImplementation, MissingTypeParams};
 use rustc_data_structures::fx::FxHashMap;
-use rustc_errors::{pluralize, struct_span_err, Applicability, ErrorGuaranteed};
+use rustc_errors::{pluralize, struct_span_err, Applicability, Diagnostic, ErrorGuaranteed};
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
-use rustc_middle::ty;
+use rustc_middle::ty::{self, Ty};
 use rustc_session::parse::feature_err;
 use rustc_span::lev_distance::find_best_match_for_name;
 use rustc_span::symbol::{sym, Ident};
@@ -221,6 +221,168 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         err.emit()
     }
 
+    // FIXME(inherent_associated_types): Find similarly named associated types and suggest them.
+    pub(crate) fn complain_about_inherent_assoc_type_not_found(
+        &self,
+        name: Ident,
+        self_ty: Ty<'tcx>,
+        candidates: &[DefId],
+        unsatisfied_predicates: Vec<ty::Predicate<'tcx>>,
+        span: Span,
+    ) -> ErrorGuaranteed {
+        let tcx = self.tcx();
+
+        let adt_did = self_ty.ty_adt_def().map(|def| def.did());
+        let add_def_label = |err: &mut Diagnostic| {
+            if let Some(did) = adt_did {
+                err.span_label(
+                    tcx.def_span(did),
+                    format!(
+                        "associated item `{name}` not found for this {}",
+                        tcx.def_kind(did).descr(did)
+                    ),
+                );
+            }
+        };
+
+        if unsatisfied_predicates.is_empty() {
+            // FIXME(fmease): Copied from `rustc_hir_typeck::method::probe`. Deduplicate.
+
+            let limit = if candidates.len() == 5 { 5 } else { 4 };
+            let type_candidates = candidates
+                .iter()
+                .take(limit)
+                .map(|candidate| {
+                    format!("- `{}`", tcx.at(span).type_of(candidate).subst_identity())
+                })
+                .collect::<Vec<_>>()
+                .join("\n");
+            let additional_types = if candidates.len() > limit {
+                format!("\nand {} more types", candidates.len() - limit)
+            } else {
+                String::new()
+            };
+
+            let mut err = struct_span_err!(
+                tcx.sess,
+                name.span,
+                E0220,
+                "associated type `{name}` not found for `{self_ty}` in the current scope"
+            );
+            err.span_label(name.span, format!("associated item not found in `{self_ty}`"));
+            err.note(&format!(
+                "the associated type was found for\n{type_candidates}{additional_types}",
+            ));
+            add_def_label(&mut err);
+            return err.emit();
+        }
+
+        let mut bound_spans = Vec::new();
+
+        // FIXME(fmease): Copied from `rustc_hir_typeck::method::probe`. Deduplicate.
+        let mut bound_span_label = |self_ty: Ty<'_>, obligation: &str, quiet: &str| {
+            let msg = format!(
+                "doesn't satisfy `{}`",
+                if obligation.len() > 50 { quiet } else { obligation }
+            );
+            match &self_ty.kind() {
+                // Point at the type that couldn't satisfy the bound.
+                ty::Adt(def, _) => bound_spans.push((tcx.def_span(def.did()), msg)),
+                // Point at the trait object that couldn't satisfy the bound.
+                ty::Dynamic(preds, _, _) => {
+                    for pred in preds.iter() {
+                        match pred.skip_binder() {
+                            ty::ExistentialPredicate::Trait(tr) => {
+                                bound_spans.push((tcx.def_span(tr.def_id), msg.clone()))
+                            }
+                            ty::ExistentialPredicate::Projection(_)
+                            | ty::ExistentialPredicate::AutoTrait(_) => {}
+                        }
+                    }
+                }
+                // Point at the closure that couldn't satisfy the bound.
+                ty::Closure(def_id, _) => {
+                    bound_spans.push((tcx.def_span(*def_id), format!("doesn't satisfy `{quiet}`")))
+                }
+                _ => {}
+            }
+        };
+
+        // FIXME(fmease): Copied from `rustc_hir_typeck::method::probe`. Deduplicate.
+        let format_pred = |pred: ty::Predicate<'tcx>| {
+            let bound_predicate = pred.kind();
+            match bound_predicate.skip_binder() {
+                ty::PredicateKind::Clause(ty::Clause::Projection(pred)) => {
+                    let pred = bound_predicate.rebind(pred);
+                    // `<Foo as Iterator>::Item = String`.
+                    let projection_ty = pred.skip_binder().projection_ty;
+
+                    let substs_with_infer_self = tcx.mk_substs(
+                        std::iter::once(tcx.mk_ty_var(ty::TyVid::from_u32(0)).into())
+                            .chain(projection_ty.substs.iter().skip(1)),
+                    );
+
+                    let quiet_projection_ty =
+                        tcx.mk_alias_ty(projection_ty.def_id, substs_with_infer_self);
+
+                    let term = pred.skip_binder().term;
+
+                    let obligation = format!("{projection_ty} = {term}");
+                    let quiet = format!("{quiet_projection_ty} = {term}");
+
+                    bound_span_label(projection_ty.self_ty(), &obligation, &quiet);
+                    Some((obligation, projection_ty.self_ty()))
+                }
+                ty::PredicateKind::Clause(ty::Clause::Trait(poly_trait_ref)) => {
+                    let p = poly_trait_ref.trait_ref;
+                    let self_ty = p.self_ty();
+                    let path = p.print_only_trait_path();
+                    let obligation = format!("{self_ty}: {path}");
+                    let quiet = format!("_: {path}");
+                    bound_span_label(self_ty, &obligation, &quiet);
+                    Some((obligation, self_ty))
+                }
+                _ => None,
+            }
+        };
+
+        // FIXME(fmease): `rustc_hir_typeck::method::suggest` uses a `skip_list` to filter out some bounds.
+        // I would do the same here if it didn't mean more code duplication.
+        let mut bounds: Vec<_> = unsatisfied_predicates
+            .into_iter()
+            .filter_map(format_pred)
+            .map(|(p, _)| format!("`{}`", p))
+            .collect();
+        bounds.sort();
+        bounds.dedup();
+
+        let mut err = tcx.sess.struct_span_err(
+            name.span,
+            &format!("the associated type `{name}` exists for `{self_ty}`, but its trait bounds were not satisfied")
+        );
+        if !bounds.is_empty() {
+            err.note(&format!(
+                "the following trait bounds were not satisfied:\n{}",
+                bounds.join("\n")
+            ));
+        }
+        err.span_label(
+            name.span,
+            format!("associated type cannot be referenced on `{self_ty}` due to unsatisfied trait bounds")
+        );
+
+        bound_spans.sort();
+        bound_spans.dedup();
+        for (span, msg) in bound_spans {
+            if !tcx.sess.source_map().is_span_accessible(span) {
+                continue;
+            }
+            err.span_label(span, &msg);
+        }
+        add_def_label(&mut err);
+        err.emit()
+    }
+
     /// When there are any missing associated types, emit an E0191 error and attempt to supply a
     /// reasonable suggestion on how to write it. For the case of multiple associated types in the
     /// same trait bound have the same name (as they come from different supertraits), we instead
diff --git a/compiler/rustc_hir_analysis/src/astconv/mod.rs b/compiler/rustc_hir_analysis/src/astconv/mod.rs
index 2ff47237b1b..92bff68cdbc 100644
--- a/compiler/rustc_hir_analysis/src/astconv/mod.rs
+++ b/compiler/rustc_hir_analysis/src/astconv/mod.rs
@@ -27,7 +27,10 @@ use rustc_hir::def::{CtorOf, DefKind, Namespace, Res};
 use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_hir::intravisit::{walk_generics, Visitor as _};
 use rustc_hir::{GenericArg, GenericArgs, OpaqueTyOrigin};
-use rustc_infer::infer::{InferCtxt, TyCtxtInferExt};
+use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
+use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt};
+use rustc_infer::traits::ObligationCause;
+use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
 use rustc_middle::middle::stability::AllowUnstable;
 use rustc_middle::ty::subst::{self, GenericArgKind, InternalSubsts, SubstsRef};
 use rustc_middle::ty::DynKind;
@@ -40,11 +43,12 @@ use rustc_span::symbol::{kw, Ident, Symbol};
 use rustc_span::{sym, Span, DUMMY_SP};
 use rustc_target::spec::abi;
 use rustc_trait_selection::traits;
-use rustc_trait_selection::traits::astconv_object_safety_violations;
 use rustc_trait_selection::traits::error_reporting::{
     report_object_safety_error, suggestions::NextTypeParamName,
 };
+use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt;
 use rustc_trait_selection::traits::wf::object_region_bounds;
+use rustc_trait_selection::traits::{astconv_object_safety_violations, NormalizeExt};
 
 use smallvec::{smallvec, SmallVec};
 use std::collections::BTreeSet;
@@ -2043,23 +2047,15 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                 }
             }
 
-            // see if we can satisfy using an inherent associated type
-            for &impl_ in tcx.inherent_impls(adt_def.did()) {
-                let Some(assoc_ty_did) = self.lookup_assoc_ty(assoc_ident, hir_ref_id, span, impl_) else {
-                    continue;
-                };
-                let ty::Adt(_, adt_substs) = qself_ty.kind() else {
-                    // FIXME(inherent_associated_types)
-                    bug!("unimplemented: non-adt self of inherent assoc ty");
-                };
-                let item_substs = self.create_substs_for_associated_item(
-                    span,
-                    assoc_ty_did,
-                    assoc_segment,
-                    adt_substs,
-                );
-                let ty = tcx.type_of(assoc_ty_did).subst(tcx, item_substs);
-                return Ok((ty, DefKind::AssocTy, assoc_ty_did));
+            if let Some((ty, did)) = self.lookup_inherent_assoc_ty(
+                assoc_ident,
+                assoc_segment,
+                adt_def.did(),
+                qself_ty,
+                hir_ref_id,
+                span,
+            )? {
+                return Ok((ty, DefKind::AssocTy, did));
             }
         }
 
@@ -2202,6 +2198,196 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         Ok((ty, DefKind::AssocTy, assoc_ty_did))
     }
 
+    fn lookup_inherent_assoc_ty(
+        &self,
+        name: Ident,
+        segment: &hir::PathSegment<'_>,
+        adt_did: DefId,
+        self_ty: Ty<'tcx>,
+        block: hir::HirId,
+        span: Span,
+    ) -> Result<Option<(Ty<'tcx>, DefId)>, ErrorGuaranteed> {
+        let tcx = self.tcx();
+
+        let candidates: Vec<_> = tcx
+            .inherent_impls(adt_did)
+            .iter()
+            .filter_map(|&impl_| Some((impl_, self.lookup_assoc_ty_unchecked(name, block, impl_)?)))
+            .collect();
+
+        if candidates.is_empty() {
+            return Ok(None);
+        }
+
+        let cause = ObligationCause::misc(span, block.owner.def_id);
+        let mut unsatisfied_predicates = Vec::new();
+
+        for &(impl_, (assoc_item, def_scope)) in &candidates {
+            let infcx = tcx.infer_ctxt().ignoring_regions().build();
+            let param_env = tcx.param_env(impl_);
+
+            let impl_ty = tcx.type_of(impl_);
+            let impl_substs = self.fresh_item_substs(impl_, &infcx);
+            let impl_ty = impl_ty.subst(tcx, impl_substs);
+
+            let InferOk { value: impl_ty, obligations } =
+                infcx.at(&cause, param_env).normalize(impl_ty);
+
+            // Check that the Self-types can be related.
+            let Ok(InferOk { obligations: sub_obligations, value: () }) = infcx
+                .at(&ObligationCause::dummy(), param_env)
+                .define_opaque_types(false)
+                .sup(impl_ty, self_ty)
+            else {
+                continue;
+            };
+
+            // Check whether the impl imposes obligations we have to worry about.
+            let impl_bounds = tcx.predicates_of(impl_);
+            let impl_bounds = impl_bounds.instantiate(tcx, impl_substs);
+
+            let InferOk { value: impl_bounds, obligations: norm_obligations } =
+                infcx.at(&cause, param_env).normalize(impl_bounds);
+
+            let impl_obligations =
+                traits::predicates_for_generics(|_, _| cause.clone(), param_env, impl_bounds);
+
+            let candidate_obligations = impl_obligations
+                .chain(norm_obligations.into_iter())
+                .chain(obligations.iter().cloned());
+
+            let mut matches = true;
+
+            // Evaluate those obligations to see if they might possibly hold.
+            for o in candidate_obligations {
+                let o = infcx.resolve_vars_if_possible(o);
+                if !infcx.predicate_may_hold(&o) {
+                    matches = false;
+                    unsatisfied_predicates.push(o.predicate);
+                }
+            }
+
+            // Evaluate those obligations to see if they might possibly hold.
+            for o in sub_obligations {
+                let o = infcx.resolve_vars_if_possible(o);
+                if !infcx.predicate_may_hold(&o) {
+                    matches = false;
+                    unsatisfied_predicates.push(o.predicate);
+                }
+            }
+
+            if !matches {
+                continue;
+            }
+
+            self.check_assoc_ty(assoc_item, name, def_scope, block, span);
+
+            let ty::Adt(_, adt_substs) = self_ty.kind() else {
+                bug!("unreachable: `lookup_inherent_assoc_ty` is only called on ADTs");
+            };
+
+            let item_substs =
+                self.create_substs_for_associated_item(span, assoc_item, segment, adt_substs);
+            // FIXME(inherent_associated_types): Check if the obligations arising from the
+            // where-clause & the bounds on the associated type and its parameters hold.
+            let ty = tcx.type_of(assoc_item).subst(tcx, item_substs);
+            return Ok(Some((ty, assoc_item)));
+        }
+
+        Err(self.complain_about_inherent_assoc_type_not_found(
+            name,
+            self_ty,
+            &candidates.into_iter().map(|(impl_, _)| impl_).collect::<Vec<_>>(),
+            unsatisfied_predicates,
+            span,
+        ))
+    }
+
+    // FIXME(fmease): Copied from `rustc_hir_typeck::method::probe`. Deduplicate.
+    fn fresh_item_substs(&self, def_id: DefId, infcx: &InferCtxt<'tcx>) -> SubstsRef<'tcx> {
+        let tcx = self.tcx();
+
+        InternalSubsts::for_item(tcx, def_id, |param, _| match param.kind {
+            GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
+            GenericParamDefKind::Type { .. } => infcx
+                .next_ty_var(TypeVariableOrigin {
+                    kind: TypeVariableOriginKind::SubstitutionPlaceholder,
+                    span: tcx.def_span(def_id),
+                })
+                .into(),
+            GenericParamDefKind::Const { .. } => {
+                let span = tcx.def_span(def_id);
+                let origin = ConstVariableOrigin {
+                    kind: ConstVariableOriginKind::SubstitutionPlaceholder,
+                    span,
+                };
+                infcx
+                    .next_const_var(
+                        tcx.type_of(param.def_id)
+                            .no_bound_vars()
+                            .expect("const parameter types cannot be generic"),
+                        origin,
+                    )
+                    .into()
+            }
+        })
+    }
+
+    fn lookup_assoc_ty(
+        &self,
+        name: Ident,
+        block: hir::HirId,
+        span: Span,
+        scope: DefId,
+    ) -> Option<DefId> {
+        let (item, def_scope) = self.lookup_assoc_ty_unchecked(name, block, scope)?;
+        self.check_assoc_ty(item, name, def_scope, block, span);
+        Some(item)
+    }
+
+    fn lookup_assoc_ty_unchecked(
+        &self,
+        name: Ident,
+        block: hir::HirId,
+        scope: DefId,
+    ) -> Option<(DefId, DefId)> {
+        let tcx = self.tcx();
+        let (ident, def_scope) = tcx.adjust_ident_and_get_scope(name, scope, block);
+
+        // We have already adjusted the item name above, so compare with `ident.normalize_to_macros_2_0()` instead
+        // of calling `find_by_name_and_kind`.
+        let item = tcx.associated_items(scope).in_definition_order().find(|i| {
+            i.kind.namespace() == Namespace::TypeNS
+                && i.ident(tcx).normalize_to_macros_2_0() == ident
+        })?;
+
+        Some((item.def_id, def_scope))
+    }
+
+    fn check_assoc_ty(
+        &self,
+        item: DefId,
+        name: Ident,
+        def_scope: DefId,
+        block: hir::HirId,
+        span: Span,
+    ) {
+        let tcx = self.tcx();
+        let kind = DefKind::AssocTy;
+
+        if !tcx.visibility(item).is_accessible_from(def_scope, tcx) {
+            let kind = kind.descr(item);
+            let msg = format!("{kind} `{name}` is private");
+            let def_span = tcx.def_span(item);
+            tcx.sess
+                .struct_span_err_with_code(span, &msg, rustc_errors::error_code!(E0624))
+                .span_label(span, &format!("private {kind}"))
+                .span_label(def_span, &format!("{kind} defined here"))
+                .emit();
+        }
+        tcx.check_stability(item, Some(block), span, None);
+    }
+
     fn probe_traits_that_match_assoc_ty(
         &self,
         qself_ty: Ty<'tcx>,
@@ -2255,39 +2441,6 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             .collect()
     }
 
-    fn lookup_assoc_ty(
-        &self,
-        ident: Ident,
-        block: hir::HirId,
-        span: Span,
-        scope: DefId,
-    ) -> Option<DefId> {
-        let tcx = self.tcx();
-        let (ident, def_scope) = tcx.adjust_ident_and_get_scope(ident, scope, block);
-
-        // We have already adjusted the item name above, so compare with `ident.normalize_to_macros_2_0()` instead
-        // of calling `find_by_name_and_kind`.
-        let item = tcx.associated_items(scope).in_definition_order().find(|i| {
-            i.kind.namespace() == Namespace::TypeNS
-                && i.ident(tcx).normalize_to_macros_2_0() == ident
-        })?;
-
-        let kind = DefKind::AssocTy;
-        if !item.visibility(tcx).is_accessible_from(def_scope, tcx) {
-            let kind = kind.descr(item.def_id);
-            let msg = format!("{kind} `{ident}` is private");
-            let def_span = self.tcx().def_span(item.def_id);
-            tcx.sess
-                .struct_span_err_with_code(span, &msg, rustc_errors::error_code!(E0624))
-                .span_label(span, &format!("private {kind}"))
-                .span_label(def_span, &format!("{kind} defined here"))
-                .emit();
-        }
-        tcx.check_stability(item.def_id, Some(block), span, None);
-
-        Some(item.def_id)
-    }
-
     fn qpath_to_ty(
         &self,
         span: Span,