Remove begin/end subseq. display items, and store on PaintController instead.

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/graphics/GraphicsLayer.h"
 #include "platform/graphics/paint/DrawingDisplayItem.h"
 #include "platform/instrumentation/tracing/TraceEvent.h"
 #include "third_party/skia/include/core/SkPictureAnalyzer.h"
@@ skipping 81 matching lines @@
 
   if (RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled() &&
       isCheckingUnderInvalidation()) {
     // We are checking under-invalidation of an ancestor subsequence enclosing
     // this one. The ancestor subsequence is supposed to have already "copied",
     // so we should let the client continue to actually paint the descendant
     // subsequences without "copying".
     return false;
   }
 
-  size_t cachedItem =
-      findCachedItem(DisplayItem::Id(client, DisplayItem::kSubsequence));
-  if (cachedItem == kNotFound) {
-    NOTREACHED();
+  SubsequenceMarkers* markers = getSubsequenceMarkers(client);
+  if (!markers) {
     return false;
   }
 
   // |cachedItem| will point to the first item after the subsequence or end of
   // the current list.
   ensureNewDisplayItemListInitialCapacity();
-  copyCachedSubsequence(cachedItem);
 
-  m_nextItemToMatch = cachedItem;
-  // Items before |cachedItem| have been copied so we don't need to index them.
-  if (cachedItem > m_nextItemToIndex)
-    m_nextItemToIndex = cachedItem;
+  size_t sizeBeforeCopy = m_newDisplayItemList.size();
+  copyCachedSubsequence(markers->start, markers->end);
+
+  if (!RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled()) {
+    addCachedSubsequence(client, sizeBeforeCopy,
+                         m_newDisplayItemList.size() - 1);
+  }
+
+  m_nextItemToMatch = markers->end + 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()) {
     // Return false to let the painter actually paint. We will check if the new
     // painting is the same as the cached one.
     return false;
   }
 
   return true;
 }
 
+PaintController::SubsequenceMarkers* PaintController::getSubsequenceMarkers(
+    const DisplayItemClient& client) {
+  auto result = m_currentCachedSubsequences.find(&client);
+  if (result == m_currentCachedSubsequences.end())
+    return nullptr;
+  return &result->value;
+}
+
+void PaintController::addCachedSubsequence(const DisplayItemClient& client,
+                                           unsigned start,
+                                           unsigned end) {
+  DCHECK(start <= end);
+  DCHECK(end < m_newDisplayItemList.size());
+  if (isCheckingUnderInvalidation()) {
+    SubsequenceMarkers* markers = getSubsequenceMarkers(client);
+    if (!markers) {
+      showSequenceUnderInvalidationError(
+          "under-invalidation : unexpected subsequence", client, start, end);
+      DCHECK(false);
+    }
+    if (markers->end - markers->start != end - start) {
+      showSequenceUnderInvalidationError(
+          "under-invalidation: new subsequence wrong length", client, start,
+          end);
+      DCHECK(false);
+    }
+  }
+
+  DCHECK(m_newCachedSubsequences.find(&client) ==
+         m_newCachedSubsequences.end());
+
+  m_newCachedSubsequences.insert(&client, SubsequenceMarkers(start, end));

[Xianzhu, 2017/04/05 22:39:17]

I'm afraid this may degrade performance. Previously we don't index at all during
the first paint, and only add out-of-order subsequences into the index during
the next paint. Now we add all subsequences into the map during the current
paint and always look up the map for cached subsequences.

Let's look at the performance data first before deciding if we need to improve
it.

[chrishtr, 2017/04/06 00:05:29]

Ok.

You're right about indexing, but OTOH there are many fewer subsequences than
display items.

Alternatively we could use a vector.

+}
+
 bool PaintController::lastDisplayItemIsNoopBegin() const {
   if (m_newDisplayItemList.isEmpty())
     return false;
 
   const auto& lastDisplayItem = m_newDisplayItemList.last();
   return lastDisplayItem.isBegin() && !lastDisplayItem.drawsContent();
 }
 
 void PaintController::removeLastDisplayItem() {
   if (m_newDisplayItemList.isEmpty())
@@ skipping 34 matching lines @@
 
 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.back());
-      }
-    }
-
-    if (displayItem.getType() == DisplayItem::kSubsequence) {
-      m_currentSubsequenceClients.push_back(&displayItem.client());
-    } else if (displayItem.getType() == DisplayItem::kEndSubsequence) {
-      CHECK(m_currentSubsequenceClients.back() == &displayItem.client());
-      m_currentSubsequenceClients.pop_back();
     }
   }
 #endif
 
   if (isSkippingCache())
     displayItem.setSkippedCache();
 
   if (RuntimeEnabledFeatures::slimmingPaintV2Enabled()) {
     size_t lastChunkIndex = m_newPaintChunks.lastChunkIndex();
     if (m_newPaintChunks.incrementDisplayItemIndex(displayItem)) {
       DCHECK(lastChunkIndex != m_newPaintChunks.lastChunkIndex());
       if (lastChunkIndex != kNotFound)
         generateChunkRasterInvalidationRects(
             m_newPaintChunks.paintChunkAt(lastChunkIndex));
     }
   }
 
 #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();
@@ skipping 155 matching lines @@
   if (RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled())
     CHECK(false) << "Can't find cached display item";
 
   // 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, 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
+// Copies a cached subsequence from current list to the new list.
+// 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) {
+void PaintController::copyCachedSubsequence(size_t beginIndex,
+                                            size_t endIndex) {
   AutoReset<size_t> subsequenceBeginIndex(
       &m_currentCachedSubsequenceBeginIndexInNewList,
       m_newDisplayItemList.size());
   DisplayItem* cachedItem =
-      &m_currentPaintArtifact.getDisplayItemList()[cachedItemIndex];
-  DCHECK(cachedItem->getType() == DisplayItem::kSubsequence);
+      &m_currentPaintArtifact.getDisplayItemList()[beginIndex];
 
   if (RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled()) {
     DCHECK(!isCheckingUnderInvalidation());
-    m_underInvalidationCheckingBegin = cachedItemIndex;
+    m_underInvalidationCheckingBegin = beginIndex;
     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);
+        m_currentPaintArtifact.findChunkByDisplayItemIndex(beginIndex);
     DCHECK(cachedChunk != m_currentPaintArtifact.paintChunks().end());
     updateCurrentPaintChunkProperties(
         cachedChunk->id ? &*cachedChunk->id : nullptr, cachedChunk->properties);
   } else {
     // Avoid uninitialized variable error on Windows.
     cachedChunk = m_currentPaintArtifact.paintChunks().begin();
   }
 
-  while (true) {
+  for (size_t currentIndex = beginIndex; currentIndex <= endIndex;
+       ++currentIndex) {
+    cachedItem = &m_currentPaintArtifact.getDisplayItemList()[currentIndex];
     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) {
+          currentIndex == cachedChunk->endIndex) {
         ++cachedChunk;
         DCHECK(cachedChunk != m_currentPaintArtifact.paintChunks().end());
         updateCurrentPaintChunkProperties(
             cachedChunk->id ? &*cachedChunk->id : nullptr,
             cachedChunk->properties);
       }
-      processNewItem(moveItemFromCurrentListToNewList(cachedItemIndex));
+      processNewItem(moveItemFromCurrentListToNewList(currentIndex));
       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());
-    cachedItem = &m_currentPaintArtifact.getDisplayItemList()[cachedItemIndex];
   }
 
   if (RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled()) {
-    m_underInvalidationCheckingEnd = cachedItemIndex;
+    m_underInvalidationCheckingEnd = endIndex + 1;
     DCHECK(isCheckingUnderInvalidation());
   }
 }
 
 DISABLE_CFI_PERF
 static IntRect visualRectForDisplayItem(
     const DisplayItem& displayItem,
     const LayoutSize& offsetFromLayoutObject) {
   LayoutRect visualRect = displayItem.client().visualRect();
   visualRect.move(-offsetFromLayoutObject);
@@ skipping 26 matching lines @@
 #endif
 
   if (RuntimeEnabledFeatures::slimmingPaintV2Enabled() &&
       !m_newDisplayItemList.isEmpty())
     generateChunkRasterInvalidationRects(m_newPaintChunks.lastChunk());
 
   SkPictureGpuAnalyzer gpuAnalyzer;
 
   m_currentCacheGeneration =
       DisplayItemClient::CacheGenerationOrInvalidationReason::next();
+
+  m_newCachedSubsequences.swap(m_currentCachedSubsequences);
+  m_newCachedSubsequences.clear();
+  for (auto& item : m_currentCachedSubsequences)
+    item.key->setDisplayItemsCached(m_currentCacheGeneration);
+
   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.
     m_newDisplayItemList.appendVisualRect(
         visualRectForDisplayItem(item, offsetFromLayoutObject));
 
@@ skipping 39 matching lines @@
     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);
 
 #if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
-  CHECK(m_currentSubsequenceClients.isEmpty());
   DisplayItemClient::endShouldKeepAliveAllClients(this);
 #endif
 
 #ifndef NDEBUG
   m_numSequentialMatches = 0;
   m_numOutOfOrderMatches = 0;
   m_numIndexedItems = 0;
 #endif
 }
 
@@ skipping 198 matching lines @@
   }
   LOG(INFO) << "new record:\n"
             << (newRecord ? recordAsDebugString(newRecord) : "None");
   LOG(INFO) << "old record:\n"
             << (oldRecord ? recordAsDebugString(oldRecord) : "None");
 
   showDebugData();
 #endif  // NDEBUG
 }
 
+void PaintController::showSequenceUnderInvalidationError(
+    const char* reason,
+    const DisplayItemClient& client,
+    int start,
+    int end) {
+  LOG(ERROR) << m_underInvalidationMessagePrefix << " " << reason;
+  LOG(ERROR) << "Subsequence client: " << client.debugName();
+#ifndef NDEBUG
+//  showDebugData();
+#else
+  LOG(ERROR) << "Run debug build to get more details.";
+#endif
+  LOG(ERROR) << "See http://crbug.com/619103.";
+}
+
 void PaintController::checkUnderInvalidation() {
   DCHECK(RuntimeEnabledFeatures::paintUnderInvalidationCheckingEnabled());
 
   if (!isCheckingUnderInvalidation())
     return;
 
   const DisplayItem& newItem = m_newDisplayItemList.last();
   size_t oldItemIndex = m_underInvalidationCheckingBegin +
                         m_skippedProbableUnderInvalidationCount;
   DisplayItem* oldItem =
@@ skipping 65 matching lines @@
                        showPaintRecords
                            ? (DisplayItemList::JsonOptions::ShowPaintRecords |
                               DisplayItemList::JsonOptions::ShowClientDebugName)
                            : DisplayItemList::JsonOptions::ShowClientDebugName)
                    ->toPrettyJSONString()
                    .utf8()
                    .data());
 }
 
 }  // namespace blink