Quelle  SkPathOpsDebug.cpp   Sprache: C

/*
 * Copyright 2013 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "src/pathops/SkPathOpsDebug.h"

#include "include/core/SkPath.h"
#include "include/core/SkPathTypes.h"
#include "include/core/SkPoint.h"
#include "include/core/SkScalar.h"
#include "include/core/SkString.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkMath.h"
#include "include/private/base/SkMutex.h"
#include "src/core/SkPathPriv.h"
#include "src/pathops/SkIntersections.h"
#include "src/pathops/SkOpAngle.h"
#include "src/pathops/SkOpCoincidence.h"
#include "src/pathops/SkOpSegment.h"
#include "src/pathops/SkOpSpan.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsQuad.h"
#include "src/pathops/SkPathOpsRect.h"
#include "src/pathops/SkPathOpsTypes.h"

#include <cstdint>
#include <cstring>

#if DEBUG_DUMP_VERIFY
bool SkPathOpsDebug::gDumpOp;  // set to true to write op to file before a crash
bool SkPathOpsDebug::gVerifyOp;  // set to true to compare result against regions
#endif

bool SkPathOpsDebug::gRunFail;  // set to true to check for success on tests known to fail
bool SkPathOpsDebug::gVeryVerbose;  // set to true to run extensive checking tests

#define FAIL_IF_COIN(cond, coin) \
         do { if (cond) log->record(SkPathOpsDebug::kFail_Glitch, coin); } while (false)

#undef FAIL_WITH_NULL_IF
#define FAIL_WITH_NULL_IF(cond, span) \
         do { if (cond) log->record(SkPathOpsDebug::kFail_Glitch, span); } while (false)

#define RETURN_FALSE_IF(cond, span) \
         do { if (cond) log->record(SkPathOpsDebug::kReturnFalse_Glitch, span); \
         } while (false)

#if DEBUG_SORT
int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
int SkPathOpsDebug::gSortCount;
#endif

#if DEBUG_ACTIVE_OP
const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor", "rdiff"};
#endif

#if defined SK_DEBUG || !FORCE_RELEASE

int SkPathOpsDebug::gContourID = 0;
int SkPathOpsDebug::gSegmentID = 0;

bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase*>& chaseArray,
                                   const SkOpSpanBase* span) {
    for (int index = 0; index < chaseArray.size(); ++index) {
        const SkOpSpanBase* entry = chaseArray[index];
        if (entry == span) {
            return true;
        }
    }
    return false;
}
#endif

#if DEBUG_ACTIVE_SPANS
SkString SkPathOpsDebug::gActiveSpans;
#endif

#if DEBUG_COIN

#include "src/pathops/SkOpContour.h"

class SkCoincidentSpans;

SkPathOpsDebug::CoinDict SkPathOpsDebug::gCoinSumChangedDict;
SkPathOpsDebug::CoinDict SkPathOpsDebug::gCoinSumVisitedDict;

static const int kGlitchType_Count = SkPathOpsDebug::kUnalignedTail_Glitch + 1;

struct SpanGlitch {
    const SkOpSpanBase* fBase;
    const SkOpSpanBase* fSuspect;
    const SkOpSegment* fSegment;
    const SkOpSegment* fOppSegment;
    const SkOpPtT* fCoinSpan;
    const SkOpPtT* fEndSpan;
    const SkOpPtT* fOppSpan;
    const SkOpPtT* fOppEndSpan;
    double fStartT;
    double fEndT;
    double fOppStartT;
    double fOppEndT;
    SkPoint fPt;
    SkPathOpsDebug::GlitchType fType;

    void dumpType() const;
};

struct SkPathOpsDebug::GlitchLog {
    void init(const SkOpGlobalState* state) {
        fGlobalState = state;
    }

    SpanGlitch* recordCommon(GlitchType type) {
        SpanGlitch* glitch = fGlitches.append();
        glitch->fBase = nullptr;
        glitch->fSuspect = nullptr;
        glitch->fSegment = nullptr;
        glitch->fOppSegment = nullptr;
        glitch->fCoinSpan = nullptr;
        glitch->fEndSpan = nullptr;
        glitch->fOppSpan = nullptr;
        glitch->fOppEndSpan = nullptr;
        glitch->fStartT = SK_ScalarNaN;
        glitch->fEndT = SK_ScalarNaN;
        glitch->fOppStartT = SK_ScalarNaN;
        glitch->fOppEndT = SK_ScalarNaN;
        glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN };
        glitch->fType = type;
        return glitch;
    }

    void record(GlitchType type, const SkOpSpanBase* base, const SkOpSpanBase* suspect = nullptr) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fBase = base;
        glitch->fSuspect = suspect;
    }

    void record(GlitchType type, const SkOpSpanBase* base, const SkOpPtT* ptT) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fBase = base;
        glitch->fCoinSpan = ptT;
    }

    void record(GlitchType type,
                const SkCoincidentSpans* coin,
                const SkCoincidentSpans* opp = nullptr) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fCoinSpan = coin->coinPtTStart();
        glitch->fEndSpan = coin->coinPtTEnd();
        if (opp) {
            glitch->fOppSpan = opp->coinPtTStart();
            glitch->fOppEndSpan = opp->coinPtTEnd();
        }
    }

    void record(GlitchType type, const SkOpSpanBase* base,
            const SkOpSegment* seg, double t, SkPoint pt) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fBase = base;
        glitch->fSegment = seg;
        glitch->fStartT = t;
        glitch->fPt = pt;
    }

    void record(GlitchType type, const SkOpSpanBase* base, double t,
            SkPoint pt) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fBase = base;
        glitch->fStartT = t;
        glitch->fPt = pt;
    }

    void record(GlitchType type, const SkCoincidentSpans* coin,
            const SkOpPtT* coinSpan, const SkOpPtT* endSpan) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fCoinSpan = coin->coinPtTStart();
        glitch->fEndSpan = coin->coinPtTEnd();
        glitch->fEndSpan = endSpan;
        glitch->fOppSpan = coinSpan;
        glitch->fOppEndSpan = endSpan;
    }

    void record(GlitchType type, const SkCoincidentSpans* coin,
            const SkOpSpanBase* base) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fBase = base;
        glitch->fCoinSpan = coin->coinPtTStart();
        glitch->fEndSpan = coin->coinPtTEnd();
    }

    void record(GlitchType type, const SkOpPtT* ptTS, const SkOpPtT* ptTE,
            const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fCoinSpan = ptTS;
        glitch->fEndSpan = ptTE;
        glitch->fOppSpan = oPtTS;
        glitch->fOppEndSpan = oPtTE;
    }

    void record(GlitchType type, const SkOpSegment* seg, double startT,
            double endT, const SkOpSegment* oppSeg, double oppStartT, double oppEndT) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fSegment = seg;
        glitch->fStartT = startT;
        glitch->fEndT = endT;
        glitch->fOppSegment = oppSeg;
        glitch->fOppStartT = oppStartT;
        glitch->fOppEndT = oppEndT;
    }

    void record(GlitchType type, const SkOpSegment* seg,
            const SkOpSpan* span) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fSegment = seg;
        glitch->fBase = span;
    }

    void record(GlitchType type, double t, const SkOpSpanBase* span) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fStartT = t;
        glitch->fBase = span;
    }

    void record(GlitchType type, const SkOpSegment* seg) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fSegment = seg;
    }

    void record(GlitchType type, const SkCoincidentSpans* coin,
            const SkOpPtT* ptT) {
        SpanGlitch* glitch = recordCommon(type);
        glitch->fCoinSpan = coin->coinPtTStart();
        glitch->fEndSpan = ptT;
    }

    SkTDArray<SpanGlitch> fGlitches;
    const SkOpGlobalState* fGlobalState;
};


void SkPathOpsDebug::CoinDict::add(const SkPathOpsDebug::CoinDict& dict) {
    int count = dict.fDict.size();
    for (int index = 0; index < count; ++index) {
        this->add(dict.fDict[index]);
    }
}

void SkPathOpsDebug::CoinDict::add(const CoinDictEntry& key) {
    int count = fDict.size();
    for (int index = 0; index < count; ++index) {
        CoinDictEntry* entry = &fDict[index];
        if (entry->fIteration == key.fIteration && entry->fLineNumber == key.fLineNumber) {
            SkASSERT(!strcmp(entry->fFunctionName, key.fFunctionName));
            if (entry->fGlitchType == kUninitialized_Glitch) {
                entry->fGlitchType = key.fGlitchType;
            }
            return;
        }
    }
    *fDict.append() = key;
}

#endif

#if DEBUG_COIN
static void missing_coincidence(SkPathOpsDebug::GlitchLog* glitches,
                                const SkOpContourHead* contourList) {
    const SkOpContour* contour = contourList;
    // bool result = false;
    do {
        /* result |= */ contour->debugMissingCoincidence(glitches);
    } while ((contour = contour->next()));
    return;
}

static void move_multiples(SkPathOpsDebug::GlitchLog* glitches,
                           const SkOpContourHead* contourList) {
    const SkOpContour* contour = contourList;
    do {
        contour->debugMoveMultiples(glitches);
    } while ((contour = contour->next()));
    return;
}

static void move_nearby(SkPathOpsDebug::GlitchLog* glitches, const SkOpContourHead* contourList) {
    const SkOpContour* contour = contourList;
    do {
        contour->debugMoveNearby(glitches);
    } while ((contour = contour->next()));
}

#endif

#if DEBUG_COIN
void SkOpGlobalState::debugAddToCoinChangedDict() {

#if DEBUG_COINCIDENCE
    SkPathOpsDebug::CheckHealth(fContourHead);
#endif
    // see if next coincident operation makes a change; if so, record it
    SkPathOpsDebug::GlitchLog glitches;
    const char* funcName = fCoinDictEntry.fFunctionName;
    if (!strcmp("calc_angles", funcName)) {
        //
    } else if (!strcmp("missing_coincidence", funcName)) {
        missing_coincidence(&glitches, fContourHead);
    } else if (!strcmp("move_multiples", funcName)) {
        move_multiples(&glitches, fContourHead);
    } else if (!strcmp("move_nearby", funcName)) {
        move_nearby(&glitches, fContourHead);
    } else if (!strcmp("addExpanded", funcName)) {
        fCoincidence->debugAddExpanded(&glitches);
    } else if (!strcmp("addMissing", funcName)) {
        bool added;
        fCoincidence->debugAddMissing(&glitches, &added);
    } else if (!strcmp("addEndMovedSpans", funcName)) {
        fCoincidence->debugAddEndMovedSpans(&glitches);
    } else if (!strcmp("correctEnds", funcName)) {
        fCoincidence->debugCorrectEnds(&glitches);
    } else if (!strcmp("expand", funcName)) {
        fCoincidence->debugExpand(&glitches);
    } else if (!strcmp("findOverlaps", funcName)) {
        //
    } else if (!strcmp("mark", funcName)) {
        fCoincidence->debugMark(&glitches);
    } else if (!strcmp("apply", funcName)) {
        //
    } else {
        SkASSERT(0);   // add missing case
    }
    if (glitches.fGlitches.size()) {
        fCoinDictEntry.fGlitchType = glitches.fGlitches[0].fType;
    }
    fCoinChangedDict.add(fCoinDictEntry);
}
#endif

void SkPathOpsDebug::ShowActiveSpans(SkOpContourHead* contourList) {
#if DEBUG_ACTIVE_SPANS
    SkString str;
    SkOpContour* contour = contourList;
    do {
        contour->debugShowActiveSpans(&str);
    } while ((contour = contour->next()));
    if (!gActiveSpans.equals(str)) {
        const char* s = str.c_str();
        const char* end;
        while ((end = strchr(s, '\n'))) {
            SkDebugf("%.*s", (int) (end - s + 1), s);
            s = end + 1;
        }
        gActiveSpans.set(str);
    }
#endif
}

#if DEBUG_COINCIDENCE || DEBUG_COIN
void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList) {
#if DEBUG_COINCIDENCE
    contourList->globalState()->debugSetCheckHealth(true);
#endif
#if DEBUG_COIN
    GlitchLog glitches;
    const SkOpContour* contour = contourList;
    const SkOpCoincidence* coincidence = contour->globalState()->coincidence();
    coincidence->debugCheckValid(&glitches); // don't call validate; spans may be inconsistent
    do {
        contour->debugCheckHealth(&glitches);
        contour->debugMissingCoincidence(&glitches);
    } while ((contour = contour->next()));
    bool added;
    coincidence->debugAddMissing(&glitches, &added);
    coincidence->debugExpand(&glitches);
    coincidence->debugAddExpanded(&glitches);
    coincidence->debugMark(&glitches);
    unsigned mask = 0;
    for (int index = 0; index < glitches.fGlitches.size(); ++index) {
        const SpanGlitch& glitch = glitches.fGlitches[index];
        mask |= 1 << glitch.fType;
    }
    for (int index = 0; index < kGlitchType_Count; ++index) {
        SkDebugf(mask & (1 << index) ? "x" : "-");
    }
    SkDebugf(" %s\n", contourList->globalState()->debugCoinDictEntry().fFunctionName);
    for (int index = 0; index < glitches.fGlitches.size(); ++index) {
        const SpanGlitch& glitch = glitches.fGlitches[index];
        SkDebugf("%02d: ", index);
        if (glitch.fBase) {
            SkDebugf(" seg/base=%d/%d", glitch.fBase->segment()->debugID(),
                    glitch.fBase->debugID());
        }
        if (glitch.fSuspect) {
            SkDebugf(" seg/base=%d/%d", glitch.fSuspect->segment()->debugID(),
                    glitch.fSuspect->debugID());
        }
        if (glitch.fSegment) {
            SkDebugf(" segment=%d", glitch.fSegment->debugID());
        }
        if (glitch.fCoinSpan) {
            SkDebugf(" coinSeg/Span/PtT=%d/%d/%d", glitch.fCoinSpan->segment()->debugID(),
                    glitch.fCoinSpan->span()->debugID(), glitch.fCoinSpan->debugID());
        }
        if (glitch.fEndSpan) {
            SkDebugf(" endSpan=%d", glitch.fEndSpan->debugID());
        }
        if (glitch.fOppSpan) {
            SkDebugf(" oppSeg/Span/PtT=%d/%d/%d", glitch.fOppSpan->segment()->debugID(),
                    glitch.fOppSpan->span()->debugID(), glitch.fOppSpan->debugID());
        }
        if (glitch.fOppEndSpan) {
            SkDebugf(" oppEndSpan=%d", glitch.fOppEndSpan->debugID());
        }
        if (!SkIsNaN(glitch.fStartT)) {
            SkDebugf(" startT=%g", glitch.fStartT);
        }
        if (!SkIsNaN(glitch.fEndT)) {
            SkDebugf(" endT=%g", glitch.fEndT);
        }
        if (glitch.fOppSegment) {
            SkDebugf(" segment=%d", glitch.fOppSegment->debugID());
        }
        if (!SkIsNaN(glitch.fOppStartT)) {
            SkDebugf(" oppStartT=%g", glitch.fOppStartT);
        }
        if (!SkIsNaN(glitch.fOppEndT)) {
            SkDebugf(" oppEndT=%g", glitch.fOppEndT);
        }
        if (!SkIsNaN(glitch.fPt.fX) || !SkIsNaN(glitch.fPt.fY)) {
            SkDebugf(" pt=%g,%g", glitch.fPt.fX, glitch.fPt.fY);
        }
        DumpGlitchType(glitch.fType);
        SkDebugf("\n");
    }
#if DEBUG_COINCIDENCE
    contourList->globalState()->debugSetCheckHealth(false);
#endif
#if 01 && DEBUG_ACTIVE_SPANS
//    SkDebugf("active after %s:\n", id);
    ShowActiveSpans(contourList);
#endif
#endif
}
#endif

#if DEBUG_COIN
void SkPathOpsDebug::DumpGlitchType(GlitchType glitchType) {
    switch (glitchType) {
        case kAddCorruptCoin_Glitch: SkDebugf(" AddCorruptCoin"); break;
        case kAddExpandedCoin_Glitch: SkDebugf(" AddExpandedCoin"); break;
        case kAddExpandedFail_Glitch: SkDebugf(" AddExpandedFail"); break;
        case kAddIfCollapsed_Glitch: SkDebugf(" AddIfCollapsed"); break;
        case kAddIfMissingCoin_Glitch: SkDebugf(" AddIfMissingCoin"); break;
        case kAddMissingCoin_Glitch: SkDebugf(" AddMissingCoin"); break;
        case kAddMissingExtend_Glitch: SkDebugf(" AddMissingExtend"); break;
        case kAddOrOverlap_Glitch: SkDebugf(" AAddOrOverlap"); break;
        case kCollapsedCoin_Glitch: SkDebugf(" CollapsedCoin"); break;
        case kCollapsedDone_Glitch: SkDebugf(" CollapsedDone"); break;
        case kCollapsedOppValue_Glitch: SkDebugf(" CollapsedOppValue"); break;
        case kCollapsedSpan_Glitch: SkDebugf(" CollapsedSpan"); break;
        case kCollapsedWindValue_Glitch: SkDebugf(" CollapsedWindValue"); break;
        case kCorrectEnd_Glitch: SkDebugf(" CorrectEnd"); break;
        case kDeletedCoin_Glitch: SkDebugf(" DeletedCoin"); break;
        case kExpandCoin_Glitch: SkDebugf(" ExpandCoin"); break;
        case kFail_Glitch: SkDebugf(" Fail"); break;
        case kMarkCoinEnd_Glitch: SkDebugf(" MarkCoinEnd"); break;
        case kMarkCoinInsert_Glitch: SkDebugf(" MarkCoinInsert"); break;
        case kMarkCoinMissing_Glitch: SkDebugf(" MarkCoinMissing"); break;
        case kMarkCoinStart_Glitch: SkDebugf(" MarkCoinStart"); break;
        case kMergeMatches_Glitch: SkDebugf(" MergeMatches"); break;
        case kMissingCoin_Glitch: SkDebugf(" MissingCoin"); break;
        case kMissingDone_Glitch: SkDebugf(" MissingDone"); break;
        case kMissingIntersection_Glitch: SkDebugf(" MissingIntersection"); break;
        case kMoveMultiple_Glitch: SkDebugf(" MoveMultiple"); break;
        case kMoveNearbyClearAll_Glitch: SkDebugf(" MoveNearbyClearAll"); break;
        case kMoveNearbyClearAll2_Glitch: SkDebugf(" MoveNearbyClearAll2"); break;
        case kMoveNearbyMerge_Glitch: SkDebugf(" MoveNearbyMerge"); break;
        case kMoveNearbyMergeFinal_Glitch: SkDebugf(" MoveNearbyMergeFinal"); break;
        case kMoveNearbyRelease_Glitch: SkDebugf(" MoveNearbyRelease"); break;
        case kMoveNearbyReleaseFinal_Glitch: SkDebugf(" MoveNearbyReleaseFinal"); break;
        case kReleasedSpan_Glitch: SkDebugf(" ReleasedSpan"); break;
        case kReturnFalse_Glitch: SkDebugf(" ReturnFalse"); break;
        case kUnaligned_Glitch: SkDebugf(" Unaligned"); break;
        case kUnalignedHead_Glitch: SkDebugf(" UnalignedHead"); break;
        case kUnalignedTail_Glitch: SkDebugf(" UnalignedTail"); break;
        case kUninitialized_Glitch: break;
        default: SkASSERT(0);
    }
}
#endif

#if defined SK_DEBUG || !FORCE_RELEASE
void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
    size_t len = strlen(str);
    bool num = false;
    for (size_t idx = 0; idx < len; ++idx) {
        if (num && str[idx] == 'e') {
            if (len + 2 >= bufferLen) {
                return;
            }
            memmove(&str[idx + 2], &str[idx + 1], len - idx);
            str[idx] = '*';
            str[idx + 1] = '^';
            ++len;
        }
        num = str[idx] >= '0' && str[idx] <= '9';
    }
}

bool SkPathOpsDebug::ValidWind(int wind) {
    return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
}

void SkPathOpsDebug::WindingPrintf(int wind) {
    if (wind == SK_MinS32) {
        SkDebugf("?");
    } else {
        SkDebugf("%d", wind);
    }
}
#endif //  defined SK_DEBUG || !FORCE_RELEASE


static void show_function_header(const char* functionName) {
    SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName);
    if (strcmp("skphealth_com76", functionName) == 0) {
        SkDebugf("found it\n");
    }
}

static const char* gOpStrs[] = {
    "kDifference_SkPathOp",
    "kIntersect_SkPathOp",
    "kUnion_SkPathOp",
    "kXOR_PathOp",
    "kReverseDifference_SkPathOp",
};

const char* SkPathOpsDebug::OpStr(SkPathOp op) {
    return gOpStrs[op];
}

static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) {
    SkDebugf(" testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]);
    SkDebugf("}\n");
}

void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
        const char* testName) {
    static SkMutex& mutex = *(new SkMutex);

    SkAutoMutexExclusive ac(mutex);
    show_function_header(testName);
    ShowOnePath(a, "path", true);
    ShowOnePath(b, "pathB", true);
    show_op(shapeOp, "path", "pathB");
}

#if DEBUG_COIN

void SkOpGlobalState::debugAddToGlobalCoinDicts() {
    static SkMutex& mutex = *(new SkMutex);
    SkAutoMutexExclusive ac(mutex);
    SkPathOpsDebug::gCoinSumChangedDict.add(fCoinChangedDict);
    SkPathOpsDebug::gCoinSumVisitedDict.add(fCoinVisitedDict);
}

#endif

#if DEBUG_T_SECT_LOOP_COUNT
void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt,
        const SkIntersectionHelper& wn) {
    for (int index = 0; index < (int) std::size(fDebugLoopCount); ++index) {
        SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index;
        if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) {
            continue;
        }
        fDebugLoopCount[index] = i->debugLoopCount(looper);
        fDebugWorstVerb[index * 2] = wt.segment()->verb();
        fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb();
        sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8);
        memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(),
                (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint));
        memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(),
                (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint));
        fDebugWorstWeight[index * 2] = wt.weight();
        fDebugWorstWeight[index * 2 + 1] = wn.weight();
    }
    i->debugResetLoopCount();
}

void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) {
    for (int index = 0; index < (int) std::size(fDebugLoopCount); ++index) {
        if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) {
            continue;
        }
        fDebugLoopCount[index] = local->fDebugLoopCount[index];
        fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2];
        fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1];
        memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4],
                sizeof(SkPoint) * 8);
        fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2];
        fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1];
    }
    local->debugResetLoopCounts();
}

static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) {
    if (!verb) {
        return;
    }
    const char* verbs[] = { "", "line", "quad", "conic", "cubic" };
    SkDebugf("%s: {{", verbs[verb]);
    int ptCount = SkPathOpsVerbToPoints(verb);
    for (int index = 0; index <= ptCount; ++index) {
        SkDPoint::Dump((&pts)[index]);
        if (index < ptCount - 1) {
            SkDebugf(", ");
        }
    }
    SkDebugf("}");
    if (weight != 1) {
        SkDebugf(", ");
        if (weight == floorf(weight)) {
            SkDebugf("%.0f", weight);
        } else {
            SkDebugf("%1.9gf", weight);
        }
    }
    SkDebugf("}\n");
}

void SkOpGlobalState::debugLoopReport() {
    const char* loops[] = { "iterations", "coinChecks", "perpCalcs" };
    SkDebugf("\n");
    for (int index = 0; index < (int) std::size(fDebugLoopCount); ++index) {
        SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]);
        dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4],
                fDebugWorstWeight[index * 2]);
        dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4],
                fDebugWorstWeight[index * 2 + 1]);
    }
}

void SkOpGlobalState::debugResetLoopCounts() {
    sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
    sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb));
    sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts));
    sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight));
}
#endif

bool SkOpGlobalState::DebugRunFail() {
    return SkPathOpsDebug::gRunFail;
}

// this is const so it can be called by const methods that overwise don't alter state
#if DEBUG_VALIDATE || DEBUG_COIN
void SkOpGlobalState::debugSetPhase(const char* funcName  DEBUG_COIN_DECLARE_PARAMS()) const {
    auto writable = const_cast<SkOpGlobalState*>(this);
#if DEBUG_VALIDATE
    writable->setPhase(phase);
#endif
#if DEBUG_COIN
    SkPathOpsDebug::CoinDictEntry* entry = &writable->fCoinDictEntry;
    writable->fPreviousFuncName = entry->fFunctionName;
    entry->fIteration = iteration;
    entry->fLineNumber = lineNo;
    entry->fGlitchType = SkPathOpsDebug::kUninitialized_Glitch;
    entry->fFunctionName = funcName;
    writable->fCoinVisitedDict.add(*entry);
    writable->debugAddToCoinChangedDict();
#endif
}
#endif

#if DEBUG_T_SECT_LOOP_COUNT
void SkIntersections::debugBumpLoopCount(DebugLoop index) {
    fDebugLoopCount[index]++;
}

int SkIntersections::debugLoopCount(DebugLoop index) const {
    return fDebugLoopCount[index];
}

void SkIntersections::debugResetLoopCount() {
    sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
}
#endif

SkDCubic SkDQuad::debugToCubic() const {
    SkDCubic cubic;
    cubic[0] = fPts[0];
    cubic[2] = fPts[1];
    cubic[3] = fPts[2];
    cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3;
    cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3;
    cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3;
    cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3;
    return cubic;
}

void SkDQuad::debugSet(const SkDPoint* pts) {
    memcpy(fPts, pts, sizeof(fPts));
    SkDEBUGCODE(fDebugGlobalState = nullptr);
}

void SkDCubic::debugSet(const SkDPoint* pts) {
    memcpy(fPts, pts, sizeof(fPts));
    SkDEBUGCODE(fDebugGlobalState = nullptr);
}

void SkDConic::debugSet(const SkDPoint* pts, SkScalar weight) {
    fPts.debugSet(pts);
    fWeight = weight;
}

void SkDRect::debugInit() {
    fLeft = fTop = fRight = fBottom = SK_ScalarNaN;
}

#if DEBUG_COIN
// commented-out lines keep this in sync with addT()
 const SkOpPtT* SkOpSegment::debugAddT(double t, SkPathOpsDebug::GlitchLog* log) const {
    debugValidate();
    SkPoint pt = this->ptAtT(t);
    const SkOpSpanBase* span = &fHead;
    do {
        const SkOpPtT* result = span->ptT();
        if (t == result->fT || this->match(result, this, t, pt)) {
//             span->bumpSpanAdds();
             return result;
        }
        if (t < result->fT) {
            const SkOpSpan* prev = result->span()->prev();
            FAIL_WITH_NULL_IF(!prev, span);
            // marks in global state that new op span has been allocated
            this->globalState()->setAllocatedOpSpan();
//             span->init(this, prev, t, pt);
            this->debugValidate();
// #if DEBUG_ADD_T
//             SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
//                     span->segment()->debugID(), span->debugID());
// #endif
//             span->bumpSpanAdds();
            return nullptr;
        }
        FAIL_WITH_NULL_IF(span != &fTail, span);
    } while ((span = span->upCast()->next()));
    SkASSERT(0);
    return nullptr;  // we never get here, but need this to satisfy compiler
}
#endif

#if DEBUG_ANGLE
void SkOpSegment::debugCheckAngleCoin() const {
    const SkOpSpanBase* base = &fHead;
    const SkOpSpan* span;
    do {
        const SkOpAngle* angle = base->fromAngle();
        if (angle && angle->debugCheckCoincidence()) {
            angle->debugCheckNearCoincidence();
        }
        if (base->final()) {
             break;
        }
        span = base->upCast();
        angle = span->toAngle();
        if (angle && angle->debugCheckCoincidence()) {
            angle->debugCheckNearCoincidence();
        }
    } while ((base = span->next()));
}
#endif

#if DEBUG_COIN
// this mimics the order of the checks in handle coincidence
void SkOpSegment::debugCheckHealth(SkPathOpsDebug::GlitchLog* glitches) const {
    debugMoveMultiples(glitches);
    debugMoveNearby(glitches);
    debugMissingCoincidence(glitches);
}

// commented-out lines keep this in sync with clearAll()
void SkOpSegment::debugClearAll(SkPathOpsDebug::GlitchLog* glitches) const {
    const SkOpSpan* span = &fHead;
    do {
        this->debugClearOne(span, glitches);
    } while ((span = span->next()->upCastable()));
    this->globalState()->coincidence()->debugRelease(glitches, this);
}

// commented-out lines keep this in sync with clearOne()
void SkOpSegment::debugClearOne(const SkOpSpan* span, SkPathOpsDebug::GlitchLog* glitches) const {
    if (span->windValue()) glitches->record(SkPathOpsDebug::kCollapsedWindValue_Glitch, span);
    if (span->oppValue()) glitches->record(SkPathOpsDebug::kCollapsedOppValue_Glitch, span);
    if (!span->done()) glitches->record(SkPathOpsDebug::kCollapsedDone_Glitch, span);
}
#endif

SkOpAngle* SkOpSegment::debugLastAngle() {
    SkOpAngle* result = nullptr;
    SkOpSpan* span = this->head();
    do {
        if (span->toAngle()) {
            SkASSERT(!result);
            result = span->toAngle();
        }
    } while ((span = span->next()->upCastable()));
    SkASSERT(result);
    return result;
}

#if DEBUG_COIN
// commented-out lines keep this in sync with ClearVisited
void SkOpSegment::DebugClearVisited(const SkOpSpanBase* span) {
    // reset visited flag back to false
    do {
        const SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
        while ((ptT = ptT->next()) != stopPtT) {
            const SkOpSegment* opp = ptT->segment();
            opp->resetDebugVisited();
        }
    } while (!span->final() && (span = span->upCast()->next()));
}
#endif

#if DEBUG_COIN
// commented-out lines keep this in sync with missingCoincidence()
// look for pairs of undetected coincident curves
// assumes that segments going in have visited flag clear
// Even though pairs of curves correct detect coincident runs, a run may be missed
// if the coincidence is a product of multiple intersections. For instance, given
// curves A, B, and C:
// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
// the end of C that the intersection is replaced with the end of C.
// Even though A-B correctly do not detect an intersection at point 2,
// the resulting run from point 1 to point 2 is coincident on A and B.
void SkOpSegment::debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const {
    if (this->done()) {
        return;
    }
    const SkOpSpan* prior = nullptr;
    const SkOpSpanBase* spanBase = &fHead;
//    bool result = false;
    do {
        const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
        SkASSERT(ptT->span() == spanBase);
        while ((ptT = ptT->next()) != spanStopPtT) {
            if (ptT->deleted()) {
                continue;
            }
            const SkOpSegment* opp = ptT->span()->segment();
            if (opp->done()) {
                continue;
            }
            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
            if (!opp->debugVisited()) {
                continue;
            }
            if (spanBase == &fHead) {
                continue;
            }
            if (ptT->segment() == this) {
                continue;
            }
            const SkOpSpan* span = spanBase->upCastable();
            // FIXME?: this assumes that if the opposite segment is coincident then no more
            // coincidence needs to be detected. This may not be true.
            if (span && span->segment() != opp && span->containsCoincidence(opp)) {  // debug has additional condition since it may be called before inner duplicate points have been deleted
                continue;
            }
            if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) {  // debug has additional condition since it may be called before inner duplicate points have been deleted
                continue;
            }
            const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
            // find prior span containing opp segment
            const SkOpSegment* priorOpp = nullptr;
            const SkOpSpan* priorTest = spanBase->prev();
            while (!priorOpp && priorTest) {
                priorStopPtT = priorPtT = priorTest->ptT();
                while ((priorPtT = priorPtT->next()) != priorStopPtT) {
                    if (priorPtT->deleted()) {
                        continue;
                    }
                    const SkOpSegment* segment = priorPtT->span()->segment();
                    if (segment == opp) {
                        prior = priorTest;
                        priorOpp = opp;
                        break;
                    }
                }
                priorTest = priorTest->prev();
            }
            if (!priorOpp) {
                continue;
            }
            if (priorPtT == ptT) {
                continue;
            }
            const SkOpPtT* oppStart = prior->ptT();
            const SkOpPtT* oppEnd = spanBase->ptT();
            bool swapped = priorPtT->fT > ptT->fT;
            if (swapped) {
                using std::swap;
                swap(priorPtT, ptT);
                swap(oppStart, oppEnd);
            }
            const SkOpCoincidence* coincidence = this->globalState()->coincidence();
            const SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
            const SkOpPtT* rootPtT = ptT->span()->ptT();
            const SkOpPtT* rootOppStart = oppStart->span()->ptT();
            const SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
            if (coincidence->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
                goto swapBack;
            }
            if (testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
            // mark coincidence
#if DEBUG_COINCIDENCE_VERBOSE
//                 SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
//                         rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
//                         rootOppEnd->debugID());
#endif
                log->record(SkPathOpsDebug::kMissingCoin_Glitch, priorPtT, ptT, oppStart, oppEnd);
                //   coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
                // }
#if DEBUG_COINCIDENCE
//                SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
#endif
                // result = true;
            }
    swapBack:
            if (swapped) {
                using std::swap;
                swap(priorPtT, ptT);
            }
        }
    } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
    DebugClearVisited(&fHead);
    return;
}

// commented-out lines keep this in sync with moveMultiples()
// if a span has more than one intersection, merge the other segments' span as needed
void SkOpSegment::debugMoveMultiples(SkPathOpsDebug::GlitchLog* glitches) const {
    debugValidate();
    const SkOpSpanBase* test = &fHead;
    do {
        int addCount = test->spanAddsCount();
//        SkASSERT(addCount >= 1);
        if (addCount <= 1) {
            continue;
        }
        const SkOpPtT* startPtT = test->ptT();
        const SkOpPtT* testPtT = startPtT;
        do {  // iterate through all spans associated with start
            const SkOpSpanBase* oppSpan = testPtT->span();
            if (oppSpan->spanAddsCount() == addCount) {
                continue;
            }
            if (oppSpan->deleted()) {
                continue;
            }
            const SkOpSegment* oppSegment = oppSpan->segment();
            if (oppSegment == this) {
                continue;
            }
            // find range of spans to consider merging
            const SkOpSpanBase* oppPrev = oppSpan;
            const SkOpSpanBase* oppFirst = oppSpan;
            while ((oppPrev = oppPrev->prev())) {
                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
                    break;
                }
                if (oppPrev->spanAddsCount() == addCount) {
                    continue;
                }
                if (oppPrev->deleted()) {
                    continue;
                }
                oppFirst = oppPrev;
            }
            const SkOpSpanBase* oppNext = oppSpan;
            const SkOpSpanBase* oppLast = oppSpan;
            while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
                    break;
                }
                if (oppNext->spanAddsCount() == addCount) {
                    continue;
                }
                if (oppNext->deleted()) {
                    continue;
                }
                oppLast = oppNext;
            }
            if (oppFirst == oppLast) {
                continue;
            }
            const SkOpSpanBase* oppTest = oppFirst;
            do {
                if (oppTest == oppSpan) {
                    continue;
                }
                // check to see if the candidate meets specific criteria:
                // it contains spans of segments in test's loop but not including 'this'
                const SkOpPtT* oppStartPtT = oppTest->ptT();
                const SkOpPtT* oppPtT = oppStartPtT;
                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
                    const SkOpSegment* oppPtTSegment = oppPtT->segment();
                    if (oppPtTSegment == this) {
                        goto tryNextSpan;
                    }
                    const SkOpPtT* matchPtT = startPtT;
                    do {
                        if (matchPtT->segment() == oppPtTSegment) {
                            goto foundMatch;
                        }
                    } while ((matchPtT = matchPtT->next()) != startPtT);
                    goto tryNextSpan;
            foundMatch:  // merge oppTest and oppSpan
                    oppSegment->debugValidate();
                    oppTest->debugMergeMatches(glitches, oppSpan);
                    oppTest->debugAddOpp(glitches, oppSpan);
                    oppSegment->debugValidate();
                    goto checkNextSpan;
                }
        tryNextSpan:
                ;
            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
        } while ((testPtT = testPtT->next()) != startPtT);
checkNextSpan:
        ;
    } while ((test = test->final() ? nullptr : test->upCast()->next()));
   debugValidate();
   return;
}

// commented-out lines keep this in sync with moveNearby()
// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
void SkOpSegment::debugMoveNearby(SkPathOpsDebug::GlitchLog* glitches) const {
    debugValidate();
    // release undeleted spans pointing to this seg that are linked to the primary span
    const SkOpSpanBase* spanBase = &fHead;
    do {
        const SkOpPtT* ptT = spanBase->ptT();
        const SkOpPtT* headPtT = ptT;
        while ((ptT = ptT->next()) != headPtT) {
            const SkOpSpanBase* test = ptT->span();
            if (ptT->segment() == this && !ptT->deleted() && test != spanBase
                    && test->ptT() == ptT) {
                if (test->final()) {
                    if (spanBase == &fHead) {
                        glitches->record(SkPathOpsDebug::kMoveNearbyClearAll_Glitch, this);
//                        return;
                    }
                    glitches->record(SkPathOpsDebug::kMoveNearbyReleaseFinal_Glitch, spanBase, ptT);
                } else if (test->prev()) {
                    glitches->record(SkPathOpsDebug::kMoveNearbyRelease_Glitch, test, headPtT);
                }
//                break;
            }
        }
        spanBase = spanBase->upCast()->next();
    } while (!spanBase->final());

    // This loop looks for adjacent spans which are near by
    spanBase = &fHead;
    do {  // iterate through all spans associated with start
        const SkOpSpanBase* test = spanBase->upCast()->next();
        bool found;
        if (!this->spansNearby(spanBase, test, &found)) {
            glitches->record(SkPathOpsDebug::kMoveNearbyMergeFinal_Glitch, test);
        }
        if (found) {
            if (test->final()) {
                if (spanBase->prev()) {
                    glitches->record(SkPathOpsDebug::kMoveNearbyMergeFinal_Glitch, test);
                } else {
                    glitches->record(SkPathOpsDebug::kMoveNearbyClearAll2_Glitch, this);
                    // return
                }
            } else {
                glitches->record(SkPathOpsDebug::kMoveNearbyMerge_Glitch, spanBase);
            }
        }
        spanBase = test;
    } while (!spanBase->final());
    debugValidate();
}
#endif

void SkOpSegment::debugReset() {
    this->init(this->fPts, this->fWeight, this->contour(), this->verb());
}

#if DEBUG_COINCIDENCE_ORDER
void SkOpSegment::debugSetCoinT(int index, SkScalar t) const {
    if (fDebugBaseMax < 0 || fDebugBaseIndex == index) {
        fDebugBaseIndex = index;
        fDebugBaseMin = std::min(t, fDebugBaseMin);
        fDebugBaseMax = std::max(t, fDebugBaseMax);
        return;
    }
    SkASSERT(fDebugBaseMin >= t || t >= fDebugBaseMax);
    if (fDebugLastMax < 0 || fDebugLastIndex == index) {
        fDebugLastIndex = index;
        fDebugLastMin = std::min(t, fDebugLastMin);
        fDebugLastMax = std::max(t, fDebugLastMax);
        return;
    }
    SkASSERT(fDebugLastMin >= t || t >= fDebugLastMax);
    SkASSERT((t - fDebugBaseMin > 0) == (fDebugLastMin - fDebugBaseMin > 0));
}
#endif

#if DEBUG_ACTIVE_SPANS
void SkOpSegment::debugShowActiveSpans(SkString* str) const {
    debugValidate();
    if (done()) {
        return;
    }
    int lastId = -1;
    double lastT = -1;
    const SkOpSpan* span = &fHead;
    do {
        if (span->done()) {
            continue;
        }
        if (lastId == this->debugID() && lastT == span->t()) {
            continue;
        }
        lastId = this->debugID();
        lastT = span->t();
        str->appendf("%s id=%d", __FUNCTION__, this->debugID());
        // since endpoints may have be adjusted, show actual computed curves
        SkDCurve curvePart;
        this->subDivide(span, span->next(), &curvePart);
        const SkDPoint* pts = curvePart.fCubic.fPts;
        str->appendf(" (%1.9g,%1.9g", pts[0].fX, pts[0].fY);
        for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
            str->appendf(" %1.9g,%1.9g", pts[vIndex].fX, pts[vIndex].fY);
        }
        if (SkPath::kConic_Verb == fVerb) {
            str->appendf(" %1.9gf", curvePart.fConic.fWeight);
        }
        str->appendf(") t=%1.9g tEnd=%1.9g", span->t(), span->next()->t());
        if (span->windSum() == SK_MinS32) {
            str->appendf(" windSum=?");
        } else {
            str->appendf(" windSum=%d", span->windSum());
        }
        if (span->oppValue() && span->oppSum() == SK_MinS32) {
            str->appendf(" oppSum=?");
        } else if (span->oppValue() || span->oppSum() != SK_MinS32) {
            str->appendf(" oppSum=%d", span->oppSum());
        }
        str->appendf(" windValue=%d", span->windValue());
        if (span->oppValue() || span->oppSum() != SK_MinS32) {
            str->appendf(" oppValue=%d", span->oppValue());
        }
        str->appendf("\n");
   } while ((span = span->next()->upCastable()));
}
#endif

#if DEBUG_MARK_DONE
void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
    const SkPoint& pt = span->ptT()->fPt;
    SkDebugf("%s id=%d", fun, this->debugID());
    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
    }
    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
    if (winding == SK_MinS32) {
        SkDebugf("?");
    } else {
        SkDebugf("%d", winding);
    }
    SkDebugf(" windSum=");
    if (span->windSum() == SK_MinS32) {
        SkDebugf("?");
    } else {
        SkDebugf("%d", span->windSum());
    }
    SkDebugf(" windValue=%d\n", span->windValue());
}

void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
                                      int oppWinding) {
    const SkPoint& pt = span->ptT()->fPt;
    SkDebugf("%s id=%d", fun, this->debugID());
    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
    }
    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
    if (winding == SK_MinS32) {
        SkDebugf("?");
    } else {
        SkDebugf("%d", winding);
    }
    SkDebugf(" newOppSum=");
    if (oppWinding == SK_MinS32) {
        SkDebugf("?");
    } else {
        SkDebugf("%d", oppWinding);
    }
    SkDebugf(" oppSum=");
    if (span->oppSum() == SK_MinS32) {
        SkDebugf("?");
    } else {
        SkDebugf("%d", span->oppSum());
    }
    SkDebugf(" windSum=");
    if (span->windSum() == SK_MinS32) {
        SkDebugf("?");
    } else {
        SkDebugf("%d", span->windSum());
    }
    SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
}

#endif

// loop looking for a pair of angle parts that are too close to be sorted
/* This is called after other more simple intersection and angle sorting tests have been exhausted.
   This should be rarely called -- the test below is thorough and time consuming.
   This checks the distance between start points; the distance between
*/
#if DEBUG_ANGLE
void SkOpAngle::debugCheckNearCoincidence() const {
    const SkOpAngle* test = this;
    do {
        const SkOpSegment* testSegment = test->segment();
        double testStartT = test->start()->t();
        SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
        double testEndT = test->end()->t();
        SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
        double testLenSq = testStartPt.distanceSquared(testEndPt);
        SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
        double testMidT = (testStartT + testEndT) / 2;
        const SkOpAngle* next = test;
        while ((next = next->fNext) != this) {
            SkOpSegment* nextSegment = next->segment();
            double testMidDistSq = testSegment->distSq(testMidT, next);
            double testEndDistSq = testSegment->distSq(testEndT, next);
            double nextStartT = next->start()->t();
            SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
            double distSq = testStartPt.distanceSquared(nextStartPt);
            double nextEndT = next->end()->t();
            double nextMidT = (nextStartT + nextEndT) / 2;
            double nextMidDistSq = nextSegment->distSq(nextMidT, test);
            double nextEndDistSq = nextSegment->distSq(nextEndT, test);
            SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
                    testSegment->debugID(), nextSegment->debugID());
            SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
            SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
            SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
            SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
            SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
            double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
            SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
            SkDebugf("\n");
        }
        test = test->fNext;
    } while (test->fNext != this);
}
#endif

#if DEBUG_ANGLE
SkString SkOpAngle::debugPart() const {
    SkString result;
    switch (this->segment()->verb()) {
        case SkPath::kLine_Verb:
            result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fPart.fCurve),
                    this->segment()->debugID());
            break;
        case SkPath::kQuad_Verb:
            result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fPart.fCurve),
                    this->segment()->debugID());
            break;
        case SkPath::kConic_Verb:
            result.printf(CONIC_DEBUG_STR " id=%d",
                    CONIC_DEBUG_DATA(fPart.fCurve, fPart.fCurve.fConic.fWeight),
                    this->segment()->debugID());
            break;
        case SkPath::kCubic_Verb:
            result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fPart.fCurve),
                    this->segment()->debugID());
            break;
        default:
            SkASSERT(0);
    }
    return result;
}
#endif

#if DEBUG_SORT
void SkOpAngle::debugLoop() const {
    const SkOpAngle* first = this;
    const SkOpAngle* next = this;
    do {
        next->dumpOne(true);
        SkDebugf("\n");
        next = next->fNext;
    } while (next && next != first);
    next = first;
    do {
        next->debugValidate();
        next = next->fNext;
    } while (next && next != first);
}
#endif

void SkOpAngle::debugValidate() const {
#if DEBUG_COINCIDENCE
    if (this->globalState()->debugCheckHealth()) {
        return;
    }
#endif
#if DEBUG_VALIDATE
    const SkOpAngle* first = this;
    const SkOpAngle* next = this;
    int wind = 0;
    int opp = 0;
    int lastXor = -1;
    int lastOppXor = -1;
    do {
        if (next->unorderable()) {
            return;
        }
        const SkOpSpan* minSpan = next->start()->starter(next->end());
        if (minSpan->windValue() == SK_MinS32) {
            return;
        }
        bool op = next->segment()->operand();
        bool isXor = next->segment()->isXor();
        bool oppXor = next->segment()->oppXor();
        SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
        SkASSERT(!DEBUG_LIMIT_WIND_SUM
                || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
        bool useXor = op ? oppXor : isXor;
        SkASSERT(lastXor == -1 || lastXor == (int) useXor);
        lastXor = (int) useXor;
        wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue());
        if (useXor) {
            wind &= 1;
        }
        useXor = op ? isXor : oppXor;
        SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
        lastOppXor = (int) useXor;
        opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue());
        if (useXor) {
            opp &= 1;
        }
        next = next->fNext;
    } while (next && next != first);
    SkASSERT(wind == 0 || !SkPathOpsDebug::gRunFail);
    SkASSERT(opp == 0 || !SkPathOpsDebug::gRunFail);
#endif
}

void SkOpAngle::debugValidateNext() const {
#if !FORCE_RELEASE
    const SkOpAngle* first = this;
    const SkOpAngle* next = first;
    SkTDArray<const SkOpAngle*> angles;
    do {
//        SkASSERT_RELEASE(next->fSegment->debugContains(next));
        angles.push_back(next);
        next = next->next();
        if (next == first) {
            break;
        }
        SkASSERT_RELEASE(!angles.contains(next));
        if (!next) {
            return;
        }
    } while (true);
#endif
}

#ifdef SK_DEBUG
void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
        const SkOpGlobalState* debugState) const {
    SkASSERT(coinPtTEnd()->span() == over || !SkOpGlobalState::DebugRunFail());
    SkASSERT(oppPtTEnd()->span() == outer || !SkOpGlobalState::DebugRunFail());
}
#endif

#if DEBUG_COIN
// sets the span's end to the ptT referenced by the previous-next
void SkCoincidentSpans::debugCorrectOneEnd(SkPathOpsDebug::GlitchLog* log,
        const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
        void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) const ) const {
    const SkOpPtT* origPtT = (this->*getEnd)();
    const SkOpSpanBase* origSpan = origPtT->span();
    const SkOpSpan* prev = origSpan->prev();
    const SkOpPtT* testPtT = prev ? prev->next()->ptT()
            : origSpan->upCast()->next()->prev()->ptT();
    if (origPtT != testPtT) {
        log->record(SkPathOpsDebug::kCorrectEnd_Glitch, this, origPtT, testPtT);
    }
}


/* Commented-out lines keep this in sync with correctEnds */
// FIXME: member pointers have fallen out of favor and can be replaced with
// an alternative approach.
// makes all span ends agree with the segment's spans that define them
void SkCoincidentSpans::debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const {
    this->debugCorrectOneEnd(log, &SkCoincidentSpans::coinPtTStart, nullptr);
    this->debugCorrectOneEnd(log, &SkCoincidentSpans::coinPtTEnd, nullptr);
    this->debugCorrectOneEnd(log, &SkCoincidentSpans::oppPtTStart, nullptr);
    this->debugCorrectOneEnd(log, &SkCoincidentSpans::oppPtTEnd, nullptr);
}

/* Commented-out lines keep this in sync with expand */
// expand the range by checking adjacent spans for coincidence
bool SkCoincidentSpans::debugExpand(SkPathOpsDebug::GlitchLog* log) const {
    bool expanded = false;
    const SkOpSegment* segment = coinPtTStart()->segment();
    const SkOpSegment* oppSegment = oppPtTStart()->segment();
    do {
        const SkOpSpan* start = coinPtTStart()->span()->upCast();
        const SkOpSpan* prev = start->prev();
        const SkOpPtT* oppPtT;
        if (!prev || !(oppPtT = prev->contains(oppSegment))) {
            break;
        }
        double midT = (prev->t() + start->t()) / 2;
        if (!segment->isClose(midT, oppSegment)) {
            break;
        }
        if (log) log->record(SkPathOpsDebug::kExpandCoin_Glitch, this, prev->ptT(), oppPtT);
        expanded = true;
    } while (false);  // actual continues while expansion is possible
    do {
        const SkOpSpanBase* end = coinPtTEnd()->span();
        SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
        if (next && next->deleted()) {
            break;
        }
        const SkOpPtT* oppPtT;
        if (!next || !(oppPtT = next->contains(oppSegment))) {
            break;
        }
        double midT = (end->t() + next->t()) / 2;
        if (!segment->isClose(midT, oppSegment)) {
            break;
        }
        if (log) log->record(SkPathOpsDebug::kExpandCoin_Glitch, this, next->ptT(), oppPtT);
        expanded = true;
    } while (false);  // actual continues while expansion is possible
    return expanded;
}

// description below
void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log, const SkOpSpan* base, const SkOpSpanBase* testSpan) const {
    const SkOpPtT* testPtT = testSpan->ptT();
    const SkOpPtT* stopPtT = testPtT;
    const SkOpSegment* baseSeg = base->segment();
    while ((testPtT = testPtT->next()) != stopPtT) {
        const SkOpSegment* testSeg = testPtT->segment();
        if (testPtT->deleted()) {
            continue;
        }
        if (testSeg == baseSeg) {
            continue;
        }
        if (testPtT->span()->ptT() != testPtT) {
            continue;
        }
        if (this->contains(baseSeg, testSeg, testPtT->fT)) {
            continue;
        }
        // intersect perp with base->ptT() with testPtT->segment()
        SkDVector dxdy = baseSeg->dSlopeAtT(base->t());
        const SkPoint& pt = base->pt();
        SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}};
        SkIntersections i;
        (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i);
        for (int index = 0; index < i.used(); ++index) {
            double t = i[0][index];
            if (!between(0, t, 1)) {
                continue;
            }
            SkDPoint oppPt = i.pt(index);
            if (!oppPt.approximatelyEqual(pt)) {
                continue;
            }
            SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
            SkOpPtT* oppStart = writableSeg->addT(t);
            if (oppStart == testPtT) {
                continue;
            }
            SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
            oppStart->span()->addOpp(writableBase);
            if (oppStart->deleted()) {
                continue;
            }
            SkOpSegment* coinSeg = base->segment();
            SkOpSegment* oppSeg = oppStart->segment();
            double coinTs, coinTe, oppTs, oppTe;
            if (Ordered(coinSeg, oppSeg)) {
                coinTs = base->t();
                coinTe = testSpan->t();
                oppTs = oppStart->fT;
                oppTe = testPtT->fT;
            } else {
                using std::swap;
                swap(coinSeg, oppSeg);
                coinTs = oppStart->fT;
                coinTe = testPtT->fT;
                oppTs = base->t();
                oppTe = testSpan->t();
            }
            if (coinTs > coinTe) {
                using std::swap;
                swap(coinTs, coinTe);
                swap(oppTs, oppTe);
            }
            bool added;
            this->debugAddOrOverlap(log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added);
        }
    }
    return;
}

// description below
void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log, const SkOpPtT* ptT) const {
    FAIL_IF_COIN(!ptT->span()->upCastable(), ptT->span());
    const SkOpSpan* base = ptT->span()->upCast();
    const SkOpSpan* prev = base->prev();
    FAIL_IF_COIN(!prev, ptT->span());
    if (!prev->isCanceled()) {
        this->debugAddEndMovedSpans(log, base, base->prev());
    }
    if (!base->isCanceled()) {
        this->debugAddEndMovedSpans(log, base, base->next());
    }
    return;
}

/*  If A is coincident with B and B includes an endpoint, and A's matching point
    is not the endpoint (i.e., there's an implied line connecting B-end and A)
    then assume that the same implied line may intersect another curve close to B.
    Since we only care about coincidence that was undetected, look at the
    ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but
    next door) and see if the A matching point is close enough to form another
    coincident pair. If so, check for a new coincident span between B-end/A ptT loop
    and the adjacent ptT loop.
*/
void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log) const {
    const SkCoincidentSpans* span = fHead;
    if (!span) {
        return;
    }
//    fTop = span;
//    fHead = nullptr;
    do {
        if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
            FAIL_IF_COIN(1 == span->coinPtTStart()->fT, span);
            bool onEnd = span->coinPtTStart()->fT == 0;
            bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
            if (onEnd) {
                if (!oOnEnd) {  // if both are on end, any nearby intersect was already found
                    this->debugAddEndMovedSpans(log, span->oppPtTStart());
                }
            } else if (oOnEnd) {
                this->debugAddEndMovedSpans(log, span->coinPtTStart());
            }
        }
        if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) {
            bool onEnd = span->coinPtTEnd()->fT == 1;
            bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT);
            if (onEnd) {
                if (!oOnEnd) {
                    this->debugAddEndMovedSpans(log, span->oppPtTEnd());
                }
            } else if (oOnEnd) {
                this->debugAddEndMovedSpans(log, span->coinPtTEnd());
            }
        }
    } while ((span = span->next()));
//    this->restoreHead();
    return;
}

/* Commented-out lines keep this in sync with addExpanded */
// for each coincident pair, match the spans
// if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
void SkOpCoincidence::debugAddExpanded(SkPathOpsDebug::GlitchLog* log) const {
//    DEBUG_SET_PHASE();
    const SkCoincidentSpans* coin = this->fHead;
    if (!coin) {
        return;
    }
    do {
        const SkOpPtT* startPtT = coin->coinPtTStart();
        const SkOpPtT* oStartPtT = coin->oppPtTStart();
        double priorT = startPtT->fT;
        double oPriorT = oStartPtT->fT;
        FAIL_IF_COIN(!startPtT->contains(oStartPtT), coin);
        SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
        const SkOpSpanBase* start = startPtT->span();
        const SkOpSpanBase* oStart = oStartPtT->span();
        const SkOpSpanBase* end = coin->coinPtTEnd()->span();
        const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
        FAIL_IF_COIN(oEnd->deleted(), coin);
        FAIL_IF_COIN(!start->upCastable(), coin);
        const SkOpSpanBase* test = start->upCast()->next();
        FAIL_IF_COIN(!coin->flipped() && !oStart->upCastable(), coin);
        const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
        FAIL_IF_COIN(!oTest, coin);
        const SkOpSegment* seg = start->segment();
        const SkOpSegment* oSeg = oStart->segment();
        while (test != end || oTest != oEnd) {
            const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
            const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
            if (!containedOpp || !containedThis) {
                // choose the ends, or the first common pt-t list shared by both
                double nextT, oNextT;
                if (containedOpp) {
                    nextT = test->t();
                    oNextT = containedOpp->fT;
                } else if (containedThis) {
                    nextT = containedThis->fT;
                    oNextT = oTest->t();
                } else {
                    // iterate through until a pt-t list found that contains the other
                    const SkOpSpanBase* walk = test;
                    const SkOpPtT* walkOpp;
                    do {
                        FAIL_IF_COIN(!walk->upCastable(), coin);
                        walk = walk->upCast()->next();
                    } while (!(walkOpp = walk->ptT()->contains(oSeg))
                            && walk != coin->coinPtTEnd()->span());
                    FAIL_IF_COIN(!walkOpp, coin);
                    nextT = walk->t();
                    oNextT = walkOpp->fT;
                }
                // use t ranges to guess which one is missing
                double startRange = nextT - priorT;
                FAIL_IF_COIN(!startRange, coin);
                double startPart = (test->t() - priorT) / startRange;
                double oStartRange = oNextT - oPriorT;
                FAIL_IF_COIN(!oStartRange, coin);
                double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
                FAIL_IF_COIN(startPart == oStartPart, coin);
                bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
                        : !!containedThis;
                bool startOver = false;
                addToOpp ? log->record(SkPathOpsDebug::kAddExpandedCoin_Glitch,
                        oPriorT + oStartRange * startPart, test)
                        : log->record(SkPathOpsDebug::kAddExpandedCoin_Glitch,
                        priorT + startRange * oStartPart, oTest);
         //       FAIL_IF_COIN(!success, coin);
                if (startOver) {
                    test = start;
                    oTest = oStart;
                }
                end = coin->coinPtTEnd()->span();
                oEnd = coin->oppPtTEnd()->span();
            }
            if (test != end) {
                FAIL_IF_COIN(!test->upCastable(), coin);
                priorT = test->t();
                test = test->upCast()->next();
            }
            if (oTest != oEnd) {
                oPriorT = oTest->t();
                oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
                FAIL_IF_COIN(!oTest, coin);
            }
        }
    } while ((coin = coin->next()));
    return;
}

/* Commented-out lines keep this in sync addIfMissing() */
// note that over1s, over1e, over2s, over2e are ordered
void SkOpCoincidence::debugAddIfMissing(SkPathOpsDebug::GlitchLog* log, const SkOpPtT* over1s, const SkOpPtT* over2s,
        double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added,
        const SkOpPtT* over1e, const SkOpPtT* over2e) const {
    SkASSERT(tStart < tEnd);
    SkASSERT(over1s->fT < over1e->fT);
    SkASSERT(between(over1s->fT, tStart, over1e->fT));
    SkASSERT(between(over1s->fT, tEnd, over1e->fT));
    SkASSERT(over2s->fT < over2e->fT);
    SkASSERT(between(over2s->fT, tStart, over2e->fT));
    SkASSERT(between(over2s->fT, tEnd, over2e->fT));
    SkASSERT(over1s->segment() == over1e->segment());
    SkASSERT(over2s->segment() == over2e->segment());
    SkASSERT(over1s->segment() == over2s->segment());
    SkASSERT(over1s->segment() != coinSeg);
    SkASSERT(over1s->segment() != oppSeg);
    SkASSERT(coinSeg != oppSeg);
    double coinTs, coinTe, oppTs, oppTe;
    coinTs = TRange(over1s, tStart, coinSeg  SkDEBUGPARAMS(over1e));
    coinTe = TRange(over1s, tEnd, coinSeg  SkDEBUGPARAMS(over1e));
    SkOpSpanBase::Collapsed result = coinSeg->collapsed(coinTs, coinTe);
    if (SkOpSpanBase::Collapsed::kNo != result) {
        return log->record(SkPathOpsDebug::kAddIfCollapsed_Glitch, coinSeg);
    }
    oppTs = TRange(over2s, tStart, oppSeg  SkDEBUGPARAMS(over2e));
    oppTe = TRange(over2s, tEnd, oppSeg  SkDEBUGPARAMS(over2e));
    result = oppSeg->collapsed(oppTs, oppTe);
    if (SkOpSpanBase::Collapsed::kNo != result) {
        return log->record(SkPathOpsDebug::kAddIfCollapsed_Glitch, oppSeg);
    }
    if (coinTs > coinTe) {
        using std::swap;
        swap(coinTs, coinTe);
--> --------------------

--> maximum size reached

--> --------------------