Merge branch 'dev' of https://github.com/xmake-io/xmake into dev

6 files changed, 273 insertions, 46 deletions

diff --git a/tests/modules/async/run_callback.lua b/tests/modules/async/run_callback.lua
new file mode 100644
index 000000000..21e75014b
--- /dev/null
+++ b/tests/modules/async/run_callback.lua
@@ -0,0 +1,19 @@
+import("core.base.scheduler")
+import("async.runjobs")
+
+function _jobfunc(index, total, opt)
+    print("%s: run job (%d/%d)", scheduler.co_running(), index, total)
+    local dt = os.mclock()
+    os.sleep(1000)
+    dt = os.mclock() - dt
+    print("%s: run job (%d/%d) end, progress: %s, dt: %d ms", scheduler.co_running(), index, total, opt.progress, dt)
+end
+
+function main()
+    print("==================================== test callback ====================================")
+    local t = os.mclock()
+    runjobs("test", _jobfunc, {total = 100, comax = 6, timeout = 1000, timer = function (running_jobs_indices)
+        print("%s: timeout (%d ms), running: %s", scheduler.co_running(), os.mclock() - t, table.concat(running_jobs_indices, ","))
+    end})
+end
+
diff --git a/tests/modules/async/run_jobgraph.lua b/tests/modules/async/run_jobgraph.lua
new file mode 100644
index 000000000..fe53a54c6
--- /dev/null
+++ b/tests/modules/async/run_jobgraph.lua
@@ -0,0 +1,53 @@
+import("core.base.scheduler")
+import("async.jobgraph")
+import("async.runjobs")
+
+function _jobfunc(index, total, opt)
+    print("%s: run job (%d/%d)", scheduler.co_running(), index, total)
+    local dt = os.mclock()
+    os.sleep(1000)
+    dt = os.mclock() - dt
+    print("%s: run job (%d/%d) end, progress: %s, dt: %d ms", scheduler.co_running(), index, total, opt.progress, dt)
+end
+
+function _test_basic()
+    print("==================================== test basic ====================================")
+    local jobs = jobgraph.new()
+    jobs:add("job/root", _jobfunc)
+    for i = 1, 3 do
+        jobs:add("job/" .. i, _jobfunc)
+        for j = 1, 50 do
+            jobs:add("job/" .. i .. "/" .. j, _jobfunc)
+            jobs:add_orders("job/" .. i .. "/" .. j, "job/" .. i, "job/root")
+        end
+    end
+    t = os.mclock()
+    runjobs("test", jobs, {comax = 6, timeout = 1000, timer = function (running_jobs_indices)
+        print("%s: timeout (%d ms), running: %s", scheduler.co_running(), os.mclock() - t, table.concat(running_jobs_indices, ","))
+    end})
+end
+
+function _test_group()
+    print("==================================== test group ====================================")
+    local jobs = jobgraph.new()
+    jobs:add("job/root", _jobfunc)
+    for i = 1, 3 do
+        jobs:add("job/" .. i, _jobfunc, {groups = "bar"})
+        jobs:group("foo", function ()
+            for j = 1, 50 do
+                jobs:add("job/" .. i .. "/" .. j, _jobfunc)
+            end
+        end)
+    end
+    jobs:add_orders("foo", "bar", "job/root")
+    t = os.mclock()
+    runjobs("test", jobs, {comax = 6, timeout = 1000, timer = function (running_jobs_indices)
+        print("%s: timeout (%d ms), running: %s", scheduler.co_running(), os.mclock() - t, table.concat(running_jobs_indices, ","))
+    end})
+end
+
+function main()
+    _test_basic()
+    _test_group()
+end
+
diff --git a/tests/modules/async/run_jobpool.lua b/tests/modules/async/run_jobpool.lua
new file mode 100644
index 000000000..5de54e36c
--- /dev/null
+++ b/tests/modules/async/run_jobpool.lua
@@ -0,0 +1,28 @@
+import("core.base.scheduler")
+import("private.async.jobpool")
+import("async.runjobs")
+
+function _jobfunc(index, total, opt)
+    print("%s: run job (%d/%d)", scheduler.co_running(), index, total)
+    local dt = os.mclock()
+    os.sleep(1000)
+    dt = os.mclock() - dt
+    print("%s: run job (%d/%d) end, progress: %s, dt: %d ms", scheduler.co_running(), index, total, opt.progress, dt)
+end
+
+function main()
+    print("==================================== test jobpool ====================================")
+    local jobs = jobpool.new()
+    local root = jobs:addjob("job/root", _jobfunc)
+    for i = 1, 3 do
+        local job = jobs:addjob("job/" .. i, _jobfunc, {rootjob = root})
+        for j = 1, 50 do
+            jobs:addjob("job/" .. i .. "/" .. j, _jobfunc, {rootjob = job})
+        end
+    end
+    t = os.mclock()
+    runjobs("test", jobs, {comax = 6, timeout = 1000, timer = function (running_jobs_indices)
+        print("%s: timeout (%d ms), running: %s", scheduler.co_running(), os.mclock() - t, table.concat(running_jobs_indices, ","))
+    end})
+end
+
diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua
index 63095be12..fe1d63e8d 100644
--- a/tests/modules/graph/test.lua
+++ b/tests/modules/graph/test.lua
@@ -1,6 +1,6 @@
 import("core.base.graph")
 
-function test_topological_sort(t)
+function test_topo_sort(t)
     local edges = {
         {0, 5},
         {0, 2},
@@ -18,7 +18,7 @@ function test_topological_sort(t)
     for _, e in ipairs(edges) do
         dag:add_edge(e[1], e[2])
     end
-    local order_path = dag:topological_sort()
+    local order_path = dag:topo_sort()
     local orders = {}
     for i, v in ipairs(order_path) do
         orders[v] = i
@@ -28,7 +28,7 @@ function test_topological_sort(t)
     end
 
     dag = dag:reverse()
-    order_path = dag:topological_sort()
+    order_path = dag:topo_sort()
     orders = {}
     for i, v in ipairs(order_path) do
         orders[v] = i
@@ -38,6 +38,138 @@ function test_topological_sort(t)
     end
 end
 
+function test_paritail_topo_sort(t)
+    local function partiail_topo_sort(dag)
+        dag:partial_topo_sort_reset()
+
+        local node, has_cycle
+        local order_vertices = {}
+        while true do
+            node, has_cycle = dag:partial_topo_sort_next()
+            if node then
+                table.insert(order_vertices, node)
+                dag:partial_topo_sort_remove(node)
+            else
+                if has_cycle then
+                    raise("has cycle!")
+                end
+                break
+            end
+        end
+
+        return order_vertices, has_cycle
+    end
+
+    local edges = {
+        {0, 5},
+        {0, 2},
+        {0, 1},
+        {3, 6},
+        {3, 5},
+        {3, 4},
+        {5, 4},
+        {6, 4},
+        {6, 0},
+        {3, 2},
+        {1, 4},
+        {2, 9},
+    }
+    local dag = graph.new(true)
+    for _, e in ipairs(edges) do
+        dag:add_edge(e[1], e[2])
+    end
+    local order_path = partiail_topo_sort(dag)
+    local orders = {}
+    for i, v in ipairs(order_path) do
+        orders[v] = i
+    end
+    for _, e in ipairs(edges) do
+        t:require(orders[e[1]] < orders[e[2]])
+    end
+
+    dag = dag:reverse()
+    order_path = partiail_topo_sort(dag)
+    orders = {}
+    for i, v in ipairs(order_path) do
+        orders[v] = i
+    end
+    for _, e in ipairs(edges) do
+        t:require(orders[e[1]] > orders[e[2]])
+    end
+end
+
+function test_paritail_topo_sort_dynamic(t)
+    local function partiail_topo_sort(dag)
+        dag:partial_topo_sort_reset()
+
+        local node, has_cycle
+        local order_vertices = {}
+        local dynamic_adjust = false
+        while true do
+            node, has_cycle = dag:partial_topo_sort_next()
+            if node then
+                if not dynamic_adjust then
+                    dag:add_edge(1, 4)
+                    dag:remove_vertex(6)
+                end
+                table.insert(order_vertices, node)
+                dag:partial_topo_sort_remove(node)
+                if not dynamic_adjust then
+                    dag:add_edge(2, 9)
+                    dynamic_adjust = true
+                end
+            else
+                if has_cycle then
+                    raise("has cycle!")
+                end
+                break
+            end
+        end
+
+        assert(#order_vertices == #dag:vertices(), "vertices count not matched, %d != %d", #order_vertices, #dag:vertices())
+        return order_vertices, has_cycle
+    end
+
+    local edges = {
+        {0, 5},
+        {0, 2},
+        {0, 1},
+        {3, 6},
+        {3, 5},
+        {3, 4},
+        {5, 4},
+        {6, 4},
+        {6, 0},
+        {3, 2},
+    }
+    local dag = graph.new(true)
+    for _, e in ipairs(edges) do
+        dag:add_edge(e[1], e[2])
+    end
+    local order_path = partiail_topo_sort(dag)
+    local orders = {}
+    for i, v in ipairs(order_path) do
+        orders[v] = i
+    end
+    edges = {
+        {0, 5},
+        {0, 2},
+        {0, 1},
+        -- {3, 6},
+        {3, 5},
+        {3, 4},
+        {5, 4},
+        -- {6, 4},
+        -- {6, 0},
+        {3, 2},
+        {1, 4},
+        {2, 9}
+    }
+    for _, e in ipairs(edges) do
+        t:require(orders[e[1]] < orders[e[2]])
+    end
+end
+
 function test_find_cycle(t)
     local edges = {
         {9, 1},
@@ -52,5 +184,8 @@ function test_find_cycle(t)
     end
     local cycle = dag:find_cycle()
     t:are_equal(cycle, {1, 6, 0})
+
+    local _, has_cycle = dag:topo_sort()
+    t:require(has_cycle)
 end
 
diff --git a/tests/modules/queue/test.lua b/tests/modules/queue/test.lua
new file mode 100644
index 000000000..b577e04c9
--- /dev/null
+++ b/tests/modules/queue/test.lua
@@ -0,0 +1,35 @@
+import("core.base.queue")
+
+function test_push(t)
+    local d = queue.new()
+    d:push(1)
+    d:push(2)
+    d:push(3)
+    d:push(4)
+    d:push(5)
+    t:are_equal(d:first(), 1)
+    t:are_equal(d:last(), 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item, idx)
+        idx = idx + 1
+    end
+end
+
+function test_pop(t)
+    local d = queue.new()
+    d:push(1)
+    d:push(2)
+    d:push(3)
+    d:push(4)
+    d:push(5)
+    d:pop()
+    t:are_equal(d:first(), 2)
+    t:are_equal(d:last(), 5)
+    local idx = 2
+    for item in d:items() do
+        t:are_equal(item, idx)
+        idx = idx + 1
+    end
+end
+
diff --git a/tests/modules/scheduler/runjobs.lua b/tests/modules/scheduler/runjobs.lua
deleted file mode 100644
index 4e2a98cc0..000000000
--- a/tests/modules/scheduler/runjobs.lua
+++ /dev/null
@@ -1,43 +0,0 @@
-import("core.base.scheduler")
-import("private.async.jobpool")
-import("async.runjobs")
-
-function _jobfunc(index, total, opt)
-    print("%s: run job (%d/%d)", scheduler.co_running(), index, total)
-    local dt = os.mclock()
-    os.sleep(1000)
-    dt = os.mclock() - dt
-    print("%s: run job (%d/%d) end, progress: %s, dt: %d ms", scheduler.co_running(), index, total, opt.progress, dt)
-end
-
-function main()
-
-    -- test callback
-    print("==================================== test callback ====================================")
-    local t = os.mclock()
-    runjobs("test", _jobfunc, {total = 100, comax = 6, timeout = 1000, timer = function (running_jobs_indices)
-        print("%s: timeout (%d ms), running: %s", scheduler.co_running(), os.mclock() - t, table.concat(running_jobs_indices, ","))
-    end})
-
-    -- test jobs
-    print("==================================== test jobs ====================================")
-    local jobs = jobpool.new()
-    local root = jobs:addjob("job/root", function (index, total, opt)
-        _jobfunc(index, total, opt)
-    end)
-    for i = 1, 3 do
-        local job = jobs:addjob("job/" .. i, function (index, total, opt)
-            _jobfunc(index, total, opt)
-        end, {rootjob = root})
-        for j = 1, 50 do
-            jobs:addjob("job/" .. i .. "/" .. j, function (index, total, opt)
-                _jobfunc(index, total, opt)
-            end, {rootjob = job})
-        end
-    end
-    t = os.mclock()
-    runjobs("test", jobs, {comax = 6, timeout = 1000, timer = function (running_jobs_indices)
-        print("%s: timeout (%d ms), running: %s", scheduler.co_running(), os.mclock() - t, table.concat(running_jobs_indices, ","))
-    end})
-end
-