rucc_ast/

ast.rs

//! The arenas, and everything that hangs off them.
//!
//! Design: `spec/03-architecture.md` section 3.3 and `spec/06-lexer-and-parser.md` section 6.2.
//!
//! One [`Ast`] per translation unit owns every node in it. Nothing is boxed and nothing is
//! individually freed: the tree is a set of flat vectors, a reference between nodes is a
//! four-byte index, and the whole thing is dropped in one go when the unit is finished. That
//! removes the allocator from the parser's hot path, removes the destructor storm at the end,
//! and makes the tree `Send` without any effort.
//!
//! Spans are out of line, in a vector parallel to each arena. Almost nothing that walks the
//! tree reads a span, and keeping eight bytes of source position out of the node makes the
//! arrays that are walked half again as dense.
//!
//! # Reading and building
//!
//! Reading is indexing: `ast[id]` gives a node and `&ast[list]` gives a slice. Building is one
//! method per table, which is also what keeps the span vectors in step with the arenas they
//! belong to.
//!
//! There are twenty-eight tables, and the accessors for them are generated by two small macros
//! at the bottom of this file rather than written twenty-eight times. This is the only place in
//! the compiler that does that, and the reason is that the alternative is two hundred lines of
//! copy-paste in which indexing the wrong vector would compile, run, and give the wrong answer.

use std::fmt;
use std::ops::Index;

use rucc_base::{Idx, IdxRange, Symbol};
use rucc_diag::Span;
use rucc_lex::{CharConstant, FloatConstant, IntConstant, StringLiteral};

use crate::asm::{Asm, AsmId, AsmOperand};
use crate::attr::{AttrArg, Attribute};
use crate::decl::{
    Decl, DeclId, Declarator, DeclaratorId, Derived, Enumerator, InitDeclarator, Member, Param,
    TypeName, TypeNameId,
};
use crate::expr::{Expr, ExprId, GenericAssoc};
use crate::init::{Designator, Init, InitId, InitItem};
use crate::spec::{DeclSpecs, DeclSpecsId};
use crate::stmt::{Stmt, StmtId};

/// An integer constant, in the constant table.
pub type IntId = Idx<IntConstant>;
/// A floating constant, in the constant table.
pub type FloatId = Idx<FloatConstant>;
/// A character constant, in the constant table.
pub type CharId = Idx<CharConstant>;
/// A string literal, in the constant table.
pub type StrId = Idx<StringLiteral>;

/// The table of references to expressions, which is what a call's arguments are a run of.
#[derive(Debug)]
pub struct ExprRef;
/// The table of references to statements, which is what a compound statement is a run of.
#[derive(Debug)]
pub struct StmtRef;
/// The table of references to declarations.
#[derive(Debug)]
pub struct DeclRef;
/// The table of references to string literals, which is what an `asm` clobber list is a run of.
#[derive(Debug)]
pub struct StrRef;

/// A run of expressions.
pub type ExprList = IdxRange<ExprRef>;
/// A run of statements.
pub type StmtList = IdxRange<StmtRef>;
/// A run of declarations.
pub type DeclList = IdxRange<DeclRef>;
/// A run of string literals.
pub type StrList = IdxRange<StrRef>;
/// A run of identifiers.
pub type SymbolList = IdxRange<Symbol>;
/// A run of attributes.
pub type AttrList = IdxRange<Attribute>;
/// A run of attribute arguments.
pub type AttrArgList = IdxRange<AttrArg>;
/// A run of declarator derivations.
pub type DerivedList = IdxRange<Derived>;
/// A run of function parameters.
pub type ParamList = IdxRange<Param>;
/// A run of struct or union members.
pub type MemberList = IdxRange<Member>;
/// A run of enumerators.
pub type EnumeratorList = IdxRange<Enumerator>;
/// A run of init-declarators.
pub type InitDeclaratorList = IdxRange<InitDeclarator>;
/// A run of braced initializer elements.
pub type InitItemList = IdxRange<InitItem>;
/// A run of designators.
pub type DesignatorList = IdxRange<Designator>;
/// A run of `_Generic` associations.
pub type GenericList = IdxRange<GenericAssoc>;
/// A run of assembly operands.
pub type AsmOperandList = IdxRange<AsmOperand>;

/// Every node of one translation unit.
#[derive(Default)]
pub struct Ast {
    exprs: Vec<Expr>,
    expr_spans: Vec<Span>,
    stmts: Vec<Stmt>,
    stmt_spans: Vec<Span>,
    decls: Vec<Decl>,
    decl_spans: Vec<Span>,

    declarators: Vec<Declarator>,
    type_names: Vec<TypeName>,
    specs: Vec<DeclSpecs>,
    inits: Vec<Init>,
    asms: Vec<Asm>,

    ints: Vec<IntConstant>,
    floats: Vec<FloatConstant>,
    chars: Vec<CharConstant>,
    strings: Vec<StringLiteral>,

    expr_refs: Vec<ExprId>,
    stmt_refs: Vec<StmtId>,
    decl_refs: Vec<DeclId>,
    str_refs: Vec<StrId>,
    symbols: Vec<Symbol>,
    attrs: Vec<Attribute>,
    attr_args: Vec<AttrArg>,
    derived: Vec<Derived>,
    params: Vec<Param>,
    members: Vec<Member>,
    enumerators: Vec<Enumerator>,
    init_declarators: Vec<InitDeclarator>,
    init_items: Vec<InitItem>,
    designators: Vec<Designator>,
    generics: Vec<GenericAssoc>,
    asm_operands: Vec<AsmOperand>,

    top_level: Vec<DeclId>,
}

impl Ast {
    /// An empty tree.
    #[must_use]
    pub fn new() -> Ast {
        Ast::default()
    }

    /// The declarations of the translation unit, in source order.
    #[must_use]
    pub fn top_level(&self) -> &[DeclId] {
        &self.top_level
    }

    /// Adds a declaration at file scope.
    pub fn add_top_level(&mut self, decl: DeclId) {
        self.top_level.push(decl);
    }

    /// Adds an expression, with the source it came from.
    ///
    /// # Panics
    ///
    /// Panics if the arena would exceed four billion nodes, which is not a translation unit
    /// this compiler intends to accept.
    pub fn expr(&mut self, expr: Expr, span: Span) -> ExprId {
        let id = Idx::from_usize(self.exprs.len());
        self.exprs.push(expr);
        self.expr_spans.push(span);
        id
    }

    /// Adds a statement, with the source it came from.
    ///
    /// # Panics
    ///
    /// Panics if the arena would exceed four billion nodes.
    pub fn stmt(&mut self, stmt: Stmt, span: Span) -> StmtId {
        let id = Idx::from_usize(self.stmts.len());
        self.stmts.push(stmt);
        self.stmt_spans.push(span);
        id
    }

    /// Adds a declaration, with the source it came from.
    ///
    /// # Panics
    ///
    /// Panics if the arena would exceed four billion nodes.
    pub fn decl(&mut self, decl: Decl, span: Span) -> DeclId {
        let id = Idx::from_usize(self.decls.len());
        self.decls.push(decl);
        self.decl_spans.push(span);
        id
    }

    /// The source an expression came from.
    #[must_use]
    pub fn expr_span(&self, id: ExprId) -> Span {
        self.expr_spans[id.index()]
    }

    /// The source a statement came from.
    #[must_use]
    pub fn stmt_span(&self, id: StmtId) -> Span {
        self.stmt_spans[id.index()]
    }

    /// The source a declaration came from.
    #[must_use]
    pub fn decl_span(&self, id: DeclId) -> Span {
        self.decl_spans[id.index()]
    }

    /// How many expressions, statements and declarations the tree holds.
    ///
    /// The three numbers the size of a translation unit is usually quoted in, and what the
    /// `--emit=ast` header prints.
    #[must_use]
    pub fn counts(&self) -> Counts {
        Counts { exprs: self.exprs.len(), stmts: self.stmts.len(), decls: self.decls.len() }
    }

    /// Whether nothing has been parsed into this tree.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.exprs.is_empty() && self.stmts.is_empty() && self.decls.is_empty()
    }
}

/// How many nodes of each kind a tree holds.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Counts {
    /// Expressions.
    pub exprs: usize,
    /// Statements.
    pub stmts: usize,
    /// Declarations.
    pub decls: usize,
}

impl fmt::Debug for Ast {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // Printing a translation unit as a `{:?}` is never what anyone wanted from the tree,
        // and there is a printer for the case where they did. This reports the shape.
        let counts = self.counts();
        f.debug_struct("Ast")
            .field("exprs", &counts.exprs)
            .field("stmts", &counts.stmts)
            .field("decls", &counts.decls)
            .field("top_level", &self.top_level.len())
            .finish()
    }
}

/// Generates the read side of a table that holds one item per index.
macro_rules! node_table {
    ($id:ty => $item:ty, $field:ident) => {
        impl Index<$id> for Ast {
            type Output = $item;

            #[inline]
            fn index(&self, id: $id) -> &$item {
                &self.$field[id.index()]
            }
        }
    };
}

/// Generates both sides of a table that is read in runs: the builder that appends a run and
/// returns the range covering it, and the indexing that gives the run back.
macro_rules! list_table {
    (
        $(#[$doc:meta])*
        $add:ident, $list:ty => $item:ty, $field:ident
    ) => {
        impl Ast {
            $(#[$doc])*
            ///
            /// # Panics
            ///
            /// Panics if the table would exceed four billion entries.
            pub fn $add(&mut self, items: &[$item]) -> $list {
                let start = Idx::from_usize(self.$field.len());
                self.$field.extend_from_slice(items);
                let end = Idx::from_usize(self.$field.len());
                IdxRange::new(start, end)
            }
        }

        impl Index<$list> for Ast {
            type Output = [$item];

            #[inline]
            fn index(&self, list: $list) -> &[$item] {
                &self.$field[list.as_usize_range()]
            }
        }
    };
}

/// Generates both sides of a side table whose items are added one at a time.
macro_rules! side_table {
    (
        $(#[$doc:meta])*
        $add:ident, $id:ty => $item:ty, $field:ident
    ) => {
        impl Ast {
            $(#[$doc])*
            ///
            /// # Panics
            ///
            /// Panics if the table would exceed four billion entries.
            pub fn $add(&mut self, item: $item) -> $id {
                let id = Idx::from_usize(self.$field.len());
                self.$field.push(item);
                id
            }
        }

        node_table!($id => $item, $field);
    };
}

node_table!(ExprId => Expr, exprs);
node_table!(StmtId => Stmt, stmts);
node_table!(DeclId => Decl, decls);

side_table! {
    /// Adds a declarator.
    add_declarator, DeclaratorId => Declarator, declarators
}
side_table! {
    /// Adds a type name.
    add_type_name, TypeNameId => TypeName, type_names
}
side_table! {
    /// Adds a set of declaration specifiers.
    add_specs, DeclSpecsId => DeclSpecs, specs
}
side_table! {
    /// Adds an initializer.
    add_init, InitId => Init, inits
}
side_table! {
    /// Adds an assembly statement.
    add_asm, AsmId => Asm, asms
}
side_table! {
    /// Adds an integer constant.
    add_int, IntId => IntConstant, ints
}
side_table! {
    /// Adds a floating constant.
    add_float, FloatId => FloatConstant, floats
}
side_table! {
    /// Adds a character constant.
    add_char, CharId => CharConstant, chars
}
side_table! {
    /// Adds a string literal.
    add_string, StrId => StringLiteral, strings
}

list_table! {
    /// Adds a run of expressions, such as the arguments of a call.
    add_expr_list, ExprList => ExprId, expr_refs
}
list_table! {
    /// Adds a run of statements, such as the body of a compound statement.
    add_stmt_list, StmtList => StmtId, stmt_refs
}
list_table! {
    /// Adds a run of declarations, such as the parameter declarations of an old-style
    /// function definition.
    add_decl_list, DeclList => DeclId, decl_refs
}
list_table! {
    /// Adds a run of string literals, such as an `asm` clobber list.
    add_str_list, StrList => StrId, str_refs
}
list_table! {
    /// Adds a run of identifiers, such as the labels of an `asm goto`.
    add_symbol_list, SymbolList => Symbol, symbols
}
list_table! {
    /// Adds a run of attributes.
    add_attr_list, AttrList => Attribute, attrs
}
list_table! {
    /// Adds a run of attribute arguments.
    add_attr_args, AttrArgList => AttrArg, attr_args
}
list_table! {
    /// Adds a run of declarator derivations, from the name outward.
    add_derived_list, DerivedList => Derived, derived
}
list_table! {
    /// Adds a run of function parameters.
    add_param_list, ParamList => Param, params
}
list_table! {
    /// Adds a run of struct or union members.
    add_member_list, MemberList => Member, members
}
list_table! {
    /// Adds a run of enumerators.
    add_enumerator_list, EnumeratorList => Enumerator, enumerators
}
list_table! {
    /// Adds a run of init-declarators.
    add_init_declarator_list, InitDeclaratorList => InitDeclarator, init_declarators
}
list_table! {
    /// Adds a run of braced initializer elements.
    add_init_item_list, InitItemList => InitItem, init_items
}
list_table! {
    /// Adds a run of designators.
    add_designator_list, DesignatorList => Designator, designators
}
list_table! {
    /// Adds a run of `_Generic` associations.
    add_generic_list, GenericList => GenericAssoc, generics
}
list_table! {
    /// Adds a run of assembly operands.
    add_asm_operand_list, AsmOperandList => AsmOperand, asm_operands
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::expr::BinaryOp;

    fn span(lo: u32, hi: u32) -> Span {
        Span::new(lo, hi)
    }

    #[test]
    fn a_new_tree_is_empty() {
        let ast = Ast::new();
        assert!(ast.is_empty());
        assert!(ast.top_level().is_empty());
        assert_eq!(ast.counts(), Counts { exprs: 0, stmts: 0, decls: 0 });
    }

    #[test]
    fn nodes_come_back_by_index_and_spans_stay_beside_them() {
        let mut ast = Ast::new();
        let one = ast.expr(Expr::Nullptr, span(0, 7));
        let two = ast.expr(Expr::Bool(true), span(10, 14));
        let sum = ast.expr(Expr::Binary { op: BinaryOp::Add, lhs: one, rhs: two }, span(0, 14));

        assert_eq!(ast[one], Expr::Nullptr);
        assert_eq!(ast[two], Expr::Bool(true));
        assert_eq!(ast[sum], Expr::Binary { op: BinaryOp::Add, lhs: one, rhs: two });
        assert_eq!(ast.expr_span(one), span(0, 7));
        assert_eq!(ast.expr_span(sum), span(0, 14));
        assert_eq!(ast.counts().exprs, 3);
        assert!(!ast.is_empty());
    }

    #[test]
    fn a_run_comes_back_in_the_order_it_went_in() {
        let mut ast = Ast::new();
        let a = ast.expr(Expr::Nullptr, span(0, 1));
        let b = ast.expr(Expr::Bool(false), span(2, 3));
        let c = ast.expr(Expr::Bool(true), span(4, 5));
        let first = ast.add_expr_list(&[a, b]);
        let second = ast.add_expr_list(&[c]);

        assert_eq!(ast[first], [a, b]);
        assert_eq!(ast[second], [c]);
        assert_eq!(first.len(), 2);
    }

    #[test]
    fn an_empty_run_is_valid_before_anything_is_in_the_table() {
        let ast = Ast::new();
        assert!(ast[AttrList::EMPTY].is_empty());
        assert!(ast[DerivedList::EMPTY].is_empty());
        assert!(ast[ExprList::EMPTY].is_empty());
    }

    #[test]
    fn the_three_arenas_are_numbered_independently() {
        let mut ast = Ast::new();
        let e = ast.expr(Expr::Nullptr, span(0, 1));
        let s = ast.stmt(Stmt::Empty, span(0, 1));
        let d = ast.decl(Decl::Error, span(0, 1));
        assert_eq!(e.raw(), 0);
        assert_eq!(s.raw(), 0);
        assert_eq!(d.raw(), 0);
        assert_eq!(ast[s], Stmt::Empty);
        assert_eq!(ast[d], Decl::Error);
        assert_eq!(ast.stmt_span(s), span(0, 1));
        assert_eq!(ast.decl_span(d), span(0, 1));
    }

    #[test]
    fn debug_reports_the_shape_rather_than_the_tree() {
        let mut ast = Ast::new();
        let d = ast.decl(Decl::Error, span(0, 1));
        ast.add_top_level(d);
        let text = format!("{ast:?}");
        assert!(text.starts_with("Ast {"), "{text}");
        assert!(text.contains("decls: 1"), "{text}");
        assert!(text.contains("top_level: 1"), "{text}");
    }
}