fix some pathops bugs found in 1M skps

src/pathops/SkPathOpsDebug.cpp

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkMutex.h"
+#include "SkOpCoincidence.h"
+#include "SkOpContour.h"
 #include "SkPath.h"
 #include "SkPathOpsDebug.h"
 #include "SkString.h"
 
+struct SkCoincidentSpans;
+
 #if DEBUG_VALIDATE
 extern bool FLAGS_runFail;
 #endif
 
 #if DEBUG_SORT
 int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
 int SkPathOpsDebug::gSortCount;
 #endif
 
 #if DEBUG_ACTIVE_OP
 const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"};
 #endif
 
 #if defined SK_DEBUG || !FORCE_RELEASE
 
 const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
 
-#if defined(SK_DEBUG) || !FORCE_RELEASE
 int SkPathOpsDebug::gContourID = 0;
 int SkPathOpsDebug::gSegmentID = 0;
-#endif
 
 bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray,
         const SkOpSpanBase* span) {
     for (int index = 0; index < chaseArray.count(); ++index) {
         const SkOpSpanBase* entry = chaseArray[index];
         if (entry == span) {
             return true;
         }
     }
     return false;
 }
+#endif
 
+#if DEBUG_COINCIDENCE
+enum GlitchType {
+    kAddCorruptCoin_Glitch,
+    kAddExpandedCoin_Glitch,
+    kAddMissingCoin_Glitch,
+    kCollapsedCoin_Glitch,
+    kCollapsedDone_Glitch,
+    kCollapsedOppValue_Glitch,
+    kCollapsedSpan_Glitch,
+    kCollapsedWindValue_Glitch,
+    kDeletedCoin_Glitch,
+    kExpandCoin_Glitch,
+    kMarkCoinEnd_Glitch,
+    kMarkCoinInsert_Glitch,
+    kMissingCoin_Glitch,
+    kMissingDone_Glitch,
+    kMissingIntersection_Glitch,
+    kMoveMultiple_Glitch,
+    kUnaligned_Glitch,
+    kUnalignedHead_Glitch,
+    kUnalignedTail_Glitch,
+    kUndetachedSpan_Glitch,
+    kUnmergedSpan_Glitch,
+};
+
+static const int kGlitchType_Count = kUnmergedSpan_Glitch + 1;
+
+struct SpanGlitch {
+    const char* fStage;
+    const SkOpSpanBase* fBase;
+    const SkOpSpanBase* fSuspect;
+    const SkCoincidentSpans* fCoin;
+    const SkOpSegment* fSegment;
+    const SkOpPtT* fCoinSpan;
+    const SkOpPtT* fEndSpan;
+    const SkOpPtT* fOppSpan;
+    const SkOpPtT* fOppEndSpan;
+    double fT;
+    SkPoint fPt;
+    GlitchType fType;
+};
+
+struct SkPathOpsDebug::GlitchLog {
+    SpanGlitch* recordCommon(GlitchType type, const char* stage) {
+        SpanGlitch* glitch = fGlitches.push();
+        glitch->fStage = stage;
+        glitch->fBase = nullptr;
+        glitch->fSuspect = nullptr;
+        glitch->fCoin = nullptr;
+        glitch->fSegment = nullptr;
+        glitch->fCoinSpan = nullptr;
+        glitch->fEndSpan = nullptr;
+        glitch->fOppSpan = nullptr;
+        glitch->fOppEndSpan = nullptr;
+        glitch->fT = SK_ScalarNaN;
+        glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN };
+        glitch->fType = type;
+        return glitch;
+    }
+
+    void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
+            const SkOpSpanBase* suspect = NULL) {
+        SpanGlitch* glitch = recordCommon(type, stage);
+        glitch->fBase = base;
+        glitch->fSuspect = suspect;
+    }
+
+    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
+            const SkOpPtT* coinSpan) {
+        SpanGlitch* glitch = recordCommon(type, stage);
+        glitch->fCoin = coin;
+        glitch->fCoinSpan = coinSpan;
+    }
+
+    void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
+            const SkOpSegment* seg, double t, SkPoint pt) {
+        SpanGlitch* glitch = recordCommon(type, stage);
+        glitch->fBase = base;
+        glitch->fSegment = seg;
+        glitch->fT = t;
+        glitch->fPt = pt;
+    }
+
+    void record(GlitchType type, const char* stage, const SkOpSpanBase* base, double t,
+            SkPoint pt) {
+        SpanGlitch* glitch = recordCommon(type, stage);
+        glitch->fBase = base;
+        glitch->fT = t;
+        glitch->fPt = pt;
+    }
+
+    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
+            const SkOpPtT* coinSpan, const SkOpPtT* endSpan) {
+        SpanGlitch* glitch = recordCommon(type, stage);
+        glitch->fCoin = coin;
+        glitch->fCoinSpan = coinSpan;
+        glitch->fEndSpan = endSpan;
+    }
+
+    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
+            const SkOpSpanBase* suspect) {
+        SpanGlitch* glitch = recordCommon(type, stage);
+        glitch->fSuspect = suspect;
+        glitch->fCoin = coin;
+    }
+
+    void record(GlitchType type, const char* stage, const SkOpPtT* ptTS, const SkOpPtT* ptTE,
+            const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) {
+        SpanGlitch* glitch = recordCommon(type, stage);
+        glitch->fCoinSpan = ptTS;
+        glitch->fEndSpan = ptTE;
+        glitch->fOppSpan = oPtTS;
+        glitch->fOppEndSpan = oPtTE;
+    }
+
+    SkTDArray<SpanGlitch> fGlitches;
+};
+
+void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
+    GlitchLog glitches;
+    const SkOpContour* contour = contourList;
+    const SkOpCoincidence* coincidence = contour->globalState()->coincidence();
+    do {
+        contour->debugCheckHealth(id, &glitches);
+        contour->debugMissingCoincidence(id, &glitches, coincidence);
+    } while ((contour = contour->next()));
+    coincidence->debugFixAligned(id, &glitches);
+    coincidence->debugAddMissing(id, &glitches);
+    coincidence->debugExpand(id, &glitches);
+    coincidence->debugAddExpanded(id, &glitches);
+    coincidence->debugMark(id, &glitches);
+    unsigned mask = 0;
+    for (int index = 0; index < glitches.fGlitches.count(); ++index) {
+        const SpanGlitch& glitch = glitches.fGlitches[index];
+        mask |= 1 << glitch.fType;
+    }
+    for (int index = 0; index < kGlitchType_Count; ++index) {
+        SkDebugf(mask & (1 << index) ? "x" : "-");
+    }
+    SkDebugf("  %s\n", id);
+}
+#endif
+
+#if defined SK_DEBUG || !FORCE_RELEASE
 void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
     size_t len = strlen(str);
     bool num = false;
     for (size_t idx = 0; idx < len; ++idx) {
         if (num && str[idx] == 'e') {
             if (len + 2 >= bufferLen) {
                 return;
             }
             memmove(&str[idx + 2], &str[idx + 1], len - idx);
             str[idx] = '*';
@@ skipping 69 matching lines @@
 void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
         const char* testName) {
     SkAutoMutexAcquire ac(gTestMutex);
     show_function_header(testName);
     ShowOnePath(a, "path", true);
     ShowOnePath(b, "pathB", true);
     show_op(shapeOp, "path", "pathB");
 }
 
 #include "SkPathOpsTypes.h"
+#include "SkIntersectionHelper.h"
+#include "SkIntersections.h"
+
+#if DEBUG_T_SECT_LOOP_COUNT
+void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt,
+        const SkIntersectionHelper& wn) {
+    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
+        SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index;
+        if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) {
+            continue;
+        }
+        fDebugLoopCount[index] = i->debugLoopCount(looper);
+        fDebugWorstVerb[index * 2] = wt.segment()->verb();
+        fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb();
+        sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8);
+        memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(),
+                (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint));
+        memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(),
+                (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint));
+        fDebugWorstWeight[index * 2] = wt.weight();
+        fDebugWorstWeight[index * 2 + 1] = wn.weight();
+    }
+    i->debugResetLoopCount();
+}
+
+void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) {
+    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
+        if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) {
+            continue;
+        }
+        fDebugLoopCount[index] = local->fDebugLoopCount[index];
+        fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2];
+        fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1];
+        memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4],
+                sizeof(SkPoint) * 8);
+        fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2];
+        fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1];
+    }
+    local->debugResetLoopCounts();
+}
+
+static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) {
+    if (!verb) {
+        return;
+    }
+    const char* verbs[] = { "", "line", "quad", "conic", "cubic" };
+    SkDebugf("%s: {{", verbs[verb]);
+    int ptCount = SkPathOpsVerbToPoints(verb);
+    for (int index = 0; index <= ptCount; ++index) {
+        SkDPoint::Dump((&pts)[index]);
+        if (index < ptCount - 1) {
+            SkDebugf(", ");
+        }
+    }
+    SkDebugf("}");
+    if (weight != 1) {
+        SkDebugf(", ");
+        if (weight == floorf(weight)) {
+            SkDebugf("%.0f", weight);
+        } else {
+            SkDebugf("%1.9gf", weight);
+        }
+    }
+    SkDebugf("}\n");
+}
+
+void SkOpGlobalState::debugLoopReport() {
+    const char* loops[] = { "iterations", "coinChecks", "perpCalcs" };
+    SkDebugf("\n");
+    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
+        SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]);
+        dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4],
+                fDebugWorstWeight[index * 2]);
+        dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4],
+                fDebugWorstWeight[index * 2 + 1]);
+    }
+}
+
+void SkOpGlobalState::debugResetLoopCounts() {
+    sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
+    sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb));
+    sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts));
+    sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight));
+}
+#endif
 
 #ifdef SK_DEBUG
 bool SkOpGlobalState::debugRunFail() const {
 #if DEBUG_VALIDATE
     return FLAGS_runFail;
 #else
     return false;
 #endif
 }
 #endif
 
+#if DEBUG_T_SECT_LOOP_COUNT
+void SkIntersections::debugBumpLoopCount(DebugLoop index) {
+    fDebugLoopCount[index]++;
+}
+
+int SkIntersections::debugLoopCount(DebugLoop index) const {
+    return fDebugLoopCount[index];
+}
+
+void SkIntersections::debugResetLoopCount() {
+    sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
+}
+#endif
+
 #include "SkPathOpsCubic.h"
 #include "SkPathOpsQuad.h"
 
 SkDCubic SkDQuad::debugToCubic() const {
     SkDCubic cubic;
     cubic[0] = fPts[0];
     cubic[2] = fPts[1];
     cubic[3] = fPts[2];
     cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3;
     cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3;
     cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3;
     cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3;
     return cubic;
 }
 
 #include "SkOpAngle.h"
-#include "SkOpCoincidence.h"
 #include "SkOpSegment.h"
 
+#if DEBUG_COINCIDENCE
+void SkOpSegment::debugAddAlignIntersection(const char* id, SkPathOpsDebug::GlitchLog* log,
+        const SkOpPtT& endPtT, const SkPoint& oldPt,  const SkOpContourHead* contourList) const {
+    const SkPoint& newPt = endPtT.fPt;
+    if (newPt == oldPt) {
+        return;
+    }
+    SkPoint line[2] = { newPt, oldPt };
+    SkPathOpsBounds lineBounds;
+    lineBounds.setBounds(line, 2);
+    SkDLine aLine;
+    aLine.set(line);
+    const SkOpContour* current = contourList;
+    do {
+        if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) {
+            continue;
+        }
+        const SkOpSegment* segment = current->first();
+        do {
+            if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) {
+                continue;
+            }
+            if (newPt == segment->fPts[0]) {
+                continue;
+            }
+            if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
+                continue;
+            }
+            if (oldPt == segment->fPts[0]) {
+                continue;
+            }
+            if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
+                continue;
+            }
+            if (endPtT.debugContains(segment)) {
+                continue;
+            }
+            SkIntersections i;
+            switch (segment->fVerb) {
+                case SkPath::kLine_Verb: {
+                    SkDLine bLine;
+                    bLine.set(segment->fPts);
+                    i.intersect(bLine, aLine);
+                    } break;
+                case SkPath::kQuad_Verb: {
+                    SkDQuad bQuad;
+                    bQuad.set(segment->fPts);
+                    i.intersect(bQuad, aLine);
+                    } break;
+                case SkPath::kConic_Verb: {
+                    SkDConic bConic;
+                    bConic.set(segment->fPts, segment->fWeight);
+                    i.intersect(bConic, aLine);
+                    } break;
+                case SkPath::kCubic_Verb: {
+                    SkDCubic bCubic;
+                    bCubic.set(segment->fPts);
+                    i.intersect(bCubic, aLine);
+                    } break;
+                default:
+                    SkASSERT(0);
+            }
+            if (i.used()) {
+                SkASSERT(i.used() == 1);
+                SkASSERT(!zero_or_one(i[0][0]));
+                SkOpSpanBase* checkSpan = fHead.next();
+                while (!checkSpan->final()) {
+                    if (checkSpan->contains(segment)) {
+                        goto nextSegment;
+                    }
+                    checkSpan = checkSpan->upCast()->next();
+                }
+                log->record(kMissingIntersection_Glitch, id, checkSpan, segment, i[0][0], newPt);
+            }
+    nextSegment:
+            ;
+        } while ((segment = segment->next()));
+    } while ((current = current->next()));
+}
+
+bool SkOpSegment::debugAddMissing(double t, const SkOpSegment* opp) const {
+    const SkOpSpanBase* existing = nullptr;
+    const SkOpSpanBase* test = &fHead;
+    double testT;
+    do {
+        if ((testT = test->ptT()->fT) >= t) {
+            if (testT == t) {
+                existing = test;
+            }
+            break;
+        }
+    } while ((test = test->upCast()->next()));
+    return !existing || !existing->debugContains(opp);
+}
+
+void SkOpSegment::debugAlign(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
+    const SkOpSpanBase* span = &fHead;
+    if (!span->aligned()) {
+        if (!span->debugAlignedEnd(0, fPts[0])) {
+            glitches->record(kUnalignedHead_Glitch, id, span);
+        }
+    }
+    while ((span = span->upCast()->next())) {
+        if (span == &fTail) {
+            break;
+        }
+        if (!span->aligned()) {
+            glitches->record(kUnaligned_Glitch, id, span);
+        }
+    }
+    if (!span->aligned()) {
+        span->debugAlignedEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]);
+    }
+    if (this->collapsed()) {
+        const SkOpSpan* span = &fHead;
+        do {
+            if (span->windValue()) {
+                glitches->record(kCollapsedWindValue_Glitch, id, span);
+            }
+            if (span->oppValue()) {
+                glitches->record(kCollapsedOppValue_Glitch, id, span);
+            }
+            if (!span->done()) {
+                glitches->record(kCollapsedDone_Glitch, id, span);
+            }
+        } while ((span = span->next()->upCastable()));
+    }
+}
+#endif
+
+#if DEBUG_ANGLE
+void SkOpSegment::debugCheckAngleCoin() const {
+    const SkOpSpanBase* base = &fHead;
+    const SkOpSpan* span;
+    do {
+        const SkOpAngle* angle = base->fromAngle();
+        if (angle && angle->fCheckCoincidence) {
+            angle->debugCheckNearCoincidence();
+        }
+        if (base->final()) {
+             break;
+        }
+        span = base->upCast();
+        angle = span->toAngle();
+        if (angle && angle->fCheckCoincidence) {
+            angle->debugCheckNearCoincidence();
+        }
+    } while ((base = span->next()));
+}
+#endif
+
+#if DEBUG_COINCIDENCE
+// this mimics the order of the checks in handle coincidence
+void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
+    debugMoveMultiples(id, glitches);
+    debugFindCollapsed(id, glitches);
+    debugMoveNearby(id, glitches);
+    debugAlign(id, glitches);
+    debugAddAlignIntersections(id, glitches, this->globalState()->contourHead());
+
+}
+
+void SkOpSegment::debugFindCollapsed(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
+    if (fHead.contains(&fTail)) {
+        const SkOpSpan* span = this->head();
+        bool missingDone = false;
+        do {
+            missingDone |= !span->done();
+        } while ((span = span->next()->upCastable()));
+        if (missingDone) {
+            glitches->record(kMissingDone_Glitch, id, &fHead);
+        }
+        if (!fHead.debugAlignedEnd(0, fHead.pt())) {
+            glitches->record(kUnalignedHead_Glitch, id, &fHead);
+        }
+        if (!fTail.aligned()) {
+            glitches->record(kUnalignedTail_Glitch, id, &fTail);
+        }
+    }
+}
+#endif
+
 SkOpAngle* SkOpSegment::debugLastAngle() {
     SkOpAngle* result = nullptr;
     SkOpSpan* span = this->head();
     do {
         if (span->toAngle()) {
             SkASSERT(!result);
             result = span->toAngle();
         }
     } while ((span = span->next()->upCastable()));
     SkASSERT(result);
     return result;
 }
 
+#if DEBUG_COINCIDENCE
+void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
+        const SkOpCoincidence* coincidences) const {
+    if (this->verb() != SkPath::kLine_Verb) {
+        return;
+    }
+    if (this->done()) {
+        return;
+    }
+    const SkOpSpan* prior = nullptr;
+    const SkOpSpanBase* spanBase = &fHead;
+    do {
+        const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
+        SkASSERT(ptT->span() == spanBase);
+        while ((ptT = ptT->next()) != spanStopPtT) {
+            if (ptT->deleted()) {
+                continue;
+            }
+            SkOpSegment* opp = ptT->span()->segment();
+//            if (opp->verb() == SkPath::kLine_Verb) {
+//                continue;
+//            }
+            if (opp->done()) {
+                continue;
+            }
+            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
+            if (!opp->visited()) {
+                continue;
+            }
+            if (spanBase == &fHead) {
+                continue;
+            }
+            const SkOpSpan* span = spanBase->upCastable();
+            // FIXME?: this assumes that if the opposite segment is coincident then no more
+            // coincidence needs to be detected. This may not be true.
+            if (span && span->segment() != opp && span->containsCoincidence(opp)) {
+                continue;
+            }
+            if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) {
+                continue;
+            } 
+            const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
+            // find prior span containing opp segment
+            const SkOpSegment* priorOpp = nullptr;
+            const SkOpSpan* priorTest = spanBase->prev();
+            while (!priorOpp && priorTest) {
+                priorStopPtT = priorPtT = priorTest->ptT();
+                while ((priorPtT = priorPtT->next()) != priorStopPtT) {
+                    if (priorPtT->deleted()) {
+                        continue;
+                    }
+                    SkOpSegment* segment = priorPtT->span()->segment();
+                    if (segment == opp) {
+                        prior = priorTest;
+                        priorOpp = opp;
+                        break;
+                    }
+                }
+                priorTest = priorTest->prev();
+            }
+            if (!priorOpp) {
+                continue;
+            }
+            const SkOpPtT* oppStart = prior->ptT();
+            const SkOpPtT* oppEnd = spanBase->ptT();
+            bool swapped = priorPtT->fT > ptT->fT;
+            if (swapped) {
+                SkTSwap(priorPtT, ptT);
+                SkTSwap(oppStart, oppEnd);
+            }
+            bool flipped = oppStart->fT > oppEnd->fT;
+            bool coincident = false;
+            if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
+                goto swapBack;
+            }
+            if (opp->verb() == SkPath::kLine_Verb) {
+                coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) ||
+                        SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) &&
+                        (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) ||
+                        SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt));
+            }
+            if (!coincident) {
+                coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000);
+            }
+            if (coincident) {
+                log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd);
+            }
+    swapBack:
+            if (swapped) {
+                SkTSwap(priorPtT, ptT);
+            }
+        }
+    } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
+}
+
+void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
+    const SkOpSpanBase* test = &fHead;
+    do {
+        int addCount = test->spanAddsCount();
+        SkASSERT(addCount >= 1);
+        if (addCount == 1) {
+            continue;
+        }
+        const SkOpPtT* startPtT = test->ptT();
+        const SkOpPtT* testPtT = startPtT;
+        do {  // iterate through all spans associated with start
+            const SkOpSpanBase* oppSpan = testPtT->span();
+            if (oppSpan->spanAddsCount() == addCount) {
+                continue;
+            }
+            if (oppSpan->deleted()) {
+                continue;
+            }
+            const SkOpSegment* oppSegment = oppSpan->segment();
+            if (oppSegment == this) {
+                continue;
+            }
+            // find range of spans to consider merging
+            const SkOpSpanBase* oppPrev = oppSpan;
+            const SkOpSpanBase* oppFirst = oppSpan;
+            while ((oppPrev = oppPrev->prev())) {
+                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
+                    break;
+                }
+                if (oppPrev->spanAddsCount() == addCount) {
+                    continue;
+                }
+                if (oppPrev->deleted()) {
+                    continue;
+                }
+                oppFirst = oppPrev;
+            }
+            const SkOpSpanBase* oppNext = oppSpan;
+            const SkOpSpanBase* oppLast = oppSpan;
+            while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
+                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
+                    break;
+                }
+                if (oppNext->spanAddsCount() == addCount) {
+                    continue;
+                }
+                if (oppNext->deleted()) {
+                    continue;
+                }
+                oppLast = oppNext;
+            }
+            if (oppFirst == oppLast) {
+                continue;
+            }
+            const SkOpSpanBase* oppTest = oppFirst;
+            do {
+                if (oppTest == oppSpan) {
+                    continue;
+                }
+                // check to see if the candidate meets specific criteria:
+                // it contains spans of segments in test's loop but not including 'this'
+                const SkOpPtT* oppStartPtT = oppTest->ptT();
+                const SkOpPtT* oppPtT = oppStartPtT;
+                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
+                    const SkOpSegment* oppPtTSegment = oppPtT->segment();
+                    if (oppPtTSegment == this) {
+                        goto tryNextSpan;
+                    }
+                    const SkOpPtT* matchPtT = startPtT;
+                    do {
+                        if (matchPtT->segment() == oppPtTSegment) {
+                            goto foundMatch;
+                        }
+                    } while ((matchPtT = matchPtT->next()) != startPtT);
+                    goto tryNextSpan;
+            foundMatch:  // merge oppTest and oppSpan
+                    if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) {
+                        SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse
+                        SkASSERT(oppSpan != &oppSegment->fTail);
+                        glitches->record(kMoveMultiple_Glitch, id, oppTest, oppSpan);
+                    } else {
+                        glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest);
+                    }
+                    goto checkNextSpan;
+                }
+        tryNextSpan: 
+                ;
+            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
+        } while ((testPtT = testPtT->next()) != startPtT);
+checkNextSpan: 
+        ;
+    } while ((test = test->final() ? nullptr : test->upCast()->next()));
+}
+
+void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
+        const SkOpSpanBase* spanS = &fHead;
+    do {
+        const SkOpSpanBase* test = spanS->upCast()->next();
+        const SkOpSpanBase* next;
+        if (spanS->contains(test)) {
+            if (!test->final()) {
+                glitches->record(kUndetachedSpan_Glitch, id, test, spanS);
+            } else if (spanS != &fHead) {
+                glitches->record(kUndetachedSpan_Glitch, id, spanS, test);
+            }
+        }
+        do {  // iterate through all spans associated with start
+            const SkOpPtT* startBase = spanS->ptT();
+            next = test->final() ? nullptr : test->upCast()->next();
+            do {
+                const SkOpPtT* testBase = test->ptT();
+                do {
+                    if (startBase == testBase) {
+                        goto checkNextSpan;
+                    }
+                    if (testBase->duplicate()) {
+                        continue;
+                    }
+                    if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) {
+                        if (test == &this->fTail) {
+                            if (spanS == &fHead) {
+                                glitches->record(kCollapsedSpan_Glitch, id, spanS);
+                            } else {
+                                glitches->record(kUnmergedSpan_Glitch, id, &this->fTail, spanS);
+                            }
+                        } else {
+                            glitches->record(kUnmergedSpan_Glitch, id, spanS, test);
+                            goto checkNextSpan;
+                        }
+                    }
+                } while ((testBase = testBase->next()) != test->ptT());
+            } while ((startBase = startBase->next()) != spanS->ptT());
+    checkNextSpan:
+            ;
+        } while ((test = next));
+        spanS = spanS->upCast()->next();
+    } while (!spanS->final());
+}
+#endif
+
 void SkOpSegment::debugReset() {
     this->init(this->fPts, this->fWeight, this->contour(), this->verb());
 }
 
 #if DEBUG_ACTIVE_SPANS
 void SkOpSegment::debugShowActiveSpans() const {
     debugValidate();
     if (done()) {
         return;
     }
@@ skipping 94 matching lines @@
     if (span->windSum() == SK_MinS32) {
         SkDebugf("?");
     } else {
         SkDebugf("%d", span->windSum());
     }
     SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
 }
 
 #endif
 
+// loop looking for a pair of angle parts that are too close to be sorted
+/* This is called after other more simple intersection and angle sorting tests have been exhausted.
+   This should be rarely called -- the test below is thorough and time consuming.
+   This checks the distance between start points; the distance between 
+*/
+#if DEBUG_ANGLE
+void SkOpAngle::debugCheckNearCoincidence() const {
+    const SkOpAngle* test = this;
+    do {
+        const SkOpSegment* testSegment = test->segment();
+        double testStartT = test->start()->t();
+        SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
+        double testEndT = test->end()->t();
+        SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
+        double testLenSq = testStartPt.distanceSquared(testEndPt);
+        SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
+        double testMidT = (testStartT + testEndT) / 2;
+        const SkOpAngle* next = test;
+        while ((next = next->fNext) != this) {
+            SkOpSegment* nextSegment = next->segment();
+            double testMidDistSq = testSegment->distSq(testMidT, next);
+            double testEndDistSq = testSegment->distSq(testEndT, next);
+            double nextStartT = next->start()->t();
+            SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
+            double distSq = testStartPt.distanceSquared(nextStartPt);
+            double nextEndT = next->end()->t();
+            double nextMidT = (nextStartT + nextEndT) / 2;
+            double nextMidDistSq = nextSegment->distSq(nextMidT, test);
+            double nextEndDistSq = nextSegment->distSq(nextEndT, test);
+            SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
+                    testSegment->debugID(), nextSegment->debugID());
+            SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
+            SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
+            SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
+            SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
+            SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
+            double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
+            SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
+            SkDebugf("\n");
+        }
+        test = test->fNext;
+    } while (test->fNext != this); 
+}
+#endif
+
 #if DEBUG_ANGLE
 SkString SkOpAngle::debugPart() const {
     SkString result;
     switch (this->segment()->verb()) {
         case SkPath::kLine_Verb:
             result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart),
                     this->segment()->debugID());
             break;
         case SkPath::kQuad_Verb:
             result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
@@ skipping 88 matching lines @@
             break;
         }
         SK_ALWAYSBREAK(!angles.contains(next));
         if (!next) {
             return;
         }
     } while (true);
 #endif
 }
 
+
+#if DEBUG_COINCIDENCE
+void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+    // 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
+    const SkCoincidentSpans* coin = this->fHead;
+    if (!coin) {
+        coin = this->fTop;
+    }
+    SkASSERT(coin);
+    do {
+        const SkOpPtT* startPtT = coin->fCoinPtTStart;
+        const SkOpPtT* oStartPtT = coin->fOppPtTStart;
+        SkASSERT(startPtT->contains(oStartPtT));
+        SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
+        const SkOpSpanBase* start = startPtT->span();
+        const SkOpSpanBase* oStart = oStartPtT->span();
+        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
+        const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
+        const SkOpSpanBase* test = start->upCast()->next();
+        const SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
+        while (test != end || oTest != oEnd) {
+            bool bumpTest = true;
+            bool bumpOTest = true;
+            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;
+                if (startPart == oStartPart) {
+                    // data is corrupt
+                    log->record(kAddCorruptCoin_Glitch, id, start, oStart);
+                    break;
+                }
+                if (startPart < oStartPart) {
+                    double newT = oStartPtT->fT + oStartRange * startPart;
+                    log->record(kAddExpandedCoin_Glitch, id, oStart, newT, test->pt());
+                    bumpOTest = false;
+                } else {
+                    double newT = startPtT->fT + startRange * oStartPart;
+                    log->record(kAddExpandedCoin_Glitch, id, start, newT, oTest->pt());
+                    bumpTest = false;
+                }
+            }
+            if (bumpTest && test != end) {
+                test = test->upCast()->next();
+            }
+            if (bumpOTest && oTest != oEnd) {
+                oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
+            }
+        }
+    } while ((coin = coin->fNext));
+}
+
+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;
+}
+
+bool SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
+            const SkOpPtT* over1e) const {
+    const SkCoincidentSpans* check = this->fTop;
+    while (check) {
+        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 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 false;
+        }
+        check = check->fNext;
+    }
+    return true;
+}
+
+bool SkOpCoincidence::debugAddIfMissing(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) const {
+    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);
+    const SkOpSegment* coinSeg = coinPtTStart->segment();
+    const SkOpSegment* oppSeg = oppPtTStart->segment();
+    SkASSERT(coinSeg != oppSeg);
+    const SkCoincidentSpans* check = this->fTop;
+    ;
+    while (check) {
+        const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment();
+        const SkOpSegment* checkOppSeg;
+        if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) {
+            goto next;
+        }
+        checkOppSeg = check->fOppPtTStart->segment();
+        if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) {
+            goto next;
+        }
+        {
+            int cTs = coinTs;
+            int cTe = coinTe;
+            int oTs = oppTs;
+            int oTe = oppTe;
+            if (checkCoinSeg != coinSeg) {
+                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;
+            }
+        }
+next:
+        check = check->fNext;
+    }
+    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
+        SkTSwap(oppTs, oppTe);
+    }
+    if (coinTs > coinTe) {
+        SkTSwap(coinTs, coinTe);
+        SkTSwap(oppTs, oppTe);
+    }
+    bool cs = coinSeg->debugAddMissing(coinTs, oppSeg);
+    bool ce = coinSeg->debugAddMissing(coinTe, oppSeg);
+    if (cs == ce) {
+        return false;
+    }
+    return true;
+}
+
+void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+    const SkCoincidentSpans* outer = fHead;
+    if (!outer) {
+        return;
+    }
+    do {
+    // 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->fCoinPtTStart->segment();
+        SkASSERT(outerCoin == outer->fCoinPtTEnd->segment());
+        const SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
+        SkASSERT(outerOpp == outer->fOppPtTEnd->segment());
+        const 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->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
+                        outer->fOppPtTStart, outer->fOppPtTEnd,
+                        inner->fOppPtTStart, inner->fOppPtTEnd)) {
+                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart);
+                }
+            } else if (outerCoin == innerOpp
+                    && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
+                if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
+                        outer->fOppPtTStart, outer->fOppPtTEnd,
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd)) {
+                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart);
+                }
+            } else if (outerOpp == innerCoin
+                    && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
+                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
+                if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
+                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                        inner->fOppPtTStart, inner->fOppPtTEnd)) {
+                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart);
+                }
+            } else if (outerOpp == innerOpp
+                    && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
+                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
+                if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
+                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
+                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd)) {
+                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart);
+                }
+            } 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
+                const SkOpPtT* testS = outer->fCoinPtTStart->debugContains(innerCoin);
+                const SkOpPtT* testE = outer->fCoinPtTEnd->debugContains(innerCoin);
+                if (testS && testS->fT >= inner->fCoinPtTStart->fT
+                        && testE && testE->fT <= inner->fCoinPtTEnd->fT
+                        && this->testForCoincidence(outer, testS, testE)) {
+                    if (this->debugAddIfMissing(outer, testS, testE)) {
+                        log->record(kAddMissingCoin_Glitch, id, outer, testS, testE);
+                    }
+                } else {
+                    testS = inner->fCoinPtTStart->debugContains(outerCoin);
+                    testE = inner->fCoinPtTEnd->debugContains(outerCoin);
+                    if (testS && testS->fT >= outer->fCoinPtTStart->fT
+                            && testE && testE->fT <= outer->fCoinPtTEnd->fT
+                            && this->testForCoincidence(inner, testS, testE)) {
+                        if (this->debugAddIfMissing(inner, testS, testE)) {
+                            log->record(kAddMissingCoin_Glitch, id, inner, testS, testE);
+                        }
+                    }
+                }
+            }
+        }
+    } while ((outer = outer->fNext));
+}
+
+bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+    const SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return false;
+    }
+    bool expanded = false;
+    do {
+        const SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
+        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
+        const SkOpSegment* segment = coin->fCoinPtTStart->segment();
+        const SkOpSegment* oppSegment = coin->fOppPtTStart->segment();
+        const SkOpSpan* prev = start->prev();
+        if (prev && prev->debugContains(oppSegment)) {
+            double midT = (prev->t() + start->t()) / 2;
+            if (segment->isClose(midT, oppSegment)) {
+                log->record(kExpandCoin_Glitch, id, coin, prev);
+            }
+        }
+        SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
+        if (next && next->debugContains(oppSegment)) {
+            double midT = (end->t() + next->t()) / 2;
+            if (segment->isClose(midT, oppSegment)) {
+                log->record(kExpandCoin_Glitch, id, coin, next);
+            }
+        }
+    } while ((coin = coin->fNext));
+    return expanded;
+}
+
+void SkOpCoincidence::debugFixAligned(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+    const SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return;
+    }
+    do {
+        if (coin->fCoinPtTStart->deleted()) {
+            log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTStart);
+        }
+        if (coin->fCoinPtTEnd->deleted()) {
+            log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTEnd);
+        }
+        if (coin->fOppPtTStart->deleted()) {
+            log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTStart);
+        }
+        if (coin->fOppPtTEnd->deleted()) {
+            log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTEnd);
+        }
+    } while ((coin = coin->fNext));
+    coin = fHead;
+    do {
+        if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)) {
+            log->record(kCollapsedCoin_Glitch, id, coin, coin->fCoinPtTStart);
+        }
+        if (coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
+            log->record(kCollapsedCoin_Glitch, id, coin, coin->fOppPtTStart);
+        }
+    } while ((coin = coin->fNext));
+}
+
+void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+    const SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return;
+    }
+    do {
+        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
+        const SkOpSpanBase* oldEnd = end;
+        const SkOpSpan* start = coin->fCoinPtTStart->span()->debugStarter(&end);
+        const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
+        const SkOpSpanBase* oOldEnd = oEnd;
+        const SkOpSpanBase* oStart = coin->fOppPtTStart->span()->debugStarter(&oEnd);
+        bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
+        if (flipped) {
+            SkTSwap(oStart, oEnd);
+        }
+        const SkOpSpanBase* next = start;
+        const SkOpSpanBase* oNext = oStart;
+        do {
+            next = next->upCast()->next();
+            oNext = flipped ? oNext->prev() : oNext->upCast()->next();
+            if (next == end || oNext == oEnd) {
+                break;
+            }
+            if (!next->containsCoinEnd(oNext)) {
+                log->record(kMarkCoinEnd_Glitch, id, next, oNext);
+            }
+            const SkOpSpan* nextSpan = next->upCast();
+            const SkOpSpan* oNextSpan = oNext->upCast();
+            if (!nextSpan->containsCoincidence(oNextSpan)) {
+                log->record(kMarkCoinInsert_Glitch, id, nextSpan, oNextSpan);
+            }
+        } while (true);
+    } while ((coin = coin->fNext));
+}
+#endif
+
 void SkOpCoincidence::debugShowCoincidence() const {
     SkCoincidentSpans* span = fHead;
     while (span) {
         SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
                 span->fCoinPtTStart->segment()->debugID(),
                 span->fCoinPtTStart->fT, span->fCoinPtTEnd->fT);
         SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
                 span->fOppPtTStart->segment()->debugID(),
                 span->fOppPtTStart->fT, span->fOppPtTEnd->fT);
         span = span->fNext;
     }
 }
 
+#if DEBUG_COINCIDENCE
+void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+    const SkOpSegment* segment = &fHead;
+    do {
+        segment->debugCheckHealth(id, log);
+    } while ((segment = segment->next()));
+}
+
+void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
+        const SkOpCoincidence* coincidence) const {
+    const SkOpSegment* segment = &fHead;
+    do {
+        segment->debugMissingCoincidence(id, log, coincidence);
+    } while ((segment = segment->next()));
+}
+#endif
+
 void SkOpSegment::debugValidate() const {
 #if DEBUG_VALIDATE
     const SkOpSpanBase* span = &fHead;
     double lastT = -1;
     const SkOpSpanBase* prev = nullptr;
     int count = 0;
     int done = 0;
     do {
         if (!span->final()) {
             ++count;
             done += span->upCast()->done() ? 1 : 0;
         }
         SkASSERT(span->segment() == this);
         SkASSERT(!prev || prev->upCast()->next() == span);
         SkASSERT(!prev || prev == span->prev());
         prev = span;
         double t = span->ptT()->fT;
         SkASSERT(lastT < t);
         lastT = t;
         span->debugValidate();
     } while (!span->final() && (span = span->upCast()->next()));
     SkASSERT(count == fCount);
     SkASSERT(done == fDoneCount);
     SkASSERT(count >= fDoneCount);
     SkASSERT(span->final());
     span->debugValidate();
 #endif
 }
 
+bool SkOpSpanBase::debugAlignedEnd(double t, const SkPoint& pt) const {
+    SkASSERT(zero_or_one(t));
+    const SkOpSegment* segment = this->segment();
+    SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt);
+    if (!debugAlignedInner()) {
+          return false;
+    }
+    if ((t ? segment->lastPt() : segment->pts()[0]) != pt) {
+        return false;
+    }
+    const SkOpPtT* ptT = &this->fPtT;
+    SkASSERT(t == ptT->fT);
+    SkASSERT(pt == ptT->fPt);
+    const SkOpPtT* test = ptT, * stopPtT = ptT;
+    while ((test = test->next()) != stopPtT) {
+        const SkOpSegment* other = test->segment();
+        if (other == this->segment()) {
+            continue;
+        }
+        if (!zero_or_one(test->fT)) {
+            continue;
+        }
+        if ((test->fT ? other->lastPt() : other->pts()[0]) != pt) {
+            return false;
+        }
+    }
+    return this->fAligned;
+}
+
+bool SkOpSpanBase::debugAlignedInner() const {
+    // force the spans to share points and t values
+    const SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
+    const SkPoint& pt = ptT->fPt;
+    do {
+        if (ptT->fPt != pt) {
+            return false;
+        }
+        const SkOpSpanBase* span = ptT->span();
+        const SkOpPtT* test = ptT;
+        do {
+            if ((test = test->next()) == stopPtT) {
+                break;
+            }
+            if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) {
+                return false;
+            }
+        } while (true);
+    } while ((ptT = ptT->next()) != stopPtT);
+    return true;
+}
+
 bool SkOpSpanBase::debugCoinEndLoopCheck() const {
     int loop = 0;
     const SkOpSpanBase* next = this;
     SkOpSpanBase* nextCoin;
     do {
         nextCoin = next->fCoinEnd;
         SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
         for (int check = 1; check < loop - 1; ++check) {
             const SkOpSpanBase* checkCoin = this->fCoinEnd;
             const SkOpSpanBase* innerCoin = checkCoin;
             for (int inner = check + 1; inner < loop; ++inner) {
                 innerCoin = innerCoin->fCoinEnd;
                 if (checkCoin == innerCoin) {
                     SkDebugf("*** bad coincident end loop ***\n");
                     return false;
                 }
             }
         }
         ++loop;
     } while ((next = nextCoin) && next != this);
     return true;
 }
 
+bool SkOpSpanBase::debugContains(const SkOpSegment* segment) const {
+    const SkOpPtT* start = &fPtT;
+    const SkOpPtT* walk = start;
+    while ((walk = walk->next()) != start) {
+        if (walk->segment() == segment) {
+            return true;
+        }
+    }
+    return false;
+}
+
+const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
+    const SkOpSpanBase* end = *endPtr;
+    SkASSERT(this->segment() == end->segment());
+    const SkOpSpanBase* result;
+    if (t() < end->t()) {
+        result = this;
+    } else {
+        result = end;
+        *endPtr = this;
+    }
+    return result->upCast();
+}
+
 void SkOpSpanBase::debugValidate() const {
 #if DEBUG_VALIDATE
     const SkOpPtT* ptT = &fPtT;
     SkASSERT(ptT->span() == this);
     do {
 //        SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
         ptT->debugValidate();
         ptT = ptT->next();
     } while (ptT != &fPtT);
     SkASSERT(this->debugCoinEndLoopCheck());
@@ skipping 49 matching lines @@
             ++count2;
         }
 #endif
     }
     SkASSERT(count == count2);
     return count;
 }
 
 #include "SkOpContour.h"
 
+bool SkOpPtT::debugContains(const SkOpPtT* check) const {
+    SkASSERT(this != check);
+    const SkOpPtT* ptT = this;
+    int links = 0;
+    do {
+        ptT = ptT->next();
+        if (ptT == check) {
+            return true;
+        }
+        ++links;
+        const SkOpPtT* test = this;
+        for (int index = 0; index < links; ++index) {
+            if (ptT == test) {
+                return false;
+            }
+            test = test->next();
+        }
+    } while (true);
+}
+
+const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
+    SkASSERT(this->segment() != check);
+    const SkOpPtT* ptT = this;
+    int links = 0;
+    do {
+        ptT = ptT->next();
+        if (ptT->segment() == check) {
+            return ptT;
+        }
+        ++links;
+        const SkOpPtT* test = this;
+        for (int index = 0; index < links; ++index) {
+            if (ptT == test) {
+                return nullptr;
+            }
+            test = test->next();
+        }
+    } while (true);
+}
+
 int SkOpPtT::debugLoopLimit(bool report) const {
     int loop = 0;
     const SkOpPtT* next = this;
     do {
         for (int check = 1; check < loop - 1; ++check) {
             const SkOpPtT* checkPtT = this->fNext;
             const SkOpPtT* innerPtT = checkPtT;
             for (int inner = check + 1; inner < loop; ++inner) {
                 innerPtT = innerPtT->fNext;
                 if (checkPtT == innerPtT) {
                     if (report) {
                         SkDebugf("*** bad ptT loop ***\n");
                     }
                     return loop;
                 }
             }
         }
-        ++loop;
+        // there's nothing wrong with extremely large loop counts -- but this may appear to hang
+        // by taking a very long time to figure out that no loop entry is a duplicate
+        // -- and it's likely that a large loop count is indicative of a bug somewhere
+        if (++loop > 1000) {
+            SkDebugf("*** loop count exceeds 1000 ***\n");
+            return 1000;
+        }
     } while ((next = next->fNext) && next != this);
     return 0;
 }
 
 void SkOpPtT::debugValidate() const {
 #if DEBUG_VALIDATE
     SkOpGlobalState::Phase phase = contour()->globalState()->phase();
     if (phase == SkOpGlobalState::kIntersecting
             || phase == SkOpGlobalState::kFixWinding) {
         return;
@@ skipping 101 matching lines @@
 #endif
     SkPath::FillType fillType = path.getFillType();
     SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
     if (includeDeclaration) {
         SkDebugf("    SkPath %s;\n", name);
     }
     SkDebugf("    %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
     iter.setPath(path);
     showPathContours(iter, name);
 }