Bonjour, chers collègues. Je suis toujours développeur ISPsystem et je m'appelle Dmitry Smirnov. Pendant un certain temps (plutôt long), je n'ai pas pu décider du sujet de la prochaine publication, car beaucoup de matériel s'est accumulé au cours des derniers mois de travail avec Boost.Asio. Et même à ce moment où il semblait qu'il était plus facile de lancer une pièce, une tâche a tout changé. Il était nécessaire de développer un outil permettant au frontend de filtrer les données dans les listes demandées. La liste elle-même depuis le backend est un json_array ordinaire. Bienvenue chez Kat, il y a tous les hauts et les bas de ces derniers jours.
Clause de non-responsabilité
Je dois dire tout de suite que la dernière fois que l'auteur a "ressenti" quelque chose comme une grammaire sans contexte il y a dix ans. Ensuite, cela semblait être une sorte d'outil plutôt embrouillé et inutile, mais j'ai découvert la bibliothèque Boost.Spirit le jour de l'énoncé du problème.
Défi
Besoin de transformer une requête comme:
(string_field CP value AND int_field NOT LT 150) OR bool_field EQ true
Dans une structure qui vérifiera l'objet json et indiquera s'il satisfait aux exigences ou non.
Premiers pas
Tout d'abord, vous devez décider de l'interface du futur filtre. Il est nécessaire de supprimer les objets inutiles du tableau, il doit donc être combiné avec les algorithmes STL, en particulier std :: remove_if.
Un foncteur sera parfait, qui sera construit directement à partir de la demande de l'avant. Comme le projet utilise nlohmann :: json, le design sera assez élégant:
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());
Pour une utilisation pratique du filtre, j'ai choisi de diviser les conditions en un arbre binaire. Les sommets les plus bas doivent contenir des opérateurs de comparaison, mais les autres doivent être des opérateurs logiques. Voici à quoi ressemblera le filtre ci-dessus dans un état démonté:
Le résultat était une forme d' AST , si vous pouvez l'appeler ainsi. Maintenant que l'image de la logique à venir a pris forme, le moment est venu pour le plus intéressant et le plus terrible. Cela doit être écrit ... Sur l'Esprit ...
Connaissance
La question la plus difficile s'est posée: par où commencer? Contrairement à Asio, la lecture des en-têtes Spirit ne donne aucun indice clair, en d'autres termes - il y a "une sorte de magie". Cela a été suivi d'une étude d'exemples dans la documentation officielle du boost et de toutes sortes d'exemples sur le réseau, qui après un certain temps ont apporté non seulement leurs fruits, mais une solution aussi proche que possible de mes besoins: calculatrice AST
Regardons la grammaire présentée dans l'exemple:
Calculatrice de grammaire 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 grammaire est héritée de la base qi :: grammar. ASTNodePtr () n'est pas un moyen évident, mais très pratique de passer un objet du résultat attendu dans un objet de grammaire.
Calculateur de nœuds AST 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;
À l'aide de la bibliothèque Boost.Phoenix, vous pouvez créer un nœud AST prêt à l'emploi à partir d'un ou plusieurs non-terminaux directement pendant l'analyse et écrire directement dans le résultat. Examinons de plus près en quoi consiste la calculatrice:
start = (product >> '+' >> start)[qi::_val = phx::new_<OperatorNode<'+'>> (qi::_1, qi::_2)] | product[qi::_val = qi::_1];
start - commence à analyser la phrase. Point de départ. Elle peut s'exprimer par la somme du produit et du début, ou simplement par le produit.
Notez l'action entre crochets pour chaque expression. C'est l'action qui doit être effectuée si l'analyse est réussie, si tout correspond. qi :: _ val est en fait boost :: spirit :: qi :: _ val est un espace réservé. Avec son aide, la réponse sera enregistrée dans le résultat. Dans le cas du démarrage, ce sera un objet OperatorNode, dont le premier argument sera le résultat de l'analyse du produit, et le second sera le résultat de l'analyse du démarrage.
Nous regardons plus loin. Supposons que nous tombions sur la deuxième option, le début n'est pas une somme, mais un produit. Comment s'exprime-t-il?
product = (factor >> '*' >> product) [qi::_val = phx::new_<OperatorNode<'*'>> (qi::_1, qi::_2)] | factor[qi::_val = qi::_1];
L'image précédente est répétée avec des différences minimes. Encore une fois, nous rencontrons une sorte d'expression, encore une fois, nous écrivons l'objet OperatorNode dans le résultat, ou simplement une sorte de facteur. Regardons ça.
factor = group[qi::_val = qi::_1] | qi::int_[qi::_val = phx::new_<ConstantNode>(qi::_1)];
Alors que nous suivons le chemin le plus court, nous supposons que nous n'avons rencontré personne d'autre que int. Maintenant, si nous décrivons toutes les étapes précédentes en pseudo-code, nous obtenons sous une forme développée quelque chose comme ceci:
factor1 = ConstantNode(1)
Chaque nœud, en commençant par le haut (à l'exception des plus bas, qui sont essentiellement des entiers ici), est exprimé par les nœuds suivants. Et le seul appel à la méthode assess () sur l'élément racine résout tout le problème, merveilleux!
Alors qi :: space_type attire votre attention - cet argument est une liste d'éléments ignorés lors de l'analyse. Cela me jouera toujours un tour :-).
Ce qui est remarquable ici, c'est la façon de prioriser la multiplication sur l'addition en exprimant simplement le début non terminal (contenant simplement +) via le produit (*). Dans ma variante grammaticale, puisqu'il a été décidé qu'Et prévaudrait sur Or, je remplace simplement les opérateurs logiques requis aux bons endroits. S'il est difficile de faire des erreurs dans l'écriture d'opérateurs mathématiques, les opérateurs logiques textuels sont une histoire complètement différente. Il existe un désir de résoudre au moins une partie des problèmes possibles, par exemple le registre. Pour cela, Spirit a un type intégré qi :: no_case
De plus, au lieu de nombres, j'aurai besoin des noms des champs, donc nous ajoutons le non terminal correspondant au lieu de l'esprit qi :: int_ intégré:
field = qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9");
Et nous obtenons ici une expression si simple (jusqu'à présent, aucune opération sémantique):
start = product >> qi::no_case["OR"] >> start | product; product = factor >> qi::no_case["AND"] >> product | factor; factor = group | field; group %= '(' >> start >> ')';
Maintenant, tout est prêt pour analyser la phrase la plus simple "champ et champ2" . Nous commençons et ... rien ne fonctionne.
Le problème s'est avéré être à un endroit inattendu: qi :: space_type ignore non seulement les espaces, il les supprime de la phrase avant l'analyse, et l'expression de filtre initiale entre en analyse déjà sous la forme:
"fieldAndfield2" \\ , "(5 * 5) + 11 " \\ "(5*5)+11"
Ce n'est qu'un seul champ. En conséquence, vous avez besoin d'un skipper:
skipper = +qi::lit(' ');
Après avoir analysé les champs, il est possible d'apprendre à obtenir des valeurs à partir d'expressions et à comprendre comment le champ doit être validé par rapport à la valeur. Toutes les options de comparaison peuvent être exprimées par les opérations suivantes:
enum class Operator { EQ,
Et les valeurs elles-mêmes sont exprimées dans un tel non-terminal:
value = qi::double_ | qi::int_ | qi::bool_ | string; string = qi::lit("'") >> +qi::char_("a-zA-Z0-9_. ") >> qi::lit("'");
Passons maintenant aux problèmes qu'une telle méthode d'obtention de valeur apporte. Spirit le renverra sous la forme de boost :: variant <int, double, bool, std :: string> , et lorsque le moment sera venu de le comparer avec certaines données, certaines astuces seront nécessaires pour obtenir la valeur du type souhaité. Voici à quelle option je suis arrivé:
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; } };
Pourquoi un getter retourne-t-il un objet Json? Ainsi, lors de la comparaison des valeurs pendant le filtrage, j'éviterai d'avoir à déterminer le type de données que la comparaison traverse, en laissant tout le travail à la bibliothèque json.
La ligne d'arrivée. Description du match lui-même. Nous utiliserons le même exemple avec une calculatrice. Pour commencer, nous avons besoin d'une abstraction, que nous passerons dans la grammaire, et l'Esprit la remplira gentiment avec nous:
class AbstractMatcher { public: AbstractMatcher() = default; virtual ~AbstractMatcher() = default; virtual bool evaluate(const Json &object) = 0;
D'autres nœuds logiques sont les principaux nœuds de filtre:
Noeud logique 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); } };
Et enfin, les nœuds inférieurs
Comparaison de valeur 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; } };
Il ne reste plus qu'à mettre tout cela ensemble:
Filtre 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;
C’est tout. Maintenant, obtenir le filtre fini est devenu une opération assez simple:
MatcherPtr matcher; std::string filter = "int not LT 15"; JsonFilterGrammar grammar; qi::parse(filter.begin(), filter.end(), grammar, matcher);
Je vais omettre le processus d'envelopper la grammaire dans un foncteur (je ne pense pas que cela sera intéressant pour personne). Nous allons mieux considérer l'outil en action en utilisant l'exemple le plus 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;
Voici la sortie:
[{"int":10},{"int":11},{"int":20},{"int":30},{"int":9}] [{"int":20},{"int":30}]
J'espère, chers lecteurs, que vous souhaitiez également connaître les bases de l'Esprit aussi bien que moi. Alors je reste. A bientôt.