RuleSet should use malloc rather than Vector

Source/core/css/RuleSet.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
  * Copyright (C) Research In Motion Limited 2011. All rights reserved.
@@ skipping 112 matching lines @@
 {
     if (addRuleFlags & RuleIsInRegionRule)
         return PropertyWhitelistRegion;
     for (const CSSSelector* component = selector; component; component = component->tagHistory()) {
         if (component->pseudoType() == CSSSelector::PseudoCue || (component->m_match == CSSSelector::PseudoElement && component->value() == TextTrackCue::cueShadowPseudoId()))
             return PropertyWhitelistCue;
     }
     return PropertyWhitelistNone;
 }
 
+namespace {
+
+// FIXME: Should we move this class to WTF?
+template<typename T>
+class TerminatedArrayBuilder {

[esprehn, 2013/06/26 00:37:33]

I'd rather we added a TerminatedArray<T> class with size() that does the loop
you have below in the constructor and exposed a proper ::iterator and such, but
we can sort that out in the future.

[abarth-chromium, 2013/06/26 00:57:00]

Ok.  I struggled with how much to abstract this work.

+public:
+    explicit TerminatedArrayBuilder(PassOwnPtr<T> array)
+        : m_array(array)
+        , m_count(0)
+        , m_capacity(0)
+    {
+        if (!m_array)
+            return;
+        for (T* item = m_array.get(); !item->isLastInArray(); ++item)
+            ++m_count;
+        ++m_count; // To count the last item itself.
+        m_capacity = m_count;
+    }
+
+    void grow(size_t count)
+    {
+        ASSERT(count);
+        if (!m_array) {
+            ASSERT(!m_count);
+            ASSERT(!m_capacity);
+            m_capacity = count;
+            m_array = adoptPtr(static_cast<T*>(fastMalloc(m_capacity * sizeof(T))));
+            return;
+        }
+        m_capacity += count;
+        m_array = adoptPtr(static_cast<T*>(fastRealloc(m_array.leakPtr(), m_capacity * sizeof(T))));
+        m_array.get()[m_count - 1].setLastInArray(false);
+    }
+
+    void append(const T& item)
+    {
+        RELEASE_ASSERT(m_count < m_capacity);
+        m_array.get()[m_count++] = item;

[esprehn, 2013/06/26 00:37:33]

This looks easy to break, I can append() an item that claims it's the last.

[abarth-chromium, 2013/06/26 00:57:00]

There's an ASSERT in release() to make sure the array is consistent when we're
done building.  I've added an ASSERT here as well.

+    }
+
+    PassOwnPtr<T> release()
+    {
+        RELEASE_ASSERT(m_count == m_capacity);
+        if (m_array)
+            m_array.get()[m_count - 1].setLastInArray(true);
+        assertValid();
+        return m_array.release();
+    }
+
+private:
+#ifndef NDEBUG
+    void assertValid()
+    {
+        for (size_t i = 0; i < m_count; ++i) {
+            bool isLastInArray = (i + 1 == m_count);
+            ASSERT(m_array.get()[i].isLastInArray() == isLastInArray);
+        }
+    }
+#else
+    void assertValid() { }
+#endif
+
+    OwnPtr<T> m_array;
+    size_t m_count;
+    size_t m_capacity;
+};
+
+}
+
 RuleData::RuleData(StyleRule* rule, unsigned selectorIndex, unsigned position, AddRuleFlags addRuleFlags)
     : m_rule(rule)
     , m_selectorIndex(selectorIndex)
+    , m_isLastInArray(0)

[esprehn, 2013/06/26 00:37:33]

I think you can just do false here.

[abarth-chromium, 2013/06/26 00:57:00]

Done.

     , m_position(position)
     , m_hasFastCheckableSelector((addRuleFlags & RuleCanUseFastCheckSelector) && SelectorCheckerFastPath::canUse(selector()))
     , m_specificity(selector()->specificity())
     , m_hasMultipartSelector(!!selector()->tagHistory())
     , m_hasRightmostSelectorMatchingHTMLBasedOnRuleHash(isSelectorMatchingHTMLBasedOnRuleHash(selector()))
     , m_containsUncommonAttributeSelector(WebCore::containsUncommonAttributeSelector(selector()))
     , m_linkMatchType(SelectorChecker::determineLinkMatchType(selector()))
     , m_hasDocumentSecurityOrigin(addRuleFlags & RuleHasDocumentSecurityOrigin)
     , m_propertyWhitelistType(determinePropertyWhitelistType(addRuleFlags, selector()))
 {
@@ skipping 228 matching lines @@
 {
     for (size_t selectorIndex = 0; selectorIndex != notFound; selectorIndex = rule->selectorList().indexOfNextSelectorAfter(selectorIndex))
         addRule(rule, selectorIndex, addRuleFlags);
 }
 
 void RuleSet::compactPendingRules(PendingRuleMap& pendingMap, CompactRuleMap& compactMap)
 {
     PendingRuleMap::iterator end = pendingMap.end();
     for (PendingRuleMap::iterator it = pendingMap.begin(); it != end; ++it) {
         OwnPtr<LinkedStack<RuleData> > pendingRules = it->value.release();
-        size_t pendingSize = pendingRules->size();
-        ASSERT(pendingSize);
+        CompactRuleMap::iterator compactRules = compactMap.add(it->key, nullptr).iterator;
 
-        OwnPtr<Vector<RuleData> >& compactRules = compactMap.add(it->key, nullptr).iterator->value;
-        if (!compactRules) {
-            compactRules = adoptPtr(new Vector<RuleData>);
-            compactRules->reserveInitialCapacity(pendingSize);
-        } else {
-            compactRules->reserveCapacity(compactRules->size() + pendingSize);
+        TerminatedArrayBuilder<RuleData> builder(compactRules->value.release());
+        builder.grow(pendingRules->size());
+        while (!pendingRules->isEmpty()) {
+            builder.append(pendingRules->peek());
+            pendingRules->pop();
         }
 
-        while (!pendingRules->isEmpty()) {
-            compactRules->append(pendingRules->peek());
-            pendingRules->pop();
-        }
+        compactRules->value = builder.release();
     }
 }
 
 void RuleSet::compactRules()
 {
     ASSERT(m_pendingRules);
     OwnPtr<PendingRuleMaps> pendingRules = m_pendingRules.release();
     compactPendingRules(pendingRules->idRules, m_idRules);
     compactPendingRules(pendingRules->classRules, m_classRules);
     compactPendingRules(pendingRules->tagRules, m_tagRules);
     compactPendingRules(pendingRules->shadowPseudoElementRules, m_shadowPseudoElementRules);
     m_linkPseudoClassRules.shrinkToFit();
     m_cuePseudoRules.shrinkToFit();
     m_focusPseudoClassRules.shrinkToFit();
     m_universalRules.shrinkToFit();
     m_pageRules.shrinkToFit();
 }
 
 } // namespace WebCore