pathops coincidence and security rewrite

src/pathops/SkOpSpan.h

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #ifndef SkOpSpan_DEFINED
 #define SkOpSpan_DEFINED
 
 #include "SkPathOpsDebug.h"
 #include "SkPathOpsTypes.h"
 #include "SkPoint.h"
 
 class SkChunkAlloc;
-struct SkOpAngle;
+class SkOpAngle;
 class SkOpContour;
 class SkOpGlobalState;
 class SkOpSegment;
 class SkOpSpanBase;
 class SkOpSpan;
+struct SkPathOpsBounds;
 
 // subset of op span used by terminal span (when t is equal to one)
 class SkOpPtT {
 public:
     enum {
         kIsAlias = 1,
         kIsDuplicate = 1
     };
 
-    void addOpp(SkOpPtT* opp) {
+    // please keep in sync with debugAddOpp()
+    bool addOpp(SkOpPtT* opp) {
         // find the fOpp ptr to opp
         SkOpPtT* oppPrev = opp->fNext;
         if (oppPrev == this) {
-            return;
+            return false;
         }
         while (oppPrev->fNext != opp) {
             oppPrev = oppPrev->fNext;
-             if (oppPrev == this) {
-                 return;
-             }
+            if (oppPrev == this) {
+                return false;
+            }
         }
-        
         SkOpPtT* oldNext = this->fNext;
         SkASSERT(this != opp);
         this->fNext = opp;
         SkASSERT(oppPrev != oldNext);
         oppPrev->fNext = oldNext;
+        return true;
     }
 
     bool alias() const;
+    bool coincident() const { return fCoincident; }
     bool collapsed(const SkOpPtT* ) const;
     bool contains(const SkOpPtT* ) const;
-    SkOpPtT* contains(const SkOpSegment* );
+    bool contains(const SkOpSegment*, const SkPoint& ) const;
+    bool contains(const SkOpSegment*, double t) const;
+    const SkOpPtT* contains(const SkOpSegment* ) const;
     SkOpContour* contour() const;
 
     int debugID() const {
         return SkDEBUGRELEASE(fID, -1);
     }
 
+    bool debugAddOpp(const SkOpPtT* opp) const;
     const SkOpAngle* debugAngle(int id) const;
+    const SkOpCoincidence* debugCoincidence() const;
     bool debugContains(const SkOpPtT* ) const;
     const SkOpPtT* debugContains(const SkOpSegment* check) const;
     SkOpContour* debugContour(int id);
     int debugLoopLimit(bool report) const;
     bool debugMatchID(int id) const;
     const SkOpPtT* debugPtT(int id) const;
     const SkOpSegment* debugSegment(int id) const;
     const SkOpSpanBase* debugSpan(int id) const;
     void debugValidate() const;
 
     bool deleted() const {
         return fDeleted;
     }
 
-    SkOpPtT* doppelganger();
-
     bool duplicate() const {
         return fDuplicatePt;
     }
 
     void dump() const;  // available to testing only
     void dumpAll() const;
     void dumpBase() const;
 
-    SkOpPtT* find(SkOpSegment* );
+    const SkOpPtT* find(const SkOpSegment* ) const;
     SkOpGlobalState* globalState() const;
     void init(SkOpSpanBase* , double t, const SkPoint& , bool dup);
 
     void insert(SkOpPtT* span) {
         SkASSERT(span != this);
         span->fNext = fNext;
         fNext = span;
     }
 
     const SkOpPtT* next() const {
         return fNext;
     }
 
     SkOpPtT* next() {
         return fNext;
     }
 
     bool onEnd() const;
 
-    static bool Overlaps(SkOpPtT* s1, SkOpPtT* e1, SkOpPtT* s2, SkOpPtT* e2,
-            SkOpPtT** sOut, SkOpPtT** eOut) {
-        SkOpPtT* start1 = s1->fT < e1->fT ? s1 : e1;
-        SkOpPtT* start2 = s2->fT < e2->fT ? s2 : e2;
+    static bool Overlaps(const SkOpPtT* s1, const SkOpPtT* e1, const SkOpPtT* s2,
+            const SkOpPtT* e2, const SkOpPtT** sOut, const SkOpPtT** eOut) {
+        const SkOpPtT* start1 = s1->fT < e1->fT ? s1 : e1;
+        const SkOpPtT* start2 = s2->fT < e2->fT ? s2 : e2;
         *sOut = between(s1->fT, start2->fT, e1->fT) ? start2
                 : between(s2->fT, start1->fT, e2->fT) ? start1 : nullptr;
-        SkOpPtT* end1 = s1->fT < e1->fT ? e1 : s1;
-        SkOpPtT* end2 = s2->fT < e2->fT ? e2 : s2;
+        const SkOpPtT* end1 = s1->fT < e1->fT ? e1 : s1;
+        const SkOpPtT* end2 = s2->fT < e2->fT ? e2 : s2;
         *eOut = between(s1->fT, end2->fT, e1->fT) ? end2
                 : between(s2->fT, end1->fT, e2->fT) ? end1 : nullptr;
         if (*sOut == *eOut) {
             SkASSERT(start1->fT >= end2->fT || start2->fT >= end1->fT);
             return false;
         }
         SkASSERT(!*sOut || *sOut != *eOut);
         return *sOut && *eOut;
     }
 
+    bool ptAlreadySeen(const SkOpPtT* head) const;
     SkOpPtT* prev();
-    SkOpPtT* remove();
-    void removeNext(SkOpPtT* kept);
+    SkOpPtT* remove(const SkOpPtT* kept);
+    void removeNext(const SkOpPtT* kept);
 
     const SkOpSegment* segment() const;
     SkOpSegment* segment();
 
-    void setDeleted() {
+    void setCoincident() const {
         SkASSERT(!fDeleted);
-        fDeleted = true;
+        fCoincident = true;
+    }
+
+    void setDeleted();
+
+    void setSpan(const SkOpSpanBase* span) {
+        fSpan = const_cast<SkOpSpanBase*>(span);
     }
 
     const SkOpSpanBase* span() const {
         return fSpan;
     }
 
     SkOpSpanBase* span() {
         return fSpan;
     }
 
     const SkOpPtT* starter(const SkOpPtT* end) const {
         return fT < end->fT ? this : end;
     }
 
-    double fT; 
+    double fT;
     SkPoint fPt;   // cache of point value at this t
 protected:
     SkOpSpanBase* fSpan;  // contains winding data
     SkOpPtT* fNext;  // intersection on opposite curve or alias on this curve
-    bool fDeleted;  // set if removed from span list 
+    bool fDeleted;  // set if removed from span list
     bool fDuplicatePt;  // set if identical pt is somewhere in the next loop
+    // below mutable since referrer is otherwise always const
+    mutable bool fCoincident;  // set if at some point a coincident span pointed here
     SkDEBUGCODE(int fID);
 };
 
 class SkOpSpanBase {
 public:
-    void align();
-
-    bool aligned() const {
-        return fAligned;
-    }
-
-    void alignEnd(double t, const SkPoint& pt);
+    void addOppAndMerge(SkOpSpanBase* );
 
     void bumpSpanAdds() {
         ++fSpanAdds;
     }
 
     bool chased() const {
         return fChased;
     }
 
-    void clearCoinEnd() {
-        SkASSERT(fCoinEnd != this);
-        fCoinEnd = this;
-    }
+    void checkForCollapsedCoincidence();
 
     const SkOpSpanBase* coinEnd() const {
         return fCoinEnd;
     }
 
     bool contains(const SkOpSpanBase* ) const;
-    SkOpPtT* contains(const SkOpSegment* );
+    const SkOpPtT* contains(const SkOpSegment* ) const;
 
     bool containsCoinEnd(const SkOpSpanBase* coin) const {
         SkASSERT(this != coin);
         const SkOpSpanBase* next = this;
         while ((next = next->fCoinEnd) != this) {
             if (next == coin) {
                 return true;
             }
         }
         return false;
     }
 
     bool containsCoinEnd(const SkOpSegment* ) const;
     SkOpContour* contour() const;
 
+#if DEBUG_COINCIDENCE_VERBOSE
+    void debugAddOppAndMerge(const char* id, SkPathOpsDebug::GlitchLog* , const SkOpSpanBase* ,
+                             bool* del1, bool* del2) const;
+#endif
+
     int debugBumpCount() {
         return SkDEBUGRELEASE(++fCount, -1);
     }
 
     int debugID() const {
         return SkDEBUGRELEASE(fID, -1);
     }
 
     bool debugAlignedEnd(double t, const SkPoint& pt) const;
     bool debugAlignedInner() const;
     const SkOpAngle* debugAngle(int id) const;
+#if DEBUG_COINCIDENCE_VERBOSE
+    void debugCheckForCollapsedCoincidence(const char* id, SkPathOpsDebug::GlitchLog* ) const;
+#endif
+    const SkOpCoincidence* debugCoincidence() const;
     bool debugCoinEndLoopCheck() const;
-    bool debugContains(const SkOpSegment* ) const;
     SkOpContour* debugContour(int id);
+#ifdef SK_DEBUG
+    bool debugDeleted() const { return fDeleted; }
+#endif
+#if DEBUG_COINCIDENCE_VERBOSE
+    void debugInsertCoinEnd(const char* id, SkPathOpsDebug::GlitchLog* ,
+                            const SkOpSpanBase* ) const;
+    void debugMergeContained(const char* id, SkPathOpsDebug::GlitchLog* ,
+                             const SkPathOpsBounds& bounds, bool* deleted) const;
+#endif
     const SkOpPtT* debugPtT(int id) const;
     const SkOpSegment* debugSegment(int id) const;
     const SkOpSpanBase* debugSpan(int id) const;
     const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const;
     SkOpGlobalState* globalState() const;
     void debugValidate() const;
 
     bool deleted() const {
         return fPtT.deleted();
     }
 
     void dump() const;  // available to testing only
     void dumpCoin() const;
     void dumpAll() const;
     void dumpBase() const;
+    void dumpHead() const;
 
     bool final() const {
         return fPtT.fT == 1;
     }
 
     SkOpAngle* fromAngle() const {
         return fFromAngle;
     }
 
     void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
 
+    // Please keep this in sync with debugInsertCoinEnd()
     void insertCoinEnd(SkOpSpanBase* coin) {
         if (containsCoinEnd(coin)) {
             SkASSERT(coin->containsCoinEnd(this));
             return;
         }
         debugValidate();
         SkASSERT(this != coin);
         SkOpSpanBase* coinNext = coin->fCoinEnd;
         coin->fCoinEnd = this->fCoinEnd;
         this->fCoinEnd = coinNext;
         debugValidate();
     }
 
     void merge(SkOpSpan* span);
+    void mergeContained(const SkPathOpsBounds& bounds);
 
-    SkOpSpan* prev() const {
+    const SkOpSpan* prev() const {
         return fPrev;
     }
 
+    SkOpSpan* prev() {
+        return fPrev;
+    }
+
     const SkPoint& pt() const {
         return fPtT.fPt;
     }
 
     const SkOpPtT* ptT() const {
         return &fPtT;
     }
 
     SkOpPtT* ptT() {
         return &fPtT;
     }
 
     SkOpSegment* segment() const {
         return fSegment;
     }
 
     void setAligned() {
         fAligned = true;
     }
 
     void setChased(bool chased) {
         fChased = chased;
     }
 
-    SkOpPtT* setCoinEnd(SkOpSpanBase* oldCoinEnd, SkOpSegment* oppSegment);
-
     void setFromAngle(SkOpAngle* angle) {
         fFromAngle = angle;
     }
 
     void setPrev(SkOpSpan* prev) {
         fPrev = prev;
     }
 
     bool simple() const {
         fPtT.debugValidate();
-        return fPtT.next()->next() == &fPtT; 
+        return fPtT.next()->next() == &fPtT;
     }
 
     int spanAddsCount() const {
         return fSpanAdds;
     }
 
     const SkOpSpan* starter(const SkOpSpanBase* end) const {
         const SkOpSpanBase* result = t() < end->t() ? this : end;
         return result->upCast();
     }
@@ skipping 54 matching lines @@
     SkOpPtT fPtT;  // list of points and t values associated with the start of this span
     SkOpSegment* fSegment;  // segment that contains this span
     SkOpSpanBase* fCoinEnd;  // linked list of coincident spans that end here (may point to itself)
     SkOpAngle* fFromAngle;  // points to next angle from span start to end
     SkOpSpan* fPrev;  // previous intersection point
     int fSpanAdds;  // number of times intersections have been added to span
     bool fAligned;
     bool fChased;  // set after span has been added to chase array
     SkDEBUGCODE(int fCount);  // number of pt/t pairs added
     SkDEBUGCODE(int fID);
+    SkDEBUGCODE(bool fDeleted);  // set when span was merged with another span
 };
 
 class SkOpSpan : public SkOpSpanBase {
 public:
     bool alreadyAdded() const {
         if (fAlreadyAdded) {
             return true;
         }
         fAlreadyAdded = true;
         return false;
@@ skipping 16 matching lines @@
         const SkOpSpan* next = this;
         while ((next = next->fCoincident) != this) {
             if (next == coin) {
                 return true;
             }
         }
         return false;
     }
 
     bool debugCoinLoopCheck() const;
-    void release(SkOpPtT* );
+#if DEBUG_COINCIDENCE_VERBOSE
+    void debugInsertCoincidence(const char* , SkPathOpsDebug::GlitchLog* , const SkOpSpan* ) const;
+    void debugInsertCoincidence(const char* , SkPathOpsDebug::GlitchLog* ,
+                                const SkOpSegment* , bool flipped) const;
+#endif
+    void release(const SkOpPtT* );
 
     bool done() const {
         SkASSERT(!final());
         return fDone;
     }
 
     void dumpCoin() const;
     bool dumpSpan() const;
     void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
+    bool insertCoincidence(const SkOpSegment* , bool flipped);
 
+    // Please keep this in sync with debugInsertCoincidence()
     void insertCoincidence(SkOpSpan* coin) {
         if (containsCoincidence(coin)) {
             SkASSERT(coin->containsCoincidence(this));
             return;
         }
         debugValidate();
         SkASSERT(this != coin);
         SkOpSpan* coinNext = coin->fCoincident;
         coin->fCoincident = this->fCoincident;
         this->fCoincident = coinNext;
@@ skipping 35 matching lines @@
     void setNext(SkOpSpanBase* nextT) {
         SkASSERT(!final());
         fNext = nextT;
     }
 
     void setOppSum(int oppSum);
 
     void setOppValue(int oppValue) {
         SkASSERT(!final());
         SkASSERT(fOppSum == SK_MinS32);
+        SkASSERT(!oppValue || !fDone);
         fOppValue = oppValue;
     }
 
     void setToAngle(SkOpAngle* angle) {
         SkASSERT(!final());
         fToAngle = angle;
     }
 
     void setWindSum(int windSum);
 
     void setWindValue(int windValue) {
         SkASSERT(!final());
         SkASSERT(windValue >= 0);
         SkASSERT(fWindSum == SK_MinS32);
+        SkASSERT(!windValue || !fDone);
         fWindValue = windValue;
     }
 
     bool sortableTop(SkOpContour* );
 
     SkOpAngle* toAngle() const {
         SkASSERT(!final());
         return fToAngle;
     }
 
@@ skipping 14 matching lines @@
     int fWindSum;  // accumulated from contours surrounding this one.
     int fOppSum;  // for binary operators: the opposite winding sum
     int fWindValue;  // 0 == canceled; 1 == normal; >1 == coincident
     int fOppValue;  // normally 0 -- when binary coincident edges combine, opp value goes here
     int fTopTTry; // specifies direction and t value to try next
     bool fDone;  // if set, this span to next higher T has been processed
     mutable bool fAlreadyAdded;
 };
 
 #endif