Inside Bitcoin

251                    assert(real[idx].capacity() > old_cap);
252                    assert(real[idx].capacity() <= 2 * (old_cap + 1));
253                }
254                break;
255            }
256            if (existing_buffer_non_full && command-- == 0) {
257                /* emplace_front() */
258                uint64_t seed{rng.rand64()};
259                size_t old_size = real[idx].size();
260                size_t old_cap = real[idx].capacity();
261                sim[idx].emplace_front(seed);
262                real[idx].emplace_front(seed);
263                assert(real[idx].size() == old_size + 1);
264                if (old_cap > old_size) {
265                    assert(real[idx].capacity() == old_cap);
266                } else {
267                    assert(real[idx].capacity() > old_cap);
268                    assert(real[idx].capacity() <= 2 * (old_cap + 1));
269                }
270                break;
271            }
272            if (existing_buffer_non_empty && command-- == 0) {
273                /* front() [modifying] */
274                tmp = T(rng.rand64());
275                size_t old_size = real[idx].size();
276                assert(sim[idx].front() == real[idx].front());
277                sim[idx].front() = *tmp;
278                real[idx].front() = std::move(*tmp);
279                assert(real[idx].size() == old_size);
280                break;
281            }
282            if (existing_buffer_non_empty && command-- == 0) {
283                /* back() [modifying] */
284                tmp = T(rng.rand64());
285                size_t old_size = real[idx].size();
286                assert(sim[idx].back() == real[idx].back());
287                sim[idx].back() = *tmp;
288                real[idx].back() = *tmp;
289                assert(real[idx].size() == old_size);
290                break;
291            }
292            if (existing_buffer_non_empty && command-- == 0) {
293                /* operator[] [modifying] */
294                tmp = T(rng.rand64());
295                size_t pos = provider.ConsumeIntegralInRange<size_t>(0, sim[idx].size() - 1);
296                size_t old_size = real[idx].size();
297                assert(sim[idx][pos] == real[idx][pos]);
298                sim[idx][pos] = *tmp;
299                real[idx][pos] = std::move(*tmp);
300                assert(real[idx].size() == old_size);
301                break;
302            }
303            if (existing_buffer_non_empty && command-- == 0) {
304                /* pop_front() */
305                assert(sim[idx].front() == real[idx].front());
306                size_t old_size = real[idx].size();
307                sim[idx].pop_front();
308                real[idx].pop_front();
309                assert(real[idx].size() == old_size - 1);
310                break;
311            }
312            if (existing_buffer_non_empty && command-- == 0) {
313                /* pop_back() */
314                assert(sim[idx].back() == real[idx].back());
315                size_t old_size = real[idx].size();
316                sim[idx].pop_back();
317                real[idx].pop_back();
318                assert(real[idx].size() == old_size - 1);
319                break;
320            }
321        }
322    }
323
324    /* Fully compare the final state. */
325    for (unsigned i = 0; i < sim.size(); ++i) {
326        // Make sure const getters work.
327        const VecDeque<T>& realbuf = real[i];
328        const std::deque<T>& simbuf = sim[i];
329        compare_fn(realbuf, simbuf);
330        for (unsigned j = 0; j < sim.size(); ++j) {
331            assert((realbuf == real[j]) == (simbuf == sim[j]));
332            assert(((realbuf <=> real[j]) >= 0) == (simbuf >= sim[j]));
333            assert(((realbuf <=> real[j]) <= 0) == (simbuf <= sim[j]));
334        }
335        // Clear out the buffers so we can check below that no objects exist anymore.
336        sim[i].clear();
337        real[i].clear();
338    }
339
340    if constexpr (CheckNoneLeft) {
341        tmp = std::nullopt;
342        T::CheckNoneExist();
343    }
344}
345
346/** Data structure with built-in tracking of all existing objects. */
347template<size_t Size>
348class TrackedObj
349{
350    static_assert(Size > 0);
351
352    /* Data type for map that actually stores the object data.
353     *
354     * The key is a pointer to the TrackedObj, the value is the uint64_t it was initialized with.
355     * Default-constructed and moved-from objects hold an std::nullopt.
356     */
357    using track_map_type = std::map<const TrackedObj<Size>*, std::optional<uint64_t>>;
358
359private:
360
361    /** Actual map. */
362    static inline track_map_type g_tracker;
363
364    /** Iterators into the tracker map for this object.
365     *
366     * This is an array of size Size, all holding the same value, to give the object configurable
367     * size. The value is g_tracker.end() if this object is not fully initialized. */
368    typename track_map_type::iterator m_track_entry[Size];
369
370    void Check() const
371    {
372        auto it = g_tracker.find(this);
373        for (size_t i = 0; i < Size; ++i) {
374            assert(m_track_entry[i] == it);
375        }
376    }
377
378    /** Create entry for this object in g_tracker and populate m_track_entry. */
379    void Register()
380    {
381        auto [it, inserted] = g_tracker.emplace(this, std::nullopt);
382        assert(inserted);
383        for (size_t i = 0; i < Size; ++i) {
384            m_track_entry[i] = it;
385        }
386    }
387
388    void Deregister()
389    {
390        Check();
391        assert(m_track_entry[0] != g_tracker.end());
392        g_tracker.erase(m_track_entry[0]);
393        for (size_t i = 0; i < Size; ++i) {
394            m_track_entry[i] = g_tracker.end();
395        }
396    }
397
398    /** Get value corresponding to this object in g_tracker. */
399    std::optional<uint64_t>& Deref()
400    {
401        Check();
402        assert(m_track_entry[0] != g_tracker.end());
403        return m_track_entry[0]->second;
404    }
405
406    /** Get value corresponding to this object in g_tracker. */
407    const std::optional<uint64_t>& Deref() const
408    {
409        Check();
410        assert(m_track_entry[0] != g_tracker.end());
411        return m_track_entry[0]->second;
412    }
413
414public:
415    ~TrackedObj() { Deregister(); }
416    TrackedObj() { Register(); }
417
418    TrackedObj(uint64_t value)
419    {
420        Register();
421        Deref() = value;
422    }
423
424    TrackedObj(const TrackedObj& other)
425    {
426        Register();
427        Deref() = other.Deref();
428    }
429
430    TrackedObj(TrackedObj&& other)
431    {
432        Register();
433        Deref() = other.Deref();
434        other.Deref() = std::nullopt;
435    }
436
437    TrackedObj& operator=(const TrackedObj& other)
438    {
439        if (this == &other) return *this;
440        Deref() = other.Deref();
441        return *this;
442    }
443
444    TrackedObj& operator=(TrackedObj&& other)
445    {
446        if (this == &other) return *this;
447        Deref() = other.Deref();
448        other.Deref() = std::nullopt;
449        return *this;
450    }
451
452    friend bool operator==(const TrackedObj& a, const TrackedObj& b)
453    {
454        return a.Deref() == b.Deref();
455    }
456
457    friend std::strong_ordering operator<=>(const TrackedObj& a, const TrackedObj& b)
458    {
459        // Libc++ 15 & 16 do not support std::optional<T>::operator<=> yet. See
460        // https://reviews.llvm.org/D146392.
461        if (!a.Deref().has_value() || !b.Deref().has_value()) {
462            return a.Deref().has_value() <=> b.Deref().has_value();
463        }
464        return *a.Deref() <=> *b.Deref();
465    }
466
467    static void CheckNoneExist()
468    {
469        assert(g_tracker.empty());
470    }
471};
472
473} // namespace
474
475FUZZ_TARGET(vecdeque)
476{
477    // Run the test with simple uints (which satisfy all the trivial properties).
478    static_assert(std::is_trivially_copyable_v<uint32_t>);
479    static_assert(std::is_trivially_destructible_v<uint64_t>);
480    TestType<uint8_t, false>(buffer, 1);
481    TestType<uint16_t, false>(buffer, 2);
482    TestType<uint32_t, false>(buffer, 3);
483    TestType<uint64_t, false>(buffer, 4);
484
485    // Run the test with TrackedObjs (which do not).
486    static_assert(!std::is_trivially_copyable_v<TrackedObj<3>>);
487    static_assert(!std::is_trivially_destructible_v<TrackedObj<17>>);
488    TestType<TrackedObj<1>, true>(buffer, 5);
489    TestType<TrackedObj<3>, true>(buffer, 6);
490    TestType<TrackedObj<17>, true>(buffer, 7);
491}
492