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;
  }
}