🧜 ☸️ 🐜 Como escalar uma árvore ↖️ 🤪 🤹🏼

Mais precisamente, como se livrar disso. Mas as primeiras coisas primeiro. Este artigo está um pouco fora do formato usual de artigo do PVS-Studio. Muitas vezes escrevemos sobre a verificação de outros projetos, mas quase nunca abrimos a porta da nossa cozinha interna. É hora de corrigi-lo e falar sobre como o analisador é construído por dentro. Mais precisamente, sobre a parte mais importante de suas partes - a árvore de sintaxe. O artigo se concentrará na parte do PVS-Studio relacionada às linguagens C e C ++.

Primeiras coisas primeiro

A árvore de sintaxe é a parte central de qualquer compilador. De uma forma ou de outra, o código precisa ser apresentado de uma forma conveniente para o processamento do programa, e acontece que a estrutura da árvore é mais adequada para isso. Não vou entrar em teoria aqui - basta dizer que a árvore reflete muito bem a hierarquia de expressões e blocos no código e, ao mesmo tempo, contém apenas os dados necessários para o trabalho.

O que o compilador tem a ver com o analisador estático? O fato é que essas duas ferramentas têm muito em comum. No estágio inicial de analisar o código, eles fazem o mesmo trabalho. Primeiro, o código é dividido em um fluxo de tokens, que é alimentado ao analisador. Em seguida, no processo de análise sintática e semântica, os tokens são organizados em uma árvore, que é enviada mais adiante ao longo do pipeline. Nesse estágio, os compiladores podem executar otimizações intermediárias antes de gerar código binário, os analisadores estáticos começam a ignorar os nós e a executar várias verificações.

No analisador PVS-Studio com uma árvore construída, várias coisas acontecem:

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

Se você estiver interessado nos detalhes de como a análise funciona, recomendo a leitura do artigo “ Tecnologias usadas no analisador de código PVS-Studio para encontrar erros e possíveis vulnerabilidades ”. Alguns pontos da lista são examinados em detalhes.

Veremos com mais detalhes o que acontece com a árvore dentro do analisador e como ela se parece. Com uma breve introdução, é hora de chegar ao fundo do assunto.

Como funciona

Historicamente, o PVS-Studio usa uma árvore binária para representar o código. Essa estrutura de dados clássica é familiar a todos - temos um nó que geralmente se refere a dois filhos. Nós que não deveriam ter descendentes, chamarei terminais, todos os outros - não terminais. Um não-terminal pode, em alguns casos, não ter nós filhos, mas sua principal diferença em relação ao terminal é que os descendentes são fundamentalmente permitidos para ele. Os nós terminais (ou folhas) não têm a capacidade de se referir a algo diferente do pai.

A estrutura usada no PVS-Studio é um pouco diferente da árvore binária clássica - isso é necessário por conveniência. Nós de terminal geralmente correspondem a palavras-chave, nomes de variáveis, literais e assim por diante. Não terminais - vários tipos de expressões, blocos de código, listas e similares, os elementos constituintes da árvore.

Do ponto de vista dos compiladores, tudo é bastante padrão aqui, aconselho a todos os interessados nos clássicos do gênero - The Dragon Book .

Estamos seguindo em frente. Vejamos um exemplo de código simples e como o analisador o vê. Além disso, haverá muitas fotos do nosso utilitário interno de visualização em árvore.

Na verdade, um exemplo:

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

Essa função simples após o processamento pelo analisador terá a seguinte aparência (nós não terminais são destacados em amarelo):

Essa visão tem seus prós e contras, e a última, na minha opinião, um pouco mais. Mas vamos olhar para a árvore. Faça imediatamente uma reserva de que é um pouco redundante, por exemplo, porque contém pontuação e parênteses. Do ponto de vista da compilação, isso é um lixo supérfluo, mas essas informações são algumas vezes necessárias ao analisador para algumas regras de diagnóstico. Em outras palavras, o analisador não funciona com a árvore de sintaxe abstrata (AST), mas com a árvore de análise (DT).

A árvore cresce da esquerda para a direita e de cima para baixo. Os nós filhos esquerdos sempre contêm algo significativo, como declaradores. Se você olhar para a direita, veremos os não terminais intermediários marcados com a palavra NonLeaf. Eles são necessários apenas para que a árvore retenha sua estrutura. Para as necessidades de análise, esses nós não carregam nenhuma carga de informações.

Enquanto estaremos interessados na parte esquerda da árvore. Aqui está em um close maior:

Este anúncio apresenta. O nó pai PtreeDeclarator é um objeto através do qual você pode acessar nós com o nome da função e seus parâmetros. Ele também armazena a assinatura codificada para o sistema de tipos. Parece-me que esta imagem é bastante visual e é muito fácil comparar os elementos da árvore com o código.

Parece fácil, certo?

Para maior clareza, vamos dar um exemplo mais simples. Imagine que temos um código que chama nossa função f :

f(42, 23);

Uma chamada de função na árvore terá a seguinte aparência:

A estrutura é muito semelhante, somente aqui vemos uma chamada de função em vez de sua declaração. Agora, suponha que desejássemos passar por todos os argumentos e fazer algo com cada um deles. Essa é uma tarefa real, frequentemente encontrada no código do analisador. É claro que tudo não se limita a argumentos e que tipos diferentes de nós precisam ser classificados, mas agora consideraremos este exemplo específico.

Suponha que tenhamos apenas um ponteiro para o nó FUNCALL pai . De qualquer não terminal, podemos obter os nós filhos esquerdo e direito. O tipo de cada um deles é conhecido. Conhecemos a estrutura da árvore, para que possamos alcançar imediatamente o nó sob o qual está a lista de argumentos - este é o NonLeaf , do qual o terminal cresce na figura 42. Não sabemos o número de argumentos com antecedência e há vírgulas na lista que, nesse caso, não são de nosso interesse.

Como faremos isso? Leia.

Fábrica de bicicletas

Parece que iterar através de uma árvore é bastante simples. Você só precisa escrever uma função que faça isso e usá-la em qualquer lugar. É possível passar um lambda como argumento para manipular cada elemento. Realmente seria assim, se não fosse por algumas nuances.

Em primeiro lugar, andar em volta de uma árvore sempre deve ser um pouco diferente. A lógica do processamento de cada nó é diferente, bem como a lógica do trabalho com a lista inteira. Digamos, em um caso, queremos examinar os argumentos da lista e passar cada um deles para uma determinada função para processamento. Em outro, queremos selecionar e retornar um argumento que atenda a alguns requisitos. Ou filtre a lista e descarte quaisquer elementos desinteressantes dela.

Em segundo lugar, às vezes você precisa conhecer o índice do elemento atual. Por exemplo, queremos processar apenas os dois primeiros argumentos e parar.

Terceiro, vamos desviar do exemplo da função. Digamos que temos um código como este:

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

Esse código é idiota, eu sei, mas vamos nos concentrar agora na aparência da árvore. Já vimos uma declaração de função, aqui precisamos do seu corpo:

Este caso é como uma lista de argumentos, mas você pode notar alguma diferença. Dê uma outra olhada na foto da seção anterior.

Você percebeu?

É isso mesmo, não há vírgulas nesta lista, o que significa que você pode processá-lo em uma linha e não se preocupar em ignorar separadores.

No total, temos pelo menos dois casos:

Lista separada.
A lista completa.

Agora vamos ver como tudo isso acontece no código do analisador. Aqui está um exemplo de percorrer uma lista de argumentos. Esta é uma versão simplificada de uma das funções no tradutor.

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

Se eu recebesse um dólar toda vez que vir um código semelhante, já ficaria rico.

Vamos ver o que acontece aqui. Devo dizer imediatamente que esse código é muito antigo, escrito muito antes do C ++ 11, sem mencionar os padrões mais modernos. Podemos dizer que procurei especificamente um fragmento dos tempos das civilizações antigas.

Portanto, primeiramente, essa função aceita uma lista de argumentos entre parênteses como entrada. Algo assim:

(42, 23)

A segunda função é chamada aqui para obter o conteúdo dos colchetes. Tudo o que ela faz é mover uma vez para a direita e depois para a esquerda através da árvore binária. Em seguida, o loop obtém sequencialmente os elementos: 42, depois uma vírgula, depois 23 e, na próxima etapa, o ponteiro argstorna-se zero porque chegamos ao final do ramo. O loop, é claro, pula vírgulas desinteressantes.

Funções semelhantes com lógica ligeiramente alterada podem ser encontradas em muitos lugares, especialmente no código antigo.

Outro exemplo. Como sei se há uma chamada para uma determinada função em um determinado bloco de código? Curtiu isso:

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

Nota. Um leitor atento pode perceber. Quantos anos tem ele? Lá std :: string_view se destaca. Tudo é simples, mesmo o código mais antigo é gradualmente refatorado e gradualmente nada permanece.

Seria bom usar algo mais elegante aqui, certo? Bem, por exemplo, o algoritmo find_if padrão . Qual é o algoritmo existente, mesmo para um intervalo normal, melhoraria bastante a legibilidade e facilitaria o suporte a esse código.

Vamos tentar conseguir isso.

Coloque a árvore na caixa

Nosso objetivo é fazer com que a árvore se comporte como um contêiner STL. Além disso, não devemos nos preocupar com a estrutura interna das listas, queremos iterar uniformemente os nós, por exemplo, assim:

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

Como você pode ver, aqui temos uma certa entidade chamada someTreeContainer , sobre a qual ainda não sabemos. Esse contêiner deve ter pelo menos métodos de início e fim que retornem iteradores. Falando em iteradores, eles também devem se comportar como os padrão. Vamos começar com eles.

No caso mais simples, o iterador fica assim:

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

Para não bagunçar o código, removi alguns detalhes. Os pontos principais aqui são desreferenciamento e incremento. O modelo é necessário para que o iterador possa trabalhar com dados constantes e não constantes.

Agora vamos escrever o contêiner no qual colocaremos o nó da árvore. Aqui está a opção mais simples:

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

Terminamos, podemos dispersar, obrigado pela atenção.

Não, espere um momento. Não pode ser tão simples, certo? Vamos voltar às nossas duas opções de lista - com e sem delimitadores. Aqui, ao incrementar, simplesmente pegamos o nó certo da árvore, para que isso não resolva o problema. Ainda precisamos pular vírgulas se quisermos trabalhar apenas com dados.

Não é um problema, apenas adicionamos um parâmetro de modelo adicional ao iterador. Digamos assim:

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

Como isso nos ajudará? Elementar. Verificaremos esse parâmetro em incrementos e nos comportaremos de acordo. Felizmente, no C ++ 17, podemos resolver isso no estágio de compilação usando a construção if constexpr :

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

Melhor, agora podemos escolher um iterador para atender às nossas necessidades. O que fazer com os contêineres? Você pode, por exemplo, assim:

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

Agora, nós definitivamente terminamos? De fato, não de verdade.

Mas isso não é tudo

Vamos olhar para este código:

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

Eu realmente não gosto muito desse código, começando do loop com o contador e terminando com o fato de que a função GetEnumElementInfo parece muito suspeita. Agora ele continua sendo uma caixa preta para nós, mas podemos assumir que ele retira o elemento enum pelo índice e retorna seu nome e nó na árvore através dos parâmetros de saída. O valor de retorno também é um pouco estranho. Vamos nos livrar completamente disso - um trabalho ideal para o nosso iterador de lista:

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

Não é ruim. Somente esse código não é compilado. Por quê? Como o índice que removemos foi usado no corpo do loop abaixo da chamada para GetEnumElementInfo . Não vou dizer aqui exatamente como foi usado, porque não é importante agora. Basta dizer que é necessário um índice.

Bem, vamos adicionar uma variável e estragar nosso belo código:

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

Ainda é uma opção de trabalho, mas eu pessoalmente reajo a algo assim:

Bem, vamos tentar resolver esse problema. Precisamos de algo que possa contar elementos automaticamente. Adicione um iterador com um contador. Mais uma vez, pulei os detalhes extras por questões de concisão:

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

Agora podemos escrever esse código, certo?

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

Em geral, realmente podemos, mas há um problema. Se você observar esse código, poderá perceber que introduzimos outra entidade - algo chamado PtreeCountedContainer . Parece que a situação está ficando complicada. Eu realmente não quero fazer malabarismos com diferentes tipos de contêineres e, como eles são iguais por dentro, a própria mão pega a navalha de Occam.

Teremos que usar um iterador como um parâmetro de modelo para o contêiner, mas mais sobre isso mais tarde.

Tipos de zoológico

Distraia os contadores e variedades de iteradores por um minuto. Em busca de um desvio universal de nós, esquecemos a coisa mais importante - a própria árvore.

Dê uma olhada neste código:

int a, b, c = 0, d;

O que vemos na árvore:

Vamos agora percorrer a lista de declaradores, mas primeiro vou lhe contar outra coisa sobre a árvore. Todo o tempo antes disso, estávamos lidando com um ponteiro para a classe Ptree . Essa é a classe base da qual todos os outros tipos de nós são herdados. Através de suas interfaces, podemos obter informações adicionais. Em particular, o nó superior da figura pode retornar para nós a lista de declaradores sem usar funções utilitárias como Primeiro e Segundo . Além disso, não precisamos de métodos de baixo nível Car e Cdr (olá para os fãs da linguagem Lisp). Isso é muito bom, pois no diagnóstico podemos ignorar a implementação da árvore. Acho que todo mundo concorda que as abstrações atuais são muito ruins.

É assim que o desvio de todos os declaradores se parece:

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

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

O método GetDeclarators retorna um contêiner iterável . Seu tipo nesse caso é PtreeContainer <const Ptree, PtreeIteratorTag :: List> .

Com esse código, tudo ficaria bem se não fosse o elenco. O fato é que a função ProcessDecl deseja um ponteiro para uma classe derivada da Ptree , mas nossos iteradores não sabem nada sobre isso. Gostaria de me livrar da necessidade de converter tipos manualmente.

Parece que é hora de mudar o iterador novamente e adicionar a capacidade de transmitir.

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

Para não escrever todos esses argumentos de modelo manualmente a cada vez, adicionamos alguns apelidos para todas as ocasiões:

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

Isso é melhor. Agora, se não precisarmos de castas, podemos especificar apenas o primeiro argumento do modelo e também não podemos entupir o valor do parâmetro tag .

Mas o que fazer com os contêineres? Deixe-me lembrá-lo de que queremos ter apenas uma classe universal adequada para qualquer iterador. Agora são indecentemente muitas combinações diferentes, e precisamos de simplicidade. Algo assim:

Ou seja, queremos que uma única classe de contêiner seja capaz de dar suporte a todos os tipos de nossos iteradores e de dizer a eles que tipo retornar quando fizer o cancelamento da referência. Em seguida, no código, simplesmente criamos o contêiner de que precisamos e começamos a trabalhar com ele sem pensar em quais iteradores precisamos.

Examinaremos essa questão na próxima seção.

Magia de padrões

Então aqui está o que precisamos:

Um contêiner que pode funcionar universalmente com qualquer iterador.
Um iterador, que, dependendo da lista de nós, pode funcionar com cada elemento e através de um.
O mesmo iterador, mas com um contador.
Ambos os iteradores devem ser capazes de converter quando derreferencing, se o tipo for especificado adicionalmente.

Primeiro de tudo, precisamos vincular de alguma forma o tipo de contêiner ao tipo de iterador através dos parâmetros do modelo. Aqui está o que aconteceu:

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

Além disso, você pode adicionar mais métodos ao contêiner. Por exemplo, é assim que podemos descobrir o número de elementos:

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

Ou aqui está o operador de indexação:

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

É claro que você precisa lidar com esses métodos com cuidado devido à sua complexidade linear, mas às vezes eles são úteis.

Para facilitar o uso, adicione aliases:

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

Agora podemos criar contêineres facilmente. Digamos, na classe PtreeDeclaration já mencionada , queremos obter um contêiner do método GetDeclarators , cujo iterador ignora os separadores, enquanto não há contador, e quando desreferenciado, ele retorna um valor do tipo PtreeDeclarator . Aqui está a declaração desse contêiner:

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

E, finalmente, como a inferência de tipo para aliases aparecerá apenas em C ++ 20, para criar mais convenientemente contêineres no código, adicionamos essas funções:

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

Lembre-se da função que trabalhou com enum . Agora podemos escrever assim:

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

Compare com a versão original, parece-me, tornou-se melhor:

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

Isso é tudo, pessoal

Isso é tudo para mim, obrigado por sua atenção. Espero que você tenha descoberto algo interessante ou até útil.

De acordo com o conteúdo do artigo, parece que estou repreendendo o código do nosso analisador e quero dizer que tudo está ruim por lá. Isso não é verdade. Como qualquer projeto com uma história, nosso analisador está cheio de depósitos geológicos que permaneceram de épocas passadas. Considere que acabamos de escavar, remover artefatos da civilização antiga de baixo do solo e realizar a restauração para torná-los com boa aparência na prateleira.

P.S

Haverá muito código aqui. Eu duvidava de incluir a implementação de iteradores aqui ou não e, no final, decidi incluí-lo para não deixar nada nos bastidores. Se você não está interessado em ler o código, aqui vou dizer adeus a você. O resto, desejo-lhe um tempo agradável com modelos.

O código

Iterador regular

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

Iterador com contador

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

Container genérico

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

Se você deseja compartilhar este artigo com um público que fala inglês, use o link para a tradução: Yuri Minaev. Como escalar uma árvore .

Como escalar uma árvore