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