Más precisamente, cómo bajar de él. Pero lo primero es lo primero. Este artículo está un poco fuera del formato de artículo habitual de PVS-Studio. A menudo escribimos sobre verificar otros proyectos, pero casi nunca abrimos la puerta de nuestra cocina interior. Es hora de arreglarlo y hablar sobre cómo se construye el analizador desde adentro. Más precisamente, sobre la más importante de sus partes: el árbol de sintaxis. El artículo se centrará en la parte de PVS-Studio que se relaciona con los lenguajes C y C ++.Lo primero es lo primero
El árbol de sintaxis es la parte central de cualquier compilador. De una forma u otra, el código debe presentarse en una forma conveniente para el procesamiento del programa, y resulta que la estructura de árbol es la más adecuada para esto. No entraré en teoría aquí: basta con decir que el árbol refleja muy bien la jerarquía de expresiones y bloques en el código, y al mismo tiempo contiene solo los datos necesarios para el trabajo.¿Qué tiene que ver el compilador con el analizador estático? El hecho es que estas dos herramientas tienen mucho en común. En la etapa inicial de analizar el código, hacen el mismo trabajo. Primero, el código se divide en una secuencia de tokens, que se alimenta al analizador. Luego, en el proceso de análisis sintáctico y semántico, los tokens se organizan en un árbol, que se envía a lo largo de la tubería. En esta etapa, los compiladores pueden realizar optimizaciones intermedias antes de generar código binario, los analizadores estáticos comienzan a pasar por alto los nodos y lanzar varias comprobaciones.En el analizador PVS-Studio con un árbol incorporado, suceden varias cosas:- . , , , using typedef, . , . ;
- . , ;
- , , , ;
- . ( ). . , nullptr , , . ;
- . , . , .
Si está interesado en los detalles de cómo funciona el análisis, le recomiendo leer el artículo " Tecnologías utilizadas en el analizador de código PVS-Studio para encontrar errores y vulnerabilidades potenciales ". Algunos puntos de la lista se examinan allí en detalle.Veremos con más detalle lo que le sucede al árbol dentro del analizador y cómo se ve en absoluto. Con una breve introducción, es hora de llegar al fondo del asunto.Cómo funciona
Históricamente, PVS-Studio usa un árbol binario para representar el código. Esta estructura de datos clásica es familiar para todos: tenemos un nodo que generalmente se refiere a dos hijos. Los nodos que se supone que no tienen descendientes, llamaré terminales, todos los demás, no terminales. Un no terminal puede en algunos casos no tener nodos secundarios, pero su diferencia clave con respecto al terminal es que los descendientes están fundamentalmente permitidos para él. Los nodos terminales (u hojas) carecen de la capacidad de referirse a algo diferente al padre.La estructura utilizada en PVS-Studio es ligeramente diferente del árbol binario clásico, esto es necesario por conveniencia. Los nodos terminales generalmente corresponden a palabras clave, nombres de variables, literales, etc. No terminales: varios tipos de expresiones, bloques de código, listas y similares, los elementos constitutivos de un árbolDesde el punto de vista de los compiladores, todo es bastante estándar aquí, aconsejo a todos los interesados en los clásicos del género: The Dragon Book .Estamos avanzando Veamos un ejemplo de código simple y cómo lo ve el analizador. Además, habrá muchas imágenes de nuestra utilidad interna de visualización de árboles.En realidad, un ejemplo:int f(int a, int b)
{
return a + b;
}
Esta función simple después del procesamiento por el analizador se verá así (los nodos no terminales se resaltan en amarillo):Este punto de vista tiene sus pros y sus contras, y este último, en mi opinión, un poco más. Pero echemos un vistazo al árbol. Inmediatamente haga una reserva de que es algo redundante, por ejemplo, porque contiene signos de puntuación y paréntesis. Desde el punto de vista de la compilación, esto es basura innecesaria, pero el analizador a veces necesita esa información para algunas reglas de diagnóstico. En otras palabras, el analizador no funciona con el árbol de sintaxis abstracta (AST), sino con el árbol de análisis (DT).El árbol crece de izquierda a derecha y de arriba a abajo. Los nodos secundarios izquierdos siempre contienen algo significativo, como los declaradores. Si mira a la derecha, veremos no terminales intermedios marcados con la palabra NonLeaf. Solo se necesitan para que el árbol conserve su estructura. Para las necesidades de análisis, tales nodos no llevan ninguna carga de información.Si bien estaremos interesados en la parte izquierda del árbol. Aquí está en un primer plano más grande:Este anuncio presenta. El nodo padre PtreeDeclarator es un objeto a través del cual puede acceder a los nodos con el nombre de la función y sus parámetros. También almacena la firma codificada para el sistema de tipos. Me parece que esta imagen es bastante visual, y es bastante fácil comparar los elementos del árbol con el código.Parece fácil, ¿verdad?Para mayor claridad, tomemos un ejemplo más simple. Imagine que tenemos un código que llama a nuestra función f :f(42, 23);
Una llamada de función en el árbol se verá así:La estructura es muy similar, solo que aquí vemos una llamada a la función en lugar de su declaración. Ahora supongamos que queremos analizar todos los argumentos y hacer algo con cada uno de ellos. Esta es una tarea real que a menudo se encuentra en el código del analizador. Está claro que todo no está limitado a argumentos, y los diferentes tipos de nodos deben ser ordenados, pero ahora consideraremos este ejemplo específico.Supongamos que solo tenemos un puntero al nodo principal FUNCALL . Desde cualquier no terminal, podemos obtener los nodos secundarios izquierdo y derecho. El tipo de cada uno de ellos es conocido. Conocemos la estructura del árbol, por lo que podemos llegar inmediatamente al nodo en el que se encuentra la lista de argumentos: esto es NonLeaf , desde el cual el terminal crece en la imagen 42. No sabemos la cantidad de argumentos por adelantado, y hay comas en la lista que en este caso no nos interesan en absoluto.¿Como haremos esto? Sigue leyendo.Fábrica de bicicletas
Parece que iterar a través de un árbol es bastante simple. Solo necesita escribir una función que haga esto y usarla en todas partes. Es posible pasarle una lambda como argumento para manejar cada elemento. Realmente sería así, si no fuera por un par de matices.En primer lugar, ir alrededor de un árbol cada vez tiene que ser un poco diferente. La lógica de procesar cada nodo es diferente, así como la lógica de trabajar con toda la lista. Digamos, en un caso, queremos revisar los argumentos de la lista y pasar cada uno de ellos a una determinada función para su procesamiento. En otro, queremos seleccionar y devolver un argumento que cumpla con algunos requisitos. O filtre la lista y descarte cualquier elemento que no le interese.En segundo lugar, a veces necesita saber el índice del elemento actual. Por ejemplo, queremos procesar solo los dos primeros argumentos y detener.Tercero, divaguemos del ejemplo de la función. Digamos que tenemos un código como este:int f(int a, int b)
{
int c = a + b;
c *= 2;
if (c < 42) return c;
return 42;
}
Este código es tonto, lo sé, pero concentrémonos ahora en cómo se ve el árbol. Ya hemos visto una declaración de función, aquí necesitamos su cuerpo:Este caso es como una lista de argumentos, pero puede notar alguna diferencia. Eche otro vistazo a la imagen de la sección anterior.¿Has notado?Así es, no hay comas en esta lista, lo que significa que puede procesarlo en una fila y no preocuparse por omitir separadores.En total, tenemos al menos dos casos:- Lista separada
- La lista completa
Ahora veamos cómo sucede todo esto en el código del analizador. Aquí hay un ejemplo al recorrer la lista de argumentos. Esta es una versión simplificada de una de las funciones del traductor.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 me pagaran un dólar cada vez que veo un código similar, ya me haría rico.Veamos que pasa aquí. Debo decir de inmediato que este es un código muy antiguo escrito mucho antes incluso de C ++ 11, sin mencionar los estándares más modernos. Podemos decir que busqué específicamente un fragmento de los tiempos de las civilizaciones antiguas.Entonces, en primer lugar, esta función acepta una lista de argumentos entre paréntesis como entrada. Algo como esto:(42, 23)La segunda función se llama aquí para obtener el contenido de los corchetes. Todo lo que hace es moverse una vez hacia la derecha y luego una vez hacia la izquierda a través del árbol binario. A continuación, el bucle obtiene secuencialmente los elementos: 42, luego una coma, luego 23, y en el siguiente paso, el puntero argsse convierte en cero porque llegamos al final de la rama. El bucle, por supuesto, omite comas sin interés.Se pueden encontrar funciones similares con una lógica ligeramente modificada en muchos lugares, especialmente en el código anterior.Otro ejemplo. ¿Cómo sé si hay una llamada a una determinada función en un determinado bloque de código? Como eso: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. Un lector atento puede notarlo. ¿Cuántos años tiene él? Hay std :: string_view sobresale. Todo es simple, incluso el código más antiguo se refactoriza gradualmente y gradualmente no quedará nada por el estilo.Sería bueno usar algo más elegante aquí, ¿verdad? Bueno, por ejemplo, el algoritmo estándar find_if . ¿Cuál es el algoritmo allí? Incluso un rango normal basado en un rango mejoraría enormemente la legibilidad y facilitaría el soporte de dicho código.Intentemos lograr esto.Pon el arbol en la caja
Nuestro objetivo es hacer que el árbol se comporte como un contenedor STL. Además, no deberíamos preocuparnos por la estructura interna de las listas, queremos iterar uniformemente sobre los nodos, por ejemplo, así:void DoSomethingWithTree(const Ptree* tree)
{
....
for (auto cur : someTreeContainer)
{
....
}
}
Como puede ver, aquí tenemos una cierta entidad llamada someTreeContainer , que aún no conocemos. Tal contenedor debería tener al menos métodos de inicio y finalización que devuelvan iteradores. Hablando de iteradores, también deberían comportarse como los estándar. Comencemos con ellos.En el caso más simple, el iterador se ve así: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 no saturar el código, eliminé algunos detalles. Los puntos clave aquí son desreferenciar e incrementar. La plantilla es necesaria para que el iterador pueda trabajar con datos constantes y no constantes.Ahora escribiremos el contenedor en el que colocaremos el nodo del árbol. Aquí está la opción más 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;
};
Hemos terminado, podemos dispersarnos, gracias por su atención.No, espera un momento. No puede ser tan simple, ¿verdad? Volvamos a nuestras dos opciones de lista, con y sin delimitadores. Aquí, al incrementar, simplemente tomamos el nodo derecho del árbol, para que esto no resuelva el problema. Todavía necesitamos omitir comas si queremos trabajar solo con datos.No es un problema, solo agregamos un parámetro de plantilla adicional al iterador. Digamos así: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 { .... };
¿Cómo nos ayudará esto? Elemental. Comprobaremos este parámetro en incrementos y nos comportaremos en consecuencia. Afortunadamente, en C ++ 17 podemos resolver esto en la etapa de compilación usando la construcción if constexpr :PtreeIterator& operator++() noexcept
{
if constexpr (tag == PtreeIteratorTag::Statement)
{
m_node = Rest(m_node);
}
else
{
m_node = RestRest(m_node);
}
return *this;
}
Eso es mejor, ahora podemos elegir un iterador para satisfacer nuestras necesidades. ¿Qué hacer con los contenedores? Puedes, por ejemplo, así:template <typename Node_t, PtreeIteratorTag tag>
class PtreeContainer
{
public:
using Iterator = PtreeIterator<Node_t, tag>;
....
};
Ahora, ¿definitivamente hemos terminado? De hecho, no realmente.Pero eso no es todo
Veamos 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);
....
}
}
Realmente no me gusta mucho este código, comenzando desde el bucle con el contador y terminando con el hecho de que la función GetEnumElementInfo parece muy sospechosa. Ahora sigue siendo un cuadro negro para nosotros, pero podemos suponer que saca el elemento enum por índice y devuelve su nombre y nodo en el árbol a través de los parámetros de salida. El valor de retorno también es un poco extraño. Eliminémoslo por completo: un trabajo ideal para nuestro iterador de listas:void ProcessEnum(const Ptree* argList)
{
for (auto elem : PtreeContainer<const Ptree, PtreeIteratorTag::List>(argList))
{
auto name = PtreeToString(elem);
....
}
}
No está mal. Solo este código no se compila. ¿Por qué? Debido a que el índice que eliminamos se usó en el cuerpo del bucle debajo de la llamada a GetEnumElementInfo . No diré aquí exactamente cómo se usó, porque ahora no es importante. Baste decir que se necesita un índice.Bueno, agreguemos una variable y estropeemos nuestro hermoso 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++);
}
}
Sigue siendo una opción de trabajo, pero personalmente reacciono a algo como esto:Bueno, intentemos resolver este problema. Necesitamos algo que pueda contar elementos automáticamente. Agregue un iterador con un contador. Nuevamente omití los detalles adicionales por brevedad: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;
};
Ahora podemos escribir ese código, ¿verdad?void ProcessEnum(const Ptree* argList)
{
for (auto [elem, i] :
PtreeCountedContainer<const Ptree, PtreeIteratorTag::List>(argList))
{
auto name = PtreeToString(elem);
....
UseIndexSomehow(i);
}
}
En general, realmente podemos, pero hay un problema. Si observa este código, puede notar que introdujimos otra entidad, algo llamado PtreeCountedContainer . Parece que la situación se está complicando. Realmente no quiero hacer malabarismos con diferentes tipos de contenedores, y dado que son los mismos en el interior, la mano misma alcanza la navaja de Occam.Tendremos que usar un iterador como parámetro de plantilla para el contenedor, pero más sobre eso más adelante.Tipos de zoológico
Distraer de contadores y variedades de iteradores por un minuto. En la búsqueda de un bypass universal de nodos, nos olvidamos de lo más importante: el árbol en sí.Echa un vistazo a este código:int a, b, c = 0, d;
Lo que vemos en el árbol:Ahora recorramos la lista de declaradores, pero primero te contaré algo más sobre el árbol. Todo el tiempo anterior a eso, estábamos tratando con un puntero a la clase Ptree . Esta es la clase base de la que se heredan todos los demás tipos de nodos. A través de sus interfaces podemos obtener información adicional. En particular, el nodo superior de la imagen puede devolvernos la lista de declaradores sin utilizar funciones de utilidad como Primero y Segundo . Además, no necesitamos métodos de bajo nivel Car y Cdr (hola a los fanáticos del lenguaje Lisp). Esto es muy bueno, ya que en diagnósticos podemos ignorar la implementación del árbol. Creo que todos están de acuerdo en que las abstracciones actuales son muy malas.Así es como se ve el bypass de todos los declaradores:void ProcessDecl(const PtreeDeclarator* decl) { .... }
void ProcessDeclarators(const PtreeDeclaration* declaration)
{
for (auto decl : declaration->GetDeclarators())
{
ProcessDecl(static_cast<const PtreeDeclarator*>(decl));
}
}
El método GetDeclarators devuelve un contenedor iterable . Su tipo en este caso es PtreeContainer <const Ptree, PtreeIteratorTag :: List> .Con este código, todo estaría bien si no fuera por el elenco. El hecho es que la función ProcessDecl quiere un puntero a una clase derivada de Ptree , pero nuestros iteradores no saben nada al respecto. Me gustaría deshacerme de la necesidad de convertir tipos manualmente.Parece que es hora de cambiar el iterador nuevamente y agregar la capacidad de lanzar.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 no escribir todos estos argumentos de plantilla manualmente cada vez, agregamos algunos alias para todas las ocasiones: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>;
Eso es mejor. Ahora, si no necesitamos castas, podemos especificar solo el primer argumento de plantilla, y tampoco podemos obstruir nuestras cabezas con el valor del parámetro de etiqueta .¿Pero qué hacer con los contenedores? Permítame recordarle que queremos tener solo una clase universal que sea adecuada para cualquier iterador. Ahora son indecentemente muchas combinaciones diferentes, y necesitamos simplicidad. Algo como esto:Es decir, queremos que una sola clase de contenedor sea capaz de admitir todos los tipos de nuestros iteradores y poder decirles qué tipo devolver al desreferenciar. Luego, en el código, simplemente creamos el contenedor que necesitamos y comenzamos a trabajar con él sin pensar en qué iteradores necesitamos.Examinaremos esta pregunta en la siguiente sección.Magia de patrón
Entonces, esto es lo que necesitamos:- Un contenedor que puede funcionar universalmente con cualquier iterador.
- Un iterador que, dependiendo de la lista de nodos, puede funcionar tanto con cada elemento como a través de uno.
- El mismo iterador, pero con un contador.
- Ambos iteradores deberían poder emitir al desreferenciar, si el tipo se especifica adicionalmente.
En primer lugar, debemos vincular de alguna manera el tipo de contenedor al tipo de iterador a través de parámetros de plantilla. Esto es lo que sucedió: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;
};
Además, puede agregar más métodos al contenedor. Por ejemplo, así es como podemos encontrar la cantidad de elementos:difference_type count() const noexcept
{
return std::distance(begin(), end());
}
O aquí está el operador de indexación: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{};
}
Está claro que debe manejar dichos métodos con cuidado debido a su complejidad lineal, pero a veces son útiles.Para facilitar su uso, agregue 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>;
Ahora podemos crear contenedores fácilmente. Digamos, en la clase PtreeDeclaration ya mencionada , queremos obtener un contenedor del método GetDeclarators , cuyo iterador omite los separadores, mientras que no hay contador en él, y cuando se desreferencia, devuelve un valor del tipo PtreeDeclarator . Aquí está la declaración de dicho contenedor: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);
}
}
Y finalmente, dado que la inferencia de tipos para los alias solo aparecerá en C ++ 20, para crear contenedores en el código de manera más conveniente, agregamos tales funciones: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 };
}
Recordemos la función que funcionó con enum . Ahora podemos escribirlo así:void ProcessEnum(const Ptree* argList)
{
for (auto [elem, i] : MakeCountedItemList(argList))
{
auto name = PtreeToString(elem);
....
UseIndexSomehow(i);
}
}
Compare con la versión original, me parece, se ha vuelto mejor: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);
}
}
Eso es todo amigos
Eso es todo por mí, gracias por su atención. Espero que hayas descubierto algo interesante o incluso útil.Según el contenido del artículo, puede parecer que estoy regañando el código de nuestro analizador y quiero decir que todo está mal allí. Esto no es verdad. Como cualquier proyecto con una historia, nuestro analizador está lleno de depósitos geológicos que han quedado de épocas pasadas. Tenga en cuenta que acabamos de excavar, eliminar artefactos de la antigua civilización de debajo del suelo y llevar a cabo la restauración para que se vean bien en el estante.PD
Habrá mucho código aquí. Dudaba si incluir la implementación de iteradores aquí o no, y al final decidí incluirlo para no dejar nada detrás de escena. Si no está interesado en leer el código, aquí le diré adiós. El resto les deseo un momento agradable con plantillas.El códigoIterador 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 con 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>;
Contenedor 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>;
