Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / sema / check / constants.lucb

#==============================================================================================
#
#   check/constants - Constants
#
#   DESCRIPTION:
#       What a constant or static initialiser may hold, and the constant values the checker
#       folds: integers, booleans, text, and conditions (§6.2).
#
#==============================================================================================
extend Checker:
    # mark: Constants ==========================================================================

    ## A constant expression (§6.4): literals; `sizeof`, `alignof`, `offsetof`, and the
    ## `luce` facts; operators and casts on constants; array, tuple, and struct literals of
    ## constants; enum cases; the address of a global or a function; top-level `let` names.
    func is_constant(e: ast.Node*) -> bool:
        match e.kind:
            .literal:
                return true
            .group:
                let inner = e.left else return false
                return self.is_constant(inner)
            .unary:
                let inner = e.left else return false
                if e.text == "&":
                    return self.global_place(inner)
                # a lane-wise operator runs (§5.12)
                return not self.table.is_vector(e.type_id) and self.is_constant(inner)
            .binary:
                let l = e.left else return false
                let r = e.right else return false
                return not self.table.is_vector(e.type_id) and self.is_constant(l) and self.is_constant(r)
            .cast:
                let inner = e.left else return false
                return self.is_constant(inner)
            .conditional:
                let cond = e.ty else return false
                let l = e.left else return false
                let r = e.right else return false
                return self.is_constant(cond) and self.is_constant(l) and self.is_constant(r)
            .array_lit, .tuple:
                return self.all_constant(e.body)
            .case_value:
                return self.all_constant(e.body)
            .name:
                let d = e.resolved else return false
                return (d.kind == ast.Kind.constant and not ast.is_linked(d)) or d.kind == ast.Kind.func_ or d.kind == ast.Kind.extern_func or d.kind == ast.Kind.enum_case
            .member:
                let owner = e.left else return false
                if owner.kind == ast.Kind.name and owner.text == "luce":
                    return true
                let d = e.resolved else return false
                return (d.kind == ast.Kind.constant and not ast.is_linked(d)) or d.kind == ast.Kind.enum_case or d.kind == ast.Kind.func_
            .call:
                let callee = e.left else return false
                if callee.kind == ast.Kind.name and callee.has(ast.flag_builtin) and (callee.text == "size_of" or callee.text == "align_of" or callee.text == "offset_of"):
                    return true
                # a struct construction or a payload case from constants; a static function
                # runs, so its result is not one
                if let f = callee.resolved:
                    if f.kind == ast.Kind.func_ or f.kind == ast.Kind.extern_func:
                        return false
                if callee.has(ast.flag_type_ref) or callee.has(ast.flag_static):
                    return self.constant_construction(e)
                return false
            _:
                return false

    ## Whether `id` is a struct with an `init` of its own.
    func has_own_init(id: u32) -> bool:
        let t = self.table.get(id)
        if t.kind != types.Kind.struct_:
            return false
        let d = t.decl else return false
        return find_member(d, "init", ast.Kind.func_) != none

    ## A construction `T(...)` or a payload case is constant when its arguments are. What it
    ## may run, a type's own `init` or a field default that calls, is allowed where the value
    ## is made at its use, a default argument or a top-level `let`; a global's storage needs
    ## a value it can hold from the start (`static_value`).
    func constant_construction(e: ast.Node*) -> bool:
        return self.all_constant(e.body)

    ## Whether a constant expression makes its value without running code, as a global's
    ## storage needs it before anything runs, on every thread for a `local var` (§6.3): no
    ## construction through a type's own `init`, none leaving out a field default that calls.
    pub func static_value(e: ast.Node*?) -> bool:
        let n = e else return true
        if n.kind == ast.Kind.call:
            if runs_init(n):
                return false
            if let callee = n.left:
                if callee.has(ast.flag_type_ref) and not self.defaults_are_static(n):
                    return false
            return self.static_items(n.body)
        if n.kind == ast.Kind.array_lit or n.kind == ast.Kind.tuple or n.kind == ast.Kind.case_value:
            return self.static_items(n.body)
        if n.kind == ast.Kind.name or n.kind == ast.Kind.member:
            # a top-level `let` whose own value runs code has no value before the program starts
            if let d = n.resolved:
                if d.kind == ast.Kind.constant and not ast.is_linked(d) and not self.static_value(d.left):
                    return false
            if n.kind == ast.Kind.name:
                return true
        if n.kind == ast.Kind.unary and n.text == "&":
            # an address is known before anything runs, whatever the storage will hold
            return true
        return self.static_value(n.left) and self.static_value(n.right) and self.static_value(n.ty)

    ## Every item of a list makes its value without running code (`static_value`).
    func static_items(items: ast.Node*?) -> bool:
        var cursor = items
        while let a = cursor:
            if not self.static_value(a.left if a.kind == ast.Kind.argument else a):
                return false
            cursor = a.next
        return true

    ## Every field default a construction leaves out is a constant that runs nothing.
    func defaults_are_static(e: ast.Node*) -> bool:
        let t = self.table.get(e.type_id)
        if t.kind != types.Kind.struct_:
            return true
        let d = t.decl else return true
        var positional: usize = 0
        var cursor = e.body
        while let a = cursor:
            if a.text.length == 0:
                positional += 1
            cursor = a.next
        var index: usize = 0
        var member = d.body
        while let f = member:
            if f.kind == ast.Kind.field:
                if let default = f.left:
                    if index >= positional and not named_in(e.body, f.text) and not (self.is_constant(default) and self.static_value(default)):
                        return false
                index += 1
            member = f.next
        return true

    ## Every item of a list is constant; an argument node wraps its expression, an array or
    ## tuple element is the expression itself.
    func all_constant(items: ast.Node*?) -> bool:
        var cursor = items
        while let a = cursor:
            if a.kind == ast.Kind.argument:
                let v = a.left else return false
                if not self.is_constant(v):
                    return false
            elif not self.is_constant(a):
                return false
            cursor = a.next
        return true

    ## A global, or an element or field of one reached by constant steps (§6.4).
    func global_place(e: ast.Node*) -> bool:
        match e.kind:
            .name:
                return names_a_global(e)
            .group:
                let inner = e.left else return false
                return self.global_place(inner)
            .index:
                let owner = e.left else return false
                let i = e.body else return false
                return self.global_place(owner) and self.is_constant(i)
            .member:
                let owner = e.left else return false
                let d = e.resolved else return false
                if d.kind == ast.Kind.global or d.kind == ast.Kind.extern_var or d.kind == ast.Kind.constant:
                    return true  # `module.global`
                return d.kind == ast.Kind.field and self.global_place(owner)
            _:
                return false

    ## Constant integer expression `e` as a value of `bits` bits, sign-extended when
    ## `signed`: only when it is built from literals, constants, casts, and operators whose
    ## result bits do not depend on signedness (`+ - * & | ^ << ~`, negation), since
    ## `constant_u64` computes in `u64`; none otherwise.
    pub func exact_integer(e: ast.Node*, bits: u64, signed: bool) -> i64?:
        if not sign_agnostic(e, 0):
            return none
        let v = self.constant_u64(e) else return none
        if bits >= 64:
            return (i64)v
        let mask = ((u64)1 << bits) - 1
        let low = v & mask
        if signed and (low >> (bits - 1)) != 0:
            return (i64)(low | ~mask)
        return (i64)low

    ## The value of a constant integer expression (§6.4), or `none` when it is not one this
    ## evaluator folds: literals, `sizeof`, `alignof`, constants, the cases of integer-backed
    ## enums, the arithmetic, bit, and shift operators, and casts.
    pub func constant_u64(e: ast.Node*) -> u64?:
        match e.kind:
            .literal:
                let v = literals.decode_integer(e.text) catch failure:
                    return none
                return v
            .group:
                let inner = e.left else return none
                return self.constant_u64(inner)
            .cast:
                # `(u8)-864` is 160, `(i8)200` is -56: the value converted to the cast's type
                let inner = e.left else return none
                let v = self.constant_u64(inner) else return none
                return self.converted_constant(v, e.type_id)
            .unary:
                let inner = e.left else return none
                let v = self.constant_u64(inner) else return none
                if e.text == "-" or e.text == "-%":
                    return 0 -% v
                if e.text == "~":
                    return ~v
                if e.text == "+":
                    return v
                return none
            .binary:
                let l = e.left else return none
                let r = e.right else return none
                let a = self.constant_u64(l) else return none
                let b = self.constant_u64(r) else return none
                return self.folded_in_type(e.text, a, b, e.type_id)
            .call:
                let callee = e.left else return none
                if callee.kind != ast.Kind.name or callee.resolved != none:
                    return none
                let arg = e.resolved else return none
                # `memory.size_of(T)` in a generic body is each instance's own, not a constant here
                if self.mentions_param(arg.type_id):
                    return none
                if callee.text == "size_of":
                    return self.table.size_of(arg.type_id)
                if callee.text == "align_of":
                    return self.table.align_of(arg.type_id)
                return none
            .name, .member:
                # a top-level `let`, this module's or an imported one's: `os.pointer_bits`;
                # or a case of an integer-backed enum, its declared value: `Id.last`
                let d = e.resolved else return none
                if d.kind != ast.Kind.constant and d.kind != ast.Kind.enum_case:
                    return none
                let init = d.left else return none
                return self.constant_u64(init)
            .conditional:
                # `6 if target.macos else 1`: the arm the constant condition picks
                let cond = e.ty else return none
                let l = e.left else return none
                let r = e.right else return none
                let truth = self.constant_bool(cond) else return none
                return self.constant_u64(l if truth else r)
            _:
                return none

    ## `a op b` folded as the program computes it in `ty` (§7.4): division, remainder and `>>`
    ## signed when the type is, the result truncated to the type's width, and nothing for a
    ## checked `+`, `-` or `*` that overflows it, which traps when it runs instead.
    func folded_in_type(op: str, a: u64, b: u64, ty: u32) -> u64?:
        if not self.table.is_integer(ty):
            return fold_binary(op, a, b)
        let signed = self.table.is_signed(ty)
        var raw: u64 = 0
        if signed and (op == "//" or op == "%" or op == ">>"):
            raw = fold_signed(op, (i64)a, (i64)b) else return none
        else:
            raw = fold_binary(op, a, b) else return none
        let out = self.converted_constant(raw, ty) else return none
        if op == "+" or op == "-" or op == "*":
            if out != raw or overflows_64(op, a, b, signed):
                return none
        return out

    ## A constant converted to an integer or `bool` type (§7.5): truncated to the width, then
    ## sign-extended when the type is signed, so the sixty-four-bit fold reads it back right.
    func converted_constant(v: u64, target: u32) -> u64?:
        if target == types.bool_id:
            return 1 if v != 0 else 0
        if not self.table.is_integer(target):
            return none
        let bits = self.table.bits(target)
        if bits >= 64:
            return v
        let mask = ((u64)1 << bits) - 1
        var out = v & mask
        if self.table.is_signed(target) and (out >> (bits - 1)) != 0:
            out |= ~mask
        return out

    ## The truth of a constant condition (§11.6): the literals, top-level `let`s of `bool`
    ## such as `os.arm64`, `not`, `and`, `or`, and comparisons of constant integers, signed
    ## when either operand's type is.
    pub func constant_bool(e: ast.Node*) -> bool?:
        match e.kind:
            .literal:
                if e.text == "true":
                    return true
                if e.text == "false":
                    return false
                return none
            .name, .member:
                let d = e.resolved else return none
                if d.kind != ast.Kind.constant:
                    return none
                let init = d.left else return none
                return self.constant_bool(init)
            .conditional:
                let cond = e.ty else return none
                let l = e.left else return none
                let r = e.right else return none
                let truth = self.constant_bool(cond) else return none
                return self.constant_bool(l if truth else r)
            .group:
                let inner = e.left else return none
                return self.constant_bool(inner)
            .unary:
                let inner = e.left else return none
                if e.text != "not":
                    return none
                let v = self.constant_bool(inner) else return none
                return not v
            .binary:
                let l = e.left else return none
                let r = e.right else return none
                if e.text == "and" or e.text == "or":
                    let a = self.constant_bool(l) else return none
                    # A known left operand can skip the right entirely. Never
                    # fold from the right alone: the left may have side effects.
                    if (e.text == "and" and not a) or (e.text == "or" and a):
                        return a
                    let b = self.constant_bool(r) else return none
                    return (a and b) if e.text == "and" else (a or b)
                let a = self.constant_u64(l) else return none
                let b = self.constant_u64(r) else return none
                let signed = self.table.is_signed(l.type_id) or self.table.is_signed(r.type_id)
                return compare_constants(e.text, a, b, signed)
            _:
                return none

    ## Whether `e` names storage a method may take the address of: a binding, `self`, an
    ## element, a dereference, a member of one of those, or a member reached through a
    ## pointer, `((T*)p).field`. An enum case or a call's result is a value.
    pub func is_place(e: ast.Node*) -> bool:
        match e.kind:
            .name, .self_, .index:
                return true
            .unary:
                return e.text == "*"
            .group:
                let inner = e.left else return false
                return self.is_place(inner)
            .member:
                if let d = e.resolved:
                    if d.kind == ast.Kind.enum_case:
                        return false
                let owner = e.left else return false
                if (e.text == "at" or e.text == "called_at") and owner.type_id == types.error_value_id:
                    return false  # where an error was raised is text made when it is read
                return self.is_place(owner) or self.table.kind(owner.type_id) == types.Kind.pointer
            _:
                return false

    ## The literal a constant expression stands for: a literal, a name or member of a
    ## constant whose initialiser stands for one, either behind parentheses or a conditional
    ## on a constant condition (`6 if os.macos else 1`); none for a computed initialiser,
    ## whose value the backends read from its global, since this evaluator is not
    ## sign-exact for arithmetic.
    pub func constant_leaf(e: ast.Node*) -> ast.Node*?:
        match e.kind:
            .literal:
                return e
            .group:
                let inner = e.left else return none
                return self.constant_leaf(inner)
            .name, .member:
                let d = e.resolved else return none
                if d.kind != ast.Kind.constant:
                    return none
                let init = d.left else return none
                return self.constant_leaf(init)
            .conditional:
                let cond = e.ty else return none
                let l = e.left else return none
                let r = e.right else return none
                let truth = self.constant_bool(cond) else return none
                return self.constant_leaf(l if truth else r)
            _:
                return none

    ## The text a constant `str` expression denotes: a literal, or a top-level `let` of one,
    ## `os.name`; none for anything else.
    pub func constant_text(e: ast.Node*) -> str?:
        match e.kind:
            .literal:
                if e.text.bytes[0] != '"':
                    return none
                return literals.decode_text(e.text)
            .group:
                let inner = e.left else return none
                return self.constant_text(inner)
            .name, .member:
                let d = e.resolved else return none
                if d.kind != ast.Kind.constant:
                    return none
                let init = d.left else return none
                return self.constant_text(init)
            .conditional:
                let cond = e.ty else return none
                let l = e.left else return none
                let r = e.right else return none
                let truth = self.constant_bool(cond) else return none
                return self.constant_text(l if truth else r)
            _:
                return none

    ## A condition that is a constant but not a literal, `if os.arm64:`, becomes the literal
    ## it stands for, so the branch it rules out is pruned; the program meant it, so no
    ## warning follows. Says whether it folded one.
    func fold_condition(s: ast.Node*) -> bool!:
        let cond = s.left else return false
        if cond.kind == ast.Kind.literal:
            return false
        let truth = self.constant_bool(cond) else return false
        let folded = try ast.Node.make(ast.Kind.literal, "true" if truth else "false", cond.start, cond.line)
        folded.type_id = types.bool_id
        s.left = folded
        return true

    ## A top-level constant typed on first use, so order does not matter.
    func check_constant(d: ast.Node*) -> !:
        if ast.is_linked(d):
            # the library defines the value; its type is what the program knows, and the
            # value, when the interface carries it, is checked but never stored (§9.8)
            let t = d.ty else return try self.fail(d, "a `linked` constant names its type (§9.8)")
            d.type_id = try self.resolve_type(t)
            if let value = d.left:
                let saved_top = self.at_top_level
                self.at_top_level = true
                _ = try self.expect(value, d.type_id)
                self.at_top_level = saved_top
            try self.rebind(d.text, d.type_id)
            return
        let init = d.left else return try self.fail(d, "a constant needs a value")
        if d.type_id == types.error_id:
            try self.fail(d, "this constant depends on itself")
        d.type_id = types.error_id
        let saved_top = self.at_top_level
        self.at_top_level = true
        var declared = types.none_id
        if let t = d.ty:
            declared = try self.resolve_type(t)
        let got = try self.expect(init, declared)
        self.at_top_level = saved_top
        if not self.is_constant(init):
            try self.fail(init, "a top-level `let` needs a constant expression (§6.4)")
        d.type_id = declared if declared != types.none_id else try self.settle(init, got)
        if d.type_id == types.none_id:
            try self.fail(d, "`none` needs a type")
        try self.rebind(d.text, d.type_id)

    ## The function a checked top-level `let` names, `pub let add = lib.add` or `let add = sum`:
    ## the function under another name (§9.4), so a use of the constant resolves to the
    ## function and a call through it takes the function's defaults and named arguments. None
    ## for any other constant, and for one whose declared type differs from the function's.
    pub func function_alias(d: ast.Node*) -> ast.Node*?:
        if d.kind != ast.Kind.constant or ast.is_linked(d):
            return none
        let init = d.left else return none
        let target = init.resolved else return none
        if target.kind != ast.Kind.func_ and target.kind != ast.Kind.extern_func:
            return none
        if generic_params_of(target) != none or d.type_id != target.type_id:
            return none
        if init.kind == ast.Kind.name:
            return target
        # `module.name`: a free function; a type's static method needs its type to call it
        if init.kind == ast.Kind.member:
            let owner = init.left else return none
            if self.table.kind(owner.type_id) == types.Kind.module:
                return target
        return none

## Whether `e` constructs a value through its type's own `init`.
func runs_init(e: ast.Node*) -> bool:
    if e.kind != ast.Kind.call:
        return false
    let own = e.resolved else return false
    return own.kind == ast.Kind.func_ and own.text == "init"

## `&global` and a function name are constant addresses (§6.4).
func names_a_global(e: ast.Node*) -> bool:
    if e.kind != ast.Kind.name:
        return false
    let d = e.resolved else return false
    return d.kind == ast.Kind.global or d.kind == ast.Kind.extern_var or d.kind == ast.Kind.constant or d.kind == ast.Kind.func_