diff options
| -rw-r--r-- | lib/lists.nix | 34 | ||||
| -rw-r--r-- | lib/tests/misc.nix | 5 |
2 files changed, 37 insertions, 2 deletions
diff --git a/lib/lists.nix b/lib/lists.nix index 2186cd4a79f..5d9af0cf711 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 dcb8f110261..ce980436c1b 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 = { |