Recursion is a frequent source of stack overflow bugs. Secondly, introduction of recursion can be non-obvious.
This PR proposes to use the clang-tidy misc-no-recursion check to make introduction of new recursion obvious. We don't make use of recursion a lot in our code base but there are a few places that need suppressions anyway (mostly the descriptor and univalue/rpc code).
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
For detailed information about the code coverage, see the test coverage report.
<!--021abf342d371248e50ceaed478a90ca-->
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | TheCharlatan, fanquake, stickies-v |
| Concept ACK | glozow |
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
<!--174a7506f384e20aa4161008e828411d-->
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
<!--85328a0da195eb286784d51f73fa0af9-->
🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.
Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
Leave a comment here, if you need help tracking down a confusing failure.
<sub>Debug: https://github.com/bitcoin/bitcoin/runs/22930920119</sub>
Recursion is hard to get right and a frequent source of bugs.
It would be good to list at least one example in this codebase.
It would be good to list at least one example in this codebase.
A simple search for recursion on github turned up a few things:
Generally concept ACK, discouraging and making recursion explicit seems like the right thing to do. Would be nice (but I don't think possible) if this could be done at compile time instead of with clang-tidy, so devs find out quicker. Now, they might spend a whole lotta time implementing something, only to find out from CI that they shouldn't, and then potentially have to quite radically change their approach. Not a very common problem, I'd suspect though.
Probably useful to mention this in developer notes? E.g.:
diff --git a/doc/developer-notes.md b/doc/developer-notes.md
index 89c13600eb..afc1e10a0b 100644
--- a/doc/developer-notes.md
+++ b/doc/developer-notes.md
@@ -115,6 +115,8 @@ code.
Use `reinterpret_cast` and `const_cast` as appropriate.
- Prefer [`list initialization ({})`](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Res-list) where possible.
For example `int x{0};` instead of `int x = 0;` or `int x(0);`
+ - Recursive functions are generally discouraged, and checked for by clang-tidy. When recursiveness
+ is the best approach, use `NOLINTNEXTLINE(misc-no-recursion)` to suppress the check.
For function calls a namespace should be specified explicitly, unless such functions have been declared within it.
Otherwise, [argument-dependent lookup](https://en.cppreference.com/w/cpp/language/adl), also known as ADL, could be
Thanks @stickies-v! added your dev note suggestion
456 | @@ -455,6 +457,7 @@ class DescribeWalletAddressVisitor 457 | return obj; 458 | } 459 | 460 | + // NOLINTNEXTLINE(misc-no-recursion)
Was this raised by clang-tidy? I think this specific overload isn't recursive?
Looks like you were right! this suppression was removed on the latest push.
crACK 0c9db2b1bb41fe1b00844cd21f226a57aeaddc53
I ran clang-tidy on master with misc-no-recursion and verified that the exceptions made correspond with where clang-tidy warned for me, with the exception of DescribeWalletAddressVisitor::ProcessSubScript (and the operator() overloads), which mine missed completely. I suspect this is because of the std::visit indirection. (LLVM 17.0.6)
The main potential risk with this PR imo is increasing developer frustration/friction, so to avoid that I would quickly bring up this PR on the next Thursday IRC meeting so people are aware and can surface concerns early?
Recursion is hard to get right and a frequent source of bugs.
I don't agree with this as a general statement and I don't think any developer who has worked with a functional language for a few years would. I think bugs are just as likely to occur in loops and you will also find a lot of examples for that. Recursion is a very basic tool in software development and discouraging it in general feels wrong. A developer who is experienced with it should be able to use it if they think it's the right tool for the job.
Recursion is hard to get right and a frequent source of bugs.
I agree that this is perhaps subjective. I've amended the description.
I don't agree with this as a general statement and I don't think any developer who has worked with a functional language for a few years would.
To me it seems like programmers are unlikely to blame recursion for bugs, when recursion is their primary tool. We are not working with a functional language in this repository, so there is no strict need for recursion.
I think bugs are just as likely to occur in loops and you will also find a lot of examples for that.
Stack overflows caused by recursion is a specific class of bugs that can be avoided by simply not using recursion. Not using loops is obviously not an option in this repository. However, clang-tidy checks to avoid bugprone loop patterns might make sense in the same spirit as discouraging recursion, e.g. https://clang.llvm.org/extra/clang-tidy/checks/bugprone/infinite-loop.html.
A developer who is experienced with it should be able to use it if they think it's the right tool for the job.
I'm not proposing a ban on recursion. A experienced programmer can still choose to use recursion and suppress the linter.
ACK ca34f36c326ee8e54f170a61e86ed74e3cb04da1
Personally, I'm in favour of discouraging recursion and making it explicit when used. It very much still should be used where it makes most sense, and that's still possible without much overhead.
114 | @@ -115,6 +115,9 @@ code. 115 | Use `reinterpret_cast` and `const_cast` as appropriate. 116 | - Prefer [`list initialization ({})`](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Res-list) where possible. 117 | For example `int x{0};` instead of `int x = 0;` or `int x(0);` 118 | + - Recursive functions are generally discouraged, and checked for by
I think "generally" is too strong and also a bit of a contradiction with the next sentence. How about something like "Recursive functions are discouraged unless they are the best approach for a given problem. In this case NOLINTNEXTLINE(misc-no-recursion) can be used to suppress the clang-tidy check."
I do not think recursive functions should be "generally discouraged" or "discouraged". Consider this wording instead:
"Think twice before introducing recursive functions. Consider an iterative approach as well. When recursiveness is the best approach, use NOLINTNEXTLINE(misc-no-recursion) to suppress the check."
"Think twice before introducing recursive functions. Consider an iterative approach as well."
This just reads like a long form of "recursion is discouraged" to me.
I think "generally" is too strong
"generally" makes it less strong, since without it the sentence would imply it's always discouraged.
It's getting a bit too bikesheddy for me so I'm going to leave this conversation here. Imo all three suggestions so far pretty much achieve the same intent (and I'd be okay with): recursion should be used if it's clearly the best choice, otherwise don't.
"generally" makes it less strong, since without it the sentence would imply it's always discouraged.
I disagree and I did not suggest to just strike it but to use a different wording that is more clear. As it is now, I read this as "When you think you want to use recursion, you are generally wrong.". Maybe it's my ego but I don't like that statement ;) I suppose you read this as "When you want to iterate over anything, generally you shouldn't use recursion." and that is also a reasonable interpretation but I don't think the distinction is clear.
(Also adding my comment from IRC in case the discussion continues here) I think it’s not going to be doing much for us because it’s not like inexperienced developers include recursion in their PRs by accident very often. But since this also won’t affect ~99% all PRs anyway, I won’t stand in the way if enough others see value in this.
114 | @@ -115,6 +115,9 @@ code. 115 | Use `reinterpret_cast` and `const_cast` as appropriate. 116 | - Prefer [`list initialization ({})`](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Res-list) where possible. 117 | For example `int x{0};` instead of `int x = 0;` or `int x(0);` 118 | + - Recursive functions are generally discouraged, and checked for by 119 | + clang-tidy. When recursiveness is the best approach, use
Not sure if the point is to discourage recursion, or to tell developers that it has to be marked explicitly? I think we can consider it implied that people should use recursion only when appropriate, just like any other practices that can lead to bugs. And disagreements about whether or not [fill in the blank] is appropriate can be resolved in review on a case-by-case basis.
- Recursion is checked by clang-tidy and thus must be made explicit. Use
That framing makes a lot more sense to me 👍
Concept ACK, as I think we agree that we want to avoid unintentional recursion. I think it's useful to have all of our recursive functions enumerated.
Concept ACK. I think tracking where any recursion currently is, is useful, as well as being alerted to new usage in the future.
Changed the dev note. Ready for review.
ACK d9536e6e423ef7384a1869f3ac8a9cf7f503ed6f
<!--85328a0da195eb286784d51f73fa0af9-->
🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.
Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
Leave a comment here, if you need help tracking down a confusing failure.
<sub>Debug: https://github.com/bitcoin/bitcoin/runs/23504435199</sub>
Co-authored-by: stickies-v <stickies-v@protonmail.com>
Co-authored-by: Gloria Zhao <gloriajzhao@gmail.com>
Rebased due to conflict
Re-ACK 78407b99ed6dd17f687fcbfb0486ecc433302287
ACK 78407b99ed6dd17f687fcbfb0486ecc433302287
ACK 78407b99ed6dd17f687fcbfb0486ecc433302287