fix remove node

3 files changed, 34 insertions, 64 deletions

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