Bug 1440753: Replace pixman regions with our own region code. r=mattwoodrow draft
authorBas Schouten <bschouten@mozilla.com>
Fri, 02 Mar 2018 00:44:49 +0100
changeset 762284 aebc32e18da496c28c5c5c1512f63b74361066d8
parent 756941 d0d3693d9beff5477175a441fdb06e281e8b7f17
push id101118
push userbschouten@mozilla.com
push dateThu, 01 Mar 2018 23:45:26 +0000
reviewersmattwoodrow
bugs1440753
milestone60.0a1
Bug 1440753: Replace pixman regions with our own region code. r=mattwoodrow MozReview-Commit-ID: DOWSYdMOjjM
gfx/layers/client/ContentClient.cpp
gfx/src/nsRegion.cpp
gfx/src/nsRegion.h
gfx/tests/gtest/TestRegion.cpp
layout/svg/nsFilterInstance.cpp
--- a/gfx/layers/client/ContentClient.cpp
+++ b/gfx/layers/client/ContentClient.cpp
@@ -226,16 +226,18 @@ ContentClient::BeginPaint(PaintedLayer* 
     }
 
     if (!canReuseBuffer) {
       dest.mBufferRect = ComputeBufferRect(dest.mNeededRegion.GetBounds());
       dest.mCanReuseBuffer = false;
     }
   }
 
+  MOZ_ASSERT(dest.mBufferRect.Contains(result.mRegionToDraw.GetBounds()));
+
   NS_ASSERTION(!(aFlags & PAINT_WILL_RESAMPLE) || dest.mBufferRect == dest.mNeededRegion.GetBounds(),
                "If we're resampling, we need to validate the entire buffer");
 
   // We never had a buffer, the buffer wasn't big enough, the content changed
   // types, or we failed to unrotate the buffer when requested. In any case,
   // we need to allocate a new one and prepare it for drawing.
   if (!dest.mCanReuseBuffer) {
     uint32_t bufferFlags = 0;
--- a/gfx/src/nsRegion.cpp
+++ b/gfx/src/nsRegion.cpp
@@ -5,545 +5,362 @@
  * 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;
+
 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;
     }
   }
   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(&region, boxes, n);
-
-  pixman_region32_fini(&mImpl);
-  mImpl = region;
+  mBands.swap(newRegion.mBands);
+  mBounds = newRegion.mBounds;
+  return;
 }
 
 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
+
+  auto iter = mBands.begin();
+
+  while (iter != mBands.end()) {
+    auto olditer = iter;
+    iter->mStrips.front().right = iter->mStrips.back().right;
+    iter->mStrips.resize(1);
+    iter++;
+
+    // Merge any bands with the same bounds.
+    while (iter != mBands.end() &&
+           iter->mStrips.front().left == olditer->mStrips.front().left &&
+           iter->mStrips.back().right == olditer->mStrips.front().right) {
+      olditer->bottom = iter->bottom;
+      iter = mBands.erase(iter);
     }
   }
 
-  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.size() > 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.size() || 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.size() && 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;
+    }
+    currentStripBottom--;
+  }
+  uint32_t currentStripTop = 0;
+  for (auto& strip : aBottomBand.mStrips) {
+    if (currentStripTop == aTopBand.mStrips.size() || 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.size() && 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;
+    }
+    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.size() < 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.erase(mBands.begin() + currentBand + 1);
     } else {
-      // copy the unmerged rects
-      destRect = CopyRow(destRect, topRects, topRectsEnd);
+      currentBand++;
+    }
+  } while (currentBand + 1 < mBands.size());
 
-      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);
-
+  if (mBands.size() == 1 && mBands[0].mStrips.size() == 1) {
+    mBands.clear();
+  }
 
-  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();
-  }
+  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.empty()) {
+    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;
+        // We always start with nothing.
+        int oldState = 0;
+        // 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 | 1;
+            } else {
+              state = oldState ^ 1;
+              topStrip++;
+            }
+            topEdgeIsLeft = !topEdgeIsLeft;
+          } else if (bottomPos < topPos) {
+            if (bottomEdgeIsLeft) {
+              state = oldState | 2;
+            } else {
+              state = oldState ^ 2;
+              bottomStrip++;
+            }
+            bottomEdgeIsLeft = !bottomEdgeIsLeft;
+          } else {
+            // bottomPos == topPos
+            state = 0;
+            if (bottomEdgeIsLeft) {
+              state = 2;
+            } else {
+              bottomStrip++;
+            }
+            if (topEdgeIsLeft) {
+              state |= 1;
+            } else {
+              topStrip++;
+            }
+            topEdgeIsLeft = !topEdgeIsLeft;
+            bottomEdgeIsLeft = !bottomEdgeIsLeft;
+          }
+
+          MOZ_ASSERT(state != oldState);
+          if (oldState == 0) {
+            // We had nothing before, make sure the left edge will be padded.
+            lastX = currentX - 1;
+          } else if (oldState == 1) {
+            if (state == 0) {
+              visit(closure, VisitSide::BOTTOM, lastX, y, currentX + 1, y);
+            } else {
+              visit(closure, VisitSide::BOTTOM, lastX, y, currentX, y);
+              lastX = currentX;
+            }
+          } else if (oldState == 2) {
+            if (state == 0) {
+              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)
@@ -564,49 +381,40 @@ uint64_t nsRegion::Area () const
 
 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(&region, boxes, n);
+  mBands.swap(newRegion.mBands);
+  mBounds = newRegion.mBounds;
 
-  pixman_region32_fini(&mImpl);
-  mImpl = region;
   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(&region, boxes, n);
-
-  pixman_region32_fini(&mImpl);
-  mImpl = region;
+  mBands.swap(newRegion.mBands);
+  mBounds = newRegion.mBounds;
   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 +429,72 @@ 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(&region, boxes, n);
-
-  pixman_region32_fini(&mImpl);
-  mImpl = region;
+  mBands.swap(newRegion.mBands);
+  mBounds = newRegion.mBounds;
   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(&region.mImpl, &n);
-  for (int i=0; i<n; i++) {
-    nsRect rect = BoxToRect(boxes[i]);
-    rect = rect.ScaleToOtherAppUnitsRoundOut(aFromAPP, aToAPP);
-    boxes[i] = RectToBox(rect);
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = iter.Get();
+    rect.ScaleToOtherAppUnitsRoundOut(aFromAPP, aToAPP);
+    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(&region.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(&region.mImpl, &n);
-  for (int i=0; i<n; i++) {
-    nsRect rect = BoxToRect(boxes[i]);
-    rect = rect.ScaleToOtherAppUnitsRoundIn(aFromAPP, aToAPP);
-    boxes[i] = RectToBox(rect);
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = iter.Get();
+    rect.ScaleToOtherAppUnitsRoundIn(aFromAPP, aToAPP);
+    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(&region.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(&region.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 +514,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(&region.mImpl, &n);
-  boxes = pixman_region32_rectangles(&region.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 +538,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(&region.mImpl, &n);
+  if (!mBands.size()) {
+    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 +885,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::ostream& stream) const
+{
+  auto iter = RectIter();
+  nsRect r = iter.Get();
+  stream << "nsRegion r(nsRect(" << r.X() << ", " << r.Y() << ", " << r.Width() << ", " << r.Height() << "));\n";
+  iter.Next();
+
+  for (; !iter.Done(); iter.Next()) {
+    nsRect r = iter.Get();
+    stream << "r.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,26 @@
 #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 "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
@@ -49,131 +56,351 @@ enum class VisitSide {
 
 class nsRegion
 {
 public:
   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.swap(aRegion.mBands); mBounds = aRegion.mBounds; aRegion.SetEmpty(); }
+  nsRegion& operator =(nsRegion&& aRegion) {
+    mBands.swap(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::ostream& stream) const;
 
   void Swap(nsRegion* aOther)
   {
-    pixman_region32_t tmp = mImpl;
-    mImpl = aOther->mImpl;
-    aOther->mImpl = tmp;
+    mBands.swap(aOther->mBands);
   }
 
   static
-  nsresult InitStatic()
+    nsresult InitStatic()
   {
     return NS_OK;
   }
 
   static
-  void ShutdownStatic() {}
+    void ShutdownStatic() {}
+
+private:
+#ifdef DEBUG_REGIONS
+  class OperationStringGenerator
+  {
+  public:
+    virtual ~OperationStringGenerator() {}
+
+    virtual void OutputOp() = 0;
+  };
+#endif
+public:
+
+  void AssertState() const {
+#ifdef DEBUG_REGIONS
+    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.front().left);
+      highestX = std::max(highestX, band.mStrips.back().right);
 
-  void AndWith(const nsRegion& aOther)
-  {
-    And(*this, aOther);
+      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) {
+      if (mCurrentOpGenerator) {
+        mCurrentOpGenerator->OutputOp();
+      }
+      MOZ_ASSERT(false);
+    }
+#endif
   }
-  void AndWith(const nsRect& aOther)
+
+  nsRegion& AndWith(const nsRegion& aRegion)
   {
-    And(*this, aOther);
+    if (mBounds.IsEmpty()) {
+      // Region is empty, stays empty.
+      return *this;
+    }
+
+    if (aRegion.IsEmpty()) {
+      SetEmpty();
+      return *this;
+    }
+
+    if (aRegion.mBands.empty()) {
+      // Other region is a rect.
+      return AndWith(aRegion.mBounds);
+    }
+
+    if (mBands.empty()) {
+      mBands.push_back(mBounds);
+    }
+
+    size_t idx = 0;
+    size_t idxOther = 0;
+
+    std::vector<Band> newBands;
+
+    while (true) {
+      while (true) {
+        while (idx != mBands.size() && mBands[idx].bottom <= aRegion.mBands[idxOther].top) {
+          idx++;
+        }
+
+        if (idx == mBands.size()) {
+          break;
+        }
+
+        while (idxOther != aRegion.mBands.size() && aRegion.mBands[idxOther].bottom <= mBands[idx].top) {
+          idxOther++;
+        }
+
+        if (idxOther == aRegion.mBands.size()) {
+          break;
+        }
+
+        if (aRegion.mBands[idxOther].top <= mBands[idx].bottom) {
+          break;
+        }
+      }
+
+      if (idx == mBands.size() || idxOther == aRegion.mBands.size()) {
+        break;
+      }
+
+      Band newBand(mBands[idx]);
+      newBand.top = std::max(mBands[idx].top, aRegion.mBands[idxOther].top);
+      newBand.bottom = std::min(mBands[idx].bottom, aRegion.mBands[idxOther].bottom);
+      newBand.IntersectStrips(aRegion.mBands[idxOther]);
+
+      if (newBand.mStrips.size()) {
+        if (newBands.size() && newBands.back().bottom == newBand.top &&
+          newBands.back().EqualStrips(newBand)) {
+          newBands.back().bottom = newBand.bottom;
+        } else {
+          newBands.push_back(newBand);
+        }
+      }
+
+      if (aRegion.mBands[idxOther].bottom < mBands[idx].bottom) {
+        idxOther++;
+        if (idxOther == aRegion.mBands.size()) {
+          break;
+        }
+      } else {
+        idx++;
+      }
+    }
+
+    mBands = newBands;
+    if (!newBands.size()) {
+      mBounds = nsRect();
+    } else {
+      mBounds = CalculateBounds();
+    }
+
+    if (mBands.size() == 1 && mBands.front().mStrips.size() == 1) {
+      mBands.clear();
+    }
+
+    AssertState();
+
+    return *this;
   }
-  nsRegion& And(const nsRegion& aRgn1,   const nsRegion& aRgn2)
+
+  nsRegion& AndWith(const nsRect& aRect)
   {
-    pixman_region32_intersect(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+    if (aRect.IsEmpty()) {
+      SetEmpty();
+    }
+
+    mBounds = mBounds.Intersect(aRect);
+
+    if (mBands.empty()) {
+      return *this;
+    }
+
+    size_t idx = 0;
+
+    while (idx != mBands.size()) {
+      if (mBands[idx].bottom <= aRect.Y()) {
+        MOZ_ASSERT(idx == 0);
+        mBands.erase(mBands.begin());
+        continue;
+      }
+
+      if (mBands[idx].top >= aRect.YMost()) {
+        mBands.erase(mBands.begin() + idx);
+        continue;
+      }
+
+      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.size()) {
+        mBands.erase(mBands.begin() + idx);
+      } else {
+        CompressBefore(idx);
+        idx++;
+      }
+    }
+
+    mBounds = CalculateBounds();
+    EnsureSimplified();
+    AssertState();
     return *this;
   }
+  nsRegion& And(const nsRegion& aRgn1, const nsRegion& aRgn2)
+  {
+    if (&aRgn1 != this) {
+      *this = aRgn1;
+    }
+    return AndWith(aRgn2);
+  }
   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) {
+      *this = aRegion;
+    }
+    AndWith(aRect);
     return *this;
   }
   nsRegion& And(const nsRect& aRect1, const nsRect& aRect2)
   {
     nsRect 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);
@@ -186,70 +413,275 @@ 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& SubOut(const nsRegion& aOther)
   {
     return Sub(*this, aOther);
   }
   nsRegion& SubOut(const nsRect& aOther)
   {
-    return Sub(*this, aOther);
+    return SubWith(aOther);
   }
   nsRegion& Sub(const nsRegion& aRgn1, const nsRegion& aRgn2)
   {
-    pixman_region32_subtract(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+    if (&aRgn1 != this) {
+      Copy(aRgn1);
+    }
+    // This implementation could be optimized.
+    for (RectIterator idx(aRgn2); !idx.Done(); idx.Next()) {
+      SubWith(idx.Get());
+    }
+    return *this;
+  }
+
+  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(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.empty()) {
+      mBands.push_back(Band(mBounds));
+    }
+
+    Strip rectStrip(aRect.X(), aRect.XMost());
+
+    size_t idx = 0;
+
+    while (idx < mBands.size()) {
+      if (mBands[idx].top >= aRect.YMost()) {
+        // This band is entirely after aRect. Done.
+        mBounds = CalculateBounds();
+        AssertState();
+        return *this;
+      }
+
+      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.
+        auto above = mBands.insert(mBands.begin() + idx, 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.size()) {
+          CompressAdjacentBands(idx);
+        } else {
+          mBands.erase(mBands.begin() + 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.size()) {
+        if (mBands[idx - 1].bottom == newBand.top && newBand.EqualStrips(mBands[idx - 1])) {
+          mBands[idx - 1].bottom = aRect.YMost();
+        } else {
+          mBands.insert(mBands.begin() + idx, newBand);
+        }
+      }
+
+      mBounds = CalculateBounds();
+      AssertState();
+      return *this;
+    }
+
+    mBounds = CalculateBounds();
+    AssertState();
     return *this;
   }
   nsRegion& Sub(const nsRegion& aRegion, const nsRect& aRect)
   {
-    return Sub(aRegion, nsRegion(aRect));
+    Copy(aRegion);
+    return SubWith(aRect);
   }
   nsRegion& Sub(const nsRect& aRect, const nsRegion& aRegion)
   {
     return Sub(nsRegion(aRect), aRegion);
   }
   nsRegion& Sub(const nsRect& aRect1, const nsRect& aRect2)
   {
     Copy(aRect1);
     return Sub(*this, 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.empty()) {
+      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.empty()) {
+      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);
+    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
   {
@@ -269,197 +701,668 @@ 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.empty() && aRegion.mBands.empty()) {
+      return mBounds.IsEqualInterior(aRegion.mBounds);
+    }
+
+    if (mBands.size() != aRegion.mBands.size()) {
+      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.empty()) {
+      return mBounds.IsEmpty() ? 0 : 1;
+    }
+
+    uint32_t rects = 0;
+
+    for (const Band& band : mBands) {
+      rects += band.mStrips.size();
+    }
+
+    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.size() == 1 && mBands.front().mStrips.size() == 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;
+      }
 
-#ifndef MOZ_TREE_PIXMAN
-  // For compatibility with pixman versions older than 0.25.2.
-  static inline void
-  pixman_region32_clear(pixman_region32_t *region)
-  {
-    pixman_region32_fini(region);
-    pixman_region32_init(region);
-  }
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream(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
 
-  nsIntRegion ToPixels(nscoord aAppUnitsPerPixel, bool aOutsidePixels) const;
+    bool isSimple = mBands.empty();
+
+    if (isSimple) {
+      if (mBounds.IsEmpty()) {
+        mBounds = aRect;
+        return;
+      } else if (mBounds.Contains(aRect)) {
+        return;
+      }
+
+      mBands.push_back(Band(mBounds));
+    }
+
+    mBounds = aRect.Union(mBounds);
+
+    size_t idx = 0;
+
+    Strip strip(aRect.X(), aRect.XMost());
+    Band remaining(aRect);
+
+    while (idx != mBands.size()) {
+      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.insert(mBands.begin() + 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;
+      }
 
-  nsRegion& Copy (const nsRegion& aRegion)
+      // mBands[idx].top <= remaining.top.
+
+      if (mBands[idx].top < remaining.top) {
+        auto before = mBands.insert(mBands.begin() + idx, 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.insert(mBands.begin() + idx + 1, 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.insert(mBands.begin() + idx, remaining);
+      idx++;
+      CompressBefore(idx);
+    } else {
+      CompressBefore(idx);
+    }
+
+    AssertState();
+    EnsureSimplified();
+  }
+
+  nsRect CalculateBounds() const
   {
-    pixman_region32_copy(&mImpl, aRegion.Impl());
-    return *this;
+    if (mBands.empty()) {
+      return mBounds;
+    }
+
+    int32_t top = mBands.front().top;
+    int32_t bottom = mBands.back().bottom;
+
+    int32_t leftMost = mBands.front().mStrips.front().left;
+    int32_t rightMost = mBands.front().mStrips.back().right;
+    for (const Band& band : mBands) {
+      leftMost = std::min(leftMost, band.mStrips.front().left);
+      rightMost = std::max(rightMost, band.mStrips.back().right);
+    }
+
+    return nsRect(leftMost, top, rightMost - leftMost, bottom - top);
   }
 
-  nsRegion& Copy (const nsRect& aRect)
+  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
   {
-    // 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);
+    MOZ_IMPLICIT Band(const nsRect& aRect)
+      : top(aRect.Y()), bottom(aRect.YMost())
+    {
+      mStrips.push_back({ aRect.X(), aRect.XMost() });
+    }
+
+    void InsertStrip(const Strip& aStrip)
+    {
+      for (auto iter = mStrips.begin();; iter++) {
+        if (iter == mStrips.end() || iter->left > aStrip.right) {
+          mStrips.insert(iter, aStrip);
+          return;
+        }
+
+        if (iter->right < aStrip.left) {
+          continue;
+        }
+
+        iter->left = std::min(iter->left, aStrip.left);
+
+        if (iter->right >= aStrip.right) {
+          return;
+        }
+
+        auto next = iter;
+        next++;
+        while (next != mStrips.end() && next->left <= aStrip.right) {
+          iter->right = next->right;
+
+          next = mStrips.erase(next);
+        }
+
+        iter->right = std::max(iter->right, aStrip.right);
+        return;
+      }
+    }
+
+    void SubStrip(const Strip& aStrip)
+    {
+      for (auto iter = mStrips.begin(); iter != mStrips.end(); iter++) {
+        if (iter->left > aStrip.right) {
+          // Strip is entirely to the right of aStrip. Done.
+          return;
+        }
+
+        if (iter->right < aStrip.left) {
+          // Strip is entirely to the left of aStrip. Move on.
+          continue;
+        }
+
+        if (iter->left < aStrip.left) {
+          if (iter->right <= aStrip.right) {
+            iter->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, iter->right);
+          iter->right = aStrip.left;
+          iter++;
+          mStrips.insert(iter, newStrip);
+          return;
+        }
+
+        // This strip lies to the right of the start of aStrip.
+        if (iter->right <= aStrip.right) {
+          // aStrip completely contains this strip.
+          iter = mStrips.erase(iter);
+          iter--;
+          continue;
+        }
+        iter->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) {
+          aStrip.left = std::max(aStrip.left, strip.left);
+        }
+
+        intersected = true;
+        rightMost = std::min(strip.right, aStrip.right);
+      }
+
+      if (intersected) {
+        aStrip.right = rightMost;
+      }
+      else {
+        aStrip.right = aStrip.left = 0;
+      }
+      return intersected;
     }
-    return *this;
+
+    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.size() != aBand.mStrips.size()) {
+        return false;
+      }
+
+      for (auto idx1 = mStrips.begin(), idx2 = aBand.mStrips.begin();
+        idx1 != mStrips.end(); idx1++, idx2++)
+      {
+        if (*idx1 != *idx2) {
+          return false;
+        }
+      }
+
+      return true;
+    }
+
+    void IntersectStrip(const Strip& aStrip)
+    {
+      auto idx = mStrips.begin();
+
+      while (idx != mStrips.end()) {
+        if (idx->right <= aStrip.left) {
+          idx = mStrips.erase(idx);
+          continue;
+        }
+
+        if (idx->left >= aStrip.right) {
+          while (idx != mStrips.end()) {
+            idx = mStrips.erase(idx);
+          }
+          return;
+        }
+
+        idx->left = std::max(aStrip.left, idx->left);
+        idx->right = std::min(aStrip.right, idx->right);
+        idx++;
+      }
+    }
+
+    void IntersectStrips(const Band& aOther)
+    {
+      auto idx = mStrips.begin();
+      auto idxOther = aOther.mStrips.begin();
+
+      std::vector<Strip> newStrips;
+
+      while (true) {
+        while (true) {
+          while (idx != mStrips.end() && idx->right <= idxOther->left) {
+            idx++;
+          }
+
+          if (idx == mStrips.end()) {
+            break;
+          }
+
+          while (idxOther != aOther.mStrips.end() && idxOther->right <= idx->left) {
+            idxOther++;
+          }
+
+          if (idxOther == aOther.mStrips.end()) {
+            break;
+          }
+
+          if (idxOther->left <= idx->right) {
+            break;
+          }
+        }
+
+        if (idx == mStrips.end() || idxOther == aOther.mStrips.end()) {
+          break;
+        }
+
+        newStrips.push_back(Strip(std::max(idx->left, idxOther->left), std::min(idxOther->right, idx->right)));
+
+        if (idxOther->right < idx->right) {
+          idxOther++;
+        }
+        else {
+          idx++;
+        }
+      }
+
+      mStrips = newStrips;
+    }
+
+    int32_t top;
+    int32_t bottom;
+    std::vector<Strip> mStrips;
+  };
+  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.size()) {
+      if (mBands[aIdx + 1].top == mBands[aIdx].bottom && mBands[aIdx + 1].EqualStrips(mBands[aIdx])) {
+        mBands[aIdx].bottom = mBands[aIdx + 1].bottom;
+        mBands.erase(mBands.begin() + 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.erase(mBands.begin() + aIdx);
+        return true;
+      }
+    }
+    return false;
   }
 
-  pixman_region32_t* Impl() const
+  void CompressBefore(size_t& aIdx)
+  {
+    if (aIdx && aIdx < mBands.size()) {
+      if (mBands[aIdx - 1].bottom == mBands[aIdx].top && mBands[aIdx - 1].EqualStrips(mBands[aIdx])) {
+        mBands[aIdx].top = mBands[aIdx - 1].top;
+        mBands.erase(mBands.begin() + aIdx - 1);
+        aIdx--;
+      }
+    }
+  }
+
+
+  std::vector<Band> mBands;
+  nsRect mBounds;
+#ifdef DEBUG_REGIONS
+  friend class OperationStringGenerator;
+  OperationStringGenerator* mCurrentOpGenerator;
+#endif
+
+public:
+  class RectIterator
   {
-    return const_cast<pixman_region32_t*>(&mImpl);
-  }
+    const nsRegion& mRegion;
+    typename std::vector<Band>::const_iterator mCurrentBand;
+    typename std::vector<Strip>::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();
+      }
+    }
+
+    bool Done() const { return mIsDone; }
+
+    const nsRect Get() const
+    {
+      if (mRegion.mBands.empty()) {
+        return mRegion.mBounds;
+      }
+      return nsRect(mCurrentStrip->left, mCurrentBand->top,
+        mCurrentStrip->right - mCurrentStrip->left,
+        mCurrentBand->bottom - mCurrentBand->top);
+    }
+
+    void Next()
+    {
+      if (mRegion.mBands.empty()) {
+        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.
  */
@@ -643,17 +1546,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());
@@ -691,17 +1594,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,233 @@ 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));
+  }
+#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) {
+  {
+    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));
+  }
+
+  const uint32_t TestIterations = 100000;
+  const uint32_t RectsPerTest = 100;
+  const uint32_t SubRectsPerTest = 10;
+
+  nsRect rects[RectsPerTest];
+  nsRect subRects[SubRectsPerTest];
+
+#ifdef REGION_RANDOM_STRESS_TESTS
+  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(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));
+  }
+#endif
+}
+
+#ifdef REGION_RANDOM_STRESS_TESTS
+TEST(Gfx, RegionAndWith) {
+  const uint32_t TestIterations = 10000;
+  const uint32_t RectsPerTest = 100;
+  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);
+        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));
+          if (!r2.Contains(p.x, p.y)) {
+            *(int*)0x0 = 1;
+          }
+        } else {
+          EXPECT_FALSE(r2.Contains(p.x, p.y));
+          if (r2.Contains(p.x, p.y)) {
+            *(int*)0x0 = 1;
+          }
+        }
+      }
+    }
+  }
+}
+#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));
@@ -219,16 +438,17 @@ TEST(Gfx, RegionSimplify) {
     r.SimplifyOutwardByArea(100*100);
 
     nsRegion result(nsRect(0,100,300,300));
 
     EXPECT_TRUE(r.IsEqual(result)) <<
       "regions not merged";
   }
 
+
   { // the rectangles will be merged
     nsRegion r(nsRect(0,100,200,100));
     r.Or(r, nsRect(0,200,300,200));
     r.Or(r, nsRect(250,100,50,100));
     r.Sub(r, nsRect(200,200,40,200));
 
     EXPECT_TRUE(r.GetNumRects() == 4) <<
       "wrong number of rects";
--- a/layout/svg/nsFilterInstance.cpp
+++ b/layout/svg/nsFilterInstance.cpp
@@ -603,17 +603,18 @@ nsIntRegion
 nsFilterInstance::FrameSpaceToFilterSpace(const nsRegion* aRegion) const
 {
   if (!aRegion) {
     return OutputFilterSpaceBounds();
   }
   nsIntRegion result;
   for (auto iter = aRegion->RectIter(); !iter.Done(); iter.Next()) {
     // FrameSpaceToFilterSpace rounds out, so this works.
-    result.Or(result, FrameSpaceToFilterSpace(&iter.Get()));
+    nsRect rect = iter.Get();
+    result.Or(result, FrameSpaceToFilterSpace(&rect));
   }
   return result;
 }
 
 nsRegion
 nsFilterInstance::FilterSpaceToFrameSpace(const nsIntRegion& aRegion) const
 {
   nsRegion result;