Repository: immunant/c2rust (language: rust)

Issue:
`SrcLoc` sorting is non-transitive and a false total order and equality (panics in 1.81)
Seems one (or more) of the types used in the transpiler have a wrong `Ord` implementation.
```
Transpiling cr.c
thread 'main' 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:     0x620e4a93b8da - std::backtrace_rs::backtrace::libunwind::trace::h4f532649ff050af0
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/../../backtrace/src/backtrace/libunwind.rs:116:5
   1:     0x620e4a93b8da - std::backtrace_rs::backtrace::trace_unsynchronized::h2bd9c4760a46d04c
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x620e4a93b8da - std::sys::backtrace::_print_fmt::h06a2f1333d2c9eb7
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/sys/backtrace.rs:66:9
   3:     0x620e4a93b8da - <std::sys::backtrace::BacktraceLock::print::DisplayBacktrace as core::fmt::Display>::fmt::hc39aee40395be66f
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/sys/backtrace.rs:39:26
   4:     0x620e4a9628db - core::fmt::rt::Argument::fmt::h391dd44a8ecf182f
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/fmt/rt.rs:177:76
   5:     0x620e4a9628db - core::fmt::write::h718938895d6a6b80
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/fmt/mod.rs:1178:21
   6:     0x620e4a937d83 - std::io::Write::write_fmt::h97874dbf951485b0
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/io/mod.rs:1823:15
   7:     0x620e4a93b722 - std::sys::backtrace::BacktraceLock::print::h28b06058dc60edca
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/sys/backtrace.rs:42:9
   8:     0x620e4a93c9e7 - std::panicking::default_hook::{{closure}}::ha6790375217144d8
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:268:22
   9:     0x620e4a93c816 - std::panicking::default_hook::h7a0db9554a291cc0
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:295:9
  10:     0x620e4a93d027 - std::panicking::rust_panic_with_hook::h35232034e4df15db
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:801:13
  11:     0x620e4a93ce93 - std::panicking::begin_panic_handler::{{closure}}::hf188e2435ae6fe44
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:667:13
  12:     0x620e4a93bdb9 - std::sys::backtrace::__rust_end_short_backtrace::h63f9b1b738507ea6
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/sys/backtrace.rs:170:18
  13:     0x620e4a93cb54 - rust_begin_unwind
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:665:5
  14:     0x620e4a960703 - core::panicking::panic_fmt::ha3d1a45ecd949c55
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/panicking.rs:74:14
  15:     0x620e4a964d9b - core::slice::sort::shared::smallsort::panic_on_ord_violation::hbf9c589b6c9b3724
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/shared/smallsort.rs:860:5
  16:     0x620e4a4c7f9f - core::slice::sort::shared::smallsort::bidirectional_merge::h6690bf85da2564d5
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/shared/smallsort.rs:838:13
  17:     0x620e4a4c7f9f - core::slice::sort::shared::smallsort::small_sort_network::h890c54e4f75c0902
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/shared/smallsort.rs:370:9
  18:     0x620e4a428107 - <T as core::slice::sort::shared::smallsort::UnstableSmallSortFreezeTypeImpl>::small_sort::hd5067ef6cf7d40f7
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/shared/smallsort.rs:164:13
  19:     0x620e4a428107 - <T as core::slice::sort::shared::smallsort::UnstableSmallSortTypeImpl>::small_sort::h2df5d3e38e278dc7
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/shared/smallsort.rs:101:9
  20:     0x620e4a428107 - core::slice::sort::unstable::quicksort::quicksort::hea4648e1605e90a5
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/unstable/quicksort.rs:24:13
  21:     0x620e4a428db8 - core::slice::sort::unstable::quicksort::quicksort::hea4648e1605e90a5
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/unstable/quicksort.rs:71:9
  22:     0x620e4a428db8 - core::slice::sort::unstable::quicksort::quicksort::hea4648e1605e90a5
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/unstable/quicksort.rs:71:9
  23:     0x620e4a512e46 - core::slice::sort::unstable::sort::h35235f49a1d553dd
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/sort/unstable/mod.rs:43:5
  24:     0x620e4a512e46 - core::slice::<impl [T]>::sort_unstable_by::h504cc4e282cf16fc
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/mod.rs:2981:9
  25:     0x620e4a512e46 - c2rust_transpile::c_ast::TypedAstContext::sort_top_decls::hc2a55804d3bb0a25
                               at /home/kriskras99/Source/c2rust/c2rust-transpile/src/c_ast/mod.rs:674:9
  26:     0x620e4a512e46 - c2rust_transpile::translator::translate::h599712b2056933b9
                               at /home/kriskras99/Source/c2rust/c2rust-transpile/src/translator/mod.rs:513:9
  27:     0x620e4a5882a5 - c2rust_transpile::transpile_single::he88bad69628bcf0b
                               at /home/kriskras99/Source/c2rust/c2rust-transpile/src/lib.rs:536:9
  28:     0x620e4a3c2fdb - c2rust_transpile::transpile::{{closure}}::h1c26c176d2edae16
                               at /home/kriskras99/Source/c2rust/c2rust-transpile/src/lib.rs:328:17
  29:     0x620e4a3c2fdb - core::iter::adapters::map::map_fold::{{closure}}::he4bccb3109727379
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/iter/adapters/map.rs:88:28
  30:     0x620e4a3c2fdb - <core::slice::iter::Iter<T> as core::iter::traits::iterator::Iterator>::fold::hd20ded494caaffcb
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/slice/iter/macros.rs:232:27
  31:     0x620e4a3c2fdb - <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::fold::h45f09cacc691c60d
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/iter/adapters/map.rs:128:9
  32:     0x620e4a3c2fdb - core::iter::traits::iterator::Iterator::for_each::h2c40a859fa37c766
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/iter/traits/iterator.rs:813:9
  33:     0x620e4a3c2fdb - alloc::vec::Vec<T,A>::extend_trusted::hb59eb0450c1a5309
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/alloc/src/vec/mod.rs:3125:17
  34:     0x620e4a3c2fdb - <alloc::vec::Vec<T,A> as alloc::vec::spec_extend::SpecExtend<T,I>>::spec_extend::hdfb895ec3556694f
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/alloc/src/vec/spec_extend.rs:26:9
  35:     0x620e4a3c2fdb - <alloc::vec::Vec<T> as alloc::vec::spec_from_iter_nested::SpecFromIterNested<T,I>>::from_iter::ha75a8e9b8b1dfed4
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/alloc/src/vec/spec_from_iter_nested.rs:60:9
  36:     0x620e4a3c2fdb - <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter::hd503974f9b2fb62a
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/alloc/src/vec/spec_from_iter.rs:33:9
  37:     0x620e4a584ece - <alloc::vec::Vec<T> as core::iter::traits::collect::FromIterator<T>>::from_iter::hdcb5e575103de682
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/alloc/src/vec/mod.rs:2989:9
  38:     0x620e4a584ece - core::iter::traits::iterator::Iterator::collect::h748ec39779ff7b21
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/iter/traits/iterator.rs:2000:9
  39:     0x620e4a584ece - c2rust_transpile::transpile::hd0035b677d692a90
                               at /home/kriskras99/Source/c2rust/c2rust-transpile/src/lib.rs:337:14
  40:     0x620e4a35911d - c2rust_transpile::main::h74e6ff961002307d
                               at /home/kriskras99/Source/c2rust/c2rust/src/bin/c2rust-transpile.rs:259:5
  41:     0x620e4a361a33 - core::ops::function::FnOnce::call_once::h5ca91e7049f14308
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/ops/function.rs:250:5
  42:     0x620e4a361a33 - std::sys::backtrace::__rust_begin_short_backtrace::hd38ba6c044c85727
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/sys/backtrace.rs:154:18
  43:     0x620e4a361a29 - std::rt::lang_start::{{closure}}::h756998bcb6544777
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/rt.rs:164:18
  44:     0x620e4a933200 - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &F>::call_once::h5412c97e5e68829b
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/core/src/ops/function.rs:284:13
  45:     0x620e4a933200 - std::panicking::try::do_call::h3d002e8ffa4f91b7
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:557:40
  46:     0x620e4a933200 - std::panicking::try::h60529ec65ad686dc
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:520:19
  47:     0x620e4a933200 - std::panic::catch_unwind::h28f4a63bd2319cba
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panic.rs:345:14
  48:     0x620e4a933200 - std::rt::lang_start_internal::{{closure}}::h14b8d458d7b543a7
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/rt.rs:143:48
  49:     0x620e4a933200 - std::panicking::try::do_call::h9747ac76d396a084
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:557:40
  50:     0x620e4a933200 - std::panicking::try::h0f984b4d1c23e9bd
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panicking.rs:520:19
  51:     0x620e4a933200 - std::panic::catch_unwind::hcd3e02aab11d9c76
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/panic.rs:345:14
  52:     0x620e4a933200 - std::rt::lang_start_internal::h370157592acdbc7d
                               at /rustc/9b72238eb813e9d06e9e9d270168512fbffd7ee7/library/std/src/rt.rs:143:20
  53:     0x620e4a35dbac - main
  54:     0x787e58034e08 - <unknown>
  55:     0x787e58034ecc - __libc_start_main
  56:     0x620e4a354325 - _start
  57:                0x0 - <unknown>
```

To reproduce:
```
cargo +1.81.0 install --git https://github.com/immunant/c2rust.git c2rust
git clone https://github.com/chirlu/soxr
cd soxr
cmake -S . -B build -DCMAKE_BUILD_TYPE=None -DCMAKE_INSTALL_PREFIX=/usr -DCMAKE_EXPORT_COMPILE_COMMANDS=ON -DBUILD_EXAMPLES=OFF -DBUILD_SHARED_LIBS=ON -DWITH_AVFFT=ON -DWITH_LSR_BINDINGS=ON -DWITH_OPENMP=OFF -DWITH_PFFFT=ON
c2rust transpile -o rust build/compile_commands.json
```




Discussion / hints:
I've added a better backtrace from a release build with debug symbols enabled.

Problem is `c2rust_transpile::c_ast::TypedAstContext::sort_top_decls` at `c2rust/c2rust-transpile/src/c_ast/mod.rs:674:9`

It seems like this is the incorrect `Ord`: https://github.com/immunant/c2rust/blob/9eaf8a15ede349a3ed9bff4af4638a80c88b8b65/c2rust-transpile/src/c_ast/mod.rs#L671-L686

Maybe this is also why the declarations were always backwards in `rav1d`?
I think it will end up being [`compare_src_locs`](https://github.com/immunant/c2rust/blob/master/c2rust-transpile%2Fsrc%2Fc_ast%2Fmod.rs#L209), but I don't understand the code enough to know what's the problem 
> I think it will end up being [`compare_src_locs`](https://github.com/immunant/c2rust/blob/master/c2rust-transpile%2Fsrc%2Fc_ast%2Fmod.rs#L209), but I don't understand the code enough to know what's the problem

Yeah, it seems like it's in there.  @fw-immunant or @rinon, do you remember what was going on here and where a non-total ordering might be coming from?  https://github.com/immunant/c2rust/blob/9eaf8a15ede349a3ed9bff4af4638a80c88b8b65/c2rust-transpile/src/c_ast/mod.rs#L209-L235
I'm not familiar with this code but the last semantically relevant change here seems to be 5d3b0aa0e4073ab71b5d6b8ffb1fcf99a1fa88f5.
"Minimal" reproducer. Anybody know of something like [creduce](https://github.com/csmith-project/creduce) for JSON?
The `sort_data.json` will pass if you remove more than 5 consecutive spans, and weeding through 1200 spans by hand is a bit of a pain.

```rust
use std::{cmp::Ordering, fs::File};

use serde::Deserialize;


#[derive(Copy, Debug, Clone, PartialOrd, PartialEq, Ord, Eq, Deserialize)]
pub struct SrcLoc {
    pub fileid: u64,
    pub line: u64,
    pub column: u64,
}

#[derive(Copy, Debug, Clone, PartialOrd, PartialEq, Ord, Eq, Deserialize)]
pub struct SrcSpan {
    pub fileid: u64,
    pub begin_line: u64,
    pub begin_column: u64,
    pub end_line: u64,
    pub end_column: u64,
}

impl SrcSpan {
    pub fn begin(&self) -> SrcLoc {
        SrcLoc {
            fileid: self.fileid,
            line: self.begin_line,
            column: self.begin_column,
        }
    }
    pub fn end(&self) -> SrcLoc {
        SrcLoc {
            fileid: self.fileid,
            line: self.end_line,
            column: self.end_column,
        }
    }
}

pub type FileId = usize;
#[derive(Deserialize)]
struct Temp {
    spans: Vec<Option<SrcSpan>>,
    file_map: Vec<FileId>,
    include_map: Vec<Vec<SrcLoc>>,
}
use Ordering::*;


pub fn main() {
    let file = File::open("sort_data.json").unwrap();
    let mut temp: Temp = serde_json::from_reader(file).unwrap();

    println!("{}", temp.spans.len());

    sort_top_decls(&mut temp.spans[..], &temp.file_map, &temp.include_map);
}

pub fn sort_top_decls(spans: &mut [Option<SrcSpan>], file_map: &[FileId], include_map: &[Vec<SrcLoc>]) {
    // Group and sort declarations by file and by position
    spans.sort_unstable_by(|a, b| {
        match (a, b) {
            (None, None) => Equal,
            (None, _) => Less,
            (_, None) => Greater,
            (Some(a), Some(b)) => {
                compare_src_locs(file_map, include_map, &a.begin(), &b.begin())
            },
        }
    });
}

pub fn compare_src_locs(file_map: &[FileId], include_map: &[Vec<SrcLoc>], a: &SrcLoc, b: &SrcLoc) -> Ordering {
    /// Compare `self` with `other`, without regard to file id
    fn cmp_pos(a: &SrcLoc, b: &SrcLoc) -> Ordering {
        (a.line, a.column).cmp(&(b.line, b.column))
    }
    let path_a = include_map[file_map[a.fileid as usize]].clone();
    let path_b = include_map[file_map[b.fileid as usize]].clone();
    for (include_a, include_b) in path_a.iter().zip(path_b.iter()) {
        if include_a.fileid != include_b.fileid {
            return cmp_pos(include_a, include_b);
        }
    }
    match path_a.len().cmp(&path_b.len()) {
        Less => {
            // compare the place b was included in a's file with a
            let b = path_b.get(path_a.len()).unwrap();
            cmp_pos(a, b)
        }
        Equal => cmp_pos(a, b),
        Greater => {
            // compare the place a was included in b's file with b
            let a = path_a.get(path_b.len()).unwrap();
            cmp_pos(a, b)
        }
    }
}
```

[sort_data.json](https://github.com/user-attachments/files/17024370/sort_data.json)

Thanks for that reproduction!  That's very helpful.  I don't know of any analogous tool like `creduce` but for JSON; that would be useful.  That said, I was able to test that on the total order properties, and found this that violates `==` transitivity:

```rust
use serde::Deserialize;
use std::cmp::Ordering;
use std::fs::File;

#[derive(Copy, Debug, Clone, PartialOrd, PartialEq, Ord, Eq, Deserialize)]
pub struct SrcLoc {
    pub fileid: u64,
    pub line: u64,
    pub column: u64,
}

#[derive(Copy, Debug, Clone, PartialOrd, PartialEq, Ord, Eq, Deserialize)]
pub struct SrcSpan {
    pub fileid: u64,
    pub begin_line: u64,
    pub begin_column: u64,
    pub end_line: u64,
    pub end_column: u64,
}

impl SrcSpan {
    pub fn begin(&self) -> SrcLoc {
        SrcLoc {
            fileid: self.fileid,
            line: self.begin_line,
            column: self.begin_column,
        }
    }

    pub fn end(&self) -> SrcLoc {
        SrcLoc {
            fileid: self.fileid,
            line: self.end_line,
            column: self.end_column,
        }
    }
}

pub type FileId = usize;
#[derive(Deserialize)]
struct Temp {
    spans: Vec<Option<SrcSpan>>,
    file_map: Vec<FileId>,
    include_map: Vec<Vec<SrcLoc>>,
}

pub fn sort_top_decls(
    spans: &mut [Option<SrcSpan>],
    file_map: &[FileId],
    include_map: &[Vec<SrcLoc>],
) {
    use Ordering::*;
    // Group and sort declarations by file and by position
    spans.sort_unstable_by(|a, b| match (a, b) {
        (None, None) => Equal,
        (None, _) => Less,
        (_, None) => Greater,
        (Some(a), Some(b)) => compare_src_locs(file_map, include_map, &a.begin(), &b.begin()),
    });
}

pub fn compare_src_locs(
    file_map: &[FileId],
    include_map: &[Vec<SrcLoc>],
    a: &SrcLoc,
    b: &SrcLoc,
) -> Ordering {
    /// Compare `self` with `other`, without regard to file id
    fn cmp_pos(a: &SrcLoc, b: &SrcLoc) -> Ordering {
        (a.line, a.column).cmp(&(b.line, b.column))
    }
    let path_a = &include_map[file_map[a.fileid as usize]][..];
    let path_b = &include_map[file_map[b.fileid as usize]][..];
    for (include_a, include_b) in path_a.iter().zip(path_b.iter()) {
        if include_a.fileid != include_b.fileid {
            return cmp_pos(include_a, include_b);
        }
    }

    use Ordering::*;
    match path_a.len().cmp(&path_b.len()) {
        Less => {
            // compare the place b was included in a's file with a
            let b = &path_b[path_a.len()];
            cmp_pos(a, b)
        }
        Equal => cmp_pos(a, b),
        Greater => {
            // compare the place a was included in b's file with b
            let a = &path_a[path_b.len()];
            cmp_pos(a, b)
        }
    }
}

struct MappedSrcLoc<'a> {
    src_loc: SrcLoc,
    file_map: &'a [FileId],
    include_map: &'a [Vec<SrcLoc>],
}

impl PartialEq for MappedSrcLoc<'_> {
    fn eq(&self, other: &Self) -> bool {
        self.partial_cmp(other) == Some(Ordering::Equal)
    }
}

impl Eq for MappedSrcLoc<'_> {}

impl PartialOrd for MappedSrcLoc<'_> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(compare_src_locs(
            self.file_map,
            self.include_map,
            &self.src_loc,
            &other.src_loc,
        ))
    }
}

impl Ord for MappedSrcLoc<'_> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

pub fn main() {
    let file = File::open("sort_data.json").unwrap();
    let temp: Temp = serde_json::from_reader(file).unwrap();
    let Temp {
        spans,
        file_map,
        include_map,
    } = temp;
    let file_map = &file_map;
    let include_map = &include_map;

    // sort_top_decls(&mut spans[..], file_map, include_map);

    let spans = spans
        .into_iter()
        .filter_map(|span| span)
        .collect::<Vec<_>>();
    // spans.sort_unstable_by(|a, b| compare_src_locs(file_map, include_map, &a.begin(), &b.begin()));

    let locs = spans
        .into_iter()
        .map(|span| span.begin())
        .collect::<Vec<_>>();
    // locs.sort_unstable_by(|a, b| compare_src_locs(file_map, include_map, &a, &b));

    let mapped_locs = locs
        .into_iter()
        .map(|src_loc| MappedSrcLoc {
            src_loc,
            file_map,
            include_map,
        })
        .collect::<Vec<_>>();
    // mapped_locs.sort_unstable();

    let n = mapped_locs.len();
    for i in 0..n {
        let a = &mapped_locs[i];
        for j in 0..n {
            let b = &mapped_locs[j];
            for k in 0..n {
                let c = &mapped_locs[k];
                if a < b && b < c {
                    assert!(a < c);
                }
                if a > b && b > c {
                    assert!(a > c);
                }
                if a == b && b == c {
                    if a != c {
                        dbg!(a.src_loc);
                        dbg!(b.src_loc);
                        dbg!(c.src_loc);
                    }
                    assert!(a == c);
                }
            }
        }
        if i % 10 == 0 {
            println!("{i}");
        }
    }
}
```

```shell
> cargo run --release
...
[src/main.rs:177:25] a.src_loc = SrcLoc {
    fileid: 1,
    line: 31,
    column: 1,
}
[src/main.rs:178:25] b.src_loc = SrcLoc {
    fileid: 2,
    line: 214,
    column: 1,
}
[src/main.rs:179:25] c.src_loc = SrcLoc {
    fileid: 1,
    line: 32,
    column: 1,
}
...
```
If you also `dbg!` the include path the problem becomes clear:
```
[src/main.rs:177:25] a.src_loc = SrcLoc {
    fileid: 5,
    line: 5,
    column: 1,
}
[src/main.rs:178:25] &include_map[file_map[a.src_loc.fileid as usize]][..] = [
    SrcLoc {
        fileid: 5,
        line: 6,
        column: 10,
    },
]
[src/main.rs:179:25] b.src_loc = SrcLoc {
    fileid: 2,
    line: 4,
    column: 1,
}
[src/main.rs:180:25] &include_map[file_map[b.src_loc.fileid as usize]][..] = [
    SrcLoc {
        fileid: 2,
        line: 6,
        column: 10,
    },
]
[src/main.rs:181:25] c.src_loc = SrcLoc {
    fileid: 5,
    line: 3,
    column: 7,
}
[src/main.rs:182:25] &include_map[file_map[c.src_loc.fileid as usize]][..] = [
    SrcLoc {
        fileid: 5,
        line: 6,
        column: 10,
    },
]
thread 'main' panicked at src/main.rs:184:21:
assertion failed: a == c
```
a == b because a and b are from different files but are included at the same position. Same for b == c.
But a != c because a and c are from the same file so they are checked not for their include but their actual location.

If you change the start of `compare_src_locs` to:
```rust
    fn cmp_pos(a: &SrcLoc, b: &SrcLoc) -> Ordering {
        (a.line, a.column).cmp(&(b.line, b.column))
    }
    fn cmp_pos_include(a: &SrcLoc, b: &SrcLoc) -> Ordering {
        (a.fileid, a.line, a.column).cmp(&(b.fileid, b.line, b.column))
    }
    let path_a = &include_map[file_map[a.fileid as usize]][..];
    let path_b = &include_map[file_map[b.fileid as usize]][..];
    for (include_a, include_b) in path_a.iter().zip(path_b.iter()) {
        if include_a.fileid != include_b.fileid {
            return cmp_pos_include(include_a, include_b);
        }
    }
```
Then everything works. But that does go against the comment ```/// Compare `self` with `other`, without regard to file id```, but I don't know why fileid would be excluded

If this is the correct way to fix this, I'll create a nicer patch and open a pull request
> If you also `dbg!` the include path the problem becomes clear:
> ...
> a == b because a and b are from different files but are included at the same position. Same for b == c. But a != c because a and c are from the same file so they are checked not for their include but their actual location.

Yeah, I realized that, too.  I'm not sure why we're doing that.

> If you change the start of `compare_src_locs` to:
> 
> ```rust
>     fn cmp_pos(a: &SrcLoc, b: &SrcLoc) -> Ordering {
>         (a.line, a.column).cmp(&(b.line, b.column))
>     }
>     fn cmp_pos_include(a: &SrcLoc, b: &SrcLoc) -> Ordering {
>         (a.fileid, a.line, a.column).cmp(&(b.fileid, b.line, b.column))
>     }
>     let path_a = &include_map[file_map[a.fileid as usize]][..];
>     let path_b = &include_map[file_map[b.fileid as usize]][..];
>     for (include_a, include_b) in path_a.iter().zip(path_b.iter()) {
>         if include_a.fileid != include_b.fileid {
>             return cmp_pos_include(include_a, include_b);
>         }
>     }
> ```

Note also that `cmp_pos_includes` can be just `.cmp` as it's the same as the `#[derive(Ord)]`.

And I changed the `.clone()`s of `Vec<SrcLoc>`s for the `path_*` variables to just slicing, as we don't need the clones there.  It only came up as a performance bottleneck when brute forcing the transitivity checks, but it's better to just not do a clone, so you could include that change as a separate commit as well.

> Then everything works. But that does go against the comment `` /// Compare `self` with `other`, without regard to file id ``, but I don't know why fileid would be excluded

> If this is the correct way to fix this, I'll create a nicer patch and open a pull request

I'm not sure either.  Let me look into it.
I think it's for sure more correct than the current order, so you're welcome to open a PR for it.

Fix patch:
diff --git a/c2rust-transpile/src/c_ast/mod.rs b/c2rust-transpile/src/c_ast/mod.rs
index 182b79581..9506eac70 100644
--- a/c2rust-transpile/src/c_ast/mod.rs
+++ b/c2rust-transpile/src/c_ast/mod.rs
@@ -206,32 +206,37 @@ impl TypedAstContext {
         self.files[id].path.as_deref()
     }
 
+    /// Compare two [`SrcLoc`]s based on their import path
     pub fn compare_src_locs(&self, a: &SrcLoc, b: &SrcLoc) -> Ordering {
-        /// Compare `self` with `other`, without regard to file id
-        fn cmp_pos(a: &SrcLoc, b: &SrcLoc) -> Ordering {
-            (a.line, a.column).cmp(&(b.line, b.column))
-        }
-        let path_a = self.include_map[self.file_map[a.fileid as usize]].clone();
-        let path_b = self.include_map[self.file_map[b.fileid as usize]].clone();
-        for (include_a, include_b) in path_a.iter().zip(path_b.iter()) {
-            if include_a.fileid != include_b.fileid {
-                return cmp_pos(include_a, include_b);
-            }
-        }
         use Ordering::*;
-        match path_a.len().cmp(&path_b.len()) {
+        let path_a = &self.include_map[self.file_map[a.fileid as usize]];
+        let path_b = &self.include_map[self.file_map[b.fileid as usize]];
+
+        // Find the first include that does not match between the two
+        let common_len = path_a.len().min(path_b.len());
+        let order = path_a[..common_len].cmp(&path_b[..common_len]);
+        if order != Equal {
+            return order;
+        }
+
+        // Either all parent includes are the same, or the include paths are of different lengths
+        // because .zip() stops when one of the iterators is empty.
+        let (a, b) = match path_a.len().cmp(&path_b.len()) {
             Less => {
-                // compare the place b was included in a'a file with a
-                let b = path_b.get(path_a.len()).unwrap();
-                cmp_pos(a, b)
+                // a has the shorter path, which means b was included in a's file
+                // so extract that include and compare the position to a
+                let b = &path_b[path_a.len()];
+                (a, b)
             }
-            Equal => cmp_pos(a, b),
+            Equal => (a, b), // a and b have the same include path and are thus in the same file
             Greater => {
-                // compare the place a was included in b's file with b
-                let a = path_a.get(path_b.len()).unwrap();
-                cmp_pos(a, b)
+                // b has the shorter path, which means a was included in b's file
+                // so extract that include and compare the position to b
+                let a = &path_a[path_b.len()];
+                (a, b)
             }
-        }
+        };
+        a.cmp(b)
     }
 
     pub fn get_file_include_line_number(&self, file: FileId) -> Option<u64> {
@@ -1865,3 +1870,244 @@ impl CTypeKind {
         Some(ty)
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_compare_src_locs_ord() {
+        let ctx = TypedAstContext {
+            c_types: Default::default(),
+            c_exprs: Default::default(),
+            c_stmts: Default::default(),
+            c_decls: Default::default(),
+            c_decls_top: vec![],
+            c_main: None,
+            parents: Default::default(),
+            files: vec![],
+            file_map: vec![0, 1, 2, 3, 4, 5, 4, 5],
+            include_map: vec![
+                vec![],
+                vec![],
+                vec![SrcLoc {
+                    fileid: 2,
+                    line: 6,
+                    column: 10,
+                }],
+                vec![],
+                vec![],
+                vec![SrcLoc {
+                    fileid: 5,
+                    line: 6,
+                    column: 10,
+                }],
+            ],
+            label_names: Default::default(),
+            macro_invocations: Default::default(),
+            macro_expansions: Default::default(),
+            macro_expansion_text: Default::default(),
+            comments: vec![],
+            prenamed_decls: Default::default(),
+            va_list_kind: BuiltinVaListKind::CharPtrBuiltinVaList,
+            target: "".to_string(),
+        };
+        let locs = &mut [
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 1,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 1,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 1,
+                line: 10,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 1,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 2,
+                line: 4,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 3,
+                column: 7,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 3,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 3,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 7,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 7,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 7,
+                column: 7,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 7,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 7,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 9,
+                column: 7,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 9,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 9,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 7,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 5,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 8,
+                column: 3,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 8,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 7,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 0,
+                column: 4,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 0,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 2,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 98,
+                column: 3,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 98,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 202,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 5,
+                line: 202,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 7,
+                line: 1,
+                column: 1,
+            },
+            SrcLoc {
+                fileid: 7,
+                line: 3,
+                column: 1,
+            },
+        ];
+
+        let n = locs.len();
+        for i in 0..n {
+            let a = locs[i];
+            for j in 0..n {
+                let b = locs[j];
+                for k in 0..n {
+                    let c = locs[k];
+                    let ab = ctx.compare_src_locs(&a, &b);
+                    let bc = ctx.compare_src_locs(&b, &c);
+                    let ac = ctx.compare_src_locs(&a, &c);
+                    if ab == bc {
+                        assert_eq!(ab, ac, "Total order (transitivity) has been violated");
+                    }
+                }
+            }
+        }
+
+        // This should not panic
+        locs.sort_unstable_by(|a, b| ctx.compare_src_locs(a, b));
+    }
+}


Test patch: