'git merge'는 세부적으로 어떻게 작동합니까?

'git merge'는 세부적으로 어떻게 작동합니까?

---

'git merge'뒤에있는 정확한 알고리즘 (또는 그 근처)을 알고 싶습니다. 최소한 다음 하위 질문에 대한 답변이 도움이 될 것입니다.

• git은 충돌하지 않는 특정 변경의 컨텍스트를 어떻게 감지합니까?
• git은 이러한 정확한 줄에 충돌이 있음을 어떻게 알 수 있습니까?
• git 자동 병합 기능은 무엇입니까?
• 브랜치 병합을위한 공통 기반이 없을 때 git은 어떻게 수행합니까?
• 브랜치를 병합하기위한 공통 기반이 여러 개인 경우 git은 어떻게 수행합니까?
• 한 번에 여러 분기를 병합하면 어떻게됩니까?
• 병합 전략의 차이점은 무엇입니까?

그러나 전체 알고리즘에 대한 설명이 훨씬 더 좋습니다.

---

3 방향 병합 알고리즘에 대한 설명을 찾는 것이 가장 좋습니다. 높은 수준의 설명은 다음과 같습니다.

1. 적합한 병합 기반을 찾으십시오 B-두 새 버전 ( X및 Y) 의 조상 인 파일의 버전 과 일반적으로 가장 최근의 해당 기반 (다음 중 하나 인 더 뒤로 돌아 가야하는 경우도 있음) git의 기본 recursive병합 기능 )
2. 의 차이점 수행 X와 B와 Y와를 B.
3. 두 개의 차이점에서 식별 된 변경 블록을 살펴보십시오. 양측이 동일한 지점에서 동일한 변경 사항을 도입하면 둘 중 하나를 수락합니다. 한 사람이 변경 사항을 도입하고 다른 사람이 해당 지역을 떠나면 최종 변경 사항을 도입하십시오. 둘 다 지점에서 변경 사항을 도입했지만 일치하지 않는 경우 충돌을 수동으로 해결하도록 표시하십시오.

전체 알고리즘 많이 더 세부이와 거래하고, (심지어 일부 문서를 가지고 /usr/share/doc/git-doc/technical/trivial-merge.txt와 함께, 하나 git help XXXXXX 중 하나이고, 페이지 merge-base, merge-file, merge, merge-one-file그리고 아마도 몇 가지 다른). 충분히 깊지 않으면 항상 소스 코드가 있습니다.

---

브랜치를 병합하기위한 공통 기반이 여러 개인 경우 git은 어떻게 수행합니까?

이 기사는 매우 유용했습니다 : http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html (여기 2 부 ).

Recursive는 diff3을 재귀 적으로 사용하여 조상으로 사용될 가상 분기를 생성합니다.

예 :

(A)----(B)----(C)-----(F)
        |      |       |
        |      |   +---+
        |      |   |
        |      +-------+
        |          |   |
        |      +---+   |
        |      |       |
        +-----(D)-----(E)

그때:

git checkout E
git merge F

2 개의 가장 좋은 공통 조상 (다른 조상이 아닌 공통 조상) C과 D. Git은이를 새로운 가상 브랜치로 병합 V한 다음 V기본으로 사용 합니다.

(A)----(B)----(C)--------(F)
        |      |          |
        |      |      +---+
        |      |      |
        |      +----------+
        |      |      |   |
        |      +--(V) |   |
        |          |  |   |
        |      +---+  |   |
        |      |      |   |
        |      +------+   |
        |      |          |
        +-----(D)--------(E)

나는 Git이 더 좋은 공통 조상이 있다면 계속해서 V다음 조상과 병합한다고 생각 합니다.

이 기사는 가상 분기 Git을 생성하는 동안 병합 충돌이 발생하면 충돌 마커를 그대로두고 계속한다고 말합니다.

한 번에 여러 분기를 병합하면 어떻게됩니까?

@Nevik Rehnel이 설명했듯이 전략에 따라 다르며 man git-merge MERGE STRATEGIES섹션에서 잘 설명되어 있습니다.

예를 들어 한 번에 여러 분기 병합 만 octopus및 ours/ theirs지원 recursive하지 않습니다.

octopus충돌이있을 경우 병합을 거부 ours하고 사소한 병합이므로 충돌이 없을 수 있습니다.

이 명령은 새 커밋을 생성하면 부모가 2 개 이상입니다.

나는 merge -X octopusGit 1.8.5에서 충돌없이 어떻게 진행되는지 확인했습니다.

초기 상태 :

   +--B
   |
A--+--C
   |
   +--D

동작:

git checkout B
git merge -Xoctopus C D

새로운 상태 :

   +--B--+
   |     |
A--+--C--+--E
   |     |
   +--D--+

예상대로 E3 명의 부모가 있습니다.

TODO : 문어가 단일 파일 수정에서 정확히 작동하는 방식. 재귀 적 2x2 3 방향 병합?

브랜치 병합을위한 공통 기반이 없을 때 git은 어떻게 수행합니까?

@Torek는 2.9 이후로 병합이 --allow-unrelated-histories.

Git 1.8.5에서 경험적으로 시도했습니다.

git init
printf 'a\nc\n' > a
git add .
git commit -m a

git checkout --orphan b
printf 'a\nb\nc\n' > a
git add .
git commit -m b
git merge master

a 포함 :

a
<<<<<<< ours
b
=======
>>>>>>> theirs
c

그때:

git checkout --conflict=diff3 -- .

a 포함 :

<<<<<<< ours
a
b
c
||||||| base
=======
a
c
>>>>>>> theirs

해석:

• 베이스가 비어있다
• 기본이 비어 있으면 단일 파일에서 수정 사항을 해결할 수 없습니다. 새 파일 추가와 같은 것만 해결할 수 있습니다. 위의 충돌은 a\nc\n단일 라인 추가 로베이스와의 3 방향 병합에서 해결됩니다.
• 내가 생각하는 기본 파일이없는 3 방향 병합 그냥 DIFF 인 2 웨이 병합이라는 것을

---

나도 관심이 있습니다. 답은 모르겠지만 ...

작동하는 복잡한 시스템은 작동하는 단순한 시스템에서 진화 한 것으로 항상 밝혀졌습니다.

나는 git의 병합이 매우 정교하고 이해하기 매우 어려울 것이라고 생각합니다.하지만 이에 접근하는 한 가지 방법은 그 선구자로부터 관심의 핵심에 집중하는 것입니다. 즉, 공통 조상이없는 두 개의 파일이 주어지면 git merge가 파일을 병합하는 방법과 충돌이있는 위치를 어떻게 파악합니까?

몇 가지 선구자를 찾아 보자. 에서 git help merge-file:

git merge-file is designed to be a minimal clone of RCS merge; that is,
       it implements all of RCS merge's functionality which is needed by
       git(1).

wikipedia에서 : http://en.wikipedia.org/wiki/Git_%28software%29- > http://en.wikipedia.org/wiki/Three-way_merge#Three-way_merge- > http : //en.wikipedia .org / wiki / Diff3- > http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

That last link is a pdf of a paper describing the diff3 algorithm in detail. Here's a google pdf-viewer version. It's only 12 pages long, and the algorithm is only a couple of pages - but a full-on mathematical treatment. That might seem a bit too formal, but if you want to understand git's merge, you'll need to understand the simpler version first. I haven't checked yet, but with a name like diff3, you'll probably also need to understand diff (which uses a longest common subsequence algorithm). However, there may be a more intuitive explanation of diff3 out there, if you have a google...

---

Now, I just did an experiment comparing diff3 and git merge-file. They take the same three input files version1 oldversion version2 and mark conflicts the way same, with <<<<<<< version1, =======, >>>>>>> version2 (diff3 also has ||||||| oldversion), showing their common heritage.

I used an empty file for oldversion, and near-identical files for version1 and version2 with just one extra line added to version2.

Result: git merge-file identified the single changed line as the conflict; but diff3 treated the whole two files as a conflict. Thus, sophisticated as diff3 is, git's merge is even more sophisticated, even for this simplest of cases.

Here's the actual results (I used @twalberg's answer for the text). Note the options needed (see respective manpages).

$ git merge-file -p fun1.txt fun0.txt fun2.txt

You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:

    Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B.  Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.
<<<<<<< fun1.txt
=======
THIS IS A BIT DIFFERENT
>>>>>>> fun2.txt

The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...

$ diff3 -m fun1.txt fun0.txt fun2.txt

<<<<<<< fun1.txt
You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:

    Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B.  Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.

The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...
||||||| fun0.txt
=======
You might be best off looking for a description of a 3-way merge algorithm. A
high-level description would go something like this:

    Find a suitable merge base B - a version of the file that is an ancestor of
both of the new versions (X and Y), and usually the most recent such base
(although there are cases where it will have to go back further, which is one
of the features of gits default recursive merge) Perform diffs of X with B and
Y with B.  Walk through the change blocks identified in the two diffs. If both
sides introduce the same change in the same spot, accept either one; if one
introduces a change and the other leaves that region alone, introduce the
change in the final; if both introduce changes in a spot, but they don't match,
mark a conflict to be resolved manually.
THIS IS A BIT DIFFERENT

The full algorithm deals with this in a lot more detail, and even has some
documentation (/usr/share/doc/git-doc/technical/trivial-merge.txt for one,
along with the git help XXX pages, where XXX is one of merge-base, merge-file,
merge, merge-one-file and possibly a few others). If that's not deep enough,
there's always source code...
>>>>>>> fun2.txt

If you are truly interested in this, it's a bit of a rabbit hole. To me, it seems as deep as regular expressions, the longest common subsequence algorithm of diff, context free grammars, or relational algebra. If you want to get to the bottom of it, I think you can, but it will take some determined study.

---

Here is the original implementation

http://git.kaarsemaker.net/git/blob/857f26d2f41e16170e48076758d974820af685ff/git-merge-recursive.py

Basically you create a list of common ancestors for two commits and then recursively merge them, either fast forwarding them, or creating virtual commits that get used for the basis of a three-way merge on the files.

---

How does git detect the context of a particular non-conflicting change?
How does git find out that there is a conflict in these exact lines?

If the same line has changed on both side of the merge, it's a conflict; if they haven't, the change from one side (if existent) is accepted.

Which things does git auto-merge?

Changes that do not conflict (see above)

How does git perform when there are multiple common bases for merging branches?

By the definition of a Git merge-base, there is only ever one (the latest common ancestor).

What happens when I merge multiple branches at once?

That depends on the merge strategy (only the octopus and the ours/theirs strategies support merging more than two branches).

What is a difference between merge strategies?

This is explained in the git merge manpage.

참고URL : https://stackoverflow.com/questions/14961255/how-does-git-merge-work-in-details