🏂🏽 📼 😒 Wie man auf einen Baum klettert 🛃 👏🏿 👨🏻

Genauer gesagt, wie man davon runterkommt. Aber das Wichtigste zuerst. Dieser Artikel ist etwas außerhalb des üblichen Artikelformats von PVS-Studio. Wir schreiben oft über die Überprüfung anderer Projekte, öffnen aber fast nie die Tür zu unserer inneren Küche. Es ist Zeit, das Problem zu beheben und darüber zu sprechen, wie der Analysator von innen aufgebaut ist. Genauer gesagt über den wichtigsten seiner Teile - den Syntaxbaum. Der Artikel konzentriert sich auf den Teil von PVS-Studio, der sich auf die Sprachen C und C ++ bezieht.

Das wichtigste zuerst

Der Syntaxbaum ist der zentrale Teil eines jeden Compilers. Auf die eine oder andere Weise muss der Code in einer für die Programmverarbeitung geeigneten Form dargestellt werden, und es kommt einfach so vor, dass die Baumstruktur dafür am besten geeignet ist. Ich werde hier nicht auf die Theorie eingehen - es genügt zu sagen, dass der Baum die Hierarchie der Ausdrücke und Blöcke im Code sehr gut widerspiegelt und gleichzeitig nur die für die Arbeit erforderlichen Daten enthält.

Was hat der Compiler mit dem statischen Analysator zu tun? Tatsache ist, dass diese beiden Tools viel gemeinsam haben. In der Anfangsphase des Parsens des Codes erledigen sie den gleichen Job. Zunächst wird der Code in einen Token-Stream unterteilt, der dem Parser zugeführt wird. Während der syntaktischen und semantischen Analyse werden Token dann in einem Baum organisiert, der weiter entlang der Pipeline gesendet wird. In dieser Phase können Compiler Zwischenoptimierungen durchführen, bevor sie Binärcode generieren. Statische Analysatoren beginnen, Knoten zu umgehen und verschiedene Überprüfungen zu starten.

Im PVS-Studio-Analysegerät mit einem erstellten Baum passieren verschiedene Dinge:

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

Wenn Sie sich für Details zur Funktionsweise der Analyse interessieren, empfehlen wir Ihnen, den Artikel „ Im PVS-Studio Code Analyzer verwendete Technologien zum Auffinden von Fehlern und potenziellen Sicherheitslücken “ zu lesen . Einige Punkte aus der Liste werden dort ausführlich untersucht.

Wir werden genauer untersuchen, was mit dem Baum im Analysator passiert und wie er überhaupt aussieht. Nach einer kurzen Einführung ist es an der Zeit, der Sache auf den Grund zu gehen.

Wie es funktioniert

In der Vergangenheit verwendet PVS-Studio einen Binärbaum zur Darstellung von Code. Diese klassische Datenstruktur ist jedem bekannt - wir haben einen Knoten, der sich im Allgemeinen auf zwei Kinder bezieht. Knoten, die keine Nachkommen haben sollen, werde ich Terminals nennen, alle anderen - Nicht-Terminals. Ein Nichtterminal kann in einigen Fällen keine untergeordneten Knoten haben, aber sein Hauptunterschied zum Terminal besteht darin, dass Nachkommen grundsätzlich dafür zugelassen sind. Endknoten (oder Blätter) können nicht auf etwas anderes als das übergeordnete Knoten verweisen.

Die in PVS-Studio verwendete Struktur unterscheidet sich geringfügig vom klassischen Binärbaum - dies ist aus praktischen Gründen erforderlich. Endknoten entsprechen normalerweise Schlüsselwörtern, Variablennamen, Literalen usw. Nichtterminale - verschiedene Arten von Ausdrücken, Codeblöcken, Listen und dergleichen, die Bestandteile des Baums.

Aus Sicht der Compiler ist hier alles ziemlich normal, ich rate jedem, der sich für die Klassiker des Genres interessiert - The Dragon Book .

Wir gehen weiter. Schauen wir uns ein einfaches Codebeispiel an und wie der Analysator es sieht. Außerdem werden viele Bilder von unserem internen Dienstprogramm zur Baumvisualisierung angezeigt.

Eigentlich ein Beispiel:

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

Diese einfache Funktion sieht nach der Verarbeitung durch den Parser folgendermaßen aus (nicht terminale Knoten werden gelb hervorgehoben):

Diese Ansicht hat ihre Vor- und Nachteile, und letztere meiner Meinung nach etwas mehr. Aber schauen wir uns den Baum an. Machen Sie sofort einen Vorbehalt, dass es etwas überflüssig ist, zum Beispiel weil es Interpunktion und Klammern enthält. Unter dem Gesichtspunkt der Kompilierung ist dies überflüssiger Müll, aber solche Informationen werden manchmal vom Analysator für einige Diagnoseregeln benötigt. Mit anderen Worten, der Analysator arbeitet nicht mit dem abstrakten Syntaxbaum (AST), sondern mit dem Analysebaum (DT).

Der Baum wächst von links nach rechts und von oben nach unten. Linke untergeordnete Knoten enthalten immer etwas Sinnvolles, z. B. Deklaratoren. Wenn Sie nach rechts schauen, sehen Sie Zwischen-Nicht-Terminals, die mit dem Wort NonLeaf gekennzeichnet sind. Sie werden nur benötigt, damit der Baum seine Struktur behält. Für die Anforderungen der Analyse tragen solche Knoten keine Informationslast.

Während wir uns für den linken Teil des Baumes interessieren werden. Hier ist es in einer größeren Nahaufnahme:

Diese Anzeige bietet. Der übergeordnete PtreeDeclarator- Knoten ist ein Objekt, über das Sie auf Knoten mit dem Namen der Funktion und ihren Parametern zugreifen können. Es speichert auch die codierte Signatur für das Typsystem. Es scheint mir, dass dieses Bild ziemlich visuell ist und es ziemlich einfach ist, die Elemente des Baums mit dem Code zu vergleichen.

Sieht einfach aus, oder?

Nehmen wir zur Verdeutlichung ein einfacheres Beispiel. Stellen Sie sich vor, wir haben Code, der unsere Funktion f aufruft :

f(42, 23);

Ein Funktionsaufruf im Baum sieht folgendermaßen aus:

Die Struktur ist sehr ähnlich, nur hier sehen wir einen Funktionsaufruf anstelle seiner Deklaration. Nehmen wir nun an, wir wollten alle Argumente durchgehen und mit jedem etwas anfangen. Dies ist eine echte Aufgabe, die häufig im Analysatorcode enthalten ist. Es ist klar, dass nicht alles auf Argumente beschränkt ist und verschiedene Knotentypen sortiert werden müssen, aber jetzt werden wir dieses spezielle Beispiel betrachten.

Angenommen, wir haben nur einen Zeiger auf den übergeordneten FUNCALL- Knoten . Von jedem Nicht-Terminal können wir den linken und rechten untergeordneten Knoten erhalten. Der Typ von jedem von ihnen ist bekannt. Wir kennen die Struktur des Baums, so dass wir sofort den Knoten erreichen können, unter dem die Liste der Argumente liegt - dies ist NonLeaf , von dem aus das Terminal im Bild 42 wächst. Wir kennen die Anzahl der Argumente nicht im Voraus und es gibt Kommas in der Liste, die in diesem Fall für uns absolut nicht von Interesse sind.

Wie machen wir das? Weiter lesen.

Fahrradfabrik

Es scheint, dass das Durchlaufen eines Baumes recht einfach ist. Sie müssen nur eine Funktion schreiben, die dies erledigt, und sie überall verwenden. Es ist möglich, ein Lambda als Argument für jedes Element zu übergeben. Es wäre wirklich so, wenn nicht ein paar Nuancen.

Erstens muss es etwas anders sein, jedes Mal um einen Baum herumzugehen. Die Logik der Verarbeitung jedes Knotens ist unterschiedlich, ebenso wie die Logik der Arbeit mit der gesamten Liste. Angenommen, in einem Fall möchten wir die Listenargumente durchgehen und jedes von ihnen zur Verarbeitung an eine bestimmte Funktion übergeben. In einem anderen Fall möchten wir ein Argument auswählen und zurückgeben, das einige Anforderungen erfüllt. Oder filtern Sie die Liste und verwerfen Sie alle uninteressanten Elemente daraus.

Zweitens müssen Sie manchmal den Index des aktuellen Elements kennen. Zum Beispiel wollen wir nur die ersten beiden Argumente verarbeiten und aufhören.

Drittens schweifen wir vom Funktionsbeispiel ab. Angenommen, wir haben folgenden Code:

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

Ich weiß, dieser Code ist dumm, aber konzentrieren wir uns jetzt darauf, wie der Baum aussieht. Wir haben bereits eine Funktionsdeklaration gesehen, hier brauchen wir ihren Körper:

Dieser Fall ähnelt einer Liste von Argumenten, aber Sie können einen Unterschied feststellen. Schauen Sie sich das Bild aus dem vorherigen Abschnitt noch einmal an.

Hast du bemerkt?

Richtig, diese Liste enthält keine Kommas. Das bedeutet, dass Sie sie hintereinander verarbeiten können und sich keine Gedanken über das Überspringen von Trennzeichen machen müssen.

Insgesamt haben wir mindestens zwei Fälle:

Getrennte Liste.
Die vollständige Liste.

Lassen Sie uns nun sehen, wie dies alles im Analysatorcode geschieht. Hier ist ein Beispiel für das Durchlaufen einer Liste von Argumenten. Dies ist eine vereinfachte Version einer der Funktionen im Übersetzer.

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

Wenn ich jedes Mal einen Dollar bekommen würde, wenn ich einen ähnlichen Code sehe, würde ich bereits reich werden.

Mal sehen, was hier passiert. Ich muss sofort sagen, dass dies sehr alter Code ist, der lange vor C ++ 11 geschrieben wurde, ganz zu schweigen von moderneren Standards. Wir können sagen, dass ich speziell nach einem Fragment der Zeit der alten Zivilisationen gesucht habe.

Diese Funktion akzeptiert also zunächst eine Liste von Argumenten in Klammern als Eingabe. Etwa so:

(42, 23)

Die zweite Funktion wird hier aufgerufen, um den Inhalt der Klammern abzurufen. Sie bewegt sich nur einmal nach rechts und dann einmal nach links durch den Binärbaum. Als nächstes erhält die Schleife nacheinander die Elemente: 42, dann ein Komma, dann 23 und im nächsten Schritt den Args- Zeigerwird Null, weil wir am Ende des Zweigs angelangt sind. Die Schleife überspringt natürlich uninteressante Kommas.

Ähnliche Funktionen mit leicht veränderter Logik finden sich an vielen Stellen, insbesondere im alten Code.

Ein anderes Beispiel. Woher weiß ich, ob eine bestimmte Funktion in einem bestimmten Codeblock aufgerufen wird? Ungefähr so:

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

Hinweis. Ein aufmerksamer Leser kann es bemerken. Wie alt ist er? Dort ragt std :: string_view heraus. Alles ist einfach, selbst der älteste Code wird nach und nach überarbeitet und nach und nach bleibt nichts dergleichen übrig.

Es wäre schön, hier etwas eleganteres zu verwenden, oder? Nun, zum Beispiel der Standardalgorithmus find_if . Was ist der Algorithmus dort, selbst ein normaler bereichsbasierter Algorithmus würde die Lesbarkeit erheblich verbessern und die Unterstützung eines solchen Codes erleichtern.

Versuchen wir dies zu erreichen.

Legen Sie den Baum in die Box

Unser Ziel ist es, dass sich der Baum wie ein STL-Container verhält. Darüber hinaus sollten wir uns nicht um die interne Struktur der Listen kümmern, sondern einheitlich über die Knoten iterieren, zum Beispiel wie folgt:

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

Wie Sie sehen können, haben wir hier eine bestimmte Entität namens someTreeContainer , von der wir noch nichts wissen. Ein solcher Behälter sollte zumindest beginnen und Ende Methoden die Rückkehr Iteratoren. Apropos Iteratoren, sie sollten sich auch wie Standard-Iteratoren verhalten. Beginnen wir mit ihnen.

Im einfachsten Fall sieht der Iterator folgendermaßen aus:

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

Um den Code nicht zu überladen, habe ich einige Details entfernt. Die wichtigsten Punkte hier sind Dereferenzierung und Inkrementierung. Die Vorlage wird benötigt, damit der Iterator sowohl mit konstanten als auch mit nicht konstanten Daten arbeiten kann.

Jetzt schreiben wir den Container, in dem wir den Baumknoten platzieren. Hier ist die einfachste Option:

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

Wir sind fertig, wir können uns zerstreuen, danke für Ihre Aufmerksamkeit.

Nein, warte einen Moment. So einfach kann es doch nicht sein, oder? Kehren wir zu unseren beiden Listenoptionen zurück - mit und ohne Trennzeichen. Hier nehmen wir beim Inkrementieren einfach den rechten Knoten des Baums, damit das Problem nicht gelöst wird. Wir müssen immer noch Kommas überspringen, wenn wir nur mit Daten arbeiten möchten.

Kein Problem, wir fügen dem Iterator lediglich einen zusätzlichen Vorlagenparameter hinzu. Sagen wir so:

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

Wie wird uns das helfen? Grundstufe. Wir werden diesen Parameter schrittweise überprüfen und uns entsprechend verhalten. Glücklicherweise können wir dies in C ++ 17 in der Kompilierungsphase mit dem Konstrukt if constexpr lösen :

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

Das ist besser, jetzt können wir einen Iterator auswählen, der unseren Anforderungen entspricht. Was tun mit Containern? Sie können zum Beispiel so aussehen:

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

Sind wir jetzt definitiv fertig? In der Tat nicht wirklich.

Aber das ist nicht alles

Schauen wir uns diesen Code an:

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

Ich mag diesen Code wirklich nicht sehr, angefangen von der Schleife mit dem Zähler bis hin zur Tatsache, dass die GetEnumElementInfo- Funktion sehr verdächtig aussieht. Jetzt bleibt es eine Black Box für uns, aber wir können davon ausgehen, dass es das enum- Element nach Index herausnimmt und seinen Namen und Knoten im Baum über die Ausgabeparameter zurückgibt. Der Rückgabewert ist auch etwas seltsam. Lassen Sie es uns ganz loswerden - ein idealer Job für unseren Listeniterator:

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

Nicht schlecht. Nur dieser Code wird nicht kompiliert. Warum? Weil der Index, den wir entfernt haben, im Hauptteil der Schleife unterhalb des Aufrufs von GetEnumElementInfo verwendet wurde . Ich werde hier nicht genau sagen, wie es verwendet wurde, weil es jetzt nicht wichtig ist. Es genügt zu sagen, dass ein Index benötigt wird.

Nun, lassen Sie uns eine Variable hinzufügen und unseren schönen Code durcheinander bringen:

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

Immer noch eine funktionierende Option, aber ich persönlich reagiere auf so etwas:

Versuchen wir, dieses Problem zu lösen. Wir brauchen etwas, das Elemente automatisch zählen kann. Fügen Sie einen Iterator mit einem Zähler hinzu. Der Kürze halber habe ich die zusätzlichen Details noch einmal übersprungen:

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

Jetzt können wir solchen Code schreiben, oder?

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

Im Allgemeinen können wir das wirklich, aber es gibt ein Problem. Wenn Sie sich diesen Code ansehen, werden Sie möglicherweise feststellen, dass wir eine andere Entität eingeführt haben - PtreeCountedContainer . Es scheint, dass die Situation kompliziert wird. Ich möchte wirklich nicht mit verschiedenen Arten von Behältern jonglieren, und da sie innen gleich sind, greift die Hand selbst nach Occams Rasiermesser.

Wir müssen einen Iterator als Vorlagenparameter für den Container verwenden, aber dazu später mehr.

Zootypen

Lenken Sie für eine Minute von Zählern und verschiedenen Iteratoren ab. Bei der Verfolgung einer universellen Umgehung von Knoten haben wir das Wichtigste vergessen - den Baum selbst.

Schauen Sie sich diesen Code an:

int a, b, c = 0, d;

Was wir im Baum sehen:

Lassen Sie uns nun die Liste der Deklaratoren durchlaufen, aber zuerst werde ich Ihnen noch etwas über den Baum erzählen. Die ganze Zeit zuvor hatten wir es mit einem Zeiger auf die Ptree- Klasse zu tun . Dies ist die Basisklasse, von der alle anderen Knotentypen geerbt werden. Über ihre Schnittstellen können wir zusätzliche Informationen erhalten. Insbesondere kann der oberste Knoten im Bild die Liste der Deklaratoren an uns zurückgeben, ohne Dienstprogrammfunktionen wie First und Second zu verwenden . Außerdem brauchen wir keine Low-Level-Methoden wie Car und Cdr (Hallo an Fans der Lisp-Sprache). Dies ist sehr gut, da wir in der Diagnose die Implementierung des Baums ignorieren können. Ich denke, alle sind sich einig, dass aktuelle Abstraktionen sehr schlecht sind.

So sieht die Umgehung aller Deklaratoren aus:

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

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

Die GetDeclarators- Methode gibt einen iterierbaren Container zurück. Sein Typ ist in diesem Fall PtreeContainer <const Ptree, PtreeIteratorTag :: List> .

Mit diesem Code wäre alles in Ordnung, wenn nicht für die Besetzung. Tatsache ist, dass die ProcessDecl- Funktion einen Zeiger auf eine von Ptree abgeleitete Klasse haben möchte , aber unsere Iteratoren wissen nichts darüber. Ich möchte die Notwendigkeit der manuellen Konvertierung von Typen beseitigen.

Es scheint an der Zeit zu sein, den Iterator erneut zu ändern und die Fähigkeit zum Wirken hinzuzufügen.

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

Um nicht alle diese Vorlagenargumente jedes Mal manuell zu schreiben, fügen wir für alle Gelegenheiten einige Aliase hinzu:

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

So ist es besser. Wenn wir jetzt keine Castes benötigen, können wir nur das erste Template-Argument angeben und unsere Köpfe nicht mit dem Wert des Tag- Parameters verstopfen .

Aber was tun mit Containern? Ich möchte Sie daran erinnern, dass wir nur eine universelle Klasse haben möchten, die für jeden Iterator geeignet ist. Jetzt gibt es unanständig viele verschiedene Kombinationen, und wir brauchen Einfachheit. Etwas wie das:

Das heißt, wir möchten, dass eine einzelne Containerklasse alle Typen unserer Iteratoren unterstützt und ihnen mitteilt, welcher Typ bei der Dereferenzierung zurückgegeben werden soll. Dann erstellen wir im Code einfach den Container, den wir benötigen, und beginnen damit zu arbeiten, ohne darüber nachzudenken, welche Iteratoren wir benötigen.

Wir werden diese Frage im nächsten Abschnitt untersuchen.

Mustermagie

Also hier ist was wir brauchen:

Ein Container, der universell mit jedem Iterator arbeiten kann.
Ein Iterator, der abhängig von der Liste der Knoten sowohl mit jedem Element als auch über eines arbeiten kann.
Der gleiche Iterator, aber mit einem Zähler.
Beide Iteratoren sollten beim Dereferenzieren umwandeln können, wenn der Typ zusätzlich angegeben wird.

Zunächst müssen wir den Containertyp über Vorlagenparameter irgendwie an den Iteratortyp binden. Folgendes ist passiert:

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

Sie können dem Container auch weitere Methoden hinzufügen. So können wir beispielsweise die Anzahl der Elemente ermitteln:

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

Oder hier ist der Indexierungsoperator:

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

Es ist klar, dass Sie solche Methoden aufgrund ihrer linearen Komplexität sorgfältig behandeln müssen, aber manchmal sind sie nützlich.

Fügen Sie zur Vereinfachung der Verwendung Aliase hinzu:

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

Jetzt können wir einfach Container erstellen. Angenommen , in der bereits erwähnten PtreeDeclaration- Klasse möchten wir einen Container aus der GetDeclarators- Methode abrufen , deren Iterator Trennzeichen überspringt, obwohl kein Zähler darin enthalten ist. Wenn dereferenziert wird, wird ein Wert vom Typ PtreeDeclarator zurückgegeben . Hier ist die Erklärung eines solchen Containers:

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

Und schließlich haben wir folgende Funktionen hinzugefügt, da Typinferenz für Aliase nur in C ++ 20 angezeigt wird, um Container im Code bequemer zu erstellen:

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

Erinnern Sie sich an die Funktion, die mit enum funktioniert hat . Jetzt können wir es so schreiben:

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

Vergleichen Sie mit der Originalversion, es scheint mir, es ist besser geworden:

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

Das war's Leute

Das ist alles für mich, danke für Ihre Aufmerksamkeit. Ich hoffe, Sie haben etwas Interessantes oder Nützliches herausgefunden.

Nach dem Inhalt des Artikels scheint es, dass ich den Code unseres Analysators schimpfe und sagen möchte, dass dort alles schlecht ist. Das ist nicht so. Wie jedes Projekt mit einer Geschichte ist unser Analysegerät voller geologischer Ablagerungen, die aus vergangenen Epochen stammen. Bedenken Sie, dass wir gerade Artefakte aus der alten Zivilisation ausgegraben, unter der Erde entfernt und die Restaurierung durchgeführt haben, damit sie im Regal gut aussehen.

P.S.

Hier wird es viel Code geben. Ich bezweifelte, ob ich hier die Implementierung von Iteratoren einbeziehen sollte oder nicht, und am Ende entschied ich mich, diese einzubeziehen, um nichts hinter den Kulissen zu lassen. Wenn Sie nicht daran interessiert sind, den Code zu lesen, werde ich mich hier von Ihnen verabschieden. Den Rest wünsche ich Ihnen eine angenehme Zeit mit Vorlagen.

Der Code

Regelmäßiger Iterator

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 mit Zähler

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

Generischer Container

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

Wenn Sie diesen Artikel einem englischsprachigen Publikum zugänglich machen möchten, verwenden Sie bitte den Link zur Übersetzung: Yuri Minaev. Wie man auf einen Baum klettert .

Wie man auf einen Baum klettert