src/core/SkClipStack.cpp

/*
 * Copyright 2011 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#include "SkClipStack.h"
#include "SkPath.h"
#include "SkThread.h"

#include <new>


// 0-2 are reserved for invalid, empty & wide-open
static const int32_t kFirstUnreservedGenID = 3;
int32_t SkClipStack::gGenID = kFirstUnreservedGenID;

void SkClipStack::Element::invertShapeFillType() {
    switch (fType) {
        case kRect_Type:
            fPath.reset();
            fPath.addRect(fRect);
            fPath.setFillType(SkPath::kInverseWinding_FillType);
            fType = kPath_Type;
            break;
        case kPath_Type:
            fPath.toggleInverseFillType();
        case kEmpty_Type:
            break;
    }
}

void SkClipStack::Element::checkEmpty() const {
    SkASSERT(fFiniteBound.isEmpty());
    SkASSERT(kNormal_BoundsType == fFiniteBoundType);
    SkASSERT(!fIsIntersectionOfRects);
    SkASSERT(kEmptyGenID == fGenID);
    SkASSERT(fPath.isEmpty());
}

bool SkClipStack::Element::canBeIntersectedInPlace(int saveCount, SkRegion::Op op) const {
    if (kEmpty_Type == fType &&
        (SkRegion::kDifference_Op == op || SkRegion::kIntersect_Op == op)) {
        return true;
    }
    // Only clips within the same save/restore frame (as captured by
    // the save count) can be merged
    return  fSaveCount == saveCount &&
            SkRegion::kIntersect_Op == op &&
            (SkRegion::kIntersect_Op == fOp || SkRegion::kReplace_Op == fOp);
}

bool SkClipStack::Element::rectRectIntersectAllowed(const SkRect& newR, bool newAA) const {
    SkASSERT(kRect_Type == fType);

    if (fDoAA == newAA) {
        // if the AA setting is the same there is no issue
        return true;
    }

    if (!SkRect::Intersects(fRect, newR)) {
        // The calling code will correctly set the result to the empty clip
        return true;
    }

    if (fRect.contains(newR)) {
        // if the new rect carves out a portion of the old one there is no
        // issue
        return true;
    }

    // So either the two overlap in some complex manner or newR contains oldR.
    // In the first, case the edges will require different AA. In the second,
    // the AA setting that would be carried forward is incorrect (e.g., oldR
    // is AA while newR is BW but since newR contains oldR, oldR will be
    // drawn BW) since the new AA setting will predominate.
    return false;
}

// a mirror of combineBoundsRevDiff
void SkClipStack::Element::combineBoundsDiff(FillCombo combination, const SkRect& prevFinite) {
    switch (combination) {
        case kInvPrev_InvCur_FillCombo:
            // In this case the only pixels that can remain set
            // are inside the current clip rect since the extensions
            // to infinity of both clips cancel out and whatever
            // is outside of the current clip is removed
            fFiniteBoundType = kNormal_BoundsType;
            break;
        case kInvPrev_Cur_FillCombo:
            // In this case the current op is finite so the only pixels
            // that aren't set are whatever isn't set in the previous
            // clip and whatever this clip carves out
            fFiniteBound.join(prevFinite);
            fFiniteBoundType = kInsideOut_BoundsType;
            break;
        case kPrev_InvCur_FillCombo:
            // In this case everything outside of this clip's bound
            // is erased, so the only pixels that can remain set
            // occur w/in the intersection of the two finite bounds
            if (!fFiniteBound.intersect(prevFinite)) {
                fFiniteBound.setEmpty();
                fGenID = kEmptyGenID;
            }
            fFiniteBoundType = kNormal_BoundsType;
            break;
        case kPrev_Cur_FillCombo:
            // The most conservative result bound is that of the
            // prior clip. This could be wildly incorrect if the
            // second clip either exactly matches the first clip
            // (which should yield the empty set) or reduces the
            // size of the prior bound (e.g., if the second clip
            // exactly matched the bottom half of the prior clip).
            // We ignore these two possibilities.
            fFiniteBound = prevFinite;
            break;
        default:
            SkDEBUGFAIL("SkClipStack::Element::combineBoundsDiff Invalid fill combination");
            break;
    }
}

void SkClipStack::Element::combineBoundsXOR(int combination, const SkRect& prevFinite) {

    switch (combination) {
        case kInvPrev_Cur_FillCombo:       // fall through
        case kPrev_InvCur_FillCombo:
            // With only one of the clips inverted the result will always
            // extend to infinity. The only pixels that may be un-writeable
            // lie within the union of the two finite bounds
            fFiniteBound.join(prevFinite);
            fFiniteBoundType = kInsideOut_BoundsType;
            break;
        case kInvPrev_InvCur_FillCombo:
            // The only pixels that can survive are within the
            // union of the two bounding boxes since the extensions
            // to infinity of both clips cancel out
            // fall through!
        case kPrev_Cur_FillCombo:
            // The most conservative bound for xor is the
            // union of the two bounds. If the two clips exactly overlapped
            // the xor could yield the empty set. Similarly the xor
            // could reduce the size of the original clip's bound (e.g.,
            // if the second clip exactly matched the bottom half of the
            // first clip). We ignore these two cases.
            fFiniteBound.join(prevFinite);
            fFiniteBoundType = kNormal_BoundsType;
            break;
        default:
            SkDEBUGFAIL("SkClipStack::Element::combineBoundsXOR Invalid fill combination");
            break;
    }
}

// a mirror of combineBoundsIntersection
void SkClipStack::Element::combineBoundsUnion(int combination, const SkRect& prevFinite) {

    switch (combination) {
        case kInvPrev_InvCur_FillCombo:
            if (!fFiniteBound.intersect(prevFinite)) {
                fFiniteBound.setEmpty();
                fGenID = kWideOpenGenID;
            }
            fFiniteBoundType = kInsideOut_BoundsType;
            break;
        case kInvPrev_Cur_FillCombo:
            // The only pixels that won't be drawable are inside
            // the prior clip's finite bound
            fFiniteBound = prevFinite;
            fFiniteBoundType = kInsideOut_BoundsType;
            break;
        case kPrev_InvCur_FillCombo:
            // The only pixels that won't be drawable are inside
            // this clip's finite bound
            break;
        case kPrev_Cur_FillCombo:
            fFiniteBound.join(prevFinite);
            break;
        default:
            SkDEBUGFAIL("SkClipStack::Element::combineBoundsUnion Invalid fill combination");
            break;
    }
}

// a mirror of combineBoundsUnion
void SkClipStack::Element::combineBoundsIntersection(int combination, const SkRect& prevFinite) {

    switch (combination) {
        case kInvPrev_InvCur_FillCombo:
            // The only pixels that aren't writable in this case
            // occur in the union of the two finite bounds
            fFiniteBound.join(prevFinite);
            fFiniteBoundType = kInsideOut_BoundsType;
            break;
        case kInvPrev_Cur_FillCombo:
            // In this case the only pixels that will remain writeable
            // are within the current clip
            break;
        case kPrev_InvCur_FillCombo:
            // In this case the only pixels that will remain writeable
            // are with the previous clip
            fFiniteBound = prevFinite;
            fFiniteBoundType = kNormal_BoundsType;
            break;
        case kPrev_Cur_FillCombo:
            if (!fFiniteBound.intersect(prevFinite)) {
                fFiniteBound.setEmpty();
                fGenID = kEmptyGenID;
            }
            break;
        default:
            SkDEBUGFAIL("SkClipStack::Element::combineBoundsIntersection Invalid fill combination");
            break;
    }
}

// a mirror of combineBoundsDiff
void SkClipStack::Element::combineBoundsRevDiff(int combination, const SkRect& prevFinite) {

    switch (combination) {
        case kInvPrev_InvCur_FillCombo:
            // The only pixels that can survive are in the
            // previous bound since the extensions to infinity in
            // both clips cancel out
            fFiniteBound = prevFinite;
            fFiniteBoundType = kNormal_BoundsType;
            break;
        case kInvPrev_Cur_FillCombo:
            if (!fFiniteBound.intersect(prevFinite)) {
                fFiniteBound.setEmpty();
                fGenID = kEmptyGenID;
            }
            fFiniteBoundType = kNormal_BoundsType;
            break;
        case kPrev_InvCur_FillCombo:
            fFiniteBound.join(prevFinite);
            fFiniteBoundType = kInsideOut_BoundsType;
            break;
        case kPrev_Cur_FillCombo:
            // Fall through - as with the kDifference_Op case, the
            // most conservative result bound is the bound of the
            // current clip. The prior clip could reduce the size of this
            // bound (as in the kDifference_Op case) but we are ignoring
            // those cases.
            break;
        default:
            SkDEBUGFAIL("SkClipStack::Element::combineBoundsRevDiff Invalid fill combination");
            break;
    }
}

void SkClipStack::Element::updateBoundAndGenID(const Element* prior) {
    // We set this first here but we may overwrite it later if we determine that the clip is
    // either wide-open or empty.
    fGenID = GetNextGenID();

    // First, optimistically update the current Element's bound information
    // with the current clip's bound
    fIsIntersectionOfRects = false;
    if (kRect_Type == fType) {
        fFiniteBound = fRect;
        fFiniteBoundType = kNormal_BoundsType;

        if (SkRegion::kReplace_Op == fOp ||
            (SkRegion::kIntersect_Op == fOp && NULL == prior) ||
            (SkRegion::kIntersect_Op == fOp && prior->fIsIntersectionOfRects &&
                prior->rectRectIntersectAllowed(fRect, fDoAA))) {
            fIsIntersectionOfRects = true;
        }

    } else {
        SkASSERT(kPath_Type == fType);

        fFiniteBound = fPath.getBounds();

        if (fPath.isInverseFillType()) {
            fFiniteBoundType = kInsideOut_BoundsType;
        } else {
            fFiniteBoundType = kNormal_BoundsType;
        }
    }

    if (!fDoAA) {
        // Here we mimic a non-anti-aliased scanline system. If there is
        // no anti-aliasing we can integerize the bounding box to exclude
        // fractional parts that won't be rendered.
        // Note: the left edge is handled slightly differently below. We
        // are a bit more generous in the rounding since we don't want to
        // risk missing the left pixels when fLeft is very close to .5
        fFiniteBound.set(SkScalarFloorToScalar(fFiniteBound.fLeft+0.45f),
                         SkScalarRoundToScalar(fFiniteBound.fTop),
                         SkScalarRoundToScalar(fFiniteBound.fRight),
                         SkScalarRoundToScalar(fFiniteBound.fBottom));
    }

    // Now determine the previous Element's bound information taking into
    // account that there may be no previous clip
    SkRect prevFinite;
    SkClipStack::BoundsType prevType;

    if (NULL == prior) {
        // no prior clip means the entire plane is writable
        prevFinite.setEmpty();   // there are no pixels that cannot be drawn to
        prevType = kInsideOut_BoundsType;
    } else {
        prevFinite = prior->fFiniteBound;
        prevType = prior->fFiniteBoundType;
    }

    FillCombo combination = kPrev_Cur_FillCombo;
    if (kInsideOut_BoundsType == fFiniteBoundType) {
        combination = (FillCombo) (combination | 0x01);
    }
    if (kInsideOut_BoundsType == prevType) {
        combination = (FillCombo) (combination | 0x02);
    }

    SkASSERT(kInvPrev_InvCur_FillCombo == combination ||
                kInvPrev_Cur_FillCombo == combination ||
                kPrev_InvCur_FillCombo == combination ||
                kPrev_Cur_FillCombo == combination);

    // Now integrate with clip with the prior clips
    switch (fOp) {
        case SkRegion::kDifference_Op:
            this->combineBoundsDiff(combination, prevFinite);
            break;
        case SkRegion::kXOR_Op:
            this->combineBoundsXOR(combination, prevFinite);
            break;
        case SkRegion::kUnion_Op:
            this->combineBoundsUnion(combination, prevFinite);
            break;
        case SkRegion::kIntersect_Op:
            this->combineBoundsIntersection(combination, prevFinite);
            break;
        case SkRegion::kReverseDifference_Op:
            this->combineBoundsRevDiff(combination, prevFinite);
            break;
        case SkRegion::kReplace_Op:
            // Replace just ignores everything prior
            // The current clip's bound information is already filled in
            // so nothing to do
            break;
        default:
            SkDebugf("SkRegion::Op error/n");
            SkASSERT(0);
            break;
    }
}

// This constant determines how many Element's are allocated together as a block in
// the deque. As such it needs to balance allocating too much memory vs.
// incurring allocation/deallocation thrashing. It should roughly correspond to
// the deepest save/restore stack we expect to see.
static const int kDefaultElementAllocCnt = 8;

SkClipStack::SkClipStack()
    : fDeque(sizeof(Element), kDefaultElementAllocCnt)
    , fSaveCount(0) {
}

SkClipStack::SkClipStack(const SkClipStack& b)
    : fDeque(sizeof(Element), kDefaultElementAllocCnt) {
    *this = b;
}

SkClipStack::SkClipStack(const SkRect& r)
    : fDeque(sizeof(Element), kDefaultElementAllocCnt)
    , fSaveCount(0) {
    if (!r.isEmpty()) {
        this->clipDevRect(r, SkRegion::kReplace_Op, false);
    }
}

SkClipStack::SkClipStack(const SkIRect& r)
    : fDeque(sizeof(Element), kDefaultElementAllocCnt)
    , fSaveCount(0) {
    if (!r.isEmpty()) {
        SkRect temp;
        temp.set(r);
        this->clipDevRect(temp, SkRegion::kReplace_Op, false);
    }
}

SkClipStack::~SkClipStack() {
    reset();
}

SkClipStack& SkClipStack::operator=(const SkClipStack& b) {
    if (this == &b) {
        return *this;
    }
    reset();

    fSaveCount = b.fSaveCount;
    SkDeque::F2BIter recIter(b.fDeque);
    for (const Element* element = (const Element*)recIter.next();
         element != NULL;
         element = (const Element*)recIter.next()) {
        new (fDeque.push_back()) Element(*element);
    }

    return *this;
}

bool SkClipStack::operator==(const SkClipStack& b) const {
    if (this->getTopmostGenID() == b.getTopmostGenID()) {
        return true;
    }
    if (fSaveCount != b.fSaveCount ||
        fDeque.count() != b.fDeque.count()) {
        return false;
    }
    SkDeque::F2BIter myIter(fDeque);
    SkDeque::F2BIter bIter(b.fDeque);
    const Element* myElement = (const Element*)myIter.next();
    const Element* bElement = (const Element*)bIter.next();

    while (myElement != NULL && bElement != NULL) {
        if (*myElement != *bElement) {
            return false;
        }
        myElement = (const Element*)myIter.next();
        bElement = (const Element*)bIter.next();
    }
    return myElement == NULL && bElement == NULL;
}

void SkClipStack::reset() {
    // We used a placement new for each object in fDeque, so we're responsible
    // for calling the destructor on each of them as well.
    while (!fDeque.empty()) {
        Element* element = (Element*)fDeque.back();
        element->~Element();
        fDeque.pop_back();
    }

    fSaveCount = 0;
}

void SkClipStack::save() {
    fSaveCount += 1;
}

void SkClipStack::restore() {
    fSaveCount -= 1;
    restoreTo(fSaveCount);
}

void SkClipStack::restoreTo(int saveCount) {
    while (!fDeque.empty()) {
        Element* element = (Element*)fDeque.back();
        if (element->fSaveCount <= saveCount) {
            break;
        }
        element->~Element();
        fDeque.pop_back();
    }
}

void SkClipStack::getBounds(SkRect* canvFiniteBound,
                            BoundsType* boundType,
                            bool* isIntersectionOfRects) const {
    SkASSERT(NULL != canvFiniteBound && NULL != boundType);

    Element* element = (Element*)fDeque.back();

    if (NULL == element) {
        // the clip is wide open - the infinite plane w/ no pixels un-writeable
        canvFiniteBound->setEmpty();
        *boundType = kInsideOut_BoundsType;
        if (NULL != isIntersectionOfRects) {
            *isIntersectionOfRects = false;
        }
        return;
    }

    *canvFiniteBound = element->fFiniteBound;
    *boundType = element->fFiniteBoundType;
    if (NULL != isIntersectionOfRects) {
        *isIntersectionOfRects = element->fIsIntersectionOfRects;
    }
}

bool SkClipStack::intersectRectWithClip(SkRect* rect) const {
    SkASSERT(NULL != rect);

    SkRect bounds;
    SkClipStack::BoundsType bt;
    this->getBounds(&bounds, &bt);
    if (bt == SkClipStack::kInsideOut_BoundsType) {
        if (bounds.contains(*rect)) {
            return false;
        } else {
            // If rect's x values are both within bound's x range we
            // could clip here. Same for y. But we don't bother to check.
            return true;
        }
    } else {
        return rect->intersect(bounds);
    }
}

bool SkClipStack::quickContains(const SkRect& rect) const {

    Iter iter(*this, Iter::kTop_IterStart);
    const Element* element = iter.prev();
    while (element != NULL) {
        if (SkRegion::kIntersect_Op != element->getOp() && SkRegion::kReplace_Op != element->getOp())
            return false;
        if (element->isInverseFilled()) {
            // Part of 'rect' could be trimmed off by the inverse-filled clip element
            if (SkRect::Intersects(element->getBounds(), rect)) {
                return false;
            }
        } else {
            if (!element->contains(rect)) {
                return false;
            }
        }
        if (SkRegion::kReplace_Op == element->getOp()) {
            break;
        }
        element = iter.prev();
    }
    return true;
}

void SkClipStack::clipDevRect(const SkRect& rect, SkRegion::Op op, bool doAA) {

    // Use reverse iterator instead of back because Rect path may need previous
    SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart);
    Element* element = (Element*) iter.prev();

    if (NULL != element) {
        if (element->canBeIntersectedInPlace(fSaveCount, op)) {
            switch (element->fType) {
                case Element::kEmpty_Type:
                    element->checkEmpty();
                    return;
                case Element::kRect_Type:
                    if (element->rectRectIntersectAllowed(rect, doAA)) {
                        if (!element->fRect.intersect(rect)) {
                            element->setEmpty();
                            return;
                        }

                        element->fDoAA = doAA;
                        Element* prev = (Element*) iter.prev();
                        element->updateBoundAndGenID(prev);
                        return;
                    }
                    break;
                case Element::kPath_Type:
                    if (!SkRect::Intersects(element->fPath.getBounds(), rect)) {
                        element->setEmpty();
                        return;
                    }
                    break;
            }
        } else if (SkRegion::kReplace_Op == op) {
            this->restoreTo(fSaveCount - 1);
            element = (Element*) fDeque.back();
        }
    }
    new (fDeque.push_back()) Element(fSaveCount, rect, op, doAA);
    ((Element*) fDeque.back())->updateBoundAndGenID(element);
}

void SkClipStack::clipDevPath(const SkPath& path, SkRegion::Op op, bool doAA) {
    SkRect alt;
    if (path.isRect(&alt) && !path.isInverseFillType()) {
        return this->clipDevRect(alt, op, doAA);
    }

    Element* element = (Element*)fDeque.back();
    if (NULL != element) {
        if (element->canBeIntersectedInPlace(fSaveCount, op)) {
            const SkRect& pathBounds = path.getBounds();
            switch (element->fType) {
                case Element::kEmpty_Type:
                    element->checkEmpty();
                    return;
                case Element::kRect_Type:
                    if (!SkRect::Intersects(element->fRect, pathBounds)) {
                        element->setEmpty();
                        return;
                    }
                    break;
                case Element::kPath_Type:
                    if (!SkRect::Intersects(element->fPath.getBounds(), pathBounds)) {
                        element->setEmpty();
                        return;
                    }
                    break;
            }
        } else if (SkRegion::kReplace_Op == op) {
            this->restoreTo(fSaveCount - 1);
            element = (Element*) fDeque.back();
        }
    }
    new (fDeque.push_back()) Element(fSaveCount, path, op, doAA);
    ((Element*) fDeque.back())->updateBoundAndGenID(element);
}

void SkClipStack::clipEmpty() {

    Element* element = (Element*) fDeque.back();

    if (element && element->canBeIntersectedInPlace(fSaveCount, SkRegion::kIntersect_Op)) {
        switch (element->fType) {
            case Element::kEmpty_Type:
                element->checkEmpty();
                return;
            case Element::kRect_Type:
            case Element::kPath_Type:
                element->setEmpty();
                return;
        }
    }
    new (fDeque.push_back()) Element(fSaveCount);

    ((Element*)fDeque.back())->fGenID = kEmptyGenID;
}

bool SkClipStack::isWideOpen() const {
    return this->getTopmostGenID() == kWideOpenGenID;
}

///////////////////////////////////////////////////////////////////////////////

SkClipStack::Iter::Iter() : fStack(NULL) {
}

SkClipStack::Iter::Iter(const SkClipStack& stack, IterStart startLoc)
    : fStack(&stack) {
    this->reset(stack, startLoc);
}

const SkClipStack::Element* SkClipStack::Iter::next() {
    return (const SkClipStack::Element*)fIter.next();
}

const SkClipStack::Element* SkClipStack::Iter::prev() {
    return (const SkClipStack::Element*)fIter.prev();
}

const SkClipStack::Element* SkClipStack::Iter::skipToTopmost(SkRegion::Op op) {

    if (NULL == fStack) {
        return NULL;
    }

    fIter.reset(fStack->fDeque, SkDeque::Iter::kBack_IterStart);

    const SkClipStack::Element* element = NULL;

    for (element = (const SkClipStack::Element*) fIter.prev();
         NULL != element;
         element = (const SkClipStack::Element*) fIter.prev()) {

        if (op == element->fOp) {
            // The Deque's iterator is actually one pace ahead of the
            // returned value. So while "element" is the element we want to
            // return, the iterator is actually pointing at (and will
            // return on the next "next" or "prev" call) the element
            // in front of it in the deque. Bump the iterator forward a
            // step so we get the expected result.
            if (NULL == fIter.next()) {
                // The reverse iterator has run off the front of the deque
                // (i.e., the "op" clip is the first clip) and can't
                // recover. Reset the iterator to start at the front.
                fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart);
            }
            break;
        }
    }

    if (NULL == element) {
        // There were no "op" clips
        fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart);
    }

    return this->next();
}

void SkClipStack::Iter::reset(const SkClipStack& stack, IterStart startLoc) {
    fStack = &stack;
    fIter.reset(stack.fDeque, static_cast<SkDeque::Iter::IterStart>(startLoc));
}

// helper method
void SkClipStack::getConservativeBounds(int offsetX,
                                        int offsetY,
                                        int maxWidth,
                                        int maxHeight,
                                        SkRect* devBounds,
                                        bool* isIntersectionOfRects) const {
    SkASSERT(NULL != devBounds);

    devBounds->setLTRB(0, 0,
                       SkIntToScalar(maxWidth), SkIntToScalar(maxHeight));

    SkRect temp;
    SkClipStack::BoundsType boundType;

    // temp starts off in canvas space here
    this->getBounds(&temp, &boundType, isIntersectionOfRects);
    if (SkClipStack::kInsideOut_BoundsType == boundType) {
        return;
    }

    // but is converted to device space here
    temp.offset(SkIntToScalar(offsetX), SkIntToScalar(offsetY));

    if (!devBounds->intersect(temp)) {
        devBounds->setEmpty();
    }
}

int32_t SkClipStack::GetNextGenID() {
    // TODO: handle overflow.
    return sk_atomic_inc(&gGenID);
}

int32_t SkClipStack::getTopmostGenID() const {
    if (fDeque.empty()) {
        return kWideOpenGenID;
    }

    const Element* back = static_cast<const Element*>(fDeque.back());
    if (kInsideOut_BoundsType == back->fFiniteBoundType && back->fFiniteBound.isEmpty()) {
        return kWideOpenGenID;
    }

    return back->getGenID();
}