Open jannic opened 2 years ago
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.
In the mean time I also saw https://github.com/korken89/fugit/issues/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 https://github.com/rp-rs/rp-hal/pull/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?
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 https://github.com/rp-rs/rp-hal/pull/439 changed the interface I used fromu64
toTimerInstantU64
.
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 byOrd
, and have a separatewrapping_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.
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.
This could be a valid approach to implement Ord
correctly but still provide the wrapping-aware comparison:
https://github.com/jannic-dev-forks/fugit/commit/a4c78d3e7d8274ffcec4717c8993ad67287778b6
Another option could be to hide the Ord
/PartialOrd
implementations behind a feature flag:
https://github.com/jannic-dev-forks/fugit/commit/9662eab4ea6edab182adb249bf49a6963156511f
That would be a breaking change, so perhaps it should only be announced in the docs and then implemented in the next major version?
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.
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.)
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.
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?
Unfortunately not in stable Rust.
The implementation
impl<const NOM: u32, const DENOM: u32> Ord for Instant<u64, NOM, DENOM>
(and same withu32
) doesn't comply with the specified requirements for implementations ofOrd
.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 neitherPartialOrd
).I noticed this when trying to find the minimum in a list of Instants, and getting inconsistent results.