tiny.smg.tree.runtime.stack

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

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 subtree = runtime.subtree;1011const testing_limits = @import("../../root.zig").default_limits.parser;1213const Link = struct {14    previous: *Node,15    tree: *const subtree.Subtree,16};1718const Node = struct {19    state: abi.State,20    position: lexer.Position,21    links: []Link,22    link_count: usize = 0,23    precedence: i64,2425    fn linkSlice(self: *const Node) []const Link {26        return self.links[0..self.link_count];27    }28};2930pub const Budget = struct {31    operations: *usize,32    limit: usize,3334    fn charge(self: Budget) !void {35        if (self.operations.* >= self.limit) return error.OperationLimitExceeded;36        self.operations.* += 1;37    }38};3940pub const Context = struct {41    arena: std.heap.ArenaAllocator,42    base: *Node,43    limits: limits_mod.Parser,4445    pub fn init(allocator: std.mem.Allocator, limits: limits_mod.Parser) !Context {46        var self = Context{47            .arena = std.heap.ArenaAllocator.init(allocator),48            .base = undefined,49            .limits = limits,50        };51        errdefer self.arena.deinit();52        self.base = try self.arena.allocator().create(Node);53        self.base.* = .{54            .state = 1,55            .position = .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },56            .links = try self.arena.allocator().alloc(Link, limits.link_count),57            .precedence = 0,58        };59        return self;60    }6162    pub fn deinit(self: *Context) void {63        self.arena.deinit();64        self.* = undefined;65    }6667    fn push(self: *Context, previous: *Node, tree: *const subtree.Subtree, state: abi.State) !*Node {68        const allocator = self.arena.allocator();69        const result = try allocator.create(Node);70        result.* = .{71            .state = state,72            .position = tree.end,73            .links = try allocator.alloc(Link, self.limits.link_count),74            .link_count = 1,75            .precedence = previous.precedence + tree.dynamic_precedence,76        };77        result.links[0] = .{ .previous = previous, .tree = tree };78        return result;79    }8081    pub fn merge(self: *Context, left: *Node, right: *Node) !bool {82        if (!canMerge(left, right)) return error.IncompatibleStackHeads;83        if (left == right) return false;84        var changed = false;85        for (right.linkSlice()) |link| changed = self.addLink(left, link) or changed;86        return changed;87    }8889    fn addLink(self: *Context, node: *Node, candidate: Link) bool {90        if (candidate.previous == node) return false;91        for (node.links[0..node.link_count]) |*existing| {92            if (!linksEquivalent(existing.*, candidate)) continue;93            if (existing.previous == candidate.previous) {94                if (candidate.tree.dynamic_precedence <= existing.tree.dynamic_precedence) return false;95                existing.tree = candidate.tree;96                node.precedence = candidate.previous.precedence + candidate.tree.dynamic_precedence;97                return true;98            }99            if (canMerge(existing.previous, candidate.previous)) {100                var changed = false;101                for (candidate.previous.linkSlice()) |link| changed = self.addLink(existing.previous, link) or changed;102                const candidate_precedence = candidate.previous.precedence + candidate.tree.dynamic_precedence;103                if (candidate_precedence > node.precedence) {104                    node.precedence = candidate_precedence;105                    changed = true;106                }107                return changed;108            }109        }110        if (node.link_count == node.links.len) return false;111        node.links[node.link_count] = candidate;112        node.link_count += 1;113        node.precedence = @max(node.precedence, candidate.previous.precedence + candidate.tree.dynamic_precedence);114        return true;115    }116};117118fn canMerge(left: *const Node, right: *const Node) bool {119    return left.state == right.state and left.position.byte == right.position.byte;120}121122fn linksEquivalent(left: Link, right: Link) bool {123    if (left.tree == right.tree) return true;124    return left.tree.symbol == right.tree.symbol and125        left.tree.start.byte -| left.previous.position.byte == right.tree.start.byte -| right.previous.position.byte and126        left.tree.end.byte -| left.tree.start.byte == right.tree.end.byte -| right.tree.start.byte and127        left.tree.children.len == right.tree.children.len and128        left.tree.extra == right.tree.extra and129        scannerStatesEqual(left.tree.scanner_state, right.tree.scanner_state);130}131132fn scannerStatesEqual(left: ?scanner.State, right: ?scanner.State) bool {133    if (left) |left_state| {134        if (right) |right_state| return left_state.eql(right_state);135        return left_state.isEmpty();136    }137    return right == null or right.?.isEmpty();138}139140pub const Branch = struct {141    head: *Node,142    position: lexer.Position,143    scanner_state: scanner.State,144145    pub fn init(context: *Context, kind: scanner.Kind) Branch {146        return .{147            .head = context.base,148            .position = .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },149            .scanner_state = scanner.State.init(kind),150        };151    }152153    pub fn deinit(self: *Branch, _: std.mem.Allocator) void {154        self.* = undefined;155    }156157    pub fn clone(self: Branch, _: std.mem.Allocator) !Branch {158        return self;159    }160161    pub fn state(self: Branch) abi.State {162        return self.head.state;163    }164165    pub fn shift(166        self: *Branch,167        context: *Context,168        tree: *const subtree.Subtree,169        state_after: abi.State,170        position: lexer.Position,171        scanner_after: scanner.State,172    ) !void {173        self.head = try context.push(self.head, tree, state_after);174        self.position = position;175        self.scanner_state = scanner_after;176    }177178    pub fn reduce(179        self: Branch,180        allocator: std.mem.Allocator,181        context: *Context,182        tree: *subtree.Tree,183        lang: language.Language,184        action: abi.Reduce,185        output: *std.ArrayList(Branch),186        budget: Budget,187    ) !void {188        var candidates: std.ArrayList(Reduction) = .empty;189        defer deinitReductions(allocator, &candidates);190        var visit = ReductionVisit{191            .allocator = allocator,192            .tree = tree,193            .action = action,194            .position = self.position,195            .candidates = &candidates,196        };197        try walkPaths(198            allocator,199            self.head,200            action.child_count,201            context.limits.iterator_count,202            budget,203            &visit,204            visitReduction,205        );206207        for (candidates.items) |candidate| {208            const next_state = lang.nextState(candidate.predecessor.state, action.symbol);209            if (next_state == 0) continue;210            var branch = Branch{211                .head = candidate.predecessor,212                .position = self.position,213                .scanner_state = self.scanner_state,214            };215            branch.head = try context.push(branch.head, candidate.parent, next_state);216            for (candidate.extras.items) |extra| branch.head = try context.push(branch.head, extra, next_state);217            try output.append(allocator, branch);218        }219    }220221    pub fn acceptedRoot(222        self: Branch,223        allocator: std.mem.Allocator,224        context: *Context,225        tree: *subtree.Tree,226        budget: Budget,227    ) !?*const subtree.Subtree {228        var visit = RootVisit{ .allocator = allocator, .tree = tree };229        try walkPaths(230            allocator,231            self.head,232            null,233            context.limits.iterator_count,234            budget,235            &visit,236            visitRoot,237        );238        return visit.selected;239    }240241    pub fn precedence(self: Branch) i64 {242        return self.head.precedence;243    }244245    pub fn equivalent(left: Branch, right: Branch) bool {246        return left.state() == right.state() and247            std.meta.eql(left.position, right.position) and248            left.scanner_state.eql(right.scanner_state);249    }250};251252const PathIterator = struct {253    node: *Node,254    structural_count: usize,255    path: std.ArrayList(*const subtree.Subtree) = .empty,256};257258fn walkPaths(259    allocator: std.mem.Allocator,260    head: *Node,261    goal: ?usize,262    iterator_count: usize,263    budget: Budget,264    context: anytype,265    comptime visit: anytype,266) !void {267    var iterators: std.ArrayList(PathIterator) = .empty;268    defer {269        for (iterators.items) |*iterator| iterator.path.deinit(allocator);270        iterators.deinit(allocator);271    }272    try iterators.append(allocator, .{ .node = head, .structural_count = 0 });273    while (iterators.items.len > 0) {274        var index: usize = 0;275        var round_count = iterators.items.len;276        while (index < round_count) {277            try budget.charge();278            const node = iterators.items[index].node;279            const complete = if (goal) |count| iterators.items[index].structural_count == count else node.link_count == 0;280            if (complete or node.link_count == 0) {281                if (complete) try visit(context, node, iterators.items[index].path.items);282                var finished = iterators.orderedRemove(index);283                finished.path.deinit(allocator);284                round_count -= 1;285                continue;286            }287288            const alternative_count = @min(289                @as(usize, node.link_count - 1),290                iterator_count -| iterators.items.len,291            );292            try iterators.ensureUnusedCapacity(allocator, alternative_count);293            for (node.links[1 .. alternative_count + 1]) |link| {294                var alternative = PathIterator{295                    .node = link.previous,296                    .structural_count = iterators.items[index].structural_count + @intFromBool(!link.tree.extra),297                };298                errdefer alternative.path.deinit(allocator);299                try alternative.path.appendSlice(allocator, iterators.items[index].path.items);300                try alternative.path.append(allocator, link.tree);301                iterators.appendAssumeCapacity(alternative);302            }303304            const first = node.links[0];305            iterators.items[index].node = first.previous;306            iterators.items[index].structural_count += @intFromBool(!first.tree.extra);307            try iterators.items[index].path.append(allocator, first.tree);308            index += 1;309        }310    }311}312313const ReductionVisit = struct {314    allocator: std.mem.Allocator,315    tree: *subtree.Tree,316    action: abi.Reduce,317    position: lexer.Position,318    candidates: *std.ArrayList(Reduction),319};320321fn visitReduction(visit: *ReductionVisit, predecessor: *Node, reverse_path: []const *const subtree.Subtree) !void {322    try addReduction(visit.allocator, visit.tree, visit.action, visit.position, predecessor, reverse_path, visit.candidates);323}324325const RootVisit = struct {326    allocator: std.mem.Allocator,327    tree: *subtree.Tree,328    selected: ?*const subtree.Subtree = null,329};330331fn visitRoot(visit: *RootVisit, _: *Node, reverse_path: []const *const subtree.Subtree) !void {332    const candidate = try rootForPath(visit.allocator, visit.tree, reverse_path) orelse return;333    if (visit.selected == null or try preferred(visit.allocator, visit.selected.?, candidate) == candidate) visit.selected = candidate;334}335336const Reduction = struct {337    predecessor: *Node,338    parent: *const subtree.Subtree,339    extras: std.ArrayList(*const subtree.Subtree),340};341342fn addReduction(343    allocator: std.mem.Allocator,344    tree: *subtree.Tree,345    action: abi.Reduce,346    position: lexer.Position,347    predecessor: *Node,348    reverse_path: []const *const subtree.Subtree,349    candidates: *std.ArrayList(Reduction),350) !void {351    var children: std.ArrayList(*const subtree.Subtree) = .empty;352    defer children.deinit(allocator);353    try children.ensureTotalCapacity(allocator, reverse_path.len);354    var index = reverse_path.len;355    while (index > 0) {356        index -= 1;357        children.appendAssumeCapacity(reverse_path[index]);358    }359    var children_end = children.items.len;360    while (children_end > 0 and children.items[children_end - 1].extra) children_end -= 1;361    const parent = try tree.node(362        action.symbol,363        children.items[0..children_end],364        action.production_id,365        predecessor.state,366        action.dynamic_precedence,367        position,368        false,369    );370    var extras: std.ArrayList(*const subtree.Subtree) = .empty;371    errdefer extras.deinit(allocator);372    try extras.appendSlice(allocator, children.items[children_end..]);373    for (candidates.items) |*candidate| {374        if (candidate.predecessor != predecessor) continue;375        const winner = try preferred(allocator, candidate.parent, parent);376        if (winner == parent) {377            candidate.parent = parent;378            candidate.extras.deinit(allocator);379            candidate.extras = extras;380        } else {381            extras.deinit(allocator);382        }383        return;384    }385    try candidates.append(allocator, .{386        .predecessor = predecessor,387        .parent = parent,388        .extras = extras,389    });390}391392fn preferred(allocator: std.mem.Allocator, left: *const subtree.Subtree, right: *const subtree.Subtree) !*const subtree.Subtree {393    if (left.dynamic_precedence > right.dynamic_precedence) return left;394    if (right.dynamic_precedence > left.dynamic_precedence) return right;395    return if (try subtree.order(allocator, left, right) == .gt) right else left;396}397398fn rootForPath(399    allocator: std.mem.Allocator,400    tree: *subtree.Tree,401    reverse_path: []const *const subtree.Subtree,402) !?*const subtree.Subtree {403    var entries: std.ArrayList(*const subtree.Subtree) = .empty;404    defer entries.deinit(allocator);405    try entries.ensureTotalCapacity(allocator, reverse_path.len);406    var reverse_index = reverse_path.len;407    while (reverse_index > 0) {408        reverse_index -= 1;409        entries.appendAssumeCapacity(reverse_path[reverse_index]);410    }411    var root_index = entries.items.len;412    while (root_index > 0) {413        root_index -= 1;414        if (!entries.items[root_index].extra) break;415    } else return null;416    const base = entries.items[root_index];417    if (root_index == 0 and entries.items.len == 1) return base;418    var children: std.ArrayList(*const subtree.Subtree) = .empty;419    defer children.deinit(allocator);420    try children.ensureTotalCapacity(allocator, entries.items.len - 1 + base.children.len);421    for (entries.items[0..root_index]) |entry| children.appendAssumeCapacity(entry);422    for (base.children) |child| children.appendAssumeCapacity(child);423    for (entries.items[root_index + 1 ..]) |entry| children.appendAssumeCapacity(entry);424    var child_precedence: i32 = 0;425    for (base.children) |child| child_precedence += child.dynamic_precedence;426    return try tree.node(427        base.symbol,428        children.items,429        base.production_id,430        base.parse_state,431        base.dynamic_precedence - child_precedence,432        base.start,433        base.extra,434    );435}436437fn deinitReductions(allocator: std.mem.Allocator, reductions: *std.ArrayList(Reduction)) void {438    for (reductions.items) |*reduction| reduction.extras.deinit(allocator);439    reductions.deinit(allocator);440}441442test "graph stack merges parser heads without merging scanner states" {443    var context = try Context.init(std.testing.allocator, testing_limits);444    defer context.deinit();445    const left = Branch.init(&context, .cpp);446    var right = Branch.init(&context, .cpp);447    try std.testing.expect(left.equivalent(right));448    right.scanner_state.cpp.delimiter_length = 1;449    try std.testing.expect(!left.equivalent(right));450}451452test "focused graph links compare serialized external scanner state" {453    var context = try Context.init(std.testing.allocator, testing_limits);454    defer context.deinit();455    var left_tree = subtree.Subtree{456        .symbol = 1,457        .children = &.{},458        .start = .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },459        .end = .{ .byte = 1, .point = .{ .row = 0, .column = 1 } },460        .production_id = 0,461        .dynamic_precedence = 0,462        .parse_state = 1,463        .visible_descendant_count = 0,464        .named_descendant_count = 0,465        .visible = true,466        .named = true,467        .extra = false,468        .scanner_state = null,469    };470    var right_tree = left_tree;471    var empty_state = scanner.State.init(.cpp);472    left_tree.scanner_state = empty_state;473    try std.testing.expect(linksEquivalent(474        .{ .previous = context.base, .tree = &left_tree },475        .{ .previous = context.base, .tree = &right_tree },476    ));477    empty_state.cpp.delimiter_length = 1;478    right_tree.scanner_state = empty_state;479    try std.testing.expect(!linksEquivalent(480        .{ .previous = context.base, .tree = &left_tree },481        .{ .previous = context.base, .tree = &right_tree },482    ));483}484485test "focused saturated graph stack ignores precedence from a dropped ninth link" {486    var context = try Context.init(std.testing.allocator, testing_limits);487    defer context.deinit();488    var trees: [9]subtree.Subtree = undefined;489    for (&trees, 0..) |*tree, index| tree.* = .{490        .symbol = @intCast(index + 1),491        .children = &.{},492        .start = .{ .byte = 0, .point = .{ .row = 0, .column = 0 } },493        .end = .{ .byte = 1, .point = .{ .row = 0, .column = 1 } },494        .production_id = 0,495        .dynamic_precedence = if (index == 8) 100 else 0,496        .parse_state = 1,497        .visible_descendant_count = 0,498        .named_descendant_count = 0,499        .visible = true,500        .named = true,501        .extra = false,502        .scanner_state = null,503    };504    var left_links: [testing_limits.link_count]Link = undefined;505    var left = Node{506        .state = 2,507        .position = trees[0].end,508        .links = &left_links,509        .link_count = testing_limits.link_count,510        .precedence = 0,511    };512    for (left.links[0..testing_limits.link_count], 0..) |*link, index| link.* = .{ .previous = context.base, .tree = &trees[index] };513    var right_links: [testing_limits.link_count]Link = undefined;514    var right = Node{515        .state = 2,516        .position = trees[8].end,517        .links = &right_links,518        .link_count = 1,519        .precedence = 100,520    };521    right.links[0] = .{ .previous = context.base, .tree = &trees[8] };522    try std.testing.expect(!try context.merge(&left, &right));523    try std.testing.expectEqual(testing_limits.link_count, left.link_count);524    try std.testing.expectEqual(@as(i64, 0), left.precedence);525}526527const WalkWitness = struct {528    count: usize = 0,529    expected_bottom: *const subtree.Subtree,530};531532fn visitWalkWitness(witness: *WalkWitness, _: *Node, path: []const *const subtree.Subtree) !void {533    try std.testing.expectEqual(@as(usize, 3), path.len);534    try std.testing.expectEqual(witness.expected_bottom, path[2]);535    witness.count += 1;536}537538test "focused saturated pop-count and pop-all retain the pinned 64-path frontier" {539    var context = try Context.init(std.testing.allocator, testing_limits);540    defer context.deinit();541    var trees: [24]subtree.Subtree = undefined;542    for (&trees, 0..) |*tree, index| tree.* = .{543        .symbol = @intCast(index + 1),544        .children = &.{},545        .start = .{ .byte = @intCast(index), .point = .{ .row = 0, .column = @intCast(index) } },546        .end = .{ .byte = @intCast(index + 1), .point = .{ .row = 0, .column = @intCast(index + 1) } },547        .production_id = 0,548        .dynamic_precedence = 0,549        .parse_state = 1,550        .visible_descendant_count = 0,551        .named_descendant_count = 0,552        .visible = true,553        .named = true,554        .extra = false,555        .scanner_state = null,556    };557    var nodes: [3]Node = undefined;558    var node_links: [3][testing_limits.link_count]Link = undefined;559    for (&nodes, 0..) |*node, level| {560        node.* = .{561            .state = @intCast(level + 2),562            .position = trees[level * testing_limits.link_count].end,563            .links = &node_links[level],564            .link_count = testing_limits.link_count,565            .precedence = 0,566        };567        const previous = if (level == 0) context.base else &nodes[level - 1];568        for (node.links[0..testing_limits.link_count], 0..) |*link, index| {569            link.* = .{ .previous = previous, .tree = &trees[level * testing_limits.link_count + index] };570        }571    }572573    for ([_]?usize{ 3, null }) |goal| {574        var operations: usize = 0;575        var witness = WalkWitness{ .expected_bottom = &trees[0] };576        try walkPaths(577            std.testing.allocator,578            &nodes[2],579            goal,580            testing_limits.iterator_count,581            .{ .operations = &operations, .limit = 137 },582            &witness,583            visitWalkWitness,584        );585        try std.testing.expectEqual(@as(usize, 64), witness.count);586        try std.testing.expectEqual(@as(usize, 137), operations);587    }588589    var operations: usize = 0;590    var witness = WalkWitness{ .expected_bottom = &trees[0] };591    try std.testing.expectError(592        error.OperationLimitExceeded,593        walkPaths(594            std.testing.allocator,595            &nodes[2],596            3,597            testing_limits.iterator_count,598            .{ .operations = &operations, .limit = 136 },599            &witness,600            visitWalkWitness,601        ),602    );603}