Bagaimana cara kerja 'git merge' secara detail?

Saya ingin tahu algoritma yang tepat (atau yang mendekati itu) di balik 'git merge'. Jawaban setidaknya untuk sub-pertanyaan ini akan membantu:

• Bagaimana git mendeteksi konteks perubahan non-konflik tertentu?
• Bagaimana git mengetahui bahwa ada konflik di baris yang sama persis?
• Hal apa yang dilakukan git auto-merge?
• Bagaimana kinerja git jika tidak ada basis umum untuk menggabungkan cabang?
• Bagaimana kinerja git ketika ada beberapa basis umum untuk menggabungkan cabang?
• Apa yang terjadi jika saya menggabungkan beberapa cabang sekaligus?
• Apa perbedaan antara strategi penggabungan?

Tetapi deskripsi dari keseluruhan algoritma akan jauh lebih baik.

Anda mungkin lebih baik mencari deskripsi tentang algoritma penggabungan 3 arah. Deskripsi tingkat tinggi akan menjadi seperti ini:

1. Temukan basis penggabungan yang sesuai B- versi file yang merupakan leluhur dari kedua versi baru ( Xdan Y), dan biasanya basis yang paling baru (meskipun ada kasus di mana itu harus kembali lebih jauh, yang merupakan salah satu dari fitur gabungan gitdefault recursive)
2. Lakukan perbedaan Xdengan Bdan Ydengan B.
3. Berjalanlah melalui blok perubahan yang diidentifikasi dalam dua perbedaan. Jika kedua belah pihak memperkenalkan perubahan yang sama di tempat yang sama, terima salah satunya; jika salah satu memperkenalkan perubahan dan yang lain meninggalkan wilayah itu sendiri, perkenalkan perubahan di tahap akhir; jika keduanya memperkenalkan perubahan di suatu tempat, tetapi tidak cocok, tandai konflik untuk diselesaikan secara manual.

Algoritme lengkap menangani hal ini dengan lebih detail, dan bahkan memiliki beberapa dokumentasi ( https://github.com/git/git/blob/master/Documentation/technical/trivial-merge.txt untuk satu, bersama dengan git help XXXhalaman , di mana XXX adalah salah satu dari merge-base, merge-file, merge, merge-one-filedan mungkin beberapa orang lain). Jika itu tidak cukup dalam, selalu ada kode sumber ...

Bagaimana kinerja git ketika ada beberapa basis umum untuk menggabungkan cabang?

Artikel ini sangat membantu: http://codicesoftware.blogspot.com/2011/09/merge-recursive-strategy.html (ini adalah bagian 2 ).

Rekursif menggunakan diff3 secara rekursif untuk menghasilkan cabang virtual yang akan digunakan sebagai leluhur.

Misalnya:

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

Kemudian:

git checkout E
git merge F

Ada 2 leluhur bersama terbaik (leluhur bersama yang bukan leluhur satu sama lain), Cdan D. Git menggabungkannya menjadi cabang virtual baru V, dan kemudian digunakan Vsebagai basis.

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

Saya kira Git hanya akan melanjutkan jika ada lebih banyak nenek moyang terbaik yang sama, bergabung Vdengan yang berikutnya.

Artikel tersebut mengatakan bahwa jika ada konflik penggabungan saat membuat cabang virtual, Git hanya meninggalkan penanda konflik di mana mereka berada dan berlanjut.

Apa yang terjadi jika saya menggabungkan beberapa cabang sekaligus?

Seperti yang dijelaskan @Nevik Rehnel, itu tergantung pada strateginya, dijelaskan dengan baik di man git-merge MERGE STRATEGIESbagian.

Hanya octopusdan ours/ theirsmendukung penggabungan beberapa cabang sekaligus, recursivemisalnya tidak.

octopusmenolak bergabung jika akan ada konflik, dan oursmerupakan penggabungan yang sepele sehingga tidak ada konflik.

Perintah tersebut menghasilkan komit baru yang akan memiliki lebih dari 2 orang tua.

Saya melakukannya merge -X octopusdi Git 1.8.5 tanpa konflik untuk melihat bagaimana kelanjutannya.

Keadaan awal:

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

Tindakan:

git checkout B
git merge -Xoctopus C D

Negara bagian baru:

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

Seperti yang diharapkan, Ememiliki 3 orang tua.

TODO: bagaimana sebenarnya gurita beroperasi pada modifikasi file tunggal. Penggabungan dua-oleh-dua 3-arah rekursif?

Bagaimana kinerja git jika tidak ada basis umum untuk menggabungkan cabang?

@Torek menyebutkan bahwa sejak 2.9, penggabungan gagal tanpa --allow-unrelated-histories.

Saya mencobanya secara empiris di 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 mengandung:

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

Kemudian:

git checkout --conflict=diff3 -- .

a mengandung:

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

Penafsiran:

• basisnya kosong
• bila basis kosong, tidak mungkin menyelesaikan modifikasi apa pun pada satu file; hanya hal-hal seperti penambahan file baru yang dapat diselesaikan. Konflik di atas akan diselesaikan dengan penggabungan 3 arah dengan basis a\nc\nsebagai penambahan satu baris
• Saya pikir penggabungan 3 arah tanpa file dasar disebut penggabungan 2 arah, yang hanya sebuah diff

Saya tertarik juga. Saya tidak tahu jawabannya, tapi ...

Sistem kompleks yang berhasil selalu ditemukan telah berevolusi dari sistem sederhana yang berfungsi

Saya pikir penggabungan git sangat canggih dan akan sangat sulit untuk dipahami - tetapi salah satu cara untuk mendekatinya adalah dari pendahulunya, dan dengan fokus pada inti perhatian Anda. Yaitu, mengingat dua file yang tidak memiliki leluhur yang sama, bagaimana git menggabungkan cara menggabungkannya, dan di mana konflik terjadi?

Mari kita coba mencari beberapa prekursor. Dari 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).

Dari 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

Tautan terakhir adalah pdf dari makalah yang menjelaskan diff3algoritme secara rinci. Ini adalah versi google pdf-viewer . Panjangnya hanya 12 halaman, dan algoritmanya hanya beberapa halaman - tetapi perawatan matematis lengkap. Itu mungkin tampak agak terlalu formal, tetapi jika Anda ingin memahami penggabungan git, Anda harus memahami versi yang lebih sederhana terlebih dahulu. Saya belum memeriksanya, tetapi dengan nama seperti diff3, Anda mungkin juga perlu memahami diff (yang menggunakan algoritma urutan umum terpanjang ). Namun, mungkin ada penjelasan yang lebih intuitif di diff3luar sana, jika Anda memiliki google ...

Sekarang, saya baru saja melakukan percobaan membandingkan diff3dan git merge-file. Mereka mengambil tiga file yang sama masukan version1 OldVersion version2 dan konflik tanda jalan yang sama, dengan <<<<<<< version1, =======, >>>>>>> version2( diff3juga memiliki ||||||| oldversion), menunjukkan warisan bersama mereka.

Saya menggunakan file kosong untuk versi lama , dan file yang hampir identik untuk versi1 dan versi2 hanya dengan satu baris tambahan ditambahkan ke versi2 .

Hasil: git merge-filemengidentifikasi satu baris yang diubah sebagai konflik; tetapi diff3memperlakukan kedua file secara keseluruhan sebagai konflik. Jadi, secanggih diff3, penggabungan git bahkan lebih canggih, bahkan untuk kasus yang paling sederhana ini.

Inilah hasil sebenarnya (saya menggunakan jawaban @ twalberg untuk teksnya). Perhatikan opsi yang diperlukan (lihat halaman manual masing-masing).

$ 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

Jika Anda benar-benar tertarik dengan ini, ini sedikit lubang kelinci. Bagi saya, ini tampaknya sedalam ekspresi reguler, algoritme urutan umum terpanjang dari diff, tata bahasa bebas konteks, atau aljabar relasional. Jika Anda ingin membacanya, saya rasa Anda bisa, tetapi itu akan membutuhkan studi yang pasti.

Inilah implementasi aslinya

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

Pada dasarnya Anda membuat daftar nenek moyang yang sama untuk dua komit dan kemudian menggabungkannya secara rekursif, baik meneruskan cepat, atau membuat komit virtual yang digunakan untuk dasar penggabungan tiga cara pada file.

Bagaimana git mendeteksi konteks perubahan non-konflik tertentu?
Bagaimana git mengetahui bahwa ada konflik di baris yang sama persis?

Jika baris yang sama telah berubah di kedua sisi penggabungan, itu konflik; jika belum, perubahan dari satu sisi (jika ada) diterima.

Hal apa yang dilakukan git auto-merge?

Perubahan yang tidak bertentangan (lihat di atas)

Bagaimana kinerja git ketika ada beberapa basis umum untuk menggabungkan cabang?

Menurut definisi basis gabungan Git , hanya ada satu (leluhur bersama terbaru).

Apa yang terjadi jika saya menggabungkan beberapa cabang sekaligus?

Itu tergantung pada strategi penggabungan (hanya yang octopusdan ours/ theirsstrateginya mendukung penggabungan lebih dari dua cabang).

Apa perbedaan antara strategi penggabungan?

Ini dijelaskan di halaman git mergemanual .