🖐️ ⛅️ 🧗🏿 Comment grimper à un arbre 🌕 👩‍💼 🖕🏻

Plus précisément, comment en descendre. Mais tout d'abord. Cet article sort un peu du format habituel de PVS-Studio. Nous écrivons souvent sur la vérification d'autres projets, mais n'ouvrons presque jamais la porte de notre cuisine intérieure. Il est temps de le réparer et de parler de la façon dont l'analyseur est construit de l'intérieur. Plus précisément, sur la plus importante de ses parties - l'arbre de syntaxe. L'article se concentrera sur la partie de PVS-Studio qui se rapporte aux langages C et C ++.

Tout d'abord

L'arbre de syntaxe est la partie centrale de tout compilateur. D'une manière ou d'une autre, le code doit être présenté sous une forme pratique pour le traitement du programme, et il se trouve que la structure arborescente est la mieux adaptée à cela. Je n'entrerai pas dans la théorie ici - il suffit de dire que l'arbre reflète très bien la hiérarchie des expressions et des blocs dans le code, et ne contient en même temps que les données nécessaires au travail.

Qu'est-ce que le compilateur a à voir avec l'analyseur statique? Le fait est que ces deux outils ont beaucoup en commun. Au stade initial de l'analyse du code, ils font le même travail. Tout d'abord, le code est divisé en un flux de jetons, qui est envoyé à l'analyseur. Ensuite, dans le processus d'analyse syntaxique et sémantique, les jetons sont organisés en un arbre, qui est envoyé plus loin le long du pipeline. À ce stade, les compilateurs peuvent effectuer des optimisations intermédiaires avant de générer du code binaire, les analyseurs statiques commencent à contourner les nœuds et à lancer divers contrôles.

Dans l'analyseur PVS-Studio avec une arborescence construite, plusieurs choses se produisent:

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

Si vous êtes intéressé par les détails du fonctionnement de l'analyse, je vous recommande de lire l'article « Technologies utilisées dans l'analyseur de code PVS-Studio pour trouver les erreurs et les vulnérabilités potentielles ». Certains points de la liste y sont examinés en détail.

Nous allons voir plus en détail ce qui arrive à l'arbre à l'intérieur de l'analyseur et à quoi il ressemble. Après une brève introduction, il est temps d'aller au fond des choses.

Comment ça fonctionne

Historiquement, PVS-Studio utilise un arbre binaire pour représenter le code. Cette structure de données classique est familière à tout le monde - nous avons un nœud qui fait généralement référence à deux enfants. Les nœuds qui ne sont pas censés avoir de descendants, j'appellerai des terminaux, tous les autres - des non-terminaux. Un terminal non terminal peut dans certains cas ne pas avoir de nœuds enfants, mais sa principale différence avec le terminal est que les descendants sont fondamentalement autorisés à le faire. Les nœuds terminaux (ou feuilles) n'ont pas la possibilité de se référer à autre chose que le parent.

La structure utilisée dans PVS-Studio est légèrement différente de l'arbre binaire classique - cela est nécessaire pour plus de commodité. Les nœuds terminaux correspondent généralement à des mots clés, des noms de variables, des littéraux, etc. Non terminaux - divers types d'expressions, blocs de code, listes et similaires, les éléments constitutifs de l'arbre.

Du point de vue des compilateurs, tout est assez standard ici, je conseille à tous ceux qui s'intéressent aux classiques du genre - The Dragon Book .

Nous allons de l'avant. Regardons un exemple de code simple et comment l'analyseur le voit. De plus, il y aura de nombreuses images de notre utilitaire de visualisation d'arborescence interne.

En fait, un exemple:

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

Cette fonction simple après traitement par l'analyseur ressemblera à ceci (les nœuds non terminaux sont surlignés en jaune):

Ce point de vue a ses avantages et ses inconvénients, et ce dernier, à mon avis, un peu plus. Mais regardons l'arbre. Faites immédiatement une réserve pour dire qu'elle est quelque peu redondante, par exemple, car elle contient des signes de ponctuation et des parenthèses. Du point de vue de la compilation, il s'agit de déchets superflus, mais de telles informations sont parfois nécessaires à l'analyseur pour certaines règles de diagnostic. En d'autres termes, l'analyseur ne fonctionne pas avec l'arbre de syntaxe abstraite (AST), mais avec l'arbre d'analyse (DT).

L'arbre pousse de gauche à droite et de haut en bas. Les nœuds enfants gauches contiennent toujours quelque chose de significatif, comme des déclarateurs. Si vous regardez à droite, nous verrons des non-terminaux intermédiaires marqués du mot NonLeaf. Ils ne sont nécessaires que pour que l'arbre conserve sa structure. Pour les besoins d'analyse, ces nœuds ne portent aucune charge d'informations.

Alors que nous serons intéressés par la partie gauche de l'arbre. Le voici en gros plan:

Cette annonce présente. Le nœud parent PtreeDeclarator est un objet à travers lequel vous pouvez accéder aux nœuds avec le nom de la fonction et ses paramètres. Il stocke également la signature codée pour le système de type. Il me semble que cette image est assez visuelle, et il est assez facile de comparer les éléments de l'arbre avec le code.

Ça a l'air facile, non?

Pour plus de clarté, prenons un exemple plus simple. Imaginez que nous ayons du code qui appelle notre fonction f :

f(42, 23);

Un appel de fonction dans l'arborescence ressemblera à ceci:

La structure est très similaire, seulement ici nous voyons un appel de fonction au lieu de sa déclaration. Supposons maintenant que nous voulions passer en revue tous les arguments et faire quelque chose avec chacun d'eux. Il s'agit d'une tâche réelle que l'on retrouve souvent dans le code de l'analyseur. Il est clair que tout n'est pas limité aux arguments, et différents types de nœuds doivent être triés, mais maintenant nous allons considérer cet exemple spécifique.

Supposons que nous ayons seulement un pointeur sur le nœud FUNCALL parent . De tout non-terminal, nous pouvons obtenir les nœuds enfants gauche et droit. Le type de chacun d'eux est connu. Nous connaissons la structure de l'arbre, de sorte que nous pouvons immédiatement atteindre le nœud sous lequel se trouve la liste des arguments - c'est NonLeaf , à partir duquel le terminal se développe dans l'image 42. Nous ne connaissons pas le nombre d'arguments à l'avance, et il y a des virgules dans la liste qui, dans ce cas, ne nous intéressent absolument pas.

Comment allons-nous procéder? Continuer à lire.

Usine de vélos

Il semblerait que l'itération à travers un arbre est assez simple. Il vous suffit d'écrire une fonction qui le fera et de l'utiliser partout. Il est possible de lui passer un lambda comme argument pour gérer chaque élément. Ce serait vraiment le cas, sinon pour quelques nuances.

Tout d'abord, faire le tour d'un arbre à chaque fois doit être un peu différent. La logique de traitement de chaque nœud est différente, ainsi que la logique de travail avec la liste entière. Disons, dans un cas, que nous voulons parcourir les arguments de la liste et passer chacun d'eux à une certaine fonction pour le traitement. Dans un autre, nous voulons sélectionner et renvoyer un argument qui répond à certaines exigences. Ou filtrez la liste et jetez-y tous les éléments inintéressants.

Deuxièmement, il faut parfois connaître l'index de l'élément courant. Par exemple, nous voulons traiter uniquement les deux premiers arguments et arrêter.

Troisièmement, s'écartons de l'exemple de fonction. Disons que nous avons un code comme celui-ci:

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

Ce code est stupide, je sais, mais concentrons-nous maintenant sur l'apparence de l'arbre. Nous avons déjà vu une déclaration de fonction, ici nous avons besoin de son corps:

Ce cas est comme une liste d'arguments, mais vous remarquerez peut-être une certaine différence. Jetez un autre coup d'œil à l'image de la section précédente.

As-tu remarqué?

C'est vrai, il n'y a pas de virgule dans cette liste, ce qui signifie que vous pouvez le traiter dans une rangée et ne pas vous soucier de sauter les séparateurs.

Au total, nous avons au moins deux cas:

Liste séparée.
La liste complète.

Voyons maintenant comment tout cela se passe dans le code de l'analyseur. Voici un exemple de traversée d'une liste d'arguments. Il s'agit d'une version simplifiée de l'une des fonctions du traducteur.

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

Si j'étais payé un dollar chaque fois que je vois un code similaire, je serais déjà riche.

Voyons voir ce qui se passe ici. Je dois dire tout de suite qu'il s'agit d'un code très ancien écrit bien avant même C ++ 11, sans parler de normes plus modernes. Nous pouvons dire que j'ai spécifiquement recherché un fragment de l'époque des civilisations anciennes.

Donc, premièrement, cette fonction accepte une liste d'arguments entre parenthèses en entrée. Quelque chose comme ceci:

(42, 23)

La deuxième fonction est appelée ici pour obtenir le contenu des crochets. Elle ne fait que se déplacer une fois à droite puis une fois à gauche à travers l'arbre binaire. Ensuite, la boucle obtient séquentiellement les éléments: 42, puis une virgule, puis 23, et à l'étape suivante, le pointeur argsdevient nul parce que nous arrivons à la fin de la branche. La boucle, bien sûr, saute les virgules inintéressantes.

Des fonctions similaires avec une logique légèrement modifiée peuvent être trouvées à de nombreux endroits, en particulier dans l'ancien code.

Un autre exemple. Comment savoir s'il y a un appel à une certaine fonction dans un certain bloc de code? Comme ça:

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

Remarque. Un lecteur attentif peut le remarquer. Quel âge a-t-il? Là, std :: string_view ressort . Tout est simple, même le code le plus ancien est progressivement refactorisé et progressivement rien de tel ne restera.

Ce serait bien d'utiliser quelque chose de plus élégant ici, non? Eh bien, par exemple, l'algorithme standard find_if . Quel est l'algorithme là-bas, même une plage normale pour améliorerait considérablement la lisibilité et faciliterait la prise en charge d'un tel code.

Essayons d'y parvenir.

Mettez l'arbre dans la boite

Notre objectif est de faire en sorte que l'arbre se comporte comme un conteneur STL. De plus, nous ne devons pas nous soucier de la structure interne des listes, nous voulons itérer uniformément sur les nœuds, par exemple, comme ceci:

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

Comme vous pouvez le voir, nous avons ici une certaine entité appelée someTreeContainer , que nous ne connaissons pas encore. Un tel conteneur doit avoir au moins des méthodes de début et de fin qui renvoient des itérateurs. En parlant d'itérateurs, ils devraient également se comporter comme des itérateurs. Commençons par eux.

Dans le cas le plus simple, l'itérateur ressemble à ceci:

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

Afin de ne pas encombrer le code, j'ai supprimé certains détails. Les points clés ici sont le déréférencement et l'incrémentation. Le modèle est nécessaire pour que l'itérateur puisse travailler avec des données constantes et non constantes.

Nous allons maintenant écrire le conteneur dans lequel nous placerons le nœud d'arbre. Voici l'option la plus simple:

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

Nous avons terminé, nous pouvons nous disperser, merci de votre attention.

Non, attends un instant. Ça ne peut pas être aussi simple, non? Revenons à nos deux options de liste - avec et sans délimiteurs. Ici, lors de l'incrémentation, nous prenons simplement le bon nœud de l'arbre, donc cela ne résout pas le problème. Nous devons toujours ignorer les virgules si nous voulons travailler uniquement avec des données.

Pas de problème, nous ajoutons simplement un paramètre de modèle supplémentaire à l'itérateur. Disons comme ceci:

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

Comment cela nous aidera-t-il? Élémentaire. Nous vérifierons ce paramètre par incréments et nous nous comporterons en conséquence. Heureusement, en C ++ 17, nous pouvons résoudre ce problème au stade de la compilation en utilisant la construction if constexpr :

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

C'est mieux, maintenant nous pouvons choisir un itérateur pour répondre à nos besoins. Que faire des conteneurs? Vous pouvez, par exemple, comme ceci:

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

Maintenant, avons-nous définitivement terminé? En fait, pas vraiment.

Mais ce n'est pas tout

Regardons ce code:

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

Je n'aime vraiment pas grand-chose dans ce code, en commençant par la boucle avec le compteur et en terminant par le fait que la fonction GetEnumElementInfo semble très suspecte. Maintenant, cela reste une boîte noire pour nous, mais nous pouvons supposer qu'il supprime l'élément enum par index et renvoie son nom et son nœud dans l'arborescence via les paramètres de sortie. La valeur de retour est également un peu étrange. Débarrassons-nous de tout cela - un travail idéal pour notre itérateur de liste:

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

Pas mal. Seul ce code ne compile pas. Pourquoi? Parce que l'index que nous avons supprimé a été utilisé dans le corps de la boucle sous l'appel à GetEnumElementInfo . Je ne dirai pas ici exactement comment il a été utilisé, car ce n'est pas important maintenant. Il suffit de dire qu'un index est nécessaire.

Eh bien, ajoutons une variable et gâchons notre beau code:

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

Toujours une option de travail, mais je réagis personnellement à quelque chose comme ça:

Eh bien, essayons de résoudre ce problème. Nous avons besoin de quelque chose qui puisse compter automatiquement les éléments. Ajoutez un itérateur avec un compteur. J'ai de nouveau ignoré les détails supplémentaires par souci de concision:

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

Maintenant, nous pouvons écrire un tel code, non?

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

En général, nous le pouvons vraiment, mais il y a un problème. Si vous regardez ce code, vous remarquerez peut-être que nous avons introduit une autre entité - quelque chose nommé PtreeCountedContainer . Il semble que la situation se complique. Je ne veux vraiment pas jongler avec différents types de récipients, et étant donné qu'ils sont les mêmes à l'intérieur, la main elle-même atteint le rasoir d'Occam.

Nous devrons utiliser un itérateur comme paramètre de modèle pour le conteneur, mais plus à ce sujet plus tard.

Types de zoo

Détournez-vous des compteurs et des variétés d'itérateurs pendant une minute. À la recherche d'un contournement universel des nœuds, nous avons oublié la chose la plus importante - l'arbre lui-même.

Jetez un œil à ce code:

int a, b, c = 0, d;

Ce que nous voyons dans l'arbre:

Passons maintenant en revue la liste des déclarants, mais je vais d'abord vous dire autre chose sur l'arbre. Tout le temps avant cela, nous avions affaire à un pointeur vers la classe Ptree . Il s'agit de la classe de base dont tous les autres types de nœuds sont hérités. Grâce à leurs interfaces, nous pouvons obtenir des informations supplémentaires. En particulier, le nœud le plus haut de l'image peut nous renvoyer la liste des déclarants sans utiliser de fonctions utilitaires comme First et Second . De plus, nous n'avons pas besoin des méthodes de bas niveau Car et Cdr (bonjour aux fans du langage Lisp). C'est très bien, car dans les diagnostics, nous pouvons ignorer l'implémentation de l'arborescence. Je pense que tout le monde convient que les abstractions actuelles sont très mauvaises.

Voici à quoi ressemble le contournement de tous les déclarants:

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

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

La méthode GetDeclarators renvoie un conteneur itérable . Son type dans ce cas est PtreeContainer <const Ptree, PtreeIteratorTag :: List> .

Avec ce code, tout irait bien sans le casting. Le fait est que la fonction ProcessDecl veut un pointeur vers une classe dérivée de Ptree , mais nos itérateurs n'en savent rien. Je voudrais me débarrasser de la nécessité de convertir les types manuellement.

Il semble qu'il est temps de changer à nouveau l'itérateur et d'ajouter la capacité de lancer.

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

Afin de ne pas écrire tous ces arguments de modèle manuellement à chaque fois, nous ajoutons quelques alias pour toutes les occasions:

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

C'est mieux. Maintenant, si nous n'avons pas besoin de castes, nous pouvons spécifier uniquement le premier argument de modèle, et nous ne pouvons pas non plus obstruer nos têtes avec la valeur du paramètre tag .

Mais que faire des conteneurs? Permettez-moi de vous rappeler que nous voulons avoir une seule classe universelle qui convient à tout itérateur. Maintenant, c'est indécemment de nombreuses combinaisons différentes, et nous avons besoin de simplicité. Quelque chose comme ça:

Autrement dit, nous voulons qu'une seule classe de conteneur puisse prendre en charge tous les types de nos itérateurs et être en mesure de leur dire quel type renvoyer lors du déréférencement. Ensuite, dans le code, nous créons simplement le conteneur dont nous avons besoin et commençons à travailler avec lui sans penser aux itérateurs dont nous avons besoin.

Nous examinerons cette question dans la section suivante.

Magie des motifs

Voici donc ce dont nous avons besoin:

Un conteneur qui peut fonctionner universellement avec n'importe quel itérateur.
Un itérateur, qui, selon la liste des nœuds, peut fonctionner à la fois avec chaque élément et via un seul.
Le même itérateur, mais avec un compteur.
Les deux itérateurs doivent pouvoir effectuer un cast lors du déréférencement, si le type est également spécifié.

Tout d'abord, nous devons en quelque sorte lier le type de conteneur au type d'itérateur via des paramètres de modèle. Voici ce qui s'est passé:

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

Vous pouvez également ajouter d'autres méthodes au conteneur. Par exemple, voici comment nous pouvons trouver le nombre d'éléments:

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

Ou voici l'opérateur d'indexation:

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

Il est clair que vous devez gérer ces méthodes avec soin en raison de leur complexité linéaire, mais parfois elles sont utiles.

Pour faciliter l'utilisation, ajoutez des 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>;

Nous pouvons maintenant créer facilement des conteneurs. Supposons que dans la classe PtreeDeclaration déjà mentionnée , nous voulons obtenir un conteneur de la méthode GetDeclarators , dont l'itérateur ignore les séparateurs, alors qu'il n'y a pas de compteur, et lorsqu'il est déréférencé, il renvoie une valeur de type PtreeDeclarator . Voici la déclaration d'un tel conteneur:

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

Et enfin, puisque l'inférence de type pour les alias n'apparaîtra qu'en C ++ 20, afin de créer plus facilement des conteneurs dans le code, nous avons ajouté de telles fonctions:

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

Rappelez la fonction qui fonctionnait avec enum . Maintenant, nous pouvons l'écrire comme ceci:

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

Comparez avec la version originale, il me semble, c'est devenu mieux:

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

C'est tout, les amis

C'est tout pour moi, merci de votre attention. J'espère que vous avez découvert quelque chose d'intéressant ou même d'utile.

Selon le contenu de l'article, il peut sembler que je gronde le code de notre analyseur et que je veuille dire que tout va mal là-bas. Ce n'est pas vrai. Comme tout projet ayant une histoire, notre analyseur regorge de dépôts géologiques qui sont restés des époques passées. Considérez que nous venons de fouiller, de retirer des artefacts de l'ancienne civilisation du sous-sol et de procéder à la restauration pour les rendre beaux sur le plateau.

P.S

Il y aura beaucoup de code ici. J'ai douté d'inclure ou non l'implémentation d'itérateurs ici et j'ai finalement décidé de l'inclure afin de ne rien laisser dans les coulisses. Si vous n'êtes pas intéressé par la lecture du code, ici je vais vous dire au revoir. Le reste je vous souhaite un agréable moment avec des modèles.

Le code

Itérateur régulier

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

Itérateur avec compteur

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

Conteneur générique

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

Si vous souhaitez partager cet article avec un public anglophone, veuillez utiliser le lien vers la traduction: Yuri Minaev. Comment grimper à un arbre .

Comment grimper à un arbre