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 780aff5b9c6082ee6bb9743fff11b2bb8152d861..eada499b53a868838e3d9faee750f688b9b9389e 100644
--- a/Source/core/paint/ViewDisplayList.cpp
+++ b/Source/core/paint/ViewDisplayList.cpp
@@ -20,7 +20,7 @@ const PaintList& ViewDisplayList::paintList()
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
 
     updatePaintList();
-    return m_newPaints;
+    return m_paintList;
 }
 
 void ViewDisplayList::add(WTF::PassOwnPtr<DisplayItem> displayItem)
@@ -35,10 +35,38 @@ void ViewDisplayList::invalidate(const RenderObject* renderer)
     m_invalidated.add(renderer);
 }
 
-bool ViewDisplayList::isRepaint(PaintList::iterator begin, const DisplayItem& displayItem)
+PaintList::iterator ViewDisplayList::wasUninvalidatedRepaint(PaintList::iterator begin, const DisplayItem& displayItem)

[leviw_travelin_and_unemployed, 2014/10/31 19:10:02]

UninvalidatedRepaint? Let's come up with a better name.

wasRepaintWithoutInvalidation?

It's also weird that this function call sounds like a boolean question, but
returns an iterator answer.

[pdr., 2014/10/31 20:37:56]

Good catch. Went with findNotUnDeRepaintWithoutUnNotWithDeInvalidation.

 {
-    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());

[leviw_travelin_and_unemployed, 2014/10/31 19:10:02]

I wonder if this hash lookup won't get expensive...

[leviw_travelin_and_unemployed, 2014/10/31 20:26:55]

To be clear, I don't think we should take it away now, but we use bits on
RenderObjects that track invalidation in the current RACUN world to avoid such
things. Perhaps we could re-use them.

[pdr., 2014/10/31 20:37:56]

We should be able to store both this lookup and the repaint lookup as two bools
on renderobject, removing all lookups.

+}
+
+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
@@ -48,7 +76,39 @@ 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) {
+        DisplayItem& repaintedDisplayItem = **newIt;
+        PaintList::iterator repaintIt = wasUninvalidatedRepaint(currentListIt, repaintedDisplayItem);
+        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