Add a function that computes a reduced representation of the clip stack.

Also adds a unit test. The function is not yet used other than in the test.
Review URL: https://codereview.appspot.com/6855098

git-svn-id: http://skia.googlecode.com/svn/trunk@6553 2bbb7eff-a529-9590-31e7-b0007b416f81

3 files changed, 353 insertions, 0 deletions

diff --git a/src/core/SkClipStack.cpp b/src/core/SkClipStack.cpp
index 38f258039f..10e15992d1 100644
--- a/src/core/SkClipStack.cpp
+++ b/src/core/SkClipStack.cpp
@@ -735,6 +735,20 @@ const SkRect& SkClipStack::Iter::Clip::getBounds() const {
     }
 }
 
+bool SkClipStack::Iter::Clip::contains(const SkRect& rect) const {
+    if (NULL != fRect) {
+        return fRect->contains(rect);
+    } else if (NULL != fPath) {
+        return fPath->conservativelyContainsRect(rect);
+    } else {
+        return false;
+    }
+}
+
+bool SkClipStack::Iter::Clip::isInverseFilled() const {
+    return NULL != fPath && fPath->isInverseFillType();
+}
+
 SkClipStack::Iter::Iter(const SkClipStack& stack, IterStart startLoc)
     : fStack(&stack) {
     this->reset(stack, startLoc);
diff --git a/src/gpu/GrClipMaskManager.cpp b/src/gpu/GrClipMaskManager.cpp
index 772ba561ee..ce520e7fc0 100644
--- a/src/gpu/GrClipMaskManager.cpp
+++ b/src/gpu/GrClipMaskManager.cpp
@@ -25,6 +25,320 @@ GR_DEFINE_RESOURCE_CACHE_DOMAIN(GrClipMaskManager, GetAlphaMaskDomain)
 #define GR_SW_CLIP 1
 
 ////////////////////////////////////////////////////////////////////////////////
+
+namespace GrReducedClip {
+
+/*
+There are plenty of optimizations that could be added here. For example we could consider
+checking for cases where an inverse path can be changed to a regular fill with a different op.
+(e.g. [kIntersect, inverse path] -> [kDifference, path]). Maybe flips could be folded into
+earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
+for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
+based on later intersect operations, and perhaps remove intersect-rects. We could optionally
+take a rect in case the caller knows a bound on what is to be drawn through this clip.
+*/
+void GrReduceClipStack(const SkClipStack& stack,
+                       SkTDArray<SkClipStack::Iter::Clip>* resultClips,
+                       SkRect* resultBounds,
+                       bool* resultsAreBounded,
+                       InitialState* initialState) {
+    resultClips->reset();
+
+    if (stack.isWideOpen()) {
+        *initialState = kAllIn_InitialState;
+        *resultsAreBounded = false;
+        return;
+    }
+
+    SkClipStack::BoundsType type;
+    bool iior;
+    stack.getBounds(resultBounds, &type, &iior);
+    if (iior) {
+        *resultsAreBounded = true;
+        *initialState = kAllOut_InitialState;
+        SkClipStack::Iter::Clip* clip = resultClips->append();
+        // append doesn't call the default cons.
+        *clip = SkClipStack::Iter::Clip();
+
+        // iior should only be true if aa/non-aa status matches.
+        SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
+        clip->fDoAA = iter.prev()->fDoAA;
+        clip->fOp = SkRegion::kReplace_Op;
+        clip->fRect = resultBounds;
+        return;
+    }
+
+    *resultsAreBounded = SkClipStack::kNormal_BoundsType == type && !resultBounds->isEmpty();
+
+    // walk backwards until we get to:
+    //  a) the beginning
+    //  b) an operation that is known to make the bounds all inside/outside
+    //  c) a replace operation    
+
+    static const InitialState kUnknown_InitialState = static_cast<InitialState>(-1);
+    *initialState = kUnknown_InitialState;
+
+    // During our backwards walk, track whether we've seen ops that either grow or shrink the clip.
+    // TODO: track these per saved clip so that we can consider them on the forward pass.
+    bool embiggens = false;
+    bool emsmallens = false;
+
+    SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
+    while ((kUnknown_InitialState == *initialState)) {
+        const SkClipStack::Iter::Clip* clip = iter.prev();
+        if (NULL == clip) {
+            *initialState = kAllIn_InitialState;
+            break;
+        }
+        if (!embiggens && SkClipStack::kEmptyGenID == clip->fGenID) {
+            *initialState = kAllOut_InitialState;
+            break;
+        }
+        if (!emsmallens && SkClipStack::kWideOpenGenID == clip->fGenID) {
+            *initialState = kAllIn_InitialState;
+            break;
+        }
+
+        bool skippable = false;
+        bool isFlip = false; // does this op just flip the in/out state of every point in the bounds
+
+        switch (clip->fOp) {
+            case SkRegion::kDifference_Op:
+                if (*resultsAreBounded) {
+                    // check if the shape subtracted either contains the entire bounds (and makes
+                    // the clip empty) or is outside the bounds and therefore can be skipped.
+                    if (clip->isInverseFilled()) {
+                        if (clip->contains(*resultBounds)) {
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            *initialState = kAllOut_InitialState;
+                            skippable = true;
+                        }
+                    } else {
+                        if (clip->contains(*resultBounds)) {
+                            *initialState = kAllOut_InitialState;
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            skippable = true;
+                        }
+                    }
+                }
+                if (!skippable) {
+                    emsmallens = true;
+                }
+                break;
+            case SkRegion::kIntersect_Op:
+                if (*resultsAreBounded) {
+                    // check if the shape intersected contains the entire bounds and therefore can
+                    // be skipped or it is outside the entire bounds and therfore makes the clip
+                    // empty.
+                    if (clip->isInverseFilled()) {
+                        if (clip->contains(*resultBounds)) {
+                            *initialState = kAllOut_InitialState;
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            skippable = true;
+                        }
+                    } else {
+                        if (clip->contains(*resultBounds)) {
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            *initialState = kAllOut_InitialState;
+                            skippable = true;
+                        }
+                    }
+                }
+                if (!skippable) {
+                    emsmallens = true;
+                }
+                break;
+            case SkRegion::kUnion_Op:
+                if (*resultsAreBounded) {
+                    // If the unioned shape contains the entire bounds then after this element
+                    // the bounds is entirely inside the clip. If the unioned shape is outside the
+                    // bounds then this op can be skipped.
+                    if (clip->isInverseFilled()) {
+                        if (clip->contains(*resultBounds)) {
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            *initialState = kAllIn_InitialState;
+                            skippable = true;
+                        }
+                    } else {
+                        if (clip->contains(*resultBounds)) {
+                            *initialState = kAllIn_InitialState;
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            skippable = true;
+                        }
+                    }
+                }
+                if (!skippable) {
+                    embiggens = true;
+                }
+                break;
+            case SkRegion::kXOR_Op:
+                if (*resultsAreBounded) {
+                    if (clip->isInverseFilled()) {
+                        if (clip->contains(*resultBounds)) {
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            isFlip = true;
+                        }
+                    } else {
+                        if (clip->contains(*resultBounds)) {
+                            isFlip = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            skippable = true;
+                        }
+                    }
+                }
+                if (!skippable) {
+                    emsmallens = embiggens = true;
+                }
+                break;
+            case SkRegion::kReverseDifference_Op:
+                if (*resultsAreBounded) {
+                    if (clip->isInverseFilled()) {
+                        if (clip->contains(*resultBounds)) {
+                            *initialState = kAllOut_InitialState;
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            isFlip = true;
+                        }
+                    } else {
+                        if (clip->contains(*resultBounds)) {
+                            isFlip = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            *initialState = kAllOut_InitialState;
+                            skippable = true;
+                        }
+                    }
+                }
+                if (!skippable) {
+                    emsmallens = embiggens = true;
+                }
+                break;
+            case SkRegion::kReplace_Op:
+                if (*resultsAreBounded) {
+                    if (clip->isInverseFilled()) {
+                        if (clip->contains(*resultBounds)) {
+                            *initialState = kAllOut_InitialState;
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            *initialState = kAllIn_InitialState;
+                            skippable = true;
+                        }
+                    } else {
+                        if (clip->contains(*resultBounds)) {
+                            *initialState = kAllIn_InitialState;
+                            skippable = true;
+                        } else if (!SkRect::Intersects(clip->getBounds(), *resultBounds)) {
+                            *initialState = kAllOut_InitialState;
+                            skippable = true;
+                        }
+                    }
+                }
+                if (!skippable) {
+                    *initialState = kAllOut_InitialState;
+                    embiggens = emsmallens = true;
+                }
+                break;
+            default:
+                SkDEBUGFAIL("Unexpected op.");
+                break;
+        }
+        if (!skippable) {
+            SkClipStack::Iter::Clip* newClip = resultClips->prepend();
+            // if it is a flip, change it to a bounds-filling rect
+            if (isFlip) {
+                SkASSERT(SkRegion::kXOR_Op == clip->fOp || 
+                         SkRegion::kReverseDifference_Op == clip->fOp);
+                newClip->fPath = NULL;
+                newClip->fRect = resultBounds;
+                // assuming this is faster to perform on GPU with stenciling than xor.
+                newClip->fOp = SkRegion::kReverseDifference_Op;
+                newClip->fDoAA = false;
+                newClip->fGenID = SkClipStack::kInvalidGenID;
+            } else {
+                *newClip = *clip;
+            }
+        }
+    }
+
+    if ((kAllOut_InitialState == *initialState && !embiggens) ||
+        (kAllIn_InitialState == *initialState && !emsmallens)) {
+        resultClips->reset();
+    } else {
+        int clipsToSkip = 0;
+        while (1) {
+            SkClipStack::Iter::Clip* clip = &(*resultClips)[clipsToSkip];
+            bool skippable = false;
+            switch (clip->fOp) {
+                case SkRegion::kDifference_Op:
+                    skippable = kAllOut_InitialState == *initialState;
+                    break;
+                case SkRegion::kIntersect_Op:
+                    skippable = kAllOut_InitialState == *initialState;
+                    break;
+                case SkRegion::kUnion_Op:
+                    if (kAllIn_InitialState == *initialState) {
+                        // unioning the infinite plane with anything is a no-op.
+                        skippable = true;
+                    } else {
+                        // unioning the empty set with a shape is the shape.
+                        clip->fOp = SkRegion::kReplace_Op;
+                    }
+                    break;
+                case SkRegion::kXOR_Op:
+                    if (kAllOut_InitialState == *initialState) {
+                        // xor could be changed to diff in the kAllIn case, not sure it's a win.
+                        clip->fOp = SkRegion::kReplace_Op;
+                    }
+                    break;
+                case SkRegion::kReverseDifference_Op:
+                    if (kAllIn_InitialState == *initialState) {
+                        // subtracting the whole plane will yield the empty set.
+                        skippable = true;
+                        *initialState = kAllOut_InitialState;
+                    } else {
+                        // this picks up flips inserted in the backwards pass.
+                        if (*resultsAreBounded && NULL != clip->fRect) {
+                            skippable = clip->isInverseFilled() ?
+                                !SkRect::Intersects(clip->getBounds(), *resultBounds) :
+                                clip->contains(*resultBounds);
+                        }
+                        if (skippable) {
+                            *initialState = kAllIn_InitialState;
+                        } else {
+                            clip->fOp = SkRegion::kReplace_Op;
+                        }
+                    }
+                    break;
+                case SkRegion::kReplace_Op:
+                    SkASSERT(!clipsToSkip); // replace should always be the first op
+                    skippable = false; // we would have skipped it in the backwards walk if we
+                                       // could've.
+                    break;
+                default:
+                    SkDEBUGFAIL("Unexpected op.");
+                    break;
+            }
+            if (!skippable) {
+                break;
+            } else {
+                ++clipsToSkip;
+                if (clipsToSkip == resultClips->count()) {
+                    break;
+                }
+            }
+        }
+        resultClips->remove(0, clipsToSkip);
+    }
+}
+} // namespace GrReducedClip
+
+////////////////////////////////////////////////////////////////////////////////
 namespace {
 // set up the draw state to enable the aa clipping mask. Besides setting up the
 // stage matrix this also alters the vertex layout
diff --git a/src/gpu/GrClipMaskManager.h b/src/gpu/GrClipMaskManager.h
index 89b1ef8249..4894a3a70c 100644
--- a/src/gpu/GrClipMaskManager.h
+++ b/src/gpu/GrClipMaskManager.h
@@ -157,4 +157,29 @@ private:
     typedef GrNoncopyable INHERITED;
 };
 
+
+namespace GrReducedClip {
+
+enum InitialState {
+    kAllIn_InitialState,
+    kAllOut_InitialState,
+};
+
+/** This function takes a clip stack and produces a reduced set of SkClipStack::Iter::Clip elements
+ *  in param clips that are equivalent to the full stack. If a finite bound for the area inside the
+ *  clip can be determined resultsAreBounds will be true and resultBounds will be those bounds. When
+ *  the results are bounded it is assumed that the caller will restrict the effect of each operation
+ *  to the bounds or intersect with the bounds as a final step. The initial state of the bounds (or
+ *  the unbounded plane when resultsArBounded is false) before the first element of clips is applied
+ *  is returned via initialState. This function is declared here so that it can be unit-tested. It
+ *  may become a member function of SkClipStack when its interface is determined to be stable.
+ */
+void GrReduceClipStack(const SkClipStack& stack,
+                       SkTDArray<SkClipStack::Iter::Clip>* resultClips,
+                       SkRect* resultBounds,
+                       bool* resultsAreBounded,
+                       InitialState* initialState);
+
+} // namespace GrReducedClip
+
 #endif // GrClipMaskManager_DEFINED