dymokomi/luce-base
Source of release 0.45.0
0.45.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