Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / sema / types.lucb

#==============================================================================================
#
#   types - Interned types and their target layout
#
#   DESCRIPTION:
#       Every type the checker names lives once in a `Table` and is referred to by its
#       index, so two equal types have one id and equality is an integer compare. The
#       scalars are pre-seeded at fixed ids. Nominal types (structs, enums, unions,
#       interfaces) are identified by their declaration node; structural ones (pointers,
#       spans, arrays, tuples, optionals, results, functions, atomics) by their parts.
#       Layout answers `sizeof`, `alignof`, and `offsetof` for the 64-bit host target
#       (base.md §5.11); pointers to unsized things carry a length word (§5.4, §5.5).
#
#==============================================================================================

import front.ast
import io
import memory
import support.list
import support.literals

## The form of a type: which of the language's type constructors it is.
pub enum Kind as u8:
    error_ = 1
    never_ = 2
    unit_ = 3
    bool_ = 4
    i8_ = 5
    i16_ = 6
    i32_ = 7
    i64_ = 8
    isize_ = 9
    u8_ = 10
    u16_ = 11
    u32_ = 12
    u64_ = 13
    usize_ = 14
    f32_ = 15
    f64_ = 16
    char_ = 17
    str_ = 18
    cstr_ = 19
    fmt_ = 20
    void_ = 21
    untyped_int = 22
    untyped_float = 23
    error_code = 24
    error_value = 25
    ## the half-precision float, seeded after the first slice's scalars
    f16_ = 26
    pointer = 30
    span = 31
    array = 32
    tuple = 33
    optional = 34
    fallible = 35
    func_ = 36
    atomic = 37
    struct_ = 40
    enum_ = 41
    union_ = 42
    interface_ = 43
    param = 44
    module = 45
    type_name = 46

# mark: Fixed ids ==============================================================================

## Ids of the pre-seeded types, in the order `Table.create` seeds them.
## How many type parameters a declaration may have: the checker refuses more, so the
## fixed rooms an instance's arguments are resolved into are never short.
pub let max_type_arguments: usize = 16
## The id of the absent type (no element, result, or payload).
pub let none_id: u32 = 0
## The id of the error placeholder, used after a type error.
pub let error_id: u32 = 1
## The id of `never`.
pub let never_id: u32 = 2
## The id of `unit`.
pub let unit_id: u32 = 3
## The id of `bool`.
pub let bool_id: u32 = 4
## The id of `i8`.
pub let i8_id: u32 = 5
## The id of `i16`.
pub let i16_id: u32 = 6
## The id of `i32`.
pub let i32_id: u32 = 7
## The id of `i64`.
pub let i64_id: u32 = 8
## The id of `isize`.
pub let isize_id: u32 = 9
## The id of `u8`.
pub let u8_id: u32 = 10
## The id of `u16`.
pub let u16_id: u32 = 11
## The id of `u32`.
pub let u32_id: u32 = 12
## The id of `u64`.
pub let u64_id: u32 = 13
## The id of `usize`.
pub let usize_id: u32 = 14
## The id of `f32`.
pub let f32_id: u32 = 15
## The id of `f64`.
pub let f64_id: u32 = 16
## The id of `char`.
pub let char_id: u32 = 17
## The id of `str`.
pub let str_id: u32 = 18
## The id of `c.str`.
pub let cstr_id: u32 = 19
## The id of the format-string type.
pub let fmt_id: u32 = 20
## The id of `void`.
pub let void_id: u32 = 21
## The id of an untyped integer literal.
pub let untyped_int_id: u32 = 22
## The id of an untyped float literal.
pub let untyped_float_id: u32 = 23
## The id of `ErrorCode`.
pub let error_code_id: u32 = 24
## The id of the `Error` value (a code and a message).
pub let error_value_id: u32 = 25
## The `c` module's distinct types (base.md §5.2): integers of a target-dependent width,
## and the opaque `va_list`, each its own type although its kind is a Base one.
pub let c_char_id: u32 = 26
## The id of `c.long`.
pub let c_long_id: u32 = 27
## The id of `c.ulong`.
pub let c_ulong_id: u32 = 28
## The id of `c.wchar`.
pub let c_wchar_id: u32 = 29
## The id of `c.va_list`.
pub let c_va_list_id: u32 = 30
## The id of `f16`.
pub let f16_id: u32 = 31
let seeded: u32 = 32

## Whether `id` is one of the `c` module's distinct types, which convert only explicitly.
pub func is_distinct_c(id: u32) -> bool:
    return id >= c_char_id and id <= c_va_list_id

## Every bucket empty.
func zero_index(index: u32[]):
    var i: usize = 0
    while i < index.length:
        index[i] = 0
        i += 1

## A hash of what `same_type` compares: the structure, and the name where it counts.
func structure_hash(t: Type) -> u64:
    var h = mix(0x9e3779b97f4a7c15, (u64)t.kind)
    h = mix(h, (u64)t.elem)
    h = mix(h, t.length)
    h = mix(h, (1 if t.is_const else 0) | (2 if t.is_volatile else 0) | (4 if t.variadic else 0))
    if let d = t.decl:
        h = mix(h, (u64)(usize)d)
    for arg in t.args:
        h = mix(h, (u64)arg)
    if t.decl == none or t.kind == Kind.param:
        for byte in t.name.bytes:
            h = mix(h, (u64)byte)
    return h

func mix(h: u64, x: u64) -> u64:
    var r = h ^ x
    r = r *% 11400714819323198485
    return r ^ (r >> 29)

# mark: The type record ========================================================================
pub struct Type:
    ## The type's form.
    pub var kind: Kind
    ## The pointee, element, payload, or result, by id; `none_id` when absent.
    pub var elem: u32
    ## Tuple members or function parameters, by id.
    pub var args: u32[]
    ## Array length.
    pub var length: u64
    ## Whether the type is `const`.
    pub var is_const: bool
    ## Whether the type is `volatile`.
    pub var is_volatile: bool
    ## Variadic function type (C only).
    pub var variadic: bool
    ## Nominal types: the declaration; generic instances: the same declaration
    ## plus the type arguments in `args`.
    pub var decl: ast.Node*?
    ## A nominal type's name, else empty.
    pub var name: str

# mark: The table ==============================================================================
pub struct Table:
    var types: list.List[Type]
    ## The target's word: the size and alignment of a pointer, and so of `usize`, `isize`,
    ## a text or span (two words), and an error value (three), in bytes (§19.5).
    pub var word: u64
    ## An open-addressing index from a type's structure to its id + 1 (0 marks an empty
    ## bucket), so `intern` is a lookup rather than a scan over every type so far.
    var index: u32[]
    ## The allocator the index was made with, which its growth goes on using: the lowerer
    ## makes types while the heap, not the checker's arena, is the current allocator.
    var allocator: memory.Allocator

    ## An empty table holding only the built-in scalar types.
    pub static func create() -> Table!:
        var t = Table(types = try list.List[Type].create(256), word = 8, index = try new u32[1024] ---, allocator = memory.allocator)
        zero_index(t.index)
        # id 0 is "no type"; the scalars follow in Kind order
        let seeds: Kind[32] = [Kind.error_, Kind.error_, Kind.never_, Kind.unit_, Kind.bool_, Kind.i8_, Kind.i16_, Kind.i32_, Kind.i64_, Kind.isize_, Kind.u8_, Kind.u16_, Kind.u32_, Kind.u64_, Kind.usize_, Kind.f32_, Kind.f64_, Kind.char_, Kind.str_, Kind.cstr_, Kind.fmt_, Kind.void_, Kind.untyped_int, Kind.untyped_float, Kind.error_code, Kind.error_value, Kind.i8_, Kind.i64_, Kind.u64_, Kind.i32_, Kind.pointer, Kind.f16_]
        let names: str[32] = ["", "<error>", "never", "unit", "bool", "i8", "i16", "i32", "i64", "isize", "u8", "u16", "u32", "u64", "usize", "f32", "f64", "char", "str", "c.str", "fmt", "void", "<integer>", "<float>", "ErrorCode", "Error", "c.char", "c.long", "c.ulong", "c.wchar", "c.va_list", "f16"]
        var i: usize = 0
        while i < (usize)seeded:
            # `c.va_list` is a pointer-sized opaque value on the supported targets
            let elem = void_id if i == (usize)c_va_list_id else 0
            try t.types.push(Type(kind = seeds[i], elem = elem, args = try no_args(), length = 0, is_const = false, is_volatile = false, variadic = false, decl = none, name = names[i]))
            i += 1
        i = 0
        while i < t.types.count:
            t.index_add(u32(i))
            i += 1
        return t

    ## A copy in the current allocator, which its growth goes on using: a type interned in
    ## one is not in the other, and the types both hold keep their ids. The records' argument
    ## lists are shared; no type changes once interned.
    pub func copied() -> Table!:
        let index = try new u32[self.index.length] ---
        memory.copy(index, self.index, index.length)
        return Table(types = try self.types.copied(), word = self.word, index = index, allocator = memory.allocator)

    ## C uses LLP64 on Windows: long is 32 bits and wchar_t is unsigned 16 bits (§5.2).
    ## Configure before interning any target-dependent compound types.
    pub func configure_c(windows: bool):
        var signed_long = self.types.get((usize)c_long_id)
        signed_long.kind = Kind.i32_ if windows else Kind.i64_
        self.types.set((usize)c_long_id, signed_long)
        var unsigned_long = self.types.get((usize)c_ulong_id)
        unsigned_long.kind = Kind.u32_ if windows else Kind.u64_
        self.types.set((usize)c_ulong_id, unsigned_long)
        var wide = self.types.get((usize)c_wchar_id)
        wide.kind = Kind.u16_ if windows else Kind.i32_
        self.types.set((usize)c_wchar_id, wide)
        zero_index(self.index)
        for i in 0..<self.types.count:
            self.index_add((u32)i)

    ## The `Type` record for `id`.
    pub func get(id: u32) -> Type:
        return self.types.get((usize)id)

    ## The form of type `id`.
    pub func kind(id: u32) -> Kind:
        return self.types.get((usize)id).kind

    ## How many types the table holds.
    pub func count() -> u32:
        return u32(self.types.count)

    ## The id of a type equal to `t`, adding it when new. Nominal types with a
    ## declaration compare by declaration and type arguments.
    pub func intern(t: Type) -> u32!:
        let mask = self.index.length - 1
        var at = (usize)structure_hash(t) & mask
        while self.index[at] != 0:
            let id = self.index[at] - 1
            if id >= seeded and same_type(self.types.get((usize)id), t):
                return id
            at = (at + 1) & mask
        let id = u32(self.types.count)
        try self.types.push(t)
        if self.types.count * 2 > self.index.length:
            try self.grow_index()
        else:
            self.index_add(id)
        return id

    ## Put type `id` into the first empty bucket on its hash's probe path.
    func index_add(id: u32):
        let mask = self.index.length - 1
        var at = (usize)structure_hash(self.types.get((usize)id)) & mask
        while self.index[at] != 0:
            at = (at + 1) & mask
        self.index[at] = id + 1

    ## Twice the buckets, every type re-added.
    func grow_index() -> !:
        let old = self.index
        self.index = try new u32[old.length * 2] --- in self.allocator
        zero_index(self.index)
        var i: usize = 0
        while i < self.types.count:
            self.index_add(u32(i))
            i += 1
        free(old) in self.allocator

    # -- constructors ---------------------------------------------------------------------
    pub func pointer(elem: u32, is_const: bool, is_volatile: bool) -> u32!:
        var t = try plain(Kind.pointer, elem, "")
        t.is_const = is_const
        t.is_volatile = is_volatile
        return try self.intern(t)

    ## The id of `elem[]`, `const` when `is_const`; interned.
    pub func span(elem: u32, is_const: bool) -> u32!:
        var t = try plain(Kind.span, elem, "")
        t.is_const = is_const
        return try self.intern(t)

    ## The id of `elem[length]`; interned.
    pub func array(elem: u32, length: u64) -> u32!:
        var t = try plain(Kind.array, elem, "")
        t.length = length
        return try self.intern(t)

    ## The id of `elem?`; `elem` itself when it is already optional.
    pub func optional(elem: u32) -> u32!:
        if self.kind(elem) == Kind.optional:
            return elem
        return try self.intern(try plain(Kind.optional, elem, ""))

    ## The id of `elem!`; `elem` itself when it is already fallible.
    pub func fallible(elem: u32) -> u32!:
        if self.kind(elem) == Kind.fallible:
            return elem
        return try self.intern(try plain(Kind.fallible, elem, ""))

    ## The id of `@elem`; interned.
    pub func atomic(elem: u32) -> u32!:
        return try self.intern(try plain(Kind.atomic, elem, ""))

    ## The id of the tuple of `members`; interned.
    pub func tuple(members: u32[]) -> u32!:
        var t = try plain(Kind.tuple, 0, "")
        t.args = members
        return try self.intern(t)

    ## The id of the function type over `params` returning `result`; interned.
    pub func function(params: u32[], result: u32, variadic: bool) -> u32!:
        var t = try plain(Kind.func_, result, "")
        t.args = params
        t.variadic = variadic
        return try self.intern(t)

    ## A nominal type for a declaration; the same declaration yields the same id.
    pub func nominal(kind: Kind, decl: ast.Node*, args: u32[]) -> u32!:
        var t = try plain(kind, 0, decl.text)
        t.decl = decl
        t.args = args
        return try self.intern(t)

    ## A generic parameter of a declaration.
    pub func parameter(decl: ast.Node*, name: str) -> u32!:
        var t = try plain(Kind.param, 0, name)
        t.decl = decl
        return try self.intern(t)

    # -- predicates -----------------------------------------------------------------------
    pub func is_integer(id: u32) -> bool:
        let k = (u8)self.kind(id)
        return (k >= (u8)Kind.i8_ and k <= (u8)Kind.usize_) or k == (u8)Kind.untyped_int

    ## Whether `id` is a signed integer type.
    pub func is_signed(id: u32) -> bool:
        let k = self.kind(id)
        return k == Kind.i8_ or k == Kind.i16_ or k == Kind.i32_ or k == Kind.i64_ or k == Kind.isize_ or k == Kind.untyped_int

    ## Whether `id` is a floating-point type.
    pub func is_float(id: u32) -> bool:
        let k = self.kind(id)
        return k == Kind.f16_ or k == Kind.f32_ or k == Kind.f64_ or k == Kind.untyped_float

    ## Whether `id` is an integer or a float.
    pub func is_numeric(id: u32) -> bool:
        return self.is_integer(id) or self.is_float(id)

    ## A vector (§5.12): an array of one integer type of a stated width, or of `f32` or
    ## `f64`, whose bytes number eight or sixteen.
    pub func is_vector(id: u32) -> bool:
        let t = self.get(id)
        if t.kind != Kind.array or is_distinct_c(t.elem):
            return false
        let k = self.kind(t.elem)
        let lane = k == Kind.i8_ or k == Kind.i16_ or k == Kind.i32_ or k == Kind.i64_ or k == Kind.u8_ or k == Kind.u16_ or k == Kind.u32_ or k == Kind.u64_ or k == Kind.f32_ or k == Kind.f64_
        if not lane:
            return false
        let bytes = self.size_of(t.elem) * t.length
        return bytes == 8 or bytes == 16

    ## `T*?`, `c.str?`, and `func(...)?` are one word with null as the niche (§5.3, §5.5,
    ## §5.6); an interface view's optional is the two-word view with a null data word
    ## (§14.3). None of them carries a flag.
    pub func has_null_niche(elem: u32) -> bool:
        let inner = self.kind(elem)
        return inner == Kind.pointer or inner == Kind.cstr_ or inner == Kind.func_ or inner == Kind.interface_ or self.is_opaque_handle(elem)

    ## An `extern type Name` with no integer shape: a pointer-shaped handle that is never
    ## null bare and keeps `none` in the null niche (§17.1).
    pub func is_opaque_handle(id: u32) -> bool:
        let t = self.get(id)
        if t.kind != Kind.struct_:
            return false
        let d = t.decl else return false
        return d.kind == ast.Kind.extern_type and d.ty == none

    ## An optional that is one word with null as its niche rather than a flag.
    pub func is_nullable_pointer(id: u32) -> bool:
        let t = self.get(id)
        return t.kind == Kind.optional and self.has_null_niche(t.elem) and self.kind(t.elem) != Kind.interface_

    ## `Writer?`: an interface view's optional, the two-word view whose data word is null
    ## for `none` (§14.3).
    pub func is_nullable_view(id: u32) -> bool:
        let t = self.get(id)
        return t.kind == Kind.optional and self.kind(t.elem) == Kind.interface_

    ## Bits of an integer or float type; `isize` and `usize` are the target's word; 0 for
    ## anything else.
    pub func bits(id: u32) -> u32:
        match self.kind(id):
            .i8_, .u8_: return 8
            .i16_, .u16_: return 16
            .i32_, .u32_: return 32
            .i64_, .u64_, .untyped_int: return 64
            .isize_, .usize_: return (u32)(self.word * 8)
            .f16_: return 16
            .f32_: return 32
            .f64_, .untyped_float: return 64
            .char_: return 32
            .bool_: return 8
            _: return 0

    ## Whether function type `want` takes a `T*` where function type `have` takes the
    ## `const T*`: a function that only reads standing for one that may change (§5.6). One
    ## machine type, but two C types, so the C backend calls it through an adapter.
    pub func reads_where_changed(have: u32, want: u32) -> bool:
        let h = self.get(have)
        let w = self.get(want)
        if h.kind != Kind.func_ or w.kind != Kind.func_ or h.args.length != w.args.length:
            return false
        var i: usize = 0
        while i < h.args.length:
            let hp = self.get(h.args[i])
            let wp = self.get(w.args[i])
            if hp.kind == Kind.pointer and wp.kind == Kind.pointer and hp.is_const and not wp.is_const and hp.elem == wp.elem:
                return true
            i += 1
        return false

    ## Whether an integer of `from` widens implicitly to `to` (base.md §7.5):
    ## the same signedness and no fewer bits.
    pub func widens(source: u32, target: u32) -> bool:
        if not self.is_integer(source) or not self.is_integer(target):
            return false
        if is_distinct_c(source) or is_distinct_c(target):
            return false
        if self.kind(source) == Kind.untyped_int:
            return true
        # strictly wider: `u64` and `usize` share a width and stay distinct (§5.1)
        return self.is_signed(source) == self.is_signed(target) and self.bits(source) < self.bits(target)

    ## Whether the zero bit pattern is a valid value (base.md §6.1).
    pub func zeroable(id: u32) -> bool:
        return self.zeroable_in(id, none, no_args_view())

    ## Zeroability of `id` where a generic instance's parameters stand for its arguments:
    ## `Pair[i64]` is zeroable because `i64` is, whatever `T` alone would say.
    func zeroable_in(id: u32, env_decl: ast.Node*?, env_args: u32[]) -> bool:
        if self.is_opaque_handle(id):
            return false  # never null bare (§17.1)
        let t = self.get(id)
        match t.kind:
            .pointer, .cstr_, .func_, .never_, .error_, .fmt_, .void_: return false
            .param:
                let resolved = self.through(id, env_decl, env_args)
                return false if resolved == id else self.zeroable_in(resolved, none, no_args_view())
            .optional: return true
            .array: return self.zeroable_in(t.elem, env_decl, env_args)
            .tuple:
                for m in t.args:
                    if not self.zeroable_in(m, env_decl, env_args):
                        return false
                return true
            .struct_, .union_:
                # a struct with a field default or a custom `init` has no zero value: the
                # zero would bypass what they establish (§6.1)
                if let decl = t.decl:
                    var room: u32[max_type_arguments]
                    let inner = self.instance_args(t, env_decl, env_args, room)
                    var cursor = decl.body
                    while let member = cursor:
                        if member.kind == ast.Kind.field and not self.zeroable_in(member.type_id, decl, inner):
                            return false
                        if t.kind == Kind.struct_ and member.kind == ast.Kind.field and member.left != none:
                            return false
                        if t.kind == Kind.struct_ and member.kind == ast.Kind.func_ and member.text == "init":
                            return false
                        cursor = member.next
                return true
            .enum_:
                # an integer-backed enum needs a case whose value is zero; a payload enum's
                # first case must carry no payload, since tag zero is that case (§6.1)
                let decl = t.decl else return true
                if decl.ty != none:
                    var cursor = decl.body
                    while let node = cursor:
                        if node.kind == ast.Kind.enum_case and case_value(decl, node) == 0:
                            return true
                        cursor = node.next
                    return false
                var first = decl.body
                while let node = first:
                    if node.kind == ast.Kind.enum_case:
                        return node.body == none
                    first = node.next
                return false
            .interface_: return false
            _: return true

    # -- layout ---------------------------------------------------------------------------

    ## Sizes and alignments of a type; a generic instance's fields are measured with
    ## the declaration's parameters standing for the instance's arguments.
    pub func size_of(id: u32) -> u64:
        return self.sized(id, none, no_args_view())

    ## The alignment of `id` in bytes.
    pub func align_of(id: u32) -> u64:
        return self.aligned(id, none, no_args_view())

    ## The parameter `t` (of `env_decl`) resolved through `env_args`, or the id itself.
    func through(id: u32, env_decl: ast.Node*?, env_args: u32[]) -> u32:
        let t = self.get(id)
        if t.kind != Kind.param:
            return id
        let d = env_decl else return id
        let owner = t.decl else return id
        if owner != d:
            return id
        var index: usize = 0
        var cursor = d.left
        if let l = cursor:
            if l.kind == ast.Kind.generic_param:
                cursor = l.body
            else:
                cursor = none
        while let g = cursor:
            if g.text == t.name:
                return env_args[index] if index < env_args.length else id
            index += 1
            cursor = g.next
        return id

    ## An instance's arguments resolved through the enclosing environment, into `out`.
    func instance_args(t: Type, env_decl: ast.Node*?, env_args: u32[], out: u32[]) -> u32[]:
        var n: usize = 0
        while n < t.args.length and n < out.length:
            out[n] = self.through(t.args[n], env_decl, env_args)
            n += 1
        return out[..<n]

    func sized(id: u32, env_decl: ast.Node*?, env_args: u32[]) -> u64:
        if self.is_opaque_handle(id):
            return self.word  # a pointer-shaped handle (§17.1)
        let t = self.get(id)
        match t.kind:
            .i8_, .u8_, .bool_: return 1
            .i16_, .u16_, .f16_: return 2
            .i32_, .u32_, .f32_, .char_, .error_code: return 4
            .i64_, .u64_, .f64_, .untyped_int, .untyped_float: return 8
            .isize_, .usize_, .pointer, .func_, .cstr_: return self.word
            .str_, .span, .interface_, .fmt_: return 2 * self.word
            .error_value: return 3 * self.word
            .param:
                let resolved = self.through(id, env_decl, env_args)
                return 0 if resolved == id else self.sized(resolved, none, no_args_view())
            .array: return self.sized(t.elem, env_decl, env_args) * t.length
            .atomic: return self.sized(t.elem, env_decl, env_args)
            .optional:
                if self.has_null_niche(t.elem):
                    return self.sized(t.elem, env_decl, env_args)  # the payload itself
                let inner = self.sized(t.elem, env_decl, env_args)
                let a = self.aligned(t.elem, env_decl, env_args)
                return round_up(inner, a) + a if a > 0 else inner + 1
            .fallible:
                # the value, then the error (a code and a message), then the flag, as C lays them out
                let inner = self.sized(t.elem, env_decl, env_args) if t.elem != unit_id and t.elem != never_id else 0
                return round_up(round_up(inner, self.word) + 3 * self.word + 1, self.word)
            .tuple:
                var offset: u64 = 0
                var largest: u64 = 1
                for m in t.args:
                    let a = self.aligned(m, env_decl, env_args)
                    offset = round_up(offset, a) + self.sized(m, env_decl, env_args)
                    largest = a if a > largest else largest
                return round_up(offset, largest)
            .struct_:
                var offset: u64 = 0
                var largest: u64 = 1
                let decl = t.decl else return 0
                var room: u32[max_type_arguments]
                let inner = self.instance_args(t, env_decl, env_args, room)
                var cursor = decl.body
                while let member = cursor:
                    if member.kind == ast.Kind.field:
                        let a = field_align(self.aligned(member.type_id, decl, inner), member)
                        if not decl.has(ast.flag_packed):
                            offset = round_up(offset, a)
                        offset += self.sized(member.type_id, decl, inner)
                        largest = a if a > largest else largest
                    cursor = member.next
                if decl.has(ast.flag_packed):
                    return offset
                return round_up(offset, declared_align(largest, decl))
            .union_:
                var largest: u64 = 0
                var widest: u64 = 1
                let decl = t.decl else return 0
                var room: u32[max_type_arguments]
                let inner = self.instance_args(t, env_decl, env_args, room)
                var cursor = decl.body
                while let member = cursor:
                    if member.kind == ast.Kind.field:
                        let s = self.sized(member.type_id, decl, inner)
                        largest = s if s > largest else largest
                        let a = field_align(self.aligned(member.type_id, decl, inner), member)
                        widest = a if a > widest else widest
                    cursor = member.next
                return round_up(largest, widest)
            .enum_:
                let decl = t.decl else return 4
                if let backing = decl.ty:
                    return self.sized(backing.type_id, none, no_args_view()) if backing.type_id != none_id else 4
                var room: u32[max_type_arguments]
                let inner = self.instance_args(t, env_decl, env_args, room)
                var largest: u64 = 0
                var widest: u64 = 4
                var cursor = decl.body
                while let node = cursor:
                    if node.kind == ast.Kind.enum_case:
                        var offset: u64 = 0
                        var pcursor = node.body
                        while let p = pcursor:
                            let a = self.aligned(p.type_id, decl, inner)
                            offset = round_up(offset, a) + self.sized(p.type_id, decl, inner)
                            widest = a if a > widest else widest
                            pcursor = p.next
                        largest = offset if offset > largest else largest
                    cursor = node.next
                return round_up(round_up(4, widest) + largest, widest)
            _: return 0

    func aligned(id: u32, env_decl: ast.Node*?, env_args: u32[]) -> u64:
        if self.is_opaque_handle(id):
            return self.word
        let t = self.get(id)
        match t.kind:
            .param:
                let resolved = self.through(id, env_decl, env_args)
                return 1 if resolved == id else self.aligned(resolved, none, no_args_view())
            .array: return self.aligned(t.elem, env_decl, env_args)
            .atomic: return self.aligned(t.elem, env_decl, env_args)
            .optional:
                if self.has_null_niche(t.elem):
                    return self.aligned(t.elem, env_decl, env_args)
                let a = self.aligned(t.elem, env_decl, env_args)
                return a if a > 0 else 1
            .fallible: return self.word
            .tuple:
                var widest: u64 = 1
                for m in t.args:
                    let a = self.aligned(m, env_decl, env_args)
                    widest = a if a > widest else widest
                return widest
            .struct_, .union_, .enum_:
                let decl = t.decl else return 1
                if decl.has(ast.flag_packed):
                    return 1
                if t.kind == Kind.enum_:
                    if let backing = decl.ty:
                        return self.aligned(backing.type_id, none, no_args_view()) if backing.type_id != none_id else 4
                var room: u32[max_type_arguments]
                let inner = self.instance_args(t, env_decl, env_args, room)
                var widest: u64 = 4 if t.kind == Kind.enum_ else 1
                var cursor = decl.body
                while let member = cursor:
                    if member.kind == ast.Kind.field:
                        let a = field_align(self.aligned(member.type_id, decl, inner), member)
                        widest = a if a > widest else widest
                    elif member.kind == ast.Kind.enum_case:
                        var pcursor = member.body
                        while let p = pcursor:
                            let a = self.aligned(p.type_id, decl, inner)
                            widest = a if a > widest else widest
                            pcursor = p.next
                    cursor = member.next
                return declared_align(widest, decl)
            .str_, .span, .interface_, .fmt_, .error_value: return self.word
            _:
                let s = self.sized(id, env_decl, env_args)
                return s if s > 0 else 1

    ## A field's alignment: its type's, raised by the `align(N)` before the field (§5.11).
    ## Every layout, in the table and in the backends, places a field by this.
    pub func field_alignment(id: u32, member: ast.Node*) -> u64:
        return field_align(self.align_of(id), member)

    ## Byte offset of `field` in the struct `id`; 0 when absent.
    pub func offset_of(id: u32, field: str) -> u64:
        let t = self.get(id)
        let decl = t.decl else return 0
        var room: u32[max_type_arguments]
        let inner = self.instance_args(t, none, no_args_view(), room)
        var offset: u64 = 0
        var cursor = decl.body
        while let member = cursor:
            if member.kind == ast.Kind.field:
                if not decl.has(ast.flag_packed):
                    offset = round_up(offset, field_align(self.aligned(member.type_id, decl, inner), member))
                if member.text == field:
                    return offset
                offset += self.sized(member.type_id, decl, inner)
            cursor = member.next
        return 0

    # -- names ----------------------------------------------------------------------------

    ## The type a suffix (`*`, `[]`, `[N]`, `?`) follows: an atomic one in parentheses,
    ## since `@` covers the whole type after it (§15.1): `(@u64)*` points to an atomic,
    ## where `@u64*` is an atomic pointer.
    ## The element of a pointer, span, array or optional, parenthesised where it would
    ## otherwise read as something else: under `const` or `volatile`, which qualify the
    ## innermost type (§5.3), a compound element, so `const (Rule*)[]` (a read-only span of
    ## pointers) is not `const Rule*[]` (a span of pointers to read-only rules); a span or
    ## array under `[]` or `[N]`, since a run of brackets reads inside-out (§5.4), so two
    ## spans of read-only bytes are `(const u8[])[2]`, not `const u8[][2]`, which is a span
    ## of arrays; an optional under `[]` or `[N]`, `(c.str?)[3]`, or under `*` unless it is
    ## a nullable pointer (`Link*?*`); a function type, whose result would take the suffix;
    ## and an atomic.
    func describe_element(out: io.Writer, elem: u32, qualified: bool, parent: Kind) -> !:
        let e = self.get(elem)
        var grouped = e.kind == Kind.atomic or e.kind == Kind.func_ or e.kind == Kind.fallible
        if qualified and (e.kind == Kind.pointer or e.kind == Kind.span or e.kind == Kind.array or e.kind == Kind.optional):
            grouped = true
        if (parent == Kind.span or parent == Kind.array) and (e.kind == Kind.span or e.kind == Kind.array):
            grouped = true
        if e.kind == Kind.optional and parent != Kind.optional:
            grouped = grouped or parent != Kind.pointer or self.kind(e.elem) != Kind.pointer
        if grouped:
            try out.write("(")
            try self.describe(out, elem)
            try out.write(")")
            return
        try self.describe(out, elem)

    ## Write the type as a programmer would spell it, for diagnostics.
    pub func describe(out: io.Writer, id: u32) -> !:
        let t = self.get(id)
        match t.kind:
            .pointer:
                if t.is_const:
                    try out.write("const ")
                if t.is_volatile:
                    try out.write("volatile ")
                try self.describe_element(out, t.elem, t.is_const or t.is_volatile, t.kind)
                try out.write("*")
            .span:
                if t.is_const:
                    try out.write("const ")
                try self.describe_element(out, t.elem, t.is_const, t.kind)
                try out.write("[]")
            .array:
                try self.describe_element(out, t.elem, false, t.kind)
                try out.write(f"[{t.length}]")
            .optional:
                try self.describe_element(out, t.elem, false, t.kind)
                try out.write("?")
            .fallible:
                if t.elem != unit_id:
                    try self.describe(out, t.elem)
                try out.write("!")
            .atomic:
                try out.write("@")
                try self.describe(out, t.elem)
            .tuple:
                try out.write("(")
                var i: usize = 0
                while i < t.args.length:
                    if i > 0:
                        try out.write(", ")
                    try self.describe(out, t.args[i])
                    i += 1
                try out.write(")")
            .func_:
                try out.write("func(")
                var i: usize = 0
                while i < t.args.length:
                    if i > 0:
                        try out.write(", ")
                    try self.describe(out, t.args[i])
                    i += 1
                try out.write(") -> ")
                try self.describe(out, t.elem)
            .struct_, .enum_, .union_, .interface_, .param, .module, .type_name:
                try out.write(t.name)
                if t.args.length > 0:
                    try out.write("[")
                    var i: usize = 0
                    while i < t.args.length:
                        if i > 0:
                            try out.write(", ")
                        try self.describe(out, t.args[i])
                        i += 1
                    try out.write("]")
            _:
                try out.write(t.name)

## Whether `have` is the type `t` describes: the same structure, and for a generic
## parameter, which is its own type, or a type without a declaration, the same name.
func same_type(have: Type, t: Type) -> bool:
    if have.kind != t.kind or have.elem != t.elem or have.length != t.length or have.is_const != t.is_const or have.is_volatile != t.is_volatile or have.variadic != t.variadic or have.decl != t.decl or not same_args(have.args, t.args):
        return false
    if t.kind == Kind.param:
        return have.name == t.name
    return have.decl != none or have.name == t.name

func plain(kind: Kind, elem: u32, name: str) -> Type!:
    return Type(kind = kind, elem = elem, args = try no_args(), length = 0, is_const = false, is_volatile = false, variadic = false, decl = none, name = name)

## An empty argument list: a one-element allocation sliced to nothing, since a
## Base array literal cannot be empty (§5.4).
## An empty argument list that lives forever, for measuring types outside any instance.
var no_arguments: u32[1]

func no_args_view() -> u32[]:
    return no_arguments[..<0]

## An empty owned `u32[]`, for a type or call with no arguments.
pub func no_args() -> u32[]!:
    let one = try new u32[1] ---
    return one[..<0]

func round_up(value: u64, align: u64) -> u64:
    if align <= 1:
        return value
    return (value + align - 1) // align * align

## Whether two lists of type arguments are the same, id for id.
pub func same_args(a: const u32[], b: const u32[]) -> bool:
    if a.length != b.length:
        return false
    var i: usize = 0
    while i < a.length:
        if a[i] != b[i]:
            return false
        i += 1
    return true

# mark: Tests ==================================================================================

test "scalars are seeded at fixed ids and interning deduplicates":
    var backing: u8[65536]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var table = try Table.create()
        assert(table.kind(i64_id) == Kind.i64_)
        assert(table.kind(str_id) == Kind.str_)
        let p1 = try table.pointer(u8_id, true, false)
        let p2 = try table.pointer(u8_id, true, false)
        let p3 = try table.pointer(u8_id, false, false)
        assert(p1 == p2)
        assert(p1 != p3)
        let o = try table.optional(p3)
        assert(table.is_nullable_pointer(o))
        assert(table.size_of(o) == 8)
        assert(table.size_of(try table.array(i32_id, 5)) == 20)
        var members: u32[2] = [u8_id, i64_id]
        let tup = try table.tuple(members)
        assert(table.size_of(tup) == 16)
        assert(table.align_of(tup) == 8)
        assert(table.widens(u8_id, u32_id))
        assert(not table.widens(u8_id, i32_id))

## The `N` of `align(N)` (§5.11) on a declaration or a field, a decimal literal, or 0 when
## there is none.
pub func explicit_align(n: ast.Node*?) -> u64:
    let e = n else return 0
    if e.kind != ast.Kind.literal:
        return 0
    var value: u64 = 0
    for b in e.text.bytes:
        if b < '0' or b > '9':
            return 0
        value = value * 10 + (u64)(b - '0')
    return value

## A field's alignment: its type's, raised by `align(N)` before the field.
func field_align(natural: u64, member: ast.Node*) -> u64:
    let e = explicit_align(member.right)
    return e if e > natural else natural

## A struct's alignment: its widest field's, raised by `align(N)` before the struct.
func declared_align(natural: u64, decl: ast.Node*) -> u64:
    if decl.kind != ast.Kind.struct_:
        return natural
    let e = explicit_align(decl.right)
    return e if e > natural else natural

## The value of case `target` of enum `d`: as written, or one more than the case before.
pub func case_value(d: ast.Node*, target: ast.Node*) -> u64:
    var next: u64 = 0
    var cursor = d.body
    while let node = cursor:
        if node.kind == ast.Kind.enum_case:
            var v = next
            if let written = node.left:
                v = written_value(written) else next
            if node == target:
                return v
            next = v +% 1
        cursor = node.next
    return 0

## For each case of enum `d`, in order, whether an earlier case has its value: the values
## in one pass and a hash set of them, where `case_value` for each case against each
## earlier one would take time cubic in the number of cases.
pub func repeated_cases(d: ast.Node*) -> bool[]!:
    var count: usize = 0
    var cursor = d.body
    while let node = cursor:
        if node.kind == ast.Kind.enum_case:
            count += 1
        cursor = node.next
    var repeated = try new bool[count] ---
    var size: usize = 16
    while size < count * 2:
        size *= 2
    # open addressing over the values; `taken` marks a filled bucket
    var buckets = try new u64[size] ---
    defer free(buckets)
    var taken = try new bool[size] ---
    defer free(taken)
    for k in 0..<size:
        taken[k] = false
    var next: u64 = 0
    var index: usize = 0
    cursor = d.body
    while let node = cursor:
        if node.kind == ast.Kind.enum_case:
            var v = next
            if let written = node.left:
                v = written_value(written) else next
            next = v +% 1
            repeated[index] = false
            var at = (usize)((v *% 0x9E3779B97F4A7C15) >> 32) & (size - 1)
            while taken[at] and buckets[at] != v:
                at = (at + 1) & (size - 1)
            if taken[at]:
                repeated[index] = true
            else:
                taken[at] = true
                buckets[at] = v
            index += 1
        cursor = node.next
    return repeated

## A case value as written: a literal, possibly grouped or negated.
func written_value(e: ast.Node*) -> u64?:
    if e.kind == ast.Kind.group:
        let inner = e.left else return none
        return written_value(inner)
    if e.kind == ast.Kind.unary and e.text == "-":
        let inner = e.left else return none
        let v = written_value(inner) else return none
        return 0 -% v
    if e.kind == ast.Kind.literal:
        let v = literals.decode_integer(e.text) catch failure:
            return none
        return v
    return none