Avoid re-iterate out-of-order display items

Source/platform/graphics/paint/DisplayItemList.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/DisplayItemList.h"
 
 #include "platform/NotImplemented.h"
 #include "platform/RuntimeEnabledFeatures.h"
 #include "platform/TraceEvent.h"
@@ skipping 131 matching lines @@
 size_t DisplayItemList::findMatchingItemFromIndex(const DisplayItem::Id& id, const DisplayItemIndicesByClientMap& displayItemIndicesByClient, const DisplayItems& list)
 {
     DisplayItemIndicesByClientMap::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) {
         // TODO(pdr): elementAt is not cheap so this should be refactored (See crbug.com/505965).
         const DisplayItem& existingItem = list[index];
-        ASSERT(existingItem.ignoreFromDisplayList() || existingItem.client() == id.client);
-        if (!existingItem.ignoreFromDisplayList() && id.matches(existingItem))
+        ASSERT(!existingItem.isValid() || existingItem.client() == id.client);
+        if (existingItem.isValid() && id.matches(existingItem))
             return index;
     }
 
     return kNotFound;
 }
 
 void DisplayItemList::addItemToIndexIfNeeded(const DisplayItem& displayItem, size_t index, DisplayItemIndicesByClientMap& displayItemIndicesByClient)
 {
     if (!displayItem.isCacheable())
         return;
 
     DisplayItemIndicesByClientMap::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);
 }
 
-DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItem(DisplayItems::iterator currentIt, const DisplayItem::Id& id, DisplayItemIndicesByClientMap& displayItemIndicesByClient)
+struct DisplayItemList::OutOfOrderIndexContext {
+    OutOfOrderIndexContext(DisplayItems::iterator begin) : nextItemToIndex(begin) { }
+
+    DisplayItems::iterator nextItemToIndex;
+    DisplayItemIndicesByClientMap displayItemIndicesByClient;
+};
+
+DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItem(DisplayItems::iterator currentIt, const DisplayItem::Id& id, OutOfOrderIndexContext& context)
 {
     ASSERT(clientCacheIsValid(id.client));
 
-    size_t foundIndex = findMatchingItemFromIndex(id, displayItemIndicesByClient, m_currentDisplayItems);
+    // Skip indexing of copied items.
+    if (currentIt - context.nextItemToIndex > 0)
+        context.nextItemToIndex = currentIt;
+
+    size_t foundIndex = findMatchingItemFromIndex(id, context.displayItemIndicesByClient, m_currentDisplayItems);
     if (foundIndex != kNotFound)
         return m_currentDisplayItems.begin() + foundIndex;
 
-    return findOutOfOrderCachedItemForward(currentIt, id, displayItemIndicesByClient);
+    return findOutOfOrderCachedItemForward(id, context);
 }
 
 // Find forward for the item and index all skipped indexable items.
-DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItemForward(DisplayItems::iterator currentIt, const DisplayItem::Id& id, DisplayItemIndicesByClientMap& displayItemIndicesByClient)
+DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItemForward(const DisplayItem::Id& id, OutOfOrderIndexContext& context)
 {
     DisplayItems::iterator currentEnd = m_currentDisplayItems.end();
-    for (; currentIt != currentEnd; ++currentIt) {
-        const DisplayItem& item = *currentIt;
-        if (!item.ignoreFromDisplayList()
-            && item.isCacheable()
-            && m_validlyCachedClients.contains(item.client())) {
+    for (; context.nextItemToIndex != currentEnd; ++context.nextItemToIndex) {
+        const DisplayItem& item = *context.nextItemToIndex;
+        ASSERT(item.isValid());
+        if (item.isCacheable() && clientCacheIsValid(item.client())) {
             if (id.matches(item))
-                return currentIt;
+                return context.nextItemToIndex++;
 
-            addItemToIndexIfNeeded(item, currentIt - m_currentDisplayItems.begin(), displayItemIndicesByClient);
+            addItemToIndexIfNeeded(item, context.nextItemToIndex - m_currentDisplayItems.begin(), context.displayItemIndicesByClient);
         }
     }
     return currentEnd;
 }
 
 void DisplayItemList::copyCachedSubtree(DisplayItems::iterator& currentIt, DisplayItems& updatedList)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
     ASSERT(currentIt->isBeginSubtree());
     ASSERT(!currentIt->scope());
     DisplayItem::Id endSubtreeId(currentIt->client(), DisplayItem::beginSubtreeTypeToEndSubtreeType(currentIt->type()), 0);
-    while (true) {
-        updatedList.appendByMoving(*currentIt, currentIt->derivedSize());
-        if (endSubtreeId.matches(updatedList.last()))
-            break;
-        ++currentIt;
+    do {
         // We should always find the EndSubtree display item.
         ASSERT(currentIt != m_currentDisplayItems.end());
-    }
+        updatedList.appendByMoving(*currentIt, currentIt->derivedSize());
+        ++currentIt;
+    } while (!endSubtreeId.matches(updatedList.last()));
 }
 
 // Update the existing display items by removing invalidated entries, updating
 // repainted ones, and appending new items.
 // - For CachedDisplayItem, copy the corresponding cached DrawingDisplayItem;
 // - For SubtreeCachedDisplayItem, copy the cached display items between the
 //   corresponding BeginSubtreeDisplayItem and EndSubtreeDisplayItem (incl.);
 // - Otherwise, copy the new display item.
 //
 // The algorithm is O(|m_currentDisplayItems| + |m_newDisplayItems|).
@@ skipping 26 matching lines @@
         return;
     }
 
     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_newDisplayItems. 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.
-    DisplayItemIndicesByClientMap displayItemIndicesByClient;
+    OutOfOrderIndexContext outOfOrderIndexContext(m_currentDisplayItems.begin());
 
 #if ENABLE(ASSERT)
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled()) {
         // Under-invalidation checking requires a full index of m_currentDisplayItems.
         size_t i = 0;
         for (const auto& item : m_currentDisplayItems) {
-            addItemToIndexIfNeeded(item, i, displayItemIndicesByClient);
+            addItemToIndexIfNeeded(item, i, outOfOrderIndexContext.displayItemIndicesByClient);
             ++i;
         }
     }
 #endif // ENABLE(ASSERT)
 
     // TODO(jbroman): Consider revisiting this heuristic.
     DisplayItems updatedList(
         kMaximumDisplayItemSize,
         std::max(m_currentDisplayItems.usedCapacityInBytes(), m_newDisplayItems.usedCapacityInBytes()));
     DisplayItems::iterator currentIt = m_currentDisplayItems.begin();
     DisplayItems::iterator currentEnd = m_currentDisplayItems.end();
     for (DisplayItems::iterator newIt = m_newDisplayItems.begin(); newIt != m_newDisplayItems.end(); ++newIt) {
         const DisplayItem& newDisplayItem = *newIt;
         const DisplayItem::Id newDisplayItemId = newDisplayItem.nonCachedId();
         bool newDisplayItemHasCachedType = newDisplayItem.type() != newDisplayItemId.type;
 
-        bool isSynchronized = currentIt != currentEnd
-            && !currentIt->ignoreFromDisplayList()
-            && newDisplayItemId.matches(*currentIt);
+        bool isSynchronized = currentIt != currentEnd && newDisplayItemId.matches(*currentIt);
 
         if (newDisplayItemHasCachedType) {
             ASSERT(!RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled());
             ASSERT(newDisplayItem.isCached());
             ASSERT(clientCacheIsValid(newDisplayItem.client()));
             if (!isSynchronized) {
-                DisplayItems::iterator foundIt = findOutOfOrderCachedItem(currentIt, newDisplayItemId, displayItemIndicesByClient);
-                ASSERT(foundIt != currentIt);
+                DisplayItems::iterator foundIt = findOutOfOrderCachedItem(currentIt, newDisplayItemId, outOfOrderIndexContext);
 
                 if (foundIt == currentEnd) {
 #ifndef NDEBUG
                     showDebugData();
                     WTFLogAlways("%s not found in m_currentDisplayItems\n", newDisplayItem.asDebugString().utf8().data());
 #endif
                     ASSERT_NOT_REACHED();
 
                     // If foundIt == currentEnd, it means that we did not find the cached display item. This should be impossible, but may occur
                     // if there is a bug in the system, such as under-invalidation, incorrect cache checking or duplicate display ids. In this case,
                     // attempt to recover rather than crashing or bailing on display of the rest of the display list.
                     continue;
                 }
+
+                ASSERT(foundIt != currentIt); // because we are in 'if (!isSynchronized)'
                 currentIt = foundIt;
             }
 
             if (newDisplayItem.isCachedDrawing()) {
                 updatedList.appendByMoving(*currentIt, currentIt->derivedSize());
+                ++currentIt;
             } else {
                 ASSERT(newDisplayItem.isCachedSubtree());
                 copyCachedSubtree(currentIt, updatedList);
                 ASSERT(updatedList.last().isEndSubtree());
             }
         } else {
 #if ENABLE(ASSERT)
             if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled())
-                checkCachedDisplayItemIsUnchanged(newDisplayItem, displayItemIndicesByClient);
+                checkCachedDisplayItemIsUnchanged(newDisplayItem, outOfOrderIndexContext.displayItemIndicesByClient);
             else
                 ASSERT(!newDisplayItem.isDrawing() || newDisplayItem.skippedCache() || !clientCacheIsValid(newDisplayItem.client()));
 #endif // ENABLE(ASSERT)
             updatedList.appendByMoving(*newIt, newIt->derivedSize());
+
+            if (isSynchronized)
+                ++currentIt;
         }
-
-        if (isSynchronized)
-            ++currentIt;
     }
 
 #if ENABLE(ASSERT)
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled())
         checkNoRemainingCachedDisplayItems();
 #endif // ENABLE(ASSERT)
 
     m_newDisplayItems.clear();
     m_validlyCachedClientsDirty = true;
     m_currentDisplayItems.swap(updatedList);
@@ skipping 93 matching lines @@
     size_t index = findMatchingItemFromIndex(displayItem.nonCachedId(), displayItemIndicesByClient, m_currentDisplayItems);
     if (index == kNotFound) {
         showUnderInvalidationError("ERROR: under-invalidation: no cached display item", displayItem);
         ASSERT_NOT_REACHED();
         return;
     }
 
     DisplayItems::iterator foundItem = m_currentDisplayItems.begin() + index;
     RefPtr<const SkPicture> newPicture = static_cast<const DrawingDisplayItem&>(displayItem).picture();
     RefPtr<const SkPicture> oldPicture = static_cast<const DrawingDisplayItem&>(*foundItem).picture();
-    // Mark the display item as ignored so that we can check if there are any remaining cached display items after merging.
-    foundItem->setIgnoredFromDisplayList();
+    // Invalidate the display item so that we can check if there are any remaining cached display items after merging.
+    foundItem->clearClientForUnderInvalidationChecking();
 
     if (!newPicture && !oldPicture)
         return;
     if (newPicture && oldPicture) {
         switch (static_cast<const DrawingDisplayItem&>(displayItem).underInvalidationCheckingMode()) {
         case DrawingDisplayItem::CheckPicture:
             if (newPicture->approximateOpCount() == oldPicture->approximateOpCount()) {
                 SkDynamicMemoryWStream newPictureSerialized;
                 newPicture->serialize(&newPictureSerialized);
                 SkDynamicMemoryWStream oldPictureSerialized;
@@ skipping 35 matching lines @@
 #endif // NDEBUG
 
     ASSERT_NOT_REACHED();
 }
 
 void DisplayItemList::checkNoRemainingCachedDisplayItems()
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled());
 
     for (const auto& displayItem : m_currentDisplayItems) {
-        if (displayItem.ignoreFromDisplayList() || !displayItem.isDrawing() || !clientCacheIsValid(displayItem.client()))
+        if (!displayItem.isValid() || !displayItem.isDrawing() || !clientCacheIsValid(displayItem.client()))
             continue;
         showUnderInvalidationError("May be under-invalidation: no new display item", displayItem);
     }
 }
 
 #endif // ENABLE(ASSERT)
 
 #ifndef NDEBUG
 
 WTF::String DisplayItemList::displayItemsAsDebugString(const DisplayItems& 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");
-        if (displayItem.ignoreFromDisplayList()) {
+        if (!displayItem.isValid()) {
             stringBuilder.append("null");
             continue;
         }
         stringBuilder.append(String::format("{index: %d, ", (int)i));
         displayItem.dumpPropertiesAsDebugString(stringBuilder);
         stringBuilder.append(", cacheIsValid: ");
         stringBuilder.append(clientCacheIsValid(displayItem.client()) ? "true" : "false");
         stringBuilder.append('}');
     }
     return stringBuilder.toString();
 }
 
 void DisplayItemList::showDebugData() const
 {
     WTFLogAlways("current display items: [%s]\n", displayItemsAsDebugString(m_currentDisplayItems).utf8().data());
     WTFLogAlways("new display items: [%s]\n", displayItemsAsDebugString(m_newDisplayItems).utf8().data());
 }
 
 #endif // ifndef NDEBUG
 
 void DisplayItemList::replay(GraphicsContext& context)
 {
     TRACE_EVENT0("blink,benchmark", "DisplayItemList::replay");
     ASSERT(m_newDisplayItems.isEmpty());
     for (DisplayItem& displayItem : m_currentDisplayItems)
         displayItem.replay(context);
 }
 
 } // namespace blink