CSS: Move duplicate property elimination to parser.
authorkling@webkit.org <kling@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 21 May 2012 19:36:39 +0000 (19:36 +0000)
committerkling@webkit.org <kling@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 21 May 2012 19:36:39 +0000 (19:36 +0000)
<http://webkit.org/b/86948>

Reviewed by Antti Koivisto.

Source/WebCore:

Remove the StylePropertySet constructor that handled elimination of duplicate
properties and move that to a new parser method, CSSParser::filteredProperties().
Call sites are converted to using StylePropertySet(const Vector<CSSProperty>&).

Instead of building a hashmap of seen properties, use the new WTF::BitArray class
to track whether a given property ID has been seen, and whether we have an
!important entry for a given ID.

* css/CSSParser.cpp:
(WebCore::CSSParser::parseValue):
(WebCore::CSSParser::parseDeclaration):
(WebCore::CSSParser::filteredProperties):
(WebCore::CSSParser::createStyleRule):
(WebCore::CSSParser::createFontFaceRule):
(WebCore::CSSParser::createPageRule):
(WebCore::CSSParser::createKeyframe):
* css/CSSParser.h:
* css/StylePropertySet.cpp:
(WebCore::StylePropertySet::StylePropertySet):
(WebCore::StylePropertySet::addParsedProperties):
* css/StylePropertySet.h:
(WebCore::StylePropertySet::create):
(StylePropertySet):
* svg/SVGFontFaceElement.cpp:
(WebCore::SVGFontFaceElement::rebuildFontFace):

Source/WTF:

Add WTF::BitArray, a simple, malloc free, fixed-size bit array class.

* GNUmakefile.list.am:
* WTF.gypi:
* WTF.pro:
* WTF.vcproj/WTF.vcproj:
* WTF.xcodeproj/project.pbxproj:
* wtf/BitArray.h: Added.
(WTF):
(BitArray):
(WTF::BitArray::BitArray):
(WTF::BitArray::set):
(WTF::BitArray::get):
* wtf/CMakeLists.txt:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@117809 268f45cc-cd09-0410-ab3c-d52691b4dbfc

14 files changed:
Source/WTF/ChangeLog
Source/WTF/GNUmakefile.list.am
Source/WTF/WTF.gypi
Source/WTF/WTF.pro
Source/WTF/WTF.vcproj/WTF.vcproj
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/BitArray.h [new file with mode: 0644]
Source/WTF/wtf/CMakeLists.txt
Source/WebCore/ChangeLog
Source/WebCore/css/CSSParser.cpp
Source/WebCore/css/CSSParser.h
Source/WebCore/css/StylePropertySet.cpp
Source/WebCore/css/StylePropertySet.h
Source/WebCore/svg/SVGFontFaceElement.cpp

index a15b3cc0c47663ebe53dae4f31d76a7068be8e40..e64a56bc38b7ccc279ab6148df2978b182a6e419 100644 (file)
@@ -1,3 +1,25 @@
+2012-05-21  Andreas Kling  <kling@webkit.org>
+
+        CSS: Move duplicate property elimination to parser.
+        <http://webkit.org/b/86948>
+
+        Reviewed by Antti Koivisto.
+
+        Add WTF::BitArray, a simple, malloc free, fixed-size bit array class.
+
+        * GNUmakefile.list.am:
+        * WTF.gypi:
+        * WTF.pro:
+        * WTF.vcproj/WTF.vcproj:
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/BitArray.h: Added.
+        (WTF):
+        (BitArray):
+        (WTF::BitArray::BitArray):
+        (WTF::BitArray::set):
+        (WTF::BitArray::get):
+        * wtf/CMakeLists.txt:
+
 2012-05-21  Allan Sandfeld Jensen  <allan.jensen@nokia.com>
 
         Colliding isinf/isnan between C99 and C++11 with GCC >=4.6
index a16884a1c10e4bd021f0aae6e8c7261f69bfb8db..1955666e176d5cfa51a6242ea7877ecf9f86372e 100644 (file)
@@ -12,6 +12,7 @@ wtf_sources += \
     Source/WTF/wtf/Assertions.cpp \
     Source/WTF/wtf/Assertions.h \
     Source/WTF/wtf/Atomics.h \
+    Source/WTF/wtf/BitArray.h \
     Source/WTF/wtf/BitVector.cpp \
     Source/WTF/wtf/BitVector.h \
     Source/WTF/wtf/Bitmap.h \
index 942856e4d7451a785b5e19434d5aa29dd3a6cba1..60474edeb1d0d79f3a22e3c4efb7578c8af93962 100644 (file)
@@ -8,6 +8,7 @@
             'wtf/AlwaysInline.h',
             'wtf/Assertions.h',
             'wtf/Atomics.h',
+            'wtf/BitArray.h',
             'wtf/BitVector.h',
             'wtf/Bitmap.h',
             'wtf/BlockStack.h',
index 2bd90b62a044cc82717fa69a1f54806b62fdbb49..46cf7caed71f49a9378dffa6d4e36b37cb5dca44 100644 (file)
@@ -22,6 +22,7 @@ HEADERS += \
     Atomics.h \
     AVLTree.h \
     Bitmap.h \
+    BitArray.h \
     BitVector.h \
     BloomFilter.h \
     BoundsCheckedPointer.h \
index bf78414bd969ca29e47c272e072bc67154985f3b..0882695536423d805294385d9ff21145fbefa147 100644 (file)
                        RelativePath="..\wtf\Bitmap.h"
                        >
                </File>
+               <File
+                       RelativePath="..\wtf\BitArray.h"
+                       >
+               </File>
                <File
                        RelativePath="..\wtf\BitVector.cpp"
                        >
index 26b92bb079421d2d1af75e5b65946bd07d2b3527..023e398f221a7fd24c616803b183d531f7c93444 100644 (file)
@@ -7,6 +7,7 @@
        objects = {
 
 /* Begin PBXBuildFile section */
+               4F0321BC156AA8D1006EBAF6 /* BitArray.h in Headers */ = {isa = PBXBuildFile; fileRef = 4F0321BB156AA8D1006EBAF6 /* BitArray.h */; };
                A876DBD8151816E500DADB95 /* Platform.h in Headers */ = {isa = PBXBuildFile; fileRef = A876DBD7151816E500DADB95 /* Platform.h */; };
                A8A4737F151A825B004123FF /* Alignment.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47254151A825A004123FF /* Alignment.h */; };
                A8A47380151A825B004123FF /* AlwaysInline.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47255151A825A004123FF /* AlwaysInline.h */; };
 /* End PBXBuildFile section */
 
 /* Begin PBXFileReference section */
+               4F0321BB156AA8D1006EBAF6 /* BitArray.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BitArray.h; sourceTree = "<group>"; };
                5D247B6214689B8600E78B76 /* libWTF.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libWTF.a; sourceTree = BUILT_PRODUCTS_DIR; };
                5D247B6E14689C4700E78B76 /* Base.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = Base.xcconfig; sourceTree = "<group>"; };
                5D247B6F14689C4700E78B76 /* CompilerVersion.xcconfig */ = {isa = PBXFileReference; lastKnownFileType = text.xcconfig; path = CompilerVersion.xcconfig; sourceTree = "<group>"; };
                                A8A4725D151A825A004123FF /* Atomics.h */,
                                A8A4725E151A825A004123FF /* AVLTree.h */,
                                A8A4725F151A825A004123FF /* Bitmap.h */,
+                               4F0321BB156AA8D1006EBAF6 /* BitArray.h */,
                                A8A47260151A825A004123FF /* BitVector.cpp */,
                                A8A47261151A825A004123FF /* BitVector.h */,
                                A8A47264151A825A004123FF /* BlockStack.h */,
                                A8A47388151A825B004123FF /* Atomics.h in Headers */,
                                A8A47389151A825B004123FF /* AVLTree.h in Headers */,
                                A8A4738A151A825B004123FF /* Bitmap.h in Headers */,
+                               4F0321BC156AA8D1006EBAF6 /* BitArray.h in Headers */,
                                A8A4738C151A825B004123FF /* BitVector.h in Headers */,
                                A8A4738E151A825B004123FF /* BlockStack.h in Headers */,
                                A8A4738F151A825B004123FF /* BloomFilter.h in Headers */,
diff --git a/Source/WTF/wtf/BitArray.h b/Source/WTF/wtf/BitArray.h
new file mode 100644 (file)
index 0000000..b1ef227
--- /dev/null
@@ -0,0 +1,62 @@
+/*
+ * Copyright (C) 2012 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef BitArray_h
+#define BitArray_h
+
+#include <string.h>
+#include <wtf/Assertions.h>
+
+namespace WTF {
+
+template<unsigned arraySize>
+class BitArray {
+public:
+    BitArray()
+    {
+        memset(m_data, 0, sizeof(m_data));
+    }
+
+    void set(unsigned index)
+    {
+        ASSERT(index < arraySize);
+        m_data[index / 8] |= 1 << (index & 7);
+    }
+
+    bool get(unsigned index) const
+    {
+        ASSERT(index < arraySize);
+        return !!(m_data[index / 8] & (1 << (index & 7)));
+    }
+
+private:
+    unsigned char m_data[arraySize / 8 + 1];
+};
+
+} // namespace WTF
+
+using WTF::BitArray;
+
+#endif // BitArray_h
index e18094fa5dc06557ea9d6fa8175842f95d1f9432..cdcca680abb949699f1c50e93923ec84b2ff41ec 100644 (file)
@@ -5,6 +5,7 @@ SET(WTF_HEADERS
     AlwaysInline.h
     Assertions.h
     Atomics.h
+    BitArray.h
     BitVector.h
     Bitmap.h
     BoundsCheckedPointer.h
index 5fa4f54cb174248e085eb4ebf1e011ab4f2b1fb1..24dead4d45a4c35134ab14ac8a1a8ba025c08b7e 100644 (file)
@@ -1,3 +1,36 @@
+2012-05-21  Andreas Kling  <kling@webkit.org>
+
+        CSS: Move duplicate property elimination to parser.
+        <http://webkit.org/b/86948>
+
+        Reviewed by Antti Koivisto.
+
+        Remove the StylePropertySet constructor that handled elimination of duplicate
+        properties and move that to a new parser method, CSSParser::filteredProperties().
+        Call sites are converted to using StylePropertySet(const Vector<CSSProperty>&).
+
+        Instead of building a hashmap of seen properties, use the new WTF::BitArray class
+        to track whether a given property ID has been seen, and whether we have an
+        !important entry for a given ID.
+
+        * css/CSSParser.cpp:
+        (WebCore::CSSParser::parseValue):
+        (WebCore::CSSParser::parseDeclaration):
+        (WebCore::CSSParser::filteredProperties):
+        (WebCore::CSSParser::createStyleRule):
+        (WebCore::CSSParser::createFontFaceRule):
+        (WebCore::CSSParser::createPageRule):
+        (WebCore::CSSParser::createKeyframe):
+        * css/CSSParser.h:
+        * css/StylePropertySet.cpp:
+        (WebCore::StylePropertySet::StylePropertySet):
+        (WebCore::StylePropertySet::addParsedProperties):
+        * css/StylePropertySet.h:
+        (WebCore::StylePropertySet::create):
+        (StylePropertySet):
+        * svg/SVGFontFaceElement.cpp:
+        (WebCore::SVGFontFaceElement::rebuildFontFace):
+
 2012-05-21  Joshua Bell  <jsbell@chromium.org>
 
         IndexedDB: Index key paths that yield invalid keys should not fail an add/put
index ddbc90f05874030813b4a0057d37e481194f9748..ab5d8041f70f9653c5fad8c424b191e4420f0f44 100644 (file)
@@ -89,6 +89,7 @@
 #include "WebKitCSSShaderValue.h"
 #endif
 #include <limits.h>
+#include <wtf/BitArray.h>
 #include <wtf/HexNumber.h>
 #include <wtf/dtoa.h>
 #include <wtf/text/StringBuffer.h>
@@ -977,7 +978,7 @@ bool CSSParser::parseValue(StylePropertySet* declaration, CSSPropertyID property
         deleteFontFaceOnlyValues();
     if (!m_parsedProperties.isEmpty()) {
         ok = true;
-        declaration->addParsedProperties(m_parsedProperties.data(), m_parsedProperties.size());
+        declaration->addParsedProperties(m_parsedProperties);
         clearProperties();
     }
 
@@ -1073,7 +1074,7 @@ bool CSSParser::parseDeclaration(StylePropertySet* declaration, const String& st
         deleteFontFaceOnlyValues();
     if (!m_parsedProperties.isEmpty()) {
         ok = true;
-        declaration->addParsedProperties(m_parsedProperties.data(), m_parsedProperties.size());
+        declaration->addParsedProperties(m_parsedProperties);
         clearProperties();
     }
 
@@ -1109,6 +1110,42 @@ PassOwnPtr<MediaQuery> CSSParser::parseMediaQuery(const String& string)
     return m_mediaQuery.release();
 }
 
+Vector<CSSProperty> CSSParser::filteredProperties() const
+{
+    BitArray<numCSSProperties> seenProperties;
+    BitArray<numCSSProperties> seenImportantProperties;
+
+    Vector<CSSProperty> results;
+    results.reserveInitialCapacity(m_parsedProperties.size());
+
+    for (unsigned i = 0; i < m_parsedProperties.size(); ++i) {
+        const CSSProperty& property = m_parsedProperties[i];
+        const unsigned propertyIDIndex = property.id() - firstCSSProperty;
+
+        // Ignore non-important properties if we already have an important property with the same ID.
+        if (!property.isImportant() && seenImportantProperties.get(propertyIDIndex))
+            continue;
+
+        // If we already had this property, this new one takes precedence, so wipe out the old one.
+        if (seenProperties.get(propertyIDIndex)) {
+            for (unsigned i = 0; i < results.size(); ++i) {
+                if (results[i].id() == property.id()) {
+                    results.remove(i);
+                    break;
+                }
+            }
+        }
+
+        if (property.isImportant())
+            seenImportantProperties.set(propertyIDIndex);
+        seenProperties.set(propertyIDIndex);
+
+        results.append(property);
+    }
+
+    return results;
+}
+
 void CSSParser::addProperty(CSSPropertyID propId, PassRefPtr<CSSValue> value, bool important, bool implicit)
 {
     m_parsedProperties.append(CSSProperty(propId, value, important, m_currentShorthand, m_implicitShorthand || implicit));
@@ -9041,7 +9078,7 @@ StyleRuleBase* CSSParser::createStyleRule(Vector<OwnPtr<CSSParserSelector> >* se
         rule->parserAdoptSelectorVector(*selectors);
         if (m_hasFontFaceOnlyValues)
             deleteFontFaceOnlyValues();
-        rule->setProperties(StylePropertySet::create(m_parsedProperties.data(), m_parsedProperties.size(), m_context.mode));
+        rule->setProperties(StylePropertySet::create(filteredProperties(), m_context.mode));
         result = rule.get();
         m_parsedRules.append(rule.release());
         if (m_ruleRangeMap) {
@@ -9077,7 +9114,7 @@ StyleRuleBase* CSSParser::createFontFaceRule()
         }
     }
     RefPtr<StyleRuleFontFace> rule = StyleRuleFontFace::create();
-    rule->setProperties(StylePropertySet::create(m_parsedProperties.data(), m_parsedProperties.size(), m_context.mode));
+    rule->setProperties(StylePropertySet::create(filteredProperties(), m_context.mode));
     clearProperties();
     StyleRuleFontFace* result = rule.get();
     m_parsedRules.append(rule.release());
@@ -9150,7 +9187,7 @@ StyleRuleBase* CSSParser::createPageRule(PassOwnPtr<CSSParserSelector> pageSelec
         Vector<OwnPtr<CSSParserSelector> > selectorVector;
         selectorVector.append(pageSelector);
         rule->parserAdoptSelectorVector(selectorVector);
-        rule->setProperties(StylePropertySet::create(m_parsedProperties.data(), m_parsedProperties.size(), m_context.mode));
+        rule->setProperties(StylePropertySet::create(filteredProperties(), m_context.mode));
         pageRule = rule.get();
         m_parsedRules.append(rule.release());
     }
@@ -9228,7 +9265,7 @@ StyleKeyframe* CSSParser::createKeyframe(CSSParserValueList* keys)
 
     RefPtr<StyleKeyframe> keyframe = StyleKeyframe::create();
     keyframe->setKeyText(keyString);
-    keyframe->setProperties(StylePropertySet::create(m_parsedProperties.data(), m_parsedProperties.size(), m_context.mode));
+    keyframe->setProperties(StylePropertySet::create(filteredProperties(), m_context.mode));
 
     clearProperties();
 
index 345231c39cd4f14d883d33f6a062fa9d0e6419d4..d8ddbb6b664eee3225ea4371e2aae879ba052724 100644 (file)
@@ -282,6 +282,8 @@ public:
 
     void clearProperties();
 
+    Vector<CSSProperty> filteredProperties() const;
+
     CSSParserContext m_context;
 
     bool m_important;
index ac7eacd8c8c9af200f24f48fd41ab699d7c13feb..67ac95c9f827e2b8498ba888b87182375d7b0448 100644 (file)
@@ -56,38 +56,14 @@ StylePropertySet::StylePropertySet(CSSParserMode cssParserMode)
 {
 }
 
-StylePropertySet::StylePropertySet(const Vector<CSSProperty>& properties)
+StylePropertySet::StylePropertySet(const Vector<CSSProperty>& properties, CSSParserMode cssParserMode)
     : m_properties(properties)
-    , m_cssParserMode(CSSStrictMode)
+    , m_cssParserMode(cssParserMode)
     , m_ownsCSSOMWrapper(false)
 {
     m_properties.shrinkToFit();
 }
 
-StylePropertySet::StylePropertySet(const CSSProperty* properties, int numProperties, CSSParserMode cssParserMode)
-    : m_cssParserMode(cssParserMode)
-    , m_ownsCSSOMWrapper(false)
-{
-    // FIXME: This logic belongs in CSSParser.
-
-    m_properties.reserveInitialCapacity(numProperties);
-    HashMap<int, bool> candidates;
-    for (int i = 0; i < numProperties; ++i) {
-        const CSSProperty& property = properties[i];
-        bool important = property.isImportant();
-
-        HashMap<int, bool>::iterator it = candidates.find(property.id());
-        if (it != candidates.end()) {
-            if (!important && it->second)
-                continue;
-            removeProperty(property.id());
-        }
-
-        m_properties.append(property);
-        candidates.set(property.id(), important);
-    }
-}
-
 StylePropertySet::StylePropertySet(const StylePropertySet& o)
     : RefCounted<StylePropertySet>()
     , m_properties(o.m_properties)
@@ -592,10 +568,10 @@ void StylePropertySet::parseDeclaration(const String& styleDeclaration, StyleShe
     parser.parseDeclaration(this, styleDeclaration, 0, contextStyleSheet);
 }
 
-void StylePropertySet::addParsedProperties(const CSSProperty* properties, int numProperties)
+void StylePropertySet::addParsedProperties(const Vector<CSSProperty>& properties)
 {
-    m_properties.reserveCapacity(numProperties);
-    for (int i = 0; i < numProperties; ++i)
+    m_properties.reserveCapacity(m_properties.size() + properties.size());
+    for (unsigned i = 0; i < properties.size(); ++i)
         addParsedProperty(properties[i]);
 }
 
index d500398d032d0f3131b18b7e092d387bc3e4ffdb..148d1e8274cd4b0f83f6a03e1c4a075f726ce555 100644 (file)
@@ -47,13 +47,9 @@ public:
     {
         return adoptRef(new StylePropertySet(cssParserMode));
     }
-    static PassRefPtr<StylePropertySet> create(const CSSProperty* properties, int numProperties, CSSParserMode cssParserMode)
+    static PassRefPtr<StylePropertySet> create(const Vector<CSSProperty>& properties, CSSParserMode cssParserMode = CSSStrictMode)
     {
-        return adoptRef(new StylePropertySet(properties, numProperties, cssParserMode));
-    }
-    static PassRefPtr<StylePropertySet> create(const Vector<CSSProperty>& properties)
-    {
-        return adoptRef(new StylePropertySet(properties));
+        return adoptRef(new StylePropertySet(properties, cssParserMode));
     }
 
     unsigned propertyCount() const { return m_properties.size(); }
@@ -80,7 +76,7 @@ public:
 
     void parseDeclaration(const String& styleDeclaration, StyleSheetInternal* contextStyleSheet);
 
-    void addParsedProperties(const CSSProperty*, int numProperties);
+    void addParsedProperties(const Vector<CSSProperty>&);
     void addParsedProperty(const CSSProperty&);
 
     PassRefPtr<StylePropertySet> copyBlockProperties() const;
@@ -121,9 +117,8 @@ public:
     
 private:
     StylePropertySet(CSSParserMode);
-    StylePropertySet(const Vector<CSSProperty>&);
+    StylePropertySet(const Vector<CSSProperty>&, CSSParserMode);
     StylePropertySet(const StylePropertySet&);
-    StylePropertySet(const CSSProperty*, int numProperties, CSSParserMode);
 
     void setNeedsStyleRecalc();
 
index 6d6bab2fd29048b755143dcdf7798038be547a7f..17175de1d67625789b06e7f37d5ab363ccdd444d 100644 (file)
@@ -297,8 +297,7 @@ void SVGFontFaceElement::rebuildFontFace()
         return;
 
     // Parse in-memory CSS rules
-    CSSProperty srcProperty(CSSPropertySrc, list);
-    m_fontFaceRule->properties()->addParsedProperties(&srcProperty, 1);
+    m_fontFaceRule->properties()->addParsedProperty(CSSProperty(CSSPropertySrc, list));
 
     if (describesParentFont) {    
         // Traverse parsed CSS values and associate CSSFontFaceSrcValue elements with ourselves.