lib/attrsets.nix

   1 /* Operations on attribute sets. */
   2 { lib }:
   3
   4 let
   5   inherit (builtins) head tail length;
   6   inherit (lib.trivial) id mergeAttrs;
   7   inherit (lib.strings) concatStringsSep concatMapStringsSep escapeNixIdentifier sanitizeDerivationName;
   8   inherit (lib.lists) foldr foldl' concatMap concatLists elemAt all partition groupBy take foldl;
   9 in
  10
  11 rec {
  12   inherit (builtins) attrNames listToAttrs hasAttr isAttrs getAttr removeAttrs;
  13
  14
  15   /* Return an attribute from nested attribute sets.
  16
  17      Example:
  18        x = { a = { b = 3; }; }
  19        # ["a" "b"] is equivalent to x.a.b
  20        # 6 is a default value to return if the path does not exist in attrset
  21        attrByPath ["a" "b"] 6 x
  22        => 3
  23        attrByPath ["z" "z"] 6 x
  24        => 6
  25
  26      Type:
  27        attrByPath :: [String] -> Any -> AttrSet -> Any
  28
  29   */
  30   attrByPath =
  31     # A list of strings representing the attribute path to return from `set`
  32     attrPath:
  33     # Default value if `attrPath` does not resolve to an existing value
  34     default:
  35     # The nested attribute set to select values from
  36     set:
  37     let attr = head attrPath;
  38     in
  39       if attrPath == [] then set
  40       else if set ? ${attr}
  41       then attrByPath (tail attrPath) default set.${attr}
  42       else default;
  43
  44   /* Return if an attribute from nested attribute set exists.
  45
  46      Example:
  47        x = { a = { b = 3; }; }
  48        hasAttrByPath ["a" "b"] x
  49        => true
  50        hasAttrByPath ["z" "z"] x
  51        => false
  52
  53     Type:
  54       hasAttrByPath :: [String] -> AttrSet -> Bool
  55   */
  56   hasAttrByPath =
  57     # A list of strings representing the attribute path to check from `set`
  58     attrPath:
  59     # The nested attribute set to check
  60     e:
  61     let attr = head attrPath;
  62     in
  63       if attrPath == [] then true
  64       else if e ? ${attr}
  65       then hasAttrByPath (tail attrPath) e.${attr}
  66       else false;
  67
  68
  69   /* Create a new attribute set with `value` set at the nested attribute location specified in `attrPath`.
  70
  71      Example:
  72        setAttrByPath ["a" "b"] 3
  73        => { a = { b = 3; }; }
  74
  75      Type:
  76        setAttrByPath :: [String] -> Any -> AttrSet
  77   */
  78   setAttrByPath =
  79     # A list of strings representing the attribute path to set
  80     attrPath:
  81     # The value to set at the location described by `attrPath`
  82     value:
  83     let
  84       len = length attrPath;
  85       atDepth = n:
  86         if n == len
  87         then value
  88         else { ${elemAt attrPath n} = atDepth (n + 1); };
  89     in atDepth 0;
  90
  91   /* Like `attrByPath`, but without a default value. If it doesn't find the
  92      path it will throw an error.
  93
  94      Example:
  95        x = { a = { b = 3; }; }
  96        getAttrFromPath ["a" "b"] x
  97        => 3
  98        getAttrFromPath ["z" "z"] x
  99        => error: cannot find attribute `z.z'
 100
 101      Type:
 102        getAttrFromPath :: [String] -> AttrSet -> Any
 103   */
 104   getAttrFromPath =
 105     # A list of strings representing the attribute path to get from `set`
 106     attrPath:
 107     # The nested attribute set to find the value in.
 108     set:
 109     let errorMsg = "cannot find attribute `" + concatStringsSep "." attrPath + "'";
 110     in attrByPath attrPath (abort errorMsg) set;
 111
 112   /* Map each attribute in the given set and merge them into a new attribute set.
 113
 114      Type:
 115        concatMapAttrs :: (String -> a -> AttrSet) -> AttrSet -> AttrSet
 116
 117      Example:
 118        concatMapAttrs
 119          (name: value: {
 120            ${name} = value;
 121            ${name + value} = value;
 122          })
 123          { x = "a"; y = "b"; }
 124        => { x = "a"; xa = "a"; y = "b"; yb = "b"; }
 125   */
 126   concatMapAttrs = f: v:
 127     foldl' mergeAttrs { }
 128       (attrValues
 129         (mapAttrs f v)
 130       );
 131
 132
 133   /* Update or set specific paths of an attribute set.
 134
 135      Takes a list of updates to apply and an attribute set to apply them to,
 136      and returns the attribute set with the updates applied. Updates are
 137      represented as `{ path = ...; update = ...; }` values, where `path` is a
 138      list of strings representing the attribute path that should be updated,
 139      and `update` is a function that takes the old value at that attribute path
 140      as an argument and returns the new
 141      value it should be.
 142
 143      Properties:
 144
 145      - Updates to deeper attribute paths are applied before updates to more
 146        shallow attribute paths
 147
 148      - Multiple updates to the same attribute path are applied in the order
 149        they appear in the update list
 150
 151      - If any but the last `path` element leads into a value that is not an
 152        attribute set, an error is thrown
 153
 154      - If there is an update for an attribute path that doesn't exist,
 155        accessing the argument in the update function causes an error, but
 156        intermediate attribute sets are implicitly created as needed
 157
 158      Example:
 159        updateManyAttrsByPath [
 160          {
 161            path = [ "a" "b" ];
 162            update = old: { d = old.c; };
 163          }
 164          {
 165            path = [ "a" "b" "c" ];
 166            update = old: old + 1;
 167          }
 168          {
 169            path = [ "x" "y" ];
 170            update = old: "xy";
 171          }
 172        ] { a.b.c = 0; }
 173        => { a = { b = { d = 1; }; }; x = { y = "xy"; }; }
 174
 175     Type: updateManyAttrsByPath :: [{ path :: [String]; update :: (Any -> Any); }] -> AttrSet -> AttrSet
 176   */
 177   updateManyAttrsByPath = let
 178     # When recursing into attributes, instead of updating the `path` of each
 179     # update using `tail`, which needs to allocate an entirely new list,
 180     # we just pass a prefix length to use and make sure to only look at the
 181     # path without the prefix length, so that we can reuse the original list
 182     # entries.
 183     go = prefixLength: hasValue: value: updates:
 184       let
 185         # Splits updates into ones on this level (split.right)
 186         # And ones on levels further down (split.wrong)
 187         split = partition (el: length el.path == prefixLength) updates;
 188
 189         # Groups updates on further down levels into the attributes they modify
 190         nested = groupBy (el: elemAt el.path prefixLength) split.wrong;
 191
 192         # Applies only nested modification to the input value
 193         withNestedMods =
 194           # Return the value directly if we don't have any nested modifications
 195           if split.wrong == [] then
 196             if hasValue then value
 197             else
 198               # Throw an error if there is no value. This `head` call here is
 199               # safe, but only in this branch since `go` could only be called
 200               # with `hasValue == false` for nested updates, in which case
 201               # it's also always called with at least one update
 202               let updatePath = (head split.right).path; in
 203               throw
 204               ( "updateManyAttrsByPath: Path '${showAttrPath updatePath}' does "
 205               + "not exist in the given value, but the first update to this "
 206               + "path tries to access the existing value.")
 207           else
 208             # If there are nested modifications, try to apply them to the value
 209             if ! hasValue then
 210               # But if we don't have a value, just use an empty attribute set
 211               # as the value, but simplify the code a bit
 212               mapAttrs (name: go (prefixLength + 1) false null) nested
 213             else if isAttrs value then
 214               # If we do have a value and it's an attribute set, override it
 215               # with the nested modifications
 216               value //
 217               mapAttrs (name: go (prefixLength + 1) (value ? ${name}) value.${name}) nested
 218             else
 219               # However if it's not an attribute set, we can't apply the nested
 220               # modifications, throw an error
 221               let updatePath = (head split.wrong).path; in
 222               throw
 223               ( "updateManyAttrsByPath: Path '${showAttrPath updatePath}' needs to "
 224               + "be updated, but path '${showAttrPath (take prefixLength updatePath)}' "
 225               + "of the given value is not an attribute set, so we can't "
 226               + "update an attribute inside of it.");
 227
 228         # We get the final result by applying all the updates on this level
 229         # after having applied all the nested updates
 230         # We use foldl instead of foldl' so that in case of multiple updates,
 231         # intermediate values aren't evaluated if not needed
 232       in foldl (acc: el: el.update acc) withNestedMods split.right;
 233
 234   in updates: value: go 0 true value updates;
 235
 236   /* Return the specified attributes from a set.
 237
 238      Example:
 239        attrVals ["a" "b" "c"] as
 240        => [as.a as.b as.c]
 241
 242      Type:
 243        attrVals :: [String] -> AttrSet -> [Any]
 244   */
 245   attrVals =
 246     # The list of attributes to fetch from `set`. Each attribute name must exist on the attrbitue set
 247     nameList:
 248     # The set to get attribute values from
 249     set: map (x: set.${x}) nameList;
 250
 251
 252   /* Return the values of all attributes in the given set, sorted by
 253      attribute name.
 254
 255      Example:
 256        attrValues {c = 3; a = 1; b = 2;}
 257        => [1 2 3]
 258
 259      Type:
 260        attrValues :: AttrSet -> [Any]
 261   */
 262   attrValues = builtins.attrValues or (attrs: attrVals (attrNames attrs) attrs);
 263
 264
 265   /* Given a set of attribute names, return the set of the corresponding
 266      attributes from the given set.
 267
 268      Example:
 269        getAttrs [ "a" "b" ] { a = 1; b = 2; c = 3; }
 270        => { a = 1; b = 2; }
 271
 272      Type:
 273        getAttrs :: [String] -> AttrSet -> AttrSet
 274   */
 275   getAttrs =
 276     # A list of attribute names to get out of `set`
 277     names:
 278     # The set to get the named attributes from
 279     attrs: genAttrs names (name: attrs.${name});
 280
 281   /* Collect each attribute named `attr` from a list of attribute
 282      sets.  Sets that don't contain the named attribute are ignored.
 283
 284      Example:
 285        catAttrs "a" [{a = 1;} {b = 0;} {a = 2;}]
 286        => [1 2]
 287
 288      Type:
 289        catAttrs :: String -> [AttrSet] -> [Any]
 290   */
 291   catAttrs = builtins.catAttrs or
 292     (attr: l: concatLists (map (s: if s ? ${attr} then [s.${attr}] else []) l));
 293
 294
 295   /* Filter an attribute set by removing all attributes for which the
 296      given predicate return false.
 297
 298      Example:
 299        filterAttrs (n: v: n == "foo") { foo = 1; bar = 2; }
 300        => { foo = 1; }
 301
 302      Type:
 303        filterAttrs :: (String -> Any -> Bool) -> AttrSet -> AttrSet
 304   */
 305   filterAttrs =
 306     # Predicate taking an attribute name and an attribute value, which returns `true` to include the attribute, or `false` to exclude the attribute.
 307     pred:
 308     # The attribute set to filter
 309     set:
 310     listToAttrs (concatMap (name: let v = set.${name}; in if pred name v then [(nameValuePair name v)] else []) (attrNames set));
 311
 312
 313   /* Filter an attribute set recursively by removing all attributes for
 314      which the given predicate return false.
 315
 316      Example:
 317        filterAttrsRecursive (n: v: v != null) { foo = { bar = null; }; }
 318        => { foo = {}; }
 319
 320      Type:
 321        filterAttrsRecursive :: (String -> Any -> Bool) -> AttrSet -> AttrSet
 322   */
 323   filterAttrsRecursive =
 324     # Predicate taking an attribute name and an attribute value, which returns `true` to include the attribute, or `false` to exclude the attribute.
 325     pred:
 326     # The attribute set to filter
 327     set:
 328     listToAttrs (
 329       concatMap (name:
 330         let v = set.${name}; in
 331         if pred name v then [
 332           (nameValuePair name (
 333             if isAttrs v then filterAttrsRecursive pred v
 334             else v
 335           ))
 336         ] else []
 337       ) (attrNames set)
 338     );
 339
 340    /*
 341     Like [`lib.lists.foldl'`](#function-library-lib.lists.foldl-prime) but for attribute sets.
 342     Iterates over every name-value pair in the given attribute set.
 343     The result of the callback function is often called `acc` for accumulator. It is passed between callbacks from left to right and the final `acc` is the return value of `foldlAttrs`.
 344
 345     Attention:
 346       There is a completely different function
 347       `lib.foldAttrs`
 348       which has nothing to do with this function, despite the similar name.
 349
 350     Example:
 351       foldlAttrs
 352         (acc: name: value: {
 353           sum = acc.sum + value;
 354           names = acc.names ++ [name];
 355         })
 356         { sum = 0; names = []; }
 357         {
 358           foo = 1;
 359           bar = 10;
 360         }
 361       ->
 362         {
 363           sum = 11;
 364           names = ["bar" "foo"];
 365         }
 366
 367       foldlAttrs
 368         (throw "function not needed")
 369         123
 370         {};
 371       ->
 372         123
 373
 374       foldlAttrs
 375         (acc: _: _: acc)
 376         3
 377         { z = throw "value not needed"; a = throw "value not needed"; };
 378       ->
 379         3
 380
 381       The accumulator doesn't have to be an attrset.
 382       It can be as simple as a number or string.
 383
 384       foldlAttrs
 385         (acc: _: v: acc * 10 + v)
 386         1
 387         { z = 1; a = 2; };
 388       ->
 389         121
 390
 391     Type:
 392       foldlAttrs :: ( a -> String -> b -> a ) -> a -> { ... :: b } -> a
 393   */
 394   foldlAttrs = f: init: set:
 395     foldl'
 396       (acc: name: f acc name set.${name})
 397       init
 398       (attrNames set);
 399
 400   /* Apply fold functions to values grouped by key.
 401
 402      Example:
 403        foldAttrs (item: acc: [item] ++ acc) [] [{ a = 2; } { a = 3; }]
 404        => { a = [ 2 3 ]; }
 405
 406      Type:
 407        foldAttrs :: (Any -> Any -> Any) -> Any -> [AttrSets] -> Any
 408
 409   */
 410   foldAttrs =
 411     # A function, given a value and a collector combines the two.
 412     op:
 413     # The starting value.
 414     nul:
 415     # A list of attribute sets to fold together by key.
 416     list_of_attrs:
 417     foldr (n: a:
 418         foldr (name: o:
 419           o // { ${name} = op n.${name} (a.${name} or nul); }
 420         ) a (attrNames n)
 421     ) {} list_of_attrs;
 422
 423
 424   /* Recursively collect sets that verify a given predicate named `pred`
 425      from the set `attrs`.  The recursion is stopped when the predicate is
 426      verified.
 427
 428      Example:
 429        collect isList { a = { b = ["b"]; }; c = [1]; }
 430        => [["b"] [1]]
 431
 432        collect (x: x ? outPath)
 433           { a = { outPath = "a/"; }; b = { outPath = "b/"; }; }
 434        => [{ outPath = "a/"; } { outPath = "b/"; }]
 435
 436      Type:
 437        collect :: (AttrSet -> Bool) -> AttrSet -> [x]
 438   */
 439   collect =
 440   # Given an attribute's value, determine if recursion should stop.
 441   pred:
 442   # The attribute set to recursively collect.
 443   attrs:
 444     if pred attrs then
 445       [ attrs ]
 446     else if isAttrs attrs then
 447       concatMap (collect pred) (attrValues attrs)
 448     else
 449       [];
 450
 451   /* Return the cartesian product of attribute set value combinations.
 452
 453     Example:
 454       cartesianProductOfSets { a = [ 1 2 ]; b = [ 10 20 ]; }
 455       => [
 456            { a = 1; b = 10; }
 457            { a = 1; b = 20; }
 458            { a = 2; b = 10; }
 459            { a = 2; b = 20; }
 460          ]
 461      Type:
 462        cartesianProductOfSets :: AttrSet -> [AttrSet]
 463   */
 464   cartesianProductOfSets =
 465     # Attribute set with attributes that are lists of values
 466     attrsOfLists:
 467     foldl' (listOfAttrs: attrName:
 468       concatMap (attrs:
 469         map (listValue: attrs // { ${attrName} = listValue; }) attrsOfLists.${attrName}
 470       ) listOfAttrs
 471     ) [{}] (attrNames attrsOfLists);
 472
 473
 474   /* Utility function that creates a `{name, value}` pair as expected by `builtins.listToAttrs`.
 475
 476      Example:
 477        nameValuePair "some" 6
 478        => { name = "some"; value = 6; }
 479
 480      Type:
 481        nameValuePair :: String -> Any -> { name :: String; value :: Any; }
 482   */
 483   nameValuePair =
 484     # Attribute name
 485     name:
 486     # Attribute value
 487     value:
 488     { inherit name value; };
 489
 490
 491   /* Apply a function to each element in an attribute set, creating a new attribute set.
 492
 493      Example:
 494        mapAttrs (name: value: name + "-" + value)
 495           { x = "foo"; y = "bar"; }
 496        => { x = "x-foo"; y = "y-bar"; }
 497
 498      Type:
 499        mapAttrs :: (String -> Any -> Any) -> AttrSet -> AttrSet
 500   */
 501   mapAttrs = builtins.mapAttrs or
 502     (f: set:
 503       listToAttrs (map (attr: { name = attr; value = f attr set.${attr}; }) (attrNames set)));
 504
 505
 506   /* Like `mapAttrs`, but allows the name of each attribute to be
 507      changed in addition to the value.  The applied function should
 508      return both the new name and value as a `nameValuePair`.
 509
 510      Example:
 511        mapAttrs' (name: value: nameValuePair ("foo_" + name) ("bar-" + value))
 512           { x = "a"; y = "b"; }
 513        => { foo_x = "bar-a"; foo_y = "bar-b"; }
 514
 515      Type:
 516        mapAttrs' :: (String -> Any -> { name :: String; value :: Any; }) -> AttrSet -> AttrSet
 517   */
 518   mapAttrs' =
 519     # A function, given an attribute's name and value, returns a new `nameValuePair`.
 520     f:
 521     # Attribute set to map over.
 522     set:
 523     listToAttrs (map (attr: f attr set.${attr}) (attrNames set));
 524
 525
 526   /* Call a function for each attribute in the given set and return
 527      the result in a list.
 528
 529      Example:
 530        mapAttrsToList (name: value: name + value)
 531           { x = "a"; y = "b"; }
 532        => [ "xa" "yb" ]
 533
 534      Type:
 535        mapAttrsToList :: (String -> a -> b) -> AttrSet -> [b]
 536
 537   */
 538   mapAttrsToList =
 539     # A function, given an attribute's name and value, returns a new value.
 540     f:
 541     # Attribute set to map over.
 542     attrs:
 543     map (name: f name attrs.${name}) (attrNames attrs);
 544
 545   /*
 546     Deconstruct an attrset to a list of name-value pairs as expected by [`builtins.listToAttrs`](https://nixos.org/manual/nix/stable/language/builtins.html#builtins-listToAttrs).
 547     Each element of the resulting list is an attribute set with these attributes:
 548     - `name` (string): The name of the attribute
 549     - `value` (any): The value of the attribute
 550
 551     The following is always true:
 552     ```nix
 553     builtins.listToAttrs (attrsToList attrs) == attrs
 554     ```
 555
 556     :::{.warning}
 557     The opposite is not always true. In general expect that
 558     ```nix
 559     attrsToList (builtins.listToAttrs list) != list
 560     ```
 561
 562     This is because the `listToAttrs` removes duplicate names and doesn't preserve the order of the list.
 563     :::
 564
 565     Example:
 566       attrsToList { foo = 1; bar = "asdf"; }
 567       => [ { name = "bar"; value = "asdf"; } { name = "foo"; value = 1; } ]
 568
 569     Type:
 570       attrsToList :: AttrSet -> [ { name :: String; value :: Any; } ]
 571
 572   */
 573   attrsToList = mapAttrsToList nameValuePair;
 574
 575
 576   /* Like `mapAttrs`, except that it recursively applies itself to
 577      the *leaf* attributes of a potentially-nested attribute set:
 578      the second argument of the function will never be an attrset.
 579      Also, the first argument of the argument function is a *list*
 580      of the attribute names that form the path to the leaf attribute.
 581
 582      For a function that gives you control over what counts as a leaf,
 583      see `mapAttrsRecursiveCond`.
 584
 585      Example:
 586        mapAttrsRecursive (path: value: concatStringsSep "-" (path ++ [value]))
 587          { n = { a = "A"; m = { b = "B"; c = "C"; }; }; d = "D"; }
 588        => { n = { a = "n-a-A"; m = { b = "n-m-b-B"; c = "n-m-c-C"; }; }; d = "d-D"; }
 589
 590      Type:
 591        mapAttrsRecursive :: ([String] -> a -> b) -> AttrSet -> AttrSet
 592   */
 593   mapAttrsRecursive =
 594     # A function, given a list of attribute names and a value, returns a new value.
 595     f:
 596     # Set to recursively map over.
 597     set:
 598     mapAttrsRecursiveCond (as: true) f set;
 599
 600
 601   /* Like `mapAttrsRecursive`, but it takes an additional predicate
 602      function that tells it whether to recurse into an attribute
 603      set.  If it returns false, `mapAttrsRecursiveCond` does not
 604      recurse, but does apply the map function.  If it returns true, it
 605      does recurse, and does not apply the map function.
 606
 607      Example:
 608        # To prevent recursing into derivations (which are attribute
 609        # sets with the attribute "type" equal to "derivation"):
 610        mapAttrsRecursiveCond
 611          (as: !(as ? "type" && as.type == "derivation"))
 612          (x: ... do something ...)
 613          attrs
 614
 615      Type:
 616        mapAttrsRecursiveCond :: (AttrSet -> Bool) -> ([String] -> a -> b) -> AttrSet -> AttrSet
 617   */
 618   mapAttrsRecursiveCond =
 619     # A function, given the attribute set the recursion is currently at, determine if to recurse deeper into that attribute set.
 620     cond:
 621     # A function, given a list of attribute names and a value, returns a new value.
 622     f:
 623     # Attribute set to recursively map over.
 624     set:
 625     let
 626       recurse = path:
 627         let
 628           g =
 629             name: value:
 630             if isAttrs value && cond value
 631               then recurse (path ++ [name]) value
 632               else f (path ++ [name]) value;
 633         in mapAttrs g;
 634     in recurse [] set;
 635
 636
 637   /* Generate an attribute set by mapping a function over a list of
 638      attribute names.
 639
 640      Example:
 641        genAttrs [ "foo" "bar" ] (name: "x_" + name)
 642        => { foo = "x_foo"; bar = "x_bar"; }
 643
 644      Type:
 645        genAttrs :: [ String ] -> (String -> Any) -> AttrSet
 646   */
 647   genAttrs =
 648     # Names of values in the resulting attribute set.
 649     names:
 650     # A function, given the name of the attribute, returns the attribute's value.
 651     f:
 652     listToAttrs (map (n: nameValuePair n (f n)) names);
 653
 654
 655   /* Check whether the argument is a derivation. Any set with
 656      `{ type = "derivation"; }` counts as a derivation.
 657
 658      Example:
 659        nixpkgs = import <nixpkgs> {}
 660        isDerivation nixpkgs.ruby
 661        => true
 662        isDerivation "foobar"
 663        => false
 664
 665      Type:
 666        isDerivation :: Any -> Bool
 667   */
 668   isDerivation =
 669     # Value to check.
 670     value: value.type or null == "derivation";
 671
 672    /* Converts a store path to a fake derivation.
 673
 674       Type:
 675         toDerivation :: Path -> Derivation
 676    */
 677    toDerivation =
 678      # A store path to convert to a derivation.
 679      path:
 680      let
 681        path' = builtins.storePath path;
 682        res =
 683          { type = "derivation";
 684            name = sanitizeDerivationName (builtins.substring 33 (-1) (baseNameOf path'));
 685            outPath = path';
 686            outputs = [ "out" ];
 687            out = res;
 688            outputName = "out";
 689          };
 690     in res;
 691
 692
 693   /* If `cond` is true, return the attribute set `as`,
 694      otherwise an empty attribute set.
 695
 696      Example:
 697        optionalAttrs (true) { my = "set"; }
 698        => { my = "set"; }
 699        optionalAttrs (false) { my = "set"; }
 700        => { }
 701
 702      Type:
 703        optionalAttrs :: Bool -> AttrSet -> AttrSet
 704   */
 705   optionalAttrs =
 706     # Condition under which the `as` attribute set is returned.
 707     cond:
 708     # The attribute set to return if `cond` is `true`.
 709     as:
 710     if cond then as else {};
 711
 712
 713   /* Merge sets of attributes and use the function `f` to merge attributes
 714      values.
 715
 716      Example:
 717        zipAttrsWithNames ["a"] (name: vs: vs) [{a = "x";} {a = "y"; b = "z";}]
 718        => { a = ["x" "y"]; }
 719
 720      Type:
 721        zipAttrsWithNames :: [ String ] -> (String -> [ Any ] -> Any) -> [ AttrSet ] -> AttrSet
 722   */
 723   zipAttrsWithNames =
 724     # List of attribute names to zip.
 725     names:
 726     # A function, accepts an attribute name, all the values, and returns a combined value.
 727     f:
 728     # List of values from the list of attribute sets.
 729     sets:
 730     listToAttrs (map (name: {
 731       inherit name;
 732       value = f name (catAttrs name sets);
 733     }) names);
 734
 735
 736   /* Merge sets of attributes and use the function f to merge attribute values.
 737      Like `lib.attrsets.zipAttrsWithNames` with all key names are passed for `names`.
 738
 739      Implementation note: Common names appear multiple times in the list of
 740      names, hopefully this does not affect the system because the maximal
 741      laziness avoid computing twice the same expression and `listToAttrs` does
 742      not care about duplicated attribute names.
 743
 744      Example:
 745        zipAttrsWith (name: values: values) [{a = "x";} {a = "y"; b = "z";}]
 746        => { a = ["x" "y"]; b = ["z"]; }
 747
 748      Type:
 749        zipAttrsWith :: (String -> [ Any ] -> Any) -> [ AttrSet ] -> AttrSet
 750   */
 751   zipAttrsWith =
 752     builtins.zipAttrsWith or (f: sets: zipAttrsWithNames (concatMap attrNames sets) f sets);
 753
 754
 755   /* Merge sets of attributes and combine each attribute value in to a list.
 756
 757      Like `lib.attrsets.zipAttrsWith` with `(name: values: values)` as the function.
 758
 759      Example:
 760        zipAttrs [{a = "x";} {a = "y"; b = "z";}]
 761        => { a = ["x" "y"]; b = ["z"]; }
 762
 763      Type:
 764        zipAttrs :: [ AttrSet ] -> AttrSet
 765   */
 766   zipAttrs =
 767     # List of attribute sets to zip together.
 768     sets:
 769     zipAttrsWith (name: values: values) sets;
 770
 771   /*
 772     Merge a list of attribute sets together using the `//` operator.
 773     In case of duplicate attributes, values from later list elements take precedence over earlier ones.
 774     The result is the same as `foldl mergeAttrs { }`, but the performance is better for large inputs.
 775     For n list elements, each with an attribute set containing m unique attributes, the complexity of this operation is O(nm log n).
 776
 777     Type:
 778       mergeAttrsList :: [ Attrs ] -> Attrs
 779
 780     Example:
 781       mergeAttrsList [ { a = 0; b = 1; } { c = 2; d = 3; } ]
 782       => { a = 0; b = 1; c = 2; d = 3; }
 783       mergeAttrsList [ { a = 0; } { a = 1; } ]
 784       => { a = 1; }
 785   */
 786   mergeAttrsList = list:
 787     let
 788       # `binaryMerge start end` merges the elements at indices `index` of `list` such that `start <= index < end`
 789       # Type: Int -> Int -> Attrs
 790       binaryMerge = start: end:
 791         # assert start < end; # Invariant
 792         if end - start >= 2 then
 793           # If there's at least 2 elements, split the range in two, recurse on each part and merge the result
 794           # The invariant is satisfied because each half will have at least 1 element
 795           binaryMerge start (start + (end - start) / 2)
 796           // binaryMerge (start + (end - start) / 2) end
 797         else
 798           # Otherwise there will be exactly 1 element due to the invariant, in which case we just return it directly
 799           elemAt list start;
 800     in
 801     if list == [ ] then
 802       # Calling binaryMerge as below would not satisfy its invariant
 803       { }
 804     else
 805       binaryMerge 0 (length list);
 806
 807
 808   /* Does the same as the update operator '//' except that attributes are
 809      merged until the given predicate is verified.  The predicate should
 810      accept 3 arguments which are the path to reach the attribute, a part of
 811      the first attribute set and a part of the second attribute set.  When
 812      the predicate is satisfied, the value of the first attribute set is
 813      replaced by the value of the second attribute set.
 814
 815      Example:
 816        recursiveUpdateUntil (path: l: r: path == ["foo"]) {
 817          # first attribute set
 818          foo.bar = 1;
 819          foo.baz = 2;
 820          bar = 3;
 821        } {
 822          #second attribute set
 823          foo.bar = 1;
 824          foo.quz = 2;
 825          baz = 4;
 826        }
 827
 828        => {
 829          foo.bar = 1; # 'foo.*' from the second set
 830          foo.quz = 2; #
 831          bar = 3;     # 'bar' from the first set
 832          baz = 4;     # 'baz' from the second set
 833        }
 834
 835      Type:
 836        recursiveUpdateUntil :: ( [ String ] -> AttrSet -> AttrSet -> Bool ) -> AttrSet -> AttrSet -> AttrSet
 837   */
 838   recursiveUpdateUntil =
 839     # Predicate, taking the path to the current attribute as a list of strings for attribute names, and the two values at that path from the original arguments.
 840     pred:
 841     # Left attribute set of the merge.
 842     lhs:
 843     # Right attribute set of the merge.
 844     rhs:
 845     let f = attrPath:
 846       zipAttrsWith (n: values:
 847         let here = attrPath ++ [n]; in
 848         if length values == 1
 849         || pred here (elemAt values 1) (head values) then
 850           head values
 851         else
 852           f here values
 853       );
 854     in f [] [rhs lhs];
 855
 856
 857   /* A recursive variant of the update operator ‘//’.  The recursion
 858      stops when one of the attribute values is not an attribute set,
 859      in which case the right hand side value takes precedence over the
 860      left hand side value.
 861
 862      Example:
 863        recursiveUpdate {
 864          boot.loader.grub.enable = true;
 865          boot.loader.grub.device = "/dev/hda";
 866        } {
 867          boot.loader.grub.device = "";
 868        }
 869
 870        returns: {
 871          boot.loader.grub.enable = true;
 872          boot.loader.grub.device = "";
 873        }
 874
 875      Type:
 876        recursiveUpdate :: AttrSet -> AttrSet -> AttrSet
 877   */
 878   recursiveUpdate =
 879     # Left attribute set of the merge.
 880     lhs:
 881     # Right attribute set of the merge.
 882     rhs:
 883     recursiveUpdateUntil (path: lhs: rhs: !(isAttrs lhs && isAttrs rhs)) lhs rhs;
 884
 885
 886   /* Returns true if the pattern is contained in the set. False otherwise.
 887
 888      Example:
 889        matchAttrs { cpu = {}; } { cpu = { bits = 64; }; }
 890        => true
 891
 892      Type:
 893        matchAttrs :: AttrSet -> AttrSet -> Bool
 894   */
 895   matchAttrs =
 896     # Attribute set structure to match
 897     pattern:
 898     # Attribute set to find patterns in
 899     attrs:
 900     assert isAttrs pattern;
 901     all id (attrValues (zipAttrsWithNames (attrNames pattern) (n: values:
 902       let pat = head values; val = elemAt values 1; in
 903       if length values == 1 then false
 904       else if isAttrs pat then isAttrs val && matchAttrs pat val
 905       else pat == val
 906     ) [pattern attrs]));
 907
 908
 909   /* Override only the attributes that are already present in the old set
 910     useful for deep-overriding.
 911
 912     Example:
 913       overrideExisting {} { a = 1; }
 914       => {}
 915       overrideExisting { b = 2; } { a = 1; }
 916       => { b = 2; }
 917       overrideExisting { a = 3; b = 2; } { a = 1; }
 918       => { a = 1; b = 2; }
 919
 920     Type:
 921       overrideExisting :: AttrSet -> AttrSet -> AttrSet
 922   */
 923   overrideExisting =
 924     # Original attribute set
 925     old:
 926     # Attribute set with attributes to override in `old`.
 927     new:
 928     mapAttrs (name: value: new.${name} or value) old;
 929
 930
 931   /* Turns a list of strings into a human-readable description of those
 932     strings represented as an attribute path. The result of this function is
 933     not intended to be machine-readable.
 934     Create a new attribute set with `value` set at the nested attribute location specified in `attrPath`.
 935
 936     Example:
 937       showAttrPath [ "foo" "10" "bar" ]
 938       => "foo.\"10\".bar"
 939       showAttrPath []
 940       => "<root attribute path>"
 941
 942     Type:
 943       showAttrPath :: [String] -> String
 944   */
 945   showAttrPath =
 946     # Attribute path to render to a string
 947     path:
 948     if path == [] then "<root attribute path>"
 949     else concatMapStringsSep "." escapeNixIdentifier path;
 950
 951
 952   /* Get a package output.
 953      If no output is found, fallback to `.out` and then to the default.
 954
 955      Example:
 956        getOutput "dev" pkgs.openssl
 957        => "/nix/store/9rz8gxhzf8sw4kf2j2f1grr49w8zx5vj-openssl-1.0.1r-dev"
 958
 959      Type:
 960        getOutput :: String -> Derivation -> String
 961   */
 962   getOutput = output: pkg:
 963     if ! pkg ? outputSpecified || ! pkg.outputSpecified
 964       then pkg.${output} or pkg.out or pkg
 965       else pkg;
 966
 967   /* Get a package's `bin` output.
 968      If the output does not exist, fallback to `.out` and then to the default.
 969
 970      Example:
 971        getBin pkgs.openssl
 972        => "/nix/store/9rz8gxhzf8sw4kf2j2f1grr49w8zx5vj-openssl-1.0.1r"
 973
 974      Type:
 975        getBin :: Derivation -> String
 976   */
 977   getBin = getOutput "bin";
 978
 979
 980   /* Get a package's `lib` output.
 981      If the output does not exist, fallback to `.out` and then to the default.
 982
 983      Example:
 984        getLib pkgs.openssl
 985        => "/nix/store/9rz8gxhzf8sw4kf2j2f1grr49w8zx5vj-openssl-1.0.1r-lib"
 986
 987      Type:
 988        getLib :: Derivation -> String
 989   */
 990   getLib = getOutput "lib";
 991
 992
 993   /* Get a package's `dev` output.
 994      If the output does not exist, fallback to `.out` and then to the default.
 995
 996      Example:
 997        getDev pkgs.openssl
 998        => "/nix/store/9rz8gxhzf8sw4kf2j2f1grr49w8zx5vj-openssl-1.0.1r-dev"
 999
1000      Type:
1001        getDev :: Derivation -> String
1002   */
1003   getDev = getOutput "dev";
1004
1005
1006   /* Get a package's `man` output.
1007      If the output does not exist, fallback to `.out` and then to the default.
1008
1009      Example:
1010        getMan pkgs.openssl
1011        => "/nix/store/9rz8gxhzf8sw4kf2j2f1grr49w8zx5vj-openssl-1.0.1r-man"
1012
1013      Type:
1014        getMan :: Derivation -> String
1015   */
1016   getMan = getOutput "man";
1017
1018   /* Pick the outputs of packages to place in `buildInputs`
1019
1020    Type: chooseDevOutputs :: [Derivation] -> [String]
1021
1022   */
1023   chooseDevOutputs =
1024     # List of packages to pick `dev` outputs from
1025     drvs:
1026     builtins.map getDev drvs;
1027
1028   /* Make various Nix tools consider the contents of the resulting
1029      attribute set when looking for what to build, find, etc.
1030
1031      This function only affects a single attribute set; it does not
1032      apply itself recursively for nested attribute sets.
1033
1034      Example:
1035        { pkgs ? import <nixpkgs> {} }:
1036        {
1037          myTools = pkgs.lib.recurseIntoAttrs {
1038            inherit (pkgs) hello figlet;
1039          };
1040        }
1041
1042      Type:
1043        recurseIntoAttrs :: AttrSet -> AttrSet
1044
1045    */
1046   recurseIntoAttrs =
1047     # An attribute set to scan for derivations.
1048     attrs:
1049     attrs // { recurseForDerivations = true; };
1050
1051   /* Undo the effect of recurseIntoAttrs.
1052
1053      Type:
1054        dontRecurseIntoAttrs :: AttrSet -> AttrSet
1055    */
1056   dontRecurseIntoAttrs =
1057     # An attribute set to not scan for derivations.
1058     attrs:
1059     attrs // { recurseForDerivations = false; };
1060
1061   /* `unionOfDisjoint x y` is equal to `x // y // z` where the
1062      attrnames in `z` are the intersection of the attrnames in `x` and
1063      `y`, and all values `assert` with an error message.  This
1064       operator is commutative, unlike (//).
1065
1066      Type: unionOfDisjoint :: AttrSet -> AttrSet -> AttrSet
1067   */
1068   unionOfDisjoint = x: y:
1069     let
1070       intersection = builtins.intersectAttrs x y;
1071       collisions = lib.concatStringsSep " " (builtins.attrNames intersection);
1072       mask = builtins.mapAttrs (name: value: builtins.throw
1073         "unionOfDisjoint: collision on ${name}; complete list: ${collisions}")
1074         intersection;
1075     in
1076       (x // y) // mask;
1077
1078   # DEPRECATED
1079   zipWithNames = zipAttrsWithNames;
1080
1081   # DEPRECATED
1082   zip = builtins.trace
1083     "lib.zip is deprecated, use lib.zipAttrsWith instead" zipAttrsWith;
1084 }