Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.44.0

0.44.0 / src / sema / check / module.lucb

#==============================================================================================
#
#   check - Names, types, and effects
#
#   DESCRIPTION:
#       Turns parsed modules into a checked program (base.md §5–§17). Declarations are
#       collected first so forward references and recursion work, then every signature
#       and field type is resolved, then every body is checked. What the checker
#       learns is written onto the tree: `type_id` on every expression, type, and
#       declaration node; `resolved` on names, members, and calls.
#
#       Generic declarations are checked once against their written constraints with
#       opaque parameter types (§13). A use with concrete arguments substitutes them
#       into the signature; bodies are not re-checked per instance, which is what
#       declaration-time checking means. The standard modules come from `prelude`,
#       parsed and bound before the program's own modules, so `io.stdout()` and
#       `Writer` resolve like any other declaration.
#
#       A failing declaration is reported and the next is checked; the module's failures
#       are one error, a line each, with a `note:` line where a second site is named.
#
#       This fragment holds the `Checker` with its fields, diagnostics, and scopes; each
#       concern's methods are in a fragment of their own under `extend Checker:`, in the
#       order `ORDER` lists them (§16.1).
#
#==============================================================================================

import luce_std.paths
import c
import platform
import luce_std.files
import back.target as targets
import front.ast
import front.parser
import front.source
import front.token
import io
import memory
import sema.init_rules
import support.decimal
import strings
import support.literals
import numerals
import sema.standard as standard
import support.cache as cache
import sema.prune
import sema.name_index
import sema.types
import support.list
import support.hashed
from support.arena import Arena
import support.in_arena
import support.manifest
import support.modules as module_paths
## Reported when a name does not resolve (§15).
pub let unknown_name: ErrorCode = ErrorCode.package(9)
## Reported for a type mismatch or an ill-typed operation.
pub let type_error: ErrorCode = ErrorCode.package(10)
## Reported for a construct the target or backend does not support.
pub let unsupported: ErrorCode = ErrorCode.package(11)

# mark: Bindings and modules ==================================================================

## One name in scope: what it is, what type it has, whether it may change.
struct Binding:
    var name: str
    var type_id: u32
    var decl: ast.Node*?
    var mutable: bool
    var depth: u32
    ## Set when the binding was initialised from a local address, so a name that reads it
    ## carries the escape taint of §6.6.
    var from_local: bool
    ## The depth of the `catch` handler whose failure's message the binding views, when it
    ## views one: the view must not outlive that handler (§11.3); 0 for none.
    var handled: u32 = 0
    ## The import that made this name visible, so a use of the name marks the import.
    var origin: ast.Node*?
    ## Some expression read or assigned the name; a local nothing used is pruned (§19.6).
    var used: bool
    ## The binding of the same name this one hides, as its scope index plus one; 0 for none.
    var shadowed: u32 = 0

## A `catch` expression whose handler recovers a view of the message of the enclosing
## handler at `depth`.
struct RecoveredView:
    var at: ast.Node*
    var depth: u32

## Public package exports resolve to the canonical module which owns the type.
pub struct ModuleAlias:
    ## The exported module name.
    pub let name: str
    ## The canonical module the name resolves to.
    pub let target: str

## One module of the program: its tree, its source for positions, and whether
## the checker supplied it from the prelude.
pub struct Module:
    ## The module's name.
    pub var name: str
    ## Its parsed syntax tree.
    pub var tree: ast.Node*
    ## Its source, for diagnostic positions.
    pub var src: source.Source
    ## Whether the checker supplied it from the prelude.
    pub var is_prelude: bool
    ## Its canonical name, for package exports.
    pub var canonical: str = ""
    ## The package it belongs to.
    pub var package_name: str = ""
    ## Whether a test build runs its tests: it belongs to the package under test (§16.5).
    pub var tested: bool = false

## A top-level declaration's name within its module, the key of `Checker.module_decls`.
struct DeclName:
    var tree: usize
    var name: str

## A `Writer` over a caller's buffer, for spelling types into diagnostics.
struct SpanWriter: io.Writer:
    var data: u8[]
    var used: usize

    ## Copy `bytes` into the buffer up to its capacity; the number written.
    pub func write(bytes: const u8[]) -> usize!:
        var i: usize = 0
        while i < bytes.length and self.used < self.data.length:
            self.data[self.used] = bytes[i]
            self.used += 1
            i += 1
        return i

## `message` in `buffer`, or as much of it as fits, cut at a character and ending in `...`:
## a diagnostic quoting a long name or literal still says where it is. `buffer` holds at
## least the three dots.
func said(buffer: u8[], message: fmt) -> str:
    let text = strings.format(buffer, message) catch:
        # `format` kept the bytes that fit: the last three, from a character's start, go
        var end = buffer.length - 3
        while end > 0 and (buffer[end] & 0xC0) == 0x80:
            end -= 1
        for k in end..<end + 3:
            buffer[k] = '.'
        return (str)buffer[..<end + 3]
    return text

# mark: The checker ===========================================================================
pub struct Checker:
    ## Development debugging retains named locals after reporting unused bindings.
    pub var debug_locals: bool
    ## The program's type table.
    pub var table: types.Table
    ## Every module of the program.
    pub var modules: list.List[Module]
    var scope: list.List[Binding]
    ## Each name's innermost binding in `scope`, so a lookup walks one name's bindings.
    var names: name_index.NameIndex
    var depth: u32
    ## Diagnostics are formatted into the first half; type spellings into the second.
    ## The buffer outlives the arena, so the backends format their own reports here too.
    pub var scratch: u8[]
    ## The failures of the module being checked, one declaration's each, kept until the
    ## module's end reports them all (§19.6).
    pub var errors: list.List[str]
    ## The target of the build (§19.5): what the `target` module says and what the backends
    ## emit for.
    pub var build_target: targets.Target
    ## The package the program is built from, as `platform.program` gives it (§19.5).
    pub var program: str = "app"
    ## That package's version, as `platform.program_version` gives it.
    pub var program_version: str = ""
    ## The module being checked, as an index into `modules`.
    var current: usize
    ## How many of `modules`, from the first, are checked (`check_program`).
    var checked: usize = 0
    var current_func: ast.Node*?
    ## Whether the body being checked is a test's own, outside any lambda in it (§16.5).
    var in_test: bool = false
    ## The unwrapped result type of the function being checked, and whether it may fail.
    var result_type: u32
    var fallible: bool
    ## An expression marker or handler permits checked propagation in its operand.
    var expression_effect: bool = false
    ## The operand an `x else y` is checking: its own failure is the `else`'s to handle, so a
    ## surrounding `try` or `catch` does not propagate it (a call inside it still is;
    ## `else_handles`).
    var else_operand: ast.Node*? = none
    var effect_count: u64 = 0
    var self_type: u32
    var self_mutable: bool
    ## Inside `init`, where `let` fields take their first value.
    var in_init: bool
    var loop_depth: u32
    ## The labels of the loops open around the statement being checked (§8.5); deeper
    ## nesting is refused.
    var labels: str[16]
    var label_count: usize
    var in_catch: bool
    ## Inside a deferred block (§8.8), which nothing may leave: no `return`, no escaping failure.
    var in_defer: bool
    ## The member expression being checked is a call's callee: a method may stand there.
    var calling: bool
    var catch_result: u32
    ## The `catch` whose handler is being checked, and the depth of its failure's binding.
    var catch_node: ast.Node*? = none
    var catch_depth: u32 = 0
    ## The `catch` expressions whose handlers recover a view of an enclosing handler's
    ## message, so their value views it too (§11.3).
    var recovered_views: list.List[RecoveredView]
    ## Inside a generic declaration, where parameter types stand for themselves.
    var checking_template: bool
    ## Inside a top-level constant initialiser, where `ErrorCode.package` is allowed.
    var at_top_level: bool
    ## The `.indexed` member of the `for` iterable being checked: the one place `indexed()`
    ## may appear, since the loop walks the span by index and no pairs are made (§8.3).
    var indexed_iterable: ast.Node*? = none
    ## The `catch` whose value `_ =` drops: its handler may end without `recover` (§7.9).
    var dropped_catch: ast.Node*? = none
    ## Whether the `if` or `while` just checked had a constant condition that is not a
    ## literal, `if os.arm64:`: what it rules out goes silently, and so does what follows it
    ## when it always leaves, since the program meant it for the other targets (§19.6).
    var folded_quietly: bool = false
    ## The directory of the entry file; dotted imports resolve beneath it. A consumer that
    ## loads several modules from their packages (`describe-closure --modules`) sets it to
    ## each one's source root before loading it.
    pub var root: str
    ## Imports resolve under `root` alone and no manifest is read: a host's check of a
    ## directory it supplies (`load_sealed`, docs/EMBEDDING.md).
    pub var sealed: bool = false
    ## Whether this checker keeps package modules for later checks (`adopt`): no module it
    ## checks is the program's entry.
    var keeping: bool = false
    ## Where modules of other packages than the one checked are loaded, when a library keeps
    ## them for later checks (`embed.Library.check_file`, `adopt`); none loads them with
    ## the rest.
    pub var kept_in: Arena*? = none
    ## How many loads into `kept_in` began and did not finish: one that failed left part of
    ## a module there.
    pub var kept_open: usize = 0
    ## Imports on the active load path. Completed modules remain in dependency order;
    ## this separate stack detects cycles before recursive loading repeats a module.
    var loading: list.List[str]
    ## Package-export aliases from a name to its canonical module.
    pub var module_aliases: list.List[ModuleAlias]
    ## `luce-base test`: every module of the package under test, the entry's, is tested and
    ## takes the fragments its package keeps under `tests/` (§16.5).
    pub var test_build: bool = false
    ## The package of the entry under test, a module of which is tested too.
    var tested_package: str = ""
    ## `--package` on `test` or `check`: every module of the entry's package is loaded,
    ## checked and, in a test, tested, whether the entry imports it or not (§16.5).
    pub var whole_package: bool = false
    ## The entry, the module under test, by its index in `modules`.
    pub var entry_index: usize = 0
    ## The manifest's name (§16.4): the identity of the package's error codes (§11.3).
    pub var package_name: str
    ## Every `ErrorCode.package(n)` folded so far, with its package identity: no two alike.
    var package_codes: list.List[u64]
    ## Every symbol an `export` claimed: no two alike (§17.6).
    var export_symbols: list.List[str]
    ## The aliases whose types are being resolved, as node addresses: one met again names
    ## itself.
    var resolving: list.List[usize]
    ## Inside a lambda body, bindings below this index (the enclosing locals) are hidden:
    ## a lambda captures nothing (§9.6).
    var lambda_floor: usize
    ## The depth of the module's own scope: its declarations, imports, and the standard
    ## names; deeper bindings are a function's locals, which a lambda cannot see.
    var module_depth: u32 = 1
    var lambda_count: u32
    ## The warnings of the whole program, formatted with their positions (§19.6).
    pub var warnings: list.List[str]
    ## The module of each top-level declaration, by its address, indexed when first asked
    ## (`owner_of`); and how many of `modules` are indexed, since modules only join the end.
    var owners: hashed.Table[usize]
    var owners_indexed: usize = 0
    ## Each module's top-level declarations by name (`module_decl`), a module indexed
    ## when first asked: `module.name` was a walk of the module's declarations each time.
    var module_decls: hashed.Table[DeclName]
    var decl_nodes: list.List[ast.Node*]
    ## The module trees indexed so far, by address.
    var decls_indexed: hashed.Table[usize]
    ## The program's modules (not the prelude's) by canonical path: a module imported again
    ## is found here before its file is read again.
    var by_canonical: hashed.Table[str]
    ## The uses of this module's methods made before it was final whether they change
    ## their receiver, settled once its bodies are checked (§9.5).
    var pending_changes: list.List[PendingChange]
    ## What generic bodies call on values of their parameters they may not change, and
    ## which parameters they pass on, with the instantiations to settle against them
    ## (§13.1).
    var read_only_uses: list.List[ReadOnlyUse]
    var use_forwards: list.List[UseForward]
    var pending_instances: list.List[PendingInstance]
    ## The modules parsed ahead (`prefetch`), and their index by path; the paths of the
    ## modules loaded from files, in order, for the next build's list (`loaded_list`).
    var ahead: list.List[Ahead]
    var ahead_index: hashed.Table[str]
    var loaded_paths: list.List[str]

    ## A fresh checker; `scratch` is a buffer for formatting diagnostics.
    pub static func create(scratch: u8[]) -> Checker!:
        return Checker(table = try types.Table.create(), modules = try list.List[Module].create(16),
                       scope = try list.List[Binding].create(512), names = try name_index.NameIndex.create(), warnings = try list.List[str].create(16), errors = try list.List[str].create(16), depth = 0, scratch = scratch,
                       current = 0, current_func = none, result_type = types.unit_id, fallible = false,
                       self_type = types.none_id, self_mutable = false, in_init = false, loop_depth = 0, in_catch = false, in_defer = false,
                       catch_result = types.none_id, checking_template = false, at_top_level = false, root = "", loading = try list.List[str].create(16), module_aliases = try list.List[ModuleAlias].create(8), package_name = "app",
                       package_codes = try list.List[u64].create(64), export_symbols = try list.List[str].create(32), resolving = try list.List[usize].create(8),
                       owners = try hashed.Table[usize].create(256), build_target = targets.Target.host(),
                       module_decls = try hashed.Table[DeclName].create(1024), decl_nodes = try list.List[ast.Node*].create(1024),
                       decls_indexed = try hashed.Table[usize].create(64), by_canonical = try hashed.Table[str].create(256),
                       pending_changes = try list.List[PendingChange].create(16), read_only_uses = try list.List[ReadOnlyUse].create(16),
                       use_forwards = try list.List[UseForward].create(16), pending_instances = try list.List[PendingInstance].create(16),
                       recovered_views = try list.List[RecoveredView].create(4), ahead = try list.List[Ahead].create(0),
                       ahead_index = try hashed.Table[str].create(16), loaded_paths = try list.List[str].create(64))

    # -- diagnostics ----------------------------------------------------------------------

    ## Report `what` at `node` and stop; the message lives in the first half of `scratch`.
    func fail(node: ast.Node*, what: str) -> never!:
        let half = self.scratch.length // 2
        let (name, line, column) = self.located(node)
        let message = said(self.scratch[..<half], f"{name}:{line}:{column}: {what}")
        error(type_error, message)

    ## A failure with a second site: `note:` names it on a line of its own (§19.6).
    func fail_at(node: ast.Node*, what: str, other: ast.Node*, note: str) -> never!:
        let half = self.scratch.length // 2
        let (name, line, column) = self.located(node)
        let (other_name, other_line, other_column) = self.located(other)
        let message = said(self.scratch[..<half], f"{name}:{line}:{column}: {what}\n  note: {other_name}:{other_line}:{other_column}: {note}")
        error(type_error, message)

    ## The file, line, and column a node came from, in the module being checked.
    func located(node: ast.Node*) -> (str, u32, u32):
        if self.current < self.modules.count:
            return self.modules.get(self.current).src.located(node.start)
        return ("?", node.line, 0)

    ## A declaration's failure, copied out of the scratch buffer, for the module's report.
    func keep_error(message: str) -> !:
        var kept = try new u8[message.length if message.length > 0 else 1] ---
        memory.copy(kept, message.bytes, message.length)
        try self.errors.push((str)kept[..<message.length])

    ## Every kept failure, one per line, as the error the check answers with: joined in the
    ## scratch buffer, which outlives the arena the failures were kept in; what does not fit
    ## is counted on a last line.
    func all_errors() -> str!:
        var joined = self.scratch
        var at: usize = 0
        var shown: usize = 0
        for e in self.errors.span():
            let needed = e.length + (1 if at > 0 else 0)
            if at + needed + 40 > joined.length:
                break
            if at > 0:
                joined[at] = '\n'
                at += 1
            memory.copy(joined[at..], e.bytes, e.length)
            at += e.length
            shown += 1
        if shown < self.errors.count:
            let rest = try strings.format(joined[at..], f"\n  ... and {self.errors.count - shown} more")
            at += rest.length
        return (str)joined[..<at]

    ## The spelling of a type, kept in the current allocator.
    pub func spell(id: u32) -> str!:
        let text = try self.with_type("", id, "")
        var out = try new u8[text.length if text.length > 0 else 1] ---
        memory.copy(out, text.bytes, text.length)
        return (str)out[..<text.length]

    ## `prefix` + the spelling of a type + `suffix`, in the second half of `scratch`.
    func with_type(prefix: str, id: u32, suffix: str) -> str!:
        let half = self.scratch.length // 2
        var sink = SpanWriter(data = self.scratch[half..], used = 0)
        _ = try sink.write(prefix.bytes)
        try self.table.describe(&sink, id)
        _ = try sink.write(suffix.bytes)
        return (str)self.scratch[half..<half + sink.used]

    func mismatch(node: ast.Node*, expected: u32, got: u32) -> never!:
        let half = self.scratch.length // 2
        var sink = SpanWriter(data = self.scratch[half..], used = 0)
        _ = try sink.write("expected `".bytes)
        try self.table.describe(&sink, expected)
        if got == types.untyped_int_id or got == types.untyped_float_id:
            _ = try sink.write("`, got an integer literal".bytes if got == types.untyped_int_id else "`, got a float literal".bytes)
        else:
            _ = try sink.write("`, got `".bytes)
            try self.table.describe(&sink, got)
            _ = try sink.write("`".bytes)
            let e = self.table.get(expected)
            let g = self.table.get(got)
            if e.kind == types.Kind.span and not e.is_const and g.kind == types.Kind.array and self.same_pointee(g.elem, e.elem):
                # the elements agree: what is missing is a mutable place to view (§5.3)
                _ = try sink.write(": a span with mutable elements views a mutable array; a literal or a `let` makes a `const` span".bytes)
            if e.kind == types.Kind.atomic and self.table.kind(e.elem) == types.Kind.pointer and g.kind == types.Kind.pointer:
                # `@` covers the suffixes after it: `@u64*` is an atomic pointer (§15.1)
                let pointee = self.table.get(e.elem).elem
                _ = try sink.write(": `".bytes)
                try self.table.describe(&sink, expected)
                _ = try sink.write("` is an atomic pointer; a pointer to an atomic is written `(@".bytes)
                try self.table.describe(&sink, pointee)
                _ = try sink.write(")*`".bytes)
        return try self.fail(node, (str)self.scratch[half..<half + sink.used])

    # -- scopes ---------------------------------------------------------------------------

    func push_scope():
        self.depth += 1

    func pop_scope():
        while self.scope.count > 0 and self.scope.get(self.scope.count - 1).depth == self.depth:
            mark_if_unused(self.scope.get(self.scope.count - 1))
            self.drop_binding()
        self.depth -= 1

    ## Remove the innermost binding; the one it hid is its name's innermost again.
    func drop_binding():
        let b = self.scope.get(self.scope.count - 1)
        self.names.set(b.name, b.shadowed) catch failure:
            trap("the name index cannot shrink")
        self.scope.count -= 1

    ## Drop bindings until `count` remain.
    func truncate_scope(count: usize):
        while self.scope.count > count:
            self.drop_binding()

    ## Add a binding, the innermost of its name.
    func push_binding(b: Binding) -> !:
        var binding = b
        binding.shadowed = self.names.head(b.name)
        try self.scope.push(binding)
        try self.names.set(b.name, (u32)self.scope.count)

    ## The scope index of the innermost binding of `name` a lookup here may see, plus one;
    ## 0 when none. Inside a lambda, the enclosing function's locals are out of reach.
    func visible(name: str) -> u32:
        var at = self.names.head(name)
        while at > 0:
            let b = self.scope.get((usize)at - 1)
            if (usize)at - 1 < self.lambda_floor and b.depth > self.module_depth:
                at = b.shadowed
                continue
            return at
        return 0

    func lookup(name: str) -> Binding?:
        let at = self.visible(name)
        if at == 0:
            return none
        return self.scope.get((usize)at - 1)

    ## Bind `name` in the innermost scope. Base has no shadowing (§3.5): a local or a
    ## parameter may not reuse the name of another local, a parameter, an import, or a
    ## declaration of the module, and nothing may reuse a core name.
    func bind(at: ast.Node*, name: str, type_id: u32, decl: ast.Node*?, mutable: bool) -> !:
        # `_` is the wildcard (§3.4): it binds nothing, so it is never read and never
        # collides, however many loops or patterns nest it
        if name == "_":
            return
        if token.is_core_name(name) and not self.in_prelude():
            try self.fail(at, "this name belongs to the language")
        if let existing = self.lookup(name):
            if existing.origin != none and existing.depth < 2 and self.depth >= 2:
                try self.fail(at, "this name is an import; a local may not shadow it")
            elif let earlier = existing.decl:
                var text: u8[256]
                try self.fail_at(at, try strings.format(text, f"`{name}` is already in scope"), earlier, "the earlier binding")
            else:
                var text: u8[256]
                try self.fail(at, try strings.format(text, f"`{name}` is already in scope"))
        try self.push_binding(Binding(name = name, type_id = type_id, decl = decl, mutable = mutable, depth = self.depth, from_local = false, origin = none, used = false, shadowed = 0))

    ## The innermost binding of `name` was read or assigned (§19.6).
    func mark_used(name: str):
        let at = self.names.head(name)
        if at == 0:
            return
        var b = self.scope.get((usize)at - 1)
        b.used = true
        self.scope.set((usize)at - 1, b)

    ## The reporter for the module being checked.
    func reporter() -> prune.Reporter:
        let m = self.modules.get(self.current)
        return prune.Reporter(path = m.src.path, src = m.src, warnings = &self.warnings, silent = m.is_prelude, keep_locals = self.debug_locals and not m.is_prelude)

    ## The binding just made came through import `at`.
    func set_origin(at: ast.Node*):
        if self.scope.count == 0:
            return
        var b = self.scope.get(self.scope.count - 1)
        b.origin = at
        self.scope.set(self.scope.count - 1, b)

    ## The standard modules may spell core names (`c.char`, `c.int`).
    func in_prelude() -> bool:
        return self.current < self.modules.count and self.modules.get(self.current).is_prelude

    func rebind(name: str, type_id: u32) -> !:
        let at = self.names.head(name)
        if at == 0:
            return
        var b = self.scope.get((usize)at - 1)
        b.type_id = type_id
        self.scope.set((usize)at - 1, b)

## A name was used: the import it came through is referenced (§16.3).
func note_origin(b: Binding):
    if let o = b.origin:
        o.flags |= ast.flag_referenced