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

    image


    Доброго времени суток, коллеги. Я по-прежнему являюсь разработчиком 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() — это не очевидный, но очень удобный способ передать в объект грамматики объект ожидаемого результата.


    AST node калькулятора
    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; }  
    };

    Осталось только собрать все это воедино:


    Json фильтр
    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}]

    Надеюсь, уважаемые читатели, вам было также интересно познакомиться с основами Спирита как и мне. Засим остаюсь. До скорых встреч.

    ISPsystem
    Софт для хостинга: ISPmanager, BILLmanager и др.

    Похожие публикации

    Комментарии 8

      0
      Как обстоят дела со временем сборки? Я как то использовал spirit для разбора математических выражений с дополнительными фичами, так у меня парсер собирался минут 10 (MinGW на Windows).
        0
        Я работаю со связкой conan + cmake + ninja + clang8. Если «на холодную», то есть conan install, потом cmake, потом билд. То да, это прямо скажем небыстрый процесс, особенно, если зависимые библиотеки конан собирает на месте. Если же зависимости уже лежат готовые в ~/.conan/data, то я бы не сказал, что все так уж плохо. Вся библиотека(которая состоит из многих инструментов помимо фильтра) с тестами, которые проверяют и парсер в том числе, собирается за 2 минуты.
        –2
        Если в ISPManager все архитектурные решения принимаются так, как указано здесь — то не зря я все это время их сторонился.

        Это же надо, сделать отдельный DSL для запросов, чтобы на фронте (!) фильтровать данные от бекенда. Вы ему не доверяете? Или ваш бекенд не в состоянии сам отфильтровать данные?
          0

          Не совсем понимаю ваш вопрос. Вы спрашиваете почему фронт фильтрует данные бэка, я правильно понимаю? Но ведь это именно бэк фильтрует, фронт только сообщает какие данные ему нужны. Условно запрос будет выглядеть как-то так:


          GET "/user/list?where%3Dname%20EQ%20Ivan"
          +1
          Такой вопрос… Вот если посмотреть на строчку:
          start = (product >> '+' >> start)[qi::_val = phx::new_<OperatorNode<'+'>> (qi::_1, qi::_2)]
          | product[qi::_val = qi::_1];
          Здесь мы видим, что узлы дерева создаются в динамической памяти, но вот не понятно, кто их потом освобождать будет?
          Если парсинг завершился успешно, то тут все нормально, корневой узел удалит своих потомков. По парсинг может отвалиться на середине, тогда корневой узел никогда не будет создан а дочерние уже созданы(вот кто их будет освобождать?).

          Или же phx::new_ там у себя внутри регистрирует все указатели где-то? Чтобы в случае неудачи освободить их все(звучит вроде логично, я пытался смотреть сам в коде phx::new_, но там мясоо..)

          А так, спасибо за статью. Редко такой материал здесь увидишь.
            0

            Это замечательный вопрос! Все именно так, как вы говорите. В изначальном примере создается как раз-таки raw pointer, по крайней мере, разбираясь в этом вопросе я не нашел подтверждения обратного. И никто не позаботится о них в случае каких-то форс-мажоров. Именно поэтому, я использую в своих фильтрах только shared_ptr. На нашем обожаемом stackoverflow я нашел подходящее решение для феникса Phoenix make_shared. Как раз его-то я и использую тут:


              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];

            Очень рад, что этот материал вас порадовал)

              0
              Ну shared_ptr для моего случая слишком жирно… Хоть бы на самописную обертку его заменить — без атомарного счетчика.
            0
            field = qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9");

            Интересный у вас выбор парсера для строкового идентификатора. Не лучше ли было бы:
            lexeme[(alpha | '_') >> *(alnum | '_')];

            Догадываюсь, что «f i e l d And f i e l d 2» он у вас разберет как «field And field2»:)

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое