/*
 * Copyright (c) 2025, Aliaksandr Kalenik <kalenik.aliaksandr@gmail.com>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 */

#include <AK/Assertions.h>
#include <AK/GenericShorthands.h>
#include <AK/Optional.h>
#include <LibWeb/CSS/Selector.h>
#include <LibWeb/CSS/StyleInvalidationData.h>

namespace Web::CSS {

enum class SimpleSelectorGroupPosition {
    Rightmost,
    NonRightmost,
};

enum class InvalidationSetPurpose {
    TriggerProperties,
    SubjectMatchSet,
};

static NonnullRefPtr<InvalidationPlan> copy_invalidation_plan(InvalidationPlan const& plan);

// Interned payload plans are at least pointer-aligned, so the low bits of their addresses are free to tag rule
// properties into the merge index keys below.
static_assert(alignof(InvalidationPlan) >= 4);

// If you add a field to InvalidationPlan, update operator==(), hash(), and include_all_from() to account for it,
// then adjust this assertion. Missing one of them would make interning conflate distinct plans and cause
// under-invalidation.
static_assert(sizeof(void*) != 8 || sizeof(InvalidationPlan) == 104);

static constexpr size_t rule_merge_index_threshold = 8;

static FlatPtr descendant_rule_merge_key(DescendantInvalidationRule const& rule)
{
    return bit_cast<FlatPtr>(rule.payload.ptr()) | (rule.match_any ? 1 : 0);
}

static FlatPtr sibling_rule_merge_key(SiblingInvalidationRule const& rule)
{
    return bit_cast<FlatPtr>(rule.payload.ptr()) | (rule.match_any ? 1 : 0) | (rule.reach == SiblingInvalidationReach::Subsequent ? 2 : 0);
}

void InvalidationPlan::add_descendant_rule(DescendantInvalidationRule rule)
{
    VERIFY(!m_interned);
    m_hash = {};

    if (!m_rule_merge_index && descendant_rules.size() + sibling_rules.size() >= rule_merge_index_threshold) {
        m_rule_merge_index = make<RuleMergeIndex>();
        for (size_t i = 0; i < descendant_rules.size(); ++i)
            m_rule_merge_index->descendant_rule_indexes.ensure(descendant_rule_merge_key(descendant_rules[i]), [i] { return i; });
        for (size_t i = 0; i < sibling_rules.size(); ++i)
            m_rule_merge_index->sibling_rule_indexes.ensure(sibling_rule_merge_key(sibling_rules[i]), [i] { return i; });
    }

    if (m_rule_merge_index) {
        auto key = descendant_rule_merge_key(rule);
        if (auto existing_index = m_rule_merge_index->descendant_rule_indexes.get(key); existing_index.has_value()) {
            auto& existing_rule = descendant_rules[*existing_index];
            if (!existing_rule.match_any)
                existing_rule.match_set.include_all_from(rule.match_set);
            return;
        }
        m_rule_merge_index->descendant_rule_indexes.set(key, descendant_rules.size());
        descendant_rules.append(move(rule));
        return;
    }

    for (auto& existing_rule : descendant_rules) {
        if (existing_rule.match_any != rule.match_any)
            continue;
        if (existing_rule.payload != rule.payload && *existing_rule.payload != *rule.payload)
            continue;

        if (existing_rule.match_any)
            return;

        existing_rule.match_set.include_all_from(rule.match_set);
        return;
    }
    descendant_rules.append(move(rule));
}

void InvalidationPlan::add_sibling_rule(SiblingInvalidationRule rule)
{
    VERIFY(!m_interned);
    m_hash = {};

    if (!m_rule_merge_index && descendant_rules.size() + sibling_rules.size() >= rule_merge_index_threshold) {
        m_rule_merge_index = make<RuleMergeIndex>();
        for (size_t i = 0; i < descendant_rules.size(); ++i)
            m_rule_merge_index->descendant_rule_indexes.ensure(descendant_rule_merge_key(descendant_rules[i]), [i] { return i; });
        for (size_t i = 0; i < sibling_rules.size(); ++i)
            m_rule_merge_index->sibling_rule_indexes.ensure(sibling_rule_merge_key(sibling_rules[i]), [i] { return i; });
    }

    if (m_rule_merge_index) {
        auto key = sibling_rule_merge_key(rule);
        if (auto existing_index = m_rule_merge_index->sibling_rule_indexes.get(key); existing_index.has_value()) {
            auto& existing_rule = sibling_rules[*existing_index];
            if (!existing_rule.match_any)
                existing_rule.match_set.include_all_from(rule.match_set);
            return;
        }
        m_rule_merge_index->sibling_rule_indexes.set(key, sibling_rules.size());
        sibling_rules.append(move(rule));
        return;
    }

    for (auto& existing_rule : sibling_rules) {
        if (existing_rule.reach != rule.reach)
            continue;
        if (existing_rule.match_any != rule.match_any)
            continue;
        if (existing_rule.payload != rule.payload && *existing_rule.payload != *rule.payload)
            continue;

        if (existing_rule.match_any)
            return;

        existing_rule.match_set.include_all_from(rule.match_set);
        return;
    }
    sibling_rules.append(move(rule));
}

void InvalidationPlan::add_guarded_rule(GuardedInvalidationRule rule)
{
    VERIFY(!m_interned);
    m_hash = {};

    for (auto& existing_rule : guarded_rules) {
        if (existing_rule.guard != rule.guard)
            continue;

        // Payloads are immutable, so merging guards means building a merged payload copy.
        auto merged_payload = copy_invalidation_plan(*existing_rule.payload);
        merged_payload->include_all_from(*rule.payload);
        existing_rule.payload = move(merged_payload);
        return;
    }
    guarded_rules.append(move(rule));
}

bool InvalidationPlan::is_empty() const
{
    return !invalidate_self && !invalidate_whole_subtree && !invalidate_self_and_structurally_affected_siblings && descendant_rules.is_empty() && sibling_rules.is_empty() && guarded_rules.is_empty();
}

bool InvalidationGuard::operator==(InvalidationGuard const& other) const
{
    return property_sets == other.property_sets;
}

bool GuardedInvalidationRule::operator==(GuardedInvalidationRule const& other) const
{
    return guard == other.guard
        && (payload == other.payload || *payload == *other.payload);
}

bool DescendantInvalidationRule::operator==(DescendantInvalidationRule const& other) const
{
    return match_set == other.match_set
        && match_any == other.match_any
        && (payload == other.payload || *payload == *other.payload);
}

bool SiblingInvalidationRule::operator==(SiblingInvalidationRule const& other) const
{
    return reach == other.reach
        && match_set == other.match_set
        && match_any == other.match_any
        && (payload == other.payload || *payload == *other.payload);
}

template<typename Rule>
static bool rule_lists_are_equal_ignoring_order(Vector<Rule> const& a, Vector<Rule> const& b)
{
    if (a.size() != b.size())
        return false;

    Vector<bool> matched_rules;
    matched_rules.resize(b.size());

    for (auto const& rule : a) {
        bool found_match = false;
        for (size_t i = 0; i < b.size(); ++i) {
            if (matched_rules[i])
                continue;
            if (!(rule == b[i]))
                continue;
            matched_rules[i] = true;
            found_match = true;
            break;
        }
        if (!found_match)
            return false;
    }

    return true;
}

bool InvalidationPlan::operator==(InvalidationPlan const& other) const
{
    if (invalidate_self != other.invalidate_self)
        return false;
    if (invalidate_whole_subtree != other.invalidate_whole_subtree)
        return false;
    if (invalidate_self_and_structurally_affected_siblings != other.invalidate_self_and_structurally_affected_siblings)
        return false;

    return rule_lists_are_equal_ignoring_order(descendant_rules, other.descendant_rules)
        && rule_lists_are_equal_ignoring_order(sibling_rules, other.sibling_rules)
        && rule_lists_are_equal_ignoring_order(guarded_rules, other.guarded_rules);
}

void InvalidationPlan::include_all_from(InvalidationPlan const& other)
{
    VERIFY(!m_interned);
    m_hash = {};
    invalidate_self |= other.invalidate_self;
    invalidate_self_and_structurally_affected_siblings |= other.invalidate_self_and_structurally_affected_siblings;

    if (invalidate_whole_subtree) {
        invalidate_self_and_structurally_affected_siblings = false;
        return;
    }

    if (other.invalidate_whole_subtree) {
        invalidate_whole_subtree = true;
        invalidate_self_and_structurally_affected_siblings = false;
        descendant_rules.clear();
        sibling_rules.clear();
        guarded_rules.clear();
        m_rule_merge_index = nullptr;
        return;
    }

    for (auto const& descendant_rule : other.descendant_rules)
        add_descendant_rule(descendant_rule);
    for (auto const& sibling_rule : other.sibling_rules)
        add_sibling_rule(sibling_rule);
    for (auto const& guarded_rule : other.guarded_rules)
        add_guarded_rule(guarded_rule);
}

u32 InvalidationPlan::hash() const
{
    if (m_hash.has_value())
        return *m_hash;

    // Payloads are hashed by pointer. This is consistent with operator== for plans whose payloads are interned:
    // structurally equal interned payloads share one pointer, and interning happens bottom-up.
    u32 rule_hash_sum = 0;
    u32 rule_hash_xor = 0;
    auto accumulate_rule_hash = [&](u32 rule_hash) {
        rule_hash_sum += rule_hash;
        rule_hash_xor ^= pair_int_hash(rule_hash, 0x9e3779b9);
    };
    for (auto const& rule : descendant_rules)
        accumulate_rule_hash(pair_int_hash(ptr_hash(rule.payload.ptr()), pair_int_hash(rule.match_set.hash(), rule.match_any)));
    for (auto const& rule : sibling_rules)
        accumulate_rule_hash(pair_int_hash(pair_int_hash(ptr_hash(rule.payload.ptr()), to_underlying(rule.reach)), pair_int_hash(rule.match_set.hash(), rule.match_any)));
    for (auto const& rule : guarded_rules) {
        u32 guard_hash = 0;
        for (auto const& property_set : rule.guard.property_sets)
            guard_hash = pair_int_hash(guard_hash, property_set.hash());
        accumulate_rule_hash(pair_int_hash(guard_hash, ptr_hash(rule.payload.ptr())));
    }

    u32 hash = pair_int_hash(invalidate_self, invalidate_whole_subtree);
    hash = pair_int_hash(hash, invalidate_self_and_structurally_affected_siblings);
    hash = pair_int_hash(hash, descendant_rules.size() + sibling_rules.size() + guarded_rules.size());
    hash = pair_int_hash(hash, rule_hash_sum);
    hash = pair_int_hash(hash, rule_hash_xor);
    m_hash = hash;
    return hash;
}

NonnullRefPtr<InvalidationPlan const> StyleInvalidationData::intern_invalidation_plan(NonnullRefPtr<InvalidationPlan> plan)
{
    VERIFY(!m_finished_building);

    // Only per-property root plans carry guarded rules, and those are never used as payloads.
    VERIFY(plan->guarded_rules.is_empty());

    // Plans are interned bottom-up: hashing payloads by pointer is only consistent with the structural operator==
    // if structurally equal payloads have already been collapsed to one pointer.
    for (auto const& rule : plan->descendant_rules)
        VERIFY(rule.payload->m_interned);
    for (auto const& rule : plan->sibling_rules)
        VERIFY(rule.payload->m_interned);

    auto& bucket = m_interned_invalidation_plans.ensure(plan->hash(), [] { return Vector<NonnullRefPtr<InvalidationPlan const>> {}; });
    for (auto const& existing_plan : bucket) {
        if (*existing_plan == *plan)
            return existing_plan;
    }
    plan->m_interned = true;
    NonnullRefPtr<InvalidationPlan const> interned_plan = move(plan);
    bucket.append(interned_plan);
    return interned_plan;
}

InvalidationPlan& StyleInvalidationData::ensure_invalidation_plan_being_built(InvalidationSet::Property const& property)
{
    VERIFY(!m_finished_building);
    return m_invalidation_plans_being_built.ensure(property, [] { return InvalidationPlan::create(); });
}

void StyleInvalidationData::did_finish_building()
{
    VERIFY(!m_finished_building);
    m_interned_invalidation_plans.clear();
    for (auto& it : m_invalidation_plans_being_built) {
        it.value->clear_rule_merge_index();
        for (auto const& guarded_rule : it.value->guarded_rules)
            guarded_rule.payload->clear_rule_merge_index();
        m_invalidation_plans.set(it.key, move(it.value));
    }
    m_invalidation_plans_being_built.clear();
    m_finished_building = true;
}

// Iterates over the given selector, grouping consecutive simple selectors that have no combinator (Combinator::None).
// For example, given "div:not(.a) + .b[foo]", the callback is invoked twice:
// once for "div:not(.a)" and once for ".b[foo]".
template<typename Callback>
static void for_each_consecutive_simple_selector_group(Selector const& selector, Callback callback)
{
    auto const& compound_selectors = selector.compound_selectors();
    int compound_selector_index = compound_selectors.size() - 1;
    Vector<Selector::SimpleSelector const&> simple_selectors;
    Selector::Combinator combinator = Selector::Combinator::None;
    bool is_rightmost = true;
    while (compound_selector_index >= 0) {
        if (!simple_selectors.is_empty()) {
            callback(simple_selectors, combinator, is_rightmost);
            simple_selectors.clear();
            is_rightmost = false;
        }

        auto const& compound_selector = compound_selectors[compound_selector_index];
        for (auto const& simple_selector : compound_selector.simple_selectors)
            simple_selectors.append(simple_selector);
        combinator = compound_selector.combinator;

        --compound_selector_index;
    }
    if (!simple_selectors.is_empty())
        callback(simple_selectors, combinator, is_rightmost);
}

static HasArgumentScope classify_has_argument_scope(Selector const& selector)
{
    if (selector.compound_selectors().is_empty())
        return HasArgumentScope::Complex;

    auto leftmost_combinator = selector.compound_selectors().first().combinator;
    switch (leftmost_combinator) {
    case Selector::Combinator::Descendant:
        return HasArgumentScope::AllDescendants;
    case Selector::Combinator::ImmediateChild:
        return selector.compound_selectors().size() == 1 ? HasArgumentScope::ChildrenOnly : HasArgumentScope::Complex;
    case Selector::Combinator::NextSibling:
        return selector.compound_selectors().size() == 1 ? HasArgumentScope::NextSiblingOnly : HasArgumentScope::Complex;
    case Selector::Combinator::SubsequentSibling:
        return selector.compound_selectors().size() == 1 ? HasArgumentScope::AllFollowingSiblings : HasArgumentScope::Complex;
    default:
        return HasArgumentScope::Complex;
    }
}

template<typename Key>
static void append_has_invalidation_metadata(HashMap<Key, Vector<HasInvalidationMetadata>>& map, Key const& key, HasInvalidationMetadata const& metadata)
{
    auto& bucket = map.ensure(key, [] { return Vector<HasInvalidationMetadata> {}; });
    if (!bucket.contains_slow(metadata))
        bucket.append(metadata);
}

template<typename Callback>
static void for_each_attribute_name_for_invalidation(Selector::SimpleSelector::Attribute const& attribute, Callback callback)
{
    auto const& attribute_name = attribute.qualified_name.name.name;
    callback(attribute_name);

    auto const& lowercase_attribute_name = attribute.qualified_name.name.lowercase_name;
    if (lowercase_attribute_name != attribute_name)
        callback(lowercase_attribute_name);
}

static void collect_attribute_invalidation_properties(Selector::SimpleSelector::Attribute const& attribute, InvalidationSet& property_set)
{
    for_each_attribute_name_for_invalidation(attribute, [&](auto const& name) {
        property_set.set_needs_invalidate_attribute(name);
    });
}

static bool selector_contains_featureless_subtree_sensitive_selector(Selector const&);

static bool pseudo_class_can_be_used_as_has_invalidation_feature(PseudoClass pseudo_class)
{
    return first_is_one_of(pseudo_class,
        PseudoClass::Enabled,
        PseudoClass::Disabled,
        PseudoClass::Defined,
        PseudoClass::PlaceholderShown,
        PseudoClass::Checked,
        PseudoClass::Required,
        PseudoClass::Optional,
        PseudoClass::Valid,
        PseudoClass::Invalid,
        PseudoClass::UserValid,
        PseudoClass::UserInvalid,
        PseudoClass::Link,
        PseudoClass::AnyLink,
        PseudoClass::LocalLink,
        PseudoClass::Hover,
        PseudoClass::Active,
        PseudoClass::Focus,
        PseudoClass::FocusVisible,
        PseudoClass::FocusWithin,
        PseudoClass::Target,
        PseudoClass::Open);
}

static void collect_properties_used_in_has(Selector::SimpleSelector const& selector, StyleInvalidationData& style_invalidation_data, Optional<HasInvalidationMetadata> metadata)
{
    switch (selector.type) {
    case Selector::SimpleSelector::Type::Id: {
        if (metadata.has_value())
            append_has_invalidation_metadata(style_invalidation_data.ids_used_in_has_selectors, selector.id_name(), *metadata);
        break;
    }
    case Selector::SimpleSelector::Type::Class: {
        if (metadata.has_value())
            append_has_invalidation_metadata(style_invalidation_data.class_names_used_in_has_selectors, selector.class_name(), *metadata);
        break;
    }
    case Selector::SimpleSelector::Type::Attribute: {
        if (metadata.has_value()) {
            for_each_attribute_name_for_invalidation(selector.attribute(), [&](auto const& name) {
                append_has_invalidation_metadata(style_invalidation_data.attribute_names_used_in_has_selectors, name, *metadata);
            });
        }
        break;
    }
    case Selector::SimpleSelector::Type::TagName: {
        if (metadata.has_value())
            append_has_invalidation_metadata(style_invalidation_data.tag_names_used_in_has_selectors, selector.qualified_name().name.lowercase_name, *metadata);
        break;
    }
    case Selector::SimpleSelector::Type::PseudoClass: {
        auto const& pseudo_class = selector.pseudo_class();
        if (pseudo_class_can_be_used_as_has_invalidation_feature(pseudo_class.type)) {
            if (metadata.has_value())
                append_has_invalidation_metadata(style_invalidation_data.pseudo_classes_used_in_has_selectors, pseudo_class.type, *metadata);
        } else if (metadata.has_value() && !first_is_one_of(pseudo_class.type, PseudoClass::Has, PseudoClass::Is, PseudoClass::Where)) {
            // The structural subtree filter can only compare concrete features and the pseudo-classes listed above.
            // For other pseudo-classes, such as :focus, :default, and :valid, a featureless node can still start or
            // stop matching. Keep the old conservative walk instead of trying to probe them generically.
            style_invalidation_data.has_selectors_sensitive_to_featureless_subtree_changes = true;
        }
        for (auto const& child_selector : pseudo_class.argument_selector_list) {
            Optional<HasInvalidationMetadata> child_metadata = metadata;
            if (pseudo_class.type == PseudoClass::Has) {
                child_metadata = HasInvalidationMetadata {
                    .relative_selector = child_selector.ptr(),
                    .scope = classify_has_argument_scope(*child_selector),
                };
                // These selectors can match because a featureless node is inserted, removed, or moved.
                // Since there is no concrete tag/class/id/attribute/pseudo-class feature to compare against
                // later, structural invalidation must keep walking conservatively for them.
                if (selector_contains_featureless_subtree_sensitive_selector(*child_selector))
                    style_invalidation_data.has_selectors_sensitive_to_featureless_subtree_changes = true;
            }
            for (auto const& compound_selector : child_selector->compound_selectors()) {
                for (auto const& simple_selector : compound_selector.simple_selectors)
                    collect_properties_used_in_has(simple_selector, style_invalidation_data, child_metadata);
            }
        }
        break;
    }
    case Selector::SimpleSelector::Type::PseudoElement: {
        // Pseudo-elements like ::slotted(.x:has(...)) carry a compound selector argument whose contents need the same
        // recursive collection.
        auto const& pseudo_element = selector.pseudo_element();
        if (pseudo_element.type() == PseudoElement::Slotted) {
            for (auto const& compound_selector : pseudo_element.compound_selector().compound_selectors()) {
                for (auto const& simple_selector : compound_selector.simple_selectors)
                    collect_properties_used_in_has(simple_selector, style_invalidation_data, metadata);
            }
        }
        break;
    }
    default:
        break;
    }
}

static bool simple_selector_is_featureless_subtree_sensitive(Selector::SimpleSelector const& selector)
{
    switch (selector.type) {
    case Selector::SimpleSelector::Type::Universal:
        return true;
    case Selector::SimpleSelector::Type::PseudoClass: {
        auto const& pseudo_class = selector.pseudo_class();
        switch (pseudo_class.type) {
        case PseudoClass::Not:
        case PseudoClass::Empty:
        case PseudoClass::FirstChild:
        case PseudoClass::LastChild:
        case PseudoClass::OnlyChild:
        case PseudoClass::FirstOfType:
        case PseudoClass::LastOfType:
        case PseudoClass::OnlyOfType:
        case PseudoClass::NthChild:
        case PseudoClass::NthLastChild:
        case PseudoClass::NthOfType:
        case PseudoClass::NthLastOfType:
            return true;
        case PseudoClass::Is:
        case PseudoClass::Where:
            for (auto const& child_selector : pseudo_class.argument_selector_list) {
                if (selector_contains_featureless_subtree_sensitive_selector(*child_selector))
                    return true;
            }
            return false;
        default:
            return false;
        }
    }
    default:
        return false;
    }
}

static bool selector_contains_featureless_subtree_sensitive_selector(Selector const& selector)
{
    for (auto const& compound_selector : selector.compound_selectors()) {
        for (auto const& simple_selector : compound_selector.simple_selectors) {
            if (simple_selector_is_featureless_subtree_sensitive(simple_selector))
                return true;
        }
    }
    return false;
}

static bool selector_contains_sibling_combinator(Selector const& selector)
{
    for (auto const& compound_selector : selector.compound_selectors()) {
        if (compound_selector.combinator == Selector::Combinator::NextSibling
            || compound_selector.combinator == Selector::Combinator::SubsequentSibling) {
            return true;
        }
    }
    return false;
}

static InvalidationSet build_invalidation_sets_for_selector_impl(StyleInvalidationData& style_invalidation_data, Selector const& selector, InsideNthChildPseudoClass inside_nth_child_pseudo_class, InvalidationPlan const& root_invalidation_plan, InvalidationSetPurpose purpose = InvalidationSetPurpose::SubjectMatchSet);

static void add_invalidation_sets_to_cover_scope_leakage_of_relative_selector_in_has_pseudo_class(Selector const& selector, StyleInvalidationData& style_invalidation_data);

static bool should_register_invalidation_property(InvalidationSet::Property const& property)
{
    return !AK::first_is_one_of(property.type, InvalidationSet::Property::Type::InvalidateSelf, InvalidationSet::Property::Type::InvalidateWholeSubtree);
}

static void collect_guard_properties_for_simple_selector(Selector::SimpleSelector const&, InvalidationSet&);
static void build_invalidation_sets_for_simple_selector_impl(Selector::SimpleSelector const&, InvalidationSet&, ExcludePropertiesNestedInNotPseudoClass, StyleInvalidationData&, InsideNthChildPseudoClass, SimpleSelectorGroupPosition, InvalidationPlan const&, InvalidationSetPurpose);

static Optional<InvalidationSet> build_invalidation_guard_property_set_for_selector_subject(Selector const& selector)
{
    if (selector.compound_selectors().is_empty())
        return {};

    InvalidationSet property_set;
    for (auto const& simple_selector : selector.compound_selectors().last().simple_selectors)
        collect_guard_properties_for_simple_selector(simple_selector, property_set);
    if (property_set.is_empty())
        return {};
    return property_set;
}

static void collect_guard_properties_for_simple_selector(Selector::SimpleSelector const& selector, InvalidationSet& property_set)
{
    switch (selector.type) {
    case Selector::SimpleSelector::Type::Class:
        property_set.set_needs_invalidate_class(selector.class_name());
        break;
    case Selector::SimpleSelector::Type::Id:
        property_set.set_needs_invalidate_id(selector.id_name());
        break;
    case Selector::SimpleSelector::Type::TagName:
        property_set.set_needs_invalidate_tag_name(selector.qualified_name().name.lowercase_name);
        break;
    case Selector::SimpleSelector::Type::Attribute:
        collect_attribute_invalidation_properties(selector.attribute(), property_set);
        break;
    case Selector::SimpleSelector::Type::PseudoClass: {
        auto const& pseudo_class = selector.pseudo_class();
        if (pseudo_class.type == PseudoClass::Is || pseudo_class.type == PseudoClass::Where) {
            InvalidationSet selector_list_property_set;
            for (auto const& nested_selector : pseudo_class.argument_selector_list) {
                auto nested_property_set = build_invalidation_guard_property_set_for_selector_subject(*nested_selector);
                if (!nested_property_set.has_value())
                    return;
                selector_list_property_set.include_all_from(*nested_property_set);
            }
            property_set.include_all_from(selector_list_property_set);
        }
        break;
    }
    default:
        break;
    }
}

static InvalidationGuard build_invalidation_guard_for_simple_selectors(Vector<Selector::SimpleSelector const&> const& simple_selectors)
{
    InvalidationGuard guard;
    for (auto const& simple_selector : simple_selectors) {
        InvalidationSet property_set;
        collect_guard_properties_for_simple_selector(simple_selector, property_set);
        if (!property_set.is_empty())
            guard.property_sets.append(move(property_set));
    }
    return guard;
}

static InvalidationSet build_invalidation_set_for_simple_selectors(Vector<Selector::SimpleSelector const&> const& simple_selectors, ExcludePropertiesNestedInNotPseudoClass exclude_properties_nested_in_not_pseudo_class, StyleInvalidationData& style_invalidation_data, InsideNthChildPseudoClass inside_nth_child_pseudo_class, SimpleSelectorGroupPosition simple_selector_group_position, InvalidationPlan const& root_invalidation_plan, InvalidationSetPurpose purpose)
{
    InvalidationSet invalidation_set;
    for (auto const& simple_selector : simple_selectors)
        build_invalidation_sets_for_simple_selector_impl(simple_selector, invalidation_set, exclude_properties_nested_in_not_pseudo_class, style_invalidation_data, inside_nth_child_pseudo_class, simple_selector_group_position, root_invalidation_plan, purpose);
    return invalidation_set;
}

static bool simple_selector_group_matches_any(Vector<Selector::SimpleSelector const&> const& simple_selectors)
{
    return simple_selectors.size() == 1 && simple_selectors.first().type == Selector::SimpleSelector::Type::Universal;
}

static NonnullRefPtr<InvalidationPlan> make_invalidate_self_invalidation()
{
    auto invalidation = InvalidationPlan::create();
    invalidation->invalidate_self = true;
    return invalidation;
}

static NonnullRefPtr<InvalidationPlan> make_invalidate_whole_subtree_invalidation()
{
    auto invalidation = InvalidationPlan::create();
    invalidation->invalidate_whole_subtree = true;
    return invalidation;
}

static NonnullRefPtr<InvalidationPlan> copy_invalidation_plan(InvalidationPlan const& plan)
{
    auto copy = InvalidationPlan::create();
    copy->include_all_from(plan);
    return copy;
}

static void add_invalidation_plan_for_properties(StyleInvalidationData& style_invalidation_data, InvalidationSet const& invalidation_properties, InvalidationPlan const& plan, InvalidationGuard const& guard = {})
{
    invalidation_properties.for_each_property([&](auto const& invalidation_property) {
        if (!should_register_invalidation_property(invalidation_property))
            return IterationDecision::Continue;

        auto& stored_invalidation = style_invalidation_data.ensure_invalidation_plan_being_built(invalidation_property);
        if (invalidation_property.type != InvalidationSet::Property::Type::PseudoClass || guard.is_empty()) {
            stored_invalidation.include_all_from(plan);
        } else {
            GuardedInvalidationRule guarded_rule {
                .guard = guard,
                .payload = copy_invalidation_plan(plan),
            };
            stored_invalidation.add_guarded_rule(move(guarded_rule));
        }
        return IterationDecision::Continue;
    });
}

struct SelectorRighthand {
    InvalidationSet subject_match_set;
    bool subject_matches_any { false };
    NonnullRefPtr<InvalidationPlan const> payload;
};

static NonnullRefPtr<InvalidationPlan const> build_invalidation_for_combinator(Selector::Combinator combinator, SelectorRighthand const& righthand, StyleInvalidationData& style_invalidation_data)
{
    if (combinator == Selector::Combinator::PseudoElement)
        return righthand.payload;

    if (righthand.payload->invalidate_whole_subtree || (!righthand.subject_matches_any && righthand.subject_match_set.is_empty()))
        return style_invalidation_data.intern_invalidation_plan(make_invalidate_whole_subtree_invalidation());

    auto invalidation = InvalidationPlan::create();
    switch (combinator) {
    case Selector::Combinator::ImmediateChild:
    case Selector::Combinator::Descendant:
        invalidation->add_descendant_rule({ righthand.subject_match_set, righthand.subject_matches_any, righthand.payload });
        break;
    case Selector::Combinator::NextSibling:
        invalidation->add_sibling_rule({ SiblingInvalidationReach::Adjacent, righthand.subject_match_set, righthand.subject_matches_any, righthand.payload });
        break;
    case Selector::Combinator::SubsequentSibling:
        invalidation->add_sibling_rule({ SiblingInvalidationReach::Subsequent, righthand.subject_match_set, righthand.subject_matches_any, righthand.payload });
        break;
    default:
        invalidation->invalidate_whole_subtree = true;
        break;
    }
    return style_invalidation_data.intern_invalidation_plan(move(invalidation));
}

static void build_invalidation_sets_for_simple_selector_impl(Selector::SimpleSelector const& selector, InvalidationSet& invalidation_set, ExcludePropertiesNestedInNotPseudoClass exclude_properties_nested_in_not_pseudo_class, StyleInvalidationData& style_invalidation_data, InsideNthChildPseudoClass inside_nth_child_selector, SimpleSelectorGroupPosition simple_selector_group_position, InvalidationPlan const& root_invalidation_plan, InvalidationSetPurpose purpose)
{
    switch (selector.type) {
    case Selector::SimpleSelector::Type::Class:
        invalidation_set.set_needs_invalidate_class(selector.class_name());
        break;
    case Selector::SimpleSelector::Type::Id:
        invalidation_set.set_needs_invalidate_id(selector.id_name());
        break;
    case Selector::SimpleSelector::Type::TagName:
        invalidation_set.set_needs_invalidate_tag_name(selector.qualified_name().name.lowercase_name);
        break;
    case Selector::SimpleSelector::Type::Attribute:
        collect_attribute_invalidation_properties(selector.attribute(), invalidation_set);
        break;
    case Selector::SimpleSelector::Type::PseudoClass: {
        auto const& pseudo_class = selector.pseudo_class();
        switch (pseudo_class.type) {
        case PseudoClass::Enabled:
        case PseudoClass::Defined:
        case PseudoClass::Disabled:
        case PseudoClass::Empty:
        case PseudoClass::PlaceholderShown:
        case PseudoClass::Checked:
        case PseudoClass::Has: {
            for (auto const& nested_selector : pseudo_class.argument_selector_list)
                add_invalidation_sets_to_cover_scope_leakage_of_relative_selector_in_has_pseudo_class(*nested_selector, style_invalidation_data);
            [[fallthrough]];
        }
        case PseudoClass::Link:
        case PseudoClass::AnyLink:
        case PseudoClass::LocalLink:
        case PseudoClass::Required:
        case PseudoClass::Optional:
        case PseudoClass::Valid:
        case PseudoClass::Invalid:
        case PseudoClass::UserValid:
        case PseudoClass::UserInvalid:
        // OPTIMIZATION: Interaction-state pseudo-classes match at most a handful of elements at any
        //               given time (the hovered element, the focused element, and ancestors thereof
        //               for :focus-within). Treating them as targetable lets a stylesheet add or
        //               remove that has, e.g., a `:hover` rule walk to those few elements instead
        //               of falling back to a whole-subtree invalidation.
        case PseudoClass::Hover:
        case PseudoClass::Focus:
        case PseudoClass::FocusVisible:
        case PseudoClass::FocusWithin:
        case PseudoClass::Active:
        case PseudoClass::Target:
        // OPTIMIZATION: :host matches at most one element per shadow root and :root matches the html
        //               element only, so treating them as targetable lets a stylesheet add or remove
        //               with `:host` / `:root` rules invalidate just those elements instead of
        //               falling back to a whole-subtree invalidation.
        case PseudoClass::Host:
        case PseudoClass::Root:
            invalidation_set.set_needs_invalidate_pseudo_class(pseudo_class.type);
            break;
        // OPTIMIZATION: Structural-position pseudo-classes are usable as subject match filters
        //               because the matcher can test them against each element. This lets selectors
        //               like `.foo:has(.bar) > :first-child` invalidate only candidate boundary
        //               children instead of broadening the :has() invalidation plan to the whole
        //               subtree. Do not register them as trigger properties here since topology
        //               mutations are invalidated separately.
        case PseudoClass::FirstChild:
        case PseudoClass::LastChild:
        case PseudoClass::OnlyChild:
            if (purpose == InvalidationSetPurpose::SubjectMatchSet)
                invalidation_set.set_needs_invalidate_pseudo_class(pseudo_class.type);
            break;
        default:
            break;
        }
        if (pseudo_class.type == PseudoClass::Has)
            break;
        if (exclude_properties_nested_in_not_pseudo_class == ExcludePropertiesNestedInNotPseudoClass::Yes && pseudo_class.type == PseudoClass::Not)
            break;
        InsideNthChildPseudoClass inside_nth_child_pseudo_class_for_nested = inside_nth_child_selector;
        if (AK::first_is_one_of(pseudo_class.type, PseudoClass::NthChild, PseudoClass::NthLastChild, PseudoClass::NthOfType, PseudoClass::NthLastOfType))
            inside_nth_child_pseudo_class_for_nested = InsideNthChildPseudoClass::Yes;
        for (auto const& nested_selector : pseudo_class.argument_selector_list) {
            auto rightmost_invalidation_set_for_selector = build_invalidation_sets_for_selector_impl(style_invalidation_data, *nested_selector, inside_nth_child_pseudo_class_for_nested, root_invalidation_plan, purpose);
            invalidation_set.include_all_from(rightmost_invalidation_set_for_selector);

            // Propagate :has() from inner selectors where it appears in non-rightmost compounds.
            // The rightmost set only carries properties from the rightmost compound, so :has() in
            // non-rightmost positions (e.g., :is(:has(.x) .y)) is not propagated. We need it in the
            // outer invalidation set so outer compounds register plans for pseudo_class:Has that
            // account for the full selector context.
            // Additionally, when :has() is inside a complex :is()/:where() argument in a
            // non-rightmost compound, or in one that contains sibling combinators, the outer
            // invalidation plan can't correctly capture the nested combinator structure. Fall back
            // to whole-subtree invalidation for :has() in these cases. Descendant and child
            // combinators in the rightmost compound are represented by the nested selector's own
            // invalidation plan above.
            if (nested_selector->contains_pseudo_class(PseudoClass::Has)) {
                invalidation_set.set_needs_invalidate_pseudo_class(PseudoClass::Has);
                if (nested_selector->compound_selectors().size() > 1 && (simple_selector_group_position == SimpleSelectorGroupPosition::NonRightmost || selector_contains_sibling_combinator(*nested_selector))) {
                    InvalidationSet has_only;
                    has_only.set_needs_invalidate_pseudo_class(PseudoClass::Has);
                    add_invalidation_plan_for_properties(style_invalidation_data, has_only, *make_invalidate_whole_subtree_invalidation());
                }
            }
        }
        break;
    }
    case Selector::SimpleSelector::Type::PseudoElement: {
        // Pseudo-elements like ::slotted(.x) and ::part(...) carry a compound selector argument whose simple
        // selectors decide which property changes should trigger invalidation against this rule.
        auto const& pseudo_element = selector.pseudo_element();
        if (pseudo_element.type() == PseudoElement::Slotted) {
            for (auto const& compound_selector : pseudo_element.compound_selector().compound_selectors()) {
                for (auto const& nested_simple : compound_selector.simple_selectors)
                    build_invalidation_sets_for_simple_selector_impl(nested_simple, invalidation_set, exclude_properties_nested_in_not_pseudo_class, style_invalidation_data, inside_nth_child_selector, simple_selector_group_position, root_invalidation_plan, purpose);
            }
        }
        break;
    }
    default:
        break;
    }
}

void build_invalidation_sets_for_simple_selector(Selector::SimpleSelector const& selector, InvalidationSet& invalidation_set, ExcludePropertiesNestedInNotPseudoClass exclude_properties_nested_in_not_pseudo_class, StyleInvalidationData& style_invalidation_data, InsideNthChildPseudoClass inside_nth_child_selector)
{
    build_invalidation_sets_for_simple_selector_impl(selector, invalidation_set, exclude_properties_nested_in_not_pseudo_class, style_invalidation_data, inside_nth_child_selector, SimpleSelectorGroupPosition::Rightmost, *make_invalidate_self_invalidation(), InvalidationSetPurpose::TriggerProperties);
}

static void add_invalidation_sets_to_cover_scope_leakage_of_relative_selector_in_has_pseudo_class(Selector const& selector, StyleInvalidationData& style_invalidation_data)
{
    // Normally, :has() invalidation scope is limited to ancestors and ancestor siblings, however it could require
    // descendants invalidation when :is() with complex selector is used inside :has() relative selector.
    // For example ".a:has(:is(.b .c))" requires invalidation whenever "b" class is added or removed.
    // To cover this case, we add descendant invalidation set that requires whole subtree invalidation for each
    // property used in non-subject part of complex selector.

    auto invalidate_whole_subtree_for_invalidation_properties_in_non_subject_part_of_complex_selector = [&](Selector const& selector_to_invalidate) {
        for_each_consecutive_simple_selector_group(selector_to_invalidate, [&](Vector<Selector::SimpleSelector const&> const& simple_selectors, Selector::Combinator, bool rightmost) {
            if (rightmost)
                return;

            auto invalidation_set = build_invalidation_set_for_simple_selectors(simple_selectors, ExcludePropertiesNestedInNotPseudoClass::No, style_invalidation_data, InsideNthChildPseudoClass::No, SimpleSelectorGroupPosition::Rightmost, *make_invalidate_self_invalidation(), InvalidationSetPurpose::TriggerProperties);
            add_invalidation_plan_for_properties(style_invalidation_data, invalidation_set, *make_invalidate_whole_subtree_invalidation());
        });
    };

    for_each_consecutive_simple_selector_group(selector, [&](Vector<Selector::SimpleSelector const&> const& simple_selectors, Selector::Combinator, bool) {
        for (auto const& simple_selector : simple_selectors) {
            if (simple_selector.type != Selector::SimpleSelector::Type::PseudoClass)
                continue;
            auto const& pseudo_class = simple_selector.pseudo_class();
            if (pseudo_class.type == PseudoClass::Is || pseudo_class.type == PseudoClass::Where || pseudo_class.type == PseudoClass::Not) {
                for (auto const& nested_selector : pseudo_class.argument_selector_list)
                    invalidate_whole_subtree_for_invalidation_properties_in_non_subject_part_of_complex_selector(*nested_selector);
            }
        }
    });
}

static InvalidationSet build_invalidation_sets_for_selector_impl(StyleInvalidationData& style_invalidation_data, Selector const& selector, InsideNthChildPseudoClass inside_nth_child_pseudo_class, InvalidationPlan const& root_invalidation_plan, InvalidationSetPurpose purpose)
{
    auto const& compound_selectors = selector.compound_selectors();
    int compound_selector_index = compound_selectors.size() - 1;
    VERIFY(compound_selector_index >= 0);

    InvalidationSet invalidation_set_for_rightmost_selector;
    Selector::Combinator previous_compound_combinator = Selector::Combinator::None;
    Optional<SelectorRighthand> selector_righthand;
    for_each_consecutive_simple_selector_group(selector, [&](Vector<Selector::SimpleSelector const&> const& simple_selectors, Selector::Combinator combinator, bool is_rightmost) {
        // Collect properties used in :has() so we can decide if only specific properties
        // trigger descendant invalidation or if the entire document must be invalidated.
        for (auto const& simple_selector : simple_selectors) {
            collect_properties_used_in_has(simple_selector, style_invalidation_data, {});
        }

        auto simple_selector_group_position = is_rightmost ? SimpleSelectorGroupPosition::Rightmost : SimpleSelectorGroupPosition::NonRightmost;
        auto invalidation_properties = build_invalidation_set_for_simple_selectors(simple_selectors, ExcludePropertiesNestedInNotPseudoClass::No, style_invalidation_data, inside_nth_child_pseudo_class, simple_selector_group_position, root_invalidation_plan, InvalidationSetPurpose::TriggerProperties);
        auto subject_match_set = build_invalidation_set_for_simple_selectors(simple_selectors, ExcludePropertiesNestedInNotPseudoClass::Yes, style_invalidation_data, inside_nth_child_pseudo_class, simple_selector_group_position, root_invalidation_plan, purpose);
        auto subject_guard = build_invalidation_guard_for_simple_selectors(simple_selectors);
        bool subject_matches_any = subject_match_set.is_empty() && simple_selector_group_matches_any(simple_selectors);

        if (is_rightmost) {
            // The rightmost selector is handled twice:
            //  1) Include properties nested in :not()
            //  2) Exclude properties nested in :not()
            //
            // This ensures we handle cases like:
            //   :not(.foo) => produce invalidation set .foo { $ } ($ = invalidate self)
            //   .bar :not(.foo) => produce invalidation sets .foo { $ } and .bar { * } (* = invalidate subtree)
            //                      which means invalidation_set_for_rightmost_selector should be empty
            auto root_plan = copy_invalidation_plan(root_invalidation_plan);
            if (inside_nth_child_pseudo_class == InsideNthChildPseudoClass::Yes) {
                // When an invalidation property is nested in an nth-child selector like
                // p:nth-child(even of #t1, #t2, #t3), a property change can alter the filtered
                // sibling index of this element and its siblings. This does not require dirtying
                // the element's descendants unless they depend on that structural match.
                if (!root_plan->invalidate_whole_subtree)
                    root_plan->invalidate_self_and_structurally_affected_siblings = true;
            }
            auto interned_root_plan = style_invalidation_data.intern_invalidation_plan(move(root_plan));
            add_invalidation_plan_for_properties(style_invalidation_data, invalidation_properties, *interned_root_plan);

            invalidation_set_for_rightmost_selector = subject_match_set;
            selector_righthand = SelectorRighthand {
                .subject_match_set = move(subject_match_set),
                .subject_matches_any = subject_matches_any,
                .payload = move(interned_root_plan),
            };
        } else {
            VERIFY(previous_compound_combinator != Selector::Combinator::None);
            VERIFY(selector_righthand.has_value());

            auto plan = build_invalidation_for_combinator(previous_compound_combinator, *selector_righthand, style_invalidation_data);
            add_invalidation_plan_for_properties(style_invalidation_data, invalidation_properties, *plan, subject_guard);

            selector_righthand = SelectorRighthand {
                .subject_match_set = move(subject_match_set),
                .subject_matches_any = subject_matches_any,
                .payload = move(plan),
            };
        }

        previous_compound_combinator = combinator;
    });

    return invalidation_set_for_rightmost_selector;
}

void StyleInvalidationData::build_invalidation_sets_for_selector(Selector const& selector)
{
    (void)build_invalidation_sets_for_selector_impl(*this, selector, InsideNthChildPseudoClass::No, *make_invalidate_self_invalidation());
}

void StyleInvalidationData::build_invalidation_sets_for_scope_boundary_selector(Selector const& selector)
{
    (void)build_invalidation_sets_for_selector_impl(*this, selector, InsideNthChildPseudoClass::No, *make_invalidate_whole_subtree_invalidation());
}

}