{
  "version": 3,
  "sources": ["../../src/diff/merge.ts"],
  "sourcesContent": ["import type { Difference } from '@/diff/diff'\nimport { Trie } from '@/diff/trie'\nimport { isArrayEqual, isKeyCollisions, mergeObjects } from '@/diff/utils'\n\n/**\n * Merges two sets of differences from the same document and resolves conflicts.\n * This function combines changes from two diff lists while handling potential conflicts\n * that arise when both diffs modify the same paths. It uses a trie data structure for\n * efficient path matching and conflict detection.\n *\n * @param diff1 - First list of differences\n * @param diff2 - Second list of differences\n * @returns Object containing:\n *   - diffs: Combined list of non-conflicting differences\n *   - conflicts: Array of conflicting difference pairs that need manual resolution\n *\n * @example\n * // Merge two sets of changes to a user profile\n * const diff1 = [\n *   { path: ['name'], changes: 'John', type: 'update' },\n *   { path: ['age'], changes: 30, type: 'add' }\n * ]\n * const diff2 = [\n *   { path: ['name'], changes: 'Johnny', type: 'update' },\n *   { path: ['address'], changes: { city: 'NY' }, type: 'add' }\n * ]\n * const { diffs, conflicts } = merge(diff1, diff2)\n * // Returns:\n * // {\n * //   diffs: [\n * //     { path: ['age'], changes: 30, type: 'add' },\n * //     { path: ['address'], changes: { city: 'NY' }, type: 'add' }\n * //   ],\n * //   conflicts: [\n * //     [\n * //       [{ path: ['name'], changes: 'John', type: 'update' }],\n * //       [{ path: ['name'], changes: 'Johnny', type: 'update' }]\n * //     ]\n * //   ]\n * // }\n */\nexport const merge = <T>(diff1: Difference<T>[], diff2: Difference<T>[]) => {\n  // Here we need to use a trie to optimize searching for a prefix\n  // With the naive approach time complexity of the algorithm would be\n  //                         O(n * m)\n  //                           ^   ^\n  // n is the length off diff1 |   | m length of diff2\n  //\n  // Assuming that the maximum depth of the nested objects would be constant lets say 0 <= D <= 100\n  // we try to optimize for that using the tire data structure.\n  // So the new time complexity would be O(n * D) where D is the maximum depth of the nested object\n  const trie = new Trie<{ index: number; changes: Difference<T> }>()\n\n  // Create the trie\n  for (const [index, diff] of diff1.entries()) {\n    trie.addPath(diff.path, { index, changes: diff })\n  }\n\n  const skipDiff1 = new Set<number>()\n  const skipDiff2 = new Set<number>()\n\n  // Keep related conflicts together for easy A, B pick conflict resolution\n  // map key is going to be conflicting index of first diff list where the diff will be\n  // a delete operation or an add/update operation with a one to many conflicts\n  const conflictsMap1 = new Map<number, [Difference<T>[], Difference<T>[]]>()\n  // map key will be the index from the second diff list where the diff will be\n  // a delete operation with one to many conflicts\n  const conflictsMap2 = new Map<number, [Difference<T>[], Difference<T>[]]>()\n\n  for (const [index, diff] of diff2.entries()) {\n    trie.findMatch(diff.path, (value) => {\n      if (diff.type === 'delete') {\n        if (value.changes.type === 'delete') {\n          // Keep the highest depth delete operation and skip the other\n          if (value.changes.path.length > diff.path.length) {\n            skipDiff1.add(value.index)\n          } else {\n            skipDiff2.add(value.index)\n          }\n        } else {\n          // Take care of updates/add on the same path (we are sure they will be on the\n          // same path since the change comes from the same document)\n          skipDiff1.add(value.index)\n          skipDiff2.add(index)\n\n          const conflictEntry = conflictsMap2.get(index)\n\n          if (conflictEntry !== undefined) {\n            conflictEntry[0].push(value.changes)\n          } else {\n            conflictsMap2.set(index, [[value.changes], [diff]])\n          }\n        }\n      }\n\n      if (diff.type === 'add' || diff.type === 'update') {\n        // For add -> add / update -> update operation we try to first see if we can merge this operations\n        if (\n          isArrayEqual(diff.path, value.changes.path) &&\n          value.changes.type !== 'delete' &&\n          !isKeyCollisions(diff.changes, value.changes.changes)\n        ) {\n          skipDiff1.add(value.index)\n          // For non primitive values we merge object keys into diff2\n          if (typeof diff.changes === 'object') {\n            mergeObjects(diff.changes, value.changes.changes)\n          }\n          return\n        }\n\n        // add/update -> delete operations always resolve in conflicts\n        skipDiff1.add(value.index)\n        skipDiff2.add(index)\n\n        const conflictEntry = conflictsMap1.get(value.index)\n\n        if (conflictEntry !== undefined) {\n          conflictEntry[1].push(diff)\n        } else {\n          conflictsMap1.set(value.index, [[value.changes], [diff]])\n        }\n      }\n    })\n  }\n\n  const conflicts: [Difference<T>[], Difference<T>[]][] = [...conflictsMap1.values(), ...conflictsMap2.values()]\n\n  // Filter all changes that should be skipped because of conflicts\n  // or auto conflict resolution\n  const diffs: Difference<T>[] = [\n    ...diff1.filter((_, index) => !skipDiff1.has(index)),\n    ...diff2.filter((_, index) => !skipDiff2.has(index)),\n  ]\n\n  return { diffs, conflicts }\n}\n"],
  "mappings": "AACA,SAAS,YAAY;AACrB,SAAS,cAAc,iBAAiB,oBAAoB;AAuCrD,MAAM,QAAQ,CAAI,OAAwB,UAA2B;AAU1E,QAAM,OAAO,IAAI,KAAgD;AAGjE,aAAW,CAAC,OAAO,IAAI,KAAK,MAAM,QAAQ,GAAG;AAC3C,SAAK,QAAQ,KAAK,MAAM,EAAE,OAAO,SAAS,KAAK,CAAC;AAAA,EAClD;AAEA,QAAM,YAAY,oBAAI,IAAY;AAClC,QAAM,YAAY,oBAAI,IAAY;AAKlC,QAAM,gBAAgB,oBAAI,IAAgD;AAG1E,QAAM,gBAAgB,oBAAI,IAAgD;AAE1E,aAAW,CAAC,OAAO,IAAI,KAAK,MAAM,QAAQ,GAAG;AAC3C,SAAK,UAAU,KAAK,MAAM,CAAC,UAAU;AACnC,UAAI,KAAK,SAAS,UAAU;AAC1B,YAAI,MAAM,QAAQ,SAAS,UAAU;AAEnC,cAAI,MAAM,QAAQ,KAAK,SAAS,KAAK,KAAK,QAAQ;AAChD,sBAAU,IAAI,MAAM,KAAK;AAAA,UAC3B,OAAO;AACL,sBAAU,IAAI,MAAM,KAAK;AAAA,UAC3B;AAAA,QACF,OAAO;AAGL,oBAAU,IAAI,MAAM,KAAK;AACzB,oBAAU,IAAI,KAAK;AAEnB,gBAAM,gBAAgB,cAAc,IAAI,KAAK;AAE7C,cAAI,kBAAkB,QAAW;AAC/B,0BAAc,CAAC,EAAE,KAAK,MAAM,OAAO;AAAA,UACrC,OAAO;AACL,0BAAc,IAAI,OAAO,CAAC,CAAC,MAAM,OAAO,GAAG,CAAC,IAAI,CAAC,CAAC;AAAA,UACpD;AAAA,QACF;AAAA,MACF;AAEA,UAAI,KAAK,SAAS,SAAS,KAAK,SAAS,UAAU;AAEjD,YACE,aAAa,KAAK,MAAM,MAAM,QAAQ,IAAI,KAC1C,MAAM,QAAQ,SAAS,YACvB,CAAC,gBAAgB,KAAK,SAAS,MAAM,QAAQ,OAAO,GACpD;AACA,oBAAU,IAAI,MAAM,KAAK;AAEzB,cAAI,OAAO,KAAK,YAAY,UAAU;AACpC,yBAAa,KAAK,SAAS,MAAM,QAAQ,OAAO;AAAA,UAClD;AACA;AAAA,QACF;AAGA,kBAAU,IAAI,MAAM,KAAK;AACzB,kBAAU,IAAI,KAAK;AAEnB,cAAM,gBAAgB,cAAc,IAAI,MAAM,KAAK;AAEnD,YAAI,kBAAkB,QAAW;AAC/B,wBAAc,CAAC,EAAE,KAAK,IAAI;AAAA,QAC5B,OAAO;AACL,wBAAc,IAAI,MAAM,OAAO,CAAC,CAAC,MAAM,OAAO,GAAG,CAAC,IAAI,CAAC,CAAC;AAAA,QAC1D;AAAA,MACF;AAAA,IACF,CAAC;AAAA,EACH;AAEA,QAAM,YAAkD,CAAC,GAAG,cAAc,OAAO,GAAG,GAAG,cAAc,OAAO,CAAC;AAI7G,QAAM,QAAyB;AAAA,IAC7B,GAAG,MAAM,OAAO,CAAC,GAAG,UAAU,CAAC,UAAU,IAAI,KAAK,CAAC;AAAA,IACnD,GAAG,MAAM,OAAO,CAAC,GAAG,UAAU,CAAC,UAAU,IAAI,KAAK,CAAC;AAAA,EACrD;AAEA,SAAO,EAAE,OAAO,UAAU;AAC5B;",
  "names": []
}