Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / sema / check / helpers.lucb

#==============================================================================================
#
#   check/helpers - Helpers
#
#   DESCRIPTION:
#       Functions of the tree and of names that need no checker.
#
#==============================================================================================
# mark: Tree helpers ==========================================================================

## The top-level declaration named `name` in a module tree.
pub func find_decl(tree: ast.Node*, name: str) -> ast.Node*?:
    var cursor = tree.body
    while let d = cursor:
        if d.text == name and d.kind != ast.Kind.import_ and d.kind != ast.Kind.from_import and d.kind != ast.Kind.test_:
            return d
        cursor = d.next
    return none

## The member of `owner` named `name` with the given kind.
pub func find_member(owner: ast.Node*, name: str, kind: ast.Kind) -> ast.Node*?:
    var cursor = owner.body
    while let m = cursor:
        if m.kind == kind and m.text == name:
            return m
        cursor = m.next
    return none

## `a op b` for an array length: none when the result overflows `u64`, divides by zero,
## or the operator is not one of `+ - * // %`.
func length_arith(op: str, a: u64, b: u64) -> u64?:
    if op == "+":
        return (a + b) if a +% b >= a else none
    if op == "-":
        return (a - b) if a >= b else none
    if op == "*":
        return (a * b) if b == 0 or (a *% b) // b == a else none
    if op == "//":
        return (a // b) if b != 0 else none
    if op == "%":
        return (a % b) if b != 0 else none
    return none

## The first field, case, or method of `d` whose name an earlier member already took.
func duplicate_member(d: ast.Node*) -> ast.Node*?:
    var cursor = d.body
    while let m = cursor:
        if is_named_member(m):
            var earlier = d.body
            while let e = earlier:
                if e == m:
                    break
                if is_named_member(e) and e.text == m.text:
                    return m
                earlier = e.next
        cursor = m.next
    return none

func is_named_member(m: ast.Node*) -> bool:
    return m.kind == ast.Kind.field or m.kind == ast.Kind.enum_case or m.kind == ast.Kind.func_

## Whether a file exists at `path`; an absence is a build input (`cache.exists`).
func file_exists(path: c.str) -> bool:
    return cache.exists(path)

## The first name in `later` that `earlier` already lists, if any.
func repeated_name(earlier: ast.Node*?, later: ast.Node*?) -> ast.Node*?:
    var cursor = later
    while let item = cursor:
        var known = earlier
        while let k = known:
            if k.text == item.text:
                return item
            known = k.next
        cursor = item.next
    return none

## The generic-parameter list of declaration `d`, or `none`.
pub func generic_params_of(d: ast.Node*) -> ast.Node*?:
    let l = d.left else return none
    if l.kind != ast.Kind.generic_param:
        return none
    return l.body

## `Equatable`, `Hashable`, and `Comparable` are satisfied by structure, never declared.
func is_derived_bound(d: ast.Node*?) -> bool:
    let decl = d else return false
    if decl.kind != ast.Kind.interface_ or not decl.has(ast.flag_builtin):
        return false
    return decl.text == "Equatable" or decl.text == "Hashable" or decl.text == "Comparable"

## Whether `e` names a function, `f`, `module.f` or `Type.method`, rather than reading a
## value that holds one.
func names_function(e: ast.Node*) -> bool:
    if e.kind != ast.Kind.name and e.kind != ast.Kind.member:
        return false
    let d = e.resolved else return false
    return d.kind == ast.Kind.func_ or d.kind == ast.Kind.extern_func

func is_type_decl(d: ast.Node*) -> bool:
    return d.kind == ast.Kind.struct_ or d.kind == ast.Kind.enum_ or d.kind == ast.Kind.union_ or d.kind == ast.Kind.interface_ or d.kind == ast.Kind.extern_type or d.kind == ast.Kind.extern_struct or d.kind == ast.Kind.extern_union

## Was field `f` of `d` given among `args`, by name or by position?
func argument_names(args: ast.Node*?, f: ast.Node*, d: ast.Node*) -> bool:
    var cursor = args
    while let a = cursor:
        if a.resolved == f:
            return true
        cursor = a.next
    return false

## User text for a diagnostic: itself when short, otherwise its first bytes and a trailing
## `...`, written into `buffer`. A message that echoes unbounded input (an assembly operand,
## an `assert` reason) clips it, or a long enough spelling overflows the formatting buffer
## and the failure is then reported with no position (§19.6).
func clip(buffer: u8[], text: str) -> str!:
    if text.length <= 64:
        return text
    return try strings.format(buffer, f"{(str)text.bytes[..<60]}...")

## Whether asm block `s` has a `reg` operand whose expression is the name `name`.
pub func asm_names_operand(s: ast.Node*, name: str) -> bool:
    var operand = s.right
    while let o = operand:
        if asm_operand_place(o) == "reg":
            if let v = o.left:
                if v.kind == ast.Kind.name and v.text == name:
                    return true
        operand = o.next
    return false

## The register an asm operand names, `x0`, or `reg` for one the compiler chooses.
pub func asm_operand_place(o: ast.Node*) -> str:
    let p = o.body else return ""
    return literals.decode_text(p.text)

## The integer an `enum Name as T` is backed by; `i32` when the enum names none.
pub func enum_backing(table: types.Table*, id: u32) -> u32:
    let d = table.get(id).decl else return types.i32_id
    let backing = d.ty else return types.i32_id
    return backing.type_id

## The identity of a package's error codes (§11.3): sixteen bits of its name, the same
## computation in every compiler of the language.
pub func package_identity(name: str) -> u32:
    var h: u32 = 2166136261
    for byte in name.bytes:
        h = (h ^ (u32)byte) *% 16777619
    return (h ^ (h >> 16)) & 65535

## How deeply generic instances nest in `id`: `Pair[Pair[i64, i64], i64]` is two. A chain of
## instantiations whose arguments nest past `max_nesting` never ends (§13.1).
pub let max_nesting: u32 = 16

## The depth of nested nominal types within `id`, for the recursion limit.
pub func nesting(table: types.Table*, id: u32) -> u32:
    let t = table.get(id)
    match t.kind:
        .struct_, .enum_, .union_:
            var deepest: u32 = 0
            for a in t.args:
                let n = nesting(table, a)
                if n > deepest:
                    deepest = n
            return deepest + 1 if t.args.length > 0 else 0
        .pointer, .span, .array, .optional, .fallible, .atomic:
            return nesting(table, t.elem)
        .tuple, .func_:
            var deepest: u32 = 0
            for a in t.args:
                let n = nesting(table, a)
                if n > deepest:
                    deepest = n
            return deepest
        _:
            return 0

## The greatest `nesting` across `args`.
pub func nesting_of_all(table: types.Table*, args: u32[]) -> u32:
    var deepest: u32 = 0
    for a in args:
        let n = nesting(table, a)
        if n > deepest:
            deepest = n
    return deepest

## The code of `memory.exhausted` (§11.7) as the backends raise it: the prelude's constant,
## under the standard modules' identity `luce`, so a program's comparison holds.
pub func exhausted_code() -> u64:
    return ((u64)package_identity("luce") << 16) | 1

## Whether a callee's receiver is the `ErrorCode` type itself.
func is_error_code_type(receiver: ast.Node*?) -> bool:
    let r = receiver else return false
    return r.has(ast.flag_type_ref) and r.type_id == types.error_code_id

## Whether a message begins with `path:line:column: `, as a located diagnostic does.
func names_a_place(message: str) -> bool:
    let b = message.bytes
    var colons: usize = 0
    var i: usize = 0
    while i < b.length and colons < 3:
        if b[i] == ':':
            colons += 1
            if colons == 3:
                return i + 1 < b.length and b[i + 1] == ' '
        elif colons > 0 and (b[i] < '0' or b[i] > '9'):
            return false
        i += 1
    return false

## The position of parameter `name` among the ones a caller supplies: an extern's `out`
## parameter takes no argument (§17.1), so it has no position.
func param_index(d: ast.Node*, name: str) -> usize?:
    var i: usize = 0
    var cursor = d.right
    while let p = cursor:
        if not p.has(ast.flag_out):
            if p.text == name:
                return i
            i += 1
        cursor = p.next
    return none

## Whether an argument list names `name`, `name = value`.
func named_in(args: ast.Node*?, name: str) -> bool:
    var cursor = args
    while let a = cursor:
        if a.text == name:
            return true
        cursor = a.next
    return false

## The parameter at `index` among the ones a caller supplies.
func param_at(d: ast.Node*, index: usize) -> ast.Node*?:
    var i: usize = 0
    var cursor = d.right
    while let p = cursor:
        if not p.has(ast.flag_out):
            if i == index:
                return p
            i += 1
        cursor = p.next
    return none

## Does a block end in a way that never reaches its own end?
# mark: Name helpers ==========================================================================

## The id of a scalar or core type name, or `none_id`.
## The `c` module's types (base.md §5.2): the fixed-width ones are Base types by another
## name; `char`, `long`, `ulong`, `wchar`, and `va_list` are distinct; `str` is C text.
pub func c_type_id(name: str) -> u32:
    if name == "int": return types.i32_id
    if name == "uint": return types.u32_id
    if name == "short": return types.i16_id
    if name == "ushort": return types.u16_id
    if name == "schar": return types.i8_id
    if name == "uchar": return types.u8_id
    if name == "longlong": return types.i64_id
    if name == "ulonglong": return types.u64_id
    if name == "float": return types.f32_id
    if name == "double": return types.f64_id
    if name == "bool": return types.bool_id
    if name == "size" or name == "uintptr": return types.usize_id
    if name == "ssize" or name == "ptrdiff" or name == "intptr": return types.isize_id
    if name == "char": return types.c_char_id
    if name == "long": return types.c_long_id
    if name == "ulong": return types.c_ulong_id
    if name == "wchar": return types.c_wchar_id
    if name == "va_list": return types.c_va_list_id
    if name == "str": return types.cstr_id
    return types.none_id

## The type id of a scalar spelled `name`, or `none_id`.
pub func scalar_id(name: str) -> u32:
    if name == "i8":
        return types.i8_id
    if name == "i16":
        return types.i16_id
    if name == "i32":
        return types.i32_id
    if name == "i64":
        return types.i64_id
    if name == "isize":
        return types.isize_id
    if name == "u8":
        return types.u8_id
    if name == "u16":
        return types.u16_id
    if name == "u32":
        return types.u32_id
    if name == "u64":
        return types.u64_id
    if name == "usize":
        return types.usize_id
    if name == "f16":
        return types.f16_id
    if name == "f32":
        return types.f32_id
    if name == "f64":
        return types.f64_id
    if name == "bool":
        return types.bool_id
    if name == "char":
        return types.char_id
    if name == "str":
        return types.str_id
    if name == "fmt":
        return types.fmt_id
    if name == "unit":
        return types.unit_id
    if name == "never":
        return types.never_id
    if name == "void":
        return types.void_id
    if name == "ErrorCode":
        return types.error_code_id
    if name == "Error":
        return types.error_value_id
    return types.none_id

## The core functions (§3.5) and modules that no declaration may shadow.
## Whether `name` is one of the core functions of §3.5.
func is_intrinsic(name: str) -> bool:
    let names: str[4] = ["assert", "error", "trap", "print"]
    for n in names:
        if n == name:
            return true
    return false

## Whether `name` is a standard-library module.
pub func is_standard_module(name: str) -> bool:
    return standard.is_module(name)

## The modules the entry file imports, directly or not, by name, as they load. Names
## are the modules' own and live for the whole compilation.
var library_modules: str[1024]
var library_module_count: usize = 0

## Start the list of library modules afresh for another compilation in the same process: a
## host that checks again and again (`embed.check_root`) does not keep the last one's names,
## which lived in its arena.
pub func forget_library_modules():
    library_module_count = 0

## A test build (§16.5) takes the file under test as library code too: its tests are the
## program, and what they do not reach is not compiled, as for any import.
pub func test_as_library(entry_name: str) -> !:
    try note_library_module(entry_name)

func note_library_module(name: str) -> !:
    for known in library_modules[..<library_module_count]:
        if known == name:
            return
    if library_module_count >= library_modules.length:
        error(unsupported, "a program imports more than 1024 modules")
    library_modules[library_module_count] = name
    library_module_count += 1

## Whether `name` is library code: a standard module or any module the entry file
## imports. The backends keep a library's functions and storage only where
## the program reaches them, so importing a package costs nothing it does not use and
## an unused platform binding pulls in no native library.
pub func is_library_module(name: str) -> bool:
    if standard.is_module(name):
        return true
    for known in library_modules[..<library_module_count]:
        if same_module(known, name):
            return true
    return false

## Whether two module names agree, a dotted path matching its symbol form:
## `luce_std.files` is `luce_std_files` once lowered.
func same_module(a: str, b: str) -> bool:
    if a.length != b.length:
        return false
    var i: usize = 0
    while i < a.length:
        let x = a.bytes[i]
        let y = b.bytes[i]
        if x != y and not ((x == '.' and y == '_') or (x == '_' and y == '.')):
            return false
        i += 1
    return true

func is_comparison(op: str) -> bool:
    return op == "==" or op == "!=" or op == "<" or op == "<=" or op == ">" or op == ">="

## The ten element types a vector may have (§5.12), by name: `T[N](x)` with one of them is
## the broadcast form, not a call through an indexed value.
func is_lane_type_name(text: str) -> bool:
    return text == "i8" or text == "i16" or text == "i32" or text == "i64" or text == "u8" or text == "u16" or text == "u32" or text == "u64" or text == "f32" or text == "f64"

func is_arithmetic(op: str) -> bool:
    return op == "+" or op == "-" or op == "*" or op == "/" or op == "//" or op == "%" or op == "+%" or op == "-%" or op == "*%" or op == "+|" or op == "-|" or op == "*|" or op == "+?" or op == "-?" or op == "*?" or op == "&" or op == "|" or op == "^"

## What the arms of a `match` cover: `_`, an optional's two cases, `true` and `false`, an
## enum's cases as bits by declaration order, and the literals seen, for duplicates.
struct Coverage:
    var wildcard: bool
    var some: bool
    var none_: bool
    var truth: bool
    var falsity: bool
    var cases: u64

## Whether the literal pattern `p` of arm `a` repeats a literal pattern of an earlier arm
## of `m`, or of the same arm.
func literal_repeats(m: ast.Node*, a: ast.Node*, p: ast.Node*) -> bool:
    let v = p.left else return false
    if v.kind != ast.Kind.literal or p.right != none or v.text == "true" or v.text == "false":
        return false
    var arm = m.body
    while let earlier = arm:
        var pattern = earlier.left
        while let q = pattern:
            if q == p:
                return false
            if q.right == none:
                if let w = q.left:
                    if w.kind == ast.Kind.literal and w.text == v.text:
                        return true
            pattern = q.next
        arm = earlier.next
    return false

## The position of a case among its enum's cases, in declaration order.
func case_index(d: ast.Node*, case_decl: ast.Node*) -> usize:
    var index: usize = 0
    var cursor = d.body
    while let m = cursor:
        if m == case_decl:
            return index
        if m.kind == ast.Kind.enum_case:
            index += 1
        cursor = m.next
    return index

func case_count(d: ast.Node*) -> usize:
    var count: usize = 0
    var cursor = d.body
    while let m = cursor:
        if m.kind == ast.Kind.enum_case:
            count += 1
        cursor = m.next
    return count

## `luce.line`, `luce.file`, or `luce.function`: a fact of the use site (§6.4).
func is_luce_fact(e: ast.Node*) -> bool:
    if e.kind != ast.Kind.member:
        return false
    let owner = e.left else return false
    return owner.kind == ast.Kind.name and owner.text == "luce" and (e.text == "line" or e.text == "file" or e.text == "function" or e.text == "location")

## `-1`: unary minus on an integer literal.
func is_negative_literal(e: ast.Node*) -> bool:
    if e.kind != ast.Kind.unary or e.text != "-":
        return false
    let inner = e.left else return false
    return inner.kind == ast.Kind.literal and not literals.is_float_literal(inner.text) and inner.text.bytes[0] >= '0' and inner.text.bytes[0] <= '9'

## Whether a type declaration holds a field (§10.1).
## The wrapping integer result of a constant binary operator, or `none` for an operator this
## evaluator does not fold or a division by zero.
func fold_binary(op: str, a: u64, b: u64) -> u64?:
    if op == "+" or op == "+%":
        return a +% b
    if op == "-" or op == "-%":
        return a -% b
    if op == "*" or op == "*%":
        return a *% b
    if op == "//":
        return (a // b) if b != 0 else none
    if op == "%":
        return (a % b) if b != 0 else none
    if op == "<<":
        return (a << b) if b < 64 else 0
    if op == ">>":
        return (a >> b) if b < 64 else 0
    if op == "&":
        return a & b
    if op == "|":
        return a | b
    if op == "^":
        return a ^ b
    return none

## Signed `//`, `%` and `>>` of two constants (§7.4): truncating division, the remainder's
## sign the dividend's, an arithmetic shift; none where the program would trap.
func fold_signed(op: str, a: i64, b: i64) -> u64?:
    if op == ">>":
        if b < 0:
            return none
        return (u64)(a >> (b if b < 63 else 63))
    if b == 0 or (b == -1 and (u64)a == 0x8000000000000000):
        return none
    if op == "//":
        return (u64)(a // b)
    if op == "%":
        return (u64)(a % b)
    return none

## Whether a checked `+`, `-` or `*` of two sixty-four-bit constants overflows.
func overflows_64(op: str, a: u64, b: u64, signed: bool) -> bool:
    if op == "+":
        let sum = a +% b
        if signed:
            return ((i64)a >= 0) == ((i64)b >= 0) and ((i64)sum >= 0) != ((i64)a >= 0)
        return sum < a
    if op == "-":
        let difference = a -% b
        if signed:
            return ((i64)a >= 0) != ((i64)b >= 0) and ((i64)difference >= 0) != ((i64)a >= 0)
        return b > a
    if op == "*":
        if a == 0 or b == 0:
            return false
        let product = a *% b
        if signed:
            if ((i64)a == -1 and b == 0x8000000000000000) or ((i64)b == -1 and a == 0x8000000000000000):
                return true
            return (i64)product // (i64)a != (i64)b
        return product // a != b
    return false

func compare_constants(op: str, a: u64, b: u64, signed: bool) -> bool?:
    if op == "==":
        return a == b
    if op == "!=":
        return a != b
    let sa = (i64)a
    let sb = (i64)b
    if op == "<":
        return (sa < sb) if signed else (a < b)
    if op == "<=":
        return (sa <= sb) if signed else (a <= b)
    if op == ">":
        return (sa > sb) if signed else (a > b)
    if op == ">=":
        return (sa >= sb) if signed else (a >= b)
    return none

## The method a witness table points at for requirement `name` of `d`: the hidden fallible
## thunk when the implementation is not fallible, else the implementation itself.
pub func witness_member(d: ast.Node*, name: str) -> ast.Node*?:
    var cursor = d.body
    while let m = cursor:
        if m.kind == ast.Kind.func_ and m.has(ast.flag_lambda) and m.text.length == name.length + 6 and ends_with_name(m.text, name):
            return m
        cursor = m.next
    return find_member(d, name, ast.Kind.func_)

func ends_with_name(text: str, name: str) -> bool:
    let t = text.bytes
    let n = name.bytes
    if t.length < n.length + 6:
        return false
    if (str)t[..<6] != "__wit_":
        return false
    return (str)t[6..] == name

## The `index`th argument's value of call `e`.
func argument_at(e: ast.Node*, index: usize) -> ast.Node*?:
    var i: usize = 0
    var cursor = e.body
    while let a = cursor:
        if i == index:
            return a.left
        i += 1
        cursor = a.next
    return none

## How strong a written `Ordering` case is: relaxed, then acquire and release, then
## acq_rel, then seq_cst; a non-literal ordering ranks as the weakest.
func ordering_rank(e: ast.Node*) -> u32:
    if e.kind != ast.Kind.case_value:
        return 0
    if e.text == "seq_cst":
        return 3
    if e.text == "acq_rel":
        return 2
    if e.text == "acquire" or e.text == "release":
        return 1
    return 0

## A call, alone or under `try`, `catch`, or parentheses (§7.9).
func is_call_statement(e: ast.Node*) -> bool:
    match e.kind:
        .call:
            return true
        .group, .catch_, .else_, .propagate:
            let inner = e.left else return false
            return is_call_statement(inner)
        .unary:
            let inner = e.left else return false
            return e.text == "try" and is_call_statement(inner)
        _:
            return false

func is_none_literal(e: ast.Node*) -> bool:
    return e.kind == ast.Kind.literal and e.text == "none"

## Whether a handler's every path ends in `recover`, `return`, `error`, `trap`, `break`, or
## `continue` (§11.4).
func handler_leaves(block: ast.Node*) -> bool:
    var cursor = block.body
    while let s = cursor:
        if handler_statement_leaves(s):
            return true
        cursor = s.next
    return false

func handler_statement_leaves(s: ast.Node*) -> bool:
    match s.kind:
        .recover_, .break_, .continue_:
            return true
        .if_:
            let then = s.body else return false
            let rest = s.right else return false
            if not handler_leaves(then):
                return false
            return handler_statement_leaves(rest) if rest.kind == ast.Kind.if_ else handler_leaves(rest)
        _:
            return prune.statement_leaves(s)

func has_field(d: ast.Node*) -> bool:
    var cursor = d.body
    while let m = cursor:
        if m.kind == ast.Kind.field:
            return true
        cursor = m.next
    return false

## `a.b.c` -> `c`.
func last_component(path: str) -> str:
    var start: usize = 0
    var i: usize = 0
    let b = path.bytes
    while i < b.length:
        if b[i] == '.':
            start = i + 1
        i += 1
    return (str)b[start..]

## `dir/name.lucb` -> `name`.
pub func module_name_of(path: str) -> str:
    return paths.stem(path)

## A module's name is spelled like any other name: a letter or `_`, then letters, digits,
## or `_` (§3.1, §16.1).
pub func is_identifier(name: str) -> bool:
    let b = name.bytes
    if b.length == 0:
        return false
    var i: usize = 0
    while i < b.length:
        let byte = b[i]
        let letter = (byte >= 'a' and byte <= 'z') or (byte >= 'A' and byte <= 'Z') or byte == '_'
        let digit = byte >= '0' and byte <= '9'
        if not letter and not (digit and i > 0):
            return false
        i += 1
    return true

## A list of one type argument, `id`.
func one_arg(id: u32) -> u32[]!:
    var one = try new u32[1] ---
    one[0] = id
    return one