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