Function ReadTopologicalSet

src/test/fuzz/cluster_linearize.cpp:285–313

/** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
template<typename SetType>
SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader, bool non_empty)
{
    // Read a bitmask from the fuzzing input. Add 1 if non_empty, so the mask is definitely not
    // zero in that case.
    uint64_t mask{0};
    try {
        reader >> VARINT(mask);
    } catch(const std::ios_base::failure&) {}
    if (mask != uint64_t(-1)) mask += non_empty;

    SetType ret;
    for (auto i : todo) {
        if (!ret[i]) {
            if (mask & 1) ret |= depgraph.Ancestors(i);
            mask >>= 1;
        }
    }
    ret &= todo;

    // While mask starts off non-zero if non_empty is true, it is still possible that all its low
    // bits are 0, and ret ends up being empty. As a last resort, use the in-todo ancestry of the
    // first todo position.
    if (non_empty && ret.None()) {
        Assume(todo.Any());
        ret = depgraph.Ancestors(todo.First()) & todo;
        Assume(ret.Any());
    }
    return ret;
}

/** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
template<typename BS>