tiny.smg.tree.runtime.subtree

1pub const subtree = @import("subtree.zig");

1const std = @import("std");2const runtime = @import("root.zig");34const abi = runtime.abi;5const language = runtime.language;6const lexer = runtime.lexer;7const scanner = @import("scanner.zig");89pub const Subtree = struct {10    symbol: abi.Symbol,11    children: []const *const Subtree,12    start: lexer.Position,13    end: lexer.Position,14    production_id: u16,15    dynamic_precedence: i32,16    parse_state: abi.State,17    visible_descendant_count: u32,18    named_descendant_count: u32,19    visible: bool,20    named: bool,21    extra: bool,22    scanner_state: ?scanner.State,23};2425pub const Tree = struct {26    allocator: std.mem.Allocator,27    arena: std.heap.ArenaAllocator,28    language: language.Language,29    root: *const Subtree,3031    pub fn init(allocator: std.mem.Allocator, lang: language.Language) !*Tree {32        const self = try allocator.create(Tree);33        self.* = .{34            .allocator = allocator,35            .arena = std.heap.ArenaAllocator.init(allocator),36            .language = lang,37            .root = undefined,38        };39        return self;40    }4142    pub fn deinit(self: *Tree) void {43        const allocator = self.allocator;44        self.arena.deinit();45        allocator.destroy(self);46    }4748    pub fn leaf(49        self: *Tree,50        symbol: abi.Symbol,51        start: lexer.Position,52        end: lexer.Position,53        parse_state: abi.State,54        extra: bool,55        scanner_state: ?scanner.State,56    ) !*const Subtree {57        const metadata = self.language.symbolMetadata(symbol);58        const result = try self.arena.allocator().create(Subtree);59        result.* = .{60            .symbol = symbol,61            .children = &.{},62            .start = start,63            .end = end,64            .production_id = 0,65            .dynamic_precedence = 0,66            .parse_state = parse_state,67            .visible_descendant_count = 0,68            .named_descendant_count = 0,69            .visible = metadata.visible,70            .named = metadata.named,71            .extra = extra,72            .scanner_state = scanner_state,73        };74        return result;75    }7677    pub fn node(78        self: *Tree,79        symbol: abi.Symbol,80        source_children: []const *const Subtree,81        production_id: u16,82        parse_state: abi.State,83        dynamic_precedence: i32,84        position: lexer.Position,85        extra: bool,86    ) !*const Subtree {87        const allocator = self.arena.allocator();88        const children = try allocator.dupe(*const Subtree, source_children);89        var total_precedence = dynamic_precedence;90        for (children) |child| total_precedence += child.dynamic_precedence;91        const descendant_counts = self.descendantCounts(children, production_id);92        const metadata = self.language.symbolMetadata(symbol);93        const result = try allocator.create(Subtree);94        result.* = .{95            .symbol = symbol,96            .children = children,97            .start = if (children.len == 0) position else children[0].start,98            .end = if (children.len == 0) position else children[children.len - 1].end,99            .production_id = production_id,100            .dynamic_precedence = total_precedence,101            .parse_state = parse_state,102            .visible_descendant_count = descendant_counts.visible,103            .named_descendant_count = descendant_counts.named,104            .visible = metadata.visible,105            .named = metadata.named,106            .extra = extra,107            .scanner_state = null,108        };109        return result;110    }111112    fn descendantCounts(self: *Tree, children: []const *const Subtree, production_id: u16) struct { visible: u32, named: u32 } {113        const aliases = self.language.aliases(production_id);114        var visible: u32 = 0;115        var named: u32 = 0;116        var structural_index: usize = 0;117        for (children) |child| {118            const alias_symbol = if (!child.extra and structural_index < aliases.len) aliases[structural_index] else 0;119            if (!child.extra) structural_index += 1;120            if (child.symbol != 0 and alias_symbol != 0) {121                visible +|= 1;122                named +|= @intFromBool(self.language.symbolMetadata(alias_symbol).named);123            } else if (child.visible) {124                visible +|= 1;125                named +|= @intFromBool(child.named);126            } else if (child.children.len > 0) {127                visible +|= child.visible_descendant_count;128                named +|= child.named_descendant_count;129            }130        }131        return .{ .visible = visible, .named = named };132    }133134    pub fn withExtra(self: *Tree, source: *const Subtree, extra: bool) !*const Subtree {135        if (source.extra == extra) return source;136        const result = try self.arena.allocator().create(Subtree);137        result.* = source.*;138        result.extra = extra;139        return result;140    }141142    pub fn withSpan(self: *Tree, source: *const Subtree, start: lexer.Position, end: lexer.Position) !*const Subtree {143        if (std.meta.eql(source.start, start) and std.meta.eql(source.end, end)) return source;144        const result = try self.arena.allocator().create(Subtree);145        result.* = source.*;146        result.start = start;147        result.end = end;148        return result;149    }150};151152pub fn order(allocator: std.mem.Allocator, left: *const Subtree, right: *const Subtree) !std.math.Order {153    const Pair = struct { left: *const Subtree, right: *const Subtree };154    var pending: std.ArrayList(Pair) = .empty;155    defer pending.deinit(allocator);156    try pending.append(allocator, .{ .left = left, .right = right });157    while (pending.pop()) |pair| {158        if (pair.left.symbol < pair.right.symbol) return .lt;159        if (pair.left.symbol > pair.right.symbol) return .gt;160        if (pair.left.children.len < pair.right.children.len) return .lt;161        if (pair.left.children.len > pair.right.children.len) return .gt;162        var index = pair.left.children.len;163        while (index > 0) {164            index -= 1;165            try pending.append(allocator, .{166                .left = pair.left.children[index],167                .right = pair.right.children[index],168            });169        }170    }171    return .eq;172}173174test "tree owns immutable source spans" {175    const raw = try std.testing.allocator.create(abi.Language);176    defer std.testing.allocator.destroy(raw);177    raw.* = std.mem.zeroes(abi.Language);178    raw.abi_version = 15;179    raw.lex_fn = testLex;180    var actions = [_]abi.ActionEntry{std.mem.zeroes(abi.ActionEntry)};181    raw.parse_actions = &actions;182    var metadata = [_]abi.SymbolMetadata{183        .{ .visible = false, .named = false, .supertype = false },184        .{ .visible = true, .named = true, .supertype = false },185    };186    raw.symbol_metadata = &metadata;187    const lang = try language.Language.init(raw);188    const tree = try Tree.init(std.testing.allocator, lang);189    defer tree.deinit();190    const leaf = try tree.leaf(1, .{ .byte = 2, .point = .{ .row = 0, .column = 2 } }, .{ .byte = 3, .point = .{ .row = 0, .column = 3 } }, 1, false, null);191    try std.testing.expectEqual(@as(u32, 2), leaf.start.byte);192    try std.testing.expect(leaf.visible);193    try std.testing.expectEqual(@as(u32, 0), leaf.visible_descendant_count);194}195196fn testLex(_: *abi.Lexer, _: abi.State) callconv(.c) bool {197    return false;198}