local function n() end local function W(n) end local function l(n) end local function X(n) end local function E(n,W)local l={}local X=n.parent repeat table.insert(l,X)X=X.parent until not X or X==W return l end local function J(n,W)local l=n.parent while l do if l==W then return true end l=l.parent end return false end local function B(n)local W={}for n,l in n do table.insert(W,E(l))end local l=table.remove(W,1)for n,l in l do local X=true for n,W in W do if not table.find(W,l)then X=false break end end if X then return l end end return end local function h(n)return B({n.source,n.target})end local function z(n)local W={}for n,l in n do if l.target then local n=h(l)while n do table.insert(W,1,n)n=n.current end end end return W end local function R(n)local W=z(n)for n,W in W do W:OnExit()end end local function s(n,W,l)table.insert(W,n)if n.type=="\099\111\109\112\111\117\110\100"then table.insert(l,n)s(n.initial,W,l)end end local function q(n,W,l)for n,W in E(n,W)do table.insert(l,W)end end local function P(n,W,l)for n,X in n do local E=h(X)s(X.target,W,l)q(X.target,E,W)end end local function I(n,W)local l={}local X={}local E={}P(n,l,X)for n,W in l do W:OnEntry()end end local function d() end local function v(n)local W={}for n,l in n do local X=false local E={}local B=z(W)for n,W in z({l})do if table.find(B,W)then if J(l.source,W)then table.insert(E,W)else X=true break end end end if not X then for n,l in E do table.remove(W,table.find(W,l))end table.insert(W,l)end end return W end local function c(n)for n,W in n.guards or{}do if not W()then return false end end return true end local function r(n)local W={}for n,l in n do if l.type~="\097\116\111\109\105\099"then continue end local X local E=l while E do local n=false for W,l in E.on._noevent do if c(l)then X=l n=true break end end if n then break end E=E.parent end if X then table.insert(W,X)end end W=v(W)return W end local function K(n,W)local l={}for W,X in W do if X.type~="\097\116\111\109\105\099"then continue end local E local J=X while J do local W=false for n,l in J.on[n.name]do if c(l)then E=l W=true break end end if W then break end J=J.parent end if E then table.insert(l,E)end end l=v(l)return l end local function a(l)while l.running do local n={}local X=false while l.running and not X do n=r()if#n==0 then if#l.internalQueue==0 then X=true else local W=l.internalQueue[1]table.remove(l.internalQueue,1)l._event=W n=K(W)end end if not(#n)==0 then W(n)end end if not l.running then break end if#l.internalQueue>0 then continue end local E=l.externalQueue[1]table.remove(l.externalQueue,1)if d(E)then l.running=false continue end l._event=E n=K(E)if not(#n)==0 then W(n)end task.wait()end n()end local function t(n,W,l)repeat n=n[n.initial]if n.OnEntry then if typeof(n.OnEntry)=="\102\117\110\099\116\105\111\110"then n.OnEntry(l)elseif typeof(n.OnEntry)=="\115\116\114\105\110\103"then W[n.OnEntry](l)end end n=n.substates until not n end local function A(n,W,l)for n,X in n do if X.OnInit then if typeof(X.OnInit)=="\102\117\110\099\116\105\111\110"then X.OnInit(l)elseif typeof(X.OnInit)=="\115\116\114\105\110\103"then W[X.OnInit](l)end end if X.substates then A(X.substates,W,l)end end end local function j(n,W)local l={}for W,X in W do if not X.id then error("\083\116\097\116\101 \100\111\101\115 \110\111\116 \104\097\118\101 \105\100\033")end l[W]=X l[W].parent=n if X.substates then l[W].type=X.type or"\099\111\109\112\111\117\110\100"l[W].substates=j(n,X.substates)else l[W].type="\097\116\111\109\105\099"end end return l end local H={}local L={}L.__index=L local function x(n)local W={}W.id=n.id W.initial=n.initial W.context={}W.running=false W.configuration={}W.statesToInvoke={}W.internalQueue={}W.externalQueue={}W.historyValue={}W.actions=n.actions W.guards=n.guards W.datamodel=j(W,n.states)return setmetatable(W,L)end local function p(n) end function L.Start(W,n)if W.running then error("\084\104\105\115 \109\097\099\104\105\110\101 \105\115 \097\108\114\101\097\100\121 \114\117\110\110\105\110\103\033")end p(W)A(W.datamodel,W.actions,W.context)W.running=true t(W.datamodel,W.actions,W.context)end return x
local function exitInterpreter() end

local function microstep(enabledTransitions) end

local function executeTransitionContent(enabledTransitions) end

local function isInFinalState(s) end

local function getProperAncestors(state1, state2)
	local orderedAncestors = {}
	local parent = state1.parent

	repeat
		table.insert(orderedAncestors, parent)
		parent = parent.parent
	until not parent or parent == state2

	return orderedAncestors
end

local function isDescendant(state1, state2)
	local parent = state1.parent

	while parent do
		if parent == state2 then
			return true
		end
		parent = parent.parent
	end

	return false
end

local function findLCCA(stateList)
	local properAncestorList = {}

	-- Populate the list of proper ancestors for each state
	for _, v in stateList do
		table.insert(properAncestorList, getProperAncestors(v))
	end

	-- Extract the head of properAncestorList
	local headOfProperAncestorList = table.remove(properAncestorList, 1)

	-- Iterate through the ancestors of the head
	for _, ancestor in headOfProperAncestorList do
		local isCommon = true

		-- Check if the ancestor is common across all lists
		for _, ancestorList in properAncestorList do
			if not table.find(ancestorList, ancestor) then
				isCommon = false
				break
			end
		end

		-- If the ancestor is common across all lists, return it
		if isCommon then
			return ancestor
		end
	end

	return -- If no common ancestor is found, return a default value (eventTransition.g., global ancestor)
end

local function getTransitionDomain(transition)
	return findLCCA({ transition.source, transition.target })
end

local function computeExitSet(enabledTransitions)
	local statesToExit = {}
	for i, t in enabledTransitions do
		if t.target then -- for targetless transitions only
			local child = getTransitionDomain(t) --initial point of exit is the LCCA of target and source
			while child do
				table.insert(statesToExit, 1, child) --ensures exit set is in ancestry order(from child to ancestor)
				child = child.current
			end
		end
	end
	return statesToExit
end

local function exitStates(enabledTransitions)
	local statesToExit = computeExitSet(enabledTransitions)

	for i, s in statesToExit do
		--assign history here in future
		s:OnExit()
	end
end

local function addDescendantStatesToEnter(state, statesToEnter, statesForDefaultEntry)
	table.insert(statesToEnter, state)
	if state.type == "compound" then
		table.insert(statesForDefaultEntry, state)
		addDescendantStatesToEnter(state.initial, statesToEnter, statesForDefaultEntry)
	end --elseif isParallelState
end

local function addAncestorStatesToEnter(state, ancestor, statesToEnter)
	for i, anc in getProperAncestors(state, ancestor) do
		table.insert(statesToEnter, anc)
		--if anc is a parallel state then fill descendants as well
	end
end

local function computeEntrySet(transitions, statesToEnter, statesForDefaultEntry)
	for i, t in transitions do
		local ancestor = getTransitionDomain(t)
		addDescendantStatesToEnter(t.target, statesToEnter, statesForDefaultEntry)
		addAncestorStatesToEnter(t.target, ancestor, statesToEnter)
	end
end

local function enterStates(enabledTransitions, context)
	local statesToEnter = {}
	local statesForDefaultEntry = {}

	local defaultHistoryContent = {}

	computeEntrySet(enabledTransitions, statesToEnter, statesForDefaultEntry)
	for i, s in statesToEnter do
		s:OnEntry()
	end
end

local function isCancelEvent() end

-- I'm not sure how this function works exactly, reference scxml before changing
local function removeConflictingTransitions(enabledTransitions)
	local filteredTransitions = {}

	for i, transition in enabledTransitions do
		local t1Preempted = false
		local transitionsToRemove = {}

		local filteredExitSet = computeExitSet(filteredTransitions)

		for _, state in computeExitSet({ transition }) do
			if table.find(filteredExitSet, state) then
				if isDescendant(transition.source, state) then
					table.insert(transitionsToRemove, state)
				else
					t1Preempted = true
					break
				end
			end
		end

		if not t1Preempted then
			for _, toRemove in transitionsToRemove do
				table.remove(filteredTransitions, table.find(filteredTransitions, toRemove))
			end
			table.insert(filteredTransitions, transition)
		end
	end

	return filteredTransitions
end

local function passedGuards(transition)
	for i, guard in transition.guards or {} do
		if not guard() then
			return false
		end
	end
	return true
end

local function selectEventlessTransitions(configuration)
	local enabledTransitions = {}

	for i, state in configuration do -- loops through active states
		if state.type ~= "atomic" then -- skips loop if state is not atomic, ensuring ancestry order
			continue
		end

		local transition
		local stateToQuery = state
		while stateToQuery do -- finds first eventless transition, from child to ancestor, that passes guards
			local broken = false

			for _, eventlessTransition in stateToQuery.on._noevent do
				if passedGuards(eventlessTransition) then
					transition = eventlessTransition
					broken = true
					break
				end
			end

			if broken then
				break
			end

			stateToQuery = stateToQuery.parent
		end
		if transition then
			table.insert(enabledTransitions, transition)
		end
	end

	enabledTransitions = removeConflictingTransitions(enabledTransitions)

	return enabledTransitions
end

local function selectTransitions(event, configuration)
	local enabledTransitions = {}

	for i, state in configuration do -- loops through active states
		if state.type ~= "atomic" then -- skips loop if state is not atomic, because atomic states are the base of ancestry order
			continue
		end

		local transition
		local stateToQuery = state
		while stateToQuery do -- finds first transition, from child to ancestor, that passes guards
			local broken = false

			for _, eventTransition in stateToQuery.on[event.name] do
				if passedGuards(eventTransition) then
					transition = eventTransition
					broken = true
					break
				end
			end

			if broken then
				break
			end

			stateToQuery = stateToQuery.parent
		end
		if transition then
			table.insert(enabledTransitions, transition)
		end
	end

	enabledTransitions = removeConflictingTransitions(enabledTransitions)

	return enabledTransitions
end

local function mainEventLoop(machine)
	while machine.running do
		local enabledTransitions = {}
		local macrostepDone = false
		--here we handle eventless transitions and transitions handled by internal events until macrostep is complete
		while machine.running and not macrostepDone do
			enabledTransitions = selectEventlessTransitions()
			if #enabledTransitions == 0 then
				if #machine.internalQueue == 0 then
					macrostepDone = true
				else
					local internalEvent = machine.internalQueue[1]
					table.remove(machine.internalQueue, 1)
					machine._event = internalEvent
					enabledTransitions = selectTransitions(internalEvent)
				end
			end
			if not #enabledTransitions == 0 then
				microstep(enabledTransitions)
			end
		end
		if not machine.running then --either we're in a final state, and we break out of the loop
			break
		end
		--or we've completed a macrostep, so we start a new macrostep by waiting for an external event

		if #machine.internalQueue > 0 then
			continue
		end

		local externalEvent = machine.externalQueue[1]
		table.remove(machine.externalQueue, 1)
		if isCancelEvent(externalEvent) then
			machine.running = false
			continue
		end
		machine._event = externalEvent

		enabledTransitions = selectTransitions(externalEvent)
		if not #enabledTransitions == 0 then
			microstep(enabledTransitions)
		end
		task.wait()
	end
	--if we get here it means we have reached a top-level final state or have been cancelled
	exitInterpreter()
end

local function enterInitialStates(state, actions, context)
	repeat
		state = state[state.initial]
		if state.OnEntry then
			if typeof(state.OnEntry) == "function" then
				state.OnEntry(context)
			elseif typeof(state.OnEntry) == "string" then
				actions[state.OnEntry](context)
			end
		end
		state = state.substates
	until not state
end

local function initializeDatamodel(datamodel, actions, context)
	for name, state in datamodel do
		if state.OnInit then
			if typeof(state.OnInit) == "function" then
				state.OnInit(context)
			elseif typeof(state.OnInit) == "string" then
				actions[state.OnInit](context)
			end
		end
		if state.substates then
			initializeDatamodel(state.substates, actions, context)
		end
	end
end

-- Add parent property to every state and ensure it is correctly types.
local function buildDatamodel(parent, document)
	local states = {}

	for name, state in document do -- in this loop I should check to ensure the necessary properties exist
		if not state.id then
			error("State does not have id!")
		end

		states[name] = state
		states[name].parent = parent

		if state.substates then
			states[name].type = state.type or "compound"
			states[name].substates = buildDatamodel(parent, state.substates)
		else
			states[name].type = "atomic"
		end
	end

	return states
end

local machineList = {}
local interpreter = {}
interpreter.__index = interpreter -- do fun metamagic to make sure users cant access any methods except what i want them to

local function createMachine(document)
	--ensure document is correctly typed
	local machine = {}

	machine.id = document.id
	machine.initial = document.initial
	machine.context = {} -- make immutable
	machine.running = false

	machine.configuration = {} --current configuration of active states
	machine.statesToInvoke = {}
	machine.internalQueue = {}
	machine.externalQueue = {}
	machine.historyValue = {}

	machine.actions = document.actions
	machine.guards = document.guards

	machine.datamodel = buildDatamodel(machine, document.states)

	return setmetatable(machine, interpreter)
end

local function mapOptionsToMachine(machine) end

function interpreter:Start(options)
	if self.running then
		error("This machine is already running!")
	end

	mapOptionsToMachine(self)

	initializeDatamodel(self.datamodel, self.actions, self.context)

	self.running = true

	enterInitialStates(self.datamodel, self.actions, self.context)
	--mainEventLoop(self)
end

return createMachine
