Merge conflicts

[gmierz]

Currently, the TUID service completely ignores merge diffs because they contain the same changes done by past patches/diffs that have already been applied.

However, there exists a case where merge conflicts can occur, leading to changes being done in the merge patch which would never be in the TUID DB with what we currently have. Furthermore, those changes applied between the previous merge, and a future merge which has a conflict, will be incorrect because of the conflict. Now, since diffs cannot be applied within that range, only annotations will be usable in these cases.

These conflicts occur anywhere from 1-9% of the time, so they are uncommon but not that rare. Currently, once a merge conflict occurs in one file, any changes applied to it afterwards will result in incorrect annotations. Because this doesn't happen very often, at most 9% of the time, we will have no choice but to return an annotation for a file at a given revision.

The solution to this problem is to use the upcoming Clogger to:
(1): Store which revisions are merges by setting a merge field to 1 to indicate it's a merge.
(2): Store a new table of (merge_revision, file) to denote all files that were actually modified by the merge.
(2i) Get all the files the merge modifies.
(2ii) Get the json-log for each file, and if the merge_revision is in the entries list, then the merge modifies it.
(3): When we encounter a merge revision in the service (searching for the closest revnum in the future with merge field set), check if any requested files are modified by the merge and then return a new annotation for them.

[klahnakoski]

Maybe the merge patch and, the aggregate of the changesets that make up the merge patch, can be compared to deduce a "delta patch" - defined as "the changes made to fix merge conflicts". This would be faster to apply; especially if the number of files touched by the delta is small.

Let me attempt some pseudo code: Usually we have a merge patch (M) be the application of multiple changesets (Ci):

M = C1 * C2 * C3 * ... * Cn

When there is a merge conflict, it is resolved by apply a delta patch:

M = C1 * C2 * C3 * ... * Cn * D

We can rearrange this equation to:

Kn * ... * K3 * K2 * K1 * M = D

where Ki is the inverse changeset of Ci

[gmierz]

To get an inverse changeset Ki when there are no merge conflicts is no issue. We start from the current revision, get the last diff applied and dis-apply it by inverting the additions and subtractions.

But when there is a merge conflict, there is no way to know how the last diff was applied, because it might not have been applied, or even misapplied.

I think that the solution you propose is also trying to solve the inverse of the problem of (1)"How do we merge these patches into a single revision?". You may already recognize what I am getting at. We would have to solve the inverse problem, which requires solving the forward problem that is (1) which is not yet automated. There are existing tools for solving this problem that do so by modifying input (diffs), and checking how well the output (simulated merge) matches the result (true merge).