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.

9 files changed, 165 insertions, 52 deletions

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);
+
+};