企业官网建设流程全解析

• 开发工具
• Lint
• 静态分析
• 硬件开发

Verible 对外部依赖采取“Bazel 依赖解析优先、仓库内 vendored 拷贝兜底”的两级管理策略，而external_libs/目录正是该策略的落地位置。本文基于 external_libs/README.md 展开，结合 external_libs/editscript.h、external_libs/editscript_test.cc 及其在verible/common/strings/diff.h、formatter 等处的实际调用链，讲清 Verible 如何组织外部库、editscript 这个模板化序列 diff 算法库的内部原理，以及它在 Verible 增量格式化、修复补丁输出等场景中的具体用途。读完本文，你将能够理解如何在 Bazel 工作区中定位并使用该库，并能读懂其 Myers O(ND) 二分递归 diff 的实现细节。

一、Verible 的外部依赖管理策略：Bazel 优先，vendored 拷贝兜底

external_libs/README.md 的核心内容只有两点：

1. 首选方式：外部依赖应通过 Bazel 工作区（原文明确提到 WORKSPACE 文件机制）来引入，这是 Bazel 工程的标准做法；
2. 兜底方式：当某些场景下该工作流不被良好支持时，external_libs/目录内直接存放来自外部来源的库的拷贝（vendored copy）。

也就是说，external_libs/不是“临时堆代码的地方”，而是一个有明确准入标准的目录：只有当某个外部库无法（或不便）通过 Bazel 的依赖解析机制引入时，才允许在这里保留一份受仓库自身版本控制、并附带许可证声明的副本。

当前仓库的实际依赖形态

需要说明的是，当前仓库快照的依赖声明已从早期的 WORKSPACE 文件演进为Bzlmod（Bazel 模块化依赖管理）。根目录下的 MODULE.bazel 声明了模块名verible（版本head），并以bazel_dep规则引入 abseil-cpp、nlohmann_json、protobuf、re2、rules_bison、rules_flex、googletest 等外部依赖。这印证了 README 所述“首选 Bazel 机制”的策略——绝大多数字符串、JSON、正则、词法/语法生成工具链依赖都走模块解析。

那么为什么仍需要一个 vendored 目录？答案就在目录里唯一的库：editscript。它是一个纯头文件（header-only）、模板化的序列差异（sequence diff）算法，源自 Google 的 diff-match-patch 项目（见文件头部 editscript.h 的版权与出处注释，Apache 2.0 许可，特别注明GetBisectSplitPoints部分派生自 diff_match_patch.cpp）。这类小型算法库单独发布一个 Bazel 模块的收益很低，直接放入仓库内管理反而更简洁，因此成为 README 所说“该工作流不被良好支持”情形的典型代表。

BUILD 规则：如何构建和测试

external_libs/BUILD 完整定义了该包的构建目标：

# This package contains externally owned libraries. # # editscript - is a template-generic sequence diff algorithm based on # diff-match-patch. load("@rules_cc//cc:defs.bzl", "cc_library", "cc_test") package( default_applicable_licenses = ["//:license"], # 复用顶层 Apache-2.0 许可证声明 default_visibility = ["//:__subpackages__"], # 只对本仓库各包可见 features = ["layering_check"], ) cc_library( name = "editscript", hdrs = ["editscript.h"], # header-only：只有头文件，无实现源文件 ) cc_test( name = "editscript_test", srcs = ["editscript_test.cc"], deps = [ ":editscript", "@abseil-cpp//absl/strings", "@googletest//:gtest", "@googletest//:gtest_main", ], )

几个值得注意的工程细节：

• cc_library只列了hdrs，没有任何srcs，这是 header-only 库在 Bazel 中的标准写法——消费者（如 verible/common/strings/BUILD 中的//external_libs:editscript依赖）只需包含头文件即可编译；
• default_visibility限定为//:__subpackages__，即外部库只能被本仓库内部包使用，不会泄露到仓库外；
• 测试目标依赖 abseil 的str_join与 googletest，与 MODULE.bazel 中声明的外部模块一一对应。

在本地验证时，可以运行：

bazel build //external_libs:editscript bazel test //external_libs:editscript_test

二、editscript 库 API 剖析：Edit 数据结构与 GetTokenDiffs

editscript 的整个公开 API 非常精简：一个Operation枚举、一个Edit结构体、一个Edits类型别名，以及唯一的入口函数模板GetTokenDiffs。文件注释给出了它的定位（editscript.h#L24-L26）：

返回将一组 token 容器变换为另一组所需的最小编辑操作数（copy、delete、insert），要求 token 流支持随机访问迭代器（cf.diff -d -e）。

2.1 核心数据结构

enum class Operation { EQUALS, DELETE, INSERT }; struct Edit { Operation operation; // One of: EQUALS, DELETE, or INSERT. int64_t start; // Start offset into tokens1 (tokens2 for INSERT). int64_t end; // End offset into tokens1 (tokens2 for INSERT). }; using Edits = std::vector<Edit>;

（摘自 editscript.h#L40-L62）

这里有一条极易混淆但至关重要的索引约定（头文件注释 L43-L48 明确强调）：

• EQUALS和DELETE的[start, end)半开区间指向 tokens1（源序列）；
• INSERT的[start, end)指向 tokens2（目标序列）；
• 把所有EQUALS与DELETE区间的 token 按序拼接，恰好还原 tokens1；把所有EQUALS与INSERT拼接，恰好还原 tokens2。

Edit实现了operator==与operator<（按 operation、start、end 三元组比较），这使得Edits可以直接参与EXPECT_EQ断言与有序容器——这一点在测试代码中得到大量利用。

2.2 入口函数：GetTokenDiffs

template <typename TokenIter> Edits GetTokenDiffs(TokenIter tokens1_begin, TokenIter tokens1_end, TokenIter tokens2_begin, TokenIter tokens2_end);

（声明见 editscript.h#L80-L82）

头文件中的示例直观展示了返回值语义：对 tokens1 ="Hello world."与 tokens2 ="Goodbye world."，结果是：

{Edit(Operation::DELETE, 0, 5), // token1[0,5) == "Hello" Edit(Operation::INSERT, 0, 7), // token2[0,7) == "Goodbye" Edit(Operation::EQUALS, 5, 12)} // token1[5, 12) == " world."

性质保证是“每一个 token 恰好属于一个 edit”，即编辑序列是对两个序列的无重叠、全覆盖切分。模板参数TokenIter要求随机访问迭代器（实现中需要begin + offset、std::mismatch、std::search等操作），因此它对char数组、std::vector<std::string>、std::vector<std::string_view>等各种 token 类型通用——这正是 README 所说“template-generic”的含义。

三、算法内部实现：剥离前后缀 → 快速路径 → Myers 二分

实现全部集中在diff_impl命名空间的Diff模板类中（editscript.h#L179-L479），公开入口GetTokenDiffs只是薄薄一层封装（L482-L490），它调用Generate(0, n1, 0, n2, &edits)并利用具名返回值优化（NRVO）避免拷贝。

3.1 Generate：先剥掉公共前缀与后缀

Generate（L207-L255）是递归驱动函数，策略在源码注释中写得很清楚：

1. 快速判定相等：若两段长度相同且内容全等，直接AppendEdit(EQUALS, ...)返回；
2. 剥离公共前缀：CommonAffix（L160-L173）用std::mismatch求公共前缀长度；
3. 剥离公共后缀：通过std::reverse_iterator反转迭代器，复用同一个CommonAffix求公共后缀长度；
4. 对中间块递归调用Compute；
5. 最后把前缀EQUALS通过InsertEditAt插回、后缀EQUALS通过AppendEdit追加。

AppendEdit与InsertEditAt（L97-L138）还实现了编辑合并：如果新 edit 与前一个（或后一个）edit 操作相同且区间首尾相接，就把它并入相邻 edit，保证输出序列里不出现可合并的碎片，这也是输出“最小编辑操作数”观感上紧凑的原因。

3.2 Compute：四条廉价快速路径

Compute（L266-L327）在动用昂贵的通用算法前，先尝试多个 O(n) 级的捷径：

• 一边为空：tokens1 空则整段INSERT，tokens2 空则整段DELETE；
• 子串命中：若 length1 > length2，用std::search在 tokens1 中查找 tokens2 整段——若命中，说明 tokens2 是 tokens1 的真子串，直接输出“DELETE 前段 + EQUALS 命中段 + DELETE 后段”（对称地处理 length2 > length1 的“插入包围”情形）；
• 单 token 替换：一侧长度为 1 且未命中相等时，输出 DELETE + INSERT。

任何一条路径都不适用时，进入Bisect。

3.3 GetBisectSplitPoints：Myers O(ND) 中间蛇

GetBisectSplitPoints（L339-L450）是算法核心，注释直接引用了文献依据：“See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations”。它维护一个交错布局（interleaved）的w数组同时推进正向路径与反向路径：

• delta = length1 - length2，总 token 数为奇数时由正向路径负责检测碰撞（front = (delta % 2 != 0)）；
• 每一轮 d 内，正向循环沿 k1 对角线前进，在相等 token 上贪婪“滑行”（L381-L385 的 while 循环），反向循环则从序列末尾镜像比较（L418-L423）；
• 一旦两条路径在图上重叠（x1 >= x2），即找到“middle snake”（中间蛇），返回分割点(x1, y1)；
• 若完全走不到重叠，返回{-1, -1}，表示两段毫无公共性。

Bisect（L460-L474）拿到分割点后：有公共性就对左右两半分别递归Generate；没有公共性则退化为最坏情形的DELETE 全部 + INSERT 全部。这一“剥离前后缀 + 中间蛇二分”的组合正是 diff-match-patch 家族算法的标志性结构，也让该实现既正确又对“差异集中、公共部分大”的 token 序列（例如格式化前后几乎相同的源码）高效。

四、测试用例：行为契约的可验证证据

external_libs/editscript_test.cc 用 GoogleTest 覆盖了算法的主要行为契约，每组断言都给出了期望的完整Edits序列，是理解输出格式的最佳参照：

以StrictSubsequence（L243-L258）为例：tokens1 ={"the","fox","jumped","over","the","dog","."}，tokens2 ={"fox","jumped","over"}，期望输出{DELETE,0,1}, {EQUALS,1,4}, {DELETE,4,7}——恰好对应 3.2 节“tokens2 是 tokens1 真子串”那条快速路径。测试文件开头还自定义了Operation/Edit/Edits的operator<<（L33-L59），使失败时的断言信息可读，这一批打印函数后来被 verible/common/strings/diff_test.cc 直接复用（其注释写明 “Print functions copied from external_libs/editscript_test.cc”）。

五、editscript 在 Verible 中的实际应用

editscript 的价值最终体现在消费者代码里。整个仓库中依赖//external_libs:editscript的主要是 verible/common/strings/BUILD（第 57、68 行两处），即diff库与其测试。

5.1 LineDiffs：把 token diff 落到“行”这个粒度

verible/common/strings/diff.h 定义了LineDiffs结构（L35-L46），它持有before_text/after_text两个string_view、按行切分后的before_lines/after_lines，以及一份diff::Edits行编辑序列。构造函数实现（verible/common/strings/diff.cc#L46-L52）正是把 editscript 用在行向量上：

LineDiffs::LineDiffs(std::string_view before, std::string_view after) : before_text(before), after_text(after), before_lines(SplitLinesKeepLineTerminator(before_text)), after_lines(SplitLinesKeepLineTerminator(after_text)), edits(diff::GetTokenDiffs(before_lines.begin(), before_lines.end(), after_lines.begin(), after_lines.end())) {}

在此之上，diff.h 还提供了三个工具函数：

• DiffEditsToAddedLineNumbers（L53）：把diff::Edits翻译为“新增行号”的区间集合，注意注释明确说明diff::Edits是 0-based 而返回值是 1-based 行号；
• DiffEditsToPatchHunks（L78-L79）：按common_context行数把整段编辑序列切分为补丁 hunk；其注释还坦承“这个函数可以上游回馈给 editscript 库，因为它与被 diff 的类型无关”（L76-L77）；
• LineDiffsToUnifiedDiff（L81-L84）：输出标准 unified diff 文本。

PrintEdit的实现（diff.cc#L63-L77）也印证了前文说的索引约定：INSERT 用after_lines定位，DELETE/EQUALS 用before_lines定位，行首标记分别为+、-、空格。

5.2 formatter：用 diff 结果驱动增量重排

editscript 最有实战味道的消费方是 Verible 格式化器。verible/verilog/formatting/formatter.cc#L169-L188 的ReformatVerilogIncrementally：

// Differences from the first formatting. const verible::LineDiffs formatting_diffs(original_text, formatted_text); // Added lines will be re-applied to incremental re-formatting. LineNumberSet formatted_lines( verible::DiffEditsToAddedLineNumbers(formatting_diffs.edits));

逻辑是：先对原文与首轮格式化结果做行级 diff，由 editscript 产生的编辑序列提取出“被格式化处理过的行号集合”，再据此对第二轮重排施加行范围约束，避免无谓地重排整个文件。verible/common/formatting/verification.cc#L32 则用同样手段对比“格式化结果”与“再格式化结果”，验证格式化是否收敛（幂等）。可以说，editscript 是 Verible formatter 收敛性验证与增量格式化机制的底层组件。

5.3 lint 修复补丁：unified diff 的输出

verible/common/analysis/violation-handler.cc 在输出 lint 诊断的修复建议与写补丁文件时（第 40-42 行、100-101 行），同样通过LineDiffs+LineDiffsToUnifiedDiff生成 1 行上下文的 unified diff——这些 diff 文本最终呈现给用户或写入补丁流，其底层编辑序列仍来自 editscript。

5.4 一个易混淆点：ReplacementEdit 不是 editscript 的 Edit

verible/common/analysis/lint-rule-status.h#L42-L43 的注释专门澄清了这一点：ReplacementEdit与 editscript 的Edit不同，它直接保存替换字符串，因此不需要“after”文本即可使用。阅读 lint autofix 相关代码时注意区分这两个结构，可避免对索引语义产生误解。

六、小结：如何在仓库中定位这套机制

• 策略文档：external_libs/README.md——Bazel 依赖优先，不支持时才 vendored；
• 库本体：external_libs/editscript.h（header-only，Apache 2.0，派生自 diff-match-patch）；
• 构建定义：external_libs/BUILD，bazel build //external_libs:editscript可编译，bazel test //external_libs:editscript_test可验证；
• 依赖声明现状：根目录 MODULE.bazel（Bzlmod），editscript 是少数不走模块解析、直接入树的库；
• 主要消费方：verible/common/strings/diff.h / verible/common/strings/diff.cc（LineDiffs、patch hunk、unified diff），下游是 verible/verilog/formatting/formatter.cc（增量重排）、verible/common/formatting/verification.cc（收敛验证）与 verible/common/analysis/violation-handler.cc（修复补丁输出）。

这套“文档说明准入策略 + header-only 算法库 + 完整测试契约 + 清晰的下游消费链”的组合，是 Verible 管理外部代码的一个小而完整的样本：外部代码进入仓库的门槛、许可证归属、可见性范围（//:__subpackages__）和行为验证（editscript_test）在仓库内都有据可查。

• 开发工具
• Lint
• 静态分析
• 硬件开发