Алгоритм обнаружения клонов

Question

Я пишу алгоритм, который обнаруживает клонов в исходном коде.Например, если есть такой блок, как:

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

... и если этот блок повторяется где-то еще в исходном коде, он будет обнаружен как клон.Метод, который я использую в данный момент, заключается в создании хэшей для строк / блоков и сравнении их с хешами других строк / блоков в том же источнике, чтобы увидеть, есть ли совпадения.

Теперь, если бы тот же блок, что и выше, нужно было где-то повторить только с аргументом doSomething иначе, он не был бы обнаружен как клон, даже если он выглядел бы очень похоже на клон для вас и меня.Мой алгоритм обнаруживает точные совпадения, но не обнаруживает совпадающие блоки, где отличается только аргумент.

Может кто-нибудь предложить какие-либо способы обойти эту проблему?Спасибо!

Answer 1

Вот очень простой способ, который может зайти слишком далеко при удалении информации (т. Е. Может привести к слишком большому количеству ложных срабатываний): заменить каждый идентификатор, который не является ключевым словом, некоторым фиксированным именем.Таким образом, вы получите

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

(при условии, что вы действительно имели в виду o вместо 0 в части инициализации for -loop).

Если вы получитеС этим можно связать огромное количество ложных срабатываний, после чего вы можете обработать их, например, посмотрев, какая часть DUMMY действительно соответствует одному и тому же идентификатору в обеих половинах совпадения или, по крайней мере, идентификаторам, которые соответствуютдва.

Чтобы добиться большего успеха, вам, вероятно, потребуется до некоторой степени проанализировать код.Это было бы намного больше работы.

Answer 2

Ну, если вы собираетесь делать что-то еще, вам придется хотя бы немного разобрать код. Например, вы можете обнаружить методы, а затем игнорировать аргументы методов в вашем хэше. В любом случае, я думаю, что всегда верно, что ваша программа должна понимать код лучше, чем «просто текстовые блоки», и это может быть довольно сложно.