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