provide safe exit for runaway intersections

src/pathops/SkPathOpsTSect.h

 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #ifndef SkPathOpsTSect_DEFINED
 #define SkPathOpsTSect_DEFINED
 
 #include "SkChunkAlloc.h"
@@ skipping 256 matching lines @@
         SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
         result->splitAt(span, t, &fHeap);
         result->initBounds(fCurve);
         span->initBounds(fCurve);
         return result;
     }
 
     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;
     void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
                                SkTSpan<TCurve, OppCurve>* last);
     int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
                               SkTSpan<TCurve, OppCurve>** last) const;
 
     int debugID() const {
         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,
                    SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult);
     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;
     void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2);
     SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const;
     void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp);
     void recoverCollapsed();
     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);
     SkTSpan<TCurve, OppCurve>* tail();
     void trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
     void unlinkSpan(SkTSpan<TCurve, OppCurve>* span);
     bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
                        SkTSpan<OppCurve, TCurve>* oppFirst);
     void validate() const;
     void validateBounded() const;
@@ skipping 647 matching lines @@
         if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
                 largest->fBoundsMax < test->fBoundsMax)) {
             largest = test;
             lCollapsed = test->fCollapsed;
         }
     }
     return largest;
 }
 
 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 {
         int consecutive = this->countConsecutiveSpans(first, &last);
         next = last->fNext;
         if (consecutive < COINCIDENT_SPAN_COUNT) {
             continue;
         }
         this->validate();
         sect2->validate();
         this->computePerpendiculars(sect2, first, last);
         this->validate();
         sect2->validate();
         // 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;
         }
         if (!next || next->fDeleted) {
             break;
         }
     } while ((first = next));
+    return true;
 }
 
 template<typename TCurve, typename OppCurve>
 void SkTSect<TCurve, OppCurve>::coincidentForce(SkTSect<OppCurve, TCurve>* sect2,
         double start1s, double start1e) {
     SkTSpan<TCurve, OppCurve>* first = fHead;
     SkTSpan<TCurve, OppCurve>* last = this->tail();
     SkTSpan<OppCurve, TCurve>* oppFirst = sect2->fHead;
     SkTSpan<OppCurve, TCurve>* oppLast = sect2->tail();
     bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
@@ skipping 116 matching lines @@
     }
     do {
         if (test->findOppSpan(span)) {
             return true;
         }
     } while ((test = test->next()));
     return false;
 }
 
 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;
     double oppStartT SK_INIT_TO_AVOID_WARNING;
     double oppEndT SK_INIT_TO_AVOID_WARNING;
     SkTSpan<TCurve, OppCurve>* prev = first->fPrev;
     SkASSERT(first->fCoinStart.isCoincident());
     SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT());
     SkOPASSERT(last->fCoinEnd.isCoincident());
     bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
@@ skipping 37 matching lines @@
     if (!oppMatched) {
         SkTSwap(oppFirst, oppLast);
         SkTSwap(oppStartT, oppEndT);
     }
     SkOPASSERT(oppStartT < oppEndT);
     SkASSERT(coinStart == first->fStartT);
     SkASSERT(coinEnd == last->fEndT);
     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();
     sect2->validate();
     bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
     deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
     this->removeSpanRange(first, last);
     sect2->removeSpanRange(oppFirst, oppLast);
     first->fEndT = last->fEndT;
     first->resetBounds(this->fCurve);
     first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve);
     first->fCoinEnd.setPerp(fCurve, first->fEndT, first->fPart[TCurve::kPointLast], sect2->fCurve);
     oppStartT = first->fCoinStart.perpT();
     oppEndT = first->fCoinEnd.perpT();
     if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) {
         if (!oppMatched) {
             SkTSwap(oppStartT, oppEndT);
         }
         oppFirst->fStartT = oppStartT;
         oppFirst->fEndT = oppEndT;
         oppFirst->resetBounds(sect2->fCurve);
     }
     this->validateBounded();
     sect2->validateBounded();
     last = first->fNext;
     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>
 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun(
         SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) {
     SkTSpan<TCurve, OppCurve>* work = first;
     SkTSpan<TCurve, OppCurve>* lastCandidate = nullptr;
     first = nullptr;
     // find the first fully coincident span
     do {
@@ skipping 264 matching lines @@
     if (!opp->fHead->contains(oppTTest)) {
         return 0;
     }
     i->setMax(1);
     i->insert(workT, oppTTest, workPt);
     return 1;
 }
 
 
 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>
 bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2,
         double t2) const {
     SkDVector dxdy = this->fCurve.dxdyAtT(t);
     SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2);
     return dxdy.dot(dxdy2) >= 0;
 }
 
@@ skipping 144 matching lines @@
     if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
         --fActiveCount;
         span->fNext = fCoincident;
         fCoincident = span;
     } else {
         this->markSpanGone(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>
 void SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first,
         SkTSpan<TCurve, OppCurve>* last) {
     if (first == last) {
         return;
     }
     SkTSpan<TCurve, OppCurve>* span = first;
     SkASSERT(span);
@@ skipping 415 matching lines @@
 #if DEBUG_T_SECT_LOOP_COUNT
         intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop);
 #endif
         // if there are 9 or more continuous spans on both sects, suspect coincidence
         if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
                 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
             if (coinLoopCount == kMaxCoinLoopCount) {
                 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
             intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
 #endif
             if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
                 /* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
                    gets stuck in a loop. It adds an extension to allow a coincident end
                    perpendicular to track its intersection in the opposite curve. However,
                    the bounding box of the extension does not intersect the original curve,
@@ skipping 136 matching lines @@
             --last;
         } else {
             intersections->setCoincident(index++);
         }
         intersections->setCoincident(index);
     }
     SkASSERT(intersections->used() <= TCurve::kMaxIntersections);
 }
 
 #endif