SkPathOpsDebug.cpp revision 025b11ecde8733d9b3eee54e132cc50a5ce8eb78 
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, 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)) {
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    bumpSpan:
609//             span->bumpSpanAdds();
610             return result;
611        }
612        if (t < result->fT) {
613            const SkOpSpan* prev = result->span()->prev();
614            if (!prev) {
615                return nullptr;  // FIXME: this is a fail case; nullptr return elsewhere means result was allocated in non-const version
616            }
617//             SkOpSpan* span = insert(prev, allocator);
618//             span->init(this, prev, t, pt);
619            this->debugValidate();
620// #if DEBUG_ADD_T
621//             SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
622//                     span->segment()->debugID(), span->debugID());
623// #endif
624//             span->bumpSpanAdds();
625            if (allocated) {
626                *allocated = true;
627            }
628            return nullptr;
629        }
630        SkASSERT(span != &fTail);
631    } while ((span = span->upCast()->next()));
632    SkASSERT(0);
633    return nullptr;
634}
635#endif
636
637#if DEBUG_ANGLE
638void SkOpSegment::debugCheckAngleCoin() const {
639    const SkOpSpanBase* base = &fHead;
640    const SkOpSpan* span;
641    do {
642        const SkOpAngle* angle = base->fromAngle();
643        if (angle && angle->debugCheckCoincidence()) {
644            angle->debugCheckNearCoincidence();
645        }
646        if (base->final()) {
647             break;
648        }
649        span = base->upCast();
650        angle = span->toAngle();
651        if (angle && angle->debugCheckCoincidence()) {
652            angle->debugCheckNearCoincidence();
653        }
654    } while ((base = span->next()));
655}
656#endif
657
658#if DEBUG_COINCIDENCE_VERBOSE
659// this mimics the order of the checks in handle coincidence
660void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
661    debugMoveMultiples(id, glitches);
662    debugMoveNearby(id, glitches);
663    debugMissingCoincidence(id, glitches);
664}
665
666// commented-out lines keep this in sync with clearAll()
667void SkOpSegment::debugClearAll(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
668    const SkOpSpan* span = &fHead;
669    do {
670        this->debugClearOne(span, id, glitches);
671    } while ((span = span->next()->upCastable()));
672    this->globalState()->coincidence()->debugRelease(id, glitches, this);
673}
674
675// commented-out lines keep this in sync with clearOne()
676void SkOpSegment::debugClearOne(const SkOpSpan* span, const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
677    if (span->windValue()) glitches->record(kCollapsedWindValue_Glitch, id, span);
678    if (span->oppValue()) glitches->record(kCollapsedOppValue_Glitch, id, span);
679    if (!span->done()) glitches->record(kCollapsedDone_Glitch, id, span);
680}
681#endif
682
683SkOpAngle* SkOpSegment::debugLastAngle() {
684    SkOpAngle* result = nullptr;
685    SkOpSpan* span = this->head();
686    do {
687        if (span->toAngle()) {
688            SkASSERT(!result);
689            result = span->toAngle();
690        }
691    } while ((span = span->next()->upCastable()));
692    SkASSERT(result);
693    return result;
694}
695
696#if DEBUG_COINCIDENCE
697// commented-out lines keep this in sync with ClearVisited
698void SkOpSegment::DebugClearVisited(const SkOpSpanBase* span) {
699    // reset visited flag back to false
700    do {
701        const SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
702        while ((ptT = ptT->next()) != stopPtT) {
703            const SkOpSegment* opp = ptT->segment();
704            opp->resetDebugVisited();
705        }
706    } while (!span->final() && (span = span->upCast()->next()));
707}
708#endif
709
710#if DEBUG_COINCIDENCE_VERBOSE
711// commented-out lines keep this in sync with missingCoincidence()
712// look for pairs of undetected coincident curves
713// assumes that segments going in have visited flag clear
714// Even though pairs of curves correct detect coincident runs, a run may be missed
715// if the coincidence is a product of multiple intersections. For instance, given
716// curves A, B, and C:
717// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
718// the end of C that the intersection is replaced with the end of C.
719// Even though A-B correctly do not detect an intersection at point 2,
720// the resulting run from point 1 to point 2 is coincident on A and B.
721void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
722    if (this->done()) {
723        return;
724    }
725    const SkOpSpan* prior = nullptr;
726    const SkOpSpanBase* spanBase = &fHead;
727//    bool result = false;
728    do {
729        const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
730        SkASSERT(ptT->span() == spanBase);
731        while ((ptT = ptT->next()) != spanStopPtT) {
732            if (ptT->deleted()) {
733                continue;
734            }
735            const SkOpSegment* opp = ptT->span()->segment();
736            if (opp->done()) {
737                continue;
738            }
739            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
740            if (!opp->debugVisited()) {
741                continue;
742            }
743            if (spanBase == &fHead) {
744                continue;
745            }
746            if (ptT->segment() == this) {
747                continue;
748            }
749            const SkOpSpan* span = spanBase->upCastable();
750            // FIXME?: this assumes that if the opposite segment is coincident then no more
751            // coincidence needs to be detected. This may not be true.
752            if (span && span->segment() != opp && span->containsCoincidence(opp)) {  // debug has additional condition since it may be called before inner duplicate points have been deleted
753                continue;
754            }
755            if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) {  // debug has additional condition since it may be called before inner duplicate points have been deleted
756                continue;
757            }
758            const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
759            // find prior span containing opp segment
760            const SkOpSegment* priorOpp = nullptr;
761            const SkOpSpan* priorTest = spanBase->prev();
762            while (!priorOpp && priorTest) {
763                priorStopPtT = priorPtT = priorTest->ptT();
764                while ((priorPtT = priorPtT->next()) != priorStopPtT) {
765                    if (priorPtT->deleted()) {
766                        continue;
767                    }
768                    SkOpSegment* segment = priorPtT->span()->segment();
769                    if (segment == opp) {
770                        prior = priorTest;
771                        priorOpp = opp;
772                        break;
773                    }
774                }
775                priorTest = priorTest->prev();
776            }
777            if (!priorOpp) {
778                continue;
779            }
780            if (priorPtT == ptT) {
781                continue;
782            }
783            const SkOpPtT* oppStart = prior->ptT();
784            const SkOpPtT* oppEnd = spanBase->ptT();
785            bool swapped = priorPtT->fT > ptT->fT;
786            if (swapped) {
787                SkTSwap(priorPtT, ptT);
788                SkTSwap(oppStart, oppEnd);
789            }
790            const SkOpCoincidence* coincidence = this->globalState()->coincidence();
791            const SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
792            const SkOpPtT* rootPtT = ptT->span()->ptT();
793            const SkOpPtT* rootOppStart = oppStart->span()->ptT();
794            const SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
795            if (coincidence->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
796                goto swapBack;
797            }
798            if (testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
799            // mark coincidence
800#if DEBUG_COINCIDENCE
801//                 SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
802//                         rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
803//                         rootOppEnd->debugID());
804#endif
805                log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd);
806                //   coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
807                // }
808#if DEBUG_COINCIDENCE
809//                SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
810#endif
811                // result = true;
812            }
813    swapBack:
814            if (swapped) {
815                SkTSwap(priorPtT, ptT);
816            }
817        }
818    } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
819    DebugClearVisited(&fHead);
820    return;
821}
822
823// commented-out lines keep this in sync with moveMultiples()
824// if a span has more than one intersection, merge the other segments' span as needed
825void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
826    debugValidate();
827    const SkOpSpanBase* test = &fHead;
828    do {
829        int addCount = test->spanAddsCount();
830        SkASSERT(addCount >= 1);
831        if (addCount == 1) {
832            continue;
833        }
834        const SkOpPtT* startPtT = test->ptT();
835        const SkOpPtT* testPtT = startPtT;
836        do {  // iterate through all spans associated with start
837            const SkOpSpanBase* oppSpan = testPtT->span();
838            if (oppSpan->spanAddsCount() == addCount) {
839                continue;
840            }
841            if (oppSpan->deleted()) {
842                continue;
843            }
844            const SkOpSegment* oppSegment = oppSpan->segment();
845            if (oppSegment == this) {
846                continue;
847            }
848            // find range of spans to consider merging
849            const SkOpSpanBase* oppPrev = oppSpan;
850            const SkOpSpanBase* oppFirst = oppSpan;
851            while ((oppPrev = oppPrev->prev())) {
852                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
853                    break;
854                }
855                if (oppPrev->spanAddsCount() == addCount) {
856                    continue;
857                }
858                if (oppPrev->deleted()) {
859                    continue;
860                }
861                oppFirst = oppPrev;
862            }
863            const SkOpSpanBase* oppNext = oppSpan;
864            const SkOpSpanBase* oppLast = oppSpan;
865            while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
866                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
867                    break;
868                }
869                if (oppNext->spanAddsCount() == addCount) {
870                    continue;
871                }
872                if (oppNext->deleted()) {
873                    continue;
874                }
875                oppLast = oppNext;
876            }
877            if (oppFirst == oppLast) {
878                continue;
879            }
880            const SkOpSpanBase* oppTest = oppFirst;
881            do {
882                if (oppTest == oppSpan) {
883                    continue;
884                }
885                // check to see if the candidate meets specific criteria:
886                // it contains spans of segments in test's loop but not including 'this'
887                const SkOpPtT* oppStartPtT = oppTest->ptT();
888                const SkOpPtT* oppPtT = oppStartPtT;
889                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
890                    const SkOpSegment* oppPtTSegment = oppPtT->segment();
891                    if (oppPtTSegment == this) {
892                        goto tryNextSpan;
893                    }
894                    const SkOpPtT* matchPtT = startPtT;
895                    do {
896                        if (matchPtT->segment() == oppPtTSegment) {
897                            goto foundMatch;
898                        }
899                    } while ((matchPtT = matchPtT->next()) != startPtT);
900                    goto tryNextSpan;
901            foundMatch:  // merge oppTest and oppSpan
902                    oppSegment->debugValidate();
903                    if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) {
904                        SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse
905                        SkASSERT(oppSpan != &oppSegment->fTail);
906                        glitches->record(kMoveMultiple_Glitch, id, oppTest, oppSpan);
907                    } else {
908                        glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest);
909                    }
910                    oppSegment->debugValidate();
911                    goto checkNextSpan;
912                }
913        tryNextSpan:
914                ;
915            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
916        } while ((testPtT = testPtT->next()) != startPtT);
917checkNextSpan:
918        ;
919    } while ((test = test->final() ? nullptr : test->upCast()->next()));
920   debugValidate();
921   return;
922}
923
924// commented-out lines keep this in sync with moveNearby()
925// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
926void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
927    debugValidate();
928    // release undeleted spans pointing to this seg that are linked to the primary span
929    const SkOpSpanBase* spanBase = &fHead;
930    do {
931        const SkOpPtT* ptT = spanBase->ptT();
932        const SkOpPtT* headPtT = ptT;
933        while ((ptT = ptT->next()) != headPtT) {
934              const SkOpSpanBase* test = ptT->span();
935            if (ptT->segment() == this && !ptT->deleted() && test != spanBase
936                    && test->ptT() == ptT) {
937                if (test->final()) {
938                    if (spanBase == &fHead) {
939                        glitches->record(kMoveNearbyClearAll_Glitch, id, this);
940//                        return;
941                    }
942                    glitches->record(kMoveNearbyReleaseFinal_Glitch, id, spanBase, ptT);
943                } else if (test->prev()) {
944                    glitches->record(kMoveNearbyRelease_Glitch, id, test, headPtT);
945                }
946//                break;
947            }
948        }
949        spanBase = spanBase->upCast()->next();
950    } while (!spanBase->final());
951
952    // This loop looks for adjacent spans which are near by
953    spanBase = &fHead;
954    do {  // iterate through all spans associated with start
955        const SkOpSpanBase* test = spanBase->upCast()->next();
956        if (this->spansNearby(spanBase, test)) {
957            if (test->final()) {
958                if (spanBase->prev()) {
959                    glitches->record(kMoveNearbyMergeFinal_Glitch, id, test);
960                } else {
961                    glitches->record(kMoveNearbyClearAll2_Glitch, id, this);
962                    // return
963                }
964            } else {
965                glitches->record(kMoveNearbyMerge_Glitch, id, spanBase);
966            }
967        }
968        spanBase = test;
969    } while (!spanBase->final());
970    debugValidate();
971}
972#endif
973
974void SkOpSegment::debugReset() {
975    this->init(this->fPts, this->fWeight, this->contour(), this->verb());
976}
977
978#if DEBUG_COINCIDENCE_ORDER
979void SkOpSegment::debugSetCoinT(int index, SkScalar t) const {
980    if (fDebugBaseMax < 0 || fDebugBaseIndex == index) {
981        fDebugBaseIndex = index;
982        fDebugBaseMin = SkTMin(t, fDebugBaseMin);
983        fDebugBaseMax = SkTMax(t, fDebugBaseMax);
984        return;
985    }
986    SkASSERT(fDebugBaseMin >= t || t >= fDebugBaseMax);
987    if (fDebugLastMax < 0 || fDebugLastIndex == index) {
988        fDebugLastIndex = index;
989        fDebugLastMin = SkTMin(t, fDebugLastMin);
990        fDebugLastMax = SkTMax(t, fDebugLastMax);
991        return;
992    }
993    SkASSERT(fDebugLastMin >= t || t >= fDebugLastMax);
994    SkASSERT((t - fDebugBaseMin > 0) == (fDebugLastMin - fDebugBaseMin > 0));
995}
996#endif
997
998#if DEBUG_ACTIVE_SPANS
999void SkOpSegment::debugShowActiveSpans() const {
1000    debugValidate();
1001    if (done()) {
1002        return;
1003    }
1004    int lastId = -1;
1005    double lastT = -1;
1006    const SkOpSpan* span = &fHead;
1007    do {
1008        if (span->done()) {
1009            continue;
1010        }
1011        if (lastId == this->debugID() && lastT == span->t()) {
1012            continue;
1013        }
1014        lastId = this->debugID();
1015        lastT = span->t();
1016        SkDebugf("%s id=%d", __FUNCTION__, this->debugID());
1017        // since endpoints may have be adjusted, show actual computed curves
1018        SkDCurve curvePart;
1019        this->subDivide(span, span->next(), &curvePart);
1020        const SkDPoint* pts = curvePart.fCubic.fPts;
1021        SkDebugf(" (%1.9g,%1.9g", pts[0].fX, pts[0].fY);
1022        for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1023            SkDebugf(" %1.9g,%1.9g", pts[vIndex].fX, pts[vIndex].fY);
1024        }
1025        if (SkPath::kConic_Verb == fVerb) {
1026            SkDebugf(" %1.9gf", curvePart.fConic.fWeight);
1027        }
1028        SkDebugf(") t=%1.9g tEnd=%1.9g", span->t(), span->next()->t());
1029        if (span->windSum() == SK_MinS32) {
1030            SkDebugf(" windSum=?");
1031        } else {
1032            SkDebugf(" windSum=%d", span->windSum());
1033        }
1034        if (span->oppValue() && span->oppSum() == SK_MinS32) {
1035            SkDebugf(" oppSum=?");
1036        } else if (span->oppValue() || span->oppSum() != SK_MinS32) {
1037            SkDebugf(" oppSum=%d", span->oppSum());
1038        }
1039        SkDebugf(" windValue=%d", span->windValue());
1040        if (span->oppValue() || span->oppSum() != SK_MinS32) {
1041            SkDebugf(" oppValue=%d", span->oppValue());
1042        }
1043        SkDebugf("\n");
1044   } while ((span = span->next()->upCastable()));
1045}
1046#endif
1047
1048#if DEBUG_MARK_DONE
1049void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
1050    const SkPoint& pt = span->ptT()->fPt;
1051    SkDebugf("%s id=%d", fun, this->debugID());
1052    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1053    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1054        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1055    }
1056    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
1057            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
1058    if (winding == SK_MinS32) {
1059        SkDebugf("?");
1060    } else {
1061        SkDebugf("%d", winding);
1062    }
1063    SkDebugf(" windSum=");
1064    if (span->windSum() == SK_MinS32) {
1065        SkDebugf("?");
1066    } else {
1067        SkDebugf("%d", span->windSum());
1068    }
1069    SkDebugf(" windValue=%d\n", span->windValue());
1070}
1071
1072void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
1073                                      int oppWinding) {
1074    const SkPoint& pt = span->ptT()->fPt;
1075    SkDebugf("%s id=%d", fun, this->debugID());
1076    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1077    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1078        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1079    }
1080    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
1081            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding);
1082    if (winding == SK_MinS32) {
1083        SkDebugf("?");
1084    } else {
1085        SkDebugf("%d", winding);
1086    }
1087    SkDebugf(" newOppSum=");
1088    if (oppWinding == SK_MinS32) {
1089        SkDebugf("?");
1090    } else {
1091        SkDebugf("%d", oppWinding);
1092    }
1093    SkDebugf(" oppSum=");
1094    if (span->oppSum() == SK_MinS32) {
1095        SkDebugf("?");
1096    } else {
1097        SkDebugf("%d", span->oppSum());
1098    }
1099    SkDebugf(" windSum=");
1100    if (span->windSum() == SK_MinS32) {
1101        SkDebugf("?");
1102    } else {
1103        SkDebugf("%d", span->windSum());
1104    }
1105    SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
1106}
1107
1108#endif
1109
1110// loop looking for a pair of angle parts that are too close to be sorted
1111/* This is called after other more simple intersection and angle sorting tests have been exhausted.
1112   This should be rarely called -- the test below is thorough and time consuming.
1113   This checks the distance between start points; the distance between
1114*/
1115#if DEBUG_ANGLE
1116void SkOpAngle::debugCheckNearCoincidence() const {
1117    const SkOpAngle* test = this;
1118    do {
1119        const SkOpSegment* testSegment = test->segment();
1120        double testStartT = test->start()->t();
1121        SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
1122        double testEndT = test->end()->t();
1123        SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
1124        double testLenSq = testStartPt.distanceSquared(testEndPt);
1125        SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
1126        double testMidT = (testStartT + testEndT) / 2;
1127        const SkOpAngle* next = test;
1128        while ((next = next->fNext) != this) {
1129            SkOpSegment* nextSegment = next->segment();
1130            double testMidDistSq = testSegment->distSq(testMidT, next);
1131            double testEndDistSq = testSegment->distSq(testEndT, next);
1132            double nextStartT = next->start()->t();
1133            SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
1134            double distSq = testStartPt.distanceSquared(nextStartPt);
1135            double nextEndT = next->end()->t();
1136            double nextMidT = (nextStartT + nextEndT) / 2;
1137            double nextMidDistSq = nextSegment->distSq(nextMidT, test);
1138            double nextEndDistSq = nextSegment->distSq(nextEndT, test);
1139            SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
1140                    testSegment->debugID(), nextSegment->debugID());
1141            SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
1142            SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
1143            SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
1144            SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
1145            SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
1146            double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
1147            SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
1148            SkDebugf("\n");
1149        }
1150        test = test->fNext;
1151    } while (test->fNext != this);
1152}
1153#endif
1154
1155#if DEBUG_ANGLE
1156SkString SkOpAngle::debugPart() const {
1157    SkString result;
1158    switch (this->segment()->verb()) {
1159        case SkPath::kLine_Verb:
1160            result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart),
1161                    this->segment()->debugID());
1162            break;
1163        case SkPath::kQuad_Verb:
1164            result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
1165                    this->segment()->debugID());
1166            break;
1167        case SkPath::kConic_Verb:
1168            result.printf(CONIC_DEBUG_STR " id=%d",
1169                    CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight),
1170                    this->segment()->debugID());
1171            break;
1172        case SkPath::kCubic_Verb:
1173            result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart),
1174                    this->segment()->debugID());
1175            break;
1176        default:
1177            SkASSERT(0);
1178    }
1179    return result;
1180}
1181#endif
1182
1183#if DEBUG_SORT
1184void SkOpAngle::debugLoop() const {
1185    const SkOpAngle* first = this;
1186    const SkOpAngle* next = this;
1187    do {
1188        next->dumpOne(true);
1189        SkDebugf("\n");
1190        next = next->fNext;
1191    } while (next && next != first);
1192    next = first;
1193    do {
1194        next->debugValidate();
1195        next = next->fNext;
1196    } while (next && next != first);
1197}
1198#endif
1199
1200void SkOpAngle::debugValidate() const {
1201#if DEBUG_COINCIDENCE
1202    if (this->globalState()->debugCheckHealth()) {
1203        return;
1204    }
1205#endif
1206#if DEBUG_VALIDATE
1207    const SkOpAngle* first = this;
1208    const SkOpAngle* next = this;
1209    int wind = 0;
1210    int opp = 0;
1211    int lastXor = -1;
1212    int lastOppXor = -1;
1213    do {
1214        if (next->unorderable()) {
1215            return;
1216        }
1217        const SkOpSpan* minSpan = next->start()->starter(next->end());
1218        if (minSpan->windValue() == SK_MinS32) {
1219            return;
1220        }
1221        bool op = next->segment()->operand();
1222        bool isXor = next->segment()->isXor();
1223        bool oppXor = next->segment()->oppXor();
1224        SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
1225        SkASSERT(!DEBUG_LIMIT_WIND_SUM
1226                || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
1227        bool useXor = op ? oppXor : isXor;
1228        SkASSERT(lastXor == -1 || lastXor == (int) useXor);
1229        lastXor = (int) useXor;
1230        wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue());
1231        if (useXor) {
1232            wind &= 1;
1233        }
1234        useXor = op ? isXor : oppXor;
1235        SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
1236        lastOppXor = (int) useXor;
1237        opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue());
1238        if (useXor) {
1239            opp &= 1;
1240        }
1241        next = next->fNext;
1242    } while (next && next != first);
1243    SkASSERT(wind == 0 || !FLAGS_runFail);
1244    SkASSERT(opp == 0 || !FLAGS_runFail);
1245#endif
1246}
1247
1248void SkOpAngle::debugValidateNext() const {
1249#if !FORCE_RELEASE
1250    const SkOpAngle* first = this;
1251    const SkOpAngle* next = first;
1252    SkTDArray<const SkOpAngle*>(angles);
1253    do {
1254//        SkASSERT_RELEASE(next->fSegment->debugContains(next));
1255        angles.push(next);
1256        next = next->next();
1257        if (next == first) {
1258            break;
1259        }
1260        SkASSERT_RELEASE(!angles.contains(next));
1261        if (!next) {
1262            return;
1263        }
1264    } while (true);
1265#endif
1266}
1267
1268#ifdef SK_DEBUG
1269void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
1270        const SkOpGlobalState* debugState) const {
1271    SkASSERT(coinPtTEnd()->span() == over || !debugState->debugRunFail());
1272    SkASSERT(oppPtTEnd()->span() == outer || !debugState->debugRunFail());
1273}
1274#endif
1275
1276#if DEBUG_COINCIDENCE_VERBOSE
1277/* Commented-out lines keep this in sync with expand */
1278bool SkCoincidentSpans::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1279    bool expanded = false;
1280    const SkOpSegment* segment = coinPtTStart()->segment();
1281    const SkOpSegment* oppSegment = oppPtTStart()->segment();
1282    do {
1283        const SkOpSpan* start = coinPtTStart()->span()->upCast();
1284        const SkOpSpan* prev = start->prev();
1285        const SkOpPtT* oppPtT;
1286        if (!prev || !(oppPtT = prev->contains(oppSegment))) {
1287            break;
1288        }
1289        double midT = (prev->t() + start->t()) / 2;
1290        if (!segment->isClose(midT, oppSegment)) {
1291            break;
1292        }
1293        if (log) log->record(kExpandCoin_Glitch, id, this, prev->ptT(), oppPtT);
1294        expanded = true;
1295    } while (false);  // actual continues while expansion is possible
1296    do {
1297        const SkOpSpanBase* end = coinPtTEnd()->span();
1298        SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
1299        const SkOpPtT* oppPtT;
1300        if (!next || !(oppPtT = next->contains(oppSegment))) {
1301            break;
1302        }
1303        double midT = (end->t() + next->t()) / 2;
1304        if (!segment->isClose(midT, oppSegment)) {
1305            break;
1306        }
1307        if (log) log->record(kExpandCoin_Glitch, id, this, next->ptT(), oppPtT);
1308        expanded = true;
1309    } while (false);  // actual continues while expansion is possible
1310    return expanded;
1311}
1312
1313#undef FAIL_IF
1314#define FAIL_IF(cond)  do { if (cond) log->record(kAddExpandedFail_Glitch, id, coin); } while (false)
1315
1316/* Commented-out lines keep this in sync with addExpanded */
1317// for each coincident pair, match the spans
1318// if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
1319void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1320    const SkCoincidentSpans* coin = this->fHead;
1321    if (!coin) {
1322        return;
1323    }
1324    do {
1325        const SkOpPtT* startPtT = coin->coinPtTStart();
1326        const SkOpPtT* oStartPtT = coin->oppPtTStart();
1327        SkASSERT(startPtT->contains(oStartPtT));
1328        SkASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
1329        const SkOpSpanBase* start = startPtT->span();
1330        const SkOpSpanBase* oStart = oStartPtT->span();
1331        const SkOpSpanBase* end = coin->coinPtTEnd()->span();
1332        const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
1333        FAIL_IF(oEnd->deleted());
1334        const SkOpSpanBase* test = start->upCast()->next();
1335        const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
1336        if (!oTest) {
1337            return;
1338        }
1339        while (test != end || oTest != oEnd) {
1340            if (!test->ptT()->contains(oTest->segment())
1341                    || !oTest->ptT()->contains(start->segment())) {
1342                // use t ranges to guess which one is missing
1343                double startRange = coin->coinPtTEnd()->fT - startPtT->fT;
1344                FAIL_IF(!startRange);
1345                double startPart = (test->t() - startPtT->fT) / startRange;
1346                double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT;
1347                FAIL_IF(!oStartRange);
1348                double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
1349                FAIL_IF(startPart == oStartPart);
1350                bool startOver = false;
1351                if (startPart < oStartPart)
1352                        log->record(kAddExpandedCoin_Glitch, id,  // strange debug formatting lines up with original
1353                                oStartPtT->fT + oStartRange * startPart, test);
1354                        else log->record(kAddExpandedCoin_Glitch, id,
1355                                startPtT->fT + startRange * oStartPart, oTest);
1356                if (false) {
1357                    SkASSERT(0);
1358                    return;
1359                }
1360                if (startOver) {
1361                    test = start;
1362                    oTest = oStart;
1363                }
1364            }
1365            if (test != end) {
1366                test = test->upCast()->next();
1367            }
1368            if (oTest != oEnd) {
1369                oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
1370                if (!oTest) {
1371                    return;
1372                }
1373            }
1374        }
1375    } while ((coin = coin->next()));
1376    return;
1377}
1378
1379/* Commented-out lines keep this in sync with addIfMissing() */
1380void SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
1381            const SkOpPtT* over1e, const char* id, SkPathOpsDebug::GlitchLog* log) const {
1382//     SkASSERT(fTop);
1383    if (fTop && alreadyAdded(fTop, outer, over1s, over1e)) {  // in debug, fTop may be null
1384        return;
1385    }
1386    if (fHead && alreadyAdded(fHead, outer, over1s, over1e)) {
1387        return;
1388    }
1389    log->record(kAddIfMissingCoin_Glitch, id, outer->coinPtTStart(), outer->coinPtTEnd(), over1s, over1e);
1390    this->debugValidate();
1391    return;
1392}
1393
1394/* Commented-out lines keep this in sync addIfMissing() */
1395void SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
1396        const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
1397        const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
1398        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, const char* id, SkPathOpsDebug::GlitchLog* log) const {
1399    double coinTs, coinTe, oppTs, oppTe;
1400    TRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
1401    TRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
1402    bool swap = coinTs > coinTe;
1403    if (swap) {
1404        SkTSwap(coinTs, coinTe);
1405    }
1406    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
1407        SkTSwap(oppTs, oppTe);
1408    }
1409    if (swap) {
1410        SkTSwap(oppTs, oppTe);
1411    }
1412    const SkOpSegment* coinSeg = coinPtTStart->segment();
1413    const SkOpSegment* oppSeg = oppPtTStart->segment();
1414    if (coinSeg == oppSeg) {
1415        return;
1416    }
1417    return this->debugAddOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, id, log);
1418}
1419
1420/* Commented-out lines keep this in sync addOrOverlap() */
1421void SkOpCoincidence::debugAddOrOverlap(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
1422        double coinTs, double coinTe, double oppTs, double oppTe, const char* id, SkPathOpsDebug::GlitchLog* log) const {
1423    SkTDArray<SkCoincidentSpans*> overlaps;
1424    SkASSERT(!fTop);   // this is (correctly) reversed in addifMissing()
1425    if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
1426        return;
1427    }
1428    if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
1429            coinTe, oppTs, oppTe, &overlaps)) {
1430        return;
1431    }
1432    const SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
1433    for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
1434        const SkCoincidentSpans* test = overlaps[index];
1435        if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
1436            log->record(kAddOrOverlap_Glitch, id, overlap, test->coinPtTStart());
1437        }
1438        if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
1439            log->record(kAddOrOverlap_Glitch, id, overlap, test->coinPtTEnd());
1440        }
1441        if (overlap->flipped()
1442                ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
1443                : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
1444            log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTStart());
1445        }
1446        if (overlap->flipped()
1447                ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
1448                : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
1449            log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTEnd());
1450        }
1451        if (!fHead) {
1452            SkAssertResult(true);
1453        }
1454    }
1455    const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
1456    const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
1457    if (overlap && cs && ce && overlap->contains(cs, ce)) {
1458        return;
1459    }
1460    SkASSERT(cs != ce || !cs);
1461    const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
1462    const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
1463    if (overlap && os && oe && overlap->contains(os, oe)) {
1464        return;
1465    }
1466    SkASSERT(true || !cs || !cs->deleted());
1467    SkASSERT(true || !os || !os->deleted());
1468    SkASSERT(true || !ce || !ce->deleted());
1469    SkASSERT(true || !oe || !oe->deleted());
1470    const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
1471    const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
1472    if (csExisting && csExisting == ceExisting) {
1473        return;
1474    }
1475    if (csExisting && (csExisting == ce || csExisting->contains(ceExisting ? ceExisting : ce))) {
1476        return;
1477    }
1478    if (ceExisting && (ceExisting == cs || ceExisting->contains(csExisting ? csExisting : cs))) {
1479        return;
1480    }
1481    const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
1482    const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
1483    if (osExisting && osExisting == oeExisting) {
1484        return;
1485    }
1486    if (osExisting && (osExisting == oe || osExisting->contains(oeExisting ? oeExisting : oe))) {
1487        return;
1488    }
1489    if (oeExisting && (oeExisting == os || oeExisting->contains(osExisting ? osExisting : os))) {
1490        return;
1491    }
1492    bool csDeleted = false, osDeleted = false, ceDeleted = false,  oeDeleted = false;
1493    this->debugValidate();
1494    if (!cs || !os) {
1495        if (!cs)
1496            cs = coinSeg->debugAddT(coinTs, nullptr);
1497        if (!os)
1498            os = oppSeg->debugAddT(oppTs, nullptr);
1499        if (cs && os) cs->span()->debugAddOppAndMerge(id, log, os->span(), &csDeleted, &osDeleted);
1500//         cs = csWritable;
1501//         os = osWritable;
1502        if ((ce && ce->deleted()) || (oe && oe->deleted())) {
1503            return;
1504        }
1505    }
1506    if (!ce || !oe) {
1507        if (!ce)
1508            ce = coinSeg->debugAddT(coinTe, nullptr);
1509        if (!oe)
1510            oe = oppSeg->debugAddT(oppTe, nullptr);
1511        if (ce && oe) ce->span()->debugAddOppAndMerge(id, log, oe->span(), &ceDeleted, &oeDeleted);
1512//         ce = ceWritable;
1513//         oe = oeWritable;
1514    }
1515    this->debugValidate();
1516    if (csDeleted || osDeleted || ceDeleted || oeDeleted) {
1517        return;
1518    }
1519    if (!cs || !ce || cs->contains(ce) || !os || !oe || os->contains(oe)) {
1520        return;
1521    }
1522//     bool result = true;
1523    if (overlap) {
1524        if (overlap->coinPtTStart()->segment() == coinSeg) {
1525                log->record(kAddMissingExtend_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
1526        } else {
1527            if (oppTs > oppTe) {
1528                SkTSwap(coinTs, coinTe);
1529                SkTSwap(oppTs, oppTe);
1530            }
1531            log->record(kAddMissingExtend_Glitch, id, oppSeg, oppTs, oppTe, coinSeg, coinTs, coinTe);
1532        }
1533#if DEBUG_COINCIDENCE_VERBOSE
1534//         if (result) {
1535//             overlap->debugShow();
1536//         }
1537#endif
1538    } else {
1539        log->record(kAddMissingCoin_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
1540#if DEBUG_COINCIDENCE_VERBOSE
1541//         fHead->debugShow();
1542#endif
1543    }
1544    this->debugValidate();
1545    return;
1546}
1547
1548// Extra commented-out lines keep this in sync with addMissing()
1549/* detects overlaps of different coincident runs on same segment */
1550/* does not detect overlaps for pairs without any segments in common */
1551// returns true if caller should loop again
1552void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1553    const SkCoincidentSpans* outer = fHead;
1554    if (!outer) {
1555        return;
1556    }
1557    // bool added = false;
1558    // fTop = outer;
1559    // fHead = nullptr;
1560    do {
1561    // addifmissing can modify the list that this is walking
1562    // save head so that walker can iterate over old data unperturbed
1563    // addifmissing adds to head freely then add saved head in the end
1564        const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
1565        const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
1566        if (outerCoin->done() || outerOpp->done()) {
1567            continue;
1568        }
1569        const SkCoincidentSpans* inner = outer;
1570        while ((inner = inner->next())) {
1571            this->debugValidate();
1572            double overS, overE;
1573            const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
1574            const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
1575            if (innerCoin->done() || innerOpp->done()) {
1576                continue;
1577            }
1578            if (outerCoin == innerCoin) {
1579                if (outerOpp != innerOpp
1580                        && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
1581                        inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
1582                    this->debugAddIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
1583                            inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
1584                            outer->oppPtTStart(), outer->oppPtTEnd(),
1585                            inner->oppPtTStart(), inner->oppPtTEnd(), id, log);
1586                }
1587            } else if (outerCoin == innerOpp) {
1588                if (outerOpp != innerCoin
1589                        && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
1590                        inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
1591                    this->debugAddIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
1592                            inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
1593                            outer->oppPtTStart(), outer->oppPtTEnd(),
1594                            inner->coinPtTStart(), inner->coinPtTEnd(), id, log);
1595                }
1596            } else if (outerOpp == innerCoin) {
1597                SkASSERT(outerCoin != innerOpp);
1598                if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
1599                        inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
1600                    this->debugAddIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
1601                            inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
1602                            outer->coinPtTStart(), outer->coinPtTEnd(),
1603                            inner->oppPtTStart(), inner->oppPtTEnd(), id, log);
1604                }
1605            } else if (outerOpp == innerOpp) {
1606                SkASSERT(outerCoin != innerCoin);
1607                if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
1608                        inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
1609                    this->debugAddIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
1610                            inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
1611                            outer->coinPtTStart(), outer->coinPtTEnd(),
1612                            inner->coinPtTStart(), inner->coinPtTEnd(), id, log);
1613                }
1614            }
1615            this->debugValidate();
1616        }
1617    } while ((outer = outer->next()));
1618    // this->restoreHead();
1619    return;
1620}
1621
1622// Commented-out lines keep this in sync with release()
1623void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* deleted) const {
1624    const SkCoincidentSpans* coin = fHead;
1625    if (!coin) {
1626        return;
1627    }
1628    do {
1629        if (coin->coinPtTStart()->segment() == deleted
1630                || coin->coinPtTEnd()->segment() == deleted
1631                || coin->oppPtTStart()->segment() == deleted
1632                || coin->oppPtTEnd()->segment() == deleted) {
1633            log->record(kReleasedSpan_Glitch, id, coin);
1634        }
1635    } while ((coin = coin->next()));
1636}
1637
1638// Commented-out lines keep this in sync with reorder()
1639// iterate through all coincident pairs, looking for ranges greater than 1
1640// if found, see if the opposite pair can match it -- which may require
1641// reordering the ptT pairs
1642void SkOpCoincidence::debugReorder(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1643    const SkCoincidentSpans* coin = fHead;
1644    if (!coin) {
1645        return;
1646    }
1647    do {
1648        // most commonly, concidence are one span long; check for that first
1649        int intervals = coin->spanCount();
1650        if (intervals = 1) {
1651#if DEBUG_COINCIDENCE_VERBOSE
1652            // SkASSERT(!coin->debugExpand(nullptr, nullptr));
1653#endif
1654            continue;
1655        }
1656        coin->debugExpand(id, log);
1657        if (coin->spanCount() <= 0) {
1658            return;
1659        }
1660        // check to see if every span in coin has a mate in opp
1661        const SkOpSpan* start = coin->coinPtTStart()->span()->upCast();
1662        bool flipped = coin->flipped();
1663        const SkOpSpanBase* oppStartBase = coin->oppPtTStart()->span();
1664        const SkOpSpan* oppStart = flipped ? oppStartBase->prev() : oppStartBase->upCast();
1665        SkDebugf("", start, oppStart);
1666    } while ((coin = coin->next()));
1667    return;
1668}
1669
1670// Commented-out lines keep this in sync with expand()
1671// expand the range by checking adjacent spans for coincidence
1672bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1673    const SkCoincidentSpans* coin = fHead;
1674    if (!coin) {
1675        return false;
1676    }
1677    bool expanded = false;
1678    do {
1679        if (coin->debugExpand(id, log)) {
1680            // check to see if multiple spans expanded so they are now identical
1681            const SkCoincidentSpans* test = fHead;
1682            do {
1683                if (coin == test) {
1684                    continue;
1685                }
1686                if (coin->coinPtTStart() == test->coinPtTStart()
1687                        && coin->oppPtTStart() == test->oppPtTStart()) {
1688                    if (log) log->record(kExpandCoin_Glitch, id, fHead, test->coinPtTStart());
1689                    break;
1690                }
1691            } while ((test = test->next()));
1692            expanded = true;
1693        }
1694    } while ((coin = coin->next()));
1695    return expanded;
1696}
1697
1698// Commented-out lines keep this in sync with removeCollapsed()
1699void SkOpCoincidence::debugRemoveCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1700    const SkCoincidentSpans* coin = fHead;
1701    if (!coin) {
1702        return;
1703    }
1704    // SkCoincidentSpans** priorPtr = &fHead;
1705    do {
1706        if (coin->coinPtTStart() == coin->coinPtTEnd()) {
1707            return;
1708        }
1709        if (coin->oppPtTStart() == coin->oppPtTEnd()) {
1710            return;
1711        }
1712        if (coin->coinPtTStart()->collapsed(coin->coinPtTEnd())) {
1713            log->record(kCollapsedCoin_Glitch, id, coin);
1714//             continue;
1715        }
1716        if (coin->oppPtTStart()->collapsed(coin->oppPtTEnd())) {
1717            log->record(kCollapsedCoin_Glitch, id, coin, coin);
1718//             continue;
1719        }
1720        // priorPtr = &coin->nextPtr();
1721    } while ((coin = coin->next()));
1722    return;
1723}
1724
1725// Commented-out lines keep this in sync with mark()
1726/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
1727void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1728    const SkCoincidentSpans* coin = fHead;
1729    if (!coin) {
1730        return;
1731    }
1732    do {
1733        const SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
1734//         SkASSERT(start->deleted());
1735        const SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
1736//         SkASSERT(end->deleted());
1737        const SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
1738//         SkASSERT(oStart->deleted());
1739        const SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
1740//         SkASSERT(oEnd->deleted());
1741        bool flipped = coin->flipped();
1742        if (flipped) {
1743            SkTSwap(oStart, oEnd);
1744        }
1745        /* coin and opp spans may not match up. Mark the ends, and then let the interior
1746           get marked as many times as the spans allow */
1747        start->debugInsertCoincidence(id, log, oStart->upCast());
1748        end->debugInsertCoinEnd(id, log, oEnd);
1749        const SkOpSegment* segment = start->segment();
1750        const SkOpSegment* oSegment = oStart->segment();
1751        const SkOpSpanBase* next = start;
1752        const SkOpSpanBase* oNext = oStart;
1753        while ((next = next->upCast()->next()) != end) {
1754            if (next->upCast()->debugInsertCoincidence(id, log, oSegment, flipped), false) {
1755                return;
1756            }
1757        }
1758        while ((oNext = oNext->upCast()->next()) != oEnd) {
1759            if (oNext->upCast()->debugInsertCoincidence(id, log, segment, flipped), false) {
1760                return;
1761            }
1762        }
1763    } while ((coin = coin->next()));
1764    return;
1765}
1766#endif
1767
1768#if DEBUG_COINCIDENCE_VERBOSE
1769// Commented-out lines keep this in sync with markCollapsed()
1770void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkOpPtT* test) const {
1771    while (coin) {
1772        if (coin->collapsed(test)) {
1773            if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
1774                log->record(kCollapsedCoin_Glitch, id, coin);
1775            }
1776            if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
1777                log->record(kCollapsedCoin_Glitch, id, coin);
1778            }
1779        }
1780        coin = coin->next();
1781    }
1782}
1783
1784// Commented-out lines keep this in sync with markCollapsed()
1785void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* test) const {
1786    this->debugMarkCollapsed(id, log, fHead, test);
1787    this->debugMarkCollapsed(id, log, fTop, test);
1788}
1789#endif
1790
1791void SkCoincidentSpans::debugShow() const {
1792    SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1793            coinPtTStart()->segment()->debugID(),
1794            coinPtTStart()->fT, coinPtTEnd()->fT);
1795    SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1796            oppPtTStart()->segment()->debugID(),
1797            oppPtTStart()->fT, oppPtTEnd()->fT);
1798}
1799
1800void SkOpCoincidence::debugShowCoincidence() const {
1801#if DEBUG_COINCIDENCE
1802    const SkCoincidentSpans* span = fHead;
1803    while (span) {
1804        span->debugShow();
1805        span = span->next();
1806    }
1807#endif
1808}
1809
1810#if DEBUG_COINCIDENCE
1811static void DebugValidate(const SkOpSpanBase* next, const SkOpSpanBase* end,
1812        double oStart, double oEnd, const SkOpSegment* oSegment,
1813        const char* id, SkPathOpsDebug::GlitchLog* log) {
1814    SkASSERT(next != end);
1815    SkASSERT(!next->contains(end) || log);
1816    if (next->t() > end->t()) {
1817        SkTSwap(next, end);
1818    }
1819    do {
1820        const SkOpPtT* ptT = next->ptT();
1821        int index = 0;
1822        bool somethingBetween;
1823        do {
1824            ++index;
1825            ptT = ptT->next();
1826            const SkOpPtT* checkPtT = next->ptT();
1827            if (ptT == checkPtT) {
1828                break;
1829            }
1830            bool looped = false;
1831            for (int check = 0; check < index; ++check) {
1832                if ((looped = checkPtT == ptT)) {
1833                    break;
1834                }
1835                checkPtT = checkPtT->next();
1836            }
1837            if (looped) {
1838                SkASSERT(0);
1839                break;
1840            }
1841            if (ptT->deleted()) {
1842                continue;
1843            }
1844            if (ptT->segment() != oSegment) {
1845                continue;
1846            }
1847            somethingBetween |= between(oStart, ptT->fT, oEnd);
1848        } while (true);
1849        SkASSERT(somethingBetween);
1850    } while (next != end && (next = next->upCast()->next()));
1851}
1852
1853static void DebugCheckOverlap(const SkCoincidentSpans* test, const SkCoincidentSpans* list,
1854        const char* id, SkPathOpsDebug::GlitchLog* log) {
1855    if (!list) {
1856        return;
1857    }
1858    const SkOpSegment* coinSeg = test->coinPtTStart()->segment();
1859    SkASSERT(coinSeg == test->coinPtTEnd()->segment());
1860    const SkOpSegment* oppSeg = test->oppPtTStart()->segment();
1861    SkASSERT(oppSeg == test->oppPtTEnd()->segment());
1862    SkASSERT(coinSeg != test->oppPtTStart()->segment());
1863    SkDEBUGCODE(double tcs = test->coinPtTStart()->fT);
1864    SkASSERT(between(0, tcs, 1));
1865    SkDEBUGCODE(double tce = test->coinPtTEnd()->fT);
1866    SkASSERT(between(0, tce, 1));
1867    SkASSERT(tcs < tce);
1868    double tos = test->oppPtTStart()->fT;
1869    SkASSERT(between(0, tos, 1));
1870    double toe = test->oppPtTEnd()->fT;
1871    SkASSERT(between(0, toe, 1));
1872    SkASSERT(tos != toe);
1873    if (tos > toe) {
1874        SkTSwap(tos, toe);
1875    }
1876    do {
1877        double lcs, lce, los, loe;
1878        if (coinSeg == list->coinPtTStart()->segment()) {
1879            if (oppSeg != list->oppPtTStart()->segment()) {
1880                continue;
1881            }
1882            lcs = list->coinPtTStart()->fT;
1883            lce = list->coinPtTEnd()->fT;
1884            los = list->oppPtTStart()->fT;
1885            loe = list->oppPtTEnd()->fT;
1886            if (los > loe) {
1887                SkTSwap(los, loe);
1888            }
1889        } else if (coinSeg == list->oppPtTStart()->segment()) {
1890            if (oppSeg != list->coinPtTStart()->segment()) {
1891                continue;
1892            }
1893            lcs = list->oppPtTStart()->fT;
1894            lce = list->oppPtTEnd()->fT;
1895            if (lcs > lce) {
1896                SkTSwap(lcs, lce);
1897            }
1898            los = list->coinPtTStart()->fT;
1899            loe = list->coinPtTEnd()->fT;
1900        } else {
1901            continue;
1902        }
1903        SkASSERT(tce < lcs || lce < tcs);
1904        SkASSERT(toe < los || loe < tos);
1905    } while ((list = list->next()));
1906}
1907
1908
1909static void DebugCheckOverlapTop(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
1910        const char* id, SkPathOpsDebug::GlitchLog* log) {
1911    // check for overlapping coincident spans
1912    const SkCoincidentSpans* test = head;
1913    while (test) {
1914        const SkCoincidentSpans* next = test->next();
1915        DebugCheckOverlap(test, next, id, log);
1916        DebugCheckOverlap(test, opt, id, log);
1917        test = next;
1918    }
1919}
1920
1921#if DEBUG_COINCIDENCE_VERBOSE
1922void SkOpCoincidence::debugCheckOverlap(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1923    DebugCheckOverlapTop(fHead, fTop, id, log);
1924    DebugCheckOverlapTop(fTop, nullptr, id, log);
1925}
1926#endif
1927
1928static void DebugValidate(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
1929        const char* id, SkPathOpsDebug::GlitchLog* log) {
1930    // look for pts inside coincident spans that are not inside the opposite spans
1931    const SkCoincidentSpans* coin = head;
1932    while (coin) {
1933        SkASSERT(SkOpCoincidence::Ordered(coin->coinPtTStart()->segment(),
1934                coin->oppPtTStart()->segment()));
1935        SkASSERT(coin->coinPtTStart()->span()->ptT() == coin->coinPtTStart());
1936        SkASSERT(coin->coinPtTEnd()->span()->ptT() == coin->coinPtTEnd());
1937        SkASSERT(coin->oppPtTStart()->span()->ptT() == coin->oppPtTStart());
1938        SkASSERT(coin->oppPtTEnd()->span()->ptT() == coin->oppPtTEnd());
1939        DebugValidate(coin->coinPtTStart()->span(), coin->coinPtTEnd()->span(),
1940                coin->oppPtTStart()->fT, coin->oppPtTEnd()->fT, coin->oppPtTStart()->segment(),
1941                id, log);
1942        DebugValidate(coin->oppPtTStart()->span(), coin->oppPtTEnd()->span(),
1943                coin->coinPtTStart()->fT, coin->coinPtTEnd()->fT, coin->coinPtTStart()->segment(),
1944                id, log);
1945        coin = coin->next();
1946    }
1947    DebugCheckOverlapTop(head, opt, id, log);
1948}
1949#endif
1950
1951void SkOpCoincidence::debugValidate() const {
1952#if DEBUG_COINCIDENCE
1953 //   if (fGlobalState->debugCheckHealth()) {
1954//        return;
1955//    }
1956    DebugValidate(fHead, fTop, nullptr, nullptr);
1957    DebugValidate(fTop, nullptr, nullptr, nullptr);
1958#endif
1959}
1960
1961#if DEBUG_COINCIDENCE_VERBOSE
1962void SkOpCoincidence::debugCheckValid(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1963    DebugValidate(fHead, fTop, id, log);
1964    DebugValidate(fTop, nullptr, id, log);
1965}
1966#endif
1967
1968#if DEBUG_COINCIDENCE_VERBOSE
1969void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1970    const SkOpSegment* segment = &fHead;
1971    do {
1972        segment->debugCheckHealth(id, log);
1973    } while ((segment = segment->next()));
1974}
1975
1976// commmented-out lines keep this aligned with missingCoincidence()
1977void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1978//    SkASSERT(fCount > 0);
1979    const SkOpSegment* segment = &fHead;
1980//    bool result = false;
1981    do {
1982        if (fState->angleCoincidence()) {
1983// #if DEBUG_ANGLE
1984//          segment->debugCheckAngleCoin();
1985// #endif
1986        } else if (segment->debugMissingCoincidence(id, log), false) {
1987//          result = true;
1988// see FIXME in missingCoincidence()
1989//
1990//
1991//
1992    //      continue;
1993        }
1994        segment = segment->next();
1995    } while (segment);
1996    return;
1997}
1998#endif
1999
2000#if DEBUG_COINCIDENCE_ORDER
2001void SkOpSegment::debugResetCoinT() const {
2002    fDebugBaseIndex = -1;
2003    fDebugBaseMin = 1;
2004    fDebugBaseMax = -1;
2005    fDebugLastIndex = -1;
2006    fDebugLastMin = 1;
2007    fDebugLastMax = -1;
2008}
2009#endif
2010
2011void SkOpSegment::debugValidate() const {
2012#if DEBUG_COINCIDENCE_ORDER
2013    {
2014        const SkOpSpanBase* span = &fHead;
2015        do {
2016            span->debugResetCoinT();
2017        } while (!span->final() && (span = span->upCast()->next()));
2018        span = &fHead;
2019        int index = 0;
2020        do {
2021            span->debugSetCoinT(index++);
2022        } while (!span->final() && (span = span->upCast()->next()));
2023    }
2024#endif
2025#if DEBUG_COINCIDENCE
2026    if (this->globalState()->debugCheckHealth()) {
2027        return;
2028    }
2029#endif
2030#if DEBUG_VALIDATE
2031    const SkOpSpanBase* span = &fHead;
2032    double lastT = -1;
2033    const SkOpSpanBase* prev = nullptr;
2034    int count = 0;
2035    int done = 0;
2036    do {
2037        if (!span->final()) {
2038            ++count;
2039            done += span->upCast()->done() ? 1 : 0;
2040        }
2041        SkASSERT(span->segment() == this);
2042        SkASSERT(!prev || prev->upCast()->next() == span);
2043        SkASSERT(!prev || prev == span->prev());
2044        prev = span;
2045        double t = span->ptT()->fT;
2046        SkASSERT(lastT < t);
2047        lastT = t;
2048        span->debugValidate();
2049    } while (!span->final() && (span = span->upCast()->next()));
2050    SkASSERT(count == fCount);
2051    SkASSERT(done == fDoneCount);
2052    SkASSERT(count >= fDoneCount);
2053    SkASSERT(span->final());
2054    span->debugValidate();
2055#endif
2056}
2057
2058#if DEBUG_COINCIDENCE_VERBOSE
2059// Commented-out lines keep this in sync with addOppAndMerge()
2060// If the added points envelop adjacent spans, merge them in.
2061void SkOpSpanBase::debugAddOppAndMerge(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp, bool* spanDeleted, bool* oppDeleted) const {
2062    if (this->ptT()->debugAddOpp(opp->ptT())) {
2063        this->debugCheckForCollapsedCoincidence(id, log);
2064    }
2065    // compute bounds of points in span
2066    SkPathOpsBounds bounds;
2067    bounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin);
2068    const SkOpPtT* head = this->ptT();
2069    const SkOpPtT* nextPt = head;
2070    do {
2071        bounds.add(nextPt->fPt);
2072    } while ((nextPt = nextPt->next()) != head);
2073    if (!bounds.width() && !bounds.height()) {
2074        return;
2075    }
2076    this->debugMergeContained(id, log, bounds, spanDeleted);
2077    opp->debugMergeContained(id, log, bounds, oppDeleted);
2078}
2079
2080// Commented-out lines keep this in sync with checkForCollapsedCoincidence()
2081void SkOpSpanBase::debugCheckForCollapsedCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
2082    const SkOpCoincidence* coins = this->globalState()->coincidence();
2083    if (coins->isEmpty()) {
2084        return;
2085    }
2086// the insert above may have put both ends of a coincident run in the same span
2087// for each coincident ptT in loop; see if its opposite in is also in the loop
2088// this implementation is the motivation for marking that a ptT is referenced by a coincident span
2089    const SkOpPtT* head = this->ptT();
2090    const SkOpPtT* test = head;
2091    do {
2092        if (!test->coincident()) {
2093            continue;
2094        }
2095        coins->debugMarkCollapsed(id, log, test);
2096    } while ((test = test->next()) != head);
2097}
2098#endif
2099
2100bool SkOpSpanBase::debugCoinEndLoopCheck() const {
2101    int loop = 0;
2102    const SkOpSpanBase* next = this;
2103    SkOpSpanBase* nextCoin;
2104    do {
2105        nextCoin = next->fCoinEnd;
2106        SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
2107        for (int check = 1; check < loop - 1; ++check) {
2108            const SkOpSpanBase* checkCoin = this->fCoinEnd;
2109            const SkOpSpanBase* innerCoin = checkCoin;
2110            for (int inner = check + 1; inner < loop; ++inner) {
2111                innerCoin = innerCoin->fCoinEnd;
2112                if (checkCoin == innerCoin) {
2113                    SkDebugf("*** bad coincident end loop ***\n");
2114                    return false;
2115                }
2116            }
2117        }
2118        ++loop;
2119    } while ((next = nextCoin) && next != this);
2120    return true;
2121}
2122
2123#if DEBUG_COINCIDENCE_VERBOSE
2124// Commented-out lines keep this in sync with insertCoinEnd()
2125void SkOpSpanBase::debugInsertCoinEnd(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* coin) const {
2126    if (containsCoinEnd(coin)) {
2127//         SkASSERT(coin->containsCoinEnd(this));
2128        return;
2129    }
2130    debugValidate();
2131//     SkASSERT(this != coin);
2132    log->record(kMarkCoinEnd_Glitch, id, this, coin);
2133//     coin->fCoinEnd = this->fCoinEnd;
2134//     this->fCoinEnd = coinNext;
2135    debugValidate();
2136}
2137
2138// Commented-out lines keep this in sync with mergeContained()
2139void SkOpSpanBase::debugMergeContained(const char* id, SkPathOpsDebug::GlitchLog* log, const SkPathOpsBounds& bounds, bool* deleted) const {
2140    // while adjacent spans' points are contained by the bounds, merge them
2141    const SkOpSpanBase* prev = this;
2142    const SkOpSegment* seg = this->segment();
2143    while ((prev = prev->prev()) && bounds.contains(prev->pt()) && !seg->ptsDisjoint(prev, this)) {
2144        if (prev->prev()) {
2145            log->record(kMergeContained_Glitch, id, this, prev);
2146        } else if (this->final()) {
2147            log->record(kMergeContained_Glitch, id, this, prev);
2148            // return;
2149        } else {
2150            log->record(kMergeContained_Glitch, id, prev, this);
2151        }
2152    }
2153    const SkOpSpanBase* current = this;
2154    const SkOpSpanBase* next = this;
2155    while (next->upCastable() && (next = next->upCast()->next())
2156            && bounds.contains(next->pt()) && !seg->ptsDisjoint(this, next)) {
2157        if (!current->prev() && next->final()) {
2158            log->record(kMergeContained_Glitch, id, next, current);
2159            current = next;
2160        }
2161        if (current->prev()) {
2162            log->record(kMergeContained_Glitch, id, next, current);
2163            current = next;
2164        } else {
2165            log->record(kMergeContained_Glitch, id, next, current);
2166            current = next;
2167        }
2168    }
2169#if DEBUG_COINCIDENCE
2170    // this->globalState()->coincidence()->debugValidate();
2171#endif
2172}
2173#endif
2174
2175void SkOpSpanBase::debugResetCoinT() const {
2176#if DEBUG_COINCIDENCE_ORDER
2177    const SkOpPtT* ptT = &fPtT;
2178    do {
2179        ptT->debugResetCoinT();
2180        ptT = ptT->next();
2181    } while (ptT != &fPtT);
2182#endif
2183}
2184
2185void SkOpSpanBase::debugSetCoinT(int index) const {
2186#if DEBUG_COINCIDENCE_ORDER
2187    const SkOpPtT* ptT = &fPtT;
2188    do {
2189        if (!ptT->deleted()) {
2190            ptT->debugSetCoinT(index);
2191        }
2192        ptT = ptT->next();
2193    } while (ptT != &fPtT);
2194#endif
2195}
2196
2197const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
2198    const SkOpSpanBase* end = *endPtr;
2199    SkASSERT(this->segment() == end->segment());
2200    const SkOpSpanBase* result;
2201    if (t() < end->t()) {
2202        result = this;
2203    } else {
2204        result = end;
2205        *endPtr = this;
2206    }
2207    return result->upCast();
2208}
2209
2210void SkOpSpanBase::debugValidate() const {
2211#if DEBUG_COINCIDENCE
2212    if (this->globalState()->debugCheckHealth()) {
2213        return;
2214    }
2215#endif
2216#if DEBUG_VALIDATE
2217    const SkOpPtT* ptT = &fPtT;
2218    SkASSERT(ptT->span() == this);
2219    do {
2220//        SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
2221        ptT->debugValidate();
2222        ptT = ptT->next();
2223    } while (ptT != &fPtT);
2224    SkASSERT(this->debugCoinEndLoopCheck());
2225    if (!this->final()) {
2226        SkASSERT(this->upCast()->debugCoinLoopCheck());
2227    }
2228    if (fFromAngle) {
2229        fFromAngle->debugValidate();
2230    }
2231    if (!this->final() && this->upCast()->toAngle()) {
2232        this->upCast()->toAngle()->debugValidate();
2233    }
2234#endif
2235}
2236
2237bool SkOpSpan::debugCoinLoopCheck() const {
2238    int loop = 0;
2239    const SkOpSpan* next = this;
2240    SkOpSpan* nextCoin;
2241    do {
2242        nextCoin = next->fCoincident;
2243        SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
2244        for (int check = 1; check < loop - 1; ++check) {
2245            const SkOpSpan* checkCoin = this->fCoincident;
2246            const SkOpSpan* innerCoin = checkCoin;
2247            for (int inner = check + 1; inner < loop; ++inner) {
2248                innerCoin = innerCoin->fCoincident;
2249                if (checkCoin == innerCoin) {
2250                    SkDebugf("*** bad coincident loop ***\n");
2251                    return false;
2252                }
2253            }
2254        }
2255        ++loop;
2256    } while ((next = nextCoin) && next != this);
2257    return true;
2258}
2259
2260#if DEBUG_COINCIDENCE_VERBOSE
2261// Commented-out lines keep this in sync with insertCoincidence() in header
2262void SkOpSpan::debugInsertCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpan* coin) const {
2263    if (containsCoincidence(coin)) {
2264//         SkASSERT(coin->containsCoincidence(this));
2265        return;
2266    }
2267    debugValidate();
2268//     SkASSERT(this != coin);
2269    log->record(kMarkCoinStart_Glitch, id, this, coin);
2270//     coin->fCoincident = this->fCoincident;
2271//     this->fCoincident = coinNext;
2272    debugValidate();
2273}
2274
2275// Commented-out lines keep this in sync with insertCoincidence()
2276void SkOpSpan::debugInsertCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* segment, bool flipped) const {
2277    if (this->containsCoincidence(segment)) {
2278        return;
2279    }
2280    const SkOpPtT* next = &fPtT;
2281    while ((next = next->next()) != &fPtT) {
2282        if (next->segment() == segment) {
2283            log->record(kMarkCoinInsert_Glitch, id, flipped ? next->span()->prev() : next->span());
2284            return;
2285        }
2286    }
2287#if DEBUG_COINCIDENCE
2288    log->record(kMarkCoinMissing_Glitch, id, segment, this);
2289#endif
2290}
2291#endif
2292
2293// called only by test code
2294int SkIntersections::debugCoincidentUsed() const {
2295    if (!fIsCoincident[0]) {
2296        SkASSERT(!fIsCoincident[1]);
2297        return 0;
2298    }
2299    int count = 0;
2300    SkDEBUGCODE(int count2 = 0;)
2301    for (int index = 0; index < fUsed; ++index) {
2302        if (fIsCoincident[0] & (1 << index)) {
2303            ++count;
2304        }
2305#ifdef SK_DEBUG
2306        if (fIsCoincident[1] & (1 << index)) {
2307            ++count2;
2308        }
2309#endif
2310    }
2311    SkASSERT(count == count2);
2312    return count;
2313}
2314
2315#include "SkOpContour.h"
2316
2317// Commented-out lines keep this in sync with addOpp()
2318bool SkOpPtT::debugAddOpp(const SkOpPtT* opp) const {
2319    // find the fOpp ptr to opp
2320    const SkOpPtT* oppPrev = opp->fNext;
2321    if (oppPrev == this) {
2322        return false;
2323    }
2324    while (oppPrev->fNext != opp) {
2325        oppPrev = oppPrev->fNext;
2326        if (oppPrev == this) {
2327            return false;
2328        }
2329    }
2330//    const SkOpPtT* oldNext = this->fNext;
2331    SkASSERT(this != opp);
2332//    this->fNext = opp;
2333//    SkASSERT(oppPrev != oldNext);
2334//    oppPrev->fNext = oldNext;
2335    return true;
2336}
2337
2338bool SkOpPtT::debugContains(const SkOpPtT* check) const {
2339    SkASSERT(this != check);
2340    const SkOpPtT* ptT = this;
2341    int links = 0;
2342    do {
2343        ptT = ptT->next();
2344        if (ptT == check) {
2345            return true;
2346        }
2347        ++links;
2348        const SkOpPtT* test = this;
2349        for (int index = 0; index < links; ++index) {
2350            if (ptT == test) {
2351                return false;
2352            }
2353            test = test->next();
2354        }
2355    } while (true);
2356}
2357
2358const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
2359    SkASSERT(this->segment() != check);
2360    const SkOpPtT* ptT = this;
2361    int links = 0;
2362    do {
2363        ptT = ptT->next();
2364        if (ptT->segment() == check) {
2365            return ptT;
2366        }
2367        ++links;
2368        const SkOpPtT* test = this;
2369        for (int index = 0; index < links; ++index) {
2370            if (ptT == test) {
2371                return nullptr;
2372            }
2373            test = test->next();
2374        }
2375    } while (true);
2376}
2377
2378int SkOpPtT::debugLoopLimit(bool report) const {
2379    int loop = 0;
2380    const SkOpPtT* next = this;
2381    do {
2382        for (int check = 1; check < loop - 1; ++check) {
2383            const SkOpPtT* checkPtT = this->fNext;
2384            const SkOpPtT* innerPtT = checkPtT;
2385            for (int inner = check + 1; inner < loop; ++inner) {
2386                innerPtT = innerPtT->fNext;
2387                if (checkPtT == innerPtT) {
2388                    if (report) {
2389                        SkDebugf("*** bad ptT loop ***\n");
2390                    }
2391                    return loop;
2392                }
2393            }
2394        }
2395        // there's nothing wrong with extremely large loop counts -- but this may appear to hang
2396        // by taking a very long time to figure out that no loop entry is a duplicate
2397        // -- and it's likely that a large loop count is indicative of a bug somewhere
2398        if (++loop > 1000) {
2399            SkDebugf("*** loop count exceeds 1000 ***\n");
2400            return 1000;
2401        }
2402    } while ((next = next->fNext) && next != this);
2403    return 0;
2404}
2405
2406void SkOpPtT::debugResetCoinT() const {
2407#if DEBUG_COINCIDENCE_ORDER
2408    this->segment()->debugResetCoinT();
2409#endif
2410}
2411
2412void SkOpPtT::debugSetCoinT(int index) const {
2413#if DEBUG_COINCIDENCE_ORDER
2414    this->segment()->debugSetCoinT(index, fT);
2415#endif
2416}
2417
2418void SkOpPtT::debugValidate() const {
2419#if DEBUG_COINCIDENCE
2420    if (this->globalState()->debugCheckHealth()) {
2421        return;
2422    }
2423#endif
2424#if DEBUG_VALIDATE
2425    SkOpGlobalState::Phase phase = contour()->globalState()->phase();
2426    if (phase == SkOpGlobalState::kIntersecting
2427            || phase == SkOpGlobalState::kFixWinding) {
2428        return;
2429    }
2430    SkASSERT(fNext);
2431    SkASSERT(fNext != this);
2432    SkASSERT(fNext->fNext);
2433    SkASSERT(debugLoopLimit(false) == 0);
2434#endif
2435}
2436
2437static void output_scalar(SkScalar num) {
2438    if (num == (int) num) {
2439        SkDebugf("%d", (int) num);
2440    } else {
2441        SkString str;
2442        str.printf("%1.9g", num);
2443        int width = (int) str.size();
2444        const char* cStr = str.c_str();
2445        while (cStr[width - 1] == '0') {
2446            --width;
2447        }
2448        str.resize(width);
2449        SkDebugf("%sf", str.c_str());
2450    }
2451}
2452
2453static void output_points(const SkPoint* pts, int count) {
2454    for (int index = 0; index < count; ++index) {
2455        output_scalar(pts[index].fX);
2456        SkDebugf(", ");
2457        output_scalar(pts[index].fY);
2458        if (index + 1 < count) {
2459            SkDebugf(", ");
2460        }
2461    }
2462}
2463
2464static void showPathContours(SkPath::RawIter& iter, const char* pathName) {
2465    uint8_t verb;
2466    SkPoint pts[4];
2467    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
2468        switch (verb) {
2469            case SkPath::kMove_Verb:
2470                SkDebugf("    %s.moveTo(", pathName);
2471                output_points(&pts[0], 1);
2472                SkDebugf(");\n");
2473                continue;
2474            case SkPath::kLine_Verb:
2475                SkDebugf("    %s.lineTo(", pathName);
2476                output_points(&pts[1], 1);
2477                SkDebugf(");\n");
2478                break;
2479            case SkPath::kQuad_Verb:
2480                SkDebugf("    %s.quadTo(", pathName);
2481                output_points(&pts[1], 2);
2482                SkDebugf(");\n");
2483                break;
2484            case SkPath::kConic_Verb:
2485                SkDebugf("    %s.conicTo(", pathName);
2486                output_points(&pts[1], 2);
2487                SkDebugf(", %1.9gf);\n", iter.conicWeight());
2488                break;
2489            case SkPath::kCubic_Verb:
2490                SkDebugf("    %s.cubicTo(", pathName);
2491                output_points(&pts[1], 3);
2492                SkDebugf(");\n");
2493                break;
2494            case SkPath::kClose_Verb:
2495                SkDebugf("    %s.close();\n", pathName);
2496                break;
2497            default:
2498                SkDEBUGFAIL("bad verb");
2499                return;
2500        }
2501    }
2502}
2503
2504static const char* gFillTypeStr[] = {
2505    "kWinding_FillType",
2506    "kEvenOdd_FillType",
2507    "kInverseWinding_FillType",
2508    "kInverseEvenOdd_FillType"
2509};
2510
2511void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
2512    SkPath::RawIter iter(path);
2513#define SUPPORT_RECT_CONTOUR_DETECTION 0
2514#if SUPPORT_RECT_CONTOUR_DETECTION
2515    int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0;
2516    if (rectCount > 0) {
2517        SkTDArray<SkRect> rects;
2518        SkTDArray<SkPath::Direction> directions;
2519        rects.setCount(rectCount);
2520        directions.setCount(rectCount);
2521        path.rectContours(rects.begin(), directions.begin());
2522        for (int contour = 0; contour < rectCount; ++contour) {
2523            const SkRect& rect = rects[contour];
2524            SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
2525                    rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
2526                    ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
2527        }
2528        return;
2529    }
2530#endif
2531    SkPath::FillType fillType = path.getFillType();
2532    SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
2533    if (includeDeclaration) {
2534        SkDebugf("    SkPath %s;\n", name);
2535    }
2536    SkDebugf("    %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
2537    iter.setPath(path);
2538    showPathContours(iter, name);
2539}
2540