fix path ops fuzz buster

Mark collapsed segments as done and remove collapsed
segment references from the coincidence array.

Also add test names to global debugging.

R=fmalita@chromium.org
BUG=512592

Review URL: https://codereview.chromium.org/1250293002

14 files changed, 68 insertions, 10 deletions

diff --git a/src/pathops/SkOpBuilder.cpp b/src/pathops/SkOpBuilder.cpp
index 0d229a8c40..24a157afc5 100644
--- a/src/pathops/SkOpBuilder.cpp
+++ b/src/pathops/SkOpBuilder.cpp
@@ -44,7 +44,7 @@ void FixWinding(SkPath* path) {
     }
     SkChunkAlloc allocator(4096);
     SkOpContourHead contourHead;
-    SkOpGlobalState globalState(NULL, &contourHead);
+    SkOpGlobalState globalState(NULL, &contourHead  SkDEBUGPARAMS(NULL));
     SkOpEdgeBuilder builder(*path, &contourHead, &allocator, &globalState);
     builder.finish(&allocator);
     SkASSERT(contourHead.next());
diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp
index 58ff7f3ab9..46d06e9e0b 100755
--- a/src/pathops/SkOpCoincidence.cpp
+++ b/src/pathops/SkOpCoincidence.cpp
@@ -568,6 +568,16 @@ void SkOpCoincidence::fixAligned() {
             coin->fOppPtTEnd = coin->fOppPtTEnd->doppelganger();
         }
     } while ((coin = coin->fNext));
+    coin = fHead;
+    SkCoincidentSpans** priorPtr = &fHead;
+    do {
+        if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)
+                || coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
+            *priorPtr = coin->fNext;
+            continue;
+        }
+        priorPtr = &coin->fNext;
+    } while ((coin = coin->fNext));
 }
 
 void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) {
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index 1225416eaa..7ef68b0377 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -192,6 +192,15 @@ public:
         return fTail->pts()[SkPathOpsVerbToPoints(fTail->verb())];
     }
 
+    bool findCollapsed() {
+        SkASSERT(fCount > 0);
+        SkOpSegment* segment = &fHead;
+        do {
+            segment->findCollapsed();
+        } while ((segment = segment->next()));
+        return true;
+    }
+
     SkOpSpan* findSortableTop(SkOpContour* );
 
     SkOpSegment* first() {
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index fd8ab65acd..fc32643558 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -615,6 +615,15 @@ double SkOpSegment::distSq(double t, SkOpAngle* oppAngle) {
     return closestDistSq;
 }
 
+void SkOpSegment::findCollapsed() {
+    if (fHead.contains(&fTail)) {
+        markAllDone();
+        // move start and end to the same point
+        fHead.alignEnd(0, fHead.pt());
+        fTail.setAligned();
+    }
+}
+
 /*
  The M and S variable name parts stand for the operators.
    Mi stands for Minuend (see wiki subtraction, analogous to difference)
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 6873203b25..a3f5989824 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -182,6 +182,7 @@ public:
     void dumpPts() const;
     void dumpPtsInner() const;
 
+    void findCollapsed();
     SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
                              SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op,
                              int xorMiMask, int xorSuMask);
diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp
index f5a52099da..5c89c736fb 100755
--- a/src/pathops/SkOpSpan.cpp
+++ b/src/pathops/SkOpSpan.cpp
@@ -13,6 +13,16 @@ bool SkOpPtT::alias() const {
     return this->span()->ptT() != this;
 }
 
+bool SkOpPtT::collapsed(const SkOpPtT* check) const {
+    if (fPt != check->fPt) {
+        return false;
+    }
+    SkASSERT(this != check);
+    const SkOpSegment* segment = this->segment();
+    SkASSERT(segment == check->segment());
+    return segment->collapsed();
+}
+
 bool SkOpPtT::contains(const SkOpPtT* check) const {
     SkASSERT(this != check);
     const SkOpPtT* ptT = this;
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index ec62246c31..2a11c96dd7 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -48,6 +48,7 @@ public:
     }
 
     bool alias() const;
+    bool collapsed(const SkOpPtT* ) const;
     bool contains(const SkOpPtT* ) const;
     SkOpPtT* contains(const SkOpSegment* );
     SkOpContour* contour() const;
@@ -266,6 +267,10 @@ public:
         return fSegment;
     }
 
+    void setAligned() {
+        fAligned = true;
+    }
+
     void setChased(bool chased) {
         fChased = chased;
     }
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 4ead297f7d..c53f458d1a 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -198,7 +198,7 @@ public:
 void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
     SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
     SkOpContourHead contour;
-    SkOpGlobalState globalState(NULL, &contour);
+    SkOpGlobalState globalState(NULL, &contour  SkDEBUGPARAMS(NULL));
 #if DEBUG_SHOW_TEST_NAME
     SkDebugf("</div>\n");
 #endif
@@ -408,6 +408,13 @@ static void calcAngles(SkOpContourHead* contourList, SkChunkAlloc* allocator) {
     } while ((contour = contour->next()));
 }
 
+static void findCollapsed(SkOpContourHead* contourList) {
+    SkOpContour* contour = contourList;
+    do {
+        contour->findCollapsed();
+    } while ((contour = contour->next()));
+}
+
 static bool missingCoincidence(SkOpContourHead* contourList,
         SkOpCoincidence* coincidence, SkChunkAlloc* allocator) {
     SkOpContour* contour = contourList;
@@ -444,6 +451,7 @@ bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc
     SkOpGlobalState* globalState = contourList->globalState();
     // combine t values when multiple intersections occur on some segments but not others
     moveMultiples(contourList);
+    findCollapsed(contourList);
     // move t values and points together to eliminate small/tiny gaps
     moveNearby(contourList);
     align(contourList);  // give all span members common values
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index f76d57c83b..73bc0f42cc 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -25,7 +25,8 @@ SkOpSegment* FindUndone(SkOpContourHead* , SkOpSpanBase** startPtr,
 void FixWinding(SkPath* path);
 bool SortContourList(SkOpContourHead** , bool evenOdd, bool oppEvenOdd);
 bool HandleCoincidence(SkOpContourHead* , SkOpCoincidence* , SkChunkAlloc* );
-bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, bool expectSuccess);
+bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result,
+             bool expectSuccess  SkDEBUGPARAMS(const char* testName));
 #if DEBUG_ACTIVE_SPANS
 void DebugShowActiveSpans(SkOpContourHead* );
 #endif
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 9c09eaf8f3..12a9578dd3 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -223,12 +223,12 @@ static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) {
 #endif
 
 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result,
-        bool expectSuccess) {
+        bool expectSuccess  SkDEBUGPARAMS(const char* testName)) {
     SkChunkAlloc allocator(4096);  // FIXME: add a constant expression here, tune
     SkOpContour contour;
     SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
     SkOpCoincidence coincidence;
-    SkOpGlobalState globalState(&coincidence, contourList);
+    SkOpGlobalState globalState(&coincidence, contourList  SkDEBUGPARAMS(testName));
 #if DEBUGGING_PATHOPS_FROM_HOST
     dump_op(one, two, op);
 #endif    
@@ -304,5 +304,5 @@ bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result,
 }
 
 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
-    return OpDebug(one, two, op, result, true);
+    return OpDebug(one, two, op, result, true  SkDEBUGPARAMS(NULL));
 }
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 11b6833a73..8c07653320 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -167,7 +167,7 @@ bool Simplify(const SkPath& path, SkPath* result) {
     SkOpCoincidence coincidence;
     SkOpContour contour;
     SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
-    SkOpGlobalState globalState(&coincidence, contourList);
+    SkOpGlobalState globalState(&coincidence, contourList  SkDEBUGPARAMS(NULL));
 #if DEBUG_SORT
     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
 #endif
diff --git a/src/pathops/SkPathOpsTightBounds.cpp b/src/pathops/SkPathOpsTightBounds.cpp
index f60c291710..7eb72a9037 100644
--- a/src/pathops/SkPathOpsTightBounds.cpp
+++ b/src/pathops/SkPathOpsTightBounds.cpp
@@ -11,7 +11,7 @@ bool TightBounds(const SkPath& path, SkRect* result) {
     SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
     SkOpContour contour;
     SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
-    SkOpGlobalState globalState(NULL, contourList);
+    SkOpGlobalState globalState(NULL, contourList  SkDEBUGPARAMS(NULL));
     // turn path into list of segments
     SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState);
     if (!builder.finish(&allocator)) {
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index dcd33c9d73..c3de93a94a 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -200,13 +200,15 @@ double SkDCubeRoot(double x) {
     return result;
 }
 
-SkOpGlobalState::SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* head)
+SkOpGlobalState::SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* head
+                                 SkDEBUGPARAMS(const char* testName))
     : fCoincidence(coincidence)
     , fContourHead(head)
     , fNested(0)
     , fWindingFailed(false)
     , fAngleCoincidence(false)
     , fPhase(kIntersecting)
+    SkDEBUGPARAMS(fDebugTestName(testName))
     SkDEBUGPARAMS(fAngleID(0))
     SkDEBUGPARAMS(fContourID(0))
     SkDEBUGPARAMS(fPtTID(0))
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 9550aa1ead..2cd45a5c4d 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -28,7 +28,8 @@ class SkOpContourHead;
 
 class SkOpGlobalState {
 public:
-    SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* head);
+    SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* head
+                    SkDEBUGPARAMS(const char* testName));
 
     enum Phase {
         kIntersecting,
@@ -67,6 +68,7 @@ public:
     bool debugRunFail() const;
     const class SkOpSegment* debugSegment(int id) const;
     const class SkOpSpanBase* debugSpan(int id) const;
+    const char* debugTestName() const { return fDebugTestName; }
 #endif
 
     int nested() const {
@@ -128,6 +130,7 @@ private:
     bool fAngleCoincidence;
     Phase fPhase;
 #ifdef SK_DEBUG
+    const char* fDebugTestName;
     int fAngleID;
     int fContourID;
     int fPtTID;