'git log --graph'或'hg graphlog'如何工作？

Question

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

我很好奇,怎么做这样的节目git log --graph还是hg graphlog画历史？我一直认为以如此好的方式画出车道和一切都很复杂.

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

注意:我试着查看Git或hg的代码,但很难跟踪并大致了解正在发生的事情.

Answer 1

首先,获取提交列表(如同git rev-list)和每个提交的父项."列保留列表"保留在内存中.

对于每次提交,然后:

• 如果提交没有为其保留列,请将其分配给空闲列.这就是分支头开始的方式.
• 根据列保留列表打印树形图,然后提交提交消息
• 使用当前提交的第一个父级更新当前列/提交的预留列表条目,以便将父级打印在同一列中.
• 其他家长得到一个新的免费专栏.
• 如果这是一个合并,下一行将尝试将第二个父链接到一个预期提交的列(这使得循环和"≡桥")

显示git-foreston aufs2-util的输出的示例,其中额外提交具有多个分支).

通过前瞻,可以预测合并点下方的距离,并在两列之间挤压木材,以获得更美观的结果.

Answer 2

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

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

因为graphlog的代码很短。您可以在hgext / graphlog.py中找到它，而真正重要的部分是前200行，其余是扩展程序的引导程序并查找所选的修订图。代码生成功能是ascii，其最后一个参数是一个呼叫的结果asciiedge（本身上的最后一行进行的呼叫generate，该函数被设置成generate通过graphlog）

Answer 3

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

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

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

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