miniscript: add a helper to find the first insane sub with no child

This is helpful for finer grained descriptor parsing error: when there
are multiple errors to report in a Miniscript descriptor start with the
"smallest" fragments: the ones closer to be a leaf.

Co-Authored-By: Pieter Wuille <pieter@wuille.net>

1 files changed, 24 insertions, 0 deletions

diff --git a/src/script/miniscript.h b/src/script/miniscript.h
index 0137293180..f783d1dafc 100644
--- a/src/script/miniscript.h
+++ b/src/script/miniscript.h
@@ -429,6 +429,21 @@ private:
         ));
     }
 
+    /** Like TreeEval, but without downfn or State type.
+     *  upfn takes (const Node&, Span<Result>) and returns Result. */
+    template<typename Result, typename UpFn>
+    Result TreeEval(UpFn upfn) const
+    {
+        struct DummyState {};
+        return std::move(*TreeEvalMaybe<Result>(DummyState{},
+            [](DummyState, const Node&, size_t) { return DummyState{}; },
+            [&upfn](DummyState, const Node& node, Span<Result> subs) {
+                Result res{upfn(node, subs)};
+                return std::optional<Result>(std::move(res));
+            }
+        ));
+    }
+
     /** Compare two miniscript subtrees, using a non-recursive algorithm. */
     friend int Compare(const Node<Key>& node1, const Node<Key>& node2)
     {
@@ -818,6 +833,15 @@ public:
     //! Return the expression type.
     Type GetType() const { return typ; }
 
+    //! Find an insane subnode which has no insane children. Nullptr if there is none.
+    const Node* FindInsaneSub() const {
+        return TreeEval<const Node*>([](const Node& node, Span<const Node*> subs) -> const Node* {
+            for (auto& sub: subs) if (sub) return sub;
+            if (!node.IsSaneSubexpression()) return &node;
+            return nullptr;
+        });
+    }
+
     //! Check whether this node is valid at all.
     bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }