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

	id: usize,
	rule_index: usize,
	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("[ {}, {}, {}, {} ]", .{
			self.id,
			self.rule_index,
			self.inner_position,
			self.input_position,
		});
	}

	pub fn debug(self: *const Self, grammar: *Grammar, input: []const u8) void {
		const rule = grammar.non_terminal_by_id(self.id).rules()[self.rule_index];
		std.debug.print("input ({s}○{s}) state (", .{
			input[0..self.input_position],
			input[self.input_position..],
		});

		for (rule, 0..) |char, index| {
			if (index == self.inner_position) {
				std.debug.print("○", .{});
			}

			std.debug.print("{}", .{char});
		}

		if (rule.len == self.inner_position) {
			std.debug.print("○", .{});
		}
		std.debug.print(")\n", .{});
	}
};

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 (0..entry.rules().len) |index| {
		const node = try allocator.create(gss.Node(State));
		node.* = gss.Node(State).init(State {
			.id = entry.id,
			.rule_index = index,
			.inner_position = 0,
			.input_position = 0,
		});

		try processing_queue.append(node);
	}

	var next_processing_queue = &queues[1];

	while (processing_queue.items.len > 0) {
		for (processing_queue.items) |node| {
			const rule = grammar.non_terminal_by_id(node.state.id).rules()[node.state.rule_index];

			if (node.state.inner_position == rule.len) {
				if (
					node.parent == null and
					node.state.id == entry.id and
					node.state.input_position == input.len
				) {
					return true;
				}

				const old_state, const parent_node = node.pop(allocator);
				if (parent_node) |parent| {
					const sibling = try parent.clone(State {
						.id = parent.state.id,
						.rule_index = parent.state.rule_index,
						.inner_position = parent.state.inner_position + 1,
						.input_position = old_state.input_position,
					}, allocator);
					try next_processing_queue.append(sibling);
				}
			} else {
				const epsilon_only = node.state.input_position == input.len;

				switch (rule[node.state.inner_position]) {
					.terminal => |t| {
						if (!epsilon_only and input[node.state.input_position] == t) {
							const sibling = try node.clone(State {
								.id = node.state.id,
								.rule_index = node.state.rule_index,
								.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_id(n);

						if (!epsilon_only and non_terminal.first.is_set(input[node.state.input_position])) {
							for (0..non_terminal.rules().len) |index| {
								const child = try node.push(State {
									.id = non_terminal.id,
									.rule_index = index,
									.inner_position = 0,
									.input_position = node.state.input_position,
								}, allocator);
								try next_processing_queue.append(child);
							}
						}

						if (non_terminal.first.is_set(Character.EPSILON)) {
							const sibling = try node.clone(State {
								.id = node.state.id,
								.rule_index = node.state.rule_index,
								.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 {
							.id = node.state.id,
							.rule_index = node.state.rule_index,
							.inner_position = node.state.inner_position + 1,
							.input_position = node.state.input_position
						}, allocator);
						try next_processing_queue.append(sibling);
					},
				}
			}
		}

		const swap = processing_queue;
		processing_queue = next_processing_queue;
		next_processing_queue = swap;
		next_processing_queue.clearRetainingCapacity();
	}

	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("S", text, allocator);
	defer grammar.deinit();

	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("S", text, allocator);
	defer grammar.deinit();

	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("S", text, allocator);
	defer grammar.deinit();

	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("S", text, allocator);
	defer grammar.deinit();

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

}