1/*
2 * Copyright (C) 1999-2003 Lars Knoll (knoll@kde.org)
3 *               1999 Waldo Bastian (bastian@kde.org)
4 *               2001 Andreas Schlapbach (schlpbch@iam.unibe.ch)
5 *               2001-2003 Dirk Mueller (mueller@kde.org)
6 * Copyright (C) 2002, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
7 * Copyright (C) 2008 David Smith (catfish.man@gmail.com)
8 * Copyright (C) 2010 Google Inc. All rights reserved.
9 *
10 * This library is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU Library General Public
12 * License as published by the Free Software Foundation; either
13 * version 2 of the License, or (at your option) any later version.
14 *
15 * This library is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18 * Library General Public License for more details.
19 *
20 * You should have received a copy of the GNU Library General Public License
21 * along with this library; see the file COPYING.LIB.  If not, write to
22 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
23 * Boston, MA 02110-1301, USA.
24 */
25
26#include "config.h"
27#include "core/css/CSSSelector.h"
28
29#include "HTMLNames.h"
30#include "RuntimeEnabledFeatures.h"
31#include "core/css/CSSOMUtils.h"
32#include "core/css/CSSSelectorList.h"
33#include "wtf/Assertions.h"
34#include "wtf/HashMap.h"
35#include "wtf/StdLibExtras.h"
36#include "wtf/text/StringBuilder.h"
37#include "wtf/text/StringHash.h"
38
39namespace WebCore {
40
41using namespace HTMLNames;
42
43struct SameSizeAsCSSSelector {
44    unsigned bitfields;
45    void *pointers[1];
46};
47
48COMPILE_ASSERT(sizeof(CSSSelector) == sizeof(SameSizeAsCSSSelector), CSSSelectorShouldStaySmall);
49
50void CSSSelector::createRareData()
51{
52    ASSERT(m_match != Tag);
53    if (m_hasRareData)
54        return;
55    // Move the value to the rare data stucture.
56    m_data.m_rareData = RareData::create(adoptRef(m_data.m_value)).leakRef();
57    m_hasRareData = true;
58}
59
60unsigned CSSSelector::specificity() const
61{
62    // make sure the result doesn't overflow
63    static const unsigned maxValueMask = 0xffffff;
64    static const unsigned idMask = 0xff0000;
65    static const unsigned classMask = 0xff00;
66    static const unsigned elementMask = 0xff;
67
68    if (isForPage())
69        return specificityForPage() & maxValueMask;
70
71    unsigned total = 0;
72    unsigned temp = 0;
73
74    for (const CSSSelector* selector = this; selector; selector = selector->tagHistory()) {
75        temp = total + selector->specificityForOneSelector();
76        // Clamp each component to its max in the case of overflow.
77        if ((temp & idMask) < (total & idMask))
78            total |= idMask;
79        else if ((temp & classMask) < (total & classMask))
80            total |= classMask;
81        else if ((temp & elementMask) < (total & elementMask))
82            total |= elementMask;
83        else
84            total = temp;
85    }
86    return total;
87}
88
89inline unsigned CSSSelector::specificityForOneSelector() const
90{
91    // FIXME: Pseudo-elements and pseudo-classes do not have the same specificity. This function
92    // isn't quite correct.
93    switch (m_match) {
94    case Id:
95        return 0x10000;
96    case PseudoClass:
97        if (pseudoType() == PseudoHost)
98            return 0;
99        // fall through.
100    case Exact:
101    case Class:
102    case Set:
103    case List:
104    case Hyphen:
105    case PseudoElement:
106    case Contain:
107    case Begin:
108    case End:
109        // FIXME: PseudoAny should base the specificity on the sub-selectors.
110        // See http://lists.w3.org/Archives/Public/www-style/2010Sep/0530.html
111        if (pseudoType() == PseudoNot) {
112            ASSERT(selectorList());
113            return selectorList()->first()->specificityForOneSelector();
114        }
115        return 0x100;
116    case Tag:
117        return (tagQName().localName() != starAtom) ? 1 : 0;
118    case Unknown:
119        return 0;
120    }
121    ASSERT_NOT_REACHED();
122    return 0;
123}
124
125unsigned CSSSelector::specificityForPage() const
126{
127    // See http://dev.w3.org/csswg/css3-page/#cascading-and-page-context
128    unsigned s = 0;
129
130    for (const CSSSelector* component = this; component; component = component->tagHistory()) {
131        switch (component->m_match) {
132        case Tag:
133            s += tagQName().localName() == starAtom ? 0 : 4;
134            break;
135        case PagePseudoClass:
136            switch (component->pseudoType()) {
137            case PseudoFirstPage:
138                s += 2;
139                break;
140            case PseudoLeftPage:
141            case PseudoRightPage:
142                s += 1;
143                break;
144            case PseudoNotParsed:
145                break;
146            default:
147                ASSERT_NOT_REACHED();
148            }
149            break;
150        default:
151            break;
152        }
153    }
154    return s;
155}
156
157PseudoId CSSSelector::pseudoId(PseudoType type)
158{
159    switch (type) {
160    case PseudoFirstLine:
161        return FIRST_LINE;
162    case PseudoFirstLetter:
163        return FIRST_LETTER;
164    case PseudoSelection:
165        return SELECTION;
166    case PseudoBefore:
167        return BEFORE;
168    case PseudoAfter:
169        return AFTER;
170    case PseudoBackdrop:
171        return BACKDROP;
172    case PseudoScrollbar:
173        return SCROLLBAR;
174    case PseudoScrollbarButton:
175        return SCROLLBAR_BUTTON;
176    case PseudoScrollbarCorner:
177        return SCROLLBAR_CORNER;
178    case PseudoScrollbarThumb:
179        return SCROLLBAR_THUMB;
180    case PseudoScrollbarTrack:
181        return SCROLLBAR_TRACK;
182    case PseudoScrollbarTrackPiece:
183        return SCROLLBAR_TRACK_PIECE;
184    case PseudoResizer:
185        return RESIZER;
186    case PseudoFullScreen:
187        return FULL_SCREEN;
188    case PseudoFullScreenDocument:
189        return FULL_SCREEN_DOCUMENT;
190    case PseudoFullScreenAncestor:
191        return FULL_SCREEN_ANCESTOR;
192    case PseudoUnknown:
193    case PseudoEmpty:
194    case PseudoFirstChild:
195    case PseudoFirstOfType:
196    case PseudoLastChild:
197    case PseudoLastOfType:
198    case PseudoOnlyChild:
199    case PseudoOnlyOfType:
200    case PseudoNthChild:
201    case PseudoNthOfType:
202    case PseudoNthLastChild:
203    case PseudoNthLastOfType:
204    case PseudoLink:
205    case PseudoVisited:
206    case PseudoAny:
207    case PseudoAnyLink:
208    case PseudoAutofill:
209    case PseudoHover:
210    case PseudoDrag:
211    case PseudoFocus:
212    case PseudoActive:
213    case PseudoChecked:
214    case PseudoEnabled:
215    case PseudoFullPageMedia:
216    case PseudoDefault:
217    case PseudoDisabled:
218    case PseudoOptional:
219    case PseudoRequired:
220    case PseudoReadOnly:
221    case PseudoReadWrite:
222    case PseudoValid:
223    case PseudoInvalid:
224    case PseudoIndeterminate:
225    case PseudoTarget:
226    case PseudoLang:
227    case PseudoNot:
228    case PseudoRoot:
229    case PseudoScope:
230    case PseudoScrollbarBack:
231    case PseudoScrollbarForward:
232    case PseudoWindowInactive:
233    case PseudoCornerPresent:
234    case PseudoDecrement:
235    case PseudoIncrement:
236    case PseudoHorizontal:
237    case PseudoVertical:
238    case PseudoStart:
239    case PseudoEnd:
240    case PseudoDoubleButton:
241    case PseudoSingleButton:
242    case PseudoNoButton:
243    case PseudoFirstPage:
244    case PseudoLeftPage:
245    case PseudoRightPage:
246    case PseudoInRange:
247    case PseudoOutOfRange:
248    case PseudoUserAgentCustomElement:
249    case PseudoWebKitCustomElement:
250    case PseudoCue:
251    case PseudoFutureCue:
252    case PseudoPastCue:
253    case PseudoSeamlessDocument:
254    case PseudoDistributed:
255    case PseudoUnresolved:
256    case PseudoContent:
257    case PseudoHost:
258        return NOPSEUDO;
259    case PseudoNotParsed:
260        ASSERT_NOT_REACHED();
261        return NOPSEUDO;
262    }
263
264    ASSERT_NOT_REACHED();
265    return NOPSEUDO;
266}
267
268static HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoTypeMap()
269{
270    DEFINE_STATIC_LOCAL(AtomicString, active, ("active", AtomicString::ConstructFromLiteral));
271    DEFINE_STATIC_LOCAL(AtomicString, after, ("after", AtomicString::ConstructFromLiteral));
272    DEFINE_STATIC_LOCAL(AtomicString, any, ("-webkit-any(", AtomicString::ConstructFromLiteral));
273    DEFINE_STATIC_LOCAL(AtomicString, anyLink, ("-webkit-any-link", AtomicString::ConstructFromLiteral));
274    DEFINE_STATIC_LOCAL(AtomicString, autofill, ("-webkit-autofill", AtomicString::ConstructFromLiteral));
275    DEFINE_STATIC_LOCAL(AtomicString, backdrop, ("backdrop", AtomicString::ConstructFromLiteral));
276    DEFINE_STATIC_LOCAL(AtomicString, before, ("before", AtomicString::ConstructFromLiteral));
277    DEFINE_STATIC_LOCAL(AtomicString, checked, ("checked", AtomicString::ConstructFromLiteral));
278    DEFINE_STATIC_LOCAL(AtomicString, defaultString, ("default", AtomicString::ConstructFromLiteral));
279    DEFINE_STATIC_LOCAL(AtomicString, disabled, ("disabled", AtomicString::ConstructFromLiteral));
280    DEFINE_STATIC_LOCAL(AtomicString, readOnly, ("read-only", AtomicString::ConstructFromLiteral));
281    DEFINE_STATIC_LOCAL(AtomicString, readWrite, ("read-write", AtomicString::ConstructFromLiteral));
282    DEFINE_STATIC_LOCAL(AtomicString, valid, ("valid", AtomicString::ConstructFromLiteral));
283    DEFINE_STATIC_LOCAL(AtomicString, invalid, ("invalid", AtomicString::ConstructFromLiteral));
284    DEFINE_STATIC_LOCAL(AtomicString, drag, ("-webkit-drag", AtomicString::ConstructFromLiteral));
285    DEFINE_STATIC_LOCAL(AtomicString, empty, ("empty", AtomicString::ConstructFromLiteral));
286    DEFINE_STATIC_LOCAL(AtomicString, enabled, ("enabled", AtomicString::ConstructFromLiteral));
287    DEFINE_STATIC_LOCAL(AtomicString, firstChild, ("first-child", AtomicString::ConstructFromLiteral));
288    DEFINE_STATIC_LOCAL(AtomicString, firstLetter, ("first-letter", AtomicString::ConstructFromLiteral));
289    DEFINE_STATIC_LOCAL(AtomicString, firstLine, ("first-line", AtomicString::ConstructFromLiteral));
290    DEFINE_STATIC_LOCAL(AtomicString, firstOfType, ("first-of-type", AtomicString::ConstructFromLiteral));
291    DEFINE_STATIC_LOCAL(AtomicString, fullPageMedia, ("-webkit-full-page-media", AtomicString::ConstructFromLiteral));
292    DEFINE_STATIC_LOCAL(AtomicString, nthChild, ("nth-child(", AtomicString::ConstructFromLiteral));
293    DEFINE_STATIC_LOCAL(AtomicString, nthOfType, ("nth-of-type(", AtomicString::ConstructFromLiteral));
294    DEFINE_STATIC_LOCAL(AtomicString, nthLastChild, ("nth-last-child(", AtomicString::ConstructFromLiteral));
295    DEFINE_STATIC_LOCAL(AtomicString, nthLastOfType, ("nth-last-of-type(", AtomicString::ConstructFromLiteral));
296    DEFINE_STATIC_LOCAL(AtomicString, focus, ("focus", AtomicString::ConstructFromLiteral));
297    DEFINE_STATIC_LOCAL(AtomicString, hover, ("hover", AtomicString::ConstructFromLiteral));
298    DEFINE_STATIC_LOCAL(AtomicString, indeterminate, ("indeterminate", AtomicString::ConstructFromLiteral));
299    DEFINE_STATIC_LOCAL(AtomicString, lastChild, ("last-child", AtomicString::ConstructFromLiteral));
300    DEFINE_STATIC_LOCAL(AtomicString, lastOfType, ("last-of-type", AtomicString::ConstructFromLiteral));
301    DEFINE_STATIC_LOCAL(AtomicString, link, ("link", AtomicString::ConstructFromLiteral));
302    DEFINE_STATIC_LOCAL(AtomicString, lang, ("lang(", AtomicString::ConstructFromLiteral));
303    DEFINE_STATIC_LOCAL(AtomicString, notStr, ("not(", AtomicString::ConstructFromLiteral));
304    DEFINE_STATIC_LOCAL(AtomicString, onlyChild, ("only-child", AtomicString::ConstructFromLiteral));
305    DEFINE_STATIC_LOCAL(AtomicString, onlyOfType, ("only-of-type", AtomicString::ConstructFromLiteral));
306    DEFINE_STATIC_LOCAL(AtomicString, optional, ("optional", AtomicString::ConstructFromLiteral));
307    DEFINE_STATIC_LOCAL(AtomicString, required, ("required", AtomicString::ConstructFromLiteral));
308    DEFINE_STATIC_LOCAL(AtomicString, resizer, ("-webkit-resizer", AtomicString::ConstructFromLiteral));
309    DEFINE_STATIC_LOCAL(AtomicString, root, ("root", AtomicString::ConstructFromLiteral));
310    DEFINE_STATIC_LOCAL(AtomicString, scrollbar, ("-webkit-scrollbar", AtomicString::ConstructFromLiteral));
311    DEFINE_STATIC_LOCAL(AtomicString, scrollbarButton, ("-webkit-scrollbar-button", AtomicString::ConstructFromLiteral));
312    DEFINE_STATIC_LOCAL(AtomicString, scrollbarCorner, ("-webkit-scrollbar-corner", AtomicString::ConstructFromLiteral));
313    DEFINE_STATIC_LOCAL(AtomicString, scrollbarThumb, ("-webkit-scrollbar-thumb", AtomicString::ConstructFromLiteral));
314    DEFINE_STATIC_LOCAL(AtomicString, scrollbarTrack, ("-webkit-scrollbar-track", AtomicString::ConstructFromLiteral));
315    DEFINE_STATIC_LOCAL(AtomicString, scrollbarTrackPiece, ("-webkit-scrollbar-track-piece", AtomicString::ConstructFromLiteral));
316    DEFINE_STATIC_LOCAL(AtomicString, selection, ("selection", AtomicString::ConstructFromLiteral));
317    DEFINE_STATIC_LOCAL(AtomicString, target, ("target", AtomicString::ConstructFromLiteral));
318    DEFINE_STATIC_LOCAL(AtomicString, visited, ("visited", AtomicString::ConstructFromLiteral));
319    DEFINE_STATIC_LOCAL(AtomicString, windowInactive, ("window-inactive", AtomicString::ConstructFromLiteral));
320    DEFINE_STATIC_LOCAL(AtomicString, decrement, ("decrement", AtomicString::ConstructFromLiteral));
321    DEFINE_STATIC_LOCAL(AtomicString, increment, ("increment", AtomicString::ConstructFromLiteral));
322    DEFINE_STATIC_LOCAL(AtomicString, start, ("start", AtomicString::ConstructFromLiteral));
323    DEFINE_STATIC_LOCAL(AtomicString, end, ("end", AtomicString::ConstructFromLiteral));
324    DEFINE_STATIC_LOCAL(AtomicString, horizontal, ("horizontal", AtomicString::ConstructFromLiteral));
325    DEFINE_STATIC_LOCAL(AtomicString, vertical, ("vertical", AtomicString::ConstructFromLiteral));
326    DEFINE_STATIC_LOCAL(AtomicString, doubleButton, ("double-button", AtomicString::ConstructFromLiteral));
327    DEFINE_STATIC_LOCAL(AtomicString, singleButton, ("single-button", AtomicString::ConstructFromLiteral));
328    DEFINE_STATIC_LOCAL(AtomicString, noButton, ("no-button", AtomicString::ConstructFromLiteral));
329    DEFINE_STATIC_LOCAL(AtomicString, cornerPresent, ("corner-present", AtomicString::ConstructFromLiteral));
330    // Paged Media pseudo-classes
331    DEFINE_STATIC_LOCAL(AtomicString, firstPage, ("first", AtomicString::ConstructFromLiteral));
332    DEFINE_STATIC_LOCAL(AtomicString, leftPage, ("left", AtomicString::ConstructFromLiteral));
333    DEFINE_STATIC_LOCAL(AtomicString, rightPage, ("right", AtomicString::ConstructFromLiteral));
334    DEFINE_STATIC_LOCAL(AtomicString, fullScreen, ("-webkit-full-screen", AtomicString::ConstructFromLiteral));
335    DEFINE_STATIC_LOCAL(AtomicString, fullScreenDocument, ("-webkit-full-screen-document", AtomicString::ConstructFromLiteral));
336    DEFINE_STATIC_LOCAL(AtomicString, fullScreenAncestor, ("-webkit-full-screen-ancestor", AtomicString::ConstructFromLiteral));
337    DEFINE_STATIC_LOCAL(AtomicString, cue, ("cue(", AtomicString::ConstructFromLiteral));
338    DEFINE_STATIC_LOCAL(AtomicString, cueWithoutParen, ("cue", AtomicString::ConstructFromLiteral));
339    DEFINE_STATIC_LOCAL(AtomicString, futureCue, ("future", AtomicString::ConstructFromLiteral));
340    DEFINE_STATIC_LOCAL(AtomicString, pastCue, ("past", AtomicString::ConstructFromLiteral));
341    DEFINE_STATIC_LOCAL(AtomicString, seamlessDocument, ("-webkit-seamless-document", AtomicString::ConstructFromLiteral));
342    DEFINE_STATIC_LOCAL(AtomicString, distributed, ("-webkit-distributed(", AtomicString::ConstructFromLiteral));
343    DEFINE_STATIC_LOCAL(AtomicString, inRange, ("in-range", AtomicString::ConstructFromLiteral));
344    DEFINE_STATIC_LOCAL(AtomicString, outOfRange, ("out-of-range", AtomicString::ConstructFromLiteral));
345    DEFINE_STATIC_LOCAL(AtomicString, scope, ("scope", AtomicString::ConstructFromLiteral));
346    DEFINE_STATIC_LOCAL(AtomicString, unresolved, ("unresolved", AtomicString::ConstructFromLiteral));
347    DEFINE_STATIC_LOCAL(AtomicString, content, ("content", AtomicString::ConstructFromLiteral));
348    DEFINE_STATIC_LOCAL(AtomicString, host, ("host", AtomicString::ConstructFromLiteral));
349    DEFINE_STATIC_LOCAL(AtomicString, hostWithParams, ("host(", AtomicString::ConstructFromLiteral));
350
351    static HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoType = 0;
352    if (!nameToPseudoType) {
353        nameToPseudoType = new HashMap<StringImpl*, CSSSelector::PseudoType>;
354        nameToPseudoType->set(active.impl(), CSSSelector::PseudoActive);
355        nameToPseudoType->set(after.impl(), CSSSelector::PseudoAfter);
356        nameToPseudoType->set(anyLink.impl(), CSSSelector::PseudoAnyLink);
357        nameToPseudoType->set(any.impl(), CSSSelector::PseudoAny);
358        nameToPseudoType->set(autofill.impl(), CSSSelector::PseudoAutofill);
359        nameToPseudoType->set(backdrop.impl(), CSSSelector::PseudoBackdrop);
360        nameToPseudoType->set(before.impl(), CSSSelector::PseudoBefore);
361        nameToPseudoType->set(checked.impl(), CSSSelector::PseudoChecked);
362        nameToPseudoType->set(defaultString.impl(), CSSSelector::PseudoDefault);
363        nameToPseudoType->set(disabled.impl(), CSSSelector::PseudoDisabled);
364        nameToPseudoType->set(readOnly.impl(), CSSSelector::PseudoReadOnly);
365        nameToPseudoType->set(readWrite.impl(), CSSSelector::PseudoReadWrite);
366        nameToPseudoType->set(valid.impl(), CSSSelector::PseudoValid);
367        nameToPseudoType->set(invalid.impl(), CSSSelector::PseudoInvalid);
368        nameToPseudoType->set(drag.impl(), CSSSelector::PseudoDrag);
369        nameToPseudoType->set(enabled.impl(), CSSSelector::PseudoEnabled);
370        nameToPseudoType->set(empty.impl(), CSSSelector::PseudoEmpty);
371        nameToPseudoType->set(firstChild.impl(), CSSSelector::PseudoFirstChild);
372        nameToPseudoType->set(fullPageMedia.impl(), CSSSelector::PseudoFullPageMedia);
373        nameToPseudoType->set(lastChild.impl(), CSSSelector::PseudoLastChild);
374        nameToPseudoType->set(lastOfType.impl(), CSSSelector::PseudoLastOfType);
375        nameToPseudoType->set(onlyChild.impl(), CSSSelector::PseudoOnlyChild);
376        nameToPseudoType->set(onlyOfType.impl(), CSSSelector::PseudoOnlyOfType);
377        nameToPseudoType->set(firstLetter.impl(), CSSSelector::PseudoFirstLetter);
378        nameToPseudoType->set(firstLine.impl(), CSSSelector::PseudoFirstLine);
379        nameToPseudoType->set(firstOfType.impl(), CSSSelector::PseudoFirstOfType);
380        nameToPseudoType->set(focus.impl(), CSSSelector::PseudoFocus);
381        nameToPseudoType->set(hover.impl(), CSSSelector::PseudoHover);
382        nameToPseudoType->set(indeterminate.impl(), CSSSelector::PseudoIndeterminate);
383        nameToPseudoType->set(link.impl(), CSSSelector::PseudoLink);
384        nameToPseudoType->set(lang.impl(), CSSSelector::PseudoLang);
385        nameToPseudoType->set(notStr.impl(), CSSSelector::PseudoNot);
386        nameToPseudoType->set(nthChild.impl(), CSSSelector::PseudoNthChild);
387        nameToPseudoType->set(nthOfType.impl(), CSSSelector::PseudoNthOfType);
388        nameToPseudoType->set(nthLastChild.impl(), CSSSelector::PseudoNthLastChild);
389        nameToPseudoType->set(nthLastOfType.impl(), CSSSelector::PseudoNthLastOfType);
390        nameToPseudoType->set(root.impl(), CSSSelector::PseudoRoot);
391        nameToPseudoType->set(windowInactive.impl(), CSSSelector::PseudoWindowInactive);
392        nameToPseudoType->set(decrement.impl(), CSSSelector::PseudoDecrement);
393        nameToPseudoType->set(increment.impl(), CSSSelector::PseudoIncrement);
394        nameToPseudoType->set(start.impl(), CSSSelector::PseudoStart);
395        nameToPseudoType->set(end.impl(), CSSSelector::PseudoEnd);
396        nameToPseudoType->set(horizontal.impl(), CSSSelector::PseudoHorizontal);
397        nameToPseudoType->set(vertical.impl(), CSSSelector::PseudoVertical);
398        nameToPseudoType->set(doubleButton.impl(), CSSSelector::PseudoDoubleButton);
399        nameToPseudoType->set(singleButton.impl(), CSSSelector::PseudoSingleButton);
400        nameToPseudoType->set(noButton.impl(), CSSSelector::PseudoNoButton);
401        nameToPseudoType->set(optional.impl(), CSSSelector::PseudoOptional);
402        nameToPseudoType->set(required.impl(), CSSSelector::PseudoRequired);
403        nameToPseudoType->set(resizer.impl(), CSSSelector::PseudoResizer);
404        nameToPseudoType->set(scope.impl(), CSSSelector::PseudoScope);
405        nameToPseudoType->set(scrollbar.impl(), CSSSelector::PseudoScrollbar);
406        nameToPseudoType->set(scrollbarButton.impl(), CSSSelector::PseudoScrollbarButton);
407        nameToPseudoType->set(scrollbarCorner.impl(), CSSSelector::PseudoScrollbarCorner);
408        nameToPseudoType->set(scrollbarThumb.impl(), CSSSelector::PseudoScrollbarThumb);
409        nameToPseudoType->set(scrollbarTrack.impl(), CSSSelector::PseudoScrollbarTrack);
410        nameToPseudoType->set(scrollbarTrackPiece.impl(), CSSSelector::PseudoScrollbarTrackPiece);
411        nameToPseudoType->set(cornerPresent.impl(), CSSSelector::PseudoCornerPresent);
412        nameToPseudoType->set(selection.impl(), CSSSelector::PseudoSelection);
413        nameToPseudoType->set(target.impl(), CSSSelector::PseudoTarget);
414        nameToPseudoType->set(visited.impl(), CSSSelector::PseudoVisited);
415        nameToPseudoType->set(firstPage.impl(), CSSSelector::PseudoFirstPage);
416        nameToPseudoType->set(leftPage.impl(), CSSSelector::PseudoLeftPage);
417        nameToPseudoType->set(rightPage.impl(), CSSSelector::PseudoRightPage);
418        nameToPseudoType->set(fullScreen.impl(), CSSSelector::PseudoFullScreen);
419        nameToPseudoType->set(fullScreenDocument.impl(), CSSSelector::PseudoFullScreenDocument);
420        nameToPseudoType->set(fullScreenAncestor.impl(), CSSSelector::PseudoFullScreenAncestor);
421        nameToPseudoType->set(cue.impl(), CSSSelector::PseudoCue);
422        nameToPseudoType->set(cueWithoutParen.impl(), CSSSelector::PseudoWebKitCustomElement);
423        nameToPseudoType->set(futureCue.impl(), CSSSelector::PseudoFutureCue);
424        nameToPseudoType->set(pastCue.impl(), CSSSelector::PseudoPastCue);
425        nameToPseudoType->set(seamlessDocument.impl(), CSSSelector::PseudoSeamlessDocument);
426        nameToPseudoType->set(distributed.impl(), CSSSelector::PseudoDistributed);
427        nameToPseudoType->set(inRange.impl(), CSSSelector::PseudoInRange);
428        nameToPseudoType->set(outOfRange.impl(), CSSSelector::PseudoOutOfRange);
429        if (RuntimeEnabledFeatures::shadowDOMEnabled()) {
430            nameToPseudoType->set(host.impl(), CSSSelector::PseudoHost);
431            nameToPseudoType->set(hostWithParams.impl(), CSSSelector::PseudoHost);
432            nameToPseudoType->set(content.impl(), CSSSelector::PseudoContent);
433        }
434        if (RuntimeEnabledFeatures::customElementsEnabled())
435            nameToPseudoType->set(unresolved.impl(), CSSSelector::PseudoUnresolved);
436    }
437    return nameToPseudoType;
438}
439
440CSSSelector::PseudoType CSSSelector::parsePseudoType(const AtomicString& name)
441{
442    if (name.isNull())
443        return PseudoUnknown;
444    HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoType = nameToPseudoTypeMap();
445    HashMap<StringImpl*, CSSSelector::PseudoType>::iterator slot = nameToPseudoType->find(name.impl());
446
447    if (slot != nameToPseudoType->end())
448        return slot->value;
449
450    if (name.startsWith("-webkit-"))
451        return PseudoWebKitCustomElement;
452    if (name.startsWith("x-") || name.startsWith("cue"))
453        return PseudoUserAgentCustomElement;
454
455    return PseudoUnknown;
456}
457
458void CSSSelector::extractPseudoType() const
459{
460    if (m_match != PseudoClass && m_match != PseudoElement && m_match != PagePseudoClass)
461        return;
462
463    m_pseudoType = parsePseudoType(value());
464
465    bool element = false; // pseudo-element
466    bool compat = false; // single colon compatbility mode
467    bool isPagePseudoClass = false; // Page pseudo-class
468
469    switch (m_pseudoType) {
470    case PseudoAfter:
471    case PseudoBefore:
472    case PseudoCue:
473    case PseudoFirstLetter:
474    case PseudoFirstLine:
475        compat = true;
476    case PseudoBackdrop:
477    case PseudoDistributed:
478    case PseudoResizer:
479    case PseudoScrollbar:
480    case PseudoScrollbarCorner:
481    case PseudoScrollbarButton:
482    case PseudoScrollbarThumb:
483    case PseudoScrollbarTrack:
484    case PseudoScrollbarTrackPiece:
485    case PseudoSelection:
486    case PseudoUserAgentCustomElement:
487    case PseudoWebKitCustomElement:
488    case PseudoContent:
489        element = true;
490        break;
491    case PseudoUnknown:
492    case PseudoEmpty:
493    case PseudoFirstChild:
494    case PseudoFirstOfType:
495    case PseudoLastChild:
496    case PseudoLastOfType:
497    case PseudoOnlyChild:
498    case PseudoOnlyOfType:
499    case PseudoNthChild:
500    case PseudoNthOfType:
501    case PseudoNthLastChild:
502    case PseudoNthLastOfType:
503    case PseudoLink:
504    case PseudoVisited:
505    case PseudoAny:
506    case PseudoAnyLink:
507    case PseudoAutofill:
508    case PseudoHover:
509    case PseudoDrag:
510    case PseudoFocus:
511    case PseudoActive:
512    case PseudoChecked:
513    case PseudoEnabled:
514    case PseudoFullPageMedia:
515    case PseudoDefault:
516    case PseudoDisabled:
517    case PseudoOptional:
518    case PseudoRequired:
519    case PseudoReadOnly:
520    case PseudoReadWrite:
521    case PseudoScope:
522    case PseudoValid:
523    case PseudoInvalid:
524    case PseudoIndeterminate:
525    case PseudoTarget:
526    case PseudoLang:
527    case PseudoNot:
528    case PseudoRoot:
529    case PseudoScrollbarBack:
530    case PseudoScrollbarForward:
531    case PseudoWindowInactive:
532    case PseudoCornerPresent:
533    case PseudoDecrement:
534    case PseudoIncrement:
535    case PseudoHorizontal:
536    case PseudoVertical:
537    case PseudoStart:
538    case PseudoEnd:
539    case PseudoDoubleButton:
540    case PseudoSingleButton:
541    case PseudoNoButton:
542    case PseudoNotParsed:
543    case PseudoFullScreen:
544    case PseudoFullScreenDocument:
545    case PseudoFullScreenAncestor:
546    case PseudoSeamlessDocument:
547    case PseudoInRange:
548    case PseudoOutOfRange:
549    case PseudoFutureCue:
550    case PseudoPastCue:
551    case PseudoHost:
552    case PseudoUnresolved:
553        break;
554    case PseudoFirstPage:
555    case PseudoLeftPage:
556    case PseudoRightPage:
557        isPagePseudoClass = true;
558        break;
559    }
560
561    bool matchPagePseudoClass = (m_match == PagePseudoClass);
562    if (matchPagePseudoClass != isPagePseudoClass)
563        m_pseudoType = PseudoUnknown;
564    else if (m_match == PseudoClass && element) {
565        if (!compat)
566            m_pseudoType = PseudoUnknown;
567        else
568            m_match = PseudoElement;
569    } else if (m_match == PseudoElement && !element)
570        m_pseudoType = PseudoUnknown;
571}
572
573bool CSSSelector::operator==(const CSSSelector& other) const
574{
575    const CSSSelector* sel1 = this;
576    const CSSSelector* sel2 = &other;
577
578    while (sel1 && sel2) {
579        if (sel1->attribute() != sel2->attribute()
580            || sel1->relation() != sel2->relation()
581            || sel1->m_match != sel2->m_match
582            || sel1->value() != sel2->value()
583            || sel1->pseudoType() != sel2->pseudoType()
584            || sel1->argument() != sel2->argument()) {
585            return false;
586        }
587        if (sel1->m_match == Tag) {
588            if (sel1->tagQName() != sel2->tagQName())
589                return false;
590        }
591        sel1 = sel1->tagHistory();
592        sel2 = sel2->tagHistory();
593    }
594
595    if (sel1 || sel2)
596        return false;
597
598    return true;
599}
600
601String CSSSelector::selectorText(const String& rightSide) const
602{
603    StringBuilder str;
604
605    if (m_match == CSSSelector::Tag && !m_tagIsForNamespaceRule) {
606        if (tagQName().prefix().isNull())
607            str.append(tagQName().localName());
608        else {
609            str.append(tagQName().prefix().string());
610            str.append('|');
611            str.append(tagQName().localName());
612        }
613    }
614
615    const CSSSelector* cs = this;
616    while (true) {
617        if (cs->m_match == CSSSelector::Id) {
618            str.append('#');
619            serializeIdentifier(cs->value(), str);
620        } else if (cs->m_match == CSSSelector::Class) {
621            str.append('.');
622            serializeIdentifier(cs->value(), str);
623        } else if (cs->m_match == CSSSelector::PseudoClass || cs->m_match == CSSSelector::PagePseudoClass) {
624            str.append(':');
625            str.append(cs->value());
626
627            switch (cs->pseudoType()) {
628            case PseudoNot:
629                ASSERT(cs->selectorList());
630                str.append(cs->selectorList()->first()->selectorText());
631                str.append(')');
632                break;
633            case PseudoLang:
634            case PseudoNthChild:
635            case PseudoNthLastChild:
636            case PseudoNthOfType:
637            case PseudoNthLastOfType:
638                str.append(cs->argument());
639                str.append(')');
640                break;
641            case PseudoAny: {
642                const CSSSelector* firstSubSelector = cs->selectorList()->first();
643                for (const CSSSelector* subSelector = firstSubSelector; subSelector; subSelector = CSSSelectorList::next(subSelector)) {
644                    if (subSelector != firstSubSelector)
645                        str.append(',');
646                    str.append(subSelector->selectorText());
647                }
648                str.append(')');
649                break;
650            }
651            case PseudoHost: {
652                if (cs->selectorList()) {
653                    const CSSSelector* firstSubSelector = cs->selectorList()->first();
654                    for (const CSSSelector* subSelector = firstSubSelector; subSelector; subSelector = CSSSelectorList::next(subSelector)) {
655                        if (subSelector != firstSubSelector)
656                            str.append(',');
657                        str.append(subSelector->selectorText());
658                    }
659                    str.append(')');
660                }
661                break;
662            }
663            default:
664                break;
665            }
666        } else if (cs->m_match == CSSSelector::PseudoElement) {
667            str.appendLiteral("::");
668            str.append(cs->value());
669
670            if (cs->pseudoType() == PseudoContent) {
671                if (cs->relation() == CSSSelector::SubSelector && cs->tagHistory())
672                    return cs->tagHistory()->selectorText() + str.toString() + rightSide;
673            }
674        } else if (cs->isAttributeSelector()) {
675            str.append('[');
676            const AtomicString& prefix = cs->attribute().prefix();
677            if (!prefix.isNull()) {
678                str.append(prefix);
679                str.append("|");
680            }
681            str.append(cs->attribute().localName());
682            switch (cs->m_match) {
683                case CSSSelector::Exact:
684                    str.append('=');
685                    break;
686                case CSSSelector::Set:
687                    // set has no operator or value, just the attrName
688                    str.append(']');
689                    break;
690                case CSSSelector::List:
691                    str.appendLiteral("~=");
692                    break;
693                case CSSSelector::Hyphen:
694                    str.appendLiteral("|=");
695                    break;
696                case CSSSelector::Begin:
697                    str.appendLiteral("^=");
698                    break;
699                case CSSSelector::End:
700                    str.appendLiteral("$=");
701                    break;
702                case CSSSelector::Contain:
703                    str.appendLiteral("*=");
704                    break;
705                default:
706                    break;
707            }
708            if (cs->m_match != CSSSelector::Set) {
709                serializeString(cs->value(), str);
710                str.append(']');
711            }
712        }
713        if (cs->relation() != CSSSelector::SubSelector || !cs->tagHistory())
714            break;
715        cs = cs->tagHistory();
716    }
717
718    if (const CSSSelector* tagHistory = cs->tagHistory()) {
719        switch (cs->relation()) {
720        case CSSSelector::Descendant:
721            if (cs->relationIsAffectedByPseudoContent() && tagHistory->pseudoType() != CSSSelector::PseudoContent)
722                return tagHistory->selectorText("::-webkit-distributed(" + str.toString() + rightSide + ")");
723            return tagHistory->selectorText(" " + str.toString() + rightSide);
724        case CSSSelector::Child:
725            if (cs->relationIsAffectedByPseudoContent() && tagHistory->pseudoType() != CSSSelector::PseudoContent)
726                return tagHistory->selectorText("::-webkit-distributed(> " + str.toString() + rightSide + ")");
727            return tagHistory->selectorText(" > " + str.toString() + rightSide);
728        case CSSSelector::ChildTree:
729            return tagHistory->selectorText(" ^ " + str.toString() + rightSide);
730        case CSSSelector::DescendantTree:
731            return tagHistory->selectorText(" ^^ " + str.toString() + rightSide);
732        case CSSSelector::DirectAdjacent:
733            return tagHistory->selectorText(" + " + str.toString() + rightSide);
734        case CSSSelector::IndirectAdjacent:
735            return tagHistory->selectorText(" ~ " + str.toString() + rightSide);
736        case CSSSelector::SubSelector:
737            ASSERT_NOT_REACHED();
738        case CSSSelector::ShadowPseudo:
739            return tagHistory->selectorText(str.toString() + rightSide);
740        }
741    }
742    return str.toString() + rightSide;
743}
744
745void CSSSelector::setAttribute(const QualifiedName& value)
746{
747    createRareData();
748    m_data.m_rareData->m_attribute = value;
749}
750
751void CSSSelector::setArgument(const AtomicString& value)
752{
753    createRareData();
754    m_data.m_rareData->m_argument = value;
755}
756
757void CSSSelector::setSelectorList(PassOwnPtr<CSSSelectorList> selectorList)
758{
759    createRareData();
760    m_data.m_rareData->m_selectorList = selectorList;
761}
762
763static bool validateSubSelector(const CSSSelector* selector)
764{
765    switch (selector->m_match) {
766    case CSSSelector::Tag:
767    case CSSSelector::Id:
768    case CSSSelector::Class:
769    case CSSSelector::Exact:
770    case CSSSelector::Set:
771    case CSSSelector::List:
772    case CSSSelector::Hyphen:
773    case CSSSelector::Contain:
774    case CSSSelector::Begin:
775    case CSSSelector::End:
776        return true;
777    case CSSSelector::PseudoElement:
778        return false;
779    case CSSSelector::PagePseudoClass:
780    case CSSSelector::PseudoClass:
781        break;
782    }
783
784    switch (selector->pseudoType()) {
785    case CSSSelector::PseudoEmpty:
786    case CSSSelector::PseudoLink:
787    case CSSSelector::PseudoVisited:
788    case CSSSelector::PseudoTarget:
789    case CSSSelector::PseudoEnabled:
790    case CSSSelector::PseudoDisabled:
791    case CSSSelector::PseudoChecked:
792    case CSSSelector::PseudoIndeterminate:
793    case CSSSelector::PseudoNthChild:
794    case CSSSelector::PseudoNthLastChild:
795    case CSSSelector::PseudoNthOfType:
796    case CSSSelector::PseudoNthLastOfType:
797    case CSSSelector::PseudoFirstChild:
798    case CSSSelector::PseudoLastChild:
799    case CSSSelector::PseudoFirstOfType:
800    case CSSSelector::PseudoLastOfType:
801    case CSSSelector::PseudoOnlyOfType:
802    case CSSSelector::PseudoHost:
803        return true;
804    default:
805        return false;
806    }
807}
808
809bool CSSSelector::isCompound() const
810{
811    if (!validateSubSelector(this))
812        return false;
813
814    const CSSSelector* prevSubSelector = this;
815    const CSSSelector* subSelector = tagHistory();
816
817    while (subSelector) {
818        if (prevSubSelector->relation() != CSSSelector::SubSelector)
819            return false;
820        if (!validateSubSelector(subSelector))
821            return false;
822
823        prevSubSelector = subSelector;
824        subSelector = subSelector->tagHistory();
825    }
826
827    return true;
828}
829
830bool CSSSelector::parseNth() const
831{
832    if (!m_hasRareData)
833        return false;
834    if (m_parsedNth)
835        return true;
836    m_parsedNth = m_data.m_rareData->parseNth();
837    return m_parsedNth;
838}
839
840bool CSSSelector::matchNth(int count) const
841{
842    ASSERT(m_hasRareData);
843    return m_data.m_rareData->matchNth(count);
844}
845
846CSSSelector::RareData::RareData(PassRefPtr<StringImpl> value)
847    : m_value(value.leakRef())
848    , m_a(0)
849    , m_b(0)
850    , m_attribute(anyQName())
851    , m_argument(nullAtom)
852{
853}
854
855CSSSelector::RareData::~RareData()
856{
857    if (m_value)
858        m_value->deref();
859}
860
861// a helper function for parsing nth-arguments
862bool CSSSelector::RareData::parseNth()
863{
864    String argument = m_argument.lower();
865
866    if (argument.isEmpty())
867        return false;
868
869    m_a = 0;
870    m_b = 0;
871    if (argument == "odd") {
872        m_a = 2;
873        m_b = 1;
874    } else if (argument == "even") {
875        m_a = 2;
876        m_b = 0;
877    } else {
878        size_t n = argument.find('n');
879        if (n != kNotFound) {
880            if (argument[0] == '-') {
881                if (n == 1)
882                    m_a = -1; // -n == -1n
883                else
884                    m_a = argument.substring(0, n).toInt();
885            } else if (!n)
886                m_a = 1; // n == 1n
887            else
888                m_a = argument.substring(0, n).toInt();
889
890            size_t p = argument.find('+', n);
891            if (p != kNotFound)
892                m_b = argument.substring(p + 1, argument.length() - p - 1).toInt();
893            else {
894                p = argument.find('-', n);
895                if (p != kNotFound)
896                    m_b = -argument.substring(p + 1, argument.length() - p - 1).toInt();
897            }
898        } else
899            m_b = argument.toInt();
900    }
901    return true;
902}
903
904// a helper function for checking nth-arguments
905bool CSSSelector::RareData::matchNth(int count)
906{
907    if (!m_a)
908        return count == m_b;
909    else if (m_a > 0) {
910        if (count < m_b)
911            return false;
912        return (count - m_b) % m_a == 0;
913    } else {
914        if (count > m_b)
915            return false;
916        return (m_b - count) % (-m_a) == 0;
917    }
918}
919
920} // namespace WebCore
921