Subtree caching implementation in blink-core

Source/platform/graphics/paint/DisplayItemList.h

 // 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.
 
 #ifndef DisplayItemList_h
 #define DisplayItemList_h
 
 #include "platform/PlatformExport.h"
 #include "platform/graphics/ContiguousContainer.h"
 #include "platform/graphics/paint/DisplayItem.h"
@@ skipping 69 matching lines @@
 
     // Returns the approximate memory usage, excluding memory likely to be
     // shared with the embedder after copying to WebDisplayItemList.
     // Should only be called right after commitNewDisplayItems.
     size_t approximateUnsharedMemoryUsage() const;
 
     // Get the paint list generated after the last painting.
     const DisplayItems& displayItems() const;
 
     bool clientCacheIsValid(DisplayItemClient) const;
+    bool subtreeCacheIsValid(DisplayItemClient, DisplayItem::Type beginSubtreeType) const;
 
     // Commits the new display items and plays back the updated display items into the given context.
     void commitNewDisplayItemsAndReplay(GraphicsContext& context)
     {
         commitNewDisplayItems();
         replay(context);
     }
 
     void appendToWebDisplayItemList(WebDisplayItemList*);
     void commitNewDisplayItemsAndAppendToWebDisplayItemList(WebDisplayItemList*);
 
     bool displayItemConstructionIsDisabled() const { return m_constructionDisabled; }
     void setDisplayItemConstructionIsDisabled(const bool disable) { m_constructionDisabled = disable; }
 
 #if ENABLE(ASSERT)
     size_t newDisplayItemsSize() const { return m_newDisplayItems.size(); }
 #endif
 
 #ifndef NDEBUG
     void showDebugData() const;
 #endif
 
 protected:
     DisplayItemList()
         : m_currentDisplayItems(kMaximumDisplayItemSize, 0)
         , m_newDisplayItems(kMaximumDisplayItemSize, kInitialDisplayItemsCapacity * kMaximumDisplayItemSize)
         , m_validlyCachedClientsDirty(false)
+        , m_subtreeIndicesByClientDirty(false)
         , m_constructionDisabled(false)
         , m_skippingCacheCount(0)
         , m_numCachedItems(0)
         , m_nextScope(1) { }
 
 private:
     friend class DisplayItemListTest;
     friend class DisplayItemListPaintTest;
     friend class DisplayItemListPaintTestForSlimmingPaintV2;
     friend class LayoutObjectDrawingRecorderTest;
 
     // Set new item state (scopes, cache skipping, etc) for a new item.
     // TODO(pdr): This only passes a pointer to make the patch easier to review. Change to a reference.
     void processNewItem(DisplayItem*);
 
     void updateValidlyCachedClientsIfNeeded() const;
+    void updateSubtreeIndicesByClientIfNeeded() const;
 
 #ifndef NDEBUG
     WTF::String displayItemsAsDebugString(const DisplayItems&) const;
 #endif
 
-    // Indices into PaintList of all DrawingDisplayItems and BeginSubtreeDisplayItems of each client.
-    // Temporarily used during merge to find out-of-order display items.
+    // Indices into DisplayItems of all certain types of display items of each client.
     using DisplayItemIndicesByClientMap = HashMap<DisplayItemClient, Vector<size_t>>;
 
     static size_t findMatchingItemFromIndex(const DisplayItem::Id&, const DisplayItemIndicesByClientMap&, const DisplayItems&);
-    static void addItemToIndexIfNeeded(const DisplayItem&, size_t index, DisplayItemIndicesByClientMap&);
+    static void addItemToIndex(const DisplayItem&, size_t index, DisplayItemIndicesByClientMap&);
 
     struct OutOfOrderIndexContext;
     DisplayItems::iterator findOutOfOrderCachedItem(DisplayItems::iterator currentIt, const DisplayItem::Id&, OutOfOrderIndexContext&);
-    DisplayItems::iterator findOutOfOrderCachedItemForward(const DisplayItem::Id&, OutOfOrderIndexContext&);
+    DisplayItems::iterator findOutOfOrderCachedItemForward(DisplayItems::iterator currentIt, const DisplayItem::Id&, OutOfOrderIndexContext&);
+
     void copyCachedSubtree(DisplayItems::iterator& currentIt, DisplayItems& updatedList);
 
 #if ENABLE(ASSERT)
     // The following two methods are for checking under-invalidations
     // (when RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled).
     void checkCachedDisplayItemIsUnchanged(const DisplayItem&, DisplayItemIndicesByClientMap&);
     void checkNoRemainingCachedDisplayItems();
 #endif
 
     void replay(GraphicsContext&);
 
     DisplayItems m_currentDisplayItems;
     DisplayItems m_newDisplayItems;
 
     // Contains all clients having valid cached paintings if updated.
     // It's lazily updated in updateValidlyCachedClientsIfNeeded().
     // FIXME: In the future we can replace this with client-side repaint flags
     // to avoid the cost of building and querying the hash table.
     mutable HashSet<DisplayItemClient> m_validlyCachedClients;
     mutable bool m_validlyCachedClientsDirty;
 
+    // Stores indices to BeginSubtree display items for subtreeCacheIsValid().
+    // It's lazily updated in updateSubtreeIndicesIfNeeded().
+    mutable DisplayItemIndicesByClientMap m_subtreeIndicesByClient;
+    mutable bool m_subtreeIndicesByClientDirty;
+
     // Allow display item construction to be disabled to isolate the costs of construction
     // in performance metrics.
     bool m_constructionDisabled;
 
     int m_skippingCacheCount;
 
     int m_numCachedItems;
 
     unsigned m_nextScope;
     Vector<unsigned> m_scopeStack;
 
 #if ENABLE(ASSERT)
     // This is used to check duplicated ids during add(). We could also check during
     // updatePaintList(), but checking during add() helps developer easily find where
     // the duplicated ids are from.
     DisplayItemIndicesByClientMap m_newDisplayItemIndicesByClient;
 #endif
 };
 
 } // namespace blink
 
 #endif // DisplayItemList_h