Boost.Spirit, ou adicione "Espiritualidade" aos filtros da lista

Bom dia, colegas. Eu ainda sou desenvolvedor de sistemas ISPs e meu nome ainda é Dmitry Smirnov. Por um tempo (bastante longo), não pude decidir sobre o tópico da próxima publicação, já que muito material se acumulou nos últimos meses de trabalho com o Boost.Asio. E mesmo naquele momento em que parecia mais fácil jogar uma moeda, uma tarefa mudou tudo. Foi necessário desenvolver uma ferramenta que permita ao front-end filtrar dados nas listas solicitadas. A própria lista do back-end é uma json_array comum. Bem-vindo ao Kat, existem todos os altos e baixos dos últimos dias.

Isenção de responsabilidade

Devo dizer imediatamente que a última vez que o autor "sentiu" algo como gramática sem contexto dez anos atrás. Parecia uma ferramenta meio arrastada e desnecessária, mas eu aprendi sobre a biblioteca Boost.Spirit no mesmo dia da declaração do problema.

Desafio

Precisa ativar uma consulta como:

(string_field CP value AND int_field NOT LT 150) OR bool_field EQ true 

Em alguma estrutura que verificará o objeto json e informará se ele atende aos requisitos ou não.

Primeiros passos

Primeiro de tudo, você precisa decidir sobre a interface do futuro filtro. É necessário remover objetos desnecessários da matriz, portanto, ele deve ser combinado com os algoritmos STL, em particular std :: remove_if.

Um functor será perfeito, que será construído diretamente a partir da solicitação de frente. Como o projeto usa nlohmann :: json, o design será bastante elegante:

 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()); 

Para uso conveniente do filtro, optei por dividir as condições em uma árvore binária. Os vértices mais baixos devem conter operadores de comparação, mas o restante deve ser operadores lógicos. É assim que o filtro acima ficará em um estado desmontado:

O resultado foi uma forma de AST , se você pode chamar assim. Agora que a imagem da lógica que está por vir tomou forma, chegou o momento das mais interessantes e terríveis. Isso deve estar escrito ... No espírito ...

Conhecimento

A questão mais difícil surgiu: por onde começar? Ao contrário do Asio, ler os cabeçalhos do Spirit não deu pistas claras, em outras palavras - há "algum tipo de mágica". Isso foi seguido por um estudo de exemplos na documentação oficial do impulso e todos os tipos de exemplos na rede, que após algum tempo trouxeram não apenas seus frutos, mas uma solução o mais próxima possível das minhas necessidades: Calculadora AST

Vejamos a gramática apresentada no exemplo:

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

A gramática é herdada da base qi :: grammar. ASTNodePtr () não é uma maneira óbvia, mas muito conveniente, de passar um objeto do resultado esperado para um objeto de gramática.

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

Usando a biblioteca Boost.Phoenix, você pode criar um nó AST pronto a partir de um ou vários terminais não durante a análise e gravar diretamente no resultado. Vamos dar uma olhada em que consiste a calculadora:

 start = (product >> '+' >> start)[qi::_val = phx::new_<OperatorNode<'+'>> (qi::_1, qi::_2)] | product[qi::_val = qi::_1]; 

start - começa a analisar a frase. Ponto de partida. Pode ser expresso pela soma do produto e início, ou simplesmente pelo produto.

Observe a ação entre colchetes para cada expressão. Essa é a ação que deve ser executada se a análise for bem-sucedida, se tudo corresponder. qi :: _ val é realmente boost :: spirit :: qi :: _ val é um espaço reservado. Com sua ajuda, a resposta será registrada no resultado. No caso de start, este será um objeto OperatorNode, cujo primeiro argumento será o resultado da análise do produto e o segundo é o resultado da análise de start.

Nós olhamos mais longe. Suponhamos que deparamos com a segunda opção: iniciar não é uma soma, mas um produto. Como ele se expressa?

 product = (factor >> '*' >> product) [qi::_val = phx::new_<OperatorNode<'*'>> (qi::_1, qi::_2)] | factor[qi::_val = qi::_1]; 

A imagem anterior é repetida com diferenças mínimas. Novamente encontramos algum tipo de expressão, novamente escrevemos o objeto OperatorNode no resultado, ou apenas algum tipo de fator. Vamos dar uma olhada.

 factor = group[qi::_val = qi::_1] | qi::int_[qi::_val = phx::new_<ConstantNode>(qi::_1)]; 

À medida que avançamos no caminho mais curto, assumimos que não nos encontramos senão int. Agora, se descrevermos todas as etapas anteriores no pseudo-código, obteremos de forma expandida algo como isto:

 factor1 = ConstantNode(1) //   ,    factor2 = ConstantNode(3) product = OperatorNode<'*'>(factor1, factor2) start = product 

Cada nó, começando do topo (exceto os mais baixos, que são essencialmente números inteiros aqui), é expresso por nós subsequentes. E a única chamada para o método Evalu () no elemento raiz resolve todo o problema, maravilhoso!

Então qi :: space_type chama sua atenção - esse argumento é uma lista de elementos ignorados ao analisar. Isso ainda será um truque para mim :-).

O que é notável aqui é a maneira de priorizar a multiplicação sobre a adição, simplesmente expressando o início não terminal (apenas contendo +) via produto (*). Na minha variante gramatical, uma vez que foi decidido que E prevaleceria sobre Ou, simplesmente substituo os operadores lógicos necessários nos lugares certos. Se é difícil cometer erros ao escrever operadores matemáticos, os operadores lógicos textuais são uma história completamente diferente. Há um desejo de resolver pelo menos parte dos possíveis problemas, por exemplo, o registro. Para isso, o Spirit possui um tipo embutido qi :: no_case

Além disso, em vez de números, precisarei dos nomes dos campos, portanto adicionamos o não terminal correspondente em vez do qi :: int_ spirit interno :

 field = qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9"); 

E chegamos aqui a uma expressão tão simples (até agora nenhuma operação semântica):

 start = product >> qi::no_case["OR"] >> start | product; product = factor >> qi::no_case["AND"] >> product | factor; factor = group | field; group %= '(' >> start >> ')'; 

Agora tudo está pronto para analisar a frase mais simples "campo E campo2" . Começamos e ... nada funciona.

O problema estava em um lugar inesperado: qi :: space_type não apenas ignora os espaços, os remove da sentença antes da análise e a expressão inicial do filtro entra na análise já no formato:

 "fieldAndfield2" \\        ,    "(5 * 5) + 11 " \\  "(5*5)+11" 

Este é apenas um único campo. Consequentemente, você precisa de um skipper:

 skipper = +qi::lit(' '); //    . ,    ,   ,  ,  C++ . start = product >> skipper >> qi::no_case["OR"] >> skipper >> start | product; ... 

Após analisar os campos, é possível aprender como obter valores de expressões e entender como o campo deve ser validado com relação ao valor. Todas as opções de comparação podem ser expressas através das seguintes operações:

 enum class Operator { EQ, //  LT, //  GT, //  CP //  (  ) }; unary = qi::no_case["NOT"]; // ,          

E os próprios valores são expressos em um termo não-terminal:

 value = qi::double_ | qi::int_ | qi::bool_ | string; string = qi::lit("'") >> +qi::char_("a-zA-Z0-9_. ") >> qi::lit("'"); 

Agora, para os problemas que esse método de obtenção de valor traz. O Spirit o retornará na forma de boost :: variant <int, double, bool, std :: string> e, quando chegar a hora de compará-lo com alguns dados, serão necessários alguns truques para obter o valor do tipo desejado. Aqui está a opção que eu vim:

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

Por que um getter retorna um objeto Json? Portanto, ao comparar valores durante a filtragem, evitarei descobrir qual tipo de dados a comparação está passando, deixando todo o trabalho para a biblioteca json.

A linha de chegada. Descrição da matéria. Usaremos o mesmo exemplo com uma calculadora. Para começar, precisamos de uma abstração, que passaremos para a gramática, e o Espírito gentilmente a preencherá conosco:

 class AbstractMatcher { public: AbstractMatcher() = default; virtual ~AbstractMatcher() = default; virtual bool evaluate(const Json &object) = 0; //       }; using MatcherPtr = std::shared_ptr<AbstractMatcher>; 

Nós lógicos adicionais são os principais nós de filtro:

 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); } }; 

E, finalmente, os nós inferiores

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

Resta apenas juntar tudo:

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

Isso é tudo. Agora, obter o filtro acabado se tornou uma operação bastante simples:

 MatcherPtr matcher; std::string filter = "int not LT 15"; JsonFilterGrammar grammar; qi::parse(filter.begin(), filter.end(), grammar, matcher); //     matcher   . 

Omitirei o processo de agrupar a gramática em um functor (não acho que seja interessante para ninguém). É melhor considerar a ferramenta em ação usando o exemplo mais simples:

 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; 

Aqui está a saída:

 [{"int":10},{"int":11},{"int":20},{"int":30},{"int":9}] [{"int":20},{"int":30}] 

Espero, queridos leitores, que você também tenha interesse em conhecer o básico do Espírito, assim como eu. Então eu permaneço. Até breve.