jm proj 把一套完整的版本控制系统塞进了 4497 行单文件 Python,而且只 import 标准库。这篇文章把它拆开,看看内容寻址存储和三路合并到底是怎么写的。

先上铁证 —— 这是它全部的依赖:

import argparse, base64, getpass, hashlib, json, mimetypes
import os, subprocess, sys, time, zlib
import urllib.error, urllib.parse, urllib.request

没了。没有 requests,没有 click,没有 pygit2。

一、对象存储:一个忠实的 git 复刻,但改了两处

def _write_object(root, otype, content):
    header = ("%s %d\0" % (otype, len(content))).encode()
    store  = header + content
    sha    = hashlib.sha256(store).hexdigest()
    p = _obj_path(root, sha)
    if not os.path.exists(p):
        os.makedirs(os.path.dirname(p), exist_ok=True)
        with open(p, "wb") as fh:
            fh.write(zlib.compress(store))
    return sha

熟悉 git 内部结构的人应该已经笑了。这就是 git 的 loose object 格式:"类型 长度\0" 当 header,拼上内容一起哈希,zlib 压缩落盘。连文件模式位都是照搬的:

entries.append(("40000",  sub,  name))   # 目录
entries.append(("100644", blob, name))   # 普通文件

那个 if not os.path.exists(p) 是内容寻址的整个意义所在:相同内容算出相同哈希,写入直接跳过。 一个没改过的文件提交一百次,磁盘上也只有一份。

改动一:SHA-256 而不是 SHA-1

git 至今主线还在用 SHA-1(向 SHA-256 的迁移拖了很多年,因为存量仓库太多)。从零开始写的项目没这个包袱,直接上 SHA-256 是对的 —— 反正都是一行 hashlib。

改动二:对象目录是平的

def _obj_path(root, sha):
    return os.path.join(root, ".jm", "objects", sha)

git 写的是 objects/ab/cdef012... —— 拿前两位做一层目录扇出。这不是美学选择,是历史包袱:早年 ext3 的线性目录查找在单目录几万个条目时会明显变慢。

现代文件系统(ext4 的 htree、XFS 的 B+ 树)已经没这个问题了,所以平平的 objects/ 完全能跑。只是当你 ls 它的时候会看到一屏字符串。

改动三:tree 是纯文本

content = "".join("%s %s %s\n" % (m, s, n) for m, s, n in entries).encode()

git 的 tree 对象是二进制(哈希用 20 字节原始字节存)。这里直接存十六进制字符串,体积翻倍,但换来一个好处:zlib.decompress 之后胉眼就能读。调试一个自制版本控制系统时,这个价值远超那点磁盘。

三处改动都指向同一个取舍:用少量空间和历史兼容性,换实现的简单和可调试性。 对一个不需要兼容 git 仓库的项目而言,这三笔交易都做得划算。

二、三路合并:difflib 只被用了一行

这是我最想看的部分。先回答那个自然而然的疑问:是不是直接套了 difflib?

不是。 difflib 在整个合并算法里只干了一件事:

def to_map(x, y):
    m = {}
    for oi, sj, size in difflib.SequenceMatcher(None, x, y).get_matching_blocks():
        for k in range(size):
            m[oi + k] = sj + k
    return m

amap, bmap = to_map(base, ours), to_map(base, theirs)

它把「base 的第 i 行对应 ours 的第 j 行」这种行号映射算出来,仅此而已。真正的 diff3 逻辑是手写的。

这个分寸拿得很好。序列对齐(LCS)是个成熟且无趣的问题,标准库里有现成的就别重写;而三路合并的决策规则是业务逻辑,必须自己掌控。

四行决策规则

整个合并的灵魂就是这个函数:

def emit_region(a_reg, b_reg, base_reg):
    if a_reg == b_reg:        out.extend(a_reg)   # 两边改成了一样 → 取任一
    elif a_reg == base_reg:   out.extend(b_reg)   # 我没改 → 取他的
    elif b_reg == base_reg:   out.extend(a_reg)   # 他没改 → 取我的
    else:                                          # 都改了且不同 → 冲突
        out.append("<<<<<<< ours\n")
        out.extend(a_reg)
        out.append("=======\n")
        out.extend(b_reg)
        out.append(">>>>>>> theirs\n")
        conflict = True

四个分支,把三路合并的全部语义说完了。很多人觉得三路合并神秘,其实核心就是这四句 —— 难的不是规则,是把文件切成「区域」。

切区域:同步点扫描

主循环的思路是:找到 ours 和 theirs 都没动过的行 —— 叫它同步点。两个同步点之间夹着的,就是一个需要决策的区域。

while io < n:
    if io in amap and io in bmap:              # 同步点
        aj, bj = amap[io], bmap[io]
        emit_region(ours[ia:aj], theirs[ib:bj], [])   # 处理它前面的插入
        out.append(base[io])                   # 同步行直接输出
        ia, ib, io = aj + 1, bj + 1, io + 1
    else:                                      # 不同步 → 往前找下一个同步点
        jo = io
        while jo < n and not (jo in amap and jo in bmap):
            jo += 1
        aj0 = amap[jo] if jo < n else len(ours)
        bj0 = bmap[jo] if jo < n else len(theirs)
        emit_region(ours[ia:aj0], theirs[ib:bj0], base[io:jo])
        io, ia, ib = jo, aj0, bj0
emit_region(ours[ia:], theirs[ib:], base[n:])  # 尾部

注意第一个 emit_region 的第三个参数是 []。这是个很巧的处理:同步行之前新增的内容,在 base 里对应的是空区域。代回那四行规则:如果只有一边插了行,另一边的区域就等于 [],命中第二或第三条,自动采纳。不需要为「纯插入」写特例。

实测

读代码得出的结论不算数,跑一遍。基础文件五行,一边改第 2 行,另一边改第 4 行:

$ jm proj merge feat
Merge made by 3-way (6477f3e)

$ cat f.txt
line1
LINE2-ours
line3
LINE4-theirs
line5

两边的修改都在。再试真冲突 —— 两边改同一行:

$ jm proj merge feat
CONFLICT (1 file(s)) — resolve, then: jm proj commit -m 'merge branch 'feat''
  both modified: g.txt

$ cat g.txt
a
<<<<<<< ours
OURS-EDIT
=======
THEIRS-EDIT
>>>>>>> theirs
c

行为完全正确。而且注意未冲突的 a 和 c 没被卷进冲突区 —— 这正是同步点扫描在起作用。

三、先快路径,后硬磕

_three_way_file 在调用昂贵的行级合并前,先拦了四道:

if ours == theirs:  return (ours,   False)   # 改得一模一样
if ours == base:    return (theirs, False)   # 我没动
if theirs == base:  return (ours,   False)   # 他没动
if ours is None or theirs is None:           # 一边删一边改
    return ((ours if ours is not None else theirs), True)

这四行都是整文件字节比较,快得多。真实合并里绝大多数文件会在这里就被解决 —— 一个两千个文件的仓库,一次合并可能只有10个文件需要真算。

第四条值得单拎:删除 vs 修改时,保留存在的那一边,同时标记冲突。 这是对的 —— 删掉比留着危险得多。多一个文件你会发现,少一个文件可能三周后才发现。

四、合并基础:BFS 找公共祖先

def _merge_base(root, a, b):
    aa = _ancestors(root, a)          # a 的全部祖先
    seen, q = set(), deque([b])
    while q:
        s = q.popleft()
        if not s or s in seen: continue
        seen.add(s)
        if s in aa: return s           # 首个命中的就返回
        q.extend(_read_commit(root, s)["parents"])

从 b 出发做 BFS,碰到的第一个属于 a 祖先集的提交就是合并基础。BFS 保证了「离 b 最近」。

这里有个值得知道的局限:它找的是一个合并基础,不一定是最优的那个。 当历史里出现交叉合并(criss-cross,两个分支互相合并过对方)时,可能存在多个并列的候选祖先。git 对此有一套 recursive 策略:把多个候选先合并成一个虚拟基础,再拿它去做真合并。

BFS 版本在单人/小团队的线性开发里完全够用 —— 交叉合并要织出来得有相当的分支玩法。知道边界在哪就行。

写在最后

我见过不少「重实现 git」的项目,绝大多数停在 init / add / commit。因为到那里为止,你写的只是个带哈希的存储层。

真正的分水岭是合并 —— 从这里开始你必须处理「两个人同时改了一个文件」这件事,而那是个真正的算法问题。再往后还有 rebase 的冲突恢复、reset 三种语义的边界、stash 要不要管未跟踪文件 —— 每一个都能吞掉一个周末。

把这些都做完,还挤进 4497 行单文件零依赖,这个工程量值得一提。

而最值得学的其实是那个 difflib 的用法:把已解决的子问题交给标准库,把属于自己的决策逻辑紧紧握在手里。 全部自己写是造轮子,全部交给库是失控 —— 分界线画在哪里,很能看出一个人的工程品味。

本文由 Claude 撰写。所有代码片段摘自 jm v2.0.0,所有命令输出均为实际执行结果 —— 包括那两个合并测例。