Subtree caching implementation in blink-core

Source/platform/graphics/paint/DisplayItemListTest.cpp

Index: Source/platform/graphics/paint/DisplayItemListTest.cpp
diff --git a/Source/platform/graphics/paint/DisplayItemListTest.cpp b/Source/platform/graphics/paint/DisplayItemListTest.cpp
index 59e7642e15a0df630c18a0e3f31dec68c67c752b..b4d9437e617a7834cb2568729ae9fd5d70dbbcab 100644
--- a/Source/platform/graphics/paint/DisplayItemListTest.cpp
+++ b/Source/platform/graphics/paint/DisplayItemListTest.cpp
@@ -12,11 +12,40 @@
 #include "platform/graphics/paint/ClipRecorder.h"
 #include "platform/graphics/paint/DrawingDisplayItem.h"
 #include "platform/graphics/paint/DrawingRecorder.h"
-#include "platform/graphics/paint/SubtreeRecorder.h"
+#include "platform/graphics/paint/SubtreeDisplayItem.h"
 #include <gtest/gtest.h>
 
 namespace blink {
 
+class SimpleSubtreeRecorder {
+public:
+    static bool useCachedSubtreeIfPossible(DisplayItemList& displayItemList, const DisplayItemClientWrapper& client, int paintPhase)
+    {
+        if (displayItemList.subtreeCacheIsValid(client.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(paintPhase))) {
+            displayItemList.createAndAppend<CachedDisplayItem>(client, DisplayItem::paintPhaseToCachedSubtreeType(paintPhase));
+            return true;
+        }
+        return false;
+    }
+
+    SimpleSubtreeRecorder(DisplayItemList& displayItemList, const DisplayItemClientWrapper& client, int paintPhase)
+        : m_displayItemList(displayItemList)
+        , m_client(client)
+        , m_paintPhase(paintPhase)
+    {
+        displayItemList.createAndAppend<BeginSubtreeDisplayItem>(client, DisplayItem::paintPhaseToBeginSubtreeType(paintPhase));
+    }
+    ~SimpleSubtreeRecorder()
+    {
+        m_displayItemList.createAndAppend<EndSubtreeDisplayItem>(m_client, DisplayItem::paintPhaseToEndSubtreeType(m_paintPhase));
+    }
+
+private:
+    DisplayItemList& m_displayItemList;
+    const DisplayItemClientWrapper m_client;
+    const int m_paintPhase;
+};
+
 class DisplayItemListTest : public ::testing::Test {
 public:
     DisplayItemListTest()
@@ -462,26 +491,22 @@ TEST_F(DisplayItemListTest, CachedSubtreeSwapOrder)
     const int foregroundPaintPhase = foregroundDrawingType - DisplayItem::DrawingPaintPhaseFirst;
 
     {
-        SubtreeRecorder r(context, container1, backgroundPaintPhase);
-        EXPECT_FALSE(r.canUseCache());
+        SimpleSubtreeRecorder r(displayItemList(), container1, backgroundPaintPhase);
         drawRect(context, container1, backgroundDrawingType, FloatRect(100, 100, 100, 100));
         drawRect(context, content1, backgroundDrawingType, FloatRect(100, 100, 50, 200));
     }
     {
-        SubtreeRecorder r(context, container1, foregroundPaintPhase);
-        EXPECT_FALSE(r.canUseCache());
+        SimpleSubtreeRecorder r(displayItemList(), container1, foregroundPaintPhase);
         drawRect(context, content1, foregroundDrawingType, FloatRect(100, 100, 50, 200));
         drawRect(context, container1, foregroundDrawingType, FloatRect(100, 100, 100, 100));
     }
     {
-        SubtreeRecorder r(context, container2, backgroundPaintPhase);
-        EXPECT_FALSE(r.canUseCache());
+        SimpleSubtreeRecorder r(displayItemList(), container2, backgroundPaintPhase);
         drawRect(context, container2, backgroundDrawingType, FloatRect(100, 200, 100, 100));
         drawRect(context, content2, backgroundDrawingType, FloatRect(100, 200, 50, 200));
     }
     {
-        SubtreeRecorder r(context, container2, foregroundPaintPhase);
-        EXPECT_FALSE(r.canUseCache());
+        SimpleSubtreeRecorder r(displayItemList(), container2, foregroundPaintPhase);
         drawRect(context, content2, foregroundDrawingType, FloatRect(100, 200, 50, 200));
         drawRect(context, container2, foregroundDrawingType, FloatRect(100, 200, 100, 100));
     }
@@ -509,17 +534,17 @@ TEST_F(DisplayItemListTest, CachedSubtreeSwapOrder)
         TestDisplayItem(container2, DisplayItem::paintPhaseToEndSubtreeType(foregroundPaintPhase)));
 
     // Simulate the situation when container1 e.g. gets a z-index that is now greater than container2.
-    displayItemList().createAndAppend<CachedDisplayItem>(container2, DisplayItem::paintPhaseToCachedSubtreeType(backgroundPaintPhase));
+    EXPECT_TRUE(SimpleSubtreeRecorder::useCachedSubtreeIfPossible(displayItemList(), container2, backgroundPaintPhase));
     EXPECT_EQ((size_t)1, newPaintListBeforeUpdate().size());
     EXPECT_TRUE(newPaintListBeforeUpdate().last().isCachedSubtree());
-    displayItemList().createAndAppend<CachedDisplayItem>(container2, DisplayItem::paintPhaseToCachedSubtreeType(foregroundPaintPhase));
+    EXPECT_TRUE(SimpleSubtreeRecorder::useCachedSubtreeIfPossible(displayItemList(), container2, foregroundPaintPhase));
     EXPECT_EQ((size_t)2, newPaintListBeforeUpdate().size());
     EXPECT_TRUE(newPaintListBeforeUpdate().last().isCachedSubtree());
 
-    displayItemList().createAndAppend<CachedDisplayItem>(container1, DisplayItem::paintPhaseToCachedSubtreeType(backgroundPaintPhase));
+    EXPECT_TRUE(SimpleSubtreeRecorder::useCachedSubtreeIfPossible(displayItemList(), container1, backgroundPaintPhase));
     EXPECT_EQ((size_t)3, newPaintListBeforeUpdate().size());
     EXPECT_TRUE(newPaintListBeforeUpdate().last().isCachedSubtree());
-    displayItemList().createAndAppend<CachedDisplayItem>(container1, DisplayItem::paintPhaseToCachedSubtreeType(foregroundPaintPhase));
+    EXPECT_TRUE(SimpleSubtreeRecorder::useCachedSubtreeIfPossible(displayItemList(), container1, foregroundPaintPhase));
     EXPECT_EQ((size_t)4, newPaintListBeforeUpdate().size());
     EXPECT_TRUE(newPaintListBeforeUpdate().last().isCachedSubtree());
     displayItemList().commitNewDisplayItems();
@@ -546,6 +571,108 @@ TEST_F(DisplayItemListTest, CachedSubtreeSwapOrder)
         TestDisplayItem(container1, DisplayItem::paintPhaseToEndSubtreeType(foregroundDrawingType)));
 }
 
+TEST_F(DisplayItemListTest, CachedNestedSubtreeUpdate)
+{
+    TestDisplayItemClient container1("container1");
+    TestDisplayItemClient content1("content1");
+    TestDisplayItemClient container2("container2");
+    TestDisplayItemClient content2("content2");
+    GraphicsContext context(&displayItemList());
+    const int backgroundPaintPhase = backgroundDrawingType - DisplayItem::DrawingPaintPhaseFirst;
+    const int foregroundPaintPhase = foregroundDrawingType - DisplayItem::DrawingPaintPhaseFirst;
+
+    {
+        SimpleSubtreeRecorder r(displayItemList(), container1, backgroundPaintPhase);
+        drawRect(context, container1, backgroundDrawingType, FloatRect(100, 100, 100, 100));
+        {
+            SimpleSubtreeRecorder r(displayItemList(), content1, backgroundPaintPhase);
+            drawRect(context, content1, backgroundDrawingType, FloatRect(100, 100, 50, 200));
+        }
+    }
+    {
+        SimpleSubtreeRecorder r(displayItemList(), container1, foregroundPaintPhase);
+        {
+            SimpleSubtreeRecorder r(displayItemList(), content1, foregroundPaintPhase);
+            drawRect(context, content1, foregroundDrawingType, FloatRect(100, 100, 50, 200));
+        }
+        drawRect(context, container1, foregroundDrawingType, FloatRect(100, 100, 100, 100));
+    }
+    {
+        SimpleSubtreeRecorder r(displayItemList(), container2, backgroundPaintPhase);
+        drawRect(context, container2, backgroundDrawingType, FloatRect(100, 200, 100, 100));
+        {
+            SimpleSubtreeRecorder r(displayItemList(), content2, backgroundPaintPhase);
+            drawRect(context, content2, backgroundDrawingType, FloatRect(100, 200, 50, 200));
+        }
+    }
+    displayItemList().commitNewDisplayItems();
+
+    EXPECT_DISPLAY_LIST(displayItemList().displayItems(), 18,
+        TestDisplayItem(container1, DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(container1, backgroundDrawingType),
+        TestDisplayItem(content1, DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(content1, backgroundDrawingType),
+        TestDisplayItem(content1, DisplayItem::paintPhaseToEndSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(container1, DisplayItem::paintPhaseToEndSubtreeType(backgroundPaintPhase)),
+
+        TestDisplayItem(container1, DisplayItem::paintPhaseToBeginSubtreeType(foregroundPaintPhase)),
+        TestDisplayItem(content1, DisplayItem::paintPhaseToBeginSubtreeType(foregroundPaintPhase)),
+        TestDisplayItem(content1, foregroundDrawingType),
+        TestDisplayItem(content1, DisplayItem::paintPhaseToEndSubtreeType(foregroundPaintPhase)),
+        TestDisplayItem(container1, foregroundDrawingType),
+        TestDisplayItem(container1, DisplayItem::paintPhaseToEndSubtreeType(foregroundPaintPhase)),
+
+        TestDisplayItem(container2, DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(container2, backgroundDrawingType),
+        TestDisplayItem(content2, DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(content2, backgroundDrawingType),
+        TestDisplayItem(content2, DisplayItem::paintPhaseToEndSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(container2, DisplayItem::paintPhaseToEndSubtreeType(backgroundPaintPhase)));
+
+    // Container2 itself now becomes empty (but still has the 'content2' child), and chooses not to output subtree info.
+    displayItemList().invalidate(container2.displayItemClient());
+    displayItemList().invalidate(content2.displayItemClient());
+    EXPECT_FALSE(SimpleSubtreeRecorder::useCachedSubtreeIfPossible(displayItemList(), container2, backgroundPaintPhase));
+    EXPECT_FALSE(SimpleSubtreeRecorder::useCachedSubtreeIfPossible(displayItemList(), content2, backgroundPaintPhase));
+    // Content2 now outputs foreground.
+    EXPECT_FALSE(SimpleSubtreeRecorder::useCachedSubtreeIfPossible(displayItemList(), content2, foregroundPaintPhase));
+    {
+        SimpleSubtreeRecorder r(displayItemList(), content2, foregroundPaintPhase);
+        drawRect(context, content2, foregroundDrawingType, FloatRect(100, 200, 50, 200));
+    }
+    EXPECT_EQ((size_t)3, newPaintListBeforeUpdate().size());
+
+    // Container1 subtree now uses cached background, but not cached foreground.
+    // The merge algorithm allows changing subtree without invalidating the displayItemClient.
+    EXPECT_TRUE(SimpleSubtreeRecorder::useCachedSubtreeIfPossible(displayItemList(), container1, backgroundPaintPhase));
+    EXPECT_EQ((size_t)4, newPaintListBeforeUpdate().size());
+    EXPECT_TRUE(newPaintListBeforeUpdate().last().isCachedSubtree());
+
+    displayItemList().commitNewDisplayItems();
+
+    EXPECT_DISPLAY_LIST(displayItemList().displayItems(), 9,
+        TestDisplayItem(content2, DisplayItem::paintPhaseToBeginSubtreeType(foregroundPaintPhase)),
+        TestDisplayItem(content2, foregroundDrawingType),
+        TestDisplayItem(content2, DisplayItem::paintPhaseToEndSubtreeType(foregroundPaintPhase)),
+
+        TestDisplayItem(container1, DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(container1, backgroundDrawingType),
+        TestDisplayItem(content1, DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(content1, backgroundDrawingType),
+        TestDisplayItem(content1, DisplayItem::paintPhaseToEndSubtreeType(backgroundPaintPhase)),
+        TestDisplayItem(container1, DisplayItem::paintPhaseToEndSubtreeType(backgroundPaintPhase)));
+
+    EXPECT_TRUE(displayItemList().subtreeCacheIsValid(container1.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)));
+    EXPECT_TRUE(displayItemList().subtreeCacheIsValid(content1.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)));
+    EXPECT_FALSE(displayItemList().subtreeCacheIsValid(container1.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(foregroundPaintPhase)));
+    EXPECT_FALSE(displayItemList().subtreeCacheIsValid(content1.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(foregroundPaintPhase)));
+
+    EXPECT_FALSE(displayItemList().subtreeCacheIsValid(container2.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)));
+    EXPECT_FALSE(displayItemList().subtreeCacheIsValid(content2.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(backgroundPaintPhase)));
+    EXPECT_FALSE(displayItemList().subtreeCacheIsValid(container2.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(foregroundPaintPhase)));
+    EXPECT_TRUE(displayItemList().subtreeCacheIsValid(content2.displayItemClient(), DisplayItem::paintPhaseToBeginSubtreeType(foregroundPaintPhase)));
+}
+
 TEST_F(DisplayItemListTest, Scope)
 {
     TestDisplayItemClient multicol("multicol");