Slimming Paint phase 2 compositing algorithm plumbing & skeleton display list API.

Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp

Index: Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp
diff --git a/Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp b/Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp
index f23c5182a0dfe7fbd6eba2d20b2bf819f4c7fd43..f2d70126b8c40a93303235d0eec52d0eac7443d4 100644
--- a/Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp
+++ b/Source/platform/graphics/paint/DisplayItemTransformTreeBuilder.cpp
@@ -6,8 +6,10 @@
 #include "platform/graphics/paint/DisplayItemTransformTreeBuilder.h"
 
 #include "platform/graphics/paint/DisplayItem.h"
+#include "platform/graphics/paint/DisplayItemList.h"
 #include "platform/graphics/paint/DisplayItemTransformTree.h"
 #include "platform/graphics/paint/Transform3DDisplayItem.h"
+#include "public/platform/WebDisplayList.h"
 
 namespace blink {
 
@@ -56,6 +58,14 @@ static BeginDisplayItemClassification classifyBeginItem(const DisplayItem& begin
 
 } // namespace
 
+void DisplayItemTransformTreeBuilder::build(const DisplayItemList& displayList, const DisplayListDiff& displayListDiff)
+{
+    // TODO(chrishtr): use |displayListDiff| to optimize.

[pdr., 2015/07/24 05:37:51]

Can you expand a little about how the diff would help? Would the DisplayListDiff
contains transform diff information?

[chrishtr, 2015/07/24 14:53:45]

Transform-related display items might occur in the diff. In those cases, some or
all of the transform tree would have to be rebuilt. If no transform-related
display items occur in the diff then the diff can be applied to the display
items comprising the 2D regions between the transform-related display items.

The equivalent optimizations we have today are in the CompositingUpdateType
enums in DeprecatedPaintLayerCompositor:

enum CompositingUpdateType {
    CompositingUpdateNone,
    CompositingUpdateAfterGeometryChange,
    CompositingUpdateAfterCompositingInputChange,
    CompositingUpdateRebuildTree,
};

CompositingUpdateNone is the default, and happens when "regular" invalidations
happen that somehow Blink knows don't affect the size, ordering, quantity and
positioning of the DeprecatedPaintLayers, and so the invalidations can't
possibly affect compositing (though this of course is incorrect already because
of the fundamental compositing bug).

In this case the new system will handle it by the display list diff only
containing changes that are between layerization hint boundaries. This means
that the diff needs to be smart enough that if a hint moves its index in the
display list, but is otherwise unchanged (e.g. its client id is the same), then
it is not part of the diff. This allows non-layerization display items to come
and go as a developer modifies the contents of a composited layer, without
causing rebuild. I think this can be implemented without too much trouble in the
diff algorithm.

If the above properties of the diff algorithm hold, then it should be
straightforward to notice that the transform tree is unchanged in
DisplayItemTransformTreeBuilder, and therefore DisplayListCompsitingBuilder can
use that fact to only invalidate whatever is now dirty inside a composited
layer.

CompositingUpdateAfterGeometryChange happens only when attempting "direct"
compositing updates, which is basically transform, opacity and scrolling of a
transform node. The way this would be implemented in the new system is to have
an update which modifies only the transform display item that implements the
transform, opacity or scrolling update (perhaps via the same functions in
DeprecatedPaintLayer that already set CompositingUpdateAfterGeometryChange
today).

The merge algorithm would output the new display list, plus a diff that says
only the transform display item changed. The code here would then easily notice
that, and compare the old and new transform display items to effect the change.
You might say that this is a lot of work for a simple change, and I agree that
it's the case where the amount of work relative to what is done today is the
highest. My response is that it's important for code sanity and layering to
represent diffs to display lists uniformly, and to make it fast (if necessary)
by optimizing the merge algorithm for such cases to be faster. Though the merge
algorithm already has optimizations for copying common subsequences (implemented
by Xianzhu) that should make this exact case fast. Doing it in a one-off way
will IMO result in difficult to understand code which can poke at compositing
from various places and encourage code layering violations.

The difference between CompositingUpdateAfterCompositingInputChange and
CompositingUpdateRebuildTree is that in
CompositingUpdateAfterCompositingInputChange mode  the code in
DeprecatedPaintLayerCompositor attempts to walk through the algorithm deciding
layerization, and if it manages to make it through without changing any
layerization decisions, it keeps the current tree and mutates its various
geometry parameters based on the new state. Otherwise it bails and performs
CompositingUpdateRebuildTree, which is the full rebuild hammer.

I think the equivalent optimizations for
CompositingUpdateAfterCompositingInputChange can be implemented directly in
DisplayListCompositingBuilder without the guessing process from various call
sites in Blink (e.g. in the call sites in DeprecatedPaintLayer it's not clear
today why exactly those situations deserve
CompositingUpdateAfterCompositingInputChange but others deserve
CompositingUpdateRebuildTree. The difference comes down to "it seems to work"
most of the time).

and GraphicsLayerUpdateScope in CompositedDeprecatedPaintLayerMapping:

enum GraphicsLayerUpdateScope {
    GraphicsLayerUpdateNone,
    GraphicsLayerUpdateLocal,
    GraphicsLayerUpdateSubtree,
};

GraphicsLayerUpdateNone is similar to CompositingUpdateNone, yet more
specialized.

GraphicsLayerUpdateLocal is supposed to be set when you know that a
GraphicsLayer but not its children need to be updated. There are three use cases
of this field. Two are arguably obscure, and the third is the direct compositing
update case that I discussed above in the context of
CompositingUpdateAfterGeometryChange.

+    for (const auto& displayItem : displayList.displayItems()) {
+        processDisplayItem(*displayItem);
+    }
+}
+
 void DisplayItemTransformTreeBuilder::processDisplayItem(const DisplayItem& displayItem)
 {
     if (displayItem.isBegin()) {