AK: Clear OrderedHashTable previous/next pointers on removal

With Clang, the previous/next pointers in buckets of an
`OrderedHashTable` are not cleared when a bucket is being shifted up as
a result of a removed bucket. As a result, an unfortunate pointer mixup
could lead to an infinite loop in the `HashTable` iterator, which was
exposed in `HashMap::keys()`.

Co-authored-by: Luke Wilde <lukew@serenityos.org>

2 files changed, 28 insertions, 0 deletions

diff --git a/AK/HashTable.h b/AK/HashTable.h
index 9ac8c9d507..a3a59560b5 100644
--- a/AK/HashTable.h
+++ b/AK/HashTable.h
@@ -690,6 +690,10 @@ private:
 
             auto* shift_to_bucket = &m_buckets[shift_to_index];
             *shift_to_bucket = move(*shift_from_bucket);
+            if constexpr (IsOrdered) {
+                shift_from_bucket->previous = nullptr;
+                shift_from_bucket->next = nullptr;
+            }
             shift_to_bucket->state = bucket_state_for_probe_length(shift_from_probe_length - 1);
             update_bucket_neighbours(shift_to_bucket);
 
diff --git a/Tests/AK/TestHashTable.cpp b/Tests/AK/TestHashTable.cpp
index 97b7cb0ae7..9d25c48739 100644
--- a/Tests/AK/TestHashTable.cpp
+++ b/Tests/AK/TestHashTable.cpp
@@ -410,3 +410,27 @@ TEST_CASE(ordered_remove_from_head)
 
     EXPECT_EQ(map.size(), 0u);
 }
+
+TEST_CASE(ordered_infinite_loop_clang_regression)
+{
+    OrderedHashTable<DeprecatedString> map;
+    map.set("");
+    map.set("1");
+    map.set("_cb");
+    map.set("2");
+    map.set("3");
+    map.set("_cb_svref");
+    map.set("_cb_svref_expires");
+    map.remove("_cb_svref");
+    map.remove("_cb_svref_expires");
+    map.set("_cb_svref");
+
+    size_t iterations = 0;
+    auto size = map.size();
+    for (auto it = map.begin(); it != map.end(); ++it) {
+        if (++iterations > size) {
+            VERIFY(false);
+            break;
+        }
+    }
+}