Consider using human/natural sort order

[tanriol]

Names used in libraries quite often contain numbers. In general, a sequence of digits in a name seems to be usually a number, not just a sequence of digits. However, rustfmt's sort order does not take that into account. For example, if I import several nom parsers for various integers, rustfmt suggests the following order

use nom::number::complete::{le_u128, le_u16, le_u32, le_u64, le_u8};

which feels really weird compared to

use nom::number::complete::{le_u8, le_u16, le_u32, le_u64, le_u128};

It would be great if the rustfmt sort order matched the natural expectations.

[joshtriplett]

Agreed. We should use the versionsort/strverscmp algorithm, documented at https://www.gnu.org/software/libc/manual/html_node/String_002fArray-Comparison.html .

[tanriol]

Hm. Looking at the linked documentation

Digits are determined by the isdigit function and are thus subject to the current locale.

is my expectation correct that rustfmt should not rely on the environment locale and should sort according to some default?

Also, what's the process here? Is anything needed before implementation and rustfmt PR?

[strega-nil]

@tanriol it's likely that as an MVP, we should just do strverscmp in the C locale (i.e., 0-9 are digits and are read from left to right, big end to small end)

[tanriol]

Would it be better to depend on some crate providing natural/version sort or to write an internal function for that?

[joshtriplett]

@tanriol I meant that as a general description of the algorithm. I would expect us to use 0-9 here for now, and I think we can implement the algorithm ourselves in Rust unless there's a crate handy that you already know of.

[tanriol]

Working on a PR and testing it, I'm seeing contradictions between actual tests and comment in them. Which ones should I follow?

[tanriol]

The PR is up as rust-lang/rustfmt#3764.

[calebcartwright]

Closing as I believe this issue has served its purposed. The Style Team agreed, decided upon a matching sort algorithm, set that as the default for Style Edition 2024 and beyond, and it's now been fully implemented within rustfmt (n.b. there's still an unstable option reorder_impl_items that needs to switch to this new algorithm, but all stable sorting formatting applies this new algorithm)