dymokomi/luce-base
Source of release 0.42.0
0.42.0 / src / sema / check / types.lucb
#==============================================================================================
#
# check/types - Types and substitution
#
# DESCRIPTION:
# Written types resolved to the table's ids, and a generic's arguments
# substituted into them (§13).
#
#==============================================================================================
extend Checker:
# mark: Types ==============================================================================
## Resolve a written type (§5, §21) to its id, recording it on the node.
pub func resolve_type(t: ast.Node*) -> u32!:
# a type node resolved once keeps its type; the checker re-reads calls it rewrites
if t.type_id != types.none_id and t.kind == ast.Kind.type_:
return t.type_id
var id = types.none_id
if t.has(ast.flag_func_type):
let n = ast.count(t.body)
var params = try types.no_args()
if n > 0:
params = try new u32[n] ---
var i: usize = 0
var cursor = t.body
while let p = cursor:
params[i] = try self.resolve_type(p)
i += 1
cursor = p.next
let result = t.left else return try self.fail(t, "a function type needs a result")
id = try self.table.function(params, try self.resolve_type(result), false)
elif t.has(ast.flag_void):
id = types.void_id
elif t.has(ast.flag_tuple_type):
let n = ast.count(t.body)
var members = try new u32[n] ---
var i: usize = 0
var cursor = t.body
while let m = cursor:
members[i] = try self.resolve_type(m)
i += 1
cursor = m.next
id = try self.table.tuple(members)
elif t.has(ast.flag_star):
let inner = t.left else return try self.fail(t, "a pointer needs a pointee")
let elem = try self.resolve_type(inner)
# a qualifier binds to the innermost type (§5.3): `const f32[4]*` is a pointer to
# a read-only array, its `const` on the element beneath the array suffixes
var qualified = inner
while qualified.has(ast.flag_array):
qualified = qualified.left else break
id = try self.table.pointer(elem, qualified.has(ast.flag_const), qualified.has(ast.flag_volatile))
elif t.has(ast.flag_span):
let inner = t.left else return try self.fail(t, "a span needs an element type")
let elem = try self.resolve_type(inner)
id = try self.table.span(elem, inner.has(ast.flag_const))
elif t.has(ast.flag_array):
let inner = t.left else return try self.fail(t, "an array needs an element type")
let count = t.right else return try self.fail(t, "an array needs a length")
let elem = try self.resolve_type(inner)
let length = try self.constant_length(count)
if length == 0:
return try self.fail(count, "an array length is positive; C has no zero-length arrays (§5.4)")
id = try self.table.array(elem, length)
elif t.has(ast.flag_optional):
let inner = t.left else return try self.fail(t, "an optional needs a payload")
id = try self.table.optional(try self.resolve_type(inner))
elif t.has(ast.flag_fallible):
let inner = t.left else return try self.fail(t, "a result needs a payload")
id = try self.table.fallible(try self.resolve_type(inner))
elif t.text == "(":
let inner = t.left else return try self.fail(t, "empty parentheses")
id = try self.resolve_type(inner)
else:
id = try self.resolve_named(t)
if t.has(ast.flag_atomic):
if not self.atomic_allowed(id):
return try self.fail(t, "`@T` needs an integer, `bool`, or a pointer of at most pointer width, or a struct of two words (§5.9)")
id = try self.table.atomic(id)
t.type_id = id
return id
## What `@T` may hold (§5.9): an integer, `bool`, a pointer or nullable pointer, all of at
## most pointer width; or a struct of two pointer-width words for the double-width cas.
func atomic_allowed(id: u32) -> bool:
let k = self.table.kind(id)
if self.table.is_integer(id) or id == types.bool_id or k == types.Kind.pointer:
return self.table.size_of(id) <= 8
if k == types.Kind.optional:
return self.table.is_nullable_pointer(id) # one word; a view's optional is two
if k == types.Kind.struct_:
return self.table.size_of(id) == 16 and self.table.align_of(id) == 8
return false
## A named type: a scalar, a declaration in scope, `module.Type`, or an
## instance `Name[args]` of a generic declaration.
func resolve_named(t: ast.Node*) -> u32!:
if let arr = try self.array_reading(t):
return try self.resolve_type(arr)
let scalar = scalar_id(t.text)
if scalar != types.none_id:
if t.body != none:
return try self.fail(t, "a scalar takes no type arguments")
return scalar
var decl: ast.Node*? = none
if let b = self.lookup(t.text):
note_origin(b)
var said2: u8[256]
let d = b.decl else return try self.fail(t, said(said2, f"`{t.text}` is not a type"))
decl = d
else:
let dot = strings.find(t.text, ".") else t.text.length
if dot >= t.text.length:
return try self.unknown_type(t)
let head = (str)t.text.bytes[..<dot]
let rest = (str)t.text.bytes[dot + 1..]
let mb = self.lookup(head) else return try self.unknown_type(t)
note_origin(mb)
let module = mb.decl else return try self.unknown_type(t)
if module.kind != ast.Kind.module:
return try self.fail(t, "that is not a module")
if self.is_c_module(module) and c_type_id(rest) != types.none_id:
return c_type_id(rest)
var said3: u8[256]
let d = self.module_decl(module, rest) else return try self.fail(t, said(said3, f"`{module.text}` has no type `{rest}`"))
if not d.has(ast.flag_pub):
var said4: u8[256]
return try self.fail(t, said(said4, f"`{rest}` is not public in `{module.text}`"))
decl = d
var said5: u8[256]
let d = decl else return try self.fail(t, said(said5, f"`{t.text}` is not a type"))
t.resolved = d
if d.kind == ast.Kind.type_alias:
if d.type_id == types.none_id:
let target = d.ty else return try self.fail(t, "an alias needs a type")
# `type Loop = Loop*`: an alias reached again while its own type is being
# resolved names itself, which no type is
for busy in self.resolving.span():
if busy == (usize)d:
return try self.fail(t, "this alias is recursive")
try self.resolving.push((usize)d)
d.type_id = try self.resolve_type(target)
self.resolving.count -= 1
return d.type_id
if d.kind == ast.Kind.generic_param:
return d.type_id
var said6: u8[256]
if not is_type_decl(d):
return try self.fail(t, said(said6, f"`{t.text}` is not a type"))
let arity = ast.count(generic_params_of(d))
if t.body != none:
let n = ast.count(t.body)
if arity != n:
return try self.fail(t, "wrong number of type arguments")
var args = try new u32[n] ---
var i: usize = 0
var cursor = t.body
while let a = cursor:
args[i] = try self.resolve_type(a)
i += 1
cursor = a.next
return try self.table.nominal(self.table.kind(d.type_id), d, args)
if arity > 0:
# inside its own declaration the generic type stands for itself
if self.self_decl() != d:
return try self.fail(t, "this type needs type arguments")
return d.type_id
## The declaration a bare or `module.`-qualified name refers to when it is a value rather
## than a type: a constant, a global, or a local.
func bracket_value_decl(text: str) -> ast.Node*?:
let dot = strings.find(text, ".") else text.length
var decl: ast.Node*? = none
if dot >= text.length:
let b = self.lookup(text) else return none
decl = b.decl
else:
let mb = self.lookup((str)text.bytes[..<dot]) else return none
let m = mb.decl else return none
if m.kind != ast.Kind.module:
return none
decl = self.module_decl(m, (str)text.bytes[dot + 1..])
let d = decl else return none
if d.kind == ast.Kind.constant or d.kind == ast.Kind.global or d.kind == ast.Kind.let_ or d.kind == ast.Kind.var_ or d.kind == ast.Kind.param:
return d
return none
## `T[NAME]` where NAME is a value, not a type: the parser read a type argument, the
## program means an array of NAME elements (§5.4). That array type, or none.
func array_reading(t: ast.Node*) -> ast.Node*?!:
let arg = t.body else return none
if arg.next != none or arg.kind != ast.Kind.type_ or arg.flags != 0 or arg.left != none or arg.body != none or arg.text.length == 0:
return none
if self.bracket_value_decl(arg.text) == none:
return none
let base = try ast.Node.make(ast.Kind.type_, t.text, t.start, t.line)
let arr = try ast.Node.make(ast.Kind.type_, "[", t.start, t.line)
arr.flags |= ast.flag_array
arr.left = base
arr.right = try bracket_name_expr(arg)
return arr
## `table[NAME].f` read as a generic instance of a value: an index (§7.6). Rewrites `e`
## in place and says whether it did.
func index_reading(e: ast.Node*) -> bool!:
let holder = e.ty else return false
let arg = holder.body else return false
if arg.next != none or arg.kind != ast.Kind.type_ or arg.flags != 0 or arg.left != none or arg.body != none:
return false
if self.bracket_value_decl(e.text) == none or self.bracket_value_decl(arg.text) == none:
return false
let owner = try ast.Node.make(ast.Kind.name, e.text, e.start, e.line)
e.kind = ast.Kind.index
e.text = ""
e.ty = none
e.left = owner
e.body = try bracket_name_expr(arg)
return true
## The type declaration whose members are being checked, if any.
func self_decl() -> ast.Node*?:
if self.self_type == types.none_id:
return none
return self.table.get(self.self_type).decl
## An array length (§5.4): a constant integer expression (§6.4), the same ones a top-level
## `let` may hold, checked as a `usize` and folded by the evaluator every constant uses.
func constant_length(e: ast.Node*) -> u64!:
let t = try self.check_expr(e, types.usize_id)
if t != types.untyped_int_id and not self.table.is_integer(t):
return try self.fail(e, "an array length is an integer")
try self.settle_values(e)
try self.length_arithmetic_fits(e)
return self.constant_u64(e) else return try self.fail(e, "an array length must be a constant integer expression (§6.4)")
## Every `+ - * // %` in a length computes inside `u64` (§5.4): where a constant wraps, a
## length that overflows or divides by zero is refused.
func length_arithmetic_fits(e: ast.Node*) -> !:
if let l = e.left:
try self.length_arithmetic_fits(l)
if let r = e.right:
try self.length_arithmetic_fits(r)
if e.kind != ast.Kind.binary or not (e.text == "+" or e.text == "-" or e.text == "*" or e.text == "//" or e.text == "%"):
return
let l = e.left else return
let r = e.right else return
let a = self.constant_u64(l) else return
let b = self.constant_u64(r) else return
if length_arith(e.text, a, b) == none:
try self.fail(e, "an array length is a constant that neither overflows nor divides by zero")
## Check the value of every constant `e` reaches whose initialiser is not checked yet, and
## of the constants those reach. A constant with a written type has its type from the
## declarations pass and its value from the bodies pass, which comes after the types that
## need its value as a length; `name_type` checks only a constant without a type.
func settle_values(e: ast.Node*) -> !:
if e.kind == ast.Kind.name or e.kind == ast.Kind.member:
if let d = e.resolved:
if d.kind == ast.Kind.constant and not ast.is_linked(d):
if let init = d.left:
if init.type_id == types.none_id and d.type_id != types.error_id:
d.type_id = types.none_id
try self.check_constant(d)
try self.settle_values(init)
if let l = e.left:
try self.settle_values(l)
if let r = e.right:
try self.settle_values(r)
var cursor = e.body
while let item = cursor:
try self.settle_values(item)
cursor = item.next
## The type an argument of `sizeof`/`alignof` names, or the type of the expression.
func type_of_argument(e: ast.Node*) -> u32!:
if e.kind == ast.Kind.type_:
e.type_id = try self.resolve_type(e)
e.flags |= ast.flag_type_ref
return e.type_id
if e.kind == ast.Kind.name:
let scalar = scalar_id(e.text)
if scalar != types.none_id:
# a scalar type name is a type reference; the backends read `type_id` and the flag
e.type_id = scalar
e.flags |= ast.flag_type_ref
return scalar
if let b = self.lookup(e.text):
note_origin(b)
if let d = b.decl:
if is_type_decl(d) or d.kind == ast.Kind.type_alias or d.kind == ast.Kind.generic_param:
if d.kind == ast.Kind.type_alias and d.type_id == types.none_id:
let target = d.ty else return 0
d.type_id = try self.resolve_type(target)
e.type_id = d.type_id
e.flags |= ast.flag_type_ref
return d.type_id
let id = try self.check_expr(e, types.none_id)
if e.has(ast.flag_type_ref):
return e.type_id
if id == types.untyped_int_id:
return types.i64_id
if id == types.untyped_float_id:
return types.f64_id
return id
# mark: Substitution =======================================================================
## Replace the generic parameters of `decl` inside `id` with `args`.
pub func substitute(id: u32, decl: ast.Node*, args: u32[]) -> u32!:
if args.length == 0:
return id
let t = self.table.get(id)
match t.kind:
.param:
var i: usize = 0
var cursor = generic_params_of(decl)
while let g = cursor:
if g.type_id == id and i < args.length:
return args[i]
i += 1
cursor = g.next
return id
.pointer:
return try self.table.pointer(try self.substitute(t.elem, decl, args), t.is_const, t.is_volatile)
.span:
return try self.table.span(try self.substitute(t.elem, decl, args), t.is_const)
.array:
return try self.table.array(try self.substitute(t.elem, decl, args), t.length)
.optional:
return try self.table.optional(try self.substitute(t.elem, decl, args))
.fallible:
return try self.table.fallible(try self.substitute(t.elem, decl, args))
.atomic:
return try self.table.atomic(try self.substitute(t.elem, decl, args))
.tuple:
var members = try new u32[t.args.length] ---
var i: usize = 0
while i < t.args.length:
members[i] = try self.substitute(t.args[i], decl, args)
i += 1
return try self.table.tuple(members)
.func_:
var params = try types.no_args()
if t.args.length > 0:
params = try new u32[t.args.length] ---
var i: usize = 0
while i < t.args.length:
params[i] = try self.substitute(t.args[i], decl, args)
i += 1
return try self.table.function(params, try self.substitute(t.elem, decl, args), t.variadic)
.struct_, .enum_, .union_, .interface_:
let d = t.decl else return id
if t.args.length == 0:
# the template's own name inside its declaration: instantiate it
if d == decl and ast.count(generic_params_of(d)) == args.length:
return try self.table.nominal(t.kind, d, args)
return id
var inner = try new u32[t.args.length] ---
var i: usize = 0
while i < t.args.length:
inner[i] = try self.substitute(t.args[i], decl, args)
i += 1
return try self.table.nominal(t.kind, d, inner)
_:
return id
## Learn the generic arguments of `decl` by matching a parameter type against
## an argument type; `out` holds one slot per generic parameter.
func infer(param: u32, arg: u32, decl: ast.Node*, out: u32[]) -> !:
let p = self.table.get(param)
let a = self.table.get(arg)
if p.kind == types.Kind.param:
var i: usize = 0
var cursor = generic_params_of(decl)
while let g = cursor:
if g.type_id == param and i < out.length and out[i] == types.none_id:
out[i] = concrete(arg)
i += 1
cursor = g.next
return
if p.kind == a.kind:
if p.kind == types.Kind.pointer or p.kind == types.Kind.span or p.kind == types.Kind.array or p.kind == types.Kind.optional or p.kind == types.Kind.fallible or p.kind == types.Kind.atomic:
try self.infer(p.elem, a.elem, decl, out)
return
if p.kind == types.Kind.tuple or p.kind == types.Kind.func_:
var i: usize = 0
while i < p.args.length and i < a.args.length:
try self.infer(p.args[i], a.args[i], decl, out)
i += 1
if p.kind == types.Kind.func_:
try self.infer(p.elem, a.elem, decl, out)
return
if p.decl == a.decl and p.args.length == a.args.length:
var i: usize = 0
while i < p.args.length:
try self.infer(p.args[i], a.args[i], decl, out)
i += 1
return
if p.kind == types.Kind.optional and arg != types.none_id:
# a value converts to its optional implicitly (`Node*` to `Node*?`), so `T?`
# learns T from the value as from the optional
try self.infer(p.elem, arg, decl, out)
return
if p.kind == types.Kind.span and a.kind == types.Kind.array:
try self.infer(p.elem, a.elem, decl, out)
if p.kind == types.Kind.interface_ and a.kind == types.Kind.pointer:
try self.infer(param, a.elem, decl, out)
## The expression a bracketed name spells: `NAME` or `module.NAME`.
func bracket_name_expr(arg: ast.Node*) -> ast.Node*!:
let dot = strings.find(arg.text, ".") else arg.text.length
if dot >= arg.text.length:
return try ast.Node.make(ast.Kind.name, arg.text, arg.start, arg.line)
let m = try ast.Node.make(ast.Kind.member, (str)arg.text.bytes[dot + 1..], arg.start, arg.line)
m.left = try ast.Node.make(ast.Kind.name, (str)arg.text.bytes[..<dot], arg.start, arg.line)
return m
## An untyped literal type made concrete for inference and bindings.
func concrete(id: u32) -> u32:
if id == types.untyped_int_id:
return types.i64_id
if id == types.untyped_float_id:
return types.f64_id
return id