cluster_linearize.h

Go to the documentation of this file.

// Copyright (c) The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
#ifndef BITCOIN_CLUSTER_LINEARIZE_H
#define BITCOIN_CLUSTER_LINEARIZE_H
 
#include <algorithm>
#include <cstdint>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
 
#include <attributes.h>
#include <memusage.h>
#include <random.h>
#include <span.h>
#include <util/feefrac.h>
#include <util/vecdeque.h>
 
namespace cluster_linearize {
 
using DepGraphIndex = uint32_t;
 
template<typename SetType>
class DepGraph
{
    struct Entry
    {
        FeeFrac feerate;
        SetType ancestors;
        SetType descendants;
 
        friend bool operator==(const Entry&, const Entry&) noexcept = default;
 
        Entry() noexcept = default;
        Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
    };
 
    std::vector<Entry> entries;
 
    SetType m_used;
 
public:
    friend bool operator==(const DepGraph& a, const DepGraph& b) noexcept
    {
        if (a.m_used != b.m_used) return false;
        // Only compare the used positions within the entries vector.
        for (auto idx : a.m_used) {
            if (a.entries[idx] != b.entries[idx]) return false;
        }
        return true;
    }
 
    // Default constructors.
    DepGraph() noexcept = default;
    DepGraph(const DepGraph&) noexcept = default;
    DepGraph(DepGraph&&) noexcept = default;
    DepGraph& operator=(const DepGraph&) noexcept = default;
    DepGraph& operator=(DepGraph&&) noexcept = default;
 
    DepGraph(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> mapping, DepGraphIndex pos_range) noexcept : entries(pos_range)
    {
        Assume(mapping.size() == depgraph.PositionRange());
        Assume((pos_range == 0) == (depgraph.TxCount() == 0));
        for (DepGraphIndex i : depgraph.Positions()) {
            auto new_idx = mapping[i];
            Assume(new_idx < pos_range);
            // Add transaction.
            entries[new_idx].ancestors = SetType::Singleton(new_idx);
            entries[new_idx].descendants = SetType::Singleton(new_idx);
            m_used.Set(new_idx);
            // Fill in fee and size.
            entries[new_idx].feerate = depgraph.entries[i].feerate;
        }
        for (DepGraphIndex i : depgraph.Positions()) {
            // Fill in dependencies by mapping direct parents.
            SetType parents;
            for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
            AddDependencies(parents, mapping[i]);
        }
        // Verify that the provided pos_range was correct (no unused positions at the end).
        Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
    }
 
    const SetType& Positions() const noexcept { return m_used; }
    DepGraphIndex PositionRange() const noexcept { return entries.size(); }
    auto TxCount() const noexcept { return m_used.Count(); }
    const FeeFrac& FeeRate(DepGraphIndex i) const noexcept { return entries[i].feerate; }
    FeeFrac& FeeRate(DepGraphIndex i) noexcept { return entries[i].feerate; }
    const SetType& Ancestors(DepGraphIndex i) const noexcept { return entries[i].ancestors; }
    const SetType& Descendants(DepGraphIndex i) const noexcept { return entries[i].descendants; }
 
    DepGraphIndex AddTransaction(const FeeFrac& feefrac) noexcept
    {
        static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
        auto available = ALL_POSITIONS - m_used;
        Assume(available.Any());
        DepGraphIndex new_idx = available.First();
        if (new_idx == entries.size()) {
            entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
        } else {
            entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
        }
        m_used.Set(new_idx);
        return new_idx;
    }
 
    void RemoveTransactions(const SetType& del) noexcept
    {
        m_used -= del;
        // Remove now-unused trailing entries.
        while (!entries.empty() && !m_used[entries.size() - 1]) {
            entries.pop_back();
        }
        // Remove the deleted transactions from ancestors/descendants of other transactions. Note
        // that the deleted positions will retain old feerate and dependency information. This does
        // not matter as they will be overwritten by AddTransaction if they get used again.
        for (auto& entry : entries) {
            entry.ancestors &= m_used;
            entry.descendants &= m_used;
        }
    }
 
    void AddDependencies(const SetType& parents, DepGraphIndex child) noexcept
    {
        Assume(m_used[child]);
        Assume(parents.IsSubsetOf(m_used));
        // Compute the ancestors of parents that are not already ancestors of child.
        SetType par_anc;
        for (auto par : parents - Ancestors(child)) {
            par_anc |= Ancestors(par);
        }
        par_anc -= Ancestors(child);
        // Bail out if there are no such ancestors.
        if (par_anc.None()) return;
        // To each such ancestor, add as descendants the descendants of the child.
        const auto& chl_des = entries[child].descendants;
        for (auto anc_of_par : par_anc) {
            entries[anc_of_par].descendants |= chl_des;
        }
        // To each descendant of the child, add those ancestors.
        for (auto dec_of_chl : Descendants(child)) {
            entries[dec_of_chl].ancestors |= par_anc;
        }
    }
 
    SetType GetReducedParents(DepGraphIndex i) const noexcept
    {
        SetType parents = Ancestors(i);
        parents.Reset(i);
        for (auto parent : parents) {
            if (parents[parent]) {
                parents -= Ancestors(parent);
                parents.Set(parent);
            }
        }
        return parents;
    }
 
    SetType GetReducedChildren(DepGraphIndex i) const noexcept
    {
        SetType children = Descendants(i);
        children.Reset(i);
        for (auto child : children) {
            if (children[child]) {
                children -= Descendants(child);
                children.Set(child);
            }
        }
        return children;
    }
 
    FeeFrac FeeRate(const SetType& elems) const noexcept
    {
        FeeFrac ret;
        for (auto pos : elems) ret += entries[pos].feerate;
        return ret;
    }
 
    SetType GetConnectedComponent(const SetType& todo, DepGraphIndex tx) const noexcept
    {
        Assume(todo[tx]);
        Assume(todo.IsSubsetOf(m_used));
        auto to_add = SetType::Singleton(tx);
        SetType ret;
        do {
            SetType old = ret;
            for (auto add : to_add) {
                ret |= Descendants(add);
                ret |= Ancestors(add);
            }
            ret &= todo;
            to_add = ret - old;
        } while (to_add.Any());
        return ret;
    }
 
    SetType FindConnectedComponent(const SetType& todo) const noexcept
    {
        if (todo.None()) return todo;
        return GetConnectedComponent(todo, todo.First());
    }
 
    bool IsConnected(const SetType& subset) const noexcept
    {
        return FindConnectedComponent(subset) == subset;
    }
 
    bool IsConnected() const noexcept { return IsConnected(m_used); }
 
    void AppendTopo(std::vector<DepGraphIndex>& list, const SetType& select) const noexcept
    {
        DepGraphIndex old_len = list.size();
        for (auto i : select) list.push_back(i);
        std::sort(list.begin() + old_len, list.end(), [&](DepGraphIndex a, DepGraphIndex b) noexcept {
            const auto a_anc_count = entries[a].ancestors.Count();
            const auto b_anc_count = entries[b].ancestors.Count();
            if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
            return a < b;
        });
    }
 
    bool IsAcyclic() const noexcept
    {
        for (auto i : Positions()) {
            if ((Ancestors(i) & Descendants(i)) != SetType::Singleton(i)) {
                return false;
            }
        }
        return true;
    }
 
    unsigned CountDependencies() const noexcept
    {
        unsigned ret = 0;
        for (auto i : Positions()) {
            ret += GetReducedParents(i).Count();
        }
        return ret;
    }
 
    void Compact() noexcept
    {
        entries.shrink_to_fit();
    }
 
    size_t DynamicMemoryUsage() const noexcept
    {
        return memusage::DynamicUsage(entries);
    }
};
 
template<typename SetType>
struct SetInfo
{
    SetType transactions;
    FeeFrac feerate;
 
    SetInfo() noexcept = default;
 
    SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
 
    explicit SetInfo(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept :
        transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
 
    explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept :
        transactions(txn), feerate(depgraph.FeeRate(txn)) {}
 
    void Set(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept
    {
        Assume(!transactions[pos]);
        transactions.Set(pos);
        feerate += depgraph.FeeRate(pos);
    }
 
    SetInfo& operator|=(const SetInfo& other) noexcept
    {
        Assume(!transactions.Overlaps(other.transactions));
        transactions |= other.transactions;
        feerate += other.feerate;
        return *this;
    }
 
    SetInfo& operator-=(const SetInfo& other) noexcept
    {
        Assume(other.transactions.IsSubsetOf(transactions));
        transactions -= other.transactions;
        feerate -= other.feerate;
        return *this;
    }
 
    SetInfo operator-(const SetInfo& other) const noexcept
    {
        Assume(other.transactions.IsSubsetOf(transactions));
        return {transactions - other.transactions, feerate - other.feerate};
    }
 
    friend void swap(SetInfo& a, SetInfo& b) noexcept
    {
        swap(a.transactions, b.transactions);
        swap(a.feerate, b.feerate);
    }
 
    friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default;
};
 
template<typename SetType>
std::vector<SetInfo<SetType>> ChunkLinearizationInfo(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
{
    std::vector<SetInfo<SetType>> ret;
    for (DepGraphIndex i : linearization) {
        SetInfo<SetType> new_chunk(depgraph, i);
        // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
        while (!ret.empty() && new_chunk.feerate >> ret.back().feerate) {
            new_chunk |= ret.back();
            ret.pop_back();
        }
        // Actually move that new chunk into the chunking.
        ret.emplace_back(std::move(new_chunk));
    }
    return ret;
}
 
template<typename SetType>
std::vector<FeeFrac> ChunkLinearization(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
{
    std::vector<FeeFrac> ret;
    for (DepGraphIndex i : linearization) {
        auto new_chunk = depgraph.FeeRate(i);
        // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
        while (!ret.empty() && new_chunk >> ret.back()) {
            new_chunk += ret.back();
            ret.pop_back();
        }
        // Actually move that new chunk into the chunking.
        ret.push_back(std::move(new_chunk));
    }
    return ret;
}
 
template<typename F, typename Arg>
concept StrongComparator =
    std::regular_invocable<F, Arg, Arg> &&
    std::is_same_v<std::invoke_result_t<F, Arg, Arg>, std::strong_ordering>;
 
using IndexTxOrder = std::compare_three_way;
 
class SFLDefaultCostModel
{
    uint64_t m_cost{0};
 
public:
    inline void InitializeBegin() noexcept {}
    inline void InitializeEnd(int num_txns, int num_deps) noexcept
    {
         // Cost of initialization.
         m_cost += 39 * num_txns;
         // Cost of producing linearization at the end.
         m_cost += 48 * num_txns + 4 * num_deps;
    }
    inline void GetLinearizationBegin() noexcept {}
    inline void GetLinearizationEnd(int num_txns, int num_deps) noexcept
    {
        // Note that we account for the cost of the final linearization at the beginning (see
        // InitializeEnd), because the cost budget decision needs to be made before calling
        // GetLinearization.
        // This function exists here to allow overriding it easily for benchmark purposes.
    }
    inline void MakeTopologicalBegin() noexcept {}
    inline void MakeTopologicalEnd(int num_chunks, int num_steps) noexcept
    {
        m_cost += 20 * num_chunks + 28 * num_steps;
    }
    inline void StartOptimizingBegin() noexcept {}
    inline void StartOptimizingEnd(int num_chunks) noexcept { m_cost += 13 * num_chunks; }
    inline void ActivateBegin() noexcept {}
    inline void ActivateEnd(int num_deps) noexcept { m_cost += 10 * num_deps + 1; }
    inline void DeactivateBegin() noexcept {}
    inline void DeactivateEnd(int num_deps) noexcept { m_cost += 11 * num_deps + 8; }
    inline void MergeChunksBegin() noexcept {}
    inline void MergeChunksMid(int num_txns) noexcept { m_cost += 2 * num_txns; }
    inline void MergeChunksEnd(int num_steps) noexcept { m_cost += 3 * num_steps + 5; }
    inline void PickMergeCandidateBegin() noexcept {}
    inline void PickMergeCandidateEnd(int num_steps) noexcept { m_cost += 8 * num_steps; }
    inline void PickChunkToOptimizeBegin() noexcept {}
    inline void PickChunkToOptimizeEnd(int num_steps) noexcept { m_cost += num_steps + 4; }
    inline void PickDependencyToSplitBegin() noexcept {}
    inline void PickDependencyToSplitEnd(int num_txns) noexcept { m_cost += 8 * num_txns + 9; }
    inline void StartMinimizingBegin() noexcept {}
    inline void StartMinimizingEnd(int num_chunks) noexcept { m_cost += 18 * num_chunks; }
    inline void MinimizeStepBegin() noexcept {}
    inline void MinimizeStepMid(int num_txns) noexcept { m_cost += 11 * num_txns + 11; }
    inline void MinimizeStepEnd(bool split) noexcept { m_cost += 17 * split + 7; }
 
    inline uint64_t GetCost() const noexcept { return m_cost; }
};
 
template<typename SetType, typename CostModel = SFLDefaultCostModel>
class SpanningForestState
{
private:
    InsecureRandomContext m_rng;
 
    using TxIdx = DepGraphIndex;
    using SetIdx = std::conditional_t<(SetType::Size() <= 0xff),
                                      uint8_t,
                                      std::conditional_t<(SetType::Size() <= 0xffff),
                                                         uint16_t,
                                                         uint32_t>>;
    static constexpr SetIdx INVALID_SET_IDX = SetIdx(-1);
 
    struct TxData {
        std::array<SetIdx, SetType::Size()> dep_top_idx;
        SetType parents;
        SetType children;
        SetType active_children;
        SetIdx chunk_idx;
    };
 
    SetType m_transaction_idxs;
    SetType m_chunk_idxs;
    SetType m_suboptimal_idxs;
    std::vector<TxData> m_tx_data;
    std::vector<SetInfo<SetType>> m_set_info;
    std::vector<std::pair<SetType, SetType>> m_reachable;
    VecDeque<SetIdx> m_suboptimal_chunks;
    VecDeque<std::tuple<SetIdx, TxIdx, unsigned>> m_nonminimal_chunks;
 
    const DepGraph<SetType>& m_depgraph;
 
    CostModel m_cost;
 
    TxIdx PickRandomTx(const SetType& tx_idxs) noexcept
    {
        Assume(tx_idxs.Any());
        unsigned pos = m_rng.randrange<unsigned>(tx_idxs.Count());
        for (auto tx_idx : tx_idxs) {
            if (pos == 0) return tx_idx;
            --pos;
        }
        Assume(false);
        return TxIdx(-1);
    }
 
    std::pair<SetType, SetType> GetReachable(const SetType& tx_idxs) const noexcept
    {
        SetType parents, children;
        for (auto tx_idx : tx_idxs) {
            const auto& tx_data = m_tx_data[tx_idx];
            parents |= tx_data.parents;
            children |= tx_data.children;
        }
        return {parents - tx_idxs, children - tx_idxs};
    }
 
    SetIdx Activate(TxIdx parent_idx, TxIdx child_idx) noexcept
    {
        m_cost.ActivateBegin();
        // Gather and check information about the parent and child transactions.
        auto& parent_data = m_tx_data[parent_idx];
        auto& child_data = m_tx_data[child_idx];
        Assume(parent_data.children[child_idx]);
        Assume(!parent_data.active_children[child_idx]);
        // Get the set index of the chunks the parent and child are currently in. The parent chunk
        // will become the top set of the newly activated dependency, while the child chunk will be
        // grown to become the merged chunk.
        auto parent_chunk_idx = parent_data.chunk_idx;
        auto child_chunk_idx = child_data.chunk_idx;
        Assume(parent_chunk_idx != child_chunk_idx);
        Assume(m_chunk_idxs[parent_chunk_idx]);
        Assume(m_chunk_idxs[child_chunk_idx]);
        auto& top_info = m_set_info[parent_chunk_idx];
        auto& bottom_info = m_set_info[child_chunk_idx];
 
        // Consider the following example:
        //
        //    A           A     There are two chunks, ABC and DEF, and the inactive E->C dependency
        //   / \         / \    is activated, resulting in a single chunk ABCDEF.
        //  B   C       B   C
        //      :  ==>      |   Dependency | top set before | top set after | change
        //  D   E       D   E   B->A       | AC             | ACDEF         | +DEF
        //   \ /         \ /    C->A       | AB             | AB            |
        //    F           F     F->D       | D              | D             |
        //                      F->E       | E              | ABCE          | +ABC
        //
        // The common pattern here is that any dependency which has the parent or child of the
        // dependency being activated (E->C here) in its top set, will have the opposite part added
        // to it. This is true for B->A and F->E, but not for C->A and F->D.
        //
        // Traverse the old parent chunk top_info (ABC in example), and add bottom_info (DEF) to
        // every dependency's top set which has the parent (C) in it. At the same time, change the
        // chunk_idx for each to be child_chunk_idx, which becomes the set for the merged chunk.
        for (auto tx_idx : top_info.transactions) {
            auto& tx_data = m_tx_data[tx_idx];
            tx_data.chunk_idx = child_chunk_idx;
            for (auto dep_child_idx : tx_data.active_children) {
                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
                if (dep_top_info.transactions[parent_idx]) dep_top_info |= bottom_info;
            }
        }
        // Traverse the old child chunk bottom_info (DEF in example), and add top_info (ABC) to
        // every dependency's top set which has the child (E) in it.
        for (auto tx_idx : bottom_info.transactions) {
            auto& tx_data = m_tx_data[tx_idx];
            for (auto dep_child_idx : tx_data.active_children) {
                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
                if (dep_top_info.transactions[child_idx]) dep_top_info |= top_info;
            }
        }
        // Merge top_info into bottom_info, which becomes the merged chunk.
        bottom_info |= top_info;
        // Compute merged sets of reachable transactions from the new chunk, based on the input
        // chunks' reachable sets.
        m_reachable[child_chunk_idx].first |= m_reachable[parent_chunk_idx].first;
        m_reachable[child_chunk_idx].second |= m_reachable[parent_chunk_idx].second;
        m_reachable[child_chunk_idx].first -= bottom_info.transactions;
        m_reachable[child_chunk_idx].second -= bottom_info.transactions;
        // Make parent chunk the set for the new active dependency.
        parent_data.dep_top_idx[child_idx] = parent_chunk_idx;
        parent_data.active_children.Set(child_idx);
        m_chunk_idxs.Reset(parent_chunk_idx);
        // Return the newly merged chunk.
        m_cost.ActivateEnd(/*num_deps=*/bottom_info.transactions.Count() - 1);
        return child_chunk_idx;
    }
 
    std::pair<SetIdx, SetIdx> Deactivate(TxIdx parent_idx, TxIdx child_idx) noexcept
    {
        m_cost.DeactivateBegin();
        // Gather and check information about the parent transactions.
        auto& parent_data = m_tx_data[parent_idx];
        Assume(parent_data.children[child_idx]);
        Assume(parent_data.active_children[child_idx]);
        // Get the top set of the active dependency (which will become the parent chunk) and the
        // chunk set the transactions are currently in (which will become the bottom chunk).
        auto parent_chunk_idx = parent_data.dep_top_idx[child_idx];
        auto child_chunk_idx = parent_data.chunk_idx;
        Assume(parent_chunk_idx != child_chunk_idx);
        Assume(m_chunk_idxs[child_chunk_idx]);
        Assume(!m_chunk_idxs[parent_chunk_idx]); // top set, not a chunk
        auto& top_info = m_set_info[parent_chunk_idx];
        auto& bottom_info = m_set_info[child_chunk_idx];
 
        // Remove the active dependency.
        parent_data.active_children.Reset(child_idx);
        m_chunk_idxs.Set(parent_chunk_idx);
        auto ntx = bottom_info.transactions.Count();
        // Subtract the top_info from the bottom_info, as it will become the child chunk.
        bottom_info -= top_info;
        // See the comment above in Activate(). We perform the opposite operations here, removing
        // instead of adding. Simultaneously, aggregate the top/bottom's union of parents/children.
        SetType top_parents, top_children;
        for (auto tx_idx : top_info.transactions) {
            auto& tx_data = m_tx_data[tx_idx];
            tx_data.chunk_idx = parent_chunk_idx;
            top_parents |= tx_data.parents;
            top_children |= tx_data.children;
            for (auto dep_child_idx : tx_data.active_children) {
                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
                if (dep_top_info.transactions[parent_idx]) dep_top_info -= bottom_info;
            }
        }
        SetType bottom_parents, bottom_children;
        for (auto tx_idx : bottom_info.transactions) {
            auto& tx_data = m_tx_data[tx_idx];
            bottom_parents |= tx_data.parents;
            bottom_children |= tx_data.children;
            for (auto dep_child_idx : tx_data.active_children) {
                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
                if (dep_top_info.transactions[child_idx]) dep_top_info -= top_info;
            }
        }
        // Compute the new sets of reachable transactions for each new chunk, based on the
        // top/bottom parents and children computed above.
        m_reachable[parent_chunk_idx].first = top_parents - top_info.transactions;
        m_reachable[parent_chunk_idx].second = top_children - top_info.transactions;
        m_reachable[child_chunk_idx].first = bottom_parents - bottom_info.transactions;
        m_reachable[child_chunk_idx].second = bottom_children - bottom_info.transactions;
        // Return the two new set idxs.
        m_cost.DeactivateEnd(/*num_deps=*/ntx - 1);
        return {parent_chunk_idx, child_chunk_idx};
    }
 
    SetIdx MergeChunks(SetIdx top_idx, SetIdx bottom_idx) noexcept
    {
        m_cost.MergeChunksBegin();
        Assume(m_chunk_idxs[top_idx]);
        Assume(m_chunk_idxs[bottom_idx]);
        auto& top_chunk_info = m_set_info[top_idx];
        auto& bottom_chunk_info = m_set_info[bottom_idx];
        // Count the number of dependencies between bottom_chunk and top_chunk.
        unsigned num_deps{0};
        for (auto tx_idx : top_chunk_info.transactions) {
            auto& tx_data = m_tx_data[tx_idx];
            num_deps += (tx_data.children & bottom_chunk_info.transactions).Count();
        }
        m_cost.MergeChunksMid(/*num_txns=*/top_chunk_info.transactions.Count());
        Assume(num_deps > 0);
        // Uniformly randomly pick one of them and activate it.
        unsigned pick = m_rng.randrange(num_deps);
        unsigned num_steps = 0;
        for (auto tx_idx : top_chunk_info.transactions) {
            ++num_steps;
            auto& tx_data = m_tx_data[tx_idx];
            auto intersect = tx_data.children & bottom_chunk_info.transactions;
            auto count = intersect.Count();
            if (pick < count) {
                for (auto child_idx : intersect) {
                    if (pick == 0) {
                        m_cost.MergeChunksEnd(/*num_steps=*/num_steps);
                        return Activate(tx_idx, child_idx);
                    }
                    --pick;
                }
                Assume(false);
                break;
            }
            pick -= count;
        }
        Assume(false);
        return INVALID_SET_IDX;
    }
 
    template<bool DownWard>
    SetIdx MergeChunksDirected(SetIdx chunk_idx, SetIdx merge_chunk_idx) noexcept
    {
        if constexpr (DownWard) {
            return MergeChunks(chunk_idx, merge_chunk_idx);
        } else {
            return MergeChunks(merge_chunk_idx, chunk_idx);
        }
    }
 
    template<bool DownWard>
    SetIdx PickMergeCandidate(SetIdx chunk_idx) noexcept
    {
        m_cost.PickMergeCandidateBegin();
        Assume(m_chunk_idxs[chunk_idx]);
        auto& chunk_info = m_set_info[chunk_idx];
        // Iterate over all chunks reachable from this one. For those depended-on chunks,
        // remember the highest-feerate (if DownWard) or lowest-feerate (if !DownWard) one.
        // If multiple equal-feerate candidate chunks to merge with exist, pick a random one
        // among them.
 
        FeeFrac best_other_chunk_feerate = chunk_info.feerate;
        SetIdx best_other_chunk_idx = INVALID_SET_IDX;
        uint64_t best_other_chunk_tiebreak{0};
 
        auto todo = DownWard ? m_reachable[chunk_idx].second : m_reachable[chunk_idx].first;
        unsigned steps = 0;
        while (todo.Any()) {
            ++steps;
            // Find a chunk for a transaction in todo, and remove all its transactions from todo.
            auto reached_chunk_idx = m_tx_data[todo.First()].chunk_idx;
            auto& reached_chunk_info = m_set_info[reached_chunk_idx];
            todo -= reached_chunk_info.transactions;
            // See if it has an acceptable feerate.
            auto cmp = DownWard ? FeeRateCompare(best_other_chunk_feerate, reached_chunk_info.feerate)
                                : FeeRateCompare(reached_chunk_info.feerate, best_other_chunk_feerate);
            if (cmp > 0) continue;
            uint64_t tiebreak = m_rng.rand64();
            if (cmp < 0 || tiebreak >= best_other_chunk_tiebreak) {
                best_other_chunk_feerate = reached_chunk_info.feerate;
                best_other_chunk_idx = reached_chunk_idx;
                best_other_chunk_tiebreak = tiebreak;
            }
        }
        Assume(steps <= m_set_info.size());
 
        m_cost.PickMergeCandidateEnd(/*num_steps=*/steps);
        return best_other_chunk_idx;
    }
 
    template<bool DownWard>
    SetIdx MergeStep(SetIdx chunk_idx) noexcept
    {
        auto merge_chunk_idx = PickMergeCandidate<DownWard>(chunk_idx);
        if (merge_chunk_idx == INVALID_SET_IDX) return INVALID_SET_IDX;
        chunk_idx = MergeChunksDirected<DownWard>(chunk_idx, merge_chunk_idx);
        Assume(chunk_idx != INVALID_SET_IDX);
        return chunk_idx;
    }
 
    template<bool DownWard>
    void MergeSequence(SetIdx chunk_idx) noexcept
    {
        Assume(m_chunk_idxs[chunk_idx]);
        while (true) {
            auto merged_chunk_idx = MergeStep<DownWard>(chunk_idx);
            if (merged_chunk_idx == INVALID_SET_IDX) break;
            chunk_idx = merged_chunk_idx;
        }
        // Add the chunk to the queue of improvable chunks, if it wasn't already there.
        if (!m_suboptimal_idxs[chunk_idx]) {
            m_suboptimal_idxs.Set(chunk_idx);
            m_suboptimal_chunks.push_back(chunk_idx);
        }
    }
 
    void Improve(TxIdx parent_idx, TxIdx child_idx) noexcept
    {
        // Deactivate the specified dependency, splitting it into two new chunks: a top containing
        // the parent, and a bottom containing the child. The top should have a higher feerate.
        auto [parent_chunk_idx, child_chunk_idx] = Deactivate(parent_idx, child_idx);
 
        // At this point we have exactly two chunks which may violate topology constraints (the
        // parent chunk and child chunk that were produced by deactivation). We can fix
        // these using just merge sequences, one upwards and one downwards, avoiding the need for a
        // full MakeTopological.
        const auto& parent_reachable = m_reachable[parent_chunk_idx].first;
        const auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions;
        if (parent_reachable.Overlaps(child_chunk_txn)) {
            // The parent chunk has a dependency on a transaction in the child chunk. In this case,
            // the parent needs to merge back with the child chunk (a self-merge), and no other
            // merges are needed. Special-case this, so the overhead of PickMergeCandidate and
            // MergeSequence can be avoided.
 
            // In the self-merge, the roles reverse: the parent chunk (from the split) depends
            // on the child chunk, so child_chunk_idx is the "top" and parent_chunk_idx is the
            // "bottom" for MergeChunks.
            auto merged_chunk_idx = MergeChunks(child_chunk_idx, parent_chunk_idx);
            if (!m_suboptimal_idxs[merged_chunk_idx]) {
                m_suboptimal_idxs.Set(merged_chunk_idx);
                m_suboptimal_chunks.push_back(merged_chunk_idx);
            }
        } else {
            // Merge the top chunk with lower-feerate chunks it depends on.
            MergeSequence<false>(parent_chunk_idx);
            // Merge the bottom chunk with higher-feerate chunks that depend on it.
            MergeSequence<true>(child_chunk_idx);
        }
    }
 
    SetIdx PickChunkToOptimize() noexcept
    {
        m_cost.PickChunkToOptimizeBegin();
        unsigned steps{0};
        while (!m_suboptimal_chunks.empty()) {
            ++steps;
            // Pop an entry from the potentially-suboptimal chunk queue.
            SetIdx chunk_idx = m_suboptimal_chunks.front();
            Assume(m_suboptimal_idxs[chunk_idx]);
            m_suboptimal_idxs.Reset(chunk_idx);
            m_suboptimal_chunks.pop_front();
            if (m_chunk_idxs[chunk_idx]) {
                m_cost.PickChunkToOptimizeEnd(/*num_steps=*/steps);
                return chunk_idx;
            }
            // If what was popped is not currently a chunk, continue. This may
            // happen when a split chunk merges in Improve() with one or more existing chunks that
            // are themselves on the suboptimal queue already.
        }
        m_cost.PickChunkToOptimizeEnd(/*num_steps=*/steps);
        return INVALID_SET_IDX;
    }
 
    std::pair<TxIdx, TxIdx> PickDependencyToSplit(SetIdx chunk_idx) noexcept
    {
        m_cost.PickDependencyToSplitBegin();
        Assume(m_chunk_idxs[chunk_idx]);
        auto& chunk_info = m_set_info[chunk_idx];
 
        // Remember the best dependency {par, chl} seen so far.
        std::pair<TxIdx, TxIdx> candidate_dep = {TxIdx(-1), TxIdx(-1)};
        uint64_t candidate_tiebreak = 0;
        // Iterate over all transactions.
        for (auto tx_idx : chunk_info.transactions) {
            const auto& tx_data = m_tx_data[tx_idx];
            // Iterate over all active child dependencies of the transaction.
            for (auto child_idx : tx_data.active_children) {
                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]];
                // Skip if this dependency is ineligible (the top chunk that would be created
                // does not have higher feerate than the chunk it is currently part of).
                auto cmp = FeeRateCompare(dep_top_info.feerate, chunk_info.feerate);
                if (cmp <= 0) continue;
                // Generate a random tiebreak for this dependency, and reject it if its tiebreak
                // is worse than the best so far. This means that among all eligible
                // dependencies, a uniformly random one will be chosen.
                uint64_t tiebreak = m_rng.rand64();
                if (tiebreak < candidate_tiebreak) continue;
                // Remember this as our (new) candidate dependency.
                candidate_dep = {tx_idx, child_idx};
                candidate_tiebreak = tiebreak;
            }
        }
        m_cost.PickDependencyToSplitEnd(/*num_txns=*/chunk_info.transactions.Count());
        return candidate_dep;
    }
 
public:
    explicit SpanningForestState(const DepGraph<SetType>& depgraph LIFETIMEBOUND, uint64_t rng_seed, const CostModel& cost = CostModel{}) noexcept :
        m_rng(rng_seed), m_depgraph(depgraph), m_cost(cost)
    {
        m_cost.InitializeBegin();
        m_transaction_idxs = depgraph.Positions();
        auto num_transactions = m_transaction_idxs.Count();
        m_tx_data.resize(depgraph.PositionRange());
        m_set_info.resize(num_transactions);
        m_reachable.resize(num_transactions);
        size_t num_chunks = 0;
        size_t num_deps = 0;
        for (auto tx_idx : m_transaction_idxs) {
            // Fill in transaction data.
            auto& tx_data = m_tx_data[tx_idx];
            tx_data.parents = depgraph.GetReducedParents(tx_idx);
            for (auto parent_idx : tx_data.parents) {
                m_tx_data[parent_idx].children.Set(tx_idx);
            }
            num_deps += tx_data.parents.Count();
            // Create a singleton chunk for it.
            tx_data.chunk_idx = num_chunks;
            m_set_info[num_chunks++] = SetInfo(depgraph, tx_idx);
        }
        // Set the reachable transactions for each chunk to the transactions' parents and children.
        for (SetIdx chunk_idx = 0; chunk_idx < num_transactions; ++chunk_idx) {
            auto& tx_data = m_tx_data[m_set_info[chunk_idx].transactions.First()];
            m_reachable[chunk_idx].first = tx_data.parents;
            m_reachable[chunk_idx].second = tx_data.children;
        }
        Assume(num_chunks == num_transactions);
        // Mark all chunk sets as chunks.
        m_chunk_idxs = SetType::Fill(num_chunks);
        m_cost.InitializeEnd(/*num_txns=*/num_chunks, /*num_deps=*/num_deps);
    }
 
    void LoadLinearization(std::span<const DepGraphIndex> old_linearization) noexcept
    {
        // Add transactions one by one, in order of existing linearization.
        for (DepGraphIndex tx_idx : old_linearization) {
            auto chunk_idx = m_tx_data[tx_idx].chunk_idx;
            // Merge the chunk upwards, as long as merging succeeds.
            while (true) {
                chunk_idx = MergeStep<false>(chunk_idx);
                if (chunk_idx == INVALID_SET_IDX) break;
            }
        }
    }
 
    void MakeTopological() noexcept
    {
        m_cost.MakeTopologicalBegin();
        Assume(m_suboptimal_chunks.empty());
        unsigned init_dir = m_rng.randbool();
        SetType merged_chunks;
        // Mark chunks as suboptimal.
        m_suboptimal_idxs = m_chunk_idxs;
        for (auto chunk_idx : m_chunk_idxs) {
            m_suboptimal_chunks.emplace_back(chunk_idx);
            // Randomize the initial order of suboptimal chunks in the queue.
            SetIdx j = m_rng.randrange<SetIdx>(m_suboptimal_chunks.size());
            if (j != m_suboptimal_chunks.size() - 1) {
                std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
            }
        }
        unsigned chunks = m_chunk_idxs.Count();
        unsigned steps = 0;
        while (!m_suboptimal_chunks.empty()) {
            ++steps;
            // Pop an entry from the potentially-suboptimal chunk queue.
            SetIdx chunk_idx = m_suboptimal_chunks.front();
            m_suboptimal_chunks.pop_front();
            Assume(m_suboptimal_idxs[chunk_idx]);
            m_suboptimal_idxs.Reset(chunk_idx);
            // If what was popped is not currently a chunk, continue. This may
            // happen when it was merged with something else since being added.
            if (!m_chunk_idxs[chunk_idx]) continue;
            unsigned direction = merged_chunks[chunk_idx] ? 3 : init_dir + 1;
            int flip = m_rng.randbool();
            for (int i = 0; i < 2; ++i) {
                if (i ^ flip) {
                    if (!(direction & 1)) continue;
                    // Attempt to merge the chunk upwards.
                    auto result_up = MergeStep<false>(chunk_idx);
                    if (result_up != INVALID_SET_IDX) {
                        if (!m_suboptimal_idxs[result_up]) {
                            m_suboptimal_idxs.Set(result_up);
                            m_suboptimal_chunks.push_back(result_up);
                        }
                        merged_chunks.Set(result_up);
                        break;
                    }
                } else {
                    if (!(direction & 2)) continue;
                    // Attempt to merge the chunk downwards.
                    auto result_down = MergeStep<true>(chunk_idx);
                    if (result_down != INVALID_SET_IDX) {
                        if (!m_suboptimal_idxs[result_down]) {
                            m_suboptimal_idxs.Set(result_down);
                            m_suboptimal_chunks.push_back(result_down);
                        }
                        merged_chunks.Set(result_down);
                        break;
                    }
                }
            }
        }
        m_cost.MakeTopologicalEnd(/*num_chunks=*/chunks, /*num_steps=*/steps);
    }
 
    void StartOptimizing() noexcept
    {
        m_cost.StartOptimizingBegin();
        Assume(m_suboptimal_chunks.empty());
        // Mark chunks suboptimal.
        m_suboptimal_idxs = m_chunk_idxs;
        for (auto chunk_idx : m_chunk_idxs) {
            m_suboptimal_chunks.push_back(chunk_idx);
            // Randomize the initial order of suboptimal chunks in the queue.
            SetIdx j = m_rng.randrange<SetIdx>(m_suboptimal_chunks.size());
            if (j != m_suboptimal_chunks.size() - 1) {
                std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
            }
        }
        m_cost.StartOptimizingEnd(/*num_chunks=*/m_suboptimal_chunks.size());
    }
 
    bool OptimizeStep() noexcept
    {
        auto chunk_idx = PickChunkToOptimize();
        if (chunk_idx == INVALID_SET_IDX) {
            // No improvable chunk was found, we are done.
            return false;
        }
        auto [parent_idx, child_idx] = PickDependencyToSplit(chunk_idx);
        if (parent_idx == TxIdx(-1)) {
            // Nothing to improve in chunk_idx. Need to continue with other chunks, if any.
            return !m_suboptimal_chunks.empty();
        }
        // Deactivate the found dependency and then make the state topological again with a
        // sequence of merges.
        Improve(parent_idx, child_idx);
        return true;
    }
 
    void StartMinimizing() noexcept
    {
        m_cost.StartMinimizingBegin();
        m_nonminimal_chunks.clear();
        m_nonminimal_chunks.reserve(m_transaction_idxs.Count());
        // Gather all chunks, and for each, add it with a random pivot in it, and a random initial
        // direction, to m_nonminimal_chunks.
        for (auto chunk_idx : m_chunk_idxs) {
            TxIdx pivot_idx = PickRandomTx(m_set_info[chunk_idx].transactions);
            m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, m_rng.randbits<1>());
            // Randomize the initial order of nonminimal chunks in the queue.
            SetIdx j = m_rng.randrange<SetIdx>(m_nonminimal_chunks.size());
            if (j != m_nonminimal_chunks.size() - 1) {
                std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[j]);
            }
        }
        m_cost.StartMinimizingEnd(/*num_chunks=*/m_nonminimal_chunks.size());
    }
 
    bool MinimizeStep() noexcept
    {
        // If the queue of potentially-non-minimal chunks is empty, we are done.
        if (m_nonminimal_chunks.empty()) return false;
        m_cost.MinimizeStepBegin();
        // Pop an entry from the potentially-non-minimal chunk queue.
        auto [chunk_idx, pivot_idx, flags] = m_nonminimal_chunks.front();
        m_nonminimal_chunks.pop_front();
        auto& chunk_info = m_set_info[chunk_idx];
        bool move_pivot_down = flags & 1;
        bool second_stage = flags & 2;
 
        // Find a random dependency whose top and bottom set feerates are equal, and which has
        // pivot in bottom set (if move_pivot_down) or in top set (if !move_pivot_down).
        std::pair<TxIdx, TxIdx> candidate_dep;
        uint64_t candidate_tiebreak{0};
        bool have_any = false;
        // Iterate over all transactions.
        for (auto tx_idx : chunk_info.transactions) {
            const auto& tx_data = m_tx_data[tx_idx];
            // Iterate over all active child dependencies of the transaction.
            for (auto child_idx : tx_data.active_children) {
                const auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]];
                // Skip if this dependency does not have equal top and bottom set feerates. Note
                // that the top cannot have higher feerate than the bottom, or OptimizeSteps would
                // have dealt with it.
                if (dep_top_info.feerate << chunk_info.feerate) continue;
                have_any = true;
                // Skip if this dependency does not have pivot in the right place.
                if (move_pivot_down == dep_top_info.transactions[pivot_idx]) continue;
                // Remember this as our chosen dependency if it has a better tiebreak.
                uint64_t tiebreak = m_rng.rand64() | 1;
                if (tiebreak > candidate_tiebreak) {
                    candidate_tiebreak = tiebreak;
                    candidate_dep = {tx_idx, child_idx};
                }
            }
        }
        m_cost.MinimizeStepMid(/*num_txns=*/chunk_info.transactions.Count());
        // If no dependencies have equal top and bottom set feerate, this chunk is minimal.
        if (!have_any) return true;
        // If all found dependencies have the pivot in the wrong place, try moving it in the other
        // direction. If this was the second stage already, we are done.
        if (candidate_tiebreak == 0) {
            // Switch to other direction, and to second phase.
            flags ^= 3;
            if (!second_stage) m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, flags);
            return true;
        }
 
        // Otherwise, deactivate the dependency that was found.
        auto [parent_chunk_idx, child_chunk_idx] = Deactivate(candidate_dep.first, candidate_dep.second);
        // Determine if there is a dependency from the new bottom to the new top (opposite from the
        // dependency that was just deactivated).
        auto& parent_reachable = m_reachable[parent_chunk_idx].first;
        auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions;
        if (parent_reachable.Overlaps(child_chunk_txn)) {
            // A self-merge is needed. Note that the child_chunk_idx is the top, and
            // parent_chunk_idx is the bottom, because we activate a dependency in the reverse
            // direction compared to the deactivation above.
            auto merged_chunk_idx = MergeChunks(child_chunk_idx, parent_chunk_idx);
            // Re-insert the chunk into the queue, in the same direction. Note that the chunk_idx
            // will have changed.
            m_nonminimal_chunks.emplace_back(merged_chunk_idx, pivot_idx, flags);
            m_cost.MinimizeStepEnd(/*split=*/false);
        } else {
            // No self-merge happens, and thus we have found a way to split the chunk. Create two
            // smaller chunks, and add them to the queue. The one that contains the current pivot
            // gets to continue with it in the same direction, to minimize the number of times we
            // alternate direction. If we were in the second phase already, the newly created chunk
            // inherits that too, because we know no split with the pivot on the other side is
            // possible already. The new chunk without the current pivot gets a new randomly-chosen
            // one.
            if (move_pivot_down) {
                auto parent_pivot_idx = PickRandomTx(m_set_info[parent_chunk_idx].transactions);
                m_nonminimal_chunks.emplace_back(parent_chunk_idx, parent_pivot_idx, m_rng.randbits<1>());
                m_nonminimal_chunks.emplace_back(child_chunk_idx, pivot_idx, flags);
            } else {
                auto child_pivot_idx = PickRandomTx(m_set_info[child_chunk_idx].transactions);
                m_nonminimal_chunks.emplace_back(parent_chunk_idx, pivot_idx, flags);
                m_nonminimal_chunks.emplace_back(child_chunk_idx, child_pivot_idx, m_rng.randbits<1>());
            }
            if (m_rng.randbool()) {
                std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[m_nonminimal_chunks.size() - 2]);
            }
            m_cost.MinimizeStepEnd(/*split=*/true);
        }
        return true;
    }
 
    std::vector<DepGraphIndex> GetLinearization(const StrongComparator<DepGraphIndex> auto& fallback_order) noexcept
    {
        m_cost.GetLinearizationBegin();
        std::vector<DepGraphIndex> ret;
        ret.reserve(m_set_info.size());
        std::vector<std::pair<SetIdx, TxIdx>> ready_chunks;
        std::vector<TxIdx> chunk_deps(m_set_info.size(), 0);
        std::vector<TxIdx> tx_deps(m_tx_data.size(), 0);
        std::vector<TxIdx> ready_tx;
        // Populate chunk_deps and tx_deps.
        unsigned num_deps{0};
        for (TxIdx chl_idx : m_transaction_idxs) {
            const auto& chl_data = m_tx_data[chl_idx];
            tx_deps[chl_idx] = chl_data.parents.Count();
            num_deps += tx_deps[chl_idx];
            auto chl_chunk_idx = chl_data.chunk_idx;
            auto& chl_chunk_info = m_set_info[chl_chunk_idx];
            chunk_deps[chl_chunk_idx] += (chl_data.parents - chl_chunk_info.transactions).Count();
        }
        auto max_fallback_fn = [&](SetIdx chunk_idx) noexcept {
            auto& chunk = m_set_info[chunk_idx].transactions;
            auto it = chunk.begin();
            DepGraphIndex ret = *it;
            ++it;
            while (it != chunk.end()) {
                if (fallback_order(*it, ret) > 0) ret = *it;
                ++it;
            }
            return ret;
        };
        auto tx_cmp_fn = [&](const auto& a, const auto& b) noexcept {
            // Bail out for identical transactions.
            if (a == b) return false;
            // First sort by increasing transaction feerate.
            auto& a_feerate = m_depgraph.FeeRate(a);
            auto& b_feerate = m_depgraph.FeeRate(b);
            auto feerate_cmp = FeeRateCompare(a_feerate, b_feerate);
            if (feerate_cmp != 0) return feerate_cmp < 0;
            // Then by decreasing transaction size.
            if (a_feerate.size != b_feerate.size) {
                return a_feerate.size > b_feerate.size;
            }
            // Tie-break by decreasing fallback_order.
            auto fallback_cmp = fallback_order(a, b);
            if (fallback_cmp != 0) return fallback_cmp > 0;
            // This should not be hit, because fallback_order defines a strong ordering.
            Assume(false);
            return a < b;
        };
        // Construct a heap with all chunks that have no out-of-chunk dependencies.
        auto chunk_cmp_fn = [&](const auto& a, const auto& b) noexcept {
            // Bail out for identical chunks.
            if (a.first == b.first) return false;
            // First sort by increasing chunk feerate.
            auto& chunk_feerate_a = m_set_info[a.first].feerate;
            auto& chunk_feerate_b = m_set_info[b.first].feerate;
            auto feerate_cmp = FeeRateCompare(chunk_feerate_a, chunk_feerate_b);
            if (feerate_cmp != 0) return feerate_cmp < 0;
            // Then by decreasing chunk size.
            if (chunk_feerate_a.size != chunk_feerate_b.size) {
                return chunk_feerate_a.size > chunk_feerate_b.size;
            }
            // Tie-break by decreasing fallback_order.
            auto fallback_cmp = fallback_order(a.second, b.second);
            if (fallback_cmp != 0) return fallback_cmp > 0;
            // This should not be hit, because fallback_order defines a strong ordering.
            Assume(false);
            return a.second < b.second;
        };
        // Construct a heap with all chunks that have no out-of-chunk dependencies.
        for (SetIdx chunk_idx : m_chunk_idxs) {
            if (chunk_deps[chunk_idx] == 0) {
                ready_chunks.emplace_back(chunk_idx, max_fallback_fn(chunk_idx));
            }
        }
        std::make_heap(ready_chunks.begin(), ready_chunks.end(), chunk_cmp_fn);
        // Pop chunks off the heap.
        while (!ready_chunks.empty()) {
            auto [chunk_idx, _rnd] = ready_chunks.front();
            std::pop_heap(ready_chunks.begin(), ready_chunks.end(), chunk_cmp_fn);
            ready_chunks.pop_back();
            Assume(chunk_deps[chunk_idx] == 0);
            const auto& chunk_txn = m_set_info[chunk_idx].transactions;
            // Build heap of all includable transactions in chunk.
            Assume(ready_tx.empty());
            for (TxIdx tx_idx : chunk_txn) {
                if (tx_deps[tx_idx] == 0) ready_tx.push_back(tx_idx);
            }
            Assume(!ready_tx.empty());
            std::make_heap(ready_tx.begin(), ready_tx.end(), tx_cmp_fn);
            // Pick transactions from the ready heap, append them to linearization, and decrement
            // dependency counts.
            while (!ready_tx.empty()) {
                // Pop an element from the tx_ready heap.
                auto tx_idx = ready_tx.front();
                std::pop_heap(ready_tx.begin(), ready_tx.end(), tx_cmp_fn);
                ready_tx.pop_back();
                // Append to linearization.
                ret.push_back(tx_idx);
                // Decrement dependency counts.
                auto& tx_data = m_tx_data[tx_idx];
                for (TxIdx chl_idx : tx_data.children) {
                    auto& chl_data = m_tx_data[chl_idx];
                    // Decrement tx dependency count.
                    Assume(tx_deps[chl_idx] > 0);
                    if (--tx_deps[chl_idx] == 0 && chunk_txn[chl_idx]) {
                        // Child tx has no dependencies left, and is in this chunk. Add it to the tx heap.
                        ready_tx.push_back(chl_idx);
                        std::push_heap(ready_tx.begin(), ready_tx.end(), tx_cmp_fn);
                    }
                    // Decrement chunk dependency count if this is out-of-chunk dependency.
                    if (chl_data.chunk_idx != chunk_idx) {
                        Assume(chunk_deps[chl_data.chunk_idx] > 0);
                        if (--chunk_deps[chl_data.chunk_idx] == 0) {
                            // Child chunk has no dependencies left. Add it to the chunk heap.
                            ready_chunks.emplace_back(chl_data.chunk_idx, max_fallback_fn(chl_data.chunk_idx));
                            std::push_heap(ready_chunks.begin(), ready_chunks.end(), chunk_cmp_fn);
                        }
                    }
                }
            }
        }
        Assume(ret.size() == m_set_info.size());
        m_cost.GetLinearizationEnd(/*num_txns=*/m_set_info.size(), /*num_deps=*/num_deps);
        return ret;
    }
 
    std::vector<FeeFrac> GetDiagram() const noexcept
    {
        std::vector<FeeFrac> ret;
        for (auto chunk_idx : m_chunk_idxs) {
            ret.push_back(m_set_info[chunk_idx].feerate);
        }
        std::sort(ret.begin(), ret.end(), std::greater{});
        return ret;
    }
 
    uint64_t GetCost() const noexcept { return m_cost.GetCost(); }
 
    void SanityCheck() const
    {
        //
        // Verify dependency parent/child information, and build list of (active) dependencies.
        //
        std::vector<std::pair<TxIdx, TxIdx>> expected_dependencies;
        std::vector<std::pair<TxIdx, TxIdx>> all_dependencies;
        std::vector<std::pair<TxIdx, TxIdx>> active_dependencies;
        for (auto parent_idx : m_depgraph.Positions()) {
            for (auto child_idx : m_depgraph.GetReducedChildren(parent_idx)) {
                expected_dependencies.emplace_back(parent_idx, child_idx);
            }
        }
        for (auto tx_idx : m_transaction_idxs) {
            for (auto child_idx : m_tx_data[tx_idx].children) {
                all_dependencies.emplace_back(tx_idx, child_idx);
                if (m_tx_data[tx_idx].active_children[child_idx]) {
                    active_dependencies.emplace_back(tx_idx, child_idx);
                }
            }
        }
        std::sort(expected_dependencies.begin(), expected_dependencies.end());
        std::sort(all_dependencies.begin(), all_dependencies.end());
        assert(expected_dependencies == all_dependencies);
 
        //
        // Verify the chunks against the list of active dependencies
        //
        SetType chunk_cover;
        for (auto chunk_idx : m_chunk_idxs) {
            const auto& chunk_info = m_set_info[chunk_idx];
            // Verify that transactions in the chunk point back to it. This guarantees
            // that chunks are non-overlapping.
            for (auto tx_idx : chunk_info.transactions) {
                assert(m_tx_data[tx_idx].chunk_idx == chunk_idx);
            }
            assert(!chunk_cover.Overlaps(chunk_info.transactions));
            chunk_cover |= chunk_info.transactions;
            // Verify the chunk's transaction set: start from an arbitrary chunk transaction,
            // and for every active dependency, if it contains the parent or child, add the
            // other. It must have exactly N-1 active dependencies in it, guaranteeing it is
            // acyclic.
            assert(chunk_info.transactions.Any());
            SetType expected_chunk = SetType::Singleton(chunk_info.transactions.First());
            while (true) {
                auto old = expected_chunk;
                size_t active_dep_count{0};
                for (const auto& [par, chl] : active_dependencies) {
                    if (expected_chunk[par] || expected_chunk[chl]) {
                        expected_chunk.Set(par);
                        expected_chunk.Set(chl);
                        ++active_dep_count;
                    }
                }
                if (old == expected_chunk) {
                    assert(expected_chunk.Count() == active_dep_count + 1);
                    break;
                }
            }
            assert(chunk_info.transactions == expected_chunk);
            // Verify the chunk's feerate.
            assert(chunk_info.feerate == m_depgraph.FeeRate(chunk_info.transactions));
            // Verify the chunk's reachable transactions.
            assert(m_reachable[chunk_idx] == GetReachable(expected_chunk));
            // Verify that the chunk's reachable transactions don't include its own transactions.
            assert(!m_reachable[chunk_idx].first.Overlaps(chunk_info.transactions));
            assert(!m_reachable[chunk_idx].second.Overlaps(chunk_info.transactions));
        }
        // Verify that together, the chunks cover all transactions.
        assert(chunk_cover == m_depgraph.Positions());
 
        //
        // Verify transaction data.
        //
        assert(m_transaction_idxs == m_depgraph.Positions());
        for (auto tx_idx : m_transaction_idxs) {
            const auto& tx_data = m_tx_data[tx_idx];
            // Verify it has a valid chunk index, and that chunk includes this transaction.
            assert(m_chunk_idxs[tx_data.chunk_idx]);
            assert(m_set_info[tx_data.chunk_idx].transactions[tx_idx]);
            // Verify parents/children.
            assert(tx_data.parents == m_depgraph.GetReducedParents(tx_idx));
            assert(tx_data.children == m_depgraph.GetReducedChildren(tx_idx));
            // Verify active_children is a subset of children.
            assert(tx_data.active_children.IsSubsetOf(tx_data.children));
            // Verify each active child's dep_top_idx points to a valid non-chunk set.
            for (auto child_idx : tx_data.active_children) {
                assert(tx_data.dep_top_idx[child_idx] < m_set_info.size());
                assert(!m_chunk_idxs[tx_data.dep_top_idx[child_idx]]);
            }
        }
 
        //
        // Verify active dependencies' top sets.
        //
        for (const auto& [par_idx, chl_idx] : active_dependencies) {
            // Verify the top set's transactions: it must contain the parent, and for every
            // active dependency, except the chl_idx->par_idx dependency itself, if it contains the
            // parent or child, it must contain both. It must have exactly N-1 active dependencies
            // in it, guaranteeing it is acyclic.
            SetType expected_top = SetType::Singleton(par_idx);
            while (true) {
                auto old = expected_top;
                size_t active_dep_count{0};
                for (const auto& [par2_idx, chl2_idx] : active_dependencies) {
                    if (par_idx == par2_idx && chl_idx == chl2_idx) continue;
                    if (expected_top[par2_idx] || expected_top[chl2_idx]) {
                        expected_top.Set(par2_idx);
                        expected_top.Set(chl2_idx);
                        ++active_dep_count;
                    }
                }
                if (old == expected_top) {
                    assert(expected_top.Count() == active_dep_count + 1);
                    break;
                }
            }
            assert(!expected_top[chl_idx]);
            auto& dep_top_info = m_set_info[m_tx_data[par_idx].dep_top_idx[chl_idx]];
            assert(dep_top_info.transactions == expected_top);
            // Verify the top set's feerate.
            assert(dep_top_info.feerate == m_depgraph.FeeRate(dep_top_info.transactions));
        }
 
        //
        // Verify m_suboptimal_chunks.
        //
        SetType suboptimal_idxs;
        for (size_t i = 0; i < m_suboptimal_chunks.size(); ++i) {
            auto chunk_idx = m_suboptimal_chunks[i];
            assert(!suboptimal_idxs[chunk_idx]);
            suboptimal_idxs.Set(chunk_idx);
        }
        assert(m_suboptimal_idxs == suboptimal_idxs);
 
        //
        // Verify m_nonminimal_chunks.
        //
        SetType nonminimal_idxs;
        for (size_t i = 0; i < m_nonminimal_chunks.size(); ++i) {
            auto [chunk_idx, pivot, flags] = m_nonminimal_chunks[i];
            assert(m_tx_data[pivot].chunk_idx == chunk_idx);
            assert(!nonminimal_idxs[chunk_idx]);
            nonminimal_idxs.Set(chunk_idx);
        }
        assert(nonminimal_idxs.IsSubsetOf(m_chunk_idxs));
    }
};
 
template<typename SetType>
std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(
    const DepGraph<SetType>& depgraph,
    uint64_t max_cost,
    uint64_t rng_seed,
    const StrongComparator<DepGraphIndex> auto& fallback_order,
    std::span<const DepGraphIndex> old_linearization = {},
    bool is_topological = true) noexcept
{
    SpanningForestState forest(depgraph, rng_seed);
    if (!old_linearization.empty()) {
        forest.LoadLinearization(old_linearization);
        if (!is_topological) forest.MakeTopological();
    } else {
        forest.MakeTopological();
    }
    // Make improvement steps to it until we hit the max_iterations limit, or an optimal result
    // is found.
    if (forest.GetCost() < max_cost) {
        forest.StartOptimizing();
        do {
            if (!forest.OptimizeStep()) break;
        } while (forest.GetCost() < max_cost);
    }
    // Make chunk minimization steps until we hit the max_iterations limit, or all chunks are
    // minimal.
    bool optimal = false;
    if (forest.GetCost() < max_cost) {
        forest.StartMinimizing();
        do {
            if (!forest.MinimizeStep()) {
                optimal = true;
                break;
            }
        } while (forest.GetCost() < max_cost);
    }
    return {forest.GetLinearization(fallback_order), optimal, forest.GetCost()};
}
 
template<typename SetType>
void PostLinearize(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> linearization)
{
    // This algorithm performs a number of passes (currently 2); the even ones operate from back to
    // front, the odd ones from front to back. Each results in an equal-or-better linearization
    // than the one started from.
    // - One pass in either direction guarantees that the resulting chunks are connected.
    // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
    //   guarantee this for graphs where each transaction has at most one child; backward passes
    //   guarantee this for graphs where each transaction has at most one parent).
    // - Starting with a backward pass guarantees the moved-tree property.
    //
    // During an odd (forward) pass, the high-level operation is:
    // - Start with an empty list of groups L=[].
    // - For every transaction i in the old linearization, from front to back:
    //   - Append a new group C=[i], containing just i, to the back of L.
    //   - While L has at least one group before C, and the group immediately before C has feerate
    //     lower than C:
    //     - If C depends on P:
    //       - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
    //     - Otherwise:
    //       - Swap P with C, continuing with the now-moved C.
    // - The output linearization is the concatenation of the groups in L.
    //
    // During even (backward) passes, i iterates from the back to the front of the existing
    // linearization, and new groups are prepended instead of appended to the list L. To enable
    // more code reuse, both passes append groups, but during even passes the meanings of
    // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
    // on output.
    //
    // In the implementation below, the groups are represented by singly-linked lists (pointing
    // from the back to the front), which are themselves organized in a singly-linked circular
    // list (each group pointing to its predecessor, with a special sentinel group at the front
    // that points back to the last group).
    //
    // Information about transaction t is stored in entries[t + 1], while the sentinel is in
    // entries[0].
 
    static constexpr DepGraphIndex SENTINEL{0};
    static constexpr DepGraphIndex NO_PREV_TX{0};
 
 
    struct TxEntry
    {
        DepGraphIndex prev_tx;
 
        // The fields below are only used for transactions that are the last one in a group
        // (referred to as tail transactions below).
 
        DepGraphIndex first_tx;
        DepGraphIndex prev_group;
        SetType group;
        SetType deps;
        FeeFrac feerate;
    };
 
    // As an example, consider the state corresponding to the linearization [1,0,3,2], with
    // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
    //
    //                                        +-----+
    //                                 0<-P-- | 0 S | ---\     Legend:
    //                                        +-----+    |
    //                                           ^       |     - digit in box: entries index
    //             /--------------F---------+    G       |       (note: one more than tx value)
    //             v                         \   |       |     - S: sentinel group
    //          +-----+        +-----+        +-----+    |          (empty feerate)
    //   0<-P-- | 2   | <--P-- | 1   | <--P-- | 4 T |    |     - T: tail transaction, contains
    //          +-----+        +-----+        +-----+    |          fields beyond prev_tv.
    //                                           ^       |     - P: prev_tx reference
    //                                           G       G     - F: first_tx reference
    //                                           |       |     - G: prev_group reference
    //                                        +-----+    |
    //                                 0<-P-- | 3 T | <--/
    //                                        +-----+
    //                                         ^   |
    //                                         \-F-/
    //
    // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
    // groups [2] and [3,0,1].
 
    std::vector<TxEntry> entries(depgraph.PositionRange() + 1);
 
    // Perform two passes over the linearization.
    for (int pass = 0; pass < 2; ++pass) {
        int rev = !(pass & 1);
        // Construct a sentinel group, identifying the start of the list.
        entries[SENTINEL].prev_group = SENTINEL;
        Assume(entries[SENTINEL].feerate.IsEmpty());
 
        // Iterate over all elements in the existing linearization.
        for (DepGraphIndex i = 0; i < linearization.size(); ++i) {
            // Even passes are from back to front; odd passes from front to back.
            DepGraphIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
            // Construct a new group containing just idx. In even passes, the meaning of
            // parent/child and high/low feerate are swapped.
            DepGraphIndex cur_group = idx + 1;
            entries[cur_group].group = SetType::Singleton(idx);
            entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
            entries[cur_group].feerate = depgraph.FeeRate(idx);
            if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
            entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
            entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
            // Insert the new group at the back of the groups linked list.
            entries[cur_group].prev_group = entries[SENTINEL].prev_group;
            entries[SENTINEL].prev_group = cur_group;
 
            // Start merge/swap cycle.
            DepGraphIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
            DepGraphIndex prev_group = entries[cur_group].prev_group;
            // Continue as long as the current group has higher feerate than the previous one.
            while (entries[cur_group].feerate >> entries[prev_group].feerate) {
                // prev_group/cur_group/next_group refer to (the last transactions of) 3
                // consecutive entries in groups list.
                Assume(cur_group == entries[next_group].prev_group);
                Assume(prev_group == entries[cur_group].prev_group);
                // The sentinel has empty feerate, which is neither higher or lower than other
                // feerates. Thus, the while loop we are in here guarantees that cur_group and
                // prev_group are not the sentinel.
                Assume(cur_group != SENTINEL);
                Assume(prev_group != SENTINEL);
                if (entries[cur_group].deps.Overlaps(entries[prev_group].group)) {
                    // There is a dependency between cur_group and prev_group; merge prev_group
                    // into cur_group. The group/deps/feerate fields of prev_group remain unchanged
                    // but become unused.
                    entries[cur_group].group |= entries[prev_group].group;
                    entries[cur_group].deps |= entries[prev_group].deps;
                    entries[cur_group].feerate += entries[prev_group].feerate;
                    // Make the first of the current group point to the tail of the previous group.
                    entries[entries[cur_group].first_tx].prev_tx = prev_group;
                    // The first of the previous group becomes the first of the newly-merged group.
                    entries[cur_group].first_tx = entries[prev_group].first_tx;
                    // The previous group becomes whatever group was before the former one.
                    prev_group = entries[prev_group].prev_group;
                    entries[cur_group].prev_group = prev_group;
                } else {
                    // There is no dependency between cur_group and prev_group; swap them.
                    DepGraphIndex preprev_group = entries[prev_group].prev_group;
                    // If PP, P, C, N were the old preprev, prev, cur, next groups, then the new
                    // layout becomes [PP, C, P, N]. Update prev_groups to reflect that order.
                    entries[next_group].prev_group = prev_group;
                    entries[prev_group].prev_group = cur_group;
                    entries[cur_group].prev_group = preprev_group;
                    // The current group remains the same, but the groups before/after it have
                    // changed.
                    next_group = prev_group;
                    prev_group = preprev_group;
                }
            }
        }
 
        // Convert the entries back to linearization (overwriting the existing one).
        DepGraphIndex cur_group = entries[0].prev_group;
        DepGraphIndex done = 0;
        while (cur_group != SENTINEL) {
            DepGraphIndex cur_tx = cur_group;
            // Traverse the transactions of cur_group (from back to front), and write them in the
            // same order during odd passes, and reversed (front to back) in even passes.
            if (rev) {
                do {
                    *(linearization.begin() + (done++)) = cur_tx - 1;
                    cur_tx = entries[cur_tx].prev_tx;
                } while (cur_tx != NO_PREV_TX);
            } else {
                do {
                    *(linearization.end() - (++done)) = cur_tx - 1;
                    cur_tx = entries[cur_tx].prev_tx;
                } while (cur_tx != NO_PREV_TX);
            }
            cur_group = entries[cur_group].prev_group;
        }
        Assume(done == linearization.size());
    }
}
 
} // namespace cluster_linearize
 
#endif // BITCOIN_CLUSTER_LINEARIZE_H