Кстати, а имеет ли смысл анализировать все минифицированные библиотеки? По крайней мере их можно проанализировать один раз, а дальше использовать закешированный результат.
Это не всегда возможно, и есть требование анализировать все зависимости на каждом анализе. Версии могут отличаться, даже если разница в одной функции — может повлиять на результат. Поэтому работать парсер должен на всем, а в случае минифицированных библиотек — обязательно, так как там набито куча всего и из-за одной ошибки можно много чего потерять.
Я рад, что у вас хватает времени на разработку оптимизированной грамматики. К сожалению, порой нет времени и на это.
Суммарно на грамматики JS и TS ушло примерно 80 человекочасов — не очень много. Если пишешь код внутри грамматики и можешь ее юнит-тестировать — сильно ускоряет процесс разработки и анализа.
Это всего лишь вопрос инструментария, который вы написали для себя (потому что с формальными грамматиками мало кто работает — соответственно все что есть — кактус). А так же понимания функционирования библиотек, которые вы используете.
Я еще с ANTLR 2.7.7 разработки делал, будучи студентом. И третью версию гонял. С ними очень много мороки и проблем, даже если они быстрее (что вряд ли), то смысла их использовать все равно нет — фичи не поддерживаются необходимые мне.
А какие еще языки поддерживаете, помимо JavaScript?
TypeScript, через него массу метаданных можно собрать, которые очень нужны в JavaScript. По сути сейчас пытаться делать SAST для JavaScript, не делая параллельно поддержку для TypeScript — все равно что выкидывать деньги на ветер.
В MVP еще будет какой-нибудь язык запросов для БД, MySql или Postgres. Пока не брался. Нужно довести с первыми двумя до нужной кондиции и уже после браться за запросы.
Кстати TypeScript парсер тоже будет публиковаться, потому что на нем лучше всего показывать особенности модели R, только не скоро это будет и по частям.
Много — это когда берешь базу из 17 тысяч файлов на JS — различные библиотеки, которые можно скачать всего лишь создав пустой проект react, а дальше получить только десяток ошибочных файлов. При этом ошибки из-за того, что какой-то умник пишет дженерики для массивов, которые в JS не поддерживаются, потому что файл препроцессируется какой-то либой.
Вот это тесты, а предложенные вами несколько файлов не позволят вам провести анализ реальных проектов.
ANTLR4 работает быстрее, чем ANTLR3.
Зачем писать свой парсер, если мне нужно универсальное решение, которое не потребует на каждый язык тратить килотонны времени?
Нужно такое решение, которое с минимальными затратами после написания грамматики даст возможность использовать весь остальной инструментарий сканера с минимальным тюнингом под специфику конкретного языка.
Не могу ничего сказать по поводу PLSQL, потому что не занимался им и пока на него нет времени.
То что известно — синтаксис у него простой, в большинстве своем работать нужно именно с запросами, а у них не бывает перестановок или чего-то в таком духе, жесткий формат.
То что есть возможность писать хранимые процедуры — это отдельная тема и их очень легко парсить отдельно. Или у вас есть процедуры на 1000 строк?
Как бы выше я писал для 30 Мб кода, это в 300 раз больше. Ваше JS представление в этом случае сколько будет в памяти занимать?
8 мб умещается в 512 мб хипа без проблем — как раз tsserver.js.
Грамматика ANTLR для JavaScript отличается по сложности в разы для PLSQL и сравнивать их бессмысленно.
Я уже не говорю о том, что для PLSQL можно сделать разбиение на небольшие куски кода и обработку их в ANTLR вообще параллельно. Для JS такое не всегда возможно сделать.
FoldToken как минимум такой оптимизацией и является
Есть другие оптимизации для работы грамматики и ANTLR, а так же генерации объектов, уменьшения потребления ресурсов объектами парсера и т.д.
Есть еще способы уменьшения lookahead ANTLR. Причем они же очевидны! Неужели не умеете делить входной файл на независимые блоки и парсить отдельно?
function a(){}
function b(){}
Такие штуки можно парсить отдельно и скорость будет выше, другой вопрос, что сделать такое разделение корректно с точки зрения синтаксиса будет непросто =)
Из ANTLR можно еще 30-40% производительности выжать без злобных хаков, но влоб кидать этой библиотеке мегабайты исходных кодов — бред.
Когда-то использовали JavaScript грамматику, но натыкались как раз на файлы, где происходило переключение SLL -> LL,
Переключение через эксепшн? Значит вы грамматику неправильно готовили. Впрочем я ее видел. Использовать в проде ее действительно нельзя. Она просто не работает, большая часть фичей стандарта не поддерживается. Надеятся на простые случаи — бессмысленно.
В общем советую вам отказываться от LL грамматик, они не могут работать быстро по определению.
Зависит от языка программирования. Вы бы еще сравнили 100 кб ассемблерного кода и 100 кб С++.
В два раза медленней — это не на порядок.
Написано же — минимум. И я не делал оптимизаций специальных для грамматики, процесса работы и прочего.
По памяти гарантированно на порядок лучше, так как вы же сами писали, что требует 1 ГБ ОЗУ для 100 кб вашего кода. Сравните это с 128 мб. Причем я еще и выгружать данные на диск в процессе анализа могу :D В том числе в процессе резолва — маппинга типов на исходный код.
Поддерживается ли у вас межпроцедурный и межфайловый taint анализ?
Модель R для того и разрабатывалась, вернее это минимум, что должно быть. Больше говорить не стану. Межпроцедурным и межфайловым анализом как раз 5 лет и занимался, так что с этим проблем точно не будет =) Цель покрупнее идет, именно поэтому все что отвечает за SAST должно быть "идеальным". Ресурсы нужны для других целей.
Зависит от языка. Для PLSQL — действительно ни о чем, но в случае минифицированного javascript — это очень много. В распакованном виде будет 2 мб исходников с очень нетривиальной логикой внутри.
Видимо я неясно выразился.
А можно ссылку на этот файл для начала? Для парсинга JavaScript мы сейчас используем Esprima.NET — порт оригинального парсера Esprima на JavaScript. Но, боюсь, это не то, что вас интересует, т.к. работает он побыстрее ANTLR, правда не обладает такой же гибкостью, поддерживает не все синтаксические конструкции.
Нет смысла сравнивать тогда универсальные решения и специализированные. Написать под конкретный язык можно и без ANTLR.
а на сколько оно там памяти потребляет и как быстро бегает.
Парсер в 8 потоков все файлы меньше 10 кб парсит при 128 мб хипа, можно ужать до 64 мб, работать будет, но кроме парсера есть еще штуки, которые память по умолчанию щадить не могут.
Если речь про большие файлы, то при однопоточном анализе, минифицированный вендор.js на 100-130 кб можно запихнуть в те же рамки, просто сборщик мусора будет работать больше.
По быстродействию скажу, что текущие универсальные решения (не специализированные, как например в браузере), будут работать минимум в 2 раза медленнее, чем rscan, во всяком случае уж точно быстрее Positive Tech =) Сложно быть медленее…
В целом планирую, что 90% проектов будут taint-анализироваться с хипом в 1 гб, этого должно быть достаточно, да и разработчику будет удобнее пользоваться непосредственно в процессе разработки, и видеть проблемные места. Насколько мне известно, уж 4 гб ОЗУ у разработчиков как правило есть, значит и для SAST место найдется. Для всяких мелкосервисов и онлайн-магазов самое то!
А почему вас интересуют такие вопросы? Спиён? =)
Все же лучше задавать вопросы по теме статьи, мы же не rscan в целом обсуждаем сейчас, а конкретно оптимизацию ANTLR. Есть ли у вас по этой теме вопросы?
Добавил в статью код, вообще можно вот тут посмотреть: лексер
Предлагаю самостоятельно разобраться, почему эта свертка будет работать быстрее, чем правило, написанное на ANTLR, а так же почему то, что вы предлагаете не будет работать.
Можете вкратце рассказать, что из себя представляет ваш SAST, какие уязвимости
находит, и почему он идеальный?
Без холиваров.
Да и грамматика упростилась — не пришлось бы в каждом блоке прописывать код для создания конкретного узла.
Грамматика не станет проще, вы пытаетесь смотреть на частности, не увидев всю картину, причем даже в том участке проекта, который был раскрыт на гитхабе — уже можно увидеть причину, почему строится собственное дерево.
AST — это абстрактное синтаксное дерево подходящее для любого, у чего есть синтаксис. Языки разработки — более конкретное множество, поэтому те операции, что создаются в обход ANTLR — имеют более строгие ограничения, чем обычный AST. При этом весь вывод уже имеет многочисленные маркировки и преобразования, из-за которых потом обработка будет проходить быстрее.
Если вы посмотрите, как например выглядит декларация переменной, то увидите, что будет что-то такое:
LANG at /ex.js[1:0-1:49]
Language: JavaScript
Children:
RAW_DECL_LOCAL at /ex.js[1:12-1:48]
Children:
NAME at /ex.js[1:12-1:33]
Children:
UNRESOLVED_ID at /ex.js[1:12-1:33]
Name: regexUnnecessaryIndex
MODIFIERS at /ex.js[1:12-1:48]
Modifiers: const
INIT at /ex.js[1:36-1:48]
В будущем работать именно с такими структурами будет куда как проще, так же как и юнит-тестировать саму грамматику и всякие штуки для обработки такого сырого документа.
Я предлагаю вам все же посмотреть проект и убедится, что то, что вы сейчас говорите не позволит экономить память. Попробуйте закоментировать вот эту строку, найти файл на 130+ кб и запустить анализ с -Xmx128m. Чудеса — правда? Памяти почему-то потребляется не столько же.
PS можно свертки (такие же как в статье, а не то, что вы написали в виде правила) реализовать и с листенерами/визиторами, просто будете ловить напрямую токен FoldBlock и обрабатывать его другим способом. Но это долго и много мороки, сложно тестировать, вариант с кодом непосредственно в грамматике гораздо лучше.
Вопрос вам: сколько времени нужно вашему анализатору Positive Tech, что бы получить AST для tsserver.js? Можно приблизительно. Достаточно измерить время между началом работы начального правила и его окончания.
Искать хоть "что-то" в том, что не может работать по определению — бессмысленная работа и демонстрация первичных половых признаков будет не так уж глупо выглядеть.
особенно если используется C++.
Достаточно иметь конфигурацию препроцессора и информацию о том, какое окружение необходимо для сборки. VCBuild — просто кладезь веревок достаточной длины и прочих интерполяций с матерыми выражениями.
Не увидел чего-то сложного перейдя по вашей ссылке.
То что понять что есть что на уровне лексера не выйдет, да и у парсера будут проблемы — да.
Но зачем идти по извилистой земляной дорожке в поле, если рядом есть шоссе?
Советую попробовать другие варианты работы с исходными кодами. Особенно это касается AST, он вам не нужен. UST — ближе, но все еще не то.
А есть ли у вас какой-нибудь опыт по обработке препроцессорных директив?
Писал, правда 5 дней было потрачено на него и, как говорил Костя, пару багов исправил, уже после моего увольнения. Соответствие спецификации 2011 года — 100%, но есть там нюансы со склейкой токенов, видимо на них баги и были.
Есть небольшое расхождение в части переноса строк, в GNU они уходят, в спеке говорится, что должны оставаться. Я про макросы и параметры.
Есть два способа — делать сложные стейтменты (когда у стейтмента может быть предок), либо же результаты макро-обработки мэппить на координаты исходного токена (или токенов). Что бы избежать наложения адресов советую добавить virtual — тогда каждый новый токен будет иметь свой адрес при любых раскладах. Указывать будет на точку применения макроса.
Вообще это отдельная тема и обсуждать ее тут не вижу смысла.
Кстати, по поводу очистки ATN. Сам создатель оптимизированного ANTLR C# рантайма рекомендует переинициализировать ATN, если нужно снизить потребление памяти.
Основное потребление памяти из-за необходимости парсера делать слишком долгие lookahead, именно из-за него получаются хипы на 4 ГБ забитые под завязку. С ATN память будет медленно течь, особую проблему быстродействия не доставляет.
Были реальные исходники, где файлы внезапно обрывались, из-за этого SLL переключался на медленный LL, что приводило к тормозам. Ну и да — есть требование в идеале парсить код с любыми ошибками, включая синтаксические.
вы все равно в этом коде ничего не сможете получить, зачем тогда парсить?
В случае синтаксических ошибок в SLL режиме лучше делать сводку о причинах и просить пользователя отправить сообщение разработчику.
В LL режиме нет смысла, разве что вы пишете IDE и неплохо было бы давать адекватную подсветку каждый раз.
В Java можно это сделать, но проще пропатчить генерируемый класс, чем везде выставлять такую штуку, тем более что в C# достаточно 2 аргументов, а в Java их надо 4. Впрочем попробую, может оно и в правду лучше работать будет.
На движке абстрактной интерпретации? Когда это было? Там ANTLR и не используется :)
Летом отчет по вебгоату присылали. Версию я не помню, осилить HASP ваш не смог :D
А как парсить файлы, в которых есть синтаксические ошибки и их нужно максимально корректно обрабатывать? Т.е. либо добавлять токен, либо удалять токен, либо пропускать последовательность до синхронизирующего токена (типа точки с запятой). Я не пробовал как работает SLL со стандартной стратегией обработки ошибок.
А зачем парсить файлы с синтаксическими ошибками?
Если это какая-то мелкая ошибка, то тем более фолдинг — лучшее решение, потому что потеряется только фрагмент, хотя достаточно требовать, что бы код компилировался родной утилитой, тогда проблем не будет.
SLL хорошо работает на компилируемых файлах. Мусор отправлять на анализ тоже такое себе дело.
Или у вас парсер позволяет в txt файле java-код или какой-нибудь еще?
Неправильно выразился, парсер, если ему отдавать сразу все работает очень медленно.
А заменить в джаве final static нельзя (на самом деле можно, но это будет слабоумие и отвага).
Как это работает, как парсится. Можно поподробней?
override def nextToken(): Token = {
if (hasEnqueuedTokens) dequeueToken
else super.nextToken() match {
case x: RScanToken if x.getType == foldOpen => buildFoldToken(x)
case x: Token => x
}
}
buildFoldToken рекурсивно собирает все токены начиная с { и по }, создает для них токен с адресом от { по }, внутри имеет список токенов, которые он поглотил, включая такие же фолды.
А уже в ANTLR идет так:
В итоге и обычный режим работает, и оптимизация тоже пашет. Парсить токены внутри FoldBlock можно когда потребуется. А главное, что lookahead убивается на корню, потому что он не нужен для случаев, когда альтернативы быть не может, но ANTLR честно их ищет.
А какие языки? :)
Java.
В чем посредственность на конкретных примерах? Было бы интересно узнать, как это можно избежать. Ну и для этого они и открытые, чтобы сообщество могло их дорабатывать.
Они не SLL. Запускаешь эти грамматики на тестовом множестве (2000+ файлов), так половина минимум падает с ошибками.
Увы, но предложенное вами решение крайне медленное. Сброс кеша в джаве таким же способом не удастся реализовать, особенно, если есть многопоточный анализ. Возможно в C# как-то по другому реализованы статики.
Дано: грамматика JavaScript 2019, на вход посылаем файл в 127 кб минифицированного кода — 38 секунд на обработку, 12% gc max. Без xmx4g запускать бессысленно.
Включаем упаковку блоков в токен (создается токен, в котором есть список токенов) — 12 секунд xmx64m дает 5% gc max, при xmx128m 1% gc max, парсим блоки в многопоточном режиме на 8 ядрах — 4 секунды. ATN создается на каждый новый инстанс парсера.
Поэтапная обработка — наше все
Если под поэтапностью вы понимаете разбор одного и того же файла разными парсерами, то да, но использовать AST, создаваемый ANTLR все равно не рекомендую, слишком много лишней информации.
Java, CSharp, Python, Php, JavaScript, TypeScript, C++, C, и многие другие языки достаточно просты, что бы сделать грамматику, которая будет работать без синтаксических ошибок в режиме SLL.
Вы что-то не так делаете в вашем парсере, что требуется включать такую фичу.
Впрочем я уже видел работу анализатора Positive Tech :D Воздержусь от критики.
Так сделано, например, в грамматике JavaScript.
Открытые грамматики реализованы крайне посредственно. Иногда можно встретить хорошее решение, но в общем случае лучше написать самому сразу SLL, чем давится ALL кактусом.
Для каждого пункта было бы неплохо добавить разъяснение и примеры кода как не надо и как надо (или наоборот, т.к. советы вредные). Особенно про ATN и SLL.
Будет отдельная статья, где объясню всю кухню работы с ANTLR4 на Java, данная статья была больше для того, что бы понять, есть ли интерес у людей к такой тематике.
override def nextToken(): Token =
if (hasEnqueuedTokens) dequeueToken
else if (templateMode) nextTokenTemplate
else nextTokenNonTemplate
private def nextTokenNonTemplate: Token = {
val token = _input.LA(1) match {
case '`' => parseTemplateLiteral
case _ => super.nextToken()
}
if (token.getChannel == Token.DEFAULT_CHANNEL)
lastToken = token
token
}
private def nextTokenTemplate: Token =
if (!insideTemplate) {
if (_input.LA(1) != '`')
throw new IllegalStateException("Template string must start with '`' character")
insideTemplate = true
val token = createToken(_input.index(), 1, templateLiteralDelimiter, Token.HIDDEN_CHANNEL)
templateStartToken()
token
} else if (_input.index() == closePosition) {
if (_input.LA(1) != '}')
throw new IllegalStateException("Close position is not at '}' character")
val token = createToken(_input.index(), 1, templateLiteralDelimiter, Token.HIDDEN_CHANNEL)
templateMiddleOrStopToken()
token
} else nextTokenNonTemplate
Это кусок кода для анализа TypeScript/JavaScript, гораздо выгоднее проанализировать собственными руками последовательность символов и сделать токен с шаблонной строкой, чем нагружать лексер, тем более, что в случае вложенности будут проблемы с анализом выражений. Для правила startTemplate токены TemplateLiteral* создавались не лексером, а руками. Код у правил удалил, потому что при просмотре превращается в кашу.
//////////////////////////////////////// Main Entry Points
startTypeScript
: typeScriptStmtList EOF
| EOF
;
//////////////////////////////////////// Secondary Entry Points
startTemplate
:
TemplateLiteralStart
// опционально, потому что TemplateLiteralStart может содержать окончание
(
expression[true,_yield,await]
(
TemplateLiteralMiddle
expression[true,_yield,await]
)*
TemplateLiteralStop
)?
EOF
;
parseTemplateString — находит индекс последнего символа шаблонной строки с учетом вложенности.
Уже после этот литерал парсится отдельно. Например вот так:
final def parse(): RLangOp = {
val result = parseInitial()
enqueue(result.folds ++ result.templates)
while (jobs.nonEmpty) {
val _j = Seq.empty ++ jobs
jobs.clear()
parseItems(_j)
}
result.op.asInstanceOf[RLangOp]
}
Внутри parseItems все folds, templates так же добавляются в очередь jobs
Полагаю, что с комментариями можно такую же штуку провернуть.
Должно быть что-то в таком духе у вас:
Если поиграетесь с режимами работы лексера (mode — его можно устанавливать до выполнения), то можно все в одном уместить, и с парсером так же удастся сделать.
Правила можно легко вызывать вот таким образом:
final def invokeRule[T](ruleName: String): T = resultOfRule[T](ruleName)
private def resultOfRule[T](ruleName: String): T =
resultField[T](getClass.getDeclaredMethod(ruleName).invoke(this))
private def resultField[T](value: AnyRef): T =
value.getClass.getDeclaredField("result").get(value).asInstanceOf[T]
Делаешь токен с новым типом, сохраняешь в него список токенов, регистрируешь каким-то образом токен, что бы можно было узнать о нем. Далее в местах, где есть блок, добавляешь альтернативу с новым типом токена. После анализа файла создаешь парсеры для сохраненных токенов и разбираешь их, пока не останется в регистре элементов. Лексер работает только один раз.
И вуаля, вместо 4 ГБ хипа хватает 128 мб.
Это не всегда возможно, и есть требование анализировать все зависимости на каждом анализе. Версии могут отличаться, даже если разница в одной функции — может повлиять на результат. Поэтому работать парсер должен на всем, а в случае минифицированных библиотек — обязательно, так как там набито куча всего и из-за одной ошибки можно много чего потерять.
Суммарно на грамматики JS и TS ушло примерно 80 человекочасов — не очень много. Если пишешь код внутри грамматики и можешь ее юнит-тестировать — сильно ускоряет процесс разработки и анализа.
Это всего лишь вопрос инструментария, который вы написали для себя (потому что с формальными грамматиками мало кто работает — соответственно все что есть — кактус). А так же понимания функционирования библиотек, которые вы используете.
Я еще с ANTLR 2.7.7 разработки делал, будучи студентом. И третью версию гонял. С ними очень много мороки и проблем, даже если они быстрее (что вряд ли), то смысла их использовать все равно нет — фичи не поддерживаются необходимые мне.
TypeScript, через него массу метаданных можно собрать, которые очень нужны в JavaScript. По сути сейчас пытаться делать SAST для JavaScript, не делая параллельно поддержку для TypeScript — все равно что выкидывать деньги на ветер.
В MVP еще будет какой-нибудь язык запросов для БД, MySql или Postgres. Пока не брался. Нужно довести с первыми двумя до нужной кондиции и уже после браться за запросы.
Кстати TypeScript парсер тоже будет публиковаться, потому что на нем лучше всего показывать особенности модели R, только не скоро это будет и по частям.
Много — это когда берешь базу из 17 тысяч файлов на JS — различные библиотеки, которые можно скачать всего лишь создав пустой проект react, а дальше получить только десяток ошибочных файлов. При этом ошибки из-за того, что какой-то умник пишет дженерики для массивов, которые в JS не поддерживаются, потому что файл препроцессируется какой-то либой.
Вот это тесты, а предложенные вами несколько файлов не позволят вам провести анализ реальных проектов.
ANTLR4 работает быстрее, чем ANTLR3.
Зачем писать свой парсер, если мне нужно универсальное решение, которое не потребует на каждый язык тратить килотонны времени?
Нужно такое решение, которое с минимальными затратами после написания грамматики даст возможность использовать весь остальной инструментарий сканера с минимальным тюнингом под специфику конкретного языка.
Не могу ничего сказать по поводу PLSQL, потому что не занимался им и пока на него нет времени.
То что известно — синтаксис у него простой, в большинстве своем работать нужно именно с запросами, а у них не бывает перестановок или чего-то в таком духе, жесткий формат.
То что есть возможность писать хранимые процедуры — это отдельная тема и их очень легко парсить отдельно. Или у вас есть процедуры на 1000 строк?
8 мб умещается в 512 мб хипа без проблем — как раз tsserver.js.
Грамматика ANTLR для JavaScript отличается по сложности в разы для PLSQL и сравнивать их бессмысленно.
Я уже не говорю о том, что для PLSQL можно сделать разбиение на небольшие куски кода и обработку их в ANTLR вообще параллельно. Для JS такое не всегда возможно сделать.
Есть другие оптимизации для работы грамматики и ANTLR, а так же генерации объектов, уменьшения потребления ресурсов объектами парсера и т.д.
Есть еще способы уменьшения lookahead ANTLR. Причем они же очевидны! Неужели не умеете делить входной файл на независимые блоки и парсить отдельно?
function a(){}
function b(){}
Такие штуки можно парсить отдельно и скорость будет выше, другой вопрос, что сделать такое разделение корректно с точки зрения синтаксиса будет непросто =)
Из ANTLR можно еще 30-40% производительности выжать без злобных хаков, но влоб кидать этой библиотеке мегабайты исходных кодов — бред.
Переключение через эксепшн? Значит вы грамматику неправильно готовили. Впрочем я ее видел. Использовать в проде ее действительно нельзя. Она просто не работает, большая часть фичей стандарта не поддерживается. Надеятся на простые случаи — бессмысленно.
В общем советую вам отказываться от LL грамматик, они не могут работать быстро по определению.
Зависит от языка программирования. Вы бы еще сравнили 100 кб ассемблерного кода и 100 кб С++.
Написано же — минимум. И я не делал оптимизаций специальных для грамматики, процесса работы и прочего.
По памяти гарантированно на порядок лучше, так как вы же сами писали, что требует 1 ГБ ОЗУ для 100 кб вашего кода. Сравните это с 128 мб. Причем я еще и выгружать данные на диск в процессе анализа могу :D В том числе в процессе резолва — маппинга типов на исходный код.
Модель R для того и разрабатывалась, вернее это минимум, что должно быть. Больше говорить не стану. Межпроцедурным и межфайловым анализом как раз 5 лет и занимался, так что с этим проблем точно не будет =) Цель покрупнее идет, именно поэтому все что отвечает за SAST должно быть "идеальным". Ресурсы нужны для других целей.
Зависит от языка. Для PLSQL — действительно ни о чем, но в случае минифицированного javascript — это очень много. В распакованном виде будет 2 мб исходников с очень нетривиальной логикой внутри.
Видимо я неясно выразился.
Нет смысла сравнивать тогда универсальные решения и специализированные. Написать под конкретный язык можно и без ANTLR.
Парсер в 8 потоков все файлы меньше 10 кб парсит при 128 мб хипа, можно ужать до 64 мб, работать будет, но кроме парсера есть еще штуки, которые память по умолчанию щадить не могут.
Если речь про большие файлы, то при однопоточном анализе, минифицированный вендор.js на 100-130 кб можно запихнуть в те же рамки, просто сборщик мусора будет работать больше.
По быстродействию скажу, что текущие универсальные решения (не специализированные, как например в браузере), будут работать минимум в 2 раза медленнее, чем rscan, во всяком случае уж точно быстрее Positive Tech =) Сложно быть медленее…
В целом планирую, что 90% проектов будут taint-анализироваться с хипом в 1 гб, этого должно быть достаточно, да и разработчику будет удобнее пользоваться непосредственно в процессе разработки, и видеть проблемные места. Насколько мне известно, уж 4 гб ОЗУ у разработчиков как правило есть, значит и для SAST место найдется. Для всяких мелкосервисов и онлайн-магазов самое то!
А почему вас интересуют такие вопросы? Спиён? =)
Все же лучше задавать вопросы по теме статьи, мы же не rscan в целом обсуждаем сейчас, а конкретно оптимизацию ANTLR. Есть ли у вас по этой теме вопросы?
Все же java есть, в статье удалял код из грамматик, потому что по какой-то причине хабра-парсер превращает всю статью в код.
Добавил в статью код, вообще можно вот тут посмотреть: лексер
Предлагаю самостоятельно разобраться, почему эта свертка будет работать быстрее, чем правило, написанное на ANTLR, а так же почему то, что вы предлагаете не будет работать.
Без холиваров.
Грамматика не станет проще, вы пытаетесь смотреть на частности, не увидев всю картину, причем даже в том участке проекта, который был раскрыт на гитхабе — уже можно увидеть причину, почему строится собственное дерево.
AST — это абстрактное синтаксное дерево подходящее для любого, у чего есть синтаксис. Языки разработки — более конкретное множество, поэтому те операции, что создаются в обход ANTLR — имеют более строгие ограничения, чем обычный AST. При этом весь вывод уже имеет многочисленные маркировки и преобразования, из-за которых потом обработка будет проходить быстрее.
Если вы посмотрите, как например выглядит декларация переменной, то увидите, что будет что-то такое:
В будущем работать именно с такими структурами будет куда как проще, так же как и юнит-тестировать саму грамматику и всякие штуки для обработки такого сырого документа.
Я предлагаю вам все же посмотреть проект и убедится, что то, что вы сейчас говорите не позволит экономить память. Попробуйте закоментировать вот эту строку, найти файл на 130+ кб и запустить анализ с -Xmx128m. Чудеса — правда? Памяти почему-то потребляется не столько же.
PS можно свертки (такие же как в статье, а не то, что вы написали в виде правила) реализовать и с листенерами/визиторами, просто будете ловить напрямую токен FoldBlock и обрабатывать его другим способом. Но это долго и много мороки, сложно тестировать, вариант с кодом непосредственно в грамматике гораздо лучше.
Вопрос вам: сколько времени нужно вашему анализатору Positive Tech, что бы получить AST для tsserver.js? Можно приблизительно. Достаточно измерить время между началом работы начального правила и его окончания.
речь не про "падать", а про игнорирование файла.
Искать хоть "что-то" в том, что не может работать по определению — бессмысленная работа и демонстрация первичных половых признаков будет не так уж глупо выглядеть.
Достаточно иметь конфигурацию препроцессора и информацию о том, какое окружение необходимо для сборки. VCBuild — просто кладезь веревок достаточной длины и прочих интерполяций с матерыми выражениями.
Не увидел чего-то сложного перейдя по вашей ссылке.
То что понять что есть что на уровне лексера не выйдет, да и у парсера будут проблемы — да.
Но зачем идти по извилистой земляной дорожке в поле, если рядом есть шоссе?
Советую попробовать другие варианты работы с исходными кодами. Особенно это касается AST, он вам не нужен. UST — ближе, но все еще не то.
Писал, правда 5 дней было потрачено на него и, как говорил Костя, пару багов исправил, уже после моего увольнения. Соответствие спецификации 2011 года — 100%, но есть там нюансы со склейкой токенов, видимо на них баги и были.
Есть небольшое расхождение в части переноса строк, в GNU они уходят, в спеке говорится, что должны оставаться. Я про макросы и параметры.
Есть два способа — делать сложные стейтменты (когда у стейтмента может быть предок), либо же результаты макро-обработки мэппить на координаты исходного токена (или токенов). Что бы избежать наложения адресов советую добавить virtual — тогда каждый новый токен будет иметь свой адрес при любых раскладах. Указывать будет на точку применения макроса.
Вообще это отдельная тема и обсуждать ее тут не вижу смысла.
Основное потребление памяти из-за необходимости парсера делать слишком долгие lookahead, именно из-за него получаются хипы на 4 ГБ забитые под завязку. С ATN память будет медленно течь, особую проблему быстродействия не доставляет.
вы все равно в этом коде ничего не сможете получить, зачем тогда парсить?
В случае синтаксических ошибок в SLL режиме лучше делать сводку о причинах и просить пользователя отправить сообщение разработчику.
В LL режиме нет смысла, разве что вы пишете IDE и неплохо было бы давать адекватную подсветку каждый раз.
В Java можно это сделать, но проще пропатчить генерируемый класс, чем везде выставлять такую штуку, тем более что в C# достаточно 2 аргументов, а в Java их надо 4. Впрочем попробую, может оно и в правду лучше работать будет.
Летом отчет по вебгоату присылали. Версию я не помню, осилить HASP ваш не смог :D
А зачем парсить файлы с синтаксическими ошибками?
Если это какая-то мелкая ошибка, то тем более фолдинг — лучшее решение, потому что потеряется только фрагмент, хотя достаточно требовать, что бы код компилировался родной утилитой, тогда проблем не будет.
SLL хорошо работает на компилируемых файлах. Мусор отправлять на анализ тоже такое себе дело.
Или у вас парсер позволяет в txt файле java-код или какой-нибудь еще?
Неправильно выразился, парсер, если ему отдавать сразу все работает очень медленно.
А заменить в джаве final static нельзя (на самом деле можно, но это будет слабоумие и отвага).
buildFoldToken рекурсивно собирает все токены начиная с { и по }, создает для них токен с адресом от { по }, внутри имеет список токенов, которые он поглотил, включая такие же фолды.
А уже в ANTLR идет так:
В итоге и обычный режим работает, и оптимизация тоже пашет. Парсить токены внутри FoldBlock можно когда потребуется. А главное, что lookahead убивается на корню, потому что он не нужен для случаев, когда альтернативы быть не может, но ANTLR честно их ищет.
Java.
Они не SLL. Запускаешь эти грамматики на тестовом множестве (2000+ файлов), так половина минимум падает с ошибками.
Увы, но предложенное вами решение крайне медленное. Сброс кеша в джаве таким же способом не удастся реализовать, особенно, если есть многопоточный анализ. Возможно в C# как-то по другому реализованы статики.
Дано: грамматика JavaScript 2019, на вход посылаем файл в 127 кб минифицированного кода — 38 секунд на обработку, 12% gc max. Без xmx4g запускать бессысленно.
Включаем упаковку блоков в токен (создается токен, в котором есть список токенов) — 12 секунд xmx64m дает 5% gc max, при xmx128m 1% gc max, парсим блоки в многопоточном режиме на 8 ядрах — 4 секунды. ATN создается на каждый новый инстанс парсера.
Если под поэтапностью вы понимаете разбор одного и того же файла разными парсерами, то да, но использовать AST, создаваемый ANTLR все равно не рекомендую, слишком много лишней информации.
Java, CSharp, Python, Php, JavaScript, TypeScript, C++, C, и многие другие языки достаточно просты, что бы сделать грамматику, которая будет работать без синтаксических ошибок в режиме SLL.
Вы что-то не так делаете в вашем парсере, что требуется включать такую фичу.
Впрочем я уже видел работу анализатора Positive Tech :D Воздержусь от критики.
Открытые грамматики реализованы крайне посредственно. Иногда можно встретить хорошее решение, но в общем случае лучше написать самому сразу SLL, чем давится ALL кактусом.
Будет отдельная статья, где объясню всю кухню работы с ANTLR4 на Java, данная статья была больше для того, что бы понять, есть ли интерес у людей к такой тематике.
У лексера можно переопределить обработку токенов:
Это кусок кода для анализа TypeScript/JavaScript, гораздо выгоднее проанализировать собственными руками последовательность символов и сделать токен с шаблонной строкой, чем нагружать лексер, тем более, что в случае вложенности будут проблемы с анализом выражений. Для правила startTemplate токены TemplateLiteral* создавались не лексером, а руками. Код у правил удалил, потому что при просмотре превращается в кашу.
parseTemplateString — находит индекс последнего символа шаблонной строки с учетом вложенности.
Уже после этот литерал парсится отдельно. Например вот так:
Внутри parseItems все folds, templates так же добавляются в очередь jobs
Полагаю, что с комментариями можно такую же штуку провернуть.
Должно быть что-то в таком духе у вас:
Если поиграетесь с режимами работы лексера (mode — его можно устанавливать до выполнения), то можно все в одном уместить, и с парсером так же удастся сделать.
Правила можно легко вызывать вот таким образом:
DELETED
Делаешь токен с новым типом, сохраняешь в него список токенов, регистрируешь каким-то образом токен, что бы можно было узнать о нем. Далее в местах, где есть блок, добавляешь альтернативу с новым типом токена. После анализа файла создаешь парсеры для сохраненных токенов и разбираешь их, пока не останется в регистре элементов. Лексер работает только один раз.
И вуаля, вместо 4 ГБ хипа хватает 128 мб.
В 2020 бы заниматься разработкой поиска уязвимостей по регулярным выражениям…
Еще в 2012 году такое было.