ydiff 是我的一个开源项目，用以探索一种全新的程序比较以及版本控制系统。

也许我根本不应该给它起名叫“ydiff”，让人感觉它只不过是对 diff 的微小改进。然而，ydiff 跟 diff 是有本质区别的。它们的区别在于，diff 只是对程序进行基于“文本”的对比，它根本不对程序进行 parse。而 ydiff 含有完整的针对程序语言的 parser，在得到了 AST 之后，才对 AST 进行“结构化的比较”。

这种结构化的程序比较，不但可以避免文件里的“空白字符”引起的肤浅区别，而且可以根据程序的结构，进行更加有意义的对比。比如，ydiff 不会认为字符串 "1000" 和数字 1000 的区别只是多了一对引号。ydiff 在比较函数的时候，首先寻找名字相同的函数，而不只是对相同位置的函数进行无谓的对比。

ydiff 含有 C++, JavaScript 和 Lisp 的 parser。这些 parser，包括用于支持这些 parser 的库代码，都是我自己完成的。ydiff 不含有任何第三方代码。ydiff 的 parser 技术不依赖于任何第三方工具（比如 ANTLR 或者 YACC）。

界面

跟普通 diff 程序的输出不一样，ydiff 生成美观的含有 JavaScript 的 HTML 文件，可以直接使用浏览器浏览，并且可以嵌入其它网页，比如像下面这样：

(单独浏览)

上面的界面有如下特点：

  1. 红色表示“删除”，绿色表示“插入”，白色表示“移动”或者没有变化
  2. 左右窗口同步滚动
  3. 点击白色方框，就可以依据框里的变量进行对齐
  4. 点击之后，左右窗口根据对齐的变量重新“耦合”，同步滚动

技术

ydiff 里面含有一些比较独特的技术。

强大而简单的 parser combinator library

一般编译器的 parser 都使用像 YACC 和 ANTLR 一样的 parser generator。这种方法虽然可行，但是它有一个很大的问题，就是你需要使用另外一种语言和另外一个工具，这样就多了一层“语义”。当你的 parser 出了问题的时候，你不能使用已有的编程工具进行调试，而只能依靠这种 parser 工具所提供的信息。这就是为什么人们都觉得 parser 很难写。有一家叫 EDG 的公司，专门销售 C++ 的 parser 代码。你可以由此看出 parser 的技术是多么的复杂和混乱。

由于这个原因，很多人的 parser 都是自己手写的。可是手写 parser 相当的费事，而且不模块化。所以函数式语言的社区就出现了 Parsec 这样的“parser combinator library”。它的原理是，每一个 parser 都是一个函数，它接受一个字符串，输出一种特定的 AST 结构。比如你可以写出一个很简单的 parser，它只能从字符串里提取一个变量，或者一个数字。由于函数式语言可以把函数作为数据，这种小的 parser 可以被一些叫做 parser combinator 的“高阶函数”作为输入，然后把它们“组合”在一起，形成更大的 parser。当所有这些 parser 组合在一起，它们就可以拥有分析整个程序文本的威力，就像“组合金刚大力神”一样。 

devastator_tf2.jpg

我的 parser 库就是受到了 Parsec 的启发。然而我的库在某种程度上比 parsec 还好用。它不但更加简单灵活，而且能够检测并且报告“左递归”的位置。这是 Parsec 没有的功能。另外，我的 parser 库里面含有很方便的宏，使得写 parser 就像写 BNF 范式一样简单，但却又不需要使用像 YACC 一样的麻烦的工具。

比如，C++ 函数的 parser 是这样定义的：

(::= $function-definition 'function
     (@or (@... (@? $modifiers) $type
                (@= 'name $identifier ) $formal-parameter-list)

          (@... (@= 'name $identifier ) $formal-parameter-list))
     (@? $initializer)
     $function-body)

在创造了这个库之后，我在一天之内写出了一个 JavaScript 的 parser。两天之后，在这个 JS parser 基础上，又写出了一个 C++ 的 parser。两天之内写出 C++ 的 parser 对于很多人来说都是不可思议的事情，但我没有感觉这有什么难度。大部分的人只不过高估了问题的难度，不然就是把问题复杂化了。

最后的 C++ parser 只有 600 行代码（不包括空行），而 JS 的 parser 只有 470 行代码。最令人惊奇的事情是，Lisp (S-expression) 的 parser 只有 11 行代码，以至于我可以把它完整的贴在这里：

(:: $open  
     (@or (@~ "(") (@~ "[")))  
(:: $close  
     (@or (@~ ")") (@~ "]")))  
(:: $non-parens  
     (@and (@! $open) (@! $close)))  
(::= $parens 'sexp  
     (@seq $open (@* $sexp) $close))  
(:: $sexp  
    (@+ (@or $parens $non-parens)))  
(:: $program $sexp)

精确的探测“代码移动”

不管你在任何位置剪切了一段代码到另外一个地方，ydiff 都能准确的探测到这个动作。比如在上面的代码里面，你也许发现了函数 unify 的主体被移动到了另一个叫做 unify-good 的函数里面。ydiff 能够精确地显示出这个事实： 

unify-ydiff.png

这种对于代码移动的检测，可以让人找到很长时间段内对代码的一切修改。为此我做了一个实验，我用 ydiff 对比了 V8 编译器的一个文件相距两年的变化，得到了直观可读的结果。如果你用普通的 diff 来对比它们，恐怕不会看出很多有用的信息，因为这个文件里的有些函数被切分成了好几个小的“帮助函数”。ydiff 能够准确的找到这些被切分的代码所在的位置。 比如我轻而易举的看到，Shell::Initialize 这个函数被切分成了如下一些函数：

Shell::Initialize
Shell::CreateGlobalTemplate
Shell::RenewEvaluationContext
Shell::InstallUtilityScript

你可以在以下的 ydiff 输出中直观的看到这个事实（搜索 Shell::Initialize 然后就可以点击每一行，看它们到什么地方去了）：

(单独浏览)

这里有一个可能的改进之处，就是让这种代码移动的现象被更加直接的显示出来，而不需要用户挨个的点击这些代码。

未来

ydiff 只是一个开端，我希望由它的启发，形成出一种全新的“版本控制系统”。这种系统将从本质上超越现有的基于文本的版本控制系统。关于这系统的细节，我已经在一篇英文博文中有基本的描述。

源代码

ydiff 是完全开源的项目，它可以从我的 GitHub 免费获得。

https://github.com/yinwang0/ydiff