cc: Replace LayerIterator with iterator that walks layer list and effect tree

cc/layers/effect_tree_layer_list_iterator.cc

Index: cc/layers/effect_tree_layer_list_iterator.cc
diff --git a/cc/layers/effect_tree_layer_list_iterator.cc b/cc/layers/effect_tree_layer_list_iterator.cc
new file mode 100644
index 0000000000000000000000000000000000000000..b214f053d8bec63fc666ea9d5bfe8c1706ace04b
--- /dev/null
+++ b/cc/layers/effect_tree_layer_list_iterator.cc
@@ -0,0 +1,137 @@
+// Copyright 2017 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.
+
+#include "cc/layers/effect_tree_layer_list_iterator.h"
+
+namespace cc {
+
+EffectTreeLayerListIterator::EffectTreeLayerListIterator(
+    LayerTreeImpl* layer_tree_impl)
+    : state_(EffectTreeLayerListIterator::State::END),
+      current_effect_tree_index_(EffectTree::kInvalidNodeId),
+      next_effect_tree_index_(EffectTree::kInvalidNodeId),
+      lowest_common_effect_tree_ancestor_index_(EffectTree::kInvalidNodeId),
+      layer_tree_impl_(layer_tree_impl),
+      effect_tree_(&layer_tree_impl->property_trees()->effect_tree) {
+  layer_list_iterator_ = layer_tree_impl->rbegin();
+
+  // Find the front-most drawn layer.
+  while (
+      layer_list_iterator_ != layer_tree_impl->rend() &&
+      !(*layer_list_iterator_)->is_drawn_render_surface_layer_list_member()) {
+    layer_list_iterator_++;
+  }
+
+  // If there are no drawn layers, start at the root render surface, if it
+  // exists.
+  if (layer_list_iterator_ == layer_tree_impl->rend()) {
+    if (effect_tree_->size() > EffectTree::kContentsRootNodeId &&

[jaydasika, 2017/03/22 20:49:42]

Root render surface should always exist, right ? In that case, can this be a
DCHECK ?

[ajuma, 2017/03/24 17:25:07]

Done. A root render surface exists as long as we have at least one layer. There
was a single EffectTreeLayerListIteratorTest that had an empty tree, so I
changed that to a tree with no drawn layers.

+        effect_tree_->GetRenderSurface(EffectTree::kContentsRootNodeId)) {
+      state_ = State::TARGET_SURFACE;
+      current_effect_tree_index_ = EffectTree::kContentsRootNodeId;
+    }
+  } else {
+    state_ = State::LAYER;
+    current_effect_tree_index_ =
+        (*layer_list_iterator_)->render_target_effect_tree_index();
+    next_effect_tree_index_ = current_effect_tree_index_;
+    lowest_common_effect_tree_ancestor_index_ = current_effect_tree_index_;
+  }
+}
+
+EffectTreeLayerListIterator::EffectTreeLayerListIterator(
+    const EffectTreeLayerListIterator& iterator) = default;
+
+EffectTreeLayerListIterator::~EffectTreeLayerListIterator() {}
+
+// Finds the lowest common ancestor that has a render surface.
+static int LowestCommonAncestor(int effect_id_1,
+                                int effect_id_2,
+                                const EffectTree* effect_tree) {
+  while (effect_id_1 != effect_id_2) {
+    if (effect_id_1 < effect_id_2)
+      effect_id_2 = effect_tree->Node(effect_id_2)->target_id;
+    else
+      effect_id_1 = effect_tree->Node(effect_id_1)->target_id;
+  }
+
+  return effect_id_1;
+}
+
+void EffectTreeLayerListIterator::operator++() {
+  switch (state_) {
+    case State::LAYER:
+      // Find the next drawn layer.
+      layer_list_iterator_++;
+      while (layer_list_iterator_ != layer_tree_impl_->rend() &&
+             !(*layer_list_iterator_)
+                  ->is_drawn_render_surface_layer_list_member()) {
+        layer_list_iterator_++;
+      }
+      if (layer_list_iterator_ == layer_tree_impl_->rend()) {
+        next_effect_tree_index_ = EffectTree::kInvalidNodeId;
+        lowest_common_effect_tree_ancestor_index_ = EffectTree::kInvalidNodeId;
+        state_ = State::TARGET_SURFACE;
+        break;

[jaydasika, 2017/03/22 20:49:42]

Should current_effect_tree_index_ be set to EffectTree::kContentsRootId here ?

[ajuma, 2017/03/24 17:25:07]

Not necessarily, it should (already) be the render target effect tree index of
the last drawn layer. This might be kContentsRoodId, but can also be something
else if the last drawn layer contributes to some other surface (e.g., if we have
the layer tree root->filter->layer, where |layer| is the only layer that draws
content, then current_effect_tree_index_ would be |filter|'s effect node id).

+      }
+
+      next_effect_tree_index_ =
+          (*layer_list_iterator_)->render_target_effect_tree_index();
+
+      // If the next drawn layer has a different target effect tree index, check
+      // for surfaces whose contributors have all been visited.
+      if (next_effect_tree_index_ != current_effect_tree_index_) {
+        lowest_common_effect_tree_ancestor_index_ = LowestCommonAncestor(
+            current_effect_tree_index_, next_effect_tree_index_, effect_tree_);
+        // If the current layer's target effect node is an ancestor of the next
+        // layer's target effect node, then the current effect node still has
+        // more contributors that need to be visited. Otherwise, all
+        // contributors have been visited, so we visit the node's surface next.
+        if (current_effect_tree_index_ ==
+            lowest_common_effect_tree_ancestor_index_) {
+          current_effect_tree_index_ = next_effect_tree_index_;
+          lowest_common_effect_tree_ancestor_index_ = next_effect_tree_index_;
+        } else {
+          state_ = State::TARGET_SURFACE;
+        }
+      }
+      break;
+    case State::TARGET_SURFACE:
+      if (current_effect_tree_index_ == EffectTree::kContentsRootNodeId) {
+        current_effect_tree_index_ = EffectTree::kInvalidNodeId;
+        state_ = State::END;
+        DCHECK(next_effect_tree_index_ == EffectTree::kInvalidNodeId);
+        DCHECK(layer_list_iterator_ == layer_tree_impl_->rend());
+      } else {
+        state_ = State::CONTRIBUTING_SURFACE;
+      }
+      break;
+    case State::CONTRIBUTING_SURFACE:
+      DCHECK(current_effect_tree_index_ !=
+             lowest_common_effect_tree_ancestor_index_);
+      // Step towards the lowest common ancestor.
+      current_effect_tree_index_ =
+          effect_tree_->Node(current_effect_tree_index_)->target_id;
+      if (current_effect_tree_index_ == next_effect_tree_index_) {
+        state_ = State::LAYER;
+      } else if (current_effect_tree_index_ ==
+                 lowest_common_effect_tree_ancestor_index_) {
+        // In this case, we know that more content contributes to the current
+        // effect node (since the next effect node is a descendant), so we're
+        // not yet ready to visit it as a target surface. The same holds for all
+        // effect nodes on the path from the current node to the next effect
+        // tree node.
+        state_ = State::LAYER;
+        current_effect_tree_index_ = next_effect_tree_index_;
+        lowest_common_effect_tree_ancestor_index_ = next_effect_tree_index_;
+      } else {
+        state_ = State::TARGET_SURFACE;

[jaydasika, 2017/03/22 20:49:42]

Is there an underlying assumption here that
lowest_common_effect_tree_ancestor_index_ = next_effect_tree_index_ in this case
? If yes, is that always true ?

[ajuma, 2017/03/24 17:25:07]

No, the assumption is only that the lowest_common_effect_tree_ancestor_index
node is a proper ancestor of the current_effect_tree_index node. That means
there can't be anything else contributing to the current node. Added a comment
about this.

+      }
+      break;
+    case State::END:
+      NOTREACHED();
+  }
+}
+
+}  // namespace cc