1// Copyright 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef CC_LAYERS_LAYER_ITERATOR_H_
6#define CC_LAYERS_LAYER_ITERATOR_H_
7
8#include "cc/base/cc_export.h"
9#include "cc/trees/layer_tree_host_common.h"
10
11namespace cc {
12
13// These classes provide means to iterate over the
14// RenderSurface-Layer tree.
15
16// Example code follows, for a tree of Layer/RenderSurface objects.
17// See below for details.
18//
19// void DoStuffOnLayers(
20//     const RenderSurfaceLayerList& render_surface_layer_list) {
21//   typedef LayerIterator<Layer> LayerIteratorType;
22//
23//   LayerIteratorType end =
24//       LayerIteratorType::End(&render_surface_layer_list);
25//   for (LayerIteratorType
26//            it = LayerIteratorType::Begin(&render_surface_layer_list);
27//        it != end;
28//        ++it) {
29//     // Only one of these will be true
30//     if (it.represents_target_render_surface())
31//       foo(*it);  // *it is a layer representing a target RenderSurface
32//     if (it.represents_contributing_render_surface())
33//       bar(*it);  // *it is a layer representing a RenderSurface that
34//                  // contributes to the layer's target RenderSurface
35//     if (it.represents_itself())
36//       baz(*it);  // *it is a layer representing itself,
37//                  // as it contributes to its own target RenderSurface
38//   }
39// }
40
41// A RenderSurface R may be referred to in one of two different contexts.
42// One RenderSurface is "current" at any time, for whatever operation
43// is being performed. This current surface is referred to as a target surface.
44// For example, when R is being painted it would be the target surface.
45// Once R has been painted, its contents may be included into another
46// surface S. While S is considered the target surface when it is being
47// painted, R is called a contributing surface in this context as it
48// contributes to the content of the target surface S.
49//
50// The iterator's current position in the tree always points to some layer.
51// The state of the iterator indicates the role of the layer,
52// and will be one of the following three states.
53// A single layer L will appear in the iteration process in at least one,
54// and possibly all, of these states.
55// 1. Representing the target surface: The iterator in this state,
56// pointing at layer L, indicates that the target RenderSurface
57// is now the surface owned by L. This will occur exactly once for each
58// RenderSurface in the tree.
59// 2. Representing a contributing surface: The iterator in this state,
60// pointing at layer L, refers to the RenderSurface owned
61// by L as a contributing surface, without changing the current
62// target RenderSurface.
63// 3. Representing itself: The iterator in this state, pointing at layer L,
64// refers to the layer itself, as a child of the
65// current target RenderSurface.
66//
67// The FrontToBack iterator will iterate over children layers of a surface
68// before the layer representing the surface as a target surface.
69//
70// To use the iterators:
71//
72// Create a stepping iterator and end iterator by calling
73// LayerIterator::Begin() and LayerIterator::End() and passing in the
74// list of layers owning target RenderSurfaces. Step through the tree
75// by incrementing the stepping iterator while it is != to
76// the end iterator. At each step the iterator knows what the layer
77// is representing, and you can query the iterator to decide
78// what actions to perform with the layer given what it represents.
79
80////////////////////////////////////////////////////////////////////////////////
81
82// Non-templated constants
83struct LayerIteratorValue {
84  static const int kInvalidTargetRenderSurfaceLayerIndex = -1;
85  // This must be -1 since the iterator action code assumes that this value can
86  // be reached by subtracting one from the position of the first layer in the
87  // current target surface's child layer list, which is 0.
88  static const int kLayerIndexRepresentingTargetRenderSurface = -1;
89};
90
91// The position of a layer iterator that is independent
92// of its many template types.
93template <typename LayerType> struct LayerIteratorPosition {
94  bool represents_target_render_surface;
95  bool represents_contributing_render_surface;
96  bool represents_itself;
97  LayerType* target_render_surface_layer;
98  LayerType* current_layer;
99};
100
101// An iterator class for walking over layers in the
102// RenderSurface-Layer tree.
103template <typename LayerType>
104class LayerIterator {
105  typedef LayerIterator<LayerType> LayerIteratorType;
106  typedef typename LayerType::LayerListType LayerList;
107  typedef typename LayerType::RenderSurfaceListType RenderSurfaceLayerList;
108  typedef typename LayerType::RenderSurfaceType RenderSurfaceType;
109
110 public:
111  LayerIterator() : render_surface_layer_list_(NULL) {}
112
113  static LayerIteratorType Begin(
114      const RenderSurfaceLayerList* render_surface_layer_list) {
115    return LayerIteratorType(render_surface_layer_list, true);
116  }
117  static LayerIteratorType End(
118      const RenderSurfaceLayerList* render_surface_layer_list) {
119    return LayerIteratorType(render_surface_layer_list, false);
120  }
121
122  LayerIteratorType& operator++() {
123    MoveToNext();
124    return *this;
125  }
126  bool operator==(const LayerIterator& other) const {
127    return target_render_surface_layer_index_ ==
128           other.target_render_surface_layer_index_ &&
129           current_layer_index_ == other.current_layer_index_;
130  }
131  bool operator!=(const LayerIteratorType& other) const {
132    return !(*this == other);
133  }
134
135  LayerType* operator->() const { return current_layer(); }
136  LayerType* operator*() const { return current_layer(); }
137
138  bool represents_target_render_surface() const {
139    return current_layer_represents_target_render_surface();
140  }
141  bool represents_contributing_render_surface() const {
142    return !represents_target_render_surface() &&
143           current_layer_represents_contributing_render_surface();
144  }
145  bool represents_itself() const {
146    return !represents_target_render_surface() &&
147           !represents_contributing_render_surface();
148  }
149
150  LayerType* target_render_surface_layer() const {
151    return render_surface_layer_list_->at(target_render_surface_layer_index_);
152  }
153
154  operator const LayerIteratorPosition<LayerType>() const {
155    LayerIteratorPosition<LayerType> position;
156    position.represents_target_render_surface =
157        represents_target_render_surface();
158    position.represents_contributing_render_surface =
159        represents_contributing_render_surface();
160    position.represents_itself = represents_itself();
161    position.target_render_surface_layer = target_render_surface_layer();
162    position.current_layer = current_layer();
163    return position;
164  }
165
166 private:
167  LayerIterator(const RenderSurfaceLayerList* render_surface_layer_list,
168                bool start)
169      : render_surface_layer_list_(render_surface_layer_list),
170        target_render_surface_layer_index_(0) {
171    for (size_t i = 0; i < render_surface_layer_list->size(); ++i) {
172      if (!render_surface_layer_list->at(i)->render_surface()) {
173        NOTREACHED();
174        MoveToEnd();
175        return;
176      }
177    }
178
179    if (start && !render_surface_layer_list->empty())
180      MoveToBegin();
181    else
182      MoveToEnd();
183  }
184
185  void MoveToBegin() {
186    target_render_surface_layer_index_ = 0;
187    current_layer_index_ = target_render_surface_children().size() - 1;
188    MoveToHighestInSubtree();
189  }
190
191  void MoveToEnd() {
192    target_render_surface_layer_index_ =
193        LayerIteratorValue::kInvalidTargetRenderSurfaceLayerIndex;
194    current_layer_index_ = 0;
195  }
196
197  void MoveToNext() {
198    // Moves to the previous layer in the current RS layer list.
199    // Then we check if the new current layer has its own RS,
200    // in which case there are things in that RS layer list that are higher,
201    // so we find the highest layer in that subtree.
202    // If we move back past the front of the list,
203    // we jump up to the previous RS layer list, picking up again where we
204    // had previously recursed into the current RS layer list.
205
206    if (!current_layer_represents_target_render_surface()) {
207      // Subtracting one here will eventually cause the current layer
208      // to become that layer representing the target render surface.
209      --current_layer_index_;
210      MoveToHighestInSubtree();
211    } else {
212      while (current_layer_represents_target_render_surface()) {
213        if (!target_render_surface_layer_index_) {
214          // End of the list.
215          target_render_surface_layer_index_ =
216              LayerIteratorValue::kInvalidTargetRenderSurfaceLayerIndex;
217          current_layer_index_ = 0;
218          return;
219        }
220        target_render_surface_layer_index_ =
221            target_render_surface()->target_render_surface_layer_index_history_;
222        current_layer_index_ =
223            target_render_surface()->current_layer_index_history_;
224      }
225    }
226  }
227
228  void MoveToHighestInSubtree() {
229    if (current_layer_represents_target_render_surface())
230      return;
231    while (current_layer_represents_contributing_render_surface()) {
232      // Save where we were in the current target surface, move to the next one,
233      // and save the target surface that we came from there
234      // so we can go back to it.
235      target_render_surface()->current_layer_index_history_ =
236          current_layer_index_;
237      int previous_target_render_surface_layer =
238          target_render_surface_layer_index_;
239
240      for (LayerType* layer = current_layer();
241           target_render_surface_layer() != layer;
242           ++target_render_surface_layer_index_) {
243      }
244      current_layer_index_ = target_render_surface_children().size() - 1;
245
246      target_render_surface()->target_render_surface_layer_index_history_ =
247          previous_target_render_surface_layer;
248    }
249  }
250
251  inline LayerType* current_layer() const {
252    return current_layer_represents_target_render_surface()
253               ? target_render_surface_layer()
254               : LayerTreeHostCommon::get_layer_as_raw_ptr(
255                     target_render_surface_children(), current_layer_index_);
256  }
257
258  inline bool current_layer_represents_contributing_render_surface() const {
259    return LayerTreeHostCommon::RenderSurfaceContributesToTarget<LayerType>(
260        current_layer(), target_render_surface_layer()->id());
261  }
262  inline bool current_layer_represents_target_render_surface() const {
263    return current_layer_index_ ==
264           LayerIteratorValue::kLayerIndexRepresentingTargetRenderSurface;
265  }
266
267  inline RenderSurfaceType* target_render_surface() const {
268    return target_render_surface_layer()->render_surface();
269  }
270  inline const LayerList& target_render_surface_children() const {
271    return target_render_surface()->layer_list();
272  }
273
274  const RenderSurfaceLayerList* render_surface_layer_list_;
275
276  // The iterator's current position.
277
278  // A position in the render_surface_layer_list. This points to a layer which
279  // owns the current target surface. This is a value from 0 to n-1
280  // (n = size of render_surface_layer_list = number of surfaces).
281  // A value outside of this range
282  // (for example, LayerIteratorValue::kInvalidTargetRenderSurfaceLayerIndex)
283  // is used to indicate a position outside the bounds of the tree.
284  int target_render_surface_layer_index_;
285  // A position in the list of layers that are children of the
286  // current target surface. When pointing to one of these layers,
287  // this is a value from 0 to n-1 (n = number of children).
288  // Since the iterator must also stop at the layers representing
289  // the target surface, this is done by setting the current_layerIndex
290  // to a value of LayerIteratorValue::LayerRepresentingTargetRenderSurface.
291  int current_layer_index_;
292};
293
294}  // namespace cc
295
296#endif  // CC_LAYERS_LAYER_ITERATOR_H_
297