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 * Copyright (C) 2013 Google Inc. All rights reserved.
12 *
13 * This library is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU Library General Public
15 * License as published by the Free Software Foundation; either
16 * version 2 of the License, or (at your option) any later version.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21 * Library General Public License for more details.
22 *
23 * You should have received a copy of the GNU Library General Public License
24 * along with this library; see the file COPYING.LIB.  If not, write to
25 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
26 * Boston, MA 02110-1301, USA.
27 */
28
29#include "config.h"
30#include "SelectorCheckerFastPath.h"
31
32#include "HTMLDocument.h"
33#include "HTMLNames.h"
34#include "StyledElement.h"
35
36namespace WebCore {
37
38using namespace HTMLNames;
39
40namespace {
41
42template <bool checkValue(const Element*, const CSSSelector*)>
43inline bool fastCheckSingleSelector(const CSSSelector*& selector, const Element*& element, const CSSSelector*& topChildOrSubselector, const Element*& topChildOrSubselectorMatchElement)
44{
45    for (; element; element = element->parentElement()) {
46        if (checkValue(element, selector)) {
47            if (selector->relation() == CSSSelector::Descendant)
48                topChildOrSubselector = 0;
49            else if (!topChildOrSubselector) {
50                ASSERT(selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector);
51                topChildOrSubselector = selector;
52                topChildOrSubselectorMatchElement = element;
53            }
54            if (selector->relation() != CSSSelector::SubSelector)
55                element = element->parentElement();
56            selector = selector->tagHistory();
57            return true;
58        }
59        if (topChildOrSubselector) {
60            // Child or subselector check failed.
61            // If the match element is null, topChildOrSubselector was also the very topmost selector and had to match
62            // the original element we were checking.
63            if (!topChildOrSubselectorMatchElement)
64                return false;
65            // There may be other matches down the ancestor chain.
66            // Rewind to the topmost child or subselector and the element it matched, continue checking ancestors.
67            selector = topChildOrSubselector;
68            element = topChildOrSubselectorMatchElement->parentElement();
69            topChildOrSubselector = 0;
70            return true;
71        }
72    }
73    return false;
74}
75
76inline bool checkClassValue(const Element* element, const CSSSelector* selector)
77{
78    return element->hasClass() && element->classNames().contains(selector->value());
79}
80
81inline bool checkIDValue(const Element* element, const CSSSelector* selector)
82{
83    return element->hasID() && element->idForStyleResolution().impl() == selector->value().impl();
84}
85
86inline bool checkExactAttributeValue(const Element* element, const CSSSelector* selector)
87{
88    return SelectorChecker::checkExactAttribute(element, selector->attribute(), selector->value().impl());
89}
90
91inline bool checkTagValue(const Element* element, const CSSSelector* selector)
92{
93    return SelectorChecker::tagMatches(element, selector->tagQName());
94}
95
96}
97
98SelectorCheckerFastPath::SelectorCheckerFastPath(const CSSSelector* selector, const Element* element)
99    : m_selector(selector)
100    , m_element(element)
101{
102}
103
104bool SelectorCheckerFastPath::matchesRightmostSelector(SelectorChecker::VisitedMatchType visitedMatchType) const
105{
106    ASSERT(SelectorCheckerFastPath::canUse(m_selector));
107
108    switch (m_selector->m_match) {
109    case CSSSelector::Tag:
110        return checkTagValue(m_element, m_selector);
111    case CSSSelector::Class:
112        return checkClassValue(m_element, m_selector);
113    case CSSSelector::Id:
114        return checkIDValue(m_element, m_selector);
115    case CSSSelector::Exact:
116    case CSSSelector::Set:
117        return checkExactAttributeValue(m_element, m_selector);
118    case CSSSelector::PseudoClass:
119        return commonPseudoClassSelectorMatches(visitedMatchType);
120    default:
121        ASSERT_NOT_REACHED();
122    }
123    return false;
124}
125
126bool SelectorCheckerFastPath::matches() const
127{
128    ASSERT(matchesRightmostSelector(SelectorChecker::VisitedMatchEnabled));
129    const CSSSelector* selector = m_selector;
130    const Element* element = m_element;
131
132    const CSSSelector* topChildOrSubselector = 0;
133    const Element* topChildOrSubselectorMatchElement = 0;
134    if (selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector)
135        topChildOrSubselector = selector;
136
137    if (selector->relation() != CSSSelector::SubSelector)
138        element = element->parentElement();
139
140    selector = selector->tagHistory();
141
142    // We know this compound selector has descendant, child and subselector combinators only and all components are simple.
143    while (selector) {
144        switch (selector->m_match) {
145        case CSSSelector::Class:
146            if (!fastCheckSingleSelector<checkClassValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
147                return false;
148            break;
149        case CSSSelector::Id:
150            if (!fastCheckSingleSelector<checkIDValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
151                return false;
152            break;
153        case CSSSelector::Tag:
154            if (!fastCheckSingleSelector<checkTagValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
155                return false;
156            break;
157        case CSSSelector::Set:
158        case CSSSelector::Exact:
159            if (!fastCheckSingleSelector<checkExactAttributeValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
160                return false;
161            break;
162        default:
163            ASSERT_NOT_REACHED();
164        }
165    }
166    return true;
167}
168
169static inline bool isFastCheckableRelation(CSSSelector::Relation relation)
170{
171    return relation == CSSSelector::Descendant || relation == CSSSelector::Child || relation == CSSSelector::SubSelector;
172}
173
174static inline bool isFastCheckableMatch(const CSSSelector* selector)
175{
176    if (selector->m_match == CSSSelector::Set) {
177        // Style attribute is generated lazily but the fast path doesn't trigger it.
178        // Disallow them here rather than making the fast path more branchy.
179        return selector->attribute() != styleAttr;
180    }
181    if (selector->m_match == CSSSelector::Exact)
182        return selector->attribute() != styleAttr && HTMLDocument::isCaseSensitiveAttribute(selector->attribute());
183    return selector->m_match == CSSSelector::Tag || selector->m_match == CSSSelector::Id || selector->m_match == CSSSelector::Class;
184}
185
186static inline bool isFastCheckableRightmostSelector(const CSSSelector* selector)
187{
188    if (!isFastCheckableRelation(selector->relation()))
189        return false;
190    return isFastCheckableMatch(selector) || SelectorChecker::isCommonPseudoClassSelector(selector);
191}
192
193bool SelectorCheckerFastPath::canUse(const CSSSelector* selector)
194{
195    if (!isFastCheckableRightmostSelector(selector))
196        return false;
197    for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
198        if (!isFastCheckableRelation(selector->relation()))
199            return false;
200        if (!isFastCheckableMatch(selector))
201            return false;
202    }
203    return true;
204}
205
206bool SelectorCheckerFastPath::commonPseudoClassSelectorMatches(SelectorChecker::VisitedMatchType visitedMatchType) const
207{
208    ASSERT(SelectorChecker::isCommonPseudoClassSelector(m_selector));
209    switch (m_selector->pseudoType()) {
210    case CSSSelector::PseudoLink:
211    case CSSSelector::PseudoAnyLink:
212        return m_element->isLink();
213    case CSSSelector::PseudoVisited:
214        return m_element->isLink() && visitedMatchType == SelectorChecker::VisitedMatchEnabled;
215    case CSSSelector::PseudoFocus:
216        return SelectorChecker::matchesFocusPseudoClass(m_element);
217    default:
218        ASSERT_NOT_REACHED();
219    }
220    return true;
221}
222
223
224}
225