1/* 2 * Copyright 2011 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#include "include/core/SkPath.h" 9#include "include/core/SkRegion.h" 10#include "include/utils/SkRandom.h" 11#include "src/core/SkAutoMalloc.h" 12#include "tests/Test.h" 13 14static void Union(SkRegion* rgn, const SkIRect& rect) { 15 rgn->op(rect, SkRegion::kUnion_Op); 16} 17 18#define TEST_NO_INTERSECT(rgn, rect) REPORTER_ASSERT(reporter, !rgn.intersects(rect)) 19#define TEST_INTERSECT(rgn, rect) REPORTER_ASSERT(reporter, rgn.intersects(rect)) 20#define TEST_NO_CONTAINS(rgn, rect) REPORTER_ASSERT(reporter, !rgn.contains(rect)) 21 22// inspired by http://code.google.com/p/skia/issues/detail?id=958 23// 24static void test_fromchrome(skiatest::Reporter* reporter) { 25 SkRegion r; 26 Union(&r, SkIRect::MakeXYWH(0, 0, 1, 1)); 27 TEST_NO_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 0, 0)); 28 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 2, 2)); 29 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, 0, 2, 2)); 30 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 2, 2)); 31 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, -1, 2, 2)); 32 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 3, 3)); 33 34 Union(&r, SkIRect::MakeXYWH(0, 0, 3, 3)); 35 Union(&r, SkIRect::MakeXYWH(10, 0, 3, 3)); 36 Union(&r, SkIRect::MakeXYWH(0, 10, 13, 3)); 37 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 2, 2)); 38 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 2, 2)); 39 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 2, 2, 2)); 40 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, 2, 2, 2)); 41 42 TEST_INTERSECT(r, SkIRect::MakeXYWH(9, -1, 2, 2)); 43 TEST_INTERSECT(r, SkIRect::MakeXYWH(12, -1, 2, 2)); 44 TEST_INTERSECT(r, SkIRect::MakeXYWH(12, 2, 2, 2)); 45 TEST_INTERSECT(r, SkIRect::MakeXYWH(9, 2, 2, 2)); 46 47 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, -1, 13, 5)); 48 TEST_INTERSECT(r, SkIRect::MakeXYWH(1, -1, 11, 5)); 49 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 9, 5)); 50 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 8, 5)); 51 TEST_INTERSECT(r, SkIRect::MakeXYWH(3, -1, 8, 5)); 52 53 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 1, 13, 1)); 54 TEST_INTERSECT(r, SkIRect::MakeXYWH(1, 1, 11, 1)); 55 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 1, 9, 1)); 56 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 1, 8, 1)); 57 TEST_INTERSECT(r, SkIRect::MakeXYWH(3, 1, 8, 1)); 58 59 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 13, 13)); 60 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 1, 13, 11)); 61 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 2, 13, 9)); 62 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 2, 13, 8)); 63 64 65 // These test SkRegion::contains(Rect) and SkRegion::contains(Region) 66 67 SkRegion container; 68 Union(&container, SkIRect::MakeXYWH(0, 0, 40, 20)); 69 Union(&container, SkIRect::MakeXYWH(30, 20, 10, 20)); 70 TEST_NO_CONTAINS(container, SkIRect::MakeXYWH(0, 0, 10, 39)); 71 TEST_NO_CONTAINS(container, SkIRect::MakeXYWH(29, 0, 10, 39)); 72 73 { 74 SkRegion rgn; 75 Union(&rgn, SkIRect::MakeXYWH(0, 0, 10, 10)); 76 Union(&rgn, SkIRect::MakeLTRB(5, 10, 20, 20)); 77 TEST_INTERSECT(rgn, SkIRect::MakeXYWH(15, 0, 5, 11)); 78 } 79} 80 81static void test_empties(skiatest::Reporter* reporter) { 82 SkRegion valid(SkIRect::MakeWH(10, 10)); 83 SkRegion empty, empty2; 84 85 REPORTER_ASSERT(reporter, empty.isEmpty()); 86 REPORTER_ASSERT(reporter, !valid.isEmpty()); 87 88 // test intersects 89 REPORTER_ASSERT(reporter, !empty.intersects(empty2)); 90 REPORTER_ASSERT(reporter, !valid.intersects(empty)); 91 92 // test contains 93 REPORTER_ASSERT(reporter, !empty.contains(empty2)); 94 REPORTER_ASSERT(reporter, !valid.contains(empty)); 95 REPORTER_ASSERT(reporter, !empty.contains(valid)); 96 97 SkPath emptyPath; 98 emptyPath.moveTo(1, 5); 99 emptyPath.close(); 100 SkRegion openClip; 101 openClip.setRect({-16000, -16000, 16000, 16000}); 102 empty.setPath(emptyPath, openClip); // should not assert 103} 104 105enum { 106 W = 256, 107 H = 256 108}; 109 110static SkIRect randRect(SkRandom& rand) { 111 int x = rand.nextU() % W; 112 int y = rand.nextU() % H; 113 int w = rand.nextU() % W; 114 int h = rand.nextU() % H; 115 return SkIRect::MakeXYWH(x, y, w >> 1, h >> 1); 116} 117 118static void randRgn(SkRandom& rand, SkRegion* rgn, int n) { 119 rgn->setEmpty(); 120 for (int i = 0; i < n; ++i) { 121 rgn->op(randRect(rand), SkRegion::kUnion_Op); 122 } 123} 124 125static bool slow_contains(const SkRegion& outer, const SkRegion& inner) { 126 SkRegion tmp; 127 tmp.op(outer, inner, SkRegion::kUnion_Op); 128 return outer == tmp; 129} 130 131static bool slow_contains(const SkRegion& outer, const SkIRect& r) { 132 SkRegion tmp; 133 tmp.op(outer, SkRegion(r), SkRegion::kUnion_Op); 134 return outer == tmp; 135} 136 137static bool slow_intersects(const SkRegion& outer, const SkRegion& inner) { 138 SkRegion tmp; 139 return tmp.op(outer, inner, SkRegion::kIntersect_Op); 140} 141 142static void test_contains_iter(skiatest::Reporter* reporter, const SkRegion& rgn) { 143 SkRegion::Iterator iter(rgn); 144 while (!iter.done()) { 145 SkIRect r = iter.rect(); 146 REPORTER_ASSERT(reporter, rgn.contains(r)); 147 r.inset(-1, -1); 148 REPORTER_ASSERT(reporter, !rgn.contains(r)); 149 iter.next(); 150 } 151} 152 153static void contains_proc(skiatest::Reporter* reporter, 154 const SkRegion& a, const SkRegion& b) { 155 // test rgn 156 bool c0 = a.contains(b); 157 bool c1 = slow_contains(a, b); 158 REPORTER_ASSERT(reporter, c0 == c1); 159 160 // test rect 161 SkIRect r = a.getBounds(); 162 r.inset(r.width()/4, r.height()/4); 163 c0 = a.contains(r); 164 c1 = slow_contains(a, r); 165 REPORTER_ASSERT(reporter, c0 == c1); 166 167 test_contains_iter(reporter, a); 168 test_contains_iter(reporter, b); 169} 170 171static void test_intersects_iter(skiatest::Reporter* reporter, const SkRegion& rgn) { 172 SkRegion::Iterator iter(rgn); 173 while (!iter.done()) { 174 SkIRect r = iter.rect(); 175 REPORTER_ASSERT(reporter, rgn.intersects(r)); 176 r.inset(-1, -1); 177 REPORTER_ASSERT(reporter, rgn.intersects(r)); 178 iter.next(); 179 } 180} 181 182static void intersects_proc(skiatest::Reporter* reporter, 183 const SkRegion& a, const SkRegion& b) { 184 bool c0 = a.intersects(b); 185 bool c1 = slow_intersects(a, b); 186 REPORTER_ASSERT(reporter, c0 == c1); 187 188 test_intersects_iter(reporter, a); 189 test_intersects_iter(reporter, b); 190} 191 192static void test_proc(skiatest::Reporter* reporter, 193 void (*proc)(skiatest::Reporter*, 194 const SkRegion& a, const SkRegion&)) { 195 SkRandom rand; 196 for (int i = 0; i < 10000; ++i) { 197 SkRegion outer; 198 randRgn(rand, &outer, 8); 199 SkRegion inner; 200 randRgn(rand, &inner, 2); 201 proc(reporter, outer, inner); 202 } 203} 204 205static void rand_rect(SkIRect* rect, SkRandom& rand) { 206 int bits = 6; 207 int shift = 32 - bits; 208 rect->setLTRB(rand.nextU() >> shift, rand.nextU() >> shift, 209 rand.nextU() >> shift, rand.nextU() >> shift); 210 rect->sort(); 211} 212 213static bool test_rects(const SkIRect rect[], int count) { 214 SkRegion rgn0, rgn1; 215 216 for (int i = 0; i < count; i++) { 217 rgn0.op(rect[i], SkRegion::kUnion_Op); 218 } 219 rgn1.setRects(rect, count); 220 221 if (rgn0 != rgn1) { 222 SkDebugf("\n"); 223 for (int i = 0; i < count; i++) { 224 SkDebugf(" { %d, %d, %d, %d },\n", 225 rect[i].fLeft, rect[i].fTop, 226 rect[i].fRight, rect[i].fBottom); 227 } 228 SkDebugf("\n"); 229 return false; 230 } 231 return true; 232} 233 234DEF_TEST(Region, reporter) { 235 const SkIRect r2[] = { 236 { 0, 0, 1, 1 }, 237 { 2, 2, 3, 3 }, 238 }; 239 REPORTER_ASSERT(reporter, test_rects(r2, SK_ARRAY_COUNT(r2))); 240 241 const SkIRect rects[] = { 242 { 0, 0, 1, 2 }, 243 { 2, 1, 3, 3 }, 244 { 4, 0, 5, 1 }, 245 { 6, 0, 7, 4 }, 246 }; 247 REPORTER_ASSERT(reporter, test_rects(rects, SK_ARRAY_COUNT(rects))); 248 249 SkRandom rand; 250 for (int i = 0; i < 1000; i++) { 251 SkRegion rgn0, rgn1; 252 253 const int N = 8; 254 SkIRect rect[N]; 255 for (int j = 0; j < N; j++) { 256 rand_rect(&rect[j], rand); 257 } 258 REPORTER_ASSERT(reporter, test_rects(rect, N)); 259 } 260 261 test_proc(reporter, contains_proc); 262 test_proc(reporter, intersects_proc); 263 test_empties(reporter); 264 test_fromchrome(reporter); 265} 266 267// Test that writeToMemory reports the same number of bytes whether there was a 268// buffer to write to or not. 269static void test_write(const SkRegion& region, skiatest::Reporter* r) { 270 const size_t bytesNeeded = region.writeToMemory(nullptr); 271 SkAutoMalloc storage(bytesNeeded); 272 const size_t bytesWritten = region.writeToMemory(storage.get()); 273 REPORTER_ASSERT(r, bytesWritten == bytesNeeded); 274 275 // Also check that the bytes are meaningful. 276 SkRegion copy; 277 REPORTER_ASSERT(r, copy.readFromMemory(storage.get(), bytesNeeded)); 278 REPORTER_ASSERT(r, region == copy); 279} 280 281DEF_TEST(Region_writeToMemory, r) { 282 // Test an empty region. 283 SkRegion region; 284 REPORTER_ASSERT(r, region.isEmpty()); 285 test_write(region, r); 286 287 // Test a rectangular region 288 bool nonEmpty = region.setRect({0, 0, 50, 50}); 289 REPORTER_ASSERT(r, nonEmpty); 290 REPORTER_ASSERT(r, region.isRect()); 291 test_write(region, r); 292 293 // Test a complex region 294 nonEmpty = region.op({50, 50, 100, 100}, SkRegion::kUnion_Op); 295 REPORTER_ASSERT(r, nonEmpty); 296 REPORTER_ASSERT(r, region.isComplex()); 297 test_write(region, r); 298 299 SkRegion complexRegion; 300 Union(&complexRegion, SkIRect::MakeXYWH(0, 0, 1, 1)); 301 Union(&complexRegion, SkIRect::MakeXYWH(0, 0, 3, 3)); 302 Union(&complexRegion, SkIRect::MakeXYWH(10, 0, 3, 3)); 303 Union(&complexRegion, SkIRect::MakeXYWH(0, 10, 13, 3)); 304 test_write(complexRegion, r); 305 306 Union(&complexRegion, SkIRect::MakeXYWH(10, 20, 3, 3)); 307 Union(&complexRegion, SkIRect::MakeXYWH(0, 20, 3, 3)); 308 test_write(complexRegion, r); 309} 310 311DEF_TEST(Region_readFromMemory_bad, r) { 312 // These assume what our binary format is: conceivably we could change it 313 // and might need to remove or change some of these tests. 314 SkRegion region; 315 316 { 317 // invalid boundary rectangle 318 int32_t data[5] = {0, 4, 4, 8, 2}; 319 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 320 } 321 // Region Layout, Serialized Format: 322 // COUNT LEFT TOP RIGHT BOTTOM Y_SPAN_COUNT TOTAL_INTERVAL_COUNT 323 // Top ( Bottom Span_Interval_Count ( Left Right )* Sentinel )+ Sentinel 324 { 325 // Example of valid data 326 int32_t data[] = {9, 0, 0, 10, 10, 1, 2, 0, 10, 2, 0, 4, 6, 10, 327 2147483647, 2147483647}; 328 REPORTER_ASSERT(r, 0 != region.readFromMemory(data, sizeof(data))); 329 } 330 { 331 // Example of valid data with 4 intervals 332 int32_t data[] = {19, 0, 0, 30, 30, 3, 4, 0, 10, 2, 0, 10, 20, 30, 333 2147483647, 20, 0, 2147483647, 30, 2, 0, 10, 20, 30, 334 2147483647, 2147483647}; 335 REPORTER_ASSERT(r, 0 != region.readFromMemory(data, sizeof(data))); 336 } 337 { 338 // Short count 339 int32_t data[] = {8, 0, 0, 10, 10, 1, 2, 0, 10, 2, 0, 4, 6, 10, 340 2147483647, 2147483647}; 341 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 342 } 343 { 344 // bounds don't match 345 int32_t data[] = {9, 0, 0, 10, 11, 1, 2, 0, 10, 2, 0, 4, 6, 10, 346 2147483647, 2147483647}; 347 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 348 } 349 { 350 // bad yspan count 351 int32_t data[] = {9, 0, 0, 10, 10, 2, 2, 0, 10, 2, 0, 4, 6, 10, 352 2147483647, 2147483647}; 353 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 354 } 355 { 356 // bad int count 357 int32_t data[] = {9, 0, 0, 10, 10, 1, 3, 0, 10, 2, 0, 4, 6, 10, 358 2147483647, 2147483647}; 359 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 360 } 361 { 362 // bad final sentinal 363 int32_t data[] = {9, 0, 0, 10, 10, 1, 2, 0, 10, 2, 0, 4, 6, 10, 364 2147483647, -1}; 365 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 366 } 367 { 368 // bad row sentinal 369 int32_t data[] = {9, 0, 0, 10, 10, 1, 2, 0, 10, 2, 0, 4, 6, 10, 370 -1, 2147483647}; 371 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 372 } 373 { 374 // starts with empty yspan 375 int32_t data[] = {12, 0, 0, 10, 10, 2, 2, -5, 0, 0, 2147483647, 10, 376 2, 0, 4, 6, 10, 2147483647, 2147483647}; 377 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 378 } 379 { 380 // ends with empty yspan 381 int32_t data[] = {12, 0, 0, 10, 10, 2, 2, 0, 10, 2, 0, 4, 6, 10, 382 2147483647, 15, 0, 2147483647, 2147483647}; 383 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 384 } 385 { 386 // y intervals out of order 387 int32_t data[] = {19, 0, -20, 30, 10, 3, 4, 0, 10, 2, 0, 10, 20, 30, 388 2147483647, -20, 0, 2147483647, -10, 2, 0, 10, 20, 30, 389 2147483647, 2147483647}; 390 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 391 } 392 { 393 // x intervals out of order 394 int32_t data[] = {9, 0, 0, 10, 10, 1, 2, 0, 10, 2, 6, 10, 0, 4, 395 2147483647, 2147483647}; 396 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data))); 397 } 398} 399 400DEF_TEST(region_toobig, reporter) { 401 const int big = 1 << 30; 402 const SkIRect neg = SkIRect::MakeXYWH(-big, -big, 10, 10); 403 const SkIRect pos = SkIRect::MakeXYWH( big, big, 10, 10); 404 405 REPORTER_ASSERT(reporter, !neg.isEmpty()); 406 REPORTER_ASSERT(reporter, !pos.isEmpty()); 407 408 SkRegion negR(neg); 409 SkRegion posR(pos); 410 411 REPORTER_ASSERT(reporter, !negR.isEmpty()); 412 REPORTER_ASSERT(reporter, !posR.isEmpty()); 413 414 SkRegion rgn; 415 rgn.op(negR, posR, SkRegion::kUnion_Op); 416 417 // If we union those to rectangles, the resulting coordinates span more than int32_t, so 418 // we must mark the region as empty. 419 REPORTER_ASSERT(reporter, rgn.isEmpty()); 420} 421 422DEF_TEST(region_inverse_union_skbug_7491, reporter) { 423 SkPath path; 424 path.setFillType(SkPathFillType::kInverseWinding); 425 path.moveTo(10, 20); path.lineTo(10, 30); path.lineTo(10.1f, 10); path.close(); 426 427 SkRegion clip; 428 clip.op(SkIRect::MakeLTRB(10, 10, 15, 20), SkRegion::kUnion_Op); 429 clip.op(SkIRect::MakeLTRB(20, 10, 25, 20), SkRegion::kUnion_Op); 430 431 SkRegion rgn; 432 rgn.setPath(path, clip); 433 434 REPORTER_ASSERT(reporter, clip == rgn); 435} 436 437DEF_TEST(giant_path_region, reporter) { 438 const SkScalar big = 32767; 439 SkPath path; 440 path.moveTo(-big, 0); 441 path.quadTo(big, 0, big, big); 442 SkIRect ir = path.getBounds().round(); 443 SkRegion rgn; 444 rgn.setPath(path, SkRegion(ir)); 445} 446 447DEF_TEST(rrect_region_crbug_850350, reporter) { 448 SkMatrix m; 449 m.reset(); 450 m[1] = 0.753662348f; 451 m[3] = 1.40079998E+20f; 452 453 const SkPoint corners[] = { 454 { 2.65876e-19f, 0.0194088f }, 455 { 4896, 0.00114702f }, 456 { 0, 0 }, 457 { 0.00114702f, 0.00495333f }, 458 }; 459 SkRRect rrect; 460 rrect.setRectRadii({-8.72387e-31f, 1.29996e-38f, 4896, 1.125f}, corners); 461 462 SkPath path; 463 path.addRRect(rrect); 464 path.transform(m); 465 466 SkRegion rgn; 467 rgn.setPath(path, SkRegion{SkIRect{0, 0, 24, 24}}); 468} 469 470DEF_TEST(region_bug_chromium_873051, reporter) { 471 SkRegion region; 472 REPORTER_ASSERT(reporter, region.setRect({0, 0, 0x7FFFFFFE, 0x7FFFFFFE})); 473 REPORTER_ASSERT(reporter, !region.setRect({0, 0, 0x7FFFFFFE, 0x7FFFFFFF})); 474 REPORTER_ASSERT(reporter, !region.setRect({0, 0, 0x7FFFFFFF, 0x7FFFFFFE})); 475 REPORTER_ASSERT(reporter, !region.setRect({0, 0, 0x7FFFFFFF, 0x7FFFFFFF})); 476} 477 478DEF_TEST(region_empty_iter, reporter) { 479 SkRegion::Iterator emptyIter; 480 REPORTER_ASSERT(reporter, !emptyIter.rewind()); 481 REPORTER_ASSERT(reporter, emptyIter.done()); 482 auto eRect = emptyIter.rect(); 483 REPORTER_ASSERT(reporter, eRect.isEmpty()); 484 REPORTER_ASSERT(reporter, SkIRect::MakeEmpty() == eRect); 485 REPORTER_ASSERT(reporter, !emptyIter.rgn()); 486 487 SkRegion region; 488 SkRegion::Iterator resetIter; 489 resetIter.reset(region); 490 REPORTER_ASSERT(reporter, resetIter.rewind()); 491 REPORTER_ASSERT(reporter, resetIter.done()); 492 auto rRect = resetIter.rect(); 493 REPORTER_ASSERT(reporter, rRect.isEmpty()); 494 REPORTER_ASSERT(reporter, SkIRect::MakeEmpty() == rRect); 495 REPORTER_ASSERT(reporter, resetIter.rgn()); 496 REPORTER_ASSERT(reporter, resetIter.rgn()->isEmpty()); 497 498 SkRegion::Iterator iter(region); 499 REPORTER_ASSERT(reporter, iter.done()); 500 auto iRect = iter.rect(); 501 REPORTER_ASSERT(reporter, iRect.isEmpty()); 502 REPORTER_ASSERT(reporter, SkIRect::MakeEmpty() == iRect); 503 REPORTER_ASSERT(reporter, iter.rgn()); 504 REPORTER_ASSERT(reporter, iter.rgn()->isEmpty()); 505 506 SkRegion::Cliperator clipIter(region, {0, 0, 100, 100}); 507 REPORTER_ASSERT(reporter, clipIter.done()); 508 auto cRect = clipIter.rect(); 509 REPORTER_ASSERT(reporter, cRect.isEmpty()); 510 REPORTER_ASSERT(reporter, SkIRect::MakeEmpty() == cRect); 511 512 SkRegion::Spanerator spanIter(region, 0, 0, 100); 513 int left = 0, right = 0; 514 REPORTER_ASSERT(reporter, !spanIter.next(&left, &right)); 515 REPORTER_ASSERT(reporter, !left); 516 REPORTER_ASSERT(reporter, !right); 517} 518