[SPv2] Defer decision of raster invalidation after paint for changes z-index, transform, etc.

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 "platform/graphics/paint/PaintController.h"
 
 #include "platform/TraceEvent.h"
 #include "platform/graphics/GraphicsLayer.h"
 #include "platform/graphics/paint/DrawingDisplayItem.h"
 #include "third_party/skia/include/core/SkPictureAnalyzer.h"
+#include "wtf/AutoReset.h"
 #include "wtf/text/StringBuilder.h"
 
 #ifndef NDEBUG
 #include "platform/graphics/LoggingCanvas.h"
 #include <stdio.h>
 #endif
 
 namespace blink {
 
 const PaintArtifact& PaintController::paintArtifact() const
@@ skipping 21 matching lines @@
 
     size_t cachedItem = findCachedItem(DisplayItem::Id(client, type));
     if (cachedItem == kNotFound) {
         NOTREACHED();
         return false;
     }
 
     ++m_numCachedNewItems;
     ensureNewDisplayItemListInitialCapacity();
     if (!RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled())
-        processNewItem(m_newDisplayItemList.appendByMoving(m_currentPaintArtifact.getDisplayItemList()[cachedItem]), FromCachedItem);
+        processNewItem(moveItemFromCurrentListToNewList(cachedItem));
 
     m_nextItemToMatch = cachedItem + 1;
     // Items before m_nextItemToMatch have been copied so we don't need to index them.
     if (m_nextItemToMatch > m_nextItemToIndex)
         m_nextItemToIndex = m_nextItemToMatch;
 
     if (RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled()) {
         if (!isCheckingUnderInvalidation()) {
             m_underInvalidationCheckingBegin = cachedItem;
             m_underInvalidationCheckingEnd = cachedItem + 1;
@@ skipping 84 matching lines @@
         m_newPaintChunks.decrementDisplayItemIndex();
 }
 
 const DisplayItem* PaintController::lastDisplayItem(unsigned offset)
 {
     if (offset < m_newDisplayItemList.size())
         return &m_newDisplayItemList[m_newDisplayItemList.size() - offset - 1];
     return nullptr;
 }
 
-void PaintController::processNewItem(DisplayItem& displayItem, NewItemSource newItemSource)
+void PaintController::processNewItem(DisplayItem& displayItem)
 {
     DCHECK(!m_constructionDisabled);
 
 #if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
     if (!isSkippingCache()) {
         if (displayItem.isCacheable()) {
             // Mark the client shouldKeepAlive under this PaintController.
             // The status will end after the new display items are committed.
             displayItem.client().beginShouldKeepAlive(this);
 
             if (!m_currentSubsequenceClients.isEmpty()) {
                 // Mark the client shouldKeepAlive under the current subsequence.
                 // The status will end when the subsequence owner is invalidated or deleted.
                 displayItem.client().beginShouldKeepAlive(m_currentSubsequenceClients.last());
             }
         }
 
         if (displayItem.getType() == DisplayItem::kSubsequence) {
             m_currentSubsequenceClients.append(&displayItem.client());
         } else if (displayItem.getType() == DisplayItem::kEndSubsequence) {
             CHECK(m_currentSubsequenceClients.last() == &displayItem.client());
             m_currentSubsequenceClients.removeLast();
         }
     }
 #endif
 
-    if (isSkippingCache()) {
-        DCHECK(newItemSource == NewPainting);
+    if (isSkippingCache())
         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.
     if (m_newDisplayItemList.size() >= 2 && displayItem.isEnd()) {
         const auto& beginDisplayItem = m_newDisplayItemList[m_newDisplayItemList.size() - 2];
         if (beginDisplayItem.isBegin() && beginDisplayItem.getType() != DisplayItem::kSubsequence && !beginDisplayItem.drawsContent())
             DCHECK(!displayItem.isEndAndPairedWith(beginDisplayItem.getType()));
     }
 
     size_t index = findMatchingItemFromIndex(displayItem.getId(), m_newDisplayItemIndicesByClient, m_newDisplayItemList);
     if (index != kNotFound) {
 #ifndef NDEBUG
         showDebugData();
-        WTFLogAlways("DisplayItem %s has duplicated id with previous %s (index=%d)\n",
-            displayItem.asDebugString().utf8().data(), m_newDisplayItemList[index].asDebugString().utf8().data(), static_cast<int>(index));
+        WTFLogAlways("DisplayItem %s has duplicated id with previous %s (index=%zu)\n",
+            displayItem.asDebugString().utf8().data(), m_newDisplayItemList[index].asDebugString().utf8().data(), index);
 #endif
         NOTREACHED();
     }
     addItemToIndexIfNeeded(displayItem, m_newDisplayItemList.size() - 1, m_newDisplayItemIndicesByClient);
 #endif // DCHECK_IS_ON()
 
     if (RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled())
         checkUnderInvalidation();
 }
 
+DisplayItem& PaintController::moveItemFromCurrentListToNewList(size_t index)
+{
+    m_itemsMovedIntoNewList.resize(m_currentPaintArtifact.getDisplayItemList().size());
+    m_itemsMovedIntoNewList[index] = m_newDisplayItemList.size();
+    return m_newDisplayItemList.appendByMoving(m_currentPaintArtifact.getDisplayItemList()[index]);
+}
+
 void PaintController::updateCurrentPaintChunkProperties(const PaintChunk::Id* id, const PaintChunkProperties& newProperties)
 {
     m_newPaintChunks.updateCurrentPaintChunkProperties(id, newProperties);
 }
 
 const PaintChunkProperties& PaintController::currentPaintChunkProperties() const
 {
     return m_newPaintChunks.currentPaintChunkProperties();
 }
 
@@ skipping 17 matching lines @@
 
 size_t PaintController::findMatchingItemFromIndex(const DisplayItem::Id& id, const IndicesByClientMap& displayItemIndicesByClient, const DisplayItemList& list)
 {
     IndicesByClientMap::const_iterator it = displayItemIndicesByClient.find(&id.client);
     if (it == displayItemIndicesByClient.end())
         return kNotFound;
 
     const Vector<size_t>& indices = it->value;
     for (size_t index : indices) {
         const DisplayItem& existingItem = list[index];
-        DCHECK(!existingItem.hasValidClient() || existingItem.client() == id.client);
+        if (!existingItem.hasValidClient())
+            continue;
+        DCHECK(existingItem.client() == id.client);
         if (id == existingItem.getId())
             return index;
     }
 
     return kNotFound;
 }
 
 void PaintController::addItemToIndexIfNeeded(const DisplayItem& displayItem, size_t index, IndicesByClientMap& displayItemIndicesByClient)
 {
     if (!displayItem.isCacheable())
@@ skipping 71 matching lines @@
     // In this case, the caller should fall back to repaint the display item.
     return kNotFound;
 }
 
 // Copies a cached subsequence from current list to the new list. On return,
 // |cachedItemIndex| points to the item after the EndSubsequence item of the subsequence.
 // When paintUnderInvaldiationCheckingEnabled() we'll not actually copy the subsequence,
 // but mark the begin and end of the subsequence for under-invalidation checking.
 void PaintController::copyCachedSubsequence(size_t& cachedItemIndex)
 {
+    AutoReset<size_t> subsequenceBeginIndex(&m_currentCachedSubsequenceBeginIndexInNewList, m_newDisplayItemList.size());
     DisplayItem* cachedItem = &m_currentPaintArtifact.getDisplayItemList()[cachedItemIndex];
     DCHECK(cachedItem->getType() == DisplayItem::kSubsequence);
 
     if (RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled()) {
         DCHECK(!isCheckingUnderInvalidation());
         m_underInvalidationCheckingBegin = cachedItemIndex;
         m_underInvalidationMessagePrefix = "(In cached subsequence of " + cachedItem->client().debugName() + ")";
     }
 
     DisplayItem::Id endSubsequenceId(cachedItem->client(), DisplayItem::kEndSubsequence);
     Vector<PaintChunk>::const_iterator cachedChunk;
     if (RuntimeEnabledFeatures::slimmingPaintV2Enabled()) {
         cachedChunk = m_currentPaintArtifact.findChunkByDisplayItemIndex(cachedItemIndex);
+        DCHECK(cachedChunk != m_currentPaintArtifact.paintChunks().end());
         updateCurrentPaintChunkProperties(cachedChunk->id ? &*cachedChunk->id : nullptr, cachedChunk->properties);
     } else {
         // This is to avoid compilation error about uninitialized variable on Windows.
         cachedChunk = m_currentPaintArtifact.paintChunks().begin();
     }
 
     while (true) {
         DCHECK(cachedItem->hasValidClient());
 #if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
         CHECK(cachedItem->client().isAlive());
 #endif
         ++m_numCachedNewItems;
         bool metEndSubsequence = cachedItem->getId() == endSubsequenceId;
         if (!RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled()) {
             if (RuntimeEnabledFeatures::slimmingPaintV2Enabled() && cachedItemIndex == cachedChunk->endIndex) {
                 ++cachedChunk;
+                DCHECK(cachedChunk != m_currentPaintArtifact.paintChunks().end());
                 updateCurrentPaintChunkProperties(cachedChunk->id ? &*cachedChunk->id : nullptr, cachedChunk->properties);
             }
-            processNewItem(m_newDisplayItemList.appendByMoving(*cachedItem), FromCachedSubsequence);
+            processNewItem(moveItemFromCurrentListToNewList(cachedItemIndex));
             if (RuntimeEnabledFeatures::slimmingPaintV2Enabled())
                 DCHECK((!m_newPaintChunks.lastChunk().id && !cachedChunk->id) || m_newPaintChunks.lastChunk().matches(*cachedChunk));
         }
 
         ++cachedItemIndex;
         if (metEndSubsequence)
             break;
 
         // We should always be able to find the EndSubsequence display item.
         DCHECK(cachedItemIndex < m_currentPaintArtifact.getDisplayItemList().size());
@@ skipping 63 matching lines @@
 
     for (auto* client : skippedCacheClients)
         client->setDisplayItemsUncached();
 
     // The new list will not be appended to again so we can release unused memory.
     m_newDisplayItemList.shrinkToFit();
     m_currentPaintArtifact = PaintArtifact(std::move(m_newDisplayItemList), m_newPaintChunks.releasePaintChunks(), gpuAnalyzer.suitableForGpuRasterization());
     resetCurrentListIndices();
     m_outOfOrderItemIndices.clear();
     m_outOfOrderChunkIndices.clear();
+    m_itemsMovedIntoNewList.clear();
 
     if (RuntimeEnabledFeatures::slimmingPaintV2Enabled()) {
         for (const auto& chunk : m_currentPaintArtifact.paintChunks()) {
             if (chunk.id && chunk.id->client.isJustCreated())
                 chunk.id->client.clearIsJustCreated();
         }
     }
 
     // We'll allocate the initial buffer when we start the next paint.
     m_newDisplayItemList = DisplayItemList(0);
@@ skipping 40 matching lines @@
     DCHECK(m_newDisplayItemList.isEmpty());
     DrawingDisplayItem& displayItem = m_currentPaintArtifact.getDisplayItemList().allocateAndConstruct<DrawingDisplayItem>(displayItemClient, DisplayItem::kDebugDrawing, std::move(picture));
     displayItem.setSkippedCache();
     // TODO(wkorman): Only compute and append visual rect for drawings.
     m_currentPaintArtifact.getDisplayItemList().appendVisualRect(visualRectForDisplayItem(displayItem, offsetFromLayoutObject));
 }
 
 void PaintController::generateChunkRasterInvalidationRects(PaintChunk& newChunk)
 {
     DCHECK(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
-    if (m_currentChunkIsFromCachedSubsequence)
+    if (newChunk.beginIndex >= m_currentCachedSubsequenceBeginIndexInNewList)
         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()) {
@@ skipping 26 matching lines @@
     }
 
     // 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*> invalidatedClientsInOldChunk;
+    size_t highestMovedToIndex = 0;
+    for (size_t oldIndex = oldChunk.beginIndex; oldIndex < oldChunk.endIndex; ++oldIndex) {
+        const DisplayItem& oldItem = m_currentPaintArtifact.getDisplayItemList()[oldIndex];
+        const DisplayItemClient* clientToInvalidate = nullptr;
+        if (!oldItem.hasValidClient()) {
+            size_t movedToIndex = m_itemsMovedIntoNewList[oldIndex];
+            if (m_newDisplayItemList[movedToIndex].drawsContent()) {
+                if (movedToIndex < newChunk.beginIndex || movedToIndex >= newChunk.endIndex) {
+                    // The item has been moved into another chunk, so need to invalidate it in the old chunk.
+                    clientToInvalidate = &m_newDisplayItemList[movedToIndex].client();
+                    // And invalidate in the new chunk into which the item was moved.
+                    PaintChunk& movedToChunk = m_newPaintChunks.findChunkByDisplayItemIndex(movedToIndex);
+                    movedToChunk.rasterInvalidationRects.append(clientToInvalidate->visualRect());
+                } else if (movedToIndex < highestMovedToIndex) {
+                    // The item has been moved behind other cached items, so need to invalidate the area
+                    // that is probably exposed by the item moved earlier.
+                    clientToInvalidate = &m_newDisplayItemList[movedToIndex].client();
+                } else {
+                    highestMovedToIndex = movedToIndex;
+                }
+            }
+        } else if (oldItem.drawsContent()) {
+            clientToInvalidate = &oldItem.client();
+        }
+        if (clientToInvalidate && invalidatedClientsInOldChunk.add(clientToInvalidate).isNewEntry) {
+            newChunk.rasterInvalidationRects.append(m_currentPaintArtifact.getDisplayItemList().visualRect(oldIndex));
+        }
     }
 
-    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()));
-            }
-        }
+    HashSet<const DisplayItemClient*> invalidatedClientsInNewChunk;
+    for (size_t newIndex = newChunk.beginIndex; newIndex < newChunk.endIndex; ++newIndex) {
+        const DisplayItem& newItem = m_newDisplayItemList[newIndex];
+        if (newItem.drawsContent() && !clientCacheIsValid(newItem.client()) && invalidatedClientsInNewChunk.add(&newItem.client()).isNewEntry)
+            newChunk.rasterInvalidationRects.append(newItem.client().visualRect());
     }
 }
 
 void PaintController::showUnderInvalidationError(const char* reason, const DisplayItem& newItem, const DisplayItem* oldItem) const
 {
     LOG(ERROR) << m_underInvalidationMessagePrefix << " " << reason;
 #ifndef NDEBUG
     LOG(ERROR) << "New display item: " << newItem.asDebugString();
     LOG(ERROR) << "Old display item: " << (oldItem ? oldItem->asDebugString() : "None");
 #else
@@ skipping 45 matching lines @@
         showUnderInvalidationError("under-invalidation: display item changed",
             m_newDisplayItemList[m_newDisplayItemList.size() - m_skippedProbableUnderInvalidationCount - 1],
             &m_currentPaintArtifact.getDisplayItemList()[m_underInvalidationCheckingBegin]);
         CHECK(false);
     }
 
     // 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.removeLast();
-    m_newDisplayItemList.appendByMoving(*oldItem);
+    moveItemFromCurrentListToNewList(oldItemIndex);
 
     ++m_underInvalidationCheckingBegin;
 }
 
 String PaintController::displayItemListAsDebugString(const DisplayItemList& list) const
 {
     StringBuilder stringBuilder;
     size_t i = 0;
     for (auto it = list.begin(); it != list.end(); ++it, ++i) {
         const DisplayItem& displayItem = *it;
         if (i)
             stringBuilder.append(",\n");
-        stringBuilder.append(String::format("{index: %d, ", (int)i));
+        stringBuilder.append(String::format("{index: %zu, ", i));
 #ifndef NDEBUG
         displayItem.dumpPropertiesAsDebugString(stringBuilder);
 #else
         stringBuilder.append(String::format("clientDebugName: %s", displayItem.client().debugName().ascii().data()));
 #endif
         if (displayItem.hasValidClient()) {
             do {
 #if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
                 if (!displayItem.client().isAlive()) {
                     stringBuilder.append(", clientIsAlive: false");
@@ skipping 15 matching lines @@
     return stringBuilder.toString();
 }
 
 void PaintController::showDebugData() const
 {
     WTFLogAlways("current display item list: [%s]\n", displayItemListAsDebugString(m_currentPaintArtifact.getDisplayItemList()).utf8().data());
     WTFLogAlways("new display item list: [%s]\n", displayItemListAsDebugString(m_newDisplayItemList).utf8().data());
 }
 
 } // namespace blink