分支颜色管理深度解析：keifu的lane分配与11色调色板算法是怎么做的

keifu 是一款终端里的 Git TUI 工具，用彩色提交图（commit graph）帮你看清每个分支从哪分叉、在哪里合并。它的分支颜色并不是随机画的：每根分支先被分配到一条 lane（泳道/列），再由一个基于"罚分打分"的算法，从一个 11 色调色板 中挑出最合适的颜色。本文带你完整拆解这套"分支颜色管理"机制，看看 keifu 的 lane 分配算法到底是怎么做的。

一、先搞懂基本概念：什么是 lane

在 keifu 的图中，一行 = 一个 commit，一列 = 一条 lane。每个 commit 节点绘制在自己 lane 的列上，分支线用 Unicode 盒线字符（│ ├ ╭ ╮ ╰ ╯）画出来。

核心数据结构是一个"车道表"：

• lanes 是一个 Vec<Option<Oid>>，每个元素记录该 lane 当前正在跟踪哪个 commit 的 OID；
• 处理每个 commit 时，先查哪条 lane 正在跟踪它——查到就"续行"，查不到就复用第一条空 lane，全部占满就追加新 lane。

这套逻辑位于 src/git/graph.rs，是整张图的骨架。

二、lane 分配的三种典型场景

keifu 从上到下（从新到旧）逐行处理 commit，每条 lane 的生命周期由三种场景驱动：

1️⃣ 续行（最常见） 父 commit 已在某条 lane 上，子 commit 直接沿用这条 lane 和它的颜色。第一父提交（first parent）永远继承同一 lane，保证主线的"直线感"。

2️⃣ 分叉（fork point） 当一个 commit 有 2 个及以上子提交时（比如 main 上拉出 feature 分支），多条 lane 会同时跟踪同一个 commit。此时 keifu 会：

• 额外插入一行"分叉连接线"（形如 ├─┴─╯），把主 lane 与其他 lane 连起来；
• 保留编号最小的 lane 作为主 lane，其余 lane 释放回收。

相关代码见 src/git/graph.rs。

3️⃣ 合并（merge） 当一个 commit 的父提交已在另一条 lane 上跟踪时，编号较大的 lane 到达终点：画一条水平线汇入主 lane，然后释放 lane 和它的颜色，供后续分支复用。合并后的颜色"断线"正是你平时在 git log --graph 里看到的效果，只不过 keifu 多了一层颜色管理。

三、11 色调色板：主分支独享的浅蓝色

keifu 使用一套 11 色循环调色板（定义在 src/graph/colors.rs）：

序号	颜色	备注
0	Cyan 青	常规循环色
1	Green 绿	常规循环色
2	Magenta 品红	常规循环色
3	Yellow 黄	常规循环色
4	Red 红	常规循环色
5–8	LightCyan / LightGreen / LightMagenta / LightYellow	常规循环色
9	LightBlue 浅蓝	主分支专用（reserved）
10	LightRed	常规循环色

两个特殊设计值得注意：

• 主分支独占浅蓝色：MAIN_BRANCH_COLOR = 9，第一个被处理的 commit（即主干）固定分配 LightBlue，并通过 reserve_color 将该颜色登记为"预留"——其他任何分支在打分时都会跳过这个候选，永远抢不走。
• 未提交变更用灰色：索引 usize::MAX 是哨兵值，渲染时映射为 DarkGray，让 uncommitted changes 一行与真实提交明显区分开（见 colors.rs）。

四、ColorAssigner：罚分制打分算法详解

颜色分配的核心是 ColorAssigner 结构体的 assign_color_advanced 方法（源码）。它不随机、也不简单轮换，而是给 11 个候选颜色逐一累加"罚分"，最终选罚分最低的颜色。罚分来自 5 条规则：

#	规则	权重	目的
1	该 lane 上一次用过的颜色	+10	分支复用 lane 时换色，避免"看起来像同一条线"
2	其他活跃 lane 正在使用的颜色	8.0 / (列距 + 1.0)，距离越近罚越重	相邻列颜色错开，横向一眼可辨
3	最近 6 行内的分配历史	行距权重 4.0/(d+1) × 列距权重 2.0/(d+1)	避免纵向"同色连珠"
4	同一 fork 内已分配的兄弟颜色	+100（近乎一票否决）	同一分叉点的多个分支必须不同色
5	颜色使用频率	(count / max) × 2.0	用得多的颜色罚得重，长期均衡分布

选好颜色后，ColorAssigner 还会更新三本"账"：该 lane 的颜色、最近 6 行分配历史（滑动窗口）、每个颜色的使用计数器。主 lane 的 continue_lane 则永远直接返回浅蓝，不参与打分。

五、特殊场景的颜色处理

• 未提交变更行：始终显示为灰色，并插在图的最顶端。keifu 会优先把这条"灰色线"接到当前 HEAD 所在的 lane；若该列被占用，则寻找距离 HEAD 最近的一条空列，画一条水平连接线汇入（源码）。
• fork 兄弟：merge commit 的第二个父提交（以及热点分叉点）会调用 assign_fork_sibling_color，触发规则 4 的 +100 罚分，保证从一个点分出的多条分支颜色互不相同。
• 分支结束：release_lane 清空该 lane 的颜色（主 lane 除外），让颜色池回归可用状态。

六、总结：从 commit 到像素的三步流水线

阶段	做了什么	源码位置
① 布局	构建 lane 表、fork/merge 连接符，产出每行的 Cell	src/git/graph.rs
② 上色	罚分算法为每条 lane 挑选调色板颜色	src/graph/colors.rs
③ 渲染	Cell 映射为盒线字符并套用颜色，分支标签加粗同色	src/ui/graph_view.rs

回到开头的问题：keifu 的分支颜色管理 = lane 分配解决"在哪一列"，11 色调色板 + 5 条罚分规则解决"用什么颜色"。想动手验证，在任意 Git 仓库里运行 keifu，按 ? 查看帮助即可；更多配置项参见 docs/configuration.md。