1/*
2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3 *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
4 * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
5 * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Apple Inc. All rights reserved.
6 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
7 * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
8 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
9 * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
10 * Copyright (C) Research In Motion Limited 2011. All rights reserved.
11 *
12 * This library is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Library General Public
14 * License as published by the Free Software Foundation; either
15 * version 2 of the License, or (at your option) any later version.
16 *
17 * This library is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
20 * Library General Public License for more details.
21 *
22 * You should have received a copy of the GNU Library General Public License
23 * along with this library; see the file COPYING.LIB.  If not, write to
24 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
25 * Boston, MA 02110-1301, USA.
26 */
27
28#include "config.h"
29#include "core/css/SelectorChecker.h"
30
31#include "HTMLNames.h"
32#include "core/css/CSSSelector.h"
33#include "core/css/CSSSelectorList.h"
34#include "core/css/SiblingTraversalStrategies.h"
35#include "core/dom/Document.h"
36#include "core/dom/Element.h"
37#include "core/dom/FullscreenElementStack.h"
38#include "core/dom/NodeRenderStyle.h"
39#include "core/dom/Text.h"
40#include "core/dom/shadow/InsertionPoint.h"
41#include "core/dom/shadow/ShadowRoot.h"
42#include "core/editing/FrameSelection.h"
43#include "core/html/HTMLAnchorElement.h"
44#include "core/html/HTMLDocument.h"
45#include "core/html/HTMLFrameElementBase.h"
46#include "core/html/HTMLInputElement.h"
47#include "core/html/HTMLOptGroupElement.h"
48#include "core/html/HTMLOptionElement.h"
49#include "core/html/parser/HTMLParserIdioms.h"
50#include "core/inspector/InspectorInstrumentation.h"
51#include "core/page/FocusController.h"
52#include "core/page/Frame.h"
53#include "core/page/Page.h"
54#include "core/platform/ScrollableArea.h"
55#include "core/platform/ScrollbarTheme.h"
56#include "core/rendering/RenderObject.h"
57#include "core/rendering/RenderScrollbar.h"
58#include "core/rendering/style/RenderStyle.h"
59
60#include "core/html/track/WebVTTElement.h"
61
62namespace WebCore {
63
64using namespace HTMLNames;
65
66SelectorChecker::SelectorChecker(Document* document, Mode mode)
67    : m_strictParsing(!document->inQuirksMode())
68    , m_documentIsHTML(document->isHTMLDocument())
69    , m_mode(mode)
70{
71}
72
73static bool matchesCustomPseudoElement(const Element* element, const CSSSelector* selector)
74{
75    ShadowRoot* root = element->containingShadowRoot();
76    if (!root)
77        return false;
78
79    if (selector->pseudoType() != CSSSelector::PseudoPart) {
80        const AtomicString& pseudoId = selector->pseudoType() == CSSSelector::PseudoWebKitCustomElement ? element->shadowPseudoId() : element->pseudo();
81        if (pseudoId != selector->value())
82            return false;
83        if (selector->pseudoType() == CSSSelector::PseudoWebKitCustomElement && root->type() != ShadowRoot::UserAgentShadowRoot)
84            return false;
85        return true;
86    }
87
88    if (element->part() != selector->argument())
89        return false;
90    if (selector->isMatchUserAgentOnly() && root->type() != ShadowRoot::UserAgentShadowRoot)
91        return false;
92    return true;
93}
94
95Element* SelectorChecker::parentElement(const SelectorCheckingContext& context) const
96{
97    // CrossesBoundary means we don't care any context.scope. So we can walk up from a shadow root to its shadow host.
98    if ((context.behaviorAtBoundary & SelectorChecker::BoundaryBehaviorMask) == SelectorChecker::CrossesBoundary)
99        return context.element->parentOrShadowHostElement();
100
101    // If context.scope is not a shadow host, we cannot walk up from a shadow root to its shadow host.
102    if (!(context.behaviorAtBoundary & SelectorChecker::ScopeIsShadowHost))
103        return context.element->parentElement();
104
105    // If behaviorAtBoundary is StaysWithInTreeScope, we cannot walk up from a shadow root to its shadow host.
106    return (context.behaviorAtBoundary & SelectorChecker::BoundaryBehaviorMask) != SelectorChecker::StaysWithinTreeScope ? context.element->parentOrShadowHostElement() : context.element->parentElement();
107}
108
109bool SelectorChecker::scopeContainsLastMatchedElement(const SelectorCheckingContext& context) const
110{
111    if (!(context.behaviorAtBoundary & SelectorChecker::ScopeContainsLastMatchedElement))
112        return true;
113
114    ASSERT(context.scope);
115    // If behaviorAtBoundary is not ScopeIsShadowHost, we can use "contains".
116    if (!(context.behaviorAtBoundary & SelectorChecker::ScopeIsShadowHost))
117        return context.scope->contains(context.element);
118
119    // If a given element is scope, i.e. shadow host, matches.
120    if (context.element == context.scope)
121        return true;
122
123    ShadowRoot* root = context.element->containingShadowRoot();
124    if (!root)
125        return false;
126
127    // If a host of the containing shadow root is scope, matches.
128    return root->host() == context.scope;
129}
130
131// Recursive check of selectors and combinators
132// It can return 4 different values:
133// * SelectorMatches          - the selector matches the element e
134// * SelectorFailsLocally     - the selector fails for the element e
135// * SelectorFailsAllSiblings - the selector fails for e and any sibling of e
136// * SelectorFailsCompletely  - the selector fails for e and any sibling or ancestor of e
137template<typename SiblingTraversalStrategy>
138SelectorChecker::Match SelectorChecker::match(const SelectorCheckingContext& context, PseudoId& dynamicPseudo, const SiblingTraversalStrategy& siblingTraversalStrategy) const
139{
140    // first selector has to match
141    if (!checkOne(context, siblingTraversalStrategy))
142        return SelectorFailsLocally;
143
144    if (context.selector->m_match == CSSSelector::PseudoElement) {
145        if (context.selector->isCustomPseudoElement()) {
146            if (!matchesCustomPseudoElement(context.element, context.selector))
147                return SelectorFailsLocally;
148        } else if (context.selector->isContentPseudoElement()) {
149            if (!context.element->isInShadowTree() || !context.element->isInsertionPoint())
150                return SelectorFailsLocally;
151        } else {
152            if ((!context.elementStyle && m_mode == ResolvingStyle) || m_mode == QueryingRules)
153                return SelectorFailsLocally;
154
155            PseudoId pseudoId = CSSSelector::pseudoId(context.selector->pseudoType());
156            if (pseudoId == FIRST_LETTER) {
157                if (Document* document = context.element->document())
158                    document->styleSheetCollection()->setUsesFirstLetterRules(true);
159            }
160            if (pseudoId != NOPSEUDO && m_mode != SharingRules)
161                dynamicPseudo = pseudoId;
162        }
163    }
164
165    // The rest of the selectors has to match
166    CSSSelector::Relation relation = context.selector->relation();
167
168    // Prepare next selector
169    const CSSSelector* historySelector = context.selector->tagHistory();
170    if (!historySelector)
171        return scopeContainsLastMatchedElement(context) ? SelectorMatches : SelectorFailsLocally;
172
173    SelectorCheckingContext nextContext(context);
174    nextContext.selector = historySelector;
175
176    PseudoId ignoreDynamicPseudo = NOPSEUDO;
177    if (relation != CSSSelector::SubSelector) {
178        // Abort if the next selector would exceed the scope.
179        if (context.element == context.scope && (context.behaviorAtBoundary & BoundaryBehaviorMask) != StaysWithinTreeScope)
180            return SelectorFailsCompletely;
181
182        // Bail-out if this selector is irrelevant for the pseudoId
183        if (context.pseudoId != NOPSEUDO && context.pseudoId != dynamicPseudo)
184            return SelectorFailsCompletely;
185
186        // Disable :visited matching when we see the first link or try to match anything else than an ancestors.
187        if (!context.isSubSelector && (context.element->isLink() || (relation != CSSSelector::Descendant && relation != CSSSelector::Child)))
188            nextContext.visitedMatchType = VisitedMatchDisabled;
189
190        nextContext.pseudoId = NOPSEUDO;
191    }
192
193    switch (relation) {
194    case CSSSelector::Descendant:
195        if (context.selector->relationIsAffectedByPseudoContent()) {
196            for (Element* element = context.element; element; element = element->parentElement()) {
197                if (matchForShadowDistributed(element, siblingTraversalStrategy, ignoreDynamicPseudo, nextContext) == SelectorMatches)
198                    return SelectorMatches;
199            }
200            return SelectorFailsCompletely;
201        }
202        nextContext.isSubSelector = false;
203        nextContext.elementStyle = 0;
204        for (nextContext.element = parentElement(context); nextContext.element; nextContext.element = parentElement(nextContext)) {
205            Match match = this->match(nextContext, ignoreDynamicPseudo, siblingTraversalStrategy);
206            if (match == SelectorMatches || match == SelectorFailsCompletely)
207                return match;
208            if (nextContext.element == nextContext.scope && (nextContext.behaviorAtBoundary & BoundaryBehaviorMask) != StaysWithinTreeScope)
209                return SelectorFailsCompletely;
210        }
211        return SelectorFailsCompletely;
212    case CSSSelector::Child:
213        {
214            if (context.selector->relationIsAffectedByPseudoContent())
215                return matchForShadowDistributed(context.element, siblingTraversalStrategy, ignoreDynamicPseudo, nextContext);
216
217            nextContext.element = parentElement(context);
218            if (!nextContext.element)
219                return SelectorFailsCompletely;
220
221            nextContext.isSubSelector = false;
222            nextContext.elementStyle = 0;
223            return match(nextContext, ignoreDynamicPseudo, siblingTraversalStrategy);
224        }
225    case CSSSelector::DirectAdjacent:
226        if (m_mode == ResolvingStyle) {
227            if (Element* parent = parentElement(context))
228                parent->setChildrenAffectedByDirectAdjacentRules();
229        }
230        nextContext.element = context.element->previousElementSibling();
231        if (!nextContext.element)
232            return SelectorFailsAllSiblings;
233        nextContext.isSubSelector = false;
234        nextContext.elementStyle = 0;
235        return match(nextContext, ignoreDynamicPseudo, siblingTraversalStrategy);
236
237    case CSSSelector::IndirectAdjacent:
238        if (m_mode == ResolvingStyle) {
239            if (Element* parent = parentElement(context))
240                parent->setChildrenAffectedByForwardPositionalRules();
241        }
242        nextContext.element = context.element->previousElementSibling();
243        nextContext.isSubSelector = false;
244        nextContext.elementStyle = 0;
245        for (; nextContext.element; nextContext.element = nextContext.element->previousElementSibling()) {
246            Match match = this->match(nextContext, ignoreDynamicPseudo, siblingTraversalStrategy);
247            if (match == SelectorMatches || match == SelectorFailsAllSiblings || match == SelectorFailsCompletely)
248                return match;
249        };
250        return SelectorFailsAllSiblings;
251
252    case CSSSelector::SubSelector:
253        // a selector is invalid if something follows a pseudo-element
254        // We make an exception for scrollbar pseudo elements and allow a set of pseudo classes (but nothing else)
255        // to follow the pseudo elements.
256        nextContext.hasScrollbarPseudo = dynamicPseudo != NOPSEUDO && (context.scrollbar || dynamicPseudo == SCROLLBAR_CORNER || dynamicPseudo == RESIZER);
257        nextContext.hasSelectionPseudo = dynamicPseudo == SELECTION;
258        if ((context.elementStyle || m_mode == CollectingRules || m_mode == QueryingRules) && dynamicPseudo != NOPSEUDO
259            && !nextContext.hasSelectionPseudo
260            && !(nextContext.hasScrollbarPseudo && nextContext.selector->m_match == CSSSelector::PseudoClass))
261            return SelectorFailsCompletely;
262        nextContext.isSubSelector = true;
263        return match(nextContext, dynamicPseudo, siblingTraversalStrategy);
264
265    case CSSSelector::ShadowPseudo:
266        {
267            // 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.
268            if (context.scope && context.scope->treeScope() == context.element->treeScope() && (context.behaviorAtBoundary & BoundaryBehaviorMask) != StaysWithinTreeScope)
269                return SelectorFailsCompletely;
270            Element* shadowHostNode = context.element->shadowHost();
271            if (!shadowHostNode)
272                return SelectorFailsCompletely;
273            nextContext.element = shadowHostNode;
274            nextContext.isSubSelector = false;
275            nextContext.elementStyle = 0;
276            return match(nextContext, ignoreDynamicPseudo, siblingTraversalStrategy);
277        }
278    }
279
280    ASSERT_NOT_REACHED();
281    return SelectorFailsCompletely;
282}
283
284template<typename SiblingTraversalStrategy>
285SelectorChecker::Match SelectorChecker::matchForShadowDistributed(const Element* element, const SiblingTraversalStrategy& siblingTraversalStrategy, PseudoId& dynamicPseudo, SelectorCheckingContext& nextContext) const
286{
287    Vector<InsertionPoint*, 8> insertionPoints;
288    collectInsertionPointsWhereNodeIsDistributed(element, insertionPoints);
289    for (size_t i = 0; i < insertionPoints.size(); ++i) {
290        nextContext.element = insertionPoints[i];
291        nextContext.isSubSelector = false;
292        nextContext.elementStyle = 0;
293        if (match(nextContext, dynamicPseudo, siblingTraversalStrategy) == SelectorMatches)
294            return SelectorMatches;
295    }
296    return SelectorFailsCompletely;
297}
298
299static inline bool containsHTMLSpace(const AtomicString& string)
300{
301    for (unsigned i = 0; i < string.length(); i++)
302        if (isHTMLSpace(string[i]))
303            return true;
304    return false;
305}
306
307static bool attributeValueMatches(const Attribute* attributeItem, CSSSelector::Match match, const AtomicString& selectorValue, bool caseSensitive)
308{
309    const AtomicString& value = attributeItem->value();
310    if (value.isNull())
311        return false;
312
313    switch (match) {
314    case CSSSelector::Exact:
315        if (caseSensitive ? selectorValue != value : !equalIgnoringCase(selectorValue, value))
316            return false;
317        break;
318    case CSSSelector::List:
319        {
320            // Ignore empty selectors or selectors containing HTML spaces
321            if (selectorValue.isEmpty() || containsHTMLSpace(selectorValue))
322                return false;
323
324            unsigned startSearchAt = 0;
325            while (true) {
326                size_t foundPos = value.find(selectorValue, startSearchAt, caseSensitive);
327                if (foundPos == notFound)
328                    return false;
329                if (!foundPos || isHTMLSpace(value[foundPos - 1])) {
330                    unsigned endStr = foundPos + selectorValue.length();
331                    if (endStr == value.length() || isHTMLSpace(value[endStr]))
332                        break; // We found a match.
333                }
334
335                // No match. Keep looking.
336                startSearchAt = foundPos + 1;
337            }
338            break;
339        }
340    case CSSSelector::Contain:
341        if (!value.contains(selectorValue, caseSensitive) || selectorValue.isEmpty())
342            return false;
343        break;
344    case CSSSelector::Begin:
345        if (!value.startsWith(selectorValue, caseSensitive) || selectorValue.isEmpty())
346            return false;
347        break;
348    case CSSSelector::End:
349        if (!value.endsWith(selectorValue, caseSensitive) || selectorValue.isEmpty())
350            return false;
351        break;
352    case CSSSelector::Hyphen:
353        if (value.length() < selectorValue.length())
354            return false;
355        if (!value.startsWith(selectorValue, caseSensitive))
356            return false;
357        // It they start the same, check for exact match or following '-':
358        if (value.length() != selectorValue.length() && value[selectorValue.length()] != '-')
359            return false;
360        break;
361    case CSSSelector::PseudoClass:
362    case CSSSelector::PseudoElement:
363    default:
364        break;
365    }
366
367    return true;
368}
369
370static bool anyAttributeMatches(Element* element, CSSSelector::Match match, const QualifiedName& selectorAttr, const AtomicString& selectorValue, bool caseSensitive)
371{
372    ASSERT(element->hasAttributesWithoutUpdate());
373    for (size_t i = 0; i < element->attributeCount(); ++i) {
374        const Attribute* attributeItem = element->attributeItem(i);
375
376        if (!attributeItem->matches(selectorAttr))
377            continue;
378
379        if (attributeValueMatches(attributeItem, match, selectorValue, caseSensitive))
380            return true;
381    }
382
383    return false;
384}
385
386template<typename SiblingTraversalStrategy>
387bool SelectorChecker::checkOne(const SelectorCheckingContext& context, const SiblingTraversalStrategy& siblingTraversalStrategy) const
388{
389    Element* const & element = context.element;
390    const CSSSelector* const & selector = context.selector;
391    ASSERT(element);
392    ASSERT(selector);
393
394    if (selector->m_match == CSSSelector::Tag)
395        return SelectorChecker::tagMatches(element, selector->tagQName());
396
397    if (selector->m_match == CSSSelector::Class)
398        return element->hasClass() && element->classNames().contains(selector->value());
399
400    if (selector->m_match == CSSSelector::Id)
401        return element->hasID() && element->idForStyleResolution() == selector->value();
402
403    if (selector->isAttributeSelector()) {
404        const QualifiedName& attr = selector->attribute();
405
406        if (!element->hasAttributes())
407            return false;
408
409        bool caseSensitive = !m_documentIsHTML || HTMLDocument::isCaseSensitiveAttribute(attr);
410
411        if (!anyAttributeMatches(element, static_cast<CSSSelector::Match>(selector->m_match), attr, selector->value(), caseSensitive))
412            return false;
413    }
414
415    if (selector->m_match == CSSSelector::PseudoClass) {
416        // Handle :not up front.
417        if (selector->pseudoType() == CSSSelector::PseudoNot) {
418            SelectorCheckingContext subContext(context);
419            subContext.isSubSelector = true;
420            ASSERT(selector->selectorList());
421            for (subContext.selector = selector->selectorList()->first(); subContext.selector; subContext.selector = subContext.selector->tagHistory()) {
422                // :not cannot nest. I don't really know why this is a
423                // restriction in CSS3, but it is, so let's honor it.
424                // the parser enforces that this never occurs
425                ASSERT(subContext.selector->pseudoType() != CSSSelector::PseudoNot);
426                // We select between :visited and :link when applying. We don't know which one applied (or not) yet.
427                if (subContext.selector->pseudoType() == CSSSelector::PseudoVisited || (subContext.selector->pseudoType() == CSSSelector::PseudoLink && subContext.visitedMatchType == VisitedMatchEnabled))
428                    return true;
429                if (!checkOne(subContext, DOMSiblingTraversalStrategy()))
430                    return true;
431            }
432        } else if (context.hasScrollbarPseudo) {
433            // CSS scrollbars match a specific subset of pseudo classes, and they have specialized rules for each
434            // (since there are no elements involved).
435            return checkScrollbarPseudoClass(context, element->document(), selector);
436        } else if (context.hasSelectionPseudo) {
437            if (selector->pseudoType() == CSSSelector::PseudoWindowInactive)
438                return !element->document()->page()->focusController().isActive();
439        }
440
441        // Normal element pseudo class checking.
442        switch (selector->pseudoType()) {
443            // Pseudo classes:
444        case CSSSelector::PseudoNot:
445            break; // Already handled up above.
446        case CSSSelector::PseudoEmpty:
447            {
448                bool result = true;
449                for (Node* n = element->firstChild(); n; n = n->nextSibling()) {
450                    if (n->isElementNode()) {
451                        result = false;
452                        break;
453                    }
454                    if (n->isTextNode()) {
455                        Text* textNode = toText(n);
456                        if (!textNode->data().isEmpty()) {
457                            result = false;
458                            break;
459                        }
460                    }
461                }
462                if (m_mode == ResolvingStyle) {
463                    element->setStyleAffectedByEmpty();
464                    if (context.elementStyle)
465                        context.elementStyle->setEmptyState(result);
466                    else if (element->renderStyle() && (element->document()->styleSheetCollection()->usesSiblingRules() || element->renderStyle()->unique()))
467                        element->renderStyle()->setEmptyState(result);
468                }
469                return result;
470            }
471        case CSSSelector::PseudoFirstChild:
472            // first-child matches the first child that is an element
473            if (Element* parent = element->parentElement()) {
474                bool result = siblingTraversalStrategy.isFirstChild(element);
475                if (m_mode == ResolvingStyle) {
476                    RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
477                    parent->setChildrenAffectedByFirstChildRules();
478                    if (result && childStyle)
479                        childStyle->setFirstChildState();
480                }
481                return result;
482            }
483            break;
484        case CSSSelector::PseudoFirstOfType:
485            // first-of-type matches the first element of its type
486            if (Element* parent = element->parentElement()) {
487                bool result = siblingTraversalStrategy.isFirstOfType(element, element->tagQName());
488                if (m_mode == ResolvingStyle)
489                    parent->setChildrenAffectedByForwardPositionalRules();
490                return result;
491            }
492            break;
493        case CSSSelector::PseudoLastChild:
494            // last-child matches the last child that is an element
495            if (Element* parent = element->parentElement()) {
496                bool result = parent->isFinishedParsingChildren() && siblingTraversalStrategy.isLastChild(element);
497                if (m_mode == ResolvingStyle) {
498                    RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
499                    parent->setChildrenAffectedByLastChildRules();
500                    if (result && childStyle)
501                        childStyle->setLastChildState();
502                }
503                return result;
504            }
505            break;
506        case CSSSelector::PseudoLastOfType:
507            // last-of-type matches the last element of its type
508            if (Element* parent = element->parentElement()) {
509                if (m_mode == ResolvingStyle)
510                    parent->setChildrenAffectedByBackwardPositionalRules();
511                if (!parent->isFinishedParsingChildren())
512                    return false;
513                return siblingTraversalStrategy.isLastOfType(element, element->tagQName());
514            }
515            break;
516        case CSSSelector::PseudoOnlyChild:
517            if (Element* parent = element->parentElement()) {
518                bool firstChild = siblingTraversalStrategy.isFirstChild(element);
519                bool onlyChild = firstChild && parent->isFinishedParsingChildren() && siblingTraversalStrategy.isLastChild(element);
520                if (m_mode == ResolvingStyle) {
521                    RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
522                    parent->setChildrenAffectedByFirstChildRules();
523                    parent->setChildrenAffectedByLastChildRules();
524                    if (firstChild && childStyle)
525                        childStyle->setFirstChildState();
526                    if (onlyChild && childStyle)
527                        childStyle->setLastChildState();
528                }
529                return onlyChild;
530            }
531            break;
532        case CSSSelector::PseudoOnlyOfType:
533            // FIXME: This selector is very slow.
534            if (Element* parent = element->parentElement()) {
535                if (m_mode == ResolvingStyle) {
536                    parent->setChildrenAffectedByForwardPositionalRules();
537                    parent->setChildrenAffectedByBackwardPositionalRules();
538                }
539                if (!parent->isFinishedParsingChildren())
540                    return false;
541                return siblingTraversalStrategy.isFirstOfType(element, element->tagQName()) && siblingTraversalStrategy.isLastOfType(element, element->tagQName());
542            }
543            break;
544        case CSSSelector::PseudoNthChild:
545            if (!selector->parseNth())
546                break;
547            if (Element* parent = element->parentElement()) {
548                int count = 1 + siblingTraversalStrategy.countElementsBefore(element);
549                if (m_mode == ResolvingStyle) {
550                    RenderStyle* childStyle = context.elementStyle ? context.elementStyle : element->renderStyle();
551                    element->setChildIndex(count);
552                    if (childStyle)
553                        childStyle->setUnique();
554                    parent->setChildrenAffectedByForwardPositionalRules();
555                }
556
557                if (selector->matchNth(count))
558                    return true;
559            }
560            break;
561        case CSSSelector::PseudoNthOfType:
562            if (!selector->parseNth())
563                break;
564            if (Element* parent = element->parentElement()) {
565                int count = 1 + siblingTraversalStrategy.countElementsOfTypeBefore(element, element->tagQName());
566                if (m_mode == ResolvingStyle)
567                    parent->setChildrenAffectedByForwardPositionalRules();
568
569                if (selector->matchNth(count))
570                    return true;
571            }
572            break;
573        case CSSSelector::PseudoNthLastChild:
574            if (!selector->parseNth())
575                break;
576            if (Element* parent = element->parentElement()) {
577                if (m_mode == ResolvingStyle)
578                    parent->setChildrenAffectedByBackwardPositionalRules();
579                if (!parent->isFinishedParsingChildren())
580                    return false;
581                int count = 1 + siblingTraversalStrategy.countElementsAfter(element);
582                if (selector->matchNth(count))
583                    return true;
584            }
585            break;
586        case CSSSelector::PseudoNthLastOfType:
587            if (!selector->parseNth())
588                break;
589            if (Element* parent = element->parentElement()) {
590                if (m_mode == ResolvingStyle)
591                    parent->setChildrenAffectedByBackwardPositionalRules();
592                if (!parent->isFinishedParsingChildren())
593                    return false;
594
595                int count = 1 + siblingTraversalStrategy.countElementsOfTypeAfter(element, element->tagQName());
596                if (selector->matchNth(count))
597                    return true;
598            }
599            break;
600        case CSSSelector::PseudoTarget:
601            if (element == element->document()->cssTarget())
602                return true;
603            break;
604        case CSSSelector::PseudoAny:
605            {
606                SelectorCheckingContext subContext(context);
607                subContext.isSubSelector = true;
608                PseudoId ignoreDynamicPseudo = NOPSEUDO;
609                ASSERT(selector->selectorList());
610                for (subContext.selector = selector->selectorList()->first(); subContext.selector; subContext.selector = CSSSelectorList::next(subContext.selector)) {
611                    if (match(subContext, ignoreDynamicPseudo, siblingTraversalStrategy) == SelectorMatches)
612                        return true;
613                }
614            }
615            break;
616        case CSSSelector::PseudoAutofill:
617            if (!element || !element->isFormControlElement())
618                break;
619            if (element->hasTagName(inputTag))
620                return toHTMLInputElement(element)->isAutofilled();
621            break;
622        case CSSSelector::PseudoAnyLink:
623        case CSSSelector::PseudoLink:
624            // :visited and :link matches are separated later when applying the style. Here both classes match all links...
625            return element->isLink();
626        case CSSSelector::PseudoVisited:
627            // ...except if :visited matching is disabled for ancestor/sibling matching.
628            return element->isLink() && context.visitedMatchType == VisitedMatchEnabled;
629        case CSSSelector::PseudoDrag:
630            if (m_mode == ResolvingStyle) {
631                if (context.elementStyle)
632                    context.elementStyle->setAffectedByDrag();
633                else
634                    element->setChildrenAffectedByDrag(true);
635            }
636            if (element->renderer() && element->renderer()->isDragging())
637                return true;
638            break;
639        case CSSSelector::PseudoFocus:
640            return matchesFocusPseudoClass(element);
641        case CSSSelector::PseudoHover:
642            // If we're in quirks mode, then hover should never match anchors with no
643            // href and *:hover should not match anything. This is important for sites like wsj.com.
644            if (m_strictParsing || context.isSubSelector || (selector->m_match == CSSSelector::Tag && selector->tagQName() != anyQName() && !isHTMLAnchorElement(element)) || element->isLink()) {
645                if (m_mode == ResolvingStyle) {
646                    if (context.elementStyle)
647                        context.elementStyle->setAffectedByHover();
648                    else
649                        element->setChildrenAffectedByHover(true);
650                }
651                if (element->hovered() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoHover))
652                    return true;
653            }
654            break;
655        case CSSSelector::PseudoActive:
656            // If we're in quirks mode, then :active should never match anchors with no
657            // href and *:active should not match anything.
658            if (m_strictParsing || context.isSubSelector || (selector->m_match == CSSSelector::Tag && selector->tagQName() != anyQName() && !isHTMLAnchorElement(element)) || element->isLink()) {
659                if (m_mode == ResolvingStyle) {
660                    if (context.elementStyle)
661                        context.elementStyle->setAffectedByActive();
662                    else
663                        element->setChildrenAffectedByActive(true);
664                }
665                if (element->active() || InspectorInstrumentation::forcePseudoState(element, CSSSelector::PseudoActive))
666                    return true;
667            }
668            break;
669        case CSSSelector::PseudoEnabled:
670            if (element && (element->isFormControlElement() || element->hasTagName(optionTag) || isHTMLOptGroupElement(element)))
671                return !element->isDisabledFormControl();
672            break;
673        case CSSSelector::PseudoFullPageMedia:
674            return element && element->document() && element->document()->isMediaDocument();
675            break;
676        case CSSSelector::PseudoDefault:
677            return element && element->isDefaultButtonForForm();
678        case CSSSelector::PseudoDisabled:
679            if (element && (element->isFormControlElement() || element->hasTagName(optionTag) || isHTMLOptGroupElement(element)))
680                return element->isDisabledFormControl();
681            break;
682        case CSSSelector::PseudoReadOnly:
683            return element && element->matchesReadOnlyPseudoClass();
684        case CSSSelector::PseudoReadWrite:
685            return element && element->matchesReadWritePseudoClass();
686        case CSSSelector::PseudoOptional:
687            return element && element->isOptionalFormControl();
688        case CSSSelector::PseudoRequired:
689            return element && element->isRequiredFormControl();
690        case CSSSelector::PseudoValid:
691            if (!element)
692                return false;
693            element->document()->setContainsValidityStyleRules();
694            return element->willValidate() && element->isValidFormControlElement();
695        case CSSSelector::PseudoInvalid:
696            if (!element)
697                return false;
698            element->document()->setContainsValidityStyleRules();
699            return element->willValidate() && !element->isValidFormControlElement();
700        case CSSSelector::PseudoChecked:
701            {
702                if (!element)
703                    break;
704                if (element->hasTagName(inputTag)) {
705                    HTMLInputElement* inputElement = toHTMLInputElement(element);
706                    // Even though WinIE allows checked and indeterminate to
707                    // co-exist, the CSS selector spec says that you can't be
708                    // both checked and indeterminate. We will behave like WinIE
709                    // behind the scenes and just obey the CSS spec here in the
710                    // test for matching the pseudo.
711                    if (inputElement->shouldAppearChecked() && !inputElement->shouldAppearIndeterminate())
712                        return true;
713                } else if (element->hasTagName(optionTag) && toHTMLOptionElement(element)->selected())
714                    return true;
715                break;
716            }
717        case CSSSelector::PseudoIndeterminate:
718            return element && element->shouldAppearIndeterminate();
719        case CSSSelector::PseudoRoot:
720            if (element == element->document()->documentElement())
721                return true;
722            break;
723        case CSSSelector::PseudoLang:
724            {
725                AtomicString value;
726                if (element->isWebVTTElement())
727                    value = toWebVTTElement(element)->language();
728                else
729                    value = element->computeInheritedLanguage();
730                const AtomicString& argument = selector->argument();
731                if (value.isEmpty() || !value.startsWith(argument, false))
732                    break;
733                if (value.length() != argument.length() && value[argument.length()] != '-')
734                    break;
735                return true;
736            }
737        case CSSSelector::PseudoFullScreen:
738            // While a Document is in the fullscreen state, and the document's current fullscreen
739            // element is an element in the document, the 'full-screen' pseudoclass applies to
740            // that element. Also, an <iframe>, <object> or <embed> element whose child browsing
741            // context's Document is in the fullscreen state has the 'full-screen' pseudoclass applied.
742            if (element->isFrameElementBase() && element->containsFullScreenElement())
743                return true;
744            if (FullscreenElementStack* fullscreen = FullscreenElementStack::fromIfExists(element->document())) {
745                if (!fullscreen->webkitIsFullScreen())
746                    return false;
747                return element == fullscreen->webkitCurrentFullScreenElement();
748            }
749            return false;
750        case CSSSelector::PseudoFullScreenAncestor:
751            return element->containsFullScreenElement();
752        case CSSSelector::PseudoFullScreenDocument:
753            // While a Document is in the fullscreen state, the 'full-screen-document' pseudoclass applies
754            // to all elements of that Document.
755            if (!FullscreenElementStack::isFullScreen(element->document()))
756                return false;
757            return true;
758        case CSSSelector::PseudoSeamlessDocument:
759            // While a document is rendered in a seamless iframe, the 'seamless-document' pseudoclass applies
760            // to all elements of that Document.
761            return element->document()->shouldDisplaySeamlesslyWithParent();
762        case CSSSelector::PseudoInRange:
763            if (!element)
764                return false;
765            element->document()->setContainsValidityStyleRules();
766            return element->isInRange();
767        case CSSSelector::PseudoOutOfRange:
768            if (!element)
769                return false;
770            element->document()->setContainsValidityStyleRules();
771            return element->isOutOfRange();
772        case CSSSelector::PseudoFutureCue:
773            return (element->isWebVTTElement() && !toWebVTTElement(element)->isPastNode());
774        case CSSSelector::PseudoPastCue:
775            return (element->isWebVTTElement() && toWebVTTElement(element)->isPastNode());
776
777        case CSSSelector::PseudoScope:
778            {
779                const Node* contextualReferenceNode = !context.scope || (context.behaviorAtBoundary & BoundaryBehaviorMask) == CrossesBoundary ? element->document()->documentElement() : context.scope;
780                if (element == contextualReferenceNode)
781                    return true;
782                break;
783            }
784
785        case CSSSelector::PseudoUnresolved:
786            if (element->isUnresolvedCustomElement())
787                return true;
788            break;
789
790        case CSSSelector::PseudoHost:
791            {
792                // :host only matches a shadow host when :host is in a shadow tree of the shadow host.
793                if (!context.scope || !(context.behaviorAtBoundary & ScopeIsShadowHost) || context.scope != element)
794                    return false;
795                ASSERT(element->shadow());
796
797                // For empty parameter case, i.e. just :host or :host().
798                if (!selector->selectorList())
799                    return true;
800
801                SelectorCheckingContext subContext(context);
802                subContext.isSubSelector = true;
803                subContext.behaviorAtBoundary = CrossesBoundary;
804                subContext.scope = 0;
805                // Use NodeRenderingTraversal to traverse a composed ancestor list of a given element.
806                for (Element* nextElement = NodeRenderingTraversal::parentElement(element); nextElement; nextElement = NodeRenderingTraversal::parentElement(nextElement)) {
807                    // If one of simple selectors matches an element, returns SelectorMatches. Just "OR".
808                    for (subContext.selector = selector->selectorList()->first(); subContext.selector; subContext.selector = CSSSelectorList::next(subContext.selector)) {
809                        PseudoId ignoreDynamicPseudo = NOPSEUDO;
810                        subContext.element = nextElement;
811                        if (match(subContext, ignoreDynamicPseudo, siblingTraversalStrategy) == SelectorMatches)
812                            return true;
813                    }
814                }
815            }
816            break;
817
818        case CSSSelector::PseudoHorizontal:
819        case CSSSelector::PseudoVertical:
820        case CSSSelector::PseudoDecrement:
821        case CSSSelector::PseudoIncrement:
822        case CSSSelector::PseudoStart:
823        case CSSSelector::PseudoEnd:
824        case CSSSelector::PseudoDoubleButton:
825        case CSSSelector::PseudoSingleButton:
826        case CSSSelector::PseudoNoButton:
827        case CSSSelector::PseudoCornerPresent:
828            return false;
829
830        case CSSSelector::PseudoUnknown:
831        case CSSSelector::PseudoNotParsed:
832        default:
833            ASSERT_NOT_REACHED();
834            break;
835        }
836        return false;
837    }
838    else if (selector->m_match == CSSSelector::PseudoElement && selector->pseudoType() == CSSSelector::PseudoCue) {
839        SelectorCheckingContext subContext(context);
840        subContext.isSubSelector = true;
841        subContext.behaviorAtBoundary = StaysWithinTreeScope;
842
843        PseudoId ignoreDynamicPseudo = NOPSEUDO;
844        const CSSSelector* const & selector = context.selector;
845        for (subContext.selector = selector->selectorList()->first(); subContext.selector; subContext.selector = CSSSelectorList::next(subContext.selector)) {
846            if (match(subContext, ignoreDynamicPseudo, siblingTraversalStrategy) == SelectorMatches)
847                return true;
848        }
849        return false;
850    }
851    // ### add the rest of the checks...
852    return true;
853}
854
855bool SelectorChecker::checkScrollbarPseudoClass(const SelectorCheckingContext& context, Document* document, const CSSSelector* selector) const
856{
857    RenderScrollbar* scrollbar = context.scrollbar;
858    ScrollbarPart part = context.scrollbarPart;
859
860    // FIXME: This is a temporary hack for resizers and scrollbar corners. Eventually :window-inactive should become a real
861    // pseudo class and just apply to everything.
862    if (selector->pseudoType() == CSSSelector::PseudoWindowInactive)
863        return !document->page()->focusController().isActive();
864
865    if (!scrollbar)
866        return false;
867
868    ASSERT(selector->m_match == CSSSelector::PseudoClass);
869    switch (selector->pseudoType()) {
870    case CSSSelector::PseudoEnabled:
871        return scrollbar->enabled();
872    case CSSSelector::PseudoDisabled:
873        return !scrollbar->enabled();
874    case CSSSelector::PseudoHover:
875        {
876            ScrollbarPart hoveredPart = scrollbar->hoveredPart();
877            if (part == ScrollbarBGPart)
878                return hoveredPart != NoPart;
879            if (part == TrackBGPart)
880                return hoveredPart == BackTrackPart || hoveredPart == ForwardTrackPart || hoveredPart == ThumbPart;
881            return part == hoveredPart;
882        }
883    case CSSSelector::PseudoActive:
884        {
885            ScrollbarPart pressedPart = scrollbar->pressedPart();
886            if (part == ScrollbarBGPart)
887                return pressedPart != NoPart;
888            if (part == TrackBGPart)
889                return pressedPart == BackTrackPart || pressedPart == ForwardTrackPart || pressedPart == ThumbPart;
890            return part == pressedPart;
891        }
892    case CSSSelector::PseudoHorizontal:
893        return scrollbar->orientation() == HorizontalScrollbar;
894    case CSSSelector::PseudoVertical:
895        return scrollbar->orientation() == VerticalScrollbar;
896    case CSSSelector::PseudoDecrement:
897        return part == BackButtonStartPart || part == BackButtonEndPart || part == BackTrackPart;
898    case CSSSelector::PseudoIncrement:
899        return part == ForwardButtonStartPart || part == ForwardButtonEndPart || part == ForwardTrackPart;
900    case CSSSelector::PseudoStart:
901        return part == BackButtonStartPart || part == ForwardButtonStartPart || part == BackTrackPart;
902    case CSSSelector::PseudoEnd:
903        return part == BackButtonEndPart || part == ForwardButtonEndPart || part == ForwardTrackPart;
904    case CSSSelector::PseudoDoubleButton:
905        {
906            ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
907            if (part == BackButtonStartPart || part == ForwardButtonStartPart || part == BackTrackPart)
908                return buttonsPlacement == ScrollbarButtonsDoubleStart || buttonsPlacement == ScrollbarButtonsDoubleBoth;
909            if (part == BackButtonEndPart || part == ForwardButtonEndPart || part == ForwardTrackPart)
910                return buttonsPlacement == ScrollbarButtonsDoubleEnd || buttonsPlacement == ScrollbarButtonsDoubleBoth;
911            return false;
912        }
913    case CSSSelector::PseudoSingleButton:
914        {
915            ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
916            if (part == BackButtonStartPart || part == ForwardButtonEndPart || part == BackTrackPart || part == ForwardTrackPart)
917                return buttonsPlacement == ScrollbarButtonsSingle;
918            return false;
919        }
920    case CSSSelector::PseudoNoButton:
921        {
922            ScrollbarButtonsPlacement buttonsPlacement = scrollbar->theme()->buttonsPlacement();
923            if (part == BackTrackPart)
924                return buttonsPlacement == ScrollbarButtonsNone || buttonsPlacement == ScrollbarButtonsDoubleEnd;
925            if (part == ForwardTrackPart)
926                return buttonsPlacement == ScrollbarButtonsNone || buttonsPlacement == ScrollbarButtonsDoubleStart;
927            return false;
928        }
929    case CSSSelector::PseudoCornerPresent:
930        return scrollbar->scrollableArea()->isScrollCornerVisible();
931    default:
932        return false;
933    }
934}
935
936unsigned SelectorChecker::determineLinkMatchType(const CSSSelector* selector)
937{
938    unsigned linkMatchType = MatchAll;
939
940    // Statically determine if this selector will match a link in visited, unvisited or any state, or never.
941    // :visited never matches other elements than the innermost link element.
942    for (; selector; selector = selector->tagHistory()) {
943        switch (selector->pseudoType()) {
944        case CSSSelector::PseudoNot:
945            {
946                // :not(:visited) is equivalent to :link. Parser enforces that :not can't nest.
947                ASSERT(selector->selectorList());
948                for (const CSSSelector* subSelector = selector->selectorList()->first(); subSelector; subSelector = subSelector->tagHistory()) {
949                    CSSSelector::PseudoType subType = subSelector->pseudoType();
950                    if (subType == CSSSelector::PseudoVisited)
951                        linkMatchType &= ~SelectorChecker::MatchVisited;
952                    else if (subType == CSSSelector::PseudoLink)
953                        linkMatchType &= ~SelectorChecker::MatchLink;
954                }
955            }
956            break;
957        case CSSSelector::PseudoLink:
958            linkMatchType &= ~SelectorChecker::MatchVisited;
959            break;
960        case CSSSelector::PseudoVisited:
961            linkMatchType &= ~SelectorChecker::MatchLink;
962            break;
963        default:
964            // We don't support :link and :visited inside :-webkit-any.
965            break;
966        }
967        CSSSelector::Relation relation = selector->relation();
968        if (relation == CSSSelector::SubSelector)
969            continue;
970        if (relation != CSSSelector::Descendant && relation != CSSSelector::Child)
971            return linkMatchType;
972        if (linkMatchType != MatchAll)
973            return linkMatchType;
974    }
975    return linkMatchType;
976}
977
978bool SelectorChecker::isFrameFocused(const Element* element)
979{
980    return element->document()->frame() && element->document()->frame()->selection()->isFocusedAndActive();
981}
982
983bool SelectorChecker::matchesFocusPseudoClass(const Element* element)
984{
985    if (InspectorInstrumentation::forcePseudoState(const_cast<Element*>(element), CSSSelector::PseudoFocus))
986        return true;
987    return element->focused() && isFrameFocused(element);
988}
989
990template
991SelectorChecker::Match SelectorChecker::match(const SelectorCheckingContext&, PseudoId&, const DOMSiblingTraversalStrategy&) const;
992
993template
994SelectorChecker::Match SelectorChecker::match(const SelectorCheckingContext&, PseudoId&, const ShadowDOMSiblingTraversalStrategy&) const;
995
996}
997