Как правила обходят AST

AST (Abstract Syntax Tree) в JavaScript представляет собой структурированное дерево, отражающее синтаксис исходного кода. ESLint строит поверх него модель обхода, в которой каждое правило подключается как набор обработчиков узлов. Именно механизм обхода AST определяет, как и когда правило «видит» конкретные конструкции кода и принимает решение о сообщении об ошибке.

ESLint использует формат ESTree. Любой файл превращается в корневой узел Program, внутри которого находятся:

  • объявления (VariableDeclaration, FunctionDeclaration)
  • выражения (ExpressionStatement)
  • импорты и экспорты (ImportDeclaration, ExportNamedDeclaration)
  • блоки и управляющие конструкции

Каждый узел содержит:

  • type — тип синтаксической конструкции
  • ссылки на дочерние узлы (body, expression, left, right и т.д.)
  • метаданные (loc, range, comments)

Обход AST строится как рекурсивный спуск по этим связям, начиная с Program.

Базовый механизм обхода в ESLint

Внутри ESLint работает универсальный traverser, основанный на глубинном обходе дерева (DFS). Его задача — последовательно посетить каждый узел дважды:

  • при входе в узел (enter)
  • при выходе из узла (exit)

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

Упрощённая модель выглядит так:

  1. Берётся текущий узел
  2. Вызываются все обработчики enter
  3. Рекурсивно обходятся дочерние узлы
  4. Вызываются обработчики exit

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

Visitor Keys и определение структуры обхода

ESLint не «угадывает» структуру узлов. Для каждого типа используется набор visitor keys — список свойств, содержащих дочерние узлы.

Пример:

  • IfStatement → test, consequent, alternate
  • BinaryExpression → left, right
  • CallExpression → callee, arguments

Эти ключи задаются в eslint-visitor-keys. Именно они определяют, куда движется обход.

Если у узла нет visitor keys, он считается листовым и обход не углубляется.

Модель выполнения правил

Каждое правило ESLint — это функция, возвращающая объект с обработчиками узлов:

create(context) {
  return {
    Identifier(node) {
      // логика проверки
    }
  };
}

Этот объект называется visitor. ESLint связывает его с обходчиком AST.

Когда traverser попадает в узел Identifier, он проверяет:

  • есть ли обработчик для этого типа
  • нужно ли вызвать его на enter или exit стадии

Таким образом правило не управляет обходом напрямую — оно «подключается» к уже существующему traversal engine.

Порядок вызова обработчиков

Если несколько правил слушают один и тот же тип узла, ESLint вызывает их последовательно в рамках одного посещения.

Порядок определяется внутренним registry правил и не зависит от структуры AST.

Сценарий выглядит так:

  1. Traverser входит в узел
  2. Вызываются все enter-обработчики для этого типа
  3. Обходятся дочерние узлы
  4. Вызываются exit-обработчики

Это важно для правил, которые зависят от контекста вложенности, например анализа областей видимости или цепочек вызовов.

Контекст узла и SourceCode

Каждый обработчик получает context, через который доступен SourceCode:

  • получение текста узла
  • доступ к комментариям
  • поиск токенов
  • работа с диапазонами (range)

AST-обход сам по себе не содержит текстовой информации — он оперирует структурой. SourceCode связывает структуру с исходным текстом.

Пример взаимодействия:

  • узел BinaryExpression
  • через context.getSourceCode().getText(node)
  • получаем исходный фрагмент кода

Это разделение позволяет traversal engine оставаться независимым от текстового представления.

Рекурсивная модель и стек вызовов

Обход AST реализуется через стек вызовов, соответствующий глубине вложенности.

Для кода:

function a() {
  if (x) {
    return y;
  }
}

последовательность обхода будет:

  1. Program
  2. FunctionDeclaration
  3. BlockStatement
  4. IfStatement
  5. Identifier (x)
  6. BlockStatement
  7. ReturnStatement
  8. Identifier (y)

После этого происходит «разворачивание» стека (exit-фаза), если используются exit-обработчики.

Selector API и расширенный обход

Помимо прямого перечисления типов узлов ESLint поддерживает CSS-подобные селекторы AST:

"CallExpression Identifier"

или:

"FunctionDeclaration > BlockStatement"

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

Это добавляет дополнительный слой:

  • базовый обход AST
  • проверка селекторов
  • вызов обработчиков

Множественные правила и общий обход

Ключевой момент архитектуры ESLint — AST обходится один раз для всех правил.

Вместо:

  • отдельного обхода для каждого правила

используется:

  • единый traverser
  • множество подписчиков

Это снижает сложность с O(R × N) до O(N), где:

  • R — количество правил
  • N — количество узлов

Каждое правило лишь «подписывается» на интересующие типы узлов.

Обход и области видимости

Во время traversal ESLint параллельно строит scope tree:

  • global scope
  • function scope
  • block scope (let/const)

Каждый узел может создавать новую область видимости.

При входе в FunctionDeclaration создаётся новый scope, который наследует родительский. Это позволяет правилам анализировать:

  • использование переменных
  • shadowing
  • undefined references

AST обход и анализ scope тесно связаны, но реализованы как отдельные проходы поверх одной структуры.

Механизм enter/exit и управление состоянием

Двойной проход по узлу (enter/exit) позволяет строить сложные состояния.

Пример:

  • enter → фиксируется начало блока
  • обход детей → собирается информация
  • exit → выполняется финальная проверка

Это особенно важно для правил:

  • проверки порядка импортов
  • анализа вложенных условий
  • контроля сложности выражений

Обработка изменений AST

Некоторые правила могут модифицировать AST (через ESLint fixer API). Однако traversal engine не пересчитывает дерево мгновенно.

Процесс выглядит так:

  1. обход AST
  2. накопление фиксов
  3. применение изменений после завершения обхода
  4. повторный запуск при необходимости

Это исключает нестабильность traversal во время модификации структуры.

Специфика обхода разных типов узлов

Разные конструкции JavaScript приводят к разной глубине и форме обхода:

Условные конструкции

IfStatement создаёт ветвление, но обход остаётся линейным: сначала test, затем consequent, затем alternate.

Выражения

CallExpression имеет переменное количество аргументов, поэтому visitor keys включают массив arguments.

Функции

Функции всегда создают новый поддеревянный scope, что увеличивает глубину traversal.

Литералы

Literal — конечный узел, traversal не продолжается.

Стабильность порядка обхода

Порядок посещения узлов строго детерминирован:

  • всегда сверху вниз
  • всегда слева направо (по AST-структуре)
  • всегда с учётом visitor keys

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

Связь AST обхода и диагностики

Каждый раз, когда обработчик вызывает context.report, он делает это в контексте текущего узла.

ESLint сохраняет:

  • ссылку на узел
  • диапазон в исходном коде
  • сообщение диагностики

Таким образом, обход AST — это не просто навигация по структуре, а основа для формирования статического анализа и точек диагностики.

Итоговая модель взаимодействия компонентов

Обход AST в ESLint можно представить как конвейер:

  • parser формирует AST
  • visitor keys определяют структуру обхода
  • traverser выполняет DFS
  • rules подключаются как наблюдатели
  • scope анализ дополняет структуру
  • SourceCode связывает узлы с текстом
  • reporter фиксирует результаты анализа

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

Оглавление