Don't show supervised user as "already on this device" while they're being imported.
[chromium-blink-merge.git] / cc / trees / property_tree.cc
blobd96e9aa56653555e04e9de238c47f82a68169201
1 // Copyright 2014 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.
5 #include <set>
6 #include <vector>
8 #include "base/logging.h"
9 #include "cc/base/math_util.h"
10 #include "cc/trees/property_tree.h"
12 namespace cc {
14 template <typename T>
15 PropertyTree<T>::PropertyTree()
16 : needs_update_(false) {
17 nodes_.push_back(T());
18 back()->id = 0;
19 back()->parent_id = -1;
22 template <typename T>
23 PropertyTree<T>::~PropertyTree() {
26 template <typename T>
27 int PropertyTree<T>::Insert(const T& tree_node, int parent_id) {
28 DCHECK_GT(nodes_.size(), 0u);
29 nodes_.push_back(tree_node);
30 T& node = nodes_.back();
31 node.parent_id = parent_id;
32 node.id = static_cast<int>(nodes_.size()) - 1;
33 return node.id;
36 template <typename T>
37 void PropertyTree<T>::clear() {
38 nodes_.clear();
39 nodes_.push_back(T());
40 back()->id = 0;
41 back()->parent_id = -1;
44 template class PropertyTree<TransformNode>;
45 template class PropertyTree<ClipNode>;
46 template class PropertyTree<OpacityNode>;
48 TransformNodeData::TransformNodeData()
49 : target_id(-1),
50 content_target_id(-1),
51 source_node_id(-1),
52 needs_local_transform_update(true),
53 is_invertible(true),
54 ancestors_are_invertible(true),
55 is_animated(false),
56 to_screen_is_animated(false),
57 flattens_inherited_transform(false),
58 node_and_ancestors_are_flat(true),
59 scrolls(false),
60 needs_sublayer_scale(false),
61 layer_scale_factor(1.0f),
62 post_local_scale_factor(1.0f) {
65 TransformNodeData::~TransformNodeData() {
68 void TransformNodeData::update_pre_local_transform(
69 const gfx::Point3F& transform_origin) {
70 pre_local.MakeIdentity();
71 pre_local.Translate3d(-transform_origin.x(), -transform_origin.y(),
72 -transform_origin.z());
75 void TransformNodeData::update_post_local_transform(
76 const gfx::PointF& position,
77 const gfx::Point3F& transform_origin) {
78 post_local.MakeIdentity();
79 post_local.Scale(post_local_scale_factor, post_local_scale_factor);
80 post_local.Translate3d(
81 position.x() + source_offset.x() + transform_origin.x(),
82 position.y() + source_offset.y() + transform_origin.y(),
83 transform_origin.z());
86 ClipNodeData::ClipNodeData() : transform_id(-1), target_id(-1) {
89 bool TransformTree::ComputeTransform(int source_id,
90 int dest_id,
91 gfx::Transform* transform) const {
92 transform->MakeIdentity();
94 if (source_id == dest_id)
95 return true;
97 if (source_id > dest_id) {
98 return CombineTransformsBetween(source_id, dest_id, transform);
101 return CombineInversesBetween(source_id, dest_id, transform);
104 bool TransformTree::ComputeTransformWithDestinationSublayerScale(
105 int source_id,
106 int dest_id,
107 gfx::Transform* transform) const {
108 bool success = ComputeTransform(source_id, dest_id, transform);
110 const TransformNode* dest_node = Node(dest_id);
111 if (!dest_node->data.needs_sublayer_scale)
112 return success;
114 transform->matrix().postScale(dest_node->data.sublayer_scale.x(),
115 dest_node->data.sublayer_scale.y(), 1.f);
116 return success;
119 bool TransformTree::ComputeTransformWithSourceSublayerScale(
120 int source_id,
121 int dest_id,
122 gfx::Transform* transform) const {
123 bool success = ComputeTransform(source_id, dest_id, transform);
125 const TransformNode* source_node = Node(source_id);
126 if (!source_node->data.needs_sublayer_scale)
127 return success;
129 transform->Scale(1.f / source_node->data.sublayer_scale.x(),
130 1.f / source_node->data.sublayer_scale.y());
131 return success;
134 bool TransformTree::Are2DAxisAligned(int source_id, int dest_id) const {
135 gfx::Transform transform;
136 return ComputeTransform(source_id, dest_id, &transform) &&
137 transform.Preserves2dAxisAlignment();
140 void TransformTree::UpdateTransforms(int id) {
141 TransformNode* node = Node(id);
142 TransformNode* parent_node = parent(node);
143 TransformNode* target_node = Node(node->data.target_id);
144 if (node->data.needs_local_transform_update ||
145 node->parent_id != node->data.source_node_id)
146 UpdateLocalTransform(node);
147 UpdateScreenSpaceTransform(node, parent_node, target_node);
148 UpdateSublayerScale(node);
149 UpdateTargetSpaceTransform(node, target_node);
150 UpdateIsAnimated(node, parent_node);
151 UpdateSnapping(node);
154 bool TransformTree::IsDescendant(int desc_id, int source_id) const {
155 while (desc_id != source_id) {
156 if (desc_id < 0)
157 return false;
158 desc_id = Node(desc_id)->parent_id;
160 return true;
163 bool TransformTree::CombineTransformsBetween(int source_id,
164 int dest_id,
165 gfx::Transform* transform) const {
166 DCHECK(source_id > dest_id);
167 const TransformNode* current = Node(source_id);
168 const TransformNode* dest = Node(dest_id);
169 // Combine transforms to and from the screen when possible. Since flattening
170 // is a non-linear operation, we cannot use this approach when there is
171 // non-trivial flattening between the source and destination nodes. For
172 // example, consider the tree R->A->B->C, where B flattens its inherited
173 // transform, and A has a non-flat transform. Suppose C is the source and A is
174 // the destination. The expected result is C * B. But C's to_screen
175 // transform is C * B * flattened(A * R), and A's from_screen transform is
176 // R^{-1} * A^{-1}. If at least one of A and R isn't flat, the inverse of
177 // flattened(A * R) won't be R^{-1} * A{-1}, so multiplying C's to_screen and
178 // A's from_screen will not produce the correct result.
179 if (!dest || (dest->data.ancestors_are_invertible &&
180 dest->data.node_and_ancestors_are_flat)) {
181 transform->ConcatTransform(current->data.to_screen);
182 if (dest)
183 transform->ConcatTransform(dest->data.from_screen);
184 return true;
187 // Flattening is defined in a way that requires it to be applied while
188 // traversing downward in the tree. We first identify nodes that are on the
189 // path from the source to the destination (this is traversing upward), and
190 // then we visit these nodes in reverse order, flattening as needed. We
191 // early-out if we get to a node whose target node is the destination, since
192 // we can then re-use the target space transform stored at that node.
193 std::vector<int> source_to_destination;
194 source_to_destination.push_back(current->id);
195 current = parent(current);
196 for (; current && current->id > dest_id; current = parent(current)) {
197 if (current->data.target_id == dest_id &&
198 current->data.content_target_id == dest_id)
199 break;
200 source_to_destination.push_back(current->id);
203 gfx::Transform combined_transform;
204 if (current->id > dest_id) {
205 combined_transform = current->data.to_target;
206 // The stored target space transform has sublayer scale baked in, but we
207 // need the unscaled transform.
208 combined_transform.Scale(1.0f / dest->data.sublayer_scale.x(),
209 1.0f / dest->data.sublayer_scale.y());
210 } else if (current->id < dest_id) {
211 // We have reached the lowest common ancestor of the source and destination
212 // nodes. This case can occur when we are transforming between a node
213 // corresponding to a fixed-position layer (or its descendant) and the node
214 // corresponding to the layer's render target. For example, consider the
215 // layer tree R->T->S->F where F is fixed-position, S owns a render surface,
216 // and T has a significant transform. This will yield the following
217 // transform tree:
218 // R
219 // |
220 // T
221 // /|
222 // S F
223 // In this example, T will have id 2, S will have id 3, and F will have id
224 // 4. When walking up the ancestor chain from F, the first node with a
225 // smaller id than S will be T, the lowest common ancestor of these nodes.
226 // We compute the transform from T to S here, and then from F to T in the
227 // loop below.
228 DCHECK(IsDescendant(dest_id, current->id));
229 CombineInversesBetween(current->id, dest_id, &combined_transform);
230 DCHECK(combined_transform.IsApproximatelyIdentityOrTranslation(
231 SkDoubleToMScalar(1e-4)));
234 for (int i = source_to_destination.size() - 1; i >= 0; i--) {
235 const TransformNode* node = Node(source_to_destination[i]);
236 if (node->data.flattens_inherited_transform)
237 combined_transform.FlattenTo2d();
238 combined_transform.PreconcatTransform(node->data.to_parent);
241 transform->ConcatTransform(combined_transform);
242 return true;
245 bool TransformTree::CombineInversesBetween(int source_id,
246 int dest_id,
247 gfx::Transform* transform) const {
248 DCHECK(source_id < dest_id);
249 const TransformNode* current = Node(dest_id);
250 const TransformNode* dest = Node(source_id);
251 // Just as in CombineTransformsBetween, we can use screen space transforms in
252 // this computation only when there isn't any non-trivial flattening
253 // involved.
254 if (current->data.ancestors_are_invertible &&
255 current->data.node_and_ancestors_are_flat) {
256 transform->PreconcatTransform(current->data.from_screen);
257 if (dest)
258 transform->PreconcatTransform(dest->data.to_screen);
259 return true;
262 // Inverting a flattening is not equivalent to flattening an inverse. This
263 // means we cannot, for example, use the inverse of each node's to_parent
264 // transform, flattening where needed. Instead, we must compute the transform
265 // from the destination to the source, with flattening, and then invert the
266 // result.
267 gfx::Transform dest_to_source;
268 CombineTransformsBetween(dest_id, source_id, &dest_to_source);
269 gfx::Transform source_to_dest;
270 bool all_are_invertible = dest_to_source.GetInverse(&source_to_dest);
271 transform->PreconcatTransform(source_to_dest);
272 return all_are_invertible;
275 void TransformTree::UpdateLocalTransform(TransformNode* node) {
276 gfx::Transform transform = node->data.post_local;
277 gfx::Vector2dF source_to_parent;
278 if (node->parent_id != node->data.source_node_id) {
279 gfx::Transform to_parent;
280 ComputeTransform(node->data.source_node_id, node->parent_id, &to_parent);
281 source_to_parent = to_parent.To2dTranslation();
283 transform.Translate(source_to_parent.x() - node->data.scroll_offset.x(),
284 source_to_parent.y() - node->data.scroll_offset.y());
285 transform.PreconcatTransform(node->data.local);
286 transform.PreconcatTransform(node->data.pre_local);
287 node->data.set_to_parent(transform);
288 node->data.needs_local_transform_update = false;
291 void TransformTree::UpdateScreenSpaceTransform(TransformNode* node,
292 TransformNode* parent_node,
293 TransformNode* target_node) {
294 if (!parent_node) {
295 node->data.to_screen = node->data.to_parent;
296 node->data.ancestors_are_invertible = true;
297 node->data.to_screen_is_animated = false;
298 node->data.node_and_ancestors_are_flat = node->data.to_parent.IsFlat();
299 } else {
300 node->data.to_screen = parent_node->data.to_screen;
301 if (node->data.flattens_inherited_transform)
302 node->data.to_screen.FlattenTo2d();
303 node->data.to_screen.PreconcatTransform(node->data.to_parent);
304 node->data.ancestors_are_invertible =
305 parent_node->data.ancestors_are_invertible;
306 node->data.node_and_ancestors_are_flat =
307 parent_node->data.node_and_ancestors_are_flat &&
308 node->data.to_parent.IsFlat();
311 if (!node->data.to_screen.GetInverse(&node->data.from_screen))
312 node->data.ancestors_are_invertible = false;
315 void TransformTree::UpdateSublayerScale(TransformNode* node) {
316 // The sublayer scale depends on the screen space transform, so update it too.
317 node->data.sublayer_scale =
318 node->data.needs_sublayer_scale
319 ? MathUtil::ComputeTransform2dScaleComponents(
320 node->data.to_screen, node->data.layer_scale_factor)
321 : gfx::Vector2dF(1.0f, 1.0f);
324 void TransformTree::UpdateTargetSpaceTransform(TransformNode* node,
325 TransformNode* target_node) {
326 if (node->data.needs_sublayer_scale) {
327 node->data.to_target.MakeIdentity();
328 node->data.to_target.Scale(node->data.sublayer_scale.x(),
329 node->data.sublayer_scale.y());
330 } else {
331 const bool target_is_root_surface = target_node->id == 1;
332 // In order to include the root transform for the root surface, we walk up
333 // to the root of the transform tree in ComputeTransform.
334 int target_id = target_is_root_surface ? 0 : target_node->id;
335 ComputeTransformWithDestinationSublayerScale(node->id, target_id,
336 &node->data.to_target);
339 if (!node->data.to_target.GetInverse(&node->data.from_target))
340 node->data.ancestors_are_invertible = false;
343 void TransformTree::UpdateIsAnimated(TransformNode* node,
344 TransformNode* parent_node) {
345 if (parent_node) {
346 node->data.to_screen_is_animated =
347 node->data.is_animated || parent_node->data.to_screen_is_animated;
351 void TransformTree::UpdateSnapping(TransformNode* node) {
352 if (!node->data.scrolls || node->data.to_screen_is_animated ||
353 !node->data.to_target.IsScaleOrTranslation()) {
354 return;
357 // Scroll snapping must be done in target space (the pixels we care about).
358 // This means we effectively snap the target space transform. If TT is the
359 // target space transform and TT' is TT with its translation components
360 // rounded, then what we're after is the scroll delta X, where TT * X = TT'.
361 // I.e., we want a transform that will realize our scroll snap. It follows
362 // that X = TT^-1 * TT'. We cache TT and TT^-1 to make this more efficient.
363 gfx::Transform rounded = node->data.to_target;
364 rounded.RoundTranslationComponents();
365 gfx::Transform delta = node->data.from_target;
366 delta *= rounded;
368 DCHECK(delta.IsApproximatelyIdentityOrTranslation(SkDoubleToMScalar(1e-4)))
369 << delta.ToString();
371 gfx::Vector2dF translation = delta.To2dTranslation();
373 // Now that we have our scroll delta, we must apply it to each of our
374 // combined, to/from matrices.
375 node->data.to_parent.Translate(translation.x(), translation.y());
376 node->data.to_target.Translate(translation.x(), translation.y());
377 node->data.from_target.matrix().postTranslate(-translation.x(),
378 -translation.y(), 0);
379 node->data.to_screen.Translate(translation.x(), translation.y());
380 node->data.from_screen.matrix().postTranslate(-translation.x(),
381 -translation.y(), 0);
383 node->data.scroll_snap = translation;
386 PropertyTrees::PropertyTrees() : needs_rebuild(true), sequence_number(0) {
389 } // namespace cc