Como escrever estruturas de dados genéricas com segurança de tipos em C

• Mesmo em C, é possível criar estruturas de dados genéricas com segurança de tipos combinando macros, void *, flexible array member e union, e o exemplo mostra uma implementação passo a passo com lista encadeada
• Incluir o cabeçalho específico por tipo várias vezes é seguro, mas o código gerado por macro pode dificultar rastrear definições e autocompletar, além de aumentar o tamanho do binário e o tempo de build
• Listas baseadas em void * são versáteis, mas não impedem erros de tipo e, se nó e dado forem alocados separadamente, podem causar 2 alocações por nó e cache misses
• Ao armazenar os dados dentro do nó com flexible array member e envolver List(type) com union, dá para anexar informação de tipo em tempo de compilação sem custo em tempo de execução
• A macro list_prepend usa o operador ternário para fazer o valor passado bater com o tipo de payload e induzir erro de compilação, e o tipo do ponteiro de retorno pode usar __typeof__()

---

Ponto de partida da implementação genérica em C

• O objetivo é declarar listas específicas por tipo em C, como List(int) e List(Foo), e fazer com que inserir um tipo errado não compile
• No exemplo, é possível inserir valores Foo em List(Foo), mas código como list_prepend(&foo_list, 7) não compila por usar um tipo diferente
• Dentro de list_for(item, &foo_list), item pode ser tratado como do tipo Foo *

Nível 0: abordagem de cabeçalho genérico

• Uma forma é escrever a estrutura de dados no cabeçalho e executar vários #include, trocando a macro de tipo T
• list.h gera tipos e funções como FooListNode e Foo_list_prepend com base em macros usando T
• Essa abordagem é genérica e type-safe, mas a usabilidade fica mais áspera
  • Tipos e funções são compostos por macros, então é difícil encontrar onde foram definidos
  • O autocompletar pode não funcionar bem
  • A mesma função é copiada para cada tipo, aumentando o tamanho do binário e o tempo de build
  • Em vez de um único list_prepend(), é preciso usar funções com prefixo de tipo, como Foo_list_prepend() e int_list_prepend()
• Para funções genéricas que realmente precisam gerar código específico por tipo, essa abordagem pode ser mais adequada

Nível 1: lista baseada em void *

• Se ListNode tiver void *data, ele pode armazenar dados de vários tipos
• list_prepend(ListNode **head, void *data) apenas guarda o ponteiro do dado, então a implementação é simples
• O problema é que essa estrutura não é type-safe
• Se o nó e os dados forem alocados separadamente, o custo de memória e desempenho também aumenta
  • São necessárias duas alocações por nó
  • O próprio ponteiro data consome memória extra
  • Ao percorrer a lista, podem ocorrer cache misses tanto ao acessar o próximo nó quanto ao acessar os dados
• O código de exemplo usa malloc por familiaridade, mas na prática é recomendável usar Arena, com materiais relacionados em vídeo e artigo

Nível 2: armazenar os dados dentro do nó

• Em vez de void *data, dá para usar Flexible Array Member para guardar os dados dentro do próprio nó
• struct ListNode passa a ter ListNode *next e char data[], e na alocação reserva-se tudo de uma vez com sizeof(* node) + data_size
• list_prepend recebe os dados e o tamanho, e copia para node->data com memcpy
• Assim, next e os dados reais ficam próximos na memória, reduzindo os problemas de alocação e cache da abordagem com void *
• Em troca, o chamador precisa passar data_size
• Se quiser evitar memcpy, list_alloc_front pode retornar um ponteiro para a área de dados do nó, e o chamador inicializa essa memória diretamente
• Questões de alinhamento, padding e cálculo de tamanho do membro data são um tema à parte e não são tratadas em detalhe no exemplo

Nível 3: anexar informação de tipo com union

• A técnica principal é definir List(type) como uma union, reunindo o ponteiro real para a cabeça da lista e um ponteiro usado para informação de tipo

#define List(type) union { \
    ListNode *head; \
    type *payload; \
}

• payload não é usado em tempo de execução; ele fornece informação de tipo em tempo de compilação
• Como é uma union, payload não consome memória extra
• Assim, é possível criar listas por tipo como List(Foo) foo_list e List(int) int_list

Verificando tipos com o operador ternário

• A macro list_prepend chama a função interna _list_prepend usando o operador ternário para alinhar os tipos de item e (list)->payload

#define list_prepend(list, item) \
    _list_prepend(&((list)->head), \
                  (1 ? (item) : (list)->payload), \
                  sizeof(*(list)->payload))

• Se os dois tipos candidatos do operador ternário não forem compatíveis, o compilador gera erro de incompatibilidade de tipos
• Por exemplo, se Bar * for passado para List(Foo), o Clang aponta incompatibilidade entre os tipos de ponteiro Foo * e Bar *
• A mesma macro também passa automaticamente o tamanho do tipo armazenado com sizeof(*(list)->payload)
• O trabalho real fica com uma função interna genérica como _list_prepend(ListNode **head, void *data, size_t data_size)

Usando __typeof__() no tipo de retorno

• Quando uma função genérica precisa retornar um ponteiro para os dados internos, __typeof__() pode converter o retorno void * para o tipo de payload

#define list_alloc_front(list) \
    (__typeof__((list)->payload))_list_alloc_front(&(list)->head, sizeof(*(list)->payload))

• __typeof__() é suportado por Clang, GCC e MSVC 19.39 ou superior
• Antes de entrar no padrão C23, __typeof__() era uma extensão opcional
• Em compiladores sem __typeof__(), como versões anteriores ao MSVC 19.39, ainda é possível usar a checagem de tipo baseada no operador ternário
• Também dá para obter retorno type-safe com um esquema de alocação via payload, mas os detalhes da implementação foram omitidos

Cuidados com a abordagem antiga e com a definição da linguagem

• A abordagem anterior chamava _list_prepend convertendo-o para um tipo de ponteiro de função que incluía __typeof__((list)->payload)
• Chamar uma função por meio de um ponteiro de função com cast é tecnicamente comportamento indefinido, embora seja tratado como algo que na prática não causa problemas em compiladores e plataformas modernos
• A abordagem atual, em vez disso, induz o erro por meio da compatibilidade de tipos no operador ternário, sem cast de ponteiro de função

O problema ao passar List(Foo) como argumento

• O compilador C pode não considerar duas definições de List(Foo) com a mesma estrutura como sendo do mesmo tipo

List(Foo) a;
List(Foo) b = a; // error

• Mesmo definindo um parâmetro como void my_function(List(Foo) list) e chamando my_function(a), pode surgir erro de tipos incompatíveis
• A solução é dar um nome ao tipo com typedef

typedef List(Foo) ListFoo;

ListFoo a;
ListFoo b = a; // ok

void my_function(ListFoo list);
my_function(a); // ok

• Em variáveis locais, ainda é possível continuar usando a forma List(Foo) local_foo_list
• No GCC 15 e no Clang do fim de 2025, uma mudança de regra deve fazer com que tipos estruturalmente idênticos com o mesmo nome de tag passem a ser tratados como o mesmo tipo

Aplicável também a outras estruturas de dados

• A mesma técnica pode ser aplicada não só a listas, mas também a mapas, arrays, árvores binárias e várias outras estruturas de dados
• Ela também pode ser estendida para estruturas que exigem vários tipos relacionados
• Por exemplo, um hash map pode reunir a estrutura interna, o tipo da chave e o tipo do valor dentro da mesma union

#define Map(key_type, value_type) union { \
    MapInternal map; \
    key_type *key; \
    value_type *value; \
}

• stb_ds.h também é um exemplo de estrutura de dados genérica com segurança de tipos, mas como arrays e mapas usam arrays em C, alguns erros de tipo só são detectados no momento da atribuição ao array, e não na passagem do valor

[click]

Fico com a dúvida se não seria mais simples simplesmente usar Zig.

[GN⁺]

Opiniões no Hacker News

• O código de nível 2, uint64_t data[];, está errado para tipos cujo requisito de alinhamento é maior que o de uint64_t, e desperdiça espaço para tipos menores. Um exemplo disso é uma ABI ilp32 em uma arquitetura de 64 bits
  O código de nível 3 deveria ser int main() { List(Foo) foo_list = {NULL};
  Como não há typeof, se você contornar isso não dá para retornar nada, e como == é simétrico, esse contorno também permite erros relacionados a const
  Também não é possível omitir payload com segurança. Ele é necessário para saber o tamanho correto. O caso de adicionar um int32_t a List(int64_t) deveria ser possível, mas não dá para saber o sizeof desse int32_t. Ainda faltam várias partes para esse código funcionar corretamente
  Os genéricos em C hoje têm duas grandes limitações. Primeiro, a abordagem de delegar a uma vtable tem funcionalidade limitada, porque uma struct não pode conter macros, apenas funções. Segundo, para evitar overhead, é preciso delegar a uma vtable externa; para isso, todos os tipos que usarão a vtable precisam ser declarados antecipadamente
  O melhor que encontrei até agora foi declarar funções static, sem defini-las, em um header de declaração antecipada que declara os typedefs. Na prática, quando o header de um tipo específico não é incluído em alguma unidade de tradução, GCC e Clang emitem o aviso de “undefined static” em etapas diferentes
  Por exemplo, pense em uma função que aceite struct SizedBuffer {void *p; size_t len;}; ou struct BoundedBuffer {void *begin; void *end;};, vindas de headers diferentes, além das versões const de cada uma

  • Por causa do problema de precisar declarar antecipadamente todos os tipos que usarão a vtable para delegar a uma vtable externa, no projeto Apache Clownfish de que participei no passado acabamos até criando um compilador para isso
    No começo fazíamos o parsing dos arquivos .h, mas no fim achamos melhor criar uma pequena linguagem de headers chamada .cfh, “Clownfish Header”
    Gerávamos código como este para chamar a versão CharBuf do método Clone definido na classe pai Obj

    typedef cfish_CharBuf*
(*CFISH_CharBuf_Clone_t)(cfish_CharBuf* self);

    extern uint32_t CFISH_CharBuf_Clone_OFFSET;

    static inline cfish_CharBuf*
CFISH_CharBuf_Clone(cfish_CharBuf* self) {
const CFISH_CharBuf_Clone_t method
= (CFISH_CharBuf_Clone_t)cfish_obj_method(
self,
CFISH_CharBuf_Clone_OFFSET
);
return method(self);
}

    O uso era assim

    cfish_CharBuf *charbuf = cfish_CharBuf_new();
cfish_CharBuf *clone = CFISH_CharBuf_Clone(charbuf);

    O objetivo do Clownfish era fornecer um modelo de objetos de mínimo denominador comum para bindings de várias linguagens dinâmicas, e os arquivos .cfh também eram usados para derivar tipos para as linguagens de binding. Ainda assim, a quantidade de código boilerplate gerada para evitar o problema apontado era realmente absurda
    Por isso, quase todo mundo acaba abrindo mão da segurança de tipos e simplesmente usa casts para void* no alvo da chamada
    https://github.com/apache/lucy-clownfish

  • Em C, int main() não significa que não recebe argumentos; significa que recebe um número desconhecido de argumentos. Para dizer que não recebe argumentos, é preciso escrever int main(void). É algo que pessoas vindas de C++ frequentemente esquecem

  • Seria bom se union pudesse ser estendida de forma aditiva. Um tipo poderia se declarar como parte da mesma union que outro tipo, sem que todos os tipos possíveis precisassem ser previamente declarados em um único lugar

  • malloc(sizeof(*node) + data_size); também pode ser problemático por causa de padding. O tamanho calculado pode acabar pequeno demais

• Discordo
  Já criei um dialeto inteiro de C usando o trick#0 mencionado no texto. Por exemplo, um heap binário genérico está em https://github.com/gritzko/librdx/blob/master/abc/HEAPx.h
  A sintaxe é meio pesada, mas há uma grande vantagem: no fim, o que se obtém são structs C comuns, simples, previsíveis e fáceis de otimizar. É o tipo de código que o compilador engole como um donut
  Outros métodos acabam exigindo void* e cálculo de tamanho de memória em runtime, e de qualquer forma também é preciso definir macros

  • Sou o autor. Heap binário e lista ligada têm casos de uso diferentes. Um heap binário precisa ler os dados inseridos para armazená-los corretamente, mas uma lista ligada não
    Se eu estivesse usando um heap binário genérico, talvez tivesse ponderado as opções de outro jeito. Também mencionei isso em uma nota de rodapé
  • Existem, de fato, vários motivos para preferir implementações em header. Ao contrário de funções em macro, código em header pode ser seguido no debugger, e a informação de tipo que o debugger consegue ver também é melhor, o que melhora o debugging
    Como cada instância é monomorfizada, há mais margem para otimizações do compilador, e não é preciso pagar custo de runtime por causa de tamanho variável. Por ter tamanho fixo, também é possível colocar a struct genérica na stack
    Pelo menos dois dos problemas mencionados pelo autor podem ser contornados. Nomes podem ser transformados de Bar_func(args…) para func(Bar)(args…) com uma macro simples de name mangling. O inchaço do binário pode ser reduzido em parte usando símbolos fracos, para que o linker elimine duplicatas de funções compartilhadas entre unidades de tradução
    Containers genéricos de tipos ponteiro têm outro problema, mas ele pode ser contornado com typedefs ou aliases de tipo
    Em C, estruturas de dados intrusivas ainda são mais convenientes, mas lidar com elas no debugger é doloroso

• O cast de tipo de função presume que o tipo de ponteiro para o item, por exemplo Foo*, tenha a mesma representação que void*, mas o padrão C não garante isso. Nos termos do padrão, os dois tipos não são “compatíveis”
  Portanto, chamar uma função com o tipo convertido é comportamento indefinido. Mesmo que a representação dos ponteiros seja por acaso igual, isso também afeta a análise de aliases do compilador. Sobre isso, [0] também vale a leitura
  Fazer cast de funções para tipos de argumentos diferentes parece ser o núcleo da segurança de tipos nas chamadas genéricas, mas não sei se esse é um problema corrigível
  https://news.ycombinator.com/item?id=44421185

  • Isso foi tratado nas notas de rodapé. O cast não é o núcleo da segurança de tipos. Basta ler o texto inteiro

• Se você quer “C com generics”, não seria melhor simplesmente usar C++, em vez de contornar tanta coisa assim?

  • Porque trabalho em um projeto legado preso a regulamentações de segurança e outras garantias de qualidade. Não dá simplesmente para lançar uma solução portada para C++ nem na próxima release, nem na décima. Então talvez seja preciso fazer as coisas funcionarem de algum modo até que isso se torne possível
    Dito isso, em projetos novos podemos definir padrões e expectativas para usar C++, e de fato fazemos isso, mirando um std específico
    Vejo esse tipo de atitude com bastante frequência no Hacker News, e ela soa meio como “melhore suas habilidades”. Acho que há muito mais contexto necessário aqui
  • Porque, em muitos casos de uso em que C é usado, migrar para C++ exigiria ainda mais contornos
  • Algumas pessoas detestam C++ até a alma, por isso esse tipo de trabalho continua aparecendo
    Foi realmente decepcionante ver a Microsoft recuar da posição de que “C++ é o futuro” mesmo depois de sua nova simpatia por Linux e por software livre e de código aberto
    https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
    https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
    Hoje em dia isso não é tão importante, já que políticas novas sobre C e C++ surgiram na Microsoft por causa de normas governamentais e leis cibernéticas
    https://azure.microsoft.com/en-us/blog/microsoft-azure-secur...
    https://blogs.windows.com/windowsexperience/2024/11/19/windo...
  • A resposta verdadeira é que este caminho é mais divertido
  • Se dá para obter o mesmo resultado em C com alguns contornos, por que usar C++?

• Truque bacana. Já estou usando também na minha biblioteca experimental https://github.com/uecker/noplate/blob/main/src/list.h

  • Se há alguém que saberia disso, imagino que seja você: vê alguma forma de aplicar essa abordagem a estruturas de dados intrusivas?
    É a abordagem de colocar a struct do nó dentro dos dados, em vez de colocar os dados dentro do nó como agora, e, como bônus, permitir que um objeto esteja em vários contêineres

• É preciso ter cuidado com a parte que diz que “tipos estruturalmente idênticos passam a ser considerados o mesmo tipo graças à mudança de regras no GCC 15 e no Clang no fim de 2025”
  Nas novas regras, só unions com tag são consideradas o mesmo tipo, e elas precisam ter a mesma estrutura e a mesma tag
  O macro List(T) teria de ser alterado para gerar uma tag diferente para cada T diferente. Para tipos simples de uma só palavra isso é fácil com ##, mas fica impossível assim que aparece algo um pouco mais complexo, como ponteiro para char, isto é, string
  Claro, dá para obrigar que todos os tipos sejam definidos com typedef antes de serem usados em List, mas isso reduz bastante a generalidade

  typedef char *str;
List(str) my_list_of_str;
List(str) tokenize(str input) {...}

  • Não entendo a afirmação de que “só unions com tag são consideradas o mesmo tipo”. Tagged union não é apenas um padrão de projeto?

• Acho que o termo comum para um “membro que não faz nada e apenas carrega um tipo” é type witness. Mas há bem menos literatura sobre type witness do que eu esperava

  • Quando há uma variável de tipo que nunca é usada como tipo de uma variável real, existe um termo parecido: phantom type
    Vi isso principalmente em Haskell, e também já usei em Scala para simular uma hierarquia de tipos que não existe de verdade no sistema de tipos
    De certa forma, esse truque com union também se parece com phantom type, já que o tipo auxiliar nunca é realmente usado

• Há também a abordagem usada no kernel Linux: embutir o struct list_head, que contém as informações da lista, dentro da struct específica de cada tipo
  https://kernelnewbies.org/FAQ/LinkedLists

  • Os nomes LIST_HEAD_INIT e INIT_LIST_HEAD confundem

• Se for para fazer isso, eu preferiria usar templates de C++ diretamente

• Em D, dá para fazer assim

  struct ListNode(T) {
ListNode* next;
T data;
}

  T!int node;

Por que sofrer com o pré-processador de C? Usar macros do pré-processador é como usar um martelo em vez de uma pistola de pregos em carpintaria de acabamento. A pistola de pregos é 10 vezes mais rápida, acerta o prego com precisão todas as vezes e não deixa marcas em forma de meia-lua na peça.

• Este texto é sobre C. Em alguns projetos, é obrigatório usar C.
• Não é preciso usar só o martelo; dá para usar um punção junto. Basta cravar o prego de acabamento com o martelo até deixar cerca de 1/8 de polegada para fora e depois usar o punção para terminar de afundá-lo.