差异分析

Difftastic将diff计算视作为有向无环图上的寻路问题。

图表示

图中的一个顶点代表两个语法树中的一个位置。

开始顶点的两个位置都指向两个树的第一个语法节点。结束顶点的两个位置都正好在两棵语法树的最后一个节点之后。

以A和X A比较为例：

START
+---------------------+
| Left: A  Right: X A |
|       ^         ^   |
+---------------------+

END
+---------------------+
| Left: A  Right: X A |
|        ^           ^|
+---------------------+

从起始顶点开始，我们有两个选择：

• 我们可以将左边的第一个语法节点标记为注意项，并推进到左边的下一个语法节点（即上面的顶点1）。
• 我们可以将右边的第一个语法节点标记为注意项，并推进到右边的下一个语法节点上（即上面的顶点2）。

            START
            +---------------------+
            | Left: A  Right: X A |
            |       ^         ^   |
            +---------------------+
                   /       \
     Novel atom L /         \ Novel atom R
1                v       2   v
+---------------------+  +---------------------+
| Left: A  Right: X A |  | Left: A  Right: X A |
|        ^        ^   |  |       ^           ^ |
+---------------------+  +---------------------+

选择"新原子R"到顶点2将是最佳选择。从顶点2，我们可以看到有三条路线通往终点。

            2
            +---------------------+
            | Left: A  Right: X A |
            |       ^           ^ |
            +---------------------+
                   /    |   \
     Novel atom L /     |    \ Novel atom R
                 v      |     v
+---------------------+ | +---------------------+
| Left: A  Right: X A | | | Left: A  Right: X A |
|        ^          ^ | | |       ^            ^|
+---------------------+ | +---------------------+
  |                     |                    |
  | Novel atom R        | Nodes match        | Novel atom L
  |                     |                    |
  |         END         v                    |
  |         +---------------------+          |
  +-------->| Left: A  Right: X A |<---------+
            |        ^           ^|
            +---------------------+

比较路线

我们给每条边分配一个成本。将一个语法节点标记为新奇，比找到一个匹配的语法节点更糟糕，因此"新奇原子"边的成本比"语法节点匹配"边更高。

最佳路线是指从起始顶点到终端顶点成本最低的路线。

寻找最佳路线

Difftastic使用Dijkstra算法来寻找最佳（或称最低成本）的路线。

这种算法的一大优势是，我们不需要事先构建图。相对于语法节点的数量，构建整个图需要指数级的内存。相反顶点的邻居是在探索图的过程中构建的。

网上有很多解释Dijkstra的算法，但我特别推荐Red Blod Games的图搜索部分。