Inside Bitcoin

3251    Next();
3252}
3253
3254void BlockBuilderImpl::Skip() noexcept
3255{
3256    // When skipping a chunk we need to not include anything more of the cluster, as that could make
3257    // the result topologically invalid. However, don't do this if the chunk is known to be the last
3258    // chunk of the cluster. This may significantly reduce the size of m_excluded_clusters,
3259    // especially when many singleton clusters are ignored.
3260    if (m_cur_cluster != nullptr && !m_known_end_of_cluster) {
3261        m_excluded_clusters.insert(m_cur_cluster->m_sequence);
3262    }
3263    Next();
3264}
3265
3266std::unique_ptr<TxGraph::BlockBuilder> TxGraphImpl::GetBlockBuilder() noexcept
3267{
3268    return std::make_unique<BlockBuilderImpl>(*this);
3269}
3270
3271std::pair<std::vector<TxGraph::Ref*>, FeePerWeight> TxGraphImpl::GetWorstMainChunk() noexcept
3272{
3273    std::pair<std::vector<Ref*>, FeePerWeight> ret;
3274    // Make sure all clusters in main are up to date, and acceptable.
3275    MakeAllAcceptable(0);
3276    Assume(m_main_clusterset.m_deps_to_add.empty());
3277    // If the graph is not empty, populate ret.
3278    if (!m_main_chunkindex.empty()) {
3279        const auto& chunk_data = *m_main_chunkindex.rbegin();
3280        const auto& chunk_end_entry = m_entries[chunk_data.m_graph_index];
3281        Cluster* cluster = chunk_end_entry.m_locator[0].cluster;
3282        if (chunk_data.m_chunk_count == LinearizationIndex(-1) || chunk_data.m_chunk_count == 1)  {
3283            // Special case for singletons.
3284            ret.first.resize(1);
3285            Assume(chunk_end_entry.m_ref != nullptr);
3286            ret.first[0] = chunk_end_entry.m_ref;
3287        } else {
3288            ret.first.resize(chunk_data.m_chunk_count);
3289            auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
3290            cluster->GetClusterRefs(*this, ret.first, start_pos);
3291            std::reverse(ret.first.begin(), ret.first.end());
3292        }
3293        ret.second = chunk_end_entry.m_main_chunk_feerate;
3294    }
3295    return ret;
3296}
3297
3298std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
3299{
3300    int level = GetTopLevel();
3301    Assume(m_main_chunkindex_observers == 0 || level != 0);
3302    std::vector<TxGraph::Ref*> ret;
3303
3304    // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
3305    auto& clusterset = GetClusterSet(level);
3306    if (clusterset.m_oversized == false) return ret;
3307    GroupClusters(level);
3308    Assume(clusterset.m_group_data.has_value());
3309    // Nothing to do if not oversized.
3310    Assume(clusterset.m_oversized.has_value());
3311    if (clusterset.m_oversized == false) return ret;
3312
3313    // In this function, would-be clusters (as precomputed in m_group_data by GroupClusters) are
3314    // trimmed by removing transactions in them such that the resulting clusters satisfy the size
3315    // and count limits.
3316    //
3317    // It works by defining for each would-be cluster a rudimentary linearization: at every point
3318    // the highest-chunk-feerate remaining transaction is picked among those with no unmet
3319    // dependencies. "Dependency" here means either a to-be-added dependency (m_deps_to_add), or
3320    // an implicit dependency added between any two consecutive transaction in their current
3321    // cluster linearization. So it can be seen as a "merge sort" of the chunks of the clusters,
3322    // but respecting the dependencies being added.
3323    //
3324    // This rudimentary linearization is computed lazily, by putting all eligible (no unmet
3325    // dependencies) transactions in a heap, and popping the highest-feerate one from it. Along the
3326    // way, the counts and sizes of the would-be clusters up to that point are tracked (by
3327    // partitioning the involved transactions using a union-find structure). Any transaction whose
3328    // addition would cause a violation is removed, along with all their descendants.
3329    //
3330    // A next invocation of GroupClusters (after applying the removals) will compute the new
3331    // resulting clusters, and none of them will violate the limits.
3332
3333    /** All dependencies (both to be added ones, and implicit ones between consecutive transactions
3334     *  in existing cluster linearizations), sorted by parent. */
3335    std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_parent;
3336    /** Same, but sorted by child. */
3337    std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_child;
3338    /** Information about all transactions involved in a Cluster group to be trimmed, sorted by
3339     *  GraphIndex. It contains entries both for transactions that have already been included,
3340     *  and ones that have not yet been. */
3341    std::vector<TrimTxData> trim_data;
3342    /** Iterators into trim_data, treated as a max heap according to cmp_fn below. Each entry is
3343     *  a transaction that has not yet been included yet, but all its ancestors have. */
3344    std::vector<std::vector<TrimTxData>::iterator> trim_heap;
3345    /** The list of representatives of the partitions a given transaction depends on. */
3346    std::vector<TrimTxData*> current_deps;
3347
3348    /** Function to define the ordering of trim_heap. */
3349    static constexpr auto cmp_fn = [](auto a, auto b) noexcept {
3350        // Sort by increasing chunk feerate, and then by decreasing size.
3351        // We do not need to sort by cluster or within clusters, because due to the implicit
3352        // dependency between consecutive linearization elements, no two transactions from the
3353        // same Cluster will ever simultaneously be in the heap.
3354        return ByRatioNegSize{a->m_chunk_feerate} < ByRatioNegSize{b->m_chunk_feerate};
3355    };
3356
3357    /** Given a TrimTxData entry, find the representative of the partition it is in. */
3358    static constexpr auto find_fn = [](TrimTxData* arg) noexcept {
3359        while (arg != arg->m_uf_parent) {
3360            // Replace pointer to parent with pointer to grandparent (path splitting).
3361            // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
3362            auto par = arg->m_uf_parent;
3363            arg->m_uf_parent = par->m_uf_parent;
3364            arg = par;
3365        }
3366        return arg;
3367    };
3368
3369    /** Given two TrimTxData entries, union the partitions they are in, and return the
3370     *  representative. */
3371    static constexpr auto union_fn = [](TrimTxData* arg1, TrimTxData* arg2) noexcept {
3372        // Replace arg1 and arg2 by their representatives.
3373        auto rep1 = find_fn(arg1);
3374        auto rep2 = find_fn(arg2);
3375        // Bail out if both representatives are the same, because that means arg1 and arg2 are in
3376        // the same partition already.
3377        if (rep1 == rep2) return rep1;
3378        // Pick the lower-count root to become a child of the higher-count one.
3379        // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_size.
3380        if (rep1->m_uf_count < rep2->m_uf_count) std::swap(rep1, rep2);
3381        rep2->m_uf_parent = rep1;
3382        // Add the statistics of arg2 (which is no longer a representative) to those of arg1 (which
3383        // is now the representative for both).
3384        rep1->m_uf_size += rep2->m_uf_size;
3385        rep1->m_uf_count += rep2->m_uf_count;
3386        return rep1;
3387    };
3388
3389    /** Get iterator to TrimTxData entry for a given index. */
3390    auto locate_fn = [&](GraphIndex index) noexcept {
3391        auto it = std::lower_bound(trim_data.begin(), trim_data.end(), index, [](TrimTxData& elem, GraphIndex idx) noexcept {
3392            return elem.m_index < idx;
3393        });
3394        Assume(it != trim_data.end() && it->m_index == index);
3395        return it;
3396    };
3397
3398    // For each group of to-be-merged Clusters.
3399    for (const auto& group_data : clusterset.m_group_data->m_groups) {
3400        trim_data.clear();
3401        trim_heap.clear();
3402        deps_by_child.clear();
3403        deps_by_parent.clear();
3404
3405        // Gather trim data and implicit dependency data from all involved Clusters.
3406        auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
3407                                .subspan(group_data.m_cluster_offset, group_data.m_cluster_count);
3408        uint64_t size{0};
3409        for (Cluster* cluster : cluster_span) {
3410            MakeAcceptable(*cluster, cluster->GetLevel(*this));
3411            size += cluster->AppendTrimData(trim_data, deps_by_child);
3412        }
3413        // If this group of Clusters does not violate any limits, continue to the next group.
3414        if (trim_data.size() <= m_max_cluster_count && size <= m_max_cluster_size) continue;
3415        // Sort the trim data by GraphIndex. In what follows, we will treat this sorted vector as
3416        // a map from GraphIndex to TrimTxData via locate_fn, and its ordering will not change
3417        // anymore.
3418        std::ranges::sort(trim_data, [](auto& a, auto& b) noexcept { return a.m_index < b.m_index; });
3419
3420        // Add the explicitly added dependencies to deps_by_child.
3421        deps_by_child.insert(deps_by_child.end(),
3422                             clusterset.m_deps_to_add.begin() + group_data.m_deps_offset,
3423                             clusterset.m_deps_to_add.begin() + group_data.m_deps_offset + group_data.m_deps_count);
3424
3425        // Sort deps_by_child by child transaction GraphIndex. The order will not be changed
3426        // anymore after this.
3427        std::ranges::sort(deps_by_child, [](auto& a, auto& b) noexcept { return a.second < b.second; });
3428        // Fill m_parents_count and m_parents_offset in trim_data, as well as m_deps_left, and
3429        // initially populate trim_heap. Because of the sort above, all dependencies involving the
3430        // same child are grouped together, so a single linear scan suffices.
3431        auto deps_it = deps_by_child.begin();
3432        for (auto trim_it = trim_data.begin(); trim_it != trim_data.end(); ++trim_it) {
3433            trim_it->m_parent_offset = deps_it - deps_by_child.begin();
3434            trim_it->m_deps_left = 0;
3435            while (deps_it != deps_by_child.end() && deps_it->second == trim_it->m_index) {
3436                ++trim_it->m_deps_left;
3437                ++deps_it;
3438            }
3439            trim_it->m_parent_count = trim_it->m_deps_left;
3440            // If this transaction has no unmet dependencies, and is not oversized, add it to the
3441            // heap (just append for now, the heapification happens below).
3442            if (trim_it->m_deps_left == 0 && trim_it->m_tx_size <= m_max_cluster_size) {
3443                trim_heap.push_back(trim_it);
3444            }
3445        }
3446        Assume(deps_it == deps_by_child.end());
3447
3448        // Construct deps_by_parent, sorted by parent transaction GraphIndex. The order will not be
3449        // changed anymore after this.
3450        deps_by_parent = deps_by_child;
3451        std::ranges::sort(deps_by_parent, [](auto& a, auto& b) noexcept { return a.first < b.first; });
3452        // Fill m_children_offset and m_children_count in trim_data. Because of the sort above, all
3453        // dependencies involving the same parent are grouped together, so a single linear scan
3454        // suffices.
3455        deps_it = deps_by_parent.begin();
3456        for (auto& trim_entry : trim_data) {
3457            trim_entry.m_children_count = 0;
3458            trim_entry.m_children_offset = deps_it - deps_by_parent.begin();
3459            while (deps_it != deps_by_parent.end() && deps_it->first == trim_entry.m_index) {
3460                ++trim_entry.m_children_count;
3461                ++deps_it;
3462            }
3463        }
3464        Assume(deps_it == deps_by_parent.end());
3465
3466        // Build a heap of all transactions with 0 unmet dependencies.
3467        std::make_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3468
3469        // Iterate over to-be-included transactions, and convert them to included transactions, or
3470        // skip them if adding them would violate resource limits of the would-be cluster.
3471        //
3472        // It is possible that the heap empties without ever hitting either cluster limit, in case
3473        // the implied graph (to be added dependencies plus implicit dependency between each
3474        // original transaction and its predecessor in the linearization it came from) contains
3475        // cycles. Such cycles will be removed entirely, because each of the transactions in the
3476        // cycle permanently have unmet dependencies. However, this cannot occur in real scenarios
3477        // where Trim() is called to deal with reorganizations that would violate cluster limits,
3478        // as all added dependencies are in the same direction (from old mempool transactions to
3479        // new from-block transactions); cycles require dependencies in both directions to be
3480        // added.
3481        while (!trim_heap.empty()) {
3482            // Move the best remaining transaction to the end of trim_heap.
3483            std::pop_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
3484            // Pop it, and find its TrimTxData.
3485            auto& entry = *trim_heap.back();
3486            trim_heap.pop_back();
3487
3488            // Initialize it as a singleton partition.
3489            entry.m_uf_parent = &entry;
3490            entry.m_uf_count = 1;
3491            entry.m_uf_size = entry.m_tx_size;
3492
3493            // Find the distinct transaction partitions this entry depends on.
3494            current_deps.clear();
3495            for (auto& [par, chl] : std::span{deps_by_child}.subspan(entry.m_parent_offset, entry.m_parent_count)) {
3496                Assume(chl == entry.m_index);
3497                current_deps.push_back(find_fn(&*locate_fn(par)));
3498            }
3499            std::ranges::sort(current_deps);
3500            current_deps.erase(std::ranges::unique(current_deps).begin(), current_deps.end());