src/third_party/WebKit/Source/core/css/CSSSelector.cpp

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