dependency resolver function

3 files changed, 71 insertions, 36 deletions

diff --git a/awall/dependency.lua b/awall/dependency.lua
new file mode 100644
index 0000000..475c412
--- /dev/null
+++ b/awall/dependency.lua
@@ -0,0 +1,40 @@
+--[[
+Dependency order resolver for Alpine Wall
+Copyright (C) 2012-2013 Kaarle Ritvanen
+Licensed under the terms of GPL2
+]]--
+
+module(..., package.seeall)
+
+local util = require('awall.util')
+
+function order(items)
+   local visited = {}
+   local res = {}
+
+   local function visit(key)
+      if util.contains(res, key) then return end
+      if visited[key] then return key end
+      visited[key] = true
+
+      local after = util.list(items[key].after)
+      for k, v in pairs(items) do
+	 if util.contains(v.before, key) then table.insert(after, k) end
+      end
+      for i, k in ipairs(after) do
+	 if items[k] then
+	    local ek = visit(k)
+	    if ek ~= nil then return ek end
+	 end
+      end
+
+      table.insert(res, key)
+   end
+
+   for i, k in util.sortedkeys(items) do
+      local ek = visit(k)
+      if ek ~= nil then return ek end
+   end
+
+   return res
+end
diff --git a/awall/policy.lua b/awall/policy.lua
index 997a4b9..2ecfdc2 100644
--- a/awall/policy.lua
+++ b/awall/policy.lua
@@ -1,6 +1,6 @@
 --[[
 Policy file handling for Alpine Wall
-Copyright (C) 2012 Kaarle Ritvanen
+Copyright (C) 2012-2013 Kaarle Ritvanen
 Licensed under the terms of GPL2
 ]]--
 
@@ -10,6 +10,7 @@ require 'json'
 require 'lfs'
 require 'lpc'
 
+require 'awall.dependency'
 require 'awall.object'
 require 'awall.util'
 
@@ -139,47 +140,32 @@ end
 
 function PolicySet:load()
    
-   local input = {}
-   local source = {}
-   local polnames = {}
    local policies = {}
 
    local function require(name, fname)
       if policies[name] then return end
-      table.insert(polnames, name)
-      policies[name] = self:loadJSON(name, fname)
-      for i, iname in util.listpairs(policies[name].import) do
-	 require(iname)
-      end
-   end
 
-   for i, pol in ipairs(list(self.autodirs)) do require(unpack(pol)) end
+      local policy = self:loadJSON(name, fname)
+      policies[name] = policy
 
+      if not policy.after then policy.after = policy.import end
+      for i, iname in util.listpairs(policy.import) do require(iname) end
+   end
 
-   local pending = {}
-   local imported = {}
+   for i, pol in ipairs(list(self.autodirs)) do require(unpack(pol)) end
 
-   local function import(name)
 
-      if util.contains(imported, name) then return end
-      if util.contains(pending, name) then
-	 error('Circular ordering directives: '..name)
-      end
-      table.insert(pending, name)
+   local order = awall.dependency.order(policies)
+   if type(order) ~= 'table' then
+      error('Circular ordering directives: '..order)
+   end
 
-      local data = policies[name]
 
-      local after = util.list(data.after or data.import)
-      for pname, policy in pairs(policies) do
-	 if util.contains(util.list(policy.before), name) then
-	    table.insert(after, pname)
-	 end
-      end
-      for i, pname in ipairs(after) do import(pname) end
+   local input = {}
+   local source = {}
 
-      table.insert(imported, name)
-      
-      for cls, objs in pairs(data) do
+   for i, name in ipairs(order) do
+      for cls, objs in pairs(policies[name]) do
 	 if not util.contains({'description', 'import', 'after', 'before'},
 			      cls) then
 	    if not source[cls] then source[cls] = {} end
@@ -203,10 +189,7 @@ function PolicySet:load()
       end
    end
 
-   table.sort(polnames)
-   for i, name in ipairs(polnames) do import(name) end
-
-   return PolicyConfig.new(input, source, polnames)
+   return PolicyConfig.new(input, source, util.keys(policies))
 end
 
 
diff --git a/awall/util.lua b/awall/util.lua
index dad057e..38dab88 100644
--- a/awall/util.lua
+++ b/awall/util.lua
@@ -1,6 +1,6 @@
 --[[
 Utility module for Alpine Wall
-Copyright (C) 2012 Kaarle Ritvanen
+Copyright (C) 2012-2013 Kaarle Ritvanen
 Licensed under the terms of GPL2
 ]]--
 
@@ -36,10 +36,22 @@ function maplist(var, func)
 end
 
 function contains(tbl, value)
-   for k, v in pairs(tbl) do if v == value then return true end end
+   for k, v in listpairs(tbl) do if v == value then return true end end
    return false
 end
 
+function keys(tbl)
+   local res = {}
+   for k, v in pairs(tbl) do table.insert(res, k) end
+   return res
+end
+
+function sortedkeys(tbl)
+   local res = keys(tbl)
+   table.sort(res)
+   return ipairs(res)
+end
+
 function extend(tbl1, tbl2)
    for i, var in listpairs(tbl2) do table.insert(tbl1, var) end
 end