Merge pull request #4677 from Arthapz/optimise-dag

improve module circular dependency detection 

10 files changed, 114 insertions, 138 deletions

diff --git a/tests/projects/c++/modules/circular_dependency/src/hello.mpp b/tests/projects/c++/modules/circular_dependency/src/hello.mpp
new file mode 100644
index 000000000..50f0f2c8f
--- /dev/null
+++ b/tests/projects/c++/modules/circular_dependency/src/hello.mpp
@@ -0,0 +1,13 @@
+export module hello;
+
+import hello3;
+
+export namespace hello {
+    class say {
+    public:
+        say(int data);
+        void hello();
+    private:
+        int data_;
+    };
+}
diff --git a/tests/projects/c++/modules/circular_dependency/src/hello2.mpp b/tests/projects/c++/modules/circular_dependency/src/hello2.mpp
new file mode 100644
index 000000000..1b6258af1
--- /dev/null
+++ b/tests/projects/c++/modules/circular_dependency/src/hello2.mpp
@@ -0,0 +1,3 @@
+export module hello2;
+
+import hello;
diff --git a/tests/projects/c++/modules/circular_dependency/src/hello3.mpp b/tests/projects/c++/modules/circular_dependency/src/hello3.mpp
new file mode 100644
index 000000000..4966cf0c0
--- /dev/null
+++ b/tests/projects/c++/modules/circular_dependency/src/hello3.mpp
@@ -0,0 +1,3 @@
+export module hello3;
+
+import hello2;
diff --git a/tests/projects/c++/modules/circular_dependency/src/main.cpp b/tests/projects/c++/modules/circular_dependency/src/main.cpp
new file mode 100644
index 000000000..6f80b6c7d
--- /dev/null
+++ b/tests/projects/c++/modules/circular_dependency/src/main.cpp
@@ -0,0 +1,7 @@
+import hello;
+
+int main() {
+    hello::say s(sizeof(hello::say));
+    s.hello();
+    return 0;
+}
\ No newline at end of file
diff --git a/tests/projects/c++/modules/circular_dependency/test.lua b/tests/projects/c++/modules/circular_dependency/test.lua
new file mode 100644
index 000000000..727e9187e
--- /dev/null
+++ b/tests/projects/c++/modules/circular_dependency/test.lua
@@ -0,0 +1,7 @@
+import(".test_base", {alias = "test_build"})
+
+function main(t)
+    if test_build.can_build() then
+        t:will_raise(test_build, "circular modules dependency detected")
+    end
+end
diff --git a/tests/projects/c++/modules/circular_dependency/xmake.lua b/tests/projects/c++/modules/circular_dependency/xmake.lua
new file mode 100644
index 000000000..73254924e
--- /dev/null
+++ b/tests/projects/c++/modules/circular_dependency/xmake.lua
@@ -0,0 +1,8 @@
+add_rules("mode.release", "mode.debug")
+set_languages("c++20")
+
+target("circular_dependency")
+    set_kind("binary")
+    add_files("src/*.cpp", "src/*.mpp")
+
+
diff --git a/tests/projects/c++/modules/test_base.lua b/tests/projects/c++/modules/test_base.lua
index c4252d41c..092fbd72f 100644
--- a/tests/projects/c++/modules/test_base.lua
+++ b/tests/projects/c++/modules/test_base.lua
@@ -1,12 +1,29 @@
 import("lib.detect.find_tool")
 import("core.base.semver")
+import("utils.ci.is_running", {alias = "ci_is_running"})
 
 function _build()
-    local ci = (os.getenv("CI") or os.getenv("GITHUB_ACTIONS") or ""):lower()
-    if ci == "true" then
-        os.exec("xmake -rvD")
+    if ci_is_running() then
+        os.run("xmake -rvD")
     else
-        os.exec("xmake -r")
+        os.run("xmake -r")
+    end
+end
+
+function can_build()
+    if is_subhost("windows") then
+        return true
+    elseif is_subhost("msys") then
+        return true
+    elseif is_host("linux") then
+        local gcc = find_tool("gcc", {version = true})
+        if gcc and gcc.version and semver.compare(gcc.version, "11.0") >= 0 then
+            return true
+        end
+        local clang = find_tool("clang", {version = true})
+        if clang and clang.version and semver.compare(clang.version, "14.0") >= 0 then
+            return true
+        end
     end
 end
 
diff --git a/tests/projects/c++/modules/test_headerunits.lua b/tests/projects/c++/modules/test_headerunits.lua
index ba7fde015..bb32070cf 100644
--- a/tests/projects/c++/modules/test_headerunits.lua
+++ b/tests/projects/c++/modules/test_headerunits.lua
@@ -1,13 +1,13 @@
 import("lib.detect.find_tool")
 import("core.base.semver")
 import("detect.sdks.find_vstudio")
+import("utils.ci.is_running", {alias = "ci_is_running"})
 
 function _build()
-    local ci = (os.getenv("CI") or os.getenv("GITHUB_ACTIONS") or ""):lower()
-    if ci == "true" then
-        os.exec("xmake -rvD")
+    if ci_is_running() then
+        os.run("xmake -rvD")
     else
-        os.exec("xmake -r")
+        os.run("xmake -r")
     end
 end
 
diff --git a/tests/projects/c++/modules/test_stdmodules.lua b/tests/projects/c++/modules/test_stdmodules.lua
index c408c1d08..68a5922ef 100644
--- a/tests/projects/c++/modules/test_stdmodules.lua
+++ b/tests/projects/c++/modules/test_stdmodules.lua
@@ -1,13 +1,13 @@
 import("lib.detect.find_tool")
 import("core.base.semver")
 import("core.tool.toolchain")
+import("utils.ci.is_running", {alias = "ci_is_running"})
 
 function _build()
-    local ci = (os.getenv("CI") or os.getenv("GITHUB_ACTIONS") or ""):lower()
-    if ci == "true" then
-        os.exec("xmake -rvD")
+    if ci_is_running() then
+        os.run("xmake -rvD")
     else
-        os.exec("xmake -r")
+        os.run("xmake -r")
     end
 end
 
diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua
index 1938260a4..7ad344750 100644
--- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua
+++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua
@@ -21,6 +21,7 @@
 -- imports
 import("core.base.json")
 import("core.base.hashset")
+import("core.base.graph")
 import("core.base.option")
 import("async.runjobs")
 import("compiler_support")
@@ -171,110 +172,24 @@ function _parse_dependencies_data(target, moduleinfos)
     return modules
 end
 
-
--- check circular dependencies for the given module
-function _check_circular_dependencies_of_module(name, moduledeps, modulesources, depspath)
-    for _, dep in ipairs(moduledeps[name]) do
-        local depinfo = moduledeps[dep]
-        if depinfo then
-            local depspath_sub
-            if depspath then
-                for idx, name in ipairs(depspath) do
-                    if name == dep then
-                        local circular_deps = table.slice(depspath, idx)
-                        table.insert(circular_deps, dep)
-                        local sourceinfo = ""
-                        for _, circular_depname in ipairs(circular_deps) do
-                            local sourcefile = modulesources[circular_depname]
-                            if sourcefile then
-                                sourceinfo = sourceinfo .. ("\n  -> module(%s) in %s"):format(circular_depname, sourcefile)
-                            end
-                        end
-                        os.raise("circular modules dependency(%s) detected!%s", table.concat(circular_deps, ", "), sourceinfo)
-                    end
-                end
-                depspath_sub = table.join(depspath, dep)
-            end
-            _check_circular_dependencies_of_module(dep, moduledeps, modulesources, depspath_sub)
-        end
-    end
-end
-
--- check circular dependencies
--- @see https://github.com/xmake-io/xmake/issues/3031
-function _check_circular_dependencies(modules)
-    local moduledeps = {}
-    local modulesources = {}
-    for _, mod in pairs(modules) do
-        if mod then
-            if mod.provides and mod.requires then
-                for name, provide in pairs(mod.provides) do
-                    modulesources[name] = provide.sourcefile
-                    local deps = moduledeps[name]
-                    if deps then
-                        table.join2(deps, mod.requires)
-                    else
-                        moduledeps[name] = table.keys(mod.requires)
-                    end
-                end
-            end
-        end
-    end
-    for name, _ in pairs(moduledeps) do
-        _check_circular_dependencies_of_module(name, moduledeps, modulesources, {name})
-    end
-end
-
-function _topological_sort_visit(node, nodes, modules, output)
-    if node.marked then
-        return
-    end
-    assert(not node.tempmarked)
-    node.tempmarked = true
-    local m1 = modules[node.objectfile]
-    for _, n in ipairs(nodes) do
-        if not n.tempmarked then
-            local m2 = modules[n.objectfile]
-            if m2 then
-                for name, _ in pairs(m1.provides) do
-                    if m2.requires and m2.requires[name] then
-                        _topological_sort_visit(n, nodes, modules, output)
-                    end
-                end
-            end
-        end
-    end
-    node.tempmarked = false
-    node.marked = true
-    table.insert(output, 1, node.objectfile)
-end
-
-function _topological_sort_has_node_without_mark(nodes)
-    for _, node in ipairs(nodes) do
-        if not node.marked then
-            return true
-        end
-    end
-    return false
-end
-
-function _topological_sort_get_first_unmarked_node(nodes)
-    for _, node in ipairs(nodes) do
-        if not node.marked and not node.tempmarked then
-            return node
-        end
-    end
-end
-
-function _fill_needed_module(target, modules, module)
-    local needed_modules = {}
-
-    for required_name, required_module in pairs(module.requires) do
-        table.insert(needed_modules, required_name)
-        table.join2(needed_modules, _fill_needed_module(target, modules, required_module))
-    end
-
-    return needed_modules
+-- generate edges for DAG
+function _get_edges(nodes, modules)
+  local edges = {}
+  for _, node in ipairs(nodes) do
+      local module = modules[node]
+      if module.requires then
+          for required_name, _ in pairs(module.requires) do
+              for _, required_node in ipairs(nodes) do
+                  local name, _, _ = compiler_support.get_provided_module(modules[required_node])
+                  if name and name == required_name then
+                      table.insert(edges, {node, required_node})
+                      break
+                  end
+              end
+          end
+      end
+  end
+  return edges
 end
 
 function _get_package_modules(target, package, opt)
@@ -318,10 +233,6 @@ function get_module_dependencies(target, sourcebatch, opt)
         if changed or modules == nil then
             local moduleinfos = compiler_support.load_moduleinfos(target, sourcebatch)
             modules = _parse_dependencies_data(target, moduleinfos)
-            if modules then
-                _check_circular_dependencies(modules)
-            end
-            modules = cull_unused_modules(target, modules)
             compiler_support.localcache():set2("modules", cachekey, modules)
             compiler_support.localcache():save()
         end
@@ -486,19 +397,34 @@ end
 
 -- topological sort
 function sort_modules_by_dependencies(objectfiles, modules)
-    local output = {}
-    local nodes  = {}
-    for _, objectfile in ipairs(objectfiles) do
-        local m = modules[objectfile]
-        if m then
-            table.insert(nodes, {marked = false, tempmarked = false, objectfile = objectfile})
+    local result = {}
+    local edges, nodeps_nodes = _get_edges(objectfiles, modules)
+    local dag = graph.new(true)
+    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])
+            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 objectfiles_sorted = dag:topological_sort()
+    for _, objectfile in ipairs(objectfiles_sorted) do
+        table.insert(result, objectfile)
     end
-    while _topological_sort_has_node_without_mark(nodes) do
-        local node = _topological_sort_get_first_unmarked_node(nodes)
-        _topological_sort_visit(node, nodes, modules, output)
+    local objectfiles_sorted_set = hashset.from(objectfiles_sorted)
+    for _, objectfile in ipairs(objectfiles) do
+        if not objectfiles_sorted_set:has(objectfile) then
+            table.insert(result, objectfile)
+        end
     end
-    return output
+    return result
 end
 
 -- get source modulefile for external target deps
@@ -521,11 +447,3 @@ function get_targetdeps_modules(target)
     return sourcefiles
 end
 
--- cull unused packages modules
--- removed named module not used in the translation units
--- when building a library we only cull external modules because we need module objectfiles to be linked inside the library
--- on an executable we cull explicitly referenced module
-function cull_unused_modules(target, modules)
-    -- TODO
-    return modules
-end