# Боремся с 16\-летним легаси\-кодом, или исправляем C и C\+\+ front\-end в PVS\-Studio

В 2022 году статическому анализатору PVS\-Studio для языков C и C\+\+ исполняется 16 лет\. Если бы анализатор был человеком, то он бы уже заканчивал школу\. Это очень старый проект, и система типов в нем не потерпела кардинальных изменений практически с самого начала\. В этой статье мы посмотрим, как работал анализатор всё это время и расскажем, что было не так, и как мы начали это исправлять\.

![0992_new_ts2_ru/image1.png](https://import.viva64.com/docx/blog/0992_new_ts2_ru/image1.png)

## Немного истории

2005 год был богат на релизы\. В то время вышли релизы таких известных игр, как "God of War", "Resident Evil 4" и "Prince of Persia: The Two Thrones"\. А ещё свет увидел релиз компилятора Visual C\+\+ 8\.0\. В нем, помимо поддержки расширений [C\+\+/CLI](https://ru.wikipedia.org/wiki/C%2B%2B/CLI) и [OpenMP](https://ru.wikipedia.org/wiki/OpenMP), появляется ещё одна важная вещь – возможность компилировать код для 64\-битных x86\-совместимых процессоров, которые также были новыми в то время\.

Переход на 64\-битную архитектуру был тяжелым\. Было недостаточно просто взять и перекомпилировать свою программу на 64 бита\. Программы в то время писались с расчётом на 32 бита и, к примеру, могли хранить указатели в переменных типа _int_, которых недостаточно для 64\-битных указателей\. [Здесь](https://pvs-studio.ru/ru/blog/posts/cpp/a0065/) вы можете подробнее ознакомиться с 64\-битными паттернами ошибок\.

Основная проблема ошибок такого рода заключается в том, что их сложно отлаживать\. Unit\-тесты скорее всего покажут, что всё хорошо, т\.к\. работают с малыми объёмами данных\. Отлаживаться же на больших объемах практически невозможно, потому что: 

* это медленно\. Релизная версия программы должна проработать определённое время, прежде чем ошибки дадут о себе знать\. Отладочная версия же будет работать ещё дольше;
* непонятно, что именно искать в отладчике\. Можно пытаться искать ошибку в миллиардах итераций цикла, но никто так не делает\. Программисты всегда при отладке стараются использовать минимальный набор данных для воспроизведения ошибки\.

Однако их легко найти инструментом, умеющим разбирать C и C\+\+ код\. Первая версия нашего анализатора \(Viva64\) делала именно это – искала 64\-битные ошибки\. В дальнейшем инструмент приобрел и другие полезные особенности – диагностики общего назначения, \([data flow analysis](https://pvs-studio.ru/ru/blog/terms/7004/)\) анализ потока данных, поддержка Linux и т\.д\. Если вам хочется погрузиться в историю создания анализатора глубже, то её можно почитать [здесь](https://pvs-studio.ru/ru/blog/posts/0465/)\.

Конечно, разрабатывать C и C\+\+ анализатор с нуля практически невозможно из\-за сложности языков, поэтому за основу было решено взять какую\-то библиотеку\. Альтернатив на то время было немного:

* EDG – front\-end языка, использующийся в IntelliSense\. Стоит денег, которых на тот момент не было\.
* Semantic Designs – ещё один front\-end, тоже коммерческий\.
* GCC – сложный код, спорная поддержка Windows, а также лицензия GPL, которая заставила бы открыть код анализатора\.
* OpenCxx – библиотека для трансляции исходного кода C\+\+\. К сожалению, не умеет обрабатывать исходный код на языке C\. Разработана японским студентом, видимо, для дипломной работы\. И лицензия позволяет вести коммерческую разработку\. Отлично, берем\!

## OpenCxx

PVS\-Studio основан на [OpenCxx](https://chibash.github.io/public/opencxx/) – библиотеке для разработки языковых инструментов, расширений и рефакторинга C\+\+ кода\. Работала она как промежуточное звено между препроцессором и компилятором и предоставляла API на основе [метаобъектов](http://opencxx.sourceforge.net/opencxx/html/mop.html)\. Рассмотрим некоторые детали реализации\.

### Синтаксическое дерево

Дерево программы представлено классом _Ptree_\. Внутри это бинарное [дерево разбора](https://pvs-studio.ru/ru/blog/terms/0039/) с терминальными и нетерминальными узлами\. Последние служат для связки узлов\.

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

* A \* B
* A\(B\)
* A<B\>::C

Их можно разобрать по\-разному\. Например, первый случай может быть как умножением, так и декларацией указателя на тип _A_\. Второй либо вызовом функции, либо объявлением переменной\. Третий – шаблон, либо сравнение\.

Также единственный способ работы с деревом – это утилитные функции _First_, _Second_, _Third_, \.\.\., _Nth_\. Они берут узел поддерева по указанной позиции\. Например, чтобы взять левый операнд бинарного выражения _A \+ B_, нужно позвать функцию _First_, правый операнд – _Third_, а операцию – _Second_\.

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

### Система типов

Система типов в этой библиотеке состоит из 2 компонентов – _Encoding_ и _TypeInfo_\. _Encoding_ – класс\-обертка над строкой, кодирующей тип\. В основном служит для формирования этой строки\. _TypeInfo_ же наоборот, класс для работы со строкой – умеет доставать из нее информацию, раскрывать псевдонимы, однако не способен делать модификации\.

Например, вот как выглядит закодированный указатель на тип:

```cpp
int *p; // Pi
```

Функции кодируются особым образом – в начале находится буква 'F', обозначающая функцию, затем идут параметры, причем неразделенные – конец каждого параметра можно узнать, лишь перебрав все содержимое с указателями, ссылками и CV\-квалификаторами\. Возвращаемое значение отделяется символом '\-':

```cpp
int main(int argc, const char **argv); // FiPPCc-i
```

Работа с пользовательскими типами наиболее сложная\. Во\-первых, формируется особый _Encoding_ с названием класса:

```cpp
class MyClass; // \x80MyClass
```

Обратите внимание на символ '\\x80'\. Это специальный символ, который кодирует длину последующей строки\. Однако _Encoding_ не может закодировать информацию о внутреннем содержимом пользовательского типа\. Поэтому _Encoding_ ассоциируется с соответствующим ему объектом класса _Class_\. Связь устанавливается через ранее упомянутый _TypeInfo_\.

Вот список всех букв, использующихся для кодирования типа:

![0992_new_ts2_ru/image3.png](https://import.viva64.com/docx/blog/0992_new_ts2_ru/image3.png)

Кстати, на картинке вы видите фрагмент уже обновлённой системы кодирования\. Естественно, во времена создания библиотеки не существовало никаких 'x' \(auto\), 'L' \(\_\_closure\) и так далее\.

Как вы понимаете, такая структура данных скорее вредит, чем делает работу с типами удобнее\. К тому же у неё есть очевидные проблемы с производительностью, а добавлять какой\-то новый тип со временем становится сложнее, т\.к\. алфавит постепенно заканчивается, а предоставлять качественный анализ хочется\.

В качестве альтернативы в PVS\-Studio была создана легковесная структура _WiseType_, которая содержит базовую информацию о типе\. Из неё можно узнать, например, что узел дерева – это указатель на _int_ или какой\-то класс\. Но узнать тип глубже второго указателя нельзя, также нельзя узнать и конкретный тип класса\.

Да, OpenCxx можно попробовать исправить, но зачем, ведь есть же\.\.\.

## Clang

Да, Clang – это замечательная библиотека с хорошей поддержкой современных стандартов языка, быстро развивающаяся и удобная в использовании\.

Однако стоит понимать, что Clang 2005\-го года — это не то же самое, что Clang в 2022\. Хотя бы потому, что изначально проект был опубликован в июле 2007, а первая версия компилятора, способная собрать себя, [вышла только в 2010](https://ru.wikipedia.org/wiki/Clang#%D0%98%D1%81%D1%82%D0%BE%D1%80%D0%B8%D1%8F_%D1%80%D0%B0%D0%B7%D0%B2%D0%B8%D1%82%D0%B8%D1%8F)\.

Перейти на него тоже тяжело, т\.к\. уже имеется большой объем кода, который зависит от реализации OpenCxx, например – это механизм data\-flow и множество диагностических правил\. К тому же Clang развивается отдельно, в нём нет поддержки некоторых сторонних стандартов – таких, как C\+\+/CLI или C\+\+/CX, а также различных особенностей embedded\-компиляторов\. Внесение любых изменений потребует болезненных мержей с каждым новым релизом проекта\.

Всё это делает переход на Clang невозможным\.

## Что же делать?

Шло время, постепенно выходили новые стандарты языка, которые приходилось поддерживать – C\+\+11, C\+\+14, C\+\+17 и с недавнего времени C\+\+20\. А в следующем году уже выйдет C\+\+23\! Вместе с количеством фичей языка выросло и количество человек в команде, так что можно было начать постепенно решать вышеописанные проблемы и убирать костыли из различных мест\. 

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

### Make Ptree great again\!

Мы вынесли некоторую информацию из класса _Ptree_, и теперь "подмешиваем" ее в нужных наследниках\. Это позволило облегчить базовый класс _Ptree_, например, раньше объект _WiseType_ находился именно в нём и, соответственно, попадал в каждый узел дерева\.

Пока что доп\. данных всего 2 вида:

* _PtreeTyped_ – узел может содержать тип;
* _PtreeValue_ – узел может содержать виртуальное значение \(данные для data\-flow\)\.

Теперь базовый класс _Ptree_ максимально облегчён, а наследники содержат только нужную информацию\. Так, все выражения теперь наследуются от класса _PtreeExpr_, а он, в свою очередь, от _PtreeValue_\. Узлы с объявлением классов наследуются от _PtreeTyped_\.

А чтобы не проверять каждый раз тип узла при обращении к нему через _First_, _Second_ и т\.д\., для узлов были реализованы интерфейсы\. Так выглядит интерфейс бинарного выражения:

* _GetLeftOperand\(\)_ – левый операнд;
* _GetOperationName\(\)_ – имя операции \(не токен\);
* _GetRightOperand\(\)_ – правый операнд\.

_GetLeftOperand_ и _GetRightOperand_ возвращают _PtreeExpr_, а не просто _Ptree_\.

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

### Brand New Type System

Новая система типов появилась в PVS\-Studio 7\.18\. Процесс перехода был сложным, но в итоге мы добились стабильной работы и включили изменения в основную ветку\.

Ранее все типы были представлены в одной структуре данных – строке символов\. Теперь же у нас есть некая иерархия классов, в которой можно хранить всё что угодно, не только символы, но, например, ещё и ссылки на узлы AST\. Также каждый тип содержит ссылку на "раскрытый" тип – без _typedef_, _using_ и некоторой другой информации\. Он вычисляется сразу при создании нового типа, так что мы можем не тратить время на его раскрытие, когда нам это нужно \(а нужно примерно всегда\)\.

![0992_new_ts2_ru/image5.png](https://import.viva64.com/docx/blog/0992_new_ts2_ru/image5.png)

Ещё одна особенность новой системы типов – это способ хранения cv\-квалификаторов\. Они лежат в старших битах указателя, которые на современных системах не используются\. Однако для разыменования такого указателя стоит эти биты возвращать "на место"\. Несмотря на это, такой способ позволяет сократить потребление памяти и сделать работу с квалификаторами чуть быстрее\. Разработчики процессоров в курсе таких трюков у программистов, поэтому сейчас Intel/AMD делают свои расширения \([Intel Linear Address Masking](https://www.phoronix.com/scan.php?page=news_item&px=Intel-LAM-Linux-Kernel-May-2022), [AMD Upper Address Ignore](https://www.phoronix.com/scan.php?page=news_item&px=AMD-Linux-UAI-Zen-4-Tagging)\), чтобы эти биты не трогать и сэкономить пару тактов на разыменование\. К слову, в Clang квалификаторы хранятся схожим образом\.

Для перехода на новую систему типов нам пришлось предоставить какой\-то слой совместимости с ней, чтобы не ломать существующий код\.

Как мы уже говорили, для формирования типов служит _Encoding_\. Идти и переписывать парсер \(а именно он создаёт изначальную информацию о типах\), ничего не поломав по пути сложно, поэтому мы сделали конвертер из строки с типом в наше новое представление\. Этот конвертер будет временным решением, т\.к\. в будущем мы планируем от него избавиться и перейти на новую систему во всех этапах работы анализатора\.

С классом _TypeInfo_ проще – нам достаточно реализовать его интерфейс и всё должно заработать\. Но это идеальный случай\. Некоторые методы реализовать очень сложно, или практически невозможно – например тот, что позволяет получить нижележащую строку с закодированным типом\. Поэтому в некоторых местах придется посмотреть на код и немного его переписать\.

## Планы на будущее

На данный момент уже сделано много работы: реализована новая система типов и готовы интерфейсы для дерева\. Но это не всё, что нам нужно для полного счастья\.

Как было сказано выше, семантический и синтаксический анализ файла сейчас строго разделен\. Такое для языка C\+\+, или даже для C неприемлемо – чтобы правильно построить дерево, нужно знать, чем является идентификатор – типом, переменной, или же мы его встречаем впервые\. Для этого стоит переносить семантический анализ из обходчика на этап парсинга\.

Текущее дерево назвать абстрактным сложно\. Внутри каждый узел содержит строку с токеном из файла, а вся структура узлов завязана на реализацию грамматики\. И само дерево бинарное – в нём очень много "мусорных" узлов, которые существуют только для связи\. Это вредит производительности обхода, а также увеличивает потребление памяти\. Мы хотели бы изменить структуру дерева, чтобы этого избежать\.

И последняя проблема, которая нас мучает – это инстанцирования шаблонов\. Все они выполняются на одном и том же дереве\. Это значит, что после инстанцирования мы теряем информацию об оригинальном дереве – теперь там лежат новые типы и виртуальные значения\. Сохранять их перед инстанцированием слишком накладно, так что после него они просто "убиваются"\. Более того, в процессе работы дерево может перестроиться, и в итоге оригинальное дерево может измениться\. Мы хотим сделать так, чтобы на каждое инстанцирование делалась копия оригинального дерева, а само оно оставалось нетронутым\.

## Заключение

Надеюсь, что эта история показалась вам полезной и интересной\. Конечно, до Clang нам еще далеко, но мы уже запустили процесс переработок и надеемся его завершить\. Вы можете оценить наши труды и проверить свой собственный проект, запросив [триальный](https://pvs-studio.ru/ru/pvs-studio/try-free/) ключ\. Если у вас обнаружатся какие\-то проблемы, то просим вас написать об этом нам в поддержку и прислать пример\. Будем рады их посмотреть и исправить\.