# Как мы научили JavaScript анализатор понимать поток управления

Недавно в статический анализатор PVS\-Studio была добавлена поддержка JavaScript/TypeScript, и он на старте умеет искать ошибки, связанные с потоком управления\. Причём тут граф потока управления, как мы его добавили и чем это полезно — читайте в этой статье\.

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

## Граф потока управления?

Я уже затрагивал эту тему, в частности, в моей [серии](https://pvs-studio.ru/ru/blog/posts/java/1198/) про taint\-анализ в Java, но кратко напомню\. Исходный код, попадая в статический анализатор, преобразуется в [абстрактное синтаксическое дерево](https://pvs-studio.ru/ru/blog/terms/0004/) \(AST\)\. Оно почти полностью отображает структуру кода, как он написан в редакторе\. Для задач анализа потока управления, таких как поиск недостижимого кода, оно подходит плохо\. На AST можно написать проверку, которая его ищет, но:

1. Это будет работать ненадёжно в граничных случаях\.
1. Это будет плохо масштабироваться на другие подобные правила\. 
1. В дальнейшем это будет тяжело поддерживать\. Как при правке ошибок, так и при поддержке новых версий языков, для которых понадобится пройтись по всем таким диагностическим правилам\. 

Для решения этих задач и существует граф потока управления \(Control Flow Graph, CFG\), который отвечает за отображение всех возможных путей в программе\.

![1418_js_cfg_ru/image2.png](https://import.viva64.com/docx/blog/1418_js_cfg_ru/image2.png)

Состоит он из трёх составляющих:

1. Узлы входа и выхода\.
1. Узлы базовых блоков, внутри которых расположены линейные инструкции\.
    * Базовые блоки заканчиваются терминаторами \(либо ничем\)\. Терминаторы — особые инструкции, выражающие определённую семантику потока выполнения: ветвления, `break`/`continue` и т\.п\.
1. Рёбра между узлами графа, отображающие возможные переходы потока управления\.

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

## Как мы это сделали?

### Обобщённый CFG

В [статье](https://pvs-studio.ru/ru/blog/posts/js/1363/) про разработку JavaScript/TypeScript анализатора мы уже [упоминали](https://pvs-studio.ru/ru/blog/posts/js/1363/#IDC01AE1A5F1), что инструмент включает в себя не только синтаксическое дерево для конкретного языка, но и обобщённое для мультиязыкового анализа\. Мы назвали его CAT \(Common Abstract Tree\)\.

И хоть пока к JavaScript/TypeScript другие языки не присоединились, уже сейчас мы заложили возможность для расширения CFG: основной движок работает агностично от конкретного языка\. Для этого мы описываем набор разных семантик и собираем их как конструктор под нужный нам язык\. Таким образом, мы экономим себе время на поддержке других языков в будущем\.

![1418_js_cfg_ru/image4.png](https://import.viva64.com/docx/blog/1418_js_cfg_ru/image4.png)

Примера таких специальных семантик для JavaScript/TypeScript два:

* `try` блоки, в которых исключения не типизированные, и больше одного `catch` быть не может\.
* Метки вешаются на конкретную инструкцию, и к ней можно перейти только из вложенного в неё `break`\. Также можно перейти по метке через `continue`, если она стоит на цикле\.

### Подход к тестированию

Проверка CFG на корректность — отдельное приключение\. Первое, что приходит в голову: сериализовать граф в [Graphviz](https://en.wikipedia.org/wiki/Graphviz) либо иным способом, проверить глазами и зафиксировать эталон\. Спойлер: это грабли, и мы на них наступили\. Вот почему это не работает:

* Граф постоянно меняется при разработке\. Придётся переписывать падающие тесты руками либо сжигать токены ИИ\-агентов\.
* Пропустить баг в эталоне очень легко\. Если бы люди не делали ошибок, то индустрия статического анализа бы не существовала\.
* Красивая топология не гарантирует, что граф реально передает всю семантику потока управления\.

В итоге мы сменили подход и написали мини\-интерпретатор нашего CAT на базе CFG\. Идея простая: если наш интерпретатор, обойдя граф, даст тот же результат, что и интерпретатор JavaScript, то граф построен верно\. Проверяется это простым Assertion API такого вида:

```cpp
@Test
void branching() {
    EvaluationAssert.evaluate("branching")
                    .withParam("param", true)
                    .expect("a", 2);

    EvaluationAssert.evaluate("branching")
                    .withParam("param", false)
                    .expect("a", 0);
}
```

Этот тест запускает интерпретатор и сверяет результаты выполнения с эталоном, который можно получить, предварительно выполнив TypeScript код:

```cpp
function branching(param: boolean) {
    let a = 1;
    if (param) {
        a++;
    } else {
        a--;
    }
}
```

Всю спецификацию JavaScript реализовывать не пришлось — хватило крохотного подмножества\. А срезание углов даже сыграло на руку: если не очищать переменные при выходе из области видимости, то можно видеть состояние кода в разных точках\.

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

Ещё один приятный бонус: минималистичный интерпретатор — полноценная проверка концепции для обработки графа и может служить как референсом для использования API, так и ориентиром для дальнейших работ по анализу потока данных\.

По итогу имеем работающий строитель графов для JavaScript/TypeScript, строящийся за один проход по AST, что довольно шустро — для [React](https://www.google.com/search?client=firefox-b-d&q=react&sei=_ymVao7PAuev5NoPzafroAY) все графы строится за четверть секунды\.

## Что уже ищем?

### Линейный код

Самые рядовые опечатки, которые можно было бы искать и через AST, конечно, идут первыми:

```cpp
if ( curveLengths[ i ] >= d ) {
    diff = curveLengths[ i ] - d;
    curve = this.curves[ i ];
    var u = 1 - diff / curve.getLength();
    return curve.getPointAt( u );
    break;
}
```

Предупреждение PVS\-Studio: [V7039](https://pvs-studio.ru/ru/docs/warnings/v7039/) Unreachable code detected\. Control flow never reaches this statement\. [three\.js 29417](https://github.com/juice-shop/juice-shop/blob/1618a611b173b4bf114028e6e02549950606e29d/frontend/src/assets/private/three.js#L29417)\.

Граф, который строит анализатор:

![1418_js_cfg_ru/image6.png](https://import.viva64.com/docx/blog/1418_js_cfg_ru/image6.png)



<details>
   <summary>Что за merge узлы?</summary>

merge — это вспомогательный узел для построения графа, который упрощает работу с ним, поскольку обрабатывать узлы с множественными предшественниками неудобно Анализ с merge узлами \(пока\) не взаимодействует\. 

На примере выше merge имеет один вход, а не два, как на картинке ранее, так как в `true` есть `return`, который обязывает создать ребро сразу к выходу\. 


</details>
На нём отлично видно, что в `break` нет ни одного пути, поэтому он помечается как недостижимый\. 

Маловероятно, что эта ошибка на что\-то влияет, и, скорее всего, недостижимый `break` просто является лишним\. Но что занятно: этот файл — библиотека [Three\.js](https://github.com/mrdoob/three.js/), скопированная внутрь [Juice Shop](https://github.com/juice-shop/juice-shop/), и такой же ошибки внутри актуального репозитория Three\.js мы не нашли\.

Кстати, классический баг с Automatic Semicolon Insertion вида:

```cpp
function foo() {
    return // asi happens here
        this.bar
}
```

Будет ловиться точно таким же образом, ведь вставленная `;` создаст терминатор в блоке с `return` и вынесет `this.bar` в следующий блок:

![1418_js_cfg_ru/image7.png](https://import.viva64.com/docx/blog/1418_js_cfg_ru/image7.png)

### Условия

Занятный случай "защитного программирования" произошёл в [Phaser](https://github.com/phaserjs/phaser):

```cpp
if (!childA.parentContainer && !childB.parentContainer)
{
    return this.displayList.getIndex(childB)
      - this.displayList.getIndex(childA);
}
else if (childA.parentContainer === childB.parentContainer) {
// more branches ending with return statements here
} else
{
    var listA = childA.getIndexList();
    var listB = childB.getIndexList();
    var len = Math.min(listA.length, listB.length);

    for (var i = 0; i < len; i++)
    {
        var indexA = listA[i];
        var indexB = listB[i];

        if (indexA === indexB)
        {
            continue;
        }
        else
        {
            return indexB - indexA;
        }
    }
    return listB.length - listA.length;
}
//  Technically this shouldn't happen, but ...
// eslint-disable-next-line no-unreachable
return 0;
```

Предупреждение PVS\-Studio: [V7039](https://pvs-studio.ru/ru/docs/warnings/v7039/) Unreachable code detected\. Control flow never reaches this statement\. [InputPlugin\.js 2981](https://github.com/phaserjs/phaser/blob/02d8931b626d9764c133cbb3fbf99966c03c757c/src/input/InputPlugin.js#L2981)

Веток else\-if было больше, но я их убрал для краткости и чтобы уменьшить граф:

![1418_js_cfg_ru/image9.png](https://import.viva64.com/docx/blog/1418_js_cfg_ru/image9.png)

Если вчитаться в комментарий и посмотреть на код, то опасение программиста должно стать понятным: выше сложная логика с 5\+ ветками, каждая из которых завершает поток выполнения, поэтому он решил перестраховаться, не доверившись даже ESLint\. Мы же вслед за ним по топологии графа увидели, что пути в `return 0` просто нет\.

### Циклы

"Бесплатно" мы получаем и нахождение циклов, которые выполняются бесконечно или, наоборот, всего один раз\. Такой случай попался в уже упомянутом Three\.js:

```cpp
loop:
for (var pos = 0; pos < limit; pos++) {
    for (; pos < limit; pos++) {                 // <=
        for (var k = 0; k < needleLength; k++) {
            if (haystack[pos + k] !== needle[k]) {
                continue loop;
            }
        }

        return pos;
    }
}
```

Предупреждение PVS\-Studio: [V7039](https://pvs-studio.ru/ru/docs/warnings/v7039/) Unreachable code detected\. Control flow never reaches this statement\. [opentype\.module\.js 6109](https://github.com/mrdoob/three.js/blob/aa625d502d4920a84975c80a6438c108678fb4ac/examples/jsm/libs/opentype.module.js#L6109)\.

Граф потока управления:

![1418_js_cfg_ru/image10.png](https://import.viva64.com/docx/blog/1418_js_cfg_ru/image10.png)

Диагностика обнаружила, что на графе инкремент переменной `pos` в цикле недостижим\. Посмотрев на код, легко заметить, что все ветки действительно прерывают второй `for`, и у него будет лишь одна итерация\. А на графе это подтверждается — пути в инкремент нет\.

Попал этот код в проект из [OpenType](https://github.com/opentypejs/opentype.js), но ныне скопированная зависимость уже удалена\.

### Обработка исключений

Случаи с вложенными `try` и прерыванием потока выполнения из `finally` не только экзотические, но часто и считаются code smell, так что сходу найти срабатывания в Open Source не вышло\.

Однако это был один из самых нетривиальных случаев для обработки из\-за запутанности семантики `try-catch-finally`\. Нужно учитывать:

* Есть ли в `try` секции `catch`, `finally` или обе\.
* Следить не только за явными `throw`, но и обрабатывать, куда тебя приведут неявные исключения\.
* Перезаписывать прерывание потока управления своим внутри `finally`, когда оно произошло в `try` или `catch`\.
* Каскадно пробрасывать прерывание потока управления сквозь `try`, если оно произошло в `finally`\.
* И ещё множество других граничных кейсов, а также их комбинаторные сочетания\.

Так что покуда этот случай показать хочется, приведу синтетический пример:

```cpp
function tryCatchFinallyCase() {
    try {
        try {
            throw new Error("Whoops");
        } finally {
            console.log("inner")
        }
        return true // V7039
    } finally {
        console.log("outer")
    }
    return false; // V7039
}
```

Для такой функции анализатор построит следующий граф:

![1418_js_cfg_ru/image11.png](https://import.viva64.com/docx/blog/1418_js_cfg_ru/image11.png)

На графе можно чётко увидеть, что сами рёбра несут в себе информацию о том, какую операцию они "запомнили" до выхода из функции\. В то же время недостижимые `return` узлы идентифицируются анализатором\. 

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

Мы рассмотрели ошибки, которые анализатор способен находить при помощи нового механизма\. И действительно, он уже показал свою эффективность, позволив достаточно тривиально реализовать диагностики [V7039](https://pvs-studio.ru/ru/docs/warnings/v7039/) \(недостижимый код\) и [V7040](https://pvs-studio.ru/ru/docs/warnings/v7040/) \(бесконечная рекурсия\) к релизу PVS\-Studio 8\.00\. Но помимо диагностик, перед нами открываются и новые перспективы:

* Углубить построение CFG, распространив его на short\-circuit выражения\.
* Научиться находить не только недостижимый, но и мёртвый код за счёт условного проброса констант\.
* Сделав основу для движка анализа потока данных, можно будет начать с [taint\-анализа](https://pvs-studio.ru/ru/blog/terms/6496/) \(анализ помеченных данных\)\.
* А углубив этот же движок, можно будет перейти к расчёту других видов [анализа потока данных](https://pvs-studio.ru/ru/blog/terms/7004/), таких как поиск разыменования нулевой ссылки, деления на ноль и прочего\.

В общем, если CAT дал нам возможность расширения вширь, то CFG позволяет расширяться вглубь, так что теперь почва для развития нового анализатора стала ещё более плодотворной\.

## Итоги

На этом небольшой экскурс в эту технологию анализатора заканчивается\. Надеюсь, вам было интересно узнать больше о том, как статический анализатор устроен изнутри, и какие ошибки можно найти при помощи анализа потока управления\. Если вдруг у вас был опыт с подобными технологиями, то пишите в комментариях — будет интересно почитать\. А впереди всё ещё маячит обещанная статья про устройство нашего CAT, как и другие статьи про качество кода, так что не забывайте следить за нами в:

* блоге PVS\-Studio в [X](https://x.com/pvs_studio);
* нашем ежемесячном [дайджесте](https://pvs-studio.ru/ru/subscribe/) статей;
* моём личном [блоге](https://twitter.com/kvolokhovskii)\.