interpolation of coincidence must be local to a single span

Pathops makes up intersections that it doesn't detect directly,
but do exist. For instance, if a is coincident with b, and
b is coincident with c, then for where they overlap
a is coincident with c.

The intersections are made up in different ways. In a few
places, the t values that are detected are interpolated to
guess the t values that represent invented intersections.

The interpolated t is not necessarily linear, but a linear
guess is good enough if the invented t lies between known
t values.

Additionally, improve debugging.

This passes the extended release test suite and additionally
passes the first 17 levels in the tiger test suite;
previously, path ops passed 7 levels.

The tiger suite is composed of 37 levels in increasing
complexity, described by about 300K tests.

TBR=reed@google.com
BUG=skia:5131
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2300203002

Review-Url: https://codereview.chromium.org/2300203002

5 files changed, 280 insertions, 174 deletions

diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp
index 831ce71190..61ea3ef444 100755
--- a/src/pathops/SkOpCoincidence.cpp
+++ b/src/pathops/SkOpCoincidence.cpp
@@ -308,7 +308,7 @@ bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase*
             SkOpSegment* coinSeg = base->segment();
             SkOpSegment* oppSeg = oppStart->segment();
             double coinTs, coinTe, oppTs, oppTe;
-            if (coinSeg < oppSeg) {
+            if (Ordered(coinSeg, oppSeg)) {
                 coinTs = base->t();
                 coinTe = testSpan->t();
                 oppTs = oppStart->fT;
@@ -416,6 +416,8 @@ bool SkOpCoincidence::addExpanded() {
     do {
         const SkOpPtT* startPtT = coin->coinPtTStart();
         const SkOpPtT* oStartPtT = coin->oppPtTStart();
+        double priorT = startPtT->fT;
+        double oPriorT = oStartPtT->fT;
         SkASSERT(startPtT->contains(oStartPtT));
         SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
         const SkOpSpanBase* start = startPtT->span();
@@ -427,23 +429,47 @@ bool SkOpCoincidence::addExpanded() {
         const SkOpSpanBase* test = start->upCast()->next();
         const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
         FAIL_IF(!oTest);
+        SkOpSegment* seg = start->segment();
+        SkOpSegment* oSeg = oStart->segment();
         while (test != end || oTest != oEnd) {
-            if (!test->ptT()->contains(oStart->segment())
-                    || !oTest->ptT()->contains(start->segment())) {
+            const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
+            const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
+            if (!containedOpp || !containedThis) {
+                // choose the ends, or the first common pt-t list shared by both
+                double nextT, oNextT;
+                if (containedOpp) {
+                    nextT = test->t();
+                    oNextT = containedOpp->fT;
+                } else if (containedThis) {
+                    nextT = containedThis->fT;
+                    oNextT = oTest->t();
+                } else {
+                    // iterate through until a pt-t list found that contains the other
+                    const SkOpSpanBase* walk = test;
+                    const SkOpPtT* walkOpp;
+                    do {
+                        FAIL_IF(!walk->upCastable());
+                        walk = walk->upCast()->next();
+                    } while (!(walkOpp = walk->ptT()->contains(oSeg))
+                            && walk != coin->coinPtTEnd()->span());
+                    nextT = walk->t();
+                    oNextT = walkOpp->fT;
+                }
                 // use t ranges to guess which one is missing
-                double startRange = coin->coinPtTEnd()->fT - startPtT->fT;
+                double startRange = nextT - priorT;
                 FAIL_IF(!startRange);
-                double startPart = (test->t() - startPtT->fT) / startRange;
-                double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT;
+                double startPart = (test->t() - priorT) / startRange;
+                double oStartRange = oNextT - oPriorT;
                 FAIL_IF(!oStartRange);
-                double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
+                double oStartPart = (oTest->t() - oPriorT) / oStartRange;
                 FAIL_IF(startPart == oStartPart);
+                bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
+                        : !!containedThis;
                 bool startOver = false;
-                bool success = startPart < oStartPart
-                        ? oStart->segment()->addExpanded(
-                                oStartPtT->fT + oStartRange * startPart, test, &startOver)
-                        : start->segment()->addExpanded(
-                                startPtT->fT + startRange * oStartPart, oTest, &startOver);
+                bool success = addToOpp ? oSeg->addExpanded(
+                        oPriorT + oStartRange * startPart, test, &startOver)
+                        : seg->addExpanded(
+                        priorT + startRange * oStartPart, oTest, &startOver);
                 FAIL_IF(!success);
                 if (startOver) {
                     test = start;
@@ -454,12 +480,15 @@ bool SkOpCoincidence::addExpanded() {
             }
             if (test != end) {
                 FAIL_IF(!test->upCastable());
+                priorT = test->t();
                 test = test->upCast()->next();
             }
             if (oTest != oEnd) {
+                oPriorT = oTest->t();
                 oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
                 FAIL_IF(!oTest);
             }
+
         }
     } while ((coin = coin->next()));
     return true;
@@ -507,16 +536,40 @@ bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over
 }
 
 // given a t span, map the same range on the coincident span
-void SkOpCoincidence::TRange(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;
+/*
+the curves may not scale linearly, so interpolation may only happen within known points
+remap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s
+then repeat to capture over1e
+*/
+double SkOpCoincidence::TRange(const SkOpPtT* overS, double t,
+       const SkOpSegment* coinSeg  SkDEBUGPARAMS(const SkOpPtT* overE)) {
+    const SkOpSpanBase* work = overS->span();
+    const SkOpPtT* foundStart = nullptr;
+    const SkOpPtT* foundEnd = nullptr;
+    const SkOpPtT* coinStart = nullptr;
+    const SkOpPtT* coinEnd = nullptr;
+    do {
+        const SkOpPtT* contained = work->contains(coinSeg);
+        if (!contained) {
+            continue;
+        }
+        if (work->t() <= t) {
+            coinStart = contained;
+            foundStart = work->ptT();
+        }
+        if (work->t() >= t) {
+            coinEnd = contained;
+            foundEnd = work->ptT();
+            break;
+        }
+        SkASSERT(work->ptT() != overE);
+    } while ((work = work->upCast()->next()));
+    SkASSERT(coinStart);
+    SkASSERT(coinEnd);
+    // while overS->fT <=t and overS contains coinSeg
+    double denom = foundEnd->fT - foundStart->fT;
+    double sRatio = denom ? (t - foundStart->fT) / denom : 1;
+    return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio;
 }
 
 // return true if span overlaps existing and needs to adjust the coincident list
@@ -568,36 +621,40 @@ bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check,
 }
 
 /* Please keep this in sync with debugAddIfMissing() */
-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) {
-    SkOpSegment* coinSeg = coinPtTStart->segment();
-    SkOpSegment* oppSeg = oppPtTStart->segment();
-    if (coinSeg == oppSeg) {
-        return false;
-    }
+// note that over1s, over1e, over2s, over2e are ordered
+bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
+        double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg  
+        SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) {
+    SkASSERT(tStart < tEnd);
+    SkASSERT(over1s->fT < over1e->fT);
+    SkASSERT(between(over1s->fT, tStart, over1e->fT));
+    SkASSERT(between(over1s->fT, tEnd, over1e->fT));
+    SkASSERT(over2s->fT < over2e->fT);
+    SkASSERT(between(over2s->fT, tStart, over2e->fT));
+    SkASSERT(between(over2s->fT, tEnd, over2e->fT));
+    SkASSERT(over1s->segment() == over1e->segment());
+    SkASSERT(over2s->segment() == over2e->segment());
+    SkASSERT(over1s->segment() == over2s->segment());
+    SkASSERT(over1s->segment() != coinSeg);
+    SkASSERT(over1s->segment() != oppSeg);
+    SkASSERT(coinSeg != oppSeg);
     double coinTs, coinTe, oppTs, oppTe;
-    TRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
+    coinTs = TRange(over1s, tStart, coinSeg  SkDEBUGPARAMS(over1e));
+    coinTe = TRange(over1s, tEnd, coinSeg  SkDEBUGPARAMS(over1e));
     if (coinSeg->collapsed(coinTs, coinTe)) {
         return false;
     }
-    TRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
+    oppTs = TRange(over2s, tStart, oppSeg  SkDEBUGPARAMS(over2e));
+    oppTe = TRange(over2s, tEnd, oppSeg  SkDEBUGPARAMS(over2e));
     if (oppSeg->collapsed(oppTs, oppTe)) {
         return false;
     }
-    bool swap = coinTs > coinTe;
-    if (swap) {
+    if (coinTs > coinTe) {
         SkTSwap(coinTs, coinTe);
-    }
-    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
-        SkTSwap(oppTs, oppTe);
-    }
-    if (swap) {
         SkTSwap(oppTs, oppTe);
     }
     return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
-        SkDEBUGPARAMS(false) /* don't assert if addOrOverlap fails */ );
+            SkDEBUGPARAMS(false) /* don't assert if addOrOverlap fails */ );
 }
 
 /* Please keep this in sync with debugAddOrOverlap() */
@@ -733,55 +790,75 @@ bool SkOpCoincidence::addMissing() {
     // addifmissing can modify the list that this is walking
     // 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->coinPtTStart()->segment();
-        const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
-        if (outerCoin->done() || outerOpp->done()) {
-            continue;
-        }
+        const SkOpPtT* ocs = outer->coinPtTStart();
+        SkASSERT(!ocs->deleted());
+        const SkOpSegment* outerCoin = ocs->segment();
+        SkASSERT(!outerCoin->done());  // if it's done, should have already been removed from list
+        const SkOpPtT* oos = outer->oppPtTStart();
+        SkASSERT(!oos->deleted());
+        const SkOpSegment* outerOpp = oos->segment();
+        SkASSERT(!outerOpp->done());
+        SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
+        SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
         SkCoincidentSpans* inner = outer;
         while ((inner = inner->next())) {
             this->debugValidate();
             double overS, overE;
-            const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
-            const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
-            if (innerCoin->done() || innerOpp->done()) {
-                continue;
-            }
+            const SkOpPtT* ics = inner->coinPtTStart();
+            SkASSERT(!ics->deleted());
+            const SkOpSegment* innerCoin = ics->segment();
+            SkASSERT(!innerCoin->done());
+            const SkOpPtT* ios = inner->oppPtTStart();
+            SkASSERT(!ios->deleted());
+            const SkOpSegment* innerOpp = ios->segment();
+            SkASSERT(!innerOpp->done());
+            SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
+            SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
             if (outerCoin == innerCoin) {
-                if (outerOpp != innerOpp
-                        && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
-                        inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
-                    added |= this->addIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
-                            outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd());
+                const SkOpPtT* oce = outer->coinPtTEnd();
+                SkASSERT(!oce->deleted());
+                const SkOpPtT* ice = inner->coinPtTEnd();
+                SkASSERT(!ice->deleted());
+                if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
+                    added |= this->addIfMissing(ocs->starter(oce), ics->starter(ice),
+                            overS, overE, outerOppWritable, innerOppWritable
+                            SkDEBUGPARAMS(ocs->debugEnder(oce))
+                            SkDEBUGPARAMS(ics->debugEnder(ice)));
                 }
             } else if (outerCoin == innerOpp) {
-                if (outerOpp != innerCoin
-                        && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
-                        inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
-                    added |= this->addIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
-                            outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd());
+                const SkOpPtT* oce = outer->coinPtTEnd();
+                SkASSERT(!oce->deleted());
+                const SkOpPtT* ioe = inner->oppPtTEnd();
+                SkASSERT(!ioe->deleted());
+                if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
+                    added |= this->addIfMissing(ocs->starter(oce), ios->starter(ioe),
+                            overS, overE, outerOppWritable, innerCoinWritable
+                            SkDEBUGPARAMS(ocs->debugEnder(oce))
+                            SkDEBUGPARAMS(ios->debugEnder(ioe)));
                 }
             } else if (outerOpp == innerCoin) {
+                const SkOpPtT* ooe = outer->oppPtTEnd();
+                SkASSERT(!ooe->deleted());
+                const SkOpPtT* ice = inner->coinPtTEnd();
+                SkASSERT(!ice->deleted());
                 SkASSERT(outerCoin != innerOpp);
-                if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
-                        inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
-                    added |= this->addIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
-                            outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd());
+                if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
+                    added |= this->addIfMissing(oos->starter(ooe), ics->starter(ice),
+                            overS, overE, outerCoinWritable, innerOppWritable
+                            SkDEBUGPARAMS(oos->debugEnder(ooe))
+                            SkDEBUGPARAMS(ics->debugEnder(ice)));
                 }
             } else if (outerOpp == innerOpp) {
+                const SkOpPtT* ooe = outer->oppPtTEnd();
+                SkASSERT(!ooe->deleted());
+                const SkOpPtT* ioe = inner->oppPtTEnd();
+                SkASSERT(!ioe->deleted());
                 SkASSERT(outerCoin != innerCoin);
-                if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
-                        inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
-                    added |= this->addIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
-                            outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd());
+                if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
+                    added |= this->addIfMissing(oos->starter(ooe), ios->starter(ioe),
+                            overS, overE, outerCoinWritable, innerCoinWritable
+                            SkDEBUGPARAMS(oos->debugEnder(ooe))
+                            SkDEBUGPARAMS(ios->debugEnder(ioe)));
                 }
             }
             this->debugValidate();
diff --git a/src/pathops/SkOpCoincidence.h b/src/pathops/SkOpCoincidence.h
index eeeb7344dc..e399ee2641 100644
--- a/src/pathops/SkOpCoincidence.h
+++ b/src/pathops/SkOpCoincidence.h
@@ -250,22 +250,9 @@ private:
         return addIfMissing(outer, const_cast<SkOpPtT*>(over1s), const_cast<SkOpPtT*>(over1e));
     }
 
-    bool 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);
-
-    bool addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
-                      const SkOpPtT* over2s, const SkOpPtT* over2e,
-                      double tStart, double tEnd,
-                      const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
-                      const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
-        return addIfMissing(over1s, over1e, over2s, over2e, tStart, tEnd,
-                const_cast<SkOpPtT*>(coinPtTStart), coinPtTEnd,
-                const_cast<SkOpPtT*>(oppPtTStart), oppPtTEnd);
-    }
-
+    bool addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
+                      double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg
+                      SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e));
     bool addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
                       double coinTs, double coinTe, double oppTs, double oppTe
                       SkDEBUGPARAMS(bool callerAborts));
@@ -282,14 +269,14 @@ private:
     bool contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
                   const SkOpSegment* opp, double oppT) const;
 #if DEBUG_COINCIDENCE_VERBOSE
-    void debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
-                           const SkOpPtT* over1e, const char* id, SkPathOpsDebug::GlitchLog*) const;
-    void debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
-                           const SkOpPtT* over2s, const SkOpPtT* over2e,
+    void debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* ,
+                           const SkCoincidentSpans* outer, const SkOpPtT* over1s,
+                           const SkOpPtT* over1e) const;
+    void debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* ,
+                           const SkOpPtT* over1s, const SkOpPtT* over2s,
                            double tStart, double tEnd,
-                           const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
-                           const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd,
-                           const char* id, SkPathOpsDebug::GlitchLog*) const;
+                           const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
+                           const SkOpPtT* over1e, const SkOpPtT* over2e) const;
 #endif
     void fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept);
     void markCollapsed(SkCoincidentSpans* head, SkOpPtT* test);
@@ -301,9 +288,9 @@ private:
     void restoreHead();
     bool testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS,
                             const SkOpPtT* testE) const;
-    static void TRange(const SkOpPtT* overS, const SkOpPtT* overE, double tStart,
-                       double tEnd, const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
-                       double* coinTs, double* coinTe);
+    // return coinPtT->segment()->t mapped from overS->fT <= t <= overE->fT
+    static double TRange(const SkOpPtT* overS, double t, const SkOpSegment* coinPtT
+                         SkDEBUGPARAMS(const SkOpPtT* overE));
 
     SkCoincidentSpans* fHead;
     SkCoincidentSpans* fTop;
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 6a62175032..484ddca412 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -258,9 +258,9 @@ bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* start
         return false;
     }
     newPtT->fPt = this->ptAtT(newT);
-    // const cast away to change linked list; pt/t values stays unchanged
     SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT);
     if (oppPrev) {
+        // const cast away to change linked list; pt/t values stays unchanged
         SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test);
         writableTest->mergeMatches(newPtT->span());
         writableTest->ptT()->addOpp(newPtT, oppPrev);
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index 7c7bf7c186..14bb7120a0 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -58,6 +58,7 @@ public:
     bool debugContains(const SkOpPtT* ) const;
     const SkOpPtT* debugContains(const SkOpSegment* check) const;
     SkOpContour* debugContour(int id) const;
+    const SkOpPtT* debugEnder(const SkOpPtT* end) const;
     int debugLoopLimit(bool report) const;
     bool debugMatchID(int id) const;
     const SkOpPtT* debugOppPrev(const SkOpPtT* opp) const;
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index d099c4a985..b5b42c40e7 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -63,6 +63,7 @@ enum GlitchType {
     kAddCorruptCoin_Glitch,
     kAddExpandedCoin_Glitch,
     kAddExpandedFail_Glitch,
+    kAddIfCollapsed_Glitch,
     kAddIfMissingCoin_Glitch,
     kAddMissingCoin_Glitch,
     kAddMissingExtend_Glitch,
@@ -286,22 +287,26 @@ void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
         const SpanGlitch& glitch = glitches.fGlitches[index];
         SkDebugf("%02d: ", index);
         if (glitch.fBase) {
-            SkDebugf(" base=%d", glitch.fBase->debugID());
+            SkDebugf(" seg/base=%d/%d", glitch.fBase->segment()->debugID(),
+                    glitch.fBase->debugID());
         }
         if (glitch.fSuspect) {
-            SkDebugf(" base=%d", glitch.fSuspect->debugID());
+            SkDebugf(" seg/base=%d/%d", glitch.fSuspect->segment()->debugID(),
+                    glitch.fSuspect->debugID());
         }
         if (glitch.fSegment) {
             SkDebugf(" segment=%d", glitch.fSegment->debugID());
         }
         if (glitch.fCoinSpan) {
-            SkDebugf(" coinSpan=%d", glitch.fCoinSpan->debugID());
+            SkDebugf(" coinSeg/Span/PtT=%d/%d/%d", glitch.fCoinSpan->segment()->debugID(),
+                    glitch.fCoinSpan->span()->debugID(), glitch.fCoinSpan->debugID());
         }
         if (glitch.fEndSpan) {
             SkDebugf(" endSpan=%d", glitch.fEndSpan->debugID());
         }
         if (glitch.fOppSpan) {
-            SkDebugf(" oppSpan=%d", glitch.fOppSpan->debugID());
+            SkDebugf(" oppSeg/Span/PtT=%d/%d/%d", glitch.fOppSpan->segment()->debugID(),
+                    glitch.fOppSpan->span()->debugID(), glitch.fOppSpan->debugID());
         }
         if (glitch.fOppEndSpan) {
             SkDebugf(" oppEndSpan=%d", glitch.fOppEndSpan->debugID());
@@ -328,6 +333,7 @@ void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
             case kAddCorruptCoin_Glitch: SkDebugf(" AddCorruptCoin"); break;
             case kAddExpandedCoin_Glitch: SkDebugf(" AddExpandedCoin"); break;
             case kAddExpandedFail_Glitch: SkDebugf(" AddExpandedFail"); break;
+            case kAddIfCollapsed_Glitch: SkDebugf(" AddIfCollapsed"); break;; break;
             case kAddIfMissingCoin_Glitch: SkDebugf(" AddIfMissingCoin"); break;
             case kAddMissingCoin_Glitch: SkDebugf(" AddMissingCoin"); break;
             case kAddMissingExtend_Glitch: SkDebugf(" AddMissingExtend"); break;
@@ -364,7 +370,7 @@ void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
         SkDebugf("\n");
     }
     contourList->globalState()->debugSetCheckHealth(false);
-#if DEBUG_ACTIVE_SPANS
+#if 0 && DEBUG_ACTIVE_SPANS
     SkDebugf("active after %s:\n", id);
     ShowActiveSpans(contourList);
 #endif
@@ -1370,8 +1376,8 @@ void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog
 }
 
 /* Commented-out lines keep this in sync with addIfMissing() */
-void SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
-            const SkOpPtT* over1e, const char* id, SkPathOpsDebug::GlitchLog* log) const {
+void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* outer, const SkOpPtT* over1s,
+            const SkOpPtT* over1e) const {
 //     SkASSERT(fTop);
     if (fTop && alreadyAdded(fTop, outer, over1s, over1e)) {  // in debug, fTop may be null
         return;
@@ -1385,29 +1391,40 @@ void SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const Sk
 }
 
 /* Commented-out lines keep this in sync addIfMissing() */
-void SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
-        const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
-        const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
-        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, const char* id, SkPathOpsDebug::GlitchLog* log) const {
+// note that over1s, over1e, over2s, over2e are ordered
+void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* over1s, const SkOpPtT* over2s,
+        double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
+        const SkOpPtT* over1e, const SkOpPtT* over2e) const {
+    SkASSERT(tStart < tEnd);
+    SkASSERT(over1s->fT < over1e->fT);
+    SkASSERT(between(over1s->fT, tStart, over1e->fT));
+    SkASSERT(between(over1s->fT, tEnd, over1e->fT));
+    SkASSERT(over2s->fT < over2e->fT);
+    SkASSERT(between(over2s->fT, tStart, over2e->fT));
+    SkASSERT(between(over2s->fT, tEnd, over2e->fT));
+    SkASSERT(over1s->segment() == over1e->segment());
+    SkASSERT(over2s->segment() == over2e->segment());
+    SkASSERT(over1s->segment() == over2s->segment());
+    SkASSERT(over1s->segment() != coinSeg);
+    SkASSERT(over1s->segment() != oppSeg);
+    SkASSERT(coinSeg != oppSeg);
     double coinTs, coinTe, oppTs, oppTe;
-    TRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
-    TRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
-    bool swap = coinTs > coinTe;
-    if (swap) {
-        SkTSwap(coinTs, coinTe);
+    coinTs = TRange(over1s, tStart, coinSeg  SkDEBUGPARAMS(over1e));
+    coinTe = TRange(over1s, tEnd, coinSeg  SkDEBUGPARAMS(over1e));
+    if (coinSeg->collapsed(coinTs, coinTe)) {
+        return log->record(kAddIfCollapsed_Glitch, id, coinSeg);
     }
-    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
-        SkTSwap(oppTs, oppTe);
+    oppTs = TRange(over2s, tStart, oppSeg  SkDEBUGPARAMS(over2e));
+    oppTe = TRange(over2s, tEnd, oppSeg  SkDEBUGPARAMS(over2e));
+    if (oppSeg->collapsed(oppTs, oppTe)) {
+        return log->record(kAddIfCollapsed_Glitch, id, oppSeg);
     }
-    if (swap) {
+    if (coinTs > coinTe) {
+        SkTSwap(coinTs, coinTe);
         SkTSwap(oppTs, oppTe);
     }
-    const SkOpSegment* coinSeg = coinPtTStart->segment();
-    const SkOpSegment* oppSeg = oppPtTStart->segment();
-    if (coinSeg == oppSeg) {
-        return;
-    }
-    return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe);
+    return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
+            );
 }
 
 /* Commented-out lines keep this in sync addOrOverlap() */
@@ -1500,8 +1517,8 @@ void SkOpCoincidence::debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLo
     RETURN_FALSE_IF(osDeleted, oppSeg); 
     RETURN_FALSE_IF(ceDeleted, coinSeg); 
     RETURN_FALSE_IF(oeDeleted, oppSeg);
-    RETURN_FALSE_IF(!cs || !ce || cs->contains(ce) || !os || !oe || os->contains(oe), coinSeg);
-//     bool result = true;
+    RETURN_FALSE_IF(!cs || !ce || cs == ce || cs->contains(ce) || !os || !oe || os == oe || os->contains(oe), coinSeg);
+    bool result = true;
     if (overlap) {
         if (overlap->coinPtTStart()->segment() == coinSeg) {
                 log->record(kAddMissingExtend_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
@@ -1512,19 +1529,19 @@ void SkOpCoincidence::debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLo
             }
             log->record(kAddMissingExtend_Glitch, id, oppSeg, oppTs, oppTe, coinSeg, coinTs, coinTe);
         }
-#if DEBUG_COINCIDENCE_VERBOSE
-//         if (result) {
-//             overlap->debugShow();
-//         }
+#if 0 && DEBUG_COINCIDENCE_VERBOSE
+        if (result) {
+             overlap->debugShow();
+        }
 #endif
     } else {
         log->record(kAddMissingCoin_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
-#if DEBUG_COINCIDENCE_VERBOSE
-//         fHead->debugShow();
+#if 0 && DEBUG_COINCIDENCE_VERBOSE
+        fHead->debugShow();
 #endif
     }
     this->debugValidate();
-    return;
+    return (void) result;
 }
 
 // Extra commented-out lines keep this in sync with addMissing()
@@ -1543,55 +1560,75 @@ void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog*
     // addifmissing can modify the list that this is walking
     // 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->coinPtTStart()->segment();
-        const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
-        if (outerCoin->done() || outerOpp->done()) {
-            continue;
-        }
+        const SkOpPtT* ocs = outer->coinPtTStart();
+        SkASSERT(!ocs->deleted());
+        const SkOpSegment* outerCoin = ocs->segment();
+        SkASSERT(!outerCoin->done());  // if it's done, should have already been removed from list
+        const SkOpPtT* oos = outer->oppPtTStart();
+        SkASSERT(!oos->deleted());
+        const SkOpSegment* outerOpp = oos->segment();
+        SkASSERT(!outerOpp->done());
+//        SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
+//        SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
         const SkCoincidentSpans* inner = outer;
         while ((inner = inner->next())) {
             this->debugValidate();
             double overS, overE;
-            const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
-            const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
-            if (innerCoin->done() || innerOpp->done()) {
-                continue;
-            }
+            const SkOpPtT* ics = inner->coinPtTStart();
+            SkASSERT(!ics->deleted());
+            const SkOpSegment* innerCoin = ics->segment();
+            SkASSERT(!innerCoin->done());
+            const SkOpPtT* ios = inner->oppPtTStart();
+            SkASSERT(!ios->deleted());
+            const SkOpSegment* innerOpp = ios->segment();
+            SkASSERT(!innerOpp->done());
+//            SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
+//            SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
             if (outerCoin == innerCoin) {
-                if (outerOpp != innerOpp
-                        && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
-                        inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
-                    this->debugAddIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
-                            outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), id, log);
+                const SkOpPtT* oce = outer->coinPtTEnd();
+                SkASSERT(!oce->deleted());
+                const SkOpPtT* ice = inner->coinPtTEnd();
+                SkASSERT(!ice->deleted());
+                if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
+                    this->debugAddIfMissing(id, log, ocs->starter(oce), ics->starter(ice),
+                            overS, overE, outerOpp, innerOpp,
+                            ocs->debugEnder(oce),
+                            ics->debugEnder(ice));
                 }
             } else if (outerCoin == innerOpp) {
-                if (outerOpp != innerCoin
-                        && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
-                        inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
-                    this->debugAddIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
-                            outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), id, log);
+                const SkOpPtT* oce = outer->coinPtTEnd();
+                SkASSERT(!oce->deleted());
+                const SkOpPtT* ioe = inner->oppPtTEnd();
+                SkASSERT(!ioe->deleted());
+                if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
+                    this->debugAddIfMissing(id, log, ocs->starter(oce), ios->starter(ioe),
+                            overS, overE, outerOpp, innerCoin,
+                            ocs->debugEnder(oce),
+                            ios->debugEnder(ioe));
                 }
             } else if (outerOpp == innerCoin) {
+                const SkOpPtT* ooe = outer->oppPtTEnd();
+                SkASSERT(!ooe->deleted());
+                const SkOpPtT* ice = inner->coinPtTEnd();
+                SkASSERT(!ice->deleted());
                 SkASSERT(outerCoin != innerOpp);
-                if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
-                        inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
-                    this->debugAddIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
-                            outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), id, log);
+                if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
+                    this->debugAddIfMissing(id, log, oos->starter(ooe), ics->starter(ice),
+                            overS, overE, outerCoin, innerOpp,
+                            oos->debugEnder(ooe),
+                            ics->debugEnder(ice));
                 }
             } else if (outerOpp == innerOpp) {
+                const SkOpPtT* ooe = outer->oppPtTEnd();
+                SkASSERT(!ooe->deleted());
+                const SkOpPtT* ioe = inner->oppPtTEnd();
+                SkASSERT(!ioe->deleted());
                 SkASSERT(outerCoin != innerCoin);
-                if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
-                        inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
-                    this->debugAddIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
-                            outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), id, log);
+                if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
+                    this->debugAddIfMissing(id, log, oos->starter(ooe), ios->starter(ioe),
+                            overS, overE, outerCoin, innerCoin,
+                            oos->debugEnder(ooe),
+                            ios->debugEnder(ioe));
                 }
             }
             this->debugValidate();
@@ -2442,6 +2479,10 @@ const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
     } while (true);
 }
 
+const SkOpPtT* SkOpPtT::debugEnder(const SkOpPtT* end) const {
+    return fT < end->fT ? end : this;
+}
+
 int SkOpPtT::debugLoopLimit(bool report) const {
     int loop = 0;
     const SkOpPtT* next = this;