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 "Test.h"
9#include "SkClipStack.h"
10#include "SkPath.h"
11#include "SkRandom.h"
12#include "SkRect.h"
13#include "SkRegion.h"
14
15#if SK_SUPPORT_GPU
16#include "GrClipStackClip.h"
17#include "GrReducedClip.h"
18#include "GrResourceCache.h"
19#include "GrSurfaceProxyPriv.h"
20#include "GrTexture.h"
21#include "GrTextureProxy.h"
22typedef GrReducedClip::ElementList ElementList;
23typedef GrReducedClip::InitialState InitialState;
24#endif
25
26static void test_assign_and_comparison(skiatest::Reporter* reporter) {
27    SkClipStack s;
28    bool doAA = false;
29
30    REPORTER_ASSERT(reporter, 0 == s.getSaveCount());
31
32    // Build up a clip stack with a path, an empty clip, and a rect.
33    s.save();
34    REPORTER_ASSERT(reporter, 1 == s.getSaveCount());
35
36    SkPath p;
37    p.moveTo(5, 6);
38    p.lineTo(7, 8);
39    p.lineTo(5, 9);
40    p.close();
41    s.clipPath(p, SkMatrix::I(), kIntersect_SkClipOp, doAA);
42
43    s.save();
44    REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
45
46    SkRect r = SkRect::MakeLTRB(1, 2, 3, 4);
47    s.clipRect(r, SkMatrix::I(), kIntersect_SkClipOp, doAA);
48    r = SkRect::MakeLTRB(10, 11, 12, 13);
49    s.clipRect(r, SkMatrix::I(), kIntersect_SkClipOp, doAA);
50
51    s.save();
52    REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
53
54    r = SkRect::MakeLTRB(14, 15, 16, 17);
55    s.clipRect(r, SkMatrix::I(), kUnion_SkClipOp, doAA);
56
57    // Test that assignment works.
58    SkClipStack copy = s;
59    REPORTER_ASSERT(reporter, s == copy);
60
61    // Test that different save levels triggers not equal.
62    s.restore();
63    REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
64    REPORTER_ASSERT(reporter, s != copy);
65
66    // Test that an equal, but not copied version is equal.
67    s.save();
68    REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
69    r = SkRect::MakeLTRB(14, 15, 16, 17);
70    s.clipRect(r, SkMatrix::I(), kUnion_SkClipOp, doAA);
71    REPORTER_ASSERT(reporter, s == copy);
72
73    // Test that a different op on one level triggers not equal.
74    s.restore();
75    REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
76    s.save();
77    REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
78    r = SkRect::MakeLTRB(14, 15, 16, 17);
79    s.clipRect(r, SkMatrix::I(), kIntersect_SkClipOp, doAA);
80    REPORTER_ASSERT(reporter, s != copy);
81
82    // Test that version constructed with rect-path rather than a rect is still considered equal.
83    s.restore();
84    s.save();
85    SkPath rp;
86    rp.addRect(r);
87    s.clipPath(rp, SkMatrix::I(), kUnion_SkClipOp, doAA);
88    REPORTER_ASSERT(reporter, s == copy);
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.clipRect(r, SkMatrix::I(), kUnion_SkClipOp, 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.clipPath(p, SkMatrix::I(), kIntersect_SkClipOp, 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.clipRect(gRects[i], SkMatrix::I(), kUnion_SkClipOp, false);
149    }
150
151    assert_count(reporter, stack, 4);
152
153    // bottom to top iteration
154    {
155        const SkClipStack::Element* element = nullptr;
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 = nullptr;
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 = nullptr;
186
187        SkClipStack::Iter iter(stack, SkClipStack::Iter::kBottom_IterStart);
188
189        element = iter.skipToTopmost(kUnion_SkClipOp);
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, SkClipStack::Element::Type primType) {
197    static const int gNumCases = 20;
198    static const SkRect gAnswerRectsBW[gNumCases] = {
199        // A op B
200        { 40, 40, 50, 50 },
201        { 10, 10, 50, 50 },
202        { 10, 10, 80, 80 },
203        { 10, 10, 80, 80 },
204        { 40, 40, 80, 80 },
205
206        // invA op B
207        { 40, 40, 80, 80 },
208        { 0, 0, 100, 100 },
209        { 0, 0, 100, 100 },
210        { 0, 0, 100, 100 },
211        { 40, 40, 50, 50 },
212
213        // A op invB
214        { 10, 10, 50, 50 },
215        { 40, 40, 50, 50 },
216        { 0, 0, 100, 100 },
217        { 0, 0, 100, 100 },
218        { 0, 0, 100, 100 },
219
220        // invA op invB
221        { 0, 0, 100, 100 },
222        { 40, 40, 80, 80 },
223        { 0, 0, 100, 100 },
224        { 10, 10, 80, 80 },
225        { 10, 10, 50, 50 },
226    };
227
228    static const SkClipOp gOps[] = {
229        kIntersect_SkClipOp,
230        kDifference_SkClipOp,
231        kUnion_SkClipOp,
232        kXOR_SkClipOp,
233        kReverseDifference_SkClipOp
234    };
235
236    SkRect rectA, rectB;
237
238    rectA.iset(10, 10, 50, 50);
239    rectB.iset(40, 40, 80, 80);
240
241    SkRRect rrectA, rrectB;
242    rrectA.setOval(rectA);
243    rrectB.setRectXY(rectB, SkIntToScalar(1), SkIntToScalar(2));
244
245    SkPath pathA, pathB;
246
247    pathA.addRoundRect(rectA, SkIntToScalar(5), SkIntToScalar(5));
248    pathB.addRoundRect(rectB, SkIntToScalar(5), SkIntToScalar(5));
249
250    SkClipStack stack;
251    SkRect devClipBound;
252    bool isIntersectionOfRects = false;
253
254    int testCase = 0;
255    int numBitTests = SkClipStack::Element::kPath_Type == primType ? 4 : 1;
256    for (int invBits = 0; invBits < numBitTests; ++invBits) {
257        for (size_t op = 0; op < SK_ARRAY_COUNT(gOps); ++op) {
258
259            stack.save();
260            bool doInvA = SkToBool(invBits & 1);
261            bool doInvB = SkToBool(invBits & 2);
262
263            pathA.setFillType(doInvA ? SkPath::kInverseEvenOdd_FillType :
264                                       SkPath::kEvenOdd_FillType);
265            pathB.setFillType(doInvB ? SkPath::kInverseEvenOdd_FillType :
266                                       SkPath::kEvenOdd_FillType);
267
268            switch (primType) {
269                case SkClipStack::Element::kEmpty_Type:
270                    SkDEBUGFAIL("Don't call this with kEmpty.");
271                    break;
272                case SkClipStack::Element::kRect_Type:
273                    stack.clipRect(rectA, SkMatrix::I(), kIntersect_SkClipOp, false);
274                    stack.clipRect(rectB, SkMatrix::I(), gOps[op], false);
275                    break;
276                case SkClipStack::Element::kRRect_Type:
277                    stack.clipRRect(rrectA, SkMatrix::I(), kIntersect_SkClipOp, false);
278                    stack.clipRRect(rrectB, SkMatrix::I(), gOps[op], false);
279                    break;
280                case SkClipStack::Element::kPath_Type:
281                    stack.clipPath(pathA, SkMatrix::I(), kIntersect_SkClipOp, false);
282                    stack.clipPath(pathB, SkMatrix::I(), gOps[op], false);
283                    break;
284            }
285
286            REPORTER_ASSERT(reporter, !stack.isWideOpen());
287            REPORTER_ASSERT(reporter, SkClipStack::kWideOpenGenID != stack.getTopmostGenID());
288
289            stack.getConservativeBounds(0, 0, 100, 100, &devClipBound,
290                                        &isIntersectionOfRects);
291
292            if (SkClipStack::Element::kRect_Type == primType) {
293                REPORTER_ASSERT(reporter, isIntersectionOfRects ==
294                        (gOps[op] == kIntersect_SkClipOp));
295            } else {
296                REPORTER_ASSERT(reporter, !isIntersectionOfRects);
297            }
298
299            SkASSERT(testCase < gNumCases);
300            REPORTER_ASSERT(reporter, devClipBound == gAnswerRectsBW[testCase]);
301            ++testCase;
302
303            stack.restore();
304        }
305    }
306}
307
308// Test out 'isWideOpen' entry point
309static void test_isWideOpen(skiatest::Reporter* reporter) {
310    {
311        // Empty stack is wide open. Wide open stack means that gen id is wide open.
312        SkClipStack stack;
313        REPORTER_ASSERT(reporter, stack.isWideOpen());
314        REPORTER_ASSERT(reporter, SkClipStack::kWideOpenGenID == stack.getTopmostGenID());
315    }
316
317    SkRect rectA, rectB;
318
319    rectA.iset(10, 10, 40, 40);
320    rectB.iset(50, 50, 80, 80);
321
322    // Stack should initially be wide open
323    {
324        SkClipStack stack;
325
326        REPORTER_ASSERT(reporter, stack.isWideOpen());
327        REPORTER_ASSERT(reporter, SkClipStack::kWideOpenGenID == stack.getTopmostGenID());
328    }
329
330    // Test out case where the user specifies a union that includes everything
331    {
332        SkClipStack stack;
333
334        SkPath clipA, clipB;
335
336        clipA.addRoundRect(rectA, SkIntToScalar(5), SkIntToScalar(5));
337        clipA.setFillType(SkPath::kInverseEvenOdd_FillType);
338
339        clipB.addRoundRect(rectB, SkIntToScalar(5), SkIntToScalar(5));
340        clipB.setFillType(SkPath::kInverseEvenOdd_FillType);
341
342        stack.clipPath(clipA, SkMatrix::I(), kReplace_SkClipOp, false);
343        stack.clipPath(clipB, SkMatrix::I(), kUnion_SkClipOp, false);
344
345        REPORTER_ASSERT(reporter, stack.isWideOpen());
346        REPORTER_ASSERT(reporter, SkClipStack::kWideOpenGenID == stack.getTopmostGenID());
347    }
348
349    // Test out union w/ a wide open clip
350    {
351        SkClipStack stack;
352
353        stack.clipRect(rectA, SkMatrix::I(), kUnion_SkClipOp, false);
354
355        REPORTER_ASSERT(reporter, stack.isWideOpen());
356        REPORTER_ASSERT(reporter, SkClipStack::kWideOpenGenID == stack.getTopmostGenID());
357    }
358
359    // Test out empty difference from a wide open clip
360    {
361        SkClipStack stack;
362
363        SkRect emptyRect;
364        emptyRect.setEmpty();
365
366        stack.clipRect(emptyRect, SkMatrix::I(), kDifference_SkClipOp, false);
367
368        REPORTER_ASSERT(reporter, stack.isWideOpen());
369        REPORTER_ASSERT(reporter, SkClipStack::kWideOpenGenID == stack.getTopmostGenID());
370    }
371
372    // Test out return to wide open
373    {
374        SkClipStack stack;
375
376        stack.save();
377
378        stack.clipRect(rectA, SkMatrix::I(), kReplace_SkClipOp, false);
379
380        REPORTER_ASSERT(reporter, !stack.isWideOpen());
381        REPORTER_ASSERT(reporter, SkClipStack::kWideOpenGenID != stack.getTopmostGenID());
382
383        stack.restore();
384
385        REPORTER_ASSERT(reporter, stack.isWideOpen());
386        REPORTER_ASSERT(reporter, SkClipStack::kWideOpenGenID == stack.getTopmostGenID());
387    }
388}
389
390static int count(const SkClipStack& stack) {
391
392    SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
393
394    const SkClipStack::Element* element = nullptr;
395    int count = 0;
396
397    for (element = iter.prev(); element; element = iter.prev(), ++count) {
398        ;
399    }
400
401    return count;
402}
403
404static void test_rect_inverse_fill(skiatest::Reporter* reporter) {
405    // non-intersecting rectangles
406    SkRect rect  = SkRect::MakeLTRB(0, 0, 10, 10);
407
408    SkPath path;
409    path.addRect(rect);
410    path.toggleInverseFillType();
411    SkClipStack stack;
412    stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
413
414    SkRect bounds;
415    SkClipStack::BoundsType boundsType;
416    stack.getBounds(&bounds, &boundsType);
417    REPORTER_ASSERT(reporter, SkClipStack::kInsideOut_BoundsType == boundsType);
418    REPORTER_ASSERT(reporter, bounds == rect);
419}
420
421static void test_rect_replace(skiatest::Reporter* reporter) {
422    SkRect rect = SkRect::MakeWH(100, 100);
423    SkRect rect2 = SkRect::MakeXYWH(50, 50, 100, 100);
424
425    SkRect bound;
426    SkClipStack::BoundsType type;
427    bool isIntersectionOfRects;
428
429    // Adding a new rect with the replace operator should not increase
430    // the stack depth. BW replacing BW.
431    {
432        SkClipStack stack;
433        REPORTER_ASSERT(reporter, 0 == count(stack));
434        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
435        REPORTER_ASSERT(reporter, 1 == count(stack));
436        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
437        REPORTER_ASSERT(reporter, 1 == count(stack));
438    }
439
440    // Adding a new rect with the replace operator should not increase
441    // the stack depth. AA replacing AA.
442    {
443        SkClipStack stack;
444        REPORTER_ASSERT(reporter, 0 == count(stack));
445        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, true);
446        REPORTER_ASSERT(reporter, 1 == count(stack));
447        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, true);
448        REPORTER_ASSERT(reporter, 1 == count(stack));
449    }
450
451    // Adding a new rect with the replace operator should not increase
452    // the stack depth. BW replacing AA replacing BW.
453    {
454        SkClipStack stack;
455        REPORTER_ASSERT(reporter, 0 == count(stack));
456        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
457        REPORTER_ASSERT(reporter, 1 == count(stack));
458        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, true);
459        REPORTER_ASSERT(reporter, 1 == count(stack));
460        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
461        REPORTER_ASSERT(reporter, 1 == count(stack));
462    }
463
464    // Make sure replace clip rects don't collapse too much.
465    {
466        SkClipStack stack;
467        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
468        stack.clipRect(rect2, SkMatrix::I(), kIntersect_SkClipOp, false);
469        REPORTER_ASSERT(reporter, 1 == count(stack));
470
471        stack.save();
472        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
473        REPORTER_ASSERT(reporter, 2 == count(stack));
474        stack.getBounds(&bound, &type, &isIntersectionOfRects);
475        REPORTER_ASSERT(reporter, bound == rect);
476        stack.restore();
477        REPORTER_ASSERT(reporter, 1 == count(stack));
478
479        stack.save();
480        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
481        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
482        REPORTER_ASSERT(reporter, 2 == count(stack));
483        stack.restore();
484        REPORTER_ASSERT(reporter, 1 == count(stack));
485
486        stack.save();
487        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
488        stack.clipRect(rect2, SkMatrix::I(), kIntersect_SkClipOp, false);
489        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, false);
490        REPORTER_ASSERT(reporter, 2 == count(stack));
491        stack.restore();
492        REPORTER_ASSERT(reporter, 1 == count(stack));
493    }
494}
495
496// Simplified path-based version of test_rect_replace.
497static void test_path_replace(skiatest::Reporter* reporter) {
498    SkRect rect = SkRect::MakeWH(100, 100);
499    SkPath path;
500    path.addCircle(50, 50, 50);
501
502    // Replace operation doesn't grow the stack.
503    {
504        SkClipStack stack;
505        REPORTER_ASSERT(reporter, 0 == count(stack));
506        stack.clipPath(path, SkMatrix::I(), kReplace_SkClipOp, false);
507        REPORTER_ASSERT(reporter, 1 == count(stack));
508        stack.clipPath(path, SkMatrix::I(), kReplace_SkClipOp, false);
509        REPORTER_ASSERT(reporter, 1 == count(stack));
510    }
511
512    // Replacing rect with path.
513    {
514        SkClipStack stack;
515        stack.clipRect(rect, SkMatrix::I(), kReplace_SkClipOp, true);
516        REPORTER_ASSERT(reporter, 1 == count(stack));
517        stack.clipPath(path, SkMatrix::I(), kReplace_SkClipOp, true);
518        REPORTER_ASSERT(reporter, 1 == count(stack));
519    }
520}
521
522// Test out SkClipStack's merging of rect clips. In particular exercise
523// merging of aa vs. bw rects.
524static void test_rect_merging(skiatest::Reporter* reporter) {
525
526    SkRect overlapLeft  = SkRect::MakeLTRB(10, 10, 50, 50);
527    SkRect overlapRight = SkRect::MakeLTRB(40, 40, 80, 80);
528
529    SkRect nestedParent = SkRect::MakeLTRB(10, 10, 90, 90);
530    SkRect nestedChild  = SkRect::MakeLTRB(40, 40, 60, 60);
531
532    SkRect bound;
533    SkClipStack::BoundsType type;
534    bool isIntersectionOfRects;
535
536    // all bw overlapping - should merge
537    {
538        SkClipStack stack;
539
540        stack.clipRect(overlapLeft, SkMatrix::I(), kReplace_SkClipOp, false);
541
542        stack.clipRect(overlapRight, SkMatrix::I(), kIntersect_SkClipOp, false);
543
544        REPORTER_ASSERT(reporter, 1 == count(stack));
545
546        stack.getBounds(&bound, &type, &isIntersectionOfRects);
547
548        REPORTER_ASSERT(reporter, isIntersectionOfRects);
549    }
550
551    // all aa overlapping - should merge
552    {
553        SkClipStack stack;
554
555        stack.clipRect(overlapLeft, SkMatrix::I(), kReplace_SkClipOp, true);
556
557        stack.clipRect(overlapRight, SkMatrix::I(), kIntersect_SkClipOp, true);
558
559        REPORTER_ASSERT(reporter, 1 == count(stack));
560
561        stack.getBounds(&bound, &type, &isIntersectionOfRects);
562
563        REPORTER_ASSERT(reporter, isIntersectionOfRects);
564    }
565
566    // mixed overlapping - should _not_ merge
567    {
568        SkClipStack stack;
569
570        stack.clipRect(overlapLeft, SkMatrix::I(), kReplace_SkClipOp, true);
571
572        stack.clipRect(overlapRight, SkMatrix::I(), kIntersect_SkClipOp, false);
573
574        REPORTER_ASSERT(reporter, 2 == count(stack));
575
576        stack.getBounds(&bound, &type, &isIntersectionOfRects);
577
578        REPORTER_ASSERT(reporter, !isIntersectionOfRects);
579    }
580
581    // mixed nested (bw inside aa) - should merge
582    {
583        SkClipStack stack;
584
585        stack.clipRect(nestedParent, SkMatrix::I(), kReplace_SkClipOp, true);
586
587        stack.clipRect(nestedChild, SkMatrix::I(), kIntersect_SkClipOp, false);
588
589        REPORTER_ASSERT(reporter, 1 == count(stack));
590
591        stack.getBounds(&bound, &type, &isIntersectionOfRects);
592
593        REPORTER_ASSERT(reporter, isIntersectionOfRects);
594    }
595
596    // mixed nested (aa inside bw) - should merge
597    {
598        SkClipStack stack;
599
600        stack.clipRect(nestedParent, SkMatrix::I(), kReplace_SkClipOp, false);
601
602        stack.clipRect(nestedChild, SkMatrix::I(), kIntersect_SkClipOp, true);
603
604        REPORTER_ASSERT(reporter, 1 == count(stack));
605
606        stack.getBounds(&bound, &type, &isIntersectionOfRects);
607
608        REPORTER_ASSERT(reporter, isIntersectionOfRects);
609    }
610
611    // reverse nested (aa inside bw) - should _not_ merge
612    {
613        SkClipStack stack;
614
615        stack.clipRect(nestedChild, SkMatrix::I(), kReplace_SkClipOp, false);
616
617        stack.clipRect(nestedParent, SkMatrix::I(), kIntersect_SkClipOp, true);
618
619        REPORTER_ASSERT(reporter, 2 == count(stack));
620
621        stack.getBounds(&bound, &type, &isIntersectionOfRects);
622
623        REPORTER_ASSERT(reporter, !isIntersectionOfRects);
624    }
625}
626
627static void test_quickContains(skiatest::Reporter* reporter) {
628    SkRect testRect = SkRect::MakeLTRB(10, 10, 40, 40);
629    SkRect insideRect = SkRect::MakeLTRB(20, 20, 30, 30);
630    SkRect intersectingRect = SkRect::MakeLTRB(25, 25, 50, 50);
631    SkRect outsideRect = SkRect::MakeLTRB(0, 0, 50, 50);
632    SkRect nonIntersectingRect = SkRect::MakeLTRB(100, 100, 110, 110);
633
634    SkPath insideCircle;
635    insideCircle.addCircle(25, 25, 5);
636    SkPath intersectingCircle;
637    intersectingCircle.addCircle(25, 40, 10);
638    SkPath outsideCircle;
639    outsideCircle.addCircle(25, 25, 50);
640    SkPath nonIntersectingCircle;
641    nonIntersectingCircle.addCircle(100, 100, 5);
642
643    {
644        SkClipStack stack;
645        stack.clipRect(outsideRect, SkMatrix::I(), kDifference_SkClipOp, false);
646        // return false because quickContains currently does not care for kDifference_SkClipOp
647        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
648    }
649
650    // Replace Op tests
651    {
652        SkClipStack stack;
653        stack.clipRect(outsideRect, SkMatrix::I(), kReplace_SkClipOp, false);
654        REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
655    }
656
657    {
658        SkClipStack stack;
659        stack.clipRect(insideRect, SkMatrix::I(), kIntersect_SkClipOp, false);
660        stack.save(); // To prevent in-place substitution by replace OP
661        stack.clipRect(outsideRect, SkMatrix::I(), kReplace_SkClipOp, false);
662        REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
663        stack.restore();
664    }
665
666    {
667        SkClipStack stack;
668        stack.clipRect(outsideRect, SkMatrix::I(), kIntersect_SkClipOp, false);
669        stack.save(); // To prevent in-place substitution by replace OP
670        stack.clipRect(insideRect, SkMatrix::I(), kReplace_SkClipOp, false);
671        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
672        stack.restore();
673    }
674
675    // Verify proper traversal of multi-element clip
676    {
677        SkClipStack stack;
678        stack.clipRect(insideRect, SkMatrix::I(), kIntersect_SkClipOp, false);
679        // Use a path for second clip to prevent in-place intersection
680        stack.clipPath(outsideCircle, SkMatrix::I(), kIntersect_SkClipOp, false);
681        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
682    }
683
684    // Intersect Op tests with rectangles
685    {
686        SkClipStack stack;
687        stack.clipRect(outsideRect, SkMatrix::I(), kIntersect_SkClipOp, false);
688        REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
689    }
690
691    {
692        SkClipStack stack;
693        stack.clipRect(insideRect, SkMatrix::I(), kIntersect_SkClipOp, false);
694        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
695    }
696
697    {
698        SkClipStack stack;
699        stack.clipRect(intersectingRect, SkMatrix::I(), kIntersect_SkClipOp, false);
700        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
701    }
702
703    {
704        SkClipStack stack;
705        stack.clipRect(nonIntersectingRect, SkMatrix::I(), kIntersect_SkClipOp, false);
706        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
707    }
708
709    // Intersect Op tests with circle paths
710    {
711        SkClipStack stack;
712        stack.clipPath(outsideCircle, SkMatrix::I(), kIntersect_SkClipOp, false);
713        REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
714    }
715
716    {
717        SkClipStack stack;
718        stack.clipPath(insideCircle, SkMatrix::I(), kIntersect_SkClipOp, false);
719        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
720    }
721
722    {
723        SkClipStack stack;
724        stack.clipPath(intersectingCircle, SkMatrix::I(), kIntersect_SkClipOp, false);
725        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
726    }
727
728    {
729        SkClipStack stack;
730        stack.clipPath(nonIntersectingCircle, SkMatrix::I(), kIntersect_SkClipOp, false);
731        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
732    }
733
734    // Intersect Op tests with inverse filled rectangles
735    {
736        SkClipStack stack;
737        SkPath path;
738        path.addRect(outsideRect);
739        path.toggleInverseFillType();
740        stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
741        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
742    }
743
744    {
745        SkClipStack stack;
746        SkPath path;
747        path.addRect(insideRect);
748        path.toggleInverseFillType();
749        stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
750        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
751    }
752
753    {
754        SkClipStack stack;
755        SkPath path;
756        path.addRect(intersectingRect);
757        path.toggleInverseFillType();
758        stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
759        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
760    }
761
762    {
763        SkClipStack stack;
764        SkPath path;
765        path.addRect(nonIntersectingRect);
766        path.toggleInverseFillType();
767        stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
768        REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
769    }
770
771    // Intersect Op tests with inverse filled circles
772    {
773        SkClipStack stack;
774        SkPath path = outsideCircle;
775        path.toggleInverseFillType();
776        stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
777        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
778    }
779
780    {
781        SkClipStack stack;
782        SkPath path = insideCircle;
783        path.toggleInverseFillType();
784        stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
785        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
786    }
787
788    {
789        SkClipStack stack;
790        SkPath path = intersectingCircle;
791        path.toggleInverseFillType();
792        stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
793        REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
794    }
795
796    {
797        SkClipStack stack;
798        SkPath path = nonIntersectingCircle;
799        path.toggleInverseFillType();
800        stack.clipPath(path, SkMatrix::I(), kIntersect_SkClipOp, false);
801        REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
802    }
803}
804
805static void set_region_to_stack(const SkClipStack& stack, const SkIRect& bounds, SkRegion* region) {
806    region->setRect(bounds);
807    SkClipStack::Iter iter(stack, SkClipStack::Iter::kBottom_IterStart);
808    while (const SkClipStack::Element *element = iter.next()) {
809        SkRegion elemRegion;
810        SkRegion boundsRgn(bounds);
811        SkPath path;
812
813        switch (element->getType()) {
814            case SkClipStack::Element::kEmpty_Type:
815                elemRegion.setEmpty();
816                break;
817            default:
818                element->asPath(&path);
819                elemRegion.setPath(path, boundsRgn);
820                break;
821        }
822        region->op(elemRegion, (SkRegion::Op)element->getOp());
823    }
824}
825
826static void test_invfill_diff_bug(skiatest::Reporter* reporter) {
827    SkClipStack stack;
828    stack.clipRect({10, 10, 20, 20}, SkMatrix::I(), kIntersect_SkClipOp, false);
829
830    SkPath path;
831    path.addRect({30, 10, 40, 20});
832    path.setFillType(SkPath::kInverseWinding_FillType);
833    stack.clipPath(path, SkMatrix::I(), kDifference_SkClipOp, false);
834
835    REPORTER_ASSERT(reporter, SkClipStack::kEmptyGenID == stack.getTopmostGenID());
836
837    SkRect stackBounds;
838    SkClipStack::BoundsType stackBoundsType;
839    stack.getBounds(&stackBounds, &stackBoundsType);
840
841    REPORTER_ASSERT(reporter, stackBounds.isEmpty());
842    REPORTER_ASSERT(reporter, SkClipStack::kNormal_BoundsType == stackBoundsType);
843
844    SkRegion region;
845    set_region_to_stack(stack, {0, 0, 50, 30}, &region);
846
847    REPORTER_ASSERT(reporter, region.isEmpty());
848}
849
850///////////////////////////////////////////////////////////////////////////////////////////////////
851
852#if SK_SUPPORT_GPU
853// Functions that add a shape to the clip stack. The shape is computed from a rectangle.
854// AA is always disabled since the clip stack reducer can cause changes in aa rasterization of the
855// stack. A fractional edge repeated in different elements may be rasterized fewer times using the
856// reduced stack.
857typedef void (*AddElementFunc) (const SkRect& rect,
858                                bool invert,
859                                SkClipOp op,
860                                SkClipStack* stack,
861                                bool doAA);
862
863static void add_round_rect(const SkRect& rect, bool invert, SkClipOp op, SkClipStack* stack,
864                           bool doAA) {
865    SkScalar rx = rect.width() / 10;
866    SkScalar ry = rect.height() / 20;
867    if (invert) {
868        SkPath path;
869        path.addRoundRect(rect, rx, ry);
870        path.setFillType(SkPath::kInverseWinding_FillType);
871        stack->clipPath(path, SkMatrix::I(), op, doAA);
872    } else {
873        SkRRect rrect;
874        rrect.setRectXY(rect, rx, ry);
875        stack->clipRRect(rrect, SkMatrix::I(), op, doAA);
876    }
877};
878
879static void add_rect(const SkRect& rect, bool invert, SkClipOp op, SkClipStack* stack,
880                     bool doAA) {
881    if (invert) {
882        SkPath path;
883        path.addRect(rect);
884        path.setFillType(SkPath::kInverseWinding_FillType);
885        stack->clipPath(path, SkMatrix::I(), op, doAA);
886    } else {
887        stack->clipRect(rect, SkMatrix::I(), op, doAA);
888    }
889};
890
891static void add_oval(const SkRect& rect, bool invert, SkClipOp op, SkClipStack* stack,
892                     bool doAA) {
893    SkPath path;
894    path.addOval(rect);
895    if (invert) {
896        path.setFillType(SkPath::kInverseWinding_FillType);
897    }
898    stack->clipPath(path, SkMatrix::I(), op, doAA);
899};
900
901static void add_elem_to_stack(const SkClipStack::Element& element, SkClipStack* stack) {
902    switch (element.getType()) {
903        case SkClipStack::Element::kRect_Type:
904            stack->clipRect(element.getRect(), SkMatrix::I(), element.getOp(), element.isAA());
905            break;
906        case SkClipStack::Element::kRRect_Type:
907            stack->clipRRect(element.getRRect(), SkMatrix::I(), element.getOp(), element.isAA());
908            break;
909        case SkClipStack::Element::kPath_Type:
910            stack->clipPath(element.getPath(), SkMatrix::I(), element.getOp(), element.isAA());
911            break;
912        case SkClipStack::Element::kEmpty_Type:
913            SkDEBUGFAIL("Why did the reducer produce an explicit empty.");
914            stack->clipEmpty();
915            break;
916    }
917}
918
919static void test_reduced_clip_stack(skiatest::Reporter* reporter) {
920    // We construct random clip stacks, reduce them, and then rasterize both versions to verify that
921    // they are equal.
922
923    // All the clip elements will be contained within these bounds.
924    static const SkIRect kIBounds = SkIRect::MakeWH(100, 100);
925    static const SkRect kBounds = SkRect::Make(kIBounds);
926
927    enum {
928        kNumTests = 250,
929        kMinElemsPerTest = 1,
930        kMaxElemsPerTest = 50,
931    };
932
933    // min/max size of a clip element as a fraction of kBounds.
934    static const SkScalar kMinElemSizeFrac = SK_Scalar1 / 5;
935    static const SkScalar kMaxElemSizeFrac = SK_Scalar1;
936
937    static const SkClipOp kOps[] = {
938        kDifference_SkClipOp,
939        kIntersect_SkClipOp,
940        kUnion_SkClipOp,
941        kXOR_SkClipOp,
942        kReverseDifference_SkClipOp,
943        kReplace_SkClipOp,
944    };
945
946    // Replace operations short-circuit the optimizer. We want to make sure that we test this code
947    // path a little bit but we don't want it to prevent us from testing many longer traversals in
948    // the optimizer.
949    static const int kReplaceDiv = 4 * kMaxElemsPerTest;
950
951    // We want to test inverse fills. However, they are quite rare in practice so don't over do it.
952    static const SkScalar kFractionInverted = SK_Scalar1 / kMaxElemsPerTest;
953
954    static const SkScalar kFractionAntialiased = 0.25;
955
956    static const AddElementFunc kElementFuncs[] = {
957        add_rect,
958        add_round_rect,
959        add_oval,
960    };
961
962    SkRandom r;
963
964    for (int i = 0; i < kNumTests; ++i) {
965        SkString testCase;
966        testCase.printf("Iteration %d", i);
967
968        // Randomly generate a clip stack.
969        SkClipStack stack;
970        int numElems = r.nextRangeU(kMinElemsPerTest, kMaxElemsPerTest);
971        bool doAA = r.nextBiasedBool(kFractionAntialiased);
972        for (int e = 0; e < numElems; ++e) {
973            SkClipOp op = kOps[r.nextULessThan(SK_ARRAY_COUNT(kOps))];
974            if (op == kReplace_SkClipOp) {
975                if (r.nextU() % kReplaceDiv) {
976                    --e;
977                    continue;
978                }
979            }
980
981            // saves can change the clip stack behavior when an element is added.
982            bool doSave = r.nextBool();
983
984            SkSize size = SkSize::Make(
985                kBounds.width()  * r.nextRangeScalar(kMinElemSizeFrac, kMaxElemSizeFrac),
986                kBounds.height() * r.nextRangeScalar(kMinElemSizeFrac, kMaxElemSizeFrac));
987
988            SkPoint xy = {r.nextRangeScalar(kBounds.fLeft, kBounds.fRight - size.fWidth),
989                          r.nextRangeScalar(kBounds.fTop, kBounds.fBottom - size.fHeight)};
990
991            SkRect rect;
992            if (doAA) {
993                rect.setXYWH(xy.fX, xy.fY, size.fWidth, size.fHeight);
994                if (GrClip::IsPixelAligned(rect)) {
995                    // Don't create an element that may accidentally become not antialiased.
996                    rect.outset(0.5f, 0.5f);
997                }
998                SkASSERT(!GrClip::IsPixelAligned(rect));
999            } else {
1000                rect.setXYWH(SkScalarFloorToScalar(xy.fX),
1001                             SkScalarFloorToScalar(xy.fY),
1002                             SkScalarCeilToScalar(size.fWidth),
1003                             SkScalarCeilToScalar(size.fHeight));
1004            }
1005
1006            bool invert = r.nextBiasedBool(kFractionInverted);
1007
1008            kElementFuncs[r.nextULessThan(SK_ARRAY_COUNT(kElementFuncs))](rect, invert, op, &stack,
1009                                                                          doAA);
1010            if (doSave) {
1011                stack.save();
1012            }
1013        }
1014
1015        // Zero the memory we will new the GrReducedClip into. This ensures the elements gen ID
1016        // will be kInvalidGenID if left uninitialized.
1017        SkAlignedSTStorage<1, GrReducedClip> storage;
1018        memset(storage.get(), 0, sizeof(GrReducedClip));
1019        GR_STATIC_ASSERT(0 == SkClipStack::kInvalidGenID);
1020
1021        // Get the reduced version of the stack.
1022        SkRect queryBounds = kBounds;
1023        queryBounds.outset(kBounds.width() / 2, kBounds.height() / 2);
1024        const GrReducedClip* reduced = new (storage.get()) GrReducedClip(stack, queryBounds);
1025
1026        REPORTER_ASSERT_MESSAGE(reporter,
1027                                reduced->elements().isEmpty() ||
1028                                SkClipStack::kInvalidGenID != reduced->elementsGenID(),
1029                                testCase.c_str());
1030
1031        if (!reduced->elements().isEmpty()) {
1032            REPORTER_ASSERT_MESSAGE(reporter, reduced->hasIBounds(), testCase.c_str());
1033            SkRect stackBounds;
1034            SkClipStack::BoundsType stackBoundsType;
1035            stack.getBounds(&stackBounds, &stackBoundsType);
1036            if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
1037                // Unless GrReducedClip starts doing some heroic tightening of the clip bounds, this
1038                // will be true since the stack bounds are completely contained inside the query.
1039                REPORTER_ASSERT_MESSAGE(reporter,
1040                                        GrClip::IsInsideClip(reduced->ibounds(), stackBounds),
1041                                        testCase.c_str());
1042            }
1043            REPORTER_ASSERT_MESSAGE(reporter, reduced->requiresAA() == doAA, testCase.c_str());
1044        }
1045
1046        // Build a new clip stack based on the reduced clip elements
1047        SkClipStack reducedStack;
1048        if (GrReducedClip::InitialState::kAllOut == reduced->initialState()) {
1049            // whether the result is bounded or not, the whole plane should start outside the clip.
1050            reducedStack.clipEmpty();
1051        }
1052        for (ElementList::Iter iter(reduced->elements()); iter.get(); iter.next()) {
1053            add_elem_to_stack(*iter.get(), &reducedStack);
1054        }
1055
1056        SkIRect ibounds = reduced->hasIBounds() ? reduced->ibounds() : kIBounds;
1057
1058        // GrReducedClipStack assumes that the final result is clipped to the returned bounds
1059        reducedStack.clipDevRect(ibounds, kIntersect_SkClipOp);
1060        stack.clipDevRect(ibounds, kIntersect_SkClipOp);
1061
1062        // convert both the original stack and reduced stack to SkRegions and see if they're equal
1063        SkRegion region;
1064        set_region_to_stack(stack, ibounds, &region);
1065
1066        SkRegion reducedRegion;
1067        set_region_to_stack(reducedStack, ibounds, &reducedRegion);
1068
1069        REPORTER_ASSERT_MESSAGE(reporter, region == reducedRegion, testCase.c_str());
1070
1071        reduced->~GrReducedClip();
1072    }
1073}
1074
1075#ifdef SK_BUILD_FOR_WIN
1076    #define SUPPRESS_VISIBILITY_WARNING
1077#else
1078    #define SUPPRESS_VISIBILITY_WARNING __attribute__((visibility("hidden")))
1079#endif
1080
1081static void test_reduced_clip_stack_genid(skiatest::Reporter* reporter) {
1082    {
1083        SkClipStack stack;
1084        stack.clipRect(SkRect::MakeXYWH(0, 0, 100, 100), SkMatrix::I(), kReplace_SkClipOp,
1085                       true);
1086        stack.clipRect(SkRect::MakeXYWH(0, 0, SkScalar(50.3), SkScalar(50.3)), SkMatrix::I(),
1087                       kReplace_SkClipOp, true);
1088        SkRect bounds = SkRect::MakeXYWH(0, 0, 100, 100);
1089
1090        SkAlignedSTStorage<1, GrReducedClip> storage;
1091        memset(storage.get(), 0, sizeof(GrReducedClip));
1092        GR_STATIC_ASSERT(0 == SkClipStack::kInvalidGenID);
1093        const GrReducedClip* reduced = new (storage.get()) GrReducedClip(stack, bounds);
1094
1095        REPORTER_ASSERT(reporter, reduced->elements().count() == 1);
1096        // Clips will be cached based on the generation id. Make sure the gen id is valid.
1097        REPORTER_ASSERT(reporter, SkClipStack::kInvalidGenID != reduced->elementsGenID());
1098
1099        reduced->~GrReducedClip();
1100    }
1101    {
1102        SkClipStack stack;
1103
1104        // Create a clip with following 25.3, 25.3 boxes which are 25 apart:
1105        //  A  B
1106        //  C  D
1107
1108        stack.clipRect(SkRect::MakeXYWH(0, 0, SkScalar(25.3), SkScalar(25.3)), SkMatrix::I(),
1109                       kReplace_SkClipOp, true);
1110        uint32_t genIDA = stack.getTopmostGenID();
1111        stack.clipRect(SkRect::MakeXYWH(50, 0, SkScalar(25.3), SkScalar(25.3)), SkMatrix::I(),
1112                       kUnion_SkClipOp, true);
1113        uint32_t genIDB = stack.getTopmostGenID();
1114        stack.clipRect(SkRect::MakeXYWH(0, 50, SkScalar(25.3), SkScalar(25.3)), SkMatrix::I(),
1115                       kUnion_SkClipOp, true);
1116        uint32_t genIDC = stack.getTopmostGenID();
1117        stack.clipRect(SkRect::MakeXYWH(50, 50, SkScalar(25.3), SkScalar(25.3)), SkMatrix::I(),
1118                       kUnion_SkClipOp, true);
1119        uint32_t genIDD = stack.getTopmostGenID();
1120
1121
1122#define IXYWH SkIRect::MakeXYWH
1123#define XYWH SkRect::MakeXYWH
1124
1125        SkIRect stackBounds = IXYWH(0, 0, 76, 76);
1126
1127        // The base test is to test each rect in two ways:
1128        // 1) The box dimensions. (Should reduce to "all in", no elements).
1129        // 2) A bit over the box dimensions.
1130        // In the case 2, test that the generation id is what is expected.
1131        // The rects are of fractional size so that case 2 never gets optimized to an empty element
1132        // list.
1133
1134        // Not passing in tighter bounds is tested for consistency.
1135        static const struct SUPPRESS_VISIBILITY_WARNING {
1136            SkRect testBounds;
1137            int reducedClipCount;
1138            uint32_t reducedGenID;
1139            InitialState initialState;
1140            SkIRect clipIRect;
1141            // parameter.
1142        } testCases[] = {
1143
1144            // Rect A.
1145            { XYWH(0, 0, 25, 25), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllIn, IXYWH(0, 0, 25, 25) },
1146            { XYWH(0.1f, 0.1f, 25.1f, 25.1f), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllIn, IXYWH(0, 0, 26, 26) },
1147            { XYWH(0, 0, 27, 27), 1, genIDA, GrReducedClip::InitialState::kAllOut, IXYWH(0, 0, 27, 27)},
1148
1149            // Rect B.
1150            { XYWH(50, 0, 25, 25), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllIn, IXYWH(50, 0, 25, 25) },
1151            { XYWH(50, 0, 25.3f, 25.3f), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllIn, IXYWH(50, 0, 26, 26) },
1152            { XYWH(50, 0, 27, 27), 1, genIDB, GrReducedClip::InitialState::kAllOut, IXYWH(50, 0, 26, 27) },
1153
1154            // Rect C.
1155            { XYWH(0, 50, 25, 25), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllIn, IXYWH(0, 50, 25, 25) },
1156            { XYWH(0.2f, 50.1f, 25.1f, 25.2f), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllIn, IXYWH(0, 50, 26, 26) },
1157            { XYWH(0, 50, 27, 27), 1, genIDC, GrReducedClip::InitialState::kAllOut, IXYWH(0, 50, 27, 26) },
1158
1159            // Rect D.
1160            { XYWH(50, 50, 25, 25), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllIn, IXYWH(50, 50, 25, 25)},
1161            { XYWH(50.3f, 50.3f, 25, 25), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllIn, IXYWH(50, 50, 26, 26)},
1162            { XYWH(50, 50, 27, 27), 1, genIDD, GrReducedClip::InitialState::kAllOut,  IXYWH(50, 50, 26, 26)},
1163
1164            // Other tests:
1165            { XYWH(0, 0, 100, 100), 4, genIDD, GrReducedClip::InitialState::kAllOut, stackBounds },
1166
1167            // Rect in the middle, touches none.
1168            { XYWH(26, 26, 24, 24), 0, SkClipStack::kInvalidGenID, GrReducedClip::InitialState::kAllOut, IXYWH(26, 26, 24, 24) },
1169
1170            // Rect in the middle, touches all the rects. GenID is the last rect.
1171            { XYWH(24, 24, 27, 27), 4, genIDD, GrReducedClip::InitialState::kAllOut, IXYWH(24, 24, 27, 27) },
1172        };
1173
1174#undef XYWH
1175#undef IXYWH
1176
1177        for (size_t i = 0; i < SK_ARRAY_COUNT(testCases); ++i) {
1178            const GrReducedClip reduced(stack, testCases[i].testBounds);
1179            REPORTER_ASSERT(reporter, reduced.elements().count() == testCases[i].reducedClipCount);
1180            SkASSERT(reduced.elements().count() == testCases[i].reducedClipCount);
1181            if (reduced.elements().count()) {
1182                REPORTER_ASSERT(reporter, reduced.elementsGenID() == testCases[i].reducedGenID);
1183                SkASSERT(reduced.elementsGenID() == testCases[i].reducedGenID);
1184            }
1185            REPORTER_ASSERT(reporter, reduced.initialState() == testCases[i].initialState);
1186            SkASSERT(reduced.initialState() == testCases[i].initialState);
1187            REPORTER_ASSERT(reporter, reduced.hasIBounds());
1188            SkASSERT(reduced.hasIBounds());
1189            REPORTER_ASSERT(reporter, reduced.ibounds() == testCases[i].clipIRect);
1190            SkASSERT(reduced.ibounds() == testCases[i].clipIRect);
1191        }
1192    }
1193}
1194
1195static void test_reduced_clip_stack_no_aa_crash(skiatest::Reporter* reporter) {
1196    SkClipStack stack;
1197    stack.clipDevRect(SkIRect::MakeXYWH(0, 0, 100, 100), kReplace_SkClipOp);
1198    stack.clipDevRect(SkIRect::MakeXYWH(0, 0, 50, 50), kReplace_SkClipOp);
1199    SkRect bounds = SkRect::MakeXYWH(0, 0, 100, 100);
1200
1201    // At the time, this would crash.
1202    const GrReducedClip reduced(stack, bounds);
1203    REPORTER_ASSERT(reporter, reduced.elements().isEmpty());
1204}
1205
1206enum class ClipMethod {
1207    kSkipDraw,
1208    kIgnoreClip,
1209    kScissor,
1210    kAAElements
1211};
1212
1213static void test_aa_query(skiatest::Reporter* reporter, const SkString& testName,
1214                          const SkClipStack& stack, const SkMatrix& queryXform,
1215                          const SkRect& preXformQuery, ClipMethod expectedMethod,
1216                          int numExpectedElems = 0) {
1217    SkRect queryBounds;
1218    queryXform.mapRect(&queryBounds, preXformQuery);
1219    const GrReducedClip reduced(stack, queryBounds);
1220
1221    SkClipStack::BoundsType stackBoundsType;
1222    SkRect stackBounds;
1223    stack.getBounds(&stackBounds, &stackBoundsType);
1224
1225    switch (expectedMethod) {
1226        case ClipMethod::kSkipDraw:
1227            SkASSERT(0 == numExpectedElems);
1228            REPORTER_ASSERT_MESSAGE(reporter, reduced.elements().isEmpty(), testName.c_str());
1229            REPORTER_ASSERT_MESSAGE(reporter,
1230                                    GrReducedClip::InitialState::kAllOut == reduced.initialState(),
1231                                    testName.c_str());
1232            return;
1233        case ClipMethod::kIgnoreClip:
1234            SkASSERT(0 == numExpectedElems);
1235            REPORTER_ASSERT_MESSAGE(reporter,
1236                                    !reduced.hasIBounds() ||
1237                                    GrClip::IsInsideClip(reduced.ibounds(), queryBounds),
1238                                    testName.c_str());
1239            REPORTER_ASSERT_MESSAGE(reporter, reduced.elements().isEmpty(), testName.c_str());
1240            REPORTER_ASSERT_MESSAGE(reporter,
1241                                    GrReducedClip::InitialState::kAllIn == reduced.initialState(),
1242                                    testName.c_str());
1243            return;
1244        case ClipMethod::kScissor: {
1245            SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
1246            SkASSERT(0 == numExpectedElems);
1247            SkIRect expectedScissor;
1248            stackBounds.round(&expectedScissor);
1249            REPORTER_ASSERT_MESSAGE(reporter, reduced.elements().isEmpty(), testName.c_str());
1250            REPORTER_ASSERT_MESSAGE(reporter, reduced.hasIBounds(), testName.c_str());
1251            REPORTER_ASSERT_MESSAGE(reporter, expectedScissor == reduced.ibounds(),
1252                                    testName.c_str());
1253            REPORTER_ASSERT_MESSAGE(reporter,
1254                                    GrReducedClip::InitialState::kAllIn == reduced.initialState(),
1255                                    testName.c_str());
1256            return;
1257        }
1258        case ClipMethod::kAAElements: {
1259            SkIRect expectedClipIBounds = GrClip::GetPixelIBounds(queryBounds);
1260            if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
1261                SkAssertResult(expectedClipIBounds.intersect(GrClip::GetPixelIBounds(stackBounds)));
1262            }
1263            REPORTER_ASSERT_MESSAGE(reporter, numExpectedElems == reduced.elements().count(),
1264                                    testName.c_str());
1265            REPORTER_ASSERT_MESSAGE(reporter, reduced.hasIBounds(), testName.c_str());
1266            REPORTER_ASSERT_MESSAGE(reporter, expectedClipIBounds == reduced.ibounds(),
1267                                    testName.c_str());
1268            REPORTER_ASSERT_MESSAGE(reporter, reduced.requiresAA() == !reduced.elements().isEmpty(),
1269                                    testName.c_str());
1270            break;
1271        }
1272    }
1273}
1274
1275static void test_reduced_clip_stack_aa(skiatest::Reporter* reporter) {
1276    constexpr SkScalar IL = 2, IT = 1, IR = 6, IB = 7;         // Pixel aligned rect.
1277    constexpr SkScalar L = 2.2f, T = 1.7f, R = 5.8f, B = 7.3f; // Generic rect.
1278    constexpr SkScalar l = 3.3f, t = 2.8f, r = 4.7f, b = 6.2f; // Small rect contained in R.
1279
1280    SkRect alignedRect = {IL, IT, IR, IB};
1281    SkRect rect = {L, T, R, B};
1282    SkRect innerRect = {l, t, r, b};
1283
1284    SkMatrix m;
1285    m.setIdentity();
1286
1287    constexpr SkScalar kMinScale = 2.0001f;
1288    constexpr SkScalar kMaxScale = 3;
1289    constexpr int kNumIters = 8;
1290
1291    SkString name;
1292    SkRandom rand;
1293
1294    for (int i = 0; i < kNumIters; ++i) {
1295        // Pixel-aligned rect (iior=true).
1296        name.printf("Pixel-aligned rect test, iter %i", i);
1297        SkClipStack stack;
1298        stack.clipRect(alignedRect, SkMatrix::I(), kIntersect_SkClipOp, true);
1299        test_aa_query(reporter, name, stack, m, {IL, IT, IR, IB}, ClipMethod::kIgnoreClip);
1300        test_aa_query(reporter, name, stack, m, {IL, IT-1, IR, IT}, ClipMethod::kSkipDraw);
1301        test_aa_query(reporter, name, stack, m, {IL, IT-2, IR, IB}, ClipMethod::kScissor);
1302
1303        // Rect (iior=true).
1304        name.printf("Rect test, iter %i", i);
1305        stack.reset();
1306        stack.clipRect(rect, SkMatrix::I(), kIntersect_SkClipOp, true);
1307        test_aa_query(reporter, name, stack, m, {L, T,  R, B}, ClipMethod::kIgnoreClip);
1308        test_aa_query(reporter, name, stack, m, {L-.1f, T, L, B}, ClipMethod::kSkipDraw);
1309        test_aa_query(reporter, name, stack, m, {L-.1f, T, L+.1f, B}, ClipMethod::kAAElements, 1);
1310
1311        // Difference rect (iior=false, inside-out bounds).
1312        name.printf("Difference rect test, iter %i", i);
1313        stack.reset();
1314        stack.clipRect(rect, SkMatrix::I(), kDifference_SkClipOp, true);
1315        test_aa_query(reporter, name, stack, m, {L, T, R, B}, ClipMethod::kSkipDraw);
1316        test_aa_query(reporter, name, stack, m, {L, T-.1f, R, T}, ClipMethod::kIgnoreClip);
1317        test_aa_query(reporter, name, stack, m, {L, T-.1f, R, T+.1f}, ClipMethod::kAAElements, 1);
1318
1319        // Complex clip (iior=false, normal bounds).
1320        name.printf("Complex clip test, iter %i", i);
1321        stack.reset();
1322        stack.clipRect(rect, SkMatrix::I(), kIntersect_SkClipOp, true);
1323        stack.clipRect(innerRect, SkMatrix::I(), kXOR_SkClipOp, true);
1324        test_aa_query(reporter, name, stack, m, {l, t, r, b}, ClipMethod::kSkipDraw);
1325        test_aa_query(reporter, name, stack, m, {r-.1f, t, R, b}, ClipMethod::kAAElements, 1);
1326        test_aa_query(reporter, name, stack, m, {r-.1f, t, R+.1f, b}, ClipMethod::kAAElements, 2);
1327        test_aa_query(reporter, name, stack, m, {r, t, R+.1f, b}, ClipMethod::kAAElements, 1);
1328        test_aa_query(reporter, name, stack, m, {r, t, R, b}, ClipMethod::kIgnoreClip);
1329        test_aa_query(reporter, name, stack, m, {R, T, R+.1f, B}, ClipMethod::kSkipDraw);
1330
1331        // Complex clip where outer rect is pixel aligned (iior=false, normal bounds).
1332        name.printf("Aligned Complex clip test, iter %i", i);
1333        stack.reset();
1334        stack.clipRect(alignedRect, SkMatrix::I(), kIntersect_SkClipOp, true);
1335        stack.clipRect(innerRect, SkMatrix::I(), kXOR_SkClipOp, true);
1336        test_aa_query(reporter, name, stack, m, {l, t, r, b}, ClipMethod::kSkipDraw);
1337        test_aa_query(reporter, name, stack, m, {l, b-.1f, r, IB}, ClipMethod::kAAElements, 1);
1338        test_aa_query(reporter, name, stack, m, {l, b-.1f, r, IB+.1f}, ClipMethod::kAAElements, 1);
1339        test_aa_query(reporter, name, stack, m, {l, b, r, IB+.1f}, ClipMethod::kAAElements, 0);
1340        test_aa_query(reporter, name, stack, m, {l, b, r, IB}, ClipMethod::kIgnoreClip);
1341        test_aa_query(reporter, name, stack, m, {IL, IB, IR, IB+.1f}, ClipMethod::kSkipDraw);
1342
1343        // Apply random transforms and try again. This ensures the clip stack reduction is hardened
1344        // against FP rounding error.
1345        SkScalar sx = rand.nextRangeScalar(kMinScale, kMaxScale);
1346        sx = SkScalarFloorToScalar(sx * alignedRect.width()) / alignedRect.width();
1347        SkScalar sy = rand.nextRangeScalar(kMinScale, kMaxScale);
1348        sy = SkScalarFloorToScalar(sy * alignedRect.height()) / alignedRect.height();
1349        SkScalar tx = SkScalarRoundToScalar(sx * alignedRect.x()) - sx * alignedRect.x();
1350        SkScalar ty = SkScalarRoundToScalar(sy * alignedRect.y()) - sy * alignedRect.y();
1351
1352        SkMatrix xform = SkMatrix::MakeScale(sx, sy);
1353        xform.postTranslate(tx, ty);
1354        xform.mapRect(&alignedRect);
1355        xform.mapRect(&rect);
1356        xform.mapRect(&innerRect);
1357        m.postConcat(xform);
1358    }
1359}
1360
1361static void test_tiny_query_bounds_assertion_bug(skiatest::Reporter* reporter) {
1362    // https://bugs.chromium.org/p/skia/issues/detail?id=5990
1363    const SkRect clipBounds = SkRect::MakeXYWH(1.5f, 100, 1000, 1000);
1364
1365    SkClipStack rectStack;
1366    rectStack.clipRect(clipBounds, SkMatrix::I(), kIntersect_SkClipOp, true);
1367
1368    SkPath clipPath;
1369    clipPath.moveTo(clipBounds.left(), clipBounds.top());
1370    clipPath.quadTo(clipBounds.right(), clipBounds.top(),
1371                    clipBounds.right(), clipBounds.bottom());
1372    clipPath.quadTo(clipBounds.left(), clipBounds.bottom(),
1373                    clipBounds.left(), clipBounds.top());
1374    SkClipStack pathStack;
1375    pathStack.clipPath(clipPath, SkMatrix::I(), kIntersect_SkClipOp, true);
1376
1377    for (const SkClipStack& stack : {rectStack, pathStack}) {
1378        for (SkRect queryBounds : {SkRect::MakeXYWH(53, 60, GrClip::kBoundsTolerance, 1000),
1379                                   SkRect::MakeXYWH(53, 60, GrClip::kBoundsTolerance/2, 1000),
1380                                   SkRect::MakeXYWH(53, 160, 1000, GrClip::kBoundsTolerance),
1381                                   SkRect::MakeXYWH(53, 160, 1000, GrClip::kBoundsTolerance/2)}) {
1382            const GrReducedClip reduced(stack, queryBounds);
1383            REPORTER_ASSERT(reporter, !reduced.hasIBounds());
1384            REPORTER_ASSERT(reporter, reduced.elements().isEmpty());
1385            REPORTER_ASSERT(reporter,
1386                            GrReducedClip::InitialState::kAllOut == reduced.initialState());
1387        }
1388    }
1389}
1390
1391#endif
1392
1393DEF_TEST(ClipStack, reporter) {
1394    SkClipStack stack;
1395
1396    REPORTER_ASSERT(reporter, 0 == stack.getSaveCount());
1397    assert_count(reporter, stack, 0);
1398
1399    static const SkIRect gRects[] = {
1400        { 0, 0, 100, 100 },
1401        { 25, 25, 125, 125 },
1402        { 0, 0, 1000, 1000 },
1403        { 0, 0, 75, 75 }
1404    };
1405    for (size_t i = 0; i < SK_ARRAY_COUNT(gRects); i++) {
1406        stack.clipDevRect(gRects[i], kIntersect_SkClipOp);
1407    }
1408
1409    // all of the above rects should have been intersected, leaving only 1 rect
1410    SkClipStack::B2TIter iter(stack);
1411    const SkClipStack::Element* element = iter.next();
1412    SkRect answer;
1413    answer.iset(25, 25, 75, 75);
1414
1415    REPORTER_ASSERT(reporter, element);
1416    REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
1417    REPORTER_ASSERT(reporter, kIntersect_SkClipOp == element->getOp());
1418    REPORTER_ASSERT(reporter, element->getRect() == answer);
1419    // now check that we only had one in our iterator
1420    REPORTER_ASSERT(reporter, !iter.next());
1421
1422    stack.reset();
1423    REPORTER_ASSERT(reporter, 0 == stack.getSaveCount());
1424    assert_count(reporter, stack, 0);
1425
1426    test_assign_and_comparison(reporter);
1427    test_iterators(reporter);
1428    test_bounds(reporter, SkClipStack::Element::kRect_Type);
1429    test_bounds(reporter, SkClipStack::Element::kRRect_Type);
1430    test_bounds(reporter, SkClipStack::Element::kPath_Type);
1431    test_isWideOpen(reporter);
1432    test_rect_merging(reporter);
1433    test_rect_replace(reporter);
1434    test_rect_inverse_fill(reporter);
1435    test_path_replace(reporter);
1436    test_quickContains(reporter);
1437    test_invfill_diff_bug(reporter);
1438#if SK_SUPPORT_GPU
1439    test_reduced_clip_stack(reporter);
1440    test_reduced_clip_stack_genid(reporter);
1441    test_reduced_clip_stack_no_aa_crash(reporter);
1442    test_reduced_clip_stack_aa(reporter);
1443    test_tiny_query_bounds_assertion_bug(reporter);
1444#endif
1445}
1446
1447//////////////////////////////////////////////////////////////////////////////
1448
1449#if SK_SUPPORT_GPU
1450sk_sp<GrTextureProxy> GrClipStackClip::testingOnly_createClipMask(GrContext* context) const {
1451    const GrReducedClip reducedClip(*fStack, SkRect::MakeWH(512, 512), 0);
1452    return this->createSoftwareClipMask(context, reducedClip);
1453}
1454
1455// Verify that clip masks are freed up when the clip state that generated them goes away.
1456DEF_GPUTEST_FOR_ALL_CONTEXTS(ClipMaskCache, reporter, ctxInfo) {
1457    // This test uses resource key tags which only function in debug builds.
1458#ifdef SK_DEBUG
1459    GrContext* context = ctxInfo.grContext();
1460    SkClipStack stack;
1461
1462    SkPath path;
1463    path.addCircle(10, 10, 8);
1464    path.addCircle(15, 15, 8);
1465    path.setFillType(SkPath::kEvenOdd_FillType);
1466
1467    static const char* kTag = GrClipStackClip::kMaskTestTag;
1468    GrResourceCache* cache = context->getResourceCache();
1469
1470    static constexpr int kN = 5;
1471
1472    for (int i = 0; i < kN; ++i) {
1473        SkMatrix m;
1474        m.setTranslate(0.5, 0.5);
1475        stack.save();
1476        stack.clipPath(path, m, SkClipOp::kIntersect, true);
1477        sk_sp<GrTextureProxy> mask = GrClipStackClip(&stack).testingOnly_createClipMask(context);
1478        mask->instantiate(context->resourceProvider());
1479        GrTexture* tex = mask->priv().peekTexture();
1480        REPORTER_ASSERT(reporter, 0 == strcmp(tex->getUniqueKey().tag(), kTag));
1481        // Make sure mask isn't pinned in cache.
1482        mask.reset(nullptr);
1483        context->flush();
1484        REPORTER_ASSERT(reporter, i + 1 == cache->countUniqueKeysWithTag(kTag));
1485    }
1486
1487    for (int i = 0; i < kN; ++i) {
1488        stack.restore();
1489        cache->purgeAsNeeded();
1490        REPORTER_ASSERT(reporter, kN - (i + 1) == cache->countUniqueKeysWithTag(kTag));
1491    }
1492#endif
1493}
1494
1495#include "SkSurface.h"
1496DEF_GPUTEST_FOR_ALL_CONTEXTS(canvas_private_clipRgn, reporter, ctxInfo) {
1497    GrContext* context = ctxInfo.grContext();
1498
1499    const int w = 10;
1500    const int h = 10;
1501    SkImageInfo info = SkImageInfo::Make(w, h, kRGBA_8888_SkColorType, kPremul_SkAlphaType);
1502    sk_sp<SkSurface> surf = SkSurface::MakeRenderTarget(context, SkBudgeted::kNo, info);
1503    SkCanvas* canvas = surf->getCanvas();
1504    SkRegion rgn;
1505
1506    canvas->temporary_internal_getRgnClip(&rgn);
1507    REPORTER_ASSERT(reporter, rgn.isRect());
1508    REPORTER_ASSERT(reporter, rgn.getBounds() == SkIRect::MakeWH(w, h));
1509
1510    canvas->save();
1511    canvas->clipRect(SkRect::MakeWH(5, 5), kDifference_SkClipOp);
1512    canvas->temporary_internal_getRgnClip(&rgn);
1513    REPORTER_ASSERT(reporter, rgn.isComplex());
1514    REPORTER_ASSERT(reporter, rgn.getBounds() == SkIRect::MakeWH(w, h));
1515    canvas->restore();
1516
1517    canvas->save();
1518    canvas->clipRRect(SkRRect::MakeOval(SkRect::MakeLTRB(3, 3, 7, 7)));
1519    canvas->temporary_internal_getRgnClip(&rgn);
1520    REPORTER_ASSERT(reporter, rgn.isComplex());
1521    REPORTER_ASSERT(reporter, rgn.getBounds() == SkIRect::MakeLTRB(3, 3, 7, 7));
1522    canvas->restore();
1523}
1524#endif
1525