“git log --graph"或“hg graphlog"如何工作? [英] How does 'git log --graph' or 'hg graphlog' work?

问题描述

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

I know that the history in Git is stored in a data structure called a DAG. I've heard about DFS and know it's somewhat related.

我很好奇，git log --graph 或 hg graphlog 之类的程序是如何绘制历史的?我一直觉得把车道和所有东西画得这么漂亮很复杂.

I'm curious, how do programs such as git log --graph or hg graphlog draw the history? I always thought it's quite complicated to draw the lanes and everything in such a nice way.

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

Could someone write some pseudo code that demonstrates it?

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

note: 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.

推荐答案

首先，获得一个提交列表(与 git rev-list 一样)，以及每个提交的父项.一个列保留列表"保存在内存中.

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.

对于每次提交:

• 如果提交没有为它保留的列，则将其分配给一个空闲列.这就是分公司负责人的开始方式.
• 根据列预留列表打印树形图，然后提交提交信息
• 当前列/提交的保留列表条目将更新为当前提交的第一个父项，这样父项将打印在同一列中.
• 其他家长获得了一个新的免费专栏.
• 如果这是一次合并，下一行将尝试将第二个父级链接到预期提交的列(这将用于循环和≡ 桥")

示例显示了 aufs2-util 上 git-forest 的输出，并带有一个以上分支的额外提交).

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

通过前瞻，您可以预测合并点将向下多远，并在两列之间挤压木材以提供更美观的结果.

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.

这篇关于“git log --graph"或“hg graphlog"如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！