LibJS: Add the SetIterator built-in and Set.prototype.{values, entries}

While this implementation should be complete it is based on HashTable's
iterator, which currently follows bucket-order instead of the required
insertion order. This can be simply fixed by replacing the underlying
HashTable member in Set with an enhanced one that maintains a linked
list in insertion order.

10 files changed, 209 insertions, 0 deletions

diff --git a/Userland/Libraries/LibJS/CMakeLists.txt b/Userland/Libraries/LibJS/CMakeLists.txt
index 5dc140c1c4..1b81a75e9a 100644
--- a/Userland/Libraries/LibJS/CMakeLists.txt
+++ b/Userland/Libraries/LibJS/CMakeLists.txt
@@ -78,6 +78,8 @@ set(SOURCES
     Runtime/ScriptFunction.cpp
     Runtime/Set.cpp
     Runtime/SetConstructor.cpp
+    Runtime/SetIterator.cpp
+    Runtime/SetIteratorPrototype.cpp
     Runtime/SetPrototype.cpp
     Runtime/Shape.cpp
     Runtime/StringConstructor.cpp
diff --git a/Userland/Libraries/LibJS/Forward.h b/Userland/Libraries/LibJS/Forward.h
index fe57b02706..c6e1a96405 100644
--- a/Userland/Libraries/LibJS/Forward.h
+++ b/Userland/Libraries/LibJS/Forward.h
@@ -69,6 +69,7 @@
 #define JS_ENUMERATE_ITERATOR_PROTOTYPES          \
     __JS_ENUMERATE(Iterator, iterator)            \
     __JS_ENUMERATE(ArrayIterator, array_iterator) \
+    __JS_ENUMERATE(SetIterator, set_iterator)     \
     __JS_ENUMERATE(StringIterator, string_iterator)
 
 #define JS_ENUMERATE_BUILTIN_TYPES \
diff --git a/Userland/Libraries/LibJS/Runtime/GlobalObject.cpp b/Userland/Libraries/LibJS/Runtime/GlobalObject.cpp
index 40d0461282..f168a11d24 100644
--- a/Userland/Libraries/LibJS/Runtime/GlobalObject.cpp
+++ b/Userland/Libraries/LibJS/Runtime/GlobalObject.cpp
@@ -48,6 +48,7 @@
 #include <LibJS/Runtime/RegExpConstructor.h>
 #include <LibJS/Runtime/RegExpPrototype.h>
 #include <LibJS/Runtime/SetConstructor.h>
+#include <LibJS/Runtime/SetIteratorPrototype.h>
 #include <LibJS/Runtime/SetPrototype.h>
 #include <LibJS/Runtime/Shape.h>
 #include <LibJS/Runtime/StringConstructor.h>
diff --git a/Userland/Libraries/LibJS/Runtime/SetIterator.cpp b/Userland/Libraries/LibJS/Runtime/SetIterator.cpp
new file mode 100644
index 0000000000..588e32877c
--- /dev/null
+++ b/Userland/Libraries/LibJS/Runtime/SetIterator.cpp
@@ -0,0 +1,35 @@
+/*
+ * Copyright (c) 2021, Idan Horowitz <idan.horowitz@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibJS/Runtime/GlobalObject.h>
+#include <LibJS/Runtime/SetIterator.h>
+
+namespace JS {
+
+SetIterator* SetIterator::create(GlobalObject& global_object, Set& set, Object::PropertyKind iteration_kind)
+{
+    return global_object.heap().allocate<SetIterator>(global_object, *global_object.set_iterator_prototype(), set, iteration_kind);
+}
+
+SetIterator::SetIterator(Object& prototype, Set& set, Object::PropertyKind iteration_kind)
+    : Object(prototype)
+    , m_set(set)
+    , m_iteration_kind(iteration_kind)
+    , m_iterator(set.values().begin())
+{
+}
+
+SetIterator::~SetIterator()
+{
+}
+
+void SetIterator::visit_edges(Cell::Visitor& visitor)
+{
+    Base::visit_edges(visitor);
+    visitor.visit(&m_set);
+}
+
+}
diff --git a/Userland/Libraries/LibJS/Runtime/SetIterator.h b/Userland/Libraries/LibJS/Runtime/SetIterator.h
new file mode 100644
index 0000000000..873d81676f
--- /dev/null
+++ b/Userland/Libraries/LibJS/Runtime/SetIterator.h
@@ -0,0 +1,39 @@
+/*
+ * Copyright (c) 2021, Idan Horowitz <idan.horowitz@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/HashTable.h>
+#include <LibJS/Runtime/Object.h>
+#include <LibJS/Runtime/Set.h>
+
+namespace JS {
+
+class SetIterator final : public Object {
+    JS_OBJECT(SetIterator, Object);
+
+public:
+    static SetIterator* create(GlobalObject&, Set& set, Object::PropertyKind iteration_kind);
+
+    explicit SetIterator(Object& prototype, Set& set, Object::PropertyKind iteration_kind);
+    virtual ~SetIterator() override;
+
+    Set& set() const { return m_set; }
+    bool done() const { return m_done; }
+    Object::PropertyKind iteration_kind() const { return m_iteration_kind; }
+
+private:
+    friend class SetIteratorPrototype;
+
+    virtual void visit_edges(Cell::Visitor&) override;
+
+    Set& m_set;
+    bool m_done { false };
+    Object::PropertyKind m_iteration_kind;
+    HashTable<Value, ValueTraits>::Iterator m_iterator;
+};
+
+}
diff --git a/Userland/Libraries/LibJS/Runtime/SetIteratorPrototype.cpp b/Userland/Libraries/LibJS/Runtime/SetIteratorPrototype.cpp
new file mode 100644
index 0000000000..89db9a9cf4
--- /dev/null
+++ b/Userland/Libraries/LibJS/Runtime/SetIteratorPrototype.cpp
@@ -0,0 +1,67 @@
+/*
+ * Copyright (c) 2020, Matthew Olsson <mattco@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibJS/Runtime/Array.h>
+#include <LibJS/Runtime/Error.h>
+#include <LibJS/Runtime/GlobalObject.h>
+#include <LibJS/Runtime/IteratorOperations.h>
+#include <LibJS/Runtime/Set.h>
+#include <LibJS/Runtime/SetIterator.h>
+#include <LibJS/Runtime/SetIteratorPrototype.h>
+
+namespace JS {
+
+SetIteratorPrototype::SetIteratorPrototype(GlobalObject& global_object)
+    : Object(*global_object.iterator_prototype())
+{
+}
+
+void SetIteratorPrototype::initialize(GlobalObject& global_object)
+{
+    auto& vm = this->vm();
+    Object::initialize(global_object);
+
+    define_native_function(vm.names.next, next, 0, Attribute::Configurable | Attribute::Writable);
+    define_property(vm.well_known_symbol_to_string_tag(), js_string(global_object.heap(), "Set Iterator"), Attribute::Configurable);
+}
+
+SetIteratorPrototype::~SetIteratorPrototype()
+{
+}
+
+JS_DEFINE_NATIVE_FUNCTION(SetIteratorPrototype::next)
+{
+    auto this_value = vm.this_value(global_object);
+    if (!this_value.is_object() || !is<SetIterator>(this_value.as_object())) {
+        vm.throw_exception<TypeError>(global_object, ErrorType::NotA, "Set Iterator");
+        return {};
+    }
+
+    auto& set_iterator = static_cast<SetIterator&>(this_value.as_object());
+    if (set_iterator.done())
+        return create_iterator_result_object(global_object, js_undefined(), true);
+
+    auto& set = set_iterator.set();
+    if (set_iterator.m_iterator == set.values().end()) {
+        set_iterator.m_done = true;
+        return create_iterator_result_object(global_object, js_undefined(), true);
+    }
+
+    auto iteration_kind = set_iterator.iteration_kind();
+    VERIFY(iteration_kind != Object::PropertyKind::Key);
+
+    auto value = *set_iterator.m_iterator;
+    ++set_iterator.m_iterator;
+    if (iteration_kind == Object::PropertyKind::Value)
+        return create_iterator_result_object(global_object, value, false);
+
+    auto* entry_array = Array::create(global_object);
+    entry_array->define_property(0, value);
+    entry_array->define_property(1, value);
+    return create_iterator_result_object(global_object, entry_array, false);
+}
+
+}
diff --git a/Userland/Libraries/LibJS/Runtime/SetIteratorPrototype.h b/Userland/Libraries/LibJS/Runtime/SetIteratorPrototype.h
new file mode 100644
index 0000000000..29744c130c
--- /dev/null
+++ b/Userland/Libraries/LibJS/Runtime/SetIteratorPrototype.h
@@ -0,0 +1,25 @@
+/*
+ * Copyright (c) 2020, Matthew Olsson <mattco@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <LibJS/Runtime/Object.h>
+
+namespace JS {
+
+class SetIteratorPrototype final : public Object {
+    JS_OBJECT(SetIteratorPrototype, Object)
+
+public:
+    SetIteratorPrototype(GlobalObject&);
+    virtual void initialize(GlobalObject&) override;
+    virtual ~SetIteratorPrototype() override;
+
+private:
+    JS_DECLARE_NATIVE_FUNCTION(next);
+};
+
+}
diff --git a/Userland/Libraries/LibJS/Runtime/SetPrototype.cpp b/Userland/Libraries/LibJS/Runtime/SetPrototype.cpp
index bfd842c1fe..d6f6a14af8 100644
--- a/Userland/Libraries/LibJS/Runtime/SetPrototype.cpp
+++ b/Userland/Libraries/LibJS/Runtime/SetPrototype.cpp
@@ -5,6 +5,7 @@
  */
 
 #include <AK/HashTable.h>
+#include <LibJS/Runtime/SetIterator.h>
 #include <LibJS/Runtime/SetPrototype.h>
 
 namespace JS {
@@ -23,11 +24,15 @@ void SetPrototype::initialize(GlobalObject& global_object)
     define_native_function(vm.names.add, add, 1, attr);
     define_native_function(vm.names.clear, clear, 0, attr);
     define_native_function(vm.names.delete_, delete_, 1, attr);
+    define_native_function(vm.names.entries, entries, 0, attr);
     define_native_function(vm.names.forEach, for_each, 1, attr);
     define_native_function(vm.names.has, has, 1, attr);
+    define_native_function(vm.names.values, values, 0, attr);
 
     define_native_property(vm.names.size, size_getter, {}, attr);
 
+    define_property(vm.names.keys, get(vm.names.values), attr);
+    define_property(vm.well_known_symbol_iterator(), get(vm.names.values), attr);
     define_property(vm.well_known_symbol_to_string_tag(), js_string(global_object.heap(), vm.names.Set), Attribute::Configurable);
 }
 
@@ -64,6 +69,15 @@ JS_DEFINE_NATIVE_FUNCTION(SetPrototype::delete_)
     return Value(set->values().remove(vm.argument(0)));
 }
 
+JS_DEFINE_NATIVE_FUNCTION(SetPrototype::entries)
+{
+    auto* set = typed_this(vm, global_object);
+    if (!set)
+        return {};
+
+    return SetIterator::create(global_object, *set, Object::PropertyKind::KeyAndValue);
+}
+
 JS_DEFINE_NATIVE_FUNCTION(SetPrototype::for_each)
 {
     auto* set = typed_this(vm, global_object);
@@ -91,6 +105,15 @@ JS_DEFINE_NATIVE_FUNCTION(SetPrototype::has)
     return Value(values.find(vm.argument(0)) != values.end());
 }
 
+JS_DEFINE_NATIVE_FUNCTION(SetPrototype::values)
+{
+    auto* set = typed_this(vm, global_object);
+    if (!set)
+        return {};
+
+    return SetIterator::create(global_object, *set, Object::PropertyKind::Value);
+}
+
 JS_DEFINE_NATIVE_GETTER(SetPrototype::size_getter)
 {
     auto* set = typed_this(vm, global_object);
diff --git a/Userland/Libraries/LibJS/Runtime/SetPrototype.h b/Userland/Libraries/LibJS/Runtime/SetPrototype.h
index a7908c2317..e0b7056140 100644
--- a/Userland/Libraries/LibJS/Runtime/SetPrototype.h
+++ b/Userland/Libraries/LibJS/Runtime/SetPrototype.h
@@ -22,8 +22,10 @@ private:
     JS_DECLARE_NATIVE_FUNCTION(add);
     JS_DECLARE_NATIVE_FUNCTION(clear);
     JS_DECLARE_NATIVE_FUNCTION(delete_);
+    JS_DECLARE_NATIVE_FUNCTION(entries);
     JS_DECLARE_NATIVE_FUNCTION(for_each);
     JS_DECLARE_NATIVE_FUNCTION(has);
+    JS_DECLARE_NATIVE_FUNCTION(values);
 
     JS_DECLARE_NATIVE_GETTER(size_getter);
 };
diff --git a/Userland/Libraries/LibJS/Tests/builtins/Set/Set.prototype.values.js b/Userland/Libraries/LibJS/Tests/builtins/Set/Set.prototype.values.js
new file mode 100644
index 0000000000..2b6a0db262
--- /dev/null
+++ b/Userland/Libraries/LibJS/Tests/builtins/Set/Set.prototype.values.js
@@ -0,0 +1,14 @@
+test("length", () => {
+    expect(Set.prototype.values.length).toBe(0);
+});
+
+test("basic functionality", () => {
+    const a = new Set([1, 2, 3]);
+    const it = a.values();
+    expect(it.next()).toEqual({ value: 1, done: false });
+    expect(it.next()).toEqual({ value: 2, done: false });
+    expect(it.next()).toEqual({ value: 3, done: false });
+    expect(it.next()).toEqual({ value: undefined, done: true });
+    expect(it.next()).toEqual({ value: undefined, done: true });
+    expect(it.next()).toEqual({ value: undefined, done: true });
+});