Value-tracking анализ JavaScript

О проекте

В третий раз мне выпала возможность проходить практику в компании JetBrains, под руководством Сергея Шкредова. Проектов для практики было несколько, и мне дали возможность выбрать интересующий меня больше других. После недолгих раздумий я остановился на проекте под названием Value-tracking анализ JavaScript.

Целью проекта являлась разработка статического анализа (т.е. анализа программы без её непосредственного исполнения), который бы позволял выяснять всякие интересные свойства программы. Например, на таком простом примере кода смог бы определить, что второе условие всегда истинно.

Или, скажем, предупредить о том, что вот такой код содержит ошибку (обращение к нулевому указателю).

Или даже сообразить, что в следующем коде внутреннее условие всегда ложно:

Работа над проектом

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

Параллельно освоению теоретической базы я знакомился с ReSharper'ом (для краткости, просто R#), для которого анализ и был задуман. В R# уже был написан другой анализ для JavaScript (расширенная версия анализа достигающих определений), и большая часть предварительной работы (например, построение графа потока управления и итерационный алгоритм решения задачи анализа потока данных) уже была сделана, а мне нужно было разобраться с существующим кодом и на его основе написать новый анализ.

Это был весьма интересный опыт, потому как R# — проект просто громадный, и даже та часть, что отвечает за анализ потоков данных, тоже весьма увесистая. Я никогда раньше не работал с проектами такого масштаба. Чтобы сделать первые шаги, мой руководитель предложил мне перевести существующий анализ на использование другой структуры данных (чтобы уменьшить потребляемое анализом количество памяти), а заодно и начать работу над R#-ом.

Понемногу, маленькими шажками, а затем всё больше набирая темп, я разбирался с существующим кодом и делал свою первую задачу. К моменту, когда я с первой задачей закончил, у меня уже сложилось достаточное представление о работе необходимого "куска" R#-ра, и я принялся непосредственно за свой проект. Дальше всё пошло уже более быстрым темпом. Мы разделили все возможные значения выражений в JavaScript на несколько классов, затем написали автоматическую генерацию кода обработки вычисления значений для всевозможных операторов в выражениях языка (нам показалось, что это проще, чем разбираться во всех хитросплетениях, которыми обладает семантика JavaScript), написали обработку различных конструкций (while, switch, и т.д.) — вобщем, работа пошла полным ходом.

Результат

К концу практики наш анализ был практически готов, он работал и выдавал ожидаемые от него результаты. Но у него были проблемы, и главная из них — производительность. К сожалению, версия анализа, которая способна обрабатывать случаи, подобные третьему примеру, казалась слишком требовательна как по памяти, так и по времени, чтобы её можно было включить в R#, который перезапускает анализ на каждое изменение файла. Но на самом деле наш конечный анализ оказался смесью двух анализов, притом один из них обладает достаточной производительностью, чтобы работать в интерактивной среде, хоть и не справляется с приведённым примером. Зато отлично справляется с двумя приведёнными выше примерами (и не только с ними, конечно):

Ещё его включили в R# 7.1 (про него можно даже прочитать в блоге компании).

Для меня стало большой приятной неожиданностью, что продукт моего труда попал в релиз такого крупного проекта. Но что ещё более важно, я открыл для себя область, которая мне оказалась очень интересна — языки программирования. Работая над анализом, я всерьёз заинтересовался тем, как можно из текста программы получить нечто, исполняемое на компьютере, как можно по тексту программы найти в ней ошибки, каким образом устроены инструменты для разработчиков и др.

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