"git log --graph"或"hg graphlog"是如何工作的？"

Question

"git log --graph"或"hg graphlog"是如何工作的？"

gitalgorithmgithubmercurialdirected-acyclic-graphs

40

我知道Git中的历史记录存储在一个叫做DAG的数据结构中。我听说过DFS，并知道它与此有些关系。

我想知道，像git log --graph或hg graphlog这样的程序如何绘制历史记录？我一直认为在这样的漂亮方式下绘制车道和其他东西相当复杂。

能否有人编写一些伪代码来演示它？

注意：我尝试查看Git或hg的代码，但很难理解并获得一个总体的想法。

- daniel.jackson

6

这是Git的graph.c文件，可供参考。 - Josh Lee

2

在 Stack Overflow 上发布一个简化但规范的“如何将 DAG 显示为文本图形”的问题，并将其标记为 code-golf。你会得到许多聪明的解决方案，包括 Python、Ruby、C、Perl 等语言。你可以要求人们发布他们的原始非 code-golf 版本代码以及他们“挤出每一个字符”的版本。 - Tyler

1

此外，Git的历史图形API也非常有用。 - Josh Lee

@Josh Lee的回答提供了API、用法和示例。通过这些，你应该能够理解git log --graph是如何操作的。你也可以在api-history-graph.txt中找到API。你需要使用asciidoc来获取它的HTML。 - albfan

在Git 2.18（2018年第二季度）中，git log --graph现在有一个commit-graph文件可用于加速遍历。请参见下面的答案。 - VonC

4个回答

5

我尝试查看Git或hg的代码，但是很难理解并且得到一个总体的概念。

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

因为graphlog的代码非常简短。您可以在hgext/graphlog.py中找到它，真正重要的部分是前面的200行左右，其余部分是扩展的引导以及找到所选修订图的部分。代码生成函数是ascii ，其最后一个参数是对asciiedge的调用结果（该调用本身在generate的最后一行执行，函数由 graphlog 提供给 generate ）

- masklinn

4

相对于图形显示而言，这个问题并不难。因为您希望保持节点的提交顺序，所以问题会变得简单得多。

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

虽然我没有阅读git源代码，但您可能只是从最新开始遍历提交列表，并维护一个打开的过去边缘列表。跟随边缘自然地导致分裂/合并列，并最终得到类似于git/hg显示的树。

在合并边缘时，您要避免穿越其他边缘，因此您需要尝试提前对列进行排序。这实际上是唯一可能不那么简单的部分。例如，可以使用两趟算法，在第一趟中为边缘制定列顺序，在第二趟中进行绘图。

- Zarat

6

git log --graph 命令的输出经常有交叉的边，并且不按时间顺序排列。我认为它比你所建议的要复杂一些，即使它只是一个相对简单的图形显示案例。 - Cascabel

1

从最新的开始，按照边缘向过去遵循，大部分我所说的仍然适用于没有严格的提交顺序。根据提交图可能无法避免经常出现边缘交叉，他们可能不会花费太多时间来找出理想的顺序。虽然我不想表明这是微不足道的，但想出一个好的解决方案还是很简单的。 - Zarat

1

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

这种提交图的概念改变了`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, 提交记录 049d51a, 提交记录 177722b, 提交记录 4f2542b, 提交记录 1b70dfd, 提交记录 2a2e32b (2018年4月10日)，以及提交记录 f237c8b, 提交记录 08fd81c, 提交记录 4ce58ee, 提交记录 ae30d7b, 提交记录 b84f767, 提交记录 cfe8321, 提交记录 f2af9f5 (2018年4月2日)，作者为Derrick Stolee (derrickstolee)。
^{(由Junio C Hamano -- gitster合并于提交记录 b10edb2，2018年5月8日)}

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

基于packfile中找到的提交记录编写提交图文件。
包括现有提交图文件中的所有提交记录。

设计文档指出：

Git walks the commit graph for many reasons, including:

Listing and filtering commit history.

Computing merge bases.

These operations can become slow as the commit count grows. The merge base calculation shows up in many user-facing commands, such as 'merge-base' or 'status' and can take minutes to compute depending on history shape.

There are two main costs here:

Decompressing and parsing commits.

Walking the entire graph to satisfy topological order constraints.

The commit graph file is a supplemental data structure that accelerates commit graph walks. If a user downgrades or disables the 'core.commitGraph' config setting, then the existing ODB is sufficient.

The file is stored as "commit-graph" either in the .git/objects/info directory or in the info directory of an alternate.

The commit graph file stores the commit graph structure along with some extra metadata to speed up graph walks.
By listing commit OIDs in lexicographic order, we can identify an integer position for each commit and refer to the parents of a commit using those integer positions.
We use binary search to find initial commits and then use the integer positions for fast lookups during the walk.

You can see the test use cases:
git log --oneline $BRANCH
git log --topo-order $BRANCH
git log --graph $COMPARE..$BRANCH
git branch -vv
git merge-base -a $BRANCH $COMPARE
This will improve git log performance.

在Git 2.39（2022年第4季度）中，新增了“提交图文件”和“可达性位图”的词汇条目。

查看提交 8fea12a, 提交 4973726, 提交 fa8e8d5, 提交 776ba91 (2022年10月29日) 由Philip Oakley (PhilipOakley)提交。
^{(由Taylor Blau -- ttaylorr --合并于提交 4b6302c，2022年11月8日)}

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

^{签名：Philip Oakley}
^{签名：Taylor Blau}

描述可达性位图的目的。

词汇表内容现在包括在其手册页面中：

可达性位图

可达性位图存储有关打包文件或多重打包索引（MIDX）中所选一组提交的可达性信息，以加快对象搜索速度。位图存储在“.bitmap”文件中。
存储库最多只能使用一个位图文件。
位图文件可以属于一个包，也可以属于存储库的多重打包索引（如果存在）。

和:

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

^{由Philip Oakley签署}
^{由Taylor Blau签署}

Git具有额外的“提交图形”功能，它补充了正常提交对象的有向无环图（DAG）。补充提交图形文件旨在提高访问速度。

从规范DAG视角和提交图形文件视角描述提交图形。此外，通过链接到ref词汇表条目，澄清分支引用和分支端点之间的链接，匹配此提交图形条目。

提交图形文件也因其连字符而与众不同。后续提交会捕获提交图形缺少连字符的少数情况。

glossary-content现在包括在其man page中：

提交图概念、表示和用法

由对象数据库中提交形成的DAG结构的同义词，通过其链接的提交链引用分支尖端。

这个结构是确定性的提交图。该图可以用其他方式表示，例如“commit-graph”文件。

提交图文件

“commit-graph”（通常连字号）文件是提交图的补充表示，可加速提交图遍历。

“commit-graph”文件存储在 .git/objects/info 目录或备用对象数据库的info目录中。

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

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

`commit-graph`: 修复当存在`.lock`文件时的用户体验问题

We use the lockfile API to avoid multiple Git processes from writing to the commit-graph file in the .git/objects/info directory.
In some cases, this directory may not exist, so we check for its existence.

The existing code does the following when acquiring the lock:

Try to acquire the lock.

If it fails, try to create the .git/object/info directory.

Try to acquire the lock, failing if necessary.

The problem is that if the lockfile exists, then the mkdir fails, giving an error that doesn't help the user:
"fatal: cannot mkdir .git/objects/info: File exists"
While technically this honors the lockfile, it does not help the user.

Instead, do the following:

Check for existence of .git/objects/info; create if necessary.

Try to acquire the lock, failing if necessary.

The new output looks like:
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中得到纠正（2019年2月）。

请参见提交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日）}

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

自Git 2.24（Q3 2019）以来，编写commit-graph代码以覆盖给定的提交对象名称已经变得更加健壮。

请查看提交 7c5c9b9, 提交 39d8831, 提交 9916073 (2019年8月5日) 由 SZEDER Gábor (szeder) 提交。
^{(由 Junio C Hamano -- gitster -- 合并于提交 6ba06b5, 2019年8月22日)}

同时，随着Git 2.24 (2019年第四季度)的推出，解析和使用提交图文件的代码已经更加健壮，可以更好地应对损坏的输入。

查看提交 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'）。如果 '*list' 导致解析错误，则随后的调用将失败。通过检查 'parse_commit_no_graph()' 的返回值来防止这种问题，避免将未解析的对象传递给期望解析的函数，从而防止段错误。

在Git 2.26（2020年第一季度）中，计算提交图的代码已经学会了一种更为稳健的方法来判断两个对象目录是否指向同一个内容。

请查看提交记录a7df60c, 提交记录ad2dd5b, 提交记录13c2499 (2020年2月3日), 提交记录0bd52e2 (2020年2月4日) 和提交记录1793280 (2020年1月30日)，作者为Taylor Blau (ttaylorr)。
^{(由Junio C Hamano -- gitster --于2020年2月14日合并至提交记录53c3be2)}

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结构中的char *object_dir的使用替换为odb->path，通过存储struct object_directory* 来实现。
这是消除'commit-graph.c'中所有路径规范化的中间步骤。现在，解析用户提供的“--object-dir”参数需要将其与已知的备用进行比较以确定相等性。
在此补丁之前，未知的“--object-dir”参数将以零状态静默退出。
这显然会导致意外行为，例如验证不在存储库自己的对象存储（或其备用之一）中的提交图，或者导致拼写错误掩盖合法的提交图验证失败。
当给定的“--object-dir”与任何已知的备用对象存储不匹配时，通过“die（）”使此错误变得非静默。

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

请参见提交2f00c35, 提交1f1304d, 提交0ec2d0f, 提交5b6653e, 提交630cd51, 提交d335ce8 (2020年5月13日), 提交fa8953c (2020年5月18日), 以及提交1fe1084，作者为Taylor Blau (ttaylorr)。
^{(由Junio C Hamano -- gitster --于提交dc57a9b合并, 2020年6月9日)}

`commit-graph`: 删除 `COMMIT_GRAPH_WRITE_CHECK_OIDS` 标记

^{协助者：Jeff King}
^{签署者：Taylor Blau}

Since 7c5c9b9c57 ("commit-graph: error out on invalid commit oids in 'write --stdin-commits'", 2019-08-05, Git v2.24.0-rc0 -- merge listed in batch #1), the commit-graph builtin dies on receiving non-commit OIDs as input to '--stdin-commits'.

This behavior can be cumbersome to work around in, say, the case of piping 'git for-each-ref' to 'git commit-graph write --stdin-commits' if the caller does not want to cull out non-commits themselves. In this situation, it would be ideal if 'git commit-graph write' wrote the graph containing the inputs that did pertain to commits, and silently ignored the remainder of the input.

Some options have been proposed to the effect of '--[no-]check-oids' which would allow callers to have the commit-graph builtin do just that.
After some discussion, it is difficult to imagine a caller who wouldn't want to pass '--no-check-oids', suggesting that we should get rid of the behavior of complaining about non-commit inputs altogether.

If callers do wish to retain this behavior, they can easily work around this change by doing the following:
git for-each-ref --format='%(objectname) %(objecttype) %(*objecttype)' |
awk '
  !/commit/ { print "not-a-commit:"$1 }
   /commit/ { print $1 }
' |
git commit-graph write --stdin-commits
To make it so that valid OIDs that refer to non-existent objects are indeed an error after loosening the error handling, perform an extra lookup to make sure that object indeed exists before sending it to the commit-graph internals.

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

请参见提交94fbd91 (2020年6月1日)，以及提交6334c5f (2020年6月3日)，作者为Taylor Blau (ttaylorr)。
^{(由Junio C Hamano -- gitster --在提交abacefe中合并，2020年6月18日)}

t5318：测试“--stdin-commits”是否遵守“--[no-]progress”

^{签名作者：Taylor Blau}
^{确认作者：Derrick Stolee}

The following lines were not covered in a recent line-coverage test against Git:
builtin/commit-graph.c
5b6653e5 244) progress = start_delayed_progress(
5b6653e5 268) stop_progress(&progress);
These statements are executed when both '--stdin-commits' and '--progress' are passed. Introduce a trio of tests that exercise various combinations of these options to ensure that these lines are covered.

More importantly, this is exercising a (somewhat) previously-ignored feature of '--stdin-commits', which is that it respects '--progress'.

Prior to 5b6653e523 ("[builtin/commit-graph.c](https://github.com/git/git/blob/94fbd9149a2d59b0dca18448ef9d3e0607a7a19d/builtin/commit-graph.c): dereference tags in builtin", 2020-05-13, Git v2.28.0 -- merge listed in batch #2), dereferencing input from '--stdin-commits' was done inside of commit-graph.c.

Now that an additional progress meter may be generated from outside of commit-graph.c, add a corresponding test to make sure that it also respects '--[no]-progress'.

The other location that generates progress meter output (from d335ce8f24 ("[commit-graph.c](https://github.com/git/git/blob/94fbd9149a2d59b0dca18448ef9d3e0607a7a19d/commit-graph.c): show progress of finding reachable commits", 2020-05-13, Git v2.28.0 -- merge listed in batch #2)) is already covered by any test that passes '--reachable'.

在Git 2.29（2020年第四季度）中，当使用提交图功能时，in_merge_bases_many()（一种查看提交是否可从一组提交中的任何提交到达的方法）完全失效，现已得到修正。

请参见8791bf1提交（由Derrick Stolee (derrickstolee)于2020年10月02日提交）。
^{（由Junio C Hamano -- gitster --于2020年10月05日合并至c01b041提交）}

commit-reach: 修复 in_merge_bases_many 的错误

^{报告人：Srinidhi Kaushik}
^{协助者：Johannes Schindelin}
^{签名作者：Derrick Stolee}

在f9b8908b（"[commit.c](https://github.com/git/git/blob/8791bf18414a37205127e184c04cad53a43aeff1/commit.c): use generation numbers for in_merge_bases()"，2018-05-01，Git v2.19.0-rc0 -- merge listed in batch #1）中，使用一种启发式方法来短路in_merge_bases()的遍历。只要调用者仅检查两个提交，这就可以正常工作，但是当有多个提交时，这种启发式方法可能非常错误。自那以后，一些代码移动已将此方法更改为commit-reach.c内的repo_in_merge_bases_many()。该启发式方法计算“引用”列表的最小生成数，然后将此数字与“提交”的生成数进行比较。在最近的一个主题中，添加了一个测试，使用in_merge_bases_many()测试是否可以从reflog中提取的多个提交中到达提交。然而，这突显了问题：如果任何参考提交具有比给定提交更小的生成数，则即使存在更高的生成数，也会跳过遍历。这种启发式方法是错误的！它必须检查参考提交的最大生成数，而不是最小生成数。修复本身是在repo_in_merge_bases_many()中交换min_generation和max_generation。

在Git 2.32之前，当存储库中使用某些功能（例如插入）与使用提交图不兼容时，我们通常会静默地关闭提交图；现在我们会告诉用户我们正在做什么。

请参见提交c85eec7（2021年2月11日），作者为Johannes Schindelin（dscho）。
^{（由Junio C Hamano -- gitster --于提交726b11d中合并，2021年2月17日）}

这将展示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

- VonC

请参见 https://github.com/git/git/commit/091f4cf3586957c3fd99d4c4c59c569d009137ad 自 https://github.com/git/git/commit/ca676b9bd354e846ac207e7879760719826517ce。 - VonC

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user611775 · Accepted Answer

首先，需要获取提交列表（例如使用git rev-list），以及每个提交的父级。在内存中保存“列保留列表”。

对于每个提交：

如果该提交没有为其保留列，则将其分配给空闲列。这是分支头开始的方式。
根据列保留列表打印树形图形，然后打印提交消息。
当前列/提交的预定列表条目会更新为当前提交的第一个父级，以便将要打印在同一列中。
其他父级获得新的空闲列。
如果这是合并操作，则下一行将尝试将第二个父级链接到预期的提交所在的列（这样形成循环和“≡桥”）。

以下是在aufs2-util上使用git-forest输出的示例，其中包含一个额外的提交以展示多个分支。

通过预判合并点距离可以使木材在两列之间挤压，从而获得更美观的结果。

"git log --graph"或"hg graphlog"是如何工作的？"

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

可达性位图

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

提交图概念、表示和用法

提交图文件

`commit-graph`: 修复当存在`.lock`文件时的用户体验问题

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

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

`commit-graph.h`：在“struct `write_commit_graph_context`”中存储odb

`commit-graph`: 删除 `COMMIT_GRAPH_WRITE_CHECK_OIDS` 标记

`t5318`：测试“--stdin-commits”是否遵守“--[no-]progress”

`commit-reach`: 修复 `in_merge_bases_many` 的错误

`commit-graph`：与图形不兼容时，指出原因

"git log --graph"或"hg graphlog"是如何工作的？"

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

可达性位图

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

提交图概念、表示和用法

提交图文件

commit-graph: 修复当存在.lock文件时的用户体验问题

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

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

commit-graph.h：在“struct write_commit_graph_context”中存储odb

commit-graph: 删除 COMMIT_GRAPH_WRITE_CHECK_OIDS 标记

t5318：测试“--stdin-commits”是否遵守“--[no-]progress”

commit-reach: 修复 in_merge_bases_many 的错误

commit-graph：与图形不兼容时，指出原因

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

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

`commit-graph`: 修复当存在`.lock`文件时的用户体验问题

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

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

`commit-graph.h`：在“struct `write_commit_graph_context`”中存储odb

`commit-graph`: 删除 `COMMIT_GRAPH_WRITE_CHECK_OIDS` 标记

`t5318`：测试“--stdin-commits”是否遵守“--[no-]progress”

`commit-reach`: 修复 `in_merge_bases_many` 的错误

`commit-graph`：与图形不兼容时，指出原因