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