{ lib, depot, ... }:
/*
  JSON Merge-Patch for nix
  Spec: https://tools.ietf.org/html/rfc7396

  An algorithm for changing and removing fields in nested objects.

  For example, given the following original document:

  {
  a = "b";
  c = {
      d = "e";
      f = "g";
  }
  }

  Changing the value of `a` and removing `f` can be achieved by merging the patch

  {
  a = "z";
  c.f = null;
  }

  which results in

  {
  a = "z";
  c = {
      d = "e";
  };
  }

  Pseudo-code:
  define MergePatch(Target, Patch):
      if Patch is an Object:
        if Target is not an Object:
          Target = {} # Ignore the contents and set it to an empty Object
        for each Name/Value pair in Patch:
          if Value is null:
            if Name exists in Target:
              remove the Name/Value pair from Target
          else:
            Target[Name] = MergePatch(Target[Name], Value)
        return Target
      else:
        return Patch
*/

let
  foldlAttrs = op: init: attrs:
    lib.foldl' op init
      (lib.mapAttrsToList lib.nameValuePair attrs);

  mergePatch = target: patch:
    if lib.isAttrs patch
    then
      let target' = if lib.isAttrs target then target else { };
      in foldlAttrs
        (acc: patchEl:
          if patchEl.value == null
          then removeAttrs acc [ patchEl.name ]
          else acc // {
            ${patchEl.name} =
              mergePatch
                (acc.${patchEl.name} or "unnused")
                patchEl.value;
          })
        target'
        patch
    else patch;

  inherit (depot.nix.runTestsuite)
    runTestsuite
    it
    assertEq
    ;

  tests =
    let
      # example target from the RFC
      testTarget = {
        a = "b";
        c = {
          d = "e";
          f = "g";
        };
      };
      # example patch from the RFC
      testPatch = {
        a = "z";
        c.f = null;
      };
      emptyPatch = it "the empty patch returns the original target" [
        (assertEq "id"
          (mergePatch testTarget { })
          testTarget)
      ];
      nonAttrs = it "one side is a non-attrset value" [
        (assertEq "target is a value means the value is replaced by the patch"
          (mergePatch 42 testPatch)
          (mergePatch { } testPatch))
        (assertEq "patch is a value means it replaces target alltogether"
          (mergePatch testTarget 42)
          42)
      ];
      rfcExamples = it "the examples from the RFC" [
        (assertEq "a subset is deleted and overwritten"
          (mergePatch testTarget testPatch)
          {
            a = "z";
            c = {
              d = "e";
            };
          })
        (assertEq "a more complicated example from the example section"
          (mergePatch
            {
              title = "Goodbye!";
              author = {
                givenName = "John";
                familyName = "Doe";
              };
              tags = [ "example" "sample" ];
              content = "This will be unchanged";
            }
            {
              title = "Hello!";
              phoneNumber = "+01-123-456-7890";
              author.familyName = null;
              tags = [ "example" ];
            })
          {
            title = "Hello!";
            phoneNumber = "+01-123-456-7890";
            author = {
              givenName = "John";
            };
            tags = [ "example" ];
            content = "This will be unchanged";
          })
      ];

      rfcTests =
        let
          r = index: target: patch: res:
            (assertEq "test number ${toString index}"
              (mergePatch target patch)
              res);
        in
        it "the test suite from the RFC" [
          (r 1 { "a" = "b"; } { "a" = "c"; } { "a" = "c"; })
          (r 2 { "a" = "b"; } { "b" = "c"; } { "a" = "b"; "b" = "c"; })
          (r 3 { "a" = "b"; } { "a" = null; } { })
          (r 4 { "a" = "b"; "b" = "c"; }
            { "a" = null; }
            { "b" = "c"; })
          (r 5 { "a" = [ "b" ]; } { "a" = "c"; } { "a" = "c"; })
          (r 6 { "a" = "c"; } { "a" = [ "b" ]; } { "a" = [ "b" ]; })
          (r 7 { "a" = { "b" = "c"; }; }
            { "a" = { "b" = "d"; "c" = null; }; }
            { "a" = { "b" = "d"; }; })
          (r 8 { "a" = [{ "b" = "c"; }]; }
            { "a" = [ 1 ]; }
            { "a" = [ 1 ]; })
          (r 9 [ "a" "b" ] [ "c" "d" ] [ "c" "d" ])
          (r 10 { "a" = "b"; } [ "c" ] [ "c" ])
          (r 11 { "a" = "foo"; } null null)
          (r 12 { "a" = "foo"; } "bar" "bar")
          (r 13 { "e" = null; } { "a" = 1; } { "e" = null; "a" = 1; })
          (r 14 [ 1 2 ]
            { "a" = "b"; "c" = null; }
            { "a" = "b"; })
          (r 15 { }
            { "a" = { "bb" = { "ccc" = null; }; }; }
            { "a" = { "bb" = { }; }; })
        ];

    in
    runTestsuite "mergePatch" [
      emptyPatch
      nonAttrs
      rfcExamples
      rfcTests
    ];

in
{
  __functor = _: mergePatch;

  inherit tests;
}