Inside Bitcoin

1751                    if (par_idx == par2_idx && chl_idx == chl2_idx) continue;
1752                    if (expected_top[par2_idx] || expected_top[chl2_idx]) {
1753                        expected_top.Set(par2_idx);
1754                        expected_top.Set(chl2_idx);
1755                        ++active_dep_count;
1756                    }
1757                }
1758                if (old == expected_top) {
1759                    assert(expected_top.Count() == active_dep_count + 1);
1760                    break;
1761                }
1762            }
1763            assert(!expected_top[chl_idx]);
1764            auto& dep_top_info = m_set_info[m_tx_data[par_idx].dep_top_idx[chl_idx]];
1765            assert(dep_top_info.transactions == expected_top);
1766            // Verify the top set's feerate.
1767            assert(dep_top_info.feerate == m_depgraph.FeeRate(dep_top_info.transactions));
1768        }
1769
1770        //
1771        // Verify m_suboptimal_chunks.
1772        //
1773        SetType suboptimal_idxs;
1774        for (size_t i = 0; i < m_suboptimal_chunks.size(); ++i) {
1775            auto chunk_idx = m_suboptimal_chunks[i];
1776            assert(!suboptimal_idxs[chunk_idx]);
1777            suboptimal_idxs.Set(chunk_idx);
1778        }
1779        assert(m_suboptimal_idxs == suboptimal_idxs);
1780
1781        //
1782        // Verify m_nonminimal_chunks.
1783        //
1784        SetType nonminimal_idxs;
1785        for (size_t i = 0; i < m_nonminimal_chunks.size(); ++i) {
1786            auto [chunk_idx, pivot, flags] = m_nonminimal_chunks[i];
1787            assert(m_tx_data[pivot].chunk_idx == chunk_idx);
1788            assert(!nonminimal_idxs[chunk_idx]);
1789            nonminimal_idxs.Set(chunk_idx);
1790        }
1791        assert(nonminimal_idxs.IsSubsetOf(m_chunk_idxs));
1792    }
1793};
1794
1795/** Find or improve a linearization for a cluster.
1796 *
1797 * @param[in] depgraph            Dependency graph of the cluster to be linearized.
1798 * @param[in] max_cost            Upper bound on the amount of work that will be done.
1799 * @param[in] rng_seed            A random number seed to control search order. This prevents peers
1800 *                                from predicting exactly which clusters would be hard for us to
1801 *                                linearize.
1802 * @param[in] fallback_order      A comparator to order transactions, used to sort equal-feerate
1803 *                                chunks and transactions. See SpanningForestState::GetLinearization
1804 *                                for details.
1805 * @param[in] old_linearization   An existing linearization for the cluster, or empty.
1806 * @param[in] is_topological      (Only relevant if old_linearization is not empty) Whether
1807 *                                old_linearization is topologically valid.
1808 * @return                        A tuple of:
1809 *                                - The resulting linearization. It is guaranteed to be at least as
1810 *                                  good (in the feerate diagram sense) as old_linearization.
1811 *                                - A boolean indicating whether the result is guaranteed to be
1812 *                                  optimal with minimal chunks.
1813 *                                - How many optimization steps were actually performed.
1814 */
1815template<typename SetType>
1816std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(
1817    const DepGraph<SetType>& depgraph,
1818    uint64_t max_cost,
1819    uint64_t rng_seed,
1820    const StrongComparator<DepGraphIndex> auto& fallback_order,
1821    std::span<const DepGraphIndex> old_linearization = {},
1822    bool is_topological = true) noexcept
1823{
1824    /** Initialize a spanning forest data structure for this cluster. */
1825    SpanningForestState forest(depgraph, rng_seed);
1826    if (!old_linearization.empty()) {
1827        forest.LoadLinearization(old_linearization);
1828        if (!is_topological) forest.MakeTopological();
1829    } else {
1830        forest.MakeTopological();
1831    }
1832    // Make improvement steps to it until we hit the max_iterations limit, or an optimal result
1833    // is found.
1834    if (forest.GetCost() < max_cost) {
1835        forest.StartOptimizing();
1836        do {
1837            if (!forest.OptimizeStep()) break;
1838        } while (forest.GetCost() < max_cost);
1839    }
1840    // Make chunk minimization steps until we hit the max_iterations limit, or all chunks are
1841    // minimal.
1842    bool optimal = false;
1843    if (forest.GetCost() < max_cost) {
1844        forest.StartMinimizing();
1845        do {
1846            if (!forest.MinimizeStep()) {
1847                optimal = true;
1848                break;
1849            }
1850        } while (forest.GetCost() < max_cost);
1851    }
1852    return {forest.GetLinearization(fallback_order), optimal, forest.GetCost()};
1853}
1854
1855/** Improve a given linearization.
1856 *
1857 * @param[in]     depgraph       Dependency graph of the cluster being linearized.
1858 * @param[in,out] linearization  On input, an existing linearization for depgraph. On output, a
1859 *                               potentially better linearization for the same graph.
1860 *
1861 * Postlinearization guarantees:
1862 * - The resulting chunks are connected.
1863 * - If the input has a tree shape (either all transactions have at most one child, or all
1864 *   transactions have at most one parent), the result is optimal.
1865 * - Given a linearization L1 and a leaf transaction T in it. Let L2 be L1 with T moved to the end,
1866 *   optionally with its fee increased. Let L3 be the postlinearization of L2. L3 will be at least
1867 *   as good as L1. This means that replacing transactions with same-size higher-fee transactions
1868 *   will not worsen linearizations through a "drop conflicts, append new transactions,
1869 *   postlinearize" process.
1870 */
1871template<typename SetType>
1872void PostLinearize(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> linearization)
1873{
1874    // This algorithm performs a number of passes (currently 2); the even ones operate from back to
1875    // front, the odd ones from front to back. Each results in an equal-or-better linearization
1876    // than the one started from.
1877    // - One pass in either direction guarantees that the resulting chunks are connected.
1878    // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
1879    //   guarantee this for graphs where each transaction has at most one child; backward passes
1880    //   guarantee this for graphs where each transaction has at most one parent).
1881    // - Starting with a backward pass guarantees the moved-tree property.
1882    //
1883    // During an odd (forward) pass, the high-level operation is:
1884    // - Start with an empty list of groups L=[].
1885    // - For every transaction i in the old linearization, from front to back:
1886    //   - Append a new group C=[i], containing just i, to the back of L.
1887    //   - While L has at least one group before C, and the group immediately before C has feerate
1888    //     lower than C:
1889    //     - If C depends on P:
1890    //       - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
1891    //     - Otherwise:
1892    //       - Swap P with C, continuing with the now-moved C.
1893    // - The output linearization is the concatenation of the groups in L.
1894    //
1895    // During even (backward) passes, i iterates from the back to the front of the existing
1896    // linearization, and new groups are prepended instead of appended to the list L. To enable
1897    // more code reuse, both passes append groups, but during even passes the meanings of
1898    // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
1899    // on output.
1900    //
1901    // In the implementation below, the groups are represented by singly-linked lists (pointing
1902    // from the back to the front), which are themselves organized in a singly-linked circular
1903    // list (each group pointing to its predecessor, with a special sentinel group at the front
1904    // that points back to the last group).
1905    //
1906    // Information about transaction t is stored in entries[t + 1], while the sentinel is in
1907    // entries[0].
1908
1909    /** Index of the sentinel in the entries array below. */
1910    static constexpr DepGraphIndex SENTINEL{0};
1911    /** Indicator that a group has no previous transaction. */
1912    static constexpr DepGraphIndex NO_PREV_TX{0};
1913
1914
1915    /** Data structure per transaction entry. */
1916    struct TxEntry
1917    {
1918        /** The index of the previous transaction in this group; NO_PREV_TX if this is the first
1919         *  entry of a group. */
1920        DepGraphIndex prev_tx;
1921
1922        // The fields below are only used for transactions that are the last one in a group
1923        // (referred to as tail transactions below).
1924
1925        /** Index of the first transaction in this group, possibly itself. */
1926        DepGraphIndex first_tx;
1927        /** Index of the last transaction in the previous group. The first group (the sentinel)
1928         *  points back to the last group here, making it a singly-linked circular list. */
1929        DepGraphIndex prev_group;
1930        /** All transactions in the group. Empty for the sentinel. */
1931        SetType group;
1932        /** All dependencies of the group (descendants in even passes; ancestors in odd ones). */
1933        SetType deps;
1934        /** The combined fee/size of transactions in the group. Fee is negated in even passes. */
1935        FeeFrac feerate;
1936    };
1937
1938    // As an example, consider the state corresponding to the linearization [1,0,3,2], with
1939    // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
1940    //
1941    //                                        +-----+
1942    //                                 0<-P-- | 0 S | ---\     Legend:
1943    //                                        +-----+    |
1944    //                                           ^       |     - digit in box: entries index
1945    //             /--------------F---------+    G       |       (note: one more than tx value)
1946    //             v                         \   |       |     - S: sentinel group
1947    //          +-----+        +-----+        +-----+    |          (empty feerate)
1948    //   0<-P-- | 2   | <--P-- | 1   | <--P-- | 4 T |    |     - T: tail transaction, contains
1949    //          +-----+        +-----+        +-----+    |          fields beyond prev_tv.
1950    //                                           ^       |     - P: prev_tx reference
1951    //                                           G       G     - F: first_tx reference
1952    //                                           |       |     - G: prev_group reference
1953    //                                        +-----+    |
1954    //                                 0<-P-- | 3 T | <--/
1955    //                                        +-----+
1956    //                                         ^   |
1957    //                                         \-F-/
1958    //
1959    // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
1960    // groups [2] and [3,0,1].
1961
1962    std::vector<TxEntry> entries(depgraph.PositionRange() + 1);
1963
1964    // Perform two passes over the linearization.
1965    for (int pass = 0; pass < 2; ++pass) {
1966        int rev = !(pass & 1);
1967        // Construct a sentinel group, identifying the start of the list.
1968        entries[SENTINEL].prev_group = SENTINEL;
1969        Assume(entries[SENTINEL].feerate.IsEmpty());
1970
1971        // Iterate over all elements in the existing linearization.
1972        for (DepGraphIndex i = 0; i < linearization.size(); ++i) {
1973            // Even passes are from back to front; odd passes from front to back.
1974            DepGraphIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
1975            // Construct a new group containing just idx. In even passes, the meaning of
1976            // parent/child and high/low feerate are swapped.
1977            DepGraphIndex cur_group = idx + 1;
1978            entries[cur_group].group = SetType::Singleton(idx);
1979            entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
1980            entries[cur_group].feerate = depgraph.FeeRate(idx);
1981            if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
1982            entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
1983            entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
1984            // Insert the new group at the back of the groups linked list.
1985            entries[cur_group].prev_group = entries[SENTINEL].prev_group;
1986            entries[SENTINEL].prev_group = cur_group;
1987
1988            // Start merge/swap cycle.
1989            DepGraphIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
1990            DepGraphIndex prev_group = entries[cur_group].prev_group;
1991            // Continue as long as the current group has higher feerate than the previous one.
1992            while (ByRatio{entries[cur_group].feerate} > ByRatio{entries[prev_group].feerate}) {
1993                // prev_group/cur_group/next_group refer to (the last transactions of) 3
1994                // consecutive entries in groups list.
1995                Assume(cur_group == entries[next_group].prev_group);
1996                Assume(prev_group == entries[cur_group].prev_group);
1997                // The sentinel has empty feerate, which is neither higher or lower than other
1998                // feerates. Thus, the while loop we are in here guarantees that cur_group and
1999                // prev_group are not the sentinel.
2000                Assume(cur_group != SENTINEL);