diff options
author | Robert Hensing <roberth@users.noreply.github.com> | 2023-06-06 19:09:56 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-06-06 19:09:56 +0200 |
commit | 6b078d2f5a2d6d4936fa1fa75786fec0a6137e8e (patch) | |
tree | 51b6632fcf62144300e6428fc9b3ad9e51871765 | |
parent | b52f6ac65d27e21516e78bd87b41ea1c81eef8b6 (diff) | |
parent | 9790e70150c83693fa2bcdc65814d01536bf4915 (diff) |
Merge pull request #235267 from tweag/lazier-findFirst
`lib.findFirst`: Add tests and make lazier
-rw-r--r-- | lib/lists.nix | 34 | ||||
-rw-r--r-- | lib/tests/misc.nix | 40 |
2 files changed, 72 insertions, 2 deletions
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 231f19c513eb2..ce980436c1bcb 100644 --- a/lib/tests/misc.nix +++ b/lib/tests/misc.nix @@ -518,6 +518,46 @@ 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; + }; + + testFindFirstLazy = { + expr = findFirst (x: x == 1) 7 [ 1 (abort "list elements after the match must not be evaluated") ]; + expected = 1; + }; # ATTRSETS |