SkPathOpsDebug.cpp revision 26ad22ab61539e3d3b6bc5e0da8dcebbd52a53de 
1/*
2 * Copyright 2013 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkMutex.h"
9#include "SkOpCoincidence.h"
10#include "SkOpContour.h"
11#include "SkPath.h"
12#include "SkPathOpsDebug.h"
13#include "SkString.h"
14
15struct SkCoincidentSpans;
16
17#if DEBUG_VALIDATE
18extern bool FLAGS_runFail;
19#endif
20
21#if DEBUG_SORT
22int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
23int SkPathOpsDebug::gSortCount;
24#endif
25
26#if DEBUG_ACTIVE_OP
27const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"};
28#endif
29
30#if defined SK_DEBUG || !FORCE_RELEASE
31
32const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
33
34int SkPathOpsDebug::gContourID = 0;
35int SkPathOpsDebug::gSegmentID = 0;
36
37bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray,
38        const SkOpSpanBase* span) {
39    for (int index = 0; index < chaseArray.count(); ++index) {
40        const SkOpSpanBase* entry = chaseArray[index];
41        if (entry == span) {
42            return true;
43        }
44    }
45    return false;
46}
47#endif
48
49#if DEBUG_COINCIDENCE
50enum GlitchType {
51    kAddCorruptCoin_Glitch,
52    kAddExpandedCoin_Glitch,
53    kAddMissingCoin_Glitch,
54    kCollapsedCoin_Glitch,
55    kCollapsedDone_Glitch,
56    kCollapsedOppValue_Glitch,
57    kCollapsedSpan_Glitch,
58    kCollapsedWindValue_Glitch,
59    kDeletedCoin_Glitch,
60    kExpandCoin_Glitch,
61    kMarkCoinEnd_Glitch,
62    kMarkCoinInsert_Glitch,
63    kMissingCoin_Glitch,
64    kMissingDone_Glitch,
65    kMissingIntersection_Glitch,
66    kMoveMultiple_Glitch,
67    kUnaligned_Glitch,
68    kUnalignedHead_Glitch,
69    kUnalignedTail_Glitch,
70    kUndetachedSpan_Glitch,
71    kUnmergedSpan_Glitch,
72};
73
74static const int kGlitchType_Count = kUnmergedSpan_Glitch + 1;
75
76struct SpanGlitch {
77    const char* fStage;
78    const SkOpSpanBase* fBase;
79    const SkOpSpanBase* fSuspect;
80    const SkCoincidentSpans* fCoin;
81    const SkOpSegment* fSegment;
82    const SkOpPtT* fCoinSpan;
83    const SkOpPtT* fEndSpan;
84    const SkOpPtT* fOppSpan;
85    const SkOpPtT* fOppEndSpan;
86    double fT;
87    SkPoint fPt;
88    GlitchType fType;
89};
90
91struct SkPathOpsDebug::GlitchLog {
92    SpanGlitch* recordCommon(GlitchType type, const char* stage) {
93        SpanGlitch* glitch = fGlitches.push();
94        glitch->fStage = stage;
95        glitch->fBase = nullptr;
96        glitch->fSuspect = nullptr;
97        glitch->fCoin = nullptr;
98        glitch->fSegment = nullptr;
99        glitch->fCoinSpan = nullptr;
100        glitch->fEndSpan = nullptr;
101        glitch->fOppSpan = nullptr;
102        glitch->fOppEndSpan = nullptr;
103        glitch->fT = SK_ScalarNaN;
104        glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN };
105        glitch->fType = type;
106        return glitch;
107    }
108
109    void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
110            const SkOpSpanBase* suspect = NULL) {
111        SpanGlitch* glitch = recordCommon(type, stage);
112        glitch->fBase = base;
113        glitch->fSuspect = suspect;
114    }
115
116    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
117            const SkOpPtT* coinSpan) {
118        SpanGlitch* glitch = recordCommon(type, stage);
119        glitch->fCoin = coin;
120        glitch->fCoinSpan = coinSpan;
121    }
122
123    void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
124            const SkOpSegment* seg, double t, SkPoint pt) {
125        SpanGlitch* glitch = recordCommon(type, stage);
126        glitch->fBase = base;
127        glitch->fSegment = seg;
128        glitch->fT = t;
129        glitch->fPt = pt;
130    }
131
132    void record(GlitchType type, const char* stage, const SkOpSpanBase* base, double t,
133            SkPoint pt) {
134        SpanGlitch* glitch = recordCommon(type, stage);
135        glitch->fBase = base;
136        glitch->fT = t;
137        glitch->fPt = pt;
138    }
139
140    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
141            const SkOpPtT* coinSpan, const SkOpPtT* endSpan) {
142        SpanGlitch* glitch = recordCommon(type, stage);
143        glitch->fCoin = coin;
144        glitch->fCoinSpan = coinSpan;
145        glitch->fEndSpan = endSpan;
146    }
147
148    void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
149            const SkOpSpanBase* suspect) {
150        SpanGlitch* glitch = recordCommon(type, stage);
151        glitch->fSuspect = suspect;
152        glitch->fCoin = coin;
153    }
154
155    void record(GlitchType type, const char* stage, const SkOpPtT* ptTS, const SkOpPtT* ptTE,
156            const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) {
157        SpanGlitch* glitch = recordCommon(type, stage);
158        glitch->fCoinSpan = ptTS;
159        glitch->fEndSpan = ptTE;
160        glitch->fOppSpan = oPtTS;
161        glitch->fOppEndSpan = oPtTE;
162    }
163
164    SkTDArray<SpanGlitch> fGlitches;
165};
166
167void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
168    GlitchLog glitches;
169    const SkOpContour* contour = contourList;
170    const SkOpCoincidence* coincidence = contour->globalState()->coincidence();
171    do {
172        contour->debugCheckHealth(id, &glitches);
173        contour->debugMissingCoincidence(id, &glitches, coincidence);
174    } while ((contour = contour->next()));
175    coincidence->debugFixAligned(id, &glitches);
176    coincidence->debugAddMissing(id, &glitches);
177    coincidence->debugExpand(id, &glitches);
178    coincidence->debugAddExpanded(id, &glitches);
179    coincidence->debugMark(id, &glitches);
180    unsigned mask = 0;
181    for (int index = 0; index < glitches.fGlitches.count(); ++index) {
182        const SpanGlitch& glitch = glitches.fGlitches[index];
183        mask |= 1 << glitch.fType;
184    }
185    for (int index = 0; index < kGlitchType_Count; ++index) {
186        SkDebugf(mask & (1 << index) ? "x" : "-");
187    }
188    SkDebugf("  %s\n", id);
189}
190#endif
191
192#if defined SK_DEBUG || !FORCE_RELEASE
193void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
194    size_t len = strlen(str);
195    bool num = false;
196    for (size_t idx = 0; idx < len; ++idx) {
197        if (num && str[idx] == 'e') {
198            if (len + 2 >= bufferLen) {
199                return;
200            }
201            memmove(&str[idx + 2], &str[idx + 1], len - idx);
202            str[idx] = '*';
203            str[idx + 1] = '^';
204            ++len;
205        }
206        num = str[idx] >= '0' && str[idx] <= '9';
207    }
208}
209
210bool SkPathOpsDebug::ValidWind(int wind) {
211    return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
212}
213
214void SkPathOpsDebug::WindingPrintf(int wind) {
215    if (wind == SK_MinS32) {
216        SkDebugf("?");
217    } else {
218        SkDebugf("%d", wind);
219    }
220}
221#endif //  defined SK_DEBUG || !FORCE_RELEASE
222
223
224#if DEBUG_SHOW_TEST_NAME
225void* SkPathOpsDebug::CreateNameStr() { return new char[DEBUG_FILENAME_STRING_LENGTH]; }
226
227void SkPathOpsDebug::DeleteNameStr(void* v) { delete[] reinterpret_cast<char*>(v); }
228
229void SkPathOpsDebug::BumpTestName(char* test) {
230    char* num = test + strlen(test);
231    while (num[-1] >= '0' && num[-1] <= '9') {
232        --num;
233    }
234    if (num[0] == '\0') {
235        return;
236    }
237    int dec = atoi(num);
238    if (dec == 0) {
239        return;
240    }
241    ++dec;
242    SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
243}
244#endif
245
246static void show_function_header(const char* functionName) {
247    SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName);
248    if (strcmp("skphealth_com76", functionName) == 0) {
249        SkDebugf("found it\n");
250    }
251}
252
253static const char* gOpStrs[] = {
254    "kDifference_SkPathOp",
255    "kIntersect_SkPathOp",
256    "kUnion_SkPathOp",
257    "kXor_PathOp",
258    "kReverseDifference_SkPathOp",
259};
260
261const char* SkPathOpsDebug::OpStr(SkPathOp op) {
262    return gOpStrs[op];
263}
264
265static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) {
266    SkDebugf("    testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]);
267    SkDebugf("}\n");
268}
269
270SK_DECLARE_STATIC_MUTEX(gTestMutex);
271
272void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
273        const char* testName) {
274    SkAutoMutexAcquire ac(gTestMutex);
275    show_function_header(testName);
276    ShowOnePath(a, "path", true);
277    ShowOnePath(b, "pathB", true);
278    show_op(shapeOp, "path", "pathB");
279}
280
281#include "SkPathOpsTypes.h"
282#include "SkIntersectionHelper.h"
283#include "SkIntersections.h"
284
285#if DEBUG_T_SECT_LOOP_COUNT
286void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt,
287        const SkIntersectionHelper& wn) {
288    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
289        SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index;
290        if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) {
291            continue;
292        }
293        fDebugLoopCount[index] = i->debugLoopCount(looper);
294        fDebugWorstVerb[index * 2] = wt.segment()->verb();
295        fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb();
296        sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8);
297        memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(),
298                (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint));
299        memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(),
300                (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint));
301        fDebugWorstWeight[index * 2] = wt.weight();
302        fDebugWorstWeight[index * 2 + 1] = wn.weight();
303    }
304    i->debugResetLoopCount();
305}
306
307void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) {
308    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
309        if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) {
310            continue;
311        }
312        fDebugLoopCount[index] = local->fDebugLoopCount[index];
313        fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2];
314        fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1];
315        memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4],
316                sizeof(SkPoint) * 8);
317        fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2];
318        fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1];
319    }
320    local->debugResetLoopCounts();
321}
322
323static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) {
324    if (!verb) {
325        return;
326    }
327    const char* verbs[] = { "", "line", "quad", "conic", "cubic" };
328    SkDebugf("%s: {{", verbs[verb]);
329    int ptCount = SkPathOpsVerbToPoints(verb);
330    for (int index = 0; index <= ptCount; ++index) {
331        SkDPoint::Dump((&pts)[index]);
332        if (index < ptCount - 1) {
333            SkDebugf(", ");
334        }
335    }
336    SkDebugf("}");
337    if (weight != 1) {
338        SkDebugf(", ");
339        if (weight == floorf(weight)) {
340            SkDebugf("%.0f", weight);
341        } else {
342            SkDebugf("%1.9gf", weight);
343        }
344    }
345    SkDebugf("}\n");
346}
347
348void SkOpGlobalState::debugLoopReport() {
349    const char* loops[] = { "iterations", "coinChecks", "perpCalcs" };
350    SkDebugf("\n");
351    for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
352        SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]);
353        dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4],
354                fDebugWorstWeight[index * 2]);
355        dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4],
356                fDebugWorstWeight[index * 2 + 1]);
357    }
358}
359
360void SkOpGlobalState::debugResetLoopCounts() {
361    sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
362    sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb));
363    sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts));
364    sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight));
365}
366#endif
367
368#ifdef SK_DEBUG
369bool SkOpGlobalState::debugRunFail() const {
370#if DEBUG_VALIDATE
371    return FLAGS_runFail;
372#else
373    return false;
374#endif
375}
376#endif
377
378#if DEBUG_T_SECT_LOOP_COUNT
379void SkIntersections::debugBumpLoopCount(DebugLoop index) {
380    fDebugLoopCount[index]++;
381}
382
383int SkIntersections::debugLoopCount(DebugLoop index) const {
384    return fDebugLoopCount[index];
385}
386
387void SkIntersections::debugResetLoopCount() {
388    sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
389}
390#endif
391
392#include "SkPathOpsCubic.h"
393#include "SkPathOpsQuad.h"
394
395SkDCubic SkDQuad::debugToCubic() const {
396    SkDCubic cubic;
397    cubic[0] = fPts[0];
398    cubic[2] = fPts[1];
399    cubic[3] = fPts[2];
400    cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3;
401    cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3;
402    cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3;
403    cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3;
404    return cubic;
405}
406
407#include "SkOpAngle.h"
408#include "SkOpSegment.h"
409
410#if DEBUG_COINCIDENCE
411void SkOpSegment::debugAddAlignIntersection(const char* id, SkPathOpsDebug::GlitchLog* log,
412        const SkOpPtT& endPtT, const SkPoint& oldPt,  const SkOpContourHead* contourList) const {
413    const SkPoint& newPt = endPtT.fPt;
414    if (newPt == oldPt) {
415        return;
416    }
417    SkPoint line[2] = { newPt, oldPt };
418    SkPathOpsBounds lineBounds;
419    lineBounds.setBounds(line, 2);
420    SkDLine aLine;
421    aLine.set(line);
422    const SkOpContour* current = contourList;
423    do {
424        if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) {
425            continue;
426        }
427        const SkOpSegment* segment = current->first();
428        do {
429            if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) {
430                continue;
431            }
432            if (newPt == segment->fPts[0]) {
433                continue;
434            }
435            if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
436                continue;
437            }
438            if (oldPt == segment->fPts[0]) {
439                continue;
440            }
441            if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
442                continue;
443            }
444            if (endPtT.debugContains(segment)) {
445                continue;
446            }
447            SkIntersections i;
448            switch (segment->fVerb) {
449                case SkPath::kLine_Verb: {
450                    SkDLine bLine;
451                    bLine.set(segment->fPts);
452                    i.intersect(bLine, aLine);
453                    } break;
454                case SkPath::kQuad_Verb: {
455                    SkDQuad bQuad;
456                    bQuad.set(segment->fPts);
457                    i.intersect(bQuad, aLine);
458                    } break;
459                case SkPath::kConic_Verb: {
460                    SkDConic bConic;
461                    bConic.set(segment->fPts, segment->fWeight);
462                    i.intersect(bConic, aLine);
463                    } break;
464                case SkPath::kCubic_Verb: {
465                    SkDCubic bCubic;
466                    bCubic.set(segment->fPts);
467                    i.intersect(bCubic, aLine);
468                    } break;
469                default:
470                    SkASSERT(0);
471            }
472            if (i.used()) {
473                SkASSERT(i.used() == 1);
474                SkASSERT(!zero_or_one(i[0][0]));
475                SkOpSpanBase* checkSpan = fHead.next();
476                while (!checkSpan->final()) {
477                    if (checkSpan->contains(segment)) {
478                        goto nextSegment;
479                    }
480                    checkSpan = checkSpan->upCast()->next();
481                }
482                log->record(kMissingIntersection_Glitch, id, checkSpan, segment, i[0][0], newPt);
483            }
484    nextSegment:
485            ;
486        } while ((segment = segment->next()));
487    } while ((current = current->next()));
488}
489
490bool SkOpSegment::debugAddMissing(double t, const SkOpSegment* opp) const {
491    const SkOpSpanBase* existing = nullptr;
492    const SkOpSpanBase* test = &fHead;
493    double testT;
494    do {
495        if ((testT = test->ptT()->fT) >= t) {
496            if (testT == t) {
497                existing = test;
498            }
499            break;
500        }
501    } while ((test = test->upCast()->next()));
502    return !existing || !existing->debugContains(opp);
503}
504
505void SkOpSegment::debugAlign(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
506    const SkOpSpanBase* span = &fHead;
507    if (!span->aligned()) {
508        if (!span->debugAlignedEnd(0, fPts[0])) {
509            glitches->record(kUnalignedHead_Glitch, id, span);
510        }
511    }
512    while ((span = span->upCast()->next())) {
513        if (span == &fTail) {
514            break;
515        }
516        if (!span->aligned()) {
517            glitches->record(kUnaligned_Glitch, id, span);
518        }
519    }
520    if (!span->aligned()) {
521        span->debugAlignedEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]);
522    }
523    if (this->collapsed()) {
524        const SkOpSpan* span = &fHead;
525        do {
526            if (span->windValue()) {
527                glitches->record(kCollapsedWindValue_Glitch, id, span);
528            }
529            if (span->oppValue()) {
530                glitches->record(kCollapsedOppValue_Glitch, id, span);
531            }
532            if (!span->done()) {
533                glitches->record(kCollapsedDone_Glitch, id, span);
534            }
535        } while ((span = span->next()->upCastable()));
536    }
537}
538#endif
539
540#if DEBUG_ANGLE
541void SkOpSegment::debugCheckAngleCoin() const {
542    const SkOpSpanBase* base = &fHead;
543    const SkOpSpan* span;
544    do {
545        const SkOpAngle* angle = base->fromAngle();
546        if (angle && angle->fCheckCoincidence) {
547            angle->debugCheckNearCoincidence();
548        }
549        if (base->final()) {
550             break;
551        }
552        span = base->upCast();
553        angle = span->toAngle();
554        if (angle && angle->fCheckCoincidence) {
555            angle->debugCheckNearCoincidence();
556        }
557    } while ((base = span->next()));
558}
559#endif
560
561#if DEBUG_COINCIDENCE
562// this mimics the order of the checks in handle coincidence
563void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
564    debugMoveMultiples(id, glitches);
565    debugFindCollapsed(id, glitches);
566    debugMoveNearby(id, glitches);
567    debugAlign(id, glitches);
568    debugAddAlignIntersections(id, glitches, this->globalState()->contourHead());
569
570}
571
572void SkOpSegment::debugFindCollapsed(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
573    if (fHead.contains(&fTail)) {
574        const SkOpSpan* span = this->head();
575        bool missingDone = false;
576        do {
577            missingDone |= !span->done();
578        } while ((span = span->next()->upCastable()));
579        if (missingDone) {
580            glitches->record(kMissingDone_Glitch, id, &fHead);
581        }
582        if (!fHead.debugAlignedEnd(0, fHead.pt())) {
583            glitches->record(kUnalignedHead_Glitch, id, &fHead);
584        }
585        if (!fTail.aligned()) {
586            glitches->record(kUnalignedTail_Glitch, id, &fTail);
587        }
588    }
589}
590#endif
591
592SkOpAngle* SkOpSegment::debugLastAngle() {
593    SkOpAngle* result = nullptr;
594    SkOpSpan* span = this->head();
595    do {
596        if (span->toAngle()) {
597            SkASSERT(!result);
598            result = span->toAngle();
599        }
600    } while ((span = span->next()->upCastable()));
601    SkASSERT(result);
602    return result;
603}
604
605#if DEBUG_COINCIDENCE
606void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
607        const SkOpCoincidence* coincidences) const {
608    if (this->verb() != SkPath::kLine_Verb) {
609        return;
610    }
611    if (this->done()) {
612        return;
613    }
614    const SkOpSpan* prior = nullptr;
615    const SkOpSpanBase* spanBase = &fHead;
616    do {
617        const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
618        SkASSERT(ptT->span() == spanBase);
619        while ((ptT = ptT->next()) != spanStopPtT) {
620            if (ptT->deleted()) {
621                continue;
622            }
623            SkOpSegment* opp = ptT->span()->segment();
624//            if (opp->verb() == SkPath::kLine_Verb) {
625//                continue;
626//            }
627            if (opp->done()) {
628                continue;
629            }
630            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
631            if (!opp->visited()) {
632                continue;
633            }
634            if (spanBase == &fHead) {
635                continue;
636            }
637            const SkOpSpan* span = spanBase->upCastable();
638            // FIXME?: this assumes that if the opposite segment is coincident then no more
639            // coincidence needs to be detected. This may not be true.
640            if (span && span->segment() != opp && span->containsCoincidence(opp)) {
641                continue;
642            }
643            if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) {
644                continue;
645            }
646            const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
647            // find prior span containing opp segment
648            const SkOpSegment* priorOpp = nullptr;
649            const SkOpSpan* priorTest = spanBase->prev();
650            while (!priorOpp && priorTest) {
651                priorStopPtT = priorPtT = priorTest->ptT();
652                while ((priorPtT = priorPtT->next()) != priorStopPtT) {
653                    if (priorPtT->deleted()) {
654                        continue;
655                    }
656                    SkOpSegment* segment = priorPtT->span()->segment();
657                    if (segment == opp) {
658                        prior = priorTest;
659                        priorOpp = opp;
660                        break;
661                    }
662                }
663                priorTest = priorTest->prev();
664            }
665            if (!priorOpp) {
666                continue;
667            }
668            const SkOpPtT* oppStart = prior->ptT();
669            const SkOpPtT* oppEnd = spanBase->ptT();
670            bool swapped = priorPtT->fT > ptT->fT;
671            if (swapped) {
672                SkTSwap(priorPtT, ptT);
673                SkTSwap(oppStart, oppEnd);
674            }
675            bool flipped = oppStart->fT > oppEnd->fT;
676            bool coincident = false;
677            if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
678                goto swapBack;
679            }
680            if (opp->verb() == SkPath::kLine_Verb) {
681                coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) ||
682                        SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) &&
683                        (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) ||
684                        SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt));
685            }
686            if (!coincident) {
687                coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000);
688            }
689            if (coincident) {
690                log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd);
691            }
692    swapBack:
693            if (swapped) {
694                SkTSwap(priorPtT, ptT);
695            }
696        }
697    } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
698}
699
700void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
701    const SkOpSpanBase* test = &fHead;
702    do {
703        int addCount = test->spanAddsCount();
704        SkASSERT(addCount >= 1);
705        if (addCount == 1) {
706            continue;
707        }
708        const SkOpPtT* startPtT = test->ptT();
709        const SkOpPtT* testPtT = startPtT;
710        do {  // iterate through all spans associated with start
711            const SkOpSpanBase* oppSpan = testPtT->span();
712            if (oppSpan->spanAddsCount() == addCount) {
713                continue;
714            }
715            if (oppSpan->deleted()) {
716                continue;
717            }
718            const SkOpSegment* oppSegment = oppSpan->segment();
719            if (oppSegment == this) {
720                continue;
721            }
722            // find range of spans to consider merging
723            const SkOpSpanBase* oppPrev = oppSpan;
724            const SkOpSpanBase* oppFirst = oppSpan;
725            while ((oppPrev = oppPrev->prev())) {
726                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
727                    break;
728                }
729                if (oppPrev->spanAddsCount() == addCount) {
730                    continue;
731                }
732                if (oppPrev->deleted()) {
733                    continue;
734                }
735                oppFirst = oppPrev;
736            }
737            const SkOpSpanBase* oppNext = oppSpan;
738            const SkOpSpanBase* oppLast = oppSpan;
739            while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
740                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
741                    break;
742                }
743                if (oppNext->spanAddsCount() == addCount) {
744                    continue;
745                }
746                if (oppNext->deleted()) {
747                    continue;
748                }
749                oppLast = oppNext;
750            }
751            if (oppFirst == oppLast) {
752                continue;
753            }
754            const SkOpSpanBase* oppTest = oppFirst;
755            do {
756                if (oppTest == oppSpan) {
757                    continue;
758                }
759                // check to see if the candidate meets specific criteria:
760                // it contains spans of segments in test's loop but not including 'this'
761                const SkOpPtT* oppStartPtT = oppTest->ptT();
762                const SkOpPtT* oppPtT = oppStartPtT;
763                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
764                    const SkOpSegment* oppPtTSegment = oppPtT->segment();
765                    if (oppPtTSegment == this) {
766                        goto tryNextSpan;
767                    }
768                    const SkOpPtT* matchPtT = startPtT;
769                    do {
770                        if (matchPtT->segment() == oppPtTSegment) {
771                            goto foundMatch;
772                        }
773                    } while ((matchPtT = matchPtT->next()) != startPtT);
774                    goto tryNextSpan;
775            foundMatch:  // merge oppTest and oppSpan
776                    if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) {
777                        SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse
778                        SkASSERT(oppSpan != &oppSegment->fTail);
779                        glitches->record(kMoveMultiple_Glitch, id, oppTest, oppSpan);
780                    } else {
781                        glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest);
782                    }
783                    goto checkNextSpan;
784                }
785        tryNextSpan:
786                ;
787            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
788        } while ((testPtT = testPtT->next()) != startPtT);
789checkNextSpan:
790        ;
791    } while ((test = test->final() ? nullptr : test->upCast()->next()));
792}
793
794void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
795        const SkOpSpanBase* spanS = &fHead;
796    do {
797        const SkOpSpanBase* test = spanS->upCast()->next();
798        const SkOpSpanBase* next;
799        if (spanS->contains(test)) {
800            if (!test->final()) {
801                glitches->record(kUndetachedSpan_Glitch, id, test, spanS);
802            } else if (spanS != &fHead) {
803                glitches->record(kUndetachedSpan_Glitch, id, spanS, test);
804            }
805        }
806        do {  // iterate through all spans associated with start
807            const SkOpPtT* startBase = spanS->ptT();
808            next = test->final() ? nullptr : test->upCast()->next();
809            do {
810                const SkOpPtT* testBase = test->ptT();
811                do {
812                    if (startBase == testBase) {
813                        goto checkNextSpan;
814                    }
815                    if (testBase->duplicate()) {
816                        continue;
817                    }
818                    if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) {
819                        if (test == &this->fTail) {
820                            if (spanS == &fHead) {
821                                glitches->record(kCollapsedSpan_Glitch, id, spanS);
822                            } else {
823                                glitches->record(kUnmergedSpan_Glitch, id, &this->fTail, spanS);
824                            }
825                        } else {
826                            glitches->record(kUnmergedSpan_Glitch, id, spanS, test);
827                            goto checkNextSpan;
828                        }
829                    }
830                } while ((testBase = testBase->next()) != test->ptT());
831            } while ((startBase = startBase->next()) != spanS->ptT());
832    checkNextSpan:
833            ;
834        } while ((test = next));
835        spanS = spanS->upCast()->next();
836    } while (!spanS->final());
837}
838#endif
839
840void SkOpSegment::debugReset() {
841    this->init(this->fPts, this->fWeight, this->contour(), this->verb());
842}
843
844#if DEBUG_ACTIVE_SPANS
845void SkOpSegment::debugShowActiveSpans() const {
846    debugValidate();
847    if (done()) {
848        return;
849    }
850    int lastId = -1;
851    double lastT = -1;
852    const SkOpSpan* span = &fHead;
853    do {
854        if (span->done()) {
855            continue;
856        }
857        if (lastId == this->debugID() && lastT == span->t()) {
858            continue;
859        }
860        lastId = this->debugID();
861        lastT = span->t();
862        SkDebugf("%s id=%d", __FUNCTION__, this->debugID());
863        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
864        for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
865            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
866        }
867        if (SkPath::kConic_Verb == fVerb) {
868            SkDebugf(" %1.9gf", fWeight);
869        }
870        const SkOpPtT* ptT = span->ptT();
871        SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY);
872        SkDebugf(" tEnd=%1.9g", span->next()->t());
873        if (span->windSum() == SK_MinS32) {
874            SkDebugf(" windSum=?");
875        } else {
876            SkDebugf(" windSum=%d", span->windSum());
877        }
878        if (span->oppValue() && span->oppSum() == SK_MinS32) {
879            SkDebugf(" oppSum=?");
880        } else if (span->oppValue() || span->oppSum() != SK_MinS32) {
881            SkDebugf(" oppSum=%d", span->oppSum());
882        }
883        SkDebugf(" windValue=%d", span->windValue());
884        if (span->oppValue() || span->oppSum() != SK_MinS32) {
885            SkDebugf(" oppValue=%d", span->oppValue());
886        }
887        SkDebugf("\n");
888   } while ((span = span->next()->upCastable()));
889}
890#endif
891
892#if DEBUG_MARK_DONE
893void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
894    const SkPoint& pt = span->ptT()->fPt;
895    SkDebugf("%s id=%d", fun, this->debugID());
896    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
897    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
898        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
899    }
900    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
901            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
902    if (winding == SK_MinS32) {
903        SkDebugf("?");
904    } else {
905        SkDebugf("%d", winding);
906    }
907    SkDebugf(" windSum=");
908    if (span->windSum() == SK_MinS32) {
909        SkDebugf("?");
910    } else {
911        SkDebugf("%d", span->windSum());
912    }
913    SkDebugf(" windValue=%d\n", span->windValue());
914}
915
916void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
917                                      int oppWinding) {
918    const SkPoint& pt = span->ptT()->fPt;
919    SkDebugf("%s id=%d", fun, this->debugID());
920    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
921    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
922        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
923    }
924    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
925            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding);
926    if (winding == SK_MinS32) {
927        SkDebugf("?");
928    } else {
929        SkDebugf("%d", winding);
930    }
931    SkDebugf(" newOppSum=");
932    if (oppWinding == SK_MinS32) {
933        SkDebugf("?");
934    } else {
935        SkDebugf("%d", oppWinding);
936    }
937    SkDebugf(" oppSum=");
938    if (span->oppSum() == SK_MinS32) {
939        SkDebugf("?");
940    } else {
941        SkDebugf("%d", span->oppSum());
942    }
943    SkDebugf(" windSum=");
944    if (span->windSum() == SK_MinS32) {
945        SkDebugf("?");
946    } else {
947        SkDebugf("%d", span->windSum());
948    }
949    SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
950}
951
952#endif
953
954// loop looking for a pair of angle parts that are too close to be sorted
955/* This is called after other more simple intersection and angle sorting tests have been exhausted.
956   This should be rarely called -- the test below is thorough and time consuming.
957   This checks the distance between start points; the distance between
958*/
959#if DEBUG_ANGLE
960void SkOpAngle::debugCheckNearCoincidence() const {
961    const SkOpAngle* test = this;
962    do {
963        const SkOpSegment* testSegment = test->segment();
964        double testStartT = test->start()->t();
965        SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
966        double testEndT = test->end()->t();
967        SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
968        double testLenSq = testStartPt.distanceSquared(testEndPt);
969        SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
970        double testMidT = (testStartT + testEndT) / 2;
971        const SkOpAngle* next = test;
972        while ((next = next->fNext) != this) {
973            SkOpSegment* nextSegment = next->segment();
974            double testMidDistSq = testSegment->distSq(testMidT, next);
975            double testEndDistSq = testSegment->distSq(testEndT, next);
976            double nextStartT = next->start()->t();
977            SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
978            double distSq = testStartPt.distanceSquared(nextStartPt);
979            double nextEndT = next->end()->t();
980            double nextMidT = (nextStartT + nextEndT) / 2;
981            double nextMidDistSq = nextSegment->distSq(nextMidT, test);
982            double nextEndDistSq = nextSegment->distSq(nextEndT, test);
983            SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
984                    testSegment->debugID(), nextSegment->debugID());
985            SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
986            SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
987            SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
988            SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
989            SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
990            double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
991            SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
992            SkDebugf("\n");
993        }
994        test = test->fNext;
995    } while (test->fNext != this);
996}
997#endif
998
999#if DEBUG_ANGLE
1000SkString SkOpAngle::debugPart() const {
1001    SkString result;
1002    switch (this->segment()->verb()) {
1003        case SkPath::kLine_Verb:
1004            result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart),
1005                    this->segment()->debugID());
1006            break;
1007        case SkPath::kQuad_Verb:
1008            result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
1009                    this->segment()->debugID());
1010            break;
1011        case SkPath::kConic_Verb:
1012            result.printf(CONIC_DEBUG_STR " id=%d",
1013                    CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight),
1014                    this->segment()->debugID());
1015            break;
1016        case SkPath::kCubic_Verb:
1017            result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart),
1018                    this->segment()->debugID());
1019            break;
1020        default:
1021            SkASSERT(0);
1022    }
1023    return result;
1024}
1025#endif
1026
1027#if DEBUG_SORT
1028void SkOpAngle::debugLoop() const {
1029    const SkOpAngle* first = this;
1030    const SkOpAngle* next = this;
1031    do {
1032        next->dumpOne(true);
1033        SkDebugf("\n");
1034        next = next->fNext;
1035    } while (next && next != first);
1036    next = first;
1037    do {
1038        next->debugValidate();
1039        next = next->fNext;
1040    } while (next && next != first);
1041}
1042#endif
1043
1044void SkOpAngle::debugValidate() const {
1045#if DEBUG_VALIDATE
1046    const SkOpAngle* first = this;
1047    const SkOpAngle* next = this;
1048    int wind = 0;
1049    int opp = 0;
1050    int lastXor = -1;
1051    int lastOppXor = -1;
1052    do {
1053        if (next->unorderable()) {
1054            return;
1055        }
1056        const SkOpSpan* minSpan = next->start()->starter(next->end());
1057        if (minSpan->windValue() == SK_MinS32) {
1058            return;
1059        }
1060        bool op = next->segment()->operand();
1061        bool isXor = next->segment()->isXor();
1062        bool oppXor = next->segment()->oppXor();
1063        SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
1064        SkASSERT(!DEBUG_LIMIT_WIND_SUM
1065                || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
1066        bool useXor = op ? oppXor : isXor;
1067        SkASSERT(lastXor == -1 || lastXor == (int) useXor);
1068        lastXor = (int) useXor;
1069        wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue());
1070        if (useXor) {
1071            wind &= 1;
1072        }
1073        useXor = op ? isXor : oppXor;
1074        SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
1075        lastOppXor = (int) useXor;
1076        opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue());
1077        if (useXor) {
1078            opp &= 1;
1079        }
1080        next = next->fNext;
1081    } while (next && next != first);
1082    SkASSERT(wind == 0 || !FLAGS_runFail);
1083    SkASSERT(opp == 0 || !FLAGS_runFail);
1084#endif
1085}
1086
1087void SkOpAngle::debugValidateNext() const {
1088#if !FORCE_RELEASE
1089    const SkOpAngle* first = this;
1090    const SkOpAngle* next = first;
1091    SkTDArray<const SkOpAngle*>(angles);
1092    do {
1093//        SK_ALWAYSBREAK(next->fSegment->debugContains(next));
1094        angles.push(next);
1095        next = next->next();
1096        if (next == first) {
1097            break;
1098        }
1099        SK_ALWAYSBREAK(!angles.contains(next));
1100        if (!next) {
1101            return;
1102        }
1103    } while (true);
1104#endif
1105}
1106
1107
1108#if DEBUG_COINCIDENCE
1109void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1110    // for each coincident pair, match the spans
1111    // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
1112    const SkCoincidentSpans* coin = this->fHead;
1113    if (!coin) {
1114        coin = this->fTop;
1115    }
1116    SkASSERT(coin);
1117    do {
1118        const SkOpPtT* startPtT = coin->fCoinPtTStart;
1119        const SkOpPtT* oStartPtT = coin->fOppPtTStart;
1120        SkASSERT(startPtT->contains(oStartPtT));
1121        SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
1122        const SkOpSpanBase* start = startPtT->span();
1123        const SkOpSpanBase* oStart = oStartPtT->span();
1124        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1125        const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
1126        const SkOpSpanBase* test = start->upCast()->next();
1127        const SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
1128        while (test != end || oTest != oEnd) {
1129            bool bumpTest = true;
1130            bool bumpOTest = true;
1131            if (!test->ptT()->contains(oTest->ptT())) {
1132                // use t ranges to guess which one is missing
1133                double startRange = coin->fCoinPtTEnd->fT - startPtT->fT;
1134                double startPart = (test->t() - startPtT->fT) / startRange;
1135                double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT;
1136                double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
1137                if (startPart == oStartPart) {
1138                    // data is corrupt
1139                    log->record(kAddCorruptCoin_Glitch, id, start, oStart);
1140                    break;
1141                }
1142                if (startPart < oStartPart) {
1143                    double newT = oStartPtT->fT + oStartRange * startPart;
1144                    log->record(kAddExpandedCoin_Glitch, id, oStart, newT, test->pt());
1145                    bumpOTest = false;
1146                } else {
1147                    double newT = startPtT->fT + startRange * oStartPart;
1148                    log->record(kAddExpandedCoin_Glitch, id, start, newT, oTest->pt());
1149                    bumpTest = false;
1150                }
1151            }
1152            if (bumpTest && test != end) {
1153                test = test->upCast()->next();
1154            }
1155            if (bumpOTest && oTest != oEnd) {
1156                oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
1157            }
1158        }
1159    } while ((coin = coin->fNext));
1160}
1161
1162static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
1163        const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
1164    double denom = overE->fT - overS->fT;
1165    double start = 0 < denom ? tStart : tEnd;
1166    double end = 0 < denom ? tEnd : tStart;
1167    double sRatio = (start - overS->fT) / denom;
1168    double eRatio = (end - overS->fT) / denom;
1169    *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
1170    *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
1171}
1172
1173bool SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
1174            const SkOpPtT* over1e) const {
1175    const SkCoincidentSpans* check = this->fTop;
1176    while (check) {
1177        if (check->fCoinPtTStart->span() == over1s->span()
1178                && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) {
1179            SkASSERT(check->fCoinPtTEnd->span() == over1e->span()
1180                    || !fDebugState->debugRunFail());
1181            SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span()
1182                    || !fDebugState->debugRunFail());
1183            return false;
1184        }
1185        if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span()
1186                && check->fOppPtTStart->span() == over1s->span()) {
1187            SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span()
1188                    || !fDebugState->debugRunFail());
1189            SkASSERT(check->fOppPtTEnd->span() == over1e->span()
1190                    || !fDebugState->debugRunFail());
1191            return false;
1192        }
1193        check = check->fNext;
1194    }
1195    return true;
1196}
1197
1198bool SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
1199                      const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
1200        SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
1201        SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const {
1202    double coinTs, coinTe, oppTs, oppTe;
1203    t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
1204    t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
1205    const SkOpSegment* coinSeg = coinPtTStart->segment();
1206    const SkOpSegment* oppSeg = oppPtTStart->segment();
1207    SkASSERT(coinSeg != oppSeg);
1208    const SkCoincidentSpans* check = this->fTop;
1209    ;
1210    while (check) {
1211        const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment();
1212        const SkOpSegment* checkOppSeg;
1213        if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) {
1214            goto next;
1215        }
1216        checkOppSeg = check->fOppPtTStart->segment();
1217        if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) {
1218            goto next;
1219        }
1220        {
1221            int cTs = coinTs;
1222            int cTe = coinTe;
1223            int oTs = oppTs;
1224            int oTe = oppTe;
1225            if (checkCoinSeg != coinSeg) {
1226                SkASSERT(checkOppSeg != oppSeg);
1227                SkTSwap(cTs, oTs);
1228                SkTSwap(cTe, oTe);
1229            }
1230            int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT)
1231                           + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT)
1232                           + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT)
1233                           + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT);
1234    //        SkASSERT(tweenCount == 0 || tweenCount == 4);
1235            if (tweenCount) {
1236                return true;
1237            }
1238        }
1239next:
1240        check = check->fNext;
1241    }
1242    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
1243        SkTSwap(oppTs, oppTe);
1244    }
1245    if (coinTs > coinTe) {
1246        SkTSwap(coinTs, coinTe);
1247        SkTSwap(oppTs, oppTe);
1248    }
1249    bool cs = coinSeg->debugAddMissing(coinTs, oppSeg);
1250    bool ce = coinSeg->debugAddMissing(coinTe, oppSeg);
1251    if (cs == ce) {
1252        return false;
1253    }
1254    return true;
1255}
1256
1257void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1258    const SkCoincidentSpans* outer = fHead;
1259    if (!outer) {
1260        return;
1261    }
1262    do {
1263    // addifmissing can modify the list that this is walking
1264    // save head so that walker can iterate over old data unperturbed
1265    // addifmissing adds to head freely then add saved head in the end
1266        const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
1267        SkASSERT(outerCoin == outer->fCoinPtTEnd->segment());
1268        const SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
1269        SkASSERT(outerOpp == outer->fOppPtTEnd->segment());
1270        const SkCoincidentSpans* inner = outer;
1271        while ((inner = inner->fNext)) {
1272            double overS, overE;
1273            const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
1274            SkASSERT(innerCoin == inner->fCoinPtTEnd->segment());
1275            const SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
1276            SkASSERT(innerOpp == inner->fOppPtTEnd->segment());
1277            if (outerCoin == innerCoin
1278                    && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1279                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
1280                if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1281                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
1282                        outer->fOppPtTStart, outer->fOppPtTEnd,
1283                        inner->fOppPtTStart, inner->fOppPtTEnd)) {
1284                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart);
1285                }
1286            } else if (outerCoin == innerOpp
1287                    && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1288                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
1289                if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1290                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
1291                        outer->fOppPtTStart, outer->fOppPtTEnd,
1292                        inner->fCoinPtTStart, inner->fCoinPtTEnd)) {
1293                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart);
1294                }
1295            } else if (outerOpp == innerCoin
1296                    && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
1297                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
1298                if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
1299                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
1300                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
1301                        inner->fOppPtTStart, inner->fOppPtTEnd)) {
1302                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart);
1303                }
1304            } else if (outerOpp == innerOpp
1305                    && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
1306                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
1307                if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
1308                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
1309                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
1310                        inner->fCoinPtTStart, inner->fCoinPtTEnd)) {
1311                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart);
1312                }
1313            } else if (outerCoin != innerCoin) {
1314                // check to see if outer span overlaps the inner span
1315                    // look for inner segment in pt-t list
1316                    // if present, and if t values are in coincident range
1317                    // add two pairs of new coincidence
1318                const SkOpPtT* testS = outer->fCoinPtTStart->debugContains(innerCoin);
1319                const SkOpPtT* testE = outer->fCoinPtTEnd->debugContains(innerCoin);
1320                if (testS && testS->fT >= inner->fCoinPtTStart->fT
1321                        && testE && testE->fT <= inner->fCoinPtTEnd->fT
1322                        && this->testForCoincidence(outer, testS, testE)) {
1323                    if (this->debugAddIfMissing(outer, testS, testE)) {
1324                        log->record(kAddMissingCoin_Glitch, id, outer, testS, testE);
1325                    }
1326                } else {
1327                    testS = inner->fCoinPtTStart->debugContains(outerCoin);
1328                    testE = inner->fCoinPtTEnd->debugContains(outerCoin);
1329                    if (testS && testS->fT >= outer->fCoinPtTStart->fT
1330                            && testE && testE->fT <= outer->fCoinPtTEnd->fT
1331                            && this->testForCoincidence(inner, testS, testE)) {
1332                        if (this->debugAddIfMissing(inner, testS, testE)) {
1333                            log->record(kAddMissingCoin_Glitch, id, inner, testS, testE);
1334                        }
1335                    }
1336                }
1337            }
1338        }
1339    } while ((outer = outer->fNext));
1340}
1341
1342bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1343    const SkCoincidentSpans* coin = fHead;
1344    if (!coin) {
1345        return false;
1346    }
1347    bool expanded = false;
1348    do {
1349        const SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
1350        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1351        const SkOpSegment* segment = coin->fCoinPtTStart->segment();
1352        const SkOpSegment* oppSegment = coin->fOppPtTStart->segment();
1353        const SkOpSpan* prev = start->prev();
1354        if (prev && prev->debugContains(oppSegment)) {
1355            double midT = (prev->t() + start->t()) / 2;
1356            if (segment->isClose(midT, oppSegment)) {
1357                log->record(kExpandCoin_Glitch, id, coin, prev);
1358            }
1359        }
1360        SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
1361        if (next && next->debugContains(oppSegment)) {
1362            double midT = (end->t() + next->t()) / 2;
1363            if (segment->isClose(midT, oppSegment)) {
1364                log->record(kExpandCoin_Glitch, id, coin, next);
1365            }
1366        }
1367    } while ((coin = coin->fNext));
1368    return expanded;
1369}
1370
1371void SkOpCoincidence::debugFixAligned(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1372    const SkCoincidentSpans* coin = fHead;
1373    if (!coin) {
1374        return;
1375    }
1376    do {
1377        if (coin->fCoinPtTStart->deleted()) {
1378            log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTStart);
1379        }
1380        if (coin->fCoinPtTEnd->deleted()) {
1381            log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTEnd);
1382        }
1383        if (coin->fOppPtTStart->deleted()) {
1384            log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTStart);
1385        }
1386        if (coin->fOppPtTEnd->deleted()) {
1387            log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTEnd);
1388        }
1389    } while ((coin = coin->fNext));
1390    coin = fHead;
1391    do {
1392        if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)) {
1393            log->record(kCollapsedCoin_Glitch, id, coin, coin->fCoinPtTStart);
1394        }
1395        if (coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
1396            log->record(kCollapsedCoin_Glitch, id, coin, coin->fOppPtTStart);
1397        }
1398    } while ((coin = coin->fNext));
1399}
1400
1401void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1402    const SkCoincidentSpans* coin = fHead;
1403    if (!coin) {
1404        return;
1405    }
1406    do {
1407        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1408        const SkOpSpanBase* oldEnd = end;
1409        const SkOpSpan* start = coin->fCoinPtTStart->span()->debugStarter(&end);
1410        const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
1411        const SkOpSpanBase* oOldEnd = oEnd;
1412        const SkOpSpanBase* oStart = coin->fOppPtTStart->span()->debugStarter(&oEnd);
1413        bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
1414        if (flipped) {
1415            SkTSwap(oStart, oEnd);
1416        }
1417        const SkOpSpanBase* next = start;
1418        const SkOpSpanBase* oNext = oStart;
1419        do {
1420            next = next->upCast()->next();
1421            oNext = flipped ? oNext->prev() : oNext->upCast()->next();
1422            if (next == end || oNext == oEnd) {
1423                break;
1424            }
1425            if (!next->containsCoinEnd(oNext)) {
1426                log->record(kMarkCoinEnd_Glitch, id, next, oNext);
1427            }
1428            const SkOpSpan* nextSpan = next->upCast();
1429            const SkOpSpan* oNextSpan = oNext->upCast();
1430            if (!nextSpan->containsCoincidence(oNextSpan)) {
1431                log->record(kMarkCoinInsert_Glitch, id, nextSpan, oNextSpan);
1432            }
1433        } while (true);
1434    } while ((coin = coin->fNext));
1435}
1436#endif
1437
1438void SkOpCoincidence::debugShowCoincidence() const {
1439    SkCoincidentSpans* span = fHead;
1440    while (span) {
1441        SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1442                span->fCoinPtTStart->segment()->debugID(),
1443                span->fCoinPtTStart->fT, span->fCoinPtTEnd->fT);
1444        SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1445                span->fOppPtTStart->segment()->debugID(),
1446                span->fOppPtTStart->fT, span->fOppPtTEnd->fT);
1447        span = span->fNext;
1448    }
1449}
1450
1451#if DEBUG_COINCIDENCE
1452void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1453    const SkOpSegment* segment = &fHead;
1454    do {
1455        segment->debugCheckHealth(id, log);
1456    } while ((segment = segment->next()));
1457}
1458
1459void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
1460        const SkOpCoincidence* coincidence) const {
1461    const SkOpSegment* segment = &fHead;
1462    do {
1463        segment->debugMissingCoincidence(id, log, coincidence);
1464    } while ((segment = segment->next()));
1465}
1466#endif
1467
1468void SkOpSegment::debugValidate() const {
1469#if DEBUG_VALIDATE
1470    const SkOpSpanBase* span = &fHead;
1471    double lastT = -1;
1472    const SkOpSpanBase* prev = nullptr;
1473    int count = 0;
1474    int done = 0;
1475    do {
1476        if (!span->final()) {
1477            ++count;
1478            done += span->upCast()->done() ? 1 : 0;
1479        }
1480        SkASSERT(span->segment() == this);
1481        SkASSERT(!prev || prev->upCast()->next() == span);
1482        SkASSERT(!prev || prev == span->prev());
1483        prev = span;
1484        double t = span->ptT()->fT;
1485        SkASSERT(lastT < t);
1486        lastT = t;
1487        span->debugValidate();
1488    } while (!span->final() && (span = span->upCast()->next()));
1489    SkASSERT(count == fCount);
1490    SkASSERT(done == fDoneCount);
1491    SkASSERT(count >= fDoneCount);
1492    SkASSERT(span->final());
1493    span->debugValidate();
1494#endif
1495}
1496
1497bool SkOpSpanBase::debugAlignedEnd(double t, const SkPoint& pt) const {
1498    SkASSERT(zero_or_one(t));
1499    const SkOpSegment* segment = this->segment();
1500    SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt);
1501    if (!debugAlignedInner()) {
1502          return false;
1503    }
1504    if ((t ? segment->lastPt() : segment->pts()[0]) != pt) {
1505        return false;
1506    }
1507    const SkOpPtT* ptT = &this->fPtT;
1508    SkASSERT(t == ptT->fT);
1509    SkASSERT(pt == ptT->fPt);
1510    const SkOpPtT* test = ptT, * stopPtT = ptT;
1511    while ((test = test->next()) != stopPtT) {
1512        const SkOpSegment* other = test->segment();
1513        if (other == this->segment()) {
1514            continue;
1515        }
1516        if (!zero_or_one(test->fT)) {
1517            continue;
1518        }
1519        if ((test->fT ? other->lastPt() : other->pts()[0]) != pt) {
1520            return false;
1521        }
1522    }
1523    return this->fAligned;
1524}
1525
1526bool SkOpSpanBase::debugAlignedInner() const {
1527    // force the spans to share points and t values
1528    const SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
1529    const SkPoint& pt = ptT->fPt;
1530    do {
1531        if (ptT->fPt != pt) {
1532            return false;
1533        }
1534        const SkOpSpanBase* span = ptT->span();
1535        const SkOpPtT* test = ptT;
1536        do {
1537            if ((test = test->next()) == stopPtT) {
1538                break;
1539            }
1540            if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) {
1541                return false;
1542            }
1543        } while (true);
1544    } while ((ptT = ptT->next()) != stopPtT);
1545    return true;
1546}
1547
1548bool SkOpSpanBase::debugCoinEndLoopCheck() const {
1549    int loop = 0;
1550    const SkOpSpanBase* next = this;
1551    SkOpSpanBase* nextCoin;
1552    do {
1553        nextCoin = next->fCoinEnd;
1554        SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
1555        for (int check = 1; check < loop - 1; ++check) {
1556            const SkOpSpanBase* checkCoin = this->fCoinEnd;
1557            const SkOpSpanBase* innerCoin = checkCoin;
1558            for (int inner = check + 1; inner < loop; ++inner) {
1559                innerCoin = innerCoin->fCoinEnd;
1560                if (checkCoin == innerCoin) {
1561                    SkDebugf("*** bad coincident end loop ***\n");
1562                    return false;
1563                }
1564            }
1565        }
1566        ++loop;
1567    } while ((next = nextCoin) && next != this);
1568    return true;
1569}
1570
1571bool SkOpSpanBase::debugContains(const SkOpSegment* segment) const {
1572    const SkOpPtT* start = &fPtT;
1573    const SkOpPtT* walk = start;
1574    while ((walk = walk->next()) != start) {
1575        if (walk->segment() == segment) {
1576            return true;
1577        }
1578    }
1579    return false;
1580}
1581
1582const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
1583    const SkOpSpanBase* end = *endPtr;
1584    SkASSERT(this->segment() == end->segment());
1585    const SkOpSpanBase* result;
1586    if (t() < end->t()) {
1587        result = this;
1588    } else {
1589        result = end;
1590        *endPtr = this;
1591    }
1592    return result->upCast();
1593}
1594
1595void SkOpSpanBase::debugValidate() const {
1596#if DEBUG_VALIDATE
1597    const SkOpPtT* ptT = &fPtT;
1598    SkASSERT(ptT->span() == this);
1599    do {
1600//        SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
1601        ptT->debugValidate();
1602        ptT = ptT->next();
1603    } while (ptT != &fPtT);
1604    SkASSERT(this->debugCoinEndLoopCheck());
1605    if (!this->final()) {
1606        SkASSERT(this->upCast()->debugCoinLoopCheck());
1607    }
1608    if (fFromAngle) {
1609        fFromAngle->debugValidate();
1610    }
1611    if (!this->final() && this->upCast()->toAngle()) {
1612        this->upCast()->toAngle()->debugValidate();
1613    }
1614#endif
1615}
1616
1617bool SkOpSpan::debugCoinLoopCheck() const {
1618    int loop = 0;
1619    const SkOpSpan* next = this;
1620    SkOpSpan* nextCoin;
1621    do {
1622        nextCoin = next->fCoincident;
1623        SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
1624        for (int check = 1; check < loop - 1; ++check) {
1625            const SkOpSpan* checkCoin = this->fCoincident;
1626            const SkOpSpan* innerCoin = checkCoin;
1627            for (int inner = check + 1; inner < loop; ++inner) {
1628                innerCoin = innerCoin->fCoincident;
1629                if (checkCoin == innerCoin) {
1630                    SkDebugf("*** bad coincident loop ***\n");
1631                    return false;
1632                }
1633            }
1634        }
1635        ++loop;
1636    } while ((next = nextCoin) && next != this);
1637    return true;
1638}
1639
1640// called only by test code
1641int SkIntersections::debugCoincidentUsed() const {
1642    if (!fIsCoincident[0]) {
1643        SkASSERT(!fIsCoincident[1]);
1644        return 0;
1645    }
1646    int count = 0;
1647    SkDEBUGCODE(int count2 = 0;)
1648    for (int index = 0; index < fUsed; ++index) {
1649        if (fIsCoincident[0] & (1 << index)) {
1650            ++count;
1651        }
1652#ifdef SK_DEBUG
1653        if (fIsCoincident[1] & (1 << index)) {
1654            ++count2;
1655        }
1656#endif
1657    }
1658    SkASSERT(count == count2);
1659    return count;
1660}
1661
1662#include "SkOpContour.h"
1663
1664bool SkOpPtT::debugContains(const SkOpPtT* check) const {
1665    SkASSERT(this != check);
1666    const SkOpPtT* ptT = this;
1667    int links = 0;
1668    do {
1669        ptT = ptT->next();
1670        if (ptT == check) {
1671            return true;
1672        }
1673        ++links;
1674        const SkOpPtT* test = this;
1675        for (int index = 0; index < links; ++index) {
1676            if (ptT == test) {
1677                return false;
1678            }
1679            test = test->next();
1680        }
1681    } while (true);
1682}
1683
1684const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
1685    SkASSERT(this->segment() != check);
1686    const SkOpPtT* ptT = this;
1687    int links = 0;
1688    do {
1689        ptT = ptT->next();
1690        if (ptT->segment() == check) {
1691            return ptT;
1692        }
1693        ++links;
1694        const SkOpPtT* test = this;
1695        for (int index = 0; index < links; ++index) {
1696            if (ptT == test) {
1697                return nullptr;
1698            }
1699            test = test->next();
1700        }
1701    } while (true);
1702}
1703
1704int SkOpPtT::debugLoopLimit(bool report) const {
1705    int loop = 0;
1706    const SkOpPtT* next = this;
1707    do {
1708        for (int check = 1; check < loop - 1; ++check) {
1709            const SkOpPtT* checkPtT = this->fNext;
1710            const SkOpPtT* innerPtT = checkPtT;
1711            for (int inner = check + 1; inner < loop; ++inner) {
1712                innerPtT = innerPtT->fNext;
1713                if (checkPtT == innerPtT) {
1714                    if (report) {
1715                        SkDebugf("*** bad ptT loop ***\n");
1716                    }
1717                    return loop;
1718                }
1719            }
1720        }
1721        // there's nothing wrong with extremely large loop counts -- but this may appear to hang
1722        // by taking a very long time to figure out that no loop entry is a duplicate
1723        // -- and it's likely that a large loop count is indicative of a bug somewhere
1724        if (++loop > 1000) {
1725            SkDebugf("*** loop count exceeds 1000 ***\n");
1726            return 1000;
1727        }
1728    } while ((next = next->fNext) && next != this);
1729    return 0;
1730}
1731
1732void SkOpPtT::debugValidate() const {
1733#if DEBUG_VALIDATE
1734    SkOpGlobalState::Phase phase = contour()->globalState()->phase();
1735    if (phase == SkOpGlobalState::kIntersecting
1736            || phase == SkOpGlobalState::kFixWinding) {
1737        return;
1738    }
1739    SkASSERT(fNext);
1740    SkASSERT(fNext != this);
1741    SkASSERT(fNext->fNext);
1742    SkASSERT(debugLoopLimit(false) == 0);
1743#endif
1744}
1745
1746static void output_scalar(SkScalar num) {
1747    if (num == (int) num) {
1748        SkDebugf("%d", (int) num);
1749    } else {
1750        SkString str;
1751        str.printf("%1.9g", num);
1752        int width = (int) str.size();
1753        const char* cStr = str.c_str();
1754        while (cStr[width - 1] == '0') {
1755            --width;
1756        }
1757        str.resize(width);
1758        SkDebugf("%sf", str.c_str());
1759    }
1760}
1761
1762static void output_points(const SkPoint* pts, int count) {
1763    for (int index = 0; index < count; ++index) {
1764        output_scalar(pts[index].fX);
1765        SkDebugf(", ");
1766        output_scalar(pts[index].fY);
1767        if (index + 1 < count) {
1768            SkDebugf(", ");
1769        }
1770    }
1771}
1772
1773static void showPathContours(SkPath::RawIter& iter, const char* pathName) {
1774    uint8_t verb;
1775    SkPoint pts[4];
1776    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1777        switch (verb) {
1778            case SkPath::kMove_Verb:
1779                SkDebugf("    %s.moveTo(", pathName);
1780                output_points(&pts[0], 1);
1781                SkDebugf(");\n");
1782                continue;
1783            case SkPath::kLine_Verb:
1784                SkDebugf("    %s.lineTo(", pathName);
1785                output_points(&pts[1], 1);
1786                SkDebugf(");\n");
1787                break;
1788            case SkPath::kQuad_Verb:
1789                SkDebugf("    %s.quadTo(", pathName);
1790                output_points(&pts[1], 2);
1791                SkDebugf(");\n");
1792                break;
1793            case SkPath::kConic_Verb:
1794                SkDebugf("    %s.conicTo(", pathName);
1795                output_points(&pts[1], 2);
1796                SkDebugf(", %1.9gf);\n", iter.conicWeight());
1797                break;
1798            case SkPath::kCubic_Verb:
1799                SkDebugf("    %s.cubicTo(", pathName);
1800                output_points(&pts[1], 3);
1801                SkDebugf(");\n");
1802                break;
1803            case SkPath::kClose_Verb:
1804                SkDebugf("    %s.close();\n", pathName);
1805                break;
1806            default:
1807                SkDEBUGFAIL("bad verb");
1808                return;
1809        }
1810    }
1811}
1812
1813static const char* gFillTypeStr[] = {
1814    "kWinding_FillType",
1815    "kEvenOdd_FillType",
1816    "kInverseWinding_FillType",
1817    "kInverseEvenOdd_FillType"
1818};
1819
1820void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
1821    SkPath::RawIter iter(path);
1822#define SUPPORT_RECT_CONTOUR_DETECTION 0
1823#if SUPPORT_RECT_CONTOUR_DETECTION
1824    int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0;
1825    if (rectCount > 0) {
1826        SkTDArray<SkRect> rects;
1827        SkTDArray<SkPath::Direction> directions;
1828        rects.setCount(rectCount);
1829        directions.setCount(rectCount);
1830        path.rectContours(rects.begin(), directions.begin());
1831        for (int contour = 0; contour < rectCount; ++contour) {
1832            const SkRect& rect = rects[contour];
1833            SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
1834                    rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
1835                    ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
1836        }
1837        return;
1838    }
1839#endif
1840    SkPath::FillType fillType = path.getFillType();
1841    SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
1842    if (includeDeclaration) {
1843        SkDebugf("    SkPath %s;\n", name);
1844    }
1845    SkDebugf("    %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
1846    iter.setPath(path);
1847    showPathContours(iter, name);
1848}
1849