Source code
Revision control
Copy as Markdown
Other Tools
/* 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
#include <algorithm>
#include <iterator>
#include "gtest/gtest.h"
#include "mozilla/ReverseIterator.h"
#include "mozilla/dom/ECMACollections.h"
#include "nsHashKeys.h"
#include "nsISupportsImpl.h"
#include "nsString.h"
using mozilla::dom::ECMAMap;
using mozilla::dom::ECMASet;
using mozilla::dom::binding_detail::ECMAStorable;
static_assert(ECMAStorable<int>::value);
static_assert(ECMAStorable<nsString>::value);
static_assert(!ECMAStorable<JS::Value>::value);
static_assert(!ECMAStorable<JSObject*>::value);
static_assert(!ECMAStorable<JSString*>::value);
static_assert(!ECMAStorable<JS::Heap<JS::Value>>::value);
static_assert(!ECMAStorable<JS::Heap<JSObject*>>::value);
// The collections under test, with the length of their entry array (live
// entries plus tombstones) exposed so that tests can observe compaction.
template <typename T, typename... HashKey>
class TestSet : public ECMASet<T, HashKey...> {
public:
uint32_t PhysicalLength() const { return this->mEntries.Length(); }
};
template <typename K, typename V, typename... HashKey>
class TestMap : public ECMAMap<K, V, HashKey...> {
public:
uint32_t PhysicalLength() const { return this->mEntries.Length(); }
};
// ==========================================================================
// ECMASet -- basic operations
// ==========================================================================
TEST(ECMASet, EmptySet)
{
TestSet<int> set;
EXPECT_EQ(set.Size(), 0u);
EXPECT_TRUE(set.IsEmpty());
EXPECT_FALSE(set.Has(42));
}
TEST(ECMASet, AddAndHas)
{
TestSet<int> set;
EXPECT_TRUE(set.Add(1));
EXPECT_TRUE(set.Add(2));
EXPECT_TRUE(set.Add(3));
EXPECT_EQ(set.Size(), 3u);
EXPECT_TRUE(set.Has(1));
EXPECT_TRUE(set.Has(2));
EXPECT_TRUE(set.Has(3));
EXPECT_FALSE(set.Has(4));
}
TEST(ECMASet, AddDuplicate)
{
TestSet<int> set;
EXPECT_TRUE(set.Add(1));
EXPECT_FALSE(set.Add(1));
EXPECT_EQ(set.Size(), 1u);
}
TEST(ECMASet, Delete)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
EXPECT_TRUE(set.Delete(2));
EXPECT_EQ(set.Size(), 2u);
EXPECT_TRUE(set.Has(1));
EXPECT_FALSE(set.Has(2));
EXPECT_TRUE(set.Has(3));
}
TEST(ECMASet, DeleteNonExistent)
{
TestSet<int> set;
set.Add(1);
EXPECT_FALSE(set.Delete(99));
EXPECT_EQ(set.Size(), 1u);
}
TEST(ECMASet, DeleteAll)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Delete(1);
set.Delete(2);
EXPECT_EQ(set.Size(), 0u);
EXPECT_TRUE(set.IsEmpty());
EXPECT_FALSE(set.Has(1));
EXPECT_FALSE(set.Has(2));
}
TEST(ECMASet, DeleteTwice)
{
TestSet<int> set;
set.Add(1);
EXPECT_TRUE(set.Delete(1));
EXPECT_FALSE(set.Delete(1));
EXPECT_EQ(set.Size(), 0u);
}
TEST(ECMASet, Clear)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Clear();
EXPECT_EQ(set.Size(), 0u);
EXPECT_TRUE(set.IsEmpty());
EXPECT_FALSE(set.Has(1));
}
TEST(ECMASet, DoubleClear)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Clear();
EXPECT_EQ(set.Size(), 0u);
set.Clear();
EXPECT_EQ(set.Size(), 0u);
}
TEST(ECMASet, ReAddAfterDelete)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Delete(1);
EXPECT_TRUE(set.Add(1));
EXPECT_EQ(set.Size(), 2u);
EXPECT_TRUE(set.Has(1));
}
TEST(ECMASet, ReAddAfterClear)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Clear();
EXPECT_TRUE(set.Add(3));
EXPECT_EQ(set.Size(), 1u);
EXPECT_TRUE(set.Has(3));
EXPECT_FALSE(set.Has(1));
}
// ==========================================================================
// ECMASet -- insertion-order iteration
// ==========================================================================
TEST(ECMASet, InsertionOrder)
{
TestSet<int> set;
set.Add(30);
set.Add(10);
set.Add(20);
nsTArray<int> result;
for (const auto& val : set) {
result.AppendElement(val);
}
ASSERT_EQ(result.Length(), 3u);
EXPECT_EQ(result[0], 30);
EXPECT_EQ(result[1], 10);
EXPECT_EQ(result[2], 20);
}
TEST(ECMASet, IterationSkipsTombstones)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Add(4);
set.Delete(2);
set.Delete(3);
nsTArray<int> result;
for (const auto& val : set) {
result.AppendElement(val);
}
ASSERT_EQ(result.Length(), 2u);
EXPECT_EQ(result[0], 1);
EXPECT_EQ(result[1], 4);
}
TEST(ECMASet, ReAddAppearsAtEnd)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Delete(2);
set.Add(2);
nsTArray<int> result;
for (const auto& val : set) {
result.AppendElement(val);
}
ASSERT_EQ(result.Length(), 3u);
EXPECT_EQ(result[0], 1);
EXPECT_EQ(result[1], 3);
EXPECT_EQ(result[2], 2);
}
// ==========================================================================
// ECMASet -- Cursor (for WebIDL codegen)
// ==========================================================================
TEST(ECMASet, CursorSkipsTombstones)
{
TestSet<int> set;
set.Add(10);
set.Add(20);
set.Add(30);
set.Delete(20);
auto cursor = set.CreateCursor();
nsTArray<int> result;
while (const auto* entry = cursor.Next()) {
result.AppendElement(entry->mValue);
}
ASSERT_EQ(result.Length(), 2u);
EXPECT_EQ(result[0], 10);
EXPECT_EQ(result[1], 30);
}
// ==========================================================================
// ECMASet -- compaction
// ==========================================================================
TEST(ECMASet, CompactionHappensWhenTombstonesExceedLive)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
for (int i = 0; i < 8; i++) {
set.Delete(i);
}
EXPECT_EQ(set.Size(), 2u);
EXPECT_LT(set.PhysicalLength(), 10u);
nsTArray<int> result;
for (const auto& val : set) {
result.AppendElement(val);
}
ASSERT_EQ(result.Length(), 2u);
EXPECT_EQ(result[0], 8);
EXPECT_EQ(result[1], 9);
}
TEST(ECMASet, ClearCompacts)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Clear();
EXPECT_EQ(set.PhysicalLength(), 0u);
EXPECT_EQ(set.Size(), 0u);
}
// ==========================================================================
// ECMASet -- compaction under live iterators
//
// Compaction reclaims tombstoned memory while iterators are alive; the
// collection moves their cursors so they resume at the same logical position.
// ==========================================================================
TEST(ECMASet, CompactionProceedsUnderLiveIterator)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto it = set.begin();
EXPECT_EQ(*it, 0);
for (int i = 1; i < 10; i++) {
set.Delete(i);
}
// The tombstones are reclaimed even though the iteration is unfinished.
EXPECT_EQ(set.PhysicalLength(), 1u);
EXPECT_EQ(set.Size(), 1u);
// Not even the entry the iterator yielded last is pinned.
set.Delete(0);
EXPECT_EQ(set.PhysicalLength(), 0u);
++it;
EXPECT_TRUE(it == set.end());
}
TEST(ECMASet, CompactionUnderLiveIteratorYieldsRemainingEntries)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto it = set.begin();
EXPECT_EQ(*it, 0);
++it;
EXPECT_EQ(*it, 1);
for (int i = 2; i < 8; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
EXPECT_EQ(set.Size(), 4u);
nsTArray<int> rest;
for (++it; it != set.end(); ++it) {
rest.AppendElement(*it);
}
ASSERT_EQ(rest.Length(), 2u);
EXPECT_EQ(rest[0], 8);
EXPECT_EQ(rest[1], 9);
}
TEST(ECMASet, TwoLiveIteratorsResumeAfterCompaction)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto first = set.begin();
++first;
auto second = set.begin();
++second;
++second;
++second;
EXPECT_EQ(*first, 1);
EXPECT_EQ(*second, 3);
for (int i = 4; i < 10; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
nsTArray<int> fromFirst;
for (++first; first != set.end(); ++first) {
fromFirst.AppendElement(*first);
}
ASSERT_EQ(fromFirst.Length(), 2u);
EXPECT_EQ(fromFirst[0], 2);
EXPECT_EQ(fromFirst[1], 3);
++second;
EXPECT_TRUE(second == set.end());
}
TEST(ECMASet, TwoIteratorsAtSamePositionResumeAfterCompaction)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto first = set.begin();
auto second = set.begin();
EXPECT_EQ(*first, 0);
EXPECT_EQ(*second, 0);
for (int i = 4; i < 10; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
nsTArray<int> fromFirst;
for (++first; first != set.end(); ++first) {
fromFirst.AppendElement(*first);
}
nsTArray<int> fromSecond;
for (++second; second != set.end(); ++second) {
fromSecond.AppendElement(*second);
}
ASSERT_EQ(fromFirst.Length(), 3u);
EXPECT_EQ(fromFirst[0], 1);
EXPECT_EQ(fromFirst[2], 3);
ASSERT_EQ(fromSecond.Length(), fromFirst.Length());
for (size_t i = 0; i < fromFirst.Length(); i++) {
EXPECT_EQ(fromSecond[i], fromFirst[i]);
}
}
TEST(ECMASet, ReverseIteratorResumesAfterCompaction)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto it = set.rbegin();
EXPECT_EQ(*it, 9);
++it;
EXPECT_EQ(*it, 8);
for (int i = 0; i < 6; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
nsTArray<int> rest;
for (++it; it != set.rend(); ++it) {
rest.AppendElement(*it);
}
ASSERT_EQ(rest.Length(), 2u);
EXPECT_EQ(rest[0], 7);
EXPECT_EQ(rest[1], 6);
}
TEST(ECMASet, ReverseCursorOnFirstTombstoneFinishes)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto it = set.rbegin();
while (*it != 1) {
++it;
}
// The next entry the iterator would examine is the tombstone at index 0.
set.Delete(0);
for (int i = 2; i < 7; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
++it;
EXPECT_TRUE(it == set.rend());
}
TEST(ECMASet, CopiedIteratorResumesAfterCompaction)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto it = set.begin();
++it;
auto copy = it;
EXPECT_TRUE(copy == it);
EXPECT_EQ(*copy, 1);
for (int i = 2; i < 8; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
++it;
EXPECT_FALSE(copy == it);
++copy;
EXPECT_TRUE(copy == it);
EXPECT_EQ(*it, 8);
EXPECT_EQ(*copy, 8);
}
TEST(ECMASet, DeleteCurrentEntryResumesAtNextEntry)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto it = set.begin();
EXPECT_EQ(*it, 0);
// The entry the iterator sits on is deleted, and the following deletes
// compact the survivors underneath it.
for (int i = 0; i < 6; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
nsTArray<int> rest;
for (++it; it != set.end(); ++it) {
rest.AppendElement(*it);
}
ASSERT_EQ(rest.Length(), 4u);
EXPECT_EQ(rest[0], 6);
EXPECT_EQ(rest[1], 7);
EXPECT_EQ(rest[2], 8);
EXPECT_EQ(rest[3], 9);
}
TEST(ECMASet, DeleteEveryEntryWhileIteratingYieldsAll)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
nsTArray<int> seen;
for (auto it = set.begin(); it != set.end(); ++it) {
const int value = *it;
seen.AppendElement(value);
ASSERT_LT(seen.Length(), 20u);
set.Delete(value);
}
ASSERT_EQ(seen.Length(), 10u);
for (size_t i = 0; i < seen.Length(); i++) {
EXPECT_EQ(seen[i], static_cast<int>(i));
}
EXPECT_EQ(set.PhysicalLength(), 0u);
EXPECT_TRUE(set.IsEmpty());
}
TEST(ECMASet, ReverseDeleteCurrentEntryResumesAtPreviousEntry)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
auto it = set.rbegin();
EXPECT_EQ(*it, 9);
set.Delete(9);
for (int i = 0; i < 5; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
nsTArray<int> rest;
for (++it; it != set.rend(); ++it) {
rest.AppendElement(*it);
}
ASSERT_EQ(rest.Length(), 4u);
EXPECT_EQ(rest[0], 8);
EXPECT_EQ(rest[1], 7);
EXPECT_EQ(rest[2], 6);
EXPECT_EQ(rest[3], 5);
}
TEST(ECMASet, MultipleLiveIteratorsDoNotSuppressCompaction)
{
TestSet<int> set;
for (int i = 0; i < 8; i++) {
set.Add(i);
}
auto first = set.begin();
auto second = set.begin();
++second;
auto third = set.begin();
++third;
++third;
for (int i = 3; i < 8; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 3u);
EXPECT_EQ(set.Size(), 3u);
++first;
++second;
++third;
EXPECT_EQ(*first, 1);
EXPECT_EQ(*second, 2);
EXPECT_TRUE(third == set.end());
}
TEST(ECMASet, ClearUnderLiveIteratorReclaims)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
auto it = set.begin();
EXPECT_EQ(*it, 1);
set.Clear();
EXPECT_EQ(set.PhysicalLength(), 0u);
EXPECT_EQ(set.Size(), 0u);
// Like an ES iterator, it goes on to the entries added after the clear.
set.Add(4);
EXPECT_EQ(set.PhysicalLength(), 1u);
++it;
ASSERT_TRUE(it != set.end());
EXPECT_EQ(*it, 4);
++it;
EXPECT_TRUE(it == set.end());
}
TEST(ECMASet, UnlinkUnderLiveIterator)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
auto it = set.begin();
EXPECT_EQ(*it, 1);
set.Unlink();
EXPECT_EQ(set.PhysicalLength(), 0u);
EXPECT_EQ(set.Size(), 0u);
// The detached cursor terminates instead of reading the discarded entries.
++it;
EXPECT_TRUE(it == set.end());
}
TEST(ECMASet, LongLivedIteratorDoesNotPinTombstones)
{
TestSet<int> set;
for (int i = 0; i < 4; i++) {
set.Add(i);
}
auto it = set.begin();
for (int i = 0; i < 200; i++) {
set.Add(100 + i);
EXPECT_LE(set.PhysicalLength(), 2 * set.Size() + 2);
set.Delete(100 + i);
EXPECT_LE(set.PhysicalLength(), 2 * set.Size() + 2);
}
EXPECT_EQ(set.Size(), 4u);
EXPECT_EQ(set.PhysicalLength(), 4u);
nsTArray<int> rest;
for (++it; it != set.end(); ++it) {
rest.AppendElement(*it);
}
ASSERT_EQ(rest.Length(), 3u);
EXPECT_EQ(rest[0], 1);
EXPECT_EQ(rest[2], 3);
}
TEST(ECMASet, RangeForSurvivesCompaction)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
nsTArray<int> seen;
for (const auto& val : set) {
const int value = val;
seen.AppendElement(value);
if (value == 1) {
for (int i = 2; i < 8; i++) {
set.Delete(i);
}
EXPECT_EQ(set.PhysicalLength(), 4u);
}
}
ASSERT_EQ(seen.Length(), 4u);
EXPECT_EQ(seen[0], 0);
EXPECT_EQ(seen[1], 1);
EXPECT_EQ(seen[2], 8);
EXPECT_EQ(seen[3], 9);
}
// ==========================================================================
// ECMASet -- string keys and move semantics
// ==========================================================================
TEST(ECMASet, StringKeys)
{
TestSet<nsString> set;
set.Add(u"hello"_ns);
set.Add(u"world"_ns);
EXPECT_TRUE(set.Has(u"hello"_ns));
EXPECT_FALSE(set.Has(u"missing"_ns));
EXPECT_EQ(set.Size(), 2u);
}
TEST(ECMASet, MoveAdd)
{
TestSet<nsString> set;
nsString str(u"hello"_ns);
set.Add(std::move(str));
EXPECT_TRUE(str.IsEmpty());
EXPECT_TRUE(set.Has(u"hello"_ns));
EXPECT_EQ(set.Size(), 1u);
}
TEST(ECMASet, MoveAddDuplicateDoesNotConsume)
{
TestSet<nsString> set;
set.Add(u"hello"_ns);
nsString str(u"hello"_ns);
EXPECT_FALSE(set.Add(std::move(str)));
// Value not consumed on duplicate.
EXPECT_FALSE(str.IsEmpty());
}
// ==========================================================================
// ECMAMap -- basic operations
// ==========================================================================
TEST(ECMAMap, EmptyMap)
{
TestMap<int, int> map;
EXPECT_EQ(map.Size(), 0u);
EXPECT_TRUE(map.IsEmpty());
EXPECT_FALSE(map.Has(1));
EXPECT_EQ(map.Get(1), nullptr);
}
TEST(ECMAMap, SetAndGet)
{
TestMap<int, int> map;
EXPECT_TRUE(map.Set(1, 100));
EXPECT_TRUE(map.Set(2, 200));
EXPECT_EQ(map.Size(), 2u);
ASSERT_NE(map.Get(1), nullptr);
EXPECT_EQ(*map.Get(1), 100);
ASSERT_NE(map.Get(2), nullptr);
EXPECT_EQ(*map.Get(2), 200);
EXPECT_EQ(map.Get(3), nullptr);
}
TEST(ECMAMap, ConstGet)
{
TestMap<int, int> map;
map.Set(1, 100);
const auto& constMap = map;
const int* val = constMap.Get(1);
ASSERT_NE(val, nullptr);
EXPECT_EQ(*val, 100);
EXPECT_EQ(constMap.Get(2), nullptr);
}
TEST(ECMAMap, SetUpdatesValueInPlace)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
EXPECT_FALSE(map.Set(1, 999));
EXPECT_EQ(map.Size(), 2u);
EXPECT_EQ(*map.Get(1), 999);
}
TEST(ECMAMap, SetUpdatePreservesInsertionOrder)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
map.Set(1, 999);
nsTArray<int> keys;
for (const auto& entry : map) {
keys.AppendElement(entry.mKey);
}
ASSERT_EQ(keys.Length(), 3u);
EXPECT_EQ(keys[0], 1);
EXPECT_EQ(keys[1], 2);
EXPECT_EQ(keys[2], 3);
}
TEST(ECMAMap, Delete)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
EXPECT_TRUE(map.Delete(2));
EXPECT_EQ(map.Size(), 2u);
EXPECT_FALSE(map.Has(2));
EXPECT_EQ(map.Get(2), nullptr);
EXPECT_TRUE(map.Has(1));
EXPECT_TRUE(map.Has(3));
}
TEST(ECMAMap, DeleteNonExistent)
{
TestMap<int, int> map;
map.Set(1, 100);
EXPECT_FALSE(map.Delete(99));
EXPECT_EQ(map.Size(), 1u);
}
TEST(ECMAMap, DeleteTwice)
{
TestMap<int, int> map;
map.Set(1, 100);
EXPECT_TRUE(map.Delete(1));
EXPECT_FALSE(map.Delete(1));
EXPECT_EQ(map.Size(), 0u);
EXPECT_EQ(map.Get(1), nullptr);
}
TEST(ECMAMap, Clear)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Clear();
EXPECT_EQ(map.Size(), 0u);
EXPECT_FALSE(map.Has(1));
}
TEST(ECMAMap, DoubleClear)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Clear();
EXPECT_EQ(map.Size(), 0u);
map.Clear();
EXPECT_EQ(map.Size(), 0u);
}
TEST(ECMAMap, GetReturnsNullAfterDelete)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Delete(1);
EXPECT_EQ(map.Get(1), nullptr);
ASSERT_NE(map.Get(2), nullptr);
EXPECT_EQ(*map.Get(2), 200);
}
TEST(ECMAMap, ReAddAfterDelete)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Delete(1);
EXPECT_TRUE(map.Set(1, 999));
EXPECT_EQ(map.Size(), 2u);
EXPECT_EQ(*map.Get(1), 999);
}
// ==========================================================================
// ECMAMap -- insertion-order iteration
// ==========================================================================
TEST(ECMAMap, InsertionOrder)
{
TestMap<int, int> map;
map.Set(30, 300);
map.Set(10, 100);
map.Set(20, 200);
nsTArray<int> keys;
nsTArray<int> values;
for (auto iter = map.begin(); iter != map.end(); ++iter) {
keys.AppendElement(iter->mKey);
values.AppendElement(iter->mValue);
}
ASSERT_EQ(keys.Length(), 3u);
EXPECT_EQ(keys[0], 30);
EXPECT_EQ(keys[1], 10);
EXPECT_EQ(keys[2], 20);
EXPECT_EQ(values[0], 300);
EXPECT_EQ(values[1], 100);
EXPECT_EQ(values[2], 200);
}
TEST(ECMAMap, IterationSkipsTombstones)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
map.Set(4, 400);
map.Delete(2);
map.Delete(3);
nsTArray<int> keys;
for (const auto& entry : map) {
keys.AppendElement(entry.mKey);
}
ASSERT_EQ(keys.Length(), 2u);
EXPECT_EQ(keys[0], 1);
EXPECT_EQ(keys[1], 4);
}
TEST(ECMAMap, ReAddAppearsAtEnd)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
map.Delete(2);
map.Set(2, 999);
nsTArray<int> keys;
for (const auto& entry : map) {
keys.AppendElement(entry.mKey);
}
ASSERT_EQ(keys.Length(), 3u);
EXPECT_EQ(keys[0], 1);
EXPECT_EQ(keys[1], 3);
EXPECT_EQ(keys[2], 2);
}
// ==========================================================================
// ECMAMap -- Cursor
// ==========================================================================
TEST(ECMAMap, CursorSkipsTombstones)
{
TestMap<int, int> map;
map.Set(10, 100);
map.Set(20, 200);
map.Set(30, 300);
map.Delete(20);
auto cursor = map.CreateCursor();
nsTArray<int> keys;
while (const auto* entry = cursor.Next()) {
keys.AppendElement(entry->mKey);
}
ASSERT_EQ(keys.Length(), 2u);
EXPECT_EQ(keys[0], 10);
EXPECT_EQ(keys[1], 30);
}
// ==========================================================================
// ECMAMap -- compaction
// ==========================================================================
TEST(ECMAMap, CompactionHappensWhenTombstonesExceedLive)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 100);
}
for (int i = 0; i < 8; i++) {
map.Delete(i);
}
EXPECT_EQ(map.Size(), 2u);
EXPECT_LT(map.PhysicalLength(), 10u);
EXPECT_EQ(*map.Get(8), 800);
EXPECT_EQ(*map.Get(9), 900);
}
TEST(ECMAMap, ClearCompacts)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
map.Clear();
EXPECT_EQ(map.PhysicalLength(), 0u);
EXPECT_EQ(map.Size(), 0u);
}
// ==========================================================================
// ECMAMap -- compaction under live iterators
// ==========================================================================
TEST(ECMAMap, CompactionProceedsUnderLiveIterator)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 100);
}
auto it = map.begin();
EXPECT_EQ(it->mKey, 0);
for (int i = 1; i < 10; i++) {
map.Delete(i);
}
EXPECT_EQ(map.PhysicalLength(), 1u);
EXPECT_EQ(map.Size(), 1u);
map.Delete(0);
EXPECT_EQ(map.PhysicalLength(), 0u);
++it;
EXPECT_TRUE(it == map.end());
}
TEST(ECMAMap, CompactionUnderLiveIteratorYieldsRemainingEntries)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 100);
}
auto it = map.begin();
EXPECT_EQ(it->mKey, 0);
++it;
EXPECT_EQ(it->mKey, 1);
for (int i = 2; i < 8; i++) {
map.Delete(i);
}
EXPECT_EQ(map.PhysicalLength(), 4u);
EXPECT_EQ(map.Size(), 4u);
nsTArray<int> keys;
nsTArray<int> values;
for (++it; it != map.end(); ++it) {
keys.AppendElement(it->mKey);
values.AppendElement(it->mValue);
}
ASSERT_EQ(keys.Length(), 2u);
EXPECT_EQ(keys[0], 8);
EXPECT_EQ(keys[1], 9);
EXPECT_EQ(values[0], 800);
EXPECT_EQ(values[1], 900);
}
TEST(ECMAMap, TwoLiveIteratorsResumeAfterCompaction)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 100);
}
auto first = map.begin();
++first;
auto second = map.begin();
++second;
++second;
++second;
EXPECT_EQ(first->mKey, 1);
EXPECT_EQ(second->mKey, 3);
for (int i = 4; i < 10; i++) {
map.Delete(i);
}
EXPECT_EQ(map.PhysicalLength(), 4u);
nsTArray<int> fromFirst;
for (++first; first != map.end(); ++first) {
fromFirst.AppendElement(first->mKey);
}
ASSERT_EQ(fromFirst.Length(), 2u);
EXPECT_EQ(fromFirst[0], 2);
EXPECT_EQ(fromFirst[1], 3);
++second;
EXPECT_TRUE(second == map.end());
}
TEST(ECMAMap, TwoIteratorsAtSamePositionResumeAfterCompaction)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 100);
}
auto first = map.begin();
auto second = map.begin();
EXPECT_EQ(first->mKey, 0);
EXPECT_EQ(second->mKey, 0);
for (int i = 4; i < 10; i++) {
map.Delete(i);
}
EXPECT_EQ(map.PhysicalLength(), 4u);
nsTArray<int> fromFirst;
for (++first; first != map.end(); ++first) {
fromFirst.AppendElement(first->mKey);
}
nsTArray<int> fromSecond;
for (++second; second != map.end(); ++second) {
fromSecond.AppendElement(second->mKey);
}
ASSERT_EQ(fromFirst.Length(), 3u);
EXPECT_EQ(fromFirst[0], 1);
EXPECT_EQ(fromFirst[2], 3);
ASSERT_EQ(fromSecond.Length(), fromFirst.Length());
for (size_t i = 0; i < fromFirst.Length(); i++) {
EXPECT_EQ(fromSecond[i], fromFirst[i]);
}
}
TEST(ECMAMap, ReverseIteratorResumesAfterCompaction)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 100);
}
auto it = map.rbegin();
EXPECT_EQ(it->mKey, 9);
++it;
EXPECT_EQ(it->mKey, 8);
for (int i = 0; i < 6; i++) {
map.Delete(i);
}
EXPECT_EQ(map.PhysicalLength(), 4u);
nsTArray<int> keys;
for (++it; it != map.rend(); ++it) {
keys.AppendElement(it->mKey);
}
ASSERT_EQ(keys.Length(), 2u);
EXPECT_EQ(keys[0], 7);
EXPECT_EQ(keys[1], 6);
}
TEST(ECMAMap, DeleteCurrentEntryResumesAtNextEntry)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 100);
}
auto it = map.begin();
EXPECT_EQ(it->mKey, 0);
for (int i = 0; i < 6; i++) {
map.Delete(i);
}
EXPECT_EQ(map.PhysicalLength(), 4u);
nsTArray<int> keys;
nsTArray<int> values;
for (++it; it != map.end(); ++it) {
keys.AppendElement(it->mKey);
values.AppendElement(it->mValue);
}
ASSERT_EQ(keys.Length(), 4u);
EXPECT_EQ(keys[0], 6);
EXPECT_EQ(keys[3], 9);
EXPECT_EQ(values[0], 600);
EXPECT_EQ(values[3], 900);
}
TEST(ECMAMap, ReverseDeleteCurrentEntryResumesAtPreviousEntry)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 100);
}
auto it = map.rbegin();
EXPECT_EQ(it->mKey, 9);
map.Delete(9);
for (int i = 0; i < 5; i++) {
map.Delete(i);
}
EXPECT_EQ(map.PhysicalLength(), 4u);
nsTArray<int> keys;
for (++it; it != map.rend(); ++it) {
keys.AppendElement(it->mKey);
}
ASSERT_EQ(keys.Length(), 4u);
EXPECT_EQ(keys[0], 8);
EXPECT_EQ(keys[1], 7);
EXPECT_EQ(keys[2], 6);
EXPECT_EQ(keys[3], 5);
}
TEST(ECMAMap, ClearUnderLiveIteratorReclaims)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
auto it = map.begin();
EXPECT_EQ(it->mKey, 1);
map.Clear();
EXPECT_EQ(map.PhysicalLength(), 0u);
EXPECT_EQ(map.Size(), 0u);
// Like an ES iterator, it goes on to the entries added after the clear.
map.Set(4, 400);
EXPECT_EQ(map.PhysicalLength(), 1u);
++it;
ASSERT_TRUE(it != map.end());
EXPECT_EQ(it->mKey, 4);
++it;
EXPECT_TRUE(it == map.end());
}
TEST(ECMAMap, LongLivedIteratorDoesNotPinTombstones)
{
TestMap<int, int> map;
for (int i = 0; i < 4; i++) {
map.Set(i, i * 100);
}
auto it = map.begin();
for (int i = 0; i < 200; i++) {
map.Set(100 + i, i);
EXPECT_LE(map.PhysicalLength(), 2 * map.Size() + 2);
map.Delete(100 + i);
EXPECT_LE(map.PhysicalLength(), 2 * map.Size() + 2);
}
EXPECT_EQ(map.Size(), 4u);
EXPECT_EQ(map.PhysicalLength(), 4u);
nsTArray<int> rest;
for (++it; it != map.end(); ++it) {
rest.AppendElement(it->mKey);
}
ASSERT_EQ(rest.Length(), 3u);
EXPECT_EQ(rest[0], 1);
EXPECT_EQ(rest[2], 3);
}
// ==========================================================================
// ECMAMap -- string keys and move semantics
// ==========================================================================
TEST(ECMAMap, StringKeys)
{
TestMap<nsString, int, nsStringHashKey> map;
map.Set(u"hello"_ns, 1);
map.Set(u"world"_ns, 2);
EXPECT_TRUE(map.Has(u"hello"_ns));
EXPECT_FALSE(map.Has(u"missing"_ns));
ASSERT_NE(map.Get(u"hello"_ns), nullptr);
EXPECT_EQ(*map.Get(u"hello"_ns), 1);
}
TEST(ECMAMap, MoveSet)
{
TestMap<nsString, nsString, nsStringHashKey> map;
nsString key(u"key"_ns);
nsString val(u"value"_ns);
map.Set(std::move(key), std::move(val));
EXPECT_TRUE(key.IsEmpty());
EXPECT_TRUE(val.IsEmpty());
EXPECT_TRUE(map.Has(u"key"_ns));
EXPECT_EQ(*map.Get(u"key"_ns), u"value"_ns);
}
TEST(ECMAMap, MoveSetUpdateDoesNotConsumeKey)
{
TestMap<nsString, nsString, nsStringHashKey> map;
map.Set(u"key"_ns, u"old"_ns);
nsString key(u"key"_ns);
nsString val(u"new"_ns);
EXPECT_FALSE(map.Set(std::move(key), std::move(val)));
// Key not consumed on update (only value is moved).
EXPECT_FALSE(key.IsEmpty());
EXPECT_TRUE(val.IsEmpty());
EXPECT_EQ(*map.Get(u"key"_ns), u"new"_ns);
}
// ==========================================================================
// ECMAMap -- RefPtr value unwrapping
// ==========================================================================
class TestRefCounted final {
public:
NS_INLINE_DECL_REFCOUNTING(TestRefCounted)
explicit TestRefCounted(int aValue) : mValue(aValue) {}
int mValue;
private:
~TestRefCounted() = default;
};
// ==========================================================================
// ECMASet -- mutation during iteration (ECMA-262 iterator semantics)
// ==========================================================================
// ECMA-262 sec-set.prototype.delete: deleting an entry ahead of the cursor
// must cause the iterator to skip it.
TEST(ECMASet, DeleteAheadDuringIteration)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Add(4);
auto cursor = set.CreateCursor();
nsTArray<int> seen;
while (const auto* entry = cursor.Next()) {
seen.AppendElement(entry->mValue);
if (seen.LastElement() == 1) {
// Delete the two entries the cursor has not reached yet.
set.Delete(2);
set.Delete(3);
}
}
ASSERT_EQ(seen.Length(), 2u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(seen[1], 4);
}
// ECMA-262 sec-set.prototype.add: adding an entry during iteration appends
// it to the end, and the iterator must visit it.
TEST(ECMASet, AddDuringIteration)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
auto cursor = set.CreateCursor();
nsTArray<int> seen;
while (const auto* entry = cursor.Next()) {
seen.AppendElement(entry->mValue);
if (seen.LastElement() == 2) {
set.Add(3);
}
}
ASSERT_EQ(seen.Length(), 3u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(seen[1], 2);
EXPECT_EQ(seen[2], 3);
}
// ECMA-262 sec-set.prototype.clear: "The existing [[SetData]] List is
// preserved because there may be existing Set Iterator objects that are
// suspended midway through iterating over that List."
// The iterator must see no more live entries and must terminate.
TEST(ECMASet, ClearDuringIteration)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
auto cursor = set.CreateCursor();
nsTArray<int> seen;
while (const auto* entry = cursor.Next()) {
seen.AppendElement(entry->mValue);
if (seen.LastElement() == 1) {
set.Clear();
}
}
ASSERT_EQ(seen.Length(), 1u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(set.PhysicalLength(), 0u);
}
// Delete-then-re-add during iteration: the re-added entry appears at the end
// and is visited exactly once, at its new position.
TEST(ECMASet, DeleteAndReAddDuringIteration)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
auto cursor = set.CreateCursor();
nsTArray<int> seen;
while (const auto* entry = cursor.Next()) {
seen.AppendElement(entry->mValue);
if (seen.LastElement() == 1) {
set.Delete(2);
set.Add(2);
}
}
ASSERT_EQ(seen.Length(), 3u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(seen[1], 3);
EXPECT_EQ(seen[2], 2);
}
// Adding and deleting on every step, which also drives compaction: every
// entry that is live when the cursor reaches it is yielded exactly once, and
// the iteration terminates.
TEST(ECMASet, EachEntryYieldedOnceUnderChurn)
{
TestSet<int> set;
for (int i = 0; i < 6; i++) {
set.Add(i);
}
auto cursor = set.CreateCursor();
nsTArray<int> seen;
uint32_t mutations = 0;
while (const auto* entry = cursor.Next()) {
const int value = entry->mValue;
seen.AppendElement(value);
ASSERT_LT(seen.Length(), 20u);
if (mutations++ < 3) {
set.Delete(value + 1);
set.Add(100 + value);
}
}
ASSERT_EQ(seen.Length(), 6u);
EXPECT_EQ(seen[0], 0);
EXPECT_EQ(seen[1], 2);
EXPECT_EQ(seen[2], 4);
EXPECT_EQ(seen[3], 100);
EXPECT_EQ(seen[4], 102);
EXPECT_EQ(seen[5], 104);
}
// ==========================================================================
// ECMASet -- mutation during C++ range-for (ConstIterator)
// ==========================================================================
TEST(ECMASet, DeleteDuringRangeFor)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Add(4);
nsTArray<int> seen;
for (const auto& val : set) {
seen.AppendElement(val);
if (val == 1) {
// Delete ahead — 2 should be skipped, 3 and 4 still visited.
set.Delete(2);
}
}
ASSERT_EQ(seen.Length(), 3u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(seen[1], 3);
EXPECT_EQ(seen[2], 4);
}
TEST(ECMASet, AddDuringExplicitForLoop)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
nsTArray<int> seen;
for (auto it = set.begin(); it != set.end(); ++it) {
seen.AppendElement(*it);
if (*it == 2) {
set.Add(3);
}
}
ASSERT_EQ(seen.Length(), 3u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(seen[1], 2);
EXPECT_EQ(seen[2], 3);
}
TEST(ECMASet, AddDuringRangeFor)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
nsTArray<int> seen;
for (const auto& val : set) {
seen.AppendElement(val);
if (val == 2) {
set.Add(3);
}
}
ASSERT_EQ(seen.Length(), 3u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(seen[1], 2);
EXPECT_EQ(seen[2], 3);
}
// ==========================================================================
// ECMAMap -- mutation during iteration (ECMA-262 iterator semantics)
// ==========================================================================
TEST(ECMAMap, DeleteAheadDuringIteration)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
map.Set(4, 400);
auto cursor = map.CreateCursor();
nsTArray<int> seen;
while (const auto* entry = cursor.Next()) {
seen.AppendElement(entry->mKey);
if (seen.LastElement() == 1) {
map.Delete(2);
map.Delete(3);
}
}
ASSERT_EQ(seen.Length(), 2u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(seen[1], 4);
}
TEST(ECMAMap, SetNewKeyDuringIteration)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
auto cursor = map.CreateCursor();
nsTArray<int> keys;
while (const auto* entry = cursor.Next()) {
keys.AppendElement(entry->mKey);
if (keys.LastElement() == 2) {
map.Set(3, 300);
}
}
ASSERT_EQ(keys.Length(), 3u);
EXPECT_EQ(keys[0], 1);
EXPECT_EQ(keys[1], 2);
EXPECT_EQ(keys[2], 3);
}
TEST(ECMAMap, SetExistingKeyDuringIteration)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
auto cursor = map.CreateCursor();
nsTArray<int> keys;
nsTArray<int> values;
while (const auto* entry = cursor.Next()) {
keys.AppendElement(entry->mKey);
values.AppendElement(entry->mValue);
if (keys.LastElement() == 1) {
// Updating an existing key must not change iteration order or count.
map.Set(2, 999);
}
}
ASSERT_EQ(keys.Length(), 3u);
EXPECT_EQ(keys[0], 1);
EXPECT_EQ(keys[1], 2);
EXPECT_EQ(keys[2], 3);
EXPECT_EQ(values[1], 999);
}
TEST(ECMAMap, ClearDuringIteration)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
auto cursor = map.CreateCursor();
nsTArray<int> keys;
while (const auto* entry = cursor.Next()) {
keys.AppendElement(entry->mKey);
if (keys.LastElement() == 1) {
map.Clear();
}
}
ASSERT_EQ(keys.Length(), 1u);
EXPECT_EQ(keys[0], 1);
EXPECT_EQ(map.PhysicalLength(), 0u);
}
TEST(ECMAMap, DeleteAndReAddDuringIteration)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
auto cursor = map.CreateCursor();
nsTArray<int> keys;
nsTArray<int> values;
while (const auto* entry = cursor.Next()) {
keys.AppendElement(entry->mKey);
values.AppendElement(entry->mValue);
if (keys.LastElement() == 1) {
map.Delete(2);
map.Set(2, 999);
}
}
ASSERT_EQ(keys.Length(), 3u);
EXPECT_EQ(keys[0], 1);
EXPECT_EQ(keys[1], 3);
EXPECT_EQ(keys[2], 2);
EXPECT_EQ(values[2], 999);
}
TEST(ECMAMap, EachEntryYieldedOnceUnderChurn)
{
TestMap<int, int> map;
for (int i = 0; i < 6; i++) {
map.Set(i, i * 100);
}
auto cursor = map.CreateCursor();
nsTArray<int> keys;
uint32_t mutations = 0;
while (const auto* entry = cursor.Next()) {
const int key = entry->mKey;
keys.AppendElement(key);
ASSERT_LT(keys.Length(), 20u);
if (mutations++ < 3) {
map.Delete(key + 1);
map.Set(100 + key, key);
}
}
ASSERT_EQ(keys.Length(), 6u);
EXPECT_EQ(keys[0], 0);
EXPECT_EQ(keys[1], 2);
EXPECT_EQ(keys[2], 4);
EXPECT_EQ(keys[3], 100);
EXPECT_EQ(keys[4], 102);
EXPECT_EQ(keys[5], 104);
}
// ==========================================================================
// ECMAMap -- mutation during C++ range-for (ConstIterator)
// ==========================================================================
TEST(ECMAMap, DeleteDuringRangeFor)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
map.Set(4, 400);
nsTArray<int> seen;
for (const auto& entry : map) {
const int key = entry.mKey;
seen.AppendElement(key);
if (key == 1) {
map.Delete(2);
}
}
ASSERT_EQ(seen.Length(), 3u);
EXPECT_EQ(seen[0], 1);
EXPECT_EQ(seen[1], 3);
EXPECT_EQ(seen[2], 4);
}
// Its destructor sets an entry in the map that held the last reference to it.
class ReentrantValue final {
public:
NS_INLINE_DECL_REFCOUNTING(ReentrantValue)
explicit ReentrantValue(TestMap<int, RefPtr<ReentrantValue>>* aMap)
: mMap(aMap) {}
private:
~ReentrantValue() {
if (mMap) {
mMap->Set(-1, mozilla::MakeRefPtr<ReentrantValue>(nullptr));
}
}
TestMap<int, RefPtr<ReentrantValue>>* mMap;
};
TEST(ECMAMap, DeleteReleasesValueAfterMutation)
{
TestMap<int, RefPtr<ReentrantValue>> map;
map.Set(1, mozilla::MakeRefPtr<ReentrantValue>(&map));
EXPECT_TRUE(map.Delete(1));
EXPECT_FALSE(map.Has(1));
EXPECT_TRUE(map.Has(-1));
EXPECT_EQ(map.Size(), 1u);
}
TEST(ECMAMap, ClearReleasesValuesAfterMutation)
{
TestMap<int, RefPtr<ReentrantValue>> map;
map.Set(1, mozilla::MakeRefPtr<ReentrantValue>(&map));
map.Set(2, mozilla::MakeRefPtr<ReentrantValue>(nullptr));
map.Clear();
EXPECT_TRUE(map.Has(-1));
EXPECT_EQ(map.Size(), 1u);
}
TEST(ECMAMap, SetReleasesReplacedValueAfterMutation)
{
TestMap<int, RefPtr<ReentrantValue>> map;
map.Set(1, mozilla::MakeRefPtr<ReentrantValue>(&map));
EXPECT_FALSE(map.Set(1, mozilla::MakeRefPtr<ReentrantValue>(nullptr)));
EXPECT_TRUE(map.Has(-1));
EXPECT_EQ(map.Size(), 2u);
}
TEST(ECMAMap, SetNewKeyDuringExplicitForLoop)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
nsTArray<int> keys;
for (auto it = map.begin(); it != map.end(); ++it) {
const int key = it->mKey;
keys.AppendElement(key);
if (key == 2) {
map.Set(3, 300);
}
}
ASSERT_EQ(keys.Length(), 3u);
EXPECT_EQ(keys[0], 1);
EXPECT_EQ(keys[1], 2);
EXPECT_EQ(keys[2], 3);
}
// ==========================================================================
// ECMAMap -- RefPtr value unwrapping
// ==========================================================================
TEST(ECMAMap, GetReturnsRawPointerForRefPtrValues)
{
TestMap<int, RefPtr<TestRefCounted>> map;
auto obj = mozilla::MakeRefPtr<TestRefCounted>(42);
TestRefCounted* raw = obj.get();
map.Set(1, obj);
// Get() returns TestRefCounted*, not RefPtr<TestRefCounted>*.
TestRefCounted* result = map.Get(1);
ASSERT_NE(result, nullptr);
EXPECT_EQ(result, raw);
EXPECT_EQ(result->mValue, 42);
EXPECT_EQ(map.Get(2), nullptr);
}
TEST(ECMAMap, ConstGetReturnsRawPointerForRefPtrValues)
{
TestMap<int, RefPtr<TestRefCounted>> map;
map.Set(1, mozilla::MakeRefPtr<TestRefCounted>(99));
const auto& constMap = map;
TestRefCounted* result = constMap.Get(1);
ASSERT_NE(result, nullptr);
EXPECT_EQ(result->mValue, 99);
}
// ==========================================================================
// Lookup types: entries are looked up by the hash key's KeyType, so a stored
// nsString is found by any nsAString and a stored RefPtr<T> by a raw T*.
// ==========================================================================
TEST(ECMASet, StringKeysLookUpBySubstring)
{
TestSet<nsString> set;
set.Add(u"hello"_ns);
set.Add(u"world"_ns);
const nsAString& hello = Substring(u"say hello"_ns, 4);
const nsAString& missing = nsDependentString(u"missing");
EXPECT_TRUE(set.Has(hello));
EXPECT_FALSE(set.Has(missing));
EXPECT_TRUE(set.Delete(hello));
EXPECT_FALSE(set.Has(hello));
EXPECT_EQ(set.Size(), 1u);
}
TEST(ECMAMap, StringKeysLookUpBySubstring)
{
TestMap<nsString, int> map;
map.Set(u"hello"_ns, 1);
const nsAString& hello = Substring(u"say hello"_ns, 4);
EXPECT_TRUE(map.Has(hello));
ASSERT_NE(map.Get(hello), nullptr);
EXPECT_EQ(*map.Get(hello), 1);
EXPECT_TRUE(map.Delete(hello));
EXPECT_EQ(map.Get(hello), nullptr);
}
TEST(ECMASet, RefPtrKeysLookUpByRawPointer)
{
TestSet<RefPtr<TestRefCounted>> set;
auto first = mozilla::MakeRefPtr<TestRefCounted>(1);
auto second = mozilla::MakeRefPtr<TestRefCounted>(2);
set.Add(first);
set.Add(second);
TestRefCounted* raw = first.get();
EXPECT_TRUE(set.Has(raw));
EXPECT_TRUE(set.Has(second));
EXPECT_TRUE(set.Delete(raw));
EXPECT_FALSE(set.Has(raw));
EXPECT_EQ(set.Size(), 1u);
}
TEST(ECMAMap, RefPtrKeysLookUpByRawPointer)
{
TestMap<RefPtr<TestRefCounted>, int> map;
auto key = mozilla::MakeRefPtr<TestRefCounted>(1);
map.Set(key, 100);
TestRefCounted* raw = key.get();
EXPECT_TRUE(map.Has(raw));
ASSERT_NE(map.Get(raw), nullptr);
EXPECT_EQ(*map.Get(raw), 100);
EXPECT_TRUE(map.Delete(raw));
EXPECT_EQ(map.Get(raw), nullptr);
}
// ==========================================================================
// Binding argument types: the collections also take what the generated
// bindings pass, a U& for a stored RefPtr<U> and a substring for a stored
// nsString.
// ==========================================================================
TEST(ECMASet, RefPtrKeysTakeReferences)
{
TestSet<RefPtr<TestRefCounted>> set;
auto obj = mozilla::MakeRefPtr<TestRefCounted>(1);
TestRefCounted& ref = *obj;
EXPECT_TRUE(set.Add(ref));
EXPECT_FALSE(set.Add(ref));
EXPECT_TRUE(set.Has(ref));
EXPECT_TRUE(set.Delete(ref));
EXPECT_FALSE(set.Has(ref));
}
TEST(ECMASet, StringKeysAddSubstring)
{
TestSet<nsString> set;
const nsAString& hello = Substring(u"say hello"_ns, 4);
EXPECT_TRUE(set.Add(hello));
EXPECT_FALSE(set.Add(hello));
EXPECT_TRUE(set.Has(u"hello"_ns));
EXPECT_EQ(*set.begin(), u"hello"_ns);
}
TEST(ECMAMap, RefPtrKeysAndValuesTakeReferences)
{
TestMap<RefPtr<TestRefCounted>, RefPtr<TestRefCounted>> map;
auto key = mozilla::MakeRefPtr<TestRefCounted>(1);
auto first = mozilla::MakeRefPtr<TestRefCounted>(2);
auto second = mozilla::MakeRefPtr<TestRefCounted>(3);
EXPECT_TRUE(map.Set(*key, *first));
EXPECT_FALSE(map.Set(*key, *second));
EXPECT_TRUE(map.Has(*key));
EXPECT_EQ(map.Get(*key), second.get());
EXPECT_TRUE(map.Delete(*key));
EXPECT_EQ(map.Get(*key), nullptr);
}
TEST(ECMAMap, StringKeysSetSubstring)
{
TestMap<nsString, RefPtr<TestRefCounted>> map;
auto value = mozilla::MakeRefPtr<TestRefCounted>(1);
const nsAString& hello = Substring(u"say hello"_ns, 4);
EXPECT_TRUE(map.Set(hello, *value));
EXPECT_EQ(map.Get(u"hello"_ns), value.get());
}
// ==========================================================================
// Cursors
// ==========================================================================
TEST(ECMASet, CopiedCursorContinuesIndependently)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
auto cursor = set.CreateCursor();
EXPECT_EQ(cursor.Next()->mValue, 1);
auto copy = cursor;
EXPECT_EQ(cursor.Next()->mValue, 2);
EXPECT_EQ(cursor.Next()->mValue, 3);
EXPECT_EQ(cursor.Next(), nullptr);
EXPECT_EQ(copy.Next()->mValue, 2);
}
TEST(ECMASet, ReverseCursor)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Delete(2);
auto cursor = set.CreateReverseCursor();
EXPECT_EQ(cursor.Next()->mValue, 3);
EXPECT_EQ(cursor.Next()->mValue, 1);
EXPECT_EQ(cursor.Next(), nullptr);
}
TEST(ECMAMap, CursorEndsOnUnlink)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
auto cursor = map.CreateCursor();
EXPECT_EQ(cursor.Next()->mKey, 1);
map.Unlink();
EXPECT_EQ(cursor.Next(), nullptr);
}
// ==========================================================================
// Standard container behaviour
// ==========================================================================
TEST(ECMASet, WorksWithStandardAlgorithms)
{
TestSet<int> set;
for (int i = 0; i < 5; i++) {
set.Add(i * 10);
}
set.Delete(20);
auto found = std::find_if(set.begin(), set.end(),
[](int aValue) { return aValue > 15; });
ASSERT_TRUE(found != set.end());
EXPECT_EQ(*found, 30);
EXPECT_EQ(std::distance(set.begin(), set.end()), 4);
EXPECT_EQ(*std::max_element(set.begin(), set.end()), 40);
EXPECT_EQ(std::count_if(set.begin(), set.end(),
[](int aValue) { return aValue % 20 == 0; }),
2);
}
TEST(ECMAMap, WorksWithStandardAlgorithms)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
auto found = std::find_if(map.begin(), map.end(), [](const auto& aEntry) {
return aEntry.mValue == 200;
});
ASSERT_TRUE(found != map.end());
EXPECT_EQ(found->mKey, 2);
EXPECT_EQ(std::distance(map.rbegin(), map.rend()), 3);
}
TEST(ECMASet, IteratorCopyAssignmentAndPostIncrement)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
auto it = set.begin();
auto old = it++;
EXPECT_EQ(*old, 1);
EXPECT_EQ(*it, 2);
old = it;
EXPECT_TRUE(old == it);
++it;
EXPECT_FALSE(old == it);
EXPECT_EQ(*old, 2);
EXPECT_EQ(*it, 3);
it = set.end();
EXPECT_TRUE(it == set.end());
EXPECT_EQ(*old, 2);
}
TEST(ECMASet, IteratorEquality)
{
TestSet<int> set;
EXPECT_TRUE(set.begin() == set.end());
EXPECT_TRUE(set.rbegin() == set.rend());
set.Add(1);
set.Add(2);
EXPECT_TRUE(set.begin() == set.begin());
EXPECT_TRUE(set.end() == set.end());
EXPECT_TRUE(set.begin() != set.end());
EXPECT_TRUE(++set.begin() != set.begin());
}
// ==========================================================================
// ECMASet -- reverse iteration
// ==========================================================================
TEST(ECMASet, ReverseInsertionOrder)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
nsTArray<int> result;
for (auto it = set.rbegin(); it != set.rend(); ++it) {
result.AppendElement(*it);
}
ASSERT_EQ(result.Length(), 3u);
EXPECT_EQ(result[0], 3);
EXPECT_EQ(result[1], 2);
EXPECT_EQ(result[2], 1);
}
TEST(ECMASet, ReverseEmptySet)
{
TestSet<int> set;
EXPECT_EQ(set.rbegin(), set.rend());
// Iteration over empty set visits nothing.
int count = 0;
for (auto it = set.rbegin(); it != set.rend(); ++it) {
count++;
}
EXPECT_EQ(count, 0);
}
TEST(ECMASet, ReverseSingleElement)
{
TestSet<int> set;
set.Add(42);
nsTArray<int> result;
for (auto it = set.rbegin(); it != set.rend(); ++it) {
result.AppendElement(*it);
}
ASSERT_EQ(result.Length(), 1u);
EXPECT_EQ(result[0], 42);
}
TEST(ECMASet, ReverseSkipsTombstones)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Add(4);
set.Delete(1);
set.Delete(3);
nsTArray<int> result;
for (auto it = set.rbegin(); it != set.rend(); ++it) {
result.AppendElement(*it);
}
ASSERT_EQ(result.Length(), 2u);
EXPECT_EQ(result[0], 4);
EXPECT_EQ(result[1], 2);
}
TEST(ECMASet, ReverseAllTombstoned)
{
TestSet<int> set;
set.Add(1);
set.Add(2);
set.Add(3);
set.Delete(1);
set.Delete(2);
set.Delete(3);
EXPECT_EQ(set.PhysicalLength(), 0u);
int count = 0;
for (auto it = set.rbegin(); it != set.rend(); ++it) {
count++;
}
EXPECT_EQ(count, 0);
}
TEST(ECMASet, ForwardAndReverseYieldSameElements)
{
TestSet<int> set;
for (int i = 0; i < 10; i++) {
set.Add(i);
}
set.Delete(3);
set.Delete(7);
nsTArray<int> fwd;
for (const auto& val : set) {
fwd.AppendElement(val);
}
nsTArray<int> rev;
for (auto it = set.rbegin(); it != set.rend(); ++it) {
rev.AppendElement(*it);
}
ASSERT_EQ(fwd.Length(), rev.Length());
for (size_t i = 0; i < fwd.Length(); i++) {
EXPECT_EQ(fwd[i], rev[rev.Length() - 1 - i]);
}
}
// ==========================================================================
// ECMAMap -- reverse iteration
// ==========================================================================
TEST(ECMAMap, ReverseInsertionOrder)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
nsTArray<int> keys;
nsTArray<int> values;
for (auto it = map.rbegin(); it != map.rend(); ++it) {
keys.AppendElement(it->mKey);
values.AppendElement(it->mValue);
}
ASSERT_EQ(keys.Length(), 3u);
EXPECT_EQ(keys[0], 3);
EXPECT_EQ(keys[1], 2);
EXPECT_EQ(keys[2], 1);
EXPECT_EQ(values[0], 300);
EXPECT_EQ(values[1], 200);
EXPECT_EQ(values[2], 100);
}
// mozilla::Reversed copies the iterators it is given.
TEST(ECMAMap, ReversedRange)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
map.Delete(2);
nsTArray<int> keys;
for (const auto& [key, value] : mozilla::Reversed(map)) {
EXPECT_EQ(value, key * 100);
keys.AppendElement(key);
}
ASSERT_EQ(keys.Length(), 2u);
EXPECT_EQ(keys[0], 3);
EXPECT_EQ(keys[1], 1);
}
TEST(ECMAMap, ReverseEmptyMap)
{
TestMap<int, int> map;
EXPECT_EQ(map.rbegin(), map.rend());
int count = 0;
for (auto it = map.rbegin(); it != map.rend(); ++it) {
count++;
}
EXPECT_EQ(count, 0);
}
TEST(ECMAMap, ReverseSkipsTombstones)
{
TestMap<int, int> map;
map.Set(1, 100);
map.Set(2, 200);
map.Set(3, 300);
map.Set(4, 400);
map.Delete(1);
map.Delete(3);
nsTArray<int> keys;
for (auto it = map.rbegin(); it != map.rend(); ++it) {
keys.AppendElement(it->mKey);
}
ASSERT_EQ(keys.Length(), 2u);
EXPECT_EQ(keys[0], 4);
EXPECT_EQ(keys[1], 2);
}
TEST(ECMAMap, ForwardAndReverseYieldSameElements)
{
TestMap<int, int> map;
for (int i = 0; i < 10; i++) {
map.Set(i, i * 10);
}
map.Delete(3);
map.Delete(7);
nsTArray<int> fwd;
for (const auto& entry : map) {
fwd.AppendElement(entry.mKey);
}
nsTArray<int> rev;
for (auto it = map.rbegin(); it != map.rend(); ++it) {
rev.AppendElement(it->mKey);
}
ASSERT_EQ(fwd.Length(), rev.Length());
for (size_t i = 0; i < fwd.Length(); i++) {
EXPECT_EQ(fwd[i], rev[rev.Length() - 1 - i]);
}
}