Merge #10456

10456: fix: Avoid cycle when lowering predicates for associated item lookup r=flodiebold a=jonas-schievink

Fixes https://github.com/rust-analyzer/rust-analyzer/issues/10386

(the salsa bug persists, but this lets us avoid it by fixing the underlying bug)

This reimplements the rustc logic in https://github.com/rust-lang/rust/blob/b27661eb33c74cb514dba059b47d86b6582ac1c2/compiler/rustc_typeck/src/collect.rs#L556: When resolving an associated type `T::Item`, we've previously lowered all predicates that could affect `T`, but we actually have to look only at those predicates whose traits define an associated type of the right name.

Co-authored-by: Jonas Schievink <jonasschievink@gmail.com>

6 files changed, 65 insertions, 17 deletions

diff --git a/crates/hir/src/display.rs b/crates/hir/src/display.rs
index aa4f25a3b44..a541cbd5e18 100644
--- a/crates/hir/src/display.rs
+++ b/crates/hir/src/display.rs
@@ -241,7 +241,7 @@ impl HirDisplay for TypeParam {
             return Ok(());
         }
 
-        let bounds = f.db.generic_predicates_for_param(self.id);
+        let bounds = f.db.generic_predicates_for_param(self.id, None);
         let substs = TyBuilder::type_params_subst(f.db, self.id.parent);
         let predicates: Vec<_> =
             bounds.iter().cloned().map(|b| b.substitute(&Interner, &substs)).collect();
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index ff795d85be4..a33c8ce65eb 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -2024,7 +2024,7 @@ impl TypeParam {
     }
 
     pub fn trait_bounds(self, db: &dyn HirDatabase) -> Vec<Trait> {
-        db.generic_predicates_for_param(self.id)
+        db.generic_predicates_for_param(self.id, None)
             .iter()
             .filter_map(|pred| match &pred.skip_binders().skip_binders() {
                 hir_ty::WhereClause::Implemented(trait_ref) => {
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index b9003c413bb..98a58490012 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -61,6 +61,7 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
     fn generic_predicates_for_param(
         &self,
         param_id: TypeParamId,
+        assoc_name: Option<Name>,
     ) -> Arc<[Binders<QuantifiedWhereClause>]>;
 
     #[salsa::invoke(crate::lower::generic_predicates_query)]
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index 3734eb10131..d5f3940149f 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -30,6 +30,7 @@ use smallvec::SmallVec;
 use stdx::impl_from;
 use syntax::ast;
 
+use crate::all_super_traits;
 use crate::{
     consteval,
     db::HirDatabase,
@@ -531,9 +532,10 @@ impl<'a> TyLoweringContext<'a> {
 
     fn select_associated_type(&self, res: Option<TypeNs>, segment: PathSegment<'_>) -> Ty {
         if let Some(res) = res {
-            let ty = associated_type_shorthand_candidates(
+            let ty = named_associated_type_shorthand_candidates(
                 self.db,
                 res,
+                Some(segment.name.clone()),
                 move |name, t, associated_ty| {
                     if name == segment.name {
                         let substs = match self.type_param_mode {
@@ -555,16 +557,16 @@ impl<'a> TyLoweringContext<'a> {
                         // associated_type_shorthand_candidates does not do that
                         let substs = substs.shifted_in_from(&Interner, self.in_binders);
                         // FIXME handle type parameters on the segment
-                        return Some(
+                        Some(
                             TyKind::Alias(AliasTy::Projection(ProjectionTy {
                                 associated_ty_id: to_assoc_type_id(associated_ty),
                                 substitution: substs,
                             }))
                             .intern(&Interner),
-                        );
+                        )
+                    } else {
+                        None
                     }
-
-                    None
                 },
             );
 
@@ -935,6 +937,15 @@ pub fn callable_item_sig(db: &dyn HirDatabase, def: CallableDefId) -> PolyFnSig
 pub fn associated_type_shorthand_candidates<R>(
     db: &dyn HirDatabase,
     res: TypeNs,
+    cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
+) -> Option<R> {
+    named_associated_type_shorthand_candidates(db, res, None, cb)
+}
+
+fn named_associated_type_shorthand_candidates<R>(
+    db: &dyn HirDatabase,
+    res: TypeNs,
+    assoc_name: Option<Name>,
     mut cb: impl FnMut(&Name, &TraitRef, TypeAliasId) -> Option<R>,
 ) -> Option<R> {
     let mut search = |t| {
@@ -959,7 +970,7 @@ pub fn associated_type_shorthand_candidates<R>(
             db.impl_trait(impl_id)?.into_value_and_skipped_binders().0,
         ),
         TypeNs::GenericParam(param_id) => {
-            let predicates = db.generic_predicates_for_param(param_id);
+            let predicates = db.generic_predicates_for_param(param_id, assoc_name);
             let res = predicates.iter().find_map(|pred| match pred.skip_binders().skip_binders() {
                 // FIXME: how to correctly handle higher-ranked bounds here?
                 WhereClause::Implemented(tr) => search(
@@ -1022,6 +1033,7 @@ pub(crate) fn field_types_query(
 pub(crate) fn generic_predicates_for_param_query(
     db: &dyn HirDatabase,
     param_id: TypeParamId,
+    assoc_name: Option<Name>,
 ) -> Arc<[Binders<QuantifiedWhereClause>]> {
     let resolver = param_id.parent.resolver(db.upcast());
     let ctx =
@@ -1031,13 +1043,46 @@ pub(crate) fn generic_predicates_for_param_query(
         .where_predicates_in_scope()
         // we have to filter out all other predicates *first*, before attempting to lower them
         .filter(|pred| match pred {
-            WherePredicate::ForLifetime { target, .. }
-            | WherePredicate::TypeBound { target, .. } => match target {
-                WherePredicateTypeTarget::TypeRef(type_ref) => {
-                    ctx.lower_ty_only_param(type_ref) == Some(param_id)
+            WherePredicate::ForLifetime { target, bound, .. }
+            | WherePredicate::TypeBound { target, bound, .. } => {
+                match target {
+                    WherePredicateTypeTarget::TypeRef(type_ref) => {
+                        if ctx.lower_ty_only_param(type_ref) != Some(param_id) {
+                            return false;
+                        }
+                    }
+                    WherePredicateTypeTarget::TypeParam(local_id) => {
+                        if *local_id != param_id.local_id {
+                            return false;
+                        }
+                    }
+                };
+
+                match &**bound {
+                    TypeBound::ForLifetime(_, path) | TypeBound::Path(path, _) => {
+                        // Only lower the bound if the trait could possibly define the associated
+                        // type we're looking for.
+
+                        let assoc_name = match &assoc_name {
+                            Some(it) => it,
+                            None => return true,
+                        };
+                        let tr = match resolver
+                            .resolve_path_in_type_ns_fully(db.upcast(), path.mod_path())
+                        {
+                            Some(TypeNs::TraitId(tr)) => tr,
+                            _ => return false,
+                        };
+
+                        all_super_traits(db.upcast(), tr).iter().any(|tr| {
+                            db.trait_data(*tr).items.iter().any(|(name, item)| {
+                                matches!(item, AssocItemId::TypeAliasId(_)) && name == assoc_name
+                            })
+                        })
+                    }
+                    TypeBound::Lifetime(_) | TypeBound::Error => false,
                 }
-                WherePredicateTypeTarget::TypeParam(local_id) => *local_id == param_id.local_id,
-            },
+            }
             WherePredicate::Lifetime { .. } => false,
         })
         .flat_map(|pred| ctx.lower_where_predicate(pred, true).map(|p| make_binders(&generics, p)))
@@ -1056,6 +1101,7 @@ pub(crate) fn generic_predicates_for_param_recover(
     _db: &dyn HirDatabase,
     _cycle: &[String],
     _param_id: &TypeParamId,
+    _assoc_name: &Option<Name>,
 ) -> Arc<[Binders<QuantifiedWhereClause>]> {
     Arc::new([])
 }
diff --git a/crates/hir_ty/src/tests/traits.rs b/crates/hir_ty/src/tests/traits.rs
index 2e074410cd4..9531be760e9 100644
--- a/crates/hir_ty/src/tests/traits.rs
+++ b/crates/hir_ty/src/tests/traits.rs
@@ -2100,7 +2100,8 @@ fn test() {
 
 #[test]
 fn unselected_projection_in_trait_env_cycle_1() {
-    // this is a legitimate cycle
+    // This is not a cycle, because the `T: Trait2<T::Item>` bound depends only on the `T: Trait`
+    // bound, not on itself (since only `Trait` can define `Item`).
     check_types(
         r#"
 trait Trait {
@@ -2111,7 +2112,7 @@ trait Trait2<T> {}
 
 fn test<T: Trait>() where T: Trait2<T::Item> {
     let x: T::Item = no_matter;
-}                  //^^^^^^^^^ {unknown}
+}                  //^^^^^^^^^ Trait::Item<T>
 "#,
     );
 }
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index 14b8a726a8f..07898f00888 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -79,7 +79,7 @@ fn direct_super_trait_refs(db: &dyn HirDatabase, trait_ref: &TraitRef) -> Vec<Tr
         Some(p) => TypeParamId { parent: trait_ref.hir_trait_id().into(), local_id: p },
         None => return Vec::new(),
     };
-    db.generic_predicates_for_param(trait_self)
+    db.generic_predicates_for_param(trait_self, None)
         .iter()
         .filter_map(|pred| {
             pred.as_ref().filter_map(|pred| match pred.skip_binders() {