Bug 1283826. r=mstange,Bas
☠☠ backed out by 9b4a6326df6e ☠ ☠
authorKartikaya Gupta <kgupta@mozilla.com>
Mon, 18 Jul 2016 11:15:00 -0400
changeset 330664 7985dab6e65e467609a515497a6cf47b2e15785c
parent 330663 1ece89d2f73e34936a4b86df16ce30a7fd51e1e9
child 330665 d9675ab3d203fcb75025724c4726232e730047e1
push id9858
push userjlund@mozilla.com
push dateMon, 01 Aug 2016 14:37:10 +0000
treeherdermozilla-aurora@203106ef6cb6 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmstange, Bas
bugs1283826
milestone50.0a1
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();
 
--- 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));
   }