local modname = minetest.get_current_modname()
local S = minetest.get_translator(modname)

_G[modname].cached_programs = {}

_G[modname].tokenize = function(program)
	local tkns = {}
	local index = 0
	for char, num in string.gmatch(program, ("([><%+%-%.,%[%]%(%)|])(%d*)"))
	do
		index = index + 1
		if char == ">" or char == "<" or char == "+" or char == "-" or char == "," or char == "|"
		then
			num = num == "" and 1 or 0 + num
			if num ~= 0 --optimization: omit if value of operation is 0
			then
				tkns[index] = {char, num}
			end
		else
			tkns[index] = char
		end
	end
	return tkns
end


--argument: token table, output from function tokenize
--output:
--	nil if the token's syntax is incorrect (e.g. imbalanced brackets)
--	a syntax tree otherwise:
--		list of instructions, loop instructions are a nested table
_G[modname].parse = function(tkns)
	local loopindexes = {}
	local tree = {}
	local currentloop = tree
	local index = 0
	local lasttoken = nil --for optimizations
	local debug_output = {}
	
	for i, tkn in ipairs(tkns)
	do
		index = index + 1
		
		--handle loop instructions first
		if tkn == "[" or tkn == "("
		then
			currentloop[index] = {}
			currentloop = currentloop[index]
			currentloop[0] = true
			loopindexes[#loopindexes + 1] = index
			index = 0
			lasttoken = "["
		elseif tkn == "]" or tkn == ")"
		then
			if #loopindexes < 1
			then
				table.insert(debug_output, S("Error: unopened loop closed at token @1", i))
				return nil, debug_output
			end
			index = loopindexes[#loopindexes]
			--find loop under currentloop
			currentloop = tree
			loopindexes[#loopindexes] = nil
			for i, v in ipairs(loopindexes)
			do
				currentloop = currentloop[v]
			end
			--show warning for empty loops
			--	these either don't run or don't halt
			if lasttoken == "["
			then
				table.insert(debug_output, S("Warning: empty loop found at token @1: these either don't run or never halt.", i))
			end
			
			lasttoken = "]"
		else
			--perform optimizations
			if type(tkn) == "table" and not tkn[0] --don't do this for loops
			then
				if lasttoken == tkn[1]
				then
					--increase previous token's number so it only has to run once
					--e.g:
					--	tokens: {{>, 3}, {>, 1}}
					--	-> syntax tree: {{>, 4}}
					index = index - 1
					tkn[2] = tkn[2] + currentloop[index][2]
				end
			end
			--non-loop instructions are just written in the list
			currentloop[index] = tkn
			lasttoken = tkn[1]
		end
	end
	--make sure loops are closed
	if currentloop ~= tree
	then
		tree = nil
		table.insert(debug_output, S("Error: unclosed loop"))
	end
	if #debug_output == 0
	then
		table.insert(debug_output, S("No errors or warnings"))
	end
	return tree, debug_output
end


_G[modname].compute_step = function(working_tape, instr, pc, input)
	local restart = 1
	local headpos = working_tape.headpos
	local output
	
	if instr == '.'
	then
		--output
		output = working_tape[headpos] or 0
	elseif not instr
	then
		--loop or program end
		pc[#pc] = nil
		if #pc == 0
		then
			--halt
			restart = nil
		elseif working_tape[headpos] --re-enter loop if current value isn't 0
		then
			--loop
			pc[#pc + 1] = 0
		end
	elseif instr[1] == ','
	then
		--accept input
		if instr[2] == 1
		then
			working_tape[headpos] = input ~= 0 and input or nil
		elseif instr[2] == 2
		then
			--wait for input
			output = "wait"
		elseif instr[2] == 3
		then
			--random input in range [0, cval]
			local cval = working_tape[headpos] or 0
			if cval
			then
				cval = math.random(cval + 1) - 1
				working_tape[headpos] = cval ~= 0 and cval or nil
			end
		end
	elseif instr[1] == '|'
	then
		--reschedule timer
		restart = instr[2]
	elseif instr[1] == '+'
	then
		--increase
		local cval = working_tape[headpos]
		working_tape[headpos] = cval and cval + instr[2] or instr[2]
	elseif instr[1] == '-'
	then
		--decrease
		local cval = working_tape[headpos]
		local result = cval and math.max(cval - instr[2], 0) or 0
		--treat nil as 0 so the garbage collector can collect garbage
		working_tape[headpos] = result ~= 0 and result or nil
	elseif instr[1] == '>'
	then
		--move right
		headpos = headpos + instr[2]
	elseif instr[1] == '<'
	then
		--move left
		headpos = headpos - instr[2]
	else
		--enter loop
		if working_tape[headpos]
		then
			pc[#pc + 1] = 0
		end
	end
	working_tape.headpos = headpos
	
	--number of steps until next step is computed or nil if should halt
	return restart, output
end
