Boost.Spirit, или Добавляем «духовности» фильтрам списков

Доброго времени суток, коллеги. Я по-прежнему являюсь разработчиком 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 ^[1], если можно так это назвать. Теперь, когда картина предстоящей логики сложилась, настал момент самого интересного и ужасного. Это надо написать… На Спирите...

Знакомство

Встал самый сложный вопрос: с чего начать? В отличие от Asio чтение хедеров Spirit не дало никаких внятных подсказок, иными словами – там "какая-то магия". Далее последовало изучение примеров в официальной документации буста и всевозможных примеров в сети, что через определенное время принесло не просто свои плоды, а решение максимально приближенное к моим нуждам: AST калькулятор ^[2]
Давайте разберем грамматику, представленную в примере:

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

Источник ^[3]