add queue and improve graph

9 files changed, 406 insertions, 61 deletions

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