Guten Tag, Kollegen. Ich bin immer noch ein ISP-Systementwickler und heiße immer noch Dmitry Smirnov. Für einige (ziemlich lange) Zeit konnte ich mich nicht für das Thema der nächsten Veröffentlichung entscheiden, da sich in den letzten Monaten der Arbeit mit Boost.Asio viel Material angesammelt hat. Und selbst in dem Moment, als es einfacher schien, eine Münze zu werfen, änderte eine Aufgabe alles. Es musste ein Tool entwickelt werden, mit dem das Frontend Daten in den angeforderten Listen filtern kann. Die Liste selbst aus dem Backend ist ein gewöhnliches json_array. Willkommen bei kat, es gibt alle Höhen und Tiefen der letzten Tage.
Haftungsausschluss
Ich muss gleich sagen, dass der Autor vor zehn Jahren das letzte Mal so etwas wie eine kontextfreie Grammatik "gefühlt" hat. Dann schien es eine Art verschwommenes und unnötiges Werkzeug zu sein, aber ich erfuhr am Tag der Problemstellung von der Boost.Spirit-Bibliothek.
Herausforderung
Müssen Sie eine Abfrage wie folgt drehen:
(string_field CP value AND int_field NOT LT 150) OR bool_field EQ true
In eine Struktur, die das json-Objekt überprüft und meldet, ob es die Anforderungen erfüllt oder nicht.
Erste Schritte
Der erste Schritt besteht darin, die Schnittstelle des zukünftigen Filters festzulegen. Es ist notwendig, unnötige Objekte aus dem Array zu entfernen, daher muss es mit STL-Algorithmen kombiniert werden, insbesondere mit std :: remove_if.
Ein Funktor wird perfekt sein, der direkt von der Anfrage von vorne konstruiert wird. Da das Projekt nlohmann :: json verwendet, wird das Design recht elegant sein:
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());
Zur bequemen Verwendung des Filters habe ich beschlossen, die Bedingungen in einen Binärbaum aufzuteilen. Die niedrigsten Eckpunkte sollten Vergleichsoperatoren enthalten, der Rest sollten logische Operatoren sein. So sieht der obige Filter in einem zerlegten Zustand aus:
Das Ergebnis war eine Form von AST , wenn man es so nennen kann. Jetzt, da das Bild der bevorstehenden Logik Gestalt angenommen hat, ist der Moment für das Interessanteste und Schrecklichste gekommen. Dies muss geschrieben werden ... On Spirit ...
Bekanntschaft
Die schwierigste Frage stellte sich: Wo soll ich anfangen? Im Gegensatz zu Asio gab das Lesen von Spirit-Headern keine klaren Hinweise, mit anderen Worten - es gibt "irgendeine Art von Magie". Es folgte eine Untersuchung von Beispielen in der offiziellen Dokumentation des Boosts und allerlei Beispiele im Netzwerk, die nach einiger Zeit nicht nur ihre Früchte brachten, sondern auch eine Lösung, die meinen Bedürfnissen so nahe wie möglich kam: den AST-Rechner
Schauen wir uns die im Beispiel dargestellte Grammatik an:
Grammatikrechner 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; };
Die Grammatik wird von der Basis qi :: grammar geerbt. ASTNodePtr () ist keine offensichtliche, aber sehr bequeme Möglichkeit, ein Objekt des erwarteten Ergebnisses an ein Grammatikobjekt zu übergeben.
AST-Knotenrechner 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;
Mit der Boost.Phoenix-Bibliothek können Sie direkt während des Parsens einen vorgefertigten AST-Knoten aus einem oder mehreren Nicht-Terminals erstellen und direkt in das Ergebnis schreiben. Schauen wir uns genauer an, woraus der Taschenrechner besteht:
start = (product >> '+' >> start)[qi::_val = phx::new_<OperatorNode<'+'>> (qi::_1, qi::_2)] | product[qi::_val = qi::_1];
start - beginne den Satz zu analysieren. Ausgangspunkt. Es kann durch die Summe von Produkt und Start oder einfach durch Produkt ausgedrückt werden.
Beachten Sie die Aktion in eckigen Klammern für jeden Ausdruck. Dies ist die Aktion, die ausgeführt werden sollte, wenn die Analyse erfolgreich ist und alles übereinstimmt. qi :: _ val ist eigentlich boost :: spirit :: qi :: _ val ist ein Platzhalter. Mit seiner Hilfe wird die Antwort im Ergebnis festgehalten. Im Fall von start ist dies ein OperatorNode-Objekt, dessen erstes Argument das Ergebnis des Parsing-Produkts und das zweite das Ergebnis des Parsing-Starts ist.
Wir schauen weiter. Angenommen, wir stoßen auf die zweite Option: Start ist keine Summe, sondern ein Produkt. Wie drückt er sich aus?
product = (factor >> '*' >> product) [qi::_val = phx::new_<OperatorNode<'*'>> (qi::_1, qi::_2)] | factor[qi::_val = qi::_1];
Das vorherige Bild wird mit minimalen Unterschieden wiederholt. Wieder treffen wir auf eine Art Ausdruck, wieder schreiben wir das OperatorNode-Objekt in das Ergebnis oder nur auf eine Art Faktor. Schauen wir es uns an.
factor = group[qi::_val = qi::_1] | qi::int_[qi::_val = phx::new_<ConstantNode>(qi::_1)];
Auf dem kürzesten Weg gehen wir davon aus, dass wir keinen anderen als int getroffen haben. Wenn wir nun alle vorherigen Schritte im Pseudocode beschreiben, erhalten wir in einer erweiterten Form ungefähr Folgendes:
factor1 = ConstantNode(1)
Jeder Knoten, beginnend von oben (mit Ausnahme der niedrigsten, die hier im Wesentlichen ganze Zahlen sind), wird durch nachfolgende Knoten ausgedrückt. Und der einzige Aufruf der evalu () -Methode für das Root-Element löst das ganze Problem, wunderbar!
Dann fällt qi :: space_type auf - dieses Argument ist eine Liste von Elementen, die beim Parsen ignoriert werden. Das wird mir immer noch einen Streich spielen :-).
Bemerkenswert ist hier die Möglichkeit, die Multiplikation gegenüber der Addition zu priorisieren, indem einfach der nicht terminale Start (der nur + enthält) über das Produkt (*) ausgedrückt wird. In meiner Grammatikvariante ersetze ich einfach die erforderlichen logischen Operatoren an den richtigen Stellen, da entschieden wurde, dass Und sich gegen Or durchsetzen würde. Wenn es schwierig ist, Fehler beim Schreiben mathematischer Operatoren zu machen, sind textuelle logische Operatoren eine ganz andere Geschichte. Es besteht der Wunsch, zumindest einen Teil der möglichen Probleme zu lösen, beispielsweise das Register. Dafür hat Spirit einen eingebauten Typ qi :: no_case
Außerdem benötige ich anstelle von Zahlen die Namen der Felder, sodass wir anstelle des integrierten qi :: int_ spirit das entsprechende Nichtterminal hinzufügen:
field = qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9");
Und wir bekommen hier einen so einfachen Ausdruck (bisher keine semantischen Operationen):
start = product >> qi::no_case["OR"] >> start | product; product = factor >> qi::no_case["AND"] >> product | factor; factor = group | field; group %= '(' >> start >> ')';
Jetzt ist alles bereit, um den einfachsten Satz "Feld und Feld2" zu analysieren. Wir fangen an und ... nichts funktioniert.
Das Problem stellte sich an einem unerwarteten Ort heraus: qi :: space_type ignoriert nicht nur Leerzeichen, sondern entfernt sie vor dem Parsen aus dem Satz, und der anfängliche Filterausdruck wird bereits in der folgenden Form analysiert:
"fieldAndfield2" \\ , "(5 * 5) + 11 " \\ "(5*5)+11"
Dies ist nur ein einziges Feld. Dementsprechend benötigen Sie einen Skipper:
skipper = +qi::lit(' ');
Nach der Analyse der Felder können Sie lernen, wie Sie Werte aus Ausdrücken abrufen und wie das Feld anhand des Werts validiert werden sollte. Alle Vergleichsoptionen können durch die folgenden Operationen ausgedrückt werden:
enum class Operator { EQ,
Und die Werte selbst werden in einem solchen Nichtterminal ausgedrückt:
value = qi::double_ | qi::int_ | qi::bool_ | string; string = qi::lit("'") >> +qi::char_("a-zA-Z0-9_. ") >> qi::lit("'");
Nun zu den Problemen, die eine solche Methode zur Wertschöpfung mit sich bringt. Spirit gibt es in Form von boost :: variante <int, double, bool, std :: string> zurück . Wenn es Zeit ist, es mit einigen Daten zu vergleichen, sind bestimmte Tricks erforderlich, um den Wert des gewünschten Typs zu erhalten. Zu welcher Option bin ich gekommen:
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; } };
Warum gibt ein Getter ein Json-Objekt zurück? Wenn ich also Werte während des Filterns vergleiche, muss ich nicht herausfinden, welchen Datentyp der Vergleich durchläuft, und die gesamte Arbeit der json-Bibliothek überlassen.
Die Ziellinie. Beschreibung des Matchers selbst. Wir werden das gleiche Beispiel mit einem Taschenrechner verwenden. Zunächst brauchen wir eine Abstraktion, die wir in die Grammatik einfließen lassen, und Spirit wird sie freundlicherweise mit uns füllen:
class AbstractMatcher { public: AbstractMatcher() = default; virtual ~AbstractMatcher() = default; virtual bool evaluate(const Json &object) = 0;
Weitere logische Knoten sind die Hauptfilterknoten:
Logischer Knoten 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); } };
Und schließlich die unteren Knoten
Wertevergleich 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; } };
Es bleibt nur, um alles zusammenzufügen:
Json Filter 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;
Das ist alles. Jetzt ist es ziemlich einfach, den fertigen Filter zu erhalten:
MatcherPtr matcher; std::string filter = "int not LT 15"; JsonFilterGrammar grammar; qi::parse(filter.begin(), filter.end(), grammar, matcher);
Ich werde den Prozess des Einwickelns der Grammatik in einen Funktor weglassen (ich denke nicht, dass es für irgendjemanden interessant sein wird). Wir betrachten das Tool am besten anhand des einfachsten Beispiels in Aktion:
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;
Hier ist die Ausgabe:
[{"int":10},{"int":11},{"int":20},{"int":30},{"int":9}] [{"int":20},{"int":30}]
Ich hoffe, liebe Leser, Sie waren auch daran interessiert, die Grundlagen von Spirit sowie mich kennenzulernen. Dann bleibe ich. Bis bald.