Sort `StorePath` by name except where necessary for legacy hashing

[roberth]

Is your feature request related to a problem? Please describe.

The default sort order (<=>) of StorePath is by base name, i.e. lexicographic starting with the hash.
This has the unfortunate effect that in some instances, Nix's behavior is more arbitrary than it should be.

As a simple example, we might have a function that throws an error when it first encounters a problem in a set of store paths.
When the user changes their expressions to hopefully resolve the problem, some hashes change, causing the order in which set presents them to the function to change, causing a different derivation with a different name to occur in the error message.

It would seem reasonable to assume that when the error message changes, the user made progress on their problem, but this was not the case. Any behavior derived from hash value comparisons is potentially very surprising, so we should strive to be as deterministic as possible, from a user perspective; not just bits and bytes.

Describe the solution you'd like

Either

• structure the code so that StorePaths are not comparable and explicit choices must be made everywhere
  • custom, restricted StorePathSet, StorePathMap types
• or identify where the legacy base name ordering matters for derivation- or output hashing stability, and change the default comparison to be (name, hash)-lexicographic

The latter can be perceived as a small change, but is a tech debt, because it won't always be obvious that a choice must be made, and the default may not be right. We should try to take advantage of code structure to prevent such mistakes.

Describe alternatives you've considered

$$\varnothing$$

Additional context

Reject the Axiom of Choice

Priorities

Add 👍 to issues you find important.