Function Parse

src/script/miniscript.h:1856–2213

 */
template <typename Key, typename Ctx>
inline std::optional<Node<Key>> Parse(std::span<const char> in, const Ctx& ctx)
{
    using namespace script;

    // Account for the minimum script size for all parsed fragments so far. It "borrows" 1
    // script byte from all leaf nodes, counting it instead whenever a space for a recursive
    // expression is added (through andor, and_*, or_*, thresh). This guarantees that all fragments
    // increment the script_size by at least one, except for:
    // - "0", "1": these leafs are only a single byte, so their subtracted-from increment is 0.
    //   This is not an issue however, as "space" for them has to be created by combinators,
    //   which do increment script_size.
    // - "v:": the v wrapper adds nothing as in some cases it results in no opcode being added
    //   (instead transforming another opcode into its VERIFY form). However, the v: wrapper has
    //   to be interleaved with other fragments to be valid, so this is not a concern.
    size_t script_size{1};
    size_t max_size{internal::MaxScriptSize(ctx.MsContext())};

    // The two integers are used to hold state for thresh()
    std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
    std::vector<Node<Key>> constructed;

    to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);

    // Parses a multi() or multi_a() from its string representation. Returns false on parsing error.
    const auto parse_multi_exp = [&](std::span<const char>& in, const bool is_multi_a) -> bool {
        const auto max_keys{is_multi_a ? MAX_PUBKEYS_PER_MULTI_A : MAX_PUBKEYS_PER_MULTISIG};
        const auto required_ctx{is_multi_a ? MiniscriptContext::TAPSCRIPT : MiniscriptContext::P2WSH};
        if (ctx.MsContext() != required_ctx) return false;
        // Get threshold
        int next_comma = FindNextChar(in, ',');
        if (next_comma < 1) return false;
        const auto k_to_integral{ToIntegral<int64_t>(std::string_view(in.data(), next_comma))};
        if (!k_to_integral.has_value()) return false;
        const int64_t k{k_to_integral.value()};
        in = in.subspan(next_comma + 1);
        // Get keys. It is compatible for both compressed and x-only keys.
        std::vector<Key> keys;
        while (next_comma != -1) {
            next_comma = FindNextChar(in, ',');
            int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
            if (key_length < 1) return false;
            std::span<const char> sp{in.begin(), in.begin() + key_length};
            auto key = ctx.FromString(sp);
            if (!key) return false;
            keys.push_back(std::move(*key));
            in = in.subspan(key_length + 1);
        }
        if (keys.size() < 1 || keys.size() > max_keys) return false;
        if (k < 1 || k > (int64_t)keys.size()) return false;
        if (is_multi_a) {
            // (push + xonly-key + CHECKSIG[ADD]) * n + k + OP_NUMEQUAL(VERIFY), minus one.
            script_size += (1 + 32 + 1) * keys.size() + BuildScript(k).size();
            constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), k);
        } else {
            script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
            constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), k);
        }
        return true;