Использование 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), при этом иметь возможность сохранять на диск в сериализованном виде все объекты, а так же юнит-тестировать части инструмента.
KvanTTT
Можете вкратце рассказать, что из себя представляет ваш SAST, какие уязвимости
находит, и почему он идеальный?
Расскажите подробней, как это сворачивается в один токен? Из статьи и исходников я так этого и не понял. Вы пользуйтесь тем, что ANTLR лексер контекстно-свободный, как и парсер, что дает возможность задавать рекурсивные токены? Примерно так:
Насколько понял, вы формируете свое представление для использования на последующих этапах, а не используете дефолтное ANTLR дерево разбора? Если так, то мне кажется, что если не строить дерево по-умолчанию, т.е. устанавливать
BuildParseTree = false
, а в Listener методах строить свое, то результат по памяти получился бы не особо хуже. Да и грамматика упростилась — не пришлось бы в каждом блоке прописывать код для создания конкретного узла.lastrix Автор
Добавил в статью код, вообще можно вот тут посмотреть: лексер
Предлагаю самостоятельно разобраться, почему эта свертка будет работать быстрее, чем правило, написанное на ANTLR, а так же почему то, что вы предлагаете не будет работать.
Без холиваров.
Грамматика не станет проще, вы пытаетесь смотреть на частности, не увидев всю картину, причем даже в том участке проекта, который был раскрыт на гитхабе — уже можно увидеть причину, почему строится собственное дерево.
AST — это абстрактное синтаксное дерево подходящее для любого, у чего есть синтаксис. Языки разработки — более конкретное множество, поэтому те операции, что создаются в обход ANTLR — имеют более строгие ограничения, чем обычный AST. При этом весь вывод уже имеет многочисленные маркировки и преобразования, из-за которых потом обработка будет проходить быстрее.
Если вы посмотрите, как например выглядит декларация переменной, то увидите, что будет что-то такое:
В будущем работать именно с такими структурами будет куда как проще, так же как и юнит-тестировать саму грамматику и всякие штуки для обработки такого сырого документа.
Я предлагаю вам все же посмотреть проект и убедится, что то, что вы сейчас говорите не позволит экономить память. Попробуйте закоментировать вот эту строку, найти файл на 130+ кб и запустить анализ с -Xmx128m. Чудеса — правда? Памяти почему-то потребляется не столько же.
PS можно свертки (такие же как в статье, а не то, что вы написали в виде правила) реализовать и с листенерами/визиторами, просто будете ловить напрямую токен FoldBlock и обрабатывать его другим способом. Но это долго и много мороки, сложно тестировать, вариант с кодом непосредственно в грамматике гораздо лучше.
Вопрос вам: сколько времени нужно вашему анализатору Positive Tech, что бы получить AST для tsserver.js? Можно приблизительно. Достаточно измерить время между началом работы начального правила и его окончания.
KvanTTT
Холивар начали вы, употребив слово "идеальный" в заголовке. Ничего идеального не существует, тем более в сфере статического анализа, включая и наши анализаторы от "Positive Tech". Либо быстро, либо качественно.
А я где-то спрашивал зачем строится собственное? Если вы так поняли мои слова, то извините за сумбурное изложение.
Мы для этого используем таблицу типов, которая отображается на AST. Но это тема уже для другого топика.
Позволяет — я об этом не так давно писал в компиляторном чате в Telegram.
Мы парсим PL/SQL файл в 900К строк кода (30 Мб) примерно за 12 секунд при условии, что используется быстрый SLL режим. При этом затрачивается 1 Гб оперативной памяти, 99% из которых — наше внутреннее представление UST (проверял профилировщиком). Его можно оптимизировать, но сейчас не вижу в этом особого смысла, т.к. такие файлы редкие. Т.е. все ANTLR объекты в основном отсеиваются в первом поколении, а это быстро.
Вот график CPU и Memory traffic из Process Hacker:
Сам файл выложить не могу, т.к. он, увы, проприетарный. Может дойдут потом руки сгенерировать подобный.
В случае полного LL все намного печальней — примерно 11.5 минут на парсинг, т.е. почти в 60 раз медленней, а это уже неприлично долго. Это коррелирует с вашими советами из прошлой статьи.
А 130Кб — уж извините, но ни о чем.
А можно ссылку на этот файл для начала? Для парсинга JavaScript мы сейчас используем Esprima.NET — порт оригинального парсера Esprima на JavaScript. Но, боюсь, это не то, что вас интересует, т.к. работает он побыстрее ANTLR, правда не обладает такой же гибкостью, поддерживает не все синтаксические конструкции.
Когда-то использовали JavaScript грамматику, но натыкались как раз на файлы, где происходило переключение SLL -> LL, и парсинг сильно замедлялся. Примерно по минуте на 100Кб+. Да и то это не особо было критично, т.к. остальные стадии ядра работали не особо быстро. Возможно в будущем вернемся на ANTLR с учетом накопленного опыта.
lastrix Автор
Зависит от языка. Для PLSQL — действительно ни о чем, но в случае минифицированного javascript — это очень много. В распакованном виде будет 2 мб исходников с очень нетривиальной логикой внутри.
Видимо я неясно выразился.
Нет смысла сравнивать тогда универсальные решения и специализированные. Написать под конкретный язык можно и без ANTLR.
lastrix Автор
Переключение через эксепшн? Значит вы грамматику неправильно готовили. Впрочем я ее видел. Использовать в проде ее действительно нельзя. Она просто не работает, большая часть фичей стандарта не поддерживается. Надеятся на простые случаи — бессмысленно.
В общем советую вам отказываться от LL грамматик, они не могут работать быстро по определению.
KvanTTT
Насчет производительности — согласен, можно оптимизировать. С другой стороны, зачем использовать ANTLR 4, если ради парсера нужно сделать столько телодвижений (как у вас в JSParser.g4)? Можно же обойтись ANTLR 3 или вообще свой парсер написать. Ради левой рекурсии?
Насчет поддержки фичей — откуда такая уверенность? Покрывать все случаи — бессмысленно, т.к. нужно те, которые как-то влияют на анализ. Например, обработка курсоров (отслеживание незакрытых). Также там много тестовых файлов, на которых парсинг производится без ошибок.
lastrix Автор
Много — это когда берешь базу из 17 тысяч файлов на JS — различные библиотеки, которые можно скачать всего лишь создав пустой проект react, а дальше получить только десяток ошибочных файлов. При этом ошибки из-за того, что какой-то умник пишет дженерики для массивов, которые в JS не поддерживаются, потому что файл препроцессируется какой-то либой.
Вот это тесты, а предложенные вами несколько файлов не позволят вам провести анализ реальных проектов.
ANTLR4 работает быстрее, чем ANTLR3.
Зачем писать свой парсер, если мне нужно универсальное решение, которое не потребует на каждый язык тратить килотонны времени?
Нужно такое решение, которое с минимальными затратами после написания грамматики даст возможность использовать весь остальной инструментарий сканера с минимальным тюнингом под специфику конкретного языка.
KvanTTT
За счет чего? Если ли тесты производительности?
А какие еще языки поддерживаете, помимо JavaScript?
lastrix Автор
Я еще с ANTLR 2.7.7 разработки делал, будучи студентом. И третью версию гонял. С ними очень много мороки и проблем, даже если они быстрее (что вряд ли), то смысла их использовать все равно нет — фичи не поддерживаются необходимые мне.
TypeScript, через него массу метаданных можно собрать, которые очень нужны в JavaScript. По сути сейчас пытаться делать SAST для JavaScript, не делая параллельно поддержку для TypeScript — все равно что выкидывать деньги на ветер.
В MVP еще будет какой-нибудь язык запросов для БД, MySql или Postgres. Пока не брался. Нужно довести с первыми двумя до нужной кондиции и уже после браться за запросы.
Кстати TypeScript парсер тоже будет публиковаться, потому что на нем лучше всего показывать особенности модели R, только не скоро это будет и по частям.
KvanTTT
Кстати, а имеет ли смысл анализировать все минифицированные библиотеки? По крайней мере их можно проанализировать один раз, а дальше использовать закешированный результат.
Я рад, что у вас хватает времени на разработку оптимизированной грамматики. К сожалению, порой нет времени и на это.
lastrix Автор
Это не всегда возможно, и есть требование анализировать все зависимости на каждом анализе. Версии могут отличаться, даже если разница в одной функции — может повлиять на результат. Поэтому работать парсер должен на всем, а в случае минифицированных библиотек — обязательно, так как там набито куча всего и из-за одной ошибки можно много чего потерять.
Суммарно на грамматики JS и TS ушло примерно 80 человекочасов — не очень много. Если пишешь код внутри грамматики и можешь ее юнит-тестировать — сильно ускоряет процесс разработки и анализа.
Это всего лишь вопрос инструментария, который вы написали для себя (потому что с формальными грамматиками мало кто работает — соответственно все что есть — кактус). А так же понимания функционирования библиотек, которые вы используете.