LibHTML: Implement compound selectors

This patch moves the Selector object model closer to the specification
objects in Selectors Level 4.

A "Selector" in LibHTML is now a { Vector<ComplexSelector> }, which is
a { Relation, CompoundSelector }. A CompoundSelector is really just
a Vector<SimpleSelector>, and SimpleSelector is "Component" renamed.

This makes a lot more selectors actually match on the Ubuntu Apache2
default homepage. :^)

5 files changed, 193 insertions, 147 deletions

diff --git a/Libraries/LibHTML/CSS/Selector.cpp b/Libraries/LibHTML/CSS/Selector.cpp
index 8e7d30c506..2222bcfa67 100644
--- a/Libraries/LibHTML/CSS/Selector.cpp
+++ b/Libraries/LibHTML/CSS/Selector.cpp
@@ -1,7 +1,7 @@
 #include <LibHTML/CSS/Selector.h>
 
-Selector::Selector(Vector<Component>&& components)
-    : m_components(move(components))
+Selector::Selector(Vector<ComplexSelector>&& component_lists)
+    : m_complex_selectors(move(component_lists))
 {
 }
 
@@ -15,19 +15,21 @@ Specificity Selector::specificity() const
     unsigned tag_names = 0;
     unsigned classes = 0;
 
-    for (auto& component : m_components) {
-        switch (component.type) {
-        case Component::Type::Id:
-            ++ids;
-            break;
-        case Component::Type::Class:
-            ++classes;
-            break;
-        case Component::Type::TagName:
-            ++tag_names;
-            break;
-        default:
-            break;
+    for (auto& list : m_complex_selectors) {
+        for (auto& simple_selector : list.compound_selector) {
+            switch (simple_selector.type) {
+            case SimpleSelector::Type::Id:
+                ++ids;
+                break;
+            case SimpleSelector::Type::Class:
+                ++classes;
+                break;
+            case SimpleSelector::Type::TagName:
+                ++tag_names;
+                break;
+            default:
+                break;
+            }
         }
     }
 
diff --git a/Libraries/LibHTML/CSS/Selector.h b/Libraries/LibHTML/CSS/Selector.h
index 7e1756a9ba..288f16a9a5 100644
--- a/Libraries/LibHTML/CSS/Selector.h
+++ b/Libraries/LibHTML/CSS/Selector.h
@@ -6,7 +6,7 @@
 
 class Selector {
 public:
-    struct Component {
+    struct SimpleSelector {
         enum class Type {
             Invalid,
             Universal,
@@ -23,15 +23,6 @@ public:
         };
         PseudoClass pseudo_class { PseudoClass::None };
 
-        enum class Relation {
-            None,
-            ImmediateChild,
-            Descendant,
-            AdjacentSibling,
-            GeneralSibling,
-        };
-        Relation relation { Relation::None };
-
         String value;
 
         enum class AttributeMatchType {
@@ -45,13 +36,27 @@ public:
         String attribute_value;
     };
 
-    explicit Selector(Vector<Component>&&);
+    struct ComplexSelector {
+        enum class Relation {
+            None,
+            ImmediateChild,
+            Descendant,
+            AdjacentSibling,
+            GeneralSibling,
+        };
+        Relation relation { Relation::None };
+
+        using CompoundSelector = Vector<SimpleSelector>;
+        CompoundSelector compound_selector;
+    };
+
+    explicit Selector(Vector<ComplexSelector>&&);
     ~Selector();
 
-    const Vector<Component>& components() const { return m_components; }
+    const Vector<ComplexSelector>& complex_selectors() const { return m_complex_selectors; }
 
     Specificity specificity() const;
 
 private:
-    Vector<Component> m_components;
+    Vector<ComplexSelector> m_complex_selectors;
 };
diff --git a/Libraries/LibHTML/CSS/SelectorEngine.cpp b/Libraries/LibHTML/CSS/SelectorEngine.cpp
index 904a188e0a..f33018607d 100644
--- a/Libraries/LibHTML/CSS/SelectorEngine.cpp
+++ b/Libraries/LibHTML/CSS/SelectorEngine.cpp
@@ -14,27 +14,27 @@ static bool matches_hover_pseudo_class(const Element& element)
     return element.is_ancestor_of(*hovered_node);
 }
 
-bool matches(const Selector::Component& component, const Element& element)
+bool matches(const Selector::SimpleSelector& component, const Element& element)
 {
     switch (component.pseudo_class) {
-    case Selector::Component::PseudoClass::None:
+    case Selector::SimpleSelector::PseudoClass::None:
         break;
-    case Selector::Component::PseudoClass::Link:
+    case Selector::SimpleSelector::PseudoClass::Link:
         if (!element.is_link())
             return false;
         break;
-    case Selector::Component::PseudoClass::Hover:
+    case Selector::SimpleSelector::PseudoClass::Hover:
         if (!matches_hover_pseudo_class(element))
             return false;
         break;
     }
 
     switch (component.attribute_match_type) {
-    case Selector::Component::AttributeMatchType::HasAttribute:
+    case Selector::SimpleSelector::AttributeMatchType::HasAttribute:
         if (!element.has_attribute(component.attribute_name))
             return false;
         break;
-    case Selector::Component::AttributeMatchType::ExactValueMatch:
+    case Selector::SimpleSelector::AttributeMatchType::ExactValueMatch:
         if (element.attribute(component.attribute_name) != component.attribute_value)
             return false;
         break;
@@ -43,50 +43,52 @@ bool matches(const Selector::Component& component, const Element& element)
     }
 
     switch (component.type) {
-    case Selector::Component::Type::Universal:
+    case Selector::SimpleSelector::Type::Universal:
         return true;
-    case Selector::Component::Type::Id:
+    case Selector::SimpleSelector::Type::Id:
         return component.value == element.attribute("id");
-    case Selector::Component::Type::Class:
+    case Selector::SimpleSelector::Type::Class:
         return element.has_class(component.value);
-    case Selector::Component::Type::TagName:
+    case Selector::SimpleSelector::Type::TagName:
         return component.value == element.tag_name();
     default:
         ASSERT_NOT_REACHED();
     }
 }
 
-bool matches(const Selector& selector, int component_index, const Element& element)
+bool matches(const Selector& selector, int component_list_index, const Element& element)
 {
-    auto& component = selector.components()[component_index];
-    if (!matches(component, element))
-        return false;
-    switch (component.relation) {
-    case Selector::Component::Relation::None:
+    auto& component_list = selector.complex_selectors()[component_list_index];
+    for (auto& component : component_list.compound_selector) {
+        if (!matches(component, element))
+            return false;
+    }
+    switch (component_list.relation) {
+    case Selector::ComplexSelector::Relation::None:
         return true;
-    case Selector::Component::Relation::Descendant:
-        ASSERT(component_index != 0);
+    case Selector::ComplexSelector::Relation::Descendant:
+        ASSERT(component_list_index != 0);
         for (auto* ancestor = element.parent(); ancestor; ancestor = ancestor->parent()) {
             if (!is<Element>(*ancestor))
                 continue;
-            if (matches(selector, component_index - 1, to<Element>(*ancestor)))
+            if (matches(selector, component_list_index - 1, to<Element>(*ancestor)))
                 return true;
         }
         return false;
-    case Selector::Component::Relation::ImmediateChild:
-        ASSERT(component_index != 0);
+    case Selector::ComplexSelector::Relation::ImmediateChild:
+        ASSERT(component_list_index != 0);
         if (!element.parent() || !is<Element>(*element.parent()))
             return false;
-        return matches(selector, component_index - 1, to<Element>(*element.parent()));
-    case Selector::Component::Relation::AdjacentSibling:
-        ASSERT(component_index != 0);
+        return matches(selector, component_list_index - 1, to<Element>(*element.parent()));
+    case Selector::ComplexSelector::Relation::AdjacentSibling:
+        ASSERT(component_list_index != 0);
         if (auto* sibling = element.previous_element_sibling())
-            return matches(selector, component_index - 1, *sibling);
+            return matches(selector, component_list_index - 1, *sibling);
         return false;
-    case Selector::Component::Relation::GeneralSibling:
-        ASSERT(component_index != 0);
+    case Selector::ComplexSelector::Relation::GeneralSibling:
+        ASSERT(component_list_index != 0);
         for (auto* sibling = element.previous_element_sibling(); sibling; sibling = sibling->previous_element_sibling()) {
-            if (matches(selector, component_index - 1, *sibling))
+            if (matches(selector, component_list_index - 1, *sibling))
                 return true;
         }
         return false;
@@ -96,8 +98,8 @@ bool matches(const Selector& selector, int component_index, const Element& eleme
 
 bool matches(const Selector& selector, const Element& element)
 {
-    ASSERT(!selector.components().is_empty());
-    return matches(selector, selector.components().size() - 1, element);
+    ASSERT(!selector.complex_selectors().is_empty());
+    return matches(selector, selector.complex_selectors().size() - 1, element);
 }
 
 }
diff --git a/Libraries/LibHTML/Dump.cpp b/Libraries/LibHTML/Dump.cpp
index 49341b0774..855262af3d 100644
--- a/Libraries/LibHTML/Dump.cpp
+++ b/Libraries/LibHTML/Dump.cpp
@@ -144,57 +144,70 @@ void dump_rule(const StyleRule& rule)
     dbgprintf("Rule:\n");
     for (auto& selector : rule.selectors()) {
         dbgprintf("  Selector:\n");
-        for (auto& component : selector.components()) {
-            const char* type_description = "Unknown";
-            switch (component.type) {
-            case Selector::Component::Type::Invalid:
-                type_description = "Invalid";
-                break;
-            case Selector::Component::Type::Universal:
-                type_description = "Universal";
-                break;
-            case Selector::Component::Type::Id:
-                type_description = "Id";
-                break;
-            case Selector::Component::Type::Class:
-                type_description = "Class";
-                break;
-            case Selector::Component::Type::TagName:
-                type_description = "TagName";
-                break;
-            }
+
+        for (auto& complex_selector : selector.complex_selectors()) {
+            dbgprintf("    ");
+
             const char* relation_description = "";
-            switch (component.relation) {
-            case Selector::Component::Relation::None:
+            switch (complex_selector.relation) {
+            case Selector::ComplexSelector::Relation::None:
                 break;
-            case Selector::Component::Relation::ImmediateChild:
-                relation_description = "{ImmediateChild}";
+            case Selector::ComplexSelector::Relation::ImmediateChild:
+                relation_description = "ImmediateChild";
                 break;
-            case Selector::Component::Relation::Descendant:
-                relation_description = "{Descendant}";
+            case Selector::ComplexSelector::Relation::Descendant:
+                relation_description = "Descendant";
                 break;
-            case Selector::Component::Relation::AdjacentSibling:
-                relation_description = "{AdjacentSibling}";
+            case Selector::ComplexSelector::Relation::AdjacentSibling:
+                relation_description = "AdjacentSibling";
                 break;
-            case Selector::Component::Relation::GeneralSibling:
-                relation_description = "{GeneralSibling}";
-                break;
-            }
-            const char* attribute_match_type_description = "";
-            switch (component.attribute_match_type) {
-            case Selector::Component::AttributeMatchType::None:
-                break;
-            case Selector::Component::AttributeMatchType::HasAttribute:
-                attribute_match_type_description = "HasAttribute";
-                break;
-            case Selector::Component::AttributeMatchType::ExactValueMatch:
-                attribute_match_type_description = "ExactValueMatch";
+            case Selector::ComplexSelector::Relation::GeneralSibling:
+                relation_description = "GeneralSibling";
                 break;
             }
 
-            dbgprintf("    %s:%s %s", type_description, component.value.characters(), relation_description);
-            if (component.attribute_match_type != Selector::Component::AttributeMatchType::None) {
-                dbgprintf(" [%s, name='%s', value='%s']", attribute_match_type_description, component.attribute_name.characters(), component.attribute_value.characters());
+            if (*relation_description)
+                dbgprintf("{%s} ", relation_description);
+
+            for (int i = 0; i < complex_selector.compound_selector.size(); ++i) {
+                auto& simple_selector = complex_selector.compound_selector[i];
+                const char* type_description = "Unknown";
+                switch (simple_selector.type) {
+                case Selector::SimpleSelector::Type::Invalid:
+                    type_description = "Invalid";
+                    break;
+                case Selector::SimpleSelector::Type::Universal:
+                    type_description = "Universal";
+                    break;
+                case Selector::SimpleSelector::Type::Id:
+                    type_description = "Id";
+                    break;
+                case Selector::SimpleSelector::Type::Class:
+                    type_description = "Class";
+                    break;
+                case Selector::SimpleSelector::Type::TagName:
+                    type_description = "TagName";
+                    break;
+                }
+                const char* attribute_match_type_description = "";
+                switch (simple_selector.attribute_match_type) {
+                case Selector::SimpleSelector::AttributeMatchType::None:
+                    break;
+                case Selector::SimpleSelector::AttributeMatchType::HasAttribute:
+                    attribute_match_type_description = "HasAttribute";
+                    break;
+                case Selector::SimpleSelector::AttributeMatchType::ExactValueMatch:
+                    attribute_match_type_description = "ExactValueMatch";
+                    break;
+                }
+
+                dbgprintf("%s:%s", type_description, simple_selector.value.characters());
+                if (simple_selector.attribute_match_type != Selector::SimpleSelector::AttributeMatchType::None) {
+                    dbgprintf(" [%s, name='%s', value='%s']", attribute_match_type_description, simple_selector.attribute_name.characters(), simple_selector.attribute_value.characters());
+                }
+
+                if (i != complex_selector.compound_selector.size() - 1)
+                    dbgprintf(", ");
             }
             dbgprintf("\n");
         }
diff --git a/Libraries/LibHTML/Parser/CSSParser.cpp b/Libraries/LibHTML/Parser/CSSParser.cpp
index 6bf0755bc5..6f7f8f20d6 100644
--- a/Libraries/LibHTML/Parser/CSSParser.cpp
+++ b/Libraries/LibHTML/Parser/CSSParser.cpp
@@ -4,6 +4,7 @@
 #include <LibHTML/Parser/CSSParser.h>
 #include <ctype.h>
 #include <stdio.h>
+#include <stdlib.h>
 
 #define PARSE_ASSERT(x)                                                   \
     if (!(x)) {                                                           \
@@ -166,8 +167,9 @@ public:
         return css[index++];
     };
 
-    void consume_whitespace_or_comments()
+    bool consume_whitespace_or_comments()
     {
+        int original_index = index;
         bool in_comment = false;
         for (; index < css.length(); ++index) {
             char ch = peek();
@@ -187,6 +189,7 @@ public:
                 continue;
             break;
         }
+        return original_index != index;
     }
 
     bool is_valid_selector_char(char ch) const
@@ -199,76 +202,59 @@ public:
         return ch == '~' || ch == '>' || ch == '+';
     }
 
-    Optional<Selector::Component> parse_selector_component()
+    Optional<Selector::SimpleSelector> parse_selector_component()
     {
-        consume_whitespace_or_comments();
-        Selector::Component::Type type;
-        Selector::Component::Relation relation = Selector::Component::Relation::Descendant;
+        if (consume_whitespace_or_comments())
+            return {};
 
-        if (peek() == '{')
+        if (peek() == '{' || peek() == ',')
             return {};
 
-        if (is_combinator(peek())) {
-            switch (peek()) {
-            case '>':
-                relation = Selector::Component::Relation::ImmediateChild;
-                break;
-            case '+':
-                relation = Selector::Component::Relation::AdjacentSibling;
-                break;
-            case '~':
-                relation = Selector::Component::Relation::GeneralSibling;
-                break;
-            }
-            consume_one();
-            consume_whitespace_or_comments();
-        }
+        Selector::SimpleSelector::Type type;
 
         if (peek() == '*') {
-            type = Selector::Component::Type::Universal;
+            type = Selector::SimpleSelector::Type::Universal;
             consume_one();
-            return Selector::Component {
+            return Selector::SimpleSelector {
                 type,
-                Selector::Component::PseudoClass::None,
-                relation,
+                Selector::SimpleSelector::PseudoClass::None,
                 String(),
-                Selector::Component::AttributeMatchType::None,
+                Selector::SimpleSelector::AttributeMatchType::None,
                 String(),
                 String()
             };
         }
 
         if (peek() == '.') {
-            type = Selector::Component::Type::Class;
+            type = Selector::SimpleSelector::Type::Class;
             consume_one();
         } else if (peek() == '#') {
-            type = Selector::Component::Type::Id;
+            type = Selector::SimpleSelector::Type::Id;
             consume_one();
         } else if (isalpha(peek())) {
-            type = Selector::Component::Type::TagName;
+            type = Selector::SimpleSelector::Type::TagName;
         } else {
-            type = Selector::Component::Type::Universal;
+            type = Selector::SimpleSelector::Type::Universal;
         }
 
-        if (type != Selector::Component::Type::Universal) {
+        if (type != Selector::SimpleSelector::Type::Universal) {
             while (is_valid_selector_char(peek()))
                 buffer.append(consume_one());
             PARSE_ASSERT(!buffer.is_null());
         }
 
-        Selector::Component component {
+        Selector::SimpleSelector component {
             type,
-            Selector::Component::PseudoClass::None,
-            relation,
+            Selector::SimpleSelector::PseudoClass::None,
             String::copy(buffer),
-            Selector::Component::AttributeMatchType::None,
+            Selector::SimpleSelector::AttributeMatchType::None,
             String(),
             String()
         };
         buffer.clear();
 
         if (peek() == '[') {
-            Selector::Component::AttributeMatchType attribute_match_type = Selector::Component::AttributeMatchType::HasAttribute;
+            Selector::SimpleSelector::AttributeMatchType attribute_match_type = Selector::SimpleSelector::AttributeMatchType::HasAttribute;
             String attribute_name;
             String attribute_value;
             bool in_value = false;
@@ -277,7 +263,7 @@ public:
             while (peek() != expected_end_of_attribute_selector) {
                 char ch = consume_one();
                 if (ch == '=') {
-                    attribute_match_type = Selector::Component::AttributeMatchType::ExactValueMatch;
+                    attribute_match_type = Selector::SimpleSelector::AttributeMatchType::ExactValueMatch;
                     attribute_name = String::copy(buffer);
                     buffer.clear();
                     in_value = true;
@@ -322,32 +308,70 @@ public:
             buffer.clear();
 
             if (pseudo_name == "link")
-                component.pseudo_class = Selector::Component::PseudoClass::Link;
+                component.pseudo_class = Selector::SimpleSelector::PseudoClass::Link;
             else if (pseudo_name == "hover")
-                component.pseudo_class = Selector::Component::PseudoClass::Hover;
+                component.pseudo_class = Selector::SimpleSelector::PseudoClass::Hover;
         }
 
         return component;
     }
 
-    void parse_selector()
+    Optional<Selector::ComplexSelector> parse_selector_component_list()
     {
-        Vector<Selector::Component> components;
+        auto relation = Selector::ComplexSelector::Relation::Descendant;
+
+        if (peek() == '{' || peek() == ',')
+            return {};
 
+        if (is_combinator(peek())) {
+            switch (peek()) {
+            case '>':
+                relation = Selector::ComplexSelector::Relation::ImmediateChild;
+                break;
+            case '+':
+                relation = Selector::ComplexSelector::Relation::AdjacentSibling;
+                break;
+            case '~':
+                relation = Selector::ComplexSelector::Relation::GeneralSibling;
+                break;
+            }
+            consume_one();
+            consume_whitespace_or_comments();
+        }
+
+        consume_whitespace_or_comments();
+
+        Vector<Selector::SimpleSelector> components;
         for (;;) {
+            dbg() << "calling parse_selector_component at index " << index << ", peek=" << peek();
             auto component = parse_selector_component();
-            if (component.has_value())
-                components.append(component.value());
+            if (!component.has_value())
+                break;
+            components.append(component.value());
+            PARSE_ASSERT(components.size() < 10);
+        }
+
+        return Selector::ComplexSelector { relation, move(components) };
+    }
+
+    void parse_selector()
+    {
+        Vector<Selector::ComplexSelector> component_lists;
+
+        for (;;) {
+            auto component_list = parse_selector_component_list();
+            if (component_list.has_value())
+                component_lists.append(component_list.value());
             consume_whitespace_or_comments();
             if (peek() == ',' || peek() == '{')
                 break;
         }
 
-        if (components.is_empty())
+        if (component_lists.is_empty())
             return;
-        components.first().relation = Selector::Component::Relation::None;
+        component_lists.first().relation = Selector::ComplexSelector::Relation::None;
 
-        current_rule.selectors.append(Selector(move(components)));
+        current_rule.selectors.append(Selector(move(component_lists)));
     };
 
     void parse_selector_list()