What should builtins.sort (a: b: true) [ 1 2 3 ]even do? Should this be a nix language-level UB? Currently manual does not provide any preconditions https://nix.dev/manual/nix/2.25/language/builtins.html?highlight=builtins.sort#builtins-sort.

This would be a tricky thing to fix. Failing gracefully would require validating the strict weak ordering or using sorting algorithms that do not explode when the comparator is broken. std::sort can easily explode since it's something like qsort. stable_sort is actually a combination of insertion sort with merge sort on top. https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01347.html#l03409

I think using a custom merge sort would be safe even for broken predicates and won't crash nix evaluator, but this would still need to be nix UB (such calls to sort are ill-formed and diagnosing it is prohibitively expensive).

Either way this calls for a custom sorting implementation that does not assume that the provided predicate is strict weak ordering.

In reply to @xokdvium:matrix.org

What should builtins.sort (a: b: true) [ 1 2 3 ]even do? Should this be a nix language-level UB? Currently manual does not provide any preconditions https://nix.dev/manual/nix/2.25/language/builtins.html?highlight=builtins.sort#builtins-sort.

This would be a tricky thing to fix. Failing gracefully would require validating the strict weak ordering or using sorting algorithms that do not explode when the comparator is broken. std::sort can easily explode since it's something like qsort. stable_sort is actually a combination of insertion sort with merge sort on top. https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01347.html#l03409

I think using a custom merge sort would be safe even for broken predicates and won't crash nix evaluator, but this would still need to be nix UB (such calls to sort are ill-formed and diagnosing it is prohibitively expensive).

Either way this calls for a custom sorting implementation that does not assume that the provided predicate is strict weak ordering.

Yup, that's clearly a huge problem and this should be fixed by not using standard sorting algorithms:

Either way this calls for a custom sorting implementation that does not assume that the provided predicate is strict weak ordering.

What I'm trying to say is that this should still be UB in the nix language, but not crash and burn the evaluator.

See the original https://github.com/NixOS/nix/issues/12106#issue-2759417825 issue. I just reproduced the problem on my end on nixpkgs master (9a90c6b6218860ab29f79ecd6213c3a547c15c7e):

../nixpkgs-check-strict-weak-order/result/bin/nix-env -qa --json --arg config 'import pkgs/top-level/packages-config.nix'
/nix/store/4KRAB2H0HD4WVXXMSCXRW21PL77J4I7J-gcc-13.3.0/include/c++/13.3.0/bits/stl_algo.h:5117:
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" @ 0x7ffff3cb8c90 {
      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*;
    }
[1]    2675868 abort (core dumped)  ../nixpkgs-check-strict-weak-order/result/bin/nix-env -qa --json --arg config

A quick glance also shows that this gets triggered in tests.coq, so this is not a one-off problem:

nix-instantiate -A tests.coq

/nix/store/4KRAB2H0HD4WVXXMSCXRW21PL77J4I7J-gcc-13.3.0/include/c++/13.3.0/bits/stl_algo.h:5117:
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" @ 0x7ffc7a9bef10 {
      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*;
    }
[1]    2713634 abort (core dumped)  nix-instantiate -A tests.coq

In reply to @czl92783719:mozilla.org
Hello everyone, I just sudo apt install nix-bin and followed the steps mentioned in cat /usr/share/doc/nix-bin/README.Debian. What's next?

In reply to @perchun:matrix.org
Nix pills are a good way to learn nix
https://nixos.org/guides/nix-pills/