Git 提交图谱的 Lane 算法笔记：gitio 是怎么把提交历史画出来的

更新: 5/22/2026 字数: 0 字 时长: 0 分钟

前言

最近在整理我自己的 gitio 项目时，我专门回头看了一遍里面的提交图谱实现。

这个功能表面上看，好像只是“把 commit 画成一列，再顺手连几条线”那么简单。但真开始做的时候很快就会发现，事情没那么轻。只要历史稍微复杂一点，光是“线不能断”“merge 不能接错”“mainline 不能一会儿跑左边一会儿跑右边”，就已经够你反复打磨很多轮了。

本文讲的就是左边这条线，长这样的。

尤其是碰到这些场景的时候：

• 嵌套 merge
• 并行 sub-branch
• 多条分支同时汇回
• octopus merge
• first-parent 不在当前最左 lane

这时候如果只是临时按“前一个 commit 连到后一个 commit”去画，最后出来的图大概率会很快乱掉。

gitio 里这套实现，核心文件在 src/composables/useCommitGraph.ts。它做的事情，本质上不是“直接画图”，而是先把一串线性提交记录，变成一组适合逐行渲染的 lane 规划结果，然后再把这些规划结果转换成 SVG 里的节点、竖线和曲线。

说白了，这套算法真正解决的问题是：

怎么把 Git 的拓扑关系，稳定地投影成一个按行展开的二维图谱。

整体思路

这套实现的输入，不是任意图结构，而是已经按 git log --topo-order 排好的提交序列。

也就是说，进入算法的时候，提交本身已经是一条“线性序列”了。算法要做的，不是重新排序，而是回答另一件事：

对于序列里的每一行 commit，它应该落在哪个 lane，这一行上面要接哪些线，下面又要延续哪些线，中间该画哪些弯曲连接。

整个过程分成两段：

git log → planRows() → RowPlan[] → renderRow() → GraphRow[] → SVG
          ↑                           ↑
     分配 lane / 规划曲线          按快照推导竖线

这一步拆得很值。

因为“规划 lane”和“真正渲染线条”其实不是一回事。前者更像在维护一组活动轨道，后者才是把结果翻译成 SVG 的可视元素。如果这两件事混在一起写，代码会很容易变得既难调又难解释。

在 gitio 里，每一行 commit 最后都会被拆成四种可视信息：

• 节点圆点，也就是当前 commit 所在的 lane
• 顶部竖线，表示哪些 lane 从上方延续下来
• 底部竖线，表示哪些 lane 还要继续往下等待 parent
• 曲线，表示 lane 之间的衔接，比如分出去、汇回来、迁移回 mainline

这样一来，渲染阶段其实就很清楚了。它不需要重新理解 Git 拓扑，只需要老老实实把前面规划好的结果画出来。

这套实现里最关键的，不是曲线，而是状态快照

如果只从视觉上看，很多人第一反应会把注意力放在那些弯曲的 merge 线条上。但实际上，这套实现真正的核心，不是曲线本身，而是它在扫描过程中保存的 lane 状态快照。

里面有两个很重要的概念：一个是活动 lane 的占用记录 LaneSlot，一个是单行规划结果 RowPlan。

LaneSlot 很简单，它记录某条 lane 当前正在等待哪个 commit：

interface LaneSlot {
  expecting: string
  colorIndex: number
}

扫描过程中维护的是一个动态数组：

lanes: Array<LaneSlot | null>

这个数组的索引，本身就是 lane 编号。lane 0 默认就是最左那条 mainline。

而 RowPlan 才是真正把“这一行该怎么画”固定下来的东西。它里面不只记当前 commit 在哪一列，还会记录进入本行和离开本行时，所有 lane 的状态。

interface RowPlan {
  commit: CommitNode
  laneIn: Array<LaneSlot | null>
  laneOut: Array<LaneSlot | null>
  nodeLane: number
  nodeColorIndex: number
  curves: GraphCurve[]
  topConsumed: Set<number>
  bottomConsumed: Set<number>
}

这里最关键的地方在于：

它把一条 lane 的“上半段”和“下半段”拆开看了。

也就是：

• laneIn 用来推导顶部竖线
• laneOut 用来推导底部竖线

这件事看起来只是数据结构层面的细分，但其实正是它能处理复杂 merge 的关键。因为只要某条 lane 在这一行里被一条曲线吃掉了，就不能再把它当成一根完整直线去画。上半段可能还在，下半段却可能已经被 out 或 in 曲线替代了。

如果不做这种拆分，最后就很容易出现直线和弯线重叠、merge 节点旁边断层，或者 lane 明明该连续却突然断开的情况。

五种曲线语义，才是这套图谱稳定的基础

useCommitGraph.ts 里没有把所有跨 lane 的连接都粗暴地归成一种“弯线”。它专门定义了五种曲线语义：

• out
• branch-in
• in
• join
• migrate

这个区分非常重要，因为它们看起来都像“从一条 lane 连到另一条 lane”，但拓扑含义并不一样。

out

out 表示从当前节点中线，向下分出一条新的 lane。

它通常出现在 merge commit 处理次父的时候：如果这个 parent 之前没有任何 lane 在等它，就说明这是一个全新的 sub-branch，需要新开 lane，然后从当前节点往那条新 lane 画一条向下的曲线。

in

in 表示某条 lane 从上面汇入当前节点。

它对应的场景是：有多条 lane 同时在等待当前这个 commit，那么最左的一条会被选为 nodeLane，其余那些 lane 则需要在本行通过 in 曲线一起汇入当前节点。

这个动作会消耗顶部竖线，也就是 topConsumed 要记上它。

branch-in

branch-in 看起来和 in 很像，都是节点和右上方某条 lane 之间的连接，但语义正好反过来。

它表示的是：当前 merge 的次父，正好就是上方某条已经存在的 lane 正在等待的那个 parent。这时候视觉上需要从当前节点向上接过去，但那条 lane 的顶部竖线不能被吃掉，因为它上面还有延续。

这就是 branch-in 和 in 最大的区别。

很多图谱实现出问题，往往就出在这里：把这两种情况混成一种弧线来画，结果就是 merge 节点边上要么断层，要么多画一段重叠线。

join

join 表示当前 commit 自己是某条 sub-branch 的 tip，现在它要汇回更左边那条 lane。

也就是当前节点在右边，但它的 first-parent 已经在左边某条 existing lane 里了。这时候不应该强行把节点挪过去，而应该保留节点当前所在位置，再用一条 join 曲线把它接回 mainline。

migrate

migrate 是这套实现里我觉得特别关键的一种处理。

它对应的是这样一种情况：当前 commit 的 first-parent 已经落在 nodeLane 右边了。

这在嵌套合并里很常见。如果你不处理，mainline 很快就会开始左右漂移，整张图会失去“主线始终尽量靠左”的稳定感。

所以这里的做法很明确：

• 把右侧那条 lane 释放掉
• 在当前 nodeLane 重新接上 first-parent
• 用一条 migrate 曲线，从右上方拉回当前节点

这个动作也会消耗顶部竖线，所以它和 in 一样，要进 topConsumed。

说白了，migrate 干的事就是：

不让 first-parent 把 mainline 带跑偏。

扫描阶段真正做的，是三步

整个 planRows() 的扫描逻辑，基本可以概括成 A、B、C 三步。

第一步：先决定当前节点落在哪个 lane

算法会先去当前 lanes 里找，哪些 lane 正在等待当前这个 commit，也就是找：

slot.expecting === commit.hash

如果找到了，说明当前 commit 不是“凭空冒出来”的，而是被上面某些提交当 parent 等着的。

这时候：

• 最左那条 waiting lane 会变成 nodeLane
• 颜色也继承它，保证主线颜色尽量连续
• 其他所有也在等当前 commit 的 lane，都会通过 in 曲线汇入 nodeLane
• 同时，这些其他 lane 会被释放掉

如果一条都没找到，那说明这是一个新分支起点，或者当前序列里它第一次出现。这种情况下就直接找最左空位：

nodeLane = findFreeLane(lanes)

如果这个位置正好是 lane 0，那它用 mainline 默认颜色；否则就分配一个新的颜色索引。

最后不管哪种情况，当前 nodeLane 本身都会被消耗掉，因为这个节点已经落下来了：

lanes[nodeLane] = null

第二步：给当前 commit 的 parents 安排去向

这一步才是整套 lane 逻辑最复杂的地方。

算法会按 commit.parents 的顺序逐个处理。首父和非首父，策略完全不同。

首父处理

首父的目标只有一个：

尽量让 mainline 延续在最左。

如果当前 first-parent 还没有任何 lane 在等它，那最简单，直接让它占用 nodeLane。

如果它已经在 nodeLane，那就继续保持。

如果它已经在更左边某条 lane 上，说明当前节点其实是某个 sub-branch 的 tip，这时候当前节点不应该去抢 mainline 的位置，而应该通过 join 接回去。

如果它已经在更右边某条 lane 上，那就说明主线偏了。这时触发 migrate：

• 记录一条从右侧 lane 到当前 nodeLane 的曲线
• 释放右边那条 lane
• 把 first-parent 重新放回 nodeLane

这就是为什么最后出来的图，mainline 通常能比较稳定地贴在左边，而不会像很多简化实现那样左右横跳。

非首父处理

非首父的逻辑更像在说：

这是分支关系，不是主线继承关系。

如果已经有某条 lane 在等待这个 parent，那就不改 lanes，只补一条 branch-in 曲线，把当前节点往上接过去。

如果没有任何 lane 在等它，那就要新开一条 lane。但这里也不是随便开，而是找最左空位，同时避开当前 nodeLane，避免覆盖自己。

然后：

• 给新 lane 分配颜色
• 让它开始等待这个 parent
• 画一条 out 曲线，从当前节点分出去
• 标记 bottomConsumed

这一步处理完，本行所有 parent 的“未来去向”其实就都固定了。

第三步：裁掉尾部空 lane

这一步看起来很小，但其实也挺重要。

每一行处理完后，算法会把 lane 数组末尾连续的空位裁掉：

while (lanes.length > 0 && !lanes[lanes.length - 1]) {
  lanes.pop()
}

这相当于告诉渲染层：

当前历史走到这里，右边那些已经彻底不用的 lane 可以收回去了。

如果不做这一步，图谱宽度只会越来越大，很多已经结束的分支也会一直留下空列，视觉上会显得特别拖沓。

渲染阶段反而简单了很多

前面把 lane 和曲线都规划完之后，真正渲染一行时反而没那么复杂。

renderRow() 基本就是按 laneIn 和 laneOut 去推导顶部、底部竖线。

顶部竖线来自 laneIn，但前提是这条 lane 没被 topConsumed 吃掉。

底部竖线来自 laneOut，但前提是这条 lane 没被 bottomConsumed 代替。

逻辑其实很直白：

for lane in laneIn:
  if laneIn[lane] && !topConsumed.has(lane)
    topLines.push(...)

for lane in laneOut:
  if laneOut[lane] && !bottomConsumed.has(lane)
    bottomLines.push(...)

这里的关键，不在这几行代码本身，而在于前面那套状态规划已经把问题拆干净了。

所以渲染层不用再理解：

• 哪条线是不是 merge 线
• 哪条 lane 是不是主线
• 这条弧线有没有把直线吃掉

这些都已经在 RowPlan 阶段决定好了。

这也是为什么我会觉得，这种“先 plan，再 render”的结构非常适合这种图谱问题。它把复杂性锁在前面，后面的输出就会稳很多。

SVG 几何其实也有几个细节挺关键

这套图谱每行高度是 32px，里面有三条关键水平线：

• y=0：行顶
• y=16：节点中线
• y=32：行底

节点圆点就在 y=16 这条中线上。

顶部竖线和底部竖线不是随便连的。代码里专门让它们和节点有一点点重叠，这样视觉上不会在节点边缘露缝。

另外还有一个细节是用了 stroke-linecap="square"，让端点多延伸半个描边宽度。这个小动作对跨行衔接特别有用，不然很容易出现那种肉眼能看到的亚像素缝隙。

曲线部分则统一用三次贝塞尔去画。

不同类型的曲线，起止点不一样：

• in / migrate：从顶部下来到节点中线
• branch-in：从节点中线往上接到已有 lane 顶部
• out / join：从节点中线往下连到目标 lane 底部

而且代码里专门把顶端和底端稍微越出 viewBox 一点，比如 -0.5 和 32.5，目的也是一样：尽量避免跨行接缝。

这些都不是算法主干，但它们决定了最后成品看起来是不是“真连续”。

这套实现真正值钱的地方，不只是能画出来

如果只是想做一个“能看”的 commit graph，其实很多简化方案都能凑出来。

但 gitio 这套实现更有价值的地方在于，它不是只对普通两三条分支的 happy path 负责，而是把一些真正会把图谱搞乱的情况提前考虑进去了。

比如：

• 多条 lane 同时等待同一个 commit，怎么汇入
• merge 的次父如果已经在上方 lane 里等待，应该是 branch-in 而不是 in
• first-parent 一旦跑到右边，怎么迁回最左 mainline
• 一条新 sub-branch 开出来之后，下半段直线该不该继续画
• lane 什么时候该收缩，什么时候不能乱裁

这些东西单独看都不算大，但它们加在一起，才决定最后这张图是“看上去像 git graph”，还是“真能在复杂历史里保持稳定”。

为什么我最后会把它拆成这套结构

回头看这部分代码，我自己现在最认同的一点，其实不是某个具体曲线公式，而是整个建模方式。

也就是这三层：

• 活动 lane：LaneSlot
• 行规划快照：RowPlan
• 最终渲染数据：GraphRow

这个分层让“拓扑关系”和“图形输出”之间有了一个中间层。很多复杂问题，都是在中间层被消化掉的。

这样后面不管是调 SVG、换样式、改颜色、加筛选，还是继续优化 lane 行为，都不会直接把 Git 拓扑逻辑搅成一团。

说白了，这套实现最后真正靠谱的原因，不是它把每根线都硬算得多聪明，而是它先把问题拆对了。

结语

Git 提交图谱这类功能，很容易在第一眼被低估。

因为它看起来只是“左边多画几根线”，但真做起来，背后其实是在处理一个拓扑序列到二维布局的映射问题。你既要让分支关系说得通，又得让图看起来稳定，还得处理那些一复杂就开始露底的 merge 场景。

gitio 里这版 useCommitGraph.ts，至少对我自己来说，最大的收获不是“终于把图画出来了”，而是把这件事想清楚了：

提交图谱不是直接画边，而是先规划 lane，再渲染行。

一旦这个思路顺了，后面的很多问题反而都会跟着顺下来。

如果后面我还继续打磨这块，大概率也还是会沿着这个方向走：不是把逻辑越堆越多，而是继续让 lane 规划和渲染语义保持清晰。