Merge pull request #5631 from Infinisil/list-compare

Make lists be comparable

5 files changed, 41 insertions, 11 deletions

diff --git a/doc/manual/src/expressions/language-operators.md b/doc/manual/src/expressions/language-operators.md
index 6ab319039..268b44f4c 100644
--- a/doc/manual/src/expressions/language-operators.md
+++ b/doc/manual/src/expressions/language-operators.md
@@ -17,10 +17,10 @@ order of precedence (from strongest to weakest binding).
 | String Concatenation     | *string1* `+` *string2*             | left          | String concatenation.                                                                                                                                                                                                         | 7          |
 | Not                      | `!` *e*                             | none          | Boolean negation.                                                                                                                                                                                                             | 8          |
 | Update                   | *e1* `//` *e2*                      | right         | Return a set consisting of the attributes in *e1* and *e2* (with the latter taking precedence over the former in case of equally named attributes).                                                                           | 9          |
-| Less Than                | *e1* `<` *e2*,                      | none          | Arithmetic comparison.                                                                                                                                                                                                        | 10         |
-| Less Than or Equal To    | *e1* `<=` *e2*                      | none          | Arithmetic comparison.                                                                                                                                                                                                        | 10         |
-| Greater Than             | *e1* `>` *e2*                       | none          | Arithmetic comparison.                                                                                                                                                                                                        | 10         |
-| Greater Than or Equal To | *e1* `>=` *e2*                      | none          | Arithmetic comparison.                                                                                                                                                                                                        | 10         |
+| Less Than                | *e1* `<` *e2*,                      | none          | Arithmetic/lexicographic comparison.                                                                                                                                                                                                        | 10         |
+| Less Than or Equal To    | *e1* `<=` *e2*                      | none          | Arithmetic/lexicographic comparison.                                                                                                                                                                                                        | 10         |
+| Greater Than             | *e1* `>` *e2*                       | none          | Arithmetic/lexicographic comparison.                                                                                                                                                                                                        | 10         |
+| Greater Than or Equal To | *e1* `>=` *e2*                      | none          | Arithmetic/lexicographic comparison.                                                                                                                                                                                                        | 10         |
 | Equality                 | *e1* `==` *e2*                      | none          | Equality.                                                                                                                                                                                                                     | 11         |
 | Inequality               | *e1* `!=` *e2*                      | none          | Inequality.                                                                                                                                                                                                                   | 11         |
 | Logical AND              | *e1* `&&` *e2*                      | left          | Logical AND.                                                                                                                                                                                                                  | 12         |
diff --git a/doc/manual/src/release-notes/rl-next.md b/doc/manual/src/release-notes/rl-next.md
index 9a29938c2..26c7d2cce 100644
--- a/doc/manual/src/release-notes/rl-next.md
+++ b/doc/manual/src/release-notes/rl-next.md
@@ -3,3 +3,5 @@
 * Binary cache stores now have a setting `compression-level`.
 
 * `nix develop` now has a flag `--unpack` to run `unpackPhase`.
+
+* Lists can now be compared lexicographically using the `<` operator.
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 24b931882..8cbeaa520 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -517,7 +517,11 @@ static RegisterPrimOp primop_isPath({
 
 struct CompareValues
 {
-    bool operator () (const Value * v1, const Value * v2) const
+    EvalState & state;
+
+    CompareValues(EvalState & state) : state(state) { };
+
+    bool operator () (Value * v1, Value * v2) const
     {
         if (v1->type() == nFloat && v2->type() == nInt)
             return v1->fpoint < v2->integer;
@@ -534,6 +538,17 @@ struct CompareValues
                 return strcmp(v1->string.s, v2->string.s) < 0;
             case nPath:
                 return strcmp(v1->path, v2->path) < 0;
+            case nList:
+                // Lexicographic comparison
+                for (size_t i = 0;; i++) {
+                    if (i == v2->listSize()) {
+                        return false;
+                    } else if (i == v1->listSize()) {
+                        return true;
+                    } else if (!state.eqValues(*v1->listElems()[i], *v2->listElems()[i])) {
+                        return (*this)(v1->listElems()[i], v2->listElems()[i]);
+                    }
+                }
             default:
                 throw EvalError("cannot compare %1% with %2%", showType(*v1), showType(*v2));
         }
@@ -621,7 +636,8 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
     ValueList res;
     // `doneKeys' doesn't need to be a GC root, because its values are
     // reachable from res.
-    set<Value *, CompareValues> doneKeys;
+    auto cmp = CompareValues(state);
+    set<Value *, decltype(cmp)> doneKeys(cmp);
     while (!workSet.empty()) {
         Value * e = *(workSet.begin());
         workSet.pop_front();
@@ -2821,7 +2837,7 @@ static void prim_sort(EvalState & state, const Pos & pos, Value * * args, Value
         /* Optimization: if the comparator is lessThan, bypass
            callFunction. */
         if (args[0]->isPrimOp() && args[0]->primOp->fun == prim_lessThan)
-            return CompareValues()(a, b);
+            return CompareValues(state)(a, b);
 
         Value * vs[] = {a, b};
         Value vBool;
@@ -3103,7 +3119,7 @@ static void prim_lessThan(EvalState & state, const Pos & pos, Value * * args, Va
 {
     state.forceValue(*args[0], pos);
     state.forceValue(*args[1], pos);
-    CompareValues comp;
+    CompareValues comp{state};
     mkBool(v, comp(args[0], args[1]));
 }
 
@@ -3693,7 +3709,7 @@ void EvalState::createBaseEnv()
        language feature gets added.  It's not necessary to increase it
        when primops get added, because you can just use `builtins ?
        primOp' to check. */
-    mkInt(v, 5);
+    mkInt(v, 6);
     addConstant("__langVersion", v);
 
     // Miscellaneous
diff --git a/tests/lang/eval-okay-sort.exp b/tests/lang/eval-okay-sort.exp
index 148b93516..899119e20 100644
--- a/tests/lang/eval-okay-sort.exp
+++ b/tests/lang/eval-okay-sort.exp
@@ -1 +1 @@
-[ [ 42 77 147 249 483 526 ] [ 526 483 249 147 77 42 ] [ "bar" "fnord" "foo" "xyzzy" ] [ { key = 1; value = "foo"; } { key = 1; value = "fnord"; } { key = 2; value = "bar"; } ] ]
+[ [ 42 77 147 249 483 526 ] [ 526 483 249 147 77 42 ] [ "bar" "fnord" "foo" "xyzzy" ] [ { key = 1; value = "foo"; } { key = 1; value = "fnord"; } { key = 2; value = "bar"; } ] [ [ ] [ ] [ 1 ] [ 1 4 ] [ 1 5 ] [ 1 6 ] [ 2 ] [ 2 3 ] [ 3 ] [ 3 ] ] ]
diff --git a/tests/lang/eval-okay-sort.nix b/tests/lang/eval-okay-sort.nix
index 8299c3a4a..50aa78e40 100644
--- a/tests/lang/eval-okay-sort.nix
+++ b/tests/lang/eval-okay-sort.nix
@@ -4,5 +4,17 @@ with builtins;
   (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"; } ]) 
+    [ { 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 ]
+  ])
 ]