Instant::cmp doesnt comply with Ord requirements

[jannic]

The implementation impl<const NOM: u32, const DENOM: u32> Ord for Instant<u64, NOM, DENOM> (and same with u32) doesn't comply with the specified requirements for implementations of Ord.

Ord requires the comparison to be transitive, ie. a < b and b < c implies a < c. (see https://doc.rust-lang.org/std/cmp/trait.Ord.html#corollaries)

However the current implementation tries to handle wrap-around of the underlying ticks counter:
https://github.com/korken89/fugit/blob/master/src/instant.rs#L55-L70. That breaks the mentioned requirement.

So either the implementation should be changed, or Instant should not implement Ord (and neither PartialOrd).

I noticed this when trying to find the minimum in a list of Instants, and getting inconsistent results.

[korken89]

Hi, thanks for reporting.

While it does try to handle wrap-arounds Ord/ParitalOrd is only valid as long as the times were acquired within 2^(N_BITS-1)-1 ticks as a maximum span.
This does also hold for the majority of operations on Instant.

The recommendation I can give is to use a storage type that makes the Instant monotonic in practice. Usually this means using u64 storage as wrap around happens after like 1 000 years.

I think this implicit requirement in fugit should be better documented somewhere.

[jannic]

In the mean time I also saw #35. Which happens to be similar to what hapend to me. I used u64::MAX as a placeholder for 'no alarm scheduled' end expected it to be larger than any real time stamp. Which happened perfectly well until rp-rs/rp-hal#439 changed the interface I used from u64 to TimerInstantU64.

I understand the intention of the wrapping behavior. However this still breaks the contract of Ord. Which in turn can break data structures and algorithms which rely on that contract.

So I think it's just not possible to both support the wrapping behavior of cmp and claim to implement Ord/PartialOrd.

From a practical point of view: If the underlying datatype is large enough that wraparounds don't happen, the wrapping behavior in cmp is not necessary. And if wraparounds do happen, it's wrong for half of the possible time stamps.

What about implementing cmp as required by Ord, and have a separate wrapping_cmp in case some application really wants it?

[korken89]

The wrapping behavior is the same as with e.g. an i32, so I don't quite see what the issue is.
If you overflow the type it is considered as undefined behavior - the same as overflowing an i32.
I.e. there is a maximum span that is valid, if you perform operations on a larger span than this, you are outside what fugit is designed for.

I used u64::MAX as a placeholder for 'no alarm scheduled' end expected it to be larger than any real time stamp. Which happened perfectly well until rp-rs/rp-hal#439 changed the interface I used from u64 to TimerInstantU64.

Makes sense, fugit and their internal representation has different contracts - so the same constants can mean different things.

From a practical point of view: If the underlying datatype is large enough that wraparounds don't happen, the wrapping behavior in cmp is not necessary. And if wraparounds do happen, it's wrong for half of the possible time stamps.

This is true, however I have not found a way to do this without traits, e.g. a PracticallyInfinite trait that says a type will not overflow for the duration of the program.

What about implementing cmp as required by Ord, and have a separate wrapping_cmp in case some application really wants it?

I'm not sure how this would be done in practice.
We don't know how the storage size and tick rate comes together to make this distinction possible.

[jannic]

Is it really the same situation as i32? (BTW, i32 overflow is not undefined behavior in rust, in contrast to C/C++. But that's just a side note and not relevant for this ticket.)

For i32, an overflow is an error (which might or might not cause a panic).
For a fugit Instant, overflow seems to be allowed (which is fine - different contracts, as you wrote). I don't want to change that.

So TimerInstantU64 is closer to Wrapping<u64> than to u64, and is internally using .wrapping_add(_) and similar to do arithmetics. And notably, Wrapping<u64> does not try to be clever about cmp(), so Wrapping(u64::MAX) + Wrapping(1) < Wrapping(u64::MAX) is true.

[jannic]

This could be a valid approach to implement Ord correctly but still provide the wrapping-aware comparison:
jannic-dev-forks@a4c78d3

[jannic]

Another option could be to hide the Ord/PartialOrd implementations behind a feature flag:
jannic-dev-forks@9662eab

That would be a breaking change, so perhaps it should only be announced in the docs and then implemented in the next major version?

[korken89]

Yeah it's not straight forward on how to solve this. I merged your comment update as the first thing.

The thing is, as I see it (and designed it) is that a < b < c holds for all valid uses of Instant.
While it is possible to break it, this only happens if you use Instant outside its design.
And to me, this is the same as UB for Instant while not technically UB as in the Rust definition.
I think we see things differently here, however this is a core feature for the ease of use and ergonomic API.

Hence I'm not that keen on changing, or hiding, this part of the API.
What I would rather have is a way to detect "overflow" and panic as i32 does, however how to do this is not clear to me.

[jannic]

To stretch the analogy of UB a little bit: The way Rust contains UB and tries to make sure that no UB can pop up in an unexpected situation is the construct of unsafe code. So if using Instant outside its design was really UB, either the creation of an Instant, or calling fn cmp would need to be marked as unsafe. Probably with a safety comment like "If you create multiple instances of Instant, you must make sure that you never use two of them together, unless they are not more than u32::MAX/2 ticks apart."

Fortunately, this is not really UB, there won't be any flying demons, but just some random bug where a comparison computes an unexpected result.

Unfortunately, I don't see a good way to prevent such bugs, short of the two suggested changes: Either modifying the behavior of cmp, or not implementing Ord. Because even a very careful programmer won't read the documentation of standard trait methods for all types involved. From the buggy code let next_event = collection_of_instants.iter().min() to the documentation on fugit::Instant::cmp there are just too many layers of indirection.

(That's why I suggested to hide it behind a feature flag: Chances are, before adding a feature flag, a careful programmer would check the documentation of that flag for its meaning. Though I must admit that this isn't a silver bullet either, as the flag may have been activated by some other crate, so the developer may not even notice that it is set.)

[korken89]

What I think is that Ord and the likes should only be implemented if some marker trait that defines the Instant to be practically monotonic.
Not sure how ergonomics would be for that though, as seemingly valid code would fail compiling with Ord/PartialOrd not implemented.

Also maybe only implementing PartialOrd is a solution.

[jannic]

That marker trait sounds like a good idea.

However, deciding that automatically depending on T, NOM and DENOM needs #![feature(generic_const_exprs)], right? Or do you have an idea how such a marker trait could be realized with current stable rust?

[korken89]

Unfortunately not in stable Rust.