First version of new merge algorithm (not enabled yet)

Source/platform/graphics/paint/DisplayItemList.cpp

Index: Source/platform/graphics/paint/DisplayItemList.cpp
diff --git a/Source/platform/graphics/paint/DisplayItemList.cpp b/Source/platform/graphics/paint/DisplayItemList.cpp
index 654b7f0f91cdd8b22e890f7a4ffc863255fe0217..991aaaefda16870847ee868e4b24e7f243a4a27f 100644
--- a/Source/platform/graphics/paint/DisplayItemList.cpp
+++ b/Source/platform/graphics/paint/DisplayItemList.cpp
@@ -15,7 +15,7 @@
 
 namespace blink {
 
-const PaintList& DisplayItemList::paintList()
+const PaintList& DisplayItemList::paintList() const
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     ASSERT(m_newPaints.isEmpty());
@@ -25,12 +25,29 @@ const PaintList& DisplayItemList::paintList()
 void DisplayItemList::add(WTF::PassOwnPtr<DisplayItem> displayItem)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
+    if (displayItem->isEnd()) {
+        ASSERT(!m_newPaints.isEmpty());
+        if (m_newPaints.last()->isBegin()) {
+            ASSERT(displayItem->isEndAndPairedWith(*m_newPaints.last()));
+            // Remove empty pairs.
+            m_newPaints.removeLast();
+            return;
+        }
+    }
+#if ENABLE(ASSERT)
+    if (RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled()) {
+        ASSERT(!m_newPaintIds.contains(displayItem->id()));
+        m_newPaintIds.add(displayItem->id());
+    }
+#endif
     m_newPaints.append(displayItem);
 }
 
 void DisplayItemList::invalidate(DisplayItemClient client)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
+    // Can only be called during layout/paintInvalidation, not during painting.
+    ASSERT(m_newPaints.isEmpty());
     m_cachedClients.remove(client);
 }
 
@@ -41,6 +58,7 @@ void DisplayItemList::invalidateAll()
     ASSERT(m_newPaints.isEmpty());
     m_paintList.clear();
     m_cachedClients.clear();
+    m_displayItemIndexMap.clear();
 }
 
 bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
@@ -48,36 +66,58 @@ bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
     return RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled() && m_cachedClients.contains(client);
 }
 
-PaintList::iterator DisplayItemList::findNextMatchingCachedItem(PaintList::iterator begin, const DisplayItem& displayItem)
+size_t DisplayItemList::findDisplayItemById(const DisplayItem::Id& id) const
 {
-    PaintList::iterator end = m_paintList.end();
-
-    if (!clientCacheIsValid(displayItem.client()))
-        return end;
+    ASSERT(clientCacheIsValid(id.client));
+    DisplayItemIndexMap::const_iterator it = m_displayItemIndexMap.find(id);
+    return it == m_displayItemIndexMap.end() ? kNotFound : it->value;
+}
 
-    for (PaintList::iterator it = begin; it != end; ++it) {
-        DisplayItem& existing = **it;
-        if (existing.isDrawing()
-            && existing.client() == displayItem.client()
-            && existing.type() == DisplayItem::cachedTypeToDrawingType(displayItem.type()))
-            return it;
-    }
+size_t DisplayItemList::findMatchingCachedItem(const DisplayItem& displayItem) const
+{
+    ASSERT(displayItem.isCached());
+    ASSERT(clientCacheIsValid(displayItem.client()));
 
-    ASSERT_NOT_REACHED();
-    return end;
+    return findDisplayItemById(DisplayItem::Id(displayItem.client(), DisplayItem::cachedTypeToDrawingType(displayItem.type())));
 }
 
-static void appendDisplayItem(PaintList& list, HashSet<DisplayItemClient>& clients, WTF::PassOwnPtr<DisplayItem> displayItem)
+void DisplayItemList::appendDisplayItem(PassOwnPtr<DisplayItem> displayItem, PaintList& list, DisplayItemClientSet& cachedClients, DisplayItemIndexMap& displayItemIndexMap)
 {
-    clients.add(displayItem->client());
+    const DisplayItem::Id& id = displayItem->id();
     list.append(displayItem);
+    cachedClients.add(id.client);
+
+    ASSERT(!displayItemIndexMap.contains(id));
+    displayItemIndexMap.add(id, list.size() - 1);
+}
+
+void DisplayItemList::copyCachedSubtree(const DisplayItem& displayItem, PaintList& list, DisplayItemClientSet& cachedClients, DisplayItemIndexMap& displayItemIndexMap)
+{
+    ASSERT(displayItem.isSubtreeCached());
+    ASSERT(clientCacheIsValid(displayItem.client()));
+
+    size_t beginSubtreeIndex = findDisplayItemById(DisplayItem::Id(displayItem.client(), DisplayItem::subtreeCachedTypeToBeginSubtreeType(displayItem.type())));
+    // The subtree previously produced no display items so was omitted.
+    if (beginSubtreeIndex == kNotFound)
+        return;
+
+    size_t endSubtreeIndex = findDisplayItemById(DisplayItem::Id(displayItem.client(), DisplayItem::subtreeCachedTypeToEndSubtreeType(displayItem.type())));
+    ASSERT(endSubtreeIndex != kNotFound);
+
+    for (size_t i = beginSubtreeIndex; i <= endSubtreeIndex; ++i) {
+        if (clientCacheIsValid(m_paintList[i]->client()))
+            appendDisplayItem(m_paintList[i].release(), list, cachedClients, displayItemIndexMap);
+    }
 }
 
 // Update the existing paintList by removing invalidated entries, updating
 // repainted ones, and appending new items.
 //
-// The algorithm is O(|existing paint list| + |newly painted list|): by using
-// the ordering implied by the existing paint list, extra treewalks are avoided.
+// The algorithm is O(|existing paint list| + |newly painted list|):
+// - For CachedDisplayItem, copy the corresponding cached DrawingDisplayItem;
+// - For SubtreeCachedDisplayItem, copy the cached display items from the
+//   corresponding BeginSubtreeDisplayItem and EndSubtreeDisplayItem;
+// - Otherwise, copy the new display item.
 void DisplayItemList::updatePaintList()
 {
     if (!RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled()) {
@@ -88,44 +128,37 @@ void DisplayItemList::updatePaintList()
     }
 
     PaintList updatedList;
+    DisplayItemIndexMap newDisplayItemIndexMap;
     HashSet<DisplayItemClient> newCachedClients;
 
-    PaintList::iterator paintListIt = m_paintList.begin();
-    PaintList::iterator paintListEnd = m_paintList.end();
-
     for (OwnPtr<DisplayItem>& newDisplayItem : m_newPaints) {
-        PaintList::iterator cachedItemIt = findNextMatchingCachedItem(paintListIt, *newDisplayItem);
-        if (cachedItemIt != paintListEnd) {
-            // Copy all of the existing items over until we hit the matching cached item.
-            for (; paintListIt != cachedItemIt; ++paintListIt) {
-                if (clientCacheIsValid((*paintListIt)->client()))
-                    appendDisplayItem(updatedList, newCachedClients, paintListIt->release());
-            }
+        if (newDisplayItem->isSubtreeCached()) {
+            copyCachedSubtree(*newDisplayItem, updatedList, newCachedClients, newDisplayItemIndexMap);
+            continue;
+        }
+
+        if (newDisplayItem->isCached()) {
+            size_t index = findMatchingCachedItem(*newDisplayItem);
+            // Previously the display item generated an empty picture so was omitted.
+            if (index == kNotFound)
+                continue;
 
             // Use the cached item for the new display item.
-            appendDisplayItem(updatedList, newCachedClients, cachedItemIt->release());
-            ++paintListIt;
-        } else {
-            // If the new display item is a cached placeholder, we should have found
-            // the cached display item.
-            ASSERT(!newDisplayItem->isCached());
-
-            // Copy over the new item.
-            appendDisplayItem(updatedList, newCachedClients, newDisplayItem.release());
+            newDisplayItem = m_paintList[index].release();
         }
-    }
-
-    // Copy over any remaining items that are validly cached.
-    for (; paintListIt != paintListEnd; ++paintListIt) {
-        if (clientCacheIsValid((*paintListIt)->client()))
-            appendDisplayItem(updatedList, newCachedClients, paintListIt->release());
+        appendDisplayItem(newDisplayItem.release(), updatedList, newCachedClients, newDisplayItemIndexMap);
     }
 
     m_newPaints.clear();
     m_paintList.clear();
     m_paintList.swap(updatedList);
+    m_displayItemIndexMap.clear();
+    m_displayItemIndexMap.swap(newDisplayItemIndexMap);
     m_cachedClients.clear();
     m_cachedClients.swap(newCachedClients);
+#if ENABLE(ASSERT)
+    m_newPaintIds.clear();
+#endif
 }
 
 #ifndef NDEBUG
@@ -133,12 +166,15 @@ void DisplayItemList::updatePaintList()
 WTF::String DisplayItemList::paintListAsDebugString(const PaintList& list) const
 {
     StringBuilder stringBuilder;
-    bool isFirst = true;
-    for (auto& displayItem : list) {
-        if (!isFirst)
+    for (size_t i = 0; i < list.size(); ++i) {
+        const OwnPtr<DisplayItem>& displayItem = list[i];
+        if (i)
             stringBuilder.append(",\n");
-        isFirst = false;
-        stringBuilder.append('{');
+        if (!displayItem) {
+            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");
@@ -153,7 +189,7 @@ void DisplayItemList::showDebugData() const
     fprintf(stderr, "new paints: [%s]\n", paintListAsDebugString(m_newPaints).utf8().data());
 }
 
-#endif
+#endif // ifndef NDEBUG
 
 void DisplayItemList::replay(GraphicsContext* context)
 {