--- a/gfx/src/nsRegion.cpp
+++ b/gfx/src/nsRegion.cpp
@@ -5,608 +5,514 @@
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#include "nsRegion.h"
#include "nsTArray.h"
#include "gfxUtils.h"
#include "mozilla/ToString.h"
+using namespace std;
+
+void
+nsRegion::AssertStateInternal() const
+{
+ bool failed = false;
+ // Verify consistent state inside the region.
+ int32_t lastY = INT32_MIN;
+ int32_t lowestX = INT32_MAX;
+ int32_t highestX = INT32_MIN;
+ for (auto iter = mBands.begin(); iter != mBands.end(); iter++) {
+ const Band& band = *iter;
+ if (band.bottom <= band.top) {
+ failed = true;
+ break;
+ }
+ if (band.top < lastY) {
+ failed = true;
+ break;
+ }
+ lastY = band.bottom;
+
+ lowestX = std::min(lowestX, band.mStrips.begin()->left);
+ highestX = std::max(highestX, band.mStrips.LastElement().right);
+
+ int32_t lastX = INT32_MIN;
+ if (iter != mBands.begin()) {
+ auto prev = iter;
+ prev--;
+
+ if (prev->bottom == iter->top) {
+ if (band.EqualStrips(*prev)) {
+ failed = true;
+ break;
+ }
+ }
+ }
+ for (const Strip& strip : band.mStrips) {
+ if (strip.right <= strip.left) {
+ failed = true;
+ break;
+ }
+ if (strip.left <= lastX) {
+ failed = true;
+ break;
+ }
+ lastX = strip.right;
+ }
+ if (failed) {
+ break;
+ }
+ }
+
+ if (!(mBounds == CalculateBounds())) {
+ failed = true;
+ }
+
+ if (failed) {
+#ifdef DEBUG_REGIONS
+ if (mCurrentOpGenerator) {
+ mCurrentOpGenerator->OutputOp();
+ }
+#endif
+ MOZ_ASSERT(false);
+ }
+}
+
bool nsRegion::Contains(const nsRegion& aRgn) const
{
// XXX this could be made faster by iterating over
// both regions at the same time some how
for (auto iter = aRgn.RectIter(); !iter.Done(); iter.Next()) {
if (!Contains(iter.Get())) {
return false;
}
}
return true;
}
bool nsRegion::Intersects(const nsRect& aRect) const
{
- // XXX this could be made faster by using pixman_region32_contains_rect
- for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
- if (iter.Get().Intersects(aRect)) {
- return true;
+ if (mBands.IsEmpty()) {
+ return mBounds.Intersects(aRect);
+ }
+
+ if (!mBounds.Intersects(aRect)) {
+ return false;
+ }
+
+ Strip rectStrip(aRect.X(), aRect.XMost());
+
+ auto iter = mBands.begin();
+ while (iter != mBands.end()) {
+ if (iter->top >= aRect.YMost()) {
+ return false;
}
+
+ if (iter->bottom <= aRect.Y()) {
+ // This band is entirely before aRect, move on.
+ iter++;
+ continue;
+ }
+
+ if (!iter->Intersects(rectStrip)) {
+ // This band does not intersect aRect horizontally. Move on.
+ iter++;
+ continue;
+ }
+
+ // This band intersects with aRect.
+ return true;
}
+
return false;
}
void nsRegion::Inflate(const nsMargin& aMargin)
{
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
- for (int i=0; i<n; i++) {
- nsRect rect = BoxToRect(boxes[i]);
+ nsRegion newRegion;
+ for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+ nsRect rect = iter.Get();
rect.Inflate(aMargin);
- boxes[i] = RectToBox(rect);
+ newRegion.AddRect(rect);
}
- pixman_region32_t region;
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(®ion, boxes, n);
-
- pixman_region32_fini(&mImpl);
- mImpl = region;
+ *this = std::move(newRegion);
}
void nsRegion::SimplifyOutward (uint32_t aMaxRects)
{
MOZ_ASSERT(aMaxRects >= 1, "Invalid max rect count");
- if (GetNumRects() <= aMaxRects)
+ if (GetNumRects() <= aMaxRects) {
return;
-
- pixman_box32_t *boxes;
- int n;
- boxes = pixman_region32_rectangles(&mImpl, &n);
+ }
// Try combining rects in horizontal bands into a single rect
- int dest = 0;
- for (int src = 1; src < n; src++)
- {
- // The goal here is to try to keep groups of rectangles that are vertically
- // discontiguous as separate rectangles in the final region. This is
- // simple and fast to implement and page contents tend to vary more
- // vertically than horizontally (which is why our rectangles are stored
- // sorted by y-coordinate, too).
- //
- // Note: if boxes share y1 because of the canonical representation they
- // will share y2
- while ((src < (n)) && boxes[dest].y1 == boxes[src].y1) {
- // merge box[i] and box[i+1]
- boxes[dest].x2 = boxes[src].x2;
- src++;
- }
- if (src < n) {
- dest++;
- boxes[dest] = boxes[src];
+ // The goal here is to try to keep groups of rectangles that are vertically
+ // discontiguous as separate rectangles in the final region. This is
+ // simple and fast to implement and page contents tend to vary more
+ // vertically than horizontally (which is why our rectangles are stored
+ // sorted by y-coordinate, too).
+ //
+ // Note: if boxes share y1 because of the canonical representation they
+ // will share y2
+
+ size_t idx = 0;
+
+ while (idx < mBands.Length()) {
+ size_t oldIdx = idx;
+ mBands[idx].mStrips.begin()->right = mBands[idx].mStrips.LastElement().right;
+ mBands[idx].mStrips.TruncateLength(1);
+ idx++;
+
+ // Merge any bands with the same bounds.
+ while (idx < mBands.Length() &&
+ mBands[idx].mStrips.begin()->left == mBands[oldIdx].mStrips.begin()->left &&
+ mBands[idx].mStrips.LastElement().right == mBands[oldIdx].mStrips.begin()->right) {
+ mBands[oldIdx].bottom = mBands[idx].bottom;
+ mBands.RemoveElementAt(idx);
}
}
- uint32_t reducedCount = dest+1;
- // pixman has a special representation for
- // regions of 1 rectangle. So just use the
- // bounds in that case
- if (reducedCount > 1 && reducedCount <= aMaxRects) {
- // reach into pixman and lower the number
- // of rects stored in data.
- mImpl.data->numRects = reducedCount;
- } else {
+ AssertState();
+
+ // mBands.size() is now equal to our rect count.
+ if (mBands.Length() > aMaxRects) {
*this = GetBounds();
}
}
// compute the covered area difference between two rows.
// by iterating over both rows simultaneously and adding up
// the additional increase in area caused by extending each
// of the rectangles to the combined height of both rows
-static uint32_t ComputeMergedAreaIncrease(pixman_box32_t *topRects,
- pixman_box32_t *topRectsEnd,
- pixman_box32_t *bottomRects,
- pixman_box32_t *bottomRectsEnd)
+uint32_t
+nsRegion::ComputeMergedAreaIncrease(const Band& aTopBand,
+ const Band& aBottomBand)
{
uint32_t totalArea = 0;
- struct pt {
- int32_t x, y;
- };
+ uint32_t topHeight = aBottomBand.top - aTopBand.top;
+ uint32_t bottomHeight = aBottomBand.bottom - aTopBand.bottom;
+ uint32_t currentStripBottom = 0;
- pt *i = (pt*)topRects;
- pt *end_i = (pt*)topRectsEnd;
- pt *j = (pt*)bottomRects;
- pt *end_j = (pt*)bottomRectsEnd;
- bool top = false;
- bool bottom = false;
+ // This could be done with slightly better worse case performance by merging these two
+ // for-loops, but this makes the code a lot easier to understand.
+ for (auto& strip : aTopBand.mStrips) {
+ if (currentStripBottom == aBottomBand.mStrips.Length() || strip.right < aBottomBand.mStrips[currentStripBottom].left) {
+ totalArea += bottomHeight * strip.Size();
+ continue;
+ }
- int cur_x = i->x;
- bool top_next = top;
- bool bottom_next = bottom;
- //XXX: we could probably simplify this condition and perhaps move it into the loop below
- if (j->x < cur_x) {
- cur_x = j->x;
- j++;
- bottom_next = !bottom;
- } else if (j->x == cur_x) {
- i++;
- top_next = !top;
- bottom_next = !bottom;
- j++;
- } else {
- top_next = !top;
- i++;
- }
+ int32_t currentX = strip.left;
+ while (currentStripBottom != aBottomBand.mStrips.Length() && aBottomBand.mStrips[currentStripBottom].left < strip.right) {
+ if (currentX >= strip.right) {
+ break;
+ }
+ if (currentX < aBottomBand.mStrips[currentStripBottom].left) {
+ // Add the part that's not intersecting.
+ totalArea += (aBottomBand.mStrips[currentStripBottom].left - currentX) * bottomHeight;
+ }
+
+ currentX = std::max(aBottomBand.mStrips[currentStripBottom].right, currentX);
+ currentStripBottom++;
+ }
- int topRectsHeight = topRects->y2 - topRects->y1;
- int bottomRectsHeight = bottomRects->y2 - bottomRects->y1;
- int inbetweenHeight = bottomRects->y1 - topRects->y2;
- int width = cur_x;
- // top and bottom are the in-status to the left of cur_x
- do {
- if (top && !bottom) {
- totalArea += (inbetweenHeight+bottomRectsHeight)*width;
- } else if (bottom && !top) {
- totalArea += (inbetweenHeight+topRectsHeight)*width;
- } else if (bottom && top) {
- totalArea += (inbetweenHeight)*width;
+ // Add remainder of this strip.
+ if (currentX < strip.right) {
+ totalArea += (strip.right - currentX) * bottomHeight;
+ }
+ if (currentStripBottom) {
+ currentStripBottom--;
+ }
+ }
+ uint32_t currentStripTop = 0;
+ for (auto& strip : aBottomBand.mStrips) {
+ if (currentStripTop == aTopBand.mStrips.Length() || strip.right < aTopBand.mStrips[currentStripTop].left) {
+ totalArea += topHeight * strip.Size();
+ continue;
}
- top = top_next;
- bottom = bottom_next;
- // find the next edge
- if (i->x < j->x) {
- top_next = !top;
- width = i->x - cur_x;
- cur_x = i->x;
- i++;
- } else if (j->x < i->x) {
- bottom_next = !bottom;
- width = j->x - cur_x;
- cur_x = j->x;
- j++;
- } else { // i->x == j->x
- top_next = !top;
- bottom_next = !bottom;
- width = i->x - cur_x;
- cur_x = i->x;
- i++;
- j++;
+
+ int32_t currentX = strip.left;
+ while (currentStripTop != aTopBand.mStrips.Length() && aTopBand.mStrips[currentStripTop].left < strip.right) {
+ if (currentX >= strip.right) {
+ break;
+ }
+ if (currentX < aTopBand.mStrips[currentStripTop].left) {
+ // Add the part that's not intersecting.
+ totalArea += (aTopBand.mStrips[currentStripTop].left - currentX) * topHeight;
+ }
+
+ currentX = std::max(aTopBand.mStrips[currentStripTop].right, currentX);
+ currentStripTop++;
}
- } while (i < end_i && j < end_j);
- // handle any remaining rects
- while (i < end_i) {
- width = i->x - cur_x;
- cur_x = i->x;
- i++;
- if (top)
- totalArea += (inbetweenHeight+bottomRectsHeight)*width;
- top = !top;
- }
-
- while (j < end_j) {
- width = j->x - cur_x;
- cur_x = j->x;
- j++;
- if (bottom)
- totalArea += (inbetweenHeight+topRectsHeight)*width;
- bottom = !bottom;
+ // Add remainder of this strip.
+ if (currentX < strip.right) {
+ totalArea += (strip.right - currentX) * topHeight;
+ }
+ if (currentStripTop) {
+ currentStripTop--;
+ }
}
return totalArea;
}
-static pixman_box32_t *
-CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end)
-{
- // XXX: std::copy
- pixman_box32_t *src_it = src_start;
- while (src_it < src_end) {
- *dest_it++ = *src_it++;
- }
- return dest_it;
-}
-
-
-#define WRITE_RECT(x1, x2, y1, y2) \
- do { \
- tmpRect->x1 = x1; \
- tmpRect->x2 = x2; \
- tmpRect->y1 = y1; \
- tmpRect->y2 = y2; \
- tmpRect++; \
- } while (0)
-
-/* If 'r' overlaps the current rect, then expand the current rect to include
- * it. Otherwise write the current rect out to tmpRect, and set r as the
- * updated current rect. */
-#define MERGE_RECT(r) \
- do { \
- if (r->x1 <= x2) { \
- if (x2 < r->x2) \
- x2 = r->x2; \
- } else { \
- WRITE_RECT(x1, x2, y1, y2); \
- x1 = r->x1; \
- x2 = r->x2; \
- } \
- r++; \
- } while (0)
-
-
-/* Can we merge two sets of rects without extra space?
- * Yes, but not easily. We can even do it stably
- * but we don't need that property.
- *
- * This is written in the style of pixman_region_union_o */
-static pixman_box32_t *
-MergeRects(pixman_box32_t *r1,
- pixman_box32_t *r1_end,
- pixman_box32_t *r2,
- pixman_box32_t *r2_end,
- pixman_box32_t *tmpRect)
-{
- /* This routine works by maintaining the current
- * rectangle in x1,x2,y1,y2 and either merging
- * in the left most rectangle if it overlaps or
- * outputing the current rectangle and setting
- * it to the the left most one */
- const int y1 = r1->y1;
- const int y2 = r2->y2;
- int x1;
- int x2;
-
- /* Find the left-most edge */
- if (r1->x1 < r2->x1) {
- x1 = r1->x1;
- x2 = r1->x2;
- r1++;
- } else {
- x1 = r2->x1;
- x2 = r2->x2;
- r2++;
- }
-
- while (r1 != r1_end && r2 != r2_end) {
- /* Find and merge the left-most rectangle */
- if (r1->x1 < r2->x1)
- MERGE_RECT (r1);
- else
- MERGE_RECT (r2);
- }
-
- /* Finish up any left overs */
- if (r1 != r1_end) {
- do {
- MERGE_RECT (r1);
- } while (r1 != r1_end);
- } else if (r2 != r2_end) {
- do {
- MERGE_RECT(r2);
- } while (r2 != r2_end);
- }
-
- /* Finish up the last rectangle */
- WRITE_RECT(x1, x2, y1, y2);
-
- return tmpRect;
-}
-
void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold)
{
-
- pixman_box32_t *boxes;
- int n;
- boxes = pixman_region32_rectangles(&mImpl, &n);
-
- // if we have no rectangles then we're done
- if (!n)
+ if (mBands.Length() < 2) {
+ // We have only one or no row and we're done.
return;
-
- pixman_box32_t *end = boxes + n;
- pixman_box32_t *topRectsEnd = boxes+1;
- pixman_box32_t *topRects = boxes;
-
- // we need some temporary storage for merging both rows of rectangles
- AutoTArray<pixman_box32_t, 10> tmpStorage;
- tmpStorage.SetCapacity(n);
- pixman_box32_t *tmpRect = tmpStorage.Elements();
-
- pixman_box32_t *destRect = boxes;
- pixman_box32_t *rect = tmpRect;
- // find the end of the first span of rectangles
- while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
- topRectsEnd++;
}
- // if we only have one row we are done
- if (topRectsEnd == end)
- return;
-
- pixman_box32_t *bottomRects = topRectsEnd;
- pixman_box32_t *bottomRectsEnd = bottomRects+1;
+ uint32_t currentBand = 0;
do {
- // find the end of the bottom span of rectangles
- while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
- bottomRectsEnd++;
- }
- uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd,
- bottomRects, bottomRectsEnd);
+ Band& band = mBands[currentBand];
+
+ uint32_t totalArea = ComputeMergedAreaIncrease(band, mBands[currentBand + 1]);
if (totalArea <= aThreshold) {
- // merge the rects into tmpRect
- rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect);
-
- // set topRects to where the newly merged rects will be so that we use them
- // as our next set of topRects
- topRects = destRect;
- // copy the merged rects back into the destination
- topRectsEnd = CopyRow(destRect, tmpRect, rect);
+ for (Strip& strip : mBands[currentBand + 1].mStrips) {
+ // This could use an optimized function to merge two bands.
+ band.InsertStrip(strip);
+ }
+ band.bottom = mBands[currentBand + 1].bottom;
+ mBands.RemoveElementAt(currentBand + 1);
} else {
- // copy the unmerged rects
- destRect = CopyRow(destRect, topRects, topRectsEnd);
+ currentBand++;
+ }
+ } while (currentBand + 1 < mBands.Length());
- topRects = bottomRects;
- topRectsEnd = bottomRectsEnd;
- if (bottomRectsEnd == end) {
- // copy the last row when we are done
- topRectsEnd = CopyRow(destRect, topRects, topRectsEnd);
- }
- }
- bottomRects = bottomRectsEnd;
- } while (bottomRectsEnd != end);
-
-
- uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n);
- // pixman has a special representation for
- // regions of 1 rectangle. So just use the
- // bounds in that case
- if (reducedCount > 1) {
- // reach into pixman and lower the number
- // of rects stored in data.
- this->mImpl.data->numRects = reducedCount;
- } else {
- *this = GetBounds();
- }
+ EnsureSimplified();
+ AssertState();
}
typedef void (*visit_fn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2);
-static bool VisitNextEdgeBetweenRect(visit_fn visit, void *closure, VisitSide side,
- pixman_box32_t *&r1, pixman_box32_t *&r2, const int y, int &x1)
+void nsRegion::VisitEdges (visit_fn visit, void *closure)
{
- // check for overlap
- if (r1->x2 >= r2->x1) {
- MOZ_ASSERT(r2->x1 >= x1);
- visit(closure, side, x1, y, r2->x1, y);
-
- // find the rect that ends first or always drop the one that comes first?
- if (r1->x2 < r2->x2) {
- x1 = r1->x2;
- r1++;
- } else {
- x1 = r2->x2;
- r2++;
- }
- return true;
- } else {
- MOZ_ASSERT(r1->x2 < r2->x2);
- // we handle the corners by just extending the top and bottom edges
- visit(closure, side, x1, y, r1->x2+1, y);
- r1++;
- // we assign x1 because we can assume that x1 <= r2->x1 - 1
- // However the caller may know better and if so, may update
- // x1 to r1->x1
- x1 = r2->x1 - 1;
- return false;
+ if (mBands.IsEmpty()) {
+ visit(closure, VisitSide::LEFT, mBounds.X(), mBounds.Y(), mBounds.X(), mBounds.YMost());
+ visit(closure, VisitSide::RIGHT, mBounds.XMost(), mBounds.Y(), mBounds.XMost(), mBounds.YMost());
+ visit(closure, VisitSide::TOP, mBounds.X() - 1, mBounds.Y(), mBounds.XMost() + 1, mBounds.Y());
+ visit(closure, VisitSide::BOTTOM, mBounds.X() - 1, mBounds.YMost(), mBounds.XMost() + 1, mBounds.YMost());
+ return;
}
-}
-
-//XXX: if we need to this can compute the end of the row
-static void
-VisitSides(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
- // XXX: we can drop LEFT/RIGHT and just use the orientation
- // of the line if it makes sense
- while (r != r_end) {
- visit(closure, VisitSide::LEFT, r->x1, r->y1, r->x1, r->y2);
- visit(closure, VisitSide::RIGHT, r->x2, r->y1, r->x2, r->y2);
- r++;
- }
-}
-static void
-VisitAbove(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
- while (r != r_end) {
- visit(closure, VisitSide::TOP, r->x1-1, r->y1, r->x2+1, r->y1);
- r++;
- }
-}
-
-static void
-VisitBelow(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
- while (r != r_end) {
- visit(closure, VisitSide::BOTTOM, r->x1-1, r->y2, r->x2+1, r->y2);
- r++;
- }
-}
-
-static pixman_box32_t *
-VisitInbetween(visit_fn visit, void *closure, pixman_box32_t *r1,
- pixman_box32_t *r1_end,
- pixman_box32_t *r2,
- pixman_box32_t *r2_end)
-{
- const int y = r1->y2;
- int x1;
-
- bool overlap = false;
- while (r1 != r1_end && r2 != r2_end) {
- if (!overlap) {
- /* Find the left-most edge */
- if (r1->x1 < r2->x1) {
- x1 = r1->x1 - 1;
- } else {
- x1 = r2->x1 - 1;
- }
- }
-
- MOZ_ASSERT((x1 >= (r1->x1 - 1)) || (x1 >= (r2->x1 - 1)));
- if (r1->x1 < r2->x1) {
- overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::BOTTOM, r1, r2, y, x1);
- } else {
- overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::TOP, r2, r1, y, x1);
- }
+ auto band = std::begin(mBands);
+ auto bandFinal = std::end(mBands);
+ bandFinal--;
+ for (const Strip& strip : band->mStrips) {
+ visit(closure, VisitSide::LEFT, strip.left, band->top, strip.left, band->bottom);
+ visit(closure, VisitSide::RIGHT, strip.right, band->top, strip.right, band->bottom);
+ visit(closure, VisitSide::TOP, strip.left - 1, band->top, strip.right + 1, band->top);
}
- /* Finish up which ever row has remaining rects*/
- if (r1 != r1_end) {
- // top row
+ if (band != bandFinal) {
do {
- visit(closure, VisitSide::BOTTOM, x1, y, r1->x2 + 1, y);
- r1++;
- if (r1 == r1_end)
- break;
- x1 = r1->x1 - 1;
- } while (true);
- } else if (r2 != r2_end) {
- // bottom row
- do {
- visit(closure, VisitSide::TOP, x1, y, r2->x2 + 1, y);
- r2++;
- if (r2 == r2_end)
- break;
- x1 = r2->x1 - 1;
- } while (true);
+ Band& topBand = *band;
+ band++;
+
+ for (const Strip& strip : band->mStrips) {
+ visit(closure, VisitSide::LEFT, strip.left, band->top, strip.left, band->bottom);
+ visit(closure, VisitSide::RIGHT, strip.right, band->top, strip.right, band->bottom);
+ }
+
+ if (band->top == topBand.bottom) {
+ // Two bands touching each other vertically.
+ Band& bottomBand = *band;
+ auto topStrip = std::begin(topBand.mStrips);
+ auto bottomStrip = std::begin(bottomBand.mStrips);
+
+ int y = topBand.bottom;
+
+ // State from this point on along the vertical edge:
+ // 0 - Empty
+ // 1 - Touched by top rect
+ // 2 - Touched by bottom rect
+ // 3 - Touched on both sides
+ int state;
+ const int TouchedByNothing = 0;
+ const int TouchedByTop = 1;
+ const int TouchedByBottom = 2;
+ // We always start with nothing.
+ int oldState = TouchedByNothing;
+ // Last state change, adjusted by -1 if the last state change was
+ // a change away from 0.
+ int lastX = std::min(topStrip->left, bottomStrip->left) - 1;
+
+ // Current edge being considered for top and bottom, 0 - left, 1 - right.
+ bool topEdgeIsLeft = true;
+ bool bottomEdgeIsLeft = true;
+ while (topStrip != std::end(topBand.mStrips) && bottomStrip != std::end(bottomBand.mStrips)) {
+ int topPos;
+ int bottomPos;
+ if (topEdgeIsLeft) {
+ topPos = topStrip->left;
+ } else {
+ topPos = topStrip->right;
+ }
+ if (bottomEdgeIsLeft) {
+ bottomPos = bottomStrip->left;
+ } else {
+ bottomPos = bottomStrip->right;
+ }
+
+ int currentX = std::min(topPos, bottomPos);
+ if (topPos < bottomPos) {
+ if (topEdgeIsLeft) {
+ state = oldState | TouchedByTop;
+ } else {
+ state = oldState ^ TouchedByTop;
+ topStrip++;
+ }
+ topEdgeIsLeft = !topEdgeIsLeft;
+ } else if (bottomPos < topPos) {
+ if (bottomEdgeIsLeft) {
+ state = oldState | TouchedByBottom;
+ } else {
+ state = oldState ^ TouchedByBottom;
+ bottomStrip++;
+ }
+ bottomEdgeIsLeft = !bottomEdgeIsLeft;
+ } else {
+ // bottomPos == topPos
+ state = TouchedByNothing;
+ if (bottomEdgeIsLeft) {
+ state = TouchedByBottom;
+ } else {
+ bottomStrip++;
+ }
+ if (topEdgeIsLeft) {
+ state |= TouchedByTop;
+ } else {
+ topStrip++;
+ }
+ topEdgeIsLeft = !topEdgeIsLeft;
+ bottomEdgeIsLeft = !bottomEdgeIsLeft;
+ }
+
+ MOZ_ASSERT(state != oldState);
+ if (oldState == TouchedByNothing) {
+ // We had nothing before, make sure the left edge will be padded.
+ lastX = currentX - 1;
+ } else if (oldState == TouchedByTop) {
+ if (state == TouchedByNothing) {
+ visit(closure, VisitSide::BOTTOM, lastX, y, currentX + 1, y);
+ } else {
+ visit(closure, VisitSide::BOTTOM, lastX, y, currentX, y);
+ lastX = currentX;
+ }
+ } else if (oldState == TouchedByBottom) {
+ if (state == TouchedByNothing) {
+ visit(closure, VisitSide::TOP, lastX, y, currentX + 1, y);
+ } else {
+ visit(closure, VisitSide::TOP, lastX, y, currentX, y);
+ lastX = currentX;
+ }
+ } else {
+ lastX = currentX;
+ }
+ oldState = state;
+ }
+
+ MOZ_ASSERT(!state || (topEdgeIsLeft || bottomEdgeIsLeft));
+ if (topStrip != std::end(topBand.mStrips)) {
+ if (!topEdgeIsLeft) {
+ visit(closure, VisitSide::BOTTOM, lastX, y, topStrip->right + 1, y);
+ topStrip++;
+ }
+ while (topStrip != std::end(topBand.mStrips)) {
+ visit(closure, VisitSide::BOTTOM, topStrip->left - 1, y, topStrip->right + 1, y);
+ topStrip++;
+ }
+ } else if (bottomStrip != std::end(bottomBand.mStrips)) {
+ if (!bottomEdgeIsLeft) {
+ visit(closure, VisitSide::TOP, lastX, y, bottomStrip->right + 1, y);
+ bottomStrip++;
+ }
+ while (bottomStrip != std::end(bottomBand.mStrips)) {
+ visit(closure, VisitSide::TOP, bottomStrip->left - 1, y, bottomStrip->right + 1, y);
+ bottomStrip++;
+ }
+ }
+ } else {
+ for (const Strip& strip : topBand.mStrips) {
+ visit(closure, VisitSide::BOTTOM, strip.left - 1, topBand.bottom, strip.right + 1, topBand.bottom);
+ }
+ for (const Strip& strip : band->mStrips) {
+ visit(closure, VisitSide::TOP, strip.left - 1, band->top, strip.right + 1, band->top);
+ }
+ }
+ } while (band != bandFinal);
}
- return 0;
-}
-
-void nsRegion::VisitEdges (visit_fn visit, void *closure)
-{
- pixman_box32_t *boxes;
- int n;
- boxes = pixman_region32_rectangles(&mImpl, &n);
-
- // if we have no rectangles then we're done
- if (!n)
- return;
-
- pixman_box32_t *end = boxes + n;
- pixman_box32_t *topRectsEnd = boxes + 1;
- pixman_box32_t *topRects = boxes;
-
- // find the end of the first span of rectangles
- while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
- topRectsEnd++;
+ for (const Strip& strip : band->mStrips) {
+ visit(closure, VisitSide::BOTTOM, strip.left - 1, band->bottom, strip.right + 1, band->bottom);
}
-
- // In order to properly handle convex corners we always visit the sides first
- // that way when we visit the corners we can pad using the value from the sides
- VisitSides(visit, closure, topRects, topRectsEnd);
-
- VisitAbove(visit, closure, topRects, topRectsEnd);
-
- pixman_box32_t *bottomRects = topRects;
- pixman_box32_t *bottomRectsEnd = topRectsEnd;
- if (topRectsEnd != end) {
- do {
- // find the next row of rects
- bottomRects = topRectsEnd;
- bottomRectsEnd = topRectsEnd + 1;
- while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
- bottomRectsEnd++;
- }
-
- VisitSides(visit, closure, bottomRects, bottomRectsEnd);
-
- if (topRects->y2 == bottomRects->y1) {
- VisitInbetween(visit, closure, topRects, topRectsEnd,
- bottomRects, bottomRectsEnd);
- } else {
- VisitBelow(visit, closure, topRects, topRectsEnd);
- VisitAbove(visit, closure, bottomRects, bottomRectsEnd);
- }
-
- topRects = bottomRects;
- topRectsEnd = bottomRectsEnd;
- } while (bottomRectsEnd != end);
- }
-
- // the bottom of the region doesn't touch anything else so we
- // can always visit it at the end
- VisitBelow(visit, closure, bottomRects, bottomRectsEnd);
}
void nsRegion::SimplifyInward (uint32_t aMaxRects)
{
NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
if (GetNumRects() <= aMaxRects)
return;
SetEmpty();
}
uint64_t nsRegion::Area () const
{
+ if (mBands.IsEmpty()) {
+ return mBounds.Area();
+ }
+
uint64_t area = 0;
- for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
- const nsRect& rect = iter.Get();
- area += uint64_t(rect.Width()) * rect.Height();
+ for (const Band& band : mBands) {
+ uint32_t height = band.bottom - band.top;
+ for (const Strip& strip : band.mStrips) {
+ area += (strip.right - strip.left) * height;
+ }
}
+
return area;
}
nsRegion& nsRegion::ScaleRoundOut (float aXScale, float aYScale)
{
if (mozilla::gfx::FuzzyEqual(aXScale, 1.0f) &&
mozilla::gfx::FuzzyEqual(aYScale, 1.0f)) {
return *this;
}
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
- for (int i=0; i<n; i++) {
- nsRect rect = BoxToRect(boxes[i]);
+ nsRegion newRegion;
+ for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+ nsRect rect = iter.Get();
rect.ScaleRoundOut(aXScale, aYScale);
- boxes[i] = RectToBox(rect);
+ newRegion.AddRect(rect);
}
- pixman_region32_t region;
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(®ion, boxes, n);
-
- pixman_region32_fini(&mImpl);
- mImpl = region;
+ *this = std::move(newRegion);
return *this;
}
nsRegion& nsRegion::ScaleInverseRoundOut (float aXScale, float aYScale)
{
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
- for (int i=0; i<n; i++) {
- nsRect rect = BoxToRect(boxes[i]);
+ nsRegion newRegion;
+ for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+ nsRect rect = iter.Get();
rect.ScaleInverseRoundOut(aXScale, aYScale);
- boxes[i] = RectToBox(rect);
+ newRegion.AddRect(rect);
}
- pixman_region32_t region;
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(®ion, boxes, n);
-
- pixman_region32_fini(&mImpl);
- mImpl = region;
+ *this = std::move(newRegion);
return *this;
}
static mozilla::gfx::IntRect
TransformRect(const mozilla::gfx::IntRect& aRect, const mozilla::gfx::Matrix4x4& aTransform)
{
if (aRect.IsEmpty()) {
return mozilla::gfx::IntRect();
@@ -621,102 +527,71 @@ TransformRect(const mozilla::gfx::IntRec
return mozilla::gfx::IntRect();
}
return intRect;
}
nsRegion& nsRegion::Transform (const mozilla::gfx::Matrix4x4 &aTransform)
{
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
- for (int i=0; i<n; i++) {
- nsRect rect = BoxToRect(boxes[i]);
- boxes[i] = RectToBox(nsIntRegion::ToRect(TransformRect(nsIntRegion::FromRect(rect), aTransform)));
+ nsRegion newRegion;
+ for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+ nsRect rect = nsIntRegion::ToRect(TransformRect(nsIntRegion::FromRect(iter.Get()), aTransform));
+ newRegion.AddRect(rect);
}
- pixman_region32_t region;
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(®ion, boxes, n);
-
- pixman_region32_fini(&mImpl);
- mImpl = region;
+ *this = std::move(newRegion);
return *this;
}
nsRegion nsRegion::ScaleToOtherAppUnitsRoundOut (int32_t aFromAPP, int32_t aToAPP) const
{
if (aFromAPP == aToAPP) {
return *this;
}
-
- nsRegion region = *this;
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
- for (int i=0; i<n; i++) {
- nsRect rect = BoxToRect(boxes[i]);
+ nsRegion newRegion;
+ for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+ nsRect rect = iter.Get();
rect = rect.ScaleToOtherAppUnitsRoundOut(aFromAPP, aToAPP);
- boxes[i] = RectToBox(rect);
+ newRegion.AddRect(rect);
}
- pixman_region32_t pixmanRegion;
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(&pixmanRegion, boxes, n);
-
- pixman_region32_fini(®ion.mImpl);
- region.mImpl = pixmanRegion;
- return region;
+ return newRegion;
}
nsRegion nsRegion::ScaleToOtherAppUnitsRoundIn (int32_t aFromAPP, int32_t aToAPP) const
{
if (aFromAPP == aToAPP) {
return *this;
}
- nsRegion region = *this;
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
- for (int i=0; i<n; i++) {
- nsRect rect = BoxToRect(boxes[i]);
+ nsRegion newRegion;
+ for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+ nsRect rect = iter.Get();
rect = rect.ScaleToOtherAppUnitsRoundIn(aFromAPP, aToAPP);
- boxes[i] = RectToBox(rect);
+ newRegion.AddRect(rect);
}
- pixman_region32_t pixmanRegion;
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(&pixmanRegion, boxes, n);
-
- pixman_region32_fini(®ion.mImpl);
- region.mImpl = pixmanRegion;
- return region;
+ return newRegion;
}
nsIntRegion nsRegion::ToPixels (nscoord aAppUnitsPerPixel, bool aOutsidePixels) const
{
- nsRegion region = *this;
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
- for (int i=0; i<n; i++) {
- nsRect rect = BoxToRect(boxes[i]);
+ nsIntRegion intRegion;
+ for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
mozilla::gfx::IntRect deviceRect;
+ nsRect rect = iter.Get();
if (aOutsidePixels)
deviceRect = rect.ToOutsidePixels(aAppUnitsPerPixel);
else
deviceRect = rect.ToNearestPixels(aAppUnitsPerPixel);
-
- boxes[i] = RectToBox(deviceRect);
+ intRegion.OrWith(deviceRect);
}
- nsIntRegion intRegion;
- pixman_region32_fini(&intRegion.mImpl.mImpl);
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n);
-
return intRegion;
}
nsIntRegion nsRegion::ToOutsidePixels (nscoord aAppUnitsPerPixel) const
{
return ToPixels(aAppUnitsPerPixel, true);
}
@@ -736,33 +611,22 @@ nsIntRegion nsRegion::ScaleToNearestPixe
}
return result;
}
nsIntRegion nsRegion::ScaleToOutsidePixels (float aScaleX, float aScaleY,
nscoord aAppUnitsPerPixel) const
{
// make a copy of the region so that we can mutate it inplace
- nsRegion region = *this;
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
- boxes = pixman_region32_rectangles(®ion.mImpl, &n);
- for (int i=0; i<n; i++) {
- nsRect rect = BoxToRect(boxes[i]);
- mozilla::gfx::IntRect irect = rect.ScaleToOutsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
- boxes[i] = RectToBox(irect);
+ nsIntRegion intRegion;
+ for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+ nsRect rect = iter.Get();
+ intRegion.OrWith(rect.ScaleToOutsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel));
}
-
- nsIntRegion iRegion;
- // clear out the initial pixman_region so that we can replace it below
- pixman_region32_fini(&iRegion.mImpl.mImpl);
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(&iRegion.mImpl.mImpl, boxes, n);
-
- return iRegion;
+ return intRegion;
}
nsIntRegion nsRegion::ScaleToInsidePixels (float aScaleX, float aScaleY,
nscoord aAppUnitsPerPixel) const
{
/* When scaling a rect, walk forward through the rect list up until the y value is greater
* than the current rect's YMost() value.
*
@@ -771,67 +635,61 @@ nsIntRegion nsRegion::ScaleToInsidePixel
*
* If it is, then the contained edge can be moved (in scaled pixels) to ensure that no
* gap exists.
*
* Since this could be potentially expensive - O(n^2), we only attempt this algorithm
* for the first rect.
*/
- // make a copy of this region so that we can mutate it in place
- nsRegion region = *this;
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
+ if (mBands.IsEmpty()) {
+ nsIntRect rect = mBounds.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
+ return nsIntRegion(rect);
+ }
nsIntRegion intRegion;
- if (n) {
- nsRect first = BoxToRect(boxes[0]);
- mozilla::gfx::IntRect firstDeviceRect =
- first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
+ RectIterator iter = RectIterator(*this);
+
+ nsRect first = iter.Get();
- for (int i=1; i<n; i++) {
- nsRect rect = nsRect(boxes[i].x1, boxes[i].y1,
- boxes[i].x2 - boxes[i].x1,
- boxes[i].y2 - boxes[i].y1);
- mozilla::gfx::IntRect deviceRect =
- rect.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
+ mozilla::gfx::IntRect firstDeviceRect =
+ first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
+
+ for (iter.Next(); !iter.Done(); iter.Next()) {
+ nsRect rect = iter.Get();
+ mozilla::gfx::IntRect deviceRect =
+ rect.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
- if (rect.Y() <= first.YMost()) {
- if (rect.XMost() == first.X() && rect.YMost() <= first.YMost()) {
- // rect is touching on the left edge of the first rect and contained within
- // the length of its left edge
- deviceRect.SetRightEdge(firstDeviceRect.X());
- } else if (rect.X() == first.XMost() && rect.YMost() <= first.YMost()) {
- // rect is touching on the right edge of the first rect and contained within
- // the length of its right edge
- deviceRect.SetLeftEdge(firstDeviceRect.XMost());
- } else if (rect.Y() == first.YMost()) {
- // The bottom of the first rect is on the same line as the top of rect, but
- // they aren't necessarily contained.
- if (rect.X() <= first.X() && rect.XMost() >= first.XMost()) {
- // The top of rect contains the bottom of the first rect
- firstDeviceRect.SetBottomEdge(deviceRect.Y());
- } else if (rect.X() >= first.X() && rect.XMost() <= first.XMost()) {
- // The bottom of the first contains the top of rect
- deviceRect.SetTopEdge(firstDeviceRect.YMost());
- }
- }
+ if (rect.Y() <= first.YMost()) {
+ if (rect.XMost() == first.X() && rect.YMost() <= first.YMost()) {
+ // rect is touching on the left edge of the first rect and contained within
+ // the length of its left edge
+ deviceRect.SetRightEdge(firstDeviceRect.X());
+ } else if (rect.X() == first.XMost() && rect.YMost() <= first.YMost()) {
+ // rect is touching on the right edge of the first rect and contained within
+ // the length of its right edge
+ deviceRect.SetLeftEdge(firstDeviceRect.XMost());
+ } else if (rect.Y() == first.YMost()) {
+ // The bottom of the first rect is on the same line as the top of rect, but
+ // they aren't necessarily contained.
+ if (rect.X() <= first.X() && rect.XMost() >= first.XMost()) {
+ // The top of rect contains the bottom of the first rect
+ firstDeviceRect.SetBottomEdge(deviceRect.Y());
+ } else if (rect.X() >= first.X() && rect.XMost() <= first.XMost()) {
+ // The bottom of the first contains the top of rect
+ deviceRect.SetTopEdge(firstDeviceRect.YMost());
+ }
}
-
- boxes[i] = RectToBox(deviceRect);
}
- boxes[0] = RectToBox(firstDeviceRect);
+ intRegion.OrWith(deviceRect);
+ }
- pixman_region32_fini(&intRegion.mImpl.mImpl);
- // This will union all of the rectangles and runs in about O(n lg(n))
- pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n);
- }
+ intRegion.OrWith(firstDeviceRect);
return intRegion;
-
}
// A cell's "value" is a pair consisting of
// a) the area of the subrectangle it corresponds to, if it's in
// aContainingRect and in the region, 0 otherwise
// b) the area of the subrectangle it corresponds to, if it's in the region,
// 0 otherwise
// Addition, subtraction and identity are defined on these values in the
@@ -1124,25 +982,41 @@ nsRect nsRegion::GetLargestRectangle (co
}
return bestRect;
}
std::ostream& operator<<(std::ostream& stream, const nsRegion& m) {
stream << "[";
- int n;
- pixman_box32_t *boxes = pixman_region32_rectangles(const_cast<pixman_region32_t*>(&m.mImpl), &n);
- for (int i=0; i<n; i++) {
- if (i != 0) {
+ bool first = true;
+ for (auto iter = m.RectIter(); !iter.Done(); iter.Next()) {
+ if (!first) {
stream << "; ";
+ } else {
+ first = true;
}
- stream << boxes[i].x1 << "," << boxes[i].y1 << "," << boxes[i].x2 << "," << boxes[i].y2;
+ const nsRect& rect = iter.Get();
+ stream << rect.X() << "," << rect.Y() << "," << rect.XMost() << "," << rect.YMost();
}
stream << "]";
return stream;
}
+void
+nsRegion::OutputToStream(std::string aObjName, std::ostream& stream) const
+{
+ auto iter = RectIter();
+ nsRect r = iter.Get();
+ stream << "nsRegion " << aObjName << "(nsRect(" << r.X() << ", " << r.Y() << ", " << r.Width() << ", " << r.Height() << "));\n";
+ iter.Next();
+
+ for (; !iter.Done(); iter.Next()) {
+ nsRect r = iter.Get();
+ stream << aObjName << ".OrWith(nsRect(" << r.X() << ", " << r.Y() << ", " << r.Width() << ", " << r.Height() << "));\n";
+ }
+}
+
nsCString
nsRegion::ToString() const {
return nsCString(mozilla::ToString(*this).c_str());
}
--- a/gfx/src/nsRegion.h
+++ b/gfx/src/nsRegion.h
@@ -18,19 +18,27 @@
#include "nsRect.h" // for mozilla::gfx::IntRect, nsRect
#include "nsMargin.h" // for nsIntMargin
#include "nsRegionFwd.h" // for nsIntRegion
#include "nsString.h" // for nsCString
#include "xpcom-config.h" // for CPP_THROW_NEW
#include "mozilla/ArrayView.h" // for ArrayView
#include "mozilla/Move.h" // for mozilla::Move
#include "mozilla/gfx/MatrixFwd.h" // for mozilla::gfx::Matrix4x4
+#include "mozilla/gfx/Logging.h"
+#include "nsTArray.h"
#include "pixman.h"
+// Uncomment this line to get additional integrity checking.
+//#define DEBUG_REGIONS
+#ifdef DEBUG_REGIONS
+#include <sstream>
+#endif
+
/* For information on the internal representation look at pixman-region.c
*
* This replaces an older homebrew implementation of nsRegion. The
* representation used here may use more rectangles than nsRegion however, the
* representation is canonical. This means that there's no need for an
* Optimize() method because for a paticular region there is only one
* representation. This means that nsIntRegion will have more predictable
* performance characteristics than the old nsRegion and should not become
@@ -42,129 +50,976 @@
enum class VisitSide {
TOP,
BOTTOM,
LEFT,
RIGHT
};
+namespace regiondetails {
+struct Band;
+}
+
+template<>
+struct nsTArray_CopyChooser<regiondetails::Band>
+{
+ typedef nsTArray_CopyWithConstructors<regiondetails::Band> Type;
+};
+
+namespace regiondetails {
+
+template<typename T, typename E>
+class UncheckedArray : public T
+{
+public:
+ using T::Elements;
+ using T::Length;
+
+ E & operator[](size_t aIndex) { return Elements()[aIndex]; }
+ const E& operator[](size_t aIndex) const { return Elements()[aIndex]; }
+ E& LastElement() { return Elements()[Length() - 1]; }
+ const E& LastElement() const { return Elements()[Length() - 1]; }
+
+ using iterator = E* ;
+ using const_iterator = const E*;
+
+ iterator begin() { return iterator(Elements()); }
+ const_iterator begin() const { return const_iterator(Elements()); }
+ const_iterator cbegin() const { return begin(); }
+ iterator end() { return iterator(Elements() + Length()); }
+ const_iterator end() const { return const_iterator(Elements() + Length()); }
+ const_iterator cend() const { return end(); }
+};
+
+struct Strip
+{
+ // Default constructor should never be called, but is required for
+ // vector::resize to compile.
+ Strip() { MOZ_CRASH(); }
+ Strip(int32_t aLeft, int32_t aRight) : left(aLeft), right(aRight) {}
+
+ bool operator != (const Strip& aOther) const
+ {
+ return left != aOther.left || right != aOther.right;
+ }
+
+ uint32_t Size() const
+ {
+ return right - left;
+ }
+
+ int32_t left;
+ int32_t right;
+};
+
+struct Band
+{
+ using Strip = regiondetails::Strip;
+#ifndef DEBUG
+ using StripArray = regiondetails::UncheckedArray<AutoTArray<Strip, 2>, Strip>;
+#else
+ using StripArray = AutoTArray<Strip, 2>;
+#endif
+
+ MOZ_IMPLICIT Band(const nsRect& aRect)
+ : top(aRect.Y()), bottom(aRect.YMost())
+ {
+ mStrips.AppendElement(Strip{ aRect.X(), aRect.XMost() });
+ }
+
+ Band(const Band& aOther)
+ : top(aOther.top), bottom(aOther.bottom)
+ , mStrips(aOther.mStrips)
+ {}
+ Band(const Band&& aOther)
+ : top(aOther.top), bottom(aOther.bottom)
+ , mStrips(std::move(aOther.mStrips))
+ {}
+
+ void InsertStrip(const Strip& aStrip)
+ {
+ for (size_t i = 0; i < mStrips.Length(); i++) {
+ Strip& strip = mStrips[i];
+ if (strip.left > aStrip.right) {
+ // Current strip is beyond aStrip, insert aStrip before.
+ mStrips.InsertElementAt(i, aStrip);
+ return;
+ }
+
+ if (strip.right < aStrip.left) {
+ // Current strip is before aStrip, try the next.
+ continue;
+ }
+
+ // Current strip intersects with aStrip, extend to the lext.
+ strip.left = std::min(strip.left, aStrip.left);
+
+ if (strip.right >= aStrip.right) {
+ // Current strip extends beyond aStrip, done.
+ return;
+ }
+
+ size_t next = i;
+ next++;
+ // Consume any subsequent strips intersecting with aStrip.
+ while (next < mStrips.Length() && mStrips[next].left <= aStrip.right) {
+ strip.right = mStrips[next].right;
+
+ mStrips.RemoveElementAt(next);
+ }
+
+ // Extend the strip in case the aStrip goes on beyond it.
+ strip.right = std::max(strip.right, aStrip.right);
+ return;
+ }
+ mStrips.AppendElement(aStrip);
+ }
+
+ void SubStrip(const Strip& aStrip)
+ {
+ for (size_t i = 0; i < mStrips.Length(); i++) {
+ Strip& strip = mStrips[i];
+ if (strip.left > aStrip.right) {
+ // Strip is entirely to the right of aStrip. Done.
+ return;
+ }
+
+ if (strip.right < aStrip.left) {
+ // Strip is entirely to the left of aStrip. Move on.
+ continue;
+ }
+
+ if (strip.left < aStrip.left) {
+ if (strip.right <= aStrip.right) {
+ strip.right = aStrip.left;
+ // This strip lies to the left of the start of aStrip.
+ continue;
+ }
+
+ // aStrip is completely contained by this strip.
+ Strip newStrip(aStrip.right, strip.right);
+ strip.right = aStrip.left;
+ if (i < mStrips.Length()) {
+ i++;
+ mStrips.InsertElementAt(i, newStrip);
+ } else {
+ mStrips.AppendElement(newStrip);
+ }
+ return;
+ }
+
+ // This strip lies to the right of the start of aStrip.
+ if (strip.right <= aStrip.right) {
+ // aStrip completely contains this strip.
+ mStrips.RemoveElementAt(i);
+ // Make sure we evaluate the strip now at i. This loop will increment.
+ i--;
+ continue;
+ }
+ strip.left = aStrip.right;
+ return;
+ }
+ }
+
+ bool Intersects(const Strip& aStrip) const
+ {
+ for (const Strip& strip : mStrips) {
+ if (strip.left >= aStrip.right) {
+ return false;
+ }
+
+ if (strip.right <= aStrip.left) {
+ continue;
+ }
+
+ return true;
+ }
+ return false;
+ }
+
+ bool IntersectStripBounds(Strip& aStrip) const
+ {
+ bool intersected = false;
+
+ int32_t rightMost;
+ for (const Strip& strip : mStrips) {
+ if (strip.left > aStrip.right) {
+ break;
+ }
+
+ if (strip.right <= aStrip.left) {
+ continue;
+ }
+
+ if (!intersected) {
+ // First intersection, this is where the left side begins.
+ aStrip.left = std::max(aStrip.left, strip.left);
+ }
+
+ intersected = true;
+ // Expand to the right for each intersecting strip found.
+ rightMost = std::min(strip.right, aStrip.right);
+ }
+
+ if (intersected) {
+ aStrip.right = rightMost;
+ }
+ else {
+ aStrip.right = aStrip.left = 0;
+ }
+ return intersected;
+ }
+
+ bool ContainsStrip(const Strip& aStrip) const
+ {
+ for (const Strip& strip : mStrips) {
+ if (strip.left > aStrip.left) {
+ return false;
+ }
+
+ if (strip.right >= aStrip.right) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ bool EqualStrips(const Band& aBand) const
+ {
+ if (mStrips.Length() != aBand.mStrips.Length()) {
+ return false;
+ }
+
+ for (auto iter1 = mStrips.begin(), iter2 = aBand.mStrips.begin();
+ iter1 != mStrips.end(); iter1++, iter2++)
+ {
+ if (*iter1 != *iter2) {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ void IntersectStrip(const Strip& aStrip)
+ {
+ size_t i = 0;
+
+ while (i < mStrips.Length()) {
+ Strip& strip = mStrips[i];
+ if (strip.right <= aStrip.left) {
+ mStrips.RemoveElementAt(i);
+ continue;
+ }
+
+ if (strip.left >= aStrip.right) {
+ mStrips.TruncateLength(i);
+ return;
+ }
+
+ strip.left = std::max(aStrip.left, strip.left);
+ strip.right = std::min(aStrip.right, strip.right);
+ i++;
+ }
+ }
+
+ void IntersectStrips(const Band& aOther)
+ {
+ auto iter = mStrips.begin();
+ auto iterOther = aOther.mStrips.begin();
+
+ StripArray newStrips;
+
+ // This function finds the intersection between two sets of strips.
+ while (true) {
+ while (true) {
+ while (iter != mStrips.end() && iter->right <= iterOther->left) {
+ // Increment our current strip until it ends beyond aOther's current strip.
+ iter++;
+ }
+
+ if (iter == mStrips.end()) {
+ // End of our strips. Done.
+ break;
+ }
+
+ while (iterOther != aOther.mStrips.end() && iterOther->right <= iter->left) {
+ // Increment aOther's current strip until it lies beyond our current strip.
+ iterOther++;
+ }
+
+ if (iterOther == aOther.mStrips.end()) {
+ // End of aOther's strips. Done.
+ break;
+ }
+
+ if (iterOther->left < iter->right) {
+ // Intersection!
+ break;
+ }
+ }
+
+ if (iter == mStrips.end() || iterOther == aOther.mStrips.end()) {
+ break;
+ }
+
+ newStrips.AppendElement(Strip(std::max(iter->left, iterOther->left), std::min(iterOther->right, iter->right)));
+
+ if (iterOther->right < iter->right) {
+ iterOther++;
+ if (iterOther == aOther.mStrips.end()) {
+ break;
+ }
+ } else {
+ iter++;
+ }
+ }
+
+ mStrips = newStrips;
+ }
+
+ bool Intersects(const Band& aOther) const
+ {
+ auto iter = mStrips.begin();
+ auto iterOther = aOther.mStrips.begin();
+
+ // This function finds the intersection between two sets of strips.
+ while (true) {
+ while (true) {
+ while (iter != mStrips.end() && iter->right <= iterOther->left) {
+ // Increment our current strip until it ends beyond aOther's current strip.
+ iter++;
+ }
+
+ if (iter == mStrips.end()) {
+ // End of our strips. Done.
+ break;
+ }
+
+ while (iterOther != aOther.mStrips.end() && iterOther->right <= iter->left) {
+ // Increment aOther's current strip until it lies beyond our current strip.
+ iterOther++;
+ }
+
+ if (iterOther == aOther.mStrips.end()) {
+ // End of aOther's strips. Done.
+ break;
+ }
+
+ if (iterOther->left < iter->right) {
+ // Intersection!
+ break;
+ }
+ }
+
+ if (iter == mStrips.end()|| iterOther == aOther.mStrips.end()) {
+ break;
+ }
+
+ return true;
+ }
+ return false;
+ }
+
+ void SubStrips(const Band& aOther)
+ {
+ size_t idx = 0;
+ auto iterOther = aOther.mStrips.begin();
+
+ // This function finds the intersection between two sets of strips.
+ while (true) {
+ while (true) {
+ while (idx < mStrips.Length() && mStrips[idx].right <= iterOther->left) {
+ // Increment our current strip until it ends beyond aOther's current strip.
+ idx++;
+ }
+
+ if (idx == mStrips.Length()) {
+ // End of our strips. Done.
+ break;
+ }
+
+ while (iterOther != aOther.mStrips.end() && iterOther->right <= mStrips[idx].left) {
+ // Increment aOther's current strip until it lies beyond our current strip.
+ iterOther++;
+ }
+
+ if (iterOther == aOther.mStrips.end()) {
+ // End of aOther's strips. Done.
+ break;
+ }
+
+ if (iterOther->left < mStrips[idx].right) {
+ // Intersection!
+ break;
+ }
+ }
+
+ if (idx == mStrips.Length() || iterOther == aOther.mStrips.end()) {
+ break;
+ }
+
+ if (mStrips[idx].left < iterOther->left) {
+ size_t oldIdx = idx;
+ // Our strip starts beyond other's
+ if (mStrips[idx].right > iterOther->right) {
+ // Our strip ends beyond other's as well.
+ Strip newStrip(mStrips[idx]);
+ newStrip.left = iterOther->right;
+ mStrips.InsertElementAt(idx + 1, newStrip);
+ idx++;
+ }
+ mStrips[oldIdx].right = iterOther->left;
+ // Either idx was just incremented, or the current index no longer intersects with iterOther.
+ continue;
+ } else if (mStrips[idx].right > iterOther->right) {
+ mStrips[idx].left = iterOther->right;
+ // Current strip no longer intersects, continue.
+ iterOther++;
+ if (iterOther == aOther.mStrips.end()) {
+ break;
+ }
+ continue;
+ }
+
+ // Our current strip is completely contained by the other strip.
+ mStrips.RemoveElementAt(idx);
+ }
+ }
+
+ int32_t top;
+ int32_t bottom;
+ StripArray mStrips;
+};
+}
+
class nsRegion
{
public:
+ using Band = regiondetails::Band;
+ using Strip = regiondetails::Strip;
+#ifndef DEBUG
+ using BandArray = regiondetails::UncheckedArray<nsTArray<Band>, Band>;
+ using StripArray = regiondetails::UncheckedArray<AutoTArray<Strip, 2>, Strip>;
+#else
+ using BandArray = nsTArray<Band>;
+ using StripArray = AutoTArray<Strip, 2>;
+#endif
+
typedef nsRect RectType;
typedef nsPoint PointType;
typedef nsMargin MarginType;
- nsRegion () { pixman_region32_init(&mImpl); }
- MOZ_IMPLICIT nsRegion (const nsRect& aRect) { pixman_region32_init_rect(&mImpl,
- aRect.X(),
- aRect.Y(),
- aRect.Width(),
- aRect.Height()); }
- explicit nsRegion (mozilla::gfx::ArrayView<pixman_box32_t> aRects)
+ nsRegion() { }
+ MOZ_IMPLICIT nsRegion(const nsRect& aRect) {
+ mBounds = aRect;
+ }
+ explicit nsRegion(mozilla::gfx::ArrayView<pixman_box32_t> aRects)
{
- pixman_region32_init_rects(&mImpl, aRects.Data(), aRects.Length());
+ for (uint32_t i = 0; i < aRects.Length(); i++) {
+ AddRect(BoxToRect(aRects[i]));
+ }
}
- nsRegion (const nsRegion& aRegion) { pixman_region32_init(&mImpl); pixman_region32_copy(&mImpl,aRegion.Impl()); }
- nsRegion (nsRegion&& aRegion) { mImpl = aRegion.mImpl; pixman_region32_init(&aRegion.mImpl); }
- nsRegion& operator = (nsRegion&& aRegion) {
- pixman_region32_fini(&mImpl);
- mImpl = aRegion.mImpl;
- pixman_region32_init(&aRegion.mImpl);
- return *this;
+
+ nsRegion(const nsRegion& aRegion) { Copy(aRegion); }
+ nsRegion(nsRegion&& aRegion) { mBands.SwapElements(aRegion.mBands); mBounds = aRegion.mBounds; aRegion.SetEmpty(); }
+ nsRegion& operator =(nsRegion&& aRegion) {
+ mBands.SwapElements(aRegion.mBands);
+ mBounds = aRegion.mBounds;
+ aRegion.SetEmpty();
+ return *this;
}
- ~nsRegion () { pixman_region32_fini(&mImpl); }
- nsRegion& operator = (const nsRect& aRect) { Copy (aRect); return *this; }
- nsRegion& operator = (const nsRegion& aRegion) { Copy (aRegion); return *this; }
+ nsRegion& operator =(const nsRect& aRect) { Copy(aRect); return *this; }
+ nsRegion& operator =(const nsRegion& aRegion) { Copy(aRegion); return *this; }
bool operator==(const nsRegion& aRgn) const
{
return IsEqual(aRgn);
}
bool operator!=(const nsRegion& aRgn) const
{
return !(*this == aRgn);
}
friend std::ostream& operator<<(std::ostream& stream, const nsRegion& m);
+ void OutputToStream(std::string aObjName, std::ostream& stream) const;
- void Swap(nsRegion* aOther)
+ static
+ nsresult InitStatic()
+ {
+ return NS_OK;
+ }
+
+ static
+ void ShutdownStatic() {}
+
+private:
+#ifdef DEBUG_REGIONS
+ class OperationStringGenerator
+ {
+ public:
+ virtual ~OperationStringGenerator() {}
+
+ virtual void OutputOp() = 0;
+ };
+#endif
+public:
+
+ void AssertStateInternal() const;
+ void AssertState() const {
+#ifdef DEBUG_REGIONS
+ AssertStateInternal();
+#endif
+ }
+
+private:
+ void And(BandArray& aOut, const BandArray& aIn1, const BandArray& aIn2)
{
- pixman_region32_t tmp = mImpl;
- mImpl = aOther->mImpl;
- aOther->mImpl = tmp;
+ size_t idx = 0;
+ size_t idxOther = 0;
+
+ // This algorithm essentially forms a new list of bands, by iterating over
+ // both regions' lists of band simultaneously, and building a new band
+ // wherever the two regions intersect.
+ while (true) {
+ while (true) {
+ while (idx != aIn1.Length() && aIn1[idx].bottom <= aIn2[idxOther].top) {
+ // Increment our current band until it ends beyond aOther's current band.
+ idx++;
+ }
+
+ if (idx == aIn1.Length()) {
+ // This region is out of bands, the other region's future bands are ignored.
+ break;
+ }
+
+ while (idxOther != aIn2.Length() && aIn2[idxOther].bottom <= aIn1[idx].top) {
+ // Increment aOther's current band until it ends beyond our current band.
+ idxOther++;
+ }
+
+ if (idxOther == aIn2.Length()) {
+ // The other region's bands are all processed, all our future bands are ignored.
+ break;
+ }
+
+ if (aIn2[idxOther].top < aIn1[idx].bottom) {
+ // We know the other band's bottom lies beyond our band's top because
+ // otherwise we would've incremented above. Intersecting bands found.
+ break;
+ }
+ }
+
+ if (idx == aIn1.Length() || idxOther == aIn2.Length()) {
+ // The above loop executed a break because we're done.
+ break;
+ }
+
+ Band newBand(aIn1[idx]);
+ // The new band is the intersection of the two current bands from both regions.
+ newBand.top = std::max(aIn1[idx].top, aIn2[idxOther].top);
+ newBand.bottom = std::min(aIn1[idx].bottom, aIn2[idxOther].bottom);
+ newBand.IntersectStrips(aIn2[idxOther]);
+
+ if (newBand.mStrips.Length()) {
+ // The intersecting area of the bands had overlapping strips, if it is
+ // identical to the band above it merge, otherwise append.
+ if (aOut.Length() && aOut.LastElement().bottom == newBand.top &&
+ aOut.LastElement().EqualStrips(newBand)) {
+ aOut.LastElement().bottom = newBand.bottom;
+ } else {
+ aOut.AppendElement(std::move(newBand));
+ }
+ }
+
+ if (aIn2[idxOther].bottom < aIn1[idx].bottom) {
+ idxOther++;
+ if (idxOther == aIn2.Length()) {
+ // Since we will access idxOther the next iteration, check if we're not done.
+ break;
+ }
+ } else {
+ // No need to check here since we do at the beginning of the next iteration.
+ idx++;
+ }
+ }
}
- void AndWith(const nsRegion& aOther)
+public:
+ nsRegion& AndWith(const nsRegion& aRegion)
{
- And(*this, aOther);
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorAndWith : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorAndWith(nsRegion& aRegion, const nsRegion& aOtherRegion)
+ : mRegion(&aRegion), mRegionCopy(aRegion), mOtherRegion(aOtherRegion)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorAndWith()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegionCopy.OutputToStream("r1", stream);
+ mOtherRegion.OutputToStream("r2", stream);
+ stream << "r1.AndWith(r2);\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion * mRegion;
+ nsRegion mRegionCopy;
+ nsRegion mOtherRegion;
+ };
+
+ OperationStringGeneratorAndWith opGenerator(*this, aRegion);
+#endif
+ if (mBounds.IsEmpty()) {
+ // Region is empty, stays empty.
+ return *this;
+ }
+
+ if (aRegion.IsEmpty()) {
+ SetEmpty();
+ return *this;
+ }
+
+ if (aRegion.mBands.IsEmpty()) {
+ // Other region is a rect.
+ return AndWith(aRegion.mBounds);
+ }
+
+ if (mBands.IsEmpty()) {
+ mBands.AppendElement(mBounds);
+ }
+
+ BandArray newBands;
+
+ And(newBands, mBands, aRegion.mBands);
+
+ mBands = std::move(newBands);
+ if (!mBands.Length()) {
+ mBounds = nsRect();
+ } else {
+ mBounds = CalculateBounds();
+ }
+
+ EnsureSimplified();
+ AssertState();
+ return *this;
}
- void AndWith(const nsRect& aOther)
+
+ nsRegion& AndWith(const nsRect& aRect)
{
- And(*this, aOther);
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorAndWith : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorAndWith(nsRegion& aRegion, const nsRect& aRect)
+ : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorAndWith()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegionCopy.OutputToStream("r", stream);
+ stream << "r.AndWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion * mRegion;
+ nsRegion mRegionCopy;
+ nsRect mRect;
+ };
+
+ OperationStringGeneratorAndWith opGenerator(*this, aRect);
+#endif
+ if (aRect.IsEmpty()) {
+ SetEmpty();
+ return *this;
+ }
+
+ if (mBands.IsEmpty()) {
+ mBounds = mBounds.Intersect(aRect);
+ return *this;
+ }
+
+ size_t idx = 0;
+
+ size_t removeStart = 0;
+
+ // This removes all bands that do not intersect with aRect, and intersects
+ // the remaining ones with aRect.
+
+ // Start by figuring out how much to remove from the start.
+ while (idx != mBands.Length() && mBands[idx].bottom <= aRect.Y()) {
+ idx++;
+ }
+
+ // We'll remove these later to avoid needless copying in the array.
+ removeStart = idx;
+
+ while (idx != mBands.Length()) {
+ if (mBands[idx].top >= aRect.YMost()) {
+ mBands.TruncateLength(idx);
+ break;
+ }
+
+ mBands[idx].top = std::max(mBands[idx].top, aRect.Y());
+ mBands[idx].bottom = std::min(mBands[idx].bottom, aRect.YMost());
+
+ mBands[idx].IntersectStrip(Strip(aRect.X(), aRect.XMost()));
+
+ if (!mBands[idx].mStrips.Length()) {
+ mBands.RemoveElementAt(idx);
+ } else {
+ if (idx > removeStart) {
+ CompressBefore(idx);
+ }
+ idx++;
+ }
+ }
+
+ if (removeStart) {
+ mBands.RemoveElementsAt(0, removeStart);
+ }
+
+ if (mBands.Length()) {
+ mBounds = CalculateBounds();
+ } else {
+ mBounds.SetEmpty();
+ }
+ EnsureSimplified();
+ AssertState();
+ return *this;
}
- nsRegion& And(const nsRegion& aRgn1, const nsRegion& aRgn2)
+ nsRegion& And(const nsRegion& aRgn1, const nsRegion& aRgn2)
{
- pixman_region32_intersect(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+ if (&aRgn1 == this) {
+ return AndWith(aRgn2);
+ }
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorAnd : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorAnd(nsRegion& aRegion, const nsRegion& aRegion1, const nsRegion& aRegion2)
+ : mRegion(&aRegion), mRegion1(aRegion1), mRegion2(aRegion2)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorAnd()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegion1.OutputToStream("r1", stream);
+ mRegion2.OutputToStream("r2", stream);
+ stream << "nsRegion r3;\nr3.And(r1, r2);\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion * mRegion;
+ nsRegion mRegion1;
+ nsRegion mRegion2;
+ };
+
+ OperationStringGeneratorAnd opGenerator(*this, aRgn1, aRgn2);
+#endif
+ mBands.Clear();
+
+ if (aRgn1.IsEmpty() || aRgn2.IsEmpty()) {
+ mBounds.SetEmpty();
+ return *this;
+ }
+
+ if (aRgn1.mBands.IsEmpty() && aRgn2.mBands.IsEmpty()) {
+ mBounds = aRgn1.mBounds.Intersect(aRgn2.mBounds);
+ return *this;
+ } else if (aRgn1.mBands.IsEmpty()) {
+ return And(aRgn2, aRgn1.mBounds);
+ } else if (aRgn2.mBands.IsEmpty()) {
+ return And(aRgn1, aRgn2.mBounds);
+ }
+
+ And(mBands, aRgn1.mBands, aRgn2.mBands);
+
+ if (!mBands.Length()) {
+ mBounds = nsRect();
+ } else {
+ mBounds = CalculateBounds();
+ }
+
+ EnsureSimplified();
+ AssertState();
return *this;
}
nsRegion& And(const nsRect& aRect, const nsRegion& aRegion)
{
return And(aRegion, aRect);
}
nsRegion& And(const nsRegion& aRegion, const nsRect& aRect)
{
- pixman_region32_intersect_rect(&mImpl, aRegion.Impl(), aRect.X(), aRect.Y(), aRect.Width(), aRect.Height());
+ if (&aRegion == this) {
+ return AndWith(aRect);
+ }
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorAnd : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorAnd(nsRegion& aThisRegion, const nsRegion& aRegion, const nsRect& aRect)
+ : mThisRegion(&aThisRegion), mRegion(aRegion), mRect(aRect)
+ {
+ aThisRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorAnd()
+ {
+ mThisRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegion.OutputToStream("r", stream);
+ stream << "nsRegion r2;\nr.And(r2, nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion* mThisRegion;
+ nsRegion mRegion;
+ nsRect mRect;
+ };
+
+ OperationStringGeneratorAnd opGenerator(*this, aRegion, aRect);
+#endif
+ mBands.Clear();
+
+ if (aRect.IsEmpty()) {
+ mBounds.SetEmpty();
+ return *this;
+ }
+
+ if (aRegion.mBands.IsEmpty()) {
+ mBounds = aRegion.mBounds.Intersect(aRect);
+ return *this;
+ }
+
+ size_t idx = 0;
+ const BandArray& bands = aRegion.mBands;
+
+ mBands.SetCapacity(bands.Length() + 3);
+ while (idx != bands.Length()) {
+ // Ignore anything before.
+ if (bands[idx].bottom <= aRect.Y()) {
+ idx++;
+ continue;
+ }
+ // We're done once we've reached the bottom.
+ if (bands[idx].top >= aRect.YMost()) {
+ break;
+ }
+
+ // Now deal with bands actually intersecting the rectangle.
+ Band newBand(bands[idx]);
+ newBand.top = std::max(bands[idx].top, aRect.Y());
+ newBand.bottom = std::min(bands[idx].bottom, aRect.YMost());
+
+ newBand.IntersectStrip(Strip(aRect.X(), aRect.XMost()));
+
+ if (newBand.mStrips.Length()) {
+ if (!mBands.IsEmpty() &&
+ newBand.top == mBands.LastElement().bottom &&
+ newBand.EqualStrips(mBands.LastElement())) {
+ mBands.LastElement().bottom = newBand.bottom;
+ } else {
+ mBands.AppendElement(std::move(newBand));
+ }
+ }
+ idx++;
+ }
+
+ if (mBands.Length()) {
+ mBounds = CalculateBounds();
+ } else {
+ mBounds.SetEmpty();
+ }
+
+ EnsureSimplified();
+ AssertState();
return *this;
}
nsRegion& And(const nsRect& aRect1, const nsRect& aRect2)
{
- nsRect TmpRect;
+ nsRect tmpRect;
- TmpRect.IntersectRect(aRect1, aRect2);
- return Copy(TmpRect);
+ tmpRect.IntersectRect(aRect1, aRect2);
+ return Copy(tmpRect);
}
nsRegion& OrWith(const nsRegion& aOther)
{
- return Or(*this, aOther);
+ for (RectIterator idx(aOther); !idx.Done(); idx.Next()) {
+ AddRect(idx.Get());
+ }
+ return *this;
}
nsRegion& OrWith(const nsRect& aOther)
{
- return Or(*this, aOther);
+ AddRect(aOther);
+ return *this;
}
nsRegion& Or(const nsRegion& aRgn1, const nsRegion& aRgn2)
{
- pixman_region32_union(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+ if (&aRgn1 != this) {
+ *this = aRgn1;
+ }
+ for (RectIterator idx(aRgn2); !idx.Done(); idx.Next()) {
+ AddRect(idx.Get());
+ }
return *this;
}
nsRegion& Or(const nsRegion& aRegion, const nsRect& aRect)
{
- pixman_region32_union_rect(&mImpl, aRegion.Impl(), aRect.X(), aRect.Y(), aRect.Width(), aRect.Height());
+ if (&aRegion != this) {
+ *this = aRegion;
+ }
+ AddRect(aRect);
return *this;
}
nsRegion& Or(const nsRect& aRect, const nsRegion& aRegion)
{
return Or(aRegion, aRect);
}
nsRegion& Or(const nsRect& aRect1, const nsRect& aRect2)
{
- Copy (aRect1);
- return Or (*this, aRect2);
+ Copy(aRect1);
+ return Or(*this, aRect2);
}
nsRegion& XorWith(const nsRegion& aOther)
{
return Xor(*this, aOther);
}
nsRegion& XorWith(const nsRect& aOther)
{
return Xor(*this, aOther);
}
- nsRegion& Xor(const nsRegion& aRgn1, const nsRegion& aRgn2)
+ nsRegion& Xor(const nsRegion& aRgn1, const nsRegion& aRgn2)
{
// this could be implemented better if pixman had direct
// support for xoring regions.
nsRegion p;
p.Sub(aRgn1, aRgn2);
nsRegion q;
q.Sub(aRgn2, aRgn1);
return Or(p, q);
@@ -177,70 +1032,759 @@ public:
{
return Xor(nsRegion(aRect), aRegion);
}
nsRegion& Xor(const nsRect& aRect1, const nsRect& aRect2)
{
return Xor(nsRegion(aRect1), nsRegion(aRect2));
}
- nsRegion ToAppUnits (nscoord aAppUnitsPerPixel) const;
+ nsRegion ToAppUnits(nscoord aAppUnitsPerPixel) const;
+
+ nsRegion& SubWith(const nsRegion& aOther)
+ {
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorSubWith : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorSubWith(nsRegion& aRegion, const nsRegion& aOtherRegion)
+ : mRegion(&aRegion), mRegionCopy(aRegion), mOtherRegion(aOtherRegion)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorSubWith()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegionCopy.OutputToStream("r1", stream);
+ mOtherRegion.OutputToStream("r2", stream);
+ stream << "r1.SubWith(r2);\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion * mRegion;
+ nsRegion mRegionCopy;
+ nsRegion mOtherRegion;
+ };
+
+ OperationStringGeneratorSubWith opGenerator(*this, aOther);
+#endif
+
+ if (mBounds.IsEmpty()) {
+ return *this;
+ }
+
+ if (aOther.mBands.IsEmpty()) {
+ return SubWith(aOther.mBounds);
+ }
+
+ if (mBands.IsEmpty()) {
+ mBands.AppendElement(Band(mBounds));
+ }
+
+ size_t idx = 0;
+ size_t idxOther = 0;
+ while (idx < mBands.Length()) {
+ while (true) {
+ while (idx != mBands.Length() && mBands[idx].bottom <= aOther.mBands[idxOther].top) {
+ // Increment our current band until it ends beyond aOther's current band.
+ idx++;
+ }
+
+ if (idx == mBands.Length()) {
+ // This region is out of bands, the other region's future bands are ignored.
+ break;
+ }
+
+ while (idxOther != aOther.mBands.Length() && aOther.mBands[idxOther].bottom <= mBands[idx].top) {
+ // Increment aOther's current band until it ends beyond our current band.
+ idxOther++;
+ }
+
+ if (idxOther == aOther.mBands.Length()) {
+ // The other region's bands are all processed, all our future bands are ignored.
+ break;
+ }
+ if (aOther.mBands[idxOther].top < mBands[idx].bottom) {
+ // We know the other band's bottom lies beyond our band's top because
+ // otherwise we would've incremented above. Intersecting bands found.
+ break;
+ }
+ }
+
+ if (idx == mBands.Length() || idxOther == aOther.mBands.Length()) {
+ // The above loop executed a break because we're done.
+ break;
+ }
+
+ const Band& bandOther = aOther.mBands[idxOther];
+
+ if (!mBands[idx].Intersects(bandOther)) {
+ if (mBands[idx].bottom < bandOther.bottom) {
+ idx++;
+ } else {
+ idxOther++;
+ if (idxOther == aOther.mBands.Length()) {
+ break;
+ }
+ }
+ continue;
+ }
+
+ // These bands actually intersect.
+ if (mBands[idx].top < bandOther.top) {
+ mBands.InsertElementAt(idx + 1, Band(mBands[idx]));
+ mBands[idx].bottom = bandOther.top;
+ idx++;
+ mBands[idx].top = bandOther.top;
+ }
+
+ // mBands[idx].top >= bandOther.top;
+ if (mBands[idx].bottom <= bandOther.bottom) {
+ mBands[idx].SubStrips(bandOther);
+ if (mBands[idx].mStrips.IsEmpty()) {
+ mBands.RemoveElementAt(idx);
+ } else {
+ CompressBefore(idx);
+ idx++;
+ // The band before us just changed, it may be identical now.
+ CompressBefore(idx);
+ }
+ continue;
+ }
+
+ // mBands[idx].bottom > bandOther.bottom
+ Band newBand = mBands[idx];
+ newBand.SubStrips(bandOther);
+
+ if (!newBand.mStrips.IsEmpty()) {
+ mBands.InsertElementAt(idx, newBand);
+ mBands[idx].bottom = bandOther.bottom;
+ CompressBefore(idx);
+ idx++;
+ }
+
+ mBands[idx].top = bandOther.bottom;
+
+ idxOther++;
+ if (idxOther == aOther.mBands.Length()) {
+ break;
+ }
+ }
+
+ if (mBands.IsEmpty()) {
+ mBounds.SetEmpty();
+ } else {
+ mBounds = CalculateBounds();
+ }
+
+ AssertState();
+ EnsureSimplified();
+ return *this;
+ }
nsRegion& SubOut(const nsRegion& aOther)
{
- return Sub(*this, aOther);
+ return SubWith(aOther);
}
nsRegion& SubOut(const nsRect& aOther)
{
- return Sub(*this, aOther);
+ return SubWith(aOther);
}
+
+private:
+ void AppendOrExtend(const Band& aNewBand)
+ {
+ if (aNewBand.mStrips.IsEmpty()) {
+ return;
+ }
+ if (mBands.IsEmpty()) {
+ mBands.AppendElement(aNewBand);
+ return;
+ }
+
+ if (mBands.LastElement().bottom == aNewBand.top && mBands.LastElement().EqualStrips(aNewBand)) {
+ mBands.LastElement().bottom = aNewBand.bottom;
+ } else {
+ mBands.AppendElement(aNewBand);
+ }
+ }
+ void AppendOrExtend(const Band&& aNewBand)
+ {
+ if (aNewBand.mStrips.IsEmpty()) {
+ return;
+ }
+ if (mBands.IsEmpty()) {
+ mBands.AppendElement(std::move(aNewBand));
+ return;
+ }
+
+ if (mBands.LastElement().bottom == aNewBand.top && mBands.LastElement().EqualStrips(aNewBand)) {
+ mBands.LastElement().bottom = aNewBand.bottom;
+ } else {
+ mBands.AppendElement(std::move(aNewBand));
+ }
+ }
+public:
nsRegion& Sub(const nsRegion& aRgn1, const nsRegion& aRgn2)
{
- pixman_region32_subtract(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+ if (&aRgn1 == this) {
+ return SubWith(aRgn2);
+ }
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorSub : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorSub(nsRegion& aRegion, const nsRegion& aRgn1, const nsRegion& aRgn2)
+ : mRegion(&aRegion), mRegion1(aRgn1), mRegion2(aRgn2)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorSub()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegion1.OutputToStream("r1", stream);
+ mRegion2.OutputToStream("r2", stream);
+ stream << "nsRegion r3;\nr3.Sub(r1, r2);\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion* mRegion;
+ nsRegion mRegion1;
+ nsRegion mRegion2;
+ };
+
+ OperationStringGeneratorSub opGenerator(*this, aRgn1, aRgn2);
+#endif
+
+ mBands.Clear();
+
+ if (aRgn1.mBounds.IsEmpty()) {
+ mBounds.SetEmpty();
+ return *this;
+ }
+
+ if (aRgn2.mBounds.IsEmpty()) {
+ Copy(aRgn1);
+ return *this;
+ }
+
+ const BandArray& bands1 = aRgn1.mBands;
+ const BandArray& bands2 = aRgn2.mBands;
+ if (aRgn1.mBands.IsEmpty() && aRgn2.mBands.IsEmpty()) {
+ return Sub(aRgn1.mBounds, aRgn2.mBounds);
+ } else if (aRgn1.mBands.IsEmpty()) {
+ return Sub(aRgn1.mBounds, aRgn2);
+ } else if (aRgn2.mBands.IsEmpty()) {
+ return Sub(aRgn1, aRgn2.mBounds);
+ }
+
+ size_t idx = 0;
+ size_t idxOther = 0;
+
+ // We iterate the source region's bands, subtracting the other regions bands from them as we
+ // move them into ours.
+ while (idx < bands1.Length()) {
+ while (idxOther < bands2.Length() && bands2[idxOther].bottom <= bands1[idx].top) {
+ // These other bands are irrelevant as they don't intersect with the
+ // band we're currently processing.
+ idxOther++;
+ }
+ if (idxOther == bands2.Length()) {
+ break;
+ }
+
+ const Band& other = bands2[idxOther];
+
+ // bands2[idxOther].bottom >= bands1[idx].top
+ Band origBand(bands1[idx]);
+ if (other.top >= origBand.bottom) {
+ // No intersecting bands, append and continue.
+ AppendOrExtend(origBand);
+ idx++;
+ continue;
+ }
+
+ // Push a band for an uncovered region above our band.
+ if (origBand.top < other.top) {
+ Band newBand(origBand);
+ newBand.bottom = other.top;
+ AppendOrExtend(std::move(newBand));
+ }
+
+ int32_t lastBottom = std::max(other.top, origBand.top);
+ while (idxOther < bands2.Length() && bands2[idxOther].top < origBand.bottom) {
+ const Band& other = bands2[idxOther];
+ Band newBand(origBand);
+ newBand.top = std::max(origBand.top, other.top);
+ newBand.bottom = std::min(origBand.bottom, other.bottom);
+
+ // If there was a gap, we need to add the original band there.
+ if (newBand.top > lastBottom) {
+ Band betweenBand(newBand);
+ betweenBand.top = lastBottom;
+ betweenBand.bottom = newBand.top;
+ AppendOrExtend(std::move(betweenBand));
+ }
+
+ lastBottom = newBand.bottom;
+ newBand.SubStrips(other);
+ AppendOrExtend(std::move(newBand));
+ idxOther++;
+ }
+ // Decrement other here so we are back at the last band in region 2
+ // that intersected.
+ idxOther--;
+
+ if (bands2[idxOther].bottom < origBand.bottom) {
+ // The last band in region2 that intersected ended before this one,
+ // we can copy the rest.
+ Band newBand(origBand);
+ newBand.top = bands2[idxOther].bottom;
+ AppendOrExtend(std::move(newBand));
+ idxOther++;
+ }
+ idx++;
+ }
+
+ // Copy any remaining bands, the first one may have to be extended to fit
+ // the last one added before. The rest can be unconditionally appended.
+ if (idx < bands1.Length()) {
+ AppendOrExtend(bands1[idx]);
+ idx++;
+ }
+
+ while (idx < bands1.Length()) {
+ mBands.AppendElement(bands1[idx]);
+ idx++;
+ }
+
+ if (mBands.IsEmpty()) {
+ mBounds.SetEmpty();
+ }
+ else {
+ mBounds = CalculateBounds();
+ }
+
+ AssertState();
+ EnsureSimplified();
+ return *this;
+ }
+
+private:
+ // Internal helper for executing subtraction.
+ void RunSubtraction(const nsRect& aRect)
+ {
+ Strip rectStrip(aRect.X(), aRect.XMost());
+
+ size_t idx = 0;
+
+ while (idx < mBands.Length()) {
+ if (mBands[idx].top >= aRect.YMost()) {
+ return;
+ }
+
+ if (mBands[idx].bottom <= aRect.Y()) {
+ // This band is entirely before aRect, move on.
+ idx++;
+ continue;
+ }
+
+ if (!mBands[idx].Intersects(Strip(aRect.X(), aRect.XMost()))) {
+ // This band does not intersect aRect horizontally. Move on.
+ idx++;
+ continue;
+ }
+
+ // This band intersects with aRect.
+
+ if (mBands[idx].top < aRect.Y()) {
+ // This band starts above the start of aRect, split the band into two
+ // along the intersection, and continue to the next iteration to process
+ // the one that now intersects exactly.
+ auto above = mBands.InsertElementAt(idx, Band(mBands[idx]));
+ above->bottom = aRect.Y();
+ idx++;
+ mBands[idx].top = aRect.Y();
+ // Continue to run the loop for the next band.
+ continue;
+ }
+
+ if (mBands[idx].bottom <= aRect.YMost()) {
+ // This band ends before the end of aRect.
+ mBands[idx].SubStrip(rectStrip);
+ if (mBands[idx].mStrips.Length()) {
+ CompressAdjacentBands(idx);
+ } else {
+ mBands.RemoveElementAt(idx);
+ }
+ continue;
+ }
+
+ // This band extends beyond aRect.
+ Band newBand = mBands[idx];
+ newBand.SubStrip(rectStrip);
+ newBand.bottom = aRect.YMost();
+ mBands[idx].top = aRect.YMost();
+
+ if (newBand.mStrips.Length()) {
+ if (idx && mBands[idx - 1].bottom == newBand.top && newBand.EqualStrips(mBands[idx - 1])) {
+ mBands[idx - 1].bottom = aRect.YMost();
+ } else {
+ mBands.InsertElementAt(idx, std::move(newBand));
+ }
+ }
+
+ return;
+ }
+ }
+
+public:
+ nsRegion& SubWith(const nsRect& aRect) {
+ if (!mBounds.Intersects(aRect)) {
+ return *this;
+ }
+
+ if (aRect.Contains(mBounds)) {
+ SetEmpty();
+ return *this;
+ }
+
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorSubWith : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorSubWith(nsRegion& aRegion, const nsRect& aRect)
+ : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorSubWith()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegionCopy.OutputToStream("r", stream);
+ stream << "r.SubWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion * mRegion;
+ nsRegion mRegionCopy;
+ nsRect mRect;
+ };
+
+ OperationStringGeneratorSubWith opGenerator(*this, aRect);
+#endif
+
+ if (mBands.IsEmpty()) {
+ mBands.AppendElement(Band(mBounds));
+ }
+
+ RunSubtraction(aRect);
+
+ if (aRect.x <= mBounds.x || aRect.y <= mBounds.y ||
+ aRect.XMost() >= mBounds.XMost() || aRect.YMost() >= mBounds.YMost()) {
+ mBounds = CalculateBounds();
+ }
+ EnsureSimplified();
+ AssertState();
return *this;
}
nsRegion& Sub(const nsRegion& aRegion, const nsRect& aRect)
{
- return Sub(aRegion, nsRegion(aRect));
+ if (aRect.Contains(aRegion.mBounds)) {
+ SetEmpty();
+ return *this;
+ }
+ if (&aRegion == this) {
+ return SubWith(aRect);
+ }
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorSub : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorSub(nsRegion& aRegion, const nsRegion& aRegionOther, const nsRect& aRect)
+ : mRegion(&aRegion), mRegionOther(aRegionOther), mRect(aRect)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorSub()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegionOther.OutputToStream("r1", stream);
+ stream << "nsRegion r2;\nr2.Sub(r1, nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion * mRegion;
+ nsRegion mRegionOther;
+ nsRect mRect;
+ };
+
+ OperationStringGeneratorSub opGenerator(*this, aRegion, aRect);
+#endif
+
+ mBands.Clear();
+
+ if (aRegion.mBounds.IsEmpty()) {
+ mBounds.SetEmpty();
+ return *this;
+ }
+
+ if (aRect.IsEmpty()) {
+ Copy(aRegion);
+ return *this;
+ }
+
+ if (aRegion.mBands.IsEmpty()) {
+ Copy(aRegion.mBounds);
+ return SubWith(aRect);
+ }
+
+ const BandArray& bands = aRegion.mBands;
+
+ size_t idx = 0;
+
+ Strip strip(aRect.X(), aRect.XMost());
+
+ mBands.SetCapacity(bands.Length() + 3);
+
+ // Process all bands that lie before aRect.
+ while (idx < bands.Length() && bands[idx].bottom <= aRect.Y()) {
+ mBands.AppendElement(bands[idx]);
+ idx++;
+ }
+
+ // This band's bottom lies beyond aRect.
+ if (idx < bands.Length() && bands[idx].top < aRect.Y()) {
+ Band newBand(bands[idx]);
+ if (bands[idx].Intersects(strip)) {
+ newBand.bottom = aRect.Y();
+ } else {
+ idx++;
+ }
+ mBands.AppendElement(std::move(newBand));
+ }
+
+ // This tracks whether the band when we -exit- the next loop intersected the rectangle.
+ bool didIntersect = false;
+
+ while (idx < bands.Length() && bands[idx].top < aRect.YMost()) {
+ // Process all bands intersecting with aRect.
+ if (!bands[idx].Intersects(strip)) {
+ AppendOrExtend(bands[idx]);
+ idx++;
+ didIntersect = false;
+ continue;
+ }
+
+ didIntersect = true;
+ Band newBand(bands[idx]);
+ newBand.top = std::max(newBand.top, aRect.Y());
+ newBand.bottom = std::min(newBand.bottom, aRect.YMost());
+ newBand.SubStrip(strip);
+ AppendOrExtend(std::move(newBand));
+ idx++;
+ }
+
+ if (didIntersect) {
+ if (aRect.YMost() < bands[idx - 1].bottom) {
+ // If this band does not intersect the loop above has already added the
+ // whole unmodified band.
+ Band newBand(bands[idx - 1]);
+ newBand.top = aRect.YMost();
+ AppendOrExtend(std::move(newBand));
+ }
+ }
+
+ // Now process all bands beyond aRect.
+ if (idx < bands.Length()) {
+ AppendOrExtend(bands[idx]);
+ idx++;
+ }
+
+ mBands.AppendElements(bands.Elements() + idx, bands.Length() - idx);
+
+ if (mBands.IsEmpty()) {
+ mBounds.SetEmpty();
+ } else {
+ mBounds = CalculateBounds();
+ }
+
+ AssertState();
+ EnsureSimplified();
+ return *this;
}
nsRegion& Sub(const nsRect& aRect, const nsRegion& aRegion)
{
- return Sub(nsRegion(aRect), aRegion);
+ Copy(aRect);
+ return SubWith(aRegion);
}
nsRegion& Sub(const nsRect& aRect1, const nsRect& aRect2)
{
Copy(aRect1);
- return Sub(*this, aRect2);
+ return SubWith(aRect2);
}
/**
- * Returns true iff the given point is inside the region. A region
+ * Returns true if the given point is inside the region. A region
* created from a rect (x=0, y=0, w=100, h=100) will NOT contain
* the point x=100, y=100.
*/
- bool Contains (int aX, int aY) const
+ bool Contains(int aX, int aY) const
{
- return pixman_region32_contains_point(Impl(), aX, aY, nullptr);
- }
- bool Contains (const nsRect& aRect) const
- {
- pixman_box32_t box = RectToBox(aRect);
- return pixman_region32_contains_rectangle(Impl(), &box) == PIXMAN_REGION_IN;
+ if (mBands.IsEmpty()) {
+ return mBounds.Contains(aX, aY);
+ }
+
+ auto iter = mBands.begin();
+
+ while (iter != mBands.end()) {
+ if (iter->bottom <= aY) {
+ iter++;
+ continue;
+ }
+
+ if (iter->top > aY) {
+ return false;
+ }
+
+ if (iter->ContainsStrip(Strip(aX, aX + 1))) {
+ return true;
+ }
+ return false;
+ }
+ return false;
}
- bool Contains (const nsRegion& aRgn) const;
- bool Intersects (const nsRect& aRect) const;
-
- void MoveBy (int32_t aXOffset, int32_t aYOffset)
+ bool Contains(const nsRect& aRect) const
{
- MoveBy (nsPoint (aXOffset, aYOffset));
+ if (aRect.IsEmpty()) {
+ return false;
+ }
+
+ if (mBands.IsEmpty()) {
+ return mBounds.Contains(aRect);
+ }
+
+ auto iter = mBands.begin();
+
+ while (iter != mBands.end()) {
+ if (iter->bottom <= aRect.Y()) {
+ iter++;
+ continue;
+ }
+
+ if (iter->top > aRect.Y()) {
+ return false;
+ }
+
+ // Now inside the rectangle.
+ if (!iter->ContainsStrip(Strip(aRect.X(), aRect.XMost()))) {
+ return false;
+ }
+
+ if (iter->bottom >= aRect.YMost()) {
+ return true;
+ }
+
+ int32_t lastY = iter->bottom;
+ iter++;
+ while (iter != mBands.end()) {
+ // Bands do not connect.
+ if (iter->top != lastY) {
+ return false;
+ }
+
+ if (!iter->ContainsStrip(Strip(aRect.X(), aRect.XMost()))) {
+ return false;
+ }
+
+ if (iter->bottom >= aRect.YMost()) {
+ return true;
+ }
+
+ lastY = iter->bottom;
+ iter++;
+ }
+ }
+ return false;
}
- void MoveBy (nsPoint aPt) { pixman_region32_translate(&mImpl, aPt.x, aPt.y); }
- void SetEmpty ()
+
+ bool Contains(const nsRegion& aRgn) const;
+ bool Intersects(const nsRect& aRect) const;
+
+ void MoveBy(int32_t aXOffset, int32_t aYOffset)
+ {
+ MoveBy(nsPoint(aXOffset, aYOffset));
+ }
+ void MoveBy(nsPoint aPt)
{
- pixman_region32_clear(&mImpl);
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorMoveBy : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorMoveBy(nsRegion& aRegion, const nsPoint& aPoint)
+ : mRegion(&aRegion), mRegionCopy(aRegion), mPoint(aPoint)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorMoveBy()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegionCopy.OutputToStream("r", stream);
+ stream << "r.MoveBy(nsPoint(" << mPoint.x << ", " << mPoint.y << "));\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion * mRegion;
+ nsRegion mRegionCopy;
+ nsPoint mPoint;
+ };
+
+ OperationStringGeneratorMoveBy opGenerator(*this, aPt);
+#endif
+
+ mBounds.MoveBy(aPt);
+ for (Band& band : mBands) {
+ band.top += aPt.Y();
+ band.bottom += aPt.Y();
+ for (Strip& strip : band.mStrips) {
+ strip.left += aPt.X();
+ strip.right += aPt.X();
+ }
+ }
+ AssertState();
+ }
+ void SetEmpty()
+ {
+ mBands.Clear();
+ mBounds.SetEmpty();
}
nsRegion MovedBy(int32_t aXOffset, int32_t aYOffset) const
{
return MovedBy(nsPoint(aXOffset, aYOffset));
}
nsRegion MovedBy(const nsPoint& aPt) const
{
@@ -260,197 +1804,427 @@ public:
nsRegion Inflated(const nsMargin& aMargin) const
{
nsRegion copy(*this);
copy.Inflate(aMargin);
return copy;
}
- bool IsEmpty () const { return !pixman_region32_not_empty(Impl()); }
- bool IsComplex () const { return GetNumRects() > 1; }
- bool IsEqual (const nsRegion& aRegion) const
- {
- return pixman_region32_equal(Impl(), aRegion.Impl());
- }
- uint32_t GetNumRects () const
+ bool IsEmpty() const { return mBounds.IsEmpty(); }
+ bool IsComplex() const { return GetNumRects() > 1; }
+ bool IsEqual(const nsRegion& aRegion) const
{
- // Work around pixman bug. Sometimes pixman creates regions with 1 rect
- // that's empty.
- uint32_t result = pixman_region32_n_rects(Impl());
- return (result == 1 && GetBounds().IsEmpty()) ? 0 : result;
+ if (mBands.IsEmpty() && aRegion.mBands.IsEmpty()) {
+ return mBounds.IsEqualInterior(aRegion.mBounds);
+ }
+
+ if (mBands.Length() != aRegion.mBands.Length()) {
+ return false;
+ }
+
+ for (auto iter1 = mBands.begin(), iter2 = aRegion.mBands.begin();
+ iter1 != mBands.end(); iter1++, iter2++)
+ {
+ if (!iter1->EqualStrips(*iter2)) {
+ return false;
+ }
+ }
+
+ return true;
}
- const nsRect GetBounds () const { return BoxToRect(mImpl.extents); }
- uint64_t Area () const;
+
+ uint32_t GetNumRects() const
+ {
+ if (mBands.IsEmpty()) {
+ return mBounds.IsEmpty() ? 0 : 1;
+ }
+
+ uint32_t rects = 0;
+
+ for (const Band& band : mBands) {
+ rects += band.mStrips.Length();
+ }
+
+ return rects;
+ }
+ const nsRect GetBounds() const { return mBounds; }
+ uint64_t Area() const;
/**
* Return this region scaled to a different appunits per pixel (APP) ratio.
* This applies nsRect::ScaleToOtherAppUnitsRoundOut/In to each rect of the region.
* @param aFromAPP the APP to scale from
* @param aToAPP the APP to scale to
* @note this can turn an empty region into a non-empty region
*/
MOZ_MUST_USE nsRegion
- ScaleToOtherAppUnitsRoundOut (int32_t aFromAPP, int32_t aToAPP) const;
+ ScaleToOtherAppUnitsRoundOut(int32_t aFromAPP, int32_t aToAPP) const;
MOZ_MUST_USE nsRegion
- ScaleToOtherAppUnitsRoundIn (int32_t aFromAPP, int32_t aToAPP) const;
+ ScaleToOtherAppUnitsRoundIn(int32_t aFromAPP, int32_t aToAPP) const;
nsRegion& ScaleRoundOut(float aXScale, float aYScale);
nsRegion& ScaleInverseRoundOut(float aXScale, float aYScale);
- nsRegion& Transform (const mozilla::gfx::Matrix4x4 &aTransform);
- nsIntRegion ScaleToOutsidePixels (float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
- nsIntRegion ScaleToInsidePixels (float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
- nsIntRegion ScaleToNearestPixels (float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
- nsIntRegion ToOutsidePixels (nscoord aAppUnitsPerPixel) const;
- nsIntRegion ToNearestPixels (nscoord aAppUnitsPerPixel) const;
+ nsRegion& Transform(const mozilla::gfx::Matrix4x4 &aTransform);
+ nsIntRegion ScaleToOutsidePixels(float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
+ nsIntRegion ScaleToInsidePixels(float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
+ nsIntRegion ScaleToNearestPixels(float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
+ nsIntRegion ToOutsidePixels(nscoord aAppUnitsPerPixel) const;
+ nsIntRegion ToNearestPixels(nscoord aAppUnitsPerPixel) const;
/**
* Gets the largest rectangle contained in the region.
* @param aContainingRect if non-empty, we choose a rectangle that
* maximizes the area intersecting with aContainingRect (and break ties by
* then choosing the largest rectangle overall)
*/
- nsRect GetLargestRectangle (const nsRect& aContainingRect = nsRect()) const;
+ nsRect GetLargestRectangle(const nsRect& aContainingRect = nsRect()) const;
/**
* Make sure the region has at most aMaxRects by adding area to it
* if necessary. The simplified region will be a superset of the
* original region. The simplified region's bounding box will be
* the same as for the current region.
*/
- void SimplifyOutward (uint32_t aMaxRects);
+ void SimplifyOutward(uint32_t aMaxRects);
/**
* Simplify the region by adding at most aThreshold area between spans of
* rects. The simplified region will be a superset of the original region.
* The simplified region's bounding box will be the same as for the current
* region.
*/
void SimplifyOutwardByArea(uint32_t aThreshold);
/**
* Make sure the region has at most aMaxRects by removing area from
* it if necessary. The simplified region will be a subset of the
* original region.
*/
- void SimplifyInward (uint32_t aMaxRects);
+ void SimplifyInward(uint32_t aMaxRects);
/**
* VisitEdges is a weird kind of function that we use for padding
* out surfaces to prevent texture filtering artifacts.
* It calls the visitFn callback for each of the exterior edges of
* the regions. The top and bottom edges will be expanded 1 pixel
* to the left and right if there's an outside corner. The order
* the edges are visited is not guaranteed.
*
* visitFn has a side parameter that can be TOP,BOTTOM,LEFT,RIGHT
* and specifies which kind of edge is being visited. x1, y1, x2, y2
* are the coordinates of the line. (x1 == x2) || (y1 == y2)
*/
- typedef void (*visitFn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2);
+ typedef void(*visitFn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2);
void VisitEdges(visitFn, void *closure);
nsCString ToString() const;
- class RectIterator
- {
- int mCurrent; // Index of the current entry
- int mLimit; // Index one past the final entry.
- mutable nsRect mTmp; // The most recently gotten rectangle.
- pixman_box32_t *mBoxes;
-
- public:
- explicit RectIterator(const nsRegion& aRegion)
- {
- mCurrent = 0;
- mBoxes = pixman_region32_rectangles(aRegion.Impl(), &mLimit);
- // Work around pixman bug. Sometimes pixman creates regions with 1 rect
- // that's empty.
- if (mLimit == 1 && nsRegion::BoxToRect(mBoxes[0]).IsEmpty()) {
- mLimit = 0;
- }
- }
-
- bool Done() const { return mCurrent == mLimit; }
-
- const nsRect& Get() const
- {
- MOZ_ASSERT(!Done());
- mTmp = nsRegion::BoxToRect(mBoxes[mCurrent]);
- NS_ASSERTION(!mTmp.IsEmpty(), "Shouldn't return empty rect");
- return mTmp;
- }
-
- void Next()
- {
- MOZ_ASSERT(!Done());
- mCurrent++;
- }
- };
-
- RectIterator RectIter() const { return RectIterator(*this); }
-
static inline pixman_box32_t RectToBox(const nsRect &aRect)
{
pixman_box32_t box = { aRect.X(), aRect.Y(), aRect.XMost(), aRect.YMost() };
return box;
}
static inline pixman_box32_t RectToBox(const mozilla::gfx::IntRect &aRect)
{
pixman_box32_t box = { aRect.X(), aRect.Y(), aRect.XMost(), aRect.YMost() };
return box;
}
+private:
+ nsIntRegion ToPixels(nscoord aAppUnitsPerPixel, bool aOutsidePixels) const;
+
+ nsRegion& Copy(const nsRegion& aRegion)
+ {
+ mBounds = aRegion.mBounds;
+ mBands = aRegion.mBands;
+ return *this;
+ }
+
+ nsRegion& Copy(const nsRect& aRect)
+ {
+ mBands.Clear();
+ mBounds = aRect;
+ return *this;
+ }
+
+ void EnsureSimplified() {
+ if (mBands.Length() == 1 && mBands.begin()->mStrips.Length() == 1) {
+ mBands.Clear();
+ }
+ }
static inline nsRect BoxToRect(const pixman_box32_t &aBox)
{
return nsRect(aBox.x1, aBox.y1,
- aBox.x2 - aBox.x1,
- aBox.y2 - aBox.y1);
+ aBox.x2 - aBox.x1,
+ aBox.y2 - aBox.y1);
}
-private:
- pixman_region32_t mImpl;
+ void AddRect(const nsRect& aRect)
+ {
+#ifdef DEBUG_REGIONS
+ class OperationStringGeneratorAddRect : public OperationStringGenerator
+ {
+ public:
+ OperationStringGeneratorAddRect(nsRegion& aRegion, const nsRect& aRect)
+ : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect)
+ {
+ aRegion.mCurrentOpGenerator = this;
+ }
+ virtual ~OperationStringGeneratorAddRect()
+ {
+ mRegion->mCurrentOpGenerator = nullptr;
+ }
+
+ virtual void OutputOp() override
+ {
+ std::stringstream stream;
+ mRegionCopy.OutputToStream("r", stream);
+ stream << "r.OrWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+ gfxCriticalError() << stream.str();
+ }
+ private:
+ nsRegion* mRegion;
+ nsRegion mRegionCopy;
+ nsRect mRect;
+ };
+
+ OperationStringGeneratorAddRect opGenerator(*this, aRect);
+#endif
+ if (aRect.IsEmpty()) {
+ return;
+ }
+
+ if (aRect.Overflows()) {
+ // We don't accept rects which overflow.
+ gfxWarning() << "Passing overflowing rect to AddRect.";
+ return;
+ }
+
+ if (mBands.IsEmpty()) {
+ if (mBounds.IsEmpty()) {
+ mBounds = aRect;
+ return;
+ } else if (mBounds.Contains(aRect)) {
+ return;
+ }
+
+ mBands.AppendElement(Band(mBounds));
+ }
+
+ mBounds = aRect.UnsafeUnion(mBounds);
+
+ size_t idx = 0;
+
+ Strip strip(aRect.X(), aRect.XMost());
+ Band remaining(aRect);
+
+ while (idx != mBands.Length()) {
+ if (mBands[idx].bottom <= remaining.top) {
+ // This band lies wholly above aRect.
+ idx++;
+ continue;
+ }
+
+ if (remaining.top >= remaining.bottom) {
+ AssertState();
+ EnsureSimplified();
+ return;
+ }
+
+ if (mBands[idx].top >= remaining.bottom) {
+ // This band lies wholly below aRect.
+ break;
+ }
+
+ if (mBands[idx].EqualStrips(remaining)) {
+ mBands[idx].top = std::min(mBands[idx].top, remaining.top);
+ // Nothing to do for this band. Just expand.
+ remaining.top = mBands[idx].bottom;
+ CompressBefore(idx);
+ idx++;
+ continue;
+ }
+
+ if (mBands[idx].top > remaining.top) {
+ auto before = mBands.InsertElementAt(idx, remaining);
+ before->bottom = mBands[idx + 1].top;
+ remaining.top = before->bottom;
+ CompressBefore(idx);
+ idx++;
+ CompressBefore(idx);
+ continue;
+ }
+
+ if (mBands[idx].ContainsStrip(strip)) {
+ remaining.top = mBands[idx].bottom;
+ idx++;
+ continue;
+ }
+
+ // mBands[idx].top <= remaining.top.
-#ifndef MOZ_TREE_PIXMAN
- // For compatibility with pixman versions older than 0.25.2.
- static inline void
- pixman_region32_clear(pixman_region32_t *region)
+ if (mBands[idx].top < remaining.top) {
+ auto before = mBands.InsertElementAt(idx, Band(mBands[idx]));
+ before->bottom = remaining.top;
+ idx++;
+ mBands[idx].top = remaining.top;
+ continue;
+ }
+
+ // mBands[idx].top == remaining.top
+ if (mBands[idx].bottom > remaining.bottom) {
+ auto below = mBands.InsertElementAt(idx + 1, Band(mBands[idx]));
+ below->top = remaining.bottom;
+ mBands[idx].bottom = remaining.bottom;
+ }
+
+ mBands[idx].InsertStrip(strip);
+ CompressBefore(idx);
+ remaining.top = mBands[idx].bottom;
+ idx++;
+ CompressBefore(idx);
+ }
+
+ if (remaining.top < remaining.bottom) {
+ // We didn't find any bands that overlapped aRect.
+ if (idx) {
+ if (mBands[idx - 1].bottom == remaining.top && mBands[idx - 1].EqualStrips(remaining)) {
+ mBands[idx - 1].bottom = remaining.bottom;
+ CompressBefore(idx);
+ AssertState();
+ EnsureSimplified();
+ return;
+ }
+ }
+ mBands.InsertElementAt(idx, remaining);
+ idx++;
+ CompressBefore(idx);
+ } else {
+ CompressBefore(idx);
+ }
+
+ AssertState();
+ EnsureSimplified();
+ }
+
+ // Most callers could probably do this on the fly, if this ever shows up
+ // in profiles we could optimize this.
+ nsRect CalculateBounds() const
{
- pixman_region32_fini(region);
- pixman_region32_init(region);
+ if (mBands.IsEmpty()) {
+ return mBounds;
+ }
+
+ int32_t top = mBands.begin()->top;
+ int32_t bottom = mBands.LastElement().bottom;
+
+ int32_t leftMost = mBands.begin()->mStrips.begin()->left;
+ int32_t rightMost = mBands.begin()->mStrips.LastElement().right;
+ for (const Band& band : mBands) {
+ leftMost = std::min(leftMost, band.mStrips.begin()->left);
+ rightMost = std::max(rightMost, band.mStrips.LastElement().right);
+ }
+
+ return nsRect(leftMost, top, rightMost - leftMost, bottom - top);
}
+
+ static uint32_t ComputeMergedAreaIncrease(const Band& aTopBand,
+ const Band& aBottomBand);
+
+ // Returns true if idx is now referring to the 'next' band
+ bool CompressAdjacentBands(size_t& aIdx)
+ {
+ if ((aIdx + 1) < mBands.Length()) {
+ if (mBands[aIdx + 1].top == mBands[aIdx].bottom && mBands[aIdx + 1].EqualStrips(mBands[aIdx])) {
+ mBands[aIdx].bottom = mBands[aIdx + 1].bottom;
+ mBands.RemoveElementAt(aIdx + 1);
+ }
+ }
+ if (aIdx) {
+ if (mBands[aIdx - 1].bottom == mBands[aIdx].top && mBands[aIdx].EqualStrips(mBands[aIdx - 1])) {
+ mBands[aIdx - 1].bottom = mBands[aIdx].bottom;
+ mBands.RemoveElementAt(aIdx);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ void CompressBefore(size_t& aIdx)
+ {
+ if (aIdx && aIdx < mBands.Length()) {
+ if (mBands[aIdx - 1].bottom == mBands[aIdx].top && mBands[aIdx - 1].EqualStrips(mBands[aIdx])) {
+ mBands[aIdx].top = mBands[aIdx - 1].top;
+ mBands.RemoveElementAt(aIdx - 1);
+ aIdx--;
+ }
+ }
+ }
+
+
+ BandArray mBands;
+ // Considering we only ever OR with nsRects, the bounds should fit in an nsRect as well.
+ nsRect mBounds;
+#ifdef DEBUG_REGIONS
+ friend class OperationStringGenerator;
+ OperationStringGenerator* mCurrentOpGenerator;
#endif
- nsIntRegion ToPixels(nscoord aAppUnitsPerPixel, bool aOutsidePixels) const;
-
- nsRegion& Copy (const nsRegion& aRegion)
- {
- pixman_region32_copy(&mImpl, aRegion.Impl());
- return *this;
- }
-
- nsRegion& Copy (const nsRect& aRect)
+public:
+ class RectIterator
{
- // pixman needs to distinguish between an empty region and a region
- // with one rect so that it can return a different number of rectangles.
- // Empty rect: data = empty_box
- // 1 rect: data = null
- // >1 rect: data = rects
- if (aRect.IsEmpty()) {
- pixman_region32_clear(&mImpl);
- } else {
- pixman_box32_t box = RectToBox(aRect);
- pixman_region32_reset(&mImpl, &box);
+ const nsRegion& mRegion;
+ typename BandArray::const_iterator mCurrentBand;
+ typename StripArray::const_iterator mCurrentStrip;
+
+ public:
+ explicit RectIterator(const nsRegion& aRegion)
+ : mRegion(aRegion)
+ , mCurrentBand(aRegion.mBands.begin())
+ {
+ mIsDone = mRegion.mBounds.IsEmpty();
+ if (mCurrentBand != aRegion.mBands.end()) {
+ mCurrentStrip = mCurrentBand->mStrips.begin();
+ }
}
- return *this;
- }
+
+ bool Done() const { return mIsDone; }
+
+ const nsRect Get() const
+ {
+ if (mRegion.mBands.IsEmpty()) {
+ return mRegion.mBounds;
+ }
+ return nsRect(mCurrentStrip->left, mCurrentBand->top,
+ mCurrentStrip->right - mCurrentStrip->left,
+ mCurrentBand->bottom - mCurrentBand->top);
+ }
- pixman_region32_t* Impl() const
- {
- return const_cast<pixman_region32_t*>(&mImpl);
- }
+ void Next()
+ {
+ if (mRegion.mBands.IsEmpty()) {
+ mIsDone = true;
+ return;
+ }
+
+ mCurrentStrip++;
+ if (mCurrentStrip == mCurrentBand->mStrips.end()) {
+ mCurrentBand++;
+ if (mCurrentBand != mRegion.mBands.end()) {
+ mCurrentStrip = mCurrentBand->mStrips.begin();
+ } else {
+ mIsDone = true;
+ }
+ }
+ }
+
+ bool mIsDone;
+ };
+
+ RectIterator RectIter() const { return RectIterator(*this); }
};
namespace mozilla {
namespace gfx {
/**
* BaseIntRegions use int32_t coordinates.
*/
@@ -486,21 +2260,16 @@ public:
{
return !(*this == aRgn);
}
friend std::ostream& operator<<(std::ostream& stream, const Derived& m) {
return stream << m.mImpl;
}
- void Swap(Derived* aOther)
- {
- mImpl.Swap(&aOther->mImpl);
- }
-
void AndWith(const Derived& aOther)
{
And(This(), aOther);
}
void AndWith(const Rect& aOther)
{
And(This(), aOther);
}
@@ -634,17 +2403,17 @@ public:
}
void MoveBy (int32_t aXOffset, int32_t aYOffset)
{
MoveBy (Point (aXOffset, aYOffset));
}
void MoveBy (Point aPt)
{
- mImpl.MoveBy (aPt.x, aPt.y);
+ mImpl.MoveBy (aPt.X(), aPt.Y());
}
Derived MovedBy(int32_t aXOffset, int32_t aYOffset) const
{
return MovedBy(Point(aXOffset, aYOffset));
}
Derived MovedBy(const Point& aPt) const
{
Derived copy(This());
@@ -682,17 +2451,17 @@ public:
return mImpl.IsEqual (aRegion.mImpl);
}
uint32_t GetNumRects () const { return mImpl.GetNumRects (); }
Rect GetBounds () const { return FromRect (mImpl.GetBounds ()); }
uint64_t Area () const { return mImpl.Area(); }
nsRegion ToAppUnits (nscoord aAppUnitsPerPixel) const
{
nsRegion result;
- for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
+ for (auto iter = RectIterator(*this); !iter.Done(); iter.Next()) {
nsRect appRect = ::ToAppUnits(iter.Get(), aAppUnitsPerPixel);
result.Or(result, appRect);
}
return result;
}
Rect GetLargestRectangle (const Rect& aContainingRect = Rect()) const
{
return FromRect (mImpl.GetLargestRectangle( ToRect(aContainingRect) ));
--- a/gfx/tests/gtest/TestRegion.cpp
+++ b/gfx/tests/gtest/TestRegion.cpp
@@ -11,16 +11,18 @@
#include "nsRegion.h"
#include "RegionBuilder.h"
#include "mozilla/gfx/TiledRegion.h"
#include "mozilla/UniquePtr.h"
using namespace std;
using namespace mozilla::gfx;
+//#define REGION_RANDOM_STRESS_TESTS
+
class TestLargestRegion {
public:
static void TestSingleRect(nsRect r) {
nsRegion region(r);
EXPECT_TRUE(region.GetLargestRectangle().IsEqualInterior(r));
}
// Construct a rectangle, remove part of it, then check the remainder
static void TestNonRectangular() {
@@ -177,16 +179,707 @@ TEST(Gfx, RegionScaleToInside) {
result.Or(result, mozilla::gfx::IntRect(0,750,318,18));
EXPECT_TRUE(result.IsEqual(scaled)) <<
"scaled result incorrect";
}
}
+TEST(Gfx, RegionOrWith) {
+ {
+ nsRegion r(nsRect(79, 31, 75, 12));
+ r.OrWith(nsRect(22, 43, 132, 5));
+ r.OrWith(nsRect(22, 48, 125, 3));
+ r.OrWith(nsRect(22, 51, 96, 20));
+ r.OrWith(nsRect(34, 71, 1, 14));
+ r.OrWith(nsRect(26, 85, 53, 1));
+ r.OrWith(nsRect(26, 86, 53, 4));
+ r.OrWith(nsRect(96, 86, 30, 4));
+ r.OrWith(nsRect(34, 90, 1, 2));
+ r.OrWith(nsRect(96, 90, 30, 2));
+ r.OrWith(nsRect(34, 92, 1, 3));
+ r.OrWith(nsRect(49, 92, 34, 3));
+ r.OrWith(nsRect(96, 92, 30, 3));
+ r.OrWith(nsRect(34, 95, 1, 17));
+ r.OrWith(nsRect(49, 95, 77, 17));
+ r.OrWith(nsRect(34, 112, 1, 12));
+ r.OrWith(nsRect(75, 112, 51, 12));
+ r.OrWith(nsRect(34, 124, 1, 10));
+ r.OrWith(nsRect(75, 124, 44, 10));
+ r.OrWith(nsRect(34, 134, 1, 19));
+ r.OrWith(nsRect(22, 17, 96, 27));
+ }
+ {
+ nsRegion r(nsRect(0, 8, 257, 32));
+ r.OrWith(nsRect(3702, 8, 138, 32));
+ r.OrWith(nsRect(0, 40, 225, 1));
+ r.OrWith(nsRect(3702, 40, 138, 1));
+ r.OrWith(nsRect(0, 41, 101, 40));
+ r.OrWith(nsRect(69, 41, 32, 40));
+ }
+ {
+ nsRegion r(nsRect(79, 56, 8, 32));
+ r.OrWith(nsRect(5, 94, 23, 81));
+ r.OrWith(nsRect(56, 29, 91, 81));
+ }
+ {
+ nsRegion r(nsRect(0, 82, 3840, 2046));
+ r.OrWith(nsRect(0, 0, 3840, 82));
+ }
+ {
+ nsRegion r(nsRect(2, 5, 600, 28));
+ r.OrWith(nsRect(2, 82, 600, 19));
+ r.OrWith(nsRect(2, 33, 600, 49));
+ }
+ {
+ nsRegion r(nsRect(3823, 0, 17, 17));
+ r.OrWith(nsRect(3823, 2029, 17, 17));
+ r.OrWith(nsRect(3823, 0, 17, 2046));
+ }
+ {
+ nsRegion r(nsRect(1036, 4, 32, 21));
+ r.OrWith(nsRect(1070, 4, 66, 21));
+ r.OrWith(nsRect(40, 5, 0, 33));
+ }
+ {
+ nsRegion r(nsRect(0, 0, 1024, 1152));
+ r.OrWith(nsRect(-335802, -1073741824, 1318851, 1860043520));
+ }
+ {
+ nsRegion r(nsRect(0, 0, 800, 1000));
+ r.OrWith(nsRect(0, 0, 536870912, 1073741824));
+ }
+ {
+ nsRegion r(nsRect(53, 2, 52, 3));
+ r.OrWith(nsRect(45, 5, 60, 16));
+ r.OrWith(nsRect(16, 21, 8, 1));
+ r.OrWith(nsRect(45, 21, 12, 1));
+ r.OrWith(nsRect(16, 22, 8, 5));
+ r.OrWith(nsRect(33, 22, 52, 5));
+ r.OrWith(nsRect(16, 27, 8, 7));
+ r.OrWith(nsRect(33, 27, 66, 7));
+ r.OrWith(nsRect(0, 34, 99, 1));
+ r.OrWith(nsRect(0, 35, 159, 27));
+ r.OrWith(nsRect(0, 62, 122, 3));
+ r.OrWith(nsRect(0, 65, 85, 11));
+ r.OrWith(nsRect(91, 65, 97, 11));
+ r.OrWith(nsRect(11, 76, 74, 2));
+ r.OrWith(nsRect(91, 76, 97, 2));
+ r.OrWith(nsRect(11, 78, 74, 12));
+ r.OrWith(nsRect(11, 90, 13, 3));
+ r.OrWith(nsRect(33, 90, 108, 3));
+ r.OrWith(nsRect(16, 93, 8, 22));
+ r.OrWith(nsRect(33, 93, 108, 22));
+ r.OrWith(nsRect(16, 115, 8, 1));
+ r.OrWith(nsRect(58, 115, 83, 1));
+ r.OrWith(nsRect(58, 116, 83, 25));
+ r.OrWith(nsRect(59, 37, 88, 92));
+ }
+#ifdef REGION_RANDOM_STRESS_TESTS
+ const uint32_t TestIterations = 100000;
+ const uint32_t RectsPerTest = 100;
+
+ nsRect rects[RectsPerTest];
+
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r;
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ r.SetEmpty();
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ r.OrWith(rects[n]);
+ }
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ EXPECT_TRUE(r.Contains(rects[n]));
+ }
+ }
+#endif
+}
+
+TEST(Gfx, RegionSubWith) {
+ PR_Sleep(PR_SecondsToInterval(10));
+ {
+ nsRegion r1(nsRect(0, 0, 100, 50));
+ r1.OrWith(nsRect(50, 50, 50, 50));
+ nsRegion r2(nsRect(0, 0, 100, 50));
+ r2.OrWith(nsRect(50, 50, 50, 50));
+ r1.SubWith(r2);
+ EXPECT_FALSE(r1.Contains(1, 1));
+ }
+ {
+ nsRegion r1(nsRect(0, 0, 800, 1000));
+ nsRegion r2(nsRect(8, 108, 22, 20));
+ r2.OrWith(nsRect(91, 138, 17, 18));
+ r1.SubWith(r2);
+ EXPECT_TRUE(r1.Contains(400, 130));
+ }
+ {
+ nsRegion r1(nsRect(392, 2, 28, 7));
+ r1.OrWith(nsRect(115, 9, 305, 16));
+ r1.OrWith(nsRect(392, 25, 28, 5));
+ r1.OrWith(nsRect(0, 32, 1280, 41));
+ nsRegion r2(nsRect(0, 0, 1280, 9));
+ r2.OrWith(nsRect(0, 9, 115, 16));
+ r2.OrWith(nsRect(331, 9, 949, 16));
+ r2.OrWith(nsRect(0, 25, 1280, 7));
+ r2.OrWith(nsRect(331, 32, 124, 1));
+ r1.SubWith(r2);
+ }
+ {
+ nsRegion r1(nsRect(552, 0, 2, 2));
+ r1.OrWith(nsRect(362, 2, 222, 28));
+ r1.OrWith(nsRect(552, 30, 2, 2));
+ r1.OrWith(nsRect(0, 32, 1280, 41));
+ nsRegion r2(nsRect(512, 0, 146, 9));
+ r2.OrWith(nsRect(340, 9, 318, 16));
+ r2.OrWith(nsRect(512, 25, 146, 8));
+ r1.SubWith(r2);
+ }
+ {
+ nsRegion r1(nsRect(0, 0, 1265, 1024));
+ nsRegion r2(nsRect(1265, 0, 15, 685));
+ r2.OrWith(nsRect(0, 714, 1280, 221));
+ nsRegion r3;
+ r3.Sub(r1, r2);
+ }
+ {
+ nsRegion r(nsRect(0, 0, 229380, 6780));
+ r.OrWith(nsRect(76800, 6780, 76800, 4440));
+ r.OrWith(nsRect(76800, 11220, 44082, 1800));
+ r.OrWith(nsRect(122682, 11220, 30918, 1800));
+ r.OrWith(nsRect(76800, 13020, 76800, 2340));
+ r.OrWith(nsRect(85020, 15360, 59340, 75520));
+ r.OrWith(nsRect(85020, 90880, 38622, 11332));
+ r.OrWith(nsRect(143789, 90880, 571, 11332));
+ r.OrWith(nsRect(85020, 102212, 59340, 960));
+ r.OrWith(nsRect(85020, 103172, 38622, 1560));
+ r.OrWith(nsRect(143789, 103172, 571, 1560));
+ r.OrWith(nsRect(85020, 104732, 59340, 12292));
+ r.OrWith(nsRect(85020, 117024, 38622, 1560));
+ r.OrWith(nsRect(143789, 117024, 571, 1560));
+ r.OrWith(nsRect(85020, 118584, 59340, 11976));
+ r.SubWith(nsRect(123642, 89320, 20147, 1560));
+ }
+ {
+ nsRegion r(nsRect(0, 0, 9480, 12900));
+ r.OrWith(nsRect(0, 12900, 8460, 1020));
+ r.SubWith(nsRect(8460, 0, 1020, 12900));
+ }
+ {
+ nsRegion r1(nsRect(99, 1, 51, 2));
+ r1.OrWith(nsRect(85, 3, 65, 1));
+ r1.OrWith(nsRect(10, 4, 66, 5));
+ r1.OrWith(nsRect(85, 4, 37, 5));
+ r1.OrWith(nsRect(10, 9, 112, 3));
+ r1.OrWith(nsRect(1, 12, 121, 1));
+ r1.OrWith(nsRect(1, 13, 139, 3));
+ r1.OrWith(nsRect(0, 16, 140, 3));
+ r1.OrWith(nsRect(0, 19, 146, 3));
+ r1.OrWith(nsRect(0, 22, 149, 2));
+ r1.OrWith(nsRect(0, 24, 154, 2));
+ r1.OrWith(nsRect(0, 26, 160, 23));
+ r1.OrWith(nsRect(0, 49, 162, 31));
+ r1.OrWith(nsRect(0, 80, 171, 19));
+ r1.OrWith(nsRect(0, 99, 173, 11));
+ r1.OrWith(nsRect(2, 110, 171, 6));
+ r1.OrWith(nsRect(6, 116, 165, 5));
+ r1.OrWith(nsRect(8, 121, 163, 1));
+ r1.OrWith(nsRect(13, 122, 158, 11));
+ r1.OrWith(nsRect(14, 133, 157, 23));
+ r1.OrWith(nsRect(29, 156, 142, 10));
+ r1.OrWith(nsRect(37, 166, 134, 6));
+ r1.OrWith(nsRect(55, 172, 4, 4));
+ r1.OrWith(nsRect(83, 172, 88, 4));
+ r1.OrWith(nsRect(55, 176, 4, 2));
+ r1.OrWith(nsRect(89, 176, 6, 2));
+ r1.OrWith(nsRect(89, 178, 6, 4));
+ nsRegion r2(nsRect(63, 11, 39, 11));
+ r2.OrWith(nsRect(63, 22, 99, 16));
+ r2.OrWith(nsRect(37, 38, 125, 61));
+ r2.OrWith(nsRect(45, 99, 117, 8));
+ r2.OrWith(nsRect(47, 107, 115, 7));
+ r2.OrWith(nsRect(47, 114, 66, 1));
+ r2.OrWith(nsRect(49, 115, 64, 2));
+ r2.OrWith(nsRect(49, 117, 54, 30));
+ r1.SubWith(r2);
+ }
+ {
+ nsRegion r1(nsRect(95, 2, 47, 1));
+ r1.OrWith(nsRect(62, 3, 80, 2));
+ r1.OrWith(nsRect(1, 5, 18, 3));
+ r1.OrWith(nsRect(48, 5, 94, 3));
+ r1.OrWith(nsRect(1, 8, 18, 3));
+ r1.OrWith(nsRect(23, 8, 119, 3));
+ r1.OrWith(nsRect(1, 11, 172, 9));
+ r1.OrWith(nsRect(1, 20, 18, 8));
+ r1.OrWith(nsRect(20, 20, 153, 8));
+ r1.OrWith(nsRect(1, 28, 172, 13));
+ r1.OrWith(nsRect(1, 41, 164, 1));
+ r1.OrWith(nsRect(1, 42, 168, 1));
+ r1.OrWith(nsRect(0, 43, 169, 15));
+ r1.OrWith(nsRect(1, 58, 168, 26));
+ r1.OrWith(nsRect(1, 84, 162, 2));
+ r1.OrWith(nsRect(1, 86, 165, 23));
+ r1.OrWith(nsRect(1, 109, 162, 23));
+ r1.OrWith(nsRect(1, 132, 152, 4));
+ r1.OrWith(nsRect(1, 136, 150, 12));
+ r1.OrWith(nsRect(12, 148, 139, 4));
+ r1.OrWith(nsRect(12, 152, 113, 2));
+ r1.OrWith(nsRect(14, 154, 31, 3));
+ r1.OrWith(nsRect(82, 154, 43, 3));
+ r1.OrWith(nsRect(17, 157, 13, 19));
+ r1.OrWith(nsRect(82, 157, 43, 19));
+ r1.OrWith(nsRect(17, 176, 13, 16));
+ nsRegion r2(nsRect(97, 9, 6, 10));
+ r2.OrWith(nsRect(71, 19, 32, 2));
+ r2.OrWith(nsRect(20, 21, 83, 2));
+ r2.OrWith(nsRect(2, 23, 101, 9));
+ r2.OrWith(nsRect(2, 32, 98, 1));
+ r2.OrWith(nsRect(2, 33, 104, 5));
+ r2.OrWith(nsRect(2, 38, 118, 2));
+ r2.OrWith(nsRect(15, 40, 9, 11));
+ r2.OrWith(nsRect(36, 40, 84, 11));
+ r2.OrWith(nsRect(4, 51, 116, 33));
+ r2.OrWith(nsRect(4, 84, 159, 8));
+ r2.OrWith(nsRect(4, 92, 116, 13));
+ r2.OrWith(nsRect(15, 105, 9, 7));
+ r2.OrWith(nsRect(36, 105, 84, 7));
+ r2.OrWith(nsRect(36, 112, 84, 22));
+ r2.OrWith(nsRect(71, 134, 39, 46));
+ r1.SubWith(r2);
+ }
+#ifdef REGION_RANDOM_STRESS_TESTS
+ const uint32_t TestIterations = 100000;
+ const uint32_t RectsPerTest = 100;
+ const uint32_t SubRectsPerTest = 10;
+
+ nsRect rects[RectsPerTest];
+ nsRect subRects[SubRectsPerTest];
+
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r;
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ r.SetEmpty();
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ r.OrWith(rects[n]);
+ }
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ EXPECT_TRUE(r.Contains(rects[n]));
+ }
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ r.SubWith(subRects[n]);
+ }
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+ EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+ }
+ }
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r;
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ r.SetEmpty();
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ r.OrWith(rects[n]);
+ }
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ EXPECT_TRUE(r.Contains(rects[n]));
+ }
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ nsRegion r2;
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ r2.OrWith(subRects[n]);
+ }
+ r.SubWith(r2);
+
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+ EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+ }
+ }
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r(nsRect(-1, -1, 202, 202));
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ r.SubWith(subRects[n]);
+ }
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+ EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+ }
+ EXPECT_TRUE(r.Contains(-1, -1));
+ EXPECT_TRUE(r.Contains(-1, 200));
+ EXPECT_TRUE(r.Contains(200, -1));
+ EXPECT_TRUE(r.Contains(200, 200));
+ }
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r(nsRect(-1, -1, 202, 202));
+ nsRegion r2;
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ r2.OrWith(subRects[n]);
+ }
+ r.SubWith(r2);
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+ EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+ }
+ EXPECT_TRUE(r.Contains(-1, -1));
+ EXPECT_TRUE(r.Contains(-1, 200));
+ EXPECT_TRUE(r.Contains(200, -1));
+ EXPECT_TRUE(r.Contains(200, 200));
+ }
+#endif
+}
+TEST(Gfx, RegionSub) {
+ {
+ nsRegion r1(nsRect(0, 0, 100, 50));
+ r1.OrWith(nsRect(50, 50, 50, 50));
+ nsRegion r2(nsRect(0, 0, 100, 50));
+ r2.OrWith(nsRect(50, 50, 50, 50));
+ nsRegion r3;
+ r3.Sub(r1, r2);
+ EXPECT_FALSE(r3.Contains(1, 1));
+ }
+ {
+ nsRegion r1(nsRect(0, 0, 800, 1000));
+ nsRegion r2(nsRect(8, 108, 22, 20));
+ r2.OrWith(nsRect(91, 138, 17, 18));
+ nsRegion r3;
+ r3.Sub(r1, r2);
+ EXPECT_TRUE(r3.Contains(400, 130));
+ }
+ {
+ nsRegion r1(nsRect(6, 0, 64, 1));
+ r1.OrWith(nsRect(6, 1, 67, 1));
+ r1.OrWith(nsRect(6, 2, 67, 2));
+ r1.OrWith(nsRect(79, 2, 67, 2));
+ r1.OrWith(nsRect(6, 4, 67, 1));
+ r1.OrWith(nsRect(79, 4, 98, 1));
+ r1.OrWith(nsRect(6, 5, 171, 18));
+ r1.OrWith(nsRect(1, 23, 176, 3));
+ r1.OrWith(nsRect(1, 26, 178, 5));
+ r1.OrWith(nsRect(1, 31, 176, 9));
+ r1.OrWith(nsRect(0, 40, 177, 57));
+ r1.OrWith(nsRect(0, 97, 176, 33));
+ r1.OrWith(nsRect(0, 130, 12, 17));
+ r1.OrWith(nsRect(15, 130, 161, 17));
+ r1.OrWith(nsRect(0, 147, 12, 5));
+ r1.OrWith(nsRect(15, 147, 111, 5));
+ r1.OrWith(nsRect(0, 152, 12, 7));
+ r1.OrWith(nsRect(17, 152, 109, 7));
+ r1.OrWith(nsRect(0, 159, 12, 2));
+ r1.OrWith(nsRect(17, 159, 98, 2));
+ r1.OrWith(nsRect(17, 161, 98, 9));
+ r1.OrWith(nsRect(27, 170, 63, 21));
+ nsRegion r2(nsRect(9, 9, 37, 17));
+ r2.OrWith(nsRect(92, 9, 26, 17));
+ r2.OrWith(nsRect(9, 26, 37, 9));
+ r2.OrWith(nsRect(84, 26, 65, 9));
+ r2.OrWith(nsRect(9, 35, 37, 2));
+ r2.OrWith(nsRect(51, 35, 98, 2));
+ r2.OrWith(nsRect(51, 37, 98, 11));
+ r2.OrWith(nsRect(51, 48, 78, 4));
+ r2.OrWith(nsRect(87, 52, 42, 7));
+ r2.OrWith(nsRect(19, 59, 12, 5));
+ r2.OrWith(nsRect(87, 59, 42, 5));
+ r2.OrWith(nsRect(19, 64, 12, 9));
+ r2.OrWith(nsRect(32, 64, 97, 9));
+ r2.OrWith(nsRect(19, 73, 12, 2));
+ r2.OrWith(nsRect(32, 73, 104, 2));
+ r2.OrWith(nsRect(19, 75, 117, 5));
+ r2.OrWith(nsRect(18, 80, 118, 5));
+ r2.OrWith(nsRect(18, 85, 111, 38));
+ r2.OrWith(nsRect(87, 123, 42, 11));
+ nsRegion r3;
+ r3.Sub(r1, r2);
+ }
+ {
+ nsRegion r1(nsRect(27, 0, 39, 1));
+ r1.OrWith(nsRect(86, 0, 22, 1));
+ r1.OrWith(nsRect(27, 1, 43, 1));
+ r1.OrWith(nsRect(86, 1, 22, 1));
+ r1.OrWith(nsRect(27, 2, 43, 1));
+ r1.OrWith(nsRect(86, 2, 75, 1));
+ r1.OrWith(nsRect(12, 3, 58, 1));
+ r1.OrWith(nsRect(86, 3, 75, 1));
+ r1.OrWith(nsRect(12, 4, 149, 5));
+ r1.OrWith(nsRect(0, 9, 161, 9));
+ r1.OrWith(nsRect(0, 18, 167, 17));
+ r1.OrWith(nsRect(0, 35, 171, 5));
+ r1.OrWith(nsRect(0, 40, 189, 28));
+ r1.OrWith(nsRect(0, 68, 171, 16));
+ r1.OrWith(nsRect(4, 84, 167, 5));
+ r1.OrWith(nsRect(4, 89, 177, 9));
+ r1.OrWith(nsRect(1, 98, 180, 59));
+ r1.OrWith(nsRect(4, 157, 177, 1));
+ r1.OrWith(nsRect(4, 158, 139, 15));
+ r1.OrWith(nsRect(17, 173, 126, 2));
+ r1.OrWith(nsRect(20, 175, 123, 2));
+ r1.OrWith(nsRect(20, 177, 118, 6));
+ r1.OrWith(nsRect(20, 183, 84, 2));
+ nsRegion r2(nsRect(64, 2, 30, 6));
+ r2.OrWith(nsRect(26, 11, 41, 17));
+ r2.OrWith(nsRect(19, 28, 48, 23));
+ r2.OrWith(nsRect(19, 51, 76, 8));
+ r2.OrWith(nsRect(4, 59, 91, 31));
+ r2.OrWith(nsRect(19, 90, 76, 29));
+ r2.OrWith(nsRect(33, 119, 62, 25));
+ r2.OrWith(nsRect(33, 144, 4, 21));
+ nsRegion r3;
+ r3.Sub(r1, r2);
+ }
+#ifdef REGION_RANDOM_STRESS_TESTS
+ const uint32_t TestIterations = 100000;
+ const uint32_t RectsPerTest = 100;
+ const uint32_t SubRectsPerTest = 10;
+
+ nsRect rects[RectsPerTest];
+ nsRect subRects[SubRectsPerTest];
+
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r;
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ r.SetEmpty();
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ r.OrWith(rects[n]);
+ }
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ EXPECT_TRUE(r.Contains(rects[n]));
+ }
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ nsRegion r2;
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ r2.OrWith(subRects[n]);
+ }
+ nsRegion r3;
+ r3.Sub(r, r2);
+
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].y));
+ EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+ }
+ }
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r(nsRect(-1, -1, 202, 202));
+ nsRegion r2;
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ r2.OrWith(subRects[n]);
+ }
+ nsRegion r3;
+ r3.Sub(r, r2);
+ for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+ EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].y));
+ EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+ EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+ }
+ EXPECT_TRUE(r3.Contains(-1, -1));
+ EXPECT_TRUE(r3.Contains(-1, 200));
+ EXPECT_TRUE(r3.Contains(200, -1));
+ EXPECT_TRUE(r3.Contains(200, 200));
+ }
+#endif
+}
+
+TEST(Gfx, RegionAndWith) {
+ {
+ nsRegion r(nsRect(20, 0, 20, 20));
+ r.OrWith(nsRect(0, 20, 40, 20));
+ r.AndWith(nsRect(0, 0, 5, 5));
+ EXPECT_FALSE(r.Contains(1, 1));
+ }
+ {
+ nsRegion r1(nsRect(512, 1792, 256, 256));
+ nsRegion r2(nsRect(17, 1860, 239, 35));
+ r2.OrWith(nsRect(17, 1895, 239, 7));
+ r2.OrWith(nsRect(768, 1895, 154, 7));
+ r2.OrWith(nsRect(17, 1902, 905, 483));
+ r1.AndWith(r2);
+ }
+#ifdef REGION_RANDOM_STRESS_TESTS
+ const uint32_t TestIterations = 100000;
+ const uint32_t RectsPerTest = 50;
+ const uint32_t pointsTested = 100;
+
+ {
+ nsRect rectsSet1[RectsPerTest];
+ nsRect rectsSet2[RectsPerTest];
+
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r1;
+ nsRegion r2;
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ rectsSet1[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ rectsSet2[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ r1.OrWith(rectsSet1[n]);
+ r2.OrWith(rectsSet1[n]);
+ }
+
+ nsRegion r3 = r1;
+ r3.AndWith(r2);
+
+ for (uint32_t n = 0; n < pointsTested; n++) {
+ nsPoint p(rand() % 200, rand() % 200);
+ if (r1.Contains(p.x, p.y) && r2.Contains(p.x, p.y)) {
+ EXPECT_TRUE(r3.Contains(p.x, p.y));
+ } else {
+ EXPECT_FALSE(r3.Contains(p.x, p.y));
+ }
+ }
+ }
+ }
+
+ {
+ nsRect rectsSet[RectsPerTest];
+ nsRect testRect;
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r;
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ rectsSet[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ r.OrWith(rectsSet[n]);
+ }
+ testRect.SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+
+ nsRegion r2 = r;
+ r2.AndWith(testRect);
+
+ for (uint32_t n = 0; n < pointsTested; n++) {
+ nsPoint p(rand() % 200, rand() % 200);
+ if (r.Contains(p.x, p.y) && testRect.Contains(p.x, p.y)) {
+ EXPECT_TRUE(r2.Contains(p.x, p.y));
+ } else {
+ EXPECT_FALSE(r2.Contains(p.x, p.y));
+ }
+ }
+ }
+ }
+#endif
+}
+
+TEST(Gfx, RegionAnd) {
+ {
+ nsRegion r(nsRect(20, 0, 20, 20));
+ r.OrWith(nsRect(0, 20, 40, 20));
+ nsRegion r2;
+ r2.And(r, nsRect(0, 0, 5, 5));
+ EXPECT_FALSE(r.Contains(1, 1));
+ }
+ {
+ nsRegion r(nsRect(51, 2, 57, 5));
+ r.OrWith(nsRect(36, 7, 72, 4));
+ r.OrWith(nsRect(36, 11, 25, 1));
+ r.OrWith(nsRect(69, 12, 6, 4));
+ r.OrWith(nsRect(37, 16, 54, 2));
+ r.OrWith(nsRect(37, 18, 82, 2));
+ r.OrWith(nsRect(10, 20, 109, 3));
+ r.OrWith(nsRect(1, 23, 136, 21));
+ r.OrWith(nsRect(1, 44, 148, 2));
+ r.OrWith(nsRect(1, 46, 176, 31));
+ r.OrWith(nsRect(6, 77, 171, 1));
+ r.OrWith(nsRect(5, 78, 172, 30));
+ r.OrWith(nsRect(5, 108, 165, 45));
+ r.OrWith(nsRect(5, 153, 61, 5));
+ r.OrWith(nsRect(72, 153, 98, 5));
+ r.OrWith(nsRect(38, 158, 25, 4));
+ r.OrWith(nsRect(72, 158, 98, 4));
+ r.OrWith(nsRect(58, 162, 5, 8));
+ r.OrWith(nsRect(72, 162, 98, 8));
+ r.OrWith(nsRect(72, 170, 98, 5));
+ nsRegion r2;
+ r.And(r2, nsRect(18, 78, 53, 45));
+ }
+#ifdef REGION_RANDOM_STRESS_TESTS
+ const uint32_t TestIterations = 100000;
+ const uint32_t RectsPerTest = 50;
+ const uint32_t pointsTested = 100;
+
+ {
+ nsRect rectsSet1[RectsPerTest];
+ nsRect rectsSet2[RectsPerTest];
+
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r1;
+ nsRegion r2;
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ rectsSet1[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ rectsSet2[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ r1.OrWith(rectsSet1[n]);
+ r2.OrWith(rectsSet1[n]);
+ }
+
+ nsRegion r3;
+ r3.And(r1, r2);
+
+ for (uint32_t n = 0; n < pointsTested; n++) {
+ nsPoint p(rand() % 200, rand() % 200);
+ if (r1.Contains(p.x, p.y) && r2.Contains(p.x, p.y)) {
+ EXPECT_TRUE(r3.Contains(p.x, p.y));
+ } else {
+ EXPECT_FALSE(r3.Contains(p.x, p.y));
+ }
+ }
+ }
+ }
+
+ {
+ nsRect rectsSet[RectsPerTest];
+ nsRect testRect;
+ for (uint32_t i = 0; i < TestIterations; i++) {
+ nsRegion r;
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ rectsSet[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+ }
+ for (uint32_t n = 0; n < RectsPerTest; n++) {
+ r.OrWith(rectsSet[n]);
+ }
+ testRect.SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+
+ nsRegion r2;
+ r2.And(r, testRect);
+
+ for (uint32_t n = 0; n < pointsTested; n++) {
+ nsPoint p(rand() % 200, rand() % 200);
+ if (r.Contains(p.x, p.y) && testRect.Contains(p.x, p.y)) {
+ EXPECT_TRUE(r2.Contains(p.x, p.y));
+ } else {
+ EXPECT_FALSE(r2.Contains(p.x, p.y));
+ }
+ }
+ }
+ }
+#endif
+}
TEST(Gfx, RegionSimplify) {
{ // ensure simplify works on a single rect
nsRegion r(nsRect(0,100,200,100));
r.SimplifyOutwardByArea(100*100);
nsRegion result(nsRect(0,100,200,100));