michael@0: 
michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkClipStack.h"
michael@0: #include "SkPath.h"
michael@0: #include "SkThread.h"
michael@0: 
michael@0: #include <new>
michael@0: 
michael@0: 
michael@0: // 0-2 are reserved for invalid, empty & wide-open
michael@0: static const int32_t kFirstUnreservedGenID = 3;
michael@0: int32_t SkClipStack::gGenID = kFirstUnreservedGenID;
michael@0: 
michael@0: SkClipStack::Element::Element(const Element& that) {
michael@0:     switch (that.getType()) {
michael@0:         case kEmpty_Type:
michael@0:             fPath.reset();
michael@0:             break;
michael@0:         case kRect_Type: // Rect uses rrect
michael@0:         case kRRect_Type:
michael@0:             fPath.reset();
michael@0:             fRRect = that.fRRect;
michael@0:             break;
michael@0:         case kPath_Type:
michael@0:             fPath.set(that.getPath());
michael@0:             break;
michael@0:     }
michael@0: 
michael@0:     fSaveCount = that.fSaveCount;
michael@0:     fOp = that.fOp;
michael@0:     fType = that.fType;
michael@0:     fDoAA = that.fDoAA;
michael@0:     fFiniteBoundType = that.fFiniteBoundType;
michael@0:     fFiniteBound = that.fFiniteBound;
michael@0:     fIsIntersectionOfRects = that.fIsIntersectionOfRects;
michael@0:     fGenID = that.fGenID;
michael@0: }
michael@0: 
michael@0: bool SkClipStack::Element::operator== (const Element& element) const {
michael@0:     if (this == &element) {
michael@0:         return true;
michael@0:     }
michael@0:     if (fOp != element.fOp ||
michael@0:         fType != element.fType ||
michael@0:         fDoAA != element.fDoAA ||
michael@0:         fSaveCount != element.fSaveCount) {
michael@0:         return false;
michael@0:     }
michael@0:     switch (fType) {
michael@0:         case kPath_Type:
michael@0:             return this->getPath() == element.getPath();
michael@0:         case kRRect_Type:
michael@0:             return fRRect == element.fRRect;
michael@0:         case kRect_Type:
michael@0:             return this->getRect() == element.getRect();
michael@0:         case kEmpty_Type:
michael@0:             return true;
michael@0:         default:
michael@0:             SkDEBUGFAIL("Unexpected type.");
michael@0:             return false;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkClipStack::Element::invertShapeFillType() {
michael@0:     switch (fType) {
michael@0:         case kRect_Type:
michael@0:             fPath.init();
michael@0:             fPath.get()->addRect(this->getRect());
michael@0:             fPath.get()->setFillType(SkPath::kInverseEvenOdd_FillType);
michael@0:             fType = kPath_Type;
michael@0:             break;
michael@0:         case kRRect_Type:
michael@0:             fPath.init();
michael@0:             fPath.get()->addRRect(fRRect);
michael@0:             fPath.get()->setFillType(SkPath::kInverseEvenOdd_FillType);
michael@0:             fType = kPath_Type;
michael@0:             break;
michael@0:         case kPath_Type:
michael@0:             fPath.get()->toggleInverseFillType();
michael@0:             break;
michael@0:         case kEmpty_Type:
michael@0:             // Should this set to an empty, inverse filled path?
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkClipStack::Element::initPath(int saveCount, const SkPath& path, SkRegion::Op op,
michael@0:                                     bool doAA) {
michael@0:     if (!path.isInverseFillType()) {
michael@0:         if (SkPath::kNone_PathAsRect != path.asRect()) {
michael@0:             this->initRect(saveCount, path.getBounds(), op, doAA);
michael@0:             return;
michael@0:         }
michael@0:         SkRect ovalRect;
michael@0:         if (path.isOval(&ovalRect)) {
michael@0:             SkRRect rrect;
michael@0:             rrect.setOval(ovalRect);
michael@0:             this->initRRect(saveCount, rrect, op, doAA);
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0:     fPath.set(path);
michael@0:     fType = kPath_Type;
michael@0:     this->initCommon(saveCount, op, doAA);
michael@0: }
michael@0: 
michael@0: void SkClipStack::Element::asPath(SkPath* path) const {
michael@0:     switch (fType) {
michael@0:         case kEmpty_Type:
michael@0:             path->reset();
michael@0:             break;
michael@0:         case kRect_Type:
michael@0:             path->reset();
michael@0:             path->addRect(this->getRect());
michael@0:             break;
michael@0:         case kRRect_Type:
michael@0:             path->reset();
michael@0:             path->addRRect(fRRect);
michael@0:             break;
michael@0:         case kPath_Type:
michael@0:             *path = *fPath.get();
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkClipStack::Element::setEmpty() {
michael@0:     fType = kEmpty_Type;
michael@0:     fFiniteBound.setEmpty();
michael@0:     fFiniteBoundType = kNormal_BoundsType;
michael@0:     fIsIntersectionOfRects = false;
michael@0:     fRRect.setEmpty();
michael@0:     fPath.reset();
michael@0:     fGenID = kEmptyGenID;
michael@0:     SkDEBUGCODE(this->checkEmpty();)
michael@0: }
michael@0: 
michael@0: void SkClipStack::Element::checkEmpty() const {
michael@0:     SkASSERT(fFiniteBound.isEmpty());
michael@0:     SkASSERT(kNormal_BoundsType == fFiniteBoundType);
michael@0:     SkASSERT(!fIsIntersectionOfRects);
michael@0:     SkASSERT(kEmptyGenID == fGenID);
michael@0:     SkASSERT(!fPath.isValid());
michael@0: }
michael@0: 
michael@0: bool SkClipStack::Element::canBeIntersectedInPlace(int saveCount, SkRegion::Op op) const {
michael@0:     if (kEmpty_Type == fType &&
michael@0:         (SkRegion::kDifference_Op == op || SkRegion::kIntersect_Op == op)) {
michael@0:         return true;
michael@0:     }
michael@0:     // Only clips within the same save/restore frame (as captured by
michael@0:     // the save count) can be merged
michael@0:     return  fSaveCount == saveCount &&
michael@0:             SkRegion::kIntersect_Op == op &&
michael@0:             (SkRegion::kIntersect_Op == fOp || SkRegion::kReplace_Op == fOp);
michael@0: }
michael@0: 
michael@0: bool SkClipStack::Element::rectRectIntersectAllowed(const SkRect& newR, bool newAA) const {
michael@0:     SkASSERT(kRect_Type == fType);
michael@0: 
michael@0:     if (fDoAA == newAA) {
michael@0:         // if the AA setting is the same there is no issue
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (!SkRect::Intersects(this->getRect(), newR)) {
michael@0:         // The calling code will correctly set the result to the empty clip
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     if (this->getRect().contains(newR)) {
michael@0:         // if the new rect carves out a portion of the old one there is no
michael@0:         // issue
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // So either the two overlap in some complex manner or newR contains oldR.
michael@0:     // In the first, case the edges will require different AA. In the second,
michael@0:     // the AA setting that would be carried forward is incorrect (e.g., oldR
michael@0:     // is AA while newR is BW but since newR contains oldR, oldR will be
michael@0:     // drawn BW) since the new AA setting will predominate.
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: // a mirror of combineBoundsRevDiff
michael@0: void SkClipStack::Element::combineBoundsDiff(FillCombo combination, const SkRect& prevFinite) {
michael@0:     switch (combination) {
michael@0:         case kInvPrev_InvCur_FillCombo:
michael@0:             // In this case the only pixels that can remain set
michael@0:             // are inside the current clip rect since the extensions
michael@0:             // to infinity of both clips cancel out and whatever
michael@0:             // is outside of the current clip is removed
michael@0:             fFiniteBoundType = kNormal_BoundsType;
michael@0:             break;
michael@0:         case kInvPrev_Cur_FillCombo:
michael@0:             // In this case the current op is finite so the only pixels
michael@0:             // that aren't set are whatever isn't set in the previous
michael@0:             // clip and whatever this clip carves out
michael@0:             fFiniteBound.join(prevFinite);
michael@0:             fFiniteBoundType = kInsideOut_BoundsType;
michael@0:             break;
michael@0:         case kPrev_InvCur_FillCombo:
michael@0:             // In this case everything outside of this clip's bound
michael@0:             // is erased, so the only pixels that can remain set
michael@0:             // occur w/in the intersection of the two finite bounds
michael@0:             if (!fFiniteBound.intersect(prevFinite)) {
michael@0:                 this->setEmpty();
michael@0:             } else {
michael@0:                 fFiniteBoundType = kNormal_BoundsType;
michael@0:             }
michael@0:             break;
michael@0:         case kPrev_Cur_FillCombo:
michael@0:             // The most conservative result bound is that of the
michael@0:             // prior clip. This could be wildly incorrect if the
michael@0:             // second clip either exactly matches the first clip
michael@0:             // (which should yield the empty set) or reduces the
michael@0:             // size of the prior bound (e.g., if the second clip
michael@0:             // exactly matched the bottom half of the prior clip).
michael@0:             // We ignore these two possibilities.
michael@0:             fFiniteBound = prevFinite;
michael@0:             break;
michael@0:         default:
michael@0:             SkDEBUGFAIL("SkClipStack::Element::combineBoundsDiff Invalid fill combination");
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkClipStack::Element::combineBoundsXOR(int combination, const SkRect& prevFinite) {
michael@0: 
michael@0:     switch (combination) {
michael@0:         case kInvPrev_Cur_FillCombo:       // fall through
michael@0:         case kPrev_InvCur_FillCombo:
michael@0:             // With only one of the clips inverted the result will always
michael@0:             // extend to infinity. The only pixels that may be un-writeable
michael@0:             // lie within the union of the two finite bounds
michael@0:             fFiniteBound.join(prevFinite);
michael@0:             fFiniteBoundType = kInsideOut_BoundsType;
michael@0:             break;
michael@0:         case kInvPrev_InvCur_FillCombo:
michael@0:             // The only pixels that can survive are within the
michael@0:             // union of the two bounding boxes since the extensions
michael@0:             // to infinity of both clips cancel out
michael@0:             // fall through!
michael@0:         case kPrev_Cur_FillCombo:
michael@0:             // The most conservative bound for xor is the
michael@0:             // union of the two bounds. If the two clips exactly overlapped
michael@0:             // the xor could yield the empty set. Similarly the xor
michael@0:             // could reduce the size of the original clip's bound (e.g.,
michael@0:             // if the second clip exactly matched the bottom half of the
michael@0:             // first clip). We ignore these two cases.
michael@0:             fFiniteBound.join(prevFinite);
michael@0:             fFiniteBoundType = kNormal_BoundsType;
michael@0:             break;
michael@0:         default:
michael@0:             SkDEBUGFAIL("SkClipStack::Element::combineBoundsXOR Invalid fill combination");
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // a mirror of combineBoundsIntersection
michael@0: void SkClipStack::Element::combineBoundsUnion(int combination, const SkRect& prevFinite) {
michael@0: 
michael@0:     switch (combination) {
michael@0:         case kInvPrev_InvCur_FillCombo:
michael@0:             if (!fFiniteBound.intersect(prevFinite)) {
michael@0:                 fFiniteBound.setEmpty();
michael@0:                 fGenID = kWideOpenGenID;
michael@0:             }
michael@0:             fFiniteBoundType = kInsideOut_BoundsType;
michael@0:             break;
michael@0:         case kInvPrev_Cur_FillCombo:
michael@0:             // The only pixels that won't be drawable are inside
michael@0:             // the prior clip's finite bound
michael@0:             fFiniteBound = prevFinite;
michael@0:             fFiniteBoundType = kInsideOut_BoundsType;
michael@0:             break;
michael@0:         case kPrev_InvCur_FillCombo:
michael@0:             // The only pixels that won't be drawable are inside
michael@0:             // this clip's finite bound
michael@0:             break;
michael@0:         case kPrev_Cur_FillCombo:
michael@0:             fFiniteBound.join(prevFinite);
michael@0:             break;
michael@0:         default:
michael@0:             SkDEBUGFAIL("SkClipStack::Element::combineBoundsUnion Invalid fill combination");
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // a mirror of combineBoundsUnion
michael@0: void SkClipStack::Element::combineBoundsIntersection(int combination, const SkRect& prevFinite) {
michael@0: 
michael@0:     switch (combination) {
michael@0:         case kInvPrev_InvCur_FillCombo:
michael@0:             // The only pixels that aren't writable in this case
michael@0:             // occur in the union of the two finite bounds
michael@0:             fFiniteBound.join(prevFinite);
michael@0:             fFiniteBoundType = kInsideOut_BoundsType;
michael@0:             break;
michael@0:         case kInvPrev_Cur_FillCombo:
michael@0:             // In this case the only pixels that will remain writeable
michael@0:             // are within the current clip
michael@0:             break;
michael@0:         case kPrev_InvCur_FillCombo:
michael@0:             // In this case the only pixels that will remain writeable
michael@0:             // are with the previous clip
michael@0:             fFiniteBound = prevFinite;
michael@0:             fFiniteBoundType = kNormal_BoundsType;
michael@0:             break;
michael@0:         case kPrev_Cur_FillCombo:
michael@0:             if (!fFiniteBound.intersect(prevFinite)) {
michael@0:                 this->setEmpty();
michael@0:             }
michael@0:             break;
michael@0:         default:
michael@0:             SkDEBUGFAIL("SkClipStack::Element::combineBoundsIntersection Invalid fill combination");
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // a mirror of combineBoundsDiff
michael@0: void SkClipStack::Element::combineBoundsRevDiff(int combination, const SkRect& prevFinite) {
michael@0: 
michael@0:     switch (combination) {
michael@0:         case kInvPrev_InvCur_FillCombo:
michael@0:             // The only pixels that can survive are in the
michael@0:             // previous bound since the extensions to infinity in
michael@0:             // both clips cancel out
michael@0:             fFiniteBound = prevFinite;
michael@0:             fFiniteBoundType = kNormal_BoundsType;
michael@0:             break;
michael@0:         case kInvPrev_Cur_FillCombo:
michael@0:             if (!fFiniteBound.intersect(prevFinite)) {
michael@0:                 this->setEmpty();
michael@0:             } else {
michael@0:                 fFiniteBoundType = kNormal_BoundsType;
michael@0:             }
michael@0:             break;
michael@0:         case kPrev_InvCur_FillCombo:
michael@0:             fFiniteBound.join(prevFinite);
michael@0:             fFiniteBoundType = kInsideOut_BoundsType;
michael@0:             break;
michael@0:         case kPrev_Cur_FillCombo:
michael@0:             // Fall through - as with the kDifference_Op case, the
michael@0:             // most conservative result bound is the bound of the
michael@0:             // current clip. The prior clip could reduce the size of this
michael@0:             // bound (as in the kDifference_Op case) but we are ignoring
michael@0:             // those cases.
michael@0:             break;
michael@0:         default:
michael@0:             SkDEBUGFAIL("SkClipStack::Element::combineBoundsRevDiff Invalid fill combination");
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkClipStack::Element::updateBoundAndGenID(const Element* prior) {
michael@0:     // We set this first here but we may overwrite it later if we determine that the clip is
michael@0:     // either wide-open or empty.
michael@0:     fGenID = GetNextGenID();
michael@0: 
michael@0:     // First, optimistically update the current Element's bound information
michael@0:     // with the current clip's bound
michael@0:     fIsIntersectionOfRects = false;
michael@0:     switch (fType) {
michael@0:         case kRect_Type:
michael@0:             fFiniteBound = this->getRect();
michael@0:             fFiniteBoundType = kNormal_BoundsType;
michael@0: 
michael@0:             if (SkRegion::kReplace_Op == fOp ||
michael@0:                 (SkRegion::kIntersect_Op == fOp && NULL == prior) ||
michael@0:                 (SkRegion::kIntersect_Op == fOp && prior->fIsIntersectionOfRects &&
michael@0:                     prior->rectRectIntersectAllowed(this->getRect(), fDoAA))) {
michael@0:                 fIsIntersectionOfRects = true;
michael@0:             }
michael@0:             break;
michael@0:         case kRRect_Type:
michael@0:             fFiniteBound = fRRect.getBounds();
michael@0:             fFiniteBoundType = kNormal_BoundsType;
michael@0:             break;
michael@0:         case kPath_Type:
michael@0:             fFiniteBound = fPath.get()->getBounds();
michael@0: 
michael@0:             if (fPath.get()->isInverseFillType()) {
michael@0:                 fFiniteBoundType = kInsideOut_BoundsType;
michael@0:             } else {
michael@0:                 fFiniteBoundType = kNormal_BoundsType;
michael@0:             }
michael@0:             break;
michael@0:         case kEmpty_Type:
michael@0:             SkDEBUGFAIL("We shouldn't get here with an empty element.");
michael@0:             break;
michael@0:     }
michael@0: 
michael@0:     if (!fDoAA) {
michael@0:         // Here we mimic a non-anti-aliased scanline system. If there is
michael@0:         // no anti-aliasing we can integerize the bounding box to exclude
michael@0:         // fractional parts that won't be rendered.
michael@0:         // Note: the left edge is handled slightly differently below. We
michael@0:         // are a bit more generous in the rounding since we don't want to
michael@0:         // risk missing the left pixels when fLeft is very close to .5
michael@0:         fFiniteBound.set(SkScalarFloorToScalar(fFiniteBound.fLeft+0.45f),
michael@0:                          SkScalarRoundToScalar(fFiniteBound.fTop),
michael@0:                          SkScalarRoundToScalar(fFiniteBound.fRight),
michael@0:                          SkScalarRoundToScalar(fFiniteBound.fBottom));
michael@0:     }
michael@0: 
michael@0:     // Now determine the previous Element's bound information taking into
michael@0:     // account that there may be no previous clip
michael@0:     SkRect prevFinite;
michael@0:     SkClipStack::BoundsType prevType;
michael@0: 
michael@0:     if (NULL == prior) {
michael@0:         // no prior clip means the entire plane is writable
michael@0:         prevFinite.setEmpty();   // there are no pixels that cannot be drawn to
michael@0:         prevType = kInsideOut_BoundsType;
michael@0:     } else {
michael@0:         prevFinite = prior->fFiniteBound;
michael@0:         prevType = prior->fFiniteBoundType;
michael@0:     }
michael@0: 
michael@0:     FillCombo combination = kPrev_Cur_FillCombo;
michael@0:     if (kInsideOut_BoundsType == fFiniteBoundType) {
michael@0:         combination = (FillCombo) (combination | 0x01);
michael@0:     }
michael@0:     if (kInsideOut_BoundsType == prevType) {
michael@0:         combination = (FillCombo) (combination | 0x02);
michael@0:     }
michael@0: 
michael@0:     SkASSERT(kInvPrev_InvCur_FillCombo == combination ||
michael@0:                 kInvPrev_Cur_FillCombo == combination ||
michael@0:                 kPrev_InvCur_FillCombo == combination ||
michael@0:                 kPrev_Cur_FillCombo == combination);
michael@0: 
michael@0:     // Now integrate with clip with the prior clips
michael@0:     switch (fOp) {
michael@0:         case SkRegion::kDifference_Op:
michael@0:             this->combineBoundsDiff(combination, prevFinite);
michael@0:             break;
michael@0:         case SkRegion::kXOR_Op:
michael@0:             this->combineBoundsXOR(combination, prevFinite);
michael@0:             break;
michael@0:         case SkRegion::kUnion_Op:
michael@0:             this->combineBoundsUnion(combination, prevFinite);
michael@0:             break;
michael@0:         case SkRegion::kIntersect_Op:
michael@0:             this->combineBoundsIntersection(combination, prevFinite);
michael@0:             break;
michael@0:         case SkRegion::kReverseDifference_Op:
michael@0:             this->combineBoundsRevDiff(combination, prevFinite);
michael@0:             break;
michael@0:         case SkRegion::kReplace_Op:
michael@0:             // Replace just ignores everything prior
michael@0:             // The current clip's bound information is already filled in
michael@0:             // so nothing to do
michael@0:             break;
michael@0:         default:
michael@0:             SkDebugf("SkRegion::Op error\n");
michael@0:             SkASSERT(0);
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // This constant determines how many Element's are allocated together as a block in
michael@0: // the deque. As such it needs to balance allocating too much memory vs.
michael@0: // incurring allocation/deallocation thrashing. It should roughly correspond to
michael@0: // the deepest save/restore stack we expect to see.
michael@0: static const int kDefaultElementAllocCnt = 8;
michael@0: 
michael@0: SkClipStack::SkClipStack()
michael@0:     : fDeque(sizeof(Element), kDefaultElementAllocCnt)
michael@0:     , fSaveCount(0) {
michael@0: }
michael@0: 
michael@0: SkClipStack::SkClipStack(const SkClipStack& b)
michael@0:     : fDeque(sizeof(Element), kDefaultElementAllocCnt) {
michael@0:     *this = b;
michael@0: }
michael@0: 
michael@0: SkClipStack::SkClipStack(const SkRect& r)
michael@0:     : fDeque(sizeof(Element), kDefaultElementAllocCnt)
michael@0:     , fSaveCount(0) {
michael@0:     if (!r.isEmpty()) {
michael@0:         this->clipDevRect(r, SkRegion::kReplace_Op, false);
michael@0:     }
michael@0: }
michael@0: 
michael@0: SkClipStack::SkClipStack(const SkIRect& r)
michael@0:     : fDeque(sizeof(Element), kDefaultElementAllocCnt)
michael@0:     , fSaveCount(0) {
michael@0:     if (!r.isEmpty()) {
michael@0:         SkRect temp;
michael@0:         temp.set(r);
michael@0:         this->clipDevRect(temp, SkRegion::kReplace_Op, false);
michael@0:     }
michael@0: }
michael@0: 
michael@0: SkClipStack::~SkClipStack() {
michael@0:     reset();
michael@0: }
michael@0: 
michael@0: SkClipStack& SkClipStack::operator=(const SkClipStack& b) {
michael@0:     if (this == &b) {
michael@0:         return *this;
michael@0:     }
michael@0:     reset();
michael@0: 
michael@0:     fSaveCount = b.fSaveCount;
michael@0:     SkDeque::F2BIter recIter(b.fDeque);
michael@0:     for (const Element* element = (const Element*)recIter.next();
michael@0:          element != NULL;
michael@0:          element = (const Element*)recIter.next()) {
michael@0:         new (fDeque.push_back()) Element(*element);
michael@0:     }
michael@0: 
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: bool SkClipStack::operator==(const SkClipStack& b) const {
michael@0:     if (this->getTopmostGenID() == b.getTopmostGenID()) {
michael@0:         return true;
michael@0:     }
michael@0:     if (fSaveCount != b.fSaveCount ||
michael@0:         fDeque.count() != b.fDeque.count()) {
michael@0:         return false;
michael@0:     }
michael@0:     SkDeque::F2BIter myIter(fDeque);
michael@0:     SkDeque::F2BIter bIter(b.fDeque);
michael@0:     const Element* myElement = (const Element*)myIter.next();
michael@0:     const Element* bElement = (const Element*)bIter.next();
michael@0: 
michael@0:     while (myElement != NULL && bElement != NULL) {
michael@0:         if (*myElement != *bElement) {
michael@0:             return false;
michael@0:         }
michael@0:         myElement = (const Element*)myIter.next();
michael@0:         bElement = (const Element*)bIter.next();
michael@0:     }
michael@0:     return myElement == NULL && bElement == NULL;
michael@0: }
michael@0: 
michael@0: void SkClipStack::reset() {
michael@0:     // We used a placement new for each object in fDeque, so we're responsible
michael@0:     // for calling the destructor on each of them as well.
michael@0:     while (!fDeque.empty()) {
michael@0:         Element* element = (Element*)fDeque.back();
michael@0:         element->~Element();
michael@0:         fDeque.pop_back();
michael@0:     }
michael@0: 
michael@0:     fSaveCount = 0;
michael@0: }
michael@0: 
michael@0: void SkClipStack::save() {
michael@0:     fSaveCount += 1;
michael@0: }
michael@0: 
michael@0: void SkClipStack::restore() {
michael@0:     fSaveCount -= 1;
michael@0:     restoreTo(fSaveCount);
michael@0: }
michael@0: 
michael@0: void SkClipStack::restoreTo(int saveCount) {
michael@0:     while (!fDeque.empty()) {
michael@0:         Element* element = (Element*)fDeque.back();
michael@0:         if (element->fSaveCount <= saveCount) {
michael@0:             break;
michael@0:         }
michael@0:         element->~Element();
michael@0:         fDeque.pop_back();
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkClipStack::getBounds(SkRect* canvFiniteBound,
michael@0:                             BoundsType* boundType,
michael@0:                             bool* isIntersectionOfRects) const {
michael@0:     SkASSERT(NULL != canvFiniteBound && NULL != boundType);
michael@0: 
michael@0:     Element* element = (Element*)fDeque.back();
michael@0: 
michael@0:     if (NULL == element) {
michael@0:         // the clip is wide open - the infinite plane w/ no pixels un-writeable
michael@0:         canvFiniteBound->setEmpty();
michael@0:         *boundType = kInsideOut_BoundsType;
michael@0:         if (NULL != isIntersectionOfRects) {
michael@0:             *isIntersectionOfRects = false;
michael@0:         }
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     *canvFiniteBound = element->fFiniteBound;
michael@0:     *boundType = element->fFiniteBoundType;
michael@0:     if (NULL != isIntersectionOfRects) {
michael@0:         *isIntersectionOfRects = element->fIsIntersectionOfRects;
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkClipStack::intersectRectWithClip(SkRect* rect) const {
michael@0:     SkASSERT(NULL != rect);
michael@0: 
michael@0:     SkRect bounds;
michael@0:     SkClipStack::BoundsType bt;
michael@0:     this->getBounds(&bounds, &bt);
michael@0:     if (bt == SkClipStack::kInsideOut_BoundsType) {
michael@0:         if (bounds.contains(*rect)) {
michael@0:             return false;
michael@0:         } else {
michael@0:             // If rect's x values are both within bound's x range we
michael@0:             // could clip here. Same for y. But we don't bother to check.
michael@0:             return true;
michael@0:         }
michael@0:     } else {
michael@0:         return rect->intersect(bounds);
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkClipStack::quickContains(const SkRect& rect) const {
michael@0: 
michael@0:     Iter iter(*this, Iter::kTop_IterStart);
michael@0:     const Element* element = iter.prev();
michael@0:     while (element != NULL) {
michael@0:         if (SkRegion::kIntersect_Op != element->getOp() && SkRegion::kReplace_Op != element->getOp())
michael@0:             return false;
michael@0:         if (element->isInverseFilled()) {
michael@0:             // Part of 'rect' could be trimmed off by the inverse-filled clip element
michael@0:             if (SkRect::Intersects(element->getBounds(), rect)) {
michael@0:                 return false;
michael@0:             }
michael@0:         } else {
michael@0:             if (!element->contains(rect)) {
michael@0:                 return false;
michael@0:             }
michael@0:         }
michael@0:         if (SkRegion::kReplace_Op == element->getOp()) {
michael@0:             break;
michael@0:         }
michael@0:         element = iter.prev();
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void SkClipStack::pushElement(const Element& element) {
michael@0:     // Use reverse iterator instead of back because Rect path may need previous
michael@0:     SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart);
michael@0:     Element* prior = (Element*) iter.prev();
michael@0: 
michael@0:     if (NULL != prior) {
michael@0:         if (prior->canBeIntersectedInPlace(fSaveCount, element.getOp())) {
michael@0:             switch (prior->fType) {
michael@0:                 case Element::kEmpty_Type:
michael@0:                     SkDEBUGCODE(prior->checkEmpty();)
michael@0:                     return;
michael@0:                 case Element::kRect_Type:
michael@0:                     if (Element::kRect_Type == element.getType()) {
michael@0:                         if (prior->rectRectIntersectAllowed(element.getRect(), element.isAA())) {
michael@0:                             SkRect isectRect;
michael@0:                             if (!isectRect.intersect(prior->getRect(), element.getRect())) {
michael@0:                                 prior->setEmpty();
michael@0:                                 return;
michael@0:                             }
michael@0: 
michael@0:                             prior->fRRect.setRect(isectRect);
michael@0:                             prior->fDoAA = element.isAA();
michael@0:                             Element* priorPrior = (Element*) iter.prev();
michael@0:                             prior->updateBoundAndGenID(priorPrior);
michael@0:                             return;
michael@0:                         }
michael@0:                         break;
michael@0:                     }
michael@0:                     // fallthrough
michael@0:                 default:
michael@0:                     if (!SkRect::Intersects(prior->getBounds(), element.getBounds())) {
michael@0:                         prior->setEmpty();
michael@0:                         return;
michael@0:                     }
michael@0:                     break;
michael@0:             }
michael@0:         } else if (SkRegion::kReplace_Op == element.getOp()) {
michael@0:             this->restoreTo(fSaveCount - 1);
michael@0:             prior = (Element*) fDeque.back();
michael@0:         }
michael@0:     }
michael@0:     Element* newElement = SkNEW_PLACEMENT_ARGS(fDeque.push_back(), Element, (element));
michael@0:     newElement->updateBoundAndGenID(prior);
michael@0: }
michael@0: 
michael@0: void SkClipStack::clipDevRRect(const SkRRect& rrect, SkRegion::Op op, bool doAA) {
michael@0:     Element element(fSaveCount, rrect, op, doAA);
michael@0:     this->pushElement(element);
michael@0: }
michael@0: 
michael@0: void SkClipStack::clipDevRect(const SkRect& rect, SkRegion::Op op, bool doAA) {
michael@0:     Element element(fSaveCount, rect, op, doAA);
michael@0:     this->pushElement(element);
michael@0: }
michael@0: 
michael@0: void SkClipStack::clipDevPath(const SkPath& path, SkRegion::Op op, bool doAA) {
michael@0:     Element element(fSaveCount, path, op, doAA);
michael@0:     this->pushElement(element);
michael@0: }
michael@0: 
michael@0: void SkClipStack::clipEmpty() {
michael@0:     Element* element = (Element*) fDeque.back();
michael@0: 
michael@0:     if (element && element->canBeIntersectedInPlace(fSaveCount, SkRegion::kIntersect_Op)) {
michael@0:         element->setEmpty();
michael@0:     }
michael@0:     new (fDeque.push_back()) Element(fSaveCount);
michael@0: 
michael@0:     ((Element*)fDeque.back())->fGenID = kEmptyGenID;
michael@0: }
michael@0: 
michael@0: bool SkClipStack::isWideOpen() const {
michael@0:     return this->getTopmostGenID() == kWideOpenGenID;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: SkClipStack::Iter::Iter() : fStack(NULL) {
michael@0: }
michael@0: 
michael@0: SkClipStack::Iter::Iter(const SkClipStack& stack, IterStart startLoc)
michael@0:     : fStack(&stack) {
michael@0:     this->reset(stack, startLoc);
michael@0: }
michael@0: 
michael@0: const SkClipStack::Element* SkClipStack::Iter::next() {
michael@0:     return (const SkClipStack::Element*)fIter.next();
michael@0: }
michael@0: 
michael@0: const SkClipStack::Element* SkClipStack::Iter::prev() {
michael@0:     return (const SkClipStack::Element*)fIter.prev();
michael@0: }
michael@0: 
michael@0: const SkClipStack::Element* SkClipStack::Iter::skipToTopmost(SkRegion::Op op) {
michael@0: 
michael@0:     if (NULL == fStack) {
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     fIter.reset(fStack->fDeque, SkDeque::Iter::kBack_IterStart);
michael@0: 
michael@0:     const SkClipStack::Element* element = NULL;
michael@0: 
michael@0:     for (element = (const SkClipStack::Element*) fIter.prev();
michael@0:          NULL != element;
michael@0:          element = (const SkClipStack::Element*) fIter.prev()) {
michael@0: 
michael@0:         if (op == element->fOp) {
michael@0:             // The Deque's iterator is actually one pace ahead of the
michael@0:             // returned value. So while "element" is the element we want to
michael@0:             // return, the iterator is actually pointing at (and will
michael@0:             // return on the next "next" or "prev" call) the element
michael@0:             // in front of it in the deque. Bump the iterator forward a
michael@0:             // step so we get the expected result.
michael@0:             if (NULL == fIter.next()) {
michael@0:                 // The reverse iterator has run off the front of the deque
michael@0:                 // (i.e., the "op" clip is the first clip) and can't
michael@0:                 // recover. Reset the iterator to start at the front.
michael@0:                 fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart);
michael@0:             }
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (NULL == element) {
michael@0:         // There were no "op" clips
michael@0:         fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart);
michael@0:     }
michael@0: 
michael@0:     return this->next();
michael@0: }
michael@0: 
michael@0: void SkClipStack::Iter::reset(const SkClipStack& stack, IterStart startLoc) {
michael@0:     fStack = &stack;
michael@0:     fIter.reset(stack.fDeque, static_cast<SkDeque::Iter::IterStart>(startLoc));
michael@0: }
michael@0: 
michael@0: // helper method
michael@0: void SkClipStack::getConservativeBounds(int offsetX,
michael@0:                                         int offsetY,
michael@0:                                         int maxWidth,
michael@0:                                         int maxHeight,
michael@0:                                         SkRect* devBounds,
michael@0:                                         bool* isIntersectionOfRects) const {
michael@0:     SkASSERT(NULL != devBounds);
michael@0: 
michael@0:     devBounds->setLTRB(0, 0,
michael@0:                        SkIntToScalar(maxWidth), SkIntToScalar(maxHeight));
michael@0: 
michael@0:     SkRect temp;
michael@0:     SkClipStack::BoundsType boundType;
michael@0: 
michael@0:     // temp starts off in canvas space here
michael@0:     this->getBounds(&temp, &boundType, isIntersectionOfRects);
michael@0:     if (SkClipStack::kInsideOut_BoundsType == boundType) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // but is converted to device space here
michael@0:     temp.offset(SkIntToScalar(offsetX), SkIntToScalar(offsetY));
michael@0: 
michael@0:     if (!devBounds->intersect(temp)) {
michael@0:         devBounds->setEmpty();
michael@0:     }
michael@0: }
michael@0: 
michael@0: int32_t SkClipStack::GetNextGenID() {
michael@0:     // TODO: handle overflow.
michael@0:     return sk_atomic_inc(&gGenID);
michael@0: }
michael@0: 
michael@0: int32_t SkClipStack::getTopmostGenID() const {
michael@0:     if (fDeque.empty()) {
michael@0:         return kWideOpenGenID;
michael@0:     }
michael@0: 
michael@0:     const Element* back = static_cast<const Element*>(fDeque.back());
michael@0:     if (kInsideOut_BoundsType == back->fFiniteBoundType && back->fFiniteBound.isEmpty()) {
michael@0:         return kWideOpenGenID;
michael@0:     }
michael@0: 
michael@0:     return back->getGenID();
michael@0: }