Доброго времени суток, коллеги. Я по-прежнему являюсь разработчиком ISPsystem, и меня все еще зовут Дмитрий Смирнов. Некоторое (довольно продолжительное) время я никак не мог определиться с темой следующей публикации, поскольку материала за последние месяцы работы с Boost.Asio накопилось много. И уже в тот момент, когда казалось, что легче подбросить монетку, одна задача все изменила. Нужно было разработать инструмент, позволяющий frontend’у фильтровать данные в запрашиваемых списках. Сам же список со стороны backend'а представляет собой обыкновенный json_array. Добро пожаловать под кат, там все взлеты и падения последних дней.
Дисклеймер
Сразу оговорюсь, что последний раз автор «щупал» нечто вроде контекстно-свободной грамматики десять лет назад. Тогда это казалось каким-то довольно невнятным и ненужным инструментом, а про библиотеку Boost.Spirit я узнал собственно в день постановки задачи.
Задача
Нужно превратить запрос типа:
(string_field CP value AND int_field NOT LT 150) OR bool_field EQ true
В какую-то структуру, которая будет проверять объект json и сообщать, удовлетворяет он требованиям или нет.
Первые шаги
Первым делом необходимо определиться с интерфейсом будущего фильтра. Предстоит убирать лишние объекты из массива, поэтому он должен сочетаться с STL алгоритмами, в частности std::remove_if.
Прекрасно подойдет функтор, который будет конструироваться непосредственно из запроса с фронта. Поскольку в проекте используется nlohmann::json, конструкция получится довольно элегантной:
filter = "(string_field CP value AND int_field NOT LT 150) OR bool_field EQ true"; json.erase(std::remove_if(json.begin(), json.end(), std::not_fn(JsonFilter{filter})), json.end());
Для удобного применения фильтра я выбрал разделение условий на двоичное дерево. Самые нижние вершины должны содержать операторы сравнения, все же прочие — логические операторы. Вот так будет выглядеть в разобранном состоянии указанный выше фильтр:
Получилась некая форма AST, если можно так это назвать. Теперь, когда картина предстоящей логики сложилась, настал момент самого интересного и ужасного. Это надо написать… На Спирите...
Знакомство
Встал самый сложный вопрос: с чего начать? В отличие от Asio чтение хедеров Spirit не дало никаких внятных подсказок, иными словами – там "какая-то магия". Далее последовало изучение примеров в официальной документации буста и всевозможных примеров в сети, что через определенное время принесло не просто свои плоды, а решение максимально приближенное к моим нуждам: AST калькулятор
Давайте разберем грамматику, представленную в примере:
class ArithmeticGrammar1 : public qi::grammar<std::string::const_iterator, ASTNodePtr(), qi::space_type> { public: using Iterator = std::string::const_iterator; ArithmeticGrammar1() : ArithmeticGrammar1::base_type(start) { start = (product >> '+' >> start) [qi::_val = phx::new_<OperatorNode<'+'>> (qi::_1, qi::_2)] | product[qi::_val = qi::_1]; product = (factor >> '*' >> product) [qi::_val = phx::new_<OperatorNode<'*'>> (qi::_1, qi::_2)] | factor[qi::_val = qi::_1]; factor = group[qi::_val = qi::_1] | qi::int_[qi::_val = phx::new_<ConstantNode>(qi::_1)]; group %= '(' >> start >> ')'; } qi::rule<Iterator, ASTNodePtr(), qi::space_type> start, group, product, factor; };
Грамматика наследуется от базовой qi::grammar. ASTNodePtr() — это не очевидный, но очень удобный способ передать в объект грамматики объект ожидаемого результата.
class ASTNode { public: virtual double evaluate() = 0; virtual ~ASTNode() {} }; using ASTNodePtr = ASTNode*; template <char Operator> class OperatorNode : public ASTNode { public: OperatorNode(const ASTNodePtr &left, const ASTNodePtr &right) : left(left) , right(right) {} double evaluate() { if (Operator == '+') return left->evaluate() + right->evaluate(); else if (Operator == '*') return left->evaluate() * right->evaluate(); } ~OperatorNode() { delete left; delete right; } private: ASTNodePtr left, right; // ветви }; class ConstantNode : public ASTNode { public: ConstantNode(double value) : value(value) {} double evaluate() { return value; } private: double value; };
С помощью библиотеки Boost.Phoenix можно прямо во время разбора создать из одного или нескольких нетерминалов готовую AST-ноду и записать непосредственно в результат. Рассмотрим поближе из чего же состоит калькулятор:
start = (product >> '+' >> start)[qi::_val = phx::new_<OperatorNode<'+'>> (qi::_1, qi::_2)] | product[qi::_val = qi::_1];
start — начало разбора предложения. Отправная точка. Он может быть выражен через сумму product и start или же через просто product.
Обратите внимание на действие в квадратных скобках у каждого выражения. Это действие, которое должно быть выполнено при удачном разборе, если все совпало. qi::_val — это на самом деле boost::spirit::qi::_val — плейсхолдер. С его помощью будет записан ответ в результат. В случае start это будет объект OperatorNode, у которого первым аргументом будет результат разбора product, а вторым — результат разбора start.
Смотрим дальше. Предположим, мы встретили второй вариант, start не сумма, а product. Как же он выражается?
product = (factor >> '*' >> product) [qi::_val = phx::new_<OperatorNode<'*'>> (qi::_1, qi::_2)] | factor[qi::_val = qi::_1];
Повторяется предыдущая картина с минимальными различиями. Снова встречаем какое-то выражение, снова записываем в результат объект OperatorNode или же просто какой-то factor. Давайте посмотрим на него.
factor = group[qi::_val = qi::_1] | qi::int_[qi::_val = phx::new_<ConstantNode>(qi::_1)];
Поскольку мы идем по самому короткому пути, предполагаем, что встретился нам не кто иной как int. Теперь, если описать все предыдущие шаги в псевдокоде, мы получим в раскрытом виде что-то вроде этого:
factor1 = ConstantNode(1) // абсолютно рандомное число, не заостряйте внимание factor2 = ConstantNode(3) product = OperatorNode<'*'>(factor1, factor2) start = product
Каждый узел, начиная с верхнего (за исключением самых нижних, которые тут являются, по сути, целыми числами), выражается через последующие узлы. И единственный вызов метода evaluate() у корневого элемента решает всю задачу целиком, замечательно!
Далее бросается в глаза qi::space_type — этот аргумент представляет собой список игнорируемых при разборе элементов. Это еще сыграет со мной злую шутку :-).
Замечательным тут является способ приоритизировать умножение над сложением простым путем выражения нетерминала start (как раз содержащего +) через product (*). В моем варианте грамматики, поскольку было решено, что And будет превалировать над Or, я просто подставляю требуемые логические операторы в нужные места. Если в написании математических операторов ошибиться трудно, то текстовые логические операторы — совсем другая история. Возникает желание решить хотя бы часть возможных проблем, например, регистр. Для этого в Спирите есть встроенный тип qi::no_case
Далее, вместо чисел мне понадобятся имена полей, поэтому добавляем соответствующий нетерминал вместо встроенного в спирит qi::int_ :
field = qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9");
И получаем вот такое простое выражение (пока никаких семантических операций):
start = product >> qi::no_case["OR"] >> start | product; product = factor >> qi::no_case["AND"] >> product | factor; factor = group | field; group %= '(' >> start >> ')';
Теперь все готово для разбора простейшего предложения "field And field2". Запускаем и… ничего не работает.
Проблема оказалась в неожиданном месте: qi::space_type не просто игнорирует пробелы, он их удаляет из предложения перед разбором, и изначальное выражение фильтра приходит в разбор уже в виде:
"fieldAndfield2" \\ В случае калькулятора это не вызывало никаких проблем, нет разницы разбирать "(5 * 5) + 11 " \\ или "(5*5)+11"
Это просто одно единственное поле. Соответственно, понадобится некий skipper:
skipper = +qi::lit(' '); // Не пугайтесь префиксного плюса. Да, выглядит не особо красиво, но постфиксных плюсов, к несчастью, в C++ нет. start = product >> skipper >> qi::no_case["OR"] >> skipper >> start | product; ...
После того как разбирать поля стало возможно, пора научиться получать из выражений значения и понимать, как поле должно валидироваться относительно значения. Все варианты сравнений можно выразить через следующие операции:
enum class Operator { EQ, // равно LT, // меньше GT, // больше CP // содержит (только для строк) }; unary = qi::no_case["NOT"]; // отрицание, с помощью которого мы сможем описать все прочие состояния
А сами значения выражаются таким нетерминалом:
value = qi::double_ | qi::int_ | qi::bool_ | string; string = qi::lit("'") >> +qi::char_("a-zA-Z0-9_. ") >> qi::lit("'");
Теперь к тем проблемам, которые несёт в себе такой способ получения значения. Спирит вернет его в виде boost::variant<int, double, bool, std::string>, и когда придет время сравнивать его с некоторыми данными, понадобятся определенные ухищрения, чтобы получить значение нужного типа. Вот к какому варианту пришел я:
using ValueType = boost::variant<int, double, bool, std::string>; struct ValueGetter : public boost::static_visitor<Json> { template <typename Type> Json operator()(const Type &value) const { return value; } };
Почему геттер возвращает объект Json? Таким образом, при сравнении значений во время фильтрации я избегу необходимости выяснять, какой именно тип данных проходит сравнение, предоставив всю работу библиотеке json.
Финишная прямая. Описание самого матчера. Воспользуемся все тем же примером с калькулятором. Для начала нам нужна абстракция, которую мы передадим в грамматику, а Спирит любезно нам ее заполнит:
class AbstractMatcher { public: AbstractMatcher() = default; virtual ~AbstractMatcher() = default; virtual bool evaluate(const Json &object) = 0; // этот метод решит всю нашу задачу }; using MatcherPtr = std::shared_ptr<AbstractMatcher>;
Далее логические ноды — основные узлы фильтра:
enum class Logic { AND, OR }; template <Logic Operator> class LogicNode final : public AbstractMatcher { public: LogicNode(MatcherPtr &left, MatcherPtr &right) : m_left(std::move(left)) , m_right(std::move(right)) { switch (Operator) { case Logic::AND: m_evaluator = &LogicNode::And; break; case Logic::OR: m_evaluator = &LogicNode::Or; } } bool evaluate(const Json &object) final { return std::invoke(m_evaluator, this, object); } private: MatcherPtr m_left; MatcherPtr m_right; using EvaluateType = bool(LogicNode::*)(const Json &); EvaluateType m_evaluator = nullptr; bool And(const Json &object) { return m_left->evaluate(object) && m_right->evaluate(object); } bool Or(const Json &object) { return m_left->evaluate(object) || m_right->evaluate(object); } };
И, наконец, нижние узлы
class ObjectNode final : public AbstractMatcher { public: ObjectNode(std::string field, const ValueType &value, boost::optional<std::string> &unary, Operator oper) : m_field(std::move(field)) , m_json_value(boost::apply_visitor(ValueGetter(), value)) , m_reject(unary.has_value()) { switch (oper) { case Operator::EQ: m_evaluator = &ObjectNode::Equal; break; case Operator::LT: m_evaluator = &ObjectNode::LesserThan; break; case Operator::GT: m_evaluator = &ObjectNode::GreaterThan; break; case Operator::CP: m_evaluator = &ObjectNode::Substr; break; } } bool evaluate(const Json &object) final { const auto &value = object.at(m_field); const bool result = std::invoke(m_evaluator, this, value); return m_reject ? !result : result; } private: using EvaluateType = bool(ObjectNode::*)(const Json &); const std::string m_field; const Json m_json_value; const bool m_reject; EvaluateType m_evaluator = nullptr; bool Equal(const Json &json) { return json == m_json_value; } bool LesserThan(const Json &json) { return json < m_json_value; } bool GreaterThan(const Json &json) { return json > m_json_value; } bool Substr(const Json &json) { return Str(json).find(Str(m_json_value)) != std::string::npos; } };
Осталось только собрать все это воедино:
struct JsonFilterGrammar : qi::grammar<std::string::const_iterator, MatcherPtr()> { JsonFilterGrammar() : JsonFilterGrammar::base_type(expression) { skipper = +qi::lit(' '); unary = qi::no_case["NOT"]; compare.add ("eq", Operator::EQ) ("lt", Operator::LT) ("gt", Operator::GT) ("cp", Operator::CP); expression = (product >> skipper >> qi::no_case["OR"] >> skipper >> expression) [qi::_val = make_shared_<LogicNode<Logic::OR>>()(qi::_1, qi::_2)] | product[qi::_val = qi::_1]; product = (term >> skipper >> qi::no_case["AND"] >> skipper >> product) [qi::_val = make_shared_<LogicNode<Logic::AND>>()(qi::_1, qi::_2)]| term[qi::_val = qi::_1]; term = group[qi::_val = qi::_1] | (field >> -(skipper >> unary)>> skipper >> qi::no_case[compare] >> skipper >> value) [qi::_val = make_shared_<ObjectNode>()(qi::_1, qi::_4, qi::_2, qi::_3)]; field = qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9"); value = qi::double_ | qi::int_ | qi::bool_ | string; string = qi::lit("'") >> +qi::char_("a-zA-Z0-9_. \u20BD€$¥-") >> qi::lit("'"); group %= '(' >> expression >> ')'; } qi::rule<Iterator> skipper; qi::rule<Iterator, MatcherPtr()> product, term, expression, group; qi::rule<Iterator, std::string()> field, unary, string; qi::rule<Iterator, ValueType()> value; qi::symbols<char, Operator> compare; // замечательный способ создать правила из enum };
Вот и все. Теперь получение готового фильтра стало довольно простой операцией:
MatcherPtr matcher; std::string filter = "int not LT 15"; JsonFilterGrammar grammar; qi::parse(filter.begin(), filter.end(), grammar, matcher); // после удачного разбора строки matcher будет содержать фильтр.
Я опущу процесс оборачивания грамматики в функтор (не думаю, что это будет кому-то интересно). Лучше рассмотрим инструмент в действии на максимально простом примере:
std::string filter = "int not LT 15"; Json json{ {{"int", 10}}, {{"int", 11}}, {{"int", 20}}, {{"int", 30}}, {{"int", 9}} }; std::cout << json.dump() << std::endl; json.erase(std::remove_if(json.begin(), json.end(), std::not_fn(JsonFilter{filter})), json.end()); std::cout << json.dump() << std::endl;
Вот полученный вывод:
[{"int":10},{"int":11},{"int":20},{"int":30},{"int":9}] [{"int":20},{"int":30}]
Надеюсь, уважаемые читатели, вам было также интересно познакомиться с основами Спирита как и мне. Засим остаюсь. До скорых встреч.
