Three way merge

[azmeuk]

Hi. First of all, thank you for your work.
It would be awesome for deepmerge to be able to solve three way merge cases, as the one described in this stackoverflow question.

The problem is to merge two dictionaries A and B, knowing a common previous state C of both dictionaries. The merge needs to occur in subelements too. In the case of real conflict, an exception needs to be raised.

1 - In the following example, the merge method should understand that A and B edited different items, and thus the merge should not raise a conflict:

C = {"x": 0, "y": 0}
A = {"x": 1, "y": 0} # Edit x, but not y
B = {"x": 0, "y": 1} # Edit y, but not x
# merge(A, B, C) => {"x": 1, "y": 1}

2 - The merge needs to be able to deal with new items and deleted items:

C = {"x": 0}
A = {"x": 0, "y": 0} # Add y, keep x untouched
B = {}               # Delete x
# merge(A, B, C) => {"y": 0}

3 - The merge should raise an exception when a real conflict occurs

C = {"x": 0}
A = {"x": 1}         # Edit x 
B = {"x": 2}         # Also edit x
# merge(A, B, C) => raise Exception

C = {"x": 0}
A = {"x": 1}         # Edit x 
B = {}               # Delete x
# merge(A, B, C) => raise Exception

4 - The merge should work recursively

C = {"deeper": {"x": 0, "y": 0}}
A = {"deeper": {"x": 1, "y": 0}} # Edit deeper["x"], but not deeper["y"]
B = {"deeper": {"x": 0, "y": 1}} # Edit deeper["y"], but not deeper["x"]
# merge(A, B, C) => {"deeper": {"x": 1, "y": 1}}

Would you accept a pull request for this job (if I ever had time to submit one) ?

[toumorokoshi]

Hey @azmeuk! This is a really interesting problem, and I think it's pretty obvious where a three-way merge would be useful. I would love to support some way to do this in deepmerge, and happy to review any PRs.

Regarding the approach: I think the core deepmerge core could be made extensible enough to support a 3-way (or n-way really) merge: the main feature is being aware of what type of data structures are recursive and acting on them.

I think as merges of any number are incorporated, there should be an easy way to plug in different conflict resolution schemes. I think the reason everyone tends to write their own merger is because it's hard to make one that specifically fits one's use case. Being able to plug in different conflict resolution functions into the merger makes deepmerge able to tackle even esoteric use cases.

I'm thinking maybe the deepmerge functions can be modified to look something like:

def merge_function(merger, target, *sources):

with sources being the versions that one is intending to merge. Should be easy to create one that uses functions that allow edits from only one particular version, and raise an exception otherwise.

I'm okay with exposing a new API and preparing a deprecation path if it means we can support cool use cases like this.

Thanks for reaching out! Don't hesitate to @ me or shoot me an e-mail if you want to discuss implementation.