GeometryMapper: Support computing visual rects in spaces that are not direct ancestors.

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

 // 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.
 
 #include "platform/graphics/paint/GeometryMapper.h"
 
 #include "platform/geometry/LayoutRect.h"
 #include "platform/graphics/paint/ClipPaintPropertyNode.h"
 #include "platform/graphics/paint/EffectPaintPropertyNode.h"
 #include "platform/graphics/paint/TransformPaintPropertyNode.h"
+#include "wtf/HashSet.h"
 
 namespace blink {
 
-FloatRect GeometryMapper::LocalToVisualRectInAncestorSpace(
+PassRefPtr<TransformPaintPropertyNode> GeometryMapper::leastCommonAncestor(PassRefPtr<TransformPaintPropertyNode> a, PassRefPtr<TransformPaintPropertyNode> b)
+{
+    HashSet<RefPtr<TransformPaintPropertyNode>> intermediates;

[pdr., 2016/07/01 18:39:40]

We may want to use a lowest common ancestor approach that doesn't allocate like
nearestCommonAncestor in PaintArtifactCompositor.

[chrishtr, 2016/07/01 22:01:12]

Refactored to reuse that code, templated for all property tree types.

+    RefPtr<TransformPaintPropertyNode> currA = a;
+    RefPtr<TransformPaintPropertyNode> currB = b;
+    while (currA || currB) {
+        if (currA) {
+            auto it = intermediates.find(currA);
+            if (it != intermediates.end())
+                return *it;
+            intermediates.add(currA);
+            currA = currA->parent();
+        }
+
+        if (currB) {
+            auto it = intermediates.find(currB);
+            if (it != intermediates.end())
+                return *it;
+            intermediates.add(currB);
+            currB = currB->parent();
+        }
+    }
+    CHECK(false);
+    return nullptr;
+}
+
+FloatRect GeometryMapper::mapToVisualRectInDestinationSpace(const FloatRect& rect,
+    const PropertyTreeState& sourceState,
+    const PropertyTreeState& destinationState,
+    bool* success)
+{
+    FloatRect result = localToVisualRectInAncestorSpace(rect, sourceState, destinationState, success);
+    if (*success)
+        return result;
+
+    RefPtr<TransformPaintPropertyNode> lcaTransform = leastCommonAncestor(sourceState.transform.get(), destinationState.transform.get());
+    DCHECK(lcaTransform.get());
+    PropertyTreeState lcaState = sourceState;
+    lcaState.transform = lcaTransform;
+
+    result = localToAncestorMatrix(sourceState.transform.get(), lcaState, success).mapRect(rect);
+    DCHECK(*success);
+
+    const TransformationMatrix& destinationToLca = localToAncestorMatrix(destinationState.transform.get(), lcaState, success);
+    DCHECK(*success);
+    if (destinationToLca.isInvertible()) {
+        *success = true;
+        return destinationToLca.inverse().mapRect(result);
+    }
+    *success = false;
+    return rect;
+}
+
+FloatRect GeometryMapper::localToVisualRectInAncestorSpace(
     const FloatRect& rect,
     const PropertyTreeState& localState,
-    const PropertyTreeState& ancestorState)
+    const PropertyTreeState& ancestorState, bool* success)
 {
-    const auto transformMatrix = LocalToAncestorMatrix(localState.transform, ancestorState);
+    const auto transformMatrix = localToAncestorMatrix(localState.transform.get(), ancestorState, success);
+    if (!(*success))
+        return rect;
+
     FloatRect mappedRect = transformMatrix.mapRect(rect);
 
-    const auto clipRect = LocalToAncestorClipRect(localState, ancestorState);
+    const auto clipRect = localToAncestorClipRect(localState, ancestorState);
 
     mappedRect.intersect(clipRect);
     return mappedRect;
 }
 
-FloatRect GeometryMapper::LocalToAncestorRect(
+FloatRect GeometryMapper::localToAncestorRect(
     const FloatRect& rect,
     const PropertyTreeState& localState,
-    const PropertyTreeState& ancestorState)
+    const PropertyTreeState& ancestorState,
+    bool* success)
 {
-    const auto transformMatrix = LocalToAncestorMatrix(localState.transform, ancestorState);
+    const auto transformMatrix = localToAncestorMatrix(localState.transform.get(), ancestorState, success);
+    if (!(*success))
+        return rect;
     return transformMatrix.mapRect(rect);
 }
 
-FloatRect GeometryMapper::AncestorToLocalRect(
+FloatRect GeometryMapper::ancestorToLocalRect(
     const FloatRect& rect,
     const PropertyTreeState& localState,
     const PropertyTreeState& ancestorState, bool* success)
 {
-    const auto& transformMatrix = LocalToAncestorMatrix(localState.transform, ancestorState);
+    const auto& transformMatrix = localToAncestorMatrix(localState.transform.get(), ancestorState, success);
+    if (!(*success))
+        return rect;
+
     if (!transformMatrix.isInvertible()) {
         *success = false;
-        return FloatRect();
+        return rect;
     }
     *success = true;
 
     // TODO(chrishtr): Cache the inverse?
     return transformMatrix.inverse().mapRect(rect);
 }
 
-PrecomputedDataForAncestor& GeometryMapper::GetPrecomputedDataForAncestor(const PropertyTreeState& ancestorState)
+PrecomputedDataForAncestor& GeometryMapper::getPrecomputedDataForAncestor(const PropertyTreeState& ancestorState)
 {
-    auto addResult = m_data.add(ancestorState.transform, nullptr);
+    auto addResult = m_data.add(ancestorState.transform.get(), nullptr);
     if (addResult.isNewEntry)
         addResult.storedValue->value = PrecomputedDataForAncestor::create();
     return *addResult.storedValue->value;
 }
 
-const FloatRect& GeometryMapper::LocalToAncestorClipRect(
+const FloatRect& GeometryMapper::localToAncestorClipRect(
     const PropertyTreeState& localState,
     const PropertyTreeState& ancestorState)
 {
-    PrecomputedDataForAncestor& precomputedData = GetPrecomputedDataForAncestor(ancestorState);
-    const ClipPaintPropertyNode* clipNode = localState.clip;
+    PrecomputedDataForAncestor& precomputedData = getPrecomputedDataForAncestor(ancestorState);
+    const ClipPaintPropertyNode* clipNode = localState.clip.get();
     Vector<const ClipPaintPropertyNode*> intermediateNodes;
     FloatRect clip(LayoutRect::infiniteIntRect());
 
     bool found = false;
     // Iterate over the path from localState.clip to ancestorState.clip. Stop if we've found a memoized (precomputed) clip
     // for any particular node.
     while (clipNode) {
         auto it = precomputedData.toAncestorClipRects.find(clipNode);
         if (it != precomputedData.toAncestorClipRects.end()) {
             clip = it->value;
             found = true;
             break;
         }
         intermediateNodes.append(clipNode);
 
         if (clipNode == ancestorState.clip)
             break;
 
         clipNode = clipNode->parent();
     }
     // It's illegal to ask for a local-to-ancestor clip when the ancestor is not an ancestor.
     DCHECK(clipNode == ancestorState.clip || found);
 
     // Iterate down from the top intermediate node found in the previous loop, computing and memoizing clip rects as we go.
     for (auto it = intermediateNodes.rbegin(); it != intermediateNodes.rend(); ++it) {
         if ((*it) != ancestorState.clip) {
-            const TransformationMatrix transformMatrix = LocalToAncestorMatrix((*it)->localTransformSpace(), ancestorState);
+            bool success = false;
+            const TransformationMatrix transformMatrix = localToAncestorMatrix((*it)->localTransformSpace(), ancestorState, &success);
+            DCHECK(success);
             FloatRect mappedRect = transformMatrix.mapRect((*it)->clipRect().rect());
             clip.intersect(mappedRect);
         }
 
         precomputedData.toAncestorClipRects.set(*it, clip);
     }
 
-    return precomputedData.toAncestorClipRects.find(localState.clip)->value;
+    return precomputedData.toAncestorClipRects.find(localState.clip.get())->value;
 }
 
-const TransformationMatrix& GeometryMapper::LocalToAncestorMatrix(
+const TransformationMatrix& GeometryMapper::localToAncestorMatrix(
     const TransformPaintPropertyNode* localTransformNode,
-    const PropertyTreeState& ancestorState) {
-    PrecomputedDataForAncestor& precomputedData = GetPrecomputedDataForAncestor(ancestorState);
+    const PropertyTreeState& ancestorState, bool* success) {
+    PrecomputedDataForAncestor& precomputedData = getPrecomputedDataForAncestor(ancestorState);
 
     const TransformPaintPropertyNode* transformNode = localTransformNode;
     Vector<const TransformPaintPropertyNode*> intermediateNodes;
     TransformationMatrix transformMatrix;
 
     bool found = false;
     // Iterate over the path from localTransformNode to ancestorState.transform. Stop if we've found a memoized (precomputed) transform
     // for any particular node.
     while (transformNode) {
         auto it = precomputedData.toAncestorTransforms.find(transformNode);
         if (it != precomputedData.toAncestorTransforms.end()) {
             transformMatrix = it->value;
             found = true;
             break;
         }
 
         intermediateNodes.append(transformNode);
 
         if (transformNode == ancestorState.transform)
             break;
 
         transformNode = transformNode->parent();
     }
-    // It's illegal to ask for a local-to-ancestor matrix when the ancestor is not an ancestor.
-    DCHECK(transformNode == ancestorState.transform || found);
+    if (!found && transformNode != ancestorState.transform) {
+        *success = false;
+        return m_identity;

[pdr., 2016/07/01 18:39:40]

Instead of using a member, you can use a static like so:
static const AffineTransform identity;

[chrishtr, 2016/07/01 22:01:12]

That doesn't work, because it requires a global constructor, which is disallowed
in our compilation flags. The other alternative is to have a static that is
demand-allocated,
but IMO the code as-is seems ok.

+    }
 
     // Iterate down from the top intermediate node found in the previous loop, computing and memoizing transforms as we go.
     for (auto it = intermediateNodes.rbegin(); it != intermediateNodes.rend(); it++) {
         if ((*it) != ancestorState.transform) {
             TransformationMatrix localTransformMatrix = (*it)->matrix();
             localTransformMatrix.applyTransformOrigin((*it)->origin());
             transformMatrix = localTransformMatrix * transformMatrix;
         }
 
         precomputedData.toAncestorTransforms.set(*it, transformMatrix);
     }
+    *success = true;
     return precomputedData.toAncestorTransforms.find(localTransformNode)->value;
 }
 
 } // namespace blink