Get best of the week

Cara memanjat pohon

Gambar 2

Lebih tepatnya, bagaimana turun dari situ. Tetapi hal pertama yang pertama. Artikel ini sedikit keluar dari format artikel biasa dari PVS-Studio. Kami sering menulis tentang memeriksa proyek lain, tetapi hampir tidak pernah membuka pintu dapur bagian dalam kami. Sudah waktunya untuk memperbaikinya dan berbicara tentang bagaimana penganalisa dibangun dari dalam. Lebih tepatnya, tentang yang paling penting dari bagian-bagiannya - pohon sintaks. Artikel ini akan fokus pada bagian PVS-Studio yang berhubungan dengan bahasa C dan C ++.

Hal pertama yang pertama


Sintaksis pohon adalah bagian pusat dari setiap kompiler. Dengan satu atau lain cara, kode perlu disajikan dalam bentuk yang nyaman untuk pemrosesan program, dan kebetulan struktur pohon paling cocok untuk ini. Saya tidak akan membahas teori di sini - cukuplah untuk mengatakan bahwa pohon sangat mencerminkan hierarki ekspresi dan blok dalam kode, dan pada saat yang sama hanya berisi data yang diperlukan untuk pekerjaan.

Apa yang harus dilakukan oleh kompiler dengan penganalisa statis? Faktanya adalah kedua alat ini memiliki banyak kesamaan. Pada tahap awal parsing kode, mereka melakukan pekerjaan yang sama. Pertama, kode dibagi menjadi aliran token, yang diumpankan ke parser. Kemudian, dalam proses analisis sintaksis dan semantik, token disusun menjadi pohon, yang dikirim lebih jauh di sepanjang pipa. Pada tahap ini, kompiler dapat melakukan optimasi menengah sebelum menghasilkan kode biner, analisa statis mulai melewati node dan meluncurkan berbagai pemeriksaan.

Dalam analisa PVS-Studio dengan pohon yang dibangun, beberapa hal terjadi:

  • . , , , using typedef, . , . ;
  • . , ;
  • , , , ;
  • . ( ). . , nullptr , , . ;
  • . , . , .

Jika Anda tertarik pada detail cara kerja analisis, saya sarankan membaca artikel " Teknologi yang Digunakan dalam Analyzer Kode PVS-Studio untuk Menemukan Kesalahan dan Kerentanan Potensial ". Beberapa poin dari daftar diperiksa di sana secara rinci.

Kami akan melihat lebih detail apa yang terjadi pada pohon di dalam alat analisis, dan bagaimana tampilannya sama sekali. Dengan pengantar singkat, saatnya untuk menyelesaikan masalah ini.

Gambar 1

Bagaimana itu bekerja


Secara historis, PVS-Studio menggunakan pohon biner untuk mewakili kode. Struktur data klasik ini akrab bagi semua orang - kami memiliki simpul yang umumnya merujuk pada dua anak. Node yang tidak seharusnya memiliki keturunan, saya akan memanggil terminal, semua yang lain - non-terminal. Dalam beberapa kasus nonterminal mungkin tidak memiliki simpul anak, tetapi perbedaan utama dari terminal adalah bahwa keturunan secara fundamental diperbolehkan untuk itu. Node terminal (atau dedaunan) tidak memiliki kemampuan untuk merujuk ke sesuatu selain orang tua.

Struktur yang digunakan dalam PVS-Studio sedikit berbeda dari pohon biner klasik - ini diperlukan untuk kenyamanan. Node terminal biasanya sesuai dengan kata kunci, nama variabel, literal, dan sebagainya. Non-terminal - berbagai jenis ekspresi, blok kode, daftar, dan sejenisnya, elemen penyusun pohon

Dari sudut pandang kompiler, semuanya cukup standar di sini, saya menyarankan semua orang tertarik dengan klasik genre - The Dragon Book .

Kami pindah. Mari kita lihat contoh kode sederhana dan bagaimana penganalisa melihatnya. Selanjutnya akan ada banyak gambar dari utilitas visualisasi pohon internal kami.

Sebenarnya, sebuah contoh:

int f(int a, int b)
{
  return a + b;
}

Fungsi sederhana ini setelah diproses oleh parser akan terlihat seperti ini (node ​​non-terminal disorot dengan warna kuning):

Gambar 6

Pandangan ini memiliki pro dan kontra, dan yang terakhir, menurut pendapat saya, sedikit lebih. Tapi mari kita lihat pohon itu. Segera buat reservasi yang agak berlebihan, misalnya, karena mengandung tanda baca dan tanda kurung. Dari sudut pandang kompilasi, ini adalah sampah yang tidak perlu, tetapi informasi seperti itu kadang-kadang diperlukan oleh penganalisa untuk beberapa aturan diagnostik. Dengan kata lain, alat analisa tidak bekerja dengan pohon sintaksis abstrak (AST), tetapi dengan pohon parse (DT).

Pohon itu tumbuh dari kiri ke kanan dan dari atas ke bawah. Node anak kiri selalu berisi sesuatu yang bermakna, seperti deklarator. Jika Anda melihat ke kanan, kita akan melihat non-terminal menengah yang ditandai dengan kata NonLeaf. Mereka diperlukan hanya agar pohon mempertahankan strukturnya. Untuk kebutuhan analisis, simpul semacam itu tidak membawa muatan informasi apa pun.

Sementara kita akan tertarik pada bagian kiri pohon. Ini dia dalam closeup yang lebih besar:

Gambar 10

Fitur iklan ini. Simpul induk PtreeDeclarator adalah objek yang melaluinya Anda dapat mengakses node dengan nama fungsi dan parameternya. Itu juga menyimpan tanda tangan yang dikodekan untuk sistem tipe. Menurut saya gambar ini cukup visual, dan sangat mudah untuk membandingkan elemen pohon dengan kode.

Terlihat mudah, bukan?

Untuk kejelasan, mari kita ambil contoh sederhana. Bayangkan kita memiliki kode yang memanggil fungsi kita f :

f(42, 23);

Panggilan fungsi di pohon akan terlihat seperti ini:

Gambar 12

Strukturnya sangat mirip, hanya di sini kita melihat pemanggilan fungsi alih-alih deklarasi. Sekarang anggaplah kita ingin membahas semua argumen dan melakukan sesuatu dengan masing-masing argumen. Ini adalah tugas nyata yang sering ditemukan dalam kode analisa. Jelas bahwa semuanya tidak terbatas pada argumen, dan berbagai jenis node harus diurutkan, tetapi sekarang kita akan mempertimbangkan contoh khusus ini.

Misalkan kita hanya memiliki pointer ke simpul FUNCALL induk . Dari sembarang terminal, kita bisa mendapatkan simpul anak kiri dan kanan. Jenis masing-masing diketahui. Kita tahu struktur pohon, sehingga kita dapat segera mencapai simpul di mana daftar argumen berada - ini adalah NonLeaf , dari mana terminal tumbuh dalam gambar 42. Kami tidak tahu jumlah argumen sebelumnya, dan ada koma dalam daftar yang dalam hal ini sama sekali tidak menarik bagi kami.

Bagaimana kita akan melakukan ini? Baca terus.

Pabrik sepeda


Tampaknya iterasi melalui pohon cukup sederhana. Anda hanya perlu menulis fungsi yang akan melakukan ini, dan menggunakannya di mana-mana. Dimungkinkan untuk memberikannya lambda sebagai argumen untuk menangani setiap elemen. Benar-benar akan begitu, kalau bukan karena beberapa nuansa.

Pertama, berkeliling pohon setiap kali harus sedikit berbeda. Logika memproses setiap node berbeda, serta logika bekerja dengan seluruh daftar. Katakanlah, dalam satu kasus, kami ingin memeriksa argumen daftar dan meneruskan masing-masing ke fungsi tertentu untuk diproses. Di lain, kami ingin memilih dan mengembalikan satu argumen yang memenuhi beberapa persyaratan. Atau filter daftar dan buang elemen yang tidak menarik darinya.

Kedua, terkadang Anda perlu mengetahui indeks elemen saat ini. Misalnya, kami hanya ingin memproses dua argumen pertama dan berhenti.

Ketiga, mari kita menyimpang dari contoh fungsi. Katakanlah kita memiliki kode seperti ini:

int f(int a, int b)
{
  int c = a + b;
  c *= 2;
  if (c < 42) return c;
  return 42;
}

Kode ini bodoh, saya tahu, tetapi mari kita berkonsentrasi sekarang tentang bagaimana pohon itu terlihat. Kita telah melihat deklarasi fungsi, di sini kita membutuhkan tubuhnya:

Gambar 4

Kasus ini seperti daftar argumen, tetapi Anda mungkin melihat beberapa perbedaan. Lihatlah gambar dari bagian sebelumnya.

Pernahkah Anda memperhatikan?

Itu benar, tidak ada koma dalam daftar ini, yang berarti bahwa Anda dapat memprosesnya berturut-turut dan tidak khawatir melompati pemisah.

Secara total, kami memiliki setidaknya dua kasus:

  • Daftar terpisah.
  • Daftar lengkap.

Sekarang mari kita lihat bagaimana ini semua terjadi dalam kode analisa. Berikut adalah contoh melintasi daftar argumen. Ini adalah versi sederhana dari salah satu fungsi di penerjemah.

void ProcessArguments(Ptree* arglist)
{
  if (!arglist) return;

  Ptree* args = Second(arglist);
  while (args)
  {
    Ptree* p = args->Car();
    if (!Eq(p, ','))
    {
      ProcessArg(p);
    }

    args = args->Cdr();
  }
}

Jika saya dibayar satu dolar setiap kali saya melihat kode yang sama, saya sudah akan menjadi kaya.

Mari kita lihat apa yang terjadi di sini. Saya harus segera mengatakan bahwa ini adalah kode yang sangat lama yang ditulis jauh sebelum C ++ 11, belum lagi standar yang lebih modern. Kita dapat mengatakan bahwa saya secara khusus mencari bagian dari zaman peradaban kuno.

Jadi, pertama, fungsi ini menerima daftar argumen dalam tanda kurung sebagai input. Sesuatu seperti ini:

(42, 23)

Fungsi kedua disebut di sini untuk mendapatkan isi tanda kurung. Yang dia lakukan adalah bergerak sekali ke kanan dan kemudian sekali ke kiri melalui pohon biner. Selanjutnya, loop secara berurutan mendapatkan elemen: 42, lalu koma, kemudian 23, dan pada langkah berikutnya, pointer argsmenjadi nol karena kita sampai ke ujung cabang. Lingkaran, tentu saja, melompati koma yang tidak menarik.

Fungsi serupa dengan logika yang sedikit berubah dapat ditemukan di banyak tempat, terutama dalam kode lama.

Contoh lain. Bagaimana saya tahu jika ada panggilan ke fungsi tertentu di blok kode tertentu? Seperti itu:

bool IsFunctionCalled(const Ptree* body, std::string_view name)
{
  if (!arglist) return;

  const Ptree* statements = body;
  while (statements)
  {
    const Ptree* cur = statements->Car();
    if (IsA(cur, ntExprStatement) && IsA(cur->Car(), ntFuncallExpr))
    {
      const Ptree* funcName = First(cur->Car());
      if (Eq(funcName, name))
        return true;
    }

    statements = statements->Cdr();
  }
  return false;
}

Catatan. Seorang pembaca yang penuh perhatian mungkin memperhatikan. Berapa umurnya? Ada std :: string_view mencuat . Semuanya sederhana, bahkan kode terlama secara bertahap dire-refored dan sedikit demi sedikit tidak ada yang tersisa.

Akan menyenangkan untuk menggunakan sesuatu yang lebih elegan di sini, bukan? Sebagai contoh, algoritma find_if standar . Apa algoritma di sana, bahkan rentang berbasis normal akan sangat meningkatkan keterbacaan dan memfasilitasi dukungan kode tersebut.

Mari kita coba untuk mencapai ini.

Masukkan pohon ke dalam kotak


Tujuan kami adalah membuat pohon berperilaku seperti wadah STL. Selain itu, kita tidak perlu peduli dengan struktur internal daftar, kita ingin mengulangi node secara seragam, misalnya, seperti ini:

void DoSomethingWithTree(const Ptree* tree)
{
  ....
  for (auto cur : someTreeContainer)
  {
    ....
  }
}

Seperti yang Anda lihat, di sini kami memiliki entitas tertentu yang disebut someTreeContainer , yang belum kami ketahui. Wadah seperti itu setidaknya harus memiliki metode awal dan akhir yang mengembalikan iterator. Berbicara tentang iterator, mereka juga harus berperilaku seperti yang standar. Mari kita mulai dengan mereka.

Dalam kasus paling sederhana, iterator terlihat seperti ini:

template <typename Node_t,
          std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>>
class PtreeIterator
{
public:
  using value_type = Node_t;
  using dereference_type = value_type;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer   = std::add_pointer_t<value_type>;
  using difference_type =
    decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;

public:
  PtreeIterator(Node_t* node) noexcept : m_node{ node } {}
  ....

  PtreeIterator& operator++() noexcept
  {
    m_node = Rest(m_node);
    return *this;
  }
  dereference_type operator*() const noexcept
  {
    return static_cast<dereference_type>(First(m_node));
  }

private:
  Node_t* m_node = nullptr;
};

Agar tidak mengacaukan kode, saya menghapus beberapa detail. Poin kunci di sini adalah dereferencing dan kenaikan. Templat diperlukan agar iterator dapat bekerja dengan data konstan dan tidak konstan.

Sekarang kita akan menulis wadah di mana kita akan menempatkan simpul pohon. Berikut ini pilihan paling sederhana:

template <typename Node_t>
class PtreeContainer
{
public:
  using Iterator = PtreeIterator<Node_t>;
  using value_type = typename Iterator::dereference_type;
  using size_type  = size_t;
  using difference_type =
        typename Iterator::difference_type;

public:
  PtreeContainer(Node_t* nodes) :
    m_nodes{ nodes }
  {
    if (IsLeaf(m_nodes))
    {
      m_nodes = nullptr;
    }
  }

  ....

  Iterator begin() const noexcept
  { 
    return m_nodes;
  }
  Iterator end() const noexcept
  { 
    return nullptr; 
  }
  bool empty() const noexcept
  {
    return begin() == end();
  }

private:
  Node_t* m_nodes = nullptr;
};

Kami sudah selesai, kami bisa bubar, terima kasih atas perhatian Anda.

Tidak, tunggu sebentar. Tidak sesederhana itu, bukan? Mari kita kembali ke dua opsi daftar kami - dengan dan tanpa pembatas. Di sini, ketika menambahkan, kita cukup mengambil simpul pohon yang tepat, jadi ini tidak menyelesaikan masalah. Kita masih perlu melewati koma jika kita ingin bekerja hanya dengan data.

Tidak masalah, kami hanya menambahkan parameter template tambahan ke iterator. Katakanlah seperti ini:

enum class PtreeIteratorTag : uint8_t
{
  Statement,
  List
};

template <typename Node_t, PtreeIteratorTag tag,
  std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0>
class PtreeIterator { .... };

Bagaimana ini akan membantu kami? Dasar. Kami akan memeriksa parameter ini secara bertahap dan berperilaku sesuai. Untungnya, di C ++ 17 kita bisa menyelesaikan ini pada tahap kompilasi menggunakan if constexpr :

PtreeIterator& operator++() noexcept
{
  if constexpr (tag == PtreeIteratorTag::Statement)
  {
    m_node = Rest(m_node);
  }
  else
  {
    m_node = RestRest(m_node);
  }
  return *this;
}

Itu lebih baik, sekarang kita dapat memilih iterator yang sesuai dengan kebutuhan kita. Apa yang harus dilakukan dengan wadah? Anda dapat, misalnya, seperti ini:

template <typename Node_t, PtreeIteratorTag tag>
class PtreeContainer
{
public:
  using Iterator = PtreeIterator<Node_t, tag>;
  ....
};

Sekarang, apakah kita sudah selesai? Sebenarnya tidak juga.

Tapi itu belum semuanya


Mari kita lihat kode ini:

void ProcessEnum(Ptree* argList, Ptree* enumPtree)
{
  const ptrdiff_t argListLen = Length(argList);
  if (argListLen < 0) return;

  for (ptrdiff_t i = 0; i < argListLen; ++i)
  {
    std::string name;
    Ptree* elem;

    const EGetEnumElement r = GetEnumElementInfo(enumPtree, i, elem, name);
    ....
  }
}

Saya benar-benar tidak suka banyak dalam kode ini, mulai dari loop dengan penghitung, dan diakhiri dengan fakta bahwa fungsi GetEnumElementInfo terlihat sangat mencurigakan. Sekarang tetap menjadi kotak hitam untuk kita, tetapi kita dapat mengasumsikan bahwa ia mengeluarkan elemen enum dengan indeks dan mengembalikan nama dan simpulnya di pohon melalui parameter output. Nilai kembaliannya juga agak aneh. Mari kita singkirkan semuanya - pekerjaan ideal untuk daftar iterator kami:

void ProcessEnum(const Ptree* argList)
{
  for (auto elem : PtreeContainer<const Ptree, PtreeIteratorTag::List>(argList))
  {
    auto name = PtreeToString(elem);
    ....
  }
}

Tidak buruk. Hanya kode ini yang tidak dikompilasi. Mengapa? Karena indeks yang kami hapus digunakan di badan loop di bawah panggilan ke GetEnumElementInfo . Saya tidak akan mengatakan di sini persis bagaimana itu digunakan, karena itu tidak penting sekarang. Cukuplah untuk mengatakan bahwa indeks diperlukan.

Baiklah, mari kita tambahkan variabel dan mengacaukan kode kita yang indah:

void ProcessEnum(const Ptree* argList)
{
  size_t i = 0;
  for (auto elem : PtreeContainer<const Ptree, PtreeIteratorTag::List>(argList))
  {
    auto name = PtreeToString(elem);
    ....
    UseIndexSomehow(i++);
  }
}

Masih merupakan opsi yang berfungsi, tetapi saya pribadi bereaksi terhadap sesuatu seperti ini:

Gambar 7

Baiklah, mari kita coba selesaikan masalah ini. Kami membutuhkan sesuatu yang dapat menghitung elemen secara otomatis. Tambahkan iterator dengan penghitung. Saya kembali melewatkan detail ekstra untuk singkatnya:

template <typename Node_t, PtreeIteratorTag tag,
  std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>>
class PtreeCountingIterator
{
public:
  using size_type = size_t;
  using value_type = Node_t;
  using dereference_type = std::pair<value_type, size_type>;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer = std::add_pointer_t<value_type>;
  using difference_type =
        decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;

public:
  PtreeCountingIterator(Node_t* node) noexcept : m_node{ node } {}
  ....

  PtreeCountingIterator& operator++() noexcept
  {
    if constexpr (tag == PtreeIteratorTag::Statement)
    {
      m_node = Rest(m_node);
    }
    else
    {
      m_node = RestRest(m_node);
    }

    ++m_counter;
    return *this;
  }

  dereference_type operator*() const noexcept
  {
    return { static_cast<value_type>(First(m_node)), counter() };
  }

private:
  Node_t* m_node = nullptr;
  size_type m_counter = 0;
};

Sekarang kita bisa menulis kode seperti itu, kan?

void ProcessEnum(const Ptree* argList)
{
  for (auto [elem, i] :
            PtreeCountedContainer<const Ptree, PtreeIteratorTag::List>(argList))
  {
    auto name = PtreeToString(elem);
    ....
    UseIndexSomehow(i);
  }
}

Secara umum, kami benar-benar bisa, tetapi ada satu masalah. Jika Anda melihat kode ini, Anda mungkin memperhatikan bahwa kami memperkenalkan entitas lain - sesuatu bernama PtreeCountedContainer . Tampaknya situasinya semakin rumit. Saya benar-benar tidak ingin menyulap dengan berbagai jenis wadah, dan mengingat bahwa mereka berada di dalam yang sama, tangan itu sendiri meraih pisau cukur Occam.

Kita harus menggunakan iterator sebagai parameter templat untuk wadah, tetapi lebih lanjut tentang itu nanti.

Jenis kebun binatang


Mengalihkan perhatian dari penghitung dan varietas iterator selama satu menit. Dalam mengejar bypass node universal, kami lupa tentang hal yang paling penting - pohon itu sendiri.

Lihatlah kode ini:

int a, b, c = 0, d;

Apa yang kita lihat di pohon:

Gambar 13

Sekarang mari kita beralih ke daftar deklarator, tapi pertama-tama saya akan memberi tahu Anda sesuatu tentang pohon itu. Sebelumnya, kami berurusan dengan pointer ke kelas Ptree . Ini adalah kelas dasar dari mana semua jenis node lainnya diwarisi. Melalui antarmuka mereka, kita dapat memperoleh informasi tambahan. Secara khusus, simpul paling atas dalam gambar dapat kembali kepada kita daftar deklarator tanpa menggunakan fungsi utilitas seperti Pertama dan Kedua . Juga, kita tidak perlu metode tingkat rendah Mobil dan Cdr (halo kepada penggemar bahasa Lisp). Ini sangat bagus, karena dalam diagnosa kita dapat mengabaikan implementasi pohon. Saya pikir semua orang setuju bahwa abstraksi saat ini sangat buruk.

Beginilah tampilan pintasan semua deklarator:

void ProcessDecl(const PtreeDeclarator* decl) { .... }

void ProcessDeclarators(const PtreeDeclaration* declaration)
{
  for (auto decl : declaration->GetDeclarators())
  {
    ProcessDecl(static_cast<const PtreeDeclarator*>(decl));
  }
}

Metode GetDeclarators mengembalikan wadah yang dapat diubah . Jenisnya dalam hal ini adalah PtreeContainer <const Ptree, PtreeIteratorTag :: List> .

Dengan kode ini, semuanya akan baik-baik saja jika bukan untuk para pemeran. Faktanya adalah bahwa fungsi ProcessDecl ingin pointer ke kelas yang berasal dari Ptree , tetapi iterator kami tidak tahu apa-apa tentang itu. Saya ingin menghilangkan kebutuhan untuk mengkonversi tipe secara manual.

Tampaknya sudah waktunya untuk mengubah iterator lagi dan menambahkan kemampuan untuk melakukan cast.

template <typename Node_t, typename Deref_t, PtreeIteratorTag tag,
  std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>>
class PtreeIterator
{
public:
  using value_type = Deref_t;
  using dereference_type = value_type;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer = std::add_pointer_t<value_type>;
  using difference_type =
        decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;
  ....
}

Agar tidak menulis semua argumen templat ini secara manual setiap kali, kami menambahkan beberapa alias untuk semua kesempatan:

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementIterator =
PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeListIterator =
PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::List>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementCountingIterator =
PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeListCountingIterator =
PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::List>;

Itu lebih baik. Sekarang, jika kita tidak perlu kasta, kita hanya bisa menentukan argumen templat pertama, dan kita juga tidak bisa menyumbat kepala kita dengan nilai parameter tag .

Tapi apa yang harus dilakukan dengan wadah? Biarkan saya mengingatkan Anda bahwa kami hanya ingin memiliki satu kelas universal yang cocok untuk setiap iterator. Sekarang banyak kombinasi yang tidak senonoh, dan kami membutuhkan kesederhanaan. Sesuatu seperti ini:

Gambar 39

Artinya, kami ingin satu kelas wadah untuk dapat mendukung semua jenis iterator kami dan dapat memberi tahu mereka jenis mana yang harus dikembalikan ketika dereferencing. Kemudian, dalam kode, kita cukup membuat wadah yang kita butuhkan dan mulai bekerja dengannya tanpa memikirkan iterator yang kita butuhkan.

Kami akan memeriksa pertanyaan ini di bagian selanjutnya.

Magic pola


Jadi inilah yang kami butuhkan:

  • Satu wadah yang dapat bekerja secara universal dengan iterator apa pun.
  • Sebuah iterator, yang, tergantung pada daftar node, dapat bekerja baik dengan masing-masing elemen, dan melalui satu.
  • Iterator yang sama, tetapi dengan penghitung.
  • Kedua iterator harus dapat melakukan cast saat dereferencing, jika jenisnya juga ditentukan.

Pertama-tama, kita perlu mengikat jenis wadah ke jenis iterator melalui parameter templat. Inilah yang terjadi:

template <template <typename, typename> typename FwdIt,
          typename Node_t,
          typename Deref_t = std::add_pointer_t<Node_t>>
class PtreeContainer
{
public:
  using Iterator = FwdIt<Node_t, Deref_t>;
  using value_type = typename Iterator::dereference_type;
  using size_type  = size_t;
  using difference_type = typename Iterator::difference_type;

public:
  PtreeContainer(Node_t* nodes) :
    m_nodes{ nodes }
  {
    if (IsLeaf(m_nodes))
    {
      m_nodes = nullptr;
    }
  }

  ....
  Iterator begin() const noexcept
  { 
    return m_nodes;
  }
  Iterator end() const noexcept
  { 
    return nullptr; 
  }
  bool empty() const noexcept
  {
    return begin() == end();
  }
  ....

private:
  Node_t* m_nodes = nullptr;
};

Anda juga dapat menambahkan lebih banyak metode ke wadah. Sebagai contoh, ini adalah bagaimana kita dapat mengetahui jumlah elemen:

difference_type count() const noexcept
{
  return std::distance(begin(), end());
}

Atau di sini adalah operator pengindeksan:

value_type operator[](size_type index) const noexcept
{
  size_type i = 0;
  for (auto it = begin(); it != end(); ++it)
  {
    if (i++ == index)
    {
      return *it;
    }
  }

  return value_type{};
}

Jelas bahwa Anda perlu menangani metode tersebut dengan hati-hati karena kompleksitas liniernya, tetapi kadang-kadang itu berguna.

Untuk kemudahan penggunaan, tambahkan alias:

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementList =
PtreeContainer<PtreeStatementIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeItemList =
PtreeContainer<PtreeListIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeCountedStatementList =
PtreeContainer<PtreeStatementCountingIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeCountedItemList =
PtreeContainer<PtreeListCountingIterator, Node_t, Deref_t>;

Sekarang kita dapat membuat wadah dengan mudah. Katakanlah, di kelas PtreeDeclaration yang sudah disebutkan , kami ingin mendapatkan sebuah wadah dari metode GetDeclarators , iterator yang melompati separator, sementara tidak ada penghitung di dalamnya, dan ketika dereferenced, ia mengembalikan nilai dari tipe PtreeDeclarator . Berikut adalah deklarasi dari wadah tersebut:

using DeclList =
      Iterators::PtreeItemList<Ptree, PtreeDeclarator*>;
using ConstDeclList =
      Iterators::PtreeItemList<const Ptree, const PtreeDeclarator*>;
             :
void ProcessDecl(const PtreeDeclarator* decl) { .... }

void ProcessDeclarators(const PtreeDeclaration* declaration)
{
  for (auto decl : declaration->GetDeclarators())
  {
    ProcessDecl(decl);
  }
}

Dan akhirnya, karena inferensi tipe untuk alias hanya akan muncul di C ++ 20, agar lebih mudah membuat wadah dalam kode, kami menambahkan fungsi-fungsi berikut:

template <typename Node_t>
PtreeStatementList<Node_t> MakeStatementList(Node_t* node)
{
  return { node };
}

template <typename Node_t>
PtreeItemList<Node_t> MakeItemList(Node_t* node)
{
  return { node };
}

template <typename Node_t>
PtreeCountedStatementList<Node_t> MakeCountedStatementList(Node_t* node)
{
  return { node };
}

template <typename Node_t>
PtreeCountedItemList<Node_t> MakeCountedItemList(Node_t* node)
{
  return { node };
}

Ingat fungsi yang bekerja dengan enum . Sekarang kita bisa menulis seperti ini:

void ProcessEnum(const Ptree* argList)
{
  for (auto [elem, i] : MakeCountedItemList(argList))
  {
    auto name = PtreeToString(elem);
    ....
    UseIndexSomehow(i);
  }
}

Bandingkan dengan versi aslinya, menurut saya, sudah menjadi lebih baik:

void ProcessEnum(Ptree* argList, Ptree* enumPtree)
{
  const ptrdiff_t argListLen = Length(argList);
  if (argListLen < 0) return;

  for (ptrdiff_t i = 0; i < argListLen; ++i)
  {
    std::string name;
    Ptree* elem;

    const EGetEnumElement r = GetEnumElementInfo(enumPtree, i, elem, name);
    ....
    UseIndexSomehow(i);
  }
}

Itu saja, semuanya


Itu semua untuk saya, terima kasih atas perhatian Anda. Saya harap Anda menemukan sesuatu yang menarik atau bahkan berguna.

Menurut isi artikel tersebut, mungkin saya memarahi kode penganalisa kami dan ingin mengatakan bahwa semuanya buruk di sana. Ini tidak benar. Seperti proyek apa pun yang memiliki sejarah, penganalisa kami penuh dengan endapan geologis yang tersisa dari masa lalu. Anggap saja kita baru saja menggali, memindahkan artefak dari peradaban kuno dari bawah tanah dan melakukan restorasi untuk membuatnya terlihat bagus di rak.

P.S


Akan ada banyak kode di sini. Saya ragu apakah akan memasukkan implementasi iterator di sini atau tidak, dan pada akhirnya saya memutuskan untuk memasukkan agar tidak meninggalkan apa pun di belakang layar. Jika Anda tidak tertarik membaca kode, di sini saya akan mengucapkan selamat tinggal kepada Anda. Selebihnya saya ingin Anda bersenang-senang dengan template.

Kode

Iterator reguler


template <typename Node_t, typename Deref_t, PtreeIteratorTag tag,
std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0>
class PtreeIterator
{
public:
  using value_type = Deref_t;
  using dereference_type = value_type;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer = std::add_pointer_t<value_type>;
  using difference_type =
        decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;

public:
  PtreeIterator(Node_t* node) noexcept : m_node{ node } {}
  PtreeIterator() = delete;
  PtreeIterator(const PtreeIterator&) = default;
  PtreeIterator& operator=(const PtreeIterator&) = default;
  PtreeIterator(PtreeIterator&&) = default;
  PtreeIterator& operator=(PtreeIterator&&) = default;

  bool operator==(const PtreeIterator & other) const noexcept
  {
    return m_node == other.m_node;
  }
  bool operator!=(const PtreeIterator & other) const noexcept
  {
    return !(*this == other);
  }
  PtreeIterator& operator++() noexcept
  {
    if constexpr (tag == PtreeIteratorTag::Statement)
    {
      m_node = Rest(m_node);
    }
    else
    {
      m_node = RestRest(m_node);
    }
    return *this;
  }
  PtreeIterator operator++(int) noexcept
  {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  dereference_type operator*() const noexcept
  {
    return static_cast<dereference_type>(First(m_node));
  }
  pointer operator->() const noexcept
  {
    return &(**this);
  }

  Node_t* get() const noexcept
  {
    return m_node;
  }

private:
  Node_t* m_node = nullptr;
};

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementIterator =
PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeListIterator =
PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::List>;

Iterator dengan penghitung


template <typename Node_t, typename Deref_t, PtreeIteratorTag tag,
std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0>
class PtreeCountingIterator
{
public:
  using size_type = size_t;
  using value_type = Deref_t;
  using dereference_type = std::pair<value_type, size_type>;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer = std::add_pointer_t<value_type>;
  using difference_type =
        decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;

 public:
  PtreeCountingIterator(Node_t* node) noexcept : m_node{ node } {}
  PtreeCountingIterator() = delete;
  PtreeCountingIterator(const PtreeCountingIterator&) = default;
  PtreeCountingIterator& operator=(const PtreeCountingIterator&) = default;
  PtreeCountingIterator(PtreeCountingIterator&&) = default;
  PtreeCountingIterator& operator=(PtreeCountingIterator&&) = default;

  bool operator==(const PtreeCountingIterator& other) const noexcept
  {
    return m_node == other.m_node;
  }
  bool operator!=(const PtreeCountingIterator& other) const noexcept
  {
    return !(*this == other);
  }
  PtreeCountingIterator& operator++() noexcept
  {
    if constexpr (tag == PtreeIteratorTag::Statement)
    {
      m_node = Rest(m_node);
    }
    else
    {
      m_node = RestRest(m_node);
    }

    ++m_counter;
    return *this;
  }
  PtreeCountingIterator operator++(int) noexcept
  {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  dereference_type operator*() const noexcept
  {
    return { static_cast<value_type>(First(m_node)), counter() };
  }
  value_type operator->() const noexcept
  {
    return (**this).first;
  }

  size_type counter() const noexcept
  {
    return m_counter;
  }
  Node_t* get() const noexcept
  {
    return m_node;
  }

private:
  Node_t* m_node = nullptr;
  size_type m_counter = 0;
};

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementCountingIterator =
PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeListCountingIterator =
PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::List>;

Wadah generik


template <template <typename, typename> typename FwdIt,
          typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
class PtreeContainer
{
public:
  using Iterator = FwdIt<Node_t, Deref_t>;
  using value_type = typename Iterator::dereference_type;
  using size_type  = size_t;
  using difference_type = typename Iterator::difference_type;

public:
  PtreeContainer(Node_t* nodes) :
    m_nodes{ nodes }
  {
    if (IsLeaf(m_nodes))
    {
      m_nodes = nullptr;
    }
  }

  PtreeContainer() = default;
  PtreeContainer(const PtreeContainer&) = default;
  PtreeContainer& operator=(const PtreeContainer&) = default;
  PtreeContainer(PtreeContainer&&) = default;
  PtreeContainer& operator=(PtreeContainer&&) = default;

  bool operator==(std::nullptr_t) const noexcept
  {
    return empty();
  }
  bool operator!=(std::nullptr_t) const noexcept
  {
    return !(*this == nullptr);
  }
  bool operator==(Node_t* node) const noexcept
  {
    return get() == node;
  }
  bool operator!=(Node_t* node) const noexcept
  {
    return !(*this == node);
  }
  bool operator==(PtreeContainer other) const noexcept
  {
    return get() == other.get();
  }
  bool operator!=(PtreeContainer other) const noexcept
  {
    return !(*this == other);
  }
  value_type operator[](size_type index) const noexcept
  {
    size_type i = 0;
    for (auto it = begin(); it != end(); ++it)
    {
      if (i++ == index)
      {
        return *it;
      }
    }

    return value_type{};
  }

  Iterator begin() const noexcept
  { 
    return m_nodes;
  }
  Iterator end() const noexcept
  { 
    return nullptr; 
  }
  bool empty() const noexcept
  {
    return begin() == end();
  }

  value_type front() const noexcept
  {
    return (*this)[0];
  }
  value_type back() const noexcept
  {
    value_type last{};
    for (auto cur : *this)
    {
      last = cur;
    }

    return last;
  }
  Node_t* get() const noexcept
  {
    return m_nodes;
  }

  difference_type count() const noexcept
  {
    return std::distance(begin(), end());
  }
  bool has_at_least(size_type n) const noexcept
  {
    size_type counter = 0;
    for (auto it = begin(); it != end(); ++it)
    {
      if (++counter == n)
      {
        return true;
      }
    }
    return false;
  }

private:
  Node_t* m_nodes = nullptr;
};

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementList =
PtreeContainer<PtreeStatementIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeItemList =
PtreeContainer<PtreeListIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeCountedStatementList =
PtreeContainer<PtreeStatementCountingIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeCountedItemList =
PtreeContainer<PtreeListCountingIterator, Node_t, Deref_t>;



Jika Anda ingin berbagi artikel ini dengan audiens yang berbahasa Inggris, silakan gunakan tautan ke terjemahan: Yuri Minaev. Cara memanjat pohon .

More articles:


All Articles