clang-tidy: Enable misc-no-recursion

[dergoegge]

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).

[DrahtBot]

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

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.

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #28710 (Remove the legacy wallet and BDB dependency by achow101)
• #27865 (wallet: Track no-longer-spendable TXOs separately by achow101)
• #22838 (descriptors: Be able to specify change and receiving in a single descriptor string by achow101)

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.

[DrahtBot]

🚧 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.

_{Debug: https://github.com/bitcoin/bitcoin/runs/22930920119}

[maflcko]

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.

[dergoegge]

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:

• Avoid running out of stack space by limiting recursion depth in Parse(...) sipa/miniscript#5
  • From the miniscript introduction PR: "all recursive algorithms were made non-recursive" (Miniscript integration #24147 (comment))
• Fix OP_EVAL recursion depth counting #730
• Fix for #956 (GUI freeze on Windows) #980 (comment)
• Remove CWalletTx::vfSpent #3694 (comment)

[stickies-v]

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.

[stickies-v]

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

[dergoegge]

Thanks @stickies-v! added your dev note suggestion

[stickies-v]

crACK 0c9db2b

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?

[fjahr]

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.

[dergoegge]

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.

[stickies-v]

ACK ca34f36

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.

[fjahr]

(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.

[glozow]

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.

[fanquake]

Concept ACK. I think tracking where any recursion currently is, is useful, as well as being alerted to new usage in the future.

[dergoegge]

Changed the dev note. Ready for review.

[TheCharlatan]

ACK d9536e6

[DrahtBot]

🚧 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.

_{Debug: https://github.com/bitcoin/bitcoin/runs/23504435199}

[dergoegge]

Rebased due to conflict

[TheCharlatan]

Re-ACK 78407b9

[fanquake]

ACK 78407b9

[stickies-v]

ACK 78407b9