fail early if coincidence can't be resolved

Bail out if a very large value causes coincidence resolution to
fail.

TBR=
BUG=415866

Author: caryclark@google.com

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

7 files changed, 39 insertions, 25 deletions

diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index 52e751bd08..27422eda5f 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -434,7 +434,7 @@ void AddSelfIntersectTs(SkOpContour* test) {
 
 // resolve any coincident pairs found while intersecting, and
 // see if coincidence is formed by clipping non-concident segments
-void CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total) {
+bool CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total) {
     int contourCount = (*contourList).count();
     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
         SkOpContour* contour = (*contourList)[cIndex];
@@ -446,10 +446,13 @@ void CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total) {
     }
     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
         SkOpContour* contour = (*contourList)[cIndex];
-        contour->calcCoincidentWinding();
+        if (!contour->calcCoincidentWinding()) {
+            return false;
+        }
     }
     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
         SkOpContour* contour = (*contourList)[cIndex];
         contour->calcPartialCoincidentWinding();
     }
+    return true;
 }
diff --git a/src/pathops/SkAddIntersections.h b/src/pathops/SkAddIntersections.h
index 94ea436b73..4c1947b635 100644
--- a/src/pathops/SkAddIntersections.h
+++ b/src/pathops/SkAddIntersections.h
@@ -13,6 +13,6 @@
 
 bool AddIntersectTs(SkOpContour* test, SkOpContour* next);
 void AddSelfIntersectTs(SkOpContour* test);
-void CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total);
+bool CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total);
 
 #endif
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index 467fab31f5..6d6ad7926e 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -267,7 +267,7 @@ bool SkOpContour::calcAngles() {
     return true;
 }
 
-void SkOpContour::calcCoincidentWinding() {
+bool SkOpContour::calcCoincidentWinding() {
     int count = fCoincidences.count();
 #if DEBUG_CONCIDENT
     if (count > 0) {
@@ -276,8 +276,11 @@ void SkOpContour::calcCoincidentWinding() {
 #endif
     for (int index = 0; index < count; ++index) {
         SkCoincidence& coincidence = fCoincidences[index];
-         calcCommonCoincidentWinding(coincidence);
+        if (!calcCommonCoincidentWinding(coincidence)) {
+            return false;
+        }
     }
+    return true;
 }
 
 void SkOpContour::calcPartialCoincidentWinding() {
@@ -471,11 +474,11 @@ void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
             addTo2->addTCancel(missingPt1, missingPt2, addOther2);
         }
     } else if (missingT1 >= 0) {
-        addTo1->addTCoincident(missingPt1, missingPt2, addTo1 == addTo2 ? missingT2 : otherT2,
-                addOther1);
+        SkAssertResult(addTo1->addTCoincident(missingPt1, missingPt2,
+                addTo1 == addTo2 ? missingT2 : otherT2, addOther1));
     } else {
-        addTo2->addTCoincident(missingPt2, missingPt1, addTo2 == addTo1 ? missingT1 : otherT1,
-                addOther2);
+        SkAssertResult(addTo2->addTCoincident(missingPt2, missingPt1,
+                addTo2 == addTo1 ? missingT1 : otherT1, addOther2));
     }
 }
 
@@ -543,20 +546,20 @@ void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coinciden
     }
 }
 
-void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
+bool SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
     if (coincidence.fNearly[0] && coincidence.fNearly[1]) {
-        return;
+        return true;
     }
     int thisIndex = coincidence.fSegments[0];
     SkOpSegment& thisOne = fSegments[thisIndex];
     if (thisOne.done()) {
-        return;
+        return true;
     }
     SkOpContour* otherContour = coincidence.fOther;
     int otherIndex = coincidence.fSegments[1];
     SkOpSegment& other = otherContour->fSegments[otherIndex];
     if (other.done()) {
-        return;
+        return true;
     }
     double startT = coincidence.fTs[0][0];
     double endT = coincidence.fTs[0][1];
@@ -577,15 +580,17 @@ void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence)
     }
     bump_out_close_span(&oStartT, &oEndT);
     SkASSERT(!approximately_negative(oEndT - oStartT));
+    bool success = true;
     if (cancelers) {
         thisOne.addTCancel(*startPt, *endPt, &other);
     } else {
-        thisOne.addTCoincident(*startPt, *endPt, endT, &other);
+        success = thisOne.addTCoincident(*startPt, *endPt, endT, &other);
     }
 #if DEBUG_CONCIDENT
     thisOne.debugShowTs("p");
     other.debugShowTs("o");
 #endif
+    return success;
 }
 
 void SkOpContour::resolveNearCoincidence() {
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index d1b3cd0179..899367ab0e 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -114,7 +114,7 @@ public:
     }
 
     bool calcAngles();
-    void calcCoincidentWinding();
+    bool calcCoincidentWinding();
     void calcPartialCoincidentWinding();
 
     void checkDuplicates() {
@@ -325,7 +325,7 @@ public:
 private:
     void alignPt(int index, SkPoint* point, int zeroPt) const;
     int alignT(bool swap, int tIndex, SkIntersections* ts) const;
-    void calcCommonCoincidentWinding(const SkCoincidence& );
+    bool calcCommonCoincidentWinding(const SkCoincidence& );
     void checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
                              const SkCoincidence& twoCoin, int twoIdx, bool partial);
     void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 5208a38667..2dda11a383 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -1271,7 +1271,7 @@ void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
 
 // set spans from start to end to increment the greater by one and decrement
 // the lesser
-void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
+bool SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
         SkOpSegment* other) {
     bool binary = fOperand != other->fOperand;
     int index = 0;
@@ -1303,7 +1303,10 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d
     // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
     do {
         SkASSERT(test->fT < 1);
-        SkASSERT(oTest->fT < 1);
+        if (oTest->fT == 1) {
+            // paths with extreme data may be so mismatched that we fail here
+            return false;
+        }
 
         // consolidate the winding count even if done
         if ((test->fWindValue == 0 && test->fOppValue == 0)
@@ -1409,6 +1412,7 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d
     }
     setCoincidentRange(startPt, endPt, other);
     other->setCoincidentRange(startPt, endPt, this);
+    return true;
 }
 
 // FIXME: this doesn't prevent the same span from being added twice
@@ -2422,8 +2426,8 @@ nextSmallCheck:
             do {
                 ++nextSpan;
             } while (nextSpan->fSmall);
-            missing.fSegment->addTCoincident(missing.fPt, nextSpan->fPt, nextSpan->fT,
-                    missingOther);
+            SkAssertResult(missing.fSegment->addTCoincident(missing.fPt, nextSpan->fPt,
+                    nextSpan->fT, missingOther));
         } else if (otherSpan.fT > 0) {
             const SkOpSpan* priorSpan = &otherSpan;
             do {
@@ -2494,7 +2498,7 @@ void SkOpSegment::checkSmallCoincidence(const SkOpSpan& span,
     }
 //    SkASSERT(oSpan.fSmall);
     if (oStartIndex < oEndIndex) {
-        addTCoincident(span.fPt, next->fPt, next->fT, other);
+        SkAssertResult(addTCoincident(span.fPt, next->fPt, next->fT, other));
     } else {
         addTCancel(span.fPt, next->fPt, other);
     }
@@ -2539,7 +2543,7 @@ void SkOpSegment::checkSmallCoincidence(const SkOpSpan& span,
                         oTest->fOtherT, tTest->fT);
 #endif
                 if (tTest->fT < oTest->fOtherT) {
-                    addTCoincident(span.fPt, next->fPt, next->fT, testOther);
+                    SkAssertResult(addTCoincident(span.fPt, next->fPt, next->fT, testOther));
                 } else {
                     addTCancel(span.fPt, next->fPt, testOther);
                 }
@@ -3428,7 +3432,7 @@ bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, const SkPoi
             if (cancel) {
                 match->addTCancel(startPt, endPt, other);
             } else {
-                match->addTCoincident(startPt, endPt, endT, other);
+                SkAssertResult(match->addTCoincident(startPt, endPt, endT, other));
             }
             return true;
         }
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index df87d058b6..24d08bd814 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -284,7 +284,7 @@ public:
     void addStartSpan(int endIndex);
     int addT(SkOpSegment* other, const SkPoint& pt, double newT);
     void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
-    void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
+    bool addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
                         SkOpSegment* other);
     const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
                              const SkPoint& pt);
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 9a8a2cf4e3..f7b7273a8d 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -699,7 +699,9 @@ bool HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
 #if DEBUG_SHOW_WINDING
     SkOpContour::debugShowWindingValues(contourList);
 #endif
-    CoincidenceCheck(contourList, total);
+    if (!CoincidenceCheck(contourList, total)) {
+        return false;
+    }
 #if DEBUG_SHOW_WINDING
     SkOpContour::debugShowWindingValues(contourList);
 #endif