Разработка инфраструктуры для покрытия кода тестами в компиляторе Kotlin/Native

Покрытие кода — это метрика качества тестового покрытия. Она помогает выявлять участки кода, которые не были исполнены в процессе тестирования. Компилятор предварительно инструментирует код, чтобы собрать информацию о покрытии. В зависимости от способа инструментирования итоговое покрытие может иметь разную точность. Если способ базируется на обходе синтаксического дерева, то неисполненный участок может быть выявлен с точностью до токена.

В рамках осенней практики под руководством Сергея Боголепова мне предстояло принять участие в разработке инфраструктуры для подсчёта покрытия внутри компилятора Kotlin/Native с высокой точностью.

Как происходит инструментирование

В Kotlin/Native инструментирование реализуется с использованием средств LLVM. Для этого при компиляции код размечается на исполняемые регионы по границам синтаксических конструкций. Например, таким регионом является фрагмент кода с телом функции или телом цикла. После разметки каждый регион ассоциируется с уникальным счётчиком, и во время кодогенерации перед входом в него вставляется инструкция, инкрементирующая счётчик.

Информация об итоговом значении всех счётчиков после исполнения сохраняется в сгенерированном файле специального формата. С помощью инструментов `llvm-profdata` и `llvm-cov`файл может быть преобразован, например, в человекочитаемый отчёт о покрытии: вывод `llvm-cov show` показывает исходный код вместе со значением счётчиков исполнения в начале каждой строки.

Задача

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

— понять, какие узлы с какими регионами должны присутствовать в отображении;

— описать это в коде;

— с помощью тестов убедиться, что полученная разметка обеспечивает корректные значения счетчиков исполнения.

Задача оказалась интересной с исследовательской точки зрения. Понятие корректности покрытия в контексте конкретного языка зависит не только от его синтаксиса, но и от семантики: например, `break` выходит из ближайшего объемлющего цикла, поэтому отдельным исполняемым регионом следует считать фрагмент кода от следующего за ним оператора до конца этого цикла. Таким образом, нужно было в том числе учесть семантику конструкций языка, чтобы получить правильный алгоритм разметки.

При этом от меня не ожидалось широких познаний о внутреннем устройстве Kotlin/Native: код, осуществляющий разметку, почти не выходил за пределы одного класса.

Ход работы

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

Так выбранная стратегия разметки давала ожидаемый результат, например, для условных выражений и циклов.

Чуть сложнее оказалось реализовать поддержку jump-выражений. Так как `return` выходит из объемлющей функции, а `break` или `continue` — из объемлющего цикла, в процессе разметки нужно помнить ближайший объемлющий регион и по достижении jump-выражения разделять его на две части. При этом вторая часть, как было описано в примере про `break` выше, должна начинаться с оператора, который будет исполнен первым, если выхода не произойдет. Поэтому понадобилось помнить текущий и следующий оператор.

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

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

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

В целом, работа была организована в виде последовательности итераций, каждая из которых состояла из реализации небольшой части алгоритма разметки, оформления изменений в pull request и прохождения ревью. Таким образом, изменения постепенно добавлялись в репозиторий, а я попробовала принять участие в реальном процессе разработки большого open source проекта.

Результат

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

— обычных функций/методов;

— блоков инициализации;

— конструкторов;

— условных выражений;

— циклов;

— jump-выражений.

Тем не менее, алгоритм разметки нельзя назвать реализованным полностью: ещё есть конструкции, поддерживающие механизм try-catch-finally, inline-функции и лямбды, и все они тоже требуют специальной обработки.

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