improve gss node cashing and creation

1 files changed, 45 insertions, 44 deletions

diff --git a/src/recognizer.zig b/src/recognizer.zig
index 3c284d1..2eeae0d 100644
--- a/src/recognizer.zig
+++ b/src/recognizer.zig
@@ -69,65 +69,65 @@ const State = struct {
 	}
 };
 
-// NOTE: Since I can't remember shit:
-//
-// if (grammar.is_next_char(
-//   non_terminal.rules()[node.state.rule_index][node.state.inner_position..],
-//   node.state.id,
-//   input[node.state.input_position],
-// ))
-
 pub fn forward_and_consume(
 	grammar: *Grammar,
-	node: *gss.Node(State),
+	base: *gss.Node(State),
 	graph: *gss.Graph(State),
 	terminal: u8,
 	queue: *std.ArrayList(*gss.Node(State)),
 	node_cache: *std.HashMap(State, *gss.Node(State), State.Context, 80),
+	allocator: std.mem.Allocator,
 ) !void {
-	const rule = grammar.non_terminal_by_id(node.state.id).rules()[node.state.rule_index];
+	var forward_queue = std.ArrayList(struct { State, *gss.Node(State) }).init(allocator);
+	try forward_queue.append(.{ base.state, base });
 
-	if (node.state.inner_position == rule.len) {
-		for (node.parents.items) |parent| {
-			const next = try graph.clone(parent, parent.state.next());
-			try forward_and_consume(grammar, next, graph, terminal, queue, node_cache);
-		}
+	while (forward_queue.popOrNull()) |checkpoint| {
+		const last_state, const last_node = checkpoint;
+		const rule = grammar.non_terminal_by_id(last_state.id).rules()[last_state.rule_index];
 
-		return;
-	}
+		if (last_state.inner_position == rule.len) {
+			for (last_node.parents.items) |parent| {
+				try forward_queue.append(.{parent.state.next(), parent});
+			}
 
-	switch (rule[node.state.inner_position]) {
-		.terminal => |t| if (t == terminal) try queue.append(try graph.clone(node, node.state.next())),
-		.non_terminal => |n| {
-			const non_terminal = grammar.non_terminal_by_id(n);
-			for (0..grammar.non_terminal_by_id(n).rules().len) |rule_index| {
-				if (grammar.is_next_char(
-						non_terminal.rules()[rule_index],
-						n,
-						terminal,
-				)) {
+			continue;
+		}
 
-					const state = State {
-						.id = n,
-						.rule_index = rule_index,
-						.inner_position = 0,
-					};
+		switch (rule[last_state.inner_position]) {
+			.terminal => |t| if (t == terminal) {
+				const node = try graph.clone(last_node, last_state.next());
+				try queue.append(node);
+			},
+			.non_terminal => |n| {
+				const non_terminal = grammar.non_terminal_by_id(n);
+				for (0..grammar.non_terminal_by_id(n).rules().len) |rule_index| {
+					if (grammar.is_next_char(
+							non_terminal.rules()[rule_index],
+							n,
+							terminal,
+					)) {
 
-					const result = try node_cache.getOrPut(state);
+						const state = State {
+							.id = n,
+							.rule_index = rule_index,
+							.inner_position = 0,
+						};
 
-					if (!result.found_existing) {
-						result.value_ptr.* = try graph.push(node, state);
-						try forward_and_consume(grammar, result.value_ptr.*, graph, terminal, queue, node_cache);
-					} else {
-						try result.value_ptr.*.parents.append(node);
+						if (node_cache.get(state)) |parent| {
+							try parent.parents.append(last_node);
+						} else {
+							const parent = try graph.clone(last_node, last_state);
+							const next = try graph.push(parent, state);
+							try node_cache.put(state, next);
+							try forward_queue.append(.{state, next});
+						}
 					}
 				}
-			}
-		},
-		.epsilon => {
-			const next = try graph.clone(node, node.state.next());
-			try forward_and_consume(grammar, next, graph, terminal, queue, node_cache);
-		},
+			},
+			.epsilon => {
+				try forward_queue.append(.{last_state.next(), last_node});
+			},
+		}
 	}
 }
 
@@ -193,6 +193,7 @@ pub fn check(grammar: *Grammar, input: []const u8, inner_allocator: std.mem.Allo
 				character,
 				next_processing_queue,
 				&node_cache,
+				allocator,
 			);
 
 			node_cache.clearRetainingCapacity();