refactor systems to use cleaner dependency resolution

3 files changed, 246 insertions, 114 deletions

diff --git a/honey/ecs/ecs.lua b/honey/ecs/ecs.lua
index dda99cb..d7eb4ac 100644
--- a/honey/ecs/ecs.lua
+++ b/honey/ecs/ecs.lua
@@ -1,6 +1,6 @@
 math.randomseed(os.time())
 
-local glm = require 'honey.glm'
+local testing, glm = pcall(require, 'honey.glm')
 
 local module = {}
 setmetatable(module, {__index=_G})
@@ -87,9 +87,11 @@ function EntityDb.load(self, filename)
 			self:createEntity(id)
 			self:addComponents(id, components)
 		end,
-		Vec3 = glm.Vec3,
-		Mat4 = glm.Mat4,
 	}
+	if not testing then
+		env.Vec3 = glm.Vec3
+		env.Mat4 = glm.Mat4
+	end
 	local f, err = loadfile(filename)
 	if not f then error(err) end
 	setfenv(f, env)
@@ -209,6 +211,35 @@ function EntityDb.deleteEntity(self, id)
 end
 
 
+--===== Systems =====--
+
+System = {}
+System.__index = System
+
+function System.new(_, name, f)
+	local self = {
+		name = name,
+		f = f,
+		dependencies = {},
+	}
+	setmetatable(self, System)
+	return self
+end
+setmetatable(System, {__call=System.new})
+
+function System.addDependency(self, system)
+	self.dependencies[system.name] = true
+	return self
+end
+
+function System.addDependencies(self, systems)
+	for _, system in ipairs(systems) do
+		self:addDependency(system)
+	end
+	return self
+end
+
+
 --===== SystemDb =====--
 
 SystemDb = {}
@@ -218,7 +249,9 @@ SystemDb.__index = SystemDb
 function SystemDb.new(_, entityDb)
 	local self = {
 		systems = {},
-		sorted = {},
+		params = {},
+		sort = {},
+		dangling = {},
 		entityDb = entityDb,
 	}
 	setmetatable(self, SystemDb)
@@ -227,49 +260,90 @@ end
 setmetatable(SystemDb, {__call=SystemDb.new})
 
 
-local function systemId()
-	local template = "xx:xx:xx"
-	return string.gsub(template, "x", function(c)
-		return string.format("%x", random(0, 0xf))
-	end)
-end
+-- depth-first topological sort
+-- thank god for wikipedia
+local function tsort(systems)
+	local graph = {}
+	local count = 0
+	for _, system in pairs(systems) do
+		graph[system.name] = { name=system.name, dependencies=system.dependencies, tmark=false, pmark=false }
+		count = count+1
+	end
 
+	local sort = {}
+	local dangling = {}
 
-function SystemDb.addSystem(self, systemFunc, params)
-	local system
-	if type(systemFunc) == "table" then
-		system = systemFunc
-	else
-		local params = params or {}
-		params.db = self.entityDb
-		system = systemFunc(params)
+	local visit
+	visit = function(node)
+		if node == nil then
+			-- dangling dependency, ignore for now
+			return true
+		end
+		if node.pmark then return false end
+		if node.tmark then error("dependency cycle detected") end
+
+		node.tmark = true
+
+		for name in pairs(node.dependencies) do
+			local dangle = visit(graph[name])
+			if dangle then
+				dangling[name] = true
+			end
+		end
+
+		node.tmark = false
+		node.pmark = true
+		count = count-1
+		table.insert(sort, node.name)
 	end
 
-	local id = systemId()
-	self.systems[id] = system
-	table.insert(self.sorted, id)
-	self:sort()
-	return id
+	for _, node in pairs(graph) do
+		visit(node)
+		if count == 0 then break end
+	end
+
+	return sort, dangling
 end
 
 
-function SystemDb.sort(self)
-	table.sort(self.sorted, function(a, b) return (self.systems[a].priority or 100) < (self.systems[b].priority or 100) end)
+function SystemDb.addSystems(self, systems, params)
+	for _, system in ipairs(systems) do
+		self.systems[system.name] = system
+		self.params[system.name] = params
+	end
+	self.sort, self.dangling = tsort(self.systems)
+	return self
 end
 
 
 function SystemDb.update(self, dt)
-	for _, system in ipairs(self.sorted) do
-		self.systems[system]:update(dt)
+	-- check for dangling dependencies
+	local dangle = ""
+	for dependency in pairs(self.dangling) do
+		print(dependency)
+		dangle = dangle .. string.format(
+			"unresolved dangling dependency: %s\n",
+			dependency
+		)
+	end
+	if dangle ~= "" then
+		error(dangle)
+	end
+
+
+	for _, name in ipairs(self.sort) do
+		local system = self.systems[name]
+		local params = self.params[name]
+		system.f(self.db, dt, params)
 	end
 end
 
 
-function SystemDb.removeSystem(self, id)
-	self.systems[id] = nil
-	for i=#self.sorted,1,-1 do
-		if self.sorted[i] == id then table.remove(self.sorted, i) end
+function SystemDb.removeSystems(self, systems)
+	for _, system in pairs(systems) do
+		self.systems[system.name] = nil
 	end
+	self.sort, self.dangling = tsort(self.systems)
 end
 
 
diff --git a/honey/ecs/ecs.test.lua b/honey/ecs/ecs.test.lua
index 74e27dc..5d0b89e 100644
--- a/honey/ecs/ecs.test.lua
+++ b/honey/ecs/ecs.test.lua
@@ -17,59 +17,6 @@ end
 local ecs = require 'ecs'
 
 
---===== Component tests =====--
-
-local Component = ecs.Component
-
-test("factories work as expected", function()
-	local factory = Component.newFactory("health", { percent=100 })
-	local comp1 = factory()
-	assert(comp1.__type == "health", "bad component type for comp1")
-	assert(comp1.percent == 100, "bat percent for comp1")
-
-	local comp2 = factory{ percent=50 }
-	assert(comp2.__type == "health", "bad component type for comp2")
-	assert(comp2.percent == 50, "bad percent for comp2")
-
-	local success = pcall(function()
-		comp2.dne = 5
-	end)
-	assert(not success, "incorrectly succeeded in setting comp2.dne")
-
-	local success = pcall(function()
-		local comp3 = factory{ percent = 44, something = 2 }
-	end)
-	assert(not success, "incorrectly succeeded in creating comp3")
-end)
-
-
-test("components serialize as expected", function()
-	local position = Component.newFactory("position", { x=0, y=0, z=0 })
-	local comp = position{x=10, y=15, z=10}
-	local str = tostring(comp)
-	local tbl = (loadstring("return " .. str))()
-	assert(tbl.__type == "position", "bad type")
-	assert(tbl.x == 10, "bad x")
-	assert(tbl.y == 15, "bad y")
-	assert(tbl.z == 10, "bad z")
-end)
-
-
-test("components serialize successfully with subcomponents", function()
-	local position = Component.newFactory("position", { x=0, y=0, z=0 })
-	local player = Component.newFactory("player", { name="", position={} })
-
-	local p = player{ name="hannah", position=position{x=10, y=9, z=8} }
-	local tbl = (loadstring("return " .. tostring(p)))()
-	assert(tbl.__type == "player")
-	assert(tbl.name == "hannah")
-	assert(tbl.position.__type == "position")
-	assert(tbl.position.x == 10)
-	assert(tbl.position.y == 9)
-	assert(tbl.position.z == 8)
-end)
-
-
 --===== EntityDb tests =====--
 
 local EntityDb = ecs.EntityDb
@@ -233,47 +180,142 @@ end)
 
 local SystemDb = ecs.SystemDb
 
-test("addSystem() correctly sorts systems", function()
+test("addSystems() correctly sorts systems", function()
 	local sdb = SystemDb(nil)
 	local str = ""
-	sdb:addSystem(function () return {
-		update=function(self, dt) str = str .. "c" end,
-		priority = 3,
-	} end)
-	sdb:addSystem{
-		update=function(self, dt) str = "a" end,
-		priority = 1,
-	}
-	sdb:addSystem{
-		update=function(self, dt) str = str .. "b" end,
-		priority = 2,
-	}
+
+	local c = ecs.System("c", function(db, dt, params)
+		str = str .. "c"
+	end)
+
+	local a = ecs.System("a", function(db, dt, params)
+		str = str .. "a"
+	end)
+
+	local b = ecs.System("b", function(db, dt, params)
+		str = str .. "b"
+	end)
+
+	b:addDependency(a)
+	c:addDependency(b)
+
+	sdb:addSystems({c, a, b}, nil)
+
 	sdb:update(0)
 	assert(str == "abc")
 end)
 
 
-test("removeSystem() correctly handles things", function()
+test("addSystems() fails on dependency loop", function()
+	local a = ecs.System("a", nil)
+	local b = ecs.System("b", nil)
+	local c = ecs.System("c", nil)
+
+	a:addDependency(c)
+	b:addDependency(a)
+	c:addDependency(b)
+
+	sdb = SystemDb(nil)
+	local success = pcall(sdb,addSystems, sdb, {c, a, b}, nil)
+	assert(success == false)
+end)
+
+
+test("addSystems() correctly inserts additional systems", function()
+	local str = ""
 	local sdb = SystemDb(nil)
+
+	local c = ecs.System("c", function(db, dt, params)
+		str = str .. "c"
+	end)
+	local a = ecs.System("a", function(db, dt, params)
+		str = str .. "a"
+	end)
+	local b = ecs.System("b", function(db, dt, params)
+		str = str .. "b"
+	end)
+
+	b:addDependency(a)
+	c:addDependency(b)
+
+	sdb:addSystems({c, a, b}, nil)
+
+	local d = ecs.System("d", function(db, dt, params)
+		str = str .. "d"
+	end)
+	local e = ecs.System("e", function(db, dt, params)
+		str = str .. "e"
+	end)
+
+	d:addDependency(c)
+	e:addDependency(d)
+
+	sdb:addSystems({e, d}, nil)
+	sdb:update(0)
+	assert(str == "abcde")
+end)
+
+
+test("addSystems() correctly handles dangling dependencies", function()
 	local str = ""
-	sdb:addSystem(function () return {
-		update=function(self, dt) str = str .. "c" end,
-		priority = 3,
-	} end)
-	sdb:addSystem{
-		update=function(self, dt) str = "a" end,
-		priority = 1,
-	}
-	local id = sdb:addSystem{
-		update=function(self, dt) str = str .. "b" end,
-		priority = 2,
-	}
+	local sdb = SystemDb(nil)
+
+	local c = ecs.System("c", function(db, dt, params)
+		str = str .. "c"
+	end)
+	local a = ecs.System("a", function(db, dt, params)
+		str = str .. "a"
+	end)
+	local b = ecs.System("b", function(db, dt, params)
+		str = str .. "b"
+	end)
+
+	b:addDependency(a)
+	c:addDependency(b)
+
+	local d = ecs.System("d", function(db, dt, params)
+		str = str .. "d"
+	end)
+	local e = ecs.System("e", function(db, dt, params)
+		str = str .. "e"
+	end)
+
+	d:addDependency(c)
+	e:addDependency(d)
+
+	sdb:addSystems({e, d}, nil)
+
+	local success = pcall(sdb.update, sdb, nil)
+	assert(success == false)
+
+	sdb:addSystems({c, a, b}, nil)
+
 	sdb:update(0)
-	assert(str == "abc")
+	assert(str == "abcde")
+end)
+
+
+
+
+test("removeSystem() correctly handles things", function()
+	local sdb = SystemDb(nil)
+	local num = 1
+
+
+	local two = ecs.System("x2", function(db, dt, p) num = num*2 end)	
+	local three = ecs.System("x3", function(db, dt, p) num = num*3 end)	
+	local five = ecs.System("x5", function(db, dt, p) num = num*5 end)	
+
+	sdb:addSystems({two, three, five}, nil)
+
+	sdb:update(0)
+	assert(num == 30)
+
+	num = 1
 
-	sdb:removeSystem(id)
+	sdb:removeSystems({three})
 	sdb:update(1)
-	assert(str == "ac")
+	assert(num == 10)
 end)
 
 
diff --git a/honey/notes.md b/honey/notes.md
index 5dd25e7..16ccc49 100644
--- a/honey/notes.md
+++ b/honey/notes.md
@@ -13,11 +13,27 @@ assets are cached. each asset type has a module (e.g. `mesh`, `image`, `sound`,
 individual assets may have additional functions.
 
 
+entities
+--------
+
+entities are just identifiers. they are UUID strings. they index into components.
+
+
+components
+-----------
+
+components are data tables. they are supposed to contain only booleans, numbers, strings, and tables containing the other three types; they may contain additional state data (e.g. userdata, functions, etc) if they are prefixed by an underscore, and these things are transient and will have to be re-created on the next load from the bools, strings, numbers, and tables. the one exception to this rule is glm types; components *are* allowed to contain Vec3/Mat4/Quaternion/etc. (the glm types serialize nicely so this is not problematic.)
+
+
 systems
 -------
 
-systems are pure functions (NOT closures!!). they can be embedded in tables that indicate dependencies, i.e. which other systems *must* execute before them in order for things to work correctly. They have a signature like
+systems are pure functions (NOT closures!!). they must be embedded in tables that give them a name and indicate their dependencies, i.e. which other systems *must* execute before them in order for things to work correctly. They have a signature like
 
 > `system(db, dt, [params])`
 
 where params is a table. all parameters, including the params table, are passed in by the systemdb every frame; the system should NEVER close over them.
+
+(i may allow an exception to the system closure rule for the sake of physics update frequencies, but in general i would prefer to avoid them at all costs.)
+
+system modules should return an array of any systems needed for that conceptual system to work; the system db will add them all as one "system."