:拓扑排序生成rebase脚本的完整执行原理)
拆解git-stack源码(二):拓扑排序生成rebase脚本的完整执行原理【免费下载链接】git-stackStacked branch management for Git项目地址: https://gitcode.com/gh_mirrors/gi/git-stackgit-stack 是一款用 Rust 编写的 Git 堆叠分支Stacked Branch管理工具让你可以像搭积木一样把功能分支一层层叠起来开发。当底层分支更新后整条分支链需要重新 rebase——git-stack 的做法是把整条链转换成一份可执行的rebase 脚本并用拓扑排序决定脚本中各批次的执行顺序。本文带你拆解这套生成与执行机制的原理。一、为什么要把 rebase 变成脚本普通开发者熟悉的是对单个分支执行git rebase。但在堆叠分支场景下一个子分支往往依赖父分支的提交master ── A ── B └── 父分支(分支1) ── C └── 子分支(分支2) ── D一旦 master 前进分支1 必须先rebase 完分支2 才能基于新的 C 重新 rebase。顺序错了所有引用都会错位。git-stack 的解法是不直接操作分支而是把整条分支链的重写计划先编译成一份类似git rebase -i待办清单的脚本再按依赖顺序逐批执行。这样计划与执行分离出了问题还能 dry-run 预览。二、脚本的三层结构Script、Batch、Command 脚本的数据结构定义在 src/rewrite/mod.rs 中自顶向下分三层层级结构体含义脚本Script一组按顺序执行的Batch列表批次Batch针对一个分支的一组操作记录基线提交onto_mark与该分支上的命令命令Command具体动作CherryPickpick、Fixupsquash、Reword、CreateBranch、DeleteBranch、RegisterMark每个Batch渲染出来就是一段 rebase 脚本片段先reset到基线然后依次pick/fixup/reword各提交必要时用exec创建或删除分支。多个批次拼起来就是一份完整的 rebase 脚本。三、构建依赖图gen_graph 把谁依赖谁画出来执行顺序的关键是搞清楚批次之间的依赖关系。gen_graph函数位于 src/rewrite/mod.rs遍历所有批次向一张有向图petgraph::DiGraphMap中添加两类边基线 → 批次批次必须基于它的onto_mark通常是父分支的某个提交才能执行批次 → 标记批次在重写过程中RegisterMark了某些提交后依赖这些标记的子批次才能执行。用图来说一条分支链会变成(onto: master) ──▶ [批次1: rebase分支1] ──▶ (mark: C) └──▶ [批次2: rebase分支2]这正是典型的有向无环图DAG——而处理 DAG 顺序的教科书算法就是拓扑排序。四、拓扑排序让父分支永远先执行 sort_batches函数调用了 petgraph 提供的algo::toposort本质是 Kahn 算法对依赖图排序不断从图中取出入度为 0所有前置依赖都已完成的节点把它加入结果序列并移除它指向的边更新入度重复直到图为空得到的线性序列就是一个合法的执行顺序。排序结果中混着批次节点和标记节点sort_batches过滤掉标记节点只按顺序还原出批次列表。于是得到保证父分支批次一定排在子分支批次之前rebase 时永远不会引用到尚未重写的旧提交。五、infer_marks自动补全 label 标记批次之间通过标记label/mark互相引用父批次在重写完提交 C 后注册一个标记子批次用这个标记定位新的基线。infer_marks函数会检查每个批次期望的onto_mark如果它出现在某个批次的重写命令里就自动插入RegisterMark命令并在渲染时输出对应的label指令。这一步让开发者无需手动维护任何引用标记关系全自动推导。六、Script::from三步流水线把上面的环节串起来就是Script的构造入口src/rewrite/mod.rs 的FromVecBatch实现一个清晰的三步流水线Batch 列表 ──▶ gen_graph 构建依赖图 ──▶ sort_batches 拓扑排序确定批次顺序 ──▶ infer_marks 补全 label 标记 ──▶ 最终 Script七、Executor按顺序逐批执行脚本脚本生成后Executor同样位于 src/rewrite/mod.rs负责执行对每个批次依次reset到基线逐个执行 pick / fixup / reword / 分支创建命令并维护marks表旧提交 → 新提交的映射若某批次失败立即abandon丢弃半成品并跳过所有依赖它的后续批次把受影响的分支名一并报告给用户——依赖图在这里再次发挥作用能精确算出谁该被跳过支持dry_run模式只做计划不落地方便预览。八、上游视角to_scripts 如何切分出批次脚本的原料批次从哪里来答案在 src/graph/ops.rs 的to_scripts函数从提交图根节点开始用descendants()游标做广度优先遍历遇到受保护提交如 master 上的提交时把之前的分支链切成一个独立批次gather_script递归收集每个提交的动作pick、fixup、reword、建分支组装成Batch。命令行入口如git stack --rebase见 src/bin/git-stack/sync.rs正是调用to_scripts得到批次列表再交给Script::from流水线完成排序与标记。整条链路提交图 → 批次 → 依赖图 → 拓扑排序 → 可执行 rebase 脚本。小结一张表看懂全流程 ✅阶段关键函数作用切分批次to_scriptssrc/graph/ops.rs按分支链切出 Batch 序列构建依赖gen_graphsrc/rewrite/mod.rs批次间依赖 → DAG确定顺序sort_batchestoposort拓扑排序父分支优先补全引用infer_marks自动生成 label/mark执行Executor::run逐批执行失败跳过依赖项拓扑排序看似只是一个图算法却是 git-stack 能安全重写整条分支栈的基石它把分支依赖这种复杂关系转化成了确定、可预览、失败可回退的执行顺序。如果你想继续阅读可以从 docs/design.md 了解堆叠分支的设计目标再回到 src/graph/mod.rs 看提交图本身是如何构建的。【免费下载链接】git-stackStacked branch management for Git项目地址: https://gitcode.com/gh_mirrors/gi/git-stack创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 拆解git-stack源码(二):拓扑排序生成rebase脚本的完整执行原理
拆解git-stack源码(二):拓扑排序生成rebase脚本的完整执行原理【免费下载链接】git-stackStacked branch management for Git项目地址: https://gitcode.com/gh_mirrors/gi/git-stackgit-stack 是一款用 Rust 编写的 Git 堆叠分支Stacked Branch管理工具让你可以像搭积木一样把功能分支一层层叠起来开发。当底层分支更新后整条分支链需要重新 rebase——git-stack 的做法是把整条链转换成一份可执行的rebase 脚本并用拓扑排序决定脚本中各批次的执行顺序。本文带你拆解这套生成与执行机制的原理。一、为什么要把 rebase 变成脚本普通开发者熟悉的是对单个分支执行git rebase。但在堆叠分支场景下一个子分支往往依赖父分支的提交master ── A ── B └── 父分支(分支1) ── C └── 子分支(分支2) ── D一旦 master 前进分支1 必须先rebase 完分支2 才能基于新的 C 重新 rebase。顺序错了所有引用都会错位。git-stack 的解法是不直接操作分支而是把整条分支链的重写计划先编译成一份类似git rebase -i待办清单的脚本再按依赖顺序逐批执行。这样计划与执行分离出了问题还能 dry-run 预览。二、脚本的三层结构Script、Batch、Command 脚本的数据结构定义在 src/rewrite/mod.rs 中自顶向下分三层层级结构体含义脚本Script一组按顺序执行的Batch列表批次Batch针对一个分支的一组操作记录基线提交onto_mark与该分支上的命令命令Command具体动作CherryPickpick、Fixupsquash、Reword、CreateBranch、DeleteBranch、RegisterMark每个Batch渲染出来就是一段 rebase 脚本片段先reset到基线然后依次pick/fixup/reword各提交必要时用exec创建或删除分支。多个批次拼起来就是一份完整的 rebase 脚本。三、构建依赖图gen_graph 把谁依赖谁画出来执行顺序的关键是搞清楚批次之间的依赖关系。gen_graph函数位于 src/rewrite/mod.rs遍历所有批次向一张有向图petgraph::DiGraphMap中添加两类边基线 → 批次批次必须基于它的onto_mark通常是父分支的某个提交才能执行批次 → 标记批次在重写过程中RegisterMark了某些提交后依赖这些标记的子批次才能执行。用图来说一条分支链会变成(onto: master) ──▶ [批次1: rebase分支1] ──▶ (mark: C) └──▶ [批次2: rebase分支2]这正是典型的有向无环图DAG——而处理 DAG 顺序的教科书算法就是拓扑排序。四、拓扑排序让父分支永远先执行 sort_batches函数调用了 petgraph 提供的algo::toposort本质是 Kahn 算法对依赖图排序不断从图中取出入度为 0所有前置依赖都已完成的节点把它加入结果序列并移除它指向的边更新入度重复直到图为空得到的线性序列就是一个合法的执行顺序。排序结果中混着批次节点和标记节点sort_batches过滤掉标记节点只按顺序还原出批次列表。于是得到保证父分支批次一定排在子分支批次之前rebase 时永远不会引用到尚未重写的旧提交。五、infer_marks自动补全 label 标记批次之间通过标记label/mark互相引用父批次在重写完提交 C 后注册一个标记子批次用这个标记定位新的基线。infer_marks函数会检查每个批次期望的onto_mark如果它出现在某个批次的重写命令里就自动插入RegisterMark命令并在渲染时输出对应的label指令。这一步让开发者无需手动维护任何引用标记关系全自动推导。六、Script::from三步流水线把上面的环节串起来就是Script的构造入口src/rewrite/mod.rs 的FromVecBatch实现一个清晰的三步流水线Batch 列表 ──▶ gen_graph 构建依赖图 ──▶ sort_batches 拓扑排序确定批次顺序 ──▶ infer_marks 补全 label 标记 ──▶ 最终 Script七、Executor按顺序逐批执行脚本脚本生成后Executor同样位于 src/rewrite/mod.rs负责执行对每个批次依次reset到基线逐个执行 pick / fixup / reword / 分支创建命令并维护marks表旧提交 → 新提交的映射若某批次失败立即abandon丢弃半成品并跳过所有依赖它的后续批次把受影响的分支名一并报告给用户——依赖图在这里再次发挥作用能精确算出谁该被跳过支持dry_run模式只做计划不落地方便预览。八、上游视角to_scripts 如何切分出批次脚本的原料批次从哪里来答案在 src/graph/ops.rs 的to_scripts函数从提交图根节点开始用descendants()游标做广度优先遍历遇到受保护提交如 master 上的提交时把之前的分支链切成一个独立批次gather_script递归收集每个提交的动作pick、fixup、reword、建分支组装成Batch。命令行入口如git stack --rebase见 src/bin/git-stack/sync.rs正是调用to_scripts得到批次列表再交给Script::from流水线完成排序与标记。整条链路提交图 → 批次 → 依赖图 → 拓扑排序 → 可执行 rebase 脚本。小结一张表看懂全流程 ✅阶段关键函数作用切分批次to_scriptssrc/graph/ops.rs按分支链切出 Batch 序列构建依赖gen_graphsrc/rewrite/mod.rs批次间依赖 → DAG确定顺序sort_batchestoposort拓扑排序父分支优先补全引用infer_marks自动生成 label/mark执行Executor::run逐批执行失败跳过依赖项拓扑排序看似只是一个图算法却是 git-stack 能安全重写整条分支栈的基石它把分支依赖这种复杂关系转化成了确定、可预览、失败可回退的执行顺序。如果你想继续阅读可以从 docs/design.md 了解堆叠分支的设计目标再回到 src/graph/mod.rs 看提交图本身是如何构建的。【免费下载链接】git-stackStacked branch management for Git项目地址: https://gitcode.com/gh_mirrors/gi/git-stack创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考