Статический анализ: скажите, совпадают ли две функции Javascript

Question

Я ищу способ, используя статический анализ двух функций JavaScript, чтобы определить, совпадают ли они.Позвольте мне определить несколько определений «одного и того же».

Уровень 1: Функции одинаковы, за исключением возможных различных пробелов, например TABS, CR, LF и SPACES.

Уровень 2 Функции могут иметь разные пробелы, такие как Уровень 1, но также могут иметь разные имена переменных.

Уровень 3 ???

---

Для первого уровня, я думаю, я мог бы просто удалить все (нелитеральные, которые могут быть жесткими) пробелы из каждой строки, содержащей два определения функции JS, а затем сравнить строки.

Для уровняво-вторых, я думаю, мне нужно будет использовать что-то вроде синтаксический анализатор SpiderMonkey для генерации двух деревьев разбора, а затем написать компаратор, который обходит деревья и позволяет переменным иметь разные имена.1022 * [Редактировать] Виллихам, подмечает ниже.Я имею в виду идентичные.Теперь я ищу некоторые практические стратегии, особенно в отношении использования деревьев разбора.

Answer 1

Reedit:

Чтобы изложить мое предложение по определению идентичных функций, можно предложить следующий поток:

Уровень 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) может подсчитывать количество символов в строке и возвращать их.

Хотя эти функции, безусловно, не будут идентичны, они будут одинаковыми: для любого заданного (действительного) входного значения они будутдать одно и то же значение.

---

Моя точка зрения:

Определение, являются ли две функции идентичными (то, чего вы, кажется, хотите достичь), является (в меру) тривиальной проблемой, выполненной, как выописать.

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

---

Редактировать: Конечноидентичные функции также одинаковы;но весьма специфичным и редко полезным способом для полного анализа.

Answer 2

См. Мою компанию (Semantic Designs) Smart Differencer инструмент. Это семейство инструментов анализирует исходный код в соответствии с грамматикой детализации уровня компилятора для интересующего языка (в вашем случае, JavaScript), создает AST, а затем сравнивает AST (который фактически игнорирует пробелы и комментарии). Литеральные значения нормализуются, поэтому не имеет значения, как они «пишутся»; 10E17 имеет то же нормализованное значение, что и 1E18.

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

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

У вас больше работы, чем вы ожидаете.

Answer 3

Ваш подход для уровня 1 кажется разумным.

Для уровня 2, как насчет замещения некоторой элементарной переменной для каждой функции, а затем подходит для уровня 1?Начните с начала и для каждого объявления переменных, с которым вы столкнетесь, переименуйте их в var1, var2, ... varX.

. Это не помогает, если функции объявляют переменные в разных порядках ... var i и var j могут использоватьсяодинаково в обеих функциях, но объявлены в разных порядках.Тогда вы, вероятно, оставили сравнение деревьев разбора, как вы упомянули.