Как работает статический анализ DTL: алгоритмы

(Настоящая цель этого поста — дать необходимый контекст для куда более интересного мне поста про дизайн анализа.)

Вычисление типов. DTL — язык с динамической типизацией, поэтому его анализ требует возможности вычислить тип любого заданного выражения в программе. (Под «заданным выражением» мы понимаем любой узел абстрактного синтаксического дерева — AST, и узлы эти в дальнейшем будем величать нодами.)

Наша IDE использует demand-driven анализ. Его суть проще всего понять на примере, которых ниже достаточно. Выбора между итеративным и demand-driven анализом мы еще когда-нибудь коснемся.

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

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

Кроме того, помимо нод, нам нужно научиться определять:
— тип возвращаемого значения конкретного метода конкретного класса;
— тип локальной переменной;
— тип аргумента;
— тип поля;
— тип глобальной переменной.

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

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

Вызов метода. Запускаем анализ для выражения слева от точки. Для всех классов, которыми может быть то выражение, ищем метод с таким именем. Получаем набор кандидатов. Далее запускаем анализ для каждого аргумента. Когда он выполнен, запускаем анализ возвращаемого значения каждого из кандидатов, передавая ему тип получателя (т.е. выражения слева от точки) и типы аргументов.

Локальная переменная. Проходим AST текущего метода и находим все присваивания этой переменной. (Т.е. находим текстуально все присваивания переменной с таким именем.) Запускаем анализ для правой части каждого присваивания. Результаты объединяем.

Аргумент. Делаем то же, что и для локальной переменной. Затем, если в текущий метод мы пришли из другого метода, то типы аргументов в конкретной точке вызова были уже вычислены, и мы просто используем их, объединяя с результатами анализа для локальной переменной. Если же типы аргументов не известны, то мы находим все вызовы нашего метода, и в каждом вызове запускаем анализ для соответствующего аргумента. Результаты объединяем.

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

Поле. Тривиально. Мы проходим по всем методам класса, в каждом находим все присваивания переменной с таким именем (да, для прототипа мы не заботились о сокрытии имен — можно было еще проверить, что это действительно ссылка на поле), для каждого запускаем анализ типа правой части. Результаты объединяем.

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

Тип возвращаемого значения метода. Находим в методе все операторы return, вызываем анализ для выражения в каждом из них, результаты объединяем.

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

Массивы. Когда мы встречаем присваивание переменной вида a[2] = x, мы запоминаем, что присваивание выполнялось переменной a, но вычисленный тип x нужно сначала обернуть в тип-массив.

Когда нам нужно вычислить тип a[2], мы запускаем анализ для a, затем среди возможных типов переменной отбираем типы-массивы и разворачиваем их, получая типы элементов.

Индекс. Поскольку обход 35 тыс. строк программы занимает около 50 мс и требуется для каждой глобальной переменной (которых мало, что дает около секунды) и каждого метода (которых много, что дает десятки секунд), мы предварительно обходим всю программу, запоминая все вызовы методов и все присваивания переменным, и группируя их по именам (так, что за константное время по заданному имени можно найти все его вызовы и все присваивания ему).

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