克隆检测算法

Question

我将编写一个算法来检测源代码中的克隆。例如，如果存在以下块：

for(int i = o; i <5; i++){
doSomething(abc);
}

如果这个代码块在源代码的其他地方被重复使用，它将被检测为克隆。目前我使用的方法是为每行/每个块创建哈希值，并将其与同一源代码中其他行/块的哈希值进行比较，以查看是否存在匹配项。

现在，如果上面的相同块在某个地方重复出现，只有doSomething参数不同，它将不会被检测为克隆，即使它看起来非常像克隆。我的算法只能检测精确匹配，无法检测仅参数不同的匹配块。

有没有人能提出解决这个问题的方法？谢谢！

- LadyMadonna234

---

... 嗯，只是好奇，但是...你为什么想这样做呢？ - flight

这个链接可能会对你有所帮助：http://stackoverflow.com/questions/5294447/how-can-i-find-source-code-copying 尽管是针对 C++ 的，但可以用于各种语言的软件已经提供。 - Brad Christie

@quasiverse：我想是为了重构代码吧？ - Brad Christie

通过消除代码重复来优化源代码。可能存在这样的工具，但我想创建自己的算法。 - LadyMadonna234

Answer 1

这里有一种超级简单的方法，可能会过度擦除信息（即可能产生太多误报）：用某个固定名称替换每个不是关键字的标识符。因此，您将得到以下结果：

for (int DUMMY = DUMMY; DUMMY<5; DUMMY++) {
  DUMMY(DUMMY);
}

（假设您在for循环的初始化部分中实际意思是o而不是0。）如果您使用此方法时得到大量错误结果，您可以通过后处理它们来查看DUMMY的比例实际上对应于匹配的两个部分之间相同的标识符，或者至少对应于两者之间一致的标识符。要取得更好的效果，您可能需要在某种程度上解析代码。这将需要更多的工作。

- Gareth McCaughan

---

使用此代码 + 去除空格和换行符，您就可以开始查找重复项了。 - stefan

你可能会将循环变量放在另一个集合中（即DUMMY1），因为它是在此块内初始化的。 - Philipp T.

糟糕，我的意思是0。我认为这是一个好主意……但我担心它会错误地标记克隆代码，例如如果一堆代码行没有任何关键字，它们可能被检测为克隆代码。 - LadyMadonna234

只有当结构相同时才能匹配——除了标识符名称不同之外，令牌的顺序也必须相同。例如，foo(a,b,c);与foo(a,b);是不同的。 - Gareth McCaughan

@Philipp T.，我不确定你是否能够真正让它工作。例如，考虑您想捕获相同的代码块，即使它有时出现在for循环内部，有时则不是。 - Gareth McCaughan

你可能会将定义抽象化，以得出（块内定义的变量、块外定义的变量、块代码）的规范定义。 - Philipp T.

Answer 2

如果你要做其他事情，那么你至少需要解析代码。例如，你可以检测方法，然后在哈希表中忽略方法参数。无论如何，我认为总是需要让程序比“纯文本块”更好地理解代码，这可能会变得非常复杂。

- Roy T.