SkPathOpsDebug.cpp revision 8016b264ceec2b11d2acbeb77a9fbe66e48368b9 
1/*
2 * Copyright 2013 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkMutex.h"
9#include "SkOpCoincidence.h"
10#include "SkOpContour.h"
11#include "SkPath.h"
12#include "SkPathOpsDebug.h"
13#include "SkString.h"
14
15#undef FAIL_IF
16#define FAIL_IF(cond, coin) \
17         do { if (cond) log->record(kAddExpandedFail_Glitch, id, coin); } while (false)
18
19#undef FAIL_WITH_NULL_IF
20#define FAIL_WITH_NULL_IF(cond, span) \
21         do { if (cond) log->record(kAddExpandedFail_Glitch, id, span); } while (false)
22
23#undef RETURN_FALSE_IF
24#define RETURN_FALSE_IF(cond, span) \
25         do { if (cond) log->record(kAddExpandedFail_Glitch, id, span); } while (false)
26
27class SkCoincidentSpans;
28
29#if DEBUG_VALIDATE
30extern bool FLAGS_runFail;
31#endif
32
33#if DEBUG_SORT
34int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
35int SkPathOpsDebug::gSortCount;
36#endif
37
38#if DEBUG_ACTIVE_OP
39const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"};
40#endif
41
42#if defined SK_DEBUG || !FORCE_RELEASE
43
44const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
45
46int SkPathOpsDebug::gContourID = 0;
47int SkPathOpsDebug::gSegmentID = 0;
48
49bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray,
50        const SkOpSpanBase* span) {
51    for (int index = 0; index < chaseArray.count(); ++index) {
52        const SkOpSpanBase* entry = chaseArray[index];
53        if (entry == span) {
54            return true;
55        }
56    }
57    return false;
58}
59#endif
60
61#if DEBUG_COINCIDENCE_VERBOSE
62enum GlitchType {
63    kAddCorruptCoin_Glitch,
64    kAddExpandedCoin_Glitch,
65    kAddExpandedFail_Glitch,
66    kAddIfCollapsed_Glitch,
67    kAddIfMissingCoin_Glitch,
68    kAddMissingCoin_Glitch,
69    kAddMissingExtend_Glitch,
70    kAddOrOverlap_Glitch,
71    kCollapsedCoin_Glitch,
72    kCollapsedDone_Glitch,
73    kCollapsedOppValue_Glitch,
74    kCollapsedSpan_Glitch,
75    kCollapsedWindValue_Glitch,
76    kDeletedCoin_Glitch,
77    kExpandCoin_Glitch,
78    kMarkCoinEnd_Glitch,
79    kMarkCoinInsert_Glitch,
80    kMarkCoinMissing_Glitch,
81    kMarkCoinStart_Glitch,
82    kMergeContained_Glitch,
83    kMergeMatches_Glitch,
84    kMissingCoin_Glitch,
85    kMissingDone_Glitch,
86    kMissingIntersection_Glitch,
87    kMoveMultiple_Glitch,
88    kMoveNearbyClearAll_Glitch,
89    kMoveNearbyClearAll2_Glitch,
90    kMoveNearbyMerge_Glitch,
91    kMoveNearbyMergeFinal_Glitch,
92    kMoveNearbyRelease_Glitch,
93    kMoveNearbyReleaseFinal_Glitch,
94    kReleasedSpan_Glitch,
95    kUnaligned_Glitch,
96    kUnalignedHead_Glitch,
97    kUnalignedTail_Glitch,
98};
99
100static const int kGlitchType_Count = kUnalignedTail_Glitch + 1;
101
102struct SpanGlitch {
103    const char* fStage;
104    const SkOpSpanBase* fBase;
105    const SkOpSpanBase* fSuspect;
106    const SkOpSegment* fSegment;
107    const SkOpSegment* fOppSegment;
108    const SkOpPtT* fCoinSpan;
109    const SkOpPtT* fEndSpan;
110    const SkOpPtT* fOppSpan;
111    const SkOpPtT* fOppEndSpan;
112    double fStartT;
113    double fEndT;
114    double fOppStartT;
115    double fOppEndT;
116    SkPoint fPt;
117    GlitchType fType;
118};
119
120struct SkPathOpsDebug::GlitchLog {
121    SpanGlitch* recordCommon(GlitchType type, const char* stage) {
122        SpanGlitch* glitch = fGlitches.push();
123        glitch->fStage = stage;
124        glitch->fBase = nullptr;
125        glitch->fSuspect = nullptr;
126        glitch->fSegment = nullptr;
127        glitch->fOppSegment = nullptr;
128        glitch->fCoinSpan = nullptr;
129        glitch->fEndSpan = nullptr;
130        glitch->fOppSpan = nullptr;
131        glitch->fOppEndSpan = nullptr;
132        glitch->fStartT = SK_ScalarNaN;
133        glitch->fEndT = SK_ScalarNaN;
134        glitch->fOppStartT = SK_ScalarNaN;
135        glitch->fOppEndT = SK_ScalarNaN;
136        glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN };
137        glitch->fType = type;
138        return glitch;
139    }
140
141    void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
142            const SkOpSpanBase* suspect = NULL) {
143        SpanGlitch* glitch = recordCommon(type, stage);
144        glitch->fBase = base;
145        glitch->fSuspect = suspect;
146    }
147
148    void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
149            const SkOpPtT* ptT) {
150        SpanGlitch* glitch = recordCommon(type, stage);
151        glitch->fBase = base;
152        glitch->fCoinSpan = ptT;
153    }
154
155    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
156            const SkCoincidentSpans* opp = NULL) {
157        SpanGlitch* glitch = recordCommon(type, stage);
158        glitch->fCoinSpan = coin->coinPtTStart();
159        glitch->fEndSpan = coin->coinPtTEnd();
160        if (opp) {
161            glitch->fOppSpan = opp->coinPtTStart();
162            glitch->fOppEndSpan = opp->coinPtTEnd();
163        }
164    }
165
166    void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
167            const SkOpSegment* seg, double t, SkPoint pt) {
168        SpanGlitch* glitch = recordCommon(type, stage);
169        glitch->fBase = base;
170        glitch->fSegment = seg;
171        glitch->fStartT = t;
172        glitch->fPt = pt;
173    }
174
175    void record(GlitchType type, const char* stage, const SkOpSpanBase* base, double t,
176            SkPoint pt) {
177        SpanGlitch* glitch = recordCommon(type, stage);
178        glitch->fBase = base;
179        glitch->fStartT = t;
180        glitch->fPt = pt;
181    }
182
183    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
184            const SkOpPtT* coinSpan, const SkOpPtT* endSpan) {
185        SpanGlitch* glitch = recordCommon(type, stage);
186        glitch->fCoinSpan = coin->coinPtTStart();
187        glitch->fEndSpan = coin->coinPtTEnd();
188        glitch->fEndSpan = endSpan;
189        glitch->fOppSpan = coinSpan;
190        glitch->fOppEndSpan = endSpan;
191    }
192
193    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
194            const SkOpSpanBase* base) {
195        SpanGlitch* glitch = recordCommon(type, stage);
196        glitch->fBase = base;
197        glitch->fCoinSpan = coin->coinPtTStart();
198        glitch->fEndSpan = coin->coinPtTEnd();
199    }
200
201    void record(GlitchType type, const char* stage, const SkOpPtT* ptTS, const SkOpPtT* ptTE,
202            const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) {
203        SpanGlitch* glitch = recordCommon(type, stage);
204        glitch->fCoinSpan = ptTS;
205        glitch->fEndSpan = ptTE;
206        glitch->fOppSpan = oPtTS;
207        glitch->fOppEndSpan = oPtTE;
208    }
209
210    void record(GlitchType type, const char* stage, const SkOpSegment* seg, double startT,
211            double endT, const SkOpSegment* oppSeg, double oppStartT, double oppEndT) {
212        SpanGlitch* glitch = recordCommon(type, stage);
213        glitch->fSegment = seg;
214        glitch->fStartT = startT;
215        glitch->fEndT = endT;
216        glitch->fOppSegment = oppSeg;
217        glitch->fOppStartT = oppStartT;
218        glitch->fOppEndT = oppEndT;
219    }
220
221    void record(GlitchType type, const char* stage, const SkOpSegment* seg,
222            const SkOpSpan* span) {
223        SpanGlitch* glitch = recordCommon(type, stage);
224        glitch->fSegment = seg;
225        glitch->fBase = span;
226    }
227
228    void record(GlitchType type, const char* stage, double t, const SkOpSpanBase* span) {
229        SpanGlitch* glitch = recordCommon(type, stage);
230        glitch->fStartT = t;
231        glitch->fBase = span;
232    }
233
234    void record(GlitchType type, const char* stage, const SkOpSegment* seg) {
235        SpanGlitch* glitch = recordCommon(type, stage);
236        glitch->fSegment = seg;
237    }
238
239    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
240            const SkOpPtT* ptT) {
241        SpanGlitch* glitch = recordCommon(type, stage);
242        glitch->fCoinSpan = coin->coinPtTStart();
243        glitch->fEndSpan = ptT;
244    }
245
246    SkTDArray<SpanGlitch> fGlitches;
247};
248#endif
249
250void SkPathOpsDebug::ShowActiveSpans(SkOpContourHead* contourList) {
251#if DEBUG_ACTIVE_SPANS
252    SkOpContour* contour = contourList;
253    do {
254        contour->debugShowActiveSpans();
255    } while ((contour = contour->next()));
256#endif
257}
258
259#if DEBUG_COINCIDENCE
260void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
261    contourList->globalState()->debugSetCheckHealth(true);
262#if DEBUG_COINCIDENCE_VERBOSE
263    GlitchLog glitches;
264    const SkOpContour* contour = contourList;
265    const SkOpCoincidence* coincidence = contour->globalState()->coincidence();
266    coincidence->debugCheckValid(id, &glitches); // don't call validate; spans may be inconsistent
267    do {
268        contour->debugCheckHealth(id, &glitches);
269        contour->debugMissingCoincidence(id, &glitches);
270    } while ((contour = contour->next()));
271    coincidence->debugRemoveCollapsed(id, &glitches);
272    coincidence->debugAddMissing(id, &glitches);
273    coincidence->debugExpand(id, &glitches);
274    coincidence->debugAddExpanded(id, &glitches);
275    coincidence->debugMark(id, &glitches);
276    coincidence->debugReorder(id, &glitches);
277    unsigned mask = 0;
278    for (int index = 0; index < glitches.fGlitches.count(); ++index) {
279        const SpanGlitch& glitch = glitches.fGlitches[index];
280        mask |= 1 << glitch.fType;
281    }
282    for (int index = 0; index < kGlitchType_Count; ++index) {
283        SkDebugf(mask & (1 << index) ? "x" : "-");
284    }
285    SkDebugf("  %s\n", id);
286    for (int index = 0; index < glitches.fGlitches.count(); ++index) {
287        const SpanGlitch& glitch = glitches.fGlitches[index];
288        SkDebugf("%02d: ", index);
289        if (glitch.fBase) {
290            SkDebugf(" seg/base=%d/%d", glitch.fBase->segment()->debugID(),
291                    glitch.fBase->debugID());
292        }
293        if (glitch.fSuspect) {
294            SkDebugf(" seg/base=%d/%d", glitch.fSuspect->segment()->debugID(),
295                    glitch.fSuspect->debugID());
296        }
297        if (glitch.fSegment) {
298            SkDebugf(" segment=%d", glitch.fSegment->debugID());
299        }
300        if (glitch.fCoinSpan) {
301            SkDebugf(" coinSeg/Span/PtT=%d/%d/%d", glitch.fCoinSpan->segment()->debugID(),
302                    glitch.fCoinSpan->span()->debugID(), glitch.fCoinSpan->debugID());
303        }
304        if (glitch.fEndSpan) {
305            SkDebugf(" endSpan=%d", glitch.fEndSpan->debugID());
306        }
307        if (glitch.fOppSpan) {
308            SkDebugf(" oppSeg/Span/PtT=%d/%d/%d", glitch.fOppSpan->segment()->debugID(),
309                    glitch.fOppSpan->span()->debugID(), glitch.fOppSpan->debugID());
310        }
311        if (glitch.fOppEndSpan) {
312            SkDebugf(" oppEndSpan=%d", glitch.fOppEndSpan->debugID());
313        }
314        if (!SkScalarIsNaN(glitch.fStartT)) {
315            SkDebugf(" startT=%g", glitch.fStartT);
316        }
317        if (!SkScalarIsNaN(glitch.fEndT)) {
318            SkDebugf(" endT=%g", glitch.fEndT);
319        }
320        if (glitch.fOppSegment) {
321            SkDebugf(" segment=%d", glitch.fOppSegment->debugID());
322        }
323        if (!SkScalarIsNaN(glitch.fOppStartT)) {
324            SkDebugf(" oppStartT=%g", glitch.fOppStartT);
325        }
326        if (!SkScalarIsNaN(glitch.fOppEndT)) {
327            SkDebugf(" oppEndT=%g", glitch.fOppEndT);
328        }
329        if (!SkScalarIsNaN(glitch.fPt.fX) || !SkScalarIsNaN(glitch.fPt.fY)) {
330            SkDebugf(" pt=%g,%g", glitch.fPt.fX, glitch.fPt.fY);
331        }
332        switch (glitch.fType) {
333            case kAddCorruptCoin_Glitch: SkDebugf(" AddCorruptCoin"); break;
334            case kAddExpandedCoin_Glitch: SkDebugf(" AddExpandedCoin"); break;
335            case kAddExpandedFail_Glitch: SkDebugf(" AddExpandedFail"); break;
336            case kAddIfCollapsed_Glitch: SkDebugf(" AddIfCollapsed"); break;; break;
337            case kAddIfMissingCoin_Glitch: SkDebugf(" AddIfMissingCoin"); break;
338            case kAddMissingCoin_Glitch: SkDebugf(" AddMissingCoin"); break;
339            case kAddMissingExtend_Glitch: SkDebugf(" AddMissingExtend"); break;
340            case kAddOrOverlap_Glitch: SkDebugf(" AAddOrOverlap"); break;
341            case kCollapsedCoin_Glitch: SkDebugf(" CollapsedCoin"); break;
342            case kCollapsedDone_Glitch: SkDebugf(" CollapsedDone"); break;
343            case kCollapsedOppValue_Glitch: SkDebugf(" CollapsedOppValue"); break;
344            case kCollapsedSpan_Glitch: SkDebugf(" CollapsedSpan"); break;
345            case kCollapsedWindValue_Glitch: SkDebugf(" CollapsedWindValue"); break;
346            case kDeletedCoin_Glitch: SkDebugf(" DeletedCoin"); break;
347            case kExpandCoin_Glitch: SkDebugf(" ExpandCoin"); break;
348            case kMarkCoinEnd_Glitch: SkDebugf(" MarkCoinEnd"); break;
349            case kMarkCoinInsert_Glitch: SkDebugf(" MarkCoinInsert"); break;
350            case kMarkCoinMissing_Glitch: SkDebugf(" MarkCoinMissing"); break;
351            case kMarkCoinStart_Glitch: SkDebugf(" MarkCoinStart"); break;
352            case kMergeContained_Glitch: SkDebugf(" MergeContained"); break;
353            case kMergeMatches_Glitch: SkDebugf(" MergeMatches"); break;
354            case kMissingCoin_Glitch: SkDebugf(" MissingCoin"); break;
355            case kMissingDone_Glitch: SkDebugf(" MissingDone"); break;
356            case kMissingIntersection_Glitch: SkDebugf(" MissingIntersection"); break;
357            case kMoveMultiple_Glitch: SkDebugf(" MoveMultiple"); break;
358            case kMoveNearbyClearAll_Glitch: SkDebugf(" MoveNearbyClearAll"); break;
359            case kMoveNearbyClearAll2_Glitch: SkDebugf(" MoveNearbyClearAll2"); break;
360            case kMoveNearbyMerge_Glitch: SkDebugf(" MoveNearbyMerge"); break;
361            case kMoveNearbyMergeFinal_Glitch: SkDebugf(" MoveNearbyMergeFinal"); break;
362            case kMoveNearbyRelease_Glitch: SkDebugf(" MoveNearbyRelease"); break;
363            case kMoveNearbyReleaseFinal_Glitch: SkDebugf(" MoveNearbyReleaseFinal"); break;
364            case kReleasedSpan_Glitch: SkDebugf(" ReleasedSpan"); break;
365            case kUnaligned_Glitch: SkDebugf(" Unaligned"); break;
366            case kUnalignedHead_Glitch: SkDebugf(" UnalignedHead"); break;
367            case kUnalignedTail_Glitch: SkDebugf(" UnalignedTail"); break;
368            default: SkASSERT(0);
369        }
370        SkDebugf("\n");
371    }
372    contourList->globalState()->debugSetCheckHealth(false);
373#if 0 && DEBUG_ACTIVE_SPANS
374    SkDebugf("active after %s:\n", id);
375    ShowActiveSpans(contourList);
376#endif
377#endif
378}
379#endif
380
381#if defined SK_DEBUG || !FORCE_RELEASE
382void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
383    size_t len = strlen(str);
384    bool num = false;
385    for (size_t idx = 0; idx < len; ++idx) {
386        if (num && str[idx] == 'e') {
387            if (len + 2 >= bufferLen) {
388                return;
389            }
390            memmove(&str[idx + 2], &str[idx + 1], len - idx);
391            str[idx] = '*';
392            str[idx + 1] = '^';
393            ++len;
394        }
395        num = str[idx] >= '0' && str[idx] <= '9';
396    }
397}
398
399bool SkPathOpsDebug::ValidWind(int wind) {
400    return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
401}
402
403void SkPathOpsDebug::WindingPrintf(int wind) {
404    if (wind == SK_MinS32) {
405        SkDebugf("?");
406    } else {
407        SkDebugf("%d", wind);
408    }
409}
410#endif //  defined SK_DEBUG || !FORCE_RELEASE
411
412
413#if DEBUG_SHOW_TEST_NAME
414void* SkPathOpsDebug::CreateNameStr() { return new char[DEBUG_FILENAME_STRING_LENGTH]; }
415
416void SkPathOpsDebug::DeleteNameStr(void* v) { delete[] reinterpret_cast<char*>(v); }
417
418void SkPathOpsDebug::BumpTestName(char* test) {
419    char* num = test + strlen(test);
420    while (num[-1] >= '0' && num[-1] <= '9') {
421        --num;
422    }
423    if (num[0] == '\0') {
424        return;
425    }
426    int dec = atoi(num);
427    if (dec == 0) {
428        return;
429    }
430    ++dec;
431    SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
432}
433#endif
434
435static void show_function_header(const char* functionName) {
436    SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName);
437    if (strcmp("skphealth_com76", functionName) == 0) {
438        SkDebugf("found it\n");
439    }
440}
441
442static const char* gOpStrs[] = {
443    "kDifference_SkPathOp",
444    "kIntersect_SkPathOp",
445    "kUnion_SkPathOp",
446    "kXOR_PathOp",
447    "kReverseDifference_SkPathOp",
448};
449
450const char* SkPathOpsDebug::OpStr(SkPathOp op) {
451    return gOpStrs[op];
452}
453
454static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) {
455    SkDebugf("    testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]);
456    SkDebugf("}\n");
457}
458
459SK_DECLARE_STATIC_MUTEX(gTestMutex);
460
461void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
462        const char* testName) {
463    SkAutoMutexAcquire ac(gTestMutex);
464    show_function_header(testName);
465    ShowOnePath(a, "path", true);
466    ShowOnePath(b, "pathB", true);
467    show_op(shapeOp, "path", "pathB");
468}
469
470#include "SkPathOpsTypes.h"
471#include "SkIntersectionHelper.h"
472#include "SkIntersections.h"
473
474#if DEBUG_T_SECT_LOOP_COUNT
475void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt,
476        const SkIntersectionHelper& wn) {
477    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
478        SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index;
479        if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) {
480            continue;
481        }
482        fDebugLoopCount[index] = i->debugLoopCount(looper);
483        fDebugWorstVerb[index * 2] = wt.segment()->verb();
484        fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb();
485        sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8);
486        memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(),
487                (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint));
488        memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(),
489                (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint));
490        fDebugWorstWeight[index * 2] = wt.weight();
491        fDebugWorstWeight[index * 2 + 1] = wn.weight();
492    }
493    i->debugResetLoopCount();
494}
495
496void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) {
497    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
498        if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) {
499            continue;
500        }
501        fDebugLoopCount[index] = local->fDebugLoopCount[index];
502        fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2];
503        fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1];
504        memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4],
505                sizeof(SkPoint) * 8);
506        fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2];
507        fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1];
508    }
509    local->debugResetLoopCounts();
510}
511
512static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) {
513    if (!verb) {
514        return;
515    }
516    const char* verbs[] = { "", "line", "quad", "conic", "cubic" };
517    SkDebugf("%s: {{", verbs[verb]);
518    int ptCount = SkPathOpsVerbToPoints(verb);
519    for (int index = 0; index <= ptCount; ++index) {
520        SkDPoint::Dump((&pts)[index]);
521        if (index < ptCount - 1) {
522            SkDebugf(", ");
523        }
524    }
525    SkDebugf("}");
526    if (weight != 1) {
527        SkDebugf(", ");
528        if (weight == floorf(weight)) {
529            SkDebugf("%.0f", weight);
530        } else {
531            SkDebugf("%1.9gf", weight);
532        }
533    }
534    SkDebugf("}\n");
535}
536
537void SkOpGlobalState::debugLoopReport() {
538    const char* loops[] = { "iterations", "coinChecks", "perpCalcs" };
539    SkDebugf("\n");
540    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
541        SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]);
542        dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4],
543                fDebugWorstWeight[index * 2]);
544        dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4],
545                fDebugWorstWeight[index * 2 + 1]);
546    }
547}
548
549void SkOpGlobalState::debugResetLoopCounts() {
550    sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
551    sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb));
552    sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts));
553    sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight));
554}
555#endif
556
557#ifdef SK_DEBUG
558bool SkOpGlobalState::debugRunFail() const {
559#if DEBUG_VALIDATE
560    return FLAGS_runFail;
561#else
562    return false;
563#endif
564}
565#endif
566
567#if DEBUG_T_SECT_LOOP_COUNT
568void SkIntersections::debugBumpLoopCount(DebugLoop index) {
569    fDebugLoopCount[index]++;
570}
571
572int SkIntersections::debugLoopCount(DebugLoop index) const {
573    return fDebugLoopCount[index];
574}
575
576void SkIntersections::debugResetLoopCount() {
577    sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
578}
579#endif
580
581#include "SkPathOpsCubic.h"
582#include "SkPathOpsQuad.h"
583
584SkDCubic SkDQuad::debugToCubic() const {
585    SkDCubic cubic;
586    cubic[0] = fPts[0];
587    cubic[2] = fPts[1];
588    cubic[3] = fPts[2];
589    cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3;
590    cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3;
591    cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3;
592    cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3;
593    return cubic;
594}
595
596void SkDRect::debugInit() {
597    fLeft = fTop = fRight = fBottom = SK_ScalarNaN;
598}
599
600#include "SkOpAngle.h"
601#include "SkOpSegment.h"
602
603#if DEBUG_COINCIDENCE_VERBOSE
604// commented-out lines keep this in sync with addT()
605 const SkOpPtT* SkOpSegment::debugAddT(double t, const char* id, SkPathOpsDebug::GlitchLog* log) const {
606    debugValidate();
607    SkPoint pt = this->ptAtT(t);
608    const SkOpSpanBase* span = &fHead;
609    do {
610        const SkOpPtT* result = span->ptT();
611        if (t == result->fT || this->match(result, this, t, pt)) {
612//             span->bumpSpanAdds();
613             return result;
614        }
615        if (t < result->fT) {
616            const SkOpSpan* prev = result->span()->prev();
617            FAIL_WITH_NULL_IF(!prev, span);
618            // marks in global state that new op span has been allocated
619            this->globalState()->setAllocatedOpSpan();
620//             span->init(this, prev, t, pt);
621            this->debugValidate();
622// #if DEBUG_ADD_T
623//             SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
624//                     span->segment()->debugID(), span->debugID());
625// #endif
626//             span->bumpSpanAdds();
627            return nullptr;
628        }
629        FAIL_WITH_NULL_IF(span != &fTail, span);
630    } while ((span = span->upCast()->next()));
631    SkASSERT(0);
632    return nullptr;  // we never get here, but need this to satisfy compiler
633}
634#endif
635
636#if DEBUG_ANGLE
637void SkOpSegment::debugCheckAngleCoin() const {
638    const SkOpSpanBase* base = &fHead;
639    const SkOpSpan* span;
640    do {
641        const SkOpAngle* angle = base->fromAngle();
642        if (angle && angle->debugCheckCoincidence()) {
643            angle->debugCheckNearCoincidence();
644        }
645        if (base->final()) {
646             break;
647        }
648        span = base->upCast();
649        angle = span->toAngle();
650        if (angle && angle->debugCheckCoincidence()) {
651            angle->debugCheckNearCoincidence();
652        }
653    } while ((base = span->next()));
654}
655#endif
656
657#if DEBUG_COINCIDENCE_VERBOSE
658// this mimics the order of the checks in handle coincidence
659void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
660    debugMoveMultiples(id, glitches);
661    debugMoveNearby(id, glitches);
662    debugMissingCoincidence(id, glitches);
663}
664
665// commented-out lines keep this in sync with clearAll()
666void SkOpSegment::debugClearAll(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
667    const SkOpSpan* span = &fHead;
668    do {
669        this->debugClearOne(span, id, glitches);
670    } while ((span = span->next()->upCastable()));
671    this->globalState()->coincidence()->debugRelease(id, glitches, this);
672}
673
674// commented-out lines keep this in sync with clearOne()
675void SkOpSegment::debugClearOne(const SkOpSpan* span, const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
676    if (span->windValue()) glitches->record(kCollapsedWindValue_Glitch, id, span);
677    if (span->oppValue()) glitches->record(kCollapsedOppValue_Glitch, id, span);
678    if (!span->done()) glitches->record(kCollapsedDone_Glitch, id, span);
679}
680#endif
681
682SkOpAngle* SkOpSegment::debugLastAngle() {
683    SkOpAngle* result = nullptr;
684    SkOpSpan* span = this->head();
685    do {
686        if (span->toAngle()) {
687            SkASSERT(!result);
688            result = span->toAngle();
689        }
690    } while ((span = span->next()->upCastable()));
691    SkASSERT(result);
692    return result;
693}
694
695#if DEBUG_COINCIDENCE
696// commented-out lines keep this in sync with ClearVisited
697void SkOpSegment::DebugClearVisited(const SkOpSpanBase* span) {
698    // reset visited flag back to false
699    do {
700        const SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
701        while ((ptT = ptT->next()) != stopPtT) {
702            const SkOpSegment* opp = ptT->segment();
703            opp->resetDebugVisited();
704        }
705    } while (!span->final() && (span = span->upCast()->next()));
706}
707#endif
708
709#if DEBUG_COINCIDENCE_VERBOSE
710// commented-out lines keep this in sync with missingCoincidence()
711// look for pairs of undetected coincident curves
712// assumes that segments going in have visited flag clear
713// Even though pairs of curves correct detect coincident runs, a run may be missed
714// if the coincidence is a product of multiple intersections. For instance, given
715// curves A, B, and C:
716// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
717// the end of C that the intersection is replaced with the end of C.
718// Even though A-B correctly do not detect an intersection at point 2,
719// the resulting run from point 1 to point 2 is coincident on A and B.
720void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
721    if (this->done()) {
722        return;
723    }
724    const SkOpSpan* prior = nullptr;
725    const SkOpSpanBase* spanBase = &fHead;
726//    bool result = false;
727    do {
728        const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
729        SkASSERT(ptT->span() == spanBase);
730        while ((ptT = ptT->next()) != spanStopPtT) {
731            if (ptT->deleted()) {
732                continue;
733            }
734            const SkOpSegment* opp = ptT->span()->segment();
735            if (opp->done()) {
736                continue;
737            }
738            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
739            if (!opp->debugVisited()) {
740                continue;
741            }
742            if (spanBase == &fHead) {
743                continue;
744            }
745            if (ptT->segment() == this) {
746                continue;
747            }
748            const SkOpSpan* span = spanBase->upCastable();
749            // FIXME?: this assumes that if the opposite segment is coincident then no more
750            // coincidence needs to be detected. This may not be true.
751            if (span && span->segment() != opp && span->containsCoincidence(opp)) {  // debug has additional condition since it may be called before inner duplicate points have been deleted
752                continue;
753            }
754            if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) {  // debug has additional condition since it may be called before inner duplicate points have been deleted
755                continue;
756            }
757            const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
758            // find prior span containing opp segment
759            const SkOpSegment* priorOpp = nullptr;
760            const SkOpSpan* priorTest = spanBase->prev();
761            while (!priorOpp && priorTest) {
762                priorStopPtT = priorPtT = priorTest->ptT();
763                while ((priorPtT = priorPtT->next()) != priorStopPtT) {
764                    if (priorPtT->deleted()) {
765                        continue;
766                    }
767                    SkOpSegment* segment = priorPtT->span()->segment();
768                    if (segment == opp) {
769                        prior = priorTest;
770                        priorOpp = opp;
771                        break;
772                    }
773                }
774                priorTest = priorTest->prev();
775            }
776            if (!priorOpp) {
777                continue;
778            }
779            if (priorPtT == ptT) {
780                continue;
781            }
782            const SkOpPtT* oppStart = prior->ptT();
783            const SkOpPtT* oppEnd = spanBase->ptT();
784            bool swapped = priorPtT->fT > ptT->fT;
785            if (swapped) {
786                SkTSwap(priorPtT, ptT);
787                SkTSwap(oppStart, oppEnd);
788            }
789            const SkOpCoincidence* coincidence = this->globalState()->coincidence();
790            const SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
791            const SkOpPtT* rootPtT = ptT->span()->ptT();
792            const SkOpPtT* rootOppStart = oppStart->span()->ptT();
793            const SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
794            if (coincidence->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
795                goto swapBack;
796            }
797            if (testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
798            // mark coincidence
799#if DEBUG_COINCIDENCE_VERBOSE
800//                 SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
801//                         rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
802//                         rootOppEnd->debugID());
803#endif
804                log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd);
805                //   coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
806                // }
807#if DEBUG_COINCIDENCE
808//                SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
809#endif
810                // result = true;
811            }
812    swapBack:
813            if (swapped) {
814                SkTSwap(priorPtT, ptT);
815            }
816        }
817    } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
818    DebugClearVisited(&fHead);
819    return;
820}
821
822// commented-out lines keep this in sync with moveMultiples()
823// if a span has more than one intersection, merge the other segments' span as needed
824void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
825    debugValidate();
826    const SkOpSpanBase* test = &fHead;
827    do {
828        int addCount = test->spanAddsCount();
829        SkASSERT(addCount >= 1);
830        if (addCount == 1) {
831            continue;
832        }
833        const SkOpPtT* startPtT = test->ptT();
834        const SkOpPtT* testPtT = startPtT;
835        do {  // iterate through all spans associated with start
836            const SkOpSpanBase* oppSpan = testPtT->span();
837            if (oppSpan->spanAddsCount() == addCount) {
838                continue;
839            }
840            if (oppSpan->deleted()) {
841                continue;
842            }
843            const SkOpSegment* oppSegment = oppSpan->segment();
844            if (oppSegment == this) {
845                continue;
846            }
847            // find range of spans to consider merging
848            const SkOpSpanBase* oppPrev = oppSpan;
849            const SkOpSpanBase* oppFirst = oppSpan;
850            while ((oppPrev = oppPrev->prev())) {
851                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
852                    break;
853                }
854                if (oppPrev->spanAddsCount() == addCount) {
855                    continue;
856                }
857                if (oppPrev->deleted()) {
858                    continue;
859                }
860                oppFirst = oppPrev;
861            }
862            const SkOpSpanBase* oppNext = oppSpan;
863            const SkOpSpanBase* oppLast = oppSpan;
864            while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
865                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
866                    break;
867                }
868                if (oppNext->spanAddsCount() == addCount) {
869                    continue;
870                }
871                if (oppNext->deleted()) {
872                    continue;
873                }
874                oppLast = oppNext;
875            }
876            if (oppFirst == oppLast) {
877                continue;
878            }
879            const SkOpSpanBase* oppTest = oppFirst;
880            do {
881                if (oppTest == oppSpan) {
882                    continue;
883                }
884                // check to see if the candidate meets specific criteria:
885                // it contains spans of segments in test's loop but not including 'this'
886                const SkOpPtT* oppStartPtT = oppTest->ptT();
887                const SkOpPtT* oppPtT = oppStartPtT;
888                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
889                    const SkOpSegment* oppPtTSegment = oppPtT->segment();
890                    if (oppPtTSegment == this) {
891                        goto tryNextSpan;
892                    }
893                    const SkOpPtT* matchPtT = startPtT;
894                    do {
895                        if (matchPtT->segment() == oppPtTSegment) {
896                            goto foundMatch;
897                        }
898                    } while ((matchPtT = matchPtT->next()) != startPtT);
899                    goto tryNextSpan;
900            foundMatch:  // merge oppTest and oppSpan
901                    oppSegment->debugValidate();
902                    oppTest->debugMergeMatches(id, glitches, oppSpan);
903                    oppTest->debugAddOpp(id, glitches, oppSpan);
904                    oppSegment->debugValidate();
905                    goto checkNextSpan;
906                }
907        tryNextSpan:
908                ;
909            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
910        } while ((testPtT = testPtT->next()) != startPtT);
911checkNextSpan:
912        ;
913    } while ((test = test->final() ? nullptr : test->upCast()->next()));
914   debugValidate();
915   return;
916}
917
918// commented-out lines keep this in sync with moveNearby()
919// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
920void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
921    debugValidate();
922    // release undeleted spans pointing to this seg that are linked to the primary span
923    const SkOpSpanBase* spanBase = &fHead;
924    do {
925        const SkOpPtT* ptT = spanBase->ptT();
926        const SkOpPtT* headPtT = ptT;
927        while ((ptT = ptT->next()) != headPtT) {
928              const SkOpSpanBase* test = ptT->span();
929            if (ptT->segment() == this && !ptT->deleted() && test != spanBase
930                    && test->ptT() == ptT) {
931                if (test->final()) {
932                    if (spanBase == &fHead) {
933                        glitches->record(kMoveNearbyClearAll_Glitch, id, this);
934//                        return;
935                    }
936                    glitches->record(kMoveNearbyReleaseFinal_Glitch, id, spanBase, ptT);
937                } else if (test->prev()) {
938                    glitches->record(kMoveNearbyRelease_Glitch, id, test, headPtT);
939                }
940//                break;
941            }
942        }
943        spanBase = spanBase->upCast()->next();
944    } while (!spanBase->final());
945
946    // This loop looks for adjacent spans which are near by
947    spanBase = &fHead;
948    do {  // iterate through all spans associated with start
949        const SkOpSpanBase* test = spanBase->upCast()->next();
950        if (this->spansNearby(spanBase, test)) {
951            if (test->final()) {
952                if (spanBase->prev()) {
953                    glitches->record(kMoveNearbyMergeFinal_Glitch, id, test);
954                } else {
955                    glitches->record(kMoveNearbyClearAll2_Glitch, id, this);
956                    // return
957                }
958            } else {
959                glitches->record(kMoveNearbyMerge_Glitch, id, spanBase);
960            }
961        }
962        spanBase = test;
963    } while (!spanBase->final());
964    debugValidate();
965}
966#endif
967
968void SkOpSegment::debugReset() {
969    this->init(this->fPts, this->fWeight, this->contour(), this->verb());
970}
971
972#if DEBUG_COINCIDENCE_ORDER
973void SkOpSegment::debugSetCoinT(int index, SkScalar t) const {
974    if (fDebugBaseMax < 0 || fDebugBaseIndex == index) {
975        fDebugBaseIndex = index;
976        fDebugBaseMin = SkTMin(t, fDebugBaseMin);
977        fDebugBaseMax = SkTMax(t, fDebugBaseMax);
978        return;
979    }
980    SkASSERT(fDebugBaseMin >= t || t >= fDebugBaseMax);
981    if (fDebugLastMax < 0 || fDebugLastIndex == index) {
982        fDebugLastIndex = index;
983        fDebugLastMin = SkTMin(t, fDebugLastMin);
984        fDebugLastMax = SkTMax(t, fDebugLastMax);
985        return;
986    }
987    SkASSERT(fDebugLastMin >= t || t >= fDebugLastMax);
988    SkASSERT((t - fDebugBaseMin > 0) == (fDebugLastMin - fDebugBaseMin > 0));
989}
990#endif
991
992#if DEBUG_ACTIVE_SPANS
993void SkOpSegment::debugShowActiveSpans() const {
994    debugValidate();
995    if (done()) {
996        return;
997    }
998    int lastId = -1;
999    double lastT = -1;
1000    const SkOpSpan* span = &fHead;
1001    do {
1002        if (span->done()) {
1003            continue;
1004        }
1005        if (lastId == this->debugID() && lastT == span->t()) {
1006            continue;
1007        }
1008        lastId = this->debugID();
1009        lastT = span->t();
1010        SkDebugf("%s id=%d", __FUNCTION__, this->debugID());
1011        // since endpoints may have be adjusted, show actual computed curves
1012        SkDCurve curvePart;
1013        this->subDivide(span, span->next(), &curvePart);
1014        const SkDPoint* pts = curvePart.fCubic.fPts;
1015        SkDebugf(" (%1.9g,%1.9g", pts[0].fX, pts[0].fY);
1016        for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1017            SkDebugf(" %1.9g,%1.9g", pts[vIndex].fX, pts[vIndex].fY);
1018        }
1019        if (SkPath::kConic_Verb == fVerb) {
1020            SkDebugf(" %1.9gf", curvePart.fConic.fWeight);
1021        }
1022        SkDebugf(") t=%1.9g tEnd=%1.9g", span->t(), span->next()->t());
1023        if (span->windSum() == SK_MinS32) {
1024            SkDebugf(" windSum=?");
1025        } else {
1026            SkDebugf(" windSum=%d", span->windSum());
1027        }
1028        if (span->oppValue() && span->oppSum() == SK_MinS32) {
1029            SkDebugf(" oppSum=?");
1030        } else if (span->oppValue() || span->oppSum() != SK_MinS32) {
1031            SkDebugf(" oppSum=%d", span->oppSum());
1032        }
1033        SkDebugf(" windValue=%d", span->windValue());
1034        if (span->oppValue() || span->oppSum() != SK_MinS32) {
1035            SkDebugf(" oppValue=%d", span->oppValue());
1036        }
1037        SkDebugf("\n");
1038   } while ((span = span->next()->upCastable()));
1039}
1040#endif
1041
1042#if DEBUG_MARK_DONE
1043void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
1044    const SkPoint& pt = span->ptT()->fPt;
1045    SkDebugf("%s id=%d", fun, this->debugID());
1046    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1047    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1048        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1049    }
1050    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
1051            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
1052    if (winding == SK_MinS32) {
1053        SkDebugf("?");
1054    } else {
1055        SkDebugf("%d", winding);
1056    }
1057    SkDebugf(" windSum=");
1058    if (span->windSum() == SK_MinS32) {
1059        SkDebugf("?");
1060    } else {
1061        SkDebugf("%d", span->windSum());
1062    }
1063    SkDebugf(" windValue=%d\n", span->windValue());
1064}
1065
1066void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
1067                                      int oppWinding) {
1068    const SkPoint& pt = span->ptT()->fPt;
1069    SkDebugf("%s id=%d", fun, this->debugID());
1070    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1071    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1072        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1073    }
1074    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
1075            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding);
1076    if (winding == SK_MinS32) {
1077        SkDebugf("?");
1078    } else {
1079        SkDebugf("%d", winding);
1080    }
1081    SkDebugf(" newOppSum=");
1082    if (oppWinding == SK_MinS32) {
1083        SkDebugf("?");
1084    } else {
1085        SkDebugf("%d", oppWinding);
1086    }
1087    SkDebugf(" oppSum=");
1088    if (span->oppSum() == SK_MinS32) {
1089        SkDebugf("?");
1090    } else {
1091        SkDebugf("%d", span->oppSum());
1092    }
1093    SkDebugf(" windSum=");
1094    if (span->windSum() == SK_MinS32) {
1095        SkDebugf("?");
1096    } else {
1097        SkDebugf("%d", span->windSum());
1098    }
1099    SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
1100}
1101
1102#endif
1103
1104// loop looking for a pair of angle parts that are too close to be sorted
1105/* This is called after other more simple intersection and angle sorting tests have been exhausted.
1106   This should be rarely called -- the test below is thorough and time consuming.
1107   This checks the distance between start points; the distance between
1108*/
1109#if DEBUG_ANGLE
1110void SkOpAngle::debugCheckNearCoincidence() const {
1111    const SkOpAngle* test = this;
1112    do {
1113        const SkOpSegment* testSegment = test->segment();
1114        double testStartT = test->start()->t();
1115        SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
1116        double testEndT = test->end()->t();
1117        SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
1118        double testLenSq = testStartPt.distanceSquared(testEndPt);
1119        SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
1120        double testMidT = (testStartT + testEndT) / 2;
1121        const SkOpAngle* next = test;
1122        while ((next = next->fNext) != this) {
1123            SkOpSegment* nextSegment = next->segment();
1124            double testMidDistSq = testSegment->distSq(testMidT, next);
1125            double testEndDistSq = testSegment->distSq(testEndT, next);
1126            double nextStartT = next->start()->t();
1127            SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
1128            double distSq = testStartPt.distanceSquared(nextStartPt);
1129            double nextEndT = next->end()->t();
1130            double nextMidT = (nextStartT + nextEndT) / 2;
1131            double nextMidDistSq = nextSegment->distSq(nextMidT, test);
1132            double nextEndDistSq = nextSegment->distSq(nextEndT, test);
1133            SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
1134                    testSegment->debugID(), nextSegment->debugID());
1135            SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
1136            SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
1137            SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
1138            SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
1139            SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
1140            double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
1141            SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
1142            SkDebugf("\n");
1143        }
1144        test = test->fNext;
1145    } while (test->fNext != this);
1146}
1147#endif
1148
1149#if DEBUG_ANGLE
1150SkString SkOpAngle::debugPart() const {
1151    SkString result;
1152    switch (this->segment()->verb()) {
1153        case SkPath::kLine_Verb:
1154            result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart),
1155                    this->segment()->debugID());
1156            break;
1157        case SkPath::kQuad_Verb:
1158            result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
1159                    this->segment()->debugID());
1160            break;
1161        case SkPath::kConic_Verb:
1162            result.printf(CONIC_DEBUG_STR " id=%d",
1163                    CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight),
1164                    this->segment()->debugID());
1165            break;
1166        case SkPath::kCubic_Verb:
1167            result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart),
1168                    this->segment()->debugID());
1169            break;
1170        default:
1171            SkASSERT(0);
1172    }
1173    return result;
1174}
1175#endif
1176
1177#if DEBUG_SORT
1178void SkOpAngle::debugLoop() const {
1179    const SkOpAngle* first = this;
1180    const SkOpAngle* next = this;
1181    do {
1182        next->dumpOne(true);
1183        SkDebugf("\n");
1184        next = next->fNext;
1185    } while (next && next != first);
1186    next = first;
1187    do {
1188        next->debugValidate();
1189        next = next->fNext;
1190    } while (next && next != first);
1191}
1192#endif
1193
1194void SkOpAngle::debugValidate() const {
1195#if DEBUG_COINCIDENCE
1196    if (this->globalState()->debugCheckHealth()) {
1197        return;
1198    }
1199#endif
1200#if DEBUG_VALIDATE
1201    const SkOpAngle* first = this;
1202    const SkOpAngle* next = this;
1203    int wind = 0;
1204    int opp = 0;
1205    int lastXor = -1;
1206    int lastOppXor = -1;
1207    do {
1208        if (next->unorderable()) {
1209            return;
1210        }
1211        const SkOpSpan* minSpan = next->start()->starter(next->end());
1212        if (minSpan->windValue() == SK_MinS32) {
1213            return;
1214        }
1215        bool op = next->segment()->operand();
1216        bool isXor = next->segment()->isXor();
1217        bool oppXor = next->segment()->oppXor();
1218        SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
1219        SkASSERT(!DEBUG_LIMIT_WIND_SUM
1220                || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
1221        bool useXor = op ? oppXor : isXor;
1222        SkASSERT(lastXor == -1 || lastXor == (int) useXor);
1223        lastXor = (int) useXor;
1224        wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue());
1225        if (useXor) {
1226            wind &= 1;
1227        }
1228        useXor = op ? isXor : oppXor;
1229        SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
1230        lastOppXor = (int) useXor;
1231        opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue());
1232        if (useXor) {
1233            opp &= 1;
1234        }
1235        next = next->fNext;
1236    } while (next && next != first);
1237    SkASSERT(wind == 0 || !FLAGS_runFail);
1238    SkASSERT(opp == 0 || !FLAGS_runFail);
1239#endif
1240}
1241
1242void SkOpAngle::debugValidateNext() const {
1243#if !FORCE_RELEASE
1244    const SkOpAngle* first = this;
1245    const SkOpAngle* next = first;
1246    SkTDArray<const SkOpAngle*>(angles);
1247    do {
1248//        SkASSERT_RELEASE(next->fSegment->debugContains(next));
1249        angles.push(next);
1250        next = next->next();
1251        if (next == first) {
1252            break;
1253        }
1254        SkASSERT_RELEASE(!angles.contains(next));
1255        if (!next) {
1256            return;
1257        }
1258    } while (true);
1259#endif
1260}
1261
1262#ifdef SK_DEBUG
1263void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
1264        const SkOpGlobalState* debugState) const {
1265    SkASSERT(coinPtTEnd()->span() == over || !debugState->debugRunFail());
1266    SkASSERT(oppPtTEnd()->span() == outer || !debugState->debugRunFail());
1267}
1268#endif
1269
1270#if DEBUG_COINCIDENCE_VERBOSE
1271/* Commented-out lines keep this in sync with expand */
1272// expand the range by checking adjacent spans for coincidence
1273bool SkCoincidentSpans::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1274    bool expanded = false;
1275    const SkOpSegment* segment = coinPtTStart()->segment();
1276    const SkOpSegment* oppSegment = oppPtTStart()->segment();
1277    do {
1278        const SkOpSpan* start = coinPtTStart()->span()->upCast();
1279        const SkOpSpan* prev = start->prev();
1280        const SkOpPtT* oppPtT;
1281        if (!prev || !(oppPtT = prev->contains(oppSegment))) {
1282            break;
1283        }
1284        double midT = (prev->t() + start->t()) / 2;
1285        if (!segment->isClose(midT, oppSegment)) {
1286            break;
1287        }
1288        if (log) log->record(kExpandCoin_Glitch, id, this, prev->ptT(), oppPtT);
1289        expanded = true;
1290    } while (false);  // actual continues while expansion is possible
1291    do {
1292        const SkOpSpanBase* end = coinPtTEnd()->span();
1293        SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
1294        if (next && next->deleted()) {
1295            break;
1296        }
1297        const SkOpPtT* oppPtT;
1298        if (!next || !(oppPtT = next->contains(oppSegment))) {
1299            break;
1300        }
1301        double midT = (end->t() + next->t()) / 2;
1302        if (!segment->isClose(midT, oppSegment)) {
1303            break;
1304        }
1305        if (log) log->record(kExpandCoin_Glitch, id, this, next->ptT(), oppPtT);
1306        expanded = true;
1307    } while (false);  // actual continues while expansion is possible
1308    return expanded;
1309}
1310
1311/* Commented-out lines keep this in sync with addExpanded */
1312// for each coincident pair, match the spans
1313// if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
1314void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1315    const SkCoincidentSpans* coin = this->fHead;
1316    if (!coin) {
1317        return;
1318    }
1319    do {
1320        const SkOpPtT* startPtT = coin->coinPtTStart();
1321        const SkOpPtT* oStartPtT = coin->oppPtTStart();
1322        SkASSERT(startPtT->contains(oStartPtT));
1323        SkASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
1324        const SkOpSpanBase* start = startPtT->span();
1325        const SkOpSpanBase* oStart = oStartPtT->span();
1326        const SkOpSpanBase* end = coin->coinPtTEnd()->span();
1327        const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
1328        FAIL_IF(oEnd->deleted(), coin);
1329        FAIL_IF(!start->upCastable(), coin);
1330        const SkOpSpanBase* test = start->upCast()->next();
1331        const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
1332        if (!oTest) {
1333            return;
1334        }
1335        while (test != end || oTest != oEnd) {
1336            if (!test->ptT()->contains(oTest->segment())
1337                    || !oTest->ptT()->contains(start->segment())) {
1338                // use t ranges to guess which one is missing
1339                double startRange = coin->coinPtTEnd()->fT - startPtT->fT;
1340                FAIL_IF(!startRange, coin);
1341                double startPart = (test->t() - startPtT->fT) / startRange;
1342                double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT;
1343                FAIL_IF(!oStartRange, coin);
1344                double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
1345                FAIL_IF(startPart == oStartPart, coin);
1346                bool startOver = false;
1347                if (startPart < oStartPart)
1348                        log->record(kAddExpandedCoin_Glitch, id,  // strange debug formatting lines up with original
1349                                oStartPtT->fT + oStartRange * startPart, test);
1350                        else log->record(kAddExpandedCoin_Glitch, id,
1351                                startPtT->fT + startRange * oStartPart, oTest);
1352                if (false) {
1353                    SkASSERT(0);
1354                    return;
1355                }
1356                if (startOver) {
1357                    test = start;
1358                    oTest = oStart;
1359                }
1360            }
1361            if (test != end) {
1362                if (!test->upCastable()) {
1363                    return;
1364                }
1365                test = test->upCast()->next();
1366            }
1367            if (oTest != oEnd) {
1368                oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
1369                if (!oTest) {
1370                    return;
1371                }
1372            }
1373        }
1374    } while ((coin = coin->next()));
1375    return;
1376}
1377
1378/* Commented-out lines keep this in sync with addIfMissing() */
1379void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* outer, const SkOpPtT* over1s,
1380            const SkOpPtT* over1e) const {
1381//     SkASSERT(fTop);
1382    if (fTop && alreadyAdded(fTop, outer, over1s, over1e)) {  // in debug, fTop may be null
1383        return;
1384    }
1385    if (fHead && alreadyAdded(fHead, outer, over1s, over1e)) {
1386        return;
1387    }
1388    log->record(kAddIfMissingCoin_Glitch, id, outer->coinPtTStart(), outer->coinPtTEnd(), over1s, over1e);
1389    this->debugValidate();
1390    return;
1391}
1392
1393/* Commented-out lines keep this in sync addIfMissing() */
1394// note that over1s, over1e, over2s, over2e are ordered
1395void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* over1s, const SkOpPtT* over2s,
1396        double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
1397        const SkOpPtT* over1e, const SkOpPtT* over2e) const {
1398    SkASSERT(tStart < tEnd);
1399    SkASSERT(over1s->fT < over1e->fT);
1400    SkASSERT(between(over1s->fT, tStart, over1e->fT));
1401    SkASSERT(between(over1s->fT, tEnd, over1e->fT));
1402    SkASSERT(over2s->fT < over2e->fT);
1403    SkASSERT(between(over2s->fT, tStart, over2e->fT));
1404    SkASSERT(between(over2s->fT, tEnd, over2e->fT));
1405    SkASSERT(over1s->segment() == over1e->segment());
1406    SkASSERT(over2s->segment() == over2e->segment());
1407    SkASSERT(over1s->segment() == over2s->segment());
1408    SkASSERT(over1s->segment() != coinSeg);
1409    SkASSERT(over1s->segment() != oppSeg);
1410    SkASSERT(coinSeg != oppSeg);
1411    double coinTs, coinTe, oppTs, oppTe;
1412    coinTs = TRange(over1s, tStart, coinSeg  SkDEBUGPARAMS(over1e));
1413    coinTe = TRange(over1s, tEnd, coinSeg  SkDEBUGPARAMS(over1e));
1414    if (coinSeg->collapsed(coinTs, coinTe)) {
1415        return log->record(kAddIfCollapsed_Glitch, id, coinSeg);
1416    }
1417    oppTs = TRange(over2s, tStart, oppSeg  SkDEBUGPARAMS(over2e));
1418    oppTe = TRange(over2s, tEnd, oppSeg  SkDEBUGPARAMS(over2e));
1419    if (oppSeg->collapsed(oppTs, oppTe)) {
1420        return log->record(kAddIfCollapsed_Glitch, id, oppSeg);
1421    }
1422    if (coinTs > coinTe) {
1423        SkTSwap(coinTs, coinTe);
1424        SkTSwap(oppTs, oppTe);
1425    }
1426    return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
1427            );
1428}
1429
1430/* Commented-out lines keep this in sync addOrOverlap() */
1431// If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
1432// If this is called by AddIfMissing(), a returned false indicates there was nothing to add
1433void SkOpCoincidence::debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLog* log,
1434        const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
1435        double coinTs, double coinTe, double oppTs, double oppTe) const {
1436    SkTDArray<SkCoincidentSpans*> overlaps;
1437    SkASSERT(!fTop);   // this is (correctly) reversed in addifMissing()
1438    if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
1439        return;
1440    }
1441    if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
1442            coinTe, oppTs, oppTe, &overlaps)) {
1443        return;
1444    }
1445    const SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
1446    for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
1447        const SkCoincidentSpans* test = overlaps[index];
1448        if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
1449            log->record(kAddOrOverlap_Glitch, id, overlap, test->coinPtTStart());
1450        }
1451        if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
1452            log->record(kAddOrOverlap_Glitch, id, overlap, test->coinPtTEnd());
1453        }
1454        if (overlap->flipped()
1455                ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
1456                : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
1457            log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTStart());
1458        }
1459        if (overlap->flipped()
1460                ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
1461                : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
1462            log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTEnd());
1463        }
1464        if (!fHead) { this->debugRelease(id, log, fHead, test);
1465            this->debugRelease(id, log, fTop, test);
1466        }
1467    }
1468    const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
1469    const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
1470    RETURN_FALSE_IF(overlap && cs && ce && overlap->contains(cs, ce), coinSeg);
1471    RETURN_FALSE_IF(cs != ce || !cs, coinSeg);
1472    const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
1473    const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
1474    RETURN_FALSE_IF(overlap && os && oe && overlap->contains(os, oe), oppSeg);
1475    SkASSERT(true || !cs || !cs->deleted());
1476    SkASSERT(true || !os || !os->deleted());
1477    SkASSERT(true || !ce || !ce->deleted());
1478    SkASSERT(true || !oe || !oe->deleted());
1479    const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
1480    const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
1481    RETURN_FALSE_IF(csExisting && csExisting == ceExisting, coinSeg);
1482    RETURN_FALSE_IF(csExisting && (csExisting == ce ||
1483            csExisting->contains(ceExisting ? ceExisting : ce)), coinSeg);
1484    RETURN_FALSE_IF(ceExisting && (ceExisting == cs ||
1485            ceExisting->contains(csExisting ? csExisting : cs)), coinSeg);
1486    const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
1487    const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
1488    RETURN_FALSE_IF(osExisting && osExisting == oeExisting, oppSeg);
1489    RETURN_FALSE_IF(osExisting && (osExisting == oe ||
1490            osExisting->contains(oeExisting ? oeExisting : oe)), oppSeg);
1491    RETURN_FALSE_IF(oeExisting && (oeExisting == os ||
1492            oeExisting->contains(osExisting ? osExisting : os)), oppSeg);
1493    bool csDeleted = false, osDeleted = false, ceDeleted = false,  oeDeleted = false;
1494    this->debugValidate();
1495    if (!cs || !os) {
1496        if (!cs)
1497            cs = coinSeg->debugAddT(coinTs, id, log);
1498        if (!os)
1499            os = oppSeg->debugAddT(oppTs, id, log);
1500//      RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable);
1501        if (cs && os) cs->span()->debugAddOpp(id, log, os->span());
1502//         cs = csWritable;
1503//         os = osWritable->active();
1504        RETURN_FALSE_IF((ce && ce->deleted()) || (oe && oe->deleted()), coinSeg);
1505    }
1506    if (!ce || !oe) {
1507        if (!ce)
1508            ce = coinSeg->debugAddT(coinTe, id, log);
1509        if (!oe)
1510            oe = oppSeg->debugAddT(oppTe, id, log);
1511        if (ce && oe) ce->span()->debugAddOpp(id, log, oe->span());
1512//         ce = ceWritable;
1513//         oe = oeWritable;
1514    }
1515    this->debugValidate();
1516    RETURN_FALSE_IF(csDeleted, coinSeg);
1517    RETURN_FALSE_IF(osDeleted, oppSeg);
1518    RETURN_FALSE_IF(ceDeleted, coinSeg);
1519    RETURN_FALSE_IF(oeDeleted, oppSeg);
1520    RETURN_FALSE_IF(!cs || !ce || cs == ce || cs->contains(ce) || !os || !oe || os == oe || os->contains(oe), coinSeg);
1521    bool result = true;
1522    if (overlap) {
1523        if (overlap->coinPtTStart()->segment() == coinSeg) {
1524                log->record(kAddMissingExtend_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
1525        } else {
1526            if (oppTs > oppTe) {
1527                SkTSwap(coinTs, coinTe);
1528                SkTSwap(oppTs, oppTe);
1529            }
1530            log->record(kAddMissingExtend_Glitch, id, oppSeg, oppTs, oppTe, coinSeg, coinTs, coinTe);
1531        }
1532#if 0 && DEBUG_COINCIDENCE_VERBOSE
1533        if (result) {
1534             overlap->debugShow();
1535        }
1536#endif
1537    } else {
1538        log->record(kAddMissingCoin_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
1539#if 0 && DEBUG_COINCIDENCE_VERBOSE
1540        fHead->debugShow();
1541#endif
1542    }
1543    this->debugValidate();
1544    return (void) result;
1545}
1546
1547// Extra commented-out lines keep this in sync with addMissing()
1548/* detects overlaps of different coincident runs on same segment */
1549/* does not detect overlaps for pairs without any segments in common */
1550// returns true if caller should loop again
1551void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1552    const SkCoincidentSpans* outer = fHead;
1553    if (!outer) {
1554        return;
1555    }
1556    // bool added = false;
1557    // fTop = outer;
1558    // fHead = nullptr;
1559    do {
1560    // addifmissing can modify the list that this is walking
1561    // save head so that walker can iterate over old data unperturbed
1562    // addifmissing adds to head freely then add saved head in the end
1563        const SkOpPtT* ocs = outer->coinPtTStart();
1564        SkASSERT(!ocs->deleted());
1565        const SkOpSegment* outerCoin = ocs->segment();
1566        SkASSERT(!outerCoin->done());  // if it's done, should have already been removed from list
1567        const SkOpPtT* oos = outer->oppPtTStart();
1568        SkASSERT(!oos->deleted());
1569        const SkOpSegment* outerOpp = oos->segment();
1570        SkASSERT(!outerOpp->done());
1571//        SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
1572//        SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
1573        const SkCoincidentSpans* inner = outer;
1574        while ((inner = inner->next())) {
1575            this->debugValidate();
1576            double overS, overE;
1577            const SkOpPtT* ics = inner->coinPtTStart();
1578            SkASSERT(!ics->deleted());
1579            const SkOpSegment* innerCoin = ics->segment();
1580            SkASSERT(!innerCoin->done());
1581            const SkOpPtT* ios = inner->oppPtTStart();
1582            SkASSERT(!ios->deleted());
1583            const SkOpSegment* innerOpp = ios->segment();
1584            SkASSERT(!innerOpp->done());
1585//            SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
1586//            SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
1587            if (outerCoin == innerCoin) {
1588                const SkOpPtT* oce = outer->coinPtTEnd();
1589                SkASSERT(!oce->deleted());
1590                const SkOpPtT* ice = inner->coinPtTEnd();
1591                SkASSERT(!ice->deleted());
1592                if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
1593                    this->debugAddIfMissing(id, log, ocs->starter(oce), ics->starter(ice),
1594                            overS, overE, outerOpp, innerOpp,
1595                            ocs->debugEnder(oce),
1596                            ics->debugEnder(ice));
1597                }
1598            } else if (outerCoin == innerOpp) {
1599                const SkOpPtT* oce = outer->coinPtTEnd();
1600                SkASSERT(!oce->deleted());
1601                const SkOpPtT* ioe = inner->oppPtTEnd();
1602                SkASSERT(!ioe->deleted());
1603                if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
1604                    this->debugAddIfMissing(id, log, ocs->starter(oce), ios->starter(ioe),
1605                            overS, overE, outerOpp, innerCoin,
1606                            ocs->debugEnder(oce),
1607                            ios->debugEnder(ioe));
1608                }
1609            } else if (outerOpp == innerCoin) {
1610                const SkOpPtT* ooe = outer->oppPtTEnd();
1611                SkASSERT(!ooe->deleted());
1612                const SkOpPtT* ice = inner->coinPtTEnd();
1613                SkASSERT(!ice->deleted());
1614                SkASSERT(outerCoin != innerOpp);
1615                if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
1616                    this->debugAddIfMissing(id, log, oos->starter(ooe), ics->starter(ice),
1617                            overS, overE, outerCoin, innerOpp,
1618                            oos->debugEnder(ooe),
1619                            ics->debugEnder(ice));
1620                }
1621            } else if (outerOpp == innerOpp) {
1622                const SkOpPtT* ooe = outer->oppPtTEnd();
1623                SkASSERT(!ooe->deleted());
1624                const SkOpPtT* ioe = inner->oppPtTEnd();
1625                SkASSERT(!ioe->deleted());
1626                SkASSERT(outerCoin != innerCoin);
1627                if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
1628                    this->debugAddIfMissing(id, log, oos->starter(ooe), ios->starter(ioe),
1629                            overS, overE, outerCoin, innerCoin,
1630                            oos->debugEnder(ooe),
1631                            ios->debugEnder(ioe));
1632                }
1633            }
1634            this->debugValidate();
1635        }
1636    } while ((outer = outer->next()));
1637    // this->restoreHead();
1638    return;
1639}
1640
1641// Commented-out lines keep this in sync with release()
1642void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkCoincidentSpans* remove) const {
1643    const SkCoincidentSpans* head = coin;
1644    const SkCoincidentSpans* prev = nullptr;
1645    const SkCoincidentSpans* next;
1646    do {
1647        next = coin->next();
1648        if (coin == remove) {
1649            if (prev) {
1650//                prev->setNext(next);
1651            } else if (head == fHead) {
1652//                fHead = next;
1653            } else {
1654//                fTop = next;
1655            }
1656            log->record(kReleasedSpan_Glitch, id, coin);
1657        }
1658        prev = coin;
1659    } while ((coin = next));
1660    return;
1661}
1662
1663void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* deleted) const {
1664    const SkCoincidentSpans* coin = fHead;
1665    if (!coin) {
1666        return;
1667    }
1668    do {
1669        if (coin->coinPtTStart()->segment() == deleted
1670                || coin->coinPtTEnd()->segment() == deleted
1671                || coin->oppPtTStart()->segment() == deleted
1672                || coin->oppPtTEnd()->segment() == deleted) {
1673            log->record(kReleasedSpan_Glitch, id, coin);
1674        }
1675    } while ((coin = coin->next()));
1676}
1677
1678
1679// Commented-out lines keep this in sync with reorder()
1680// iterate through all coincident pairs, looking for ranges greater than 1
1681// if found, see if the opposite pair can match it -- which may require
1682// reordering the ptT pairs
1683void SkOpCoincidence::debugReorder(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1684    const SkCoincidentSpans* coin = fHead;
1685    if (!coin) {
1686        return;
1687    }
1688    do {
1689        // most commonly, concidence are one span long; check for that first
1690        int intervals = coin->spanCount();
1691        if (intervals <= 0) {
1692            return;
1693        }
1694        if (1 == intervals) {
1695#if DEBUG_COINCIDENCE_VERBOSE
1696            // SkASSERT(!coin->debugExpand(nullptr, nullptr));
1697#endif
1698            continue;
1699        }
1700        coin->debugExpand(id, log);
1701        if (coin->spanCount() <= 0) {
1702            return;
1703        }
1704        // check to see if every span in coin has a mate in opp
1705        const SkOpSpan* start = coin->coinPtTStart()->span()->upCast();
1706        bool flipped = coin->flipped();
1707        const SkOpSpanBase* oppStartBase = coin->oppPtTStart()->span();
1708        const SkOpSpan* oppStart = flipped ? oppStartBase->prev() : oppStartBase->upCast();
1709        SkDebugf("", start, oppStart);
1710    } while ((coin = coin->next()));
1711    return;
1712}
1713
1714// Commented-out lines keep this in sync with expand()
1715// expand the range by checking adjacent spans for coincidence
1716bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1717    const SkCoincidentSpans* coin = fHead;
1718    if (!coin) {
1719        return false;
1720    }
1721    bool expanded = false;
1722    do {
1723        if (coin->debugExpand(id, log)) {
1724            // check to see if multiple spans expanded so they are now identical
1725            const SkCoincidentSpans* test = fHead;
1726            do {
1727                if (coin == test) {
1728                    continue;
1729                }
1730                if (coin->coinPtTStart() == test->coinPtTStart()
1731                        && coin->oppPtTStart() == test->oppPtTStart()) {
1732                    if (log) log->record(kExpandCoin_Glitch, id, fHead, test->coinPtTStart());
1733                    break;
1734                }
1735            } while ((test = test->next()));
1736            expanded = true;
1737        }
1738    } while ((coin = coin->next()));
1739    return expanded;
1740}
1741
1742// Commented-out lines keep this in sync with removeCollapsed()
1743void SkOpCoincidence::debugRemoveCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1744    const SkCoincidentSpans* coin = fHead;
1745    if (!coin) {
1746        return;
1747    }
1748    // SkCoincidentSpans** priorPtr = &fHead;
1749    do {
1750        if (coin->coinPtTStart() == coin->coinPtTEnd()) {
1751            return;
1752        }
1753        if (coin->oppPtTStart() == coin->oppPtTEnd()) {
1754            return;
1755        }
1756        if (coin->coinPtTStart()->collapsed(coin->coinPtTEnd())) {
1757            log->record(kCollapsedCoin_Glitch, id, coin);
1758//             continue;
1759        }
1760        if (coin->oppPtTStart()->collapsed(coin->oppPtTEnd())) {
1761            log->record(kCollapsedCoin_Glitch, id, coin, coin);
1762//             continue;
1763        }
1764        // priorPtr = &coin->nextPtr();
1765    } while ((coin = coin->next()));
1766    return;
1767}
1768
1769// Commented-out lines keep this in sync with mark()
1770/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
1771void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1772    const SkCoincidentSpans* coin = fHead;
1773    if (!coin) {
1774        return;
1775    }
1776    do {
1777        if (!coin->coinPtTStartWritable()->span()->upCastable()) {
1778            return;
1779        }
1780        const SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
1781//         SkASSERT(start->deleted());
1782        const SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
1783//         SkASSERT(end->deleted());
1784        const SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
1785//         SkASSERT(oStart->deleted());
1786        const SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
1787//         SkASSERT(oEnd->deleted());
1788        bool flipped = coin->flipped();
1789        if (flipped) {
1790            SkTSwap(oStart, oEnd);
1791        }
1792        /* coin and opp spans may not match up. Mark the ends, and then let the interior
1793           get marked as many times as the spans allow */
1794        start->debugInsertCoincidence(id, log, oStart->upCast());
1795        end->debugInsertCoinEnd(id, log, oEnd);
1796        const SkOpSegment* segment = start->segment();
1797        const SkOpSegment* oSegment = oStart->segment();
1798        const SkOpSpanBase* next = start;
1799        const SkOpSpanBase* oNext = oStart;
1800        while ((next = next->upCast()->next()) != end) {
1801            if (!next->upCastable()) {
1802                return;
1803            }
1804            if (next->upCast()->debugInsertCoincidence(id, log, oSegment, flipped), false) {
1805                return;
1806            }
1807        }
1808        while ((oNext = oNext->upCast()->next()) != oEnd) {
1809            if (!oNext->upCastable()) {
1810                return;
1811            }
1812            if (oNext->upCast()->debugInsertCoincidence(id, log, segment, flipped), false) {
1813                return;
1814            }
1815        }
1816    } while ((coin = coin->next()));
1817    return;
1818}
1819#endif
1820
1821#if DEBUG_COINCIDENCE_VERBOSE
1822// Commented-out lines keep this in sync with markCollapsed()
1823void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkOpPtT* test) const {
1824    const SkCoincidentSpans* head = coin;
1825    while (coin) {
1826        if (coin->collapsed(test)) {
1827            if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
1828                log->record(kCollapsedCoin_Glitch, id, coin);
1829            }
1830            if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
1831                log->record(kCollapsedCoin_Glitch, id, coin);
1832            }
1833            this->debugRelease(id, log, head, coin);
1834        }
1835        coin = coin->next();
1836    }
1837}
1838
1839// Commented-out lines keep this in sync with markCollapsed()
1840void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* test) const {
1841    this->debugMarkCollapsed(id, log, fHead, test);
1842    this->debugMarkCollapsed(id, log, fTop, test);
1843}
1844#endif
1845
1846void SkCoincidentSpans::debugShow() const {
1847    SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1848            coinPtTStart()->segment()->debugID(),
1849            coinPtTStart()->fT, coinPtTEnd()->fT);
1850    SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1851            oppPtTStart()->segment()->debugID(),
1852            oppPtTStart()->fT, oppPtTEnd()->fT);
1853}
1854
1855void SkOpCoincidence::debugShowCoincidence() const {
1856#if DEBUG_COINCIDENCE
1857    const SkCoincidentSpans* span = fHead;
1858    while (span) {
1859        span->debugShow();
1860        span = span->next();
1861    }
1862#endif
1863}
1864
1865#if DEBUG_COINCIDENCE
1866static void DebugValidate(const SkOpSpanBase* next, const SkOpSpanBase* end,
1867        double oStart, double oEnd, const SkOpSegment* oSegment,
1868        const char* id, SkPathOpsDebug::GlitchLog* log) {
1869    SkASSERT(next != end);
1870    SkASSERT(!next->contains(end) || log);
1871    if (next->t() > end->t()) {
1872        SkTSwap(next, end);
1873    }
1874    do {
1875        const SkOpPtT* ptT = next->ptT();
1876        int index = 0;
1877        bool somethingBetween;
1878        do {
1879            ++index;
1880            ptT = ptT->next();
1881            const SkOpPtT* checkPtT = next->ptT();
1882            if (ptT == checkPtT) {
1883                break;
1884            }
1885            bool looped = false;
1886            for (int check = 0; check < index; ++check) {
1887                if ((looped = checkPtT == ptT)) {
1888                    break;
1889                }
1890                checkPtT = checkPtT->next();
1891            }
1892            if (looped) {
1893                SkASSERT(0);
1894                break;
1895            }
1896            if (ptT->deleted()) {
1897                continue;
1898            }
1899            if (ptT->segment() != oSegment) {
1900                continue;
1901            }
1902            somethingBetween |= between(oStart, ptT->fT, oEnd);
1903        } while (true);
1904        SkASSERT(somethingBetween);
1905    } while (next != end && (next = next->upCast()->next()));
1906}
1907
1908static void DebugCheckOverlap(const SkCoincidentSpans* test, const SkCoincidentSpans* list,
1909        const char* id, SkPathOpsDebug::GlitchLog* log) {
1910    if (!list) {
1911        return;
1912    }
1913    const SkOpSegment* coinSeg = test->coinPtTStart()->segment();
1914    SkASSERT(coinSeg == test->coinPtTEnd()->segment());
1915    const SkOpSegment* oppSeg = test->oppPtTStart()->segment();
1916    SkASSERT(oppSeg == test->oppPtTEnd()->segment());
1917    SkASSERT(coinSeg != test->oppPtTStart()->segment());
1918    SkDEBUGCODE(double tcs = test->coinPtTStart()->fT);
1919    SkASSERT(between(0, tcs, 1));
1920    SkDEBUGCODE(double tce = test->coinPtTEnd()->fT);
1921    SkASSERT(between(0, tce, 1));
1922    SkASSERT(tcs < tce);
1923    double tos = test->oppPtTStart()->fT;
1924    SkASSERT(between(0, tos, 1));
1925    double toe = test->oppPtTEnd()->fT;
1926    SkASSERT(between(0, toe, 1));
1927    SkASSERT(tos != toe);
1928    if (tos > toe) {
1929        SkTSwap(tos, toe);
1930    }
1931    do {
1932        double lcs, lce, los, loe;
1933        if (coinSeg == list->coinPtTStart()->segment()) {
1934            if (oppSeg != list->oppPtTStart()->segment()) {
1935                continue;
1936            }
1937            lcs = list->coinPtTStart()->fT;
1938            lce = list->coinPtTEnd()->fT;
1939            los = list->oppPtTStart()->fT;
1940            loe = list->oppPtTEnd()->fT;
1941            if (los > loe) {
1942                SkTSwap(los, loe);
1943            }
1944        } else if (coinSeg == list->oppPtTStart()->segment()) {
1945            if (oppSeg != list->coinPtTStart()->segment()) {
1946                continue;
1947            }
1948            lcs = list->oppPtTStart()->fT;
1949            lce = list->oppPtTEnd()->fT;
1950            if (lcs > lce) {
1951                SkTSwap(lcs, lce);
1952            }
1953            los = list->coinPtTStart()->fT;
1954            loe = list->coinPtTEnd()->fT;
1955        } else {
1956            continue;
1957        }
1958        SkASSERT(tce < lcs || lce < tcs);
1959        SkASSERT(toe < los || loe < tos);
1960    } while ((list = list->next()));
1961}
1962
1963
1964static void DebugCheckOverlapTop(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
1965        const char* id, SkPathOpsDebug::GlitchLog* log) {
1966    // check for overlapping coincident spans
1967    const SkCoincidentSpans* test = head;
1968    while (test) {
1969        const SkCoincidentSpans* next = test->next();
1970        DebugCheckOverlap(test, next, id, log);
1971        DebugCheckOverlap(test, opt, id, log);
1972        test = next;
1973    }
1974}
1975
1976#if DEBUG_COINCIDENCE_VERBOSE
1977void SkOpCoincidence::debugCheckOverlap(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1978    DebugCheckOverlapTop(fHead, fTop, id, log);
1979    DebugCheckOverlapTop(fTop, nullptr, id, log);
1980}
1981#endif
1982
1983static void DebugValidate(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
1984        const char* id, SkPathOpsDebug::GlitchLog* log) {
1985    // look for pts inside coincident spans that are not inside the opposite spans
1986    const SkCoincidentSpans* coin = head;
1987    while (coin) {
1988        SkASSERT(SkOpCoincidence::Ordered(coin->coinPtTStart()->segment(),
1989                coin->oppPtTStart()->segment()));
1990        SkASSERT(coin->coinPtTStart()->span()->ptT() == coin->coinPtTStart());
1991        SkASSERT(coin->coinPtTEnd()->span()->ptT() == coin->coinPtTEnd());
1992        SkASSERT(coin->oppPtTStart()->span()->ptT() == coin->oppPtTStart());
1993        SkASSERT(coin->oppPtTEnd()->span()->ptT() == coin->oppPtTEnd());
1994        DebugValidate(coin->coinPtTStart()->span(), coin->coinPtTEnd()->span(),
1995                coin->oppPtTStart()->fT, coin->oppPtTEnd()->fT, coin->oppPtTStart()->segment(),
1996                id, log);
1997        DebugValidate(coin->oppPtTStart()->span(), coin->oppPtTEnd()->span(),
1998                coin->coinPtTStart()->fT, coin->coinPtTEnd()->fT, coin->coinPtTStart()->segment(),
1999                id, log);
2000        coin = coin->next();
2001    }
2002    DebugCheckOverlapTop(head, opt, id, log);
2003}
2004#endif
2005
2006void SkOpCoincidence::debugValidate() const {
2007#if DEBUG_COINCIDENCE
2008 //   if (fGlobalState->debugCheckHealth()) {
2009//        return;
2010//    }
2011    DebugValidate(fHead, fTop, nullptr, nullptr);
2012    DebugValidate(fTop, nullptr, nullptr, nullptr);
2013#endif
2014}
2015
2016#if DEBUG_COINCIDENCE_VERBOSE
2017void SkOpCoincidence::debugCheckValid(const char* id, SkPathOpsDebug::GlitchLog* log) const {
2018    DebugValidate(fHead, fTop, id, log);
2019    DebugValidate(fTop, nullptr, id, log);
2020}
2021#endif
2022
2023#if DEBUG_COINCIDENCE_VERBOSE
2024void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const {
2025    const SkOpSegment* segment = &fHead;
2026    do {
2027        segment->debugCheckHealth(id, log);
2028    } while ((segment = segment->next()));
2029}
2030
2031// commmented-out lines keep this aligned with missingCoincidence()
2032void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
2033//    SkASSERT(fCount > 0);
2034    const SkOpSegment* segment = &fHead;
2035//    bool result = false;
2036    do {
2037        if (fState->angleCoincidence()) {
2038// #if DEBUG_ANGLE
2039//          segment->debugCheckAngleCoin();
2040// #endif
2041        } else if (segment->debugMissingCoincidence(id, log), false) {
2042//          result = true;
2043// see FIXME in missingCoincidence()
2044//
2045//
2046//
2047    //      continue;
2048        }
2049        segment = segment->next();
2050    } while (segment);
2051    return;
2052}
2053#endif
2054
2055#if DEBUG_COINCIDENCE_ORDER
2056void SkOpSegment::debugResetCoinT() const {
2057    fDebugBaseIndex = -1;
2058    fDebugBaseMin = 1;
2059    fDebugBaseMax = -1;
2060    fDebugLastIndex = -1;
2061    fDebugLastMin = 1;
2062    fDebugLastMax = -1;
2063}
2064#endif
2065
2066void SkOpSegment::debugValidate() const {
2067#if DEBUG_COINCIDENCE_ORDER
2068    {
2069        const SkOpSpanBase* span = &fHead;
2070        do {
2071            span->debugResetCoinT();
2072        } while (!span->final() && (span = span->upCast()->next()));
2073        span = &fHead;
2074        int index = 0;
2075        do {
2076            span->debugSetCoinT(index++);
2077        } while (!span->final() && (span = span->upCast()->next()));
2078    }
2079#endif
2080#if DEBUG_COINCIDENCE
2081    if (this->globalState()->debugCheckHealth()) {
2082        return;
2083    }
2084#endif
2085#if DEBUG_VALIDATE
2086    const SkOpSpanBase* span = &fHead;
2087    double lastT = -1;
2088    const SkOpSpanBase* prev = nullptr;
2089    int count = 0;
2090    int done = 0;
2091    do {
2092        if (!span->final()) {
2093            ++count;
2094            done += span->upCast()->done() ? 1 : 0;
2095        }
2096        SkASSERT(span->segment() == this);
2097        SkASSERT(!prev || prev->upCast()->next() == span);
2098        SkASSERT(!prev || prev == span->prev());
2099        prev = span;
2100        double t = span->ptT()->fT;
2101        SkASSERT(lastT < t);
2102        lastT = t;
2103        span->debugValidate();
2104    } while (!span->final() && (span = span->upCast()->next()));
2105    SkASSERT(count == fCount);
2106    SkASSERT(done == fDoneCount);
2107    SkASSERT(count >= fDoneCount);
2108    SkASSERT(span->final());
2109    span->debugValidate();
2110#endif
2111}
2112
2113#if DEBUG_COINCIDENCE_VERBOSE
2114
2115// Commented-out lines keep this in sync with addOpp()
2116void SkOpSpanBase::debugAddOpp(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const {
2117    const SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
2118    if (!oppPrev) {
2119        return;
2120    }
2121    this->debugMergeMatches(id, log, opp);
2122    this->ptT()->debugAddOpp(opp->ptT(), oppPrev);
2123    this->debugCheckForCollapsedCoincidence(id, log);
2124}
2125
2126// Commented-out lines keep this in sync with checkForCollapsedCoincidence()
2127void SkOpSpanBase::debugCheckForCollapsedCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
2128    const SkOpCoincidence* coins = this->globalState()->coincidence();
2129    if (coins->isEmpty()) {
2130        return;
2131    }
2132// the insert above may have put both ends of a coincident run in the same span
2133// for each coincident ptT in loop; see if its opposite in is also in the loop
2134// this implementation is the motivation for marking that a ptT is referenced by a coincident span
2135    const SkOpPtT* head = this->ptT();
2136    const SkOpPtT* test = head;
2137    do {
2138        if (!test->coincident()) {
2139            continue;
2140        }
2141        coins->debugMarkCollapsed(id, log, test);
2142    } while ((test = test->next()) != head);
2143}
2144#endif
2145
2146bool SkOpSpanBase::debugCoinEndLoopCheck() const {
2147    int loop = 0;
2148    const SkOpSpanBase* next = this;
2149    SkOpSpanBase* nextCoin;
2150    do {
2151        nextCoin = next->fCoinEnd;
2152        SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
2153        for (int check = 1; check < loop - 1; ++check) {
2154            const SkOpSpanBase* checkCoin = this->fCoinEnd;
2155            const SkOpSpanBase* innerCoin = checkCoin;
2156            for (int inner = check + 1; inner < loop; ++inner) {
2157                innerCoin = innerCoin->fCoinEnd;
2158                if (checkCoin == innerCoin) {
2159                    SkDebugf("*** bad coincident end loop ***\n");
2160                    return false;
2161                }
2162            }
2163        }
2164        ++loop;
2165    } while ((next = nextCoin) && next != this);
2166    return true;
2167}
2168
2169#if DEBUG_COINCIDENCE_VERBOSE
2170// Commented-out lines keep this in sync with insertCoinEnd()
2171void SkOpSpanBase::debugInsertCoinEnd(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* coin) const {
2172    if (containsCoinEnd(coin)) {
2173//         SkASSERT(coin->containsCoinEnd(this));
2174        return;
2175    }
2176    debugValidate();
2177//     SkASSERT(this != coin);
2178    log->record(kMarkCoinEnd_Glitch, id, this, coin);
2179//     coin->fCoinEnd = this->fCoinEnd;
2180//     this->fCoinEnd = coinNext;
2181    debugValidate();
2182}
2183
2184// Commented-out lines keep this in sync with mergeContained()
2185void SkOpSpanBase::debugMergeContained(const char* id, SkPathOpsDebug::GlitchLog* log, const SkPathOpsBounds& bounds, bool* deleted) const {
2186    // while adjacent spans' points are contained by the bounds, merge them
2187    const SkOpSpanBase* prev = this;
2188    const SkOpSegment* seg = this->segment();
2189    while ((prev = prev->prev()) && bounds.contains(prev->pt()) && !seg->ptsDisjoint(prev, this)) {
2190        if (prev->prev()) {
2191            log->record(kMergeContained_Glitch, id, this, prev);
2192        } else if (this->final()) {
2193            log->record(kMergeContained_Glitch, id, this, prev);
2194            // return;
2195        } else {
2196            log->record(kMergeContained_Glitch, id, prev, this);
2197        }
2198    }
2199    const SkOpSpanBase* current = this;
2200    const SkOpSpanBase* next = this;
2201    while (next->upCastable() && (next = next->upCast()->next())
2202            && bounds.contains(next->pt()) && !seg->ptsDisjoint(this, next)) {
2203        if (!current->prev() && next->final()) {
2204            log->record(kMergeContained_Glitch, id, next, current);
2205            current = next;
2206        }
2207        if (current->prev()) {
2208            log->record(kMergeContained_Glitch, id, next, current);
2209            current = next;
2210        } else {
2211            log->record(kMergeContained_Glitch, id, next, current);
2212            current = next;
2213        }
2214    }
2215#if DEBUG_COINCIDENCE
2216    // this->globalState()->coincidence()->debugValidate();
2217#endif
2218}
2219
2220// Commented-out lines keep this in sync with mergeMatches()
2221// Look to see if pt-t linked list contains same segment more than once
2222// if so, and if each pt-t is directly pointed to by spans in that segment,
2223// merge them
2224// keep the points, but remove spans so that the segment doesn't have 2 or more
2225// spans pointing to the same pt-t loop at different loop elements
2226void SkOpSpanBase::debugMergeMatches(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const {
2227    const SkOpPtT* test = &fPtT;
2228    const SkOpPtT* testNext;
2229    const SkOpPtT* stop = test;
2230    do {
2231        testNext = test->next();
2232        if (test->deleted()) {
2233            continue;
2234        }
2235        const SkOpSpanBase* testBase = test->span();
2236        SkASSERT(testBase->ptT() == test);
2237        const SkOpSegment* segment = test->segment();
2238        if (segment->done()) {
2239            continue;
2240        }
2241        const SkOpPtT* inner = opp->ptT();
2242        const SkOpPtT* innerStop = inner;
2243        do {
2244            if (inner->segment() != segment) {
2245                continue;
2246            }
2247            if (inner->deleted()) {
2248                continue;
2249            }
2250            const SkOpSpanBase* innerBase = inner->span();
2251            SkASSERT(innerBase->ptT() == inner);
2252            // when the intersection is first detected, the span base is marked if there are
2253            // more than one point in the intersection.
2254//            if (!innerBase->hasMultipleHint() && !testBase->hasMultipleHint()) {
2255                if (!zero_or_one(inner->fT)) {
2256                    log->record(kMergeMatches_Glitch, id, innerBase, test);
2257                } else {
2258                    SkASSERT(inner->fT != test->fT);
2259                    if (!zero_or_one(test->fT)) {
2260                        log->record(kMergeMatches_Glitch, id, testBase, inner);
2261                    } else {
2262                        log->record(kMergeMatches_Glitch, id, segment);
2263//                        SkDEBUGCODE(testBase->debugSetDeleted());
2264//                        test->setDeleted();
2265//                        SkDEBUGCODE(innerBase->debugSetDeleted());
2266//                        inner->setDeleted();
2267                    }
2268                }
2269#ifdef SK_DEBUG   // assert if another undeleted entry points to segment
2270                const SkOpPtT* debugInner = inner;
2271                while ((debugInner = debugInner->next()) != innerStop) {
2272                    if (debugInner->segment() != segment) {
2273                        continue;
2274                    }
2275                    if (debugInner->deleted()) {
2276                        continue;
2277                    }
2278                    SkOPASSERT(0);
2279                }
2280#endif
2281                break;
2282//            }
2283            break;
2284        } while ((inner = inner->next()) != innerStop);
2285    } while ((test = testNext) != stop);
2286    this->debugCheckForCollapsedCoincidence(id, log);
2287}
2288
2289#endif
2290
2291void SkOpSpanBase::debugResetCoinT() const {
2292#if DEBUG_COINCIDENCE_ORDER
2293    const SkOpPtT* ptT = &fPtT;
2294    do {
2295        ptT->debugResetCoinT();
2296        ptT = ptT->next();
2297    } while (ptT != &fPtT);
2298#endif
2299}
2300
2301void SkOpSpanBase::debugSetCoinT(int index) const {
2302#if DEBUG_COINCIDENCE_ORDER
2303    const SkOpPtT* ptT = &fPtT;
2304    do {
2305        if (!ptT->deleted()) {
2306            ptT->debugSetCoinT(index);
2307        }
2308        ptT = ptT->next();
2309    } while (ptT != &fPtT);
2310#endif
2311}
2312
2313const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
2314    const SkOpSpanBase* end = *endPtr;
2315    SkASSERT(this->segment() == end->segment());
2316    const SkOpSpanBase* result;
2317    if (t() < end->t()) {
2318        result = this;
2319    } else {
2320        result = end;
2321        *endPtr = this;
2322    }
2323    return result->upCast();
2324}
2325
2326void SkOpSpanBase::debugValidate() const {
2327#if DEBUG_COINCIDENCE
2328    if (this->globalState()->debugCheckHealth()) {
2329        return;
2330    }
2331#endif
2332#if DEBUG_VALIDATE
2333    const SkOpPtT* ptT = &fPtT;
2334    SkASSERT(ptT->span() == this);
2335    do {
2336//        SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
2337        ptT->debugValidate();
2338        ptT = ptT->next();
2339    } while (ptT != &fPtT);
2340    SkASSERT(this->debugCoinEndLoopCheck());
2341    if (!this->final()) {
2342        SkASSERT(this->upCast()->debugCoinLoopCheck());
2343    }
2344    if (fFromAngle) {
2345        fFromAngle->debugValidate();
2346    }
2347    if (!this->final() && this->upCast()->toAngle()) {
2348        this->upCast()->toAngle()->debugValidate();
2349    }
2350#endif
2351}
2352
2353bool SkOpSpan::debugCoinLoopCheck() const {
2354    int loop = 0;
2355    const SkOpSpan* next = this;
2356    SkOpSpan* nextCoin;
2357    do {
2358        nextCoin = next->fCoincident;
2359        SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
2360        for (int check = 1; check < loop - 1; ++check) {
2361            const SkOpSpan* checkCoin = this->fCoincident;
2362            const SkOpSpan* innerCoin = checkCoin;
2363            for (int inner = check + 1; inner < loop; ++inner) {
2364                innerCoin = innerCoin->fCoincident;
2365                if (checkCoin == innerCoin) {
2366                    SkDebugf("*** bad coincident loop ***\n");
2367                    return false;
2368                }
2369            }
2370        }
2371        ++loop;
2372    } while ((next = nextCoin) && next != this);
2373    return true;
2374}
2375
2376#if DEBUG_COINCIDENCE_VERBOSE
2377// Commented-out lines keep this in sync with insertCoincidence() in header
2378void SkOpSpan::debugInsertCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpan* coin) const {
2379    if (containsCoincidence(coin)) {
2380//         SkASSERT(coin->containsCoincidence(this));
2381        return;
2382    }
2383    debugValidate();
2384//     SkASSERT(this != coin);
2385    log->record(kMarkCoinStart_Glitch, id, this, coin);
2386//     coin->fCoincident = this->fCoincident;
2387//     this->fCoincident = coinNext;
2388    debugValidate();
2389}
2390
2391// Commented-out lines keep this in sync with insertCoincidence()
2392void SkOpSpan::debugInsertCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* segment, bool flipped) const {
2393    if (this->containsCoincidence(segment)) {
2394        return;
2395    }
2396    const SkOpPtT* next = &fPtT;
2397    while ((next = next->next()) != &fPtT) {
2398        if (next->segment() == segment) {
2399            log->record(kMarkCoinInsert_Glitch, id, flipped ? next->span()->prev() : next->span());
2400            return;
2401        }
2402    }
2403#if DEBUG_COINCIDENCE
2404    log->record(kMarkCoinMissing_Glitch, id, segment, this);
2405#endif
2406}
2407#endif
2408
2409// called only by test code
2410int SkIntersections::debugCoincidentUsed() const {
2411    if (!fIsCoincident[0]) {
2412        SkASSERT(!fIsCoincident[1]);
2413        return 0;
2414    }
2415    int count = 0;
2416    SkDEBUGCODE(int count2 = 0;)
2417    for (int index = 0; index < fUsed; ++index) {
2418        if (fIsCoincident[0] & (1 << index)) {
2419            ++count;
2420        }
2421#ifdef SK_DEBUG
2422        if (fIsCoincident[1] & (1 << index)) {
2423            ++count2;
2424        }
2425#endif
2426    }
2427    SkASSERT(count == count2);
2428    return count;
2429}
2430
2431#include "SkOpContour.h"
2432
2433// Commented-out lines keep this in sync with addOpp()
2434void SkOpPtT::debugAddOpp(const SkOpPtT* opp, const SkOpPtT* oppPrev) const {
2435    SkDEBUGCODE(const SkOpPtT* oldNext = this->fNext);
2436    SkASSERT(this != opp);
2437//    this->fNext = opp;
2438    SkASSERT(oppPrev != oldNext);
2439//    oppPrev->fNext = oldNext;
2440}
2441
2442bool SkOpPtT::debugContains(const SkOpPtT* check) const {
2443    SkASSERT(this != check);
2444    const SkOpPtT* ptT = this;
2445    int links = 0;
2446    do {
2447        ptT = ptT->next();
2448        if (ptT == check) {
2449            return true;
2450        }
2451        ++links;
2452        const SkOpPtT* test = this;
2453        for (int index = 0; index < links; ++index) {
2454            if (ptT == test) {
2455                return false;
2456            }
2457            test = test->next();
2458        }
2459    } while (true);
2460}
2461
2462const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
2463    SkASSERT(this->segment() != check);
2464    const SkOpPtT* ptT = this;
2465    int links = 0;
2466    do {
2467        ptT = ptT->next();
2468        if (ptT->segment() == check) {
2469            return ptT;
2470        }
2471        ++links;
2472        const SkOpPtT* test = this;
2473        for (int index = 0; index < links; ++index) {
2474            if (ptT == test) {
2475                return nullptr;
2476            }
2477            test = test->next();
2478        }
2479    } while (true);
2480}
2481
2482const SkOpPtT* SkOpPtT::debugEnder(const SkOpPtT* end) const {
2483    return fT < end->fT ? end : this;
2484}
2485
2486int SkOpPtT::debugLoopLimit(bool report) const {
2487    int loop = 0;
2488    const SkOpPtT* next = this;
2489    do {
2490        for (int check = 1; check < loop - 1; ++check) {
2491            const SkOpPtT* checkPtT = this->fNext;
2492            const SkOpPtT* innerPtT = checkPtT;
2493            for (int inner = check + 1; inner < loop; ++inner) {
2494                innerPtT = innerPtT->fNext;
2495                if (checkPtT == innerPtT) {
2496                    if (report) {
2497                        SkDebugf("*** bad ptT loop ***\n");
2498                    }
2499                    return loop;
2500                }
2501            }
2502        }
2503        // there's nothing wrong with extremely large loop counts -- but this may appear to hang
2504        // by taking a very long time to figure out that no loop entry is a duplicate
2505        // -- and it's likely that a large loop count is indicative of a bug somewhere
2506        if (++loop > 1000) {
2507            SkDebugf("*** loop count exceeds 1000 ***\n");
2508            return 1000;
2509        }
2510    } while ((next = next->fNext) && next != this);
2511    return 0;
2512}
2513
2514const SkOpPtT* SkOpPtT::debugOppPrev(const SkOpPtT* opp) const {
2515    return this->oppPrev(const_cast<SkOpPtT*>(opp));
2516}
2517
2518void SkOpPtT::debugResetCoinT() const {
2519#if DEBUG_COINCIDENCE_ORDER
2520    this->segment()->debugResetCoinT();
2521#endif
2522}
2523
2524void SkOpPtT::debugSetCoinT(int index) const {
2525#if DEBUG_COINCIDENCE_ORDER
2526    this->segment()->debugSetCoinT(index, fT);
2527#endif
2528}
2529
2530void SkOpPtT::debugValidate() const {
2531#if DEBUG_COINCIDENCE
2532    if (this->globalState()->debugCheckHealth()) {
2533        return;
2534    }
2535#endif
2536#if DEBUG_VALIDATE
2537    SkOpGlobalState::Phase phase = contour()->globalState()->phase();
2538    if (phase == SkOpGlobalState::kIntersecting
2539            || phase == SkOpGlobalState::kFixWinding) {
2540        return;
2541    }
2542    SkASSERT(fNext);
2543    SkASSERT(fNext != this);
2544    SkASSERT(fNext->fNext);
2545    SkASSERT(debugLoopLimit(false) == 0);
2546#endif
2547}
2548
2549static void output_scalar(SkScalar num) {
2550    if (num == (int) num) {
2551        SkDebugf("%d", (int) num);
2552    } else {
2553        SkString str;
2554        str.printf("%1.9g", num);
2555        int width = (int) str.size();
2556        const char* cStr = str.c_str();
2557        while (cStr[width - 1] == '0') {
2558            --width;
2559        }
2560        str.resize(width);
2561        SkDebugf("%sf", str.c_str());
2562    }
2563}
2564
2565static void output_points(const SkPoint* pts, int count) {
2566    for (int index = 0; index < count; ++index) {
2567        output_scalar(pts[index].fX);
2568        SkDebugf(", ");
2569        output_scalar(pts[index].fY);
2570        if (index + 1 < count) {
2571            SkDebugf(", ");
2572        }
2573    }
2574}
2575
2576static void showPathContours(SkPath::RawIter& iter, const char* pathName) {
2577    uint8_t verb;
2578    SkPoint pts[4];
2579    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
2580        switch (verb) {
2581            case SkPath::kMove_Verb:
2582                SkDebugf("    %s.moveTo(", pathName);
2583                output_points(&pts[0], 1);
2584                SkDebugf(");\n");
2585                continue;
2586            case SkPath::kLine_Verb:
2587                SkDebugf("    %s.lineTo(", pathName);
2588                output_points(&pts[1], 1);
2589                SkDebugf(");\n");
2590                break;
2591            case SkPath::kQuad_Verb:
2592                SkDebugf("    %s.quadTo(", pathName);
2593                output_points(&pts[1], 2);
2594                SkDebugf(");\n");
2595                break;
2596            case SkPath::kConic_Verb:
2597                SkDebugf("    %s.conicTo(", pathName);
2598                output_points(&pts[1], 2);
2599                SkDebugf(", %1.9gf);\n", iter.conicWeight());
2600                break;
2601            case SkPath::kCubic_Verb:
2602                SkDebugf("    %s.cubicTo(", pathName);
2603                output_points(&pts[1], 3);
2604                SkDebugf(");\n");
2605                break;
2606            case SkPath::kClose_Verb:
2607                SkDebugf("    %s.close();\n", pathName);
2608                break;
2609            default:
2610                SkDEBUGFAIL("bad verb");
2611                return;
2612        }
2613    }
2614}
2615
2616static const char* gFillTypeStr[] = {
2617    "kWinding_FillType",
2618    "kEvenOdd_FillType",
2619    "kInverseWinding_FillType",
2620    "kInverseEvenOdd_FillType"
2621};
2622
2623void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
2624    SkPath::RawIter iter(path);
2625#define SUPPORT_RECT_CONTOUR_DETECTION 0
2626#if SUPPORT_RECT_CONTOUR_DETECTION
2627    int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0;
2628    if (rectCount > 0) {
2629        SkTDArray<SkRect> rects;
2630        SkTDArray<SkPath::Direction> directions;
2631        rects.setCount(rectCount);
2632        directions.setCount(rectCount);
2633        path.rectContours(rects.begin(), directions.begin());
2634        for (int contour = 0; contour < rectCount; ++contour) {
2635            const SkRect& rect = rects[contour];
2636            SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
2637                    rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
2638                    ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
2639        }
2640        return;
2641    }
2642#endif
2643    SkPath::FillType fillType = path.getFillType();
2644    SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
2645    if (includeDeclaration) {
2646        SkDebugf("    SkPath %s;\n", name);
2647    }
2648    SkDebugf("    %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
2649    iter.setPath(path);
2650    showPathContours(iter, name);
2651}
2652