gfx/tests/gtest/TestRegion.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include <algorithm>
   8
   9 #include "gtest/gtest.h"
  10 #include "nsRegion.h"
  11 #include "RegionBuilder.h"
  12 #include "mozilla/UniquePtr.h"
  13
  14 using namespace mozilla::gfx;
  15
  16 // #define REGION_RANDOM_STRESS_TESTS
  17
  18 class TestLargestRegion {
  19  public:
  20   static void TestSingleRect(nsRect r) {
  21     nsRegion region(r);
  22     EXPECT_TRUE(region.GetLargestRectangle().IsEqualInterior(r));
  23   }
  24   // Construct a rectangle, remove part of it, then check the remainder
  25   static void TestNonRectangular() {
  26     nsRegion r(nsRect(0, 0, 30, 30));
  27
  28     const int nTests = 19;
  29     struct {
  30       nsRect rect;
  31       int64_t expectedArea;
  32     } tests[nTests] = {// Remove a 20x10 chunk from the square
  33                        {nsRect(0, 0, 20, 10), 600},
  34                        {nsRect(10, 0, 20, 10), 600},
  35                        {nsRect(10, 20, 20, 10), 600},
  36                        {nsRect(0, 20, 20, 10), 600},
  37                        // Remove a 10x20 chunk from the square
  38                        {nsRect(0, 0, 10, 20), 600},
  39                        {nsRect(20, 0, 10, 20), 600},
  40                        {nsRect(20, 10, 10, 20), 600},
  41                        {nsRect(0, 10, 10, 20), 600},
  42                        // Remove the center 10x10
  43                        {nsRect(10, 10, 10, 10), 300},
  44                        // Remove the middle column
  45                        {nsRect(10, 0, 10, 30), 300},
  46                        // Remove the middle row
  47                        {nsRect(0, 10, 30, 10), 300},
  48                        // Remove the corners 10x10
  49                        {nsRect(0, 0, 10, 10), 600},
  50                        {nsRect(20, 20, 10, 10), 600},
  51                        {nsRect(20, 0, 10, 10), 600},
  52                        {nsRect(0, 20, 10, 10), 600},
  53                        // Remove the corners 20x20
  54                        {nsRect(0, 0, 20, 20), 300},
  55                        {nsRect(10, 10, 20, 20), 300},
  56                        {nsRect(10, 0, 20, 20), 300},
  57                        {nsRect(0, 10, 20, 20), 300}};
  58
  59     for (int32_t i = 0; i < nTests; i++) {
  60       nsRegion r2;
  61       r2.Sub(r, tests[i].rect);
  62
  63       EXPECT_TRUE(r2.IsComplex()) << "nsRegion code got unexpectedly smarter!";
  64
  65       nsRect largest = r2.GetLargestRectangle();
  66       EXPECT_TRUE(largest.Width() * largest.Height() == tests[i].expectedArea)
  67           << "Did not successfully find largest rectangle in non-rectangular "
  68              "region on iteration "
  69           << i;
  70     }
  71   }
  72   static void TwoRectTest() {
  73     nsRegion r(nsRect(0, 0, 100, 100));
  74     const int nTests = 4;
  75     struct {
  76       nsRect rect1, rect2;
  77       int64_t expectedArea;
  78     } tests[nTests] = {
  79         {nsRect(0, 0, 75, 40), nsRect(0, 60, 75, 40), 2500},
  80         {nsRect(25, 0, 75, 40), nsRect(25, 60, 75, 40), 2500},
  81         {nsRect(25, 0, 75, 40), nsRect(0, 60, 75, 40), 2000},
  82         {nsRect(0, 0, 75, 40), nsRect(25, 60, 75, 40), 2000},
  83     };
  84     for (int32_t i = 0; i < nTests; i++) {
  85       nsRegion r2;
  86
  87       r2.Sub(r, tests[i].rect1);
  88       r2.Sub(r2, tests[i].rect2);
  89
  90       EXPECT_TRUE(r2.IsComplex()) << "nsRegion code got unexpectedly smarter!";
  91
  92       nsRect largest = r2.GetLargestRectangle();
  93       EXPECT_TRUE(largest.Width() * largest.Height() == tests[i].expectedArea)
  94           << "Did not successfully find largest rectangle in two-rect-subtract "
  95              "region on iteration "
  96           << i;
  97     }
  98   }
  99   static void TestContainsSpecifiedRect() {
 100     nsRegion r(nsRect(0, 0, 100, 100));
 101     r.Or(r, nsRect(0, 300, 50, 50));
 102     EXPECT_TRUE(r.GetLargestRectangle(nsRect(0, 300, 10, 10))
 103                     .IsEqualInterior(nsRect(0, 300, 50, 50)))
 104         << "Chose wrong rectangle";
 105   }
 106   static void TestContainsSpecifiedOverflowingRect() {
 107     nsRegion r(nsRect(0, 0, 100, 100));
 108     r.Or(r, nsRect(0, 300, 50, 50));
 109     EXPECT_TRUE(r.GetLargestRectangle(nsRect(0, 290, 10, 20))
 110                     .IsEqualInterior(nsRect(0, 300, 50, 50)))
 111         << "Chose wrong rectangle";
 112   }
 113 };
 114
 115 TEST(Gfx, RegionSingleRect)
 116 {
 117   TestLargestRegion::TestSingleRect(nsRect(0, 52, 720, 480));
 118   TestLargestRegion::TestSingleRect(nsRect(-20, 40, 50, 20));
 119   TestLargestRegion::TestSingleRect(nsRect(-20, 40, 10, 8));
 120   TestLargestRegion::TestSingleRect(nsRect(-20, -40, 10, 8));
 121   TestLargestRegion::TestSingleRect(nsRect(-10, -10, 20, 20));
 122 }
 123
 124 TEST(Gfx, RegionNonRectangular)
 125 { TestLargestRegion::TestNonRectangular(); }
 126
 127 TEST(Gfx, RegionTwoRectTest)
 128 { TestLargestRegion::TwoRectTest(); }
 129
 130 TEST(Gfx, RegionContainsSpecifiedRect)
 131 { TestLargestRegion::TestContainsSpecifiedRect(); }
 132
 133 TEST(Gfx, RegionTestContainsSpecifiedOverflowingRect)
 134 { TestLargestRegion::TestContainsSpecifiedOverflowingRect(); }
 135
 136 TEST(Gfx, RegionScaleToInside)
 137 {
 138   {  // no rectangles
 139     nsRegion r;
 140
 141     nsIntRegion scaled = r.ScaleToInsidePixels(1, 1, 60);
 142     nsIntRegion result;
 143
 144     EXPECT_TRUE(result.IsEqual(scaled)) << "scaled result incorrect";
 145   }
 146
 147   {  // one rectangle
 148     nsRegion r(nsRect(0, 44760, 19096, 264));
 149
 150     nsIntRegion scaled = r.ScaleToInsidePixels(1, 1, 60);
 151     nsIntRegion result(mozilla::gfx::IntRect(0, 746, 318, 4));
 152
 153     EXPECT_TRUE(result.IsEqual(scaled)) << "scaled result incorrect";
 154   }
 155
 156   {  // the first rectangle gets adjusted
 157     nsRegion r(nsRect(0, 44760, 19096, 264));
 158     r.Or(r, nsRect(0, 45024, 19360, 1056));
 159
 160     nsIntRegion scaled = r.ScaleToInsidePixels(1, 1, 60);
 161     nsIntRegion result(mozilla::gfx::IntRect(0, 746, 318, 5));
 162     result.Or(result, mozilla::gfx::IntRect(0, 751, 322, 17));
 163
 164     EXPECT_TRUE(result.IsEqual(scaled)) << "scaled result incorrect";
 165   }
 166
 167   {  // the second rectangle gets adjusted
 168     nsRegion r(nsRect(0, 44760, 19360, 264));
 169     r.Or(r, nsRect(0, 45024, 19096, 1056));
 170
 171     nsIntRegion scaled = r.ScaleToInsidePixels(1, 1, 60);
 172     nsIntRegion result(mozilla::gfx::IntRect(0, 746, 322, 4));
 173     result.Or(result, mozilla::gfx::IntRect(0, 750, 318, 18));
 174
 175     EXPECT_TRUE(result.IsEqual(scaled)) << "scaled result incorrect";
 176   }
 177 }
 178
 179 TEST(Gfx, RegionIsEqual)
 180 {
 181   {
 182     nsRegion r(nsRect(0, 0, 50, 50));
 183     EXPECT_FALSE(nsRegion().IsEqual(r));
 184   }
 185   {
 186     nsRegion r1(nsRect(0, 0, 50, 50));
 187     nsRegion r2(nsRect(0, 0, 50, 50));
 188     EXPECT_TRUE(r1.IsEqual(r2));
 189   }
 190   {
 191     nsRegion r1(nsRect(0, 0, 50, 50));
 192     nsRegion r2(nsRect(0, 0, 60, 50));
 193     EXPECT_FALSE(r1.IsEqual(r2));
 194   }
 195   {
 196     nsRegion r1(nsRect(0, 0, 50, 50));
 197     r1.OrWith(nsRect(0, 60, 50, 50));
 198     nsRegion r2(nsRect(0, 0, 50, 50));
 199     r2.OrWith(nsRect(0, 60, 50, 50));
 200     EXPECT_TRUE(r1.IsEqual(r2));
 201   }
 202   {
 203     nsRegion r1(nsRect(0, 0, 50, 50));
 204     r1.OrWith(nsRect(0, 60, 50, 50));
 205     nsRegion r2(nsRect(0, 0, 50, 50));
 206     r2.OrWith(nsRect(0, 70, 50, 50));
 207     EXPECT_FALSE(r1.IsEqual(r2));
 208   }
 209   {
 210     nsRegion r1(nsRect(0, 0, 50, 50));
 211     r1.OrWith(nsRect(0, 60, 50, 50));
 212     r1.OrWith(nsRect(100, 60, 50, 50));
 213     nsRegion r2(nsRect(0, 0, 50, 50));
 214     r2.OrWith(nsRect(0, 60, 50, 50));
 215     EXPECT_FALSE(r1.IsEqual(r2));
 216   }
 217 }
 218
 219 TEST(Gfx, RegionOrWith)
 220 {
 221   PR_Sleep(PR_SecondsToInterval(10));
 222   {
 223     nsRegion r(nsRect(11840, 11840, 4640, -10880));
 224     r.OrWith(nsRect(160, 160, 7720, 880));
 225   }
 226   {
 227     nsRegion r(nsRect(79, 31, 75, 12));
 228     r.OrWith(nsRect(22, 43, 132, 5));
 229     r.OrWith(nsRect(22, 48, 125, 3));
 230     r.OrWith(nsRect(22, 51, 96, 20));
 231     r.OrWith(nsRect(34, 71, 1, 14));
 232     r.OrWith(nsRect(26, 85, 53, 1));
 233     r.OrWith(nsRect(26, 86, 53, 4));
 234     r.OrWith(nsRect(96, 86, 30, 4));
 235     r.OrWith(nsRect(34, 90, 1, 2));
 236     r.OrWith(nsRect(96, 90, 30, 2));
 237     r.OrWith(nsRect(34, 92, 1, 3));
 238     r.OrWith(nsRect(49, 92, 34, 3));
 239     r.OrWith(nsRect(96, 92, 30, 3));
 240     r.OrWith(nsRect(34, 95, 1, 17));
 241     r.OrWith(nsRect(49, 95, 77, 17));
 242     r.OrWith(nsRect(34, 112, 1, 12));
 243     r.OrWith(nsRect(75, 112, 51, 12));
 244     r.OrWith(nsRect(34, 124, 1, 10));
 245     r.OrWith(nsRect(75, 124, 44, 10));
 246     r.OrWith(nsRect(34, 134, 1, 19));
 247     r.OrWith(nsRect(22, 17, 96, 27));
 248   }
 249   {
 250     nsRegion r(nsRect(0, 8, 257, 32));
 251     r.OrWith(nsRect(3702, 8, 138, 32));
 252     r.OrWith(nsRect(0, 40, 225, 1));
 253     r.OrWith(nsRect(3702, 40, 138, 1));
 254     r.OrWith(nsRect(0, 41, 101, 40));
 255     r.OrWith(nsRect(69, 41, 32, 40));
 256   }
 257   {
 258     nsRegion r(nsRect(79, 56, 8, 32));
 259     r.OrWith(nsRect(5, 94, 23, 81));
 260     r.OrWith(nsRect(56, 29, 91, 81));
 261   }
 262   {
 263     nsRegion r(nsRect(0, 82, 3840, 2046));
 264     r.OrWith(nsRect(0, 0, 3840, 82));
 265   }
 266   {
 267     nsRegion r(nsRect(2, 5, 600, 28));
 268     r.OrWith(nsRect(2, 82, 600, 19));
 269     r.OrWith(nsRect(2, 33, 600, 49));
 270   }
 271   {
 272     nsRegion r(nsRect(3823, 0, 17, 17));
 273     r.OrWith(nsRect(3823, 2029, 17, 17));
 274     r.OrWith(nsRect(3823, 0, 17, 2046));
 275   }
 276   {
 277     nsRegion r(nsRect(1036, 4, 32, 21));
 278     r.OrWith(nsRect(1070, 4, 66, 21));
 279     r.OrWith(nsRect(40, 5, 0, 33));
 280   }
 281   {
 282     nsRegion r(nsRect(0, 0, 1024, 1152));
 283     r.OrWith(nsRect(-335802, -1073741824, 1318851, 1860043520));
 284   }
 285   {
 286     nsRegion r(nsRect(0, 0, 800, 1000));
 287     r.OrWith(nsRect(0, 0, 536870912, 1073741824));
 288   }
 289   {
 290     nsRegion r(nsRect(53, 2, 52, 3));
 291     r.OrWith(nsRect(45, 5, 60, 16));
 292     r.OrWith(nsRect(16, 21, 8, 1));
 293     r.OrWith(nsRect(45, 21, 12, 1));
 294     r.OrWith(nsRect(16, 22, 8, 5));
 295     r.OrWith(nsRect(33, 22, 52, 5));
 296     r.OrWith(nsRect(16, 27, 8, 7));
 297     r.OrWith(nsRect(33, 27, 66, 7));
 298     r.OrWith(nsRect(0, 34, 99, 1));
 299     r.OrWith(nsRect(0, 35, 159, 27));
 300     r.OrWith(nsRect(0, 62, 122, 3));
 301     r.OrWith(nsRect(0, 65, 85, 11));
 302     r.OrWith(nsRect(91, 65, 97, 11));
 303     r.OrWith(nsRect(11, 76, 74, 2));
 304     r.OrWith(nsRect(91, 76, 97, 2));
 305     r.OrWith(nsRect(11, 78, 74, 12));
 306     r.OrWith(nsRect(11, 90, 13, 3));
 307     r.OrWith(nsRect(33, 90, 108, 3));
 308     r.OrWith(nsRect(16, 93, 8, 22));
 309     r.OrWith(nsRect(33, 93, 108, 22));
 310     r.OrWith(nsRect(16, 115, 8, 1));
 311     r.OrWith(nsRect(58, 115, 83, 1));
 312     r.OrWith(nsRect(58, 116, 83, 25));
 313     r.OrWith(nsRect(59, 37, 88, 92));
 314   }
 315 #ifdef REGION_RANDOM_STRESS_TESTS
 316   const uint32_t TestIterations = 100000;
 317   const uint32_t RectsPerTest = 100;
 318
 319   nsRect rects[RectsPerTest];
 320
 321   for (uint32_t i = 0; i < TestIterations; i++) {
 322     nsRegion r;
 323     for (uint32_t n = 0; n < RectsPerTest; n++) {
 324       rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 325                        rand() % 99 + 1);
 326     }
 327     r.SetEmpty();
 328     for (uint32_t n = 0; n < RectsPerTest; n++) {
 329       r.OrWith(rects[n]);
 330     }
 331     for (uint32_t n = 0; n < RectsPerTest; n++) {
 332       EXPECT_TRUE(r.Contains(rects[n]));
 333     }
 334   }
 335 #endif
 336 }
 337
 338 TEST(Gfx, RegionSubWith)
 339 {
 340   {
 341     nsRegion r1(nsRect(0, 0, 100, 50));
 342     r1.OrWith(nsRect(50, 50, 50, 50));
 343     nsRegion r2(nsRect(0, 0, 100, 50));
 344     r2.OrWith(nsRect(50, 50, 50, 50));
 345     r1.SubWith(r2);
 346     EXPECT_FALSE(r1.Contains(1, 1));
 347   }
 348   {
 349     nsRegion r1(nsRect(0, 0, 800, 1000));
 350     nsRegion r2(nsRect(8, 108, 22, 20));
 351     r2.OrWith(nsRect(91, 138, 17, 18));
 352     r1.SubWith(r2);
 353     EXPECT_TRUE(r1.Contains(400, 130));
 354   }
 355   {
 356     nsRegion r1(nsRect(392, 2, 28, 7));
 357     r1.OrWith(nsRect(115, 9, 305, 16));
 358     r1.OrWith(nsRect(392, 25, 28, 5));
 359     r1.OrWith(nsRect(0, 32, 1280, 41));
 360     nsRegion r2(nsRect(0, 0, 1280, 9));
 361     r2.OrWith(nsRect(0, 9, 115, 16));
 362     r2.OrWith(nsRect(331, 9, 949, 16));
 363     r2.OrWith(nsRect(0, 25, 1280, 7));
 364     r2.OrWith(nsRect(331, 32, 124, 1));
 365     r1.SubWith(r2);
 366     EXPECT_FALSE(r1.Contains(350, 15));
 367   }
 368   {
 369     nsRegion r1(nsRect(552, 0, 2, 2));
 370     r1.OrWith(nsRect(362, 2, 222, 28));
 371     r1.OrWith(nsRect(552, 30, 2, 2));
 372     r1.OrWith(nsRect(0, 32, 1280, 41));
 373     nsRegion r2(nsRect(512, 0, 146, 9));
 374     r2.OrWith(nsRect(340, 9, 318, 16));
 375     r2.OrWith(nsRect(512, 25, 146, 8));
 376     r1.SubWith(r2);
 377     EXPECT_FALSE(r1.Contains(350, 15));
 378   }
 379   {
 380     nsRegion r(nsRect(0, 0, 229380, 6780));
 381     r.OrWith(nsRect(76800, 6780, 76800, 4440));
 382     r.OrWith(nsRect(76800, 11220, 44082, 1800));
 383     r.OrWith(nsRect(122682, 11220, 30918, 1800));
 384     r.OrWith(nsRect(76800, 13020, 76800, 2340));
 385     r.OrWith(nsRect(85020, 15360, 59340, 75520));
 386     r.OrWith(nsRect(85020, 90880, 38622, 11332));
 387     r.OrWith(nsRect(143789, 90880, 571, 11332));
 388     r.OrWith(nsRect(85020, 102212, 59340, 960));
 389     r.OrWith(nsRect(85020, 103172, 38622, 1560));
 390     r.OrWith(nsRect(143789, 103172, 571, 1560));
 391     r.OrWith(nsRect(85020, 104732, 59340, 12292));
 392     r.OrWith(nsRect(85020, 117024, 38622, 1560));
 393     r.OrWith(nsRect(143789, 117024, 571, 1560));
 394     r.OrWith(nsRect(85020, 118584, 59340, 11976));
 395     r.SubWith(nsRect(123642, 89320, 20147, 1560));
 396   }
 397   {
 398     nsRegion r(nsRect(0, 0, 9480, 12900));
 399     r.OrWith(nsRect(0, 12900, 8460, 1020));
 400     r.SubWith(nsRect(8460, 0, 1020, 12900));
 401   }
 402   {
 403     nsRegion r1(nsRect(99, 1, 51, 2));
 404     r1.OrWith(nsRect(85, 3, 65, 1));
 405     r1.OrWith(nsRect(10, 4, 66, 5));
 406     r1.OrWith(nsRect(85, 4, 37, 5));
 407     r1.OrWith(nsRect(10, 9, 112, 3));
 408     r1.OrWith(nsRect(1, 12, 121, 1));
 409     r1.OrWith(nsRect(1, 13, 139, 3));
 410     r1.OrWith(nsRect(0, 16, 140, 3));
 411     r1.OrWith(nsRect(0, 19, 146, 3));
 412     r1.OrWith(nsRect(0, 22, 149, 2));
 413     r1.OrWith(nsRect(0, 24, 154, 2));
 414     r1.OrWith(nsRect(0, 26, 160, 23));
 415     r1.OrWith(nsRect(0, 49, 162, 31));
 416     r1.OrWith(nsRect(0, 80, 171, 19));
 417     r1.OrWith(nsRect(0, 99, 173, 11));
 418     r1.OrWith(nsRect(2, 110, 171, 6));
 419     r1.OrWith(nsRect(6, 116, 165, 5));
 420     r1.OrWith(nsRect(8, 121, 163, 1));
 421     r1.OrWith(nsRect(13, 122, 158, 11));
 422     r1.OrWith(nsRect(14, 133, 157, 23));
 423     r1.OrWith(nsRect(29, 156, 142, 10));
 424     r1.OrWith(nsRect(37, 166, 134, 6));
 425     r1.OrWith(nsRect(55, 172, 4, 4));
 426     r1.OrWith(nsRect(83, 172, 88, 4));
 427     r1.OrWith(nsRect(55, 176, 4, 2));
 428     r1.OrWith(nsRect(89, 176, 6, 2));
 429     r1.OrWith(nsRect(89, 178, 6, 4));
 430     nsRegion r2(nsRect(63, 11, 39, 11));
 431     r2.OrWith(nsRect(63, 22, 99, 16));
 432     r2.OrWith(nsRect(37, 38, 125, 61));
 433     r2.OrWith(nsRect(45, 99, 117, 8));
 434     r2.OrWith(nsRect(47, 107, 115, 7));
 435     r2.OrWith(nsRect(47, 114, 66, 1));
 436     r2.OrWith(nsRect(49, 115, 64, 2));
 437     r2.OrWith(nsRect(49, 117, 54, 30));
 438     r1.SubWith(r2);
 439   }
 440   {
 441     nsRegion r1(nsRect(95, 2, 47, 1));
 442     r1.OrWith(nsRect(62, 3, 80, 2));
 443     r1.OrWith(nsRect(1, 5, 18, 3));
 444     r1.OrWith(nsRect(48, 5, 94, 3));
 445     r1.OrWith(nsRect(1, 8, 18, 3));
 446     r1.OrWith(nsRect(23, 8, 119, 3));
 447     r1.OrWith(nsRect(1, 11, 172, 9));
 448     r1.OrWith(nsRect(1, 20, 18, 8));
 449     r1.OrWith(nsRect(20, 20, 153, 8));
 450     r1.OrWith(nsRect(1, 28, 172, 13));
 451     r1.OrWith(nsRect(1, 41, 164, 1));
 452     r1.OrWith(nsRect(1, 42, 168, 1));
 453     r1.OrWith(nsRect(0, 43, 169, 15));
 454     r1.OrWith(nsRect(1, 58, 168, 26));
 455     r1.OrWith(nsRect(1, 84, 162, 2));
 456     r1.OrWith(nsRect(1, 86, 165, 23));
 457     r1.OrWith(nsRect(1, 109, 162, 23));
 458     r1.OrWith(nsRect(1, 132, 152, 4));
 459     r1.OrWith(nsRect(1, 136, 150, 12));
 460     r1.OrWith(nsRect(12, 148, 139, 4));
 461     r1.OrWith(nsRect(12, 152, 113, 2));
 462     r1.OrWith(nsRect(14, 154, 31, 3));
 463     r1.OrWith(nsRect(82, 154, 43, 3));
 464     r1.OrWith(nsRect(17, 157, 13, 19));
 465     r1.OrWith(nsRect(82, 157, 43, 19));
 466     r1.OrWith(nsRect(17, 176, 13, 16));
 467     nsRegion r2(nsRect(97, 9, 6, 10));
 468     r2.OrWith(nsRect(71, 19, 32, 2));
 469     r2.OrWith(nsRect(20, 21, 83, 2));
 470     r2.OrWith(nsRect(2, 23, 101, 9));
 471     r2.OrWith(nsRect(2, 32, 98, 1));
 472     r2.OrWith(nsRect(2, 33, 104, 5));
 473     r2.OrWith(nsRect(2, 38, 118, 2));
 474     r2.OrWith(nsRect(15, 40, 9, 11));
 475     r2.OrWith(nsRect(36, 40, 84, 11));
 476     r2.OrWith(nsRect(4, 51, 116, 33));
 477     r2.OrWith(nsRect(4, 84, 159, 8));
 478     r2.OrWith(nsRect(4, 92, 116, 13));
 479     r2.OrWith(nsRect(15, 105, 9, 7));
 480     r2.OrWith(nsRect(36, 105, 84, 7));
 481     r2.OrWith(nsRect(36, 112, 84, 22));
 482     r2.OrWith(nsRect(71, 134, 39, 46));
 483     r1.SubWith(r2);
 484   }
 485 #ifdef REGION_RANDOM_STRESS_TESTS
 486   const uint32_t TestIterations = 100000;
 487   const uint32_t RectsPerTest = 100;
 488   const uint32_t SubRectsPerTest = 10;
 489
 490   nsRect rects[RectsPerTest];
 491   nsRect subRects[SubRectsPerTest];
 492
 493   for (uint32_t i = 0; i < TestIterations; i++) {
 494     nsRegion r;
 495     for (uint32_t n = 0; n < RectsPerTest; n++) {
 496       rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 497                        rand() % 99 + 1);
 498     }
 499     r.SetEmpty();
 500     for (uint32_t n = 0; n < RectsPerTest; n++) {
 501       r.OrWith(rects[n]);
 502     }
 503     for (uint32_t n = 0; n < RectsPerTest; n++) {
 504       EXPECT_TRUE(r.Contains(rects[n]));
 505     }
 506     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 507       subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 508                           rand() % 99 + 1);
 509     }
 510     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 511       r.SubWith(subRects[n]);
 512     }
 513     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 514       EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
 515       EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
 516       EXPECT_FALSE(
 517           r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
 518       EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
 519     }
 520   }
 521   for (uint32_t i = 0; i < TestIterations; i++) {
 522     nsRegion r;
 523     for (uint32_t n = 0; n < RectsPerTest; n++) {
 524       rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 525                        rand() % 99 + 1);
 526     }
 527     r.SetEmpty();
 528     for (uint32_t n = 0; n < RectsPerTest; n++) {
 529       r.OrWith(rects[n]);
 530     }
 531     for (uint32_t n = 0; n < RectsPerTest; n++) {
 532       EXPECT_TRUE(r.Contains(rects[n]));
 533     }
 534     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 535       subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 536                           rand() % 99 + 1);
 537     }
 538     nsRegion r2;
 539     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 540       r2.OrWith(subRects[n]);
 541     }
 542     r.SubWith(r2);
 543
 544     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 545       EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
 546       EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
 547       EXPECT_FALSE(
 548           r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
 549       EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
 550     }
 551   }
 552   for (uint32_t i = 0; i < TestIterations; i++) {
 553     nsRegion r(nsRect(-1, -1, 202, 202));
 554     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 555       subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 556                           rand() % 99 + 1);
 557       r.SubWith(subRects[n]);
 558     }
 559     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 560       EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
 561       EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
 562       EXPECT_FALSE(
 563           r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
 564       EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
 565     }
 566     EXPECT_TRUE(r.Contains(-1, -1));
 567     EXPECT_TRUE(r.Contains(-1, 200));
 568     EXPECT_TRUE(r.Contains(200, -1));
 569     EXPECT_TRUE(r.Contains(200, 200));
 570   }
 571   for (uint32_t i = 0; i < TestIterations; i++) {
 572     nsRegion r(nsRect(-1, -1, 202, 202));
 573     nsRegion r2;
 574     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 575       subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 576                           rand() % 99 + 1);
 577       r2.OrWith(subRects[n]);
 578     }
 579     r.SubWith(r2);
 580     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 581       EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].y));
 582       EXPECT_FALSE(r.Contains(subRects[n].x, subRects[n].YMost() - 1));
 583       EXPECT_FALSE(
 584           r.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
 585       EXPECT_FALSE(r.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
 586     }
 587     EXPECT_TRUE(r.Contains(-1, -1));
 588     EXPECT_TRUE(r.Contains(-1, 200));
 589     EXPECT_TRUE(r.Contains(200, -1));
 590     EXPECT_TRUE(r.Contains(200, 200));
 591   }
 592 #endif
 593 }
 594 TEST(Gfx, RegionSub)
 595 {
 596   {
 597     nsRegion r1(nsRect(0, 0, 100, 50));
 598     r1.OrWith(nsRect(50, 50, 50, 50));
 599     nsRegion r2(nsRect(0, 0, 100, 50));
 600     r2.OrWith(nsRect(50, 50, 50, 50));
 601     nsRegion r3;
 602     r3.Sub(r1, r2);
 603     EXPECT_FALSE(r3.Contains(1, 1));
 604   }
 605   {
 606     nsRegion r1(nsRect(0, 0, 800, 1000));
 607     nsRegion r2(nsRect(8, 108, 22, 20));
 608     r2.OrWith(nsRect(91, 138, 17, 18));
 609     nsRegion r3;
 610     r3.Sub(r1, r2);
 611     EXPECT_TRUE(r3.Contains(400, 130));
 612   }
 613   {
 614     nsRegion r1(nsRect(392, 2, 28, 7));
 615     r1.OrWith(nsRect(115, 9, 305, 16));
 616     r1.OrWith(nsRect(392, 25, 28, 5));
 617     r1.OrWith(nsRect(0, 32, 1280, 41));
 618     nsRegion r2(nsRect(0, 0, 1280, 9));
 619     r2.OrWith(nsRect(0, 9, 115, 16));
 620     r2.OrWith(nsRect(331, 9, 949, 16));
 621     r2.OrWith(nsRect(0, 25, 1280, 7));
 622     r2.OrWith(nsRect(331, 32, 124, 1));
 623     nsRegion r3;
 624     r3.Sub(r1, r2);
 625     EXPECT_FALSE(r3.Contains(350, 15));
 626   }
 627   {
 628     nsRegion r1(nsRect(552, 0, 2, 2));
 629     r1.OrWith(nsRect(362, 2, 222, 28));
 630     r1.OrWith(nsRect(552, 30, 2, 2));
 631     r1.OrWith(nsRect(0, 32, 1280, 41));
 632     nsRegion r2(nsRect(512, 0, 146, 9));
 633     r2.OrWith(nsRect(340, 9, 318, 16));
 634     r2.OrWith(nsRect(512, 25, 146, 8));
 635     nsRegion r3;
 636     r3.Sub(r1, r2);
 637     EXPECT_FALSE(r3.Contains(350, 15));
 638   }
 639   {
 640     nsRegion r1(nsRect(0, 0, 1265, 1024));
 641     nsRegion r2(nsRect(1265, 0, 15, 685));
 642     r2.OrWith(nsRect(0, 714, 1280, 221));
 643     nsRegion r3;
 644     r3.Sub(r1, r2);
 645   }
 646   {
 647     nsRegion r1(nsRect(6, 0, 64, 1));
 648     r1.OrWith(nsRect(6, 1, 67, 1));
 649     r1.OrWith(nsRect(6, 2, 67, 2));
 650     r1.OrWith(nsRect(79, 2, 67, 2));
 651     r1.OrWith(nsRect(6, 4, 67, 1));
 652     r1.OrWith(nsRect(79, 4, 98, 1));
 653     r1.OrWith(nsRect(6, 5, 171, 18));
 654     r1.OrWith(nsRect(1, 23, 176, 3));
 655     r1.OrWith(nsRect(1, 26, 178, 5));
 656     r1.OrWith(nsRect(1, 31, 176, 9));
 657     r1.OrWith(nsRect(0, 40, 177, 57));
 658     r1.OrWith(nsRect(0, 97, 176, 33));
 659     r1.OrWith(nsRect(0, 130, 12, 17));
 660     r1.OrWith(nsRect(15, 130, 161, 17));
 661     r1.OrWith(nsRect(0, 147, 12, 5));
 662     r1.OrWith(nsRect(15, 147, 111, 5));
 663     r1.OrWith(nsRect(0, 152, 12, 7));
 664     r1.OrWith(nsRect(17, 152, 109, 7));
 665     r1.OrWith(nsRect(0, 159, 12, 2));
 666     r1.OrWith(nsRect(17, 159, 98, 2));
 667     r1.OrWith(nsRect(17, 161, 98, 9));
 668     r1.OrWith(nsRect(27, 170, 63, 21));
 669     nsRegion r2(nsRect(9, 9, 37, 17));
 670     r2.OrWith(nsRect(92, 9, 26, 17));
 671     r2.OrWith(nsRect(9, 26, 37, 9));
 672     r2.OrWith(nsRect(84, 26, 65, 9));
 673     r2.OrWith(nsRect(9, 35, 37, 2));
 674     r2.OrWith(nsRect(51, 35, 98, 2));
 675     r2.OrWith(nsRect(51, 37, 98, 11));
 676     r2.OrWith(nsRect(51, 48, 78, 4));
 677     r2.OrWith(nsRect(87, 52, 42, 7));
 678     r2.OrWith(nsRect(19, 59, 12, 5));
 679     r2.OrWith(nsRect(87, 59, 42, 5));
 680     r2.OrWith(nsRect(19, 64, 12, 9));
 681     r2.OrWith(nsRect(32, 64, 97, 9));
 682     r2.OrWith(nsRect(19, 73, 12, 2));
 683     r2.OrWith(nsRect(32, 73, 104, 2));
 684     r2.OrWith(nsRect(19, 75, 117, 5));
 685     r2.OrWith(nsRect(18, 80, 118, 5));
 686     r2.OrWith(nsRect(18, 85, 111, 38));
 687     r2.OrWith(nsRect(87, 123, 42, 11));
 688     nsRegion r3;
 689     r3.Sub(r1, r2);
 690   }
 691   {
 692     nsRegion r1(nsRect(27, 0, 39, 1));
 693     r1.OrWith(nsRect(86, 0, 22, 1));
 694     r1.OrWith(nsRect(27, 1, 43, 1));
 695     r1.OrWith(nsRect(86, 1, 22, 1));
 696     r1.OrWith(nsRect(27, 2, 43, 1));
 697     r1.OrWith(nsRect(86, 2, 75, 1));
 698     r1.OrWith(nsRect(12, 3, 58, 1));
 699     r1.OrWith(nsRect(86, 3, 75, 1));
 700     r1.OrWith(nsRect(12, 4, 149, 5));
 701     r1.OrWith(nsRect(0, 9, 161, 9));
 702     r1.OrWith(nsRect(0, 18, 167, 17));
 703     r1.OrWith(nsRect(0, 35, 171, 5));
 704     r1.OrWith(nsRect(0, 40, 189, 28));
 705     r1.OrWith(nsRect(0, 68, 171, 16));
 706     r1.OrWith(nsRect(4, 84, 167, 5));
 707     r1.OrWith(nsRect(4, 89, 177, 9));
 708     r1.OrWith(nsRect(1, 98, 180, 59));
 709     r1.OrWith(nsRect(4, 157, 177, 1));
 710     r1.OrWith(nsRect(4, 158, 139, 15));
 711     r1.OrWith(nsRect(17, 173, 126, 2));
 712     r1.OrWith(nsRect(20, 175, 123, 2));
 713     r1.OrWith(nsRect(20, 177, 118, 6));
 714     r1.OrWith(nsRect(20, 183, 84, 2));
 715     nsRegion r2(nsRect(64, 2, 30, 6));
 716     r2.OrWith(nsRect(26, 11, 41, 17));
 717     r2.OrWith(nsRect(19, 28, 48, 23));
 718     r2.OrWith(nsRect(19, 51, 76, 8));
 719     r2.OrWith(nsRect(4, 59, 91, 31));
 720     r2.OrWith(nsRect(19, 90, 76, 29));
 721     r2.OrWith(nsRect(33, 119, 62, 25));
 722     r2.OrWith(nsRect(33, 144, 4, 21));
 723     nsRegion r3;
 724     r3.Sub(r1, r2);
 725   }
 726 #ifdef REGION_RANDOM_STRESS_TESTS
 727   const uint32_t TestIterations = 100000;
 728   const uint32_t RectsPerTest = 100;
 729   const uint32_t SubRectsPerTest = 10;
 730
 731   nsRect rects[RectsPerTest];
 732   nsRect subRects[SubRectsPerTest];
 733
 734   for (uint32_t i = 0; i < TestIterations; i++) {
 735     nsRegion r;
 736     for (uint32_t n = 0; n < RectsPerTest; n++) {
 737       rects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 738                        rand() % 99 + 1);
 739     }
 740     r.SetEmpty();
 741     for (uint32_t n = 0; n < RectsPerTest; n++) {
 742       r.OrWith(rects[n]);
 743     }
 744     for (uint32_t n = 0; n < RectsPerTest; n++) {
 745       EXPECT_TRUE(r.Contains(rects[n]));
 746     }
 747     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 748       subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 749                           rand() % 99 + 1);
 750     }
 751     nsRegion r2;
 752     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 753       r2.OrWith(subRects[n]);
 754     }
 755     nsRegion r3;
 756     r3.Sub(r, r2);
 757
 758     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 759       EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].y));
 760       EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].YMost() - 1));
 761       EXPECT_FALSE(
 762           r3.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
 763       EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
 764     }
 765   }
 766   for (uint32_t i = 0; i < TestIterations; i++) {
 767     nsRegion r(nsRect(-1, -1, 202, 202));
 768     nsRegion r2;
 769     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 770       subRects[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 771                           rand() % 99 + 1);
 772       r2.OrWith(subRects[n]);
 773     }
 774     nsRegion r3;
 775     r3.Sub(r, r2);
 776     for (uint32_t n = 0; n < SubRectsPerTest; n++) {
 777       EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].y));
 778       EXPECT_FALSE(r3.Contains(subRects[n].x, subRects[n].YMost() - 1));
 779       EXPECT_FALSE(
 780           r3.Contains(subRects[n].XMost() - 1, subRects[n].YMost() - 1));
 781       EXPECT_FALSE(r3.Contains(subRects[n].XMost() - 1, subRects[n].Y()));
 782     }
 783     EXPECT_TRUE(r3.Contains(-1, -1));
 784     EXPECT_TRUE(r3.Contains(-1, 200));
 785     EXPECT_TRUE(r3.Contains(200, -1));
 786     EXPECT_TRUE(r3.Contains(200, 200));
 787   }
 788 #endif
 789 }
 790
 791 TEST(Gfx, RegionAndWith)
 792 {
 793   {
 794     nsRegion r(nsRect(20, 0, 20, 20));
 795     r.OrWith(nsRect(0, 20, 40, 20));
 796     r.AndWith(nsRect(0, 0, 5, 5));
 797     EXPECT_FALSE(r.Contains(1, 1));
 798   }
 799   {
 800     nsRegion r1(nsRect(512, 1792, 256, 256));
 801     nsRegion r2(nsRect(17, 1860, 239, 35));
 802     r2.OrWith(nsRect(17, 1895, 239, 7));
 803     r2.OrWith(nsRect(768, 1895, 154, 7));
 804     r2.OrWith(nsRect(17, 1902, 905, 483));
 805     r1.AndWith(r2);
 806   }
 807 #ifdef REGION_RANDOM_STRESS_TESTS
 808   const uint32_t TestIterations = 100000;
 809   const uint32_t RectsPerTest = 50;
 810   const uint32_t pointsTested = 100;
 811
 812   {
 813     nsRect rectsSet1[RectsPerTest];
 814     nsRect rectsSet2[RectsPerTest];
 815
 816     for (uint32_t i = 0; i < TestIterations; i++) {
 817       nsRegion r1;
 818       nsRegion r2;
 819       for (uint32_t n = 0; n < RectsPerTest; n++) {
 820         rectsSet1[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 821                              rand() % 99 + 1);
 822         rectsSet2[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 823                              rand() % 99 + 1);
 824         r1.OrWith(rectsSet1[n]);
 825         r2.OrWith(rectsSet1[n]);
 826       }
 827
 828       nsRegion r3 = r1;
 829       r3.AndWith(r2);
 830
 831       for (uint32_t n = 0; n < pointsTested; n++) {
 832         nsPoint p(rand() % 200, rand() % 200);
 833         if (r1.Contains(p.x, p.y) && r2.Contains(p.x, p.y)) {
 834           EXPECT_TRUE(r3.Contains(p.x, p.y));
 835         } else {
 836           EXPECT_FALSE(r3.Contains(p.x, p.y));
 837         }
 838       }
 839     }
 840   }
 841
 842   {
 843     nsRect rectsSet[RectsPerTest];
 844     nsRect testRect;
 845     for (uint32_t i = 0; i < TestIterations; i++) {
 846       nsRegion r;
 847       for (uint32_t n = 0; n < RectsPerTest; n++) {
 848         rectsSet[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 849                             rand() % 99 + 1);
 850       }
 851       for (uint32_t n = 0; n < RectsPerTest; n++) {
 852         r.OrWith(rectsSet[n]);
 853       }
 854       testRect.SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 855                        rand() % 99 + 1);
 856
 857       nsRegion r2 = r;
 858       r2.AndWith(testRect);
 859
 860       for (uint32_t n = 0; n < pointsTested; n++) {
 861         nsPoint p(rand() % 200, rand() % 200);
 862         if (r.Contains(p.x, p.y) && testRect.Contains(p.x, p.y)) {
 863           EXPECT_TRUE(r2.Contains(p.x, p.y));
 864         } else {
 865           EXPECT_FALSE(r2.Contains(p.x, p.y));
 866         }
 867       }
 868     }
 869   }
 870 #endif
 871 }
 872
 873 TEST(Gfx, RegionAnd)
 874 {
 875   {
 876     nsRegion r(nsRect(20, 0, 20, 20));
 877     r.OrWith(nsRect(0, 20, 40, 20));
 878     nsRegion r2;
 879     r2.And(r, nsRect(0, 0, 5, 5));
 880     EXPECT_FALSE(r.Contains(1, 1));
 881   }
 882   {
 883     nsRegion r(nsRect(51, 2, 57, 5));
 884     r.OrWith(nsRect(36, 7, 72, 4));
 885     r.OrWith(nsRect(36, 11, 25, 1));
 886     r.OrWith(nsRect(69, 12, 6, 4));
 887     r.OrWith(nsRect(37, 16, 54, 2));
 888     r.OrWith(nsRect(37, 18, 82, 2));
 889     r.OrWith(nsRect(10, 20, 109, 3));
 890     r.OrWith(nsRect(1, 23, 136, 21));
 891     r.OrWith(nsRect(1, 44, 148, 2));
 892     r.OrWith(nsRect(1, 46, 176, 31));
 893     r.OrWith(nsRect(6, 77, 171, 1));
 894     r.OrWith(nsRect(5, 78, 172, 30));
 895     r.OrWith(nsRect(5, 108, 165, 45));
 896     r.OrWith(nsRect(5, 153, 61, 5));
 897     r.OrWith(nsRect(72, 153, 98, 5));
 898     r.OrWith(nsRect(38, 158, 25, 4));
 899     r.OrWith(nsRect(72, 158, 98, 4));
 900     r.OrWith(nsRect(58, 162, 5, 8));
 901     r.OrWith(nsRect(72, 162, 98, 8));
 902     r.OrWith(nsRect(72, 170, 98, 5));
 903     nsRegion r2;
 904     r.And(r2, nsRect(18, 78, 53, 45));
 905   }
 906 #ifdef REGION_RANDOM_STRESS_TESTS
 907   const uint32_t TestIterations = 100000;
 908   const uint32_t RectsPerTest = 50;
 909   const uint32_t pointsTested = 100;
 910
 911   {
 912     nsRect rectsSet1[RectsPerTest];
 913     nsRect rectsSet2[RectsPerTest];
 914
 915     for (uint32_t i = 0; i < TestIterations; i++) {
 916       nsRegion r1;
 917       nsRegion r2;
 918       for (uint32_t n = 0; n < RectsPerTest; n++) {
 919         rectsSet1[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 920                              rand() % 99 + 1);
 921         rectsSet2[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 922                              rand() % 99 + 1);
 923         r1.OrWith(rectsSet1[n]);
 924         r2.OrWith(rectsSet1[n]);
 925       }
 926
 927       nsRegion r3;
 928       r3.And(r1, r2);
 929
 930       for (uint32_t n = 0; n < pointsTested; n++) {
 931         nsPoint p(rand() % 200, rand() % 200);
 932         if (r1.Contains(p.x, p.y) && r2.Contains(p.x, p.y)) {
 933           EXPECT_TRUE(r3.Contains(p.x, p.y));
 934         } else {
 935           EXPECT_FALSE(r3.Contains(p.x, p.y));
 936         }
 937       }
 938     }
 939   }
 940
 941   {
 942     nsRect rectsSet[RectsPerTest];
 943     nsRect testRect;
 944     for (uint32_t i = 0; i < TestIterations; i++) {
 945       nsRegion r;
 946       for (uint32_t n = 0; n < RectsPerTest; n++) {
 947         rectsSet[n].SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 948                             rand() % 99 + 1);
 949       }
 950       for (uint32_t n = 0; n < RectsPerTest; n++) {
 951         r.OrWith(rectsSet[n]);
 952       }
 953       testRect.SetRect(rand() % 100, rand() % 100, rand() % 99 + 1,
 954                        rand() % 99 + 1);
 955
 956       nsRegion r2;
 957       r2.And(r, testRect);
 958
 959       for (uint32_t n = 0; n < pointsTested; n++) {
 960         nsPoint p(rand() % 200, rand() % 200);
 961         if (r.Contains(p.x, p.y) && testRect.Contains(p.x, p.y)) {
 962           EXPECT_TRUE(r2.Contains(p.x, p.y));
 963         } else {
 964           EXPECT_FALSE(r2.Contains(p.x, p.y));
 965         }
 966       }
 967     }
 968   }
 969 #endif
 970 }
 971
 972 TEST(Gfx, RegionSimplify)
 973 {
 974   {  // ensure simplify works on a single rect
 975     nsRegion r(nsRect(0, 100, 200, 100));
 976
 977     r.SimplifyOutwardByArea(100 * 100);
 978
 979     nsRegion result(nsRect(0, 100, 200, 100));
 980
 981     EXPECT_TRUE(r.IsEqual(result)) << "regions not the same";
 982   }
 983
 984   {  // the rectangles will be merged
 985     nsRegion r(nsRect(0, 100, 200, 100));
 986     r.Or(r, nsRect(0, 200, 300, 200));
 987
 988     r.SimplifyOutwardByArea(100 * 100);
 989
 990     nsRegion result(nsRect(0, 100, 300, 300));
 991
 992     EXPECT_TRUE(r.IsEqual(result)) << "regions not merged";
 993   }
 994
 995   {  // two rectangle on the first span
 996     // one on the second
 997     nsRegion r(nsRect(0, 100, 200, 100));
 998     r.Or(r, nsRect(0, 200, 300, 200));
 999     r.Or(r, nsRect(250, 100, 50, 100));
1000
1001     EXPECT_TRUE(r.GetNumRects() == 3) << "wrong number of rects";
1002
1003     r.SimplifyOutwardByArea(100 * 100);
1004
1005     nsRegion result(nsRect(0, 100, 300, 300));
1006
1007     EXPECT_TRUE(r.IsEqual(result)) << "regions not merged";
1008   }
1009
1010   {  // the rectangles will be merged
1011     nsRegion r(nsRect(0, 100, 200, 100));
1012     r.Or(r, nsRect(0, 200, 300, 200));
1013     r.Or(r, nsRect(250, 100, 50, 100));
1014     r.Sub(r, nsRect(200, 200, 40, 200));
1015
1016     EXPECT_TRUE(r.GetNumRects() == 4) << "wrong number of rects";
1017
1018     r.SimplifyOutwardByArea(100 * 100);
1019
1020     nsRegion result(nsRect(0, 100, 300, 300));
1021     result.Sub(result, nsRect(200, 100, 40, 300));
1022
1023     EXPECT_TRUE(r.IsEqual(result)) << "regions not merged";
1024   }
1025
1026   {  // three spans of rectangles
1027     nsRegion r(nsRect(0, 100, 200, 100));
1028     r.Or(r, nsRect(0, 200, 300, 200));
1029     r.Or(r, nsRect(250, 100, 50, 50));
1030     r.Sub(r, nsRect(200, 200, 40, 200));
1031
1032     r.SimplifyOutwardByArea(100 * 100);
1033
1034     nsRegion result(nsRect(0, 100, 300, 300));
1035     result.Sub(result, nsRect(200, 100, 40, 300));
1036
1037     EXPECT_TRUE(r.IsEqual(result)) << "regions not merged";
1038   }
1039
1040   {  // three spans of rectangles and an unmerged rectangle
1041     nsRegion r(nsRect(0, 100, 200, 100));
1042     r.Or(r, nsRect(0, 200, 300, 200));
1043     r.Or(r, nsRect(250, 100, 50, 50));
1044     r.Sub(r, nsRect(200, 200, 40, 200));
1045     r.Or(r, nsRect(250, 900, 150, 50));
1046
1047     r.SimplifyOutwardByArea(100 * 100);
1048
1049     nsRegion result(nsRect(0, 100, 300, 300));
1050     result.Sub(result, nsRect(200, 100, 40, 300));
1051     result.Or(result, nsRect(250, 900, 150, 50));
1052
1053     EXPECT_TRUE(r.IsEqual(result)) << "regions not merged";
1054   }
1055
1056   {  // unmerged regions
1057     nsRegion r(nsRect(0, 100, 200, 100));
1058     r.Or(r, nsRect(0, 200, 300, 200));
1059
1060     r.SimplifyOutwardByArea(100);
1061
1062     nsRegion result(nsRect(0, 100, 200, 100));
1063     result.Or(result, nsRect(0, 200, 300, 200));
1064
1065     EXPECT_TRUE(r.IsEqual(result)) << "regions not merged";
1066   }
1067
1068   {  // empty region
1069     // just make sure this doesn't crash.
1070     nsRegion r;
1071     r.SimplifyOutwardByArea(100);
1072   }
1073 }
1074
1075 TEST(Gfx, RegionContains)
1076 {
1077   {  // ensure Contains works on a simple region
1078     nsRegion r(nsRect(0, 0, 100, 100));
1079
1080     EXPECT_TRUE(r.Contains(0, 0));
1081     EXPECT_TRUE(r.Contains(0, 99));
1082     EXPECT_TRUE(r.Contains(99, 0));
1083     EXPECT_TRUE(r.Contains(99, 99));
1084
1085     EXPECT_FALSE(r.Contains(-1, 50));
1086     EXPECT_FALSE(r.Contains(100, 50));
1087     EXPECT_FALSE(r.Contains(50, -1));
1088     EXPECT_FALSE(r.Contains(50, 100));
1089
1090     EXPECT_TRUE(r.Contains(nsRect(0, 0, 100, 100)));
1091     EXPECT_TRUE(r.Contains(nsRect(99, 99, 1, 1)));
1092
1093     EXPECT_FALSE(r.Contains(nsRect(100, 100, 1, 1)));
1094     EXPECT_FALSE(r.Contains(nsRect(100, 100, 0, 0)));
1095   }
1096
1097   {  // empty regions contain nothing
1098     nsRegion r(nsRect(100, 100, 0, 0));
1099
1100     EXPECT_FALSE(r.Contains(0, 0));
1101     EXPECT_FALSE(r.Contains(100, 100));
1102     EXPECT_FALSE(r.Contains(nsRect(100, 100, 0, 0)));
1103     EXPECT_FALSE(r.Contains(nsRect(100, 100, 1, 1)));
1104   }
1105
1106   {  // complex region contain tests
1107     // The region looks like this, with two squares that overlap.
1108     // (hard to do accurately with ASCII art)
1109     // +------+
1110     // |      |
1111     // |      +--+
1112     // |         |
1113     // +--+      |
1114     //    |      |
1115     //    +------+
1116     nsRegion r(nsRect(0, 0, 100, 100));
1117     r.OrWith(nsRect(50, 50, 100, 100));
1118
1119     EXPECT_TRUE(r.Contains(0, 0));
1120     EXPECT_TRUE(r.Contains(99, 99));
1121     EXPECT_TRUE(r.Contains(50, 100));
1122     EXPECT_TRUE(r.Contains(100, 50));
1123     EXPECT_TRUE(r.Contains(149, 149));
1124
1125     EXPECT_FALSE(r.Contains(49, 100));
1126     EXPECT_FALSE(r.Contains(100, 49));
1127     EXPECT_FALSE(r.Contains(150, 150));
1128
1129     EXPECT_TRUE(r.Contains(nsRect(100, 100, 1, 1)));
1130     EXPECT_FALSE(r.Contains(nsRect(49, 99, 2, 2)));
1131   }
1132
1133   {  // region with a hole
1134     nsRegion r(nsRect(0, 0, 100, 100));
1135     r.SubOut(nsRect(40, 40, 10, 10));
1136
1137     EXPECT_TRUE(r.Contains(0, 0));
1138     EXPECT_TRUE(r.Contains(39, 39));
1139     EXPECT_FALSE(r.Contains(40, 40));
1140     EXPECT_FALSE(r.Contains(49, 49));
1141     EXPECT_TRUE(r.Contains(50, 50));
1142
1143     EXPECT_FALSE(r.Contains(nsRect(40, 40, 10, 10)));
1144     EXPECT_FALSE(r.Contains(nsRect(39, 39, 2, 2)));
1145   }
1146 }
1147
1148 #define DILATE_VALUE 0x88
1149 #define REGION_VALUE 0xff
1150
1151 struct RegionBitmap {
1152   RegionBitmap(unsigned char* bitmap, int width, int height)
1153       : bitmap(bitmap), width(width), height(height) {}
1154
1155   void clear() {
1156     for (int y = 0; y < height; y++) {
1157       for (int x = 0; x < width; x++) {
1158         bitmap[x + y * width] = 0;
1159       }
1160     }
1161   }
1162
1163   void set(nsRegion& region) {
1164     clear();
1165     for (auto iter = region.RectIter(); !iter.Done(); iter.Next()) {
1166       const nsRect& r = iter.Get();
1167       for (int y = r.Y(); y < r.YMost(); y++) {
1168         for (int x = r.X(); x < r.XMost(); x++) {
1169           bitmap[x + y * width] = REGION_VALUE;
1170         }
1171       }
1172     }
1173   }
1174
1175   void dilate() {
1176     for (int y = 0; y < height; y++) {
1177       for (int x = 0; x < width; x++) {
1178         if (bitmap[x + y * width] == REGION_VALUE) {
1179           for (int yn = std::max(y - 1, 0); yn <= std::min(y + 1, height - 1);
1180                yn++) {
1181             for (int xn = std::max(x - 1, 0); xn <= std::min(x + 1, width - 1);
1182                  xn++) {
1183               if (bitmap[xn + yn * width] == 0)
1184                 bitmap[xn + yn * width] = DILATE_VALUE;
1185             }
1186           }
1187         }
1188       }
1189     }
1190   }
1191   void compare(RegionBitmap& reference) {
1192     for (int y = 0; y < height; y++) {
1193       for (int x = 0; x < width; x++) {
1194         EXPECT_EQ(bitmap[x + y * width], reference.bitmap[x + y * width]);
1195       }
1196     }
1197   }
1198
1199   unsigned char* bitmap;
1200   int width;
1201   int height;
1202 };
1203
1204 static void VisitEdge(void* closure, VisitSide side, int x1, int y1, int x2,
1205                       int y2) {
1206   EXPECT_GE(x2, x1);
1207   RegionBitmap* visitor = static_cast<RegionBitmap*>(closure);
1208   unsigned char* bitmap = visitor->bitmap;
1209   const int width = visitor->width;
1210
1211   if (side == VisitSide::TOP) {
1212     while (x1 != x2) {
1213       bitmap[x1 + (y1 - 1) * width] = DILATE_VALUE;
1214       x1++;
1215     }
1216   } else if (side == VisitSide::BOTTOM) {
1217     while (x1 != x2) {
1218       bitmap[x1 + y1 * width] = DILATE_VALUE;
1219       x1++;
1220     }
1221   } else if (side == VisitSide::LEFT) {
1222     while (y1 != y2) {
1223       bitmap[x1 - 1 + y1 * width] = DILATE_VALUE;
1224       y1++;
1225     }
1226   } else if (side == VisitSide::RIGHT) {
1227     while (y1 != y2) {
1228       bitmap[x1 + y1 * width] = DILATE_VALUE;
1229       y1++;
1230     }
1231   }
1232 }
1233
1234 static void TestVisit(nsRegion& r) {
1235   auto reference = mozilla::MakeUnique<unsigned char[]>(600 * 600);
1236   auto result = mozilla::MakeUnique<unsigned char[]>(600 * 600);
1237   RegionBitmap ref(reference.get(), 600, 600);
1238   RegionBitmap res(result.get(), 600, 600);
1239
1240   ref.set(r);
1241   ref.dilate();
1242
1243   res.set(r);
1244   r.VisitEdges(VisitEdge, &res);
1245   res.compare(ref);
1246 }
1247
1248 TEST(Gfx, RegionVisitEdges)
1249 {
1250   {  // visit edges
1251     nsRegion r(nsRect(20, 20, 100, 100));
1252     r.Or(r, nsRect(20, 120, 200, 100));
1253     TestVisit(r);
1254   }
1255
1256   {  // two rects side by side - 1 pixel inbetween
1257     nsRegion r(nsRect(20, 20, 100, 100));
1258     r.Or(r, nsRect(121, 20, 100, 100));
1259     TestVisit(r);
1260   }
1261
1262   {  // two rects side by side - 2 pixels inbetween
1263     nsRegion r(nsRect(20, 20, 100, 100));
1264     r.Or(r, nsRect(122, 20, 100, 100));
1265     TestVisit(r);
1266   }
1267
1268   {
1269     // only corner of the rects are touching
1270     nsRegion r(nsRect(20, 20, 100, 100));
1271     r.Or(r, nsRect(120, 120, 100, 100));
1272
1273     TestVisit(r);
1274   }
1275
1276   {
1277     // corners are 1 pixel away
1278     nsRegion r(nsRect(20, 20, 100, 100));
1279     r.Or(r, nsRect(121, 120, 100, 100));
1280
1281     TestVisit(r);
1282   }
1283
1284   {
1285     // vertically separated
1286     nsRegion r(nsRect(20, 20, 100, 100));
1287     r.Or(r, nsRect(120, 125, 100, 100));
1288
1289     TestVisit(r);
1290   }
1291
1292   {
1293     // not touching
1294     nsRegion r(nsRect(20, 20, 100, 100));
1295     r.Or(r, nsRect(130, 120, 100, 100));
1296     r.Or(r, nsRect(240, 20, 100, 100));
1297
1298     TestVisit(r);
1299   }
1300
1301   {  // rect with a hole in it
1302     nsRegion r(nsRect(20, 20, 100, 100));
1303     r.Sub(r, nsRect(40, 40, 10, 10));
1304
1305     TestVisit(r);
1306   }
1307   {
1308     // left overs
1309     nsRegion r(nsRect(20, 20, 10, 10));
1310     r.Or(r, nsRect(50, 20, 10, 10));
1311     r.Or(r, nsRect(90, 20, 10, 10));
1312     r.Or(r, nsRect(24, 30, 10, 10));
1313     r.Or(r, nsRect(20, 40, 15, 10));
1314     r.Or(r, nsRect(50, 40, 15, 10));
1315     r.Or(r, nsRect(90, 40, 15, 10));
1316
1317     TestVisit(r);
1318   }
1319
1320   {
1321     // vertically separated
1322     nsRegion r(nsRect(20, 20, 100, 100));
1323     r.Or(r, nsRect(120, 125, 100, 100));
1324
1325     TestVisit(r);
1326   }
1327
1328   {
1329     // two upper rects followed by a lower one
1330     // on the same line
1331     nsRegion r(nsRect(5, 5, 50, 50));
1332     r.Or(r, nsRect(100, 5, 50, 50));
1333     r.Or(r, nsRect(200, 50, 50, 50));
1334
1335     TestVisit(r);
1336   }
1337
1338   {
1339     // bug 1130978.
1340     nsRegion r(nsRect(4, 1, 61, 49));
1341     r.Or(r, nsRect(115, 1, 99, 49));
1342     r.Or(r, nsRect(115, 49, 99, 1));
1343     r.Or(r, nsRect(12, 50, 11, 5));
1344     r.Or(r, nsRect(25, 50, 28, 5));
1345     r.Or(r, nsRect(115, 50, 99, 5));
1346     r.Or(r, nsRect(115, 55, 99, 12));
1347
1348     TestVisit(r);
1349   }
1350 }