/*
 * Copyright (C) 2015-2024 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"

#include "Helpers/Test.h"
#include <algorithm>
#include <thread>
#include <wtf/HashCountedSet.h>
#include <wtf/HashMap.h>
#include <wtf/HashSet.h>
#include <wtf/ListHashSet.h>
#include <wtf/Lock.h>
#include <wtf/NeverDestroyed.h>
#include <wtf/ThreadSafeWeakHashSet.h>
#include <wtf/WeakHashMap.h>
#include <wtf/WeakHashSet.h>
#include <wtf/WeakListHashSet.h>
#include <wtf/WeakRef.h>

namespace TestWebKitAPI {
class Base;
class Derived;
struct Int;
struct Foo;
class MultipleInheritanceBase1;
class MultipleInheritanceBase2;
class MultipleInheritanceDerived;
class TestType;
}

namespace WTF {
template<typename T> struct IsDeprecatedWeakRefSmartPointerException;
template<> struct IsDeprecatedWeakRefSmartPointerException<TestWebKitAPI::Base> : std::true_type { };
template<> struct IsDeprecatedWeakRefSmartPointerException<TestWebKitAPI::Derived> : std::true_type { };
template<> struct IsDeprecatedWeakRefSmartPointerException<TestWebKitAPI::Foo> : std::true_type { };
template<> struct IsDeprecatedWeakRefSmartPointerException<TestWebKitAPI::Int> : std::true_type { };
template<> struct IsDeprecatedWeakRefSmartPointerException<TestWebKitAPI::MultipleInheritanceBase1> : std::true_type { };
template<> struct IsDeprecatedWeakRefSmartPointerException<TestWebKitAPI::MultipleInheritanceBase2> : std::true_type { };
template<> struct IsDeprecatedWeakRefSmartPointerException<TestWebKitAPI::MultipleInheritanceDerived> : std::true_type { };
template<> struct IsDeprecatedWeakRefSmartPointerException<TestWebKitAPI::TestType> : std::true_type { };
}

namespace TestWebKitAPI {

static unsigned s_baseWeakReferences = 0;

class WeakPtrImplWithCounter final : public WTF::WeakPtrImplBase<WeakPtrImplWithCounter> {
public:
    template<typename T>
    WeakPtrImplWithCounter(T* ptr)
        : WTF::WeakPtrImplBase<WeakPtrImplWithCounter>(ptr)
    {
        increment();
    }

    ~WeakPtrImplWithCounter()
    {
        decrement();
    }

    static void increment() { ++s_baseWeakReferences; }
    static void decrement() { --s_baseWeakReferences; }
};

template<typename T> using CanMakeWeakPtr = WTF::CanMakeWeakPtr<T, WeakPtrFactoryInitialization::Lazy, WeakPtrImplWithCounter>;
template<typename T, typename U> using WeakHashMap = WTF::WeakHashMap<T, U, WeakPtrImplWithCounter>;
template<typename T> using WeakHashSet = WTF::WeakHashSet<T, WeakPtrImplWithCounter>;
template<typename T> using WeakListHashSet = WTF::WeakListHashSet<T, WeakPtrImplWithCounter>;
template<typename T> using WeakPtr = WTF::WeakPtr<T, WeakPtrImplWithCounter>;
template<typename T> using WeakRef = WTF::WeakRef<T, WeakPtrImplWithCounter>;
template<typename T> using WeakPtrFactory = WTF::WeakPtrFactory<T, WeakPtrImplWithCounter>;

struct Int : public CanMakeWeakPtr<Int> {
    Int(int i) : m_i(i) { }
    operator int() const { return m_i; }
    bool operator==(const Int& other) const { return m_i == other.m_i; }
    int m_i;
};

class Base : public CanMakeWeakPtr<Base> {
    WTF_DEPRECATED_MAKE_FAST_ALLOCATED(Base);
public:
    Base() { }

    virtual ~Base() = default;

    int foo()
    {
        return 0;
    }

    int dummy; // Prevent empty base class optimization, to make testing more interesting.
};

class Derived : public Base {
public:
    Derived() { }

    ~Derived() override { } // Force a pointer fixup when casting Base <-> Derived

    int foo()
    {
        return 1;
    }
};

TEST(WTF_WeakPtr, Basic)
{
    Int dummy(5);
    WeakPtrFactory<Int>* factory = new WeakPtrFactory<Int>();
    WeakPtr<Int> weakPtr1 = factory->createWeakPtr(dummy);
    WeakPtr<Int> weakPtr2 = factory->createWeakPtr(dummy);
    WeakPtr<Int> weakPtr3 = factory->createWeakPtr(dummy);
    EXPECT_EQ(weakPtr1.get(), &dummy);
    EXPECT_EQ(weakPtr2.get(), &dummy);
    EXPECT_EQ(weakPtr3.get(), &dummy);
    EXPECT_TRUE(!!weakPtr1);
    EXPECT_TRUE(!!weakPtr2);
    EXPECT_TRUE(!!weakPtr3);
    EXPECT_TRUE(weakPtr1 == weakPtr2);
    EXPECT_TRUE(weakPtr1 == &dummy);
    EXPECT_TRUE(&dummy == weakPtr2);
    delete factory;
    EXPECT_NULL(weakPtr1.get());
    EXPECT_NULL(weakPtr2.get());
    EXPECT_NULL(weakPtr3.get());
    EXPECT_FALSE(weakPtr1);
    EXPECT_FALSE(weakPtr2);
    EXPECT_FALSE(weakPtr3);
}

TEST(WTF_WeakPtr, Assignment)
{
    Int dummy(5);
    WeakPtr<Int> weakPtr;
    {
        WeakPtrFactory<Int> factory;
        EXPECT_NULL(weakPtr.get());
        weakPtr = factory.createWeakPtr(dummy);
        EXPECT_EQ(weakPtr.get(), &dummy);
    }
    EXPECT_NULL(weakPtr.get());
}

TEST(WTF_WeakPtr, MultipleFactories)
{
    Int dummy1(5);
    Int dummy2(7);
    WeakPtrFactory<Int>* factory1 = new WeakPtrFactory<Int>();
    WeakPtrFactory<Int>* factory2 = new WeakPtrFactory<Int>();
    WeakPtr<Int> weakPtr1 = factory1->createWeakPtr(dummy1);
    WeakPtr<Int> weakPtr2 = factory2->createWeakPtr(dummy2);
    EXPECT_EQ(weakPtr1.get(), &dummy1);
    EXPECT_EQ(weakPtr2.get(), &dummy2);
    EXPECT_TRUE(weakPtr1 != weakPtr2);
    EXPECT_TRUE(weakPtr1 != &dummy2);
    EXPECT_TRUE(&dummy1 != weakPtr2);
    delete factory1;
    EXPECT_NULL(weakPtr1.get());
    EXPECT_EQ(weakPtr2.get(), &dummy2);
    delete factory2;
    EXPECT_NULL(weakPtr2.get());
}

TEST(WTF_WeakPtr, RevokeAll)
{
    Int dummy(5);
    WeakPtrFactory<Int> factory;
    WeakPtr<Int> weakPtr1 = factory.createWeakPtr(dummy);
    WeakPtr<Int> weakPtr2 = factory.createWeakPtr(dummy);
    WeakPtr<Int> weakPtr3 = factory.createWeakPtr(dummy);
    EXPECT_EQ(weakPtr1.get(), &dummy);
    EXPECT_EQ(weakPtr2.get(), &dummy);
    EXPECT_EQ(weakPtr3.get(), &dummy);
    factory.revokeAll();
    EXPECT_NULL(weakPtr1.get());
    EXPECT_NULL(weakPtr2.get());
    EXPECT_NULL(weakPtr3.get());
}

struct Foo : public CanMakeWeakPtr<Foo> {
    void bar() { };
};

TEST(WTF_WeakPtr, Dereference)
{
    Foo f;
    WeakPtrFactory<Foo> factory;
    WeakPtr<Foo> weakPtr = factory.createWeakPtr(f);
    weakPtr->bar();
}

TEST(WTF_WeakPtr, Operators)
{
    Foo f;
    WeakPtrFactory<Foo> factory;
    WeakPtr<Foo> weakPtr = factory.createWeakPtr(f);

    WeakPtr<Foo> weakPtr2 = weakPtr;
    EXPECT_EQ(weakPtr2.get(), &f);

    WeakPtr<Foo> weakPtr3;
    weakPtr3 = weakPtr;
    EXPECT_EQ(weakPtr3.get(), &f);

    WeakPtr<Foo> weakPtr4 = WTF::move(weakPtr);
    EXPECT_EQ(weakPtr4.get(), &f);
    SUPPRESS_USE_AFTER_MOVE EXPECT_FALSE(weakPtr);
}

TEST(WTF_WeakPtr, Forget)
{
    Int dummy(5);
    Int dummy2(7);

    WeakPtrFactory<Int> outerFactory;
    WeakPtr<Int> weakPtr1, weakPtr2, weakPtr3, weakPtr4;
    {
        WeakPtrFactory<Int> innerFactory;
        weakPtr1 = innerFactory.createWeakPtr(dummy);
        weakPtr2 = innerFactory.createWeakPtr(dummy);
        weakPtr3 = innerFactory.createWeakPtr(dummy);
        EXPECT_EQ(weakPtr1.get(), &dummy);
        EXPECT_EQ(weakPtr2.get(), &dummy);
        EXPECT_EQ(weakPtr3.get(), &dummy);
        weakPtr1.clear();
        weakPtr3 = nullptr;
        EXPECT_NULL(weakPtr1.get());
        EXPECT_EQ(weakPtr2.get(), &dummy);
        EXPECT_NULL(weakPtr3.get());
        weakPtr1.clear();
        weakPtr3.clear();
        EXPECT_NULL(weakPtr1.get());
        EXPECT_EQ(weakPtr2.get(), &dummy);
        EXPECT_NULL(weakPtr3.get());
        weakPtr3 = nullptr;
        EXPECT_NULL(weakPtr1.get());
        EXPECT_EQ(weakPtr2.get(), &dummy);
        EXPECT_NULL(weakPtr3.get());
        
        weakPtr4 = weakPtr2;
        EXPECT_EQ(weakPtr2.get(), &dummy);
        EXPECT_EQ(weakPtr4.get(), &dummy);

        WeakPtr<Int> weakPtr5 = weakPtr2;
        EXPECT_EQ(weakPtr2.get(), &dummy);
        EXPECT_EQ(weakPtr5.get(), &dummy);
        weakPtr5.clear();
        EXPECT_NULL(weakPtr5.get());
        EXPECT_EQ(weakPtr2.get(), &dummy);

        weakPtr4 = outerFactory.createWeakPtr(dummy2);
        EXPECT_EQ(weakPtr2.get(), &dummy);
        EXPECT_EQ(weakPtr4.get(), &dummy2);
    }

    EXPECT_NULL(weakPtr1.get());
    EXPECT_NULL(weakPtr2.get());
    EXPECT_EQ(weakPtr4.get(), &dummy2);

    WeakPtr<Int> weakPtr5 = weakPtr4;
    EXPECT_EQ(weakPtr4.get(), &dummy2);
    EXPECT_EQ(weakPtr5.get(), &dummy2);
    weakPtr5.clear();
    EXPECT_NULL(weakPtr5.get());
    WeakPtr<Int> weakPtr6 = weakPtr5;
    EXPECT_NULL(weakPtr6.get());
    EXPECT_EQ(weakPtr5.get(), weakPtr6.get());

    WeakPtr<Int> weakPtr7 = outerFactory.createWeakPtr(dummy2);
    EXPECT_EQ(weakPtr7.get(), &dummy2);
    weakPtr7 = nullptr;
    EXPECT_NULL(weakPtr7.get());
}

TEST(WTF_WeakPtr, Downcasting)
{
    int dummy0(0);
    int dummy1(1);

    WeakPtr<Base> baseWeakPtr;
    WeakPtr<Derived> derivedWeakPtr;

    {
        Derived object;
        Derived* derivedPtr = &object;
        Base* basePtr = static_cast<Base*>(&object);

        baseWeakPtr = WeakPtr<Base>(object);
        EXPECT_EQ(basePtr->foo(), dummy0);
        EXPECT_EQ(baseWeakPtr->foo(), basePtr->foo());
        EXPECT_EQ(baseWeakPtr.get()->foo(), basePtr->foo());

        derivedWeakPtr = object;
        EXPECT_EQ(derivedWeakPtr->foo(), dummy1);
        EXPECT_EQ(derivedWeakPtr->foo(), derivedPtr->foo());
        EXPECT_EQ(derivedWeakPtr.get()->foo(), derivedPtr->foo());

        EXPECT_EQ(baseWeakPtr.get(), derivedWeakPtr.get());
    }

    EXPECT_NULL(baseWeakPtr.get());
    EXPECT_NULL(derivedWeakPtr.get());
}

TEST(WTF_WeakPtr, DerivedConstructAndAssign)
{
    Derived derived;
    {
        WeakPtr<Derived> derivedWeakPtr { derived };
        WeakPtr<Base> baseWeakPtr { WTF::move(derivedWeakPtr) };
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        SUPPRESS_USE_AFTER_MOVE EXPECT_NULL(derivedWeakPtr.get());
    }

    {
        WeakPtr<Derived> derivedWeakPtr { derived };
        WeakPtr<Base> baseWeakPtr { derivedWeakPtr };
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        EXPECT_EQ(derivedWeakPtr.get(), &derived);
    }

    {
        WeakPtr<Derived> derivedWeakPtr { derived };
        WeakPtr<Base> baseWeakPtr;
        baseWeakPtr = WTF::move(derivedWeakPtr);
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        SUPPRESS_USE_AFTER_MOVE EXPECT_NULL(derivedWeakPtr.get());
    }

    {
        WeakPtr<Derived> derivedWeakPtr { derived };
        WeakPtr<Base> baseWeakPtr;
        baseWeakPtr = derivedWeakPtr;
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        EXPECT_EQ(derivedWeakPtr.get(), &derived);
    }
}

TEST(WTF_WeakPtr, DerivedConstructAndAssignConst)
{
    const Derived derived;
    {
        WeakPtr<const Derived> derivedWeakPtr { derived };
        WeakPtr<const Base> baseWeakPtr { WTF::move(derivedWeakPtr) };
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        SUPPRESS_USE_AFTER_MOVE EXPECT_NULL(derivedWeakPtr.get());
    }

    {
        WeakPtr<const Derived> derivedWeakPtr { derived };
        WeakPtr<const Base> baseWeakPtr { derivedWeakPtr };
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        EXPECT_EQ(derivedWeakPtr.get(), &derived);
    }

    {
        WeakPtr<const Derived> derivedWeakPtr { derived };
        WeakPtr<const Base> baseWeakPtr;
        baseWeakPtr = WTF::move(derivedWeakPtr);
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        SUPPRESS_USE_AFTER_MOVE EXPECT_NULL(derivedWeakPtr.get());
    }

    {
        WeakPtr<const Derived> derivedWeakPtr { derived };
        WeakPtr<const Base> baseWeakPtr;
        baseWeakPtr = derivedWeakPtr;
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        EXPECT_EQ(derivedWeakPtr.get(), &derived);
    }
}

class BaseObjectWithRefAndWeakPtr : public RefCounted<BaseObjectWithRefAndWeakPtr>, public CanMakeWeakPtr<BaseObjectWithRefAndWeakPtr> {
public:
    static Ref<BaseObjectWithRefAndWeakPtr> create() { return adoptRef(*new BaseObjectWithRefAndWeakPtr()); }

    virtual ~BaseObjectWithRefAndWeakPtr() = default;
    void someFunction() { }

protected:
    BaseObjectWithRefAndWeakPtr() = default;
};

class DerivedObjectWithRefAndWeakPtr : public BaseObjectWithRefAndWeakPtr {
public:
    static Ref<DerivedObjectWithRefAndWeakPtr> create() { return adoptRef(*new DerivedObjectWithRefAndWeakPtr()); }

private:
    DerivedObjectWithRefAndWeakPtr() = default;
    virtual ~DerivedObjectWithRefAndWeakPtr() = default;
};

TEST(WTF_WeakPtr, MakeWeakPtrTakesRef)
{
    Ref baseObject = BaseObjectWithRefAndWeakPtr::create();
    EXPECT_EQ(baseObject->refCount(), 1U);
    EXPECT_EQ(baseObject->weakCount(), 0U);
    {
        WeakPtr<BaseObjectWithRefAndWeakPtr> baseObjectWeakPtr { baseObject.get() };
        EXPECT_EQ(baseObject->refCount(), 1U);
        EXPECT_EQ(baseObject->weakCount(), 1U);
        EXPECT_EQ(baseObjectWeakPtr.get(), baseObject.ptr());
    }
    EXPECT_EQ(baseObject->refCount(), 1U);
    EXPECT_EQ(baseObject->weakCount(), 0U);

    WeakPtr<BaseObjectWithRefAndWeakPtr> baseWeakPtr;
    {
        Ref derivedObject = DerivedObjectWithRefAndWeakPtr::create();
        EXPECT_EQ(derivedObject->refCount(), 1U);
        EXPECT_EQ(derivedObject->weakCount(), 0U);
        {
            WeakPtr<DerivedObjectWithRefAndWeakPtr> derivedObjectWeakPtr { derivedObject };
            EXPECT_EQ(derivedObject->refCount(), 1U);
            EXPECT_EQ(derivedObject->weakCount(), 1U);
            EXPECT_EQ(derivedObjectWeakPtr.get(), derivedObject.ptr());
        }
        EXPECT_EQ(derivedObject->refCount(), 1U);
        EXPECT_EQ(derivedObject->weakCount(), 0U);
        {
            Ref<BaseObjectWithRefAndWeakPtr> baseRefPtr = derivedObject;
            EXPECT_EQ(derivedObject->refCount(), 2U);
            EXPECT_EQ(derivedObject->weakCount(), 0U);
            baseWeakPtr = baseRefPtr.get();
            EXPECT_EQ(derivedObject->refCount(), 2U);
            EXPECT_EQ(derivedObject->weakCount(), 1U);
            EXPECT_EQ(baseWeakPtr.get(), derivedObject.ptr());
        }
        EXPECT_EQ(derivedObject->refCount(), 1U);
        EXPECT_EQ(derivedObject->weakCount(), 1U);
        EXPECT_EQ(baseWeakPtr.get(), derivedObject.ptr());
    }
    EXPECT_EQ(baseWeakPtr.get(), nullptr);
}

TEST(WTF_WeakPtr, MakeWeakPtrTakesRefPtr)
{
    RefPtr<BaseObjectWithRefAndWeakPtr> baseObject = BaseObjectWithRefAndWeakPtr::create();
    EXPECT_EQ(baseObject->refCount(), 1U);
    EXPECT_EQ(baseObject->weakCount(), 0U);
    {
        WeakPtr<BaseObjectWithRefAndWeakPtr> baseObjectWeakPtr { baseObject.get() };
        EXPECT_EQ(baseObject->refCount(), 1U);
        EXPECT_EQ(baseObject->weakCount(), 1U);
        EXPECT_EQ(baseObjectWeakPtr.get(), baseObject.get());
        baseObject = nullptr;
        EXPECT_EQ(baseObjectWeakPtr.get(), nullptr);
    }

    RefPtr<DerivedObjectWithRefAndWeakPtr> derivedObject = DerivedObjectWithRefAndWeakPtr::create();
    EXPECT_EQ(derivedObject->refCount(), 1U);
    EXPECT_EQ(derivedObject->weakCount(), 0U);
    {
        WeakPtr<DerivedObjectWithRefAndWeakPtr> derivedObjectWeakPtr { derivedObject.get() };
        EXPECT_EQ(derivedObject->refCount(), 1U);
        EXPECT_EQ(derivedObject->weakCount(), 1U);
        EXPECT_EQ(derivedObjectWeakPtr.get(), derivedObject.get());

        WeakPtr<BaseObjectWithRefAndWeakPtr> baseObjectWeakPtr { derivedObject.get() };
        EXPECT_EQ(derivedObject->refCount(), 1U);
        EXPECT_EQ(derivedObject->weakCount(), 2U);
        EXPECT_EQ(baseObjectWeakPtr.get(), derivedObject.get());
    }
    EXPECT_EQ(derivedObject->refCount(), 1U);
    EXPECT_EQ(derivedObject->weakCount(), 0U);
}

template <typename T>
unsigned computeSizeOfWeakHashSet(const WeakHashSet<T>& set)
{
    unsigned size = 0;
    for (auto& item : set) {
        UNUSED_PARAM(item);
        size++;
    }
    return size;
}

TEST(WTF_WeakPtr, WeakHashSetBasic)
{
    {
        WeakHashSet<Base> weakHashSet;
        Base object;
        EXPECT_FALSE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        weakHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        EXPECT_TRUE(weakHashSet.contains(object));
        weakHashSet.add(object);
        EXPECT_TRUE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakHashSet<Base> weakHashSet;
        Derived object;
        EXPECT_FALSE(weakHashSet.contains(object));
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        EXPECT_EQ(s_baseWeakReferences, 0u);
        weakHashSet.add(object);
        EXPECT_TRUE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.add(object);
        EXPECT_TRUE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakHashSet<Base> weakHashSet;
        {
            Base object;
            EXPECT_FALSE(weakHashSet.contains(object));
            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
            EXPECT_EQ(s_baseWeakReferences, 0u);
            weakHashSet.add(object);
            EXPECT_TRUE(weakHashSet.contains(object));
            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
            EXPECT_EQ(s_baseWeakReferences, 1u);
        }
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        weakHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakHashSet<Base> weakHashSet;
        {
            Base object1;
            Base object2;
            EXPECT_FALSE(weakHashSet.contains(object1));
            EXPECT_FALSE(weakHashSet.contains(object2));
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
            weakHashSet.add(object1);
            EXPECT_TRUE(weakHashSet.contains(object1));
            EXPECT_FALSE(weakHashSet.contains(object2));
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
            weakHashSet.add(object2);
            EXPECT_TRUE(weakHashSet.contains(object1));
            EXPECT_TRUE(weakHashSet.contains(object2));
            EXPECT_EQ(s_baseWeakReferences, 2u);
            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 2u);
            weakHashSet.remove(object1);
            EXPECT_FALSE(weakHashSet.contains(object1));
            EXPECT_TRUE(weakHashSet.contains(object2));
            EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        }
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        weakHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakHashSet<Base> weakHashSet;
        Base object1;
        Base object2;
        Base object3;
        EXPECT_FALSE(weakHashSet.contains(object1));
        EXPECT_FALSE(weakHashSet.contains(object2));
        EXPECT_FALSE(weakHashSet.contains(object3));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        weakHashSet.add(object1);
        weakHashSet.add(object2);
        EXPECT_TRUE(weakHashSet.contains(object1));
        EXPECT_TRUE(weakHashSet.contains(object2));
        EXPECT_FALSE(weakHashSet.contains(object3));
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 2u);
        weakHashSet.remove(object1);
        EXPECT_FALSE(weakHashSet.contains(object1));
        EXPECT_TRUE(weakHashSet.contains(object2));
        EXPECT_FALSE(weakHashSet.contains(object3));
        EXPECT_EQ(s_baseWeakReferences, 2u); // Because object2 holds onto WeakReference.
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.remove(object3);
        EXPECT_FALSE(weakHashSet.contains(object1));
        EXPECT_TRUE(weakHashSet.contains(object2));
        EXPECT_FALSE(weakHashSet.contains(object3));
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.add(object2);
        EXPECT_FALSE(weakHashSet.contains(object1));
        EXPECT_TRUE(weakHashSet.contains(object2));
        EXPECT_FALSE(weakHashSet.contains(object3));
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);
}

TEST(WTF_WeakPtr, WeakHashSetRemoveIf)
{
    {
        WeakHashSet<Base> weakHashSet;
        Base object1;
        Base object2;
        Base object3;
        weakHashSet.add(object1);
        weakHashSet.add(object2);
        weakHashSet.add(object3);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 3u);

        bool removedAny = weakHashSet.removeIf([&](Base& item) {
            return &item == &object2;
        });
        EXPECT_TRUE(removedAny);
        EXPECT_TRUE(weakHashSet.contains(object1));
        EXPECT_FALSE(weakHashSet.contains(object2));
        EXPECT_TRUE(weakHashSet.contains(object3));
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 2u);

        bool removedNone = weakHashSet.removeIf([](Base&) {
            return false;
        });
        EXPECT_FALSE(removedNone);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 2u);
        weakHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        // removeIf() drops dead (null) weak references as it iterates and reports them
        // as removed, but never invokes the predicate for them.
        WeakHashSet<Base> weakHashSet;
        auto object1 = makeUnique<Base>();
        Base object2;
        weakHashSet.add(*object1);
        weakHashSet.add(object2);
        EXPECT_EQ(s_baseWeakReferences, 2u);
        object1 = nullptr;

        unsigned predicateCalls = 0;
        bool removedAny = weakHashSet.removeIf([&](Base& item) {
            ++predicateCalls;
            EXPECT_EQ(&item, &object2);
            return false;
        });
        EXPECT_TRUE(removedAny);
        EXPECT_EQ(predicateCalls, 1u);
        EXPECT_TRUE(weakHashSet.contains(object2));
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);
}

TEST(WTF_WeakPtr, WeakHashSetConstObjects)
{
    {
        WeakHashSet<Base> weakHashSet;
        const Base object;
        EXPECT_FALSE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        weakHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        EXPECT_TRUE(weakHashSet.contains(object));
        weakHashSet.checkConsistency();
        weakHashSet.add(object);
        EXPECT_TRUE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.checkConsistency();
        weakHashSet.remove(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
    }

    {
        WeakHashSet<Base> weakHashSet;
        const Derived object;
        EXPECT_FALSE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        weakHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        EXPECT_TRUE(weakHashSet.contains(object));
        weakHashSet.checkConsistency();
        weakHashSet.add(object);
        EXPECT_TRUE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.checkConsistency();
        weakHashSet.remove(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
    }

    {
        WeakHashSet<Derived> weakHashSet;
        const Derived object;
        EXPECT_FALSE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        weakHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        EXPECT_TRUE(weakHashSet.contains(object));
        weakHashSet.checkConsistency();
        weakHashSet.add(object);
        EXPECT_TRUE(weakHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 1u);
        weakHashSet.checkConsistency();
        weakHashSet.remove(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
    }
}

TEST(WTF_WeakPtr, WeakHashSetExpansion)
{
    unsigned initialCapacity;
    static constexpr unsigned maxLoadCap = 3;
    {
        WeakHashSet<Base> weakHashSet;
        Base object;
        EXPECT_EQ(s_baseWeakReferences, 0u);
        weakHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        initialCapacity = weakHashSet.capacity();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakHashSet<Base> weakHashSet;
        Vector<std::unique_ptr<Base>> objects;
        Vector<std::unique_ptr<Base>> otherObjects;

        EXPECT_EQ(weakHashSet.capacity(), 0u);
        EXPECT_TRUE(initialCapacity / maxLoadCap);
        for (unsigned i = 0; i < initialCapacity / maxLoadCap; ++i) {
            auto object = makeUnique<Base>();
            weakHashSet.add(*object);
            objects.append(WTF::move(object));
            otherObjects.append(makeUnique<Base>());
            weakHashSet.checkConsistency();
        }
        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), objects.size());
        for (unsigned i = 0; i < otherObjects.size(); ++i) {
            EXPECT_TRUE(weakHashSet.contains(*objects[i]));
            EXPECT_FALSE(weakHashSet.contains(*otherObjects[i]));
        }
        objects.clear();
        weakHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
        for (auto& object : otherObjects)
            EXPECT_FALSE(weakHashSet.contains(*object));
        for (auto& object : otherObjects) {
            weakHashSet.add(*object);
            weakHashSet.checkConsistency();
        }
        EXPECT_EQ(weakHashSet.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), otherObjects.size());
        for (auto& object : otherObjects)
            EXPECT_TRUE(weakHashSet.contains(*object));
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    for (unsigned i = 0; i < 10; ++i) {
        WeakHashSet<Base> weakHashSet;
        Vector<std::unique_ptr<Base>> objects;
        EXPECT_EQ(weakHashSet.capacity(), 0u);
        unsigned objectCount = initialCapacity * 2;
        for (unsigned i = 0; i < objectCount; ++i) {
            auto object = makeUnique<Base>();
            weakHashSet.add(*object);
            objects.append(WTF::move(object));
            weakHashSet.checkConsistency();
        }
        unsigned originalCapacity = weakHashSet.capacity();
        EXPECT_EQ(s_baseWeakReferences, objects.size());
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), objects.size());
        for (auto& object : objects)
            EXPECT_TRUE(weakHashSet.contains(*object));
        objects.clear();
        weakHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, objectCount);
        EXPECT_EQ(weakHashSet.capacity(), originalCapacity);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), 0u);
    }
}

TEST(WTF_WeakPtr, WeakHashSetisEmptyIgnoringNullReferences)
{
    {
        WeakHashSet<Base> weakHashSet;
        {
            Base object;
            EXPECT_EQ(s_baseWeakReferences, 0u);
            weakHashSet.add(object);
            EXPECT_FALSE(weakHashSet.isEmptyIgnoringNullReferences());
        }
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_TRUE(weakHashSet.isEmptyIgnoringNullReferences());
    }

    {
        WeakHashSet<Base> weakHashSet;
        Base object1;
        EXPECT_EQ(s_baseWeakReferences, 0u);
        weakHashSet.add(object1);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        {
            Base object2;
            weakHashSet.add(object2);
            EXPECT_FALSE(weakHashSet.isEmptyIgnoringNullReferences());
        }
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_FALSE(weakHashSet.isEmptyIgnoringNullReferences());
        weakHashSet.remove(object1);
        EXPECT_TRUE(weakHashSet.isEmptyIgnoringNullReferences());
    }

    {
        WeakHashSet<Base> weakHashSet;
        Vector<std::unique_ptr<Base>> objects;
        auto firstObject = makeUnique<Base>();
        weakHashSet.add(*firstObject);
        do {
            auto object = makeUnique<Base>();
            weakHashSet.add(*object);
            objects.append(WTF::move(object));
        } while (weakHashSet.begin().get() == firstObject.get());

        EXPECT_EQ(s_baseWeakReferences, objects.size() + 1);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), objects.size() + 1);
        EXPECT_FALSE(weakHashSet.isEmptyIgnoringNullReferences());
        firstObject = nullptr;
        EXPECT_FALSE(weakHashSet.isEmptyIgnoringNullReferences());
        EXPECT_EQ(s_baseWeakReferences, objects.size() + 1);
        EXPECT_EQ(computeSizeOfWeakHashSet(weakHashSet), objects.size());
    }
}

TEST(WTF_WeakPtr, WeakHashSetComputeSize)
{
    {
        WeakHashSet<Base> weakHashSet;
        {
            Base object;
            EXPECT_EQ(s_baseWeakReferences, 0u);
            weakHashSet.add(object);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_EQ(weakHashSet.computeSize(), 1u);
            weakHashSet.checkConsistency();
        }
        EXPECT_TRUE(weakHashSet.isEmptyIgnoringNullReferences());
        EXPECT_EQ(weakHashSet.computeSize(), 0u);
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_TRUE(weakHashSet.isEmptyIgnoringNullReferences());
        weakHashSet.checkConsistency();
    }

    {
        WeakHashSet<Base> weakHashSet;
        {
            Base object1;
            EXPECT_EQ(s_baseWeakReferences, 0u);
            weakHashSet.add(object1);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            {
                Base object2;
                weakHashSet.add(object2);
                EXPECT_EQ(s_baseWeakReferences, 2u);
                EXPECT_EQ(weakHashSet.computeSize(), 2u);
                weakHashSet.checkConsistency();
            }
            EXPECT_EQ(s_baseWeakReferences, 2u);
            EXPECT_EQ(weakHashSet.computeSize(), 1u);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            weakHashSet.checkConsistency();
            weakHashSet.remove(object1);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_EQ(weakHashSet.computeSize(), 0u);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            weakHashSet.checkConsistency();
        }
        EXPECT_EQ(s_baseWeakReferences, 0u);
        weakHashSet.checkConsistency();
    }

    while (1) {
        WeakHashSet<Base> weakHashSet;
        auto firstObject = makeUnique<Base>();
        auto lastObject = makeUnique<Base>();
        weakHashSet.add(*firstObject);
        weakHashSet.add(*lastObject);
        if (weakHashSet.begin().get() != firstObject.get())
            continue;
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(weakHashSet.computeSize(), 2u);
        EXPECT_EQ(s_baseWeakReferences, 2u);
        weakHashSet.checkConsistency();
        firstObject = nullptr;
        EXPECT_EQ(weakHashSet.computeSize(), 1u);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        weakHashSet.checkConsistency();
        lastObject = nullptr;
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(weakHashSet.computeSize(), 0u);
        EXPECT_EQ(s_baseWeakReferences, 0u);
        weakHashSet.checkConsistency();
        break;
    }

    {
        WeakHashSet<Base> weakHashSet;
        Vector<std::unique_ptr<Base>> objects;
        auto nonFirstObject = makeUnique<Base>();
        weakHashSet.add(*nonFirstObject);
        do {
            auto object = makeUnique<Base>();
            weakHashSet.add(*object);
            objects.append(WTF::move(object));
        } while (weakHashSet.begin().get() == nonFirstObject.get());

        unsigned objectsCount = objects.size();
        EXPECT_EQ(s_baseWeakReferences, objectsCount + 1);
        EXPECT_EQ(weakHashSet.computeSize(), objectsCount + 1);
        EXPECT_EQ(s_baseWeakReferences, objectsCount + 1);
        weakHashSet.checkConsistency();
        nonFirstObject = nullptr;
        EXPECT_EQ(weakHashSet.computeSize(), objectsCount);
        EXPECT_EQ(s_baseWeakReferences, objectsCount);
        weakHashSet.checkConsistency();
        objects.clear();
        EXPECT_EQ(s_baseWeakReferences, objectsCount);
        EXPECT_EQ(weakHashSet.computeSize(), 0u);
        EXPECT_EQ(s_baseWeakReferences, 0u);
    }
}

TEST(WTF_WeakPtr, WeakHashSetAmortizedCleanup)
{
    {
        WeakHashSet<Base> weakHashSet;
        Vector<std::unique_ptr<Base>> objects;
        EXPECT_EQ(s_baseWeakReferences, 0u);
        for (unsigned i = 0; i < 50; ++i) {
            objects.append(makeUnique<Base>());
            weakHashSet.add(*objects[i]);
        }
        EXPECT_EQ(s_baseWeakReferences, 50u);
        EXPECT_EQ(weakHashSet.computeSize(), 50u);
        EXPECT_FALSE(weakHashSet.hasNullReferences());
        for (unsigned i = 0; i < objects.size(); ++i) {
            if (!(i % 8))
                objects[i] = nullptr;
        }
        EXPECT_EQ(s_baseWeakReferences, 50u);
        EXPECT_TRUE(weakHashSet.hasNullReferences());
        for (unsigned i = 0; i < 3; ++i) {
            unsigned count = 0;
            for (auto& item : weakHashSet) {
                UNUSED_PARAM(item);
                count++;
            } 
            EXPECT_EQ(count, 43u);
        }
        EXPECT_EQ(s_baseWeakReferences, 50u);
        EXPECT_TRUE(weakHashSet.hasNullReferences());
        Base object;
        weakHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 44u);
        EXPECT_FALSE(weakHashSet.hasNullReferences());
    }

    {
        WeakHashSet<Base> weakHashSet;
        Vector<std::unique_ptr<Base>> objects;
        EXPECT_EQ(s_baseWeakReferences, 0u);
        for (unsigned i = 0; i < 50; ++i) {
            objects.append(makeUnique<Base>());
            weakHashSet.add(*objects[i]);
        }
        EXPECT_EQ(s_baseWeakReferences, 50u);
        EXPECT_EQ(weakHashSet.computeSize(), 50u);
        EXPECT_FALSE(weakHashSet.hasNullReferences());
        Vector<Base*> objectsInIterationOrder;
        for (auto& item : weakHashSet)
            objectsInIterationOrder.append(&item);
        for (unsigned i = 0; i < 50; ++i) {
            if (i < 40)
                continue;
            auto* objectToRemove = objectsInIterationOrder[i];
            for (unsigned j = 0; j < 50; ++j) {
                if (objects[j].get() == objectToRemove)
                    objects[j] = nullptr;
            }
        }
        EXPECT_EQ(s_baseWeakReferences, 50u);
        for (unsigned i = 0; i < 5; ++i)
            EXPECT_TRUE(weakHashSet.hasNullReferences());
        EXPECT_EQ(s_baseWeakReferences, 50u);
        Base object;
        weakHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 41u);
        EXPECT_FALSE(weakHashSet.hasNullReferences());
    }
}

template <typename T, typename U>
unsigned computeSizeOfWeakHashMap(const WeakHashMap<T, U>& map)
{
    unsigned size = 0;
    for (auto item : map) {
        UNUSED_PARAM(item);
        size++;
    }
    return size;
}

struct ValueObject : public RefCounted<ValueObject> {
public:

    static Ref<ValueObject> create(int value) { return adoptRef(*new ValueObject(value)); }

    ~ValueObject() { ASSERT(s_count); --s_count; }

    int value;

    static unsigned s_count;

private:
    ValueObject(unsigned short value)
        : value(value)
    {
        ++s_count;
    }
};

unsigned ValueObject::s_count = 0;

TEST(WTF_WeakPtr, WeakHashMapBasic)
{
    {
        WeakHashMap<Base, int> weakHashMap;
        Base object;
        EXPECT_FALSE(weakHashMap.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        weakHashMap.set(object, 34);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), 34);
        weakHashMap.add(object, 12);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), 34);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.set(object, 7);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), 7);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakHashMap<Base, int> weakHashMap;
        {
            Base object;
            EXPECT_FALSE(weakHashMap.contains(object));
            EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
            EXPECT_EQ(s_baseWeakReferences, 0u);
            weakHashMap.add(object, 7);
            EXPECT_TRUE(weakHashMap.contains(object));
            EXPECT_EQ(weakHashMap.get(object), 7);
            EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
            EXPECT_EQ(s_baseWeakReferences, 1u);
        }
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        weakHashMap.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakHashMap<Base, int> weakHashMap;
        {
            Base object1;
            Base object2;
            EXPECT_FALSE(weakHashMap.contains(object1));
            EXPECT_EQ(weakHashMap.get(object1), 0);
            EXPECT_FALSE(weakHashMap.contains(object2));
            EXPECT_EQ(weakHashMap.get(object2), 0);
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
            weakHashMap.add(object1, 3);
            EXPECT_TRUE(weakHashMap.contains(object1));
            EXPECT_EQ(weakHashMap.get(object1), 3);
            EXPECT_FALSE(weakHashMap.contains(object2));
            EXPECT_EQ(weakHashMap.get(object2), 0);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
            weakHashMap.add(object2, 24);
            EXPECT_TRUE(weakHashMap.contains(object1));
            EXPECT_EQ(weakHashMap.get(object1), 3);
            EXPECT_TRUE(weakHashMap.contains(object2));
            EXPECT_EQ(weakHashMap.get(object2), 24);
            EXPECT_EQ(s_baseWeakReferences, 2u);
            EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 2u);
            weakHashMap.remove(object1);
            EXPECT_FALSE(weakHashMap.contains(object1));
            EXPECT_EQ(weakHashMap.get(object1), 0);
            EXPECT_TRUE(weakHashMap.contains(object2));
            EXPECT_EQ(weakHashMap.get(object2), 24);
            EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        }
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        weakHashMap.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakHashMap<Base, Ref<ValueObject>> weakHashMap;
        Base object1;
        Base object2;
        Base object3;
        EXPECT_FALSE(weakHashMap.contains(object1));
        EXPECT_EQ(weakHashMap.get(object1), nullptr);
        EXPECT_FALSE(weakHashMap.contains(object2));
        EXPECT_EQ(weakHashMap.get(object2), nullptr);
        EXPECT_FALSE(weakHashMap.contains(object3));
        EXPECT_EQ(weakHashMap.get(object3), nullptr);
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        weakHashMap.add(object1, ValueObject::create(100));
        weakHashMap.add(object2, ValueObject::create(200));
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(ValueObject::s_count, 2u);
        EXPECT_TRUE(weakHashMap.contains(object1));
        EXPECT_EQ(weakHashMap.get(object1)->value, 100);
        EXPECT_TRUE(weakHashMap.contains(object2));
        EXPECT_EQ(weakHashMap.get(object2)->value, 200);
        EXPECT_FALSE(weakHashMap.contains(object3));
        EXPECT_EQ(weakHashMap.get(object3), nullptr);
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(ValueObject::s_count, 2u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 2u);
        weakHashMap.remove(object1);
        EXPECT_FALSE(weakHashMap.contains(object1));
        EXPECT_EQ(weakHashMap.get(object1), nullptr);
        EXPECT_TRUE(weakHashMap.contains(object2));
        EXPECT_EQ(weakHashMap.get(object2)->value, 200);
        EXPECT_FALSE(weakHashMap.contains(object3));
        EXPECT_EQ(weakHashMap.get(object3), nullptr);
        EXPECT_EQ(s_baseWeakReferences, 2u); // Because object2 holds onto WeakReference.
        EXPECT_EQ(ValueObject::s_count, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.remove(object3);
        EXPECT_FALSE(weakHashMap.contains(object1));
        EXPECT_EQ(weakHashMap.get(object1), nullptr);
        EXPECT_TRUE(weakHashMap.contains(object2));
        EXPECT_EQ(weakHashMap.get(object2)->value, 200);
        EXPECT_FALSE(weakHashMap.contains(object3));
        EXPECT_EQ(weakHashMap.get(object3), nullptr);
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(ValueObject::s_count, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.add(object2, ValueObject::create(210));
        EXPECT_FALSE(weakHashMap.contains(object1));
        EXPECT_EQ(weakHashMap.get(object1), nullptr);
        EXPECT_TRUE(weakHashMap.contains(object2));
        EXPECT_EQ(weakHashMap.get(object2)->value, 200);
        EXPECT_FALSE(weakHashMap.contains(object3));
        EXPECT_EQ(weakHashMap.get(object3), nullptr);
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(ValueObject::s_count, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.set(object2, ValueObject::create(220));
        EXPECT_FALSE(weakHashMap.contains(object1));
        EXPECT_EQ(weakHashMap.get(object1), nullptr);
        EXPECT_TRUE(weakHashMap.contains(object2));
        EXPECT_EQ(weakHashMap.get(object2)->value, 220);
        EXPECT_FALSE(weakHashMap.contains(object3));
        EXPECT_EQ(weakHashMap.get(object3), nullptr);
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(ValueObject::s_count, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.remove(object2);
        EXPECT_FALSE(weakHashMap.contains(object1));
        EXPECT_EQ(weakHashMap.get(object1), nullptr);
        EXPECT_FALSE(weakHashMap.contains(object2));
        EXPECT_EQ(weakHashMap.get(object2), nullptr);
        EXPECT_FALSE(weakHashMap.contains(object3));
        EXPECT_EQ(weakHashMap.get(object3), nullptr);
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_EQ(ValueObject::s_count, 0u);
        weakHashMap.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);
    EXPECT_EQ(ValueObject::s_count, 0u);
}

TEST(WTF_WeakPtr, WeakHashMapConstObjects)
{
    {
        WeakHashMap<Base, Ref<ValueObject>> weakHashMap;
        const Base object;
        EXPECT_FALSE(weakHashMap.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        weakHashMap.add(object, ValueObject::create(3));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object)->value, 3);
        weakHashMap.checkConsistency();
        weakHashMap.add(object, ValueObject::create(7));
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object)->value, 3);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.checkConsistency();
        weakHashMap.set(object, ValueObject::create(11));
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object)->value, 11);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.checkConsistency();
        weakHashMap.remove(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        EXPECT_FALSE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), nullptr);
    }

    {
        WeakHashMap<Base, String> weakHashMap;
        const Derived object;
        EXPECT_FALSE(weakHashMap.contains(object));
        EXPECT_TRUE(weakHashMap.get(object).isNull());
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        weakHashMap.add(object, "hello"_s);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_STREQ(weakHashMap.get(object).utf8().data(), "hello");
        weakHashMap.checkConsistency();
        weakHashMap.add(object, "world"_s);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_STREQ(weakHashMap.get(object).utf8().data(), "hello");
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.checkConsistency();
        weakHashMap.set(object, "WebKit"_s);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_STREQ(weakHashMap.get(object).utf8().data(), "WebKit");
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.checkConsistency();
        weakHashMap.remove(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        EXPECT_FALSE(weakHashMap.contains(object));
        EXPECT_TRUE(weakHashMap.get(object).isNull());
    }

    {
        WeakHashMap<Base, int> weakHashMap;
        const Derived object;
        EXPECT_FALSE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), 0);
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        weakHashMap.checkConsistency();
        weakHashMap.add(object, 3);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), 3);
        weakHashMap.checkConsistency();
        weakHashMap.add(object, 7);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), 3);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.checkConsistency();
        weakHashMap.set(object, 11);
        EXPECT_TRUE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), 11);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 1u);
        weakHashMap.checkConsistency();
        weakHashMap.remove(object);
        EXPECT_FALSE(weakHashMap.contains(object));
        EXPECT_EQ(weakHashMap.get(object), 0);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
    }
}

TEST(WTF_WeakPtr, WeakHashMapRemoveIterator)
{
    WeakHashMap<Base, int> weakHashMap;
    Vector<std::unique_ptr<Base>> objects;
    for (unsigned i = 0; i < 13; ++i) {
        auto object = makeUnique<Base>();
        weakHashMap.add(*object, 0);
        objects.append(WTF::move(object));
    }
    while (!objects.isEmpty()) {
        auto it = weakHashMap.find(*objects.last());
        objects.removeAt(0);
        weakHashMap.remove(it);
        weakHashMap.checkConsistency();
    }
}

TEST(WTF_WeakPtr, WeakHashMapExpansion)
{
    unsigned initialCapacity;
    static constexpr unsigned maxLoadCap = 3;
    {
        WeakHashMap<Base, int> weakHashMap;
        Base object;
        EXPECT_EQ(s_baseWeakReferences, 0u);
        weakHashMap.add(object, 1);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        initialCapacity = weakHashMap.capacity();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    for (unsigned testCount = 0; testCount < 10; ++testCount) {
        WeakHashMap<Base, unsigned> weakHashMap;
        Vector<std::unique_ptr<Base>> objects;
        Vector<std::unique_ptr<Base>> otherObjects;

        EXPECT_EQ(weakHashMap.capacity(), 0u);
        EXPECT_TRUE(initialCapacity / maxLoadCap);
        for (unsigned i = 0; i < initialCapacity / maxLoadCap; ++i) {
            auto object = makeUnique<Base>();
            weakHashMap.add(*object, i);
            objects.append(WTF::move(object));
            otherObjects.append(makeUnique<Base>());
            weakHashMap.checkConsistency();
        }
        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
        EXPECT_EQ(weakHashMap.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), objects.size());
        for (unsigned i = 0; i < otherObjects.size(); ++i) {
            EXPECT_TRUE(weakHashMap.contains(*objects[i]));
            EXPECT_EQ(weakHashMap.get(*objects[i]), i);
            EXPECT_FALSE(weakHashMap.contains(*otherObjects[i]));
        }
        objects.clear();
        weakHashMap.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
        EXPECT_EQ(weakHashMap.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
        for (auto& object : otherObjects)
            EXPECT_FALSE(weakHashMap.contains(*object));
        unsigned i = 100;
        for (auto& object : otherObjects) {
            weakHashMap.add(*object, i);
            weakHashMap.checkConsistency();
            ++i;
        }
        EXPECT_EQ(weakHashMap.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), otherObjects.size());
        i = 100;
        for (auto& object : otherObjects) {
            EXPECT_TRUE(weakHashMap.contains(*object));
            EXPECT_EQ(weakHashMap.get(*object), i);
            ++i;
        }
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    for (unsigned testCount = 0; testCount < 10; ++testCount) {
        WeakHashMap<Base, Ref<ValueObject>> weakHashMap;
        Vector<std::unique_ptr<Base>> objects;
        EXPECT_EQ(weakHashMap.capacity(), 0u);
        unsigned objectCount = initialCapacity * 2;
        for (unsigned i = 0; i < objectCount; ++i) {
            auto object = makeUnique<Base>();
            weakHashMap.set(*object, ValueObject::create(100 + i));
            objects.append(WTF::move(object));
            weakHashMap.checkConsistency();
        }
        unsigned originalCapacity = weakHashMap.capacity();
        EXPECT_EQ(s_baseWeakReferences, objects.size());
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), objects.size());

        int i = 100;
        for (auto& object : objects) {
            EXPECT_TRUE(weakHashMap.contains(*object));
            EXPECT_EQ(weakHashMap.get(*object)->value, i);
            ++i;
        }

        objects.clear();
        weakHashMap.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, objectCount);
        EXPECT_EQ(weakHashMap.capacity(), originalCapacity);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), 0u);
    }
}

TEST(WTF_WeakPtr, WeakHashMapIsEmptyIgnoringNullReferences)
{
    {
        WeakHashMap<Base, int> weakHashMap;
        {
            Base object;
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_TRUE(weakHashMap.isEmptyIgnoringNullReferences());
            weakHashMap.add(object, 1);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_FALSE(weakHashMap.isEmptyIgnoringNullReferences());
            weakHashMap.checkConsistency();
            weakHashMap.set(object, 2);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_FALSE(weakHashMap.isEmptyIgnoringNullReferences());
            weakHashMap.checkConsistency();
            weakHashMap.add(object, 3);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_FALSE(weakHashMap.isEmptyIgnoringNullReferences());
            weakHashMap.checkConsistency();
        }
        EXPECT_TRUE(weakHashMap.hasNullReferences());
        EXPECT_TRUE(weakHashMap.isEmptyIgnoringNullReferences());
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        weakHashMap.checkConsistency();
    }

    {
        WeakHashMap<Base, int> weakHashMap;
        Base object1;
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        EXPECT_TRUE(weakHashMap.isEmptyIgnoringNullReferences());
        weakHashMap.checkConsistency();
        weakHashMap.add(object1, 100);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        EXPECT_FALSE(weakHashMap.isEmptyIgnoringNullReferences());
        weakHashMap.checkConsistency();
        {
            Base object2;
            weakHashMap.add(object2, 200);
            EXPECT_EQ(s_baseWeakReferences, 2u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_FALSE(weakHashMap.isEmptyIgnoringNullReferences());
            weakHashMap.checkConsistency();
        }
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_TRUE(weakHashMap.hasNullReferences());
        EXPECT_FALSE(weakHashMap.isEmptyIgnoringNullReferences());
        weakHashMap.checkConsistency();
        weakHashMap.remove(object1);
        EXPECT_TRUE(weakHashMap.isEmptyIgnoringNullReferences());
        weakHashMap.checkConsistency();
    }

    {
        WeakHashMap<Base, Ref<ValueObject>> weakHashMap;
        Vector<std::unique_ptr<Base>> objects;
        auto firstObject = makeUnique<Base>();
        int value = 1;
        weakHashMap.set(*firstObject, ValueObject::create(value++));
        do {
            auto object = makeUnique<Base>();
            weakHashMap.set(*object, ValueObject::create(value++));
            objects.append(WTF::move(object));
        } while (&weakHashMap.begin()->key == firstObject.get());

        EXPECT_EQ(ValueObject::s_count, objects.size() + 1);
        EXPECT_EQ(s_baseWeakReferences, objects.size() + 1);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), objects.size() + 1);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        EXPECT_FALSE(weakHashMap.isEmptyIgnoringNullReferences());
        firstObject = nullptr;
        EXPECT_TRUE(weakHashMap.hasNullReferences());
        EXPECT_FALSE(weakHashMap.isEmptyIgnoringNullReferences());
        EXPECT_EQ(s_baseWeakReferences, objects.size() + 1);
        EXPECT_EQ(computeSizeOfWeakHashMap(weakHashMap), objects.size());
        objects.clear();
        EXPECT_TRUE(weakHashMap.hasNullReferences());
        EXPECT_TRUE(weakHashMap.isEmptyIgnoringNullReferences());
        weakHashMap.clear();
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        EXPECT_TRUE(weakHashMap.isEmptyIgnoringNullReferences());
    }
}

TEST(WTF_WeakPtr, WeakHashMapRemoveNullReferences)
{
    {
        WeakHashMap<Base, int> weakHashMap;
        {
            Base object;
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            weakHashMap.removeNullReferences();
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            weakHashMap.add(object, 1);
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            weakHashMap.removeNullReferences();
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            weakHashMap.set(object, 2);
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            weakHashMap.removeNullReferences();
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            weakHashMap.set(object, 3);
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
        }
        weakHashMap.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_TRUE(weakHashMap.hasNullReferences());

        weakHashMap.removeNullReferences();
        weakHashMap.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
    }

    {
        WeakHashMap<Base, RefPtr<ValueObject>> weakHashMap;
        Vector<std::unique_ptr<Derived>> objects;

        for (unsigned i = 0; i < 50; ++i) {
            auto key = makeUnique<Derived>();
            weakHashMap.add(*key, ValueObject::create(i + 100));
            objects.append(WTF::move(key));
        }
        EXPECT_EQ(ValueObject::s_count, 50U);
        EXPECT_EQ(s_baseWeakReferences, 50U);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        weakHashMap.checkConsistency();

        weakHashMap.removeNullReferences();
        EXPECT_EQ(ValueObject::s_count, 50U);
        EXPECT_EQ(s_baseWeakReferences, 50U);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        weakHashMap.checkConsistency();

        for (unsigned i = 0; i < 50; ++i) {
            if (i % 2)
                objects[i] = nullptr;
        }

        weakHashMap.removeNullReferences();
        EXPECT_EQ(ValueObject::s_count, 25U);
        EXPECT_EQ(s_baseWeakReferences, 25U);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        weakHashMap.checkConsistency();

        bool seen[50] = { false };
        for (auto keyValue : weakHashMap) {
            int rawValue = keyValue.value->value;
            EXPECT_TRUE(rawValue >= 100 && rawValue < 150);
            EXPECT_EQ((rawValue - 100) % 2, 0);
            unsigned index = rawValue - 100;
            EXPECT_FALSE(seen[index]);
            seen[index] = true;
            EXPECT_EQ(&keyValue.key, objects[index].get());
            EXPECT_EQ(weakHashMap.get(keyValue.key), keyValue.value.get());
        }
        for (unsigned i = 0; i < 50; ++i) {
            bool shouldBePresent = !(i % 2);
            EXPECT_EQ(seen[i], shouldBePresent);
        }

        objects.clear();
        weakHashMap.removeNullReferences();
        EXPECT_EQ(ValueObject::s_count, 0U);
        EXPECT_EQ(s_baseWeakReferences, 0U);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        weakHashMap.checkConsistency();
    }
}

template <typename KeyType, typename ValueType, typename Map>
auto collectKeyValuePairsUsingIterators(Map& map)
{
    HashSet<std::pair<KeyType, ValueType>> pairs;
    for (auto it = map.begin(); it != map.end(); ++it) {
        std::pair keyValuePair { &it->key, it.get()->value };
        EXPECT_FALSE(pairs.contains(keyValuePair));
        pairs.add(keyValuePair);
    }
    return pairs;
};

TEST(WTF_WeakPtr, WeakHashMapIterators)
{
    {
        WeakHashMap<Base, int> weakHashMap;
        {
            Base object1;
            Derived object2;
            Base object3;
            Derived object4;
            weakHashMap.checkConsistency();
            weakHashMap.add(object1, 1);
            weakHashMap.add(object2, 2);
            weakHashMap.add(object3, 3);
            weakHashMap.add(object4, 4);
            EXPECT_EQ(s_baseWeakReferences, 4u);
            EXPECT_EQ(weakHashMap.computeSize(), 4u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            const auto& constMap = weakHashMap;
            auto pairs = collectKeyValuePairsUsingIterators<Base*, int>(constMap);
            EXPECT_EQ(pairs.size(), 4u);
            EXPECT_TRUE(pairs.contains(std::pair { &object1, 1 }));
            EXPECT_TRUE(pairs.contains(std::pair { &object2, 2 }));
            EXPECT_TRUE(pairs.contains(std::pair { &object3, 3 }));
            EXPECT_TRUE(pairs.contains(std::pair { &object4, 4 }));

            weakHashMap.remove(object2);
            weakHashMap.remove(object3);
            EXPECT_EQ(s_baseWeakReferences, 4u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            pairs = collectKeyValuePairsUsingIterators<Base*, int>(constMap);
            EXPECT_EQ(pairs.size(), 2u);
            EXPECT_TRUE(pairs.contains(std::pair { &object1, 1 }));
            EXPECT_FALSE(pairs.contains(std::pair { &object2, 2 }));
            EXPECT_FALSE(pairs.contains(std::pair { &object3, 3 }));
            EXPECT_TRUE(pairs.contains(std::pair { &object4, 4 }));
        }
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_TRUE(weakHashMap.hasNullReferences());

        auto pairs = collectKeyValuePairsUsingIterators<Base*, int>(weakHashMap);
        EXPECT_EQ(pairs.size(), 0u);
    }

    {
        WeakHashMap<Base, int> weakHashMap;
        {
            Vector<std::unique_ptr<Base>> objects;
            for (unsigned i = 0; i < 50; ++i) {
                if (i % 2)
                    objects.append(makeUnique<Derived>());
                else
                    objects.append(makeUnique<Base>());
                weakHashMap.set(*objects.last(), i);
            }
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_EQ(weakHashMap.computeSize(), 50u);

            for (auto it = weakHashMap.begin(); it != weakHashMap.end(); ++it) {
                auto keyValue = *it;
                if (keyValue.value % 6)
                    continue;
                keyValue.value *= 51;
            }

            weakHashMap.removeIf([](auto& keyValue) { return !(keyValue.value % 5); });
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());

            auto pairs = collectKeyValuePairsUsingIterators<Base*, int>(weakHashMap);
            ASSERT(pairs.size(), 40U);
            for (unsigned i = 0; i < 50; ++i) {
                if (!(i % 5))
                    EXPECT_TRUE(std::ranges::all_of(pairs, [&](auto& item) { return item.first != objects[i].get(); }));
                else if (!(i % 6))
                    EXPECT_TRUE(pairs.contains(std::pair { objects[i].get(), i * 51 }));
                else
                    EXPECT_TRUE(pairs.contains(std::pair { objects[i].get(), i }));
            }

            for (unsigned i = 0; i < 50; ++i) {
                if (!(i % 5) || !(i % 9))
                    objects[i] = nullptr;
            }
            EXPECT_EQ(s_baseWeakReferences, 40u);
            weakHashMap.checkConsistency();

            pairs = collectKeyValuePairsUsingIterators<Base*, int>(weakHashMap);
            ASSERT(pairs.size(), 36U);
            for (unsigned i = 0; i < 50; ++i) {
                if (!(i % 5) || !(i % 9))
                    EXPECT_TRUE(std::ranges::all_of(pairs, [&](auto& item) { return item.first != objects[i].get(); }));
                else if (!(i % 6))
                    EXPECT_TRUE(pairs.contains(std::pair { objects[i].get(), i * 51 }));
                else
                    EXPECT_TRUE(pairs.contains(std::pair { objects[i].get(), i }));
            }
            weakHashMap.removeNullReferences();
            EXPECT_EQ(s_baseWeakReferences, 36u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            ASSERT(pairs.size(), weakHashMap.computeSize());
            weakHashMap.checkConsistency();
        }
        EXPECT_EQ(s_baseWeakReferences, 36u);
        weakHashMap.checkConsistency();
        EXPECT_TRUE(weakHashMap.hasNullReferences());

        auto pairs = collectKeyValuePairsUsingIterators<Base*, int>(weakHashMap);
        EXPECT_EQ(pairs.size(), 0u);

        EXPECT_EQ(s_baseWeakReferences, 36u);
        weakHashMap.checkConsistency();
        EXPECT_TRUE(weakHashMap.hasNullReferences());
    }

    {
        WeakHashMap<Base, RefPtr<ValueObject>> weakHashMap;
        {
            Vector<std::pair<std::unique_ptr<Base>, RefPtr<ValueObject>>> objects;
            for (unsigned i = 0; i < 50; ++i) {
                if (i % 2)
                    objects.append(std::pair { makeUnique<Derived>(), ValueObject::create(i * 83) });
                else
                    objects.append(std::pair { makeUnique<Base>(), ValueObject::create(i) });
                objects.last().first->dummy = 0;
                if (i < 25)
                    weakHashMap.add(*objects.last().first, objects.last().second);
            }
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 25u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_EQ(weakHashMap.computeSize(), 25u);

            for (unsigned i = 0; i < 50; ++i) {
                auto it = weakHashMap.find(*objects[i].first);
                if (i < 25) {
                    EXPECT_TRUE(it != weakHashMap.end());
                    EXPECT_EQ(it->key.dummy, 0);
                    if (i % 9)
                        continue;
                } else
                    EXPECT_TRUE(it == weakHashMap.end());
                weakHashMap.remove(it);
                weakHashMap.checkConsistency();
            }

            EXPECT_EQ(s_baseWeakReferences, 25u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_EQ(weakHashMap.computeSize(), 22u);
            for (int i = 0; i < 25; ++i) {
                auto it = weakHashMap.find(*objects[i].first);
                if (!(i % 9)) {
                    EXPECT_TRUE(it == weakHashMap.end());
                    continue;
                }

                EXPECT_EQ(&it.get()->key, objects[i].first.get());
                EXPECT_EQ(it.get()->key.dummy, 0);
                if (i % 2) {
                    it.get()->key.dummy = i * 11;
                    EXPECT_EQ(it.get()->value->value, i * 83);
                } else
                    EXPECT_EQ(it.get()->value->value, i);

                if (!(i % 4))
                    objects[i].first = nullptr;
            }

            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 25u);
            EXPECT_TRUE(weakHashMap.hasNullReferences());
            for (int i = 0; i < 25; ++i) {
                if (!(i % 4))
                    continue;
                auto it = weakHashMap.find(*objects[i].first);
                if (!(i % 9)) {
                    EXPECT_TRUE(it == weakHashMap.end());
                    continue;
                }
                EXPECT_EQ(&(*it).key, objects[i].first.get());
                if (i % 2) {
                    EXPECT_EQ((*it).key.dummy, i * 11);
                    EXPECT_EQ((*it).value->value, i * 83);
                } else {
                    EXPECT_EQ((*it).key.dummy, 0);
                    it->key.dummy = i * 31;
                    EXPECT_EQ((*it).value->value, i);
                }
            }
            weakHashMap.checkConsistency();
            EXPECT_EQ(weakHashMap.computeSize(), 16u);
            for (int i = 0; i < 25; ++i) {
                if (!(i % 4))
                    continue;
                auto it = weakHashMap.find(*objects[i].first);
                if (!(i % 9)) {
                    EXPECT_TRUE(it == weakHashMap.end());
                    continue;
                }
                EXPECT_EQ(&it->key, objects[i].first.get());
                auto keyValue = it.get();
                if (i % 2) {
                    EXPECT_EQ(keyValue->key.dummy, i * 11);
                    EXPECT_EQ(keyValue->value->value, i * 83);
                } else {
                    EXPECT_EQ((*keyValue).key.dummy, i * 31);
                    EXPECT_EQ((*keyValue).value->value, i);
                }
            }
        }
        EXPECT_EQ(s_baseWeakReferences, 16u);
        EXPECT_TRUE(weakHashMap.hasNullReferences());
        auto pairs = collectKeyValuePairsUsingIterators<Base*, RefPtr<ValueObject>>(weakHashMap);
        EXPECT_EQ(pairs.size(), 0U);
        weakHashMap.removeNullReferences();
        EXPECT_FALSE(weakHashMap.hasNullReferences());
        EXPECT_EQ(s_baseWeakReferences, 0U);
    }
}

TEST(WTF_WeakPtr, WeakHashMapAmortizedCleanup)
{
    {
        WeakHashMap<Base, int> weakHashMap;
        {
            Vector<std::unique_ptr<Base>> objects;
            for (unsigned i = 0; i < 50; ++i) {
                if (i % 2)
                    objects.append(makeUnique<Derived>());
                else
                    objects.append(makeUnique<Base>());
                weakHashMap.set(*objects.last(), i);
            }
            for (unsigned i = 0; i < 4; ++i)
                collectKeyValuePairsUsingIterators<Base*, int>(weakHashMap);
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_EQ(weakHashMap.computeSize(), 50u);
            
            for (unsigned i = 0; i < 50; ++i) {
                if (!(i % 5))
                    objects[i] = nullptr;
            }
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_TRUE(weakHashMap.hasNullReferences());

            for (unsigned i = 0; i < 4; ++i)
                collectKeyValuePairsUsingIterators<Base*, int>(weakHashMap);

            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_TRUE(weakHashMap.hasNullReferences());

            for (unsigned i = 0; i < 50; ++i) {
                if (!(i % 9))
                    objects[i] = nullptr;
            }

            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_TRUE(weakHashMap.hasNullReferences());

            for (unsigned i = 0; i < 4; ++i)
                collectKeyValuePairsUsingIterators<Base*, int>(weakHashMap);

            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_TRUE(weakHashMap.hasNullReferences());
        }
    }

    {
        WeakHashMap<Base, Ref<ValueObject>> weakHashMap;
        {
            Vector<std::unique_ptr<Base>> objects;
            for (unsigned i = 0; i < 50; ++i) {
                objects.append(makeUnique<Derived>());
                weakHashMap.set(*objects.last(), ValueObject::create(i));
            }
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_EQ(ValueObject::s_count, 50u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_EQ(weakHashMap.computeSize(), 50u);
            
            for (unsigned i = 0; i < 50; ++i) {
                if (!(i % 7))
                    objects[i] = nullptr;
            }
            weakHashMap.checkConsistency();
            EXPECT_TRUE(weakHashMap.hasNullReferences());
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_EQ(ValueObject::s_count, 50u);

            for (unsigned i = 0; i < 10; ++i) {
                for (auto& ptr : objects) {
                    if (!ptr)
                        continue;
                    auto it = weakHashMap.find(*ptr);
                    EXPECT_TRUE(it != weakHashMap.end());
                }
            }
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_EQ(ValueObject::s_count, 50u);
            EXPECT_TRUE(weakHashMap.hasNullReferences());

            for (unsigned i = 0; i < 50; ++i) {
                if (!(i % 3))
                    objects[i] = nullptr;
            }
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_EQ(ValueObject::s_count, 50u);
            EXPECT_TRUE(weakHashMap.hasNullReferences());

            for (unsigned i = 0; i < 4; ++i) {
                int objectIndex = 0;
                for (auto& ptr : objects) {
                    if (ptr) {
                        auto result = weakHashMap.add(*ptr, ValueObject::create(objectIndex * 51));
                        EXPECT_EQ(result.iterator->value->value, objectIndex);
                    }
                    ++objectIndex;
                }
            }
            weakHashMap.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 28u);
            EXPECT_EQ(ValueObject::s_count, 28u);
            EXPECT_FALSE(weakHashMap.hasNullReferences());
            EXPECT_EQ(weakHashMap.computeSize(), 28u);
        }
        weakHashMap.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 28u);
        EXPECT_EQ(ValueObject::s_count, 28u);
        EXPECT_TRUE(weakHashMap.hasNullReferences());

        EXPECT_TRUE(weakHashMap.isEmptyIgnoringNullReferences());
        weakHashMap.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(ValueObject::s_count, 0u);
        EXPECT_FALSE(weakHashMap.hasNullReferences());
    }
}

TEST(WTF_WeakPtr, WeakHashMap_iterator_destruction)
{
    constexpr unsigned objectCount = 10;
    WeakHashMap<Base, unsigned> weakHashMap;
    Vector<std::unique_ptr<Base>> objects;
    objects.reserveInitialCapacity(objectCount);
    for (unsigned i = 0; i < objectCount; ++i) {
        auto object = makeUnique<Base>();
        weakHashMap.add(*object, i);
        objects.append(WTF::move(object));
    }

    auto a = objects.takeLast();
    auto b = objects.takeLast();

    auto aIterator = weakHashMap.find(*a);
    objects.clear();
    for (unsigned i = 0; i < 20; ++i) {
        auto bIterator = weakHashMap.find(*b);
        EXPECT_EQ(bIterator->value, objectCount - 2);
        EXPECT_EQ(aIterator->value, objectCount - 1);
    }
}

TEST(WTF_WeakPtr, ListHashSetBoundedGrowth)
{
    ListHashSet<WeakPtr<BaseObjectWithRefAndWeakPtr>> set;
    for (size_t i = 0; i < 128; ++i)
        set.add(BaseObjectWithRefAndWeakPtr::create().get());

    size_t entryCount = 0;
    for (auto entry : set)
        ++entryCount;

    EXPECT_LT(entryCount, 16u);
}

template <typename T>
unsigned computeSizeOfWeakListHashSet(const WeakListHashSet<T>& set)
{
    unsigned size = 0;
    for (auto& item : set) {
        UNUSED_PARAM(item);
        size++;
    }
    return size;
}

TEST(WTF_WeakPtr, WeakListHashSetBasic)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        Base object;
        EXPECT_FALSE(weakListHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        weakListHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
        EXPECT_TRUE(weakListHashSet.contains(object));
        weakListHashSet.add(object);
        weakListHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
        EXPECT_TRUE(weakListHashSet.contains(object));
        weakListHashSet.clear();
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        EXPECT_FALSE(weakListHashSet.contains(object));
        weakListHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object;
            EXPECT_FALSE(weakListHashSet.contains(object));
            EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
            EXPECT_EQ(s_baseWeakReferences, 0u);
            weakListHashSet.add(object);
            EXPECT_TRUE(weakListHashSet.contains(object));
            EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
            EXPECT_EQ(s_baseWeakReferences, 1u);
        }
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        weakListHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object1;
            Base object2;
            EXPECT_FALSE(weakListHashSet.contains(object1));
            EXPECT_FALSE(weakListHashSet.contains(object2));
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
            weakListHashSet.add(object1);
            EXPECT_TRUE(weakListHashSet.contains(object1));
            EXPECT_FALSE(weakListHashSet.contains(object2));
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
            weakListHashSet.add(object2);
            EXPECT_TRUE(weakListHashSet.contains(object1));
            EXPECT_TRUE(weakListHashSet.contains(object2));
            EXPECT_EQ(s_baseWeakReferences, 2u);
            EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 2u);
            {
                Vector<Base*> objectsInIterationOrder;
                for (auto& object : weakListHashSet)
                    objectsInIterationOrder.append(&object);
                EXPECT_EQ(objectsInIterationOrder[0], &object1);
                EXPECT_EQ(objectsInIterationOrder[1], &object2);
            }
            weakListHashSet.remove(object1);
            EXPECT_FALSE(weakListHashSet.contains(object1));
            EXPECT_TRUE(weakListHashSet.contains(object2));
            EXPECT_EQ(s_baseWeakReferences, 2u);
            EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
        }
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        weakListHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        WeakListHashSet<Base> weakListHashSet;
        Vector<std::unique_ptr<Base>> objects;
        for (unsigned i = 0; i < 50; ++i) {
            auto object = makeUnique<Base>();
            weakListHashSet.add(*object);
            objects.append(WTF::move(object));
        }

        unsigned i = 0;
        for (auto& item : weakListHashSet) {
            EXPECT_EQ(objects[i].get(), &item);
            ++i;
        }

        for (unsigned i = 0; i < 50; ++i)
            weakListHashSet.add(*objects[50 - i - 1]);

        i = 0;
        for (auto& item : weakListHashSet) {
            EXPECT_EQ(objects[i].get(), &item);
            ++i;
        }
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);
    EXPECT_EQ(ValueObject::s_count, 0u);
}

TEST(WTF_WeakPtr, WeakListHashMapConstObjects)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        const Base object;
        EXPECT_FALSE(weakListHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        weakListHashSet.add(object);
        weakListHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
        EXPECT_TRUE(weakListHashSet.contains(object));
        weakListHashSet.checkConsistency();
        weakListHashSet.add(object);
        EXPECT_TRUE(weakListHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
        weakListHashSet.checkConsistency();
        weakListHashSet.remove(object);
        weakListHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        EXPECT_FALSE(weakListHashSet.contains(object));
    }

    {
        WeakListHashSet<Base> weakListHashSet;
        const Derived object;
        EXPECT_FALSE(weakListHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        weakListHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
        EXPECT_TRUE(weakListHashSet.contains(object));
        weakListHashSet.checkConsistency();
        weakListHashSet.add(object);
        EXPECT_TRUE(weakListHashSet.contains(object));
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
        weakListHashSet.checkConsistency();
        weakListHashSet.remove(object);
        weakListHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        EXPECT_FALSE(weakListHashSet.contains(object));
    }
}

TEST(WTF_WeakPtr, WeakListHashSetRemoveIf)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        Base object1;
        Base object2;
        Base object3;
        Base object4;
        weakListHashSet.add(object1);
        weakListHashSet.add(object2);
        weakListHashSet.add(object3);
        weakListHashSet.add(object4);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 4u);

        // Remove object2 and object3; object1 and object4 must remain in insertion order.
        bool removedAny = weakListHashSet.removeIf([&](Base& item) {
            return &item == &object2 || &item == &object3;
        });
        EXPECT_TRUE(removedAny);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 2u);

        Vector<Base*> objectsInIterationOrder;
        for (auto& object : weakListHashSet)
            objectsInIterationOrder.append(&object);
        EXPECT_EQ(objectsInIterationOrder.size(), 2u);
        EXPECT_EQ(objectsInIterationOrder[0], &object1);
        EXPECT_EQ(objectsInIterationOrder[1], &object4);
        weakListHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    {
        // removeIf() drops dead (null) weak references without invoking the predicate.
        WeakListHashSet<Base> weakListHashSet;
        auto object1 = makeUnique<Base>();
        Base object2;
        weakListHashSet.add(*object1);
        weakListHashSet.add(object2);
        EXPECT_EQ(s_baseWeakReferences, 2u);
        object1 = nullptr;

        unsigned predicateCalls = 0;
        bool removedAny = weakListHashSet.removeIf([&](Base& item) {
            ++predicateCalls;
            EXPECT_EQ(&item, &object2);
            return false;
        });
        EXPECT_TRUE(removedAny);
        EXPECT_EQ(predicateCalls, 1u);
        EXPECT_TRUE(weakListHashSet.contains(object2));
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 1u);
        weakListHashSet.checkConsistency();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);
}

TEST(WTF_WeakPtr, WeakListHashSetRemoveIterator)
{
    WeakListHashSet<Base> weakListHashSet;
    Vector<std::unique_ptr<Base>> objects;
    for (unsigned i = 0; i < 13; ++i) {
        auto object = makeUnique<Base>();
        weakListHashSet.add(*object);
        objects.append(WTF::move(object));
    }
    for (unsigned i = 0; i < 13; ++i) {
        auto it = weakListHashSet.find(*objects[0]);
        objects.removeAt(0);
        weakListHashSet.remove(it);
        weakListHashSet.checkConsistency();
        unsigned j = 0;
        for (auto& item : weakListHashSet) {
            EXPECT_EQ(objects[j].get(), &item);
            ++j;
        }
    }
}

TEST(WTF_WeakPtr, WeakListHashSetExpansion)
{
    unsigned initialCapacity;
    static constexpr unsigned maxLoadCap = 3;
    {
        WeakListHashSet<Base> weakListHashSet;
        Base object;
        EXPECT_EQ(s_baseWeakReferences, 0u);
        weakListHashSet.add(object);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        initialCapacity = weakListHashSet.capacity();
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    for (unsigned testCount = 0; testCount < 10; ++testCount) {
        WeakListHashSet<Base> weakListHashSet;
        Vector<std::unique_ptr<Base>> objects;
        Vector<std::unique_ptr<Base>> otherObjects;

        EXPECT_EQ(weakListHashSet.capacity(), 0u);
        EXPECT_TRUE(initialCapacity / maxLoadCap);
        for (unsigned i = 0; i < initialCapacity / maxLoadCap; ++i) {
            auto object = makeUnique<Base>();
            weakListHashSet.add(*object);
            objects.append(WTF::move(object));
            otherObjects.append(makeUnique<Base>());
            weakListHashSet.checkConsistency();
        }
        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
        EXPECT_EQ(weakListHashSet.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), objects.size());
        for (unsigned i = 0; i < otherObjects.size(); ++i) {
            EXPECT_TRUE(weakListHashSet.contains(*objects[i]));
            EXPECT_FALSE(weakListHashSet.contains(*otherObjects[i]));
        }
        objects.clear();
        weakListHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, otherObjects.size());
        EXPECT_EQ(weakListHashSet.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
        for (auto& object : otherObjects)
            EXPECT_FALSE(weakListHashSet.contains(*object));
        for (auto& object : otherObjects) {
            weakListHashSet.add(*object);
            weakListHashSet.checkConsistency();
        }
        EXPECT_EQ(weakListHashSet.capacity(), initialCapacity);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), otherObjects.size());
        for (auto& object : otherObjects)
            EXPECT_TRUE(weakListHashSet.contains(*object));
    }
    EXPECT_EQ(s_baseWeakReferences, 0u);

    for (unsigned testCount = 0; testCount < 10; ++testCount) {
        WeakListHashSet<Base> weakListHashSet;
        Vector<std::unique_ptr<Base>> objects;
        EXPECT_EQ(weakListHashSet.capacity(), 0u);
        unsigned objectCount = initialCapacity * 2;
        for (unsigned i = 0; i < objectCount; ++i) {
            auto object = makeUnique<Base>();
            weakListHashSet.add(*object);
            objects.append(WTF::move(object));
            weakListHashSet.checkConsistency();
        }
        unsigned originalCapacity = weakListHashSet.capacity();
        EXPECT_EQ(s_baseWeakReferences, objects.size());
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), objects.size());

        for (auto& object : objects)
            EXPECT_TRUE(weakListHashSet.contains(*object));

        objects.clear();
        weakListHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, objectCount);
        EXPECT_EQ(weakListHashSet.capacity(), originalCapacity);
        EXPECT_EQ(computeSizeOfWeakListHashSet(weakListHashSet), 0u);
    }
}

TEST(WTF_WeakPtr, WeakListHashSetIsEmptyIgnoringNullReferences)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object;
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());
            EXPECT_TRUE(weakListHashSet.isEmptyIgnoringNullReferences());
            weakListHashSet.add(object);
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());
            EXPECT_FALSE(weakListHashSet.isEmptyIgnoringNullReferences());
            weakListHashSet.checkConsistency();
        }
        EXPECT_TRUE(weakListHashSet.hasNullReferences());
        EXPECT_TRUE(weakListHashSet.isEmptyIgnoringNullReferences());
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
        weakListHashSet.checkConsistency();
    }

    {
        WeakListHashSet<Base> weakListHashSet;
        Base object1;
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
        EXPECT_TRUE(weakListHashSet.isEmptyIgnoringNullReferences());
        weakListHashSet.checkConsistency();
        weakListHashSet.add(object1);
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
        EXPECT_FALSE(weakListHashSet.isEmptyIgnoringNullReferences());
        weakListHashSet.checkConsistency();
        {
            Base object2;
            weakListHashSet.add(object2);
            EXPECT_EQ(s_baseWeakReferences, 2u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());
            EXPECT_FALSE(weakListHashSet.isEmptyIgnoringNullReferences());
            weakListHashSet.checkConsistency();
        }
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_TRUE(weakListHashSet.hasNullReferences());
        EXPECT_FALSE(weakListHashSet.isEmptyIgnoringNullReferences());
        weakListHashSet.checkConsistency();
        weakListHashSet.remove(object1);
        EXPECT_TRUE(weakListHashSet.isEmptyIgnoringNullReferences());
        weakListHashSet.checkConsistency();
    }
}

TEST(WTF_WeakPtr, WeakListHashSetRemoveNullReferences)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object;
            weakListHashSet.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            weakListHashSet.removeNullReferences();
            weakListHashSet.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 0u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            weakListHashSet.add(object);
            weakListHashSet.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            weakListHashSet.removeNullReferences();
            weakListHashSet.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 1u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());
        }
        weakListHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 1u);
        EXPECT_TRUE(weakListHashSet.hasNullReferences());

        weakListHashSet.removeNullReferences();
        weakListHashSet.checkConsistency();
        EXPECT_EQ(s_baseWeakReferences, 0u);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
    }

    {
        WeakListHashSet<Base> weakListHashSet;
        Vector<std::unique_ptr<Derived>> objects;

        for (unsigned i = 0; i < 50; ++i) {
            auto key = makeUnique<Derived>();
            weakListHashSet.add(*key);
            objects.append(WTF::move(key));
        }
        EXPECT_EQ(s_baseWeakReferences, 50U);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
        weakListHashSet.checkConsistency();

        weakListHashSet.removeNullReferences();
        EXPECT_EQ(s_baseWeakReferences, 50U);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
        weakListHashSet.checkConsistency();

        for (unsigned i = 0; i < 50; ++i) {
            if (i % 2)
                objects[i] = nullptr;
        }

        weakListHashSet.removeNullReferences();
        EXPECT_EQ(s_baseWeakReferences, 25U);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
        weakListHashSet.checkConsistency();

        unsigned i = 0;
        for (auto& item : weakListHashSet) {
            EXPECT_EQ(objects[i].get(), &item);
            i += 2;
        }

        objects.clear();
        weakListHashSet.removeNullReferences();
        EXPECT_EQ(s_baseWeakReferences, 0U);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
        weakListHashSet.checkConsistency();
    }
}

Vector<Base*> collectItemsInWeakListHashSet(WeakListHashSet<Base>& set)
{
    Vector<Base*> items;
    for (auto& item : set)
        items.append(&item);
    return items;
}

TEST(WTF_WeakPtr, WeakListHashSetIterators)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object1;
            Derived object2;
            Base object3;
            Derived object4;
            weakListHashSet.checkConsistency();
            weakListHashSet.add(object1);
            weakListHashSet.add(object2);
            weakListHashSet.add(object3);
            weakListHashSet.add(object4);
            EXPECT_EQ(s_baseWeakReferences, 4u);
            EXPECT_EQ(weakListHashSet.computeSize(), 4u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            auto items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 4u);
            EXPECT_EQ(items[0], &object1);
            EXPECT_EQ(items[1], &object2);
            EXPECT_EQ(items[2], &object3);
            EXPECT_EQ(items[3], &object4);

            weakListHashSet.remove(object2);
            weakListHashSet.remove(object3);
            EXPECT_EQ(s_baseWeakReferences, 4u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 2u);
            EXPECT_EQ(items[0], &object1);
            EXPECT_EQ(items[1], &object4);
        }
        EXPECT_EQ(s_baseWeakReferences, 2u);
        EXPECT_TRUE(weakListHashSet.hasNullReferences());
        EXPECT_EQ(collectItemsInWeakListHashSet(weakListHashSet).size(), 0u);
    }

    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Vector<std::unique_ptr<Base>> objects;
            for (unsigned i = 0; i < 50; ++i) {
                if (i % 2)
                    objects.append(makeUnique<Derived>());
                else
                    objects.append(makeUnique<Base>());
                weakListHashSet.add(*objects.last());
            }
            weakListHashSet.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());
            EXPECT_EQ(weakListHashSet.computeSize(), 50u);

            for (unsigned i = 0; i < 50; ++i) {
                if (i % 5)
                    continue;
                weakListHashSet.remove(*objects[i]);
            }
            weakListHashSet.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            auto items = collectItemsInWeakListHashSet(weakListHashSet);

            ASSERT(items.size(), 40U);
            for (unsigned i = 0, j = 0; i < items.size() && j < 50; ++j) {
                if (!(j % 5))
                    continue;
                EXPECT_EQ(items[i], objects[j].get());
                ++i;
            }
            EXPECT_EQ(weakListHashSet.computeSize(), 40u);
        }
        EXPECT_EQ(s_baseWeakReferences, 40u);
        weakListHashSet.checkConsistency();
        EXPECT_TRUE(weakListHashSet.hasNullReferences());

        EXPECT_EQ(weakListHashSet.computeSize(), 0u);
        EXPECT_FALSE(weakListHashSet.hasNullReferences());
    }

    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Vector<std::unique_ptr<Base>> objects;
            for (unsigned i = 0; i < 50; ++i) {
                if (i % 2)
                    objects.append(makeUnique<Derived>());
                else
                    objects.append(makeUnique<Base>());
                objects.last()->dummy = i + 1;
                weakListHashSet.add(*objects.last());
            }
            weakListHashSet.checkConsistency();
            EXPECT_EQ(s_baseWeakReferences, 50u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());
            EXPECT_EQ(weakListHashSet.computeSize(), 50u);

            {
                auto it = weakListHashSet.end();
                unsigned sum = 0;
                while (it != weakListHashSet.begin()) {
                    --it;
                    sum += it->dummy;
                }
                weakListHashSet.checkConsistency();
                EXPECT_EQ(sum, 1275u);
            }

            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            for (unsigned i = 0; i < 50; ++i) {
                if (!(i % 2))
                    objects[i] = nullptr;
            }

            EXPECT_TRUE(weakListHashSet.hasNullReferences());

            {
                auto it = weakListHashSet.end();
                unsigned sum = 0;
                while (it != weakListHashSet.begin()) {
                    --it;
                    sum += it->dummy;
                }
                EXPECT_EQ(sum, 650u);
            }
        }
        EXPECT_TRUE(weakListHashSet.hasNullReferences());
        EXPECT_TRUE(weakListHashSet.end() == weakListHashSet.begin());
    }
}

TEST(WTF_WeakPtr, WeakListHashSetAppendOrMoveToLast)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object1;
            Derived object2;
            Base object3;
            Derived object4;
            weakListHashSet.checkConsistency();
            weakListHashSet.add(object1);
            weakListHashSet.add(object2);
            weakListHashSet.add(object3);
            EXPECT_EQ(s_baseWeakReferences, 3u);
            EXPECT_EQ(weakListHashSet.computeSize(), 3u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            auto items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 3u);
            EXPECT_EQ(items[0], &object1);
            EXPECT_EQ(items[1], &object2);
            EXPECT_EQ(items[2], &object3);

            weakListHashSet.appendOrMoveToLast(object1);

            items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 3u);
            EXPECT_EQ(items[0], &object2);
            EXPECT_EQ(items[1], &object3);
            EXPECT_EQ(items[2], &object1);

            weakListHashSet.appendOrMoveToLast(object4);
            items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 4u);
            EXPECT_EQ(items[0], &object2);
            EXPECT_EQ(items[1], &object3);
            EXPECT_EQ(items[2], &object1);
            EXPECT_EQ(items[3], &object4);

        }
        EXPECT_EQ(s_baseWeakReferences, 4u);
        EXPECT_TRUE(weakListHashSet.hasNullReferences());

        EXPECT_EQ(collectItemsInWeakListHashSet(weakListHashSet).size(), 0u);
    }
}

TEST(WTF_WeakPtr, WeakListHashSetPrependOrMoveToFirst)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object1;
            Derived object2;
            Base object3;
            Derived object4;
            weakListHashSet.checkConsistency();
            weakListHashSet.add(object1);
            weakListHashSet.add(object2);
            weakListHashSet.add(object3);
            EXPECT_EQ(s_baseWeakReferences, 3u);
            EXPECT_EQ(weakListHashSet.computeSize(), 3u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            auto items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 3u);
            EXPECT_EQ(items[0], &object1);
            EXPECT_EQ(items[1], &object2);
            EXPECT_EQ(items[2], &object3);

            weakListHashSet.prependOrMoveToFirst(object4);
            items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 4u);
            EXPECT_EQ(items[0], &object4);
            EXPECT_EQ(items[1], &object1);
            EXPECT_EQ(items[2], &object2);
            EXPECT_EQ(items[3], &object3);

            weakListHashSet.prependOrMoveToFirst(object3);
            items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 4u);
            EXPECT_EQ(items[0], &object3);
            EXPECT_EQ(items[1], &object4);
            EXPECT_EQ(items[2], &object1);
            EXPECT_EQ(items[3], &object2);
        }
        EXPECT_EQ(s_baseWeakReferences, 4u);
        EXPECT_TRUE(weakListHashSet.hasNullReferences());

        EXPECT_EQ(collectItemsInWeakListHashSet(weakListHashSet).size(), 0u);
    }
}

TEST(WTF_WeakPtr, WeakListHashSetInsertBefore)
{
    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object1;
            Derived object2;
            Base object3;
            Derived object4;
            weakListHashSet.checkConsistency();
            weakListHashSet.add(object1);
            weakListHashSet.add(object2);
            weakListHashSet.add(object3);
            EXPECT_EQ(s_baseWeakReferences, 3u);
            EXPECT_EQ(weakListHashSet.computeSize(), 3u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            auto items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 3u);
            EXPECT_EQ(items[0], &object1);
            EXPECT_EQ(items[1], &object2);
            EXPECT_EQ(items[2], &object3);

            weakListHashSet.insertBefore(object2, object4);
            items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 4u);
            EXPECT_EQ(items[0], &object1);
            EXPECT_EQ(items[1], &object4);
            EXPECT_EQ(items[2], &object2);
            EXPECT_EQ(items[3], &object3);
        }
        EXPECT_EQ(s_baseWeakReferences, 4u);
        EXPECT_TRUE(weakListHashSet.hasNullReferences());

        EXPECT_EQ(collectItemsInWeakListHashSet(weakListHashSet).size(), 0u);
    }

    {
        WeakListHashSet<Base> weakListHashSet;
        {
            Base object1;
            Derived object2;
            Base object3;
            Derived object4;
            weakListHashSet.checkConsistency();
            weakListHashSet.add(object1);
            weakListHashSet.add(object2);
            EXPECT_EQ(s_baseWeakReferences, 2u);
            EXPECT_EQ(weakListHashSet.computeSize(), 2u);
            EXPECT_FALSE(weakListHashSet.hasNullReferences());

            auto items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 2u);
            EXPECT_EQ(items[0], &object1);
            EXPECT_EQ(items[1], &object2);

            weakListHashSet.insertBefore(weakListHashSet.find(object2), object3);
            items = collectItemsInWeakListHashSet(weakListHashSet);

            EXPECT_EQ(items.size(), 3u);
            EXPECT_EQ(items[0], &object1);
            EXPECT_EQ(items[1], &object3);
            EXPECT_EQ(items[2], &object2);
        }
        EXPECT_EQ(s_baseWeakReferences, 3u);
        EXPECT_TRUE(weakListHashSet.hasNullReferences());

        EXPECT_EQ(collectItemsInWeakListHashSet(weakListHashSet).size(), 0u);
    }
}

class MultipleInheritanceBase1 : public CanMakeWeakPtr<MultipleInheritanceBase1> {
public:
    MultipleInheritanceBase1() = default;
    virtual ~MultipleInheritanceBase1() = default;

    virtual void meow() = 0;

    int dummy; // Prevent empty base class optimization, to make testing more interesting.
};

class MultipleInheritanceBase2 : public CanMakeWeakPtr<MultipleInheritanceBase2> {
public:
    MultipleInheritanceBase2() = default;
    virtual ~MultipleInheritanceBase2() = default;

    virtual void woof() = 0;

    int dummy; // Prevent empty base class optimization, to make testing more interesting.
};

class MultipleInheritanceDerived : public MultipleInheritanceBase1, public MultipleInheritanceBase2 {
public:
    MultipleInheritanceDerived() = default;
    virtual ~MultipleInheritanceDerived() = default;

    bool meowCalled() const
    {
        return m_meowCalled;
    }
    bool woofCalled() const
    {
        return m_woofCalled;
    }

private:
    void meow() final
    {
        m_meowCalled = true;
    }

    void woof() final
    {
        m_woofCalled = true;
    }

    bool m_meowCalled { false };
    bool m_woofCalled { false };
};

TEST(WTF_WeakPtr, MultipleInheritance)
{
    WeakHashSet<MultipleInheritanceBase1> base1Set;
    WeakHashSet<MultipleInheritanceBase2> base2Set;
    {
        MultipleInheritanceDerived derived;
        base1Set.add(derived);
        base2Set.add(derived);
        for (MultipleInheritanceBase1& base1 : base1Set)
            base1.meow();
        for (MultipleInheritanceBase2& base2 : base2Set)
            base2.woof();
        EXPECT_TRUE(derived.meowCalled());
        EXPECT_TRUE(derived.woofCalled());
    }
    EXPECT_TRUE(base1Set.isEmptyIgnoringNullReferences());
    EXPECT_TRUE(base2Set.isEmptyIgnoringNullReferences());
}

struct ThreadSafeInstanceCounter : public ThreadSafeRefCountedAndCanMakeThreadSafeWeakPtr<ThreadSafeInstanceCounter> {
    ThreadSafeInstanceCounter() { instanceCount++; }
    ~ThreadSafeInstanceCounter() { instanceCount--; }
    static std::atomic<size_t> instanceCount;
};

std::atomic<size_t> ThreadSafeInstanceCounter::instanceCount;

TEST(WTF_ThreadSafeWeakPtr, ThreadSafety)
{
    RefPtr counter = adoptRef(*new ThreadSafeInstanceCounter());
    ThreadSafeWeakPtr<ThreadSafeInstanceCounter> weakPtr(counter);
    EXPECT_NOT_NULL(weakPtr.get());

    std::atomic<size_t> readyThreads { 0 };
    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 1u);
    std::array<std::thread, 3> threads { std::thread { [&, counter] () mutable {
        Vector<RefPtr<ThreadSafeInstanceCounter>> strongReferences;
        strongReferences.reserveInitialCapacity(101);
        readyThreads++;
        while (readyThreads < 3) { }
        for (size_t i = 0; i < 100; i++) {
            strongReferences.append(counter);
            strongReferences.append(counter);
            strongReferences.takeLast();
        }
        counter = nullptr;
    } }, std::thread { [&, counter] () mutable {
        Vector<ThreadSafeWeakPtr<ThreadSafeInstanceCounter>> weakReferences;
        weakReferences.reserveInitialCapacity(101);
        readyThreads++;
        while (readyThreads < 3) { }
        for (size_t i = 0; i < 100; i++) {
            weakReferences.append(counter);
            weakReferences.append(counter);
            weakReferences.takeLast();
        }
        counter = nullptr;
    } }, std::thread { [&, counter] () mutable {
        Vector<RefPtr<ThreadSafeInstanceCounter>> strongReferences;
        Vector<ThreadSafeWeakPtr<ThreadSafeInstanceCounter>> weakReferences;
        strongReferences.reserveInitialCapacity(51);
        weakReferences.reserveInitialCapacity(51);
        readyThreads++;
        while (readyThreads < 3) { }
        for (size_t i = 0; i < 50; i++) {
            strongReferences.append(counter.get());
            weakReferences.append(counter);
            weakReferences.append(counter);
            strongReferences.append(weakReferences.takeLast().get());
            strongReferences.takeLast();
        }
        counter = nullptr;
    } } };

    counter = nullptr;
    for (auto& thread : threads)
        thread.join();
    EXPECT_NULL(weakPtr.get());
    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 0u);
}

TEST(WTF_ThreadSafeWeakPtr, UseAfterMoveResistance)
{
    Ref counter = adoptRef(*new ThreadSafeInstanceCounter());
    auto weakPtr = ThreadSafeWeakPtr { counter.get() };
    auto movedTo = WTF::move(weakPtr);
    SUPPRESS_USE_AFTER_MOVE EXPECT_NULL(weakPtr.get());
    EXPECT_NOT_NULL(movedTo.get());
    ThreadSafeWeakPtr<ThreadSafeInstanceCounter> emptyConstructor;
    EXPECT_NULL(emptyConstructor.get());
}

TEST(WTF_ThreadSafeWeakPtr, ThreadSafeWeakHashSet)
{
    RefPtr first = adoptRef(*new ThreadSafeInstanceCounter);
    ThreadSafeWeakHashSet<ThreadSafeInstanceCounter> set;
    EXPECT_FALSE(set.contains(*first));
    set.add(*first);
    EXPECT_TRUE(set.contains(*first));

    std::atomic<size_t> readyThreads { 0 };
    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 1u);

    std::array<std::thread, 3> threads { std::thread { [&] () mutable {
        Vector<Ref<ThreadSafeInstanceCounter>> strongReferences;
        strongReferences.reserveInitialCapacity(100);
        for (size_t i = 0; i < 100; i++)
            strongReferences.append(adoptRef(*new ThreadSafeInstanceCounter));
        readyThreads++;
        while (readyThreads < 3) { }
        for (size_t i = 0; i < 100; i++)
            set.add(strongReferences.takeLast().get());
    } }, std::thread { [&] () mutable {
        readyThreads++;
        while (readyThreads < 3) { }
        for (size_t i = 0; i < 100; i++) {
            size_t count { 0 };
            bool foundFirst { false };
            set.forEach([&] (auto& instance) {
                if (&instance == first.get())
                    foundFirst = true;
                count++;
            });
            EXPECT_GT(count, 0u);
            EXPECT_TRUE(foundFirst);
        }
    } }, std::thread { [&] () mutable {
        Vector<Ref<ThreadSafeInstanceCounter>> strongReferences;
        strongReferences.reserveInitialCapacity(101);
        for (size_t i = 0; i < 101; i++)
            strongReferences.append(adoptRef(*new ThreadSafeInstanceCounter));
        readyThreads++;
        while (readyThreads < 3) { }
        for (size_t i = 0; i < 100; i++) {
            EXPECT_FALSE(set.contains(strongReferences[i].get()));
            EXPECT_FALSE(set.contains(strongReferences[i + 1].get()));
            set.add(strongReferences[i].get());
            EXPECT_TRUE(set.contains(strongReferences[i].get()));
            EXPECT_FALSE(set.contains(strongReferences[i + 1].get()));
            set.add(strongReferences[i + 1].get());
            EXPECT_TRUE(set.contains(strongReferences[i].get()));
            EXPECT_TRUE(set.contains(strongReferences[i + 1].get()));
            set.remove(strongReferences[i].get());
            EXPECT_FALSE(set.contains(strongReferences[i].get()));
            EXPECT_TRUE(set.contains(strongReferences[i + 1].get()));
            set.remove(strongReferences[i + 1].get());
            EXPECT_FALSE(set.contains(strongReferences[i].get()));
            EXPECT_FALSE(set.contains(strongReferences[i + 1].get()));
        }
    } } };

    for (auto& thread : threads)
        thread.join();

    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 1u);
    EXPECT_TRUE(set.contains(*first));
    EXPECT_FALSE(set.isEmptyIgnoringNullReferences());
    set.clear();
    EXPECT_FALSE(set.contains(*first));
    EXPECT_TRUE(set.isEmptyIgnoringNullReferences());
    first = nullptr;
    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 0u);
}

class ObjectAddingAndRemovingItself : public ThreadSafeRefCountedAndCanMakeThreadSafeWeakPtr<ObjectAddingAndRemovingItself> {
public:
    static Ref<ObjectAddingAndRemovingItself> create(ThreadSafeWeakHashSet<ObjectAddingAndRemovingItself>& set)
    {
        return adoptRef(*new ObjectAddingAndRemovingItself(set));
    }

    ~ObjectAddingAndRemovingItself()
    {
        auto sizeBefore = m_set.sizeIncludingEmptyEntriesForTesting();
        EXPECT_FALSE(m_set.contains(*this));
        auto sizeAfter = m_set.sizeIncludingEmptyEntriesForTesting();
        EXPECT_FALSE(m_set.remove(*this));
        auto sizeAfterRemove = m_set.sizeIncludingEmptyEntriesForTesting();
        EXPECT_EQ(sizeBefore, sizeAfter + 1);
        EXPECT_EQ(sizeAfter, sizeAfterRemove);
        EXPECT_FALSE(m_set.contains(*this));
    }

private:
    ObjectAddingAndRemovingItself(ThreadSafeWeakHashSet<ObjectAddingAndRemovingItself>& set)
        : m_set(set)
    {
        EXPECT_FALSE(m_set.contains(*this));
        m_set.add(*this);
        EXPECT_TRUE(m_set.contains(*this));
    }

    ThreadSafeWeakHashSet<ObjectAddingAndRemovingItself>& m_set;
};

TEST(WTF_ThreadSafeWeakPtr, ThreadSafeWeakHashSetRemoveOnDestruction)
{
    ThreadSafeWeakHashSet<ObjectAddingAndRemovingItself> set;
    Vector<Ref<ObjectAddingAndRemovingItself>> objects;
    for (int i = 0; i < 10; ++i)
        objects.append(ObjectAddingAndRemovingItself::create(set));
    unsigned setSize = 0;
    set.forEach([&](auto& object) { ++setSize; });
    EXPECT_EQ(setSize, 10u);

    objects.removeLast();
    setSize = 0;
    set.forEach([&](auto& object) { ++setSize; });
    EXPECT_EQ(setSize, 9u);

    objects.clear();
    setSize = 0;
    set.forEach([&](auto& object) { ++setSize; });
    EXPECT_EQ(setSize, 0u);
}

class ObjectRemovingItself : public ThreadSafeRefCountedAndCanMakeThreadSafeWeakPtr<ObjectRemovingItself> {
public:
    static Ref<ObjectRemovingItself> create(ThreadSafeWeakHashSet<ObjectRemovingItself>& set)
    {
        return adoptRef(*new ObjectRemovingItself(set));
    }

    ~ObjectRemovingItself()
    {
        EXPECT_FALSE(m_set.contains(*this));
        EXPECT_FALSE(m_set.remove(*this));
    }

private:
    ObjectRemovingItself(ThreadSafeWeakHashSet<ObjectRemovingItself>& set)
        : m_set(set)
    {
    }

    ThreadSafeWeakHashSet<ObjectRemovingItself>& m_set;
};

// Test removing an object that was never inserted during its destructor is ok.
TEST(WTF_ThreadSafeWeakPtr, ThreadSafeWeakHashSetRemoveNonExistantOnDestruction)
{
    ThreadSafeWeakHashSet<ObjectRemovingItself> set;
    {
        Ref<ObjectRemovingItself> object = ObjectRemovingItself::create(set);
    }
}

class ObjectAddingItselfOnly : public ThreadSafeRefCountedAndCanMakeThreadSafeWeakPtr<ObjectAddingAndRemovingItself> {
public:
    static Ref<ObjectAddingItselfOnly> create(ThreadSafeWeakHashSet<ObjectAddingItselfOnly>& set)
    {
        return adoptRef(*new ObjectAddingItselfOnly(set));
    }

private:
    ObjectAddingItselfOnly(ThreadSafeWeakHashSet<ObjectAddingItselfOnly>& set)
        : m_set(set)
    {
        m_set.add(*this);
    }

    ThreadSafeWeakHashSet<ObjectAddingItselfOnly>& m_set;
};

TEST(WTF_ThreadSafeWeakPtr, ThreadSafeWeakHashAmortizedCleanupWhenOnlyAdding)
{
    struct Struct : ThreadSafeRefCountedAndCanMakeThreadSafeWeakPtr<Struct> {
        Struct() = default;
    };

    ThreadSafeWeakHashSet<Struct> set;
    for (int i = 0; i < 10000; ++i) {
        Ref obj = adoptRef(*new Struct);
        set.add(obj.get());
    }
    EXPECT_LT(set.sizeIncludingEmptyEntriesForTesting(), 1000u);
}

// The test passes if it doesn't time out.
TEST(WTF_ThreadSafeWeakPtr, AmortizedCleanupNotQuadratic)
{
    struct Struct : ThreadSafeRefCountedAndCanMakeThreadSafeWeakPtr<Struct> {
        Struct() = default;
    };

    ThreadSafeWeakHashSet<Struct> set;
    HashSet<Ref<Struct>> strongSet;
    for (int i = 0; i < 1000000; ++i) {
        Ref obj = adoptRef(*new Struct);
        set.add(obj.get());
        strongSet.add(WTF::move(obj));
    }
}

TEST(WTF_ThreadSafeWeakPtr, MultipleInheritance)
{
    enum class Destructor : uint8_t { Cat, Dog, CatDog };
    static Vector<Destructor> destructors;

    struct Cat : public ThreadSafeRefCountedAndCanMakeThreadSafeWeakPtr<Cat> {
        virtual ~Cat() { destructors.append(Destructor::Cat); }
        virtual void meow() = 0;

        bool cat { true };
    };

    struct Dog {
        virtual ~Dog() { destructors.append(Destructor::Dog); }
        virtual void woof() = 0;

        virtual void ref() const = 0;
        virtual void deref() const = 0;
        virtual ThreadSafeWeakPtrControlBlock& controlBlock() const = 0;
        virtual size_t weakRefCount() const = 0;

        bool dog { true };
    };

    struct CatDog : public Cat, public Dog {
        ~CatDog() { destructors.append(Destructor::CatDog); }

        void ref() const final { Cat::ref(); }
        void deref() const final { Cat::deref(); }
        ThreadSafeWeakPtrControlBlock& controlBlock() const final { return Cat::controlBlock(); }
        size_t weakRefCount() const final { return Cat::weakRefCount(); }

        void meow() final { meowed = true; }
        void woof() final { barked = true; }

        bool meowed { false };
        bool barked { false };
    };

    ThreadSafeWeakHashSet<Dog> dogs;
    ThreadSafeWeakHashSet<Cat> cats;
    {
        Ref catDog = adoptRef(*new CatDog);
        Cat* catPointer { nullptr };
        Dog* dogPointer { nullptr };

        cats.add(catDog.get());
        dogs.add(catDog.get());
        for (auto& cat : cats) {
            cat.meow();
            catPointer = &cat;
        }
        for (auto& dog : dogs) {
            dogPointer = &dog;
            dog.woof();
        }
        EXPECT_NE((size_t)catPointer, (size_t)dogPointer);
        EXPECT_TRUE(catDog->meowed);
        EXPECT_TRUE(catDog->barked);
    }
    EXPECT_TRUE(dogs.isEmptyIgnoringNullReferences());
    EXPECT_TRUE(cats.isEmptyIgnoringNullReferences());

    RefPtr keepCat = adoptRef(new CatDog);
    RefPtr<Cat> cat(keepCat.get());
    keepCat = nullptr;
    cat = nullptr;

    RefPtr keepDog = adoptRef(new CatDog);
    RefPtr<Dog> dog(keepDog.get());
    keepDog = nullptr;
    dog = nullptr;

    Vector<Destructor> expectedDestructors {
        Destructor::CatDog,
        Destructor::Dog,
        Destructor::Cat,
        Destructor::CatDog,
        Destructor::Dog,
        Destructor::Cat,
        Destructor::CatDog,
        Destructor::Dog,
        Destructor::Cat,
    };
    EXPECT_EQ(destructors, expectedDestructors);
}

struct Struct : public ThreadSafeRefCountedAndCanMakeThreadSafeWeakPtr<Struct> {
    Struct();
    ~Struct();
};

static ThreadSafeWeakHashSet<Struct>& set()
{
    static NeverDestroyed<ThreadSafeWeakHashSet<Struct>> set;
    return set.get();
}

Struct::Struct()
{
    set().add(*this);
}

Struct::~Struct()
{
    set().remove(*this);
}

TEST(WTF_ThreadSafeWeakPtr, RemoveInDestructor)
{
    for (size_t i = 0; i < 100; i++) {
        Vector<Ref<Struct>> vector;
        vector.reserveInitialCapacity(i);
        ThreadSafeWeakHashSet<Struct> set;
        for (size_t j = 0; j < i; j++) {
            vector.append(adoptRef(*new Struct()));
            set.add(vector.last().get());
        }
    }
}

// The four tests below reproduce races in ThreadSafeWeakPtr and ThreadSafeWeakHashSet. Each runs
// its accesses twice: once unguarded, which is where the race lives, and once with every access to
// the shared handle under a single lock. The guarded run is the control -- if only the unguarded
// run trips an oracle or a sanitizer, the cause is the missing synchronization rather than the
// access pattern itself.
enum class GuardWithLock : bool { No, Yes };

template<typename Function>
static void performWithOptionalLock(Lock& lock, GuardWithLock guard, const Function& function)
{
    if (guard == GuardWithLock::Yes) {
        Locker locker { lock };
        function();
    } else
        function();
}

static void testTornPairOnAssignment(GuardWithLock guard)
{
    constexpr unsigned iterations = 200000;

    Lock lock;
    ThreadSafeWeakPtr<ThreadSafeInstanceCounter> sharedWeak;
    std::atomic<bool> readerShouldStop { false };

    RefPtr counter = adoptRef(*new ThreadSafeInstanceCounter);
    sharedWeak = *counter;

    std::thread reader { [&] {
        while (!readerShouldStop.load(std::memory_order_relaxed)) {
            performWithOptionalLock(lock, guard, [&] {
                // A torn read pairs the old control block with the new null object pointer, so it
                // resolves to null rather than to a bad object. The damage it does is the
                // unmatched strong reference asserted after the join.
                RefPtr strong = sharedWeak.get();
            });
        }
    } };

    std::thread writer { [&] {
        for (unsigned i = 0; i < iterations; ++i) {
            performWithOptionalLock(lock, guard, [&] {
                sharedWeak = nullptr;
                sharedWeak = *counter;
            });
        }
        readerShouldStop.store(true, std::memory_order_relaxed);
    } };

    writer.join();
    reader.join();

    // Only this function's RefPtr should hold a strong reference now. Any extra count is a torn
    // read that incremented m_strongReferenceCount and returned adoptRef(nullptr).
    EXPECT_EQ(counter->refCount(), 1u);

    sharedWeak = nullptr;
    counter = nullptr;
    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 0u);
}

TEST(WTF_ThreadSafeWeakPtr, TornPairOnAssignment)
{
    testTornPairOnAssignment(GuardWithLock::No);
    testTornPairOnAssignment(GuardWithLock::Yes);
}

static void testControlBlockFreedUnderReader(GuardWithLock guard)
{
    constexpr unsigned iterations = 200000;

    Lock lock;
    ThreadSafeWeakPtr<ThreadSafeInstanceCounter> sharedWeak;
    std::atomic<bool> readerShouldStop { false };

    std::thread reader { [&] {
        while (!readerShouldStop.load(std::memory_order_relaxed)) {
            performWithOptionalLock(lock, guard, [&] {
                RefPtr strong = sharedWeak.get();
            });
        }
    } };

    std::thread writer { [&] {
        for (unsigned i = 0; i < iterations; ++i) {
            performWithOptionalLock(lock, guard, [&] {
                {
                    RefPtr victim = adoptRef(*new ThreadSafeInstanceCounter);
                    sharedWeak = *victim;
                }
                // The pointee is gone and sharedWeak holds the last weak reference, so this
                // assignment is the one that frees the control block.
                sharedWeak = nullptr;
            });
        }
        readerShouldStop.store(true, std::memory_order_relaxed);
    } };

    writer.join();
    reader.join();

    EXPECT_NULL(sharedWeak.get());
    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 0u);
}

TEST(WTF_ThreadSafeWeakPtr, ControlBlockFreedUnderReader)
{
    testControlBlockFreedUnderReader(GuardWithLock::No);
    testControlBlockFreedUnderReader(GuardWithLock::Yes);
}

TEST(WTF_ThreadSafeWeakPtr, GetRacingWithLastWeakReferenceRelease)
{
    constexpr unsigned iterations = 200000;

    ThreadSafeWeakPtr<ThreadSafeInstanceCounter> sharedWeak;
    std::atomic<bool> writerFinished { false };
    std::atomic<uint64_t> resolvedCount { 0 };
    std::atomic<uint64_t> readAttempts { 0 };
    std::atomic<unsigned> readyThreads { 0 };

    // Counts assignments published by the writer. The reader serves rounds rather than latching a
    // generation, so it cannot miss the one the writer is in and spin against a handle that is
    // already empty.
    std::atomic<uint64_t> generation { 0 };

    std::atomic<bool> objectAlive { false };
    std::atomic<uint64_t> resolvedWhileLagging { 0 };
    std::atomic<uint64_t> resolvedWhileAlive { 0 };
    std::atomic<uint64_t> resolvedInWindow { 0 };
    std::atomic<uint64_t> laggingAttempts { 0 };

    std::thread reader { [&] {
        readyThreads++;
        while (readyThreads < 3) { }
        for (uint64_t roundsServed = 0; ; ++roundsServed) {
            while (generation.load(std::memory_order_acquire) == roundsServed) {
                if (writerFinished.load(std::memory_order_relaxed))
                    return;
            }
            readAttempts.fetch_add(1, std::memory_order_relaxed);
            bool lagging = generation.load(std::memory_order_acquire) != roundsServed + 1;
            if (lagging)
                laggingAttempts.fetch_add(1, std::memory_order_relaxed);
            bool aliveBefore = objectAlive.load(std::memory_order_acquire);
            // Racing the writer's `sharedWeak = nullptr` below, which frees the control block this
            // get() is about to read.
            if (RefPtr strong = sharedWeak.get()) {
                bool aliveAfter = objectAlive.load(std::memory_order_acquire);
                bool staleRound = generation.load(std::memory_order_acquire) != roundsServed + 1;
                resolvedCount.fetch_add(1, std::memory_order_relaxed);
                if (lagging)
                    resolvedWhileLagging.fetch_add(1, std::memory_order_relaxed);
                if (aliveBefore || aliveAfter)
                    resolvedWhileAlive.fetch_add(1, std::memory_order_relaxed);
                if (!lagging && !staleRound && !aliveBefore && !aliveAfter)
                    resolvedInWindow.fetch_add(1, std::memory_order_relaxed);
            }
        }
    } };

    // Recycles control blocks so that one freed under the reader is likely to be reused, rather than
    // left untouched where reading it would look harmless.
    std::thread allocationChurn { [&] {
        readyThreads++;
        while (readyThreads < 3) { }
        while (!writerFinished.load(std::memory_order_relaxed)) {
            Ref object = adoptRef(*new ThreadSafeInstanceCounter);
            // Forces a control block into existence, so this churns the same allocations.
            ThreadSafeWeakPtr weak { object.get() };
        }
    } };

    readyThreads++;
    while (readyThreads < 3) { }

    for (unsigned i = 0; i < iterations; ++i) {
        {
            Ref victim = adoptRef(*new ThreadSafeInstanceCounter);
            objectAlive.store(true, std::memory_order_release);
            sharedWeak = victim.get();
        }
        objectAlive.store(false, std::memory_order_release);
        // The object is already destroyed, so sharedWeak holds the block's last weak reference and
        // the assignment below is the one that frees it. Publishing first is what puts the reader's
        // get() and that release in the same window.
        generation.fetch_add(1, std::memory_order_release);
        sharedWeak = nullptr;
    }

    writerFinished.store(true, std::memory_order_relaxed);
    generation.fetch_add(1, std::memory_order_release);
    reader.join();
    allocationChurn.join();

    EXPECT_GT(readAttempts.load(), 0u);
    EXPECT_EQ(resolvedInWindow.load(), 0u);
    EXPECT_NULL(sharedWeak.get());
    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 0u);
}

static void testDoubleWeakDeref(GuardWithLock guard)
{
    constexpr unsigned balanceIterations = 200000;
    constexpr unsigned hashSetIterations = 20000;

    Lock lock;
    ThreadSafeWeakPtr<ThreadSafeInstanceCounter> sharedWeak;
    auto assignSharedWeak = [&](ThreadSafeInstanceCounter& object) {
        performWithOptionalLock(lock, guard, [&] { sharedWeak = object; });
    };
    auto clearSharedWeak = [&] {
        performWithOptionalLock(lock, guard, [&] { sharedWeak = nullptr; });
    };

    {
        RefPtr a = adoptRef(*new ThreadSafeInstanceCounter);
        RefPtr b = adoptRef(*new ThreadSafeInstanceCounter);

        // One long-lived weak reference each, so the expected final count is exactly 1.
        ThreadSafeWeakPtr keeperA { *a };
        ThreadSafeWeakPtr keeperB { *b };

        std::thread writerA { [&] {
            for (unsigned i = 0; i < balanceIterations; ++i)
                assignSharedWeak(*a);
        } };
        std::thread writerB { [&] {
            for (unsigned i = 0; i < balanceIterations; ++i)
                assignSharedWeak(*b);
        } };
        writerA.join();
        writerB.join();

        clearSharedWeak();
        EXPECT_EQ(a->weakRefCount(), 1u);
        EXPECT_EQ(b->weakRefCount(), 1u);
    }

    {
        ThreadSafeWeakHashSet<ThreadSafeInstanceCounter> set;

        // Phase 2 needs the two writers to overlap on the SAME assignment, so they are released one
        // iteration at a time instead of running free.
        std::atomic<unsigned> generation { 0 };
        std::atomic<unsigned> workersDone { 0 };
        std::atomic<bool> finished { false };

        // A worker counts the rounds it has served rather than latching whichever generation it
        // happens to observe first: main may already have published a round by the time a worker
        // starts running, and a worker that then waited for the generation to change again would
        // wait forever against main waiting for that same round to be served.
        auto worker = [&] {
            for (unsigned roundsServed = 0; ; ++roundsServed) {
                while (generation.load(std::memory_order_acquire) == roundsServed) {
                    if (finished.load(std::memory_order_acquire))
                        return;
                }
                if (finished.load(std::memory_order_acquire))
                    return;
                clearSharedWeak();
                workersDone.fetch_add(1, std::memory_order_release);
            }
        };

        std::thread writerA { worker };
        std::thread writerB { worker };

        for (unsigned i = 0; i < hashSetIterations; ++i) {
            {
                RefPtr victim = adoptRef(*new ThreadSafeInstanceCounter);
                set.add(*victim);
                assignSharedWeak(*victim);
            }
            // The block now has two weak references (the set's bucket and sharedWeak) and no strong
            // ones. Let both writers clear sharedWeak at once.
            workersDone.store(0, std::memory_order_release);
            generation.fetch_add(1, std::memory_order_release);
            while (workersDone.load(std::memory_order_acquire) < 2) { }

            // Drives amortizedCleanupIfNeeded() -> objectHasStartedDeletion() over the buckets.
            EXPECT_TRUE(set.isEmptyIgnoringNullReferences());
        }

        finished.store(true, std::memory_order_release);
        generation.fetch_add(1, std::memory_order_release);
        writerA.join();
        writerB.join();
    }

    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 0u);
}

TEST(WTF_ThreadSafeWeakPtr, DoubleWeakDeref)
{
    testDoubleWeakDeref(GuardWithLock::No);
    testDoubleWeakDeref(GuardWithLock::Yes);
}

static void testWeakHashSetTimeOfCheckTimeOfUse(GuardWithLock guard)
{
    constexpr unsigned iterations = 200000;

    Lock lock;
    ThreadSafeWeakHashSet<ThreadSafeInstanceCounter> set;
    ThreadSafeWeakPtr<ThreadSafeInstanceCounter> sharedWeak;
    std::atomic<bool> shouldStop { false };

    // The object outlives every thread below, so every set operation is in contract.
    RefPtr keepAlive = adoptRef(*new ThreadSafeInstanceCounter);

    std::thread setUser { [&] {
        for (size_t i = 0; !shouldStop.load(std::memory_order_relaxed); ++i) {
            performWithOptionalLock(lock, guard, [&] {
                switch (i % 3) {
                case 0:
                    set.add(*keepAlive);
                    break;
                case 1:
                    (void)set.contains(*keepAlive);
                    break;
                default:
                    (void)set.remove(*keepAlive);
                    break;
                }
            });
        }
    } };

    auto churnHandle = [&](bool assignObject) {
        for (unsigned i = 0; i < iterations; ++i) {
            performWithOptionalLock(lock, guard, [&] {
                if (assignObject)
                    sharedWeak = *keepAlive;
                else
                    sharedWeak = nullptr;
            });
        }
    };

    std::thread writerA { [&] {
        churnHandle(true);
    } };
    std::thread writerB { [&] {
        churnHandle(false);
    } };

    writerA.join();
    writerB.join();
    shouldStop.store(true, std::memory_order_relaxed);
    setUser.join();

    // The set holds 0 or 1 weak references here and sharedWeak holds 0 or 1, so 0..2 is in range.
    // Anything larger is a corrupted count; see the sanitizer output for the race itself.
    EXPECT_LE(keepAlive->weakRefCount(), 2u);

    sharedWeak = nullptr;
    set.clear();
    keepAlive = nullptr;
    EXPECT_EQ(ThreadSafeInstanceCounter::instanceCount, 0u);
}

TEST(WTF_ThreadSafeWeakPtr, WeakHashSetTimeOfCheckTimeOfUse)
{
    testWeakHashSetTimeOfCheckTimeOfUse(GuardWithLock::No);
    testWeakHashSetTimeOfCheckTimeOfUse(GuardWithLock::Yes);
}

DECLARE_ALLOCATOR_WITH_HEAP_IDENTIFIER(DidUpdateRefCountWeakPtrImpl);

class DidUpdateRefCountWeakPtrImpl final {
    WTF_MAKE_NONCOPYABLE(DidUpdateRefCountWeakPtrImpl);
    WTF_DEPRECATED_MAKE_FAST_ALLOCATED_WITH_HEAP_IDENTIFIER(DidUpdateRefCountWeakPtrImpl, DidUpdateRefCountWeakPtrImpl);
public:
    template<typename T> typename T::WeakValueType* get()
    {
        return static_cast<typename T::WeakValueType*>(m_ptr);
    }

    explicit operator bool() const { return m_ptr; }
    void clear()
    {
        m_ptr = nullptr;
#if !ASSERT_WITH_SECURITY_IMPLICATION_DISABLED
        m_thread = anyThreadLike;
#endif
    }

    template<typename T>
    explicit DidUpdateRefCountWeakPtrImpl(T* ptr)
        : m_ptr(static_cast<typename T::WeakValueType*>(ptr))
    {
    }

#if !ASSERT_WITH_SECURITY_IMPLICATION_DISABLED
    ~DidUpdateRefCountWeakPtrImpl() { m_thread = anyThreadLike; }

    const ThreadLikeAssertion& threadAssertion() const { return m_thread; }
#endif

    void resetDidUpdateRefCount() { m_didUpdateRefCount = false; }
    bool didUpdateRefCount() const { return m_didUpdateRefCount; }

    void ref() const
    {
        m_didUpdateRefCount = true;
        ++m_refCount;
    }
    void deref() const
    {
        m_didUpdateRefCount = true;
        uint32_t tempRefCount = m_refCount - 1;
        if (!tempRefCount) {
            delete this;
            return;
        }
        m_refCount = tempRefCount;
    }

private:
    mutable uint32_t m_refCount { 1 };
    void* m_ptr;
    mutable bool m_didUpdateRefCount { false };
#if !ASSERT_WITH_SECURITY_IMPLICATION_DISABLED
    NO_UNIQUE_ADDRESS mutable ThreadLikeAssertion m_thread { mainThreadLike };
#endif
};
DEFINE_ALLOCATOR_WITH_HEAP_IDENTIFIER(DidUpdateRefCountWeakPtrImpl);

class TestType : public WTF::CanMakeWeakPtr<TestType, WeakPtrFactoryInitialization::Lazy, DidUpdateRefCountWeakPtrImpl> {
public:
    TestType() = default;

    void resetDidUpdateImplRefCount() { weakPtrFactory().impl()->resetDidUpdateRefCount(); }
    bool didUpdateImplRefCount() const { return weakPtrFactory().impl()->didUpdateRefCount(); }
};

TEST(WTF_WeakRef, HashSetLookupFromRawRef)
{
    HashSet<WTF::WeakRef<TestType, DidUpdateRefCountWeakPtrImpl>> set;

    TestType object;
    set.add(object);
    EXPECT_EQ(set.size(), 1U);

    object.resetDidUpdateImplRefCount();
    EXPECT_TRUE(set.contains(object));
    EXPECT_FALSE(object.didUpdateImplRefCount());

    object.resetDidUpdateImplRefCount();
    EXPECT_TRUE(set.find(object) != set.end());
    EXPECT_FALSE(object.didUpdateImplRefCount());

    EXPECT_TRUE(set.remove(object));
    set.add(object);

    object.resetDidUpdateImplRefCount();
    WTF::WeakPtr<TestType, DidUpdateRefCountWeakPtrImpl> taken = set.take(object);
    EXPECT_FALSE(object.didUpdateImplRefCount());
    EXPECT_EQ(taken.get(), &object);
}

TEST(WTF_WeakRef, HashMapLookupFromRawRef)
{
    HashMap<WTF::WeakRef<TestType, DidUpdateRefCountWeakPtrImpl>, unsigned> map;

    TestType object;
    map.add(object, 1);
    EXPECT_EQ(map.size(), 1U);

    object.resetDidUpdateImplRefCount();
    EXPECT_TRUE(map.contains(object));
    EXPECT_FALSE(object.didUpdateImplRefCount());

    object.resetDidUpdateImplRefCount();
    EXPECT_TRUE(map.find(object) != map.end());
    EXPECT_FALSE(object.didUpdateImplRefCount());

    EXPECT_TRUE(map.remove(object));
    map.add(object, 2);

    object.resetDidUpdateImplRefCount();
    EXPECT_EQ(map.get(object), 2U);
    EXPECT_FALSE(object.didUpdateImplRefCount());

    unsigned taken = map.take(object);
    EXPECT_EQ(taken, 2U);
}

TEST(WTF_WeakRef, ListHashSetLookupFromRawRef)
{
    ListHashSet<WTF::WeakRef<TestType, DidUpdateRefCountWeakPtrImpl>> set;

    TestType object;
    set.add(object);
    EXPECT_EQ(set.size(), 1U);

    object.resetDidUpdateImplRefCount();
    EXPECT_TRUE(set.contains(object));
    EXPECT_FALSE(object.didUpdateImplRefCount());

    object.resetDidUpdateImplRefCount();
    EXPECT_TRUE(set.find(object) != set.end());
    EXPECT_FALSE(object.didUpdateImplRefCount());

    EXPECT_TRUE(set.remove(object));
    set.add(object);

    object.resetDidUpdateImplRefCount();
    TestType object2;
    set.insertBefore(object, object2);
    EXPECT_FALSE(object.didUpdateImplRefCount());
    EXPECT_EQ(set.size(), 2U);
}

TEST(WTF_WeakRef, HashCountedSetLookupFromRawRef)
{
    HashCountedSet<WTF::WeakRef<TestType, DidUpdateRefCountWeakPtrImpl>> set;

    TestType object;
    set.add(object);
    EXPECT_EQ(set.size(), 1U);

    object.resetDidUpdateImplRefCount();
    EXPECT_TRUE(set.contains(object));
    EXPECT_FALSE(object.didUpdateImplRefCount());

    object.resetDidUpdateImplRefCount();
    EXPECT_TRUE(set.find(object) != set.end());
    EXPECT_FALSE(object.didUpdateImplRefCount());

    object.resetDidUpdateImplRefCount();
    EXPECT_EQ(set.count(object), 1U);
    EXPECT_FALSE(object.didUpdateImplRefCount());

    EXPECT_TRUE(set.remove(object));
    EXPECT_EQ(set.size(), 0U);
    set.add(object);
}

TEST(WTF_WeakPtr, AssignFromWeakRef)
{
    Derived derived;

    {
        // Copy assign WeakRef<Derived> to WeakPtr<Derived> (same type).
        WeakRef<Derived> derivedWeakRef { derived };
        WeakPtr<Derived> derivedWeakPtr;
        derivedWeakPtr = derivedWeakRef;
        EXPECT_EQ(derivedWeakPtr.get(), &derived);
        EXPECT_EQ(&derivedWeakRef.get(), &derived);
    }

    {
        // Move assign WeakRef<Derived> to WeakPtr<Derived> (same type).
        WeakRef<Derived> derivedWeakRef { derived };
        WeakPtr<Derived> derivedWeakPtr;
        derivedWeakPtr = WTF::move(derivedWeakRef);
        EXPECT_EQ(derivedWeakPtr.get(), &derived);
    }

    {
        // Copy assign WeakRef<Derived> to WeakPtr<Base> (cross-type).
        WeakRef<Derived> derivedWeakRef { derived };
        WeakPtr<Base> baseWeakPtr;
        baseWeakPtr = derivedWeakRef;
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        EXPECT_EQ(&derivedWeakRef.get(), &derived);
    }

    {
        // Move assign WeakRef<Derived> to WeakPtr<Base> (cross-type).
        WeakRef<Derived> derivedWeakRef { derived };
        WeakPtr<Base> baseWeakPtr;
        baseWeakPtr = WTF::move(derivedWeakRef);
        EXPECT_EQ(baseWeakPtr.get(), &derived);
    }
}

TEST(WTF_WeakPtr, AssignFromWeakRefConst)
{
    const Derived derived;

    {
        // Copy assign WeakRef<const Derived> to WeakPtr<const Base> (cross-type).
        WeakRef<const Derived> derivedWeakRef { derived };
        WeakPtr<const Base> baseWeakPtr;
        baseWeakPtr = derivedWeakRef;
        EXPECT_EQ(baseWeakPtr.get(), &derived);
        EXPECT_EQ(&derivedWeakRef.get(), &derived);
    }

    {
        // Move assign WeakRef<const Derived> to WeakPtr<const Base> (cross-type).
        WeakRef<const Derived> derivedWeakRef { derived };
        WeakPtr<const Base> baseWeakPtr;
        baseWeakPtr = WTF::move(derivedWeakRef);
        EXPECT_EQ(baseWeakPtr.get(), &derived);
    }
}

} // namespace TestWebKitAPI