Inside Bitcoin

1501            num_deps += tx_deps[chl_idx];
1502            auto chl_chunk_idx = chl_data.chunk_idx;
1503            auto& chl_chunk_info = m_set_info[chl_chunk_idx];
1504            chunk_deps[chl_chunk_idx] += (chl_data.parents - chl_chunk_info.transactions).Count();
1505        }
1506        /** Function to compute the highest element of a chunk, by fallback_order. */
1507        auto max_fallback_fn = [&](SetIdx chunk_idx) noexcept {
1508            auto& chunk = m_set_info[chunk_idx].transactions;
1509            auto it = chunk.begin();
1510            DepGraphIndex ret = *it;
1511            ++it;
1512            while (it != chunk.end()) {
1513                if (fallback_order(*it, ret) > 0) ret = *it;
1514                ++it;
1515            }
1516            return ret;
1517        };
1518        /** Comparison function for the transaction heap. Note that it is a max-heap, so
1519         *  tx_cmp_fn(a, b) == true means "a appears after b in the linearization". */
1520        auto tx_cmp_fn = [&](const auto& a, const auto& b) noexcept {
1521            // Bail out for identical transactions.
1522            if (a == b) return false;
1523            // First sort by increasing transaction feerate.
1524            auto& a_feerate = m_depgraph.FeeRate(a);
1525            auto& b_feerate = m_depgraph.FeeRate(b);
1526            auto feerate_cmp = ByRatio{a_feerate} <=> ByRatio{b_feerate};
1527            if (feerate_cmp != 0) return feerate_cmp < 0;
1528            // Then by decreasing transaction size.
1529            if (a_feerate.size != b_feerate.size) {
1530                return a_feerate.size > b_feerate.size;
1531            }
1532            // Tie-break by decreasing fallback_order.
1533            auto fallback_cmp = fallback_order(a, b);
1534            if (fallback_cmp != 0) return fallback_cmp > 0;
1535            // This should not be hit, because fallback_order defines a strong ordering.
1536            Assume(false);
1537            return a < b;
1538        };
1539        // Construct a heap with all chunks that have no out-of-chunk dependencies.
1540        /** Comparison function for the chunk heap. Note that it is a max-heap, so
1541         *  chunk_cmp_fn(a, b) == true means "a appears after b in the linearization". */
1542        auto chunk_cmp_fn = [&](const auto& a, const auto& b) noexcept {
1543            // Bail out for identical chunks.
1544            if (a.first == b.first) return false;
1545            // First sort by increasing chunk feerate.
1546            auto& chunk_feerate_a = m_set_info[a.first].feerate;
1547            auto& chunk_feerate_b = m_set_info[b.first].feerate;
1548            auto feerate_cmp = ByRatio{chunk_feerate_a} <=> ByRatio{chunk_feerate_b};
1549            if (feerate_cmp != 0) return feerate_cmp < 0;
1550            // Then by decreasing chunk size.
1551            if (chunk_feerate_a.size != chunk_feerate_b.size) {
1552                return chunk_feerate_a.size > chunk_feerate_b.size;
1553            }
1554            // Tie-break by decreasing fallback_order.
1555            auto fallback_cmp = fallback_order(a.second, b.second);
1556            if (fallback_cmp != 0) return fallback_cmp > 0;
1557            // This should not be hit, because fallback_order defines a strong ordering.
1558            Assume(false);
1559            return a.second < b.second;
1560        };
1561        // Construct a heap with all chunks that have no out-of-chunk dependencies.
1562        for (SetIdx chunk_idx : m_chunk_idxs) {
1563            if (chunk_deps[chunk_idx] == 0) {
1564                ready_chunks[num_ready_chunks++] = {chunk_idx, max_fallback_fn(chunk_idx)};
1565            }
1566        }
1567        std::make_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn);
1568        // Pop chunks off the heap.
1569        while (num_ready_chunks > 0) {
1570            auto [chunk_idx, _rnd] = ready_chunks.front();
1571            std::pop_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn);
1572            --num_ready_chunks;
1573            Assume(chunk_deps[chunk_idx] == 0);
1574            const auto& chunk_txn = m_set_info[chunk_idx].transactions;
1575            // Build heap of all includable transactions in chunk.
1576            Assume(num_ready_tx == 0);
1577            for (TxIdx tx_idx : chunk_txn) {
1578                if (tx_deps[tx_idx] == 0) ready_tx[num_ready_tx++] = tx_idx;
1579            }
1580            Assume(num_ready_tx > 0);
1581            std::make_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn);
1582            // Pick transactions from the ready heap, append them to linearization, and decrement
1583            // dependency counts.
1584            while (num_ready_tx > 0) {
1585                // Pop an element from the tx_ready heap.
1586                auto tx_idx = ready_tx.front();
1587                std::pop_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn);
1588                --num_ready_tx;
1589                // Append to linearization.
1590                ret.push_back(tx_idx);
1591                // Decrement dependency counts.
1592                auto& tx_data = m_tx_data[tx_idx];
1593                for (TxIdx chl_idx : tx_data.children) {
1594                    auto& chl_data = m_tx_data[chl_idx];
1595                    // Decrement tx dependency count.
1596                    Assume(tx_deps[chl_idx] > 0);
1597                    if (--tx_deps[chl_idx] == 0 && chunk_txn[chl_idx]) {
1598                        // Child tx has no dependencies left, and is in this chunk. Add it to the tx heap.
1599                        ready_tx[num_ready_tx++] = chl_idx;
1600                        std::push_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn);
1601                    }
1602                    // Decrement chunk dependency count if this is out-of-chunk dependency.
1603                    if (chl_data.chunk_idx != chunk_idx) {
1604                        Assume(chunk_deps[chl_data.chunk_idx] > 0);
1605                        if (--chunk_deps[chl_data.chunk_idx] == 0) {
1606                            // Child chunk has no dependencies left. Add it to the chunk heap.
1607                            ready_chunks[num_ready_chunks++] = {chl_data.chunk_idx, max_fallback_fn(chl_data.chunk_idx)};
1608                            std::push_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn);
1609                        }
1610                    }
1611                }
1612            }
1613        }
1614        Assume(ret.size() == m_set_info.size());
1615        m_cost.GetLinearizationEnd(/*num_txns=*/m_set_info.size(), /*num_deps=*/num_deps);
1616        return ret;
1617    }
1618
1619    /** Get the diagram for the current state, which must be topological. Test-only.
1620     *
1621     * The linearization produced by GetLinearization() is always at least as good (in the
1622     * CompareChunks() sense) as this diagram, but may be better.
1623     *
1624     * After an OptimizeStep(), the diagram will always be at least as good as before. Once
1625     * OptimizeStep() returns false, the diagram will be equivalent to that produced by
1626     * GetLinearization(), and optimal.
1627     *
1628     * After a MinimizeStep(), the diagram cannot change anymore (in the CompareChunks() sense),
1629     * but its number of segments can increase still. Once MinimizeStep() returns false, the number
1630     * of chunks of the produced linearization will match the number of segments in the diagram.
1631     */
1632    std::vector<FeeFrac> GetDiagram() const noexcept
1633    {
1634        std::vector<FeeFrac> ret;
1635        for (auto chunk_idx : m_chunk_idxs) {
1636            ret.push_back(m_set_info[chunk_idx].feerate);
1637        }
1638        std::ranges::sort(ret, std::greater<ByRatioNegSize<FeeFrac>>{});
1639        return ret;
1640    }
1641
1642    /** Determine how much work was performed so far. */
1643    uint64_t GetCost() const noexcept { return m_cost.GetCost(); }
1644
1645    /** Verify internal consistency of the data structure. */
1646    void SanityCheck() const
1647    {
1648        //
1649        // Verify dependency parent/child information, and build list of (active) dependencies.
1650        //
1651        std::vector<std::pair<TxIdx, TxIdx>> expected_dependencies;
1652        std::vector<std::pair<TxIdx, TxIdx>> all_dependencies;
1653        std::vector<std::pair<TxIdx, TxIdx>> active_dependencies;
1654        for (auto parent_idx : m_depgraph.Positions()) {
1655            for (auto child_idx : m_depgraph.GetReducedChildren(parent_idx)) {
1656                expected_dependencies.emplace_back(parent_idx, child_idx);
1657            }
1658        }
1659        for (auto tx_idx : m_transaction_idxs) {
1660            for (auto child_idx : m_tx_data[tx_idx].children) {
1661                all_dependencies.emplace_back(tx_idx, child_idx);
1662                if (m_tx_data[tx_idx].active_children[child_idx]) {
1663                    active_dependencies.emplace_back(tx_idx, child_idx);
1664                }
1665            }
1666        }
1667        std::ranges::sort(expected_dependencies);
1668        std::ranges::sort(all_dependencies);
1669        assert(expected_dependencies == all_dependencies);
1670
1671        //
1672        // Verify the chunks against the list of active dependencies
1673        //
1674        SetType chunk_cover;
1675        for (auto chunk_idx : m_chunk_idxs) {
1676            const auto& chunk_info = m_set_info[chunk_idx];
1677            // Verify that transactions in the chunk point back to it. This guarantees
1678            // that chunks are non-overlapping.
1679            for (auto tx_idx : chunk_info.transactions) {
1680                assert(m_tx_data[tx_idx].chunk_idx == chunk_idx);
1681            }
1682            assert(!chunk_cover.Overlaps(chunk_info.transactions));
1683            chunk_cover |= chunk_info.transactions;
1684            // Verify the chunk's transaction set: start from an arbitrary chunk transaction,
1685            // and for every active dependency, if it contains the parent or child, add the
1686            // other. It must have exactly N-1 active dependencies in it, guaranteeing it is
1687            // acyclic.
1688            assert(chunk_info.transactions.Any());
1689            SetType expected_chunk = SetType::Singleton(chunk_info.transactions.First());
1690            while (true) {
1691                auto old = expected_chunk;
1692                size_t active_dep_count{0};
1693                for (const auto& [par, chl] : active_dependencies) {
1694                    if (expected_chunk[par] || expected_chunk[chl]) {
1695                        expected_chunk.Set(par);
1696                        expected_chunk.Set(chl);
1697                        ++active_dep_count;
1698                    }
1699                }
1700                if (old == expected_chunk) {
1701                    assert(expected_chunk.Count() == active_dep_count + 1);
1702                    break;
1703                }
1704            }
1705            assert(chunk_info.transactions == expected_chunk);
1706            // Verify the chunk's feerate.
1707            assert(chunk_info.feerate == m_depgraph.FeeRate(chunk_info.transactions));
1708            // Verify the chunk's reachable transactions.
1709            assert(m_reachable[chunk_idx] == GetReachable(expected_chunk));
1710            // Verify that the chunk's reachable transactions don't include its own transactions.
1711            assert(!m_reachable[chunk_idx].first.Overlaps(chunk_info.transactions));
1712            assert(!m_reachable[chunk_idx].second.Overlaps(chunk_info.transactions));
1713        }
1714        // Verify that together, the chunks cover all transactions.
1715        assert(chunk_cover == m_depgraph.Positions());
1716
1717        //
1718        // Verify transaction data.
1719        //
1720        assert(m_transaction_idxs == m_depgraph.Positions());
1721        for (auto tx_idx : m_transaction_idxs) {
1722            const auto& tx_data = m_tx_data[tx_idx];
1723            // Verify it has a valid chunk index, and that chunk includes this transaction.
1724            assert(m_chunk_idxs[tx_data.chunk_idx]);
1725            assert(m_set_info[tx_data.chunk_idx].transactions[tx_idx]);
1726            // Verify parents/children.
1727            assert(tx_data.parents == m_depgraph.GetReducedParents(tx_idx));
1728            assert(tx_data.children == m_depgraph.GetReducedChildren(tx_idx));
1729            // Verify active_children is a subset of children.
1730            assert(tx_data.active_children.IsSubsetOf(tx_data.children));
1731            // Verify each active child's dep_top_idx points to a valid non-chunk set.
1732            for (auto child_idx : tx_data.active_children) {
1733                assert(tx_data.dep_top_idx[child_idx] < m_set_info.size());
1734                assert(!m_chunk_idxs[tx_data.dep_top_idx[child_idx]]);
1735            }
1736        }
1737
1738        //
1739        // Verify active dependencies' top sets.
1740        //
1741        for (const auto& [par_idx, chl_idx] : active_dependencies) {
1742            // Verify the top set's transactions: it must contain the parent, and for every
1743            // active dependency, except the chl_idx->par_idx dependency itself, if it contains the
1744            // parent or child, it must contain both. It must have exactly N-1 active dependencies
1745            // in it, guaranteeing it is acyclic.
1746            SetType expected_top = SetType::Singleton(par_idx);
1747            while (true) {
1748                auto old = expected_top;
1749                size_t active_dep_count{0};
1750                for (const auto& [par2_idx, chl2_idx] : active_dependencies) {