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

EN

重新编辑：

为阐明我对确定相同职能的建议，可建议以下流程：

第1级:删除不属于字符串文字的任何空格；在每个{、;和}之后插入换行符并进行比较。如果相同，则功能相同，如果不相同的话：

第2级:将不依赖于在同一作用域中定义的其他变量的状态的所有变量声明和赋值移到它们在其中声明的作用域的开始(或者如果不想真正解析JS；大括号的开始)；并按行长对它们进行排序；将所有变量名称视为4个字符长，并在绑定长度的情况下返回字母顺序忽略变量名。按字母顺序重新排序所有集合，并重命名所有变量vSNN，其中v是文字，S是嵌套大括号的数目，NN是遇到变量的顺序。

比较；如果相同，则功能相同，如果不相同：

第3级:用"sNN"替换所有字符串文字，其中"和s是文字，NN是遇到字符串的顺序。比较；如果相同，则功能相同，如果不相同：

第4级:通过按照字母顺序使用具有最高优先级的函数的名称(在下面的示例中，对p_strlen()的任何调用都将被c_strlen()替换)来规范已知相同的函数的名称。如有必要，按1级重复重排序.比较；如果相同，则函数是相同的(如果不是)；函数几乎肯定是不相同的。

原始答案：

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

正如你所发现的，这两者之间的区别是至关重要的：

两个函数是完全相同的，如果遵循某种方式的规范化，(删除非文字空格，将变量重命名和重新排序为规范化顺序，用占位符…替换字符串文本)它们相当于字面上的平等。

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

虽然这些函数肯定不是相同的，但它们是相同的:对于任何给定(有效)输入值，它们都会给出相同的值。

我的观点是：

确定两个函数是否相同(您似乎想要实现的功能)是一个(适度的)琐碎问题，正如您所描述的。

确定两个函数是否真的是相同的(您可能实际上想要实现的功能)并不简单；实际上，这是非常困难的，可能与停止问题有关，而不是通过静态分析可以完成的事情。

编辑:当然，相同的函数也是相同的，但是对于完整的分析，是非常具体的，也很少有用。

你对第一级的做法似乎是合理的。

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

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

请参阅我公司的(语义设计) 智能差分器工具。这一系列工具根据编译级详细语法来解析所关注的语言(在您的例子中是JavaScript)，构建AST，然后比较这些AST(实际上忽略了空格和注释)。文字值是标准化的，所以它们如何“拼写”并不重要；10E17的归一化值与1E18相同。

如果这两棵树是一样的，它会告诉你“没有区别”。如果它们因标识符的一致重命名而不同，则该工具将告诉您一致性重命名及其发生的块。其他差异报告为语言元素(标识符、语句、块、类、.)插入、删除、复制或移动。我们的目标是报告一小部分可以合理解释差异的三角洲。您可以在网站上看到许多语言的示例。

在实践中，您不能超越这一点；要确定两个函数是否计算相同的答案，原则上您必须解决停止问题。您可能能够检测到两个语言元素(作为交换列表中的元素)可以在没有效果的情况下被交换；我们正在进行这方面的工作。您可能可以应用规范化重写来规范某些表单(例如，将所有多个声明映射到一系列词汇排序的单个声明中)。您可能可以将源代码转换为其等效的数据流集，并进行图同构匹配(80年代麻省理工学院的程序员学徒曾提议这样做，但我认为他们还没有做到这一点)。

所有的工作都比你想象的要多。