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