Add script to detect circular dependencies between source modules #13228

pull sipa wants to merge 1 commits into bitcoin:master from sipa:201805_circular_detect changing 2 files +90 −0
  1. sipa commented at 8:27 PM on May 13, 2018: member

    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 #includes 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
  2. sipa force-pushed on May 13, 2018
  3. fanquake added the label Scripts and tools on May 13, 2018
  4. promag commented at 10:43 PM on May 13, 2018: member

    Concept ACK.

  5. fanquake commented at 7:16 AM on May 14, 2018: member

    Concept ACK

    bash-3.2$ ../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 -> net_processing -> init
Circular dependency: init -> index/txindex -> init
Circular dependency: init -> rpc/server -> init
Circular dependency: init -> txdb -> init
Circular dependency: init -> validation -> init
Circular dependency: init -> validationinterface -> init
Circular dependency: random -> util -> random
Circular dependency: sync -> util -> sync
Circular dependency: txmempool -> policy/fees -> txmempool
Circular dependency: txmempool -> validation -> txmempool
Circular dependency: validation -> index/txindex -> validation
Circular dependency: validation -> validationinterface -> validation
Circular dependency: validation -> policy/policy -> validation
Circular dependency: qt/addresstablemodel -> qt/walletmodel -> qt/addresstablemodel
Circular dependency: qt/bantablemodel -> qt/clientmodel -> qt/bantablemodel
Circular dependency: qt/bitcoingui -> qt/utilitydialog -> qt/bitcoingui
Circular dependency: qt/bitcoingui -> qt/walletview -> qt/bitcoingui
Circular dependency: qt/bitcoingui -> qt/walletframe -> 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/wallet -> wallet/walletdb -> wallet/wallet
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
  6. practicalswift commented at 7:30 AM on May 14, 2018: contributor

    Concept ACK

    Very nice!

    Suggested changes to make the output deterministic:

    --- ../circular-dependencies.py	2018-05-14 08:50:58.691253505 +0200
+++ ../circular-dependencies-deterministic.py	2018-05-14 09:28:20.164794798 +0200
@@ -35,7 +35,7 @@

 # Iterate again, and build list of direct dependencies for each module
 # TODO: implement support for multiple include directories
-for arg in files.keys():
+for arg in sorted(files.keys()):
     module = files[arg]
     with open(arg, 'r') as f:
         for line in f:
@@ -49,7 +49,7 @@
 # Loop to find the shortest (remaining) circular dependency
 while True:
     shortest_cycle = None
-    for module in deps.keys():
+    for module in sorted(deps.keys()):
         # Build the transitive closure of dependencies of module
         closure = dict()
         for dep in deps[module]:
@@ -57,7 +57,7 @@
         while True:
             old_size = len(closure)
             old_closure_keys = list(closure.keys())
-            for src in old_closure_keys:
+            for src in sorted(old_closure_keys):
                 for dep in deps[src]:
                     if dep not in closure:
                         closure[dep] = closure[src] + [src]
  7. Empact commented at 9:52 PM on May 14, 2018: member

    nit: I would expect this to work from root, with a call like: contrib/devtools/circular-dependencies.py src/{*,*/*,*/*/*}.{h,cpp} but it doesn't.

  8. sipa commented at 10:02 PM on May 14, 2018: member

    Yes, it can't. To deal with that it needs logic to actually resolve includes w.r.t. include directories; that's a TODO in the code. The README gives the correct invocation.

  9. in contrib/devtools/README.md:207 in 50c69b7801 outdated 
     202 | +This looks only at which files include other files, treating the `.cpp` and `.h` file as one unit.
 203 | +
 204 | +Example usage:
 205 | +
 206 | +    cd .../src
 207 | +    ../contrib/devtools/circular-dependencies.py {*,*/*,*/*/*}.{h,cpp}
    promag commented at 12:20 AM on May 15, 2018:

    nit ../contrib/devtools/circular-dependencies.py **/*.{h,cpp}.

    Empact commented at 2:08 AM on May 15, 2018:

    @promag FWIW on my system **/*.h does not capture immediate *.h files. But that may be mac gnu-sed specific.

    promag commented at 12:06 PM on May 16, 2018:

    Ah 😝never mind then.

  10. promag commented at 12:26 AM on May 15, 2018: member

    Tested ACK 50c69b78.

    👍 to @practicalswift suggestions.

    Is there a use case to pass only a subset of the files? I mean, instead of passing the list of files, the script could traverse the entire source tree.

    Suggestion, script could exit 0 if no circular dependencies are found.

  11. ken2812221 commented at 3:02 PM on May 15, 2018: contributor

    Tested ACK 50c69b78011c1bc55885ebfd216db60ed490ebea

  12. practicalswift commented at 9:44 AM on May 16, 2018: contributor

    ACK assuming output is made deterministic

    Nit: Would be nice if the exit code indicated if circular dependencies were found

  13. Add circular dependencies script a7b295e91e
  14. sipa force-pushed on May 16, 2018
  15. sipa commented at 11:56 PM on May 16, 2018: member

    Made the ordering deterministic, and added an exit code.

  16. Empact commented at 12:19 AM on May 17, 2018: member

    utACK a7b295e

  17. practicalswift commented at 4:47 AM on May 17, 2018: contributor

    utACK a7b295e91e4917495efe59948bae0ea554b7674c

  18. ken2812221 commented at 6:14 AM on May 17, 2018: contributor

    utACK a7b295e

  19. MarcoFalke merged this on May 18, 2018
  20. MarcoFalke closed this on May 18, 2018
  21. MarcoFalke referenced this in commit d792e47421 on May 18, 2018
  22. laanwj referenced this in commit 7c32b414b6 on Jun 11, 2018
  23. scravy referenced this in commit 7e67c75d6f on Apr 8, 2019
  24. PastaPastaPasta referenced this in commit 0295a8986a on Jun 17, 2020
  25. PastaPastaPasta referenced this in commit 6e5b3f3b9e on Jul 2, 2020
  26. PastaPastaPasta referenced this in commit 5103888706 on Jul 18, 2020
  27. PastaPastaPasta referenced this in commit cadbe8eefc on Jul 19, 2020
  28. DrahtBot locked this on Sep 8, 2021
Contributors
sipapromagfanquakepracticalswiftEmpactken2812221
Labels
Scripts and tools
Linked (view graph)
#13230 Simplify include analysis by enforcing the developer guide's include syntax
github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-04-13 18:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me