Bug 1283826. r=mstange,Bas
authorKartikaya Gupta <kgupta@mozilla.com>
Tue, 19 Jul 2016 21:50:09 -0400
changeset 345791 8e2f62943272dda354db63bfdb42510355dfaa72
parent 345790 fe259a08d225f4b533fac6c66329acc6c7d65388
child 345792 fcb6731a7e2b83d02dd093ce85ae97cb57770ac8
push id6389
push userraliiev@mozilla.com
push dateMon, 19 Sep 2016 13:38:22 +0000
treeherdermozilla-beta@01d67bfe6c81 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmstange, Bas
bugs1283826
milestone50.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 1283826. r=mstange,Bas MozReview-Commit-ID: HiwjHBlhmKk
gfx/2d/BaseRect.h
gfx/2d/Rect.h
gfx/src/TiledRegion.cpp
gfx/src/TiledRegion.h
gfx/tests/gtest/TestRegion.cpp
--- a/gfx/2d/BaseRect.h
+++ b/gfx/2d/BaseRect.h
@@ -129,29 +129,33 @@ struct BaseRect {
     *static_cast<Sub*>(this) = aRect1.Intersect(aRect2);
     return !IsEmpty();
   }
 
   // Returns the smallest rectangle that contains both the area of both
   // this and aRect2.
   // Thus, empty input rectangles are ignored.
   // If both rectangles are empty, returns this.
+  // WARNING! This is not safe against overflow, prefer using SafeUnion instead
+  // when dealing with int-based rects.
   MOZ_MUST_USE Sub Union(const Sub& aRect) const
   {
     if (IsEmpty()) {
       return aRect;
     } else if (aRect.IsEmpty()) {
       return *static_cast<const Sub*>(this);
     } else {
       return UnionEdges(aRect);
     }
   }
   // Returns the smallest rectangle that contains both the points (including
   // edges) of both aRect1 and aRect2.
   // Thus, empty input rectangles are allowed to affect the result.
+  // WARNING! This is not safe against overflow, prefer using SafeUnionEdges
+  // instead when dealing with int-based rects.
   MOZ_MUST_USE Sub UnionEdges(const Sub& aRect) const
   {
     Sub result;
     result.x = std::min(x, aRect.x);
     result.y = std::min(y, aRect.y);
     result.width = std::max(XMost(), aRect.XMost()) - result.x;
     result.height = std::max(YMost(), aRect.YMost()) - result.y;
     return result;
--- a/gfx/2d/Rect.h
+++ b/gfx/2d/Rect.h
@@ -80,16 +80,17 @@ IntMarginTyped<units> RoundedToInt(const
 template<class units>
 struct IntRectTyped :
     public BaseRect<int32_t, IntRectTyped<units>, IntPointTyped<units>, IntSizeTyped<units>, IntMarginTyped<units> >,
     public units {
     static_assert(IsPixel<units>::value,
                   "'units' must be a coordinate system tag");
 
     typedef BaseRect<int32_t, IntRectTyped<units>, IntPointTyped<units>, IntSizeTyped<units>, IntMarginTyped<units> > Super;
+    typedef IntRectTyped<units> Self;
 
     IntRectTyped() : Super() {}
     IntRectTyped(const IntPointTyped<units>& aPos, const IntSizeTyped<units>& aSize) :
         Super(aPos, aSize) {}
     IntRectTyped(int32_t _x, int32_t _y, int32_t _width, int32_t _height) :
         Super(_x, _y, _width, _height) {}
 
     // Rounding isn't meaningful on an integer rectangle.
@@ -111,16 +112,51 @@ struct IntRectTyped :
     bool Overflows() const {
       CheckedInt<int32_t> xMost = this->x;
       xMost += this->width;
       CheckedInt<int32_t> yMost = this->y;
       yMost += this->height;
       return !xMost.isValid() || !yMost.isValid();
     }
 
+    // Same as Union(), but in the cases where aRect is non-empty, the union is
+    // done while guarding against overflow. If an overflow is detected, Nothing
+    // is returned.
+    MOZ_MUST_USE Maybe<Self> SafeUnion(const Self& aRect) const
+    {
+      if (this->IsEmpty()) {
+        return aRect.Overflows() ? Nothing() : Some(aRect);
+      } else if (aRect.IsEmpty()) {
+        return Some(*static_cast<const Self*>(this));
+      } else {
+        return this->SafeUnionEdges(aRect);
+      }
+    }
+
+    // Same as UnionEdges, but guards against overflow. If an overflow is detected,
+    // Nothing is returned.
+    MOZ_MUST_USE Maybe<Self> SafeUnionEdges(const Self& aRect) const
+    {
+      if (this->Overflows() || aRect.Overflows()) {
+        return Nothing();
+      }
+      // If neither |this| nor |aRect| overflow, then their XMost/YMost values
+      // should be safe to use.
+      CheckedInt<int32_t> newX = std::min(this->x, aRect.x);
+      CheckedInt<int32_t> newY = std::min(this->y, aRect.y);
+      CheckedInt<int32_t> newXMost = std::max(this->XMost(), aRect.XMost());
+      CheckedInt<int32_t> newYMost = std::max(this->YMost(), aRect.YMost());
+      CheckedInt<int32_t> newW = newXMost - newX;
+      CheckedInt<int32_t> newH = newYMost - newY;
+      if (!newW.isValid() || !newH.isValid()) {
+        return Nothing();
+      }
+      return Some(Self(newX.value(), newY.value(), newW.value(), newH.value()));
+    }
+
     // This is here only to keep IPDL-generated code happy. DO NOT USE.
     bool operator==(const IntRectTyped<units>& aRect) const
     {
       return IntRectTyped<units>::IsEqualEdges(aRect);
     }
 
     void InflateToMultiple(const IntSizeTyped<units>& aTileSize)
     {
--- a/gfx/src/TiledRegion.cpp
+++ b/gfx/src/TiledRegion.cpp
@@ -127,20 +127,25 @@ public:
   TileIterator End() const { return TileIterator(mTileBounds, mEnd); }
 
   // The number of tiles in this tile range.
   size_t Length() const
   {
     if (mEnd.y == mStart.y) {
       return (mEnd.x - mStart.x) / kTileSize;
     }
-    size_t numberOfFullRows = (mEnd.y - mStart.y) / kTileSize - 1;
-    return ((mTileBounds.x2 - mStart.x) +
-            (mTileBounds.x2 - mTileBounds.x1) * numberOfFullRows +
-            (mEnd.x - mTileBounds.x1)) / kTileSize;
+    int64_t numberOfFullRows = (((int64_t)mEnd.y - (int64_t)mStart.y) / kTileSize) - 1;
+    int64_t tilesInFirstRow = ((int64_t)mTileBounds.x2 - (int64_t)mStart.x) / kTileSize;
+    int64_t tilesInLastRow = ((int64_t)mEnd.x - (int64_t)mTileBounds.x1) / kTileSize;
+    int64_t tilesInFullRow = ((int64_t)mTileBounds.x2 - (int64_t)mTileBounds.x1) / kTileSize;
+    int64_t total = tilesInFirstRow + (tilesInFullRow * numberOfFullRows) + tilesInLastRow;
+    MOZ_ASSERT(total > 0);
+    // The total may be larger than what fits in a size_t, so clamp it to
+    // SIZE_MAX in that case.
+    return ((uint64_t)total > (uint64_t)SIZE_MAX) ? SIZE_MAX : (size_t)total;
   }
 
   // If aTileOrigin does not describe a tile inside our tile bounds, move it
   // to the next tile that you'd encounter by "advancing" a tile iterator
   // inside these tile bounds. If aTileOrigin is after the last tile inside
   // our tile bounds, move it to the range end tile.
   // The result of this method is a valid end tile for a tile range with our
   // tile bounds.
@@ -198,16 +203,20 @@ IterationEndReason ProcessIntersectedTil
                                            HandleNonEmptyTileFunction aHandleNonEmptyTile)
 {
   pixman_box32_t tileBounds = {
     RoundDownToMultiple(aRect.x1, kTileSize),
     RoundDownToMultiple(aRect.y1, kTileSize),
     RoundUpToMultiple(aRect.x2, kTileSize),
     RoundUpToMultiple(aRect.y2, kTileSize)
   };
+  if (tileBounds.x2 < tileBounds.x1 || tileBounds.y2 < tileBounds.y1) {
+    // RoundUpToMultiple probably overflowed. Bail out.
+    return IterationEndReason::STOPPED;
+  }
 
   TileRange tileRange(tileBounds);
   TileIterator rangeEnd = tileRange.End();
 
   // tileIterator points to the next tile in tileRange, or to rangeEnd if we're
   // done.
   TileIterator tileIterator = tileRange.Begin();
 
@@ -278,17 +287,19 @@ TiledRegionImpl::AddRect(const pixman_bo
 {
   // We are adding a rectangle that can span multiple tiles.
   // For each empty tile that aRect intersects, we need to add the intersection
   // of aRect with that tile to mRects, respecting the order of mRects.
   // For each tile that already has a rectangle, we need to enlarge that
   // existing rectangle to include the intersection of aRect with the tile.
   return ProcessIntersectedTiles(aRect, mRects,
     [&aRect](nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
-      if (rects.Length() + emptyTiles.Length() >= kMaxTiles ||
+      CheckedInt<size_t> newLength(rects.Length());
+      newLength += emptyTiles.Length();
+      if (!newLength.isValid() || newLength.value() >= kMaxTiles ||
           !rects.InsertElementsAt(rectIndex, emptyTiles.Length(), fallible)) {
         return IterationAction::STOP;
       }
       for (TileIterator tileIt = emptyTiles.Begin();
            tileIt != emptyTiles.End();
            ++tileIt, ++rectIndex) {
         rects[rectIndex] = tileIt.IntersectionWith(aRect);
       }
--- a/gfx/src/TiledRegion.h
+++ b/gfx/src/TiledRegion.h
@@ -84,38 +84,53 @@ public:
   }
 
   void Add(const RectT& aRect)
   {
     if (aRect.IsEmpty()) {
       return;
     }
 
-    mBounds = mBounds.Union(aRect);
+    Maybe<RectT> newBounds = mBounds.SafeUnion(aRect);
+    if (!newBounds) {
+      return;
+    }
+    mBounds = newBounds.value();
+    MOZ_ASSERT(!mBounds.Overflows());
 
     if (mCoversBounds) {
       return;
     }
 
     if (!mImpl.AddRect(RectToBox(aRect))) {
       FallBackToBounds();
     }
   }
 
   void Add(const RegionT& aRegion)
   {
-    mBounds = mBounds.Union(aRegion.GetBounds());
+    Maybe<RectT> newBounds = mBounds.SafeUnion(aRegion.GetBounds());
+    if (!newBounds) {
+      return;
+    }
+    mBounds = newBounds.value();
+    MOZ_ASSERT(!mBounds.Overflows());
 
     if (mCoversBounds) {
       return;
     }
 
     for (auto iter = aRegion.RectIter(); !iter.Done(); iter.Next()) {
       RectT r = iter.Get();
-      MOZ_ASSERT(!r.IsEmpty());
+      if (r.IsEmpty() || r.Overflows()) {
+        // This can happen if e.g. a negative-width rect was wrapped into a
+        // region. Treat it the same as we would if such a rect was passed to
+        // the Add(const RectT&) function.
+        continue;
+      }
       if (!mImpl.AddRect(RectToBox(r))) {
         FallBackToBounds();
         return;
       }
     }
   }
 
   bool IsEmpty() const { return mBounds.IsEmpty(); }
@@ -127,29 +142,35 @@ public:
     mCoversBounds = false;
   }
 
   RectT GetBounds() const { return mBounds; }
   bool CoversBounds() const { return mCoversBounds; }
 
   bool Intersects(const RectT& aRect) const
   {
-    if (!mBounds.Intersects(aRect)) {
+    if (aRect.IsEmpty()) {
+      return true;
+    }
+    if (aRect.Overflows() || !mBounds.Intersects(aRect)) {
       return false;
     }
     if (mCoversBounds) {
       return true;
     }
 
     return mImpl.Intersects(RectToBox(aRect));
   }
 
   bool Contains(const RectT& aRect) const
   {
-    if (!mBounds.Contains(aRect)) {
+    if (aRect.IsEmpty()) {
+      return true;
+    }
+    if (aRect.Overflows() || !mBounds.Contains(aRect)) {
       return false;
     }
     if (mCoversBounds) {
       return true;
     }
     return mImpl.Contains(RectToBox(aRect));
   }
 
@@ -158,16 +179,18 @@ private:
   void FallBackToBounds()
   {
     mCoversBounds = true;
     mImpl.Clear();
   }
 
   static pixman_box32_t RectToBox(const RectT& aRect)
   {
+    MOZ_ASSERT(!aRect.IsEmpty());
+    MOZ_ASSERT(!aRect.Overflows());
     return { aRect.x, aRect.y, aRect.XMost(), aRect.YMost() };
   }
 
   RectT mBounds;
   TiledRegionImpl mImpl;
 
   // mCoversBounds is true if we bailed out due to a large number of tiles.
   // mCoversBounds being true means that this TiledRegion is just a simple
--- a/gfx/tests/gtest/TestRegion.cpp
+++ b/gfx/tests/gtest/TestRegion.cpp
@@ -685,16 +685,96 @@ TEST(Gfx, TiledRegionIntersects) {
   // Both tiles should have simplified their rectangles, and those two
   // rectangles are adjacent to each other, so they just build up one rect.
   EXPECT_TRUE(tiledRegion.Intersects(nsIntRect(50, 50, 300, 50)));
   EXPECT_TRUE(tiledRegion.Intersects(nsIntRect(200, 10, 10, 50)));
   EXPECT_TRUE(tiledRegion.Intersects(nsIntRect(50, 50, 301, 50)));
   EXPECT_FALSE(tiledRegion.Intersects(nsIntRect(0, 0, 50, 500)));
 }
 
+TEST(Gfx, TiledRegionBoundaryConditions1) {
+  TiledIntRegion tiledRegion;
+  // This one works fine
+  tiledRegion.Add(nsIntRegion(nsIntRect(INT_MIN, INT_MIN, 1, 1)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(INT_MIN, INT_MIN, 1, 1)));
+
+  // This causes the tiledRegion.mBounds to overflow, so it is ignored
+  tiledRegion.Add(nsIntRegion(nsIntRect(INT_MAX - 1, INT_MAX - 1, 1, 1)));
+
+  // Verify that the tiledRegion contains only things we expect
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(INT_MIN, INT_MIN, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(INT_MAX - 1, INT_MAX - 1, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(0, 0, 1, 1)));
+}
+
+TEST(Gfx, TiledRegionBoundaryConditions2) {
+  TiledIntRegion tiledRegion;
+  // This one works fine
+  tiledRegion.Add(nsIntRegion(nsIntRect(INT_MAX - 1, INT_MIN, 1, 1)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(INT_MAX - 1, INT_MIN, 1, 1)));
+
+  // As with TiledRegionBoundaryConditions1, this overflows, so it is ignored
+  tiledRegion.Add(nsIntRegion(nsIntRect(INT_MIN, INT_MAX - 1, 1, 1)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(INT_MAX - 1, INT_MIN, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(INT_MIN, INT_MAX - 1, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(0, 0, 1, 1)));
+}
+
+TEST(Gfx, TiledRegionBigRects) {
+  TiledIntRegion tiledRegion;
+  // Super wide region, forces simplification into bounds mode
+  tiledRegion.Add(nsIntRegion(nsIntRect(INT_MIN, INT_MIN, INT_MAX, 100)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(INT_MIN, INT_MIN, 1, 1)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(-2, INT_MIN + 99, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(-2, INT_MIN + 100, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(-1, INT_MIN + 99, 1, 1)));
+
+  // Add another rect, verify that simplification caused the entire bounds
+  // to expand by a lot more.
+  tiledRegion.Add(nsIntRegion(nsIntRect(INT_MIN, INT_MIN + 200, 1, 1)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(-2, INT_MIN + 100, 1, 1)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(-2, INT_MIN + 200, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(-2, INT_MIN + 201, 1, 1)));
+}
+
+TEST(Gfx, TiledRegionBoundaryOverflow) {
+  TiledIntRegion tiledRegion;
+  tiledRegion.Add(nsIntRegion(nsIntRect(100, 100, 1, 1)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(100, 100, 1, 1)));
+
+  // The next region is invalid, so it gets ignored
+  tiledRegion.Add(nsIntRegion(nsIntRect(INT_MAX, INT_MAX, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(INT_MAX, INT_MAX, 1, 1)));
+
+  // Try that again as a rect, it will also get ignored
+  tiledRegion.Add(nsIntRect(INT_MAX, INT_MAX, 1, 1));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(INT_MAX, INT_MAX, 1, 1)));
+
+  // Try with a bigger overflowing rect
+  tiledRegion.Add(nsIntRect(INT_MAX, INT_MAX, 500, 500));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(INT_MIN, INT_MIN, 10, 10)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(INT_MAX, INT_MAX, 100, 100)));
+
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(0, 0, 1, 1)));
+}
+
+TEST(Gfx, TiledRegionNegativeRect) {
+  TiledIntRegion tiledRegion;
+  // The next region is invalid, so it gets ignored
+  tiledRegion.Add(nsIntRegion(nsIntRect(0, 0, -500, -500)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(-50, -50, 1, 1)));
+  // Rects with negative widths/heights are treated as empty and ignored
+  tiledRegion.Add(nsIntRect(0, 0, -500, -500));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(-1, -1, 1, 1)));
+  EXPECT_FALSE(tiledRegion.Contains(nsIntRect(0, 0, 1, 1)));
+  // Empty rects are always contained
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(0, 0, -1, -1)));
+  EXPECT_TRUE(tiledRegion.Contains(nsIntRect(100, 100, -1, -1)));
+}
+
 MOZ_GTEST_BENCH(GfxBench, RegionOr, []{
   const int size = 5000;
 
   nsRegion r;
   for (int i = 0; i < size; i++) {
     r = r.Or(r, nsRect(i, i, i + 10, i + 10));
   }