improve to find cycle

5 files changed, 51 insertions, 32 deletions

diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua
index 63095be12..4bbefe069 100644
--- a/tests/modules/graph/test.lua
+++ b/tests/modules/graph/test.lua
@@ -52,5 +52,8 @@ function test_find_cycle(t)
     end
     local cycle = dag:find_cycle()
     t:are_equal(cycle, {1, 6, 0})
+
+    local _, has_cycle = dag:topological_sort()
+    t:require(has_cycle)
 end
 
diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua
index bf6b724ce..3b88a642a 100644
--- a/xmake/core/base/graph.lua
+++ b/xmake/core/base/graph.lua
@@ -125,29 +125,40 @@ function graph:topological_sort(opt)
     for _, v in ipairs(self:vertices()) do
         visited[v] = false
     end
+    local in_stack = {}
     local order_vertices = {}
     local function dfs(v)
         visited[v] = true
+        in_stack[v] = true
         local edges = self:adjacent_edges(v)
         if edges then
             for _, e in ipairs(edges) do
                 local w = e:other(v)
                 if not visited[w] then
-                    dfs(w)
+                    if dfs(w) then
+                        return true
+                    end
+                elseif in_stack[w] then
+                    return true
                 end
             end
         end
+        in_stack[v] = false
         table.insert(order_vertices, v)
     end
+    local has_cycle = false
     for _, v in ipairs(self:vertices()) do
         if not visited[v] then
-            dfs(v)
+            if dfs(v) then
+                has_cycle = true
+                break
+            end
         end
     end
     if opt.reverse then
-        return order_vertices
+        return order_vertices, has_cycle
     else
-        return table.reverse(order_vertices)
+        return table.reverse(order_vertices), has_cycle
     end
 end
 
diff --git a/xmake/core/tool/builder.lua b/xmake/core/tool/builder.lua
index 2bf4efc1f..b0f802237 100644
--- a/xmake/core/tool/builder.lua
+++ b/xmake/core/tool/builder.lua
@@ -668,11 +668,14 @@ function builder:_sort_links_of_items(items, opt)
             gh:add_edge(k, v)
         end
         if not gh:empty() then
-            local cycle = gh:find_cycle()
-            if cycle then
-                utils.warning("cycle links found in add_linkorders(): %s", table.concat(cycle, " -> "))
+            local has_cycle
+            links, has_cycle = gh:topological_sort()
+            if has_cycle then
+                local cycle = gh:find_cycle()
+                if cycle then
+                    utils.warning("cycle links found in add_linkorders(): %s", table.concat(cycle, " -> "))
+                end
             end
-            links = gh:topological_sort()
         end
     end
 
diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua
index 9bf98f7b5..6d96ff0ff 100644
--- a/xmake/modules/async/jobgraph.lua
+++ b/xmake/modules/async/jobgraph.lua
@@ -47,20 +47,21 @@ function jobqueue:_build()
     local dag = graph._dag
     local queue = self._queue
 
-    -- check circular dependencies
-    local cycle = dag:find_cycle()
-    if cycle then
-        local names = {}
-        for _, job in ipairs(cycle) do
-            table.insert(names, job.name)
-        end
-        table.insert(names, names[1])
-        raise("%s: circular job dependency detected!\n%s", graph, table.concat(names, "\n   -> "))
-    end
-
     -- build job queue
     queue:clear()
-    for _, job in ipairs(dag:topological_sort({reverse = true})) do
+    local order_jobs, has_cycle = dag:topological_sort({reverse = true})
+    if has_cycle then
+        local cycle = dag:find_cycle()
+        if cycle then
+            local names = {}
+            for _, job in ipairs(cycle) do
+                table.insert(names, job.name)
+            end
+            table.insert(names, names[1])
+            raise("%s: circular job dependency detected!\n%s", graph, table.concat(names, "\n   -> "))
+        end
+    end
+    for _, job in ipairs(order_jobs) do
         job._deps = nil
         job._parents = nil
         queue:insert(job)
diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua
index 9d552d0fd..df8c85441 100644
--- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua
+++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua
@@ -222,7 +222,7 @@ function _generate_dependencies(target, sourcebatch, opt)
     local changed = false
     if opt.batchjobs then
         local jobs = option.get("jobs") or os.default_njob()
-        runjobs(target:name() .. "_module_dependency_scanner", function(index) 
+        runjobs(target:name() .. "_module_dependency_scanner", function(index)
             local sourcefile = sourcebatch.sourcefiles[index]
             changed = _dependency_scanner(target).generate_dependency_for(target, sourcefile, opt) or changed
         end, {comax = jobs, total = #sourcebatch.sourcefiles})
@@ -415,19 +415,20 @@ function sort_modules_by_dependencies(target, objectfiles, modules, opt)
     for _, e in ipairs(edges) do
         dag:add_edge(e[1], e[2])
     end
-    local cycle = dag:find_cycle()
-    if cycle then
-        local names = {}
-        for _, objectfile in ipairs(cycle) do
-            local name, _, cppfile = compiler_support.get_provided_module(modules[objectfile])
+    local objectfiles_sorted, has_cycle = dag:topological_sort({reverse = true})
+    if has_cycle then
+        local cycle = dag:find_cycle()
+        if cycle then
+            local names = {}
+            for _, objectfile in ipairs(cycle) do
+                local name, _, cppfile = compiler_support.get_provided_module(modules[objectfile])
+                table.insert(names, name or cppfile)
+            end
+            local name, _, cppfile = compiler_support.get_provided_module(modules[cycle[1]])
             table.insert(names, name or cppfile)
+            raise("circular modules dependency detected!\n%s", table.concat(names, "\n   -> import "))
         end
-        local name, _, cppfile = compiler_support.get_provided_module(modules[cycle[1]])
-        table.insert(names, name or cppfile)
-        raise("circular modules dependency detected!\n%s", table.concat(names, "\n   -> import "))
     end
-
-    local objectfiles_sorted = table.reverse(dag:topological_sort())
     local objectfiles_sorted_set = hashset.from(objectfiles_sorted)
     for _, objectfile in ipairs(objectfiles) do
         if not objectfiles_sorted_set:has(objectfile) then
@@ -465,7 +466,7 @@ function sort_modules_by_dependencies(target, objectfiles, modules, opt)
                 end
             end
         end
-        if insert then 
+        if insert then
             table.insert(build_objectfiles, objectfile)
             table.insert(link_objectfiles, objectfile)
         elseif external and not external.from_moduleonly then