third_party/WebKit/Source/platform/geometry/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 #include "platform/geometry/Region.h"
  27
  28 #include <gtest/gtest.h>
  29
  30 namespace blink {
  31
  32 #define TEST_INSIDE_RECT(r, x, y, w, h)                      \
  33     EXPECT_TRUE(r.contains(IntPoint(x, y)));                 \
  34     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y)));         \
  35     EXPECT_TRUE(r.contains(IntPoint(x, y + h - 1)));         \
  36     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y + h - 1))); \
  37     EXPECT_TRUE(r.contains(IntPoint(x, y + h / 2)));         \
  38     EXPECT_TRUE(r.contains(IntPoint(x + w - 1, y + h / 2))); \
  39     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y)));         \
  40     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y + h - 1))); \
  41     EXPECT_TRUE(r.contains(IntPoint(x + w / 2, y + h / 2))); \
  42
  43 #define TEST_LEFT_OF_RECT(r, x, y, w, h)                     \
  44     EXPECT_FALSE(r.contains(IntPoint(x - 1, y)));            \
  45     EXPECT_FALSE(r.contains(IntPoint(x - 1, y + h - 1)));    \
  46
  47 #define TEST_RIGHT_OF_RECT(r, x, y, w, h)                 \
  48     EXPECT_FALSE(r.contains(IntPoint(x + w, y)));         \
  49     EXPECT_FALSE(r.contains(IntPoint(x + w, y + h - 1))); \
  50
  51 #define TEST_TOP_OF_RECT(r, x, y, w, h)                   \
  52     EXPECT_FALSE(r.contains(IntPoint(x, y - 1)));         \
  53     EXPECT_FALSE(r.contains(IntPoint(x + w - 1, y - 1))); \
  54
  55 #define TEST_BOTTOM_OF_RECT(r, x, y, w, h)                \
  56     EXPECT_FALSE(r.contains(IntPoint(x, y + h)));         \
  57     EXPECT_FALSE(r.contains(IntPoint(x + w - 1, y + h))); \
  58
  59 TEST(RegionTest, containsPoint)
  60 {
  61     Region r;
  62
  63     EXPECT_FALSE(r.contains(IntPoint(0, 0)));
  64
  65     r.unite(IntRect(35, 35, 1, 1));
  66     TEST_INSIDE_RECT(r, 35, 35, 1, 1);
  67     TEST_LEFT_OF_RECT(r, 35, 35, 1, 1);
  68     TEST_RIGHT_OF_RECT(r, 35, 35, 1, 1);
  69     TEST_TOP_OF_RECT(r, 35, 35, 1, 1);
  70     TEST_BOTTOM_OF_RECT(r, 35, 35, 1, 1);
  71
  72     r.unite(IntRect(30, 30, 10, 10));
  73     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
  74     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
  75     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
  76     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
  77     TEST_BOTTOM_OF_RECT(r, 30, 30, 10, 10);
  78
  79     r.unite(IntRect(31, 40, 10, 10));
  80     EXPECT_FALSE(r.contains(IntPoint(30, 40)));
  81     EXPECT_TRUE(r.contains(IntPoint(31, 40)));
  82     EXPECT_FALSE(r.contains(IntPoint(40, 39)));
  83     EXPECT_TRUE(r.contains(IntPoint(40, 40)));
  84
  85     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
  86     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
  87     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
  88     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
  89     TEST_INSIDE_RECT(r, 31, 40, 10, 10);
  90     TEST_LEFT_OF_RECT(r, 31, 40, 10, 10);
  91     TEST_RIGHT_OF_RECT(r, 31, 40, 10, 10);
  92     TEST_BOTTOM_OF_RECT(r, 31, 40, 10, 10);
  93
  94     r.unite(IntRect(42, 40, 10, 10));
  95
  96     TEST_INSIDE_RECT(r, 42, 40, 10, 10);
  97     TEST_LEFT_OF_RECT(r, 42, 40, 10, 10);
  98     TEST_RIGHT_OF_RECT(r, 42, 40, 10, 10);
  99     TEST_TOP_OF_RECT(r, 42, 40, 10, 10);
 100     TEST_BOTTOM_OF_RECT(r, 42, 40, 10, 10);
 101
 102     TEST_INSIDE_RECT(r, 30, 30, 10, 10);
 103     TEST_LEFT_OF_RECT(r, 30, 30, 10, 10);
 104     TEST_RIGHT_OF_RECT(r, 30, 30, 10, 10);
 105     TEST_TOP_OF_RECT(r, 30, 30, 10, 10);
 106     TEST_INSIDE_RECT(r, 31, 40, 10, 10);
 107     TEST_LEFT_OF_RECT(r, 31, 40, 10, 10);
 108     TEST_RIGHT_OF_RECT(r, 31, 40, 10, 10);
 109     TEST_BOTTOM_OF_RECT(r, 31, 40, 10, 10);
 110 }
 111
 112 TEST(RegionTest, emptySpan)
 113 {
 114     Region r;
 115     r.unite(IntRect(5, 0, 10, 10));
 116     r.unite(IntRect(0, 5, 10, 10));
 117     r.subtract(IntRect(7, 7, 10, 0));
 118
 119     Vector<IntRect> rects = r.rects();
 120     for (size_t i = 0; i < rects.size(); ++i)
 121         EXPECT_FALSE(rects[i].isEmpty());
 122 }
 123
 124 #define TEST_NO_INTERSECT(a, b)      \
 125 {                                    \
 126     Region ar = a;                   \
 127     Region br = b;                   \
 128     EXPECT_FALSE(ar.intersects(br)); \
 129     EXPECT_FALSE(br.intersects(ar)); \
 130 }
 131
 132 #define TEST_INTERSECT(a, b)        \
 133 {                                   \
 134     Region ar = a;                  \
 135     Region br = b;                  \
 136     EXPECT_TRUE(ar.intersects(br)); \
 137     EXPECT_TRUE(br.intersects(ar)); \
 138 }
 139
 140 TEST(RegionTest, intersectsRegion)
 141 {
 142     Region r;
 143
 144     TEST_NO_INTERSECT(IntRect(), IntRect());
 145     TEST_NO_INTERSECT(IntRect(), IntRect(0, 0, 1, 1));
 146     TEST_NO_INTERSECT(IntRect(), IntRect(1, 1, 1, 1));
 147
 148     r.unite(IntRect(0, 0, 1, 1));
 149     TEST_NO_INTERSECT(r, IntRect());
 150     TEST_INTERSECT(r, IntRect(0, 0, 1, 1));
 151     TEST_INTERSECT(r, IntRect(0, 0, 2, 2));
 152     TEST_INTERSECT(r, IntRect(-1, 0, 2, 2));
 153     TEST_INTERSECT(r, IntRect(-1, -1, 2, 2));
 154     TEST_INTERSECT(r, IntRect(0, -1, 2, 2));
 155     TEST_INTERSECT(r, IntRect(-1, -1, 3, 3));
 156
 157     r.unite(IntRect(0, 0, 3, 3));
 158     r.unite(IntRect(10, 0, 3, 3));
 159     r.unite(IntRect(0, 10, 13, 3));
 160     TEST_NO_INTERSECT(r, IntRect());
 161     TEST_INTERSECT(r, IntRect(1, 1, 1, 1));
 162     TEST_INTERSECT(r, IntRect(0, 0, 2, 2));
 163     TEST_INTERSECT(r, IntRect(1, 0, 2, 2));
 164     TEST_INTERSECT(r, IntRect(1, 1, 2, 2));
 165     TEST_INTERSECT(r, IntRect(0, 1, 2, 2));
 166     TEST_INTERSECT(r, IntRect(0, 0, 3, 3));
 167     TEST_INTERSECT(r, IntRect(-1, -1, 2, 2));
 168     TEST_INTERSECT(r, IntRect(2, -1, 2, 2));
 169     TEST_INTERSECT(r, IntRect(2, 2, 2, 2));
 170     TEST_INTERSECT(r, IntRect(-1, 2, 2, 2));
 171
 172     TEST_INTERSECT(r, IntRect(11, 1, 1, 1));
 173     TEST_INTERSECT(r, IntRect(10, 0, 2, 2));
 174     TEST_INTERSECT(r, IntRect(11, 0, 2, 2));
 175     TEST_INTERSECT(r, IntRect(11, 1, 2, 2));
 176     TEST_INTERSECT(r, IntRect(10, 1, 2, 2));
 177     TEST_INTERSECT(r, IntRect(10, 0, 3, 3));
 178     TEST_INTERSECT(r, IntRect(9, -1, 2, 2));
 179     TEST_INTERSECT(r, IntRect(12, -1, 2, 2));
 180     TEST_INTERSECT(r, IntRect(12, 2, 2, 2));
 181     TEST_INTERSECT(r, IntRect(9, 2, 2, 2));
 182
 183     TEST_INTERSECT(r, IntRect(0, -1, 13, 5));
 184     TEST_INTERSECT(r, IntRect(1, -1, 11, 5));
 185     TEST_INTERSECT(r, IntRect(2, -1, 9, 5));
 186     TEST_INTERSECT(r, IntRect(2, -1, 8, 5));
 187     TEST_INTERSECT(r, IntRect(3, -1, 8, 5));
 188     TEST_NO_INTERSECT(r, IntRect(3, -1, 7, 5));
 189
 190     TEST_INTERSECT(r, IntRect(0, 1, 13, 1));
 191     TEST_INTERSECT(r, IntRect(1, 1, 11, 1));
 192     TEST_INTERSECT(r, IntRect(2, 1, 9, 1));
 193     TEST_INTERSECT(r, IntRect(2, 1, 8, 1));
 194     TEST_INTERSECT(r, IntRect(3, 1, 8, 1));
 195     TEST_NO_INTERSECT(r, IntRect(3, 1, 7, 1));
 196
 197     TEST_INTERSECT(r, IntRect(0, 0, 13, 13));
 198     TEST_INTERSECT(r, IntRect(0, 1, 13, 11));
 199     TEST_INTERSECT(r, IntRect(0, 2, 13, 9));
 200     TEST_INTERSECT(r, IntRect(0, 2, 13, 8));
 201     TEST_INTERSECT(r, IntRect(0, 3, 13, 8));
 202     TEST_NO_INTERSECT(r, IntRect(0, 3, 13, 7));
 203 }
 204
 205 TEST(RegionTest, ReadPastFullSpanVectorInIntersectsTest)
 206 {
 207     Region r;
 208
 209     // This region has enough spans to fill its allocated Vector exactly.
 210     r.unite(IntRect(400, 300, 1, 800));
 211     r.unite(IntRect(785, 585, 1, 1));
 212     r.unite(IntRect(787, 585, 1, 1));
 213     r.unite(IntRect(0, 587, 16, 162));
 214     r.unite(IntRect(26, 590, 300, 150));
 215     r.unite(IntRect(196, 750, 1, 1));
 216     r.unite(IntRect(0, 766, 1, 1));
 217     r.unite(IntRect(0, 782, 1, 1));
 218     r.unite(IntRect(745, 798, 1, 1));
 219     r.unite(IntRect(795, 882, 10, 585));
 220     r.unite(IntRect(100, 1499, 586, 1));
 221     r.unite(IntRect(100, 1500, 585, 784));
 222     // This query rect goes past the bottom of the Region, causing the
 223     // test to reach the last span and try go past it. It should not read
 224     // memory off the end of the span Vector.
 225     TEST_NO_INTERSECT(r, IntRect(0, 2184, 1, 150));
 226 }
 227
 228 #define TEST_NO_CONTAINS(a, b)     \
 229 {                                  \
 230     Region ar = a;                 \
 231     Region br = b;                 \
 232     EXPECT_FALSE(ar.contains(br)); \
 233 }
 234
 235 #define TEST_CONTAINS(a, b)       \
 236 {                                 \
 237     Region ar = a;                \
 238     Region br = b;                \
 239     EXPECT_TRUE(ar.contains(br)); \
 240 }
 241
 242 TEST(RegionTest, containsRegion)
 243 {
 244     TEST_CONTAINS(IntRect(), IntRect());
 245     TEST_NO_CONTAINS(IntRect(), IntRect(0, 0, 1, 1));
 246     TEST_NO_CONTAINS(IntRect(), IntRect(1, 1, 1, 1));
 247
 248     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(11, 10, 1, 1));
 249     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 11, 1, 1));
 250     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 10, 1, 1));
 251     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 9, 1, 1));
 252     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 9, 2, 2));
 253     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 9, 2, 2));
 254     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 10, 2, 2));
 255     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 10, 2, 2));
 256     TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 9, 3, 3));
 257
 258     Region hLines;
 259     for (int i = 10; i < 20; i += 2)
 260         hLines.unite(IntRect(i, 10, 1, 10));
 261
 262     TEST_CONTAINS(IntRect(10, 10, 9, 10), hLines);
 263     TEST_NO_CONTAINS(IntRect(10, 10, 9, 9), hLines);
 264     TEST_NO_CONTAINS(IntRect(10, 11, 9, 9), hLines);
 265     TEST_NO_CONTAINS(IntRect(10, 10, 8, 10), hLines);
 266     TEST_NO_CONTAINS(IntRect(11, 10, 8, 10), hLines);
 267
 268     Region vLines;
 269     for (int i = 10; i < 20; i += 2)
 270         vLines.unite(IntRect(10, i, 10, 1));
 271
 272     TEST_CONTAINS(IntRect(10, 10, 10, 9), vLines);
 273     TEST_NO_CONTAINS(IntRect(10, 10, 9, 9), vLines);
 274     TEST_NO_CONTAINS(IntRect(11, 10, 9, 9), vLines);
 275     TEST_NO_CONTAINS(IntRect(10, 10, 10, 8), vLines);
 276     TEST_NO_CONTAINS(IntRect(10, 11, 10, 8), vLines);
 277
 278     Region grid;
 279     for (int i = 10; i < 20; i += 2)
 280         for (int j = 10; j < 20; j += 2)
 281             grid.unite(IntRect(i, j, 1, 1));
 282
 283     TEST_CONTAINS(IntRect(10, 10, 9, 9), grid);
 284     TEST_NO_CONTAINS(IntRect(10, 10, 9, 8), grid);
 285     TEST_NO_CONTAINS(IntRect(10, 11, 9, 8), grid);
 286     TEST_NO_CONTAINS(IntRect(10, 10, 8, 9), grid);
 287     TEST_NO_CONTAINS(IntRect(11, 10, 8, 9), grid);
 288
 289     TEST_CONTAINS(hLines, hLines);
 290     TEST_CONTAINS(vLines, vLines);
 291     TEST_NO_CONTAINS(vLines, hLines);
 292     TEST_NO_CONTAINS(hLines, vLines);
 293     TEST_CONTAINS(grid, grid);
 294     TEST_CONTAINS(hLines, grid);
 295     TEST_CONTAINS(vLines, grid);
 296     TEST_NO_CONTAINS(grid, hLines);
 297     TEST_NO_CONTAINS(grid, vLines);
 298
 299     for (int i = 10; i < 20; i += 2)
 300         TEST_CONTAINS(hLines, IntRect(i, 10, 1, 10));
 301
 302     for (int i = 10; i < 20; i += 2)
 303         TEST_CONTAINS(vLines, IntRect(10, i, 10, 1));
 304
 305     for (int i = 10; i < 20; i += 2)
 306         for (int j = 10; j < 20; j += 2)
 307             TEST_CONTAINS(grid, IntRect(i, j, 1, 1));
 308
 309     Region container;
 310     container.unite(IntRect(0, 0, 40, 20));
 311     container.unite(IntRect(0, 20, 41, 20));
 312     TEST_CONTAINS(container, IntRect(5, 5, 30, 30));
 313
 314     container = Region();
 315     container.unite(IntRect(0, 0, 10, 10));
 316     container.unite(IntRect(0, 30, 10, 10));
 317     container.unite(IntRect(30, 30, 10, 10));
 318     container.unite(IntRect(30, 0, 10, 10));
 319     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
 320
 321     container = Region();
 322     container.unite(IntRect(0, 0, 10, 10));
 323     container.unite(IntRect(0, 30, 10, 10));
 324     container.unite(IntRect(30, 0, 10, 40));
 325     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
 326
 327     container = Region();
 328     container.unite(IntRect(30, 0, 10, 10));
 329     container.unite(IntRect(30, 30, 10, 10));
 330     container.unite(IntRect(0, 0, 10, 40));
 331     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
 332
 333     container = Region();
 334     container.unite(IntRect(0, 0, 10, 40));
 335     container.unite(IntRect(30, 0, 10, 40));
 336     TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30));
 337
 338     container = Region();
 339     container.unite(IntRect(0, 0, 40, 40));
 340     TEST_NO_CONTAINS(container, IntRect(10, -1, 20, 10));
 341
 342     container = Region();
 343     container.unite(IntRect(0, 0, 40, 40));
 344     TEST_NO_CONTAINS(container, IntRect(10, 31, 20, 10));
 345
 346     container = Region();
 347     container.unite(IntRect(0, 0, 40, 20));
 348     container.unite(IntRect(0, 20, 41, 20));
 349     TEST_NO_CONTAINS(container, IntRect(-1, 10, 10, 20));
 350
 351     container = Region();
 352     container.unite(IntRect(0, 0, 40, 20));
 353     container.unite(IntRect(0, 20, 41, 20));
 354     TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20));
 355
 356     container = Region();
 357     container.unite(IntRect(0, 0, 40, 40));
 358     container.subtract(IntRect(0, 20, 60, 0));
 359     TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20));
 360 }
 361
 362 TEST(RegionTest, unite)
 363 {
 364     Region r;
 365     Region r2;
 366
 367     // A rect uniting a contained rect does not change the region.
 368     r2 = r = IntRect(0, 0, 50, 50);
 369     r2.unite(IntRect(20, 20, 10, 10));
 370     EXPECT_EQ(r, r2);
 371
 372     // A rect uniting a containing rect gives back the containing rect.
 373     r = IntRect(0, 0, 50, 50);
 374     r.unite(IntRect(0, 0, 100, 100));
 375     EXPECT_EQ(Region(IntRect(0, 0, 100, 100)), r);
 376
 377     // A complex region uniting a contained rect does not change the region.
 378     r = IntRect(0, 0, 50, 50);
 379     r.unite(IntRect(100, 0, 50, 50));
 380     r2 = r;
 381     r2.unite(IntRect(20, 20, 10, 10));
 382     EXPECT_EQ(r, r2);
 383
 384     // A complex region uniting a containing rect gives back the containing rect.
 385     r = IntRect(0, 0, 50, 50);
 386     r.unite(IntRect(100, 0, 50, 50));
 387     r. unite(IntRect(0, 0, 500, 500));
 388     EXPECT_EQ(Region(IntRect(0, 0, 500, 500)), r);
 389 }
 390
 391 } // namespace blink