sclass JsonDiff {

  srecord DiffResult(O a, O b) {}

  // key made from getListKey

  srecord GatheredKey(S key, O value) {

    O get() { ret value; }

  }

  sclass Removed > DiffResult { *(O *a, O *b) {} } // b missing

  sclass Added > DiffResult { *(O *a, O *b) {} } // a missing

  sclass DifferentType > DiffResult { *(O *a, O *b) {} }

  sclass Different > DiffResult { *(O *a, O *b) {} } // same type, generally different

  // paths are usually L<String>, but IDs gathered by getListKey can also be in there

  IF1<L, S> getListKey; // key field for diffing lists. argument is path

  // returns null if identical

  O diff(S json1, S json2) {

    O o1 = jsonDecode(json1), o2 = jsonDecode(json2);

    ret diff(json1, json2, new L);

  }

  // a, b = decoded JSON

  O diff(O a, O b) {

    ret diff(a, b, new L);

  }

  // a, b = decoded JSON

  O diff(O a, O b, L path) {

    if (eq(a, b)) null;

    if (a == null) ret new Added(a, b);

    if (b == null) ret new Removed(a, b);

    if (a.getClass() != b.getClass()) ret new DifferentType(a, b);

    // from here on, we know that a and b have the same type

    if (a cast Map)

      ret diffMaps(a, (Map) b, path);

    if (a cast L)

      try object diffLists(a, (L) b, path);

    ret new Different(a, b);

  }

  O diffMaps(Map a, Map b, L path) {

    ret withoutNullValues

    (mapKeyAndFunction_lhm(concatAsOrderedSet(keys(a), keys(b)),

      key -> {

        temp tempAddToList(path, key);

        ret diff(a.get(key), b/Map.get(key), path);

      }));

  }

  O diffLists(L a, L b, L path) {

    S key = callF(getListKey, path);

    if (key == null) null;

    Map mapA = gatherListElements(a, key, path);

    if (mapA == null) null;

    Map mapB = gatherListElements(b, key, path);

    if (mapB == null) null;

    ret diffMaps(mapA, mapB, path);

  }

  Map gatherListElements(L l, S key, L path) {

    new LinkedHashMap mapOut;

    for (O x : l) {

      if (!x instanceof Map)

        ret null with print("Can't get object key " + key + " of non-map (path: " + path + ")");

      mapOut.put(new GatheredKey(key, x/Map.get(key)), x);

    }

    ret mapOut;

  }

}