Git: A three-way merge of snapshots

Merge two whole snapshots against their merge base, file by file.

What to build

A program that performs a file-level three-way merge and reports conflicts the way Git does.

Requirements

  • For each path (sorted): if ours equals theirs, use it; else if ours equals base, take theirs; else if theirs equals base, keep ours; otherwise it is a conflict: CONFLICT (modify/delete): PATH deleted in ours and modified in theirs (or deleted in theirs and modified in ours), CONFLICT (add/add): Merge conflict in PATH if it is not in the base, or CONFLICT (content): Merge conflict in PATH. A missing version counts as different from any content.
  • Print the conflict lines (sorted by path), then merged: and the merged files as path=content separated by spaces (or merged: (empty)), then Automatic merge failed; fix conflicts and then commit the result. if there were conflicts, else Merge made by the 'ort' strategy.

Input

Three blocks for base, ours and theirs: a line with k, then k lines path content.

Output

The conflict lines, the merged line and the result line.

Constraints

At most 200 paths; no spaces in paths or contents.

Example

Input:

2
app.py v1
README.md v1
2
app.py v2
README.md v1
2
app.py v1
README.md v2

Output:

merged: README.md=v2 app.py=v2
Merge made by the 'ort' strategy.

Why it works

Comparing each side with the base shows which side made a change, so independent changes combine automatically, and only changes both sides made to the same file need a person.

Examples

Example 1 · Input
2
app.py v1
README.md v1
2
app.py v2
README.md v1
2
app.py v1
README.md v2
Expected output
merged: README.md=v2 app.py=v2
Merge made by the 'ort' strategy.
Example 2 · Input
1
a v1
1
a v2
1
a v3
Expected output
CONFLICT (content): Merge conflict in a
merged: (empty)
Automatic merge failed; fix conflicts and then commit the result.

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each path take its versions in base, ours and theirs (missing means deleted or never added).

Hint 2

Same on both sides → use it; only one side changed → take that side; otherwise decide which kind of conflict it is.

Solution

Show one correct solution (try it yourself first)
base = dict(input().split() for _ in range(int(input())))
ours = dict(input().split() for _ in range(int(input())))
theirs = dict(input().split() for _ in range(int(input())))
merged, conflicts = {}, []
for path in sorted(set(base) | set(ours) | set(theirs)):
    b, o, t = base.get(path), ours.get(path), theirs.get(path)
    if o == t:
        chosen = o
    elif o == b:
        chosen = t
    elif t == b:
        chosen = o
    else:
        if o is None:
            conflicts.append(f"CONFLICT (modify/delete): {path} deleted in ours and modified in theirs")
        elif t is None:
            conflicts.append(f"CONFLICT (modify/delete): {path} deleted in theirs and modified in ours")
        elif b is None:
            conflicts.append(f"CONFLICT (add/add): Merge conflict in {path}")
        else:
            conflicts.append(f"CONFLICT (content): Merge conflict in {path}")
        continue
    if chosen is not None:
        merged[path] = chosen
for line in conflicts:
    print(line)
print("merged: " + (" ".join(f"{p}={c}" for p, c in sorted(merged.items())) or "(empty)"))
print("Automatic merge failed; fix conflicts and then commit the result." if conflicts else "Merge made by the 'ort' strategy.")

Lesson: Merging →