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 "core/platform/graphics/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 395
