从零到一构建智能终端(五)：Git 提交图的可视化算法

引言

Git 的提交历史是一个有向无环图（DAG），每个提交可以有多个父节点（合并）和多个子节点（分支）。将这个 DAG 渲染成类似 git log --graph 的二维图形，需要解决两个核心问题：

X 轴分配：每个提交应该放在哪一列？
连线绘制：如何连接子提交和父提交？

本文介绍一种简洁有效的算法——列占用法（Column Reservation）。

问题建模

输入

Git 提交列表，按时间倒序排列（最新的在前）：

typescriptinterface CommitInfo {
  hash: string
  parents: string[]  // 父提交的 hash 列表
  message: string
  // ...其他字段
}

关键点：

parents[0] 是"第一父提交"（主线）
parents[1...] 是"其他父提交"（合并进来的分支）

输出

节点和边的坐标信息：

typescriptinterface GraphNode {
  commit: CommitInfo
  x: number      // 列号（0, 1, 2, ...）
  index: number  // 行号（在列表中的位置）
  color: string  // 该列的颜色
}

interface GraphEdge {
  fromHash: string
  fromX: number
  toHash: string
  toX: number
  color: string
}

列占用算法

核心思想

维护一个"列状态数组" columns，记录每一列当前被哪个提交"占用"：

columns[x] = commitHash  // 该列被某个提交占用
columns[x] = null        // 该列空闲

当处理一个提交时：

找到它应该在的列（可能已被预留，或者找一个空闲的）
清空该列（我们已经"到达"了）
为它的父提交预留列

算法步骤

输入: commits[] 按时间倒序
输出: nodes[], edges[]

初始化:
  columns = []           // 列状态数组
  hashToIndex = Map()    // hash → 行号的映射

预处理:
  for i, commit in commits:
    hashToIndex[commit.hash] = i

主循环:
  for i, commit in commits:
    hash = commit.hash
    parents = commit.parents

    // 步骤1: 确定当前提交的列
    myX = columns.indexOf(hash)
    if myX == -1:
      // 没有预留列，找一个空闲的
      myX = columns.indexOf(null)
      if myX == -1:
        // 没有空闲列，新建一列
        myX = columns.length
        columns.push(null)

    // 步骤2: 清空该列（我们已到达）
    columns[myX] = null

    // 记录节点
    nodes.push({ commit, x: myX, index: i })

    // 步骤3: 为父提交预留列
    for p, parentHash in parents:
      parentIndex = hashToIndex[parentHash]
      if parentIndex == undefined:
        continue  // 父提交不在当前视图中

      parentX = columns.indexOf(parentHash)

      if parentX == -1:
        // 父提交还没有预留列
        if p == 0:
          // 第一父提交：继承当前列（主线延续）
          parentX = myX
          columns[myX] = parentHash
        else:
          // 其他父提交：需要新列（合并线）
          parentX = columns.indexOf(null)
          if parentX == -1:
            parentX = columns.length
            columns.push(null)
          columns[parentX] = parentHash

      // 记录边
      edges.push({
        fromHash: hash, fromX: myX,
        toHash: parentHash, toX: parentX
      })

执行示例

考虑以下提交历史（从上到下时间递增）：

A ← B ← D ← F  (main)
     ↖ C ← E ↗ (feature，在 F 合并)

提交顺序（倒序）：[F, E, D, C, B, A]

父子关系：

F: parents = [D, E]（合并提交）
E: parents = [C]
D: parents = [B]
C: parents = [B]
B: parents = [A]
A: parents = []

执行过程：

步骤	处理	columns 状态	分配 X
1	F	[null] → [D]	F→0, 预留 D→0, E→1
2	E	[D, E] → [D, C]	E→1, 预留 C→1
3	D	[D, C] → [B, C]	D→0, 预留 B→0
4	C	[B, C] → [B, B]	C→1, 预留 B→0（已有）
5	B	[B, B] → [A, null]	B→0, 预留 A→0
6	A	[A, null] → [null, null]	A→0

最终布局：

列:    0    1
       F────┐
       │    E
       D    │
       │    C
       B←───┘
       │
       A

关键设计决策

第一父提交继承当前列

这是让图形美观的关键：

typescriptif (p === 0) {
  // First parent: stays in same column (main line continues)
  parentX = myX
  columns[myX] = parentHash
}

如果不这样做，主线会频繁跳列，看起来很乱。

合并提交的处理

当一个提交有多个父节点时（合并提交）：

第一父提交（被合并进的分支，通常是 main）→ 继承当前列
其他父提交（被合并的分支）→ 分配新列

这保证了主线保持垂直，分支线斜向合入。

列复用

当一个提交被处理后，它占用的列就释放了：

typescriptcolumns[myX] = null

后续提交可以复用这个列，避免列数无限增长。

SVG 路径生成

有了节点坐标，需要绘制连接线。

直线 vs 曲线

如果起点和终点在同一列，画直线：

typescriptif (fromX === toX) {
  return `M ${x1} ${y1} L ${x2} ${y2}`
}

如果跨列，画贝塞尔曲线：

typescriptconst controlY = y1 + Math.abs(y2 - y1) * 0.3
return `M ${x1} ${y1} C ${x1} ${controlY}, ${x2} ${controlY}, ${x2} ${y2}`

这里用三次贝塞尔曲线（Cubic Bezier），控制点设置为：

控制点1：(x1, controlY) — 从起点垂直向下
控制点2：(x2, controlY) — 在终点列垂直向下

效果是：线条先垂直向下，然后平滑转向目标列。

为什么用 0.3 系数

typescriptconst controlY = y1 + Math.abs(y2 - y1) * 0.3

这个 0.3 控制曲线的"弯曲程度"：

太小（如 0.1）：曲线太尖锐
太大（如 0.5）：曲线太平缓，可能与其他线重叠
0.3 是经验值，视觉效果较好

颜色分配

每一列分配一个固定颜色：

typescriptconst LANE_COLORS = [
  '#f97316', '#eab308', '#22c55e', '#06b6d4',
  '#3b82f6', '#8b5cf6', '#ec4899', '#ef4444'
]

const getLaneColor = (lane: number) => LANE_COLORS[lane % LANE_COLORS.length]

8 种颜色循环使用。边的颜色继承目标列的颜色（columnColors[parentX]），这样视觉上能追踪分支流向。

Y 坐标计算

X 坐标由算法分配，Y 坐标有两种策略：

固定行高

最简单的方案：

typescriptconst ROW_HEIGHT = 28
const getNodeY = (index: number) => index * ROW_HEIGHT + ROW_HEIGHT / 2

每个提交占一行，Y 坐标直接由行号计算。

动态行高

当提交行展开显示文件列表时，行高会变化。需要动态计算：

typescriptconst commitRowCenterY = new Map<string, number>()

const updateCommitRowCenters = () => {
  for (const [hash, rowEl] of commitRowRefs) {
    const infoHeight = rowEl.querySelector('.commit-info')?.offsetHeight ?? ROW_HEIGHT
    commitRowCenterY.set(hash, rowEl.offsetTop + infoHeight / 2)
  }
}

const getNodeY = (hash: string, index: number) => {
  return commitRowCenterY.get(hash) ?? index * ROW_HEIGHT + ROW_HEIGHT / 2
}

每次行高变化（展开/折叠）后，重新计算所有节点的 Y 坐标。

渲染层次

SVG 图层需要正确的层次关系：

1. 边（path）— 底层
2. 节点外圈（circle，背景色）— 中层
3. 节点内圈（circle，彩色）— 顶层

这样节点会盖住经过它的边，看起来更清晰：

html<svg>
  <!-- 先画所有边 -->
  <path v-for="edge in edges" :d="getEdgePath(edge)" />

  <!-- 再画所有节点 -->
  <g v-for="node in nodes">
    <circle r="5" fill="背景色" />  <!-- 外圈，遮住边 -->
    <circle r="4" :fill="node.color" />  <!-- 内圈，实际颜色 -->
  </g>
</svg>

边界情况处理

父提交不在视图中

当滚动加载时，可能只加载了部分历史。如果父提交不在当前列表中：

typescriptconst parentIndex = hashToIndex.get(parentHash)
if (parentIndex === undefined) {
  continue  // 跳过，不画这条边
}

这条边会在加载更多提交后出现。

空提交列表

typescriptif (commits.length === 0) {
  return { nodes: [], edges: [], maxX: 0 }
}

无父提交（初始提交）

初始提交的 parents 为空数组，算法自然处理——不会创建任何边。

性能考虑

时间复杂度

主循环：O(n)，n 是提交数量
columns.indexOf()：O(k)，k 是当前列数（通常很小，< 10）
总体：O(n × k) ≈ O(n)

空间复杂度

columns：O(k)
nodes 和 edges：O(n + e)，e 是边数（最多 2n）
总体：O(n)

增量更新

当加载更多提交时，可以选择：

重新计算：简单，代码已经是 O(n)
增量追加：复杂，需要保存中间状态

对于几百条提交，重新计算完全可以接受（< 1ms）。

与其他算法对比

算法	复杂度	美观度	适用场景
列占用法	O(n)	良好	一般场景
拓扑排序+层次布局	O(n log n)	优秀	复杂 DAG
力导向布局	O(n²)	可变	交互式探索

列占用法是简单与效果的平衡点，适合 Git 这种"主要是线性，偶尔分支合并"的 DAG 结构。

总结

Git 提交图可视化的核心是列占用法：

维护列状态数组，记录每列被哪个提交占用
处理提交时：找到或分配列 → 清空列 → 为父提交预留列
第一父提交继承当前列，保持主线垂直
跨列边用贝塞尔曲线，同列边用直线
正确处理渲染层次：边在底，节点在顶

这个算法的优点是单次遍历完成布局，不需要回溯或多轮迭代，非常适合实时渲染场景。

引言