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