“git log --graph”如何实现？或“hg graphlog”工作？

Question

我知道 Git 中的历史记录存储在称为 DAG 的数据结构中。我听说过 DFS 并且知道它有些相关。

我很好奇，git log --graph 或 hg graphlog 等程序如何绘制历史记录？我一直认为以如此漂亮的方式绘制车道和所有东西是相当复杂的。

有人可以写一些伪代码来演示它吗？

注意：我尝试查看 Git 或 hg 的代码，但很难理解并大致了解正在发生的事情。

Answer 1

首先，获取提交列表（与 git rev-list 一样）以及每个提交的父项。内存中保存有“列保留列表”。

对于每个提交，然后：

• 如果提交没有为其保留列，则将其分配给空闲列。这就是支部负责人的开始方式。
• 根据列保留列表打印树形图形，然后打印提交消息
• 当前列/提交的保留列表条目将使用当前提交的第一个父级进行更新，以便父级将在同一列中打印。
• 其他家长可以获得新的免费专栏。
• 如果这是合并，下一行将尝试将第二个父级链接到预期提交的列（这会产生循环和“i 桥”）

显示 git-forest 输出的示例> 在 aufs2-util 上进行额外提交以拥有多个分支）。

通过前瞻，人们可以预测合并点将有多远，并在两根柱子之间挤压木材，以获得更美观的结果。

Answer 2

我尝试查看 Git 或 hg 的代码，但很难跟踪并大致了解正在发生的事情。

对于 hg，您是否尝试遵循 hg 本身或 graphlog 中的代码？

因为graphlog的代码很短。您可以在 hgext/graphlog.py 中找到它，实际上，最重要的部分是前 200 行，其余部分是扩展的引导和查找选定的修订图。代码生成函数是 ascii，其最后一个参数是调用 asciiedge 的结果（调用本身在 generate 的最后一行执行） code>，由 graphlog 提供给 generate 的函数）

Answer 3

与一般的图形显示相比，这个特殊问题并不难。因为您希望保持节点的提交顺序，所以问题变得更加简单。

另请注意，显示模型是基于网格的，行是提交，列是过去/未来的边缘。

虽然我没有阅读 git 源代码，但您可能只是从最新的开始遍历提交列表，并维护过去的开放边缘列表。沿着边缘自然会导致拆分/合并列，最终会得到树 git/hg 显示的类型。

合并边时，您希望避免交叉其他边，因此您必须尝试提前对列进行排序。这实际上是唯一可能不简单的部分。例如，可以执行双遍算法，在第一遍中为边缘制定列顺序，并在第二遍中进行绘图。

Answer 4

注意：Git 2.18（2018 年第 2 季度）现在会预先计算祖先遍历所需的信息并将其存储在单独的文件中，以优化图形遍历。

提交图的概念确实改变了“git log --graph”的工作方式。

正如此处提到：

git config --global core.commitGraph true
git config --global gc.writeCommitGraph true
cd /path/to/repo
git commit-graph write

请参阅提交 7547b95，提交 3d5df01，< a href="https://github.com/git/git/commit/049d51a2bb9a03d2f2c2cce1ae41e57dbbf42244" rel="nofollow noreferrer">提交 049d51a, 提交 177722b，提交 4f2542b< /a>, 提交 1b70dfd, 提交 2a2e32b（2018 年 4 月 10 日），以及 提交 f237c8b，提交 08fd81c， 提交 4ce58ee，提交 ae30d7b, 提交 b84f767 ，提交cfe8321，提交 f2af9f5（2018 年 4 月 2 日），作者：德里克·斯托利 (derrickstolee)。
^{（由 Junio C Hamano -- gitster -- 合并于 提交 b10edb2，2018 年 5 月 8 日）}

您现在拥有命令 git commit-graph：编写并验证 Git 提交图形文件。

根据包文件中找到的提交编写提交图文件。
包括现有提交图文件中的所有提交。

设计文档指出：

Git 遍历提交图的原因有很多，包括：

1. 列出并过滤提交历史记录。
2. 计算合并基础。

随着提交计数的增加，这些操作可能会变慢。合并
基数计算出现在许多面向用户的命令中，例如“merge-base”
或“状态”，并且可能需要几分钟的时间来计算，具体取决于历史记录的形状。

这里有两个主要成本：

1. 解压缩并解析提交。
2. 遍历整个图以满足拓扑顺序约束。

提交图文件是一种补充数据结构，可以加速
提交图行走。
如果用户降级或禁用“core.commitGraph”配置设置，则现有 ODB 就足够了。

该文件以“commit-graph”形式存储在 .git/objects/info 目录或备用目录的 info 目录中。

提交图文件存储提交图结构以及一些
额外的元数据可以加速图形遍历。
通过按字典顺序列出提交 OID，我们可以识别每个提交的整数位置，并使用这些整数位置引用提交的父级。
我们使用二分搜索来查找初始提交，然后使用整数位置
用于在行走过程中快速查找。

您可以看到测试用例：

git log --oneline $BRANCH
git log --topo-order $BRANCH
git log --graph $COMPARE..$BRANCH
git 分支 -vv
git merge-base -a $BRANCH $COMPARE

这将提高git log性能。

---

在 Git 2.39（2022 年第 4 季度）中，添加了“提交图文件”和“可达性位图”的术语表条目。

请参阅提交8fea12a，提交 4973726，提交fa8e8d5，提交 776ba91（2022 年 10 月 29 日），作者：菲利普·奥克利 (PhilipOakley)。
^{（由 Taylor Blau -- ttaylorr -- 合并于 提交 4b6302c，2022 年 11 月 8 日）}

词汇表：添加可达性位图描述

^{签字人：Philip Oakley
签字人：Taylor Blau}

描述可达性位图的用途。

glossary-content 现在包含在其 手册页：

可达性位图

可达性位图存储有关
中选定的一组提交的可达性
包文件或多包索引 (MIDX)，以加速对象搜索。
位图存储在“.bitmap”文件中。
存储库可能位于
使用最多的一个位图文件。
位图文件可以属于任一
pack，或存储库的多包索引（如果存在）。

和：

词汇表：添加“提交图”描述

^{签字人：Philip Oakley
签字人：Taylor Blau}

Git 有一个额外的“提交图”功能，可以补充普通提交对象的有向无环图 (DAG)。
补充提交图文件是为了提高访问速度而设计的。

从规范 DAG 角度和提交图文件角度描述提交图。

此外，通过链接到与此提交图条目匹配的 ref 术语表条目来阐明分支引用和分支提示之间的链接。

提交图文件也通过它的连字符来区分。

后续提交会捕获提交图连字符丢失的少数情况。

glossary-content 现在包含在其 手册页：

提交图概念、表示和用法

由提交形成的 DAG 结构的同义词
在对象数据库中，由分支提示引用，
使用他们的链接提交链。
该结构是最终的提交图。这
图可以用其他方式表示，例如
“提交图”文件。

提交图文件

“commit-graph”（通常用连字符连接）文件是补充文件
提交图的表示
这加速了提交图的遍历。
“提交图”文件是
存储在 .git/objects/info 目录或 info 中
备用对象数据库的目录。

---

Git 2.19（2018 年第 3 季度）将处理锁定文件：

请参阅 commit 33286dc ( 2018 年 5 月 10 日），提交 1472978，提交 7adf526，提交 04bc8d1，提交 d7c1ec3，提交f9b8908，提交 819807b，提交 e2838d8， 提交 3afc679，提交 3258c66 （2018 年 5 月 1 日），以及 提交 83073cc，提交 8fb572a（2018 年 4 月 25 日）作者：Derrick Stolee (derrickstolee)。
帮助者：Jeff King (peff)。
^{（由 Junio C Hamano -- gitster -- 合并于 提交 a856e7d，2018 年 6 月 25 日）}

commit-graph：修复 .lock 文件存在时的 UX 问题

我们使用锁文件 API 来避免多个 Git 进程写入
.git/objects/info 目录中的提交图文件。
在某些情况下，该目录可能不存在，因此我们检查它是否存在。

现有代码在获取锁时执行以下操作：

1. 尝试获取锁。
2. 如果失败，请尝试创建 .git/object/info 目录。
3. 尝试获取锁，必要时会失败。

问题是，如果锁文件存在，则 mkdir 失败，给出
对用户没有帮助的错误：

“致命：无法 mkdir .git/objects/info：文件存在”

虽然从技术上讲这尊重锁定文件，但它对用户没有帮助。

相反，请执行以下操作：

1. 检查.git/objects/info是否存在；如有必要，请创建。
2. 尝试获取锁，必要时会失败。

新输出如下所示：

致命：无法创建
'/.git/objects/info/commit-graph.lock'：文件存在。

另一个 git 进程似乎正在这个存储库中运行，例如
由“git commit”打开的编辑器。 
请确保所有进程都已终止，然后重试。 
如果仍然失败，则 git 进程可能之前在此存储库中崩溃了：
手动删除文件以继续。

---

注意：当核心对象
从未知类型提升到提交（例如，提交是
通过引用它的标签访问）涉及，这已经
使用 Git 2.21 更正（2019 年 2 月）

请参阅 commit 4468d44（2019 年 1 月 27 日） SZEDER Gábor (szeder)。
^{（由 Junio C Hamano -- gitster -- 合并于 提交 2ed3de4，2019 年 2 月 5 日）}

---

该算法正在 Git 2.23 中重构（ 2019 年第三季度）。

请参阅提交238def5，提交 f998d54, 提交014e344，提交b2c8306，提交 4c9efe8, 提交 ef5b83f，提交 c9905be，提交 10bd0be，提交 5af8039，提交 e103f72 （2019 年 6 月 12 日），以及提交 c794405（2019 年 5 月 9 日），作者：Derrick Stolee (derrickstolee)。
^{（由 Junio C Hamano -- gitster -- 合并于 提交 e116894，2019 年 7 月 9 日）}

Commit 10bd0be 解释范围的变化。

---

在 Git 2.24（2109 年第 3 季度）中，通过给定提交对象名称编写commit-graph 的代码变得更加健壮。

请参阅 提交 7c5c9b9、提交 39d8831, 提交9916073（2019 年 8 月 5 日），作者：SZEDER Gábor (szeder)。
^{（由 Junio C Hamano -- gitster -- 合并于 提交 6ba06b5，2019 年 8 月 22 日）}

---

而且，仍然使用 Git 2.24（2019 年第 4 季度 ） ），解析和使用提交图文件的代码针对损坏的输入变得更加健壮。

请参阅 提交 806278d、提交 16749b8, 提交23424ea（2019 年 9 月 5 日），作者：Taylor Blau (ttaylorr)。
^{（由 Junio C Hamano -- gitster -- 合并于 提交 80693e3，2019 年 10 月 7 日）}

t/t5318：引入失败的“git commit-graph write”测试

在损坏的存储库中调用“git commit-graph”时，如果祖先提交以某种方式损坏，可能会导致段错误。
这是由于“commit-graph.c”代码中的两个函数调用可能导致
返回NULL，但在取消引用之前不检查是否为 NULL。

因此：

commit-graph.c：处理提交解析错误

要写入提交图块，“write_graph_chunk_data()”会获取要写入的提交列表，并在写入必要的数据之前解析每个提交，然后继续处理列表中的下一个提交。

由于这些提交中的大多数都不会提前解析（列表中的最后提交是一个例外，它在“copy_oids_to_commits”中提前解析） ），对它们调用“parse_commit_no_graph()”可能会返回错误。
在取消引用后续调用之前未能捕获这些错误可能会导致未定义的内存访问和 SIGSEGV。
²
一个这样的示例是“get_commit_tree_oid()”，它期望一个已解析的对象作为其输入（在本例中，commit-graph 代码传递“*列表')。
如果“*list”导致解析错误，则后续调用将失败。

通过检查“parse_commit_no_graph()”的返回值来防止此类问题，以避免将未解析的对象传递给需要已解析对象的函数，从而防止段错误。

---

在 Git 2.26（2020 年第一季度）中，计算提交图的代码已被教导使用更强大的方法来判断两个对象目录是否引用同一事物。

请参阅提交a7df60c，提交 ad2dd5b, 提交13c2499（2020 年 2 月 3 日），提交 0bd52e2（2020 年 2 月 4 日） ，以及 提交 1793280（2020 年 1 月 30 日），作者：泰勒·布劳 (ttaylorr)。
^{（由 Junio C Hamano -- gitster -- 合并于 提交 53c3be2，2020 年 2 月 14 日）}

commit-graph.h：存储'struct write_commit_graph_context' 中的odb

^{签字人：Taylor Blau}

commit-graph 中有很多地方。 h，其中函数具有（或几乎具有）完整的 struct object_directory *，访问 ->path`，然后丢弃结构的其余部分。

在比较备用对象目录的位置时（例如，在决定是否可以合并两个提交图层的情况下），这可能会导致头痛。
这些路径使用 normalize_path_copy() 进行标准化，这可以缓解一些比较问题，但不是全部1。

通过在 write_commit_graph_context 中存储 struct object_directory* ，将 char *object_dir 的用法替换为 odb->path代码>结构。
这是摆脱 'commit-graph.c'.

现在解析用户提供的“--object-dir”参数需要我们将其与已知的替代项进行比较以确保相等。

在此补丁之前，未知的“--object-dir”参数会以状态零静默退出。

这显然会导致意外的行为，例如验证不在存储库自己的对象存储（或其替代对象存储之一）中的提交图，或者导致拼写错误掩盖合法的提交图验证失败。< br>
当给定的“--object-dir”与任何已知的备用对象存储不匹配时，通过“die()”-ing 使此错误变得非静默。

---

在 Git 2.28（2020 年第 3 季度）中，commit-graph write --stdin-commits 得到了优化。

请参阅 提交 2f00c35、提交 1f1304d, 提交 5b6653e，提交 630cd51，提交 d335ce8（2020 年 5 月 13 日），提交 fa8953c （2020 年 5 月 18 日），以及 提交 1fe1084（2020 年 5 月 05 日），作者：泰勒·布劳 (ttaylorr)。
^{（由 Junio C Hamano -- gitster -- 合并于 提交 dc57a9b，2020 年 6 月 9 日）}

commit-graph：删除 COMMIT_GRAPH_WRITE_CHECK_OIDS 标志

^{帮助者：杰夫·金
签字人：Taylor Blau}

以来写入-stdin-commits '“”，2019-08-05中，在无效的commit oids上出现错误/git/git/commit/6BA06B582BCF0FB4AFA9FCC7D265005EB20CD50F“ rel =“ nofollow noreferrer”> Merge 98F776C26“ rel =“ nofollow noreferrer” >批次＃1 ），commit-graph内置因接收非委托OID作为' - stdin-commits '。

输入

这种行为可能很麻烦，例如，' git for-each-ref 'to' git commit-git-graph 写'写了包含与提交有关的输入的图表，并默默地忽略了输入的其余部分。

已经提出了一些选项，以实现' - [no-] check-ods '，这将使呼叫者能够让commit-graph hildiN添加。

经过一番讨论，很难想象一个不想通过'的来电者-No-Check-ods '，这表明我们应该摆脱抱怨非招称的行为完全输入。

如果呼叫者确实希望保留此行为，则可以通过以下几种操作来轻松解决此更改：

  git for-each-ref -format ='％（objectName）％（objectType）％（*objectType）'|
尴尬'
  ！/ commit/ {print“ not-a-commit：” $ 1}
   / commit/ {打印$ 1}
' |
git commit-graph写作-stdin-commits

使其成为指向不存在的对象的有效OID在松开错误处理后确实是错误p>

用GIT 2.28（Q3 2020）对此进行了测试。

参见 commits 6334c5f （03 Jun 2020）（03 Jun 2020） nofollow noreferrer“> taylor blau（ ttaylorr ）。
^{（由 Junio C Hamano -- gitster -- 合并于}

'尊重'<代码> - [no-] progress '

^{签名：泰勒·布劳
Acked-by：Derrick Stolee}

最近针对GIT的线覆盖测试中未涵盖以下几行：

 内置/commit-graph.c
5B6653E5 244）progress = start_delayed_progress（
5B6653E5 268）stop_progress（＆amp; progress）;

当两个' - stdin-commits '和' - progress '被传递时，这些语句将执行。介绍三个测试，这些测试可以遵守这些选项的各种组合，以确保涵盖这些线路。

更重要的是，这是在' - stdin-commits '的（某种程度上）的（某种程度上）的功能，即它尊重' - progress ' .

]（https ：//github.com/git/git/git/blob/94fbd9149a2d59b0dca1844484848ef9d3e0607a7a7a19d/builtin/builtin/builtin/commit-graph.c） ，git v2.28.0- batch＃2 ），从' stdin-comports nide of of code

现在，可以从 commit-graph.c ，添加一个相应的测试，以确保它也尊重' - [no] -progress '。

另一个生成进度仪表输出的位置（从 [ commit-graph.c ]（https ：//github.com/git/git/git/blob/94fbd9149a2d59b0dca184444848484848484848ef9d3e0607a7a7a19d/commit-graph.c） ，2020-05-13，git v2.28.0- '。

---

使用GIT 2.29（Q4 2020），IN_Merge_Bases_Many（）是一种查看一组提交中任何提交是否可以达到提交的方法，当使用了提交订单 - 格拉普功能（已纠正）时，已完全破坏。

参见 noreflowl noreferrer“> commit github.com/derrickstolee“ rel =“ nofollow noreferrer”> derrick stolee（ derrickstolee ）。
^{（由 Junio C Hamano -- gitster -- 合并于}

bug

^{报告：srinidhi kaushik
帮助：约翰内斯·辛德林
签名：Derrick Stolee}

返回]（https ：//github.com/git/git/git/blob/8791bf18414a37205127E184C04C04CAD53A43AEFF1/COMMIT.C）： 05-01，git v2.19.0-rc0- nofollow noreferrer“> batch＃1 ） /代码>步行。
只要呼叫者仅检查两次提交，这种情况就可以正常工作，但是当有多个提交时，这种启发式可能是非常错误的。

。

自那时以来，某些代码移动已将此方法更改为 repo_in_merge_bases_many（） commit-reach.c 。启发式计算“参考”列表的最小生成数，然后将此数字与“ commit”的生成编号进行比较。

在最近的主题中，添加了一个测试，该测试使用 in_merge_bases_many（）来测试是否可以从从反射仪中提取的许多提交中达到提交。但是，这突出了问题：如果任何参考提交的生成号都比给定提交较小，则步行会跳过 _even 如果存在一些具有较高生成号码_。

的wall。

这个启发式是错误的！它必须检查参考提交的最大生成数，而不是最低。

修复本身是 min_generation 与 max_generation in repo_in_merge_merge_bases_many（）。

---

在GIT 2.32（Q1 2021）之前，当存储库中使用的某些功能（例如移植物）与使用提交图的使用不符时，我们过去曾默默关闭提交图形；现在，我们告诉用户我们在做什么。

参见 johannes schindelin（ dscho ）。
^{（由 Junio C Hamano -- gitster -- 合并于 noreflow noreferrer“}

> ，但是

noreflow noreferrer”> ，指示为什么

^{签名：Johannes Schindelin
Acked-by：Derrick Stolee}

当 gc.writecommitgraph = true 时，提示图可能是 stall 未写的：替换对象，移植物和浅库库与commit-图形功能。

在这种情况下，我们需要向用户表明为什么未写下提交图片而不是对此保持沉默。

警告将是：

 存储库包含替换对象；跳过提交图
存储库包含（不推荐的）移植物；跳过提交图
存储库很浅；跳过提交图