Home | History | Annotate | Download | only in tests 
      1 
      2 /*
      3  * Copyright 2011 Google Inc.
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 #include "Test.h"
      9 #if SK_SUPPORT_GPU
     10     #include "GrReducedClip.h"
     11 #endif
     12 #include "SkClipStack.h"
     13 #include "SkPath.h"
     14 #include "SkRandom.h"
     15 #include "SkRect.h"
     16 #include "SkRegion.h"
     17 
     18 
     19 static void test_assign_and_comparison(skiatest::Reporter* reporter) {
     20     SkClipStack s;
     21     bool doAA = false;
     22 
     23     REPORTER_ASSERT(reporter, 0 == s.getSaveCount());
     24 
     25     // Build up a clip stack with a path, an empty clip, and a rect.
     26     s.save();
     27     REPORTER_ASSERT(reporter, 1 == s.getSaveCount());
     28 
     29     SkPath p;
     30     p.moveTo(5, 6);
     31     p.lineTo(7, 8);
     32     p.lineTo(5, 9);
     33     p.close();
     34     s.clipDevPath(p, SkRegion::kIntersect_Op, doAA);
     35 
     36     s.save();
     37     REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
     38 
     39     SkRect r = SkRect::MakeLTRB(1, 2, 3, 4);
     40     s.clipDevRect(r, SkRegion::kIntersect_Op, doAA);
     41     r = SkRect::MakeLTRB(10, 11, 12, 13);
     42     s.clipDevRect(r, SkRegion::kIntersect_Op, doAA);
     43 
     44     s.save();
     45     REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
     46 
     47     r = SkRect::MakeLTRB(14, 15, 16, 17);
     48     s.clipDevRect(r, SkRegion::kUnion_Op, doAA);
     49 
     50     // Test that assignment works.
     51     SkClipStack copy = s;
     52     REPORTER_ASSERT(reporter, s == copy);
     53 
     54     // Test that different save levels triggers not equal.
     55     s.restore();
     56     REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
     57     REPORTER_ASSERT(reporter, s != copy);
     58 
     59     // Test that an equal, but not copied version is equal.
     60     s.save();
     61     REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
     62 
     63     r = SkRect::MakeLTRB(14, 15, 16, 17);
     64     s.clipDevRect(r, SkRegion::kUnion_Op, doAA);
     65     REPORTER_ASSERT(reporter, s == copy);
     66 
     67     // Test that a different op on one level triggers not equal.
     68     s.restore();
     69     REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
     70     s.save();
     71     REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
     72 
     73     r = SkRect::MakeLTRB(14, 15, 16, 17);
     74     s.clipDevRect(r, SkRegion::kIntersect_Op, doAA);
     75     REPORTER_ASSERT(reporter, s != copy);
     76 
     77     // Test that different state (clip type) triggers not equal.
     78     // NO LONGER VALID: if a path contains only a rect, we turn
     79     // it into a bare rect for performance reasons (working
     80     // around Chromium/JavaScript bad pattern).
     81 /*
     82     s.restore();
     83     s.save();
     84     SkPath rp;
     85     rp.addRect(r);
     86     s.clipDevPath(rp, SkRegion::kUnion_Op, doAA);
     87     REPORTER_ASSERT(reporter, s != copy);
     88 */
     89 
     90     // Test that different rects triggers not equal.
     91     s.restore();
     92     REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
     93     s.save();
     94     REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
     95 
     96     r = SkRect::MakeLTRB(24, 25, 26, 27);
     97     s.clipDevRect(r, SkRegion::kUnion_Op, doAA);
     98     REPORTER_ASSERT(reporter, s != copy);
     99 
    100     // Sanity check
    101     s.restore();
    102     REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
    103 
    104     copy.restore();
    105     REPORTER_ASSERT(reporter, 2 == copy.getSaveCount());
    106     REPORTER_ASSERT(reporter, s == copy);
    107     s.restore();
    108     REPORTER_ASSERT(reporter, 1 == s.getSaveCount());
    109     copy.restore();
    110     REPORTER_ASSERT(reporter, 1 == copy.getSaveCount());
    111     REPORTER_ASSERT(reporter, s == copy);
    112 
    113     // Test that different paths triggers not equal.
    114     s.restore();
    115     REPORTER_ASSERT(reporter, 0 == s.getSaveCount());
    116     s.save();
    117     REPORTER_ASSERT(reporter, 1 == s.getSaveCount());
    118 
    119     p.addRect(r);
    120     s.clipDevPath(p, SkRegion::kIntersect_Op, doAA);
    121     REPORTER_ASSERT(reporter, s != copy);
    122 }
    123 
    124 static void assert_count(skiatest::Reporter* reporter, const SkClipStack& stack,
    125                          int count) {
    126     SkClipStack::B2TIter iter(stack);
    127     int counter = 0;
    128     while (iter.next()) {
    129         counter += 1;
    130     }
    131     REPORTER_ASSERT(reporter, count == counter);
    132 }
    133 
    134 // Exercise the SkClipStack's bottom to top and bidirectional iterators
    135 // (including the skipToTopmost functionality)
    136 static void test_iterators(skiatest::Reporter* reporter) {
    137     SkClipStack stack;
    138 
    139     static const SkRect gRects[] = {
    140         { 0,   0,  40,  40 },
    141         { 60,  0, 100,  40 },
    142         { 0,  60,  40, 100 },
    143         { 60, 60, 100, 100 }
    144     };
    145 
    146     for (size_t i = 0; i < SK_ARRAY_COUNT(gRects); i++) {
    147         // the union op will prevent these from being fused together
    148         stack.clipDevRect(gRects[i], SkRegion::kUnion_Op, false);
    149     }
    150 
    151     assert_count(reporter, stack, 4);
    152 
    153     // bottom to top iteration
    154     {
    155         const SkClipStack::Element* element = NULL;
    156 
    157         SkClipStack::B2TIter iter(stack);
    158         int i;
    159 
    160         for (i = 0, element = iter.next(); element; ++i, element = iter.next()) {
    161             REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
    162             REPORTER_ASSERT(reporter, element->getRect() == gRects[i]);
    163         }
    164 
    165         SkASSERT(i == 4);
    166     }
    167 
    168     // top to bottom iteration
    169     {
    170         const SkClipStack::Element* element = NULL;
    171 
    172         SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
    173         int i;
    174 
    175         for (i = 3, element = iter.prev(); element; --i, element = iter.prev()) {
    176             REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
    177             REPORTER_ASSERT(reporter, element->getRect() == gRects[i]);
    178         }
    179 
    180         SkASSERT(i == -1);
    181     }
    182 
    183     // skipToTopmost
    184     {
    185         const SkClipStack::Element* element = NULL;
    186 
    187         SkClipStack::Iter iter(stack, SkClipStack::Iter::kBottom_IterStart);
    188 
    189         element = iter.skipToTopmost(SkRegion::kUnion_Op);
    190         REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
    191         REPORTER_ASSERT(reporter, element->getRect() == gRects[3]);
    192     }
    193 }
    194 
    195 // Exercise the SkClipStack's getConservativeBounds computation
    196 static void test_bounds(skiatest::Reporter* reporter, bool useRects) {
    197 
    198     static const int gNumCases = 20;
    199     static const SkRect gAnswerRectsBW[gNumCases] = {
    200         // A op B
    201         { 40, 40, 50, 50 },
    202         { 10, 10, 50, 50 },
    203         { 10, 10, 80, 80 },
    204         { 10, 10, 80, 80 },
    205         { 40, 40, 80, 80 },
    206 
    207         // invA op B
    208         { 40, 40, 80, 80 },
    209         { 0, 0, 100, 100 },
    210         { 0, 0, 100, 100 },
    211         { 0, 0, 100, 100 },
    212         { 40, 40, 50, 50 },
    213 
    214         // A op invB
    215         { 10, 10, 50, 50 },
    216         { 40, 40, 50, 50 },
    217         { 0, 0, 100, 100 },
    218         { 0, 0, 100, 100 },
    219         { 0, 0, 100, 100 },
    220 
    221         // invA op invB
    222         { 0, 0, 100, 100 },
    223         { 40, 40, 80, 80 },
    224         { 0, 0, 100, 100 },
    225         { 10, 10, 80, 80 },
    226         { 10, 10, 50, 50 },
    227     };
    228 
    229     static const SkRegion::Op gOps[] = {
    230         SkRegion::kIntersect_Op,
    231         SkRegion::kDifference_Op,
    232         SkRegion::kUnion_Op,
    233         SkRegion::kXOR_Op,
    234         SkRegion::kReverseDifference_Op
    235     };
    236 
    237     SkRect rectA, rectB;
    238 
    239     rectA.iset(10, 10, 50, 50);
    240     rectB.iset(40, 40, 80, 80);
    241 
    242     SkPath clipA, clipB;
    243 
    244     clipA.addRoundRect(rectA, SkIntToScalar(5), SkIntToScalar(5));
    245     clipB.addRoundRect(rectB, SkIntToScalar(5), SkIntToScalar(5));
    246 
    247     SkClipStack stack;
    248     SkRect devClipBound;
    249     bool isIntersectionOfRects = false;
    250 
    251     int testCase = 0;
    252     int numBitTests = useRects ? 1 : 4;
    253     for (int invBits = 0; invBits < numBitTests; ++invBits) {
    254         for (size_t op = 0; op < SK_ARRAY_COUNT(gOps); ++op) {
    255 
    256             stack.save();
    257             bool doInvA = SkToBool(invBits & 1);
    258             bool doInvB = SkToBool(invBits & 2);
    259 
    260             clipA.setFillType(doInvA ? SkPath::kInverseEvenOdd_FillType :
    261                                        SkPath::kEvenOdd_FillType);
    262             clipB.setFillType(doInvB ? SkPath::kInverseEvenOdd_FillType :
    263                                        SkPath::kEvenOdd_FillType);
    264 
    265             if (useRects) {
    266                 stack.clipDevRect(rectA, SkRegion::kIntersect_Op, false);
    267                 stack.clipDevRect(rectB, gOps[op], false);
    268             } else {
    269                 stack.clipDevPath(clipA, SkRegion::kIntersect_Op, false);
    270                 stack.clipDevPath(clipB, gOps[op], false);
    271             }
    272 
    273             REPORTER_ASSERT(reporter, !stack.isWideOpen());
    274 
    275             stack.getConservativeBounds(0, 0, 100, 100, &devClipBound,
    276                                         &isIntersectionOfRects);
    277 
    278             if (useRects) {
    279                 REPORTER_ASSERT(reporter, isIntersectionOfRects ==
    280                         (gOps[op] == SkRegion::kIntersect_Op));
    281             } else {
    282                 REPORTER_ASSERT(reporter, !isIntersectionOfRects);
    283             }
    284 
    285             SkASSERT(testCase < gNumCases);
    286             REPORTER_ASSERT(reporter, devClipBound == gAnswerRectsBW[testCase]);
    287             ++testCase;
    288 
    289             stack.restore();
    290         }
    291     }
    292 }
    293 
    294 // Test out 'isWideOpen' entry point
    295 static void test_isWideOpen(skiatest::Reporter* reporter) {
    296 
    297     SkRect rectA, rectB;
    298 
    299     rectA.iset(10, 10, 40, 40);
    300     rectB.iset(50, 50, 80, 80);
    301 
    302     // Stack should initially be wide open
    303     {
    304         SkClipStack stack;
    305 
    306         REPORTER_ASSERT(reporter, stack.isWideOpen());
    307     }
    308 
    309     // Test out case where the user specifies a union that includes everything
    310     {
    311         SkClipStack stack;
    312 
    313         SkPath clipA, clipB;
    314 
    315         clipA.addRoundRect(rectA, SkIntToScalar(5), SkIntToScalar(5));
    316         clipA.setFillType(SkPath::kInverseEvenOdd_FillType);
    317 
    318         clipB.addRoundRect(rectB, SkIntToScalar(5), SkIntToScalar(5));
    319         clipB.setFillType(SkPath::kInverseEvenOdd_FillType);
    320 
    321         stack.clipDevPath(clipA, SkRegion::kReplace_Op, false);
    322         stack.clipDevPath(clipB, SkRegion::kUnion_Op, false);
    323 
    324         REPORTER_ASSERT(reporter, stack.isWideOpen());
    325     }
    326 
    327     // Test out union w/ a wide open clip
    328     {
    329         SkClipStack stack;
    330 
    331         stack.clipDevRect(rectA, SkRegion::kUnion_Op, false);
    332 
    333         REPORTER_ASSERT(reporter, stack.isWideOpen());
    334     }
    335 
    336     // Test out empty difference from a wide open clip
    337     {
    338         SkClipStack stack;
    339 
    340         SkRect emptyRect;
    341         emptyRect.setEmpty();
    342 
    343         stack.clipDevRect(emptyRect, SkRegion::kDifference_Op, false);
    344 
    345         REPORTER_ASSERT(reporter, stack.isWideOpen());
    346     }
    347 
    348     // Test out return to wide open
    349     {
    350         SkClipStack stack;
    351 
    352         stack.save();
    353 
    354         stack.clipDevRect(rectA, SkRegion::kReplace_Op, false);
    355 
    356         REPORTER_ASSERT(reporter, !stack.isWideOpen());
    357 
    358         stack.restore();
    359 
    360         REPORTER_ASSERT(reporter, stack.isWideOpen());
    361     }
    362 }
    363 
    364 static int count(const SkClipStack& stack) {
    365 
    366     SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
    367 
    368     const SkClipStack::Element* element = NULL;
    369     int count = 0;
    370 
    371     for (element = iter.prev(); element; element = iter.prev(), ++count) {
    372         ;
    373     }
    374 
    375     return count;
    376 }
    377 
    378 static void test_rect_inverse_fill(skiatest::Reporter* reporter) {
    379     // non-intersecting rectangles
    380     SkRect rect  = SkRect::MakeLTRB(0, 0, 10, 10);
    381 
    382     SkPath path;
    383     path.addRect(rect);
    384     path.toggleInverseFillType();
    385     SkClipStack stack;
    386     stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    387 
    388     SkRect bounds;
    389     SkClipStack::BoundsType boundsType;
    390     stack.getBounds(&bounds, &boundsType);
    391     REPORTER_ASSERT(reporter, SkClipStack::kInsideOut_BoundsType == boundsType);
    392     REPORTER_ASSERT(reporter, bounds == rect);
    393 }
    394 
    395 static void test_rect_replace(skiatest::Reporter* reporter) {
    396     SkRect rect = SkRect::MakeWH(100, 100);
    397     SkRect rect2 = SkRect::MakeXYWH(50, 50, 100, 100);
    398 
    399     SkRect bound;
    400     SkClipStack::BoundsType type;
    401     bool isIntersectionOfRects;
    402 
    403     // Adding a new rect with the replace operator should not increase
    404     // the stack depth. BW replacing BW.
    405     {
    406         SkClipStack stack;
    407         REPORTER_ASSERT(reporter, 0 == count(stack));
    408         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    409         REPORTER_ASSERT(reporter, 1 == count(stack));
    410         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    411         REPORTER_ASSERT(reporter, 1 == count(stack));
    412     }
    413 
    414     // Adding a new rect with the replace operator should not increase
    415     // the stack depth. AA replacing AA.
    416     {
    417         SkClipStack stack;
    418         REPORTER_ASSERT(reporter, 0 == count(stack));
    419         stack.clipDevRect(rect, SkRegion::kReplace_Op, true);
    420         REPORTER_ASSERT(reporter, 1 == count(stack));
    421         stack.clipDevRect(rect, SkRegion::kReplace_Op, true);
    422         REPORTER_ASSERT(reporter, 1 == count(stack));
    423     }
    424 
    425     // Adding a new rect with the replace operator should not increase
    426     // the stack depth. BW replacing AA replacing BW.
    427     {
    428         SkClipStack stack;
    429         REPORTER_ASSERT(reporter, 0 == count(stack));
    430         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    431         REPORTER_ASSERT(reporter, 1 == count(stack));
    432         stack.clipDevRect(rect, SkRegion::kReplace_Op, true);
    433         REPORTER_ASSERT(reporter, 1 == count(stack));
    434         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    435         REPORTER_ASSERT(reporter, 1 == count(stack));
    436     }
    437 
    438     // Make sure replace clip rects don't collapse too much.
    439     {
    440         SkClipStack stack;
    441         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    442         stack.clipDevRect(rect2, SkRegion::kIntersect_Op, false);
    443         REPORTER_ASSERT(reporter, 1 == count(stack));
    444 
    445         stack.save();
    446         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    447         REPORTER_ASSERT(reporter, 2 == count(stack));
    448         stack.getBounds(&bound, &type, &isIntersectionOfRects);
    449         REPORTER_ASSERT(reporter, bound == rect);
    450         stack.restore();
    451         REPORTER_ASSERT(reporter, 1 == count(stack));
    452 
    453         stack.save();
    454         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    455         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    456         REPORTER_ASSERT(reporter, 2 == count(stack));
    457         stack.restore();
    458         REPORTER_ASSERT(reporter, 1 == count(stack));
    459 
    460         stack.save();
    461         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    462         stack.clipDevRect(rect2, SkRegion::kIntersect_Op, false);
    463         stack.clipDevRect(rect, SkRegion::kReplace_Op, false);
    464         REPORTER_ASSERT(reporter, 2 == count(stack));
    465         stack.restore();
    466         REPORTER_ASSERT(reporter, 1 == count(stack));
    467     }
    468 }
    469 
    470 // Simplified path-based version of test_rect_replace.
    471 static void test_path_replace(skiatest::Reporter* reporter) {
    472     SkRect rect = SkRect::MakeWH(100, 100);
    473     SkPath path;
    474     path.addCircle(50, 50, 50);
    475 
    476     // Replace operation doesn't grow the stack.
    477     {
    478         SkClipStack stack;
    479         REPORTER_ASSERT(reporter, 0 == count(stack));
    480         stack.clipDevPath(path, SkRegion::kReplace_Op, false);
    481         REPORTER_ASSERT(reporter, 1 == count(stack));
    482         stack.clipDevPath(path, SkRegion::kReplace_Op, false);
    483         REPORTER_ASSERT(reporter, 1 == count(stack));
    484     }
    485 
    486     // Replacing rect with path.
    487     {
    488         SkClipStack stack;
    489         stack.clipDevRect(rect, SkRegion::kReplace_Op, true);
    490         REPORTER_ASSERT(reporter, 1 == count(stack));
    491         stack.clipDevPath(path, SkRegion::kReplace_Op, true);
    492         REPORTER_ASSERT(reporter, 1 == count(stack));
    493     }
    494 }
    495 
    496 // Test out SkClipStack's merging of rect clips. In particular exercise
    497 // merging of aa vs. bw rects.
    498 static void test_rect_merging(skiatest::Reporter* reporter) {
    499 
    500     SkRect overlapLeft  = SkRect::MakeLTRB(10, 10, 50, 50);
    501     SkRect overlapRight = SkRect::MakeLTRB(40, 40, 80, 80);
    502 
    503     SkRect nestedParent = SkRect::MakeLTRB(10, 10, 90, 90);
    504     SkRect nestedChild  = SkRect::MakeLTRB(40, 40, 60, 60);
    505 
    506     SkRect bound;
    507     SkClipStack::BoundsType type;
    508     bool isIntersectionOfRects;
    509 
    510     // all bw overlapping - should merge
    511     {
    512         SkClipStack stack;
    513 
    514         stack.clipDevRect(overlapLeft, SkRegion::kReplace_Op, false);
    515 
    516         stack.clipDevRect(overlapRight, SkRegion::kIntersect_Op, false);
    517 
    518         REPORTER_ASSERT(reporter, 1 == count(stack));
    519 
    520         stack.getBounds(&bound, &type, &isIntersectionOfRects);
    521 
    522         REPORTER_ASSERT(reporter, isIntersectionOfRects);
    523     }
    524 
    525     // all aa overlapping - should merge
    526     {
    527         SkClipStack stack;
    528 
    529         stack.clipDevRect(overlapLeft, SkRegion::kReplace_Op, true);
    530 
    531         stack.clipDevRect(overlapRight, SkRegion::kIntersect_Op, true);
    532 
    533         REPORTER_ASSERT(reporter, 1 == count(stack));
    534 
    535         stack.getBounds(&bound, &type, &isIntersectionOfRects);
    536 
    537         REPORTER_ASSERT(reporter, isIntersectionOfRects);
    538     }
    539 
    540     // mixed overlapping - should _not_ merge
    541     {
    542         SkClipStack stack;
    543 
    544         stack.clipDevRect(overlapLeft, SkRegion::kReplace_Op, true);
    545 
    546         stack.clipDevRect(overlapRight, SkRegion::kIntersect_Op, false);
    547 
    548         REPORTER_ASSERT(reporter, 2 == count(stack));
    549 
    550         stack.getBounds(&bound, &type, &isIntersectionOfRects);
    551 
    552         REPORTER_ASSERT(reporter, !isIntersectionOfRects);
    553     }
    554 
    555     // mixed nested (bw inside aa) - should merge
    556     {
    557         SkClipStack stack;
    558 
    559         stack.clipDevRect(nestedParent, SkRegion::kReplace_Op, true);
    560 
    561         stack.clipDevRect(nestedChild, SkRegion::kIntersect_Op, false);
    562 
    563         REPORTER_ASSERT(reporter, 1 == count(stack));
    564 
    565         stack.getBounds(&bound, &type, &isIntersectionOfRects);
    566 
    567         REPORTER_ASSERT(reporter, isIntersectionOfRects);
    568     }
    569 
    570     // mixed nested (aa inside bw) - should merge
    571     {
    572         SkClipStack stack;
    573 
    574         stack.clipDevRect(nestedParent, SkRegion::kReplace_Op, false);
    575 
    576         stack.clipDevRect(nestedChild, SkRegion::kIntersect_Op, true);
    577 
    578         REPORTER_ASSERT(reporter, 1 == count(stack));
    579 
    580         stack.getBounds(&bound, &type, &isIntersectionOfRects);
    581 
    582         REPORTER_ASSERT(reporter, isIntersectionOfRects);
    583     }
    584 
    585     // reverse nested (aa inside bw) - should _not_ merge
    586     {
    587         SkClipStack stack;
    588 
    589         stack.clipDevRect(nestedChild, SkRegion::kReplace_Op, false);
    590 
    591         stack.clipDevRect(nestedParent, SkRegion::kIntersect_Op, true);
    592 
    593         REPORTER_ASSERT(reporter, 2 == count(stack));
    594 
    595         stack.getBounds(&bound, &type, &isIntersectionOfRects);
    596 
    597         REPORTER_ASSERT(reporter, !isIntersectionOfRects);
    598     }
    599 }
    600 
    601 static void test_quickContains(skiatest::Reporter* reporter) {
    602     SkRect testRect = SkRect::MakeLTRB(10, 10, 40, 40);
    603     SkRect insideRect = SkRect::MakeLTRB(20, 20, 30, 30);
    604     SkRect intersectingRect = SkRect::MakeLTRB(25, 25, 50, 50);
    605     SkRect outsideRect = SkRect::MakeLTRB(0, 0, 50, 50);
    606     SkRect nonIntersectingRect = SkRect::MakeLTRB(100, 100, 110, 110);
    607 
    608     SkPath insideCircle;
    609     insideCircle.addCircle(25, 25, 5);
    610     SkPath intersectingCircle;
    611     intersectingCircle.addCircle(25, 40, 10);
    612     SkPath outsideCircle;
    613     outsideCircle.addCircle(25, 25, 50);
    614     SkPath nonIntersectingCircle;
    615     nonIntersectingCircle.addCircle(100, 100, 5);
    616 
    617     {
    618         SkClipStack stack;
    619         stack.clipDevRect(outsideRect, SkRegion::kDifference_Op, false);
    620         // return false because quickContains currently does not care for kDifference_Op
    621         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    622     }
    623 
    624     // Replace Op tests
    625     {
    626         SkClipStack stack;
    627         stack.clipDevRect(outsideRect, SkRegion::kReplace_Op, false);
    628         REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
    629     }
    630 
    631     {
    632         SkClipStack stack;
    633         stack.clipDevRect(insideRect, SkRegion::kIntersect_Op, false);
    634         stack.save(); // To prevent in-place substitution by replace OP
    635         stack.clipDevRect(outsideRect, SkRegion::kReplace_Op, false);
    636         REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
    637         stack.restore();
    638     }
    639 
    640     {
    641         SkClipStack stack;
    642         stack.clipDevRect(outsideRect, SkRegion::kIntersect_Op, false);
    643         stack.save(); // To prevent in-place substitution by replace OP
    644         stack.clipDevRect(insideRect, SkRegion::kReplace_Op, false);
    645         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    646         stack.restore();
    647     }
    648 
    649     // Verify proper traversal of multi-element clip
    650     {
    651         SkClipStack stack;
    652         stack.clipDevRect(insideRect, SkRegion::kIntersect_Op, false);
    653         // Use a path for second clip to prevent in-place intersection
    654         stack.clipDevPath(outsideCircle, SkRegion::kIntersect_Op, false);
    655         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    656     }
    657 
    658     // Intersect Op tests with rectangles
    659     {
    660         SkClipStack stack;
    661         stack.clipDevRect(outsideRect, SkRegion::kIntersect_Op, false);
    662         REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
    663     }
    664 
    665     {
    666         SkClipStack stack;
    667         stack.clipDevRect(insideRect, SkRegion::kIntersect_Op, false);
    668         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    669     }
    670 
    671     {
    672         SkClipStack stack;
    673         stack.clipDevRect(intersectingRect, SkRegion::kIntersect_Op, false);
    674         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    675     }
    676 
    677     {
    678         SkClipStack stack;
    679         stack.clipDevRect(nonIntersectingRect, SkRegion::kIntersect_Op, false);
    680         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    681     }
    682 
    683     // Intersect Op tests with circle paths
    684     {
    685         SkClipStack stack;
    686         stack.clipDevPath(outsideCircle, SkRegion::kIntersect_Op, false);
    687         REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
    688     }
    689 
    690     {
    691         SkClipStack stack;
    692         stack.clipDevPath(insideCircle, SkRegion::kIntersect_Op, false);
    693         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    694     }
    695 
    696     {
    697         SkClipStack stack;
    698         stack.clipDevPath(intersectingCircle, SkRegion::kIntersect_Op, false);
    699         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    700     }
    701 
    702     {
    703         SkClipStack stack;
    704         stack.clipDevPath(nonIntersectingCircle, SkRegion::kIntersect_Op, false);
    705         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    706     }
    707 
    708     // Intersect Op tests with inverse filled rectangles
    709     {
    710         SkClipStack stack;
    711         SkPath path;
    712         path.addRect(outsideRect);
    713         path.toggleInverseFillType();
    714         stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    715         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    716     }
    717 
    718     {
    719         SkClipStack stack;
    720         SkPath path;
    721         path.addRect(insideRect);
    722         path.toggleInverseFillType();
    723         stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    724         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    725     }
    726 
    727     {
    728         SkClipStack stack;
    729         SkPath path;
    730         path.addRect(intersectingRect);
    731         path.toggleInverseFillType();
    732         stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    733         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    734     }
    735 
    736     {
    737         SkClipStack stack;
    738         SkPath path;
    739         path.addRect(nonIntersectingRect);
    740         path.toggleInverseFillType();
    741         stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    742         REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
    743     }
    744 
    745     // Intersect Op tests with inverse filled circles
    746     {
    747         SkClipStack stack;
    748         SkPath path = outsideCircle;
    749         path.toggleInverseFillType();
    750         stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    751         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    752     }
    753 
    754     {
    755         SkClipStack stack;
    756         SkPath path = insideCircle;
    757         path.toggleInverseFillType();
    758         stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    759         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    760     }
    761 
    762     {
    763         SkClipStack stack;
    764         SkPath path = intersectingCircle;
    765         path.toggleInverseFillType();
    766         stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    767         REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
    768     }
    769 
    770     {
    771         SkClipStack stack;
    772         SkPath path = nonIntersectingCircle;
    773         path.toggleInverseFillType();
    774         stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
    775         REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
    776     }
    777 }
    778 
    779 ///////////////////////////////////////////////////////////////////////////////////////////////////
    780 
    781 #if SK_SUPPORT_GPU
    782 // Functions that add a shape to the clip stack. The shape is computed from a rectangle.
    783 // AA is always disabled since the clip stack reducer can cause changes in aa rasterization of the
    784 // stack. A fractional edge repeated in different elements may be rasterized fewer times using the
    785 // reduced stack.
    786 typedef void (*AddElementFunc) (const SkRect& rect,
    787                                 bool invert,
    788                                 SkRegion::Op op,
    789                                 SkClipStack* stack);
    790 
    791 static void add_round_rect(const SkRect& rect, bool invert, SkRegion::Op op, SkClipStack* stack) {
    792     SkPath path;
    793     SkScalar rx = rect.width() / 10;
    794     SkScalar ry = rect.height() / 20;
    795     path.addRoundRect(rect, rx, ry);
    796     if (invert) {
    797         path.setFillType(SkPath::kInverseWinding_FillType);
    798     }
    799     stack->clipDevPath(path, op, false);
    800 };
    801 
    802 static void add_rect(const SkRect& rect, bool invert, SkRegion::Op op, SkClipStack* stack) {
    803     if (invert) {
    804         SkPath path;
    805         path.addRect(rect);
    806         path.setFillType(SkPath::kInverseWinding_FillType);
    807         stack->clipDevPath(path, op, false);
    808     } else {
    809         stack->clipDevRect(rect, op, false);
    810     }
    811 };
    812 
    813 static void add_oval(const SkRect& rect, bool invert, SkRegion::Op op, SkClipStack* stack) {
    814     SkPath path;
    815     path.addOval(rect);
    816     if (invert) {
    817         path.setFillType(SkPath::kInverseWinding_FillType);
    818     }
    819     stack->clipDevPath(path, op, false);
    820 };
    821 
    822 static void add_elem_to_stack(const SkClipStack::Element& element, SkClipStack* stack) {
    823     switch (element.getType()) {
    824         case SkClipStack::Element::kRect_Type:
    825             stack->clipDevRect(element.getRect(), element.getOp(), element.isAA());
    826             break;
    827         case SkClipStack::Element::kPath_Type:
    828             stack->clipDevPath(element.getPath(), element.getOp(), element.isAA());
    829             break;
    830         case SkClipStack::Element::kEmpty_Type:
    831             SkDEBUGFAIL("Why did the reducer produce an explicit empty.");
    832             stack->clipEmpty();
    833             break;
    834     }
    835 }
    836 
    837 static void add_elem_to_region(const SkClipStack::Element& element,
    838                                const SkIRect& bounds,
    839                                SkRegion* region) {
    840     SkRegion elemRegion;
    841     SkRegion boundsRgn(bounds);
    842 
    843     switch (element.getType()) {
    844         case SkClipStack::Element::kRect_Type: {
    845             SkPath path;
    846             path.addRect(element.getRect());
    847             elemRegion.setPath(path, boundsRgn);
    848             break;
    849         }
    850         case SkClipStack::Element::kPath_Type:
    851             elemRegion.setPath(element.getPath(), boundsRgn);
    852             break;
    853         case SkClipStack::Element::kEmpty_Type:
    854             //
    855             region->setEmpty();
    856             return;
    857     }
    858     region->op(elemRegion, element.getOp());
    859 }
    860 
    861 // This can assist with debugging the clip stack reduction code when the test below fails.
    862 static inline void print_clip(const SkClipStack::Element& element) {
    863     static const char* kOpStrs[] = {
    864         "DF",
    865         "IS",
    866         "UN",
    867         "XR",
    868         "RD",
    869         "RP",
    870     };
    871     if (SkClipStack::Element::kEmpty_Type != element.getType()) {
    872         const SkRect& bounds = element.getBounds();
    873         bool isRect = SkClipStack::Element::kRect_Type == element.getType();
    874         SkDebugf("%s %s %s [%f %f] x [%f %f]\n",
    875                  kOpStrs[element.getOp()],
    876                  (isRect ? "R" : "P"),
    877                  (element.isInverseFilled() ? "I" : " "),
    878                  bounds.fLeft, bounds.fRight, bounds.fTop, bounds.fBottom);
    879     } else {
    880         SkDebugf("EM\n");
    881     }
    882 }
    883 
    884 static void test_reduced_clip_stack(skiatest::Reporter* reporter) {
    885     // We construct random clip stacks, reduce them, and then rasterize both versions to verify that
    886     // they are equal.
    887 
    888     // All the clip elements will be contained within these bounds.
    889     static const SkRect kBounds = SkRect::MakeWH(100, 100);
    890 
    891     enum {
    892         kNumTests = 200,
    893         kMinElemsPerTest = 1,
    894         kMaxElemsPerTest = 50,
    895     };
    896 
    897     // min/max size of a clip element as a fraction of kBounds.
    898     static const SkScalar kMinElemSizeFrac = SK_Scalar1 / 5;
    899     static const SkScalar kMaxElemSizeFrac = SK_Scalar1;
    900 
    901     static const SkRegion::Op kOps[] = {
    902         SkRegion::kDifference_Op,
    903         SkRegion::kIntersect_Op,
    904         SkRegion::kUnion_Op,
    905         SkRegion::kXOR_Op,
    906         SkRegion::kReverseDifference_Op,
    907         SkRegion::kReplace_Op,
    908     };
    909 
    910     // Replace operations short-circuit the optimizer. We want to make sure that we test this code
    911     // path a little bit but we don't want it to prevent us from testing many longer traversals in
    912     // the optimizer.
    913     static const int kReplaceDiv = 4 * kMaxElemsPerTest;
    914 
    915     // We want to test inverse fills. However, they are quite rare in practice so don't over do it.
    916     static const SkScalar kFractionInverted = SK_Scalar1 / kMaxElemsPerTest;
    917 
    918     static const AddElementFunc kElementFuncs[] = {
    919         add_rect,
    920         add_round_rect,
    921         add_oval,
    922     };
    923 
    924     SkMWCRandom r;
    925 
    926     for (int i = 0; i < kNumTests; ++i) {
    927         // Randomly generate a clip stack.
    928         SkClipStack stack;
    929         int numElems = r.nextRangeU(kMinElemsPerTest, kMaxElemsPerTest);
    930         for (int e = 0; e < numElems; ++e) {
    931             SkRegion::Op op = kOps[r.nextULessThan(SK_ARRAY_COUNT(kOps))];
    932             if (op == SkRegion::kReplace_Op) {
    933                 if (r.nextU() % kReplaceDiv) {
    934                     --e;
    935                     continue;
    936                 }
    937             }
    938 
    939             // saves can change the clip stack behavior when an element is added.
    940             bool doSave = r.nextBool();
    941 
    942             SkSize size = SkSize::Make(
    943                 SkScalarFloorToScalar(SkScalarMul(kBounds.width(), r.nextRangeScalar(kMinElemSizeFrac, kMaxElemSizeFrac))),
    944                 SkScalarFloorToScalar(SkScalarMul(kBounds.height(), r.nextRangeScalar(kMinElemSizeFrac, kMaxElemSizeFrac))));
    945 
    946             SkPoint xy = {SkScalarFloorToScalar(r.nextRangeScalar(kBounds.fLeft, kBounds.fRight - size.fWidth)),
    947                           SkScalarFloorToScalar(r.nextRangeScalar(kBounds.fTop, kBounds.fBottom - size.fHeight))};
    948 
    949             SkRect rect = SkRect::MakeXYWH(xy.fX, xy.fY, size.fWidth, size.fHeight);
    950 
    951             bool invert = r.nextBiasedBool(kFractionInverted);
    952             kElementFuncs[r.nextULessThan(SK_ARRAY_COUNT(kElementFuncs))](rect, invert, op, &stack);
    953             if (doSave) {
    954                 stack.save();
    955             }
    956         }
    957 
    958         SkRect inflatedBounds = kBounds;
    959         inflatedBounds.outset(kBounds.width() / 2, kBounds.height() / 2);
    960         SkIRect inflatedIBounds;
    961         inflatedBounds.roundOut(&inflatedIBounds);
    962 
    963         typedef GrReducedClip::ElementList ElementList;
    964         // Get the reduced version of the stack.
    965         ElementList reducedClips;
    966 
    967         GrReducedClip::InitialState initial;
    968         SkIRect tBounds(inflatedIBounds);
    969         SkIRect* tightBounds = r.nextBool() ? &tBounds : NULL;
    970         GrReducedClip::ReduceClipStack(stack,
    971                                        inflatedIBounds,
    972                                        &reducedClips,
    973                                        &initial,
    974                                        tightBounds);
    975 
    976         // Build a new clip stack based on the reduced clip elements
    977         SkClipStack reducedStack;
    978         if (GrReducedClip::kAllOut_InitialState == initial) {
    979             // whether the result is bounded or not, the whole plane should start outside the clip.
    980             reducedStack.clipEmpty();
    981         }
    982         for (ElementList::Iter iter = reducedClips.headIter(); NULL != iter.get(); iter.next()) {
    983             add_elem_to_stack(*iter.get(), &reducedStack);
    984         }
    985 
    986         // GrReducedClipStack assumes that the final result is clipped to the returned bounds
    987         if (NULL != tightBounds) {
    988             reducedStack.clipDevRect(*tightBounds, SkRegion::kIntersect_Op);
    989         }
    990 
    991         // convert both the original stack and reduced stack to SkRegions and see if they're equal
    992         SkRegion region;
    993         SkRegion reducedRegion;
    994 
    995         region.setRect(inflatedIBounds);
    996         const SkClipStack::Element* element;
    997         SkClipStack::Iter iter(stack, SkClipStack::Iter::kBottom_IterStart);
    998         while ((element = iter.next())) {
    999             add_elem_to_region(*element, inflatedIBounds, &region);
   1000         }
   1001 
   1002         reducedRegion.setRect(inflatedIBounds);
   1003         iter.reset(reducedStack, SkClipStack::Iter::kBottom_IterStart);
   1004         while ((element = iter.next())) {
   1005             add_elem_to_region(*element, inflatedIBounds, &reducedRegion);
   1006         }
   1007 
   1008         REPORTER_ASSERT(reporter, region == reducedRegion);
   1009     }
   1010 }
   1011 
   1012 #endif
   1013 ///////////////////////////////////////////////////////////////////////////////////////////////////
   1014 
   1015 static void TestClipStack(skiatest::Reporter* reporter) {
   1016     SkClipStack stack;
   1017 
   1018     REPORTER_ASSERT(reporter, 0 == stack.getSaveCount());
   1019     assert_count(reporter, stack, 0);
   1020 
   1021     static const SkIRect gRects[] = {
   1022         { 0, 0, 100, 100 },
   1023         { 25, 25, 125, 125 },
   1024         { 0, 0, 1000, 1000 },
   1025         { 0, 0, 75, 75 }
   1026     };
   1027     for (size_t i = 0; i < SK_ARRAY_COUNT(gRects); i++) {
   1028         stack.clipDevRect(gRects[i], SkRegion::kIntersect_Op);
   1029     }
   1030 
   1031     // all of the above rects should have been intersected, leaving only 1 rect
   1032     SkClipStack::B2TIter iter(stack);
   1033     const SkClipStack::Element* element = iter.next();
   1034     SkRect answer;
   1035     answer.iset(25, 25, 75, 75);
   1036 
   1037     REPORTER_ASSERT(reporter, NULL != element);
   1038     REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
   1039     REPORTER_ASSERT(reporter, SkRegion::kIntersect_Op == element->getOp());
   1040     REPORTER_ASSERT(reporter, element->getRect() == answer);
   1041     // now check that we only had one in our iterator
   1042     REPORTER_ASSERT(reporter, !iter.next());
   1043 
   1044     stack.reset();
   1045     REPORTER_ASSERT(reporter, 0 == stack.getSaveCount());
   1046     assert_count(reporter, stack, 0);
   1047 
   1048     test_assign_and_comparison(reporter);
   1049     test_iterators(reporter);
   1050     test_bounds(reporter, true);        // once with rects
   1051     test_bounds(reporter, false);       // once with paths
   1052     test_isWideOpen(reporter);
   1053     test_rect_merging(reporter);
   1054     test_rect_replace(reporter);
   1055     test_rect_inverse_fill(reporter);
   1056     test_path_replace(reporter);
   1057     test_quickContains(reporter);
   1058 #if SK_SUPPORT_GPU
   1059     test_reduced_clip_stack(reporter);
   1060 #endif
   1061 }
   1062 
   1063 #include "TestClassDef.h"
   1064 DEFINE_TESTCLASS("ClipStack", TestClipStackClass, TestClipStack)
   1065