diff options
Diffstat (limited to 'Userland')
7 files changed, 302 insertions, 20 deletions
diff --git a/Userland/Libraries/LibJS/Runtime/Map.cpp b/Userland/Libraries/LibJS/Runtime/Map.cpp index 9116b50f39..53729bcc10 100644 --- a/Userland/Libraries/LibJS/Runtime/Map.cpp +++ b/Userland/Libraries/LibJS/Runtime/Map.cpp @@ -34,7 +34,7 @@ bool Map::map_remove(Value const& key) { Optional<size_t> index; - for (auto it = m_keys.begin(); it != m_keys.end(); ++it) { + for (auto it = m_keys.begin(); !it.is_end(); ++it) { if (ValueTraits::equals(*it, key)) { index = it.key(); break; diff --git a/Userland/Libraries/LibJS/Runtime/Map.h b/Userland/Libraries/LibJS/Runtime/Map.h index 6564dd1b54..476aa7bee7 100644 --- a/Userland/Libraries/LibJS/Runtime/Map.h +++ b/Userland/Libraries/LibJS/Runtime/Map.h @@ -38,32 +38,26 @@ public: struct IteratorImpl { bool is_end() const { - if (m_index.has_value()) { - return m_map.m_keys.begin_from(*m_index).is_end() - && m_map.m_keys.find_smallest_not_below_iterator(*m_index).is_end(); - } - - // First attempt and no iteration, ask the map if it has anything. - return m_map.m_keys.is_empty(); + return m_map.m_keys.begin_from(m_index).is_end() + && m_map.m_keys.find_smallest_not_below_iterator(m_index).is_end(); } IteratorImpl& operator++() { - if (auto it = m_map.m_keys.find_smallest_not_below_iterator(ensure_index() + 1); it.is_end()) - m_index = m_map.m_next_insertion_id; - else - m_index = it.key(); + ++m_index; return *this; } decltype(auto) operator*() { - return *m_map.m_entries.find(*m_map.m_keys.begin_from(ensure_index())); + ensure_next_element(); + return *m_map.m_entries.find(*m_map.m_keys.begin_from(m_index)); } decltype(auto) operator*() const { - return *m_map.m_entries.find(*m_map.m_keys.begin_from(ensure_index())); + ensure_next_element(); + return *m_map.m_entries.find(*m_map.m_keys.begin_from(m_index)); } bool operator==(IteratorImpl const& other) const { return m_index == other.m_index && &m_map == &other.m_map; } @@ -74,24 +68,33 @@ public: IteratorImpl(Map const& map) requires(IsConst) : m_map(map) { + ensure_index(); } IteratorImpl(Map& map) requires(!IsConst) : m_map(map) { + ensure_index(); } - size_t ensure_index() + void ensure_index() const { - if (!m_index.has_value()) { - VERIFY(!m_map.m_keys.is_empty()); + if (m_map.m_keys.is_empty()) + m_index = m_map.m_next_insertion_id; + else m_index = m_map.m_keys.begin().key(); - } - return *m_index; + } + + void ensure_next_element() const + { + if (auto it = m_map.m_keys.find_smallest_not_below_iterator(m_index); it.is_end()) + m_index = m_map.m_next_insertion_id; + else + m_index = it.key(); } Conditional<IsConst, Map const&, Map&> m_map; - mutable Optional<size_t> m_index; + mutable size_t m_index { 0 }; }; using Iterator = IteratorImpl<false>; diff --git a/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.delete.js b/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.delete.js index c7d6bd9192..ac3a8d8ce2 100644 --- a/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.delete.js +++ b/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.delete.js @@ -12,3 +12,74 @@ test("basic functionality", () => { expect(map.delete("b")).toBeFalse(); expect(map).toHaveSize(2); }); + +describe("modification with active iterators", () => { + test("deleted element is skipped", () => { + const map = new Map([ + [1, 2], + [3, 4], + [5, 6], + ]); + const iterator = map.entries(); + + expect(iterator.next()).toBeIteratorResultWithValue([1, 2]); + + expect(map.delete(3)).toBeTrue(); + + expect(iterator.next()).toBeIteratorResultWithValue([5, 6]); + + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("if rest of elements is deleted skip immediately to done", () => { + const map = new Map([[-1, -1]]); + + for (let i = 1; i <= 25; ++i) map.set(i, i); + + const iterator = map.entries(); + + expect(iterator.next()).toBeIteratorResultWithValue([-1, -1]); + + for (let i = 1; i <= 25; ++i) expect(map.delete(i)).toBeTrue(); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("deleting elements which were already visited has no effect", () => { + const map = new Map([ + [1, 2], + [3, 4], + [5, 6], + ]); + + const iterator = map.entries(); + + expect(iterator.next()).toBeIteratorResultWithValue([1, 2]); + + expect(map.delete(1)).toBeTrue(); + + expect(iterator.next()).toBeIteratorResultWithValue([3, 4]); + + expect(map.delete(3)).toBeTrue(); + + expect(iterator.next()).toBeIteratorResultWithValue([5, 6]); + + expect(map.delete(5)).toBeTrue(); + expect(map.delete(7)).toBeFalse(); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("deleting the last element before the iterator visited it means you immediately get end", () => { + const map = new Map([[1, 2]]); + + const iterator = map.entries(); + + expect(map.delete(1)).toBeTrue(); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); +}); diff --git a/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.set.js b/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.set.js index c4c9a4ab07..9670815e3e 100644 --- a/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.set.js +++ b/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.set.js @@ -12,3 +12,84 @@ test("basic functionality", () => { expect(map.set("a", -1)).toBe(map); expect(map).toHaveSize(4); }); + +describe("modification with active iterators", () => { + test("added element is visited (after initial elements)", () => { + const map = new Map([ + [1, 2], + [5, 6], + ]); + const iterator = map.entries(); + + expect(iterator.next()).toBeIteratorResultWithValue([1, 2]); + + map.set(3, 4); + + expect(iterator.next()).toBeIteratorResultWithValue([5, 6]); + + expect(iterator.next()).toBeIteratorResultWithValue([3, 4]); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("entries added after iterator is done are not visited", () => { + const map = new Map([[1, 2]]); + + const iterator = map.entries(); + + expect(iterator.next()).toBeIteratorResultWithValue([1, 2]); + + expect(iterator.next()).toBeIteratorResultDone(); + + map.set(3, 4); + + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("entries which are deleted and then added are visited at the end", () => { + const map = new Map([ + [1, 2], + [3, 4], + ]); + + const iterator = map.entries(); + + expect(iterator.next()).toBeIteratorResultWithValue([1, 2]); + + expect(map.delete(1)).toBeTrue(); + map.set(1, 10); + + expect(map.delete(3)).toBeTrue(); + map.set(3, 11); + + expect(iterator.next()).toBeIteratorResultWithValue([1, 10]); + + expect(iterator.next()).toBeIteratorResultWithValue([3, 11]); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("entries which added to empty map after iterator created are still visited", () => { + const map = new Map(); + + const iteratorImmediateDone = map.entries(); + expect(iteratorImmediateDone.next()).toBeIteratorResultDone(); + + const iterator = map.entries(); + + map.set(1, 2); + + expect(iterator.next()).toBeIteratorResultWithValue([1, 2]); + + expect(map.delete(1)).toBeTrue(); + + map.set(3, 4); + + expect(iterator.next()).toBeIteratorResultWithValue([3, 4]); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); +}); diff --git a/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.values.js b/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.values.js index 8437336cd3..32028caf22 100644 --- a/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.values.js +++ b/Userland/Libraries/LibJS/Tests/builtins/Map/Map.prototype.values.js @@ -17,3 +17,62 @@ test("basic functionality", () => { expect(it.next()).toEqual({ value: undefined, done: true }); expect(it.next()).toEqual({ value: undefined, done: true }); }); + +describe("empty maps give no values", () => { + test("always empty", () => { + const map = new Map(); + const iterator = map.values(); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("just emptied map", () => { + const map = new Map([ + [1, 2], + [3, 4], + ]); + + const iterator = map.values(); + + expect(map.delete(1)).toBeTrue(); + expect(map.delete(3)).toBeTrue(); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("cleared map", () => { + const map = new Map([ + [1, 2], + [3, 4], + ]); + + const iterator = map.values(); + + map.clear(); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("added and then removed elements", () => { + const map = new Map([[1, 2]]); + + const iterator = map.values(); + + map.set(3, 4); + + map.delete(3); + map.set(5, 6); + map.delete(1); + map.set(1, 4); + map.delete(5); + map.delete(1); + + expect(map).toHaveSize(0); + + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); +}); diff --git a/Userland/Libraries/LibJS/Tests/builtins/Set/Set.prototype.add.js b/Userland/Libraries/LibJS/Tests/builtins/Set/Set.prototype.add.js index e4dbb3dc72..30f1affb7c 100644 --- a/Userland/Libraries/LibJS/Tests/builtins/Set/Set.prototype.add.js +++ b/Userland/Libraries/LibJS/Tests/builtins/Set/Set.prototype.add.js @@ -8,3 +8,31 @@ test("basic functionality", () => { expect(set.add("a")).toBe(set); expect(set).toHaveSize(4); }); + +describe("elements added after iteration start are still visited", () => { + test("element added after iterator", () => { + const set = new Set(); + const iterator = set.values(); + set.add(1); + expect(iterator.next()).toBeIteratorResultWithValue(1); + expect(iterator.next()).toBeIteratorResultDone(); + expect(iterator.next()).toBeIteratorResultDone(); + }); + + test("elements (re)added after deleting", () => { + const set = new Set(); + const iterator1 = set.values(); + set.add(1); + set.add(2); + set.clear(); + const iterator2 = set.values(); + set.add(1); + expect(iterator1.next()).toBeIteratorResultWithValue(1); + expect(iterator1.next()).toBeIteratorResultDone(); + expect(iterator1.next()).toBeIteratorResultDone(); + + expect(iterator2.next()).toBeIteratorResultWithValue(1); + expect(iterator2.next()).toBeIteratorResultDone(); + expect(iterator2.next()).toBeIteratorResultDone(); + }); +}); diff --git a/Userland/Libraries/LibJS/Tests/test-common.js b/Userland/Libraries/LibJS/Tests/test-common.js index 778fff4169..1f9e3af979 100644 --- a/Userland/Libraries/LibJS/Tests/test-common.js +++ b/Userland/Libraries/LibJS/Tests/test-common.js @@ -446,6 +446,46 @@ class ExpectationError extends Error { }); } + toBeIteratorResultWithValue(value) { + this.__expect(this.target !== undefined && this.target !== null); + this.__doMatcher(() => { + this.__expect( + this.target.done === false, + () => + `toGiveIteratorResultWithValue: expected 'done' to be _false_ got ${valueToString( + this.target.done + )}` + ); + this.__expect( + deepEquals(value, this.target.value), + () => + `toGiveIteratorResultWithValue: expected 'value' to be _${valueToString( + value + )}_ got ${valueToString(this.target.value)}` + ); + }); + } + + toBeIteratorResultDone() { + this.__expect(this.target !== undefined && this.target !== null); + this.__doMatcher(() => { + this.__expect( + this.target.done === true, + () => + `toGiveIteratorResultDone: expected 'done' to be _true_ got ${valueToString( + this.target.done + )}` + ); + this.__expect( + this.target.value === undefined, + () => + `toGiveIteratorResultDone: expected 'value' to be _undefined_ got ${valueToString( + this.target.value + )}` + ); + }); + } + __doMatcher(matcher) { if (!this.inverted) { matcher(); |