From b64836f09b250e1d77773cb9e0c53c33ecaaa9de Mon Sep 17 00:00:00 2001 From: Arthur LAURENT Date: Fri, 2 Feb 2024 12:52:06 +0100 Subject: improve module circular dependency detection we're already doing a DFS to sort modules and it already check for circular imports, so instead of rolling a custom detection afterward just signal the circular dependency when detected in the DFS --- .../modules/modules_support/dependency_scanner.lua | 113 +++++++++------------ 1 file changed, 46 insertions(+), 67 deletions(-) (limited to 'xmake/rules/c++/modules') diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index 46d53577a..d07884b19 100644 --- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua +++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua @@ -169,77 +169,56 @@ 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 +function _topological_sort_get_edges(node, nodes, modules) + local edges = {} + + local module = modules[node.objectfile] + local _, provide, _ = compiler_support.get_provided_module(module) + + if provide and module.requires then + for required, _ in pairs(module.requires) do + for objectfile, dep in pairs(modules) do + local name, _, _ = compiler_support.get_provided_module(dep) + if name and name == required then + local edge + for _, n in ipairs(nodes) do + if n.objectfile == objectfile then + edge = n + break + end + end + + table.insert(edges, edge) + break + end + end + end + end + + return edges end function _topological_sort_visit(node, nodes, modules, output) if node.marked then return end - assert(not node.tempmarked) + + local module = modules[node.objectfile] + local name, _, _ = compiler_support.get_provided_module(module) + + if node.tempmarked then + return {name} + end + + local edges = _topological_sort_get_edges(node, nodes, modules) + 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 + for _, edge in ipairs(edges) do + -- check circular dependencies + -- @see https://github.com/xmake-io/xmake/issues/3031 + local circular_dependency = _topological_sort_visit(edge, nodes, modules, output) + if circular_dependency then + return table.join(name, circular_dependency) end end node.tempmarked = false @@ -258,7 +237,7 @@ end function _topological_sort_get_first_unmarked_node(nodes) for _, node in ipairs(nodes) do - if not node.marked and not node.tempmarked then + if not node.marked then return node end end @@ -301,9 +280,9 @@ function get_module_dependencies(target, sourcebatch, opt) local moduleinfos = compiler_support.load_moduleinfos(target, sourcebatch) modules = _parse_dependencies_data(target, moduleinfos) if modules then - _check_circular_dependencies(modules) + -- _check_circular_dependencies(modules) + modules = cull_unused_modules(target, modules) end - modules = cull_unused_modules(target, modules) compiler_support.localcache():set2("modules", cachekey, modules) compiler_support.localcache():save() end -- cgit v1.3.1 From aedc8fa8b17560952782e8409fb41937fa781486 Mon Sep 17 00:00:00 2001 From: Arthur LAURENT Date: Fri, 2 Feb 2024 18:28:14 +0100 Subject: use core.base.graph instead of rolling out a custom DAG --- .../modules/modules_support/dependency_scanner.lua | 129 ++++++--------------- 1 file changed, 35 insertions(+), 94 deletions(-) (limited to 'xmake/rules/c++/modules') diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index d07884b19..f7d05a609 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("compiler_support") import("stl_headers") @@ -169,91 +170,26 @@ function _parse_dependencies_data(target, moduleinfos) return modules end -function _topological_sort_get_edges(node, nodes, modules) +-- generate edges for DAG +function _get_edges(nodes, modules) local edges = {} - - local module = modules[node.objectfile] - local _, provide, _ = compiler_support.get_provided_module(module) - - if provide and module.requires then - for required, _ in pairs(module.requires) do - for objectfile, dep in pairs(modules) do - local name, _, _ = compiler_support.get_provided_module(dep) - if name and name == required then - local edge - for _, n in ipairs(nodes) do - if n.objectfile == objectfile then - edge = n - break - end + 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 - - table.insert(edges, edge) - break end end end end - return edges end -function _topological_sort_visit(node, nodes, modules, output) - if node.marked then - return - end - - local module = modules[node.objectfile] - local name, _, _ = compiler_support.get_provided_module(module) - - if node.tempmarked then - return {name} - end - - local edges = _topological_sort_get_edges(node, nodes, modules) - - node.tempmarked = true - for _, edge in ipairs(edges) do - -- check circular dependencies - -- @see https://github.com/xmake-io/xmake/issues/3031 - local circular_dependency = _topological_sort_visit(edge, nodes, modules, output) - if circular_dependency then - return table.join(name, circular_dependency) - 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 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 -end - function _get_package_modules(target, package, opt) local package_modules @@ -280,8 +216,7 @@ function get_module_dependencies(target, sourcebatch, opt) local moduleinfos = compiler_support.load_moduleinfos(target, sourcebatch) modules = _parse_dependencies_data(target, moduleinfos) if modules then - -- _check_circular_dependencies(modules) - modules = cull_unused_modules(target, modules) + -- modules = cull_unused_modules(target, modules) end compiler_support.localcache():set2("modules", cachekey, modules) compiler_support.localcache():save() @@ -448,16 +383,30 @@ 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 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) + os.raise("circular modules dependency detected!\n%s", table.concat(names, "\n -> import ")) 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 sorted = dag:topological_sort() + for _, objectfile in ipairs(sorted) do + table.insert(output, objectfile) + end + for _, objectfile in ipairs(objectfiles) do + if not table.find(sorted, objectfile) then + table.insert(output, objectfile) + end end return output end @@ -482,11 +431,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 -- cgit v1.3.1 From 52d859465f2de6bdaafa05406cfe5ee56e5820a5 Mon Sep 17 00:00:00 2001 From: Arthur LAURENT Date: Fri, 2 Feb 2024 18:32:54 +0100 Subject: cleanup --- xmake/rules/c++/modules/modules_support/dependency_scanner.lua | 3 --- 1 file changed, 3 deletions(-) (limited to 'xmake/rules/c++/modules') diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index f7d05a609..a491f97cc 100644 --- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua +++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua @@ -215,9 +215,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 - -- modules = cull_unused_modules(target, modules) - end compiler_support.localcache():set2("modules", cachekey, modules) compiler_support.localcache():save() end -- cgit v1.3.1 From 07c0af96d81dcaa2c4ab5b5a9450367a70758c2d Mon Sep 17 00:00:00 2001 From: Arthur LAURENT Date: Sat, 3 Feb 2024 16:39:14 +0100 Subject: use hashset to improve speed --- xmake/rules/c++/modules/modules_support/dependency_scanner.lua | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'xmake/rules/c++/modules') diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index 6c02f51e7..ce8b37a92 100644 --- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua +++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua @@ -418,8 +418,9 @@ function sort_modules_by_dependencies(objectfiles, modules) for _, objectfile in ipairs(sorted) do table.insert(output, objectfile) end + local _objectfiles = hashset.from(objectfiles) for _, objectfile in ipairs(objectfiles) do - if not table.find(sorted, objectfile) then + if not _objectfiles:has(objectfile) then table.insert(output, objectfile) end end -- cgit v1.3.1 From 3bdb07d5fd49df3ba101b835b77c03a73ab23ce0 Mon Sep 17 00:00:00 2001 From: Arthur LAURENT Date: Sat, 3 Feb 2024 17:34:36 +0100 Subject: use raise instead of os.raise --- xmake/rules/c++/modules/modules_support/dependency_scanner.lua | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'xmake/rules/c++/modules') diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index ce8b37a92..311aca14e 100644 --- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua +++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua @@ -412,7 +412,7 @@ function sort_modules_by_dependencies(objectfiles, modules) end local name, _, cppfile = compiler_support.get_provided_module(modules[cycle[1]]) table.insert(names, name or cppfile) - os.raise("circular modules dependency detected!\n%s", table.concat(names, "\n -> import ")) + raise("circular modules dependency detected!\n%s", table.concat(names, "\n -> import ")) end local sorted = dag:topological_sort() for _, objectfile in ipairs(sorted) do -- cgit v1.3.1 From c5a17b3a1af1c1d377cf04c25f5546a3047bfd03 Mon Sep 17 00:00:00 2001 From: Arthur LAURENT Date: Sat, 3 Feb 2024 17:50:26 +0100 Subject: fix dependency_scanner hashset values --- xmake/rules/c++/modules/modules_support/dependency_scanner.lua | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'xmake/rules/c++/modules') diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index 311aca14e..6d93985bf 100644 --- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua +++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua @@ -418,7 +418,7 @@ function sort_modules_by_dependencies(objectfiles, modules) for _, objectfile in ipairs(sorted) do table.insert(output, objectfile) end - local _objectfiles = hashset.from(objectfiles) + local _objectfiles = hashset.from(sorted) for _, objectfile in ipairs(objectfiles) do if not _objectfiles:has(objectfile) then table.insert(output, objectfile) -- cgit v1.3.1 From 7f4af3b1df794fe2990ad23a75316514c70f6a44 Mon Sep 17 00:00:00 2001 From: ruki Date: Sun, 4 Feb 2024 09:31:33 +0800 Subject: Update dependency_scanner.lua --- .../c++/modules/modules_support/dependency_scanner.lua | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'xmake/rules/c++/modules') diff --git a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua index 6d93985bf..7ad344750 100644 --- a/xmake/rules/c++/modules/modules_support/dependency_scanner.lua +++ b/xmake/rules/c++/modules/modules_support/dependency_scanner.lua @@ -397,7 +397,7 @@ end -- topological sort function sort_modules_by_dependencies(objectfiles, modules) - local output = {} + local result = {} local edges, nodeps_nodes = _get_edges(objectfiles, modules) local dag = graph.new(true) for _, e in ipairs(edges) do @@ -414,17 +414,17 @@ function sort_modules_by_dependencies(objectfiles, modules) table.insert(names, name or cppfile) raise("circular modules dependency detected!\n%s", table.concat(names, "\n -> import ")) end - local sorted = dag:topological_sort() - for _, objectfile in ipairs(sorted) do - table.insert(output, objectfile) + local objectfiles_sorted = dag:topological_sort() + for _, objectfile in ipairs(objectfiles_sorted) do + table.insert(result, objectfile) end - local _objectfiles = hashset.from(sorted) + local objectfiles_sorted_set = hashset.from(objectfiles_sorted) for _, objectfile in ipairs(objectfiles) do - if not _objectfiles:has(objectfile) then - table.insert(output, objectfile) + 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 -- cgit v1.3.1