А зачем вам парсер, если на уровне лексера вы можете встроить анализ всех этих конструкций? Более того, давайте посмотрим на то, как работает препроцессор С++, он вообще не знает в плане вычислений условий, что существует С++, все вычисления производится только согласно стандарту препроцессора. Это вообще отдельная грамматика.
По сути процесс разбора для С++ выглядит примерно так:
1 Токенизировать файл, получить шаблонный файл препроцессора, состоящего из конструкций #if #else #end, #define, #udef, etc… Причем директивы можно вполне обрабатывать прямо вклинившись в токенизатор. Если есть инклюд, который вы не обработали, то ничто не мешает рекурсивно вызывать разбор файла внутри разбора файла. Это нужно, что бы потом можно было модифицировать набор дефайнов согласно шаблону. Т.е. вы проходите по хидеру, игнорируете все, что не относится к препроцессору, берете только дефайны, актуальные для текущего момента. При этом разбор заголовка ничем не будет отличаться от других файлов.
2 Преобразование потока токенов согласно шаблонным файлам, раскрыть макросы и управление препроцессором. В итоге если у вас были setup.h, setup.cpp, то на выходе будут те же самые файлы, только с раскрытыми макросами и удаленными полностью инструкциями препроцессора. Из setup.h в setup.cpp ничего не копируется и не вставляется.
3 Передать поток уже готовых токенов файла в парсер.
При таком подходе вам не надо все сливать в один файл (есть исключение для файлов inc, их токены надо именно что вставлять). Поэтому работать парсер будет на маленьком файле и ему не надо парсить каждый раз один и тот же набор деклараций из заголовков, потому что вы их проанализируете как отдельный файл.
И да, хочу еще раз отметить, что есть небольшая проблема с inc файлами, но обычно у них именно такое расширение, так что разрулить можно, хуже если умник какой-нибудь нарушает стандарты. Такой подход конечно же рискованный, но для SAST он вполне актуален. Экономит просто массу вычислительных ресурсов. Тем более что подать потом на парсер файлы в определенном порядке (а мы знаем все зависимости между файлами) труда вообще не составляет, не так ли?
Да это пример. И на ANTLR все языки пробую больше для понимания пределов работы этого фреймворка. Мне нужно знать его ограничения, так как некоторые вещи на нем реализовывать не просто быстрее и легче, но и оптимальнее.
Сделать самописный рекурсивный парсер вообще не представляется никакой проблемой. Более того, можно почти один в один скопировать код из roslyn на джаву и получить нужный мне парсер. Но зачем, если я уже знаю как оно будет работать с точностью до второго знака после запятой? =)
Если потребуется оптимизировать работу того или иного парсера/лексера — это можно будет сделать уже отдельно потом, потому что внутренний поток данных уже будет стандартом и от реализации никак не изменится.
Если я правильно понял, вы предлагаете хранить связь пользователь-роль-объект доступа в каждом ресурсном микросервисе, но всё равно, при наличии глобальных ролей, обращаться в сервис ролей за ними, тем самым делая на один запрос к какому-либо ресурсу 1 сетевой запрос и 1 запрос в БД.
Вам не всегда нужно делать дополнительный запрос в свою БД, при просмотре вы можете за один запрос и сущность получить и флаг видно/нет вытащить, а то и вовсе кинуть человеку 404, если он не должен видеть. Если же это изменение и нужно проверку сделать до, то что мешает держать кеш (Пользователь, Ресурс)=Булев? Он много памяти не скушает. Да и не особо он нужен в таком виде, необходимый запрос к БД выполняется за 0.002 ms, даже если у вас 10 000 000 строк в таблице. А зачем вам каждый раз для одного и того же пользователя получать его роли? В статье про то, что их нужно кешировать как раз и писалось.
Если хранить все доступы в одном месте, то возникает 2 проблемы:
Если идете по пути универсализации, то получается из БД вы вытаскиваете расчеты в приложение (нам же не просто доступ нужен, он может быть условный, временный или еще какой-то) — а это значит, что работать ваш ACL будет как старый пыльный пень, не надо так;
Если же пойдете по пути добавления функционала на каждый микросервис и подгонки БД под это дело, то у вас будет 100500 АПИ на каждый случай жизни и большущая команда разработки авторизации, когда хватило бы полтора инвалида для тех поддержки полностью завершенного и закрытого микросервиса ролевой модели, в который доработки если и потребуются, то на уровне "добавьте роль в БД на проме".
Роли пользователя не размазываются по микросервисам, потому что вы передаете только доступы. Попробуйте смотреть на предложенное с точки зрения иерархии микросервисов и разделения их на сегменты, что-то в духе — эта часть работы с проектами, эта с подбором персонала, а тут у нас обучение. Выкидываете один сегмент — все остальные работают как и работали, выпиливать или удалять из других БД вам ничего не нужно, потому что все лишнее уже само ушло. У вас система получается более гибкой и устойчивой к проблемам. Если у вас один огромный монолит под названием авторизация, то вы туда можете сколько угодно заливать ресурсов, но после определенного порога, вы уже кроме снижения производительности ничего не получите.
Если для вас мега-клиент, который должны использовать все против 1-2 клиента из N является более приемлимым вариантом, то я не знаю что вам тут сказать. Монолитом пахнет может? Это помимо того, что ваш мега-клиент будет стучаться в такой же мега-микросервис, в котором объединено много чего и вам нужна команда человек 40, просто что бы оно жило.
это от вас зависит. Сделать это можно как и раньше. Вы можете с сущностью вычислить доступ пользователя.
Что-то в таком духе (могут быть ошибки в синтаксисе):
SELECT new R(entity, (SELECT exists(*) FROM ppa where ppa.person = ?2 AND ppa.page = ?1 AND ppa.valid_until > CURRENT_TIMESTAMP ) FROM p WHERE p.id = ?1
Вам не нужно ничего перерасчитывать на фронте. Либо можно вовсе отдельную ручку сделать, отдаете туда идентификаторы статей/авторов, в ответ получаете карту ид=булев.
То же самое, если вам нужно массово получать статьи, но только те, на которые у вас есть подписки, к вашим условиям фильтрации добавляете дополнительное — существование записи ppa с нужными полями. Постгрес это делает очень быстро, особенно в случае индекс онли скана, что и должно быть.
Да, текст не хранится в токенах. По хорошему, если текст потом используется где-то (например в названиях переменных), то нужно обязательно пропускать через собственный интернер, что бы строки не дублировались в памяти, но вносить такое в токен не стоит.
Есть такое, но для регулярных выражений очень сложная семантика, поэтому выгоднее сделать простой валидатор, что бы не запускать процесс обработки вовсе, чем добавлять в кеш эту штуку.
Просто для примера, неправильно позиционированный предикат для регулярок JS заставляет в кэш попадать строки по 20-30 тысяч символов, просто потому что регулярка так парсится =) Это случается редко и скорее всего лишь во время жертвоприношения девственниц, но бабахает больно. Поэтому и не стал добавлять в список вредных советов ваш вариант, так как он ситуативен, даже несмотря на приведенный вами комментарий про DFA. Как уже говорил — DFA работает лишь в определенных границах, вне его пределов — превращается в шлак.
Статистику не собирал, слишком долго. Но в районе 2-3% должно дать, да. Правда есть одно но: изначально говорил, что еще можно 30-40% оптимизировать без злобных хаков то, что выложил =)
Ищите и думайте =) Итак уже безвозмездно выложил оптимизацию в 2-10 раз.
Кстати, а имеет ли смысл анализировать все минифицированные библиотеки? По крайней мере их можно проанализировать один раз, а дальше использовать закешированный результат.
Это не всегда возможно, и есть требование анализировать все зависимости на каждом анализе. Версии могут отличаться, даже если разница в одной функции — может повлиять на результат. Поэтому работать парсер должен на всем, а в случае минифицированных библиотек — обязательно, так как там набито куча всего и из-за одной ошибки можно много чего потерять.
Я рад, что у вас хватает времени на разработку оптимизированной грамматики. К сожалению, порой нет времени и на это.
Суммарно на грамматики 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 грамматик, они не могут работать быстро по определению.
Никто не сравнится с программистом, угрожающим проверять свои коммиты, перед тем как делать PR!
Тем не менее в режиме SLL со сверточной оптимизацией — творит чудеса =)
Спасибо за замечание, исправил.
После того обсуждения вопрос отложил пока, потому что бюджет времени на С# исчерпан пока что =)
Делу время, а потехе час.
А зачем вам парсер, если на уровне лексера вы можете встроить анализ всех этих конструкций? Более того, давайте посмотрим на то, как работает препроцессор С++, он вообще не знает в плане вычислений условий, что существует С++, все вычисления производится только согласно стандарту препроцессора. Это вообще отдельная грамматика.
По сути процесс разбора для С++ выглядит примерно так:
1 Токенизировать файл, получить шаблонный файл препроцессора, состоящего из конструкций #if #else #end, #define, #udef, etc… Причем директивы можно вполне обрабатывать прямо вклинившись в токенизатор. Если есть инклюд, который вы не обработали, то ничто не мешает рекурсивно вызывать разбор файла внутри разбора файла. Это нужно, что бы потом можно было модифицировать набор дефайнов согласно шаблону. Т.е. вы проходите по хидеру, игнорируете все, что не относится к препроцессору, берете только дефайны, актуальные для текущего момента. При этом разбор заголовка ничем не будет отличаться от других файлов.
2 Преобразование потока токенов согласно шаблонным файлам, раскрыть макросы и управление препроцессором. В итоге если у вас были setup.h, setup.cpp, то на выходе будут те же самые файлы, только с раскрытыми макросами и удаленными полностью инструкциями препроцессора. Из setup.h в setup.cpp ничего не копируется и не вставляется.
3 Передать поток уже готовых токенов файла в парсер.
При таком подходе вам не надо все сливать в один файл (есть исключение для файлов inc, их токены надо именно что вставлять). Поэтому работать парсер будет на маленьком файле и ему не надо парсить каждый раз один и тот же набор деклараций из заголовков, потому что вы их проанализируете как отдельный файл.
И да, хочу еще раз отметить, что есть небольшая проблема с inc файлами, но обычно у них именно такое расширение, так что разрулить можно, хуже если умник какой-нибудь нарушает стандарты. Такой подход конечно же рискованный, но для SAST он вполне актуален. Экономит просто массу вычислительных ресурсов. Тем более что подать потом на парсер файлы в определенном порядке (а мы знаем все зависимости между файлами) труда вообще не составляет, не так ли?
100% покрытие именно кода.
На 100% перебор всех альтернатив и вариантов комбинаций правил даже бейсика уйдет пара млн. человеколет.
Да это пример. И на ANTLR все языки пробую больше для понимания пределов работы этого фреймворка. Мне нужно знать его ограничения, так как некоторые вещи на нем реализовывать не просто быстрее и легче, но и оптимальнее.
Сделать самописный рекурсивный парсер вообще не представляется никакой проблемой. Более того, можно почти один в один скопировать код из roslyn на джаву и получить нужный мне парсер. Но зачем, если я уже знаю как оно будет работать с точностью до второго знака после запятой? =)
Если потребуется оптимизировать работу того или иного парсера/лексера — это можно будет сделать уже отдельно потом, потому что внутренний поток данных уже будет стандартом и от реализации никак не изменится.
Вам не всегда нужно делать дополнительный запрос в свою БД, при просмотре вы можете за один запрос и сущность получить и флаг видно/нет вытащить, а то и вовсе кинуть человеку 404, если он не должен видеть. Если же это изменение и нужно проверку сделать до, то что мешает держать кеш (Пользователь, Ресурс)=Булев? Он много памяти не скушает. Да и не особо он нужен в таком виде, необходимый запрос к БД выполняется за 0.002 ms, даже если у вас 10 000 000 строк в таблице. А зачем вам каждый раз для одного и того же пользователя получать его роли? В статье про то, что их нужно кешировать как раз и писалось.
Если хранить все доступы в одном месте, то возникает 2 проблемы:
Роли пользователя не размазываются по микросервисам, потому что вы передаете только доступы. Попробуйте смотреть на предложенное с точки зрения иерархии микросервисов и разделения их на сегменты, что-то в духе — эта часть работы с проектами, эта с подбором персонала, а тут у нас обучение. Выкидываете один сегмент — все остальные работают как и работали, выпиливать или удалять из других БД вам ничего не нужно, потому что все лишнее уже само ушло. У вас система получается более гибкой и устойчивой к проблемам. Если у вас один огромный монолит под названием авторизация, то вы туда можете сколько угодно заливать ресурсов, но после определенного порога, вы уже кроме снижения производительности ничего не получите.
Если для вас мега-клиент, который должны использовать все против 1-2 клиента из N является более приемлимым вариантом, то я не знаю что вам тут сказать. Монолитом пахнет может? Это помимо того, что ваш мега-клиент будет стучаться в такой же мега-микросервис, в котором объединено много чего и вам нужна команда человек 40, просто что бы оно жило.
это от вас зависит. Сделать это можно как и раньше. Вы можете с сущностью вычислить доступ пользователя.
Что-то в таком духе (могут быть ошибки в синтаксисе):
SELECT new R(entity, (SELECT exists(*) FROM ppa where ppa.person = ?2 AND ppa.page = ?1 AND ppa.valid_until > CURRENT_TIMESTAMP ) FROM p WHERE p.id = ?1
Вам не нужно ничего перерасчитывать на фронте. Либо можно вовсе отдельную ручку сделать, отдаете туда идентификаторы статей/авторов, в ответ получаете карту ид=булев.
То же самое, если вам нужно массово получать статьи, но только те, на которые у вас есть подписки, к вашим условиям фильтрации добавляете дополнительное — существование записи ppa с нужными полями. Постгрес это делает очень быстро, особенно в случае индекс онли скана, что и должно быть.
Никогда не променяю на ваши жалкие бусы.
Да, текст не хранится в токенах. По хорошему, если текст потом используется где-то (например в названиях переменных), то нужно обязательно пропускать через собственный интернер, что бы строки не дублировались в памяти, но вносить такое в токен не стоит.
Есть такое, но для регулярных выражений очень сложная семантика, поэтому выгоднее сделать простой валидатор, что бы не запускать процесс обработки вовсе, чем добавлять в кеш эту штуку.
Просто для примера, неправильно позиционированный предикат для регулярок JS заставляет в кэш попадать строки по 20-30 тысяч символов, просто потому что регулярка так парсится =) Это случается редко и скорее всего лишь во время жертвоприношения девственниц, но бабахает больно. Поэтому и не стал добавлять в список вредных советов ваш вариант, так как он ситуативен, даже несмотря на приведенный вами комментарий про DFA. Как уже говорил — DFA работает лишь в определенных границах, вне его пределов — превращается в шлак.
Статистику не собирал, слишком долго. Но в районе 2-3% должно дать, да. Правда есть одно но: изначально говорил, что еще можно 30-40% оптимизировать без злобных хаков то, что выложил =)
Ищите и думайте =) Итак уже безвозмездно выложил оптимизацию в 2-10 раз.
Тест токенизации файла размером 1,7 мб:
Как было — 5615 ms
Перенес за символ / предикат — 5440 ms
Небольшой выигрыш оказался :D
DELETED
Это не всегда возможно, и есть требование анализировать все зависимости на каждом анализе. Версии могут отличаться, даже если разница в одной функции — может повлиять на результат. Поэтому работать парсер должен на всем, а в случае минифицированных библиотек — обязательно, так как там набито куча всего и из-за одной ошибки можно много чего потерять.
Суммарно на грамматики 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 грамматик, они не могут работать быстро по определению.