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