Make import sorting order follow 2024 edition style

5 files changed, 219 insertions, 50 deletions

diff --git a/src/tools/rust-analyzer/crates/ide-assists/src/handlers/merge_imports.rs b/src/tools/rust-analyzer/crates/ide-assists/src/handlers/merge_imports.rs
index 6bf7f584914..9ba73d23dd2 100644
--- a/src/tools/rust-analyzer/crates/ide-assists/src/handlers/merge_imports.rs
+++ b/src/tools/rust-analyzer/crates/ide-assists/src/handlers/merge_imports.rs
@@ -605,7 +605,7 @@ use foo::$0{
 ",
             r"
 use foo::{
-    bar::baz, FooBar
+    FooBar, bar::baz,
 };
 ",
         )
diff --git a/src/tools/rust-analyzer/crates/ide-assists/src/handlers/normalize_import.rs b/src/tools/rust-analyzer/crates/ide-assists/src/handlers/normalize_import.rs
index bba28b5fc8a..36da1d17882 100644
--- a/src/tools/rust-analyzer/crates/ide-assists/src/handlers/normalize_import.rs
+++ b/src/tools/rust-analyzer/crates/ide-assists/src/handlers/normalize_import.rs
@@ -109,8 +109,8 @@ mod tests {
     #[test]
     fn test_order() {
         check_assist_variations!(
-            "foo::{*, Qux, bar::{Quux, Bar}, baz, FOO_BAZ, self, Baz}",
-            "foo::{self, bar::{Bar, Quux}, baz, Baz, Qux, FOO_BAZ, *}"
+            "foo::{*, Qux, bar::{Quux, Bar}, baz, FOO_BAZ, self, Baz, v10, v9, r#aaa}",
+            "foo::{self, Baz, FOO_BAZ, Qux, r#aaa, bar::{Bar, Quux}, baz, v9, v10, *}"
         );
     }
 
@@ -145,17 +145,17 @@ fn main() {
 
     #[test]
     fn test_redundant_braces() {
-        check_assist_variations!("foo::{bar::{baz, Qux}}", "foo::bar::{baz, Qux}");
+        check_assist_variations!("foo::{bar::{baz, Qux}}", "foo::bar::{Qux, baz}");
         check_assist_variations!("foo::{bar::{self}}", "foo::bar::{self}");
         check_assist_variations!("foo::{bar::{*}}", "foo::bar::*");
         check_assist_variations!("foo::{bar::{Qux as Quux}}", "foo::bar::Qux as Quux");
         check_assist_variations!(
             "foo::bar::{{FOO_BAZ, Qux, self}, {*, baz}}",
-            "foo::bar::{self, baz, Qux, FOO_BAZ, *}"
+            "foo::bar::{self, FOO_BAZ, Qux, baz, *}"
         );
         check_assist_variations!(
             "foo::bar::{{{FOO_BAZ}, {{Qux}, {self}}}, {{*}, {baz}}}",
-            "foo::bar::{self, baz, Qux, FOO_BAZ, *}"
+            "foo::bar::{self, FOO_BAZ, Qux, baz, *}"
         );
     }
 
@@ -163,11 +163,11 @@ fn main() {
     fn test_merge() {
         check_assist_variations!(
             "foo::{*, bar, {FOO_BAZ, qux}, bar::{*, baz}, {Quux}}",
-            "foo::{bar::{self, baz, *}, qux, Quux, FOO_BAZ, *}"
+            "foo::{FOO_BAZ, Quux, bar::{self, baz, *}, qux, *}"
         );
         check_assist_variations!(
             "foo::{*, bar, {FOO_BAZ, qux}, bar::{*, baz}, {Quux, bar::{baz::Foo}}}",
-            "foo::{bar::{self, baz::{self, Foo}, *}, qux, Quux, FOO_BAZ, *}"
+            "foo::{FOO_BAZ, Quux, bar::{self, baz::{self, Foo}, *}, qux, *}"
         );
     }
 
@@ -229,15 +229,15 @@ use {
         check_assist_not_applicable_variations!("foo::bar");
         check_assist_not_applicable_variations!("foo::bar::*");
         check_assist_not_applicable_variations!("foo::bar::Qux as Quux");
-        check_assist_not_applicable_variations!("foo::bar::{self, baz, Qux, FOO_BAZ, *}");
+        check_assist_not_applicable_variations!("foo::bar::{self, FOO_BAZ, Qux, baz, *}");
         check_assist_not_applicable_variations!(
-            "foo::{self, bar::{Bar, Quux}, baz, Baz, Qux, FOO_BAZ, *}"
+            "foo::{self, Baz, FOO_BAZ, Qux, bar::{Bar, Quux}, baz, *}"
         );
         check_assist_not_applicable_variations!(
-            "foo::{bar::{self, baz, *}, qux, Quux, FOO_BAZ, *}"
+            "foo::{FOO_BAZ, Quux, bar::{self, baz, *}, qux, *}"
         );
         check_assist_not_applicable_variations!(
-            "foo::{bar::{self, baz::{self, Foo}, *}, qux, Quux, FOO_BAZ, *}"
+            "foo::{bar::{self, FOO_BAZ, Quux, baz::{self, Foo}, *}, qux, *}"
         );
     }
 }
diff --git a/src/tools/rust-analyzer/crates/ide-completion/src/tests/flyimport.rs b/src/tools/rust-analyzer/crates/ide-completion/src/tests/flyimport.rs
index 27c91bc7c45..04bed418eec 100644
--- a/src/tools/rust-analyzer/crates/ide-completion/src/tests/flyimport.rs
+++ b/src/tools/rust-analyzer/crates/ide-completion/src/tests/flyimport.rs
@@ -114,7 +114,7 @@ fn main() {
 }
 "#,
         r#"
-use dep::{some_module::{SecondStruct, ThirdStruct}, FirstStruct};
+use dep::{FirstStruct, some_module::{SecondStruct, ThirdStruct}};
 
 fn main() {
     ThirdStruct
diff --git a/src/tools/rust-analyzer/crates/ide-db/src/imports/insert_use/tests.rs b/src/tools/rust-analyzer/crates/ide-db/src/imports/insert_use/tests.rs
index 4a00854f01a..3350e1c3d20 100644
--- a/src/tools/rust-analyzer/crates/ide-db/src/imports/insert_use/tests.rs
+++ b/src/tools/rust-analyzer/crates/ide-db/src/imports/insert_use/tests.rs
@@ -782,18 +782,18 @@ fn merge_groups_long_last_list() {
 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::{quux::{Fez, Fizz}, Baz, Qux};",
+        r"use std::foo::bar::{quux::{Fez, Fizz}, Qux};",
+        r"use std::foo::bar::{Baz, Qux, quux::{Fez, Fizz}};",
     );
     check_crate(
         "std::foo::bar::r#Baz",
-        r"use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
-        r"use std::foo::bar::{quux::{Fez, Fizz}, r#Baz, Qux};",
+        r"use std::foo::bar::{quux::{Fez, Fizz}, Qux};",
+        r"use std::foo::bar::{r#Baz, Qux, quux::{Fez, Fizz}};",
     );
     check_one(
         "std::foo::bar::Baz",
-        r"use {std::foo::bar::{Qux, quux::{Fez, Fizz}}};",
-        r"use {std::foo::bar::{quux::{Fez, Fizz}, Baz, Qux}};",
+        r"use {std::foo::bar::{quux::{Fez, Fizz}}, Qux};",
+        r"use {Qux, std::foo::bar::{Baz, quux::{Fez, Fizz}}};",
     );
 }
 
@@ -811,13 +811,13 @@ use std::foo::bar::{Qux, quux::{Fez, Fizz}};",
 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::{quux::{Baz, Fez, Fizz}, Qux};",
+        r"use std::foo::bar::{quux::{Fez, Fizz}, Qux};",
+        r"use std::foo::bar::{Qux, quux::{Baz, Fez, Fizz}};",
     );
     check_one(
         "std::foo::bar::quux::Baz",
-        r"use {std::foo::bar::{Qux, quux::{Fez, Fizz}}};",
-        r"use {std::foo::bar::{quux::{Baz, Fez, Fizz}, Qux}};",
+        r"use {std::foo::bar::{quux::{Fez, Fizz}}, Qux};",
+        r"use {Qux, std::foo::bar::quux::{Baz, Fez, Fizz}};",
     );
 }
 
@@ -988,8 +988,8 @@ use syntax::SyntaxKind::{self, *};",
 fn merge_glob_nested() {
     check_crate(
         "foo::bar::quux::Fez",
-        r"use foo::bar::{Baz, quux::*};",
-        r"use foo::bar::{quux::{Fez, *}, Baz};",
+        r"use foo::bar::{quux::*, Baz};",
+        r"use foo::bar::{Baz, quux::{Fez, *}};",
     )
 }
 
@@ -998,7 +998,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::{write_bounds_like_dyn_trait, HirDisplayError, HirFormatter}, method_resolution};",
+        r"use hir_ty::{autoderef, display::{HirDisplayError, HirFormatter, write_bounds_like_dyn_trait}, method_resolution};",
     );
 }
 
diff --git a/src/tools/rust-analyzer/crates/ide-db/src/imports/merge_imports.rs b/src/tools/rust-analyzer/crates/ide-db/src/imports/merge_imports.rs
index 61962e59347..4e779a7d858 100644
--- a/src/tools/rust-analyzer/crates/ide-db/src/imports/merge_imports.rs
+++ b/src/tools/rust-analyzer/crates/ide-db/src/imports/merge_imports.rs
@@ -3,7 +3,6 @@ use std::cmp::Ordering;
 
 use itertools::{EitherOrBoth, Itertools};
 use parser::T;
-use stdx::is_upper_snake_case;
 use syntax::{
     Direction, SyntaxElement, algo,
     ast::{
@@ -543,12 +542,13 @@ fn use_tree_cmp_bin_search(lhs: &ast::UseTree, rhs: &ast::UseTree) -> Ordering {
     }
 }
 
-/// 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 version sorting algorithm for ordering imports.
 ///
-/// Example: `foo::{self, baz, foo, Baz, Qux, FOO_BAZ, *, {Bar}}`
-/// Ref: <https://github.com/rust-lang/rustfmt/blob/6356fca675bd756d71f5c123cd053d17b16c573e/src/imports.rs#L83-L86>.
+/// Example: `foo::{self, Baz, FOO_BAZ, Qux, baz, foo, *, {Bar}}`
+///
+/// Ref:
+///   - <https://doc.rust-lang.org/style-guide/index.html#sorting>
+///   - <https://doc.rust-lang.org/edition-guide/rust-2024/rustfmt.html>
 pub(super) fn use_tree_cmp(a: &ast::UseTree, b: &ast::UseTree) -> Ordering {
     let a_is_simple_path = a.is_simple_path() && a.rename().is_none();
     let b_is_simple_path = b.is_simple_path() && b.rename().is_none();
@@ -613,26 +613,9 @@ fn path_segment_cmp(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering {
                 (Some(_), None) => Ordering::Greater,
                 (None, Some(_)) => Ordering::Less,
                 (Some(a_name), Some(b_name)) => {
-                    // snake_case < UpperCamelCase < UPPER_SNAKE_CASE
                     let a_text = a_name.as_str().trim_start_matches("r#");
                     let b_text = b_name.as_str().trim_start_matches("r#");
-                    if a_text.starts_with(char::is_lowercase)
-                        && b_text.starts_with(char::is_uppercase)
-                    {
-                        return Ordering::Less;
-                    }
-                    if a_text.starts_with(char::is_uppercase)
-                        && b_text.starts_with(char::is_lowercase)
-                    {
-                        return Ordering::Greater;
-                    }
-                    if !is_upper_snake_case(a_text) && is_upper_snake_case(b_text) {
-                        return Ordering::Less;
-                    }
-                    if is_upper_snake_case(a_text) && !is_upper_snake_case(b_text) {
-                        return Ordering::Greater;
-                    }
-                    a_text.cmp(b_text)
+                    version_sort::version_sort(a_text, b_text)
                 }
             }
         }
@@ -740,3 +723,189 @@ fn remove_subtree_if_only_self(use_tree: &ast::UseTree) {
         _ => (),
     }
 }
+
+// Taken from rustfmt
+// https://github.com/rust-lang/rustfmt/blob/0332da01486508710f2a542111e40513bfb215aa/src/sort.rs
+mod version_sort {
+    // Original rustfmt code contains some clippy lints.
+    // Suppress them to minimize changes from upstream.
+    #![allow(clippy::all)]
+
+    use std::cmp::Ordering;
+
+    use itertools::{EitherOrBoth, Itertools};
+
+    struct VersionChunkIter<'a> {
+        ident: &'a str,
+        start: usize,
+    }
+
+    impl<'a> VersionChunkIter<'a> {
+        pub(crate) fn new(ident: &'a str) -> Self {
+            Self { ident, start: 0 }
+        }
+
+        fn parse_numeric_chunk(
+            &mut self,
+            mut chars: std::str::CharIndices<'a>,
+        ) -> Option<VersionChunk<'a>> {
+            let mut end = self.start;
+            let mut is_end_of_chunk = false;
+
+            while let Some((idx, c)) = chars.next() {
+                end = self.start + idx;
+
+                if c.is_ascii_digit() {
+                    continue;
+                }
+
+                is_end_of_chunk = true;
+                break;
+            }
+
+            let source = if is_end_of_chunk {
+                let value = &self.ident[self.start..end];
+                self.start = end;
+                value
+            } else {
+                let value = &self.ident[self.start..];
+                self.start = self.ident.len();
+                value
+            };
+
+            let zeros = source.chars().take_while(|c| *c == '0').count();
+            let value = source.parse::<usize>().ok()?;
+
+            Some(VersionChunk::Number { value, zeros, source })
+        }
+
+        fn parse_str_chunk(
+            &mut self,
+            mut chars: std::str::CharIndices<'a>,
+        ) -> Option<VersionChunk<'a>> {
+            let mut end = self.start;
+            let mut is_end_of_chunk = false;
+
+            while let Some((idx, c)) = chars.next() {
+                end = self.start + idx;
+
+                if c == '_' {
+                    is_end_of_chunk = true;
+                    break;
+                }
+
+                if !c.is_ascii_digit() {
+                    continue;
+                }
+
+                is_end_of_chunk = true;
+                break;
+            }
+
+            let source = if is_end_of_chunk {
+                let value = &self.ident[self.start..end];
+                self.start = end;
+                value
+            } else {
+                let value = &self.ident[self.start..];
+                self.start = self.ident.len();
+                value
+            };
+
+            Some(VersionChunk::Str(source))
+        }
+    }
+
+    impl<'a> Iterator for VersionChunkIter<'a> {
+        type Item = VersionChunk<'a>;
+
+        fn next(&mut self) -> Option<Self::Item> {
+            let mut chars = self.ident[self.start..].char_indices();
+            let (_, next) = chars.next()?;
+
+            if next == '_' {
+                self.start = self.start + next.len_utf8();
+                return Some(VersionChunk::Underscore);
+            }
+
+            if next.is_ascii_digit() {
+                return self.parse_numeric_chunk(chars);
+            }
+
+            self.parse_str_chunk(chars)
+        }
+    }
+
+    /// Represents a chunk in the version-sort algorithm
+    #[derive(Debug, PartialEq, Eq)]
+    enum VersionChunk<'a> {
+        /// A single `_` in an identifier. Underscores are sorted before all other characters.
+        Underscore,
+        /// A &str chunk in the version sort.
+        Str(&'a str),
+        /// A numeric chunk in the version sort. Keeps track of the numeric value and leading zeros.
+        Number { value: usize, zeros: usize, source: &'a str },
+    }
+
+    /// Determine which side of the version-sort comparison had more leading zeros.
+    #[derive(Debug, PartialEq, Eq)]
+    enum MoreLeadingZeros {
+        Left,
+        Right,
+        Equal,
+    }
+
+    pub(super) fn version_sort(a: &str, b: &str) -> Ordering {
+        let iter_a = VersionChunkIter::new(a);
+        let iter_b = VersionChunkIter::new(b);
+        let mut more_leading_zeros = MoreLeadingZeros::Equal;
+
+        for either_or_both in iter_a.zip_longest(iter_b) {
+            match either_or_both {
+                EitherOrBoth::Left(_) => return std::cmp::Ordering::Greater,
+                EitherOrBoth::Right(_) => return std::cmp::Ordering::Less,
+                EitherOrBoth::Both(a, b) => match (a, b) {
+                    (VersionChunk::Underscore, VersionChunk::Underscore) => {
+                        continue;
+                    }
+                    (VersionChunk::Underscore, _) => return std::cmp::Ordering::Less,
+                    (_, VersionChunk::Underscore) => return std::cmp::Ordering::Greater,
+                    (VersionChunk::Str(ca), VersionChunk::Str(cb))
+                    | (VersionChunk::Str(ca), VersionChunk::Number { source: cb, .. })
+                    | (VersionChunk::Number { source: ca, .. }, VersionChunk::Str(cb)) => {
+                        match ca.cmp(&cb) {
+                            std::cmp::Ordering::Equal => {
+                                continue;
+                            }
+                            order @ _ => return order,
+                        }
+                    }
+                    (
+                        VersionChunk::Number { value: va, zeros: lza, .. },
+                        VersionChunk::Number { value: vb, zeros: lzb, .. },
+                    ) => match va.cmp(&vb) {
+                        std::cmp::Ordering::Equal => {
+                            if lza == lzb {
+                                continue;
+                            }
+
+                            if more_leading_zeros == MoreLeadingZeros::Equal && lza > lzb {
+                                more_leading_zeros = MoreLeadingZeros::Left;
+                            } else if more_leading_zeros == MoreLeadingZeros::Equal && lza < lzb {
+                                more_leading_zeros = MoreLeadingZeros::Right;
+                            }
+                            continue;
+                        }
+                        order @ _ => return order,
+                    },
+                },
+            }
+        }
+
+        match more_leading_zeros {
+            MoreLeadingZeros::Equal => std::cmp::Ordering::Equal,
+            MoreLeadingZeros::Left => std::cmp::Ordering::Less,
+            MoreLeadingZeros::Right => std::cmp::Ordering::Greater,
+        }
+    }
+}