kcc — a C compiler, written as literature.

\chapter{Type System}
\label{ch:types}

Every C expression has a type, and the compiler must track these types to enforce the language's constraints and to determine the size, alignment, and representation of every object.  This chapter defines the type descriptor---a 48-byte arena-allocated record that encodes kind, size, alignment, and qualifiers---and builds the infrastructure around it.  We begin with the descriptor layout and the pre-allocated singletons for built-in types, then provide constructors for derived types (pointers, arrays, functions, structures, unions, and enumerations), predicate functions for querying type properties, a specifier resolver that converts the parser's bitmask into a canonical type, and a diagnostic dump for debugging.

\section{Type Descriptor Layout}

A type descriptor occupies 48 bytes with the following layout:

\begin{center}
\begin{tabular}{lll}
Offset & Field & Description \\
\hline
0  & TY\_KIND  & type kind constant \\
8  & TY\_SIZE  & size in bytes \\
16 & TY\_ALIGN & alignment in bytes \\
24 & TY\_QUALS & const=1, volatile=2, restrict=4, \_Atomic=8 \\
32 & TY\_F0    & kind-specific field 0 \\
40 & TY\_F1    & kind-specific field 1 \\
\end{tabular}
\end{center}

@d Types: constants @{
// -- Type descriptor layout ---
.equ TY_KIND,       0
.equ TY_SIZE,       8
.equ TY_ALIGN,     16
.equ TY_QUALS,     24
.equ TY_F0,        32
.equ TY_F1,        40
.equ TY_DESC_SIZE, 48

// -- Type kind constants ---
.equ TY_VOID,       1
.equ TY_BOOL,       2
.equ TY_CHAR,       3    // F0=signed(1)/unsigned(0)
.equ TY_SHORT,      4    // F0=signed(1)/unsigned(0)
.equ TY_INT,        5    // F0=signed(1)/unsigned(0)
.equ TY_LONG,       6    // F0=signed(1)/unsigned(0)
.equ TY_LLONG,      7    // F0=signed(1)/unsigned(0)
.equ TY_FLOAT,      8
.equ TY_DOUBLE,     9
.equ TY_LDOUBLE,   10
.equ TY_PTR,       11    // F0=pointee type descriptor
.equ TY_ARRAY,     12    // F0=element type, F1=length
.equ TY_FUNC,      13    // F0=return type, F1=param vec*
.equ TY_STRUCT,    14    // F0=struct_decl AST, F1=member vec*
.equ TY_UNION,     15    // F0=union_decl AST, F1=member vec*
.equ TY_ENUM,      16    // F0=enum_decl AST
.equ TY_INT128,    17    // __int128, F0=signed(1)/unsigned(0); size 16, align 16

// -- Specifier bitmask constants (from parser) ---
.equ SPEC_VOID,       (1 << 0)
.equ SPEC_CHAR,       (1 << 1)
.equ SPEC_SHORT,      (1 << 2)
.equ SPEC_INT,        (1 << 3)
.equ SPEC_LONG,       (1 << 4)
.equ SPEC_LLONG,      (1 << 5)
.equ SPEC_FLOAT,      (1 << 6)
.equ SPEC_DOUBLE,     (1 << 7)
.equ SPEC_SIGNED,     (1 << 8)
.equ SPEC_UNSIGNED,   (1 << 9)
.equ SPEC_BOOL,       (1 << 10)
.equ SPEC_COMPLEX,    (1 << 11)
.equ SPEC_INT128,     (1 << 12)
@}

\section{Type Initialization}

Pre-allocate singleton descriptors for all basic types.  Alongside the standard
integer widths, two singletons cover the GNU 128-bit integer \texttt{\_\_int128}
(kind \texttt{TY\_INT128}, signed and unsigned): each carries size and
alignment~16, so it lays out correctly wherever a 16-byte object is expected---%
notably inside the \texttt{union \_\_u128\_halves} the Linux kernel's
\texttt{cmpxchg16b} code builds.  Only its \emph{arithmetic} is deferred
(Appendix~\ref{ch:limitations}); the descriptor itself is a first-class basic
type.

@d Types: init @{
// -- kcc_types_init ---
// void kcc_types_init(void)
// Pre-allocates singleton type descriptors for all basic types.
.text
.globl _kcc_types_init
.p2align 2
_kcc_types_init:
    stp x29, x30, [sp, #-32]!
    mov x29, sp
    stp x19, x20, [sp, #16]

    // void
    mov x0, #TY_DESC_SIZE
    bl _kcc_arena_alloc
    mov x19, x0
    mov x1, #TY_VOID
    str x1, [x19, #TY_KIND]
    str xzr, [x19, #TY_SIZE]       // void has no size
    str xzr, [x19, #TY_ALIGN]
    str xzr, [x19, #TY_QUALS]
    str xzr, [x19, #TY_F0]
    str xzr, [x19, #TY_F1]
    adrp x1, _kcc_type_void@@PAGE
    add  x1, x1, _kcc_type_void@@PAGEOFF
    str x19, [x1]

    // _Bool
    mov x0, #TY_DESC_SIZE
    bl _kcc_arena_alloc
    mov x19, x0
    mov x1, #TY_BOOL
    str x1, [x19, #TY_KIND]
    mov x1, #1
    str x1, [x19, #TY_SIZE]
    str x1, [x19, #TY_ALIGN]
    str xzr, [x19, #TY_QUALS]
    str xzr, [x19, #TY_F0]
    str xzr, [x19, #TY_F1]
    adrp x1, _kcc_type_bool@@PAGE
    add  x1, x1, _kcc_type_bool@@PAGEOFF
    str x19, [x1]
@| _kcc_types_init
@}

\paragraph{Character and Integer Type Singletons}

The next block allocates singletons for every standard integer type, from
\texttt{char} through \texttt{long long}, each in both signed and unsigned
variants.  The C17 standard treats plain \texttt{char}, \texttt{signed char},
and \texttt{unsigned char} as three distinct types (\stdref{6.2.5p15}); our
implementation maps plain \texttt{char} to \texttt{signed char}, following the
default sign convention on Apple ARM64 targets.  Each descriptor stores its
signedness in \texttt{TY\_F0} (1 for signed, 0 for unsigned) so that later
stages can select the correct conversion and promotion rules.