// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstdlib>
#include <stdexcept>
#include <string>
#include <type_traits>

using namespace std;

#define STATIC_ASSERT(...) static_assert(__VA_ARGS__, #__VA_ARGS__)

// Also test LWG-4140 "Useless default constructors for bit reference types" for bitset<N>::reference.
namespace lwg_4140 {
    struct default_constructible_type {};

    void test_default_constructor(default_constructible_type) {}
    void test_default_constructor(bitset<0>::reference) {}
    void test_default_constructor(bitset<1>::reference) {}
    void test_default_constructor(bitset<8>::reference) {}
    void test_default_constructor(bitset<16>::reference) {}
    void test_default_constructor(bitset<32>::reference) {}
    void test_default_constructor(bitset<48>::reference) {}
    void test_default_constructor(bitset<64>::reference) {}
    void test_default_constructor(bitset<96>::reference) {}

    void test() { // COMPILE-ONLY
        test_default_constructor({});
    }
} // namespace lwg_4140

// Also test LWG-4294 "bitset(const CharT*) constructor needs to be constrained".

template <size_t Len, class Elem, bool Expected>
void test_ntcts_constructibility_single() { // COMPILE-ONLY
    STATIC_ASSERT(is_constructible_v<bitset<Len>, Elem*, size_t, Elem, Elem> == Expected);
    STATIC_ASSERT(is_constructible_v<bitset<Len>, const Elem*, size_t, Elem, Elem> == Expected);
    // the constructor is explicit
    STATIC_ASSERT(!is_convertible_v<Elem*, bitset<Len>>);
    STATIC_ASSERT(!is_convertible_v<const Elem*, bitset<Len>>);
}

template <class Elem, bool Expected>
void test_ntcts_constructibility_for_lengths() { // COMPILE-ONLY
    test_ntcts_constructibility_single<0, Elem, Expected>();
    test_ntcts_constructibility_single<1, Elem, Expected>();
    test_ntcts_constructibility_single<8, Elem, Expected>();
    test_ntcts_constructibility_single<16, Elem, Expected>();
    test_ntcts_constructibility_single<32, Elem, Expected>();
    test_ntcts_constructibility_single<48, Elem, Expected>();
    test_ntcts_constructibility_single<64, Elem, Expected>();
    test_ntcts_constructibility_single<96, Elem, Expected>();
}

void test_ntcts_constructibility() { // COMPILE-ONLY
    // test encoded character types (expected usages)
    test_ntcts_constructibility_for_lengths<char, true>();
#ifdef __cpp_char8_t
    test_ntcts_constructibility_for_lengths<char8_t, true>();
#endif // __cpp_char8_t
    test_ntcts_constructibility_for_lengths<char16_t, true>();
    test_ntcts_constructibility_for_lengths<char32_t, true>();
    test_ntcts_constructibility_for_lengths<wchar_t, true>();

    enum unscoped_enum {};
    enum class scoped_enum {};

    struct pod_class {
        int n1;
    };
    struct missing_trivial_default_ctor {
        int n2 = 42;
    };
    struct missing_standard_layout : pod_class {
        int n3;
    };
    struct missing_trivially_copyable {
        missing_trivially_copyable()                                             = default;
        missing_trivially_copyable(const missing_trivially_copyable&)            = default;
        missing_trivially_copyable(missing_trivially_copyable&&)                 = default;
        missing_trivially_copyable& operator=(const missing_trivially_copyable&) = default;
        constexpr missing_trivially_copyable& operator=(missing_trivially_copyable&&) noexcept {
            return *this;
        }
        ~missing_trivially_copyable() = default;
    };

    // test scalar types
    test_ntcts_constructibility_for_lengths<int, true>();
    test_ntcts_constructibility_for_lengths<char*, true>();
    test_ntcts_constructibility_for_lengths<void (*)(), true>();
    test_ntcts_constructibility_for_lengths<unscoped_enum, true>();
    test_ntcts_constructibility_for_lengths<scoped_enum, true>();
    test_ntcts_constructibility_for_lengths<int missing_trivial_default_ctor::*, true>();
    test_ntcts_constructibility_for_lengths<void (missing_standard_layout::*)() const&, true>();

    // test POD array types
    test_ntcts_constructibility_for_lengths<char[1], false>();
    test_ntcts_constructibility_for_lengths<char[1][2], false>();
#ifdef __cpp_char8_t
    test_ntcts_constructibility_for_lengths<char8_t[2], false>();
    test_ntcts_constructibility_for_lengths<char8_t[2][4], false>();
#endif // __cpp_char8_t
    test_ntcts_constructibility_for_lengths<char16_t[3], false>();
    test_ntcts_constructibility_for_lengths<char16_t[3][6], false>();
    test_ntcts_constructibility_for_lengths<char32_t[4], false>();
    test_ntcts_constructibility_for_lengths<char32_t[4][8], false>();
    test_ntcts_constructibility_for_lengths<wchar_t[5], false>();
    test_ntcts_constructibility_for_lengths<wchar_t[5][10], false>();
    test_ntcts_constructibility_for_lengths<int[6], false>();
    test_ntcts_constructibility_for_lengths<int[6][12][3], false>();
    test_ntcts_constructibility_for_lengths<char* [7], false>();
    test_ntcts_constructibility_for_lengths<char* [7][1][2][14], false>();

    // test class types
    test_ntcts_constructibility_for_lengths<pod_class, true>();
    test_ntcts_constructibility_for_lengths<missing_trivial_default_ctor, false>();
    test_ntcts_constructibility_for_lengths<missing_standard_layout, false>();
    test_ntcts_constructibility_for_lengths<missing_trivially_copyable, false>();

    // test worse class types
    test_ntcts_constructibility_for_lengths<string, false>();
    test_ntcts_constructibility_for_lengths<invalid_argument, false>();
}

const char parsedStr[] = "1000110111110011110111111111111111010111110111100101010100001001"
                         "1111111111111111111111111111111111111111111111111111111111111111"
                         "0111111111111111111111111111111111111111111111111111111111111111"
                         "1111111111111111111111111111111100000000000000000000000000000000";

struct isZero {
    bool operator()(const char c) const noexcept {
        return c == '0';
    }
};

void test_DevDiv917456();
void test_DevDiv931383();
void test_VSO_742338();
void test_Getword();

int main() {
    {
        bitset<5> b;

        assert(b.to_string() == "00000");
    }


    {
        bitset<5> b(23);

        assert(b.to_string() == "10111");
    }

    {
        bitset<5> b(29UL);

        assert(b.to_string() == "11101");
    }

    {
        bitset<5> b(25ULL);

        assert(b.to_string() == "11001");
    }


    {
        wstring w(L"10011");

        bitset<5> b(w);

        assert(b.to_string() == "10011");
    }

    {
        wstring w(L"zzz01000");

        bitset<5> b(w, 3);

        assert(b.to_string() == "01000");
    }

    {
        wstring w(L"zzz00010zzz");

        bitset<5> b(w, 3, 5);

        assert(b.to_string() == "00010");
    }

    {
        wstring w(L"zzz.11..zzz");

        bitset<5> b(w, 3, 5, L'.');

        assert(b.to_string() == "01100");
    }

    {
        wstring w(L"zzz..!!.zzz");

        bitset<5> b(w, 3, 5, L'.', L'!');

        assert(b.to_string() == "00110");
    }


    {
        bitset<5> b(L"10011");

        assert(b.to_string() == "10011");
    }

    {
        const wchar_t* const ptr = L"zzz01000";

        bitset<5> b(ptr + 3);

        assert(b.to_string() == "01000");
    }

    {
        const wchar_t* const ptr = L"zzz00010zzz";

        bitset<5> b(ptr + 3, 5);

        assert(b.to_string() == "00010");
    }

    {
        const wchar_t* const ptr = L"zzz.11..zzz";

        bitset<5> b(ptr + 3, 5, L'.');

        assert(b.to_string() == "01100");
    }

    {
        const wchar_t* const ptr = L"zzz..!!.zzz";

        bitset<5> b(ptr + 3, 5, L'.', L'!');

        assert(b.to_string() == "00110");
    }

    test_DevDiv917456();
    test_DevDiv931383();
    test_VSO_742338();
    test_Getword();
}

// Also test DevDiv-917456 "<bitset>: none() and any() return incorrect count after call set() function in a
// std::bitset<0> object [libcxx]".
void test_bitset0(const bitset<0>& b) {
    assert(b.to_ulong() == 0);
    assert(b.to_ullong() == 0);
    assert(b.to_string() == "");
    assert(b.count() == 0);
    assert(b.all());
    assert(!b.any());
    assert(b.none());
}

void test_DevDiv917456() {
    {
        bitset<0> b;
        test_bitset0(b);
    }

    {
        bitset<0> b;
        b.set();
        test_bitset0(b);
    }

    {
        bitset<0> b;
        b.reset();
        test_bitset0(b);
    }

    {
        bitset<0> b;
        b.flip();
        test_bitset0(b);
    }

    {
        bitset<0> b(0xFFFFFFFFFFFFFFFFULL);
        test_bitset0(b);
    }
}

// Also test DevDiv-931383 "<bitset>: We need to validate all characters and use traits::eq()".
void test(const string& str, const size_t pos, const size_t n, const string& expected) noexcept {
    try {
        bitset<8> b(str, pos, n, 'o', 'i');
        assert(b.to_string() == expected);
    } catch (const invalid_argument&) {
        assert(expected == "invalid_argument");
    } catch (const out_of_range&) {
        assert(expected == "out_of_range");
    }
}

void test_DevDiv931383() {
    // N3936 20.6.1 [bitset.cons]/4: "Throws: out_of_range if pos > str.size()."
    test("AAAA", 5, 0, "out_of_range");

    // /5: "Effects: Determines the effective length rlen of the initializing string
    // as the smaller of n and str.size() - pos. The function then throws invalid_argument
    // if any of the rlen characters in str beginning at position pos is other than zero or one."
    test("oiooiiioBBB", 0, string::npos, "invalid_argument");

    // "Otherwise, the function constructs an object of class bitset<N>, initializing
    // the first M bit positions to values determined from the corresponding characters
    // in the string str. M is the smaller of N and rlen."
    test("oiiiiiooiiiiCCC", 0, 12, "01111100");
    test("DDDoiooiiioEEE", 3, 8, "01001110");

    // /6-7: "Character position pos + M - 1 corresponds to bit position zero.
    // Subsequent decreasing character positions correspond to increasing bit positions.
    // If M < N, remaining bit positions are initialized to zero."
    test("FFiioiiiGG", 2, 6, "00110111");
}

// Also test Dev10-479284 "C6326 when running static analysis with <bitset>".
template class std::bitset<7>;
template class std::bitset<32>;

template class std::bitset<47>;
template class std::bitset<64>;

template class std::bitset<1729>;
template class std::bitset<2048>;

template <size_t bitsetBits>
void test_VSO_742338_case(size_t useLength) {
    // This tests for a case where a bitset which needs multiple words internally reversed the order of those words.
    const bitset<bitsetBits> bits(parsedStr, useLength);
    auto asStr          = bits.to_string();
    const auto division = asStr.begin() + static_cast<ptrdiff_t>(bitsetBits - useLength);
    assert(all_of(asStr.begin(), division, isZero{}));
    assert(equal(division, asStr.end(), parsedStr));
    reverse(asStr.begin(), asStr.end());
    for (size_t idx = 0; idx < useLength; ++idx) {
        assert(bits[idx] == (asStr[idx] == '1'));
    }
    for (size_t idx = useLength; idx < bitsetBits; ++idx) {
        assert(!bits[idx]);
    }
}

void test_VSO_742338() {
    for (size_t idx = 0; idx <= 25; ++idx) {
        test_VSO_742338_case<25>(idx);
    }

    for (size_t idx = 0; idx <= 256; ++idx) {
        test_VSO_742338_case<256>(idx);
    }
}

void test_Getword() {
    // Tests nonstandard extension _Getword which we provide for performance-sensitive scenarios where DirectX needed
    // access to the array inside the bitset.
    STATIC_ASSERT(is_same_v<unsigned long, decltype(bitset<16>{}._Getword(0))>);
    STATIC_ASSERT(is_same_v<unsigned long, decltype(bitset<32>{}._Getword(0))>);
    STATIC_ASSERT(is_same_v<unsigned long long, decltype(bitset<33>{}._Getword(0))>);
    STATIC_ASSERT(is_same_v<unsigned long long, decltype(bitset<64>{}._Getword(0))>);
    STATIC_ASSERT(is_same_v<unsigned long long, decltype(bitset<65>{}._Getword(0))>);
    const bitset<16> bits16(parsedStr);
    assert(bits16._Getword(0) == 36339ul);
    const bitset<256> bits256(parsedStr);
    assert(bits256._Getword(0) == 18446744069414584320ull);
    assert(bits256._Getword(1) == 9223372036854775807ull);
    assert(bits256._Getword(2) == 18446744073709551615ull);
    assert(bits256._Getword(3) == 10228765468619855113ull);
}
