Repository: rust-lang/rust-analyzer
Pull request #16687 (2024-02-26 18:55:32)

feat: Add "make tuple" tactic to term search
Follow up to https://github.com/rust-lang/rust-analyzer/pull/16092

Now term search also supports tuples.
```rust
let a: i32 = 1;
let b: f64 = 0.0;
let c: (i32, (f64, i32)) = todo!(); // Finds (a, (b, a))
```
In addition to new tactic that handles tuples I changed how the generics are handled.
Previously it tried all possible options from types we had in scope but now it only tries useful ones that help us directly towards the goal or at least towards calling some other function.
This changes O(2^n) to O(n^2) where n is amount of rounds which in practice allows using types that take generics for multiple rounds (previously limited to 1). Average case that also used to be exponential is now roughly linear.
This means that deeply nested generics also work.
````rust
// Finds all valid combos, including `Some(Some(Some(...)))`
let a: Option<Option<Option<bool>>> = todo!();
````

_Note that although the complexity is smaller allowing more types with generics the search overall slows down considerably. I hope it's fine tho as the autocomplete is disabled by default and for code actions it's not super slow. Might have to tweak the depth hyper parameter tho_

This resulted in a huge increase of results found (benchmarks on `ripgrep` crate):  
Before
````
Tail Expr syntactic hits: 149/1692 (8%)
Tail Exprs found: 749/1692 (44%)
Term search avg time: 18ms
```
After
```
Tail Expr syntactic hits: 291/1692 (17%)
Tail Exprs found: 1253/1692 (74%)
Term search avg time: 139ms
````

Most changes are local to term search except some tuple related stuff on `hir::Type`.


Patch:
diff --git a/crates/hir-ty/src/infer/unify.rs b/crates/hir-ty/src/infer/unify.rs
index 4a181f4a32..709760b64f 100644
--- a/crates/hir-ty/src/infer/unify.rs
+++ b/crates/hir-ty/src/infer/unify.rs
@@ -457,7 +457,6 @@ impl<'a> InferenceTable<'a> {
     }
 
     /// Unify two relatable values (e.g. `Ty`) and register new trait goals that arise from that.
-    #[tracing::instrument(skip_all)]
     pub(crate) fn unify<T: ?Sized + Zip<Interner>>(&mut self, ty1: &T, ty2: &T) -> bool {
         let result = match self.try_unify(ty1, ty2) {
             Ok(r) => r,
diff --git a/crates/hir-ty/src/method_resolution.rs b/crates/hir-ty/src/method_resolution.rs
index 4bb412d01c..a4baf572d9 100644
--- a/crates/hir-ty/src/method_resolution.rs
+++ b/crates/hir-ty/src/method_resolution.rs
@@ -254,11 +254,6 @@ impl TraitImpls {
             .flat_map(|v| v.iter().copied())
     }
 
-    /// Queries whether `self_ty` has potentially applicable implementations of `trait_`.
-    pub fn has_impls_for_trait_and_self_ty(&self, trait_: TraitId, self_ty: TyFingerprint) -> bool {
-        self.for_trait_and_self_ty(trait_, self_ty).next().is_some()
-    }
-
     pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
         self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
     }
@@ -1175,7 +1170,7 @@ fn iterate_trait_method_candidates(
         for &(_, item) in data.items.iter() {
             // Don't pass a `visible_from_module` down to `is_valid_candidate`,
             // since only inherent methods should be included into visibility checking.
-            let visible = match is_valid_method_candidate(table, name, receiver_ty, item, self_ty) {
+            let visible = match is_valid_candidate(table, name, receiver_ty, item, self_ty, None) {
                 IsValidCandidate::Yes => true,
                 IsValidCandidate::NotVisible => false,
                 IsValidCandidate::No => continue,
@@ -1419,74 +1414,6 @@ fn is_valid_candidate(
     }
 }
 
-/// Checks whether a given `AssocItemId` is applicable for `receiver_ty`.
-///
-/// This method should *only* be called by [`iterate_trait_method_candidates`],
-/// as it is responsible for determining applicability in completions.
-#[tracing::instrument(skip_all, fields(name))]
-fn is_valid_method_candidate(
-    table: &mut InferenceTable<'_>,
-    name: Option<&Name>,
-    receiver_ty: Option<&Ty>,
-    item: AssocItemId,
-    self_ty: &Ty,
-) -> IsValidCandidate {
-    let db = table.db;
-    match item {
-        AssocItemId::FunctionId(fn_id) => {
-            let data = db.function_data(fn_id);
-
-            check_that!(name.map_or(true, |n| n == &data.name));
-
-            table.run_in_snapshot(|table| {
-                let container = fn_id.lookup(db.upcast()).container;
-                let (impl_subst, expect_self_ty) = match container {
-                    ItemContainerId::ImplId(it) => {
-                        let subst = TyBuilder::subst_for_def(db, it, None)
-                            .fill_with_inference_vars(table)
-                            .build();
-                        let self_ty = db.impl_self_ty(it).substitute(Interner, &subst);
-                        (subst, self_ty)
-                    }
-                    ItemContainerId::TraitId(it) => {
-                        let subst = TyBuilder::subst_for_def(db, it, None)
-                            .fill_with_inference_vars(table)
-                            .build();
-                        let self_ty = subst.at(Interner, 0).assert_ty_ref(Interner).clone();
-                        (subst, self_ty)
-                    }
-                    _ => unreachable!(),
-                };
-
-                check_that!(table.unify(&expect_self_ty, self_ty));
-
-                if let Some(receiver_ty) = receiver_ty {
-                    check_that!(data.has_self_param());
-
-                    let fn_subst = TyBuilder::subst_for_def(db, fn_id, Some(impl_subst.clone()))
-                        .fill_with_inference_vars(table)
-                        .build();
-
-                    let sig = db.callable_item_signature(fn_id.into());
-                    let expected_receiver =
-                        sig.map(|s| s.params()[0].clone()).substitute(Interner, &fn_subst);
-
-                    check_that!(table.unify(receiver_ty, &expected_receiver));
-                }
-
-                IsValidCandidate::Yes
-            })
-        }
-        AssocItemId::ConstId(c) => {
-            check_that!(receiver_ty.is_none());
-            check_that!(name.map_or(true, |n| db.const_data(c).name.as_ref() == Some(n)));
-
-            IsValidCandidate::Yes
-        }
-        _ => IsValidCandidate::No,
-    }
-}
-
 enum IsValidCandidate {
     Yes,
     No,
@@ -1514,8 +1441,6 @@ fn is_valid_fn_candidate(
     }
     table.run_in_snapshot(|table| {
         let container = fn_id.lookup(db.upcast()).container;
-
-        let _p = tracing::span!(tracing::Level::INFO, "subst_for_def").entered();
         let (impl_subst, expect_self_ty) = match container {
             ItemContainerId::ImplId(it) => {
                 let subst =
@@ -1535,7 +1460,6 @@ fn is_valid_fn_candidate(
         check_that!(table.unify(&expect_self_ty, self_ty));
 
         if let Some(receiver_ty) = receiver_ty {
-            let _p = tracing::span!(tracing::Level::INFO, "check_receiver_ty").entered();
             check_that!(data.has_self_param());
 
             let fn_subst = TyBuilder::subst_for_def(db, fn_id, Some(impl_subst.clone()))
@@ -1550,7 +1474,6 @@ fn is_valid_fn_candidate(
         }
 
         if let ItemContainerId::ImplId(impl_id) = container {
-            let _p = tracing::span!(tracing::Level::INFO, "check_item_container").entered();
             // We need to consider the bounds on the impl to distinguish functions of the same name
             // for a type.
             let predicates = db.generic_predicates(impl_id.into());
diff --git a/crates/hir-ty/src/traits.rs b/crates/hir-ty/src/traits.rs
index 71a4ab020b..b2232b920a 100644
--- a/crates/hir-ty/src/traits.rs
+++ b/crates/hir-ty/src/traits.rs
@@ -139,7 +139,6 @@ fn solve(
     block: Option<BlockId>,
     goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<Interner>>>,
 ) -> Option<chalk_solve::Solution<Interner>> {
-    let _p = tracing::span!(tracing::Level::INFO, "solve", ?krate, ?block).entered();
     let context = ChalkContext { db, krate, block };
     tracing::debug!("solve goal: {:?}", goal);
     let mut solver = create_chalk_solver();
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 3147b59141..f157b11df5 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -3856,6 +3856,11 @@ impl Type {
         Type { env: ty.env, ty: TyBuilder::slice(ty.ty) }
     }
 
+    pub fn new_tuple(krate: CrateId, tys: &[Type]) -> Type {
+        let tys = tys.iter().map(|it| it.ty.clone());
+        Type { env: TraitEnvironment::empty(krate), ty: TyBuilder::tuple_with(tys) }
+    }
+
     pub fn is_unit(&self) -> bool {
         matches!(self.ty.kind(Interner), TyKind::Tuple(0, ..))
     }
@@ -4239,10 +4244,6 @@ impl Type {
         }
     }
 
-    pub fn fingerprint_for_trait_impl(&self) -> Option<TyFingerprint> {
-        TyFingerprint::for_trait_impl(&self.ty)
-    }
-
     pub(crate) fn canonical(&self) -> Canonical<Ty> {
         hir_ty::replace_errors_with_variables(&self.ty)
     }
@@ -4320,8 +4321,10 @@ impl Type {
         self.ty
             .strip_references()
             .as_adt()
+            .map(|(_, substs)| substs)
+            .or_else(|| self.ty.strip_references().as_tuple())
             .into_iter()
-            .flat_map(|(_, substs)| substs.iter(Interner))
+            .flat_map(|substs| substs.iter(Interner))
             .filter_map(|arg| arg.ty(Interner).cloned())
             .map(move |ty| self.derived(ty))
     }
diff --git a/crates/hir/src/term_search.rs b/crates/hir/src/term_search.rs
index 72762007dc..93e7300491 100644
--- a/crates/hir/src/term_search.rs
+++ b/crates/hir/src/term_search.rs
@@ -72,6 +72,10 @@ impl AlternativeExprs {
             AlternativeExprs::Many => (),
         }
     }
+
+    fn is_many(&self) -> bool {
+        matches!(self, AlternativeExprs::Many)
+    }
 }
 
 /// # Lookup table for term search
@@ -103,27 +107,36 @@ struct LookupTable {
 
 impl LookupTable {
     /// Initialize lookup table
-    fn new(many_threshold: usize) -> Self {
+    fn new(many_threshold: usize, goal: Type) -> Self {
         let mut res = Self { many_threshold, ..Default::default() };
         res.new_types.insert(NewTypesKey::ImplMethod, Vec::new());
         res.new_types.insert(NewTypesKey::StructProjection, Vec::new());
+        res.types_wishlist.insert(goal);
         res
     }
 
     /// Find all `Expr`s that unify with the `ty`
-    fn find(&self, db: &dyn HirDatabase, ty: &Type) -> Option<Vec<Expr>> {
-        self.data
+    fn find(&mut self, db: &dyn HirDatabase, ty: &Type) -> Option<Vec<Expr>> {
+        let res = self
+            .data
             .iter()
             .find(|(t, _)| t.could_unify_with_deeply(db, ty))
-            .map(|(t, tts)| tts.exprs(t))
+            .map(|(t, tts)| tts.exprs(t));
+
+        if res.is_none() {
+            self.types_wishlist.insert(ty.clone());
+        }
+
+        res
     }
 
     /// Same as find but automatically creates shared reference of types in the lookup
     ///
     /// For example if we have type `i32` in data and we query for `&i32` it map all the type
     /// trees we have for `i32` with `Expr::Reference` and returns them.
-    fn find_autoref(&self, db: &dyn HirDatabase, ty: &Type) -> Option<Vec<Expr>> {
-        self.data
+    fn find_autoref(&mut self, db: &dyn HirDatabase, ty: &Type) -> Option<Vec<Expr>> {
+        let res = self
+            .data
             .iter()
             .find(|(t, _)| t.could_unify_with_deeply(db, ty))
             .map(|(t, it)| it.exprs(t))
@@ -139,7 +152,13 @@ impl LookupTable {
                             .map(|expr| Expr::Reference(Box::new(expr)))
                             .collect()
                     })
-            })
+            });
+
+        if res.is_none() {
+            self.types_wishlist.insert(ty.clone());
+        }
+
+        res
     }
 
     /// Insert new type trees for type
@@ -149,7 +168,12 @@ impl LookupTable {
     /// but they clearly do not unify themselves.
     fn insert(&mut self, ty: Type, exprs: impl Iterator<Item = Expr>) {
         match self.data.get_mut(&ty) {
-            Some(it) => it.extend_with_threshold(self.many_threshold, exprs),
+            Some(it) => {
+                it.extend_with_threshold(self.many_threshold, exprs);
+                if it.is_many() {
+                    self.types_wishlist.remove(&ty);
+                }
+            }
             None => {
                 self.data.insert(ty.clone(), AlternativeExprs::new(self.many_threshold, exprs));
                 for it in self.new_types.values_mut() {
@@ -206,8 +230,8 @@ impl LookupTable {
     }
 
     /// Types queried but not found
-    fn take_types_wishlist(&mut self) -> FxHashSet<Type> {
-        std::mem::take(&mut self.types_wishlist)
+    fn types_wishlist(&mut self) -> &FxHashSet<Type> {
+        &self.types_wishlist
     }
 }
 
@@ -272,7 +296,7 @@ pub fn term_search<DB: HirDatabase>(ctx: &TermSearchCtx<'_, DB>) -> Vec<Expr> {
         defs.insert(def);
     });
 
-    let mut lookup = LookupTable::new(ctx.config.many_alternatives_threshold);
+    let mut lookup = LookupTable::new(ctx.config.many_alternatives_threshold, ctx.goal.clone());
 
     // Try trivial tactic first, also populates lookup table
     let mut solutions: Vec<Expr> = tactics::trivial(ctx, &defs, &mut lookup).collect();
@@ -287,6 +311,7 @@ pub fn term_search<DB: HirDatabase>(ctx: &TermSearchCtx<'_, DB>) -> Vec<Expr> {
         solutions.extend(tactics::impl_method(ctx, &defs, &mut lookup));
         solutions.extend(tactics::struct_projection(ctx, &defs, &mut lookup));
         solutions.extend(tactics::impl_static_method(ctx, &defs, &mut lookup));
+        solutions.extend(tactics::make_tuple(ctx, &defs, &mut lookup));
 
         // Discard not interesting `ScopeDef`s for speedup
         for def in lookup.exhausted_scopedefs() {
diff --git a/crates/hir/src/term_search/expr.rs b/crates/hir/src/term_search/expr.rs
index 254fbe7e2b..2d0c5630e1 100644
--- a/crates/hir/src/term_search/expr.rs
+++ b/crates/hir/src/term_search/expr.rs
@@ -138,6 +138,8 @@ pub enum Expr {
     Variant { variant: Variant, generics: Vec<Type>, params: Vec<Expr> },
     /// Struct construction
     Struct { strukt: Struct, generics: Vec<Type>, params: Vec<Expr> },
+    /// Tuple construction
+    Tuple { ty: Type, params: Vec<Expr> },
     /// Struct field access
     Field { expr: Box<Expr>, field: Field },
     /// Passing type as reference (with `&`)
@@ -366,6 +368,18 @@ impl Expr {
                 let prefix = mod_item_path_str(sema_scope, &ModuleDef::Adt(Adt::Struct(*strukt)))?;
                 Ok(format!("{prefix}{inner}"))
             }
+            Expr::Tuple { params, .. } => {
+                let args = params
+                    .iter()
+                    .map(|a| {
+                        a.gen_source_code(sema_scope, many_formatter, prefer_no_std, prefer_prelude)
+                    })
+                    .collect::<Result<Vec<String>, DisplaySourceCodeError>>()?
+                    .into_iter()
+                    .join(", ");
+                let res = format!("({args})");
+                Ok(res)
+            }
             Expr::Field { expr, field } => {
                 if expr.contains_many_in_illegal_pos() {
                     return Ok(many_formatter(&expr.ty(db)));
@@ -420,6 +434,7 @@ impl Expr {
             Expr::Struct { strukt, generics, .. } => {
                 Adt::from(*strukt).ty_with_args(db, generics.iter().cloned())
             }
+            Expr::Tuple { ty, .. } => ty.clone(),
             Expr::Field { expr, field } => field.ty_with_args(db, expr.ty(db).type_arguments()),
             Expr::Reference(it) => it.ty(db),
             Expr::Many(ty) => ty.clone(),
diff --git a/crates/hir/src/term_search/tactics.rs b/crates/hir/src/term_search/tactics.rs
index edbf75affe..102e0ca4c3 100644
--- a/crates/hir/src/term_search/tactics.rs
+++ b/crates/hir/src/term_search/tactics.rs
@@ -109,7 +109,6 @@ pub(super) fn type_constructor<'a, DB: HirDatabase>(
         lookup: &mut LookupTable,
         parent_enum: Enum,
         variant: Variant,
-        goal: &Type,
         config: &TermSearchConfig,
     ) -> Vec<(Type, Vec<Expr>)> {
         // Ignore unstable
@@ -143,11 +142,14 @@ pub(super) fn type_constructor<'a, DB: HirDatabase>(
         let non_default_type_params_len =
             type_params.iter().filter(|it| it.default(db).is_none()).count();
 
+        let enum_ty_shallow = Adt::from(parent_enum).ty(db);
         let generic_params = lookup
-            .iter_types()
-            .collect::<Vec<_>>() // Force take ownership
+            .types_wishlist()
+            .clone()
             .into_iter()
-            .permutations(non_default_type_params_len);
+            .filter(|ty| ty.could_unify_with(db, &enum_ty_shallow))
+            .map(|it| it.type_arguments().collect::<Vec<Type>>())
+            .chain((non_default_type_params_len == 0).then_some(Vec::new()));
 
         generic_params
             .filter_map(move |generics| {
@@ -155,17 +157,11 @@ pub(super) fn type_constructor<'a, DB: HirDatabase>(
                 let mut g = generics.into_iter();
                 let generics: Vec<_> = type_params
                     .iter()
-                    .map(|it| it.default(db).unwrap_or_else(|| g.next().expect("No generic")))
-                    .collect();
+                    .map(|it| it.default(db).or_else(|| g.next()))
+                    .collect::<Option<_>>()?;
 
                 let enum_ty = Adt::from(parent_enum).ty_with_args(db, generics.iter().cloned());
 
-                // Allow types with generics only if they take us straight to goal for
-                // performance reasons
-                if !generics.is_empty() && !enum_ty.could_unify_with_deeply(db, goal) {
-                    return None;
-                }
-
                 // Ignore types that have something to do with lifetimes
                 if config.enable_borrowcheck && enum_ty.contains_reference(db) {
                     return None;
@@ -199,21 +195,37 @@ pub(super) fn type_constructor<'a, DB: HirDatabase>(
         .filter_map(move |def| match def {
             ScopeDef::ModuleDef(ModuleDef::Variant(it)) => {
                 let variant_exprs =
-                    variant_helper(db, lookup, it.parent_enum(db), *it, &ctx.goal, &ctx.config);
+                    variant_helper(db, lookup, it.parent_enum(db), *it, &ctx.config);
                 if variant_exprs.is_empty() {
                     return None;
                 }
-                lookup.mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Variant(*it)));
+                if GenericDef::from(it.parent_enum(db))
+                    .type_or_const_params(db)
+                    .into_iter()
+                    .filter_map(|it| it.as_type_param(db))
+                    .all(|it| it.default(db).is_some())
+                {
+                    lookup.mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Variant(*it)));
+                }
                 Some(variant_exprs)
             }
             ScopeDef::ModuleDef(ModuleDef::Adt(Adt::Enum(enum_))) => {
                 let exprs: Vec<(Type, Vec<Expr>)> = enum_
                     .variants(db)
                     .into_iter()
-                    .flat_map(|it| variant_helper(db, lookup, *enum_, it, &ctx.goal, &ctx.config))
+                    .flat_map(|it| variant_helper(db, lookup, *enum_, it, &ctx.config))
                     .collect();
 
-                if !exprs.is_empty() {
+                if exprs.is_empty() {
+                    return None;
+                }
+
+                if GenericDef::from(*enum_)
+                    .type_or_const_params(db)
+                    .into_iter()
+                    .filter_map(|it| it.as_type_param(db))
+                    .all(|it| it.default(db).is_some())
+                {
                     lookup.mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Adt(Adt::Enum(*enum_))));
                 }
 
@@ -249,11 +261,14 @@ pub(super) fn type_constructor<'a, DB: HirDatabase>(
                 let non_default_type_params_len =
                     type_params.iter().filter(|it| it.default(db).is_none()).count();
 
+                let struct_ty_shallow = Adt::from(*it).ty(db);
                 let generic_params = lookup
-                    .iter_types()
-                    .collect::<Vec<_>>() // Force take ownership
+                    .types_wishlist()
+                    .clone()
                     .into_iter()
-                    .permutations(non_default_type_params_len);
+                    .filter(|ty| ty.could_unify_with(db, &struct_ty_shallow))
+                    .map(|it| it.type_arguments().collect::<Vec<Type>>())
+                    .chain((non_default_type_params_len == 0).then_some(Vec::new()));
 
                 let exprs = generic_params
                     .filter_map(|generics| {
@@ -261,22 +276,11 @@ pub(super) fn type_constructor<'a, DB: HirDatabase>(
                         let mut g = generics.into_iter();
                         let generics: Vec<_> = type_params
                             .iter()
-                            .map(|it| {
-                                it.default(db)
-                                    .unwrap_or_else(|| g.next().expect("Missing type param"))
-                            })
-                            .collect();
+                            .map(|it| it.default(db).or_else(|| g.next()))
+                            .collect::<Option<_>>()?;
 
                         let struct_ty = Adt::from(*it).ty_with_args(db, generics.iter().cloned());
 
-                        // Allow types with generics only if they take us straight to goal for
-                        // performance reasons
-                        if non_default_type_params_len != 0
-                            && struct_ty.could_unify_with_deeply(db, &ctx.goal)
-                        {
-                            return None;
-                        }
-
                         // Ignore types that have something to do with lifetimes
                         if ctx.config.enable_borrowcheck && struct_ty.contains_reference(db) {
                             return None;
@@ -309,8 +313,12 @@ pub(super) fn type_constructor<'a, DB: HirDatabase>(
                                 .collect()
                         };
 
-                        lookup
-                            .mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Adt(Adt::Struct(*it))));
+                        if non_default_type_params_len == 0 {
+                            // Fulfilled only if there are no generic parameters
+                            lookup.mark_fulfilled(ScopeDef::ModuleDef(ModuleDef::Adt(
+                                Adt::Struct(*it),
+                            )));
+                        }
                         lookup.insert(struct_ty.clone(), struct_exprs.iter().cloned());
 
                         Some((struct_ty, struct_exprs))
@@ -525,14 +533,17 @@ pub(super) fn impl_method<'a, DB: HirDatabase>(
                 return None;
             }
 
-            let non_default_type_params_len = imp_type_params
-                .iter()
-                .chain(fn_type_params.iter())
-                .filter(|it| it.default(db).is_none())
-                .count();
+            // Double check that we have fully known type
+            if ty.type_arguments().any(|it| it.contains_unknown()) {
+                return None;
+            }
+
+            let non_default_fn_type_params_len =
+                fn_type_params.iter().filter(|it| it.default(db).is_none()).count();
 
-            // Ignore bigger number of generics for now as they kill the performance
-            if non_default_type_params_len > 0 {
+            // Ignore functions with generics for now as they kill the performance
+            // Also checking bounds for generics is problematic
+            if non_default_fn_type_params_len > 0 {
                 return None;
             }
 
@@ -540,23 +551,23 @@ pub(super) fn impl_method<'a, DB: HirDatabase>(
                 .iter_types()
                 .collect::<Vec<_>>() // Force take ownership
                 .into_iter()
-                .permutations(non_default_type_params_len);
+                .permutations(non_default_fn_type_params_len);
 
             let exprs: Vec<_> = generic_params
                 .filter_map(|generics| {
                     // Insert default type params
                     let mut g = generics.into_iter();
-                    let generics: Vec<_> = imp_type_params
-                        .iter()
-                        .chain(fn_type_params.iter())
-                        .map(|it| match it.default(db) {
+                    let generics: Vec<_> = ty
+                        .type_arguments()
+                        .map(Some)
+                        .chain(fn_type_params.iter().map(|it| match it.default(db) {
                             Some(ty) => Some(ty),
                             None => {
                                 let generic = g.next().expect("Missing type param");
                                 // Filter out generics that do not unify due to trait bounds
                                 it.ty(db).could_unify_with(db, &generic).then_some(generic)
                             }
-                        })
+                        }))
                         .collect::<Option<_>>()?;
 
                     let ret_ty = it.ret_type_with_args(
@@ -713,7 +724,8 @@ pub(super) fn impl_static_method<'a, DB: HirDatabase>(
     let db = ctx.sema.db;
     let module = ctx.scope.module();
     lookup
-        .take_types_wishlist()
+        .types_wishlist()
+        .clone()
         .into_iter()
         .chain(iter::once(ctx.goal.clone()))
         .flat_map(|ty| {
@@ -768,14 +780,17 @@ pub(super) fn impl_static_method<'a, DB: HirDatabase>(
                 return None;
             }
 
-            let non_default_type_params_len = imp_type_params
-                .iter()
-                .chain(fn_type_params.iter())
-                .filter(|it| it.default(db).is_none())
-                .count();
+            // Double check that we have fully known type
+            if ty.type_arguments().any(|it| it.contains_unknown()) {
+                return None;
+            }
+
+            let non_default_fn_type_params_len =
+                fn_type_params.iter().filter(|it| it.default(db).is_none()).count();
 
-            // Ignore bigger number of generics for now as they kill the performance
-            if non_default_type_params_len > 1 {
+            // Ignore functions with generics for now as they kill the performance
+            // Also checking bounds for generics is problematic
+            if non_default_fn_type_params_len > 0 {
                 return None;
             }
 
@@ -783,16 +798,16 @@ pub(super) fn impl_static_method<'a, DB: HirDatabase>(
                 .iter_types()
                 .collect::<Vec<_>>() // Force take ownership
                 .into_iter()
-                .permutations(non_default_type_params_len);
+                .permutations(non_default_fn_type_params_len);
 
             let exprs: Vec<_> = generic_params
                 .filter_map(|generics| {
                     // Insert default type params
                     let mut g = generics.into_iter();
-                    let generics: Vec<_> = imp_type_params
-                        .iter()
-                        .chain(fn_type_params.iter())
-                        .map(|it| match it.default(db) {
+                    let generics: Vec<_> = ty
+                        .type_arguments()
+                        .map(Some)
+                        .chain(fn_type_params.iter().map(|it| match it.default(db) {
                             Some(ty) => Some(ty),
                             None => {
                                 let generic = g.next().expect("Missing type param");
@@ -802,7 +817,7 @@ pub(super) fn impl_static_method<'a, DB: HirDatabase>(
                                 // Filter out generics that do not unify due to trait bounds
                                 it.ty(db).could_unify_with(db, &generic).then_some(generic)
                             }
-                        })
+                        }))
                         .collect::<Option<_>>()?;
 
                     let ret_ty = it.ret_type_with_args(
@@ -857,3 +872,61 @@ pub(super) fn impl_static_method<'a, DB: HirDatabase>(
         .filter_map(|(ty, exprs)| ty.could_unify_with_deeply(db, &ctx.goal).then_some(exprs))
         .flatten()
 }
+
+/// # Make tuple tactic
+///
+/// Attempts to create tuple types if any are listed in types wishlist
+///
+/// Updates lookup by new types reached and returns iterator that yields
+/// elements that unify with `goal`.
+///
+/// # Arguments
+/// * `ctx` - Context for the term search
+/// * `defs` - Set of items in scope at term search target location
+/// * `lookup` - Lookup table for types
+pub(super) fn make_tuple<'a, DB: HirDatabase>(
+    ctx: &'a TermSearchCtx<'a, DB>,
+    _defs: &'a FxHashSet<ScopeDef>,
+    lookup: &'a mut LookupTable,
+) -> impl Iterator<Item = Expr> + 'a {
+    let db = ctx.sema.db;
+    let module = ctx.scope.module();
+
+    lookup
+        .types_wishlist()
+        .clone()
+        .into_iter()
+        .filter(|ty| ty.is_tuple())
+        .filter_map(move |ty| {
+            // Double check to not contain unknown
+            if ty.contains_unknown() {
+                return None;
+            }
+
+            // Ignore types that have something to do with lifetimes
+            if ctx.config.enable_borrowcheck && ty.contains_reference(db) {
+                return None;
+            }
+
+            // Early exit if some param cannot be filled from lookup
+            let param_exprs: Vec<Vec<Expr>> =
+                ty.type_arguments().map(|field| lookup.find(db, &field)).collect::<Option<_>>()?;
+
+            let exprs: Vec<Expr> = param_exprs
+                .into_iter()
+                .multi_cartesian_product()
+                .map(|params| {
+                    let tys: Vec<Type> = params.iter().map(|it| it.ty(db)).collect();
+                    let tuple_ty = Type::new_tuple(module.krate().into(), &tys);
+
+                    let expr = Expr::Tuple { ty: tuple_ty.clone(), params };
+                    lookup.insert(tuple_ty, iter::once(expr.clone()));
+                    expr
+                })
+                .collect();
+
+            Some(exprs)
+        })
+        .flatten()
+        .filter_map(|expr| expr.ty(db).could_unify_with_deeply(db, &ctx.goal).then_some(expr))
+}
diff --git a/crates/ide-assists/src/handlers/term_search.rs b/crates/ide-assists/src/handlers/term_search.rs
index 51a1a406f3..0f4a8e3aec 100644
--- a/crates/ide-assists/src/handlers/term_search.rs
+++ b/crates/ide-assists/src/handlers/term_search.rs
@@ -57,11 +57,14 @@ pub(crate) fn term_search(acc: &mut Assists, ctx: &AssistContext<'_>) -> Option<
         })
         .unique();
 
+    let macro_name = macro_call.name(ctx.sema.db);
+    let macro_name = macro_name.display(ctx.sema.db);
+
     for code in paths {
         acc.add_group(
             &GroupLabel(String::from("Term search")),
             AssistId("term_search", AssistKind::Generate),
-            format!("Replace todo!() with {code}"),
+            format!("Replace {macro_name}!() with {code}"),
             goal_range,
             |builder| {
                 builder.replace(goal_range, code);
@@ -250,4 +253,24 @@ fn g() { let a = &1; let b: f32 = f(a); }"#,
             fn g() { let a = &mut 1; let b: f32 = todo$0!(); }"#,
         )
     }
+
+    #[test]
+    fn test_tuple_simple() {
+        check_assist(
+            term_search,
+            r#"//- minicore: todo, unimplemented
+fn f() { let a = 1; let b = 0.0; let c: (i32, f64) = todo$0!(); }"#,
+            r#"fn f() { let a = 1; let b = 0.0; let c: (i32, f64) = (a, b); }"#,
+        )
+    }
+
+    #[test]
+    fn test_tuple_nested() {
+        check_assist(
+            term_search,
+            r#"//- minicore: todo, unimplemented
+fn f() { let a = 1; let b = 0.0; let c: (i32, (i32, f64)) = todo$0!(); }"#,
+            r#"fn f() { let a = 1; let b = 0.0; let c: (i32, (i32, f64)) = (a, (a, b)); }"#,
+        )
+    }
 }
diff --git a/crates/ide-completion/src/render.rs b/crates/ide-completion/src/render.rs
index 3f374b307f..6d1a5a0bc5 100644
--- a/crates/ide-completion/src/render.rs
+++ b/crates/ide-completion/src/render.rs
@@ -2599,6 +2599,7 @@ fn foo() {
             expect![[r#"
                 lc foo [type+local]
                 ex foo [type]
+                ex Foo::B [type]
                 ev Foo::A(…) [type_could_unify]
                 ev Foo::B [type_could_unify]
                 en Foo [type_could_unify]
diff --git a/crates/ide-db/src/imports/import_assets.rs b/crates/ide-db/src/imports/import_assets.rs
index c597555a3b..a71d8e9002 100644
--- a/crates/ide-db/src/imports/import_assets.rs
+++ b/crates/ide-db/src/imports/import_assets.rs
@@ -1,9 +1,8 @@
 //! Look up accessible paths for items.
 
 use hir::{
-    db::HirDatabase, AsAssocItem, AssocItem, AssocItemContainer, Crate, HasCrate, ItemInNs,
-    ModPath, Module, ModuleDef, Name, PathResolution, PrefixKind, ScopeDef, Semantics,
-    SemanticsScope, Trait, Type,
+    AsAssocItem, AssocItem, AssocItemContainer, Crate, ItemInNs, ModPath, Module, ModuleDef, Name,
+    PathResolution, PrefixKind, ScopeDef, Semantics, SemanticsScope, Type,
 };
 use itertools::{EitherOrBoth, Itertools};
 use rustc_hash::{FxHashMap, FxHashSet};
@@ -518,7 +517,7 @@ fn trait_applicable_items(
     let related_traits = inherent_traits.chain(env_traits).collect::<FxHashSet<_>>();
 
     let mut required_assoc_items = FxHashSet::default();
-    let mut trait_candidates: FxHashSet<_> = items_locator::items_with_name(
+    let trait_candidates: FxHashSet<_> = items_locator::items_with_name(
         sema,
         current_crate,
         trait_candidate.assoc_item_name.clone(),
@@ -539,32 +538,6 @@ fn trait_applicable_items(
     })
     .collect();
 
-    trait_candidates.retain(|&candidate_trait_id| {
-        // we care about the following cases:
-        // 1. Trait's definition crate
-        // 2. Definition crates for all trait's generic arguments
-        //     a. This is recursive for fundamental types: `Into<Box<A>> for ()`` is OK, but
-        //        `Into<Vec<A>> for ()`` is *not*.
-        // 3. Receiver type definition crate
-        //    a. This is recursive for fundamental types
-        let defining_crate_for_trait = Trait::from(candidate_trait_id).krate(db);
-        let Some(receiver) = trait_candidate.receiver_ty.fingerprint_for_trait_impl() else {
-            return false;
-        };
-        let definitions_exist_in_trait_crate = db
-            .trait_impls_in_crate(defining_crate_for_trait.into())
-            .has_impls_for_trait_and_self_ty(candidate_trait_id, receiver);
-
-        // this is a closure for laziness: if `definitions_exist_in_trait_crate` is true,
-        // we can avoid a second db lookup.
-        let definitions_exist_in_receiver_crate = || {
-            db.trait_impls_in_crate(trait_candidate.receiver_ty.krate(db).into())
-                .has_impls_for_trait_and_self_ty(candidate_trait_id, receiver)
-        };
-
-        definitions_exist_in_trait_crate || definitions_exist_in_receiver_crate()
-    });
-
     let mut located_imports = FxHashSet::default();
     let mut trait_import_paths = FxHashMap::default();
 
diff --git a/crates/rust-analyzer/src/cli/analysis_stats.rs b/crates/rust-analyzer/src/cli/analysis_stats.rs
index ce7e3b3cd6..186b65692e 100644
--- a/crates/rust-analyzer/src/cli/analysis_stats.rs
+++ b/crates/rust-analyzer/src/cli/analysis_stats.rs
@@ -453,8 +453,11 @@ impl flags::AnalysisStats {
                                     err_idx += 7;
                                     let err_code = &err[err_idx..err_idx + 4];
                                     match err_code {
-                                        "0282" => continue,                              // Byproduct of testing method
-                                        "0277" if generated.contains(&todo) => continue, // See https://github.com/rust-lang/rust/issues/69882
+                                        "0282" | "0283" => continue, // Byproduct of testing method
+                                        "0277" | "0308" if generated.contains(&todo) => continue, // See https://github.com/rust-lang/rust/issues/69882
+                                        // FIXME: In some rare cases `AssocItem::container_or_implemented_trait` returns `None` for trait methods.
+                                        // Generated code is valid in case traits are imported
+                                        "0599" if err.contains("the following trait is implemented but not in scope") => continue,
                                         _ => (),
                                     }
                                     bar.println(err);


Test patch:
diff --git a/crates/ide-completion/src/tests/flyimport.rs b/crates/ide-completion/src/tests/flyimport.rs
index d2227d23cd..fff193ba4c 100644
--- a/crates/ide-completion/src/tests/flyimport.rs
+++ b/crates/ide-completion/src/tests/flyimport.rs
@@ -374,135 +374,6 @@ fn main() {
     );
 }
 
-#[test]
-fn trait_method_fuzzy_completion_aware_of_fundamental_boxes() {
-    let fixture = r#"
-//- /fundamental.rs crate:fundamental
-#[lang = "owned_box"]
-#[fundamental]
-pub struct Box<T>(T);
-//- /foo.rs crate:foo
-pub trait TestTrait {
-    fn some_method(&self);
-}
-//- /main.rs crate:main deps:foo,fundamental
-struct TestStruct;
-
-impl foo::TestTrait for fundamental::Box<TestStruct> {
-    fn some_method(&self) {}
-}
-
-fn main() {
-    let t = fundamental::Box(TestStruct);
-    t.$0
-}
-"#;
-
-    check(
-        fixture,
-        expect![[r#"
-        me some_method() (use foo::TestTrait) fn(&self)
-    "#]],
-    );
-
-    check_edit(
-        "some_method",
-        fixture,
-        r#"
-use foo::TestTrait;
-
-struct TestStruct;
-
-impl foo::TestTrait for fundamental::Box<TestStruct> {
-    fn some_method(&self) {}
-}
-
-fn main() {
-    let t = fundamental::Box(TestStruct);
-    t.some_method()$0
-}
-"#,
-    );
-}
-
-#[test]
-fn trait_method_fuzzy_completion_aware_of_fundamental_references() {
-    let fixture = r#"
-//- /foo.rs crate:foo
-pub trait TestTrait {
-    fn some_method(&self);
-}
-//- /main.rs crate:main deps:foo
-struct TestStruct;
-
-impl foo::TestTrait for &TestStruct {
-    fn some_method(&self) {}
-}
-
-fn main() {
-    let t = &TestStruct;
-    t.$0
-}
-"#;
-
-    check(
-        fixture,
-        expect![[r#"
-        me some_method() (use foo::TestTrait) fn(&self)
-    "#]],
-    );
-
-    check_edit(
-        "some_method",
-        fixture,
-        r#"
-use foo::TestTrait;
-
-struct TestStruct;
-
-impl foo::TestTrait for &TestStruct {
-    fn some_method(&self) {}
-}
-
-fn main() {
-    let t = &TestStruct;
-    t.some_method()$0
-}
-"#,
-    );
-}
-
-#[test]
-fn trait_method_fuzzy_completion_aware_of_unit_type() {
-    let fixture = r#"
-//- /test_trait.rs crate:test_trait
-pub trait TestInto<T> {
-    fn into(self) -> T;
-}
-
-//- /main.rs crate:main deps:test_trait
-struct A;
-
-impl test_trait::TestInto<A> for () {
-    fn into(self) -> A {
-        A
-    }
-}
-
-fn main() {
-    let a = ();
-    a.$0
-}
-"#;
-
-    check(
-        fixture,
-        expect![[r#"
-    me into() (use test_trait::TestInto) fn(self) -> T
-    "#]],
-    );
-}
-
 #[test]
 fn trait_method_from_alias() {
     let fixture = r#"