39

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

我很好奇，这样的程序是如何绘制git log --graph或hg graphlog绘制历史的？我一直认为以如此好的方式绘制车道和所有内容非常复杂。

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

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

4

4 回答 4

7

First, one obtains a list of commits (as with git rev-list), and parents of each commit. A "column reservation list" is kept in memory.

For each commit then:

  • If the commit has no column reserved for it, assign it to a free column. This is how the branch heads will start.
  • Print the tree graphics according to the column reservation list, and then the commit message
  • The reservation's list entry for the current column/commit is updated with the first parent of the current commit, such that the parent is going to be printed in the same column.
  • Other parents get a new free column.
  • If this was a merge, the next line will try to link the second parent to a column where the commit is expected (this makes for the loops and the "≡ bridge")

Example showing output of git-forest on aufs2-util with an extra commit to have more than one branch).

Example

With lookahead, one can anticipate how far down the merge point will be and squeeze the wood between two columns to give a more aesthetically pleasing result.

于 2011-02-15T14:45:58.380 回答
5

I tried looking around Git or hg's code but it's very hard to follow and get a general idea of what's going on.

For hg, did you try to follow the code in hg itself, or in graphlog?

Because the code of graphlog is pretty short. You can find it in hgext/graphlog.py, and really the important part is the top ~200 lines, the rest is the extension's bootstrapping and finding the revision graph selected. The code generation function is ascii, with its last parameter being the result of a call to asciiedge (the call itself is performed on the last line of generate, the function being provided to generate by graphlog)

于 2011-02-15T12:22:48.413 回答
4

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

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

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

合并边缘时，您希望避免与其他边缘交叉，因此您必须尝试提前订购列。这实际上是唯一可能不直截了当的部分。例如，可以做一个双通道算法，在第一个通道中为边缘制作一个列顺序，并在第二个通道中进行绘图。

于 2011-01-19T20:48:42.143 回答
1

注意：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

See commit 7547b95 , commit 3d5df01 , commit 049d51a , commit 177722b , commit 4f2542b , commit 1b70dfd , commit 2a2e32b (10 Apr 2018), and commit f237c8b , commit 08fd81c , commit 4ce58ee , commit ae30d7b , commit b84f767 , commit cfe8321 , commit f2af9f5 (02 2018 年 4 月）由Derrick Stolee ( derrickstolee)撰写。
（由Junio C Hamano 合并 -- gitster--在提交 b10edb2中，2018 年 5 月 8 日）

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

根据 packfiles 中的提交编写提交图文件。
包括来自现有提交图文件的所有提交。

设计文件指出：

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

  1. 列出和过滤提交历史。
  2. 计算合并基地。

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

这里有两个主要成本：

  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 branch -vv
git merge-base -a $BRANCH $COMPARE

这将提高git log性能。

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

请参阅提交 33286dc（2018 年 5 月 10 日），提交 1472978，提交 7adf526，提交 04bc8d1，提交 d7c1ec3，提交 f9b8908，提交 819807b，提交 e2838d8，提交 3afc679，提交 3258c66（2018 年 5 月 1 日，2018 年7 月 1 日，4 月8 日）和提交 8fb cc 2018) 由Derrick Stolee ( derrickstolee)撰写。
帮助者：Jeff King ( peff)。
（由Junio C Hamano 合并gitster——在提交 a856e7d中，2018 年 6 月 25 日）

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

我们使用 lockfile API 来避免多个 Git 进程写入.git/objects/info目录中的 commit-graph 文件。
在某些情况下，这个目录可能不存在，所以我们检查它是否存在。

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

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

问题是，如果 lockfile 存在，那么 mkdir 会失败，给出一个对用户没有帮助的错误：

"fatal: cannot mkdir .git/objects/info: File exists"

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

相反，请执行以下操作：

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

新输出如下所示：

fatal: Unable to create
'<dir>/.git/objects/info/commit-graph.lock': File exists.

Another git process seems to be running in this repository, e.g.
an editor opened by 'git commit'. 
Please make sure all processes are terminated then try again. 
If it still fails, a git process may have crashed in this repository earlier:
remove the file manually to continue.

注意：当涉及从未知类型提升为提交的核心对象（例如，通过引用它的标签访问的提交）时，提交图工具不起作用，这已在 Git 2.21（2 月. 2019)

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

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

请参阅提交 238def5、提交 f998d54、提交 014e344、提交 b2c8306、提交 4c9efe8、提交 ef5b83f、提交 c9905be、提交 10bd0be、提交 5af8039、提交 e103f72（2019 年 6 月 12 日）和提交 c794405 （derrickstolee 201 年 5 月 9 日）。
（由Junio C Hamano 合并 -- gitster--在提交 e116894中，2019 年 7 月 9 日）

提交 10bd0be解释范围的变化。

在 Git 2.24 (Q3 2109) 中，重写给commit-graph定提交对象名称的代码变得更加健壮。

请参阅SZEDER Gábor ( ) 的提交 7c5c9b9、提交 39d8831、提交 9916073（2019 年 8 月 5 日）。（由Junio C Hamano 合并——在提交 6ba06b5中，2019 年 8 月 22 日）szeder
gitster

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

请参阅Taylor Blau ( )的提交 806278d、提交 16749b8、提交 23424ea（2019 年 9 月 5 日） 。（由Junio C Hamano 合并 -- --在提交 80693e3中，2019 年 10 月 7 日）ttaylorr
gitster

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'）。
如果 ' *list' 导致解析错误，则后续调用将失败。

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

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

请参阅Taylor Blau ( ) 的提交 a7df60c、提交 ad2dd5b、提交 13c2499（2020 年 2 月 3 日）、提交 0bd52e2（2020 年 2 月 4 日）和提交 1793280（2020 年 1 月 30 日）。（由Junio C Hamano 合并 -- --在提交 53c3be2中，2020 年 2 月 14 日）ttaylorr
gitster

commit-graph.hwrite_commit_graph_context: 在 'struct '中存储一个 odb

签字人：Taylor Blau

在很多地方commit-graph.h，一个函数要么有（或几乎有）一个完整的struct object_directory * , accesses ->path`，然后丢弃结构的其余部分。

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

通过在结构中存储 a来替换char *object_dirwith的使用。 这是摆脱“ ”中所有路径规范化的中间步骤。odb->pathstruct object_directory* write_commit_graph_context
commit-graph.c

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

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

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

使用 Git 2.28（2020 年第三季度）进行了commit-graph write --stdin-commits优化。

请参阅Taylor Blau的提交 2f00c35 、提交1f1304d、提交 0ec2d0f、提交 5b6653e、提交 630cd51、提交 d335ce8（2020 年 5 月 13 日）、提交 fa8953c（2020 年 5 月 18 日）和提交 1fe1084（2020 年 5 月 5 日），作者为Taylor Blau ( ttaylorr)。
（由Junio C Hamano 合并 -- gitster--在dc57a9b 提交中，2020 年 6 月 9 日）

commit-graph: 丢弃COMMIT_GRAPH_WRITE_CHECK_OIDS标志

帮助者：Jeff King
签字者：Taylor Blau

自7c5c9b9c57（“ commit-graph：错误输出在 ' write --stdin-commits' 中的无效提交 oid”，2019-08-05，Git v2.24.0-rc0 -批次 #1中列出的合并），commit-graph builtin 在接收非提交 OID 时死亡作为' '的输入。--stdin-commits

如果调用者不想自己剔除未提交，则此行为可能很麻烦，例如，在管道 ' git for-each-ref' 到 ' ' 的情况下。git commit-graph write --stdin-commits在这种情况下，如果“git commit-graph写”写出包含与提交相关的输入的图表，并且默默地忽略输入的其余部分，那将是理想的。

已经提出了一些选项来达到 ' --[no-]check-oids' 的效果，这将允许调用者让内置的 commit-graph 做到这一点。
经过一番讨论，很难想象一个调用者不想通过' --no-check-oids'，建议我们应该完全摆脱抱怨未提交输入的行为。

如果调用者确实希望保留此行为，他们可以通过执行以下操作轻松解决此更改：

git for-each-ref --format='%(objectname) %(objecttype) %(*objecttype)' |
awk '
  !/commit/ { print "not-a-commit:"$1 }
   /commit/ { print $1 }
' |
git commit-graph write --stdin-commits

为了使引用不存在对象的有效 OID 在放松错误处理后确实是一个错误，请在将对象发送到提交图内部之前执行额外的查找以确保该对象确实存在。

这是使用 Git 2.28（2020 年第三季度）进行测试的。

请参阅Taylor Blau ( ) 的提交94fbd91 （ 2020 年 6 月 1 日）和提交 6334c5f（2020 年 6 月 3日）。（由Junio C Hamano 合并 -- --在abacefe 提交中，2020 年 6 月 18 日）ttaylorr
gitster

t5318：测试' --stdin-commits'尊重' --[no-]progress'

签字人：Taylor Blau
签字人：Derrick Stolee

最近针对 Git 的线路覆盖测试未涵盖以下行：

builtin/commit-graph.c
5b6653e5 244) progress = start_delayed_progress(
5b6653e5 268) stop_progress(&progress);

这些语句在 ' --stdin-commits' 和 ' --progress' 都通过时执行。引入三个测试，对这些选项进行各种组合，以确保覆盖这些行。

更重要的是，这是在行使 ' ' 的一个（某种程度上）以前被忽略的特性，--stdin-commits即它尊重 ' --progress'。

在5b6653e523之前（“ [builtin/commit-graph.c ](https://github.com/git/git/blob/94fbd9149a2d59b0dca18448ef9d3e0607a7a19d/builtin/commit-graph.c）：在 builtin 中取消引用标签”，2020-05-13，Git v2 .28.0 -批次#2中列出的合并），取消引用来自“ ”的输入是在.--stdin-commitscommit-graph.c

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

生成进度表输出的另一个位置（来自d335ce8f24（“ [commit-graph.c ](https://github.com/git/git/blob/94fbd9149a2d59b0dca18448ef9d3e0607a7a19d/commit-graph.c）：显示查找可达提交的进度”，2020- 05-13，Git v2.28.0 -批次 #2中列出的合并））已经被任何通过“ ”的测试所覆盖。--reachable

在 Git 2.29（2020 年第四季度）中，in_merge_bases_many() 是一种查看是否可以从一组提交中的任何提交访问提交的方法，在使用提交图功能时完全被破坏了，该功能已得到纠正。

请参阅Derrick Stolee ( ) 的提交 8791bf1（2020 年 10 月 2 日）。（由Junio C Hamano 合并 -- --在提交 c01b041中，2020 年 10 月 5 日）derrickstolee
gitster

commit-reach: 修复in_merge_bases_many错误

报告人：Srinidhi Kaushik
帮助人：Johannes Schindelin
签字人：Derrick Stolee

回到f9b8908b（“ [commit.c ](https://github.com/git/git/blob/8791bf18414a37205127e184c04cad53a43aeff1/commit.c）：使用in_merge_bases()代号”，2018-05-01，Git v2.19.0-rc0 --合并在批次#1中列出），使用启发式方法来缩短in_merge_bases()步行。
只要调用者只检查两个提交，这就可以正常工作，但是当有多个提交时，这种启发式可能是非常错误的。

此后的一些代码移动已将此方法更改为repo_in_merge_bases_many()inside commit-reach.c。启发式计算“参考”列表的最小代数，然后将该数字与“提交”的代数进行比较。

在最近的一个主题中，添加了一个测试，用于in_merge_bases_many()测试是否可以从 reflog 中提取的多个提交中访问该提交。但是，这突出了问题：如果任何参考提交的代号小于给定的提交，则_even如果存在具有更高代号的部分，则跳过遍历。

这种启发式是错误的！它必须检查参考提交的 MAXIMUM 代数，而不是 MINIMUM。

修复本身是min_generation与max_generationin交换repo_in_merge_bases_many()。

在 Git 2.32 hopefullu (Q1 2021) 之前，当存储库中使用的某些特性（例如嫁接）与 commit-graph 的使用不兼容时，我们习惯于默默地关闭 commit-graph；我们现在告诉用户我们在做什么。

请参阅Johannes Schindelin ( ) 的commit c85eec7（2021 年 2 月 11 日）。（由Junio C Hamano 合并 -- --在提交 726b11d中，2021 年 2 月 17 日）dscho
gitster

这将显示 Git 2.31 的用途，但它已被恢复，因为它在当前形式下有点过分热心。

commit-graph：当与图表不兼容时，说明原因

签字人：Johannes Schindelin
签字人：Derrick Stolee

当 时gc.writeCommitGraph = true，提交图可能仍未写入：替换对象、移植和浅存储库与提交图功能不兼容。

在这种情况下，我们需要向用户说明为什么没有编写提交图，而不是保持沉默。

警告将是：

repository contains replace objects; skipping commit-graph
repository contains (deprecated) grafts; skipping commit-graph
repository is shallow; skipping commit-graph
于 2018-05-10T14:39:37.473 回答