Selamat siang, kolega. Saya masih seorang pengembang sistem ISP, dan nama saya masih Dmitry Smirnov. Untuk beberapa waktu (agak lama) saya tidak bisa memutuskan topik publikasi berikutnya, karena banyak materi telah terakumulasi selama beberapa bulan terakhir bekerja dengan Boost.Asio. Dan bahkan pada saat itu ketika tampaknya lebih mudah untuk melempar koin, satu tugas mengubah segalanya. Itu perlu untuk mengembangkan alat yang memungkinkan ujung depan untuk menyaring data dalam daftar yang diminta. Daftar itu sendiri dari backend adalah json_array biasa. Selamat datang di kat, ada semua pasang surut beberapa hari terakhir.
Penafian
Saya harus segera mengatakan bahwa terakhir kali penulis "merasakan" sesuatu seperti tata bahasa bebas konteks sepuluh tahun yang lalu. Kemudian itu tampak seperti semacam alat yang agak cadel dan tidak perlu, tetapi saya belajar tentang Boost. Perpustakaan Spirit pada hari yang sama dengan pernyataan masalah.
Tantangan
Perlu mengubah kueri seperti:
(string_field CP value AND int_field NOT LT 150) OR bool_field EQ true
Menjadi beberapa struktur yang akan memeriksa objek json dan melaporkan apakah memenuhi persyaratan atau tidak.
Langkah pertama
Pertama-tama, Anda perlu memutuskan antarmuka filter di masa depan. Hal ini diperlukan untuk menghapus objek yang tidak perlu dari array, sehingga harus dikombinasikan dengan algoritma STL, khususnya std :: remove_if.
Seorang functor akan sempurna, yang akan dibangun langsung dari permintaan dari depan. Karena proyek ini menggunakan nlohmann :: json, desainnya akan cukup elegan:
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());
Untuk memudahkan penggunaan filter, saya memilih untuk membagi kondisi menjadi pohon biner. Simpul terendah harus berisi operator pembanding, tetapi sisanya harus operator logis. Ini adalah bagaimana filter di atas akan terlihat dalam keadaan dibongkar:
Hasilnya adalah bentuk AST , jika Anda bisa menyebutnya begitu. Sekarang gambar dari logika yang akan datang telah mengambil bentuk, saatnya telah tiba untuk yang paling menarik dan mengerikan. Ini harus ditulis ... On Spirit ...
Kenalan
Pertanyaan paling sulit muncul: dari mana harus memulai? Tidak seperti Asio, membaca header Spirit tidak memberikan petunjuk yang jelas, dengan kata lain - ada "semacam sihir." Ini diikuti oleh studi tentang contoh-contoh dalam dokumentasi resmi tentang dorongan dan semua jenis contoh di jaringan, yang setelah beberapa waktu tidak hanya membawa buah-buahnya, tetapi solusi sedekat mungkin dengan kebutuhan saya: AST kalkulator
Mari kita lihat tata bahasa yang disajikan dalam contoh:
Kalkulator Tata Bahasa 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; };
Tata bahasa diwariskan dari basis qi :: tata bahasa. ASTNodePtr () bukan cara yang jelas, tetapi sangat nyaman untuk melewatkan objek dari hasil yang diharapkan ke objek tata bahasa.
Kalkulator simpul 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;
Menggunakan perpustakaan Boost.Phoenix, Anda bisa membuat simpul AST yang sudah jadi dari satu atau beberapa non-terminal tepat selama parsing dan menulis langsung ke hasilnya. Mari kita lihat lebih dekat apa yang terdiri dari kalkulator:
start = (product >> '+' >> start)[qi::_val = phx::new_<OperatorNode<'+'>> (qi::_1, qi::_2)] | product[qi::_val = qi::_1];
mulai - mulai parsing kalimat. Titik awal. Ini dapat diekspresikan melalui jumlah produk dan mulai, atau hanya melalui produk.
Catat tindakan dalam tanda kurung siku untuk setiap ekspresi. Ini adalah tindakan yang harus dilakukan jika parsing berhasil, jika semuanya cocok. qi :: _ val sebenarnya adalah boost :: spirit :: qi :: _ val adalah placeholder. Dengan bantuannya, jawabannya akan dicatat dalam hasilnya. Dalam kasus mulai, ini akan menjadi objek OperatorNode, yang argumen pertamanya akan menjadi hasil parsing produk, dan yang kedua adalah hasil parsing start.
Kami melihat lebih jauh. Misalkan kita menemukan pilihan kedua, mulai bukan jumlah, tetapi produk. Bagaimana dia diungkapkan?
product = (factor >> '*' >> product) [qi::_val = phx::new_<OperatorNode<'*'>> (qi::_1, qi::_2)] | factor[qi::_val = qi::_1];
Gambar sebelumnya diulang dengan perbedaan minimal. Sekali lagi kita bertemu semacam ekspresi, lagi-lagi kita menulis objek OperatorNode di hasilnya, atau hanya semacam faktor. Mari kita melihatnya.
factor = group[qi::_val = qi::_1] | qi::int_[qi::_val = phx::new_<ConstantNode>(qi::_1)];
Saat kita menempuh jalan terpendek, kita berasumsi bahwa kita bertemu tidak lain dari int. Sekarang, jika kita menggambarkan semua langkah sebelumnya dalam pseudo-code, kita mendapatkan sesuatu yang diperluas seperti ini:
factor1 = ConstantNode(1)
Setiap node, mulai dari atas (kecuali yang terendah, yang pada dasarnya adalah bilangan bulat di sini), diekspresikan melalui node berikutnya. Dan satu-satunya panggilan ke metode evalu () pada elemen root menyelesaikan seluruh masalah, luar biasa!
Kemudian qi :: space_type menarik perhatian Anda - argumen ini adalah daftar elemen yang diabaikan saat parsing. Ini masih akan mempermainkan saya :-).
Apa yang luar biasa di sini adalah cara untuk memprioritaskan multiplikasi daripada penambahan dengan hanya mengekspresikan awal nonterminal (hanya berisi +) melalui produk (*). Dalam varian tata bahasa saya, karena diputuskan bahwa Dan akan menang atas Atau, saya hanya mengganti operator logis yang diperlukan di tempat yang tepat. Jika sulit untuk membuat kesalahan dalam menulis operator matematika, maka operator logis tekstual adalah cerita yang sama sekali berbeda. Ada keinginan untuk menyelesaikan setidaknya sebagian dari masalah yang mungkin terjadi, misalnya register. Untuk ini, Spirit memiliki tipe qi :: no_case bawaan
Selanjutnya, alih-alih angka, saya akan membutuhkan nama-nama bidang, jadi kami menambahkan nonterminal yang sesuai sebagai ganti built-in qi :: int_ spirit:
field = qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9");
Dan kami sampai di sini ungkapan sederhana (sejauh ini tidak ada operasi semantik):
start = product >> qi::no_case["OR"] >> start | product; product = factor >> qi::no_case["AND"] >> product | factor; factor = group | field; group %= '(' >> start >> ')';
Sekarang semuanya siap untuk menguraikan kalimat paling sederhana "bidang Dan bidang2" . Kita mulai dan ... tidak ada yang berhasil.
Masalahnya ternyata berada di tempat yang tidak terduga: qi :: space_type tidak hanya mengabaikan spasi, ia menghilangkannya dari kalimat sebelum parsing, dan ekspresi filter awal menjadi parsing sudah dalam bentuk:
"fieldAndfield2" \\ , "(5 * 5) + 11 " \\ "(5*5)+11"
Ini hanya satu bidang tunggal. Karena itu, Anda perlu beberapa nakhoda:
skipper = +qi::lit(' ');
Setelah menganalisis bidang, dimungkinkan untuk mempelajari cara mendapatkan nilai dari ekspresi dan memahami bagaimana bidang harus divalidasi terhadap nilai. Semua opsi perbandingan dapat diekspresikan melalui operasi berikut:
enum class Operator { EQ,
Dan nilai-nilai itu sendiri diekspresikan dalam bentuk nonterminal:
value = qi::double_ | qi::int_ | qi::bool_ | string; string = qi::lit("'") >> +qi::char_("a-zA-Z0-9_. ") >> qi::lit("'");
Sekarang untuk masalah yang membawa metode semacam itu nilai. Spirit akan mengembalikannya dalam bentuk boost :: varian <int, double, bool, std :: string> , dan ketika saatnya tiba untuk membandingkannya dengan beberapa data, diperlukan trik tertentu untuk mendapatkan nilai dari tipe yang diinginkan. Inilah opsi yang saya datangi:
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; } };
Mengapa seorang pengambil mengembalikan objek Json? Jadi, ketika membandingkan nilai-nilai selama pemfilteran, saya akan menghindari harus mencari tahu tipe data apa yang akan dilakukan perbandingan, meninggalkan semua pekerjaan ke pustaka json.
Garis finish. Deskripsi pencocokan dirinya sendiri. Kami akan menggunakan contoh yang sama dengan kalkulator. Untuk memulainya, kita membutuhkan abstraksi, yang akan kita sampaikan ke dalam tata bahasa, dan Roh dengan baik hati akan mengisinya dengan kita:
class AbstractMatcher { public: AbstractMatcher() = default; virtual ~AbstractMatcher() = default; virtual bool evaluate(const Json &object) = 0;
Node logis lebih lanjut adalah node filter utama:
Node logis 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); } };
Dan akhirnya, simpul bawah
Perbandingan Nilai 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; } };
Tinggal menyatukan semuanya:
Filter 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;
Itu saja. Sekarang mendapatkan filter selesai telah menjadi operasi yang cukup sederhana:
MatcherPtr matcher; std::string filter = "int not LT 15"; JsonFilterGrammar grammar; qi::parse(filter.begin(), filter.end(), grammar, matcher);
Saya akan menghilangkan proses pembungkus tata bahasa dalam sebuah functor (saya pikir itu tidak akan menarik bagi siapa pun). Kami akan lebih baik mempertimbangkan alat dalam aksi menggunakan contoh paling sederhana:
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;
Berikut hasilnya:
[{"int":10},{"int":11},{"int":20},{"int":30},{"int":9}] [{"int":20},{"int":30}]
Saya harap, para pembaca yang budiman, Anda juga tertarik untuk mengetahui dasar-dasar Roh serta saya. Lalu saya tetap tinggal. Sampai ketemu lagi.