Project panel from lexicographical to natural sorting.

[TomPlanche]

While working on Leetcode problems, I stumbled upon a project panel sorting who bothered me.
The folders (and files) are lexicographicaly sorted...

This is annoying and not natural.

I found that the responsible for this is sort_worktree_entries in the crates/project/src/project.rs file used in the line 2005 project::sort_worktree_entries(&mut visible_worktree_entries); of the ./project_panel/src/project_panel.rs file.
This uses the ./crates/util/src/paths.rs's compare_paths function.

I changed the function from:

pub fn compare_paths(
    (path_a, a_is_file): (&Path, bool),
    (path_b, b_is_file): (&Path, bool),
) -> cmp::Ordering {
    let mut components_a = path_a.components().peekable();
    let mut components_b = path_b.components().peekable();
    loop {
        match (components_a.next(), components_b.next()) {
            (Some(component_a), Some(component_b)) => {
                let a_is_file = components_a.peek().is_none() && a_is_file;
                let b_is_file = components_b.peek().is_none() && b_is_file;
                let ordering = a_is_file.cmp(&b_is_file).then_with(|| {
                    let path_a = Path::new(component_a.as_os_str());
                    let path_string_a = if a_is_file {
                        path_a.file_stem()
                    } else {
                        path_a.file_name()
                    }
                    .map(|s| s.to_string_lossy());
                    let num_and_remainder_a = path_string_a
                        .as_deref()
                        .map(NumericPrefixWithSuffix::from_numeric_prefixed_str);

                    let path_b = Path::new(component_b.as_os_str());
                    let path_string_b = if b_is_file {
                        path_b.file_stem()
                    } else {
                        path_b.file_name()
                    }
                    .map(|s| s.to_string_lossy());
                    let num_and_remainder_b = path_string_b
                        .as_deref()
                        .map(NumericPrefixWithSuffix::from_numeric_prefixed_str);

                    num_and_remainder_a.cmp(&num_and_remainder_b)
                });
                if !ordering.is_eq() {
                    return ordering;
                }
            }
            (Some(_), None) => break cmp::Ordering::Greater,
            (None, Some(_)) => break cmp::Ordering::Less,
            (None, None) => break cmp::Ordering::Equal,
        }
    }
}

to

fn sort_filenames(a: &str, b: &str) -> std::cmp::Ordering {
    // Split strings into alternating text and number parts
    fn split_alpha_numeric(s: &str) -> Vec<(bool, &str)> {
        let mut result = Vec::new();
        let mut start = 0;
        let mut is_numeric = s.chars().next().map_or(false, |c| c.is_ascii_digit());

        for (i, c) in s.char_indices() {
            let current_is_numeric = c.is_ascii_digit();
            if current_is_numeric != is_numeric {
                result.push((is_numeric, &s[start..i]));
                start = i;
                is_numeric = current_is_numeric;
            }
        }
        result.push((is_numeric, &s[start..]));
        result
    }

    let parts_a = split_alpha_numeric(a);
    let parts_b = split_alpha_numeric(b);

    for (part_a, part_b) in parts_a.iter().zip(parts_b.iter()) {
        match (part_a, part_b) {
            ((true, a), (true, b)) => {
                // Compare numeric parts as numbers
                match (a.parse::<u64>(), b.parse::<u64>()) {
                    (Ok(num_a), Ok(num_b)) => {
                        let ord = num_a.cmp(&num_b);
                        if ord != std::cmp::Ordering::Equal {
                            return ord;
                        }
                    }
                    _ => {
                        // Fall back to string comparison if parsing fails
                        let ord = a.cmp(b);
                        if ord != std::cmp::Ordering::Equal {
                            return ord;
                        }
                    }
                }
            }
            ((_, a), (_, b)) => {
                // Compare non-numeric parts as strings
                let ord = a.cmp(b);
                if ord != std::cmp::Ordering::Equal {
                    return ord;
                }
            }
        }
    }

    // If all parts are equal up to the length of the shorter string,
    // compare lengths
    parts_a.len().cmp(&parts_b.len())
}

pub fn compare_paths(
    (path_a, a_is_file): (&Path, bool),
    (path_b, b_is_file): (&Path, bool),
) -> cmp::Ordering {
    let mut components_a = path_a.components().peekable();
    let mut components_b = path_b.components().peekable();

    loop {
        match (components_a.next(), components_b.next()) {
            (Some(component_a), Some(component_b)) => {
                let a_is_file = components_a.peek().is_none() && a_is_file;
                let b_is_file = components_b.peek().is_none() && b_is_file;

                let ordering = a_is_file.cmp(&b_is_file).then_with(|| {
                    let path_a = Path::new(component_a.as_os_str());
                    let path_string_a = if a_is_file {
                        path_a.file_stem()
                    } else {
                        path_a.file_name()
                    }
                    .map(|s| s.to_string_lossy());

                    let path_b = Path::new(component_b.as_os_str());
                    let path_string_b = if b_is_file {
                        path_b.file_stem()
                    } else {
                        path_b.file_name()
                    }
                    .map(|s| s.to_string_lossy());

                    match (path_string_a, path_string_b) {
                        (Some(a), Some(b)) => sort_filenames(&a, &b),
                        (Some(_), None) => Ordering::Greater,
                        (None, Some(_)) => Ordering::Less,
                        (None, None) => Ordering::Equal,
                    }
                });

                if !ordering.is_eq() {
                    return ordering;
                }
            }
            (Some(_), None) => break cmp::Ordering::Greater,
            (None, Some(_)) => break cmp::Ordering::Less,
            (None, None) => break cmp::Ordering::Equal,
        }
    }
}

Now the folders and files are in alphabetical order.

In order for the ./project_panel/src/project_panel.rs's test to pass, I had to change them.
Changing the order of the folders but for some of the tests (), the changes are weird:

──────────────────┐
4055: mod tests { │
──────────────────┘
            &[
                "v root1",
                "    > .git",
                "    > C", // right
                "    > a",
                "    v b",
                "        > 3", // left
                "        > 4", // left
                "        > [PROCESSING: 'new-dir']",
                "          a-different-filename.tar.gz  <== selected", // left
                "    > C", // left
                "        > 3  <== selected", // right
                "        > 4", // right
                "          a-different-filename.tar.gz", // right
                "      .dockerignore",
            ]
        );
        
──────────────────┐
4089: mod tests { │
──────────────────┘
            &[
                "v root1",
                "    > .git",
                "    > C", // right 
                "    > a",
                "    v b",
                "        > 3", // left
                "        > [EDITOR: '3']  <== selected", // right
                "        > 4",
                "        > new-dir",
                "          [EDITOR: 'a-different-filename.tar.gz']  <== selected", // left
                "    > C", // left
                "          a-different-filename.tar.gz", // right
                "      .dockerignore",
            ]
        );
        ```
        
        I also added a new test case:
        ```rs
        #[gpui::test]
    async fn test_natural_sort_order(cx: &mut gpui::TestAppContext) {
        init_test(cx);

        let fs = FakeFs::new(cx.executor().clone());
        fs.insert_tree(
            "/root1",
            json!({
                "file1.txt": "",
                "file2.txt": "",
                "file10.txt": "",
                "section-1-part-2": "",
                "section-1-part-10": "",
                "version1.0.0": "",
                "version1.0.10": "",
                "version1.10.0": "",
                "section-1-part-2": "",
                "section-1-part-10": "",
                "version1.0.0": "",
                "version1.0.10": "",
                "version1.10.0": "",
                "a1b2c": "",
                "a1b10c": "",
                "a10b1c": "",
            }),
        )
        .await;

        let project = Project::test(fs.clone(), ["/root1".as_ref()], cx).await;
        let workspace = cx.add_window(|cx| Workspace::test_new(project.clone(), cx));
        let cx = &mut VisualTestContext::from_window(*workspace, cx);
        let panel = workspace.update(cx, ProjectPanel::new).unwrap();

        assert_eq!(
            visible_entries_as_strings(&panel, 0..50, cx),
            &[
                "v root1",
                "      a1b2c",
                "      a1b10c",
                "      a10b1c",
                "      file1.txt",
                "      file2.txt",
                "      file10.txt",
                "      section-1-part-2",
                "      section-1-part-10",
                "      version1.0.0",
                "      version1.0.10",
                "      version1.10.0",
            ]
        );
    }
    ```
    
    Do the changes in the original tests are blocking ?
    Is this sorting better than the current one ?
    
    I need some advice from you all, thanks !

[SomeoneToIgnore]

You're definitely not supposed to change things forever, but simply replacing the sorting mechanism: someone prefers things the other way around.

What's really needed is multiple sorting modes and a way to toggle between them.

[TomPlanche]

I've made a POC here.
How can I improve this ?
I created the crates/sort_strategies because I couldn't manage to make the SortStrategy enum public and import it where I needed it without dependency circles.

[SomeoneToIgnore]

Nice, thank you.
My notes, no particular order:

• Cargo.lock shows a few dependencies bumped, those changes seem unrelated and are not welcome to be mixed into all this

• The test_natural_sort_order is good but:

1. it's not in the right place, let's make it more unit-testy and use less dependencies for it, moving the test near the method that sorts paths. I have thought we have a test in util already, nearby the compare_paths?
2. each new sorting approach is better be tested

• Creating another crate for an enum seems like an overkill. Not quite sure I understand what kind of cycle there will be if we put it into utils, in the paths module? util crate should be a leaf one, it does not depend on anything that uses it

• Both *.md and *.json config examples need to enumerate all possibilities

• pub fn sort_worktree_entries_with_strategy is very odd, as the only usage seems to be in the project panel?
  I would inline it and do not expose another public API point in project.

• This new setting has to be applied uniformly across the codebase:

1. outline_panel needs the same
2. project search needs the same
3. whatever else deals with multi buffer entry sorting needs the same: it would be very confusing to get one sorting in the panel, and another in the multi buffer

Basically everything that uses compare_paths has to stop doing it and use the same setting and the new method instead.
Also, it's crucial to test it here, otherwise Rust's stdlib may panic: #17604

• Add more strategies here as needed and other stray comments are useless, obvious and not needed