2017年4月
简介：最近我编写了大约500行Python代码，它们实现了足够的Git客户端来创建存储库，将文件添加到索引，提交并将自身推送到GitHub。本文提供了一些关于我的黑客的背景知识并介绍了代码。
Git因其非常简单的对象模型而闻名（其中包括） - 并且有充分的理由。学习时git我发现本地对象数据库只是目录中的一堆普通文件.git。除了index（.git/index）和pack文件（它们是可选的）之外，这些文件的布局和格式非常简单。
有点受到Mary Rose Cook的类似努力的启发，我想看看我是否能够实现足够的git创建库，执行提交，并推送到真正的服务器（在这种情况下为GitHub）。
玛丽的gitlet课程更多的是教育重点; 我将自己推向了GitHub，因此（以我的拙见）具有更多的黑客价值。在某些领域，她实施了更多的Git（包括基本合并），但在其他方面更少。例如，她使用了一种更简单的基于文本的索引格式，而不是使用的二进制格式git。此外，虽然她gitlet确实支持推送，但它只推送到本地存在的另一个存储库，而不是远程服务器上。
在本练习中，我想编写一个可以执行所有步骤的版本，包括推送到真正的Git服务器。我也想使用相同的二进制索引格式，git因此我可以git在每一步使用命令检查我的工作。
我的版本叫做pygitPython（3.5+）并且只使用标准库模块。它只有500多行代码，包括空白行和注释。至少我所需要的init，add，commit，和push命令，但pygit还实现了status，diff，cat-file，ls-files，和hash-object。后面的命令本身很有用，但在调试pygit时它们也非常有用。
那么让我们深入研究代码吧！您可以在GitHub上查看所有pygit.py，或者在我查看下面的各个部分时跟随它。
初始化库
初始化本地Git仓库只需要创建.git目录以及其下的一些文件和目录。在定义read_file和write_file辅助函数之后，我们可以写init()：
def init(repo):
"""Create directory for repo and initialize .git directory."""
os.mkdir(repo)
os.mkdir(os.path.join(repo, '.git'))
for name in ['objects', 'refs', 'refs/heads']:
os.mkdir(os.path.join(repo, '.git', name))
write_file(os.path.join(repo, '.git', 'HEAD'),
b'ref: refs/heads/master')
print('initialized empty repository: {}'.format(repo))
你会注意到，没有很多优雅的错误处理。毕竟，这是一个500行的子集。如果repo目录已经存在，那么它将使用回溯失败。
散列对象
该hash_object函数将单个对象哈希并写入.git/objects“数据库”。Git模型中有三种类型的对象：blob（普通文件），提交和树（这些表示单个目录的状态）。
每个对象都有一个小标题，包括字节的类型和大小。接下来是NUL字节，然后是文件的数据字节。整个事情是zlib压缩并写入.git/objects/ab/cd...，其中ab是40个字符的SHA-1哈希的前两个字符，cd...其余部分。
请注意使用Python标准库的主题，我们可以（os和hashlib）。Python附带“batteries included”。
def hash_object(data, obj_type, write=True):
"""Compute hash of object data of given type and write to object store
if "write" is True. Return SHA-1 object hash as hex string.
"""
header = '{} {}'.format(obj_type, len(data)).encode()
full_data = header + b'\x00' + data
sha1 = hashlib.sha1(full_data).hexdigest()
if write:
path = os.path.join('.git', 'objects', sha1[:2], sha1[2:])
if not os.path.exists(path):
os.makedirs(os.path.dirname(path), exist_ok=True)
write_file(path, zlib.compress(full_data))
return sha1
然后是find_object()，它通过散列（或散列前缀）找到一个对象，并且read_object()读取一个对象及其类型 - 基本上是反转的hash_object()。最后，cat_file是一个实现pygit等价的函数git cat-file：它将对象的内容（或其大小或类型）漂亮地打印到stdout。
git索引
我们希望能够做的下一件事是将文件添加到索引或暂存区域。索引是按路径排序的文件条目列表，每个条目包含路径名，修改时间，SHA-1哈希等。请注意，索引列出了当前树中的所有文件，而不仅仅是要提交的文件马上。
索引是单个文件.git/index，以自定义二进制格式存储。它并不是很复杂，但它确实涉及一些struct用法，加上一点舞蹈来到可变长度路径字段后的下一个索引条目。
前12个字节是标题，最后20个字节是索引的SHA-1散列，其间的字节是索引条目，每个62字节加上路径的长度和一些填充。这是我们的IndexEntrynamedtuple和read_index函数：
# Data for one entry in the git index (.git/index)
IndexEntry = collections.namedtuple('IndexEntry', [
'ctime_s', 'ctime_n', 'mtime_s', 'mtime_n', 'dev', 'ino', 'mode',
'uid', 'gid', 'size', 'sha1', 'flags', 'path',
])
def read_index():
"""Read git index file and return list of IndexEntry objects."""
try:
data = read_file(os.path.join('.git', 'index'))
except FileNotFoundError:
return []
digest = hashlib.sha1(data[:-20]).digest()
assert digest == data[-20:], 'invalid index checksum'
signature, version, num_entries = struct.unpack('!4sLL', data[:12])
assert signature == b'DIRC', \
'invalid index signature {}'.format(signature)
assert version == 2, 'unknown index version {}'.format(version)
entry_data = data[12:-20]
entries = []
i = 0
while i + 62 < len(entry_data):
fields_end = i + 62
fields = struct.unpack('!LLLLLLLLLL20sH',
entry_data[i:fields_end])
path_end = entry_data.index(b'\x00', fields_end)
path = entry_data[fields_end:path_end]
entry = IndexEntry(*(fields + (path.decode(),)))
entries.append(entry)
entry_len = ((62 + len(path) + 8) // 8) * 8
i += entry_len
assert len(entries) == num_entries
return entries
此功能之后ls_files，status和diff，所有这些基本上不同的方式来打印索引的状态：
-
ls_files只打印索引中的所有文件（以及它们的模式和散列，如果-s指定） -
status用于get_status()将索引中的文件与当前目录树中的文件进行比较，并打印出修改，新建和删除的文件 -
diff打印每个修改过的文件的差异，显示索引中的内容与当前工作副本中的内容（使用Python的difflib模块执行脏工作）
我100％肯定git使用索引，这些命令的实现比我的更有效，考虑到文件修改时间和所有这些。我只是通过一个完整的目录列表os.walk()获取文件路径，并使用一些设置操作，然后比较哈希。例如，这是我用来确定更改路径列表的集合理解：
changed = {p for p in (paths & entry_paths)
if hash_object(read_file(p), 'blob', write=False) !=
entries_by_path[p].sha1.hex()}
最后有一个write_index函数可以将索引写回，并向索引add()添加一个或多个路径 - 后者只需读取整个索引，添加路径，重新排序，然后再将其写出来。
此时我们可以将文件添加到索引中，我们已准备好进行提交。
提交
执行提交包括编写两个对象：
首先，树对象，它是提交时当前目录（或实际上是索引）的快照。树只列出目录中文件（blob）和子树的哈希值 - 它是递归的。
因此，每次提交都是整个目录树的快照。但是这种通过散列存储事物的方式的巧妙之处在于，如果树中的任何文件发生变化，整个树的散列也会发生变化。相反，如果文件或子树没有改变，它只会被相同的散列引用。因此，您可以有效地存储目录树中的更改。
这是一个打印的树对象的示例cat-file pretty 2226（每行显示文件模式，对象类型，哈希和文件名）：
100644 blob 4aab5f560862b45d7a9f1370b1c163b74484a24d LICENSE.txt
100644 blob 43ab992ed09fa756c56ff162d5fe303003b5ae0f README.md
100644 blob c10cb8bc2c114aba5a1cb20dea4c1597e5a3c193 pygit.py
write_tree奇怪的是，该函数用于编写树对象。关于某些Git文件格式的一个奇怪的事情是它们是混合二进制和文本的事实 - 例如，树对象中的每个“行”是“模式空间路径”作为文本，然后是NUL字节，然后是二进制SHA-1哈希。这是我们的write_tree()：
def write_tree():
"""Write a tree object from the current index entries."""
tree_entries = []
for entry in read_index():
assert '/' not in entry.path, \
'currently only supports a single, top-level directory'
mode_path = '{:o} {}'.format(entry.mode, entry.path).encode()
tree_entry = mode_path + b'\x00' + entry.sha1
tree_entries.append(tree_entry)
return hash_object(b''.join(tree_entries), 'tree')
第二，提交对象。这会记录树形哈希，父提交，作者和时间戳以及提交消息。合并当然是关于Git的好东西之一，但pygit只支持单个线性分支，所以只有一个父级（或者在第一次提交的情况下没有父级！）。
这是一个提交对象的示例，再次使用cat-file pretty aa8d以下方式打印：
tree 22264ec0ce9da29d0c420e46627fa0cf057e709a
parent 03f882ade69ad898aba73664740641d909883cdc
author Ben Hoyt <benhoyt@gmail.com> 1493170892 -0500
committer Ben Hoyt <benhoyt@gmail.com> 1493170892 -0500
Fix cat-file size/type/pretty handling
这是我们的commit功能 - 再次，感谢Git的对象模型，几乎是行人：
def commit(message, author):
"""Commit the current state of the index to master with given message.
Return hash of commit object.
"""
tree = write_tree()
parent = get_local_master_hash()
timestamp = int(time.mktime(time.localtime()))
utc_offset = -time.timezone
author_time = '{} {}{:02}{:02}'.format(
timestamp,
'+' if utc_offset > 0 else '-',
abs(utc_offset) // 3600,
(abs(utc_offset) // 60) % 60)
lines = ['tree ' + tree]
if parent:
lines.append('parent ' + parent)
lines.append('author {} {}'.format(author, author_time))
lines.append('committer {} {}'.format(author, author_time))
lines.append('')
lines.append(message)
lines.append('')
data = '\n'.join(lines).encode()
sha1 = hash_object(data, 'commit')
master_path = os.path.join('.git', 'refs', 'heads', 'master')
write_file(master_path, (sha1 + '\n').encode())
print('committed to master: {:7}'.format(sha1))
return sha1
与服务器交谈
接下来是稍微更难的部分，其中我们将pygit与真实的Git服务器进行对话（我将pygit推送到GitHub，但它也适用于Bitbucket和其他服务器）。
基本思想是查询服务器的主分支以了解它所在的提交，然后确定它需要赶上当前本地提交的对象集。最后，更新远程的提交哈希并发送所有缺失对象的“包文件”。
这被称为“智能协议” - 截至2011年，GitHub 停止了对“哑”传输协议的支持，该协议只是.git直接传输文件，并且在某种程度上更容易实现。因此，我们必须使用“智能”协议并将对象打包到包文件中。
不幸的是，当我实现智能协议时，我犯了一个愚蠢的错误 - 我没有找到关于HTTP协议和打包协议的主要技术文档，直到我完成它。我正在使用Git Book 的相当手动的传输协议部分以及packfile格式的Git代码库。
在使其工作的最后阶段，我还使用Python的http.server模块实现了一个小型HTTP服务器，因此我可以git针对它运行常规客户端并查看一些实际请求。一些逆向工程值得一千行代码。
pkt-line格式
传输协议的关键部分之一是所谓的“pkt-line”格式，它是一种长度前缀的数据包格式，用于发送提交哈希等元数据。每个“行”具有4位十六进制长度（加上4以包括长度的长度），然后长度减去4个字节的数据。每行通常LF在末尾也有一个字节。特殊长度0000用作节标记并位于数据的末尾。
例如，这是GitHub对git-receive-packGET请求的响应。请注意，其他换行符和缩进不是实际数据的一部分：
001f# service=git-receive-pack\n
0000
00b20000000000000000000000000000000000000000 capabilities^{}\x00
report-status delete-refs side-band-64k quiet atomic ofs-delta
agent=git/2.9.3~peff-merge-upstream-2-9-1788-gef730f7\n
0000
所以我们需要两个函数，一个用于将pkt-line数据转换为一个行列表，另一个用于将行列表转换为pkt-line格式：
def extract_lines(data):
"""Extract list of lines from given server data."""
lines = []
i = 0
for _ in range(1000):
line_length = int(data[i:i + 4], 16)
line = data[i + 4:i + line_length]
lines.append(line)
if line_length == 0:
i += 4
else:
i += line_length
if i >= len(data):
break
return lines
def build_lines_data(lines):
"""Build byte string from given lines to send to server."""
result = []
for line in lines:
result.append('{:04x}'.format(len(line) + 5).encode())
result.append(line)
result.append(b'\n')
result.append(b'0000')
return b''.join(result)
发出HTTPS请求
下一个技巧 - 因为我只想使用标准库 - 是在没有requests库的情况下进行经过身份验证的HTTPS请求。这是代码：
def http_request(url, username, password, data=None):
"""Make an authenticated HTTP request to given URL (GET by default,
POST if "data" is not None).
"""
password_manager = urllib.request.HTTPPasswordMgrWithDefaultRealm()
password_manager.add_password(None, url, username, password)
auth_handler = urllib.request.HTTPBasicAuthHandler(password_manager)
opener = urllib.request.build_opener(auth_handler)
f = opener.open(url, data=data)
return f.read()
以上是确切requests存在的原因的一个例子。您可以使用标准库的urllib.request模块执行所有操作，但有时会很痛苦。大多数Python stdlib都很棒，其他部分则不是很多。使用的等效代码requests甚至不需要辅助函数：
def http_request(url, username, password):
response = requests.get(url, auth=(username, password))
response.raise_for_status()
return response.content
我们可以使用上面的内容来询问服务器它的主分支是什么提交，就像这样（这个函数相当脆弱，但可以很容易地推广）：
def get_remote_master_hash(git_url, username, password):
"""Get commit hash of remote master branch, return SHA-1 hex string or
None if no remote commits.
"""
url = git_url + '/info/refs?service=git-receive-pack'
response = http_request(url, username, password)
lines = extract_lines(response)
assert lines[0] == b'# service=git-receive-pack\n'
assert lines[1] == b''
if lines[2][:40] == b'0' * 40:
return None
master_sha1, master_ref = lines[2].split(b'\x00')[0].split()
assert master_ref == b'refs/heads/master'
assert len(master_sha1) == 40
return master_sha1.decode()
确定丢失的对象
接下来，我们需要确定服务器所需的对象，而不是已有的对象。pygit假设它具有本地的所有内容（它不支持“拉”），所以我有一个read_tree函数（与之相反write_tree）然后以下两个函数以递归方式查找给定树和给定提交中的对象哈希集：
def find_tree_objects(tree_sha1):
"""Return set of SHA-1 hashes of all objects in this tree
(recursively), including the hash of the tree itself.
"""
objects = {tree_sha1}
for mode, path, sha1 in read_tree(sha1=tree_sha1):
if stat.S_ISDIR(mode):
objects.update(find_tree_objects(sha1))
else:
objects.add(sha1)
return objects
def find_commit_objects(commit_sha1):
"""Return set of SHA-1 hashes of all objects in this commit
(recursively), its tree, its parents, and the hash of the commit
itself.
"""
objects = {commit_sha1}
obj_type, commit = read_object(commit_sha1)
assert obj_type == 'commit'
lines = commit.decode().splitlines()
tree = next(l[5:45] for l in lines if l.startswith('tree '))
objects.update(find_tree_objects(tree))
parents = (l[7:47] for l in lines if l.startswith('parent '))
for parent in parents:
objects.update(find_commit_objects(parent))
return objects
然后我们需要做的就是获取本地提交引用的对象集，并减去远程提交中引用的对象集。此设置差异是远程端丢失的对象。我确信有更有效的方法来生成这个集合，但这对于pygit来说已经足够好了：
def find_missing_objects(local_sha1, remote_sha1):
"""Return set of SHA-1 hashes of objects in local commit that are
missing at the remote (based on the given remote commit hash).
"""
local_objects = find_commit_objects(local_sha1)
if remote_sha1 is None:
return local_objects
remote_objects = find_commit_objects(remote_sha1)
return local_objects - remote_objects
推动本身
要执行推送，我们需要发送一个pkt-line请求来说“将主分支更新为此提交哈希”，然后是一个包含上面找到的所有缺失对象的连接内容的包文件。
包文件有一个12字节的标题（以...开头PACK），然后每个对象用可变长度编码并使用zlib压缩，最后是整个包文件的20字节散列。我们使用对象的“未定义”表示来保持简单 - 有更复杂的方法来根据对象之间的增量来缩小包文件，但这对我们来说太过分了：
def encode_pack_object(obj):
"""Encode a single object for a pack file and return bytes
(variable-length header followed by compressed data bytes).
"""
obj_type, data = read_object(obj)
type_num = ObjectType[obj_type].value
size = len(data)
byte = (type_num << 4) | (size & 0x0f)
size >>= 4
header = []
while size:
header.append(byte | 0x80)
byte = size & 0x7f
size >>= 7
header.append(byte)
return bytes(header) + zlib.compress(data)
def create_pack(objects):
"""Create pack file containing all objects in given given set of
SHA-1 hashes, return data bytes of full pack file.
"""
header = struct.pack('!4sLL', b'PACK', 2, len(objects))
body = b''.join(encode_pack_object(o) for o in sorted(objects))
contents = header + body
sha1 = hashlib.sha1(contents).digest()
data = contents + sha1
return data
然后，所有这一切的最后一步，push()本身 - 为了简洁，删除了一些外围代码：
def push(git_url, username, password):
"""Push master branch to given git repo URL."""
remote_sha1 = get_remote_master_hash(git_url, username, password)
local_sha1 = get_local_master_hash()
missing = find_missing_objects(local_sha1, remote_sha1)
lines = ['{} {} refs/heads/master\x00 report-status'.format(
remote_sha1 or ('0' * 40), local_sha1).encode()]
data = build_lines_data(lines) + create_pack(missing)
url = git_url + '/git-receive-pack'
response = http_request(url, username, password, data=data)
lines = extract_lines(response)
assert lines[0] == b'unpack ok\n', \
"expected line 1 b'unpack ok', got: {}".format(lines[0])
命令行解析
pygit也使用标准库的一个相当不错的示例argparse模块，包括子命令（pygit init，pygit commit等）。我不会在这里复制代码，但请查看源代码中的argparse代码。
使用pygit
在大多数地方，我试图使pygit命令行语法与语法相同或非常相似git。以下是将pygit提交给GitHub的内容：
$ python3 misc/pygit.py init pygit
initialized empty repository: pygit
$ cd pygit
# ... write and test pygit.py using a test repo ...
$ python3 pygit.py status
new files:
pygit.py
$ python3 pygit.py add pygit.py
$ python3 pygit.py commit -m "First working version of pygit"
committed to master: 00d56c2a774147c35eeb7b205c0595cf436bf2fe
$ python3 pygit.py cat-file commit 00d5
tree 7758205fe7dfc6638bd5b098f6b653b2edd0657b
author Ben Hoyt <benhoyt@gmail.com> 1493169321 -0500
committer Ben Hoyt <benhoyt@gmail.com> 1493169321 -0500
First working version of pygit
# ... make some changes ...
$ python3 pygit.py status
changed files:
pygit.py
$ python3 pygit.py diff
--- pygit.py (index)
+++ pygit.py (working copy)
@@ -100,8 +100,9 @@
"""
obj_type, data = read_object(sha1_prefix)
if mode in ['commit', 'tree', 'blob']:
- assert obj_type == mode, 'expected object type {}, got {}'.format(
- mode, obj_type)
+ if obj_type != mode:
+ raise ValueError('expected object type {}, got {}'.format(
+ mode, obj_type))
sys.stdout.buffer.write(data)
elif mode == '-s':
print(len(data))
$ python3 pygit.py add pygit.py
$ python3 pygit.py commit -m "Graceful error exit for cat-file with bad
object type"
committed to master: 4117234220d4e9927e1a626b85e33041989252b5
$ python3 pygit.py push https://github.com/benhoyt/pygit.git
updating remote master from no commits to
4117234220d4e9927e1a626b85e33041989252b5 (6 objects)
总而言之，伙计们
而已！如果你到了这里，你只是走了大约500行没有价值的Python - 哦等等，除了教育和工匠黑客的价值。:-)希望你也学到了一些关于Git内部的东西。
请写下您对Hacker News或编程reddit的评论。
