version control - Git merge affects on working directory and staging area

Question

I am new by Git and trying to know how git merge command works. So I tried a simple git project for example:

I have two branches: master and b. You can see git log for both here (1,2,4 are sample files that are created in branches):

* cf3456b (HEAD, b) add and modify 4 in b
* 68b9086 edit 1 in branch b
| * 81e6490 (master) remove 1 from branch b1
| * e0a6844 modify 2 in branch b1
| * 06bad1d add2 in branch b1
|/  
* c667d3b add 1 in branch master

So
master only has one file: 2
b only has two files: 1,4

Now when I try to do:

git merge master

I saw this message:

CONFLICT (modify/delete): 1 deleted in master and modified in HEAD. Version HEAD of 1 left in tree. Automatic merge failed; fix conflicts and then commit the result.

That is strange for me, I thought before that:

1. merge like a checkout tries to copy content from latest commit of merge in branch to latest commit of merge into branch but opposite of checkout, merge tries to do not change any file in merge into.And finally if both merge in and merge into branches have same file with different status, conflict occurs.
2. I know that git only saves snapshot of files instead of differences. So how git know about changes in latest commits of branches? (In message you can see 1 deleted in master and modified in HEAD which are differences)

Now if my thought was true, no conflict should occur for file 1. So my thought is not true, but how merge works really?

Answer 1

Re point #2, you are correct that git saves snapshots. However, given any two snapshots a and b, we can get a changeset (difference) by comparing b vs a—and git does just that, as needed.

As for the merge itself, first, we must note that git keeps a commit graph (also called "the DAG" or "the commit DAG", as the graph is a Directed Acyclic Graph or DAG). This is what your git log --graph output shows, though in this particular case we have such a simple form of graph that it's just a tree (until the merge is committed).

With any tree, and with many DAGs,¹ given two nodes in the tree we can find a unique Lowest Common Ancestor node, or LCA. The two nodes here are the tips of the two branches—commits cf3456b (the tip of your current branch) and 81e6490 (the tip of master)—and the LCA in this particular case is the first commit, c667d3b. In simple cases like this, the LCA is easy to spot visually: you just look through the commit graph to find the place that the two branches join up (all commits from there, back to the root, are on both branches).

This LCA node is the merge base. Git first finds the merge base of the current commit and the argument you give it. (For an "octopus merge", where you direct git to merge multiple commits onto the current branch, the job is a little more involved, but we can just ignore those here.)

Next, given the existing merge base and the two distinct tip commits, git must compute two changesets: one from the merge-base to the current commit, and one from the merge-base to the argument commit. Note that git does this once, up front, for the entire process, after which it can proceed with the merge action.

Now, for each file for which there are changes, git must combine the changes. For most simple modifications, the method is straightforward: if file 1 is modified in just one branch, take the modification as is. If it's modified in both branches, attempt to combine the modifications, taking just one copy where both branches made the same change. Of course, you get a conflict if both branches made differing changes to the same region of a single file.

For file creation or deletion cases, or when there are renames, things get a bit trickier. If a file is deleted in one branch and untouched in the other, git can resolve this by deleting the file ("keeping it deleted" if it's already deleted in HEAD, deleting it if it's deleted in the other commit). If the file is renamed in one branch, and modified in the other, git can combine these changes as well (doing or keeping the rename while also importing or retaining the other changes). For just about anything else, though, git simply declares a conflict, throws up its metaphorical hands, and makes you resolve the conflict.

In this case, file 1 really was modified in your current branch, and really was deleted in master. Git is not sure whether to delete the file (as directed by the merge-base to master diff), or keep the changes (as directed by the merge-base to HEAD diff), so it leaves you with the file and a conflict.

If you had created a new file 5 in both branches, git would again give you a conflict (except, possibly, if the file's new contents are the same in both branches—I have not tested this case).

---

¹With complex DAGs there may be multiple Lowest Common Ancestor candidates. For git's "recursive" merge, git handles this by merging each LCA candidate to form a new "virtual base". This virtual base becomes the merge-base against which the two commits are compared. If there are only two LCA candidates, the virtual merge base is obtained by doing the rough equivalent of:

git checkout -b temp candidate_1
git merge candidate_2
git commit -a -m ""

Any merge conflicts that occur during this "inner merge" are ignored: the conflicted merge-base is used with its conflicts in place. This can make for some funky-looking conflicts, especially when there's a conflict in the same region of the "outer" merge: see this SO question.

If there are more than two LCA candidates, merge-recursive takes the first two and merges them, then merges the third, then merges the fourth, and so on, iteratively. It does this even though it could merge pairs to cut the number in half, then merge the merged-pairs to cut it in half again, and so on. That is, given N LCA candidates, it would be possible to do ceil(log2(N)) merges, rather than N-1 merges, but git doesn't—N rarely exceeds 2 anyway.