Import sorting does not handle uppercase/lowercase consistently

[joshtriplett]

This may be related to #4648 , but I don't know if it's the same issue.

rustfmt sorts imports, and braced groups within imports, in the following order:

use a;
use aA;
use aa;
use Aa;
use WoRD;
use Word;
use A;
use AA;
use WORD;

use brace_group_sort_test::{a, aA, aa, Aa, WoRD, Word, A, AA, WORD};

This isn't alphabetical, ASCIIbetical, or any other sort order that I can identify.

The style guide says to sort ascii-betically here, in both cases (top-level and within braced lists).

[ytmimi]

Thanks for the report!

Confirming that I'm able to reproduce this on rustfmt 1.4.38-nightly (b4de150d 2022-03-12). I'll try to set aside some time later to look a little deeper into this.

[joshtriplett]

@ytmimi Thank you!

[ytmimi]

I did some digging and I think the formatting you're seeing is caused by the implementation of Ord for UseSegment. As highlighted by the comment (line 776) we're trying to preserve the order based on snake_case < CamelCase < UPPER_SNAKE_CASE, before taking into account the ASCIIbetical order.

rustfmt/src/imports.rs

Lines 761 to 780 in 1bb85bd

	impl Ord for UseSegment {
	fn cmp(&self, other: &UseSegment) -> Ordering {
	use self::UseSegment::*;
	fn is_upper_snake_case(s: &str) -> bool {
	s.chars()
	.all(|c| c.is_uppercase() || c == '_' || c.is_numeric())
	}
	match (self, other) {
	(&Slf(ref a), &Slf(ref b))
	| (&Super(ref a), &Super(ref b))
	| (&Crate(ref a), &Crate(ref b)) => a.cmp(b),
	(&Glob, &Glob) => Ordering::Equal,
	(&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => {
	// snake_case < CamelCase < UPPER_SNAKE_CASE
	if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) {
	return Ordering::Greater;
	}
	if ia.starts_with(char::is_lowercase) && ib.starts_with(char::is_uppercase) {

[ytmimi]

It also looks like we're not doing an explicit "CamelCase" check, and that might explain why aA comes before aa. I think when comparing that case we're following the ascii order

[calebcartwright]

Acknowledge seeing this and share the initial reaction of puzzlement. Obviously any changes here, bug fix or otherwise, can have a wide blast radius of formatting changes, so we'll need to be extremely thorough and thoughtful.

The corresponding code hasn't been touched in a long time, so I'd also suggest going back through the original style guide issue to see if perhaps there were any discussion of relevant behavior that perhaps never made its way into the final codified result.

rust-lang/style-team#24

Though somewhat tangential, #5075 and rust-lang/style-team#143 may also be of interest if the door is being reopened

[digama0]

It looks like #1785 was the PR that introduced this change.

[joshtriplett]

@calebcartwright I do understand that rustfmt has to be cautious about introducing changes that will cause churn. If rustfmt were sorting in a plausible order that just disagreed with the style guide, I would absolutely suggest we keep that until an edition boundary or similar, to avoid churn. However, in this case, it seems like this is producing an unpredictable order that people can't easily replicate, and I think this may be close enough to a bugfix to be worth considering.

(That's separate from any future changes to do version-sorting or similar, which I'd love to see but which does seem like 2.0 material.)

This won't arise in every import list, and in the ones where it does arise, I think the inconsistency and inability for a human to produce the same order as rustfmt before running rustfmt provide a sufficiently compelling motivation for this change.

That said, I also acknowledge that any such change will incur a cost, even if we think that cost is worthwhile. And whether or not this can be fixed in rustfmt 1, I'd still like to see it fixed in the next generation.

[calebcartwright]

@joshtriplett - to be clear, I have not said nor am I implying that we do nothing. It deserves consideration and careful inspection, both to determine/confirm there's divergence from prescribed behavior and if so then when/how a fix/change would be rolled out.

I am stressing the need for caution and thoroughness, however, as there's been more than a few occasions where something seemed like an obvious bug at first blush but which later turned out to not be the case.

I realize that if there were anyone that would know/remember the specifics it would be folks like yourself and Nick, but on our end we do still need to go back through relevant discussions to confirm, especially given the age and thoroughness of those threads.

[calebcartwright]

I'm marking this as a p-high, as I'd really like to get imports_granularity stabilized, with at least a few of the variants stabilized (IIRC one or two may not be ready due to bugs/relative nascency).

@yaahc - this could potentially be a pretty gnarly one, but also potentially a decent one if you wanted to hack on the rustfmt codebase a little.

Subsequent to some of my prior comments, @ytmimi has developed some really sweet automation that we can use to evaluate changes for idempotency across multiple codebases (kinda like our own mini formatting crater run) that helps reduce the review burden of having to mentally conjure potential formatting impacts

[tgross35]

Is this issue as simple as redoing the section @ytmimi linked to not check for cases and instead do ascii sorting? Or are there further decisions to make here, with impact being the biggest issue? If impact is an issue, could sorting just become style edition dependent? I am assuming that would be fairly easy too if edition is stored in an atomic somewhere.

Btw @joshtriplett your style guide link in the original post is dead

[ytmimi]

@tgross35 UseSegment was updated a while ago to store the version.

rustfmt/src/imports.rs

Lines 104 to 108 in 16db2a4

	#[derive(Clone, Eq, PartialEq)]
	pub(crate) struct UseSegment {
	pub(crate) kind: UseSegmentKind,
	pub(crate) version: Version,
	}

That should make it easier to change the Ord impl for Version::Two and get a version gated fix out for this.

[trevyn]

TLDR: The ALL_CAPS vs CamelCase vs snake_case sorting came about in order to separate constants from types in list imports (e.g. use self::libc::{access, c_char, c_int, W_OK};). Is it incorrectly getting applied to groups of imports separated by whitespace? Also it appears this sort method got general consensus, but didn't end up in the style guide.

Btw @joshtriplett your style guide link in the original post is dead

Updated style guide link: https://github.com/rust-lang/rust/blob/master/src/doc/style-guide/src/items.md#ordering-of-imports

Timeline of rust-lang/style-team#24 as it pertains:

Dec 16, 2016:

• ssokolow expresses desire for "all-caps things like simple integer constants" in list imports to be at the end of the sort order, e.g. use self::libc::{access, c_char, c_int, W_OK};, support is expressed for the general idea of constants appearing together.

Mar 28, 2017:

• alobb summarizes as either "Types and functions should appear ahead of constants within a use statement" or "either types and functions appear first, or constants appear first". (The edits are unfortunately lost to GitHub.)
• nrc says regarding types/functions/constants "I'm having second thoughts about this. I think this is hard to implement - we could only rely on convention in order to enforce it. Alphabetical sorting would get close to this and I think is good enough."
• joshtriplett thinks separating constants vs others seems promising, and doesn't mind doing it by convention, noting that ASCIIbetical sorts types and constants together, e.g. use foo::{BAZ_QUUX, BazQuuz, FOO_BAR, FooBar, baz_quux, foo_bar};

Mar 29, 2017:

• nrc makes first mention of grouping by ALL_CAPS vs CamelCase vs snake_case, which gets general support.

May 9, 2017:

• nrc summarizes consensus as "Within each import, we sort in groups: snake_case, CamelCase, SCREAMING_SNAKE_CASE, within each group, sort alphabetically"

July 12, 2017:

• topecongiro opens PR for implementation in rustfmt; merged two days later.

July 13, 2017:

• joshtriplett writes:

Sort names imported from a module into the following groups in order, if present; within groups, sort alphabetically:

* `self`

* `CamelCase` names (e.g. types)

* `snake_case` names (e.g. functions, modules)

* `ALL_CAPS` (e.g. constants)

Apr 14, 2018:

• nrc summarizes thread, but without mention of camel/snake case. This appears to be the source of what ended up in the style guide.