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 --- xmake/core/tool/builder.lua | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) (limited to 'xmake/core/tool/builder.lua') 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 -- 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 'xmake/core/tool/builder.lua') 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