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