radiance · Radiance self-hosting compiler

compiler/ lib/ examples/ std/ arch/ collections/ lang/ alloc/ ast/ gen/ il/ lower/ module/ parser/ resolver/ scanner/ alloc.rad 4.2 KiB ast.rad 22.6 KiB gen.rad 265 B il.rad 15.1 KiB lower.rad 258.3 KiB module.rad 14.1 KiB package.rad 1.4 KiB parser.rad 78.7 KiB resolver.rad 227.9 KiB scanner.rad 23.4 KiB sexpr.rad 7.0 KiB strings.rad 2.2 KiB sys/ arch.rad 65 B collections.rad 36 B fmt.rad 3.8 KiB intrinsics.rad 206 B io.rad 1.2 KiB lang.rad 222 B mem.rad 2.2 KiB sys.rad 167 B testing.rad 2.4 KiB tests.rad 11.6 KiB vec.rad 3.1 KiB std.rad 231 B scripts/ seed/ test/ vim/ .gitignore 353 B .gitsigners 112 B LICENSE 1.1 KiB Makefile 3.1 KiB README 2.5 KiB std.lib 987 B std.lib.test 252 B
lib/std/lang/ast.rad 22.6 KiB raw
//! Radiance AST modules.
pub mod printer;

use std::io;
use std::lang::alloc;

/// Maximum number of trait methods.
pub const MAX_TRAIT_METHODS: u32 = 8;

/// Maximum number of supertraits.
pub const MAX_SUPERTRAITS: u32 = 4;

/// Arena for all parser allocations.
///
/// Uses a bump allocator for both AST nodes and node pointer arrays.
pub record NodeArena {
    /// Bump allocator for all allocations.
    arena: alloc::Arena,
    /// Next node ID to assign. Incremented on each node allocation.
    nextId: u32,
}

/// Initialize a node arena backed by the given byte slice.
pub fn nodeArena(data: *mut [u8]) -> NodeArena {
    return NodeArena {
        arena: alloc::new(data),
        nextId: 0,
    };
}

/// Create an empty `*mut [*Node]` slice with the given capacity.
pub fn nodeSlice(arena: *mut NodeArena, capacity: u32) -> *mut [*Node] {
    if capacity == 0 {
        return &mut [];
    }
    let ptr = try! alloc::allocSlice(&mut arena.arena, @sizeOf(*Node), @alignOf(*Node), capacity);

    return @sliceOf(ptr.ptr as *mut *Node, 0, capacity);
}

/// Return an allocator backed by the node arena.
// TODO: Why do we need this?
pub fn nodeAllocator(arena: *mut NodeArena) -> alloc::Allocator {
    return alloc::arenaAllocator(&mut arena.arena);
}

/// Attribute bit set applied to declarations or fields.
pub union Attribute {
    /// Public visibility attribute.
    Pub = 0b1,
    /// Default implementation attribute.
    Default = 0b10,
    /// Extern linkage attribute.
    Extern = 0b100,
    /// Test-only declaration attribute.
    Test = 0b1000,
    /// Compiler intrinsic attribute.
    Intrinsic = 0b10000,
}

/// Ordered collection of attribute nodes applied to a declaration.
pub record Attributes {
    list: *mut [*Node],
}

/// Check if an attributes list contains an attribute.
pub fn attributesContains(self: *Attributes, attr: Attribute) -> bool {
    for node in self.list {
        if let case NodeValue::Attribute(a) = node.value; a == attr {
            return true;
        }
    }
    return false;
}

/// Check if an attribute set includes the given attribute.
pub fn hasAttribute(attrs: u32, attr: Attribute) -> bool {
    return (attrs & (attr as u32)) != 0;
}

/// Signedness of an integer type.
pub union Signedness {
    /// Signed, eg. `i8`.
    Signed,
    /// Unsigned, eg. `u32`.
    Unsigned,
}

/// Radix/base of a number.
pub union Radix {
    /// Binary literal (0b...).
    Binary,
    /// Decimal literal.
    Decimal,
    /// Hexadecimal literal (0x...).
    Hex,
}

/// Parsed integer literal metadata.
pub record IntLiteral {
    /// Raw characters that comprised the literal.
    text: *[u8],
    /// Absolute magnitude parsed from the literal.
    magnitude: u64,
    /// Radix used by the literal.
    radix: Radix,
    /// Whether the literal spelled an explicit sign.
    signed: bool,
    /// Whether the literal used a negative sign.
    negative: bool,
}

/// Binary operator kinds used in numeric expressions.
pub union BinaryOp {
    /// Addition (`+`).
    Add,
    /// Subtraction (`-`).
    Sub,
    /// Multiplication (`*`).
    Mul,
    /// Division (`/`).
    Div,
    /// Remainder (`%`).
    Mod,
    /// Bitwise AND (`&`).
    BitAnd,
    /// Bitwise OR (`|`).
    BitOr,
    /// Bitwise XOR (`^`).
    BitXor,
    /// Left shift (`<<`).
    Shl,
    /// Right shift (`>>`).
    Shr,

    /// Equality comparison (`==`).
    Eq,
    /// Inequality comparison (`!=`).
    Ne,
    /// Less-than comparison (`<`).
    Lt,
    /// Greater-than comparison (`>`).
    Gt,
    /// Less-than-or-equal comparison (`<=`).
    Lte,
    /// Greater-than-or-equal comparison (`>=`).
    Gte,

    /// Logical conjunction (`and`).
    And,
    /// Logical disjunction (`or`).
    Or,
    /// Logical exclusive disjunction (`xor`).
    Xor,
}

/// Unary operator kinds used in expressions.
pub union UnaryOp {
    /// Logical negation (`not`).
    Not,
    /// Arithmetic negation (`-`).
    Neg,
    /// Bitwise NOT (`~`).
    BitNot,
}

/// Builtin function kind.
pub union Builtin {
    /// Size of type in bytes (`@sizeOf`).
    SizeOf,
    /// Alignment requirement of type (`@alignOf`).
    AlignOf,
    /// Construct a slice from pointer, length, and optional capacity (`@sliceOf`).
    SliceOf,
}

/// Source extent for a node measured in bytes.
pub record Span {
    /// Byte offset from the start of the source file.
    offset: u32,
    /// Length of the node in bytes.
    length: u32,
}

/// Type signature node.
pub union TypeSig {
    /// Absence of type.
    Void,
    /// Opaque type.
    Opaque,
    /// Boolean type.
    Bool,
    /// Integer type.
    Integer {
        /// Size of values, in bytes.
        width: u8,
        /// Signedness of values.
        sign: Signedness,
    },
    /// Fixed-size array type, eg. `[i32; 16]`.
    Array {
        /// Array element type.
        itemType: *Node,
        /// Expression that evaluates to the array length.
        length: *Node,
    },
    /// Slice type, eg. `*[i32]` or `*mut [i32]`.
    Slice {
        /// Slice element type.
        itemType: *Node,
        /// Whether the slice is mutable.
        mutable: bool,
    },
    /// Pointer, eg. `*i32` or `*mut i32`.
    Pointer {
        /// Pointer target type.
        valueType: *Node,
        /// Whether the pointer is mutable.
        mutable: bool,
    },
    /// Optional, eg. `?i32`.
    Optional {
        /// Underlying type.
        valueType: *Node,
    },
    /// Nominal type, points to identifier node.
    Nominal(*Node),
    /// Inline record type for union variant payloads.
    Record {
        /// Field declaration nodes.
        fields: *mut [*Node],
        /// Whether this record has labeled fields.
        labeled: bool,
    },
    /// Anonymous function type.
    Fn(FnSig),
    /// Trait object type, eg. `*opaque Allocator`.
    TraitObject {
        /// Trait name identifier.
        traitName: *Node,
        /// Whether the pointer is mutable.
        mutable: bool,
    },
}

/// Function signature.
pub record FnSig {
    /// Parameter type nodes in declaration order.
    params: *mut [*Node],
    /// Optional return type node.
    returnType: ?*Node,
    /// Throwable type nodes declared in the signature.
    throwList: *mut [*Node],
}

/// Address-of expression metadata.
pub record AddressOf {
    /// Target expression being referenced.
    target: *Node,
    /// Indicates whether the reference is mutable.
    mutable: bool,
}

/// Compound statement block with optional dedicated scope.
pub record Block {
    /// Statements that belong to this block.
    statements: *mut [*Node],
}

/// Function call expression.
pub record Call {
    /// Callee expression.
    callee: *Node,
    /// Argument expressions in source order.
    args: *mut [*Node],
}

/// Single argument to a function or record literal, optionally labeled.
pub record Arg {
    /// Optional label applied to the argument.
    label: ?*Node,
    /// Expression supplying the argument value.
    value: *Node,
}

/// Assignment expression connecting a target and value.
pub record Assign {
    /// Expression representing the assignment target.
    left: *Node,
    /// Expression providing the value being assigned.
    right: *Node,
}

/// While loop with an optional alternate branch.
pub record While {
    /// Condition evaluated before each iteration.
    condition: *Node,
    /// Loop body executed while `condition` is true.
    body: *Node,
    /// Optional branch executed when the condition is false at entry.
    elseBranch: ?*Node,
}

/// `while let` loop binding metadata.
pub record WhileLet {
    /// Pattern matching structure.
    pattern: PatternMatch,
    /// Loop body executed when the pattern matches.
    body: *Node,
    /// Optional branch executed when the match fails immediately.
    elseBranch: ?*Node,
}

/// Try expression metadata.
pub record Try {
    /// Expression evaluated with implicit error propagation.
    expr: *Node,
    /// Catch clauses. Empty for propagation (`try`), `try!`, or `try?`.
    catches: *mut [*Node],
    /// Whether the try should panic instead of returning an error.
    shouldPanic: bool,
    /// Whether the try should return an optional instead of propagating error.
    returnsOptional: bool,
}

/// A single catch clause in a `try ... catch` expression.
pub record CatchClause {
    /// Optional identifier binding for the error value (eg. `e`).
    binding: ?*Node,
    /// Optional type annotation after `as` (eg. `IoError`).
    typeNode: ?*Node,
    /// Block body executed when this clause matches.
    body: *Node,
}

/// `for` loop metadata.
pub record For {
    /// Loop variable binding.
    binding: *Node,
    /// Optional index binding for enumeration loops.
    index: ?*Node,
    /// Expression producing the iterable value.
    iterable: *Node,
    /// Body executed for each element.
    body: *Node,
    /// Optional branch executed when the loop body never runs.
    elseBranch: ?*Node,
}

/// Conditional `if` statement metadata.
pub record If {
    /// Condition controlling the branch.
    condition: *Node,
    /// Branch executed when `condition` is true.
    thenBranch: *Node,
    /// Optional branch executed when `condition` is false.
    elseBranch: ?*Node,
}

/// Conditional expression (`<true> if <condition> else <false>`).
pub record CondExpr {
    /// Condition controlling which branch is evaluated.
    condition: *Node,
    /// Expression evaluated when `condition` is true.
    thenExpr: *Node,
    /// Expression evaluated when `condition` is false.
    elseExpr: *Node,
}

/// Classification of pattern matches (if-let, while-let, let-else).
pub union PatternKind {
    /// Case pattern match.
    Case,
    /// Binding pattern match.
    Binding,
}

/// Prong arm.
pub union ProngArm {
    /// Case arm with pattern list.
    Case(*mut [*Node]),
    /// Binding arm with single identifier or placeholder.
    Binding(*Node),
    /// Else arm.
    Else,
}

/// Common pattern matching structure used by `if let`, `while let`, and `let-else`.
pub record PatternMatch {
    /// Pattern or binding to match against.
    pattern: *Node,
    /// Scrutinee expression to match against.
    scrutinee: *Node,
    /// Optional guard that must evaluate to `true`.
    guard: ?*Node,
    /// Whether this is a case pattern or binding.
    kind: PatternKind,
    /// Whether the binding is mutable.
    mutable: bool,
}

/// `if let` conditional binding metadata.
pub record IfLet {
    /// Pattern matching structure.
    pattern: PatternMatch,
    /// Branch executed when the pattern matches.
    thenBranch: *Node,
    /// Optional branch executed when the match fails.
    elseBranch: ?*Node,
}

/// `let-else` statement metadata.
pub record LetElse {
    /// Pattern matching structure.
    pattern: PatternMatch,
    /// Else branch executed if match fails (must diverge).
    elseBranch: *Node,
}

/// `match` statement metadata.
pub record Match {
    /// Expression whose value controls the match.
    subject: *Node,
    /// Prong nodes evaluated in order.
    prongs: *mut [*Node],
}

/// `match` prong metadata.
pub record MatchProng {
    /// Prong arm.
    arm: ProngArm,
    /// Optional guard that must evaluate to `true`.
    guard: ?*Node,
    /// Body executed when patterns match and guard passes.
    body: *Node,
}

/// `let` binding.
pub record Let {
    /// Identifier bound by the declaration.
    ident: *Node,
    /// Declared type annotation.
    type: ?*Node,
    /// Initializer expression.
    value: *Node,
    /// Storage alignment.
    alignment: ?*Node,
    /// Whether the variable is mutable.
    mutable: bool,
}

/// Constant declaration.
pub record ConstDecl {
    /// Identifier bound by the declaration.
    ident: *Node,
    /// Declared type annotation.
    type: *Node,
    /// Constant initializer expression.
    value: *Node,
    /// Optional attribute list applied to the constant.
    attrs: ?Attributes,
}

/// Static storage declaration.
pub record StaticDecl {
    /// Identifier bound by the declaration.
    ident: *Node,
    /// Declared storage type.
    type: *Node,
    /// Initialization expression.
    value: *Node,
    /// Optional attribute list applied to the static.
    attrs: ?Attributes,
}

/// Function parameter declaration.
pub record FnParam {
    /// Parameter identifier.
    name: *Node,
    /// Parameter type annotation.
    type: *Node,
}

/// Record literal expression metadata.
pub record RecordLit {
    /// Type name associated with the literal.
    /// If `nil`, it's an anonymous record literal.
    typeName: ?*Node,
    /// Field initializer nodes.
    fields: *mut [*Node],
    /// When true, remaining fields are discarded (`{ x, .. }`).
    ignoreRest: bool,
}

/// Record declaration.
pub record RecordDecl {
    /// Identifier naming the record.
    name: *Node,
    /// Field declaration nodes.
    fields: *mut [*Node],
    /// Optional attribute list applied to the record.
    attrs: ?Attributes,
    /// Trait derivations attached to the record.
    derives: *mut [*Node],
    /// Whether this record has labeled fields.
    labeled: bool,
}

/// Union declarations.
pub record UnionDecl {
    /// Identifier naming the union.
    name: *Node,
    /// Variant nodes making up the union.
    variants: *mut [*Node],
    /// Optional attribute list applied to the union.
    attrs: ?Attributes,
    /// Trait derivations attached to the union.
    derives: *mut [*Node],
}

/// Union variant declaration.
pub record UnionDeclVariant {
    /// Identifier naming the variant.
    name: *Node,
    /// Variant index.
    index: u32,
    /// Explicit discriminant value, if provided.
    value: ?*Node,
    /// Optional payload type.
    type: ?*Node,
}

/// Function declaration.
pub record FnDecl {
    /// Identifier naming the function.
    name: *Node,
    /// Function type signature.
    sig: FnSig,
    /// Optional function body (`nil` for extern functions).
    body: ?*Node,
    /// Optional attribute list applied to the function.
    attrs: ?Attributes,
}

/// Array repeat literal metadata.
pub record ArrayRepeatLit {
    /// Expression providing the repeated value.
    item: *Node,
    /// Expression providing the repetition count.
    count: *Node,
}

/// Module declaration.
pub record Mod {
    /// Identifier naming the module.
    name: *Node,
    /// Optional attribute list applied to the module.
    attrs: ?Attributes,
}

/// Use declaration for importing modules.
pub record Use {
    /// Access node identifying the imported module.
    path: *Node,
    /// Whether this is a wildcard import (e.g. `use ast::*`).
    wildcard: bool,
    /// Optional attribute list applied to the use declaration.
    attrs: ?Attributes,
}

/// Access expression used for field, scope, and index lookups.
pub record Access {
    /// Expression providing the container or namespace.
    parent: *Node,
    /// Expression identifying the member, scope element, or index.
    child: *Node,
}

/// `as` cast expression metadata.
pub record As {
    /// Expression being coerced.
    value: *Node,
    /// Target type annotation.
    type: *Node,
}

/// Range expression metadata.
pub record Range {
    /// Optional inclusive start expression.
    start: ?*Node,
    /// Optional exclusive end expression.
    end: ?*Node,
}

/// Binary operation expression, eg. `x * y`.
pub record BinOp {
    /// Operator applied to the operands.
    op: BinaryOp,
    /// Left-hand operand.
    left: *Node,
    /// Right-hand operand.
    right: *Node,
}

/// Unary operation expression, eg. `-x`.
pub record UnOp {
    /// Operator applied to the operand.
    op: UnaryOp,
    /// Operand expression.
    value: *Node,
}

/// Tagged union describing every possible AST node payload.
pub union NodeValue {
    /// Placeholder `_` expression.
    Placeholder,
    /// Nil literal (`nil`).
    Nil,
    /// Undefined literal (`undefined`).
    Undef,
    /// Boolean literal (`true` or `false`).
    Bool(bool),
    /// Character literal like `'x'`.
    Char(u8),
    /// String literal like `"Hello World!"`.
    String(*[u8]),
    /// Identifier expression.
    Ident(*[u8]),
    /// Numeric literal such as `42` or `0xFF`.
    Number(IntLiteral),
    /// Range expression such as `0..10` or `..`.
    Range(Range),
    /// Array literal expression.
    ArrayLit(*mut [*Node]),
    /// Array repeat literal expression.
    ArrayRepeatLit(ArrayRepeatLit),
    /// Array subscript expression.
    Subscript {
        /// Array or slice.
        container: *Node,
        /// Index expression.
        index: *Node
    },
    /// Binary operator expression.
    BinOp(BinOp),
    /// Unary operator expression.
    UnOp(UnOp),
    /// Builtin function call (e.g. `@sizeOf(T)`).
    BuiltinCall {
        /// Builtin function kind.
        kind: Builtin,
        /// Argument list.
        args: *mut [*Node],
    },
    /// Block expression or statement body.
    Block(Block),
    /// Call expression, eg. `f(x)`.
    Call(Call),
    /// Field access expression (e.g. `foo.bar`).
    FieldAccess(Access),
    /// Scope access expression (e.g. `foo::bar`).
    ScopeAccess(Access),
    /// Address of expression (e.g. `&mut x`).
    AddressOf(AddressOf),
    /// Dereference expression (e.g. `*ptr`).
    Deref(*Node),
    /// Cast expression using `as`.
    As(As),
    /// While loop statement.
    While(While),
    /// `while let` loop statement.
    WhileLet(WhileLet),
    /// `for` loop statement.
    For(For),
    /// Infinite loop statement.
    Loop {
        /// Body executed each iteration.
        body: *Node,
    },
    /// Break statement.
    Break,
    /// Continue statement.
    Continue,
    /// Return statement.
    Return {
        /// Expression returned by this statement, if any.
        value: ?*Node,
    },
    /// Throw statement.
    Throw {
        /// Expression to throw.
        expr: *Node,
    },
    /// Panic statement.
    Panic {
        /// Optional panic message expression.
        message: ?*Node,
    },
    /// Assert statement.
    Assert {
        /// Condition expression that must be true.
        condition: *Node,
        /// Optional assertion failure message.
        message: ?*Node,
    },
    /// Conditional statement.
    If(If),
    /// Conditional expression.
    CondExpr(CondExpr),
    /// `if let` conditional binding.
    IfLet(IfLet),
    /// `let-else` statement.
    LetElse(LetElse),
    /// Try expression.
    Try(Try),
    /// Match statement.
    Match(Match),
    /// Match prong.
    MatchProng(MatchProng),
    /// Function declaration.
    FnDecl(FnDecl),
    /// Function parameter declaration.
    FnParam(FnParam),
    /// `let binding.
    Let(Let),
    /// Constant declaration.
    ConstDecl(ConstDecl),
    /// Static storage declaration.
    StaticDecl(StaticDecl),
    /// Type signature node.
    TypeSig(TypeSig),
    /// Assignment expression.
    Assign(Assign),
    /// Expression statement.
    ExprStmt(*Node),
    /// Module declaration (`mod`).
    Mod(Mod),
    /// Parent module reference.
    Super,
    /// Module use declaration.
    Use(Use),
    /// Union type declaration.
    UnionDecl(UnionDecl),
    /// Union variant declaration.
    UnionDeclVariant(UnionDeclVariant),
    /// Attribute node.
    Attribute(Attribute),
    /// Record type declaration.
    RecordDecl(RecordDecl),
    /// Record field declaration.
    RecordField {
        /// Identifier bound by the declaration.
        field: ?*Node,
        /// Declared type annotation.
        type: *Node,
        /// Optional initializer expression.
        value: ?*Node,
    },
    /// Record literal expression.
    RecordLit(RecordLit),
    /// Record literal field initializer.
    RecordLitField(Arg),
    /// Alignment specifier.
    Align {
        /// Alignment value.
        value: *Node,
    },
    /// Catch clause within a try expression.
    CatchClause(CatchClause),
    /// Trait declaration.
    TraitDecl {
        /// Trait name identifier.
        name: *Node,
        /// Supertrait name nodes.
        supertraits: *mut [*Node],
        /// Method signature nodes ([`TraitMethodSig`]).
        methods: *mut [*Node],
        /// Optional attributes.
        attrs: ?Attributes,
    },
    /// Method signature inside a trait declaration.
    TraitMethodSig {
        /// Method name identifier.
        name: *Node,
        /// Receiver type node (eg. `*mut Allocator`).
        receiver: *Node,
        /// Function signature.
        sig: FnSig,
    },
    /// Instance block.
    InstanceDecl {
        /// Trait name identifier.
        traitName: *Node,
        /// Target type identifier.
        targetType: *Node,
        /// Method definition nodes ([`InstanceMethodDecl`]).
        methods: *mut [*Node],
    },
    /// Method definition inside an instance block.
    InstanceMethodDecl {
        /// Method name identifier.
        name: *Node,
        /// Receiver binding name ([`Ident`] node).
        receiverName: *Node,
        /// Receiver type node (eg. `*mut Arena`).
        receiverType: *Node,
        /// Function signature.
        sig: FnSig,
        /// Method body.
        body: *Node,
    },
}

/// Full AST node with shared metadata and variant-specific payload.
pub record Node {
    /// Unique identifier for this node.
    id: u32,
    /// Source span describing where the node originated.
    span: Span,
    /// Variant-specific payload for the node.
    value: NodeValue,
}

/// Allocate a new AST node from the arena with the given span and value.
pub fn allocNode(arena: *mut NodeArena, span: Span, value: NodeValue) -> *mut Node {
    let p = try! alloc::alloc(&mut arena.arena, @sizeOf(Node), @alignOf(Node));
    let node = p as *mut Node;
    let nodeId = arena.nextId;
    arena.nextId = nodeId + 1;

    *node = Node { id: nodeId, span, value };

    return node;
}

/// Allocate a synthetic AST node with a zero-length span.
pub fn synthNode(arena: *mut NodeArena, value: NodeValue) -> *mut Node {
    return allocNode(arena, Span { offset: 0, length: 0 }, value);
}

/// Synthetic module with a single function in it.
record SynthFnMod {
    /// The module block.
    modBody: *Node,
    /// The function block.
    fnBody: *Node
}

/// Synthesize a module with a function in it with the given name and statements.
pub fn synthFnModule(
    arena: *mut NodeArena, name: *[u8], bodyStmts: *mut [*Node]
) -> SynthFnMod {
    let a = nodeAllocator(arena);
    let fnName = synthNode(arena, NodeValue::Ident(name));
    let params: *mut [*Node] = &mut [];
    let throwList: *mut [*Node] = &mut [];
    let fnSig = FnSig { params, returnType: nil, throwList };
    let fnBody = synthNode(arena, NodeValue::Block(Block { statements: bodyStmts }));
    let fnDecl = synthNode(arena, NodeValue::FnDecl(FnDecl {
        name: fnName, sig: fnSig, body: fnBody, attrs: nil,
    }));
    let mut rootStmts: *mut [*Node] = &mut [];
    rootStmts.append(fnDecl, a);
    let modBody = synthNode(arena, NodeValue::Block(Block { statements: rootStmts }));

    return SynthFnMod { modBody, fnBody };
}