Panics with Rust 1.81.0

[ctron]

Starting with Rust 1.81.0 we see the following issues in trunk:

thread 'notify-rs debouncer loop' panicked at library/core/src/slice/sort/shared/smallsort.rs:862:5:
user-provided comparison function does not correctly implement a total order
stack backtrace:
   0: rust_begin_unwind
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/std/src/panicking.rs:665:5
   1: core::panicking::panic_fmt
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/panicking.rs:74:14
   2: core::slice::sort::shared::smallsort::panic_on_ord_violation
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/shared/smallsort.rs:862:5
   3: core::slice::sort::shared::smallsort::bidirectional_merge
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/shared/smallsort.rs:841:13
   4: core::slice::sort::shared::smallsort::small_sort_general_with_scratch
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/shared/smallsort.rs:289:9
   5: <T as core::slice::sort::shared::smallsort::StableSmallSortTypeImpl>::small_sort
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/shared/smallsort.rs:64:9
   6: core::slice::sort::stable::quicksort::quicksort
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/stable/quicksort.rs:27:13
   7: core::slice::sort::stable::drift::create_run
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/stable/drift.rs:257:9
   8: core::slice::sort::stable::drift::sort
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/stable/drift.rs:66:17
   9: core::slice::sort::stable::driftsort_main
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/stable/mod.rs:86:5
  10: core::slice::sort::stable::sort
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/core/src/slice/sort/stable/mod.rs:47:5
  11: alloc::slice::stable_sort
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/alloc/src/slice.rs:883:5
  12: alloc::slice::<impl [T]>::sort_by
             at /rustc/eeb90cda1969383f56a2637cbd3037bdf598841c/library/alloc/src/slice.rs:289:9
  13: notify_debouncer_full::DebounceDataInner<T>::debounced_events
             at /home/jreimann/.cargo/registry/src/index.crates.io-6f17d22bba15001f/notify-debouncer-full-0.3.1/src/lib.rs:253:9
  14: notify_debouncer_full::new_debouncer_opt::{{closure}}
             at /home/jreimann/.cargo/registry/src/index.crates.io-6f17d22bba15001f/notify-debouncer-full-0.3.1/src/lib.rs:603:29

So my understanding, that's an issue with the comparator provided:

        // order events for different files chronologically, but keep the order of events for the same file
        events_expired.sort_by(|event_a, event_b| {
            // use the last path because rename events are emitted for the target path
            if event_a.paths.last() == event_b.paths.last() {
                std::cmp::Ordering::Equal
            } else {
                event_a.time.cmp(&event_b.time)
            }
        });

[mo8it]

Transitivity is violated here. It requires that a <= b AND b <= c -> a <= c.

Assume the events a, b and c with the fields l for the last path and t for the time:

	l	t
a	1	3
b	1	1
c	3	2

I am using numbers for the fields as a placeholder for something that implements total order.

The closure defines the order like this: x <= y <-> x.l = y.l OR x.t <= y.t

In our example, a <= b is true because a.l = b.l (1 = 1). b <= c is also true because b.t <= c.t (1 <= 2). But a <= c is false since a.l != c.l (1 != 3) and a.t > c.t (3 > 2).

[0xpr03]

cc @dfaust

[maratik123]

I've made PoC with correct sorting to fix this issue

https://gist.github.com/maratik123/30e53d21dc13644b77aee4c92a64c375#file-main-rs-L23-L52

[dfaust]

Thanks everybody. I wasn't able to reproduce the panic, but the new sort logic of #638 should fix the issue and it's also stable now.

@maratik123: Thank you for your work, but your solution doesn't quite implement the intended logic. Have a look at my PR if you are interested, I hope it's understandable. If not, let me know.

@0xpr03: Can we do a patch release for notify-debouncer-full?

[ctron]

Thanks for solving this issue. Is that released already? If not, could you do a quick release?

[0xpr03]

I've had a suspicion which turned out to be true: We haven't yet release notify-debouncer-full 0.4.0. Currently going through all MRs and writing up the changelog.

[dfaust]

I've had a suspicion which turned out to be true: We haven't yet release notify-debouncer-full 0.4.0.

@0xpr03:

That's why we should probably make a patch release for notify-debouncer-full.

But apart from that I think we can also make a new release of the main branch. I would like to merge #630 first, though.