From a278d3bd3e74027e7fd1f878c7d8c991caf1a75f Mon Sep 17 00:00:00 2001
From: ruki <waruqi@gmail.com>
Date: Thu, 20 Mar 2025 23:16:51 +0800
Subject: improve to find cycle

---
 tests/modules/graph/test.lua | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'tests/modules/graph/test.lua')

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
 
-- 
cgit v1.3.1


From 741da62196bcb64c88e386f1a769462211c63b4e Mon Sep 17 00:00:00 2001
From: ruki <waruqi@gmail.com>
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/graph/test.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


From 43ea0c1fb1d9954e065f3dfdb7bd93493d5d9e38 Mon Sep 17 00:00:00 2001
From: ruki <waruqi@gmail.com>
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/graph/test.lua')

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 <waruqi@gmail.com>
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/graph/test.lua')

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 <waruqi@gmail.com>
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/graph/test.lua')

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 <waruqi@gmail.com>
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/graph/test.lua')

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 <waruqi@gmail.com>
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/graph/test.lua')

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 <waruqi@gmail.com>
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/graph/test.lua')

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 9b3f6f86ae92c9fb779fbb898801ab4c70a6390e Mon Sep 17 00:00:00 2001
From: ruki <waruqi@gmail.com>
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/graph/test.lua')

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