aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--contrib/devtools/README.md11
-rwxr-xr-xcontrib/devtools/circular-dependencies.py79
2 files changed, 90 insertions, 0 deletions
diff --git a/contrib/devtools/README.md b/contrib/devtools/README.md
index 15ee8a3959..7ac8aa39d3 100644
--- a/contrib/devtools/README.md
+++ b/contrib/devtools/README.md
@@ -194,3 +194,14 @@ It will do the following automatically:
- add missing translations to the build system (TODO)
See doc/translation-process.md for more information.
+
+circular-dependencies.py
+========================
+
+Run this script from the root of the source tree (`src/`) to find circular dependencies in the source code.
+This looks only at which files include other files, treating the `.cpp` and `.h` file as one unit.
+
+Example usage:
+
+ cd .../src
+ ../contrib/devtools/circular-dependencies.py {*,*/*,*/*/*}.{h,cpp}
diff --git a/contrib/devtools/circular-dependencies.py b/contrib/devtools/circular-dependencies.py
new file mode 100755
index 0000000000..d544d5c371
--- /dev/null
+++ b/contrib/devtools/circular-dependencies.py
@@ -0,0 +1,79 @@
+#!/usr/bin/env python3
+
+import sys
+import re
+
+MAPPING = {
+ 'core_read.cpp': 'core_io.cpp',
+ 'core_write.cpp': 'core_io.cpp',
+}
+
+def module_name(path):
+ if path in MAPPING:
+ path = MAPPING[path]
+ if path.endswith(".h"):
+ return path[:-2]
+ if path.endswith(".c"):
+ return path[:-2]
+ if path.endswith(".cpp"):
+ return path[:-4]
+ return None
+
+files = dict()
+deps = dict()
+
+RE = re.compile("^#include <(.*)>")
+
+# Iterate over files, and create list of modules
+for arg in sys.argv[1:]:
+ module = module_name(arg)
+ if module is None:
+ print("Ignoring file %s (does not constitute module)\n" % arg)
+ else:
+ files[arg] = module
+ deps[module] = set()
+
+# Iterate again, and build list of direct dependencies for each module
+# TODO: implement support for multiple include directories
+for arg in sorted(files.keys()):
+ module = files[arg]
+ with open(arg, 'r') as f:
+ for line in f:
+ match = RE.match(line)
+ if match:
+ include = match.group(1)
+ included_module = module_name(include)
+ if included_module is not None and included_module in deps and included_module != module:
+ deps[module].add(included_module)
+
+# Loop to find the shortest (remaining) circular dependency
+have_cycle = False
+while True:
+ shortest_cycle = None
+ for module in sorted(deps.keys()):
+ # Build the transitive closure of dependencies of module
+ closure = dict()
+ for dep in deps[module]:
+ closure[dep] = []
+ while True:
+ old_size = len(closure)
+ old_closure_keys = sorted(closure.keys())
+ for src in old_closure_keys:
+ for dep in deps[src]:
+ if dep not in closure:
+ closure[dep] = closure[src] + [src]
+ if len(closure) == old_size:
+ break
+ # If module is in its own transitive closure, it's a circular dependency; check if it is the shortest
+ if module in closure and (shortest_cycle is None or len(closure[module]) + 1 < len(shortest_cycle)):
+ shortest_cycle = [module] + closure[module]
+ if shortest_cycle is None:
+ break
+ # We have the shortest circular dependency; report it
+ module = shortest_cycle[0]
+ print("Circular dependency: %s" % (" -> ".join(shortest_cycle + [module])))
+ # And then break the dependency to avoid repeating in other cycles
+ deps[shortest_cycle[-1]] = deps[shortest_cycle[-1]] - set([module])
+ have_cycle = True
+
+sys.exit(1 if have_cycle else 0)