fix some pathops bugs found in 1M skps

src/pathops/SkOpCoincidence.cpp

 /*
  * Copyright 2015 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkOpCoincidence.h"
 #include "SkOpSegment.h"
 #include "SkPathOpsTSect.h"
 
@@ skipping 33 matching lines @@
         SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
     SkASSERT(coinPtTStart->fT < coinPtTEnd->fT);
     bool flipped = oppPtTStart->fT > oppPtTEnd->fT;
     SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator);
     coinRec->fNext = this->fHead;
     coinRec->fCoinPtTStart = coinPtTStart;
     coinRec->fCoinPtTEnd = coinPtTEnd;
     coinRec->fOppPtTStart = oppPtTStart;
     coinRec->fOppPtTEnd = oppPtTEnd;
     coinRec->fFlipped = flipped;
+    SkDEBUGCODE(coinRec->fID = fDebugState->nextCoinID());
+
     this->fHead = coinRec;
 }
 
 static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
         const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
     double denom = overE->fT - overS->fT;
     double start = 0 < denom ? tStart : tEnd;
     double end = 0 < denom ? tEnd : tStart;
     double sRatio = (start - overS->fT) / denom;
     double eRatio = (end - overS->fT) / denom;
     *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
     *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
 }
 
-void SkOpCoincidence::addExpanded(SkChunkAlloc* allocator
+bool SkOpCoincidence::addExpanded(SkChunkAlloc* allocator
         PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* globalState)) {
 #if DEBUG_VALIDATE
     globalState->setPhase(SkOpGlobalState::kIntersecting);
 #endif
     // for each coincident pair, match the spans
     // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
     SkCoincidentSpans* coin = this->fHead;
     SkASSERT(coin);
     do {
         SkOpPtT* startPtT = coin->fCoinPtTStart;
         SkOpPtT* oStartPtT = coin->fOppPtTStart;
         SkASSERT(startPtT->contains(oStartPtT));
         SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
         SkOpSpanBase* start = startPtT->span();
         SkOpSpanBase* oStart = oStartPtT->span();
         const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
         const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
         SkOpSpanBase* test = start->upCast()->next();
         SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
         while (test != end || oTest != oEnd) {
             if (!test->ptT()->contains(oTest->ptT())) {
                 // use t ranges to guess which one is missing
                 double startRange = coin->fCoinPtTEnd->fT - startPtT->fT;
                 double startPart = (test->t() - startPtT->fT) / startRange;
                 double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT;
                 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
-                SkASSERT(startPart != oStartPart);
+                if (startPart == oStartPart) {
+                    return false;
+                }
                 SkOpPtT* newPt;
                 if (startPart < oStartPart) {
                     double newT = oStartPtT->fT + oStartRange * startPart;
                     newPt = oStart->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator);
                     newPt->fPt = test->pt();
                     test->ptT()->addOpp(newPt);
                 } else {
                     double newT = startPtT->fT + startRange * oStartPart;
                     newPt = start->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator);
                     newPt->fPt = oTest->pt();
                     oTest->ptT()->addOpp(newPt);
                 }
                 // start over
                 test = start;
                 oTest = oStart;
             }
             if (test != end) {
                 test = test->upCast()->next();
             }
-            if (oStart != oEnd) {
+            if (oTest != oEnd) {
                 oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
             }
         }
     } while ((coin = coin->fNext));
 #if DEBUG_VALIDATE
     globalState->setPhase(SkOpGlobalState::kWalking);
 #endif
+    return true;
 }
 
-void SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s,
+bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s,
             SkOpPtT* over1e, SkChunkAlloc* allocator) {
     SkCoincidentSpans* check = this->fTop;
     do {
         if (check->fCoinPtTStart->span() == over1s->span()
                 && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) {
             SkASSERT(check->fCoinPtTEnd->span() == over1e->span()
                     || !fDebugState->debugRunFail());
             SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span()
                     || !fDebugState->debugRunFail());
-            return;
+            return false;
         }
         if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span()
                 && check->fOppPtTStart->span() == over1s->span()) {
             SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span()
                     || !fDebugState->debugRunFail());
             SkASSERT(check->fOppPtTEnd->span() == over1e->span()
                     || !fDebugState->debugRunFail());
-            return;
+            return false;
         }
     } while ((check = check->fNext));
     this->add(outer->fCoinPtTStart, outer->fCoinPtTEnd, over1s, over1e, allocator);
 #if 0
     // FIXME: up to four flavors could be added -- do we need only one?
 #endif
+    return true;
 }
 
 bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
                       const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
         SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
         SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
     double coinTs, coinTe, oppTs, oppTe;
     t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
     t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
     SkOpSegment* coinSeg = coinPtTStart->segment();
@@ skipping 17 matching lines @@
             SkASSERT(checkOppSeg != oppSeg);
             SkTSwap(cTs, oTs);
             SkTSwap(cTe, oTe);
         }
         int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT)
                        + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT)
                        + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT)
                        + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT);
 //        SkASSERT(tweenCount == 0 || tweenCount == 4);
         if (tweenCount) {
-            return true;
+            return false;
         }
     } while ((check = check->fNext));
     if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
         SkTSwap(oppTs, oppTe);
     }
     if (coinTs > coinTe) {
         SkTSwap(coinTs, coinTe);
         SkTSwap(oppTs, oppTe);
     }
     SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator);
     SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator);
-    if (cs == ce) {
-        return false;
-    }
+    SkASSERT(cs != ce);
     SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator);
     SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator);
     SkASSERT(os != oe);
     cs->addOpp(os);
     ce->addOpp(oe);
     this->add(cs, ce, os, oe, allocator);
     return true;
 }
 
 /* detects overlaps of different coincident runs on same segment */
 /* does not detect overlaps for pairs without any segments in common */
 bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) {
     SkCoincidentSpans* outer = fHead;
     if (!outer) {
         return true;
     }
-    bool result;
+    bool added = false;
     fTop = outer;
     fHead = nullptr;
     do {
     // addifmissing can modify the list that this is walking
-    // maybe save head so that walker can iterate over old data unperturbed
-    // and addifmissing can add to head freely then add saved head in the end
+    // save head so that walker can iterate over old data unperturbed
+    // addifmissing adds to head freely then add saved head in the end
         const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
         SkASSERT(outerCoin == outer->fCoinPtTEnd->segment());
         const SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
         SkASSERT(outerOpp == outer->fOppPtTEnd->segment());
         SkCoincidentSpans* inner = outer;
         while ((inner = inner->fNext)) {
             double overS, overE;
             const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
             SkASSERT(innerCoin == inner->fCoinPtTEnd->segment());
             const SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
             SkASSERT(innerOpp == inner->fOppPtTEnd->segment());
             if (outerCoin == innerCoin
                     && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
                     inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
-                if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
                         inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
                         outer->fOppPtTStart, outer->fOppPtTEnd,
-                        inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) {
-                    result = false;
-                    goto returnResult;
-                }
+                        inner->fOppPtTStart, inner->fOppPtTEnd, allocator);
             } else if (outerCoin == innerOpp
                     && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
                     inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
-                if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
                         inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
                         outer->fOppPtTStart, outer->fOppPtTEnd,
-                        inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) {
-                    result = false;
-                    goto returnResult;
-                }
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator);
             } else if (outerOpp == innerCoin
                     && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
                     inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
-                if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
+                added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
                         inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
                         outer->fCoinPtTStart, outer->fCoinPtTEnd,
-                        inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) {
-                    result = false;
-                    goto returnResult;
-                }
+                        inner->fOppPtTStart, inner->fOppPtTEnd, allocator);
             } else if (outerOpp == innerOpp
                     && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
                     inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
-                if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
+                added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
                         inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
                         outer->fCoinPtTStart, outer->fCoinPtTEnd,
-                        inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) {
-                    result = false;
-                    goto returnResult;
-                }
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator);
             } else if (outerCoin != innerCoin) {
                 // check to see if outer span overlaps the inner span
                     // look for inner segment in pt-t list
                     // if present, and if t values are in coincident range
                     // add two pairs of new coincidence
                 SkOpPtT* testS = outer->fCoinPtTStart->contains(innerCoin);
                 SkOpPtT* testE = outer->fCoinPtTEnd->contains(innerCoin);
                 if (testS && testS->fT >= inner->fCoinPtTStart->fT
                         && testE && testE->fT <= inner->fCoinPtTEnd->fT
                         && this->testForCoincidence(outer, testS, testE)) {
-                    this->addIfMissing(outer, testS, testE, allocator);
+                    added |= this->addIfMissing(outer, testS, testE, allocator);
                 } else {
                     testS = inner->fCoinPtTStart->contains(outerCoin);
                     testE = inner->fCoinPtTEnd->contains(outerCoin);
                     if (testS && testS->fT >= outer->fCoinPtTStart->fT
                             && testE && testE->fT <= outer->fCoinPtTEnd->fT
                             && this->testForCoincidence(inner, testS, testE)) {
-                        this->addIfMissing(inner, testS, testE, allocator);
+                        added |= this->addIfMissing(inner, testS, testE, allocator);
                     }
                 }
             }
+#if 0 && DEBUG_COINCIDENCE
+            SkString miss;
+            miss.printf("addMissing inner=%d outer=%d", inner->debugID(), outer->debugID());
+            DEBUG_COINCIDENCE_HEALTH(fDebugState->contourHead(), miss.c_str());
+#endif
         }
     } while ((outer = outer->fNext));
-    result = true;
-returnResult:
     SkCoincidentSpans** headPtr = &fHead;
     while (*headPtr) {
         SkCoincidentSpans** headNext = &(*headPtr)->fNext;
         if (*headNext) {
             break;
         }
         headPtr = headNext;
     }
     *headPtr = fTop;
-    return result;
+    return added;
 }
 
 void SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegment* seg2,
         SkOpSegment* seg2o, SkOpPtT* overS, SkOpPtT* overE, SkChunkAlloc* allocator) {
     SkOpPtT* s1 = overS->find(seg1);
     SkOpPtT* e1 = overE->find(seg1);
     if (!s1->starter(e1)->span()->upCast()->windValue()) {
         s1 = overS->find(seg1o);
         e1 = overE->find(seg1o);
         if (!s1->starter(e1)->span()->upCast()->windValue()) {
@@ skipping 12 matching lines @@
     if (s1->segment() == s2->segment()) {
         return;
     }
     if (s1->fT > e1->fT) {
         SkTSwap(s1, e1);
         SkTSwap(s2, e2);
     }
     this->add(s1, e1, s2, e2, allocator);
 }
 
-bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
-        SkOpPtT* oppPtTEnd, bool flipped) {
-    SkCoincidentSpans* coin = fHead;
+bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
+        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, bool flipped) const {
+    const SkCoincidentSpans* coin = fHead;
     if (!coin) {
         return false;
     }
     do {
         if (coin->fCoinPtTStart == coinPtTStart &&  coin->fCoinPtTEnd == coinPtTEnd
                 && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd
                 && coin->fFlipped == flipped) {
             return true;
         }
     } while ((coin = coin->fNext));
@@ skipping 91 matching lines @@
                 segment->markDone(start);
             }
             if (!oWindValue && !oOppValue) {
                 oSegment->markDone(oStart);
             }
             SkOpSpanBase* next = start->next();
             SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
             if (next == end) {
                 break;
             }
+            if (!next->upCastable()) {
+                return false;
+            }
             start = next->upCast();
             // if the opposite ran out too soon, just reuse the last span
             if (!oNext || !oNext->upCastable()) {
                oNext = oStart;
             }
             oStart = oNext->upCast();
         } while (true);
     } while ((coin = coin->fNext));
     return true;
 }
@@ skipping 188 matching lines @@
 }
 
 bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, 
         const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
     SkASSERT(coin1s->segment() == coin2s->segment());
     *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT));
     *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT));
     return *overS < *overE;
 }
 
-bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, SkOpPtT* testS,
-        SkOpPtT* testE) const {
+bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS,
+        const SkOpPtT* testE) const {
     return testS->segment()->testForCoincidence(testS, testE, testS->span(),
             testE->span(), outer->fCoinPtTStart->segment(), 120000);  // FIXME: replace with tuned
 }