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