Идеальный 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
  }

  def buildFoldToken(start: RScanToken): RScanToken = {
    val (token, list) = createFoldBlockBody(
      mutable.MutableList[RScanToken]()
        ++ List(start.asInstanceOf[RScanToken])
    )
    val result = new RScanToken(path, _tokenFactorySourcePair, foldBlock, Lexer.DEFAULT_TOKEN_CHANNEL, start.getStartIndex, token.getStopIndex)
    result.setLine(start.getLine)
    result.setCharPositionInLine(start.getCharPositionInLine)
    result.setFoldedTokens(list)
    result
  }

  private def createFoldBlockBody(list: mutable.MutableList[RScanToken]): (RScanToken, mutable.MutableList[RScanToken]) = {
    var current: RScanToken = null
    while (current == null || current.getType != Token.EOF && current.getType != foldClose) {
      current = nextToken().asInstanceOf[RScanToken]
      list += current
    }
    if (current.getType == Token.EOF)
      throw new IllegalStateException()
    (current, list)
  }

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

startJavaScript 
    :   HashBangLine? jsFileBody? EOF
    ;

startFoldBlock
   :   block EOF
   ;

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

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

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

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

Файл	Размер, кб	До оптимизации, мс	После оптимизации, мс
normalize-and-load-metadata.js	10	1839	1372
rewrite-live-references.js	8	899	528
dom.umd.min.js	130	43852	6607
react.pure.umd.min.js	139	51668	6495
tsserver.js	8151	362857	117787

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

Запуск осуществлялся на машине с 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), при этом иметь возможность сохранять на диск в сериализованном виде все объекты, а так же юнит-тестировать части инструмента.