[SPv2] Rasterization invalidation

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 cde9a3c99881117026576217ac7b733d00d121e9..d07ef20399335a8486e9295313d1f266e0e93617 100644
--- a/third_party/WebKit/Source/platform/graphics/paint/PaintController.cpp
+++ b/third_party/WebKit/Source/platform/graphics/paint/PaintController.cpp
@@ -51,7 +51,7 @@ bool PaintController::useCachedDrawingIfPossible(const DisplayItemClient& client
     ++m_numCachedNewItems;
     ensureNewDisplayItemListInitialCapacity();
     if (!DCHECK_IS_ON() || !RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled())
-        processNewItem(m_newDisplayItemList.appendByMoving(m_currentPaintArtifact.getDisplayItemList()[cachedItem]));
+        processNewItem(m_newDisplayItemList.appendByMoving(m_currentPaintArtifact.getDisplayItemList()[cachedItem]), FromCachedItem);
 
     m_nextItemToMatch = cachedItem + 1;
     // Items before m_nextItemToMatch have been copied so we don't need to index them.
@@ -133,7 +133,7 @@ void PaintController::removeLastDisplayItem()
 
 #if DCHECK_IS_ON()
     // Also remove the index pointing to the removed display item.
-    DisplayItemIndicesByClientMap::iterator it = m_newDisplayItemIndicesByClient.find(&m_newDisplayItemList.last().client());
+    IndicesByClientMap::iterator it = m_newDisplayItemIndicesByClient.find(&m_newDisplayItemList.last().client());
     if (it != m_newDisplayItemIndicesByClient.end()) {
         Vector<size_t>& indices = it->value;
         if (!indices.isEmpty() && indices.last() == (m_newDisplayItemList.size() - 1))
@@ -162,7 +162,7 @@ const DisplayItem* PaintController::lastDisplayItem(unsigned offset)
     return nullptr;
 }
 
-void PaintController::processNewItem(DisplayItem& displayItem)
+void PaintController::processNewItem(DisplayItem& displayItem, NewItemSource newItemSource)
 {
     DCHECK(!m_constructionDisabled);
 
@@ -189,8 +189,23 @@ void PaintController::processNewItem(DisplayItem& displayItem)
     }
 #endif
 
-    if (isSkippingCache())
+    if (isSkippingCache()) {
+        DCHECK(newItemSource == NewPainting);
         displayItem.setSkippedCache();
+    }
+
+    if (RuntimeEnabledFeatures::slimmingPaintV2Enabled()) {
+        if (newItemSource != FromCachedSubsequence)
+            m_currentChunkIsFromCachedSubsequence = false;
+
+        size_t lastChunkIndex = m_newPaintChunks.lastChunkIndex();
+        if (m_newPaintChunks.incrementDisplayItemIndex(displayItem)) {
+            DCHECK(lastChunkIndex != m_newPaintChunks.lastChunkIndex());
+            if (lastChunkIndex != kNotFound)
+                generateChunkRasterInvalidationRects(m_newPaintChunks.paintChunkAt(lastChunkIndex));
+            m_currentChunkIsFromCachedSubsequence = true;
+        }
+    }
 
 #if DCHECK_IS_ON()
     // Verify noop begin/end pairs have been removed.
@@ -214,9 +229,6 @@ void PaintController::processNewItem(DisplayItem& displayItem)
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled())
         checkUnderInvalidation();
 #endif // DCHECK_IS_ON()
-
-    if (RuntimeEnabledFeatures::slimmingPaintV2Enabled())
-        m_newPaintChunks.incrementDisplayItemIndex(displayItem);
 }
 
 void PaintController::updateCurrentPaintChunkProperties(const PaintChunk::Id* id, const PaintChunkProperties& newProperties)
@@ -247,9 +259,9 @@ bool PaintController::clientCacheIsValid(const DisplayItemClient& client) const
     return client.displayItemsAreCached(m_currentCacheGeneration);
 }
 
-size_t PaintController::findMatchingItemFromIndex(const DisplayItem::Id& id, const DisplayItemIndicesByClientMap& displayItemIndicesByClient, const DisplayItemList& list)
+size_t PaintController::findMatchingItemFromIndex(const DisplayItem::Id& id, const IndicesByClientMap& displayItemIndicesByClient, const DisplayItemList& list)
 {
-    DisplayItemIndicesByClientMap::const_iterator it = displayItemIndicesByClient.find(&id.client);
+    IndicesByClientMap::const_iterator it = displayItemIndicesByClient.find(&id.client);
     if (it == displayItemIndicesByClient.end())
         return kNotFound;
 
@@ -264,12 +276,12 @@ size_t PaintController::findMatchingItemFromIndex(const DisplayItem::Id& id, con
     return kNotFound;
 }
 
-void PaintController::addItemToIndexIfNeeded(const DisplayItem& displayItem, size_t index, DisplayItemIndicesByClientMap& displayItemIndicesByClient)
+void PaintController::addItemToIndexIfNeeded(const DisplayItem& displayItem, size_t index, IndicesByClientMap& displayItemIndicesByClient)
 {
     if (!displayItem.isCacheable())
         return;
 
-    DisplayItemIndicesByClientMap::iterator it = displayItemIndicesByClient.find(&displayItem.client());
+    IndicesByClientMap::iterator it = displayItemIndicesByClient.find(&displayItem.client());
     Vector<size_t>& indices = it == displayItemIndicesByClient.end() ?
         displayItemIndicesByClient.add(&displayItem.client(), Vector<size_t>()).storedValue->value : it->value;
     indices.append(index);
@@ -377,7 +389,7 @@ void PaintController::copyCachedSubsequence(size_t& cachedItemIndex)
                 ++cachedChunk;
                 updateCurrentPaintChunkProperties(cachedChunk->id ? &*cachedChunk->id : nullptr, cachedChunk->properties);
             }
-            processNewItem(m_newDisplayItemList.appendByMoving(*cachedItem));
+            processNewItem(m_newDisplayItemList.appendByMoving(*cachedItem), FromCachedSubsequence);
             if (RuntimeEnabledFeatures::slimmingPaintV2Enabled())
                 DCHECK((!m_newPaintChunks.lastChunk().id && !cachedChunk->id) || m_newPaintChunks.lastChunk().matches(*cachedChunk));
         }
@@ -410,6 +422,7 @@ void PaintController::resetCurrentListIndices()
 {
     m_nextItemToMatch = 0;
     m_nextItemToIndex = 0;
+    m_nextChunkToMatch = 0;
 #if DCHECK_IS_ON()
     m_underInvalidationCheckingBegin = 0;
     m_underInvalidationCheckingEnd = 0;
@@ -430,6 +443,9 @@ void PaintController::commitNewDisplayItems(const LayoutSize& offsetFromLayoutOb
     m_newDisplayItemIndicesByClient.clear();
 #endif
 
+    if (RuntimeEnabledFeatures::slimmingPaintV2Enabled() && !m_newDisplayItemList.isEmpty())
+        generateChunkRasterInvalidationRects(m_newPaintChunks.lastChunk());
+
     SkPictureGpuAnalyzer gpuAnalyzer;
 
     m_currentCacheGeneration = DisplayItemClient::CacheGenerationOrInvalidationReason::next();
@@ -460,6 +476,7 @@ void PaintController::commitNewDisplayItems(const LayoutSize& offsetFromLayoutOb
     m_currentPaintArtifact = PaintArtifact(std::move(m_newDisplayItemList), m_newPaintChunks.releasePaintChunks(), gpuAnalyzer.suitableForGpuRasterization());
     resetCurrentListIndices();
     m_outOfOrderItemIndices.clear();
+    m_outOfOrderChunkIndices.clear();
 
     if (RuntimeEnabledFeatures::slimmingPaintV2Enabled()) {
         for (const auto& chunk : m_currentPaintArtifact.paintChunks()) {
@@ -517,6 +534,86 @@ void PaintController::appendDebugDrawingAfterCommit(const DisplayItemClient& dis
     m_currentPaintArtifact.getDisplayItemList().appendVisualRect(visualRectForDisplayItem(displayItem, offsetFromLayoutObject));
 }
 
+void PaintController::generateChunkRasterInvalidationRects(PaintChunk& newChunk)
+{
+    DCHECK(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
+    if (m_currentChunkIsFromCachedSubsequence)
+        return;
+
+    if (!newChunk.id) {
+        newChunk.rasterInvalidationRects.append(FloatRect(LayoutRect::infiniteIntRect()));
+        return;
+    }
+
+    // Try to match old chunk sequentially first.
+    const auto& oldChunks = m_currentPaintArtifact.paintChunks();
+    while (m_nextChunkToMatch < oldChunks.size()) {
+        const PaintChunk& oldChunk = oldChunks[m_nextChunkToMatch];
+        if (newChunk.matches(oldChunk)) {
+            generateChunkRasterInvalidationRectsComparingOldChunk(newChunk, oldChunk);
+            ++m_nextChunkToMatch;
+            return;
+        }
+
+        // Add skipped old chunks into the index.
+        if (oldChunk.id) {
+            auto it = m_outOfOrderChunkIndices.find(&oldChunk.id->client);
+            Vector<size_t>& indices = it == m_outOfOrderChunkIndices.end() ?
+                m_outOfOrderChunkIndices.add(&oldChunk.id->client, Vector<size_t>()).storedValue->value : it->value;
+            indices.append(m_nextChunkToMatch);
+        }
+        ++m_nextChunkToMatch;
+    }
+
+    // Sequential matching reaches the end. Find from the out-of-order index.
+    auto it = m_outOfOrderChunkIndices.find(&newChunk.id->client);
+    if (it != m_outOfOrderChunkIndices.end()) {
+        for (size_t i : it->value) {
+            if (newChunk.matches(oldChunks[i])) {
+                generateChunkRasterInvalidationRectsComparingOldChunk(newChunk, oldChunks[i]);
+                return;
+            }
+        }
+    }
+
+    // We reach here because the chunk is new.
+    newChunk.rasterInvalidationRects.append(FloatRect(LayoutRect::infiniteIntRect()));
+}
+
+void PaintController::generateChunkRasterInvalidationRectsComparingOldChunk(PaintChunk& newChunk, const PaintChunk& oldChunk)
+{
+    DCHECK(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
+
+    // TODO(wangxianzhu): Support raster invalidation for reordered display items without invalidating
+    // display item clients. Currently we invalidate display item clients ensuring raster invalidation.
+    // TODO(wangxianzhu): Handle PaintInvalidationIncremental.
+    // TODO(wangxianzhu): Optimize paint offset change.
+
+    // Maps from each client to the index of the first drawing-content display item of the client.
+    HashMap<const DisplayItemClient*, size_t> oldChunkClients;
+    for (size_t i = oldChunk.beginIndex; i < oldChunk.endIndex; ++i) {
+        const DisplayItem& oldItem = m_currentPaintArtifact.getDisplayItemList()[i];
+        // oldItem.hasValidClient() indicates that the item has not been copied as a cached item into
+        // m_newDislayItemList, so the item either disappeared or changed, and needs raster invalidation.
+        if (oldItem.hasValidClient() && oldItem.drawsContent() && oldChunkClients.add(&oldItem.client(), i).isNewEntry)
+            newChunk.rasterInvalidationRects.append(m_currentPaintArtifact.getDisplayItemList().visualRect(i));
+    }
+
+    HashSet<const DisplayItemClient*> newChunkClients;
+    for (size_t i = newChunk.beginIndex; i < newChunk.endIndex; ++i) {
+        const DisplayItem& newItem = m_newDisplayItemList[i];
+        if (newItem.drawsContent()) {
+            if (!clientCacheIsValid(newItem.client())) {
+                if (newChunkClients.add(&newItem.client()).isNewEntry)
+                    newChunk.rasterInvalidationRects.append(newItem.client().visualRect());
+            } else {
+                // The cached item was moved from the old chunk which should not contain any item of the client now.
+                DCHECK(!oldChunkClients.contains(&newItem.client()));
+            }
+        }
+    }
+}
+
 #if DCHECK_IS_ON()
 
 void PaintController::showUnderInvalidationError(const char* reason, const DisplayItem& newItem, const DisplayItem* oldItem) const
@@ -549,7 +646,7 @@ void PaintController::checkUnderInvalidation()
 
     const DisplayItem& newItem = m_newDisplayItemList.last();
     size_t oldItemIndex = m_underInvalidationCheckingBegin + m_skippedProbableUnderInvalidationCount;
-    const DisplayItem* oldItem = oldItemIndex < m_currentPaintArtifact.getDisplayItemList().size() ? &m_currentPaintArtifact.getDisplayItemList()[oldItemIndex] : nullptr;
+    DisplayItem* oldItem = oldItemIndex < m_currentPaintArtifact.getDisplayItemList().size() ? &m_currentPaintArtifact.getDisplayItemList()[oldItemIndex] : nullptr;
 
     bool oldAndNewEqual = oldItem && newItem.equals(*oldItem);
     if (!oldAndNewEqual) {
@@ -577,6 +674,10 @@ void PaintController::checkUnderInvalidation()
         NOTREACHED();
     }
 
+    // Align with the non-under-invalidation-checking path: move the cached item into m_newDisplayItemList.
+    m_newDisplayItemList.removeLast();

[chrishtr, 2016/08/26 20:01:49]

This part is new too, right? Why?

[Xianzhu, 2016/08/26 20:23:23]

This is required by the new
generateChunkRasterInvalidationRectsComparingOldChunk() in under-invalidation
checking mode: any display items left in the old chunk will be invalidated for
raster because cached display items have been moved into the new chunk, without
the need to check if they are changed in the new chunk.

[chrishtr, 2016/08/26 20:32:22]

I still don't get it. What exactly do these two lines achieve? Sorry to make you
spell it out, still not grokking.

[Xianzhu, 2016/08/26 20:53:49]

In normal mode, if a display item can use cache, we move the item from the old
paint list into the new list using appendByMoving. The movement empties the slot
in the old list. Then in
generateChunkRasterInvalidationRectsComparingOldChunk(), all remaining display
items in the old chunk will be for only disappeared or invalidated clients, so
we can simply invalidate raster of all these clients, without needing to compare
them to the items in the new list.

In under-invalidation checking mode, we force repaint of all display items even
if they can use cache to see if the newly painted display items really don't
change. These two lines remove the forced repainted item and move the cached
item from the old list into the new list, to meet the requirement of
generateChunkRasterInvalidationRectsComparingOldChunk().

Updated comments:

    // Discard the forced repainted display item and move the cached item into
m_newDisplayItemList.
    // This is to align with the non-under-invalidation-checking path to empty
the original cached slot,
    // leaving only disappeared or invalidated display items in the old list
after painting.

+    m_newDisplayItemList.appendByMoving(*oldItem);
+
     ++m_underInvalidationCheckingBegin;
 }
 
@@ -597,8 +698,12 @@ String PaintController::displayItemListAsDebugString(const DisplayItemList& list
         stringBuilder.append(String::format("clientDebugName: %s", displayItem.client().debugName().ascii().data()));
 #endif
         if (displayItem.hasValidClient()) {
-            stringBuilder.append(", cacheIsValid: ");
-            stringBuilder.append(clientCacheIsValid(displayItem.client()) ? "true" : "false");
+            if (displayItem.client().isAlive()) {
+                stringBuilder.append(", cacheIsValid: ");
+                stringBuilder.append(clientCacheIsValid(displayItem.client()) ? "true" : "false");
+            } else {
+                stringBuilder.append(", clientIsAlive: false");
+            }
         }
         if (list.hasVisualRect(i)) {
             IntRect visualRect = list.visualRect(i);