LibWeb: Implement a slow but functional HTMLCollection :^)

HTMLCollection is an awkward legacy interface from the DOM spec.

It provides a live view of a DOM subtree, with some kind of filtering
that determines which elements are part of the collection.

We now return HTMLCollection objects from these APIs:

- getElementsByClassName()
- getElementsByName()
- getElementsByTagName()

This initial implementation does not do any kind of caching, since that
is quite a tricky problem, and there will be plenty of time for tricky
problems later on when the engine is more mature.

14 files changed, 207 insertions, 55 deletions

diff --git a/Userland/Libraries/LibWeb/Bindings/HTMLCollectionWrapperCustom.cpp b/Userland/Libraries/LibWeb/Bindings/HTMLCollectionWrapperCustom.cpp
new file mode 100644
index 0000000000..dae42548f1
--- /dev/null
+++ b/Userland/Libraries/LibWeb/Bindings/HTMLCollectionWrapperCustom.cpp
@@ -0,0 +1,31 @@
+/*
+ * Copyright (c) 2021, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <AK/ScopeGuard.h>
+#include <LibWeb/Bindings/HTMLCollectionWrapper.h>
+#include <LibWeb/Bindings/NodeWrapper.h>
+#include <LibWeb/Bindings/NodeWrapperFactory.h>
+#include <LibWeb/DOM/Element.h>
+
+namespace Web::Bindings {
+
+JS::Value HTMLCollectionWrapper::get(JS::PropertyName const& name, JS::Value receiver, bool without_side_effects) const
+{
+    auto* item = const_cast<DOM::HTMLCollection&>(impl()).named_item(name.to_string());
+    if (!item)
+        return Base::get(name, receiver, without_side_effects);
+    return JS::Value { wrap(global_object(), *item) };
+}
+
+JS::Value HTMLCollectionWrapper::get_by_index(u32 property_index) const
+{
+    auto* item = const_cast<DOM::HTMLCollection&>(impl()).item(property_index);
+    if (!item)
+        return Base::get_by_index(property_index);
+    return wrap(global_object(), *item);
+}
+
+}
diff --git a/Userland/Libraries/LibWeb/CMakeLists.txt b/Userland/Libraries/LibWeb/CMakeLists.txt
index 5361b96482..5983c94f1d 100644
--- a/Userland/Libraries/LibWeb/CMakeLists.txt
+++ b/Userland/Libraries/LibWeb/CMakeLists.txt
@@ -3,6 +3,7 @@ set(SOURCES
     Bindings/EventListenerWrapper.cpp
     Bindings/EventWrapperFactory.cpp
     Bindings/EventTargetWrapperFactory.cpp
+    Bindings/HTMLCollectionWrapperCustom.cpp
     Bindings/ImageConstructor.cpp
     Bindings/LocationObject.cpp
     Bindings/MainThreadVM.cpp
@@ -48,6 +49,7 @@ set(SOURCES
     DOM/Element.cpp
     DOM/ElementFactory.cpp
     DOM/Event.cpp
+    DOM/HTMLCollection.cpp
     DOM/Range.cpp
     DOM/EventDispatcher.cpp
     DOM/EventListener.cpp
@@ -309,6 +311,7 @@ libweb_js_wrapper(DOM/DOMImplementation)
 libweb_js_wrapper(DOM/Element)
 libweb_js_wrapper(DOM/Event)
 libweb_js_wrapper(DOM/EventTarget)
+libweb_js_wrapper(DOM/HTMLCollection)
 libweb_js_wrapper(DOM/ProcessingInstruction)
 libweb_js_wrapper(DOM/ShadowRoot)
 libweb_js_wrapper(DOM/Node)
diff --git a/Userland/Libraries/LibWeb/CodeGenerators/WrapperGenerator.cpp b/Userland/Libraries/LibWeb/CodeGenerators/WrapperGenerator.cpp
index f96a054e98..ea0e923134 100644
--- a/Userland/Libraries/LibWeb/CodeGenerators/WrapperGenerator.cpp
+++ b/Userland/Libraries/LibWeb/CodeGenerators/WrapperGenerator.cpp
@@ -850,6 +850,7 @@ void generate_implementation(const IDL::Interface& interface)
 #include <LibWeb/Bindings/EventTargetWrapperFactory.h>
 #include <LibWeb/Bindings/EventWrapperFactory.h>
 #include <LibWeb/Bindings/HTMLCanvasElementWrapper.h>
+#include <LibWeb/Bindings/HTMLCollectionWrapper.h>
 #include <LibWeb/Bindings/HTMLFormElementWrapper.h>
 #include <LibWeb/Bindings/HTMLHeadElementWrapper.h>
 #include <LibWeb/Bindings/HTMLImageElementWrapper.h>
@@ -1191,6 +1192,7 @@ void generate_prototype_implementation(const IDL::Interface& interface)
 #include <LibWeb/Bindings/EventWrapperFactory.h>
 #include <LibWeb/Bindings/ExceptionOrUtils.h>
 #include <LibWeb/Bindings/HTMLCanvasElementWrapper.h>
+#include <LibWeb/Bindings/HTMLCollectionWrapper.h>
 #include <LibWeb/Bindings/HTMLFormElementWrapper.h>
 #include <LibWeb/Bindings/HTMLHeadElementWrapper.h>
 #include <LibWeb/Bindings/HTMLImageElementWrapper.h>
diff --git a/Userland/Libraries/LibWeb/DOM/Document.cpp b/Userland/Libraries/LibWeb/DOM/Document.cpp
index 7a04f4d688..b1de98c8a5 100644
--- a/Userland/Libraries/LibWeb/DOM/Document.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Document.cpp
@@ -24,6 +24,7 @@
 #include <LibWeb/DOM/ElementFactory.h>
 #include <LibWeb/DOM/Event.h>
 #include <LibWeb/DOM/ExceptionOr.h>
+#include <LibWeb/DOM/HTMLCollection.h>
 #include <LibWeb/DOM/Range.h>
 #include <LibWeb/DOM/ShadowRoot.h>
 #include <LibWeb/DOM/Text.h>
@@ -484,42 +485,29 @@ void Document::set_hovered_node(Node* node)
     invalidate_style();
 }
 
-NonnullRefPtrVector<Element> Document::get_elements_by_name(const String& name) const
+NonnullRefPtr<HTMLCollection> Document::get_elements_by_name(String const& name)
 {
-    NonnullRefPtrVector<Element> elements;
-    for_each_in_inclusive_subtree_of_type<Element>([&](auto& element) {
-        if (element.attribute(HTML::AttributeNames::name) == name)
-            elements.append(element);
-        return IterationDecision::Continue;
+    return HTMLCollection::create(*this, [name](Element const& element) {
+        return element.name() == name;
     });
-    return elements;
 }
 
-NonnullRefPtrVector<Element> Document::get_elements_by_tag_name(const FlyString& tag_name) const
+NonnullRefPtr<HTMLCollection> Document::get_elements_by_tag_name(FlyString const& tag_name)
 {
     // FIXME: Support "*" for tag_name
     // https://dom.spec.whatwg.org/#concept-getelementsbytagname
-    NonnullRefPtrVector<Element> elements;
-    for_each_in_inclusive_subtree_of_type<Element>([&](auto& element) {
-        if (element.namespace_() == Namespace::HTML
-                ? element.local_name().to_lowercase() == tag_name.to_lowercase()
-                : element.local_name() == tag_name) {
-            elements.append(element);
-        }
-        return IterationDecision::Continue;
+    return HTMLCollection::create(*this, [tag_name](Element const& element) {
+        if (element.namespace_() == Namespace::HTML)
+            return element.local_name().to_lowercase() == tag_name.to_lowercase();
+        return element.local_name() == tag_name;
     });
-    return elements;
 }
 
-NonnullRefPtrVector<Element> Document::get_elements_by_class_name(const FlyString& class_name) const
+NonnullRefPtr<HTMLCollection> Document::get_elements_by_class_name(FlyString const& class_name)
 {
-    NonnullRefPtrVector<Element> elements;
-    for_each_in_inclusive_subtree_of_type<Element>([&](auto& element) {
-        if (element.has_class(class_name, in_quirks_mode() ? CaseSensitivity::CaseInsensitive : CaseSensitivity::CaseSensitive))
-            elements.append(element);
-        return IterationDecision::Continue;
+    return HTMLCollection::create(*this, [class_name, quirks_mode = document().in_quirks_mode()](Element const& element) {
+        return element.has_class(class_name, quirks_mode ? CaseSensitivity::CaseInsensitive : CaseSensitivity::CaseSensitive);
     });
-    return elements;
 }
 
 Color Document::link_color() const
diff --git a/Userland/Libraries/LibWeb/DOM/Document.h b/Userland/Libraries/LibWeb/DOM/Document.h
index 03caa5dd1b..684d5ced28 100644
--- a/Userland/Libraries/LibWeb/DOM/Document.h
+++ b/Userland/Libraries/LibWeb/DOM/Document.h
@@ -136,9 +136,9 @@ public:
     void schedule_style_update();
     void schedule_forced_layout();
 
-    NonnullRefPtrVector<Element> get_elements_by_name(const String&) const;
-    NonnullRefPtrVector<Element> get_elements_by_tag_name(const FlyString&) const;
-    NonnullRefPtrVector<Element> get_elements_by_class_name(const FlyString&) const;
+    NonnullRefPtr<HTMLCollection> get_elements_by_name(String const&);
+    NonnullRefPtr<HTMLCollection> get_elements_by_tag_name(FlyString const&);
+    NonnullRefPtr<HTMLCollection> get_elements_by_class_name(FlyString const&);
 
     const String& source() const { return m_source; }
     void set_source(const String& source) { m_source = source; }
diff --git a/Userland/Libraries/LibWeb/DOM/Document.idl b/Userland/Libraries/LibWeb/DOM/Document.idl
index 23d0b76266..c3a26ef15a 100644
--- a/Userland/Libraries/LibWeb/DOM/Document.idl
+++ b/Userland/Libraries/LibWeb/DOM/Document.idl
@@ -14,9 +14,9 @@ interface Document : Node {
     attribute DOMString cookie;
 
     Element? getElementById(DOMString id);
-    ArrayFromVector getElementsByName(DOMString name);
-    ArrayFromVector getElementsByTagName(DOMString tagName);
-    ArrayFromVector getElementsByClassName(DOMString className);
+    HTMLCollection getElementsByName(DOMString name);
+    HTMLCollection getElementsByTagName(DOMString tagName);
+    HTMLCollection getElementsByClassName(DOMString className);
 
     Element createElement(DOMString tagName);
     Element createElementNS(DOMString? namespace, DOMString qualifiedName);
diff --git a/Userland/Libraries/LibWeb/DOM/Element.cpp b/Userland/Libraries/LibWeb/DOM/Element.cpp
index 960865b8cd..8ec37bd14a 100644
--- a/Userland/Libraries/LibWeb/DOM/Element.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Element.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2018-2021, Andreas Kling <kling@serenityos.org>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -14,6 +14,7 @@
 #include <LibWeb/DOM/Document.h>
 #include <LibWeb/DOM/Element.h>
 #include <LibWeb/DOM/ExceptionOr.h>
+#include <LibWeb/DOM/HTMLCollection.h>
 #include <LibWeb/DOM/ShadowRoot.h>
 #include <LibWeb/DOM/Text.h>
 #include <LibWeb/HTML/Parser/HTMLDocumentParser.h>
@@ -325,31 +326,22 @@ bool Element::is_focused() const
     return document().focused_element() == this;
 }
 
-NonnullRefPtrVector<Element> Element::get_elements_by_tag_name(const FlyString& tag_name) const
+NonnullRefPtr<HTMLCollection> Element::get_elements_by_tag_name(FlyString const& tag_name)
 {
     // FIXME: Support "*" for tag_name
     // https://dom.spec.whatwg.org/#concept-getelementsbytagname
-    NonnullRefPtrVector<Element> elements;
-    for_each_in_inclusive_subtree_of_type<Element>([&](auto& element) {
-        if (element.namespace_() == Namespace::HTML
-                ? element.local_name().to_lowercase() == tag_name.to_lowercase()
-                : element.local_name() == tag_name) {
-            elements.append(element);
-        }
-        return IterationDecision::Continue;
+    return HTMLCollection::create(*this, [tag_name](Element const& element) {
+        if (element.namespace_() == Namespace::HTML)
+            return element.local_name().to_lowercase() == tag_name.to_lowercase();
+        return element.local_name() == tag_name;
     });
-    return elements;
 }
 
-NonnullRefPtrVector<Element> Element::get_elements_by_class_name(const FlyString& class_name) const
+NonnullRefPtr<HTMLCollection> Element::get_elements_by_class_name(FlyString const& class_name)
 {
-    NonnullRefPtrVector<Element> elements;
-    for_each_in_inclusive_subtree_of_type<Element>([&](auto& element) {
-        if (element.has_class(class_name, m_document->in_quirks_mode() ? CaseSensitivity::CaseInsensitive : CaseSensitivity::CaseSensitive))
-            elements.append(element);
-        return IterationDecision::Continue;
+    return HTMLCollection::create(*this, [class_name, quirks_mode = document().in_quirks_mode()](Element const& element) {
+        return element.has_class(class_name, quirks_mode ? CaseSensitivity::CaseInsensitive : CaseSensitivity::CaseSensitive);
     });
-    return elements;
 }
 
 void Element::set_shadow_root(RefPtr<ShadowRoot> shadow_root)
diff --git a/Userland/Libraries/LibWeb/DOM/Element.h b/Userland/Libraries/LibWeb/DOM/Element.h
index 86d3d44eb2..189363a99f 100644
--- a/Userland/Libraries/LibWeb/DOM/Element.h
+++ b/Userland/Libraries/LibWeb/DOM/Element.h
@@ -82,8 +82,8 @@ public:
     bool is_focused() const;
     virtual bool is_focusable() const { return false; }
 
-    NonnullRefPtrVector<Element> get_elements_by_tag_name(const FlyString&) const;
-    NonnullRefPtrVector<Element> get_elements_by_class_name(const FlyString&) const;
+    NonnullRefPtr<HTMLCollection> get_elements_by_tag_name(FlyString const&);
+    NonnullRefPtr<HTMLCollection> get_elements_by_class_name(FlyString const&);
 
     ShadowRoot* shadow_root() { return m_shadow_root; }
     const ShadowRoot* shadow_root() const { return m_shadow_root; }
diff --git a/Userland/Libraries/LibWeb/DOM/Element.idl b/Userland/Libraries/LibWeb/DOM/Element.idl
index a6c2202165..6e4eb30cbd 100644
--- a/Userland/Libraries/LibWeb/DOM/Element.idl
+++ b/Userland/Libraries/LibWeb/DOM/Element.idl
@@ -8,8 +8,8 @@ interface Element : Node {
     boolean hasAttribute(DOMString qualifiedName);
     boolean hasAttributes();
 
-    ArrayFromVector getElementsByTagName(DOMString tagName);
-    ArrayFromVector getElementsByClassName(DOMString className);
+    HTMLCollection getElementsByTagName(DOMString tagName);
+    HTMLCollection getElementsByClassName(DOMString className);
 
     [LegacyNullToEmptyString] attribute DOMString innerHTML;
     [Reflect] attribute DOMString id;
diff --git a/Userland/Libraries/LibWeb/DOM/HTMLCollection.cpp b/Userland/Libraries/LibWeb/DOM/HTMLCollection.cpp
new file mode 100644
index 0000000000..86b26a087c
--- /dev/null
+++ b/Userland/Libraries/LibWeb/DOM/HTMLCollection.cpp
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2021, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibWeb/DOM/Element.h>
+#include <LibWeb/DOM/HTMLCollection.h>
+#include <LibWeb/DOM/ParentNode.h>
+
+namespace Web::DOM {
+
+HTMLCollection::HTMLCollection(ParentNode& root, Function<bool(Element const&)> filter)
+    : m_root(root)
+    , m_filter(move(filter))
+{
+}
+
+HTMLCollection::~HTMLCollection()
+{
+}
+
+Vector<NonnullRefPtr<Element>> HTMLCollection::collect_matching_elements()
+{
+    Vector<NonnullRefPtr<Element>> elements;
+    m_root->for_each_in_inclusive_subtree_of_type<Element>([&](auto& element) {
+        if (m_filter(element))
+            elements.append(element);
+        return IterationDecision::Continue;
+    });
+    return elements;
+}
+
+size_t HTMLCollection::length()
+{
+    return collect_matching_elements().size();
+}
+
+Element* HTMLCollection::item(size_t index)
+{
+    auto elements = collect_matching_elements();
+    if (index >= elements.size())
+        return nullptr;
+    return elements[index];
+}
+
+Element* HTMLCollection::named_item(FlyString const& name)
+{
+    if (name.is_null())
+        return nullptr;
+    auto elements = collect_matching_elements();
+    // First look for an "id" attribute match
+    if (auto it = elements.find_if([&](auto& entry) { return entry->attribute(HTML::AttributeNames::id) == name; }); it != elements.end())
+        return *it;
+    // Then look for a "name" attribute match
+    if (auto it = elements.find_if([&](auto& entry) { return entry->name() == name; }); it != elements.end())
+        return *it;
+    return nullptr;
+}
+
+}
diff --git a/Userland/Libraries/LibWeb/DOM/HTMLCollection.h b/Userland/Libraries/LibWeb/DOM/HTMLCollection.h
new file mode 100644
index 0000000000..a4c87f4fe4
--- /dev/null
+++ b/Userland/Libraries/LibWeb/DOM/HTMLCollection.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright (c) 2021, Andreas Kling <kling@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/FlyString.h>
+#include <AK/Function.h>
+#include <AK/Noncopyable.h>
+#include <LibWeb/Bindings/Wrappable.h>
+#include <LibWeb/Forward.h>
+
+namespace Web::DOM {
+
+// NOTE: HTMLCollection is in the DOM namespace because it's part of the DOM specification.
+
+// This class implements a live, filtered view of a DOM subtree.
+// When constructing an HTMLCollection, you provide a root node + a filter.
+// The filter is a simple Function object that answers the question
+// "is this Element part of the collection?"
+
+// FIXME: HTMLCollection currently does no caching. It will re-filter on every access!
+//        We should teach it how to cache results. The main challenge is invalidating
+//        these caches, since this needs to happen on various kinds of DOM mutation.
+
+class HTMLCollection
+    : public RefCounted<HTMLCollection>
+    , public Bindings::Wrappable {
+    AK_MAKE_NONCOPYABLE(HTMLCollection);
+    AK_MAKE_NONMOVABLE(HTMLCollection);
+
+public:
+    using WrapperType = Bindings::HTMLCollectionWrapper;
+
+    static NonnullRefPtr<HTMLCollection> create(ParentNode& root, Function<bool(Element const&)> filter)
+    {
+        return adopt(*new HTMLCollection(root, move(filter)));
+    }
+
+    ~HTMLCollection();
+
+    size_t length();
+    Element* item(size_t index);
+    Element* named_item(FlyString const& name);
+
+    Vector<NonnullRefPtr<Element>> collect_matching_elements();
+
+protected:
+    HTMLCollection(ParentNode& root, Function<bool(Element const&)> filter);
+
+private:
+    NonnullRefPtr<ParentNode> m_root;
+    Function<bool(Element const&)> m_filter;
+};
+
+}
+
+namespace Web::Bindings {
+
+HTMLCollectionWrapper* wrap(JS::GlobalObject&, DOM::HTMLCollection&);
+
+}
diff --git a/Userland/Libraries/LibWeb/DOM/HTMLCollection.idl b/Userland/Libraries/LibWeb/DOM/HTMLCollection.idl
new file mode 100644
index 0000000000..89cc874c8a
--- /dev/null
+++ b/Userland/Libraries/LibWeb/DOM/HTMLCollection.idl
@@ -0,0 +1,8 @@
+[CustomGet,CustomGetByIndex]
+interface HTMLCollection {
+
+    readonly attribute unsigned long length;
+    Element? item(unsigned long index);
+    Element? namedItem(DOMString name);
+
+};
diff --git a/Userland/Libraries/LibWeb/Forward.h b/Userland/Libraries/LibWeb/Forward.h
index edd5b05ff9..e2446cc11b 100644
--- a/Userland/Libraries/LibWeb/Forward.h
+++ b/Userland/Libraries/LibWeb/Forward.h
@@ -42,6 +42,7 @@ class Event;
 class EventHandler;
 class EventListener;
 class EventTarget;
+class HTMLCollection;
 class MouseEvent;
 class Node;
 class ParentNode;
@@ -218,6 +219,7 @@ class HTMLBodyElementWrapper;
 class HTMLBRElementWrapper;
 class HTMLButtonElementWrapper;
 class HTMLCanvasElementWrapper;
+class HTMLCollectionWrapper;
 class HTMLDataElementWrapper;
 class HTMLDataListElementWrapper;
 class HTMLDetailsElementWrapper;
diff --git a/Userland/Libraries/LibWeb/Page/Frame.cpp b/Userland/Libraries/LibWeb/Page/Frame.cpp
index b53f02bbbe..aea48fcb07 100644
--- a/Userland/Libraries/LibWeb/Page/Frame.cpp
+++ b/Userland/Libraries/LibWeb/Page/Frame.cpp
@@ -6,6 +6,7 @@
 
 #include <LibWeb/DOM/Document.h>
 #include <LibWeb/DOM/Event.h>
+#include <LibWeb/DOM/HTMLCollection.h>
 #include <LibWeb/DOM/Window.h>
 #include <LibWeb/HTML/HTMLAnchorElement.h>
 #include <LibWeb/InProcessWebView.h>
@@ -161,9 +162,9 @@ void Frame::scroll_to_anchor(const String& fragment)
     auto element = document()->get_element_by_id(fragment);
     if (!element) {
         auto candidates = document()->get_elements_by_name(fragment);
-        for (auto& candidate : candidates) {
-            if (is<HTML::HTMLAnchorElement>(candidate)) {
-                element = downcast<HTML::HTMLAnchorElement>(candidate);
+        for (auto& candidate : candidates->collect_matching_elements()) {
+            if (is<HTML::HTMLAnchorElement>(*candidate)) {
+                element = downcast<HTML::HTMLAnchorElement>(*candidate);
                 break;
             }
         }