Raster display item lists via a visual rect RTree.

third_party/WebKit/Source/platform/graphics/paint/PaintController.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 "platform/graphics/paint/PaintController.h"
 
 #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
 #include "platform/graphics/LoggingCanvas.h"
 #include "wtf/text/StringBuilder.h"
 #include <stdio.h>
 #endif
 
 namespace blink {
 
@@ skipping 93 matching lines @@
 void PaintController::endScope()
 {
     m_scopeStack.removeLast();
     endSkippingCache();
 }
 
 void PaintController::invalidate(const DisplayItemClientWrapper& client, PaintInvalidationReason paintInvalidationReason, const IntRect* visualRect)
 {
     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)
 {
 #if ENABLE(ASSERT)
     // Slimming paint v1 CompositedLayerMapping may invalidate client on extra layers.
     if (RuntimeEnabledFeatures::slimmingPaintV2Enabled() || clientCacheIsValid(client.displayItemClient()))
         m_invalidations.append(client.debugName());
 #endif
 
@@ skipping 137 matching lines @@
 // The algorithm is O(|m_currentDisplayItemList| + |m_newDisplayItemList|).
 // Coefficients are related to the ratio of out-of-order CachedDisplayItems
 // and the average number of (Drawing|Subsequence)DisplayItems per client.
 //
 void PaintController::commitNewDisplayItems()
 {
     TRACE_EVENT2("blink,benchmark", "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) {
         // The whole display item list is cached.
         ASSERT(m_newDisplayItemList.size() == 1);
         ASSERT(m_invalidations.isEmpty());
         ASSERT(m_clientsCheckedPaintInvalidation.isEmpty());
         m_newDisplayItemList.clear();
         m_newPaintChunks.clear();
         return;
@@ skipping 25 matching lines @@
     }
 
     updateValidlyCachedClientsIfNeeded();
 
     // Stores indices to valid DrawingDisplayItems in m_currentDisplayItems that have not been matched
     // by CachedDisplayItems during synchronized matching. The indexed items will be matched
     // by later out-of-order CachedDisplayItems in m_newDisplayItemList. This ensures that when
     // 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;
     DisplayItemList::iterator currentIt = m_currentPaintArtifact.displayItemList().begin();
     DisplayItemList::iterator currentEnd = m_currentPaintArtifact.displayItemList().end();
     for (DisplayItemList::iterator newIt = m_newDisplayItemList.begin(); newIt != m_newDisplayItemList.end(); ++newIt) {
         const DisplayItem& newDisplayItem = *newIt;
         const DisplayItem::Id newDisplayItemId = newDisplayItem.nonCachedId();
         bool newDisplayItemHasCachedType = newDisplayItem.type() != newDisplayItemId.type;
 
@@ skipping 16 matching lines @@
                     // In this case, attempt to recover rather than crashing or bailing on display of the rest of the display list.
                     continue;
                 }
             }
 #if ENABLE(ASSERT)
             if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled()) {
                 DisplayItemList::iterator temp = currentIt;
                 checkUnderInvalidation(newIt, temp);
             }
 #endif
+
+            allDisplayItemClients.add(currentIt->client());
+
             if (newDisplayItem.isCachedDrawing()) {
                 updatedList.appendByMoving(*currentIt);
                 ++currentIt;
             } else {
                 ASSERT(newDisplayItem.type() == DisplayItem::CachedSubsequence);
                 copyCachedSubsequence(currentIt, updatedList);
                 ASSERT(updatedList.last().type() == DisplayItem::EndSubsequence);
             }
         } else {
             ASSERT(!newDisplayItem.isDrawing()
                 || newDisplayItem.skippedCache()
                 || !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)
                 ++currentIt;
         }
         // Items before currentIt should have been copied so we don't need to index them.
         if (currentIt - outOfOrderIndexContext.nextItemToIndex > 0)
             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();
 #endif // ENABLE(ASSERT)
 
     // TODO(jbroman): When subsequence caching applies to SPv2, we'll need to
     // merge the paint chunks as well.
     m_currentPaintArtifact.displayItemList().swap(updatedList);
     m_currentPaintArtifact.paintChunks() = m_newPaintChunks.releasePaintChunks();
 
@@ skipping 169 matching lines @@
 
 void PaintController::showDebugData() const
 {
     WTFLogAlways("current display item list: [%s]\n", displayItemListAsDebugString(m_currentPaintArtifact.displayItemList()).utf8().data());
     WTFLogAlways("new display item list: [%s]\n", displayItemListAsDebugString(m_newDisplayItemList).utf8().data());
 }
 
 #endif // ifndef NDEBUG
 
 } // namespace blink