tiny.smg.tree.runtime.parser

1const std = @import("std");2const runtime = @import("root.zig");3const limits_mod = @import("../../limits/root.zig");45const abi = runtime.abi;6const language = runtime.language;7const lexer = runtime.lexer;8const scanner = runtime.scanner;9const selection = runtime.selection;10const stack = runtime.stack;11const subtree = runtime.subtree;1213const testing_limits = @import("../../root.zig").default_limits.parser;1415pub const Grammar = struct {16    raw: *const abi.Language,17    scanner_kind: scanner.Kind,18};1920pub const Options = struct {21    limits: limits_mod.Parser,22    operation_limit: ?usize = null,23    selection_trace: ?*selection.Trace = null,24};2526const Lookahead = struct {27    tree: *const subtree.Subtree,28    end: lexer.Position,29    scanner_after: scanner.State,30    fallback_symbol: ?abi.Symbol,31};3233const Candidate = struct {34    version: usize,35    branch: stack.Branch,36    lookahead: Lookahead,37};3839const Version = struct {40    id: usize,41    branch: stack.Branch,42};4344const AdvanceOutcome = union(enum) {45    replacement: Candidate,46    shifted: Version,47    done,48};4950pub fn parse(allocator: std.mem.Allocator, grammar: Grammar, source: []const u8, options: Options) !?*subtree.Tree {51    const lang = language.Language.init(grammar.raw) catch return null;52    const tree = try subtree.Tree.init(allocator, lang);53    errdefer tree.deinit();54    var stack_context = try stack.Context.init(allocator, options.limits);55    defer stack_context.deinit();5657    var active: std.ArrayList(Version) = .empty;58    defer deinitVersions(allocator, &active);59    try active.append(allocator, .{ .id = 0, .branch = stack.Branch.init(&stack_context, grammar.scanner_kind) });6061    var accepted: ?selection.Accepted = null;62    var operations: usize = 0;63    var next_version: usize = 1;64    const source_budget = std.math.mul(usize, source.len, 4096) catch std.math.maxInt(usize);65    const operation_limit = options.operation_limit orelse66        (std.math.add(usize, source_budget, 100_000) catch std.math.maxInt(usize));67    var last_position: usize = 0;6869    while (active.items.len > 0) {70        var shifted: std.ArrayList(Version) = .empty;71        errdefer deinitVersions(allocator, &shifted);72        var first_version = true;7374        while (active.items.len > 0) {75            var version = active.orderedRemove(0);76            while (true) {77                const lookahead = lex(tree, grammar, source, version.branch) catch |err| {78                    version.branch.deinit(allocator);79                    return err;80                } orelse {81                    version.branch.deinit(allocator);82                    break;83                };84                const advanced = try advance(85                    allocator,86                    &stack_context,87                    tree,88                    .{ .version = version.id, .branch = version.branch, .lookahead = lookahead },89                    &active,90                    &shifted,91                    &accepted,92                    options.selection_trace,93                    &operations,94                    operation_limit,95                    &next_version,96                ) orelse break;97                version = advanced;98                const position = version.branch.position.byte;99                if (position > last_position or (!first_version and position == last_position)) {100                    last_position = position;101                    shifted.append(allocator, version) catch |err| {102                        version.branch.deinit(allocator);103                        return err;104                    };105                    break;106                }107            }108            first_version = false;109        }110111        active.deinit(allocator);112        active = shifted;113        shifted = .empty;114        try compact(allocator, &stack_context, &active);115    }116117    if (accepted) |result| {118        tree.root = result.root;119        return tree;120    }121    tree.deinit();122    return null;123}124125fn lex(126    tree: *subtree.Tree,127    grammar: Grammar,128    source: []const u8,129    branch: stack.Branch,130) !?Lookahead {131    const lang = tree.language;132    const state = branch.state();133    const mode = lang.mode(state);134135    if (mode.external_lex_state != 0) {136        var external_lexer = lexer.Lexer.init(source, branch.position);137        external_lexer.start();138        var scanner_after = branch.scanner_state;139        if (scanner.scan(grammar.scanner_kind, &scanner_after, &external_lexer, lang.externalValid(mode.external_lex_state))) {140            const token = external_lexer.finish();141            if (token.symbol >= grammar.raw.external_token_count) return null;142            const symbol = grammar.raw.external_scanner.symbol_map.?[token.symbol];143            return .{144                .tree = try tree.leaf(symbol, token.start, token.end, state, false, scanner_after),145                .end = token.end,146                .scanner_after = scanner_after,147                .fallback_symbol = null,148            };149        }150    }151152    var internal_lexer = lexer.Lexer.init(source, branch.position);153    internal_lexer.start();154    if (!grammar.raw.lex_fn.?(&internal_lexer.abi, mode.lex_state)) return null;155156    const token = internal_lexer.finish();157    var symbol = token.symbol;158    var fallback_symbol: ?abi.Symbol = null;159    if (symbol != 0 and symbol == grammar.raw.keyword_capture_token) {160        if (grammar.raw.keyword_lex_fn) |keyword_lex_fn| {161            var keyword_lexer = lexer.Lexer.init(source, token.start);162            keyword_lexer.start();163            if (keyword_lex_fn(&keyword_lexer.abi, 0)) {164                const keyword = keyword_lexer.finish();165                if (keyword.end.byte == token.end.byte and (lang.hasActions(state, keyword.symbol) or lang.isReserved(mode, keyword.symbol))) {166                    fallback_symbol = symbol;167                    symbol = keyword.symbol;168                }169            }170        }171    }172173    return .{174        .tree = try tree.leaf(symbol, token.start, token.end, state, false, null),175        .end = token.end,176        .scanner_after = branch.scanner_state,177        .fallback_symbol = fallback_symbol,178    };179}180181fn advance(182    allocator: std.mem.Allocator,183    stack_context: *stack.Context,184    tree: *subtree.Tree,185    initial: Candidate,186    ready: *std.ArrayList(Version),187    shifted: *std.ArrayList(Version),188    accepted: *?selection.Accepted,189    selection_trace: ?*selection.Trace,190    operations: *usize,191    operation_limit: usize,192    next_version: *usize,193) !?Version {194    var candidate = initial;195    while (true) {196        if (operations.* >= operation_limit) {197            var exhausted = candidate.branch;198            exhausted.deinit(allocator);199            return error.OperationLimitExceeded;200        }201        operations.* += 1;202        const outcome = try expandCandidate(203            allocator,204            stack_context,205            tree,206            candidate,207            ready,208            shifted,209            accepted,210            selection_trace,211            next_version,212            .{ .operations = operations, .limit = operation_limit },213        );214        switch (outcome) {215            .replacement => |replacement| candidate = replacement,216            .shifted => |version| return version,217            .done => return null,218        }219    }220}221222fn expandCandidate(223    allocator: std.mem.Allocator,224    stack_context: *stack.Context,225    tree: *subtree.Tree,226    candidate: Candidate,227    ready: *std.ArrayList(Version),228    shifted: *std.ArrayList(Version),229    accepted: *?selection.Accepted,230    selection_trace: ?*selection.Trace,231    next_version: *usize,232    budget: stack.Budget,233) !AdvanceOutcome {234    var owned = candidate.branch;235    defer owned.deinit(allocator);236    var lookahead = candidate.lookahead;237    var entry = tree.language.entry(owned.state(), lookahead.tree.symbol);238    if (entry.actions.len == 0) {239        if (lookahead.fallback_symbol) |fallback| {240            if (!tree.language.isReserved(tree.language.mode(owned.state()), lookahead.tree.symbol)) {241                lookahead.tree = try tree.leaf(fallback, lookahead.tree.start, lookahead.tree.end, lookahead.tree.parse_state, false, null);242                lookahead.fallback_symbol = null;243                entry = tree.language.entry(owned.state(), fallback);244            }245        }246    }247    if (entry.actions.len == 0) return .done;248249    var replacement_version: ?usize = null;250    for (entry.actions) |action| {251        switch (@as(abi.ActionType, @fromBackingInt(@intCast(action.type)))) {252            .shift => {253                if (action.shift.repetition) continue;254                var fork = try owned.clone(allocator);255                errdefer fork.deinit(allocator);256                const shifted_tree = try tree.withExtra(lookahead.tree, action.shift.extra);257                const next_state = if (action.shift.extra) fork.state() else action.shift.state;258                try fork.shift(stack_context, shifted_tree, next_state, lookahead.end, lookahead.scanner_after);259                return .{ .shifted = .{ .id = candidate.version, .branch = fork } };260            },261            .reduce => {262                var reductions: std.ArrayList(stack.Branch) = .empty;263                defer deinitBranches(allocator, &reductions);264                try owned.reduce(allocator, stack_context, tree, tree.language, action.reduce, &reductions, budget);265                var action_replacement: ?usize = null;266                for (reductions.items) |fork| {267                    const version = next_version.*;268                    next_version.* += 1;269                    const retained = try integrateReductionVersion(270                        allocator,271                        stack_context,272                        .{ .id = version, .branch = fork },273                        ready,274                        shifted,275                    );276                    if (retained and action_replacement == null) action_replacement = version;277                }278                if (action_replacement) |version| replacement_version = version;279            },280            .accept => {281                if (lookahead.tree.symbol != abi.end_symbol) continue;282                const structural_root = try owned.acceptedRoot(283                    allocator,284                    stack_context,285                    tree,286                    budget,287                ) orelse continue;288                const root = try tree.withSpan(289                    structural_root,290                    if (structural_root.start.byte == structural_root.end.byte) lookahead.end else structural_root.start,291                    lookahead.end,292                );293                try selection.consider(allocator, accepted, root, owned.precedence(), selection_trace);294                return .done;295            },296            .recover => return .done,297        }298    }299    if (replacement_version) |version| {300        const index = versionIndex(ready.items, version) orelse return .done;301        const replacement = ready.orderedRemove(index);302        return .{ .replacement = .{303            .version = candidate.version,304            .branch = replacement.branch,305            .lookahead = lookahead,306        } };307    }308    return .done;309}310311fn integrateReductionVersion(312    allocator: std.mem.Allocator,313    context: *stack.Context,314    version: Version,315    ready: *std.ArrayList(Version),316    shifted: *std.ArrayList(Version),317) !bool {318    const retained_count = std.math.add(319        usize,320        context.limits.active_version_count,321        context.limits.version_count_overflow,322    ) catch return error.CapacityOverflow;323    if (shifted.items.len + ready.items.len + 1 > retained_count) {324        var dropped = version.branch;325        dropped.deinit(allocator);326        return false;327    }328    for (shifted.items) |existing| {329        if (!version.branch.equivalent(existing.branch)) continue;330        _ = try context.merge(existing.branch.head, version.branch.head);331        var merged = version.branch;332        merged.deinit(allocator);333        return false;334    }335    for (ready.items) |existing| {336        if (!version.branch.equivalent(existing.branch)) continue;337        _ = try context.merge(existing.branch.head, version.branch.head);338        var merged = version.branch;339        merged.deinit(allocator);340        return false;341    }342    ready.append(allocator, version) catch |err| {343        var failed = version.branch;344        failed.deinit(allocator);345        return err;346    };347    return true;348}349350fn versionIndex(versions: []const Version, id: usize) ?usize {351    for (versions, 0..) |version, index| if (version.id == id) return index;352    return null;353}354355fn compact(allocator: std.mem.Allocator, context: *stack.Context, versions: *std.ArrayList(Version)) !void {356    var index: usize = 0;357    while (index < versions.items.len) {358        var other: usize = 0;359        var removed = false;360        while (other < index) : (other += 1) {361            if (!versions.items[index].branch.equivalent(versions.items[other].branch)) continue;362            _ = try context.merge(versions.items[other].branch.head, versions.items[index].branch.head);363            var merged = versions.orderedRemove(index);364            merged.branch.deinit(allocator);365            removed = true;366            break;367        }368        if (!removed) index += 1;369    }370371    var rank_index: usize = 1;372    while (rank_index < versions.items.len) : (rank_index += 1) {373        const current = versions.items[rank_index];374        var destination = rank_index;375        while (destination > 0 and current.branch.precedence() > versions.items[destination - 1].branch.precedence()) : (destination -= 1) {376            versions.items[destination] = versions.items[destination - 1];377        }378        versions.items[destination] = current;379    }380    while (versions.items.len > context.limits.active_version_count) {381        var discarded = versions.orderedRemove(context.limits.active_version_count);382        discarded.branch.deinit(allocator);383    }384}385386fn deinitBranches(allocator: std.mem.Allocator, branches: *std.ArrayList(stack.Branch)) void {387    for (branches.items) |*branch| branch.deinit(allocator);388    branches.deinit(allocator);389    branches.* = .empty;390}391392fn deinitVersions(allocator: std.mem.Allocator, versions: *std.ArrayList(Version)) void {393    for (versions.items) |*version| version.branch.deinit(allocator);394    versions.deinit(allocator);395    versions.* = .empty;396}397398extern fn tree_sitter_zig() callconv(.c) *const abi.Language;399400test "focused operation exhaustion is a resource error" {401    const grammar = Grammar{ .raw = tree_sitter_zig(), .scanner_kind = .zig };402    try std.testing.expectError(403        error.OperationLimitExceeded,404        parse(std.testing.allocator, grammar, "const value = 1;", .{ .limits = testing_limits, .operation_limit = 0 }),405    );406}407408test "focused ambiguous parse propagates every allocation failure" {409    try std.testing.checkAllAllocationFailures(410        std.testing.allocator,411        checkAmbiguousParseAllocationFailures,412        .{testing_limits},413    );414}415416fn checkAmbiguousParseAllocationFailures(allocator: std.mem.Allocator, limits: limits_mod.Parser) !void {417    const grammar = Grammar{ .raw = tree_sitter_zig(), .scanner_kind = .zig };418    const result = try parse(419        allocator,420        grammar,421        "const order_fn: ?*const fn (*anyopaque, *anyopaque) std.math.Order = null;",422        .{ .limits = limits },423    );424    const tree = result orelse return error.UnexpectedInvalidTree;425    defer tree.deinit();426}427428test "focused equal-precedence active version compaction retains the first six identities" {429    var raw = std.mem.zeroes(abi.Language);430    raw.abi_version = 15;431    raw.symbol_count = 2;432    raw.lex_fn = testLex;433    var actions = [_]abi.ActionEntry{std.mem.zeroes(abi.ActionEntry)};434    raw.parse_actions = &actions;435    var metadata = [_]abi.SymbolMetadata{436        .{ .visible = false, .named = false, .supertype = false },437        .{ .visible = true, .named = true, .supertype = false },438    };439    raw.symbol_metadata = &metadata;440    const lang = try language.Language.init(&raw);441    const tree = try subtree.Tree.init(std.testing.allocator, lang);442    defer tree.deinit();443    var context = try stack.Context.init(std.testing.allocator, testing_limits);444    defer context.deinit();445    var versions: std.ArrayList(Version) = .empty;446    defer deinitVersions(std.testing.allocator, &versions);447    for (0..7) |index| {448        var branch = stack.Branch.init(&context, .zig);449        const parent = try tree.node(450            1,451            &.{},452            0,453            1,454            0,455            .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },456            false,457        );458        try branch.shift(459            &context,460            parent,461            @intCast(index + 2),462            .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },463            scanner.State.init(.zig),464        );465        try versions.append(std.testing.allocator, .{ .id = index, .branch = branch });466    }467    try compact(std.testing.allocator, &context, &versions);468    try std.testing.expectEqual(testing_limits.active_version_count, versions.items.len);469    for (versions.items, 0..) |version, index| try std.testing.expectEqual(@as(abi.State, @intCast(index + 2)), version.branch.state());470}471472test "focused active version compaction ranks precedence before stable identities" {473    var raw = std.mem.zeroes(abi.Language);474    raw.abi_version = 15;475    raw.symbol_count = 2;476    raw.lex_fn = testLex;477    var actions = [_]abi.ActionEntry{std.mem.zeroes(abi.ActionEntry)};478    raw.parse_actions = &actions;479    var metadata = [_]abi.SymbolMetadata{480        .{ .visible = false, .named = false, .supertype = false },481        .{ .visible = true, .named = true, .supertype = false },482    };483    raw.symbol_metadata = &metadata;484    const lang = try language.Language.init(&raw);485    const tree = try subtree.Tree.init(std.testing.allocator, lang);486    defer tree.deinit();487    var context = try stack.Context.init(std.testing.allocator, testing_limits);488    defer context.deinit();489    var versions: std.ArrayList(Version) = .empty;490    defer deinitVersions(std.testing.allocator, &versions);491    for (0..7) |index| {492        var branch = stack.Branch.init(&context, .zig);493        const parent = try tree.node(494            1,495            &.{},496            0,497            1,498            if (index == 6) 10 else 0,499            .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },500            false,501        );502        try branch.shift(503            &context,504            parent,505            @intCast(index + 2),506            .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },507            scanner.State.init(.zig),508        );509        try versions.append(std.testing.allocator, .{ .id = index, .branch = branch });510    }511    try compact(std.testing.allocator, &context, &versions);512    const expected = [_]abi.State{ 8, 2, 3, 4, 5, 6 };513    for (versions.items, expected) |version, state| try std.testing.expectEqual(state, version.branch.state());514}515516test "focused temporary version overflow is global and retains FIFO identities" {517    var raw = std.mem.zeroes(abi.Language);518    raw.abi_version = 15;519    raw.symbol_count = 2;520    raw.lex_fn = testLex;521    var actions = [_]abi.ActionEntry{std.mem.zeroes(abi.ActionEntry)};522    raw.parse_actions = &actions;523    var metadata = [_]abi.SymbolMetadata{524        .{ .visible = false, .named = false, .supertype = false },525        .{ .visible = true, .named = true, .supertype = false },526    };527    raw.symbol_metadata = &metadata;528    const lang = try language.Language.init(&raw);529    const tree = try subtree.Tree.init(std.testing.allocator, lang);530    defer tree.deinit();531    const lookahead_tree = try tree.leaf(532        1,533        .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },534        .{ .byte = 1, .point = .{ .row = 0, .column = 1 } },535        1,536        false,537        null,538    );539    var context = try stack.Context.init(std.testing.allocator, testing_limits);540    defer context.deinit();541    var ready: std.ArrayList(Version) = .empty;542    defer deinitVersions(std.testing.allocator, &ready);543    var shifted: std.ArrayList(Version) = .empty;544    defer deinitVersions(std.testing.allocator, &shifted);545    try appendTestVersions(&context, &ready, lookahead_tree, 4, 20, 100);546    try appendTestVersions(&context, &shifted, lookahead_tree, 2, 30, 200);547    for (0..6) |index| {548        const version = try testVersion(&context, lookahead_tree, @intCast(index + 2), index);549        const retained = try integrateReductionVersion(550            std.testing.allocator,551            &context,552            version,553            &ready,554            &shifted,555        );556        try std.testing.expectEqual(index < 4, retained);557    }558    try std.testing.expectEqual(@as(usize, 8), ready.items.len);559    for (ready.items[4..], 0..) |version, index| {560        try std.testing.expectEqual(index, version.id);561        try std.testing.expectEqual(@as(abi.State, @intCast(index + 2)), version.branch.state());562    }563}564565test "focused temporary overflow cannot merge a dropped late candidate" {566    var raw = std.mem.zeroes(abi.Language);567    raw.abi_version = 15;568    raw.symbol_count = 3;569    raw.lex_fn = testLex;570    var actions = [_]abi.ActionEntry{std.mem.zeroes(abi.ActionEntry)};571    raw.parse_actions = &actions;572    var metadata = [_]abi.SymbolMetadata{573        .{ .visible = false, .named = false, .supertype = false },574        .{ .visible = true, .named = true, .supertype = false },575        .{ .visible = true, .named = true, .supertype = false },576    };577    raw.symbol_metadata = &metadata;578    const lang = try language.Language.init(&raw);579    const tree = try subtree.Tree.init(std.testing.allocator, lang);580    defer tree.deinit();581    const retained_tree = try tree.node(582        1,583        &.{},584        0,585        1,586        0,587        .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },588        false,589    );590    const dropped_tree = try tree.node(591        2,592        &.{},593        0,594        1,595        10,596        .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },597        false,598    );599    var context = try stack.Context.init(std.testing.allocator, testing_limits);600    defer context.deinit();601    var ready: std.ArrayList(Version) = .empty;602    defer deinitVersions(std.testing.allocator, &ready);603    var shifted: std.ArrayList(Version) = .empty;604    defer deinitVersions(std.testing.allocator, &shifted);605    try appendTestVersions(&context, &shifted, retained_tree, 8, 20, 100);606    const trees = [_]*const subtree.Subtree{ retained_tree, retained_tree, dropped_tree };607    const states = [_]abi.State{ 2, 3, 2 };608    for (trees, states, 0..) |candidate_tree, state, index| {609        const version = try testVersion(&context, candidate_tree, state, index);610        const retained = try integrateReductionVersion(611            std.testing.allocator,612            &context,613            version,614            &ready,615            &shifted,616        );617        try std.testing.expectEqual(index < 2, retained);618    }619    try std.testing.expectEqual(@as(usize, 2), ready.items.len);620    try std.testing.expectEqual(@as(i64, 0), ready.items[0].branch.precedence());621}622623test "focused an allowed boundary merge frees the next temporary version" {624    var raw = std.mem.zeroes(abi.Language);625    raw.abi_version = 15;626    raw.symbol_count = 3;627    raw.lex_fn = testLex;628    var actions = [_]abi.ActionEntry{std.mem.zeroes(abi.ActionEntry)};629    raw.parse_actions = &actions;630    var metadata = [_]abi.SymbolMetadata{631        .{ .visible = false, .named = false, .supertype = false },632        .{ .visible = true, .named = true, .supertype = false },633        .{ .visible = true, .named = true, .supertype = false },634    };635    raw.symbol_metadata = &metadata;636    const lang = try language.Language.init(&raw);637    const tree = try subtree.Tree.init(std.testing.allocator, lang);638    defer tree.deinit();639    const retained_tree = try tree.node(640        1,641        &.{},642        0,643        1,644        0,645        .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },646        false,647    );648    const merging_tree = try tree.node(649        2,650        &.{},651        0,652        1,653        10,654        .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },655        false,656    );657    var context = try stack.Context.init(std.testing.allocator, testing_limits);658    defer context.deinit();659    var ready: std.ArrayList(Version) = .empty;660    defer deinitVersions(std.testing.allocator, &ready);661    var shifted: std.ArrayList(Version) = .empty;662    defer deinitVersions(std.testing.allocator, &shifted);663    try appendTestVersions(&context, &shifted, retained_tree, 8, 20, 100);664    const trees = [_]*const subtree.Subtree{ retained_tree, merging_tree, retained_tree };665    const states = [_]abi.State{ 2, 2, 3 };666    for (trees, states, 0..) |candidate_tree, state, index| {667        const version = try testVersion(&context, candidate_tree, state, index);668        _ = try integrateReductionVersion(669            std.testing.allocator,670            &context,671            version,672            &ready,673            &shifted,674        );675    }676    try std.testing.expectEqual(@as(usize, 2), ready.items.len);677    try std.testing.expectEqual(@as(i64, 10), ready.items[0].branch.precedence());678    try std.testing.expectEqual(@as(abi.State, 3), ready.items[1].branch.state());679}680681fn testVersion(682    context: *stack.Context,683    candidate_tree: *const subtree.Subtree,684    state: abi.State,685    id: usize,686) !Version {687    var branch = stack.Branch.init(context, .zig);688    try branch.shift(context, candidate_tree, state, candidate_tree.end, scanner.State.init(.zig));689    return .{ .id = id, .branch = branch };690}691692fn appendTestVersions(693    context: *stack.Context,694    versions: *std.ArrayList(Version),695    candidate_tree: *const subtree.Subtree,696    count: usize,697    state_base: abi.State,698    id_base: usize,699) !void {700    for (0..count) |index| {701        try versions.append(702            std.testing.allocator,703            try testVersion(context, candidate_tree, state_base + @as(abi.State, @intCast(index)), id_base + index),704        );705    }706}707708fn testLex(_: *abi.Lexer, _: abi.State) callconv(.c) bool {709    return false;710}

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