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