Add script to detect circular dependencies between source modules #13228

sipa · 2018-05-13T20:27:53Z

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

promag · 2018-05-13T22:43:51Z

Concept ACK.

fanquake · 2018-05-14T07:16:03Z

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

practicalswift · 2018-05-14T07:30:43Z

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]

Empact · 2018-05-14T21:52:53Z

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.

sipa · 2018-05-14T22:02:47Z

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.

promag

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.

promag · 2018-05-15T00:20:05Z

contrib/devtools/README.md

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

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

Ah 😝never mind then.

ken2812221 · 2018-05-15T15:02:32Z

Tested ACK 50c69b78011c1bc55885ebfd216db60ed490ebea

practicalswift · 2018-05-16T09:44:03Z

ACK assuming output is made deterministic

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

sipa · 2018-05-16T23:56:23Z

Made the ordering deterministic, and added an exit code.

Empact · 2018-05-17T00:19:55Z

utACK a7b295e

practicalswift · 2018-05-17T04:47:38Z

utACK a7b295e

ken2812221 · 2018-05-17T06:14:23Z

utACK a7b295e

…ce modules a7b295e 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

@sipa

…ide's include syntax 16e3cd3 Clarify include recommendation (practicalswift) 6d10f43 Enforce the use of bracket syntax includes ("#include <foo.h>") (practicalswift) 906bee8 Use bracket syntax includes ("#include <foo.h>") (practicalswift) Pull request description: When analysing includes in the project it is often assumed that the preferred bracket include syntax (`#include <foo.h>`) mentioned in `developer-docs.md` is used consistently. @sipa:s excellent circular dependencies script [`circular-dependencies.py`](https://github.com/sipa/bitcoin/blob/50c69b78011c1bc55885ebfd216db60ed490ebea/contrib/devtools/circular-dependencies.py) (#13228) is an example of a script making this reasonable assumption. This PR enables automatic Travis checking of the include syntax making sure that the bracket syntax includes (`#include <foo.h>`) is used consistently. Tree-SHA512: a414921aabe8e487ebed42f3f1cbd02fecd1add385065c1f2244cd602c31889e61fea5a801507ec501ef9bd309b05d3c999f915cec1c2b44f085bb0d2835c182

Backport of bitcoin/bitcoin#13228 Signed-off-by: Julian Fleischer <[email protected]>

@sipa

…oper guide's include syntax 16e3cd3 Clarify include recommendation (practicalswift) 6d10f43 Enforce the use of bracket syntax includes ("#include <foo.h>") (practicalswift) 906bee8 Use bracket syntax includes ("#include <foo.h>") (practicalswift) Pull request description: When analysing includes in the project it is often assumed that the preferred bracket include syntax (`#include <foo.h>`) mentioned in `developer-docs.md` is used consistently. @sipa:s excellent circular dependencies script [`circular-dependencies.py`](https://github.com/sipa/bitcoin/blob/50c69b78011c1bc55885ebfd216db60ed490ebea/contrib/devtools/circular-dependencies.py) (bitcoin#13228) is an example of a script making this reasonable assumption. This PR enables automatic Travis checking of the include syntax making sure that the bracket syntax includes (`#include <foo.h>`) is used consistently. Tree-SHA512: a414921aabe8e487ebed42f3f1cbd02fecd1add385065c1f2244cd602c31889e61fea5a801507ec501ef9bd309b05d3c999f915cec1c2b44f085bb0d2835c182 Signed-off-by: pasta <[email protected]>

…en source modules a7b295e 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

sipa force-pushed the 201805_circular_detect branch from 36257f9 to 50c69b7 Compare May 13, 2018 20:30

fanquake added the Scripts and tools label May 13, 2018

practicalswift mentioned this pull request May 14, 2018

Simplify include analysis by enforcing the developer guide's include syntax #13230

Merged

Empact mentioned this pull request May 15, 2018

Break circular dependency: chain -> pow -> chain #13234

Merged

promag reviewed May 15, 2018

View reviewed changes

Empact mentioned this pull request May 15, 2018

Break circular dependency: init -> * -> init by extracting shutdown.h #13235

Merged

Add circular dependencies script

a7b295e

sipa force-pushed the 201805_circular_detect branch from 50c69b7 to a7b295e Compare May 16, 2018 23:55

maflcko merged commit a7b295e into bitcoin:master May 18, 2018

Bushstar mentioned this pull request May 21, 2018

commits from bitcoin/master FeatherCoin/Feathercoin#334

Merged

Empact mentioned this pull request Jul 18, 2018

lint: Add linter for circular dependencies #13695

Merged

HashUnlimited mentioned this pull request Sep 11, 2018

Simplify include analysis by enforcing the developer guide's include syntax chaincoin/chaincoin#410

Merged

scravy mentioned this pull request Apr 8, 2019

Add circular dependencies script dtr-org/unit-e#905

Merged

scravy added a commit to dtr-org/unit-e that referenced this pull request Apr 8, 2019

Add circular dependencies script (#905)

7e67c75

Backport of bitcoin/bitcoin#13228 Signed-off-by: Julian Fleischer <[email protected]>

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Add script to detect circular dependencies between source modules #13228

Add script to detect circular dependencies between source modules #13228

Uh oh!

Conversation

sipa commented May 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

promag commented May 13, 2018

Uh oh!

fanquake commented May 14, 2018

Uh oh!

practicalswift commented May 14, 2018

Uh oh!

Empact commented May 14, 2018

Uh oh!

sipa commented May 14, 2018

Uh oh!

promag left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

promag May 15, 2018

Choose a reason for hiding this comment

Uh oh!

Empact May 15, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

promag May 16, 2018

Choose a reason for hiding this comment

Uh oh!

ken2812221 commented May 15, 2018

Uh oh!

practicalswift commented May 16, 2018

Uh oh!

sipa commented May 16, 2018

Uh oh!

Empact commented May 17, 2018

Uh oh!

practicalswift commented May 17, 2018

Uh oh!

ken2812221 commented May 17, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

sipa commented May 13, 2018 •

edited

Loading

promag left a comment •

edited

Loading

Empact May 15, 2018 •

edited

Loading