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