Introduce LayerListIterator

This iterator (unlike the other iterators which are intended to operate
on the RSLL) will traverse a collection of LayerImpls. It is intended
to be used whenever we currently do a walk over the LayerImpl tree.

It currently operates on a tree of layers, but if we migrate all code
to work in terms of this iterator, when we change the underlying
iterator implementation to work on lists, all code will be updated in
unison.

BUG=557194
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Review URL: https://codereview.chromium.org/1758823003

Cr-Commit-Position: refs/heads/master@{#378827}

diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index ce1a7c5..023c7ba 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn

@@ -133,6 +133,8 @@
     "layers/layer_impl.cc",
     "layers/layer_impl.h",
     "layers/layer_iterator.h",
+    "layers/layer_list_iterator.cc",
+    "layers/layer_list_iterator.h",
     "layers/layer_lists.h",
     "layers/layer_position_constraint.cc",
     "layers/layer_position_constraint.h",
@@ -785,6 +787,7 @@
     "layers/io_surface_layer_impl_unittest.cc",
     "layers/layer_impl_unittest.cc",
     "layers/layer_iterator_unittest.cc",
+    "layers/layer_list_iterator_unittest.cc",
     "layers/layer_position_constraint_unittest.cc",
     "layers/layer_proto_converter_unittest.cc",
     "layers/layer_unittest.cc",

diff --git a/cc/cc.gyp b/cc/cc.gyp
index 62afc299..bffecd1 100644
--- a/cc/cc.gyp
+++ b/cc/cc.gyp

@@ -195,6 +195,8 @@
         'layers/layer_impl.cc',
         'layers/layer_impl.h',
         'layers/layer_iterator.h',
+        'layers/layer_list_iterator.cc',
+        'layers/layer_list_iterator.h',
         'layers/layer_lists.h',
         'layers/layer_position_constraint.cc',
         'layers/layer_position_constraint.h',

diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp
index 91933d6..6aea39c 100644
--- a/cc/cc_tests.gyp
+++ b/cc/cc_tests.gyp

@@ -42,6 +42,7 @@
       'layers/io_surface_layer_impl_unittest.cc',
       'layers/layer_impl_unittest.cc',
       'layers/layer_iterator_unittest.cc',
+      'layers/layer_list_iterator_unittest.cc',
       'layers/layer_position_constraint_unittest.cc',
       'layers/layer_proto_converter_unittest.cc',
       'layers/layer_unittest.cc',

diff --git a/cc/layers/layer_list_iterator.cc b/cc/layers/layer_list_iterator.cc
new file mode 100644
index 0000000..858440b
--- /dev/null
+++ b/cc/layers/layer_list_iterator.cc

@@ -0,0 +1,96 @@
+// Copyright 2016 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/layer_list_iterator.h"
+
+#include "cc/layers/layer_impl.h"
+
+namespace cc {
+
+LayerListIterator::LayerListIterator(LayerImpl* root_layer)
+    : current_layer_(root_layer) {
+  DCHECK(!root_layer || !root_layer->parent());
+  list_indices_.push_back(0);
+}
+
+LayerListIterator::~LayerListIterator() {}
+
+LayerListIterator& LayerListIterator::operator++() {
+  // case 0: done
+  if (!current_layer_)
+    return *this;
+
+  // case 1: descend.
+  const OwnedLayerImplList& current_list = current_layer_->children();
+  if (!current_list.empty()) {
+    current_layer_ = current_list[0].get();
+    list_indices_.push_back(0);
+    return *this;
+  }
+
+  for (LayerImpl* parent = current_layer_->parent(); parent;
+       parent = parent->parent()) {
+    // We now try and advance in some list of siblings.
+    const OwnedLayerImplList& sibling_list = parent->children();
+
+    // case 2: Advance to a sibling.
+    if (list_indices_.back() + 1 < sibling_list.size()) {
+      ++list_indices_.back();
+      current_layer_ = sibling_list[list_indices_.back()].get();
+      return *this;
+    }
+
+    // We need to ascend. We will pop an index off the stack.
+    list_indices_.pop_back();
+  }
+
+  current_layer_ = nullptr;
+  return *this;
+}
+
+LayerListReverseIterator::LayerListReverseIterator(LayerImpl* root_layer)
+    : LayerListIterator(root_layer) {
+  DescendToRightmostInSubtree();
+}
+
+LayerListReverseIterator::~LayerListReverseIterator() {}
+
+// We will only support prefix increment.
+LayerListIterator& LayerListReverseIterator::operator++() {
+  // case 0: done
+  if (!current_layer_)
+    return *this;
+
+  // case 1: we're the leftmost sibling.
+  if (!list_indices_.back()) {
+    list_indices_.pop_back();
+    current_layer_ = current_layer_->parent();
+    return *this;
+  }
+
+  // case 2: we're not the leftmost sibling. In this case, we want to move one
+  // sibling over, and then descend to the rightmost descendant in that subtree.
+  CHECK(current_layer_->parent());
+  --list_indices_.back();
+  const OwnedLayerImplList& parent_list = current_layer_->parent()->children();
+  current_layer_ = parent_list[list_indices_.back()].get();
+  DescendToRightmostInSubtree();
+  return *this;
+}
+
+void LayerListReverseIterator::DescendToRightmostInSubtree() {
+  if (!current_layer_)
+    return;
+
+  const OwnedLayerImplList& current_list = current_layer_->children();
+  if (current_list.empty())
+    return;
+
+  size_t last_index = current_list.size() - 1;
+  current_layer_ = current_list[last_index].get();
+  list_indices_.push_back(last_index);
+  DescendToRightmostInSubtree();
+}
+
+}  // namespace cc

diff --git a/cc/layers/layer_list_iterator.h b/cc/layers/layer_list_iterator.h
new file mode 100644
index 0000000..ba3c4d2
--- /dev/null
+++ b/cc/layers/layer_list_iterator.h

@@ -0,0 +1,62 @@
+// Copyright 2016 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.
+
+#ifndef CC_LAYERS_LAYER_LIST_ITERATOR_H_
+#define CC_LAYERS_LAYER_LIST_ITERATOR_H_
+
+#include <stdlib.h>
+#include <vector>
+
+#include "cc/base/cc_export.h"
+
+namespace cc {
+
+class LayerImpl;
+
+// Unlike LayerIterator and friends, these iterators are not intended to permit
+// traversing the RSLL. Rather, they visit a collection of LayerImpls in
+// stacking order. All recursive walks over the LayerImpl tree should be
+// switched to use these classes instead as the concept of a LayerImpl tree is
+// deprecated.
+class CC_EXPORT LayerListIterator {
+ public:
+  explicit LayerListIterator(LayerImpl* root_layer);
+  virtual ~LayerListIterator();
+
+  bool operator==(const LayerListIterator& other) const {
+    return current_layer_ == other.current_layer_;
+  }
+
+  bool operator!=(const LayerListIterator& other) const {
+    return !(*this == other);
+  }
+
+  // We will only support prefix increment.
+  virtual LayerListIterator& operator++();
+  LayerImpl* operator->() const { return current_layer_; }
+  LayerImpl* operator*() const { return current_layer_; }
+
+ protected:
+  // The implementation of this iterator is currently tied tightly to the layer
+  // tree, but it should be straightforward to reimplement in terms of a list
+  // when it's ready.
+  LayerImpl* current_layer_;
+  std::vector<size_t> list_indices_;
+};
+
+class CC_EXPORT LayerListReverseIterator : public LayerListIterator {
+ public:
+  explicit LayerListReverseIterator(LayerImpl* root_layer);
+  ~LayerListReverseIterator() override;
+
+  // We will only support prefix increment.
+  LayerListIterator& operator++() override;
+
+ private:
+  void DescendToRightmostInSubtree();
+};
+
+}  // namespace cc
+
+#endif  // CC_LAYERS_LAYER_LIST_ITERATOR_H_

diff --git a/cc/layers/layer_list_iterator_unittest.cc b/cc/layers/layer_list_iterator_unittest.cc
new file mode 100644
index 0000000..eca2b3c
--- /dev/null
+++ b/cc/layers/layer_list_iterator_unittest.cc

@@ -0,0 +1,179 @@
+// Copyright 2016 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/layer_list_iterator.h"
+
+#include "base/memory/scoped_ptr.h"
+#include "cc/test/fake_impl_task_runner_provider.h"
+#include "cc/test/fake_layer_tree_host_impl.h"
+#include "cc/test/fake_output_surface.h"
+#include "cc/test/test_shared_bitmap_manager.h"
+#include "cc/test/test_task_graph_runner.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace cc {
+namespace {
+
+TEST(LayerListIteratorTest, VerifyTraversalOrder) {
+  // Unfortunate preamble.
+  FakeImplTaskRunnerProvider task_runner_provider;
+  TestSharedBitmapManager shared_bitmap_manager;
+  TestTaskGraphRunner task_graph_runner;
+  scoped_ptr<OutputSurface> output_surface = FakeOutputSurface::Create3d();
+  FakeLayerTreeHostImpl host_impl(&task_runner_provider, &shared_bitmap_manager,
+                                  &task_graph_runner);
+  host_impl.SetVisible(true);
+  EXPECT_TRUE(host_impl.InitializeRenderer(output_surface.get()));
+
+  // This test constructs the following tree.
+  // 1
+  // +-2
+  // | +-3
+  // | +-4
+  // + 5
+  //   +-6
+  //   +-7
+  // We expect to visit all seven layers in that order.
+  scoped_ptr<LayerImpl> layer1 = LayerImpl::Create(host_impl.active_tree(), 1);
+  scoped_ptr<LayerImpl> layer2 = LayerImpl::Create(host_impl.active_tree(), 2);
+  scoped_ptr<LayerImpl> layer3 = LayerImpl::Create(host_impl.active_tree(), 3);
+  scoped_ptr<LayerImpl> layer4 = LayerImpl::Create(host_impl.active_tree(), 4);
+  scoped_ptr<LayerImpl> layer5 = LayerImpl::Create(host_impl.active_tree(), 5);
+  scoped_ptr<LayerImpl> layer6 = LayerImpl::Create(host_impl.active_tree(), 6);
+  scoped_ptr<LayerImpl> layer7 = LayerImpl::Create(host_impl.active_tree(), 7);
+
+  layer2->AddChild(std::move(layer3));
+  layer2->AddChild(std::move(layer4));
+
+  layer5->AddChild(std::move(layer6));
+  layer5->AddChild(std::move(layer7));
+
+  layer1->AddChild(std::move(layer2));
+  layer1->AddChild(std::move(layer5));
+
+  int i = 1;
+  LayerListIterator it(layer1.get());
+  LayerListIterator end(nullptr);
+  for (; it != end; ++it, ++i) {
+    EXPECT_EQ(i, it->id());
+  }
+  EXPECT_EQ(8, i);
+}
+
+TEST(LayerListIteratorTest, VerifySingleLayer) {
+  // Unfortunate preamble.
+  FakeImplTaskRunnerProvider task_runner_provider;
+  TestSharedBitmapManager shared_bitmap_manager;
+  TestTaskGraphRunner task_graph_runner;
+  scoped_ptr<OutputSurface> output_surface = FakeOutputSurface::Create3d();
+  FakeLayerTreeHostImpl host_impl(&task_runner_provider, &shared_bitmap_manager,
+                                  &task_graph_runner);
+  host_impl.SetVisible(true);
+  EXPECT_TRUE(host_impl.InitializeRenderer(output_surface.get()));
+
+  // This test constructs a tree consisting of a single layer.
+  scoped_ptr<LayerImpl> layer1 = LayerImpl::Create(host_impl.active_tree(), 1);
+  int i = 1;
+  LayerListIterator it(layer1.get());
+  LayerListIterator end(nullptr);
+  for (; it != end; ++it, ++i) {
+    EXPECT_EQ(i, it->id());
+  }
+  EXPECT_EQ(2, i);
+}
+
+TEST(LayerListIteratorTest, VerifyNullFirstLayer) {
+  // Ensures that if an iterator is constructed with a nullptr, that it can be
+  // iterated without issue and that it remains equal to any other
+  // null-initialized iterator.
+  LayerListIterator it(nullptr);
+  LayerListIterator end(nullptr);
+
+  EXPECT_EQ(it, end);
+  ++it;
+  EXPECT_EQ(it, end);
+}
+
+TEST(LayerListReverseIteratorTest, VerifyTraversalOrder) {
+  // Unfortunate preamble.
+  FakeImplTaskRunnerProvider task_runner_provider;
+  TestSharedBitmapManager shared_bitmap_manager;
+  TestTaskGraphRunner task_graph_runner;
+  scoped_ptr<OutputSurface> output_surface = FakeOutputSurface::Create3d();
+  FakeLayerTreeHostImpl host_impl(&task_runner_provider, &shared_bitmap_manager,
+                                  &task_graph_runner);
+  host_impl.SetVisible(true);
+  EXPECT_TRUE(host_impl.InitializeRenderer(output_surface.get()));
+
+  // This test constructs the following tree.
+  // 1
+  // +-2
+  // | +-3
+  // | +-4
+  // + 5
+  //   +-6
+  //   +-7
+  // We expect to visit all seven layers in reverse order.
+  scoped_ptr<LayerImpl> layer1 = LayerImpl::Create(host_impl.active_tree(), 1);
+  scoped_ptr<LayerImpl> layer2 = LayerImpl::Create(host_impl.active_tree(), 2);
+  scoped_ptr<LayerImpl> layer3 = LayerImpl::Create(host_impl.active_tree(), 3);
+  scoped_ptr<LayerImpl> layer4 = LayerImpl::Create(host_impl.active_tree(), 4);
+  scoped_ptr<LayerImpl> layer5 = LayerImpl::Create(host_impl.active_tree(), 5);
+  scoped_ptr<LayerImpl> layer6 = LayerImpl::Create(host_impl.active_tree(), 6);
+  scoped_ptr<LayerImpl> layer7 = LayerImpl::Create(host_impl.active_tree(), 7);
+
+  layer2->AddChild(std::move(layer3));
+  layer2->AddChild(std::move(layer4));
+
+  layer5->AddChild(std::move(layer6));
+  layer5->AddChild(std::move(layer7));
+
+  layer1->AddChild(std::move(layer2));
+  layer1->AddChild(std::move(layer5));
+
+  int i = 7;
+  LayerListReverseIterator it(layer1.get());
+  LayerListReverseIterator end(nullptr);
+  for (; it != end; ++it, --i) {
+    EXPECT_EQ(i, it->id());
+  }
+  EXPECT_EQ(0, i);
+}
+
+TEST(LayerListReverseIteratorTest, VerifySingleLayer) {
+  // Unfortunate preamble.
+  FakeImplTaskRunnerProvider task_runner_provider;
+  TestSharedBitmapManager shared_bitmap_manager;
+  TestTaskGraphRunner task_graph_runner;
+  scoped_ptr<OutputSurface> output_surface = FakeOutputSurface::Create3d();
+  FakeLayerTreeHostImpl host_impl(&task_runner_provider, &shared_bitmap_manager,
+                                  &task_graph_runner);
+  host_impl.SetVisible(true);
+  EXPECT_TRUE(host_impl.InitializeRenderer(output_surface.get()));
+
+  // This test constructs a tree consisting of a single layer.
+  scoped_ptr<LayerImpl> layer1 = LayerImpl::Create(host_impl.active_tree(), 1);
+  int i = 1;
+  LayerListReverseIterator it(layer1.get());
+  LayerListReverseIterator end(nullptr);
+  for (; it != end; ++it, --i) {
+    EXPECT_EQ(i, it->id());
+  }
+  EXPECT_EQ(0, i);
+}
+
+TEST(LayerListReverseIteratorTest, VerifyNullFirstLayer) {
+  // Ensures that if an iterator is constructed with a nullptr, that it can be
+  // iterated without issue and that it remains equal to any other
+  // null-initialized iterator.
+  LayerListReverseIterator it(nullptr);
+  LayerListReverseIterator end(nullptr);
+
+  EXPECT_EQ(it, end);
+  ++it;
+  EXPECT_EQ(it, end);
+}
+
+}  // namespace
+}  // namespace cc