<commit_before>/*
 * Copyright (C) 1999 <NAME> (<EMAIL>)
 *           (C) 2004-2005 <NAME> (<EMAIL>)
 * Copyright (C) 2006, 2007 <NAME> (<EMAIL>)
 * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Apple Inc. All rights reserved.
 * Copyright (C) 2007 <NAME> <<EMAIL>>
 * Copyright (C) 2007, 2008 <NAME> <<EMAIL>>
 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
 * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
 * Copyright (C) Research In Motion Limited 2011. All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 */

#include "config.h"
#include "core/css/SelectorChecker.h"

#include "HTMLNames.h"
#include "core/css/CSSSelectorList.h"
#include "core/css/SiblingTraversalStrategies.h"
#include "core/dom/Document.h"
#include "core/dom/ElementTraversal.h"
#include "core/dom/FullscreenElementStack.h"
#include "core/dom/NodeRenderStyle.h"
#include "core/dom/Text.h"
#include "core/dom/shadow/InsertionPoint.h"
#include "core/dom/shadow/ShadowRoot.h"
#include "core/editing/FrameSelection.h"
#include "core/frame/LocalFrame.h"
#include "core/html/HTMLDocument.h"
#include "core/html/HTMLFrameElementBase.h"
#include "core/html/HTMLInputElement.h"
#include "core/html/HTMLOptionElement.h"
#include "core/html/parser/HTMLParserIdioms.h"
#include "core/html/track/vtt/VTTElement.h"
#include "core/inspector/InspectorInstrumentation.h"
#include "core/page/FocusController.h"
#include "core/rendering/RenderObject.h"
#include "core/rendering/RenderScrollbar.h"
#include "core/rendering/style/RenderStyle.h"
#include "platform/scroll/ScrollableArea.h"
#include "platform/scroll/ScrollbarTheme.h"

namespace WebCore {

using namespace HTMLNames;

SelectorChecker::SelectorChecker(Document& document, Mode mode)
    : m_strictParsing(!document.inQuirksMode())
    , m_documentIsHTML(document.isHTMLDocument())
    , m_mode(mode)
{
}

static bool matchesCustomPseudoElement(const Element* element, const CSSSelector& selector)
{
    ShadowRoot* root = element->containingShadowRoot();
    if (!root || root->type() != ShadowRoot::UserAgentShadowRoot)
        return false;

    if (element->shadowPseudoId() != selector.value())
        return false;

    return true;
}

Element* SelectorChecker::parentElement(const SelectorCheckingContext& context, bool allowToCrossBoundary) const
{
    // CrossesBoundary means we don't care any context.scope. So we can walk up from a shadow root to its shadow host.
    if (allowToCrossBoundary)
        return context.element->parentOrShadowHostElement();

    // If context.scope is a shadow host, we should walk up from a shadow root to its shadow host.
    if ((context.behaviorAtBoundary & SelectorChecker::ScopeIsShadowHost) && context.scope == context.element->shadowHost())
        return context.element->parentOrShadowHostElement();

    if ((context.behaviorAtBoundary & SelectorChecker::BoundaryBehaviorMask) != SelectorChecker::StaysWithinTreeScope)
        return context.element->parentElement();

    // If context.scope is some element in some shadow tree and querySelector initialized the context,
    // e.g. shadowRoot.querySelector(':host *'),
    // (a) context.element has the same treescope as context.scope, need to walk up to its shadow host.
    // (b) Otherwise, should not walk up from a shadow root to a shadow host.
    if (context.scope && context.scope->treeScope() == context.element->treeScope())
        return context.element->parentOrShadowHostElement();

    return context.element->parentElement();
}

bool SelectorChecker::scopeContainsLastMatchedElement(const SelectorCheckingContext& context) const
{
    if (!(context.behaviorAtBoundary & SelectorChecker::ScopeContainsLastMatchedElement))
        return true;

    ASSERT(context.scope);
    // If behaviorAtBoundary is not ScopeIsShadowHost, we can use "contains".
    if (!(context.behaviorAtBoundary & SelectorChecker::ScopeIsShadowHost))
        return context.scope->contains(context.element);

    // If a given element is scope, i.e. shadow host, matches.
    if (context.element == context.scope && (!context.previousElement || context.previousElement->isInDescendantTreeOf(context.element)))
        return true;

    ShadowRoot* root = context.element->containingShadowRoot();
    if (!root)
        return false;

    // If a host of the containing shadow root is scope, matches.
    return root->host() == context.scope;
}

static inline bool nextSelectorExceedsScope(const SelectorChecker::SelectorCheckingContext& context)
{
    if ((context.behaviorAtBoundary & SelectorChecker::BoundaryBehaviorMask) != SelectorChecker::StaysWithinTreeScope)
        return context.element == context.scope;

    if (context.scope && context.scope->isInShadowTree())
        return context.element == context.scope->containingShadowRoot()->host();
    return false;
}

// Recursive check of selectors and combinators
// It can return 4 different values:
// * SelectorMatches          - the selector matches the element e
// * SelectorFailsLocally     - the selector fails for the element e
// * SelectorFailsAllSiblings - the selector fails for e and any sibling of e
// * SelectorFailsCompletely  - the selector fails for e and any sibling or ancestor of e
template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::match(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, MatchResult* result) const
{
    // first selector has to match
    unsigned specificity = 0;
    if (!checkOne(context, siblingTraversalStrategy, &specificity))
        return SelectorFailsLocally;

    if (context.selector->m_match == CSSSelector::PseudoElement) {
        if (context.selector->isCustomPseudoElement()) {
            if (!matchesCustomPseudoElement(context.element, *context.selector))
                return SelectorFailsLocally;
        } else if (context.selector->isContentPseudoElement()) {
            if (!context.element->isInShadowTree() || !context.element->isInsertionPoint())
                return SelectorFailsLocally;
        } else if (context.selector->isShadowPseudoElement()) {
            if (!context.element->isInShadowTree() || !context.previousElement)
                return SelectorFailsCompletely;
        } else {
            if ((!context.elementStyle && m_mode == ResolvingStyle) || m_mode == QueryingRules)
                return SelectorFailsLocally;

            PseudoId pseudoId = CSSSelector::pseudoId(context.selector->pseudoType());
            if (pseudoId == FIRST_LETTER)
                context.element->document().styleEngine()->setUsesFirstLetterRules(true);
            if (pseudoId != NOPSEUDO && m_mode != SharingRules && result)
                result->dynamicPseudo = pseudoId;
        }
    }

    // Prepare next selector
    const CSSSelector* historySelector = context.selector->tagHistory();
    if (!historySelector) {
        if (scopeContainsLastMatchedElement(context)) {
            if (result)
                result->specificity += specificity;
            return SelectorMatches;
        }
        return SelectorFailsLocally;
    }

    Match match;
    if (context.selector->relation() != CSSSelector::SubSelector) {
        // Abort if the next selector would exceed the scope.
        if (nextSelectorExceedsScope(context))
            return SelectorFailsCompletely;

        // Bail-out if this selector is irrelevant for the pseudoId
        if (context.pseudoId != NOPSEUDO && (!result || context.pseudoId != result->dynamicPseudo))
            return SelectorFailsCompletely;

        if (result) {
            TemporaryChange<PseudoId> dynamicPseudoScope(result->dynamicPseudo, NOPSEUDO);
            match = matchForRelation(context, siblingTraversalStrategy, result);
        } else {
            return matchForRelation(context, siblingTraversalStrategy, 0);
        }
    } else {
        match = matchForSubSelector(context, siblingTraversalStrategy, result);
    }
    if (match != SelectorMatches || !result)
        return match;

    result->specificity += specificity;
    return SelectorMatches;
}

static inline SelectorChecker::SelectorCheckingContext prepareNextContextForRelation(const SelectorChecker::SelectorCheckingContext& context)
{
    SelectorChecker::SelectorCheckingContext nextContext(context);
    ASSERT(context.selector->tagHistory());
    nextContext.selector = context.selector->tagHistory();
    return nextContext;
}

static inline bool isAuthorShadowRoot(const Node* node)
{
    return node && node->isShadowRoot() && toShadowRoot(node)->type() == ShadowRoot::AuthorShadowRoot;
}

template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::matchForSubSelector(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, MatchResult* result) const
{
    SelectorCheckingContext nextContext = prepareNextContextForRelation(context);

    PseudoId dynamicPseudo = result ? result->dynamicPseudo : NOPSEUDO;
    // a selector is invalid if something follows a pseudo-element
    // We make an exception for scrollbar pseudo elements and allow a set of pseudo classes (but nothing else)
    // to follow the pseudo elements.
    nextContext.hasScrollbarPseudo = dynamicPseudo != NOPSEUDO && (context.scrollbar || dynamicPseudo == SCROLLBAR_CORNER || dynamicPseudo == RESIZER);
    nextContext.hasSelectionPseudo = dynamicPseudo == SELECTION;
    if ((context.elementStyle || m_mode == CollectingCSSRules || m_mode == CollectingStyleRules || m_mode == QueryingRules) && dynamicPseudo != NOPSEUDO
        && !nextContext.hasSelectionPseudo
        && !(nextContext.hasScrollbarPseudo && nextContext.selector->m_match == CSSSelector::PseudoClass))
        return SelectorFailsCompletely;

    nextContext.isSubSelector = true;
    return match(nextContext, siblingTraversalStrategy, result);
}

static bool selectorMatchesShadowRoot(const CSSSelector* selector)
{
    return selector && selector->isShadowPseudoElement();
}

template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::matchForPseudoShadow(const ContainerNode* node, const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, MatchResult* result) const
{
    if (!isAuthorShadowRoot(node))
        return SelectorFailsCompletely;
    return match(context, siblingTraversalStrategy, result);
}

template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::matchForRelation(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, MatchResult* result) const
{
    SelectorCheckingContext nextContext = prepareNextContextForRelation(context);
    nextContext.previousElement = context.element;

    CSSSelector::Relation relation = context.selector->relation();

    // Disable :visited matching when we see the first link or try to match anything else than an ancestors.
    if (!context.isSubSelector && (context.element->isLink() || (relation != CSSSelector::Descendant && relation != CSSSelector::Child)))
        nextContext.visitedMatchType = VisitedMatchDisabled;

    nextContext.pseudoId = NOPSEUDO;

    switch (relation) {
    case CSSSelector::Descendant:
        if (context.selector->relationIsAffectedByPseudoContent()) {
            for (Element* element = context.element; element; element = element->parentElement()) {
                if (matchForShadowDistributed(element, siblingTraversalStrategy, nextContext, result) == SelectorMatches)
                    return SelectorMatches;
            }
            return SelectorFailsCompletely;
        }
        nextContext.isSubSelector = false;
        nextContext.elementStyle = 0;

        if (selectorMatchesShadowRoot(nextContext.selector))
            return matchForPseudoShadow(context.element->containingShadowRoot(), nextContext, siblingTraversalStrategy, result);

        for (nextContext.element = parentElement(context); nextContext.element; nextContext.element = parentElement(nextContext)) {
            Match match = this->match(nextContext, siblingTraversalStrategy, result);
            if (match == SelectorMatches || match == SelectorFailsCompletely)
                return match;
            if (nextSelectorExceedsScope(nextContext))
                return SelectorFailsCompletely;
        }
        return SelectorFailsCompletely;
    case CSSSelector::Child:
        {
            if (context.selector->relationIsAffectedByPseudoContent())
                return matchForShadowDistributed(context.element, siblingTraversalStrategy, nextContext, result);

            nextContext.isSubSelector = false;
            nextContext.elementStyle = 0;

            if (selectorMatchesShadowRoot(nextContext.selector))
                return matchForPseudoShadow(context.element->parentNode(), nextContext, siblingTraversalStrategy, result);

            nextContext.element = parentElement(context);
            if (!nextContext.element)
                return SelectorFailsCompletely;
            return match(nextContext, siblingTraversalStrategy, result);
        }
    case CSSSelector::DirectAdjacent:
        // Shadow roots can't have sibling elements
        if (selectorMatchesShadowRoot(nextContext.selector))
            return SelectorFailsCompletely;

        if (m_mode == ResolvingStyle) {
            if (ContainerNode* parent = context.element->parentElementOrShadowRoot())
                parent->setChildrenAffectedByDirectAdjacentRules();
        }
        nextContext.element = ElementTraversal::previousSibling(*context.element);
        if (!nextContext.element)
            return SelectorFailsAllSiblings;
        nextContext.isSubSelector = false;
        nextContext.elementStyle = 0;
        return match(nextContext, siblingTraversalStrategy, result);

    case CSSSelector::IndirectAdjacent:
        // Shadow roots can't have sibling elements
        if (selectorMatchesShadowRoot(nextContext.selector))
            return SelectorFailsCompletely;

        if (m_mode == ResolvingStyle) {
            if (ContainerNode* parent = context.element->parentElementOrShadowRoot())
                parent->setChildrenAffectedByIndirectAdjacentRules();
        }
        nextContext.element = ElementTraversal::previousSibling(*context.element);
        nextContext.isSubSelector = false;
        nextContext.elementStyle = 0;
        for (; nextContext.element; nextContext.element = ElementTraversal::previousSibling(*nextContext.element)) {
            Match match = this->match(nextContext, siblingTraversalStrategy, result);
            if (match == SelectorMatches || match == SelectorFailsAllSiblings || match == SelectorFailsCompletely)
                return match;
        };
        return SelectorFailsAllSiblings;

    case CSSSelector::ShadowPseudo:
        {
            // If we're in the same tree-scope as the scoping element, then following a shadow descendant combinator would escape that and thus the scope.
            if (context.scope && context.scope->treeScope() == context.element->treeScope() && (context.behaviorAtBoundary & BoundaryBehaviorMask) != StaysWithinTreeScope)
                return SelectorFailsCompletely;

            Element* shadowHost = context.element->shadowHost();
            if (!shadowHost)
                return SelectorFailsCompletely;
            nextContext.element = shadowHost;
            nextContext.isSubSelector = false;
            nextContext.elementStyle = 0;
            return this->match(nextContext, siblingTraversalStrategy, result);
        }

    case CSSSelector::ShadowDeep:
        {
            nextContext.isSubSelector = false;
            nextContext.elementStyle = 0;
            for (nextContext.element = parentElement(context, true); nextContext.element; nextContext.element = parentElement(nextContext, true)) {
                Match match = this->match(nextContext, siblingTraversalStrategy, result);
                if (match == SelectorMatches || match == SelectorFailsCompletely)
                    return match;
                if (nextSelectorExceedsScope(nextContext))
                    return SelectorFailsCompletely;
            }
            return SelectorFailsCompletely;
        }

    case CSSSelector::SubSelector:
        ASSERT_NOT_REACHED();
    }

    ASSERT_NOT_REACHED();
    return SelectorFailsCompletely;
}

template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::matchForShadowDistributed(const Element* element, const SiblingTraversalStrategy& siblingTraversalStrategy, SelectorCheckingContext& nextContext, MatchResult* result) const
{
    ASSERT(element);
    WillBeHeapVector<RawPtrWillBeMember<InsertionPoint>, 8> insertionPoints;

    const ContainerNode* scope = nextContext.scope;
    BehaviorAtBoundary behaviorAtBoundary = nextContext.behaviorAtBoundary;

    collectDestinationInsertionPoints(*element, insertionPoints);
    for (size_t i = 0; i < insertionPoints.size(); ++i) {
        nextContext.element = insertionPoints[i];

        // If a given scope is a shadow host of an insertion point but behaviorAtBoundary doesn't have ScopeIsShadowHost,
        // we need to update behaviorAtBoundary to make selectors like ":host > ::content" work correctly.
        if (m_mode == SharingRules) {
            nextContext.behaviorAtBoundary = static_cast<BehaviorAtBoundary>(behaviorAtBoundary | ScopeIsShadowHost);
            nextContext.scope = insertionPoints[i]->containingShadowRoot()->shadowHost();
        } else if (scope == insertionPoints[i]->containingShadowRoot()->shadowHost() && !(behaviorAtBoundary & ScopeIsShadowHost))
            nextContext.behaviorAtBoundary = static_cast<BehaviorAtBoundary>(behaviorAtBoundary | ScopeIsShadowHost);
        else
            nextContext.behaviorAtBoundary = behaviorAtBoundary;

        nextContext.isSubSelector = false;
        nextContext.elementStyle = 0;
        if (match(nextContext, siblingTraversalStrategy, result) == SelectorMatches)
            return SelectorMatches;
    }
    return SelectorFailsLocally;
}

template<typename CharType>
static inline bool containsHTMLSpaceTemplate(const CharType* string, unsigned length)
{
    for (unsigned i = 0; i < length; ++i)
        if (isHTMLSpace<CharType>(string[i]))
            return true;
    return false;
}

static inline bool containsHTMLSpace(const AtomicString& string)
{
    if (LIKELY(string.is8Bit()))
        return containsHTMLSpaceTemplate<LChar>(string.characters8(), string.length());
    return containsHTMLSpaceTemplate<UChar>(string.characters16(), string.length());
}

static bool attributeValueMatches(const Attribute& attributeItem, CSSSelector::Match match, const AtomicString& selectorValue, bool caseSensitive)
{
    const AtomicString& value = attributeItem.value();
    if (value.isNull())
        return false;

    switch (match) {
    case CSSSelector::Exact:
        if (caseSensitive ? selectorValue != value : !equalIgnoringCase(selectorValue, value))
            return false;
        break;
    case CSSSelector::List:
        {
            // Ignore empty selectors or selectors containing HTML spaces
            if (selectorValue.isEmpty() || containsHTMLSpace(selectorValue))
                return false;

            unsigned startSearchAt = 0;
            while (true) {
                size_t foundPos = value.find(selectorValue, startSearchAt, caseSensitive);
                if (foundPos == kNotFound)
                    return false;
                if (!foundPos || isHTMLSpace<UChar>(value[foundPos - 1])) {
                    unsigned endStr = foundPos + selectorValue.length();
                    if (endStr == value.length() || isHTMLSpace<UChar>(value[endStr]))
                        break; // We found a match.
                }

                // No match. Keep looking.
                startSearchAt = foundPos + 1;
            }
            break;
        }
    case CSSSelector::Contain:
        if (!value.contains(selectorValue, caseSensitive) || selectorValue.isEmpty())
            return false;
        break;
    case CSSSelector::Begin:
        if (!value.startsWith(selectorValue, caseSensitive) || selectorValue.isEmpty())
            return false;
        break;
    case CSSSelector::End:
        if (!value.endsWith(selectorValue, caseSensitive) || selectorValue.isEmpty())
            return false;
        break;
    case CSSSelector::Hyphen:
        if (value.length() < selectorValue.length())
            return false;
        if (!value.startsWith(selectorValue, caseSensitive))
            return false;
        // It they start the same, check for exact match or following '-':
        if (value.length() != selectorValue.length() && value[selectorValue.length()] != '-')
            return false;
        break;
    case CSSSelector::PseudoClass:
    case CSSSelector::PseudoElement:
    default:
        break;
    }

    return true;
}

static bool anyAttributeMatches(Element& element, CSSSelector::Match match, const CSSSelector& selector)
{
    const QualifiedName& selectorAttr = selector.attribute();
    ASSERT(selectorAttr.localName() != starAtom); // Should not be possible from the CSS grammar.

    // Synchronize the attribute in case it is lazy-computed.
    // Currently all lazy properties have a null namespace, so only pass localName().
    element.synchronizeAttribute(selectorAttr.localName());

    if (!element.hasAttributesWithoutUpdate())
        return false;

    const AtomicString& selectorValue =  selector.value();

    unsigned attributeCount = element.attributeCount();
    for (size_t i = 0; i < attributeCount; ++i) {
        const Attribute& attributeItem = element.attributeItem(i);

        if (!attributeItem.matches(selectorAttr))
            continue;

        if (attributeValueMatches(attributeItem, match, selectorValue, true))
            return true;

        // Case sensitivity for attribute matching is looser than hasAttribute or
        // Element::shouldIgnoreAttributeCase() for now. Unclear if that's correct.
        bool caseSensitive = !element.document().isHTMLDocument() || HTMLDocument::isCaseSensitiveAttribute(selectorAttr);

        // If case-insensitive, re-check, and count if result differs.
        // See http://code.google.com/p/chromium/issues/detail?id=327060
        if (!caseSensitive && attributeValueMatches(attributeItem, match, selectorValue, false)) {
            UseCounter::count(element.document(), UseCounter::CaseInsensitiveAttrSelectorMatch);
            return true;
        }
    }

    return false;
}

template<typename SiblingTraversalStrategy>
bool SelectorChecker::checkOne(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, unsigned* specificity) const
{
    ASSERT(context.element);
    Element& element = *context.element;
    ASSERT(context.selector);
    const CSSSelector& selector = *context.selector;

    bool elementIsHostInItsShadowTree = isHostInItsShadowTree(element, context.behaviorAtBoundary, context.scope);

    // Only :host and :ancestor should match the host: http://drafts.csswg.org/css-scoping/#host-element
    if (elementIsHostInItsShadowTree && !selector.isHostPseudoClass())
        return false;

    if (selector.m_match == CSSSelector::Tag)
        return SelectorChecker::tagMatches(element, selector.tagQName());

    if (selector.m_match == CSSSelector::Class)
        return element.hasClass() && element.classNames().contains(selector.value());

    if (selector.m_match == CSSSelector::Id)
        return element.hasID() && element.idForStyleResolution() == selector.value();

    if (selector.isAttributeSelector()) {
        if (!anyAttributeMatches(element, static_cast<CSSSelector::Match>(selector.m_match), selector))
            return false;
    }

    if (selector.m_match == CSSSelector::PseudoClass) {
        // Handle :not up front.
        if (selector.pseudoType() == CSSSelector::PseudoNot) {
            SelectorCheckingContext subContext(context);
            subContext.isSubSelector = true;
            ASSERT(selector.selectorList());
            for (subContext.selector = selector.selectorList()->first(); subContext.selector; subContext.selector = subContext.selector->tagHistory()) {
                // :not cannot nest. I don't really know why this is a
                // restriction in CSS3, but it is, so let's honor it.
                // the parser enforces that this never occurs
                ASSERT(subContext.selector->pseudoType() != CSSSelector::PseudoNot);
                // We select between :visited and :link when applying. We don't know which one applied (or not) yet.
                if (subContext.selector->pseudoType() == CSSSelector::PseudoVisited || (subContext.selector->pseudoType() == CSSSelector::PseudoLink && subContext.visitedMatchType == VisitedMatchEnabled))
                    return true;
                // context.scope is not available if m_mode == SharingRules.
                // We cannot determine whether :host or :scope matches a given element or not.
                if (m_mode == SharingRules && (subContext.selector->isHostPseudoClass() || subContext.selector->pseudoType() == CSSSelector::PseudoScope))
                    return true;
                if (!checkOne(subContext, DOMSiblingTraversalStrategy()))
                    return true;
            }
        } else if (context.hasScrollbarPseudo) {
            // CSS scrollbars match a specific subset of pseudo classes, and they have specialized rules for each
            // (since there are no elements involved).
            return checkScrollbarPseudoClass(context, &element.document(), selector);
        } else if (context.hasSelectionPseudo) {
            if (selector.pseudoType() == CSSSelector::PseudoWindowInactive)
                return !element.document().page()->focusController().isActive();
        }<commit_msg>Return early in SelectorChecker::checkOne() if selector.isAttributeSelector() is true<commit_after>/*
 * Copyright (C) 1999 <NAME> (<EMAIL>)
 *           (C) 2004-2005 <NAME> (<EMAIL>)
 * Copyright (C) 2006, 2007 <NAME> (<EMAIL>)
 * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Apple Inc. All rights reserved.
 * Copyright (C) 2007 <NAME> <<EMAIL>>
 * Copyright (C) 2007, 2008 <NAME> <<EMAIL>>
 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
 * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
 * Copyright (C) Research In Motion Limited 2011. All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 */

#include "config.h"
#include "core/css/SelectorChecker.h"

#include "HTMLNames.h"
#include "core/css/CSSSelectorList.h"
#include "core/css/SiblingTraversalStrategies.h"
#include "core/dom/Document.h"
#include "core/dom/ElementTraversal.h"
#include "core/dom/FullscreenElementStack.h"
#include "core/dom/NodeRenderStyle.h"
#include "core/dom/Text.h"
#include "core/dom/shadow/InsertionPoint.h"
#include "core/dom/shadow/ShadowRoot.h"
#include "core/editing/FrameSelection.h"
#include "core/frame/LocalFrame.h"
#include "core/html/HTMLDocument.h"
#include "core/html/HTMLFrameElementBase.h"
#include "core/html/HTMLInputElement.h"
#include "core/html/HTMLOptionElement.h"
#include "core/html/parser/HTMLParserIdioms.h"
#include "core/html/track/vtt/VTTElement.h"
#include "core/inspector/InspectorInstrumentation.h"
#include "core/page/FocusController.h"
#include "core/rendering/RenderObject.h"
#include "core/rendering/RenderScrollbar.h"
#include "core/rendering/style/RenderStyle.h"
#include "platform/scroll/ScrollableArea.h"
#include "platform/scroll/ScrollbarTheme.h"

namespace WebCore {

using namespace HTMLNames;

SelectorChecker::SelectorChecker(Document& document, Mode mode)
    : m_strictParsing(!document.inQuirksMode())
    , m_documentIsHTML(document.isHTMLDocument())
    , m_mode(mode)
{
}

static bool matchesCustomPseudoElement(const Element* element, const CSSSelector& selector)
{
    ShadowRoot* root = element->containingShadowRoot();
    if (!root || root->type() != ShadowRoot::UserAgentShadowRoot)
        return false;

    if (element->shadowPseudoId() != selector.value())
        return false;

    return true;
}

Element* SelectorChecker::parentElement(const SelectorCheckingContext& context, bool allowToCrossBoundary) const
{
    // CrossesBoundary means we don't care any context.scope. So we can walk up from a shadow root to its shadow host.
    if (allowToCrossBoundary)
        return context.element->parentOrShadowHostElement();

    // If context.scope is a shadow host, we should walk up from a shadow root to its shadow host.
    if ((context.behaviorAtBoundary & SelectorChecker::ScopeIsShadowHost) && context.scope == context.element->shadowHost())
        return context.element->parentOrShadowHostElement();

    if ((context.behaviorAtBoundary & SelectorChecker::BoundaryBehaviorMask) != SelectorChecker::StaysWithinTreeScope)
        return context.element->parentElement();

    // If context.scope is some element in some shadow tree and querySelector initialized the context,
    // e.g. shadowRoot.querySelector(':host *'),
    // (a) context.element has the same treescope as context.scope, need to walk up to its shadow host.
    // (b) Otherwise, should not walk up from a shadow root to a shadow host.
    if (context.scope && context.scope->treeScope() == context.element->treeScope())
        return context.element->parentOrShadowHostElement();

    return context.element->parentElement();
}

bool SelectorChecker::scopeContainsLastMatchedElement(const SelectorCheckingContext& context) const
{
    if (!(context.behaviorAtBoundary & SelectorChecker::ScopeContainsLastMatchedElement))
        return true;

    ASSERT(context.scope);
    // If behaviorAtBoundary is not ScopeIsShadowHost, we can use "contains".
    if (!(context.behaviorAtBoundary & SelectorChecker::ScopeIsShadowHost))
        return context.scope->contains(context.element);

    // If a given element is scope, i.e. shadow host, matches.
    if (context.element == context.scope && (!context.previousElement || context.previousElement->isInDescendantTreeOf(context.element)))
        return true;

    ShadowRoot* root = context.element->containingShadowRoot();
    if (!root)
        return false;

    // If a host of the containing shadow root is scope, matches.
    return root->host() == context.scope;
}

static inline bool nextSelectorExceedsScope(const SelectorChecker::SelectorCheckingContext& context)
{
    if ((context.behaviorAtBoundary & SelectorChecker::BoundaryBehaviorMask) != SelectorChecker::StaysWithinTreeScope)
        return context.element == context.scope;

    if (context.scope && context.scope->isInShadowTree())
        return context.element == context.scope->containingShadowRoot()->host();
    return false;
}

// Recursive check of selectors and combinators
// It can return 4 different values:
// * SelectorMatches          - the selector matches the element e
// * SelectorFailsLocally     - the selector fails for the element e
// * SelectorFailsAllSiblings - the selector fails for e and any sibling of e
// * SelectorFailsCompletely  - the selector fails for e and any sibling or ancestor of e
template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::match(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, MatchResult* result) const
{
    // first selector has to match
    unsigned specificity = 0;
    if (!checkOne(context, siblingTraversalStrategy, &specificity))
        return SelectorFailsLocally;

    if (context.selector->m_match == CSSSelector::PseudoElement) {
        if (context.selector->isCustomPseudoElement()) {
            if (!matchesCustomPseudoElement(context.element, *context.selector))
                return SelectorFailsLocally;
        } else if (context.selector->isContentPseudoElement()) {
            if (!context.element->isInShadowTree() || !context.element->isInsertionPoint())
                return SelectorFailsLocally;
        } else if (context.selector->isShadowPseudoElement()) {
            if (!context.element->isInShadowTree() || !context.previousElement)
                return SelectorFailsCompletely;
        } else {
            if ((!context.elementStyle && m_mode == ResolvingStyle) || m_mode == QueryingRules)
                return SelectorFailsLocally;

            PseudoId pseudoId = CSSSelector::pseudoId(context.selector->pseudoType());
            if (pseudoId == FIRST_LETTER)
                context.element->document().styleEngine()->setUsesFirstLetterRules(true);
            if (pseudoId != NOPSEUDO && m_mode != SharingRules && result)
                result->dynamicPseudo = pseudoId;
        }
    }

    // Prepare next selector
    const CSSSelector* historySelector = context.selector->tagHistory();
    if (!historySelector) {
        if (scopeContainsLastMatchedElement(context)) {
            if (result)
                result->specificity += specificity;
            return SelectorMatches;
        }
        return SelectorFailsLocally;
    }

    Match match;
    if (context.selector->relation() != CSSSelector::SubSelector) {
        // Abort if the next selector would exceed the scope.
        if (nextSelectorExceedsScope(context))
            return SelectorFailsCompletely;

        // Bail-out if this selector is irrelevant for the pseudoId
        if (context.pseudoId != NOPSEUDO && (!result || context.pseudoId != result->dynamicPseudo))
            return SelectorFailsCompletely;

        if (result) {
            TemporaryChange<PseudoId> dynamicPseudoScope(result->dynamicPseudo, NOPSEUDO);
            match = matchForRelation(context, siblingTraversalStrategy, result);
        } else {
            return matchForRelation(context, siblingTraversalStrategy, 0);
        }
    } else {
        match = matchForSubSelector(context, siblingTraversalStrategy, result);
    }
    if (match != SelectorMatches || !result)
        return match;

    result->specificity += specificity;
    return SelectorMatches;
}

static inline SelectorChecker::SelectorCheckingContext prepareNextContextForRelation(const SelectorChecker::SelectorCheckingContext& context)
{
    SelectorChecker::SelectorCheckingContext nextContext(context);
    ASSERT(context.selector->tagHistory());
    nextContext.selector = context.selector->tagHistory();
    return nextContext;
}

static inline bool isAuthorShadowRoot(const Node* node)
{
    return node && node->isShadowRoot() && toShadowRoot(node)->type() == ShadowRoot::AuthorShadowRoot;
}

template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::matchForSubSelector(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, MatchResult* result) const
{
    SelectorCheckingContext nextContext = prepareNextContextForRelation(context);

    PseudoId dynamicPseudo = result ? result->dynamicPseudo : NOPSEUDO;
    // a selector is invalid if something follows a pseudo-element
    // We make an exception for scrollbar pseudo elements and allow a set of pseudo classes (but nothing else)
    // to follow the pseudo elements.
    nextContext.hasScrollbarPseudo = dynamicPseudo != NOPSEUDO && (context.scrollbar || dynamicPseudo == SCROLLBAR_CORNER || dynamicPseudo == RESIZER);
    nextContext.hasSelectionPseudo = dynamicPseudo == SELECTION;
    if ((context.elementStyle || m_mode == CollectingCSSRules || m_mode == CollectingStyleRules || m_mode == QueryingRules) && dynamicPseudo != NOPSEUDO
        && !nextContext.hasSelectionPseudo
        && !(nextContext.hasScrollbarPseudo && nextContext.selector->m_match == CSSSelector::PseudoClass))
        return SelectorFailsCompletely;

    nextContext.isSubSelector = true;
    return match(nextContext, siblingTraversalStrategy, result);
}

static bool selectorMatchesShadowRoot(const CSSSelector* selector)
{
    return selector && selector->isShadowPseudoElement();
}

template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::matchForPseudoShadow(const ContainerNode* node, const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, MatchResult* result) const
{
    if (!isAuthorShadowRoot(node))
        return SelectorFailsCompletely;
    return match(context, siblingTraversalStrategy, result);
}

template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::matchForRelation(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, MatchResult* result) const
{
    SelectorCheckingContext nextContext = prepareNextContextForRelation(context);
    nextContext.previousElement = context.element;

    CSSSelector::Relation relation = context.selector->relation();

    // Disable :visited matching when we see the first link or try to match anything else than an ancestors.
    if (!context.isSubSelector && (context.element->isLink() || (relation != CSSSelector::Descendant && relation != CSSSelector::Child)))
        nextContext.visitedMatchType = VisitedMatchDisabled;

    nextContext.pseudoId = NOPSEUDO;

    switch (relation) {
    case CSSSelector::Descendant:
        if (context.selector->relationIsAffectedByPseudoContent()) {
            for (Element* element = context.element; element; element = element->parentElement()) {
                if (matchForShadowDistributed(element, siblingTraversalStrategy, nextContext, result) == SelectorMatches)
                    return SelectorMatches;
            }
            return SelectorFailsCompletely;
        }
        nextContext.isSubSelector = false;
        nextContext.elementStyle = 0;

        if (selectorMatchesShadowRoot(nextContext.selector))
            return matchForPseudoShadow(context.element->containingShadowRoot(), nextContext, siblingTraversalStrategy, result);

        for (nextContext.element = parentElement(context); nextContext.element; nextContext.element = parentElement(nextContext)) {
            Match match = this->match(nextContext, siblingTraversalStrategy, result);
            if (match == SelectorMatches || match == SelectorFailsCompletely)
                return match;
            if (nextSelectorExceedsScope(nextContext))
                return SelectorFailsCompletely;
        }
        return SelectorFailsCompletely;
    case CSSSelector::Child:
        {
            if (context.selector->relationIsAffectedByPseudoContent())
                return matchForShadowDistributed(context.element, siblingTraversalStrategy, nextContext, result);

            nextContext.isSubSelector = false;
            nextContext.elementStyle = 0;

            if (selectorMatchesShadowRoot(nextContext.selector))
                return matchForPseudoShadow(context.element->parentNode(), nextContext, siblingTraversalStrategy, result);

            nextContext.element = parentElement(context);
            if (!nextContext.element)
                return SelectorFailsCompletely;
            return match(nextContext, siblingTraversalStrategy, result);
        }
    case CSSSelector::DirectAdjacent:
        // Shadow roots can't have sibling elements
        if (selectorMatchesShadowRoot(nextContext.selector))
            return SelectorFailsCompletely;

        if (m_mode == ResolvingStyle) {
            if (ContainerNode* parent = context.element->parentElementOrShadowRoot())
                parent->setChildrenAffectedByDirectAdjacentRules();
        }
        nextContext.element = ElementTraversal::previousSibling(*context.element);
        if (!nextContext.element)
            return SelectorFailsAllSiblings;
        nextContext.isSubSelector = false;
        nextContext.elementStyle = 0;
        return match(nextContext, siblingTraversalStrategy, result);

    case CSSSelector::IndirectAdjacent:
        // Shadow roots can't have sibling elements
        if (selectorMatchesShadowRoot(nextContext.selector))
            return SelectorFailsCompletely;

        if (m_mode == ResolvingStyle) {
            if (ContainerNode* parent = context.element->parentElementOrShadowRoot())
                parent->setChildrenAffectedByIndirectAdjacentRules();
        }
        nextContext.element = ElementTraversal::previousSibling(*context.element);
        nextContext.isSubSelector = false;
        nextContext.elementStyle = 0;
        for (; nextContext.element; nextContext.element = ElementTraversal::previousSibling(*nextContext.element)) {
            Match match = this->match(nextContext, siblingTraversalStrategy, result);
            if (match == SelectorMatches || match == SelectorFailsAllSiblings || match == SelectorFailsCompletely)
                return match;
        };
        return SelectorFailsAllSiblings;

    case CSSSelector::ShadowPseudo:
        {
            // If we're in the same tree-scope as the scoping element, then following a shadow descendant combinator would escape that and thus the scope.
            if (context.scope && context.scope->treeScope() == context.element->treeScope() && (context.behaviorAtBoundary & BoundaryBehaviorMask) != StaysWithinTreeScope)
                return SelectorFailsCompletely;

            Element* shadowHost = context.element->shadowHost();
            if (!shadowHost)
                return SelectorFailsCompletely;
            nextContext.element = shadowHost;
            nextContext.isSubSelector = false;
            nextContext.elementStyle = 0;
            return this->match(nextContext, siblingTraversalStrategy, result);
        }

    case CSSSelector::ShadowDeep:
        {
            nextContext.isSubSelector = false;
            nextContext.elementStyle = 0;
            for (nextContext.element = parentElement(context, true); nextContext.element; nextContext.element = parentElement(nextContext, true)) {
                Match match = this->match(nextContext, siblingTraversalStrategy, result);
                if (match == SelectorMatches || match == SelectorFailsCompletely)
                    return match;
                if (nextSelectorExceedsScope(nextContext))
                    return SelectorFailsCompletely;
            }
            return SelectorFailsCompletely;
        }

    case CSSSelector::SubSelector:
        ASSERT_NOT_REACHED();
    }

    ASSERT_NOT_REACHED();
    return SelectorFailsCompletely;
}

template<typename SiblingTraversalStrategy>
SelectorChecker::Match SelectorChecker::matchForShadowDistributed(const Element* element, const SiblingTraversalStrategy& siblingTraversalStrategy, SelectorCheckingContext& nextContext, MatchResult* result) const
{
    ASSERT(element);
    WillBeHeapVector<RawPtrWillBeMember<InsertionPoint>, 8> insertionPoints;

    const ContainerNode* scope = nextContext.scope;
    BehaviorAtBoundary behaviorAtBoundary = nextContext.behaviorAtBoundary;

    collectDestinationInsertionPoints(*element, insertionPoints);
    for (size_t i = 0; i < insertionPoints.size(); ++i) {
        nextContext.element = insertionPoints[i];

        // If a given scope is a shadow host of an insertion point but behaviorAtBoundary doesn't have ScopeIsShadowHost,
        // we need to update behaviorAtBoundary to make selectors like ":host > ::content" work correctly.
        if (m_mode == SharingRules) {
            nextContext.behaviorAtBoundary = static_cast<BehaviorAtBoundary>(behaviorAtBoundary | ScopeIsShadowHost);
            nextContext.scope = insertionPoints[i]->containingShadowRoot()->shadowHost();
        } else if (scope == insertionPoints[i]->containingShadowRoot()->shadowHost() && !(behaviorAtBoundary & ScopeIsShadowHost))
            nextContext.behaviorAtBoundary = static_cast<BehaviorAtBoundary>(behaviorAtBoundary | ScopeIsShadowHost);
        else
            nextContext.behaviorAtBoundary = behaviorAtBoundary;

        nextContext.isSubSelector = false;
        nextContext.elementStyle = 0;
        if (match(nextContext, siblingTraversalStrategy, result) == SelectorMatches)
            return SelectorMatches;
    }
    return SelectorFailsLocally;
}

template<typename CharType>
static inline bool containsHTMLSpaceTemplate(const CharType* string, unsigned length)
{
    for (unsigned i = 0; i < length; ++i)
        if (isHTMLSpace<CharType>(string[i]))
            return true;
    return false;
}

static inline bool containsHTMLSpace(const AtomicString& string)
{
    if (LIKELY(string.is8Bit()))
        return containsHTMLSpaceTemplate<LChar>(string.characters8(), string.length());
    return containsHTMLSpaceTemplate<UChar>(string.characters16(), string.length());
}

static bool attributeValueMatches(const Attribute& attributeItem, CSSSelector::Match match, const AtomicString& selectorValue, bool caseSensitive)
{
    const AtomicString& value = attributeItem.value();
    if (value.isNull())
        return false;

    switch (match) {
    case CSSSelector::Exact:
        if (caseSensitive ? selectorValue != value : !equalIgnoringCase(selectorValue, value))
            return false;
        break;
    case CSSSelector::List:
        {
            // Ignore empty selectors or selectors containing HTML spaces
            if (selectorValue.isEmpty() || containsHTMLSpace(selectorValue))
                return false;

            unsigned startSearchAt = 0;
            while (true) {
                size_t foundPos = value.find(selectorValue, startSearchAt, caseSensitive);
                if (foundPos == kNotFound)
                    return false;
                if (!foundPos || isHTMLSpace<UChar>(value[foundPos - 1])) {
                    unsigned endStr = foundPos + selectorValue.length();
                    if (endStr == value.length() || isHTMLSpace<UChar>(value[endStr]))
                        break; // We found a match.
                }

                // No match. Keep looking.
                startSearchAt = foundPos + 1;
            }
            break;
        }
    case CSSSelector::Contain:
        if (!value.contains(selectorValue, caseSensitive) || selectorValue.isEmpty())
            return false;
        break;
    case CSSSelector::Begin:
        if (!value.startsWith(selectorValue, caseSensitive) || selectorValue.isEmpty())
            return false;
        break;
    case CSSSelector::End:
        if (!value.endsWith(selectorValue, caseSensitive) || selectorValue.isEmpty())
            return false;
        break;
    case CSSSelector::Hyphen:
        if (value.length() < selectorValue.length())
            return false;
        if (!value.startsWith(selectorValue, caseSensitive))
            return false;
        // It they start the same, check for exact match or following '-':
        if (value.length() != selectorValue.length() && value[selectorValue.length()] != '-')
            return false;
        break;
    case CSSSelector::PseudoClass:
    case CSSSelector::PseudoElement:
    default:
        break;
    }

    return true;
}

static bool anyAttributeMatches(Element& element, CSSSelector::Match match, const CSSSelector& selector)
{
    const QualifiedName& selectorAttr = selector.attribute();
    ASSERT(selectorAttr.localName() != starAtom); // Should not be possible from the CSS grammar.

    // Synchronize the attribute in case it is lazy-computed.
    // Currently all lazy properties have a null namespace, so only pass localName().
    element.synchronizeAttribute(selectorAttr.localName());

    if (!element.hasAttributesWithoutUpdate())
        return false;

    const AtomicString& selectorValue =  selector.value();

    unsigned attributeCount = element.attributeCount();
    for (size_t i = 0; i < attributeCount; ++i) {
        const Attribute& attributeItem = element.attributeItem(i);

        if (!attributeItem.matches(selectorAttr))
            continue;

        if (attributeValueMatches(attributeItem, match, selectorValue, true))
            return true;

        // Case sensitivity for attribute matching is looser than hasAttribute or
        // Element::shouldIgnoreAttributeCase() for now. Unclear if that's correct.
        bool caseSensitive = !element.document().isHTMLDocument() || HTMLDocument::isCaseSensitiveAttribute(selectorAttr);

        // If case-insensitive, re-check, and count if result differs.
        // See http://code.google.com/p/chromium/issues/detail?id=327060
        if (!caseSensitive && attributeValueMatches(attributeItem, match, selectorValue, false)) {
            UseCounter::count(element.document(), UseCounter::CaseInsensitiveAttrSelectorMatch);
            return true;
        }
    }

    return false;
}

template<typename SiblingTraversalStrategy>
bool SelectorChecker::checkOne(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy, unsigned* specificity) const
{
    ASSERT(context.element);
    Element& element = *context.element;
    ASSERT(context.selector);
    const CSSSelector& selector = *context.selector;

    bool elementIsHostInItsShadowTree = isHostInItsShadowTree(element, context.behaviorAtBoundary, context.scope);

    // Only :host and :ancestor should match the host: http://drafts.csswg.org/css-scoping/#host-element
    if (elementIsHostInItsShadowTree && !selector.isHostPseudoClass())
        return false;

    if (selector.m_match == CSSSelector::Tag)
        return SelectorChecker::tagMatches(element, selector.tagQName());

    if (selector.m_match == CSSSelector::Class)
        return element.hasClass() && element.classNames().contains(selector.value());

    if (selector.m_match == CSSSelector::Id)
        return element.hasID() && element.idForStyleResolution() == selector.value();

    if (selector.isAttributeSelector())
        return anyAttributeMatches(element, static_cast<CSSSelector::Match>(selector.m_match), selector);

    if (selector.m_match == CSSSelector::PseudoClass) {
        // Handle :not up front.
        if (selector.pseudoType() == CSSSelector::PseudoNot) {
            SelectorCheckingContext subContext(context);
            subContext.isSubSelector = true;
            ASSERT(selector.selectorList());
            for (subContext.selector = selector.selectorList()->first(); subContext.selector; subContext.selector = subContext.selector->tagHistory()) {
                // :not cannot nest. I don't really know why this is a
                // restriction in CSS3, but it is, so let's honor it.
                // the parser enforces that this never occurs
                ASSERT(subContext.selector->pseudoType() != CSSSelector::PseudoNot);
                // We select between :visited and :link when applying. We don't know which one applied (or not) yet.
                if (subContext.selector->pseudoType() == CSSSelector::PseudoVisited || (subContext.selector->pseudoType() == CSSSelector::PseudoLink && subContext.visitedMatchType == VisitedMatchEnabled))
                    return true;
                // context.scope is not available if m_mode == SharingRules.
                // We cannot determine whether :host or :scope matches a given element or not.
                if (m_mode == SharingRules && (subContext.selector->isHostPseudoClass() || subContext.selector->pseudoType() == CSSSelector::PseudoScope))
                    return true;
                if (!checkOne(subContext, DOMSiblingTraversalStrategy()))
                    return true;
            }
        } else if (context.hasScrollbarPseudo) {
            // CSS scrollbars match a specific subset of pseudo classes, and they have specialized rules for each
            // (since there are no elements involved).
            return checkScrollbarPseudoClass(context, &element.document(), selector);
        } else if (context.hasSelectionPseudo) {
            if (selector.pseudoType() == CSSSelector::PseudoWindowInactive)
                return !element.document().page()->focusController().isActive();
        }
{'fraction_non_alphanumeric': 0.09722948248823837, 'fraction_numerical': 0.0046299753565827795, 'mean_word_length': 3.37015582932202, 'pattern_counts': {'":': 2, '<': 71, '<?xml version=': 0, '>': 209, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5812687', 'n_tokens_mistral': 14383, 'n_tokens_neox': 13742, 'n_words': 3531}