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 "SkCanvas.h"
9 #include "SkClipStack.h"
10 #include "SkPath.h"
11 #include "SkPathOps.h"
12 #include "SkClipOpPriv.h"
13 #include <atomic>
14 #include <new>
15 
16 #if SK_SUPPORT_GPU
17 #include "GrProxyProvider.h"
18 #endif
19 
Element(const Element & that)20 SkClipStack::Element::Element(const Element& that) {
21     switch (that.getDeviceSpaceType()) {
22         case DeviceSpaceType::kEmpty:
23             fDeviceSpaceRRect.setEmpty();
24             fDeviceSpacePath.reset();
25             break;
26         case DeviceSpaceType::kRect:  // Rect uses rrect
27         case DeviceSpaceType::kRRect:
28             fDeviceSpacePath.reset();
29             fDeviceSpaceRRect = that.fDeviceSpaceRRect;
30             break;
31         case DeviceSpaceType::kPath:
32             fDeviceSpacePath.set(that.getDeviceSpacePath());
33             break;
34     }
35 
36     fSaveCount = that.fSaveCount;
37     fOp = that.fOp;
38     fDeviceSpaceType = that.fDeviceSpaceType;
39     fDoAA = that.fDoAA;
40     fFiniteBoundType = that.fFiniteBoundType;
41     fFiniteBound = that.fFiniteBound;
42     fIsIntersectionOfRects = that.fIsIntersectionOfRects;
43     fGenID = that.fGenID;
44 }
45 
~Element()46 SkClipStack::Element::~Element() {
47 #if SK_SUPPORT_GPU
48     for (int i = 0; i < fKeysToInvalidate.count(); ++i) {
49         fProxyProvider->processInvalidUniqueKey(fKeysToInvalidate[i], nullptr,
50                                                 GrProxyProvider::InvalidateGPUResource::kYes);
51     }
52 #endif
53 }
54 
operator ==(const Element & element) const55 bool SkClipStack::Element::operator== (const Element& element) const {
56     if (this == &element) {
57         return true;
58     }
59     if (fOp != element.fOp || fDeviceSpaceType != element.fDeviceSpaceType ||
60         fDoAA != element.fDoAA || fSaveCount != element.fSaveCount) {
61         return false;
62     }
63     switch (fDeviceSpaceType) {
64         case DeviceSpaceType::kPath:
65             return this->getDeviceSpacePath() == element.getDeviceSpacePath();
66         case DeviceSpaceType::kRRect:
67             return fDeviceSpaceRRect == element.fDeviceSpaceRRect;
68         case DeviceSpaceType::kRect:
69             return this->getDeviceSpaceRect() == element.getDeviceSpaceRect();
70         case DeviceSpaceType::kEmpty:
71             return true;
72         default:
73             SkDEBUGFAIL("Unexpected type.");
74             return false;
75     }
76 }
77 
getBounds() const78 const SkRect& SkClipStack::Element::getBounds() const {
79     static const SkRect kEmpty = {0, 0, 0, 0};
80     switch (fDeviceSpaceType) {
81         case DeviceSpaceType::kRect:  // fallthrough
82         case DeviceSpaceType::kRRect:
83             return fDeviceSpaceRRect.getBounds();
84         case DeviceSpaceType::kPath:
85             return fDeviceSpacePath.get()->getBounds();
86         case DeviceSpaceType::kEmpty:
87             return kEmpty;
88         default:
89             SkDEBUGFAIL("Unexpected type.");
90             return kEmpty;
91     }
92 }
93 
contains(const SkRect & rect) const94 bool SkClipStack::Element::contains(const SkRect& rect) const {
95     switch (fDeviceSpaceType) {
96         case DeviceSpaceType::kRect:
97             return this->getDeviceSpaceRect().contains(rect);
98         case DeviceSpaceType::kRRect:
99             return fDeviceSpaceRRect.contains(rect);
100         case DeviceSpaceType::kPath:
101             return fDeviceSpacePath.get()->conservativelyContainsRect(rect);
102         case DeviceSpaceType::kEmpty:
103             return false;
104         default:
105             SkDEBUGFAIL("Unexpected type.");
106             return false;
107     }
108 }
109 
contains(const SkRRect & rrect) const110 bool SkClipStack::Element::contains(const SkRRect& rrect) const {
111     switch (fDeviceSpaceType) {
112         case DeviceSpaceType::kRect:
113             return this->getDeviceSpaceRect().contains(rrect.getBounds());
114         case DeviceSpaceType::kRRect:
115             // We don't currently have a generalized rrect-rrect containment.
116             return fDeviceSpaceRRect.contains(rrect.getBounds()) || rrect == fDeviceSpaceRRect;
117         case DeviceSpaceType::kPath:
118             return fDeviceSpacePath.get()->conservativelyContainsRect(rrect.getBounds());
119         case DeviceSpaceType::kEmpty:
120             return false;
121         default:
122             SkDEBUGFAIL("Unexpected type.");
123             return false;
124     }
125 }
126 
invertShapeFillType()127 void SkClipStack::Element::invertShapeFillType() {
128     switch (fDeviceSpaceType) {
129         case DeviceSpaceType::kRect:
130             fDeviceSpacePath.init();
131             fDeviceSpacePath.get()->addRect(this->getDeviceSpaceRect());
132             fDeviceSpacePath.get()->setFillType(SkPath::kInverseEvenOdd_FillType);
133             fDeviceSpaceType = DeviceSpaceType::kPath;
134             break;
135         case DeviceSpaceType::kRRect:
136             fDeviceSpacePath.init();
137             fDeviceSpacePath.get()->addRRect(fDeviceSpaceRRect);
138             fDeviceSpacePath.get()->setFillType(SkPath::kInverseEvenOdd_FillType);
139             fDeviceSpaceType = DeviceSpaceType::kPath;
140             break;
141         case DeviceSpaceType::kPath:
142             fDeviceSpacePath.get()->toggleInverseFillType();
143             break;
144         case DeviceSpaceType::kEmpty:
145             // Should this set to an empty, inverse filled path?
146             break;
147     }
148 }
149 
initCommon(int saveCount,SkClipOp op,bool doAA)150 void SkClipStack::Element::initCommon(int saveCount, SkClipOp op, bool doAA) {
151     fSaveCount = saveCount;
152     fOp = op;
153     fDoAA = doAA;
154     // A default of inside-out and empty bounds means the bounds are effectively void as it
155     // indicates that nothing is known to be outside the clip.
156     fFiniteBoundType = kInsideOut_BoundsType;
157     fFiniteBound.setEmpty();
158     fIsIntersectionOfRects = false;
159     fGenID = kInvalidGenID;
160 }
161 
initRect(int saveCount,const SkRect & rect,const SkMatrix & m,SkClipOp op,bool doAA)162 void SkClipStack::Element::initRect(int saveCount, const SkRect& rect, const SkMatrix& m,
163                                     SkClipOp op, bool doAA) {
164     if (m.rectStaysRect()) {
165         SkRect devRect;
166         m.mapRect(&devRect, rect);
167         fDeviceSpaceRRect.setRect(devRect);
168         fDeviceSpaceType = DeviceSpaceType::kRect;
169         this->initCommon(saveCount, op, doAA);
170         return;
171     }
172     SkPath path;
173     path.addRect(rect);
174     path.setIsVolatile(true);
175     this->initAsPath(saveCount, path, m, op, doAA);
176 }
177 
initRRect(int saveCount,const SkRRect & rrect,const SkMatrix & m,SkClipOp op,bool doAA)178 void SkClipStack::Element::initRRect(int saveCount, const SkRRect& rrect, const SkMatrix& m,
179                                      SkClipOp op, bool doAA) {
180     if (rrect.transform(m, &fDeviceSpaceRRect)) {
181         SkRRect::Type type = fDeviceSpaceRRect.getType();
182         if (SkRRect::kRect_Type == type || SkRRect::kEmpty_Type == type) {
183             fDeviceSpaceType = DeviceSpaceType::kRect;
184         } else {
185             fDeviceSpaceType = DeviceSpaceType::kRRect;
186         }
187         this->initCommon(saveCount, op, doAA);
188         return;
189     }
190     SkPath path;
191     path.addRRect(rrect);
192     path.setIsVolatile(true);
193     this->initAsPath(saveCount, path, m, op, doAA);
194 }
195 
initPath(int saveCount,const SkPath & path,const SkMatrix & m,SkClipOp op,bool doAA)196 void SkClipStack::Element::initPath(int saveCount, const SkPath& path, const SkMatrix& m,
197                                     SkClipOp op, bool doAA) {
198     if (!path.isInverseFillType()) {
199         SkRect r;
200         if (path.isRect(&r)) {
201             this->initRect(saveCount, r, m, op, doAA);
202             return;
203         }
204         SkRect ovalRect;
205         if (path.isOval(&ovalRect)) {
206             SkRRect rrect;
207             rrect.setOval(ovalRect);
208             this->initRRect(saveCount, rrect, m, op, doAA);
209             return;
210         }
211     }
212     this->initAsPath(saveCount, path, m, op, doAA);
213 }
214 
initAsPath(int saveCount,const SkPath & path,const SkMatrix & m,SkClipOp op,bool doAA)215 void SkClipStack::Element::initAsPath(int saveCount, const SkPath& path, const SkMatrix& m,
216                                       SkClipOp op, bool doAA) {
217     path.transform(m, fDeviceSpacePath.init());
218     fDeviceSpacePath.get()->setIsVolatile(true);
219     fDeviceSpaceType = DeviceSpaceType::kPath;
220     this->initCommon(saveCount, op, doAA);
221 }
222 
asDeviceSpacePath(SkPath * path) const223 void SkClipStack::Element::asDeviceSpacePath(SkPath* path) const {
224     switch (fDeviceSpaceType) {
225         case DeviceSpaceType::kEmpty:
226             path->reset();
227             break;
228         case DeviceSpaceType::kRect:
229             path->reset();
230             path->addRect(this->getDeviceSpaceRect());
231             break;
232         case DeviceSpaceType::kRRect:
233             path->reset();
234             path->addRRect(fDeviceSpaceRRect);
235             break;
236         case DeviceSpaceType::kPath:
237             *path = *fDeviceSpacePath.get();
238             break;
239     }
240     path->setIsVolatile(true);
241 }
242 
setEmpty()243 void SkClipStack::Element::setEmpty() {
244     fDeviceSpaceType = DeviceSpaceType::kEmpty;
245     fFiniteBound.setEmpty();
246     fFiniteBoundType = kNormal_BoundsType;
247     fIsIntersectionOfRects = false;
248     fDeviceSpaceRRect.setEmpty();
249     fDeviceSpacePath.reset();
250     fGenID = kEmptyGenID;
251     SkDEBUGCODE(this->checkEmpty();)
252 }
253 
checkEmpty() const254 void SkClipStack::Element::checkEmpty() const {
255     SkASSERT(fFiniteBound.isEmpty());
256     SkASSERT(kNormal_BoundsType == fFiniteBoundType);
257     SkASSERT(!fIsIntersectionOfRects);
258     SkASSERT(kEmptyGenID == fGenID);
259     SkASSERT(fDeviceSpaceRRect.isEmpty());
260     SkASSERT(!fDeviceSpacePath.isValid());
261 }
262 
canBeIntersectedInPlace(int saveCount,SkClipOp op) const263 bool SkClipStack::Element::canBeIntersectedInPlace(int saveCount, SkClipOp op) const {
264     if (DeviceSpaceType::kEmpty == fDeviceSpaceType &&
265         (kDifference_SkClipOp == op || kIntersect_SkClipOp == op)) {
266         return true;
267     }
268     // Only clips within the same save/restore frame (as captured by
269     // the save count) can be merged
270     return  fSaveCount == saveCount &&
271             kIntersect_SkClipOp == op &&
272             (kIntersect_SkClipOp == fOp || kReplace_SkClipOp == fOp);
273 }
274 
rectRectIntersectAllowed(const SkRect & newR,bool newAA) const275 bool SkClipStack::Element::rectRectIntersectAllowed(const SkRect& newR, bool newAA) const {
276     SkASSERT(DeviceSpaceType::kRect == fDeviceSpaceType);
277 
278     if (fDoAA == newAA) {
279         // if the AA setting is the same there is no issue
280         return true;
281     }
282 
283     if (!SkRect::Intersects(this->getDeviceSpaceRect(), newR)) {
284         // The calling code will correctly set the result to the empty clip
285         return true;
286     }
287 
288     if (this->getDeviceSpaceRect().contains(newR)) {
289         // if the new rect carves out a portion of the old one there is no
290         // issue
291         return true;
292     }
293 
294     // So either the two overlap in some complex manner or newR contains oldR.
295     // In the first, case the edges will require different AA. In the second,
296     // the AA setting that would be carried forward is incorrect (e.g., oldR
297     // is AA while newR is BW but since newR contains oldR, oldR will be
298     // drawn BW) since the new AA setting will predominate.
299     return false;
300 }
301 
302 // a mirror of combineBoundsRevDiff
combineBoundsDiff(FillCombo combination,const SkRect & prevFinite)303 void SkClipStack::Element::combineBoundsDiff(FillCombo combination, const SkRect& prevFinite) {
304     switch (combination) {
305         case kInvPrev_InvCur_FillCombo:
306             // In this case the only pixels that can remain set
307             // are inside the current clip rect since the extensions
308             // to infinity of both clips cancel out and whatever
309             // is outside of the current clip is removed
310             fFiniteBoundType = kNormal_BoundsType;
311             break;
312         case kInvPrev_Cur_FillCombo:
313             // In this case the current op is finite so the only pixels
314             // that aren't set are whatever isn't set in the previous
315             // clip and whatever this clip carves out
316             fFiniteBound.join(prevFinite);
317             fFiniteBoundType = kInsideOut_BoundsType;
318             break;
319         case kPrev_InvCur_FillCombo:
320             // In this case everything outside of this clip's bound
321             // is erased, so the only pixels that can remain set
322             // occur w/in the intersection of the two finite bounds
323             if (!fFiniteBound.intersect(prevFinite)) {
324                 fFiniteBound.setEmpty();
325                 fGenID = kEmptyGenID;
326             }
327             fFiniteBoundType = kNormal_BoundsType;
328             break;
329         case kPrev_Cur_FillCombo:
330             // The most conservative result bound is that of the
331             // prior clip. This could be wildly incorrect if the
332             // second clip either exactly matches the first clip
333             // (which should yield the empty set) or reduces the
334             // size of the prior bound (e.g., if the second clip
335             // exactly matched the bottom half of the prior clip).
336             // We ignore these two possibilities.
337             fFiniteBound = prevFinite;
338             break;
339         default:
340             SkDEBUGFAIL("SkClipStack::Element::combineBoundsDiff Invalid fill combination");
341             break;
342     }
343 }
344 
combineBoundsXOR(int combination,const SkRect & prevFinite)345 void SkClipStack::Element::combineBoundsXOR(int combination, const SkRect& prevFinite) {
346 
347     switch (combination) {
348         case kInvPrev_Cur_FillCombo:       // fall through
349         case kPrev_InvCur_FillCombo:
350             // With only one of the clips inverted the result will always
351             // extend to infinity. The only pixels that may be un-writeable
352             // lie within the union of the two finite bounds
353             fFiniteBound.join(prevFinite);
354             fFiniteBoundType = kInsideOut_BoundsType;
355             break;
356         case kInvPrev_InvCur_FillCombo:
357             // The only pixels that can survive are within the
358             // union of the two bounding boxes since the extensions
359             // to infinity of both clips cancel out
360             // fall through!
361         case kPrev_Cur_FillCombo:
362             // The most conservative bound for xor is the
363             // union of the two bounds. If the two clips exactly overlapped
364             // the xor could yield the empty set. Similarly the xor
365             // could reduce the size of the original clip's bound (e.g.,
366             // if the second clip exactly matched the bottom half of the
367             // first clip). We ignore these two cases.
368             fFiniteBound.join(prevFinite);
369             fFiniteBoundType = kNormal_BoundsType;
370             break;
371         default:
372             SkDEBUGFAIL("SkClipStack::Element::combineBoundsXOR Invalid fill combination");
373             break;
374     }
375 }
376 
377 // a mirror of combineBoundsIntersection
combineBoundsUnion(int combination,const SkRect & prevFinite)378 void SkClipStack::Element::combineBoundsUnion(int combination, const SkRect& prevFinite) {
379 
380     switch (combination) {
381         case kInvPrev_InvCur_FillCombo:
382             if (!fFiniteBound.intersect(prevFinite)) {
383                 fFiniteBound.setEmpty();
384                 fGenID = kWideOpenGenID;
385             }
386             fFiniteBoundType = kInsideOut_BoundsType;
387             break;
388         case kInvPrev_Cur_FillCombo:
389             // The only pixels that won't be drawable are inside
390             // the prior clip's finite bound
391             fFiniteBound = prevFinite;
392             fFiniteBoundType = kInsideOut_BoundsType;
393             break;
394         case kPrev_InvCur_FillCombo:
395             // The only pixels that won't be drawable are inside
396             // this clip's finite bound
397             break;
398         case kPrev_Cur_FillCombo:
399             fFiniteBound.join(prevFinite);
400             break;
401         default:
402             SkDEBUGFAIL("SkClipStack::Element::combineBoundsUnion Invalid fill combination");
403             break;
404     }
405 }
406 
407 // a mirror of combineBoundsUnion
combineBoundsIntersection(int combination,const SkRect & prevFinite)408 void SkClipStack::Element::combineBoundsIntersection(int combination, const SkRect& prevFinite) {
409 
410     switch (combination) {
411         case kInvPrev_InvCur_FillCombo:
412             // The only pixels that aren't writable in this case
413             // occur in the union of the two finite bounds
414             fFiniteBound.join(prevFinite);
415             fFiniteBoundType = kInsideOut_BoundsType;
416             break;
417         case kInvPrev_Cur_FillCombo:
418             // In this case the only pixels that will remain writeable
419             // are within the current clip
420             break;
421         case kPrev_InvCur_FillCombo:
422             // In this case the only pixels that will remain writeable
423             // are with the previous clip
424             fFiniteBound = prevFinite;
425             fFiniteBoundType = kNormal_BoundsType;
426             break;
427         case kPrev_Cur_FillCombo:
428             if (!fFiniteBound.intersect(prevFinite)) {
429                 this->setEmpty();
430             }
431             break;
432         default:
433             SkDEBUGFAIL("SkClipStack::Element::combineBoundsIntersection Invalid fill combination");
434             break;
435     }
436 }
437 
438 // a mirror of combineBoundsDiff
combineBoundsRevDiff(int combination,const SkRect & prevFinite)439 void SkClipStack::Element::combineBoundsRevDiff(int combination, const SkRect& prevFinite) {
440 
441     switch (combination) {
442         case kInvPrev_InvCur_FillCombo:
443             // The only pixels that can survive are in the
444             // previous bound since the extensions to infinity in
445             // both clips cancel out
446             fFiniteBound = prevFinite;
447             fFiniteBoundType = kNormal_BoundsType;
448             break;
449         case kInvPrev_Cur_FillCombo:
450             if (!fFiniteBound.intersect(prevFinite)) {
451                 this->setEmpty();
452             } else {
453                 fFiniteBoundType = kNormal_BoundsType;
454             }
455             break;
456         case kPrev_InvCur_FillCombo:
457             fFiniteBound.join(prevFinite);
458             fFiniteBoundType = kInsideOut_BoundsType;
459             break;
460         case kPrev_Cur_FillCombo:
461             // Fall through - as with the kDifference_Op case, the
462             // most conservative result bound is the bound of the
463             // current clip. The prior clip could reduce the size of this
464             // bound (as in the kDifference_Op case) but we are ignoring
465             // those cases.
466             break;
467         default:
468             SkDEBUGFAIL("SkClipStack::Element::combineBoundsRevDiff Invalid fill combination");
469             break;
470     }
471 }
472 
updateBoundAndGenID(const Element * prior)473 void SkClipStack::Element::updateBoundAndGenID(const Element* prior) {
474     // We set this first here but we may overwrite it later if we determine that the clip is
475     // either wide-open or empty.
476     fGenID = GetNextGenID();
477 
478     // First, optimistically update the current Element's bound information
479     // with the current clip's bound
480     fIsIntersectionOfRects = false;
481     switch (fDeviceSpaceType) {
482         case DeviceSpaceType::kRect:
483             fFiniteBound = this->getDeviceSpaceRect();
484             fFiniteBoundType = kNormal_BoundsType;
485 
486             if (kReplace_SkClipOp == fOp || (kIntersect_SkClipOp == fOp && nullptr == prior) ||
487                 (kIntersect_SkClipOp == fOp && prior->fIsIntersectionOfRects &&
488                  prior->rectRectIntersectAllowed(this->getDeviceSpaceRect(), fDoAA))) {
489                 fIsIntersectionOfRects = true;
490             }
491             break;
492         case DeviceSpaceType::kRRect:
493             fFiniteBound = fDeviceSpaceRRect.getBounds();
494             fFiniteBoundType = kNormal_BoundsType;
495             break;
496         case DeviceSpaceType::kPath:
497             fFiniteBound = fDeviceSpacePath.get()->getBounds();
498 
499             if (fDeviceSpacePath.get()->isInverseFillType()) {
500                 fFiniteBoundType = kInsideOut_BoundsType;
501             } else {
502                 fFiniteBoundType = kNormal_BoundsType;
503             }
504             break;
505         case DeviceSpaceType::kEmpty:
506             SkDEBUGFAIL("We shouldn't get here with an empty element.");
507             break;
508     }
509 
510     // Now determine the previous Element's bound information taking into
511     // account that there may be no previous clip
512     SkRect prevFinite;
513     SkClipStack::BoundsType prevType;
514 
515     if (nullptr == prior) {
516         // no prior clip means the entire plane is writable
517         prevFinite.setEmpty();   // there are no pixels that cannot be drawn to
518         prevType = kInsideOut_BoundsType;
519     } else {
520         prevFinite = prior->fFiniteBound;
521         prevType = prior->fFiniteBoundType;
522     }
523 
524     FillCombo combination = kPrev_Cur_FillCombo;
525     if (kInsideOut_BoundsType == fFiniteBoundType) {
526         combination = (FillCombo) (combination | 0x01);
527     }
528     if (kInsideOut_BoundsType == prevType) {
529         combination = (FillCombo) (combination | 0x02);
530     }
531 
532     SkASSERT(kInvPrev_InvCur_FillCombo == combination ||
533                 kInvPrev_Cur_FillCombo == combination ||
534                 kPrev_InvCur_FillCombo == combination ||
535                 kPrev_Cur_FillCombo == combination);
536 
537     // Now integrate with clip with the prior clips
538     switch (fOp) {
539         case kDifference_SkClipOp:
540             this->combineBoundsDiff(combination, prevFinite);
541             break;
542         case kXOR_SkClipOp:
543             this->combineBoundsXOR(combination, prevFinite);
544             break;
545         case kUnion_SkClipOp:
546             this->combineBoundsUnion(combination, prevFinite);
547             break;
548         case kIntersect_SkClipOp:
549             this->combineBoundsIntersection(combination, prevFinite);
550             break;
551         case kReverseDifference_SkClipOp:
552             this->combineBoundsRevDiff(combination, prevFinite);
553             break;
554         case kReplace_SkClipOp:
555             // Replace just ignores everything prior
556             // The current clip's bound information is already filled in
557             // so nothing to do
558             break;
559         default:
560             SkDebugf("SkClipOp error\n");
561             SkASSERT(0);
562             break;
563     }
564 }
565 
566 // This constant determines how many Element's are allocated together as a block in
567 // the deque. As such it needs to balance allocating too much memory vs.
568 // incurring allocation/deallocation thrashing. It should roughly correspond to
569 // the deepest save/restore stack we expect to see.
570 static const int kDefaultElementAllocCnt = 8;
571 
SkClipStack()572 SkClipStack::SkClipStack()
573     : fDeque(sizeof(Element), kDefaultElementAllocCnt)
574     , fSaveCount(0) {
575 }
576 
SkClipStack(void * storage,size_t size)577 SkClipStack::SkClipStack(void* storage, size_t size)
578     : fDeque(sizeof(Element), storage, size, kDefaultElementAllocCnt)
579     , fSaveCount(0) {
580 }
581 
SkClipStack(const SkClipStack & b)582 SkClipStack::SkClipStack(const SkClipStack& b)
583     : fDeque(sizeof(Element), kDefaultElementAllocCnt) {
584     *this = b;
585 }
586 
~SkClipStack()587 SkClipStack::~SkClipStack() {
588     reset();
589 }
590 
operator =(const SkClipStack & b)591 SkClipStack& SkClipStack::operator=(const SkClipStack& b) {
592     if (this == &b) {
593         return *this;
594     }
595     reset();
596 
597     fSaveCount = b.fSaveCount;
598     SkDeque::F2BIter recIter(b.fDeque);
599     for (const Element* element = (const Element*)recIter.next();
600          element != nullptr;
601          element = (const Element*)recIter.next()) {
602         new (fDeque.push_back()) Element(*element);
603     }
604 
605     return *this;
606 }
607 
operator ==(const SkClipStack & b) const608 bool SkClipStack::operator==(const SkClipStack& b) const {
609     if (this->getTopmostGenID() == b.getTopmostGenID()) {
610         return true;
611     }
612     if (fSaveCount != b.fSaveCount ||
613         fDeque.count() != b.fDeque.count()) {
614         return false;
615     }
616     SkDeque::F2BIter myIter(fDeque);
617     SkDeque::F2BIter bIter(b.fDeque);
618     const Element* myElement = (const Element*)myIter.next();
619     const Element* bElement = (const Element*)bIter.next();
620 
621     while (myElement != nullptr && bElement != nullptr) {
622         if (*myElement != *bElement) {
623             return false;
624         }
625         myElement = (const Element*)myIter.next();
626         bElement = (const Element*)bIter.next();
627     }
628     return myElement == nullptr && bElement == nullptr;
629 }
630 
reset()631 void SkClipStack::reset() {
632     // We used a placement new for each object in fDeque, so we're responsible
633     // for calling the destructor on each of them as well.
634     while (!fDeque.empty()) {
635         Element* element = (Element*)fDeque.back();
636         element->~Element();
637         fDeque.pop_back();
638     }
639 
640     fSaveCount = 0;
641 }
642 
save()643 void SkClipStack::save() {
644     fSaveCount += 1;
645 }
646 
restore()647 void SkClipStack::restore() {
648     fSaveCount -= 1;
649     restoreTo(fSaveCount);
650 }
651 
restoreTo(int saveCount)652 void SkClipStack::restoreTo(int saveCount) {
653     while (!fDeque.empty()) {
654         Element* element = (Element*)fDeque.back();
655         if (element->fSaveCount <= saveCount) {
656             break;
657         }
658         element->~Element();
659         fDeque.pop_back();
660     }
661 }
662 
bounds(const SkIRect & deviceBounds) const663 SkRect SkClipStack::bounds(const SkIRect& deviceBounds) const {
664     // TODO: optimize this.
665     SkRect r;
666     SkClipStack::BoundsType bounds;
667     this->getBounds(&r, &bounds);
668     if (bounds == SkClipStack::kInsideOut_BoundsType) {
669         return SkRect::Make(deviceBounds);
670     }
671     return r.intersect(SkRect::Make(deviceBounds)) ? r : SkRect::MakeEmpty();
672 }
673 
674 // TODO: optimize this.
isEmpty(const SkIRect & r) const675 bool SkClipStack::isEmpty(const SkIRect& r) const { return this->bounds(r).isEmpty(); }
676 
getBounds(SkRect * canvFiniteBound,BoundsType * boundType,bool * isIntersectionOfRects) const677 void SkClipStack::getBounds(SkRect* canvFiniteBound,
678                             BoundsType* boundType,
679                             bool* isIntersectionOfRects) const {
680     SkASSERT(canvFiniteBound && boundType);
681 
682     Element* element = (Element*)fDeque.back();
683 
684     if (nullptr == element) {
685         // the clip is wide open - the infinite plane w/ no pixels un-writeable
686         canvFiniteBound->setEmpty();
687         *boundType = kInsideOut_BoundsType;
688         if (isIntersectionOfRects) {
689             *isIntersectionOfRects = false;
690         }
691         return;
692     }
693 
694     *canvFiniteBound = element->fFiniteBound;
695     *boundType = element->fFiniteBoundType;
696     if (isIntersectionOfRects) {
697         *isIntersectionOfRects = element->fIsIntersectionOfRects;
698     }
699 }
700 
internalQuickContains(const SkRect & rect) const701 bool SkClipStack::internalQuickContains(const SkRect& rect) const {
702 
703     Iter iter(*this, Iter::kTop_IterStart);
704     const Element* element = iter.prev();
705     while (element != nullptr) {
706         if (kIntersect_SkClipOp != element->getOp() && kReplace_SkClipOp != element->getOp())
707             return false;
708         if (element->isInverseFilled()) {
709             // Part of 'rect' could be trimmed off by the inverse-filled clip element
710             if (SkRect::Intersects(element->getBounds(), rect)) {
711                 return false;
712             }
713         } else {
714             if (!element->contains(rect)) {
715                 return false;
716             }
717         }
718         if (kReplace_SkClipOp == element->getOp()) {
719             break;
720         }
721         element = iter.prev();
722     }
723     return true;
724 }
725 
internalQuickContains(const SkRRect & rrect) const726 bool SkClipStack::internalQuickContains(const SkRRect& rrect) const {
727 
728     Iter iter(*this, Iter::kTop_IterStart);
729     const Element* element = iter.prev();
730     while (element != nullptr) {
731         if (kIntersect_SkClipOp != element->getOp() && kReplace_SkClipOp != element->getOp())
732             return false;
733         if (element->isInverseFilled()) {
734             // Part of 'rrect' could be trimmed off by the inverse-filled clip element
735             if (SkRect::Intersects(element->getBounds(), rrect.getBounds())) {
736                 return false;
737             }
738         } else {
739             if (!element->contains(rrect)) {
740                 return false;
741             }
742         }
743         if (kReplace_SkClipOp == element->getOp()) {
744             break;
745         }
746         element = iter.prev();
747     }
748     return true;
749 }
750 
asPath(SkPath * path) const751 bool SkClipStack::asPath(SkPath *path) const {
752     bool isAA = false;
753 
754     path->reset();
755     path->setFillType(SkPath::kInverseEvenOdd_FillType);
756 
757     SkClipStack::Iter iter(*this, SkClipStack::Iter::kBottom_IterStart);
758     while (const SkClipStack::Element* element = iter.next()) {
759         SkPath operand;
760         if (element->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kEmpty) {
761             element->asDeviceSpacePath(&operand);
762         }
763 
764         SkClipOp elementOp = element->getOp();
765         if (elementOp == kReplace_SkClipOp) {
766             *path = operand;
767         } else {
768             Op(*path, operand, (SkPathOp)elementOp, path);
769         }
770 
771         // if the prev and curr clips disagree about aa -vs- not, favor the aa request.
772         // perhaps we need an API change to avoid this sort of mixed-signals about
773         // clipping.
774         isAA = (isAA || element->isAA());
775     }
776 
777     return isAA;
778 }
779 
pushElement(const Element & element)780 void SkClipStack::pushElement(const Element& element) {
781     // Use reverse iterator instead of back because Rect path may need previous
782     SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart);
783     Element* prior = (Element*) iter.prev();
784 
785     if (prior) {
786         if (prior->canBeIntersectedInPlace(fSaveCount, element.getOp())) {
787             switch (prior->fDeviceSpaceType) {
788                 case Element::DeviceSpaceType::kEmpty:
789                     SkDEBUGCODE(prior->checkEmpty();)
790                     return;
791                 case Element::DeviceSpaceType::kRect:
792                     if (Element::DeviceSpaceType::kRect == element.getDeviceSpaceType()) {
793                         if (prior->rectRectIntersectAllowed(element.getDeviceSpaceRect(),
794                                                             element.isAA())) {
795                             SkRect isectRect;
796                             if (!isectRect.intersect(prior->getDeviceSpaceRect(),
797                                                      element.getDeviceSpaceRect())) {
798                                 prior->setEmpty();
799                                 return;
800                             }
801 
802                             prior->fDeviceSpaceRRect.setRect(isectRect);
803                             prior->fDoAA = element.isAA();
804                             Element* priorPrior = (Element*) iter.prev();
805                             prior->updateBoundAndGenID(priorPrior);
806                             return;
807                         }
808                         break;
809                     }
810                     // fallthrough
811                 default:
812                     if (!SkRect::Intersects(prior->getBounds(), element.getBounds())) {
813                         prior->setEmpty();
814                         return;
815                     }
816                     break;
817             }
818         } else if (kReplace_SkClipOp == element.getOp()) {
819             this->restoreTo(fSaveCount - 1);
820             prior = (Element*) fDeque.back();
821         }
822     }
823     Element* newElement = new (fDeque.push_back()) Element(element);
824     newElement->updateBoundAndGenID(prior);
825 }
826 
clipRRect(const SkRRect & rrect,const SkMatrix & matrix,SkClipOp op,bool doAA)827 void SkClipStack::clipRRect(const SkRRect& rrect, const SkMatrix& matrix, SkClipOp op,
828                             bool doAA) {
829     Element element(fSaveCount, rrect, matrix, op, doAA);
830     this->pushElement(element);
831     if (this->hasClipRestriction(op)) {
832         Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp,
833                             false);
834         this->pushElement(restriction);
835     }
836 }
837 
clipRect(const SkRect & rect,const SkMatrix & matrix,SkClipOp op,bool doAA)838 void SkClipStack::clipRect(const SkRect& rect, const SkMatrix& matrix, SkClipOp op,
839                            bool doAA) {
840     Element element(fSaveCount, rect, matrix, op, doAA);
841     this->pushElement(element);
842     if (this->hasClipRestriction(op)) {
843         Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp,
844                             false);
845         this->pushElement(restriction);
846     }
847 }
848 
clipPath(const SkPath & path,const SkMatrix & matrix,SkClipOp op,bool doAA)849 void SkClipStack::clipPath(const SkPath& path, const SkMatrix& matrix, SkClipOp op,
850                            bool doAA) {
851     Element element(fSaveCount, path, matrix, op, doAA);
852     this->pushElement(element);
853     if (this->hasClipRestriction(op)) {
854         Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp,
855                             false);
856         this->pushElement(restriction);
857     }
858 }
859 
clipEmpty()860 void SkClipStack::clipEmpty() {
861     Element* element = (Element*) fDeque.back();
862 
863     if (element && element->canBeIntersectedInPlace(fSaveCount, kIntersect_SkClipOp)) {
864         element->setEmpty();
865     }
866     new (fDeque.push_back()) Element(fSaveCount);
867 
868     ((Element*)fDeque.back())->fGenID = kEmptyGenID;
869 }
870 
871 ///////////////////////////////////////////////////////////////////////////////
872 
Iter()873 SkClipStack::Iter::Iter() : fStack(nullptr) {
874 }
875 
Iter(const SkClipStack & stack,IterStart startLoc)876 SkClipStack::Iter::Iter(const SkClipStack& stack, IterStart startLoc)
877     : fStack(&stack) {
878     this->reset(stack, startLoc);
879 }
880 
next()881 const SkClipStack::Element* SkClipStack::Iter::next() {
882     return (const SkClipStack::Element*)fIter.next();
883 }
884 
prev()885 const SkClipStack::Element* SkClipStack::Iter::prev() {
886     return (const SkClipStack::Element*)fIter.prev();
887 }
888 
skipToTopmost(SkClipOp op)889 const SkClipStack::Element* SkClipStack::Iter::skipToTopmost(SkClipOp op) {
890 
891     if (nullptr == fStack) {
892         return nullptr;
893     }
894 
895     fIter.reset(fStack->fDeque, SkDeque::Iter::kBack_IterStart);
896 
897     const SkClipStack::Element* element = nullptr;
898 
899     for (element = (const SkClipStack::Element*) fIter.prev();
900          element;
901          element = (const SkClipStack::Element*) fIter.prev()) {
902 
903         if (op == element->fOp) {
904             // The Deque's iterator is actually one pace ahead of the
905             // returned value. So while "element" is the element we want to
906             // return, the iterator is actually pointing at (and will
907             // return on the next "next" or "prev" call) the element
908             // in front of it in the deque. Bump the iterator forward a
909             // step so we get the expected result.
910             if (nullptr == fIter.next()) {
911                 // The reverse iterator has run off the front of the deque
912                 // (i.e., the "op" clip is the first clip) and can't
913                 // recover. Reset the iterator to start at the front.
914                 fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart);
915             }
916             break;
917         }
918     }
919 
920     if (nullptr == element) {
921         // There were no "op" clips
922         fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart);
923     }
924 
925     return this->next();
926 }
927 
reset(const SkClipStack & stack,IterStart startLoc)928 void SkClipStack::Iter::reset(const SkClipStack& stack, IterStart startLoc) {
929     fStack = &stack;
930     fIter.reset(stack.fDeque, static_cast<SkDeque::Iter::IterStart>(startLoc));
931 }
932 
933 // helper method
getConservativeBounds(int offsetX,int offsetY,int maxWidth,int maxHeight,SkRect * devBounds,bool * isIntersectionOfRects) const934 void SkClipStack::getConservativeBounds(int offsetX,
935                                         int offsetY,
936                                         int maxWidth,
937                                         int maxHeight,
938                                         SkRect* devBounds,
939                                         bool* isIntersectionOfRects) const {
940     SkASSERT(devBounds);
941 
942     devBounds->setLTRB(0, 0,
943                        SkIntToScalar(maxWidth), SkIntToScalar(maxHeight));
944 
945     SkRect temp;
946     SkClipStack::BoundsType boundType;
947 
948     // temp starts off in canvas space here
949     this->getBounds(&temp, &boundType, isIntersectionOfRects);
950     if (SkClipStack::kInsideOut_BoundsType == boundType) {
951         return;
952     }
953 
954     // but is converted to device space here
955     temp.offset(SkIntToScalar(offsetX), SkIntToScalar(offsetY));
956 
957     if (!devBounds->intersect(temp)) {
958         devBounds->setEmpty();
959     }
960 }
961 
isRRect(const SkRect & bounds,SkRRect * rrect,bool * aa) const962 bool SkClipStack::isRRect(const SkRect& bounds, SkRRect* rrect, bool* aa) const {
963     // We limit to 5 elements. This means the back element will be bounds checked at most 4 times if
964     // it is an rrect.
965     int cnt = fDeque.count();
966     if (!cnt || cnt > 5) {
967         return false;
968     }
969     const Element* back = static_cast<const Element*>(fDeque.back());
970     if (back->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kRect &&
971         back->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kRRect) {
972         return false;
973     }
974     if (back->getOp() == kReplace_SkClipOp) {
975         *rrect = back->asDeviceSpaceRRect();
976         *aa = back->isAA();
977         return true;
978     }
979 
980     if (back->getOp() == kIntersect_SkClipOp) {
981         SkRect backBounds;
982         if (!backBounds.intersect(bounds, back->asDeviceSpaceRRect().rect())) {
983             return false;
984         }
985         if (cnt > 1) {
986             SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart);
987             SkAssertResult(static_cast<const Element*>(iter.prev()) == back);
988             while (const Element* prior = (const Element*)iter.prev()) {
989                 if ((prior->getOp() != kIntersect_SkClipOp &&
990                      prior->getOp() != kReplace_SkClipOp) ||
991                     !prior->contains(backBounds)) {
992                     return false;
993                 }
994                 if (prior->getOp() == kReplace_SkClipOp) {
995                     break;
996                 }
997             }
998         }
999         *rrect = back->asDeviceSpaceRRect();
1000         *aa = back->isAA();
1001         return true;
1002     }
1003     return false;
1004 }
1005 
GetNextGenID()1006 uint32_t SkClipStack::GetNextGenID() {
1007     // 0-2 are reserved for invalid, empty & wide-open
1008     static const uint32_t kFirstUnreservedGenID = 3;
1009     static std::atomic<uint32_t> nextID{kFirstUnreservedGenID};
1010 
1011     uint32_t id;
1012     do {
1013         id = nextID++;
1014     } while (id < kFirstUnreservedGenID);
1015     return id;
1016 }
1017 
getTopmostGenID() const1018 uint32_t SkClipStack::getTopmostGenID() const {
1019     if (fDeque.empty()) {
1020         return kWideOpenGenID;
1021     }
1022 
1023     const Element* back = static_cast<const Element*>(fDeque.back());
1024     if (kInsideOut_BoundsType == back->fFiniteBoundType && back->fFiniteBound.isEmpty()) {
1025         return kWideOpenGenID;
1026     }
1027 
1028     return back->getGenID();
1029 }
1030 
1031 #ifdef SK_DEBUG
dump() const1032 void SkClipStack::Element::dump() const {
1033     static const char* kTypeStrings[] = {
1034         "empty",
1035         "rect",
1036         "rrect",
1037         "path"
1038     };
1039     static_assert(0 == static_cast<int>(DeviceSpaceType::kEmpty), "enum mismatch");
1040     static_assert(1 == static_cast<int>(DeviceSpaceType::kRect), "enum mismatch");
1041     static_assert(2 == static_cast<int>(DeviceSpaceType::kRRect), "enum mismatch");
1042     static_assert(3 == static_cast<int>(DeviceSpaceType::kPath), "enum mismatch");
1043     static_assert(SK_ARRAY_COUNT(kTypeStrings) == kTypeCnt, "enum mismatch");
1044 
1045     static const char* kOpStrings[] = {
1046         "difference",
1047         "intersect",
1048         "union",
1049         "xor",
1050         "reverse-difference",
1051         "replace",
1052     };
1053     static_assert(0 == static_cast<int>(kDifference_SkClipOp), "enum mismatch");
1054     static_assert(1 == static_cast<int>(kIntersect_SkClipOp), "enum mismatch");
1055     static_assert(2 == static_cast<int>(kUnion_SkClipOp), "enum mismatch");
1056     static_assert(3 == static_cast<int>(kXOR_SkClipOp), "enum mismatch");
1057     static_assert(4 == static_cast<int>(kReverseDifference_SkClipOp), "enum mismatch");
1058     static_assert(5 == static_cast<int>(kReplace_SkClipOp), "enum mismatch");
1059     static_assert(SK_ARRAY_COUNT(kOpStrings) == SkRegion::kOpCnt, "enum mismatch");
1060 
1061     SkDebugf("Type: %s, Op: %s, AA: %s, Save Count: %d\n", kTypeStrings[(int)fDeviceSpaceType],
1062              kOpStrings[static_cast<int>(fOp)], (fDoAA ? "yes" : "no"), fSaveCount);
1063     switch (fDeviceSpaceType) {
1064         case DeviceSpaceType::kEmpty:
1065             SkDebugf("\n");
1066             break;
1067         case DeviceSpaceType::kRect:
1068             this->getDeviceSpaceRect().dump();
1069             SkDebugf("\n");
1070             break;
1071         case DeviceSpaceType::kRRect:
1072             this->getDeviceSpaceRRect().dump();
1073             SkDebugf("\n");
1074             break;
1075         case DeviceSpaceType::kPath:
1076             this->getDeviceSpacePath().dump(nullptr, true, false);
1077             break;
1078     }
1079 }
1080 
dump() const1081 void SkClipStack::dump() const {
1082     B2TIter iter(*this);
1083     const Element* e;
1084     while ((e = iter.next())) {
1085         e->dump();
1086         SkDebugf("\n");
1087     }
1088 }
1089 #endif
1090