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