harden pathops for pathological test

src/pathops/SkPathOpsCommon.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkAddIntersections.h"
 #include "SkOpEdgeBuilder.h"
 #include "SkPathOpsCommon.h"
 #include "SkPathWriter.h"
@@ skipping 143 matching lines @@
             *chase->append() = span;
     #endif
             return last->segment();
         }
         if (done) {
             continue;
         }
         if (!sortable) {
             continue;
         }
-        // find first angle, initialize winding to computed fWindSum
+        // find first angle, initialize winding to computed wind sum
         const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
         const SkOpAngle* firstAngle;
         SkDEBUGCODE(firstAngle = angle);
         SkDEBUGCODE(bool loop = false);
         int winding;
         do {
             angle = angle->next();
             SkASSERT(angle != firstAngle || !loop);
             SkDEBUGCODE(loop |= angle == firstAngle);
             segment = angle->segment();
@@ skipping 26 matching lines @@
             *endIndex = angle->end();
             int lesser = SkMin32(*tIndex, *endIndex);
             const SkOpSpan& nextSpan = segment->span(lesser);
             if (!nextSpan.fDone) {
             // FIXME: this be wrong? assign startWinding if edge is in
             // same direction. If the direction is opposite, winding to
             // assign is flipped sign or +/- 1?
                 if (SkOpSegment::UseInnerWinding(maxWinding, winding)) {
                     maxWinding = winding;
                 }
-                (void) segment->markAndChaseWinding(angle, maxWinding, 0);
+                // allowed to do nothing
+                (void) segment->markAndChaseWinding(angle, maxWinding, 0, NULL);
                 break;
             }
         }
         *chase->insert(0) = span;
         return segment;
     }
     return NULL;
 }
 
 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
@@ skipping 86 matching lines @@
         }
         SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex);
         if (nonVertical) {
             *current = nonVertical;
             return;
         }
     }
     return;
 }
 
+struct SortableTop {  // error if local in pre-C++11
+    SkOpSegment* fSegment;
+    int fIndex;
+    int fEndIndex;
+};
+
 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
         SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
         int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical,
         bool firstPass) {
     SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
             done, firstPass);
     if (!current) {
         return NULL;
     }
     const int startIndex = *indexPtr;
@@ skipping 21 matching lines @@
         return current;
     }
     int contourWinding;
     int oppContourWinding = 0;
     // the simple upward projection of the unresolved points hit unsortable angles
     // shoot rays at right angles to the segment to find its winding, ignoring angle cases
     bool tryAgain;
     double tHit;
     SkScalar hitDx = 0;
     SkScalar hitOppDx = 0;
+    // keep track of subsequent returns to detect infinite loops
+    SkTDArray<SortableTop> sortableTops;
     do {
         // if current is vertical, find another candidate which is not
         // if only remaining candidates are vertical, then they can be marked done
         SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
         skipVertical(contourList, &current, indexPtr, endIndexPtr);
         SkASSERT(current);  // FIXME: if null, all remaining are vertical
         SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
         tryAgain = false;
         contourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
                 &hitDx, &tryAgain, onlyVertical, false);
+        if (tryAgain) {
+            bool giveUp = false;
+            int count = sortableTops.count();
+            for (int index = 0; index < count; ++index) {
+                const SortableTop& prev = sortableTops[index];
+                if (giveUp) {
+                    prev.fSegment->markDoneFinal(prev.fIndex);
+                } else if (prev.fSegment == current
+                        && (prev.fIndex == *indexPtr || prev.fEndIndex == *endIndexPtr)) {
+                    // remaining edges are non-vertical and cannot have their winding computed
+                    // mark them as done and return, and hope that assembly can fill the holes
+                    giveUp = true;
+                    index = -1;
+                }
+            }
+            if (giveUp) {
+                *done = true;
+                return NULL;
+            }
+        }
+        SortableTop* sortableTop = sortableTops.append();
+        sortableTop->fSegment = current;
+        sortableTop->fIndex = *indexPtr;
+        sortableTop->fEndIndex = *endIndexPtr;
+#if DEBUG_SORT
+        SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=%d vert=%d\n",
+                __FUNCTION__, current->debugID(), *indexPtr, *endIndexPtr, tHit, hitDx, tryAgain,
+                *onlyVertical);
+#endif
         if (*onlyVertical) {
             return current;
         }
         if (tryAgain) {
             continue;
         }
         if (angleIncludeType < SkOpAngle::kBinarySingle) {
             break;
         }
         oppContourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
                 &hitOppDx, &tryAgain, NULL, true);
     } while (tryAgain);
-    current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding,
-            hitOppDx);
+    bool success = current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx,
+            oppContourWinding, hitOppDx);
     if (current->done()) {
         return NULL;
+    } else if (!success) {  // check if the span has a valid winding
+        int min = SkTMin(*indexPtr, *endIndexPtr);
+        const SkOpSpan& span = current->span(min);
+        if (span.fWindSum == SK_MinS32) {
+            return NULL;
+        }
     }
     return current;
 }
 
 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) {
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         if (!contour->calcAngles()) {
             return false;
         }
     }
     return true;
 }
 
 static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) {
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         contour->checkDuplicates();
     }
 }
 
-static void checkEnds(SkTArray<SkOpContour*, true>* contourList) {
+static bool checkEnds(SkTArray<SkOpContour*, true>* contourList) {
     // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
     // instead, look to see if the connecting curve intersected at that same end.
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
-        contour->checkEnds();
+        if (!contour->checkEnds()) {
+            return false;
+        }
     }
+    return true;
 }
 
 static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) {
     bool hasMultiples = false;
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
         contour->checkMultiples();
         hasMultiples |= contour->hasMultiples();
     }
@@ skipping 273 matching lines @@
 #if DEBUG_SHOW_WINDING
     SkOpContour::debugShowWindingValues(contourList);
 #endif
     if (!CoincidenceCheck(contourList, total)) {
         return false;
     }
 #if DEBUG_SHOW_WINDING
     SkOpContour::debugShowWindingValues(contourList);
 #endif
     fixOtherTIndex(contourList);
-    checkEnds(contourList);  // check if connecting curve intersected at the same end
+    if (!checkEnds(contourList)) {  // check if connecting curve intersected at the same end
+        return false;
+    }
     bool hasM = checkMultiples(contourList);  // check if intersections agree on t and point values
     SkTDArray<SkOpSegment::AlignedSpan> aligned;
     if (hasM) {
         alignMultiples(contourList, &aligned);  // align pairs of identical points
         alignCoincidence(contourList, aligned);
     }
     checkDuplicates(contourList);  // check if spans have the same number on the other end
     checkTiny(contourList);  // if pair have the same end points, mark them as parallel
     checkSmall(contourList);  // a pair of curves with a small span may turn into coincident lines
     joinCoincidence(contourList);  // join curves that connect to a coincident pair
     sortSegments(contourList);
     if (!calcAngles(contourList)) {
         return false;
     }
     sortAngles(contourList);
 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
     DebugShowActiveSpans(*contourList);
 #endif
     return true;
 }