bigywater.tech
Git · 44

merge-base 怎么算出来的

git merge-base 是怎么找出两个分支的分叉点的?当历史里有交叉合并时它会返回几个?提交时间不准会不会出错?这篇用暴力集合运算在随机生成的 DAG 上逐对比对,再看 --fork-point 怎样借助 reflog 找回被强推改写之前的分叉点。

300 / 300
随机 DAG 上 git merge-base --all 与暴力算法一致的对子数,有无 commit-graph、时间戳乱序均如此
2 个
criss-cross 合并历史中最佳公共祖先的数量,git merge-base 不带 --all 只给 1 个
--fork-point
借助 origin/main 的 reflog 找到上游被强推之前的分叉点 U2;普通 merge-base 只能给出 U1

定义

实测 · 本机执行输出
  $ git log --graph --oneline --all | sed -E "s/[0-9a-f]{7} //"
  * F2
  * F1
  | * M3
  | * M2
  |/
  * M1
  * M0
  git merge-base main feature → M1
  用集合算:main 的祖先 ∩ feature 的祖先 = ['M0', 'M1'];其中不是别的公共祖先的祖先的那个,就是 merge-base

两个提交的公共祖先是它们祖先集合的交集;其中“最佳”的是那些不是其它公共祖先的祖先的提交。多数情况下只有一个,就是分叉点。

多个最佳基础

实测 · 本机执行输出
  $ git log --graph --oneline --all | sed -E "s/[0-9a-f]{7} //"
  * A2
  *   A 合并 B1
  |\
  | | * B2
  | | * B 合并 A1
  | |/|
  | |/
  |/|
  * | A1
  | * B1
  |/
  * R
  $ git merge-base A B | wc -l; git merge-base --all A B | wc -l; for c in $(git merge-base --all A B); do git log -1 --format="  最佳公共祖先: %s" $c; done
         1
         2
    最佳公共祖先: A1
    最佳公共祖先: B1

历史里有交叉合并(criss-cross)时,可能有多个互不为祖先的最佳公共祖先。git merge-base 不带 --all 只输出其中一个;--all 全部输出。合并时 ort 策略会处理多基础的情形。

与暴力算法对账

实测 · 本机执行输出
  时间戳正常递增:无 commit-graph 300/300 一致;写入 commit-graph 之后 300/300 一致;其中有 13 对存在多个最佳公共祖先
  时间戳乱序(±2 小时的偏差,模拟时钟不同步):无 commit-graph 300/300 一致;写入 commit-graph 之后 300/300 一致;其中有 50 对存在多个最佳公共祖先

在随机生成的 300 个提交的 DAG 上,300 对提交的 git merge-base --all 结果与暴力集合运算一致,不论有没有 commit-graph、提交时间是否乱序。时间戳只影响 git 内部的遍历顺序,不影响结果的正确性。

相关选项

实测 · 本机执行输出
  $ git merge-base --is-ancestor feature main; echo "feature 是 main 的祖先吗?退出码 $?"; git merge-base --is-ancestor main~2 main; echo "main~2 是 main 的祖先吗?退出码 $?"
  feature 是 main 的祖先吗?退出码 1
  main~2 是 main 的祖先吗?退出码 0
  $ git merge-base --octopus main feature third | xargs -I{} git log -1 --format="三个分支的公共祖先: %s" {}
  三个分支的公共祖先: M0
  $ git merge-base --independent main feature third main~1 | xargs -I{} git log -1 --format="  独立的(不是彼此祖先的)提交: %s" {}
    独立的(不是彼此祖先的)提交: M3
    独立的(不是彼此祖先的)提交: F2
    独立的(不是彼此祖先的)提交: T1

--is-ancestor 用退出码回答,--octopus 算多个分支的公共祖先,--independent 去掉是别人祖先的提交。

--fork-point

实测 · 本机执行输出
  上游把 U2 重写成 U2重写(强推)。topic 原来基于 U2。
  普通 git merge-base origin/main topic        → U1  (U1:两条历史唯一共同的祖先)
  git merge-base --fork-point origin/main topic → U2  (U2:用 origin/main 的 reflog 找到它旧的位置)
  $ git reflog show origin/main --format='%gd: %gs' | head -3
  origin/main@{0}: fetch -q origin: forced-update
  rebase --onto 的典型用法:git rebase --onto origin/main $(git merge-base --fork-point origin/main topic) topic

上游被 rebase 或强推后,提交图里只剩更早的共同祖先。--fork-point 额外参考上游分支的 reflog,找到这个分支开出去时上游所在的位置,用于 git rebase --onto。

分步演示

merge-base
本步的对象

    本文用到的工具与边界

    • 本机 macOS 27 arm64 / git 2.54.0(Apple Git-157);每个实验在临时目录里新建仓库,HOME 和全局配置指向实验专用的空目录(不读用户自己的 git 配置),提交的作者与时间固定以便复现;需要网络协议的实验用本机的 file:// 或 git daemon 回环端口(9800 以上),不碰任何远程仓库;计时用 time.perf_counter,数字每次运行会有小幅抖动。随机 DAG 由 git fast-import 生成(固定种子),暴力算法是 Python 集合运算;时间戳乱序是给每个提交的 committer 时间加 ±7200 秒的随机偏差;--fork-point 一节的提交使用真实时间(reflog 依赖时间)
    • 没有验证:更大的 DAG(几万提交)上 git 的遍历性能;三个以上 parent 的章鱼合并作为 merge-base 候选的情形;ort 策略如何把多个基础合成虚拟基础(只在文字上提及);--fork-point 在 reflog 过期之后的行为
    京ICP备2026067502号-1京公网安备11010502063487号