Merge-এর ভেতরে — merge base, ort strategy, diff3 আর rerere

$ git log --oneline --graph --all
* e104383 E: b = 2
*   773fa0c M2: merge B into side
|\
| | * 26043ea D: a = 2
| | * 998a27d M1: merge side into main
| |/|
| |/
|/|
* | c567f5e C: b = 1
| * 612c0ad B: a = 1
|/
* dacb7cf A: start
$ git merge-base main side
612c0ad4ae5ce87bcf7d225f1a44871df2ef829d
$ git merge-base --all main side
612c0ad4ae5ce87bcf7d225f1a44871df2ef829d
c567f5ecf952ffb4358a7fed9ace34c3b4c8bb8a
$ git merge-base --is-ancestor 612c0ad side && echo yes || echo no
yes
$ git merge-base --is-ancestor main side && echo yes || echo no
no

$ git merge-tree --write-tree 612c0ad c567f5e
491859d986dafd0d8c1de8dd7245134729c092ad
$ git show $(git merge-tree --write-tree 612c0ad c567f5e):f.txt
a = 1
keep 1
keep 2
keep 3
b = 1
# (git switch -c try-resolve)
$ git merge -s resolve side
Trying simple merge.
Simple merge failed, trying Automatic merge.
Auto-merging f.txt
ERROR: content conflict in f.txt
fatal: merge program failed
Automatic merge failed; fix conflicts and then commit the result.
$ cat f.txt
a = 2
keep 1
keep 2
keep 3
<<<<<<< .merge_file_q5jRne
b = 1
=======
b = 2
>>>>>>> .merge_file_01p3fB
# (git merge --abort; git switch main)
$ git merge side
Auto-merging f.txt
Merge made by the 'ort' strategy.
 f.txt | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
$ cat f.txt
a = 2
keep 1
keep 2
keep 3
b = 2

// Criss-cross: all merge bases, then the virtual merge base that ort/recursive builds.
const parents = { A: [], B: ["A"], C: ["A"], M1: ["B", "C"], M2: ["C", "B"], D: ["M1"], E: ["M2"] };
const file = { A: { a: 0, b: 0 }, B: { a: 1, b: 0 }, C: { a: 0, b: 1 },   // content of f.txt
  M1: { a: 1, b: 1 }, M2: { a: 1, b: 1 }, D: { a: 2, b: 1 }, E: { a: 1, b: 2 } };
function ancestors(c, seen = new Set()) {           // c and everything reachable through parents
  if (!seen.has(c)) { seen.add(c); parents[c].forEach(p => ancestors(p, seen)); }
  return seen;
}
const isAnc = (x, y) => ancestors(y).has(x);          // like git merge-base --is-ancestor x y
function mergeBases(x, y) {                           // best common ancestors
  const common = [...ancestors(x)].filter(c => ancestors(y).has(c));
  return common.filter(c => !common.some(d => d !== c && isAnc(c, d)));
}
function merge3(base, ours, theirs) {                 // key by key, like line by line
  const out = {};
  for (const k in base) {
    if (ours[k] === theirs[k] || theirs[k] === base[k]) out[k] = ours[k];
    else if (ours[k] === base[k]) out[k] = theirs[k];
    else out[k] = "CONFLICT(" + ours[k] + "|" + theirs[k] + ")";
  }
  return out;
}
const show = o => Object.entries(o).map(([k, v]) => k + "=" + v).join(" ");
const bases = mergeBases("D", "E");
console.log("merge bases of D and E:", bases.join(", "));
console.log("B ancestor of C?", isAnc("B", "C"), "| C ancestor of B?", isAnc("C", "B"));
console.log("common ancestors:", [...ancestors("D")].filter(c => ancestors("E").has(c)).join(" "));
const inner = mergeBases(bases[0], bases[1]);          // the bases' own merge base
const virtual = merge3(file[inner[0]], file[bases[0]], file[bases[1]]);
console.log("virtual base = merge(B, C) over " + inner + ":", show(virtual));
console.log("ort with virtual base :", show(merge3(virtual, file.D, file.E)));
console.log("resolve, picks base B :", show(merge3(file.B, file.D, file.E)));

$ git merge-base --octopus main docs ci i18n
869be076d4aa9bfdead89538d877166814f7f337
$ git merge docs ci i18n
Trying simple merge with docs
Trying simple merge with ci
Trying simple merge with i18n
Merge made by the 'octopus' strategy.
 GUIDE.md | 1 +
 bn.txt   | 1 +
 ci.yml   | 1 +
 3 files changed, 3 insertions(+)
 create mode 100644 GUIDE.md
 create mode 100644 bn.txt
 create mode 100644 ci.yml
$ git log --oneline --graph
*---.   c2986bb Merge branches 'docs', 'ci' and 'i18n'
|\ \ \
| | | * b3a4c20 Add Bangla strings
| | * | 3686306 Add CI config
| | |/
| * / 26c2b7c Add order guide
| |/
* / a215ca2 Update README
|/
* 869be07 Start
$ git cat-file -p HEAD | grep parent
parent a215ca2a566564422f18778057a0558e840a3950
parent 26c2b7cf4ec3e3889a87ce611da4d6b8f05a8925
parent 3686306e0af29d367150dffe021031439fe67724
parent b3a4c2028c0c6fba100042c66951edaec479f891

$ git merge fee-a fee-b
Trying simple merge with fee-a
Trying simple merge with fee-b
Simple merge did not work, trying automatic merge.
Auto-merging shop.conf
ERROR: content conflict in shop.conf
fatal: merge program failed
Automatic merge failed; fix conflicts and then commit the result.
$ git status --short
UU shop.conf
# (git merge --abort; a fresh trial branch)
$ git merge fee-a fee-b note
Trying simple merge with fee-a
Trying simple merge with fee-b
Simple merge did not work, trying automatic merge.
Auto-merging shop.conf
ERROR: content conflict in shop.conf
fatal: merge program failed
Automated merge did not work.
Should not be doing an octopus.
Merge with strategy octopus failed.
$ git status --short

# (git switch -c try-default main)
$ git merge promo
Auto-merging shop.conf
CONFLICT (content): Merge conflict in shop.conf
Automatic merge failed; fix conflicts and then commit the result.
$ cat shop.conf
name = Bazar Mart
<<<<<<< HEAD
delivery_fee = 70
=======
delivery_fee = 50
>>>>>>> promo
cod = yes
free_over = 800
# (git merge --abort; git switch -c try-xours main)
$ git merge -X ours promo
Auto-merging shop.conf
Merge made by the 'ort' strategy.
 banner.txt | 1 +
 shop.conf  | 2 +-
 2 files changed, 2 insertions(+), 1 deletion(-)
 create mode 100644 banner.txt
$ cat shop.conf
name = Bazar Mart
delivery_fee = 70
cod = yes
free_over = 800
# (git switch -c try-xtheirs main)
$ git merge -X theirs promo
Auto-merging shop.conf
Merge made by the 'ort' strategy.
 banner.txt | 1 +
 shop.conf  | 4 ++--
 2 files changed, 3 insertions(+), 2 deletions(-)
 create mode 100644 banner.txt
$ cat shop.conf
name = Bazar Mart
delivery_fee = 50
cod = yes
free_over = 800
# (git switch -c try-sours main)
$ git merge -s ours promo
Merge made by the 'ours' strategy.
$ cat shop.conf
name = Bazar Mart
delivery_fee = 70
cod = yes
free_over = 1000
$ ls
shop.conf
$ git diff main try-sours --stat
$ git log --oneline --graph -3
*   77cd777 Merge branch 'promo' into try-sours
|\
| * d5cf90a Promo: fee 50, free over 800, banner
* | 4779563 Raise delivery fee to 70
|/
$ git merge -s theirs promo
Could not find merge strategy 'theirs'.
Available strategies are: octopus ours recursive resolve subtree.

// -X ours / -X theirs (OPTIONS) vs -s ours (a STRATEGY). Simplified: lines are only replaced.
function merge3(base, ours, theirs, opt, name) {
  const out = []; let conflicts = 0;
  for (let i = 0, j; i < base.length; i = j) {
    j = i;                                       // a hunk = a run of lines changed by anyone
    while (j < base.length && (ours[j] !== base[j] || theirs[j] !== base[j])) j++;
    if (j === i) { out.push(base[i]); j = i + 1; continue; }
    const b = base.slice(i, j).join("\n"), o = ours.slice(i, j).join("\n"), t = theirs.slice(i, j).join("\n");
    if (o === b) out.push(t);                    // only theirs changed this hunk
    else if (t === b || o === t) out.push(o);    // only ours, or both the same
    else if (opt === "ours") out.push(o);        // -X ours: conflicting hunk only
    else if (opt === "theirs") out.push(t);      // -X theirs: conflicting hunk only
    else { conflicts++; out.push("<<<<<<< HEAD\n" + o + "\n=======\n" + t + "\n>>>>>>> " + name); }
  }
  return { text: out.join("\n"), conflicts };
}
function mergeTrees(base, ours, theirs, mode) {  // a tree = { path: [lines] }
  if (mode === "-s ours") return { tree: ours, conflicts: 0 };   // ignore theirs entirely
  const tree = {}; let conflicts = 0;
  for (const p of new Set([...Object.keys(ours), ...Object.keys(theirs)])) {
    if (!base[p]) { tree[p] = (ours[p] || theirs[p]); continue; }  // added on one side only
    const r = merge3(base[p], ours[p], theirs[p], mode.replace("-X ", ""), "promo");
    tree[p] = r.text.split("\n"); conflicts += r.conflicts;
  }
  return { tree, conflicts };
}
const base = { "shop.conf": ["name = Bazar Mart", "delivery_fee = 60", "cod = yes", "free_over = 1000"] };
const ours = { "shop.conf": ["name = Bazar Mart", "delivery_fee = 70", "cod = yes", "free_over = 1000"] };
const theirs = { "shop.conf": ["name = Bazar Mart", "delivery_fee = 50", "cod = yes", "free_over = 800"],
                 "banner.txt": ["Eid sale!"] };
for (const mode of ["default", "-X ours", "-X theirs", "-s ours"]) {
  const r = mergeTrees(base, ours, theirs, mode);
  console.log("=== " + mode + " | files: " + Object.keys(r.tree).join(", ") + " | conflicts: " + r.conflicts);
  console.log(r.tree["shop.conf"].join("\n"));
}

$ git diff -M --summary HEAD~1 HEAD
 rename price.js => pricing.js (60%)
$ git diff -M --stat HEAD~1 HEAD
 price.js => pricing.js | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
# (git switch -c try-default main)
$ git merge fix
Auto-merging pricing.js
Merge made by the 'ort' strategy.
 pricing.js | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
$ grep -n 'return 50' pricing.js
7:  return 50;
# (git switch -c try-strict main)
$ git merge -X find-renames=90% fix
CONFLICT (modify/delete): price.js deleted in HEAD and modified in fix.  Version fix of price.js left in tree.
Automatic merge failed; fix conflicts and then commit the result.
$ git status --short
DU price.js

# Rename detection: pair a deleted path with an added path if their contents are similar enough.
from difflib import SequenceMatcher
old = {"price.js": """function vat(amount) {
  return amount * 0.15;
}
function delivery(total) {
  if (total >= 1000) return 0;
  return 60;
}
function discount(total) {
  return total * 0.05;
}
function round(x) {
  return Math.round(x);
}
"""}
new_pricing = "const VAT_RATE = 0.15;\n" + old["price.js"].replace("function vat(", "function vatOf(") \
    .replace("amount * 0.15", "amount * VAT_RATE").replace("function round(", "function roundTaka(")
new = {"pricing.js": new_pricing,
       "report.js": "function report(orders) {\n  return orders.length + ' orders';\n}\n"}

def similarity(a, b):        # bytes in matching lines / size of the bigger file (like Git)
    la, lb = a.splitlines(True), b.splitlines(True)
    blocks = SequenceMatcher(None, la, lb).get_matching_blocks()
    same = sum(len("".join(la[k.a:k.a + k.size])) for k in blocks)
    return same / max(len(a), len(b))

for threshold in (0.50, 0.90):
    print(f"threshold {threshold:.0%}:")
    for o, a in old.items():
        for n, b in new.items():
            s = similarity(a, b)
            verdict = "rename" if s >= threshold else "delete + add"
            print(f"  {o} -> {n:<11} similarity {s:4.0%}  {verdict}")
print("sizes:", {k: len(v) for k, v in {**old, **new}.items()})

$ git ls-files -s
100644 6ee16a42b20f8aa31b5ac040581a4a280505aeef 0	marks.txt
$ git merge recheck
Auto-merging marks.txt
CONFLICT (content): Merge conflict in marks.txt
Automatic merge failed; fix conflicts and then commit the result.
$ git ls-files -u
100644 6198895ad62944f7b3182daedcd17cac80e5eb80 1	marks.txt
100644 6ee16a42b20f8aa31b5ac040581a4a280505aeef 2	marks.txt
100644 46dc5afee4515e03146243e9f38b7cacd2fccb53 3	marks.txt
$ git show :1:marks.txt
roll = 7
name = Karim
bangla = 78
math = 90
$ git checkout --theirs marks.txt
Updated 1 path from the index
$ git ls-files -u
100644 6198895ad62944f7b3182daedcd17cac80e5eb80 1	marks.txt
100644 6ee16a42b20f8aa31b5ac040581a4a280505aeef 2	marks.txt
100644 46dc5afee4515e03146243e9f38b7cacd2fccb53 3	marks.txt
$ git checkout -m marks.txt
Recreated 1 merge conflict
$ cat marks.txt
roll = 7
name = Karim
<<<<<<< ours
bangla = 80
=======
bangla = 82
>>>>>>> theirs
math = 90
$ git checkout --theirs marks.txt
Updated 1 path from the index
$ git add marks.txt
$ git ls-files -s
100644 46dc5afee4515e03146243e9f38b7cacd2fccb53 0	marks.txt

$ git merge-file -p ours.txt base.txt theirs.txt; echo "exit=$?"
<<<<<<< ours.txt
tea = 12
=======
tea = 15
>>>>>>> theirs.txt
rice = 50
egg = 20
exit=1
$ git merge-file -p --diff3 -L ours -L base -L theirs ours.txt base.txt theirs.txt
<<<<<<< ours
tea = 12
||||||| base
tea = 10
=======
tea = 15
>>>>>>> theirs
rice = 50
egg = 20
$ git merge-file -p --theirs ours.txt base.txt theirs.txt
tea = 15
rice = 50
egg = 20
$ git merge-file -p --union ours.txt base.txt theirs.txt
tea = 12
tea = 15
rice = 50
egg = 20
# (theirs2.txt changes only egg = 18)
$ git merge-file ours.txt base.txt theirs2.txt; echo "exit=$?"
exit=0
$ cat ours.txt
tea = 12
rice = 50
egg = 18

$ git merge-tree --write-tree main promo; echo "exit=$?"
e3c4071da68d8b809f25f610d75e4df317371bc0
100644 5beb3cf3ec9caab08c6338306311d4b82dfd6287 1	shop.conf
100644 594a1b00215a233fe15f4bab22c245e9373c1cc7 2	shop.conf
100644 bc71ecf24355c8de85adbf4b0ed1346c33874a25 3	shop.conf

Auto-merging shop.conf
CONFLICT (content): Merge conflict in shop.conf
exit=1
$ git merge-tree --write-tree --name-only main promo
e3c4071da68d8b809f25f610d75e4df317371bc0
shop.conf

Auto-merging shop.conf
CONFLICT (content): Merge conflict in shop.conf
$ git show e3c4071:shop.conf
name = Bazar Mart
<<<<<<< main
delivery_fee = 70
=======
delivery_fee = 50
>>>>>>> promo
cod = yes
free_over = 800
$ git merge-tree --write-tree main readme; echo "exit=$?"
a91166ddc8e527da7ef467d9174d4c0bf42d4091
exit=0
$ git ls-tree $(git merge-tree --write-tree main readme)
100644 blob f4a02e4ca06d4f2b1c39877b68bcf0854db71725	README.md
100644 blob 594a1b00215a233fe15f4bab22c245e9373c1cc7	shop.conf
$ git commit-tree -p main -p readme -m 'Merge readme (server side)' $(git merge-tree --write-tree main readme)
44d31a9711a2988b86d8a28b68c01f41a67f2823
$ git status --short
$ git log --oneline -1
4779563 Raise delivery fee to 70

$ git config rerere.enabled true
# (git switch -c trial main)
$ git merge topic
Auto-merging shop.conf
CONFLICT (content): Merge conflict in shop.conf
Recorded preimage for 'shop.conf'
Automatic merge failed; fix conflicts and then commit the result.
$ git rerere status
shop.conf
$ git rerere diff
--- a/shop.conf
+++ b/shop.conf
@@ -1,8 +1,8 @@
 name = Bazar Mart
-<<<<<<<
-delivery_fee = 50
-=======
+<<<<<<< HEAD
 delivery_fee = 70
->>>>>>>
+=======
+delivery_fee = 50
+>>>>>>> topic
 cod = yes
 free_over = 1000
$ find .git/rr-cache -type f
.git/rr-cache/17c3f75953c55480055d848cf7dc2996db8b4e4d/preimage
# (edit shop.conf: delivery_fee = 55, remove the markers)
$ git add shop.conf
$ git commit -q --no-edit
Recorded resolution for 'shop.conf'.
$ find .git/rr-cache -type f
.git/rr-cache/17c3f75953c55480055d848cf7dc2996db8b4e4d/postimage
.git/rr-cache/17c3f75953c55480055d848cf7dc2996db8b4e4d/preimage

# (git switch topic)
$ git rebase main
Rebasing (1/1)Auto-merging shop.conf
CONFLICT (content): Merge conflict in shop.conf
error: could not apply f979c51... Topic: fee 50
hint: Resolve all conflicts manually, mark them as resolved with
…
Resolved 'shop.conf' using previous resolution.
Could not apply f979c51... # Topic: fee 50
$ cat shop.conf
name = Bazar Mart
delivery_fee = 55
cod = yes
free_over = 1000
$ git status --short
UU shop.conf
$ git add shop.conf
$ git rebase --continue
[detached HEAD e7042f7] Topic: fee 50
 1 file changed, 1 insertion(+), 1 deletion(-)
Successfully rebased and updated refs/heads/topic.
$ git show HEAD:shop.conf
name = Bazar Mart
delivery_fee = 55
cod = yes
free_over = 1000

// Toy rerere: remember "this conflict -> this resolution" and replay it next time.
function fnv1a(s) {                       // 32-bit FNV-1a; stands in for Git's SHA-1 here
  let h = 0x811c9dc5;
  for (const ch of s) { h ^= ch.charCodeAt(0); h = Math.imul(h, 0x01000193) >>> 0; }
  return h.toString(16).padStart(8, "0");
}
// Normalise like rerere: drop branch labels, sort the two sides so ours/theirs order is irrelevant.
function conflictId(sideA, sideB) {
  const [x, y] = [sideA, sideB].sort();
  return fnv1a("<<<<<<<\n" + x + "\n=======\n" + y + "\n>>>>>>>\n");
}
const rrCache = new Map();                // .git/rr-cache: id -> { preimage, postimage }
function onConflict(where, ours, theirs) {
  const id = conflictId(ours, theirs), entry = rrCache.get(id);
  if (entry && entry.postimage) {
    console.log(where + ": Resolved using previous resolution [" + id + "] -> " + entry.postimage);
    return entry.postimage;
  }
  if (!entry) rrCache.set(id, { preimage: [ours, theirs].sort(), postimage: null });
  console.log(where + ": Recorded preimage [" + id + "], please resolve by hand");
  return null;
}
function onCommit(ours, theirs, resolved) {   // rerere records the postimage when you commit
  rrCache.get(conflictId(ours, theirs)).postimage = resolved;
  console.log("commit: Recorded resolution -> " + resolved);
}
// 1) test merge of topic into main: fee 70 (ours) vs fee 50 (theirs)
if (!onConflict("merge  ", "delivery_fee = 70", "delivery_fee = 50"))
  onCommit("delivery_fee = 70", "delivery_fee = 50", "delivery_fee = 55");
// 2) rebase topic onto main: same conflict, but ours and theirs are swapped
onConflict("rebase ", "delivery_fee = 50", "delivery_fee = 70");
// 3) a different conflict gets a different id
onConflict("merge 2", "delivery_fee = 70", "delivery_fee = 45");
console.log("rr-cache entries:", rrCache.size);

$ git merge feat
Auto-merging CHANGELOG.md
CONFLICT (content): Merge conflict in CHANGELOG.md
Auto-merging app.lock
CONFLICT (content): Merge conflict in app.lock
warning: Cannot merge binary files: logo.png (HEAD vs. feat)
Auto-merging logo.png
CONFLICT (content): Merge conflict in logo.png
Automatic merge failed; fix conflicts and then commit the result.
$ git status --short
UU CHANGELOG.md
UU app.lock
UU logo.png
# (git merge --abort; commit a .gitattributes on main)
$ cat .gitattributes
CHANGELOG.md merge=union
app.lock merge=keepours
$ git config merge.keepours.name "Keep our lockfile, regenerate later"
$ git config merge.keepours.driver true
# (git switch -c try-attr main)
$ git merge feat
Auto-merging CHANGELOG.md
Auto-merging app.lock
warning: Cannot merge binary files: logo.png (HEAD vs. feat)
Auto-merging logo.png
CONFLICT (content): Merge conflict in logo.png
Automatic merge failed; fix conflicts and then commit the result.
$ git status --short
M  CHANGELOG.md
UU logo.png
$ cat CHANGELOG.md
# Changelog

- 1.1: eid discount
- 1.1: wallet payment
- 1.0: first release
$ cat app.lock
lock from main
$ git checkout --theirs logo.png
Updated 1 path from the index
$ git add logo.png
$ git status --short
M  CHANGELOG.md
M  logo.png