Spurious "found two different crates with name `alloc`" errors in PR builder

[Centril]

• Fix inconsistent link formatting. #64378 (comment)
• Fix failure note to_str implementation #64429 (comment)

[Mark-Simulacrum]

Some relatively unscientific digging for where we create SVHs dug up this bit of code -- that sort_unstable looks rather suspicious, as it's presumably possible for two crates with different hashes to end up in a different order, and then when we go on to hash it it'll lead to problems down the line if the sort resulted in a different ordering then we'd expect.

To be clear, thinking some more about this, I think it's presumably fine for this to be an unstable sort since an unstable sort should still have stable output, it just might be different than input order, AIUI -- what's not fine is that we're introducing non-determinism by not sorting by hash.

cc @michaelwoerister who I believe is the original author of this bit of code in 8129c53

cc @Zoxc @aturon -- this is a potentially interesting case for wg-parallel-rustc to examine, as it's a case where we need to be careful about ordering in a subtle way -- the output of a query is assumed to be ordering-stable across compilations, otherwise this svh computation won't work well I believe, though not certain

[Mark-Simulacrum]

Another note is that this is likely to prove rather hard to track down as to what caused this as we've seen relatively few of these errors - the PR description lists one case, and anecdotal data suggests maybe around 6 or so errors that we've noted like this. Interestingly, all were specifically in these liballoc doctests which explicitly have an extern crate alloc;; maybe that points to the bug (Cc @petrochenkov, in case this is somehow resolver related). I suspect that means we have something like two extern crate allocs in these tests due to rustdoc auto-insertion, but haven't verified.

I personally suspect this is sort of due to #63470 which likely causes us to keep around more artifacts than previously and perhaps one of those is contaminating the path whereas it didn't before; to be clear, this exposed the bug perhaps but almost certainly didn't cause it.

[ehuss]

Has this happened before #63827?

[Mark-Simulacrum]

I believe so, but not completely confident. It occurs really rarely, so it's hard to be certain unfortunately.

[michaelwoerister]

Copying my comment from discord:
The list being sorted there should never contain duplicate entries. (crate-name, crate-disambiguator) must uniquely identify a crate, otherwise there'll be logic errors all over the place.
One could add an assertion after sorting that this list does indeed not contain duplicates. If it does that points to a bug in a different place.

Cargo usually takes care of correctly setting crate disambiguators but if this occurs in a setup that is not driven by Cargo, then that might be the source of the bug. Two versions of the same crate must always be compiled with differing crate disambiguators. The disambiguators are how we implement supporting multiple versions of the same crate.

Another note: The following line should make sure that we sort lexicographically (as opposed to some kind of pointer value) here:
8129c53#diff-5c91206f29170d97620d0f4bce664722R139

If that is not the case for some reason, the sort order would indeed be undeterministic.

[Centril]

I haven't seen this reproduced for a long time so I'll close it for now.

[mati865]

There was similar error recently but with bitflags when building rustdoc: #66108

[Enselic]

Triage: Has anyone here seen this error in recent years?

[ehuss]

GitHub search shows the most recent this particular message was in #67281, 4 years ago.

The error message has since changed. I'm going to close, since I don't think this is a direct issue anymore. Here are my notes:

The error appeared when compiling alloc doctests, while loading the alloc library via extern crate alloc;.

error[E0523]: found two different crates with name `alloc` that are not distinguished by differing `-C metadata`. This will result in symbol conflicts between the two.

There was a verification step in creader.rs which would check if two crates have the same stable crate ID, but different SVH, and it would raise that error.

#100928 migrated to use the new diagnostics.

#100599 removed the particular message and replaced it with a bug!:

bug!(
    "Previously returned E0523 here. \
     See https://github.com/rust-lang/rust/pull/100599 for additional discussion.\
     root.name() = {}.",
    root.name()
);

Looks like the authors couldn't find a way to create a test for it, and thought that maybe it was an unreachable section.
However, jyn happened to run into it after bug! was added.

Shortly afterwards, the bug! and SVH check was simply removed in #109213 which refactored things to eagerly verify collisions (updated in #111461). Now, if there are two crates with the same stable crate ID, the errors are now:

• If collision with local crate:
  SymbolConflictsCurrent
  E0519 the current crate is indistinguishable from one of its dependencies: it has the same crate-name {$crate_name} and was compiled with the same -C metadata arguments. This will result in symbol conflicts between the two.
• If it knows the name of the other:
  StableCrateIdCollision
  found crates ({$crate_name0} and {$crate_name1}) with colliding StableCrateId values.
• If it doesn't know the name of the other:
  NotFound
  CannotFindCrate
  can't find crate

Searching for those error messages doesn't pull up anything recent.