Merge pull request #273004 from hercules-ci/attrset-path-longest-prefix

lib.attrsets.longestValidPathPrefix: init

2 files changed, 117 insertions, 0 deletions

diff --git a/lib/attrsets.nix b/lib/attrsets.nix
index 3d4366ce1814..9b4a8684f9b7 100644
--- a/lib/attrsets.nix
+++ b/lib/attrsets.nix
@@ -51,12 +51,19 @@ rec {
 
   /* Return if an attribute from nested attribute set exists.
 
+     **Laws**:
+      1.  ```nix
+          hasAttrByPath [] x == true
+          ```
+
      Example:
        x = { a = { b = 3; }; }
        hasAttrByPath ["a" "b"] x
        => true
        hasAttrByPath ["z" "z"] x
        => false
+       hasAttrByPath [] (throw "no need")
+       => true
 
     Type:
       hasAttrByPath :: [String] -> AttrSet -> Bool
@@ -80,6 +87,71 @@ rec {
     in
       hasAttrByPath' 0 e;
 
+  /*
+    Return the longest prefix of an attribute path that refers to an existing attribute in a nesting of attribute sets.
+
+    Can be used after [`mapAttrsRecursiveCond`](#function-library-lib.attrsets.mapAttrsRecursiveCond) to apply a condition,
+    although this will evaluate the predicate function on sibling attributes as well.
+
+    Note that the empty attribute path is valid for all values, so this function only throws an exception if any of its inputs does.
+
+    **Laws**:
+    1.  ```nix
+        attrsets.longestValidPathPrefix [] x == []
+        ```
+
+    2.  ```nix
+        hasAttrByPath (attrsets.longestValidPathPrefix p x) x == true
+        ```
+
+    Example:
+      x = { a = { b = 3; }; }
+      attrsets.longestValidPathPrefix ["a" "b" "c"] x
+      => ["a" "b"]
+      attrsets.longestValidPathPrefix ["a"] x
+      => ["a"]
+      attrsets.longestValidPathPrefix ["z" "z"] x
+      => []
+      attrsets.longestValidPathPrefix ["z" "z"] (throw "no need")
+      => []
+
+    Type:
+      attrsets.longestValidPathPrefix :: [String] -> Value -> [String]
+  */
+  longestValidPathPrefix =
+    # A list of strings representing the longest possible path that may be returned.
+    attrPath:
+    # The nested attribute set to check.
+    v:
+    let
+      lenAttrPath = length attrPath;
+      getPrefixForSetAtIndex =
+        # The nested attribute set to check, if it is an attribute set, which
+        # is not a given.
+        remainingSet:
+        # The index of the attribute we're about to check, as well as
+        # the length of the prefix we've already checked.
+        remainingPathIndex:
+
+          if remainingPathIndex == lenAttrPath then
+            # All previously checked attributes exist, and no attr names left,
+            # so we return the whole path.
+            attrPath
+          else
+            let
+              attr = elemAt attrPath remainingPathIndex;
+            in
+            if remainingSet ? ${attr} then
+              getPrefixForSetAtIndex
+                remainingSet.${attr}      # advance from the set to the attribute value
+                (remainingPathIndex + 1)  # advance the path
+            else
+              # The attribute doesn't exist, so we return the prefix up to the
+              # previously checked length.
+              take remainingPathIndex attrPath;
+    in
+      getPrefixForSetAtIndex v 0;
+
   /* Create a new attribute set with `value` set at the nested attribute location specified in `attrPath`.
 
      Example:
diff --git a/lib/tests/misc.nix b/lib/tests/misc.nix
index 608af656d02c..2884e880e13a 100644
--- a/lib/tests/misc.nix
+++ b/lib/tests/misc.nix
@@ -697,6 +697,51 @@ runTests {
     expected = false;
   };
 
+  testHasAttrByPathNonStrict = {
+    expr = hasAttrByPath [] (throw "do not use");
+    expected = true;
+  };
+
+  testLongestValidPathPrefix_empty_empty = {
+    expr = attrsets.longestValidPathPrefix [ ] { };
+    expected = [ ];
+  };
+
+  testLongestValidPathPrefix_empty_nonStrict = {
+    expr = attrsets.longestValidPathPrefix [ ] (throw "do not use");
+    expected = [ ];
+  };
+
+  testLongestValidPathPrefix_zero = {
+    expr = attrsets.longestValidPathPrefix [ "a" (throw "do not use") ] { d = null; };
+    expected = [ ];
+  };
+
+  testLongestValidPathPrefix_zero_b = {
+    expr = attrsets.longestValidPathPrefix [ "z" "z" ] "remarkably harmonious";
+    expected = [ ];
+  };
+
+  testLongestValidPathPrefix_one = {
+    expr = attrsets.longestValidPathPrefix [ "a" "b" "c" ] { a = null; };
+    expected = [ "a" ];
+  };
+
+  testLongestValidPathPrefix_two = {
+    expr = attrsets.longestValidPathPrefix [ "a" "b" "c" ] { a.b = null; };
+    expected = [ "a" "b" ];
+  };
+
+  testLongestValidPathPrefix_three = {
+    expr = attrsets.longestValidPathPrefix [ "a" "b" "c" ] { a.b.c = null; };
+    expected = [ "a" "b" "c" ];
+  };
+
+  testLongestValidPathPrefix_three_extra = {
+    expr = attrsets.longestValidPathPrefix [ "a" "b" "c" ] { a.b.c.d = throw "nope"; };
+    expected = [ "a" "b" "c" ];
+  };
+
   testFindFirstIndexExample1 = {
     expr = lists.findFirstIndex (x: x > 3) (abort "index found, so a default must not be evaluated") [ 1 6 4 ];
     expected = 1;