Inside Bitcoin

251                chunking = perm_chunking;
252            }
253        } else {
254            // Otherwise, fast forward to the last permutation with the same non-topological
255            // prefix.
256            auto first_non_topo = perm_linearization.begin() + topo_length;
257            assert(std::is_sorted(first_non_topo + 1, perm_linearization.end()));
258            std::reverse(first_non_topo + 1, perm_linearization.end());
259        }
260    } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
261
262    return linearization;
263}
264
265
266/** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
267template<typename BS>
268void MakeConnected(DepGraph<BS>& depgraph)
269{
270    auto todo = depgraph.Positions();
271    auto comp = depgraph.FindConnectedComponent(todo);
272    Assume(depgraph.IsConnected(comp));
273    todo -= comp;
274    while (todo.Any()) {
275        auto nextcomp = depgraph.FindConnectedComponent(todo);
276        Assume(depgraph.IsConnected(nextcomp));
277        depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
278        todo -= nextcomp;
279        comp = nextcomp;
280    }
281}
282
283/** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
284template<typename SetType>
285SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader, bool non_empty)
286{
287    // Read a bitmask from the fuzzing input. Add 1 if non_empty, so the mask is definitely not
288    // zero in that case.
289    uint64_t mask{0};
290    try {
291        reader >> VARINT(mask);
292    } catch(const std::ios_base::failure&) {}
293    if (mask != uint64_t(-1)) mask += non_empty;
294
295    SetType ret;
296    for (auto i : todo) {
297        if (!ret[i]) {
298            if (mask & 1) ret |= depgraph.Ancestors(i);
299            mask >>= 1;
300        }
301    }
302    ret &= todo;
303
304    // While mask starts off non-zero if non_empty is true, it is still possible that all its low
305    // bits are 0, and ret ends up being empty. As a last resort, use the in-todo ancestry of the
306    // first todo position.
307    if (non_empty && ret.None()) {
308        Assume(todo.Any());
309        ret = depgraph.Ancestors(todo.First()) & todo;
310        Assume(ret.Any());
311    }
312    return ret;
313}
314
315/** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
316template<typename BS>
317std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader, bool topological=true)
318{
319    std::vector<DepGraphIndex> linearization;
320    TestBitSet todo = depgraph.Positions();
321    // In every iteration one transaction is appended to linearization.
322    while (todo.Any()) {
323        // Compute the set of transactions to select from.
324        TestBitSet potential_next;
325        if (topological) {
326            // Find all transactions with no not-yet-included ancestors.
327            for (auto j : todo) {
328                if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
329                    potential_next.Set(j);
330                }
331            }
332        } else {
333            // Allow any element to be selected next, regardless of topology.
334            potential_next = todo;
335        }
336        // There must always be one (otherwise there is a cycle in the graph).
337        assert(potential_next.Any());
338        // Read a number from reader, and interpret it as index into potential_next.
339        uint64_t idx{0};
340        try {
341            reader >> VARINT(idx);
342        } catch (const std::ios_base::failure&) {}
343        idx %= potential_next.Count();
344        // Find out which transaction that corresponds to.
345        for (auto j : potential_next) {
346            if (idx == 0) {
347                // When found, add it to linearization and remove it from todo.
348                linearization.push_back(j);
349                assert(todo[j]);
350                todo.Reset(j);
351                break;
352            }
353            --idx;
354        }
355    }
356    return linearization;
357}
358
359/** Given a dependency graph, construct a tree-structured graph.
360 *
361 * Copies the nodes from the depgraph, but only keeps the first parent (even direction)
362 * or the first child (odd direction) for each transaction.
363 */
364template<typename BS>
365DepGraph<BS> BuildTreeGraph(const DepGraph<BS>& depgraph, uint8_t direction)
366{
367    DepGraph<BS> depgraph_tree;
368    for (DepGraphIndex i = 0; i < depgraph.PositionRange(); ++i) {
369        if (depgraph.Positions()[i]) {
370            depgraph_tree.AddTransaction(depgraph.FeeRate(i));
371        } else {
372            // For holes, add a dummy transaction which is deleted below, so that non-hole
373            // transactions retain their position.
374            depgraph_tree.AddTransaction(FeeFrac{});
375        }
376    }
377    depgraph_tree.RemoveTransactions(BS::Fill(depgraph.PositionRange()) - depgraph.Positions());
378
379    if (direction & 1) {
380        for (DepGraphIndex i : depgraph.Positions()) {
381            auto children = depgraph.GetReducedChildren(i);
382            if (children.Any()) {
383                depgraph_tree.AddDependencies(BS::Singleton(i), children.First());
384            }
385        }
386    } else {
387        for (DepGraphIndex i : depgraph.Positions()) {
388            auto parents = depgraph.GetReducedParents(i);
389            if (parents.Any()) {
390                depgraph_tree.AddDependencies(BS::Singleton(parents.First()), i);
391            }
392        }
393    }
394
395    return depgraph_tree;
396}
397
398} // namespace
399
400FUZZ_TARGET(clusterlin_depgraph_sim)
401{
402    // Simulation test to verify the full behavior of DepGraph.
403
404    FuzzedDataProvider provider(buffer.data(), buffer.size());
405
406    /** Real DepGraph being tested. */
407    DepGraph<TestBitSet> real;
408    /** Simulated DepGraph (sim[i] is std::nullopt if position i does not exist; otherwise,
409     *  sim[i]->first is its individual feerate, and sim[i]->second is its set of ancestors. */
410    std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
411    /** The number of non-nullopt position in sim. */
412    DepGraphIndex num_tx_sim{0};
413
414    /** Read a valid index of a transaction from the provider. */
415    auto idx_fn = [&]() {
416        auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1);
417        for (DepGraphIndex i = 0; i < sim.size(); ++i) {
418            if (!sim[i].has_value()) continue;
419            if (offset == 0) return i;
420            --offset;
421        }
422        assert(false);
423        return DepGraphIndex(-1);
424    };
425
426    /** Read a valid subset of the transactions from the provider. */
427    auto subset_fn = [&]() {
428        auto range = (uint64_t{1} << num_tx_sim) - 1;
429        const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
430        auto mask_shifted = mask;
431        TestBitSet subset;
432        for (DepGraphIndex i = 0; i < sim.size(); ++i) {
433            if (!sim[i].has_value()) continue;
434            if (mask_shifted & 1) {
435                subset.Set(i);
436            }
437            mask_shifted >>= 1;
438        }
439        assert(mask_shifted == 0);
440        return subset;
441    };
442
443    /** Read any set of transactions from the provider (including unused positions). */
444    auto set_fn = [&]() {
445        auto range = (uint64_t{1} << sim.size()) - 1;
446        const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
447        TestBitSet set;
448        for (DepGraphIndex i = 0; i < sim.size(); ++i) {
449            if ((mask >> i) & 1) {
450                set.Set(i);
451            }
452        }
453        return set;
454    };
455
456    /** Propagate ancestor information in sim. */
457    auto anc_update_fn = [&]() {
458        while (true) {
459            bool updates{false};
460            for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
461                if (!sim[chl].has_value()) continue;
462                for (auto par : sim[chl]->second) {
463                    if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
464                        sim[chl]->second |= sim[par]->second;
465                        updates = true;
466                    }
467                }
468            }
469            if (!updates) break;
470        }
471    };
472
473    /** Compare the state of transaction i in the simulation with the real one. */
474    auto check_fn = [&](DepGraphIndex i) {
475        // Compare used positions.
476        assert(real.Positions()[i] == sim[i].has_value());
477        if (sim[i].has_value()) {
478            // Compare feerate.
479            assert(real.FeeRate(i) == sim[i]->first);
480            // Compare ancestors (note that SanityCheck verifies correspondence between ancestors
481            // and descendants, so we can restrict ourselves to ancestors here).
482            assert(real.Ancestors(i) == sim[i]->second);
483        }
484    };
485
486    auto last_compaction_pos{real.PositionRange()};
487
488    LIMITED_WHILE (provider.remaining_bytes() > 0, 1000) {
489        int command = provider.ConsumeIntegral<uint8_t>() % 4;
490        while (true) {
491            // Iterate decreasing command until an applicable branch is found.
492            if (num_tx_sim < TestBitSet::Size() && command-- == 0) {
493                // AddTransaction.
494                auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
495                auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
496                FeeFrac feerate{fee, size};
497                // Apply to DepGraph.
498                auto idx = real.AddTransaction(feerate);
499                // Verify that the returned index is correct.
500                assert(!sim[idx].has_value());