概要：pygit是一个大约500行Python代码工具，实现了一些git功能，包括创建库、将文件添加到索引、提交、将自身推送到GitHub上去。 这篇文章给出了一些代码编写过程，并详细介绍了相关代码。

Git因其具有非常简单的对象模型而着称。在学习git时，我发现本地对象数据库只是.git目录中的一堆普通文件。除了索引（.git/index）和打包文件（可有可无）外，这些文件的存放规则和格式相当的简单。

受Mary Rose Cook的程序启发，我也想看看是否能够编写出创建仓库，执行提交，并推送到服务器（比如GitHub）的git客户端。

Mary的gitlet程序有着很多可供学习的地方，而我的程序需要把自身推送到GitHub上去，所以具有更多的创新功能。在某些方面，她实现了更多的Git功能（包括基本的合并），但在其他方面实现的功能就比较的少。例如，她使用了一个简单的基于文本的索引格式，而不是用git使用的二进制格式。此外，虽然她的gitlet支持推送，但它只会推送到本地已经存在的仓库中，而不是到远程服务器上。

对于本文涉及的这个练习，我打算编写一个可以执行所有步骤的版本，包括推送到一个真正的Git服务器上去。我也会使用与git相同的二进制索引格式，这样，我就可以在每一步骤上都使用git命令来检查程序的功能。

我的程序叫pygit，用Python（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):
    """创建仓库目录，初始化.git目录"""
    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行啊。如果仓库目录已经存在，程序会终止，并抛出traceback。

取对象的散列值
hash_object函数用来获取单个文件对象的散列值，并写入.git/objects目录下的“数据库”中。在Git模型中，包含三种对象，分别是：普通文件（blob），提交（commit）和树（tree，也就是目录结构）。

每个对象都有一个文件头，包括文件类型和文件大小，大概几个字节的长度。之后是NUL字符，然后是文件的数据内容。所有这些都使用zlib压缩并写入到文件.git/objects/ab/cd…中，其中ab是40个字符长的SHA-1散列的前两个字符，而cd…则是剩余的部分。

请注意，这里使用了Python标准库（os和hashlib）。

def hash_object(data, obj_type, write=True):
    """根据对象类型计算对象的散列值，如果write是真的话，则保存到文件中。
    以十六进制字符串的形式返回SHA-1散列
    """
    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是一个与git cat-file具有相同功能的pygit函数：它将对象的内容（或者大小和类型）进行格式化并打印到标准输出。

git索引
接下来我们要做的事情就是要将文件添加到索引或暂存区中。索引就是文件列表，按路径名排序，每个路径都包含路径名，修改时间，SHA-1散列等等。需要注意的是，索引列出了当前树中的所有文件，而不仅仅是在暂存区中等待提交的文件。

索引以自定义的二进制格式存储在.git/index文件中。这个文件虽然并不是很复杂，但它还是涉及到了结构体的用法，通过一定规则的字节偏移，可以在长度可变的路径名称字段之后获得下一个索引条目。

文件的前12个字节是文件头，最后20个字节是索引的SHA-1散列，在这中间的字节是索引条目，每个索引条目为62个字节加上路径的长度再加上填充的长度。下面是namedtuple类型的IndexEntry和read_index函数：

# git索引(.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():
    """读取git索引文件，并返回IndexEntry对象列表"""
    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模块来完成这个功能）

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()函数将一个或多个路径添加到索引中。add()函数首先读取整个索引，将路径添加进去，然后重新排序并回写索引。

此时，我们已经将文件添加到索引中了，下面，我们可以开始实现commit操作了。

提交
执行提交操作需要编写两个对象：

首先是树对象，它是提交时当前目录（或者是索引）的一个快照。这棵树递归列出了目录中的文件和子目录的散列。

所以每个提交都是整个目录树的快照。 这种使用散列值来存储东西的好处是，如果树中的任意一个文件发生改变，则整个树的散列也会跟着发生改变。相反，如果一个文件或子目录没有改变，则散列也不会改变。所以你可以高效地存储目录树中的变更。

这是一个用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():
    """从当前的索引条目中写入一个树对象"""
    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

这个是我们的提交函数，再次感谢Git的对象模型，相当的简单：

def commit(message, author):
    """将索引的当前状态提交到master。
    返回提交对象的散列值
    """
    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目录中的文件直接传输过去，所以实现起来更加容易。这里，我们必须得使用“智能协议”将对象打包到一个文件中。

在最后的工作阶段，我使用了Python的http.server模块实现了一个小型的HTTP服务器，这样，我就可以运行其他的git客户端与这个服务器进行交互，以此来查看真正的请求与相应数据。

pkt-line格式
传输协议的关键部分之一是“pkt-line”格式，它是用于发送元数据（如提交散列）的数据报文格式。报文的开头是长度值。每“行”开头是4个十六进制字符表示的长度值（所表示的长度要包含这个长度值字段），所以，包的长度必须小于这4个字符表示的数值。 每行的最后都有一个LF字符。数据结尾的0000是段结束标记。

例如，这个是GitHub对git-receive-pack GET请求的响应报文。请注意，额外的换行符和缩进并不是报文的一部分。

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):
    """将从服务器接收到数据转换成多行数据"""
    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):
    """将多行数据转换成服务器所需的数据格式"""
    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):
    """发送HTTP认证请求(默认使用GET,如果data非空，则用POST"""
    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标准库是很好用的，有一些则不是，虽然数量并不多。如果使用request的话，甚至都不需要帮助函数：

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):
    """获取远程master分支的提交散列，返回SHA-1十六进制字符串，如果远程master没有提交，则返回空
    """
    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假定所有东西都在本地（它不支持“pulling”），所以，我写了read_tree函数（与write_tree相反），然后，用以下这两个函数在指定的树和指定的提交中递归寻找对象散列集合：

def find_tree_objects(tree_sha1):
    """返回tree_sha1树目录下的所有对象的SHA-1散列集合，包括树目录本身的散列
    """
    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):
    """返回commit_sha1下所有对象的SHA-1散列
    """
    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):
    """返回远程服务器上相对于本地递交缺少的所有对象的SHA-1散列结婚
    """
    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):
    """把单一对象编码成打包文件（包括长度可变的报文头和压缩过的数据）
    """
    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):
    """把master分支推送到指定的git仓库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，包括子命令（pygit init，pygit commit等），是一个使用标准库argparse模块的例子。我没有把代码复制到这里，你可以查看源代码中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内部逻辑方面的知识。