// Copyright 2026 The Dawn & Tint Authors
//
// 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.
//
// 3. Neither the name of the copyright holder nor the names of its
//    contributors may be used to endorse or promote products derived from
//    this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT HOLDER OR 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 "src/utils/heap_array.h"

#include <array>
#include <limits>
#include <ranges>

#include "src/utils/gtest.h"
#include "src/utils/typed_integer.h"

namespace dawn {
namespace {

class HeapArrayTest : public ::testing::Test {
  protected:
    using Index = TypedInteger<struct KeyT, size_t>;
    using Val = TypedInteger<struct ValT, uint32_t>;
    using HeapArrayVal = ityp::HeapArray<Index, Val>;

    // Type for use with Uninit() which requires a POD value type.
    using HeapArrayPOD = ityp::HeapArray<Index, int>;
};

// Name "*DeathTest" per https://google.github.io/googletest/advanced.html#death-test-naming
using HeapArrayDeathTest = HeapArrayTest;

TEST_F(HeapArrayTest, KeyTypes) {
    (void)ityp::HeapArray<TypedInteger<struct KU8, uint8_t>, int>();
    (void)ityp::HeapArray<TypedInteger<struct KU32, uint32_t>, int>();
    (void)ityp::HeapArray<TypedInteger<struct KSizeT, size_t>, int>();

    enum class E : uint32_t {};
    (void)ityp::HeapArray<E, int>();

    (void)ityp::HeapArray<uint16_t, int>();
}

// Test that values can be set at an index and retrieved from the same index.
TEST_F(HeapArrayTest, Indexing) {
    HeapArrayVal arr{Index{10u}};
    {
        arr[Index{2u}] = Val{5u};
        arr[Index{1u}] = Val{9u};
        arr[Index{9u}] = Val{2u};
        arr.front() = Val{8u};

        EXPECT_EQ(arr[Index{2u}], Val{5u});
        EXPECT_EQ(arr[Index{1u}], Val{9u});
        EXPECT_EQ(arr[Index{9u}], Val{2u});
        EXPECT_EQ(arr.front(), Val{8u});
    }
}

// Test that the HeapArray can be iterated in order with a range-based for loop
TEST_F(HeapArrayTest, RangeBasedIteration) {
    // Also check that it satisfies various range concepts.
    static_assert(std::ranges::common_range<HeapArrayVal>);
    static_assert(std::ranges::contiguous_range<HeapArrayVal>);
    static_assert(std::ranges::input_range<HeapArrayVal>);
    static_assert(std::ranges::output_range<HeapArrayVal, Val>);
    static_assert(std::ranges::sized_range<HeapArrayVal>);
    static_assert(std::ranges::viewable_range<HeapArrayVal>);
    static_assert(!std::ranges::borrowed_range<HeapArrayVal>);
    static_assert(!std::ranges::view<HeapArrayVal>);

    HeapArrayVal arr{Index{10u}};
    EXPECT_TRUE(bool{arr});

    // Assign in a non-const range-based for loop
    for (uint32_t i = 0; Val& val : arr) {
        val = Val(i);
    }

    // Check values in a const range-based for loop
    for (uint32_t i = 0; Val val : static_cast<const HeapArrayVal&>(arr)) {
        EXPECT_EQ(val, arr[Index(i++)]);
    }
}

// Test that begin/end/front/back/data return pointers/references to the correct elements.
TEST_F(HeapArrayTest, BeginEndFrontBackData) {
    HeapArrayVal arr{Index{10u}};

    // non-const versions
    EXPECT_EQ(&*arr.begin(), &arr[Index{0u}]);
    EXPECT_EQ(&*arr.end(),
              // SAFETY: Comparing safe implementation with unsafe re-implementation.
              DAWN_UNSAFE_BUFFERS(&arr[Index{0u}] + static_cast<size_t>(arr.size())));
    EXPECT_EQ(&arr.front(), &arr[Index{0u}]);
    EXPECT_EQ(&arr.back(), &arr[Index{9u}]);
    EXPECT_EQ(arr.data(), &arr[Index{0u}]);

    // const versions
    const HeapArrayVal& constArr = arr;
    EXPECT_EQ(&*constArr.begin(), &constArr[Index{0u}]);
    EXPECT_EQ(&*constArr.end(),
              // SAFETY: Comparing safe implementation with unsafe re-implementation.
              DAWN_UNSAFE_BUFFERS(&constArr[Index{0u}] + static_cast<size_t>(constArr.size())));
    EXPECT_EQ(&constArr.front(), &constArr[Index{0u}]);
    EXPECT_EQ(&constArr.back(), &constArr[Index{9u}]);
    EXPECT_EQ(constArr.data(), &constArr[Index{0u}]);
}

// Empty HeapArray.
TEST_F(HeapArrayTest, Empty) {
    {
        HeapArrayVal arr{Index{0u}};
        EXPECT_TRUE(bool{arr});
        EXPECT_NE(nullptr, arr.data());
        EXPECT_EQ(Index{0u}, arr.size());
    }
    {
        HeapArrayVal arr{Index{0u}, std::nothrow};
        EXPECT_TRUE(bool{arr});
        EXPECT_NE(nullptr, arr.data());
        EXPECT_EQ(Index{0u}, arr.size());
    }
}

// `Uninit`ialized HeapArray.
TEST_F(HeapArrayTest, Uninit) {
    // SAFETY: Testing unsafe API.
    auto arr = DAWN_UNSAFE_BUFFERS(HeapArrayPOD::Uninit(Index{1u}));
    EXPECT_TRUE(bool{arr});

    arr[Index{0u}] = 5;
    EXPECT_EQ(arr[Index{0u}], 5);
}

// Tests for the HeapArrayFrom helper.
TEST_F(HeapArrayTest, HeapArrayFrom) {
    constexpr std::array<int, 5> kSrc = {1, 2, 3, 4, 5};
    {
        auto arr = ityp::HeapArrayFrom<Index>(kSrc);
        EXPECT_EQ(arr[Index{0u}], 1);
        EXPECT_EQ(arr[Index{4u}], 5);
    }
    {
        auto arr = HeapArrayFrom(kSrc);
        EXPECT_EQ(arr[0], 1);
        EXPECT_EQ(arr[4], 5);
    }
}

// Test HeapArray can be used as a range (by converting it to span).
TEST_F(HeapArrayTest, Range) {
    HeapArrayVal arr{Index{10u}};

    // Explicit construction.
    (void)std::span<Val>(arr);
    // Dawn's span requires the index type to match.
    (void)ityp::span<Index, Val>(arr);

    // Spans also allow implicit construction from a range.
    [[maybe_unused]] std::span<Val> s1 = arr;
    [[maybe_unused]] ityp::span<Index, Val> s2 = arr;
}

// Test HeapArrayFrom handles when the source range is larger than its index type.
// (There are no other HeapArray constructors that need to check this.)
TEST_F(HeapArrayDeathTest, SmallIndex) {
    using IndexU8 = TypedInteger<struct IndexU8T, uint8_t>;
    {
        (void)ityp::HeapArrayFrom<IndexU8>(std::array<int, 254>{});

        // 255 is invalid because it's reserved as a sentinel value by dawn::SpanBase.
        EXPECT_DEATH_IF_SUPPORTED((void)ityp::HeapArrayFrom<IndexU8>(std::array<int, 255>{}), "");
    }
}

// Checks that various byte types are always aligned to alignof(std::max_align_t).
template <typename HA>
void CheckByteAllocation(const HA& ha) {
    EXPECT_EQ(reinterpret_cast<uintptr_t>(ha.data()) % alignof(std::max_align_t), 0u);
}
TEST_F(HeapArrayTest, ByteTypeAlignment) {
    CheckByteAllocation(HeapArray<std::byte>(16));
    CheckByteAllocation(HeapArray<char>(16));
    // uint8_t is not technically guaranteed to be max-aligned, but in practice it will be.
    // As of this writing, some Dawn code relies on it.
    CheckByteAllocation(HeapArray<uint8_t>(16));
}

// Check that various non-byte types are always aligned as expected.
template <typename T>
void CheckTypedAllocation(const HeapArray<T>& ha) {
    EXPECT_EQ(reinterpret_cast<uintptr_t>(ha.data()) % alignof(T), 0u);
}
TEST_F(HeapArrayTest, NonByteTypeAlignment) {
    CheckTypedAllocation(HeapArray<uint32_t>(16));
    struct A {
        uint8_t x;
    };
    CheckTypedAllocation(HeapArray<A>{16});
    struct B {
        std::max_align_t x;
    };
    CheckTypedAllocation(HeapArray<B>{16});
    struct alignas(256) C {
        int x;
    };
    static_assert(alignof(C) == 256);
    CheckTypedAllocation(HeapArray<C>{16});
}

// Test allocations close to the size of the address space.
TEST_F(HeapArrayTest, OutOfMemoryAtLimit) {
    // Allocation of uint8_t values
    {
        // Test sizes that are blocked by the HeapArray implementation before trying to allocate,
        // and one element smaller so that HeapArray will actually try to allocate.
        for (size_t leaveSpace : {0, 4094, 4095}) {
            HeapArray<uint8_t> arr{std::numeric_limits<size_t>::max() - leaveSpace, std::nothrow};
            // Access the pointer first to prevent the allocation from being optimized away by
            // the compiler assuming it will succeed.
            EXPECT_EQ(arr.data(), nullptr);
            EXPECT_FALSE(bool{arr});
        }
    }
    // Allocation of uint32_t values
    {
        static constexpr size_t kMaxSize = std::numeric_limits<size_t>::max() / sizeof(uint32_t);

        // Test sizes that are blocked by the HeapArray implementation before trying to allocate,
        // and one element smaller so that HeapArray will actually try to allocate.
        for (size_t leaveSpace : {0, 1022, 1023}) {
            HeapArray<uint32_t> arr{kMaxSize - leaveSpace, std::nothrow};
            // Access the pointer first to prevent the allocation from being optimized away.
            EXPECT_EQ(arr.data(), nullptr);
            EXPECT_FALSE(bool{arr});
        }

        // Cases where size * sizeof(val) is larger than the address space and could overflow.
        {
            HeapArray<uint32_t> arr{kMaxSize + 1, std::nothrow};
            EXPECT_FALSE(bool{arr});
        }
        {
            HeapArray<uint32_t> arr{kMaxSize + 2, std::nothrow};
            EXPECT_FALSE(bool{arr});
        }
    }
}

// 64-bit size is way too large to allocate (but well within size_t on 64-bit).
TEST_F(HeapArrayTest, OutOfMemory64) {
    using Key64 = TypedInteger<struct Key64T, uint64_t>;
    static constexpr Key64 kHugeSize{0x1000'0000'0000'0000u};

    {
        ityp::HeapArray<Key64, Val> arr{kHugeSize, std::nothrow};
        // Access the pointer first to prevent the allocation from being optimized away.
        EXPECT_EQ(arr.data(), nullptr);
        EXPECT_FALSE(bool{arr});
    }
    {
        auto arr =
            // SAFETY: Testing unsafe API.
            DAWN_UNSAFE_BUFFERS(ityp::HeapArray<Key64, int>::Uninit(kHugeSize, std::nothrow));
        // Access the pointer first to prevent the allocation from being optimized away.
        EXPECT_EQ(arr.data(), nullptr);
        EXPECT_FALSE(bool{arr});
    }
}

// Test allocations close to the size of the address space.
TEST_F(HeapArrayDeathTest, OutOfMemoryAtLimit) {
    // We store the allocation's pointer here so the allocation attempt can't be optimized away.
    void* volatile ptr;

    // Allocation of uint8_t values
    {
        // Exact maximum amount that will fit in the address space
        EXPECT_DEATH_IF_SUPPORTED(
            (ptr = HeapArray<uint8_t>{std::numeric_limits<size_t>::max()}.data()), "");
        // And a bit less.
        EXPECT_DEATH_IF_SUPPORTED(
            (ptr = HeapArray<uint8_t>{std::numeric_limits<size_t>::max() - 4095}.data()), "");
    }
    // Allocation of uint32_t values
    {
        static constexpr size_t kMaxSize = std::numeric_limits<size_t>::max() / sizeof(uint32_t);
        // Maximum amount that will fit in the address space
        EXPECT_DEATH_IF_SUPPORTED((ptr = HeapArray<uint32_t>{kMaxSize}.data()), "");
        // And a bit less.
        EXPECT_DEATH_IF_SUPPORTED((ptr = HeapArray<uint32_t>{kMaxSize - 1023}.data()), "");

        // Cases where size * sizeof(val) is larger than the address space and could overflow.
        EXPECT_DEATH_IF_SUPPORTED((ptr = HeapArray<uint32_t>{kMaxSize + 1}.data()), "");
        EXPECT_DEATH_IF_SUPPORTED((ptr = HeapArray<uint32_t>{kMaxSize + 2}.data()), "");
    }
}

// 64-bit size is way too large to allocate (but well within size_t on 64-bit).
TEST_F(HeapArrayDeathTest, OutOfMemory64) {
    using Key64 = TypedInteger<struct Key64T, uint64_t>;
    static constexpr Key64 kHugeSize{0x1000'0000'0000'0000u};

    // We store the allocation's pointer here so the allocation attempt can't be optimized away.
    void* volatile ptr;

    EXPECT_DEATH_IF_SUPPORTED((ptr = ityp::HeapArray<Key64, Val>{kHugeSize}.data()), "");
    EXPECT_DEATH_IF_SUPPORTED(
        // SAFETY: Testing unsafe API.
        (ptr = DAWN_UNSAFE_BUFFERS(ityp::HeapArray<Key64, int>::Uninit(kHugeSize)).data()), "");
}

// Out of bounds accesses should crash even in release (the underlying container
// should have asserts enabled).
TEST_F(HeapArrayDeathTest, OutOfBounds) {
    // MSVC doesn't have asserts (without _MSVC_STL_HARDENING).
    if constexpr (DAWN_COMPILER_IS(MSVC)) {
        GTEST_SKIP();
    }

    HeapArrayVal arr{Index{10u}};
    EXPECT_DEATH_IF_SUPPORTED(arr[Index{10u}], "");

    const HeapArrayVal& constArr = arr;
    EXPECT_DEATH_IF_SUPPORTED(constArr[Index{10u}], "");
}

// If the index/size is 64-bit, it needs to be narrowed to size_t. Verify that's checked correctly.
TEST_F(HeapArrayDeathTest, OversizedIndex) {
    // These tests are only relevant on 32-bit builds.
    if constexpr (sizeof(size_t) > sizeof(uint32_t)) {
        GTEST_SKIP();
    }

    using Key64 = TypedInteger<struct Key64T, uint64_t>;
    static constexpr Key64 kHugeKey64{0x1000'0000'0000'0000u};

    // Crash either due to OOM (on 64-bit) or due to narrowing (on 32-bit).
    EXPECT_DEATH_IF_SUPPORTED((ityp::HeapArray<Key64, Val>(kHugeKey64)), "");

    ityp::HeapArray<Key64, Val> vec(Key64{10u});

    vec[Key64{9u}];
    // Regular out-of-bounds.
    EXPECT_DEATH_IF_SUPPORTED(vec[Key64{10u}], "");

    vec[Key64{0u}];
    // If this were cast to a 32-bit size_t without a check, it would be in-bounds.
    EXPECT_DEATH_IF_SUPPORTED(vec[kHugeKey64], "");
}

// Using uninitialized memory should crash on MSan builds.
TEST_F(HeapArrayDeathTest, ReadUninitWithPODType) {
    if constexpr (!DAWN_MSAN_ENABLED()) {
        GTEST_SKIP();
    }

    // SAFETY: Testing unsafe API.
    auto arr = DAWN_UNSAFE_BUFFERS(HeapArrayPOD::Uninit(Index{1u}));
    EXPECT_DEATH_IF_SUPPORTED([&]() { printf("%d\n", arr[Index{0u}]); }(), "");
}

}  // anonymous namespace
}  // namespace dawn