Merge quiz - find the common ancestor

Wednesday, April 02, 2014 1 Comments

Edit:There's a conversation going on in LinkedIn.

Suppose you have a branch hierarchy like the one below and you need to merge changeset “18” (the ‘source of the merge’) to changeset “22” (‘the destination of the merge’).

In order to perform a 3-way merge your version control system will need to find the ‘common ancestor’ of the two changesets.

This is something your version control will do for you (depending on which one you’re using :P) but, in the branch diagram below, can you calculate which one is the changeset (or changesets!) that is the common ancestor of commits “18” and “22”?


  • Green arrows are merge links.

  • Grey arrows going back to the parent changeset just indicate how the changesets are linked to each other.


Edit April 10th 2014:I'm going to add the solution here just in case anyone is interested.

Here goes the solution: there are 3 possible ancestors (ancestors that are not parent of a another ancestor).

So, recursive merge will have to deal with the situation. Another choice would be selecting one of the three (maybe the 'nearest') but it would potentially lead to errors as I explained here.

What 'recursive' is going to do is:

  • It will take two of the ancestors and will merge them creating a new 'virtual ancestor 0'
  • Virt ancestor 0 will be merged with the remaining ancestor (remember there were three) creating 'virtual ancestor 1'
  • The 'virtual ancestor 1' will be used as the base to merge 18 and 22 ('src' and 'dst')

Check the following figure for an explanation:

Hope it helps digging into the different merge algorithms available! :-) Enjoy!

1 comment:

  1. I'll bite ... :-)
    Changesets 4 & 5 if you are thinking of recursive merge, and possibly one more - I can't see which changeset branch0004 is branched from.

    If you have a 3-way merge tool that tolerates identical deltas applied to both the 'source' and 'destination' versions, then you could use changeset 2 as a least common ancestor, but that would not be my preferred way of working.