First implementation of the paint slimming update algorithm

Source/core/paint/ViewDisplayList.cpp

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "config.h"
 #include "core/paint/ViewDisplayList.h"
 
 #include "platform/NotImplemented.h"
 #include "platform/RuntimeEnabledFeatures.h"
 
 #ifndef NDEBUG
 #include "core/rendering/RenderObject.h"
 #include "wtf/text/WTFString.h"
 #endif
 
 namespace blink {
 
 // DisplayItem types must be kept in sync with PaintPhase.
 COMPILE_ASSERT((unsigned)DisplayItem::DrawingPaintPhaseBlockBackground == (unsigned)PaintPhaseBlockBackground, DisplayItem_Type_should_stay_in_sync);
 COMPILE_ASSERT((unsigned)DisplayItem::DrawingPaintPhaseClippingMask == (unsigned)PaintPhaseClippingMask, DisplayItem_Type_should_stay_in_sync);
 
 const PaintList& ViewDisplayList::paintList()
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
 
     updatePaintList();
-    return m_newPaints;
+    return m_paintList;
 }
 
 void ViewDisplayList::add(WTF::PassOwnPtr<DisplayItem> displayItem)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     m_newPaints.append(displayItem);
 }
 
 void ViewDisplayList::invalidate(const RenderObject* renderer)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     m_invalidated.add(renderer);
 }
 
-bool ViewDisplayList::isRepaint(PaintList::iterator begin, const DisplayItem& displayItem)
+PaintList::iterator ViewDisplayList::findRepaintWithoutInvalidation(PaintList::iterator begin, const DisplayItem& displayItem)

[chrishtr, 2014/10/31 21:30:11]

The name findRepaintWithoutInvalidation is not that great for explaining what
this is doing. How about just findDisplayItem? and move the check for
wasInvalidated up to the caller and don't call this method unless you want to
find the display item.

[pdr., 2014/11/01 05:23:23]

Good idea. Done.

 {
-    notImplemented();
-    return false;
+    PaintList::iterator end = m_paintList.end();
+
+    if (wasInvalidated(displayItem))
+        return end;
+
+    if (displayItem.renderer() && !m_paintListRenderers.contains(displayItem.renderer()))
+        return end;
+
+    for (PaintList::iterator it = begin; it != end; ++it) {
+        DisplayItem& existing = **it;
+        if (existing.idsEqual(displayItem))
+            return it;
+    }
+
+    // This should only occur for non-renderer display items.
+    // FIXME: figure out how to handle clips/etc.
+    ASSERT(!displayItem.renderer());
+    return end;
+}
+
+bool ViewDisplayList::wasInvalidated(const DisplayItem& displayItem) const
+{
+    return displayItem.renderer() && m_invalidated.contains(displayItem.renderer());
+}
+
+static void appendDisplayItem(PaintList& list, HashSet<const RenderObject*>& renderers, WTF::PassOwnPtr<DisplayItem> displayItem)
+{
+    if (RenderObject* renderer = displayItem->renderer())
+        renderers.add(renderer);
+    list.append(displayItem);
 }
 
 // Update the existing paintList by removing invalidated entries, updating repainted existing ones, and
 // appending new items.
 //
 // The algorithm should be O(|existing paint list| + |newly painted list|). By using the ordering
 // implied by the existing paint list, extra treewalks are avoided.
 void ViewDisplayList::updatePaintList()
 {
-    notImplemented();
+    PaintList updatedList;
+    HashSet<const RenderObject*> updatedRenderers;
+
+    PaintList::iterator currentListIt = m_paintList.begin();
+    PaintList::iterator paintListEnd = m_paintList.end();
+    for (PaintList::iterator newIt = m_newPaints.begin(); newIt != m_newPaints.end(); ++newIt) {
+        PaintList::iterator repaintIt = findRepaintWithoutInvalidation(currentListIt, **newIt);
+        if (repaintIt != paintListEnd) {
+            // Copy all of the non-invalidated existing chunks over until we hit the repainted chunk.
+            for (; currentListIt != repaintIt; ++currentListIt) {
+                DisplayItem& displayItem = **currentListIt;
+                if (!wasInvalidated(displayItem))
+                    appendDisplayItem(updatedList, updatedRenderers, currentListIt->release());
+            }
+            currentListIt++;
+        }
+        // Copy over the new paint.
+        appendDisplayItem(updatedList, updatedRenderers, newIt->release());
+    }
+
+    // Copy over any remaining paints that were not invalidated.
+    for (; currentListIt != paintListEnd; ++currentListIt) {
+        if (!wasInvalidated(**currentListIt))
+            appendDisplayItem(updatedList, updatedRenderers, currentListIt->release());
+    }
+
+    m_invalidated.clear();
+    m_newPaints.clear();
+    m_paintList.clear();
+    m_paintListRenderers.clear();
+    m_paintListRenderers.swap(updatedRenderers);
+    m_paintList.swap(updatedList);
 }
 
 #ifndef NDEBUG
 WTF::String DisplayItem::typeAsDebugString(DisplayItem::Type type)
 {
     switch (type) {
     case DisplayItem::DrawingPaintPhaseBlockBackground: return "DrawingPaintPhaseBlockBackground";
     case DisplayItem::DrawingPaintPhaseChildBlockBackground: return "DrawingPaintPhaseChildBlockBackground";
     case DisplayItem::DrawingPaintPhaseChildBlockBackgrounds: return "DrawingPaintPhaseChildBlockBackgrounds";
     case DisplayItem::DrawingPaintPhaseFloat: return "DrawingPaintPhaseFloat";
@@ skipping 52 matching lines @@
 }
 
 void ViewDisplayList::showDebugData() const
 {
     fprintf(stderr, "paint list: [%s]\n", paintListAsDebugString(m_paintList).utf8().data());
     fprintf(stderr, "new paints: [%s]\n", paintListAsDebugString(m_newPaints).utf8().data());
 }
 #endif
 
 } // namespace blink