Извлечение AST из кода - часть, которая должна быть реализована отдельно для каждого языка программирования; остальное - общий. Пока что я написал его для C ++ и Python. В первом случае я использовал LLVM сначала для компиляции, а затем для вывода дерева. Поскольку символы кода C ++ могут быть неоднозначными, необходима компиляция, которая, очевидно, требует, чтобы код прошел этап компиляции без ошибок. Подумайте на секунду, сколько интерпретаций может иметь этот фрагмент кода C ++: x * y;

  • Объявление y указателя типа x,
  • Умножение x на y.

Версия Python, будучи интерпретируемым языком, не так уж необходима и может получить AST, если только синтаксис не ошибочен.

Как вы могли догадаться, отслеживание всех уникальных образцов деревьев становится практически невозможным для достаточно больших деревьев и достаточно расширенных образцов деревьев. Чтобы справиться со сложностью, нужны некоторые хитрости.

Уловка # 1

Чтобы оценить повторение выборки дерева внутри AST, нам нужен алгоритм, чтобы отслеживать все образцы дерева и группировать их в соответствии с их структурой и идентификаторами узлов. После группировки мы узнаем, какие образцы (символы) дерева присутствуют в дереве, а также сколько их. По сути, у нас есть номинатор при вычислении вероятности появления символов, pₛ = повторениеₛ / # символов; достижение #symbols или количества всех перекрывающихся образцов дерева в дереве - это отдельная проблема.

Количество отслеживаемых выборок дерева увеличивается экспоненциально по мере увеличения размера AST и размера выборок дерева. Невозможно отследить все символы размером ›10 даже в AST небольшого размера (~ 5000 узлов).
Но нам нужно только отслеживать повторяющиеся символы, остальные можно отбросить, так как каждый из неповторяющиеся символы имеют значение repeat, равное 1, поэтому их pₛ = 1 / # символы всегда. Я сделал визуализацию того, как повторяющиеся образцы дерева увеличивающегося размера выглядят в небольшом дереве. Посмотрим, сможете ли вы понять трюк, просто проверив анимацию:

Я знаю, что это беспорядок. Тем не менее, очевидно одно: уникальные узлы (те, которые не обведены кружком k = 1) никогда не являются частью повторяющейся выборки дерева, независимо от значения k. Еще один шаг: уникальная связная пара узлов в дереве (k = 2) никогда не является частью повторяющихся выборок дерева размером k ›2. Таким образом, можно обнаружить общее правило: отслеживая повторяющиеся образцы дерева при увеличивающихся размерах, мы знаем, что при размере k + 1 нам нужно только расширить уже найденные неуникальные образцы дерева размера k. Даже если пойти дальше, когда мы расширяем образцы дерева - расширяем дерево на один узел, который подключен к нему в исходном AST - сами расширения должны быть чем-то, что повторяется, чтобы получить потенциально повторяющееся k + 1 образец. Таким образом, простой способ расширения выборки дерева - сохранить все повторяющиеся пары родитель-потомок (k = 2) и попытаться прикрепить их к образцам размером k следующим образом: для каждого (повторяющегося) образца дерева размером k uᵢ и каждого (повторяющегося) образца дерева размером 2 qⱼ проверьте, uᵢ содержит узел parent (qⱼ), но не child (qⱼ); если это подходит, uᵢ можно расширить с помощью child (qⱼ) в нужной позиции, чтобы получить вероятный повторяющийся символ размера k + 1 .

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

Уловка # 2

Чтобы получить вероятность каждого символа и, следовательно, энтропию AST, нам все равно нужно вычислить # symbolsₖ, которое представляет собой количество всех выборок дерева размером k в дан AST. При k = 1 # символов₁ = # узлов. При k = 2, #symbols ₂ = # node - 1 или количество дочерних элементов в дереве, кроме корня.

Получение # символов₃ по-прежнему интуитивно понятно: на каждом узле vᵢ подсчитываются возможные символы с корнем vᵢ; если vᵢ имеет m ᵢ количество дочерних элементов, необходимо выбрать 2 из них независимо от порядка, поэтому создается образец дерева размером 3. Другой способ построения дерева трех размеров - взять ветку от vᵢ длиной не менее 2 узлов, поэтому вместе с vᵢ они составляют 3 узла; Итак, допустим, у нас есть количество потомков детей vᵢ, м² ᵢ. m² ᵢ дает нам количество двух длинных путей, начинающихся с vᵢ. Таким образом, # symbols₃ = SUMᵢ ((mᵢ select 2) + m²ᵢ). Когда k ›3, наши руки должны пачкаться.

Эта проблема по существу описана на этой странице Reddit. Короче говоря, на каждом узле vᵢ мы должны подсчитать количество возможных выборок дерева размером 1, 2,…, k с корнями в vᵢ . Это выполняется при обходе AST по порядку, восходящем от листьев вверх. В vᵢ мы должны знать размеры выборки дерева до k всех его дочерних элементов. Чтобы подсчитать всю комбинацию из k узлов с корнями в vᵢ, мы должны решить проблему суммы подмножеств - взять комбинации образцов дерева, основанных на дочерних элементах vᵢ, поэтому сумма их размеров равна k-1; это то же самое, что иметь набор чисел (размеры выборки дерева детей) и пытаться найти комбинации (подмножества) этих чисел, чтобы в сумме получить k-1. Поскольку нам нужны узлы
k-1 ниже vᵢ, чтобы включить k узлов вместе с vᵢ . Проконсультируйтесь с реализацией функций ntreesample и ntreesample_ для получения дополнительных сведений - я провел дополнительную оптимизацию сверху - но я надеюсь, что вы поняли суть.

Я также реализовал быструю приблизительную версию подсчета выборки дерева, потому что описанное выше решение, вероятно, имеет полиномиальную сложность степени k, которая резко возрастает при k ›10. Аппроксимация выполняется путем случайного создания мини-деревьев, которые представляют степень и структуру узлов и их окружения в исходном AST. После подсчета количества выборок дерева размером k на этих мини-деревьях я усредняю ​​счетчики по ним, а затем умножаю среднее значение на количество узлов, чтобы получить результат. Это приближение так же далеко от реальности, как и гендерная политика; тем не менее, ошибка здесь превращается в log (error) в значении энтропии, поэтому она должна быть только приблизительной.

Дальнейшее развитие

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

Взгляните на мою реализацию отсюда и поиграйте с ней! Для вычисления энтропии дерева вашего кода C ++ или Python требуется один прогон. Возможно, вам сначала придется запустить LLVM, но только для части C ++!