共计 4403 个字符，预计需要花费 12 分钟才能阅读完成。
序言
作为一个天天都在用的工具，各位同行想必都十分相熟 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
➜ 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 对象
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 中，挑选出下一个要打印的提交对象。显然，这是一个周而复始的过程：
- 从待打印的
commit对象中，找出提交工夫戳最大的一个； - 打印它的音讯；
- 将
commit的所有父级提交退出到待打印的对象池中，回到第 1 个步骤；
这个过程始终继续到没有待打印的 commit 对象为止，而所有待打印的 commit 对象组成了一个优先级队列——能够用一个大根堆来实现。
然而，我并不打算在这短短的演示当中真的去实现一个堆数据结构——我用插入排序来代替它。
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:]最初再提供一个启动函数就能够体验一番了
@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 对象的程序是否正确，我先将它的输入内容重定向到一个文件中
➜ 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 以同样的格局打印进去
➜ gin git:(master) git log --pretty='format:%H %ct' 'e38955615a14e567811e390c87afe705df957f3a' -n 20 > /tmp/git_log.txt最初让 diff 命令通知咱们这两个文件是否有差别
➜ gin git:(master) diff /tmp/git_log.txt /tmp/my_git_log.txt
20c20
< 2521d8246d9813d65700650b29e278a08823e3ae 1499266911
\ No newline at end of file
---
> 2521d8246d9813d65700650b29e278a08823e3ae 1499266911能够说是截然不同了。
浏览原文
