From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- js/src/jsapi-tests/testHashTable.cpp | 564 +++++++++++++++++++++++++++++++++++ 1 file changed, 564 insertions(+) create mode 100644 js/src/jsapi-tests/testHashTable.cpp (limited to 'js/src/jsapi-tests/testHashTable.cpp') diff --git a/js/src/jsapi-tests/testHashTable.cpp b/js/src/jsapi-tests/testHashTable.cpp new file mode 100644 index 0000000000..4cd55f4cba --- /dev/null +++ b/js/src/jsapi-tests/testHashTable.cpp @@ -0,0 +1,564 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "mozilla/HashFunctions.h" + +#include + +#include "ds/OrderedHashTable.h" +#include "js/HashTable.h" +#include "js/Utility.h" +#include "jsapi-tests/tests.h" + +// #define FUZZ + +typedef js::HashMap, + js::SystemAllocPolicy> + IntMap; +typedef js::HashSet, + js::SystemAllocPolicy> + IntSet; + +/* + * The rekeying test as conducted by adding only keys masked with 0x0000FFFF + * that are unique. We rekey by shifting left 16 bits. + */ +#ifdef FUZZ +const size_t TestSize = 0x0000FFFF / 2; +const size_t TestIterations = SIZE_MAX; +#else +const size_t TestSize = 10000; +const size_t TestIterations = 10; +#endif + +static_assert(TestSize <= 0x0000FFFF / 2); + +struct LowToHigh { + static uint32_t rekey(uint32_t initial) { + if (initial > uint32_t(0x0000FFFF)) { + return initial; + } + return initial << 16; + } + + static bool shouldBeRemoved(uint32_t initial) { return false; } +}; + +struct LowToHighWithRemoval { + static uint32_t rekey(uint32_t initial) { + if (initial > uint32_t(0x0000FFFF)) { + return initial; + } + return initial << 16; + } + + static bool shouldBeRemoved(uint32_t initial) { + if (initial >= 0x00010000) { + return (initial >> 16) % 2 == 0; + } + return initial % 2 == 0; + } +}; + +static bool MapsAreEqual(IntMap& am, IntMap& bm) { + bool equal = true; + if (am.count() != bm.count()) { + equal = false; + fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), + bm.count()); + } + for (auto iter = am.iter(); !iter.done(); iter.next()) { + if (!bm.has(iter.get().key())) { + equal = false; + fprintf(stderr, "B does not have %x which is in A\n", iter.get().key()); + } + } + for (auto iter = bm.iter(); !iter.done(); iter.next()) { + if (!am.has(iter.get().key())) { + equal = false; + fprintf(stderr, "A does not have %x which is in B\n", iter.get().key()); + } + } + return equal; +} + +static bool SetsAreEqual(IntSet& am, IntSet& bm) { + bool equal = true; + if (am.count() != bm.count()) { + equal = false; + fprintf(stderr, "A.count() == %u and B.count() == %u\n", am.count(), + bm.count()); + } + for (auto iter = am.iter(); !iter.done(); iter.next()) { + if (!bm.has(iter.get())) { + equal = false; + fprintf(stderr, "B does not have %x which is in A\n", iter.get()); + } + } + for (auto iter = bm.iter(); !iter.done(); iter.next()) { + if (!am.has(iter.get())) { + equal = false; + fprintf(stderr, "A does not have %x which is in B\n", iter.get()); + } + } + return equal; +} + +static bool AddLowKeys(IntMap* am, IntMap* bm, int seed) { + size_t i = 0; + srand(seed); + while (i < TestSize) { + uint32_t n = rand() & 0x0000FFFF; + if (!am->has(n)) { + if (bm->has(n)) { + return false; + } + + if (!am->putNew(n, n) || !bm->putNew(n, n)) { + return false; + } + i++; + } + } + return true; +} + +static bool AddLowKeys(IntSet* as, IntSet* bs, int seed) { + size_t i = 0; + srand(seed); + while (i < TestSize) { + uint32_t n = rand() & 0x0000FFFF; + if (!as->has(n)) { + if (bs->has(n)) { + return false; + } + if (!as->putNew(n) || !bs->putNew(n)) { + return false; + } + i++; + } + } + return true; +} + +template +static bool SlowRekey(IntMap* m) { + IntMap tmp; + + for (auto iter = m->iter(); !iter.done(); iter.next()) { + if (NewKeyFunction::shouldBeRemoved(iter.get().key())) { + continue; + } + uint32_t hi = NewKeyFunction::rekey(iter.get().key()); + if (tmp.has(hi)) { + return false; + } + if (!tmp.putNew(hi, iter.get().value())) { + return false; + } + } + + m->clear(); + for (auto iter = tmp.iter(); !iter.done(); iter.next()) { + if (!m->putNew(iter.get().key(), iter.get().value())) { + return false; + } + } + + return true; +} + +template +static bool SlowRekey(IntSet* s) { + IntSet tmp; + + for (auto iter = s->iter(); !iter.done(); iter.next()) { + if (NewKeyFunction::shouldBeRemoved(iter.get())) { + continue; + } + uint32_t hi = NewKeyFunction::rekey(iter.get()); + if (tmp.has(hi)) { + return false; + } + if (!tmp.putNew(hi)) { + return false; + } + } + + s->clear(); + for (auto iter = tmp.iter(); !iter.done(); iter.next()) { + if (!s->putNew(iter.get())) { + return false; + } + } + + return true; +} + +BEGIN_TEST(testHashRekeyManual) { + IntMap am, bm; + for (size_t i = 0; i < TestIterations; ++i) { +#ifdef FUZZ + fprintf(stderr, "map1: %lu\n", i); +#endif + CHECK(AddLowKeys(&am, &bm, i)); + CHECK(MapsAreEqual(am, bm)); + + for (auto iter = am.modIter(); !iter.done(); iter.next()) { + uint32_t tmp = LowToHigh::rekey(iter.get().key()); + if (tmp != iter.get().key()) { + iter.rekey(tmp); + } + } + CHECK(SlowRekey(&bm)); + + CHECK(MapsAreEqual(am, bm)); + am.clear(); + bm.clear(); + } + + IntSet as, bs; + for (size_t i = 0; i < TestIterations; ++i) { +#ifdef FUZZ + fprintf(stderr, "set1: %lu\n", i); +#endif + CHECK(AddLowKeys(&as, &bs, i)); + CHECK(SetsAreEqual(as, bs)); + + for (auto iter = as.modIter(); !iter.done(); iter.next()) { + uint32_t tmp = LowToHigh::rekey(iter.get()); + if (tmp != iter.get()) { + iter.rekey(tmp); + } + } + CHECK(SlowRekey(&bs)); + + CHECK(SetsAreEqual(as, bs)); + as.clear(); + bs.clear(); + } + + return true; +} +END_TEST(testHashRekeyManual) + +BEGIN_TEST(testHashRekeyManualRemoval) { + IntMap am, bm; + for (size_t i = 0; i < TestIterations; ++i) { +#ifdef FUZZ + fprintf(stderr, "map2: %lu\n", i); +#endif + CHECK(AddLowKeys(&am, &bm, i)); + CHECK(MapsAreEqual(am, bm)); + + for (auto iter = am.modIter(); !iter.done(); iter.next()) { + if (LowToHighWithRemoval::shouldBeRemoved(iter.get().key())) { + iter.remove(); + } else { + uint32_t tmp = LowToHighWithRemoval::rekey(iter.get().key()); + if (tmp != iter.get().key()) { + iter.rekey(tmp); + } + } + } + CHECK(SlowRekey(&bm)); + + CHECK(MapsAreEqual(am, bm)); + am.clear(); + bm.clear(); + } + + IntSet as, bs; + for (size_t i = 0; i < TestIterations; ++i) { +#ifdef FUZZ + fprintf(stderr, "set1: %lu\n", i); +#endif + CHECK(AddLowKeys(&as, &bs, i)); + CHECK(SetsAreEqual(as, bs)); + + for (auto iter = as.modIter(); !iter.done(); iter.next()) { + if (LowToHighWithRemoval::shouldBeRemoved(iter.get())) { + iter.remove(); + } else { + uint32_t tmp = LowToHighWithRemoval::rekey(iter.get()); + if (tmp != iter.get()) { + iter.rekey(tmp); + } + } + } + CHECK(SlowRekey(&bs)); + + CHECK(SetsAreEqual(as, bs)); + as.clear(); + bs.clear(); + } + + return true; +} +END_TEST(testHashRekeyManualRemoval) + +// A type that is not copyable, only movable. +struct MoveOnlyType { + uint32_t val; + + explicit MoveOnlyType(uint32_t val) : val(val) {} + + MoveOnlyType(MoveOnlyType&& rhs) { val = rhs.val; } + + MoveOnlyType& operator=(MoveOnlyType&& rhs) { + MOZ_ASSERT(&rhs != this); + this->~MoveOnlyType(); + new (this) MoveOnlyType(std::move(rhs)); + return *this; + } + + struct HashPolicy { + typedef MoveOnlyType Lookup; + + static js::HashNumber hash(const Lookup& lookup) { return lookup.val; } + + static bool match(const MoveOnlyType& existing, const Lookup& lookup) { + return existing.val == lookup.val; + } + }; + + private: + MoveOnlyType(const MoveOnlyType&) = delete; + MoveOnlyType& operator=(const MoveOnlyType&) = delete; +}; + +BEGIN_TEST(testHashSetOfMoveOnlyType) { + typedef js::HashSet + Set; + + Set set; + + MoveOnlyType a(1); + + CHECK(set.put(std::move(a))); // This shouldn't generate a compiler error. + + return true; +} +END_TEST(testHashSetOfMoveOnlyType) + +#if defined(DEBUG) + +// Add entries to a HashMap until either we get an OOM, or the table has been +// resized a few times. +static bool GrowUntilResize() { + IntMap m; + + // Add entries until we've resized the table four times. + size_t lastCapacity = m.capacity(); + size_t resizes = 0; + uint32_t key = 0; + while (resizes < 4) { + auto p = m.lookupForAdd(key); + if (!p && !m.add(p, key, 0)) { + return false; // OOM'd in lookupForAdd() or add() + } + + size_t capacity = m.capacity(); + if (capacity != lastCapacity) { + resizes++; + lastCapacity = capacity; + } + key++; + } + + return true; +} + +BEGIN_TEST(testHashMapGrowOOM) { + uint32_t timeToFail; + for (timeToFail = 1; timeToFail < 1000; timeToFail++) { + js::oom::simulator.simulateFailureAfter( + js::oom::FailureSimulator::Kind::OOM, timeToFail, js::THREAD_TYPE_MAIN, + false); + GrowUntilResize(); + } + + js::oom::simulator.reset(); + return true; +} + +END_TEST(testHashMapGrowOOM) +#endif // defined(DEBUG) + +BEGIN_TEST(testHashTableMovableModIterator) { + IntSet set; + + // Exercise returning a hash table ModIterator object from a function. + + CHECK(set.put(1)); + for (auto iter = setModIter(set); !iter.done(); iter.next()) { + iter.remove(); + } + CHECK(set.count() == 0); + + // Test moving an ModIterator object explicitly. + + CHECK(set.put(1)); + CHECK(set.put(2)); + CHECK(set.put(3)); + CHECK(set.count() == 3); + { + auto i1 = set.modIter(); + CHECK(!i1.done()); + i1.remove(); + i1.next(); + + auto i2 = std::move(i1); + CHECK(!i2.done()); + i2.remove(); + i2.next(); + } + + CHECK(set.count() == 1); + return true; +} + +IntSet::ModIterator setModIter(IntSet& set) { return set.modIter(); } + +END_TEST(testHashTableMovableModIterator) + +BEGIN_TEST(testHashLazyStorage) { + // The following code depends on the current capacity computation, which + // could change in the future. + uint32_t defaultCap = 32; + uint32_t minCap = 4; + + IntSet set; + CHECK(set.capacity() == 0); + + CHECK(set.put(1)); + CHECK(set.capacity() == defaultCap); + + set.compact(); // effectively a no-op + CHECK(set.capacity() == minCap); + + set.clear(); + CHECK(set.capacity() == minCap); + + set.compact(); + CHECK(set.capacity() == 0); + + CHECK(set.putNew(1)); + CHECK(set.capacity() == minCap); + + set.clear(); + set.compact(); + CHECK(set.capacity() == 0); + + auto p = set.lookupForAdd(1); + CHECK(set.capacity() == 0); + CHECK(set.add(p, 1)); + CHECK(set.capacity() == minCap); + CHECK(set.has(1)); + + set.clear(); + set.compact(); + CHECK(set.capacity() == 0); + + p = set.lookupForAdd(1); + CHECK(set.putNew(2)); + CHECK(set.capacity() == minCap); + CHECK(set.relookupOrAdd(p, 1, 1)); + CHECK(set.capacity() == minCap); + CHECK(set.has(1)); + + set.clear(); + set.compact(); + CHECK(set.capacity() == 0); + + CHECK(set.putNew(1)); + p = set.lookupForAdd(1); + set.clear(); + set.compact(); + CHECK(set.count() == 0); + CHECK(set.relookupOrAdd(p, 1, 1)); + CHECK(set.count() == 1); + CHECK(set.capacity() == minCap); + + set.clear(); + set.compact(); + CHECK(set.capacity() == 0); + + CHECK(set.reserve(0)); // a no-op + CHECK(set.capacity() == 0); + + CHECK(set.reserve(1)); + CHECK(set.capacity() == minCap); + + CHECK(set.reserve(0)); // a no-op + CHECK(set.capacity() == minCap); + + CHECK(set.reserve(2)); // effectively a no-op + CHECK(set.capacity() == minCap); + + // No need to clear here because we didn't add anything. + set.compact(); + CHECK(set.capacity() == 0); + + CHECK(set.reserve(128)); + CHECK(set.capacity() == 256); + CHECK(set.reserve(3)); // effectively a no-op + CHECK(set.capacity() == 256); + for (int i = 0; i < 8; i++) { + CHECK(set.putNew(i)); + } + CHECK(set.count() == 8); + CHECK(set.capacity() == 256); + set.compact(); + CHECK(set.capacity() == 16); + set.compact(); // effectively a no-op + CHECK(set.capacity() == 16); + for (int i = 8; i < 16; i++) { + CHECK(set.putNew(i)); + } + CHECK(set.count() == 16); + CHECK(set.capacity() == 32); + set.clear(); + CHECK(set.capacity() == 32); + set.compact(); + CHECK(set.capacity() == 0); + + // Lowest length for which reserve() will fail. + static const uint32_t toobig = (1 << 29) + 1; + CHECK(!set.reserve(toobig)); + CHECK(set.capacity() == 0); // unchanged + CHECK(set.reserve(16)); + CHECK(set.capacity() == 32); + + return true; +} +END_TEST(testHashLazyStorage) + +BEGIN_TEST(testOrderedHashSetWithoutInit) { + { + struct NonzeroUint32HashPolicy { + using Lookup = uint32_t; + static js::HashNumber hash(const Lookup& v, + const mozilla::HashCodeScrambler& hcs) { + return mozilla::HashGeneric(v); + } + static bool match(const uint32_t& k, const Lookup& l) { return k == l; } + static bool isEmpty(const uint32_t& v) { return v == 0; } + static void makeEmpty(uint32_t* v) { *v = 0; } + }; + + using OHS = js::OrderedHashSet; + + OHS set(js::SystemAllocPolicy(), mozilla::HashCodeScrambler(17, 42)); + CHECK(set.count() == 0); + + // This test passes if the set is safely destructible even when |init()| is + // never called. + } + + return true; +} +END_TEST(testOrderedHashSetWithoutInit) -- cgit v1.2.3