1 files changed, 490 insertions, 0 deletions
diff --git a/gfx/skia/skia/src/pathops/SkOpSpan.cpp b/gfx/skia/skia/src/pathops/SkOpSpan.cpp
new file mode 100644
index 0000000000..a7e898915a
--- /dev/null
+++ b/gfx/skia/skia/src/pathops/SkOpSpan.cpp
@@ -0,0 +1,490 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "include/core/SkPoint.h"
+#include "include/core/SkTypes.h"
+#include "include/private/base/SkTemplates.h"
+#include "src/pathops/SkOpCoincidence.h"
+#include "src/pathops/SkOpContour.h"
+#include "src/pathops/SkOpSegment.h"
+#include "src/pathops/SkOpSpan.h"
+#include "src/pathops/SkPathOpsTypes.h"
+
+#include <algorithm>
+
+bool SkOpPtT::alias() const {
+    return this->span()->ptT() != this;
+}
+
+const SkOpPtT* SkOpPtT::active() const {
+    if (!fDeleted) {
+        return this;
+    }
+    const SkOpPtT* ptT = this;
+    const SkOpPtT* stopPtT = ptT;
+    while ((ptT = ptT->next()) != stopPtT) {
+        if (ptT->fSpan == fSpan && !ptT->fDeleted) {
+            return ptT;
+        }
+    }
+    return nullptr; // should never return deleted; caller must abort
+}
+
+bool SkOpPtT::contains(const SkOpPtT* check) const {
+    SkOPASSERT(this != check);
+    const SkOpPtT* ptT = this;
+    const SkOpPtT* stopPtT = ptT;
+    while ((ptT = ptT->next()) != stopPtT) {
+        if (ptT == check) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool SkOpPtT::contains(const SkOpSegment* segment, const SkPoint& pt) const {
+    SkASSERT(this->segment() != segment);
+    const SkOpPtT* ptT = this;
+    const SkOpPtT* stopPtT = ptT;
+    while ((ptT = ptT->next()) != stopPtT) {
+        if (ptT->fPt == pt && ptT->segment() == segment) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool SkOpPtT::contains(const SkOpSegment* segment, double t) const {
+    const SkOpPtT* ptT = this;
+    const SkOpPtT* stopPtT = ptT;
+    while ((ptT = ptT->next()) != stopPtT) {
+        if (ptT->fT == t && ptT->segment() == segment) {
+            return true;
+        }
+    }
+    return false;
+}
+
+const SkOpPtT* SkOpPtT::contains(const SkOpSegment* check) const {
+    SkASSERT(this->segment() != check);
+    const SkOpPtT* ptT = this;
+    const SkOpPtT* stopPtT = ptT;
+    while ((ptT = ptT->next()) != stopPtT) {
+        if (ptT->segment() == check && !ptT->deleted()) {
+            return ptT;
+        }
+    }
+    return nullptr;
+}
+
+SkOpContour* SkOpPtT::contour() const {
+    return segment()->contour();
+}
+
+const SkOpPtT* SkOpPtT::find(const SkOpSegment* segment) const {
+    const SkOpPtT* ptT = this;
+    const SkOpPtT* stopPtT = ptT;
+    do {
+        if (ptT->segment() == segment && !ptT->deleted()) {
+            return ptT;
+        }
+        ptT = ptT->fNext;
+    } while (stopPtT != ptT);
+//    SkASSERT(0);
+    return nullptr;
+}
+
+SkOpGlobalState* SkOpPtT::globalState() const {
+    return contour()->globalState();
+}
+
+void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) {
+    fT = t;
+    fPt = pt;
+    fSpan = span;
+    fNext = this;
+    fDuplicatePt = duplicate;
+    fDeleted = false;
+    fCoincident = false;
+    SkDEBUGCODE(fID = span->globalState()->nextPtTID());
+}
+
+bool SkOpPtT::onEnd() const {
+    const SkOpSpanBase* span = this->span();
+    if (span->ptT() != this) {
+        return false;
+    }
+    const SkOpSegment* segment = this->segment();
+    return span == segment->head() || span == segment->tail();
+}
+
+bool SkOpPtT::ptAlreadySeen(const SkOpPtT* check) const {
+    while (this != check) {
+        if (this->fPt == check->fPt) {
+            return true;
+        }
+        check = check->fNext;
+    }
+    return false;
+}
+
+SkOpPtT* SkOpPtT::prev() {
+    SkOpPtT* result = this;
+    SkOpPtT* next = this;
+    while ((next = next->fNext) != this) {
+        result = next;
+    }
+    SkASSERT(result->fNext == this);
+    return result;
+}
+
+const SkOpSegment* SkOpPtT::segment() const {
+    return span()->segment();
+}
+
+SkOpSegment* SkOpPtT::segment() {
+    return span()->segment();
+}
+
+void SkOpPtT::setDeleted() {
+    SkASSERT(this->span()->debugDeleted() || this->span()->ptT() != this);
+    SkOPASSERT(!fDeleted);
+    fDeleted = true;
+}
+
+bool SkOpSpanBase::addOpp(SkOpSpanBase* opp) {
+    SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
+    if (!oppPrev) {
+        return true;
+    }
+    FAIL_IF(!this->mergeMatches(opp));
+    this->ptT()->addOpp(opp->ptT(), oppPrev);
+    this->checkForCollapsedCoincidence();
+    return true;
+}
+
+SkOpSpanBase::Collapsed SkOpSpanBase::collapsed(double s, double e) const {
+    const SkOpPtT* start = &fPtT;
+    const SkOpPtT* startNext = nullptr;
+    const SkOpPtT* walk = start;
+    double min = walk->fT;
+    double max = min;
+    const SkOpSegment* segment = this->segment();
+    int safetyNet = 100000;
+    while ((walk = walk->next()) != start) {
+        if (!--safetyNet) {
+            return Collapsed::kError;
+        }
+        if (walk == startNext) {
+            return Collapsed::kError;
+        }
+        if (walk->segment() != segment) {
+            continue;
+        }
+        min = std::min(min, walk->fT);
+        max = std::max(max, walk->fT);
+        if (between(min, s, max) && between(min, e, max)) {
+            return Collapsed::kYes;
+        }
+        startNext = start->next();
+    }
+    return Collapsed::kNo;
+}
+
+bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
+    const SkOpPtT* start = &fPtT;
+    const SkOpPtT* check = &span->fPtT;
+    SkOPASSERT(start != check);
+    const SkOpPtT* walk = start;
+    while ((walk = walk->next()) != start) {
+        if (walk == check) {
+            return true;
+        }
+    }
+    return false;
+}
+
+const SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) const {
+    const SkOpPtT* start = &fPtT;
+    const SkOpPtT* walk = start;
+    while ((walk = walk->next()) != start) {
+        if (walk->deleted()) {
+            continue;
+        }
+        if (walk->segment() == segment && walk->span()->ptT() == walk) {
+            return walk;
+        }
+    }
+    return nullptr;
+}
+
+bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
+    SkASSERT(this->segment() != segment);
+    const SkOpSpanBase* next = this;
+    while ((next = next->fCoinEnd) != this) {
+        if (next->segment() == segment) {
+            return true;
+        }
+    }
+    return false;
+}
+
+SkOpContour* SkOpSpanBase::contour() const {
+    return segment()->contour();
+}
+
+SkOpGlobalState* SkOpSpanBase::globalState() const {
+    return contour()->globalState();
+}
+
+void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
+    fSegment = segment;
+    fPtT.init(this, t, pt, false);
+    fCoinEnd = this;
+    fFromAngle = nullptr;
+    fPrev = prev;
+    fSpanAdds = 0;
+    fAligned = true;
+    fChased = false;
+    SkDEBUGCODE(fCount = 1);
+    SkDEBUGCODE(fID = globalState()->nextSpanID());
+    SkDEBUGCODE(fDebugDeleted = false);
+}
+
+// this pair of spans share a common t value or point; merge them and eliminate duplicates
+// this does not compute the best t or pt value; this merely moves all data into a single list
+void SkOpSpanBase::merge(SkOpSpan* span) {
+    SkOpPtT* spanPtT = span->ptT();
+    SkASSERT(this->t() != spanPtT->fT);
+    SkASSERT(!zero_or_one(spanPtT->fT));
+    span->release(this->ptT());
+    if (this->contains(span)) {
+        SkOPASSERT(0);  // check to see if this ever happens -- should have been found earlier
+        return;  // merge is already in the ptT loop
+    }
+    SkOpPtT* remainder = spanPtT->next();
+    this->ptT()->insert(spanPtT);
+    while (remainder != spanPtT) {
+        SkOpPtT* next = remainder->next();
+        SkOpPtT* compare = spanPtT->next();
+        while (compare != spanPtT) {
+            SkOpPtT* nextC = compare->next();
+            if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
+                goto tryNextRemainder;
+            }
+            compare = nextC;
+        }
+        spanPtT->insert(remainder);
+tryNextRemainder:
+        remainder = next;
+    }
+    fSpanAdds += span->fSpanAdds;
+}
+
+// please keep in sync with debugCheckForCollapsedCoincidence()
+void SkOpSpanBase::checkForCollapsedCoincidence() {
+    SkOpCoincidence* coins = this->globalState()->coincidence();
+    if (coins->isEmpty()) {
+        return;
+    }
+// the insert above may have put both ends of a coincident run in the same span
+// for each coincident ptT in loop; see if its opposite in is also in the loop
+// this implementation is the motivation for marking that a ptT is referenced by a coincident span
+    SkOpPtT* head = this->ptT();
+    SkOpPtT* test = head;
+    do {
+        if (!test->coincident()) {
+            continue;
+        }
+        coins->markCollapsed(test);
+    } while ((test = test->next()) != head);
+    coins->releaseDeleted();
+}
+
+// please keep in sync with debugMergeMatches()
+// Look to see if pt-t linked list contains same segment more than once
+// if so, and if each pt-t is directly pointed to by spans in that segment,
+// merge them
+// keep the points, but remove spans so that the segment doesn't have 2 or more
+// spans pointing to the same pt-t loop at different loop elements
+bool SkOpSpanBase::mergeMatches(SkOpSpanBase* opp) {
+    SkOpPtT* test = &fPtT;
+    SkOpPtT* testNext;
+    const SkOpPtT* stop = test;
+    int safetyHatch = 1000000;
+    do {
+        if (!--safetyHatch) {
+            return false;
+        }
+        testNext = test->next();
+        if (test->deleted()) {
+            continue;
+        }
+        SkOpSpanBase* testBase = test->span();
+        SkASSERT(testBase->ptT() == test);
+        SkOpSegment* segment = test->segment();
+        if (segment->done()) {
+            continue;
+        }
+        SkOpPtT* inner = opp->ptT();
+        const SkOpPtT* innerStop = inner;
+        do {
+            if (inner->segment() != segment) {
+                continue;
+            }
+            if (inner->deleted()) {
+                continue;
+            }
+            SkOpSpanBase* innerBase = inner->span();
+            SkASSERT(innerBase->ptT() == inner);
+            // when the intersection is first detected, the span base is marked if there are
+            // more than one point in the intersection.
+            if (!zero_or_one(inner->fT)) {
+                innerBase->upCast()->release(test);
+            } else {
+                SkOPASSERT(inner->fT != test->fT);
+                if (!zero_or_one(test->fT)) {
+                    testBase->upCast()->release(inner);
+                } else {
+                    segment->markAllDone();  // mark segment as collapsed
+                    SkDEBUGCODE(testBase->debugSetDeleted());
+                    test->setDeleted();
+                    SkDEBUGCODE(innerBase->debugSetDeleted());
+                    inner->setDeleted();
+                }
+            }
+#ifdef SK_DEBUG   // assert if another undeleted entry points to segment
+            const SkOpPtT* debugInner = inner;
+            while ((debugInner = debugInner->next()) != innerStop) {
+                if (debugInner->segment() != segment) {
+                    continue;
+                }
+                if (debugInner->deleted()) {
+                    continue;
+                }
+                SkOPASSERT(0);
+            }
+#endif
+            break;
+        } while ((inner = inner->next()) != innerStop);
+    } while ((test = testNext) != stop);
+    this->checkForCollapsedCoincidence();
+    return true;
+}
+
+int SkOpSpan::computeWindSum() {
+    SkOpGlobalState* globals = this->globalState();
+    SkOpContour* contourHead = globals->contourHead();
+    int windTry = 0;
+    while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
+    }
+    return this->windSum();
+}
+
+bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
+    SkASSERT(this->segment() != segment);
+    const SkOpSpan* next = fCoincident;
+    do {
+        if (next->segment() == segment) {
+            return true;
+        }
+    } while ((next = next->fCoincident) != this);
+    return false;
+}
+
+void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
+    SkASSERT(t != 1);
+    initBase(segment, prev, t, pt);
+    fCoincident = this;
+    fToAngle = nullptr;
+    fWindSum = fOppSum = SK_MinS32;
+    fWindValue = 1;
+    fOppValue = 0;
+    fTopTTry = 0;
+    fChased = fDone = false;
+    segment->bumpCount();
+    fAlreadyAdded = false;
+}
+
+// Please keep this in sync with debugInsertCoincidence()
+bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped, bool ordered) {
+    if (this->containsCoincidence(segment)) {
+        return true;
+    }
+    SkOpPtT* next = &fPtT;
+    while ((next = next->next()) != &fPtT) {
+        if (next->segment() == segment) {
+            SkOpSpan* span;
+            SkOpSpanBase* base = next->span();
+            if (!ordered) {
+                const SkOpPtT* spanEndPtT = fNext->contains(segment);
+                FAIL_IF(!spanEndPtT);
+                const SkOpSpanBase* spanEnd = spanEndPtT->span();
+                const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT());
+                FAIL_IF(!start->span()->upCastable());
+                span = const_cast<SkOpSpan*>(start->span()->upCast());
+            } else if (flipped) {
+                span = base->prev();
+                FAIL_IF(!span);
+            } else {
+                FAIL_IF(!base->upCastable());
+                span = base->upCast();
+            }
+            this->insertCoincidence(span);
+            return true;
+        }
+    }
+#if DEBUG_COINCIDENCE
+    SkASSERT(0); // FIXME? if we get here, the span is missing its opposite segment...
+#endif
+    return true;
+}
+
+void SkOpSpan::release(const SkOpPtT* kept) {
+    SkDEBUGCODE(fDebugDeleted = true);
+    SkOPASSERT(kept->span() != this);
+    SkASSERT(!final());
+    SkOpSpan* prev = this->prev();
+    SkASSERT(prev);
+    SkOpSpanBase* next = this->next();
+    SkASSERT(next);
+    prev->setNext(next);
+    next->setPrev(prev);
+    this->segment()->release(this);
+    SkOpCoincidence* coincidence = this->globalState()->coincidence();
+    if (coincidence) {
+        coincidence->fixUp(this->ptT(), kept);
+    }
+    this->ptT()->setDeleted();
+    SkOpPtT* stopPtT = this->ptT();
+    SkOpPtT* testPtT = stopPtT;
+    const SkOpSpanBase* keptSpan = kept->span();
+    do {
+        if (this == testPtT->span()) {
+            testPtT->setSpan(keptSpan);
+        }
+    } while ((testPtT = testPtT->next()) != stopPtT);
+}
+
+void SkOpSpan::setOppSum(int oppSum) {
+    SkASSERT(!final());
+    if (fOppSum != SK_MinS32 && fOppSum != oppSum) {
+        this->globalState()->setWindingFailed();
+        return;
+    }
+    SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(oppSum) <= DEBUG_LIMIT_WIND_SUM);
+    fOppSum = oppSum;
+}
+
+void SkOpSpan::setWindSum(int windSum) {
+    SkASSERT(!final());
+    if (fWindSum != SK_MinS32 && fWindSum != windSum) {
+        this->globalState()->setWindingFailed();
+        return;
+    }
+    SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM);
+    fWindSum = windSum;
+}