Поиск похожих фрагментов кода с использованием поддеревьев

Question

Я читал эту статью под названием Обнаружение клонов с использованием абстрактных синтаксических деревьев , авторы Ira D. Baxter et al.Ниже приведен абзац из статьи, которую я воспроизвел:

В принципе, найти клоны поддеревьев легко: сравните каждое поддерево с любым другим поддеревом на равенство.На практике возникает несколько проблем: обнаружение почти отсутствующих клонов, субклоны и масштабирование....

При нахождении клонов, близких к пропущенным, хеширование на полных поддеревьях завершается неудачей именно потому, что хорошие функции хеширования включают в себя все элементы дерева и, таким образом, сортируют тресс с небольшими отличиями в разные сегменты.Мы решили эту проблему, выбрав искусственно плохую хеш-функцию .Эта функция должна быть охарактеризована таким образом, чтобы основные свойства, которые каждый хочет найти в клонах, близких к мисс, были сохранены.Обычно клоны создаются с помощью процедур копирования и вставки с небольшими изменениями.Эти модификации обычно генерируют небольшие изменения в форме дерева, связанного с скопированным фрагментом кода.Поэтому мы утверждаем, что этот вид клонов, близких к мисс, часто имеет только несколько разных небольших поддеревьев.Основываясь на этом наблюдении, хеш-функция, которая игнорирует маленькие поддеревья, является хорошим выбором. В представленном здесь эксперименте мы использовали хэш-функцию, которая игнорирует только имена идентификаторов (листья в дереве).Таким образом, наша функция хеширования помещает деревья, которые являются похожими по модулю идентификаторами, в одни и те же хэш-контейнеры для сравнения.

Я пытаюсь реализовать методы, описанные в этой статье, но застрял в попытке понять этоодин абзац (это, к сожалению, в начале статьи).Я понимаю, о чем говорится в этом абзаце, но авторы не упоминают, какую хеш-функцию выбрать или как на самом деле хешировать AST.Может кто-нибудь объяснить это простым примером с точки зрения реализации?

Answer 1

Оттенки, на которые должен ответить сам автор.Разве StackOverflow не велик: -?

Смысл хеш-функций в том, что вы выбираете, не имеет значения, если он равномерно распределяет входные значения по большому количеству сегментов.Вам нужна хеш-функция, которую можно применить ко всему дереву;обычная техника для этого состоит в том, чтобы сериализовать дерево любым возможным способом (скажем, путем посещения дерева по порядку), а затем применить хеш-функцию к потоку значений (узлам дерева), которые это производит.(Эта идея взята из литературы по компилятору об обнаружении общих подвыражений, которая послужила источником вдохновения для оригинального CloneDR).Если это неясно, вам нужно потратить больше энергии на понимание того, как хэш-функции применяются к сложным структурам данных.Википедия о хэшировании - хорошее место для начала;если этого недостаточно, вам нужно найти книгу по алгоритмам и изучить ее.

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

Конечно, в алгоритме обнаружения всего клона гораздо больше, чем просто сопоставление деревьев по модулю идентификаторов.Вам нужно беспокоиться о сопоставлении параметризованных последовательностей (что является важным моментом в статье), сообщать о результатах и, конечно, вам нужен высококачественный синтаксический анализатор языка для любого языка, который вам нужен, чтобы применить эток.

Вы можете увидеть результаты CloneDR для ряда различных языков.

Answer 2

Если вы знаете, что два AST являются «клонами» для вашего человеческого глаза, вы хотите убедиться, что они также имеют одинаковое значение хеш-функции.

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

Или используйте коммутативное хеширование для выражения, которое является коммутативным, т.е. убедитесь, что a + b и b + a получают одинаковоехэш-значение.

Пример арифметических выражений, включающих переменные, целые числа, операторы и скобки:

 hash VariableName = 0x12345678
 hash IntegerConstant = 0xff77ff77
 hash x + y = (hash x) + (hash y)
 hash (x) = (hash x) <<< 13
 hash x * y = (hash x) xor (hash y)

И т. д.