use gss

1 files changed, 81 insertions, 80 deletions

diff --git a/src/recognizer.zig b/src/recognizer.zig
index 3adb7a4..1783db1 100644
--- a/src/recognizer.zig
+++ b/src/recognizer.zig
@@ -31,111 +31,112 @@ const State = struct {
 	}
 };
 
-pub fn check(grammar: *Grammar, input: []const u8, allocator: std.mem.Allocator) !bool {
-	var stacks = std.ArrayList(std.ArrayList(State)).init(allocator);
-	defer {
-		for (stacks.items) |stack| {
-			stack.deinit();
-		}
-		stacks.deinit();
-	}
+pub fn check(grammar: *Grammar, input: []const u8, inner_allocator: std.mem.Allocator) !bool {
+	var arena = std.heap.ArenaAllocator.init(inner_allocator);
+	defer arena.deinit();
+	const allocator = arena.allocator();
 
 	const entry = grammar.entry_point();
+	var queues = [2]std.ArrayList(*gss.Node(State)) {
+		std.ArrayList(*gss.Node(State)).init(allocator),
+		std.ArrayList(*gss.Node(State)).init(allocator),
+	};
+	defer for (queues) |queue| queue.deinit();
+	var processing_queue = &queues[0];
 
 	for (entry.rules()) |rule| {
-		const state = State {
+		const node = try allocator.create(gss.Node(State));
+		node.* = gss.Node(State).init(State {
 			.name = entry.name,
 			.rule = rule,
 			.inner_position = 0,
 			.input_position = 0,
-		};
+		});
 
-		var stack = std.ArrayList(State).init(allocator);
-		try stack.append(state);
-		try stacks.append(stack);
+		try processing_queue.append(node);
 	}
 
-	var remove_queue = std.ArrayList(usize).init(allocator);
-	defer remove_queue.deinit();
-	var add_queue = std.ArrayList(std.ArrayList(State)).init(allocator);
-	defer add_queue.deinit();
+	var next_processing_queue = &queues[1];
 
-	while (stacks.items.len > 0) {
-		for (stacks.items, 0..) |*stack, stack_index| {
-			var state: *State = &stack.items[stack.items.len - 1];
-			
-			if (state.inner_position == state.rule.len) {
+	while (processing_queue.items.len > 0) {
+		for (processing_queue.items) |node| {
+			if (node.state.inner_position == node.state.rule.len) {
 				if (
-					stack.items.len == 1 and
-					state.name == entry.name and
-					state.input_position == input.len
+					node.parent == null and
+					node.state.name == entry.name and
+					node.state.input_position == input.len
 				) {
 					return true;
 				}
 
-				const old_state = stack.pop();
-				if (stack.items.len > 0) {
-					state = &stack.items[stack.items.len - 1];
-					state.inner_position += 1;
-					state.input_position = old_state.input_position;
-				} else {
-					try remove_queue.append(stack_index);
+				const old_state, const parent_node = node.pop(allocator);
+				if (parent_node) |parent| {
+					const sibling = try parent.clone(State {
+						.name = parent.state.name,
+						.rule = parent.state.rule,
+						.inner_position = parent.state.inner_position + 1,
+						.input_position = old_state.input_position,
+					}, allocator);
+					try next_processing_queue.append(sibling);
 				}
-				continue;
-			}
-
-			const epsilon_only = state.input_position == input.len;
+			} else {
+				const epsilon_only = node.state.input_position == input.len;
 
-			switch (state.rule[state.inner_position]) {
-				.terminal => |t| {
-					if (!epsilon_only and input[state.input_position] == t) {
-						state.inner_position += 1;
-						state.input_position += 1;
-					} else {
-						try remove_queue.append(stack_index);
-					}
-				},
-				.non_terminal => |n| {
-					const non_terminal = grammar.non_terminal_by_name(n);
-					const rules = non_terminal.rules();
+				switch (node.state.rule[node.state.inner_position]) {
+					.terminal => |t| {
+						if (!epsilon_only and input[node.state.input_position] == t) {
+							const sibling = try node.clone(State {
+								.name = node.state.name,
+								.rule = node.state.rule,
+								.inner_position = node.state.inner_position + 1,
+								.input_position = node.state.input_position + 1,
+							}, allocator);
+							try next_processing_queue.append(sibling);
+						}
+					},
+					.non_terminal => |n| {
+						const non_terminal = grammar.non_terminal_by_name(n);
+						const rules = non_terminal.rules();
 
-					if (!epsilon_only and non_terminal.first.is_set(input[state.input_position])) {
-						for (rules) |rule| {
-							const next_state = State {
-								.name = non_terminal.name,
-								.rule = rule,
-								.inner_position = 0,
-								.input_position = state.input_position,
-							};
-							var new_stack = try stack.clone();
-							try new_stack.append(next_state);
-							try add_queue.append(new_stack);
+						if (!epsilon_only and non_terminal.first.is_set(input[node.state.input_position])) {
+							for (rules) |rule| {
+								const child = try node.push(State {
+									.name = non_terminal.name,
+									.rule = rule,
+									.inner_position = 0,
+									.input_position = node.state.input_position,
+								}, allocator);
+								try next_processing_queue.append(child);
+							}
 						}
-					}
 
-					if (non_terminal.first.is_set(Character.EPSILON)) {
-						state.inner_position += 1;
-					} else {
-						try remove_queue.append(stack_index);
-					}
-				},
-				.epsilon => {
-					state.inner_position += 1;
-				},
+						if (non_terminal.first.is_set(Character.EPSILON)) {
+							const sibling = try node.clone(State {
+								.name = node.state.name,
+								.rule = node.state.rule,
+								.inner_position = node.state.inner_position + 1,
+								.input_position = node.state.input_position
+							}, allocator);
+							try next_processing_queue.append(sibling);
+						}
+					},
+					.epsilon => {
+						const sibling = try node.clone(State {
+							.name = node.state.name,
+							.rule = node.state.rule,
+							.inner_position = node.state.inner_position + 1,
+							.input_position = node.state.input_position
+						}, allocator);
+						try next_processing_queue.append(sibling);
+					},
+				}
 			}
 		}
 
-		for (remove_queue.items, 0..) |index, offset| {
-			const stack = stacks.orderedRemove(index - offset);
-			stack.deinit();
-		}
-
-		for (add_queue.items) |stack| {
-			try stacks.append(stack);
-		}
-
-		remove_queue.clearAndFree();
-		add_queue.clearAndFree();
+		const swap = processing_queue;
+		processing_queue = next_processing_queue;
+		next_processing_queue = swap;
+		next_processing_queue.clearRetainingCapacity();
 	}
 
 	return false;