Cómo escribir estructuras de datos type-safe (genéricas) en C

• Este artículo explica un nuevo método para crear estructuras de datos type-safe (genéricas) en C
• Describe, usando como ejemplo una implementación de lista enlazada, una técnica que asocia información de tipo a la estructura de datos mediante union
• Compara las diferencias y desventajas de cada enfoque frente a los patrones genéricos tradicionales de C (macros, punteros void, Flexible Array Member)
• Permite verificación de tipos en tiempo de compilación, lo que ayuda a prevenir de antemano el uso de tipos incorrectos
• La nueva técnica ofrece una interfaz de funciones/estructuras de datos clara y consistente, como foo_list

---

Introducción

• Presenta una forma de crear estructuras de datos genéricas en C con seguridad de tipos
• Esta técnica conecta la información de tipo a la estructura de datos en tiempo de compilación usando union
• Puede aplicarse a cualquier estructura de datos, como mapas, arreglos o árboles binarios, y se explica con el ejemplo de una lista enlazada básica
• Como muchos desarrolladores creen que los genéricos no son posibles en C, la explicación avanza paso a paso de forma sencilla

Genéricos tradicionales basados en macros

• La forma tradicional de implementar estructuras de datos genéricas en C consiste en usar macros para generar nombres de estructuras, funciones y tipos
• Se amplía incluyendo varias veces el encabezado de la estructura de datos para distintos tipos

Ejemplos:

• Uso de macros (por ejemplo, CONCAT, NODE_TYPE, PREPEND_FUNC) para generar nombres de estructuras y funciones adecuados para cada tipo
• Como se genera una función y una estructura separadas para cada tipo, se obtienen definiciones distintas para tipos como int y Foo

Desventajas:

• Es difícil identificar dónde están definidas los tipos y las funciones (se generan con macros y cuesta rastrearlas)
• Es difícil aprovechar el autocompletado de código
• Se generan múltiples versiones de la misma función, lo que incrementa el tamaño del binario y el tiempo de compilación
• Los nombres de función requieren un prefijo de tipo (por ejemplo, Foo_list_prepend)

Etapa 1 de los genéricos: enfoque con punteros void

• El tipo de dato de la estructura se hace independiente del tipo usando void *
• El campo data de la lista enlazada se declara como void *
• Como no es posible verificar tipos, pueden producirse errores de tipo en tiempo de ejecución y la seguridad en compilación es baja
• Uso ineficiente de memoria y caché: el nodo y los datos se asignan por separado, lo que añade sobrecarga innecesaria y aumenta los fallos de caché

Etapa 2 de los genéricos: almacenamiento inline (Flexible Array Member)

• Se utiliza Flexible Array Member para guardar el propio dato dentro del nodo en lugar de almacenar un puntero
• Basta con una sola asignación por nodo, y en caché los datos quedan ubicados junto al puntero next
• Este enfoque requiere pasar información de tamaño y usar algo como memcpy, pero mejora el rendimiento gracias a una disposición de memoria consistente
• Con la función list_alloc_front es posible inicializar directamente la estructura sin memcpy

Etapa 3 de los genéricos: implementación de verificación de tipos

• Se declara un puntero del tipo parametrizado en el miembro payload de un union para añadir información de tipo a la estructura de datos en tiempo de compilación
• Ejemplo: #define List(type) union { ListNode *head; type *payload; }
• De esta forma se puede obtener el tipo de la lista con __typeof__(foo_list.payload)
• En la macro list_prepend, mediante un cast del tipo de función, la compilación solo es válida si se usa el tipo correcto
• Si se usa un tipo incorrecto, se produce un error en tiempo de compilación

Ejemplo de error:

• Si se agrega un int a foo_list, aparece el mensaje de error de compilación 'incompatible integer to pointer conversion'

Compatibilidad con compiladores sin typeof

• Hasta antes de C23, __typeof__ no era estándar, por lo que algunos compiladores (por ejemplo, versiones antiguas de MSVC) no lo soportan
• Se puede lograr un efecto similar con métodos alternativos, como aprovechar un miembro payload dentro de una struct

Paso de parámetros y typedef

• Incluso si tienen la misma forma, el compilador considera que distintos List(Foo) son tipos diferentes
• Al usar typedef, el paso de parámetros y la asignación funcionan de manera más fluida

Ejemplos:

• typedef List(Foo) ListFoo;
• Se puede declarar una variable ListFoo y usarla como parámetro de función

Cierre y ampliación a distintas estructuras de datos

• Esta técnica también puede usarse en estructuras de datos que requieren varios parámetros de tipo (por ejemplo, un hash map)
• Mediante union, es posible garantizar la seguridad de tipos tanto para key como para value
• Para una práctica más detallada y la implementación de las macros, consulta el gist de código relacionado

Conclusión

• El nuevo enfoque supera las desventajas de los métodos existentes (legibilidad, eficiencia de compilación y mantenibilidad) y ofrece un esquema de nombres consistente para funciones junto con seguridad de tipos
• Facilita el soporte para múltiples estructuras de datos y varios parámetros de tipo
• Gracias a la verificación de tipos en tiempo de compilación, asegura al mismo tiempo la seguridad y la eficiencia al usar estructuras de datos genéricas

Agradecimientos

• Este artículo fue completado con la retroalimentación y el apoyo de Martin Fouilleul

[click]

¿No sería más simple usar Zig?

[GN⁺]

Opiniones de Hacker News

• Señalan que, en el código del paso 2, la forma de usar uint64_t data[]; no sirve para tipos cuyos requisitos de alineación son mayores que uint64_t, y en cambio desperdicia espacio para tipos más pequeños; por ejemplo, esto es aún más problemático en un ABI ilp32 sobre una arquitectura de 64 bits. También comentan que en el código del paso 3 debería ser int main() { List(Foo) foo_list = {NULL}; así. Sin typeof no se puede devolver el valor de retorno, y en el código alternativo pueden aparecer errores relacionados con const; este problema se hace más visible por la simetría del operador ==. Si se quita payload, deja de haber información de tamaño y ya no es seguro; por ejemplo, podría parecer que agregar un int32_t a List(int64_t) está bien, pero en realidad no se puede determinar el tamaño real de int32_t. Dicen que haría falta reforzarlo para que sea más seguro. Consideran que hay dos grandes limitaciones al usar genéricos en C: primero, que el enfoque de delegación con vtable está limitado porque los structs no pueden incluir macros; segundo, que al delegar a una vtable externa hay que declarar de antemano todos los tipos que se van a usar. Añaden que la mejor forma es declarar solo funciones estáticas en un header que incluya las declaraciones typedef, pero que GCC y Clang difieren en el momento en que emiten advertencias por static indefinidos. Al final ponen como ejemplo el diseño de funciones que reciben distintos structs de buffer, subrayando que también hay que mantener todas las versiones const

  • Sobre el problema de delegar a una vtable externa, comparten que en un proyecto anterior incluso llegaron a crear un compilador para resolverlo directamente. Cuentan que, al iniciar el proyecto Apache Clownfish, empezaron parseando archivos .h, pero terminaron creando su propio formato, los headers de Clownfish (.cfh). Muestran como ejemplo código que llama al método "Clone" de un obj real, y describen la experiencia de haber tenido que generar en masa este tipo de código forzado para soportar bindings de lenguajes dinámicos que necesitaban características orientadas a objetos. Explican que el objetivo de Clownfish era ofrecer el modelo de objetos mínimo común, y que los tipos de los lenguajes enlazados también se generaban desde .cfh. Añaden que, por esta complejidad, la mayoría termina renunciando a la seguridad de tipos y usando casts a void*. https://github.com/apache/lucy-clownfish

  • Sobre int main(), recuerdan que en C int main() significa que la cantidad de argumentos es indeterminada. Para indicar que no hay argumentos debe declararse como int main(void). Enfatizan que es algo que muchos programadores de C++ suelen olvidar

  • Opinan que les gustaría que un union pudiera realmente unirse con otras estructuras, es decir, que un tipo pudiera declararse a sí mismo como parte del union de otro tipo

  • Señalan que al hacer malloc, por el padding interno el tamaño calculado puede ser menor que el real; por ejemplo, plantean el riesgo de algo como malloc(sizeof(*node) + data_size);

• Refutan el contenido del truco #0 y dicen que usaron ese truco al crear un dialecto completo de C. Comparten como ejemplo una implementación de binary heap genérico: https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h. Dicen que la sintaxis es algo pesada, pero que al final se convierte en un struct normal de C, lo que aporta grandes ventajas en optimización y previsibilidad. Consideran que en otras implementaciones son inevitables void*, el dimensionamiento de memoria en tiempo de ejecución y las definiciones por macro

  • Como autor, explica que un binary heap y una linked list tienen propósitos distintos. Un binary heap necesita leer los datos al almacenarlos, así que el enfoque es diferente, y al escribir un binary heap genérico las decisiones pueden ser otras. Aclara que eso también lo mencionó en una nota al pie del texto

  • Presentan varias razones para preferir implementaciones en headers. Al depurar, es más fácil seguir el código y aprovechar la información de tipos que con funciones hechas con macros. El compilador puede aplicar optimización monomorfizada a cada instancia, sin costo en tiempo de ejecución ni carga por tamaños variables. También se pueden poner structs genéricos en la pila. Dicen que los dos problemas mencionados por el autor se pueden esquivar: los nombres se pueden cambiar fácilmente con macros de nombres de función, y usando weak symbol el enlazador puede fusionar automáticamente definiciones duplicadas. Añaden que los contenedores genéricos de tipos puntero tienen otro problema, pero que puede resolverse con typedef y similares. Comentan que en C las estructuras de datos intrusive siguen siendo cómodas, aunque difíciles de depurar

  • La frase de que "el compilador se los come como donas" les causó mucha risa

• Al convertir tipos de función, por ejemplo, se asume que la representación interna de Foo* y void* es la misma, pero el estándar de C no lo garantiza. Cuando no hay compatibilidad de tipos ("compatible") entre ellos, ese cast puede llevar a comportamiento indefinido. También mencionan que esto podría afectar al análisis de aliasing del compilador, y adjuntan un enlace de referencia: https://news.ycombinator.com/item?id=44421185

  • Responden que eso ya se menciona en una nota al pie del artículo, y sostienen que el cast no es el núcleo de la seguridad de tipos. Recomiendan leer el texto completo

• Preguntan: "Si para usar genéricos en C hay que hacer estas maromas, ¿no sería mejor simplemente usar C++?"

  • Comparten la experiencia de que, por criterios de seguridad y otros requisitos, en muchos proyectos heredados migrar a C++ no es algo viable de inmediato. En proyectos nuevos sí establecen estándares e introducen C++, pero creen que los proyectos existentes tendrán que seguir en C por un tiempo. Opinan que la postura de "simplemente usa C++" agradecería un poco más de contexto y empatía

  • Añaden que, en la práctica, en entornos donde se usa C, cambiar a C++ puede ser aún más complejo y causar más problemas

  • En cambio, otro comenta que si con un poco de esfuerzo se puede lograr lo mismo en C, entonces no hace falta ir hasta C++

• Presentan un patrón que realmente se usa en el kernel de Linux: incluir un struct list_head con la información de la lista dentro del struct específico de cada tipo. Dejan un enlace de referencia relacionado: https://kernelnewbies.org/FAQ/LinkedLists

  • A uno le parece que los nombres de las macros LIST_HEAD_INIT e INIT_LIST_HEAD del kernel de Linux no son muy intuitivos

• Señalan que, en la sección "typeof on old compilers", (list)->payload = (item); en realidad no es un no-op, sino que sobrescribe la cabecera de la lista con item. Proponen que, si ese era el comportamiento esperado, debería envolverse en if(0)

  • También dicen que en el ejemplo cambiaron el union por un struct, y que eso igual parece un desperdicio. Opinan que sería mejor resolverlo dentro de if(0)

• Muestran que en el lenguaje D este tipo de lista genérica es mucho más simple, y recalcan la incomodidad de las macros de C con la metáfora de que el preprocesador de C se siente como martillarse las uñas, mientras que para clavar un Nail gun es mucho más rápido y limpio

  • Responden que la publicación trata sobre C y que, en algunos proyectos, simplemente hay que usar C sí o sí

• Les parece interesante la idea de aprovechar union y typeof(). En su caso, sienten que con estructuras de datos intrusive al final hace falta un wrapper envuelto en macros grandes, y se preguntan si union y typeof también permitirían una implementación así. Comparten como ejemplo código de un wrapper de hash table y un enlace a la documentación: https://github.com/FRRouting/frr/blob/master/lib/typesafe.h#L823-L971 https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html

• Comparten que personalmente ya usan esta técnica en una biblioteca experimental: https://github.com/uecker/noplate/blob/main/src/list.h

  • Preguntan por ideas sobre structs intrusive, es decir, incluir la estructura de nodo dentro de los datos para que un objeto pueda pertenecer a varios contenedores al mismo tiempo

• Parece que la idea central es asegurar la seguridad de tipos aprovechando el tipo de los punteros a función, en vez del típico tipo handle. Comentan que el estándar C23 mejoró los problemas de compatibilidad de tipos, y comparten el documento del estándar y el estado de soporte en GCC/Clang recientes: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3037.pdf

  • Como autor, enfatiza que la idea clave es usar un union para vincular la información de tipo al tipo de datos genérico; no se trata solo de casts de funciones, y menciona que también discutió varias alternativas en las notas al pie y en "typeof on old compilers" con bastante detalle