静态解析：判断两个Javascript函数是否相同

Question

我正在寻找一种方法，使用两个JavaScript函数的静态分析来判断它们是否相同。让我定义“相同”的多个定义。

等级1：除了可能的不同空白（例如， TABS，CR，LF和SPACES。

2级函数可能有不同的空白，如1级，但也可能有不同的变量名称。

3级 ???

---

对于一个水平，我想我可以只含有两个JS函数定义每个字符串中删除所有（非文本，这可能是艰难的）空白，然后比较字符串。

对于二级，我想我需要使用类似SpiderMonkey's parser的东西来生成两个解析树，然后编写一个比较器来遍历树并允许变量具有不同的名称。

---

[编辑] Williham，使得下面好点。我的意思是相同的。现在，我正在寻找一些实用策略，特别是关于使用分析树的方面。

Answer 1

重新编辑：

要在我的建议阐述用于确定相同的功能，下面的流可被提示：

等级1：删除任何空白不是一个字符串的一部分;在每个{,;和}之后插入换行符并进行比较。如果相等;功能是相同的，如果不是：

级别2：移动所有变量声明和赋值，这些变量声明和赋值不依赖于在同一范围内定义的其他变量的状态到它们声明的范围的开始处（或if不想实际解析JS;大括号的开始）;并按行长排序;将所有变量名称视为长度为4个字符，并且在长度相同时忽略变量名称。按字母顺序重新排列所有集合，并重命名所有变量vSNN，其中v是文字，S是嵌套花括号的数量，NN是变量遇到的顺序。

比较;如果相等，则各功能是相同的，如果不是：

级别3：与"sNN"，其中"和s是文字全部替换字符串文字，和NN是在其中遇到串的顺序。比较;如果不相等，则功能相同：

级别4：根据字母顺序使用具有最高优先级的函数的名称标准化已知的任何函数的名称（在下面的示例中，到p_strlen()任何呼叫将与c_strlen()代替重复重新排序按如有必要1水平比较;如果相等，则各功能是相同的，如果不是，该功能几乎肯定是不相同

---

。原始回答：

我想你会发现你的意思是“相同”，而不是“相同”。

的区别，因为你会发现，是至关重要的：

两个功能相同如果按照规范化的某种方式，（除去非字面空格，重命名和重新排序变量标准化秩序，用占位符替换字符串文字，...）他们比较字面上相等。

两个函数是相同如果在任何给定的输入值被调用时它们会给出相同的返回值。在一般情况下，考虑一种编程语言，它计算了零终止字符串（如果您愿意的话，可以使用混合Pascal/C字符串）。函数p_strlen(str)可能会查看字符串的字符数并返回该字符。函数c_strlen(str)可能会计算字符串中的字符数并返回该字符数。

虽然这些函数肯定不会相同，但它们将是相同的：对于任何给定的（有效）输入值，它们将给出相同的值。

---

我的观点是：

确定阉两个功能是相同的（你似乎想达到什么）是（中等）很重要的问题，做你描述。

确定这两个函数是否真的是一样的（你可能想要实现的）是不平凡的;事实上，它很难完成，可能与Halting Problem有关，而不是静态分析可以做到的。

---

编辑：当然，这是相同的功能也相同;但以完全分析的高度特异且很少有用的方式。

Answer 2

您的级别1的方法似乎是合理的。

对于2级，如何对每个函数做一些基本的变量替换，然后确定是否达到1级？从开始处开始，对于每个遇到的变量声明，将它们重命名为var1, var2, ... varX。

如果函数声明变量的顺序不同，则这没有帮助... var i和var j可能在这两个函数中都以相同的方式使用，但是以不同的顺序声明。然后你可能会像你提到的那样对树分析进行比较。

Answer 3

查看我公司的（语义设计）Smart Differencer工具。这个工具家族根据感兴趣的语言（在你的情况下，JavaScript）的编译器级别细节语法解析源代码，构建AST，然后比较AST（它们有效地忽略了空白和注释）。字面值被标准化，所以它们如何“拼写”并不重要; 10E17具有与1E18相同的标准化值。

如果两棵树相同，它会告诉你“没有区别”。如果它们通过标识符的一致重命名而不同，则该工具将告诉您consisten重命名以及它发生的块。其他差异以语言元素（标识符，语句，块，类，...）插入，删除，复制或移动来报告。目标是报告可以解释差异的一小组三角形。您可以在网站上查看许多语言的示例。

你不能在实践中超出这个范围;以确定两个函数是否计算相同的答案，原则上你必须解决暂停问题。您可能能够检测出作为交换列表元素的两种语言元素可以在没有影响的情况下进行减法;我们正在研究这个。您可能能够应用规范化重写来规范化某些形式（例如，将所有多个声明映射到词法排序的单个声明序列中）。您可能能够将源代码转换为其等价的数据流集，并进行图同构匹配（麻省理工学院的程序员学徒提出要做到这一点，但我不认为他们曾经到过那里）。

所有有更多的工作要做，比你想象的要多。