Populate the name-to-pseudo map lazily

Source/core/css/CSSSelector.cpp

 /*
  * Copyright (C) 1999-2003 Lars Knoll (knoll@kde.org)
  *               1999 Waldo Bastian (bastian@kde.org)
  *               2001 Andreas Schlapbach (schlpbch@iam.unibe.ch)
  *               2001-2003 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2002, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
  * Copyright (C) 2008 David Smith (catfish.man@gmail.com)
  * Copyright (C) 2010 Google Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
@@ skipping 15 matching lines @@
 #include "config.h"
 #include "core/css/CSSSelector.h"
 
 #include "HTMLNames.h"
 #include "RuntimeEnabledFeatures.h"
 #include "core/css/CSSOMUtils.h"
 #include "core/css/CSSSelectorList.h"
 #include "wtf/Assertions.h"
 #include "wtf/HashMap.h"
 #include "wtf/StdLibExtras.h"
+#include "wtf/text/AtomicStringHash.h"
 #include "wtf/text/StringBuilder.h"
-#include "wtf/text/StringHash.h"
 
 #ifndef NDEBUG
 #include <stdio.h>
 #endif
 
 namespace WebCore {
 
 using namespace HTMLNames;
 
 struct SameSizeAsCSSSelector {
@@ skipping 219 matching lines @@
     ASSERT_NOT_REACHED();
     return NOPSEUDO;
 }
 
 // Could be made smaller and faster by replacing pointer with an
 // offset into a string buffer and making the bit fields smaller but
 // that could not be maintained by hand.
 struct NameToPseudoStruct {
     const char* string;
     unsigned type:8;
+
+    bool operator<(const NameToPseudoStruct& b) const { return strcmp(string, b.string) < 0; }
 };
 
+// This table should be kept sorted.
 const static NameToPseudoStruct pseudoTypeMap[] = {
-{"active",                        CSSSelector::PseudoActive},
-{"after",                         CSSSelector::PseudoAfter},
 {"-webkit-any(",                  CSSSelector::PseudoAny},
 {"-webkit-any-link",              CSSSelector::PseudoAnyLink},
 {"-webkit-autofill",              CSSSelector::PseudoAutofill},
-{"backdrop",                      CSSSelector::PseudoBackdrop},
-{"before",                        CSSSelector::PseudoBefore},
-{"checked",                       CSSSelector::PseudoChecked},
-{"default",                       CSSSelector::PseudoDefault},
-{"disabled",                      CSSSelector::PseudoDisabled},
-{"read-only",                     CSSSelector::PseudoReadOnly},
-{"read-write",                    CSSSelector::PseudoReadWrite},
-{"valid",                         CSSSelector::PseudoValid},
-{"invalid",                       CSSSelector::PseudoInvalid},
 {"-webkit-drag",                  CSSSelector::PseudoDrag},
-{"empty",                         CSSSelector::PseudoEmpty},
-{"enabled",                       CSSSelector::PseudoEnabled},
-{"first-child",                   CSSSelector::PseudoFirstChild},
-{"first-letter",                  CSSSelector::PseudoFirstLetter},
-{"first-line",                    CSSSelector::PseudoFirstLine},
-{"first-of-type",                 CSSSelector::PseudoFirstOfType},
 {"-webkit-full-page-media",       CSSSelector::PseudoFullPageMedia},
-{"nth-child(",                    CSSSelector::PseudoNthChild},
-{"nth-of-type(",                  CSSSelector::PseudoNthOfType},
-{"nth-last-child(",               CSSSelector::PseudoNthLastChild},
-{"nth-last-of-type(",             CSSSelector::PseudoNthLastOfType},
-{"focus",                         CSSSelector::PseudoFocus},
-{"hover",                         CSSSelector::PseudoHover},
-{"indeterminate",                 CSSSelector::PseudoIndeterminate},
-{"last-child",                    CSSSelector::PseudoLastChild},
-{"last-of-type",                  CSSSelector::PseudoLastOfType},
-{"link",                          CSSSelector::PseudoLink},
-{"lang(",                         CSSSelector::PseudoLang},
-{"not(",                          CSSSelector::PseudoNot},
-{"only-child",                    CSSSelector::PseudoOnlyChild},
-{"only-of-type",                  CSSSelector::PseudoOnlyOfType},
-{"optional",                      CSSSelector::PseudoOptional},
-{"required",                      CSSSelector::PseudoRequired},
+{"-webkit-full-screen",           CSSSelector::PseudoFullScreen},
+{"-webkit-full-screen-ancestor",  CSSSelector::PseudoFullScreenAncestor},
+{"-webkit-full-screen-document",  CSSSelector::PseudoFullScreenDocument},
 {"-webkit-resizer",               CSSSelector::PseudoResizer},
-{"root",                          CSSSelector::PseudoRoot},
 {"-webkit-scrollbar",             CSSSelector::PseudoScrollbar},
 {"-webkit-scrollbar-button",      CSSSelector::PseudoScrollbarButton},
 {"-webkit-scrollbar-corner",      CSSSelector::PseudoScrollbarCorner},
 {"-webkit-scrollbar-thumb",       CSSSelector::PseudoScrollbarThumb},
 {"-webkit-scrollbar-track",       CSSSelector::PseudoScrollbarTrack},
 {"-webkit-scrollbar-track-piece", CSSSelector::PseudoScrollbarTrackPiece},
-{"selection",                     CSSSelector::PseudoSelection},
-{"target",                        CSSSelector::PseudoTarget},
-{"visited",                       CSSSelector::PseudoVisited},
-{"window-inactive",               CSSSelector::PseudoWindowInactive},
+{"active",                        CSSSelector::PseudoActive},
+{"after",                         CSSSelector::PseudoAfter},
+{"backdrop",                      CSSSelector::PseudoBackdrop},
+{"before",                        CSSSelector::PseudoBefore},
+{"checked",                       CSSSelector::PseudoChecked},
+{"content",                       CSSSelector::PseudoContent},
+{"corner-present",                CSSSelector::PseudoCornerPresent},
+{"cue",                           CSSSelector::PseudoWebKitCustomElement},
+{"cue(",                          CSSSelector::PseudoCue},
 {"decrement",                     CSSSelector::PseudoDecrement},
-{"increment",                     CSSSelector::PseudoIncrement},
-{"start",                         CSSSelector::PseudoStart},
+{"default",                       CSSSelector::PseudoDefault},
+{"disabled",                      CSSSelector::PseudoDisabled},
+{"double-button",                 CSSSelector::PseudoDoubleButton},
+{"empty",                         CSSSelector::PseudoEmpty},
+{"enabled",                       CSSSelector::PseudoEnabled},
 {"end",                           CSSSelector::PseudoEnd},
+{"first",                         CSSSelector::PseudoFirstPage},
+{"first-child",                   CSSSelector::PseudoFirstChild},
+{"first-letter",                  CSSSelector::PseudoFirstLetter},
+{"first-line",                    CSSSelector::PseudoFirstLine},
+{"first-of-type",                 CSSSelector::PseudoFirstOfType},
+{"focus",                         CSSSelector::PseudoFocus},
+{"future",                        CSSSelector::PseudoFutureCue},
 {"horizontal",                    CSSSelector::PseudoHorizontal},
-{"vertical",                      CSSSelector::PseudoVertical},
-{"double-button",                 CSSSelector::PseudoDoubleButton},
-{"single-button",                 CSSSelector::PseudoSingleButton},
-{"no-button",                     CSSSelector::PseudoNoButton},
-{"corner-present",                CSSSelector::PseudoCornerPresent},
-{"first",                         CSSSelector::PseudoFirstPage},
-{"left",                          CSSSelector::PseudoLeftPage},
-{"right",                         CSSSelector::PseudoRightPage},
-{"-webkit-full-screen",           CSSSelector::PseudoFullScreen},
-{"-webkit-full-screen-document",  CSSSelector::PseudoFullScreenDocument},
-{"-webkit-full-screen-ancestor",  CSSSelector::PseudoFullScreenAncestor},
-{"cue(",                          CSSSelector::PseudoCue},
-{"cue",                           CSSSelector::PseudoWebKitCustomElement},
-{"future",                        CSSSelector::PseudoFutureCue},
-{"past",                          CSSSelector::PseudoPastCue},
-{"in-range",                      CSSSelector::PseudoInRange},
-{"out-of-range",                  CSSSelector::PseudoOutOfRange},
-{"scope",                         CSSSelector::PseudoScope},
-{"unresolved",                    CSSSelector::PseudoUnresolved},
 {"host",                          CSSSelector::PseudoHost},
 {"host(",                         CSSSelector::PseudoHost},
 {"host-context(",                 CSSSelector::PseudoHostContext},
-{"content",                       CSSSelector::PseudoContent},
+{"hover",                         CSSSelector::PseudoHover},
+{"in-range",                      CSSSelector::PseudoInRange},
+{"increment",                     CSSSelector::PseudoIncrement},
+{"indeterminate",                 CSSSelector::PseudoIndeterminate},
+{"invalid",                       CSSSelector::PseudoInvalid},
+{"lang(",                         CSSSelector::PseudoLang},
+{"last-child",                    CSSSelector::PseudoLastChild},
+{"last-of-type",                  CSSSelector::PseudoLastOfType},
+{"left",                          CSSSelector::PseudoLeftPage},
+{"link",                          CSSSelector::PseudoLink},
+{"no-button",                     CSSSelector::PseudoNoButton},
+{"not(",                          CSSSelector::PseudoNot},
+{"nth-child(",                    CSSSelector::PseudoNthChild},
+{"nth-last-child(",               CSSSelector::PseudoNthLastChild},
+{"nth-last-of-type(",             CSSSelector::PseudoNthLastOfType},
+{"nth-of-type(",                  CSSSelector::PseudoNthOfType},
+{"only-child",                    CSSSelector::PseudoOnlyChild},
+{"only-of-type",                  CSSSelector::PseudoOnlyOfType},
+{"optional",                      CSSSelector::PseudoOptional},
+{"out-of-range",                  CSSSelector::PseudoOutOfRange},
+{"past",                          CSSSelector::PseudoPastCue},
+{"read-only",                     CSSSelector::PseudoReadOnly},
+{"read-write",                    CSSSelector::PseudoReadWrite},
+{"required",                      CSSSelector::PseudoRequired},
+{"right",                         CSSSelector::PseudoRightPage},
+{"root",                          CSSSelector::PseudoRoot},
+{"scope",                         CSSSelector::PseudoScope},
+{"selection",                     CSSSelector::PseudoSelection},
 {"shadow",                        CSSSelector::PseudoShadow},
+{"single-button",                 CSSSelector::PseudoSingleButton},
+{"start",                         CSSSelector::PseudoStart},
+{"target",                        CSSSelector::PseudoTarget},
+{"unresolved",                    CSSSelector::PseudoUnresolved},
+{"valid",                         CSSSelector::PseudoValid},
+{"vertical",                      CSSSelector::PseudoVertical},
+{"visited",                       CSSSelector::PseudoVisited},
+{"window-inactive",               CSSSelector::PseudoWindowInactive},
 };
 
-static HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoTypeMap()
+static CSSSelector::PseudoType nameToPseudoType(const AtomicString& name)
 {
-    static HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoType = 0;
-    if (!nameToPseudoType) {
-        nameToPseudoType = new HashMap<StringImpl*, CSSSelector::PseudoType>;
+    typedef HashMap<AtomicString, CSSSelector::PseudoType> NameToPseudoTypeMap;
+    DEFINE_STATIC_LOCAL(NameToPseudoTypeMap, nameToPseudoTypeMap, ());
 
-        size_t pseudoCount = WTF_ARRAY_LENGTH(pseudoTypeMap);
-        for (size_t i = 0; i < pseudoCount; i++) {
-            const char* str = pseudoTypeMap[i].string;
-            CSSSelector::PseudoType type;
-            type = static_cast<CSSSelector::PseudoType>(pseudoTypeMap[i].type);
-            // This is a one-time leak.
-            AtomicString* name = new AtomicString(str, strlen(str), AtomicString::ConstructFromLiteral);
-            nameToPseudoType->set(name->impl(), type);
-        }
-    }
+    NameToPseudoTypeMap::iterator slot = nameToPseudoTypeMap.find(name);

[esprehn, 2014/04/25 09:08:03]

You might even be able to always binary search and get rid of the hash table
entirely.

[fs, 2014/04/25 11:23:33]

Yepp, that's doable, but I figured it'd be too gnarly... Anyway, uploaded now,
and probably warrants a new look.

+    if (slot != nameToPseudoTypeMap.end())
+        return slot->value;
 
-    return nameToPseudoType;
+    const NameToPseudoStruct* pseudoTypeMapEnd = pseudoTypeMap + WTF_ARRAY_LENGTH(pseudoTypeMap);
+    CString cstrName = name.utf8();

[apavlov, 2014/04/24 15:19:18]

This could as well be inlined

[fs, 2014/04/24 16:01:53]

Assuming you by that mean:

... key = { name.utf8().data(), ... };

then, no, I don't think so, since the lifetime of the CString would then not
last to the next line. Unfortunately.

[apavlov, 2014/04/24 16:53:06]

Ahh, correct. There's a newly constructed object in flight there...

+    NameToPseudoStruct key = { cstrName.data(), CSSSelector::PseudoUnknown };
+    const NameToPseudoStruct* match = std::lower_bound(pseudoTypeMap, pseudoTypeMapEnd, key);
+    if (match == pseudoTypeMapEnd || strcmp(match->string, key.string))
+        return CSSSelector::PseudoUnknown;
+
+    CSSSelector::PseudoType pseudoType = static_cast<CSSSelector::PseudoType>(match->type);
+    nameToPseudoTypeMap.set(name, pseudoType);
+    return pseudoType;
 }
 
 #ifndef NDEBUG
 void CSSSelector::show(int indent) const
 {
     printf("%*sselectorText(): %s\n", indent, "", selectorText().ascii().data());
     printf("%*sm_match: %d\n", indent, "", m_match);
     printf("%*sisCustomPseudoElement(): %d\n", indent, "", isCustomPseudoElement());
     if (m_match != Tag)
         printf("%*svalue(): %s\n", indent, "", value().ascii().data());
@@ skipping 18 matching lines @@
     printf("\n******* CSSSelector::show(\"%s\") *******\n", selectorText().ascii().data());
     show(2);
     printf("******* end *******\n");
 }
 #endif
 
 CSSSelector::PseudoType CSSSelector::parsePseudoType(const AtomicString& name)
 {
     if (name.isNull())
         return PseudoUnknown;
-    HashMap<StringImpl*, CSSSelector::PseudoType>* nameToPseudoType = nameToPseudoTypeMap();
-    HashMap<StringImpl*, CSSSelector::PseudoType>::iterator slot = nameToPseudoType->find(name.impl());
 
-    if (slot != nameToPseudoType->end())
-        return slot->value;
+    CSSSelector::PseudoType pseudoType = nameToPseudoType(name);
+    if (pseudoType != PseudoUnknown)
+        return pseudoType;
 
     if (name.startsWith("-webkit-"))
         return PseudoWebKitCustomElement;
     if (name.startsWith("cue"))
         return PseudoUserAgentCustomElement;
 
     return PseudoUnknown;
 }
 
 void CSSSelector::extractPseudoType() const
@@ skipping 446 matching lines @@
             return false;
         return (count - m_b) % m_a == 0;
     } else {
         if (count > m_b)
             return false;
         return (m_b - count) % (-m_a) == 0;
     }
 }
 
 } // namespace WebCore