# The parser of the Nit language.
class Parser
	super TablesCapable
	# Associated lexer
	var lexer: Lexer

	# Stack of pushed states and productions
	private var stack = new Array[State]

	# Position in the stack
	private var stack_pos: Int = -1

	init
	do
		self.reduce_table = once build_reduce_table
	end

	# Do a transition in the automata
	private fun go_to(index: Int): Int
	do
		var state = state
		var low = 1
		var high = parser_goto(index, 0) - 1

		while low <= high do
			var middle = (low + high) / 2
			var subindex = middle * 2 + 1 # +1 because parser_goto(index, 0) is the length

			var goal = parser_goto(index, subindex)
			if state < goal then
				high = middle - 1
			else if state > goal then
				low = middle + 1
			else
				return parser_goto(index, subindex+1)
			end
		end

		return parser_goto(index, 2) # Default value
	end

	# Push someting in the state stack
	private fun push(numstate: Int, list_node: nullable Object)
	do
		var pos = _stack_pos + 1
		_stack_pos = pos
		if pos < _stack.length then
			var state = _stack[pos]
			state._state = numstate
			state._nodes = list_node
		else
			_stack.push(new State(numstate, list_node))
		end
	end

	# The current state
	private fun state: Int
	do
		return _stack[_stack_pos]._state
	end

	# Pop something from the stack state
	private fun pop: nullable Object
	do
		var res = _stack[_stack_pos]._nodes
		_stack_pos = _stack_pos -1
		return res
	end

	# Build and return a full AST.
	fun parse: Start
	do
		push(0, null)

		var lexer = _lexer
		loop
			var token = lexer.peek
			if token isa AError then
				return new Start(null, token)
			end

			var state = self.state
			var index = token.parser_index
			var action_type = parser_action(state, 2)
			var action_value = parser_action(state, 3)

			var low = 1
			var high = parser_action(state, 0) - 1

			while low <= high do
				var middle = (low + high) / 2
				var subindex = middle * 3 + 1 # +1 because parser_action(state, 0) is the length

				var goal = parser_action(state, subindex)
				if index < goal then
					high = middle - 1
				else if index > goal then
					low = middle + 1
				else
					action_type = parser_action(state, subindex+1)
					action_value = parser_action(state, subindex+2)
					break
				end
			end

			if action_type == 0 then # SHIFT
				push(action_value, lexer.next)
			else if action_type == 1 then # REDUCE
				_reduce_table[action_value].action(self)
			else if action_type == 2 then # ACCEPT
				var node2 = lexer.next
				assert node2 isa EOF
				var node1 = pop
				assert node1 isa AModule
				var node = new Start(node1, node2)
				node2.parent = node
				(new ComputeProdLocationVisitor(lexer.file.first_token)).enter_visit(node)
				return node
			else if action_type == 3 then # ERROR
				# skip injected tokens
				while not isset token._location do token = lexer.next
				var node2 = new AParserError.init_parser_error("Syntax Error: unexpected {token}.", token.location, token)
				var node = new Start(null, node2)
				return node
			end
		end
	end

	private var reduce_table: Array[ReduceAction] is noinit
	private fun build_reduce_table: Array[ReduceAction] is abstract
end