[SPv2] Rasterization invalidation

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"
@@ skipping 33 matching lines @@
 
     size_t cachedItem = findCachedItem(DisplayItem::Id(client, type));
     if (cachedItem == kNotFound) {
         NOTREACHED();
         return false;
     }
 
     ++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.
     if (m_nextItemToMatch > m_nextItemToIndex)
         m_nextItemToIndex = m_nextItemToMatch;
 
 #if DCHECK_IS_ON()
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled()) {
         if (!isCheckingUnderInvalidation()) {
             m_underInvalidationCheckingBegin = cachedItem;
@@ skipping 61 matching lines @@
     return lastDisplayItem.isBegin() && !lastDisplayItem.drawsContent();
 }
 
 void PaintController::removeLastDisplayItem()
 {
     if (m_newDisplayItemList.isEmpty())
         return;
 
 #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))
             indices.removeLast();
     }
 
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled() && isCheckingUnderInvalidation()) {
         if (m_skippedProbableUnderInvalidationCount) {
             --m_skippedProbableUnderInvalidationCount;
         } else {
             DCHECK(m_underInvalidationCheckingBegin);
             --m_underInvalidationCheckingBegin;
         }
     }
 #endif
     m_newDisplayItemList.removeLast();
 
     if (RuntimeEnabledFeatures::slimmingPaintV2Enabled())
         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)
+void PaintController::processNewItem(DisplayItem& displayItem, NewItemSource newItemSource)
 {
     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::Subsequence) {
             m_currentSubsequenceClients.append(&displayItem.client());
         } else if (displayItem.getType() == DisplayItem::EndSubsequence) {
             CHECK(m_currentSubsequenceClients.last() == &displayItem.client());
             m_currentSubsequenceClients.removeLast();
         }
     }
 #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.
     if (m_newDisplayItemList.size() >= 2 && displayItem.isEnd()) {
         const auto& beginDisplayItem = m_newDisplayItemList[m_newDisplayItemList.size() - 2];
         if (beginDisplayItem.isBegin() && beginDisplayItem.getType() != DisplayItem::Subsequence && !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));
 #endif
         NOTREACHED();
     }
     addItemToIndexIfNeeded(displayItem, m_newDisplayItemList.size() - 1, m_newDisplayItemIndicesByClient);
 
     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)
 {
     m_newPaintChunks.updateCurrentPaintChunkProperties(id, newProperties);
 }
 
 const PaintChunkProperties& PaintController::currentPaintChunkProperties() const
 {
     return m_newPaintChunks.currentPaintChunkProperties();
@@ skipping 10 matching lines @@
 bool PaintController::clientCacheIsValid(const DisplayItemClient& client) const
 {
 #if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
     CHECK(client.isAlive());
 #endif
     if (isSkippingCache())
         return false;
     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;
 
     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 (id == existingItem.getId())
             return index;
     }
 
     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);
 }
 
 size_t PaintController::findCachedItem(const DisplayItem::Id& id)
 {
     DCHECK(clientCacheIsValid(id.client));
 
     // Try to find the item sequentially first. This is fast if the current list and the new list are in
@@ skipping 87 matching lines @@
 #if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
         CHECK(cachedItem->client().isAlive());
 #endif
         ++m_numCachedNewItems;
         bool metEndSubsequence = cachedItem->getId() == endSubsequenceId;
         if (!DCHECK_IS_ON() || !RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled()) {
             if (RuntimeEnabledFeatures::slimmingPaintV2Enabled() && cachedItemIndex == cachedChunk->endIndex) {
                 ++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));
         }
 
         ++cachedItemIndex;
         if (metEndSubsequence)
             break;
 
         // We should always be able to find the EndSubsequence display item.
         DCHECK(cachedItemIndex < m_currentPaintArtifact.getDisplayItemList().size());
@@ skipping 12 matching lines @@
 {
     LayoutRect visualRect = displayItem.client().visualRect();
     visualRect.move(-offsetFromLayoutObject);
     return enclosingIntRect(visualRect);
 }
 
 void PaintController::resetCurrentListIndices()
 {
     m_nextItemToMatch = 0;
     m_nextItemToIndex = 0;
+    m_nextChunkToMatch = 0;
 #if DCHECK_IS_ON()
     m_underInvalidationCheckingBegin = 0;
     m_underInvalidationCheckingEnd = 0;
     m_skippedProbableUnderInvalidationCount = 0;
 #endif
 }
 
 void PaintController::commitNewDisplayItems(const LayoutSize& offsetFromLayoutObject)
 {
     TRACE_EVENT2("blink,benchmark", "PaintController::commitNewDisplayItems",
         "current_display_list_size", (int)m_currentPaintArtifact.getDisplayItemList().size(),
         "num_non_cached_new_items", (int)m_newDisplayItemList.size() - m_numCachedNewItems);
     m_numCachedNewItems = 0;
 
     // These data structures are used during painting only.
     DCHECK(!isSkippingCache());
 #if DCHECK_IS_ON()
     m_newDisplayItemIndicesByClient.clear();
 #endif
 
+    if (RuntimeEnabledFeatures::slimmingPaintV2Enabled() && !m_newDisplayItemList.isEmpty())
+        generateChunkRasterInvalidationRects(m_newPaintChunks.lastChunk());
+
     SkPictureGpuAnalyzer gpuAnalyzer;
 
     m_currentCacheGeneration = DisplayItemClient::CacheGenerationOrInvalidationReason::next();
     Vector<const DisplayItemClient*> skippedCacheClients;
     for (const auto& item : m_newDisplayItemList) {
         // No reason to continue the analysis once we have a veto.
         if (gpuAnalyzer.suitableForGpuRasterization())
             item.analyzeForGpuRasterization(gpuAnalyzer);
 
         // TODO(wkorman): Only compute and append visual rect for drawings.
@@ skipping 10 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();
 
     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 37 matching lines @@
 
 void PaintController::appendDebugDrawingAfterCommit(const DisplayItemClient& displayItemClient, PassRefPtr<SkPicture> picture, const LayoutSize& offsetFromLayoutObject)
 {
     DCHECK(m_newDisplayItemList.isEmpty());
     DrawingDisplayItem& displayItem = m_currentPaintArtifact.getDisplayItemList().allocateAndConstruct<DrawingDisplayItem>(displayItemClient, DisplayItem::DebugDrawing, 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)
+        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
 {
     LOG(ERROR) << m_underInvalidationMessagePrefix << " " << reason;
 #ifndef NDEBUG
     LOG(ERROR) << "New display item: " << newItem.asDebugString();
     LOG(ERROR) << "Old display item: " << (oldItem ? oldItem->asDebugString() : "None");
 #else
     LOG(ERROR) << "Run debug build to get more details.";
@@ skipping 12 matching lines @@
 
 void PaintController::checkUnderInvalidation()
 {
     DCHECK(RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled());
 
     if (!isCheckingUnderInvalidation())
         return;
 
     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) {
         if (newItem.isBegin()) {
             // Temporarily skip mismatching begin display item which may be removed when we remove a no-op pair.
             ++m_skippedProbableUnderInvalidationCount;
             return;
         }
         if (newItem.isDrawing() && m_skippedProbableUnderInvalidationCount == 1) {
             DCHECK_GE(m_newDisplayItemList.size(), 2u);
             if (m_newDisplayItemList[m_newDisplayItemList.size() - 2].getType() == DisplayItem::BeginCompositing) {
                 // This might be a drawing item between a pair of begin/end compositing display items that will be folded
                 // into a single drawing display item.
                 ++m_skippedProbableUnderInvalidationCount;
                 return;
             }
         }
     }
 
     if (m_skippedProbableUnderInvalidationCount || !oldAndNewEqual) {
         // If we ever skipped reporting any under-invalidations, report the earliest one.
         showUnderInvalidationError("under-invalidation: display item changed",
             m_newDisplayItemList[m_newDisplayItemList.size() - m_skippedProbableUnderInvalidationCount - 1],
             &m_currentPaintArtifact.getDisplayItemList()[m_underInvalidationCheckingBegin]);
         NOTREACHED();
     }
 
+    // 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);
+
     ++m_underInvalidationCheckingBegin;
 }
 
 #endif // DCHECK_IS_ON()
 
 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));
 #ifndef NDEBUG
         displayItem.dumpPropertiesAsDebugString(stringBuilder);
 #else
         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");
+            do {
+#if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
+                if (!displayItem.client().isAlive()) {
+                    stringBuilder.append(", clientIsAlive: false");
+                    break;
+                }
+#endif
+                stringBuilder.append(", cacheIsValid: ");
+                stringBuilder.append(clientCacheIsValid(displayItem.client()) ? "true" : "false");
+            } while (false);
         }
         if (list.hasVisualRect(i)) {
             IntRect visualRect = list.visualRect(i);
             stringBuilder.append(String::format(", visualRect: [%d,%d %dx%d]",
                 visualRect.x(), visualRect.y(),
                 visualRect.width(), visualRect.height()));
         }
         stringBuilder.append('}');
     }
     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