Идеальный SAST. Парсер

Цикл статей посвящен описанию оптимального подхода для реализаций инструментов статического анализа кода, рассчитан на специалистов. Целью работы являются подходы, модели и методики для получения максимальной производительности инструмента при минимизации трудоемкости разработки и поддержки/изменения инструмента. В данной статье рассматривается способ ускорения работы парсера и снижения потребления памяти. Статья построена таким образом, что читатель прочел руководство написанное Терренсом Парром.

Использование ANTLR на полную

ANTLR наиболее хорошо работает примерно в пределах 1 кб — 10 кб, файлы большего размера не будут анализироваться данной библиотекой с максимальным быстродействием. Так же отладка работы на больших файлах становится почти невозможной. Основной причиной, по которой необходимо держать объем входных данных для парсера в заданных пределах — алгоритмы прогнозирования ветвлений для ANTLR активно используют стек, соответственно любыми способами необходимо избавляться от циклов в грамматике, когда одно правило вызывает само себя через множество других правил в том числе с определенными условиями активации такой связи, рассмотрим на примере:

var f = fun a(b) { b = 10; return b; }

Данный код можно описать следующей грамматикой:

start: stmt* EOF; stmt: varDecl | funDecl | expr ';' | 'return' expr ';'; varDecl: 'var' id '=' expr; expr: id ('=' expr)? | number; funDecl: 'fun' id '(' id* ')' '{' stmt* '}'

Легко заметить, что stmt вызывается внутри правила funDecl, что формирует цикл, который в реальных приложениях может привести к тому, что файл в 100 кб потребует хипа на 4 ГБ ОЗУ для максимальной производительности, а то и вовсе возможности работать, что является совершенно недопустимой ситуацией.

Одним из способов для преодоления такого недостатка является добавление специальных модификаций в процессе создания токенов, а именно — свертка блоков {} в токен, с обработкой этих токенов позднее в новом парсере, на вход которого будут переданы свернутые токены.

Для этого в ANTLR имеется возможность переопределить метод org.antlr.v4.runtime.Lexer#nextToken лексера, где можно реализовать функционал свертки:

  override def nextToken(): Token = super.nextToken() match {       case x: RScanToken if x.getType == foldOpen => buildFoldToken(x)       case x: Token => x  }

Грамматика должна быть дополнена:

startJavaScript      :   HashBangLine? jsFileBody? EOF     ;  startFoldBlock    :   block EOF    ;  block     :   LBRACE stmtList? RBRACE     |   FoldBlock  // сохраняем информацию в специальный узел, // что бы потом вызвать startFoldBlock     ; 

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

Скорость обработки вырастает от 2 до 10 раз, особенно заметна разница становится на минифицированных js файлах.

Влияние на работу ANTLR предлагаемой оптимизации на примере нескольких javascript файлов:

Без оптимизации работа осуществляется в один поток, с оптимизацией, если возможно, то обработка параллелится.

Запуск осуществлялся на машине с 64 гб ОЗУ, Intel® Core(TM) i7-9700K CPU @ 3.60GHz, OpenJDK Runtime Environment AdoptOpenJDK (build 11.0.4+11).

Ключи запуска JVM: -Xmx4G -XX:+UseG1GC -XX:MaxHeapFreeRatio=30 -XX:MinHeapFreeRatio=10
Для файла tsserver.js ключ -Xmx32G, при этом потребление памяти достигло 22 гб! В то время как минифицированные файлы до 200 кб с оптимизацией анализируются с лимитом хипа в 128 мб в параллельном режиме без необходимости сборщику мусора оказывать нагрузку на процессор, максимум 2%!

Профилирование

ANTLR поддерживает профилирование работы парсера/лексера в рантайме, что бы включить, нужно вызвать метод: org.antlr.v4.runtime.Parser#setProfile до выполнения каких-либо правил. Далее можно получить всю информацию, например таким способом:

    private def printProfileInfo(parser: AbstractRScanParser, tokenStream: TokenStream): Unit = {       // do the actual parsing       val parseInfo = parser.getParseInfo       val atn = parser.getATN       for (di <- parseInfo.getDecisionInfo if di.ambiguities.size() > 0) {         val ds = atn.decisionToState.get(di.decision)         val ruleName = parser.ruleName(ds.ruleIndex)         log.debug("Ambiguity in rule '" + ruleName + "' -> {}", di)         log.debug("=========================")         log.debug(tokenStream.getText)         log.debug("=========================")       }     }

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

Заключение

В данной статье предложен метод оптимизации работы формальных грамматик, реализованных с помощью библиотеки ANTLR, хотя сам подход можно попытаться применить и к другим библиотекам. Особенностью оптимизации является уменьшение количества переходов вперед для валидации входного потока токенов. Так же она позволяет анализировать большие файлы (более 1 мб) при затратах памяти в 512 мб при однопоточной обработке, в то время как отсутствие оптимизации будет требовать в 50 раз больше памяти для быстрой работы с использованием той же самой грамматики.

Исходный код доступен на гитхабе. Данный проект сделан для демонстрации работы оптимизации. Проект упрощен максимально, начать изучение рекомендуется в класса GrammarTester, для него сделана конфигурация запуска, вам останется прописать только путь к папке с входными данными. Обратите внимание на ключ rscan.tester.cache.dir, в эту папку будут писаться временные файлы, успешный анализ файла закрепляется в этой папке и не позволит парсеру анализировать его второй раз — удобно для исправления ошибок. В данный момент грамматика протестирована на 17 тыс файлах из node_modules, создаваемого для базового приложения react. Игнорировались только вложенные node_modules.

В следующей статье будут рассмотрены варианты организации данных и модель R (Отражение) для оптимального представления исходных данных в виде объектов анализа с минимальным потреблением памяти, возможностью реализовать алгоритмы поиска элементов со сложностью О(1), при этом иметь возможность сохранять на диск в сериализованном виде все объекты, а так же юнит-тестировать части инструмента.