feat(tvix/eval): Implement builtins.sort r/5222

This is a bit tricky because the comparator can throw errors, so we
need to propagate them out if they exist and try to avoid sorting
forever by returning a reasonable ordering in this case (as
short-circuiting is not available).

Co-Authored-By: Vincent Ambo <tazjin@tvl.su>
Change-Id: Icae1d30f43ec1ae64b2ba51e73ee467605686792
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7072
Tested-by: BuildkiteCI
Reviewed-by: sterni <sternenseemann@systemli.org>

1 files changed, 20 insertions, 0 deletions

diff --git a/tvix/eval/src/tests/nix_tests/eval-okay-sort.nix b/tvix/eval/src/tests/nix_tests/eval-okay-sort.nix
new file mode 100644
index 0000000000..50aa78e403
--- /dev/null
+++ b/tvix/eval/src/tests/nix_tests/eval-okay-sort.nix
@@ -0,0 +1,20 @@
+with builtins;
+
+[ (sort lessThan [ 483 249 526 147 42 77 ])
+  (sort (x: y: y < x) [ 483 249 526 147 42 77 ])
+  (sort lessThan [ "foo" "bar" "xyzzy" "fnord" ])
+  (sort (x: y: x.key < y.key)
+    [ { key = 1; value = "foo"; } { key = 2; value = "bar"; } { key = 1; value = "fnord"; } ])
+  (sort lessThan [
+    [ 1 6 ]
+    [ ]
+    [ 2 3 ]
+    [ 3 ]
+    [ 1 5 ]
+    [ 2 ]
+    [ 1 ]
+    [ ]
+    [ 1 4 ]
+    [ 3 ]
+  ])
+]