Initial implementation of GeometryMapper

third_party/WebKit/Source/platform/graphics/paint/GeometryMapper.h

Index: third_party/WebKit/Source/platform/graphics/paint/GeometryMapper.h
diff --git a/third_party/WebKit/Source/platform/graphics/paint/GeometryMapper.h b/third_party/WebKit/Source/platform/graphics/paint/GeometryMapper.h
new file mode 100644
index 0000000000000000000000000000000000000000..091ace3804bee8ee6f7cb225a4fc740c3cc4a3f2
--- /dev/null
+++ b/third_party/WebKit/Source/platform/graphics/paint/GeometryMapper.h
@@ -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.
+
+#ifndef GeometryMapper_h
+#define GeometryMapper_h
+
+#include "platform/geometry/FloatRect.h"
+#include "platform/graphics/paint/PropertyTreeState.h"
+#include "platform/transforms/TransformationMatrix.h"
+#include "wtf/HashMap.h"
+
+namespace blink {
+
+struct PrecomputedDataForAncestor {
+    // Maps from a transform node that is a descendant of the ancestor to the combined
+    // transform between the descendant's and the ancestor's coordinate space.
+    HashMap<const TransformPaintPropertyNode*, TransformationMatrix>
+    toAncestorTransforms;

[Xianzhu, 2016/06/22 23:20:30]

Nit: The wrapping looks weird. I would put the above 2 lines into one line.

[chrishtr, 2016/06/23 00:18:26]

Done.

+
+    // Maps from a descendant clip node to its equivalent "clip visual rect" in the space of the ancestor.
+    // The clip visual rect is defined as the intersection of all clips between the descendant
+    // and the ancestor (*not* including the ancestor) in the clip tree, individually transformed from their
+    // localTransformSpace into the ancestor's localTransformSpace.
+    HashMap<const ClipPaintPropertyNode*, FloatRect> toAncestorClipRects;
+};
+
+// GeometryMapper is a helper class for fast computations of transformed and visual rects in different
+// PropertyTreeStates. The design document has a number of details on use cases, algorithmic definitions,
+// and running times.
+//
+// Design document: http://bit.ly/28P4FDA
+//
+// TODO(chrishtr): take effect and scroll trees into account.
+class PLATFORM_EXPORT GeometryMapper {
+public:
+    GeometryMapper() {}
+
+    // The runtime of m calls among LocalToVisibleRectInAncestorSpace, LocalToAncestorRect or AncestorToLocalRect
+    // with the same |ancestorState| parameter is guaranteed to be O(n + m),  where n is the number of transform and clip/

[wkorman, 2016/06/22 23:33:32]

rm '/' after clip

[chrishtr, 2016/06/23 00:18:26]

Done.

+    // nodes in their respective property trees.
+
+    // Maps from a rect in |localTransformSpace| to its visual rect in |ancestorState|. This is computed
+    // by multiplying the rect by its combined transform between |localTransformSpace| and |ancestorSpace|,
+    // then flattening into 2D space, then intersecting by the "clip visual rect" for |localTransformState|'s clips.
+    // See above for the definition of "clip visual rect".
+    //
+    // Note that the clip of |ancestorState| is *not* applied.
+    //
+    // It is an error to call this method if any of the paint property tree nodes in |localTransformState| not equal

[wkorman, 2016/06/22 23:33:32]

are not equal

[chrishtr, 2016/06/23 00:18:27]

Done.

+    // to or a descendat of that in |ancestorState|.

[Xianzhu, 2016/06/22 23:20:30]

Nit: s/descendat/descendant/.

[wkorman, 2016/06/22 23:33:32]

descendant (and 2x more below)

[chrishtr, 2016/06/23 00:18:27]

Done.

+    FloatRect LocalToVisibleRectInAncestorSpace(const FloatRect&,

[Xianzhu, 2016/06/22 23:20:30]

VisualRect?

[wkorman, 2016/06/22 23:33:32]

Visible -> Visual in method name?

[chrishtr, 2016/06/23 00:18:26]

Done.

+        const PropertyTreeState& localTransformState,
+        const PropertyTreeState& ancestorState);
+
+    // Maps from a rect in |localTransformSpace}| to its transformed rect in |ancestorSpace|. This is computed

[Xianzhu, 2016/06/22 23:20:30]

Nit: extra '}'

[chrishtr, 2016/06/23 00:18:27]

Done.

+    // by multiplying the rect by the combined transform between |localTransformState| and |ancestorState|,
+    // then flattening into 2D space.
+    //
+    // It is an error to call this method if any of the paint property tree nodes in |localTransformState| not equal

[wkorman, 2016/06/22 23:33:32]

What would be returned in this case? Should we have success arg here as well?

[chrishtr, 2016/06/23 00:18:27]

Undefined. It should never happen and represents a bug in chrome. I have an
assert in the
implementation that checks for this situation.

+    // to or a descendat of that in |ancestorState|.
+    FloatRect LocalToAncestorRect(const FloatRect&,
+        const PropertyTreeState& localTransformState,
+        const PropertyTreeState& ancestorState);
+
+    // Maps from a rect in |ancestorSpace}| to its transformed rect in |localTransformSpace|. This is computed

[wkorman, 2016/06/22 23:33:32]

rm } before |

[chrishtr, 2016/06/23 00:18:27]

Done.

+    // by multiplying the rect by the inverse combined transform between |localTransformState| and |ancestorState|.
+    //
+    // It is an error to call this method if any of the paint property tree nodes in |localTransformState| not equal
+    // to or a descendat of that in |ancestorState|.
+    FloatRect AncestorToLocalRect(const FloatRect&,

[wkorman, 2016/06/22 23:33:32]

Should briefly comment on success arg and return value in case where mapping
can't be done.

[chrishtr, 2016/06/23 00:18:26]

Done.

+        const PropertyTreeState& localTransformState,
+        const PropertyTreeState& ancestorState, bool* success);
+private:

[Xianzhu, 2016/06/22 23:20:30]

Nit: Insert a blank line before private:.

[chrishtr, 2016/06/23 00:18:26]

Done.

+    // Returns the matrix used in |LocalToAncestorRect|.
+    const TransformationMatrix LocalToAncestorMatrix(
+        const TransformPaintPropertyNode* localTransformState,
+        const PropertyTreeState& ancestorState);
+
+    // Returns the "clip visual rect" between |localTransformState| and |ancestorState|. See above for the definition
+    // of "clip visual rect".
+    const FloatRect LocalToAncestorClipRect(
+        const PropertyTreeState& localTransformState,
+        const PropertyTreeState& ancestorState);
+
+    // Returns the precomputed data if already set, or adds and memoizes a new PrecomputedDataForAncestor otherwise.
+    PrecomputedDataForAncestor* GetPrecomputedDataForAncestor(const PropertyTreeState&);
+
+    friend class GeometryMapperTest;
+
+    HashMap<const TransformPaintPropertyNode*, PrecomputedDataForAncestor> m_data;
+};
+
+} // namespace blink
+
+#endif // GeometryMapper_h