First version of new merge algorithm (not enabled yet)

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"
 #ifndef NDEBUG
 #include "platform/graphics/paint/DisplayItem.h"
 #include "wtf/text/StringBuilder.h"
 #include <stdio.h>
 #endif
 
 namespace blink {
 
-const PaintList& DisplayItemList::paintList()
+const PaintList& DisplayItemList::paintList() const
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     ASSERT(m_newPaints.isEmpty());
     return m_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.

[chrishtr, 2015/02/03 00:39:00]

Why bother to clean these out?

[Xianzhu, 2015/02/03 01:57:12]

Without this, most of the display items in a paint list would be empty
BeginSubtree/EndSubtree pairs.

Tested ViewDisplayListTest.FullDocumentPaintingWithCaret without this, and it
produced 30 display items (originally 2). With this code, we generate 10 display
items (see the patched ViewDisplayListTest.cpp).

+#if ENABLE(ASSERT)
+            m_newPaintIds.remove(m_newPaints.last()->id());
+#endif
+            m_newPaints.removeLast();
+            return;
+        }
+    }
+#if ENABLE(ASSERT)
+    if (RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled()) {
+        ASSERT(!m_newPaintIds.contains(displayItem->id()));
+        if (displayItem->isDrawing() || displayItem->isBeginSubtree())
+            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);
 }
 
 void DisplayItemList::invalidateAll()
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     // Can only be called during layout/paintInvalidation, not during painting.
     ASSERT(m_newPaints.isEmpty());
     m_paintList.clear();
     m_cachedClients.clear();
 }
 
 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::findMatchingCachedItem(const DisplayItem& displayItem)
 {
-    PaintList::iterator end = m_paintList.end();
+    ASSERT(displayItem.isCached());
+    ASSERT(clientCacheIsValid(displayItem.client()));
 
-    if (!clientCacheIsValid(displayItem.client()))
-        return end;
-
-    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;
-    }
-
-    ASSERT_NOT_REACHED();
-    return end;
+    DisplayItem::Id drawingDisplayItemId(displayItem.client(), DisplayItem::cachedTypeToDrawingType(displayItem.type()));
+    DisplayItemIndexMap::const_iterator it = m_displayItemIndexMap.find(drawingDisplayItemId);
+    return it == m_displayItemIndexMap.end() ? kNotFound : it->value;
 }
 
-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);
+
+    // For now we only need to map Drawing and BeginSubtree display items.
+    if (!list.last()->isDrawing() && !list.last()->isBeginSubtree())
+        return;
+    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()));
+
+    DisplayItem::Id beginSubtreeDisplayItemId(displayItem.client(), DisplayItem::subtreeCachedTypeToBeginSubtreeType(displayItem.type()));
+    DisplayItemIndexMap::const_iterator it = m_displayItemIndexMap.find(beginSubtreeDisplayItemId);
+    if (it == m_displayItemIndexMap.end())
+        return;

[chrishtr, 2015/02/03 00:39:00]

Don't you want to insert the CachedSubtreeDisplayItem in this case?

[Xianzhu, 2015/02/03 01:57:12]

No. This is a valid case that the subtree previously produced nothing. We don't
store empty BeginSubtree/EndSubtree pairs otherwise there would be too many of
them.

Added comments about the case.

+
+    DisplayItem::Id endSubtreeId(displayItem.client(), DisplayItem::subtreeCachedTypeToEndSubtreeType(displayItem.type()));
+    for (size_t i = it->value; ; ++i) {
+        if (clientCacheIsValid(m_paintList[i]->client()))
+            appendDisplayItem(m_paintList[i].release(), list, cachedClients, displayItemIndexMap);
+        if (list.last()->id() == endSubtreeId)
+            break;
+    }

[chrishtr, 2015/02/03 00:39:00]

Add an assert that it found the endSubtreeId. Better yet, why not look up the
index of the first and last in the displayItemIndexMap, and do a simple for loop
count between them?

[Xianzhu, 2015/02/03 01:57:12]

Looping between first/last looks clearer. Done.

In this patch only Drawing and BeginSubtree display items are mapped. The
limitation seems not necessary. Removed it.

 }
 
 // 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()) {
         m_paintList.clear();
         m_paintList.swap(m_newPaints);
         m_cachedClients.clear();
         return;
     }
 
     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) {
+        if (newDisplayItem->isSubtreeCached()) {

[chrishtr, 2015/02/03 00:39:00]

Subtree cached can be thought of as a type of cached, right? Then you can use
the same helper method to map from cached display item to non-cached.
Then if you add a fallback to the existing cached item if the non-cached is not
present, you can also avoid the 'continue' jumps.

[Xianzhu, 2015/02/03 01:57:12]

There seems little code to share by SubtreeCached and normal Cached (extracted
findDisplayItemById though in the new patch set).

The 'continue' jumps is to skip the display item which previously generated
nothing (empty subtree or empty picture), so seems unavoidable. (I could use a
bool variable to avoid the 'continue's but this seems no better).

The patch in https://codereview.chromium.org/847783003/ used the 'not-found'
result as an indicator of under-invalidation and appended the cached display
items into paint list to draw visual indications. However, the method is far
from complete to detect under-invalidations, and requires us to keep empty
display items (which was also a must when we used linear storage, but not
necessary when we use the map).

+            copyCachedSubtree(*newDisplayItem, updatedList, newCachedClients, newDisplayItemIndexMap);
+            continue;
+        }
 
-    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->isCached()) {
+            size_t index = findMatchingCachedItem(*newDisplayItem);
+            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
 
 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");
         stringBuilder.append('}');
     }
     return stringBuilder.toString();
 }
 
 void DisplayItemList::showDebugData() const
 {
     fprintf(stderr, "paint list: [%s]\n", paintListAsDebugString(m_paintList).utf8().data());
     fprintf(stderr, "new paints: [%s]\n", paintListAsDebugString(m_newPaints).utf8().data());
 }
 
-#endif
+#endif // ifndef NDEBUG
 
 void DisplayItemList::replay(GraphicsContext* context)
 {
     updatePaintList();
     for (auto& displayItem : m_paintList)
         displayItem->replay(context);
 }
 
 } // namespace blink