Merge #13228: Add script to detect circular dependencies between source modules

a7b295e91e Add circular dependencies script (Pieter Wuille)

Pull request description:

  This script finds dependencies between source code modules, treating the `.cpp` and `.h` file as one unit (so it will detect `A.cpp` depending on `B.h` where `B.cpp` depends on `A.h`). This can be used to find out which modules cannot be used independently from each other.

  It is very simplistic at this point, and assumes that a `.cpp` file's corresponding header has the exact same name, with `.cpp` replaced by `.h`. Furthermore, it assumes all `#include`s are relative to the `src/` directory.

  This is not a linter, and is not enforced through Travis or otherwise.

  This is the current output:

  ```
  $ ../contrib/devtools/circular-dependencies.py {*,*/*,*/*/*}.{h,cpp}
  Circular dependency: chain -> pow -> chain
  Circular dependency: chainparamsbase -> util -> chainparamsbase
  Circular dependency: checkpoints -> validation -> checkpoints
  Circular dependency: init -> index/txindex -> init
  Circular dependency: init -> validation -> init
  Circular dependency: init -> net_processing -> init
  Circular dependency: init -> rpc/server -> init
  Circular dependency: init -> txdb -> init
  Circular dependency: init -> validationinterface -> init
  Circular dependency: random -> util -> random
  Circular dependency: sync -> util -> sync
  Circular dependency: txmempool -> validation -> txmempool
  Circular dependency: txmempool -> policy/fees -> txmempool
  Circular dependency: validation -> index/txindex -> validation
  Circular dependency: validation -> policy/policy -> validation
  Circular dependency: validation -> validationinterface -> validation
  Circular dependency: qt/addresstablemodel -> qt/walletmodel -> qt/addresstablemodel
  Circular dependency: qt/bantablemodel -> qt/clientmodel -> qt/bantablemodel
  Circular dependency: qt/bitcoingui -> qt/walletview -> qt/bitcoingui
  Circular dependency: qt/bitcoingui -> qt/walletframe -> qt/bitcoingui
  Circular dependency: qt/bitcoingui -> qt/utilitydialog -> qt/bitcoingui
  Circular dependency: qt/clientmodel -> qt/peertablemodel -> qt/clientmodel
  Circular dependency: qt/paymentserver -> qt/walletmodel -> qt/paymentserver
  Circular dependency: qt/recentrequeststablemodel -> qt/walletmodel -> qt/recentrequeststablemodel
  Circular dependency: qt/sendcoinsdialog -> qt/walletmodel -> qt/sendcoinsdialog
  Circular dependency: qt/transactiontablemodel -> qt/walletmodel -> qt/transactiontablemodel
  Circular dependency: qt/walletmodel -> qt/walletmodeltransaction -> qt/walletmodel
  Circular dependency: rpc/rawtransaction -> wallet/rpcwallet -> rpc/rawtransaction
  Circular dependency: wallet/coincontrol -> wallet/wallet -> wallet/coincontrol
  Circular dependency: wallet/fees -> wallet/wallet -> wallet/fees
  Circular dependency: wallet/rpcwallet -> wallet/wallet -> wallet/rpcwallet
  Circular dependency: wallet/walletdb -> wallet/wallet -> wallet/walletdb
  Circular dependency: txmempool -> validation -> policy/rbf -> txmempool
  Circular dependency: txmempool -> validation -> validationinterface -> txmempool
  Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/addressbookpage
  Circular dependency: qt/guiutil -> qt/walletmodel -> qt/optionsmodel -> qt/guiutil
  Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/signverifymessagedialog -> qt/addressbookpage
  Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/receivecoinsdialog -> qt/addressbookpage
  Circular dependency: qt/guiutil -> qt/walletmodel -> qt/optionsmodel -> qt/intro -> qt/guiutil
  Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/sendcoinsdialog -> qt/sendcoinsentry -> qt/addressbookpage
  ```

Tree-SHA512: 29bc985b7a41699f4666b0aaa785ca63c2145e84c37458536f4dcf8e3de8f1312cf0323fe09cb8f348a9d363583f76eac2d5bee574bc6a9f9cc97a9b0aad406f

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)