const std = @import("std");
const Grammar = @import("grammar.zig");
const NonTerminal = @import("non-terminal.zig");
const Character = @import("character.zig").Character;
const Generator = @import("generator.zig").Generator;
const gss = @import("gss.zig");

const State = struct {
	const Self = @This();

	name: u8,
	rule: NonTerminal.Rule,
	inner_position: usize,
	input_position: usize,

	pub fn format(
		self: *const Self,
		comptime fmt: []const u8,
		options: std.fmt.FormatOptions,
		writer: anytype,
	) !void {
		_ = fmt;
		_ = options;

		try writer.print("[ {c}, {s}, {}, {} ]", .{
			self.name,
			self.rule,
			self.inner_position,
			self.input_position,
		});
	}
};

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();
	}

	const entry = grammar.entry_point();

	for (entry.rules()) |rule| {
		const state = 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);
	}

	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();

	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) {
				if (
					stack.items.len == 1 and
					state.name == entry.name and
					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);
				}
				continue;
			}

			const epsilon_only = 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();

					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 (non_terminal.first.is_set(Character.EPSILON)) {
						state.inner_position += 1;
					} else {
						try remove_queue.append(stack_index);
					}
				},
				.epsilon => {
					state.inner_position += 1;
				},
			}
		}

		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();
	}

	return false;
}

test "expr" {
	const text =
			\\S -> B A
			\\A -> + B A
			\\A -> _
			\\B -> D C
			\\C -> * D C
			\\C -> _
			\\D -> ( S )
			\\D -> a
			\\D -> b
			;

	const input = "b+a*b";

	const allocator = std.testing.allocator;

	var grammar = try Grammar.parse(text, allocator);
	defer grammar.deinit(allocator);

	try std.testing.expect(try check(&grammar, input, allocator));
}

test "simple 0 - success" {
	const text =
		\\S -> A S d
		\\S -> B S
		\\S -> _
		\\A -> a
		\\A -> c
		\\B -> a
		\\B -> b
		;

	const input = "aad";

	const allocator = std.testing.allocator;

	var grammar = try Grammar.parse(text, allocator);
	defer grammar.deinit(allocator);

	try std.testing.expect(try check(&grammar, input, allocator));
}

test "simple 0 - fail" {
	const text =
		\\S -> A S d
		\\S -> B S
		\\S -> _
		\\A -> a
		\\A -> c
		\\B -> a
		\\B -> b
		;

	const input = "accd";

	const allocator = std.testing.allocator;

	var grammar = try Grammar.parse(text, allocator);
	defer grammar.deinit(allocator);

	try std.testing.expect(!try check(&grammar, input, allocator));
}

test "simple 0 - fuzzy" {
	const text =
		\\S -> A S d
		\\S -> B S
		\\S -> _
		\\A -> a
		\\A -> c
		\\B -> a
		\\B -> b
		;

	const allocator = std.testing.allocator;

	var grammar = try Grammar.parse(text, allocator);
	defer grammar.deinit(allocator);

	var generator = Generator(struct {
		const Self = @This();

		pub fn next(_: *Self, n: usize) usize {
			return std.crypto.random.uintLessThan(usize, n);
		}
	}){};

	for (0..100) |_| {
		const input = try generator.sentential_from_grammar(&grammar, 1000, allocator);
		defer allocator.free(input);

		try std.testing.expect(try check(&grammar, input, allocator));
	}

}