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