Add ICU message format support
[chromium-blink-merge.git] / cc / trees / property_tree.cc
blob0b60d2792678f0cfaf2a9e316c80afc248122f5a
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 TransformTree::TransformTree() : source_to_parent_updates_allowed_(true) {
29 TransformTree::~TransformTree() {
32 template <typename T>
33 int PropertyTree<T>::Insert(const T& tree_node, int parent_id) {
34 DCHECK_GT(nodes_.size(), 0u);
35 nodes_.push_back(tree_node);
36 T& node = nodes_.back();
37 node.parent_id = parent_id;
38 node.id = static_cast<int>(nodes_.size()) - 1;
39 return node.id;
42 template <typename T>
43 void PropertyTree<T>::clear() {
44 nodes_.clear();
45 nodes_.push_back(T());
46 back()->id = 0;
47 back()->parent_id = -1;
50 template class PropertyTree<TransformNode>;
51 template class PropertyTree<ClipNode>;
52 template class PropertyTree<OpacityNode>;
54 TransformNodeData::TransformNodeData()
55 : target_id(-1),
56 content_target_id(-1),
57 source_node_id(-1),
58 needs_local_transform_update(true),
59 is_invertible(true),
60 ancestors_are_invertible(true),
61 is_animated(false),
62 to_screen_is_animated(false),
63 flattens_inherited_transform(false),
64 node_and_ancestors_are_flat(true),
65 node_and_ancestors_have_only_integer_translation(true),
66 scrolls(false),
67 needs_sublayer_scale(false),
68 affected_by_inner_viewport_bounds_delta_x(false),
69 affected_by_inner_viewport_bounds_delta_y(false),
70 affected_by_outer_viewport_bounds_delta_x(false),
71 affected_by_outer_viewport_bounds_delta_y(false),
72 layer_scale_factor(1.0f),
73 post_local_scale_factor(1.0f) {
76 TransformNodeData::~TransformNodeData() {
79 void TransformNodeData::update_pre_local_transform(
80 const gfx::Point3F& transform_origin) {
81 pre_local.MakeIdentity();
82 pre_local.Translate3d(-transform_origin.x(), -transform_origin.y(),
83 -transform_origin.z());
86 void TransformNodeData::update_post_local_transform(
87 const gfx::PointF& position,
88 const gfx::Point3F& transform_origin) {
89 post_local.MakeIdentity();
90 post_local.Scale(post_local_scale_factor, post_local_scale_factor);
91 post_local.Translate3d(
92 position.x() + source_offset.x() + transform_origin.x(),
93 position.y() + source_offset.y() + transform_origin.y(),
94 transform_origin.z());
97 ClipNodeData::ClipNodeData()
98 : transform_id(-1),
99 target_id(-1),
100 inherit_parent_target_space_clip(false) {}
102 OpacityNodeData::OpacityNodeData() : opacity(1.f), screen_space_opacity(1.f) {
105 void TransformTree::clear() {
106 PropertyTree<TransformNode>::clear();
108 nodes_affected_by_inner_viewport_bounds_delta_.clear();
109 nodes_affected_by_outer_viewport_bounds_delta_.clear();
112 bool TransformTree::ComputeTransform(int source_id,
113 int dest_id,
114 gfx::Transform* transform) const {
115 transform->MakeIdentity();
117 if (source_id == dest_id)
118 return true;
120 if (source_id > dest_id) {
121 return CombineTransformsBetween(source_id, dest_id, transform);
124 return CombineInversesBetween(source_id, dest_id, transform);
127 bool TransformTree::ComputeTransformWithDestinationSublayerScale(
128 int source_id,
129 int dest_id,
130 gfx::Transform* transform) const {
131 bool success = ComputeTransform(source_id, dest_id, transform);
133 const TransformNode* dest_node = Node(dest_id);
134 if (!dest_node->data.needs_sublayer_scale)
135 return success;
137 transform->matrix().postScale(dest_node->data.sublayer_scale.x(),
138 dest_node->data.sublayer_scale.y(), 1.f);
139 return success;
142 bool TransformTree::ComputeTransformWithSourceSublayerScale(
143 int source_id,
144 int dest_id,
145 gfx::Transform* transform) const {
146 bool success = ComputeTransform(source_id, dest_id, transform);
148 const TransformNode* source_node = Node(source_id);
149 if (!source_node->data.needs_sublayer_scale)
150 return success;
152 if (source_node->data.sublayer_scale.x() == 0 ||
153 source_node->data.sublayer_scale.y() == 0)
154 return false;
156 transform->Scale(1.f / source_node->data.sublayer_scale.x(),
157 1.f / source_node->data.sublayer_scale.y());
158 return success;
161 bool TransformTree::Are2DAxisAligned(int source_id, int dest_id) const {
162 gfx::Transform transform;
163 return ComputeTransform(source_id, dest_id, &transform) &&
164 transform.Preserves2dAxisAlignment();
167 bool TransformTree::NeedsSourceToParentUpdate(TransformNode* node) {
168 return (source_to_parent_updates_allowed() &&
169 node->parent_id != node->data.source_node_id);
172 void TransformTree::UpdateTransforms(int id) {
173 TransformNode* node = Node(id);
174 TransformNode* parent_node = parent(node);
175 TransformNode* target_node = Node(node->data.target_id);
176 if (node->data.needs_local_transform_update ||
177 NeedsSourceToParentUpdate(node))
178 UpdateLocalTransform(node);
179 UpdateScreenSpaceTransform(node, parent_node, target_node);
180 UpdateSublayerScale(node);
181 UpdateTargetSpaceTransform(node, target_node);
182 UpdateIsAnimated(node, parent_node);
183 UpdateSnapping(node);
184 UpdateNodeAndAncestorsHaveIntegerTranslations(node, parent_node);
187 bool TransformTree::IsDescendant(int desc_id, int source_id) const {
188 while (desc_id != source_id) {
189 if (desc_id < 0)
190 return false;
191 desc_id = Node(desc_id)->parent_id;
193 return true;
196 bool TransformTree::CombineTransformsBetween(int source_id,
197 int dest_id,
198 gfx::Transform* transform) const {
199 DCHECK(source_id > dest_id);
200 const TransformNode* current = Node(source_id);
201 const TransformNode* dest = Node(dest_id);
202 // Combine transforms to and from the screen when possible. Since flattening
203 // is a non-linear operation, we cannot use this approach when there is
204 // non-trivial flattening between the source and destination nodes. For
205 // example, consider the tree R->A->B->C, where B flattens its inherited
206 // transform, and A has a non-flat transform. Suppose C is the source and A is
207 // the destination. The expected result is C * B. But C's to_screen
208 // transform is C * B * flattened(A * R), and A's from_screen transform is
209 // R^{-1} * A^{-1}. If at least one of A and R isn't flat, the inverse of
210 // flattened(A * R) won't be R^{-1} * A{-1}, so multiplying C's to_screen and
211 // A's from_screen will not produce the correct result.
212 if (!dest || (dest->data.ancestors_are_invertible &&
213 dest->data.node_and_ancestors_are_flat)) {
214 transform->ConcatTransform(current->data.to_screen);
215 if (dest)
216 transform->ConcatTransform(dest->data.from_screen);
217 return true;
220 // Flattening is defined in a way that requires it to be applied while
221 // traversing downward in the tree. We first identify nodes that are on the
222 // path from the source to the destination (this is traversing upward), and
223 // then we visit these nodes in reverse order, flattening as needed. We
224 // early-out if we get to a node whose target node is the destination, since
225 // we can then re-use the target space transform stored at that node. However,
226 // we cannot re-use a stored target space transform if the destination has a
227 // zero sublayer scale, since stored target space transforms have sublayer
228 // scale baked in, but we need to compute an unscaled transform.
229 std::vector<int> source_to_destination;
230 source_to_destination.push_back(current->id);
231 current = parent(current);
232 bool destination_has_non_zero_sublayer_scale =
233 dest->data.sublayer_scale.x() != 0.f &&
234 dest->data.sublayer_scale.y() != 0.f;
235 DCHECK(destination_has_non_zero_sublayer_scale ||
236 !dest->data.ancestors_are_invertible);
237 for (; current && current->id > dest_id; current = parent(current)) {
238 if (destination_has_non_zero_sublayer_scale &&
239 current->data.target_id == dest_id &&
240 current->data.content_target_id == dest_id)
241 break;
242 source_to_destination.push_back(current->id);
245 gfx::Transform combined_transform;
246 if (current->id > dest_id) {
247 combined_transform = current->data.to_target;
248 // The stored target space transform has sublayer scale baked in, but we
249 // need the unscaled transform.
250 combined_transform.Scale(1.0f / dest->data.sublayer_scale.x(),
251 1.0f / dest->data.sublayer_scale.y());
252 } else if (current->id < dest_id) {
253 // We have reached the lowest common ancestor of the source and destination
254 // nodes. This case can occur when we are transforming between a node
255 // corresponding to a fixed-position layer (or its descendant) and the node
256 // corresponding to the layer's render target. For example, consider the
257 // layer tree R->T->S->F where F is fixed-position, S owns a render surface,
258 // and T has a significant transform. This will yield the following
259 // transform tree:
260 // R
261 // |
262 // T
263 // /|
264 // S F
265 // In this example, T will have id 2, S will have id 3, and F will have id
266 // 4. When walking up the ancestor chain from F, the first node with a
267 // smaller id than S will be T, the lowest common ancestor of these nodes.
268 // We compute the transform from T to S here, and then from F to T in the
269 // loop below.
270 DCHECK(IsDescendant(dest_id, current->id));
271 CombineInversesBetween(current->id, dest_id, &combined_transform);
272 DCHECK(combined_transform.IsApproximatelyIdentityOrTranslation(
273 SkDoubleToMScalar(1e-4)));
276 size_t source_to_destination_size = source_to_destination.size();
277 for (size_t i = 0; i < source_to_destination_size; ++i) {
278 size_t index = source_to_destination_size - 1 - i;
279 const TransformNode* node = Node(source_to_destination[index]);
280 if (node->data.flattens_inherited_transform)
281 combined_transform.FlattenTo2d();
282 combined_transform.PreconcatTransform(node->data.to_parent);
285 transform->ConcatTransform(combined_transform);
286 return true;
289 bool TransformTree::CombineInversesBetween(int source_id,
290 int dest_id,
291 gfx::Transform* transform) const {
292 DCHECK(source_id < dest_id);
293 const TransformNode* current = Node(dest_id);
294 const TransformNode* dest = Node(source_id);
295 // Just as in CombineTransformsBetween, we can use screen space transforms in
296 // this computation only when there isn't any non-trivial flattening
297 // involved.
298 if (current->data.ancestors_are_invertible &&
299 current->data.node_and_ancestors_are_flat) {
300 transform->PreconcatTransform(current->data.from_screen);
301 if (dest)
302 transform->PreconcatTransform(dest->data.to_screen);
303 return true;
306 // Inverting a flattening is not equivalent to flattening an inverse. This
307 // means we cannot, for example, use the inverse of each node's to_parent
308 // transform, flattening where needed. Instead, we must compute the transform
309 // from the destination to the source, with flattening, and then invert the
310 // result.
311 gfx::Transform dest_to_source;
312 CombineTransformsBetween(dest_id, source_id, &dest_to_source);
313 gfx::Transform source_to_dest;
314 bool all_are_invertible = dest_to_source.GetInverse(&source_to_dest);
315 transform->PreconcatTransform(source_to_dest);
316 return all_are_invertible;
319 void TransformTree::UpdateLocalTransform(TransformNode* node) {
320 gfx::Transform transform = node->data.post_local;
321 if (NeedsSourceToParentUpdate(node)) {
322 gfx::Transform to_parent;
323 ComputeTransform(node->data.source_node_id, node->parent_id, &to_parent);
324 node->data.source_to_parent = to_parent.To2dTranslation();
327 gfx::Vector2dF fixed_position_adjustment;
328 if (node->data.affected_by_inner_viewport_bounds_delta_x)
329 fixed_position_adjustment.set_x(inner_viewport_bounds_delta_.x());
330 else if (node->data.affected_by_outer_viewport_bounds_delta_x)
331 fixed_position_adjustment.set_x(outer_viewport_bounds_delta_.x());
333 if (node->data.affected_by_inner_viewport_bounds_delta_y)
334 fixed_position_adjustment.set_y(inner_viewport_bounds_delta_.y());
335 else if (node->data.affected_by_outer_viewport_bounds_delta_y)
336 fixed_position_adjustment.set_y(outer_viewport_bounds_delta_.y());
338 transform.Translate(
339 node->data.source_to_parent.x() - node->data.scroll_offset.x() +
340 fixed_position_adjustment.x(),
341 node->data.source_to_parent.y() - node->data.scroll_offset.y() +
342 fixed_position_adjustment.y());
343 transform.PreconcatTransform(node->data.local);
344 transform.PreconcatTransform(node->data.pre_local);
345 node->data.set_to_parent(transform);
346 node->data.needs_local_transform_update = false;
349 void TransformTree::UpdateScreenSpaceTransform(TransformNode* node,
350 TransformNode* parent_node,
351 TransformNode* target_node) {
352 if (!parent_node) {
353 node->data.to_screen = node->data.to_parent;
354 node->data.ancestors_are_invertible = true;
355 node->data.to_screen_is_animated = false;
356 node->data.node_and_ancestors_are_flat = node->data.to_parent.IsFlat();
357 } else {
358 node->data.to_screen = parent_node->data.to_screen;
359 if (node->data.flattens_inherited_transform)
360 node->data.to_screen.FlattenTo2d();
361 node->data.to_screen.PreconcatTransform(node->data.to_parent);
362 node->data.ancestors_are_invertible =
363 parent_node->data.ancestors_are_invertible;
364 node->data.node_and_ancestors_are_flat =
365 parent_node->data.node_and_ancestors_are_flat &&
366 node->data.to_parent.IsFlat();
369 if (!node->data.to_screen.GetInverse(&node->data.from_screen))
370 node->data.ancestors_are_invertible = false;
373 void TransformTree::UpdateSublayerScale(TransformNode* node) {
374 // The sublayer scale depends on the screen space transform, so update it too.
375 node->data.sublayer_scale =
376 node->data.needs_sublayer_scale
377 ? MathUtil::ComputeTransform2dScaleComponents(
378 node->data.to_screen, node->data.layer_scale_factor)
379 : gfx::Vector2dF(1.0f, 1.0f);
382 void TransformTree::UpdateTargetSpaceTransform(TransformNode* node,
383 TransformNode* target_node) {
384 if (node->data.needs_sublayer_scale) {
385 node->data.to_target.MakeIdentity();
386 node->data.to_target.Scale(node->data.sublayer_scale.x(),
387 node->data.sublayer_scale.y());
388 } else {
389 const bool target_is_root_surface = target_node->id == 1;
390 // In order to include the root transform for the root surface, we walk up
391 // to the root of the transform tree in ComputeTransform.
392 int target_id = target_is_root_surface ? 0 : target_node->id;
393 ComputeTransformWithDestinationSublayerScale(node->id, target_id,
394 &node->data.to_target);
397 if (!node->data.to_target.GetInverse(&node->data.from_target))
398 node->data.ancestors_are_invertible = false;
401 void TransformTree::UpdateIsAnimated(TransformNode* node,
402 TransformNode* parent_node) {
403 if (parent_node) {
404 node->data.to_screen_is_animated =
405 node->data.is_animated || parent_node->data.to_screen_is_animated;
409 void TransformTree::UpdateSnapping(TransformNode* node) {
410 if (!node->data.scrolls || node->data.to_screen_is_animated ||
411 !node->data.to_target.IsScaleOrTranslation()) {
412 return;
415 // Scroll snapping must be done in target space (the pixels we care about).
416 // This means we effectively snap the target space transform. If TT is the
417 // target space transform and TT' is TT with its translation components
418 // rounded, then what we're after is the scroll delta X, where TT * X = TT'.
419 // I.e., we want a transform that will realize our scroll snap. It follows
420 // that X = TT^-1 * TT'. We cache TT and TT^-1 to make this more efficient.
421 gfx::Transform rounded = node->data.to_target;
422 rounded.RoundTranslationComponents();
423 gfx::Transform delta = node->data.from_target;
424 delta *= rounded;
426 DCHECK(delta.IsApproximatelyIdentityOrTranslation(SkDoubleToMScalar(1e-4)))
427 << delta.ToString();
429 gfx::Vector2dF translation = delta.To2dTranslation();
431 // Now that we have our scroll delta, we must apply it to each of our
432 // combined, to/from matrices.
433 node->data.to_parent.Translate(translation.x(), translation.y());
434 node->data.to_target.Translate(translation.x(), translation.y());
435 node->data.from_target.matrix().postTranslate(-translation.x(),
436 -translation.y(), 0);
437 node->data.to_screen.Translate(translation.x(), translation.y());
438 node->data.from_screen.matrix().postTranslate(-translation.x(),
439 -translation.y(), 0);
441 node->data.scroll_snap = translation;
444 void TransformTree::SetInnerViewportBoundsDelta(gfx::Vector2dF bounds_delta) {
445 if (inner_viewport_bounds_delta_ == bounds_delta)
446 return;
448 inner_viewport_bounds_delta_ = bounds_delta;
450 if (nodes_affected_by_inner_viewport_bounds_delta_.empty())
451 return;
453 set_needs_update(true);
454 for (int i : nodes_affected_by_inner_viewport_bounds_delta_)
455 Node(i)->data.needs_local_transform_update = true;
458 void TransformTree::SetOuterViewportBoundsDelta(gfx::Vector2dF bounds_delta) {
459 if (outer_viewport_bounds_delta_ == bounds_delta)
460 return;
462 outer_viewport_bounds_delta_ = bounds_delta;
464 if (nodes_affected_by_outer_viewport_bounds_delta_.empty())
465 return;
467 set_needs_update(true);
468 for (int i : nodes_affected_by_outer_viewport_bounds_delta_)
469 Node(i)->data.needs_local_transform_update = true;
472 void TransformTree::AddNodeAffectedByInnerViewportBoundsDelta(int node_id) {
473 nodes_affected_by_inner_viewport_bounds_delta_.push_back(node_id);
476 void TransformTree::AddNodeAffectedByOuterViewportBoundsDelta(int node_id) {
477 nodes_affected_by_outer_viewport_bounds_delta_.push_back(node_id);
480 bool TransformTree::HasNodesAffectedByInnerViewportBoundsDelta() const {
481 return !nodes_affected_by_inner_viewport_bounds_delta_.empty();
484 bool TransformTree::HasNodesAffectedByOuterViewportBoundsDelta() const {
485 return !nodes_affected_by_outer_viewport_bounds_delta_.empty();
488 void OpacityTree::UpdateOpacities(int id) {
489 OpacityNode* node = Node(id);
490 node->data.screen_space_opacity = node->data.opacity;
492 OpacityNode* parent_node = parent(node);
493 if (parent_node)
494 node->data.screen_space_opacity *= parent_node->data.screen_space_opacity;
497 void TransformTree::UpdateNodeAndAncestorsHaveIntegerTranslations(
498 TransformNode* node,
499 TransformNode* parent_node) {
500 node->data.node_and_ancestors_have_only_integer_translation =
501 node->data.to_parent.IsIdentityOrIntegerTranslation();
502 if (parent_node)
503 node->data.node_and_ancestors_have_only_integer_translation =
504 node->data.node_and_ancestors_have_only_integer_translation &&
505 parent_node->data.node_and_ancestors_have_only_integer_translation;
508 PropertyTrees::PropertyTrees() : needs_rebuild(true), sequence_number(0) {
511 } // namespace cc