miniscript refactor: Remove unique_ptr-indirection (#30866 follow-up) #31713

pull hodlinator wants to merge 7 commits into bitcoin:master from hodlinator:2024/11/miniscript_ownership changing 4 files +380 −332
  1. hodlinator commented at 9:16 pm on January 22, 2025: contributor

    Removes one level of unnecessary indirection, which was a change that originally aided in finding one issue in #30866. Simplifies the code one step further than 09a1875ad8cddeb17c19af34b8282d37fed0937e belonging to aforementioned PR.

    Also adds test which verifies resistance to stack overflow when it comes to ~Node() and Node::Clone().

    No observed difference when running benchmarks: ExpandDescriptor/WalletIsMineDescriptors/WalletIsMineMigratedDescriptors/WalletLoadingDescriptors.

  2. DrahtBot commented at 9:16 pm on January 22, 2025: contributor

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

    Code Coverage & Benchmarks

    For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31713.

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    Concept ACK sipa
    Stale ACK l0rinc

    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:

    • #32471 (wallet/rpc: fix listdescriptors RPC fails to return descriptors with private key information when wallet contains descriptors missing any key by Eunovo)
    • #31734 (miniscript: account for all StringType variants in Miniscriptdescriptor::ToString() by pythcoiner)

    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.

  3. hodlinator commented at 9:20 pm on January 22, 2025: contributor

    CC @achow101 @darosior @brunoerg from parent PR to gauge their interest.

    It’s unfortunate that this PR touches many lines, so if there’s little support for the refactoring I’m fine with closing, or letting it linger for a while (I understand this is super-low priority). At least it helped find the issue mentioned at the top of the summary.

  4. darosior commented at 1:04 am on January 23, 2025: member

    CI failure looks unrelated. Could you s/script/miniscript/ in the PR title to make it clear to reviewer this does not touch consensus critical stuff?

    It’s unfortunate that this PR touches many lines

    It’s also not a part of the codebase where i expect much churn, so it probably lowers the bar for doing something like this.

  5. hodlinator renamed this:
    script refactor: Remove superfluous unique_ptr-indirection (#30866 follow-up)
    miniscript refactor: Remove unique_ptr-indirection (#30866 follow-up)
    on Jan 23, 2025
  6. hodlinator force-pushed on Jan 23, 2025
  7. maflcko commented at 8:33 am on January 23, 2025: member

    CI failure looks unrelated.

    I can’t seem to find it. It would be good to always report or at least leave a comment with the log to any CI failure. Otherwise, it will remain unfixed and will just happen on another pull later on.

  8. l0rinc commented at 8:59 am on January 23, 2025: contributor

    leave a comment with the log to any CI failure

    I think they meant the p2p_1p1c_network failure at https://github.com/bitcoin/bitcoin/actions/runs/12917231673/job/36023158007?pr=31713

  9. hodlinator commented at 9:05 am on January 23, 2025: contributor

    I think they meant the p2p_1p1c_network failure at https://github.com/bitcoin/bitcoin/actions/runs/12917231673/job/36023158007?pr=31713

    Yes, that’s the one, thanks for finding it @l0rinc!

    Could you s/script/miniscript/ in the PR title to make it clear to reviewer this does not touch consensus critical stuff?

    Updated PR title and commit message titles.

  10. darosior commented at 3:36 pm on January 23, 2025: member

    From a quick skim, this looks fine to me. I wonder if @sipa has any objection to not using pointers here.

    Let me see if we can get the conflicts in first and then do this when nothing else is conflicting anymore.

  11. sipa commented at 5:07 pm on January 23, 2025: member

    Very rough-skim Concept ACK.

    This will make the code diverge further from the c++ miniscript policy compiler code, but that’s a bullet we already took with the shared_ptr to unique_ptr change, and it doesn’t seem there is development happening on that anyway.

  12. in src/script/descriptor.cpp:1304 in 58e9c7ca89 outdated
    1300@@ -1301,31 +1301,31 @@ class StringMaker {
    1301 class MiniscriptDescriptor final : public DescriptorImpl
    1302 {
    1303 private:
    1304-    miniscript::NodeRef<uint32_t> m_node;
    1305+    const miniscript::Node<uint32_t> m_node;
    


    purpleKarrot commented at 4:02 pm on February 27, 2025:

    hodlinator commented at 3:51 pm on March 1, 2025:

    Thanks for having a look! const fields are the bane of making types movable, as in c7f1829b4bb3a579c65a99a62b42f64de946c0da of this very PR, so good to have another argument in that direction.

    Still think there’s some value in marking fields as const to collapse down the mental model of the code when moving is not necessary. Wish we had “const except on move”.

    But I’ve proven my point that it can now be made const. I’ll remove it on the next push.


    hodlinator commented at 2:41 pm on March 20, 2025:
    Adjusted in latest push, which is otherwise just a rebase.
  13. laanwj added the label Utils/log/libs on Mar 4, 2025
  14. DrahtBot added the label Needs rebase on Mar 20, 2025
  15. hodlinator force-pushed on Mar 20, 2025
  16. DrahtBot removed the label Needs rebase on Mar 20, 2025
  17. DrahtBot added the label Needs rebase on Apr 10, 2025
  18. hodlinator force-pushed on Apr 12, 2025
  19. DrahtBot removed the label Needs rebase on Apr 12, 2025
  20. DrahtBot added the label Needs rebase on Apr 29, 2025
  21. hodlinator force-pushed on Apr 30, 2025
  22. DrahtBot removed the label Needs rebase on Apr 30, 2025
  23. DrahtBot added the label CI failed on Apr 30, 2025
  24. DrahtBot commented at 10:33 am on April 30, 2025: contributor

    🚧 At least one of the CI tasks failed. Task tidy: https://github.com/bitcoin/bitcoin/runs/41407555382 LLM reason (✨ experimental): The CI failure is caused by clang-tidy reporting errors related to functions being within a recursive call chain, indicating static analysis issues rather than build or test errors.

    Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

    • Possibly 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.

    • A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

    • An intermittent issue.

    Leave a comment here, if you need help tracking down a confusing failure.

  25. hodlinator force-pushed on Apr 30, 2025
  26. hodlinator force-pushed on Apr 30, 2025
  27. hodlinator force-pushed on Apr 30, 2025
  28. hodlinator force-pushed on Apr 30, 2025
  29. hodlinator force-pushed on Apr 30, 2025
  30. hodlinator force-pushed on Apr 30, 2025
  31. maflcko commented at 10:16 am on May 6, 2025: member
    If there is a clang-tidy bug, it could make sense to minimize the reproducer and report/fix it upstream
  32. hodlinator commented at 10:23 am on May 6, 2025: contributor

    If there is a clang-tidy bug, it could make sense to minimize the reproducer and report/fix it upstream

    Currently trying to just recreate the CI failure locally on NixOS instead of spamming subscribers of the PR (a bit involved due to clang-tidy depending on generated LLVM headers). I keep getting nerd-sniped into trying a more NixOS-native approach. Was able to iterate through env -i HOME="$HOME" PATH="$PATH" USER="$USER" bash -c 'MAKEJOBS="-j$(nproc)" FILE_ENV="./ci/test/00_setup_env_native_tidy.sh" ./ci/test_run_all.sh'.

    https://reviews.llvm.org/D72362 which added the recursion check does mention not supporting destructors.

    Edit: Using NOLINTBEGIN/-END rather than NOLINTNEXTLINE did the job. So it was just invalid use of clang-tidy, not a bug.

  33. hodlinator force-pushed on May 7, 2025
  34. DrahtBot removed the label CI failed on May 7, 2025
  35. in src/script/miniscript.h:420 in 33df8e9103 outdated
    413@@ -421,11 +414,11 @@ struct Ops {
    414  */
    415 struct SatInfo {
    416     //! Whether a canonical satisfaction/dissatisfaction is possible at all.
    417-    const bool valid;
    418+    bool valid;
    419     //! How much higher the stack size at start of execution can be compared to at the end.
    420-    const int32_t netdiff;
    421+    int32_t netdiff;
    422     //! Mow much higher the stack size can be during execution compared to at the end.
    


    maflcko commented at 12:58 pm on May 7, 2025:

    unrelated, but it looks like there are typos:

    Mow much -> How much [Typo in “Mow much”]

    RIPEMD10 -> RIPEMD160 [Incorrect algorithm name]


    hodlinator commented at 3:07 pm on May 7, 2025:
    Taken in latest push.
  36. hodlinator force-pushed on May 7, 2025
  37. in src/test/fuzz/miniscript.cpp:314 in 8ccda63b6a outdated
    310@@ -311,11 +311,6 @@ const struct KeyComparator {
    311 // A dummy scriptsig to pass to VerifyScript (we always use Segwit v0).
    312 const CScript DUMMY_SCRIPTSIG;
    313 
    314-//! Construct a miniscript node as a shared_ptr.
    


    hodlinator commented at 12:22 pm on June 18, 2025:

    @maflcko, the LLM linter is showing issues for the code before my changes, and also changing casing by itself which causes it to detect it as an error:

    Possible typos and grammar issues:

    * Mow much higher -> How much higher [Typo in comment]
    
    * Constructed.emplace_back -> constructed.emplace_back [Typo in variable name]
    
    * //! Construct a miniscript node as a shared_ptr. -> This comment is inaccurate given the code changes, as Node is no longer represented by a shared_ptr. [Inaccurate comment]
    

    maflcko commented at 12:26 pm on June 18, 2025:
    Thx, this was fixed in https://github.com/maflcko/DrahtBot/commit/30bb2f0baa4e920211cfa35f5be72aed013253a1 last month. You can ignore it, or rebase, if you want it to re-run.

    hodlinator commented at 9:03 pm on June 18, 2025:
    Rebased, thanks!
  38. hodlinator force-pushed on Jun 18, 2025
  39. in src/script/miniscript.h:518 in db2ede0828 outdated
    514@@ -515,9 +515,11 @@ struct Node {
    515     //! The Script context for this node. Either P2WSH or Tapscript.
    516     const MiniscriptContext m_script_ctx;
    517 
    518-    /* Destroy the shared pointers iteratively to avoid a stack-overflow due to recursive calls
    


    l0rinc commented at 12:12 pm on June 22, 2025:
    The comment is a #30866 leftover, right? we might want to mention it in the commit message for context (i.e. independently of the PR’s description)

    hodlinator commented at 6:43 am on June 24, 2025:
    Added to reference in commit message.
  40. in src/script/miniscript.h:535 in db2ede0828 outdated
    520-    ~Node() {
    521+    ~Node()
    522+    {
    523+        // Destroy the subexpressions iteratively after moving out their
    524+        // subexpressions to avoid a stack-overflow due to recursive calls to
    525+        // the subs' destructors.
    


    l0rinc commented at 12:17 pm on June 22, 2025:

    so this basically flattens out the tree structure to make sure the desctructor’s call stack has at most 1 indirection? Would TreeEval complicate this too much?

    Do we have a test that makes sure this doesn’t cause a stack-overflow? Maybe we could cover these changed lines with something that exercises the clone and destructor, e.g.:

     0// Confirm that `Node`’s destructor and Clone() are stack-safe
     1BOOST_AUTO_TEST_CASE(node_deep_destruct)
     2{
     3    using miniscript::internal::NoDupCheck;
     4    using miniscript::Fragment;
     5    using NodeU32 = miniscript::Node<uint32_t>;
     6
     7    constexpr auto ctx{miniscript::MiniscriptContext::P2WSH};
     8
     9    NodeU32 root{NoDupCheck{}, ctx, Fragment::JUST_1};
    10    for (uint32_t i{0}; i < 100'000; ++i) {
    11        root = NodeU32{NoDupCheck{}, ctx, Fragment::WRAP_S, Vector(std::move(root))};
    12    }
    13
    14    for(auto clone{root.Clone()}; !clone.subs.empty(); ) {
    15        BOOST_CHECK_EQUAL(clone.subs.size(), root.subs.size());
    16        clone = std::move(clone.subs[0]);
    17        root = std::move(root.subs[0]);
    18    }
    19}
    

    which would fail for:

    0~Node()
    1{
    2}
    

    or

    0Node<Key> Clone() const
    1{
    2    std::vector<Node> new_subs;
    3    new_subs.reserve(subs.size());
    4    for (const Node& child : subs) {
    5        new_subs.push_back(child.Clone());
    6    }
    7
    8    return Node{internal::NoDupCheck{}, m_script_ctx, fragment, std::move(new_subs), keys, data, k};
    9}
    

    hodlinator commented at 12:17 pm on June 24, 2025:

    Thanks for the test! Added as the last commit (78db9e119136154bd733c95fc6379c780703234a f22f4f75e252e4f2171af34e4f92f3e6a396f227). Had to increase the depth from 100'000 to 1000'000 for it to cause stack overflow. Could simplify Clone()ing.

    so this basically flattens out the tree structure to make sure the desctructor’s call stack has at most 1 indirection? Would TreeEval complicate this too much?

    I’ve brought back an earlier version of the destructor I had that destroys entire vector<Node>s at once in a separate commit (106d6937372ce62ccebf5d2c019381a337681826 00ce8ef316646221c7a2d21734694bf27cae71df). If that doesn’t satisfy I’m happy to see a TreeEval-version.


    l0rinc commented at 7:15 am on June 25, 2025:
    Nice, I like the new one a lot more (moving the whole subs vector instead of one-by-one)! One small nit: I think I’d prefer the flattening metaphor rather than the stripping one

    hodlinator commented at 5:33 pm on June 27, 2025:
    (Forgot to mention but I changed from to_be_stripped + stripping to queue + flattening). https://github.com/bitcoin/bitcoin/blob/2bb86e371c21ca996cf8c1fbc80bc9b39f3d1dec/src/script/miniscript.h#L536-L544

    l0rinc commented at 9:25 pm on June 27, 2025:
    … and you also changed to do/while since there’s always at least one value in the queue 👍
  41. in src/script/miniscript.h:525 in db2ede0828 outdated
    523+        // Destroy the subexpressions iteratively after moving out their
    524+        // subexpressions to avoid a stack-overflow due to recursive calls to
    525+        // the subs' destructors.
    526         while (!subs.empty()) {
    527             auto node = std::move(subs.back());
    528             subs.pop_back();
    


    l0rinc commented at 12:23 pm on June 22, 2025:
    Given that this can cause stack overflow, I assume the levels aren’t trivial, which makes me wonder if we can Bulk move all node->subs over (in a reverse order though) and clear it at the end instead of popping one-by-one.

    hodlinator commented at 12:19 pm on June 24, 2025:
    I prefer moving whole vectors. See reply to #31713 (review).
  42. in src/script/miniscript.h:514 in c04b7b490e outdated
    514-    const std::vector<unsigned char> data;
    515+    std::vector<Key> keys;
    516+    //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD160).
    517+    std::vector<unsigned char> data;
    518     //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
    519     mutable std::vector<NodeRef<Key>> subs;
    


    l0rinc commented at 12:44 pm on June 22, 2025:
    Could we remove the mutable in commit c04b7b490e0c63942000472ea9f918df326c5b00 for consistency?

    hodlinator commented at 12:20 pm on June 24, 2025:
    It got a bit complicated since NodeRef is internally const (std::unique_ptr<const Node<Key>>). Did it as a separate commit for now: effcf701474eacd85a24da4d1707120fc756aa91.
  43. in src/test/miniscript_tests.cpp:653 in 5e4573adda outdated
    649@@ -650,13 +650,13 @@ BOOST_AUTO_TEST_CASE(fixed_tests)
    650     // A Script with a non minimal push is invalid
    651     constexpr auto nonminpush{"0000210232780000feff00ffffffffffff21ff005f00ae21ae00000000060602060406564c2102320000060900fe00005f00ae21ae00100000060606060606000000000000000000000000000000000000000000000000000000000000000000"_hex_u8};
    652     const CScript nonminpush_script(nonminpush.begin(), nonminpush.end());
    653-    BOOST_CHECK(miniscript::FromScript(nonminpush_script, wsh_converter) == nullptr);
    654-    BOOST_CHECK(miniscript::FromScript(nonminpush_script, tap_converter) == nullptr);
    655+    BOOST_CHECK(miniscript::FromScript(nonminpush_script, wsh_converter) == std::nullopt);
    


    l0rinc commented at 12:49 pm on June 22, 2025:

    We could even simplify these to:

    0    BOOST_CHECK(!miniscript::FromScript(nonminpush_script, wsh_converter));
    

    (given that *_EQUALS wouldn’t easily work)


    hodlinator commented at 7:34 am on June 24, 2025:
    Was doing that in earlier pushes of the PR but changed back to != nullopt since it disambiguates pointer/optional cases and is closer to master.
  44. in src/script/miniscript.h:195 in 5e4573adda outdated
    187@@ -188,13 +188,6 @@ inline consteval Type operator""_mst(const char* c, size_t l)
    188 
    189 using Opcode = std::pair<opcodetype, std::vector<unsigned char>>;
    190 
    191-template<typename Key> struct Node;
    192-template<typename Key> using NodeRef = std::unique_ptr<const Node<Key>>;
    193-
    194-//! Construct a miniscript node as a unique_ptr.
    195-template<typename Key, typename... Args>
    


    l0rinc commented at 12:50 pm on June 22, 2025:
    commit 5e4573adda107e6bfad6ba1afb417fdb4fdc81ed is too big (especially compared to the rest), could we do it in smaller scripted diffs instead?

    hodlinator commented at 1:19 pm on June 24, 2025:

    Broke out removal of NodeRef & MakeNodeRef() as mentioned in other comment.

    Let me know if you still see potential in for a non-contrived scripted diff.

  45. in src/script/miniscript.h:522 in 5e4573adda outdated
    517@@ -523,25 +518,27 @@ struct Node {
    518         while (!subs.empty()) {
    519             auto node = std::move(subs.back());
    520             subs.pop_back();
    521-            while (!node->subs.empty()) {
    522-                subs.push_back(std::move(node->subs.back()));
    523-                node->subs.pop_back();
    524+            while (!node.subs.empty()) {
    525+                subs.emplace_back(std::move(node.subs.back()));
    


    l0rinc commented at 12:52 pm on June 22, 2025:

    maybe we could do the push_back -> emplace_back changes in a separate commit. I’m not sure all of them make sense - does emplace_back have any advantage when the objects are already built?

     0diff --git a/src/script/miniscript.h b/src/script/miniscript.h
     1index f99c9a8036..be1913b785 100644
     2--- a/src/script/miniscript.h
     3+++ b/src/script/miniscript.h
     4@@ -519,7 +519,7 @@ struct Node {
     5             auto node = std::move(subs.back());
     6             subs.pop_back();
     7             while (!node.subs.empty()) {
     8-                subs.emplace_back(std::move(node.subs.back()));
     9+                subs.push_back(std::move(node.subs.back()));
    10                 node.subs.pop_back();
    11             }
    12         }
    13@@ -534,7 +534,7 @@ struct Node {
    14             for (auto& child : children) {
    15                 // It's fine to move from children as they are new nodes having
    16                 // been produced by calling this function one level down.
    17-                new_subs.emplace_back(std::move(child));
    18+                new_subs.push_back(std::move(child));
    19             }
    20             return Node{internal::NoDupCheck{}, node.m_script_ctx, node.fragment, std::move(new_subs), node.keys, node.data, node.k};
    21         };
    22diff --git a/src/test/fuzz/miniscript.cpp b/src/test/fuzz/miniscript.cpp
    23index c9904583e5..743226c33f 100644
    24--- a/src/test/fuzz/miniscript.cpp
    25+++ b/src/test/fuzz/miniscript.cpp
    26@@ -994,7 +994,7 @@ std::optional<Node> GenNode(MsCtx script_ctx, F ConsumeNode, Type root_type, boo
    27                 return {};
    28             }
    29             // Move it to the stack.
    30-            stack.emplace_back(std::move(*node));
    31+            stack.push_back(std::move(*node));
    32             todo.pop_back();
    33         }
    34     }
    

    hodlinator commented at 1:23 pm on June 24, 2025:
    Agree I went overboard in those 3 cases, :+1: reverted.
  46. in src/script/miniscript.h:1693 in 5e4573adda outdated
    1694     Node(const Node&) = delete;
    1695     Node& operator=(const Node&) = delete;
    1696+
    1697+    // subs is movable, circumventing recursion, so these are permitted.
    1698+    Node(Node&&) = default;
    1699+    Node& operator=(Node&&) = default;
    


    l0rinc commented at 12:53 pm on June 22, 2025:
    Are these implicitly already noexcept? In other such cases we’ve made them explicit.

    hodlinator commented at 12:35 pm on June 24, 2025:
    Probably not implicit, added for good measure.
  47. in src/script/miniscript.h:516 in c04b7b490e outdated
    502@@ -503,17 +503,17 @@ struct NoDupCheck {};
    503 template<typename Key>
    504 struct Node {
    505     //! What node type this node is.
    506-    const Fragment fragment;
    507+    Fragment fragment;
    


    l0rinc commented at 1:16 pm on June 22, 2025:

    I don’t mind removing the const from the privates in Node, but I’m not a fan of making the publics mutable… It seems to me we could make them private if we move FindChallenges over.

     0diff --git a/src/script/miniscript.h b/src/script/miniscript.h
     1index f99c9a8036..181a6614cf 100644
     2--- a/src/script/miniscript.h
     3+++ b/src/script/miniscript.h
     4@@ -495,19 +495,6 @@ struct NoDupCheck {};
     5 //! A node in a miniscript expression.
     6 template<typename Key>
     7 struct Node {
     8-    //! What node type this node is.
     9-    Fragment fragment;
    10-    //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
    11-    uint32_t k = 0;
    12-    //! The keys used by this expression (only for PK_K/PK_H/MULTI)
    13-    std::vector<Key> keys;
    14-    //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD160).
    15-    std::vector<unsigned char> data;
    16-    //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
    17-    std::vector<Node> subs;
    18-    //! The Script context for this node. Either P2WSH or Tapscript.
    19-    MiniscriptContext m_script_ctx;
    20-
    21     // Permit 1 level deep recursion since we own instances of our own type.
    22     // NOLINTBEGIN(misc-no-recursion)
    23     ~Node()
    24@@ -541,7 +528,26 @@ struct Node {
    25         return TreeEval<Node>(upfn);
    26     }
    27 
    28+    Fragment GetFragment() const noexcept { return fragment; }
    29+    uint32_t GetK() const noexcept { return k; }
    30+    std::span<const Key> GetKeys() const noexcept { return keys; }
    31+    std::span<const unsigned char> GetData() const noexcept { return data; }
    32+    std::span<const Node> GetSubs() const noexcept { return subs; }
    33+
    34 private:
    35+    //! What node type this node is.
    36+    Fragment fragment;
    37+    //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
    38+    uint32_t k = 0;
    39+    //! The keys used by this expression (only for PK_K/PK_H/MULTI)
    40+    std::vector<Key> keys;
    41+    //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD160).
    42+    std::vector<unsigned char> data;
    43+    //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
    44+    std::vector<Node> subs;
    45+    //! The Script context for this node. Either P2WSH or Tapscript.
    46+    MiniscriptContext m_script_ctx;
    47+
    48     //! Cached ops counts.
    49     internal::Ops ops;
    50     //! Cached stack size bounds.
    51diff --git a/src/test/miniscript_tests.cpp b/src/test/miniscript_tests.cpp
    52index cee88373c4..8a5a54b0bf 100644
    53--- a/src/test/miniscript_tests.cpp
    54+++ b/src/test/miniscript_tests.cpp
    55@@ -121,7 +121,7 @@ enum class ChallengeType {
    56  * For hashes it's just the first 4 bytes of the hash. For pubkeys, it's the last 4 bytes.
    57  */
    58 uint32_t ChallengeNumber(const CPubKey& pubkey) { return ReadLE32(pubkey.data() + 29); }
    59-uint32_t ChallengeNumber(const std::vector<unsigned char>& hash) { return ReadLE32(hash.data()); }
    60+uint32_t ChallengeNumber(std::span<const unsigned char> hash) { return ReadLE32(hash.data()); }
    61 
    62 //! A Challenge is a combination of type of leaf condition and its challenge number.
    63 typedef std::pair<ChallengeType, uint32_t> Challenge;
    64@@ -304,19 +304,19 @@ std::set<Challenge> FindChallenges(const Node& root)
    65         const auto* ref{stack.back()};
    66         stack.pop_back();
    67 
    68-        for (const auto& key : ref->keys) {
    69+        for (const auto& key : ref->GetKeys()) {
    70             chal.emplace(ChallengeType::PK, ChallengeNumber(key));
    71         }
    72-        switch (ref->fragment) {
    73-        case Fragment::OLDER: chal.emplace(ChallengeType::OLDER, ref->k); break;
    74-        case Fragment::AFTER: chal.emplace(ChallengeType::AFTER, ref->k); break;
    75-        case Fragment::SHA256: chal.emplace(ChallengeType::SHA256, ChallengeNumber(ref->data)); break;
    76-        case Fragment::RIPEMD160: chal.emplace(ChallengeType::RIPEMD160, ChallengeNumber(ref->data)); break;
    77-        case Fragment::HASH256: chal.emplace(ChallengeType::HASH256, ChallengeNumber(ref->data)); break;
    78-        case Fragment::HASH160: chal.emplace(ChallengeType::HASH160, ChallengeNumber(ref->data)); break;
    79+        switch (ref->GetFragment()) {
    80+        case Fragment::OLDER: chal.emplace(ChallengeType::OLDER, ref->GetK()); break;
    81+        case Fragment::AFTER: chal.emplace(ChallengeType::AFTER, ref->GetK()); break;
    82+        case Fragment::SHA256: chal.emplace(ChallengeType::SHA256, ChallengeNumber(ref->GetData())); break;
    83+        case Fragment::RIPEMD160: chal.emplace(ChallengeType::RIPEMD160, ChallengeNumber(ref->GetData())); break;
    84+        case Fragment::HASH256: chal.emplace(ChallengeType::HASH256, ChallengeNumber(ref->GetData())); break;
    85+        case Fragment::HASH160: chal.emplace(ChallengeType::HASH160, ChallengeNumber(ref->GetData())); break;
    86         default: break;
    87         }
    88-        for (const auto& sub : ref->subs) {
    89+        for (const auto& sub : ref->GetSubs()) {
    90             stack.push_back(&sub);
    91         }
    92     }
    

    hodlinator commented at 12:46 pm on June 24, 2025:
    Variant of this done as part of: a41db39bf87303d8a8173db56d0020c491239d38.
  48. in src/script/miniscript.h:582 in 5e4573adda outdated
    578     //! Cached script length (computed by CalcScriptLen).
    579-    const size_t scriptlen;
    580+    size_t scriptlen;
    581     //! Whether a public key appears more than once in this node. This value is initialized
    582     //! by all constructors except the NoDupCheck ones. The NoDupCheck ones skip the
    583     //! computation, requiring it to be done manually by invoking DuplicateKeyCheck().
    


    l0rinc commented at 1:25 pm on June 23, 2025:

    I wish we could remove the mutable from std::optional<bool> has_duplicate_keys as well since auto upfn = [&ctx](const Node& node promises more than it can deliver - but it seems we would need to touch a lot of declarations - I’ll let you decide if there’s anything to do here.

    If nothing else, we should at least cover it with tests: https://maflcko.github.io/b-c-cov/total.coverage/src/script/miniscript.h.gcov.html#L1464


    hodlinator commented at 12:40 pm on June 24, 2025:
    Good find, but would rather leave that for another PR. This one has ballooned enough IMO just from wanting to remove unique_ptr.
  49. in src/test/miniscript_tests.cpp:348 in 5e4573adda outdated
    344@@ -346,9 +345,10 @@ void SatisfactionToWitness(miniscript::MiniscriptContext ctx, CScriptWitness& wi
    345 
    346 struct MiniScriptTest : BasicTestingSetup {
    347 /** Run random satisfaction tests. */
    348-void TestSatisfy(const KeyConverter& converter, const std::string& testcase, const NodeRef& node) {
    349-    auto script = node->ToScript(converter);
    350-    const auto challenges{FindChallenges(node.get())}; // Find all challenges in the generated miniscript.
    351+void TestSatisfy(const KeyConverter& converter, const std::string& testcase, const Node& node)
    


    l0rinc commented at 1:53 pm on June 23, 2025:
    Is testcase here for debugging purposes only? Seems unused…

    hodlinator commented at 12:40 pm on June 24, 2025:
    It was added as a parameter when the function was introduced in 22c5b00345063bdeb8b6d3da8b5692d18f92bfb7 but I couldn’t find any commit where we started using it. Removed.
  50. in src/script/miniscript.h:347 in 5e4573adda outdated
    341@@ -349,8 +342,8 @@ struct InputResult {
    342 //! Class whose objects represent the maximum of a list of integers.
    343 template<typename I>
    344 struct MaxInt {
    345-    const bool valid;
    346-    const I value;
    347+    bool valid;
    348+    I value;
    


    l0rinc commented at 3:14 pm on June 23, 2025:
    can we make these private or friend now that they’re exposed?

    hodlinator commented at 12:47 pm on June 24, 2025:
    See response to #31713 (review).
  51. in src/script/miniscript.h:423 in 5e4573adda outdated
    413@@ -421,11 +414,11 @@ struct Ops {
    414  */
    415 struct SatInfo {
    416     //! Whether a canonical satisfaction/dissatisfaction is possible at all.
    417-    const bool valid;
    418+    bool valid;
    


    l0rinc commented at 3:14 pm on June 23, 2025:
    same

    hodlinator commented at 12:47 pm on June 24, 2025:
    See response to #31713 (review).
  52. in src/script/miniscript.h:2087 in 5e4573adda outdated
    2092+            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::OR_I, Vector(std::move(constructed.back()), Node<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0))};
    2093             break;
    2094         }
    2095         case ParseContext::WRAP_T: {
    2096-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1)));
    2097+            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::AND_V, Vector(std::move(constructed.back()), Node<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1))};
    


    l0rinc commented at 3:20 pm on June 23, 2025:
    👍 for using the alias - but as mentioned before, there are too many changes in this commit, could you do these in smaller, more focused commits instead?

    hodlinator commented at 1:11 pm on June 24, 2025:
    Broke out removal of NodeRef & MakeNodeRef() into its own commit: c4d30115f5cefe3945ac8b69c021a551eb2b6a72.
  53. in src/test/fuzz/miniscript.cpp:966 in 5e4573adda outdated
    968                 sub.push_back(std::move(*(stack.end() - info.subtypes.size() + i)));
    969             }
    970             stack.erase(stack.end() - info.subtypes.size(), stack.end());
    971-            // Construct new NodeRef.
    972-            NodeRef node;
    973+            // Construct new Node.
    


    l0rinc commented at 3:22 pm on June 23, 2025:
    comment is redundant

    hodlinator commented at 1:13 pm on June 24, 2025:
    The comments around this code seem to be introducing different phases of the code. I’d rather not rip one out and leave the other ones there, so not touching for now.

    l0rinc commented at 7:30 am on June 25, 2025:

    Hmm, this isn’t even an optional, since it always receives a value, right? We could use an IIFE instead:

    0Node node{[&] {
    1    if (info.keys.empty()) {
    2        return {miniscript::internal::NoDupCheck{}, script_ctx, info.fragment, std::move(sub), std::move(info.hash), info.k};
    3    }
    4    assert(sub.empty());
    5    assert(info.hash.empty());
    6    return {miniscript::internal::NoDupCheck{}, script_ctx, info.fragment, std::move(info.keys), info.k};
    7}()};
    
  54. in src/test/fuzz/miniscript.cpp:972 in 5e4573adda outdated
    972-            NodeRef node;
    973+            // Construct new Node.
    974+            std::optional<Node> node;
    975             if (info.keys.empty()) {
    976-                node = MakeNodeRef(script_ctx, info.fragment, std::move(sub), std::move(info.hash), info.k);
    977+                node = Node{miniscript::internal::NoDupCheck{}, script_ctx, info.fragment, std::move(sub), std::move(info.hash), info.k};
    


    l0rinc commented at 3:23 pm on June 23, 2025:
    I would inline this in a separate commit, it’s non-trivial

    hodlinator commented at 1:13 pm on June 24, 2025:
    Done, see reply to #31713 (review).
  55. l0rinc changes_requested
  56. l0rinc commented at 3:36 pm on June 23, 2025: contributor

    Concept ACK, makes sense to improve locality by removing needless indirection!

    My main concerns are:

    • the last commit contains too many changes of different types;
    • we may not have proper coverage for all corner cases (duplicate keys, case Fragment::WRAP_J, stack-safety for destructor and clone)
    • the introduced mutability lowers security
    • needless emplace_back changes
    • unused params (not introduced here, but may be a mistake anyway)
  57. hodlinator force-pushed on Jun 24, 2025
  58. hodlinator commented at 7:23 pm on June 24, 2025: contributor
    New push in response to all concerns from #31713#pullrequestreview-2948159254
  59. hodlinator force-pushed on Jun 24, 2025
  60. DrahtBot added the label CI failed on Jun 24, 2025
  61. DrahtBot commented at 8:14 pm on June 24, 2025: contributor

    🚧 At least one of the CI tasks failed. Task tidy: https://github.com/bitcoin/bitcoin/runs/44712881670 LLM reason (✨ experimental): Clang-tidy reported errors related to recursive function calls in vector.h, causing the CI failure.

    Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

    • Possibly 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.

    • A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

    • An intermittent issue.

    Leave a comment here, if you need help tracking down a confusing failure.

  62. hodlinator commented at 8:19 pm on June 24, 2025: contributor

    Pushed clang-tidy fix for https://cirrus-ci.com/task/6094677570486272?logs=ci#L2068:

    0[15:19:19.395] [ 29/669][11.0s] clang-tidy-20 -p=/ci_container_base/ci/scratch/build-x86_64-pc-linux-gnu -quiet -load=/tidy-build/libbitcoin-tidy.so /ci_container_base/src/test/fuzz/miniscript.cpp
    1[15:19:19.395] /ci_container_base/src/util/vector.h:23:49: error: function 'Vector<std::vector<miniscript::Node<(anonymous namespace)::ScriptParserContext::Key>>>' is within a recursive call chain [misc-no-recursion,-warnings-as-errors]
    2[15:19:19.395]    23 | inline std::vector<std::common_type_t<Args...>> Vector(Args&&... args)
    3[15:19:19.395]       |                                                 ^
    4[15:19:19.395] /ci_container_base/src/util/vector.h:23:49: error: function 'Vector<std::vector<miniscript::Node<CPubKey>>>' is within a recursive call chain [misc-no-recursion,-warnings-as-errors]
    5[15:19:19.395] 1059 warnings generated.
    

    Fix: https://github.com/bitcoin/bitcoin/compare/106d6937372ce62ccebf5d2c019381a337681826..00ce8ef316646221c7a2d21734694bf27cae71df

  63. DrahtBot removed the label CI failed on Jun 24, 2025
  64. in src/test/miniscript_tests.cpp:744 in f22f4f75e2 outdated
    739+    NodeU32 root{NoDupCheck{}, ctx, Fragment::JUST_1};
    740+    for (uint32_t i{0}; i < 1000'000; ++i) {
    741+        root = NodeU32{NoDupCheck{}, ctx, Fragment::WRAP_S, Vector(std::move(root))};
    742+    }
    743+
    744+    root.Clone();
    


    l0rinc commented at 7:09 am on June 25, 2025:
    +1 for the example in the commit message (if you touch again consider reducing the indentation) we could even lightly validate the clone here by comparing the two depths for good measure

    hodlinator commented at 12:51 pm on June 25, 2025:
    • Reduced indentation in commit message.
    • Added validation of the ScriptSize() to the test which is a value that depends on child nodes.
  65. in src/test/miniscript_tests.cpp:740 in f22f4f75e2 outdated
    735+    using NodeU32 = miniscript::Node<uint32_t>;
    736+
    737+    constexpr auto ctx{miniscript::MiniscriptContext::P2WSH};
    738+
    739+    NodeU32 root{NoDupCheck{}, ctx, Fragment::JUST_1};
    740+    for (uint32_t i{0}; i < 1000'000; ++i) {
    


    l0rinc commented at 7:10 am on June 25, 2025:
    0    for (uint32_t i{0}; i < 1'000'000; ++i) {
    

    (locally 100'000 is enough for me to reproduce the failure with incorrect destructor and clone - this test may be too heavy otherwise)


    hodlinator commented at 12:47 pm on June 25, 2025:
    100'000 isn’t sufficient for my configuration with an empty destructor. But 200'000 was for both, decreased.
  66. in src/test/fuzz/miniscript.cpp:1177 in f22f4f75e2 outdated
    1177+            return sats >= node.GetK();
    1178         }
    1179         case Fragment::OLDER:
    1180         case Fragment::AFTER:
    1181-            return node.k & 1;
    1182+            return node.GetK() & 1;
    


    l0rinc commented at 7:11 am on June 25, 2025:
    when do you use a Get prefix and when just a capitalized field name?
  67. in src/test/fuzz/miniscript.cpp:1170 in f22f4f75e2 outdated
    1168-            return is_key_satisfiable(node.keys[0]);
    1169+            return is_key_satisfiable(node.GetKeys()[0]);
    1170         case Fragment::MULTI:
    1171         case Fragment::MULTI_A: {
    1172-            size_t sats = std::count_if(node.keys.begin(), node.keys.end(), [&](const auto& key) {
    1173+            size_t sats = std::ranges::count_if(node.GetKeys(), [&](const auto& key) {
    


    l0rinc commented at 7:11 am on June 25, 2025:
    👍
  68. in src/script/miniscript.h:494 in f22f4f75e2 outdated
    491 
    492+public:
    493     constexpr StackSize(SatInfo in_sat, SatInfo in_dsat) noexcept : sat(in_sat), dsat(in_dsat) {};
    494     constexpr StackSize(SatInfo in_both) noexcept : sat(in_both), dsat(in_both) {};
    495+
    496+    const SatInfo& Sat() const { return sat; }
    


    l0rinc commented at 7:18 am on June 25, 2025:
    nit: unless there’s a good reason, I’d unify the Get/Is prefixes (I actually prefer without anything here) and consider noexcept for these as well

    hodlinator commented at 12:56 pm on June 25, 2025:

    Regarding naming of accessors: There is some precedent in Node::IsValid(). But I also prefer it without prefixes - updated.

    Regarding noexcept: The compiler should be able to infer noexcept by itself for simple accessors, so would rather avoid that noise.

  69. in src/script/miniscript.h:360 in a41db39bf8 outdated
    359 
    360+public:
    361     MaxInt() : valid(false), value(0) {}
    362     MaxInt(I val) : valid(true), value(val) {}
    363 
    364+    bool IsValid() const { return valid; }
    


    l0rinc commented at 7:21 am on June 25, 2025:
    nit: I’m repeating myself a bit, but not sure why some getters have prefixes
  70. in src/script/miniscript.h:567 in a41db39bf8 outdated
    561@@ -544,17 +562,23 @@ struct Node {
    562         return TreeEval<NodeRef<Key>>(upfn);
    563     }
    564 
    565+    Fragment GetFragment() const { return fragment; }
    566+    uint32_t GetK() const { return k; }
    567+    const std::vector<Key>& GetKeys() const { return keys; }
    


    l0rinc commented at 7:22 am on June 25, 2025:
    do we need to return vectors here? Seems overly specific, I think spans should also suffice here

    hodlinator commented at 12:55 pm on June 25, 2025:
    I prefer leaving up to the client of the interface to choose which type they want to switch to.
  71. in src/script/miniscript.h:192 in 1784cfaa13 outdated
    188@@ -189,11 +189,11 @@ inline consteval Type operator""_mst(const char* c, size_t l)
    189 using Opcode = std::pair<opcodetype, std::vector<unsigned char>>;
    190 
    191 template<typename Key> class Node;
    192-template<typename Key> using NodeRef = std::unique_ptr<Node<Key>>;
    193+template<typename Key> using NodeRef = Node<Key>; // <- removed in next commit
    


    l0rinc commented at 7:25 am on June 25, 2025:
    👍 - if you touch again, consider adding a TODO prefix to make sure we get a warning from the linters or the IDE if we accidentally leave them there

    hodlinator commented at 12:54 pm on June 25, 2025:
    Done.
  72. in src/test/fuzz/miniscript.cpp:847 in 1784cfaa13 outdated
    851@@ -851,12 +852,12 @@ std::optional<NodeInfo> ConsumeNodeSmart(MsCtx script_ctx, FuzzedDataProvider& p
    852  * Generate a Miniscript node based on the fuzzer's input.
    853  *
    854  * - ConsumeNode is a function object taking a Type, and returning an std::optional<NodeInfo>.
    855- * - root_type is the required type properties of the constructed NodeRef.
    856+ * - root_type is the required type properties of the constructed Node.
    857  * - strict_valid sets whether ConsumeNode is expected to guarantee a NodeInfo that results in
    858- *   a NodeRef whose Type() matches the type fed to ConsumeNode.
    859+ *   a Node whose Type() matches the type fed to ConsumeNode.
    


    l0rinc commented at 7:28 am on June 25, 2025:

    Nit: would this be more accurate?

    0 *   an std::optional<Node> whose Type() matches the type fed to ConsumeNode.
    

    hodlinator commented at 1:16 pm on June 25, 2025:
    Think it’s better as is, documenting the properties of the Node inside the optional.
  73. l0rinc approved
  74. l0rinc commented at 7:53 am on June 25, 2025: contributor

    Code review ACK f22f4f75e252e4f2171af34e4f92f3e6a396f227

    Someone else with more experience should also review it, I have only lightly tested it locally.

  75. DrahtBot requested review from sipa on Jun 25, 2025
  76. hodlinator force-pushed on Jun 25, 2025
  77. DrahtBot added the label CI failed on Jun 25, 2025
  78. DrahtBot commented at 2:28 pm on June 25, 2025: contributor

    🚧 At least one of the CI tasks failed. Task ARM, unit tests, no functional tests: https://github.com/bitcoin/bitcoin/runs/44768522506 LLM reason (✨ experimental): The CI failure is caused by a compilation error due to a change in the meaning of ‘Fragment’ caused by a conflicting declaration in miniscript.h.

    Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

    • Possibly 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.

    • A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

    • An intermittent issue.

    Leave a comment here, if you need help tracking down a confusing failure.

  79. hodlinator force-pushed on Jun 25, 2025
  80. DrahtBot removed the label CI failed on Jun 25, 2025
  81. l0rinc commented at 2:48 pm on June 27, 2025: contributor

    Code review re-ACK 9adf381d810f11b997ea036da6e2ce7dbad74cf6

    Someone else with more experience should also review it, I have only lightly tested it locally.

  82. DrahtBot added the label Needs rebase on Jul 2, 2025
  83. doc(miniscript): Remove mention of shared pointers
    Correct destructor implementation comment to no longer refer to shared pointers and also move it into the function body, in symmetry with Clone() right below.
    
    Leftover from #30866.
    b0dd90ab07
  84. refactor(miniscript): Make fields non-const & private
    Makes a lot of fields in miniscript.h non-const in order to allow move-operations in next commit.
    
    Also fixes adjacent comment typos.
    
    Co-authored-by: Lőrinc <pap.lorinc@gmail.com>
    Co-authored-by: MarcoFalke <*~=`'#}+{/-|&$^_@721217.xyz>
    c90e2017ed
  85. refactor(miniscript): Remove Node::subs mutability a336af3f38
  86. refactor(miniscript): Remove superfluous unique_ptr-indirection
    Functional parity is achieved through making Node move-able.
    
    Unfortunately ~Node() now needs to have the recursion linter disabled, as it is unable to figure out that recursion stops 1 level down. The former smart pointers must have been circumventing the linter somehow.
    
    NodeRef & MakeNodeRef() are deleted in the following commit (broken out to facilitate review).
    d85e120e66
  87. refactor(miniscript): Remove NodeRef & MakeNodeRef()
    (Also removes parameter to TestSatisfy() which existed unused from the start in 22c5b00345063bdeb8b6d3da8b5692d18f92bfb7).
    f897b2e53f
  88. refactor(miniscript): Destroy nodes one full subs-vector at a time 2c37c05ea4
  89. test(miniscript): Prove avoidance of stack overflow
    Can be tested through emptying the function body of ~Node() or replacing Clone() implementation with naive version:
    ```C++
    Node<Key> Clone() const
    {
        std::vector<Node> new_subs;
        new_subs.reserve(subs.size());
        for (const Node& child : subs) {
            new_subs.push_back(child.Clone());
        }
        return Node{internal::NoDupCheck{}, m_script_ctx, fragment, std::move(new_subs), keys, data, k};
    }
    ```
    
    Co-authored-by: Lőrinc <pap.lorinc@gmail.com>
    6bf4f4a878
  90. hodlinator force-pushed on Jul 2, 2025
  91. DrahtBot removed the label Needs rebase on Jul 2, 2025

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: 2025-07-11 03:13 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me