Source/WebKit/chromium/tests/RegionTest.cpp

   1 /*
   2  * Copyright (C) 2012 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1.  Redistributions of source code must retain the above copyright
   8  *     notice, this list of conditions and the following disclaimer.
   9  * 2.  Redistributions in binary form must reproduce the above copyright
  10  *     notice, this list of conditions and the following disclaimer in the
  11  *     documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  15  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  16  * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  17  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  18  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  19  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
  20  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  22  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23  */
  24
  25 #include "config.h"
  26
  27 #include "Region.h"
  28
  29 #include <gtest/gtest.h>
  30
  31 using namespace WebCore;
  32
  33 namespace {
  34
  35 #define TEST_INSIDE_RECT(r, x, y, w, h)                      \
  36     EXPECT_TRUE(r.contains(IntPoint(x, y)));                 \
  37     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y)));         \
  38     EXPECT_TRUE(r.contains(IntPoint(x, y + h - 1)));         \
  39     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y + h - 1))); \
  40     EXPECT_TRUE(r.contains(IntPoint(x, y + h / 2)));         \
  41     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y + h / 2))); \
  42     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y)));         \
  43     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y + h - 1))); \
  44     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y + h / 2))); \
  45
  46 #define TEST_LEFT_OF_RECT(r, x, y, w, h)                     \
  47     EXPECT_FALSE(r.contains(IntPoint(x - 1, y)));            \
  48     EXPECT_FALSE(r.contains(IntPoint(x - 1, y + h - 1)));    \
  49
  50 #define TEST_RIGHT_OF_RECT(r, x, y, w, h)                 \
  51     EXPECT_FALSE(r.contains(IntPoint(x + w, y)));         \
  52     EXPECT_FALSE(r.contains(IntPoint(x + w, y + h - 1))); \
  53
  54 #define TEST_TOP_OF_RECT(r, x, y, w, h)                   \
  55     EXPECT_FALSE(r.contains(IntPoint(x, y - 1)));         \
  56     EXPECT_FALSE(r.contains(IntPoint(x + w - 1, y - 1))); \
  57
  58 #define TEST_BOTTOM_OF_RECT(r, x, y, w, h)                \
  59     EXPECT_FALSE(r.contains(IntPoint(x, y + h)));         \
  60     EXPECT_FALSE(r.contains(IntPoint(x + w - 1, y + h))); \
  61
  62 TEST(RegionTest, containsPoint)
  63 {
  64     Region r;
  65
  66     EXPECT_FALSE(r.contains(IntPoint(0, 0)));
  67
  68     r.unite(IntRect(35, 35, 1, 1));
  69     TEST_INSIDE_RECT(r, 35, 35, 1, 1);
  70     TEST_LEFT_OF_RECT(r, 35, 35, 1, 1);
  71     TEST_RIGHT_OF_RECT(r, 35, 35, 1, 1);
  72     TEST_TOP_OF_RECT(r, 35, 35, 1, 1);
  73     TEST_BOTTOM_OF_RECT(r, 35, 35, 1, 1);
  74
  75     r.unite(IntRect(30, 30, 10, 10));
  76     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
  77     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
  78     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
  79     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
  80     TEST_BOTTOM_OF_RECT(r, 30, 30, 10, 10);
  81
  82     r.unite(IntRect(31, 40, 10, 10));
  83     EXPECT_FALSE(r.contains(IntPoint(30, 40)));
  84     EXPECT_TRUE(r.contains(IntPoint(31, 40)));
  85     EXPECT_FALSE(r.contains(IntPoint(40, 39)));
  86     EXPECT_TRUE(r.contains(IntPoint(40, 40)));
  87
  88     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
  89     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
  90     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
  91     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
  92     TEST_INSIDE_RECT(r, 31, 40, 10, 10);
  93     TEST_LEFT_OF_RECT(r, 31, 40, 10, 10);
  94     TEST_RIGHT_OF_RECT(r, 31, 40, 10, 10);
  95     TEST_BOTTOM_OF_RECT(r, 31, 40, 10, 10);
  96
  97     r.unite(IntRect(42, 40, 10, 10));
  98
  99     TEST_INSIDE_RECT(r, 42, 40, 10, 10);
 100     TEST_LEFT_OF_RECT(r, 42, 40, 10, 10);
 101     TEST_RIGHT_OF_RECT(r, 42, 40, 10, 10);
 102     TEST_TOP_OF_RECT(r, 42, 40, 10, 10);
 103     TEST_BOTTOM_OF_RECT(r, 42, 40, 10, 10);
 104
 105     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
 106     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
 107     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
 108     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
 109     TEST_INSIDE_RECT(r, 31, 40, 10, 10);
 110     TEST_LEFT_OF_RECT(r, 31, 40, 10, 10);
 111     TEST_RIGHT_OF_RECT(r, 31, 40, 10, 10);
 112     TEST_BOTTOM_OF_RECT(r, 31, 40, 10, 10);
 113 }
 114
 115 TEST(RegionTest, emptySpan)
 116 {
 117     Region r;
 118     r.unite(IntRect(5, 0, 10, 10));
 119     r.unite(IntRect(0, 5, 10, 10));
 120     r.subtract(IntRect(7, 7, 10, 0));
 121
 122     Vector<IntRect> rects = r.rects();
 123     for (size_t i = 0; i < rects.size(); ++i)
 124         EXPECT_FALSE(rects[i].isEmpty());
 125 }
 126
 127 #define TEST_NO_INTERSECT(a, b)      \
 128 {                                    \
 129     Region ar = a;                   \
 130     Region br = b;                   \
 131     EXPECT_FALSE(ar.intersects(br)); \
 132     EXPECT_FALSE(br.intersects(ar)); \
 133 }
 134
 135 #define TEST_INTERSECT(a, b)        \
 136 {                                   \
 137     Region ar = a;                  \
 138     Region br = b;                  \
 139     EXPECT_TRUE(ar.intersects(br)); \
 140     EXPECT_TRUE(br.intersects(ar)); \
 141 }
 142
 143 TEST(RegionTest, intersectsRegion)
 144 {
 145     Region r;
 146
 147     TEST_NO_INTERSECT(IntRect(), IntRect());
 148     TEST_NO_INTERSECT(IntRect(), IntRect(0, 0, 1, 1));
 149     TEST_NO_INTERSECT(IntRect(), IntRect(1, 1, 1, 1));
 150
 151     r.unite(IntRect(0, 0, 1, 1));
 152     TEST_NO_INTERSECT(r, IntRect());
 153     TEST_INTERSECT(r, IntRect(0, 0, 1, 1));
 154     TEST_INTERSECT(r, IntRect(0, 0, 2, 2));
 155     TEST_INTERSECT(r, IntRect(-1, 0, 2, 2));
 156     TEST_INTERSECT(r, IntRect(-1, -1, 2, 2));
 157     TEST_INTERSECT(r, IntRect(0, -1, 2, 2));
 158     TEST_INTERSECT(r, IntRect(-1, -1, 3, 3));
 159
 160     r.unite(IntRect(0, 0, 3, 3));
 161     r.unite(IntRect(10, 0, 3, 3));
 162     r.unite(IntRect(0, 10, 13, 3));
 163     TEST_NO_INTERSECT(r, IntRect());
 164     TEST_INTERSECT(r, IntRect(1, 1, 1, 1));
 165     TEST_INTERSECT(r, IntRect(0, 0, 2, 2));
 166     TEST_INTERSECT(r, IntRect(1, 0, 2, 2));
 167     TEST_INTERSECT(r, IntRect(1, 1, 2, 2));
 168     TEST_INTERSECT(r, IntRect(0, 1, 2, 2));
 169     TEST_INTERSECT(r, IntRect(0, 0, 3, 3));
 170     TEST_INTERSECT(r, IntRect(-1, -1, 2, 2));
 171     TEST_INTERSECT(r, IntRect(2, -1, 2, 2));
 172     TEST_INTERSECT(r, IntRect(2, 2, 2, 2));
 173     TEST_INTERSECT(r, IntRect(-1, 2, 2, 2));
 174
 175     TEST_INTERSECT(r, IntRect(11, 1, 1, 1));
 176     TEST_INTERSECT(r, IntRect(10, 0, 2, 2));
 177     TEST_INTERSECT(r, IntRect(11, 0, 2, 2));
 178     TEST_INTERSECT(r, IntRect(11, 1, 2, 2));
 179     TEST_INTERSECT(r, IntRect(10, 1, 2, 2));
 180     TEST_INTERSECT(r, IntRect(10, 0, 3, 3));
 181     TEST_INTERSECT(r, IntRect(9, -1, 2, 2));
 182     TEST_INTERSECT(r, IntRect(12, -1, 2, 2));
 183     TEST_INTERSECT(r, IntRect(12, 2, 2, 2));
 184     TEST_INTERSECT(r, IntRect(9, 2, 2, 2));
 185
 186     TEST_INTERSECT(r, IntRect(0, -1, 13, 5));
 187     TEST_INTERSECT(r, IntRect(1, -1, 11, 5));
 188     TEST_INTERSECT(r, IntRect(2, -1, 9, 5));
 189     TEST_INTERSECT(r, IntRect(2, -1, 8, 5));
 190     TEST_INTERSECT(r, IntRect(3, -1, 8, 5));
 191     TEST_NO_INTERSECT(r, IntRect(3, -1, 7, 5));
 192
 193     TEST_INTERSECT(r, IntRect(0, 1, 13, 1));
 194     TEST_INTERSECT(r, IntRect(1, 1, 11, 1));
 195     TEST_INTERSECT(r, IntRect(2, 1, 9, 1));
 196     TEST_INTERSECT(r, IntRect(2, 1, 8, 1));
 197     TEST_INTERSECT(r, IntRect(3, 1, 8, 1));
 198     TEST_NO_INTERSECT(r, IntRect(3, 1, 7, 1));
 199
 200     TEST_INTERSECT(r, IntRect(0, 0, 13, 13));
 201     TEST_INTERSECT(r, IntRect(0, 1, 13, 11));
 202     TEST_INTERSECT(r, IntRect(0, 2, 13, 9));
 203     TEST_INTERSECT(r, IntRect(0, 2, 13, 8));
 204     TEST_INTERSECT(r, IntRect(0, 3, 13, 8));
 205     TEST_NO_INTERSECT(r, IntRect(0, 3, 13, 7));
 206 }
 207
 208 TEST(RegionTest, ReadPastFullSpanVectorInIntersectsTest)
 209 {
 210     Region r;
 211
 212     // This region has enough spans to fill its allocated Vector exactly.
 213     r.unite(IntRect(400, 300, 1, 800));
 214     r.unite(IntRect(785, 585, 1, 1));
 215     r.unite(IntRect(787, 585, 1, 1));
 216     r.unite(IntRect(0, 587, 16, 162));
 217     r.unite(IntRect(26, 590, 300, 150));
 218     r.unite(IntRect(196, 750, 1, 1));
 219     r.unite(IntRect(0, 766, 1, 1));
 220     r.unite(IntRect(0, 782, 1, 1));
 221     r.unite(IntRect(745, 798, 1, 1));
 222     r.unite(IntRect(795, 882, 10, 585));
 223     r.unite(IntRect(100, 1499, 586, 1));
 224     r.unite(IntRect(100, 1500, 585, 784));
 225     // This query rect goes past the bottom of the Region, causing the
 226     // test to reach the last span and try go past it. It should not read
 227     // memory off the end of the span Vector.
 228     TEST_NO_INTERSECT(r, IntRect(0, 2184, 1, 150));
 229 }
 230
 231 #define TEST_NO_CONTAINS(a, b)     \
 232 {                                  \
 233     Region ar = a;                 \
 234     Region br = b;                 \
 235     EXPECT_FALSE(ar.contains(br)); \
 236 }
 237
 238 #define TEST_CONTAINS(a, b)       \
 239 {                                 \
 240     Region ar = a;                \
 241     Region br = b;                \
 242     EXPECT_TRUE(ar.contains(br)); \
 243 }
 244
 245 TEST(RegionTest, containsRegion)
 246 {
 247     TEST_CONTAINS(IntRect(), IntRect());
 248     TEST_NO_CONTAINS(IntRect(), IntRect(0, 0, 1, 1));
 249     TEST_NO_CONTAINS(IntRect(), IntRect(1, 1, 1, 1));
 250
 251     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(11, 10, 1, 1));
 252     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 11, 1, 1));
 253     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 10, 1, 1));
 254     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 9, 1, 1));
 255     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 9, 2, 2));
 256     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 9, 2, 2));
 257     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 10, 2, 2));
 258     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 10, 2, 2));
 259     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 9, 3, 3));
 260
 261     Region hLines;
 262     for (int i = 10; i < 20; i += 2)
 263         hLines.unite(IntRect(i, 10, 1, 10));
 264
 265     TEST_CONTAINS(IntRect(10, 10, 9, 10), hLines);
 266     TEST_NO_CONTAINS(IntRect(10, 10, 9, 9), hLines);
 267     TEST_NO_CONTAINS(IntRect(10, 11, 9, 9), hLines);
 268     TEST_NO_CONTAINS(IntRect(10, 10, 8, 10), hLines);
 269     TEST_NO_CONTAINS(IntRect(11, 10, 8, 10), hLines);
 270
 271     Region vLines;
 272     for (int i = 10; i < 20; i += 2)
 273         vLines.unite(IntRect(10, i, 10, 1));
 274
 275     TEST_CONTAINS(IntRect(10, 10, 10, 9), vLines);
 276     TEST_NO_CONTAINS(IntRect(10, 10, 9, 9), vLines);
 277     TEST_NO_CONTAINS(IntRect(11, 10, 9, 9), vLines);
 278     TEST_NO_CONTAINS(IntRect(10, 10, 10, 8), vLines);
 279     TEST_NO_CONTAINS(IntRect(10, 11, 10, 8), vLines);
 280
 281     Region grid;
 282     for (int i = 10; i < 20; i += 2)
 283         for (int j = 10; j < 20; j += 2)
 284             grid.unite(IntRect(i, j, 1, 1));
 285
 286     TEST_CONTAINS(IntRect(10, 10, 9, 9), grid);
 287     TEST_NO_CONTAINS(IntRect(10, 10, 9, 8), grid);
 288     TEST_NO_CONTAINS(IntRect(10, 11, 9, 8), grid);
 289     TEST_NO_CONTAINS(IntRect(10, 10, 8, 9), grid);
 290     TEST_NO_CONTAINS(IntRect(11, 10, 8, 9), grid);
 291
 292     TEST_CONTAINS(hLines, hLines);
 293     TEST_CONTAINS(vLines, vLines);
 294     TEST_NO_CONTAINS(vLines, hLines);
 295     TEST_NO_CONTAINS(hLines, vLines);
 296     TEST_CONTAINS(grid, grid);
 297     TEST_CONTAINS(hLines, grid);
 298     TEST_CONTAINS(vLines, grid);
 299     TEST_NO_CONTAINS(grid, hLines);
 300     TEST_NO_CONTAINS(grid, vLines);
 301
 302     for (int i = 10; i < 20; i += 2)
 303         TEST_CONTAINS(hLines, IntRect(i, 10, 1, 10));
 304
 305     for (int i = 10; i < 20; i += 2)
 306         TEST_CONTAINS(vLines, IntRect(10, i, 10, 1));
 307
 308     for (int i = 10; i < 20; i += 2)
 309         for (int j = 10; j < 20; j += 2)
 310             TEST_CONTAINS(grid, IntRect(i, j, 1, 1));
 311
 312     Region container;
 313     container.unite(IntRect(0, 0, 40, 20));
 314     container.unite(IntRect(0, 20, 41, 20));
 315     TEST_CONTAINS(container, IntRect(5, 5, 30, 30));
 316
 317     container = Region();
 318     container.unite(IntRect(0, 0, 10, 10));
 319     container.unite(IntRect(0, 30, 10, 10));
 320     container.unite(IntRect(30, 30, 10, 10));
 321     container.unite(IntRect(30, 0, 10, 10));
 322     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
 323
 324     container = Region();
 325     container.unite(IntRect(0, 0, 10, 10));
 326     container.unite(IntRect(0, 30, 10, 10));
 327     container.unite(IntRect(30, 0, 10, 40));
 328     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
 329
 330     container = Region();
 331     container.unite(IntRect(30, 0, 10, 10));
 332     container.unite(IntRect(30, 30, 10, 10));
 333     container.unite(IntRect(0, 0, 10, 40));
 334     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
 335
 336     container = Region();
 337     container.unite(IntRect(0, 0, 10, 40));
 338     container.unite(IntRect(30, 0, 10, 40));
 339     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
 340
 341     container = Region();
 342     container.unite(IntRect(0, 0, 40, 40));
 343     TEST_NO_CONTAINS(container, IntRect(10, -1, 20, 10));
 344
 345     container = Region();
 346     container.unite(IntRect(0, 0, 40, 40));
 347     TEST_NO_CONTAINS(container, IntRect(10, 31, 20, 10));
 348
 349     container = Region();
 350     container.unite(IntRect(0, 0, 40, 20));
 351     container.unite(IntRect(0, 20, 41, 20));
 352     TEST_NO_CONTAINS(container, IntRect(-1, 10, 10, 20));
 353
 354     container = Region();
 355     container.unite(IntRect(0, 0, 40, 20));
 356     container.unite(IntRect(0, 20, 41, 20));
 357     TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20));
 358
 359     container = Region();
 360     container.unite(IntRect(0, 0, 40, 40));
 361     container.subtract(IntRect(0, 20, 60, 0));
 362     TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20));
 363 }
 364
 365 TEST(RegionTest, unite)
 366 {
 367     Region r;
 368     Region r2;
 369
 370     // A rect uniting a contained rect does not change the region.
 371     r2 = r = IntRect(0, 0, 50, 50);
 372     r2.unite(IntRect(20, 20, 10, 10));
 373     EXPECT_EQ(r, r2);
 374
 375     // A rect uniting a containing rect gives back the containing rect.
 376     r = IntRect(0, 0, 50, 50);
 377     r.unite(IntRect(0, 0, 100, 100));
 378     EXPECT_EQ(Region(IntRect(0, 0, 100, 100)), r);
 379
 380     // A complex region uniting a contained rect does not change the region.
 381     r = IntRect(0, 0, 50, 50);
 382     r.unite(IntRect(100, 0, 50, 50));
 383     r2 = r;
 384     r2.unite(IntRect(20, 20, 10, 10));
 385     EXPECT_EQ(r, r2);
 386
 387     // A complex region uniting a containing rect gives back the containing rect.
 388     r = IntRect(0, 0, 50, 50);
 389     r.unite(IntRect(100, 0, 50, 50));
 390     r. unite(IntRect(0, 0, 500, 500));
 391     EXPECT_EQ(Region(IntRect(0, 0, 500, 500)), r);
 392 }
 393
 394 } // namespace