Subtree caching implementation in blink-core

Source/platform/graphics/paint/DisplayItemList.h

Index: Source/platform/graphics/paint/DisplayItemList.h
diff --git a/Source/platform/graphics/paint/DisplayItemList.h b/Source/platform/graphics/paint/DisplayItemList.h
index ea3ad1b11ace8ecf07f55088e74860d0a826f3c0..7325c18f7fbedb00bea051bfd7804eb96291f089 100644
--- a/Source/platform/graphics/paint/DisplayItemList.h
+++ b/Source/platform/graphics/paint/DisplayItemList.h
@@ -87,6 +87,7 @@ public:
     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)
@@ -114,6 +115,7 @@ protected:
         : m_currentDisplayItems(kMaximumDisplayItemSize, 0)
         , m_newDisplayItems(kMaximumDisplayItemSize, kInitialDisplayItemsCapacity * kMaximumDisplayItemSize)
         , m_validlyCachedClientsDirty(false)
+        , m_subtreeIndicesByClientDirty(false)
         , m_constructionDisabled(false)
         , m_skippingCacheCount(0)
         , m_numCachedItems(0)
@@ -130,21 +132,22 @@ private:
     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&);
+
     void copyCachedSubtree(DisplayItems::iterator& currentIt, DisplayItems& updatedList);
 
 #if ENABLE(ASSERT)
@@ -166,6 +169,11 @@ private:
     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;