add pathops debugging

Pathops has many points of failure, most of which
are triggered by extreme data generated by fuzzers.
It's difficult to figure out which failure point
was triggered when the operation gives up.

Add instrumentation so that the failure can
be debugged when the data is well-behaved.

Also, add a check that looks for a sequence of
coincident points on multiple edges that are out
of order when compared to each other.

TBR=reed@google.com
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2274803003

Review-Url: https://codereview.chromium.org/2274803003

7 files changed, 141 insertions, 69 deletions

diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp
index 84c4003968..7717d06a80 100755
--- a/src/pathops/SkOpCoincidence.cpp
+++ b/src/pathops/SkOpCoincidence.cpp
@@ -8,12 +8,6 @@
 #include "SkOpSegment.h"
 #include "SkPathOpsTSect.h"
 
-#if DEBUG_COINCIDENCE
-#define FAIL_IF(cond) SkASSERT(!(cond))
-#else
-#define FAIL_IF(cond) do { if (cond) return false; } while (false)
-#endif
-
 // returns true if coincident span's start and end are the same
 bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const {
     return (fCoinPtTStart == test && fCoinPtTEnd->contains(test))
@@ -330,7 +324,8 @@ bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase*
                 SkTSwap(coinTs, coinTe);
                 SkTSwap(oppTs, oppTe);
             }
-            if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe)) {
+            if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
+                    SkDEBUGPARAMS(true) /* do assert if addOrOverlap fails */ )) {
                 return false;
             }
         }
@@ -340,14 +335,10 @@ bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase*
 
 // description below
 bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) {
-    if (!ptT->span()->upCastable()) {
-        return false;
-    }
+    FAIL_IF(!ptT->span()->upCastable());
     const SkOpSpan* base = ptT->span()->upCast();
     const SkOpSpan* prev = base->prev();
-    if (!prev) {
-        return false;
-    }
+    FAIL_IF(!prev);
     if (!prev->isCanceled()) {
         if (!this->addEndMovedSpans(base, base->prev())) {
             return false;
@@ -379,9 +370,7 @@ bool SkOpCoincidence::addEndMovedSpans() {
     fHead = nullptr;
     do {
         if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
-            if (1 == span->coinPtTStart()->fT) {
-                return false;
-            }
+            FAIL_IF(1 == span->coinPtTStart()->fT);
             bool onEnd = span->coinPtTStart()->fT == 0;
             bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
             if (onEnd) {
@@ -608,16 +597,18 @@ bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
     if (coinSeg == oppSeg) {
         return false;
     }
-    return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe);
+    return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
+        SkDEBUGPARAMS(false) /* don't assert if addOrOverlap fails */ );
 }
 
 /* Please keep this in sync with debugAddOrOverlap() */
+// If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
+// If this is called by AddIfMissing(), a returned false indicates there was nothing to add
 bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
-        double coinTs, double coinTe, double oppTs, double oppTe) {
+        double coinTs, double coinTe, double oppTs, double oppTe
+        SkDEBUGPARAMS(bool callerAborts)) {
     SkTDArray<SkCoincidentSpans*> overlaps;
-    if (!fTop) {
-        return false;
-    }
+    RETURN_FALSE_IF(callerAborts, !fTop);
     if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
         return false;
     }
@@ -650,43 +641,29 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
     }
     const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
     const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
-    if (overlap && cs && ce && overlap->contains(cs, ce)) {
-        return false;
-    }
-    if (cs == ce && cs) {
-        return false;
-    }
+    RETURN_FALSE_IF(callerAborts, overlap && cs && ce && overlap->contains(cs, ce));
+    RETURN_FALSE_IF(callerAborts, cs == ce && cs);
     const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
     const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
-    if (overlap && os && oe && overlap->contains(os, oe)) {
-        return false;
-    }
+    RETURN_FALSE_IF(callerAborts, overlap && os && oe && overlap->contains(os, oe));
     SkASSERT(!cs || !cs->deleted());
     SkASSERT(!os || !os->deleted());
     SkASSERT(!ce || !ce->deleted());
     SkASSERT(!oe || !oe->deleted());
     const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
     const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
-    if (csExisting && csExisting == ceExisting) {
-        return false;
-    }
-    if (csExisting && (csExisting == ce || csExisting->contains(ceExisting ? ceExisting : ce))) {
-        return false;
-    }
-    if (ceExisting && (ceExisting == cs || ceExisting->contains(csExisting ? csExisting : cs))) {
-        return false;
-    }
+    RETURN_FALSE_IF(callerAborts, csExisting && csExisting == ceExisting);
+    RETURN_FALSE_IF(callerAborts, csExisting && (csExisting == ce ||
+            csExisting->contains(ceExisting ? ceExisting : ce)));
+    RETURN_FALSE_IF(callerAborts, ceExisting && (ceExisting == cs ||
+            ceExisting->contains(csExisting ? csExisting : cs)));
     const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
     const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
-    if (osExisting && osExisting == oeExisting) {
-        return false;
-    }
-    if (osExisting && (osExisting == oe || osExisting->contains(oeExisting ? oeExisting : oe))) {
-        return false;
-    }
-    if (oeExisting && (oeExisting == os || oeExisting->contains(osExisting ? osExisting : os))) {
-        return false;
-    }
+    RETURN_FALSE_IF(callerAborts, osExisting && osExisting == oeExisting);
+    RETURN_FALSE_IF(callerAborts, osExisting && (osExisting == oe ||
+            osExisting->contains(oeExisting ? oeExisting : oe)));
+    RETURN_FALSE_IF(callerAborts, oeExisting && (oeExisting == os ||
+            oeExisting->contains(osExisting ? osExisting : os)));
     // extra line in debug code
     this->debugValidate();
     if (!cs || !os) {
@@ -694,15 +671,11 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
             : coinSeg->addT(coinTs, nullptr);
         SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os)
             : oppSeg->addT(oppTs, nullptr);
-        if (!csWritable || !osWritable) {
-            return false;
-        }
+        RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable);
         csWritable->span()->addOppAndMerge(osWritable->span());
         cs = csWritable;
         os = osWritable;
-        if ((ce && ce->deleted()) || (oe && oe->deleted())) {
-            return false;
-        }
+        RETURN_FALSE_IF(callerAborts, (ce && ce->deleted()) || (oe && oe->deleted()));
     }
     if (!ce || !oe) {
         SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce)
@@ -714,12 +687,11 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
         oe = oeWritable;
     }
     this->debugValidate();
-    if (cs->deleted() || os->deleted() || ce->deleted() || oe->deleted()) {
-        return false;
-    }
-    if (cs->contains(ce) || os->contains(oe)) {
-        return false;
-    }
+    RETURN_FALSE_IF(callerAborts, cs->deleted());
+    RETURN_FALSE_IF(callerAborts, os->deleted());
+    RETURN_FALSE_IF(callerAborts, ce->deleted());
+    RETURN_FALSE_IF(callerAborts, oe->deleted());
+    RETURN_FALSE_IF(callerAborts, cs->contains(ce) || os->contains(oe));
     bool result = true;
     if (overlap) {
         if (overlap->coinPtTStart()->segment() == coinSeg) {
diff --git a/src/pathops/SkOpCoincidence.h b/src/pathops/SkOpCoincidence.h
index cd184e353f..436fa82527 100644
--- a/src/pathops/SkOpCoincidence.h
+++ b/src/pathops/SkOpCoincidence.h
@@ -264,7 +264,8 @@ private:
     }
 
     bool addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
-                      double coinTs, double coinTe, double oppTs, double oppTe);
+                      double coinTs, double coinTe, double oppTs, double oppTe
+                      SkDEBUGPARAMS(bool callerAborts));
     bool addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
                     const SkOpSegment* seg2, const SkOpSegment* seg2o,
                     const SkOpPtT* overS, const SkOpPtT* overE);
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 20f0013230..87023261c5 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -9,8 +9,6 @@
 #include "SkOpSegment.h"
 #include "SkPathWriter.h"
 
-#define FAIL_IF(cond) do { if (cond) return false; } while (false)
-
 /*
 After computing raw intersections, post process all segments to:
 - find small collections of points that can be collapsed to a single point
@@ -163,10 +161,7 @@ bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sum
 
 bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
         SkPathWriter* path) const {
-    if (start->starter(end)->alreadyAdded()) {
-        SkDEBUGF(("same curve added twice aborted pathops\n"));
-        return false;
-    }
+    FAIL_IF(start->starter(end)->alreadyAdded());
     SkOpCurve edge;
     const SkPoint* ePtr;
     SkScalar eWeight;
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 61a9e45ac8..312312a153 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -166,8 +166,13 @@ public:
     const SkOpSpanBase* debugSpan(int id) const;
     void debugValidate() const;
 
+#if DEBUG_COINCIDENCE_ORDER
+    void debugResetCoinT() const; 
+    void debugSetCoinT(int, SkScalar ) const; 
+#endif
+
 #if DEBUG_COINCIDENCE
-    static void SkOpSegment::DebugClearVisited(const SkOpSpanBase* span);
+    static void DebugClearVisited(const SkOpSpanBase* span);
 
     bool debugVisited() const {
         if (!fDebugVisited) {
@@ -436,6 +441,14 @@ private:
 #if DEBUG_COINCIDENCE
     mutable bool fDebugVisited;  // used by debug missing coincidence check
 #endif
+#if DEBUG_COINCIDENCE_ORDER
+    mutable int fDebugBaseIndex;
+    mutable SkScalar fDebugBaseMin;  // if > 0, the 1st t value in this seg vis-a-vis the ref seg
+    mutable SkScalar fDebugBaseMax;
+    mutable int fDebugLastIndex;
+    mutable SkScalar fDebugLastMin;  // if > 0, the last t -- next t val - base has same sign
+    mutable SkScalar fDebugLastMax;
+#endif
     SkDEBUGCODE(int fID);
 };
 
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index aff3646190..ebcc984b33 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -71,7 +71,9 @@ public:
     int debugLoopLimit(bool report) const;
     bool debugMatchID(int id) const;
     const SkOpPtT* debugPtT(int id) const;
+    void debugResetCoinT() const;
     const SkOpSegment* debugSegment(int id) const;
+    void debugSetCoinT(int ) const;
     const SkOpSpanBase* debugSpan(int id) const;
     void debugValidate() const;
 
@@ -235,7 +237,9 @@ public:
                              const SkPathOpsBounds& bounds, bool* deleted) const;
 #endif
     const SkOpPtT* debugPtT(int id) const;
+    void debugResetCoinT() const;
     const SkOpSegment* debugSegment(int id) const;
+    void debugSetCoinT(int ) const;
     const SkOpSpanBase* debugSpan(int id) const;
     const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const;
     SkOpGlobalState* globalState() const;
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 4d833a0b84..df35be0cfe 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -975,6 +975,26 @@ 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 = SkTMin(t, fDebugBaseMin);
+        fDebugBaseMax = SkTMax(t, fDebugBaseMax);
+        return;
+    } 
+    SkASSERT(fDebugBaseMin >= t || t >= fDebugBaseMax);
+    if (fDebugLastMax < 0 || fDebugLastIndex == index) {
+        fDebugLastIndex = index;
+        fDebugLastMin = SkTMin(t, fDebugLastMin);
+        fDebugLastMax = SkTMax(t, fDebugLastMax);
+        return;
+    }
+    SkASSERT(fDebugLastMin >= t || t >= fDebugLastMax);
+    SkASSERT((t - fDebugBaseMin > 0) == (fDebugLastMin - fDebugBaseMin > 0));
+}
+#endif
+
 #if DEBUG_ACTIVE_SPANS
 void SkOpSegment::debugShowActiveSpans() const {
     debugValidate();
@@ -1290,6 +1310,7 @@ bool SkCoincidentSpans::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* l
     return expanded;
 }
 
+#undef FAIL_IF
 #define FAIL_IF(cond)  do { if (cond) log->record(kAddExpandedFail_Glitch, id, coin); } while (false)
 
 /* Commented-out lines keep this in sync with addExpanded */
@@ -1976,7 +1997,31 @@ void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::Glitch
 }
 #endif
 
+#if DEBUG_COINCIDENCE_ORDER
+void SkOpSegment::debugResetCoinT() const {
+    fDebugBaseIndex = -1;
+    fDebugBaseMin = 1;
+    fDebugBaseMax = -1;
+    fDebugLastIndex = -1;
+    fDebugLastMin = 1;
+    fDebugLastMax = -1;
+}
+#endif
+
 void SkOpSegment::debugValidate() const {
+#if DEBUG_COINCIDENCE_ORDER
+    {
+        const SkOpSpanBase* span = &fHead;
+        do {
+            span->debugResetCoinT();
+        } while (!span->final() && (span = span->upCast()->next()));
+        span = &fHead;
+        int index = 0;
+        do {
+            span->debugSetCoinT(index++);
+        } while (!span->final() && (span = span->upCast()->next()));
+    }
+#endif
 #if DEBUG_COINCIDENCE
     if (this->globalState()->debugCheckHealth()) {
         return;
@@ -2127,6 +2172,28 @@ void SkOpSpanBase::debugMergeContained(const char* id, SkPathOpsDebug::GlitchLog
 }
 #endif
 
+void SkOpSpanBase::debugResetCoinT() const {
+#if DEBUG_COINCIDENCE_ORDER
+    const SkOpPtT* ptT = &fPtT;
+    do {
+        ptT->debugResetCoinT();
+        ptT = ptT->next();
+    } while (ptT != &fPtT);
+#endif
+}
+
+void SkOpSpanBase::debugSetCoinT(int index) const {
+#if DEBUG_COINCIDENCE_ORDER
+    const SkOpPtT* ptT = &fPtT;
+    do {
+        if (!ptT->deleted()) {
+            ptT->debugSetCoinT(index);
+        }
+        ptT = ptT->next();
+    } while (ptT != &fPtT);
+#endif
+}
+
 const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
     const SkOpSpanBase* end = *endPtr;
     SkASSERT(this->segment() == end->segment());
@@ -2336,6 +2403,18 @@ int SkOpPtT::debugLoopLimit(bool report) const {
     return 0;
 }
 
+void SkOpPtT::debugResetCoinT() const {
+#if DEBUG_COINCIDENCE_ORDER
+    this->segment()->debugResetCoinT(); 
+#endif
+}
+
+void SkOpPtT::debugSetCoinT(int index) const {
+#if DEBUG_COINCIDENCE_ORDER
+    this->segment()->debugSetCoinT(index, fT); 
+#endif
+}
+
 void SkOpPtT::debugValidate() const {
 #if DEBUG_COINCIDENCE
     if (this->globalState()->debugCheckHealth()) {
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index e7849ffbaf..c1b1adb707 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -49,6 +49,7 @@
 #define DEBUG_ANGLE 0
 #define DEBUG_ASSEMBLE 0
 #define DEBUG_COINCIDENCE 0
+#define DEBUG_COINCIDENCE_ORDER 0
 #define DEBUG_COINCIDENCE_VERBOSE 0
 #define DEBUG_CUBIC_BINARY_SEARCH 0
 #define DEBUG_CUBIC_SPLIT 0
@@ -67,7 +68,6 @@
 #define DEBUG_WINDING 0
 #define DEBUG_WINDING_AT_T 0
 
-
 #else
 
 #define DEBUG_ACTIVE_OP 1
@@ -78,6 +78,7 @@
 #define DEBUG_ANGLE 1
 #define DEBUG_ASSEMBLE 1
 #define DEBUG_COINCIDENCE 01
+#define DEBUG_COINCIDENCE_ORDER 0
 #define DEBUG_COINCIDENCE_VERBOSE 01
 #define DEBUG_CUBIC_BINARY_SEARCH 0
 #define DEBUG_CUBIC_SPLIT 1
@@ -155,6 +156,13 @@
 #include "SkTLS.h"
 #endif
 
+#define FAIL_IF(cond) do { bool fail = (cond); SkOPASSERT(!fail); if (fail) return false; } \
+        while (false)
+
+#define RETURN_FALSE_IF(abort, cond) \
+        do { bool fail = (cond); SkOPASSERT(!(abort) || !fail); if (fail) return false; } \
+        while (false)
+
 class SkPathOpsDebug {
 public:
     static const char* kLVerbStr[];