Доброго времени суток, коллеги. Я по-прежнему являюсь разработчиком 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}]Надеюсь, уважаемые читатели, вам было также интересно познакомиться с основами Спирита как и мне. Засим остаюсь. До скорых встреч.
Автор: Kroineko
