Auto merge of #16117 - mustakimali:mo-order, r=Veykril

feat: completion list suggests constructor like & builder methods first

When typing `MyType::` the completion items' order could be re-ordered based on how likely we want to select those:
* Constructors: `new` like functions to be able to create the type,
* Constructors that take args: Any other function that creates `Self`,
* Builder Methods: any builder methods available,
* Regular methods & associated functions (no change there)

![image](https://github.com/rust-lang/rust-analyzer/assets/1546896/54593b91-07b3-455a-8a71-8d203d4eaf4a)

In this photo, the order is:
* `new` constructor is first
* `new_builder` second is a builder method
* `aaaanew` is a constructor that takes arguments, is third  and is irrespective of its alphabetical order among names.

---

Another Example using actix `HttpServer` shows preferring constructor without `self` arg first (the `new` method)

![image](https://github.com/rust-lang/rust-analyzer/assets/1546896/938d3fb0-3d7a-4427-ae2f-ec02a834ccbe)

![image](https://github.com/rust-lang/rust-analyzer/assets/1546896/2c13860c-efd1-459d-b25e-df8adb61bbd0)

I've dropped my previous idea of highlighting these functions in the rustdoc (https://github.com/rust-lang/rust/pull/107926)

3 files changed, 438 insertions, 4 deletions

diff --git a/crates/ide-completion/src/item.rs b/crates/ide-completion/src/item.rs
index 17dfcc08ca1..c2c0641961a 100644
--- a/crates/ide-completion/src/item.rs
+++ b/crates/ide-completion/src/item.rs
@@ -166,6 +166,8 @@ pub struct CompletionRelevance {
     pub postfix_match: Option<CompletionRelevancePostfixMatch>,
     /// This is set for type inference results
     pub is_definite: bool,
+    /// This is set for items that are function (associated or method)
+    pub function: Option<CompletionRelevanceFn>,
 }
 
 #[derive(Debug, Clone, Copy, Eq, PartialEq)]
@@ -207,6 +209,24 @@ pub enum CompletionRelevancePostfixMatch {
     Exact,
 }
 
+#[derive(Debug, Clone, Copy, Eq, PartialEq)]
+pub struct CompletionRelevanceFn {
+    pub has_params: bool,
+    pub has_self_param: bool,
+    pub return_type: CompletionRelevanceReturnType,
+}
+
+#[derive(Debug, Clone, Copy, Eq, PartialEq)]
+pub enum CompletionRelevanceReturnType {
+    Other,
+    /// Returns the Self type of the impl/trait
+    DirectConstructor,
+    /// Returns something that indirectly constructs the `Self` type of the impl/trait e.g. `Result<Self, ()>`, `Option<Self>`
+    Constructor,
+    /// Returns a possible builder for the type
+    Builder,
+}
+
 impl CompletionRelevance {
     /// Provides a relevance score. Higher values are more relevant.
     ///
@@ -231,6 +251,7 @@ impl CompletionRelevance {
             postfix_match,
             is_definite,
             is_item_from_notable_trait,
+            function,
         } = self;
 
         // lower rank private things
@@ -275,6 +296,33 @@ impl CompletionRelevance {
         if is_definite {
             score += 10;
         }
+
+        score += function
+            .map(|asf| {
+                let mut fn_score = match asf.return_type {
+                    CompletionRelevanceReturnType::DirectConstructor => 15,
+                    CompletionRelevanceReturnType::Builder => 10,
+                    CompletionRelevanceReturnType::Constructor => 5,
+                    CompletionRelevanceReturnType::Other => 0,
+                };
+
+                // When a fn is bumped due to return type:
+                // Bump Constructor or Builder methods with no arguments,
+                // over them tha with self arguments
+                if fn_score > 0 {
+                    if !asf.has_params {
+                        // bump associated functions
+                        fn_score += 1;
+                    } else if asf.has_self_param {
+                        // downgrade methods (below Constructor)
+                        fn_score = 1;
+                    }
+                }
+
+                fn_score
+            })
+            .unwrap_or_default();
+
         score
     }
 
diff --git a/crates/ide-completion/src/render.rs b/crates/ide-completion/src/render.rs
index 88dc3b5cbe7..3f374b307fb 100644
--- a/crates/ide-completion/src/render.rs
+++ b/crates/ide-completion/src/render.rs
@@ -676,6 +676,16 @@ mod tests {
     }
 
     #[track_caller]
+    fn check_function_relevance(ra_fixture: &str, expect: Expect) {
+        let actual: Vec<_> = do_completion(ra_fixture, CompletionItemKind::Method)
+            .into_iter()
+            .map(|item| (item.detail.unwrap_or_default(), item.relevance.function))
+            .collect();
+
+        expect.assert_debug_eq(&actual);
+    }
+
+    #[track_caller]
     fn check_relevance_for_kinds(ra_fixture: &str, kinds: &[CompletionItemKind], expect: Expect) {
         let mut actual = get_all_items(TEST_CONFIG, ra_fixture, None);
         actual.retain(|it| kinds.contains(&it.kind));
@@ -1254,6 +1264,7 @@ fn main() { let _: m::Spam = S$0 }
                             is_private_editable: false,
                             postfix_match: None,
                             is_definite: false,
+                            function: None,
                         },
                         trigger_call_info: true,
                     },
@@ -1281,6 +1292,7 @@ fn main() { let _: m::Spam = S$0 }
                             is_private_editable: false,
                             postfix_match: None,
                             is_definite: false,
+                            function: None,
                         },
                         trigger_call_info: true,
                     },
@@ -1360,6 +1372,7 @@ fn foo() { A { the$0 } }
                             is_private_editable: false,
                             postfix_match: None,
                             is_definite: false,
+                            function: None,
                         },
                     },
                 ]
@@ -1393,6 +1406,26 @@ impl S {
                         documentation: Documentation(
                             "Method docs",
                         ),
+                        relevance: CompletionRelevance {
+                            exact_name_match: false,
+                            type_match: None,
+                            is_local: false,
+                            is_item_from_trait: false,
+                            is_item_from_notable_trait: false,
+                            is_name_already_imported: false,
+                            requires_import: false,
+                            is_op_method: false,
+                            is_private_editable: false,
+                            postfix_match: None,
+                            is_definite: false,
+                            function: Some(
+                                CompletionRelevanceFn {
+                                    has_params: true,
+                                    has_self_param: true,
+                                    return_type: Other,
+                                },
+                            ),
+                        },
                     },
                     CompletionItem {
                         label: "foo",
@@ -1498,6 +1531,26 @@ fn foo(s: S) { s.$0 }
                         kind: Method,
                         lookup: "the_method",
                         detail: "fn(&self)",
+                        relevance: CompletionRelevance {
+                            exact_name_match: false,
+                            type_match: None,
+                            is_local: false,
+                            is_item_from_trait: false,
+                            is_item_from_notable_trait: false,
+                            is_name_already_imported: false,
+                            requires_import: false,
+                            is_op_method: false,
+                            is_private_editable: false,
+                            postfix_match: None,
+                            is_definite: false,
+                            function: Some(
+                                CompletionRelevanceFn {
+                                    has_params: true,
+                                    has_self_param: true,
+                                    return_type: Other,
+                                },
+                            ),
+                        },
                     },
                 ]
             "#]],
@@ -2099,6 +2152,254 @@ fn main() {
     }
 
     #[test]
+    fn constructor_order_simple() {
+        check_relevance(
+            r#"
+struct Foo;
+struct Other;
+struct Option<T>(T);
+
+impl Foo {
+    fn fn_ctr() -> Foo { unimplemented!() }
+    fn fn_another(n: u32) -> Other { unimplemented!() }
+    fn fn_ctr_self() -> Option<Self> { unimplemented!() }
+}
+
+fn test() {
+    let a = Foo::$0;
+}
+"#,
+            expect![[r#"
+                fn fn_ctr() [type_could_unify]
+                fn fn_ctr_self() [type_could_unify]
+                fn fn_another(…) [type_could_unify]
+            "#]],
+        );
+    }
+
+    #[test]
+    fn constructor_order_kind() {
+        check_function_relevance(
+            r#"
+struct Foo;
+struct Bar;
+struct Option<T>(T);
+enum Result<T, E> { Ok(T), Err(E) };
+
+impl Foo {
+    fn fn_ctr(&self) -> Foo { unimplemented!() }
+    fn fn_ctr_with_args(&self, n: u32) -> Foo { unimplemented!() }
+    fn fn_another(&self, n: u32) -> Bar { unimplemented!() }
+    fn fn_ctr_wrapped(&self, ) -> Option<Self> { unimplemented!() }
+    fn fn_ctr_wrapped_2(&self, ) -> Result<Self, Bar> { unimplemented!() }
+    fn fn_ctr_wrapped_3(&self, ) -> Result<Bar, Self> { unimplemented!() } // Self is not the first type
+    fn fn_ctr_wrapped_with_args(&self, m: u32) -> Option<Self> { unimplemented!() }
+    fn fn_another_unit(&self) { unimplemented!() }
+}
+
+fn test() {
+    let a = self::Foo::$0;
+}
+"#,
+            expect![[r#"
+                [
+                    (
+                        "fn(&self, u32) -> Bar",
+                        Some(
+                            CompletionRelevanceFn {
+                                has_params: true,
+                                has_self_param: true,
+                                return_type: Other,
+                            },
+                        ),
+                    ),
+                    (
+                        "fn(&self)",
+                        Some(
+                            CompletionRelevanceFn {
+                                has_params: true,
+                                has_self_param: true,
+                                return_type: Other,
+                            },
+                        ),
+                    ),
+                    (
+                        "fn(&self) -> Foo",
+                        Some(
+                            CompletionRelevanceFn {
+                                has_params: true,
+                                has_self_param: true,
+                                return_type: DirectConstructor,
+                            },
+                        ),
+                    ),
+                    (
+                        "fn(&self, u32) -> Foo",
+                        Some(
+                            CompletionRelevanceFn {
+                                has_params: true,
+                                has_self_param: true,
+                                return_type: DirectConstructor,
+                            },
+                        ),
+                    ),
+                    (
+                        "fn(&self) -> Option<Foo>",
+                        Some(
+                            CompletionRelevanceFn {
+                                has_params: true,
+                                has_self_param: true,
+                                return_type: Constructor,
+                            },
+                        ),
+                    ),
+                    (
+                        "fn(&self) -> Result<Foo, Bar>",
+                        Some(
+                            CompletionRelevanceFn {
+                                has_params: true,
+                                has_self_param: true,
+                                return_type: Constructor,
+                            },
+                        ),
+                    ),
+                    (
+                        "fn(&self) -> Result<Bar, Foo>",
+                        Some(
+                            CompletionRelevanceFn {
+                                has_params: true,
+                                has_self_param: true,
+                                return_type: Constructor,
+                            },
+                        ),
+                    ),
+                    (
+                        "fn(&self, u32) -> Option<Foo>",
+                        Some(
+                            CompletionRelevanceFn {
+                                has_params: true,
+                                has_self_param: true,
+                                return_type: Constructor,
+                            },
+                        ),
+                    ),
+                ]
+            "#]],
+        );
+    }
+
+    #[test]
+    fn constructor_order_relevance() {
+        check_relevance(
+            r#"
+struct Foo;
+struct FooBuilder;
+struct Result<T>(T);
+
+impl Foo {
+    fn fn_no_ret(&self) {}
+    fn fn_ctr_with_args(input: u32) -> Foo { unimplemented!() }
+    fn fn_direct_ctr() -> Self { unimplemented!() }
+    fn fn_ctr() -> Result<Self> { unimplemented!() }
+    fn fn_other() -> Result<u32> { unimplemented!() }
+    fn fn_builder() -> FooBuilder { unimplemented!() }
+}
+
+fn test() {
+    let a = self::Foo::$0;
+}
+"#,
+            // preference:
+            // Direct Constructor
+            // Direct Constructor with args
+            // Builder
+            // Constructor
+            // Others
+            expect![[r#"
+                fn fn_direct_ctr() [type_could_unify]
+                fn fn_ctr_with_args(…) [type_could_unify]
+                fn fn_builder() [type_could_unify]
+                fn fn_ctr() [type_could_unify]
+                me fn_no_ret(…) [type_could_unify]
+                fn fn_other() [type_could_unify]
+            "#]],
+        );
+
+        //
+    }
+
+    #[test]
+    fn function_relevance_generic_1() {
+        check_relevance(
+            r#"
+struct Foo<T: Default>(T);
+struct FooBuilder;
+struct Option<T>(T);
+enum Result<T, E>{Ok(T), Err(E)};
+
+impl<T: Default> Foo<T> {
+    fn fn_returns_unit(&self) {}
+    fn fn_ctr_with_args(input: T) -> Foo<T> { unimplemented!() }
+    fn fn_direct_ctr() -> Self { unimplemented!() }
+    fn fn_ctr_wrapped() -> Option<Self> { unimplemented!() }
+    fn fn_ctr_wrapped_2() -> Result<Self, u32> { unimplemented!() }
+    fn fn_other() -> Option<u32> { unimplemented!() }
+    fn fn_builder() -> FooBuilder { unimplemented!() }
+}
+
+fn test() {
+    let a = self::Foo::<u32>::$0;
+}
+                "#,
+            expect![[r#"
+                        fn fn_direct_ctr() [type_could_unify]
+                        fn fn_ctr_with_args(…) [type_could_unify]
+                        fn fn_builder() [type_could_unify]
+                        fn fn_ctr_wrapped() [type_could_unify]
+                        fn fn_ctr_wrapped_2() [type_could_unify]
+                        me fn_returns_unit(…) [type_could_unify]
+                        fn fn_other() [type_could_unify]
+                    "#]],
+        );
+    }
+
+    #[test]
+    fn function_relevance_generic_2() {
+        // Generic 2
+        check_relevance(
+            r#"
+struct Foo<T: Default>(T);
+struct FooBuilder;
+struct Option<T>(T);
+enum Result<T, E>{Ok(T), Err(E)};
+
+impl<T: Default> Foo<T> {
+    fn fn_no_ret(&self) {}
+    fn fn_ctr_with_args(input: T) -> Foo<T> { unimplemented!() }
+    fn fn_direct_ctr() -> Self { unimplemented!() }
+    fn fn_ctr() -> Option<Self> { unimplemented!() }
+    fn fn_ctr2() -> Result<Self, u32> { unimplemented!() }
+    fn fn_other() -> Option<u32> { unimplemented!() }
+    fn fn_builder() -> FooBuilder { unimplemented!() }
+}
+
+fn test() {
+    let a : Res<Foo<u32>> = Foo::$0;
+}
+                "#,
+            expect![[r#"
+                fn fn_direct_ctr() [type_could_unify]
+                fn fn_ctr_with_args(…) [type_could_unify]
+                fn fn_builder() [type_could_unify]
+                fn fn_ctr() [type_could_unify]
+                fn fn_ctr2() [type_could_unify]
+                me fn_no_ret(…) [type_could_unify]
+                fn fn_other() [type_could_unify]
+            "#]],
+        );
+    }
+
+    #[test]
     fn struct_field_method_ref() {
         check_kinds(
             r#"
@@ -2118,6 +2419,26 @@ fn foo(f: Foo) { let _: &u32 = f.b$0 }
                         kind: Method,
                         lookup: "baz",
                         detail: "fn(&self) -> u32",
+                        relevance: CompletionRelevance {
+                            exact_name_match: false,
+                            type_match: None,
+                            is_local: false,
+                            is_item_from_trait: false,
+                            is_item_from_notable_trait: false,
+                            is_name_already_imported: false,
+                            requires_import: false,
+                            is_op_method: false,
+                            is_private_editable: false,
+                            postfix_match: None,
+                            is_definite: false,
+                            function: Some(
+                                CompletionRelevanceFn {
+                                    has_params: true,
+                                    has_self_param: true,
+                                    return_type: Other,
+                                },
+                            ),
+                        },
                         ref_match: "&@107",
                     },
                     CompletionItem {
@@ -2192,6 +2513,7 @@ fn foo() {
                             is_private_editable: false,
                             postfix_match: None,
                             is_definite: false,
+                            function: None,
                         },
                     },
                 ]
@@ -2229,6 +2551,26 @@ fn main() {
                         ),
                         lookup: "foo",
                         detail: "fn() -> S",
+                        relevance: CompletionRelevance {
+                            exact_name_match: false,
+                            type_match: None,
+                            is_local: false,
+                            is_item_from_trait: false,
+                            is_item_from_notable_trait: false,
+                            is_name_already_imported: false,
+                            requires_import: false,
+                            is_op_method: false,
+                            is_private_editable: false,
+                            postfix_match: None,
+                            is_definite: false,
+                            function: Some(
+                                CompletionRelevanceFn {
+                                    has_params: false,
+                                    has_self_param: false,
+                                    return_type: Other,
+                                },
+                            ),
+                        },
                         ref_match: "&@92",
                     },
                 ]
@@ -2590,6 +2932,7 @@ fn main() {
                             is_private_editable: false,
                             postfix_match: None,
                             is_definite: false,
+                            function: None,
                         },
                     },
                     CompletionItem {
@@ -2612,6 +2955,7 @@ fn main() {
                             is_private_editable: false,
                             postfix_match: None,
                             is_definite: false,
+                            function: None,
                         },
                     },
                 ]
diff --git a/crates/ide-completion/src/render/function.rs b/crates/ide-completion/src/render/function.rs
index 27186a2b7ff..cf9fe1ab307 100644
--- a/crates/ide-completion/src/render/function.rs
+++ b/crates/ide-completion/src/render/function.rs
@@ -8,8 +8,13 @@ use syntax::{format_smolstr, AstNode, SmolStr};
 
 use crate::{
     context::{CompletionContext, DotAccess, DotAccessKind, PathCompletionCtx, PathKind},
-    item::{Builder, CompletionItem, CompletionItemKind, CompletionRelevance},
-    render::{compute_exact_name_match, compute_ref_match, compute_type_match, RenderContext},
+    item::{
+        Builder, CompletionItem, CompletionItemKind, CompletionRelevance, CompletionRelevanceFn,
+        CompletionRelevanceReturnType,
+    },
+    render::{
+        compute_exact_name_match, compute_ref_match, compute_type_match, match_types, RenderContext,
+    },
     CallableSnippets,
 };
 
@@ -61,9 +66,9 @@ fn render(
         ),
         _ => (name.unescaped().to_smol_str(), name.to_smol_str()),
     };
-
+    let has_self_param = func.self_param(db).is_some();
     let mut item = CompletionItem::new(
-        if func.self_param(db).is_some() {
+        if has_self_param {
             CompletionItemKind::Method
         } else {
             CompletionItemKind::SymbolKind(SymbolKind::Function)
@@ -99,6 +104,15 @@ fn render(
         .filter(|_| !has_call_parens)
         .and_then(|cap| Some((cap, params(ctx.completion, func, &func_kind, has_dot_receiver)?)));
 
+    let function = assoc_item
+        .and_then(|assoc_item| assoc_item.implementing_ty(db))
+        .map(|self_type| compute_return_type_match(db, &ctx, self_type, &ret_type))
+        .map(|return_type| CompletionRelevanceFn {
+            has_params: has_self_param || func.num_params(db) > 0,
+            has_self_param,
+            return_type,
+        });
+
     item.set_relevance(CompletionRelevance {
         type_match: if has_call_parens || complete_call_parens.is_some() {
             compute_type_match(completion, &ret_type)
@@ -106,6 +120,7 @@ fn render(
             compute_type_match(completion, &func.ty(db))
         },
         exact_name_match: compute_exact_name_match(completion, &call),
+        function,
         is_op_method,
         is_item_from_notable_trait,
         ..ctx.completion_relevance()
@@ -156,6 +171,33 @@ fn render(
     item
 }
 
+fn compute_return_type_match(
+    db: &dyn HirDatabase,
+    ctx: &RenderContext<'_>,
+    self_type: hir::Type,
+    ret_type: &hir::Type,
+) -> CompletionRelevanceReturnType {
+    if match_types(ctx.completion, &self_type, ret_type).is_some() {
+        // fn([..]) -> Self
+        CompletionRelevanceReturnType::DirectConstructor
+    } else if ret_type
+        .type_arguments()
+        .any(|ret_type_arg| match_types(ctx.completion, &self_type, &ret_type_arg).is_some())
+    {
+        // fn([..]) -> Result<Self, E> OR Wrapped<Foo, Self>
+        CompletionRelevanceReturnType::Constructor
+    } else if ret_type
+        .as_adt()
+        .and_then(|adt| adt.name(db).as_str().map(|name| name.ends_with("Builder")))
+        .unwrap_or(false)
+    {
+        // fn([..]) -> [..]Builder
+        CompletionRelevanceReturnType::Builder
+    } else {
+        CompletionRelevanceReturnType::Other
+    }
+}
+
 pub(super) fn add_call_parens<'b>(
     builder: &'b mut Builder,
     ctx: &CompletionContext<'_>,