LibWeb: Implement :nth-child pseudo-class

6 files changed, 161 insertions, 36 deletions

diff --git a/Userland/Libraries/LibWeb/CSS/Parser/DeprecatedCSSParser.cpp b/Userland/Libraries/LibWeb/CSS/Parser/DeprecatedCSSParser.cpp
index b30cd6023e..61c686b4ba 100644
--- a/Userland/Libraries/LibWeb/CSS/Parser/DeprecatedCSSParser.cpp
+++ b/Userland/Libraries/LibWeb/CSS/Parser/DeprecatedCSSParser.cpp
@@ -11,6 +11,7 @@
 #include <LibWeb/CSS/CSSStyleRule.h>
 #include <LibWeb/CSS/Parser/DeprecatedCSSParser.h>
 #include <LibWeb/CSS/PropertyID.h>
+#include <LibWeb/CSS/Selector.h>
 #include <LibWeb/DOM/Document.h>
 #include <ctype.h>
 #include <stdlib.h>
@@ -384,6 +385,17 @@ public:
         return ch == '~' || ch == '>' || ch == '+';
     }
 
+    static StringView capture_selector_args(const String& pseudo_name)
+    {
+        if (const auto start_pos = pseudo_name.find('('); start_pos.has_value()) {
+            const auto start = start_pos.value() + 1;
+            if (const auto end_pos = pseudo_name.index_of(")", start); end_pos.has_value()) {
+                return pseudo_name.substring_view(start, end_pos.value() - start).trim_whitespace();
+            }
+        }
+        return {};
+    }
+
     Optional<CSS::Selector::SimpleSelector> parse_simple_selector()
     {
         auto index_at_start = index;
@@ -399,15 +411,9 @@ public:
         if (peek() == '*') {
             type = CSS::Selector::SimpleSelector::Type::Universal;
             consume_one();
-            return CSS::Selector::SimpleSelector {
-                type,
-                CSS::Selector::SimpleSelector::PseudoClass::None,
-                CSS::Selector::SimpleSelector::PseudoElement::None,
-                String(),
-                CSS::Selector::SimpleSelector::AttributeMatchType::None,
-                String(),
-                String()
-            };
+            CSS::Selector::SimpleSelector result;
+            result.type = type;
+            return result;
         }
 
         if (peek() == '.') {
@@ -435,15 +441,9 @@ public:
             value = value.to_lowercase();
         }
 
-        CSS::Selector::SimpleSelector simple_selector {
-            type,
-            CSS::Selector::SimpleSelector::PseudoClass::None,
-            CSS::Selector::SimpleSelector::PseudoElement::None,
-            value,
-            CSS::Selector::SimpleSelector::AttributeMatchType::None,
-            String(),
-            String()
-        };
+        CSS::Selector::SimpleSelector simple_selector;
+        simple_selector.type = type;
+        simple_selector.value = value;
         buffer.clear();
 
         if (peek() == '[') {
@@ -563,6 +563,9 @@ public:
                 simple_selector.pseudo_class = CSS::Selector::SimpleSelector::PseudoClass::FirstOfType;
             } else if (pseudo_name.equals_ignoring_case("last-of-type")) {
                 simple_selector.pseudo_class = CSS::Selector::SimpleSelector::PseudoClass::LastOfType;
+            } else if (pseudo_name.starts_with("nth-child", CaseSensitivity::CaseInsensitive)) {
+                simple_selector.pseudo_class = CSS::Selector::SimpleSelector::PseudoClass::NthChild;
+                simple_selector.nth_child_pattern = CSS::Selector::SimpleSelector::NthChildPattern::parse(capture_selector_args(pseudo_name));
             } else if (pseudo_name.equals_ignoring_case("before")) {
                 simple_selector.pseudo_element = CSS::Selector::SimpleSelector::PseudoElement::Before;
             } else if (pseudo_name.equals_ignoring_case("after")) {
diff --git a/Userland/Libraries/LibWeb/CSS/Parser/Parser.cpp b/Userland/Libraries/LibWeb/CSS/Parser/Parser.cpp
index 3d07d6a248..479a9a4846 100644
--- a/Userland/Libraries/LibWeb/CSS/Parser/Parser.cpp
+++ b/Userland/Libraries/LibWeb/CSS/Parser/Parser.cpp
@@ -104,15 +104,9 @@ Vector<CSS::Selector::ComplexSelector> Parser::parse_selectors(Vector<String> pa
         if (currentToken == "*") {
             type = CSS::Selector::SimpleSelector::Type::Universal;
             index++;
-            return CSS::Selector::SimpleSelector {
-                type,
-                CSS::Selector::SimpleSelector::PseudoClass::None,
-                CSS::Selector::SimpleSelector::PseudoElement::None,
-                String(),
-                CSS::Selector::SimpleSelector::AttributeMatchType::None,
-                String(),
-                String()
-            };
+            CSS::Selector::SimpleSelector result;
+            result.type = type;
+            return result;
         }
 
         if (currentToken == ".") {
@@ -132,15 +126,9 @@ Vector<CSS::Selector::ComplexSelector> Parser::parse_selectors(Vector<String> pa
             value = value.to_lowercase();
         }
 
-        CSS::Selector::SimpleSelector simple_selector {
-            type,
-            CSS::Selector::SimpleSelector::PseudoClass::None,
-            CSS::Selector::SimpleSelector::PseudoElement::None,
-            value,
-            CSS::Selector::SimpleSelector::AttributeMatchType::None,
-            String(),
-            String()
-        };
+        CSS::Selector::SimpleSelector simple_selector;
+        simple_selector.type = type;
+        simple_selector.value = value;
 
         if (index >= parts.size()) {
             return simple_selector;
diff --git a/Userland/Libraries/LibWeb/CSS/Selector.cpp b/Userland/Libraries/LibWeb/CSS/Selector.cpp
index 1acf2fd9c9..1ddd9de306 100644
--- a/Userland/Libraries/LibWeb/CSS/Selector.cpp
+++ b/Userland/Libraries/LibWeb/CSS/Selector.cpp
@@ -4,7 +4,10 @@
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
+#include "Selector.h"
+#include <AK/StringUtils.h>
 #include <LibWeb/CSS/Selector.h>
+#include <ctype.h>
 
 namespace Web::CSS {
 
@@ -44,4 +47,73 @@ u32 Selector::specificity() const
     return ids * 0x10000 + classes * 0x100 + tag_names;
 }
 
+Selector::SimpleSelector::NthChildPattern Selector::SimpleSelector::NthChildPattern::parse(const StringView& args)
+{
+    CSS::Selector::SimpleSelector::NthChildPattern pattern;
+    if (args.equals_ignoring_case("odd")) {
+        pattern.step_size = 2;
+        pattern.offset = 1;
+    } else if (args.equals_ignoring_case("even")) {
+        pattern.step_size = 2;
+    } else {
+        const auto consume_int = [](GenericLexer& lexer) -> Optional<int> {
+            return AK::StringUtils::convert_to_int(lexer.consume_while([](char c) -> bool {
+                return isdigit(c) || c == '+' || c == '-';
+            }));
+        };
+
+        // Try to match any of following patterns:
+        // 1. An+B
+        // 2. An
+        // 3. B
+        // ...where "A" is "step_size", "B" is "offset" and rest are literals.
+        // "A" can be omitted, in that case "A" = 1.
+        // "A" may have "+" or "-" sign, "B" always must be predated by sign for pattern (1).
+
+        int step_size_or_offset = 0;
+        GenericLexer lexer { args };
+
+        // "When a=1, or a=-1, the 1 may be omitted from the rule."
+        if (lexer.consume_specific("n") || lexer.consume_specific("+n")) {
+            step_size_or_offset = +1;
+            lexer.retreat();
+        } else if (lexer.consume_specific("-n")) {
+            step_size_or_offset = -1;
+            lexer.retreat();
+        } else {
+            const auto value = consume_int(lexer);
+            if (!value.has_value())
+                return {};
+            step_size_or_offset = value.value();
+        }
+
+        if (lexer.consume_specific("n")) {
+            lexer.ignore_while(isspace);
+            if (lexer.next_is('+') || lexer.next_is('-')) {
+                const auto sign = lexer.next_is('+') ? 1 : -1;
+                lexer.ignore();
+                lexer.ignore_while(isspace);
+
+                // "An+B" pattern
+                const auto offset = consume_int(lexer);
+                if (!offset.has_value())
+                    return {};
+                pattern.step_size = step_size_or_offset;
+                pattern.offset = sign * offset.value();
+            } else {
+                // "An" pattern
+                pattern.step_size = step_size_or_offset;
+            }
+        } else {
+            // "B" pattern
+            pattern.offset = step_size_or_offset;
+        }
+
+        if (lexer.remaining().length() > 0)
+            return {};
+    }
+
+    return pattern;
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/CSS/Selector.h b/Userland/Libraries/LibWeb/CSS/Selector.h
index 62c28c4642..d64909a4c1 100644
--- a/Userland/Libraries/LibWeb/CSS/Selector.h
+++ b/Userland/Libraries/LibWeb/CSS/Selector.h
@@ -36,6 +36,7 @@ public:
             Root,
             FirstOfType,
             LastOfType,
+            NthChild,
         };
         PseudoClass pseudo_class { PseudoClass::None };
 
@@ -59,6 +60,17 @@ public:
         AttributeMatchType attribute_match_type { AttributeMatchType::None };
         FlyString attribute_name;
         String attribute_value;
+
+        struct NthChildPattern {
+            int step_size = 0;
+            int offset = 0;
+
+            static NthChildPattern parse(const StringView& args);
+        };
+
+        // FIXME: We don't need this field on every single SimpleSelector, but it's also annoying to malloc it somewhere.
+        // Only used when "pseudo_class" == PseudoClass::NthChild.
+        NthChildPattern nth_child_pattern;
     };
 
     struct ComplexSelector {
diff --git a/Userland/Libraries/LibWeb/CSS/SelectorEngine.cpp b/Userland/Libraries/LibWeb/CSS/SelectorEngine.cpp
index 866266f914..a1b77a8019 100644
--- a/Userland/Libraries/LibWeb/CSS/SelectorEngine.cpp
+++ b/Userland/Libraries/LibWeb/CSS/SelectorEngine.cpp
@@ -82,6 +82,53 @@ static bool matches(const CSS::Selector::SimpleSelector& component, const DOM::E
                 return false;
         }
         break;
+    case CSS::Selector::SimpleSelector::PseudoClass::NthChild:
+        const auto step_size = component.nth_child_pattern.step_size;
+        const auto offset = component.nth_child_pattern.offset;
+        if (step_size == 0 && offset == 0)
+            return false; // "If both a and b are equal to zero, the pseudo-class represents no element in the document tree."
+
+        const auto* parent = element.parent_element();
+        if (!parent)
+            return false;
+
+        int index = 1;
+        for (auto* child = parent->first_child_of_type<DOM::Element>(); child && child != &element; child = child->next_element_sibling()) {
+            ++index;
+        }
+
+        if (step_size < 0) {
+            // When "step_size" is negative, selector represents first "offset" elements in document tree.
+            if (offset <= 0 || index > offset)
+                return false;
+            else
+                break;
+        } else if (step_size == 1) {
+            // When "step_size == 1", selector represents last "offset" elements in document tree.
+            if (offset < 0 || index < offset)
+                return false;
+            else
+                break;
+        }
+
+        // Like "a % b", but handles negative integers correctly.
+        const auto canonical_modulo = [](int a, int b) -> int {
+            int c = a % b;
+            if ((c < 0 && b > 0) || (c > 0 && b < 0)) {
+                c += b;
+            }
+            return c;
+        };
+
+        if (step_size == 0) {
+            // Avoid divide by zero.
+            if (index != offset) {
+                return false;
+            }
+        } else if (canonical_modulo(index - offset, step_size) != 0) {
+            return false;
+        }
+        break;
     }
 
     switch (component.attribute_match_type) {
diff --git a/Userland/Libraries/LibWeb/Dump.cpp b/Userland/Libraries/LibWeb/Dump.cpp
index abc35aca2f..a290178944 100644
--- a/Userland/Libraries/LibWeb/Dump.cpp
+++ b/Userland/Libraries/LibWeb/Dump.cpp
@@ -351,6 +351,9 @@ void dump_selector(StringBuilder& builder, const CSS::Selector& selector)
             case CSS::Selector::SimpleSelector::PseudoClass::LastOfType:
                 pseudo_class_description = "LastOfType";
                 break;
+            case CSS::Selector::SimpleSelector::PseudoClass::NthChild:
+                pseudo_class_description = "NthChild";
+                break;
             case CSS::Selector::SimpleSelector::PseudoClass::Focus:
                 pseudo_class_description = "Focus";
                 break;