Bug 1440753: Replace pixman regions with our own region code. r=mattwoodrow
☠☠ backed out by 3a78edaef5e7 ☠ ☠
authorBas Schouten <bschouten@mozilla.com>
Fri, 09 Mar 2018 05:27:15 +0100
changeset 411335 d85b5825a721eb18febaf5b9e068a9ec3268a2f5
parent 411334 0702a754328d4e220a67c53161c2be15401de373
child 411336 dd609e3b9e0bf0c9f0431c376889485232aacc4f
push id101626
push userbschouten@mozilla.com
push dateMon, 02 Apr 2018 17:43:18 +0000
treeherdermozilla-inbound@d85b5825a721 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmattwoodrow
bugs1440753
milestone61.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/painting/FrameLayerBuilder.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,608 +5,514 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 
 #include "nsRegion.h"
 #include "nsTArray.h"
 #include "gfxUtils.h"
 #include "mozilla/ToString.h"
 
+using namespace std;
+
+void
+nsRegion::AssertStateInternal() const
+{
+  bool failed = false;
+  // Verify consistent state inside the region.
+  int32_t lastY = INT32_MIN;
+  int32_t lowestX = INT32_MAX;
+  int32_t highestX = INT32_MIN;
+  for (auto iter = mBands.begin(); iter != mBands.end(); iter++) {
+    const Band& band = *iter;
+    if (band.bottom <= band.top) {
+      failed = true;
+      break;
+    }
+    if (band.top < lastY) {
+      failed = true;
+      break;
+    }
+    lastY = band.bottom;
+
+    lowestX = std::min(lowestX, band.mStrips.begin()->left);
+    highestX = std::max(highestX, band.mStrips.LastElement().right);
+
+    int32_t lastX = INT32_MIN;
+    if (iter != mBands.begin()) {
+      auto prev = iter;
+      prev--;
+
+      if (prev->bottom == iter->top) {
+        if (band.EqualStrips(*prev)) {
+          failed = true;
+          break;
+        }
+      }
+    }
+    for (const Strip& strip : band.mStrips) {
+      if (strip.right <= strip.left) {
+        failed = true;
+        break;
+      }
+      if (strip.left <= lastX) {
+        failed = true;
+        break;
+      }
+      lastX = strip.right;
+    }
+    if (failed) {
+      break;
+    }
+  }
+
+  if (!(mBounds == CalculateBounds())) {
+    failed = true;
+  }
+
+  if (failed) {
+#ifdef DEBUG_REGIONS
+    if (mCurrentOpGenerator) {
+      mCurrentOpGenerator->OutputOp();
+    }
+#endif
+    MOZ_ASSERT(false);
+  }
+}
+
 bool nsRegion::Contains(const nsRegion& aRgn) const
 {
   // XXX this could be made faster by iterating over
   // both regions at the same time some how
   for (auto iter = aRgn.RectIter(); !iter.Done(); iter.Next()) {
     if (!Contains(iter.Get())) {
       return false;
     }
   }
   return true;
 }
 
 bool nsRegion::Intersects(const nsRect& aRect) const
 {
-  // XXX this could be made faster by using pixman_region32_contains_rect
-  for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
-    if (iter.Get().Intersects(aRect)) {
-      return true;
+  if (mBands.IsEmpty()) {
+    return mBounds.Intersects(aRect);
+  }
+
+  if (!mBounds.Intersects(aRect)) {
+    return false;
+  }
+
+  Strip rectStrip(aRect.X(), aRect.XMost());
+
+  auto iter = mBands.begin();
+  while (iter != mBands.end()) {
+    if (iter->top >= aRect.YMost()) {
+      return false;
     }
+
+    if (iter->bottom <= aRect.Y()) {
+      // This band is entirely before aRect, move on.
+      iter++;
+      continue;
+    }
+
+    if (!iter->Intersects(rectStrip)) {
+      // This band does not intersect aRect horizontally. Move on.
+      iter++;
+      continue;
+    }
+
+    // This band intersects with aRect.
+    return true;
   }
+
   return false;
 }
 
 void nsRegion::Inflate(const nsMargin& aMargin)
 {
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
-  for (int i=0; i<n; i++) {
-    nsRect rect = BoxToRect(boxes[i]);
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = iter.Get();
     rect.Inflate(aMargin);
-    boxes[i] = RectToBox(rect);
+    newRegion.AddRect(rect);
   }
 
-  pixman_region32_t region;
-  // This will union all of the rectangles and runs in about O(n lg(n))
-  pixman_region32_init_rects(&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;
+    }
+    if (currentStripBottom) {
+      currentStripBottom--;
+    }
+  }
+  uint32_t currentStripTop = 0;
+  for (auto& strip : aBottomBand.mStrips) {
+    if (currentStripTop == aTopBand.mStrips.Length() || strip.right < aTopBand.mStrips[currentStripTop].left) {
+      totalArea += topHeight * strip.Size();
+      continue;
     }
-    top = top_next;
-    bottom = bottom_next;
-    // find the next edge
-    if (i->x < j->x) {
-      top_next = !top;
-      width = i->x - cur_x;
-      cur_x = i->x;
-      i++;
-    } else if (j->x < i->x) {
-      bottom_next = !bottom;
-      width = j->x - cur_x;
-      cur_x = j->x;
-      j++;
-    } else { // i->x == j->x
-      top_next = !top;
-      bottom_next = !bottom;
-      width = i->x - cur_x;
-      cur_x = i->x;
-      i++;
-      j++;
+
+    int32_t currentX = strip.left;
+    while (currentStripTop != aTopBand.mStrips.Length() && aTopBand.mStrips[currentStripTop].left < strip.right) {
+      if (currentX >= strip.right) {
+        break;
+      }
+      if (currentX < aTopBand.mStrips[currentStripTop].left) {
+        // Add the part that's not intersecting.
+        totalArea += (aTopBand.mStrips[currentStripTop].left - currentX) * topHeight;
+      }
+
+      currentX = std::max(aTopBand.mStrips[currentStripTop].right, currentX);
+      currentStripTop++;
     }
-  } while (i < end_i && j < end_j);
 
-  // handle any remaining rects
-  while (i < end_i) {
-    width = i->x - cur_x;
-    cur_x = i->x;
-    i++;
-    if (top)
-      totalArea += (inbetweenHeight+bottomRectsHeight)*width;
-    top = !top;
-  }
-
-  while (j < end_j) {
-    width = j->x - cur_x;
-    cur_x = j->x;
-    j++;
-    if (bottom)
-      totalArea += (inbetweenHeight+topRectsHeight)*width;
-    bottom = !bottom;
+    // Add remainder of this strip.
+    if (currentX < strip.right) {
+      totalArea += (strip.right - currentX) * topHeight;
+    }
+    if (currentStripTop) {
+      currentStripTop--;
+    }
   }
   return totalArea;
 }
 
-static pixman_box32_t *
-CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end)
-{
-    // XXX: std::copy
-    pixman_box32_t *src_it = src_start;
-    while (src_it < src_end) {
-        *dest_it++ = *src_it++;
-    }
-    return dest_it;
-}
-
-
-#define WRITE_RECT(x1, x2, y1, y2) \
-    do {                    \
-         tmpRect->x1 = x1;  \
-         tmpRect->x2 = x2;  \
-         tmpRect->y1 = y1;  \
-         tmpRect->y2 = y2;  \
-         tmpRect++;         \
-    } while (0)
-
-/* If 'r' overlaps the current rect, then expand the current rect to include
- * it. Otherwise write the current rect out to tmpRect, and set r as the
- * updated current rect. */
-#define MERGE_RECT(r)                 \
-    do {                              \
-      if (r->x1 <= x2) {              \
-          if (x2 < r->x2)             \
-              x2 = r->x2;             \
-      } else {                        \
-          WRITE_RECT(x1, x2, y1, y2); \
-          x1 = r->x1;                 \
-          x2 = r->x2;                 \
-      }                               \
-      r++;                            \
-    } while (0)
-
-
-/* Can we merge two sets of rects without extra space?
- * Yes, but not easily. We can even do it stably
- * but we don't need that property.
- *
- * This is written in the style of pixman_region_union_o */
-static pixman_box32_t *
-MergeRects(pixman_box32_t *r1,
-           pixman_box32_t *r1_end,
-           pixman_box32_t *r2,
-           pixman_box32_t *r2_end,
-           pixman_box32_t *tmpRect)
-{
-    /* This routine works by maintaining the current
-     * rectangle in x1,x2,y1,y2 and either merging
-     * in the left most rectangle if it overlaps or
-     * outputing the current rectangle and setting
-     * it to the the left most one */
-    const int y1 = r1->y1;
-    const int y2 = r2->y2;
-    int x1;
-    int x2;
-
-    /* Find the left-most edge */
-    if (r1->x1 < r2->x1) {
-        x1 = r1->x1;
-        x2 = r1->x2;
-        r1++;
-    } else {
-        x1 = r2->x1;
-        x2 = r2->x2;
-        r2++;
-    }
-
-    while (r1 != r1_end && r2 != r2_end) {
-        /* Find and merge the left-most rectangle */
-        if (r1->x1 < r2->x1)
-            MERGE_RECT (r1);
-        else
-            MERGE_RECT (r2);
-    }
-
-    /* Finish up any left overs */
-    if (r1 != r1_end) {
-        do {
-            MERGE_RECT (r1);
-        } while (r1 != r1_end);
-    } else if (r2 != r2_end) {
-        do {
-            MERGE_RECT(r2);
-        } while (r2 != r2_end);
-    }
-
-    /* Finish up the last rectangle */
-    WRITE_RECT(x1, x2, y1, y2);
-
-    return tmpRect;
-}
-
 void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold)
 {
-
-  pixman_box32_t *boxes;
-  int n;
-  boxes = pixman_region32_rectangles(&mImpl, &n);
-
-  // if we have no rectangles then we're done
-  if (!n)
+  if (mBands.Length() < 2) {
+    // We have only one or no row and we're done.
     return;
-
-  pixman_box32_t *end = boxes + n;
-  pixman_box32_t *topRectsEnd = boxes+1;
-  pixman_box32_t *topRects = boxes;
-
-  // we need some temporary storage for merging both rows of rectangles
-  AutoTArray<pixman_box32_t, 10> tmpStorage;
-  tmpStorage.SetCapacity(n);
-  pixman_box32_t *tmpRect = tmpStorage.Elements();
-
-  pixman_box32_t *destRect = boxes;
-  pixman_box32_t *rect = tmpRect;
-  // find the end of the first span of rectangles
-  while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
-    topRectsEnd++;
   }
 
-  // if we only have one row we are done
-  if (topRectsEnd == end)
-    return;
-
-  pixman_box32_t *bottomRects = topRectsEnd;
-  pixman_box32_t *bottomRectsEnd = bottomRects+1;
+  uint32_t currentBand = 0;
   do {
-    // find the end of the bottom span of rectangles
-    while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
-      bottomRectsEnd++;
-    }
-    uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd,
-                                                   bottomRects, bottomRectsEnd);
+    Band& band = mBands[currentBand];
+
+    uint32_t totalArea = ComputeMergedAreaIncrease(band, mBands[currentBand + 1]);
 
     if (totalArea <= aThreshold) {
-      // merge the rects into tmpRect
-      rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect);
-
-      // set topRects to where the newly merged rects will be so that we use them
-      // as our next set of topRects
-      topRects = destRect;
-      // copy the merged rects back into the destination
-      topRectsEnd = CopyRow(destRect, tmpRect, rect);
+      for (Strip& strip : mBands[currentBand + 1].mStrips) {
+        // This could use an optimized function to merge two bands.
+        band.InsertStrip(strip);
+      }
+      band.bottom = mBands[currentBand + 1].bottom;
+      mBands.RemoveElementAt(currentBand + 1);
     } else {
-      // copy the unmerged rects
-      destRect = CopyRow(destRect, topRects, topRectsEnd);
+      currentBand++;
+    }
+  } while (currentBand + 1 < mBands.Length());
 
-      topRects = bottomRects;
-      topRectsEnd = bottomRectsEnd;
-      if (bottomRectsEnd == end) {
-        // copy the last row when we are done
-        topRectsEnd = CopyRow(destRect, topRects, topRectsEnd);
-      }
-    }
-    bottomRects = bottomRectsEnd;
-  } while (bottomRectsEnd != end);
-
-
-  uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n);
-  // pixman has a special representation for
-  // regions of 1 rectangle. So just use the
-  // bounds in that case
-  if (reducedCount > 1) {
-    // reach into pixman and lower the number
-    // of rects stored in data.
-    this->mImpl.data->numRects = reducedCount;
-  } else {
-    *this = GetBounds();
-  }
+  EnsureSimplified();
+  AssertState();
 }
 
 
 typedef void (*visit_fn)(void *closure, VisitSide side, int x1, int y1, int x2, int y2);
 
-static bool VisitNextEdgeBetweenRect(visit_fn visit, void *closure, VisitSide side,
-				     pixman_box32_t *&r1, pixman_box32_t *&r2, const int y, int &x1)
+void nsRegion::VisitEdges (visit_fn visit, void *closure)
 {
-  // check for overlap
-  if (r1->x2 >= r2->x1) {
-    MOZ_ASSERT(r2->x1 >= x1);
-    visit(closure, side, x1, y, r2->x1, y);
-
-    // find the rect that ends first or always drop the one that comes first?
-    if (r1->x2 < r2->x2) {
-      x1 = r1->x2;
-      r1++;
-    } else {
-      x1 = r2->x2;
-      r2++;
-    }
-    return true;
-  } else {
-    MOZ_ASSERT(r1->x2 < r2->x2);
-    // we handle the corners by just extending the top and bottom edges
-    visit(closure, side, x1, y, r1->x2+1, y);
-    r1++;
-    // we assign x1 because we can assume that x1 <= r2->x1 - 1
-    // However the caller may know better and if so, may update
-    // x1 to r1->x1
-    x1 = r2->x1 - 1;
-    return false;
+  if (mBands.IsEmpty()) {
+    visit(closure, VisitSide::LEFT, mBounds.X(), mBounds.Y(), mBounds.X(), mBounds.YMost());
+    visit(closure, VisitSide::RIGHT, mBounds.XMost(), mBounds.Y(), mBounds.XMost(), mBounds.YMost());
+    visit(closure, VisitSide::TOP, mBounds.X() - 1, mBounds.Y(), mBounds.XMost() + 1, mBounds.Y());
+    visit(closure, VisitSide::BOTTOM, mBounds.X() - 1, mBounds.YMost(), mBounds.XMost() + 1, mBounds.YMost());
+    return;
   }
-}
-
-//XXX: if we need to this can compute the end of the row
-static void
-VisitSides(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
-  // XXX: we can drop LEFT/RIGHT and just use the orientation
-  // of the line if it makes sense
-  while (r != r_end) {
-    visit(closure, VisitSide::LEFT, r->x1, r->y1, r->x1, r->y2);
-    visit(closure, VisitSide::RIGHT, r->x2, r->y1, r->x2, r->y2);
-    r++;
-  }
-}
 
-static void
-VisitAbove(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
-  while (r != r_end) {
-    visit(closure, VisitSide::TOP, r->x1-1, r->y1, r->x2+1, r->y1);
-    r++;
-  }
-}
-
-static void
-VisitBelow(visit_fn visit, void *closure, pixman_box32_t *r, pixman_box32_t *r_end)
-{
-  while (r != r_end) {
-    visit(closure, VisitSide::BOTTOM, r->x1-1, r->y2, r->x2+1, r->y2);
-    r++;
-  }
-}
-
-static pixman_box32_t *
-VisitInbetween(visit_fn visit, void *closure, pixman_box32_t *r1,
-               pixman_box32_t *r1_end,
-               pixman_box32_t *r2,
-               pixman_box32_t *r2_end)
-{
-  const int y = r1->y2;
-  int x1;
-
-  bool overlap = false;
-  while (r1 != r1_end && r2 != r2_end) {
-    if (!overlap) {
-      /* Find the left-most edge */
-      if (r1->x1 < r2->x1) {
-	x1 = r1->x1 - 1;
-      } else {
-	x1 = r2->x1 - 1;
-      }
-    }
-
-    MOZ_ASSERT((x1 >= (r1->x1 - 1)) || (x1 >= (r2->x1 - 1)));
-    if (r1->x1 < r2->x1) {
-      overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::BOTTOM, r1, r2, y, x1);
-    } else {
-      overlap = VisitNextEdgeBetweenRect(visit, closure, VisitSide::TOP, r2, r1, y, x1);
-    }
+  auto band = std::begin(mBands);
+  auto bandFinal = std::end(mBands);
+  bandFinal--;
+  for (const Strip& strip : band->mStrips) {
+    visit(closure, VisitSide::LEFT, strip.left, band->top, strip.left, band->bottom);
+    visit(closure, VisitSide::RIGHT, strip.right, band->top, strip.right, band->bottom);
+    visit(closure, VisitSide::TOP, strip.left - 1, band->top, strip.right + 1, band->top);
   }
 
-  /* Finish up which ever row has remaining rects*/
-  if (r1 != r1_end) {
-    // top row
+  if (band != bandFinal) {
     do {
-      visit(closure, VisitSide::BOTTOM, x1, y, r1->x2 + 1, y);
-      r1++;
-      if (r1 == r1_end)
-	break;
-      x1 = r1->x1 - 1;
-    } while (true);
-  } else if (r2 != r2_end) {
-    // bottom row
-    do {
-      visit(closure, VisitSide::TOP, x1, y, r2->x2 + 1, y);
-      r2++;
-      if (r2 == r2_end)
-	break;
-      x1 = r2->x1 - 1;
-    } while (true);
+      Band& topBand = *band;
+      band++;
+
+      for (const Strip& strip : band->mStrips) {
+        visit(closure, VisitSide::LEFT, strip.left, band->top, strip.left, band->bottom);
+        visit(closure, VisitSide::RIGHT, strip.right, band->top, strip.right, band->bottom);
+      }
+
+      if (band->top == topBand.bottom) {
+        // Two bands touching each other vertically.
+        Band& bottomBand = *band;
+        auto topStrip = std::begin(topBand.mStrips);
+        auto bottomStrip = std::begin(bottomBand.mStrips);
+
+        int y = topBand.bottom;
+
+        // State from this point on along the vertical edge:
+        // 0 - Empty
+        // 1 - Touched by top rect
+        // 2 - Touched by bottom rect
+        // 3 - Touched on both sides
+        int state;
+        const int TouchedByNothing = 0;
+        const int TouchedByTop = 1;
+        const int TouchedByBottom = 2;
+        // We always start with nothing.
+        int oldState = TouchedByNothing;
+        // Last state change, adjusted by -1 if the last state change was
+        // a change away from 0.
+        int lastX = std::min(topStrip->left, bottomStrip->left) - 1;
+
+        // Current edge being considered for top and bottom, 0 - left, 1 - right.
+        bool topEdgeIsLeft = true;
+        bool bottomEdgeIsLeft = true;
+        while (topStrip != std::end(topBand.mStrips) && bottomStrip != std::end(bottomBand.mStrips)) {
+          int topPos;
+          int bottomPos;
+          if (topEdgeIsLeft) {
+            topPos = topStrip->left;
+          } else {
+            topPos = topStrip->right;
+          }
+          if (bottomEdgeIsLeft) {
+            bottomPos = bottomStrip->left;
+          } else {
+            bottomPos = bottomStrip->right;
+          }
+
+          int currentX = std::min(topPos, bottomPos);
+          if (topPos < bottomPos) {
+            if (topEdgeIsLeft) {
+              state = oldState | TouchedByTop;
+            } else {
+              state = oldState ^ TouchedByTop;
+              topStrip++;
+            }
+            topEdgeIsLeft = !topEdgeIsLeft;
+          } else if (bottomPos < topPos) {
+            if (bottomEdgeIsLeft) {
+              state = oldState | TouchedByBottom;
+            } else {
+              state = oldState ^ TouchedByBottom;
+              bottomStrip++;
+            }
+            bottomEdgeIsLeft = !bottomEdgeIsLeft;
+          } else {
+            // bottomPos == topPos
+            state = TouchedByNothing;
+            if (bottomEdgeIsLeft) {
+              state = TouchedByBottom;
+            } else {
+              bottomStrip++;
+            }
+            if (topEdgeIsLeft) {
+              state |= TouchedByTop;
+            } else {
+              topStrip++;
+            }
+            topEdgeIsLeft = !topEdgeIsLeft;
+            bottomEdgeIsLeft = !bottomEdgeIsLeft;
+          }
+
+          MOZ_ASSERT(state != oldState);
+          if (oldState == TouchedByNothing) {
+            // We had nothing before, make sure the left edge will be padded.
+            lastX = currentX - 1;
+          } else if (oldState == TouchedByTop) {
+            if (state == TouchedByNothing) {
+              visit(closure, VisitSide::BOTTOM, lastX, y, currentX + 1, y);
+            } else {
+              visit(closure, VisitSide::BOTTOM, lastX, y, currentX, y);
+              lastX = currentX;
+            }
+          } else if (oldState == TouchedByBottom) {
+            if (state == TouchedByNothing) {
+              visit(closure, VisitSide::TOP, lastX, y, currentX + 1, y);
+            } else {
+              visit(closure, VisitSide::TOP, lastX, y, currentX, y);
+              lastX = currentX;
+            }
+          } else {
+            lastX = currentX;
+          }
+          oldState = state;
+        }
+
+        MOZ_ASSERT(!state || (topEdgeIsLeft || bottomEdgeIsLeft));
+        if (topStrip != std::end(topBand.mStrips)) {
+          if (!topEdgeIsLeft) {
+            visit(closure, VisitSide::BOTTOM, lastX, y, topStrip->right + 1, y);
+            topStrip++;
+          }
+          while (topStrip != std::end(topBand.mStrips)) {
+            visit(closure, VisitSide::BOTTOM, topStrip->left - 1, y, topStrip->right + 1, y);
+            topStrip++;
+          }
+        } else if (bottomStrip != std::end(bottomBand.mStrips)) {
+          if (!bottomEdgeIsLeft) {
+            visit(closure, VisitSide::TOP, lastX, y, bottomStrip->right + 1, y);
+            bottomStrip++;
+          }
+          while (bottomStrip != std::end(bottomBand.mStrips)) {
+            visit(closure, VisitSide::TOP, bottomStrip->left - 1, y, bottomStrip->right + 1, y);
+            bottomStrip++;
+          }
+        }
+      } else {
+        for (const Strip& strip : topBand.mStrips) {
+          visit(closure, VisitSide::BOTTOM, strip.left - 1, topBand.bottom, strip.right + 1, topBand.bottom);
+        }
+        for (const Strip& strip : band->mStrips) {
+          visit(closure, VisitSide::TOP, strip.left - 1, band->top, strip.right + 1, band->top);
+        }
+      }
+    } while (band != bandFinal);
   }
 
-  return 0;
-}
-
-void nsRegion::VisitEdges (visit_fn visit, void *closure)
-{
-  pixman_box32_t *boxes;
-  int n;
-  boxes = pixman_region32_rectangles(&mImpl, &n);
-
-  // if we have no rectangles then we're done
-  if (!n)
-    return;
-
-  pixman_box32_t *end = boxes + n;
-  pixman_box32_t *topRectsEnd = boxes + 1;
-  pixman_box32_t *topRects = boxes;
-
-  // find the end of the first span of rectangles
-  while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
-    topRectsEnd++;
+  for (const Strip& strip : band->mStrips) {
+    visit(closure, VisitSide::BOTTOM, strip.left - 1, band->bottom, strip.right + 1, band->bottom);
   }
-
-  // In order to properly handle convex corners we always visit the sides first
-  // that way when we visit the corners we can pad using the value from the sides
-  VisitSides(visit, closure, topRects, topRectsEnd);
-
-  VisitAbove(visit, closure, topRects, topRectsEnd);
-
-  pixman_box32_t *bottomRects = topRects;
-  pixman_box32_t *bottomRectsEnd = topRectsEnd;
-  if (topRectsEnd != end) {
-    do {
-      // find the next row of rects
-      bottomRects = topRectsEnd;
-      bottomRectsEnd = topRectsEnd + 1;
-      while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
-        bottomRectsEnd++;
-      }
-
-      VisitSides(visit, closure, bottomRects, bottomRectsEnd);
-
-      if (topRects->y2 == bottomRects->y1) {
-        VisitInbetween(visit, closure, topRects, topRectsEnd,
-                                       bottomRects, bottomRectsEnd);
-      } else {
-        VisitBelow(visit, closure, topRects, topRectsEnd);
-        VisitAbove(visit, closure, bottomRects, bottomRectsEnd);
-      }
-
-      topRects = bottomRects;
-      topRectsEnd = bottomRectsEnd;
-    } while (bottomRectsEnd != end);
-  }
-
-  // the bottom of the region doesn't touch anything else so we
-  // can always visit it at the end
-  VisitBelow(visit, closure, bottomRects, bottomRectsEnd);
 }
 
 
 void nsRegion::SimplifyInward (uint32_t aMaxRects)
 {
   NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
 
   if (GetNumRects() <= aMaxRects)
     return;
 
   SetEmpty();
 }
 
 uint64_t nsRegion::Area () const
 {
+  if (mBands.IsEmpty()) {
+    return mBounds.Area();
+  }
+
   uint64_t area = 0;
-  for (auto iter = RectIter(); !iter.Done(); iter.Next()) {
-    const nsRect& rect = iter.Get();
-    area += uint64_t(rect.Width()) * rect.Height();
+  for (const Band& band : mBands) {
+    uint32_t height = band.bottom - band.top;
+    for (const Strip& strip : band.mStrips) {
+      area += (strip.right - strip.left) * height;
+    }
   }
+
   return area;
 }
 
 nsRegion& nsRegion::ScaleRoundOut (float aXScale, float aYScale)
 {
   if (mozilla::gfx::FuzzyEqual(aXScale, 1.0f) &&
       mozilla::gfx::FuzzyEqual(aYScale, 1.0f)) {
     return *this;
   }
 
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
-  for (int i=0; i<n; i++) {
-    nsRect rect = BoxToRect(boxes[i]);
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = iter.Get();
     rect.ScaleRoundOut(aXScale, aYScale);
-    boxes[i] = RectToBox(rect);
+    newRegion.AddRect(rect);
   }
 
-  pixman_region32_t region;
-  // This will union all of the rectangles and runs in about O(n lg(n))
-  pixman_region32_init_rects(&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 +527,71 @@ TransformRect(const mozilla::gfx::IntRec
         return mozilla::gfx::IntRect();
     }
 
     return intRect;
 }
 
 nsRegion& nsRegion::Transform (const mozilla::gfx::Matrix4x4 &aTransform)
 {
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
-  for (int i=0; i<n; i++) {
-    nsRect rect = BoxToRect(boxes[i]);
-    boxes[i] = RectToBox(nsIntRegion::ToRect(TransformRect(nsIntRegion::FromRect(rect), aTransform)));
+  nsRegion newRegion;
+  for (RectIterator iter = RectIterator(*this); !iter.Done(); iter.Next()) {
+    nsRect rect = nsIntRegion::ToRect(TransformRect(nsIntRegion::FromRect(iter.Get()), aTransform));
+    newRegion.AddRect(rect);
   }
 
-  pixman_region32_t region;
-  // This will union all of the rectangles and runs in about O(n lg(n))
-  pixman_region32_init_rects(&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 +611,22 @@ nsIntRegion nsRegion::ScaleToNearestPixe
   }
   return result;
 }
 
 nsIntRegion nsRegion::ScaleToOutsidePixels (float aScaleX, float aScaleY,
                                             nscoord aAppUnitsPerPixel) const
 {
   // make a copy of the region so that we can mutate it inplace
-  nsRegion region = *this;
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(&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 +635,61 @@ nsIntRegion nsRegion::ScaleToInsidePixel
    *
    * If it is, then the contained edge can be moved (in scaled pixels) to ensure that no
    * gap exists.
    *
    * Since this could be potentially expensive - O(n^2), we only attempt this algorithm
    * for the first rect.
    */
 
-  // make a copy of this region so that we can mutate it in place
-  nsRegion region = *this;
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(&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 +982,41 @@ nsRect nsRegion::GetLargestRectangle (co
   }
 
   return bestRect;
 }
 
 std::ostream& operator<<(std::ostream& stream, const nsRegion& m) {
   stream << "[";
 
-  int n;
-  pixman_box32_t *boxes = pixman_region32_rectangles(const_cast<pixman_region32_t*>(&m.mImpl), &n);
-  for (int i=0; i<n; i++) {
-    if (i != 0) {
+  bool first = true;
+  for (auto iter = m.RectIter(); !iter.Done(); iter.Next()) {
+    if (!first) {
       stream << "; ";
+    } else {
+      first = true;
     }
-    stream << boxes[i].x1 << "," << boxes[i].y1 << "," << boxes[i].x2 << "," << boxes[i].y2;
+    const nsRect& rect = iter.Get();
+    stream << rect.X() << "," << rect.Y() << "," << rect.XMost() << "," << rect.YMost();
   }
 
   stream << "]";
   return stream;
 }
 
+void
+nsRegion::OutputToStream(std::string aObjName, std::ostream& stream) const
+{
+  auto iter = RectIter();
+  nsRect r = iter.Get();
+  stream << "nsRegion " << aObjName << "(nsRect(" << r.X() << ", " << r.Y() << ", " << r.Width() << ", " << r.Height() << "));\n";
+  iter.Next();
+
+  for (; !iter.Done(); iter.Next()) {
+    nsRect r = iter.Get();
+    stream << aObjName << ".OrWith(nsRect(" << r.X() << ", " << r.Y() << ", " << r.Width() << ", " << r.Height() << "));\n";
+  }
+}
+
 nsCString
 nsRegion::ToString() const {
   return nsCString(mozilla::ToString(*this).c_str());
 }
--- a/gfx/src/nsRegion.h
+++ b/gfx/src/nsRegion.h
@@ -18,19 +18,27 @@
 #include "nsRect.h"                     // for mozilla::gfx::IntRect, nsRect
 #include "nsMargin.h"                   // for nsIntMargin
 #include "nsRegionFwd.h"                // for nsIntRegion
 #include "nsString.h"                   // for nsCString
 #include "xpcom-config.h"               // for CPP_THROW_NEW
 #include "mozilla/ArrayView.h"          // for ArrayView
 #include "mozilla/Move.h"               // for mozilla::Move
 #include "mozilla/gfx/MatrixFwd.h"      // for mozilla::gfx::Matrix4x4
+#include "mozilla/gfx/Logging.h"
+#include "nsTArray.h"
 
 #include "pixman.h"
 
+// Uncomment this line to get additional integrity checking.
+//#define DEBUG_REGIONS
+#ifdef DEBUG_REGIONS
+#include <sstream>
+#endif
+
 /* For information on the internal representation look at pixman-region.c
  *
  * This replaces an older homebrew implementation of nsRegion. The
  * representation used here may use more rectangles than nsRegion however, the
  * representation is canonical.  This means that there's no need for an
  * Optimize() method because for a paticular region there is only one
  * representation. This means that nsIntRegion will have more predictable
  * performance characteristics than the old nsRegion and should not become
@@ -42,129 +50,976 @@
 
 enum class VisitSide {
 	TOP,
 	BOTTOM,
 	LEFT,
 	RIGHT
 };
 
+namespace regiondetails {
+struct Band;
+}
+
+template<>
+struct nsTArray_CopyChooser<regiondetails::Band>
+{
+  typedef nsTArray_CopyWithConstructors<regiondetails::Band> Type;
+};
+
+namespace regiondetails {
+
+template<typename T, typename E>
+class UncheckedArray : public T
+{
+public:
+  using T::Elements;
+  using T::Length;
+
+  E & operator[](size_t aIndex) { return Elements()[aIndex]; }
+  const E& operator[](size_t aIndex) const { return Elements()[aIndex]; }
+  E& LastElement() { return Elements()[Length() - 1]; }
+  const E& LastElement() const { return Elements()[Length() - 1]; }
+
+  using iterator = E* ;
+  using const_iterator = const E*;
+
+  iterator begin() { return iterator(Elements()); }
+  const_iterator begin() const { return const_iterator(Elements()); }
+  const_iterator cbegin() const { return begin(); }
+  iterator end() { return iterator(Elements() + Length()); }
+  const_iterator end() const { return const_iterator(Elements() + Length()); }
+  const_iterator cend() const { return end(); }
+};
+
+struct Strip
+{
+  // Default constructor should never be called, but is required for
+  // vector::resize to compile.
+  Strip() { MOZ_CRASH(); }
+  Strip(int32_t aLeft, int32_t aRight) : left(aLeft), right(aRight) {}
+
+  bool operator != (const Strip& aOther) const
+  {
+    return left != aOther.left || right != aOther.right;
+  }
+
+  uint32_t Size() const
+  {
+    return right - left;
+  }
+
+  int32_t left;
+  int32_t right;
+};
+
+struct Band
+{
+  using Strip = regiondetails::Strip;
+#ifndef DEBUG
+  using StripArray = regiondetails::UncheckedArray<AutoTArray<Strip, 2>, Strip>;
+#else
+  using StripArray = AutoTArray<Strip, 2>;
+#endif
+
+  MOZ_IMPLICIT Band(const nsRect& aRect)
+    : top(aRect.Y()), bottom(aRect.YMost())
+  {
+    mStrips.AppendElement(Strip{ aRect.X(), aRect.XMost() });
+  }
+
+  Band(const Band& aOther)
+    : top(aOther.top), bottom(aOther.bottom)
+    , mStrips(aOther.mStrips)
+  {}
+  Band(const Band&& aOther)
+    : top(aOther.top), bottom(aOther.bottom)
+    , mStrips(std::move(aOther.mStrips))
+  {}
+
+  void InsertStrip(const Strip& aStrip)
+  {
+    for (size_t i = 0; i < mStrips.Length(); i++) {
+      Strip& strip = mStrips[i];
+      if (strip.left > aStrip.right) {
+        // Current strip is beyond aStrip, insert aStrip before.
+        mStrips.InsertElementAt(i, aStrip);
+        return;
+      }
+
+      if (strip.right < aStrip.left) {
+        // Current strip is before aStrip, try the next.
+        continue;
+      }
+
+      // Current strip intersects with aStrip, extend to the lext.
+      strip.left = std::min(strip.left, aStrip.left);
+
+      if (strip.right >= aStrip.right) {
+        // Current strip extends beyond aStrip, done.
+        return;
+      }
+
+      size_t next = i;
+      next++;
+      // Consume any subsequent strips intersecting with aStrip.
+      while (next < mStrips.Length() && mStrips[next].left <= aStrip.right) {
+        strip.right = mStrips[next].right;
+
+        mStrips.RemoveElementAt(next);
+      }
+
+      // Extend the strip in case the aStrip goes on beyond it.
+      strip.right = std::max(strip.right, aStrip.right);
+      return;
+    }
+    mStrips.AppendElement(aStrip);
+  }
+
+  void SubStrip(const Strip& aStrip)
+  {
+    for (size_t i = 0; i < mStrips.Length(); i++) {
+      Strip& strip = mStrips[i];
+      if (strip.left > aStrip.right) {
+        // Strip is entirely to the right of aStrip. Done.
+        return;
+      }
+
+      if (strip.right < aStrip.left) {
+        // Strip is entirely to the left of aStrip. Move on.
+        continue;
+      }
+
+      if (strip.left < aStrip.left) {
+        if (strip.right <= aStrip.right) {
+          strip.right = aStrip.left;
+          // This strip lies to the left of the start of aStrip.
+          continue;
+        }
+
+        // aStrip is completely contained by this strip.
+        Strip newStrip(aStrip.right, strip.right);
+        strip.right = aStrip.left;
+        if (i < mStrips.Length()) {
+          i++;
+          mStrips.InsertElementAt(i, newStrip);
+        } else {
+          mStrips.AppendElement(newStrip);
+        }
+        return;
+      }
+
+      // This strip lies to the right of the start of aStrip.
+      if (strip.right <= aStrip.right) {
+        // aStrip completely contains this strip.
+        mStrips.RemoveElementAt(i);
+        // Make sure we evaluate the strip now at i. This loop will increment.
+        i--;
+        continue;
+      }
+      strip.left = aStrip.right;
+      return;
+    }
+  }
+
+  bool Intersects(const Strip& aStrip) const
+  {
+    for (const Strip& strip : mStrips) {
+      if (strip.left >= aStrip.right) {
+        return false;
+      }
+
+      if (strip.right <= aStrip.left) {
+        continue;
+      }
+
+      return true;
+    }
+    return false;
+  }
+
+  bool IntersectStripBounds(Strip& aStrip) const
+  {
+    bool intersected = false;
+
+    int32_t rightMost;
+    for (const Strip& strip : mStrips) {
+      if (strip.left > aStrip.right) {
+        break;
+      }
+
+      if (strip.right <= aStrip.left) {
+        continue;
+      }
+
+      if (!intersected) {
+        // First intersection, this is where the left side begins.
+        aStrip.left = std::max(aStrip.left, strip.left);
+      }
+
+      intersected = true;
+      // Expand to the right for each intersecting strip found.
+      rightMost = std::min(strip.right, aStrip.right);
+    }
+
+    if (intersected) {
+      aStrip.right = rightMost;
+    }
+    else {
+      aStrip.right = aStrip.left = 0;
+    }
+    return intersected;
+  }
+
+  bool ContainsStrip(const Strip& aStrip) const
+  {
+    for (const Strip& strip : mStrips) {
+      if (strip.left > aStrip.left) {
+        return false;
+      }
+
+      if (strip.right >= aStrip.right) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  bool EqualStrips(const Band& aBand) const
+  {
+    if (mStrips.Length() != aBand.mStrips.Length()) {
+      return false;
+    }
+
+    for (auto iter1 = mStrips.begin(), iter2 = aBand.mStrips.begin();
+      iter1 != mStrips.end(); iter1++, iter2++)
+    {
+      if (*iter1 != *iter2) {
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  void IntersectStrip(const Strip& aStrip)
+  {
+    size_t i = 0;
+
+    while (i < mStrips.Length()) {
+      Strip& strip = mStrips[i];
+      if (strip.right <= aStrip.left) {
+        mStrips.RemoveElementAt(i);
+        continue;
+      }
+
+      if (strip.left >= aStrip.right) {
+        mStrips.TruncateLength(i);
+        return;
+      }
+
+      strip.left = std::max(aStrip.left, strip.left);
+      strip.right = std::min(aStrip.right, strip.right);
+      i++;
+    }
+  }
+
+  void IntersectStrips(const Band& aOther)
+  {
+    auto iter = mStrips.begin();
+    auto iterOther = aOther.mStrips.begin();
+
+    StripArray newStrips;
+
+    // This function finds the intersection between two sets of strips.
+    while (true) {
+      while (true) {
+        while (iter != mStrips.end() && iter->right <= iterOther->left) {
+          // Increment our current strip until it ends beyond aOther's current strip.
+          iter++;
+        }
+
+        if (iter == mStrips.end()) {
+          // End of our strips. Done.
+          break;
+        }
+
+        while (iterOther != aOther.mStrips.end() && iterOther->right <= iter->left) {
+          // Increment aOther's current strip until it lies beyond our current strip.
+          iterOther++;
+        }
+
+        if (iterOther == aOther.mStrips.end()) {
+          // End of aOther's strips. Done.
+          break;
+        }
+
+        if (iterOther->left < iter->right) {
+          // Intersection!
+          break;
+        }
+      }
+
+      if (iter == mStrips.end() || iterOther == aOther.mStrips.end()) {
+        break;
+      }
+
+      newStrips.AppendElement(Strip(std::max(iter->left, iterOther->left), std::min(iterOther->right, iter->right)));
+
+      if (iterOther->right < iter->right) {
+        iterOther++;
+        if (iterOther == aOther.mStrips.end()) {
+          break;
+        }
+      } else {
+        iter++;
+      }
+    }
+
+    mStrips = newStrips;
+  }
+
+  bool Intersects(const Band& aOther) const
+  {
+    auto iter = mStrips.begin();
+    auto iterOther = aOther.mStrips.begin();
+
+    // This function finds the intersection between two sets of strips.
+    while (true) {
+      while (true) {
+        while (iter != mStrips.end() && iter->right <= iterOther->left) {
+          // Increment our current strip until it ends beyond aOther's current strip.
+          iter++;
+        }
+
+        if (iter == mStrips.end()) {
+          // End of our strips. Done.
+          break;
+        }
+
+        while (iterOther != aOther.mStrips.end() && iterOther->right <= iter->left) {
+          // Increment aOther's current strip until it lies beyond our current strip.
+          iterOther++;
+        }
+
+        if (iterOther == aOther.mStrips.end()) {
+          // End of aOther's strips. Done.
+          break;
+        }
+
+        if (iterOther->left < iter->right) {
+          // Intersection!
+          break;
+        }
+      }
+
+      if (iter == mStrips.end()|| iterOther == aOther.mStrips.end()) {
+        break;
+      }
+
+      return true;
+    }
+    return false;
+  }
+
+  void SubStrips(const Band& aOther)
+  {
+    size_t idx = 0;
+    auto iterOther = aOther.mStrips.begin();
+
+    // This function finds the intersection between two sets of strips.
+    while (true) {
+      while (true) {
+        while (idx < mStrips.Length() && mStrips[idx].right <= iterOther->left) {
+          // Increment our current strip until it ends beyond aOther's current strip.
+          idx++;
+        }
+
+        if (idx == mStrips.Length()) {
+          // End of our strips. Done.
+          break;
+        }
+
+        while (iterOther != aOther.mStrips.end() && iterOther->right <= mStrips[idx].left) {
+          // Increment aOther's current strip until it lies beyond our current strip.
+          iterOther++;
+        }
+
+        if (iterOther == aOther.mStrips.end()) {
+          // End of aOther's strips. Done.
+          break;
+        }
+
+        if (iterOther->left < mStrips[idx].right) {
+          // Intersection!
+          break;
+        }
+      }
+
+      if (idx == mStrips.Length() || iterOther == aOther.mStrips.end()) {
+        break;
+      }
+
+      if (mStrips[idx].left < iterOther->left) {
+        size_t oldIdx = idx;
+        // Our strip starts beyond other's
+        if (mStrips[idx].right > iterOther->right) {
+          // Our strip ends beyond other's as well.
+          Strip newStrip(mStrips[idx]);
+          newStrip.left = iterOther->right;
+          mStrips.InsertElementAt(idx + 1, newStrip);
+          idx++;
+        }
+        mStrips[oldIdx].right = iterOther->left;
+        // Either idx was just incremented, or the current index no longer intersects with iterOther.
+        continue;
+      } else if (mStrips[idx].right > iterOther->right) {
+        mStrips[idx].left = iterOther->right;
+        // Current strip no longer intersects, continue.
+        iterOther++;
+        if (iterOther == aOther.mStrips.end()) {
+          break;
+        }
+        continue;
+      }
+
+      // Our current strip is completely contained by the other strip.
+      mStrips.RemoveElementAt(idx);
+    }
+  }
+
+  int32_t top;
+  int32_t bottom;
+  StripArray mStrips;
+};
+}
+
 class nsRegion
 {
 public:
+  using Band = regiondetails::Band;
+  using Strip = regiondetails::Strip;
+#ifndef DEBUG
+  using BandArray = regiondetails::UncheckedArray<nsTArray<Band>, Band>;
+  using StripArray = regiondetails::UncheckedArray<AutoTArray<Strip, 2>, Strip>;
+#else
+  using BandArray = nsTArray<Band>;
+  using StripArray = AutoTArray<Strip, 2>;
+#endif
+
   typedef nsRect RectType;
   typedef nsPoint PointType;
   typedef nsMargin MarginType;
 
-  nsRegion () { pixman_region32_init(&mImpl); }
-  MOZ_IMPLICIT nsRegion (const nsRect& aRect) { pixman_region32_init_rect(&mImpl,
-                                                                          aRect.X(),
-                                                                          aRect.Y(),
-                                                                          aRect.Width(),
-                                                                          aRect.Height()); }
-  explicit nsRegion (mozilla::gfx::ArrayView<pixman_box32_t> aRects)
+  nsRegion() { }
+  MOZ_IMPLICIT nsRegion(const nsRect& aRect) {
+    mBounds = aRect;
+  }
+  explicit nsRegion(mozilla::gfx::ArrayView<pixman_box32_t> aRects)
   {
-    pixman_region32_init_rects(&mImpl, aRects.Data(), aRects.Length());
+    for (uint32_t i = 0; i < aRects.Length(); i++) {
+      AddRect(BoxToRect(aRects[i]));
+    }
   }
-  nsRegion (const nsRegion& aRegion) { pixman_region32_init(&mImpl); pixman_region32_copy(&mImpl,aRegion.Impl()); }
-  nsRegion (nsRegion&& aRegion) { mImpl = aRegion.mImpl; pixman_region32_init(&aRegion.mImpl); }
-  nsRegion& operator = (nsRegion&& aRegion) {
-      pixman_region32_fini(&mImpl);
-      mImpl = aRegion.mImpl;
-      pixman_region32_init(&aRegion.mImpl);
-      return *this;
+
+  nsRegion(const nsRegion& aRegion) { Copy(aRegion); }
+  nsRegion(nsRegion&& aRegion) { mBands.SwapElements(aRegion.mBands); mBounds = aRegion.mBounds; aRegion.SetEmpty(); }
+  nsRegion& operator =(nsRegion&& aRegion) {
+    mBands.SwapElements(aRegion.mBands);
+    mBounds = aRegion.mBounds;
+    aRegion.SetEmpty();
+    return *this;
   }
- ~nsRegion () { pixman_region32_fini(&mImpl); }
-  nsRegion& operator = (const nsRect& aRect) { Copy (aRect); return *this; }
-  nsRegion& operator = (const nsRegion& aRegion) { Copy (aRegion); return *this; }
+  nsRegion& operator =(const nsRect& aRect) { Copy(aRect); return *this; }
+  nsRegion& operator =(const nsRegion& aRegion) { Copy(aRegion); return *this; }
   bool operator==(const nsRegion& aRgn) const
   {
     return IsEqual(aRgn);
   }
   bool operator!=(const nsRegion& aRgn) const
   {
     return !(*this == aRgn);
   }
 
   friend std::ostream& operator<<(std::ostream& stream, const nsRegion& m);
+  void OutputToStream(std::string aObjName, std::ostream& stream) const;
 
-  void Swap(nsRegion* aOther)
+  static
+    nsresult InitStatic()
+  {
+    return NS_OK;
+  }
+
+  static
+    void ShutdownStatic() {}
+
+private:
+#ifdef DEBUG_REGIONS
+  class OperationStringGenerator
+  {
+  public:
+    virtual ~OperationStringGenerator() {}
+
+    virtual void OutputOp() = 0;
+  };
+#endif
+public:
+
+  void AssertStateInternal() const;
+  void AssertState() const {
+#ifdef DEBUG_REGIONS
+    AssertStateInternal();
+#endif
+  }
+
+private:
+  void And(BandArray& aOut, const BandArray& aIn1, const BandArray& aIn2)
   {
-    pixman_region32_t tmp = mImpl;
-    mImpl = aOther->mImpl;
-    aOther->mImpl = tmp;
+    size_t idx = 0;
+    size_t idxOther = 0;
+
+    // This algorithm essentially forms a new list of bands, by iterating over
+    // both regions' lists of band simultaneously, and building a new band
+    // wherever the two regions intersect.
+    while (true) {
+      while (true) {
+        while (idx != aIn1.Length() && aIn1[idx].bottom <= aIn2[idxOther].top) {
+          // Increment our current band until it ends beyond aOther's current band.
+          idx++;
+        }
+
+        if (idx == aIn1.Length()) {
+          // This region is out of bands, the other region's future bands are ignored.
+          break;
+        }
+
+        while (idxOther != aIn2.Length() && aIn2[idxOther].bottom <= aIn1[idx].top) {
+          // Increment aOther's current band until it ends beyond our current band.
+          idxOther++;
+        }
+
+        if (idxOther == aIn2.Length()) {
+          // The other region's bands are all processed, all our future bands are ignored.
+          break;
+        }
+
+        if (aIn2[idxOther].top < aIn1[idx].bottom) {
+          // We know the other band's bottom lies beyond our band's top because
+          // otherwise we would've incremented above. Intersecting bands found.
+          break;
+        }
+      }
+
+      if (idx == aIn1.Length() || idxOther == aIn2.Length()) {
+        // The above loop executed a break because we're done.
+        break;
+      }
+
+      Band newBand(aIn1[idx]);
+      // The new band is the intersection of the two current bands from both regions.
+      newBand.top = std::max(aIn1[idx].top, aIn2[idxOther].top);
+      newBand.bottom = std::min(aIn1[idx].bottom, aIn2[idxOther].bottom);
+      newBand.IntersectStrips(aIn2[idxOther]);
+
+      if (newBand.mStrips.Length()) {
+        // The intersecting area of the bands had overlapping strips, if it is
+        // identical to the band above it merge, otherwise append.
+        if (aOut.Length() && aOut.LastElement().bottom == newBand.top &&
+          aOut.LastElement().EqualStrips(newBand)) {
+          aOut.LastElement().bottom = newBand.bottom;
+        } else {
+          aOut.AppendElement(std::move(newBand));
+        }
+      }
+
+      if (aIn2[idxOther].bottom < aIn1[idx].bottom) {
+        idxOther++;
+        if (idxOther == aIn2.Length()) {
+          // Since we will access idxOther the next iteration, check if we're not done.
+          break;
+        }
+      } else {
+        // No need to check here since we do at the beginning of the next iteration.
+        idx++;
+      }
+    }
   }
 
-  void AndWith(const nsRegion& aOther)
+public:
+  nsRegion& AndWith(const nsRegion& aRegion)
   {
-    And(*this, aOther);
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorAndWith : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorAndWith(nsRegion& aRegion, const nsRegion& aOtherRegion)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mOtherRegion(aOtherRegion)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorAndWith()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r1", stream);
+        mOtherRegion.OutputToStream("r2", stream);
+        stream << "r1.AndWith(r2);\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsRegion mOtherRegion;
+    };
+
+    OperationStringGeneratorAndWith opGenerator(*this, aRegion);
+#endif
+    if (mBounds.IsEmpty()) {
+      // Region is empty, stays empty.
+      return *this;
+    }
+
+    if (aRegion.IsEmpty()) {
+      SetEmpty();
+      return *this;
+    }
+
+    if (aRegion.mBands.IsEmpty()) {
+      // Other region is a rect.
+      return AndWith(aRegion.mBounds);
+    }
+
+    if (mBands.IsEmpty()) {
+      mBands.AppendElement(mBounds);
+    }
+
+    BandArray newBands;
+
+    And(newBands, mBands, aRegion.mBands);
+
+    mBands = std::move(newBands);
+    if (!mBands.Length()) {
+      mBounds = nsRect();
+    } else {
+      mBounds = CalculateBounds();
+    }
+
+    EnsureSimplified();
+    AssertState();
+    return *this;
   }
-  void AndWith(const nsRect& aOther)
+
+  nsRegion& AndWith(const nsRect& aRect)
   {
-    And(*this, aOther);
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorAndWith : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorAndWith(nsRegion& aRegion, const nsRect& aRect)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorAndWith()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r", stream);
+        stream << "r.AndWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsRect mRect;
+    };
+
+    OperationStringGeneratorAndWith opGenerator(*this, aRect);
+#endif
+    if (aRect.IsEmpty()) {
+      SetEmpty();
+      return *this;
+    }
+
+    if (mBands.IsEmpty()) {
+      mBounds = mBounds.Intersect(aRect);
+      return *this;
+    }
+
+    size_t idx = 0;
+
+    size_t removeStart = 0;
+
+    // This removes all bands that do not intersect with aRect, and intersects
+    // the remaining ones with aRect.
+
+    // Start by figuring out how much to remove from the start.
+    while (idx != mBands.Length() && mBands[idx].bottom <= aRect.Y()) {
+      idx++;
+    }
+
+    // We'll remove these later to avoid needless copying in the array.
+    removeStart = idx;
+
+    while (idx != mBands.Length()) {
+      if (mBands[idx].top >= aRect.YMost()) {
+        mBands.TruncateLength(idx);
+        break;
+      }
+
+      mBands[idx].top = std::max(mBands[idx].top, aRect.Y());
+      mBands[idx].bottom = std::min(mBands[idx].bottom, aRect.YMost());
+
+      mBands[idx].IntersectStrip(Strip(aRect.X(), aRect.XMost()));
+
+      if (!mBands[idx].mStrips.Length()) {
+        mBands.RemoveElementAt(idx);
+      } else {
+        if (idx > removeStart) {
+          CompressBefore(idx);
+        }
+        idx++;
+      }
+    }
+
+    if (removeStart) {
+      mBands.RemoveElementsAt(0, removeStart);
+    }
+
+    if (mBands.Length()) {
+      mBounds = CalculateBounds();
+    } else {
+      mBounds.SetEmpty();
+    }
+    EnsureSimplified();
+    AssertState();
+    return *this;
   }
-  nsRegion& And(const nsRegion& aRgn1,   const nsRegion& aRgn2)
+  nsRegion& And(const nsRegion& aRgn1, const nsRegion& aRgn2)
   {
-    pixman_region32_intersect(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+    if (&aRgn1 == this) {
+      return AndWith(aRgn2);
+    }
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorAnd : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorAnd(nsRegion& aRegion, const nsRegion& aRegion1, const nsRegion& aRegion2)
+        : mRegion(&aRegion), mRegion1(aRegion1), mRegion2(aRegion2)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorAnd()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegion1.OutputToStream("r1", stream);
+        mRegion2.OutputToStream("r2", stream);
+        stream << "nsRegion r3;\nr3.And(r1, r2);\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegion1;
+      nsRegion mRegion2;
+    };
+
+    OperationStringGeneratorAnd opGenerator(*this, aRgn1, aRgn2);
+#endif
+    mBands.Clear();
+
+    if (aRgn1.IsEmpty() || aRgn2.IsEmpty()) {
+      mBounds.SetEmpty();
+      return *this;
+    }
+
+    if (aRgn1.mBands.IsEmpty() && aRgn2.mBands.IsEmpty()) {
+      mBounds = aRgn1.mBounds.Intersect(aRgn2.mBounds);
+      return *this;
+    } else if (aRgn1.mBands.IsEmpty()) {
+      return And(aRgn2, aRgn1.mBounds);
+    } else if (aRgn2.mBands.IsEmpty()) {
+      return And(aRgn1, aRgn2.mBounds);
+    }
+
+    And(mBands, aRgn1.mBands, aRgn2.mBands);
+
+    if (!mBands.Length()) {
+      mBounds = nsRect();
+    } else {
+      mBounds = CalculateBounds();
+    }
+
+    EnsureSimplified();
+    AssertState();
     return *this;
   }
   nsRegion& And(const nsRect& aRect, const nsRegion& aRegion)
   {
     return And(aRegion, aRect);
   }
   nsRegion& And(const nsRegion& aRegion, const nsRect& aRect)
   {
-    pixman_region32_intersect_rect(&mImpl, aRegion.Impl(), aRect.X(), aRect.Y(), aRect.Width(), aRect.Height());
+    if (&aRegion == this) {
+      return AndWith(aRect);
+    }
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorAnd : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorAnd(nsRegion& aThisRegion, const nsRegion& aRegion, const nsRect& aRect)
+        : mThisRegion(&aThisRegion), mRegion(aRegion), mRect(aRect)
+      {
+        aThisRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorAnd()
+      {
+        mThisRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegion.OutputToStream("r", stream);
+        stream << "nsRegion r2;\nr.And(r2, nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion* mThisRegion;
+      nsRegion mRegion;
+      nsRect mRect;
+    };
+
+    OperationStringGeneratorAnd opGenerator(*this, aRegion, aRect);
+#endif
+    mBands.Clear();
+
+    if (aRect.IsEmpty()) {
+      mBounds.SetEmpty();
+      return *this;
+    }
+
+    if (aRegion.mBands.IsEmpty()) {
+      mBounds = aRegion.mBounds.Intersect(aRect);
+      return *this;
+    }
+
+    size_t idx = 0;
+    const BandArray& bands = aRegion.mBands;
+
+    mBands.SetCapacity(bands.Length() + 3);
+    while (idx != bands.Length()) {
+      // Ignore anything before.
+      if (bands[idx].bottom <= aRect.Y()) {
+        idx++;
+        continue;
+      }
+      // We're done once we've reached the bottom.
+      if (bands[idx].top >= aRect.YMost()) {
+        break;
+      }
+
+      // Now deal with bands actually intersecting the rectangle.
+      Band newBand(bands[idx]);
+      newBand.top = std::max(bands[idx].top, aRect.Y());
+      newBand.bottom = std::min(bands[idx].bottom, aRect.YMost());
+
+      newBand.IntersectStrip(Strip(aRect.X(), aRect.XMost()));
+
+      if (newBand.mStrips.Length()) {
+        if (!mBands.IsEmpty() &&
+            newBand.top == mBands.LastElement().bottom &&
+            newBand.EqualStrips(mBands.LastElement())) {
+          mBands.LastElement().bottom = newBand.bottom;
+        } else {
+          mBands.AppendElement(std::move(newBand));
+        }
+      }
+      idx++;
+    }
+
+    if (mBands.Length()) {
+      mBounds = CalculateBounds();
+    } else {
+      mBounds.SetEmpty();
+    }
+
+    EnsureSimplified();
+    AssertState();
     return *this;
   }
   nsRegion& And(const nsRect& aRect1, const nsRect& aRect2)
   {
-    nsRect TmpRect;
+    nsRect tmpRect;
 
-    TmpRect.IntersectRect(aRect1, aRect2);
-    return Copy(TmpRect);
+    tmpRect.IntersectRect(aRect1, aRect2);
+    return Copy(tmpRect);
   }
 
   nsRegion& OrWith(const nsRegion& aOther)
   {
-    return Or(*this, aOther);
+    for (RectIterator idx(aOther); !idx.Done(); idx.Next()) {
+      AddRect(idx.Get());
+    }
+    return *this;
   }
   nsRegion& OrWith(const nsRect& aOther)
   {
-    return Or(*this, aOther);
+    AddRect(aOther);
+    return *this;
   }
   nsRegion& Or(const nsRegion& aRgn1, const nsRegion& aRgn2)
   {
-    pixman_region32_union(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+    if (&aRgn1 != this) {
+      *this = aRgn1;
+    }
+    for (RectIterator idx(aRgn2); !idx.Done(); idx.Next()) {
+      AddRect(idx.Get());
+    }
     return *this;
   }
   nsRegion& Or(const nsRegion& aRegion, const nsRect& aRect)
   {
-    pixman_region32_union_rect(&mImpl, aRegion.Impl(), aRect.X(), aRect.Y(), aRect.Width(), aRect.Height());
+    if (&aRegion != this) {
+      *this = aRegion;
+    }
+    AddRect(aRect);
     return *this;
   }
   nsRegion& Or(const nsRect& aRect, const nsRegion& aRegion)
   {
     return  Or(aRegion, aRect);
   }
   nsRegion& Or(const nsRect& aRect1, const nsRect& aRect2)
   {
-    Copy (aRect1);
-    return Or (*this, aRect2);
+    Copy(aRect1);
+    return Or(*this, aRect2);
   }
 
   nsRegion& XorWith(const nsRegion& aOther)
   {
     return Xor(*this, aOther);
   }
   nsRegion& XorWith(const nsRect& aOther)
   {
     return Xor(*this, aOther);
   }
-  nsRegion& Xor(const nsRegion& aRgn1,   const nsRegion& aRgn2)
+  nsRegion& Xor(const nsRegion& aRgn1, const nsRegion& aRgn2)
   {
     // this could be implemented better if pixman had direct
     // support for xoring regions.
     nsRegion p;
     p.Sub(aRgn1, aRgn2);
     nsRegion q;
     q.Sub(aRgn2, aRgn1);
     return Or(p, q);
@@ -177,70 +1032,760 @@ public:
   {
     return Xor(nsRegion(aRect), aRegion);
   }
   nsRegion& Xor(const nsRect& aRect1, const nsRect& aRect2)
   {
     return Xor(nsRegion(aRect1), nsRegion(aRect2));
   }
 
-  nsRegion ToAppUnits (nscoord aAppUnitsPerPixel) const;
+  nsRegion ToAppUnits(nscoord aAppUnitsPerPixel) const;
+
+  nsRegion& SubWith(const nsRegion& aOther)
+  {
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorSubWith : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorSubWith(nsRegion& aRegion, const nsRegion& aOtherRegion)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mOtherRegion(aOtherRegion)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorSubWith()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r1", stream);
+        mOtherRegion.OutputToStream("r2", stream);
+        stream << "r1.SubWith(r2);\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsRegion mOtherRegion;
+    };
+
+    OperationStringGeneratorSubWith opGenerator(*this, aOther);
+#endif
+
+    if (mBounds.IsEmpty()) {
+      return *this;
+    }
+
+    if (aOther.mBands.IsEmpty()) {
+      return SubWith(aOther.mBounds);
+    }
+
+    if (mBands.IsEmpty()) {
+      mBands.AppendElement(Band(mBounds));
+    }
+
+    size_t idx = 0;
+    size_t idxOther = 0;
+    while (idx < mBands.Length()) {
+      while (true) {
+        while (idx != mBands.Length() && mBands[idx].bottom <= aOther.mBands[idxOther].top) {
+          // Increment our current band until it ends beyond aOther's current band.
+          idx++;
+        }
+
+        if (idx == mBands.Length()) {
+          // This region is out of bands, the other region's future bands are ignored.
+          break;
+        }
+
+        while (idxOther != aOther.mBands.Length() && aOther.mBands[idxOther].bottom <= mBands[idx].top) {
+          // Increment aOther's current band until it ends beyond our current band.
+          idxOther++;
+        }
+
+        if (idxOther == aOther.mBands.Length()) {
+          // The other region's bands are all processed, all our future bands are ignored.
+          break;
+        }
 
+        if (aOther.mBands[idxOther].top < mBands[idx].bottom) {
+          // We know the other band's bottom lies beyond our band's top because
+          // otherwise we would've incremented above. Intersecting bands found.
+          break;
+        }
+      }
+
+      if (idx == mBands.Length() || idxOther == aOther.mBands.Length()) {
+        // The above loop executed a break because we're done.
+        break;
+      }
+
+      const Band& bandOther = aOther.mBands[idxOther];
+
+      if (!mBands[idx].Intersects(bandOther)) {
+        if (mBands[idx].bottom < bandOther.bottom) {
+          idx++;
+        } else {
+          idxOther++;
+          if (idxOther == aOther.mBands.Length()) {
+            break;
+          }
+        }
+        continue;
+      }
+
+      // These bands actually intersect.
+      if (mBands[idx].top < bandOther.top) {
+        mBands.InsertElementAt(idx + 1, Band(mBands[idx]));
+        mBands[idx].bottom = bandOther.top;
+        idx++;
+        mBands[idx].top = bandOther.top;
+      }
+
+      // mBands[idx].top >= bandOther.top;
+      if (mBands[idx].bottom <= bandOther.bottom) {
+        mBands[idx].SubStrips(bandOther);
+        if (mBands[idx].mStrips.IsEmpty()) {
+          mBands.RemoveElementAt(idx);
+        } else {
+          CompressBefore(idx);
+          idx++;
+          // The band before us just changed, it may be identical now.
+          CompressBefore(idx);
+        }
+        continue;
+      }
+
+      // mBands[idx].bottom > bandOther.bottom
+      Band newBand = mBands[idx];
+      newBand.SubStrips(bandOther);
+
+      if (!newBand.mStrips.IsEmpty()) {
+        mBands.InsertElementAt(idx, newBand);
+        mBands[idx].bottom = bandOther.bottom;
+        CompressBefore(idx);
+        idx++;
+      }
+
+      mBands[idx].top = bandOther.bottom;
+
+      idxOther++;
+      if (idxOther == aOther.mBands.Length()) {
+        break;
+      }
+    }
+
+    if (mBands.IsEmpty()) {
+      mBounds.SetEmpty();
+    } else {
+      mBounds = CalculateBounds();
+    }
+
+    AssertState();
+    EnsureSimplified();
+    return *this;
+  }
   nsRegion& SubOut(const nsRegion& aOther)
   {
-    return Sub(*this, aOther);
+    return SubWith(aOther);
   }
   nsRegion& SubOut(const nsRect& aOther)
   {
-    return Sub(*this, aOther);
+    return SubWith(aOther);
   }
+
+private:
+  void AppendOrExtend(const Band& aNewBand)
+  {
+    if (aNewBand.mStrips.IsEmpty()) {
+      return;
+    }
+    if (mBands.IsEmpty()) {
+      mBands.AppendElement(aNewBand);
+      return;
+    }
+
+    if (mBands.LastElement().bottom == aNewBand.top && mBands.LastElement().EqualStrips(aNewBand)) {
+      mBands.LastElement().bottom = aNewBand.bottom;
+    } else {
+      mBands.AppendElement(aNewBand);
+    }
+  }
+  void AppendOrExtend(const Band&& aNewBand)
+  {
+    if (aNewBand.mStrips.IsEmpty()) {
+      return;
+    }
+    if (mBands.IsEmpty()) {
+      mBands.AppendElement(std::move(aNewBand));
+      return;
+    }
+
+    if (mBands.LastElement().bottom == aNewBand.top && mBands.LastElement().EqualStrips(aNewBand)) {
+      mBands.LastElement().bottom = aNewBand.bottom;
+    } else {
+      mBands.AppendElement(std::move(aNewBand));
+    }
+  }
+public:
   nsRegion& Sub(const nsRegion& aRgn1, const nsRegion& aRgn2)
   {
-    pixman_region32_subtract(&mImpl, aRgn1.Impl(), aRgn2.Impl());
+    if (&aRgn1 == this) {
+      return SubWith(aRgn2);
+    }
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorSub : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorSub(nsRegion& aRegion, const nsRegion& aRgn1, const nsRegion& aRgn2)
+        : mRegion(&aRegion), mRegion1(aRgn1), mRegion2(aRgn2)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorSub()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegion1.OutputToStream("r1", stream);
+        mRegion2.OutputToStream("r2", stream);
+        stream << "nsRegion r3;\nr3.Sub(r1, r2);\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion* mRegion;
+      nsRegion mRegion1;
+      nsRegion mRegion2;
+    };
+
+    OperationStringGeneratorSub opGenerator(*this, aRgn1, aRgn2);
+#endif
+
+    mBands.Clear();
+
+    if (aRgn1.mBounds.IsEmpty()) {
+      mBounds.SetEmpty();
+      return *this;
+    }
+
+    if (aRgn2.mBounds.IsEmpty()) {
+      Copy(aRgn1);
+      return *this;
+    }
+
+    if (aRgn1.mBands.IsEmpty() && aRgn2.mBands.IsEmpty()) {
+      return Sub(aRgn1.mBounds, aRgn2.mBounds);
+    } else if (aRgn1.mBands.IsEmpty()) {
+      return Sub(aRgn1.mBounds, aRgn2);
+    } else if (aRgn2.mBands.IsEmpty()) {
+      return Sub(aRgn1, aRgn2.mBounds);
+    }
+
+    const BandArray& bands1 = aRgn1.mBands;
+    const BandArray& bands2 = aRgn2.mBands;
+
+    size_t idx = 0;
+    size_t idxOther = 0;
+
+    // We iterate the source region's bands, subtracting the other regions bands from them as we
+    // move them into ours.
+    while (idx < bands1.Length()) {
+      while (idxOther < bands2.Length() && bands2[idxOther].bottom <= bands1[idx].top) {
+        // These other bands are irrelevant as they don't intersect with the
+        // band we're currently processing.
+        idxOther++;
+      }
+      if (idxOther == bands2.Length()) {
+        break;
+      }
+
+      const Band& other = bands2[idxOther];
+
+      // bands2[idxOther].bottom >= bands1[idx].top
+      Band origBand(bands1[idx]);
+      if (other.top >= origBand.bottom) {
+        // No intersecting bands, append and continue.
+        AppendOrExtend(origBand);
+        idx++;
+        continue;
+      }
+
+      // Push a band for an uncovered region above our band.
+      if (origBand.top < other.top) {
+        Band newBand(origBand);
+        newBand.bottom = other.top;
+        AppendOrExtend(std::move(newBand));
+      }
+
+      int32_t lastBottom = std::max(other.top, origBand.top);
+      while (idxOther < bands2.Length() && bands2[idxOther].top < origBand.bottom) {
+        const Band& other = bands2[idxOther];
+        Band newBand(origBand);
+        newBand.top = std::max(origBand.top, other.top);
+        newBand.bottom = std::min(origBand.bottom, other.bottom);
+
+        // If there was a gap, we need to add the original band there.
+        if (newBand.top > lastBottom) {
+          Band betweenBand(newBand);
+          betweenBand.top = lastBottom;
+          betweenBand.bottom = newBand.top;
+          AppendOrExtend(std::move(betweenBand));
+        }
+
+        lastBottom = newBand.bottom;
+        newBand.SubStrips(other);
+        AppendOrExtend(std::move(newBand));
+        idxOther++;
+      }
+      // Decrement other here so we are back at the last band in region 2
+      // that intersected.
+      idxOther--;
+
+      if (bands2[idxOther].bottom < origBand.bottom) {
+        // The last band in region2 that intersected ended before this one,
+        // we can copy the rest.
+        Band newBand(origBand);
+        newBand.top = bands2[idxOther].bottom;
+        AppendOrExtend(std::move(newBand));
+        idxOther++;
+      }
+      idx++;
+    }
+
+    // Copy any remaining bands, the first one may have to be extended to fit
+    // the last one added before. The rest can be unconditionally appended.
+    if (idx < bands1.Length()) {
+      AppendOrExtend(bands1[idx]);
+      idx++;
+    }
+
+    while (idx < bands1.Length()) {
+      mBands.AppendElement(bands1[idx]);
+      idx++;
+    }
+
+    if (mBands.IsEmpty()) {
+      mBounds.SetEmpty();
+    }
+    else {
+      mBounds = CalculateBounds();
+    }
+
+    AssertState();
+    EnsureSimplified();
+    return *this;
+  }
+
+private:
+  // Internal helper for executing subtraction.
+  void RunSubtraction(const nsRect& aRect)
+  {
+    Strip rectStrip(aRect.X(), aRect.XMost());
+
+    size_t idx = 0;
+
+    while (idx < mBands.Length()) {
+      if (mBands[idx].top >= aRect.YMost()) {
+        return;
+      }
+
+      if (mBands[idx].bottom <= aRect.Y()) {
+        // This band is entirely before aRect, move on.
+        idx++;
+        continue;
+      }
+
+      if (!mBands[idx].Intersects(Strip(aRect.X(), aRect.XMost()))) {
+        // This band does not intersect aRect horizontally. Move on.
+        idx++;
+        continue;
+      }
+
+      // This band intersects with aRect.
+
+      if (mBands[idx].top < aRect.Y()) {
+        // This band starts above the start of aRect, split the band into two
+        // along the intersection, and continue to the next iteration to process
+        // the one that now intersects exactly.
+        auto above = mBands.InsertElementAt(idx, Band(mBands[idx]));
+        above->bottom = aRect.Y();
+        idx++;
+        mBands[idx].top = aRect.Y();
+        // Continue to run the loop for the next band.
+        continue;
+      }
+
+      if (mBands[idx].bottom <= aRect.YMost()) {
+        // This band ends before the end of aRect.
+        mBands[idx].SubStrip(rectStrip);
+        if (mBands[idx].mStrips.Length()) {
+          CompressAdjacentBands(idx);
+        } else {
+          mBands.RemoveElementAt(idx);
+        }
+        continue;
+      }
+
+      // This band extends beyond aRect.
+      Band newBand = mBands[idx];
+      newBand.SubStrip(rectStrip);
+      newBand.bottom = aRect.YMost();
+      mBands[idx].top = aRect.YMost();
+
+      if (newBand.mStrips.Length()) {
+        if (idx && mBands[idx - 1].bottom == newBand.top && newBand.EqualStrips(mBands[idx - 1])) {
+          mBands[idx - 1].bottom = aRect.YMost();
+        } else {
+          mBands.InsertElementAt(idx, std::move(newBand));
+        }
+      }
+
+      return;
+    }
+  }
+
+public:
+  nsRegion& SubWith(const nsRect& aRect) {
+    if (!mBounds.Intersects(aRect)) {
+      return *this;
+    }
+
+    if (aRect.Contains(mBounds)) {
+      SetEmpty();
+      return *this;
+    }
+
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorSubWith : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorSubWith(nsRegion& aRegion, const nsRect& aRect)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorSubWith()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r", stream);
+        stream << "r.SubWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsRect mRect;
+    };
+
+    OperationStringGeneratorSubWith opGenerator(*this, aRect);
+#endif
+
+    if (mBands.IsEmpty()) {
+      mBands.AppendElement(Band(mBounds));
+    }
+
+    RunSubtraction(aRect);
+
+    if (aRect.x <= mBounds.x || aRect.y <= mBounds.y ||
+        aRect.XMost() >= mBounds.XMost() || aRect.YMost() >= mBounds.YMost()) {
+      mBounds = CalculateBounds();
+    }
+    EnsureSimplified();
+    AssertState();
     return *this;
   }
   nsRegion& Sub(const nsRegion& aRegion, const nsRect& aRect)
   {
-    return Sub(aRegion, nsRegion(aRect));
+    if (aRect.Contains(aRegion.mBounds)) {
+      SetEmpty();
+      return *this;
+    }
+    if (&aRegion == this) {
+      return SubWith(aRect);
+    }
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorSub : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorSub(nsRegion& aRegion, const nsRegion& aRegionOther, const nsRect& aRect)
+        : mRegion(&aRegion), mRegionOther(aRegionOther), mRect(aRect)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorSub()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionOther.OutputToStream("r1", stream);
+        stream << "nsRegion r2;\nr2.Sub(r1, nsRect(" << mRect.X() << ", " << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height() << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionOther;
+      nsRect mRect;
+    };
+
+    OperationStringGeneratorSub opGenerator(*this, aRegion, aRect);
+#endif
+
+    mBands.Clear();
+
+    if (aRegion.mBounds.IsEmpty()) {
+      mBounds.SetEmpty();
+      return *this;
+    }
+
+    if (aRect.IsEmpty()) {
+      Copy(aRegion);
+      return *this;
+    }
+
+    if (aRegion.mBands.IsEmpty()) {
+      Copy(aRegion.mBounds);
+      return SubWith(aRect);
+    }
+
+    const BandArray& bands = aRegion.mBands;
+
+    size_t idx = 0;
+
+    Strip strip(aRect.X(), aRect.XMost());
+
+    mBands.SetCapacity(bands.Length() + 3);
+
+    // Process all bands that lie before aRect.
+    while (idx < bands.Length() && bands[idx].bottom <= aRect.Y()) {
+      mBands.AppendElement(bands[idx]);
+      idx++;
+    }
+
+    // This band's bottom lies beyond aRect.
+    if (idx < bands.Length() && bands[idx].top < aRect.Y()) {
+      Band newBand(bands[idx]);
+      if (bands[idx].Intersects(strip)) {
+        newBand.bottom = aRect.Y();
+      } else {
+        idx++;
+      }
+      mBands.AppendElement(std::move(newBand));
+    }
+
+    // This tracks whether the band when we -exit- the next loop intersected the rectangle.
+    bool didIntersect = false;
+
+    while (idx < bands.Length() && bands[idx].top < aRect.YMost()) {
+      // Process all bands intersecting with aRect.
+      if (!bands[idx].Intersects(strip)) {
+        AppendOrExtend(bands[idx]);
+        idx++;
+        didIntersect = false;
+        continue;
+      }
+
+      didIntersect = true;
+      Band newBand(bands[idx]);
+      newBand.top = std::max(newBand.top, aRect.Y());
+      newBand.bottom = std::min(newBand.bottom, aRect.YMost());
+      newBand.SubStrip(strip);
+      AppendOrExtend(std::move(newBand));
+      idx++;
+    }
+
+    if (didIntersect) {
+      if (aRect.YMost() < bands[idx - 1].bottom) {
+        // If this band does not intersect the loop above has already added the
+        // whole unmodified band.
+        Band newBand(bands[idx - 1]);
+        newBand.top = aRect.YMost();
+        AppendOrExtend(std::move(newBand));
+      }
+    }
+
+    // Now process all bands beyond aRect.
+    if (idx < bands.Length()) {
+      AppendOrExtend(bands[idx]);
+      idx++;
+    }
+
+    mBands.AppendElements(bands.Elements() + idx, bands.Length() - idx);
+
+    if (mBands.IsEmpty()) {
+      mBounds.SetEmpty();
+    } else {
+      mBounds = CalculateBounds();
+    }
+
+    AssertState();
+    EnsureSimplified();
+    return *this;
   }
   nsRegion& Sub(const nsRect& aRect, const nsRegion& aRegion)
   {
-    return Sub(nsRegion(aRect), aRegion);
+    Copy(aRect);
+    return SubWith(aRegion);
   }
   nsRegion& Sub(const nsRect& aRect1, const nsRect& aRect2)
   {
     Copy(aRect1);
-    return Sub(*this, aRect2);
+    return SubWith(aRect2);
   }
 
   /**
-   * Returns true iff the given point is inside the region. A region
+   * Returns true if the given point is inside the region. A region
    * created from a rect (x=0, y=0, w=100, h=100) will NOT contain
    * the point x=100, y=100.
    */
-  bool Contains (int aX, int aY) const
+  bool Contains(int aX, int aY) const
   {
-    return pixman_region32_contains_point(Impl(), aX, aY, nullptr);
-  }
-  bool Contains (const nsRect& aRect) const
-  {
-    pixman_box32_t box = RectToBox(aRect);
-    return pixman_region32_contains_rectangle(Impl(), &box) == PIXMAN_REGION_IN;
+    if (mBands.IsEmpty()) {
+      return mBounds.Contains(aX, aY);
+    }
+
+    auto iter = mBands.begin();
+
+    while (iter != mBands.end()) {
+      if (iter->bottom <= aY) {
+        iter++;
+        continue;
+      }
+
+      if (iter->top > aY) {
+        return false;
+      }
+
+      if (iter->ContainsStrip(Strip(aX, aX + 1))) {
+        return true;
+      }
+      return false;
+    }
+    return false;
   }
-  bool Contains (const nsRegion& aRgn) const;
-  bool Intersects (const nsRect& aRect) const;
-
-  void MoveBy (int32_t aXOffset, int32_t aYOffset)
+  bool Contains(const nsRect& aRect) const
   {
-    MoveBy (nsPoint (aXOffset, aYOffset));
+    if (aRect.IsEmpty()) {
+      return false;
+    }
+
+    if (mBands.IsEmpty()) {
+      return mBounds.Contains(aRect);
+    }
+
+    auto iter = mBands.begin();
+
+    while (iter != mBands.end()) {
+      if (iter->bottom <= aRect.Y()) {
+        iter++;
+        continue;
+      }
+
+      if (iter->top > aRect.Y()) {
+        return false;
+      }
+
+      // Now inside the rectangle.
+      if (!iter->ContainsStrip(Strip(aRect.X(), aRect.XMost()))) {
+        return false;
+      }
+
+      if (iter->bottom >= aRect.YMost()) {
+        return true;
+      }
+
+      int32_t lastY = iter->bottom;
+      iter++;
+      while (iter != mBands.end()) {
+        // Bands do not connect.
+        if (iter->top != lastY) {
+          return false;
+        }
+
+        if (!iter->ContainsStrip(Strip(aRect.X(), aRect.XMost()))) {
+          return false;
+        }
+
+        if (iter->bottom >= aRect.YMost()) {
+          return true;
+        }
+
+        lastY = iter->bottom;
+        iter++;
+      }
+    }
+    return false;
   }
-  void MoveBy (nsPoint aPt) { pixman_region32_translate(&mImpl, aPt.x, aPt.y); }
-  void SetEmpty ()
+
+  bool Contains(const nsRegion& aRgn) const;
+  bool Intersects(const nsRect& aRect) const;
+
+  void MoveBy(int32_t aXOffset, int32_t aYOffset)
+  {
+    MoveBy(nsPoint(aXOffset, aYOffset));
+  }
+  void MoveBy(nsPoint aPt)
   {
-    pixman_region32_clear(&mImpl);
+#ifdef DEBUG_REGIONS
+    class OperationStringGeneratorMoveBy : public OperationStringGenerator
+    {
+    public:
+      OperationStringGeneratorMoveBy(nsRegion& aRegion, const nsPoint& aPoint)
+        : mRegion(&aRegion), mRegionCopy(aRegion), mPoint(aPoint)
+      {
+        aRegion.mCurrentOpGenerator = this;
+      }
+      virtual ~OperationStringGeneratorMoveBy()
+      {
+        mRegion->mCurrentOpGenerator = nullptr;
+      }
+
+      virtual void OutputOp() override
+      {
+        std::stringstream stream;
+        mRegionCopy.OutputToStream("r", stream);
+        stream << "r.MoveBy(nsPoint(" << mPoint.x << ", " << mPoint.y << "));\n";
+        gfxCriticalError() << stream.str();
+      }
+    private:
+      nsRegion * mRegion;
+      nsRegion mRegionCopy;
+      nsPoint mPoint;
+    };
+
+    OperationStringGeneratorMoveBy opGenerator(*this, aPt);
+#endif
+
+    mBounds.MoveBy(aPt);
+    for (Band& band : mBands) {
+      band.top += aPt.Y();
+      band.bottom += aPt.Y();
+      for (Strip& strip : band.mStrips) {
+        strip.left += aPt.X();
+        strip.right += aPt.X();
+      }
+    }
+    AssertState();
+  }
+  void SetEmpty()
+  {
+    mBands.Clear();
+    mBounds.SetEmpty();
   }
 
   nsRegion MovedBy(int32_t aXOffset, int32_t aYOffset) const
   {
     return MovedBy(nsPoint(aXOffset, aYOffset));
   }
   nsRegion MovedBy(const nsPoint& aPt) const
   {
@@ -260,197 +1805,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 +2261,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 +2404,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 +2452,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,734 @@ 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 r1(nsRect(0, 0, 100, 50));
+    r1.OrWith(nsRect(50, 50, 50, 50));
+    nsRegion r2(nsRect(0, 0, 100, 50));
+    r2.OrWith(nsRect(50, 50, 50, 50));
+    r1.SubWith(r2);
+    EXPECT_FALSE(r1.Contains(1, 1));
+  }
+  {
+    nsRegion r1(nsRect(0, 0, 800, 1000));
+    nsRegion r2(nsRect(8, 108, 22, 20));
+    r2.OrWith(nsRect(91, 138, 17, 18));
+    r1.SubWith(r2);
+    EXPECT_TRUE(r1.Contains(400, 130));
+  }
+  {
+    nsRegion r1(nsRect(392, 2, 28, 7));
+    r1.OrWith(nsRect(115, 9, 305, 16));
+    r1.OrWith(nsRect(392, 25, 28, 5));
+    r1.OrWith(nsRect(0, 32, 1280, 41));
+    nsRegion r2(nsRect(0, 0, 1280, 9));
+    r2.OrWith(nsRect(0, 9, 115, 16));
+    r2.OrWith(nsRect(331, 9, 949, 16));
+    r2.OrWith(nsRect(0, 25, 1280, 7));
+    r2.OrWith(nsRect(331, 32, 124, 1));
+    r1.SubWith(r2);
+    EXPECT_FALSE(r1.Contains(350, 15));
+  }
+  {
+    nsRegion r1(nsRect(552, 0, 2, 2));
+    r1.OrWith(nsRect(362, 2, 222, 28));
+    r1.OrWith(nsRect(552, 30, 2, 2));
+    r1.OrWith(nsRect(0, 32, 1280, 41));
+    nsRegion r2(nsRect(512, 0, 146, 9));
+    r2.OrWith(nsRect(340, 9, 318, 16));
+    r2.OrWith(nsRect(512, 25, 146, 8));
+    r1.SubWith(r2);
+    EXPECT_FALSE(r1.Contains(350, 15));
+  }
+  {
+    nsRegion r(nsRect(0, 0, 229380, 6780));
+    r.OrWith(nsRect(76800, 6780, 76800, 4440));
+    r.OrWith(nsRect(76800, 11220, 44082, 1800));
+    r.OrWith(nsRect(122682, 11220, 30918, 1800));
+    r.OrWith(nsRect(76800, 13020, 76800, 2340));
+    r.OrWith(nsRect(85020, 15360, 59340, 75520));
+    r.OrWith(nsRect(85020, 90880, 38622, 11332));
+    r.OrWith(nsRect(143789, 90880, 571, 11332));
+    r.OrWith(nsRect(85020, 102212, 59340, 960));
+    r.OrWith(nsRect(85020, 103172, 38622, 1560));
+    r.OrWith(nsRect(143789, 103172, 571, 1560));
+    r.OrWith(nsRect(85020, 104732, 59340, 12292));
+    r.OrWith(nsRect(85020, 117024, 38622, 1560));
+    r.OrWith(nsRect(143789, 117024, 571, 1560));
+    r.OrWith(nsRect(85020, 118584, 59340, 11976));
+    r.SubWith(nsRect(123642, 89320, 20147, 1560));
+  }
+  {
+    nsRegion r(nsRect(0, 0, 9480, 12900));
+    r.OrWith(nsRect(0, 12900, 8460, 1020));
+    r.SubWith(nsRect(8460, 0, 1020, 12900));
+  }
+  {
+    nsRegion r1(nsRect(99, 1, 51, 2));
+    r1.OrWith(nsRect(85, 3, 65, 1));
+    r1.OrWith(nsRect(10, 4, 66, 5));
+    r1.OrWith(nsRect(85, 4, 37, 5));
+    r1.OrWith(nsRect(10, 9, 112, 3));
+    r1.OrWith(nsRect(1, 12, 121, 1));
+    r1.OrWith(nsRect(1, 13, 139, 3));
+    r1.OrWith(nsRect(0, 16, 140, 3));
+    r1.OrWith(nsRect(0, 19, 146, 3));
+    r1.OrWith(nsRect(0, 22, 149, 2));
+    r1.OrWith(nsRect(0, 24, 154, 2));
+    r1.OrWith(nsRect(0, 26, 160, 23));
+    r1.OrWith(nsRect(0, 49, 162, 31));
+    r1.OrWith(nsRect(0, 80, 171, 19));
+    r1.OrWith(nsRect(0, 99, 173, 11));
+    r1.OrWith(nsRect(2, 110, 171, 6));
+    r1.OrWith(nsRect(6, 116, 165, 5));
+    r1.OrWith(nsRect(8, 121, 163, 1));
+    r1.OrWith(nsRect(13, 122, 158, 11));
+    r1.OrWith(nsRect(14, 133, 157, 23));
+    r1.OrWith(nsRect(29, 156, 142, 10));
+    r1.OrWith(nsRect(37, 166, 134, 6));
+    r1.OrWith(nsRect(55, 172, 4, 4));
+    r1.OrWith(nsRect(83, 172, 88, 4));
+    r1.OrWith(nsRect(55, 176, 4, 2));
+    r1.OrWith(nsRect(89, 176, 6, 2));
+    r1.OrWith(nsRect(89, 178, 6, 4));
+    nsRegion r2(nsRect(63, 11, 39, 11));
+    r2.OrWith(nsRect(63, 22, 99, 16));
+    r2.OrWith(nsRect(37, 38, 125, 61));
+    r2.OrWith(nsRect(45, 99, 117, 8));
+    r2.OrWith(nsRect(47, 107, 115, 7));
+    r2.OrWith(nsRect(47, 114, 66, 1));
+    r2.OrWith(nsRect(49, 115, 64, 2));
+    r2.OrWith(nsRect(49, 117, 54, 30));
+    r1.SubWith(r2);
+  }
+  {
+    nsRegion r1(nsRect(95, 2, 47, 1));
+    r1.OrWith(nsRect(62, 3, 80, 2));
+    r1.OrWith(nsRect(1, 5, 18, 3));
+    r1.OrWith(nsRect(48, 5, 94, 3));
+    r1.OrWith(nsRect(1, 8, 18, 3));
+    r1.OrWith(nsRect(23, 8, 119, 3));
+    r1.OrWith(nsRect(1, 11, 172, 9));
+    r1.OrWith(nsRect(1, 20, 18, 8));
+    r1.OrWith(nsRect(20, 20, 153, 8));
+    r1.OrWith(nsRect(1, 28, 172, 13));
+    r1.OrWith(nsRect(1, 41, 164, 1));
+    r1.OrWith(nsRect(1, 42, 168, 1));
+    r1.OrWith(nsRect(0, 43, 169, 15));
+    r1.OrWith(nsRect(1, 58, 168, 26));
+    r1.OrWith(nsRect(1, 84, 162, 2));
+    r1.OrWith(nsRect(1, 86, 165, 23));
+    r1.OrWith(nsRect(1, 109, 162, 23));
+    r1.OrWith(nsRect(1, 132, 152, 4));
+    r1.OrWith(nsRect(1, 136, 150, 12));
+    r1.OrWith(nsRect(12, 148, 139, 4));
+    r1.OrWith(nsRect(12, 152, 113, 2));
+    r1.OrWith(nsRect(14, 154, 31, 3));
+    r1.OrWith(nsRect(82, 154, 43, 3));
+    r1.OrWith(nsRect(17, 157, 13, 19));
+    r1.OrWith(nsRect(82, 157, 43, 19));
+    r1.OrWith(nsRect(17, 176, 13, 16));
+    nsRegion r2(nsRect(97, 9, 6, 10));
+    r2.OrWith(nsRect(71, 19, 32, 2));
+    r2.OrWith(nsRect(20, 21, 83, 2));
+    r2.OrWith(nsRect(2, 23, 101, 9));
+    r2.OrWith(nsRect(2, 32, 98, 1));
+    r2.OrWith(nsRect(2, 33, 104, 5));
+    r2.OrWith(nsRect(2, 38, 118, 2));
+    r2.OrWith(nsRect(15, 40, 9, 11));
+    r2.OrWith(nsRect(36, 40, 84, 11));
+    r2.OrWith(nsRect(4, 51, 116, 33));
+    r2.OrWith(nsRect(4, 84, 159, 8));
+    r2.OrWith(nsRect(4, 92, 116, 13));
+    r2.OrWith(nsRect(15, 105, 9, 7));
+    r2.OrWith(nsRect(36, 105, 84, 7));
+    r2.OrWith(nsRect(36, 112, 84, 22));
+    r2.OrWith(nsRect(71, 134, 39, 46));
+    r1.SubWith(r2);
+  }
+#ifdef REGION_RANDOM_STRESS_TESTS
+  const uint32_t TestIterations = 100000;
+  const uint32_t RectsPerTest = 100;
+  const uint32_t SubRectsPerTest = 10;
+
+  nsRect rects[RectsPerTest];
+  nsRect subRects[SubRectsPerTest];
+
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r;
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    r.SetEmpty();
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      r.OrWith(rects[n]);
+    }
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      EXPECT_TRUE(r.Contains(rects[n]));
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      r.SubWith(subRects[n]);
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+    }
+  }
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r;
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    r.SetEmpty();
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      r.OrWith(rects[n]);
+    }
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      EXPECT_TRUE(r.Contains(rects[n]));
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    nsRegion r2;
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      r2.OrWith(subRects[n]);
+    }
+    r.SubWith(r2);
+
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+    }
+  }
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r(nsRect(-1, -1, 202, 202));
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+      r.SubWith(subRects[n]);
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+    }
+    EXPECT_TRUE(r.Contains(-1, -1));
+    EXPECT_TRUE(r.Contains(-1, 200));
+    EXPECT_TRUE(r.Contains(200, -1));
+    EXPECT_TRUE(r.Contains(200, 200));
+  }
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r(nsRect(-1, -1, 202, 202));
+    nsRegion r2;
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+      r2.OrWith(subRects[n]);
+    }
+    r.SubWith(r2);
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
+      EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+    }
+    EXPECT_TRUE(r.Contains(-1, -1));
+    EXPECT_TRUE(r.Contains(-1, 200));
+    EXPECT_TRUE(r.Contains(200, -1));
+    EXPECT_TRUE(r.Contains(200, 200));
+  }
+#endif
+}
+TEST(Gfx, RegionSub) {
+  {
+    nsRegion r1(nsRect(0, 0, 100, 50));
+    r1.OrWith(nsRect(50, 50, 50, 50));
+    nsRegion r2(nsRect(0, 0, 100, 50));
+    r2.OrWith(nsRect(50, 50, 50, 50));
+    nsRegion r3;
+    r3.Sub(r1, r2);
+    EXPECT_FALSE(r3.Contains(1, 1));
+  }
+  {
+    nsRegion r1(nsRect(0, 0, 800, 1000));
+    nsRegion r2(nsRect(8, 108, 22, 20));
+    r2.OrWith(nsRect(91, 138, 17, 18));
+    nsRegion r3;
+    r3.Sub(r1, r2);
+    EXPECT_TRUE(r3.Contains(400, 130));
+  }
+  {
+    nsRegion r1(nsRect(392, 2, 28, 7));
+    r1.OrWith(nsRect(115, 9, 305, 16));
+    r1.OrWith(nsRect(392, 25, 28, 5));
+    r1.OrWith(nsRect(0, 32, 1280, 41));
+    nsRegion r2(nsRect(0, 0, 1280, 9));
+    r2.OrWith(nsRect(0, 9, 115, 16));
+    r2.OrWith(nsRect(331, 9, 949, 16));
+    r2.OrWith(nsRect(0, 25, 1280, 7));
+    r2.OrWith(nsRect(331, 32, 124, 1));
+    nsRegion r3;
+    r3.Sub(r1, r2);
+    EXPECT_FALSE(r3.Contains(350, 15));
+  }
+  {
+    nsRegion r1(nsRect(552, 0, 2, 2));
+    r1.OrWith(nsRect(362, 2, 222, 28));
+    r1.OrWith(nsRect(552, 30, 2, 2));
+    r1.OrWith(nsRect(0, 32, 1280, 41));
+    nsRegion r2(nsRect(512, 0, 146, 9));
+    r2.OrWith(nsRect(340, 9, 318, 16));
+    r2.OrWith(nsRect(512, 25, 146, 8));
+    nsRegion r3;
+    r3.Sub(r1, r2);
+    EXPECT_FALSE(r3.Contains(350, 15));
+  }
+  {
+    nsRegion r1(nsRect(0, 0, 1265, 1024));
+    nsRegion r2(nsRect(1265, 0, 15, 685));
+    r2.OrWith(nsRect(0, 714, 1280, 221));
+    nsRegion r3;
+    r3.Sub(r1, r2);
+  }
+  {
+    nsRegion r1(nsRect(6, 0, 64, 1));
+    r1.OrWith(nsRect(6, 1, 67, 1));
+    r1.OrWith(nsRect(6, 2, 67, 2));
+    r1.OrWith(nsRect(79, 2, 67, 2));
+    r1.OrWith(nsRect(6, 4, 67, 1));
+    r1.OrWith(nsRect(79, 4, 98, 1));
+    r1.OrWith(nsRect(6, 5, 171, 18));
+    r1.OrWith(nsRect(1, 23, 176, 3));
+    r1.OrWith(nsRect(1, 26, 178, 5));
+    r1.OrWith(nsRect(1, 31, 176, 9));
+    r1.OrWith(nsRect(0, 40, 177, 57));
+    r1.OrWith(nsRect(0, 97, 176, 33));
+    r1.OrWith(nsRect(0, 130, 12, 17));
+    r1.OrWith(nsRect(15, 130, 161, 17));
+    r1.OrWith(nsRect(0, 147, 12, 5));
+    r1.OrWith(nsRect(15, 147, 111, 5));
+    r1.OrWith(nsRect(0, 152, 12, 7));
+    r1.OrWith(nsRect(17, 152, 109, 7));
+    r1.OrWith(nsRect(0, 159, 12, 2));
+    r1.OrWith(nsRect(17, 159, 98, 2));
+    r1.OrWith(nsRect(17, 161, 98, 9));
+    r1.OrWith(nsRect(27, 170, 63, 21));
+    nsRegion r2(nsRect(9, 9, 37, 17));
+    r2.OrWith(nsRect(92, 9, 26, 17));
+    r2.OrWith(nsRect(9, 26, 37, 9));
+    r2.OrWith(nsRect(84, 26, 65, 9));
+    r2.OrWith(nsRect(9, 35, 37, 2));
+    r2.OrWith(nsRect(51, 35, 98, 2));
+    r2.OrWith(nsRect(51, 37, 98, 11));
+    r2.OrWith(nsRect(51, 48, 78, 4));
+    r2.OrWith(nsRect(87, 52, 42, 7));
+    r2.OrWith(nsRect(19, 59, 12, 5));
+    r2.OrWith(nsRect(87, 59, 42, 5));
+    r2.OrWith(nsRect(19, 64, 12, 9));
+    r2.OrWith(nsRect(32, 64, 97, 9));
+    r2.OrWith(nsRect(19, 73, 12, 2));
+    r2.OrWith(nsRect(32, 73, 104, 2));
+    r2.OrWith(nsRect(19, 75, 117, 5));
+    r2.OrWith(nsRect(18, 80, 118, 5));
+    r2.OrWith(nsRect(18, 85, 111, 38));
+    r2.OrWith(nsRect(87, 123, 42, 11));
+    nsRegion r3;
+    r3.Sub(r1, r2);
+  }
+  {
+    nsRegion r1(nsRect(27, 0, 39, 1));
+    r1.OrWith(nsRect(86, 0, 22, 1));
+    r1.OrWith(nsRect(27, 1, 43, 1));
+    r1.OrWith(nsRect(86, 1, 22, 1));
+    r1.OrWith(nsRect(27, 2, 43, 1));
+    r1.OrWith(nsRect(86, 2, 75, 1));
+    r1.OrWith(nsRect(12, 3, 58, 1));
+    r1.OrWith(nsRect(86, 3, 75, 1));
+    r1.OrWith(nsRect(12, 4, 149, 5));
+    r1.OrWith(nsRect(0, 9, 161, 9));
+    r1.OrWith(nsRect(0, 18, 167, 17));
+    r1.OrWith(nsRect(0, 35, 171, 5));
+    r1.OrWith(nsRect(0, 40, 189, 28));
+    r1.OrWith(nsRect(0, 68, 171, 16));
+    r1.OrWith(nsRect(4, 84, 167, 5));
+    r1.OrWith(nsRect(4, 89, 177, 9));
+    r1.OrWith(nsRect(1, 98, 180, 59));
+    r1.OrWith(nsRect(4, 157, 177, 1));
+    r1.OrWith(nsRect(4, 158, 139, 15));
+    r1.OrWith(nsRect(17, 173, 126, 2));
+    r1.OrWith(nsRect(20, 175, 123, 2));
+    r1.OrWith(nsRect(20, 177, 118, 6));
+    r1.OrWith(nsRect(20, 183, 84, 2));
+    nsRegion r2(nsRect(64, 2, 30, 6));
+    r2.OrWith(nsRect(26, 11, 41, 17));
+    r2.OrWith(nsRect(19, 28, 48, 23));
+    r2.OrWith(nsRect(19, 51, 76, 8));
+    r2.OrWith(nsRect(4, 59, 91, 31));
+    r2.OrWith(nsRect(19, 90, 76, 29));
+    r2.OrWith(nsRect(33, 119, 62, 25));
+    r2.OrWith(nsRect(33, 144, 4, 21));
+    nsRegion r3;
+    r3.Sub(r1, r2);
+  }
+#ifdef REGION_RANDOM_STRESS_TESTS
+  const uint32_t TestIterations = 100000;
+  const uint32_t RectsPerTest = 100;
+  const uint32_t SubRectsPerTest = 10;
+
+  nsRect rects[RectsPerTest];
+  nsRect subRects[SubRectsPerTest];
+
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r;
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    r.SetEmpty();
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      r.OrWith(rects[n]);
+    }
+    for (uint32_t n = 0; n < RectsPerTest; n++) {
+      EXPECT_TRUE(r.Contains(rects[n]));
+    }
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+    }
+    nsRegion r2;
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      r2.OrWith(subRects[n]);
+    }
+    nsRegion r3;
+    r3.Sub(r, r2);
+
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].y));
+      EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+    }
+  }
+  for (uint32_t i = 0; i < TestIterations; i++) {
+    nsRegion r(nsRect(-1, -1, 202, 202));
+    nsRegion r2;
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+      r2.OrWith(subRects[n]);
+    }
+    nsRegion r3;
+    r3.Sub(r, r2);
+    for (uint32_t n = 0; n < SubRectsPerTest; n++) {
+      EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].y));
+      EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
+      EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
+    }
+    EXPECT_TRUE(r3.Contains(-1, -1));
+    EXPECT_TRUE(r3.Contains(-1, 200));
+    EXPECT_TRUE(r3.Contains(200, -1));
+    EXPECT_TRUE(r3.Contains(200, 200));
+  }
+#endif
+}
+
+TEST(Gfx, RegionAndWith) {
+  {
+    nsRegion r(nsRect(20, 0, 20, 20));
+    r.OrWith(nsRect(0, 20, 40, 20));
+    r.AndWith(nsRect(0, 0, 5, 5));
+    EXPECT_FALSE(r.Contains(1, 1));
+  }
+  {
+    nsRegion r1(nsRect(512, 1792, 256, 256));
+    nsRegion r2(nsRect(17, 1860, 239, 35));
+    r2.OrWith(nsRect(17, 1895, 239, 7));
+    r2.OrWith(nsRect(768, 1895, 154, 7));
+    r2.OrWith(nsRect(17, 1902, 905, 483));
+    r1.AndWith(r2);
+  }
+#ifdef REGION_RANDOM_STRESS_TESTS
+  const uint32_t TestIterations = 100000;
+  const uint32_t RectsPerTest = 50;
+  const uint32_t pointsTested = 100;
+
+  {
+    nsRect rectsSet1[RectsPerTest];
+    nsRect rectsSet2[RectsPerTest];
+
+    for (uint32_t i = 0; i < TestIterations; i++) {
+      nsRegion r1;
+      nsRegion r2;
+      for (uint32_t n = 0; n < RectsPerTest; n++) {
+        rectsSet1[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+        rectsSet2[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+        r1.OrWith(rectsSet1[n]);
+        r2.OrWith(rectsSet1[n]);
+      }
+
+      nsRegion r3 = r1;
+      r3.AndWith(r2);
+
+      for (uint32_t n = 0; n < pointsTested; n++) {
+        nsPoint p(rand() % 200, rand() % 200);
+        if (r1.Contains(p.x, p.y) && r2.Contains(p.x, p.y)) {
+          EXPECT_TRUE(r3.Contains(p.x, p.y));
+        } else {
+          EXPECT_FALSE(r3.Contains(p.x, p.y));
+        }
+      }
+    }
+  }
+
+  {
+    nsRect rectsSet[RectsPerTest];
+    nsRect testRect;
+    for (uint32_t i = 0; i < TestIterations; i++) {
+      nsRegion r;
+      for (uint32_t n = 0; n < RectsPerTest; n++) {
+        rectsSet[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+      }
+      for (uint32_t n = 0; n < RectsPerTest; n++) {
+        r.OrWith(rectsSet[n]);
+      }
+      testRect.SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+
+      nsRegion r2 = r;
+      r2.AndWith(testRect);
+
+      for (uint32_t n = 0; n < pointsTested; n++) {
+        nsPoint p(rand() % 200, rand() % 200);
+        if (r.Contains(p.x, p.y) && testRect.Contains(p.x, p.y)) {
+          EXPECT_TRUE(r2.Contains(p.x, p.y));
+        } else {
+          EXPECT_FALSE(r2.Contains(p.x, p.y));
+        }
+      }
+    }
+  }
+#endif
+}
+
+TEST(Gfx, RegionAnd) {
+  {
+    nsRegion r(nsRect(20, 0, 20, 20));
+    r.OrWith(nsRect(0, 20, 40, 20));
+    nsRegion r2;
+    r2.And(r, nsRect(0, 0, 5, 5));
+    EXPECT_FALSE(r.Contains(1, 1));
+  }
+  {
+    nsRegion r(nsRect(51, 2, 57, 5));
+    r.OrWith(nsRect(36, 7, 72, 4));
+    r.OrWith(nsRect(36, 11, 25, 1));
+    r.OrWith(nsRect(69, 12, 6, 4));
+    r.OrWith(nsRect(37, 16, 54, 2));
+    r.OrWith(nsRect(37, 18, 82, 2));
+    r.OrWith(nsRect(10, 20, 109, 3));
+    r.OrWith(nsRect(1, 23, 136, 21));
+    r.OrWith(nsRect(1, 44, 148, 2));
+    r.OrWith(nsRect(1, 46, 176, 31));
+    r.OrWith(nsRect(6, 77, 171, 1));
+    r.OrWith(nsRect(5, 78, 172, 30));
+    r.OrWith(nsRect(5, 108, 165, 45));
+    r.OrWith(nsRect(5, 153, 61, 5));
+    r.OrWith(nsRect(72, 153, 98, 5));
+    r.OrWith(nsRect(38, 158, 25, 4));
+    r.OrWith(nsRect(72, 158, 98, 4));
+    r.OrWith(nsRect(58, 162, 5, 8));
+    r.OrWith(nsRect(72, 162, 98, 8));
+    r.OrWith(nsRect(72, 170, 98, 5));
+    nsRegion r2;
+    r.And(r2, nsRect(18, 78, 53, 45));
+  }
+#ifdef REGION_RANDOM_STRESS_TESTS
+  const uint32_t TestIterations = 100000;
+  const uint32_t RectsPerTest = 50;
+  const uint32_t pointsTested = 100;
+
+  {
+    nsRect rectsSet1[RectsPerTest];
+    nsRect rectsSet2[RectsPerTest];
+
+    for (uint32_t i = 0; i < TestIterations; i++) {
+      nsRegion r1;
+      nsRegion r2;
+      for (uint32_t n = 0; n < RectsPerTest; n++) {
+        rectsSet1[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+        rectsSet2[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+        r1.OrWith(rectsSet1[n]);
+        r2.OrWith(rectsSet1[n]);
+      }
+
+      nsRegion r3;
+      r3.And(r1, r2);
+
+      for (uint32_t n = 0; n < pointsTested; n++) {
+        nsPoint p(rand() % 200, rand() % 200);
+        if (r1.Contains(p.x, p.y) && r2.Contains(p.x, p.y)) {
+          EXPECT_TRUE(r3.Contains(p.x, p.y));
+        } else {
+          EXPECT_FALSE(r3.Contains(p.x, p.y));
+        }
+      }
+    }
+  }
+
+  {
+    nsRect rectsSet[RectsPerTest];
+    nsRect testRect;
+    for (uint32_t i = 0; i < TestIterations; i++) {
+      nsRegion r;
+      for (uint32_t n = 0; n < RectsPerTest; n++) {
+        rectsSet[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+      }
+      for (uint32_t n = 0; n < RectsPerTest; n++) {
+        r.OrWith(rectsSet[n]);
+      }
+      testRect.SetRect(rand() % 100, rand() % 100, rand() % 99 + 1, rand() % 99 + 1);
+
+      nsRegion r2;
+      r2.And(r, testRect);
+
+      for (uint32_t n = 0; n < pointsTested; n++) {
+        nsPoint p(rand() % 200, rand() % 200);
+        if (r.Contains(p.x, p.y) && testRect.Contains(p.x, p.y)) {
+          EXPECT_TRUE(r2.Contains(p.x, p.y));
+        } else {
+          EXPECT_FALSE(r2.Contains(p.x, p.y));
+        }
+      }
+    }
+  }
+#endif
+}
 
 TEST(Gfx, RegionSimplify) {
   { // ensure simplify works on a single rect
     nsRegion r(nsRect(0,100,200,100));
 
     r.SimplifyOutwardByArea(100*100);
 
     nsRegion result(nsRect(0,100,200,100));
--- a/layout/painting/FrameLayerBuilder.cpp
+++ b/layout/painting/FrameLayerBuilder.cpp
@@ -5929,17 +5929,17 @@ FrameLayerBuilder::RecomputeVisibilityFo
     // region since we aren't displaying everything inside the rect.
     if (clip.GetRoundedRectCount() == 0) {
       nsRegion removed;
       removed.Sub(clipped, finalClipped);
       nsRegion newVisible;
       newVisible.Sub(visible, removed);
       // Don't let the visible region get too complex.
       if (newVisible.GetNumRects() <= 15) {
-        visible = newVisible;
+        visible = Move(newVisible);
       }
     }
   }
 }
 
 void
 FrameLayerBuilder::PaintItems(nsTArray<AssignedDisplayItem>& aItems,
                               const nsIntRect& aRect,
--- 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;