/*

 * Copyright (c) 2018-2024, Andreas Kling <kling@serenityos.org>

 * Copyright (c) 2021-2024, Sam Atkins <sam@ladybird.org>

 *

 * SPDX-License-Identifier: BSD-2-Clause

 */

#include <LibWeb/CSS/Keyword.h>

#include <LibWeb/CSS/Parser/Parser.h>

#include <LibWeb/CSS/SelectorEngine.h>

#include <LibWeb/CSS/StyleProperties.h>

#include <LibWeb/DOM/Attr.h>

#include <LibWeb/DOM/Document.h>

#include <LibWeb/DOM/Element.h>

#include <LibWeb/DOM/NamedNodeMap.h>

#include <LibWeb/DOM/Text.h>

#include <LibWeb/HTML/AttributeNames.h>

#include <LibWeb/HTML/HTMLAnchorElement.h>

#include <LibWeb/HTML/HTMLAreaElement.h>

#include <LibWeb/HTML/HTMLButtonElement.h>

#include <LibWeb/HTML/HTMLDetailsElement.h>

#include <LibWeb/HTML/HTMLDialogElement.h>

#include <LibWeb/HTML/HTMLFieldSetElement.h>

#include <LibWeb/HTML/HTMLHtmlElement.h>

#include <LibWeb/HTML/HTMLInputElement.h>

#include <LibWeb/HTML/HTMLMediaElement.h>

#include <LibWeb/HTML/HTMLOptGroupElement.h>

#include <LibWeb/HTML/HTMLOptionElement.h>

#include <LibWeb/HTML/HTMLProgressElement.h>

#include <LibWeb/HTML/HTMLSelectElement.h>

#include <LibWeb/HTML/HTMLTextAreaElement.h>

#include <LibWeb/Infra/Strings.h>

#include <LibWeb/Namespace.h>

namespace Web::SelectorEngine {

// Upward traversal for descendant (' ') and immediate child combinator ('>')

// If we're starting inside a shadow tree, traversal stops at the nearest shadow host.

// This is an implementation detail of the :host selector. Otherwise we would just traverse up to the document root.

static inline JS::GCPtr<DOM::Node const> traverse_up(JS::GCPtr<DOM::Node const> node, JS::GCPtr<DOM::Element const> shadow_host)

{

    if (!node)

        return nullptr;

    if (shadow_host) {

        // NOTE: We only traverse up to the shadow host, not beyond.

        if (node == shadow_host)

            return nullptr;

        return node->parent_or_shadow_host_element();

    }

    return node->parent();

}

// https://drafts.csswg.org/selectors-4/#the-lang-pseudo

static inline bool matches_lang_pseudo_class(DOM::Element const& element, Vector<FlyString> const& languages)

{

    FlyString element_language;

    for (auto const* e = &element; e; e = e->parent_element()) {

        auto lang = e->attribute(HTML::AttributeNames::lang);

        if (lang.has_value()) {

            element_language = lang.release_value();

            break;

        }

    }

    if (element_language.is_empty())

        return false;

    // FIXME: This is ad-hoc. Implement a proper language range matching algorithm as recommended by BCP47.

    for (auto const& language : languages) {

        if (language.is_empty())

            continue;

        if (language == "*"sv)

            return true;

        if (!element_language.to_string().contains('-') && Infra::is_ascii_case_insensitive_match(element_language, language))

            return true;

        auto parts = element_language.to_string().split_limit('-', 2).release_value_but_fixme_should_propagate_errors();

        if (Infra::is_ascii_case_insensitive_match(parts[0], language))

            return true;

    }

    return false;

}

// https://drafts.csswg.org/selectors-4/#relational

static inline bool matches_has_pseudo_class(CSS::Selector const& selector, Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule, DOM::Element const& anchor, JS::GCPtr<DOM::Element const> shadow_host)

{

    switch (selector.compound_selectors()[0].combinator) {

    // Shouldn't be possible because we've parsed relative selectors, which always have a combinator, implicitly or explicitly.

    case CSS::Selector::Combinator::None:

        VERIFY_NOT_REACHED();

    case CSS::Selector::Combinator::Descendant: {

        bool has = false;

        anchor.for_each_in_subtree([&](auto const& descendant) {

            if (!descendant.is_element())

                return TraversalDecision::Continue;

            auto const& descendant_element = static_cast<DOM::Element const&>(descendant);

            if (matches(selector, style_sheet_for_rule, descendant_element, shadow_host, {}, {}, SelectorKind::Relative)) {

                has = true;

                return TraversalDecision::Break;

            }

            return TraversalDecision::Continue;

        });

        return has;

    }

    case CSS::Selector::Combinator::ImmediateChild: {

        bool has = false;

        anchor.for_each_child([&](DOM::Node const& child) {

            if (!child.is_element())

                return IterationDecision::Continue;

            auto const& child_element = static_cast<DOM::Element const&>(child);

            if (matches(selector, style_sheet_for_rule, child_element, shadow_host, {}, {}, SelectorKind::Relative)) {

                has = true;

                return IterationDecision::Break;

            }

            return IterationDecision::Continue;

        });

        return has;

    }

    case CSS::Selector::Combinator::NextSibling:

        return anchor.next_element_sibling() != nullptr && matches(selector, style_sheet_for_rule, *anchor.next_element_sibling(), shadow_host, {}, {}, SelectorKind::Relative);

    case CSS::Selector::Combinator::SubsequentSibling: {

        for (auto* sibling = anchor.next_element_sibling(); sibling; sibling = sibling->next_element_sibling()) {

            if (matches(selector, style_sheet_for_rule, *sibling, shadow_host, {}, {}, SelectorKind::Relative))

                return true;

        }

        return false;

    }

    case CSS::Selector::Combinator::Column:

        TODO();

    }

    return false;

}

// https://html.spec.whatwg.org/multipage/semantics-other.html#selector-link

static inline bool matches_link_pseudo_class(DOM::Element const& element)

{

    // All a elements that have an href attribute, and all area elements that have an href attribute, must match one of :link and :visited.

    if (!is<HTML::HTMLAnchorElement>(element) && !is<HTML::HTMLAreaElement>(element))

        return false;

    return element.has_attribute(HTML::AttributeNames::href);

}

bool matches_hover_pseudo_class(DOM::Element const& element)

{

    auto* hovered_node = element.document().hovered_node();

    if (!hovered_node)

        return false;

    if (&element == hovered_node)

        return true;

    return element.is_shadow_including_ancestor_of(*hovered_node);

}

// https://html.spec.whatwg.org/multipage/semantics-other.html#selector-checked

static inline bool matches_checked_pseudo_class(DOM::Element const& element)

{

    // The :checked pseudo-class must match any element falling into one of the following categories:

    // - input elements whose type attribute is in the Checkbox state and whose checkedness state is true

    // - input elements whose type attribute is in the Radio Button state and whose checkedness state is true

    if (is<HTML::HTMLInputElement>(element)) {

        auto const& input_element = static_cast<HTML::HTMLInputElement const&>(element);

        switch (input_element.type_state()) {

        case HTML::HTMLInputElement::TypeAttributeState::Checkbox:

        case HTML::HTMLInputElement::TypeAttributeState::RadioButton:

            return static_cast<HTML::HTMLInputElement const&>(element).checked();

        default:

            return false;

        }

    }

    // - option elements whose selectedness is true

    if (is<HTML::HTMLOptionElement>(element)) {

        return static_cast<HTML::HTMLOptionElement const&>(element).selected();

    }

    return false;

}

// https://html.spec.whatwg.org/multipage/semantics-other.html#selector-indeterminate

static inline bool matches_indeterminate_pseudo_class(DOM::Element const& element)

{

    // The :indeterminate pseudo-class must match any element falling into one of the following categories:

    // - input elements whose type attribute is in the Checkbox state and whose indeterminate IDL attribute is set to true

    // FIXME: - input elements whose type attribute is in the Radio Button state and whose radio button group contains no input elements whose checkedness state is true.

    if (is<HTML::HTMLInputElement>(element)) {

        auto const& input_element = static_cast<HTML::HTMLInputElement const&>(element);

        switch (input_element.type_state()) {

        case HTML::HTMLInputElement::TypeAttributeState::Checkbox:

            return input_element.indeterminate();

        default:

            return false;

        }

    }

    // - progress elements with no value content attribute

    if (is<HTML::HTMLProgressElement>(element)) {

        return !element.has_attribute(HTML::AttributeNames::value);

    }

    return false;

}

static inline bool matches_attribute(CSS::Selector::SimpleSelector::Attribute const& attribute, [[maybe_unused]] Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule, DOM::Element const& element)

{

    // FIXME: Check the attribute's namespace, once we support that in DOM::Element!

    auto const& attribute_name = attribute.qualified_name.name.name;

    auto const* attr = element.namespace_uri() == Namespace::HTML ? element.attributes()->get_attribute_with_lowercase_qualified_name(attribute_name)

                                                                  : element.attributes()->get_attribute(attribute_name);

    if (attribute.match_type == CSS::Selector::SimpleSelector::Attribute::MatchType::HasAttribute) {

        // Early way out in case of an attribute existence selector.

        return attr != nullptr;

    }

    if (!attr)

        return false;

    auto case_sensitivity = [&](CSS::Selector::SimpleSelector::Attribute::CaseType case_type) {

        switch (case_type) {

        case CSS::Selector::SimpleSelector::Attribute::CaseType::CaseInsensitiveMatch:

            return CaseSensitivity::CaseInsensitive;

        case CSS::Selector::SimpleSelector::Attribute::CaseType::CaseSensitiveMatch:

            return CaseSensitivity::CaseSensitive;

        case CSS::Selector::SimpleSelector::Attribute::CaseType::DefaultMatch:

            // See: https://html.spec.whatwg.org/multipage/semantics-other.html#case-sensitivity-of-selectors

            if (element.document().is_html_document()

                && element.namespace_uri() == Namespace::HTML

                && attribute_name.is_one_of(

                    HTML::AttributeNames::accept, HTML::AttributeNames::accept_charset, HTML::AttributeNames::align,

                    HTML::AttributeNames::alink, HTML::AttributeNames::axis, HTML::AttributeNames::bgcolor, HTML::AttributeNames::charset,

                    HTML::AttributeNames::checked, HTML::AttributeNames::clear, HTML::AttributeNames::codetype, HTML::AttributeNames::color,

                    HTML::AttributeNames::compact, HTML::AttributeNames::declare, HTML::AttributeNames::defer, HTML::AttributeNames::dir,

                    HTML::AttributeNames::direction, HTML::AttributeNames::disabled, HTML::AttributeNames::enctype, HTML::AttributeNames::face,

                    HTML::AttributeNames::frame, HTML::AttributeNames::hreflang, HTML::AttributeNames::http_equiv, HTML::AttributeNames::lang,

                    HTML::AttributeNames::language, HTML::AttributeNames::link, HTML::AttributeNames::media, HTML::AttributeNames::method,

                    HTML::AttributeNames::multiple, HTML::AttributeNames::nohref, HTML::AttributeNames::noresize, HTML::AttributeNames::noshade,

                    HTML::AttributeNames::nowrap, HTML::AttributeNames::readonly, HTML::AttributeNames::rel, HTML::AttributeNames::rev,

                    HTML::AttributeNames::rules, HTML::AttributeNames::scope, HTML::AttributeNames::scrolling, HTML::AttributeNames::selected,

                    HTML::AttributeNames::shape, HTML::AttributeNames::target, HTML::AttributeNames::text, HTML::AttributeNames::type,

                    HTML::AttributeNames::valign, HTML::AttributeNames::valuetype, HTML::AttributeNames::vlink)) {

                return CaseSensitivity::CaseInsensitive;

            }

            return CaseSensitivity::CaseSensitive;

        }

        VERIFY_NOT_REACHED();

    }(attribute.case_type);

    auto case_insensitive_match = case_sensitivity == CaseSensitivity::CaseInsensitive;

    switch (attribute.match_type) {

    case CSS::Selector::SimpleSelector::Attribute::MatchType::ExactValueMatch:

        return case_insensitive_match

            ? Infra::is_ascii_case_insensitive_match(attr->value(), attribute.value)

            : attr->value() == attribute.value;

    case CSS::Selector::SimpleSelector::Attribute::MatchType::ContainsWord: {

        if (attribute.value.is_empty()) {

            // This selector is always false is match value is empty.

            return false;

        }

        auto const& attribute_value = attr->value();

        auto const view = attribute_value.bytes_as_string_view().split_view(' ');

        auto const size = view.size();

        for (size_t i = 0; i < size; ++i) {

            auto const value = view.at(i);

            if (case_insensitive_match

                    ? Infra::is_ascii_case_insensitive_match(value, attribute.value)

                    : value == attribute.value) {

                return true;

            }

        }

        return false;

    }

    case CSS::Selector::SimpleSelector::Attribute::MatchType::ContainsString:

        return !attribute.value.is_empty()

            && attr->value().contains(attribute.value, case_sensitivity);

    case CSS::Selector::SimpleSelector::Attribute::MatchType::StartsWithSegment: {

        auto const& element_attr_value = attr->value();

        if (element_attr_value.is_empty()) {

            // If the attribute value on element is empty, the selector is true

            // if the match value is also empty and false otherwise.

            return attribute.value.is_empty();

        }

        if (attribute.value.is_empty()) {

            return false;

        }

        auto segments = element_attr_value.bytes_as_string_view().split_view('-');

        return case_insensitive_match

            ? Infra::is_ascii_case_insensitive_match(segments.first(), attribute.value)

            : segments.first() == attribute.value;

    }

    case CSS::Selector::SimpleSelector::Attribute::MatchType::StartsWithString:

        return !attribute.value.is_empty()

            && attr->value().bytes_as_string_view().starts_with(attribute.value, case_sensitivity);

    case CSS::Selector::SimpleSelector::Attribute::MatchType::EndsWithString:

        return !attribute.value.is_empty()

            && attr->value().bytes_as_string_view().ends_with(attribute.value, case_sensitivity);

    default:

        break;

    }

    return false;

}

static inline DOM::Element const* previous_sibling_with_same_tag_name(DOM::Element const& element)

{

    for (auto const* sibling = element.previous_element_sibling(); sibling; sibling = sibling->previous_element_sibling()) {

        if (sibling->tag_name() == element.tag_name())

            return sibling;

    }

    return nullptr;

}

static inline DOM::Element const* next_sibling_with_same_tag_name(DOM::Element const& element)

{

    for (auto const* sibling = element.next_element_sibling(); sibling; sibling = sibling->next_element_sibling()) {

        if (sibling->tag_name() == element.tag_name())

            return sibling;

    }

    return nullptr;

}

// https://html.spec.whatwg.org/multipage/semantics-other.html#selector-read-write

static bool matches_read_write_pseudo_class(DOM::Element const& element)

{

    // The :read-write pseudo-class must match any element falling into one of the following categories,

    // which for the purposes of Selectors are thus considered user-alterable: [SELECTORS]

    // - input elements to which the readonly attribute applies, and that are mutable

    //   (i.e. that do not have the readonly attribute specified and that are not disabled)

    if (is<HTML::HTMLInputElement>(element)) {

        auto& input_element = static_cast<HTML::HTMLInputElement const&>(element);

        if (input_element.has_attribute(HTML::AttributeNames::readonly))

            return false;

        if (!input_element.enabled())

            return false;

        return true;

    }

    // - textarea elements that do not have a readonly attribute, and that are not disabled

    if (is<HTML::HTMLTextAreaElement>(element)) {

        auto& input_element = static_cast<HTML::HTMLTextAreaElement const&>(element);

        if (input_element.has_attribute(HTML::AttributeNames::readonly))

            return false;

        if (!input_element.enabled())

            return false;

        return true;

    }

    // - elements that are editing hosts or editable and are neither input elements nor textarea elements

    return element.is_editable();

}

// https://www.w3.org/TR/selectors-4/#open-state

static bool matches_open_state_pseudo_class(DOM::Element const& element, bool open)

{

    // The :open pseudo-class represents an element that has both “open” and “closed” states,

    // and which is currently in the “open” state.

    // The :closed pseudo-class represents an element that has both “open” and “closed” states,

    // and which is currently in the closed state.

    // NOTE: Spec specifically suggests supporting <details>, <dialog>, and <select>.

    //       There may be others we want to treat as open or closed.

    if (is<HTML::HTMLDetailsElement>(element) || is<HTML::HTMLDialogElement>(element))

        return open == element.has_attribute(HTML::AttributeNames::open);

    if (is<HTML::HTMLSelectElement>(element))

        return open == static_cast<HTML::HTMLSelectElement const&>(element).is_open();

    return false;

}

// https://drafts.csswg.org/css-scoping/#host-selector

static inline bool matches_host_pseudo_class(JS::NonnullGCPtr<DOM::Element const> element, JS::GCPtr<DOM::Element const> shadow_host, CSS::SelectorList const& argument_selector_list, Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule)

{

    // When evaluated in the context of a shadow tree, it matches the shadow tree’s shadow host if the shadow host,

    // in its normal context, matches the selector argument. In any other context, it matches nothing.

    if (!shadow_host || element != shadow_host)

        return false;

    // NOTE: There's either 0 or 1 argument selector, since the syntax is :host or :host(<compound-selector>)

    if (!argument_selector_list.is_empty())

        return matches(argument_selector_list.first(), style_sheet_for_rule, element, nullptr);

    return true;

}

static inline bool matches_pseudo_class(CSS::Selector::SimpleSelector::PseudoClassSelector const& pseudo_class, Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule, DOM::Element const& element, JS::GCPtr<DOM::Element const> shadow_host, JS::GCPtr<DOM::ParentNode const> scope, SelectorKind selector_kind)

{

    switch (pseudo_class.type) {

    case CSS::PseudoClass::Link:

    case CSS::PseudoClass::AnyLink:

        // NOTE: AnyLink should match whether the link is visited or not, so if we ever start matching

        //       :visited, we'll need to handle these differently.

        return matches_link_pseudo_class(element);

    case CSS::PseudoClass::LocalLink: {

        // The :local-link pseudo-class allows authors to style hyperlinks based on the users current location

        // within a site. It represents an element that is the source anchor of a hyperlink whose target’s

        // absolute URL matches the element’s own document URL. If the hyperlink’s target includes a fragment

        // URL, then the fragment URL of the current URL must also match; if it does not, then the fragment

        // URL portion of the current URL is not taken into account in the comparison.

        if (!matches_link_pseudo_class(element))

            return false;

        auto document_url = element.document().url();

        URL::URL target_url = element.document().parse_url(element.attribute(HTML::AttributeNames::href).value_or({}));

        if (target_url.fragment().has_value())

            return document_url.equals(target_url, URL::ExcludeFragment::No);

        return document_url.equals(target_url, URL::ExcludeFragment::Yes);

    }

    case CSS::PseudoClass::Visited:

        // FIXME: Maybe match this selector sometimes?

        return false;

    case CSS::PseudoClass::Active:

        return element.is_active();

    case CSS::PseudoClass::Hover:

        return matches_hover_pseudo_class(element);

    case CSS::PseudoClass::Focus:

        return element.is_focused();

    case CSS::PseudoClass::FocusVisible:

        // FIXME: We should only apply this when a visible focus is useful. Decide when that is!

        return element.is_focused();

    case CSS::PseudoClass::FocusWithin: {

        auto* focused_element = element.document().focused_element();

        return focused_element && element.is_inclusive_ancestor_of(*focused_element);

    }

    case CSS::PseudoClass::FirstChild:

        return !element.previous_element_sibling();

    case CSS::PseudoClass::LastChild:

        return !element.next_element_sibling();

    case CSS::PseudoClass::OnlyChild:

        return !(element.previous_element_sibling() || element.next_element_sibling());

    case CSS::PseudoClass::Empty: {

        if (!element.has_children())

            return true;

        if (element.first_child_of_type<DOM::Element>())

            return false;

        // NOTE: CSS Selectors level 4 changed ":empty" to also match whitespace-only text nodes.

        //       However, none of the major browser supports this yet, so let's just hang back until they do.

        bool has_nonempty_text_child = false;

        element.for_each_child_of_type<DOM::Text>([&](auto const& text_child) {

            if (!text_child.data().is_empty()) {

                has_nonempty_text_child = true;

                return IterationDecision::Break;

            }

            return IterationDecision::Continue;

        });

        return !has_nonempty_text_child;

    }

    case CSS::PseudoClass::Root:

        return is<HTML::HTMLHtmlElement>(element);

    case CSS::PseudoClass::Host:

        return matches_host_pseudo_class(element, shadow_host, pseudo_class.argument_selector_list, style_sheet_for_rule);

    case CSS::PseudoClass::Scope:

        return scope ? &element == scope : is<HTML::HTMLHtmlElement>(element);

    case CSS::PseudoClass::FirstOfType:

        return !previous_sibling_with_same_tag_name(element);

    case CSS::PseudoClass::LastOfType:

        return !next_sibling_with_same_tag_name(element);

    case CSS::PseudoClass::OnlyOfType:

        return !previous_sibling_with_same_tag_name(element) && !next_sibling_with_same_tag_name(element);

    case CSS::PseudoClass::Lang:

        return matches_lang_pseudo_class(element, pseudo_class.languages);

    case CSS::PseudoClass::Disabled:

        // https://html.spec.whatwg.org/multipage/semantics-other.html#selector-disabled

        // The :disabled pseudo-class must match any element that is actually disabled.

        return element.is_actually_disabled();

    case CSS::PseudoClass::Enabled:

        // https://html.spec.whatwg.org/multipage/semantics-other.html#selector-enabled

        // The :enabled pseudo-class must match any button, input, select, textarea, optgroup, option, fieldset element, or form-associated custom element that is not actually disabled.

        return (is<HTML::HTMLButtonElement>(element) || is<HTML::HTMLInputElement>(element) || is<HTML::HTMLSelectElement>(element) || is<HTML::HTMLTextAreaElement>(element) || is<HTML::HTMLOptGroupElement>(element) || is<HTML::HTMLOptionElement>(element) || is<HTML::HTMLFieldSetElement>(element))

            && !element.is_actually_disabled();

    case CSS::PseudoClass::Checked:

        return matches_checked_pseudo_class(element);

    case CSS::PseudoClass::Indeterminate:

        return matches_indeterminate_pseudo_class(element);

    case CSS::PseudoClass::Defined:

        return element.is_defined();

    case CSS::PseudoClass::Has:

        // :has() cannot be nested in a :has()

        if (selector_kind == SelectorKind::Relative)

            return false;

        // These selectors should be relative selectors (https://drafts.csswg.org/selectors-4/#relative-selector)

        for (auto& selector : pseudo_class.argument_selector_list) {

            if (matches_has_pseudo_class(selector, style_sheet_for_rule, element, shadow_host))

                return true;

        }

        return false;

    case CSS::PseudoClass::Is:

    case CSS::PseudoClass::Where:

        for (auto& selector : pseudo_class.argument_selector_list) {

            if (matches(selector, style_sheet_for_rule, element, shadow_host))

                return true;

        }

        return false;

    case CSS::PseudoClass::Not:

        for (auto& selector : pseudo_class.argument_selector_list) {

            if (matches(selector, style_sheet_for_rule, element, shadow_host))

                return false;

        }

        return true;

    case CSS::PseudoClass::NthChild:

    case CSS::PseudoClass::NthLastChild:

    case CSS::PseudoClass::NthOfType:

    case CSS::PseudoClass::NthLastOfType: {

        auto const step_size = pseudo_class.nth_child_pattern.step_size;

        auto const offset = pseudo_class.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."

        auto const* parent = element.parent_element();

        if (!parent)

            return false;

        auto matches_selector_list = [&style_sheet_for_rule, shadow_host](CSS::SelectorList const& list, DOM::Element const& element) {

            if (list.is_empty())

                return true;

            for (auto const& child_selector : list) {

                if (matches(child_selector, style_sheet_for_rule, element, shadow_host)) {

                    return true;

                }

            }

            return false;

        };

        int index = 1;

        switch (pseudo_class.type) {

        case CSS::PseudoClass::NthChild: {

            if (!matches_selector_list(pseudo_class.argument_selector_list, element))

                return false;

            for (auto* child = parent->first_child_of_type<DOM::Element>(); child && child != &element; child = child->next_element_sibling()) {

                if (matches_selector_list(pseudo_class.argument_selector_list, *child))

                    ++index;

            }

            break;

        }

        case CSS::PseudoClass::NthLastChild: {

            if (!matches_selector_list(pseudo_class.argument_selector_list, element))

                return false;

            for (auto* child = parent->last_child_of_type<DOM::Element>(); child && child != &element; child = child->previous_element_sibling()) {

                if (matches_selector_list(pseudo_class.argument_selector_list, *child))

                    ++index;

            }

            break;

        }

        case CSS::PseudoClass::NthOfType: {

            for (auto* child = previous_sibling_with_same_tag_name(element); child; child = previous_sibling_with_same_tag_name(*child))

                ++index;

            break;

        }

        case CSS::PseudoClass::NthLastOfType: {

            for (auto* child = next_sibling_with_same_tag_name(element); child; child = next_sibling_with_same_tag_name(*child))

                ++index;

            break;

        }

        default:

            VERIFY_NOT_REACHED();

        }

        // When "step_size == -1", selector represents first "offset" elements in document tree.

        if (step_size == -1)

            return !(offset <= 0 || index > offset);

        // When "step_size == 1", selector represents last "offset" elements in document tree.

        if (step_size == 1)

            return !(offset < 0 || index < offset);

        // When "step_size == 0", selector picks only the "offset" element.

        if (step_size == 0)

            return index == offset;

        // If both are negative, nothing can match.

        if (step_size < 0 && offset < 0)

            return false;

        // Like "a % b", but handles negative integers correctly.

        auto const canonical_modulo = [](int a, int b) -> int {

            int c = a % b;

            if ((c < 0 && b > 0) || (c > 0 && b < 0)) {

                c += b;

            }

            return c;

        };

        // When "step_size < 0", we start at "offset" and count backwards.

        if (step_size < 0)

            return index <= offset && canonical_modulo(index - offset, -step_size) == 0;

        // Otherwise, we start at "offset" and count forwards.

        return index >= offset && canonical_modulo(index - offset, step_size) == 0;

    }

    case CSS::PseudoClass::Playing: {

        if (!is<HTML::HTMLMediaElement>(element))

            return false;

        auto const& media_element = static_cast<HTML::HTMLMediaElement const&>(element);

        return !media_element.paused();

    }

    case CSS::PseudoClass::Paused: {

        if (!is<HTML::HTMLMediaElement>(element))

            return false;

        auto const& media_element = static_cast<HTML::HTMLMediaElement const&>(element);

        return media_element.paused();

    }

    case CSS::PseudoClass::Seeking: {

        if (!is<HTML::HTMLMediaElement>(element))

            return false;

        auto const& media_element = static_cast<HTML::HTMLMediaElement const&>(element);

        return media_element.seeking();

    }

    case CSS::PseudoClass::Muted: {

        if (!is<HTML::HTMLMediaElement>(element))

            return false;

        auto const& media_element = static_cast<HTML::HTMLMediaElement const&>(element);

        return media_element.muted();

    }

    case CSS::PseudoClass::VolumeLocked: {

        // FIXME: Currently we don't allow the user to specify an override volume, so this is always false.

        //        Once we do, implement this!

        return false;

    }

    case CSS::PseudoClass::Buffering: {

        if (!is<HTML::HTMLMediaElement>(element))

            return false;

        auto const& media_element = static_cast<HTML::HTMLMediaElement const&>(element);

        return media_element.blocked();

    }

    case CSS::PseudoClass::Stalled: {

        if (!is<HTML::HTMLMediaElement>(element))

            return false;

        auto const& media_element = static_cast<HTML::HTMLMediaElement const&>(element);

        return media_element.stalled();

    }

    case CSS::PseudoClass::Target:

        return element.is_target();

    case CSS::PseudoClass::TargetWithin: {

        auto* target_element = element.document().target_element();

        if (!target_element)

            return false;

        return element.is_inclusive_ancestor_of(*target_element);

    }

    case CSS::PseudoClass::Dir: {

        // "Values other than ltr and rtl are not invalid, but do not match anything."

        // - https://www.w3.org/TR/selectors-4/#the-dir-pseudo

        if (!first_is_one_of(pseudo_class.keyword, CSS::Keyword::Ltr, CSS::Keyword::Rtl))

            return false;

        switch (element.directionality()) {

        case DOM::Element::Directionality::Ltr:

            return pseudo_class.keyword == CSS::Keyword::Ltr;

        case DOM::Element::Directionality::Rtl:

            return pseudo_class.keyword == CSS::Keyword::Rtl;

        }

        VERIFY_NOT_REACHED();

    }

    case CSS::PseudoClass::ReadOnly:

        return !matches_read_write_pseudo_class(element);

    case CSS::PseudoClass::ReadWrite:

        return matches_read_write_pseudo_class(element);

    case CSS::PseudoClass::PlaceholderShown: {

        // https://html.spec.whatwg.org/multipage/semantics-other.html#selector-placeholder-shown

        //  The :placeholder-shown pseudo-class must match any element falling into one of the following categories:

        // - input elements that have a placeholder attribute whose value is currently being presented to the user.

        if (is<HTML::HTMLInputElement>(element) && element.has_attribute(HTML::AttributeNames::placeholder)) {

            auto const& input_element = static_cast<HTML::HTMLInputElement const&>(element);

            return input_element.placeholder_element() && input_element.placeholder_value().has_value();

        }

        // - FIXME: textarea elements that have a placeholder attribute whose value is currently being presented to the user.

        return false;

    }

    case CSS::PseudoClass::Open:

        return matches_open_state_pseudo_class(element, pseudo_class.type == CSS::PseudoClass::Open);

    case CSS::PseudoClass::Modal: {

        // https://drafts.csswg.org/selectors/#modal-state

        if (is<HTML::HTMLDialogElement>(element)) {

            auto const& dialog_element = static_cast<HTML::HTMLDialogElement const&>(element);

            return dialog_element.is_modal();

        }

        // FIXME: fullscreen elements are also modal.

        return false;

    }

    }

    return false;

}

static ALWAYS_INLINE bool matches_namespace(

    CSS::Selector::SimpleSelector::QualifiedName const& qualified_name,

    DOM::Element const& element,

    Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule)

{

    switch (qualified_name.namespace_type) {

    case CSS::Selector::SimpleSelector::QualifiedName::NamespaceType::Default:

        // "if no default namespace has been declared for selectors, this is equivalent to *|E."

        if (!style_sheet_for_rule.has_value() || !style_sheet_for_rule->default_namespace_rule())

            return true;

        // "Otherwise it is equivalent to ns|E where ns is the default namespace."

        return element.namespace_uri() == style_sheet_for_rule->default_namespace_rule()->namespace_uri();

    case CSS::Selector::SimpleSelector::QualifiedName::NamespaceType::None:

        // "elements with name E without a namespace"

        return !element.namespace_uri().has_value();

    case CSS::Selector::SimpleSelector::QualifiedName::NamespaceType::Any:

        // "elements with name E in any namespace, including those without a namespace"

        return true;

    case CSS::Selector::SimpleSelector::QualifiedName::NamespaceType::Named:

        // "elements with name E in namespace ns"

        // Unrecognized namespace prefixes are invalid, so don't match.

        // (We can't detect this at parse time, since a namespace rule may be inserted later.)

        // So, if we don't have a context to look up namespaces from, we fail to match.

        if (!style_sheet_for_rule.has_value())

            return false;

        auto selector_namespace = style_sheet_for_rule->namespace_uri(qualified_name.namespace_);

        return selector_namespace.has_value() && selector_namespace.value() == element.namespace_uri();

    }

    VERIFY_NOT_REACHED();

}

static inline bool matches(CSS::Selector::SimpleSelector const& component, Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule, DOM::Element const& element, JS::GCPtr<DOM::Element const> shadow_host, JS::GCPtr<DOM::ParentNode const> scope, SelectorKind selector_kind)

{

    switch (component.type) {

    case CSS::Selector::SimpleSelector::Type::Universal:

    case CSS::Selector::SimpleSelector::Type::TagName: {

        auto const& qualified_name = component.qualified_name();

        // Reject if the tag name doesn't match

        if (component.type == CSS::Selector::SimpleSelector::Type::TagName) {

            // See https://html.spec.whatwg.org/multipage/semantics-other.html#case-sensitivity-of-selectors

            if (element.document().document_type() == DOM::Document::Type::HTML) {

                if (qualified_name.name.lowercase_name != element.local_name())

                    return false;

            } else if (!Infra::is_ascii_case_insensitive_match(qualified_name.name.name, element.local_name())) {

                return false;

            }

        }

        return matches_namespace(qualified_name, element, style_sheet_for_rule);

    }

    case CSS::Selector::SimpleSelector::Type::Id:

        return component.name() == element.id();

    case CSS::Selector::SimpleSelector::Type::Class: {

        // Class selectors are matched case insensitively in quirks mode.

        // See: https://drafts.csswg.org/selectors-4/#class-html

        auto case_sensitivity = element.document().in_quirks_mode() ? CaseSensitivity::CaseInsensitive : CaseSensitivity::CaseSensitive;

        return element.has_class(component.name(), case_sensitivity);

    }

    case CSS::Selector::SimpleSelector::Type::Attribute:

        return matches_attribute(component.attribute(), style_sheet_for_rule, element);

    case CSS::Selector::SimpleSelector::Type::PseudoClass:

        return matches_pseudo_class(component.pseudo_class(), style_sheet_for_rule, element, shadow_host, scope, selector_kind);

    case CSS::Selector::SimpleSelector::Type::PseudoElement:

        // Pseudo-element matching/not-matching is handled in the top level matches().

        return true;

    case CSS::Selector::SimpleSelector::Type::Nesting:

        // We should only try to match selectors that have been absolutized!

        VERIFY_NOT_REACHED();

    }

    VERIFY_NOT_REACHED();

}

static inline bool matches(CSS::Selector const& selector, Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule, int component_list_index, DOM::Element const& element, JS::GCPtr<DOM::Element const> shadow_host, JS::GCPtr<DOM::ParentNode const> scope, SelectorKind selector_kind)

{

    auto& compound_selector = selector.compound_selectors()[component_list_index];

    for (auto& simple_selector : compound_selector.simple_selectors) {

        if (!matches(simple_selector, style_sheet_for_rule, element, shadow_host, scope, selector_kind)) {

            return false;

        }

    }

    // Always matches because we assume that element is already relative to its anchor

    if (selector_kind == SelectorKind::Relative && component_list_index == 0)

        return true;

    switch (compound_selector.combinator) {

    case CSS::Selector::Combinator::None:

        VERIFY(selector_kind != SelectorKind::Relative);

        return true;

    case CSS::Selector::Combinator::Descendant:

        VERIFY(component_list_index != 0);

        for (auto ancestor = traverse_up(element, shadow_host); ancestor; ancestor = traverse_up(ancestor, shadow_host)) {

            if (!is<DOM::Element>(*ancestor))

                continue;

            if (matches(selector, style_sheet_for_rule, component_list_index - 1, static_cast<DOM::Element const&>(*ancestor), shadow_host, scope, selector_kind))

                return true;

        }

        return false;

    case CSS::Selector::Combinator::ImmediateChild: {

        VERIFY(component_list_index != 0);

        auto parent = traverse_up(element, shadow_host);

        if (!parent || !parent->is_element())

            return false;

        return matches(selector, style_sheet_for_rule, component_list_index - 1, static_cast<DOM::Element const&>(*parent), shadow_host, scope, selector_kind);

    }

    case CSS::Selector::Combinator::NextSibling:

        VERIFY(component_list_index != 0);

        if (auto* sibling = element.previous_element_sibling())

            return matches(selector, style_sheet_for_rule, component_list_index - 1, *sibling, shadow_host, scope, selector_kind);

        return false;

    case CSS::Selector::Combinator::SubsequentSibling:

        VERIFY(component_list_index != 0);

        for (auto* sibling = element.previous_element_sibling(); sibling; sibling = sibling->previous_element_sibling()) {

            if (matches(selector, style_sheet_for_rule, component_list_index - 1, *sibling, shadow_host, scope, selector_kind))

                return true;

        }

        return false;

    case CSS::Selector::Combinator::Column:

        TODO();

    }

    VERIFY_NOT_REACHED();

}

bool matches(CSS::Selector const& selector, Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule, DOM::Element const& element, JS::GCPtr<DOM::Element const> shadow_host, Optional<CSS::Selector::PseudoElement::Type> pseudo_element, JS::GCPtr<DOM::ParentNode const> scope, SelectorKind selector_kind)

{

    VERIFY(!selector.compound_selectors().is_empty());

    if (pseudo_element.has_value() && selector.pseudo_element().has_value() && selector.pseudo_element().value().type() != pseudo_element)

        return false;

    if (!pseudo_element.has_value() && selector.pseudo_element().has_value())

        return false;

    return matches(selector, style_sheet_for_rule, selector.compound_selectors().size() - 1, element, shadow_host, scope, selector_kind);

}

static bool fast_matches_simple_selector(CSS::Selector::SimpleSelector const& simple_selector, Optional<CSS::CSSStyleSheet const&> style_sheet_for_rule, DOM::Element const& element, JS::GCPtr<DOM::Element const> shadow_host)

{

    switch (simple_selector.type) {

    case CSS::Selector::SimpleSelector::Type::Universal:

        return matches_namespace(simple_selector.qualified_name(), element, style_sheet_for_rule);

    case CSS::Selector::SimpleSelector::Type::TagName:

        if (element.document().document_type() == DOM::Document::Type::HTML) {

            if (simple_selector.qualified_name().name.lowercase_name != element.local_name())

                return false;

        } else if (!Infra::is_ascii_case_insensitive_match(simple_selector.qualified_name().name.name, element.local_name())) {

            return false;

        }

        return matches_namespace(simple_selector.qualified_name(), element, style_sheet_for_rule);

    case CSS::Selector::SimpleSelector::Type::Class: {

        // Class selectors are matched case insensitively in quirks mode.

        // See: https://drafts.csswg.org/selectors-4/#class-html

        auto case_sensitivity = element.document().in_quirks_mode() ? CaseSensitivity::CaseInsensitive : CaseSensitivity::CaseSensitive;

        return element.has_class(simple_selector.name(), case_sensitivity);

    }

    case CSS::Selector::SimpleSelector::Type::Id:

        return simple_selector.name() == element.id();

    case CSS::Selector::SimpleSelector::Type::Attribute:

        return matches_attribute(simple_selector.attribute(), style_sheet_for_rule, element);

    case CSS::Selector::SimpleSelector::Type::PseudoClass:

        return matches_pseudo_class(simple_selector.pseudo_class(), style_sheet_for_rule, element, shadow_host, nullptr, SelectorKind::Normal);