platform/geometry/region.cc

/*
 * Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "third_party/blink/renderer/platform/geometry/region.h"

#include <stdio.h>

namespace blink {

Region::Region() = default;

Region::Region(const IntRect& rect) : bounds_(rect), shape_(rect) {}

Vector<IntRect> Region::Rects() const {
  Vector<IntRect> rects;

  for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
       span != end && span + 1 != end; ++span) {
    int y = span->y;
    int height = (span + 1)->y - y;

    for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
                                segment_end = shape_.SegmentsEnd(span);
         segment != segment_end && segment + 1 != segment_end; segment += 2) {
      int x = *segment;
      int width = *(segment + 1) - x;

      rects.push_back(IntRect(x, y, width, height));
    }
  }

  return rects;
}

bool Region::Contains(const Region& region) const {
  if (!bounds_.Contains(region.bounds_))
    return false;

  return Shape::CompareShapes<Shape::CompareContainsOperation>(shape_,
                                                               region.shape_);
}

bool Region::Contains(const IntPoint& point) const {
  if (!bounds_.Contains(point))
    return false;

  for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
       span != end && span + 1 != end; ++span) {
    int y = span->y;
    int max_y = (span + 1)->y;

    if (y > point.Y())
      break;
    if (max_y <= point.Y())
      continue;

    for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
                                segment_end = shape_.SegmentsEnd(span);
         segment != segment_end && segment + 1 != segment_end; segment += 2) {
      int x = *segment;
      int max_x = *(segment + 1);

      if (x > point.X())
        break;
      if (max_x > point.X())
        return true;
    }
  }

  return false;
}

bool Region::Intersects(const Region& region) const {
  if (!bounds_.Intersects(region.bounds_))
    return false;

  return Shape::CompareShapes<Shape::CompareIntersectsOperation>(shape_,
                                                                 region.shape_);
}

uint64_t Region::Area() const {
  uint64_t area = 0;
  for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
       span != end && span + 1 != end; ++span) {
    int height = (span + 1)->y - span->y;

    for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
                                segment_end = shape_.SegmentsEnd(span);
         segment != segment_end && segment + 1 != segment_end; segment += 2) {
      int width = *(segment + 1) - *segment;
      area += (uint64_t)height * (uint64_t)width;
    }
  }
  return area;
}

template <typename CompareOperation>
bool Region::Shape::CompareShapes(const Shape& a_shape, const Shape& b_shape) {
  bool result = CompareOperation::kDefaultResult;

  Shape::SpanIterator a_span = a_shape.SpansBegin();
  Shape::SpanIterator a_span_end = a_shape.SpansEnd();
  Shape::SpanIterator b_span = b_shape.SpansBegin();
  Shape::SpanIterator b_span_end = b_shape.SpansEnd();

  bool a_had_segment_in_previous_span = false;
  bool b_had_segment_in_previous_span = false;
  while (a_span != a_span_end && a_span + 1 != a_span_end &&
         b_span != b_span_end && b_span + 1 != b_span_end) {
    int a_y = a_span->y;
    int a_max_y = (a_span + 1)->y;
    int b_y = b_span->y;
    int b_max_y = (b_span + 1)->y;

    Shape::SegmentIterator a_segment = a_shape.SegmentsBegin(a_span);
    Shape::SegmentIterator a_segment_end = a_shape.SegmentsEnd(a_span);
    Shape::SegmentIterator b_segment = b_shape.SegmentsBegin(b_span);
    Shape::SegmentIterator b_segment_end = b_shape.SegmentsEnd(b_span);

    // Look for a non-overlapping part of the spans. If B had a segment in its
    // previous span, then we already tested A against B within that span.
    bool a_has_segment_in_span = a_segment != a_segment_end;
    bool b_has_segment_in_span = b_segment != b_segment_end;
    if (a_y < b_y && !b_had_segment_in_previous_span && a_has_segment_in_span &&
        CompareOperation::AOutsideB(result))
      return result;
    if (b_y < a_y && !a_had_segment_in_previous_span && b_has_segment_in_span &&
        CompareOperation::BOutsideA(result))
      return result;

    a_had_segment_in_previous_span = a_has_segment_in_span;
    b_had_segment_in_previous_span = b_has_segment_in_span;

    bool spans_overlap = b_max_y > a_y && b_y < a_max_y;
    if (spans_overlap) {
      while (a_segment != a_segment_end && b_segment != b_segment_end) {
        int a_x = *a_segment;
        int a_max_x = *(a_segment + 1);
        int b_x = *b_segment;
        int b_max_x = *(b_segment + 1);

        bool segments_overlap = b_max_x > a_x && b_x < a_max_x;
        if (segments_overlap && CompareOperation::AOverlapsB(result))
          return result;
        if (a_x < b_x && CompareOperation::AOutsideB(result))
          return result;
        if (b_x < a_x && CompareOperation::BOutsideA(result))
          return result;

        if (a_max_x < b_max_x) {
          a_segment += 2;
        } else if (b_max_x < a_max_x) {
          b_segment += 2;
        } else {
          a_segment += 2;
          b_segment += 2;
        }
      }

      if (a_segment != a_segment_end && CompareOperation::AOutsideB(result))
        return result;
      if (b_segment != b_segment_end && CompareOperation::BOutsideA(result))
        return result;
    }

    if (a_max_y < b_max_y) {
      a_span += 1;
    } else if (b_max_y < a_max_y) {
      b_span += 1;
    } else {
      a_span += 1;
      b_span += 1;
    }
  }

  if (a_span != a_span_end && a_span + 1 != a_span_end &&
      CompareOperation::AOutsideB(result))
    return result;
  if (b_span != b_span_end && b_span + 1 != b_span_end &&
      CompareOperation::BOutsideA(result))
    return result;

  return result;
}

void Region::Shape::TrimCapacities() {
  segments_.ShrinkToReasonableCapacity();
  spans_.ShrinkToReasonableCapacity();
}

struct Region::Shape::CompareContainsOperation {
  STATIC_ONLY(CompareContainsOperation);
  const static bool kDefaultResult = true;
  inline static bool AOutsideB(bool& /* result */) { return false; }
  inline static bool BOutsideA(bool& result) {
    result = false;
    return true;
  }
  inline static bool AOverlapsB(bool& /* result */) { return false; }
};

struct Region::Shape::CompareIntersectsOperation {
  STATIC_ONLY(CompareIntersectsOperation);
  const static bool kDefaultResult = false;
  inline static bool AOutsideB(bool& /* result */) { return false; }
  inline static bool BOutsideA(bool& /* result */) { return false; }
  inline static bool AOverlapsB(bool& result) {
    result = true;
    return true;
  }
};

Region::Shape::Shape() = default;

Region::Shape::Shape(const IntRect& rect) {
  AppendSpan(rect.Y());
  AppendSegment(rect.X());
  AppendSegment(rect.MaxX());
  AppendSpan(rect.MaxY());
}

Region::Shape::Shape(wtf_size_t segments_capacity, wtf_size_t spans_capacity) {
  segments_.ReserveCapacity(segments_capacity);
  spans_.ReserveCapacity(spans_capacity);
}

void Region::Shape::AppendSpan(int y) {
  spans_.push_back(Span(y, segments_.size()));
}

bool Region::Shape::CanCoalesce(SegmentIterator begin, SegmentIterator end) {
  if (spans_.IsEmpty())
    return false;

  SegmentIterator last_span_begin =
      segments_.data() + spans_.back().segment_index;
  SegmentIterator last_span_end = segments_.data() + segments_.size();

  // Check if both spans have an equal number of segments.
  if (last_span_end - last_span_begin != end - begin)
    return false;

  // Check if both spans are equal.
  if (!std::equal(begin, end, last_span_begin))
    return false;

  // Since the segments are equal the second segment can just be ignored.
  return true;
}

void Region::Shape::AppendSpan(int y,
                               SegmentIterator begin,
                               SegmentIterator end) {
  if (CanCoalesce(begin, end))
    return;

  AppendSpan(y);
  segments_.AppendRange(begin, end);
}

void Region::Shape::AppendSpans(const Shape& shape,
                                SpanIterator begin,
                                SpanIterator end) {
  for (SpanIterator it = begin; it != end; ++it)
    AppendSpan(it->y, shape.SegmentsBegin(it), shape.SegmentsEnd(it));
}

void Region::Shape::AppendSegment(int x) {
  segments_.push_back(x);
}

Region::Shape::SpanIterator Region::Shape::SpansBegin() const {
  return spans_.data();
}

Region::Shape::SpanIterator Region::Shape::SpansEnd() const {
  return spans_.data() + spans_.size();
}

Region::Shape::SegmentIterator Region::Shape::SegmentsBegin(
    SpanIterator it) const {
  DCHECK_GE(it, spans_.data());
  DCHECK_LT(it, spans_.data() + spans_.size());

  // Check if this span has any segments.
  if (it->segment_index == segments_.size())
    return nullptr;

  return &segments_[it->segment_index];
}

Region::Shape::SegmentIterator Region::Shape::SegmentsEnd(
    SpanIterator it) const {
  DCHECK_GE(it, spans_.data());
  DCHECK_LT(it, spans_.data() + spans_.size());

  // Check if this span has any segments.
  if (it->segment_index == segments_.size())
    return nullptr;

  DCHECK_LT(it + 1, spans_.data() + spans_.size());
  wtf_size_t segment_index = (it + 1)->segment_index;

  SECURITY_DCHECK(segment_index <= segments_.size());
  return segments_.data() + segment_index;
}

#if DCHECK_IS_ON()
void Region::Shape::Dump() const {
  for (Shape::SpanIterator span = SpansBegin(), end = SpansEnd(); span != end;
       ++span) {
    printf("%6d: (", span->y);

    for (Shape::SegmentIterator segment = SegmentsBegin(span),
                                segment_end = SegmentsEnd(span);
         segment != segment_end; ++segment)
      printf("%d ", *segment);
    printf(")\n");
  }

  printf("\n");
}
#endif

IntRect Region::Shape::Bounds() const {
  if (IsEmpty())
    return IntRect();

  SpanIterator span = SpansBegin();
  int min_y = span->y;

  SpanIterator last_span = SpansEnd() - 1;
  int max_y = last_span->y;

  int min_x = std::numeric_limits<int>::max();
  int max_x = std::numeric_limits<int>::min();

  while (span != last_span) {
    SegmentIterator first_segment = SegmentsBegin(span);
    SegmentIterator last_segment = SegmentsEnd(span) - 1;

    if (first_segment && last_segment) {
      DCHECK_NE(first_segment, last_segment);

      if (*first_segment < min_x)
        min_x = *first_segment;

      if (*last_segment > max_x)
        max_x = *last_segment;
    }

    ++span;
  }

  DCHECK_LE(min_x, max_x);
  DCHECK_LE(min_y, max_y);

  return IntRect(min_x, min_y, max_x - min_x, max_y - min_y);
}

void Region::Shape::Translate(const IntSize& offset) {
  for (wtf_size_t i = 0; i < segments_.size(); ++i)
    segments_[i] += offset.Width();
  for (wtf_size_t i = 0; i < spans_.size(); ++i)
    spans_[i].y += offset.Height();
}

void Region::Shape::Swap(Shape& other) {
  segments_.swap(other.segments_);
  spans_.swap(other.spans_);
}

enum {
  kShape1,
  kShape2,
};

template <typename Operation>
Region::Shape Region::Shape::ShapeOperation(const Shape& shape1,
                                            const Shape& shape2) {
  static_assert(!(!Operation::kShouldAddRemainingSegmentsFromSpan1 &&
                  Operation::kShouldAddRemainingSegmentsFromSpan2),
                "invalid segment combination");
  static_assert(!(!Operation::kShouldAddRemainingSpansFromShape1 &&
                  Operation::kShouldAddRemainingSpansFromShape2),
                "invalid span combination");

  wtf_size_t segments_capacity = shape1.SegmentsSize() + shape2.SegmentsSize();
  wtf_size_t spans_capacity = shape1.SpansSize() + shape2.SpansSize();
  Shape result(segments_capacity, spans_capacity);
  if (Operation::TrySimpleOperation(shape1, shape2, result))
    return result;

  SpanIterator spans1 = shape1.SpansBegin();
  SpanIterator spans1_end = shape1.SpansEnd();

  SpanIterator spans2 = shape2.SpansBegin();
  SpanIterator spans2_end = shape2.SpansEnd();

  SegmentIterator segments1 = nullptr;
  SegmentIterator segments1_end = nullptr;

  SegmentIterator segments2 = nullptr;
  SegmentIterator segments2_end = nullptr;

  Vector<int, 32> segments;
  segments.ReserveCapacity(
      std::max(shape1.SegmentsSize(), shape2.SegmentsSize()));

  // Iterate over all spans.
  while (spans1 != spans1_end && spans2 != spans2_end) {
    int y = 0;
    int y_diff = spans1->y - spans2->y;

    if (y_diff <= 0) {
      y = spans1->y;

      segments1 = shape1.SegmentsBegin(spans1);
      segments1_end = shape1.SegmentsEnd(spans1);
      ++spans1;
    }
    if (y_diff >= 0) {
      y = spans2->y;

      segments2 = shape2.SegmentsBegin(spans2);
      segments2_end = shape2.SegmentsEnd(spans2);
      ++spans2;
    }

    int flag = 0;
    int old_flag = 0;

    SegmentIterator s1 = segments1;
    SegmentIterator s2 = segments2;

    // Clear vector without dropping capacity.
    segments.resize(0);
    DCHECK(segments.capacity());

    // Now iterate over the segments in each span and construct a new vector of
    // segments.
    while (s1 != segments1_end && s2 != segments2_end) {
      int s_diff = *s1 - *s2;
      int x;

      if (s_diff <= 0) {
        x = *s1;
        flag = flag ^ 1;
        ++s1;
      }
      if (s_diff >= 0) {
        x = *s2;
        flag = flag ^ 2;
        ++s2;
      }

      if (flag == Operation::kOpCode || old_flag == Operation::kOpCode)
        segments.push_back(x);

      old_flag = flag;
    }

    // Add any remaining segments.
    if (Operation::kShouldAddRemainingSegmentsFromSpan1 && s1 != segments1_end)
      segments.AppendRange(s1, segments1_end);
    else if (Operation::kShouldAddRemainingSegmentsFromSpan2 &&
             s2 != segments2_end)
      segments.AppendRange(s2, segments2_end);

    // Add the span.
    if (!segments.IsEmpty() || !result.IsEmpty())
      result.AppendSpan(y, segments.data(), segments.data() + segments.size());
  }

  // Add any remaining spans.
  if (Operation::kShouldAddRemainingSpansFromShape1 && spans1 != spans1_end)
    result.AppendSpans(shape1, spans1, spans1_end);
  else if (Operation::kShouldAddRemainingSpansFromShape2 &&
           spans2 != spans2_end)
    result.AppendSpans(shape2, spans2, spans2_end);

  result.TrimCapacities();

  return result;
}

struct Region::Shape::UnionOperation {
  STATIC_ONLY(UnionOperation);
  static bool TrySimpleOperation(const Shape& shape1,
                                 const Shape& shape2,
                                 Shape& result) {
    if (shape1.IsEmpty()) {
      result = shape2;
      return true;
    }

    return false;
  }

  static const int kOpCode = 0;

  static const bool kShouldAddRemainingSegmentsFromSpan1 = true;
  static const bool kShouldAddRemainingSegmentsFromSpan2 = true;
  static const bool kShouldAddRemainingSpansFromShape1 = true;
  static const bool kShouldAddRemainingSpansFromShape2 = true;
};

Region::Shape Region::Shape::UnionShapes(const Shape& shape1,
                                         const Shape& shape2) {
  return ShapeOperation<UnionOperation>(shape1, shape2);
}

struct Region::Shape::IntersectOperation {
  STATIC_ONLY(IntersectOperation);
  static bool TrySimpleOperation(const Shape&, const Shape&, Shape&) {
    return false;
  }

  static const int kOpCode = 3;

  static const bool kShouldAddRemainingSegmentsFromSpan1 = false;
  static const bool kShouldAddRemainingSegmentsFromSpan2 = false;
  static const bool kShouldAddRemainingSpansFromShape1 = false;
  static const bool kShouldAddRemainingSpansFromShape2 = false;
};

Region::Shape Region::Shape::IntersectShapes(const Shape& shape1,
                                             const Shape& shape2) {
  return ShapeOperation<IntersectOperation>(shape1, shape2);
}

struct Region::Shape::SubtractOperation {
  STATIC_ONLY(SubtractOperation);
  static bool TrySimpleOperation(const Shape&, const Shape&, Region::Shape&) {
    return false;
  }

  static const int kOpCode = 1;

  static const bool kShouldAddRemainingSegmentsFromSpan1 = true;
  static const bool kShouldAddRemainingSegmentsFromSpan2 = false;
  static const bool kShouldAddRemainingSpansFromShape1 = true;
  static const bool kShouldAddRemainingSpansFromShape2 = false;
};

Region::Shape Region::Shape::SubtractShapes(const Shape& shape1,
                                            const Shape& shape2) {
  return ShapeOperation<SubtractOperation>(shape1, shape2);
}

#if DCHECK_IS_ON()
void Region::Dump() const {
  printf("Bounds: (%d, %d, %d, %d)\n", bounds_.X(), bounds_.Y(),
         bounds_.Width(), bounds_.Height());
  shape_.Dump();
}
#endif

void Region::Intersect(const Region& region) {
  if (bounds_.IsEmpty())
    return;
  if (!bounds_.Intersects(region.bounds_)) {
    shape_ = Shape();
    bounds_ = IntRect();
    return;
  }

  Shape intersected_shape = Shape::IntersectShapes(shape_, region.shape_);

  shape_.Swap(intersected_shape);
  bounds_ = shape_.Bounds();
}

void Region::Unite(const Region& region) {
  if (region.IsEmpty())
    return;
  if (IsRect() && bounds_.Contains(region.bounds_))
    return;
  if (region.IsRect() && region.bounds_.Contains(bounds_)) {
    shape_ = region.shape_;
    bounds_ = region.bounds_;
    return;
  }
  // FIXME: We may want another way to construct a Region without doing this
  // test when we expect it to be false.
  if (!IsRect() && Contains(region))
    return;

  Shape united_shape = Shape::UnionShapes(shape_, region.shape_);

  shape_.Swap(united_shape);
  bounds_.Unite(region.bounds_);
}

void Region::Subtract(const Region& region) {
  if (bounds_.IsEmpty())
    return;
  if (region.IsEmpty())
    return;
  if (!bounds_.Intersects(region.bounds_))
    return;

  Shape subtracted_shape = Shape::SubtractShapes(shape_, region.shape_);

  shape_.Swap(subtracted_shape);
  bounds_ = shape_.Bounds();
}

void Region::Translate(const IntSize& offset) {
  bounds_.Move(offset);
  shape_.Translate(offset);
}

}  // namespace blink