Raster display item lists via a visual rect RTree.

third_party/WebKit/Source/platform/graphics/paint/PaintController.cpp

Index: third_party/WebKit/Source/platform/graphics/paint/PaintController.cpp
diff --git a/third_party/WebKit/Source/platform/graphics/paint/PaintController.cpp b/third_party/WebKit/Source/platform/graphics/paint/PaintController.cpp
index 6f06a7f0462ba12ac4baec6f5359d78254bfdac0..35da20f0bc8b12ae812b6a5ed1ac9dcf397cabc7 100644
--- a/third_party/WebKit/Source/platform/graphics/paint/PaintController.cpp
+++ b/third_party/WebKit/Source/platform/graphics/paint/PaintController.cpp
@@ -8,6 +8,7 @@
 #include "platform/NotImplemented.h"
 #include "platform/TraceEvent.h"
 #include "platform/graphics/GraphicsLayer.h"
+#include "platform/graphics/paint/DisplayItemClient.h"
 #include "platform/graphics/paint/DrawingDisplayItem.h"
 
 #ifndef NDEBUG
@@ -121,9 +122,10 @@ void PaintController::invalidate(const DisplayItemClientWrapper& client, PaintIn
 {
     invalidateClient(client);
 
-    if (visualRect) {
-        // TODO(wkorman): cache visualRect for the client.
-    }
+    if (!visualRect)
+        return;
+
+    m_displayItemInvalidationRects.add(client.displayItemClient(), *visualRect);
 }
 
 void PaintController::invalidateClient(const DisplayItemClientWrapper& client)
@@ -281,6 +283,15 @@ void PaintController::commitNewDisplayItems()
         "current_display_list_size", (int)m_currentPaintArtifact.displayItemList().size(),
         "num_non_cached_new_items", (int)m_newDisplayItemList.size() - m_numCachedItems);
 
+    // showDebugData();
+
+    // TODO(wkorman): Remove entries from m_DisplayItemInvalidationRects for which their display items are no longer
+    // present in the display item list.
+    fprintf(stderr, "PaintController::commitNewDisplayItems [currentItems=%d, newItems=%d, invalidationRects=%d].\n",
+        (int)m_currentPaintArtifact.displayItemList().size(),
+        (int)m_newDisplayItemList.size(),
+        m_displayItemInvalidationRects.size());
+
     if (RuntimeEnabledFeatures::slimmingPaintSynchronizedPaintingEnabled()
         && !m_newDisplayItemList.isEmpty()
         && m_newDisplayItemList.last().type() == DisplayItem::CachedDisplayItemList) {
@@ -326,7 +337,7 @@ void PaintController::commitNewDisplayItems()
     // out-of-order CachedDisplayItems occur, we only traverse at most once over m_currentDisplayItems
     // looking for potential matches. Thus we can ensure that the algorithm runs in linear time.
     OutOfOrderIndexContext outOfOrderIndexContext(m_currentPaintArtifact.displayItemList().begin());
-
+    HashSet<DisplayItemClient> allDisplayItemClients;
     // TODO(jbroman): Consider revisiting this heuristic.
     DisplayItemList updatedList(std::max(m_currentPaintArtifact.displayItemList().usedCapacityInBytes(), m_newDisplayItemList.usedCapacityInBytes()));
     Vector<PaintChunk> updatedPaintChunks;
@@ -363,6 +374,9 @@ void PaintController::commitNewDisplayItems()
                 checkUnderInvalidation(newIt, temp);
             }
 #endif
+
+            allDisplayItemClients.add(currentIt->client());
+
             if (newDisplayItem.isCachedDrawing()) {
                 updatedList.appendByMoving(*currentIt);
                 ++currentIt;
@@ -377,6 +391,13 @@ void PaintController::commitNewDisplayItems()
                 || !clientCacheIsValid(newDisplayItem.client())
                 || (RuntimeEnabledFeatures::slimmingPaintOffsetCachingEnabled() && paintOffsetWasInvalidated(newDisplayItem.client())));
 
+            if (newDisplayItem.client()) {
+                allDisplayItemClients.add(newDisplayItem.client());
+            } else {
+                // TODO(wkorman): Is this normal/expected as part of delete optimization?
+                fprintf(stderr, "Null DisplayItemClient: %s\n", newDisplayItem.asDebugString().ascii().data());
+            }
+
             updatedList.appendByMoving(*newIt);
 
             if (isSynchronized)
@@ -387,6 +408,24 @@ void PaintController::commitNewDisplayItems()
             outOfOrderIndexContext.nextItemToIndex = currentIt;
     }
 
+    // TODO(wkorman): Rework this to remove through iteration directly.
+    int staleRemoveCount = 0;
+    Vector<DisplayItemClient> staleClients;
+    for (DisplayItemClient client : m_displayItemInvalidationRects.keys()) {
+        if (!allDisplayItemClients.contains(client)) {
+            staleRemoveCount++;
+            staleClients.append(client);
+            IntRect visualRect = m_displayItemInvalidationRects.get(client);
+            fprintf(stderr, "Removing stale invalidation rect [rect=(%d, %d, %d, %d)].\n",
+                visualRect.x(), visualRect.y(), visualRect.width(), visualRect.height());
+        }
+    }
+    m_displayItemInvalidationRects.removeAll(staleClients);
+    fprintf(stderr, "Cleaned invalidation rects [newItemClientCount=%d, invalidationRectCount=%d, staleRemoveCount=%d].\n",
+        allDisplayItemClients.size(),
+        m_displayItemInvalidationRects.size(),
+        staleRemoveCount);
+
 #if ENABLE(ASSERT)
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled())
         checkNoRemainingCachedDisplayItems();