First version of new merge algorithm (not enabled yet)

Source/platform/graphics/paint/DisplayItem.h

Index: Source/platform/graphics/paint/DisplayItem.h
diff --git a/Source/platform/graphics/paint/DisplayItem.h b/Source/platform/graphics/paint/DisplayItem.h
index 73532d62ff407d26277ee6f88121c4df3266805f..307b554f3d5bf6e45d3c71316d6c2f4be7528633 100644
--- a/Source/platform/graphics/paint/DisplayItem.h
+++ b/Source/platform/graphics/paint/DisplayItem.h
@@ -8,6 +8,7 @@
 #include "platform/PlatformExport.h"
 #include "platform/graphics/paint/DisplayItemClient.h"
 #include "wtf/Assertions.h"
+#include "wtf/HashTraits.h"
 #include "wtf/PassOwnPtr.h"
 
 #ifndef NDEBUG
@@ -118,6 +119,31 @@ public:
         EndTransform,
         BeginClipPath,
         EndClipPath,
+
+        SubtreeCachedFirst,
+        SubtreeCachedPaintPhaseFirst = SubtreeCachedFirst,
+        SubtreeCachedPaintPhaseLast = SubtreeCachedPaintPhaseFirst + PaintPhaseMax,
+        SubtreeCachedLast = SubtreeCachedPaintPhaseLast,
+
+        BeginSubtreeFirst,
+        BeginSubtreePaintPhaseFirst = BeginSubtreeFirst,
+        BeginSubtreePaintPhaseLast = BeginSubtreePaintPhaseFirst + PaintPhaseMax,
+        BeginSubtreeLast = BeginSubtreePaintPhaseLast,
+
+        EndSubtreeFirst,
+        EndSubtreePaintPhaseFirst = EndSubtreeFirst,
+        EndSubtreePaintPhaseLast = EndSubtreePaintPhaseFirst + PaintPhaseMax,
+        EndSubtreeLast = EndSubtreePaintPhaseLast,
+    };
+
+    struct Id {
+        Id(DisplayItemClient c, Type t) : client(c), type(t) { }
+
+        bool operator==(const Id& other) const { return client == other.client && type == other.type; }
+        bool operator!=(const Id& other) const { return !(*this == other); }
+
+        DisplayItemClient client;
+        Type type;
     };
 
     // Create a dummy display item which just holds the id but has no display operation.
@@ -130,7 +156,8 @@ public:
 
     DisplayItemClient client() const { return m_id.client; }
     Type type() const { return m_id.type; }
-    bool idsEqual(const DisplayItem& other) const { return m_id.client == other.m_id.client && m_id.type == other.m_id.type; }
+    const Id& id() const { return m_id; }
+    bool idsEqual(const DisplayItem& other) const { return m_id == other.m_id; }
 
     virtual void appendToWebDisplayItemList(WebDisplayItemList*) const { }
 
@@ -182,6 +209,34 @@ public:
     DEFINE_PAIRED_CATEGORY_METHODS(Scroll, scroll)
     DEFINE_PAINT_PHASE_CONVERSION_METHOD(Scroll)
 
+    DEFINE_CATEGORY_METHODS(SubtreeCached)
+    DEFINE_PAINT_PHASE_CONVERSION_METHOD(SubtreeCached)
+    DEFINE_CATEGORY_METHODS(BeginSubtree)
+    DEFINE_PAINT_PHASE_CONVERSION_METHOD(BeginSubtree)
+    DEFINE_CATEGORY_METHODS(EndSubtree)
+    DEFINE_PAINT_PHASE_CONVERSION_METHOD(EndSubtree)
+    DEFINE_CONVERSION_METHODS(SubtreeCached, subtreeCached, BeginSubtree, beginSubtree)
+    DEFINE_CONVERSION_METHODS(SubtreeCached, subtreeCached, EndSubtree, endSubtree)
+    DEFINE_CONVERSION_METHODS(BeginSubtree, beginSubtree, EndSubtree, endSubtree)
+
+    bool isBegin() const { return isClip() || isFloatClip() || isScroll() || isBeginSubtree() || type() == BeginFilter || type() == BeginCompositing || type() == BeginTransform || type() == BeginClipPath; }

[pdr., 2015/02/04 05:19:58]

Can we introduce a subclass of paired display item types to make this cleaner?
Keeping this up to date is error-prone.

[Xianzhu, 2015/02/04 20:46:32]

Done and separated into https://codereview.chromium.org/900653003/.

Tried to avoid virtual functions, but it seems not worth it to sacrifice code
maintainability.

+    bool isEnd() const { return isEndClip() || isEndFloatClip() || isEndScroll() || isEndSubtree() || type() == EndFilter || type() == EndCompositing || type() == EndTransform || type() == EndClipPath; }
+
+#if ENABLE(ASSERT)
+    bool isEndAndPairedWith(DisplayItem& other) const
+    {
+        return client() == other.client()
+            && ((isEndClip() && other.isClip() && type() == clipTypeToEndClipType(other.type()))
+                || (isEndFloatClip() && other.isFloatClip() && type() == floatClipTypeToEndFloatClipType(other.type()))
+                || (isEndScroll() && other.isScroll() && type() == scrollTypeToEndScrollType(other.type()))
+                || (isEndSubtree() && other.isBeginSubtree() && type() == beginSubtreeTypeToEndSubtreeType(other.type()))
+                || (type() == EndFilter && other.type() == BeginFilter)
+                || (type() == EndCompositing && other.type() == BeginCompositing)
+                || (type() == EndTransform && other.type() == BeginTransform)
+                || (type() == EndClipPath && other.type() == BeginClipPath));
+    }
+#endif
+
 #ifndef NDEBUG
     static WTF::String typeAsDebugString(DisplayItem::Type);
 
@@ -200,22 +255,32 @@ protected:
     }
 
 private:
-    struct Id {
-        Id(DisplayItemClient c, Type t)
-            : client(c)
-            , type(t)
-        {
-            ASSERT(client);
-        }
-
-        const DisplayItemClient client;
-        const Type type;
-    } m_id;
+    const Id m_id;
 #ifndef NDEBUG
     WTF::String m_clientDebugString;
 #endif
 };
 
-}
+} // namespace blink
+
+// Allow DisplayItem::Id to be hash key.
+namespace WTF {
+
+template<> struct DefaultHash<blink::DisplayItem::Id> {
+    struct Hash {
+        static unsigned hash(const blink::DisplayItem::Id& id) { return pairIntHash(PtrHash<blink::DisplayItemClient>::hash(id.client), static_cast<unsigned>(id.type)); }
+        static bool equal(const blink::DisplayItem::Id& a, const blink::DisplayItem::Id& b) { return a == b; }
+        static const bool safeToCompareToEmptyOrDeleted = true;
+    };
+};
+template<> struct HashTraits<blink::DisplayItem::Id> : GenericHashTraits<blink::DisplayItem::Id> {
+    static const bool emptyValueIsZero = true;
+    static const bool needsDestruction = false;
+    static blink::DisplayItem::Id emptyValue() { return blink::DisplayItem::Id(nullptr, static_cast<blink::DisplayItem::Type>(0)); }
+    static void constructDeletedValue(blink::DisplayItem::Id& slot, bool) { new (NotNull, &slot) blink::DisplayItem::Id(nullptr, static_cast<blink::DisplayItem::Type>(-1)); }
+    static bool isDeletedValue(const blink::DisplayItem::Id& id) { return id.type == static_cast<blink::DisplayItem::Type>(-1); }
+};
+
+} // namespace WTF
 
 #endif // DisplayItem_h