summaryrefslogtreecommitdiff
path: root/Tests/AK
diff options
context:
space:
mode:
authorBrian Gianforcaro <bgianf@serenityos.org>2021-05-06 01:19:30 -0700
committerAndreas Kling <kling@serenityos.org>2021-05-06 17:54:28 +0200
commit67322b0702836807e29265e86556ebf43bb9d510 (patch)
tree86d2e2099ecc377cf11ddcf9106c500969b1afbb /Tests/AK
parentfd0dbd1ebfbcbc29d46393061daa49dc7390caa7 (diff)
downloadserenity-67322b0702836807e29265e86556ebf43bb9d510.zip
Tests: Move AK tests to Tests/AK
Diffstat (limited to 'Tests/AK')
-rw-r--r--Tests/AK/CMakeLists.txt69
-rw-r--r--Tests/AK/TestAllOf.cpp21
-rw-r--r--Tests/AK/TestAnyOf.cpp23
-rw-r--r--Tests/AK/TestArray.cpp30
-rw-r--r--Tests/AK/TestAtomic.cpp342
-rw-r--r--Tests/AK/TestBadge.cpp14
-rw-r--r--Tests/AK/TestBase64.cpp46
-rw-r--r--Tests/AK/TestBinaryHeap.cpp67
-rw-r--r--Tests/AK/TestBinarySearch.cpp118
-rw-r--r--Tests/AK/TestBitCast.cpp23
-rw-r--r--Tests/AK/TestBitmap.cpp250
-rw-r--r--Tests/AK/TestByteBuffer.cpp51
-rw-r--r--Tests/AK/TestChecked.cpp388
-rw-r--r--Tests/AK/TestCircularDeque.cpp63
-rw-r--r--Tests/AK/TestCircularDuplexStream.cpp63
-rw-r--r--Tests/AK/TestCircularQueue.cpp68
-rw-r--r--Tests/AK/TestComplex.cpp44
-rw-r--r--Tests/AK/TestDistinctNumeric.cpp285
-rw-r--r--Tests/AK/TestDoublyLinkedList.cpp43
-rw-r--r--Tests/AK/TestEndian.cpp17
-rw-r--r--Tests/AK/TestEnumBits.cpp69
-rw-r--r--Tests/AK/TestFind.cpp54
-rw-r--r--Tests/AK/TestFormat.cpp291
-rw-r--r--Tests/AK/TestGenericLexer.cpp158
-rw-r--r--Tests/AK/TestHashFunctions.cpp61
-rw-r--r--Tests/AK/TestHashMap.cpp174
-rw-r--r--Tests/AK/TestHashTable.cpp175
-rw-r--r--Tests/AK/TestHex.cpp61
-rw-r--r--Tests/AK/TestIPv4Address.cpp153
-rw-r--r--Tests/AK/TestIndexSequence.cpp49
-rw-r--r--Tests/AK/TestIntrusiveList.cpp123
-rw-r--r--Tests/AK/TestIntrusiveRedBlackTree.cpp116
-rw-r--r--Tests/AK/TestJSON.cpp100
-rw-r--r--Tests/AK/TestLexicalPath.cpp76
-rw-r--r--Tests/AK/TestMACAddress.cpp84
-rw-r--r--Tests/AK/TestMemMem.cpp68
-rw-r--r--Tests/AK/TestMemoryStream.cpp222
-rw-r--r--Tests/AK/TestNeverDestroyed.cpp73
-rw-r--r--Tests/AK/TestNonnullRefPtr.cpp61
-rw-r--r--Tests/AK/TestNumberFormat.cpp127
-rw-r--r--Tests/AK/TestOptional.cpp55
-rw-r--r--Tests/AK/TestQueue.cpp59
-rw-r--r--Tests/AK/TestQuickSort.cpp100
-rw-r--r--Tests/AK/TestRedBlackTree.cpp88
-rw-r--r--Tests/AK/TestRefPtr.cpp149
-rw-r--r--Tests/AK/TestSinglyLinkedList.cpp61
-rw-r--r--Tests/AK/TestSourceGenerator.cpp71
-rw-r--r--Tests/AK/TestSourceLocation.cpp32
-rw-r--r--Tests/AK/TestSpan.cpp125
-rw-r--r--Tests/AK/TestString.cpp237
-rw-r--r--Tests/AK/TestStringUtils.cpp306
-rw-r--r--Tests/AK/TestStringView.cpp179
-rw-r--r--Tests/AK/TestTime.cpp263
-rw-r--r--Tests/AK/TestTrie.cpp68
-rw-r--r--Tests/AK/TestTypeTraits.cpp107
-rw-r--r--Tests/AK/TestTypedTransfer.cpp41
-rw-r--r--Tests/AK/TestURL.cpp202
-rw-r--r--Tests/AK/TestUtf8.cpp69
-rw-r--r--Tests/AK/TestVariant.cpp112
-rw-r--r--Tests/AK/TestVector.cpp401
-rw-r--r--Tests/AK/TestWeakPtr.cpp66
l---------Tests/AK/test.frm1
62 files changed, 7112 insertions, 0 deletions
diff --git a/Tests/AK/CMakeLists.txt b/Tests/AK/CMakeLists.txt
new file mode 100644
index 0000000000..ff0d6b0119
--- /dev/null
+++ b/Tests/AK/CMakeLists.txt
@@ -0,0 +1,69 @@
+set(AK_TEST_SOURCES
+ TestAllOf.cpp
+ TestAnyOf.cpp
+ TestArray.cpp
+ TestAtomic.cpp
+ TestBadge.cpp
+ TestBase64.cpp
+ TestBinaryHeap.cpp
+ TestBinarySearch.cpp
+ TestBitCast.cpp
+ TestBitmap.cpp
+ TestByteBuffer.cpp
+ TestChecked.cpp
+ TestCircularDeque.cpp
+ TestCircularDuplexStream.cpp
+ TestCircularQueue.cpp
+ TestComplex.cpp
+ TestDistinctNumeric.cpp
+ TestDoublyLinkedList.cpp
+ TestEndian.cpp
+ TestEnumBits.cpp
+ TestFind.cpp
+ TestFormat.cpp
+ TestGenericLexer.cpp
+ TestHashFunctions.cpp
+ TestHashMap.cpp
+ TestHashTable.cpp
+ TestHex.cpp
+ TestIPv4Address.cpp
+ TestIndexSequence.cpp
+ TestIntrusiveList.cpp
+ TestIntrusiveRedBlackTree.cpp
+ TestJSON.cpp
+ TestLexicalPath.cpp
+ TestMACAddress.cpp
+ TestMemMem.cpp
+ TestMemoryStream.cpp
+ TestNeverDestroyed.cpp
+ TestNonnullRefPtr.cpp
+ TestNumberFormat.cpp
+ TestOptional.cpp
+ TestQueue.cpp
+ TestQuickSort.cpp
+ TestRedBlackTree.cpp
+ TestRefPtr.cpp
+ TestSinglyLinkedList.cpp
+ TestSourceGenerator.cpp
+ TestSourceLocation.cpp
+ TestSpan.cpp
+ TestString.cpp
+ TestStringUtils.cpp
+ TestStringView.cpp
+ TestTime.cpp
+ TestTrie.cpp
+ TestTypeTraits.cpp
+ TestTypedTransfer.cpp
+ TestURL.cpp
+ TestUtf8.cpp
+ TestVariant.cpp
+ TestVector.cpp
+ TestWeakPtr.cpp
+)
+
+foreach(source ${AK_TEST_SOURCES})
+ serenity_test(${source} AK)
+endforeach()
+
+get_filename_component(TEST_FRM_RESOLVED ./test.frm REALPATH)
+install(FILES ${TEST_FRM_RESOLVED} DESTINATION usr/Tests/AK)
diff --git a/Tests/AK/TestAllOf.cpp b/Tests/AK/TestAllOf.cpp
new file mode 100644
index 0000000000..48f5d0f7aa
--- /dev/null
+++ b/Tests/AK/TestAllOf.cpp
@@ -0,0 +1,21 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/AllOf.h>
+#include <AK/Array.h>
+
+TEST_CASE(should_determine_if_predicate_applies_to_all_elements_in_container)
+{
+ constexpr Array<int, 10> a {};
+
+ static_assert(all_of(a.begin(), a.end(), [](auto elem) { return elem == 0; }));
+ static_assert(!all_of(a.begin(), a.end(), [](auto elem) { return elem == 1; }));
+
+ EXPECT(all_of(a.begin(), a.end(), [](auto elem) { return elem == 0; }));
+ EXPECT(!all_of(a.begin(), a.end(), [](auto elem) { return elem == 1; }));
+}
diff --git a/Tests/AK/TestAnyOf.cpp b/Tests/AK/TestAnyOf.cpp
new file mode 100644
index 0000000000..2fcfaf29e6
--- /dev/null
+++ b/Tests/AK/TestAnyOf.cpp
@@ -0,0 +1,23 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/AnyOf.h>
+#include <AK/Array.h>
+
+TEST_CASE(should_determine_if_predicate_applies_to_any_element_in_container)
+{
+ constexpr Array<int, 10> a { 1 };
+
+ static_assert(any_of(a.begin(), a.end(), [](auto elem) { return elem == 0; }));
+ static_assert(any_of(a.begin(), a.end(), [](auto elem) { return elem == 1; }));
+ static_assert(!any_of(a.begin(), a.end(), [](auto elem) { return elem == 2; }));
+
+ EXPECT(any_of(a.begin(), a.end(), [](auto elem) { return elem == 0; }));
+ EXPECT(any_of(a.begin(), a.end(), [](auto elem) { return elem == 1; }));
+ EXPECT(!any_of(a.begin(), a.end(), [](auto elem) { return elem == 2; }));
+}
diff --git a/Tests/AK/TestArray.cpp b/Tests/AK/TestArray.cpp
new file mode 100644
index 0000000000..440a9935ae
--- /dev/null
+++ b/Tests/AK/TestArray.cpp
@@ -0,0 +1,30 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Array.h>
+
+static constexpr int constexpr_sum(const Span<const int> span)
+{
+ int sum = 0;
+ for (auto value : span)
+ sum += value;
+
+ return sum;
+}
+
+TEST_CASE(compile_time_contructible)
+{
+ constexpr Array<int, 4> array = { 0, 1, 2, 3 };
+ static_assert(array.size() == 4);
+}
+
+TEST_CASE(compile_time_iterable)
+{
+ constexpr Array<int, 8> array = { 0, 1, 2, 3, 4, 5, 6, 7 };
+ static_assert(constexpr_sum(array) == 28);
+}
diff --git a/Tests/AK/TestAtomic.cpp b/Tests/AK/TestAtomic.cpp
new file mode 100644
index 0000000000..eb7a3843ef
--- /dev/null
+++ b/Tests/AK/TestAtomic.cpp
@@ -0,0 +1,342 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Atomic.h>
+
+TEST_CASE(construct_empty)
+{
+ EXPECT(Atomic<bool>().load() == false);
+ EXPECT(Atomic<u32>().load() == 0);
+ EXPECT(Atomic<u16>().load() == 0);
+ EXPECT(Atomic<u8>().load() == 0);
+
+ EXPECT(Atomic<u16*>().load() == nullptr);
+}
+
+TEST_CASE(construct_with_value)
+{
+ EXPECT(Atomic<bool>(false).load() == false);
+ EXPECT(Atomic<bool>(true).load() == true);
+ EXPECT(Atomic<u32>(2).load() == 2);
+ EXPECT(Atomic<u16>(3).load() == 3);
+ EXPECT(Atomic<u8>(4).load() == 4);
+
+ u16 v_u16 = 0;
+ EXPECT(Atomic<u16*>(&v_u16).load() == &v_u16);
+}
+
+TEST_CASE(do_exchange)
+{
+ Atomic<bool> a_bool(false);
+ EXPECT(a_bool.exchange(true) == false);
+ EXPECT(a_bool.load() == true && static_cast<bool>(a_bool) == true);
+
+ Atomic<u32> a_u32(2);
+ EXPECT(a_u32.exchange(22) == 2);
+ EXPECT(a_u32.load() == 22 && static_cast<u8>(a_u32) == 22);
+
+ Atomic<u16> a_u16(3);
+ EXPECT(a_u16.exchange(33) == 3);
+ EXPECT(a_u16.load() == 33 && static_cast<u8>(a_u16) == 33);
+
+ Atomic<u8> a_u8(4);
+ EXPECT(a_u8.exchange(44) == 4);
+ EXPECT(a_u8.load() == 44 && static_cast<u8>(a_u8) == 44);
+
+ u16 v_u16[6];
+ Atomic<u16*> a_pu16(&v_u16[2]);
+ EXPECT(a_pu16.load() == &v_u16[2] && static_cast<u16*>(a_pu16) == &v_u16[2]);
+}
+
+TEST_CASE(do_compare_exchange)
+{
+ Atomic<bool> a_bool(false);
+ bool e_bool = true;
+ EXPECT(a_bool.compare_exchange_strong(e_bool, true) == false);
+ EXPECT(e_bool == false);
+ EXPECT(a_bool.load() == false && static_cast<bool>(a_bool) == false);
+ e_bool = false;
+ EXPECT(a_bool.compare_exchange_strong(e_bool, true) == true);
+ EXPECT(a_bool.load() == true && static_cast<bool>(a_bool) == true);
+
+ Atomic<u32> a_u32(2);
+ u32 e_u32 = 99;
+ EXPECT(a_u32.compare_exchange_strong(e_u32, 22) == false);
+ EXPECT(e_u32 == 2);
+ EXPECT(a_u32.load() == 2 && static_cast<u32>(a_u32) == 2);
+ e_u32 = 2;
+ EXPECT(a_u32.compare_exchange_strong(e_u32, 22) == true);
+ EXPECT(a_u32.load() == 22 && static_cast<u32>(a_u32) == 22);
+
+ Atomic<u16> a_u16(3);
+ u16 e_u16 = 99;
+ EXPECT(a_u16.compare_exchange_strong(e_u16, 33) == false);
+ EXPECT(e_u16 == 3);
+ EXPECT(a_u16.load() == 3 && static_cast<u16>(a_u16) == 3);
+ e_u16 = 3;
+ EXPECT(a_u16.compare_exchange_strong(e_u16, 33) == true);
+ EXPECT(a_u16.load() == 33 && static_cast<u16>(a_u16) == 33);
+
+ Atomic<u8> a_u8(4);
+ u8 e_u8 = 99;
+ EXPECT(a_u8.compare_exchange_strong(e_u8, 44) == false);
+ EXPECT(e_u8 == 4);
+ EXPECT(a_u8.load() == 4 && static_cast<u16>(a_u8) == 4);
+ e_u8 = 4;
+ EXPECT(a_u8.compare_exchange_strong(e_u8, 44) == true);
+ EXPECT(a_u8.load() == 44 && static_cast<u16>(a_u8) == 44);
+}
+
+TEST_CASE(fetch_add)
+{
+ Atomic<u32> a_u32(5);
+ EXPECT(a_u32.fetch_add(2) == 5);
+ EXPECT(a_u32.load() == 7 && static_cast<u32>(a_u32) == 7);
+
+ Atomic<u16> a_u16(5);
+ EXPECT(a_u16.fetch_add(2) == 5);
+ EXPECT(a_u16.load() == 7 && static_cast<u16>(a_u16) == 7);
+
+ Atomic<u8> a_u8(5);
+ EXPECT(a_u8.fetch_add(2) == 5);
+ EXPECT(a_u8.load() == 7 && static_cast<u8>(a_u8) == 7);
+
+ u32 v_u32[6];
+ Atomic<u32*> a_pu32(&v_u32[2]);
+ EXPECT(a_pu32.load() == &v_u32[2] && static_cast<u32*>(a_pu32) == &v_u32[2]);
+ EXPECT(a_pu32.fetch_add(2) == &v_u32[2]);
+ EXPECT(a_pu32.load() == &v_u32[4] && static_cast<u32*>(a_pu32) == &v_u32[4]);
+ EXPECT(a_pu32.fetch_add(-3) == &v_u32[4]);
+ EXPECT(a_pu32.load() == &v_u32[1] && static_cast<u32*>(a_pu32) == &v_u32[1]);
+
+ u16 v_u16[6];
+ Atomic<u16*> a_pu16(&v_u16[2]);
+ EXPECT(a_pu16.load() == &v_u16[2] && static_cast<u16*>(a_pu16) == &v_u16[2]);
+ EXPECT(a_pu16.fetch_add(2) == &v_u16[2]);
+ EXPECT(a_pu16.load() == &v_u16[4] && static_cast<u16*>(a_pu16) == &v_u16[4]);
+ EXPECT(a_pu16.fetch_add(-3) == &v_u16[4]);
+ EXPECT(a_pu16.load() == &v_u16[1] && static_cast<u16*>(a_pu16) == &v_u16[1]);
+
+ u8 v_u8[6];
+ Atomic<u8*> a_pu8(&v_u8[2]);
+ EXPECT(a_pu8.load() == &v_u8[2] && static_cast<u8*>(a_pu8) == &v_u8[2]);
+ EXPECT(a_pu8.fetch_add(2) == &v_u8[2]);
+ EXPECT(a_pu8.load() == &v_u8[4] && static_cast<u8*>(a_pu8) == &v_u8[4]);
+ EXPECT(a_pu8.fetch_add(-3) == &v_u8[4]);
+ EXPECT(a_pu8.load() == &v_u8[1] && static_cast<u8*>(a_pu8) == &v_u8[1]);
+}
+
+TEST_CASE(fetch_sub)
+{
+ Atomic<u32> a_u32(5);
+ EXPECT(a_u32.fetch_sub(2) == 5);
+ EXPECT(a_u32.load() == 3 && static_cast<u32>(a_u32) == 3);
+
+ Atomic<u16> a_u16(5);
+ EXPECT(a_u16.fetch_sub(2) == 5);
+ EXPECT(a_u16.load() == 3 && static_cast<u16>(a_u16) == 3);
+
+ Atomic<u8> a_u8(5);
+ EXPECT(a_u8.fetch_sub(2) == 5);
+ EXPECT(a_u8.load() == 3 && static_cast<u8>(a_u8) == 3);
+
+ u32 v_u32[6];
+ Atomic<u32*> a_pu32(&v_u32[2]);
+ EXPECT(a_pu32.load() == &v_u32[2] && static_cast<u32*>(a_pu32) == &v_u32[2]);
+ EXPECT(a_pu32.fetch_sub(2) == &v_u32[2]);
+ EXPECT(a_pu32.load() == &v_u32[0] && static_cast<u32*>(a_pu32) == &v_u32[0]);
+ EXPECT(a_pu32.fetch_sub(-3) == &v_u32[0]);
+ EXPECT(a_pu32.load() == &v_u32[3] && static_cast<u32*>(a_pu32) == &v_u32[3]);
+
+ u16 v_u16[6];
+ Atomic<u16*> a_pu16(&v_u16[2]);
+ EXPECT(a_pu16.load() == &v_u16[2] && static_cast<u16*>(a_pu16) == &v_u16[2]);
+ EXPECT(a_pu16.fetch_sub(2) == &v_u16[2]);
+ EXPECT(a_pu16.load() == &v_u16[0] && static_cast<u16*>(a_pu16) == &v_u16[0]);
+ EXPECT(a_pu16.fetch_sub(-3) == &v_u16[0]);
+ EXPECT(a_pu16.load() == &v_u16[3] && static_cast<u16*>(a_pu16) == &v_u16[3]);
+
+ u8 v_u8[6];
+ Atomic<u8*> a_pu8(&v_u8[2]);
+ EXPECT(a_pu8.load() == &v_u8[2] && static_cast<u8*>(a_pu8) == &v_u8[2]);
+ EXPECT(a_pu8.fetch_sub(2) == &v_u8[2]);
+ EXPECT(a_pu8.load() == &v_u8[0] && static_cast<u8*>(a_pu8) == &v_u8[0]);
+ EXPECT(a_pu8.fetch_sub(-3) == &v_u8[0]);
+ EXPECT(a_pu8.load() == &v_u8[3] && static_cast<u8*>(a_pu8) == &v_u8[3]);
+}
+
+TEST_CASE(fetch_inc)
+{
+ Atomic<u32> a_u32(5);
+ EXPECT(a_u32++ == 5);
+ EXPECT(a_u32.load() == 6 && a_u32 == 6);
+ EXPECT(++a_u32 == 7);
+ EXPECT(a_u32.load() == 7 && a_u32 == 7);
+ EXPECT((a_u32 += 2) == 9);
+ EXPECT(a_u32.load() == 9 && a_u32 == 9);
+
+ Atomic<u16> a_u16(5);
+ EXPECT(a_u16++ == 5);
+ EXPECT(a_u16.load() == 6 && a_u16 == 6);
+ EXPECT(++a_u16 == 7);
+ EXPECT(a_u16.load() == 7 && a_u16 == 7);
+ EXPECT((a_u16 += 2) == 9);
+ EXPECT(a_u16.load() == 9 && a_u16 == 9);
+
+ Atomic<u8> a_u8(5);
+ EXPECT(a_u8++ == 5);
+ EXPECT(a_u8.load() == 6 && a_u8 == 6);
+ EXPECT(++a_u8 == 7);
+ EXPECT(a_u8.load() == 7 && a_u8 == 7);
+ EXPECT((a_u8 += 2) == 9);
+ EXPECT(a_u8.load() == 9 && a_u8 == 9);
+
+ u32 v_u32[8];
+ Atomic<u32*> a_pu32(&v_u32[2]);
+ EXPECT(a_pu32++ == &v_u32[2]);
+ EXPECT(a_pu32.load() == &v_u32[3] && a_pu32 == &v_u32[3]);
+ EXPECT(++a_pu32 == &v_u32[4]);
+ EXPECT(a_pu32.load() == &v_u32[4] && a_pu32 == &v_u32[4]);
+ EXPECT((a_pu32 += 2) == &v_u32[6]);
+ EXPECT(a_pu32.load() == &v_u32[6] && a_pu32 == &v_u32[6]);
+
+ u16 v_u16[8];
+ Atomic<u16*> a_pu16(&v_u16[2]);
+ EXPECT(a_pu16++ == &v_u16[2]);
+ EXPECT(a_pu16.load() == &v_u16[3] && a_pu16 == &v_u16[3]);
+ EXPECT(++a_pu16 == &v_u16[4]);
+ EXPECT(a_pu16.load() == &v_u16[4] && a_pu16 == &v_u16[4]);
+ EXPECT((a_pu16 += 2) == &v_u16[6]);
+ EXPECT(a_pu16.load() == &v_u16[6] && a_pu16 == &v_u16[6]);
+
+ u8 v_u8[8];
+ Atomic<u8*> a_pu8(&v_u8[2]);
+ EXPECT(a_pu8++ == &v_u8[2]);
+ EXPECT(a_pu8.load() == &v_u8[3] && a_pu8 == &v_u8[3]);
+ EXPECT(++a_pu8 == &v_u8[4]);
+ EXPECT(a_pu8.load() == &v_u8[4] && a_pu8 == &v_u8[4]);
+ EXPECT((a_pu8 += 2) == &v_u8[6]);
+ EXPECT(a_pu8.load() == &v_u8[6] && a_pu8 == &v_u8[6]);
+}
+
+TEST_CASE(fetch_dec)
+{
+ Atomic<u32> a_u32(5);
+ EXPECT(a_u32-- == 5);
+ EXPECT(a_u32.load() == 4 && a_u32 == 4);
+ EXPECT(--a_u32 == 3);
+ EXPECT(a_u32.load() == 3 && a_u32 == 3);
+ EXPECT((a_u32 -= 2) == 1);
+ EXPECT(a_u32.load() == 1 && a_u32 == 1);
+
+ Atomic<u16> a_u16(5);
+ EXPECT(a_u16-- == 5);
+ EXPECT(a_u16.load() == 4 && a_u16 == 4);
+ EXPECT(--a_u16 == 3);
+ EXPECT(a_u16.load() == 3 && a_u16 == 3);
+ EXPECT((a_u16 -= 2) == 1);
+ EXPECT(a_u16.load() == 1 && a_u16 == 1);
+
+ Atomic<u8> a_u8(5);
+ EXPECT(a_u8-- == 5);
+ EXPECT(a_u8.load() == 4 && a_u8 == 4);
+ EXPECT(--a_u8 == 3);
+ EXPECT(a_u8.load() == 3 && a_u8 == 3);
+ EXPECT((a_u8 -= 2) == 1);
+ EXPECT(a_u8.load() == 1 && a_u8 == 1);
+
+ u32 v_u32[8];
+ Atomic<u32*> a_pu32(&v_u32[7]);
+ EXPECT(a_pu32-- == &v_u32[7]);
+ EXPECT(a_pu32.load() == &v_u32[6] && a_pu32 == &v_u32[6]);
+ EXPECT(--a_pu32 == &v_u32[5]);
+ EXPECT(a_pu32.load() == &v_u32[5] && a_pu32 == &v_u32[5]);
+ EXPECT((a_pu32 -= 2) == &v_u32[3]);
+ EXPECT(a_pu32.load() == &v_u32[3] && a_pu32 == &v_u32[3]);
+
+ u16 v_u16[8];
+ Atomic<u16*> a_pu16(&v_u16[7]);
+ EXPECT(a_pu16-- == &v_u16[7]);
+ EXPECT(a_pu16.load() == &v_u16[6] && a_pu16 == &v_u16[6]);
+ EXPECT(--a_pu16 == &v_u16[5]);
+ EXPECT(a_pu16.load() == &v_u16[5] && a_pu16 == &v_u16[5]);
+ EXPECT((a_pu16 -= 2) == &v_u16[3]);
+ EXPECT(a_pu16.load() == &v_u16[3] && a_pu16 == &v_u16[3]);
+
+ u8 v_u8[8];
+ Atomic<u8*> a_pu8(&v_u8[7]);
+ EXPECT(a_pu8-- == &v_u8[7]);
+ EXPECT(a_pu8.load() == &v_u8[6] && a_pu8 == &v_u8[6]);
+ EXPECT(--a_pu8 == &v_u8[5]);
+ EXPECT(a_pu8.load() == &v_u8[5] && a_pu8 == &v_u8[5]);
+ EXPECT((a_pu8 -= 2) == &v_u8[3]);
+ EXPECT(a_pu8.load() == &v_u8[3] && a_pu8 == &v_u8[3]);
+}
+
+TEST_CASE(fetch_and)
+{
+ Atomic<u32> a_u32(0xdeadbeef);
+ EXPECT(a_u32.fetch_and(0x8badf00d) == 0xdeadbeef);
+ EXPECT(a_u32.load() == 0x8aadb00d && static_cast<u32>(a_u32) == 0x8aadb00d);
+ a_u32 = 0xdeadbeef;
+ EXPECT((a_u32 &= 0x8badf00d) == 0x8aadb00d);
+
+ Atomic<u16> a_u16(0xbeef);
+ EXPECT(a_u16.fetch_and(0xf00d) == 0xbeef);
+ EXPECT(a_u16.load() == 0xb00d && static_cast<u16>(a_u16) == 0xb00d);
+ a_u16 = 0xbeef;
+ EXPECT((a_u16 &= 0xf00d) == 0xb00d);
+
+ Atomic<u8> a_u8(0xef);
+ EXPECT(a_u8.fetch_and(0x0d) == 0xef);
+ EXPECT(a_u8.load() == 0x0d && static_cast<u8>(a_u8) == 0x0d);
+ a_u8 = 0xef;
+ EXPECT((a_u8 &= 0x0d) == 0x0d);
+}
+
+TEST_CASE(fetch_or)
+{
+ Atomic<u32> a_u32(0xaadb00d);
+ EXPECT(a_u32.fetch_or(0xdeadbeef) == 0xaadb00d);
+ EXPECT(a_u32.load() == 0xdeadbeef && static_cast<u32>(a_u32) == 0xdeadbeef);
+ a_u32 = 0xaadb00d;
+ EXPECT((a_u32 |= 0xdeadbeef) == 0xdeadbeef);
+
+ Atomic<u16> a_u16(0xb00d);
+ EXPECT(a_u16.fetch_or(0xbeef) == 0xb00d);
+ EXPECT(a_u16.load() == 0xbeef && static_cast<u16>(a_u16) == 0xbeef);
+ a_u16 = 0xb00d;
+ EXPECT((a_u16 |= 0xbeef) == 0xbeef);
+
+ Atomic<u8> a_u8(0x0d);
+ EXPECT(a_u8.fetch_or(0xef) == 0x0d);
+ EXPECT(a_u8.load() == 0xef && static_cast<u8>(a_u8) == 0xef);
+ a_u8 = 0x0d;
+ EXPECT((a_u8 |= 0xef) == 0xef);
+}
+
+TEST_CASE(fetch_xor)
+{
+ Atomic<u32> a_u32(0x55004ee2);
+ EXPECT(a_u32.fetch_xor(0xdeadbeef) == 0x55004ee2);
+ EXPECT(a_u32.load() == 0x8badf00d && static_cast<u32>(a_u32) == 0x8badf00d);
+ a_u32 = 0x55004ee2;
+ EXPECT((a_u32 ^= 0xdeadbeef) == 0x8badf00d);
+
+ Atomic<u16> a_u16(0x4ee2);
+ EXPECT(a_u16.fetch_xor(0xbeef) == 0x4ee2);
+ EXPECT(a_u16.load() == 0xf00d && static_cast<u16>(a_u16) == 0xf00d);
+ a_u16 = 0x4ee2;
+ EXPECT((a_u16 ^= 0xbeef) == 0xf00d);
+
+ Atomic<u8> a_u8(0xe2);
+ EXPECT(a_u8.fetch_xor(0xef) == 0xe2);
+ EXPECT(a_u8.load() == 0x0d && static_cast<u8>(a_u8) == 0x0d);
+ a_u8 = 0xe2;
+ EXPECT((a_u8 ^= 0xef) == 0x0d);
+}
diff --git a/Tests/AK/TestBadge.cpp b/Tests/AK/TestBadge.cpp
new file mode 100644
index 0000000000..8f12b9dcb3
--- /dev/null
+++ b/Tests/AK/TestBadge.cpp
@@ -0,0 +1,14 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Badge.h>
+
+TEST_CASE(should_provide_underlying_type)
+{
+ static_assert(IsSame<int, Badge<int>::Type>);
+}
diff --git a/Tests/AK/TestBase64.cpp b/Tests/AK/TestBase64.cpp
new file mode 100644
index 0000000000..698a86c354
--- /dev/null
+++ b/Tests/AK/TestBase64.cpp
@@ -0,0 +1,46 @@
+/*
+ * Copyright (c) 2020, Tom Lebreux <tomlebreux@hotmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Base64.h>
+#include <AK/ByteBuffer.h>
+#include <AK/String.h>
+#include <string.h>
+
+TEST_CASE(test_decode)
+{
+ auto decode_equal = [&](const char* input, const char* expected) {
+ auto decoded = decode_base64(StringView(input));
+ EXPECT(String::copy(decoded) == String(expected));
+ EXPECT(StringView(expected).length() <= calculate_base64_decoded_length(StringView(input).bytes()));
+ };
+
+ decode_equal("", "");
+ decode_equal("Zg==", "f");
+ decode_equal("Zm8=", "fo");
+ decode_equal("Zm9v", "foo");
+ decode_equal("Zm9vYg==", "foob");
+ decode_equal("Zm9vYmE=", "fooba");
+ decode_equal("Zm9vYmFy", "foobar");
+}
+
+TEST_CASE(test_encode)
+{
+ auto encode_equal = [&](const char* input, const char* expected) {
+ auto encoded = encode_base64({ input, strlen(input) });
+ EXPECT(encoded == String(expected));
+ EXPECT_EQ(StringView(expected).length(), calculate_base64_encoded_length(StringView(input).bytes()));
+ };
+
+ encode_equal("", "");
+ encode_equal("f", "Zg==");
+ encode_equal("fo", "Zm8=");
+ encode_equal("foo", "Zm9v");
+ encode_equal("foob", "Zm9vYg==");
+ encode_equal("fooba", "Zm9vYmE=");
+ encode_equal("foobar", "Zm9vYmFy");
+}
diff --git a/Tests/AK/TestBinaryHeap.cpp b/Tests/AK/TestBinaryHeap.cpp
new file mode 100644
index 0000000000..dbd4a9a4af
--- /dev/null
+++ b/Tests/AK/TestBinaryHeap.cpp
@@ -0,0 +1,67 @@
+/*
+ * Copyright (c) 2021, Idan Horowitz <idan.horowitz@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/BinaryHeap.h>
+#include <AK/String.h>
+
+TEST_CASE(construct)
+{
+ BinaryHeap<int, int, 5> empty;
+ EXPECT(empty.is_empty());
+ EXPECT(empty.size() == 0);
+}
+
+TEST_CASE(construct_from_existing)
+{
+ int keys[] = { 3, 2, 1 };
+ char values[] = { 'c', 'b', 'a' };
+ BinaryHeap<int, char, 5> from_existing(keys, values, 3);
+ EXPECT(from_existing.size() == 3);
+ EXPECT_EQ(from_existing.pop_min(), 'a');
+ EXPECT_EQ(from_existing.pop_min(), 'b');
+ EXPECT_EQ(from_existing.pop_min(), 'c');
+}
+
+TEST_CASE(populate_int)
+{
+ BinaryHeap<int, int, 5> ints;
+ ints.insert(1, 10);
+ ints.insert(3, 20);
+ ints.insert(2, 30);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(ints.pop_min(), 10);
+ EXPECT_EQ(ints.size(), 2u);
+ EXPECT_EQ(ints.pop_min(), 30);
+ EXPECT_EQ(ints.size(), 1u);
+ EXPECT_EQ(ints.pop_min(), 20);
+ EXPECT_EQ(ints.size(), 0u);
+}
+
+TEST_CASE(populate_string)
+{
+ BinaryHeap<int, String, 5> strings;
+ strings.insert(1, "ABC");
+ strings.insert(2, "DEF");
+ EXPECT_EQ(strings.size(), 2u);
+ EXPECT_EQ(strings.pop_min(), "ABC");
+ EXPECT_EQ(strings.pop_min(), "DEF");
+ EXPECT(strings.is_empty());
+}
+
+TEST_CASE(large_populate_reverse)
+{
+ BinaryHeap<int, int, 1024> ints;
+ for (int i = 1023; i >= 0; i--) {
+ ints.insert(i, i);
+ }
+ EXPECT_EQ(ints.size(), 1024u);
+ for (int i = 0; i < 1024; i++) {
+ EXPECT_EQ(ints.peek_min(), i);
+ EXPECT_EQ(ints.pop_min(), i);
+ }
+}
diff --git a/Tests/AK/TestBinarySearch.cpp b/Tests/AK/TestBinarySearch.cpp
new file mode 100644
index 0000000000..3e5d65c240
--- /dev/null
+++ b/Tests/AK/TestBinarySearch.cpp
@@ -0,0 +1,118 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/BinarySearch.h>
+#include <AK/Span.h>
+#include <cstring>
+#include <new>
+
+TEST_CASE(vector_ints)
+{
+ Vector<int> ints;
+ ints.append(1);
+ ints.append(2);
+ ints.append(3);
+
+ auto test1 = *binary_search(ints, 1);
+ auto test2 = *binary_search(ints, 2);
+ auto test3 = *binary_search(ints, 3);
+ EXPECT_EQ(test1, 1);
+ EXPECT_EQ(test2, 2);
+ EXPECT_EQ(test3, 3);
+}
+
+TEST_CASE(span_rvalue_reference)
+{
+ Array<long, 3> array { 1, 2, 3 };
+
+ size_t nearby_index = 0;
+ auto* pointer = binary_search(array.span(), 2, &nearby_index);
+
+ EXPECT_EQ(nearby_index, 1u);
+ EXPECT_EQ(pointer, &array[1]);
+}
+
+TEST_CASE(array_doubles)
+{
+ Array<double, 3> array { 1.1, 9.9, 33.33 };
+
+ EXPECT_EQ(binary_search(array, 1.1), &array[0]);
+ EXPECT_EQ(binary_search(array, 33.33), &array[2]);
+ EXPECT_EQ(binary_search(array, 9.9), &array[1]);
+}
+
+TEST_CASE(vector_strings)
+{
+ Vector<String> strings;
+ strings.append("bat");
+ strings.append("cat");
+ strings.append("dog");
+
+ auto string_compare = [](const String& a, const String& b) -> int {
+ return strcmp(a.characters(), b.characters());
+ };
+ auto test1 = *binary_search(strings, String("bat"), nullptr, string_compare);
+ auto test2 = *binary_search(strings, String("cat"), nullptr, string_compare);
+ auto test3 = *binary_search(strings, String("dog"), nullptr, string_compare);
+ EXPECT_EQ(test1, String("bat"));
+ EXPECT_EQ(test2, String("cat"));
+ EXPECT_EQ(test3, String("dog"));
+}
+
+TEST_CASE(single_element)
+{
+ Vector<int> ints;
+ ints.append(1);
+
+ auto test1 = *binary_search(ints, 1);
+ EXPECT_EQ(test1, 1);
+}
+
+TEST_CASE(not_found)
+{
+ Vector<int> ints;
+ ints.append(1);
+ ints.append(2);
+ ints.append(3);
+
+ auto test1 = binary_search(ints, -1);
+ auto test2 = binary_search(ints, 0);
+ auto test3 = binary_search(ints, 4);
+ EXPECT_EQ(test1, nullptr);
+ EXPECT_EQ(test2, nullptr);
+ EXPECT_EQ(test3, nullptr);
+}
+
+TEST_CASE(no_elements)
+{
+ Vector<int> ints;
+
+ auto test1 = binary_search(ints, 1);
+ EXPECT_EQ(test1, nullptr);
+}
+
+TEST_CASE(constexpr_array_search)
+{
+ constexpr Array<int, 3> array = { 1, 17, 42 };
+
+ static_assert(binary_search(array, 42) == &array[2]);
+ static_assert(binary_search(array, 17) == &array[1]);
+ static_assert(binary_search(array, 3) == nullptr);
+}
+
+TEST_CASE(unsigned_to_signed_regression)
+{
+ const Array<u32, 5> input { 0, 1, 2, 3, 4 };
+
+ // The algorithm computes 1 - input[2] = -1, and if this is (incorrectly) cast
+ // to an unsigned then it will look in the wrong direction and miss the 1.
+
+ size_t nearby_index = 1;
+ EXPECT_EQ(binary_search(input, 1u, &nearby_index), &input[1]);
+ EXPECT_EQ(nearby_index, 1u);
+}
diff --git a/Tests/AK/TestBitCast.cpp b/Tests/AK/TestBitCast.cpp
new file mode 100644
index 0000000000..baf270f9b6
--- /dev/null
+++ b/Tests/AK/TestBitCast.cpp
@@ -0,0 +1,23 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/BitCast.h>
+
+template<typename A, typename B>
+void check_cast_both_ways(const A& a, const B& b)
+{
+ EXPECT_EQ((bit_cast<A, B>(b)), a);
+ EXPECT_EQ((bit_cast<B, A>(a)), b);
+}
+
+TEST_CASE(double_int_conversion)
+{
+ check_cast_both_ways(static_cast<u64>(0), 0.0);
+ check_cast_both_ways(static_cast<u64>(1) << 63, -0.0);
+ check_cast_both_ways(static_cast<u64>(0x4172f58bc0000000), 19880124.0);
+}
diff --git a/Tests/AK/TestBitmap.cpp b/Tests/AK/TestBitmap.cpp
new file mode 100644
index 0000000000..b4326dcd54
--- /dev/null
+++ b/Tests/AK/TestBitmap.cpp
@@ -0,0 +1,250 @@
+/*
+ * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Bitmap.h>
+
+TEST_CASE(construct_empty)
+{
+ Bitmap bitmap;
+ EXPECT_EQ(bitmap.size(), 0u);
+}
+
+TEST_CASE(find_first_set)
+{
+ Bitmap bitmap(128, false);
+ bitmap.set(69, true);
+ EXPECT_EQ(bitmap.find_first_set().value(), 69u);
+}
+
+TEST_CASE(find_first_unset)
+{
+ Bitmap bitmap(128, true);
+ bitmap.set(51, false);
+ EXPECT_EQ(bitmap.find_first_unset().value(), 51u);
+}
+
+TEST_CASE(find_one_anywhere_set)
+{
+ {
+ Bitmap bitmap(168, false);
+ bitmap.set(34, true);
+ bitmap.set(97, true);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(0).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(31).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(32).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(34).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(36).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(63).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(64).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(96).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(96).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(97).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(127).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(128).value(), 34u);
+ }
+ {
+ Bitmap bitmap(128 + 24, false);
+ bitmap.set(34, true);
+ bitmap.set(126, true);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(0).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(63).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_set(64).value(), 126u);
+ }
+ {
+ Bitmap bitmap(32, false);
+ bitmap.set(12, true);
+ bitmap.set(24, true);
+ auto got = bitmap.find_one_anywhere_set(0).value();
+ EXPECT(got == 12 || got == 24);
+ }
+}
+
+TEST_CASE(find_one_anywhere_unset)
+{
+ {
+ Bitmap bitmap(168, true);
+ bitmap.set(34, false);
+ bitmap.set(97, false);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(0).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(31).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(32).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(34).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(36).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(63).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(64).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(96).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(96).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(97).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(127).value(), 97u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(128).value(), 34u);
+ }
+ {
+ Bitmap bitmap(128 + 24, true);
+ bitmap.set(34, false);
+ bitmap.set(126, false);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(0).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(63).value(), 34u);
+ EXPECT_EQ(bitmap.find_one_anywhere_unset(64).value(), 126u);
+ }
+ {
+ Bitmap bitmap(32, true);
+ bitmap.set(12, false);
+ bitmap.set(24, false);
+ auto got = bitmap.find_one_anywhere_unset(0).value();
+ EXPECT(got == 12 || got == 24);
+ }
+}
+
+TEST_CASE(find_first_range)
+{
+ Bitmap bitmap(128, true);
+ bitmap.set(47, false);
+ bitmap.set(48, false);
+ bitmap.set(49, false);
+ bitmap.set(50, false);
+ bitmap.set(51, false);
+ size_t found_range_size = 0;
+ auto result = bitmap.find_longest_range_of_unset_bits(5, found_range_size);
+ EXPECT_EQ(result.has_value(), true);
+ EXPECT_EQ(found_range_size, 5u);
+ EXPECT_EQ(result.value(), 47u);
+}
+
+TEST_CASE(set_range)
+{
+ {
+ Bitmap bitmap(128, false);
+ bitmap.set_range(41, 10, true);
+ EXPECT_EQ(bitmap.get(40), false);
+ EXPECT_EQ(bitmap.get(41), true);
+ EXPECT_EQ(bitmap.get(42), true);
+ EXPECT_EQ(bitmap.get(43), true);
+ EXPECT_EQ(bitmap.get(44), true);
+ EXPECT_EQ(bitmap.get(45), true);
+ EXPECT_EQ(bitmap.get(46), true);
+ EXPECT_EQ(bitmap.get(47), true);
+ EXPECT_EQ(bitmap.get(48), true);
+ EXPECT_EQ(bitmap.get(49), true);
+ EXPECT_EQ(bitmap.get(50), true);
+ EXPECT_EQ(bitmap.get(51), false);
+ }
+ {
+ Bitmap bitmap(288, false);
+ bitmap.set_range(48, 32, true);
+ bitmap.set_range(94, 39, true);
+ bitmap.set_range(190, 71, true);
+ bitmap.set_range(190 + 71 - 7, 21, false); // slightly overlapping clear
+ for (size_t i = 0; i < bitmap.size(); i++) {
+ bool should_be_set = (i >= 48 && i < 48 + 32)
+ || (i >= 94 && i < 94 + 39)
+ || ((i >= 190 && i < 190 + 71) && !(i >= 190 + 71 - 7 && i < 190 + 71 - 7 + 21));
+ EXPECT_EQ(bitmap.get(i), should_be_set);
+ }
+ EXPECT_EQ(bitmap.count_slow(true), 32u + 39u + 71u - 7u);
+ }
+}
+
+TEST_CASE(find_first_fit)
+{
+ {
+ Bitmap bitmap(32, true);
+ auto fit = bitmap.find_first_fit(1);
+ EXPECT_EQ(fit.has_value(), false);
+ }
+ {
+ Bitmap bitmap(32, true);
+ bitmap.set(31, false);
+ auto fit = bitmap.find_first_fit(1);
+ EXPECT_EQ(fit.has_value(), true);
+ EXPECT_EQ(fit.value(), 31u);
+ }
+
+ for (size_t i = 0; i < 128; ++i) {
+ Bitmap bitmap(128, true);
+ bitmap.set(i, false);
+ auto fit = bitmap.find_first_fit(1);
+ EXPECT_EQ(fit.has_value(), true);
+ EXPECT_EQ(fit.value(), i);
+ }
+
+ for (size_t i = 0; i < 127; ++i) {
+ Bitmap bitmap(128, true);
+ bitmap.set(i, false);
+ bitmap.set(i + 1, false);
+ auto fit = bitmap.find_first_fit(2);
+ EXPECT_EQ(fit.has_value(), true);
+ EXPECT_EQ(fit.value(), i);
+ }
+
+ size_t bitmap_size = 1024;
+ for (size_t chunk_size = 1; chunk_size < 64; ++chunk_size) {
+ for (size_t i = 0; i < bitmap_size - chunk_size; ++i) {
+ Bitmap bitmap(bitmap_size, true);
+ for (size_t c = 0; c < chunk_size; ++c)
+ bitmap.set(i + c, false);
+ auto fit = bitmap.find_first_fit(chunk_size);
+ EXPECT_EQ(fit.has_value(), true);
+ EXPECT_EQ(fit.value(), i);
+ }
+ }
+}
+
+TEST_CASE(find_longest_range_of_unset_bits_edge)
+{
+ Bitmap bitmap(36, true);
+ bitmap.set_range(32, 4, false);
+ size_t found_range_size = 0;
+ auto result = bitmap.find_longest_range_of_unset_bits(1, found_range_size);
+ EXPECT_EQ(result.has_value(), true);
+ EXPECT_EQ(result.value(), 32u);
+}
+
+TEST_CASE(count_in_range)
+{
+ Bitmap bitmap(256, false);
+ bitmap.set(14, true);
+ bitmap.set(17, true);
+ bitmap.set(19, true);
+ bitmap.set(20, true);
+ for (size_t i = 34; i < 250; i++) {
+ if (i < 130 || i > 183)
+ bitmap.set(i, true);
+ }
+
+ auto count_bits_slow = [](const Bitmap& b, size_t start, size_t len, bool value) -> size_t {
+ size_t count = 0;
+ for (size_t i = start; i < start + len; i++) {
+ if (b.get(i) == value)
+ count++;
+ }
+ return count;
+ };
+ auto test_with_value = [&](bool value) {
+ auto do_test = [&](size_t start, size_t len) {
+ EXPECT_EQ(bitmap.count_in_range(start, len, value), count_bits_slow(bitmap, start, len, value));
+ };
+ do_test(16, 2);
+ do_test(16, 3);
+ do_test(16, 4);
+
+ for (size_t start = 8; start < 24; start++) {
+ for (size_t end = 9; end < 25; end++) {
+ if (start >= end)
+ continue;
+ do_test(start, end - start);
+ }
+ }
+
+ for (size_t start = 1; start <= 9; start++) {
+ for (size_t i = start + 1; i < bitmap.size() - start + 1; i++)
+ do_test(start, i - start);
+ }
+ };
+ test_with_value(true);
+ test_with_value(false);
+}
diff --git a/Tests/AK/TestByteBuffer.cpp b/Tests/AK/TestByteBuffer.cpp
new file mode 100644
index 0000000000..a6fabd7085
--- /dev/null
+++ b/Tests/AK/TestByteBuffer.cpp
@@ -0,0 +1,51 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/ByteBuffer.h>
+
+TEST_CASE(equality_operator)
+{
+ ByteBuffer a = ByteBuffer::copy("Hello, world", 7);
+ ByteBuffer b = ByteBuffer::copy("Hello, friend", 7);
+ // `a` and `b` are both "Hello, ".
+ ByteBuffer c = ByteBuffer::copy("asdf", 4);
+ ByteBuffer d;
+ EXPECT_EQ(a == a, true);
+ EXPECT_EQ(a == b, true);
+ EXPECT_EQ(a == c, false);
+ EXPECT_EQ(a == d, false);
+ EXPECT_EQ(b == a, true);
+ EXPECT_EQ(b == b, true);
+ EXPECT_EQ(b == c, false);
+ EXPECT_EQ(b == d, false);
+ EXPECT_EQ(c == a, false);
+ EXPECT_EQ(c == b, false);
+ EXPECT_EQ(c == c, true);
+ EXPECT_EQ(c == d, false);
+ EXPECT_EQ(d == a, false);
+ EXPECT_EQ(d == b, false);
+ EXPECT_EQ(d == c, false);
+ EXPECT_EQ(d == d, true);
+}
+
+/*
+ * FIXME: These `negative_*` tests should cause precisely one compilation error
+ * each, and always for the specified reason. Currently we do not have a harness
+ * for that, so in order to run the test you need to set the #define to 1, compile
+ * it, and check the error messages manually.
+ */
+#define COMPILE_NEGATIVE_TESTS 0
+#if COMPILE_NEGATIVE_TESTS
+TEST_CASE(negative_operator_lt)
+{
+ ByteBuffer a = ByteBuffer::copy("Hello, world", 10);
+ ByteBuffer b = ByteBuffer::copy("Hello, friend", 10);
+ [[maybe_unused]] auto res = a < b;
+ // error: error: use of deleted function ‘bool AK::ByteBuffer::operator<(const AK::ByteBuffer&) const’
+}
+#endif /* COMPILE_NEGATIVE_TESTS */
diff --git a/Tests/AK/TestChecked.cpp b/Tests/AK/TestChecked.cpp
new file mode 100644
index 0000000000..a4c932d696
--- /dev/null
+++ b/Tests/AK/TestChecked.cpp
@@ -0,0 +1,388 @@
+/*
+ * Copyright (c) 2020, Ben Wiederhake <BenWiederhake.GitHub@gmx.de>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Checked.h>
+#include <AK/NumericLimits.h>
+
+// These tests only check whether the usual operator semantics work.
+// TODO: Add tests about the actual `Check`ing itself!
+
+TEST_CASE(address_identity)
+{
+ Checked<int> a = 4;
+ Checked<int> b = 5;
+ EXPECT_EQ(&a == &a, true);
+ EXPECT_EQ(&a == &b, false);
+ EXPECT_EQ(&a != &a, false);
+ EXPECT_EQ(&a != &b, true);
+}
+
+TEST_CASE(operator_identity)
+{
+ Checked<int> a = 4;
+ EXPECT_EQ(a == 4, true);
+ EXPECT_EQ(a == 5, false);
+ EXPECT_EQ(a != 4, false);
+ EXPECT_EQ(a != 5, true);
+}
+
+TEST_CASE(operator_incr)
+{
+ Checked<int> a = 4;
+ EXPECT_EQ(++a, 5);
+ EXPECT_EQ(++a, 6);
+ EXPECT_EQ(++a, 7);
+ EXPECT_EQ(a++, 7);
+ EXPECT_EQ(a++, 8);
+ EXPECT_EQ(a++, 9);
+ EXPECT_EQ(a, 10);
+ // TODO: If decrementing gets supported, test it.
+}
+
+TEST_CASE(operator_cmp)
+{
+ Checked<int> a = 4;
+ EXPECT_EQ(a > 3, true);
+ EXPECT_EQ(a < 3, false);
+ EXPECT_EQ(a >= 3, true);
+ EXPECT_EQ(a <= 3, false);
+ EXPECT_EQ(a > 4, false);
+ EXPECT_EQ(a < 4, false);
+ EXPECT_EQ(a >= 4, true);
+ EXPECT_EQ(a <= 4, true);
+ EXPECT_EQ(a > 5, false);
+ EXPECT_EQ(a < 5, true);
+ EXPECT_EQ(a >= 5, false);
+ EXPECT_EQ(a <= 5, true);
+}
+
+TEST_CASE(operator_arith)
+{
+ Checked<int> a = 12;
+ Checked<int> b = 345;
+ EXPECT_EQ(a + b, 357);
+ EXPECT_EQ(b + a, 357);
+ EXPECT_EQ(a - b, -333);
+ EXPECT_EQ(b - a, 333);
+ EXPECT_EQ(a * b, 4140);
+ EXPECT_EQ(b * a, 4140);
+ EXPECT_EQ(a / b, 0);
+ EXPECT_EQ(b / a, 28);
+}
+
+TEST_CASE(detects_signed_overflow)
+{
+ EXPECT(!(Checked<int>(0x40000000) + Checked<int>(0x3fffffff)).has_overflow());
+ EXPECT((Checked<int>(0x40000000) + Checked<int>(0x40000000)).has_overflow());
+ EXPECT(!(Checked<int>(-0x40000000) + Checked<int>(-0x40000000)).has_overflow());
+ EXPECT((Checked<int>(-0x40000001) + Checked<int>(-0x40000000)).has_overflow());
+
+ EXPECT(!(Checked<int>(0x40000000) - Checked<int>(-0x3fffffff)).has_overflow());
+ EXPECT((Checked<int>(0x40000000) - Checked<int>(-0x40000000)).has_overflow());
+ EXPECT(!(Checked<int>(-0x40000000) - Checked<int>(0x40000000)).has_overflow());
+ EXPECT((Checked<int>(-0x40000000) - Checked<int>(0x40000001)).has_overflow());
+
+ EXPECT(!(Checked<i64>(0x4000000000000000) + Checked<i64>(0x3fffffffffffffff)).has_overflow());
+ EXPECT((Checked<i64>(0x4000000000000000) + Checked<i64>(0x4000000000000000)).has_overflow());
+ EXPECT(!(Checked<i64>(-0x4000000000000000) + Checked<i64>(-0x4000000000000000)).has_overflow());
+ EXPECT((Checked<i64>(-0x4000000000000001) + Checked<i64>(-0x4000000000000000)).has_overflow());
+
+ EXPECT(!(Checked<i64>(0x4000000000000000) - Checked<i64>(-0x3fffffffffffffff)).has_overflow());
+ EXPECT((Checked<i64>(0x4000000000000000) - Checked<i64>(-0x4000000000000000)).has_overflow());
+ EXPECT(!(Checked<i64>(-0x4000000000000000) - Checked<i64>(0x4000000000000000)).has_overflow());
+ EXPECT((Checked<i64>(-0x4000000000000000) - Checked<i64>(0x4000000000000001)).has_overflow());
+}
+
+TEST_CASE(detects_unsigned_overflow)
+{
+ EXPECT(!(Checked<u32>(0x40000000) + Checked<u32>(0x3fffffff)).has_overflow());
+ EXPECT(!(Checked<u32>(0x40000000) + Checked<u32>(0x40000000)).has_overflow());
+ EXPECT(!(Checked<u32>(0xf0000000) + Checked<u32>(0x0fffffff)).has_overflow());
+ EXPECT((Checked<u32>(0xf0000000) + Checked<u32>(0x10000000)).has_overflow());
+
+ EXPECT(!(Checked<u32>(0x40000000) - Checked<u32>(0x3fffffff)).has_overflow());
+ EXPECT(!(Checked<u32>(0x40000000) - Checked<u32>(0x40000000)).has_overflow());
+ EXPECT((Checked<u32>(0x40000000) - Checked<u32>(0x40000001)).has_overflow());
+
+ EXPECT(!(Checked<u64>(0x4000000000000000) + Checked<u64>(0x3fffffffffffffff)).has_overflow());
+ EXPECT(!(Checked<u64>(0x4000000000000000) + Checked<u64>(0x4000000000000000)).has_overflow());
+ EXPECT(!(Checked<u64>(0xf000000000000000) + Checked<u64>(0x0fffffffffffffff)).has_overflow());
+ EXPECT((Checked<u64>(0xf000000000000000) + Checked<u64>(0x1000000000000000)).has_overflow());
+
+ EXPECT(!(Checked<u64>(0x4000000000000000) - Checked<u64>(0x3fffffffffffffff)).has_overflow());
+ EXPECT(!(Checked<u64>(0x4000000000000000) - Checked<u64>(0x4000000000000000)).has_overflow());
+ EXPECT((Checked<u64>(0x4000000000000000) - Checked<u64>(0x4000000000000001)).has_overflow());
+}
+
+TEST_CASE(should_constexpr_default_construct)
+{
+ constexpr Checked<int> checked_value {};
+ static_assert(!checked_value.has_overflow());
+ static_assert(checked_value == int {});
+}
+
+TEST_CASE(should_constexpr_value_construct)
+{
+ constexpr Checked<int> checked_value { 42 };
+ static_assert(!checked_value.has_overflow());
+ static_assert(checked_value == 42);
+}
+
+TEST_CASE(should_constexpr_convert_construct)
+{
+ constexpr Checked<int> checked_value { 42u };
+ static_assert(!checked_value.has_overflow());
+ static_assert(checked_value == 42);
+}
+
+TEST_CASE(should_constexpr_copy_construct)
+{
+ constexpr auto checked_value = [] {
+ const Checked<int> old_value { 42 };
+ Checked<int> value(old_value);
+ return value;
+ }();
+ static_assert(!checked_value.has_overflow());
+ static_assert(checked_value == 42);
+}
+
+TEST_CASE(should_constexpr_move_construct)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value(Checked<int> { 42 });
+ return value;
+ }();
+ static_assert(!checked_value.has_overflow());
+ static_assert(checked_value == 42);
+}
+
+TEST_CASE(should_constexpr_copy_assign)
+{
+ constexpr auto checked_value = [] {
+ const Checked<int> old_value { 42 };
+ Checked<int> value {};
+ value = old_value;
+ return value;
+ }();
+ static_assert(!checked_value.has_overflow());
+ static_assert(checked_value == 42);
+}
+
+TEST_CASE(should_constexpr_move_assign)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value {};
+ value = Checked<int> { 42 };
+ return value;
+ }();
+ static_assert(!checked_value.has_overflow());
+ static_assert(checked_value == 42);
+}
+
+TEST_CASE(should_constexpr_convert_and_assign)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value {};
+ value = 42;
+ return value;
+ }();
+ static_assert(!checked_value.has_overflow());
+ static_assert(checked_value == 42);
+}
+
+TEST_CASE(should_constexpr_not_operator)
+{
+ constexpr Checked<int> value {};
+ static_assert(!value);
+}
+
+TEST_CASE(should_constexpr_value_accessor)
+{
+ constexpr Checked<int> value { 42 };
+ static_assert(value.value() == 42);
+}
+
+TEST_CASE(should_constexpr_add)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value.add(3);
+ return value;
+ }();
+ static_assert(checked_value == 45);
+}
+
+TEST_CASE(should_constexpr_sub)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value.sub(3);
+ return value;
+ }();
+ static_assert(checked_value == 39);
+}
+
+TEST_CASE(should_constexpr_mul)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value.mul(2);
+ return value;
+ }();
+ static_assert(checked_value == 84);
+}
+
+TEST_CASE(should_constexpr_div)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value.div(3);
+ return value;
+ }();
+ static_assert(checked_value == 14);
+}
+
+TEST_CASE(should_constexpr_assignment_by_sum)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value += 3;
+ return value;
+ }();
+ static_assert(checked_value == 45);
+}
+
+TEST_CASE(should_constexpr_assignment_by_diff)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value -= 3;
+ return value;
+ }();
+ static_assert(checked_value == 39);
+}
+
+TEST_CASE(should_constexpr_assignment_by_product)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value *= 2;
+ return value;
+ }();
+ static_assert(checked_value == 84);
+}
+
+TEST_CASE(should_constexpr_assignment_by_quotient)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value /= 3;
+ return value;
+ }();
+ static_assert(checked_value == 14);
+}
+
+TEST_CASE(should_constexpr_prefix_increment)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ ++value;
+ return value;
+ }();
+ static_assert(checked_value == 43);
+}
+
+TEST_CASE(should_constexpr_postfix_increment)
+{
+ constexpr auto checked_value = [] {
+ Checked<int> value { 42 };
+ value++;
+ return value;
+ }();
+ static_assert(checked_value == 43);
+}
+
+TEST_CASE(should_constexpr_check_for_overflow_addition)
+{
+ static_assert(Checked<int>::addition_would_overflow(NumericLimits<int>::max(), 1));
+}
+
+TEST_CASE(should_constexpr_check_for_overflow_multiplication)
+{
+ static_assert(Checked<int>::multiplication_would_overflow(NumericLimits<int>::max(), 2));
+ static_assert(Checked<int>::multiplication_would_overflow(NumericLimits<int>::max(), 1, 2));
+}
+
+TEST_CASE(should_constexpr_add_checked_values)
+{
+ constexpr Checked<int> a { 42 };
+ constexpr Checked<int> b { 17 };
+ constexpr Checked<int> expected { 59 };
+ static_assert(expected == (a + b).value());
+}
+
+TEST_CASE(should_constexpr_subtract_checked_values)
+{
+ constexpr Checked<int> a { 42 };
+ constexpr Checked<int> b { 17 };
+ constexpr Checked<int> expected { 25 };
+ static_assert(expected == (a - b).value());
+}
+
+TEST_CASE(should_constexpr_multiply_checked_values)
+{
+ constexpr Checked<int> a { 3 };
+ constexpr Checked<int> b { 5 };
+ constexpr Checked<int> expected { 15 };
+ static_assert(expected == (a * b).value());
+}
+
+TEST_CASE(should_constexpr_divide_checked_values)
+{
+ constexpr Checked<int> a { 10 };
+ constexpr Checked<int> b { 2 };
+ constexpr Checked<int> expected { 5 };
+ static_assert(expected == (a / b).value());
+}
+
+TEST_CASE(should_constexpr_compare_checked_values_lhs)
+{
+ constexpr Checked<int> a { 10 };
+
+ static_assert(a > 5);
+ static_assert(a >= 10);
+ static_assert(a >= 5);
+
+ static_assert(a < 20);
+ static_assert(a <= 30);
+ static_assert(a <= 20);
+
+ static_assert(a == 10);
+ static_assert(a != 20);
+}
+
+TEST_CASE(should_constexpr_compare_checked_values_rhs)
+{
+ constexpr Checked<int> a { 10 };
+
+ static_assert(5 < a);
+ static_assert(10 <= a);
+ static_assert(5 <= a);
+
+ static_assert(20 > a);
+ static_assert(30 >= a);
+ static_assert(30 >= a);
+
+ static_assert(10 == a);
+ static_assert(20 != a);
+}
+
+TEST_CASE(should_constexpr_make_via_factory)
+{
+ [[maybe_unused]] constexpr auto value = make_checked(42);
+}
diff --git a/Tests/AK/TestCircularDeque.cpp b/Tests/AK/TestCircularDeque.cpp
new file mode 100644
index 0000000000..3fa5189bb8
--- /dev/null
+++ b/Tests/AK/TestCircularDeque.cpp
@@ -0,0 +1,63 @@
+/*
+ * Copyright (c) 2020, Fei Wu <f.eiwu@yahoo.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/CircularDeque.h>
+#include <AK/StdLibExtras.h>
+#include <AK/String.h>
+
+TEST_CASE(enqueue_begin)
+{
+ CircularDeque<int, 3> ints;
+
+ ints.enqueue_begin(0);
+ EXPECT_EQ(ints.size(), 1u);
+ EXPECT_EQ(ints.first(), 0);
+
+ ints.enqueue_begin(1);
+ EXPECT_EQ(ints.size(), 2u);
+ EXPECT_EQ(ints.first(), 1);
+ EXPECT_EQ(ints.last(), 0);
+
+ ints.enqueue_begin(2);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(ints.first(), 2);
+ EXPECT_EQ(ints.last(), 0);
+
+ ints.enqueue_begin(3);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(ints.first(), 3);
+ EXPECT_EQ(ints.at(1), 2);
+ EXPECT_EQ(ints.last(), 1);
+}
+
+TEST_CASE(enqueue_begin_being_moved_from)
+{
+ CircularDeque<String, 2> strings;
+
+ String str { "test" };
+ strings.enqueue_begin(move(str));
+ EXPECT(str.is_null());
+}
+
+TEST_CASE(deque_end)
+{
+ CircularDeque<int, 3> ints;
+ ints.enqueue(0);
+ ints.enqueue(1);
+ ints.enqueue(2);
+ EXPECT_EQ(ints.size(), 3u);
+
+ EXPECT_EQ(ints.dequeue_end(), 2);
+ EXPECT_EQ(ints.size(), 2u);
+
+ EXPECT_EQ(ints.dequeue_end(), 1);
+ EXPECT_EQ(ints.size(), 1u);
+
+ EXPECT_EQ(ints.dequeue_end(), 0);
+ EXPECT(ints.is_empty());
+}
diff --git a/Tests/AK/TestCircularDuplexStream.cpp b/Tests/AK/TestCircularDuplexStream.cpp
new file mode 100644
index 0000000000..fa1a91a76e
--- /dev/null
+++ b/Tests/AK/TestCircularDuplexStream.cpp
@@ -0,0 +1,63 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/CircularDuplexStream.h>
+
+TEST_CASE(works_like_a_queue)
+{
+ constexpr size_t capacity = 32;
+
+ CircularQueue<u8, capacity> queue;
+ CircularDuplexStream<capacity> stream;
+
+ for (size_t idx = 0; idx < capacity; ++idx) {
+ queue.enqueue(static_cast<u8>(idx % 256));
+ stream << static_cast<u8>(idx % 256);
+ }
+
+ for (size_t idx = 0; idx < capacity; ++idx) {
+ u8 byte = 0;
+ stream >> byte;
+
+ EXPECT_EQ(queue.dequeue(), byte);
+ }
+
+ EXPECT(stream.eof());
+}
+
+TEST_CASE(overwritting_is_well_defined)
+{
+ constexpr size_t half_capacity = 16;
+ constexpr size_t capacity = 2 * half_capacity;
+
+ CircularDuplexStream<capacity> stream;
+
+ for (size_t idx = 0; idx < capacity; ++idx)
+ stream << static_cast<u8>(idx % 256);
+
+ Array<u8, half_capacity> buffer;
+ stream >> buffer;
+
+ for (size_t idx = 0; idx < half_capacity; ++idx)
+ EXPECT_EQ(buffer[idx], idx % 256);
+
+ for (size_t idx = 0; idx < half_capacity; ++idx)
+ stream << static_cast<u8>(idx % 256);
+
+ for (size_t idx = 0; idx < capacity; ++idx) {
+ u8 byte = 0;
+ stream >> byte;
+
+ if (idx < half_capacity)
+ EXPECT_EQ(byte, half_capacity + idx % 256);
+ else
+ EXPECT_EQ(byte, idx % 256 - half_capacity);
+ }
+
+ EXPECT(stream.eof());
+}
diff --git a/Tests/AK/TestCircularQueue.cpp b/Tests/AK/TestCircularQueue.cpp
new file mode 100644
index 0000000000..edc3cb5184
--- /dev/null
+++ b/Tests/AK/TestCircularQueue.cpp
@@ -0,0 +1,68 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/CircularQueue.h>
+#include <AK/String.h>
+
+TEST_CASE(basic)
+{
+ CircularQueue<int, 3> ints;
+ EXPECT(ints.is_empty());
+ ints.enqueue(1);
+ ints.enqueue(2);
+ ints.enqueue(3);
+ EXPECT_EQ(ints.size(), 3u);
+
+ ints.enqueue(4);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(ints.dequeue(), 2);
+ EXPECT_EQ(ints.dequeue(), 3);
+ EXPECT_EQ(ints.dequeue(), 4);
+ EXPECT_EQ(ints.size(), 0u);
+}
+
+TEST_CASE(complex_type)
+{
+ CircularQueue<String, 2> strings;
+
+ strings.enqueue("ABC");
+ strings.enqueue("DEF");
+
+ EXPECT_EQ(strings.size(), 2u);
+
+ strings.enqueue("abc");
+ strings.enqueue("def");
+
+ EXPECT_EQ(strings.dequeue(), "abc");
+ EXPECT_EQ(strings.dequeue(), "def");
+}
+
+TEST_CASE(complex_type_clear)
+{
+ CircularQueue<String, 5> strings;
+ strings.enqueue("xxx");
+ strings.enqueue("xxx");
+ strings.enqueue("xxx");
+ strings.enqueue("xxx");
+ strings.enqueue("xxx");
+ EXPECT_EQ(strings.size(), 5u);
+ strings.clear();
+ EXPECT_EQ(strings.size(), 0u);
+}
+
+struct ConstructorCounter {
+ static unsigned s_num_constructor_calls;
+ ConstructorCounter() { ++s_num_constructor_calls; }
+};
+unsigned ConstructorCounter::s_num_constructor_calls = 0;
+
+TEST_CASE(should_not_call_value_type_constructor_when_created)
+{
+ CircularQueue<ConstructorCounter, 10> queue;
+ EXPECT_EQ(0u, ConstructorCounter::s_num_constructor_calls);
+}
diff --git a/Tests/AK/TestComplex.cpp b/Tests/AK/TestComplex.cpp
new file mode 100644
index 0000000000..5079569d18
--- /dev/null
+++ b/Tests/AK/TestComplex.cpp
@@ -0,0 +1,44 @@
+/*
+ * Copyright (c) 2021, Cesar Torres <shortanemoia@protonmail.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Complex.h>
+
+TEST_CASE(Complex)
+{
+ auto a = Complex<float> { 1.f, 1.f };
+ auto b = complex_real_unit<double> + Complex<double> { 0, 1 } * 1;
+ EXPECT_APPROXIMATE(a.real(), b.real());
+ EXPECT_APPROXIMATE(a.imag(), b.imag());
+
+#ifdef AKCOMPLEX_CAN_USE_MATH_H
+ EXPECT_APPROXIMATE((complex_imag_unit<float> - complex_imag_unit<float>).magnitude(), 0);
+ EXPECT_APPROXIMATE((complex_imag_unit<float> + complex_real_unit<float>).magnitude(), sqrt(2));
+
+ auto c = Complex<double> { 0., 1. };
+ auto d = Complex<double>::from_polar(1., M_PI / 2.);
+ EXPECT_APPROXIMATE(c.real(), d.real());
+ EXPECT_APPROXIMATE(c.imag(), d.imag());
+
+ c = Complex<double> { -1., 1. };
+ d = Complex<double>::from_polar(sqrt(2.), 3. * M_PI / 4.);
+ EXPECT_APPROXIMATE(c.real(), d.real());
+ EXPECT_APPROXIMATE(c.imag(), d.imag());
+ EXPECT_APPROXIMATE(d.phase(), 3. * M_PI / 4.);
+ EXPECT_APPROXIMATE(c.magnitude(), d.magnitude());
+ EXPECT_APPROXIMATE(c.magnitude(), sqrt(2.));
+#endif
+ EXPECT_EQ((complex_imag_unit<double> * complex_imag_unit<double>).real(), -1.);
+ EXPECT_EQ((complex_imag_unit<double> / complex_imag_unit<double>).real(), 1.);
+
+ EXPECT_EQ(Complex(1., 10.) == (Complex<double>(1., 0.) + Complex(0., 10.)), true);
+ EXPECT_EQ(Complex(1., 10.) != (Complex<double>(1., 1.) + Complex(0., 10.)), true);
+#ifdef AKCOMPLEX_CAN_USE_MATH_H
+ EXPECT_EQ(approx_eq(Complex<int>(1), Complex<float>(1.0000004f)), true);
+ EXPECT_APPROXIMATE(cexp(Complex<double>(0., 1.) * M_PI).real(), -1.);
+#endif
+}
diff --git a/Tests/AK/TestDistinctNumeric.cpp b/Tests/AK/TestDistinctNumeric.cpp
new file mode 100644
index 0000000000..1ecc740098
--- /dev/null
+++ b/Tests/AK/TestDistinctNumeric.cpp
@@ -0,0 +1,285 @@
+/*
+ * Copyright (c) 2020, Ben Wiederhake <BenWiederhake.GitHub@gmx.de>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/DistinctNumeric.h>
+
+template<typename T>
+class ForType {
+public:
+ static void check_size()
+ {
+ TYPEDEF_DISTINCT_NUMERIC_GENERAL(T, false, false, false, false, false, false, TheNumeric);
+ EXPECT_EQ(sizeof(T), sizeof(TheNumeric));
+ }
+};
+
+TEST_CASE(check_size)
+{
+#define CHECK_SIZE_FOR_SIGNABLE(T) \
+ do { \
+ ForType<signed T>::check_size(); \
+ ForType<unsigned T>::check_size(); \
+ } while (false)
+ CHECK_SIZE_FOR_SIGNABLE(char);
+ CHECK_SIZE_FOR_SIGNABLE(short);
+ CHECK_SIZE_FOR_SIGNABLE(int);
+ CHECK_SIZE_FOR_SIGNABLE(long);
+ CHECK_SIZE_FOR_SIGNABLE(long long);
+ ForType<float>::check_size();
+ ForType<double>::check_size();
+}
+
+TYPEDEF_DISTINCT_NUMERIC_GENERAL(int, false, false, false, false, false, false, BareNumeric);
+TYPEDEF_DISTINCT_NUMERIC_GENERAL(int, true, false, false, false, false, false, IncrNumeric);
+TYPEDEF_DISTINCT_NUMERIC_GENERAL(int, false, true, false, false, false, false, CmpNumeric);
+TYPEDEF_DISTINCT_NUMERIC_GENERAL(int, false, false, true, false, false, false, BoolNumeric);
+TYPEDEF_DISTINCT_NUMERIC_GENERAL(int, false, false, false, true, false, false, FlagsNumeric);
+TYPEDEF_DISTINCT_NUMERIC_GENERAL(int, false, false, false, false, true, false, ShiftNumeric);
+TYPEDEF_DISTINCT_NUMERIC_GENERAL(int, false, false, false, false, false, true, ArithNumeric);
+TYPEDEF_DISTINCT_NUMERIC_GENERAL(int, true, true, true, true, true, true, GeneralNumeric);
+
+TEST_CASE(address_identity)
+{
+ BareNumeric a = 4;
+ BareNumeric b = 5;
+ EXPECT_EQ(&a == &a, true);
+ EXPECT_EQ(&a == &b, false);
+ EXPECT_EQ(&a != &a, false);
+ EXPECT_EQ(&a != &b, true);
+}
+
+TEST_CASE(operator_identity)
+{
+ BareNumeric a = 4;
+ BareNumeric b = 5;
+ EXPECT_EQ(a == a, true);
+ EXPECT_EQ(a == b, false);
+ EXPECT_EQ(a != a, false);
+ EXPECT_EQ(a != b, true);
+}
+
+TEST_CASE(operator_incr)
+{
+ IncrNumeric a = 4;
+ IncrNumeric b = 5;
+ IncrNumeric c = 6;
+ EXPECT_EQ(++a, b);
+ EXPECT_EQ(a++, b);
+ EXPECT_EQ(a, c);
+ EXPECT_EQ(--a, b);
+ EXPECT_EQ(a--, b);
+ EXPECT(a != b);
+}
+
+TEST_CASE(operator_cmp)
+{
+ CmpNumeric a = 4;
+ CmpNumeric b = 5;
+ CmpNumeric c = 5;
+ EXPECT_EQ(a > b, false);
+ EXPECT_EQ(a < b, true);
+ EXPECT_EQ(a >= b, false);
+ EXPECT_EQ(a <= b, true);
+ EXPECT_EQ(b > a, true);
+ EXPECT_EQ(b < a, false);
+ EXPECT_EQ(b >= a, true);
+ EXPECT_EQ(b <= a, false);
+ EXPECT_EQ(b > c, false);
+ EXPECT_EQ(b < c, false);
+ EXPECT_EQ(b >= c, true);
+ EXPECT_EQ(b <= c, true);
+}
+
+TEST_CASE(operator_bool)
+{
+ BoolNumeric a = 0;
+ BoolNumeric b = 42;
+ BoolNumeric c = 1337;
+ EXPECT_EQ(!a, true);
+ EXPECT_EQ(!b, false);
+ EXPECT_EQ(!c, false);
+}
+
+TEST_CASE(operator_flags)
+{
+ FlagsNumeric a = 0;
+ FlagsNumeric b = 0xA60;
+ FlagsNumeric c = 0x03B;
+ EXPECT_EQ(~a, FlagsNumeric(~0x0));
+ EXPECT_EQ(~b, FlagsNumeric(~0xA60));
+ EXPECT_EQ(~c, FlagsNumeric(~0x03B));
+
+ EXPECT_EQ(a & b, b & a);
+ EXPECT_EQ(a & c, c & a);
+ EXPECT_EQ(b & c, c & b);
+ EXPECT_EQ(a | b, b | a);
+ EXPECT_EQ(a | c, c | a);
+ EXPECT_EQ(b | c, c | b);
+ EXPECT_EQ(a ^ b, b ^ a);
+ EXPECT_EQ(a ^ c, c ^ a);
+ EXPECT_EQ(b ^ c, c ^ b);
+
+ EXPECT_EQ(a & b, FlagsNumeric(0x000));
+ EXPECT_EQ(a & c, FlagsNumeric(0x000));
+ EXPECT_EQ(b & c, FlagsNumeric(0x020));
+ EXPECT_EQ(a | b, FlagsNumeric(0xA60));
+ EXPECT_EQ(a | c, FlagsNumeric(0x03B));
+ EXPECT_EQ(b | c, FlagsNumeric(0xA7B));
+ EXPECT_EQ(a ^ b, FlagsNumeric(0xA60));
+ EXPECT_EQ(a ^ c, FlagsNumeric(0x03B));
+ EXPECT_EQ(b ^ c, FlagsNumeric(0xA5B));
+
+ EXPECT_EQ(a &= b, FlagsNumeric(0x000));
+ EXPECT_EQ(a, FlagsNumeric(0x000));
+ EXPECT_EQ(a |= b, FlagsNumeric(0xA60));
+ EXPECT_EQ(a, FlagsNumeric(0xA60));
+ EXPECT_EQ(a &= c, FlagsNumeric(0x020));
+ EXPECT_EQ(a, FlagsNumeric(0x020));
+ EXPECT_EQ(a ^= b, FlagsNumeric(0xA40));
+ EXPECT_EQ(a, FlagsNumeric(0xA40));
+
+ EXPECT_EQ(b, FlagsNumeric(0xA60));
+ EXPECT_EQ(c, FlagsNumeric(0x03B));
+}
+
+TEST_CASE(operator_shift)
+{
+ ShiftNumeric a = 0x040;
+ EXPECT_EQ(a << ShiftNumeric(0), ShiftNumeric(0x040));
+ EXPECT_EQ(a << ShiftNumeric(1), ShiftNumeric(0x080));
+ EXPECT_EQ(a << ShiftNumeric(2), ShiftNumeric(0x100));
+ EXPECT_EQ(a >> ShiftNumeric(0), ShiftNumeric(0x040));
+ EXPECT_EQ(a >> ShiftNumeric(1), ShiftNumeric(0x020));
+ EXPECT_EQ(a >> ShiftNumeric(2), ShiftNumeric(0x010));
+
+ EXPECT_EQ(a <<= ShiftNumeric(5), ShiftNumeric(0x800));
+ EXPECT_EQ(a, ShiftNumeric(0x800));
+ EXPECT_EQ(a >>= ShiftNumeric(8), ShiftNumeric(0x008));
+ EXPECT_EQ(a, ShiftNumeric(0x008));
+}
+
+TEST_CASE(operator_arith)
+{
+ ArithNumeric a = 12;
+ ArithNumeric b = 345;
+ EXPECT_EQ(a + b, ArithNumeric(357));
+ EXPECT_EQ(b + a, ArithNumeric(357));
+ EXPECT_EQ(a - b, ArithNumeric(-333));
+ EXPECT_EQ(b - a, ArithNumeric(333));
+ EXPECT_EQ(+a, ArithNumeric(12));
+ EXPECT_EQ(-a, ArithNumeric(-12));
+ EXPECT_EQ(a * b, ArithNumeric(4140));
+ EXPECT_EQ(b * a, ArithNumeric(4140));
+ EXPECT_EQ(a / b, ArithNumeric(0));
+ EXPECT_EQ(b / a, ArithNumeric(28));
+ EXPECT_EQ(a % b, ArithNumeric(12));
+ EXPECT_EQ(b % a, ArithNumeric(9));
+
+ EXPECT_EQ(a += a, ArithNumeric(24));
+ EXPECT_EQ(a, ArithNumeric(24));
+ EXPECT_EQ(a *= a, ArithNumeric(576));
+ EXPECT_EQ(a, ArithNumeric(576));
+ EXPECT_EQ(a /= a, ArithNumeric(1));
+ EXPECT_EQ(a, ArithNumeric(1));
+ EXPECT_EQ(a %= a, ArithNumeric(0));
+ EXPECT_EQ(a, ArithNumeric(0));
+}
+
+TEST_CASE(composability)
+{
+ GeneralNumeric a = 0;
+ GeneralNumeric b = 1;
+ // Ident
+ EXPECT_EQ(a == a, true);
+ EXPECT_EQ(a == b, false);
+ // Incr
+ EXPECT_EQ(++a, b);
+ EXPECT_EQ(a--, b);
+ EXPECT_EQ(a == b, false);
+ // Cmp
+ EXPECT_EQ(a < b, true);
+ EXPECT_EQ(a >= b, false);
+ // Bool
+ EXPECT_EQ(!a, true);
+ // Flags
+ EXPECT_EQ(a & b, GeneralNumeric(0));
+ EXPECT_EQ(a | b, GeneralNumeric(1));
+ // Shift
+ EXPECT_EQ(b << GeneralNumeric(4), GeneralNumeric(0x10));
+ EXPECT_EQ(b >> b, GeneralNumeric(0));
+ // Arith
+ EXPECT_EQ(-b, GeneralNumeric(-1));
+ EXPECT_EQ(a + b, b);
+ EXPECT_EQ(b * GeneralNumeric(42), GeneralNumeric(42));
+}
+
+/*
+ * FIXME: These `negative_*` tests should cause precisely one compilation error
+ * each, and always for the specified reason. Currently we do not have a harness
+ * for that, so in order to run the test you need to set the #define to 1, compile
+ * it, and check the error messages manually.
+ */
+#define COMPILE_NEGATIVE_TESTS 0
+#if COMPILE_NEGATIVE_TESTS
+TEST_CASE(negative_incr)
+{
+ BareNumeric a = 12;
+ a++;
+ // error: static assertion failed: 'a++' is only available for DistinctNumeric types with 'Incr'.
+}
+
+TEST_CASE(negative_cmp)
+{
+ BareNumeric a = 12;
+ [[maybe_unused]] auto res = (a < a);
+ // error: static assertion failed: 'a<b' is only available for DistinctNumeric types with 'Cmp'.
+}
+
+TEST_CASE(negative_bool)
+{
+ BareNumeric a = 12;
+ [[maybe_unused]] auto res = !a;
+ // error: static assertion failed: '!a', 'a&&b', 'a||b' and similar operators are only available for DistinctNumeric types with 'Bool'.
+}
+
+TEST_CASE(negative_flags)
+{
+ BareNumeric a = 12;
+ [[maybe_unused]] auto res = (a & a);
+ // error: static assertion failed: 'a&b' is only available for DistinctNumeric types with 'Flags'.
+}
+
+TEST_CASE(negative_shift)
+{
+ BareNumeric a = 12;
+ [[maybe_unused]] auto res = (a << a);
+ // error: static assertion failed: 'a<<b' is only available for DistinctNumeric types with 'Shift'.
+}
+
+TEST_CASE(negative_arith)
+{
+ BareNumeric a = 12;
+ [[maybe_unused]] auto res = (a + a);
+ // error: static assertion failed: 'a+b' is only available for DistinctNumeric types with 'Arith'.
+}
+
+TEST_CASE(negative_incompatible)
+{
+ GeneralNumeric a = 12;
+ ArithNumeric b = 345;
+ // And this is the entire point of `DistinctNumeric`:
+ // Theoretically, the operation *could* be supported, but we declared those int types incompatible.
+ [[maybe_unused]] auto res = (a + b);
+ // error: no match for ‘operator+’ (operand types are ‘GeneralNumeric’ {aka ‘AK::DistinctNumeric<int, true, true, true, true, true, true, 64, 64>’} and ‘ArithNumeric’ {aka ‘AK::DistinctNumeric<int, false, false, false, false, false, true, 64, 63>’})
+ // 313 | [[maybe_unused]] auto res = (a + b);
+ // | ~ ^ ~
+ // | | |
+ // | | DistinctNumeric<[...],false,false,false,false,false,[...],[...],63>
+ // | DistinctNumeric<[...],true,true,true,true,true,[...],[...],64>
+}
+#endif /* COMPILE_NEGATIVE_TESTS */
diff --git a/Tests/AK/TestDoublyLinkedList.cpp b/Tests/AK/TestDoublyLinkedList.cpp
new file mode 100644
index 0000000000..407484e443
--- /dev/null
+++ b/Tests/AK/TestDoublyLinkedList.cpp
@@ -0,0 +1,43 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/DoublyLinkedList.h>
+
+static DoublyLinkedList<int> make_list()
+{
+ DoublyLinkedList<int> list {};
+ list.append(0);
+ list.append(1);
+ list.append(2);
+ list.append(3);
+ list.append(4);
+ list.append(5);
+ list.append(6);
+ list.append(7);
+ list.append(8);
+ list.append(9);
+ return list;
+}
+
+TEST_CASE(should_find_mutable)
+{
+ auto sut = make_list();
+
+ EXPECT_EQ(4, *sut.find(4));
+
+ EXPECT_EQ(sut.end(), sut.find(42));
+}
+
+TEST_CASE(should_find_const)
+{
+ const auto sut = make_list();
+
+ EXPECT_EQ(4, *sut.find(4));
+
+ EXPECT_EQ(sut.end(), sut.find(42));
+}
diff --git a/Tests/AK/TestEndian.cpp b/Tests/AK/TestEndian.cpp
new file mode 100644
index 0000000000..7f7f1a57ff
--- /dev/null
+++ b/Tests/AK/TestEndian.cpp
@@ -0,0 +1,17 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Endian.h>
+
+static_assert(BigEndian<u32> {} == 0, "Big endian values should be default constructed in a constexpr context.");
+
+static_assert(BigEndian<u32> { 42 } == 42, "Big endian values should be value constructed in a constexpr context.");
+
+static_assert(LittleEndian<u32> {} == 0, "Little endian values should be default constructed in a constexpr context.");
+
+static_assert(LittleEndian<u32> { 42 } == 42, "Little endian values should be value constructed in a constexpr context.");
diff --git a/Tests/AK/TestEnumBits.cpp b/Tests/AK/TestEnumBits.cpp
new file mode 100644
index 0000000000..dc9eadf32d
--- /dev/null
+++ b/Tests/AK/TestEnumBits.cpp
@@ -0,0 +1,69 @@
+/*
+ * Copyright (c) 2021, Brian Gianforcaro <bgianf@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/EnumBits.h>
+
+enum class VideoIntro : u8 {
+ None = 0x0,
+ Well = 0x1,
+ Hello = 0x2,
+ Friends = 0x4,
+ ExclimationMark = 0x8,
+ CompleteIntro = Well | Hello | Friends | ExclimationMark,
+};
+
+AK_ENUM_BITWISE_OPERATORS(VideoIntro);
+
+TEST_CASE(bitwise_or)
+{
+ auto intro = VideoIntro::Well | VideoIntro::Hello | VideoIntro::Friends | VideoIntro::ExclimationMark;
+ EXPECT_EQ(intro, VideoIntro::CompleteIntro);
+}
+
+TEST_CASE(bitwise_and)
+{
+ auto intro = VideoIntro::CompleteIntro;
+ EXPECT_EQ(intro & VideoIntro::Hello, VideoIntro::Hello);
+}
+
+TEST_CASE(bitwise_xor)
+{
+ auto intro = VideoIntro::Well | VideoIntro::Hello | VideoIntro::Friends;
+ EXPECT_EQ(intro ^ VideoIntro::CompleteIntro, VideoIntro::ExclimationMark);
+}
+
+TEST_CASE(bitwise_not)
+{
+ auto intro = ~VideoIntro::CompleteIntro;
+ EXPECT_EQ(intro & VideoIntro::CompleteIntro, VideoIntro::None);
+}
+
+TEST_CASE(bitwise_or_equal)
+{
+ auto intro = VideoIntro::Well | VideoIntro::Hello | VideoIntro::Friends;
+ EXPECT_EQ(intro |= VideoIntro::ExclimationMark, VideoIntro::CompleteIntro);
+}
+
+TEST_CASE(bitwise_and_equal)
+{
+ auto intro = VideoIntro::CompleteIntro;
+ EXPECT_EQ(intro &= VideoIntro::Hello, VideoIntro::Hello);
+}
+
+TEST_CASE(bitwise_xor_equal)
+{
+ auto intro = VideoIntro::Well | VideoIntro::Hello | VideoIntro::Friends;
+ EXPECT_EQ(intro ^= VideoIntro::CompleteIntro, VideoIntro::ExclimationMark);
+}
+
+TEST_CASE(has_flag)
+{
+ auto intro = VideoIntro::Hello | VideoIntro::Friends;
+ EXPECT(has_flag(intro, VideoIntro::Friends));
+ EXPECT(!has_flag(intro, VideoIntro::Well));
+}
diff --git a/Tests/AK/TestFind.cpp b/Tests/AK/TestFind.cpp
new file mode 100644
index 0000000000..26d4ab11fd
--- /dev/null
+++ b/Tests/AK/TestFind.cpp
@@ -0,0 +1,54 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Array.h>
+#include <AK/Find.h>
+#include <AK/Vector.h>
+
+TEST_CASE(should_return_end_if_not_in_container)
+{
+ constexpr Array<int, 10> a {};
+
+ static_assert(a.end() == AK::find(a.begin(), a.end(), 1));
+
+ EXPECT(a.end() == AK::find(a.begin(), a.end(), 1));
+}
+
+TEST_CASE(should_return_iterator_to_first_matching_value_in_container)
+{
+ static constexpr Array<int, 10> a { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
+
+ constexpr auto expected = a.begin() + 4;
+
+ static_assert(expected == AK::find(a.begin(), a.end(), 0));
+
+ EXPECT(expected == AK::find(a.begin(), a.end(), 0));
+}
+
+TEST_CASE(should_return_iterator_to_first_predicate_matching_value_in_container)
+{
+ static constexpr Array<int, 10> a { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
+
+ constexpr auto expected = a.begin() + 4;
+
+ static_assert(expected == AK::find_if(a.begin(), a.end(), [](auto v) { return v == 0; }));
+
+ EXPECT(expected == AK::find_if(a.begin(), a.end(), [](auto v) { return v == 0; }));
+
+ auto find_me = 8;
+ EXPECT(find_me == *AK::find_if(a.begin(), a.end(), [&](auto v) { return v == find_me; }));
+}
+
+TEST_CASE(should_return_index_to_first_predicate_matching_value_in_container)
+{
+ static constexpr Array<int, 10> a { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
+
+ static_assert(4 == AK::find_index(a.begin(), a.end(), 0));
+
+ EXPECT(4 == AK::find_index(a.begin(), a.end(), 0));
+}
diff --git a/Tests/AK/TestFormat.cpp b/Tests/AK/TestFormat.cpp
new file mode 100644
index 0000000000..237d1a4354
--- /dev/null
+++ b/Tests/AK/TestFormat.cpp
@@ -0,0 +1,291 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/String.h>
+#include <AK/StringBuilder.h>
+
+TEST_CASE(is_integral_works_properly)
+{
+ EXPECT(!IsIntegral<const char*>);
+ EXPECT(IsIntegral<unsigned long>);
+}
+
+TEST_CASE(format_string_literals)
+{
+ EXPECT_EQ(String::formatted("prefix-{}-suffix", "abc"), "prefix-abc-suffix");
+ EXPECT_EQ(String::formatted("{}{}{}", "a", "b", "c"), "abc");
+}
+
+TEST_CASE(format_integers)
+{
+ EXPECT_EQ(String::formatted("{}", 42u), "42");
+ EXPECT_EQ(String::formatted("{:4}", 42u), " 42");
+ EXPECT_EQ(String::formatted("{:08}", 42u), "00000042");
+ EXPECT_EQ(String::formatted("{:7}", -17), " -17");
+ EXPECT_EQ(String::formatted("{}", -17), "-17");
+ EXPECT_EQ(String::formatted("{:04}", 13), "0013");
+ EXPECT_EQ(String::formatted("{:08x}", 4096), "00001000");
+ EXPECT_EQ(String::formatted("{:x}", 0x1111222233334444ull), "1111222233334444");
+ EXPECT_EQ(String::formatted("{:4}", 12345678), "12345678");
+}
+
+TEST_CASE(reorder_format_arguments)
+{
+ EXPECT_EQ(String::formatted("{1}{0}", "a", "b"), "ba");
+ EXPECT_EQ(String::formatted("{0}{1}", "a", "b"), "ab");
+ // Compiletime check bypass: ignoring a passed argument.
+ EXPECT_EQ(String::formatted(StringView { "{0}{0}{0}" }, "a", "b"), "aaa");
+ // Compiletime check bypass: ignoring a passed argument.
+ EXPECT_EQ(String::formatted(StringView { "{1}{}{0}" }, "a", "b", "c"), "baa");
+}
+
+TEST_CASE(escape_braces)
+{
+ EXPECT_EQ(String::formatted("{{{}", "foo"), "{foo");
+ EXPECT_EQ(String::formatted("{}}}", "bar"), "bar}");
+}
+
+TEST_CASE(everything)
+{
+ EXPECT_EQ(String::formatted("{{{:04}/{}/{0:8}/{1}", 42u, "foo"), "{0042/foo/ 42/foo");
+}
+
+TEST_CASE(string_builder)
+{
+ StringBuilder builder;
+ builder.appendff(" {} ", 42);
+ builder.appendff("{1}{0} ", 1, 2);
+
+ EXPECT_EQ(builder.to_string(), " 42 21 ");
+}
+
+TEST_CASE(format_without_arguments)
+{
+ EXPECT_EQ(String::formatted("foo"), "foo");
+}
+
+TEST_CASE(format_upper_case_integer)
+{
+ EXPECT_EQ(String::formatted("{:4X}", 0xff), " FF");
+ EXPECT_EQ(String::formatted("{:#4X}", 0xff), "0XFF");
+
+ EXPECT_EQ(String::formatted("{:b}", 0xff), "11111111");
+ EXPECT_EQ(String::formatted("{:B}", 0xff), "11111111");
+ EXPECT_EQ(String::formatted("{:#b}", 0xff), "0b11111111");
+}
+
+TEST_CASE(format_aligned)
+{
+ EXPECT_EQ(String::formatted("{:*<8}", 13), "13******");
+ EXPECT_EQ(String::formatted("{:*^8}", 13), "***13***");
+ EXPECT_EQ(String::formatted("{:*>8}", 13), "******13");
+ EXPECT_EQ(String::formatted("{:*>+8}", 13), "*****+13");
+ EXPECT_EQ(String::formatted("{:*^ 8}", 13), "** 13***");
+}
+
+TEST_CASE(format_octal)
+{
+ EXPECT_EQ(String::formatted("{:o}", 0744), "744");
+ EXPECT_EQ(String::formatted("{:#o}", 0744), "0744");
+}
+
+TEST_CASE(zero_pad)
+{
+ EXPECT_EQ(String::formatted("{: <010}", 42), "42 ");
+ EXPECT_EQ(String::formatted("{:010}", 42), "0000000042");
+ EXPECT_EQ(String::formatted("{:/^010}", 42), "////42////");
+ EXPECT_EQ(String::formatted("{:04x}", -32), "-0020");
+ EXPECT_EQ(String::formatted("{:#06x}", -64), "-0x000040");
+}
+
+TEST_CASE(replacement_field)
+{
+ // FIXME: Compiletime check bypass: cannot parse '}}' correctly.
+ EXPECT_EQ(String::formatted(StringView { "{:*>{1}}" }, 13, static_cast<size_t>(10)), "********13");
+ EXPECT_EQ(String::formatted(StringView { "{:*<{1}}" }, 7, 4), "7***");
+ EXPECT_EQ(String::formatted(StringView { "{:{2}}" }, -5, 8, 16), " -5");
+ EXPECT_EQ(String::formatted(StringView { "{{{:*^{1}}}}" }, 1, 3), "{*1*}");
+ EXPECT_EQ(String::formatted(StringView { "{:0{}}" }, 1, 3), "001");
+}
+
+TEST_CASE(replacement_field_regression)
+{
+ // FIXME: Compiletime check bypass: cannot parse '}}' correctly.
+ EXPECT_EQ(String::formatted(StringView { "{:{}}" }, "", static_cast<unsigned long>(6)), " ");
+}
+
+TEST_CASE(complex_string_specifiers)
+{
+ EXPECT_EQ(String::formatted("{:.8}", "123456789"), "12345678");
+ EXPECT_EQ(String::formatted("{:9}", "abcd"), "abcd ");
+ EXPECT_EQ(String::formatted("{:>9}", "abcd"), " abcd");
+ EXPECT_EQ(String::formatted("{:^9}", "abcd"), " abcd ");
+}
+
+TEST_CASE(cast_integer_to_character)
+{
+ EXPECT_EQ(String::formatted("{:c}", static_cast<int>('a')), "a");
+ EXPECT_EQ(String::formatted("{:c}", static_cast<unsigned int>('f')), "f");
+}
+
+TEST_CASE(boolean_values)
+{
+ EXPECT_EQ(String::formatted("{}", true), "true");
+ EXPECT_EQ(String::formatted("{}", false), "false");
+ EXPECT_EQ(String::formatted("{:6}", true), "true ");
+ EXPECT_EQ(String::formatted("{:>4}", false), "false");
+ EXPECT_EQ(String::formatted("{:d}", false), "0");
+ EXPECT_EQ(String::formatted("{:d}", true), "1");
+ EXPECT_EQ(String::formatted("{:#08x}", true), "0x00000001");
+}
+
+TEST_CASE(pointers)
+{
+ void* ptr = reinterpret_cast<void*>(0x4000);
+
+ if (sizeof(void*) == 4) {
+ EXPECT_EQ(String::formatted("{:p}", 32), "0x00000020");
+ EXPECT_EQ(String::formatted("{:p}", ptr), "0x00004000");
+ EXPECT_EQ(String::formatted("{}", ptr), "0x00004000");
+ } else if (sizeof(void*) == 8) {
+ EXPECT_EQ(String::formatted("{:p}", 32), "0x0000000000000020");
+ EXPECT_EQ(String::formatted("{:p}", ptr), "0x0000000000004000");
+ EXPECT_EQ(String::formatted("{}", ptr), "0x0000000000004000");
+ } else {
+ VERIFY_NOT_REACHED();
+ }
+}
+
+// If the format implementation did absolutely nothing, all tests would pass. This
+// is because when a test fails we only write "FAIL" to stdout using format.
+//
+// This is a bit scary, thus this test. At least this test should fail in this case.
+TEST_CASE(ensure_that_format_works)
+{
+ if (String::formatted("FAIL") != "FAIL") {
+ fprintf(stderr, "FAIL\n");
+ exit(1);
+ }
+
+ if (String::formatted("{} FAIL {}", 1, 2) != "1 FAIL 2") {
+ fprintf(stderr, "FAIL\n");
+ exit(1);
+ }
+}
+
+TEST_CASE(format_string_literal_as_pointer)
+{
+ const char* literal = "abc";
+ EXPECT_EQ(String::formatted("{:p}", literal), String::formatted("{:p}", reinterpret_cast<FlatPtr>(literal)));
+}
+
+TEST_CASE(format_character)
+{
+ char a = 'a';
+ EXPECT_EQ(String::formatted("{}", true ? a : 'b'), "a");
+}
+
+struct A {
+};
+struct B {
+};
+template<>
+struct AK::Formatter<B> : Formatter<StringView> {
+ void format(FormatBuilder& builder, B)
+ {
+ Formatter<StringView>::format(builder, "B");
+ }
+};
+
+TEST_CASE(format_if_supported)
+{
+ EXPECT_EQ(String::formatted("{}", FormatIfSupported { A {} }), "?");
+ EXPECT_EQ(String::formatted("{}", FormatIfSupported { B {} }), "B");
+}
+
+TEST_CASE(file_descriptor)
+{
+ char filename[] = "/tmp/test-file-descriptor-XXXXXX";
+
+ int fd = mkstemp(filename);
+ FILE* file = fdopen(fd, "w+");
+
+ outln(file, "{}", "Hello, World!");
+ out(file, "foo");
+ outln(file, "bar");
+
+ rewind(file);
+
+ Array<u8, 256> buffer;
+ const auto nread = fread(buffer.data(), 1, buffer.size(), file);
+
+ EXPECT_EQ(StringView { "Hello, World!\nfoobar\n" }, StringView { buffer.span().trim(nread) });
+
+ fclose(file);
+}
+
+TEST_CASE(floating_point_numbers)
+{
+ EXPECT_EQ(String::formatted("{}", 1.12), "1.12");
+ EXPECT_EQ(String::formatted("{}", 1.), "1");
+ EXPECT_EQ(String::formatted("{:.3}", 1.12), "1.12");
+ EXPECT_EQ(String::formatted("{:.1}", 1.12), "1.1");
+ EXPECT_EQ(String::formatted("{}", -1.12), "-1.12");
+
+ // FIXME: There is always the question what we mean with the width field. Do we mean significant digits?
+ // Do we mean the whole width? This is what was the simplest to implement:
+ EXPECT_EQ(String::formatted("{:x>5.1}", 1.12), "xx1.1");
+}
+
+TEST_CASE(no_precision_no_trailing_number)
+{
+ EXPECT_EQ(String::formatted("{:.0}", 0.1), "0");
+}
+
+TEST_CASE(yay_this_implementation_sucks)
+{
+ EXPECT_EQ(String::formatted("{:.0}", .99999999999), "0");
+}
+
+TEST_CASE(magnitude_less_than_zero)
+{
+ EXPECT_EQ(String::formatted("{}", -0.654), "-0.654");
+ EXPECT_EQ(String::formatted("{}", 0.654), "0.654");
+}
+
+TEST_CASE(format_nullptr)
+{
+ EXPECT_EQ(String::formatted("{}", nullptr), String::formatted("{:p}", static_cast<FlatPtr>(0)));
+}
+
+struct C {
+ int i;
+};
+template<>
+struct AK::Formatter<C> : AK::Formatter<FormatString> {
+ void format(FormatBuilder& builder, C c)
+ {
+ return AK::Formatter<FormatString>::format(builder, "C(i={})", c.i);
+ }
+};
+
+TEST_CASE(use_format_string_formatter)
+{
+ EXPECT_EQ(String::formatted("{:*<10}", C { 42 }), "C(i=42)***");
+}
+
+TEST_CASE(long_long_regression)
+{
+ EXPECT_EQ(String::formatted("{}", 0x0123456789abcdefLL), "81985529216486895");
+
+ StringBuilder builder;
+ AK::FormatBuilder fmtbuilder { builder };
+ fmtbuilder.put_i64(0x0123456789abcdefLL);
+
+ EXPECT_EQ(builder.string_view(), "81985529216486895");
+}
diff --git a/Tests/AK/TestGenericLexer.cpp b/Tests/AK/TestGenericLexer.cpp
new file mode 100644
index 0000000000..8b9a08cd1d
--- /dev/null
+++ b/Tests/AK/TestGenericLexer.cpp
@@ -0,0 +1,158 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/GenericLexer.h>
+#include <AK/StringView.h>
+
+TEST_CASE(should_constexpr_construct_from_empty_string_view)
+{
+ constexpr GenericLexer sut(StringView {});
+ static_assert(sut.is_eof());
+}
+
+TEST_CASE(should_construct_from_string_view)
+{
+ constexpr GenericLexer sut(StringView { "abcdef" });
+ static_assert(!sut.is_eof());
+}
+
+TEST_CASE(should_constexpr_tell)
+{
+ constexpr GenericLexer sut(StringView { "abcdef" });
+ static_assert(sut.tell() == 0);
+}
+
+TEST_CASE(should_constexpr_tell_remaining)
+{
+ constexpr GenericLexer sut(StringView { "abcdef" });
+ static_assert(sut.tell_remaining() == 6);
+}
+
+TEST_CASE(should_constexpr_peek)
+{
+ constexpr GenericLexer sut(StringView { "abcdef" });
+ static_assert(sut.peek() == 'a');
+ static_assert(sut.peek(2) == 'c');
+ static_assert(sut.peek(100) == '\0');
+}
+
+TEST_CASE(should_constexpr_next_is)
+{
+ constexpr GenericLexer sut(StringView { "abcdef" });
+ static_assert(sut.next_is('a'));
+ static_assert(sut.next_is("abc"));
+ static_assert(sut.next_is(StringView { "abc" }));
+}
+
+TEST_CASE(should_constexpr_retreat)
+{
+ constexpr auto sut = [] {
+ GenericLexer sut(StringView { "abcdef" });
+ sut.consume();
+ sut.retreat();
+ return sut;
+ }();
+ static_assert(sut.peek() == 'a');
+}
+
+TEST_CASE(should_constexpr_consume_1)
+{
+ constexpr auto sut = [] {
+ GenericLexer sut(StringView { "abcdef" });
+ sut.consume();
+ return sut;
+ }();
+ static_assert(sut.peek() == 'b');
+}
+
+TEST_CASE(should_constexpr_consume_specific_char)
+{
+ constexpr auto sut = [] {
+ GenericLexer sut(StringView { "abcdef" });
+ sut.consume_specific('a');
+ return sut;
+ }();
+ static_assert(sut.peek() == 'b');
+}
+
+TEST_CASE(should_constexpr_consume_specific_string_view)
+{
+ constexpr auto sut = [] {
+ GenericLexer sut(StringView { "abcdef" });
+ sut.consume_specific(StringView { "ab" });
+ return sut;
+ }();
+ static_assert(sut.peek() == 'c');
+}
+
+TEST_CASE(should_constexpr_consume_specific_cstring)
+{
+ constexpr auto sut = [] {
+ GenericLexer sut(StringView { "abcdef" });
+ sut.consume_specific("abcd");
+ return sut;
+ }();
+ static_assert(sut.peek() == 'e');
+}
+
+TEST_CASE(should_constexpr_ignore_until)
+{
+ constexpr auto sut = [] {
+ GenericLexer sut(StringView { "abcdef" });
+ sut.ignore_until('d');
+ return sut;
+ }();
+ static_assert(sut.peek() == 'e');
+}
+
+TEST_CASE(should_constexpr_ignore_until_cstring)
+{
+ constexpr auto sut = [] {
+ GenericLexer sut(StringView { "abcdef" });
+ sut.ignore_until("cde");
+ return sut;
+ }();
+ static_assert(sut.peek() == 'f');
+}
+
+TEST_CASE(should_constexpr_next_is_pred)
+{
+ constexpr auto pred = [](auto c) {
+ return c == 'a';
+ };
+ constexpr GenericLexer sut(StringView { "abcdef" });
+ static_assert(sut.next_is(pred));
+}
+
+TEST_CASE(should_constexpr_ignore_while_pred)
+{
+ constexpr auto sut = [] {
+ constexpr auto pred = [](auto c) {
+ return c == 'a';
+ };
+
+ GenericLexer sut(StringView { "abcdef" });
+ sut.ignore_while(pred);
+ return sut;
+ }();
+ static_assert(sut.peek() == 'b');
+}
+
+TEST_CASE(should_constexpr_ignore_until_pred)
+{
+ constexpr auto sut = [] {
+ constexpr auto pred = [](auto c) {
+ return c == 'c';
+ };
+
+ GenericLexer sut(StringView { "abcdef" });
+ sut.ignore_until(pred);
+ return sut;
+ }();
+ static_assert(sut.peek() == 'c');
+}
diff --git a/Tests/AK/TestHashFunctions.cpp b/Tests/AK/TestHashFunctions.cpp
new file mode 100644
index 0000000000..fa8eafae9e
--- /dev/null
+++ b/Tests/AK/TestHashFunctions.cpp
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/HashFunctions.h>
+#include <AK/Types.h>
+
+TEST_CASE(int_hash)
+{
+ static_assert(int_hash(42) == 3564735745u);
+ static_assert(int_hash(0) == 1177991625u);
+}
+
+TEST_CASE(double_hash)
+{
+ static_assert(double_hash(42) == 524450u);
+ static_assert(double_hash(0) == 12384u);
+}
+
+TEST_CASE(pair_int_hash)
+{
+ static_assert(pair_int_hash(42, 17) == 339337046u);
+ static_assert(pair_int_hash(0, 0) == 954888656u);
+}
+
+TEST_CASE(u64_hash)
+{
+ static_assert(u64_hash(42) == 2824066580u);
+ static_assert(u64_hash(0) == 954888656u);
+}
+
+TEST_CASE(ptr_hash)
+{
+ // These tests are not static_asserts because the values are
+ // different and the goal is to bind the behavior.
+ if constexpr (sizeof(FlatPtr) == 8) {
+ EXPECT_EQ(ptr_hash(FlatPtr(42)), 2824066580u);
+ EXPECT_EQ(ptr_hash(FlatPtr(0)), 954888656u);
+
+ EXPECT_EQ(ptr_hash(reinterpret_cast<const void*>(42)), 2824066580u);
+ EXPECT_EQ(ptr_hash(reinterpret_cast<const void*>(0)), 954888656u);
+ } else {
+ EXPECT_EQ(ptr_hash(FlatPtr(42)), 3564735745u);
+ EXPECT_EQ(ptr_hash(FlatPtr(0)), 1177991625u);
+
+ EXPECT_EQ(ptr_hash(reinterpret_cast<const void*>(42)), 3564735745u);
+ EXPECT_EQ(ptr_hash(reinterpret_cast<const void*>(0)), 1177991625u);
+ }
+}
+
+TEST_CASE(constexpr_ptr_hash)
+{
+ // This test does not check the result because the goal is just to
+ // ensure the function can be executed in a constexpr context. The
+ // "ptr_hash" test binds the result.
+ static_assert(ptr_hash(FlatPtr(42)));
+}
diff --git a/Tests/AK/TestHashMap.cpp b/Tests/AK/TestHashMap.cpp
new file mode 100644
index 0000000000..a057319309
--- /dev/null
+++ b/Tests/AK/TestHashMap.cpp
@@ -0,0 +1,174 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/HashMap.h>
+#include <AK/String.h>
+
+TEST_CASE(construct)
+{
+ using IntIntMap = HashMap<int, int>;
+ EXPECT(IntIntMap().is_empty());
+ EXPECT_EQ(IntIntMap().size(), 0u);
+}
+
+TEST_CASE(construct_from_initializer_list)
+{
+ HashMap<int, String> number_to_string {
+ { 1, "One" },
+ { 2, "Two" },
+ { 3, "Three" },
+ };
+ EXPECT_EQ(number_to_string.is_empty(), false);
+ EXPECT_EQ(number_to_string.size(), 3u);
+}
+
+TEST_CASE(populate)
+{
+ HashMap<int, String> number_to_string;
+ number_to_string.set(1, "One");
+ number_to_string.set(2, "Two");
+ number_to_string.set(3, "Three");
+
+ EXPECT_EQ(number_to_string.is_empty(), false);
+ EXPECT_EQ(number_to_string.size(), 3u);
+}
+
+TEST_CASE(range_loop)
+{
+ HashMap<int, String> number_to_string;
+ EXPECT_EQ(number_to_string.set(1, "One"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(number_to_string.set(2, "Two"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(number_to_string.set(3, "Three"), AK::HashSetResult::InsertedNewEntry);
+
+ int loop_counter = 0;
+ for (auto& it : number_to_string) {
+ EXPECT_EQ(it.value.is_null(), false);
+ ++loop_counter;
+ }
+ EXPECT_EQ(loop_counter, 3);
+}
+
+TEST_CASE(map_remove)
+{
+ HashMap<int, String> number_to_string;
+ EXPECT_EQ(number_to_string.set(1, "One"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(number_to_string.set(2, "Two"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(number_to_string.set(3, "Three"), AK::HashSetResult::InsertedNewEntry);
+
+ EXPECT_EQ(number_to_string.remove(1), true);
+ EXPECT_EQ(number_to_string.size(), 2u);
+ EXPECT(number_to_string.find(1) == number_to_string.end());
+
+ EXPECT_EQ(number_to_string.remove(3), true);
+ EXPECT_EQ(number_to_string.size(), 1u);
+ EXPECT(number_to_string.find(3) == number_to_string.end());
+ EXPECT(number_to_string.find(2) != number_to_string.end());
+}
+
+TEST_CASE(case_insensitive)
+{
+ HashMap<String, int, CaseInsensitiveStringTraits> casemap;
+ EXPECT_EQ(String("nickserv").to_lowercase(), String("NickServ").to_lowercase());
+ EXPECT_EQ(casemap.set("nickserv", 3), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(casemap.set("NickServ", 3), AK::HashSetResult::ReplacedExistingEntry);
+ EXPECT_EQ(casemap.size(), 1u);
+}
+
+TEST_CASE(hashmap_of_nonnullownptr_get)
+{
+ struct Object {
+ Object(const String& s)
+ : string(s)
+ {
+ }
+ String string;
+ };
+
+ HashMap<int, NonnullOwnPtr<Object>> objects;
+ objects.set(1, make<Object>("One"));
+ objects.set(2, make<Object>("Two"));
+ objects.set(3, make<Object>("Three"));
+
+ {
+ auto x = objects.get(2);
+ EXPECT_EQ(x.has_value(), true);
+ EXPECT_EQ(x.value()->string, "Two");
+ }
+
+ {
+ // Do it again to make sure that peeking into the map above didn't
+ // remove the value from the map.
+ auto x = objects.get(2);
+ EXPECT_EQ(x.has_value(), true);
+ EXPECT_EQ(x.value()->string, "Two");
+ }
+
+ EXPECT_EQ(objects.size(), 3u);
+}
+
+TEST_CASE(many_strings)
+{
+ HashMap<String, int> strings;
+ for (int i = 0; i < 999; ++i) {
+ EXPECT_EQ(strings.set(String::number(i), i), AK::HashSetResult::InsertedNewEntry);
+ }
+ EXPECT_EQ(strings.size(), 999u);
+ for (auto& it : strings) {
+ EXPECT_EQ(it.key.to_int().value(), it.value);
+ }
+ for (int i = 0; i < 999; ++i) {
+ EXPECT_EQ(strings.remove(String::number(i)), true);
+ }
+ EXPECT_EQ(strings.is_empty(), true);
+}
+
+TEST_CASE(basic_remove)
+{
+ HashMap<int, int> map;
+ map.set(1, 10);
+ map.set(2, 20);
+ map.set(3, 30);
+
+ EXPECT_EQ(map.remove(3), true);
+ EXPECT_EQ(map.remove(3), false);
+ EXPECT_EQ(map.size(), 2u);
+
+ EXPECT_EQ(map.remove(1), true);
+ EXPECT_EQ(map.remove(1), false);
+ EXPECT_EQ(map.size(), 1u);
+
+ EXPECT_EQ(map.remove(2), true);
+ EXPECT_EQ(map.remove(2), false);
+ EXPECT_EQ(map.size(), 0u);
+}
+
+TEST_CASE(basic_contains)
+{
+ HashMap<int, int> map;
+ map.set(1, 10);
+ map.set(2, 20);
+ map.set(3, 30);
+
+ EXPECT_EQ(map.contains(1), true);
+ EXPECT_EQ(map.contains(2), true);
+ EXPECT_EQ(map.contains(3), true);
+ EXPECT_EQ(map.contains(4), false);
+
+ EXPECT_EQ(map.remove(3), true);
+ EXPECT_EQ(map.contains(3), false);
+ EXPECT_EQ(map.contains(1), true);
+ EXPECT_EQ(map.contains(2), true);
+
+ EXPECT_EQ(map.remove(2), true);
+ EXPECT_EQ(map.contains(2), false);
+ EXPECT_EQ(map.contains(3), false);
+ EXPECT_EQ(map.contains(1), true);
+
+ EXPECT_EQ(map.remove(1), true);
+ EXPECT_EQ(map.contains(1), false);
+}
diff --git a/Tests/AK/TestHashTable.cpp b/Tests/AK/TestHashTable.cpp
new file mode 100644
index 0000000000..55c297e774
--- /dev/null
+++ b/Tests/AK/TestHashTable.cpp
@@ -0,0 +1,175 @@
+/*
+ * Copyright (c) 2021, thislooksfun <tlf@thislooks.fun>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/HashTable.h>
+#include <AK/String.h>
+
+TEST_CASE(construct)
+{
+ using IntTable = HashTable<int>;
+ EXPECT(IntTable().is_empty());
+ EXPECT_EQ(IntTable().size(), 0u);
+}
+
+TEST_CASE(populate)
+{
+ HashTable<String> strings;
+ strings.set("One");
+ strings.set("Two");
+ strings.set("Three");
+
+ EXPECT_EQ(strings.is_empty(), false);
+ EXPECT_EQ(strings.size(), 3u);
+}
+
+TEST_CASE(range_loop)
+{
+ HashTable<String> strings;
+ EXPECT_EQ(strings.set("One"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(strings.set("Two"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(strings.set("Three"), AK::HashSetResult::InsertedNewEntry);
+
+ int loop_counter = 0;
+ for (auto& it : strings) {
+ EXPECT_EQ(it.is_null(), false);
+ ++loop_counter;
+ }
+ EXPECT_EQ(loop_counter, 3);
+}
+
+TEST_CASE(table_remove)
+{
+ HashTable<String> strings;
+ EXPECT_EQ(strings.set("One"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(strings.set("Two"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(strings.set("Three"), AK::HashSetResult::InsertedNewEntry);
+
+ EXPECT_EQ(strings.remove("One"), true);
+ EXPECT_EQ(strings.size(), 2u);
+ EXPECT(strings.find("One") == strings.end());
+
+ EXPECT_EQ(strings.remove("Three"), true);
+ EXPECT_EQ(strings.size(), 1u);
+ EXPECT(strings.find("Three") == strings.end());
+ EXPECT(strings.find("Two") != strings.end());
+}
+
+TEST_CASE(case_insensitive)
+{
+ HashTable<String, CaseInsensitiveStringTraits> casetable;
+ EXPECT_EQ(String("nickserv").to_lowercase(), String("NickServ").to_lowercase());
+ EXPECT_EQ(casetable.set("nickserv"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(casetable.set("NickServ"), AK::HashSetResult::ReplacedExistingEntry);
+ EXPECT_EQ(casetable.size(), 1u);
+}
+
+TEST_CASE(many_strings)
+{
+ HashTable<String> strings;
+ for (int i = 0; i < 999; ++i) {
+ EXPECT_EQ(strings.set(String::number(i)), AK::HashSetResult::InsertedNewEntry);
+ }
+ EXPECT_EQ(strings.size(), 999u);
+ for (int i = 0; i < 999; ++i) {
+ EXPECT_EQ(strings.remove(String::number(i)), true);
+ }
+ EXPECT_EQ(strings.is_empty(), true);
+}
+
+TEST_CASE(many_collisions)
+{
+ struct StringCollisionTraits : public GenericTraits<String> {
+ static unsigned hash(const String&) { return 0; }
+ };
+
+ HashTable<String, StringCollisionTraits> strings;
+ for (int i = 0; i < 999; ++i) {
+ EXPECT_EQ(strings.set(String::number(i)), AK::HashSetResult::InsertedNewEntry);
+ }
+
+ EXPECT_EQ(strings.set("foo"), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(strings.size(), 1000u);
+
+ for (int i = 0; i < 999; ++i) {
+ EXPECT_EQ(strings.remove(String::number(i)), true);
+ }
+
+ // FIXME: Doing this with an "EXPECT_NOT_EQ" would be cleaner.
+ EXPECT_EQ(strings.find("foo") == strings.end(), false);
+}
+
+TEST_CASE(space_reuse)
+{
+ struct StringCollisionTraits : public GenericTraits<String> {
+ static unsigned hash(const String&) { return 0; }
+ };
+
+ HashTable<String, StringCollisionTraits> strings;
+
+ // Add a few items to allow it to do initial resizing.
+ EXPECT_EQ(strings.set("0"), AK::HashSetResult::InsertedNewEntry);
+ for (int i = 1; i < 5; ++i) {
+ EXPECT_EQ(strings.set(String::number(i)), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(strings.remove(String::number(i - 1)), true);
+ }
+
+ auto capacity = strings.capacity();
+
+ for (int i = 5; i < 999; ++i) {
+ EXPECT_EQ(strings.set(String::number(i)), AK::HashSetResult::InsertedNewEntry);
+ EXPECT_EQ(strings.remove(String::number(i - 1)), true);
+ }
+
+ EXPECT_EQ(strings.capacity(), capacity);
+}
+
+TEST_CASE(basic_remove)
+{
+ HashTable<int> table;
+ table.set(1);
+ table.set(2);
+ table.set(3);
+
+ EXPECT_EQ(table.remove(3), true);
+ EXPECT_EQ(table.remove(3), false);
+ EXPECT_EQ(table.size(), 2u);
+
+ EXPECT_EQ(table.remove(1), true);
+ EXPECT_EQ(table.remove(1), false);
+ EXPECT_EQ(table.size(), 1u);
+
+ EXPECT_EQ(table.remove(2), true);
+ EXPECT_EQ(table.remove(2), false);
+ EXPECT_EQ(table.size(), 0u);
+}
+
+TEST_CASE(basic_contains)
+{
+ HashTable<int> table;
+ table.set(1);
+ table.set(2);
+ table.set(3);
+
+ EXPECT_EQ(table.contains(1), true);
+ EXPECT_EQ(table.contains(2), true);
+ EXPECT_EQ(table.contains(3), true);
+ EXPECT_EQ(table.contains(4), false);
+
+ EXPECT_EQ(table.remove(3), true);
+ EXPECT_EQ(table.contains(3), false);
+ EXPECT_EQ(table.contains(1), true);
+ EXPECT_EQ(table.contains(2), true);
+
+ EXPECT_EQ(table.remove(2), true);
+ EXPECT_EQ(table.contains(2), false);
+ EXPECT_EQ(table.contains(3), false);
+ EXPECT_EQ(table.contains(1), true);
+
+ EXPECT_EQ(table.remove(1), true);
+ EXPECT_EQ(table.contains(1), false);
+}
diff --git a/Tests/AK/TestHex.cpp b/Tests/AK/TestHex.cpp
new file mode 100644
index 0000000000..0f94cc03c8
--- /dev/null
+++ b/Tests/AK/TestHex.cpp
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Hex.h>
+
+TEST_CASE(should_decode_hex_digit)
+{
+ EXPECT_EQ(0u, decode_hex_digit('0'));
+ EXPECT_EQ(1u, decode_hex_digit('1'));
+ EXPECT_EQ(2u, decode_hex_digit('2'));
+ EXPECT_EQ(3u, decode_hex_digit('3'));
+ EXPECT_EQ(4u, decode_hex_digit('4'));
+ EXPECT_EQ(5u, decode_hex_digit('5'));
+ EXPECT_EQ(6u, decode_hex_digit('6'));
+ EXPECT_EQ(7u, decode_hex_digit('7'));
+ EXPECT_EQ(8u, decode_hex_digit('8'));
+ EXPECT_EQ(9u, decode_hex_digit('9'));
+ EXPECT_EQ(10u, decode_hex_digit('a'));
+ EXPECT_EQ(11u, decode_hex_digit('b'));
+ EXPECT_EQ(12u, decode_hex_digit('c'));
+ EXPECT_EQ(13u, decode_hex_digit('d'));
+ EXPECT_EQ(14u, decode_hex_digit('e'));
+ EXPECT_EQ(15u, decode_hex_digit('f'));
+ EXPECT_EQ(10u, decode_hex_digit('A'));
+ EXPECT_EQ(11u, decode_hex_digit('B'));
+ EXPECT_EQ(12u, decode_hex_digit('C'));
+ EXPECT_EQ(13u, decode_hex_digit('D'));
+ EXPECT_EQ(14u, decode_hex_digit('E'));
+ EXPECT_EQ(15u, decode_hex_digit('F'));
+}
+
+TEST_CASE(should_constexpr_decode_hex_digit)
+{
+ static_assert(0u == decode_hex_digit('0'));
+ static_assert(1u == decode_hex_digit('1'));
+ static_assert(2u == decode_hex_digit('2'));
+ static_assert(3u == decode_hex_digit('3'));
+ static_assert(4u == decode_hex_digit('4'));
+ static_assert(5u == decode_hex_digit('5'));
+ static_assert(6u == decode_hex_digit('6'));
+ static_assert(7u == decode_hex_digit('7'));
+ static_assert(8u == decode_hex_digit('8'));
+ static_assert(9u == decode_hex_digit('9'));
+ static_assert(10u == decode_hex_digit('a'));
+ static_assert(11u == decode_hex_digit('b'));
+ static_assert(12u == decode_hex_digit('c'));
+ static_assert(13u == decode_hex_digit('d'));
+ static_assert(14u == decode_hex_digit('e'));
+ static_assert(15u == decode_hex_digit('f'));
+ static_assert(10u == decode_hex_digit('A'));
+ static_assert(11u == decode_hex_digit('B'));
+ static_assert(12u == decode_hex_digit('C'));
+ static_assert(13u == decode_hex_digit('D'));
+ static_assert(14u == decode_hex_digit('E'));
+ static_assert(15u == decode_hex_digit('F'));
+}
diff --git a/Tests/AK/TestIPv4Address.cpp b/Tests/AK/TestIPv4Address.cpp
new file mode 100644
index 0000000000..b8f07d1e3c
--- /dev/null
+++ b/Tests/AK/TestIPv4Address.cpp
@@ -0,0 +1,153 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Endian.h>
+#include <AK/IPv4Address.h>
+
+TEST_CASE(should_default_contructor_with_0s)
+{
+ constexpr IPv4Address addr {};
+
+ static_assert(addr.is_zero());
+
+ EXPECT(addr.is_zero());
+}
+
+TEST_CASE(should_construct_from_c_array)
+{
+ constexpr auto addr = [] {
+ const u8 a[4] = { 1, 2, 3, 4 };
+ return IPv4Address(a);
+ }();
+
+ static_assert(!addr.is_zero());
+
+ EXPECT(!addr.is_zero());
+}
+
+TEST_CASE(should_construct_from_u32)
+{
+ constexpr auto addr = [] {
+ const NetworkOrdered<u32> a = 0x11'22'33'44;
+ return IPv4Address(a);
+ }();
+
+ static_assert(!addr.is_zero());
+
+ EXPECT(!addr.is_zero());
+}
+
+TEST_CASE(should_get_octets_by_byte_offset)
+{
+ constexpr IPv4Address addr(1, 25, 39, 42);
+
+ static_assert(1 == addr[0]);
+ static_assert(25 == addr[1]);
+ static_assert(39 == addr[2]);
+ static_assert(42 == addr[3]);
+
+ EXPECT_EQ(1, addr[0]);
+ EXPECT_EQ(25, addr[1]);
+ EXPECT_EQ(39, addr[2]);
+ EXPECT_EQ(42, addr[3]);
+}
+
+TEST_CASE(should_convert_to_string)
+{
+ constexpr IPv4Address addr(1, 25, 39, 42);
+
+ EXPECT_EQ("1.25.39.42", addr.to_string());
+}
+
+TEST_CASE(should_make_ipv4_address_from_string)
+{
+ const auto addr = IPv4Address::from_string("192.168.0.1");
+
+ EXPECT(addr.has_value());
+ EXPECT_EQ(192, addr.value()[0]);
+ EXPECT_EQ(168, addr.value()[1]);
+ EXPECT_EQ(0, addr.value()[2]);
+ EXPECT_EQ(1, addr.value()[3]);
+}
+
+TEST_CASE(should_make_empty_optional_from_bad_string)
+{
+ const auto addr = IPv4Address::from_string("bad string");
+
+ EXPECT(!addr.has_value());
+}
+
+TEST_CASE(should_make_empty_optional_from_out_of_range_values)
+{
+ const auto addr = IPv4Address::from_string("192.168.0.500");
+
+ EXPECT(!addr.has_value());
+}
+
+TEST_CASE(should_fill_d_octet_from_1_part)
+{
+ const auto addr = IPv4Address::from_string("1");
+
+ EXPECT(addr.has_value());
+ EXPECT_EQ(0, addr.value()[0]);
+ EXPECT_EQ(0, addr.value()[1]);
+ EXPECT_EQ(0, addr.value()[2]);
+ EXPECT_EQ(1, addr.value()[3]);
+}
+
+TEST_CASE(should_fill_a_and_d_octets_from_2_parts)
+{
+ const auto addr = IPv4Address::from_string("192.1");
+
+ EXPECT(addr.has_value());
+ EXPECT_EQ(192, addr.value()[0]);
+ EXPECT_EQ(0, addr.value()[1]);
+ EXPECT_EQ(0, addr.value()[2]);
+ EXPECT_EQ(1, addr.value()[3]);
+}
+
+TEST_CASE(should_fill_a_b_d_octets_from_3_parts)
+{
+ const auto addr = IPv4Address::from_string("192.168.1");
+
+ EXPECT(addr.has_value());
+ EXPECT_EQ(192, addr.value()[0]);
+ EXPECT_EQ(168, addr.value()[1]);
+ EXPECT_EQ(0, addr.value()[2]);
+ EXPECT_EQ(1, addr.value()[3]);
+}
+
+TEST_CASE(should_convert_to_in_addr_t)
+{
+ constexpr IPv4Address addr(1, 2, 3, 4);
+
+ static_assert(0x04'03'02'01u == addr.to_in_addr_t());
+
+ EXPECT_EQ(0x04'03'02'01u, addr.to_in_addr_t());
+}
+
+TEST_CASE(should_convert_to_u32)
+{
+ constexpr IPv4Address addr(1, 2, 3, 4);
+
+ static_assert(0x04'03'02'01u == addr.to_in_addr_t());
+
+ EXPECT_EQ(0x04'03'02'01u, addr.to_u32());
+}
+
+TEST_CASE(should_compare)
+{
+ constexpr IPv4Address addr_a(1, 2, 3, 4);
+ constexpr IPv4Address addr_b(1, 2, 3, 5);
+
+ static_assert(addr_a != addr_b);
+ static_assert(addr_a == addr_a);
+
+ EXPECT(addr_a != addr_b);
+ EXPECT(addr_a == addr_a);
+}
diff --git a/Tests/AK/TestIndexSequence.cpp b/Tests/AK/TestIndexSequence.cpp
new file mode 100644
index 0000000000..31b9401651
--- /dev/null
+++ b/Tests/AK/TestIndexSequence.cpp
@@ -0,0 +1,49 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/StdLibExtras.h>
+#include <AK/TypeList.h>
+
+template<typename F, typename... Args>
+F for_each_argument(F f, Args&&... args)
+{
+ (f(forward<Args>(args)), ...);
+ return f;
+}
+
+template<typename T, T... ints>
+void verify_sequence(IntegerSequence<T, ints...> seq, std::initializer_list<T> expected)
+{
+ EXPECT_EQ(seq.size(), expected.size());
+ for_each_argument([idx = expected.begin()](T t) mutable { EXPECT_EQ(t, *(idx++)); }, ints...);
+}
+
+TEST_CASE(TestIndexSequence)
+{
+ constexpr auto integer_seq1 = IntegerSequence<int, 0, 1, 2, 3, 4> {};
+ constexpr auto integer_seq2 = MakeIntegerSequence<int, 5> {};
+ static_assert(IsSame<decltype(integer_seq1), decltype(integer_seq2)>, "");
+
+ static_assert(integer_seq1.size() == 5, "");
+ static_assert(integer_seq2.size() == 5, "");
+
+ constexpr auto index_seq1 = IndexSequence<0, 1, 2> {};
+ constexpr auto index_seq2 = MakeIndexSequence<3> {};
+ static_assert(IsSame<decltype(index_seq1), decltype(index_seq2)>, "");
+
+ verify_sequence(MakeIndexSequence<10> {}, std::initializer_list<unsigned> { 0U, 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U });
+ verify_sequence(MakeIntegerSequence<long, 16> {}, std::initializer_list<long> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
+}
+
+TEST_CASE(TypeList)
+{
+ using MyTypes = TypeList<int, bool, char>;
+ static_assert(IsSame<MyTypes::Type<0>, int>, "");
+ static_assert(IsSame<MyTypes::Type<1>, bool>, "");
+ static_assert(IsSame<MyTypes::Type<2>, char>, "");
+}
diff --git a/Tests/AK/TestIntrusiveList.cpp b/Tests/AK/TestIntrusiveList.cpp
new file mode 100644
index 0000000000..f75db9afb7
--- /dev/null
+++ b/Tests/AK/TestIntrusiveList.cpp
@@ -0,0 +1,123 @@
+/*
+ * Copyright (c) 2021, Brian Gianforcaro <bgianf@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/IntrusiveList.h>
+#include <AK/NonnullOwnPtr.h>
+#include <AK/RefPtr.h>
+
+class IntrusiveTestItem {
+public:
+ IntrusiveTestItem() = default;
+ IntrusiveListNode<IntrusiveTestItem> m_list_node;
+};
+using IntrusiveTestList = IntrusiveList<IntrusiveTestItem, RawPtr<IntrusiveTestItem>, &IntrusiveTestItem::m_list_node>;
+
+TEST_CASE(construct)
+{
+ IntrusiveTestList empty;
+ EXPECT(empty.is_empty());
+}
+
+TEST_CASE(insert)
+{
+ IntrusiveTestList list;
+ list.append(*new IntrusiveTestItem());
+
+ EXPECT(!list.is_empty());
+
+ delete list.take_last();
+}
+
+TEST_CASE(enumeration)
+{
+ constexpr size_t expected_size = 10;
+ IntrusiveTestList list;
+ for (size_t i = 0; i < expected_size; i++) {
+ list.append(*new IntrusiveTestItem());
+ }
+
+ size_t actual_size = 0;
+ for (auto& elem : list) {
+ (void)elem;
+ actual_size++;
+ }
+ EXPECT_EQ(expected_size, actual_size);
+ while (auto elem = list.take_first()) {
+ delete elem;
+ }
+}
+
+class IntrusiveRefPtrItem : public RefCounted<IntrusiveRefPtrItem> {
+public:
+ IntrusiveRefPtrItem() = default;
+ IntrusiveListNode<IntrusiveRefPtrItem, RefPtr<IntrusiveRefPtrItem>> m_list_node;
+};
+using IntrusiveRefPtrList = IntrusiveList<IntrusiveRefPtrItem, RefPtr<IntrusiveRefPtrItem>, &IntrusiveRefPtrItem::m_list_node>;
+
+TEST_CASE(intrusive_ref_ptr_no_ref_leaks)
+{
+ auto item = adopt_ref(*new IntrusiveRefPtrItem());
+ EXPECT_EQ(1u, item->ref_count());
+ IntrusiveRefPtrList ref_list;
+
+ ref_list.append(*item);
+ EXPECT_EQ(2u, item->ref_count());
+
+ ref_list.remove(*item);
+ EXPECT_EQ(1u, item->ref_count());
+}
+
+TEST_CASE(intrusive_ref_ptr_clear)
+{
+ auto item = adopt_ref(*new IntrusiveRefPtrItem());
+ EXPECT_EQ(1u, item->ref_count());
+ IntrusiveRefPtrList ref_list;
+
+ ref_list.append(*item);
+ EXPECT_EQ(2u, item->ref_count());
+
+ ref_list.clear();
+ EXPECT_EQ(1u, item->ref_count());
+}
+
+TEST_CASE(intrusive_ref_ptr_destructor)
+{
+ auto item = adopt_ref(*new IntrusiveRefPtrItem());
+ EXPECT_EQ(1u, item->ref_count());
+
+ {
+ IntrusiveRefPtrList ref_list;
+ ref_list.append(*item);
+ EXPECT_EQ(2u, item->ref_count());
+ }
+
+ EXPECT_EQ(1u, item->ref_count());
+}
+
+class IntrusiveNonnullRefPtrItem : public RefCounted<IntrusiveNonnullRefPtrItem> {
+public:
+ IntrusiveNonnullRefPtrItem() = default;
+ IntrusiveListNode<IntrusiveNonnullRefPtrItem, NonnullRefPtr<IntrusiveNonnullRefPtrItem>> m_list_node;
+};
+using IntrusiveNonnullRefPtrList = IntrusiveList<IntrusiveNonnullRefPtrItem, NonnullRefPtr<IntrusiveNonnullRefPtrItem>, &IntrusiveNonnullRefPtrItem::m_list_node>;
+
+TEST_CASE(intrusive_nonnull_ref_ptr_intrusive)
+{
+ auto item = adopt_ref(*new IntrusiveNonnullRefPtrItem());
+ EXPECT_EQ(1u, item->ref_count());
+ IntrusiveNonnullRefPtrList nonnull_ref_list;
+
+ nonnull_ref_list.append(*item);
+ EXPECT_EQ(2u, item->ref_count());
+ EXPECT(!nonnull_ref_list.is_empty());
+
+ nonnull_ref_list.remove(*item);
+ EXPECT_EQ(1u, item->ref_count());
+
+ EXPECT(nonnull_ref_list.is_empty());
+}
diff --git a/Tests/AK/TestIntrusiveRedBlackTree.cpp b/Tests/AK/TestIntrusiveRedBlackTree.cpp
new file mode 100644
index 0000000000..207b026cec
--- /dev/null
+++ b/Tests/AK/TestIntrusiveRedBlackTree.cpp
@@ -0,0 +1,116 @@
+/*
+ * Copyright (c) 2021, Idan Horowitz <idan.horowitz@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/IntrusiveRedBlackTree.h>
+#include <AK/NonnullOwnPtrVector.h>
+#include <AK/Random.h>
+
+class IntrusiveTest {
+public:
+ IntrusiveTest(int key, int value)
+ : m_tree_node(key)
+ , m_some_value(value)
+ {
+ }
+
+ IntrusiveRedBlackTreeNode<int> m_tree_node;
+ int m_some_value;
+};
+
+TEST_CASE(construct)
+{
+ IntrusiveRedBlackTree<int, IntrusiveTest, &IntrusiveTest::m_tree_node> empty;
+ EXPECT(empty.is_empty());
+ EXPECT(empty.size() == 0);
+}
+
+TEST_CASE(ints)
+{
+ IntrusiveRedBlackTree<int, IntrusiveTest, &IntrusiveTest::m_tree_node> test;
+ IntrusiveTest first { 1, 10 };
+ test.insert(first);
+ IntrusiveTest second { 3, 20 };
+ test.insert(second);
+ IntrusiveTest third { 2, 30 };
+ test.insert(third);
+ EXPECT_EQ(test.size(), 3u);
+ EXPECT_EQ(test.find(3)->m_some_value, 20);
+ EXPECT_EQ(test.find(2)->m_some_value, 30);
+ EXPECT_EQ(test.find(1)->m_some_value, 10);
+ EXPECT(!test.remove(4));
+ EXPECT(test.remove(2));
+ EXPECT(test.remove(1));
+ EXPECT(test.remove(3));
+ EXPECT_EQ(test.size(), 0u);
+}
+
+TEST_CASE(largest_smaller_than)
+{
+ IntrusiveRedBlackTree<int, IntrusiveTest, &IntrusiveTest::m_tree_node> test;
+ IntrusiveTest first { 1, 10 };
+ test.insert(first);
+ IntrusiveTest second { 11, 20 };
+ test.insert(second);
+ IntrusiveTest third { 21, 30 };
+ test.insert(third);
+ EXPECT_EQ(test.size(), 3u);
+ EXPECT_EQ(test.find_largest_not_above(3)->m_some_value, 10);
+ EXPECT_EQ(test.find_largest_not_above(17)->m_some_value, 20);
+ EXPECT_EQ(test.find_largest_not_above(22)->m_some_value, 30);
+ EXPECT_EQ(test.find_largest_not_above(-5), nullptr);
+ VERIFY(test.remove(1));
+ VERIFY(test.remove(11));
+ VERIFY(test.remove(21));
+}
+
+TEST_CASE(key_ordered_iteration)
+{
+ constexpr auto amount = 10000;
+ IntrusiveRedBlackTree<int, IntrusiveTest, &IntrusiveTest::m_tree_node> test;
+ NonnullOwnPtrVector<IntrusiveTest> m_entries;
+ Array<int, amount> keys {};
+
+ // generate random key order
+ for (int i = 0; i < amount; i++) {
+ keys[i] = i;
+ }
+ for (size_t i = 0; i < amount; i++) {
+ swap(keys[i], keys[get_random<size_t>() % amount]);
+ }
+
+ // insert random keys
+ for (size_t i = 0; i < amount; i++) {
+ auto entry = make<IntrusiveTest>(keys[i], keys[i]);
+ test.insert(*entry);
+ m_entries.append(move(entry));
+ }
+
+ // check key-ordered iteration
+ int index = 0;
+ for (auto& value : test) {
+ EXPECT(value.m_some_value == index++);
+ }
+
+ // ensure we can remove all of them (aka, tree structure is not destroyed somehow)
+ for (size_t i = 0; i < amount; i++) {
+ EXPECT(test.remove(i));
+ }
+}
+
+TEST_CASE(clear)
+{
+ IntrusiveRedBlackTree<int, IntrusiveTest, &IntrusiveTest::m_tree_node> test;
+ NonnullOwnPtrVector<IntrusiveTest> m_entries;
+ for (size_t i = 0; i < 1000; i++) {
+ auto entry = make<IntrusiveTest>(i, i);
+ test.insert(*entry);
+ m_entries.append(move(entry));
+ }
+ test.clear();
+ EXPECT_EQ(test.size(), 0u);
+}
diff --git a/Tests/AK/TestJSON.cpp b/Tests/AK/TestJSON.cpp
new file mode 100644
index 0000000000..b1c8b5d0e7
--- /dev/null
+++ b/Tests/AK/TestJSON.cpp
@@ -0,0 +1,100 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/HashMap.h>
+#include <AK/JsonArray.h>
+#include <AK/JsonObject.h>
+#include <AK/JsonValue.h>
+#include <AK/String.h>
+#include <AK/StringBuilder.h>
+
+TEST_CASE(load_form)
+{
+ FILE* fp = fopen("test.frm", "r");
+ VERIFY(fp);
+
+ StringBuilder builder;
+ for (;;) {
+ char buffer[1024];
+ if (!fgets(buffer, sizeof(buffer), fp))
+ break;
+ builder.append(buffer);
+ }
+
+ fclose(fp);
+
+ JsonValue form_json = JsonValue::from_string(builder.to_string()).value();
+
+ EXPECT(form_json.is_object());
+
+ auto name = form_json.as_object().get("name").to_string();
+
+ EXPECT_EQ(name, "Form1");
+
+ auto widgets = form_json.as_object().get("widgets").as_array();
+
+ widgets.for_each([&](const JsonValue& widget_value) {
+ auto& widget_object = widget_value.as_object();
+ auto widget_class = widget_object.get("class").as_string();
+ widget_object.for_each_member([&]([[maybe_unused]] auto& property_name, [[maybe_unused]] const JsonValue& property_value) {
+ });
+ });
+}
+
+TEST_CASE(json_empty_string)
+{
+ auto json = JsonValue::from_string("\"\"").value();
+ EXPECT_EQ(json.type(), JsonValue::Type::String);
+ EXPECT_EQ(json.as_string().is_null(), false);
+ EXPECT_EQ(json.as_string().is_empty(), true);
+}
+
+TEST_CASE(json_string)
+{
+ auto json = JsonValue::from_string("\"A\"").value();
+ EXPECT_EQ(json.type(), JsonValue::Type::String);
+ EXPECT_EQ(json.as_string().is_null(), false);
+ EXPECT_EQ(json.as_string().length(), size_t { 1 });
+ EXPECT_EQ(json.as_string() == "A", true);
+}
+
+TEST_CASE(json_utf8_character)
+{
+ auto json = JsonValue::from_string("\"\\u0041\"").value();
+ EXPECT_EQ(json.type(), JsonValue::Type::String);
+ EXPECT_EQ(json.as_string().is_null(), false);
+ EXPECT_EQ(json.as_string().length(), size_t { 1 });
+ EXPECT_EQ(json.as_string() == "A", true);
+}
+
+TEST_CASE(json_utf8_multibyte)
+{
+ auto json = JsonValue::from_string("\"š\"").value();
+ EXPECT_EQ(json.type(), JsonValue::Type::String);
+ EXPECT_EQ(json.as_string().is_null(), false);
+ EXPECT_EQ(json.as_string().length(), size_t { 2 });
+ EXPECT_EQ(json.as_string() == "š", true);
+ EXPECT_EQ(json.as_string() == "\xc5\xa1", true);
+}
+
+TEST_CASE(json_64_bit_value)
+{
+ auto big_value = 0x12345678aabbccddull;
+ JsonValue big_json_value(big_value);
+ JsonValue big_json_value_copy = big_json_value;
+ EXPECT_EQ(big_json_value.as_u64(), big_json_value_copy.as_u64());
+}
+
+TEST_CASE(json_duplicate_keys)
+{
+ JsonObject json;
+ json.set("test", "foo");
+ json.set("test", "bar");
+ json.set("test", "baz");
+ EXPECT_EQ(json.to_string(), "{\"test\":\"baz\"}");
+}
diff --git a/Tests/AK/TestLexicalPath.cpp b/Tests/AK/TestLexicalPath.cpp
new file mode 100644
index 0000000000..044f5f157a
--- /dev/null
+++ b/Tests/AK/TestLexicalPath.cpp
@@ -0,0 +1,76 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/LexicalPath.h>
+#include <AK/String.h>
+
+TEST_CASE(construct)
+{
+ EXPECT_EQ(LexicalPath().is_valid(), false);
+}
+
+TEST_CASE(basic)
+{
+ LexicalPath path("/abc/def/ghi.txt");
+ EXPECT_EQ(path.is_valid(), true);
+ EXPECT_EQ(path.basename(), "ghi.txt");
+ EXPECT_EQ(path.title(), "ghi");
+ EXPECT_EQ(path.extension(), "txt");
+ EXPECT_EQ(path.parts().size(), 3u);
+ EXPECT_EQ(path.parts(), Vector<String>({ "abc", "def", "ghi.txt" }));
+ EXPECT_EQ(path.string(), "/abc/def/ghi.txt");
+}
+
+TEST_CASE(dotdot_coalescing)
+{
+ EXPECT_EQ(LexicalPath("/home/user/../../not/home").string(), "/not/home");
+ EXPECT_EQ(LexicalPath("/../../../../").string(), "/");
+}
+
+TEST_CASE(has_extension)
+{
+ {
+ LexicalPath path("/tmp/simple.png");
+ EXPECT(path.has_extension(".png"));
+ EXPECT(path.has_extension(".pnG"));
+ EXPECT(path.has_extension(".PNG"));
+ }
+
+ {
+ LexicalPath path("/TMP/SIMPLE.PNG");
+ EXPECT(path.has_extension(".png"));
+ EXPECT(path.has_extension(".pnG"));
+ EXPECT(path.has_extension(".PNG"));
+ }
+
+ {
+ LexicalPath path(".png");
+ EXPECT(path.has_extension(".png"));
+ }
+
+ {
+ LexicalPath path;
+ EXPECT_EQ(path.has_extension(".png"), false);
+ }
+
+ {
+ LexicalPath path("png");
+ EXPECT_EQ(path.has_extension(".png"), false);
+ }
+}
+
+TEST_CASE(relative_path)
+{
+ EXPECT_EQ(LexicalPath::relative_path("/tmp/abc.txt", "/tmp"), "abc.txt");
+ EXPECT_EQ(LexicalPath::relative_path("/tmp/abc.txt", "/tmp/"), "abc.txt");
+ EXPECT_EQ(LexicalPath::relative_path("/tmp/abc.txt", "/"), "tmp/abc.txt");
+ EXPECT_EQ(LexicalPath::relative_path("/tmp/abc.txt", "/usr"), "/tmp/abc.txt");
+
+ EXPECT_EQ(LexicalPath::relative_path("/tmp/foo.txt", "tmp"), String {});
+ EXPECT_EQ(LexicalPath::relative_path("tmp/foo.txt", "/tmp"), String {});
+}
diff --git a/Tests/AK/TestMACAddress.cpp b/Tests/AK/TestMACAddress.cpp
new file mode 100644
index 0000000000..f91ae043a2
--- /dev/null
+++ b/Tests/AK/TestMACAddress.cpp
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/MACAddress.h>
+#include <AK/Types.h>
+
+TEST_CASE(should_default_construct)
+{
+ constexpr MACAddress sut {};
+ static_assert(sut.is_zero());
+ EXPECT(sut.is_zero());
+}
+
+TEST_CASE(should_braces_construct)
+{
+ constexpr MACAddress sut { 1, 2, 3, 4, 5, 6 };
+ static_assert(!sut.is_zero());
+ EXPECT(!sut.is_zero());
+}
+
+TEST_CASE(should_construct_from_6_octets)
+{
+ constexpr MACAddress sut(1, 2, 3, 4, 5, 6);
+ static_assert(!sut.is_zero());
+ EXPECT(!sut.is_zero());
+}
+
+TEST_CASE(should_provide_read_access_to_octet_by_index)
+{
+ constexpr auto is_all_expected = [](auto& sut) {
+ for (auto i = 0u; i < sizeof(MACAddress); ++i) {
+ if (sut[i] != i + 1) {
+ return false;
+ }
+ }
+ return true;
+ };
+
+ constexpr MACAddress sut(1, 2, 3, 4, 5, 6);
+
+ static_assert(is_all_expected(sut));
+
+ for (auto i = 0u; i < sizeof(MACAddress); ++i) {
+ EXPECT_EQ(i + 1, sut[i]);
+ }
+}
+
+TEST_CASE(should_provide_write_access_to_octet_by_index)
+{
+ constexpr auto sut = [] {
+ MACAddress m {};
+ for (auto i = 0u; i < sizeof(MACAddress); ++i) {
+ m[i] = i + 1;
+ }
+ return m;
+ }();
+
+ constexpr MACAddress expected(1, 2, 3, 4, 5, 6);
+
+ static_assert(expected == sut);
+}
+
+TEST_CASE(should_equality_compare)
+{
+ constexpr MACAddress a(1, 2, 3, 4, 5, 6);
+ constexpr MACAddress b(1, 2, 3, 42, 5, 6);
+
+ static_assert(a == a);
+ static_assert(a != b);
+
+ EXPECT(a == a);
+ EXPECT(a != b);
+}
+
+TEST_CASE(should_string_format)
+{
+ MACAddress sut(1, 2, 3, 4, 5, 6);
+ EXPECT_EQ("01:02:03:04:05:06", sut.to_string());
+}
diff --git a/Tests/AK/TestMemMem.cpp b/Tests/AK/TestMemMem.cpp
new file mode 100644
index 0000000000..f4dd0a3e52
--- /dev/null
+++ b/Tests/AK/TestMemMem.cpp
@@ -0,0 +1,68 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/MemMem.h>
+
+TEST_CASE(bitap)
+{
+ Array<u8, 8> haystack { 1, 0, 1, 2, 3, 4, 5, 0 };
+ Array<u8, 4> needle_0 { 2, 3, 4, 5 };
+ Array<u8, 4> needle_1 { 1, 2, 3, 4 };
+ Array<u8, 4> needle_2 { 3, 4, 5, 0 };
+ Array<u8, 4> needle_3 { 3, 4, 5, 6 };
+
+ auto result_0 = AK::memmem(haystack.data(), haystack.size(), needle_0.data(), needle_0.size());
+ auto result_1 = AK::memmem(haystack.data(), haystack.size(), needle_1.data(), needle_1.size());
+ auto result_2 = AK::memmem(haystack.data(), haystack.size(), needle_2.data(), needle_2.size());
+ auto result_3 = AK::memmem(haystack.data(), haystack.size(), needle_3.data(), needle_3.size());
+
+ EXPECT_EQ(result_0, &haystack[3]);
+ EXPECT_EQ(result_1, &haystack[2]);
+ EXPECT_EQ(result_2, &haystack[4]);
+ EXPECT_EQ(result_3, nullptr);
+}
+
+TEST_CASE(kmp_one_chunk)
+{
+ Array<u8, 8> haystack { 1, 0, 1, 2, 3, 4, 5, 0 };
+ Array<Array<u8, 8>, 1> haystack_arr { haystack };
+ Array<u8, 4> needle_0 { 2, 3, 4, 5 };
+ Array<u8, 4> needle_1 { 1, 2, 3, 4 };
+ Array<u8, 4> needle_2 { 3, 4, 5, 0 };
+ Array<u8, 4> needle_3 { 3, 4, 5, 6 };
+
+ auto result_0 = AK::memmem(haystack_arr.begin(), haystack_arr.end(), needle_0);
+ auto result_1 = AK::memmem(haystack_arr.begin(), haystack_arr.end(), needle_1);
+ auto result_2 = AK::memmem(haystack_arr.begin(), haystack_arr.end(), needle_2);
+ auto result_3 = AK::memmem(haystack_arr.begin(), haystack_arr.end(), needle_3);
+
+ EXPECT_EQ(result_0.value_or(9), 3u);
+ EXPECT_EQ(result_1.value_or(9), 2u);
+ EXPECT_EQ(result_2.value_or(9), 4u);
+ EXPECT(!result_3.has_value());
+}
+
+TEST_CASE(kmp_two_chunks)
+{
+ Array<u8, 4> haystack_first_half { 1, 0, 1, 2 }, haystack_second_half { 3, 4, 5, 0 };
+ Array<Array<u8, 4>, 2> haystack { haystack_first_half, haystack_second_half };
+ Array<u8, 4> needle_0 { 2, 3, 4, 5 };
+ Array<u8, 4> needle_1 { 1, 2, 3, 4 };
+ Array<u8, 4> needle_2 { 3, 4, 5, 0 };
+ Array<u8, 4> needle_3 { 3, 4, 5, 6 };
+
+ auto result_0 = AK::memmem(haystack.begin(), haystack.end(), needle_0);
+ auto result_1 = AK::memmem(haystack.begin(), haystack.end(), needle_1);
+ auto result_2 = AK::memmem(haystack.begin(), haystack.end(), needle_2);
+ auto result_3 = AK::memmem(haystack.begin(), haystack.end(), needle_3);
+
+ EXPECT_EQ(result_0.value_or(9), 3u);
+ EXPECT_EQ(result_1.value_or(9), 2u);
+ EXPECT_EQ(result_2.value_or(9), 4u);
+ EXPECT(!result_3.has_value());
+}
diff --git a/Tests/AK/TestMemoryStream.cpp b/Tests/AK/TestMemoryStream.cpp
new file mode 100644
index 0000000000..90512fe456
--- /dev/null
+++ b/Tests/AK/TestMemoryStream.cpp
@@ -0,0 +1,222 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Array.h>
+#include <AK/MemoryStream.h>
+
+TEST_CASE(read_an_integer)
+{
+ u32 expected = 0x01020304, actual;
+
+ InputMemoryStream stream { { &expected, sizeof(expected) } };
+ stream >> actual;
+
+ EXPECT(!stream.has_any_error() && stream.eof());
+ EXPECT_EQ(expected, actual);
+}
+
+TEST_CASE(read_a_bool)
+{
+ bool expected = true, actual;
+
+ InputMemoryStream stream { { &expected, sizeof(expected) } };
+ stream >> actual;
+
+ EXPECT(!stream.has_any_error() && stream.eof());
+ EXPECT_EQ(expected, actual);
+}
+
+TEST_CASE(read_a_double)
+{
+ double expected = 3.141592653589793, actual;
+
+ InputMemoryStream stream { { &expected, sizeof(expected) } };
+ stream >> actual;
+
+ EXPECT(!stream.has_any_error() && stream.eof());
+ EXPECT_EQ(expected, actual);
+}
+
+TEST_CASE(recoverable_error)
+{
+ u32 expected = 0x01020304, actual = 0;
+ u64 to_large_value = 0;
+
+ InputMemoryStream stream { { &expected, sizeof(expected) } };
+
+ EXPECT(!stream.has_any_error() && !stream.eof());
+ stream >> to_large_value;
+ EXPECT(stream.has_recoverable_error() && !stream.eof());
+
+ EXPECT(stream.handle_recoverable_error());
+ EXPECT(!stream.has_any_error() && !stream.eof());
+
+ stream >> actual;
+ EXPECT(!stream.has_any_error() && stream.eof());
+ EXPECT_EQ(expected, actual);
+}
+
+TEST_CASE(chain_stream_operator)
+{
+ const Array<u8, 4> expected { 0, 1, 2, 3 };
+ Array<u8, 4> actual;
+
+ InputMemoryStream stream { expected };
+
+ stream >> actual[0] >> actual[1] >> actual[2] >> actual[3];
+ EXPECT(!stream.has_any_error() && stream.eof());
+
+ EXPECT_EQ(expected, actual);
+}
+
+TEST_CASE(seeking_slicing_offset)
+{
+ const Array<u8, 8> input { 0, 1, 2, 3, 4, 5, 6, 7 };
+ const Array<u8, 4> expected0 { 0, 1, 2, 3 };
+ const Array<u8, 4> expected1 { 4, 5, 6, 7 };
+ const Array<u8, 4> expected2 { 1, 2, 3, 4 };
+
+ Array<u8, 4> actual0 {}, actual1 {}, actual2 {};
+
+ InputMemoryStream stream { input };
+
+ stream >> actual0;
+ EXPECT(!stream.has_any_error() && !stream.eof());
+ EXPECT_EQ(expected0, actual0);
+
+ stream.seek(4);
+ stream >> actual1;
+ EXPECT(!stream.has_any_error() && stream.eof());
+ EXPECT_EQ(expected1, actual1);
+
+ stream.seek(1);
+ stream >> actual2;
+ EXPECT(!stream.has_any_error() && !stream.eof());
+ EXPECT_EQ(expected2, actual2);
+}
+
+TEST_CASE(duplex_simple)
+{
+ DuplexMemoryStream stream;
+
+ EXPECT(stream.eof());
+ stream << 42;
+ EXPECT(!stream.eof());
+
+ int value;
+ stream >> value;
+ EXPECT_EQ(value, 42);
+ EXPECT(stream.eof());
+}
+
+TEST_CASE(duplex_large_buffer)
+{
+ DuplexMemoryStream stream;
+
+ Array<u8, 1024> one_kibibyte;
+
+ EXPECT_EQ(stream.size(), 0ul);
+
+ for (size_t idx = 0; idx < 256; ++idx)
+ stream << one_kibibyte;
+
+ EXPECT_EQ(stream.size(), 256 * 1024ul);
+
+ for (size_t idx = 0; idx < 128; ++idx)
+ stream >> one_kibibyte;
+
+ EXPECT_EQ(stream.size(), 128 * 1024ul);
+
+ for (size_t idx = 0; idx < 128; ++idx)
+ stream >> one_kibibyte;
+
+ EXPECT(stream.eof());
+}
+
+TEST_CASE(read_endian_values)
+{
+ const Array<u8, 8> input { 0, 1, 2, 3, 4, 5, 6, 7 };
+ InputMemoryStream stream { input };
+
+ LittleEndian<u32> value1;
+ BigEndian<u32> value2;
+ stream >> value1 >> value2;
+
+ EXPECT_EQ(value1, 0x03020100u);
+ EXPECT_EQ(value2, 0x04050607u);
+}
+
+TEST_CASE(write_endian_values)
+{
+ const Array<u8, 8> expected { 4, 3, 2, 1, 1, 2, 3, 4 };
+
+ DuplexMemoryStream stream;
+ stream << LittleEndian<u32> { 0x01020304 } << BigEndian<u32> { 0x01020304 };
+
+ EXPECT_EQ(stream.size(), 8u);
+ EXPECT(expected.span() == stream.copy_into_contiguous_buffer().span());
+}
+
+TEST_CASE(new_output_memory_stream)
+{
+ Array<u8, 16> buffer;
+ OutputMemoryStream stream { buffer };
+
+ EXPECT_EQ(stream.size(), 0u);
+ EXPECT_EQ(stream.remaining(), 16u);
+
+ stream << LittleEndian<u16>(0x12'87);
+
+ EXPECT_EQ(stream.size(), 2u);
+ EXPECT_EQ(stream.remaining(), 14u);
+
+ stream << buffer;
+
+ EXPECT(stream.handle_recoverable_error());
+ EXPECT_EQ(stream.size(), 2u);
+ EXPECT_EQ(stream.remaining(), 14u);
+
+ EXPECT_EQ(stream.bytes().data(), buffer.data());
+ EXPECT_EQ(stream.bytes().size(), 2u);
+}
+
+TEST_CASE(offset_of_out_of_bounds)
+{
+ Array<u8, 4> target { 0xff, 0xff, 0xff, 0xff };
+
+ Array<u8, DuplexMemoryStream::chunk_size> whole_chunk;
+ whole_chunk.span().fill(0);
+
+ DuplexMemoryStream stream;
+
+ stream << whole_chunk;
+
+ EXPECT(!stream.offset_of(target).has_value());
+}
+
+TEST_CASE(unsigned_integer_underflow_regression)
+{
+ Array<u8, DuplexMemoryStream::chunk_size + 1> buffer;
+
+ DuplexMemoryStream stream;
+ stream << buffer;
+}
+
+TEST_CASE(offset_calculation_error_regression)
+{
+ Array<u8, DuplexMemoryStream::chunk_size> input, output;
+ input.span().fill(0xff);
+
+ DuplexMemoryStream stream;
+ stream << 0x00000000 << input << 0x00000000;
+
+ stream.discard_or_error(sizeof(int));
+ stream.read(output);
+
+ EXPECT_EQ(input, output);
+}
diff --git a/Tests/AK/TestNeverDestroyed.cpp b/Tests/AK/TestNeverDestroyed.cpp
new file mode 100644
index 0000000000..7b72d6bae3
--- /dev/null
+++ b/Tests/AK/TestNeverDestroyed.cpp
@@ -0,0 +1,73 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/NeverDestroyed.h>
+#include <AK/StdLibExtras.h>
+
+struct Counter {
+ Counter() = default;
+
+ ~Counter() { ++num_destroys; }
+
+ Counter(const Counter&)
+ {
+ ++num_copies;
+ }
+
+ Counter(Counter&&) { ++num_moves; }
+
+ int num_copies {};
+ int num_moves {};
+ int num_destroys {};
+};
+
+TEST_CASE(should_construct_by_copy)
+{
+ Counter c {};
+ AK::NeverDestroyed<Counter> n { c };
+
+ EXPECT_EQ(1, n->num_copies);
+ EXPECT_EQ(0, n->num_moves);
+}
+
+TEST_CASE(should_construct_by_move)
+{
+ Counter c {};
+ AK::NeverDestroyed<Counter> n { move(c) };
+
+ EXPECT_EQ(0, n->num_copies);
+ EXPECT_EQ(1, n->num_moves);
+}
+
+TEST_CASE(should_not_destroy)
+{
+ Counter* c = nullptr;
+ {
+ AK::NeverDestroyed<Counter> n {};
+ c = &n.get();
+ }
+ EXPECT_EQ(0, c->num_destroys);
+}
+
+TEST_CASE(should_provide_dereference_operator)
+{
+ AK::NeverDestroyed<Counter> n {};
+ EXPECT_EQ(0, n->num_destroys);
+}
+
+TEST_CASE(should_provide_indirection_operator)
+{
+ AK::NeverDestroyed<Counter> n {};
+ EXPECT_EQ(0, (*n).num_destroys);
+}
+
+TEST_CASE(should_provide_basic_getter)
+{
+ AK::NeverDestroyed<Counter> n {};
+ EXPECT_EQ(0, n.get().num_destroys);
+}
diff --git a/Tests/AK/TestNonnullRefPtr.cpp b/Tests/AK/TestNonnullRefPtr.cpp
new file mode 100644
index 0000000000..c26adadacc
--- /dev/null
+++ b/Tests/AK/TestNonnullRefPtr.cpp
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/NonnullRefPtr.h>
+#include <AK/String.h>
+
+struct Object : public RefCounted<Object> {
+ int x;
+};
+
+TEST_CASE(basics)
+{
+ auto object = adopt_ref(*new Object);
+ EXPECT(object.ptr() != nullptr);
+ EXPECT_EQ(object->ref_count(), 1u);
+ object->ref();
+ EXPECT_EQ(object->ref_count(), 2u);
+ object->unref();
+ EXPECT_EQ(object->ref_count(), 1u);
+
+ {
+ NonnullRefPtr another = object;
+ EXPECT_EQ(object->ref_count(), 2u);
+ }
+
+ EXPECT_EQ(object->ref_count(), 1u);
+}
+
+TEST_CASE(assign_reference)
+{
+ auto object = adopt_ref(*new Object);
+ EXPECT_EQ(object->ref_count(), 1u);
+ object = *object;
+ EXPECT_EQ(object->ref_count(), 1u);
+}
+
+TEST_CASE(assign_owner_of_self)
+{
+ struct Object : public RefCounted<Object> {
+ RefPtr<Object> parent;
+ };
+
+ auto parent = adopt_ref(*new Object);
+ auto child = adopt_ref(*new Object);
+ child->parent = move(parent);
+
+ child = *child->parent;
+ EXPECT_EQ(child->ref_count(), 1u);
+}
+
+TEST_CASE(swap_with_self)
+{
+ auto object = adopt_ref(*new Object);
+ swap(object, object);
+ EXPECT_EQ(object->ref_count(), 1u);
+}
diff --git a/Tests/AK/TestNumberFormat.cpp b/Tests/AK/TestNumberFormat.cpp
new file mode 100644
index 0000000000..373d3bef98
--- /dev/null
+++ b/Tests/AK/TestNumberFormat.cpp
@@ -0,0 +1,127 @@
+/*
+ * Copyright (c) 2020, Ben Wiederhake <BenWiederhake.GitHub@gmx.de>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/NumberFormat.h>
+
+/*
+ * These tests are mostly meant as a rough sanity-check, to see whether
+ * human_readable_size() crashes or does something very silly. That, however,
+ * is a fuzzy human term, so these tests have to hard-code the exact expected
+ * strings.
+ *
+ * Please feel free to tweak human_readable_size()'s behavior, and update the
+ * "expected" strings below.
+ */
+
+TEST_CASE(golden_path)
+{
+ EXPECT_EQ(human_readable_size(0), "0 B");
+ EXPECT_EQ(human_readable_size(123), "123 B");
+ EXPECT_EQ(human_readable_size(123 * KiB), "123.0 KiB");
+ EXPECT_EQ(human_readable_size(123 * MiB), "123.0 MiB");
+ EXPECT_EQ(human_readable_size(2 * GiB), "2.0 GiB");
+}
+
+TEST_CASE(border_B_KiB)
+{
+ EXPECT_EQ(human_readable_size(1000), "1000 B");
+ EXPECT_EQ(human_readable_size(1023), "1023 B");
+ // KiB = 1024
+ EXPECT_EQ(human_readable_size(1024), "1.0 KiB");
+ EXPECT_EQ(human_readable_size(1025), "1.0 KiB");
+}
+
+TEST_CASE(fraction_KiB)
+{
+ EXPECT_EQ(human_readable_size(1050), "1.0 KiB");
+ EXPECT_EQ(human_readable_size(1075), "1.0 KiB");
+ // 1024 * 1.05 = 1075.2
+ EXPECT_EQ(human_readable_size(1076), "1.0 KiB");
+
+ EXPECT_EQ(human_readable_size(1100), "1.0 KiB");
+
+ EXPECT_EQ(human_readable_size(1126), "1.0 KiB");
+ // 1024 * 1.1 = 1126.4
+ EXPECT_EQ(human_readable_size(1127), "1.1 KiB");
+ EXPECT_EQ(human_readable_size(1146), "1.1 KiB");
+}
+
+TEST_CASE(border_KiB_MiB)
+{
+ EXPECT_EQ(human_readable_size(1000 * KiB), "1000.0 KiB");
+ EXPECT_EQ(human_readable_size(1024 * KiB - 1), "1023.9 KiB");
+ // MiB
+ EXPECT_EQ(human_readable_size(1024 * KiB), "1.0 MiB");
+ EXPECT_EQ(human_readable_size(1024 * KiB + 1), "1.0 MiB");
+}
+
+TEST_CASE(fraction_MiB)
+{
+ EXPECT_EQ(human_readable_size(1069547), "1.0 MiB");
+ EXPECT_EQ(human_readable_size(1101004), "1.0 MiB");
+ // 1024 * 1024 * 1.05 = 1101004.8
+ EXPECT_EQ(human_readable_size(1101005), "1.0 MiB");
+ EXPECT_EQ(human_readable_size(1101006), "1.0 MiB");
+
+ EXPECT_EQ(human_readable_size(1120000), "1.0 MiB");
+
+ EXPECT_EQ(human_readable_size(1153433), "1.0 MiB");
+ // 1024 * 1024 * 1.1 = 1153433.6
+ EXPECT_EQ(human_readable_size(1153434), "1.1 MiB");
+}
+
+TEST_CASE(border_MiB_GiB)
+{
+ EXPECT_EQ(human_readable_size(1000 * MiB), "1000.0 MiB");
+ EXPECT_EQ(human_readable_size(1024 * MiB - 1), "1023.9 MiB");
+ EXPECT_EQ(human_readable_size(1024 * MiB), "1.0 GiB");
+ EXPECT_EQ(human_readable_size(1024 * MiB + 1), "1.0 GiB");
+}
+
+TEST_CASE(fraction_GiB)
+{
+ EXPECT_EQ(human_readable_size(1095216660), "1.0 GiB");
+ EXPECT_EQ(human_readable_size(1127428915), "1.0 GiB");
+ // 1024 * 1024 * 1024 * 1.05 = 1127428915.2
+ EXPECT_EQ(human_readable_size(1127428916), "1.0 GiB");
+ EXPECT_EQ(human_readable_size(1127536289), "1.0 GiB");
+
+ EXPECT_EQ(human_readable_size(1154272461), "1.0 GiB");
+
+ EXPECT_EQ(human_readable_size(1181115968), "1.0 GiB");
+ EXPECT_EQ(human_readable_size(1181115969), "1.0 GiB");
+ EXPECT_EQ(human_readable_size(1181116000), "1.0 GiB");
+ EXPECT_EQ(human_readable_size(1181116006), "1.0 GiB");
+ // 1024 * 1024 * 1024 * 1.1 = 1181116006.4
+ EXPECT_EQ(human_readable_size(1181116007), "1.1 GiB");
+ EXPECT_EQ(human_readable_size(1202590842), "1.1 GiB");
+}
+
+TEST_CASE(extremes_4byte)
+{
+ EXPECT_EQ(human_readable_size(0x7fffffff), "1.9 GiB");
+ EXPECT_EQ(human_readable_size(0x80000000), "2.0 GiB");
+ EXPECT_EQ(human_readable_size(0xffffffff), "3.9 GiB");
+}
+
+TEST_CASE(extremes_8byte)
+{
+ if constexpr (sizeof(size_t) == 8) {
+ warnln("(Running 8-byte-size_t test)");
+ EXPECT_EQ(human_readable_size(0x100000000ULL), "4.0 GiB");
+ EXPECT_EQ(human_readable_size(0x100000001ULL), "4.0 GiB");
+ EXPECT_EQ(human_readable_size(0x800000000ULL), "32.0 GiB");
+ EXPECT_EQ(human_readable_size(0x10000000000ULL), "1.0 TiB");
+ EXPECT_EQ(human_readable_size(0x4000000000000ULL), "1.0 PiB");
+ EXPECT_EQ(human_readable_size(0x7fffffffffffffffULL), "7.9 EiB");
+ EXPECT_EQ(human_readable_size(0x8000000000000000ULL), "8.0 EiB");
+ EXPECT_EQ(human_readable_size(0xffffffffffffffffULL), "15.9 EiB");
+ } else {
+ warnln("(Skipping 8-byte-size_t test on 32-bit platform)");
+ }
+}
diff --git a/Tests/AK/TestOptional.cpp b/Tests/AK/TestOptional.cpp
new file mode 100644
index 0000000000..583d11f0eb
--- /dev/null
+++ b/Tests/AK/TestOptional.cpp
@@ -0,0 +1,55 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Optional.h>
+#include <AK/String.h>
+
+TEST_CASE(basic_optional)
+{
+ Optional<int> x;
+ EXPECT_EQ(x.has_value(), false);
+ x = 3;
+ EXPECT_EQ(x.has_value(), true);
+ EXPECT_EQ(x.value(), 3);
+}
+
+TEST_CASE(move_optional)
+{
+ Optional<int> x;
+ EXPECT_EQ(x.has_value(), false);
+ x = 3;
+ EXPECT_EQ(x.has_value(), true);
+ EXPECT_EQ(x.value(), 3);
+
+ Optional<int> y;
+ y = move(x);
+ EXPECT_EQ(y.has_value(), true);
+ EXPECT_EQ(y.value(), 3);
+ EXPECT_EQ(x.has_value(), false);
+}
+
+TEST_CASE(optional_leak_1)
+{
+ struct Structure {
+ Optional<String> str;
+ };
+
+ // This used to leak, it does not anymore.
+ Vector<Structure> vec;
+ vec.append({ "foo" });
+ EXPECT_EQ(vec[0].str.has_value(), true);
+ EXPECT_EQ(vec[0].str.value(), "foo");
+}
+
+TEST_CASE(short_notation)
+{
+ Optional<StringView> value = "foo";
+
+ EXPECT_EQ(value->length(), 3u);
+ EXPECT_EQ(*value, "foo");
+}
diff --git a/Tests/AK/TestQueue.cpp b/Tests/AK/TestQueue.cpp
new file mode 100644
index 0000000000..6e11e6e685
--- /dev/null
+++ b/Tests/AK/TestQueue.cpp
@@ -0,0 +1,59 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Queue.h>
+#include <AK/String.h>
+
+TEST_CASE(construct)
+{
+ EXPECT(Queue<int>().is_empty());
+ EXPECT(Queue<int>().size() == 0);
+}
+
+TEST_CASE(populate_int)
+{
+ Queue<int> ints;
+ ints.enqueue(1);
+ ints.enqueue(2);
+ ints.enqueue(3);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(ints.dequeue(), 1);
+ EXPECT_EQ(ints.size(), 2u);
+ EXPECT_EQ(ints.dequeue(), 2);
+ EXPECT_EQ(ints.size(), 1u);
+ EXPECT_EQ(ints.dequeue(), 3);
+ EXPECT_EQ(ints.size(), 0u);
+}
+
+TEST_CASE(populate_string)
+{
+ Queue<String> strings;
+ strings.enqueue("ABC");
+ strings.enqueue("DEF");
+ EXPECT_EQ(strings.size(), 2u);
+ EXPECT_EQ(strings.dequeue(), "ABC");
+ EXPECT_EQ(strings.dequeue(), "DEF");
+ EXPECT(strings.is_empty());
+}
+
+TEST_CASE(order)
+{
+ Queue<String> strings;
+ EXPECT(strings.is_empty());
+
+ for (size_t i = 0; i < 10000; ++i) {
+ strings.enqueue(String::number(i));
+ EXPECT_EQ(strings.size(), i + 1);
+ }
+
+ for (int i = 0; i < 10000; ++i) {
+ EXPECT_EQ(strings.dequeue().to_int().value(), i);
+ }
+
+ EXPECT(strings.is_empty());
+}
diff --git a/Tests/AK/TestQuickSort.cpp b/Tests/AK/TestQuickSort.cpp
new file mode 100644
index 0000000000..23fc7692dc
--- /dev/null
+++ b/Tests/AK/TestQuickSort.cpp
@@ -0,0 +1,100 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Checked.h>
+#include <AK/Noncopyable.h>
+#include <AK/QuickSort.h>
+#include <AK/StdLibExtras.h>
+
+TEST_CASE(sorts_without_copy)
+{
+ struct NoCopy {
+ AK_MAKE_NONCOPYABLE(NoCopy);
+
+ public:
+ NoCopy() = default;
+ NoCopy(NoCopy&&) = default;
+
+ NoCopy& operator=(NoCopy&&) = default;
+
+ int value { 0 };
+ };
+
+ Array<NoCopy, 64> array;
+
+ // Test the dual pivot quick sort.
+ for (size_t i = 0; i < 64; ++i)
+ array[i].value = (64 - i) % 32 + 32;
+
+ dual_pivot_quick_sort(array, 0, array.size() - 1, [](auto& a, auto& b) { return a.value < b.value; });
+
+ for (size_t i = 0; i < 63; ++i)
+ EXPECT(array[i].value <= array[i + 1].value);
+
+ // Test the single pivot quick sort.
+ for (size_t i = 0; i < 64; ++i)
+ array[i].value = (64 - i) % 32 + 32;
+
+ AK::single_pivot_quick_sort(array.begin(), array.end(), [](auto& a, auto& b) { return a.value < b.value; });
+
+ for (size_t i = 0; i < 63; ++i)
+ EXPECT(array[i].value <= array[i + 1].value);
+}
+
+// This test case may fail to construct a worst-case input if the pivot choice
+// of the underlying quick_sort no longer matches the one used here.
+// So it provides no strong guarantees about the properties of quick_sort.
+TEST_CASE(maximum_stack_depth)
+{
+ const int size = 256;
+ int* data = new int[size];
+
+ for (int i = 0; i < size; i++) {
+ data[i] = i;
+ }
+
+ // Construct the data in such a way that the assumed pivot choice
+ // of (size / 2) causes the partitions to be of worst case size.
+ for (int i = 0; i < size / 2; i++) {
+ swap(data[i], data[i + (size - i) / 2]);
+ }
+
+ // Measure the depth of the call stack through the less_than argument
+ // of quick_sort as it gets copied for each recursive call.
+ struct DepthMeasurer {
+ int& max_depth;
+ int depth { 0 };
+ DepthMeasurer(int& max_depth)
+ : max_depth(max_depth)
+ {
+ }
+ DepthMeasurer(const DepthMeasurer& obj)
+ : max_depth(obj.max_depth)
+ {
+ depth = obj.depth + 1;
+ if (depth > max_depth) {
+ max_depth = depth;
+ }
+ }
+ bool operator()(int& a, int& b)
+ {
+ return a < b;
+ }
+ };
+
+ int max_depth = 0;
+ DepthMeasurer measurer(max_depth);
+ AK::single_pivot_quick_sort(data, data + size, measurer);
+
+ EXPECT(max_depth <= 64);
+
+ for (int i = 0; i < size; i++)
+ EXPECT(data[i] == i);
+
+ delete[] data;
+}
diff --git a/Tests/AK/TestRedBlackTree.cpp b/Tests/AK/TestRedBlackTree.cpp
new file mode 100644
index 0000000000..51f9549957
--- /dev/null
+++ b/Tests/AK/TestRedBlackTree.cpp
@@ -0,0 +1,88 @@
+/*
+ * Copyright (c) 2021, Idan Horowitz <idan.horowitz@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Random.h>
+#include <AK/RedBlackTree.h>
+
+TEST_CASE(construct)
+{
+ RedBlackTree<int, int> empty;
+ EXPECT(empty.is_empty());
+ EXPECT(empty.size() == 0);
+}
+
+TEST_CASE(ints)
+{
+ RedBlackTree<int, int> ints;
+ ints.insert(1, 10);
+ ints.insert(3, 20);
+ ints.insert(2, 30);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(*ints.find(3), 20);
+ EXPECT_EQ(*ints.find(2), 30);
+ EXPECT_EQ(*ints.find(1), 10);
+ EXPECT(!ints.remove(4));
+ EXPECT(ints.remove(2));
+ EXPECT(ints.remove(1));
+ EXPECT(ints.remove(3));
+ EXPECT_EQ(ints.size(), 0u);
+}
+
+TEST_CASE(largest_smaller_than)
+{
+ RedBlackTree<int, int> ints;
+ ints.insert(1, 10);
+ ints.insert(11, 20);
+ ints.insert(21, 30);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(*ints.find_largest_not_above(3), 10);
+ EXPECT_EQ(*ints.find_largest_not_above(17), 20);
+ EXPECT_EQ(*ints.find_largest_not_above(22), 30);
+ EXPECT_EQ(ints.find_largest_not_above(-5), nullptr);
+}
+
+TEST_CASE(key_ordered_iteration)
+{
+ constexpr auto amount = 10000;
+ RedBlackTree<int, size_t> test;
+ Array<int, amount> keys {};
+
+ // generate random key order
+ for (int i = 0; i < amount; i++) {
+ keys[i] = i;
+ }
+ for (size_t i = 0; i < amount; i++) {
+ swap(keys[i], keys[get_random<size_t>() % amount]);
+ }
+
+ // insert random keys
+ for (size_t i = 0; i < amount; i++) {
+ test.insert(keys[i], keys[i]);
+ }
+
+ // check key-ordered iteration
+ size_t index = 0;
+ for (auto& value : test) {
+ EXPECT(value == index++);
+ }
+
+ // ensure we can remove all of them (aka, tree structure is not destroyed somehow)
+ for (size_t i = 0; i < amount; i++) {
+ EXPECT(test.remove(i));
+ }
+}
+
+TEST_CASE(clear)
+{
+ RedBlackTree<size_t, size_t> test;
+ for (size_t i = 0; i < 1000; i++) {
+ test.insert(i, i);
+ }
+ test.clear();
+ EXPECT_EQ(test.size(), 0u);
+}
diff --git a/Tests/AK/TestRefPtr.cpp b/Tests/AK/TestRefPtr.cpp
new file mode 100644
index 0000000000..8c85ace774
--- /dev/null
+++ b/Tests/AK/TestRefPtr.cpp
@@ -0,0 +1,149 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/NonnullRefPtr.h>
+#include <AK/String.h>
+
+struct Object : public RefCounted<Object> {
+ int x;
+};
+
+struct Object2 : Object {
+};
+
+struct SelfAwareObject : public RefCounted<SelfAwareObject> {
+ void one_ref_left() { m_has_one_ref_left = true; }
+ void will_be_destroyed() { ++num_destroyed; }
+
+ bool m_has_one_ref_left = false;
+ static size_t num_destroyed;
+};
+size_t SelfAwareObject::num_destroyed = 0;
+
+TEST_CASE(basics)
+{
+ RefPtr<Object> object = adopt_ref(*new Object);
+ EXPECT(object.ptr() != nullptr);
+ EXPECT_EQ(object->ref_count(), 1u);
+ object->ref();
+ EXPECT_EQ(object->ref_count(), 2u);
+ object->unref();
+ EXPECT_EQ(object->ref_count(), 1u);
+
+ {
+ NonnullRefPtr another = *object;
+ EXPECT_EQ(object->ref_count(), 2u);
+ }
+
+ EXPECT_EQ(object->ref_count(), 1u);
+}
+
+TEST_CASE(assign_reference)
+{
+ RefPtr<Object> object = adopt_ref(*new Object);
+ EXPECT_EQ(object->ref_count(), 1u);
+ object = *object;
+ EXPECT_EQ(object->ref_count(), 1u);
+}
+
+TEST_CASE(assign_ptr)
+{
+ RefPtr<Object> object = adopt_ref(*new Object);
+ EXPECT_EQ(object->ref_count(), 1u);
+ object = object.ptr();
+ EXPECT_EQ(object->ref_count(), 1u);
+}
+
+TEST_CASE(copy_move_ref)
+{
+ RefPtr<Object2> object = adopt_ref(*new Object2);
+ EXPECT_EQ(object->ref_count(), 1u);
+ {
+ auto object2 = object;
+ EXPECT_EQ(object->ref_count(), 2u);
+
+ RefPtr<Object> object1 = object;
+ EXPECT_EQ(object->ref_count(), 3u);
+
+ object1 = move(object2);
+ EXPECT_EQ(object->ref_count(), 2u);
+
+ RefPtr<Object> object3(move(object1));
+ EXPECT_EQ(object3->ref_count(), 2u);
+
+ object1 = object3;
+ EXPECT_EQ(object3->ref_count(), 3u);
+ }
+ EXPECT_EQ(object->ref_count(), 1u);
+}
+
+TEST_CASE(swap)
+{
+ RefPtr<Object> object_a = adopt_ref(*new Object);
+ RefPtr<Object> object_b = adopt_ref(*new Object);
+ auto* ptr_a = object_a.ptr();
+ auto* ptr_b = object_b.ptr();
+ swap(object_a, object_b);
+ EXPECT_EQ(object_a, ptr_b);
+ EXPECT_EQ(object_b, ptr_a);
+ EXPECT_EQ(object_a->ref_count(), 1u);
+ EXPECT_EQ(object_b->ref_count(), 1u);
+}
+
+TEST_CASE(assign_moved_self)
+{
+ RefPtr<Object> object = adopt_ref(*new Object);
+ EXPECT_EQ(object->ref_count(), 1u);
+#ifdef __clang__
+# pragma clang diagnostic push
+# pragma clang diagnostic ignored "-Wself-move"
+#endif
+ object = move(object);
+#ifdef __clang__
+# pragma clang diagnostic pop
+#endif
+ EXPECT_EQ(object->ref_count(), 1u);
+}
+
+TEST_CASE(assign_copy_self)
+{
+ RefPtr<Object> object = adopt_ref(*new Object);
+ EXPECT_EQ(object->ref_count(), 1u);
+
+#ifdef __clang__
+# pragma clang diagnostic push
+# pragma clang diagnostic ignored "-Wself-assign-overloaded"
+#endif
+ object = object;
+#ifdef __clang__
+# pragma clang diagnostic pop
+#endif
+
+ EXPECT_EQ(object->ref_count(), 1u);
+}
+
+TEST_CASE(self_observers)
+{
+ RefPtr<SelfAwareObject> object = adopt_ref(*new SelfAwareObject);
+ EXPECT_EQ(object->ref_count(), 1u);
+ EXPECT_EQ(object->m_has_one_ref_left, false);
+ EXPECT_EQ(SelfAwareObject::num_destroyed, 0u);
+
+ object->ref();
+ EXPECT_EQ(object->ref_count(), 2u);
+ EXPECT_EQ(object->m_has_one_ref_left, false);
+ EXPECT_EQ(SelfAwareObject::num_destroyed, 0u);
+
+ object->unref();
+ EXPECT_EQ(object->ref_count(), 1u);
+ EXPECT_EQ(object->m_has_one_ref_left, true);
+ EXPECT_EQ(SelfAwareObject::num_destroyed, 0u);
+
+ object->unref();
+ EXPECT_EQ(SelfAwareObject::num_destroyed, 1u);
+}
diff --git a/Tests/AK/TestSinglyLinkedList.cpp b/Tests/AK/TestSinglyLinkedList.cpp
new file mode 100644
index 0000000000..3df43d2cb5
--- /dev/null
+++ b/Tests/AK/TestSinglyLinkedList.cpp
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/SinglyLinkedList.h>
+
+static SinglyLinkedList<int> make_list()
+{
+ SinglyLinkedList<int> list {};
+ list.append(0);
+ list.append(1);
+ list.append(2);
+ list.append(3);
+ list.append(4);
+ list.append(5);
+ list.append(6);
+ list.append(7);
+ list.append(8);
+ list.append(9);
+ return list;
+}
+
+TEST_CASE(should_find_mutable)
+{
+ auto sut = make_list();
+
+ EXPECT_EQ(4, *sut.find(4));
+
+ EXPECT_EQ(sut.end(), sut.find(42));
+}
+
+TEST_CASE(should_find_mutable_with_predicate)
+{
+ auto sut = make_list();
+
+ EXPECT_EQ(4, *sut.find_if([](const auto v) { return v == 4; }));
+
+ EXPECT_EQ(sut.end(), sut.find_if([](const auto v) { return v == 42; }));
+}
+
+TEST_CASE(should_find_const)
+{
+ const auto sut = make_list();
+
+ EXPECT_EQ(4, *sut.find(4));
+
+ EXPECT_EQ(sut.end(), sut.find(42));
+}
+
+TEST_CASE(should_find_const_with_predicate)
+{
+ const auto sut = make_list();
+
+ EXPECT_EQ(4, *sut.find_if([](const auto v) { return v == 4; }));
+
+ EXPECT_EQ(sut.end(), sut.find_if([](const auto v) { return v == 42; }));
+}
diff --git a/Tests/AK/TestSourceGenerator.cpp b/Tests/AK/TestSourceGenerator.cpp
new file mode 100644
index 0000000000..9b8a3b7b6c
--- /dev/null
+++ b/Tests/AK/TestSourceGenerator.cpp
@@ -0,0 +1,71 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/SourceGenerator.h>
+
+TEST_CASE(wrap_builder)
+{
+ StringBuilder builder;
+ SourceGenerator generator { builder };
+
+ generator.append("Hello, World!");
+
+ EXPECT_EQ(builder.string_view(), "Hello, World!");
+}
+
+TEST_CASE(generate_c_code)
+{
+ StringBuilder builder;
+ SourceGenerator generator { builder };
+ generator.set("name", "foo");
+
+ generator.append("const char* @name@ (void) { return \"@name@\"; }");
+
+ EXPECT_EQ(generator.as_string_view(), "const char* foo (void) { return \"foo\"; }");
+}
+
+TEST_CASE(scoped)
+{
+ StringBuilder builder;
+ SourceGenerator global_generator { builder };
+
+ global_generator.append("\n");
+
+ global_generator.set("foo", "foo-0");
+ global_generator.set("bar", "bar-0");
+ global_generator.append("@foo@ @bar@\n"); // foo-0 bar-0
+
+ {
+ auto scoped_generator_1 = global_generator.fork();
+ scoped_generator_1.set("bar", "bar-1");
+ global_generator.append("@foo@ @bar@\n"); // foo-0 bar-0
+ }
+
+ global_generator.append("@foo@ @bar@\n"); // foo-0 bar-0
+
+ {
+ auto scoped_generator_2 = global_generator.fork();
+ scoped_generator_2.set("foo", "foo-2");
+ scoped_generator_2.append("@foo@ @bar@\n"); // foo-2 bar-0
+
+ {
+ auto scoped_generator_3 = scoped_generator_2.fork();
+ scoped_generator_3.set("bar", "bar-3");
+ scoped_generator_3.append("@foo@ @bar@\n"); // foo-2 bar-3
+ }
+
+ {
+ auto scoped_generator_4 = global_generator.fork();
+ scoped_generator_4.append("@foo@ @bar@\n"); // foo-0 bar-0
+ }
+
+ scoped_generator_2.append("@foo@ @bar@\n"); // foo-2 bar-0
+ }
+
+ EXPECT_EQ(global_generator.as_string_view(), "\nfoo-0 bar-0\nfoo-0 bar-0\nfoo-0 bar-0\nfoo-2 bar-0\nfoo-2 bar-3\nfoo-0 bar-0\nfoo-2 bar-0\n");
+}
diff --git a/Tests/AK/TestSourceLocation.cpp b/Tests/AK/TestSourceLocation.cpp
new file mode 100644
index 0000000000..d770751d1d
--- /dev/null
+++ b/Tests/AK/TestSourceLocation.cpp
@@ -0,0 +1,32 @@
+/*
+ * Copyright (c) 2021, Andrew Kaster <andrewdkaster@gmail.com>
+ * Copyright (c) 2021, Brian Gianforcaro <bgianf@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/SourceLocation.h>
+#include <AK/StringView.h>
+
+TEST_CASE(basic_scenario)
+{
+ auto location = SourceLocation::current();
+ EXPECT_EQ(StringView(__FILE__), location.filename());
+ EXPECT_EQ(StringView(__FUNCTION__), location.function_name());
+ EXPECT_EQ(__LINE__ - 3u, location.line_number());
+}
+
+static StringView test_default_arg(const SourceLocation& loc = SourceLocation::current())
+{
+ return loc.function_name();
+}
+
+TEST_CASE(default_arg_scenario)
+{
+ auto actual_calling_function = test_default_arg();
+ auto expected_calling_function = StringView(__FUNCTION__);
+
+ EXPECT_EQ(expected_calling_function, actual_calling_function);
+}
diff --git a/Tests/AK/TestSpan.cpp b/Tests/AK/TestSpan.cpp
new file mode 100644
index 0000000000..2668133c4e
--- /dev/null
+++ b/Tests/AK/TestSpan.cpp
@@ -0,0 +1,125 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Checked.h>
+#include <AK/Span.h>
+#include <AK/StdLibExtras.h>
+#include <string.h>
+
+TEST_CASE(constexpr_default_constructor_is_empty)
+{
+ constexpr Span<int> span;
+ static_assert(span.is_empty(), "Default constructed span should be empty.");
+}
+
+TEST_CASE(implicit_converson_to_const)
+{
+ constexpr Bytes bytes0;
+ [[maybe_unused]] constexpr ReadonlyBytes bytes2 = bytes0;
+ [[maybe_unused]] constexpr ReadonlyBytes bytes3 = static_cast<ReadonlyBytes>(bytes2);
+}
+
+TEST_CASE(span_works_with_constant_types)
+{
+ static constexpr u8 buffer[4] { 1, 2, 3, 4 };
+ constexpr ReadonlyBytes bytes { buffer, 4 };
+
+ static_assert(IsConst<RemoveReference<decltype(bytes[1])>>);
+ static_assert(bytes[2] == 3);
+}
+
+TEST_CASE(span_works_with_mutable_types)
+{
+ u8 buffer[4] { 1, 2, 3, 4 };
+ Bytes bytes { buffer, 4 };
+
+ EXPECT_EQ(bytes[2], 3);
+ ++bytes[2];
+ EXPECT_EQ(bytes[2], 4);
+}
+
+TEST_CASE(iterator_behaves_like_loop)
+{
+ u8 buffer[256];
+ for (int idx = 0; idx < 256; ++idx) {
+ buffer[idx] = static_cast<u8>(idx);
+ }
+
+ Bytes bytes { buffer, 256 };
+ size_t idx = 0;
+ for (auto iter = bytes.begin(); iter < bytes.end(); ++iter) {
+ EXPECT_EQ(*iter, buffer[idx]);
+
+ ++idx;
+ }
+}
+
+TEST_CASE(modifying_is_possible)
+{
+ int values_before[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
+ int values_after[8] = { 7, 6, 5, 4, 3, 2, 1, 0 };
+
+ Span<int> span { values_before, 8 };
+ for (auto& value : span) {
+ value = 8 - value;
+ }
+
+ for (int idx = 0; idx < 8; ++idx) {
+ EXPECT_EQ(values_before[idx], values_after[idx]);
+ }
+}
+
+TEST_CASE(at_and_index_operator_return_same_value)
+{
+ u8 buffer[256];
+ for (int idx = 0; idx < 256; ++idx) {
+ buffer[idx] = static_cast<u8>(idx);
+ }
+
+ Bytes bytes { buffer, 256 };
+ for (int idx = 0; idx < 256; ++idx) {
+ EXPECT_EQ(buffer[idx], bytes[idx]);
+ EXPECT_EQ(bytes[idx], bytes.at(idx));
+ }
+}
+
+TEST_CASE(can_subspan_whole_span)
+{
+ static constexpr u8 buffer[16] {};
+ constexpr ReadonlyBytes bytes { buffer, 16 };
+
+ constexpr auto slice = bytes.slice(0, 16);
+
+ static_assert(slice.data() == buffer);
+ static_assert(slice.size() == 16u);
+}
+
+TEST_CASE(can_subspan_as_intended)
+{
+ static constexpr u16 buffer[8] { 1, 2, 3, 4, 5, 6, 7, 8 };
+
+ constexpr Span<const u16> span { buffer, 8 };
+ constexpr auto slice = span.slice(3, 2);
+
+ static_assert(slice.size() == 2u);
+ static_assert(slice[0] == 4);
+ static_assert(slice[1] == 5);
+}
+
+TEST_CASE(span_from_void_pointer)
+{
+ int value = 0;
+ [[maybe_unused]] Bytes bytes0 { reinterpret_cast<void*>(value), 4 };
+ [[maybe_unused]] ReadonlyBytes bytes1 { reinterpret_cast<const void*>(value), 4 };
+}
+
+TEST_CASE(span_from_c_string)
+{
+ const char* str = "Serenity";
+ [[maybe_unused]] ReadonlyBytes bytes { str, strlen(str) };
+}
diff --git a/Tests/AK/TestString.cpp b/Tests/AK/TestString.cpp
new file mode 100644
index 0000000000..b61828199e
--- /dev/null
+++ b/Tests/AK/TestString.cpp
@@ -0,0 +1,237 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/FlyString.h>
+#include <AK/String.h>
+#include <AK/StringBuilder.h>
+#include <cstring>
+
+TEST_CASE(construct_empty)
+{
+ EXPECT(String().is_null());
+ EXPECT(String().is_empty());
+ EXPECT(!String().characters());
+
+ EXPECT(!String("").is_null());
+ EXPECT(String("").is_empty());
+ EXPECT(String("").characters() != nullptr);
+
+ EXPECT(String("").impl() == String::empty().impl());
+}
+
+TEST_CASE(construct_contents)
+{
+ String test_string = "ABCDEF";
+ EXPECT(!test_string.is_empty());
+ EXPECT(!test_string.is_null());
+ EXPECT_EQ(test_string.length(), 6u);
+ EXPECT_EQ(test_string.length(), strlen(test_string.characters()));
+ EXPECT(test_string.characters() != nullptr);
+ EXPECT(!strcmp(test_string.characters(), "ABCDEF"));
+
+ EXPECT(test_string == "ABCDEF");
+ EXPECT(test_string != "ABCDE");
+ EXPECT(test_string != "ABCDEFG");
+}
+
+TEST_CASE(compare)
+{
+ String test_string = "ABCDEF";
+ EXPECT("a" < String("b"));
+ EXPECT(!("a" > String("b")));
+ EXPECT("b" > String("a"));
+ EXPECT(!("b" < String("b")));
+ EXPECT("a" >= String("a"));
+ EXPECT(!("a" >= String("b")));
+ EXPECT("a" <= String("a"));
+ EXPECT(!("b" <= String("a")));
+}
+
+TEST_CASE(index_access)
+{
+ String test_string = "ABCDEF";
+ EXPECT_EQ(test_string[0], 'A');
+ EXPECT_EQ(test_string[1], 'B');
+}
+
+TEST_CASE(starts_with)
+{
+ String test_string = "ABCDEF";
+ EXPECT(test_string.starts_with("AB"));
+ EXPECT(test_string.starts_with('A'));
+ EXPECT(!test_string.starts_with('B'));
+ EXPECT(test_string.starts_with("ABCDEF"));
+ EXPECT(!test_string.starts_with("DEF"));
+ EXPECT(test_string.starts_with("abc", CaseSensitivity::CaseInsensitive));
+ EXPECT(!test_string.starts_with("abc", CaseSensitivity::CaseSensitive));
+}
+
+TEST_CASE(ends_with)
+{
+ String test_string = "ABCDEF";
+ EXPECT(test_string.ends_with("EF"));
+ EXPECT(test_string.ends_with('F'));
+ EXPECT(!test_string.ends_with('E'));
+ EXPECT(test_string.ends_with("ABCDEF"));
+ EXPECT(!test_string.ends_with("ABC"));
+ EXPECT(test_string.ends_with("def", CaseSensitivity::CaseInsensitive));
+ EXPECT(!test_string.ends_with("def", CaseSensitivity::CaseSensitive));
+}
+
+TEST_CASE(copy_string)
+{
+ String test_string = "ABCDEF";
+ auto test_string_copy = test_string;
+ EXPECT_EQ(test_string, test_string_copy);
+ EXPECT_EQ(test_string.characters(), test_string_copy.characters());
+}
+
+TEST_CASE(move_string)
+{
+ String test_string = "ABCDEF";
+ auto test_string_copy = test_string;
+ auto test_string_move = move(test_string_copy);
+ EXPECT_EQ(test_string, test_string_move);
+ EXPECT(test_string_copy.is_null());
+}
+
+TEST_CASE(repeated)
+{
+ EXPECT_EQ(String::repeated('x', 0), "");
+ EXPECT_EQ(String::repeated('x', 1), "x");
+ EXPECT_EQ(String::repeated('x', 2), "xx");
+}
+
+TEST_CASE(to_int)
+{
+ EXPECT_EQ(String("123").to_int().value(), 123);
+ EXPECT_EQ(String("-123").to_int().value(), -123);
+}
+
+TEST_CASE(to_lowercase)
+{
+ EXPECT(String("ABC").to_lowercase() == "abc");
+}
+
+TEST_CASE(to_uppercase)
+{
+ EXPECT(String("AbC").to_uppercase() == "ABC");
+}
+
+TEST_CASE(flystring)
+{
+ {
+ FlyString a("foo");
+ FlyString b("foo");
+ EXPECT_EQ(a.impl(), b.impl());
+ }
+
+ {
+ String a = "foo";
+ FlyString b = a;
+ StringBuilder builder;
+ builder.append('f');
+ builder.append("oo");
+ FlyString c = builder.to_string();
+ EXPECT_EQ(a.impl(), b.impl());
+ EXPECT_EQ(a.impl(), c.impl());
+ }
+}
+
+TEST_CASE(replace)
+{
+ String test_string = "Well, hello Friends!";
+ u32 replacements = test_string.replace("Friends", "Testers");
+ EXPECT(replacements == 1);
+ EXPECT(test_string == "Well, hello Testers!");
+
+ replacements = test_string.replace("ell", "e're", true);
+ EXPECT(replacements == 2);
+ EXPECT(test_string == "We're, he'reo Testers!");
+
+ replacements = test_string.replace("!", " :^)");
+ EXPECT(replacements == 1);
+ EXPECT(test_string == "We're, he'reo Testers :^)");
+
+ test_string = String("111._.111._.111");
+ replacements = test_string.replace("111", "|||", true);
+ EXPECT(replacements == 3);
+ EXPECT(test_string == "|||._.|||._.|||");
+
+ replacements = test_string.replace("|||", "111");
+ EXPECT(replacements == 1);
+ EXPECT(test_string == "111._.|||._.|||");
+}
+
+TEST_CASE(substring)
+{
+ String test = "abcdef";
+ EXPECT_EQ(test.substring(0, 6), test);
+ EXPECT_EQ(test.substring(0, 3), "abc");
+ EXPECT_EQ(test.substring(3, 3), "def");
+ EXPECT_EQ(test.substring(3, 0), "");
+ EXPECT_EQ(test.substring(6, 0), "");
+}
+
+TEST_CASE(split)
+{
+ String test = "foo bar baz";
+ auto parts = test.split(' ');
+ EXPECT_EQ(parts.size(), 3u);
+ EXPECT_EQ(parts[0], "foo");
+ EXPECT_EQ(parts[1], "bar");
+ EXPECT_EQ(parts[2], "baz");
+
+ EXPECT_EQ(parts[0].characters()[3], '\0');
+ EXPECT_EQ(parts[1].characters()[3], '\0');
+ EXPECT_EQ(parts[2].characters()[3], '\0');
+
+ test = "a b";
+
+ parts = test.split(' ');
+ EXPECT_EQ(parts.size(), 2u);
+ EXPECT_EQ(parts[0], "a");
+ EXPECT_EQ(parts[1], "b");
+
+ parts = test.split(' ', true);
+ EXPECT_EQ(parts.size(), 5u);
+ EXPECT_EQ(parts[0], "a");
+ EXPECT_EQ(parts[1], "");
+ EXPECT_EQ(parts[2], "");
+ EXPECT_EQ(parts[3], "");
+ EXPECT_EQ(parts[4], "b");
+
+ test = "axxbx";
+ EXPECT_EQ(test.split('x').size(), 2u);
+ EXPECT_EQ(test.split('x', true).size(), 4u);
+ EXPECT_EQ(test.split_view('x').size(), 2u);
+ EXPECT_EQ(test.split_view('x', true).size(), 4u);
+}
+
+TEST_CASE(builder_zero_initial_capacity)
+{
+ StringBuilder builder(0);
+ builder.append("");
+ auto built = builder.build();
+ EXPECT_EQ(built.is_null(), false);
+ EXPECT_EQ(built.length(), 0u);
+}
+
+TEST_CASE(sprintf)
+{
+ char buf1[128];
+ int ret1 = sprintf(buf1, "%+d", 12);
+ EXPECT_EQ(ret1, 3);
+
+ char buf2[128];
+ int ret2 = sprintf(buf2, "%+d", -12);
+ EXPECT_EQ(ret2, 3);
+
+ EXPECT_EQ(String(buf1), String("+12"));
+ EXPECT_EQ(String(buf2), String("-12"));
+}
diff --git a/Tests/AK/TestStringUtils.cpp b/Tests/AK/TestStringUtils.cpp
new file mode 100644
index 0000000000..315c14f1da
--- /dev/null
+++ b/Tests/AK/TestStringUtils.cpp
@@ -0,0 +1,306 @@
+/*
+ * Copyright (c) 2020, Fei Wu <f.eiwu@yahoo.com>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/StringUtils.h>
+
+TEST_CASE(matches_null)
+{
+ EXPECT(AK::StringUtils::matches(StringView(), StringView()));
+
+ EXPECT(!AK::StringUtils::matches(StringView(), ""));
+ EXPECT(!AK::StringUtils::matches(StringView(), "*"));
+ EXPECT(!AK::StringUtils::matches(StringView(), "?"));
+ EXPECT(!AK::StringUtils::matches(StringView(), "a"));
+
+ EXPECT(!AK::StringUtils::matches("", StringView()));
+ EXPECT(!AK::StringUtils::matches("a", StringView()));
+}
+
+TEST_CASE(matches_empty)
+{
+ EXPECT(AK::StringUtils::matches("", ""));
+
+ EXPECT(AK::StringUtils::matches("", "*"));
+ EXPECT(!AK::StringUtils::matches("", "?"));
+ EXPECT(!AK::StringUtils::matches("", "a"));
+
+ EXPECT(!AK::StringUtils::matches("a", ""));
+}
+
+TEST_CASE(matches_case_sensitive)
+{
+ EXPECT(AK::StringUtils::matches("a", "a", CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::matches("a", "A", CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::matches("A", "a", CaseSensitivity::CaseSensitive));
+}
+
+TEST_CASE(matches_case_insensitive)
+{
+ EXPECT(!AK::StringUtils::matches("aa", "a"));
+ EXPECT(AK::StringUtils::matches("aa", "*"));
+ EXPECT(!AK::StringUtils::matches("cb", "?a"));
+ EXPECT(AK::StringUtils::matches("adceb", "a*b"));
+ EXPECT(!AK::StringUtils::matches("acdcb", "a*c?b"));
+}
+
+TEST_CASE(matches_with_positions)
+{
+ Vector<AK::MaskSpan> spans;
+ EXPECT(AK::StringUtils::matches("abbb", "a*", CaseSensitivity::CaseSensitive, &spans));
+ EXPECT(spans == Vector<AK::MaskSpan>({ { 1, 3 } }));
+
+ spans.clear();
+ EXPECT(AK::StringUtils::matches("abbb", "?*", CaseSensitivity::CaseSensitive, &spans));
+ EXPECT_EQ(spans, Vector<AK::MaskSpan>({ { 0, 1 }, { 1, 3 } }));
+
+ spans.clear();
+ EXPECT(AK::StringUtils::matches("acdcxb", "a*c?b", CaseSensitivity::CaseSensitive, &spans));
+ EXPECT_EQ(spans, Vector<AK::MaskSpan>({ { 1, 2 }, { 4, 1 } }));
+
+ spans.clear();
+ EXPECT(AK::StringUtils::matches("aaaa", "A*", CaseSensitivity::CaseInsensitive, &spans));
+ EXPECT_EQ(spans, Vector<AK::MaskSpan>({ { 1, 3 } }));
+}
+
+// #4607
+TEST_CASE(matches_trailing)
+{
+ EXPECT(AK::StringUtils::matches("ab", "ab*"));
+ EXPECT(AK::StringUtils::matches("ab", "ab****"));
+ EXPECT(AK::StringUtils::matches("ab", "*ab****"));
+}
+
+TEST_CASE(convert_to_int)
+{
+ auto value = AK::StringUtils::convert_to_int(StringView());
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_int("");
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_int("a");
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_int("+");
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_int("-");
+ EXPECT(!value.has_value());
+
+ auto actual = AK::StringUtils::convert_to_int("0");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 0);
+
+ actual = AK::StringUtils::convert_to_int("1");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 1);
+
+ actual = AK::StringUtils::convert_to_int("+1");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 1);
+
+ actual = AK::StringUtils::convert_to_int("-1");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), -1);
+
+ actual = AK::StringUtils::convert_to_int("01");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 1);
+
+ actual = AK::StringUtils::convert_to_int("12345");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 12345);
+
+ actual = AK::StringUtils::convert_to_int("-12345");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), -12345);
+
+ actual = AK::StringUtils::convert_to_int(" \t-12345 \n\n");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), -12345);
+
+ auto actual_i8 = AK::StringUtils::convert_to_int<i8>("-1");
+ EXPECT(actual_i8.has_value());
+ EXPECT_EQ(actual_i8.value(), -1);
+ EXPECT_EQ(sizeof(actual_i8.value()), (size_t)1);
+ actual_i8 = AK::StringUtils::convert_to_int<i8>("128");
+ EXPECT(!actual_i8.has_value());
+
+ auto actual_i16 = AK::StringUtils::convert_to_int<i16>("-1");
+ EXPECT(actual_i16.has_value());
+ EXPECT_EQ(actual_i16.value(), -1);
+ EXPECT_EQ(sizeof(actual_i16.value()), (size_t)2);
+ actual_i16 = AK::StringUtils::convert_to_int<i16>("32768");
+ EXPECT(!actual_i16.has_value());
+
+ auto actual_i32 = AK::StringUtils::convert_to_int<i32>("-1");
+ EXPECT(actual_i32.has_value());
+ EXPECT_EQ(actual_i32.value(), -1);
+ EXPECT_EQ(sizeof(actual_i32.value()), (size_t)4);
+ actual_i32 = AK::StringUtils::convert_to_int<i32>("2147483648");
+ EXPECT(!actual_i32.has_value());
+
+ auto actual_i64 = AK::StringUtils::convert_to_int<i64>("-1");
+ EXPECT(actual_i64.has_value());
+ EXPECT_EQ(actual_i64.value(), -1);
+ EXPECT_EQ(sizeof(actual_i64.value()), (size_t)8);
+ actual_i64 = AK::StringUtils::convert_to_int<i64>("9223372036854775808");
+ EXPECT(!actual_i64.has_value());
+}
+
+TEST_CASE(convert_to_uint)
+{
+ auto value = AK::StringUtils::convert_to_uint(StringView());
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_uint("");
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_uint("a");
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_uint("+");
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_uint("-");
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_uint("+1");
+ EXPECT(!value.has_value());
+
+ value = AK::StringUtils::convert_to_uint("-1");
+ EXPECT(!value.has_value());
+
+ auto actual = AK::StringUtils::convert_to_uint("0");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 0u);
+
+ actual = AK::StringUtils::convert_to_uint("1");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 1u);
+
+ actual = AK::StringUtils::convert_to_uint("01");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 1u);
+
+ actual = AK::StringUtils::convert_to_uint("12345");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 12345u);
+
+ actual = AK::StringUtils::convert_to_uint(" \t12345 \n\n");
+ EXPECT_EQ(actual.has_value(), true);
+ EXPECT_EQ(actual.value(), 12345u);
+
+ auto actual_u8 = AK::StringUtils::convert_to_uint<u8>("255");
+ EXPECT(actual_u8.has_value());
+ EXPECT_EQ(actual_u8.value(), 255u);
+ EXPECT_EQ(sizeof(actual_u8.value()), (size_t)1);
+ actual_u8 = AK::StringUtils::convert_to_uint<u8>("256");
+ EXPECT(!actual_u8.has_value());
+
+ auto actual_u16 = AK::StringUtils::convert_to_uint<u16>("65535");
+ EXPECT(actual_u16.has_value());
+ EXPECT_EQ(actual_u16.value(), 65535u);
+ EXPECT_EQ(sizeof(actual_u16.value()), (size_t)2);
+ actual_u16 = AK::StringUtils::convert_to_uint<u16>("65536");
+ EXPECT(!actual_u16.has_value());
+
+ auto actual_u32 = AK::StringUtils::convert_to_uint<u32>("4294967295");
+ EXPECT(actual_u32.has_value());
+ EXPECT_EQ(actual_u32.value(), 4294967295ul);
+ EXPECT_EQ(sizeof(actual_u32.value()), (size_t)4);
+ actual_u32 = AK::StringUtils::convert_to_uint<u32>("4294967296");
+ EXPECT(!actual_u32.has_value());
+
+ auto actual_u64 = AK::StringUtils::convert_to_uint<u64>("18446744073709551615");
+ EXPECT(actual_u64.has_value());
+ EXPECT_EQ(actual_u64.value(), 18446744073709551615ull);
+ EXPECT_EQ(sizeof(actual_u64.value()), (size_t)8);
+ actual_u64 = AK::StringUtils::convert_to_uint<u64>("18446744073709551616");
+ EXPECT(!actual_u64.has_value());
+}
+
+TEST_CASE(ends_with)
+{
+ String test_string = "ABCDEF";
+ EXPECT(AK::StringUtils::ends_with(test_string, "DEF", CaseSensitivity::CaseSensitive));
+ EXPECT(AK::StringUtils::ends_with(test_string, "ABCDEF", CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::ends_with(test_string, "ABCDE", CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::ends_with(test_string, "ABCDEFG", CaseSensitivity::CaseSensitive));
+ EXPECT(AK::StringUtils::ends_with(test_string, "def", CaseSensitivity::CaseInsensitive));
+ EXPECT(!AK::StringUtils::ends_with(test_string, "def", CaseSensitivity::CaseSensitive));
+}
+
+TEST_CASE(starts_with)
+{
+ String test_string = "ABCDEF";
+ EXPECT(AK::StringUtils::starts_with(test_string, "ABC", CaseSensitivity::CaseSensitive));
+ EXPECT(AK::StringUtils::starts_with(test_string, "ABCDEF", CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::starts_with(test_string, "BCDEF", CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::starts_with(test_string, "ABCDEFG", CaseSensitivity::CaseSensitive));
+ EXPECT(AK::StringUtils::starts_with(test_string, "abc", CaseSensitivity::CaseInsensitive));
+ EXPECT(!AK::StringUtils::starts_with(test_string, "abc", CaseSensitivity::CaseSensitive));
+}
+
+TEST_CASE(contains)
+{
+ String test_string = "ABCDEFABCXYZ";
+ EXPECT(AK::StringUtils::contains(test_string, "ABC", CaseSensitivity::CaseSensitive));
+ EXPECT(AK::StringUtils::contains(test_string, "ABC", CaseSensitivity::CaseInsensitive));
+ EXPECT(AK::StringUtils::contains(test_string, "AbC", CaseSensitivity::CaseInsensitive));
+ EXPECT(AK::StringUtils::contains(test_string, "BCX", CaseSensitivity::CaseSensitive));
+ EXPECT(AK::StringUtils::contains(test_string, "BCX", CaseSensitivity::CaseInsensitive));
+ EXPECT(AK::StringUtils::contains(test_string, "BcX", CaseSensitivity::CaseInsensitive));
+ EXPECT(!AK::StringUtils::contains(test_string, "xyz", CaseSensitivity::CaseSensitive));
+ EXPECT(AK::StringUtils::contains(test_string, "xyz", CaseSensitivity::CaseInsensitive));
+ EXPECT(!AK::StringUtils::contains(test_string, "EFG", CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::contains(test_string, "EfG", CaseSensitivity::CaseInsensitive));
+ EXPECT(AK::StringUtils::contains(test_string, "", CaseSensitivity::CaseSensitive));
+ EXPECT(AK::StringUtils::contains(test_string, "", CaseSensitivity::CaseInsensitive));
+ EXPECT(!AK::StringUtils::contains("", test_string, CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::contains("", test_string, CaseSensitivity::CaseInsensitive));
+ EXPECT(!AK::StringUtils::contains(test_string, "L", CaseSensitivity::CaseSensitive));
+ EXPECT(!AK::StringUtils::contains(test_string, "L", CaseSensitivity::CaseInsensitive));
+}
+
+TEST_CASE(is_whitespace)
+{
+ EXPECT(AK::StringUtils::is_whitespace(""));
+ EXPECT(AK::StringUtils::is_whitespace(" "));
+ EXPECT(AK::StringUtils::is_whitespace(" \t"));
+ EXPECT(AK::StringUtils::is_whitespace(" \t\n"));
+ EXPECT(AK::StringUtils::is_whitespace(" \t\n\r\v"));
+ EXPECT(!AK::StringUtils::is_whitespace(" a "));
+ EXPECT(!AK::StringUtils::is_whitespace("a\t"));
+}
+
+TEST_CASE(find)
+{
+ String test_string = "1234567";
+ EXPECT_EQ(AK::StringUtils::find(test_string, "1").value_or(1), 0u);
+ EXPECT_EQ(AK::StringUtils::find(test_string, "2").value_or(2), 1u);
+ EXPECT_EQ(AK::StringUtils::find(test_string, "3").value_or(3), 2u);
+ EXPECT_EQ(AK::StringUtils::find(test_string, "4").value_or(4), 3u);
+ EXPECT_EQ(AK::StringUtils::find(test_string, "5").value_or(5), 4u);
+ EXPECT_EQ(AK::StringUtils::find(test_string, "34").value_or(3), 2u);
+ EXPECT_EQ(AK::StringUtils::find(test_string, "78").has_value(), false);
+}
+
+TEST_CASE(to_snakecase)
+{
+ EXPECT_EQ(AK::StringUtils::to_snakecase("foobar"), "foobar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("Foobar"), "foobar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("FOOBAR"), "foobar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("fooBar"), "foo_bar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("FooBar"), "foo_bar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("fooBAR"), "foo_bar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("FOOBar"), "foo_bar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("foo_bar"), "foo_bar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("FBar"), "f_bar");
+ EXPECT_EQ(AK::StringUtils::to_snakecase("FooB"), "foo_b");
+}
diff --git a/Tests/AK/TestStringView.cpp b/Tests/AK/TestStringView.cpp
new file mode 100644
index 0000000000..2ffbdf65fd
--- /dev/null
+++ b/Tests/AK/TestStringView.cpp
@@ -0,0 +1,179 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/String.h>
+
+TEST_CASE(construct_empty)
+{
+ EXPECT(StringView().is_null());
+ EXPECT(StringView().is_empty());
+ EXPECT(!StringView().characters_without_null_termination());
+ EXPECT_EQ(StringView().length(), 0u);
+}
+
+TEST_CASE(view_literal)
+{
+ const char* truth = "cats rule dogs drool";
+ StringView view(truth);
+ EXPECT_EQ(view.is_null(), false);
+ EXPECT_EQ(view.characters_without_null_termination(), truth);
+ EXPECT_EQ(view, view);
+ EXPECT_EQ(view, truth);
+}
+
+TEST_CASE(compare_views)
+{
+ String foo1 = "foo";
+ String foo2 = "foo";
+ auto view1 = foo1.view();
+ auto view2 = foo2.view();
+
+ EXPECT_EQ(view1, view2);
+ EXPECT_EQ(view1, foo1);
+ EXPECT_EQ(view1, foo2);
+ EXPECT_EQ(view1, "foo");
+}
+
+TEST_CASE(string_view_literal_operator)
+{
+ StringView literal_view = "foo"sv;
+ String test_string = "foo";
+
+ EXPECT_EQ(literal_view.length(), test_string.length());
+ EXPECT_EQ(literal_view, test_string);
+}
+
+TEST_CASE(starts_with)
+{
+ String test_string = "ABCDEF";
+ StringView test_string_view = test_string.view();
+ EXPECT(test_string_view.starts_with('A'));
+ EXPECT(!test_string_view.starts_with('B'));
+ EXPECT(test_string_view.starts_with("AB"));
+ EXPECT(test_string_view.starts_with("ABCDEF"));
+ EXPECT(!test_string_view.starts_with("DEF"));
+ EXPECT(test_string_view.starts_with("abc", CaseSensitivity::CaseInsensitive));
+ EXPECT(!test_string_view.starts_with("abc", CaseSensitivity::CaseSensitive));
+}
+
+TEST_CASE(ends_with)
+{
+ String test_string = "ABCDEF";
+ StringView test_string_view = test_string.view();
+ EXPECT(test_string_view.ends_with("DEF"));
+ EXPECT(test_string_view.ends_with('F'));
+ EXPECT(!test_string_view.ends_with('E'));
+ EXPECT(test_string_view.ends_with("ABCDEF"));
+ EXPECT(!test_string_view.ends_with("ABCDE"));
+ EXPECT(!test_string_view.ends_with("ABCDEFG"));
+ EXPECT(test_string_view.ends_with("def", CaseSensitivity::CaseInsensitive));
+ EXPECT(!test_string_view.ends_with("def", CaseSensitivity::CaseSensitive));
+}
+
+TEST_CASE(lines)
+{
+ String test_string = "a\nb\r\nc\rd";
+ StringView test_string_view = test_string.view();
+ Vector<StringView> test_string_vector = test_string_view.lines();
+ EXPECT_EQ(test_string_vector.size(), 4u);
+ EXPECT(test_string_vector.at(0) == String("a"));
+ EXPECT(test_string_vector.at(1) == String("b"));
+ EXPECT(test_string_vector.at(2) == String("c"));
+ EXPECT(test_string_vector.at(3) == String("d"));
+
+ test_string = "```\nHello there\r\nHello there\n```";
+ test_string_view = test_string.view();
+ test_string_vector = test_string_view.lines();
+ EXPECT_EQ(test_string_vector.size(), 4u);
+ EXPECT(test_string_vector.at(0) == String("```"));
+ EXPECT(test_string_vector.at(1) == String("Hello there"));
+ EXPECT(test_string_vector.at(2) == String("Hello there"));
+ EXPECT(test_string_vector.at(3) == String("```"));
+
+ test_string = "\n\n\n";
+ test_string_view = test_string.view();
+ test_string_vector = test_string_view.lines();
+ EXPECT_EQ(test_string_vector.size(), 3u);
+ EXPECT_EQ(test_string_vector.at(0).is_empty(), true);
+ EXPECT_EQ(test_string_vector.at(1).is_empty(), true);
+ EXPECT_EQ(test_string_vector.at(2).is_empty(), true);
+}
+
+TEST_CASE(find_first_of)
+{
+ String test_string = "aabbcc_xy_ccbbaa";
+ StringView test_string_view = test_string.view();
+
+ EXPECT_EQ(test_string_view.find_first_of('b').has_value(), true);
+ EXPECT_EQ(test_string_view.find_first_of('b').value(), 2U);
+
+ EXPECT_EQ(test_string_view.find_first_of('_').has_value(), true);
+ EXPECT_EQ(test_string_view.find_first_of('_').value(), 6U);
+
+ EXPECT_EQ(test_string_view.find_first_of("bc").has_value(), true);
+ EXPECT_EQ(test_string_view.find_first_of("bc").value(), 2U);
+
+ EXPECT_EQ(test_string_view.find_first_of("yx").has_value(), true);
+ EXPECT_EQ(test_string_view.find_first_of("yx").value(), 7U);
+
+ EXPECT_EQ(test_string_view.find_first_of('n').has_value(), false);
+ EXPECT_EQ(test_string_view.find_first_of("defg").has_value(), false);
+}
+
+TEST_CASE(find_last_of)
+{
+ String test_string = "aabbcc_xy_ccbbaa";
+ StringView test_string_view = test_string.view();
+
+ EXPECT_EQ(test_string_view.find_last_of('b').has_value(), true);
+ EXPECT_EQ(test_string_view.find_last_of('b').value(), 13U);
+
+ EXPECT_EQ(test_string_view.find_last_of('_').has_value(), true);
+ EXPECT_EQ(test_string_view.find_last_of('_').value(), 9U);
+
+ EXPECT_EQ(test_string_view.find_last_of("bc").has_value(), true);
+ EXPECT_EQ(test_string_view.find_last_of("bc").value(), 13U);
+
+ EXPECT_EQ(test_string_view.find_last_of("yx").has_value(), true);
+ EXPECT_EQ(test_string_view.find_last_of("yx").value(), 8U);
+
+ EXPECT_EQ(test_string_view.find_last_of('3').has_value(), false);
+ EXPECT_EQ(test_string_view.find_last_of("fghi").has_value(), false);
+
+ test_string_view = "/";
+ EXPECT_EQ(test_string_view.find_last_of('/').has_value(), true);
+ EXPECT_EQ(test_string_view.find_last_of('/').value(), 0U);
+ EXPECT_EQ(test_string_view.find_last_of("/").has_value(), true);
+ EXPECT_EQ(test_string_view.find_last_of("/").value(), 0U);
+}
+
+TEST_CASE(split_view)
+{
+ StringView test_string_view = "axxbxcxd";
+ EXPECT_EQ(test_string_view.split_view('x'), Vector<StringView>({ "a", "b", "c", "d" }));
+ EXPECT_EQ(test_string_view.split_view('x', true), Vector<StringView>({ "a", "", "b", "c", "d" }));
+ EXPECT_EQ(test_string_view.split_view("x"), Vector<StringView>({ "a", "b", "c", "d" }));
+ EXPECT_EQ(test_string_view.split_view("x", true), Vector<StringView>({ "a", "", "b", "c", "d" }));
+
+ test_string_view = "axxbx";
+ EXPECT_EQ(test_string_view.split_view('x'), Vector<StringView>({ "a", "b" }));
+ EXPECT_EQ(test_string_view.split_view('x', true), Vector<StringView>({ "a", "", "b", "" }));
+ EXPECT_EQ(test_string_view.split_view("x"), Vector<StringView>({ "a", "b" }));
+ EXPECT_EQ(test_string_view.split_view("x", true), Vector<StringView>({ "a", "", "b", "" }));
+
+ test_string_view = "axxbcxxdxx";
+ EXPECT_EQ(test_string_view.split_view("xx"), Vector<StringView>({ "a", "bc", "d" }));
+ EXPECT_EQ(test_string_view.split_view("xx", true), Vector<StringView>({ "a", "bc", "d", "" }));
+
+ test_string_view = "ax_b_cxd";
+ auto predicate = [](char ch) { return ch == 'x' || ch == '_'; };
+ EXPECT_EQ(test_string_view.split_view_if(predicate), Vector<StringView>({ "a", "b", "c", "d" }));
+ EXPECT_EQ(test_string_view.split_view_if(predicate, true), Vector<StringView>({ "a", "", "b", "c", "d" }));
+ EXPECT_EQ(test_string_view.split_view_if(predicate), Vector<StringView>({ "a", "b", "c", "d" }));
+ EXPECT_EQ(test_string_view.split_view_if(predicate, true), Vector<StringView>({ "a", "", "b", "c", "d" }));
+}
diff --git a/Tests/AK/TestTime.cpp b/Tests/AK/TestTime.cpp
new file mode 100644
index 0000000000..61319cd605
--- /dev/null
+++ b/Tests/AK/TestTime.cpp
@@ -0,0 +1,263 @@
+/*
+ * Copyright (c) 2021, Ben Wiederhake <BenWiederhake.GitHub@gmx.de>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Time.h>
+#include <sys/time.h>
+
+#define EXPECT_TIME(t, s, ns) \
+ do { \
+ auto ts = (t).to_timespec(); \
+ EXPECT_EQ(ts.tv_sec, (s)); \
+ EXPECT_EQ(ts.tv_nsec, (ns)); \
+ } while (0)
+
+TEST_CASE(is_sane)
+{
+ auto t0 = Time::from_seconds(0);
+ auto t2 = Time::from_seconds(2);
+ auto t5 = Time::from_seconds(5);
+ auto tn3 = Time::from_seconds(-3);
+ EXPECT(t0 == t0);
+ EXPECT(t2 == t2);
+ EXPECT(t5 == t5);
+ EXPECT(t0 != t2);
+ EXPECT(t2 != tn3);
+ EXPECT(t2 != t5);
+ EXPECT_TIME(t0, 0, 0);
+ EXPECT_TIME(t2, 2, 0);
+ EXPECT_TIME(t5, 5, 0);
+ EXPECT_TIME(t2 + t5, 7, 0);
+ EXPECT_TIME(tn3 + t2, -1, 0);
+ EXPECT_TIME(tn3 + t5, 2, 0);
+}
+
+TEST_CASE(limits)
+{
+ EXPECT_TIME(Time::min(), (i64)-0x8000'0000'0000'0000, 0);
+ EXPECT_TIME(Time::max(), 0x7fff'ffff'ffff'ffff, 999'999'999);
+}
+
+TEST_CASE(seconds_parsing)
+{
+ EXPECT_TIME(Time::from_seconds(0), 0, 0);
+ EXPECT_TIME(Time::from_seconds(42), 42, 0);
+ EXPECT_TIME(Time::from_seconds(-1), -1, 0);
+
+ // "6.4.4.1.5: The type of an integer constant is the first of the corresponding list in which its value can be represented."
+ // In the case of "0x8000'0000", the list is "int, unsigned int, …", and unsigned int (u32) matches.
+ // Then the unary minus: On unsigned 32-bit integers, -0x8000'0000 == 0x8000'0000, which only then is made signed again.
+ // So we would pass a medium-large *positive* number to 'from_seconds', which is not what we want to test here.
+ // That's why this is the only place that needs an "LL" suffix.
+ EXPECT_TIME(Time::from_seconds(-0x8000'0000LL), -0x8000'0000LL, 0);
+ EXPECT_TIME(Time::from_seconds(-0x8000'0000'0000'0000), (i64)-0x8000'0000'0000'0000, 0);
+ EXPECT_TIME(Time::from_seconds(0x7fff'ffff'ffff'ffff), 0x7fff'ffff'ffff'ffff, 0);
+}
+
+TEST_CASE(timespec_parsing)
+{
+ EXPECT_TIME(Time::from_timespec(timespec { 2, 4 }), 2, 4);
+ EXPECT_TIME(Time::from_timespec(timespec { 1234, 5678 }), 1234, 5678);
+
+ EXPECT_TIME(Time::from_timespec(timespec { 0, 1'000'000'000 }), 1, 0);
+ EXPECT_TIME(Time::from_timespec(timespec { 8, 2'000'000'000 }), 10, 0);
+ EXPECT_TIME(Time::from_timespec(timespec { 0, 2'147'483'647 }), 2, 147'483'647);
+
+ EXPECT_TIME(Time::from_timespec(timespec { 1, -1 }), 0, 999'999'999);
+ EXPECT_TIME(Time::from_timespec(timespec { 0, -1 }), -1, 999'999'999);
+ EXPECT_TIME(Time::from_timespec(timespec { -1, 0 }), -1, 0);
+ EXPECT_TIME(Time::from_timespec(timespec { -1, 1'000'000'001 }), 0, 1);
+ EXPECT_TIME(Time::from_timespec(timespec { -2, 2'000'000'003 }), 0, 3);
+ EXPECT_TIME(Time::from_timespec(timespec { -2, 1'999'999'999 }), -1, 999'999'999);
+
+ EXPECT_TIME(Time::from_timespec(timespec { 0x7fff'ffff'ffff'fffe, 999'999'998 }), 0x7fff'ffff'ffff'fffe, 999'999'998);
+ EXPECT_TIME(Time::from_timespec(timespec { 0x7fff'ffff'ffff'fffe, 1'999'999'998 }), 0x7fff'ffff'ffff'ffff, 999'999'998);
+ EXPECT_TIME(Time::from_timespec(timespec { 0x7fff'ffff'ffff'fffe, 1'999'999'999 }), 0x7fff'ffff'ffff'ffff, 999'999'999);
+ EXPECT_TIME(Time::from_timespec(timespec { 0x7fff'ffff'ffff'fffe, 2'000'000'000 }), 0x7fff'ffff'ffff'ffff, 999'999'999);
+
+ EXPECT_TIME(Time::from_timespec(timespec { -0x7fff'ffff'ffff'fffe, -1 }), -0x7fff'ffff'ffff'ffff, 999'999'999);
+ EXPECT_TIME(Time::from_timespec(timespec { -0x7fff'ffff'ffff'fffe, -999'999'999 }), -0x7fff'ffff'ffff'ffff, 1);
+ EXPECT_TIME(Time::from_timespec(timespec { -0x7fff'ffff'ffff'fffe, -1'999'999'999 }), (i64)-0x8000'0000'0000'0000, 1);
+ EXPECT_TIME(Time::from_timespec(timespec { -0x7fff'ffff'ffff'fffe, -2'000'000'000 }), (i64)-0x8000'0000'0000'0000, 0);
+ EXPECT_TIME(Time::from_timespec(timespec { -0x7fff'ffff'ffff'fffe, -2'000'000'001 }), (i64)-0x8000'0000'0000'0000, 0);
+}
+
+TEST_CASE(timeval_parsing)
+{
+ EXPECT_TIME(Time::from_timeval(timeval { 2, 4 }), 2, 4'000);
+ EXPECT_TIME(Time::from_timeval(timeval { 1234, 5'678 }), 1234, 5'678'000);
+ EXPECT_TIME(Time::from_timeval(timeval { -123, -45'678 }), -124, 954'322'000);
+
+ EXPECT_TIME(Time::from_timeval(timeval { 0, 1'000'000 }), 1, 0);
+ EXPECT_TIME(Time::from_timeval(timeval { 0, 1'000'000'000 }), 1'000, 0);
+ EXPECT_TIME(Time::from_timeval(timeval { 8, 2'000'000 }), 10, 0);
+ EXPECT_TIME(Time::from_timeval(timeval { 0, 2'147'483'647 }), 2'147, 483'647'000);
+
+ EXPECT_TIME(Time::from_timeval(timeval { 1, -1 }), 0, 999'999'000);
+ EXPECT_TIME(Time::from_timeval(timeval { 0, -1 }), -1, 999'999'000);
+ EXPECT_TIME(Time::from_timeval(timeval { -1, 0 }), -1, 0);
+ EXPECT_TIME(Time::from_timeval(timeval { -1, 1'000'001 }), 0, 1'000);
+ EXPECT_TIME(Time::from_timeval(timeval { -2, 2'000'003 }), 0, 3'000);
+ EXPECT_TIME(Time::from_timeval(timeval { -2, 1'999'999 }), -1, 999'999'000);
+
+ EXPECT_TIME(Time::from_timeval(timeval { 0x7fff'ffff'ffff'fffe, 999'998 }), 0x7fff'ffff'ffff'fffe, 999'998'000);
+ EXPECT_TIME(Time::from_timeval(timeval { 0x7fff'ffff'ffff'fffe, 1'999'998 }), 0x7fff'ffff'ffff'ffff, 999'998'000);
+ EXPECT_TIME(Time::from_timeval(timeval { 0x7fff'ffff'ffff'fffe, 1'999'999 }), 0x7fff'ffff'ffff'ffff, 999'999'000);
+ EXPECT_TIME(Time::from_timeval(timeval { 0x7fff'ffff'ffff'fffe, 2'000'000 }), 0x7fff'ffff'ffff'ffff, 999'999'999);
+
+ EXPECT_TIME(Time::from_timeval(timeval { -0x7fff'ffff'ffff'fffe, -1 }), -0x7fff'ffff'ffff'ffff, 999'999'000);
+ EXPECT_TIME(Time::from_timeval(timeval { -0x7fff'ffff'ffff'fffe, -999'999 }), -0x7fff'ffff'ffff'ffff, 1'000);
+ EXPECT_TIME(Time::from_timeval(timeval { -0x7fff'ffff'ffff'fffe, -1'999'999 }), (i64)-0x8000'0000'0000'0000, 1'000);
+ EXPECT_TIME(Time::from_timeval(timeval { -0x7fff'ffff'ffff'fffe, -2'000'000 }), (i64)-0x8000'0000'0000'0000, 0);
+ EXPECT_TIME(Time::from_timeval(timeval { -0x7fff'ffff'ffff'fffe, -2'000'001 }), (i64)-0x8000'0000'0000'0000, 0);
+}
+
+#define TIME(s, ns) \
+ Time::from_timespec(timespec { (s), (ns) })
+
+TEST_CASE(addition)
+{
+#define EXPECT_ADDITION(s1, ns1, s2, ns2, sr, nsr) \
+ do { \
+ EXPECT_TIME(TIME(s1, ns1) + TIME(s2, ns2), sr, nsr); \
+ EXPECT_TIME(TIME(s2, ns2) + TIME(s1, ns1), sr, nsr); \
+ auto t = TIME(s1, ns1); \
+ t += TIME(s2, ns2); \
+ EXPECT_TIME(t, sr, nsr); \
+ } while (0)
+
+ EXPECT_ADDITION(11, 123'456'789, 22, 900'000'000, 34, 23'456'789);
+
+ EXPECT_ADDITION(0, 0, 9223372036854775807LL, 999'999'998, 0x7fff'ffff'ffff'ffff, 999'999'998);
+ EXPECT_ADDITION(0, 1, 9223372036854775807LL, 999'999'998, 0x7fff'ffff'ffff'ffff, 999'999'999);
+ EXPECT_ADDITION(0, 2, 9223372036854775807LL, 999'999'998, 0x7fff'ffff'ffff'ffff, 999'999'999);
+
+ EXPECT_ADDITION(0x80, 40, 0x7fff'ffff'ffff'ff7f, 999'999'958, 0x7fff'ffff'ffff'ffff, 999'999'998);
+ EXPECT_ADDITION(0x80, 41, 0x7fff'ffff'ffff'ff7f, 999'999'958, 0x7fff'ffff'ffff'ffff, 999'999'999);
+ EXPECT_ADDITION(0x80, 42, 0x7fff'ffff'ffff'ff7f, 999'999'958, 0x7fff'ffff'ffff'ffff, 999'999'999);
+
+ EXPECT_ADDITION(-2, 5, -3, 7, -5, 12);
+ EXPECT_ADDITION(-2, 999'999'995, -3, 999'999'997, -4, 999'999'992);
+
+ EXPECT_ADDITION(-0x7fff'ffff'ffff'ffff, 999'999'995, -1, 6, -0x7fff'ffff'ffff'ffff, 1);
+ EXPECT_ADDITION(-0x7fff'ffff'ffff'ffff, 999'999'995, -2, 6, (i64)-0x8000'0000'0000'0000, 1);
+ EXPECT_ADDITION(-0x7fff'ffff'ffff'ffff, 999'999'995, -2, 5, (i64)-0x8000'0000'0000'0000, 0);
+ EXPECT_ADDITION(-0x7fff'ffff'ffff'ffff, 999'999'995, -2, 4, (i64)-0x8000'0000'0000'0000, 0);
+
+ EXPECT_ADDITION((i64)-0x8000'0000'0000'0000, 999'999'995, 0x7fff'ffff'ffff'ffff, 4, -1, 999'999'999);
+ EXPECT_ADDITION((i64)-0x8000'0000'0000'0000, 999'999'995, 0x7fff'ffff'ffff'ffff, 5, 0, 0);
+ EXPECT_ADDITION((i64)-0x8000'0000'0000'0000, 999'999'995, 0x7fff'ffff'ffff'ffff, 6, 0, 1);
+#undef EXPECT_ADDITION
+}
+
+TEST_CASE(subtraction)
+{
+#define EXPECT_SUBTRACTION(s1, ns1, s2, ns2, sr, nsr) \
+ do { \
+ EXPECT_TIME(TIME(s1, ns1) - TIME(s2, ns2), sr, nsr); \
+ auto t = TIME(s1, ns1); \
+ t -= TIME(s2, ns2); \
+ EXPECT_TIME(t, sr, nsr); \
+ } while (0)
+
+ EXPECT_SUBTRACTION(5, 0, 3, 0, 2, 0);
+ EXPECT_SUBTRACTION(0, 0, 0, 0, 0, 0);
+ EXPECT_SUBTRACTION(0, 5, 0, 3, 0, 2);
+ EXPECT_SUBTRACTION(0x7fff'ffff'ffff'ffff, 999'999'999, 8, 123, 0x7fff'ffff'ffff'fff7, 999'999'876);
+
+ EXPECT_SUBTRACTION(1, 0, 0, 999'999'999, 0, 1);
+ EXPECT_SUBTRACTION(0x7fff'ffff'ffff'ffff, 0, 1, 999'999'999, 0x7fff'ffff'ffff'fffd, 1);
+
+ EXPECT_SUBTRACTION(3, 0, 5, 0, -2, 0);
+ EXPECT_SUBTRACTION(0, 3, 0, 5, -1, 999'999'998);
+ EXPECT_SUBTRACTION(0, 0, 0x7fff'ffff'ffff'ffff, 999'999'999, (i64)-0x8000'0000'0000'0000, 1);
+ EXPECT_SUBTRACTION(0, 0, (i64)-0x8000'0000'0000'0000, 0, 0x7fff'ffff'ffff'ffff, 999'999'999);
+ EXPECT_SUBTRACTION(-1, 999'999'999, (i64)-0x8000'0000'0000'0000, 0, 0x7fff'ffff'ffff'ffff, 999'999'999);
+ EXPECT_SUBTRACTION(-1, 999'999'998, (i64)-0x8000'0000'0000'0000, 0, 0x7fff'ffff'ffff'ffff, 999'999'998);
+
+ EXPECT_SUBTRACTION(123, 456, 123, 455, 0, 1);
+ EXPECT_SUBTRACTION(123, 456, 123, 456, 0, 0);
+ EXPECT_SUBTRACTION(123, 456, 123, 457, -1, 999'999'999);
+
+ EXPECT_SUBTRACTION(124, 456, 123, 455, 1, 1);
+ EXPECT_SUBTRACTION(124, 456, 123, 456, 1, 0);
+ EXPECT_SUBTRACTION(124, 456, 123, 457, 0, 999'999'999);
+
+ EXPECT_SUBTRACTION(-0x7fff'ffff'ffff'ffff, 999'999'995, 1, 999'999'994, (i64)-0x8000'0000'0000'0000, 1);
+ EXPECT_SUBTRACTION(-0x7fff'ffff'ffff'ffff, 999'999'995, 1, 999'999'995, (i64)-0x8000'0000'0000'0000, 0);
+ EXPECT_SUBTRACTION(-0x7fff'ffff'ffff'ffff, 999'999'995, 1, 999'999'996, (i64)-0x8000'0000'0000'0000, 0);
+}
+
+TEST_CASE(rounding)
+{
+ EXPECT_EQ(TIME(2, 800'800'800).to_seconds(), 3);
+ EXPECT_EQ(TIME(2, 800'800'800).to_milliseconds(), 2'801);
+ EXPECT_EQ(TIME(2, 800'800'800).to_microseconds(), 2'800'801);
+ EXPECT_EQ(TIME(2, 800'800'800).to_nanoseconds(), 2'800'800'800);
+ EXPECT_EQ(TIME(-2, 800'800'800).to_seconds(), -2);
+ EXPECT_EQ(TIME(-2, 800'800'800).to_milliseconds(), -1'200);
+ EXPECT_EQ(TIME(-2, 800'800'800).to_microseconds(), -1'199'200);
+ EXPECT_EQ(TIME(-2, 800'800'800).to_nanoseconds(), -1'199'199'200);
+
+ EXPECT_EQ(TIME(0, 0).to_seconds(), 0);
+ EXPECT_EQ(TIME(0, 0).to_milliseconds(), 0);
+ EXPECT_EQ(TIME(0, 0).to_microseconds(), 0);
+ EXPECT_EQ(TIME(0, 0).to_nanoseconds(), 0);
+
+ EXPECT_EQ(TIME(0, 1).to_seconds(), 1);
+ EXPECT_EQ(TIME(0, 1).to_milliseconds(), 1);
+ EXPECT_EQ(TIME(0, 1).to_microseconds(), 1);
+ EXPECT_EQ(TIME(0, 1).to_nanoseconds(), 1);
+ EXPECT_EQ(TIME(0, -1).to_seconds(), -1);
+ EXPECT_EQ(TIME(0, -1).to_milliseconds(), -1);
+ EXPECT_EQ(TIME(0, -1).to_microseconds(), -1);
+ EXPECT_EQ(TIME(0, -1).to_nanoseconds(), -1);
+
+ EXPECT_EQ(TIME(-9223372037, 145'224'191).to_nanoseconds(), (i64)-0x8000'0000'0000'0000);
+ EXPECT_EQ(TIME(-9223372037, 145'224'192).to_nanoseconds(), (i64)-0x8000'0000'0000'0000);
+ EXPECT_EQ(TIME(-9223372037, 145'224'193).to_nanoseconds(), -0x7fff'ffff'ffff'ffff);
+ EXPECT_EQ(TIME(9223372036, 854'775'806).to_nanoseconds(), 0x7fff'ffff'ffff'fffe);
+ EXPECT_EQ(TIME(9223372036, 854'775'807).to_nanoseconds(), 0x7fff'ffff'ffff'ffff);
+ EXPECT_EQ(TIME(9223372036, 854'775'808).to_nanoseconds(), 0x7fff'ffff'ffff'ffff);
+}
+
+TEST_CASE(truncation)
+{
+ // Sanity
+ EXPECT_EQ(TIME(2, 0).to_truncated_seconds(), 2);
+ EXPECT_EQ(TIME(-2, 0).to_truncated_seconds(), -2);
+ EXPECT_EQ(TIME(2, 800'800'800).to_truncated_seconds(), 2);
+ EXPECT_EQ(TIME(2, 800'800'800).to_truncated_milliseconds(), 2'800);
+ EXPECT_EQ(TIME(2, 800'800'800).to_truncated_microseconds(), 2'800'800);
+ EXPECT_EQ(TIME(-2, -800'800'800).to_truncated_seconds(), -2);
+ EXPECT_EQ(TIME(-2, -800'800'800).to_truncated_milliseconds(), -2'800);
+ EXPECT_EQ(TIME(-2, -800'800'800).to_truncated_microseconds(), -2'800'800);
+
+ // Overflow, seconds
+ EXPECT_EQ(Time::min().to_truncated_seconds(), (i64)-0x8000'0000'0000'0000);
+ EXPECT_EQ(Time::max().to_truncated_seconds(), 0x7fff'ffff'ffff'ffff);
+
+ // Overflow, milliseconds
+ EXPECT_EQ(TIME(-9223372036854776, 191'000'000).to_truncated_milliseconds(), (i64)-0x8000'0000'0000'0000);
+ EXPECT_EQ(TIME(-9223372036854776, 192'000'000).to_truncated_milliseconds(), (i64)-0x8000'0000'0000'0000);
+ EXPECT_EQ(TIME(-9223372036854776, 192'000'001).to_truncated_milliseconds(), -0x7fff'ffff'ffff'ffff);
+ EXPECT_EQ(TIME(-9223372036854776, 193'000'000).to_truncated_milliseconds(), -0x7fff'ffff'ffff'ffff);
+ EXPECT_EQ(TIME(9223372036854775, 806'000'000).to_truncated_milliseconds(), 0x7fff'ffff'ffff'fffe);
+ EXPECT_EQ(TIME(9223372036854775, 806'999'999).to_truncated_milliseconds(), 0x7fff'ffff'ffff'fffe);
+ EXPECT_EQ(TIME(9223372036854775, 807'000'000).to_truncated_milliseconds(), 0x7fff'ffff'ffff'ffff);
+ EXPECT_EQ(TIME(9223372036854775, 808'000'000).to_truncated_milliseconds(), 0x7fff'ffff'ffff'ffff);
+
+ // Overflow, microseconds
+ EXPECT_EQ(TIME(-9223372036855, 224'191'000).to_truncated_microseconds(), (i64)-0x8000'0000'0000'0000);
+ EXPECT_EQ(TIME(-9223372036855, 224'192'000).to_truncated_microseconds(), (i64)-0x8000'0000'0000'0000);
+ EXPECT_EQ(TIME(-9223372036855, 224'192'001).to_truncated_microseconds(), (i64)-0x7fff'ffff'ffff'ffff);
+ EXPECT_EQ(TIME(-9223372036855, 224'193'000).to_truncated_microseconds(), (i64)-0x7fff'ffff'ffff'ffff);
+ EXPECT_EQ(TIME(9223372036854, 775'806'000).to_truncated_microseconds(), 0x7fff'ffff'ffff'fffe);
+ EXPECT_EQ(TIME(9223372036854, 775'806'999).to_truncated_microseconds(), 0x7fff'ffff'ffff'fffe);
+ EXPECT_EQ(TIME(9223372036854, 775'807'000).to_truncated_microseconds(), 0x7fff'ffff'ffff'ffff);
+ EXPECT_EQ(TIME(9223372036854, 775'808'000).to_truncated_microseconds(), 0x7fff'ffff'ffff'ffff);
+}
diff --git a/Tests/AK/TestTrie.cpp b/Tests/AK/TestTrie.cpp
new file mode 100644
index 0000000000..50b574cced
--- /dev/null
+++ b/Tests/AK/TestTrie.cpp
@@ -0,0 +1,68 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Trie.h>
+
+TEST_CASE(normal_behaviour)
+{
+ Trie<char, String> dictionary('/', "");
+ constexpr static const char* data[] { "test", "example", "foo", "foobar" };
+ constexpr static const size_t total_chars = 18; // root (1), 'test' (4), 'example' (7), 'foo' (3), 'foobar' (3, "foo" already stored).
+ for (auto& entry : data) {
+ StringView view { entry };
+ auto it = view.begin();
+ dictionary.insert(it, view.end(), view, [](auto& parent, auto& it) -> Optional<String> { return String::formatted("{}{}", parent.metadata_value(), *it); });
+ }
+
+ size_t i = 0;
+ for ([[maybe_unused]] auto& node : dictionary)
+ ++i;
+ EXPECT_EQ(i, total_chars);
+
+ for (auto& entry : data) {
+ StringView view { entry };
+ auto it = view.begin();
+ auto& node = dictionary.traverse_until_last_accessible_node(it, view.end());
+ EXPECT(it.is_end());
+ EXPECT(node.metadata().has_value());
+ EXPECT_EQ(view, node.metadata_value());
+ }
+
+ constexpr static const char* test_data_with_prefix_in_dict[] { "testx", "exampley", "fooa", "foobarb", "fox", "text" };
+ for (auto& entry : test_data_with_prefix_in_dict) {
+ StringView view { entry };
+ auto it = view.begin();
+ auto& node = dictionary.traverse_until_last_accessible_node(it, view.end());
+ EXPECT(!it.is_end());
+ EXPECT(node.metadata().has_value());
+ EXPECT(view.starts_with(node.metadata_value()));
+ }
+}
+
+TEST_CASE(iterate)
+{
+ Trie<int> bunch_of_numbers { 0 };
+ Array<int, 64> input;
+ for (size_t i = 0; i < input.size(); ++i)
+ input[i] = i;
+
+ bunch_of_numbers.insert(input.begin(), input.end());
+
+ // Iteration order is preorder (order between adjacent nodes is not defined, but parents come before children)
+ // in this case, the tree is linear.
+ size_t i = 0;
+ bool is_root = true;
+ for (auto& node : bunch_of_numbers) {
+ if (is_root) {
+ is_root = false;
+ continue;
+ }
+ EXPECT_EQ(input[i], node.value());
+ ++i;
+ }
+}
diff --git a/Tests/AK/TestTypeTraits.cpp b/Tests/AK/TestTypeTraits.cpp
new file mode 100644
index 0000000000..ecea1bfc15
--- /dev/null
+++ b/Tests/AK/TestTypeTraits.cpp
@@ -0,0 +1,107 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/StdLibExtras.h>
+#include <AK/TypeList.h>
+
+#define STATIC_EXPECT_EQ(lhs, rhs) \
+ static_assert(IsSame<lhs, rhs>, "");
+
+#define STATIC_EXPECT_FALSE(Expression) \
+ static_assert(!Expression, "");
+
+#define STATIC_EXPECT_TRUE(Expression) \
+ static_assert(Expression, "");
+
+#define EXPECT_TRAIT_TRUE(trait, ...) \
+ for_each_type<TypeList<__VA_ARGS__>>([]<typename T>(TypeWrapper<T>) { \
+ STATIC_EXPECT_TRUE(trait<T>); \
+ })
+
+#define EXPECT_TRAIT_FALSE(trait, ...) \
+ for_each_type<TypeList<__VA_ARGS__>>([]<typename T>(TypeWrapper<T>) { \
+ STATIC_EXPECT_FALSE(trait<T>); \
+ })
+
+#define EXPECT_EQ_WITH_TRAIT(trait, ListA, ListB) \
+ for_each_type_zipped<ListA, ListB>([]<typename A, typename B>(TypeWrapper<A>, TypeWrapper<B>) { \
+ STATIC_EXPECT_EQ(trait<A>, B); \
+ })
+
+struct Empty {
+};
+
+enum class Enummer : u8 {
+ Dummmy,
+};
+
+TEST_CASE(FundamentalTypeClassification)
+{
+ EXPECT_TRAIT_TRUE(IsVoid, void);
+ EXPECT_TRAIT_FALSE(IsVoid, int, Empty, std::nullptr_t);
+
+ EXPECT_TRAIT_TRUE(IsNullPointer, std::nullptr_t);
+ EXPECT_TRAIT_FALSE(IsNullPointer, void, int, Empty, decltype(0));
+
+ EXPECT_TRAIT_TRUE(IsFloatingPoint, float, double, long double);
+ EXPECT_TRAIT_FALSE(IsFloatingPoint, int, Empty, std::nullptr_t, void);
+
+ EXPECT_TRAIT_TRUE(IsArithmetic, float, double, long double, bool, size_t);
+ EXPECT_TRAIT_TRUE(IsArithmetic, char, signed char, unsigned char, char8_t, char16_t, char32_t);
+ EXPECT_TRAIT_TRUE(IsArithmetic, short, int, long, long long);
+ EXPECT_TRAIT_TRUE(IsArithmetic, unsigned short, unsigned int, unsigned long, unsigned long long);
+
+ EXPECT_TRAIT_FALSE(IsArithmetic, void, std::nullptr_t, Empty);
+
+ EXPECT_TRAIT_TRUE(IsFundamental, void, std::nullptr_t);
+ EXPECT_TRAIT_TRUE(IsFundamental, float, double, long double, bool, size_t);
+ EXPECT_TRAIT_TRUE(IsFundamental, char, signed char, unsigned char, char8_t, char16_t, char32_t);
+ EXPECT_TRAIT_TRUE(IsFundamental, short, int, long, long long);
+ EXPECT_TRAIT_TRUE(IsFundamental, unsigned short, unsigned int, unsigned long, unsigned long long);
+
+ EXPECT_TRAIT_FALSE(IsFundamental, Empty, int*, int&);
+
+ EXPECT_TRAIT_FALSE(IsSigned, unsigned);
+ EXPECT_TRAIT_FALSE(IsSigned, unsigned short);
+ EXPECT_TRAIT_FALSE(IsSigned, unsigned char);
+ EXPECT_TRAIT_FALSE(IsSigned, unsigned long);
+ EXPECT_TRAIT_TRUE(IsSigned, int);
+ EXPECT_TRAIT_TRUE(IsSigned, short);
+ EXPECT_TRAIT_TRUE(IsSigned, long);
+
+ EXPECT_TRAIT_TRUE(IsUnsigned, unsigned);
+ EXPECT_TRAIT_TRUE(IsUnsigned, unsigned short);
+ EXPECT_TRAIT_TRUE(IsUnsigned, unsigned char);
+ EXPECT_TRAIT_TRUE(IsUnsigned, unsigned long);
+ EXPECT_TRAIT_FALSE(IsUnsigned, int);
+ EXPECT_TRAIT_FALSE(IsUnsigned, short);
+ EXPECT_TRAIT_FALSE(IsUnsigned, long);
+
+ EXPECT_TRAIT_TRUE(IsEnum, Enummer);
+ EXPECT_TRAIT_FALSE(IsEnum, Empty);
+ EXPECT_TRAIT_FALSE(IsEnum, int);
+ EXPECT_TRAIT_FALSE(IsEnum, void);
+ EXPECT_TRAIT_FALSE(IsEnum, std::nullptr_t);
+}
+
+TEST_CASE(AddConst)
+{
+ // clang-format off
+ using NoConstList = TypeList<int, const int, Empty, const Empty>;
+ using YesConstList = TypeList<const int, const int, const Empty, const Empty>;
+ // clang-format on
+
+ EXPECT_EQ_WITH_TRAIT(AddConst, NoConstList, YesConstList);
+}
+
+TEST_CASE(UnderlyingType)
+{
+ using Type = UnderlyingType<Enummer>;
+
+ STATIC_EXPECT_EQ(Type, u8);
+}
diff --git a/Tests/AK/TestTypedTransfer.cpp b/Tests/AK/TestTypedTransfer.cpp
new file mode 100644
index 0000000000..5a0c347092
--- /dev/null
+++ b/Tests/AK/TestTypedTransfer.cpp
@@ -0,0 +1,41 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Array.h>
+#include <AK/TypedTransfer.h>
+
+struct NonPrimitiveIntWrapper {
+ NonPrimitiveIntWrapper(int value)
+ : m_value(value)
+ {
+ }
+
+ int m_value;
+};
+
+TEST_CASE(overlapping_source_and_destination_1)
+{
+ const Array<NonPrimitiveIntWrapper, 6> expected { 3, 4, 5, 6, 5, 6 };
+
+ Array<NonPrimitiveIntWrapper, 6> actual { 1, 2, 3, 4, 5, 6 };
+ AK::TypedTransfer<NonPrimitiveIntWrapper>::copy(actual.data(), actual.data() + 2, 4);
+
+ for (size_t i = 0; i < 6; ++i)
+ EXPECT_EQ(actual[i].m_value, expected[i].m_value);
+}
+
+TEST_CASE(overlapping_source_and_destination_2)
+{
+ const Array<NonPrimitiveIntWrapper, 6> expected { 1, 2, 1, 2, 3, 4 };
+
+ Array<NonPrimitiveIntWrapper, 6> actual { 1, 2, 3, 4, 5, 6 };
+ AK::TypedTransfer<NonPrimitiveIntWrapper>::copy(actual.data() + 2, actual.data(), 4);
+
+ for (size_t i = 0; i < 6; ++i)
+ EXPECT_EQ(actual[i].m_value, expected[i].m_value);
+}
diff --git a/Tests/AK/TestURL.cpp b/Tests/AK/TestURL.cpp
new file mode 100644
index 0000000000..c92ee4fc5b
--- /dev/null
+++ b/Tests/AK/TestURL.cpp
@@ -0,0 +1,202 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/URL.h>
+
+TEST_CASE(construct)
+{
+ EXPECT_EQ(URL().is_valid(), false);
+}
+
+TEST_CASE(basic)
+{
+ {
+ URL url("http://www.serenityos.org");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "http");
+ EXPECT_EQ(url.host(), "www.serenityos.org");
+ EXPECT_EQ(url.port(), 80);
+ EXPECT_EQ(url.path(), "/");
+ EXPECT_EQ(url.query(), "");
+ EXPECT_EQ(url.fragment(), "");
+ }
+ {
+ URL url("https://www.serenityos.org/index.html");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "https");
+ EXPECT_EQ(url.host(), "www.serenityos.org");
+ EXPECT_EQ(url.port(), 443);
+ EXPECT_EQ(url.path(), "/index.html");
+ EXPECT_EQ(url.query(), "");
+ EXPECT_EQ(url.fragment(), "");
+ }
+ {
+ URL url("https://localhost:1234/~anon/test/page.html");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "https");
+ EXPECT_EQ(url.host(), "localhost");
+ EXPECT_EQ(url.port(), 1234);
+ EXPECT_EQ(url.path(), "/~anon/test/page.html");
+ EXPECT_EQ(url.query(), "");
+ EXPECT_EQ(url.fragment(), "");
+ }
+ {
+ URL url("http://www.serenityos.org/index.html?#");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "http");
+ EXPECT_EQ(url.host(), "www.serenityos.org");
+ EXPECT_EQ(url.port(), 80);
+ EXPECT_EQ(url.path(), "/index.html");
+ EXPECT_EQ(url.query(), "");
+ EXPECT_EQ(url.fragment(), "");
+ }
+ {
+ URL url("http://www.serenityos.org/index.html?foo=1&bar=2");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "http");
+ EXPECT_EQ(url.host(), "www.serenityos.org");
+ EXPECT_EQ(url.port(), 80);
+ EXPECT_EQ(url.path(), "/index.html");
+ EXPECT_EQ(url.query(), "foo=1&bar=2");
+ EXPECT_EQ(url.fragment(), "");
+ }
+ {
+ URL url("http://www.serenityos.org/index.html#fragment");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "http");
+ EXPECT_EQ(url.host(), "www.serenityos.org");
+ EXPECT_EQ(url.port(), 80);
+ EXPECT_EQ(url.path(), "/index.html");
+ EXPECT_EQ(url.query(), "");
+ EXPECT_EQ(url.fragment(), "fragment");
+ }
+ {
+ URL url("http://www.serenityos.org/index.html?foo=1&bar=2&baz=/?#frag/ment?test#");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "http");
+ EXPECT_EQ(url.host(), "www.serenityos.org");
+ EXPECT_EQ(url.port(), 80);
+ EXPECT_EQ(url.path(), "/index.html");
+ EXPECT_EQ(url.query(), "foo=1&bar=2&baz=/?");
+ EXPECT_EQ(url.fragment(), "frag/ment?test#");
+ }
+}
+
+TEST_CASE(some_bad_urls)
+{
+ EXPECT_EQ(URL("http:serenityos.org").is_valid(), false);
+ EXPECT_EQ(URL("http:/serenityos.org").is_valid(), false);
+ EXPECT_EQ(URL("http//serenityos.org").is_valid(), false);
+ EXPECT_EQ(URL("http:///serenityos.org").is_valid(), false);
+ EXPECT_EQ(URL("serenityos.org").is_valid(), false);
+ EXPECT_EQ(URL("://serenityos.org").is_valid(), false);
+ EXPECT_EQ(URL("://:80").is_valid(), false);
+ EXPECT_EQ(URL("http://serenityos.org:80:80/").is_valid(), false);
+ EXPECT_EQ(URL("http://serenityos.org:80:80").is_valid(), false);
+ EXPECT_EQ(URL("http://serenityos.org:abc").is_valid(), false);
+ EXPECT_EQ(URL("http://serenityos.org:abc:80").is_valid(), false);
+ EXPECT_EQ(URL("http://serenityos.org:abc:80/").is_valid(), false);
+ EXPECT_EQ(URL("http://serenityos.org:/abc/").is_valid(), false);
+ EXPECT_EQ(URL("data:").is_valid(), false);
+ EXPECT_EQ(URL("file:").is_valid(), false);
+ EXPECT_EQ(URL("about:").is_valid(), false);
+}
+
+TEST_CASE(serialization)
+{
+ EXPECT_EQ(URL("http://www.serenityos.org/").to_string(), "http://www.serenityos.org/");
+ EXPECT_EQ(URL("http://www.serenityos.org:0/").to_string(), "http://www.serenityos.org/");
+ EXPECT_EQ(URL("http://www.serenityos.org:80/").to_string(), "http://www.serenityos.org/");
+ EXPECT_EQ(URL("http://www.serenityos.org:81/").to_string(), "http://www.serenityos.org:81/");
+ EXPECT_EQ(URL("https://www.serenityos.org:443/foo/bar.html?query#fragment").to_string(), "https://www.serenityos.org/foo/bar.html?query#fragment");
+}
+
+TEST_CASE(file_url_with_hostname)
+{
+ URL url("file://localhost/my/file");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.host(), "localhost");
+ EXPECT_EQ(url.path(), "/my/file");
+ EXPECT_EQ(url.to_string(), "file://localhost/my/file");
+}
+
+TEST_CASE(file_url_without_hostname)
+{
+ URL url("file:///my/file");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "file");
+ EXPECT_EQ(url.host(), "");
+ EXPECT_EQ(url.path(), "/my/file");
+ EXPECT_EQ(url.to_string(), "file:///my/file");
+}
+
+TEST_CASE(about_url)
+{
+ URL url("about:blank");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "about");
+ EXPECT_EQ(url.host(), "");
+ EXPECT_EQ(url.path(), "blank");
+ EXPECT_EQ(url.to_string(), "about:blank");
+}
+
+TEST_CASE(data_url)
+{
+ URL url("data:text/html,test");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "data");
+ EXPECT_EQ(url.host(), "");
+ EXPECT_EQ(url.data_mime_type(), "text/html");
+ EXPECT_EQ(url.data_payload(), "test");
+ EXPECT_EQ(url.to_string(), "data:text/html,test");
+}
+
+TEST_CASE(data_url_encoded)
+{
+ URL url("data:text/html,Hello%20friends%2C%0X%X0");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "data");
+ EXPECT_EQ(url.host(), "");
+ EXPECT_EQ(url.data_mime_type(), "text/html");
+ EXPECT_EQ(url.data_payload(), "Hello friends,%0X%X0");
+ // FIXME: Surely this should be URL-encoded again?!
+ EXPECT_EQ(url.to_string(), "data:text/html,Hello friends,%0X%X0");
+}
+
+TEST_CASE(data_url_base64_encoded)
+{
+ URL url("data:text/html;base64,test");
+ EXPECT_EQ(url.is_valid(), true);
+ EXPECT_EQ(url.protocol(), "data");
+ EXPECT_EQ(url.host(), "");
+ EXPECT_EQ(url.data_mime_type(), "text/html");
+ EXPECT_EQ(url.data_payload(), "test");
+ EXPECT_EQ(url.to_string(), "data:text/html;base64,test");
+}
+
+TEST_CASE(trailing_slash_with_complete_url)
+{
+ EXPECT_EQ(URL("http://a/b/").complete_url("c/").to_string(), "http://a/b/c/");
+ EXPECT_EQ(URL("http://a/b/").complete_url("c").to_string(), "http://a/b/c");
+ EXPECT_EQ(URL("http://a/b").complete_url("c/").to_string(), "http://a/c/");
+ EXPECT_EQ(URL("http://a/b").complete_url("c").to_string(), "http://a/c");
+}
+
+TEST_CASE(trailing_port)
+{
+ URL url("http://example.com:8086");
+ EXPECT_EQ(url.port(), 8086);
+}
+
+TEST_CASE(port_int_overflow_wrap)
+{
+ auto expected_port = 80;
+ URL url(String::formatted("http://example.com:{}/", (u32)((65536 * 1000) + expected_port)));
+ EXPECT_EQ(url.port(), expected_port);
+ EXPECT_EQ(url.is_valid(), true);
+}
diff --git a/Tests/AK/TestUtf8.cpp b/Tests/AK/TestUtf8.cpp
new file mode 100644
index 0000000000..4a3f4e8029
--- /dev/null
+++ b/Tests/AK/TestUtf8.cpp
@@ -0,0 +1,69 @@
+/*
+ * Copyright (c) 2019-2020, Sergey Bugaev <bugaevc@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/Utf8View.h>
+
+TEST_CASE(decode_ascii)
+{
+ Utf8View utf8 { "Hello World!11" };
+ EXPECT(utf8.validate());
+
+ u32 expected[] = { 72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33, 49, 49 };
+ size_t expected_size = sizeof(expected) / sizeof(expected[0]);
+
+ size_t i = 0;
+ for (u32 code_point : utf8) {
+ VERIFY(i < expected_size);
+ EXPECT_EQ(code_point, expected[i]);
+ i++;
+ }
+ EXPECT_EQ(i, expected_size);
+}
+
+TEST_CASE(decode_utf8)
+{
+ Utf8View utf8 { "Привет, мир! 😀 γειά σου κόσμος こんにちは世界" };
+ size_t valid_bytes;
+ EXPECT(utf8.validate(valid_bytes));
+ EXPECT(valid_bytes == (size_t)utf8.byte_length());
+
+ u32 expected[] = { 1055, 1088, 1080, 1074, 1077, 1090, 44, 32, 1084, 1080, 1088, 33, 32, 128512, 32, 947, 949, 953, 940, 32, 963, 959, 965, 32, 954, 972, 963, 956, 959, 962, 32, 12371, 12435, 12395, 12385, 12399, 19990, 30028 };
+ size_t expected_size = sizeof(expected) / sizeof(expected[0]);
+
+ size_t i = 0;
+ for (u32 code_point : utf8) {
+ VERIFY(i < expected_size);
+ EXPECT_EQ(code_point, expected[i]);
+ i++;
+ }
+ EXPECT_EQ(i, expected_size);
+}
+
+TEST_CASE(validate_invalid_ut8)
+{
+ size_t valid_bytes;
+ char invalid_utf8_1[] = { 42, 35, (char)182, 9, 0 };
+ Utf8View utf8_1 { invalid_utf8_1 };
+ EXPECT(!utf8_1.validate(valid_bytes));
+ EXPECT(valid_bytes == 2);
+
+ char invalid_utf8_2[] = { 42, 35, (char)208, (char)208, 0 };
+ Utf8View utf8_2 { invalid_utf8_2 };
+ EXPECT(!utf8_2.validate(valid_bytes));
+ EXPECT(valid_bytes == 2);
+
+ char invalid_utf8_3[] = { (char)208, 0 };
+ Utf8View utf8_3 { invalid_utf8_3 };
+ EXPECT(!utf8_3.validate(valid_bytes));
+ EXPECT(valid_bytes == 0);
+
+ char invalid_utf8_4[] = { (char)208, 35, 0 };
+ Utf8View utf8_4 { invalid_utf8_4 };
+ EXPECT(!utf8_4.validate(valid_bytes));
+ EXPECT(valid_bytes == 0);
+}
diff --git a/Tests/AK/TestVariant.cpp b/Tests/AK/TestVariant.cpp
new file mode 100644
index 0000000000..769cde605a
--- /dev/null
+++ b/Tests/AK/TestVariant.cpp
@@ -0,0 +1,112 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenity.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestSuite.h>
+
+#include <AK/Variant.h>
+
+TEST_CASE(basic)
+{
+ Variant<int, String> the_value { 42 };
+ EXPECT(the_value.has<int>());
+ EXPECT_EQ(the_value.get<int>(), 42);
+ the_value = String("42");
+ EXPECT(the_value.has<String>());
+ EXPECT_EQ(the_value.get<String>(), "42");
+}
+
+TEST_CASE(visit)
+{
+ bool correct = false;
+ Variant<int, String, float> the_value { 42.0f };
+ the_value.visit(
+ [&](const int&) { correct = false; },
+ [&](const String&) { correct = false; },
+ [&](const float&) { correct = true; });
+ EXPECT(correct);
+}
+
+TEST_CASE(destructor)
+{
+ struct DestructionChecker {
+ explicit DestructionChecker(bool& was_destroyed)
+ : m_was_destroyed(was_destroyed)
+ {
+ }
+
+ ~DestructionChecker()
+ {
+ m_was_destroyed = true;
+ }
+ bool& m_was_destroyed;
+ };
+
+ bool was_destroyed = false;
+ {
+ Variant<DestructionChecker> test_variant { DestructionChecker { was_destroyed } };
+ }
+ EXPECT(was_destroyed);
+}
+
+TEST_CASE(move_moves)
+{
+ struct NoCopy {
+ AK_MAKE_NONCOPYABLE(NoCopy);
+
+ public:
+ NoCopy() = default;
+ NoCopy(NoCopy&&) = default;
+ };
+
+ Variant<NoCopy, int> first_variant { 42 };
+ // Should not fail to compile
+ first_variant = NoCopy {};
+
+ Variant<NoCopy, int> second_variant = move(first_variant);
+ EXPECT(second_variant.has<NoCopy>());
+}
+
+TEST_CASE(downcast)
+{
+ Variant<i8, i16, i32, i64> one_integer_to_rule_them_all { static_cast<i32>(42) };
+ auto fake_integer = one_integer_to_rule_them_all.downcast<i8, i32>();
+ EXPECT(fake_integer.has<i32>());
+ EXPECT(one_integer_to_rule_them_all.has<i32>());
+ EXPECT_EQ(fake_integer.get<i32>(), 42);
+ EXPECT_EQ(one_integer_to_rule_them_all.get<i32>(), 42);
+
+ fake_integer = static_cast<i8>(60);
+ one_integer_to_rule_them_all = fake_integer.downcast<i8, i16>().downcast<i8, i32, float>().downcast<i8, i16, i32, i64>();
+ EXPECT(fake_integer.has<i8>());
+ EXPECT(one_integer_to_rule_them_all.has<i8>());
+ EXPECT_EQ(fake_integer.get<i8>(), 60);
+ EXPECT_EQ(one_integer_to_rule_them_all.get<i8>(), 60);
+}
+
+TEST_CASE(moved_from_state)
+{
+ // Note: This test requires that Vector's moved-from state be consistent
+ // it need not be in a specific state (though as it is currently implemented,
+ // a moved-from vector is the same as a newly-created vector)
+ // This test does not make assumptions about the state itself, but rather that
+ // it remains consistent when done on different instances.
+ // Should this assumption be broken, we should probably switch to defining a local
+ // class that has fixed semantics, but I doubt the moved-from state of Vector will
+ // change any time soon :P
+ Vector<i32> bunch_of_values { 1, 2, 3, 4, 5, 6, 7, 8 };
+ Variant<Vector<i32>, Empty> optionally_a_bunch_of_values { Vector<i32> { 1, 2, 3, 4, 5, 6, 7, 8 } };
+
+ {
+ [[maybe_unused]] auto devnull_0 = move(bunch_of_values);
+ [[maybe_unused]] auto devnull_1 = move(optionally_a_bunch_of_values);
+ }
+
+ // The moved-from state should be the same in both cases, and the variant should still contain a moved-from vector.
+ // Note: Use after move is intentional.
+ EXPECT(optionally_a_bunch_of_values.has<Vector<i32>>());
+ auto same_contents = __builtin_memcmp(&bunch_of_values, &optionally_a_bunch_of_values.get<Vector<i32>>(), sizeof(bunch_of_values)) == 0;
+ EXPECT(same_contents);
+}
diff --git a/Tests/AK/TestVector.cpp b/Tests/AK/TestVector.cpp
new file mode 100644
index 0000000000..0439a0605f
--- /dev/null
+++ b/Tests/AK/TestVector.cpp
@@ -0,0 +1,401 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/NonnullOwnPtrVector.h>
+#include <AK/OwnPtr.h>
+#include <AK/String.h>
+#include <AK/Vector.h>
+
+TEST_CASE(construct)
+{
+ EXPECT(Vector<int>().is_empty());
+ EXPECT(Vector<int>().size() == 0);
+}
+
+TEST_CASE(ints)
+{
+ Vector<int> ints;
+ ints.append(1);
+ ints.append(2);
+ ints.append(3);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(ints.take_last(), 3);
+ EXPECT_EQ(ints.size(), 2u);
+ EXPECT_EQ(ints.take_last(), 2);
+ EXPECT_EQ(ints.size(), 1u);
+ EXPECT_EQ(ints.take_last(), 1);
+ EXPECT_EQ(ints.size(), 0u);
+
+ ints.clear();
+ EXPECT_EQ(ints.size(), 0u);
+}
+
+TEST_CASE(strings)
+{
+ Vector<String> strings;
+ strings.append("ABC");
+ strings.append("DEF");
+
+ int loop_counter = 0;
+ for (const String& string : strings) {
+ EXPECT(!string.is_null());
+ EXPECT(!string.is_empty());
+ ++loop_counter;
+ }
+
+ loop_counter = 0;
+ for (auto& string : (const_cast<const Vector<String>&>(strings))) {
+ EXPECT(!string.is_null());
+ EXPECT(!string.is_empty());
+ ++loop_counter;
+ }
+ EXPECT_EQ(loop_counter, 2);
+}
+
+TEST_CASE(strings_insert_ordered)
+{
+ Vector<String> strings;
+ strings.append("abc");
+ strings.append("def");
+ strings.append("ghi");
+
+ strings.insert_before_matching("f-g", [](auto& entry) {
+ return "f-g" < entry;
+ });
+
+ EXPECT_EQ(strings[0], "abc");
+ EXPECT_EQ(strings[1], "def");
+ EXPECT_EQ(strings[2], "f-g");
+ EXPECT_EQ(strings[3], "ghi");
+}
+
+TEST_CASE(prepend_vector)
+{
+ Vector<int> ints;
+ ints.append(1);
+ ints.append(2);
+ ints.append(3);
+
+ Vector<int> more_ints;
+ more_ints.append(4);
+ more_ints.append(5);
+ more_ints.append(6);
+
+ ints.prepend(move(more_ints));
+
+ EXPECT_EQ(ints.size(), 6u);
+ EXPECT_EQ(more_ints.size(), 0u);
+
+ EXPECT_EQ(ints[0], 4);
+ EXPECT_EQ(ints[1], 5);
+ EXPECT_EQ(ints[2], 6);
+ EXPECT_EQ(ints[3], 1);
+ EXPECT_EQ(ints[4], 2);
+ EXPECT_EQ(ints[5], 3);
+
+ ints.prepend(move(more_ints));
+ EXPECT_EQ(ints.size(), 6u);
+ EXPECT_EQ(more_ints.size(), 0u);
+
+ more_ints.prepend(move(ints));
+ EXPECT_EQ(more_ints.size(), 6u);
+ EXPECT_EQ(ints.size(), 0u);
+}
+
+TEST_CASE(prepend_vector_object)
+{
+ struct SubObject {
+ SubObject(int v)
+ : value(v)
+ {
+ }
+ int value { 0 };
+ };
+ struct Object {
+ Object(NonnullOwnPtr<SubObject>&& a_subobject)
+ : subobject(move(a_subobject))
+ {
+ }
+ OwnPtr<SubObject> subobject;
+ };
+
+ Vector<Object> objects;
+ objects.empend(make<SubObject>(1));
+ objects.empend(make<SubObject>(2));
+ objects.empend(make<SubObject>(3));
+
+ EXPECT_EQ(objects.size(), 3u);
+
+ Vector<Object> more_objects;
+ more_objects.empend(make<SubObject>(4));
+ more_objects.empend(make<SubObject>(5));
+ more_objects.empend(make<SubObject>(6));
+ EXPECT_EQ(more_objects.size(), 3u);
+
+ objects.prepend(move(more_objects));
+ EXPECT_EQ(more_objects.size(), 0u);
+ EXPECT_EQ(objects.size(), 6u);
+
+ EXPECT_EQ(objects[0].subobject->value, 4);
+ EXPECT_EQ(objects[1].subobject->value, 5);
+ EXPECT_EQ(objects[2].subobject->value, 6);
+ EXPECT_EQ(objects[3].subobject->value, 1);
+ EXPECT_EQ(objects[4].subobject->value, 2);
+ EXPECT_EQ(objects[5].subobject->value, 3);
+}
+
+TEST_CASE(vector_compare)
+{
+ Vector<int> ints;
+ Vector<int> same_ints;
+
+ for (int i = 0; i < 1000; ++i) {
+ ints.append(i);
+ same_ints.append(i);
+ }
+
+ EXPECT_EQ(ints.size(), 1000u);
+ EXPECT_EQ(ints, same_ints);
+
+ Vector<String> strings;
+ Vector<String> same_strings;
+
+ for (int i = 0; i < 1000; ++i) {
+ strings.append(String::number(i));
+ same_strings.append(String::number(i));
+ }
+
+ EXPECT_EQ(strings.size(), 1000u);
+ EXPECT_EQ(strings, same_strings);
+}
+
+TEST_CASE(grow_past_inline_capacity)
+{
+ auto make_vector = [] {
+ Vector<String, 16> strings;
+ for (int i = 0; i < 32; ++i) {
+ strings.append(String::number(i));
+ }
+ return strings;
+ };
+
+ auto strings = make_vector();
+
+ EXPECT_EQ(strings.size(), 32u);
+ EXPECT_EQ(strings[31], "31");
+
+ strings.clear();
+ EXPECT_EQ(strings.size(), 0u);
+ EXPECT_EQ(strings.capacity(), 16u);
+
+ strings = make_vector();
+
+ strings.clear_with_capacity();
+ EXPECT_EQ(strings.size(), 0u);
+ EXPECT(strings.capacity() >= 32u);
+}
+
+BENCHMARK_CASE(vector_append_trivial)
+{
+ // This should be super fast thanks to Vector using memmove.
+ Vector<int> ints;
+ for (int i = 0; i < 1000000; ++i) {
+ ints.append(i);
+ }
+ for (int i = 0; i < 100; ++i) {
+ Vector<int> tmp;
+ tmp.append(ints);
+ EXPECT_EQ(tmp.size(), 1000000u);
+ }
+}
+
+BENCHMARK_CASE(vector_remove_trivial)
+{
+ // This should be super fast thanks to Vector using memmove.
+ Vector<int> ints;
+ for (int i = 0; i < 10000; ++i) {
+ ints.append(i);
+ }
+ while (!ints.is_empty()) {
+ ints.remove(0);
+ }
+ EXPECT_EQ(ints.size(), 0u);
+}
+
+TEST_CASE(vector_remove)
+{
+ Vector<int> ints;
+ ints.append(1);
+ ints.append(2);
+ ints.append(3);
+ ints.append(4);
+ ints.append(5);
+
+ ints.remove(1);
+ EXPECT_EQ(ints.size(), 4u);
+ EXPECT_EQ(ints[0], 1);
+ EXPECT_EQ(ints[1], 3);
+ EXPECT_EQ(ints[2], 4);
+ EXPECT_EQ(ints[3], 5);
+
+ ints.remove(0);
+ EXPECT_EQ(ints.size(), 3u);
+ EXPECT_EQ(ints[0], 3);
+ EXPECT_EQ(ints[1], 4);
+ EXPECT_EQ(ints[2], 5);
+
+ ints.take_last();
+ EXPECT_EQ(ints.size(), 2u);
+ EXPECT_EQ(ints[0], 3);
+ EXPECT_EQ(ints[1], 4);
+
+ ints.take_first();
+ EXPECT_EQ(ints.size(), 1u);
+ EXPECT_EQ(ints[0], 4);
+}
+
+TEST_CASE(nonnullownptrvector)
+{
+ struct Object {
+ String string;
+ };
+ NonnullOwnPtrVector<Object> objects;
+
+ objects.append(make<Object>());
+ EXPECT_EQ(objects.size(), 1u);
+
+ OwnPtr<Object> o = make<Object>();
+ objects.append(o.release_nonnull());
+ EXPECT(o == nullptr);
+ EXPECT_EQ(objects.size(), 2u);
+}
+
+TEST_CASE(insert_trivial)
+{
+ Vector<int> ints;
+ ints.append(0);
+ ints.append(10);
+ ints.append(20);
+ ints.append(30);
+ ints.append(40);
+ ints.insert(2, 15);
+ EXPECT_EQ(ints.size(), 6u);
+ EXPECT_EQ(ints[0], 0);
+ EXPECT_EQ(ints[1], 10);
+ EXPECT_EQ(ints[2], 15);
+ EXPECT_EQ(ints[3], 20);
+ EXPECT_EQ(ints[4], 30);
+ EXPECT_EQ(ints[5], 40);
+}
+
+TEST_CASE(resize_initializes)
+{
+ struct A {
+ A() { initialized = true; }
+ bool initialized { false };
+ };
+
+ Vector<A> ints;
+ ints.resize(32);
+
+ for (size_t idx = 0; idx < 32; ++idx)
+ EXPECT(ints[idx].initialized);
+}
+
+TEST_CASE(should_compare_vectors_of_same_type)
+{
+ Vector<int> a {};
+ Vector<int> b {};
+
+ EXPECT(a == b);
+ EXPECT(!(a != b));
+
+ a.append(1);
+ EXPECT(!(a == b));
+ EXPECT(a != b);
+
+ b.append(1);
+ EXPECT(a == b);
+ EXPECT(!(a != b));
+
+ a.append(42);
+ b.append(17);
+ EXPECT(!(a == b));
+ EXPECT(a != b);
+}
+
+TEST_CASE(should_compare_vectors_of_different_inline_capacity)
+{
+ Vector<int, 1> a {};
+ Vector<int, 64> b {};
+
+ EXPECT(a == b);
+ EXPECT(!(a != b));
+
+ a.append(1);
+ EXPECT(!(a == b));
+ EXPECT(a != b);
+
+ b.append(1);
+ EXPECT(a == b);
+ EXPECT(!(a != b));
+
+ a.append(42);
+ b.append(17);
+ EXPECT(!(a == b));
+ EXPECT(a != b);
+}
+
+TEST_CASE(should_compare_vectors_of_different_sizes)
+{
+ Vector<int, 0> a {};
+ Vector<int, 0> b {};
+
+ EXPECT(a == b);
+ EXPECT(!(a != b));
+
+ // A is longer
+ a.append(1);
+ EXPECT(!(a == b));
+ EXPECT(a != b);
+
+ b.append(1);
+ EXPECT(a == b);
+ EXPECT(!(a != b));
+
+ // B is longer
+ b.append(42);
+ EXPECT(!(a == b));
+ EXPECT(a != b);
+}
+
+TEST_CASE(should_find_value)
+{
+ Vector<int> v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
+
+ const auto expected = v.begin() + 4;
+
+ EXPECT_EQ(expected, v.find(0));
+}
+
+TEST_CASE(should_find_predicate)
+{
+ Vector<int> v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
+
+ const auto expected = v.begin() + 4;
+
+ EXPECT_EQ(expected, v.find_if([](const auto v) { return v == 0; }));
+}
+
+TEST_CASE(should_find_index)
+{
+ Vector<int> v { 1, 2, 3, 4, 0, 6, 7, 8, 0, 0 };
+
+ EXPECT_EQ(4u, v.find_first_index(0).value());
+ EXPECT(!v.find_first_index(42).has_value());
+}
diff --git a/Tests/AK/TestWeakPtr.cpp b/Tests/AK/TestWeakPtr.cpp
new file mode 100644
index 0000000000..8a573276cd
--- /dev/null
+++ b/Tests/AK/TestWeakPtr.cpp
@@ -0,0 +1,66 @@
+/*
+ * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <AK/String.h>
+#include <AK/WeakPtr.h>
+#include <AK/Weakable.h>
+
+#ifdef __clang__
+# pragma clang diagnostic push
+# pragma clang diagnostic ignored "-Wunused-private-field"
+#endif
+
+class SimpleWeakable : public Weakable<SimpleWeakable>
+ , public RefCounted<SimpleWeakable> {
+public:
+ SimpleWeakable() = default;
+
+private:
+ int m_member { 123 };
+};
+
+#ifdef __clang__
+# pragma clang diagnostic pop
+#endif
+
+TEST_CASE(basic_weak)
+{
+ WeakPtr<SimpleWeakable> weak1;
+ WeakPtr<SimpleWeakable> weak2;
+
+ {
+ auto simple = adopt_ref(*new SimpleWeakable);
+ weak1 = simple;
+ weak2 = simple;
+ EXPECT_EQ(weak1.is_null(), false);
+ EXPECT_EQ(weak2.is_null(), false);
+ EXPECT_EQ(weak1.strong_ref().ptr(), simple.ptr());
+ EXPECT_EQ(weak1.strong_ref().ptr(), weak2.strong_ref().ptr());
+ }
+
+ EXPECT_EQ(weak1.is_null(), true);
+ EXPECT_EQ(weak1.strong_ref().ptr(), nullptr);
+ EXPECT_EQ(weak1.strong_ref().ptr(), weak2.strong_ref().ptr());
+}
+
+TEST_CASE(weakptr_move)
+{
+ WeakPtr<SimpleWeakable> weak1;
+ WeakPtr<SimpleWeakable> weak2;
+
+ {
+ auto simple = adopt_ref(*new SimpleWeakable);
+ weak1 = simple;
+ weak2 = move(weak1);
+ EXPECT_EQ(weak1.is_null(), true);
+ EXPECT_EQ(weak2.is_null(), false);
+ EXPECT_EQ(weak2.strong_ref().ptr(), simple.ptr());
+ }
+
+ EXPECT_EQ(weak2.is_null(), true);
+}
diff --git a/Tests/AK/test.frm b/Tests/AK/test.frm
new file mode 120000
index 0000000000..b01e93f4ee
--- /dev/null
+++ b/Tests/AK/test.frm
@@ -0,0 +1 @@
+../../Base/home/anon/Source/little/test.frm \ No newline at end of file