Add WTF::move()
[WebKit-https.git] / Source / WebCore / 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, 2013 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 "CSSSelector.h"
28
29 #include "CSSOMUtils.h"
30 #include "CSSSelectorList.h"
31 #include "HTMLNames.h"
32 #include "SelectorPseudoTypeMap.h"
33 #include <wtf/Assertions.h>
34 #include <wtf/HashMap.h>
35 #include <wtf/NeverDestroyed.h>
36 #include <wtf/StdLibExtras.h>
37 #include <wtf/Vector.h>
38 #include <wtf/text/AtomicStringHash.h>
39 #include <wtf/text/StringBuilder.h>
40
41 namespace WebCore {
42
43 using namespace HTMLNames;
44
45 void CSSSelector::createRareData()
46 {
47     ASSERT(m_match != Tag);
48     if (m_hasRareData)
49         return;
50     // Move the value to the rare data stucture.
51     m_data.m_rareData = RareData::create(adoptRef(m_data.m_value)).leakRef();
52     m_hasRareData = true;
53 }
54
55 unsigned CSSSelector::specificity() const
56 {
57     // make sure the result doesn't overflow
58     static const unsigned maxValueMask = 0xffffff;
59     static const unsigned idMask = 0xff0000;
60     static const unsigned classMask = 0xff00;
61     static const unsigned elementMask = 0xff;
62
63     if (isForPage())
64         return specificityForPage() & maxValueMask;
65
66     unsigned total = 0;
67     unsigned temp = 0;
68
69     for (const CSSSelector* selector = this; selector; selector = selector->tagHistory()) {
70         temp = total + selector->specificityForOneSelector();
71         // Clamp each component to its max in the case of overflow.
72         if ((temp & idMask) < (total & idMask))
73             total |= idMask;
74         else if ((temp & classMask) < (total & classMask))
75             total |= classMask;
76         else if ((temp & elementMask) < (total & elementMask))
77             total |= elementMask;
78         else
79             total = temp;
80     }
81     return total;
82 }
83
84 inline unsigned CSSSelector::specificityForOneSelector() const
85 {
86     // FIXME: Pseudo-elements and pseudo-classes do not have the same specificity. This function
87     // isn't quite correct.
88     switch (m_match) {
89     case Id:
90         return 0x10000;
91
92     case PseudoClass:
93         // FIXME: PsuedoAny should base the specificity on the sub-selectors.
94         // See http://lists.w3.org/Archives/Public/www-style/2010Sep/0530.html
95         if (pseudoClassType() == PseudoClassNot && selectorList())
96             return selectorList()->first()->specificityForOneSelector();
97         FALLTHROUGH;
98     case Exact:
99     case Class:
100     case Set:
101     case List:
102     case Hyphen:
103     case PseudoElement:
104     case Contain:
105     case Begin:
106     case End:
107         return 0x100;
108
109     case Tag:
110         return (tagQName().localName() != starAtom) ? 1 : 0;
111     case Unknown:
112         return 0;
113     }
114     ASSERT_NOT_REACHED();
115     return 0;
116 }
117
118 unsigned CSSSelector::specificityForPage() const
119 {
120     // See http://dev.w3.org/csswg/css3-page/#cascading-and-page-context
121     unsigned s = 0;
122
123     for (const CSSSelector* component = this; component; component = component->tagHistory()) {
124         switch (component->m_match) {
125         case Tag:
126             s += tagQName().localName() == starAtom ? 0 : 4;
127             break;
128         case PagePseudoClass:
129             switch (component->pagePseudoClassType()) {
130             case PagePseudoClassFirst:
131                 s += 2;
132                 break;
133             case PagePseudoClassLeft:
134             case PagePseudoClassRight:
135                 s += 1;
136                 break;
137             }
138             break;
139         default:
140             break;
141         }
142     }
143     return s;
144 }
145
146 PseudoId CSSSelector::pseudoId(PseudoElementType type)
147 {
148     switch (type) {
149     case PseudoElementFirstLine:
150         return FIRST_LINE;
151     case PseudoElementFirstLetter:
152         return FIRST_LETTER;
153     case PseudoElementSelection:
154         return SELECTION;
155     case PseudoElementBefore:
156         return BEFORE;
157     case PseudoElementAfter:
158         return AFTER;
159     case PseudoElementScrollbar:
160         return SCROLLBAR;
161     case PseudoElementScrollbarButton:
162         return SCROLLBAR_BUTTON;
163     case PseudoElementScrollbarCorner:
164         return SCROLLBAR_CORNER;
165     case PseudoElementScrollbarThumb:
166         return SCROLLBAR_THUMB;
167     case PseudoElementScrollbarTrack:
168         return SCROLLBAR_TRACK;
169     case PseudoElementScrollbarTrackPiece:
170         return SCROLLBAR_TRACK_PIECE;
171     case PseudoElementResizer:
172         return RESIZER;
173 #if ENABLE(VIDEO_TRACK)
174     case PseudoElementCue:
175 #endif
176     case PseudoElementUnknown:
177     case PseudoElementUserAgentCustom:
178     case PseudoElementWebKitCustom:
179         return NOPSEUDO;
180     }
181
182     ASSERT_NOT_REACHED();
183     return NOPSEUDO;
184 }
185
186 CSSSelector::PseudoElementType CSSSelector::parsePseudoElementType(const String& name)
187 {
188     if (name.isNull())
189         return PseudoElementUnknown;
190
191     PseudoElementType type = parsePseudoElementString(*name.impl());
192     if (type == PseudoElementUnknown) {
193         if (name.startsWith("-webkit-"))
194             type = PseudoElementWebKitCustom;
195
196         if (name.startsWith("x-"))
197             type = PseudoElementUserAgentCustom;
198     }
199     return type;
200 }
201
202
203 bool CSSSelector::operator==(const CSSSelector& other) const
204 {
205     const CSSSelector* sel1 = this;
206     const CSSSelector* sel2 = &other;
207
208     while (sel1 && sel2) {
209         if (sel1->attribute() != sel2->attribute()
210             || sel1->relation() != sel2->relation()
211             || sel1->m_match != sel2->m_match
212             || sel1->value() != sel2->value()
213             || sel1->m_pseudoType != sel2->m_pseudoType
214             || sel1->argument() != sel2->argument()) {
215             return false;
216         }
217         if (sel1->m_match == Tag) {
218             if (sel1->tagQName() != sel2->tagQName())
219                 return false;
220         }
221         sel1 = sel1->tagHistory();
222         sel2 = sel2->tagHistory();
223     }
224
225     if (sel1 || sel2)
226         return false;
227
228     return true;
229 }
230
231 static void appendPseudoClassFunctionTail(StringBuilder& str, const CSSSelector* selector)
232 {
233     switch (selector->pseudoClassType()) {
234     case CSSSelector::PseudoClassLang:
235     case CSSSelector::PseudoClassNthChild:
236     case CSSSelector::PseudoClassNthLastChild:
237     case CSSSelector::PseudoClassNthOfType:
238     case CSSSelector::PseudoClassNthLastOfType:
239         str.append(selector->argument());
240         str.append(')');
241         break;
242     default:
243         break;
244     }
245
246 }
247
248 String CSSSelector::selectorText(const String& rightSide) const
249 {
250     StringBuilder str;
251
252     if (m_match == CSSSelector::Tag && !m_tagIsForNamespaceRule) {
253         if (tagQName().prefix().isNull())
254             str.append(tagQName().localName());
255         else {
256             str.append(tagQName().prefix().string());
257             str.append('|');
258             str.append(tagQName().localName());
259         }
260     }
261
262     const CSSSelector* cs = this;
263     while (true) {
264         if (cs->m_match == CSSSelector::Id) {
265             str.append('#');
266             serializeIdentifier(cs->value(), str);
267         } else if (cs->m_match == CSSSelector::Class) {
268             str.append('.');
269             serializeIdentifier(cs->value(), str);
270         } else if (cs->m_match == CSSSelector::PseudoClass) {
271             switch (cs->pseudoClassType()) {
272 #if ENABLE(FULLSCREEN_API)
273             case CSSSelector::PseudoClassAnimatingFullScreenTransition:
274                 str.appendLiteral(":-webkit-animating-full-screen-transition");
275                 break;
276 #endif
277             case CSSSelector::PseudoClassAny: {
278                 str.appendLiteral(":-webkit-any(");
279                 const CSSSelector* firstSubSelector = cs->selectorList()->first();
280                 for (const CSSSelector* subSelector = firstSubSelector; subSelector; subSelector = CSSSelectorList::next(subSelector)) {
281                     if (subSelector != firstSubSelector)
282                         str.append(',');
283                     str.append(subSelector->selectorText());
284                 }
285                 str.append(')');
286                 break;
287             }
288             case CSSSelector::PseudoClassAnyLink:
289                 str.appendLiteral(":-webkit-any-link");
290                 break;
291             case CSSSelector::PseudoClassAutofill:
292                 str.appendLiteral(":-webkit-autofill");
293                 break;
294             case CSSSelector::PseudoClassDrag:
295                 str.appendLiteral(":-webkit-drag");
296                 break;
297             case CSSSelector::PseudoClassFullPageMedia:
298                 str.appendLiteral(":-webkit-full-page-media");
299                 break;
300 #if ENABLE(FULLSCREEN_API)
301             case CSSSelector::PseudoClassFullScreen:
302                 str.appendLiteral(":-webkit-full-screen");
303                 break;
304             case CSSSelector::PseudoClassFullScreenAncestor:
305                 str.appendLiteral(":-webkit-full-screen-ancestor");
306                 break;
307             case CSSSelector::PseudoClassFullScreenDocument:
308                 str.appendLiteral(":-webkit-full-screen-document");
309                 break;
310 #endif
311             case CSSSelector::PseudoClassActive:
312                 str.appendLiteral(":active");
313                 break;
314             case CSSSelector::PseudoClassChecked:
315                 str.appendLiteral(":checked");
316                 break;
317             case CSSSelector::PseudoClassCornerPresent:
318                 str.appendLiteral(":corner-present");
319                 break;
320             case CSSSelector::PseudoClassDecrement:
321                 str.appendLiteral(":decrement");
322                 break;
323             case CSSSelector::PseudoClassDefault:
324                 str.appendLiteral(":default");
325                 break;
326             case CSSSelector::PseudoClassDisabled:
327                 str.appendLiteral(":disabled");
328                 break;
329             case CSSSelector::PseudoClassDoubleButton:
330                 str.appendLiteral(":double-button");
331                 break;
332             case CSSSelector::PseudoClassEmpty:
333                 str.appendLiteral(":empty");
334                 break;
335             case CSSSelector::PseudoClassEnabled:
336                 str.appendLiteral(":enabled");
337                 break;
338             case CSSSelector::PseudoClassEnd:
339                 str.appendLiteral(":end");
340                 break;
341             case CSSSelector::PseudoClassFirstChild:
342                 str.appendLiteral(":first-child");
343                 break;
344             case CSSSelector::PseudoClassFirstOfType:
345                 str.appendLiteral(":first-of-type");
346                 break;
347             case CSSSelector::PseudoClassFocus:
348                 str.appendLiteral(":focus");
349                 break;
350 #if ENABLE(VIDEO_TRACK)
351             case CSSSelector::PseudoClassFuture:
352                 str.appendLiteral(":future");
353                 break;
354 #endif
355             case CSSSelector::PseudoClassHorizontal:
356                 str.appendLiteral(":horizontal");
357                 break;
358             case CSSSelector::PseudoClassHover:
359                 str.appendLiteral(":hover");
360                 break;
361             case CSSSelector::PseudoClassInRange:
362                 str.appendLiteral(":in-range");
363                 break;
364             case CSSSelector::PseudoClassIncrement:
365                 str.appendLiteral(":increment");
366                 break;
367             case CSSSelector::PseudoClassIndeterminate:
368                 str.appendLiteral(":indeterminate");
369                 break;
370             case CSSSelector::PseudoClassInvalid:
371                 str.appendLiteral(":invalid");
372                 break;
373             case CSSSelector::PseudoClassLang:
374                 str.appendLiteral(":lang(");
375                 appendPseudoClassFunctionTail(str, cs);
376                 break;
377             case CSSSelector::PseudoClassLastChild:
378                 str.appendLiteral(":last-child");
379                 break;
380             case CSSSelector::PseudoClassLastOfType:
381                 str.appendLiteral(":last-of-type");
382                 break;
383             case CSSSelector::PseudoClassLink:
384                 str.appendLiteral(":link");
385                 break;
386             case CSSSelector::PseudoClassNoButton:
387                 str.appendLiteral(":no-button");
388                 break;
389             case CSSSelector::PseudoClassNot:
390                 str.appendLiteral(":not(");
391                 if (const CSSSelectorList* selectorList = cs->selectorList())
392                     str.append(selectorList->first()->selectorText());
393                 str.append(')');
394                 break;
395             case CSSSelector::PseudoClassNthChild:
396                 str.appendLiteral(":nth-child(");
397                 appendPseudoClassFunctionTail(str, cs);
398                 break;
399             case CSSSelector::PseudoClassNthLastChild:
400                 str.appendLiteral(":nth-last-child(");
401                 appendPseudoClassFunctionTail(str, cs);
402                 break;
403             case CSSSelector::PseudoClassNthLastOfType:
404                 str.appendLiteral(":nth-last-of-type(");
405                 appendPseudoClassFunctionTail(str, cs);
406                 break;
407             case CSSSelector::PseudoClassNthOfType:
408                 str.appendLiteral(":nth-of-type(");
409                 appendPseudoClassFunctionTail(str, cs);
410                 break;
411             case CSSSelector::PseudoClassOnlyChild:
412                 str.appendLiteral(":only-child");
413                 break;
414             case CSSSelector::PseudoClassOnlyOfType:
415                 str.appendLiteral(":only-of-type");
416                 break;
417             case CSSSelector::PseudoClassOptional:
418                 str.appendLiteral(":optional");
419                 break;
420             case CSSSelector::PseudoClassOutOfRange:
421                 str.appendLiteral(":out-of-range");
422                 break;
423 #if ENABLE(VIDEO_TRACK)
424             case CSSSelector::PseudoClassPast:
425                 str.appendLiteral(":past");
426                 break;
427 #endif
428             case CSSSelector::PseudoClassReadOnly:
429                 str.appendLiteral(":read-only");
430                 break;
431             case CSSSelector::PseudoClassReadWrite:
432                 str.appendLiteral(":read-write");
433                 break;
434             case CSSSelector::PseudoClassRequired:
435                 str.appendLiteral(":required");
436                 break;
437             case CSSSelector::PseudoClassRoot:
438                 str.appendLiteral(":root");
439                 break;
440             case CSSSelector::PseudoClassScope:
441                 str.appendLiteral(":scope");
442                 break;
443             case CSSSelector::PseudoClassSingleButton:
444                 str.appendLiteral(":single-button");
445                 break;
446             case CSSSelector::PseudoClassStart:
447                 str.appendLiteral(":start");
448                 break;
449             case CSSSelector::PseudoClassTarget:
450                 str.appendLiteral(":target");
451                 break;
452             case CSSSelector::PseudoClassValid:
453                 str.appendLiteral(":valid");
454                 break;
455             case CSSSelector::PseudoClassVertical:
456                 str.appendLiteral(":vertical");
457                 break;
458             case CSSSelector::PseudoClassVisited:
459                 str.appendLiteral(":visited");
460                 break;
461             case CSSSelector::PseudoClassWindowInactive:
462                 str.appendLiteral(":window-inactive");
463                 break;
464             default:
465                 ASSERT_NOT_REACHED();
466             }
467         } else if (cs->m_match == CSSSelector::PseudoElement) {
468             str.appendLiteral("::");
469             str.append(cs->value());
470         } else if (cs->isAttributeSelector()) {
471             str.append('[');
472             const AtomicString& prefix = cs->attribute().prefix();
473             if (!prefix.isNull()) {
474                 str.append(prefix);
475                 str.append('|');
476             }
477             str.append(cs->attribute().localName());
478             switch (cs->m_match) {
479                 case CSSSelector::Exact:
480                     str.append('=');
481                     break;
482                 case CSSSelector::Set:
483                     // set has no operator or value, just the attrName
484                     str.append(']');
485                     break;
486                 case CSSSelector::List:
487                     str.appendLiteral("~=");
488                     break;
489                 case CSSSelector::Hyphen:
490                     str.appendLiteral("|=");
491                     break;
492                 case CSSSelector::Begin:
493                     str.appendLiteral("^=");
494                     break;
495                 case CSSSelector::End:
496                     str.appendLiteral("$=");
497                     break;
498                 case CSSSelector::Contain:
499                     str.appendLiteral("*=");
500                     break;
501                 default:
502                     break;
503             }
504             if (cs->m_match != CSSSelector::Set) {
505                 serializeString(cs->value(), str);
506                 str.append(']');
507             }
508         } else if (cs->m_match == CSSSelector::PagePseudoClass) {
509             switch (cs->pagePseudoClassType()) {
510             case PagePseudoClassFirst:
511                 str.appendLiteral(":first");
512                 break;
513             case PagePseudoClassLeft:
514                 str.appendLiteral(":left");
515                 break;
516             case PagePseudoClassRight:
517                 str.appendLiteral(":right");
518                 break;
519             }
520         }
521
522         if (cs->relation() != CSSSelector::SubSelector || !cs->tagHistory())
523             break;
524         cs = cs->tagHistory();
525     }
526
527     if (const CSSSelector* tagHistory = cs->tagHistory()) {
528         switch (cs->relation()) {
529         case CSSSelector::Descendant:
530             return tagHistory->selectorText(" " + str.toString() + rightSide);
531         case CSSSelector::Child:
532             return tagHistory->selectorText(" > " + str.toString() + rightSide);
533         case CSSSelector::DirectAdjacent:
534             return tagHistory->selectorText(" + " + str.toString() + rightSide);
535         case CSSSelector::IndirectAdjacent:
536             return tagHistory->selectorText(" ~ " + str.toString() + rightSide);
537         case CSSSelector::SubSelector:
538             ASSERT_NOT_REACHED();
539 #if ASSERT_DISABLED
540             FALLTHROUGH;
541 #endif
542         case CSSSelector::ShadowDescendant:
543             return tagHistory->selectorText(str.toString() + rightSide);
544         }
545     }
546     return str.toString() + rightSide;
547 }
548
549 void CSSSelector::setAttribute(const QualifiedName& value, bool isCaseInsensitive)
550 {
551     createRareData();
552     m_data.m_rareData->m_attribute = value;
553     m_data.m_rareData->m_attributeCanonicalLocalName = isCaseInsensitive ? value.localName().lower() : value.localName();
554 }
555
556 void CSSSelector::setArgument(const AtomicString& value)
557 {
558     createRareData();
559     m_data.m_rareData->m_argument = value;
560 }
561
562 void CSSSelector::setSelectorList(std::unique_ptr<CSSSelectorList> selectorList)
563 {
564     createRareData();
565     m_data.m_rareData->m_selectorList = WTF::move(selectorList);
566 }
567
568 bool CSSSelector::parseNth() const
569 {
570     if (!m_hasRareData)
571         return false;
572     if (m_parsedNth)
573         return true;
574     m_parsedNth = m_data.m_rareData->parseNth();
575     return m_parsedNth;
576 }
577
578 bool CSSSelector::matchNth(int count) const
579 {
580     ASSERT(m_hasRareData);
581     return m_data.m_rareData->matchNth(count);
582 }
583
584 int CSSSelector::nthA() const
585 {
586     ASSERT(m_hasRareData);
587     ASSERT(m_parsedNth);
588     return m_data.m_rareData->m_a;
589 }
590
591 int CSSSelector::nthB() const
592 {
593     ASSERT(m_hasRareData);
594     ASSERT(m_parsedNth);
595     return m_data.m_rareData->m_b;
596 }
597
598 CSSSelector::RareData::RareData(PassRefPtr<AtomicStringImpl> value)
599     : m_value(value.leakRef())
600     , m_a(0)
601     , m_b(0)
602     , m_attribute(anyQName())
603     , m_argument(nullAtom)
604 {
605 }
606
607 CSSSelector::RareData::~RareData()
608 {
609     if (m_value)
610         m_value->deref();
611 }
612
613 // a helper function for parsing nth-arguments
614 bool CSSSelector::RareData::parseNth()
615 {
616     String argument = m_argument.lower();
617
618     if (argument.isEmpty())
619         return false;
620
621     m_a = 0;
622     m_b = 0;
623     if (argument == "odd") {
624         m_a = 2;
625         m_b = 1;
626     } else if (argument == "even") {
627         m_a = 2;
628         m_b = 0;
629     } else {
630         size_t n = argument.find('n');
631         if (n != notFound) {
632             if (argument[0] == '-') {
633                 if (n == 1)
634                     m_a = -1; // -n == -1n
635                 else {
636                     bool ok;
637                     m_a = argument.substringSharingImpl(0, n).toIntStrict(&ok);
638                     if (!ok)
639                         return false;
640                 }
641             } else if (!n)
642                 m_a = 1; // n == 1n
643             else {
644                 bool ok;
645                 m_a = argument.substringSharingImpl(0, n).toIntStrict(&ok);
646                 if (!ok)
647                     return false;
648             }
649
650             size_t p = argument.find('+', n);
651             if (p != notFound) {
652                 bool ok;
653                 m_b = argument.substringSharingImpl(p + 1, argument.length() - p - 1).toIntStrict(&ok);
654                 if (!ok)
655                     return false;
656             } else {
657                 p = argument.find('-', n);
658                 if (p != notFound) {
659                     bool ok;
660                     m_b = -argument.substringSharingImpl(p + 1, argument.length() - p - 1).toIntStrict(&ok);
661                     if (!ok)
662                         return false;
663                 }
664             }
665         } else {
666             bool ok;
667             m_b = argument.toIntStrict(&ok);
668             if (!ok)
669                 return false;
670         }
671     }
672     return true;
673 }
674
675 // a helper function for checking nth-arguments
676 bool CSSSelector::RareData::matchNth(int count)
677 {
678     if (!m_a)
679         return count == m_b;
680     else if (m_a > 0) {
681         if (count < m_b)
682             return false;
683         return (count - m_b) % m_a == 0;
684     } else {
685         if (count > m_b)
686             return false;
687         return (m_b - count) % (-m_a) == 0;
688     }
689 }
690
691 } // namespace WebCore