search

mito-ds / saga

Version control all the things
7 stars 1 forks source link

Research: Investigate bad merge example. #26

Open naterush opened 4 years ago

naterush commented 4 years ago

Problem statement: https://tahoe-lafs.org/~zooko/badmerge/simple.html

Proposed solution: build an LCS between a, b1. Then build an LCS between b1 and b2. Then, combine these two LCS where if (x, y) are matched indices in the first LCS and (y, z) are matched indicies in the second LCS, then (x, z) is in the final output.

naterush commented 4 years ago

I'm wondering why we don't need to build an LCS between these two LCSs? Like, does a greedy algorithm suffice for these matches?

It suffices to maintain that the algorithm is an CS, but it might not be the LCS between the three files.

Note that a three-way LCS is actually strictly worse in this case, as it would still fall-prey to the bad merge, I think. This combining step actually preserves more information...