:如何用petgraph把整个分支栈装进一张图)
拆解git-stack源码(一):如何用petgraph把整个分支栈装进一张图【免费下载链接】git-stackStacked branch management for Git项目地址: https://gitcode.com/gh_mirrors/gi/git-stack本文是git-stack 源码拆解系列的第一篇。git-stack 是一个Git 分支栈管理工具Stacked branch management帮你自动化分支堆在分支上时的 rebase、fixup 和推送判断。它的核心思路很优雅把仓库里所有堆叠分支装进一张 petgraph 有向图里之后所有复杂操作都变成图上的边移动和节点遍历。这一篇我们就拆开 src/graph/mod.rs看看这张图是怎么建起来的。为什么分支栈需要一张图先回忆一下痛点你创建了feature1在它上面又创建feature2再在feature2上建feature3。这就是一个分支栈。当main前进时你需要把feature1rebase 到main再把feature2rebase 到feature1的新头……手动做就是 README 里那段 40 行的 rebase 命令清单。docs/design.md 对栈的定义是一串提交其中某些提交上插着分支最终落在一个受保护分支的提交上。要同时维护多个这样的栈用线性思维很痛苦——而图天生就是处理这种谁依赖谁的结构。Graph 结构4 个字段装下整个分支栈核心结构 src/graph/mod.rs#L17-L23 只有 4 个字段pub struct Graph { graph: petgraph::graphmap::DiGraphMapgit2::Oid, usize, root_id: git2::Oid, commits: BTreeMapgit2::Oid, BTreeMapAnyId, BoxedResource, pub branches: BranchSet, }字段类型职责graphpetgraph::graphmap::DiGraphMap有向图节点是提交 OID边是提交 → 父提交root_idgit2::Oid整张图的根所有分支的公共 merge basecommitsOID → 资源表挂在每个提交上的标签动作、WIP、推送状态等branchesBranchSet哪个提交上插着哪些分支几个关键设计决策用DiGraphMap而不是DiGraph。petgraph 的DiGraph用内部索引当节点 ID而DiGraphMap允许直接用git2::Oid提交哈希当节点 ID。这样图节点天然就是 git 世界的提交不用再维护一张索引 ↔ OID映射表——这是装进 git 场景的第一块基石依赖见 Cargo.toml#L147petgraph 0.8.3。边权重是usize0 号边表示主父提交。构建图时用parent_ids(commit)的枚举序号当权重src/graph/mod.rs#L57-L59所以primary_parent_of只要找weight 0的出边即可#L143-L147。merge commit 的多个父提交也都如实连边图因此能表达真实拓扑而不是被压扁的线性链。commits是一张类型安全的资源表。每个提交挂一个BTreeMapAnyId, BoxedResourceAnyId基于TypeId见 src/any.rs#L62-L77。任何实现了ResourceTag的类型——ActionPick/Fixup/Protected、Wip、Fixup、PushStatus、Reword等——都能贴到任意提交上互不干扰。这是图 标签模式图负责结构标签负责语义。 顺带一提旧实现 src/legacy/graph/mod.rs 里Node自带children: HashSet节点自己记孩子。新实现把父子关系全部交给 petgraph节点回归纯数据遍历、剪边、改父全部有库函数兜底。建图三步走Graph::from_branches建图入口是 src/graph/mod.rs#L26-L64逻辑三步求根对所有分支端点两两求merge_base滚动得到整张图的root_id——最深的公共祖先。任何一个分支连不上就报NotFound图必须是一棵连通的。定范围对每个分支取branch_id..root_id这个提交区间只把栈内提交收进图root 之下的历史一概不管。连边区间内每个提交按parent_ids顺序把提交 → 各父提交连成带权边。整个过程中BranchSetsrc/graph/branch.rs同步记录哪个 OID 上插着什么分支并区分Mutable / Mixed / Protected / Deleted四种分支种类——受保护分支如main在图中是一堵不可触碰的墙。三个图原语insert / rebase / remove建好图之后git-stack 的所有改写世界的操作都归结为对图做三种手术①rebase—— 移动一条边src/graph/mod.rs#L85-L96let weight self.graph.remove_edge(id, from).unwrap(); self.graph.add_edge(id, to, weight);就这两行把提交id从旧父from摘下来挂到新父to上权重主/次父身份原样保留。git-stack 里把一个分支栈搬个家在图层面就是改一条边——真正的git rebase留到执行脚本阶段才发生。②remove—— 抽掉节点孩子自动接上#L98-L118删除提交时先把它的所有孩子 → 它的边换成孩子 → 它的各父实现 bypass。相当于 git 里 fixup 掉一个提交后后面的提交自动落到再上一级。③insert—— 加节点连边#L66-L83fixup 场景下先把 fixup 提交摘出remove再插到目标提交的后面insert。遍历与剪枝Cursor 的 stop() 是灵魂图上跑操作离不开遍历。src/graph/mod.rs#L246-L296 的AncestorsCursor是一个 BFS 队列node_queue装待访问节点seen集合去重。但最有意思的是stop()方法——它把prior置空让本次迭代到此为止不再扩展下一层。这个设计把遇到受保护分支就停这类业务规则变成了遍历的一等公民。比如rebase_development_branchessrc/graph/ops.rs#L255-L283沿后代遍历遇到Action::Protected就continue遇到分支点就stop()防止重复处理同一条链——受保护分支像一堵墙遍历到墙就停下墙后面的历史永远不被改写。DescendantsCursor#L318-L350同理从根向下逐层推入孩子。图能做什么git sync的本质现在可以看懂 src/graph/ops.rs 里那些操作的本质了protect_branches#L7-L22找出所有受保护分支端点ancestors_of上溯逐个打上Action::Protected标签rebase_development_branches(onto_id)遍历所有后代凡是指向旧受保护基线的非受保护提交执行graph.rebase(id, 旧基线, onto_id)——一次git sync的全部图运算就是批量移动边mark_wip/mark_fixup沿后代打标签识别WIP:、fixup!提交fixup#L597-L705把 fixup 提交remove出来insert到目标提交正后方再把它上面的分支指针全部改指——fixup 归位纯图操作pushable/mark_push_status#L362-L444自下而上沿祖先递归任何祖先有 WIP、受保护或父分支未推就标记Blocked——哪些分支现在能推变成一次图上的标签传播realign_stacks#L708-L772某个分支多了新提交后把悬空的依赖分支rebase边重新对齐到栈顶merge_stacks_by_tree_id#L775-L817rebase 之后若同一提交出现新旧两个副本按tree_id判同、保留最新者把分叉的栈缝回去。最终由to_scripts#L855-L922遍历图把图上的差异翻译成CherryPick / CreateBranch / DeleteBranch等改写脚本交由 src/rewrite/mod.rs 真正落盘。先改图、后执行的架构保证了图算错了仓库毫发无伤图算对了才动 git——这也是 README 里所有永久性变更推迟到最后承诺的实现基础。相关图操作都有测试覆盖可以从 tests/testsuite/graph.rs 和 tests/fixtures/ 下的 YAML 场景fixup、conflict、squash 等入手对照阅读。小结一张图带来的三个好处数据与操作分离git 对象库是只读事实Graph是可随意切割粘贴的计划Oid 即节点DiGraphMap免掉了索引映射图代码与 git 世界零摩擦对接剪枝式遍历Cursor.stop()让到墙就停的栈语义写起来自然无比。下一篇我们沿着to_scripts的产出往下走拆解 src/rewrite/mod.rs图上的边是怎么一步步变成 cherry-pick 命令、分支指针怎么安全回写的。【免费下载链接】git-stackStacked branch management for Git项目地址: https://gitcode.com/gh_mirrors/gi/git-stack创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 拆解git-stack源码(一):如何用petgraph把整个分支栈装进一张图
拆解git-stack源码(一):如何用petgraph把整个分支栈装进一张图【免费下载链接】git-stackStacked branch management for Git项目地址: https://gitcode.com/gh_mirrors/gi/git-stack本文是git-stack 源码拆解系列的第一篇。git-stack 是一个Git 分支栈管理工具Stacked branch management帮你自动化分支堆在分支上时的 rebase、fixup 和推送判断。它的核心思路很优雅把仓库里所有堆叠分支装进一张 petgraph 有向图里之后所有复杂操作都变成图上的边移动和节点遍历。这一篇我们就拆开 src/graph/mod.rs看看这张图是怎么建起来的。为什么分支栈需要一张图先回忆一下痛点你创建了feature1在它上面又创建feature2再在feature2上建feature3。这就是一个分支栈。当main前进时你需要把feature1rebase 到main再把feature2rebase 到feature1的新头……手动做就是 README 里那段 40 行的 rebase 命令清单。docs/design.md 对栈的定义是一串提交其中某些提交上插着分支最终落在一个受保护分支的提交上。要同时维护多个这样的栈用线性思维很痛苦——而图天生就是处理这种谁依赖谁的结构。Graph 结构4 个字段装下整个分支栈核心结构 src/graph/mod.rs#L17-L23 只有 4 个字段pub struct Graph { graph: petgraph::graphmap::DiGraphMapgit2::Oid, usize, root_id: git2::Oid, commits: BTreeMapgit2::Oid, BTreeMapAnyId, BoxedResource, pub branches: BranchSet, }字段类型职责graphpetgraph::graphmap::DiGraphMap有向图节点是提交 OID边是提交 → 父提交root_idgit2::Oid整张图的根所有分支的公共 merge basecommitsOID → 资源表挂在每个提交上的标签动作、WIP、推送状态等branchesBranchSet哪个提交上插着哪些分支几个关键设计决策用DiGraphMap而不是DiGraph。petgraph 的DiGraph用内部索引当节点 ID而DiGraphMap允许直接用git2::Oid提交哈希当节点 ID。这样图节点天然就是 git 世界的提交不用再维护一张索引 ↔ OID映射表——这是装进 git 场景的第一块基石依赖见 Cargo.toml#L147petgraph 0.8.3。边权重是usize0 号边表示主父提交。构建图时用parent_ids(commit)的枚举序号当权重src/graph/mod.rs#L57-L59所以primary_parent_of只要找weight 0的出边即可#L143-L147。merge commit 的多个父提交也都如实连边图因此能表达真实拓扑而不是被压扁的线性链。commits是一张类型安全的资源表。每个提交挂一个BTreeMapAnyId, BoxedResourceAnyId基于TypeId见 src/any.rs#L62-L77。任何实现了ResourceTag的类型——ActionPick/Fixup/Protected、Wip、Fixup、PushStatus、Reword等——都能贴到任意提交上互不干扰。这是图 标签模式图负责结构标签负责语义。 顺带一提旧实现 src/legacy/graph/mod.rs 里Node自带children: HashSet节点自己记孩子。新实现把父子关系全部交给 petgraph节点回归纯数据遍历、剪边、改父全部有库函数兜底。建图三步走Graph::from_branches建图入口是 src/graph/mod.rs#L26-L64逻辑三步求根对所有分支端点两两求merge_base滚动得到整张图的root_id——最深的公共祖先。任何一个分支连不上就报NotFound图必须是一棵连通的。定范围对每个分支取branch_id..root_id这个提交区间只把栈内提交收进图root 之下的历史一概不管。连边区间内每个提交按parent_ids顺序把提交 → 各父提交连成带权边。整个过程中BranchSetsrc/graph/branch.rs同步记录哪个 OID 上插着什么分支并区分Mutable / Mixed / Protected / Deleted四种分支种类——受保护分支如main在图中是一堵不可触碰的墙。三个图原语insert / rebase / remove建好图之后git-stack 的所有改写世界的操作都归结为对图做三种手术①rebase—— 移动一条边src/graph/mod.rs#L85-L96let weight self.graph.remove_edge(id, from).unwrap(); self.graph.add_edge(id, to, weight);就这两行把提交id从旧父from摘下来挂到新父to上权重主/次父身份原样保留。git-stack 里把一个分支栈搬个家在图层面就是改一条边——真正的git rebase留到执行脚本阶段才发生。②remove—— 抽掉节点孩子自动接上#L98-L118删除提交时先把它的所有孩子 → 它的边换成孩子 → 它的各父实现 bypass。相当于 git 里 fixup 掉一个提交后后面的提交自动落到再上一级。③insert—— 加节点连边#L66-L83fixup 场景下先把 fixup 提交摘出remove再插到目标提交的后面insert。遍历与剪枝Cursor 的 stop() 是灵魂图上跑操作离不开遍历。src/graph/mod.rs#L246-L296 的AncestorsCursor是一个 BFS 队列node_queue装待访问节点seen集合去重。但最有意思的是stop()方法——它把prior置空让本次迭代到此为止不再扩展下一层。这个设计把遇到受保护分支就停这类业务规则变成了遍历的一等公民。比如rebase_development_branchessrc/graph/ops.rs#L255-L283沿后代遍历遇到Action::Protected就continue遇到分支点就stop()防止重复处理同一条链——受保护分支像一堵墙遍历到墙就停下墙后面的历史永远不被改写。DescendantsCursor#L318-L350同理从根向下逐层推入孩子。图能做什么git sync的本质现在可以看懂 src/graph/ops.rs 里那些操作的本质了protect_branches#L7-L22找出所有受保护分支端点ancestors_of上溯逐个打上Action::Protected标签rebase_development_branches(onto_id)遍历所有后代凡是指向旧受保护基线的非受保护提交执行graph.rebase(id, 旧基线, onto_id)——一次git sync的全部图运算就是批量移动边mark_wip/mark_fixup沿后代打标签识别WIP:、fixup!提交fixup#L597-L705把 fixup 提交remove出来insert到目标提交正后方再把它上面的分支指针全部改指——fixup 归位纯图操作pushable/mark_push_status#L362-L444自下而上沿祖先递归任何祖先有 WIP、受保护或父分支未推就标记Blocked——哪些分支现在能推变成一次图上的标签传播realign_stacks#L708-L772某个分支多了新提交后把悬空的依赖分支rebase边重新对齐到栈顶merge_stacks_by_tree_id#L775-L817rebase 之后若同一提交出现新旧两个副本按tree_id判同、保留最新者把分叉的栈缝回去。最终由to_scripts#L855-L922遍历图把图上的差异翻译成CherryPick / CreateBranch / DeleteBranch等改写脚本交由 src/rewrite/mod.rs 真正落盘。先改图、后执行的架构保证了图算错了仓库毫发无伤图算对了才动 git——这也是 README 里所有永久性变更推迟到最后承诺的实现基础。相关图操作都有测试覆盖可以从 tests/testsuite/graph.rs 和 tests/fixtures/ 下的 YAML 场景fixup、conflict、squash 等入手对照阅读。小结一张图带来的三个好处数据与操作分离git 对象库是只读事实Graph是可随意切割粘贴的计划Oid 即节点DiGraphMap免掉了索引映射图代码与 git 世界零摩擦对接剪枝式遍历Cursor.stop()让到墙就停的栈语义写起来自然无比。下一篇我们沿着to_scripts的产出往下走拆解 src/rewrite/mod.rs图上的边是怎么一步步变成 cherry-pick 命令、分支指针怎么安全回写的。【免费下载链接】git-stackStacked branch management for Git项目地址: https://gitcode.com/gh_mirrors/gi/git-stack创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考