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