序言作为每天都在用的工具，想必业内人士都非常熟悉Git的基本用法，例如：使用git-blame查找哪一行的bug是同事介绍的，他负责；用git-merge把别人的代码合并到他的无瑕分支里，然后发现单元测试跑不通；使用git-push-f覆盖团队中其他人的所有提交。另外，Git其实是一个key-value数据库，具有版本功能：所有提交的内容都存放在.git/objects/目录下；有存储文件内容的blob对象、存储文件元数据的tree对象、存储commit记录的Commit对象等；Git提供了key-value风格的读写命令git-cat-file和git-hash-object。看过我上一篇文章《当我们git merge的时候到底在merge什么》的朋友应该知道，如果一个merge不是fast-forward，会产生一个新的commit类型对象，它有两个parentcommit对象。以著名的Go语言web框架gin的仓库为例。哈希值为e38955615a14e567811e390c87afe705df957f3a的提交是由合并生成的。Therearetwolinesinthecommitcontentparent?gingit:(master)gitcat-file-p'e38955615a14e567811e390c87afe705df957f3a'tree93e5046e502847a6355ed26223a902b4de2de7c7parentad087650e9881c93a19fd8db75a86968aa998cacparentce26751a5a3ed13e9a6aa010d9a7fa767de91b8cauthorJavierProvechoFernandez1499534953+0200committerJavierProvechoFernandez1499535020+0200Mergepullrequest#520from178inaba/travis-import_path通过一个提交的父属性，所有提交对象形成一个有向无环图。但是如果你聪明的话，你应该已经发现git-log的输出是线性的，所以Git使用了某种图遍历算法。查阅mangit-log，可以看到在CommitOrdering部分，默认情况下，提交是按照时间倒序显示的。聪明的你一定已经知道如何实现这个图的遍历算法了。自己写一个git-log解析commit对象如果想按照正确的顺序打印commit对象的信息，就必须先解析。我们不需要从头开始打开文件，读取字节流，解压文件内容，只需要像上面那样调用git-cat-file即可。在git-cat-file打印出来的内容中，有一些需要提取出来：以parent开头的行。该行的哈希值用于定位DAG中的节点；以提交者开头的行。该行的UNIX时间戳将用于确定谁是顺序的“下一个节点”。可以用Python写一个类来解析一个commit对象classCommitObject:"""Git中一个commit类型对象的解析结果."""def__init__(self,*,commit_id:str)->None:self.commit_id=commit_idfile_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]returnsubprocess.check_output(cmd).decode('utf-8')def_parse_commit_timestamp(self,file_content:str)->int:"""解析出UNIX时间戳的承诺。"""lines=file_content.split('\n')forlineinlines:ifline.startswith('committer'):m=re.search('committer.+<[^]+>([0-9]+)',line.strip())returnint(m.group(1))def_parse_parents(self,file_content:str)->List[str]:lines=file_content.split('\n')parents:List[str]=[]forlineinlines:ifline.startswith('parent'):m=re.search('parent(.*)',line.strip())parent_id=m.group(1)parents.append(parent_id)returnparentstraversethedirectedacyclicgraphcomposedofcommit——DagenduiCongratulations,thedatastructureyouhavelearnedcancomeinhandy.AssumethattheaboveclassCommitObjectisusedtoparsethehashvalueingine38955615a14e567811e390c87afe705df957f3a的提交，那么它的parents属性中会有两个字符串：ad087650e9881c93a19fd8db75a86968aa998cac；ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c。其中：哈希值为ad087650e9881c93a19fd8db75a86968aa998cac的提交的时间为SatJul812:31:44；哈希值为ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c的提交时间ForJan2802:32:44.显然，如果日志是按时间倒序（reversechronological）打印的，那么打印的下一个节点应该是ad087650e9881c93a19fd8db75a86968aa998cac——这一点可以用git-log命令来确认。打印ad087650e9881c93a19fd8db75a86968aa998cac后，需要从其parentsubmission和ce26751a5a3ed13e9a6aa010d9a7fa767de91b8c中选择下一个要打印的提交对象。显然，这是一个迭代的过程：从要打印的提交对象中，找到提交时间戳最大的；打印它的信息；将commit的所有parentcommit添加到待打印的对象池中，返回第一步；这个过程一直持续到没有要打印的提交对象，并且所有要打印的提交对象形成一个优先级队列——这可以用一个大的根堆来实现。但是，我不会在这个简短的演示中实际实现堆数据结构——我将改用插入排序。类MyGitLogPrinter():def__init__(self,*,commit_id:str,n:int)->None:self.commits:List[CommitObject]=[]self.times=ncommit=CommitObject(commit_id=commit_id)self._enqueue(commit)defrun(self):i=0whilelen(self.commits)>0andiself.commits[i].timestamp:breaki+=1self.commits=self.commits[0:i]+[commit]+self.commits[i:]最后提供启动函数体验一下@click.command()@click.option('--commit-id',required=True)@click.option('-n',default=20)defcli(commit_id:str,n:int):MyGitLogPrinter(commit_id=commit_id,n=n).run()if__name__=='__main__':cli()真假孙悟空对比看是否上面代码打印的提交对象的顺序是正确的，我首先将其输出重定向到一个文件?gingit:(master)python3~/SourceCode/python/my_git_log/my_git_log.py--commit-id'e38955615a14e567811e390c87afe705df957f3a'-n20>/tmp/my_git_log.txt然后用git-log同样的格式打印出来?gingit:(master)gitlog--pretty='format:%H%ct''e38955615a56780fd37afe999-n20>/tmp/git_log.txt最后让diff命令告诉我们两个文件是否有区别?gingit:(master)diff/tmp/git_log.txt/tmp/my_git_log.txt20c20<2521d8246d9813d65700650b29e278a08823e3ae1499266911\新lineatendoffile--->2521d8246d9813d65700650b29e278a08823e3ae1499266911可以说是一模一样。阅读原文
