provide safe exit for runaway intersections

Curve intersections with extreme numbers may
cause the intersection template code to loop
forever. Detect this by looking for
marking more spans gone than exist, and
return without any intersections found.

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

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

2 files changed, 68 insertions, 24 deletions

diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
index bd26e5ace3..70ee8ababd 100644
--- a/src/pathops/SkPathOpsTSect.h
+++ b/src/pathops/SkPathOpsTSect.h
@@ -274,7 +274,7 @@ private:
     bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t,
                           double* oppT);
     SkTSpan<TCurve, OppCurve>* boundsMax() const;
-    void coincidentCheck(SkTSect<OppCurve, TCurve>* sect2);
+    bool coincidentCheck(SkTSect<OppCurve, TCurve>* sect2);
     void coincidentForce(SkTSect<OppCurve, TCurve>* sect2, double start1s, double start1e);
     bool coincidentHasT(double t);
     int collapsed() const;
@@ -287,14 +287,13 @@ private:
         return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
     }
 
-    void deleteEmptySpans();
+    bool deleteEmptySpans();
     void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const;
     void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const;
     static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2,
                          SkIntersections* );
-    SkTSpan<TCurve, OppCurve>* extractCoincident(SkTSect<OppCurve, TCurve>* sect2,
-                                                  SkTSpan<TCurve, OppCurve>* first,
-                                                  SkTSpan<TCurve, OppCurve>* last);
+    bool extractCoincident(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
+                           SkTSpan<TCurve, OppCurve>* last, SkTSpan<TCurve, OppCurve>** result);
     SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first,
                                                   SkTSpan<TCurve, OppCurve>** lastPtr);
     int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
@@ -302,7 +301,7 @@ private:
     bool isParallel(const SkDLine& thisLine, const SkTSect<OppCurve, TCurve>* opp) const;
     int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
                        SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* );
-    void markSpanGone(SkTSpan<TCurve, OppCurve>* span);
+    bool markSpanGone(SkTSpan<TCurve, OppCurve>* span);
     bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const;
     void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2,
                          bool* calcMatched, bool* oppMatched) const;
@@ -313,7 +312,7 @@ private:
     void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween);
     void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span,
                       SkTSect<OppCurve, TCurve>* opp);
-    void removeSpan(SkTSpan<TCurve, OppCurve>* span);
+    bool removeSpan(SkTSpan<TCurve, OppCurve>* span);
     void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last);
     void removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
     SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan);
@@ -981,7 +980,7 @@ SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() const {
 }
 
 template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) {
+bool SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) {
     SkTSpan<TCurve, OppCurve>* first = fHead;
     SkTSpan<TCurve, OppCurve>* last, * next;
     do {
@@ -998,7 +997,10 @@ void SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2
         // check to see if a range of points are on the curve
         SkTSpan<TCurve, OppCurve>* coinStart = first;
         do {
-            coinStart = this->extractCoincident(sect2, coinStart, last);
+            bool success = this->extractCoincident(sect2, coinStart, last, &coinStart);
+            if (!success) {
+                return false;
+            }
         } while (coinStart && !last->fDeleted);
         if (!fHead || !sect2->fHead) {
             break;
@@ -1007,6 +1009,7 @@ void SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2
             break;
         }
     } while ((first = next));
+    return true;
 }
 
 template<typename TCurve, typename OppCurve>
@@ -1143,24 +1146,29 @@ bool SkTSect<TCurve, OppCurve>::debugHasBounded(const SkTSpan<OppCurve, TCurve>*
 }
 
 template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::deleteEmptySpans() {
+bool SkTSect<TCurve, OppCurve>::deleteEmptySpans() {
     SkTSpan<TCurve, OppCurve>* test;
     SkTSpan<TCurve, OppCurve>* next = fHead;
     while ((test = next)) {
         next = test->fNext;
         if (!test->fBounded) {
-            this->removeSpan(test);
+            if (!this->removeSpan(test)) {
+                return false;
+            }
         }
     }
+    return true;
 }
 
 template<typename TCurve, typename OppCurve>
-SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::extractCoincident(
+bool SkTSect<TCurve, OppCurve>::extractCoincident(
         SkTSect<OppCurve, TCurve>* sect2,
-        SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) {
+        SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
+        SkTSpan<TCurve, OppCurve>** result) {
     first = findCoincidentRun(first, &last);
     if (!first || !last) {
-        return nullptr;
+        *result = nullptr;
+        return true;
     }
     // march outwards to find limit of coincidence from here to previous and next spans
     double startT = first->fStartT;
@@ -1218,10 +1226,12 @@ SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::extractCoincident(
     SkOPASSERT(oppStartT == oppFirst->fStartT);
     SkOPASSERT(oppEndT == oppLast->fEndT);
     if (!oppFirst) {
-        return nullptr;
+        *result = nullptr;
+        return true;
     }
     if (!oppLast) {
-        return nullptr;
+        *result = nullptr;
+        return true;
     }
     // reduce coincident runs to single entries
     this->validate();
@@ -1250,12 +1260,15 @@ SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::extractCoincident(
     this->removeCoincident(first, false);
     sect2->removeCoincident(oppFirst, true);
     if (deleteEmptySpans) {
-        this->deleteEmptySpans();
-        sect2->deleteEmptySpans();
+        if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) {
+            *result = nullptr;
+            return false;
+        }
     }
     this->validate();
     sect2->validate();
-    return last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr;
+    *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr;
+    return true;
 }
 
 template<typename TCurve, typename OppCurve>
@@ -1540,12 +1553,15 @@ int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span,
 
 
 template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) {
-    --fActiveCount;
+bool SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) {
+    if (--fActiveCount < 0) {
+        return false;
+    }
     span->fNext = fDeleted;
     fDeleted = span;
     SkOPASSERT(!span->fDeleted);
     span->fDeleted = true;
+    return true;
 }
 
 template<typename TCurve, typename OppCurve>
@@ -1710,9 +1726,9 @@ void SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span
 }
 
 template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {
+bool SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {
     this->unlinkSpan(span);
-    this->markSpanGone(span);
+    return this->markSpanGone(span);
 }
 
 template<typename TCurve, typename OppCurve>
@@ -2148,7 +2164,9 @@ void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1,
                 start1s = sect1->fHead->fStartT;
                 start1e = sect1->tail()->fEndT;
             }
-            sect1->coincidentCheck(sect2);
+            if (!sect1->coincidentCheck(sect2)) {
+                return;
+            }
             sect1->validate();
             sect2->validate();
 #if DEBUG_T_SECT_LOOP_COUNT
diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp
index 3316f7e0cb..7261455019 100644
--- a/tests/PathOpsOpTest.cpp
+++ b/tests/PathOpsOpTest.cpp
@@ -7407,7 +7407,33 @@ path.cubicTo(SkBits2Float(0x6d6d6d6d), SkBits2Float(0x6d6d6d6d), SkBits2Float(0x
     testPathOpFuzz(reporter, path1, path2, (SkPathOp) 2, filename);
 }
 
+static void fuzz763_31(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path;
+    path.setFillType((SkPath::FillType) 1);
+
+    SkPath path1(path);
+    path.reset();
+    path.setFillType((SkPath::FillType) 0);
+path.moveTo(SkBits2Float(0xd72a8c55), SkBits2Float(0x61081f2a));  // -1.8752e+14f, 1.56938e+20f
+path.conicTo(SkBits2Float(0x6a4b7bc0), SkBits2Float(0x4793ed7a), SkBits2Float(0x282a3a21), SkBits2Float(0xdf3a2128), SkBits2Float(0x471ac575));  // 6.14991e+25f, 75739, 9.4495e-15f, -1.3412e+19f, 39621.5f
+path.lineTo(SkBits2Float(0x28404040), SkBits2Float(0x552a298a));  // 1.06721e-14f, 1.16935e+13f
+path.moveTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a));  // 5.8414e-19f, 4.61198e-19f
+path.conicTo(SkBits2Float(0x6a4b7bc0), SkBits2Float(0x80ed7a3a), SkBits2Float(0x2a3a2147), SkBits2Float(0xdf212828), SkBits2Float(0x4f1a3a3a));  // 6.14991e+25f, -2.18089e-38f, 1.65317e-13f, -1.16126e+19f, 2.58751e+09f
+path.lineTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a));  // 5.8414e-19f, 4.61198e-19f
+path.close();
+path.moveTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a));  // 5.8414e-19f, 4.61198e-19f
+path.cubicTo(SkBits2Float(0x3ac2213a), SkBits2Float(0x432a2928), SkBits2Float(0x96812be6), SkBits2Float(0x272a1d2a), SkBits2Float(0x3a2a3529), SkBits2Float(0x3b1e2ab0));  // 0.00148109f, 170.161f, -2.08688e-25f, 2.3608e-15f, 0.000649291f, 0.00241343f
+path.lineTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a));  // 5.8414e-19f, 4.61198e-19f
+path.close();
+path.moveTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a));  // 5.8414e-19f, 4.61198e-19f
+path.cubicTo(SkBits2Float(0xc5272927), SkBits2Float(0x22383b39), SkBits2Float(0x1051523a), SkBits2Float(0x2927b029), SkBits2Float(0x685b2d27), SkBits2Float(0x5b2d6855));  // -2674.57f, 2.4968e-18f, 4.12813e-29f, 3.72342e-14f, 4.14012e+24f, 4.88099e+16f
+
+    SkPath path2(path);
+    testPathOpFuzz(reporter, path1, path2, (SkPathOp) 4, filename);
+}
+
 static struct TestDesc failTests[] = {
+    TEST(fuzz763_31),
     TEST(fuzz763_30),
     TEST(fuzz763_29),
     TEST(fuzz763_28),