Bug 1440753: Replace pixman regions with our own region code. r=mattwoodrow
☠☠ backed out by 14ef02ecc303 ☠ ☠
authorBas Schouten <bschouten@mozilla.com>
Fri, 09 Mar 2018 05:27:15 +0100
changeset 462333 d9297cea0239855bcbef78e40967b4054983a093
parent 462332 3e333746d6339fe947e3b6e9be581a2b88f67f8d
child 462334 d2474e66469725bef72fc67c20eb99282018caad
push id1683
push usersfraser@mozilla.com
push dateThu, 26 Apr 2018 16:43:40 +0000
treeherdermozilla-release@5af6cb21869d [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmattwoodrow
bugs1440753
milestone60.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1440753: Replace pixman regions with our own region code. r=mattwoodrow MozReview-Commit-ID: KPsTAw3Uwa2
gfx/layers/client/ContentClient.cpp
gfx/src/nsRect.h
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/nsRect.h
+++ b/gfx/src/nsRect.h
@@ -107,16 +107,20 @@ struct nsRect :
   void UnionRectEdges(const nsRect& aRect1, const nsRect& aRect2)
   {
     *this = aRect1.UnionEdges(aRect2);
   }
   MOZ_MUST_USE nsRect Union(const nsRect& aRect) const
   {
     return SaturatingUnion(aRect);
   }
+  MOZ_MUST_USE nsRect UnsafeUnion(const nsRect& aRect) const
+  {
+    return Super::Union(aRect);
+  }
   void UnionRect(const nsRect& aRect1, const nsRect& aRect2)
   {
     *this = aRect1.Union(aRect2);
   }
 #endif
 
   void SaturatingUnionRect(const nsRect& aRect1, const nsRect& aRect2)
   {
--- a/gfx/src/nsRegion.cpp
+++ b/gfx/src/nsRegion.cpp
@@ -5,545 +5,425 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 
 #include "nsRegion.h"
 #include "nsTArray.h"
 #include "gfxUtils.h"
 #include "mozilla/ToString.h"
 
+using namespace std;
+
+void
+nsRegion::AssertStateInternal() const
+{
+  bool failed = false;
+  // Verify consistent state inside the region.
+  int32_t lastY = INT32_MIN;
+  int32_t lowestX = INT32_MAX;
+  int32_t highestX = INT32_MIN;
+  for (auto iter = mBands.begin(); iter != mBands.end(); iter++) {
+    const Band& band = *iter;
+    if (band.bottom <= band.top) {
+      failed = true;
+      break;
+    }
+    if (band.top < lastY) {
+      failed = true;
+      break;
+    }
+    lastY = band.bottom;
+
+    lowestX = std::min(lowestX, band.mStrips.begin()->left);
+    highestX = std::max(highestX, band.mStrips.LastElement().right);
+
+    int32_t lastX = INT32_MIN;
+    if (iter != mBands.begin()) {
+      auto prev = iter;
+      prev--;
+
+      if (prev->bottom == iter->top) {
+        if (band.EqualStrips(*prev)) {
+          failed = true;
+          break;
+        }
+      }
+    }
+    for (const Strip& strip : band.mStrips) {
+      if (strip.right <= strip.left) {
+        failed = true;
+        break;
+      }
+      if (strip.left <= lastX) {
+        failed = true;
+        break;
+      }
+      lastX = strip.right;
+    }
+    if (failed) {
+      break;
+    }
+  }
+
+  if (!(mBounds == CalculateBounds())) {
+    failed = true;
+  }
+
+  if (failed) {
+#ifdef DEBUG_REGIONS
+    if (mCurrentOpGenerator) {
+      mCurrentOpGenerator->OutputOp();
+    }
+#endif
+    MOZ_ASSERT(false);
+  }
+}
+
 bool nsRegion::Contains(const nsRegion& aRgn) const
 {
   // XXX this could be made faster by iterating over
   // both regions at the same time some how
   for (auto iter = aRgn.RectIter(); !iter.Done(); iter.Next()) {
     if (!Contains(iter.Get())) {
       return false;
     }
   }
   return true;
 }
 
 bool nsRegion::Intersects(const nsRect& aRect) const
 {
-  // XXX this could be made faster by using pixman_region32_contains_rect
   for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
     if (iter.Get().Intersects(aRect)) {
       return true;
     }
   }
   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;
+  *this = std::move(newRegion);
 }
 
 void nsRegion::SimplifyOutward (uint32_t aMaxRects)
 {
   MOZ_ASSERT(aMaxRects >= 1, "Invalid max rect count");
 
-  if (GetNumRects() <= aMaxRects)
+  if (GetNumRects() <= aMaxRects) {
     return;
-
-  pixman_box32_t *boxes;
-  int n;
-  boxes = pixman_region32_rectangles(&mImpl, &n);
+  }
 
   // Try combining rects in horizontal bands into a single rect
-  int dest = 0;
-  for (int src = 1; src < n; src++)
-  {
-    // The goal here is to try to keep groups of rectangles that are vertically
-    // discontiguous as separate rectangles in the final region. This is
-    // simple and fast to implement and page contents tend to vary more
-    // vertically than horizontally (which is why our rectangles are stored
-    // sorted by y-coordinate, too).
-    //
-    // Note: if boxes share y1 because of the canonical representation they
-    // will share y2
-    while ((src < (n)) && boxes[dest].y1 == boxes[src].y1) {
-      // merge box[i] and box[i+1]
-      boxes[dest].x2 = boxes[src].x2;
-      src++;
-    }
-    if (src < n) {
-      dest++;
-      boxes[dest] = boxes[src];
+  // The goal here is to try to keep groups of rectangles that are vertically
+  // discontiguous as separate rectangles in the final region. This is
+  // simple and fast to implement and page contents tend to vary more
+  // vertically than horizontally (which is why our rectangles are stored
+  // sorted by y-coordinate, too).
+  //
+  // Note: if boxes share y1 because of the canonical representation they
+  // will share y2
+
+  size_t idx = 0;
+
+  while (idx < mBands.Length()) {
+    size_t oldIdx = idx;
+    mBands[idx].mStrips.begin()->right = mBands[idx].mStrips.LastElement().right;
+    mBands[idx].mStrips.TruncateLength(1);
+    idx++;
+
+    // Merge any bands with the same bounds.
+    while (idx < mBands.Length() &&
+           mBands[idx].mStrips.begin()->left == mBands[oldIdx].mStrips.begin()->left &&
+           mBands[idx].mStrips.LastElement().right == mBands[oldIdx].mStrips.begin()->right) {
+      mBands[oldIdx].bottom = mBands[idx].bottom;
+      mBands.RemoveElementAt(idx);
     }
   }
 
-  uint32_t reducedCount = dest+1;
-  // pixman has a special representation for
-  // regions of 1 rectangle. So just use the
-  // bounds in that case
-  if (reducedCount > 1 && reducedCount <= aMaxRects) {
-    // reach into pixman and lower the number
-    // of rects stored in data.
-    mImpl.data->numRects = reducedCount;
-  } else {
+  AssertState();
+
+  // mBands.size() is now equal to our rect count.
+  if (mBands.Length() > aMaxRects) {
     *this = GetBounds();
   }
 }
 
 // compute the covered area difference between two rows.
 // by iterating over both rows simultaneously and adding up
 // the additional increase in area caused by extending each
 // of the rectangles to the combined height of both rows
-static uint32_t ComputeMergedAreaIncrease(pixman_box32_t *topRects,
-		                     pixman_box32_t *topRectsEnd,
-		                     pixman_box32_t *bottomRects,
-		                     pixman_box32_t *bottomRectsEnd)
+uint32_t
+nsRegion::ComputeMergedAreaIncrease(const Band& aTopBand,
+                                    const Band& aBottomBand)
 {
   uint32_t totalArea = 0;
-  struct pt {
-    int32_t x, y;
-  };
 
+  uint32_t topHeight = aBottomBand.top - aTopBand.top;
+  uint32_t bottomHeight = aBottomBand.bottom - aTopBand.bottom;
+  uint32_t currentStripBottom = 0;
 
-  pt *i = (pt*)topRects;
-  pt *end_i = (pt*)topRectsEnd;
-  pt *j = (pt*)bottomRects;
-  pt *end_j = (pt*)bottomRectsEnd;
-  bool top = false;
-  bool bottom = false;
+  // This could be done with slightly better worse case performance by merging these two
+  // for-loops, but this makes the code a lot easier to understand.
+  for (auto& strip : aTopBand.mStrips) {
+    if (currentStripBottom == aBottomBand.mStrips.Length() || strip.right < aBottomBand.mStrips[currentStripBottom].left) {
+      totalArea += bottomHeight * strip.Size();
+      continue;
+    }
 
-  int cur_x = i->x;
-  bool top_next = top;
-  bool bottom_next = bottom;
-  //XXX: we could probably simplify this condition and perhaps move it into the loop below
-  if (j->x < cur_x) {
-    cur_x = j->x;
-    j++;
-    bottom_next = !bottom;
-  } else if (j->x == cur_x) {
-    i++;
-    top_next = !top;
-    bottom_next = !bottom;
-    j++;
-  } else {
-    top_next = !top;
-    i++;
-  }
+    int32_t currentX = strip.left;
+    while (currentStripBottom != aBottomBand.mStrips.Length() && aBottomBand.mStrips[currentStripBottom].left < strip.right) {
+      if (currentX >= strip.right) {
+        break;
+      }
+      if (currentX < aBottomBand.mStrips[currentStripBottom].left) {
+        // Add the part that's not intersecting.
+        totalArea += (aBottomBand.mStrips[currentStripBottom].left - currentX) * bottomHeight;
+      }
+
+      currentX = std::max(aBottomBand.mStrips[currentStripBottom].right, currentX);
+      currentStripBottom++;
+    }
 
-  int topRectsHeight = topRects->y2 - topRects->y1;
-  int bottomRectsHeight = bottomRects->y2 - bottomRects->y1;
-  int inbetweenHeight = bottomRects->y1 - topRects->y2;
-  int width = cur_x;
-  // top and bottom are the in-status to the left of cur_x
-  do {
-    if (top && !bottom) {
-      totalArea += (inbetweenHeight+bottomRectsHeight)*width;
-    } else if (bottom && !top) {
-      totalArea += (inbetweenHeight+topRectsHeight)*width;
-    } else if (bottom && top) {
-      totalArea += (inbetweenHeight)*width;
+    // Add remainder of this strip.
+    if (currentX < strip.right) {
+      totalArea += (strip.right - currentX) * bottomHeight;
+    }
+    currentStripBottom--;
+  }
+  uint32_t currentStripTop = 0;
+  for (auto& strip : aBottomBand.mStrips) {
+    if (currentStripTop == aTopBand.mStrips.Length() || strip.right < aTopBand.mStrips[currentStripTop].left) {
+      totalArea += topHeight * strip.Size();
+      continue;
     }
-    top = top_next;
-    bottom = bottom_next;
-    // find the next edge
-    if (i->x < j->x) {
-      top_next = !top;
-      width = i->x - cur_x;
-      cur_x = i->x;
-      i++;
-    } else if (j->x < i->x) {
-      bottom_next = !bottom;
-      width = j->x - cur_x;
-      cur_x = j->x;
-      j++;
-    } else { // i->x == j->x
-      top_next = !top;
-      bottom_next = !bottom;
-      width = i->x - cur_x;
-      cur_x = i->x;
-      i++;
-      j++;
+
+    int32_t currentX = strip.left;
+    while (currentStripTop != aTopBand.mStrips.Length() && aTopBand.mStrips[currentStripTop].left < strip.right) {
+      if (currentX >= strip.right) {
+        break;
+      }
+      if (currentX < aTopBand.mStrips[currentStripTop].left) {
+        // Add the part that's not intersecting.
+        totalArea += (aTopBand.mStrips[currentStripTop].left - currentX) * topHeight;
+      }
+
+      currentX = std::max(aTopBand.mStrips[currentStripTop].right, currentX);
+      currentStripTop++;
     }
-  } while (i < end_i && j < end_j);
 
-  // handle any remaining rects
-  while (i < end_i) {
-    width = i->x - cur_x;
-    cur_x = i->x;
-    i++;
-    if (top)
-      totalArea += (inbetweenHeight+bottomRectsHeight)*width;
-    top = !top;
-  }
-
-  while (j < end_j) {
-    width = j->x - cur_x;
-    cur_x = j->x;
-    j++;
-    if (bottom)
-      totalArea += (inbetweenHeight+topRectsHeight)*width;
-    bottom = !bottom;
+    // Add remainder of this strip.
+    if (currentX < strip.right) {
+      totalArea += (strip.right - currentX) * topHeight;
+    }
+    currentStripTop--;
   }
   return totalArea;
 }
 
-static pixman_box32_t *
-CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end)
-{
-    // XXX: std::copy
-    pixman_box32_t *src_it = src_start;
-    while (src_it < src_end) {
-        *dest_it++ = *src_it++;
-    }
-    return dest_it;
-}
-
-
-#define WRITE_RECT(x1, x2, y1, y2) \
-    do {                    \
-         tmpRect->x1 = x1;  \
-         tmpRect->x2 = x2;  \
-         tmpRect->y1 = y1;  \
-         tmpRect->y2 = y2;  \
-         tmpRect++;         \
-    } while (0)
-
-/* If 'r' overlaps the current rect, then expand the current rect to include
- * it. Otherwise write the current rect out to tmpRect, and set r as the
- * updated current rect. */
-#define MERGE_RECT(r)                 \
-    do {                              \
-      if (r->x1 <= x2) {              \
-          if (x2 < r->x2)             \
-              x2 = r->x2;             \
-      } else {                        \
-          WRITE_RECT(x1, x2, y1, y2); \
-          x1 = r->x1;                 \
-          x2 = r->x2;                 \
-      }                               \
-      r++;                            \
-    } while (0)
-
-
-/* Can we merge two sets of rects without extra space?
- * Yes, but not easily. We can even do it stably
- * but we don't need that property.
- *
- * This is written in the style of pixman_region_union_o */
-static pixman_box32_t *
-MergeRects(pixman_box32_t *r1,
-           pixman_box32_t *r1_end,
-           pixman_box32_t *r2,
-           pixman_box32_t *r2_end,
-           pixman_box32_t *tmpRect)
-{
-    /* This routine works by maintaining the current
-     * rectangle in x1,x2,y1,y2 and either merging
-     * in the left most rectangle if it overlaps or
-     * outputing the current rectangle and setting
-     * it to the the left most one */
-    const int y1 = r1->y1;
-    const int y2 = r2->y2;
-    int x1;
-    int x2;
-
-    /* Find the left-most edge */
-    if (r1->x1 < r2->x1) {
-        x1 = r1->x1;
-        x2 = r1->x2;
-        r1++;
-    } else {
-        x1 = r2->x1;
-        x2 = r2->x2;
-        r2++;
-    }
-
-    while (r1 != r1_end && r2 != r2_end) {
-        /* Find and merge the left-most rectangle */
-        if (r1->x1 < r2->x1)
-            MERGE_RECT (r1);
-        else
-            MERGE_RECT (r2);
-    }
-
-    /* Finish up any left overs */
-    if (r1 != r1_end) {
-        do {
-            MERGE_RECT (r1);
-        } while (r1 != r1_end);
-    } else if (r2 != r2_end) {
-        do {
-            MERGE_RECT(r2);
-        } while (r2 != r2_end);
-    }
-
-    /* Finish up the last rectangle */
-    WRITE_RECT(x1, x2, y1, y2);
-
-    return tmpRect;
-}
-
 void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold)
 {
-
-  pixman_box32_t *boxes;
-  int n;
-  boxes = pixman_region32_rectangles(&mImpl, &n);
-
-  // if we have no rectangles then we're done
-  if (!n)
+  if (mBands.Length() < 2) {
+    // We have only one or no row and we're done.
     return;
-
-  pixman_box32_t *end = boxes + n;
-  pixman_box32_t *topRectsEnd = boxes+1;
-  pixman_box32_t *topRects = boxes;
-
-  // we need some temporary storage for merging both rows of rectangles
-  AutoTArray<pixman_box32_t, 10> tmpStorage;
-  tmpStorage.SetCapacity(n);
-  pixman_box32_t *tmpRect = tmpStorage.Elements();
-
-  pixman_box32_t *destRect = boxes;
-  pixman_box32_t *rect = tmpRect;
-  // find the end of the first span of rectangles
-  while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
-    topRectsEnd++;
   }
 
-  // if we only have one row we are done
-  if (topRectsEnd == end)
-    return;
-
-  pixman_box32_t *bottomRects = topRectsEnd;
-  pixman_box32_t *bottomRectsEnd = bottomRects+1;
+  uint32_t currentBand = 0;
   do {
-    // find the end of the bottom span of rectangles
-    while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
-      bottomRectsEnd++;
-    }
-    uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd,
-                                                   bottomRects, bottomRectsEnd);
+    Band& band = mBands[currentBand];
+
+    uint32_t totalArea = ComputeMergedAreaIncrease(band, mBands[currentBand + 1]);
 
     if (totalArea <= aThreshold) {
-      // merge the rects into tmpRect
-      rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect);
-
-      // set topRects to where the newly merged rects will be so that we use them
-      // as our next set of topRects
-      topRects = destRect;
-      // copy the merged rects back into the destination
-      topRectsEnd = CopyRow(destRect, tmpRect, rect);
+      for (Strip& strip : mBands[currentBand + 1].mStrips) {
+        // This could use an optimized function to merge two bands.
+        band.InsertStrip(strip);
+      }
+      band.bottom = mBands[currentBand + 1].bottom;
+      mBands.RemoveElementAt(currentBand + 1);
     } else {
-      // copy the unmerged rects
-      destRect = CopyRow(destRect, topRects, topRectsEnd);
+      currentBand++;
+    }
+  } while (currentBand + 1 < mBands.Length());
 
-      topRects = bottomRects;
-      topRectsEnd = bottomRectsEnd;
-      if (bottomRectsEnd == end) {
-        // copy the last row when we are done
-        topRectsEnd = CopyRow(destRect, topRects, topRectsEnd);
-      }
-    }
-    bottomRects = bottomRectsEnd;
-  } while (bottomRectsEnd != end);
-
-
-  uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n);
-  // pixman has a special representation for
-  // regions of 1 rectangle. So just use the
-  // bounds in that case
-  if (reducedCount > 1) {
-    // reach into pixman and lower the number
-    // of rects stored in data.
-    this->mImpl.data->numRects = reducedCount;
-  } else {
-    *this = GetBounds();
-  }
+  EnsureSimplified();
+  AssertState();
 }
 
 
 typedef void (*visit_fn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2);
 
-static bool VisitNextEdgeBetweenRect(visit_fn visit, void *closure, VisitSide side,
-				     pixman_box32_t *&r1, pixman_box32_t *&r2, const int y, int &x1)
+void nsRegion::VisitEdges (visit_fn visit, void *closure)
 {
-  // check for overlap
-  if (r1->x2 >= r2->x1) {
-    MOZ_ASSERT(r2->x1 >= x1);
-    visit(closure, side, x1, y, r2->x1, y);
-
-    // find the rect that ends first or always drop the one that comes first?
-    if (r1->x2 < r2->x2) {
-      x1 = r1->x2;
-      r1++;
-    } else {
-      x1 = r2->x2;
-      r2++;
-    }
-    return true;
-  } else {
-    MOZ_ASSERT(r1->x2 < r2->x2);
-    // we handle the corners by just extending the top and bottom edges
-    visit(closure, side, x1, y, r1->x2+1, y);
-    r1++;
-    // we assign x1 because we can assume that x1 <= r2->x1 - 1
-    // However the caller may know better and if so, may update
-    // x1 to r1->x1
-    x1 = r2->x1 - 1;
-    return false;
+  if (mBands.IsEmpty()) {
+    visit(closure, VisitSide::LEFT, mBounds.X(), mBounds.Y(), mBounds.X(), mBounds.YMost());
+    visit(closure, VisitSide::RIGHT, mBounds.XMost(), mBounds.Y(), mBounds.XMost(), mBounds.YMost());
+    visit(closure, VisitSide::TOP, mBounds.X() - 1, mBounds.Y(), mBounds.XMost() + 1, mBounds.Y());
+    visit(closure, VisitSide::BOTTOM, mBounds.X() - 1, mBounds.YMost(), mBounds.XMost() + 1, mBounds.YMost());
+    return;
   }
-}
-
-//XXX: if we need to this can compute the end of the row
-static void
-VisitSides(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
-  // XXX: we can drop LEFT/RIGHT and just use the orientation
-  // of the line if it makes sense
-  while (r != r_end) {
-    visit(closure, VisitSide::LEFT, r->x1, r->y1, r->x1, r->y2);
-    visit(closure, VisitSide::RIGHT, r->x2, r->y1, r->x2, r->y2);
-    r++;
-  }
-}
 
-static void
-VisitAbove(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
-  while (r != r_end) {
-    visit(closure, VisitSide::TOP, r->x1-1, r->y1, r->x2+1, r->y1);
-    r++;
-  }
-}
-
-static void
-VisitBelow(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
-  while (r != r_end) {
-    visit(closure, VisitSide::BOTTOM, r->x1-1, r->y2, r->x2+1, r->y2);
-    r++;
-  }
-}
-
-static pixman_box32_t *
-VisitInbetween(visit_fn visit, void *closure, pixman_box32_t *r1,
-               pixman_box32_t *r1_end,
-               pixman_box32_t *r2,
-               pixman_box32_t *r2_end)
-{
-  const int y = r1->y2;
-  int x1;
-
-  bool overlap = false;
-  while (r1 != r1_end && r2 != r2_end) {
-    if (!overlap) {
-      /* Find the left-most edge */
-      if (r1->x1 < r2->x1) {
-	x1 = r1->x1 - 1;
-      } else {
-	x1 = r2->x1 - 1;
-      }
-    }
-
-    MOZ_ASSERT((x1 >= (r1->x1 - 1)) || (x1 >= (r2->x1 - 1)));
-    if (r1->x1 < r2->x1) {
-      overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::BOTTOM, r1, r2, y, x1);
-    } else {
-      overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::TOP, r2, r1, y, x1);
-    }
+  auto band = std::begin(mBands);
+  auto bandFinal = std::end(mBands);
+  bandFinal--;
+  for (const Strip& strip : band->mStrips) {
+    visit(closure, VisitSide::LEFT, strip.left, band->top, strip.left, band->bottom);
+    visit(closure, VisitSide::RIGHT, strip.right, band->top, strip.right, band->bottom);
+    visit(closure, VisitSide::TOP, strip.left - 1, band->top, strip.right + 1, band->top);
   }
 
-  /* Finish up which ever row has remaining rects*/
-  if (r1 != r1_end) {
-    // top row
+  if (band != bandFinal) {
     do {
-      visit(closure, VisitSide::BOTTOM, x1, y, r1->x2 + 1, y);
-      r1++;
-      if (r1 == r1_end)
-	break;
-      x1 = r1->x1 - 1;
-    } while (true);
-  } else if (r2 != r2_end) {
-    // bottom row
-    do {
-      visit(closure, VisitSide::TOP, x1, y, r2->x2 + 1, y);
-      r2++;
-      if (r2 == r2_end)
-	break;
-      x1 = r2->x1 - 1;
-    } while (true);
+      Band& topBand = *band;
+      band++;
+
+      for (const Strip& strip : band->mStrips) {
+        visit(closure, VisitSide::LEFT, strip.left, band->top, strip.left, band->bottom);
+        visit(closure, VisitSide::RIGHT, strip.right, band->top, strip.right, band->bottom);
+      }
+
+      if (band->top == topBand.bottom) {
+        // Two bands touching each other vertically.
+        Band& bottomBand = *band;
+        auto topStrip = std::begin(topBand.mStrips);
+        auto bottomStrip = std::begin(bottomBand.mStrips);
+
+        int y = topBand.bottom;
+
+        // State from this point on along the vertical edge:
+        // 0 - Empty
+        // 1 - Touched by top rect
+        // 2 - Touched by bottom rect
+        // 3 - Touched on both sides
+        int state;
+        const int TouchedByNothing = 0;
+        const int TouchedByTop = 1;
+        const int TouchedByBottom = 2;
+        // We always start with nothing.
+        int oldState = TouchedByNothing;
+        // Last state change, adjusted by -1 if the last state change was
+        // a change away from 0.
+        int lastX = std::min(topStrip->left, bottomStrip->left) - 1;
+
+        // Current edge being considered for top and bottom, 0 - left, 1 - right.
+        bool topEdgeIsLeft = true;
+        bool bottomEdgeIsLeft = true;
+        while (topStrip != std::end(topBand.mStrips) && bottomStrip != std::end(bottomBand.mStrips)) {
+          int topPos;
+          int bottomPos;
+          if (topEdgeIsLeft) {
+            topPos = topStrip->left;
+          } else {
+            topPos = topStrip->right;
+          }
+          if (bottomEdgeIsLeft) {
+            bottomPos = bottomStrip->left;
+          } else {
+            bottomPos = bottomStrip->right;
+          }
+
+          int currentX = std::min(topPos, bottomPos);
+          if (topPos < bottomPos) {
+            if (topEdgeIsLeft) {
+              state = oldState | TouchedByTop;
+            } else {
+              state = oldState ^ TouchedByTop;
+              topStrip++;
+            }
+            topEdgeIsLeft = !topEdgeIsLeft;
+          } else if (bottomPos < topPos) {
+            if (bottomEdgeIsLeft) {
+              state = oldState | TouchedByBottom;
+            } else {
+              state = oldState ^ TouchedByBottom;
+              bottomStrip++;
+            }
+            bottomEdgeIsLeft = !bottomEdgeIsLeft;
+          } else {
+            // bottomPos == topPos
+            state = TouchedByNothing;
+            if (bottomEdgeIsLeft) {
+              state = TouchedByBottom;
+            } else {
+              bottomStrip++;
+            }
+            if (topEdgeIsLeft) {
+              state |= TouchedByTop;
+            } else {
+              topStrip++;
+            }
+            topEdgeIsLeft = !topEdgeIsLeft;
+            bottomEdgeIsLeft = !bottomEdgeIsLeft;
+          }
+
+          MOZ_ASSERT(state != oldState);
+          if (oldState == TouchedByNothing) {
+            // We had nothing before, make sure the left edge will be padded.
+            lastX = currentX - 1;
+          } else if (oldState == TouchedByTop) {
+            if (state == TouchedByNothing) {
+              visit(closure, VisitSide::BOTTOM, lastX, y, currentX + 1, y);
+            } else {
+              visit(closure, VisitSide::BOTTOM, lastX, y, currentX, y);
+              lastX = currentX;
+            }
+          } else if (oldState == TouchedByBottom) {
+            if (state == TouchedByNothing) {
+              visit(closure, VisitSide::TOP, lastX, y, currentX + 1, y);
+            } else {
+              visit(closure, VisitSide::TOP, lastX, y, currentX, y);
+              lastX = currentX;
+            }
+          } else {
+            lastX = currentX;
+          }
+          oldState = state;
+        }
+
+        MOZ_ASSERT(!state || (topEdgeIsLeft || bottomEdgeIsLeft));
+        if (topStrip != std::end(topBand.mStrips)) {
+          if (!topEdgeIsLeft) {
+            visit(closure, VisitSide::BOTTOM, lastX, y, topStrip->right + 1, y);
+            topStrip++;
+          }
+          while (topStrip != std::end(topBand.mStrips)) {
+            visit(closure, VisitSide::BOTTOM, topStrip->left - 1, y, topStrip->right + 1, y);
+            topStrip++;
+          }
+        } else if (bottomStrip != std::end(bottomBand.mStrips)) {
+          if (!bottomEdgeIsLeft) {
+            visit(closure, VisitSide::TOP, lastX, y, bottomStrip->right + 1, y);
+            bottomStrip++;
+          }
+          while (bottomStrip != std::end(bottomBand.mStrips)) {
+            visit(closure, VisitSide::TOP, bottomStrip->left - 1, y, bottomStrip->right + 1, y);
+            bottomStrip++;
+          }
+        }
+      } else {
+        for (const Strip& strip : topBand.mStrips) {
+          visit(closure, VisitSide::BOTTOM, strip.left - 1, topBand.bottom, strip.right + 1, topBand.bottom);
+        }
+        for (const Strip& strip : band->mStrips) {
+          visit(closure, VisitSide::TOP, strip.left - 1, band->top, strip.right + 1, band->top);
+        }
+      }
+    } while (band != bandFinal);
   }
 
-  return 0;
-}
-
-void nsRegion::VisitEdges (visit_fn visit, void *closure)
-{
-  pixman_box32_t *boxes;
-  int n;
-  boxes = pixman_region32_rectangles(&mImpl, &n);
-
-  // if we have no rectangles then we're done
-  if (!n)
-    return;
-
-  pixman_box32_t *end = boxes + n;
-  pixman_box32_t *topRectsEnd = boxes + 1;
-  pixman_box32_t *topRects = boxes;
-
-  // find the end of the first span of rectangles
-  while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
-    topRectsEnd++;
+  for (const Strip& strip : band->mStrips) {
+    visit(closure, VisitSide::BOTTOM, strip.left - 1, band->bottom, strip.right + 1, band->bottom);
   }
-
-  // In order to properly handle convex corners we always visit the sides first
-  // that way when we visit the corners we can pad using the value from the sides
-  VisitSides(visit, closure, topRects, topRectsEnd);
-
-  VisitAbove(visit, closure, topRects, topRectsEnd);
-
-  pixman_box32_t *bottomRects = topRects;
-  pixman_box32_t *bottomRectsEnd = topRectsEnd;
-  if (topRectsEnd != end) {
-    do {
-      // find the next row of rects
-      bottomRects = topRectsEnd;
-      bottomRectsEnd = topRectsEnd + 1;
-      while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
-        bottomRectsEnd++;
-      }
-
-      VisitSides(visit, closure, bottomRects, bottomRectsEnd);
-
-      if (topRects->y2 == bottomRects->y1) {
-        VisitInbetween(visit, closure, topRects, topRectsEnd,
-                                       bottomRects, bottomRectsEnd);
-      } else {
-        VisitBelow(visit, closure, topRects, topRectsEnd);
-        VisitAbove(visit, closure, bottomRects, bottomRectsEnd);
-      }
-
-      topRects = bottomRects;
-      topRectsEnd = bottomRectsEnd;
-    } while (bottomRectsEnd != end);
-  }
-
-  // the bottom of the region doesn't touch anything else so we
-  // can always visit it at the end
-  VisitBelow(visit, closure, bottomRects, bottomRectsEnd);
 }
 
 
 void nsRegion::SimplifyInward (uint32_t aMaxRects)
 {
   NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
 
   if (GetNumRects() <= aMaxRects)
@@ -564,49 +444,37 @@ 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);
-
-  pixman_region32_fini(&mImpl);
-  mImpl = region;
+  *this = std::move(newRegion);
   return *this;
 }
 
 nsRegion& nsRegion::ScaleInverseRoundOut (float aXScale, float aYScale)
 {
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
-  for (int i=0; i<n; i++) {
-    nsRect rect = BoxToRect(boxes[i]);
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = iter.Get();
     rect.ScaleInverseRoundOut(aXScale, aYScale);
-    boxes[i] = RectToBox(rect);
+    newRegion.AddRect(rect);
   }
 
-  pixman_region32_t region;
-  // This will union all of the rectangles and runs in about O(n lg(n))
-  pixman_region32_init_rects(&region, boxes, n);
-
-  pixman_region32_fini(&mImpl);
-  mImpl = region;
+  *this = std::move(newRegion);
   return *this;
 }
 
 static mozilla::gfx::IntRect
 TransformRect(const mozilla::gfx::IntRect& aRect, const mozilla::gfx::Matrix4x4& aTransform)
 {
     if (aRect.IsEmpty()) {
         return mozilla::gfx::IntRect();
@@ -621,102 +489,71 @@ TransformRect(const mozilla::gfx::IntRec
         return mozilla::gfx::IntRect();
     }
 
     return intRect;
 }
 
 nsRegion& nsRegion::Transform (const mozilla::gfx::Matrix4x4 &aTransform)
 {
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
-  for (int i=0; i<n; i++) {
-    nsRect rect = BoxToRect(boxes[i]);
-    boxes[i] = RectToBox(nsIntRegion::ToRect(TransformRect(nsIntRegion::FromRect(rect), aTransform)));
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = nsIntRegion::ToRect(TransformRect(nsIntRegion::FromRect(iter.Get()), aTransform));
+    newRegion.AddRect(rect);
   }
 
-  pixman_region32_t region;
-  // This will union all of the rectangles and runs in about O(n lg(n))
-  pixman_region32_init_rects(&region, boxes, n);
-
-  pixman_region32_fini(&mImpl);
-  mImpl = region;
+  *this = std::move(newRegion);
   return *this;
 }
 
 
 nsRegion nsRegion::ScaleToOtherAppUnitsRoundOut (int32_t aFromAPP, int32_t aToAPP) const
 {
   if (aFromAPP == aToAPP) {
     return *this;
   }
-
-  nsRegion region = *this;
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(&region.mImpl, &n);
-  for (int i=0; i<n; i++) {
-    nsRect rect = BoxToRect(boxes[i]);
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = iter.Get();
     rect = rect.ScaleToOtherAppUnitsRoundOut(aFromAPP, aToAPP);
-    boxes[i] = RectToBox(rect);
+    newRegion.AddRect(rect);
   }
 
-  pixman_region32_t pixmanRegion;
-  // This will union all of the rectangles and runs in about O(n lg(n))
-  pixman_region32_init_rects(&pixmanRegion, boxes, n);
-
-  pixman_region32_fini(&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]);
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = iter.Get();
     rect = rect.ScaleToOtherAppUnitsRoundIn(aFromAPP, aToAPP);
-    boxes[i] = RectToBox(rect);
+    newRegion.AddRect(rect);
   }
 
-  pixman_region32_t pixmanRegion;
-  // This will union all of the rectangles and runs in about O(n lg(n))
-  pixman_region32_init_rects(&pixmanRegion, boxes, n);
-
-  pixman_region32_fini(&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 +573,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 +597,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.IsEmpty()) {
+    nsIntRect rect = mBounds.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
+    return nsIntRegion(rect);
+  }
 
   nsIntRegion intRegion;
-  if (n) {
-    nsRect first = BoxToRect(boxes[0]);
-    mozilla::gfx::IntRect firstDeviceRect =
-      first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
+  RectIterator iter = RectIterator(*this);
+
+  nsRect first = iter.Get();
 
-    for (int i=1; i<n; i++) {
-      nsRect rect = nsRect(boxes[i].x1, boxes[i].y1,
-	  boxes[i].x2 - boxes[i].x1,
-	  boxes[i].y2 - boxes[i].y1);
-      mozilla::gfx::IntRect deviceRect =
-	rect.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
+  mozilla::gfx::IntRect firstDeviceRect =
+    first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
+
+  for (iter.Next(); !iter.Done(); iter.Next()) {
+    nsRect rect = iter.Get();
+    mozilla::gfx::IntRect deviceRect =
+                          rect.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
 
-      if (rect.Y() <= first.YMost()) {
-	if (rect.XMost() == first.X() && rect.YMost() <= first.YMost()) {
-	  // rect is touching on the left edge of the first rect and contained within
-	  // the length of its left edge
-	  deviceRect.SetRightEdge(firstDeviceRect.X());
-	} else if (rect.X() == first.XMost() && rect.YMost() <= first.YMost()) {
-	  // rect is touching on the right edge of the first rect and contained within
-	  // the length of its right edge
-	  deviceRect.SetLeftEdge(firstDeviceRect.XMost());
-	} else if (rect.Y() == first.YMost()) {
-	  // The bottom of the first rect is on the same line as the top of rect, but
-	  // they aren't necessarily contained.
-	  if (rect.X() <= first.X() && rect.XMost() >= first.XMost()) {
-	    // The top of rect contains the bottom of the first rect
-	    firstDeviceRect.SetBottomEdge(deviceRect.Y());
-	  } else if (rect.X() >= first.X() && rect.XMost() <= first.XMost()) {
-	    // The bottom of the first contains the top of rect
-	    deviceRect.SetTopEdge(firstDeviceRect.YMost());
-	  }
-	}
+    if (rect.Y() <= first.YMost()) {
+      if (rect.XMost() == first.X() && rect.YMost() <= first.YMost()) {
+        // rect is touching on the left edge of the first rect and contained within
+        // the length of its left edge
+        deviceRect.SetRightEdge(firstDeviceRect.X());
+      } else if (rect.X() == first.XMost() && rect.YMost() <= first.YMost()) {
+        // rect is touching on the right edge of the first rect and contained within
+        // the length of its right edge
+        deviceRect.SetLeftEdge(firstDeviceRect.XMost());
+      } else if (rect.Y() == first.YMost()) {
+        // The bottom of the first rect is on the same line as the top of rect, but
+        // they aren't necessarily contained.
+        if (rect.X() <= first.X() && rect.XMost() >= first.XMost()) {
+          // The top of rect contains the bottom of the first rect
+          firstDeviceRect.SetBottomEdge(deviceRect.Y());
+        } else if (rect.X() >= first.X() && rect.XMost() <= first.XMost()) {
+          // The bottom of the first contains the top of rect
+          deviceRect.SetTopEdge(firstDeviceRect.YMost());
+        }
       }
-
-      boxes[i] = RectToBox(deviceRect);
     }
 
-    boxes[0] = RectToBox(firstDeviceRect);
+    intRegion.OrWith(deviceRect);
+  }
 
-    pixman_region32_fini(&intRegion.mImpl.mImpl);
-    // This will union all of the rectangles and runs in about O(n lg(n))
-    pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n);
-  }
+  intRegion.OrWith(firstDeviceRect);
   return intRegion;
-
 }
 
 // A cell's "value" is a pair consisting of
 // a) the area of the subrectangle it corresponds to, if it's in
 // aContainingRect and in the region, 0 otherwise
 // b) the area of the subrectangle it corresponds to, if it's in the region,
 // 0 otherwise
 // Addition, subtraction and identity are defined on these values in the
@@ -1124,25 +944,41 @@ nsRect nsRegion::GetLargestRectangle (co
   }
 
   return bestRect;
 }
 
 std::ostream& operator<<(std::ostream& stream, const nsRegion& m) {
   stream << "[";
 
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(const_cast<pixman_region32_t*>(&m.mImpl), &n);
-  for (int i=0; i<n; i++) {
-    if (i != 0) {
+  bool first = true;
+  for (auto iter = m.RectIter(); !iter.Done(); iter.Next()) {
+    if (!first) {
       stream << "; ";
+    } else {
+      first = true;
     }
-    stream << boxes[i].x1 << "," << boxes[i].y1 << "," << boxes[i].x2 << "," << boxes[i].y2;
+    const nsRect& rect = iter.Get();
+    stream << rect.X() << "," << rect.Y() << "," << rect.XMost() << "," << rect.YMost();
   }
 
   stream << "]";
   return stream;
 }
 
+void
+nsRegion::OutputToStream(std::string aObjName, std::ostream& stream) const
+{
+  auto iter = RectIter();
+  nsRect r = iter.Get();
+  stream << "nsRegion " << aObjName << "(nsRect(" << r.X() << ", " << r.Y() << ", " << r.Width() << ", " << r.Height() << "));\n";
+  iter.Next();
+
+  for (; !iter.Done(); iter.Next()) {
+    nsRect r = iter.Get();
+    stream << aObjName << ".OrWith(nsRect(" << r.X() << ", " << r.Y() << ", " << r.Width() << ", " << r.Height() << "));\n";
+  }
+}
+
 nsCString
 nsRegion::ToString() const {
   return nsCString(mozilla::ToString(*this).c_str());
 }
--- a/gfx/src/nsRegion.h
+++ b/gfx/src/nsRegion.h
@@ -18,19 +18,27 @@
 #include "nsRect.h"                     // for mozilla::gfx::IntRect, nsRect
 #include "nsMargin.h"                   // for nsIntMargin
 #include "nsRegionFwd.h"                // for nsIntRegion
 #include "nsString.h"                   // for nsCString
 #include "xpcom-config.h"               // for CPP_THROW_NEW
 #include "mozilla/ArrayView.h"          // for ArrayView
 #include "mozilla/Move.h"               // for mozilla::Move
 #include "mozilla/gfx/MatrixFwd.h"      // for mozilla::gfx::Matrix4x4
+#include "mozilla/gfx/Logging.h"
+#include "nsTArray.h"
 
 #include "pixman.h"
 
+// Uncomment this line to get additional integrity checking.
+//#define DEBUG_REGIONS
+#ifdef DEBUG_REGIONS
+#include <sstream>
+#endif
+
 /* For information on the internal representation look at pixman-region.c
  *
  * This replaces an older homebrew implementation of nsRegion. The
  * representation used here may use more rectangles than nsRegion however, the
  * representation is canonical.  This means that there's no need for an
  * Optimize() method because for a paticular region there is only one
  * representation. This means that nsIntRegion will have more predictable
  * performance characteristics than the old nsRegion and should not become
@@ -42,129 +50,704 @@
 
 enum class VisitSide {
 	TOP,
 	BOTTOM,
 	LEFT,
 	RIGHT
 };
 
+namespace details {
+struct Band;
+}
+
+template<>
+struct nsTArray_CopyChooser<details::Band>
+{
+  typedef nsTArray_CopyWithConstructors<details::Band> Type;
+}; 
+
+namespace details {
+
+template<typename T, typename E>
+class UncheckedArray : public T
+{
+public:
+  using T::Elements;
+  using T::Length;
+
+  E & operator[](size_t aIndex) { return Elements()[aIndex]; }
+  const E& operator[](size_t aIndex) const { return Elements()[aIndex]; }
+
+  using iterator = E* ;
+  using const_iterator = const E*;
+
+  iterator begin() { return iterator(Elements()); }
+  const_iterator begin() const { return const_iterator(Elements()); }
+  const_iterator cbegin() const { return begin(); }
+  iterator end() { return iterator(Elements() + Length()); }
+  const_iterator end() const { return const_iterator(Elements() + Length()); }
+  const_iterator cend() const { return end(); }
+};
+
+struct Strip
+{
+  // Default constructor should never be called, but is required for
+  // vector::resize to compile.
+  Strip() { MOZ_CRASH(); }
+  Strip(int32_t aLeft, int32_t aRight) : left(aLeft), right(aRight) {}
+
+  bool operator != (const Strip& aOther) const
+  {
+    return left != aOther.left || right != aOther.right;
+  }
+
+  uint32_t Size() const
+  {
+    return right - left;
+  }
+
+  int32_t left;
+  int32_t right;
+};
+
+struct Band
+{
+  using Strip = details::Strip;
+#ifndef DEBUG
+  using StripArray = details::UncheckedArray<AutoTArray<Strip, 2>, Strip>;
+#else
+  using StripArray = AutoTArray<Strip, 2>;
+#endif
+
+  MOZ_IMPLICIT Band(const nsRect& aRect)
+    : top(aRect.Y()), bottom(aRect.YMost())
+  {
+    mStrips.AppendElement(Strip{ aRect.X(), aRect.XMost() });
+  }
+
+  Band(const Band& aOther)
+    : top(aOther.top), bottom(aOther.bottom)
+    , mStrips(aOther.mStrips)
+  {}
+
+  void InsertStrip(const Strip& aStrip)
+  {
+    for (size_t i = 0; i < mStrips.Length(); i++) {
+      Strip& strip = mStrips[i];
+      if (strip.left > aStrip.right) {
+        // Current strip is beyond aStrip, insert aStrip before.
+        mStrips.InsertElementAt(i, aStrip);
+        return;
+      }
+
+      if (strip.right < aStrip.left) {
+        // Current strip is before aStrip, try the next.
+        continue;
+      }
+
+      // Current strip intersects with aStrip, extend to the lext.
+      strip.left = std::min(strip.left, aStrip.left);
+
+      if (strip.right >= aStrip.right) {
+        // Current strip extends beyond aStrip, done.
+        return;
+      }
+
+      size_t next = i;
+      next++;
+      // Consume any subsequent strips intersecting with aStrip.
+      while (next < mStrips.Length() && mStrips[next].left <= aStrip.right) {
+        strip.right = mStrips[next].right;
+
+        mStrips.RemoveElementAt(next);
+      }
+
+      // Extend the strip in case the aStrip goes on beyond it.
+      strip.right = std::max(strip.right, aStrip.right);
+      return;
+    }
+    mStrips.AppendElement(aStrip);
+  }
+
+  void SubStrip(const Strip& aStrip)
+  {
+    for (size_t i = 0; i < mStrips.Length(); i++) {
+      Strip& strip = mStrips[i];
+      if (strip.left > aStrip.right) {
+        // Strip is entirely to the right of aStrip. Done.
+        return;
+      }
+
+      if (strip.right < aStrip.left) {
+        // Strip is entirely to the left of aStrip. Move on.
+        continue;
+      }
+
+      if (strip.left < aStrip.left) {
+        if (strip.right <= aStrip.right) {
+          strip.right = aStrip.left;
+          // This strip lies to the left of the start of aStrip.
+          continue;
+        }
+
+        // aStrip is completely contained by this strip.
+        Strip newStrip(aStrip.right, strip.right);
+        strip.right = aStrip.left;
+        if (i < mStrips.Length()) {
+          i++;
+          mStrips.InsertElementAt(i, newStrip);
+        } else {
+          mStrips.AppendElement(newStrip);
+        }
+        return;
+      }
+
+      // This strip lies to the right of the start of aStrip.
+      if (strip.right <= aStrip.right) {
+        // aStrip completely contains this strip.
+        mStrips.RemoveElementAt(i);
+        // Make sure we evaluate the strip now at i. This loop will increment.
+        i--;
+        continue;
+      }
+      strip.left = aStrip.right;
+      return;
+    }
+  }
+
+  bool Intersects(const Strip& aStrip) const
+  {
+    for (const Strip& strip : mStrips) {
+      if (strip.left >= aStrip.right) {
+        return false;
+      }
+
+      if (strip.right <= aStrip.left) {
+        continue;
+      }
+
+      return true;
+    }
+    return false;
+  }
+
+  bool IntersectStripBounds(Strip& aStrip) const
+  {
+    bool intersected = false;
+
+    int32_t rightMost;
+    for (const Strip& strip : mStrips) {
+      if (strip.left > aStrip.right) {
+        break;
+      }
+
+      if (strip.right <= aStrip.left) {
+        continue;
+      }
+
+      if (!intersected) {
+        // First intersection, this is where the left side begins.
+        aStrip.left = std::max(aStrip.left, strip.left);
+      }
+
+      intersected = true;
+      // Expand to the right for each intersecting strip found.
+      rightMost = std::min(strip.right, aStrip.right);
+    }
+
+    if (intersected) {
+      aStrip.right = rightMost;
+    }
+    else {
+      aStrip.right = aStrip.left = 0;
+    }
+    return intersected;
+  }
+
+  bool ContainsStrip(const Strip& aStrip) const
+  {
+    for (const Strip& strip : mStrips) {
+      if (strip.left > aStrip.left) {
+        return false;
+      }
+
+      if (strip.right >= aStrip.right) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  bool EqualStrips(const Band& aBand) const
+  {
+    if (mStrips.Length() != aBand.mStrips.Length()) {
+      return false;
+    }
+
+    for (auto iter1 = mStrips.begin(), iter2 = aBand.mStrips.begin();
+      iter1 != mStrips.end(); iter1++, iter2++)
+    {
+      if (*iter1 != *iter2) {
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  void IntersectStrip(const Strip& aStrip)
+  {
+    size_t i = 0;
+
+    while (i < mStrips.Length()) {
+      Strip& strip = mStrips[i];
+      if (strip.right <= aStrip.left) {
+        mStrips.RemoveElementAt(i);
+        continue;
+      }
+
+      if (strip.left >= aStrip.right) {
+        mStrips.TruncateLength(i);
+        return;
+      }
+
+      strip.left = std::max(aStrip.left, strip.left);
+      strip.right = std::min(aStrip.right, strip.right);
+      i++;
+    }
+  }
+
+  void IntersectStrips(const Band& aOther)
+  {
+    auto iter = mStrips.begin();
+    auto iterOther = aOther.mStrips.begin();
+
+    StripArray newStrips;
+
+    // This function finds the intersection between two sets of strips.
+    while (true) {
+      while (true) {
+        while (iter != mStrips.end() && iter->right <= iterOther->left) {
+          // Increment our current strip until it ends beyond aOther's current strip.
+          iter++;
+        }
+
+        if (iter == mStrips.end()) {
+          // End of our strips. Done.
+          break;
+        }
+
+        while (iterOther != aOther.mStrips.end() && iterOther->right <= iter->left) {
+          // Increment aOther's current strip until it lies beyond our current strip.
+          iterOther++;
+        }
+
+        if (iterOther == aOther.mStrips.end()) {
+          // End of aOther's strips. Done.
+          break;
+        }
+
+        if (iterOther->left < iter->right) {
+          // Intersection!
+          break;
+        }
+      }
+
+      if (iter == mStrips.end() || iterOther == aOther.mStrips.end()) {
+        break;
+      }
+
+      newStrips.AppendElement(Strip(std::max(iter->left, iterOther->left), std::min(iterOther->right, iter->right)));
+
+      if (iterOther->right < iter->right) {
+        iterOther++;
+        if (iterOther == aOther.mStrips.end()) {
+          break;
+        }
+      } else {
+        iter++;
+      }
+    }
+
+    mStrips = newStrips;
+  }
+
+  int32_t top;
+  int32_t bottom;
+  StripArray mStrips;
+};
+}
+
 class nsRegion
 {
 public:
+  using Band = details::Band;
+  using Strip = details::Strip;
+#ifndef DEBUG
+  using BandArray = details::UncheckedArray<nsTArray<Band>, Band>;
+  using StripArray = details::UncheckedArray<AutoTArray<Strip, 2>, Strip>;
+#else
+  using BandArray = nsTArray<Band>;
+  using StripArray = AutoTArray<Strip, 2>;
+#endif
+
   typedef nsRect RectType;
   typedef nsPoint PointType;
   typedef nsMargin MarginType;
 
-  nsRegion () { pixman_region32_init(&mImpl); }
-  MOZ_IMPLICIT nsRegion (const nsRect& aRect) { pixman_region32_init_rect(&mImpl,
-                                                                          aRect.X(),
-                                                                          aRect.Y(),
-                                                                          aRect.Width(),
-                                                                          aRect.Height()); }
-  explicit nsRegion (mozilla::gfx::ArrayView<pixman_box32_t> aRects)
+  nsRegion() { }
+  MOZ_IMPLICIT nsRegion(const nsRect& aRect) {
+    mBounds = aRect;
+  }
+  explicit nsRegion(mozilla::gfx::ArrayView<pixman_box32_t> aRects)
   {
-    pixman_region32_init_rects(&mImpl, aRects.Data(), aRects.Length());
+    for (uint32_t i = 0; i < aRects.Length(); i++) {
+      AddRect(BoxToRect(aRects[i]));
+    }
   }
-  nsRegion (const nsRegion& aRegion) { pixman_region32_init(&mImpl); pixman_region32_copy(&mImpl,aRegion.Impl()); }
-  nsRegion (nsRegion&& aRegion) { mImpl = aRegion.mImpl; pixman_region32_init(&aRegion.mImpl); }
-  nsRegion& operator = (nsRegion&& aRegion) {
-      pixman_region32_fini(&mImpl);
-      mImpl = aRegion.mImpl;
-      pixman_region32_init(&aRegion.mImpl);
-      return *this;
+
+  nsRegion(const nsRegion& aRegion) { Copy(aRegion); }
+  nsRegion(nsRegion&& aRegion) { mBands.SwapElements(aRegion.mBands); mBounds = aRegion.mBounds; aRegion.SetEmpty(); }
+  nsRegion& operator =(nsRegion&& aRegion) {
+    mBands.SwapElements(aRegion.mBands);
+    mBounds = aRegion.mBounds;
+    aRegion.SetEmpty();
+    return *this;
   }
- ~nsRegion () { pixman_region32_fini(&mImpl); }
-  nsRegion& operator = (const nsRect& aRect) { Copy (aRect); return *this; }
-  nsRegion& operator = (const nsRegion& aRegion) { Copy (aRegion); return *this; }
+  nsRegion& operator =(const nsRect& aRect) { Copy(aRect); return *this; }
+  nsRegion& operator =(const nsRegion& aRegion) { Copy(aRegion); return *this; }
   bool operator==(const nsRegion& aRgn) const
   {
     return IsEqual(aRgn);
   }
   bool operator!=(const nsRegion& aRgn) const
   {
     return !(*this == aRgn);
   }
 
   friend std::ostream& operator<<(std::ostream& stream, const nsRegion& m);
+  void OutputToStream(std::string aObjName, std::ostream& stream) const;
 
-  void Swap(nsRegion* aOther)
+  static
+    nsresult InitStatic()
   {
-    pixman_region32_t tmp = mImpl;
-    mImpl = aOther->mImpl;
-    aOther->mImpl = tmp;
+    return NS_OK;
+  }
+
+  static
+    void ShutdownStatic() {}
+
+private:
+#ifdef DEBUG_REGIONS
+  class OperationStringGenerator
+  {
+  public:
+    virtual ~OperationStringGenerator() {}
+
+    virtual void OutputOp() = 0;
+  };
+#endif
+public:
+
+  void AssertStateInternal() const;
+  void AssertState() const {
+#ifdef DEBUG_REGIONS
+    AssertStateInternal();
+#endif
   }
 
-  void AndWith(const nsRegion& aOther)
-  {
-    And(*this, aOther);
-  }
-  void AndWith(const nsRect& aOther)
+  nsRegion& AndWith(const nsRegion& aRegion)
   {
-    And(*this, aOther);
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorAndWith : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorAndWith(nsRegion& aRegion, const nsRegion& aOtherRegion)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mOtherRegion(aOtherRegion)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorAndWith()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r1", stream);
+        mOtherRegion.OutputToStream("r2", stream);
+        stream << "r1.AndWith(r2);\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsRegion mOtherRegion;
+    };
+
+    OperationStringGeneratorAndWith opGenerator(*this, aRegion);
+#endif
+    if (mBounds.IsEmpty()) {
+      // Region is empty, stays empty.
+      return *this;
+    }
+
+    if (aRegion.IsEmpty()) {
+      SetEmpty();
+      return *this;
+    }
+
+    if (aRegion.mBands.IsEmpty()) {
+      // Other region is a rect.
+      return AndWith(aRegion.mBounds);
+    }
+
+    if (mBands.IsEmpty()) {
+      mBands.AppendElement(mBounds);
+    }
+
+    size_t idx = 0;
+    size_t idxOther = 0;
+
+    BandArray newBands;
+
+    // This algorithm essentially forms a new list of bands, by iterating over
+    // both regions' lists of band simultaneously, and building a new band
+    // wherever the two regions intersect.
+    while (true) {
+      while (true) {
+        while (idx != mBands.Length() && mBands[idx].bottom <= aRegion.mBands[idxOther].top) {
+          // Increment our current band until it ends beyond aOther's current band.
+          idx++;
+        }
+
+        if (idx == mBands.Length()) {
+          // This region is out of bands, the other region's future bands are ignored.
+          break;
+        }
+
+        while (idxOther != aRegion.mBands.Length() && aRegion.mBands[idxOther].bottom <= mBands[idx].top) {
+          // Increment aOther's current band until it ends beyond our current band.
+          idxOther++;
+        }
+
+        if (idxOther == aRegion.mBands.Length()) {
+          // The other region's bands are all processed, all our future bands are ignored.
+          break;
+        }
+
+        if (aRegion.mBands[idxOther].top < mBands[idx].bottom) {
+          // We know the other band's bottom lies beyond our band's top because
+          // otherwise we would've incremented above. Intersecting bands found.
+          break;
+        }
+      }
+
+      if (idx == mBands.Length() || idxOther == aRegion.mBands.Length()) {
+        // The above loop executed a break because we're done.
+        break;
+      }
+
+      Band newBand(mBands[idx]);
+      // The new band is the intersection of the two current bands from both regions.
+      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.Length()) {
+        // The intersecting area of the bands had overlapping strips, if it is
+        // identical to the band above it merge, otherwise append.
+        if (newBands.Length() && newBands.LastElement().bottom == newBand.top &&
+          newBands.LastElement().EqualStrips(newBand)) {
+          newBands.LastElement().bottom = newBand.bottom;
+        } else {
+          newBands.AppendElement(newBand);
+        }
+      }
+
+      if (aRegion.mBands[idxOther].bottom < mBands[idx].bottom) {
+        idxOther++;
+        if (idxOther == aRegion.mBands.Length()) {
+          // Since we will access idxOther the next iteration, check if we're not done.
+          break;
+        }
+      } else {
+        // No need to check here since we do at the beginning of the next iteration.
+        idx++;
+      }
+    }
+
+    mBands = newBands;
+    if (!newBands.Length()) {
+      mBounds = nsRect();
+    } else {
+      mBounds = CalculateBounds();
+    }
+
+    EnsureSimplified();
+    AssertState();
+    return *this;
   }
-  nsRegion& And(const nsRegion& aRgn1,   const nsRegion& aRgn2)
+
+  nsRegion& AndWith(const nsRect& aRect)
   {
-    pixman_region32_intersect(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorAndWith : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorAndWith(nsRegion& aRegion, const nsRect& aRect)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorAndWith()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r", stream);
+        stream << "r.AndWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsRect mRect;
+    };
+
+    OperationStringGeneratorAndWith opGenerator(*this, aRect);
+#endif
+    if (aRect.IsEmpty()) {
+      SetEmpty();
+    }
+
+    if (mBands.IsEmpty()) {
+      mBounds = mBounds.Intersect(aRect);
+      return *this;
+    }
+
+    size_t idx = 0;
+
+    // This removes all bands that do not intersect with aRect, and intersects
+    // the remaining ones with aRect.
+    while (idx != mBands.Length()) {
+      if (mBands[idx].bottom <= aRect.Y()) {
+        MOZ_ASSERT(idx == 0);
+        mBands.RemoveElementAt(0);
+        continue;
+      }
+
+      if (mBands[idx].top >= aRect.YMost()) {
+        mBands.RemoveElementAt(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.Length()) {
+        mBands.RemoveElementAt(idx);
+      } else {
+        CompressBefore(idx);
+        idx++;
+      }
+    }
+
+    if (mBands.Length()) {
+      mBounds = CalculateBounds();
+    } else {
+      mBounds.SetEmpty();
+    }
+    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);
@@ -177,70 +760,313 @@ 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;
+  }
+
+private:
+  // Internal helper for executing subtraction.
+  void RunSubtraction(const nsRect& aRect)
+  {
+    Strip rectStrip(aRect.X(), aRect.XMost());
+
+    size_t idx = 0;
+
+    while (idx < mBands.Length()) {
+      if (mBands[idx].top >= aRect.YMost()) {
+        return;
+      }
+
+      if (mBands[idx].bottom <= aRect.Y()) {
+        // This band is entirely before aRect, move on.
+        idx++;
+        continue;
+      }
+
+      if (!mBands[idx].Intersects(Strip(aRect.X(), aRect.XMost()))) {
+        // This band does not intersect aRect horizontally. Move on.
+        idx++;
+        continue;
+      }
+
+      // This band intersects with aRect.
+
+      if (mBands[idx].top < aRect.Y()) {
+        // This band starts above the start of aRect, split the band into two
+        // along the intersection, and continue to the next iteration to process
+        // the one that now intersects exactly.
+        auto above = mBands.InsertElementAt(idx, Band(mBands[idx]));
+        above->bottom = aRect.Y();
+        idx++;
+        mBands[idx].top = aRect.Y();
+        // Continue to run the loop for the next band.
+        continue;
+      }
+
+      if (mBands[idx].bottom <= aRect.YMost()) {
+        // This band ends before the end of aRect.
+        mBands[idx].SubStrip(rectStrip);
+        if (mBands[idx].mStrips.Length()) {
+          CompressAdjacentBands(idx);
+        }
+        else {
+          mBands.RemoveElementAt(idx);
+        }
+        continue;
+      }
+
+      // This band extends beyond aRect.
+      Band newBand = mBands[idx];
+      newBand.SubStrip(rectStrip);
+      newBand.bottom = aRect.YMost();
+      mBands[idx].top = aRect.YMost();
+
+      if (newBand.mStrips.Length()) {
+        if (idx && mBands[idx - 1].bottom == newBand.top && newBand.EqualStrips(mBands[idx - 1])) {
+          mBands[idx - 1].bottom = aRect.YMost();
+        }
+        else {
+          mBands.InsertElementAt(idx, newBand);
+        }
+      }
+
+      return;
+    }
+  }
+
+public:
+  nsRegion& SubWith(const nsRect& aRect) {
+    if (!mBounds.Intersects(aRect)) {
+      return *this;
+    }
+
+    if (aRect.Contains(mBounds)) {
+      SetEmpty();
+      return *this;
+    }
+
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorSubWith : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorSubWith(nsRegion& aRegion, const nsRect& aRect)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorSubWith()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r", stream);
+        stream << "r.SubWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsRect mRect;
+    };
+
+    OperationStringGeneratorSubWith opGenerator(*this, aRect);
+#endif
+
+    if (mBands.IsEmpty()) {
+      mBands.AppendElement(Band(mBounds));
+    }
+
+    RunSubtraction(aRect);
+
+    mBounds = CalculateBounds();
+    EnsureSimplified();
+    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.IsEmpty()) {
+      return mBounds.Contains(aX, aY);
+    }
+
+    auto iter = mBands.begin();
+
+    while (iter != mBands.end()) {
+      if (iter->bottom <= aY) {
+        iter++;
+        continue;
+      }
+
+      if (iter->top > aY) {
+        return false;
+      }
+
+      if (iter->ContainsStrip(Strip(aX, aX + 1))) {
+        return true;
+      }
+      return false;
+    }
+    return false;
   }
-  bool Contains (const nsRegion& aRgn) const;
-  bool Intersects (const nsRect& aRect) const;
-
-  void MoveBy (int32_t aXOffset, int32_t aYOffset)
+  bool Contains(const nsRect& aRect) const
   {
-    MoveBy (nsPoint (aXOffset, aYOffset));
+    if (aRect.IsEmpty()) {
+      return false;
+    }
+
+    if (mBands.IsEmpty()) {
+      return mBounds.Contains(aRect);
+    }
+
+    auto iter = mBands.begin();
+
+    while (iter != mBands.end()) {
+      if (iter->bottom <= aRect.Y()) {
+        iter++;
+        continue;
+      }
+
+      if (iter->top > aRect.Y()) {
+        return false;
+      }
+
+      // Now inside the rectangle.
+      if (!iter->ContainsStrip(Strip(aRect.X(), aRect.XMost()))) {
+        return false;
+      }
+
+      if (iter->bottom >= aRect.YMost()) {
+        return true;
+      }
+
+      int32_t lastY = iter->bottom;
+      iter++;
+      while (iter != mBands.end()) {
+        // Bands do not connect.
+        if (iter->top != lastY) {
+          return false;
+        }
+
+        if (!iter->ContainsStrip(Strip(aRect.X(), aRect.XMost()))) {
+          return false;
+        }
+
+        if (iter->bottom >= aRect.YMost()) {
+          return true;
+        }
+
+        lastY = iter->bottom;
+        iter++;
+      }
+    }
+    return false;
   }
-  void MoveBy (nsPoint aPt) { pixman_region32_translate(&mImpl, aPt.x, aPt.y); }
-  void SetEmpty ()
+
+  bool Contains(const nsRegion& aRgn) const;
+  bool Intersects(const nsRect& aRect) const;
+
+  void MoveBy(int32_t aXOffset, int32_t aYOffset)
+  {
+    MoveBy(nsPoint(aXOffset, aYOffset));
+  }
+  void MoveBy(nsPoint aPt)
   {
-    pixman_region32_clear(&mImpl);
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorMoveBy : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorMoveBy(nsRegion& aRegion, const nsPoint& aPoint)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mPoint(aPoint)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorMoveBy()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r", stream);
+        stream << "r.MoveBy(nsPoint(" << mPoint.x << ", " << mPoint.y << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsPoint mPoint;
+    };
+
+    OperationStringGeneratorMoveBy opGenerator(*this, aPt);
+#endif
+
+    mBounds.MoveBy(aPt);
+    for (Band& band : mBands) {
+      band.top += aPt.Y();
+      band.bottom += aPt.Y();
+      for (Strip& strip : band.mStrips) {
+        strip.left += aPt.X();
+        strip.right += aPt.X();
+      }
+    }
+    AssertState();
+  }
+  void SetEmpty()
+  {
+    mBands.Clear();
+    mBounds.SetEmpty();
   }
 
   nsRegion MovedBy(int32_t aXOffset, int32_t aYOffset) const
   {
     return MovedBy(nsPoint(aXOffset, aYOffset));
   }
   nsRegion MovedBy(const nsPoint& aPt) const
   {
@@ -260,197 +1086,427 @@ public:
 
   nsRegion Inflated(const nsMargin& aMargin) const
   {
     nsRegion copy(*this);
     copy.Inflate(aMargin);
     return copy;
   }
 
-  bool IsEmpty () const { return !pixman_region32_not_empty(Impl()); }
-  bool IsComplex () const { return GetNumRects() > 1; }
-  bool IsEqual (const nsRegion& aRegion) const
-  {
-    return pixman_region32_equal(Impl(), aRegion.Impl());
-  }
-  uint32_t GetNumRects () const
+  bool IsEmpty() const { return mBounds.IsEmpty(); }
+  bool IsComplex() const { return GetNumRects() > 1; }
+  bool IsEqual(const nsRegion& aRegion) const
   {
-    // Work around pixman bug. Sometimes pixman creates regions with 1 rect
-    // that's empty.
-    uint32_t result = pixman_region32_n_rects(Impl());
-    return (result == 1 && GetBounds().IsEmpty()) ? 0 : result;
+    if (mBands.IsEmpty() && aRegion.mBands.IsEmpty()) {
+      return mBounds.IsEqualInterior(aRegion.mBounds);
+    }
+
+    if (mBands.Length() != aRegion.mBands.Length()) {
+      return false;
+    }
+
+    for (auto iter1 = mBands.begin(), iter2 = aRegion.mBands.begin();
+      iter1 != mBands.end(); iter1++, iter2++)
+    {
+      if (!iter1->EqualStrips(*iter2)) {
+        return false;
+      }
+    }
+
+    return true;
   }
-  const nsRect GetBounds () const { return BoxToRect(mImpl.extents); }
-  uint64_t Area () const;
+
+  uint32_t GetNumRects() const
+  {
+    if (mBands.IsEmpty()) {
+      return mBounds.IsEmpty() ? 0 : 1;
+    }
+
+    uint32_t rects = 0;
+
+    for (const Band& band : mBands) {
+      rects += band.mStrips.Length();
+    }
+
+    return rects;
+  }
+  const nsRect GetBounds() const { return mBounds; }
+  uint64_t Area() const;
 
   /**
    * Return this region scaled to a different appunits per pixel (APP) ratio.
    * This applies nsRect::ScaleToOtherAppUnitsRoundOut/In to each rect of the region.
    * @param aFromAPP the APP to scale from
    * @param aToAPP the APP to scale to
    * @note this can turn an empty region into a non-empty region
    */
   MOZ_MUST_USE nsRegion
-    ScaleToOtherAppUnitsRoundOut (int32_t aFromAPP, int32_t aToAPP) const;
+    ScaleToOtherAppUnitsRoundOut(int32_t aFromAPP, int32_t aToAPP) const;
   MOZ_MUST_USE nsRegion
-    ScaleToOtherAppUnitsRoundIn (int32_t aFromAPP, int32_t aToAPP) const;
+    ScaleToOtherAppUnitsRoundIn(int32_t aFromAPP, int32_t aToAPP) const;
   nsRegion& ScaleRoundOut(float aXScale, float aYScale);
   nsRegion& ScaleInverseRoundOut(float aXScale, float aYScale);
-  nsRegion& Transform (const mozilla::gfx::Matrix4x4 &aTransform);
-  nsIntRegion ScaleToOutsidePixels (float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
-  nsIntRegion ScaleToInsidePixels (float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
-  nsIntRegion ScaleToNearestPixels (float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
-  nsIntRegion ToOutsidePixels (nscoord aAppUnitsPerPixel) const;
-  nsIntRegion ToNearestPixels (nscoord aAppUnitsPerPixel) const;
+  nsRegion& Transform(const mozilla::gfx::Matrix4x4 &aTransform);
+  nsIntRegion ScaleToOutsidePixels(float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
+  nsIntRegion ScaleToInsidePixels(float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
+  nsIntRegion ScaleToNearestPixels(float aXScale, float aYScale, nscoord aAppUnitsPerPixel) const;
+  nsIntRegion ToOutsidePixels(nscoord aAppUnitsPerPixel) const;
+  nsIntRegion ToNearestPixels(nscoord aAppUnitsPerPixel) const;
 
   /**
    * Gets the largest rectangle contained in the region.
    * @param aContainingRect if non-empty, we choose a rectangle that
    * maximizes the area intersecting with aContainingRect (and break ties by
    * then choosing the largest rectangle overall)
    */
-  nsRect GetLargestRectangle (const nsRect& aContainingRect = nsRect()) const;
+  nsRect GetLargestRectangle(const nsRect& aContainingRect = nsRect()) const;
 
   /**
    * Make sure the region has at most aMaxRects by adding area to it
    * if necessary. The simplified region will be a superset of the
    * original region. The simplified region's bounding box will be
    * the same as for the current region.
    */
-  void SimplifyOutward (uint32_t aMaxRects);
+  void SimplifyOutward(uint32_t aMaxRects);
   /**
    * Simplify the region by adding at most aThreshold area between spans of
    * rects.  The simplified region will be a superset of the original region.
    * The simplified region's bounding box will be the same as for the current
    * region.
    */
   void SimplifyOutwardByArea(uint32_t aThreshold);
   /**
    * Make sure the region has at most aMaxRects by removing area from
    * it if necessary. The simplified region will be a subset of the
    * original region.
    */
-  void SimplifyInward (uint32_t aMaxRects);
+  void SimplifyInward(uint32_t aMaxRects);
 
   /**
    * VisitEdges is a weird kind of function that we use for padding
    * out surfaces to prevent texture filtering artifacts.
    * It calls the visitFn callback for each of the exterior edges of
    * the regions. The top and bottom edges will be expanded 1 pixel
    * to the left and right if there's an outside corner. The order
    * the edges are visited is not guaranteed.
    *
    * visitFn has a side parameter that can be TOP,BOTTOM,LEFT,RIGHT
    * and specifies which kind of edge is being visited. x1, y1, x2, y2
    * are the coordinates of the line. (x1 == x2) || (y1 == y2)
    */
-  typedef void (*visitFn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2);
+  typedef void(*visitFn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2);
   void VisitEdges(visitFn, void *closure);
 
   nsCString ToString() const;
 
-  class RectIterator
-  {
-    int mCurrent;               // Index of the current entry
-    int mLimit;                 // Index one past the final entry.
-    mutable nsRect mTmp;        // The most recently gotten rectangle.
-    pixman_box32_t *mBoxes;
-
-  public:
-    explicit RectIterator(const nsRegion& aRegion)
-    {
-      mCurrent = 0;
-      mBoxes = pixman_region32_rectangles(aRegion.Impl(), &mLimit);
-      // Work around pixman bug. Sometimes pixman creates regions with 1 rect
-      // that's empty.
-      if (mLimit == 1 && nsRegion::BoxToRect(mBoxes[0]).IsEmpty()) {
-        mLimit = 0;
-      }
-    }
-
-    bool Done() const { return mCurrent == mLimit; }
-
-    const nsRect& Get() const
-    {
-      MOZ_ASSERT(!Done());
-      mTmp = nsRegion::BoxToRect(mBoxes[mCurrent]);
-      NS_ASSERTION(!mTmp.IsEmpty(), "Shouldn't return empty rect");
-      return mTmp;
-    }
-
-    void Next()
-    {
-      MOZ_ASSERT(!Done());
-      mCurrent++;
-    }
-  };
-
-  RectIterator RectIter() const { return RectIterator(*this); }
-
   static inline pixman_box32_t RectToBox(const nsRect &aRect)
   {
     pixman_box32_t box = { aRect.X(), aRect.Y(), aRect.XMost(), aRect.YMost() };
     return box;
   }
 
   static inline pixman_box32_t RectToBox(const mozilla::gfx::IntRect &aRect)
   {
     pixman_box32_t box = { aRect.X(), aRect.Y(), aRect.XMost(), aRect.YMost() };
     return box;
   }
+private:
 
+  nsIntRegion ToPixels(nscoord aAppUnitsPerPixel, bool aOutsidePixels) const;
+
+  nsRegion& Copy(const nsRegion& aRegion)
+  {
+    mBounds = aRegion.mBounds;
+    mBands = aRegion.mBands;
+    return *this;
+  }
+
+  nsRegion& Copy(const nsRect& aRect)
+  {
+    mBands.Clear();
+    mBounds = aRect;
+    return *this;
+  }
+
+  void EnsureSimplified() {
+    if (mBands.Length() == 1 && mBands.begin()->mStrips.Length() == 1) {
+      mBands.Clear();
+    }
+  }
 
   static inline nsRect BoxToRect(const pixman_box32_t &aBox)
   {
     return nsRect(aBox.x1, aBox.y1,
-                  aBox.x2 - aBox.x1,
-                  aBox.y2 - aBox.y1);
+      aBox.x2 - aBox.x1,
+      aBox.y2 - aBox.y1);
   }
 
-private:
-  pixman_region32_t mImpl;
+  void AddRect(const nsRect& aRect)
+  {
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorAddRect : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorAddRect(nsRegion& aRegion, const nsRect& aRect)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorAddRect()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r", stream);
+        stream << "r.OrWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion* mRegion;
+      nsRegion mRegionCopy;
+      nsRect mRect;
+    };
+
+    OperationStringGeneratorAddRect opGenerator(*this, aRect);
+#endif
+    if (aRect.IsEmpty()) {
+      return;
+    }
+
+    if (aRect.Overflows()) {
+      // We don't accept rects which overflow.
+      gfxWarning() << "Passing overflowing rect to AddRect.";
+      return;
+    }
+
+    if (mBands.IsEmpty()) {
+      if (mBounds.IsEmpty()) {
+        mBounds = aRect;
+        return;
+      } else if (mBounds.Contains(aRect)) {
+        return;
+      }
+
+      mBands.AppendElement(Band(mBounds));
+    }
+
+    mBounds = aRect.UnsafeUnion(mBounds);
+
+    size_t idx = 0;
+
+    Strip strip(aRect.X(), aRect.XMost());
+    Band remaining(aRect);
+
+    while (idx != mBands.Length()) {
+      if (mBands[idx].bottom <= remaining.top) {
+        // This band lies wholly above aRect.
+        idx++;
+        continue;
+      }
+
+      if (remaining.top >= remaining.bottom) {
+        AssertState();
+        EnsureSimplified();
+        return;
+      }
+
+      if (mBands[idx].top >= remaining.bottom) {
+        // This band lies wholly below aRect.
+        break;
+      }
+
+      if (mBands[idx].EqualStrips(remaining)) {
+        mBands[idx].top = std::min(mBands[idx].top, remaining.top);
+        // Nothing to do for this band. Just expand.
+        remaining.top = mBands[idx].bottom;
+        CompressBefore(idx);
+        idx++;
+        continue;
+      }
+
+      if (mBands[idx].top > remaining.top) {
+        auto before = mBands.InsertElementAt(idx, remaining);
+        before->bottom = mBands[idx + 1].top;
+        remaining.top = before->bottom;
+        CompressBefore(idx);
+        idx++;
+        CompressBefore(idx);
+        continue;
+      }
+
+      if (mBands[idx].ContainsStrip(strip)) {
+        remaining.top = mBands[idx].bottom;
+        idx++;
+        continue;
+      }
+
+      // mBands[idx].top <= remaining.top.
 
-#ifndef MOZ_TREE_PIXMAN
-  // For compatibility with pixman versions older than 0.25.2.
-  static inline void
-  pixman_region32_clear(pixman_region32_t *region)
+      if (mBands[idx].top < remaining.top) {
+        auto before = mBands.InsertElementAt(idx, Band(mBands[idx]));
+        before->bottom = remaining.top;
+        idx++;
+        mBands[idx].top = remaining.top;
+        continue;
+      }
+
+      // mBands[idx].top == remaining.top
+      if (mBands[idx].bottom > remaining.bottom) {
+        auto below = mBands.InsertElementAt(idx + 1, Band(mBands[idx]));
+        below->top = remaining.bottom;
+        mBands[idx].bottom = remaining.bottom;
+      }
+
+      mBands[idx].InsertStrip(strip);
+      CompressBefore(idx);
+      remaining.top = mBands[idx].bottom;
+      idx++;
+      CompressBefore(idx);
+    }
+
+    if (remaining.top < remaining.bottom) {
+      // We didn't find any bands that overlapped aRect.
+      if (idx) {
+        if (mBands[idx - 1].bottom == remaining.top && mBands[idx - 1].EqualStrips(remaining)) {
+          mBands[idx - 1].bottom = remaining.bottom;
+          CompressBefore(idx);
+          AssertState();
+          EnsureSimplified();
+          return;
+        }
+      }
+      mBands.InsertElementAt(idx, remaining);
+      idx++;
+      CompressBefore(idx);
+    } else {
+      CompressBefore(idx);
+    }
+
+    AssertState();
+    EnsureSimplified();
+  }
+
+  // Most callers could probably do this on the fly, if this ever shows up
+  // in profiles we could optimize this.
+  nsRect CalculateBounds() const
   {
-    pixman_region32_fini(region);
-    pixman_region32_init(region);
+    if (mBands.IsEmpty()) {
+      return mBounds;
+    }
+
+    int32_t top = mBands.begin()->top;
+    int32_t bottom = mBands.LastElement().bottom;
+
+    int32_t leftMost = mBands.begin()->mStrips.begin()->left;
+    int32_t rightMost = mBands.begin()->mStrips.LastElement().right;
+    for (const Band& band : mBands) {
+      leftMost = std::min(leftMost, band.mStrips.begin()->left);
+      rightMost = std::max(rightMost, band.mStrips.LastElement().right);
+    }
+
+    return nsRect(leftMost, top, rightMost - leftMost, bottom - top);
   }
+
+  static uint32_t ComputeMergedAreaIncrease(const Band& aTopBand,
+                                            const Band& aBottomBand);
+
+  // Returns true if idx is now referring to the 'next' band
+  bool CompressAdjacentBands(size_t& aIdx)
+  {
+    if ((aIdx + 1) < mBands.Length()) {
+      if (mBands[aIdx + 1].top == mBands[aIdx].bottom && mBands[aIdx + 1].EqualStrips(mBands[aIdx])) {
+        mBands[aIdx].bottom = mBands[aIdx + 1].bottom;
+        mBands.RemoveElementAt(aIdx + 1);
+      }
+    }
+    if (aIdx) {
+      if (mBands[aIdx - 1].bottom == mBands[aIdx].top && mBands[aIdx].EqualStrips(mBands[aIdx - 1])) {
+        mBands[aIdx - 1].bottom = mBands[aIdx].bottom;
+        mBands.RemoveElementAt(aIdx);
+        return true;
+      }
+    }
+    return false;
+  }
+
+  void CompressBefore(size_t& aIdx)
+  {
+    if (aIdx && aIdx < mBands.Length()) {
+      if (mBands[aIdx - 1].bottom == mBands[aIdx].top && mBands[aIdx - 1].EqualStrips(mBands[aIdx])) {
+        mBands[aIdx].top = mBands[aIdx - 1].top;
+        mBands.RemoveElementAt(aIdx - 1);
+        aIdx--;
+      }
+    }
+  }
+
+
+  BandArray mBands;
+  // Considering we only ever OR with nsRects, the bounds should fit in an nsRect as well.
+  nsRect mBounds;
+#ifdef DEBUG_REGIONS
+  friend class OperationStringGenerator;
+  OperationStringGenerator* mCurrentOpGenerator;
 #endif
 
-  nsIntRegion ToPixels(nscoord aAppUnitsPerPixel, bool aOutsidePixels) const;
-
-  nsRegion& Copy (const nsRegion& aRegion)
-  {
-    pixman_region32_copy(&mImpl, aRegion.Impl());
-    return *this;
-  }
-
-  nsRegion& Copy (const nsRect& aRect)
+public:
+  class RectIterator
   {
-    // pixman needs to distinguish between an empty region and a region
-    // with one rect so that it can return a different number of rectangles.
-    // Empty rect: data = empty_box
-    //     1 rect: data = null
-    //    >1 rect: data = rects
-    if (aRect.IsEmpty()) {
-      pixman_region32_clear(&mImpl);
-    } else {
-      pixman_box32_t box = RectToBox(aRect);
-      pixman_region32_reset(&mImpl, &box);
+    const nsRegion& mRegion;
+    typename BandArray::const_iterator mCurrentBand;
+    typename StripArray::const_iterator mCurrentStrip;
+
+  public:
+    explicit RectIterator(const nsRegion& aRegion)
+      : mRegion(aRegion)
+      , mCurrentBand(aRegion.mBands.begin())
+    {
+      mIsDone = mRegion.mBounds.IsEmpty();
+      if (mCurrentBand != aRegion.mBands.end()) {
+        mCurrentStrip = mCurrentBand->mStrips.begin();
+      }
     }
-    return *this;
-  }
+
+    bool Done() const { return mIsDone; }
+
+    const nsRect Get() const
+    {
+      if (mRegion.mBands.IsEmpty()) {
+        return mRegion.mBounds;
+      }
+      return nsRect(mCurrentStrip->left, mCurrentBand->top,
+        mCurrentStrip->right - mCurrentStrip->left,
+        mCurrentBand->bottom - mCurrentBand->top);
+    }
 
-  pixman_region32_t* Impl() const
-  {
-    return const_cast<pixman_region32_t*>(&mImpl);
-  }
+    void Next()
+    {
+      if (mRegion.mBands.IsEmpty()) {
+        mIsDone = true;
+        return;
+      }
+
+      mCurrentStrip++;
+      if (mCurrentStrip == mCurrentBand->mStrips.end()) {
+        mCurrentBand++;
+        if (mCurrentBand != mRegion.mBands.end()) {
+          mCurrentStrip = mCurrentBand->mStrips.begin();
+        } else {
+          mIsDone = true;
+        }
+      }
+    }
+
+    bool mIsDone;
+  };
+
+  RectIterator RectIter() const { return RectIterator(*this); }
 };
 
 namespace mozilla {
 namespace gfx {
 
 /**
  * BaseIntRegions use int32_t coordinates.
  */
@@ -486,21 +1542,16 @@ public:
   {
     return !(*this == aRgn);
   }
 
   friend std::ostream& operator<<(std::ostream& stream, const Derived& m) {
     return stream << m.mImpl;
   }
 
-  void Swap(Derived* aOther)
-  {
-    mImpl.Swap(&aOther->mImpl);
-  }
-
   void AndWith(const Derived& aOther)
   {
     And(This(), aOther);
   }
   void AndWith(const Rect& aOther)
   {
     And(This(), aOther);
   }
@@ -634,17 +1685,17 @@ public:
   }
 
   void MoveBy (int32_t aXOffset, int32_t aYOffset)
   {
     MoveBy (Point (aXOffset, aYOffset));
   }
   void MoveBy (Point aPt)
   {
-    mImpl.MoveBy (aPt.x, aPt.y);
+    mImpl.MoveBy (aPt.X(), aPt.Y());
   }
   Derived MovedBy(int32_t aXOffset, int32_t aYOffset) const
   {
     return MovedBy(Point(aXOffset, aYOffset));
   }
   Derived MovedBy(const Point& aPt) const
   {
     Derived copy(This());
@@ -682,17 +1733,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,280 @@ TEST(Gfx, RegionScaleToInside) {
     result.Or(result, mozilla::gfx::IntRect(0,750,318,18));
 
     EXPECT_TRUE(result.IsEqual(scaled)) <<
       "scaled result incorrect";
   }
 
 }
 
+TEST(Gfx, RegionOrWith) {
+  {
+    nsRegion r(nsRect(79, 31, 75, 12));
+    r.OrWith(nsRect(22, 43, 132, 5));
+    r.OrWith(nsRect(22, 48, 125, 3));
+    r.OrWith(nsRect(22, 51, 96, 20));
+    r.OrWith(nsRect(34, 71, 1, 14));
+    r.OrWith(nsRect(26, 85, 53, 1));
+    r.OrWith(nsRect(26, 86, 53, 4));
+    r.OrWith(nsRect(96, 86, 30, 4));
+    r.OrWith(nsRect(34, 90, 1, 2));
+    r.OrWith(nsRect(96, 90, 30, 2));
+    r.OrWith(nsRect(34, 92, 1, 3));
+    r.OrWith(nsRect(49, 92, 34, 3));
+    r.OrWith(nsRect(96, 92, 30, 3));
+    r.OrWith(nsRect(34, 95, 1, 17));
+    r.OrWith(nsRect(49, 95, 77, 17));
+    r.OrWith(nsRect(34, 112, 1, 12));
+    r.OrWith(nsRect(75, 112, 51, 12));
+    r.OrWith(nsRect(34, 124, 1, 10));
+    r.OrWith(nsRect(75, 124, 44, 10));
+    r.OrWith(nsRect(34, 134, 1, 19));
+    r.OrWith(nsRect(22, 17, 96, 27));
+  }
+  {
+    nsRegion r(nsRect(0, 8, 257, 32));
+    r.OrWith(nsRect(3702, 8, 138, 32));
+    r.OrWith(nsRect(0, 40, 225, 1));
+    r.OrWith(nsRect(3702, 40, 138, 1));
+    r.OrWith(nsRect(0, 41, 101, 40));
+    r.OrWith(nsRect(69, 41, 32, 40));
+  }
+  {
+    nsRegion r(nsRect(79, 56, 8, 32));
+    r.OrWith(nsRect(5, 94, 23, 81));
+    r.OrWith(nsRect(56, 29, 91, 81));
+  }
+  {
+    nsRegion r(nsRect(0, 82, 3840, 2046));
+    r.OrWith(nsRect(0, 0, 3840, 82));
+  }
+  {
+    nsRegion r(nsRect(2, 5, 600, 28));
+    r.OrWith(nsRect(2, 82, 600, 19));
+    r.OrWith(nsRect(2, 33, 600, 49));
+  }
+  {
+    nsRegion r(nsRect(3823, 0, 17, 17));
+    r.OrWith(nsRect(3823, 2029, 17, 17));
+    r.OrWith(nsRect(3823, 0, 17, 2046));
+  }
+  {
+    nsRegion r(nsRect(1036, 4, 32, 21));
+    r.OrWith(nsRect(1070, 4, 66, 21));
+    r.OrWith(nsRect(40, 5, 0, 33));
+  }
+  {
+    nsRegion r(nsRect(0, 0, 1024, 1152));
+    r.OrWith(nsRect(-335802, -1073741824, 1318851, 1860043520));
+  }
+  {
+    nsRegion r(nsRect(0, 0, 800, 1000));
+    r.OrWith(nsRect(0, 0, 536870912, 1073741824));
+  }
+  {
+    nsRegion r(nsRect(53, 2, 52, 3));
+    r.OrWith(nsRect(45, 5, 60, 16));
+    r.OrWith(nsRect(16, 21, 8, 1));
+    r.OrWith(nsRect(45, 21, 12, 1));
+    r.OrWith(nsRect(16, 22, 8, 5));
+    r.OrWith(nsRect(33, 22, 52, 5));
+    r.OrWith(nsRect(16, 27, 8, 7));
+    r.OrWith(nsRect(33, 27, 66, 7));
+    r.OrWith(nsRect(0, 34, 99, 1));
+    r.OrWith(nsRect(0, 35, 159, 27));
+    r.OrWith(nsRect(0, 62, 122, 3));
+    r.OrWith(nsRect(0, 65, 85, 11));
+    r.OrWith(nsRect(91, 65, 97, 11));
+    r.OrWith(nsRect(11, 76, 74, 2));
+    r.OrWith(nsRect(91, 76, 97, 2));
+    r.OrWith(nsRect(11, 78, 74, 12));
+    r.OrWith(nsRect(11, 90, 13, 3));
+    r.OrWith(nsRect(33, 90, 108, 3));
+    r.OrWith(nsRect(16, 93, 8, 22));
+    r.OrWith(nsRect(33, 93, 108, 22));
+    r.OrWith(nsRect(16, 115, 8, 1));
+    r.OrWith(nsRect(58, 115, 83, 1));
+    r.OrWith(nsRect(58, 116, 83, 25));
+    r.OrWith(nsRect(59, 37, 88, 92));
+  }
+#ifdef REGION_RANDOM_STRESS_TESTS
+  const uint32_t TestIterations = 100000;
+  const uint32_t RectsPerTest = 100;
+
+  nsRect rects[RectsPerTest];
+
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r;
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    r.SetEmpty();
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      r.OrWith(rects[n]);
+    }
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      EXPECT_TRUE(r.Contains(rects[n]));
+    }
+  }
+#endif
+}
+
+TEST(Gfx, RegionSubWith) {
+  {
+    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));
+  }
+
+#ifdef REGION_RANDOM_STRESS_TESTS
+  const uint32_t TestIterations = 100000;
+  const uint32_t RectsPerTest = 100;
+  const uint32_t SubRectsPerTest = 10;
+
+  nsRect rects[RectsPerTest];
+  nsRect subRects[SubRectsPerTest];
+
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r;
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    r.SetEmpty();
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      r.OrWith(rects[n]);
+    }
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      EXPECT_TRUE(r.Contains(rects[n]));
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      r.SubWith(subRects[n]);
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+    }
+  }
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r(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
+}
+
+TEST(Gfx, RegionAndWith) {
+  {
+    nsRegion r(nsRect(20, 0, 20, 20));
+    r.OrWith(nsRect(0, 20, 40, 20));
+    r.AndWith(nsRect(0, 0, 5, 5));
+    EXPECT_FALSE(r.Contains(1, 1));
+  }
+  {
+    nsRegion r1(nsRect(512, 1792, 256, 256));
+    nsRegion r2(nsRect(17, 1860, 239, 35));
+    r2.OrWith(nsRect(17, 1895, 239, 7));
+    r2.OrWith(nsRect(768, 1895, 154, 7));
+    r2.OrWith(nsRect(17, 1902, 905, 483));
+    r1.AndWith(r2);
+  }
+#ifdef REGION_RANDOM_STRESS_TESTS
+  const uint32_t TestIterations = 100000;
+  const uint32_t RectsPerTest = 50;
+  const uint32_t pointsTested = 100;
+
+  {
+    nsRect rectsSet1[RectsPerTest];
+    nsRect rectsSet2[RectsPerTest];
+
+    for (uint32_t i = 0; i < TestIterations; i++) {
+      nsRegion r1;
+      nsRegion r2;
+      for (uint32_t n = 0; n < RectsPerTest; n++) {
+        rectsSet1[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+        rectsSet2[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+        r1.OrWith(rectsSet1[n]);
+        r2.OrWith(rectsSet1[n]);
+      }
+
+      nsRegion r3 = r1;
+      r3.AndWith(r2);
+
+      for (uint32_t n = 0; n < pointsTested; n++) {
+        nsPoint p(rand() % 200, rand() % 200);
+        if (r1.Contains(p.x, p.y) && r2.Contains(p.x, p.y)) {
+          EXPECT_TRUE(r3.Contains(p.x, p.y));
+        } else {
+          EXPECT_FALSE(r3.Contains(p.x, p.y));
+        }
+      }
+    }
+  }
+
+  {
+    nsRect rectsSet[RectsPerTest];
+    nsRect testRect;
+    for (uint32_t i = 0; i < TestIterations; i++) {
+      nsRegion r;
+      for (uint32_t n = 0; n < RectsPerTest; n++) {
+        rectsSet[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+        r.OrWith(rectsSet[n]);
+      }
+      testRect.SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+
+      nsRegion r2 = r;
+      r2.AndWith(testRect);
+
+      for (uint32_t n = 0; n < pointsTested; n++) {
+        nsPoint p(rand() % 200, rand() % 200);
+        if (r.Contains(p.x, p.y) && testRect.Contains(p.x, p.y)) {
+          EXPECT_TRUE(r2.Contains(p.x, p.y));
+        } else {
+          EXPECT_FALSE(r2.Contains(p.x, p.y));
+        }
+      }
+    }
+  }
+#endif
+}
 
 TEST(Gfx, 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 +485,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;