How does merging work the second, third, etc. time you merge a file?

Question

I'm interested in knowing how revision-control systems do merging.

Suppose you have a file A. On one branch, file A is modified - call it file B. On another branch, file A is modified - call it file C:

  B
 /
A
 \
  C

When the second branch is merged into the first branch, I understand that a 3-way merge is performed between B, C, and their parent A. The result is file D on the first branch:

  B--D
 /
A
 \
  C

Now what I don't understand is what happens after another iteration. D is modified, becoming E, and C is modified, becoming F:

  B--D--E
 /
A
 \
  C--F

If we want to do another merge from the second branch to the first, what are the 3 files involved in the 3-way merge?

Answer 1

I'll give a concrete example using Git (other version control systems will be different). When you merge B and C together, you get history that looks something like this:

  B---D
 /   /
A   /
 \ /
  C

At this point, D has two parents, B and C. After you do more work and introduce E and F and do a merge, you will get something like:

  B---D--E--G
 /   /     /
A   /     /
 \ /     /
  C-----F

In the merge, the closest common parent between E and F is C.

The git merge documentation has more examples and descriptions of how this works. Also, the Git for Computer Scientists article has more descriptions, examples, and even better pictures (start with the "History" section for merge discussion.)

Answer 2

I guess the 3 files involved are E, F, and A. See Fig 3-16 in http://progit.org/book/ch3-2.html