乍听之下，不无道理；仔细揣摩，胡说八道

0%

git-log很好，你也可以写一个

发表于 Disqus：

序言

作为一个天天都在用的工具，各位同行想必都非常熟悉 Git 的基本用法，例如：

  • 用git-blame找出某一行 bug 是哪一位同事引入的，由他背锅；
  • 用git-merge把别人的代码合进自己完美无瑕的分支中，然后发现单元测试无法跑通；
  • 用git-push -f把团队里其他人的提交通通覆盖掉。

除此之外，Git 其实还是一个带版本功能的键值数据库：

  • 所有提交的内容都存储在目录.git/objects/下；
  • 有存储文件内容的blob对象、存储文件元数据的tree对象，还有存储提交记录的commit对象等；
  • Git 提供了键值风格的读写命令git-cat-file和git-hash-object。

读过我以前的文章《当我们git merge的时候到底在merge什么》的朋友们应该都知道，如果一次合并不是fast-forward的，那么会产生一个新的commit类型的对象，并且它有两个父级commit对象。以知名的 Go 语言 Web 框架gin的仓库为例，它的哈希值为e38955615a14e567811e390c87afe705df957f3a的提交是一次合并产生的，这个提交的内容中有两行parent

1
2
3
4
5
6
7
8
➜  gin git:(master) git cat-file -p 'e38955615a14e567811e390c87afe705df957f3a'
tree 93e5046e502847a6355ed26223a902b4de2de7c7
parent ad087650e9881c93a19fd8db75a86968aa998cac
parent ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c
author Javier Provecho Fernandez <javiertitan@gmail.com> 1499534953 +0200
committer Javier Provecho Fernandez <javiertitan@gmail.com> 1499535020 +0200

Merge pull request #520 from 178inaba/travis-import_path

通过一个提交的parent属性，所有的提交对象组成了一个有向无环图。但聪明的你应该发现了，git-log的输出结果是线性的，所以 Git 用到了某种图的遍历算法。

查阅man git-log，可以在Commit Ordering一节中看到

By default, the commits are shown in reverse chronological order.

聪明的你想必已经知道该如何实现这个图的遍历算法了。

自己动手写一个git-log

解析commit对象

要想以正确的顺序打印commit对象的信息，得先解析它。我们不需要从零开始自己打开文件、读取字节流，以及解压文件内容，只需要像上文那样调用git-cat-file即可。git-cat-file打印的内容中，有一些是需要提取备用的：

  • 以parent开头的行。这一行的哈希值要用于定位到有向无环图中的一个节点；
  • 以committer开头的行。这一行的 UNIX 时间戳将会作为决定谁是“下一个节点”的排序依据。

可以随手写一个 Python 中的类来解析一个commit对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class CommitObject:
    """一个Git中的commit类型的对象解析后的结果。"""
    def __init__(self, *, commit_id: str) -> None:
        self.commit_id = commit_id

        file_content = self._cat_file(commit_id)
        self.parents = self._parse_parents(file_content)
        self.timestamp = self._parse_commit_timestamp(file_content)

    def _cat_file(self, commit_id: str) -> str:
        cmd = ['git', 'cat-file', '-p', commit_id]
        return subprocess.check_output(cmd).decode('utf-8')

    def _parse_commit_timestamp(self, file_content: str) -> int:
        """解析出提交的UNIX时间戳。"""
        lines = file_content.split('\n')
        for line in lines:
            if line.startswith('committer '):
                m = re.search('committer .+ <[^ ]+> ([0-9]+)', line.strip())
                return int(m.group(1))

    def _parse_parents(self, file_content: str) -> List[str]:
        lines = file_content.split('\n')
        parents: List[str] = []
        for line in lines:
            if line.startswith('parent '):
                m = re.search('parent (.*)', line.strip())
                parent_id = m.group(1)
                parents.append(parent_id)
        return parents

遍历commit组成的有向无环图——大根堆

恭喜你，你学过的数据结构可以派上用场了。

假设用上面的类CommitObject解析了gin中哈希值为e38955615a14e567811e390c87afe705df957f3a的提交，那么它的parents属性中会有两个字符串：

  • ad087650e9881c93a19fd8db75a86968aa998cac；
  • ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c。

其中：

  • 哈希值为ad087650e9881c93a19fd8db75a86968aa998cac的提交的时间为Sat Jul 8 12:31:44；
  • 哈希值为ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c的提交时间为Jan 28 02:32:44。

显然，按照反转的时间先后顺序（reverse chronological）打印日志的话，下一个打印的节点应当是是ad087650e9881c93a19fd8db75a86968aa998cac——用git-log命令可以确认这一点。

打印完ad087650e9881c93a19fd8db75a86968aa998cac之后，又要从它的父级提交和ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c中，挑选出下一个要打印的提交对象。显然，这是一个循环往复的过程：

  1. 从待打印的commit对象中，找出提交时间戳最大的一个；
  2. 打印它的消息；
  3. 将commit的所有父级提交加入到待打印的对象池中，回到第1个步骤；

这个过程一直持续到没有待打印的commit对象为止，而所有待打印的commit对象组成了一个优先级队列——可以用一个大根堆来实现。

然而，我并不打算在这短短的演示当中真的去实现一个堆数据结构——我用插入排序来代替它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class MyGitLogPrinter():
    def __init__(self, *, commit_id: str, n: int) -> None:
        self.commits: List[CommitObject] = []
        self.times = n

        commit = CommitObject(commit_id=commit_id)
        self._enqueue(commit)

    def run(self):
        i = 0
        while len(self.commits) > 0 and i < self.times:
            commit = self.commits.pop(0)

            for parent_id in commit.parents:
                parent = CommitObject(commit_id=parent_id)
                self._enqueue(parent)

            print('{} {}'.format(commit.commit_id, commit.timestamp))
            i += 1

    def _enqueue(self, commit: CommitObject):
        for comm in self.commits:
            if commit.commit_id == comm.commit_id:
                return
        # 插入排序，先找到一个待插入的下标，然后将从i到最后一个元素都往尾部移动，再将新节点插入下标i的位置。
        i = 0
        while i < len(self.commits):
            if commit.timestamp > self.commits[i].timestamp:
                break
            i += 1
        self.commits = self.commits[0:i] + [commit] + self.commits[i:]

最后再提供一个启动函数就可以体验一番了

1
2
3
4
5
6
7
8
9
@click.command()
@click.option('--commit-id', required=True)
@click.option('-n', default=20)
def cli(commit_id: str, n: int):
    MyGitLogPrinter(commit_id=commit_id, n=n).run()


if __name__ == '__main__':
    cli()

真假美猴王对比

为了看看上面的代码所打印出来的commit对象的顺序是否正确，我先将它的输出内容重定向到一个文件中

1
➜  gin git:(master) python3 ~/SourceCode/python/my_git_log/my_git_log.py --commit-id 'e38955615a14e567811e390c87afe705df957f3a' -n 20 > /tmp/my_git_log.txt

再用git-log以同样的格式打印出来

1
➜  gin git:(master) git log --pretty='format:%H %ct' 'e38955615a14e567811e390c87afe705df957f3a' -n 20 > /tmp/git_log.txt

最后让diff命令告诉我们这两个文件是否有差异

1
2
3
4
5
6
➜  gin git:(master) diff /tmp/git_log.txt /tmp/my_git_log.txt
20c20
< 2521d8246d9813d65700650b29e278a08823e3ae 1499266911
\ No newline at end of file
---
> 2521d8246d9813d65700650b29e278a08823e3ae 1499266911

可以说是一模一样了。

Liutos wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！
你的一点心意，我的十分动力。