Who we are

We are the developers of Plastic SCM, a full version control stack (not a Git variant). We work on the strongest branching and merging you can find, and a core that doesn't cringe with huge binaries and repos. We also develop the GUIs, mergetools and everything needed to give you the full version control stack.

If you want to give it a try, download it from here.

We also code SemanticMerge, and the gmaster Git client.

Merge quiz - find the common ancestor

Wednesday, April 02, 2014 Pablo Santos 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”?

Notes:

  • Green arrows are merge links.

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

Solution!

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!

Pablo Santos
I'm the CTO and Founder at Códice.
I've been leading Plastic SCM since 2005. My passion is helping teams work better through version control.
I had the opportunity to see teams from many different industries at work while I helped them improving their version control practices.
I really enjoy teaching (I've been a University professor for 6+ years) and sharing my experience in talks and articles.
And I love simple code. You can reach me at @psluaces.

Pablo Santos

1 comment:

  1. UnknownApril 9, 2014 at 5:50 PM

    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.

    ReplyDelete

Subscribe to: Post Comments (Atom)