find cycle in graph

4 files changed, 88 insertions, 8 deletions

diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua
index cc0e16738..63095be12 100644
--- a/tests/modules/graph/test.lua
+++ b/tests/modules/graph/test.lua
@@ -38,3 +38,19 @@ function test_topological_sort(t)
     end
 end
 
+function test_find_cycle(t)
+    local edges = {
+        {9, 1},
+        {1, 6},
+        {6, 0},
+        {0, 1},
+        {4, 5}
+    }
+    local dag = graph.new(true)
+    for _, e in ipairs(edges) do
+        dag:add_edge(e[1], e[2])
+    end
+    local cycle = dag:find_cycle()
+    t:are_equal(cycle, {1, 6, 0})
+end
+
diff --git a/tests/projects/c++/linkorders/xmake.lua b/tests/projects/c++/linkorders/xmake.lua
index 8a5f1d18c..5d64c72b4 100644
--- a/tests/projects/c++/linkorders/xmake.lua
+++ b/tests/projects/c++/linkorders/xmake.lua
@@ -24,6 +24,7 @@ target("demo")
     end
     add_linkorders("framework::Foundation", "png16", "foo")
     add_linkorders("dl", "linkgroup::syslib")
+--    add_linkorders("foo", "png16")
     add_linkgroups("m", "pthread", {name = "syslib"})
 
 
diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua
index 875bceb45..80d4566ec 100644
--- a/xmake/core/base/graph.lua
+++ b/xmake/core/base/graph.lua
@@ -113,32 +113,76 @@ end
 
 -- topological sort
 function graph:topological_sort()
-    local marked = {}
+    local visited = {}
     for _, v in ipairs(self:vertices()) do
-        marked[v] = false
+        visited[v] = false
     end
     local order_vertices = {}
-    local function graph_topological_sort_dfs(v)
-        marked[v] = true
+    local function dfs(v)
+        visited[v] = true
         local edges = self:adjacent_edges(v)
         if edges then
             for _, e in ipairs(edges) do
                 local w = e:other(v)
-                if marked[w] == false then
-                    graph_topological_sort_dfs(w)
+                if not visited[w] then
+                    dfs(w)
                 end
             end
         end
         table.insert(order_vertices, v)
     end
     for _, v in ipairs(self:vertices()) do
-        if marked[v] == false then
-            graph_topological_sort_dfs(v)
+        if not visited[v] then
+            dfs(v)
         end
     end
     return table.reverse(order_vertices)
 end
 
+-- find cycle
+function graph:find_cycle()
+    local visited = {}
+    local stack = {}
+    local cycle = {}
+
+    local function dfs(v)
+        visited[v] = true
+        stack[v] = true
+        table.insert(cycle, v)
+        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
+                    if dfs(w) then
+                        return true
+                    elseif stack[w] then
+                        return true
+                    end
+                elseif stack[w] then
+                    for i = #cycle, 1, -1 do
+                        if cycle[i] == w then
+                            cycle = table.slice(cycle, i)
+                            return true
+                        end
+                    end
+                end
+            end
+        end
+        table.remove(cycle)
+        stack[v] = false
+        return false
+    end
+
+    for _, v in ipairs(self:vertices()) do
+        if not visited[v] then
+            if dfs(v) then
+                return cycle
+            end
+        end
+    end
+end
+
 -- get edges
 function graph:edges()
     return self._edges
@@ -208,6 +252,22 @@ function graph:reverse()
     return gh
 end
 
+-- dump graph
+function graph:dump()
+    local vertices = self:vertices()
+    local edges = self:edges()
+    print(string.format("graph: %s, vertices: %d, edges: %d", self:is_directed() and "directed" or "not-directed", #vertices, #edges))
+    print("vertices: ")
+    for _, v in ipairs(vertices) do
+        print(string.format("  %s", v))
+    end
+    print("")
+    print("edges: ")
+    for _, e in ipairs(edges) do
+        print(string.format("  %s -> %s", e:from(), e:to()))
+    end
+end
+
 -- new graph
 function graph.new(directed)
     local gh = graph {directed}
diff --git a/xmake/core/tool/builder.lua b/xmake/core/tool/builder.lua
index b8ef3a0df..69e7b4de5 100644
--- a/xmake/core/tool/builder.lua
+++ b/xmake/core/tool/builder.lua
@@ -518,6 +518,9 @@ function builder:_sort_links_of_items(target, items)
         if not gh:empty() then
             links = gh:topological_sort()
         end
+        gh:dump()
+        local cycle = gh:find_cycle()
+        utils.dump(cycle)
     end
 
     -- re-generate links to items list