display_list/geometry/dl_region.cc - mirrors/engine - Git at Google

 // Copyright 2013 The Flutter 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 "flutter/display_list/geometry/dl_region.h"

 #include "flutter/fml/logging.h"

 namespace flutter {

 // Threshold for switching from linear search through span lines to binary
 // search.
 const int kBinarySearchThreshold = 10;

 DlRegion::SpanBuffer::SpanBuffer(DlRegion::SpanBuffer&& m)
     : capacity_(m.capacity_), size_(m.size_), spans_(m.spans_) {
   m.size_ = 0;
   m.capacity_ = 0;
   m.spans_ = nullptr;
 };

 DlRegion::SpanBuffer::SpanBuffer(const DlRegion::SpanBuffer& m)
     : capacity_(m.capacity_), size_(m.size_) {
   if (m.spans_ == nullptr) {
     spans_ = nullptr;
   } else {
     spans_ = static_cast<Span*>(std::malloc(capacity_ * sizeof(Span)));
     memcpy(spans_, m.spans_, size_ * sizeof(Span));
   }
 };

 DlRegion::SpanBuffer& DlRegion::SpanBuffer::operator=(
     const DlRegion::SpanBuffer& buffer) {
   SpanBuffer copy(buffer);
   std::swap(*this, copy);
   return *this;
 }

 DlRegion::SpanBuffer& DlRegion::SpanBuffer::operator=(
     DlRegion::SpanBuffer&& buffer) {
   std::swap(capacity_, buffer.capacity_);
   std::swap(size_, buffer.size_);
   std::swap(spans_, buffer.spans_);
   return *this;
 }

 DlRegion::SpanBuffer::~SpanBuffer() {
   free(spans_);
 }

 void DlRegion::SpanBuffer::reserve(size_t capacity) {
   if (capacity_ < capacity) {
     spans_ = static_cast<Span*>(std::realloc(spans_, capacity * sizeof(Span)));
     capacity_ = capacity;
   }
 }

 DlRegion::SpanChunkHandle DlRegion::SpanBuffer::storeChunk(const Span* begin,
                                                            const Span* end) {
   size_t chunk_size = end - begin;
   size_t min_capacity = size_ + chunk_size + 1;
   if (capacity_ < min_capacity) {
     size_t new_capacity = std::max(min_capacity, capacity_ * 2);
     new_capacity = std::max(new_capacity, size_t(512));
     reserve(new_capacity);
   }
   SpanChunkHandle res = size_;
   size_ += chunk_size + 1;
   setChunkSize(res, chunk_size);

   auto* dst = spans_ + res + 1;
   memmove(dst, begin, chunk_size * sizeof(Span));

   return res;
 }

 size_t DlRegion::SpanBuffer::getChunkSize(SpanChunkHandle handle) const {
   FML_DCHECK(handle < size_);
   return spans_[handle].left;
 }

 void DlRegion::SpanBuffer::setChunkSize(SpanChunkHandle handle, size_t size) {
   FML_DCHECK(handle < size_);
   FML_DCHECK(spans_ != nullptr);
   // NOLINTNEXTLINE(clang-analyzer-core.NullDereference)
   spans_[handle].left = size;
 }

 void DlRegion::SpanBuffer::getSpans(SpanChunkHandle handle,
                                     const DlRegion::Span*& begin,
                                     const DlRegion::Span*& end) const {
   FML_DCHECK(handle < size_);
   begin = spans_ + handle + 1;
   end = begin + getChunkSize(handle);
 }

 DlRegion::DlRegion(const std::vector<SkIRect>& rects) {
   setRects(rects);
 }

 DlRegion::DlRegion(const SkIRect& rect) : bounds_(rect) {
   Span span{rect.left(), rect.right()};
   lines_.push_back(makeLine(rect.top(), rect.bottom(), &span, &span + 1));
 }

 bool DlRegion::spansEqual(SpanLine& line,
                           const Span* begin,
                           const Span* end) const {
   const Span *our_begin, *our_end;
   span_buffer_.getSpans(line.chunk_handle, our_begin, our_end);
   size_t our_size = our_end - our_begin;
   size_t their_size = end - begin;
   if (our_size != their_size) {
     return false;
   }

   return memcmp(our_begin, begin, our_size * sizeof(Span)) == 0;
 }

 DlRegion::SpanLine DlRegion::makeLine(int32_t top,
                                       int32_t bottom,
                                       const SpanVec& v) {
   return makeLine(top, bottom, v.data(), v.data() + v.size());
 }

 DlRegion::SpanLine DlRegion::makeLine(int32_t top,
                                       int32_t bottom,
                                       const Span* begin,
                                       const Span* end) {
   auto handle = span_buffer_.storeChunk(begin, end);
   return {top, bottom, handle};
 }

 // Returns number of valid spans in res. For performance reasons res is never
 // downsized.
 size_t DlRegion::unionLineSpans(std::vector<Span>& res,
                                 const SpanBuffer& a_buffer,
                                 SpanChunkHandle a_handle,
                                 const SpanBuffer& b_buffer,
                                 SpanChunkHandle b_handle) {
   class OrderedSpanAccumulator {
    public:
     explicit OrderedSpanAccumulator(std::vector<Span>& res) : res(res) {}

     void accumulate(const Span& span) {
       if (span.left > last_ || len == 0) {
         res[len++] = span;
         last_ = span.right;
       } else if (span.right > last_) {
         FML_DCHECK(len > 0);
         res[len - 1].right = span.right;
         last_ = span.right;
       }
     }

     size_t len = 0;
     std::vector<Span>& res;

    private:
     int32_t last_ = std::numeric_limits<int32_t>::min();
   };

   const Span *begin1, *end1;
   a_buffer.getSpans(a_handle, begin1, end1);

   const Span *begin2, *end2;
   b_buffer.getSpans(b_handle, begin2, end2);

   size_t min_size = (end1 - begin1) + (end2 - begin2);
   if (res.size() < min_size) {
     res.resize(min_size);
   }

   OrderedSpanAccumulator accumulator(res);

   while (true) {
     if (begin1->left < begin2->left) {
       accumulator.accumulate(*begin1++);
       if (begin1 == end1) {
         break;
       }
     } else {
       // Either 2 is first, or they are equal, in which case add 2 now
       // and we might combine 1 with it next time around
       accumulator.accumulate(*begin2++);
       if (begin2 == end2) {
         break;
       }
     }
   }

   FML_DCHECK(begin1 == end1 || begin2 == end2);

   while (begin1 < end1) {
     accumulator.accumulate(*begin1++);
   }
   while (begin2 < end2) {
     accumulator.accumulate(*begin2++);
   }

   FML_DCHECK(begin1 == end1 && begin2 == end2);

   return accumulator.len;
 }

 size_t DlRegion::intersectLineSpans(std::vector<Span>& res,
                                     const SpanBuffer& a_buffer,
                                     SpanChunkHandle a_handle,
                                     const SpanBuffer& b_buffer,
                                     SpanChunkHandle b_handle) {
   const Span *begin1, *end1;
   a_buffer.getSpans(a_handle, begin1, end1);

   const Span *begin2, *end2;
   b_buffer.getSpans(b_handle, begin2, end2);

   // Worst case scenario, interleaved overlapping spans
   //   AAAA  BBBB  CCCC
   // XXX  YYYY  XXXX
   size_t min_size = (end1 - begin1) + (end2 - begin2) - 1;
   if (res.size() < min_size) {
     res.resize(min_size);
   }

   // Pointer to the next span to be written.
   Span* new_span = res.data();

   while (begin1 != end1 && begin2 != end2) {
     if (begin1->right <= begin2->left) {
       ++begin1;
     } else if (begin2->right <= begin1->left) {
       ++begin2;
     } else {
       int32_t left = std::max(begin1->left, begin2->left);
       int32_t right = std::min(begin1->right, begin2->right);
       FML_DCHECK(left < right);
       FML_DCHECK(new_span < res.data() + res.size());
       *new_span++ = {left, right};
       if (begin1->right == right) {
         ++begin1;
       }
       if (begin2->right == right) {
         ++begin2;
       }
     }
   }

   return new_span - res.data();
 }

 void DlRegion::setRects(const std::vector<SkIRect>& unsorted_rects) {
   // setRects can only be called on empty regions.
   FML_DCHECK(lines_.empty());

   size_t count = unsorted_rects.size();
   std::vector<const SkIRect*> rects(count);
   for (size_t i = 0; i < count; i++) {
     rects[i] = &unsorted_rects[i];
     bounds_.join(unsorted_rects[i]);
   }
   std::sort(rects.begin(), rects.end(), [](const SkIRect* a, const SkIRect* b) {
     if (a->top() < b->top()) {
       return true;
     }
     if (a->top() > b->top()) {
       return false;
     }
     return a->left() < b->left();
   });

   size_t active_end = 0;
   size_t next_rect = 0;
   int32_t cur_y = std::numeric_limits<int32_t>::min();
   SpanVec working_spans;

 #ifdef DlRegion_DO_STATS
   size_t active_rect_count = 0;
   size_t span_count = 0;
   int pass_count = 0;
   int line_count = 0;
 #endif

   while (next_rect < count || active_end > 0) {
     // First prune passed rects out of the active list
     size_t preserve_end = 0;
     for (size_t i = 0; i < active_end; i++) {
       const SkIRect* r = rects[i];
       if (r->bottom() > cur_y) {
         rects[preserve_end++] = r;
       }
     }
     active_end = preserve_end;

     // If we have no active rects any more, jump to the top of the
     // next available input rect.
     if (active_end == 0) {
       if (next_rect >= count) {
         // No active rects and no more rects to bring in. We are done.
         break;
       }
       cur_y = rects[next_rect]->top();
     }

     // Next, insert any new rects we've reached into the active list
     while (next_rect < count) {
       const SkIRect* r = rects[next_rect];
       if (r->isEmpty()) {
         continue;
       }
       if (r->top() > cur_y) {
         break;
       }
       // We now know that we will be inserting this rect into active list
       next_rect++;
       size_t insert_at = active_end++;
       while (insert_at > 0) {
         const SkIRect* ir = rects[insert_at - 1];
         if (ir->left() <= r->left()) {
           break;
         }
         rects[insert_at--] = ir;
       }
       rects[insert_at] = r;
     }

     // We either preserved some rects in the active list or added more from
     // the remaining input rects, or we would have exited the loop above.
     FML_DCHECK(active_end != 0);
     working_spans.clear();
     FML_DCHECK(working_spans.empty());

 #ifdef DlRegion_DO_STATS
     active_rect_count += active_end;
     pass_count++;
 #endif

     // [start_x, end_x) always represents a valid span to be inserted
     // [cur_y, end_y) is the intersecting range over which all spans are valid
     int32_t start_x = rects[0]->left();
     int32_t end_x = rects[0]->right();
     int32_t end_y = rects[0]->bottom();
     for (size_t i = 1; i < active_end; i++) {
       const SkIRect* r = rects[i];
       if (r->left() > end_x) {
         working_spans.emplace_back(start_x, end_x);
         start_x = r->left();
         end_x = r->right();
       } else if (end_x < r->right()) {
         end_x = r->right();
       }
       if (end_y > r->bottom()) {
         end_y = r->bottom();
       }
     }
     working_spans.emplace_back(start_x, end_x);

     // end_y must not pass by the top of the next input rect
     if (next_rect < count && end_y > rects[next_rect]->top()) {
       end_y = rects[next_rect]->top();
     }

     // If all of the rules above work out, we should never collapse the
     // current range of Y coordinates to empty
     FML_DCHECK(end_y > cur_y);

     if (!lines_.empty() && lines_.back().bottom == cur_y &&
         spansEqual(lines_.back(), working_spans.data(),
                    working_spans.data() + working_spans.size())) {
       lines_.back().bottom = end_y;
     } else {
 #ifdef DlRegion_DO_STATS
       span_count += working_spans.size();
       line_count++;
 #endif
       lines_.push_back(makeLine(cur_y, end_y, working_spans));
     }
     cur_y = end_y;
   }

 #ifdef DlRegion_DO_STATS
   double span_avg = ((double)span_count) / line_count;
   double active_avg = ((double)active_rect_count) / pass_count;
   FML_LOG(ERROR) << lines_.size() << " lines for " << count
                  << " input rects, avg " << span_avg
                  << " spans per line and avg " << active_avg
                  << " active rects per loop";
 #endif
 }

 void DlRegion::appendLine(int32_t top,
                           int32_t bottom,
                           const Span* begin,
                           const Span* end) {
   if (lines_.empty()) {
     lines_.push_back(makeLine(top, bottom, begin, end));
   } else {
     if (lines_.back().bottom == top && spansEqual(lines_.back(), begin, end)) {
       lines_.back().bottom = bottom;
     } else {
       lines_.push_back(makeLine(top, bottom, begin, end));
     }
   }
 }

 DlRegion DlRegion::MakeUnion(const DlRegion& a, const DlRegion& b) {
   if (a.isEmpty()) {
     return b;
   } else if (b.isEmpty()) {
     return a;
   } else if (a.isSimple() && a.bounds_.contains(b.bounds_)) {
     return a;
   } else if (b.isSimple() && b.bounds_.contains(a.bounds_)) {
     return b;
   }

   DlRegion res;
   res.bounds_ = a.bounds_;
   res.bounds_.join(b.bounds_);
   res.span_buffer_.reserve(a.span_buffer_.capacity() +
                            b.span_buffer_.capacity());

   auto& lines = res.lines_;
   lines.reserve(a.lines_.size() + b.lines_.size());

   auto a_it = a.lines_.begin();
   auto b_it = b.lines_.begin();
   auto a_end = a.lines_.end();
   auto b_end = b.lines_.end();

   FML_DCHECK(a_it != a_end && b_it != b_end);

   auto& a_buffer = a.span_buffer_;
   auto& b_buffer = b.span_buffer_;

   std::vector<Span> tmp;

   int32_t cur_top = std::numeric_limits<int32_t>::min();

   while (a_it != a_end && b_it != b_end) {
     auto a_top = std::max(cur_top, a_it->top);
     auto b_top = std::max(cur_top, b_it->top);
     if (a_it->bottom <= b_top) {
       res.appendLine(a_top, a_it->bottom, a_buffer, a_it->chunk_handle);
       ++a_it;
     } else if (b_it->bottom <= a_top) {
       res.appendLine(b_top, b_it->bottom, b_buffer, b_it->chunk_handle);
       ++b_it;
     } else {
       if (a_top < b_top) {
         res.appendLine(a_top, b_top, a_buffer, a_it->chunk_handle);
         cur_top = b_top;
         if (cur_top == a_it->bottom) {
           ++a_it;
         }
       } else if (b_top < a_top) {
         res.appendLine(b_top, a_top, b_buffer, b_it->chunk_handle);
         cur_top = a_top;
         if (cur_top == b_it->bottom) {
           ++b_it;
         }
       } else {
         auto new_bottom = std::min(a_it->bottom, b_it->bottom);
         FML_DCHECK(a_top == b_top);
         FML_DCHECK(new_bottom > a_top);
         FML_DCHECK(new_bottom > b_top);
         auto size = unionLineSpans(tmp, a_buffer, a_it->chunk_handle, b_buffer,
                                    b_it->chunk_handle);
         res.appendLine(a_top, new_bottom, tmp.data(), tmp.data() + size);
         cur_top = new_bottom;
         if (cur_top == a_it->bottom) {
           ++a_it;
         }
         if (cur_top == b_it->bottom) {
           ++b_it;
         }
       }
     }
   }

   FML_DCHECK(a_it == a_end || b_it == b_end);

   while (a_it != a_end) {
     auto a_top = std::max(cur_top, a_it->top);
     res.appendLine(a_top, a_it->bottom, a_buffer, a_it->chunk_handle);
     ++a_it;
   }

   while (b_it != b_end) {
     auto b_top = std::max(cur_top, b_it->top);
     res.appendLine(b_top, b_it->bottom, b_buffer, b_it->chunk_handle);
     ++b_it;
   }

   return res;
 }

 DlRegion DlRegion::MakeIntersection(const DlRegion& a, const DlRegion& b) {
   if (!SkIRect::Intersects(a.bounds_, b.bounds_)) {
     return DlRegion();
   } else if (a.isSimple() && b.isSimple()) {
     SkIRect r(a.bounds_);
     auto res = r.intersect(b.bounds_);
     (void)res;  // Suppress unused variable warning in release builds.
     FML_DCHECK(res);
     return DlRegion(r);
   } else if (a.isSimple() && a.bounds_.contains(b.bounds_)) {
     return b;
   } else if (b.isSimple() && b.bounds_.contains(a.bounds_)) {
     return a;
   }

   DlRegion res;
   res.span_buffer_.reserve(
       std::max(a.span_buffer_.capacity(), b.span_buffer_.capacity()));

   auto& lines = res.lines_;
   lines.reserve(std::min(a.lines_.size(), b.lines_.size()));

   std::vector<SpanLine>::const_iterator a_it, b_it;
   getIntersectionIterators(a.lines_, b.lines_, a_it, b_it);

   auto a_end = a.lines_.end();
   auto b_end = b.lines_.end();

   auto& a_buffer = a.span_buffer_;
   auto& b_buffer = b.span_buffer_;

   std::vector<Span> tmp;

   int32_t cur_top = std::numeric_limits<int32_t>::min();

   while (a_it != a_end && b_it != b_end) {
     auto a_top = std::max(cur_top, a_it->top);
     auto b_top = std::max(cur_top, b_it->top);
     if (a_it->bottom <= b_top) {
       ++a_it;
     } else if (b_it->bottom <= a_top) {
       ++b_it;
     } else {
       auto top = std::max(a_top, b_top);
       auto bottom = std::min(a_it->bottom, b_it->bottom);
       FML_DCHECK(top < bottom);
       auto size = intersectLineSpans(tmp, a_buffer, a_it->chunk_handle,
                                      b_buffer, b_it->chunk_handle);
       if (size > 0) {
         res.appendLine(top, bottom, tmp.data(), tmp.data() + size);
         res.bounds_.join(SkIRect::MakeLTRB(
             tmp.data()->left, top, (tmp.data() + size - 1)->right, bottom));
       }
       cur_top = bottom;
       if (cur_top == a_it->bottom) {
         ++a_it;
       }
       if (cur_top == b_it->bottom) {
         ++b_it;
       }
     }
   }
   FML_DCHECK(a_it == a_end || b_it == b_end);
   return res;
 }

 std::vector<SkIRect> DlRegion::getRects(bool deband) const {
   std::vector<SkIRect> rects;
   if (isEmpty()) {
     return rects;
   } else if (isSimple()) {
     rects.push_back(bounds_);
     return rects;
   }

   size_t rect_count = 0;
   size_t previous_span_end = 0;
   for (const auto& line : lines_) {
     rect_count += span_buffer_.getChunkSize(line.chunk_handle);
   }
   rects.reserve(rect_count);

   for (const auto& line : lines_) {
     const Span *span_begin, *span_end;
     span_buffer_.getSpans(line.chunk_handle, span_begin, span_end);
     for (const auto* span = span_begin; span < span_end; ++span) {
       SkIRect rect{span->left, line.top, span->right, line.bottom};
       if (deband) {
         auto iter = rects.begin() + previous_span_end;
         // If there is rectangle previously in rects on which this one is a
         // vertical continuation, remove the previous rectangle and expand
         // this one vertically to cover the area.
         while (iter != rects.begin()) {
           --iter;
           if (iter->bottom() < rect.top()) {
             // Went all the way to previous span line.
             break;
           } else if (iter->left() == rect.left() &&
                      iter->right() == rect.right()) {
             FML_DCHECK(iter->bottom() == rect.top());
             rect.fTop = iter->fTop;
             rects.erase(iter);
             --previous_span_end;
             break;
           }
         }
       }
       rects.push_back(rect);
     }
     previous_span_end = rects.size();
   }
   return rects;
 }

 bool DlRegion::isComplex() const {
   return lines_.size() > 1 ||
          (lines_.size() == 1 &&
           span_buffer_.getChunkSize(lines_.front().chunk_handle) > 1);
 }

 bool DlRegion::intersects(const SkIRect& rect) const {
   if (isEmpty()) {
     return false;
   }

   auto bounds_intersect = SkIRect::Intersects(bounds_, rect);

   if (isSimple()) {
     return bounds_intersect;
   }

   if (!bounds_intersect) {
     return false;
   }

   auto it = lines_.begin();
   auto end = lines_.end();
   if (lines_.size() > kBinarySearchThreshold &&
       it[kBinarySearchThreshold].bottom <= rect.fTop) {
     it = std::lower_bound(
         lines_.begin() + kBinarySearchThreshold + 1, lines_.end(), rect.fTop,
         [](const SpanLine& line, int32_t top) { return line.bottom <= top; });
   } else {
     while (it != end && it->bottom <= rect.fTop) {
       ++it;
       continue;
     }
   }
   while (it != end && it->top < rect.fBottom) {
     FML_DCHECK(rect.fTop < it->bottom && it->top < rect.fBottom);
     const Span *begin, *end;
     span_buffer_.getSpans(it->chunk_handle, begin, end);
     while (begin != end && begin->left < rect.fRight) {
       if (begin->right > rect.fLeft) {
         return true;
       }
       ++begin;
     }
     ++it;
   }

   return false;
 }

 bool DlRegion::spansIntersect(const Span* begin1,
                               const Span* end1,
                               const Span* begin2,
                               const Span* end2) {
   while (begin1 != end1 && begin2 != end2) {
     if (begin1->right <= begin2->left) {
       ++begin1;
     } else if (begin2->right <= begin1->left) {
       ++begin2;
     } else {
       return true;
     }
   }
   return false;
 }

 void DlRegion::getIntersectionIterators(
     const std::vector<SpanLine>& a_lines,
     const std::vector<SpanLine>& b_lines,
     std::vector<SpanLine>::const_iterator& a_it,
     std::vector<SpanLine>::const_iterator& b_it) {
   a_it = a_lines.begin();
   auto a_end = a_lines.end();
   b_it = b_lines.begin();
   auto b_end = b_lines.end();

   FML_DCHECK(a_it != a_end && b_it != b_end);

   auto a_len = a_end - a_it;
   auto b_len = b_end - b_it;

   if (a_len > kBinarySearchThreshold &&
       a_it[kBinarySearchThreshold].bottom <= b_it->top) {
     a_it = std::lower_bound(
         a_lines.begin() + kBinarySearchThreshold + 1, a_lines.end(), b_it->top,
         [](const SpanLine& line, int32_t top) { return line.bottom <= top; });
   } else if (b_len > kBinarySearchThreshold &&
              b_it[kBinarySearchThreshold].bottom <= a_it->top) {
     b_it = std::lower_bound(
         b_lines.begin() + kBinarySearchThreshold + 1, b_lines.end(), a_it->top,
         [](const SpanLine& line, int32_t top) { return line.bottom <= top; });
   }
 }

 bool DlRegion::intersects(const DlRegion& region) const {
   if (isEmpty() || region.isEmpty()) {
     return false;
   }

   auto our_complex = isComplex();
   auto their_complex = region.isComplex();
   auto bounds_intersect = SkIRect::Intersects(bounds_, region.bounds_);

   if (!our_complex && !their_complex) {
     return bounds_intersect;
   }

   if (!bounds_intersect) {
     return false;
   }

   if (!our_complex) {
     return region.intersects(bounds_);
   }

   if (!their_complex) {
     return intersects(region.bounds_);
   }

   std::vector<SpanLine>::const_iterator ours, theirs;
   getIntersectionIterators(lines_, region.lines_, ours, theirs);
   auto ours_end = lines_.end();
   auto theirs_end = region.lines_.end();

   while (ours != ours_end && theirs != theirs_end) {
     if (ours->bottom <= theirs->top) {
       ++ours;
     } else if (theirs->bottom <= ours->top) {
       ++theirs;
     } else {
       FML_DCHECK(ours->top < theirs->bottom && theirs->top < ours->bottom);
       const Span *ours_begin, *ours_end;
       span_buffer_.getSpans(ours->chunk_handle, ours_begin, ours_end);
       const Span *theirs_begin, *theirs_end;
       region.span_buffer_.getSpans(theirs->chunk_handle, theirs_begin,
                                    theirs_end);
       if (spansIntersect(ours_begin, ours_end, theirs_begin, theirs_end)) {
         return true;
       }
       if (ours->bottom < theirs->bottom) {
         ++ours;
       } else {
         ++theirs;
       }
     }
   }
   return false;
 }

 }  // namespace flutter
	// Copyright 2013 The Flutter 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 "flutter/display_list/geometry/dl_region.h"

	#include "flutter/fml/logging.h"

	namespace flutter {

	// Threshold for switching from linear search through span lines to binary
	// search.
	const int kBinarySearchThreshold = 10;

	DlRegion::SpanBuffer::SpanBuffer(DlRegion::SpanBuffer&& m)
	: capacity_(m.capacity_), size_(m.size_), spans_(m.spans_) {
	m.size_ = 0;
	m.capacity_ = 0;
	m.spans_ = nullptr;
	};

	DlRegion::SpanBuffer::SpanBuffer(const DlRegion::SpanBuffer& m)
	: capacity_(m.capacity_), size_(m.size_) {
	if (m.spans_ == nullptr) {
	spans_ = nullptr;
	} else {
	spans_ = static_cast<Span>(std::malloc(capacity_ sizeof(Span)));
	memcpy(spans_, m.spans_, size_ * sizeof(Span));
	}
	};

	DlRegion::SpanBuffer& DlRegion::SpanBuffer::operator=(
	const DlRegion::SpanBuffer& buffer) {
	SpanBuffer copy(buffer);
	std::swap(*this, copy);
	return *this;
	}

	DlRegion::SpanBuffer& DlRegion::SpanBuffer::operator=(
	DlRegion::SpanBuffer&& buffer) {
	std::swap(capacity_, buffer.capacity_);
	std::swap(size_, buffer.size_);
	std::swap(spans_, buffer.spans_);
	return *this;
	}

	DlRegion::SpanBuffer::~SpanBuffer() {
	free(spans_);
	}

	void DlRegion::SpanBuffer::reserve(size_t capacity) {
	if (capacity_ < capacity) {
	spans_ = static_cast<Span>(std::realloc(spans_, capacity sizeof(Span)));
	capacity_ = capacity;
	}
	}

	DlRegion::SpanChunkHandle DlRegion::SpanBuffer::storeChunk(const Span* begin,
	const Span* end) {
	size_t chunk_size = end - begin;
	size_t min_capacity = size_ + chunk_size + 1;
	if (capacity_ < min_capacity) {
	size_t new_capacity = std::max(min_capacity, capacity_ * 2);
	new_capacity = std::max(new_capacity, size_t(512));
	reserve(new_capacity);
	}
	SpanChunkHandle res = size_;
	size_ += chunk_size + 1;
	setChunkSize(res, chunk_size);

	auto* dst = spans_ + res + 1;
	memmove(dst, begin, chunk_size * sizeof(Span));

	return res;
	}

	size_t DlRegion::SpanBuffer::getChunkSize(SpanChunkHandle handle) const {
	FML_DCHECK(handle < size_);
	return spans_[handle].left;
	}

	void DlRegion::SpanBuffer::setChunkSize(SpanChunkHandle handle, size_t size) {
	FML_DCHECK(handle < size_);
	FML_DCHECK(spans_ != nullptr);
	// NOLINTNEXTLINE(clang-analyzer-core.NullDereference)
	spans_[handle].left = size;
	}

	void DlRegion::SpanBuffer::getSpans(SpanChunkHandle handle,
	const DlRegion::Span*& begin,
	const DlRegion::Span*& end) const {
	FML_DCHECK(handle < size_);
	begin = spans_ + handle + 1;
	end = begin + getChunkSize(handle);
	}

	DlRegion::DlRegion(const std::vector<SkIRect>& rects) {
	setRects(rects);
	}

	DlRegion::DlRegion(const SkIRect& rect) : bounds_(rect) {
	Span span{rect.left(), rect.right()};
	lines_.push_back(makeLine(rect.top(), rect.bottom(), &span, &span + 1));
	}

	bool DlRegion::spansEqual(SpanLine& line,
	const Span* begin,
	const Span* end) const {
	const Span our_begin, our_end;
	span_buffer_.getSpans(line.chunk_handle, our_begin, our_end);
	size_t our_size = our_end - our_begin;
	size_t their_size = end - begin;
	if (our_size != their_size) {
	return false;
	}

	return memcmp(our_begin, begin, our_size * sizeof(Span)) == 0;
	}

	DlRegion::SpanLine DlRegion::makeLine(int32_t top,
	int32_t bottom,
	const SpanVec& v) {
	return makeLine(top, bottom, v.data(), v.data() + v.size());
	}

	DlRegion::SpanLine DlRegion::makeLine(int32_t top,
	int32_t bottom,
	const Span* begin,
	const Span* end) {
	auto handle = span_buffer_.storeChunk(begin, end);
	return {top, bottom, handle};
	}

	// Returns number of valid spans in res. For performance reasons res is never
	// downsized.
	size_t DlRegion::unionLineSpans(std::vector<Span>& res,
	const SpanBuffer& a_buffer,
	SpanChunkHandle a_handle,
	const SpanBuffer& b_buffer,
	SpanChunkHandle b_handle) {
	class OrderedSpanAccumulator {
	public:
	explicit OrderedSpanAccumulator(std::vector<Span>& res) : res(res) {}

	void accumulate(const Span& span) {
	if (span.left > last_ \|\| len == 0) {
	res[len++] = span;
	last_ = span.right;
	} else if (span.right > last_) {
	FML_DCHECK(len > 0);
	res[len - 1].right = span.right;
	last_ = span.right;
	}
	}

	size_t len = 0;
	std::vector<Span>& res;

	private:
	int32_t last_ = std::numeric_limits<int32_t>::min();
	};

	const Span begin1, end1;
	a_buffer.getSpans(a_handle, begin1, end1);

	const Span begin2, end2;
	b_buffer.getSpans(b_handle, begin2, end2);

	size_t min_size = (end1 - begin1) + (end2 - begin2);
	if (res.size() < min_size) {
	res.resize(min_size);
	}

	OrderedSpanAccumulator accumulator(res);

	while (true) {
	if (begin1->left < begin2->left) {
	accumulator.accumulate(*begin1++);
	if (begin1 == end1) {
	break;
	}
	} else {
	// Either 2 is first, or they are equal, in which case add 2 now
	// and we might combine 1 with it next time around
	accumulator.accumulate(*begin2++);
	if (begin2 == end2) {
	break;
	}
	}
	}

	FML_DCHECK(begin1 == end1 \|\| begin2 == end2);

	while (begin1 < end1) {
	accumulator.accumulate(*begin1++);
	}
	while (begin2 < end2) {
	accumulator.accumulate(*begin2++);
	}

	FML_DCHECK(begin1 == end1 && begin2 == end2);

	return accumulator.len;
	}

	size_t DlRegion::intersectLineSpans(std::vector<Span>& res,
	const SpanBuffer& a_buffer,
	SpanChunkHandle a_handle,
	const SpanBuffer& b_buffer,
	SpanChunkHandle b_handle) {
	const Span begin1, end1;
	a_buffer.getSpans(a_handle, begin1, end1);

	const Span begin2, end2;
	b_buffer.getSpans(b_handle, begin2, end2);

	// Worst case scenario, interleaved overlapping spans
	// AAAA BBBB CCCC
	// XXX YYYY XXXX
	size_t min_size = (end1 - begin1) + (end2 - begin2) - 1;
	if (res.size() < min_size) {
	res.resize(min_size);
	}

	// Pointer to the next span to be written.
	Span* new_span = res.data();

	while (begin1 != end1 && begin2 != end2) {
	if (begin1->right <= begin2->left) {
	++begin1;
	} else if (begin2->right <= begin1->left) {
	++begin2;
	} else {
	int32_t left = std::max(begin1->left, begin2->left);
	int32_t right = std::min(begin1->right, begin2->right);
	FML_DCHECK(left < right);
	FML_DCHECK(new_span < res.data() + res.size());
	*new_span++ = {left, right};
	if (begin1->right == right) {
	++begin1;
	}
	if (begin2->right == right) {
	++begin2;
	}
	}
	}

	return new_span - res.data();
	}

	void DlRegion::setRects(const std::vector<SkIRect>& unsorted_rects) {
	// setRects can only be called on empty regions.
	FML_DCHECK(lines_.empty());

	size_t count = unsorted_rects.size();
	std::vector<const SkIRect*> rects(count);
	for (size_t i = 0; i < count; i++) {
	rects[i] = &unsorted_rects[i];
	bounds_.join(unsorted_rects[i]);
	}
	std::sort(rects.begin(), rects.end(), [](const SkIRect* a, const SkIRect* b) {
	if (a->top() < b->top()) {
	return true;
	}
	if (a->top() > b->top()) {
	return false;
	}
	return a->left() < b->left();
	});

	size_t active_end = 0;
	size_t next_rect = 0;
	int32_t cur_y = std::numeric_limits<int32_t>::min();
	SpanVec working_spans;

	#ifdef DlRegion_DO_STATS
	size_t active_rect_count = 0;
	size_t span_count = 0;
	int pass_count = 0;
	int line_count = 0;
	#endif

	while (next_rect < count \|\| active_end > 0) {
	// First prune passed rects out of the active list
	size_t preserve_end = 0;
	for (size_t i = 0; i < active_end; i++) {
	const SkIRect* r = rects[i];
	if (r->bottom() > cur_y) {
	rects[preserve_end++] = r;
	}
	}
	active_end = preserve_end;

	// If we have no active rects any more, jump to the top of the
	// next available input rect.
	if (active_end == 0) {
	if (next_rect >= count) {
	// No active rects and no more rects to bring in. We are done.
	break;
	}
	cur_y = rects[next_rect]->top();
	}

	// Next, insert any new rects we've reached into the active list
	while (next_rect < count) {
	const SkIRect* r = rects[next_rect];
	if (r->isEmpty()) {
	continue;
	}
	if (r->top() > cur_y) {
	break;
	}
	// We now know that we will be inserting this rect into active list
	next_rect++;
	size_t insert_at = active_end++;
	while (insert_at > 0) {
	const SkIRect* ir = rects[insert_at - 1];
	if (ir->left() <= r->left()) {
	break;
	}
	rects[insert_at--] = ir;
	}
	rects[insert_at] = r;
	}

	// We either preserved some rects in the active list or added more from
	// the remaining input rects, or we would have exited the loop above.
	FML_DCHECK(active_end != 0);
	working_spans.clear();
	FML_DCHECK(working_spans.empty());

	#ifdef DlRegion_DO_STATS
	active_rect_count += active_end;
	pass_count++;
	#endif

	// [start_x, end_x) always represents a valid span to be inserted
	// [cur_y, end_y) is the intersecting range over which all spans are valid
	int32_t start_x = rects[0]->left();
	int32_t end_x = rects[0]->right();
	int32_t end_y = rects[0]->bottom();
	for (size_t i = 1; i < active_end; i++) {
	const SkIRect* r = rects[i];
	if (r->left() > end_x) {
	working_spans.emplace_back(start_x, end_x);
	start_x = r->left();
	end_x = r->right();
	} else if (end_x < r->right()) {
	end_x = r->right();
	}
	if (end_y > r->bottom()) {
	end_y = r->bottom();
	}
	}
	working_spans.emplace_back(start_x, end_x);

	// end_y must not pass by the top of the next input rect
	if (next_rect < count && end_y > rects[next_rect]->top()) {
	end_y = rects[next_rect]->top();
	}

	// If all of the rules above work out, we should never collapse the
	// current range of Y coordinates to empty
	FML_DCHECK(end_y > cur_y);

	if (!lines_.empty() && lines_.back().bottom == cur_y &&
	spansEqual(lines_.back(), working_spans.data(),
	working_spans.data() + working_spans.size())) {
	lines_.back().bottom = end_y;
	} else {
	#ifdef DlRegion_DO_STATS
	span_count += working_spans.size();
	line_count++;
	#endif
	lines_.push_back(makeLine(cur_y, end_y, working_spans));
	}
	cur_y = end_y;
	}

	#ifdef DlRegion_DO_STATS
	double span_avg = ((double)span_count) / line_count;
	double active_avg = ((double)active_rect_count) / pass_count;
	FML_LOG(ERROR) << lines_.size() << " lines for " << count
	<< " input rects, avg " << span_avg
	<< " spans per line and avg " << active_avg
	<< " active rects per loop";
	#endif
	}

	void DlRegion::appendLine(int32_t top,
	int32_t bottom,
	const Span* begin,
	const Span* end) {
	if (lines_.empty()) {
	lines_.push_back(makeLine(top, bottom, begin, end));
	} else {
	if (lines_.back().bottom == top && spansEqual(lines_.back(), begin, end)) {
	lines_.back().bottom = bottom;
	} else {
	lines_.push_back(makeLine(top, bottom, begin, end));
	}
	}
	}

	DlRegion DlRegion::MakeUnion(const DlRegion& a, const DlRegion& b) {
	if (a.isEmpty()) {
	return b;
	} else if (b.isEmpty()) {
	return a;
	} else if (a.isSimple() && a.bounds_.contains(b.bounds_)) {
	return a;
	} else if (b.isSimple() && b.bounds_.contains(a.bounds_)) {
	return b;
	}

	DlRegion res;
	res.bounds_ = a.bounds_;
	res.bounds_.join(b.bounds_);
	res.span_buffer_.reserve(a.span_buffer_.capacity() +
	b.span_buffer_.capacity());

	auto& lines = res.lines_;
	lines.reserve(a.lines_.size() + b.lines_.size());

	auto a_it = a.lines_.begin();
	auto b_it = b.lines_.begin();
	auto a_end = a.lines_.end();
	auto b_end = b.lines_.end();

	FML_DCHECK(a_it != a_end && b_it != b_end);

	auto& a_buffer = a.span_buffer_;
	auto& b_buffer = b.span_buffer_;

	std::vector<Span> tmp;

	int32_t cur_top = std::numeric_limits<int32_t>::min();

	while (a_it != a_end && b_it != b_end) {
	auto a_top = std::max(cur_top, a_it->top);
	auto b_top = std::max(cur_top, b_it->top);
	if (a_it->bottom <= b_top) {
	res.appendLine(a_top, a_it->bottom, a_buffer, a_it->chunk_handle);
	++a_it;
	} else if (b_it->bottom <= a_top) {
	res.appendLine(b_top, b_it->bottom, b_buffer, b_it->chunk_handle);
	++b_it;
	} else {
	if (a_top < b_top) {
	res.appendLine(a_top, b_top, a_buffer, a_it->chunk_handle);
	cur_top = b_top;
	if (cur_top == a_it->bottom) {
	++a_it;
	}
	} else if (b_top < a_top) {
	res.appendLine(b_top, a_top, b_buffer, b_it->chunk_handle);
	cur_top = a_top;
	if (cur_top == b_it->bottom) {
	++b_it;
	}
	} else {
	auto new_bottom = std::min(a_it->bottom, b_it->bottom);
	FML_DCHECK(a_top == b_top);
	FML_DCHECK(new_bottom > a_top);
	FML_DCHECK(new_bottom > b_top);
	auto size = unionLineSpans(tmp, a_buffer, a_it->chunk_handle, b_buffer,
	b_it->chunk_handle);
	res.appendLine(a_top, new_bottom, tmp.data(), tmp.data() + size);
	cur_top = new_bottom;
	if (cur_top == a_it->bottom) {
	++a_it;
	}
	if (cur_top == b_it->bottom) {
	++b_it;
	}
	}
	}
	}

	FML_DCHECK(a_it == a_end \|\| b_it == b_end);

	while (a_it != a_end) {
	auto a_top = std::max(cur_top, a_it->top);
	res.appendLine(a_top, a_it->bottom, a_buffer, a_it->chunk_handle);
	++a_it;
	}

	while (b_it != b_end) {
	auto b_top = std::max(cur_top, b_it->top);
	res.appendLine(b_top, b_it->bottom, b_buffer, b_it->chunk_handle);
	++b_it;
	}

	return res;
	}

	DlRegion DlRegion::MakeIntersection(const DlRegion& a, const DlRegion& b) {
	if (!SkIRect::Intersects(a.bounds_, b.bounds_)) {
	return DlRegion();
	} else if (a.isSimple() && b.isSimple()) {
	SkIRect r(a.bounds_);
	auto res = r.intersect(b.bounds_);
	(void)res; // Suppress unused variable warning in release builds.
	FML_DCHECK(res);
	return DlRegion(r);
	} else if (a.isSimple() && a.bounds_.contains(b.bounds_)) {
	return b;
	} else if (b.isSimple() && b.bounds_.contains(a.bounds_)) {
	return a;
	}

	DlRegion res;
	res.span_buffer_.reserve(
	std::max(a.span_buffer_.capacity(), b.span_buffer_.capacity()));

	auto& lines = res.lines_;
	lines.reserve(std::min(a.lines_.size(), b.lines_.size()));

	std::vector<SpanLine>::const_iterator a_it, b_it;
	getIntersectionIterators(a.lines_, b.lines_, a_it, b_it);

	auto a_end = a.lines_.end();
	auto b_end = b.lines_.end();

	auto& a_buffer = a.span_buffer_;
	auto& b_buffer = b.span_buffer_;

	std::vector<Span> tmp;

	int32_t cur_top = std::numeric_limits<int32_t>::min();

	while (a_it != a_end && b_it != b_end) {
	auto a_top = std::max(cur_top, a_it->top);
	auto b_top = std::max(cur_top, b_it->top);
	if (a_it->bottom <= b_top) {
	++a_it;
	} else if (b_it->bottom <= a_top) {
	++b_it;
	} else {
	auto top = std::max(a_top, b_top);
	auto bottom = std::min(a_it->bottom, b_it->bottom);
	FML_DCHECK(top < bottom);
	auto size = intersectLineSpans(tmp, a_buffer, a_it->chunk_handle,
	b_buffer, b_it->chunk_handle);
	if (size > 0) {
	res.appendLine(top, bottom, tmp.data(), tmp.data() + size);
	res.bounds_.join(SkIRect::MakeLTRB(
	tmp.data()->left, top, (tmp.data() + size - 1)->right, bottom));
	}
	cur_top = bottom;
	if (cur_top == a_it->bottom) {
	++a_it;
	}
	if (cur_top == b_it->bottom) {
	++b_it;
	}
	}
	}
	FML_DCHECK(a_it == a_end \|\| b_it == b_end);
	return res;
	}

	std::vector<SkIRect> DlRegion::getRects(bool deband) const {
	std::vector<SkIRect> rects;
	if (isEmpty()) {
	return rects;
	} else if (isSimple()) {
	rects.push_back(bounds_);
	return rects;
	}

	size_t rect_count = 0;
	size_t previous_span_end = 0;
	for (const auto& line : lines_) {
	rect_count += span_buffer_.getChunkSize(line.chunk_handle);
	}
	rects.reserve(rect_count);

	for (const auto& line : lines_) {
	const Span span_begin, span_end;
	span_buffer_.getSpans(line.chunk_handle, span_begin, span_end);
	for (const auto* span = span_begin; span < span_end; ++span) {
	SkIRect rect{span->left, line.top, span->right, line.bottom};
	if (deband) {
	auto iter = rects.begin() + previous_span_end;
	// If there is rectangle previously in rects on which this one is a
	// vertical continuation, remove the previous rectangle and expand
	// this one vertically to cover the area.
	while (iter != rects.begin()) {
	--iter;
	if (iter->bottom() < rect.top()) {
	// Went all the way to previous span line.
	break;
	} else if (iter->left() == rect.left() &&
	iter->right() == rect.right()) {
	FML_DCHECK(iter->bottom() == rect.top());
	rect.fTop = iter->fTop;
	rects.erase(iter);
	--previous_span_end;
	break;
	}
	}
	}
	rects.push_back(rect);
	}
	previous_span_end = rects.size();
	}
	return rects;
	}

	bool DlRegion::isComplex() const {
	return lines_.size() > 1 \|\|
	(lines_.size() == 1 &&
	span_buffer_.getChunkSize(lines_.front().chunk_handle) > 1);
	}

	bool DlRegion::intersects(const SkIRect& rect) const {
	if (isEmpty()) {
	return false;
	}

	auto bounds_intersect = SkIRect::Intersects(bounds_, rect);

	if (isSimple()) {
	return bounds_intersect;
	}

	if (!bounds_intersect) {
	return false;
	}

	auto it = lines_.begin();
	auto end = lines_.end();
	if (lines_.size() > kBinarySearchThreshold &&
	it[kBinarySearchThreshold].bottom <= rect.fTop) {
	it = std::lower_bound(
	lines_.begin() + kBinarySearchThreshold + 1, lines_.end(), rect.fTop,
	[](const SpanLine& line, int32_t top) { return line.bottom <= top; });
	} else {
	while (it != end && it->bottom <= rect.fTop) {
	++it;
	continue;
	}
	}
	while (it != end && it->top < rect.fBottom) {
	FML_DCHECK(rect.fTop < it->bottom && it->top < rect.fBottom);
	const Span begin, end;
	span_buffer_.getSpans(it->chunk_handle, begin, end);
	while (begin != end && begin->left < rect.fRight) {
	if (begin->right > rect.fLeft) {
	return true;
	}
	++begin;
	}
	++it;
	}

	return false;
	}

	bool DlRegion::spansIntersect(const Span* begin1,
	const Span* end1,
	const Span* begin2,
	const Span* end2) {
	while (begin1 != end1 && begin2 != end2) {
	if (begin1->right <= begin2->left) {
	++begin1;
	} else if (begin2->right <= begin1->left) {
	++begin2;
	} else {
	return true;
	}
	}
	return false;
	}

	void DlRegion::getIntersectionIterators(
	const std::vector<SpanLine>& a_lines,
	const std::vector<SpanLine>& b_lines,
	std::vector<SpanLine>::const_iterator& a_it,
	std::vector<SpanLine>::const_iterator& b_it) {
	a_it = a_lines.begin();
	auto a_end = a_lines.end();
	b_it = b_lines.begin();
	auto b_end = b_lines.end();

	FML_DCHECK(a_it != a_end && b_it != b_end);

	auto a_len = a_end - a_it;
	auto b_len = b_end - b_it;

	if (a_len > kBinarySearchThreshold &&
	a_it[kBinarySearchThreshold].bottom <= b_it->top) {
	a_it = std::lower_bound(
	a_lines.begin() + kBinarySearchThreshold + 1, a_lines.end(), b_it->top,
	[](const SpanLine& line, int32_t top) { return line.bottom <= top; });
	} else if (b_len > kBinarySearchThreshold &&
	b_it[kBinarySearchThreshold].bottom <= a_it->top) {
	b_it = std::lower_bound(
	b_lines.begin() + kBinarySearchThreshold + 1, b_lines.end(), a_it->top,
	[](const SpanLine& line, int32_t top) { return line.bottom <= top; });
	}
	}

	bool DlRegion::intersects(const DlRegion& region) const {
	if (isEmpty() \|\| region.isEmpty()) {
	return false;
	}

	auto our_complex = isComplex();
	auto their_complex = region.isComplex();
	auto bounds_intersect = SkIRect::Intersects(bounds_, region.bounds_);

	if (!our_complex && !their_complex) {
	return bounds_intersect;
	}

	if (!bounds_intersect) {
	return false;
	}

	if (!our_complex) {
	return region.intersects(bounds_);
	}

	if (!their_complex) {
	return intersects(region.bounds_);
	}

	std::vector<SpanLine>::const_iterator ours, theirs;
	getIntersectionIterators(lines_, region.lines_, ours, theirs);
	auto ours_end = lines_.end();
	auto theirs_end = region.lines_.end();

	while (ours != ours_end && theirs != theirs_end) {
	if (ours->bottom <= theirs->top) {
	++ours;
	} else if (theirs->bottom <= ours->top) {
	++theirs;
	} else {
	FML_DCHECK(ours->top < theirs->bottom && theirs->top < ours->bottom);
	const Span ours_begin, ours_end;
	span_buffer_.getSpans(ours->chunk_handle, ours_begin, ours_end);
	const Span theirs_begin, theirs_end;
	region.span_buffer_.getSpans(theirs->chunk_handle, theirs_begin,
	theirs_end);
	if (spansIntersect(ours_begin, ours_end, theirs_begin, theirs_end)) {
	return true;
	}
	if (ours->bottom < theirs->bottom) {
	++ours;
	} else {
	++theirs;
	}
	}
	}
	return false;
	}

	} // namespace flutter