Graphtage：一种新的语义差异比较工具

Graphtage 是一个命令行实用程序及底层库，用于语义比较和合并树状结构，如 JSON、JSON5、XML、HTML、YAML 和 TOML 文件。其名称是“graph”和“graftage”（即园艺中将两棵树连接成一棵的实践）的组合词。继续阅读以了解：

• Graphtage 的不同之处和优势
• 我们开发它的原因
• 它的工作原理
• 将其用作库的指南
• 各种好处

Graphtage 让您快速轻松地查看两个文件之间的差异，但它不是像 diff 那样的标准面向行的比较工具。Graphtage 具有语义感知能力，使其能够映射跨无序结构（如 JSON 字典和 XML 元素标签）的差异。您甚至可以比较两种不同格式的文件！当与我们的 PolyFile 工具配对时，您可以对任意文件格式进行语义差异比较。

树状文件格式作为传输和存储数据的手段变得越来越常见。如果您曾经处理过复杂的 REST API、解析过模板生成的网页输出，或编写过配置文件（随后需要找出哪个具体更改使事情正常工作），您可能对当前开源语义差异工具的状态感到失望。

Graphtage 解决了这些问题。它今天就可使用。要安装该实用程序，请运行：

1

pip3 install graphtage

在此处获取源代码。

现有差异工具的不足

树中的有序节点（例如 JSON 列表）以及特别是映射（例如 JSON 字典）具有挑战性。大多数现有的差异算法和实用程序假设结构是有序的。以以下 JSON 为例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# original.json
{
    "foo": [1, 2, 3, 4],
    "bar": "testing"
}
# modified.json
{
    "foo": [2, 3, 4, 5],
    "zab": "testing",
    "woo": ["foobar"]
}

现有工具有效地规范化 JSON（例如，按键对字典元素排序并将列表格式化为每行一个项目），然后执行传统差异。我们不需要花哨的工具！以下是它们 effectively 所做的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

$ cat original.json | jq -M --sort-keys > original.canonical.json
$ cat modified.json | jq -M --sort-keys > modified.canonical.json
$ diff -u original.canonical.json modified.canonical.json
    {
    -  "bar": "testing",
       "foo": [
    -    1,
         2,
         3,
    -    4
    -  ]
    +    4,
    +    5
    +  ],
    +  "woo": [
    +    "foobar"
    +  ],
    +  "zab": "testing"
    }

该结果不是很有用，特别是当输入文件很大时。问题是更改字典键会破坏差异：由于“bar”被更改为“zab”，规范表示发生了变化，传统差异算法将它们视为单独的编辑（差异的第 2 行和第 15 行）。

相比之下，以下是 Graphtage 对同一对文件的输出：

为什么以前没有做到这一点？

一般来说，将一个图最优映射到另一个图不能在多项式时间内执行，因此对于任何有用大小的图来说都是不可行的（除非 P=NP）。即使对于像 DAG 这样的受限图类也是如此。然而，树和森林是可以在多项式时间内映射的特殊情况，并对可能的编辑类型施加合理的约束。Graphtage 利用了这一点。

它是如何知道的？

Graphtage 的差异算法在中间表示上操作，而不是在原始文件格式的数据结构上。这使 Graphtage 能够拥有适用于任何输入文件类型的通用比较算法。因此，要添加对新文件类型的支持，只需将其“提升”到中间表示即可。同样，只需一次实现对新编辑类型的支持，它将立即可用于所有支持的文件类型。使用中间表示还有一个额外的好处，即允许跨格式比较和格式转换：Graphtage 会很乐意将 JSON 文件与 YAML 文件进行差异比较，并以 TOML 语法格式化差异输出。

Graphtage 使用 Levenshtein 距离度量的“在线”“构造性”实现来匹配有序序列（如列表），类似于 Wagner–Fischer 算法。该算法从无界映射开始，并迭代改进它，直到边界收敛，此时发现最优编辑序列。

通过解决从源字典中的键/值对到目标字典中的键/值对的完全二分图上的最小权重匹配问题来匹配字典。

Graphtage 是一个命令行实用程序，但它也可以轻松用作库。可以直接从 Python 与 Graphtage 交互，并扩展它以支持新的文件格式和编辑类型。

Graphtage 的下一步

我们认为 Graphtage 非常巧妙。您还可以将 Graphtage 与我们的 PolyFile 工具结合使用，以对任意文件格式进行语义差异比较，即使它们本质上不是基于树的。尝试一下，并告诉我们您如何使用它。

我们还计划扩展 Graphtage 以处理抽象语法树，这将使您的源代码差异能够告诉您哪些变量被更改以及代码块是否被重新排序。如果您对新功能有类似巧妙的想法，请与我们分享！

注意：此工具部分由国防高级研究计划局（DARPA）在 SafeDocs 项目上资助开发。所表达的观点、意见和/或发现是作者的观点，不应解释为代表国防部或美国政府的官方观点或政策。

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容 各种好处 现有差异工具的不足？ 为什么以前没有做到这一点？ 它是如何知道的？ Graphtage 的下一步 最近帖子 Trail of Bits 的 Buttercup 在 AIxCC 挑战赛中获得第二名 Buttercup 现已开源！ AIxCC 决赛：记录 攻击者的提示注入工程：利用 GitHub Copilot 在 NVIDIA Triton 中发现内存损坏（作为新员工） © 2025 Trail of Bits。 使用 Hugo 和 Mainroad 主题生成。