Impulsar el espíritu o agregar "espiritualidad" a los filtros de lista

Buen día, colegas. Todavía soy un desarrollador de sistemas ISP, y mi nombre sigue siendo Dmitry Smirnov. Durante un tiempo (bastante largo) no pude decidir sobre el tema de la próxima publicación, ya que se ha acumulado mucho material en los últimos meses de trabajo con Boost.Asio. E incluso en ese momento cuando parecía que era más fácil lanzar una moneda, una tarea cambió todo. Fue necesario desarrollar una herramienta que permita a la interfaz filtrar datos en las listas solicitadas. La lista misma del backend es un json_array ordinario. Bienvenido a Kat, hay todos los altibajos de los últimos días.

Descargo de responsabilidad

Debo decir de inmediato que la última vez que el autor "sintió" algo así como una gramática libre de contexto hace diez años. Entonces parecía una herramienta bastante innecesaria, pero aprendí sobre la biblioteca Boost.Spirit el día de la declaración del problema.

Desafío

Necesita activar una consulta como:

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

En alguna estructura que verificará el objeto json e informará si cumple con los requisitos o no.

Primeros pasos

En primer lugar, debe decidir sobre la interfaz del filtro futuro. Es necesario eliminar objetos innecesarios de la matriz, por lo que debe combinarse con algoritmos STL, en particular std :: remove_if.

Un functor será perfecto, que se construirá directamente a partir de la solicitud desde el frente. Como el proyecto usa nlohmann :: json, el diseño 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 un uso conveniente del filtro, elegí dividir las condiciones en un árbol binario. Los vértices más bajos deben contener operadores de comparación, pero el resto deben ser operadores lógicos. Así es como se verá el filtro anterior en un estado desmontado:

El resultado fue una forma de AST , si puede llamarlo así. Ahora que la imagen de la próxima lógica ha tomado forma, ha llegado el momento de lo más interesante y terrible. Esto debe estar escrito ... Sobre el Espíritu ...

Conocido

La pregunta más difícil surgió: ¿por dónde empezar? A diferencia de Asio, leer encabezados de Spirit no dio pistas claras, en otras palabras, hay "algún tipo de magia". Esto fue seguido por un estudio de ejemplos en la documentación oficial del impulso y todo tipo de ejemplos en la red, que después de un tiempo trajo no solo sus frutos, sino una solución lo más cercana posible a mis necesidades: calculadora AST

Veamos la gramática presentada en el ejemplo:

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

La gramática se hereda de la base qi :: grammar. ASTNodePtr () no es una forma obvia, pero muy conveniente de pasar un objeto del resultado esperado a un 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 la biblioteca Boost.Phoenix, puede crear un nodo AST listo a partir de uno o varios no terminales justo durante el análisis y escribir directamente en el resultado. Echemos un vistazo más de cerca en qué consiste la calculadora:

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

start: comienza a analizar la oración. Punto de partida Se puede expresar a través de la suma del producto y el inicio, o simplemente a través del producto.

Tenga en cuenta la acción entre corchetes para cada expresión. Esta es la acción que debe realizarse si el análisis es exitoso, si todo coincide. qi :: _ val es realmente boost :: spirit :: qi :: _ val es un marcador de posición. Con su ayuda, la respuesta se registrará en el resultado. En el caso del inicio, este será un objeto OperatorNode, cuyo primer argumento será el resultado del análisis del producto, y el segundo será el resultado del inicio del análisis.

Nosotros miramos más allá. Supongamos que encontramos la segunda opción, comenzar no es una suma, sino un producto. ¿Cómo se expresa?

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

La imagen anterior se repite con mínimas diferencias. Nuevamente encontramos algún tipo de expresión, nuevamente escribimos el objeto OperatorNode en el resultado, o simplemente algún tipo de factor. Miremoslo.

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

A medida que avanzamos por el camino más corto, asumimos que nos encontramos con nada menos que int. Ahora, si describimos todos los pasos anteriores en pseudocódigo, obtenemos en forma expandida algo como esto:

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

Cada nodo, comenzando desde la parte superior (excepto los más bajos, que son esencialmente enteros aquí), se expresa a través de nodos posteriores. Y la única llamada al método Evaluation () en el elemento raíz resuelve todo el problema, ¡maravilloso!

Entonces qi :: space_type llama tu atención: este argumento es una lista de elementos ignorados al analizar. Esto todavía me jugará un truco :-).

Lo que es notable aquí es la forma de priorizar la multiplicación sobre la suma simplemente expresando el inicio no terminal (solo que contiene +) a través del producto (*). En mi variante gramatical, ya que se decidió que Y prevalecería sobre O, simplemente sustituyo los operadores lógicos requeridos en los lugares correctos. Si es difícil cometer errores al escribir operadores matemáticos, los operadores lógicos textuales son una historia completamente diferente. Existe el deseo de resolver al menos parte de los posibles problemas, por ejemplo, el registro. Para esto, Spirit tiene un tipo incorporado qi :: no_case

Además, en lugar de números, necesitaré los nombres de los campos, por lo que agregamos el no terminal correspondiente en lugar del qi :: int_ spirit incorporado:

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

Y obtenemos aquí una expresión tan simple (hasta ahora no hay operaciones semánticas):

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

Ahora todo está listo para analizar la oración más simple "campo Y campo2" . Comenzamos y ... nada funciona.

El problema resultó estar en un lugar inesperado: qi :: space_type no solo ignora los espacios, sino que los elimina de la oración antes del análisis, y la expresión de filtro inicial entra en análisis ya en la forma:

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

Este es solo un campo único. En consecuencia, necesitas un patrón:

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

Después de analizar los campos, es posible aprender cómo obtener valores de las expresiones y comprender cómo se debe validar el campo contra el valor. Todas las opciones de comparación se pueden expresar a través de las siguientes operaciones:

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

Y los valores en sí mismos se expresan en tal no terminal:

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

Ahora a los problemas que trae tal método de obtener valor. Spirit lo devolverá en forma de boost :: variant <int, double, bool, std :: string> , y cuando llegue el momento de compararlo con algunos datos, se necesitarán ciertos trucos para obtener el valor del tipo deseado. Aquí es a qué opción vine:

 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 qué un getter devuelve un objeto Json? Por lo tanto, al comparar valores durante el filtrado, evitaré tener que averiguar qué tipo de datos está pasando la comparación, dejando todo el trabajo a la biblioteca json.

La linea de meta. Descripción del mismo matcher. Usaremos el mismo ejemplo con una calculadora. Para comenzar, necesitamos una abstracción, que pasaremos a la gramática, y el Espíritu la llenará amablemente con nosotros:

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

Otros nodos lógicos son los nodos de filtro principales:

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

Y finalmente, los nodos 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; } }; 

Solo queda juntarlo todo:

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

Eso es todo Ahora obtener el filtro terminado se ha convertido en una operación bastante simple:

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

Omitiré el proceso de envolver la gramática en un functor (no creo que sea interesante para nadie). Consideraremos mejor la herramienta en acción usando el ejemplo más simple:

 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; 

Aquí está la salida:

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

Espero, queridos lectores, que también estén interesados ​​en conocer los conceptos básicos del Espíritu, así como yo. Entonces me quedo. Hasta pronto.