3-way merge

[uiteoi]

This is a feature request.

Given a common ancestor and 2 sets of patches, provide a merged document that may include conflicts to resolve manually.

This would be useful to allow two or more users collaborate on the edition of a document, implementing an equivalent of git merge.

It is assumed that the most recent common ancestor is know and provided as a parameter:

JsDiff.merge( commonAncestor, x_patches, y_patches [, options] )

Where x_patches and y_patches are Arrays of patches for the x and y branches from the common ancestor,

Options may be used to provide a manual merge patterns which could default to:

mergePattern: [ "<<<<<<< x", "=======", ">>>>>>> y" ]

For the algorithm, see https://www.quora.com/How-does-Git-merge-work.

[gonzofish]

This was implemented but not made part of the top-level API f94da90

[goodmind]

@gonzofish how to write it to file like git does?

[gonzofish]

sorry @goodmind, I don't remember, I haven't used this library in over a year...sorry I cannot be more help

[goodmind]

@kpdecker

[doug65536]

I have done it, but I found merge misbehaving bug Basically what I did was hand-process the "+", "-" " " prefix of the lines that result from calling merge, and handle the conflict blocks that look like { conflict: true, mine: ['#yes'], theirs: ['#no']} interspersed into the string lines of the patch. You write >>>>>>>> (emit the 'theirs' lines) ======== (emit 'ours' lines) <<<<<<<<

[ExplodingCabbage]

Hmm. Just started looking at the merge.js code and besides the already-reported bugs I see more to dislike; loadPatch seems to heuristically detect if the passed param is a patch or not by looking for substrings like @@, and change its behaviour accordingly, which seems obviously fragile/incorrect given that you could legitimately want to diff two files that contain those substrings. An API that depends upon that kind of heuristic to determine how to treat its inputs is fundamentally bad, IMO.

[ExplodingCabbage]

I just had another few minutes to look at this. I've been reading the key bit of logic here and trying to reason about it:

  while (mineIndex < mine.hunks.length || theirsIndex < theirs.hunks.length) {
    let mineCurrent = mine.hunks[mineIndex] || {oldStart: Infinity},
        theirsCurrent = theirs.hunks[theirsIndex] || {oldStart: Infinity};

    if (hunkBefore(mineCurrent, theirsCurrent)) {
      // This patch does not overlap with any of the others, yay.
      ret.hunks.push(cloneHunk(mineCurrent, mineOffset));
      mineIndex++;
      theirsOffset += mineCurrent.newLines - mineCurrent.oldLines;
    } else if (hunkBefore(theirsCurrent, mineCurrent)) {
      // This patch does not overlap with any of the others, yay.
      ret.hunks.push(cloneHunk(theirsCurrent, theirsOffset));
      theirsIndex++;
      mineOffset += theirsCurrent.newLines - theirsCurrent.oldLines;
    } else {
      // Overlap, merge as best we can
      let mergedHunk = {
        oldStart: Math.min(mineCurrent.oldStart, theirsCurrent.oldStart),
        oldLines: 0,
        newStart: Math.min(mineCurrent.newStart + mineOffset, theirsCurrent.oldStart + theirsOffset),
        newLines: 0,
        lines: []
      };
      mergeLines(mergedHunk, mineCurrent.oldStart, mineCurrent.lines, theirsCurrent.oldStart, theirsCurrent.lines);
      theirsIndex++;
      mineIndex++;

      ret.hunks.push(mergedHunk);
    }
  }

Maybe I'm missing something, but just by inspection, I think I immediately see a bug in that else block at the end - namely that it doesn't handle the case where one hunk from mine overlaps with two separate hunks from theirs, or vice versa. So it'll (I think) produce a patch with overlapping, perhaps conflicting, hunks. I should probably create a test case demonstrating this.