Astra Engine

Appearance

AST Design ​

AXSLC uses an unconventional but highly efficient AST representation.

Flat Array with Integer IDs ​

The AST is not a tree of heap-allocated node pointers. It is a flat std::vector<ASTNode>, and all cross-references between nodes use NodeID - a uint32_t index into that vector.

cpp
using NodeID = uint32_t;

struct ASTNode {
    NodeID         id;
    SourceLocation location;
    TypeRef        type;      // unused by default
    ASTNodeData    data;      // std::variant<LiteralExpr, BinaryExpr, ...>
};

Traditional Tree vs Flat Array ​

Node Reference by Index ​

This represents the expression: 5 + (10 * x)

Benefits ​

This design has several advantages:

No Heap Allocation Per Node ​

The vector may reallocate, but all references are stable indices, not pointers. No need to manage individual node lifetimes.

Trivial Serialization ​

ASTs from included files can be merged by simply appending vectors and rebasing indices.

High Memory Locality ​

Sequential traversal benefits from cache coherency since nodes are stored contiguously.

Simple Merging ​

The visit_offset() pattern makes AST composition straightforward.

Trade-offs ​

No Compile-Time Safety ​

Accessing m_nodes[id] and then std::get-ing the wrong variant type is a runtime error, not a compile-time error.

No Parent Pointers ​

Traversal is always top-down from a known root ID. You can't navigate upward in the tree.

Node Types ​

All possible node payloads are described by ASTNodeData, a std::variant of 33 types:

Expressions ​

LiteralExpr, IdentifierExpr, UnresolvedRef, BinaryExpr, UnaryExpr, TernaryExpr, CallExpr, IndexExpr, FieldExpr, ConstructExpr, AssignExpr

Statements ​

BlockStmt, IfStmt, ForStmt, WhileStmt, ReturnStmt, ExprStmt, DeclStmt, BreakStmt, ContinueStmt, DiscardStmt

Declarations ​

VarDecl, ParamDecl, FuncDecl, StructDecl, FieldDecl, UniformDecl, BufferDecl, InterfaceDecl, InterfaceBlock, InterfaceRef

Top-level ​

StageBlock, Program

The visit_offset() Pattern ​

Every node type implements a visit_offset(NodeID off) method. It increments all child NodeID fields by off. This is used during include merging:

When an included file's parsed nodes are appended to the main node vector at offset N, all NodeIDs inside those nodes must be bumped by N so they continue to point to the correct entries.

cpp
static void offset_node_ids(std::vector<ASTNode> &nodes, NodeID offset) {
    for (auto &node : nodes) {
        node.id += offset;
        std::visit([offset](auto &d) { d.visit_offset(offset); }, node.data);
    }
}

Leaf nodes (nodes with no child NodeIDs) implement visit_offset as a no-op.

Include Merging Example ​

TypeRef ​

cpp
struct TypeRef {
    TokenKind kind;   // TokenKind::TypeVec3, TokenKind::Identifier, etc.
    std::string name; // only populated when kind == TokenKind::Identifier
};

For built-in types, kind holds the specific token kind and name is empty. For user-defined types (struct names), kind is TokenKind::Identifier and name holds the type string.

UnresolvedRef ​

During parsing, when the parser encounters a function call foo(...) where foo has not been declared yet, it initially emits an IdentifierExpr. At call-site disambiguation time (still in the parser), if foo is not in the declared set, the node is rewritten to UnresolvedRef{foo}.

The linker then validates all UnresolvedRef nodes against its final declared set. A reference that is still unresolved after link is an error.

Example Traversal ​

cpp
void print_expr(const std::vector<ASTNode>& nodes, NodeID id) {
    const auto& node = nodes[id];

    if (auto* bin = std::get_if<BinaryExpr>(&node.data)) {
        std::cout << "(";
        print_expr(nodes, bin->left);
        std::cout << " " << op_to_string(bin->op) << " ";
        print_expr(nodes, bin->right);
        std::cout << ")";
    } else if (auto* lit = std::get_if<LiteralExpr>(&node.data)) {
        std::cout << lit->value;
    }
    // ... handle other node types
}