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:

     0$ ../contrib/devtools/circular-dependencies.py {*,*/*,*/*/*}.{h,cpp}
 1Circular dependency: chain -> pow -> chain
 2Circular dependency: chainparamsbase -> util -> chainparamsbase
 3Circular dependency: checkpoints -> validation -> checkpoints
 4Circular dependency: init -> index/txindex -> init
 5Circular dependency: init -> validation -> init
 6Circular dependency: init -> net_processing -> init
 7Circular dependency: init -> rpc/server -> init
 8Circular dependency: init -> txdb -> init
 9Circular dependency: init -> validationinterface -> init
10Circular dependency: random -> util -> random
11Circular dependency: sync -> util -> sync
12Circular dependency: txmempool -> validation -> txmempool
13Circular dependency: txmempool -> policy/fees -> txmempool
14Circular dependency: validation -> index/txindex -> validation
15Circular dependency: validation -> policy/policy -> validation
16Circular dependency: validation -> validationinterface -> validation
17Circular dependency: qt/addresstablemodel -> qt/walletmodel -> qt/addresstablemodel
18Circular dependency: qt/bantablemodel -> qt/clientmodel -> qt/bantablemodel
19Circular dependency: qt/bitcoingui -> qt/walletview -> qt/bitcoingui
20Circular dependency: qt/bitcoingui -> qt/walletframe -> qt/bitcoingui
21Circular dependency: qt/bitcoingui -> qt/utilitydialog -> qt/bitcoingui
22Circular dependency: qt/clientmodel -> qt/peertablemodel -> qt/clientmodel
23Circular dependency: qt/paymentserver -> qt/walletmodel -> qt/paymentserver
24Circular dependency: qt/recentrequeststablemodel -> qt/walletmodel -> qt/recentrequeststablemodel
25Circular dependency: qt/sendcoinsdialog -> qt/walletmodel -> qt/sendcoinsdialog
26Circular dependency: qt/transactiontablemodel -> qt/walletmodel -> qt/transactiontablemodel
27Circular dependency: qt/walletmodel -> qt/walletmodeltransaction -> qt/walletmodel
28Circular dependency: rpc/rawtransaction -> wallet/rpcwallet -> rpc/rawtransaction
29Circular dependency: wallet/coincontrol -> wallet/wallet -> wallet/coincontrol
30Circular dependency: wallet/fees -> wallet/wallet -> wallet/fees
31Circular dependency: wallet/rpcwallet -> wallet/wallet -> wallet/rpcwallet
32Circular dependency: wallet/walletdb -> wallet/wallet -> wallet/walletdb
33Circular dependency: txmempool -> validation -> policy/rbf -> txmempool
34Circular dependency: txmempool -> validation -> validationinterface -> txmempool
35Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/addressbookpage
36Circular dependency: qt/guiutil -> qt/walletmodel -> qt/optionsmodel -> qt/guiutil
37Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/signverifymessagedialog -> qt/addressbookpage
38Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/receivecoinsdialog -> qt/addressbookpage
39Circular dependency: qt/guiutil -> qt/walletmodel -> qt/optionsmodel -> qt/intro -> qt/guiutil
40Circular 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

     0bash-3.2$ ../contrib/devtools/circular-dependencies.py {*,*/*,*/*/*}.{h,cpp}
 1Circular dependency: chain -> pow -> chain
 2Circular dependency: chainparamsbase -> util -> chainparamsbase
 3Circular dependency: checkpoints -> validation -> checkpoints
 4Circular dependency: init -> net_processing -> init
 5Circular dependency: init -> index/txindex -> init
 6Circular dependency: init -> rpc/server -> init
 7Circular dependency: init -> txdb -> init
 8Circular dependency: init -> validation -> init
 9Circular dependency: init -> validationinterface -> init
10Circular dependency: random -> util -> random
11Circular dependency: sync -> util -> sync
12Circular dependency: txmempool -> policy/fees -> txmempool
13Circular dependency: txmempool -> validation -> txmempool
14Circular dependency: validation -> index/txindex -> validation
15Circular dependency: validation -> validationinterface -> validation
16Circular dependency: validation -> policy/policy -> validation
17Circular dependency: qt/addresstablemodel -> qt/walletmodel -> qt/addresstablemodel
18Circular dependency: qt/bantablemodel -> qt/clientmodel -> qt/bantablemodel
19Circular dependency: qt/bitcoingui -> qt/utilitydialog -> qt/bitcoingui
20Circular dependency: qt/bitcoingui -> qt/walletview -> qt/bitcoingui
21Circular dependency: qt/bitcoingui -> qt/walletframe -> qt/bitcoingui
22Circular dependency: qt/clientmodel -> qt/peertablemodel -> qt/clientmodel
23Circular dependency: qt/paymentserver -> qt/walletmodel -> qt/paymentserver
24Circular dependency: qt/recentrequeststablemodel -> qt/walletmodel -> qt/recentrequeststablemodel
25Circular dependency: qt/sendcoinsdialog -> qt/walletmodel -> qt/sendcoinsdialog
26Circular dependency: qt/transactiontablemodel -> qt/walletmodel -> qt/transactiontablemodel
27Circular dependency: qt/walletmodel -> qt/walletmodeltransaction -> qt/walletmodel
28Circular dependency: rpc/rawtransaction -> wallet/rpcwallet -> rpc/rawtransaction
29Circular dependency: wallet/coincontrol -> wallet/wallet -> wallet/coincontrol
30Circular dependency: wallet/fees -> wallet/wallet -> wallet/fees
31Circular dependency: wallet/rpcwallet -> wallet/wallet -> wallet/rpcwallet
32Circular dependency: wallet/wallet -> wallet/walletdb -> wallet/wallet
33Circular dependency: txmempool -> validation -> policy/rbf -> txmempool
34Circular dependency: txmempool -> validation -> validationinterface -> txmempool
35Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/addressbookpage
36Circular dependency: qt/guiutil -> qt/walletmodel -> qt/optionsmodel -> qt/guiutil
37Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/signverifymessagedialog -> qt/addressbookpage
38Circular dependency: qt/addressbookpage -> qt/bitcoingui -> qt/walletview -> qt/receivecoinsdialog -> qt/addressbookpage
39Circular dependency: qt/guiutil -> qt/walletmodel -> qt/optionsmodel -> qt/intro -> qt/guiutil
40Circular 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:

     0--- ../circular-dependencies.py	2018-05-14 08:50:58.691253505 +0200
 1+++ ../circular-dependencies-deterministic.py	2018-05-14 09:28:20.164794798 +0200
 2@@ -35,7 +35,7 @@
 3
 4 # Iterate again, and build list of direct dependencies for each module
 5 # TODO: implement support for multiple include directories
 6-for arg in files.keys():
 7+for arg in sorted(files.keys()):
 8     module = files[arg]
 9     with open(arg, 'r') as f:
10         for line in f:
11@@ -49,7 +49,7 @@
12 # Loop to find the shortest (remaining) circular dependency
13 while True:
14     shortest_cycle = None
15-    for module in deps.keys():
16+    for module in sorted(deps.keys()):
17         # Build the transitive closure of dependencies of module
18         closure = dict()
19         for dep in deps[module]:
20@@ -57,7 +57,7 @@
21         while True:
22             old_size = len(closure)
23             old_closure_keys = list(closure.keys())
24-            for src in old_closure_keys:
25+            for src in sorted(old_closure_keys):
26                 for dep in deps[src]:
27                     if dep not in closure:
28                         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 0: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 0: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 0: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


sipa promag fanquake practicalswift Empact ken2812221

Labels
Scripts and tools

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: 2024-12-18 21:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me