From 00ebba39f7e81d2b52bfb3be458f9825e6d7c070 Mon Sep 17 00:00:00 2001 From: ruki Date: Fri, 14 Mar 2025 00:53:08 +0800 Subject: add jobgraph stub --- tests/modules/async/jobgraph.lua | 7 ++++++ tests/modules/async/runjobs.lua | 43 +++++++++++++++++++++++++++++++++++++ tests/modules/scheduler/runjobs.lua | 43 ------------------------------------- 3 files changed, 50 insertions(+), 43 deletions(-) create mode 100644 tests/modules/async/jobgraph.lua create mode 100644 tests/modules/async/runjobs.lua delete mode 100644 tests/modules/scheduler/runjobs.lua (limited to 'tests/modules') diff --git a/tests/modules/async/jobgraph.lua b/tests/modules/async/jobgraph.lua new file mode 100644 index 000000000..dd8cb05f8 --- /dev/null +++ b/tests/modules/async/jobgraph.lua @@ -0,0 +1,7 @@ +import("core.base.scheduler") +import("async.jobgraph") + +function main() + +end + diff --git a/tests/modules/async/runjobs.lua b/tests/modules/async/runjobs.lua new file mode 100644 index 000000000..4e2a98cc0 --- /dev/null +++ b/tests/modules/async/runjobs.lua @@ -0,0 +1,43 @@ +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 + 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 - -- cgit v1.3.1 From 1621db050a13474f4d79d02c4d306013770d35b4 Mon Sep 17 00:00:00 2001 From: ruki Date: Tue, 18 Mar 2025 23:55:15 +0800 Subject: add jobgraph.new --- tests/modules/async/jobgraph.lua | 4 ++-- xmake/modules/async/jobgraph.lua | 12 +++++++++--- 2 files changed, 11 insertions(+), 5 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/async/jobgraph.lua b/tests/modules/async/jobgraph.lua index dd8cb05f8..7a0b87c65 100644 --- a/tests/modules/async/jobgraph.lua +++ b/tests/modules/async/jobgraph.lua @@ -1,7 +1,7 @@ -import("core.base.scheduler") import("async.jobgraph") function main() - + local gh = jobgraph.new() + print(gh) end diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index 519544cf2..3fd36194a 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -20,17 +20,23 @@ -- imports import("core.base.object") +import("core.base.list") import("core.base.graph") -- define module -local jobgraph = jobgraph or object {_init = {"_size"}} +local jobgraph = jobgraph or object {_init = {"_jobs", "_graph"}} + +-- get jobs +function jobgraph:jobs() + return self._jobs +end -- tostring function jobgraph:__tostring() - return "" + return string.format("", self:jobs():size()) end -- new a jobgraph function new() - return jobgraph {0} + return jobgraph {list.new(), graph.new(true)} end -- cgit v1.3.1 From 6785ce5822f298ce64684548dfc9d35ec8dd5030 Mon Sep 17 00:00:00 2001 From: ruki Date: Wed, 19 Mar 2025 23:03:25 +0800 Subject: improve runjobs tests --- tests/modules/async/jobgraph.lua | 7 ------ tests/modules/async/run_callback.lua | 19 ++++++++++++++++ tests/modules/async/run_jobgraph.lua | 28 +++++++++++++++++++++++ tests/modules/async/run_jobpool.lua | 28 +++++++++++++++++++++++ tests/modules/async/runjobs.lua | 43 ------------------------------------ xmake/modules/async/jobgraph.lua | 15 +++++++++++++ 6 files changed, 90 insertions(+), 50 deletions(-) delete mode 100644 tests/modules/async/jobgraph.lua create mode 100644 tests/modules/async/run_callback.lua create mode 100644 tests/modules/async/run_jobgraph.lua create mode 100644 tests/modules/async/run_jobpool.lua delete mode 100644 tests/modules/async/runjobs.lua (limited to 'tests/modules') diff --git a/tests/modules/async/jobgraph.lua b/tests/modules/async/jobgraph.lua deleted file mode 100644 index 7a0b87c65..000000000 --- a/tests/modules/async/jobgraph.lua +++ /dev/null @@ -1,7 +0,0 @@ -import("async.jobgraph") - -function main() - local gh = jobgraph.new() - print(gh) -end - 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..bcf5be2fd --- /dev/null +++ b/tests/modules/async/run_jobgraph.lua @@ -0,0 +1,28 @@ +import("core.base.scheduler") +import("async.jobgraph") +import("async.runjobs") + +function _jobfunc(job, opt) + print("%s: run job (%s)", scheduler.co_running(), job.name) + local dt = os.mclock() + os.sleep(1000) + dt = os.mclock() - dt + print("%s: run job (%s) end, progress: %s, dt: %d ms", scheduler.co_running(), job.name, opt.progress, dt) +end + +function main() + print("==================================== test jobpool ====================================") + local jobs = jobgraph.new() + jobs:add_job("job/root", _jobfunc) + for i = 1, 3 do + jobs:add_job("job/" .. i, _jobfunc) + for j = 1, 50 do + jobs:add_job("job/" .. i .. "/" .. j, _jobfunc) + 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/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/async/runjobs.lua b/tests/modules/async/runjobs.lua deleted file mode 100644 index 4e2a98cc0..000000000 --- a/tests/modules/async/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 - diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index 3fd36194a..30513ae56 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -31,6 +31,21 @@ function jobgraph:jobs() return self._jobs end +-- add a job to the jobgraph +-- +-- e.g. +-- jobgraph:add_job("xxx", function (job, opt) +-- end) +-- +-- @param name the job name +-- @param run the job run command/script +-- @param opt the job options +-- +function jobgraph:add_job(name, run, opt) + local job = {name = name, run = run, opt = opt} + self:jobs():insert(job) +end + -- tostring function jobgraph:__tostring() return string.format("", self:jobs():size()) -- cgit v1.3.1 From f8346ab6e40bdcf9506f1400f74860bbcea764ff Mon Sep 17 00:00:00 2001 From: ruki Date: Wed, 19 Mar 2025 23:23:55 +0800 Subject: improve jobgraph tests --- tests/modules/async/run_jobgraph.lua | 13 ++++++----- xmake/modules/async/jobgraph.lua | 44 ++++++++++++++++++++++++++++++++---- xmake/modules/async/runjobs.lua | 5 ++++ 3 files changed, 51 insertions(+), 11 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/async/run_jobgraph.lua b/tests/modules/async/run_jobgraph.lua index bcf5be2fd..ec9c9175f 100644 --- a/tests/modules/async/run_jobgraph.lua +++ b/tests/modules/async/run_jobgraph.lua @@ -2,22 +2,23 @@ import("core.base.scheduler") import("async.jobgraph") import("async.runjobs") -function _jobfunc(job, opt) - print("%s: run job (%s)", scheduler.co_running(), job.name) +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 (%s) end, progress: %s, dt: %d ms", scheduler.co_running(), job.name, opt.progress, 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 = jobgraph.new() - jobs:add_job("job/root", _jobfunc) + jobs:add("job/root", _jobfunc) for i = 1, 3 do - jobs:add_job("job/" .. i, _jobfunc) + jobs:add("job/" .. i, _jobfunc) for j = 1, 50 do - jobs:add_job("job/" .. i .. "/" .. j, _jobfunc) + jobs:add("job/" .. i .. "/" .. j, _jobfunc) + jobs:add_deps("job/" .. i .. "/" .. j, "job/" .. i, "job/root") end end t = os.mclock() diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index 30513ae56..313bc2d11 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -24,7 +24,16 @@ import("core.base.list") import("core.base.graph") -- define module -local jobgraph = jobgraph or object {_init = {"_jobs", "_graph"}} +local jobqueue = jobqueue or object {_init = {"_jobgraph"}} +local jobgraph = jobgraph or object {_init = {"_jobs", "_graph", "_dirty"}} + +-- remove the given job from the job queue +function jobqueue:remove(job) +end + +-- get a free job from the job queue +function jobqueue:getfree() +end -- get jobs function jobgraph:jobs() @@ -34,24 +43,49 @@ end -- add a job to the jobgraph -- -- e.g. --- jobgraph:add_job("xxx", function (job, opt) +-- jobgraph:add("xxx", function (index, total, opt) -- end) -- -- @param name the job name -- @param run the job run command/script -- @param opt the job options -- -function jobgraph:add_job(name, run, opt) +function jobgraph:add(name, run, opt) local job = {name = name, run = run, opt = opt} self:jobs():insert(job) + self._dirty = true +end + +-- remove a given job +function jobgraph:remove(name) + self._dirty = true +end + +-- add job deps, e.g. add_deps(a, b, c, ...): a -> b -> c, ... +function jobgraph:add_deps(...) + local deps = table.pack(...) +end + +-- add jog group +function jobgraph:add_group(name, callback) +end + +-- build a job queue +function jobgraph:build() + return jobqueue {self} +end + +-- get job size +function jobgraph:size() + return self:jobs():size() end -- tostring function jobgraph:__tostring() - return string.format("", self:jobs():size()) + return string.format("", self:size()) end -- new a jobgraph function new() - return jobgraph {list.new(), graph.new(true)} + return jobgraph {list.new(), graph.new(true), false} end diff --git a/xmake/modules/async/runjobs.lua b/xmake/modules/async/runjobs.lua index 0c2a6f366..959eb1e77 100644 --- a/xmake/modules/async/runjobs.lua +++ b/xmake/modules/async/runjobs.lua @@ -64,6 +64,11 @@ function main(name, jobs, opt) local group_name = name local jobs_cb = type(jobs) == "function" and jobs or nil assert(timeout < 60000, "runjobs: invalid timeout!") + + -- build jobs queue + if jobs.build then + jobs = jobs:build() + end assert(jobs, "runjobs: no jobs!") -- show waiting tips? -- cgit v1.3.1 From bc4f14679956d6eac336cb23d72e5e91c189a5bf Mon Sep 17 00:00:00 2001 From: ruki Date: Wed, 19 Mar 2025 23:35:27 +0800 Subject: add deps for jobgraph --- tests/modules/async/run_jobgraph.lua | 2 +- xmake/modules/async/jobgraph.lua | 31 ++++++++++++++++++++++++------- 2 files changed, 25 insertions(+), 8 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/async/run_jobgraph.lua b/tests/modules/async/run_jobgraph.lua index ec9c9175f..a3e1edeb3 100644 --- a/tests/modules/async/run_jobgraph.lua +++ b/tests/modules/async/run_jobgraph.lua @@ -11,7 +11,7 @@ function _jobfunc(index, total, opt) end function main() - print("==================================== test jobpool ====================================") + print("==================================== test jobgraph ====================================") local jobs = jobgraph.new() jobs:add("job/root", _jobfunc) for i = 1, 3 do diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index 612e56dee..684b7d7d8 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -25,7 +25,7 @@ import("core.base.graph") -- define module local jobqueue = jobqueue or object {_init = {"_jobgraph"}} -local jobgraph = jobgraph or object {_init = {"_jobs", "_size", "_deps", "_dirty"}} +local jobgraph = jobgraph or object {_init = {"_name", "_jobs", "_size", "_deps", "_dirty"}} -- build the job queue function jobqueue:_build() @@ -87,9 +87,21 @@ end -- add job deps, e.g. add_deps(a, b, c, ...): a -> b -> c, ... function jobgraph:add_deps(...) - -- TODO - local deps = table.pack(...) - self._dirty = true + local prev + local dirty + local jobs = self._jobs + local deps = self._deps + for _, name in ipairs(table.pack(...)) do + local curr = assert(jobs[name], "job(%s) not found in jobgraph(%s)", name, self) + if prev then + deps:add_edge(prev, curr) + dirty = true + end + prev = curr + end + if dirty then + self._dirty = true + end end -- add jog group @@ -108,6 +120,11 @@ function jobgraph:jobs() return self._jobs end +-- get jobgraph name +function jobgraph:name() + return self._name +end + -- get job size function jobgraph:size() return self._size @@ -115,10 +132,10 @@ end -- tostring function jobgraph:__tostring() - return string.format("", self:size()) + return string.format("", self:name() or "anonymous", self:size()) end -- new a jobgraph -function new() - return jobgraph {{}, 0, graph.new(true), false} +function new(name) + return jobgraph {name, {}, 0, graph.new(true), false} end -- cgit v1.3.1 From a278d3bd3e74027e7fd1f878c7d8c991caf1a75f Mon Sep 17 00:00:00 2001 From: ruki Date: Thu, 20 Mar 2025 23:16:51 +0800 Subject: improve to find cycle --- tests/modules/graph/test.lua | 3 +++ xmake/core/base/graph.lua | 19 ++++++++++++---- xmake/core/tool/builder.lua | 11 ++++++---- xmake/modules/async/jobgraph.lua | 25 +++++++++++----------- .../modules/modules_support/dependency_scanner.lua | 25 +++++++++++----------- 5 files changed, 51 insertions(+), 32 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index 63095be12..4bbefe069 100644 --- a/tests/modules/graph/test.lua +++ b/tests/modules/graph/test.lua @@ -52,5 +52,8 @@ function test_find_cycle(t) end local cycle = dag:find_cycle() t:are_equal(cycle, {1, 6, 0}) + + local _, has_cycle = dag:topological_sort() + t:require(has_cycle) end diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index bf6b724ce..3b88a642a 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -125,29 +125,40 @@ function graph:topological_sort(opt) for _, v in ipairs(self:vertices()) do visited[v] = false end + local in_stack = {} local order_vertices = {} local function dfs(v) visited[v] = true + in_stack[v] = true local edges = self:adjacent_edges(v) if edges then for _, e in ipairs(edges) do local w = e:other(v) if not visited[w] then - dfs(w) + if dfs(w) then + return true + end + elseif in_stack[w] then + return true end end end + in_stack[v] = false table.insert(order_vertices, v) end + local has_cycle = false for _, v in ipairs(self:vertices()) do if not visited[v] then - dfs(v) + if dfs(v) then + has_cycle = true + break + end end end if opt.reverse then - return order_vertices + return order_vertices, has_cycle else - return table.reverse(order_vertices) + return table.reverse(order_vertices), has_cycle end end diff --git a/xmake/core/tool/builder.lua b/xmake/core/tool/builder.lua index 2bf4efc1f..b0f802237 100644 --- a/xmake/core/tool/builder.lua +++ b/xmake/core/tool/builder.lua @@ -668,11 +668,14 @@ function builder:_sort_links_of_items(items, opt) gh:add_edge(k, v) end if not gh:empty() then - local cycle = gh:find_cycle() - if cycle then - utils.warning("cycle links found in add_linkorders(): %s", table.concat(cycle, " -> ")) + local has_cycle + links, has_cycle = gh:topological_sort() + if has_cycle then + local cycle = gh:find_cycle() + if cycle then + utils.warning("cycle links found in add_linkorders(): %s", table.concat(cycle, " -> ")) + end end - links = gh:topological_sort() end end diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index 9bf98f7b5..6d96ff0ff 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -47,20 +47,21 @@ function jobqueue:_build() local dag = graph._dag local queue = self._queue - -- check circular dependencies - local cycle = dag:find_cycle() - if cycle then - local names = {} - for _, job in ipairs(cycle) do - table.insert(names, job.name) - end - table.insert(names, names[1]) - raise("%s: circular job dependency detected!\n%s", graph, table.concat(names, "\n -> ")) - end - -- build job queue queue:clear() - for _, job in ipairs(dag:topological_sort({reverse = true})) do + local order_jobs, has_cycle = dag:topological_sort({reverse = true}) + if has_cycle then + local cycle = dag:find_cycle() + if cycle then + local names = {} + for _, job in ipairs(cycle) do + table.insert(names, job.name) + end + table.insert(names, names[1]) + raise("%s: circular job dependency detected!\n%s", graph, table.concat(names, "\n -> ")) + end + end + for _, job in ipairs(order_jobs) do job._deps = nil job._parents = nil queue:insert(job) diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index 9d552d0fd..df8c85441 100644 --- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua +++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua @@ -222,7 +222,7 @@ function _generate_dependencies(target, sourcebatch, opt) local changed = false if opt.batchjobs then local jobs = option.get("jobs") or os.default_njob() - runjobs(target:name() .. "_module_dependency_scanner", function(index) + runjobs(target:name() .. "_module_dependency_scanner", function(index) local sourcefile = sourcebatch.sourcefiles[index] changed = _dependency_scanner(target).generate_dependency_for(target, sourcefile, opt) or changed end, {comax = jobs, total = #sourcebatch.sourcefiles}) @@ -415,19 +415,20 @@ function sort_modules_by_dependencies(target, objectfiles, modules, opt) for _, e in ipairs(edges) do dag:add_edge(e[1], e[2]) end - local cycle = dag:find_cycle() - if cycle then - local names = {} - for _, objectfile in ipairs(cycle) do - local name, _, cppfile = compiler_support.get_provided_module(modules[objectfile]) + local objectfiles_sorted, has_cycle = dag:topological_sort({reverse = true}) + if has_cycle then + local cycle = dag:find_cycle() + if cycle then + local names = {} + for _, objectfile in ipairs(cycle) do + local name, _, cppfile = compiler_support.get_provided_module(modules[objectfile]) + table.insert(names, name or cppfile) + end + local name, _, cppfile = compiler_support.get_provided_module(modules[cycle[1]]) table.insert(names, name or cppfile) + raise("circular modules dependency detected!\n%s", table.concat(names, "\n -> import ")) end - local name, _, cppfile = compiler_support.get_provided_module(modules[cycle[1]]) - table.insert(names, name or cppfile) - raise("circular modules dependency detected!\n%s", table.concat(names, "\n -> import ")) end - - local objectfiles_sorted = table.reverse(dag:topological_sort()) local objectfiles_sorted_set = hashset.from(objectfiles_sorted) for _, objectfile in ipairs(objectfiles) do if not objectfiles_sorted_set:has(objectfile) then @@ -465,7 +466,7 @@ function sort_modules_by_dependencies(target, objectfiles, modules, opt) end end end - if insert then + if insert then table.insert(build_objectfiles, objectfile) table.insert(link_objectfiles, objectfile) elseif external and not external.from_moduleonly then -- cgit v1.3.1 From 741da62196bcb64c88e386f1a769462211c63b4e Mon Sep 17 00:00:00 2001 From: ruki Date: Fri, 21 Mar 2025 23:03:29 +0800 Subject: add queue and improve graph --- tests/modules/graph/test.lua | 8 +- tests/modules/queue/test.lua | 35 ++++ xmake/core/base/graph.lua | 216 +++++++++++++++++++-- xmake/core/base/queue.lua | 125 ++++++++++++ .../sandbox/modules/import/core/base/queue.lua | 22 +++ xmake/core/tool/builder.lua | 2 +- xmake/modules/async/jobgraph.lua | 54 ++---- xmake/modules/cli/amalgamate.lua | 2 +- .../modules/modules_support/dependency_scanner.lua | 3 +- 9 files changed, 406 insertions(+), 61 deletions(-) create mode 100644 tests/modules/queue/test.lua create mode 100644 xmake/core/base/queue.lua create mode 100644 xmake/core/sandbox/modules/import/core/base/queue.lua (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index 4bbefe069..33e1f3fa7 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 @@ -53,7 +53,7 @@ function test_find_cycle(t) local cycle = dag:find_cycle() t:are_equal(cycle, {1, 6, 0}) - local _, has_cycle = dag:topological_sort() + 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/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index ffcd815c5..448eebb88 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -19,9 +19,10 @@ -- -- load modules -local table = require("base/table") -local list = require("base/list") -local object = require("base/object") +local table = require("base/table") +local queue = require("base/queue") +local object = require("base/object") +local hashset = require("base/hashset") -- define module local graph = graph or object { _init = {"_directed"} } {true} @@ -58,6 +59,9 @@ function graph:clear() self._edges = {} self._adjacent_edges = {} self._edges_map = {} + + -- clear partial topological sort state + self:partial_topo_sort_reset() end -- is empty? @@ -116,10 +120,171 @@ function graph:remove_vertex(v) end end end + + -- reset partial topological sort state since graph structure changed + self:partial_topo_sort_reset() + end +end + +-- check if there's a cycle in the remaining unprocessed nodes +function graph:_check_cycle_in_remaining() + -- if all remaining nodes have in-degree > 0, we have a cycle + if self._topo_remaining_count > 0 and self._topo_remaining_count == self._topo_non_zero_indegree_count then + self._topo_has_cycle = true + return true end + return false end --- topological sort, use Kahn's algorithm +-- reset partial topological sort state +function graph:partial_topo_sort_reset() + self._topo_in_progress = false + self._topo_in_degree = nil + self._topo_queue = nil + self._topo_processed = nil + self._topo_has_cycle = nil + self._topo_remaining_count = nil + self._topo_non_zero_indegree_count = nil +end + +-- get next batch of nodes in topological order with limit +-- +-- @param limit the maximum number of nodes to return +-- @return array of nodes with zero in-degree, empty when complete +-- @return has_cycle indicates if a cycle was detected +-- +-- e.g. +-- +-- add_edge(a, b) -- a depend on b +-- add_edge(b, c) -- b depend on c +-- +-- local batch1, has_cycle = g:partial_topo_sort_next(1) -- returns {c} +-- local batch2, has_cycle = g:partial_topo_sort_next(1) -- returns {b} +-- local batch3, has_cycle = g:partial_topo_sort_next(1) -- returns {a} +-- local batch4, has_cycle = g:partial_topo_sort_next(1) -- returns {} (empty, all done) +-- +function graph:partial_topo_sort_next(limit) + if not self:is_directed() then + return {}, false + end + + limit = limit or math.huge + + -- check if we already detected a cycle + if self._topo_has_cycle then + return {}, true + end + + -- initialize topological sort state if not already in progress + if not self._topo_in_progress then + -- calculate in-degree for each vertex + self._topo_in_degree = {} + for _, v in ipairs(self:vertices()) do + self._topo_in_degree[v] = 0 + end + + -- count incoming edges for each vertex + for _, v in ipairs(self:vertices()) do + local edges = self:adjacent_edges(v) + if edges then + for _, e in ipairs(edges) do + if e:from() == v then + local w = e:to() + self._topo_in_degree[w] = (self._topo_in_degree[w] or 0) + 1 + end + end + end + end + + -- initialize queue with vertices that have no incoming edges + self._topo_queue = queue.new() + for _, v in ipairs(self:vertices()) do + if self._topo_in_degree[v] == 0 then + self._topo_queue:push(v) + end + end + + -- track processed vertices + self._topo_processed = hashset.new() + self._topo_in_progress = true + + -- track counts for efficient cycle detection + self._topo_remaining_count = #self:vertices() + self._topo_non_zero_indegree_count = self._topo_remaining_count - self._topo_queue:size() + + -- quick cycle detection: if no nodes have zero in-degree, we have a cycle + if self._topo_queue:empty() and self._topo_remaining_count > 0 then + self._topo_has_cycle = true + return {}, true + end + end + + -- return empty batch if queue is empty (all processed or cycle detected) + if self._topo_queue:empty() then + -- check if all vertices were processed + local processed_count = self._topo_processed:size() + self._topo_has_cycle = processed_count ~= #self:vertices() + + -- if this is the first call and we detect a cycle, mark as complete + if processed_count == 0 then + self._topo_in_progress = false + end + + return {}, self._topo_has_cycle + end + + -- collect up to 'limit' nodes with zero in-degree + local batch = {} + while not self._topo_queue:empty() and #batch < limit do + local v = self._topo_queue:pop() + table.insert(batch, v) + self._topo_processed:insert(v) + self._topo_remaining_count = self._topo_remaining_count - 1 + end + + -- update in-degrees based on the nodes in this batch + for _, v in ipairs(batch) do + local edges = self:adjacent_edges(v) + if edges then + for _, e in ipairs(edges) do + if e:from() == v then + local w = e:to() + self._topo_in_degree[w] = self._topo_in_degree[w] - 1 + + -- update non-zero in-degree count + if self._topo_in_degree[w] == 0 then + self._topo_non_zero_indegree_count = self._topo_non_zero_indegree_count - 1 + + -- if in-degree becomes zero, add to queue for next batch + if not self._topo_processed:has(w) then + self._topo_queue:push(w) + end + end + end + end + end + end + + -- early cycle detection - if all remaining nodes have in-degree > 0 + if self:_check_cycle_in_remaining() then + return batch, true + end + + -- if queue is now empty and all vertices processed, reset state + if self._topo_queue:empty() then + local processed_count = self._topo_processed:size() + if processed_count == #self:vertices() then + self._topo_in_progress = false + else + -- if queue is empty but we still have unprocessed nodes, we have a cycle + self._topo_has_cycle = true + end + end + + return batch, self._topo_has_cycle +end + +-- topological sort, use kahn's algorithm -- -- e.g. -- @@ -127,8 +292,35 @@ end -- add_edge(b, c) -- b depend on c -- -- it will return {c, b, a} -function graph:topological_sort(opt) - opt = opt or {} +--[[ +function graph:topo_sort() + if not self:is_directed() then + return + end + + -- reset partial sort state to ensure we start fresh + self:partial_topo_sort_reset() + + local order_vertices = {} + local batch_size = math.huge -- no limit, get all at once + + -- get all nodes in one go + local batch, has_cycle = self:partial_topo_sort_next(batch_size) + while #batch > 0 do + for _, v in ipairs(batch) do + table.insert(order_vertices, v) + end + batch, has_cycle = self:partial_topo_sort_next(batch_size) + + -- quick exit if cycle is detected + if has_cycle then + break + end + end + + return order_vertices, has_cycle +end]] +function graph:topo_sort() if not self:is_directed() then return end @@ -153,10 +345,10 @@ function graph:topological_sort(opt) end -- queue of vertices with no incoming edges (no dependencies) - local queue = list.new() + local queue = queue.new() for _, v in ipairs(self:vertices()) do if in_degree[v] == 0 then - queue:insert(v) + queue:push(v) end end @@ -166,7 +358,7 @@ function graph:topological_sort(opt) -- process queue while not queue:empty() do -- remove a vertex with no incoming edges - local v = queue:remove_first() + local v = queue:pop() table.insert(order_vertices, v) -- for each outgoing edge, remove it and update in-degrees @@ -178,7 +370,7 @@ function graph:topological_sort(opt) in_degree[w] = in_degree[w] - 1 -- if in-degree becomes zero, add to queue if in_degree[w] == 0 then - queue:insert(w) + queue:push(w) end end end @@ -263,6 +455,9 @@ function graph:add_edge(from, to) edges_map[to][from] = true end table.insert(self._edges, e) + + -- reset partial topological sort state since graph structure changed + self:partial_topo_sort_reset() end -- has the given edge? @@ -340,4 +535,3 @@ end -- return module: graph return graph - diff --git a/xmake/core/base/queue.lua b/xmake/core/base/queue.lua new file mode 100644 index 000000000..dbdc1d87a --- /dev/null +++ b/xmake/core/base/queue.lua @@ -0,0 +1,125 @@ +--!A cross-platform build utility based on Lua +-- +-- Licensed under the Apache License, Version 2.0 (the "License"); +-- you may not use this file except in compliance with the License. +-- You may obtain a copy of the License at +-- +-- http://www.apache.org/licenses/LICENSE-2.0 +-- +-- Unless required by applicable law or agreed to in writing, software +-- distributed under the License is distributed on an "AS IS" BASIS, +-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +-- See the License for the specific language governing permissions and +-- limitations under the License. +-- +-- Copyright (C) 2015-present, TBOOX Open Source Group. +-- +-- @author ruki +-- @file queue.lua +-- + +-- load modules +local object = require("base/object") + +-- define module +local queue = queue or object {_init = {"_first", "_last"}} {1, 0} + +-- clear queue +function queue:clear() + self._first = 1 + self._last = 0 +end + +-- push item to queue +function queue:push(item) + local last = self._last + 1 + self._last = last + self[last] = item +end + +-- pop item from queue +function queue:pop() + local first = self._first + if first > self._last then + return nil + end + + local value = self[first] + self[first] = nil + self._first = first + 1 + return value +end + +-- get queue size +function queue:size() + return self._last - self._first + 1 +end + +-- is queue empty? +function queue:empty() + return self._first > self._last +end + +-- peek the first item of queue +function queue:first() + if self._first > self._last then + return nil + end + return self[self._first] +end + +-- peek the last item of queue +function queue:last() + if self._first > self._last then + return nil + end + return self[self._last] +end + +-- iterator for all items (forward) +-- +-- e.g. +-- +-- for item in queue:items() do +-- print(item) +-- end +-- +function queue:items() + local index = self._first - 1 + local last = self._last + return function() + index = index + 1 + if index <= last then + return self[index] + end + end +end + +-- iterator for all items (reverse) +function queue:ritems() + local index = self._last + 1 + local first = self._first + return function() + index = index - 1 + if index >= first then + return self[index] + end + end +end + +-- clone queue +function queue:clone() + local q = queue.new() + for i = self._first, self._last do + q:push(self[i]) + end + return q +end + +-- new queue +function queue.new() + return queue() +end + +-- return module: queue +return queue diff --git a/xmake/core/sandbox/modules/import/core/base/queue.lua b/xmake/core/sandbox/modules/import/core/base/queue.lua new file mode 100644 index 000000000..aab0a8214 --- /dev/null +++ b/xmake/core/sandbox/modules/import/core/base/queue.lua @@ -0,0 +1,22 @@ +--!A cross-platform build utility based on Lua +-- +-- Licensed under the Apache License, Version 2.0 (the "License"); +-- you may not use this file except in compliance with the License. +-- You may obtain a copy of the License at +-- +-- http://www.apache.org/licenses/LICENSE-2.0 +-- +-- Unless required by applicable law or agreed to in writing, software +-- distributed under the License is distributed on an "AS IS" BASIS, +-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +-- See the License for the specific language governing permissions and +-- limitations under the License. +-- +-- Copyright (C) 2015-present, TBOOX Open Source Group. +-- +-- @author ruki +-- @file queue.lua +-- + +-- return module +return require("base/queue") diff --git a/xmake/core/tool/builder.lua b/xmake/core/tool/builder.lua index b0f802237..0e85911eb 100644 --- a/xmake/core/tool/builder.lua +++ b/xmake/core/tool/builder.lua @@ -669,7 +669,7 @@ function builder:_sort_links_of_items(items, opt) end if not gh:empty() then local has_cycle - links, has_cycle = gh:topological_sort() + links, has_cycle = gh:topo_sort() if has_cycle then local cycle = gh:find_cycle() if cycle then diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index ca8725b28..4a0dac110 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -25,18 +25,20 @@ import("core.base.graph") import("core.base.hashset") -- define module -local jobqueue = jobqueue or object {_init = {"_jobgraph", "_queue"}} +local jobqueue = jobqueue or object {_init = {"_jobgraph"}} local jobgraph = jobgraph or object {_init = {"_name", "_jobs", "_size", "_dag", "_dirty"}} --- build the job queue -function jobqueue:_build() +-- remove the given job from the job queue +function jobqueue:remove(job) +end + +-- get a free job from the job queue +function jobqueue:getfree() local graph = self._jobgraph local dag = graph._dag - local queue = self._queue -- build job queue - queue:clear() - local order_jobs, has_cycle = dag:topological_sort() + local order_jobs, has_cycle = dag:partial_topo_sort_next(1) if has_cycle then local cycle = dag:find_cycle() if cycle then @@ -48,42 +50,8 @@ function jobqueue:_build() raise("%s: circular job dependency detected!\n%s", graph, table.concat(names, "\n -> ")) end end - for _, job in ipairs(order_jobs) do - print("insert", job.name) - queue:insert(job) - end -end - --- update the job queue -function jobqueue:_update() - local graph = self._jobgraph - if graph._dirty then - self:_build() - graph._dirty = false - end -end - --- remove the given job from the job queue -function jobqueue:remove(job) - local queue = self._queue - print("remove", job.name) - queue:remove(job) - -- TODO remove deps -end - --- get a free job from the job queue -function jobqueue:getfree() - self:_update() - - local queue = self._queue - if queue:empty() then - return - end - - -- TODO - for job in queue:ritems() do - print("get free job", job.name) - return job + if order_jobs then + return table.unwrap(order_jobs) end end @@ -150,7 +118,7 @@ end -- build a job queue function jobgraph:build() - return jobqueue {self, list.new()} + return jobqueue {self} end -- get jobs diff --git a/xmake/modules/cli/amalgamate.lua b/xmake/modules/cli/amalgamate.lua index 8c7ec6fd7..d0a5ba40c 100644 --- a/xmake/modules/cli/amalgamate.lua +++ b/xmake/modules/cli/amalgamate.lua @@ -96,7 +96,7 @@ function _generate_file(target, inputpaths, outputpath, uniqueid) _generate_include_graph(target, inputpaths, gh, {}) -- sort file paths and remove root path - local filepaths = gh:topological_sort() + local filepaths = gh:topo_sort() table.remove(filepaths, 1) -- generate amalgamate file diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index df8c85441..94c14e60d 100644 --- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua +++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua @@ -415,7 +415,7 @@ function sort_modules_by_dependencies(target, objectfiles, modules, opt) for _, e in ipairs(edges) do dag:add_edge(e[1], e[2]) end - local objectfiles_sorted, has_cycle = dag:topological_sort({reverse = true}) + local objectfiles_sorted, has_cycle = dag:topo_sort() if has_cycle then local cycle = dag:find_cycle() if cycle then @@ -429,6 +429,7 @@ function sort_modules_by_dependencies(target, objectfiles, modules, opt) raise("circular modules dependency detected!\n%s", table.concat(names, "\n -> import ")) end end + objectfiles_sorted = table.reverse(objectfiles_sorted) local objectfiles_sorted_set = hashset.from(objectfiles_sorted) for _, objectfile in ipairs(objectfiles) do if not objectfiles_sorted_set:has(objectfile) then -- cgit v1.3.1 From 43ea0c1fb1d9954e065f3dfdb7bd93493d5d9e38 Mon Sep 17 00:00:00 2001 From: ruki Date: Fri, 21 Mar 2025 23:05:26 +0800 Subject: add partial topo test --- tests/modules/graph/test.lua | 59 ++++++++++++++++++++ xmake/core/base/graph.lua | 125 +++++++++++++++++-------------------------- 2 files changed, 109 insertions(+), 75 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index 33e1f3fa7..3d5a0aede 100644 --- a/tests/modules/graph/test.lua +++ b/tests/modules/graph/test.lua @@ -38,6 +38,65 @@ function test_topo_sort(t) end end +function test_paritail_topo_sort(t) + local function partiail_topo_sort(dag) + dag:partial_topo_sort_reset() + + local order_vertices = {} + local batch_size = math.huge + local batch, has_cycle = dag:partial_topo_sort_next(batch_size) + while #batch > 0 do + for _, v in ipairs(batch) do + table.insert(order_vertices, v) + end + batch, has_cycle = dag:partial_topo_sort_next(batch_size) + + if has_cycle then + 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}, + } + 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_find_cycle(t) local edges = { {9, 1}, diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index 448eebb88..496bffeba 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -122,15 +122,15 @@ function graph:remove_vertex(v) end -- reset partial topological sort state since graph structure changed - self:partial_topo_sort_reset() + self._partial_topo_dirty = true end end -- check if there's a cycle in the remaining unprocessed nodes function graph:_check_cycle_in_remaining() -- if all remaining nodes have in-degree > 0, we have a cycle - if self._topo_remaining_count > 0 and self._topo_remaining_count == self._topo_non_zero_indegree_count then - self._topo_has_cycle = true + if self._partial_topo_remaining_count > 0 and self._partial_topo_remaining_count == self._partial_topo_non_zero_indegree_count then + self._partial_topo_has_cycle = true return true end return false @@ -138,13 +138,14 @@ end -- reset partial topological sort state function graph:partial_topo_sort_reset() - self._topo_in_progress = false - self._topo_in_degree = nil - self._topo_queue = nil - self._topo_processed = nil - self._topo_has_cycle = nil - self._topo_remaining_count = nil - self._topo_non_zero_indegree_count = nil + self._partial_topo_in_progress = false + self._partial_topo_in_degree = nil + self._partial_topo_queue = nil + self._partial_topo_processed = nil + self._partial_topo_has_cycle = nil + self._partial_topo_remaining_count = nil + self._partial_topo_non_zero_indegree_count = nil + self._partial_topo_dirty = false end -- get next batch of nodes in topological order with limit @@ -168,19 +169,23 @@ function graph:partial_topo_sort_next(limit) return {}, false end + if self._partial_topo_dirty then + self:partial_topo_sort_reset() + end + limit = limit or math.huge -- check if we already detected a cycle - if self._topo_has_cycle then + if self._partial_topo_has_cycle then return {}, true end -- initialize topological sort state if not already in progress - if not self._topo_in_progress then + if not self._partial_topo_in_progress then -- calculate in-degree for each vertex - self._topo_in_degree = {} + self._partial_topo_in_degree = {} for _, v in ipairs(self:vertices()) do - self._topo_in_degree[v] = 0 + self._partial_topo_in_degree[v] = 0 end -- count incoming edges for each vertex @@ -190,56 +195,56 @@ function graph:partial_topo_sort_next(limit) for _, e in ipairs(edges) do if e:from() == v then local w = e:to() - self._topo_in_degree[w] = (self._topo_in_degree[w] or 0) + 1 + self._partial_topo_in_degree[w] = (self._partial_topo_in_degree[w] or 0) + 1 end end end end -- initialize queue with vertices that have no incoming edges - self._topo_queue = queue.new() + self._partial_topo_queue = queue.new() for _, v in ipairs(self:vertices()) do - if self._topo_in_degree[v] == 0 then - self._topo_queue:push(v) + if self._partial_topo_in_degree[v] == 0 then + self._partial_topo_queue:push(v) end end -- track processed vertices - self._topo_processed = hashset.new() - self._topo_in_progress = true + self._partial_topo_processed = hashset.new() + self._partial_topo_in_progress = true -- track counts for efficient cycle detection - self._topo_remaining_count = #self:vertices() - self._topo_non_zero_indegree_count = self._topo_remaining_count - self._topo_queue:size() + self._partial_topo_remaining_count = #self:vertices() + self._partial_topo_non_zero_indegree_count = self._partial_topo_remaining_count - self._partial_topo_queue:size() -- quick cycle detection: if no nodes have zero in-degree, we have a cycle - if self._topo_queue:empty() and self._topo_remaining_count > 0 then - self._topo_has_cycle = true + if self._partial_topo_queue:empty() and self._partial_topo_remaining_count > 0 then + self._partial_topo_has_cycle = true return {}, true end end -- return empty batch if queue is empty (all processed or cycle detected) - if self._topo_queue:empty() then + if self._partial_topo_queue:empty() then -- check if all vertices were processed - local processed_count = self._topo_processed:size() - self._topo_has_cycle = processed_count ~= #self:vertices() + local processed_count = self._partial_topo_processed:size() + self._partial_topo_has_cycle = processed_count ~= #self:vertices() -- if this is the first call and we detect a cycle, mark as complete if processed_count == 0 then - self._topo_in_progress = false + self._partial_topo_in_progress = false end - return {}, self._topo_has_cycle + return {}, self._partial_topo_has_cycle end -- collect up to 'limit' nodes with zero in-degree local batch = {} - while not self._topo_queue:empty() and #batch < limit do - local v = self._topo_queue:pop() + while not self._partial_topo_queue:empty() and #batch < limit do + local v = self._partial_topo_queue:pop() table.insert(batch, v) - self._topo_processed:insert(v) - self._topo_remaining_count = self._topo_remaining_count - 1 + self._partial_topo_processed:insert(v) + self._partial_topo_remaining_count = self._partial_topo_remaining_count - 1 end -- update in-degrees based on the nodes in this batch @@ -249,15 +254,15 @@ function graph:partial_topo_sort_next(limit) for _, e in ipairs(edges) do if e:from() == v then local w = e:to() - self._topo_in_degree[w] = self._topo_in_degree[w] - 1 + self._partial_topo_in_degree[w] = self._partial_topo_in_degree[w] - 1 -- update non-zero in-degree count - if self._topo_in_degree[w] == 0 then - self._topo_non_zero_indegree_count = self._topo_non_zero_indegree_count - 1 + if self._partial_topo_in_degree[w] == 0 then + self._partial_topo_non_zero_indegree_count = self._partial_topo_non_zero_indegree_count - 1 -- if in-degree becomes zero, add to queue for next batch - if not self._topo_processed:has(w) then - self._topo_queue:push(w) + if not self._partial_topo_processed:has(w) then + self._partial_topo_queue:push(w) end end end @@ -271,17 +276,17 @@ function graph:partial_topo_sort_next(limit) end -- if queue is now empty and all vertices processed, reset state - if self._topo_queue:empty() then - local processed_count = self._topo_processed:size() + if self._partial_topo_queue:empty() then + local processed_count = self._partial_topo_processed:size() if processed_count == #self:vertices() then - self._topo_in_progress = false + self._partial_topo_in_progress = false else -- if queue is empty but we still have unprocessed nodes, we have a cycle - self._topo_has_cycle = true + self._partial_topo_has_cycle = true end end - return batch, self._topo_has_cycle + return batch, self._partial_topo_has_cycle end -- topological sort, use kahn's algorithm @@ -292,34 +297,6 @@ end -- add_edge(b, c) -- b depend on c -- -- it will return {c, b, a} ---[[ -function graph:topo_sort() - if not self:is_directed() then - return - end - - -- reset partial sort state to ensure we start fresh - self:partial_topo_sort_reset() - - local order_vertices = {} - local batch_size = math.huge -- no limit, get all at once - - -- get all nodes in one go - local batch, has_cycle = self:partial_topo_sort_next(batch_size) - while #batch > 0 do - for _, v in ipairs(batch) do - table.insert(order_vertices, v) - end - batch, has_cycle = self:partial_topo_sort_next(batch_size) - - -- quick exit if cycle is detected - if has_cycle then - break - end - end - - return order_vertices, has_cycle -end]] function graph:topo_sort() if not self:is_directed() then return @@ -352,10 +329,8 @@ function graph:topo_sort() end end - -- result list for topologically sorted vertices - local order_vertices = {} - -- process queue + local order_vertices = {} while not queue:empty() do -- remove a vertex with no incoming edges local v = queue:pop() @@ -457,7 +432,7 @@ function graph:add_edge(from, to) table.insert(self._edges, e) -- reset partial topological sort state since graph structure changed - self:partial_topo_sort_reset() + self._partial_topo_dirty = true end -- has the given edge? -- cgit v1.3.1 From 093894844d4d7e7e58a7a78d36f04cf59b95ff31 Mon Sep 17 00:00:00 2001 From: ruki Date: Fri, 21 Mar 2025 23:12:16 +0800 Subject: improve tests --- tests/modules/graph/test.lua | 6 ++---- xmake/core/base/graph.lua | 3 +-- 2 files changed, 3 insertions(+), 6 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index 3d5a0aede..da6218f14 100644 --- a/tests/modules/graph/test.lua +++ b/tests/modules/graph/test.lua @@ -43,14 +43,12 @@ function test_paritail_topo_sort(t) dag:partial_topo_sort_reset() local order_vertices = {} - local batch_size = math.huge - local batch, has_cycle = dag:partial_topo_sort_next(batch_size) + local batch, has_cycle = dag:partial_topo_sort_next() while #batch > 0 do for _, v in ipairs(batch) do table.insert(order_vertices, v) end - batch, has_cycle = dag:partial_topo_sort_next(batch_size) - + batch, has_cycle = dag:partial_topo_sort_next() if has_cycle then break end diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index 496bffeba..31e7038d1 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -165,6 +165,7 @@ end -- local batch4, has_cycle = g:partial_topo_sort_next(1) -- returns {} (empty, all done) -- function graph:partial_topo_sort_next(limit) + limit = limit or math.huge if not self:is_directed() then return {}, false end @@ -173,8 +174,6 @@ function graph:partial_topo_sort_next(limit) self:partial_topo_sort_reset() end - limit = limit or math.huge - -- check if we already detected a cycle if self._partial_topo_has_cycle then return {}, true -- cgit v1.3.1 From 53d124455837e9afa2c78e41b88f0f973fdf83e7 Mon Sep 17 00:00:00 2001 From: ruki Date: Fri, 21 Mar 2025 23:16:34 +0800 Subject: get parital single node --- tests/modules/graph/test.lua | 12 +++++------- xmake/core/base/graph.lua | 41 +++++++++++++++++++---------------------- 2 files changed, 24 insertions(+), 29 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index da6218f14..c9584a69a 100644 --- a/tests/modules/graph/test.lua +++ b/tests/modules/graph/test.lua @@ -42,16 +42,14 @@ function test_paritail_topo_sort(t) local function partiail_topo_sort(dag) dag:partial_topo_sort_reset() + local node, has_cycle local order_vertices = {} - local batch, has_cycle = dag:partial_topo_sort_next() - while #batch > 0 do - for _, v in ipairs(batch) do - table.insert(order_vertices, v) - end - batch, has_cycle = dag:partial_topo_sort_next() - if has_cycle then + while true do + node, has_cycle = dag:partial_topo_sort_next() + if node == nil or has_cycle then break end + table.insert(order_vertices, node) end return order_vertices, has_cycle diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index 31e7038d1..b2d22a3c4 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -148,7 +148,7 @@ function graph:partial_topo_sort_reset() self._partial_topo_dirty = false end --- get next batch of nodes in topological order with limit +-- get next node in topological order -- -- @param limit the maximum number of nodes to return -- @return array of nodes with zero in-degree, empty when complete @@ -159,15 +159,15 @@ end -- add_edge(a, b) -- a depend on b -- add_edge(b, c) -- b depend on c -- --- local batch1, has_cycle = g:partial_topo_sort_next(1) -- returns {c} --- local batch2, has_cycle = g:partial_topo_sort_next(1) -- returns {b} --- local batch3, has_cycle = g:partial_topo_sort_next(1) -- returns {a} --- local batch4, has_cycle = g:partial_topo_sort_next(1) -- returns {} (empty, all done) +-- local node1, has_cycle = g:partial_topo_sort_next() -- returns c +-- local node2, has_cycle = g:partial_topo_sort_next() -- returns b +-- local node3, has_cycle = g:partial_topo_sort_next() -- returns a +-- local node4, has_cycle = g:partial_topo_sort_next() -- returns nil (empty, all done) -- function graph:partial_topo_sort_next(limit) limit = limit or math.huge if not self:is_directed() then - return {}, false + return nil, false end if self._partial_topo_dirty then @@ -176,7 +176,7 @@ function graph:partial_topo_sort_next(limit) -- check if we already detected a cycle if self._partial_topo_has_cycle then - return {}, true + return nil, true end -- initialize topological sort state if not already in progress @@ -219,7 +219,7 @@ function graph:partial_topo_sort_next(limit) -- quick cycle detection: if no nodes have zero in-degree, we have a cycle if self._partial_topo_queue:empty() and self._partial_topo_remaining_count > 0 then self._partial_topo_has_cycle = true - return {}, true + return nil, true end end @@ -234,24 +234,21 @@ function graph:partial_topo_sort_next(limit) self._partial_topo_in_progress = false end - return {}, self._partial_topo_has_cycle + return nil, self._partial_topo_has_cycle end - -- collect up to 'limit' nodes with zero in-degree - local batch = {} - while not self._partial_topo_queue:empty() and #batch < limit do - local v = self._partial_topo_queue:pop() - table.insert(batch, v) - self._partial_topo_processed:insert(v) + -- get one node with zero in-degree + local node + if not self._partial_topo_queue:empty() then + node = self._partial_topo_queue:pop() + self._partial_topo_processed:insert(node) self._partial_topo_remaining_count = self._partial_topo_remaining_count - 1 - end - -- update in-degrees based on the nodes in this batch - for _, v in ipairs(batch) do - local edges = self:adjacent_edges(v) + -- update in-degrees based on the nodes in this batch + local edges = self:adjacent_edges(node) if edges then for _, e in ipairs(edges) do - if e:from() == v then + if e:from() == node then local w = e:to() self._partial_topo_in_degree[w] = self._partial_topo_in_degree[w] - 1 @@ -271,7 +268,7 @@ function graph:partial_topo_sort_next(limit) -- early cycle detection - if all remaining nodes have in-degree > 0 if self:_check_cycle_in_remaining() then - return batch, true + return node, true end -- if queue is now empty and all vertices processed, reset state @@ -285,7 +282,7 @@ function graph:partial_topo_sort_next(limit) end end - return batch, self._partial_topo_has_cycle + return node, self._partial_topo_has_cycle end -- topological sort, use kahn's algorithm -- cgit v1.3.1 From f1a16a647593691302154af0ff592a9cdf9cda5e Mon Sep 17 00:00:00 2001 From: ruki Date: Sat, 22 Mar 2025 00:36:14 +0800 Subject: fix remove node --- tests/modules/graph/test.lua | 3 ++ xmake/core/base/graph.lua | 83 ++++++++++++---------------------------- xmake/modules/async/jobgraph.lua | 12 +++--- 3 files changed, 34 insertions(+), 64 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index c9584a69a..1fb0bcb43 100644 --- a/tests/modules/graph/test.lua +++ b/tests/modules/graph/test.lua @@ -50,6 +50,9 @@ function test_paritail_topo_sort(t) break end table.insert(order_vertices, node) + if node then + dag:partial_topo_sort_remove(node) + end end return order_vertices, has_cycle diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index bd6c8a3cc..04b0c6573 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -132,9 +132,8 @@ function graph:partial_topo_sort_reset() self._partial_topo_in_degree = nil self._partial_topo_queue = nil self._partial_topo_processed = nil + self._partial_topo_pending = 0 self._partial_topo_has_cycle = nil - self._partial_topo_remaining_count = nil - self._partial_topo_non_zero_indegree_count = nil self._partial_topo_dirty = false end @@ -173,59 +172,44 @@ function graph:partial_topo_sort_next(limit) if not self._partial_topo_in_progress then self:_partial_topo_sort_init() self._partial_topo_in_progress = true - if self._partial_topo_has_cycle then - return nil, true - end end + -- get one node with zero in-degree local node - if self._partial_topo_queue:empty() then - -- return empty node if queue is empty (all processed or cycle detected) - local processed_count = self._partial_topo_processed:size() - self._partial_topo_has_cycle = processed_count ~= #self:vertices() - return nil, self._partial_topo_has_cycle - else - -- get one node with zero in-degree + if not self._partial_topo_queue:empty() then node = self._partial_topo_queue:pop() self._partial_topo_processed:insert(node) - self._partial_topo_remaining_count = self._partial_topo_remaining_count - 1 - - -- update in-degrees based on the nodes in this node - local edges = self:adjacent_edges(node) - if edges then - for _, e in ipairs(edges) do - if e:from() == node then - local w = e:to() - self._partial_topo_in_degree[w] = self._partial_topo_in_degree[w] - 1 + self._partial_topo_pending = self._partial_topo_pending + 1 + end - -- update non-zero in-degree count - if self._partial_topo_in_degree[w] == 0 then - self._partial_topo_non_zero_indegree_count = self._partial_topo_non_zero_indegree_count - 1 + return node, self._partial_topo_has_cycle +end - -- if in-degree becomes zero, add to queue for next node - if not self._partial_topo_processed:has(w) then - self._partial_topo_queue:push(w) - end +-- remove node and update in-degrees based on the nodes in this node +function graph:partial_topo_sort_remove(node) + if node == nil then + return + end + self._partial_topo_pending = self._partial_topo_pending - 1 + local edges = self:adjacent_edges(node) + if edges then + for _, e in ipairs(edges) do + if e:from() == node then + local w = e:to() + self._partial_topo_in_degree[w] = self._partial_topo_in_degree[w] - 1 + if self._partial_topo_in_degree[w] == 0 then + if not self._partial_topo_processed:has(w) then + self._partial_topo_queue:push(w) end end end end end - -- early cycle detection - if all remaining nodes have in-degree > 0 - if self:_check_cycle_in_remaining() then - return node, true - end - - -- if queue is empty but we still have unprocessed nodes, we have a cycle - if self._partial_topo_queue:empty() then + if self._partial_topo_queue:empty() and self._partial_topo_pending == 0 then local processed_count = self._partial_topo_processed:size() - if processed_count ~= #self:vertices() then - self._partial_topo_has_cycle = true - end + self._partial_topo_has_cycle = processed_count ~= #self:vertices() end - - return node, self._partial_topo_has_cycle end -- topological sort, use kahn's algorithm @@ -472,25 +456,6 @@ function graph:_partial_topo_sort_init() -- track processed vertices self._partial_topo_processed = hashset.new() - - -- track counts for efficient cycle detection - self._partial_topo_remaining_count = #self:vertices() - self._partial_topo_non_zero_indegree_count = self._partial_topo_remaining_count - self._partial_topo_queue:size() - - -- quick cycle detection: if no nodes have zero in-degree, we have a cycle - if self._partial_topo_queue:empty() and self._partial_topo_remaining_count > 0 then - self._partial_topo_has_cycle = true - end -end - --- check if there's a cycle in the remaining unprocessed nodes -function graph:_check_cycle_in_remaining() - -- if all remaining nodes have in-degree > 0, we have a cycle - if self._partial_topo_remaining_count > 0 and self._partial_topo_remaining_count == self._partial_topo_non_zero_indegree_count then - self._partial_topo_has_cycle = true - return true - end - return false end -- new graph diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index 46b10381b..9994ac1f3 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -25,11 +25,13 @@ import("core.base.graph") import("core.base.hashset") -- define module -local jobqueue = jobqueue or object {_init = {"_dag"}} +local jobqueue = jobqueue or object {_init = {"_jobgraph", "_dag"}} local jobgraph = jobgraph or object {_init = {"_name", "_jobs", "_size", "_dag"}} --- nothing to do, we need not to remove it +-- remove the finished job function jobqueue:remove(job) + local dag = self._dag + dag:partial_topo_sort_remove(job) end -- get a free job from the job queue @@ -37,15 +39,15 @@ function jobqueue:getfree() local dag = self._dag local freejob, has_cycle = dag:partial_topo_sort_next() if has_cycle then + local names = {} local cycle = dag:find_cycle() if cycle then - local names = {} for _, job in ipairs(cycle) do table.insert(names, job.name) end table.insert(names, names[1]) - raise("%s: circular job dependency detected!\n%s", graph, table.concat(names, "\n -> ")) end + raise("%s: circular job dependency detected!\n%s", self._jobgraph, table.concat(names, "\n -> ")) end return freejob end @@ -107,7 +109,7 @@ end function jobgraph:build() local dag = self._dag dag:partial_topo_sort_reset() - return jobqueue {dag} + return jobqueue {self, dag} end -- get jobs -- cgit v1.3.1 From 4a8219cda19cf320330ab7488f53158624c8c393 Mon Sep 17 00:00:00 2001 From: ruki Date: Sat, 22 Mar 2025 00:43:40 +0800 Subject: update comments --- tests/modules/graph/test.lua | 10 ++++++---- xmake/core/base/graph.lua | 19 +++++++++++++++++++ 2 files changed, 25 insertions(+), 4 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index 1fb0bcb43..c242962db 100644 --- a/tests/modules/graph/test.lua +++ b/tests/modules/graph/test.lua @@ -46,12 +46,14 @@ function test_paritail_topo_sort(t) local order_vertices = {} while true do node, has_cycle = dag:partial_topo_sort_next() - if node == nil or has_cycle then - break - end - table.insert(order_vertices, node) 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 diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index 090d41ade..4be7a2b77 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -142,6 +142,25 @@ end -- @return array of nodes with zero in-degree, empty when complete -- @return has_cycle indicates if a cycle was detected -- +-- @code +-- 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 +-- -- find cycle +-- end +-- break +-- end +-- end +-- @endcode +-- -- e.g. -- -- add_edge(a, b) -- a depend on b -- cgit v1.3.1 From 172dbb827ab0efb3c32ebcac823ce866c18b2dd8 Mon Sep 17 00:00:00 2001 From: ruki Date: Sat, 22 Mar 2025 00:04:10 +0800 Subject: improve tests --- tests/modules/graph/test.lua | 57 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index c242962db..a13737b6e 100644 --- a/tests/modules/graph/test.lua +++ b/tests/modules/graph/test.lua @@ -72,6 +72,7 @@ function test_paritail_topo_sort(t) {6, 0}, {3, 2}, {1, 4}, + {2, 9}, } local dag = graph.new(true) for _, e in ipairs(edges) do @@ -97,6 +98,62 @@ function test_paritail_topo_sort(t) 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:add_edge(2, 9) + dynamic_adjust = true + end + table.insert(order_vertices, node) + dag:partial_topo_sort_remove(node) + 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 + table.insert(edges, {1, 4}) + table.insert(edges, {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 = { -- cgit v1.3.1 From d31fc3eb8ade62b0d80280f22329bb132ea95cfc Mon Sep 17 00:00:00 2001 From: ruki Date: Sat, 22 Mar 2025 22:28:30 +0800 Subject: support for job group --- tests/modules/async/run_jobgraph.lua | 26 ++++++++++++-- xmake/modules/async/jobgraph.lua | 68 +++++++++++++++++++++++++++++------- 2 files changed, 79 insertions(+), 15 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/async/run_jobgraph.lua b/tests/modules/async/run_jobgraph.lua index a3e1edeb3..bc1b5500f 100644 --- a/tests/modules/async/run_jobgraph.lua +++ b/tests/modules/async/run_jobgraph.lua @@ -10,8 +10,8 @@ function _jobfunc(index, total, opt) 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 jobgraph ====================================") +function _test_basic() + print("==================================== test basic ====================================") local jobs = jobgraph.new() jobs:add("job/root", _jobfunc) for i = 1, 3 do @@ -27,3 +27,25 @@ function main() 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"}) + for j = 1, 50 do + jobs:add("job/" .. i .. "/" .. j, _jobfunc, {groups = "foo"}) + end + end + jobs:add_deps("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/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index ee3a6f274..edf3cfe81 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -37,6 +37,7 @@ end -- get a free job from the job queue function jobqueue:getfree() local dag = self._dag +::continue:: local freejob, has_cycle = dag:partial_topo_sort_next() if has_cycle then local names = {} @@ -49,6 +50,11 @@ function jobqueue:getfree() end raise("%s: circular job dependency detected!\n%s", self._jobgraph, table.concat(names, "\n -> ")) end + -- if it's a fake job, we need to skip it and continue to get the next job + if freejob and not freejob.run then + dag:partial_topo_sort_remove(freejob) + goto continue + end return freejob end @@ -60,23 +66,25 @@ end -- -- @param name the job name -- @param run the job run command/script --- @param opt the job options, e.g. {group = "xxx"} +-- @param opt the job options, e.g. {groups = {"xxx"}} -- function jobgraph:add(name, run, opt) + opt = opt or {} local jobs = self._jobs if not jobs[name] then local job = {name = name, run = run, opt = opt} jobs[name] = job self._size = self._size + 1 - local group_name = opt.group - if group_name then - local groups = self._groups[group_name] - if not groups then - groups = {} - self._groups[group_name] = groups + if opt.groups then + for _, group_name in ipairs(opt.groups) do + local groups = self._groups[group_name] + if not groups then + groups = {} + self._groups[group_name] = groups + end + table.insert(groups, job) end - table.insert(groups, job) end end end @@ -97,19 +105,53 @@ end -- add job deps, e.g. add_deps(a, b, c, ...): a -> b -> c, ... function jobgraph:add_deps(...) local prev + local prev_is_group local dag = self._dag local jobs = self._jobs + local groups = self._groups for _, name in ipairs(table.pack(...)) do - local curr = assert(jobs[name], "job(%s) not found in jobgraph(%s)", name, self) + local curr_is_group = false + local curr = jobs[name] + if not curr then + curr = groups[name] + curr_is_group = true + end + assert(curr, "job(%s) not found in jobgraph(%s)", name, self) if prev then - if not dag:has_edge(prev, curr) then - dag:add_edge(prev, curr) + if prev_is_group and curr_is_group then + -- we use a fake task as a node to bridge the two groups. + local fakejob = {} + for _, job in ipairs(prev) do + if not dag:has_edge(job, fakejob) then + dag:add_edge(job, fakejob) + end + end + for _, job in ipairs(curr) do + if not dag:has_edge(fakejob, job) then + dag:add_edge(fakejob, job) + end + end + elseif curr_is_group then + for _, job in ipairs(curr) do + if not dag:has_edge(prev, job) then + dag:add_edge(prev, job) + end + end + elseif prev_is_group then + for _, job in ipairs(prev) do + if not dag:has_edge(job, curr) then + dag:add_edge(job, curr) + end + end + else + if not dag:has_edge(prev, curr) then + dag:add_edge(prev, curr) + end end end prev = curr + prev_is_group = curr_is_group end - -- TODO - -- add groups jobs end -- build a job queue -- cgit v1.3.1 From 9b3f6f86ae92c9fb779fbb898801ab4c70a6390e Mon Sep 17 00:00:00 2001 From: ruki Date: Sun, 23 Mar 2025 21:46:33 +0800 Subject: fix remove vertex --- tests/modules/graph/test.lua | 23 +++++++++++++++++++---- xmake/core/base/graph.lua | 28 ++++++++++++++-------------- 2 files changed, 33 insertions(+), 18 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua index a13737b6e..fe1d63e8d 100644 --- a/tests/modules/graph/test.lua +++ b/tests/modules/graph/test.lua @@ -110,11 +110,14 @@ function test_paritail_topo_sort_dynamic(t) if node then if not dynamic_adjust then dag:add_edge(1, 4) - dag:add_edge(2, 9) - dynamic_adjust = true + 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!") @@ -148,8 +151,20 @@ function test_paritail_topo_sort_dynamic(t) for i, v in ipairs(order_path) do orders[v] = i end - table.insert(edges, {1, 4}) - table.insert(edges, {2, 9}) + 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 diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index dcb274318..658b71e73 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -107,17 +107,15 @@ function graph:remove_vertex(v) self._edges_map[v] = nil self._adjacent_edges[v] = nil -- remove the adjacent edge with this vertex in the other vertices - if not self:is_directed() then - for _, w in ipairs(self:vertices()) do - local edges = self:adjacent_edges(w) - if edges then - table.remove_if(edges, function (_, e) - if e:other(w) == v then - self._edges_map[w] = nil - return true - end - end) - end + for _, w in ipairs(self:vertices()) do + local edges = self:adjacent_edges(w) + if edges then + table.remove_if(edges, function (_, e) + if e:other(w) == v then + self._edges_map[w] = nil + return true + end + end) end end @@ -176,7 +174,7 @@ function graph:partial_topo_sort_next() -- recompute all nodes if has dirty nodes if self._partial_topo_dirty then - self:_partial_topo_sort_recompute_all() + self:_partial_topo_sort_recompute_dirty() end -- check if we already detected a cycle @@ -487,8 +485,10 @@ function graph:_partial_topo_sort_init() return true end --- recompute all nodes -function graph:_partial_topo_sort_recompute_all() +-- recompute all dirty nodes +-- +-- TODO we recompute all nodes now, but we should optimize to recompute only dirty nodes +function graph:_partial_topo_sort_recompute_dirty() self._partial_topo_in_progress = false self._partial_topo_in_degree = nil self._partial_topo_queue = nil -- cgit v1.3.1 From 8beb0732ff716cd5b3d7a40744b1d239302fdb4b Mon Sep 17 00:00:00 2001 From: ruki Date: Thu, 27 Mar 2025 22:49:41 +0800 Subject: rename add_deps to add_orders --- tests/modules/async/run_jobgraph.lua | 4 ++-- xmake/actions/build/target_utils.lua | 15 +++++++++------ xmake/core/base/graph.lua | 18 +++++++++++------- xmake/modules/async/jobgraph.lua | 20 ++++++++++---------- 4 files changed, 32 insertions(+), 25 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/async/run_jobgraph.lua b/tests/modules/async/run_jobgraph.lua index bc1b5500f..9b8f529ed 100644 --- a/tests/modules/async/run_jobgraph.lua +++ b/tests/modules/async/run_jobgraph.lua @@ -18,7 +18,7 @@ function _test_basic() jobs:add("job/" .. i, _jobfunc) for j = 1, 50 do jobs:add("job/" .. i .. "/" .. j, _jobfunc) - jobs:add_deps("job/" .. i .. "/" .. j, "job/" .. i, "job/root") + jobs:add_orders("job/" .. i .. "/" .. j, "job/" .. i, "job/root") end end t = os.mclock() @@ -37,7 +37,7 @@ function _test_group() jobs:add("job/" .. i .. "/" .. j, _jobfunc, {groups = "foo"}) end end - jobs:add_deps("foo", "bar", "job/root") + 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, ",")) diff --git a/xmake/actions/build/target_utils.lua b/xmake/actions/build/target_utils.lua index 1fef599ac..b91b436f0 100644 --- a/xmake/actions/build/target_utils.lua +++ b/xmake/actions/build/target_utils.lua @@ -50,7 +50,7 @@ function _add_stage_jobs_for_target(jobgraph, target, stage, opt) end -- call target and rules script - local jobdeps = {} + local joborders = {} for _, instance in ipairs(instances) do local script = instance:script(script_name) if script then @@ -59,7 +59,7 @@ function _add_stage_jobs_for_target(jobgraph, target, stage, opt) -- TODO bind target envs script(target, {progress = progress}) end, {groups = group_name}) - table.insert(jobdeps, jobname) + table.insert(joborders, jobname) else local scriptcmd = instance:script(scriptcmd_name) if scriptcmd then @@ -70,13 +70,16 @@ function _add_stage_jobs_for_target(jobgraph, target, stage, opt) scriptcmd(target, batchcmds_, {progress = progress}) batchcmds_:runcmds({changed = target:is_rebuilt(), dryrun = option.get("dry-run")}) end, {groups = group_name}) - table.insert(jobdeps, jobname) + table.insert(joborders, jobname) end end end - -- add job deps - jobgraph:add_deps(jobdeps) + -- add job orders + if #joborders > 0 then + jobgraph:add_orders(joborders) + return group_name + end end -- add jobs for the given target @@ -90,7 +93,7 @@ function _add_jobs_for_target(jobgraph, target, opt) local group = _add_stage_jobs_for_target(jobgraph, target, "", opt) local group_before = _add_stage_jobs_for_target(jobgraph, target, "before", opt) local group_after = _add_stage_jobs_for_target(jobgraph, target, "after", opt) - jobgraph:add_deps(group_after, group, group_before) + jobgraph:add_orders(group_before, group, group_after) end -- add jobs for the given target and deps diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index 43b43ce3c..db8682b21 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -173,12 +173,14 @@ end -- -- e.g. -- --- add_edge(a, b) -- a depend on b --- add_edge(b, c) -- b depend on c +-- edges: a (indegree: 0) -> b -> c -- --- local node1, has_cycle = g:partial_topo_sort_next() -- return c +-- add_edge(a, b) +-- add_edge(b, c) +-- +-- local node1, has_cycle = g:partial_topo_sort_next() -- return a -- local node2, has_cycle = g:partial_topo_sort_next() -- return b --- local node3, has_cycle = g:partial_topo_sort_next() -- return a +-- local node3, has_cycle = g:partial_topo_sort_next() -- return c -- local node4, has_cycle = g:partial_topo_sort_next() -- return nil (empty, all done) -- function graph:partial_topo_sort_next() @@ -250,10 +252,12 @@ end -- -- e.g. -- --- add_edge(a, b) -- a depend on b --- add_edge(b, c) -- b depend on c +-- edges: a (indegree: 0) -> b -> c +-- +-- add_edge(a, b) +-- add_edge(b, c) -- --- it will return {c, b, a} +-- it will return {a, b, c} function graph:topo_sort() if not self:is_directed() then return diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index b72fb5b16..fe42f6647 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -104,25 +104,25 @@ function jobgraph:remove(name) end end --- add job deps, e.g. add_deps(a, b, c, ...): a -> b -> c, ... +-- add job orders, e.g. add_orders(a, b, c, ...): a -> b -> c, ... -- --- and it supports nil, e.g add_deps("foo", nil, "bar", ...) --- and it also supports to add deps list, e.g. add_deps(deps) +-- and it supports nil, e.g add_orders("foo", nil, "bar", ...) +-- and it also supports to add orders list, e.g. add_orders(orders) -- -function jobgraph:add_deps(...) +function jobgraph:add_orders(...) local prev local prev_is_group local dag = self._dag local jobs = self._jobs local groups = self._groups - local deps = table.pack(...) - local count = deps.n - if count == 1 and type(deps[1]) == "table" then - deps = deps[1] - count = #deps + local orders = table.pack(...) + local count = orders.n + if count == 1 and type(orders[1]) == "table" then + orders = orders[1] + count = #orders end for i = 1, count do - local name = deps[i] + local name = orders[i] if name then local curr_is_group = false local curr = jobs[name] -- cgit v1.3.1 From f55ca39e18390317210ac7d660cbfaa517c1e691 Mon Sep 17 00:00:00 2001 From: ruki Date: Thu, 27 Mar 2025 23:05:03 +0800 Subject: add jobgraph:group --- tests/modules/async/run_jobgraph.lua | 8 +++++--- xmake/actions/build/target_utils.lua | 21 ++++++++++++--------- xmake/modules/async/jobgraph.lua | 27 +++++++++++++++++++++++++-- 3 files changed, 42 insertions(+), 14 deletions(-) (limited to 'tests/modules') diff --git a/tests/modules/async/run_jobgraph.lua b/tests/modules/async/run_jobgraph.lua index 9b8f529ed..4463038b7 100644 --- a/tests/modules/async/run_jobgraph.lua +++ b/tests/modules/async/run_jobgraph.lua @@ -33,9 +33,11 @@ function _test_group() jobs:add("job/root", _jobfunc) for i = 1, 3 do jobs:add("job/" .. i, _jobfunc, {groups = "bar"}) - for j = 1, 50 do - jobs:add("job/" .. i .. "/" .. j, _jobfunc, {groups = "foo"}) - end + jobgraph: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() diff --git a/xmake/actions/build/target_utils.lua b/xmake/actions/build/target_utils.lua index 41c979b85..13cf54ad9 100644 --- a/xmake/actions/build/target_utils.lua +++ b/xmake/actions/build/target_utils.lua @@ -39,7 +39,6 @@ end function _add_script_job(jobgraph, instance, script_name, scriptcmd_name, opt) opt = opt or {} local joborders = opt.joborders - local group_name = opt.group_name local script = instance:script(script_name) if script then -- call custom script with jobgraph @@ -49,6 +48,7 @@ function _add_script_job(jobgraph, instance, script_name, scriptcmd_name, opt) -- on_build(function (target, jobgraph, opt) -- end, {jobgraph = true}) if instance:extraconf(script_name, "jobgraph") then + -- TODO group and joborders script(target, jobgraph) elseif instance:extraconf(script_name, "batch") then wprint("%s.%s: the batch mode is deprecated, please use jobgraph mode instead of it.", instance:fullname(), script_name) @@ -62,9 +62,11 @@ function _add_script_job(jobgraph, instance, script_name, scriptcmd_name, opt) local jobname = string.format("%s/%s/%s", instance == target and "target" or "rule", instance:fullname(), script_name) jobgraph:add(jobname, function (index, total, opt) script(target, {progress = opt.progress}) - end, {groups = group_name}) + end) table.insert(joborders, jobname) end + elseif false then + -- TODO call builtin script else -- call command script -- e.g. @@ -79,7 +81,7 @@ function _add_script_job(jobgraph, instance, script_name, scriptcmd_name, opt) local batchcmds_ = batchcmds.new({target = target}) scriptcmd(target, batchcmds_, {progress = opt.progress}) batchcmds_:runcmds({changed = target:is_rebuilt(), dryrun = option.get("dry-run")}) - end, {groups = group_name}) + end) table.insert(joborders, jobname) end end @@ -108,12 +110,13 @@ function _add_stage_jobs_for_target(jobgraph, target, stage, opt) -- call target and rules script local joborders = {} - for _, instance in ipairs(instances) do - _add_script_job(jobgraph, instance, script_name, scriptcmd_name, { - group_name = group_name, - joborders = joborders - }) - end + jobgraph:group(group_name, function () + for _, instance in ipairs(instances) do + _add_script_job(jobgraph, instance, script_name, scriptcmd_name, { + joborders = joborders + }) + end + end) -- add job orders if #joborders > 0 then diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua index fe42f6647..b9e9a46da 100644 --- a/xmake/modules/async/jobgraph.lua +++ b/xmake/modules/async/jobgraph.lua @@ -78,8 +78,9 @@ function jobgraph:add(name, run, opt) dag:add_vertex(job) self._size = self._size + 1 - if opt.groups then - for _, group_name in ipairs(opt.groups) do + if self._current_groups or opt.groups then + local job_groups = table.join(self._current_groups or {}, opt.groups) + for _, group_name in ipairs(job_groups) do local groups = self._groups[group_name] if not groups then groups = {} @@ -104,6 +105,28 @@ function jobgraph:remove(name) end end +-- enter group to add jobs +-- +-- e.g. +-- jobgraph:group("foo", function () +-- jobgraph:add("job1", function (index, total, opt) +-- TODO +-- end) +-- jobgraph:add("job2", function (index, total, opt) +-- TODO +-- end) +-- end) +function jobgraph:group(name, callback) + local current_groups = self._current_groups + if current_groups == nil then + current_groups = {} + self._current_groups = current_groups + end + table.insert(current_groups, name) + callback() + table.remove(current_groups) +end + -- add job orders, e.g. add_orders(a, b, c, ...): a -> b -> c, ... -- -- and it supports nil, e.g add_orders("foo", nil, "bar", ...) -- cgit v1.3.1 From 987ab86a6270073e6d1d08d4e8e70d6487e0d65c Mon Sep 17 00:00:00 2001 From: ruki Date: Thu, 27 Mar 2025 23:05:19 +0800 Subject: fix test --- tests/modules/async/run_jobgraph.lua | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'tests/modules') diff --git a/tests/modules/async/run_jobgraph.lua b/tests/modules/async/run_jobgraph.lua index 4463038b7..fe53a54c6 100644 --- a/tests/modules/async/run_jobgraph.lua +++ b/tests/modules/async/run_jobgraph.lua @@ -33,7 +33,7 @@ function _test_group() jobs:add("job/root", _jobfunc) for i = 1, 3 do jobs:add("job/" .. i, _jobfunc, {groups = "bar"}) - jobgraph:group("foo", function () + jobs:group("foo", function () for j = 1, 50 do jobs:add("job/" .. i .. "/" .. j, _jobfunc) end -- cgit v1.3.1