ClipStackTest.cpp revision e0e7cfe44bb9d66d76120a79e5275c294bacaa22 
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
19static 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
124static 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)
136static 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
196static 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
295static 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
364static 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
378static 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
395static 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.
471static 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.
498static 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
601static 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.
786typedef void (*AddElementFunc) (const SkRect& rect,
787                                bool invert,
788                                SkRegion::Op op,
789                                SkClipStack* stack);
790
791static 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
802static 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
813static 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
822static 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
837static 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.
862static 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
884static 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    SkRandom 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
1015static 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"
1064DEFINE_TESTCLASS("ClipStack", TestClipStackClass, TestClipStack)
1065