Merge branch 'nixos-unstable' of https://github.com/NixOS/nixpkgs

Conflicts:
	nixpkgs/pkgs/applications/window-managers/sway/default.nix
	nixpkgs/pkgs/build-support/go/module.nix
	nixpkgs/pkgs/build-support/rust/build-rust-package/default.nix
	nixpkgs/pkgs/development/libraries/mesa/default.nix
	nixpkgs/pkgs/servers/dict/dictd-db.nix

Link: https://gitlab.freedesktop.org/xkeyboard-config/xkeyboard-config/-/issues/391

1 files changed, 37 insertions, 1 deletions

diff --git a/nixpkgs/lib/attrsets.nix b/nixpkgs/lib/attrsets.nix
index 73b71f68db79..77e36d3271f7 100644
--- a/nixpkgs/lib/attrsets.nix
+++ b/nixpkgs/lib/attrsets.nix
@@ -3,7 +3,7 @@
 
 let
   inherit (builtins) head tail length;
-  inherit (lib.trivial) flip id mergeAttrs pipe;
+  inherit (lib.trivial) id mergeAttrs;
   inherit (lib.strings) concatStringsSep concatMapStringsSep escapeNixIdentifier sanitizeDerivationName;
   inherit (lib.lists) foldr foldl' concatMap concatLists elemAt all partition groupBy take foldl;
 in
@@ -738,6 +738,42 @@ rec {
     sets:
     zipAttrsWith (name: values: values) sets;
 
+  /*
+    Merge a list of attribute sets together using the `//` operator.
+    In case of duplicate attributes, values from later list elements take precedence over earlier ones.
+    The result is the same as `foldl mergeAttrs { }`, but the performance is better for large inputs.
+    For n list elements, each with an attribute set containing m unique attributes, the complexity of this operation is O(nm log n).
+
+    Type:
+      mergeAttrsList :: [ Attrs ] -> Attrs
+
+    Example:
+      mergeAttrsList [ { a = 0; b = 1; } { c = 2; d = 3; } ]
+      => { a = 0; b = 1; c = 2; d = 3; }
+      mergeAttrsList [ { a = 0; } { a = 1; } ]
+      => { a = 1; }
+  */
+  mergeAttrsList = list:
+    let
+      # `binaryMerge start end` merges the elements at indices `index` of `list` such that `start <= index < end`
+      # Type: Int -> Int -> Attrs
+      binaryMerge = start: end:
+        # assert start < end; # Invariant
+        if end - start >= 2 then
+          # If there's at least 2 elements, split the range in two, recurse on each part and merge the result
+          # The invariant is satisfied because each half will have at least 1 element
+          binaryMerge start (start + (end - start) / 2)
+          // binaryMerge (start + (end - start) / 2) end
+        else
+          # Otherwise there will be exactly 1 element due to the invariant, in which case we just return it directly
+          elemAt list start;
+    in
+    if list == [ ] then
+      # Calling binaryMerge as below would not satisfy its invariant
+      { }
+    else
+      binaryMerge 0 (length list);
+
 
   /* Does the same as the update operator '//' except that attributes are
      merged until the given predicate is verified.  The predicate should