First implementation of the paint slimming update algorithm

Source/core/paint/ViewDisplayList.cpp

Index: Source/core/paint/ViewDisplayList.cpp
diff --git a/Source/core/paint/ViewDisplayList.cpp b/Source/core/paint/ViewDisplayList.cpp
index 4e64ec228643a6335bab7769fc9e846113cb0b48..d5164659dd0978b02a9d0182917c6f81f3a7be96 100644
--- a/Source/core/paint/ViewDisplayList.cpp
+++ b/Source/core/paint/ViewDisplayList.cpp
@@ -24,7 +24,7 @@ const PaintList& ViewDisplayList::paintList()
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
 
     updatePaintList();
-    return m_newPaints;
+    return m_paintList;
 }
 
 void ViewDisplayList::add(WTF::PassOwnPtr<DisplayItem> displayItem)
@@ -39,10 +39,38 @@ void ViewDisplayList::invalidate(const RenderObject* renderer)
     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
@@ -52,7 +80,38 @@ bool ViewDisplayList::isRepaint(PaintList::iterator begin, const DisplayItem& di
 // 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