possible fix for pathops timeout

fuzzer causes pathops to loop
somewhere finding complex
intersections, but does not
have a reproducible test case.

Somewhat grasping at straws,
the failing condition in this
CL was triggered by the fuzzer
tests, but may or may not be
related to the hang.

TBR=reed@google.com
Bug: 754434
Change-Id: Ia8edc0709cec559b277ed83a5ad6feb67d8088c6
Reviewed-on: https://skia-review.googlesource.com/42780
Reviewed-by: Cary Clark <caryclark@skia.org>
Commit-Queue: Cary Clark <caryclark@skia.org>

2 files changed, 112 insertions, 8 deletions

diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
index ef0799de4f..a89785542f 100644
--- a/src/pathops/SkPathOpsTSect.h
+++ b/src/pathops/SkPathOpsTSect.h
@@ -309,7 +309,7 @@ private:
     SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const;
     void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp);
     void recoverCollapsed();
-    void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween);
+    bool removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween);
     void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span,
                       SkTSect<OppCurve, TCurve>* opp);
     bool removeSpan(SkTSpan<TCurve, OppCurve>* span);
@@ -324,7 +324,7 @@ private:
     SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan);
     SkTSpan<TCurve, OppCurve>* tail();
     bool trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
-    void unlinkSpan(SkTSpan<TCurve, OppCurve>* span);
+    bool unlinkSpan(SkTSpan<TCurve, OppCurve>* span);
     bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
                        SkTSpan<OppCurve, TCurve>* oppFirst);
     void validate() const;
@@ -1273,8 +1273,12 @@ bool SkTSect<TCurve, OppCurve>::extractCoincident(
     this->validateBounded();
     sect2->validateBounded();
     last = first->fNext;
-    this->removeCoincident(first, false);
-    sect2->removeCoincident(oppFirst, true);
+    if (!this->removeCoincident(first, false)) {
+        return false;
+    }
+    if (!sect2->removeCoincident(oppFirst, true)) {
+        return false;
+    }
     if (deleteEmptySpans) {
         if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) {
             *result = nullptr;
@@ -1737,8 +1741,10 @@ void SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>*
 }
 
 template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) {
-    this->unlinkSpan(span);
+bool SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) {
+    if (!this->unlinkSpan(span)) {
+        return false;
+    }
     if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
         --fActiveCount;
         span->fNext = fCoincident;
@@ -1746,6 +1752,7 @@ void SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span
     } else {
         this->markSpanGone(span);
     }
+    return true;
 }
 
 template<typename TCurve, typename OppCurve>
@@ -1761,7 +1768,9 @@ void SkTSect<TCurve, OppCurve>::removedEndCheck(SkTSpan<TCurve, OppCurve>* span)
 template<typename TCurve, typename OppCurve>
 bool SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {\
     this->removedEndCheck(span);
-    this->unlinkSpan(span);
+    if (!this->unlinkSpan(span)) {
+        return false;
+    }
     return this->markSpanGone(span);
 }
 
@@ -1864,13 +1873,16 @@ bool SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span,
 }
 
 template<typename TCurve, typename OppCurve>
-void SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) {
+bool SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) {
     SkTSpan<TCurve, OppCurve>* prev = span->fPrev;
     SkTSpan<TCurve, OppCurve>* next = span->fNext;
     if (prev) {
         prev->fNext = next;
         if (next) {
             next->fPrev = prev;
+            if (next->fStartT > next->fEndT) {
+                return false;
+            }
             next->validate();
         }
     } else {
@@ -1879,6 +1891,7 @@ void SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) {
             next->fPrev = nullptr;
         }
     }
+    return true;
 }
 
 template<typename TCurve, typename OppCurve>
diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp
index e18774ae94..0f94008fb1 100644
--- a/tests/PathOpsOpTest.cpp
+++ b/tests/PathOpsOpTest.cpp
@@ -8559,8 +8559,99 @@ path.quadTo(SkBits2Float(0x5c525200), SkBits2Float(0x46090052), SkBits2Float(0x7
     testPathOpFail(reporter, path1, path2, (SkPathOp) 3, filename);

 }

 

+static void fuzz754434_1(skiatest::Reporter* reporter, const char* filename) {

+    SkPath path;

+    path.setFillType((SkPath::FillType) 0);

+path.setFillType(SkPath::kWinding_FillType);

+

+    SkPath path1(path);

+    path.reset();

+    path.setFillType((SkPath::FillType) 0);

+path.setFillType(SkPath::kWinding_FillType);

+path.moveTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000));  // 0, 0

+path.cubicTo(SkBits2Float(0x535e5372), SkBits2Float(0x53536153), SkBits2Float(0x79530f53), SkBits2Float(0x101b6c88), SkBits2Float(0x5353735e), SkBits2Float(0x006df653));  // 9.54883e+11f, 9.07871e+11f, 6.84928e+34f, 3.0652e-29f, 9.08174e+11f, 1.00984e-38f

+path.cubicTo(SkBits2Float(0xf26df46d), SkBits2Float(0xf6f6f6f6), SkBits2Float(0x5656f666), SkBits2Float(0x5a565656), SkBits2Float(0x00000056), SkBits2Float(0xf66e5600));  // -4.71318e+30f, -2.50452e+33f, 5.90884e+13f, 1.50826e+16f, 1.20512e-43f, -1.20851e+33f

+path.lineTo(SkBits2Float(0xff00ff56), SkBits2Float(0x00faf6f6));  // -1.71467e+38f, 2.30475e-38f

+path.moveTo(SkBits2Float(0x60576bfa), SkBits2Float(0x006df653));  // 6.20911e+19f, 1.00984e-38f

+path.cubicTo(SkBits2Float(0xf26df46d), SkBits2Float(0xf653f6f6), SkBits2Float(0x563ef666), SkBits2Float(0x56565656), SkBits2Float(0x65565656), SkBits2Float(0xf6765656));  // -4.71318e+30f, -1.07479e+33f, 5.24914e+13f, 5.89166e+13f, 6.32612e+22f, -1.24908e+33f

+

+    SkPath path2(path);

+    testPathOpFuzz(reporter, path1, path2, (SkPathOp) 3, filename);

+}

+

+static void fuzz754434_2(skiatest::Reporter* reporter, const char* filename) {

+    SkPath path;

+    path.setFillType((SkPath::FillType) 1);

+path.setFillType(SkPath::kEvenOdd_FillType);

+path.moveTo(SkBits2Float(0xff00ff56), SkBits2Float(0x00000000));  // -1.71467e+38f, 0

+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0xf66e5600));  // 0, -1.20851e+33f

+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0xf629168b));  // 0, -8.57378e+32f

+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000));  // 0, 0

+path.lineTo(SkBits2Float(0xff00ff56), SkBits2Float(0x00000000));  // -1.71467e+38f, 0

+path.close();

+

+    SkPath path1(path);

+    path.reset();

+    path.setFillType((SkPath::FillType) 0);

+path.setFillType(SkPath::kWinding_FillType);

+path.moveTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000));  // 0, 0

+path.lineTo(SkBits2Float(0x03e8f6f6), SkBits2Float(0xf7060000));  // 1.36924e-36f, -2.71784e+33f

+path.lineTo(SkBits2Float(0x4ff6f6f6), SkBits2Float(0x3e3e3e2a));  // 8.28676e+09f, 0.185784f

+path.conicTo(SkBits2Float(0x6c8879ff), SkBits2Float(0x08761b1b), SkBits2Float(0x7066662d), SkBits2Float(0x70707070), SkBits2Float(0x70707070));  // 1.31992e+27f, 7.40598e-34f, 2.8522e+29f, 2.97649e+29f, 2.97649e+29f

+

+    SkPath path2(path);

+    testPathOpFuzz(reporter, path1, path2, (SkPathOp) 2, filename);

+}

+

+static void fuzz754434_3(skiatest::Reporter* reporter, const char* filename) {

+    SkPath path;

+    path.setFillType((SkPath::FillType) 0);

+path.setFillType(SkPath::kWinding_FillType);

+

+    SkPath path1(path);

+    path.reset();

+    path.setFillType((SkPath::FillType) 0);

+path.setFillType(SkPath::kWinding_FillType);

+path.moveTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000));  // 0, 0

+path.cubicTo(SkBits2Float(0x535e5372), SkBits2Float(0x53536153), SkBits2Float(0x79530f53), SkBits2Float(0x101b6c88), SkBits2Float(0x5353735e), SkBits2Float(0x006df653));  // 9.54883e+11f, 9.07871e+11f, 6.84928e+34f, 3.0652e-29f, 9.08174e+11f, 1.00984e-38f

+path.cubicTo(SkBits2Float(0xf26df46d), SkBits2Float(0xf6f6f6f6), SkBits2Float(0x5656f666), SkBits2Float(0x5a565656), SkBits2Float(0x00000056), SkBits2Float(0xf66e5600));  // -4.71318e+30f, -2.50452e+33f, 5.90884e+13f, 1.50826e+16f, 1.20512e-43f, -1.20851e+33f

+path.lineTo(SkBits2Float(0xff00ff56), SkBits2Float(0x00faf6f6));  // -1.71467e+38f, 2.30475e-38f

+path.moveTo(SkBits2Float(0x60576bfa), SkBits2Float(0x006df653));  // 6.20911e+19f, 1.00984e-38f

+path.cubicTo(SkBits2Float(0xf26df46d), SkBits2Float(0xf653f6f6), SkBits2Float(0x563ef666), SkBits2Float(0x56565656), SkBits2Float(0x65565656), SkBits2Float(0xf6765656));  // -4.71318e+30f, -1.07479e+33f, 5.24914e+13f, 5.89166e+13f, 6.32612e+22f, -1.24908e+33f

+

+    SkPath path2(path);

+    testPathOpFuzz(reporter, path1, path2, (SkPathOp) 3, filename);

+}

+

+static void fuzz754434_4(skiatest::Reporter* reporter, const char* filename) {

+    SkPath path;

+    path.setFillType((SkPath::FillType) 1);

+path.setFillType(SkPath::kEvenOdd_FillType);

+path.moveTo(SkBits2Float(0xff00ff56), SkBits2Float(0x00000000));  // -1.71467e+38f, 0

+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0xf66e5600));  // 0, -1.20851e+33f

+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0xf629168b));  // 0, -8.57378e+32f

+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000));  // 0, 0

+path.lineTo(SkBits2Float(0xff00ff56), SkBits2Float(0x00000000));  // -1.71467e+38f, 0

+path.close();

+

+    SkPath path1(path);

+    path.reset();

+    path.setFillType((SkPath::FillType) 0);

+path.setFillType(SkPath::kWinding_FillType);

+path.moveTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000));  // 0, 0

+path.lineTo(SkBits2Float(0x03e8f6f6), SkBits2Float(0xf7060000));  // 1.36924e-36f, -2.71784e+33f

+path.lineTo(SkBits2Float(0x4ff6f6f6), SkBits2Float(0x3e3e3e2a));  // 8.28676e+09f, 0.185784f

+path.conicTo(SkBits2Float(0x6c8879ff), SkBits2Float(0x08761b1b), SkBits2Float(0x7066662d), SkBits2Float(0x70707070), SkBits2Float(0x70707070));  // 1.31992e+27f, 7.40598e-34f, 2.8522e+29f, 2.97649e+29f, 2.97649e+29f

+

+    SkPath path2(path);

+    testPathOpFuzz(reporter, path1, path2, (SkPathOp) 2, filename);

+}

 

 static struct TestDesc failTests[] = {

+    TEST(fuzz754434_1),

+    TEST(fuzz754434_2),

+    TEST(fuzz754434_3),

+    TEST(fuzz754434_4),

     TEST(fuzzhang_3),

     TEST(fuzzhang_2),

     TEST(release_13),