Tagged unions in C: representing an AST without malloc hell

The AST is the central data structure of any interpreter. Getting it right matters — a design that is awkward to work with makes every subsequent feature harder. There are two common approaches in C, and first uses the less common one.

The pointer approach

The standard approach is a base Node struct with a type tag and a void* data pointer, with each variant separately allocated. Every node is two allocations, every access requires a cast, and freeing the tree means knowing the variant type to free the right data pointer. It works, but the overhead adds up quickly when you are adding new node types frequently.

The tagged union approach

first uses a single AST struct containing a tag field and an anonymous data union of all variant structs, one member per Kind. One allocation, no casts, no separate data pointer to manage:

typedef struct AST {
  Kind tag;
  union {
    struct AST_PROGRAM              AST_PROGRAM;
    struct AST_EXPRESSION_LIST      AST_EXPRESSION_LIST;
    struct AST_BINARY_EXPRESSION    AST_BINARY_EXPRESSION;
    struct AST_IDENTIFIER           AST_IDENTIFIER;
    struct AST_BOOLEAN              AST_BOOLEAN;
    struct AST_NUMBER               AST_NUMBER;
    struct AST_STRING               AST_STRING;
    struct AST_ASSIGNMENT           AST_ASSIGNMENT;
    struct AST_VARIABLE_DECLARATION AST_VARIABLE_DECLARATION;
    struct AST_UNARY                AST_UNARY;
    struct AST_CONDITIONAL          AST_CONDITIONAL;
    struct AST_BLOCK                AST_BLOCK;
  } data;
} AST;

Every node is the same size in memory — the size of the largest variant. The tag field tells the interpreter which data member is valid. Adding a new node type is one new struct in the union and one new case in the interpreter switch.

The compiler as safety net

With -Wswitch enabled (it is, via -Wextra), the compiler warns if any switch (ast->tag) does not handle every enum value. Adding a new Kind causes compile-time warnings everywhere you forgot to update. The compiler does the audit.

The cost

Every node occupies the same memory as the largest variant — today, that's AST_CONDITIONAL, which carries a growable array of when-arm pointers for a when expression. A number literal still takes that much space. For an interpreter handling millions of nodes per second in a hot loop, this might matter. For first today, it does not — and the simplicity of one allocation per node is worth far more than the wasted bytes.

One thing this design gets almost for free: growth. Since the union was first written, first added AST_UNARY, AST_BOOLEAN, AST_CONDITIONAL, and AST_BLOCK — four new node kinds, each just a new struct AST_* and a new enum value, with the compiler pointing at every switch that needed a new case.