SkPathOpsDebug.cpp revision ed0935a28a29af7d3b16ac8d9365f291a335c6bd 
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
407void SkDRect::debugInit() {
408    fLeft = fTop = fRight = fBottom = SK_ScalarNaN;
409}
410
411#include "SkOpAngle.h"
412#include "SkOpSegment.h"
413
414#if DEBUG_COINCIDENCE
415void SkOpSegment::debugAddAlignIntersection(const char* id, SkPathOpsDebug::GlitchLog* log,
416        const SkOpPtT& endPtT, const SkPoint& oldPt,  const SkOpContourHead* contourList) const {
417    const SkPoint& newPt = endPtT.fPt;
418    if (newPt == oldPt) {
419        return;
420    }
421    SkPoint line[2] = { newPt, oldPt };
422    SkPathOpsBounds lineBounds;
423    lineBounds.setBounds(line, 2);
424    SkDLine aLine;
425    aLine.set(line);
426    const SkOpContour* current = contourList;
427    do {
428        if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) {
429            continue;
430        }
431        const SkOpSegment* segment = current->first();
432        do {
433            if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) {
434                continue;
435            }
436            if (newPt == segment->fPts[0]) {
437                continue;
438            }
439            if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
440                continue;
441            }
442            if (oldPt == segment->fPts[0]) {
443                continue;
444            }
445            if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
446                continue;
447            }
448            if (endPtT.debugContains(segment)) {
449                continue;
450            }
451            SkIntersections i;
452            switch (segment->fVerb) {
453                case SkPath::kLine_Verb: {
454                    SkDLine bLine;
455                    bLine.set(segment->fPts);
456                    i.intersect(bLine, aLine);
457                    } break;
458                case SkPath::kQuad_Verb: {
459                    SkDQuad bQuad;
460                    bQuad.set(segment->fPts);
461                    i.intersect(bQuad, aLine);
462                    } break;
463                case SkPath::kConic_Verb: {
464                    SkDConic bConic;
465                    bConic.set(segment->fPts, segment->fWeight);
466                    i.intersect(bConic, aLine);
467                    } break;
468                case SkPath::kCubic_Verb: {
469                    SkDCubic bCubic;
470                    bCubic.set(segment->fPts);
471                    i.intersect(bCubic, aLine);
472                    } break;
473                default:
474                    SkASSERT(0);
475            }
476            if (i.used()) {
477                SkASSERT(i.used() == 1);
478                SkASSERT(!zero_or_one(i[0][0]));
479                SkOpSpanBase* checkSpan = fHead.next();
480                while (!checkSpan->final()) {
481                    if (checkSpan->contains(segment)) {
482                        goto nextSegment;
483                    }
484                    checkSpan = checkSpan->upCast()->next();
485                }
486                log->record(kMissingIntersection_Glitch, id, checkSpan, segment, i[0][0], newPt);
487            }
488    nextSegment:
489            ;
490        } while ((segment = segment->next()));
491    } while ((current = current->next()));
492}
493
494bool SkOpSegment::debugAddMissing(double t, const SkOpSegment* opp) const {
495    const SkOpSpanBase* existing = nullptr;
496    const SkOpSpanBase* test = &fHead;
497    double testT;
498    do {
499        if ((testT = test->ptT()->fT) >= t) {
500            if (testT == t) {
501                existing = test;
502            }
503            break;
504        }
505    } while ((test = test->upCast()->next()));
506    return !existing || !existing->debugContains(opp);
507}
508
509void SkOpSegment::debugAlign(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
510    const SkOpSpanBase* span = &fHead;
511    if (!span->aligned()) {
512        if (!span->debugAlignedEnd(0, fPts[0])) {
513            glitches->record(kUnalignedHead_Glitch, id, span);
514        }
515    }
516    while ((span = span->upCast()->next())) {
517        if (span == &fTail) {
518            break;
519        }
520        if (!span->aligned()) {
521            glitches->record(kUnaligned_Glitch, id, span);
522        }
523    }
524    if (!span->aligned()) {
525        span->debugAlignedEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]);
526    }
527    if (this->collapsed()) {
528        const SkOpSpan* span = &fHead;
529        do {
530            if (span->windValue()) {
531                glitches->record(kCollapsedWindValue_Glitch, id, span);
532            }
533            if (span->oppValue()) {
534                glitches->record(kCollapsedOppValue_Glitch, id, span);
535            }
536            if (!span->done()) {
537                glitches->record(kCollapsedDone_Glitch, id, span);
538            }
539        } while ((span = span->next()->upCastable()));
540    }
541}
542#endif
543
544#if DEBUG_ANGLE
545void SkOpSegment::debugCheckAngleCoin() const {
546    const SkOpSpanBase* base = &fHead;
547    const SkOpSpan* span;
548    do {
549        const SkOpAngle* angle = base->fromAngle();
550        if (angle && angle->fCheckCoincidence) {
551            angle->debugCheckNearCoincidence();
552        }
553        if (base->final()) {
554             break;
555        }
556        span = base->upCast();
557        angle = span->toAngle();
558        if (angle && angle->fCheckCoincidence) {
559            angle->debugCheckNearCoincidence();
560        }
561    } while ((base = span->next()));
562}
563#endif
564
565#if DEBUG_COINCIDENCE
566// this mimics the order of the checks in handle coincidence
567void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
568    debugMoveMultiples(id, glitches);
569    debugFindCollapsed(id, glitches);
570    debugMoveNearby(id, glitches);
571    debugAlign(id, glitches);
572    debugAddAlignIntersections(id, glitches, this->globalState()->contourHead());
573
574}
575
576void SkOpSegment::debugFindCollapsed(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
577    if (fHead.contains(&fTail)) {
578        const SkOpSpan* span = this->head();
579        bool missingDone = false;
580        do {
581            missingDone |= !span->done();
582        } while ((span = span->next()->upCastable()));
583        if (missingDone) {
584            glitches->record(kMissingDone_Glitch, id, &fHead);
585        }
586        if (!fHead.debugAlignedEnd(0, fHead.pt())) {
587            glitches->record(kUnalignedHead_Glitch, id, &fHead);
588        }
589        if (!fTail.aligned()) {
590            glitches->record(kUnalignedTail_Glitch, id, &fTail);
591        }
592    }
593}
594#endif
595
596SkOpAngle* SkOpSegment::debugLastAngle() {
597    SkOpAngle* result = nullptr;
598    SkOpSpan* span = this->head();
599    do {
600        if (span->toAngle()) {
601            SkASSERT(!result);
602            result = span->toAngle();
603        }
604    } while ((span = span->next()->upCastable()));
605    SkASSERT(result);
606    return result;
607}
608
609#if DEBUG_COINCIDENCE
610void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
611        const SkOpCoincidence* coincidences) const {
612    if (this->verb() != SkPath::kLine_Verb) {
613        return;
614    }
615    if (this->done()) {
616        return;
617    }
618    const SkOpSpan* prior = nullptr;
619    const SkOpSpanBase* spanBase = &fHead;
620    do {
621        const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
622        SkASSERT(ptT->span() == spanBase);
623        while ((ptT = ptT->next()) != spanStopPtT) {
624            if (ptT->deleted()) {
625                continue;
626            }
627            SkOpSegment* opp = ptT->span()->segment();
628//            if (opp->verb() == SkPath::kLine_Verb) {
629//                continue;
630//            }
631            if (opp->done()) {
632                continue;
633            }
634            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
635            if (!opp->visited()) {
636                continue;
637            }
638            if (spanBase == &fHead) {
639                continue;
640            }
641            const SkOpSpan* span = spanBase->upCastable();
642            // FIXME?: this assumes that if the opposite segment is coincident then no more
643            // coincidence needs to be detected. This may not be true.
644            if (span && span->segment() != opp && span->containsCoincidence(opp)) {
645                continue;
646            }
647            if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) {
648                continue;
649            }
650            const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
651            // find prior span containing opp segment
652            const SkOpSegment* priorOpp = nullptr;
653            const SkOpSpan* priorTest = spanBase->prev();
654            while (!priorOpp && priorTest) {
655                priorStopPtT = priorPtT = priorTest->ptT();
656                while ((priorPtT = priorPtT->next()) != priorStopPtT) {
657                    if (priorPtT->deleted()) {
658                        continue;
659                    }
660                    SkOpSegment* segment = priorPtT->span()->segment();
661                    if (segment == opp) {
662                        prior = priorTest;
663                        priorOpp = opp;
664                        break;
665                    }
666                }
667                priorTest = priorTest->prev();
668            }
669            if (!priorOpp) {
670                continue;
671            }
672            const SkOpPtT* oppStart = prior->ptT();
673            const SkOpPtT* oppEnd = spanBase->ptT();
674            bool swapped = priorPtT->fT > ptT->fT;
675            if (swapped) {
676                SkTSwap(priorPtT, ptT);
677                SkTSwap(oppStart, oppEnd);
678            }
679            bool flipped = oppStart->fT > oppEnd->fT;
680            bool coincident = false;
681            if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
682                goto swapBack;
683            }
684            if (opp->verb() == SkPath::kLine_Verb) {
685                coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) ||
686                        SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) &&
687                        (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) ||
688                        SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt));
689            }
690            if (!coincident) {
691                coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000);
692            }
693            if (coincident) {
694                log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd);
695            }
696    swapBack:
697            if (swapped) {
698                SkTSwap(priorPtT, ptT);
699            }
700        }
701    } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
702}
703
704void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
705    const SkOpSpanBase* test = &fHead;
706    do {
707        int addCount = test->spanAddsCount();
708        SkASSERT(addCount >= 1);
709        if (addCount == 1) {
710            continue;
711        }
712        const SkOpPtT* startPtT = test->ptT();
713        const SkOpPtT* testPtT = startPtT;
714        do {  // iterate through all spans associated with start
715            const SkOpSpanBase* oppSpan = testPtT->span();
716            if (oppSpan->spanAddsCount() == addCount) {
717                continue;
718            }
719            if (oppSpan->deleted()) {
720                continue;
721            }
722            const SkOpSegment* oppSegment = oppSpan->segment();
723            if (oppSegment == this) {
724                continue;
725            }
726            // find range of spans to consider merging
727            const SkOpSpanBase* oppPrev = oppSpan;
728            const SkOpSpanBase* oppFirst = oppSpan;
729            while ((oppPrev = oppPrev->prev())) {
730                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
731                    break;
732                }
733                if (oppPrev->spanAddsCount() == addCount) {
734                    continue;
735                }
736                if (oppPrev->deleted()) {
737                    continue;
738                }
739                oppFirst = oppPrev;
740            }
741            const SkOpSpanBase* oppNext = oppSpan;
742            const SkOpSpanBase* oppLast = oppSpan;
743            while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
744                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
745                    break;
746                }
747                if (oppNext->spanAddsCount() == addCount) {
748                    continue;
749                }
750                if (oppNext->deleted()) {
751                    continue;
752                }
753                oppLast = oppNext;
754            }
755            if (oppFirst == oppLast) {
756                continue;
757            }
758            const SkOpSpanBase* oppTest = oppFirst;
759            do {
760                if (oppTest == oppSpan) {
761                    continue;
762                }
763                // check to see if the candidate meets specific criteria:
764                // it contains spans of segments in test's loop but not including 'this'
765                const SkOpPtT* oppStartPtT = oppTest->ptT();
766                const SkOpPtT* oppPtT = oppStartPtT;
767                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
768                    const SkOpSegment* oppPtTSegment = oppPtT->segment();
769                    if (oppPtTSegment == this) {
770                        goto tryNextSpan;
771                    }
772                    const SkOpPtT* matchPtT = startPtT;
773                    do {
774                        if (matchPtT->segment() == oppPtTSegment) {
775                            goto foundMatch;
776                        }
777                    } while ((matchPtT = matchPtT->next()) != startPtT);
778                    goto tryNextSpan;
779            foundMatch:  // merge oppTest and oppSpan
780                    if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) {
781                        SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse
782                        SkASSERT(oppSpan != &oppSegment->fTail);
783                        glitches->record(kMoveMultiple_Glitch, id, oppTest, oppSpan);
784                    } else {
785                        glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest);
786                    }
787                    goto checkNextSpan;
788                }
789        tryNextSpan:
790                ;
791            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
792        } while ((testPtT = testPtT->next()) != startPtT);
793checkNextSpan:
794        ;
795    } while ((test = test->final() ? nullptr : test->upCast()->next()));
796}
797
798void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
799        const SkOpSpanBase* spanS = &fHead;
800    do {
801        const SkOpSpanBase* test = spanS->upCast()->next();
802        const SkOpSpanBase* next;
803        if (spanS->contains(test)) {
804            if (!test->final()) {
805                glitches->record(kUndetachedSpan_Glitch, id, test, spanS);
806            } else if (spanS != &fHead) {
807                glitches->record(kUndetachedSpan_Glitch, id, spanS, test);
808            }
809        }
810        do {  // iterate through all spans associated with start
811            const SkOpPtT* startBase = spanS->ptT();
812            next = test->final() ? nullptr : test->upCast()->next();
813            do {
814                const SkOpPtT* testBase = test->ptT();
815                do {
816                    if (startBase == testBase) {
817                        goto checkNextSpan;
818                    }
819                    if (testBase->duplicate()) {
820                        continue;
821                    }
822                    if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) {
823                        if (test == &this->fTail) {
824                            if (spanS == &fHead) {
825                                glitches->record(kCollapsedSpan_Glitch, id, spanS);
826                            } else {
827                                glitches->record(kUnmergedSpan_Glitch, id, &this->fTail, spanS);
828                            }
829                        } else {
830                            glitches->record(kUnmergedSpan_Glitch, id, spanS, test);
831                            goto checkNextSpan;
832                        }
833                    }
834                } while ((testBase = testBase->next()) != test->ptT());
835            } while ((startBase = startBase->next()) != spanS->ptT());
836    checkNextSpan:
837            ;
838        } while ((test = next));
839        spanS = spanS->upCast()->next();
840    } while (!spanS->final());
841}
842#endif
843
844void SkOpSegment::debugReset() {
845    this->init(this->fPts, this->fWeight, this->contour(), this->verb());
846}
847
848#if DEBUG_ACTIVE_SPANS
849void SkOpSegment::debugShowActiveSpans() const {
850    debugValidate();
851    if (done()) {
852        return;
853    }
854    int lastId = -1;
855    double lastT = -1;
856    const SkOpSpan* span = &fHead;
857    do {
858        if (span->done()) {
859            continue;
860        }
861        if (lastId == this->debugID() && lastT == span->t()) {
862            continue;
863        }
864        lastId = this->debugID();
865        lastT = span->t();
866        SkDebugf("%s id=%d", __FUNCTION__, this->debugID());
867        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
868        for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
869            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
870        }
871        if (SkPath::kConic_Verb == fVerb) {
872            SkDebugf(" %1.9gf", fWeight);
873        }
874        const SkOpPtT* ptT = span->ptT();
875        SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY);
876        SkDebugf(" tEnd=%1.9g", span->next()->t());
877        if (span->windSum() == SK_MinS32) {
878            SkDebugf(" windSum=?");
879        } else {
880            SkDebugf(" windSum=%d", span->windSum());
881        }
882        if (span->oppValue() && span->oppSum() == SK_MinS32) {
883            SkDebugf(" oppSum=?");
884        } else if (span->oppValue() || span->oppSum() != SK_MinS32) {
885            SkDebugf(" oppSum=%d", span->oppSum());
886        }
887        SkDebugf(" windValue=%d", span->windValue());
888        if (span->oppValue() || span->oppSum() != SK_MinS32) {
889            SkDebugf(" oppValue=%d", span->oppValue());
890        }
891        SkDebugf("\n");
892   } while ((span = span->next()->upCastable()));
893}
894#endif
895
896#if DEBUG_MARK_DONE
897void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
898    const SkPoint& pt = span->ptT()->fPt;
899    SkDebugf("%s id=%d", fun, this->debugID());
900    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
901    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
902        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
903    }
904    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
905            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
906    if (winding == SK_MinS32) {
907        SkDebugf("?");
908    } else {
909        SkDebugf("%d", winding);
910    }
911    SkDebugf(" windSum=");
912    if (span->windSum() == SK_MinS32) {
913        SkDebugf("?");
914    } else {
915        SkDebugf("%d", span->windSum());
916    }
917    SkDebugf(" windValue=%d\n", span->windValue());
918}
919
920void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
921                                      int oppWinding) {
922    const SkPoint& pt = span->ptT()->fPt;
923    SkDebugf("%s id=%d", fun, this->debugID());
924    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
925    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
926        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
927    }
928    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
929            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding);
930    if (winding == SK_MinS32) {
931        SkDebugf("?");
932    } else {
933        SkDebugf("%d", winding);
934    }
935    SkDebugf(" newOppSum=");
936    if (oppWinding == SK_MinS32) {
937        SkDebugf("?");
938    } else {
939        SkDebugf("%d", oppWinding);
940    }
941    SkDebugf(" oppSum=");
942    if (span->oppSum() == SK_MinS32) {
943        SkDebugf("?");
944    } else {
945        SkDebugf("%d", span->oppSum());
946    }
947    SkDebugf(" windSum=");
948    if (span->windSum() == SK_MinS32) {
949        SkDebugf("?");
950    } else {
951        SkDebugf("%d", span->windSum());
952    }
953    SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
954}
955
956#endif
957
958// loop looking for a pair of angle parts that are too close to be sorted
959/* This is called after other more simple intersection and angle sorting tests have been exhausted.
960   This should be rarely called -- the test below is thorough and time consuming.
961   This checks the distance between start points; the distance between
962*/
963#if DEBUG_ANGLE
964void SkOpAngle::debugCheckNearCoincidence() const {
965    const SkOpAngle* test = this;
966    do {
967        const SkOpSegment* testSegment = test->segment();
968        double testStartT = test->start()->t();
969        SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
970        double testEndT = test->end()->t();
971        SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
972        double testLenSq = testStartPt.distanceSquared(testEndPt);
973        SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
974        double testMidT = (testStartT + testEndT) / 2;
975        const SkOpAngle* next = test;
976        while ((next = next->fNext) != this) {
977            SkOpSegment* nextSegment = next->segment();
978            double testMidDistSq = testSegment->distSq(testMidT, next);
979            double testEndDistSq = testSegment->distSq(testEndT, next);
980            double nextStartT = next->start()->t();
981            SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
982            double distSq = testStartPt.distanceSquared(nextStartPt);
983            double nextEndT = next->end()->t();
984            double nextMidT = (nextStartT + nextEndT) / 2;
985            double nextMidDistSq = nextSegment->distSq(nextMidT, test);
986            double nextEndDistSq = nextSegment->distSq(nextEndT, test);
987            SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
988                    testSegment->debugID(), nextSegment->debugID());
989            SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
990            SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
991            SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
992            SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
993            SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
994            double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
995            SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
996            SkDebugf("\n");
997        }
998        test = test->fNext;
999    } while (test->fNext != this);
1000}
1001#endif
1002
1003#if DEBUG_ANGLE
1004SkString SkOpAngle::debugPart() const {
1005    SkString result;
1006    switch (this->segment()->verb()) {
1007        case SkPath::kLine_Verb:
1008            result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart),
1009                    this->segment()->debugID());
1010            break;
1011        case SkPath::kQuad_Verb:
1012            result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
1013                    this->segment()->debugID());
1014            break;
1015        case SkPath::kConic_Verb:
1016            result.printf(CONIC_DEBUG_STR " id=%d",
1017                    CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight),
1018                    this->segment()->debugID());
1019            break;
1020        case SkPath::kCubic_Verb:
1021            result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart),
1022                    this->segment()->debugID());
1023            break;
1024        default:
1025            SkASSERT(0);
1026    }
1027    return result;
1028}
1029#endif
1030
1031#if DEBUG_SORT
1032void SkOpAngle::debugLoop() const {
1033    const SkOpAngle* first = this;
1034    const SkOpAngle* next = this;
1035    do {
1036        next->dumpOne(true);
1037        SkDebugf("\n");
1038        next = next->fNext;
1039    } while (next && next != first);
1040    next = first;
1041    do {
1042        next->debugValidate();
1043        next = next->fNext;
1044    } while (next && next != first);
1045}
1046#endif
1047
1048void SkOpAngle::debugValidate() const {
1049#if DEBUG_VALIDATE
1050    const SkOpAngle* first = this;
1051    const SkOpAngle* next = this;
1052    int wind = 0;
1053    int opp = 0;
1054    int lastXor = -1;
1055    int lastOppXor = -1;
1056    do {
1057        if (next->unorderable()) {
1058            return;
1059        }
1060        const SkOpSpan* minSpan = next->start()->starter(next->end());
1061        if (minSpan->windValue() == SK_MinS32) {
1062            return;
1063        }
1064        bool op = next->segment()->operand();
1065        bool isXor = next->segment()->isXor();
1066        bool oppXor = next->segment()->oppXor();
1067        SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
1068        SkASSERT(!DEBUG_LIMIT_WIND_SUM
1069                || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
1070        bool useXor = op ? oppXor : isXor;
1071        SkASSERT(lastXor == -1 || lastXor == (int) useXor);
1072        lastXor = (int) useXor;
1073        wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue());
1074        if (useXor) {
1075            wind &= 1;
1076        }
1077        useXor = op ? isXor : oppXor;
1078        SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
1079        lastOppXor = (int) useXor;
1080        opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue());
1081        if (useXor) {
1082            opp &= 1;
1083        }
1084        next = next->fNext;
1085    } while (next && next != first);
1086    SkASSERT(wind == 0 || !FLAGS_runFail);
1087    SkASSERT(opp == 0 || !FLAGS_runFail);
1088#endif
1089}
1090
1091void SkOpAngle::debugValidateNext() const {
1092#if !FORCE_RELEASE
1093    const SkOpAngle* first = this;
1094    const SkOpAngle* next = first;
1095    SkTDArray<const SkOpAngle*>(angles);
1096    do {
1097//        SK_ALWAYSBREAK(next->fSegment->debugContains(next));
1098        angles.push(next);
1099        next = next->next();
1100        if (next == first) {
1101            break;
1102        }
1103        SK_ALWAYSBREAK(!angles.contains(next));
1104        if (!next) {
1105            return;
1106        }
1107    } while (true);
1108#endif
1109}
1110
1111
1112#if DEBUG_COINCIDENCE
1113void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1114    // for each coincident pair, match the spans
1115    // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
1116    const SkCoincidentSpans* coin = this->fHead;
1117    if (!coin) {
1118        coin = this->fTop;
1119    }
1120    if (!coin) {
1121        return;
1122    }
1123    do {
1124        const SkOpPtT* startPtT = coin->fCoinPtTStart;
1125        const SkOpPtT* oStartPtT = coin->fOppPtTStart;
1126        SkASSERT(startPtT->contains(oStartPtT));
1127        SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
1128        const SkOpSpanBase* start = startPtT->span();
1129        const SkOpSpanBase* oStart = oStartPtT->span();
1130        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1131        const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
1132        const SkOpSpanBase* test = start->upCast()->next();
1133        const SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
1134        while (test != end || oTest != oEnd) {
1135            bool bumpTest = true;
1136            bool bumpOTest = true;
1137            if (!test->ptT()->contains(oTest->ptT())) {
1138                // use t ranges to guess which one is missing
1139                double startRange = coin->fCoinPtTEnd->fT - startPtT->fT;
1140                double startPart = (test->t() - startPtT->fT) / startRange;
1141                double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT;
1142                double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
1143                if (startPart == oStartPart) {
1144                    // data is corrupt
1145                    log->record(kAddCorruptCoin_Glitch, id, start, oStart);
1146                    break;
1147                }
1148                if (startPart < oStartPart) {
1149                    double newT = oStartPtT->fT + oStartRange * startPart;
1150                    log->record(kAddExpandedCoin_Glitch, id, oStart, newT, test->pt());
1151                    bumpOTest = false;
1152                } else {
1153                    double newT = startPtT->fT + startRange * oStartPart;
1154                    log->record(kAddExpandedCoin_Glitch, id, start, newT, oTest->pt());
1155                    bumpTest = false;
1156                }
1157            }
1158            if (bumpTest && test != end) {
1159                test = test->upCast()->next();
1160            }
1161            if (bumpOTest && oTest != oEnd) {
1162                oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
1163            }
1164        }
1165    } while ((coin = coin->fNext));
1166}
1167
1168static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
1169        const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
1170    double denom = overE->fT - overS->fT;
1171    double start = 0 < denom ? tStart : tEnd;
1172    double end = 0 < denom ? tEnd : tStart;
1173    double sRatio = (start - overS->fT) / denom;
1174    double eRatio = (end - overS->fT) / denom;
1175    *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
1176    *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
1177}
1178
1179bool SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
1180            const SkOpPtT* over1e) const {
1181    const SkCoincidentSpans* check = this->fTop;
1182    while (check) {
1183        if (check->fCoinPtTStart->span() == over1s->span()
1184                && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) {
1185            SkASSERT(check->fCoinPtTEnd->span() == over1e->span()
1186                    || !fDebugState->debugRunFail());
1187            SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span()
1188                    || !fDebugState->debugRunFail());
1189            return false;
1190        }
1191        if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span()
1192                && check->fOppPtTStart->span() == over1s->span()) {
1193            SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span()
1194                    || !fDebugState->debugRunFail());
1195            SkASSERT(check->fOppPtTEnd->span() == over1e->span()
1196                    || !fDebugState->debugRunFail());
1197            return false;
1198        }
1199        check = check->fNext;
1200    }
1201    return true;
1202}
1203
1204bool SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
1205                      const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
1206        SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
1207        SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const {
1208    double coinTs, coinTe, oppTs, oppTe;
1209    t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
1210    t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
1211    const SkOpSegment* coinSeg = coinPtTStart->segment();
1212    const SkOpSegment* oppSeg = oppPtTStart->segment();
1213    SkASSERT(coinSeg != oppSeg);
1214    const SkCoincidentSpans* check = this->fTop;
1215    ;
1216    while (check) {
1217        const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment();
1218        const SkOpSegment* checkOppSeg;
1219        if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) {
1220            goto next;
1221        }
1222        checkOppSeg = check->fOppPtTStart->segment();
1223        if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) {
1224            goto next;
1225        }
1226        {
1227            int cTs = coinTs;
1228            int cTe = coinTe;
1229            int oTs = oppTs;
1230            int oTe = oppTe;
1231            if (checkCoinSeg != coinSeg) {
1232                SkASSERT(checkOppSeg != oppSeg);
1233                SkTSwap(cTs, oTs);
1234                SkTSwap(cTe, oTe);
1235            }
1236            int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT)
1237                           + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT)
1238                           + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT)
1239                           + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT);
1240    //        SkASSERT(tweenCount == 0 || tweenCount == 4);
1241            if (tweenCount) {
1242                return true;
1243            }
1244        }
1245next:
1246        check = check->fNext;
1247    }
1248    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
1249        SkTSwap(oppTs, oppTe);
1250    }
1251    if (coinTs > coinTe) {
1252        SkTSwap(coinTs, coinTe);
1253        SkTSwap(oppTs, oppTe);
1254    }
1255    bool cs = coinSeg->debugAddMissing(coinTs, oppSeg);
1256    bool ce = coinSeg->debugAddMissing(coinTe, oppSeg);
1257    if (cs == ce) {
1258        return false;
1259    }
1260    return true;
1261}
1262
1263void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1264    const SkCoincidentSpans* outer = fHead;
1265    if (!outer) {
1266        return;
1267    }
1268    do {
1269    // addifmissing can modify the list that this is walking
1270    // save head so that walker can iterate over old data unperturbed
1271    // addifmissing adds to head freely then add saved head in the end
1272        const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
1273        SkASSERT(outerCoin == outer->fCoinPtTEnd->segment());
1274        const SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
1275        SkASSERT(outerOpp == outer->fOppPtTEnd->segment());
1276        const SkCoincidentSpans* inner = outer;
1277        while ((inner = inner->fNext)) {
1278            double overS, overE;
1279            const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
1280            SkASSERT(innerCoin == inner->fCoinPtTEnd->segment());
1281            const SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
1282            SkASSERT(innerOpp == inner->fOppPtTEnd->segment());
1283            if (outerCoin == innerCoin
1284                    && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1285                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
1286                if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1287                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
1288                        outer->fOppPtTStart, outer->fOppPtTEnd,
1289                        inner->fOppPtTStart, inner->fOppPtTEnd)) {
1290                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart);
1291                }
1292            } else if (outerCoin == innerOpp
1293                    && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1294                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
1295                if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1296                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
1297                        outer->fOppPtTStart, outer->fOppPtTEnd,
1298                        inner->fCoinPtTStart, inner->fCoinPtTEnd)) {
1299                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart);
1300                }
1301            } else if (outerOpp == innerCoin
1302                    && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
1303                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
1304                if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
1305                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
1306                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
1307                        inner->fOppPtTStart, inner->fOppPtTEnd)) {
1308                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart);
1309                }
1310            } else if (outerOpp == innerOpp
1311                    && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
1312                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
1313                if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
1314                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
1315                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
1316                        inner->fCoinPtTStart, inner->fCoinPtTEnd)) {
1317                    log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart);
1318                }
1319            } else if (outerCoin != innerCoin) {
1320                // check to see if outer span overlaps the inner span
1321                    // look for inner segment in pt-t list
1322                    // if present, and if t values are in coincident range
1323                    // add two pairs of new coincidence
1324                const SkOpPtT* testS = outer->fCoinPtTStart->debugContains(innerCoin);
1325                const SkOpPtT* testE = outer->fCoinPtTEnd->debugContains(innerCoin);
1326                if (testS && testS->fT >= inner->fCoinPtTStart->fT
1327                        && testE && testE->fT <= inner->fCoinPtTEnd->fT
1328                        && this->testForCoincidence(outer, testS, testE)) {
1329                    if (this->debugAddIfMissing(outer, testS, testE)) {
1330                        log->record(kAddMissingCoin_Glitch, id, outer, testS, testE);
1331                    }
1332                } else {
1333                    testS = inner->fCoinPtTStart->debugContains(outerCoin);
1334                    testE = inner->fCoinPtTEnd->debugContains(outerCoin);
1335                    if (testS && testS->fT >= outer->fCoinPtTStart->fT
1336                            && testE && testE->fT <= outer->fCoinPtTEnd->fT
1337                            && this->testForCoincidence(inner, testS, testE)) {
1338                        if (this->debugAddIfMissing(inner, testS, testE)) {
1339                            log->record(kAddMissingCoin_Glitch, id, inner, testS, testE);
1340                        }
1341                    }
1342                }
1343            }
1344        }
1345    } while ((outer = outer->fNext));
1346}
1347
1348bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1349    const SkCoincidentSpans* coin = fHead;
1350    if (!coin) {
1351        return false;
1352    }
1353    bool expanded = false;
1354    do {
1355        const SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
1356        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1357        const SkOpSegment* segment = coin->fCoinPtTStart->segment();
1358        const SkOpSegment* oppSegment = coin->fOppPtTStart->segment();
1359        const SkOpSpan* prev = start->prev();
1360        if (prev && prev->debugContains(oppSegment)) {
1361            double midT = (prev->t() + start->t()) / 2;
1362            if (segment->isClose(midT, oppSegment)) {
1363                log->record(kExpandCoin_Glitch, id, coin, prev);
1364            }
1365        }
1366        SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
1367        if (next && next->debugContains(oppSegment)) {
1368            double midT = (end->t() + next->t()) / 2;
1369            if (segment->isClose(midT, oppSegment)) {
1370                log->record(kExpandCoin_Glitch, id, coin, next);
1371            }
1372        }
1373    } while ((coin = coin->fNext));
1374    return expanded;
1375}
1376
1377void SkOpCoincidence::debugFixAligned(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1378    const SkCoincidentSpans* coin = fHead;
1379    if (!coin) {
1380        return;
1381    }
1382    do {
1383        if (coin->fCoinPtTStart->deleted()) {
1384            log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTStart);
1385        }
1386        if (coin->fCoinPtTEnd->deleted()) {
1387            log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTEnd);
1388        }
1389        if (coin->fOppPtTStart->deleted()) {
1390            log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTStart);
1391        }
1392        if (coin->fOppPtTEnd->deleted()) {
1393            log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTEnd);
1394        }
1395    } while ((coin = coin->fNext));
1396    coin = fHead;
1397    do {
1398        if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)) {
1399            log->record(kCollapsedCoin_Glitch, id, coin, coin->fCoinPtTStart);
1400        }
1401        if (coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
1402            log->record(kCollapsedCoin_Glitch, id, coin, coin->fOppPtTStart);
1403        }
1404    } while ((coin = coin->fNext));
1405}
1406
1407void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1408    const SkCoincidentSpans* coin = fHead;
1409    if (!coin) {
1410        return;
1411    }
1412    do {
1413        const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1414        const SkOpSpanBase* oldEnd = end;
1415        const SkOpSpan* start = coin->fCoinPtTStart->span()->debugStarter(&end);
1416        const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
1417        const SkOpSpanBase* oOldEnd = oEnd;
1418        const SkOpSpanBase* oStart = coin->fOppPtTStart->span()->debugStarter(&oEnd);
1419        bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
1420        if (flipped) {
1421            SkTSwap(oStart, oEnd);
1422        }
1423        const SkOpSpanBase* next = start;
1424        const SkOpSpanBase* oNext = oStart;
1425        do {
1426            next = next->upCast()->next();
1427            oNext = flipped ? oNext->prev() : oNext->upCast()->next();
1428            if (next == end || oNext == oEnd) {
1429                break;
1430            }
1431            if (!next->containsCoinEnd(oNext)) {
1432                log->record(kMarkCoinEnd_Glitch, id, next, oNext);
1433            }
1434            const SkOpSpan* nextSpan = next->upCast();
1435            const SkOpSpan* oNextSpan = oNext->upCast();
1436            if (!nextSpan->containsCoincidence(oNextSpan)) {
1437                log->record(kMarkCoinInsert_Glitch, id, nextSpan, oNextSpan);
1438            }
1439        } while (true);
1440    } while ((coin = coin->fNext));
1441}
1442#endif
1443
1444void SkOpCoincidence::debugShowCoincidence() const {
1445    SkCoincidentSpans* span = fHead;
1446    while (span) {
1447        SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1448                span->fCoinPtTStart->segment()->debugID(),
1449                span->fCoinPtTStart->fT, span->fCoinPtTEnd->fT);
1450        SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1451                span->fOppPtTStart->segment()->debugID(),
1452                span->fOppPtTStart->fT, span->fOppPtTEnd->fT);
1453        span = span->fNext;
1454    }
1455}
1456
1457#if DEBUG_COINCIDENCE
1458void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1459    const SkOpSegment* segment = &fHead;
1460    do {
1461        segment->debugCheckHealth(id, log);
1462    } while ((segment = segment->next()));
1463}
1464
1465void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
1466        const SkOpCoincidence* coincidence) const {
1467    const SkOpSegment* segment = &fHead;
1468    do {
1469        segment->debugMissingCoincidence(id, log, coincidence);
1470    } while ((segment = segment->next()));
1471}
1472#endif
1473
1474void SkOpSegment::debugValidate() const {
1475#if DEBUG_VALIDATE
1476    const SkOpSpanBase* span = &fHead;
1477    double lastT = -1;
1478    const SkOpSpanBase* prev = nullptr;
1479    int count = 0;
1480    int done = 0;
1481    do {
1482        if (!span->final()) {
1483            ++count;
1484            done += span->upCast()->done() ? 1 : 0;
1485        }
1486        SkASSERT(span->segment() == this);
1487        SkASSERT(!prev || prev->upCast()->next() == span);
1488        SkASSERT(!prev || prev == span->prev());
1489        prev = span;
1490        double t = span->ptT()->fT;
1491        SkASSERT(lastT < t);
1492        lastT = t;
1493        span->debugValidate();
1494    } while (!span->final() && (span = span->upCast()->next()));
1495    SkASSERT(count == fCount);
1496    SkASSERT(done == fDoneCount);
1497    SkASSERT(count >= fDoneCount);
1498    SkASSERT(span->final());
1499    span->debugValidate();
1500#endif
1501}
1502
1503bool SkOpSpanBase::debugAlignedEnd(double t, const SkPoint& pt) const {
1504    SkASSERT(zero_or_one(t));
1505    const SkOpSegment* segment = this->segment();
1506    SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt);
1507    if (!debugAlignedInner()) {
1508          return false;
1509    }
1510    if ((t ? segment->lastPt() : segment->pts()[0]) != pt) {
1511        return false;
1512    }
1513    const SkOpPtT* ptT = &this->fPtT;
1514    SkASSERT(t == ptT->fT);
1515    SkASSERT(pt == ptT->fPt);
1516    const SkOpPtT* test = ptT, * stopPtT = ptT;
1517    while ((test = test->next()) != stopPtT) {
1518        const SkOpSegment* other = test->segment();
1519        if (other == this->segment()) {
1520            continue;
1521        }
1522        if (!zero_or_one(test->fT)) {
1523            continue;
1524        }
1525        if ((test->fT ? other->lastPt() : other->pts()[0]) != pt) {
1526            return false;
1527        }
1528    }
1529    return this->fAligned;
1530}
1531
1532bool SkOpSpanBase::debugAlignedInner() const {
1533    // force the spans to share points and t values
1534    const SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
1535    const SkPoint& pt = ptT->fPt;
1536    do {
1537        if (ptT->fPt != pt) {
1538            return false;
1539        }
1540        const SkOpSpanBase* span = ptT->span();
1541        const SkOpPtT* test = ptT;
1542        do {
1543            if ((test = test->next()) == stopPtT) {
1544                break;
1545            }
1546            if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) {
1547                return false;
1548            }
1549        } while (true);
1550    } while ((ptT = ptT->next()) != stopPtT);
1551    return true;
1552}
1553
1554bool SkOpSpanBase::debugCoinEndLoopCheck() const {
1555    int loop = 0;
1556    const SkOpSpanBase* next = this;
1557    SkOpSpanBase* nextCoin;
1558    do {
1559        nextCoin = next->fCoinEnd;
1560        SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
1561        for (int check = 1; check < loop - 1; ++check) {
1562            const SkOpSpanBase* checkCoin = this->fCoinEnd;
1563            const SkOpSpanBase* innerCoin = checkCoin;
1564            for (int inner = check + 1; inner < loop; ++inner) {
1565                innerCoin = innerCoin->fCoinEnd;
1566                if (checkCoin == innerCoin) {
1567                    SkDebugf("*** bad coincident end loop ***\n");
1568                    return false;
1569                }
1570            }
1571        }
1572        ++loop;
1573    } while ((next = nextCoin) && next != this);
1574    return true;
1575}
1576
1577bool SkOpSpanBase::debugContains(const SkOpSegment* segment) const {
1578    const SkOpPtT* start = &fPtT;
1579    const SkOpPtT* walk = start;
1580    while ((walk = walk->next()) != start) {
1581        if (walk->segment() == segment) {
1582            return true;
1583        }
1584    }
1585    return false;
1586}
1587
1588const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
1589    const SkOpSpanBase* end = *endPtr;
1590    SkASSERT(this->segment() == end->segment());
1591    const SkOpSpanBase* result;
1592    if (t() < end->t()) {
1593        result = this;
1594    } else {
1595        result = end;
1596        *endPtr = this;
1597    }
1598    return result->upCast();
1599}
1600
1601void SkOpSpanBase::debugValidate() const {
1602#if DEBUG_VALIDATE
1603    const SkOpPtT* ptT = &fPtT;
1604    SkASSERT(ptT->span() == this);
1605    do {
1606//        SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
1607        ptT->debugValidate();
1608        ptT = ptT->next();
1609    } while (ptT != &fPtT);
1610    SkASSERT(this->debugCoinEndLoopCheck());
1611    if (!this->final()) {
1612        SkASSERT(this->upCast()->debugCoinLoopCheck());
1613    }
1614    if (fFromAngle) {
1615        fFromAngle->debugValidate();
1616    }
1617    if (!this->final() && this->upCast()->toAngle()) {
1618        this->upCast()->toAngle()->debugValidate();
1619    }
1620#endif
1621}
1622
1623bool SkOpSpan::debugCoinLoopCheck() const {
1624    int loop = 0;
1625    const SkOpSpan* next = this;
1626    SkOpSpan* nextCoin;
1627    do {
1628        nextCoin = next->fCoincident;
1629        SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
1630        for (int check = 1; check < loop - 1; ++check) {
1631            const SkOpSpan* checkCoin = this->fCoincident;
1632            const SkOpSpan* innerCoin = checkCoin;
1633            for (int inner = check + 1; inner < loop; ++inner) {
1634                innerCoin = innerCoin->fCoincident;
1635                if (checkCoin == innerCoin) {
1636                    SkDebugf("*** bad coincident loop ***\n");
1637                    return false;
1638                }
1639            }
1640        }
1641        ++loop;
1642    } while ((next = nextCoin) && next != this);
1643    return true;
1644}
1645
1646// called only by test code
1647int SkIntersections::debugCoincidentUsed() const {
1648    if (!fIsCoincident[0]) {
1649        SkASSERT(!fIsCoincident[1]);
1650        return 0;
1651    }
1652    int count = 0;
1653    SkDEBUGCODE(int count2 = 0;)
1654    for (int index = 0; index < fUsed; ++index) {
1655        if (fIsCoincident[0] & (1 << index)) {
1656            ++count;
1657        }
1658#ifdef SK_DEBUG
1659        if (fIsCoincident[1] & (1 << index)) {
1660            ++count2;
1661        }
1662#endif
1663    }
1664    SkASSERT(count == count2);
1665    return count;
1666}
1667
1668#include "SkOpContour.h"
1669
1670bool SkOpPtT::debugContains(const SkOpPtT* check) const {
1671    SkASSERT(this != check);
1672    const SkOpPtT* ptT = this;
1673    int links = 0;
1674    do {
1675        ptT = ptT->next();
1676        if (ptT == check) {
1677            return true;
1678        }
1679        ++links;
1680        const SkOpPtT* test = this;
1681        for (int index = 0; index < links; ++index) {
1682            if (ptT == test) {
1683                return false;
1684            }
1685            test = test->next();
1686        }
1687    } while (true);
1688}
1689
1690const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
1691    SkASSERT(this->segment() != check);
1692    const SkOpPtT* ptT = this;
1693    int links = 0;
1694    do {
1695        ptT = ptT->next();
1696        if (ptT->segment() == check) {
1697            return ptT;
1698        }
1699        ++links;
1700        const SkOpPtT* test = this;
1701        for (int index = 0; index < links; ++index) {
1702            if (ptT == test) {
1703                return nullptr;
1704            }
1705            test = test->next();
1706        }
1707    } while (true);
1708}
1709
1710int SkOpPtT::debugLoopLimit(bool report) const {
1711    int loop = 0;
1712    const SkOpPtT* next = this;
1713    do {
1714        for (int check = 1; check < loop - 1; ++check) {
1715            const SkOpPtT* checkPtT = this->fNext;
1716            const SkOpPtT* innerPtT = checkPtT;
1717            for (int inner = check + 1; inner < loop; ++inner) {
1718                innerPtT = innerPtT->fNext;
1719                if (checkPtT == innerPtT) {
1720                    if (report) {
1721                        SkDebugf("*** bad ptT loop ***\n");
1722                    }
1723                    return loop;
1724                }
1725            }
1726        }
1727        // there's nothing wrong with extremely large loop counts -- but this may appear to hang
1728        // by taking a very long time to figure out that no loop entry is a duplicate
1729        // -- and it's likely that a large loop count is indicative of a bug somewhere
1730        if (++loop > 1000) {
1731            SkDebugf("*** loop count exceeds 1000 ***\n");
1732            return 1000;
1733        }
1734    } while ((next = next->fNext) && next != this);
1735    return 0;
1736}
1737
1738void SkOpPtT::debugValidate() const {
1739#if DEBUG_VALIDATE
1740    SkOpGlobalState::Phase phase = contour()->globalState()->phase();
1741    if (phase == SkOpGlobalState::kIntersecting
1742            || phase == SkOpGlobalState::kFixWinding) {
1743        return;
1744    }
1745    SkASSERT(fNext);
1746    SkASSERT(fNext != this);
1747    SkASSERT(fNext->fNext);
1748    SkASSERT(debugLoopLimit(false) == 0);
1749#endif
1750}
1751
1752static void output_scalar(SkScalar num) {
1753    if (num == (int) num) {
1754        SkDebugf("%d", (int) num);
1755    } else {
1756        SkString str;
1757        str.printf("%1.9g", num);
1758        int width = (int) str.size();
1759        const char* cStr = str.c_str();
1760        while (cStr[width - 1] == '0') {
1761            --width;
1762        }
1763        str.resize(width);
1764        SkDebugf("%sf", str.c_str());
1765    }
1766}
1767
1768static void output_points(const SkPoint* pts, int count) {
1769    for (int index = 0; index < count; ++index) {
1770        output_scalar(pts[index].fX);
1771        SkDebugf(", ");
1772        output_scalar(pts[index].fY);
1773        if (index + 1 < count) {
1774            SkDebugf(", ");
1775        }
1776    }
1777}
1778
1779static void showPathContours(SkPath::RawIter& iter, const char* pathName) {
1780    uint8_t verb;
1781    SkPoint pts[4];
1782    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1783        switch (verb) {
1784            case SkPath::kMove_Verb:
1785                SkDebugf("    %s.moveTo(", pathName);
1786                output_points(&pts[0], 1);
1787                SkDebugf(");\n");
1788                continue;
1789            case SkPath::kLine_Verb:
1790                SkDebugf("    %s.lineTo(", pathName);
1791                output_points(&pts[1], 1);
1792                SkDebugf(");\n");
1793                break;
1794            case SkPath::kQuad_Verb:
1795                SkDebugf("    %s.quadTo(", pathName);
1796                output_points(&pts[1], 2);
1797                SkDebugf(");\n");
1798                break;
1799            case SkPath::kConic_Verb:
1800                SkDebugf("    %s.conicTo(", pathName);
1801                output_points(&pts[1], 2);
1802                SkDebugf(", %1.9gf);\n", iter.conicWeight());
1803                break;
1804            case SkPath::kCubic_Verb:
1805                SkDebugf("    %s.cubicTo(", pathName);
1806                output_points(&pts[1], 3);
1807                SkDebugf(");\n");
1808                break;
1809            case SkPath::kClose_Verb:
1810                SkDebugf("    %s.close();\n", pathName);
1811                break;
1812            default:
1813                SkDEBUGFAIL("bad verb");
1814                return;
1815        }
1816    }
1817}
1818
1819static const char* gFillTypeStr[] = {
1820    "kWinding_FillType",
1821    "kEvenOdd_FillType",
1822    "kInverseWinding_FillType",
1823    "kInverseEvenOdd_FillType"
1824};
1825
1826void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
1827    SkPath::RawIter iter(path);
1828#define SUPPORT_RECT_CONTOUR_DETECTION 0
1829#if SUPPORT_RECT_CONTOUR_DETECTION
1830    int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0;
1831    if (rectCount > 0) {
1832        SkTDArray<SkRect> rects;
1833        SkTDArray<SkPath::Direction> directions;
1834        rects.setCount(rectCount);
1835        directions.setCount(rectCount);
1836        path.rectContours(rects.begin(), directions.begin());
1837        for (int contour = 0; contour < rectCount; ++contour) {
1838            const SkRect& rect = rects[contour];
1839            SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
1840                    rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
1841                    ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
1842        }
1843        return;
1844    }
1845#endif
1846    SkPath::FillType fillType = path.getFillType();
1847    SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
1848    if (includeDeclaration) {
1849        SkDebugf("    SkPath %s;\n", name);
1850    }
1851    SkDebugf("    %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
1852    iter.setPath(path);
1853    showPathContours(iter, name);
1854}
1855