order merged use trees

5 files changed, 186 insertions, 92 deletions

diff --git a/crates/ide-assists/src/handlers/bool_to_enum.rs b/crates/ide-assists/src/handlers/bool_to_enum.rs
index dc1952c3ff3..bec540790b2 100644
--- a/crates/ide-assists/src/handlers/bool_to_enum.rs
+++ b/crates/ide-assists/src/handlers/bool_to_enum.rs
@@ -986,7 +986,7 @@ fn foo() {
 }
 
 //- /main.rs
-use foo::{Foo, Bool};
+use foo::{Bool, Foo};
 
 mod foo;
 
@@ -1662,7 +1662,7 @@ impl Foo {
 }
 
 //- /foo.rs
-use crate::{Foo, Bool};
+use crate::{Bool, Foo};
 
 fn foo() -> bool {
     Foo::BOOL == Bool::True
diff --git a/crates/ide-assists/src/handlers/merge_imports.rs b/crates/ide-assists/src/handlers/merge_imports.rs
index d7ddc5f23f5..78f3825c3c0 100644
--- a/crates/ide-assists/src/handlers/merge_imports.rs
+++ b/crates/ide-assists/src/handlers/merge_imports.rs
@@ -179,7 +179,7 @@ use std::fmt::Debug;
 use std::fmt$0::Display;
 ",
             r"
-use std::fmt::{Display, Debug};
+use std::fmt::{Debug, Display};
 ",
         );
     }
@@ -206,7 +206,7 @@ use std::fmt::{self, Display};
 use std::{fmt, $0fmt::Display};
 ",
             r"
-use std::{fmt::{Display, self}};
+use std::{fmt::{self, Display}};
 ",
         );
     }
@@ -318,7 +318,7 @@ use std::{fmt::{Debug, Display}};
 use std::{fmt::Debug, fmt$0::Display};
 ",
             r"
-use std::{fmt::{Display, Debug}};
+use std::{fmt::{Debug, Display}};
 ",
         );
     }
@@ -332,7 +332,7 @@ use std$0::{fmt::{Write, Display}};
 use std::{fmt::{self, Debug}};
 ",
             r"
-use std::{fmt::{Write, Display, self, Debug}};
+use std::{fmt::{self, Debug, Display, Write}};
 ",
         );
     }
@@ -346,7 +346,7 @@ use std$0::{fmt::{self, Debug}};
 use std::{fmt::{Write, Display}};
 ",
             r"
-use std::{fmt::{self, Debug, Write, Display}};
+use std::{fmt::{self, Debug, Display, Write}};
 ",
         );
     }
@@ -359,7 +359,7 @@ use std::{fmt::{self, Debug, Write, Display}};
 use std::{fmt$0::{self, Debug}, fmt::{Write, Display}};
 ",
             r"
-use std::{fmt::{self, Debug, Write, Display}};
+use std::{fmt::{self, Debug, Display, Write}};
 ",
         );
     }
@@ -401,7 +401,7 @@ use std$0::{fmt::*};
 use std::{fmt::{self, Display}};
 ",
             r"
-use std::{fmt::{*, self, Display}};
+use std::{fmt::{self, Display, *}};
 ",
         )
     }
@@ -496,7 +496,7 @@ use foo::$0{
 ",
             r"
 use foo::{
-    FooBar, bar::baz,
+    bar::baz, FooBar
 };
 ",
         )
@@ -521,7 +521,7 @@ use foo::$0*;
 use foo::bar::Baz;
 ",
             r"
-use foo::{*, bar::Baz};
+use foo::{bar::Baz, *};
 ",
         );
     }
@@ -539,7 +539,7 @@ $0use std::fmt::Result;
 ",
             r"
 use std::fmt::Error;
-use std::fmt::{Display, Debug, Write};
+use std::fmt::{Debug, Display, Write};
 use std::fmt::Result;
 ",
         );
@@ -560,7 +560,7 @@ use std::{
             r"
 use std::{
     fmt::Error,
-    fmt::{Display, Debug, Write},
+    fmt::{Debug, Display, Write},
     fmt::Result,
 };",
         );
@@ -568,7 +568,7 @@ use std::{
         check_assist(
             merge_imports,
             r"use std::$0{fmt::Display, fmt::Debug}$0;",
-            r"use std::{fmt::{Display, Debug}};",
+            r"use std::{fmt::{Debug, Display}};",
         );
     }
 }
diff --git a/crates/ide-assists/src/handlers/replace_qualified_name_with_use.rs b/crates/ide-assists/src/handlers/replace_qualified_name_with_use.rs
index f03eb6118a5..ba1c25fa5a7 100644
--- a/crates/ide-assists/src/handlers/replace_qualified_name_with_use.rs
+++ b/crates/ide-assists/src/handlers/replace_qualified_name_with_use.rs
@@ -313,7 +313,7 @@ fn main() {
     ",
             r"
 mod std { pub mod fmt { pub trait Display {} } }
-use std::fmt::{Display, self};
+use std::fmt::{self, Display};
 
 fn main() {
     fmt;
diff --git a/crates/ide-db/src/imports/insert_use/tests.rs b/crates/ide-db/src/imports/insert_use/tests.rs
index a3abce89642..4e626ada83e 100644
--- a/crates/ide-db/src/imports/insert_use/tests.rs
+++ b/crates/ide-db/src/imports/insert_use/tests.rs
@@ -596,7 +596,7 @@ fn merge_groups_full() {
 
 #[test]
 fn merge_groups_long_full() {
-    check_crate("std::foo::bar::Baz", r"use std::foo::bar::Qux;", r"use std::foo::bar::{Qux, Baz};")
+    check_crate("std::foo::bar::Baz", r"use std::foo::bar::Qux;", r"use std::foo::bar::{Baz, Qux};")
 }
 
 #[test]
@@ -604,7 +604,7 @@ fn merge_groups_long_last() {
     check_module(
         "std::foo::bar::Baz",
         r"use std::foo::bar::Qux;",
-        r"use std::foo::bar::{Qux, Baz};",
+        r"use std::foo::bar::{Baz, Qux};",
     )
 }
 
@@ -613,7 +613,7 @@ fn merge_groups_long_full_list() {
     check_crate(
         "std::foo::bar::Baz",
         r"use std::foo::bar::{Qux, Quux};",
-        r"use std::foo::bar::{Qux, Quux, Baz};",
+        r"use std::foo::bar::{Baz, Quux, Qux};",
     )
 }
 
@@ -622,7 +622,7 @@ fn merge_groups_long_last_list() {
     check_module(
         "std::foo::bar::Baz",
         r"use std::foo::bar::{Qux, Quux};",
-        r"use std::foo::bar::{Qux, Quux, Baz};",
+        r"use std::foo::bar::{Baz, Quux, Qux};",
     )
 }
 
@@ -631,7 +631,7 @@ fn merge_groups_long_full_nested() {
     check_crate(
         "std::foo::bar::Baz",
         r"use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
-        r"use std::foo::bar::{Qux, quux::{Fez, Fizz}, Baz};",
+        r"use std::foo::bar::{quux::{Fez, Fizz}, Baz, Qux};",
     )
 }
 
@@ -650,7 +650,7 @@ fn merge_groups_full_nested_deep() {
     check_crate(
         "std::foo::bar::quux::Baz",
         r"use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
-        r"use std::foo::bar::{Qux, quux::{Fez, Fizz, Baz}};",
+        r"use std::foo::bar::{Qux, quux::{Baz, Fez, Fizz}};",
     )
 }
 
@@ -659,7 +659,7 @@ fn merge_groups_full_nested_long() {
     check_crate(
         "std::foo::bar::Baz",
         r"use std::{foo::bar::Qux};",
-        r"use std::{foo::bar::{Qux, Baz}};",
+        r"use std::{foo::bar::{Baz, Qux}};",
     );
 }
 
@@ -668,7 +668,7 @@ fn merge_groups_last_nested_long() {
     check_crate(
         "std::foo::bar::Baz",
         r"use std::{foo::bar::Qux};",
-        r"use std::{foo::bar::{Qux, Baz}};",
+        r"use std::{foo::bar::{Baz, Qux}};",
     );
 }
 
@@ -733,7 +733,7 @@ fn merge_mod_into_glob() {
     check_with_config(
         "token::TokenKind",
         r"use token::TokenKind::*;",
-        r"use token::TokenKind::{*, self};",
+        r"use token::TokenKind::{self, *};",
         &InsertUseConfig {
             granularity: ImportGranularity::Crate,
             enforce_granularity: true,
@@ -742,7 +742,6 @@ fn merge_mod_into_glob() {
             skip_glob_imports: false,
         },
     )
-    // FIXME: have it emit `use token::TokenKind::{self, *}`?
 }
 
 #[test]
@@ -750,7 +749,7 @@ fn merge_self_glob() {
     check_with_config(
         "self",
         r"use self::*;",
-        r"use self::{*, self};",
+        r"use self::{self, *};",
         &InsertUseConfig {
             granularity: ImportGranularity::Crate,
             enforce_granularity: true,
@@ -759,7 +758,6 @@ fn merge_self_glob() {
             skip_glob_imports: false,
         },
     )
-    // FIXME: have it emit `use {self, *}`?
 }
 
 #[test]
@@ -769,7 +767,7 @@ fn merge_glob() {
         r"
 use syntax::{SyntaxKind::*};",
         r"
-use syntax::{SyntaxKind::{*, self}};",
+use syntax::{SyntaxKind::{self, *}};",
     )
 }
 
@@ -778,7 +776,7 @@ fn merge_glob_nested() {
     check_crate(
         "foo::bar::quux::Fez",
         r"use foo::bar::{Baz, quux::*};",
-        r"use foo::bar::{Baz, quux::{*, Fez}};",
+        r"use foo::bar::{Baz, quux::{Fez, *}};",
     )
 }
 
@@ -787,7 +785,7 @@ fn merge_nested_considers_first_segments() {
     check_crate(
         "hir_ty::display::write_bounds_like_dyn_trait",
         r"use hir_ty::{autoderef, display::{HirDisplayError, HirFormatter}, method_resolution};",
-        r"use hir_ty::{autoderef, display::{HirDisplayError, HirFormatter, write_bounds_like_dyn_trait}, method_resolution};",
+        r"use hir_ty::{autoderef, display::{write_bounds_like_dyn_trait, HirDisplayError, HirFormatter}, method_resolution};",
     );
 }
 
diff --git a/crates/ide-db/src/imports/merge_imports.rs b/crates/ide-db/src/imports/merge_imports.rs
index df43bb553fc..c64599c6b58 100644
--- a/crates/ide-db/src/imports/merge_imports.rs
+++ b/crates/ide-db/src/imports/merge_imports.rs
@@ -1,10 +1,14 @@
 //! Handle syntactic aspects of merging UseTrees.
 use std::cmp::Ordering;
+use std::iter::{empty, successors};
 
 use itertools::{EitherOrBoth, Itertools};
+use parser::{SyntaxKind, T};
+use rustc_hash::{FxHashMap, FxHashSet};
 use syntax::{
-    ast::{self, AstNode, HasAttrs, HasName, HasVisibility, PathSegmentKind},
-    ted, TokenText,
+    ast::{self, make, AstNode, HasAttrs, HasName, HasVisibility, PathSegmentKind},
+    ted::{self, Position},
+    SyntaxElement, TokenText,
 };
 
 use crate::syntax_helpers::node_ext::vis_eq;
@@ -97,20 +101,35 @@ fn recursive_merge(lhs: &ast::UseTree, rhs: &ast::UseTree, merge: MergeBehavior)
         // same as a `filter` op).
         .map(|tree| merge.is_tree_allowed(&tree).then_some(tree))
         .collect::<Option<_>>()?;
+    // Preserves some positional formatting info before sorting.
+    let positional_formatting_map: FxHashMap<_, _> = use_trees
+        .iter()
+        .enumerate()
+        .filter_map(|(idx, tree)| {
+            formatting_whitespace(&SyntaxElement::from(tree.syntax().clone()))
+                .map(|trivia| (idx, trivia))
+        })
+        .collect();
+    let closing_formatting_trivia = if use_trees.len() > 0 {
+        lhs.use_tree_list()
+            .and_then(|list| list.r_curly_token())
+            .and_then(|token| formatting_whitespace(&SyntaxElement::from(token)))
+    } else {
+        None
+    };
+    // Sorts the use trees similar to rustfmt's algorithm for ordering imports
+    // (see `use_tree_cmp` doc).
     use_trees.sort_unstable_by(|a, b| use_tree_cmp(a, b));
     for rhs_t in rhs.use_tree_list().into_iter().flat_map(|list| list.use_trees()) {
         if !merge.is_tree_allowed(&rhs_t) {
             return None;
         }
-        let rhs_path = rhs_t.path();
 
-        match use_trees
-            .binary_search_by(|lhs_t| path_cmp_bin_search(lhs_t.path(), rhs_path.as_ref()))
-        {
+        match use_trees.binary_search_by(|lhs_t| use_tree_cmp_bin_search(lhs_t, &rhs_t)) {
             Ok(idx) => {
                 let lhs_t = &mut use_trees[idx];
                 let lhs_path = lhs_t.path()?;
-                let rhs_path = rhs_path?;
+                let rhs_path = rhs_t.path()?;
                 let (lhs_prefix, rhs_prefix) = common_prefix(&lhs_path, &rhs_path)?;
                 if lhs_prefix == lhs_path && rhs_prefix == rhs_path {
                     let tree_is_self = |tree: &ast::UseTree| {
@@ -159,13 +178,66 @@ fn recursive_merge(lhs: &ast::UseTree, rhs: &ast::UseTree, merge: MergeBehavior)
             {
                 return None
             }
-            Err(idx) => {
-                use_trees.insert(idx, rhs_t.clone());
-                lhs.get_or_create_use_tree_list().add_use_tree(rhs_t);
+            Err(insert_idx) => {
+                use_trees.insert(insert_idx, rhs_t.clone());
+                match lhs.use_tree_list() {
+                    // Creates a new use tree list with the item.
+                    None => lhs.get_or_create_use_tree_list().add_use_tree(rhs_t),
+                    // Recreates the use tree list with sorted items (see `use_tree_cmp` doc).
+                    // Also attempts to preserve formatting (but only in terms of index-based
+                    // "positions" of new lines and indents).
+                    Some(old_list) => {
+                        ted::remove(old_list.syntax());
+
+                        let new_list = make::use_tree_list(empty()).clone_for_update();
+                        let mut elements = Vec::new();
+                        for (idx, tree) in use_trees.iter().enumerate() {
+                            if idx > 0 {
+                                elements.push(make::token(T![,]).into());
+                            }
+                            match positional_formatting_map.get(&idx) {
+                                None if idx > 0 => {
+                                    elements.push(make::tokens::single_space().into())
+                                }
+                                Some(prev_trivia) => {
+                                    elements.extend(prev_trivia.clone().into_iter())
+                                }
+                                _ => (),
+                            }
+                            elements.push(tree.syntax().clone().into());
+                        }
+                        if let Some(ref trivia) = closing_formatting_trivia {
+                            elements.extend(trivia.clone().into_iter())
+                        }
+
+                        let trees_pos = match new_list.l_curly_token() {
+                            Some(l_curly) => Position::after(l_curly),
+                            None => Position::last_child_of(new_list.syntax()),
+                        };
+                        ted::insert_all_raw(trees_pos, elements);
+
+                        let list_pos = Position::last_child_of(lhs.syntax());
+                        ted::insert_raw(list_pos, new_list.syntax());
+                    }
+                }
             }
         }
     }
-    Some(())
+    return Some(());
+
+    // Returns all trivia preceding a syntax element if it may be relevant to formatting
+    // (i.e. includes at least one new line character).
+    fn formatting_whitespace(elem: &SyntaxElement) -> Option<FxHashSet<SyntaxElement>> {
+        let succ =
+            |item: &SyntaxElement| item.prev_sibling_or_token().filter(|it| it.kind().is_trivia());
+        let first = succ(elem);
+        let trivia_set: FxHashSet<_> = successors(first, succ).collect();
+        let contains_formatting_whitespace = trivia_set.iter().any(|it| {
+            it.kind() == SyntaxKind::WHITESPACE
+                && it.as_token().is_some_and(|token| token.text().contains('\n'))
+        });
+        contains_formatting_whitespace.then_some(trivia_set)
+    }
 }
 
 /// Traverses both paths until they differ, returning the common prefix of both.
@@ -190,70 +262,39 @@ pub fn common_prefix(lhs: &ast::Path, rhs: &ast::Path) -> Option<(ast::Path, ast
     }
 }
 
-/// Path comparison func for binary searching for merging.
-fn path_cmp_bin_search(lhs: Option<ast::Path>, rhs: Option<&ast::Path>) -> Ordering {
-    match (lhs.as_ref().and_then(ast::Path::first_segment), rhs.and_then(ast::Path::first_segment))
-    {
-        (None, None) => Ordering::Equal,
-        (None, Some(_)) => Ordering::Less,
+/// Use tree comparison func for binary searching for merging.
+fn use_tree_cmp_bin_search(lhs: &ast::UseTree, rhs: &ast::UseTree) -> Ordering {
+    match (
+        lhs.path().as_ref().and_then(ast::Path::first_segment),
+        rhs.path().as_ref().and_then(ast::Path::first_segment),
+    ) {
+        (None, None) => match (lhs.is_simple_path(), lhs.is_simple_path()) {
+            (true, true) => Ordering::Equal,
+            (true, false) => Ordering::Less,
+            (false, true) => Ordering::Greater,
+            (false, false) => use_tree_cmp_by_tree_list_glob_or_alias(lhs, rhs, false),
+        },
+        (Some(_), None) if !rhs.is_simple_path() => Ordering::Less,
         (Some(_), None) => Ordering::Greater,
+        (None, Some(_)) if !lhs.is_simple_path() => Ordering::Greater,
+        (None, Some(_)) => Ordering::Less,
         (Some(ref a), Some(ref b)) => path_segment_cmp(a, b),
     }
 }
 
-/// Orders use trees following `rustfmt`'s algorithm for ordering imports, which is `self`, `super` and `crate` first,
-/// then identifier imports with lowercase ones first and upper snake case (e.g. UPPER_SNAKE_CASE) ones last,
-/// then glob imports, and at last list imports.
+/// Orders use trees following `rustfmt`'s algorithm for ordering imports, which is `self`, `super`
+/// and `crate` first, then identifier imports with lowercase ones first and upper snake case
+/// (e.g. UPPER_SNAKE_CASE) ones last, then glob imports, and at last list imports.
 ///
 /// Example foo::{self, foo, baz, Baz, Qux, FOO_BAZ, *, {Bar}}
 /// Ref: <https://github.com/rust-lang/rustfmt/blob/6356fca675bd756d71f5c123cd053d17b16c573e/src/imports.rs#L83-L86>.
 pub(super) fn use_tree_cmp(a: &ast::UseTree, b: &ast::UseTree) -> Ordering {
-    let tiebreak_by_glob_or_alias = || match (a.star_token().is_some(), b.star_token().is_some()) {
-        (true, false) => Ordering::Greater,
-        (false, true) => Ordering::Less,
-        _ => match (a.rename(), b.rename()) {
-            (None, None) => Ordering::Equal,
-            (Some(_), None) => Ordering::Greater,
-            (None, Some(_)) => Ordering::Less,
-            (Some(a_rename), Some(b_rename)) => a_rename
-                .name()
-                .as_ref()
-                .map(ast::Name::text)
-                .as_ref()
-                .map_or("_", TokenText::as_str)
-                .cmp(
-                    b_rename
-                        .name()
-                        .as_ref()
-                        .map(ast::Name::text)
-                        .as_ref()
-                        .map_or("_", TokenText::as_str),
-                ),
-        },
-    };
-    let tiebreak_by_tree_list_glob_or_alias = || match (a.use_tree_list(), b.use_tree_list()) {
-        (None, None) => tiebreak_by_glob_or_alias(),
-        (Some(_), None) => Ordering::Greater,
-        (None, Some(_)) => Ordering::Less,
-        (Some(a_list), Some(b_list)) => a_list
-            .use_trees()
-            .zip_longest(b_list.use_trees())
-            .find_map(|zipped| match zipped {
-                EitherOrBoth::Both(ref a_tree, ref b_tree) => match use_tree_cmp(a_tree, b_tree) {
-                    Ordering::Equal => None,
-                    ord => Some(ord),
-                },
-                EitherOrBoth::Left(_) => Some(Ordering::Greater),
-                EitherOrBoth::Right(_) => Some(Ordering::Less),
-            })
-            .unwrap_or_else(tiebreak_by_glob_or_alias),
-    };
     match (a.path(), b.path()) {
         (None, None) => match (a.is_simple_path(), b.is_simple_path()) {
             (true, true) => Ordering::Equal,
             (true, false) => Ordering::Less,
             (false, true) => Ordering::Greater,
-            (false, false) => tiebreak_by_tree_list_glob_or_alias(),
+            (false, false) => use_tree_cmp_by_tree_list_glob_or_alias(a, b, true),
         },
         (Some(_), None) if !b.is_simple_path() => Ordering::Less,
         (Some(_), None) => Ordering::Greater,
@@ -277,7 +318,7 @@ pub(super) fn use_tree_cmp(a: &ast::UseTree, b: &ast::UseTree) -> Ordering {
                     EitherOrBoth::Right(_) if a.is_simple_path() => Some(Ordering::Less),
                     EitherOrBoth::Right(_) => Some(Ordering::Greater),
                 })
-                .unwrap_or_else(tiebreak_by_tree_list_glob_or_alias)
+                .unwrap_or_else(|| use_tree_cmp_by_tree_list_glob_or_alias(a, b, true))
         }
     }
 }
@@ -338,6 +379,61 @@ fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering {
     }
 }
 
+// Orders for use trees with equal paths (see `use_tree_cmp` for details about use tree ordering).
+//
+// If the `strict` parameter is set to true and both trees have tree lists, the tree lists are
+// ordered by calling `use_tree_cmp` on their "sub-tree" pairs until either the tie is broken
+// or tree list equality is confirmed, otherwise (i.e. if either `strict` is false or at least
+// one of the trees does *not* have tree list), this potentially recursive step is skipped,
+// and only the presence of a glob pattern or an alias is used to determine the ordering.
+fn use_tree_cmp_by_tree_list_glob_or_alias(
+    a: &ast::UseTree,
+    b: &ast::UseTree,
+    strict: bool,
+) -> Ordering {
+    let cmp_by_glob_or_alias = || match (a.star_token().is_some(), b.star_token().is_some()) {
+        (true, false) => Ordering::Greater,
+        (false, true) => Ordering::Less,
+        _ => match (a.rename(), b.rename()) {
+            (None, None) => Ordering::Equal,
+            (Some(_), None) => Ordering::Greater,
+            (None, Some(_)) => Ordering::Less,
+            (Some(a_rename), Some(b_rename)) => a_rename
+                .name()
+                .as_ref()
+                .map(ast::Name::text)
+                .as_ref()
+                .map_or("_", TokenText::as_str)
+                .cmp(
+                    b_rename
+                        .name()
+                        .as_ref()
+                        .map(ast::Name::text)
+                        .as_ref()
+                        .map_or("_", TokenText::as_str),
+                ),
+        },
+    };
+
+    match (a.use_tree_list(), b.use_tree_list()) {
+        (Some(_), None) => Ordering::Greater,
+        (None, Some(_)) => Ordering::Less,
+        (Some(a_list), Some(b_list)) if strict => a_list
+            .use_trees()
+            .zip_longest(b_list.use_trees())
+            .find_map(|zipped| match zipped {
+                EitherOrBoth::Both(ref a_tree, ref b_tree) => match use_tree_cmp(a_tree, b_tree) {
+                    Ordering::Equal => None,
+                    ord => Some(ord),
+                },
+                EitherOrBoth::Left(_) => Some(Ordering::Greater),
+                EitherOrBoth::Right(_) => Some(Ordering::Less),
+            })
+            .unwrap_or_else(cmp_by_glob_or_alias),
+        _ => cmp_by_glob_or_alias(),
+    }
+}
+
 pub fn eq_visibility(vis0: Option<ast::Visibility>, vis1: Option<ast::Visibility>) -> bool {
     match (vis0, vis1) {
         (None, None) => true,