`builtins.sort` crashes when `nix ` is build with `-D_GLIBCXX_DEBUG`: Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

[trofi]

Describe the bug

In an attempt to reproduce an unrelated I tried to build nix with -D_GLIBCXX_DEBUG. This exposed the invariant violation around the comparator to stable_sort:

nix-env -qa --json --arg config 'import <nixpkgs/pkgs/top-level/packages-config.nix>' -I nixpkgs=~/n -f ~/n
/nix/store/L89IQC7AM6I60Y8VK507ZWRZXF0WCD3V-gcc-14-20241116/include/c++/14-20241116/bits/stl_algo.h:5027:
In function:
    void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter =
    nix::Value**; _Compare = nix::prim_sort(EvalState&, PosIdx, Value**,
    Value&)::<lambda(nix::Value*, nix::Value*)>]

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

Objects involved in the operation:
    instance "functor" @ 0x7ffcb5307980 {
      type = nix::prim_sort(nix::EvalState&, nix::PosIdx, nix::Value**, nix::Value&)::{lambda(nix::Value*, nix::Value*)#1};
    }
    iterator::value_type "ordered type"  {
      type = nix::Value*;
    }
Aborted (core dumped)

Steps To Reproduce

Build nix with -D_GLIBCXX_DEBUG. I did it as:

  nix.package = ((pkgs.nixVersions.latest or pkgs.nixVersions.unstable).override ({
    # propagate -D_GLIBCXX_DEBUG to dependencies where is affects ABI
    withAWS = false;
    gtest = pkgs.gtest.overrideAttrs (oa: {
      env = (oa.env or {}) // {
        NIX_CFLAGS_COMPILE = (oa.env.NIX_CFLAGS_COMPILE or "") + " -D_GLIBCXX_DEBUG";
      };
    });
  })).overrideAttrs (oa: {
    env = (oa.env or {}) // {
      NIX_CFLAGS_COMPILE = (oa.env.NIX_CFLAGS_COMPILE or "") + " -D_GLIBCXX_DEBUG";
    };
  });

Expected behavior

nix-env should not crash.

Metadata

nix-env (Nix) 2.25.3

Additional context

It looks like the predicate problem is already known at

nix/src/libexpr/primops.cc

Line 3642 in bff9296

/* FIXME: std::sort can segfault if the comparator is not a strict

    /* FIXME: std::sort can segfault if the comparator is not a strict
       weak ordering. What to do? std::stable_sort() seems more
       resilient, but no guarantees... */
    std::stable_sort(list.begin(), list.end(), comparator);

The backtrace:

$ gdb --args nix-env -qa --json --arg config 'import <nixpkgs/pkgs/top-level/packages-config.nix>' -I nixpkgs=~/n -f ~/n
(gdb) run
...
(gdb) bt
#0  0x00007ffff66988ec in __pthread_kill_implementation () from /nix/store/65h17wjrrlsj2rj540igylrx7fqcd6vq-glibc-2.40-36/lib/libc.so.6
#1  0x00007ffff66409c6 in raise () from /nix/store/65h17wjrrlsj2rj540igylrx7fqcd6vq-glibc-2.40-36/lib/libc.so.6
#2  0x00007ffff6628938 in abort () from /nix/store/65h17wjrrlsj2rj540igylrx7fqcd6vq-glibc-2.40-36/lib/libc.so.6
#3  0x00007ffff6ab0203 in __gnu_debug::_Error_formatter::_M_error() const [clone .cold] () from /nix/store/bpq1s72cw9qb2fs8mnmlw6hn2c7iy0ss-gcc-14-20241116-lib/lib/libstdc++.so.6
#4  0x00007ffff7bab7fe in nix::prim_sort(nix::EvalState&, nix::PosIdx, nix::Value**, nix::Value&) [clone .lto_priv.0] () from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
#5  0x00007ffff7aed1bf in nix::EvalState::callFunction(nix::Value&, unsigned long, nix::Value**, nix::Value&, nix::PosIdx) () from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
#6  0x00007ffff7baac4c in nix::prim_length(nix::EvalState&, nix::PosIdx, nix::Value**, nix::Value&) [clone .lto_priv.0] () from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
#7  0x00007ffff7aece69 in nix::EvalState::callFunction(nix::Value&, unsigned long, nix::Value**, nix::Value&, nix::PosIdx) () from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
#8  0x00007ffff7af1150 in nix::ExprCall::eval(nix::EvalState&, nix::Env&, nix::Value&) () from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
#9  0x00007ffff7badace in nix::prim_lessThan(nix::EvalState&, nix::PosIdx, nix::Value**, nix::Value&) [clone .lto_priv.0] () from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
#10 0x00007ffff7aece69 in nix::EvalState::callFunction(nix::Value&, unsigned long, nix::Value**, nix::Value&, nix::PosIdx) () from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
#11 0x00007ffff7af1150 in nix::ExprCall::eval(nix::EvalState&, nix::Env&, nix::Value&) () from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
#12 0x00007ffff7ae8bc4 in nix::EvalState::evalBool(nix::Env&, nix::Expr*, nix::PosIdx, std::basic_string_view<char, std::char_traits<char> >) ()
   from /nix/store/nmf85jbch9v9a9mq516wrlm0qxq32vfb-nix-2.25.3/lib/libnixexpr.so
...

Checklist

• checked open bug issues and pull requests for possible duplicates

---

Add 👍 to issues you find important.

[trofi]

Shorter reproducer without the need for external files:

$ nix eval --expr 'builtins.sort (a: b: true) [ 1 2 3 ]'

/nix/store/L89IQC7AM6I60Y8VK507ZWRZXF0WCD3V-gcc-14-20241116/include/c++/14-20241116/bits/stl_algo.h:5027:
In function:
    void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter =
    nix::Value**; _Compare = nix::prim_sort(EvalState&, PosIdx, Value**,
    Value&)::<lambda(nix::Value*, nix::Value*)>]

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

Objects involved in the operation:
    instance "functor" @ 0x7ffd7d2fdb00 {
      type = nix::prim_sort(nix::EvalState&, nix::PosIdx, nix::Value**, nix::Value&)::{lambda(nix::Value*, nix::Value*)#1};
    }
    iterator::value_type "ordered type"  {
      type = nix::Value*;
    }
Aborted (core dumped)

[trofi]

With the following hack against nix:

--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -3633,6 +3633,24 @@ static void prim_sort(EvalState & state, const PosIdx pos, Value * * args, Value
                 return CompareValues(state, noPos, "while evaluating the ordering function passed to builtins.sort")(a, b);
         }

+        /* Validate basic ordering requirements for comparator: */
+        {
+            Value * vs[] = {a, a};
+            Value vBool;
+            state.callFunction(*args[0], vs, vBool, noPos);
+            bool br = state.forceBool(vBool, pos, "while evaluating the return value of the sorting function passed to builtins.sort");
+            if (br)
+                state.error<EvalError>("!(a < a) assert failed").atPos(pos).debugThrow();
+        }
+        {
+            Value * vs[] = {b, b};
+            Value vBool;
+            state.callFunction(*args[0], vs, vBool, noPos);
+            bool br = state.forceBool(vBool, pos, "while evaluating the return value of the sorting function passed to builtins.sort");
+            if (br)
+                state.error<EvalError>("!(b < b) assert failed").atPos(pos).debugThrow();
+        }
+
         Value * vs[] = {a, b};
         Value vBool;
         state.callFunction(*args[0], vs, vBool, noPos);

I can now see where in nixpkgs the invariant is breaking:

$ nix-instantiate -A colmapWithCuda --show-trace
error:
       … while calling a functor (an attribute set with a '__functor' attribute)
         at /home/slyfox/dev/git/nixpkgs-master/pkgs/top-level/all-packages.nix:5843:20:
         5842|   colmap = libsForQt5.callPackage ../applications/science/misc/colmap { inherit (config) cudaSupport; };
         5843|   colmapWithCuda = colmap.override { cudaSupport = true; };
             |                    ^
         5844|
...
         at /home/slyfox/dev/git/nixpkgs-master/pkgs/development/cuda-modules/generic-builders/multiplex.nix:88:17:
           87|   # perSystemReleases :: List Package
           88|   allReleases = lib.pipe releaseSets [
             |                 ^
           89|     (lib.attrValues)

It's an indirect way to point at pkgs/development/cuda-modules/generic-builders/multiplex.nix:

  preferable =
    p1: p2: (isSupported p2 -> isSupported p1) && (strings.versionAtLeast p1.version p2.version);

 # ...
  newest = builtins.head (builtins.sort preferable allReleases);

[trofi]

/cc @fricklerhandwerk if Valentin you are still looking after the documentation bits of nix. Today :doc builtins.sort does not say much about what happens when comparator does not implement the "strict weak order" property required by std::stable_sort(). Looks like right now it's an undefined behaviour (an occasional crash in debug builds) inherited by unguarded use of C++ implementation.

[roberth]

This seems quite tricky and a reproducibility minefield if we were to try to make it succeed, because it's probably dependent on the standard library sort implementation details.
I think in theory we could either

a. Implement our own sort, so that it can do garbage-in garbage-out in a known, deterministic way, regardless of eval platform

b. Validate the user-provided function

If we only validate the user-provided function for the comparisons that are needed by the STL sort implementation, we will still be dependent on the platform's choice of sort implementation to pick the pairings for which the comparator is tested. This leads errors whose occurrence is non-deterministic. Checking all pairings is not feasible. The error message suggests that we only need to check $$n$$ reflexive pairings, but it doubt that's good enough. Surely we're relying on other properties, such as a < b -> b > a, which requires the full cartesian product of pairings to be compared. That's not feasible.

So I'm leaning towards (a), implement our own sort. What did I miss?

[xokdvium]

@roberth, @trofi I've whipped up #12623 with custom sort implementation which uses the "garbage-in garbage-out" approach. I've also included some documentation changes for the builtins.sort primop with complete description of implicit preconditions.