Clarify the meaning of `ArbitraryOrd`

[Kixunil]

It is unclear whether the ordering of ArbitraryOrd should stay stable across executions (or minor version upgrades) or not. A good example of where this question is relevant is secp256k1::PublicKey. We could implement ArbitraryOrd on it to do the same thing as Ord, for convenience or we could also implement ArbitraryOrd that does NOT serialize the keys and instead compares the internal bytes. However if the internal representation changes the ordering will change, so if someone sorts keys and stores them on disk then they would appear unsorted after loading them with a new version.

To solve this, I propose to define in documentation that ArbitraryOrd does not guarantee stable ordering across executions and it's meant only to allow storing things in trees. People storing them need to define their ordering explicitly.

We could in addition provide this:

/// A trait providing ordering that is guaranteed to be preserved across executions.
///
/// As opposed to `ArbitraryOrd`, this trait also promises to keep the ordering the same across executions.
/// In other words, the function must be pure and changing the ordering is considered a breaking change.
/// **Important:** The consumers requiring stable ordering **must** call the method on this trait and **must not** rely on implementations of `ArbitraryOrd` and `StableArbitraryOrd` being the same.
///
/// By default this calls into `ArbitraryOrd` so if your implementation of `ArbitraryOrd` already has a defined stable ordering you can just implement this as if it was a marker trait.
/// However, in some cases computing an arbitrary ordering can be faster than computing a stable ordering. Types with this property should override this and offer different algorithms.
pub trait StableArbitraryOrd<Rhs = Self>: ArbitraryOrd<Rhs> {
    fn stable_arbitrary_cmp(&self, other: &Rhs) -> core::cmp::Ordering {
        self.arbitrary_cmp(other)
    }
}

// derives here
pub struct StableOrdered<T>(pub T);

// impl Ord for StableOrdered<T> by calling into stable_arbitrary_cmp

However this is not needed for 1.0 and I think that since the main objective of this in the first place was to store things in trees we should not do the reverse (define it as stable and provide unstable trait - that way also has issues with specializing the method). But maybe ordering is significant enough in miniscript to warrant stable ordering @apoelstra please LMK if it is so.

[apoelstra]

I don't think we use this in Miniscript. In Miniscript we sort our objects lexicographically by serialization and have manual Ord impls that use this.

AFAIK this crate isn't actually used anywhere. We might use the trait on the rust-bitcoin locktime. But I'm really not sure what benefit it brings over just defining an inherent arbitrary_cmp method or even just telling users to call locktime.to_consensus_u32().cmp() so I would advise that we stop using it before 1.0.

Anyway, agreed that we shouldn't commit to any guarantees about stability before 1.0.

[Kixunil]

we shouldn't commit to any guarantees about stability before 1.0.

Note that it's not just about us, it'll become a contract for everyone implementing or consuming the trait, making any change breaking. But I think a hierarchy of traits is better because both interpretations are equally valid but one seems more needed in practice, so should be prioritized.