ACP: add `str::version_cmp`

[lolbinarycat]

Proposal

Problem statement

"version sorting" as defined by the rust style guide is a broadly useful operation, and using it instead of lexicographic sorting is usually one of the first things done to improve a program's user-friendlyness.

Motivating examples or use cases

This operation is currently used in many places throughout the project, and currently that is done by copy-pasting the implementation all over, leading to inconsistencies.

This is not just useful within the project, though, pretty much anything that wants to present a sorted list of strings would benefit from this, from file browsers, irc clients, email clients, text editors, static site generators, command-line argument parsers (to sort the autogenerated helptext) and even games (for inventories).

Solution sketch

impl str {
  fn version_cmp(&self, other: &str) -> std::cmp::Ordering;
}

Alternatives

• More complicated and configurable system. I don't think most users will care about what exact sorting is used, and the few that do (such as those within the project) only care that it is the sorting defined in the style guide.
• Publish as a standalone crate. I don't think a function that is well under 200 LoC needs to be split off like this, we don't need another cfg-if.
• Also include a utility function <&mut [impl AsRef<&str>]>::version_sort instead of requiring user to call sort_by.
• Better name that doesn't imply an overly narrow usecase.

Links and related work

• Sorting has drifted between rustfmt, rustdoc, and other places where it matters rust#151934, the issue that inspired this ACP
• Tracking issue for cfg_select (formerly cfg_match) rust#115585, cfg-select (formerly cfg-match), for precedence on including small utilities like this in the stdlib over having them be separate crates.

Additional Notes

I couldn't find a popular implementation of this on crates.io, which suggests either:

• Most people using version sorting are rolling their own implementation
• People aren't using version sorting in situations where it would make sense due to not wanting to add another dependency
• I didn't look hard enough

Hopefully adding this to the standard library would result in more people using version sorting where applicable, and thus higher quality Rust software in general.

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[clarfonthey]

FWIW, the main reason why I didn't propose an ACP for this initially is because "version comparison" is extremely subjective and depends on the situation. While the sorting from the Rust style guide is one implementation, there's also the logic that Cargo uses for crate versions, which is another valid "version" sorting implementation.

That said, there are potentially cases of code that could use this form of sorting, like proc_macro::Ident, or maybe a later version of compile-time reflection.

[programmerjake]

imo the name should probably be more specific to avoid confusing people who are looking for a different kind of version sorting. how about version_cmp_rustfmt or style_guide_version_cmp?

[programmerjake]

an alternative is to not even mention version in the name and name it friendly_cmp or something.

[tgross35]

I'm not sure there is a convincing argument that this is useful outside of rust-lang. The style guide includes this statement:

This algorithm does not purport to precisely match the behavior of any particular other algorithm, only to produce a simple and satisfying result for Rust formatting.

Also what would we do if the style guide changes over an edition?

[ChrisDenton]

Could it not just live somewhere in rustc_driver? Most tooling uses that in some way, no?

[kennytm]

The term "version sorting" is very confusing, because it suggests the function compares like semver, but this function using the style guide's definition would give us "1.2.3-beta" > "1.2.3".

Other standard library usually call this kind of ordering "natural ordering" (e.g. PHP's strnatcmp) or "numeric ordering" (e.g. JavaScript's numeric property). Note that "natural ordering" recognizes leading zeroes, which leads to a slightly different ordering ("9.099" < "9.11" in PHP but "9.099" > "9.11" in rustfmt)

[traviscross]

Cc @tmandry regarding rust-lang/rfcs#3905.

We talked about this in the libs-api call today. The feeling was that having this API makes sense (e.g., it'd be useful to have a library equivalent to the sort logic of cfg_version) but that it's likely to need a lot of refinement in nightly. There are many details to version sorting. We'll need to make sure that it's fully documented how this is done and that it aligns with what ends up being done with cfg_version and how things work in Cargo (noting that the version sort there is a partial order).

[clarfonthey]

I would also be very in favour of having the style guide logic specifically for stuff like reflection and proc macros: while it's not critical for automatically generated code to follow style guidelines, it would be very useful to just use the same code as Rust itself instead of duplicating it. And such code, being specific to the style guide implementation, could always take an edition argument just in case.

[ChrisDenton]

it'd be useful to have a library equivalent to the sort logic of cfg_version

The cfg_version RFC as currently proposed is far simpler. It basically splits a version string on . and then parses each component as an integer.

[ChrisDenton]

I would also be very in favour of having the style guide logic specifically for stuff like reflection and proc macros: while it's not critical for automatically generated code to follow style guidelines, it would be very useful to just use the same code as Rust itself instead of duplicating it. And such code, being specific to the style guide implementation, could always take an edition argument just in case.

That makes it sound like it should live in the proc_macro crate. At the very least it does seem weird to me to have such a rust-lang specific utility function as an associate method on str.

[tgross35]

It could be a nice idea to have a natural sort and/or a well-defined version sort algorithm in std. But I think it would be a mistake to attempt to line this up with the algorithms used by the style guide, rustfmt, Cargo, cfg_version, etc. or to document it as such, because ability to evolve those algorithms shouldn't be bound by the API stability guarantees of std.

• Publish as a standalone crate. I don't think a function that is well under 200 LoC needs to be split off like this, we don't need another cfg-if.

Small crates aren't bad and cfg-if isn't a great comparison here, the necessity is significantly different.

A theoretical rustc-simple-utils crate could have a few algorithms such as style_guide_sort, cargo_version_sort, etc. It could also serve as a home for other dependency-free helpers to make user code a bit closer to what rust-lang tooling does (e.g. latest_stable_version(&[&str]) -> &str or valid_version_string(&str) -> bool).

[lolbinarycat]

Could it not just live somewhere in rustc_driver? Most tooling uses that in some way, no?

I believe libtest doesn't, which is one of the places we're using this.

[tmandry]

I think we would have the property that strings accepted by both cfg_version and this API would be sorted the same, even if cfg_version starts supporting prereleases.

That said, I would recommend against using the word "version" to name both of these things. They are simply too different and the name suggests something far more similar.

Other terms I could find for this are alphanum order and natural order.