Panic user-provided comparison function does not correctly implement a total order in oxc_linter::rules::eslint::sort_keys::alphanumeric_sort

[qarmin]

File content(at the bottom should be attached raw, not formatted file - github removes some non-printable characters, so copying from here may not work):

s={C:{"":0,"":.3,"8":1,"":.1,"4":0,"8":0,"":3,"":0,"":2,"1":0.,"15":0,"":2,"":.7,"1":.02,"1":0,"2":8,"O3":4,"2":4,"":2,"1":.7,_}}

command

timeout -v 100 oxlint -D all -D nursery --import-plugin --jsdoc-plugin --jest-plugin --vitest-plugin --jsx-a11y-plugin --nextjs-plugin --react-perf-plugin TEST___FILE.js --fix

App was compiled with nightly rust compiler to be able to use address sanitizer
On Ubuntu 24.04, the commands to compile were:

rustup default nightly
rustup component add rust-src --toolchain nightly-x86_64-unknown-linux-gnu
rustup component add llvm-tools-preview --toolchain nightly-x86_64-unknown-linux-gnu

export RUST_BACKTRACE=1
export ASAN_SYMBOLIZER_PATH=$(which llvm-symbolizer-18)
export ASAN_OPTIONS=symbolize=1
RUSTFLAGS="-Zsanitizer=address" cargo +nightly build --target x86_64-unknown-linux-gnu

cause this

thread '<unnamed>' panicked at core/src/slice/sort/shared/smallsort.rs:860:5:
user-provided comparison function does not correctly implement a total order
stack backtrace:
   0:     0x587b788f32ca - <std::sys::backtrace::BacktraceLock::print::DisplayBacktrace as core::fmt::Display>::fmt::h85a9257eb6c41e04
   1:     0x587b7891a08b - core::fmt::write::hcc8bee8d21353e39
   2:     0x587b788ef803 - std::io::Write::write_fmt::h70ac935b0c89b059
   3:     0x587b788f3112 - std::sys::backtrace::BacktraceLock::print::hd262bc6f83870824
   4:     0x587b788f4517 - std::panicking::default_hook::{{closure}}::h1ac01a4d50ceb64f
   5:     0x587b788f4346 - std::panicking::default_hook::h7c4ba54603c1d0b3
   6:     0x587b788f4b57 - std::panicking::rust_panic_with_hook::h0dd05eda4407feb9
   7:     0x587b788f49c3 - std::panicking::begin_panic_handler::{{closure}}::hff4951198a9049be
   8:     0x587b788f37a9 - std::sys::backtrace::__rust_end_short_backtrace::hae232f20e82e2c44
   9:     0x587b788f4684 - rust_begin_unwind
  10:     0x587b78917983 - core::panicking::panic_fmt::h6dddd3310fdcb8b7
  11:     0x587b7891c33b - core::slice::sort::shared::smallsort::panic_on_ord_violation::h060c6011fe214cfb
  12:     0x587b780f4c3b - core::slice::sort::shared::smallsort::bidirectional_merge::h2b038163c69d2381
  13:     0x587b780f9cee - core::slice::sort::shared::smallsort::small_sort_general_with_scratch::h2a46be74a5a0e1c5
  14:     0x587b780e4a15 - core::slice::sort::stable::quicksort::quicksort::h1361fa861a65525c
  15:     0x587b77f9a483 - core::slice::sort::stable::drift::create_run::h2a1a764ccee2193f
  16:     0x587b77f9ec2e - core::slice::sort::stable::drift::sort::h2ba9bad200e9d7f0
  17:     0x587b77f212ca - core::slice::sort::stable::driftsort_main::he9cd0a1bc197c09c
  18:     0x587b77f86831 - alloc::slice::stable_sort::hda1171882354f3f3
  19:     0x587b7810a6b2 - alloc::slice::<impl [T]>::sort_by::hdb25a9c6ccd69e2c
  20:     0x587b77f637c7 - oxc_linter::rules::eslint::sort_keys::alphanumeric_sort::h3f87f1baed2ce4f7
  21:     0x587b77f62c6d - <oxc_linter::rules::eslint::sort_keys::SortKeys as oxc_linter::rule::Rule>::run::h4461e91d87584fb7
  22:     0x587b77f468ef - oxc_linter::rules::RuleEnum::run::h7ff7c2084f02dcd2
  23:     0x587b780eb178 - oxc_linter::Linter::run::h316d2cac4b8a78a0
  24:     0x587b781046b0 - oxc_linter::service::Runtime::process_source::hafa2b3b18d281940
  25:     0x587b78102b1f - oxc_linter::service::Runtime::process_path::ha0a905b52c104219
  26:     0x587b7821f423 - oxc_linter::service::LintService::run::{{closure}}::hb51bd463b38d60ba
  27:     0x587b78147444 - <rayon::iter::map_with::MapWithFolder<C,U,F> as rayon::iter::plumbing::Folder<T>>::consume::h70934fc7879b95f0
  28:     0x587b77fec9c3 - <&rayon::iter::par_bridge::IterParallelProducer<Iter> as rayon::iter::plumbing::UnindexedProducer>::fold_with::h3cf1a26d1757c113
  29:     0x587b7803d9fd - rayon::iter::plumbing::bridge_unindexed_producer_consumer::he3d5d5a628f86761
  30:     0x587b7803dd84 - rayon::iter::plumbing::bridge_unindexed_producer_consumer::{{closure}}::h849a15ac2c7506c9
  31:     0x587b77f13720 - rayon_core::join::join_context::call_a::{{closure}}::h32df242b2eba1522
  32:     0x587b7818bbd1 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h6cf95dd870fb75c6
  33:     0x587b77e87dd1 - std::panicking::try::do_call::h9b310f26d502a4aa
  34:     0x587b78110abb - __rust_try
  35:     0x587b7810e9b2 - std::panic::catch_unwind::h09d79795d67119b7
  36:     0x587b780d3fd9 - rayon_core::unwind::halt_unwinding::hb3f3b8d317262a15
  37:     0x587b77f13293 - rayon_core::join::join_context::{{closure}}::hcc0c9123d5632910
  38:     0x587b781b3b8d - rayon_core::registry::in_worker::h9033a5ec2711cf85
  39:     0x587b77f12a19 - rayon_core::join::join_context::h3d922ebe58efb817
  40:     0x587b7803dbab - rayon::iter::plumbing::bridge_unindexed_producer_consumer::he3d5d5a628f86761
  41:     0x587b7803dd84 - rayon::iter::plumbing::bridge_unindexed_producer_consumer::{{closure}}::h849a15ac2c7506c9
  42:     0x587b77f13720 - rayon_core::join::join_context::call_a::{{closure}}::h32df242b2eba1522
  43:     0x587b7818bbd1 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h6cf95dd870fb75c6
  44:     0x587b77e87dd1 - std::panicking::try::do_call::h9b310f26d502a4aa
  45:     0x587b78110abb - __rust_try
  46:     0x587b7810e9b2 - std::panic::catch_unwind::h09d79795d67119b7
  47:     0x587b780d3fd9 - rayon_core::unwind::halt_unwinding::hb3f3b8d317262a15
  48:     0x587b77f13293 - rayon_core::join::join_context::{{closure}}::hcc0c9123d5632910
  49:     0x587b781b3b8d - rayon_core::registry::in_worker::h9033a5ec2711cf85
  50:     0x587b77f12a19 - rayon_core::join::join_context::h3d922ebe58efb817
  51:     0x587b7803dbab - rayon::iter::plumbing::bridge_unindexed_producer_consumer::he3d5d5a628f86761
  52:     0x587b7803dd84 - rayon::iter::plumbing::bridge_unindexed_producer_consumer::{{closure}}::h849a15ac2c7506c9
  53:     0x587b77f13720 - rayon_core::join::join_context::call_a::{{closure}}::h32df242b2eba1522
  54:     0x587b7818bbd1 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h6cf95dd870fb75c6
  55:     0x587b77e87dd1 - std::panicking::try::do_call::h9b310f26d502a4aa
  56:     0x587b78110abb - __rust_try
  57:     0x587b7810e9b2 - std::panic::catch_unwind::h09d79795d67119b7
  58:     0x587b780d3fd9 - rayon_core::unwind::halt_unwinding::hb3f3b8d317262a15
  59:     0x587b77f13293 - rayon_core::join::join_context::{{closure}}::hcc0c9123d5632910
  60:     0x587b781b3b8d - rayon_core::registry::in_worker::h9033a5ec2711cf85
  61:     0x587b77f12a19 - rayon_core::join::join_context::h3d922ebe58efb817
  62:     0x587b7803dbab - rayon::iter::plumbing::bridge_unindexed_producer_consumer::he3d5d5a628f86761
  63:     0x587b7803df94 - rayon::iter::plumbing::bridge_unindexed_producer_consumer::{{closure}}::ha9c5cc7a25604bb6
  64:     0x587b77f13892 - rayon_core::join::join_context::call_b::{{closure}}::h331723d9abc4b235
  65:     0x587b780d32b2 - rayon_core::job::JobResult<T>::call::{{closure}}::hf1fdea948ef2318f
  66:     0x587b7818bc01 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h7a655f1d518a1f32
  67:     0x587b77e87d9d - std::panicking::try::do_call::h6ec17200adea48c0
  68:     0x587b78110abb - __rust_try
  69:     0x587b7810eb52 - std::panic::catch_unwind::h8a48b3fe654a5daa
  70:     0x587b780d3ec9 - rayon_core::unwind::halt_unwinding::h9694ec7608d4fdca
  71:     0x587b780d2e87 - rayon_core::job::JobResult<T>::call::h284059af37d659d2
  72:     0x587b780d4181 - <rayon_core::job::StackJob<L,F,R> as rayon_core::job::Job>::execute::h4b3d68c36158ea0b
  73:     0x587b7828bfde - rayon_core::job::JobRef::execute::he8814c953b8ef2e5
  74:     0x587b78286113 - rayon_core::registry::WorkerThread::execute::h9bd6bdd9df687901
  75:     0x587b78285eb2 - rayon_core::registry::WorkerThread::wait_until_cold::he55fc49795f17153
  76:     0x587b78285c8a - rayon_core::registry::WorkerThread::wait_until::ha830c3a1b302886f
  77:     0x587b78285ff7 - rayon_core::registry::WorkerThread::wait_until_out_of_work::hf9b06014095b1b53
  78:     0x587b78286487 - rayon_core::registry::main_loop::h28f9b822b209ee0e
  79:     0x587b78282f46 - rayon_core::registry::ThreadBuilder::run::h95c5f07919e2a61a
  80:     0x587b782833ad - <rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{{closure}}::haa06075482346afe
  81:     0x587b7828f5b6 - std::sys::backtrace::__rust_begin_short_backtrace::hd252c1efeb16b771
  82:     0x587b78289fed - std::thread::Builder::spawn_unchecked_::{{closure}}::{{closure}}::h8d556585203b3637
  83:     0x587b7828a931 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::he57ec76c4901018e
  84:     0x587b7828f5ed - std::panicking::try::do_call::h82b23803b6ee7c95
  85:     0x587b7828a7eb - __rust_try
  86:     0x587b78289baa - std::thread::Builder::spawn_unchecked_::{{closure}}::h2bf1dc186fa3aeb7
  87:     0x587b78291bd7 - core::ops::function::FnOnce::call_once{{vtable.shim}}::h512281276390ab0d
  88:     0x587b788f756b - std::sys::pal::unix::thread::Thread::new::thread_start::hdd18e2f9323a466b
  89:     0x7beed6a9ca94 - start_thread
                               at ./nptl/pthread_create.c:447:8
  90:     0x7beed6b29c3c - clone3
                               at ./misc/../sysdeps/unix/sysv/linux/x86_64/clone3.S:78
  91:                0x0 - <unknown>
Rayon: detected unexpected panic; aborting
timeout: the monitored command dumped core
Aborted

compressed.zip

[Boshen]

Crashed in oxc_linter::rules::eslint::sort_keys::alphanumeric_sort

cc @Goldziher

[qarmin]

Here is code that helps to find broken items

use rand::Rng;
use std::cmp::Ordering;

fn alphanumeric_cmp(a: &str, b: &str) -> Ordering {
    /* regex key special case */
    if a.starts_with('/') && a.ends_with('/') {
        if b.starts_with('/') && b.ends_with('/') {
            return a.cmp(b);
        }
        return Ordering::Greater;
    }

    if b.starts_with('/') && b.ends_with('/') {
        return Ordering::Less;
    }

    /* empty keys special case */
    if a.is_empty() && b.starts_with('[') || b.is_empty() && a.starts_with('[') {
        return Ordering::Equal;
    }

    let len = a.len().min(b.len());

    for (a_char, b_char) in a.chars().take(len).zip(b.chars().take(len)) {
        if a_char == b_char {
            continue;
        }
        /* JS sorting apparently places _ after uppercase alphanumerics and before lowercase ones */
        if a_char.is_uppercase() && b_char == '_' {
            return Ordering::Less;
        }

        if a_char == '_' && b_char.is_uppercase() {
            return Ordering::Greater;
        }

        /* computed properties should come before alpha numeric chars */
        if a_char == '[' && b_char.is_alphanumeric() {
            return Ordering::Less;
        }

        if a_char.is_alphanumeric() && b_char == '[' {
            return Ordering::Greater;
        }

        if a_char.is_alphanumeric() && !b_char.is_alphanumeric() {
            return Ordering::Greater;
        }

        if !a_char.is_alphanumeric() && b_char.is_alphanumeric() {
            return Ordering::Less;
        }

        return a_char.cmp(&b_char);
    }

    a.cmp(b)
}

fn detect_inconsistency(a: &str, b: &str, c: &str) -> bool {
    let ab = alphanumeric_cmp(a, b);
    let bc = alphanumeric_cmp(b, c);
    let ac = alphanumeric_cmp(a, c);

    if ab == Ordering::Less && bc == Ordering::Less && ac == Ordering::Greater {
        return true;
    }

    if ab == Ordering::Greater && bc == Ordering::Greater && ac == Ordering::Less {
        return true;
    }

    false
}

fn random_ascii_string(len: usize) -> String {
    let mut rng = rand::thread_rng();
    (0..len)
        .map(|_| rng.gen_range(b'!'..=b'~') as char)
        .collect()
}

fn main() {
    loop {
        let a = random_ascii_string(2);
        let b = random_ascii_string(2);
        let c = random_ascii_string(2);

        if detect_inconsistency(&a, &b, &c) {
            panic!("Found inconsistency: {} < {}, {} < {}, but {} > {}", a, b, b, c, a, c);
        }
    }
}

Found inconsistency: _M < 2D, 2D < J_, but _M > J_

[daflyinbed]

I guess is relate to rust 1.81.0?

The new sort implementations may panic if a type’s implementation of Ord (or the given comparison function) does not implement a total order as the trait requires. Ord’s supertraits (PartialOrd, Eq, and PartialEq) must also be consistent. The previous implementations would not “notice” any problem, but the new implementations have a good chance of detecting inconsistencies, throwing a panic rather than returning knowingly unsorted data.

[Goldziher]

Hi, i can look into this in a couple of days. I'm not sure whats the issue though, could anyone explain?

[Boshen]

Hi, i can look into this in a couple of days. I'm not sure whats the issue though, could anyone explain?

Rust v1.81.0 changed the sort algorithm, which panics on incorrect sorter.

https://blog.rust-lang.org/2024/09/05/Rust-1.81.0.html#new-sort-implementations