From 6996f76885d81fbc1b066fe346713630e6ac9e1b Mon Sep 17 00:00:00 2001
From: Silvan Mosberger <silvan.mosberger@tweag.io>
Date: Wed, 31 May 2023 22:50:00 +0200
Subject: lib/tests: Add findFirst tests

---
 lib/tests/misc.nix | 35 +++++++++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

(limited to 'lib/tests')

diff --git a/lib/tests/misc.nix b/lib/tests/misc.nix
index 231f19c513eb2..dcb8f1102612b 100644
--- a/lib/tests/misc.nix
+++ b/lib/tests/misc.nix
@@ -518,6 +518,41 @@ runTests {
     expected = false;
   };
 
+  testFindFirstExample1 = {
+    expr = findFirst (x: x > 3) 7 [ 1 6 4 ];
+    expected = 6;
+  };
+
+  testFindFirstExample2 = {
+    expr = findFirst (x: x > 9) 7 [ 1 6 4 ];
+    expected = 7;
+  };
+
+  testFindFirstEmpty = {
+    expr = findFirst (abort "when the list is empty, the predicate is not needed") null [];
+    expected = null;
+  };
+
+  testFindFirstSingleMatch = {
+    expr = findFirst (x: x == 5) null [ 5 ];
+    expected = 5;
+  };
+
+  testFindFirstSingleDefault = {
+    expr = findFirst (x: false) null [ (abort "if the predicate doesn't access the value, it must not be evaluated") ];
+    expected = null;
+  };
+
+  testFindFirstNone = {
+    expr = builtins.tryEval (findFirst (x: x == 2) null [ 1 (throw "the last element must be evaluated when there's no match") ]);
+    expected = { success = false; value = false; };
+  };
+
+  # Makes sure that the implementation doesn't cause a stack overflow
+  testFindFirstBig = {
+    expr = findFirst (x: x == 1000000) null (range 0 1000000);
+    expected = 1000000;
+  };
 
 # ATTRSETS
 
-- 
cgit 1.4.1


From 9790e70150c83693fa2bcdc65814d01536bf4915 Mon Sep 17 00:00:00 2001
From: Silvan Mosberger <silvan.mosberger@tweag.io>
Date: Wed, 31 May 2023 22:53:50 +0200
Subject: lib.list.findFirst: Make lazier

There's no need to evaluate list elements after a matching element
---
 lib/lists.nix      | 34 ++++++++++++++++++++++++++++++++--
 lib/tests/misc.nix |  5 +++++
 2 files changed, 37 insertions(+), 2 deletions(-)

(limited to 'lib/tests')

diff --git a/lib/lists.nix b/lib/lists.nix
index 2186cd4a79f60..5d9af0cf7114e 100644
--- a/lib/lists.nix
+++ b/lib/lists.nix
@@ -198,8 +198,38 @@ rec {
     default:
     # Input list
     list:
-    let found = filter pred list;
-    in if found == [] then default else head found;
+    let
+      # A naive recursive implementation would be much simpler, but
+      # would also overflow the evaluator stack. We use `foldl'` as a workaround
+      # because it reuses the same stack space, evaluating the function for one
+      # element after another. We can't return early, so this means that we
+      # sacrifice early cutoff, but that appears to be an acceptable cost. A
+      # clever scheme with "exponential search" is possible, but appears over-
+      # engineered for now. See https://github.com/NixOS/nixpkgs/pull/235267
+
+      # Invariant:
+      # - if index < 0 then el == elemAt list (- index - 1) and all elements before el didn't satisfy pred
+      # - if index >= 0 then pred (elemAt list index) and all elements before (elemAt list index) didn't satisfy pred
+      #
+      # We start with index -1 and the 0'th element of the list, which satisfies the invariant
+      resultIndex = foldl' (index: el:
+        if index < 0 then
+          # No match yet before the current index, we need to check the element
+          if pred el then
+            # We have a match! Turn it into the actual index to prevent future iterations from modifying it
+            - index - 1
+          else
+            # Still no match, update the index to the next element (we're counting down, so minus one)
+            index - 1
+        else
+          # There's already a match, propagate the index without evaluating anything
+          index
+      ) (-1) list;
+    in
+    if resultIndex < 0 then
+      default
+    else
+      elemAt list resultIndex;
 
   /* Return true if function `pred` returns true for at least one
      element of `list`.
diff --git a/lib/tests/misc.nix b/lib/tests/misc.nix
index dcb8f1102612b..ce980436c1bcb 100644
--- a/lib/tests/misc.nix
+++ b/lib/tests/misc.nix
@@ -554,6 +554,11 @@ runTests {
     expected = 1000000;
   };
 
+  testFindFirstLazy = {
+    expr = findFirst (x: x == 1) 7 [ 1 (abort "list elements after the match must not be evaluated") ];
+    expected = 1;
+  };
+
 # ATTRSETS
 
   testConcatMapAttrs = {
-- 
cgit 1.4.1