path: root/chromium/third_party/blink/renderer/platform/graphics/paint/geometry_mapper.h

// 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 THIRD_PARTY_BLINK_RENDERER_PLATFORM_GRAPHICS_PAINT_GEOMETRY_MAPPER_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_GRAPHICS_PAINT_GEOMETRY_MAPPER_H_

#include "base/optional.h"
#include "third_party/blink/renderer/platform/graphics/overlay_scrollbar_clip_behavior.h"
#include "third_party/blink/renderer/platform/graphics/paint/float_clip_rect.h"
#include "third_party/blink/renderer/platform/graphics/paint/property_tree_state.h"
#include "third_party/blink/renderer/platform/transforms/transformation_matrix.h"
#include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
#include "third_party/blink/renderer/platform/wtf/hash_map.h"

namespace blink {

// Clips can use FloatRect::Intersect or FloatRect::InclusiveIntersect.
enum InclusiveIntersectOrNot { kNonInclusiveIntersect, kInclusiveIntersect };

// Whether to expand the visual or clip rect to infinity when we meet any
// animating transform or filter when walking from a descendant state to an
// ancestor state, when mapping a visual rect or getting the accumulated clip
// rect. After we expanded the rect, we will still apply ancestor clips when
// continuing walking up the tree. TODO(crbug.com/1026653): Consider animation
// bounds instead of using infinite rect.
enum ExpandVisualRectForAnimationOrNot {
  kDontExpandVisualRectForAnimation,
  kExpandVisualRectForAnimation,
};

// 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.
//
// NOTE: A GeometryMapper object is only valid for property trees that do not
// change. If any mutation occurs, a new GeometryMapper object must be allocated
// corresponding to the new state.
//
// Design document: http://bit.ly/28P4FDA
class PLATFORM_EXPORT GeometryMapper {
  STATIC_ONLY(GeometryMapper);

 public:
  // The return value of SourceToDestinationProjection. If the result is known
  // to be accumulation of 2d translations, |matrix| is nullptr, and
  // |translation_2d| is the accumulated 2d translation. Otherwise |matrix|
  // points to the accumulated projection, and |translation_2d| is zero.
  class Translation2DOrMatrix {
    DISALLOW_NEW();

   public:
    Translation2DOrMatrix() { DCHECK(IsIdentity()); }
    explicit Translation2DOrMatrix(const FloatSize& translation_2d)
        : translation_2d_(translation_2d) {
      DCHECK(IsIdentityOr2DTranslation());
    }
    explicit Translation2DOrMatrix(const TransformationMatrix& matrix)
        : matrix_(matrix) {
      DCHECK(!IsIdentityOr2DTranslation());
    }

    bool IsIdentity() const { return !matrix_ && translation_2d_.IsZero(); }
    bool IsIdentityOr2DTranslation() const { return !matrix_; }
    const FloatSize& Translation2D() const {
      DCHECK(IsIdentityOr2DTranslation());
      return translation_2d_;
    }
    const TransformationMatrix& Matrix() const {
      DCHECK(!IsIdentityOr2DTranslation());
      return *matrix_;
    }

    template <typename Rect>
    void MapRect(Rect& rect) const {
      if (LIKELY(IsIdentityOr2DTranslation()))
        MoveRect(rect, Translation2D());
      else
        rect = Matrix().MapRect(rect);
    }

    void MapQuad(FloatQuad& quad) const {
      if (LIKELY(IsIdentityOr2DTranslation()))
        quad.Move(Translation2D());
      else
        quad = Matrix().MapQuad(quad);
    }

    void MapFloatClipRect(FloatClipRect& rect) const {
      if (LIKELY(IsIdentityOr2DTranslation()))
        rect.MoveBy(FloatPoint(Translation2D()));
      else
        rect.Map(Matrix());
    }

    FloatPoint MapPoint(const FloatPoint& point) const {
      if (LIKELY(IsIdentityOr2DTranslation()))
        return point + Translation2D();
      return Matrix().MapPoint(point);
    }

    void PostTranslate(float x, float y) {
      if (LIKELY(IsIdentityOr2DTranslation()))
        translation_2d_.Expand(x, y);
      else
        matrix_->PostTranslate(x, y);
    }

    SkM44 ToSkM44() const { return TransformationMatrix::ToSkM44(Matrix()); }

    SkMatrix ToSkMatrix() const {
      if (LIKELY(IsIdentityOr2DTranslation())) {
        return SkMatrix::Translate(Translation2D().Width(),
                                   Translation2D().Height());
      }
      return SkMatrix(TransformationMatrix::ToSkMatrix44(Matrix()));
    }

    bool operator==(const Translation2DOrMatrix& other) {
      return translation_2d_ == other.translation_2d_ &&
             matrix_ == other.matrix_;
    }

    bool operator!=(const Translation2DOrMatrix& other) {
      return !(*this == other);
    }

   private:
    FloatSize translation_2d_;
    base::Optional<TransformationMatrix> matrix_;
  };

  // Returns the matrix that is suitable to map geometries on the source plane
  // to some backing in the destination plane.
  // Formal definition:
  //   output = flatten(destination_to_screen)^-1 * flatten(source_to_screen)
  // There are some cases that flatten(destination_to_screen) being
  // singular yet we can still define a reasonable projection, for example:
  // 1. Both nodes inherited a common singular flat ancestor:
  // 2. Both nodes are co-planar to a common singular ancestor:
  // Not every cases outlined above are supported!
  // Read implementation comments for specific restrictions.
  static Translation2DOrMatrix SourceToDestinationProjection(
      const TransformPaintPropertyNodeOrAlias& source,
      const TransformPaintPropertyNodeOrAlias& destination) {
    return SourceToDestinationProjection(source.Unalias(),
                                         destination.Unalias());
  }
  static Translation2DOrMatrix SourceToDestinationProjection(
      const TransformPaintPropertyNode& source,
      const TransformPaintPropertyNode& destination);

  // Same as SourceToDestinationProjection() except that it maps the rect
  // rather than returning the matrix.
  // |mapping_rect| is both input and output. Its type can be FloatRect,
  // LayoutRect or IntRect.
  template <typename Rect>
  static void SourceToDestinationRect(
      const TransformPaintPropertyNodeOrAlias& source,
      const TransformPaintPropertyNodeOrAlias& destination,
      Rect& mapping_rect) {
    SourceToDestinationRect(source.Unalias(), destination.Unalias(),
                            mapping_rect);
  }
  template <typename Rect>
  static void SourceToDestinationRect(
      const TransformPaintPropertyNode& source,
      const TransformPaintPropertyNode& destination,
      Rect& mapping_rect) {
    if (&source == &destination)
      return;

    // Fast-path optimization for mapping through just |source| when |source| is
    // a 2d translation.
    if (&destination == source.Parent() && source.IsIdentityOr2DTranslation()) {
      MoveRect(mapping_rect, source.Translation2D());
      return;
    }

    // Fast-path optimization for mapping through just |destination| when
    // |destination| is a 2d translation.
    if (&source == destination.Parent() &&
        destination.IsIdentityOr2DTranslation()) {
      MoveRect(mapping_rect, -destination.Translation2D());
      return;
    }

    bool has_animation = false;
    bool success = false;
    const auto& source_to_destination = SourceToDestinationProjectionInternal(
        source, destination, has_animation, success);
    if (!success)
      mapping_rect = Rect();
    else
      source_to_destination.MapRect(mapping_rect);
  }

  // Returns the clip rect between |local_state| and |ancestor_state|. The clip
  // rect is the total clip rect that should be applied when painting contents
  // of |local_state| in |ancestor_state| space. Because this clip rect applies
  // on contents of |local_state|, it's not affected by any effect nodes between
  // |local_state| and |ancestor_state|.
  //
  // The UnsnappedClipRect of any clip nodes is used, *not* the
  // PixelSnappedClipRect.
  //
  // Note that the clip of |ancestor_state| is *not* applied.
  //
  // The output FloatClipRect may contain false positives for rounded-ness
  // if a rounded clip is clipped out, and overly conservative results
  // in the presences of transforms.

  static FloatClipRect LocalToAncestorClipRect(
      const PropertyTreeStateOrAlias& local_state,
      const PropertyTreeStateOrAlias& ancestor_state,
      OverlayScrollbarClipBehavior behavior = kIgnoreOverlayScrollbarSize) {
    return LocalToAncestorClipRect(local_state.Unalias(),
                                   ancestor_state.Unalias(), behavior);
  }
  static FloatClipRect LocalToAncestorClipRect(
      const PropertyTreeState& local_state,
      const PropertyTreeState& ancestor_state,
      OverlayScrollbarClipBehavior = kIgnoreOverlayScrollbarSize);

  // Maps from a rect in |local_state| to its visual rect in |ancestor_state|.
  // If there is no effect node between |local_state| (included) and
  // |ancestor_state| (not included), the result is computed by multiplying the
  // rect by its combined transform between |local_state| and |ancestor_space|,
  // then flattening into 2D space, then intersecting by the clip for
  // |local_state|'s clips. If there are any pixel-moving effect nodes between
  // |local_state| and |ancestor_state|, for each segment of states separated
  // by the effect nodes, we'll execute the above process and map the result
  // rect with the effect.
  //
  // Note that the clip of |ancestor_state| is *not* applied.
  //
  // DCHECK fails if any of the paint property tree nodes in |local_state| are
  // not equal to or a descendant of that in |ancestor_state|.
  //
  // |mapping_rect| is both input and output.
  //
  // The output FloatClipRect may contain false positives for rounded-ness
  // if a rounded clip is clipped out, and overly conservative results
  // in the presences of transforms.
  //
  // Returns true if the mapped rect is non-empty. (Note: this has special
  // meaning in the presence of inclusive intersection.)
  //
  // Note: if inclusive intersection is specified, then the
  // GeometryMapperClipCache is bypassed (the GeometryMapperTRansformCache is
  // still used, however).
  //
  // If kInclusiveIntersect is set, clipping operations will
  // use FloatRect::InclusiveIntersect, and the return value of
  // InclusiveIntersect will be propagated to the return value of this method.
  // Otherwise, clipping operations will use LayoutRect::intersect, and the
  // return value will be true only if the clipped rect has non-zero area.
  // See the documentation for FloatRect::InclusiveIntersect for more
  // information.
  static bool LocalToAncestorVisualRect(
      const PropertyTreeStateOrAlias& local_state,
      const PropertyTreeStateOrAlias& ancestor_state,
      FloatClipRect& mapping_rect,
      OverlayScrollbarClipBehavior clip = kIgnoreOverlayScrollbarSize,
      InclusiveIntersectOrNot intersect = kNonInclusiveIntersect,
      ExpandVisualRectForAnimationOrNot animation =
          kDontExpandVisualRectForAnimation) {
    return LocalToAncestorVisualRect(local_state.Unalias(),
                                     ancestor_state.Unalias(), mapping_rect,
                                     clip, intersect, animation);
  }
  static bool LocalToAncestorVisualRect(
      const PropertyTreeState& local_state,
      const PropertyTreeState& ancestor_state,
      FloatClipRect& mapping_rect,
      OverlayScrollbarClipBehavior = kIgnoreOverlayScrollbarSize,
      InclusiveIntersectOrNot = kNonInclusiveIntersect,
      ExpandVisualRectForAnimationOrNot = kDontExpandVisualRectForAnimation);

  static void ClearCache();

 private:
  // The internal methods do the same things as their public counterparts, but
  // take an extra |success| parameter which indicates if the function is
  // successful on return. See comments of the public functions for failure
  // conditions.

  static Translation2DOrMatrix SourceToDestinationProjectionInternal(
      const TransformPaintPropertyNode& source,
      const TransformPaintPropertyNode& destination,
      bool& has_animation,
      bool& success);

  static FloatClipRect LocalToAncestorClipRectInternal(
      const ClipPaintPropertyNode& descendant,
      const ClipPaintPropertyNode& ancestor_clip,
      const TransformPaintPropertyNode& ancestor_transform,
      OverlayScrollbarClipBehavior,
      InclusiveIntersectOrNot,
      ExpandVisualRectForAnimationOrNot,
      bool& success);

  // The return value has the same meaning as that for
  // LocalToAncestorVisualRect.
  static bool LocalToAncestorVisualRectInternal(
      const PropertyTreeState& local_state,
      const PropertyTreeState& ancestor_state,
      FloatClipRect& mapping_rect,
      OverlayScrollbarClipBehavior,
      InclusiveIntersectOrNot,
      ExpandVisualRectForAnimationOrNot,
      bool& success);

  // The return value has the same meaning as that for
  // LocalToAncestorVisualRect.
  static bool SlowLocalToAncestorVisualRectWithEffects(
      const PropertyTreeState& local_state,
      const PropertyTreeState& ancestor_state,
      FloatClipRect& mapping_rect,
      OverlayScrollbarClipBehavior,
      InclusiveIntersectOrNot,
      ExpandVisualRectForAnimationOrNot,
      bool& success);

  static void MoveRect(FloatRect& rect, const FloatSize& delta) {
    rect.Move(delta.Width(), delta.Height());
  }

  static void MoveRect(LayoutRect& rect, const FloatSize& delta) {
    rect.Move(LayoutSize(delta.Width(), delta.Height()));
  }

  static void MoveRect(IntRect& rect, const FloatSize& delta) {
    auto float_rect = FloatRect(rect);
    MoveRect(float_rect, delta);
    rect = EnclosingIntRect(float_rect);
  }

  friend class GeometryMapperTest;
  friend class PaintLayerClipperTest;
};

}  // namespace blink

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_GRAPHICS_PAINT_GEOMETRY_MAPPER_H_