Update from https://crrev.com/308996

cc/trees/property_tree.h

+// Copyright 2014 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_TREES_PROPERTY_TREE_H_
+#define CC_TREES_PROPERTY_TREE_H_
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "cc/base/cc_export.h"
+#include "ui/gfx/rect.h"
+#include "ui/gfx/transform.h"
+
+namespace cc {
+
+template <typename T>
+struct CC_EXPORT TreeNode {
+  TreeNode() : id(-1), parent_id(-1), data() {}
+  int id;
+  int parent_id;
+  T data;
+};
+
+struct CC_EXPORT TransformNodeData {
+  TransformNodeData();
+  ~TransformNodeData();
+
+  gfx::Transform to_parent;
+  gfx::Transform from_parent;
+
+  gfx::Transform to_screen;
+  gfx::Transform from_screen;
+
+  int target_id;
+
+  bool is_invertible;
+  bool ancestors_are_invertible;
+
+  bool is_animated;
+  bool to_screen_is_animated;
+
+  bool flattens;
+
+  void set_to_parent(const gfx::Transform& transform) {
+    to_parent = transform;
+    is_invertible = to_parent.GetInverse(&from_parent);
+  }
+};
+
+typedef TreeNode<TransformNodeData> TransformNode;
+
+struct CC_EXPORT ClipNodeData {
+  ClipNodeData();
+
+  gfx::RectF clip;
+  gfx::RectF combined_clip;
+  int transform_id;
+  int target_id;
+};
+
+typedef TreeNode<ClipNodeData> ClipNode;
+
+template <typename T>
+class CC_EXPORT PropertyTree {
+ public:
+  PropertyTree();
+  virtual ~PropertyTree();
+
+  int Insert(const T& tree_node, int parent_id);
+
+  T* Node(int i) { return i > -1 ? &nodes_[i] : nullptr; }
+  const T* Node(int i) const { return i > -1 ? &nodes_[i] : nullptr; }
+
+  T* parent(const T* t) {
+    return t->parent_id > -1 ? Node(t->parent_id) : nullptr;
+  }
+  const T* parent(const T* t) const {
+    return t->parent_id > -1 ? Node(t->parent_id) : nullptr;
+  }
+
+  T* back() { return size() ? &nodes_[nodes_.size() - 1] : nullptr; }
+  const T* back() const {
+    return size() ? &nodes_[nodes_.size() - 1] : nullptr;
+  }
+
+  void clear() { nodes_.clear(); }
+  size_t size() const { return nodes_.size(); }
+
+ private:
+  // Copy and assign are permitted. This is how we do tree sync.
+  std::vector<T> nodes_;
+};
+
+class CC_EXPORT TransformTree final : public PropertyTree<TransformNode> {
+ public:
+  // Computes the change of basis transform from node |source_id| to |dest_id|.
+  // The function returns false iff the inverse of a singular transform was
+  // used (and the result should, therefore, not be trusted).
+  bool ComputeTransform(int source_id,
+                        int dest_id,
+                        gfx::Transform* transform) const;
+
+  // Returns true iff the nodes indexed by |source_id| and |dest_id| are 2D axis
+  // aligned with respect to one another.
+  bool Are2DAxisAligned(int source_id, int dest_id) const;
+
+  // This recomputes the screen space transform (and its inverse) for the node
+  // at |id|.
+  void UpdateScreenSpaceTransform(int id);
+
+ private:
+  // Returns true iff the node at |desc_id| is a descendant of the node at
+  // |anc_id|.
+  bool IsDescendant(int desc_id, int anc_id) const;
+
+  // Returns the index of the lowest common ancestor of the nodes |a| and |b|.
+  int LowestCommonAncestor(int a, int b) const;
+
+  // Computes the combined transform between |source_id| and |dest_id| and
+  // returns false if the inverse of a singular transform was used. These two
+  // nodes must be on the same ancestor chain.
+  bool CombineTransformsBetween(int source_id,
+                                int dest_id,
+                                gfx::Transform* transform) const;
+
+  // Computes the combined inverse transform between |source_id| and |dest_id|
+  // and returns false if the inverse of a singular transform was used. These
+  // two nodes must be on the same ancestor chain.
+  bool CombineInversesBetween(int source_id,
+                              int dest_id,
+                              gfx::Transform* transform) const;
+};
+
+class CC_EXPORT ClipTree final : public PropertyTree<ClipNode> {};
+
+}  // namespace cc
+
+#endif  // CC_TREES_PROPERTY_TREE_H_