Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.43.0

0.43.0 / src / front / ast.lucb

#==============================================================================================
#
#   ast - The untyped syntax tree
#
#   DESCRIPTION:
#       One `Node` shape for every construct (base.md §21): a kind, a spelling, a span, four
#       child slots, and a sibling link for lists. Nodes come from the current allocator and
#       are never freed individually; a compilation's arena owns them. The checker writes what
#       it learns onto the same nodes, so there is one tree from parsing through emission.
#
#==============================================================================================

import io
import memory

## Every kind of node the parser and checker produce.
pub enum Kind as u8:
    module = 1
    import_ = 2
    from_import = 3
    func_ = 4
    struct_ = 5
    enum_ = 6
    union_ = 7
    interface_ = 8
    type_alias = 9
    constant = 10
    global = 11
    test_ = 12
    extern_func = 13
    extern_type = 14
    extern_var = 15
    extern_struct = 16
    extern_union = 17
    assert_ = 18
    asm_ = 19
    field = 20
    enum_case = 21
    param = 22
    generic_param = 23
    attribute = 24
    block = 30
    let_ = 31
    var_ = 32
    assign = 33
    if_ = 34
    while_ = 35
    for_ = 36
    match_ = 37
    match_arm = 38
    return_ = 39
    break_ = 40
    continue_ = 41
    defer_ = 42
    errdefer_ = 43
    recover_ = 44
    free_ = 45
    with_ = 46
    expr_stmt = 47
    name = 60
    self_ = 61
    literal = 62
    unary = 63
    binary = 64
    call = 65
    member = 66
    index = 67
    slice = 68
    tuple = 69
    array_lit = 70
    group = 71
    lambda = 72
    conditional = 73
    else_ = 74
    catch_ = 75
    cast = 76
    case_value = 77
    formatted = 78
    format_text = 79
    format_field = 80
    new_ = 81
    ## `new T[count] ---`: an allocation whose elements stay unwritten (§12.2).
    new_unwritten = 82
    span_make = 83
    match_expr = 84
    unit_ = 85
    type_ = 90
    pattern = 91
    argument = 92
    ## Checked propagation of one fallible operation, inserted before lowering.
    propagate = 93
    ## `extend Type:` in a fragment of the module that declares `Type`: methods of that type,
    ## moved into its declaration once the module is parsed (§9.5).
    extend_ = 94

# mark: Flags =================================================================================

## Flags on a node; which ones apply depends on the kind.
pub let flag_pub: u32 = 1
## A method that changes its receiver, found from its body (§9.5).
pub let flag_mutating: u32 = 2
## A `static` function of a type, which has no receiver; on a member, one reached through
## the type (§9.5).
pub let flag_static: u32 = 4
## An `export` declaration, with C linkage.
pub let flag_export: u32 = 8
## Set by the checker on a propagation (`propagate`) whose operand calls a function or method
## of another package by name: a failure it passes records the call as the error's
## `called_at` (§11.3). It shares its bit with `flag_export`, which only a declaration carries.
pub let flag_crossing: u32 = 8
## A `packed` struct.
pub let flag_packed: u32 = 16
## Set by the checker on a call of `assert` written in a test's own body, a lambda's
## excepted: a false condition fails the test rather than trapping (§16.5). It shares its
## bit with `flag_packed`, which only a struct carries.
pub let flag_test_assert: u32 = 16
## A `local` (thread-local) global.
pub let flag_thread_local: u32 = 32
## An uninitialised binding (`= ---`).
pub let flag_uninit: u32 = 64
## A `const` binding or pointee.
pub let flag_const: u32 = 128
## A `volatile` pointee.
pub let flag_volatile: u32 = 256
## An atomic type (`@T`).
pub let flag_atomic: u32 = 512
## An optional type (`T?`).
pub let flag_optional: u32 = 1024
## A fallible type or result (`T!`).
pub let flag_fallible: u32 = 2048
## A `for` element bound by pointer (§8.2).
pub let flag_by_pointer: u32 = 4096
## A `noalias` parameter.
pub let flag_noalias: u32 = 8192
## An `out` parameter, written by the callee.
pub let flag_out: u32 = 16384
## A `blocking` function or call.
pub let flag_blocking: u32 = 32768
## A variadic function.
pub let flag_variadic: u32 = 65536
## A pointer type node (`T*`).
pub let flag_star: u32 = 131072
## A span type node (`T[]`).
pub let flag_span: u32 = 262144
## An array type node (`T[N]`).
pub let flag_array: u32 = 524288
## A function type node.
pub let flag_func_type: u32 = 1048576
## A `void` marker.
pub let flag_void: u32 = 2097152
## A tuple type node.
pub let flag_tuple_type: u32 = 4194304
## An `if let` / `while let` binding form.
pub let flag_if_let: u32 = 8388608
## A `_` wildcard pattern.
pub let flag_wildcard: u32 = 16777216
## Set by the checker on a name that denotes a type rather than a value.
pub let flag_type_ref: u32 = 33554432
## Set by the checker on every declaration of a standard module: the backend
## maps these onto the runtime instead of emitting their placeholder bodies.
pub let flag_builtin: u32 = 67108864
## An expression whose value is, or aliases, the address of a local (§6.6).
pub let flag_local: u32 = 134217728
## An import that some name resolved through; an import without it is unused (§16.3).
pub let flag_referenced: u32 = 268435456
## A hidden function the checker made from a lambda (§9.6); it is not checked again.
pub let flag_lambda: u32 = 536870912
## A local no expression read: the block it is in prunes it (§19.6).
pub let flag_unused: u32 = 1073741824
## The sink of the formatted string being built (a name), the call that displays a field
## through it, and the field itself (§14.4).
pub let flag_format_sink: u32 = 2147483648

# mark: Nodes and lists =======================================================================
pub struct Node:
    ## What this node is.
    pub var kind: Kind
    ## The spelling that matters: a name, a literal, an operator, a label.
    pub var text: str
    ## The byte offset where the node's source begins.
    pub var start: usize
    ## The byte offset just past the node's source.
    pub var end: usize
    ## The one-based line the node begins on.
    pub var line: u32
    ## The `flag_*` bits set on this node.
    pub var flags: u32
    ## A child whose role depends on the kind: an operand, subject, or type.
    pub var left: Node*?
    ## A second child, by kind.
    pub var right: Node*?
    ## The node's body list: statements, members, or arguments, by kind.
    pub var body: Node*?
    ## A type or auxiliary child, by kind.
    pub var ty: Node*?
    ## The next node in a sibling list.
    pub var next: Node*?
    ## The attributes of §9.8 before a `func` or a top-level `var`: nodes named by the word,
    ## `section` carrying its name in `left`.
    pub var attrs: Node*?
    ## Written by the checker: the interned type id of this node (0 = none)
    ## and the declaration a name, call, or member resolved to.
    pub var type_id: u32
    ## The declaration a name, call, or member resolved to; `none` until the checker sets it.
    pub var resolved: Node*?

    ## A fresh node of `kind` spelling `text`, at `start` on `line`, with no children.
    pub static func make(kind: Kind, text: str, start: usize, line: u32) -> Node*!:
        return try new Node(kind = kind, text = text, start = start, end = start, line = line,
                            flags = 0, left = none, right = none, body = none, ty = none, next = none,
                            type_id = 0, resolved = none)

    ## A checked constructor call records the actual initializer on its node.
    pub func initializer() -> Node*?:
        let declaration = self.resolved else return none
        if declaration.kind == Kind.func_ and declaration.text == "init":
            return declaration
        return none

    ## Whether `flag` is set on this node.
    pub func has(flag: u32) -> bool:
        return (self.flags & flag) != 0

## Append `item` to the sibling list at `list`, keeping `tail` current so a
## long list costs nothing per append.
pub func append(list: Node*?*, tail: Node*?*, item: Node*):
    item.next = none
    if let last = *tail:
        last.next = item
    else:
        *list = item
    *tail = item

## The number of nodes in the sibling list at `list`.
pub func count(list: Node*?) -> usize:
    var n: usize = 0
    var cursor = list
    while let node = cursor:
        n += 1
        cursor = node.next
    return n

# mark: Dumping ===============================================================================

## The kind as it prints in a dump.
pub func kind_name(kind: Kind) -> str:
    match kind:
        .propagate: return "propagate"
        .extend_: return "extend"
        .module: return "module"
        .import_: return "import"
        .from_import: return "from_import"
        .func_: return "func"
        .struct_: return "struct"
        .enum_: return "enum"
        .union_: return "union"
        .interface_: return "interface"
        .type_alias: return "type_alias"
        .constant: return "constant"
        .global: return "global"
        .test_: return "test"
        .extern_func: return "extern_func"
        .extern_type: return "extern_type"
        .extern_var: return "extern_var"
        .extern_struct: return "extern_struct"
        .extern_union: return "extern_union"
        .assert_: return "assert"
        .asm_: return "asm"
        .field: return "field"
        .enum_case: return "enum_case"
        .param: return "param"
        .generic_param: return "generic_param"
        .attribute: return "attribute"
        .block: return "block"
        .let_: return "let"
        .var_: return "var"
        .assign: return "assign"
        .if_: return "if"
        .while_: return "while"
        .for_: return "for"
        .match_: return "match"
        .match_arm: return "arm"
        .return_: return "return"
        .break_: return "break"
        .continue_: return "continue"
        .defer_: return "defer"
        .errdefer_: return "errdefer"
        .recover_: return "recover"
        .free_: return "free"
        .with_: return "with"
        .expr_stmt: return "expr"
        .name: return "name"
        .self_: return "self"
        .literal: return "literal"
        .unary: return "unary"
        .binary: return "binary"
        .call: return "call"
        .member: return "member"
        .index: return "index"
        .slice: return "slice"
        .tuple: return "tuple"
        .array_lit: return "array"
        .group: return "group"
        .lambda: return "lambda"
        .conditional: return "conditional"
        .else_: return "else"
        .catch_: return "catch"
        .cast: return "cast"
        .case_value: return "case"
        .formatted: return "formatted"
        .format_text: return "format_text"
        .format_field: return "format_field"
        .new_: return "new"
        .new_unwritten: return "new_unwritten"
        .span_make: return "span_make"
        .match_expr: return "match_expr"
        .unit_: return "unit"
        .type_: return "type"
        .pattern: return "pattern"
        .argument: return "argument"
        _: return "?"

## Print `node` and everything under it as nested s-expressions.
pub func dump(out: io.Writer, node: Node*?, depth: u32) -> !:
    var cursor = node
    while let n = cursor:
        var i: u32 = 0
        while i < depth:
            try out.write("  ")
            i += 1
        try out.write("(")
        try out.write(kind_name(n.kind))
        if n.text.length > 0:
            try out.write(f" {n.text}")
        if n.flags != 0:
            try out.write(f" #{n.flags}")
        let children = n.left != none or n.right != none or n.body != none or n.ty != none
        if children:
            try out.write("\n")
            try dump(out, n.ty, depth + 1)
            try dump(out, n.left, depth + 1)
            try dump(out, n.right, depth + 1)
            try dump(out, n.body, depth + 1)
            i = 0
            while i < depth:
                try out.write("  ")
                i += 1
        try out.write(")\n")
        cursor = n.next

test "append keeps order and count":
    var backing: u8[1024]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var list: Node*? = none
        var tail: Node*? = none
        let a = try Node.make(Kind.name, "a", 0, 1)
        append(&list, &tail, a)
        let b = try Node.make(Kind.name, "b", 1, 1)
        append(&list, &tail, b)
        assert(count(list) == 2)
        assert(a.next != none)
        assert(b.next == none)

## Whether declaration `d` carries the attribute `word` of §9.8.
## Whether a function or global is `linked` (§9.8): its definition is in a library the
## program links, so the declaration carries no body and no initialiser.
pub func is_linked(d: Node*) -> bool:
    return has_attribute(d, "linked")

## Whether declaration `d` carries the attribute named `word` (§9.8).
pub func has_attribute(d: Node*, word: str) -> bool:
    var cursor = d.attrs
    while let a = cursor:
        if a.text == word:
            return true
        cursor = a.next
    return false