1/*
2 * Copyright 2015 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "SkOpCoincidence.h"
8#include "SkOpSegment.h"
9#include "SkPathOpsTSect.h"
10
11// returns true if coincident span's start and end are the same
12bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const {
13    return (fCoinPtTStart == test && fCoinPtTEnd->contains(test))
14        || (fCoinPtTEnd == test && fCoinPtTStart->contains(test))
15        || (fOppPtTStart == test && fOppPtTEnd->contains(test))
16        || (fOppPtTEnd == test && fOppPtTStart->contains(test));
17}
18
19// out of line since this function is referenced by address
20const SkOpPtT* SkCoincidentSpans::coinPtTEnd() const {
21    return fCoinPtTEnd;
22}
23
24// out of line since this function is referenced by address
25const SkOpPtT* SkCoincidentSpans::coinPtTStart() const {
26    return fCoinPtTStart;
27}
28
29// sets the span's end to the ptT referenced by the previous-next
30void SkCoincidentSpans::correctOneEnd(
31        const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
32        void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) {
33    const SkOpPtT* origPtT = (this->*getEnd)();
34    const SkOpSpanBase* origSpan = origPtT->span();
35    const SkOpSpan* prev = origSpan->prev();
36    const SkOpPtT* testPtT = prev ? prev->next()->ptT()
37            : origSpan->upCast()->next()->prev()->ptT();
38    if (origPtT != testPtT) {
39        (this->*setEnd)(testPtT);
40    }
41}
42
43/* Please keep this in sync with debugCorrectEnds */
44// FIXME: member pointers have fallen out of favor and can be replaced with
45// an alternative approach.
46// makes all span ends agree with the segment's spans that define them
47void SkCoincidentSpans::correctEnds() {
48    this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart);
49    this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd);
50    this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart);
51    this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd);
52}
53
54/* Please keep this in sync with debugExpand */
55// expand the range by checking adjacent spans for coincidence
56bool SkCoincidentSpans::expand() {
57    bool expanded = false;
58    const SkOpSegment* segment = coinPtTStart()->segment();
59    const SkOpSegment* oppSegment = oppPtTStart()->segment();
60    do {
61        const SkOpSpan* start = coinPtTStart()->span()->upCast();
62        const SkOpSpan* prev = start->prev();
63        const SkOpPtT* oppPtT;
64        if (!prev || !(oppPtT = prev->contains(oppSegment))) {
65            break;
66        }
67        double midT = (prev->t() + start->t()) / 2;
68        if (!segment->isClose(midT, oppSegment)) {
69            break;
70        }
71        setStarts(prev->ptT(), oppPtT);
72        expanded = true;
73    } while (true);
74    do {
75        const SkOpSpanBase* end = coinPtTEnd()->span();
76        SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
77        if (next && next->deleted()) {
78            break;
79        }
80        const SkOpPtT* oppPtT;
81        if (!next || !(oppPtT = next->contains(oppSegment))) {
82            break;
83        }
84        double midT = (end->t() + next->t()) / 2;
85        if (!segment->isClose(midT, oppSegment)) {
86            break;
87        }
88        setEnds(next->ptT(), oppPtT);
89        expanded = true;
90    } while (true);
91    return expanded;
92}
93
94// increase the range of this span
95bool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
96        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
97    bool result = false;
98    if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped()
99            ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) {
100        this->setStarts(coinPtTStart, oppPtTStart);
101        result = true;
102    }
103    if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped()
104            ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) {
105        this->setEnds(coinPtTEnd, oppPtTEnd);
106        result = true;
107    }
108    return result;
109}
110
111// set the range of this span
112void SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart,
113        const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
114    SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart));
115    fNext = next;
116    this->setStarts(coinPtTStart, oppPtTStart);
117    this->setEnds(coinPtTEnd, oppPtTEnd);
118}
119
120// returns true if both points are inside this
121bool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const {
122    if (s->fT > e->fT) {
123        SkTSwap(s, e);
124    }
125    if (s->segment() == fCoinPtTStart->segment()) {
126        return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT;
127    } else {
128        SkASSERT(s->segment() == fOppPtTStart->segment());
129        double oppTs = fOppPtTStart->fT;
130        double oppTe = fOppPtTEnd->fT;
131        if (oppTs > oppTe) {
132            SkTSwap(oppTs, oppTe);
133        }
134        return oppTs <= s->fT && e->fT <= oppTe;
135    }
136}
137
138// out of line since this function is referenced by address
139const SkOpPtT* SkCoincidentSpans::oppPtTStart() const {
140    return fOppPtTStart;
141}
142
143// out of line since this function is referenced by address
144const SkOpPtT* SkCoincidentSpans::oppPtTEnd() const {
145    return fOppPtTEnd;
146}
147
148// A coincident span is unordered if the pairs of points in the main and opposite curves'
149// t values do not ascend or descend. For instance, if a tightly arced quadratic is
150// coincident with another curve, it may intersect it out of order.
151bool SkCoincidentSpans::ordered(bool* result) const {
152    const SkOpSpanBase* start = this->coinPtTStart()->span();
153    const SkOpSpanBase* end = this->coinPtTEnd()->span();
154    const SkOpSpanBase* next = start->upCast()->next();
155    if (next == end) {
156        *result = true;
157        return true;
158    }
159    bool flipped = this->flipped();
160    const SkOpSegment* oppSeg = this->oppPtTStart()->segment();
161    double oppLastT = fOppPtTStart->fT;
162    do {
163        const SkOpPtT* opp = next->contains(oppSeg);
164        if (!opp) {
165//            SkOPOBJASSERT(start, 0);  // may assert if coincident span isn't fully processed
166            return false;
167        }
168        if ((oppLastT > opp->fT) != flipped) {
169            *result = false;
170            return true;
171        }
172        oppLastT = opp->fT;
173        if (next == end) {
174            break;
175        }
176        if (!next->upCastable()) {
177            *result = false;
178            return true;
179        }
180        next = next->upCast()->next();
181    } while (true);
182    *result = true;
183    return true;
184}
185
186// if there is an existing pair that overlaps the addition, extend it
187bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
188        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
189    SkCoincidentSpans* test = fHead;
190    if (!test) {
191        return false;
192    }
193    const SkOpSegment* coinSeg = coinPtTStart->segment();
194    const SkOpSegment* oppSeg = oppPtTStart->segment();
195    if (!Ordered(coinPtTStart, oppPtTStart)) {
196        SkTSwap(coinSeg, oppSeg);
197        SkTSwap(coinPtTStart, oppPtTStart);
198        SkTSwap(coinPtTEnd, oppPtTEnd);
199        if (coinPtTStart->fT > coinPtTEnd->fT) {
200            SkTSwap(coinPtTStart, coinPtTEnd);
201            SkTSwap(oppPtTStart, oppPtTEnd);
202        }
203    }
204    double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT);
205    SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT));
206    do {
207        if (coinSeg != test->coinPtTStart()->segment()) {
208            continue;
209        }
210        if (oppSeg != test->oppPtTStart()->segment()) {
211            continue;
212        }
213        double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
214        double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
215        // if debug check triggers, caller failed to check if extended already exists
216        SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT
217                || coinPtTEnd->fT > test->coinPtTEnd()->fT
218                || oTestMinT > oppMinT || oppMaxT > oTestMaxT);
219        if ((test->coinPtTStart()->fT <= coinPtTEnd->fT
220                && coinPtTStart->fT <= test->coinPtTEnd()->fT)
221                || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) {
222            test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
223            return true;
224        }
225    } while ((test = test->next()));
226    return false;
227}
228
229// verifies that the coincidence hasn't already been added
230static void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart,
231        const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
232#if DEBUG_COINCIDENCE
233    while (check) {
234        SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd
235                || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd);
236        SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd
237                || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd);
238        check = check->next();
239    }
240#endif
241}
242
243// adds a new coincident pair
244void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
245        SkOpPtT* oppPtTEnd) {
246    // OPTIMIZE: caller should have already sorted
247    if (!Ordered(coinPtTStart, oppPtTStart)) {
248        if (oppPtTStart->fT < oppPtTEnd->fT) {
249            this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd);
250        } else {
251            this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart);
252        }
253        return;
254    }
255    SkASSERT(Ordered(coinPtTStart, oppPtTStart));
256    // choose the ptT at the front of the list to track
257    coinPtTStart = coinPtTStart->span()->ptT();
258    coinPtTEnd = coinPtTEnd->span()->ptT();
259    oppPtTStart = oppPtTStart->span()->ptT();
260    oppPtTEnd = oppPtTEnd->span()->ptT();
261    SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT);
262    SkOPASSERT(oppPtTStart->fT != oppPtTEnd->fT);
263    SkOPASSERT(!coinPtTStart->deleted());
264    SkOPASSERT(!coinPtTEnd->deleted());
265    SkOPASSERT(!oppPtTStart->deleted());
266    SkOPASSERT(!oppPtTEnd->deleted());
267    DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
268    DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
269    SkCoincidentSpans* coinRec = this->globalState()->allocator()->make<SkCoincidentSpans>();
270    coinRec->init(SkDEBUGCODE(fGlobalState));
271    coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
272    fHead = coinRec;
273}
274
275// description below
276bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) {
277    const SkOpPtT* testPtT = testSpan->ptT();
278    const SkOpPtT* stopPtT = testPtT;
279    const SkOpSegment* baseSeg = base->segment();
280    int escapeHatch = 100000;  // this is 100 times larger than the debugLoopLimit test
281    while ((testPtT = testPtT->next()) != stopPtT) {
282        if (--escapeHatch <= 0) {
283            return false;  // if triggered (likely by a fuzz-generated test) too complex to succeed
284        }
285        const SkOpSegment* testSeg = testPtT->segment();
286        if (testPtT->deleted()) {
287            continue;
288        }
289        if (testSeg == baseSeg) {
290            continue;
291        }
292        if (testPtT->span()->ptT() != testPtT) {
293            continue;
294        }
295        if (this->contains(baseSeg, testSeg, testPtT->fT)) {
296            continue;
297        }
298        // intersect perp with base->ptT() with testPtT->segment()
299        SkDVector dxdy = baseSeg->dSlopeAtT(base->t());
300        const SkPoint& pt = base->pt();
301        SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}};
302        SkIntersections i  SkDEBUGCODE((this->globalState()));
303        (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i);
304        for (int index = 0; index < i.used(); ++index) {
305            double t = i[0][index];
306            if (!between(0, t, 1)) {
307                continue;
308            }
309            SkDPoint oppPt = i.pt(index);
310            if (!oppPt.approximatelyEqual(pt)) {
311                continue;
312            }
313            SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
314            SkOpPtT* oppStart = writableSeg->addT(t);
315            if (oppStart == testPtT) {
316                continue;
317            }
318            SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
319            oppStart->span()->addOpp(writableBase);
320            if (oppStart->deleted()) {
321                continue;
322            }
323            SkOpSegment* coinSeg = base->segment();
324            SkOpSegment* oppSeg = oppStart->segment();
325            double coinTs, coinTe, oppTs, oppTe;
326            if (Ordered(coinSeg, oppSeg)) {
327                coinTs = base->t();
328                coinTe = testSpan->t();
329                oppTs = oppStart->fT;
330                oppTe = testPtT->fT;
331            } else {
332                SkTSwap(coinSeg, oppSeg);
333                coinTs = oppStart->fT;
334                coinTe = testPtT->fT;
335                oppTs = base->t();
336                oppTe = testSpan->t();
337            }
338            if (coinTs > coinTe) {
339                SkTSwap(coinTs, coinTe);
340                SkTSwap(oppTs, oppTe);
341            }
342            bool added;
343            if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) {
344                return false;
345            }
346        }
347    }
348    return true;
349}
350
351// description below
352bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) {
353    FAIL_IF(!ptT->span()->upCastable());
354    const SkOpSpan* base = ptT->span()->upCast();
355    const SkOpSpan* prev = base->prev();
356    FAIL_IF(!prev);
357    if (!prev->isCanceled()) {
358        if (!this->addEndMovedSpans(base, base->prev())) {
359            return false;
360        }
361    }
362    if (!base->isCanceled()) {
363        if (!this->addEndMovedSpans(base, base->next())) {
364            return false;
365        }
366    }
367    return true;
368}
369
370/*  If A is coincident with B and B includes an endpoint, and A's matching point
371    is not the endpoint (i.e., there's an implied line connecting B-end and A)
372    then assume that the same implied line may intersect another curve close to B.
373    Since we only care about coincidence that was undetected, look at the
374    ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but
375    next door) and see if the A matching point is close enough to form another
376    coincident pair. If so, check for a new coincident span between B-end/A ptT loop
377    and the adjacent ptT loop.
378*/
379bool SkOpCoincidence::addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
380    DEBUG_SET_PHASE();
381    SkCoincidentSpans* span = fHead;
382    if (!span) {
383        return true;
384    }
385    fTop = span;
386    fHead = nullptr;
387    do {
388        if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
389            FAIL_IF(1 == span->coinPtTStart()->fT);
390            bool onEnd = span->coinPtTStart()->fT == 0;
391            bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
392            if (onEnd) {
393                if (!oOnEnd) {  // if both are on end, any nearby intersect was already found
394                    if (!this->addEndMovedSpans(span->oppPtTStart())) {
395                        return false;
396                    }
397                }
398            } else if (oOnEnd) {
399                if (!this->addEndMovedSpans(span->coinPtTStart())) {
400                    return false;
401                }
402            }
403        }
404        if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) {
405            bool onEnd = span->coinPtTEnd()->fT == 1;
406            bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT);
407            if (onEnd) {
408                if (!oOnEnd) {
409                    if (!this->addEndMovedSpans(span->oppPtTEnd())) {
410                        return false;
411                    }
412                }
413            } else if (oOnEnd) {
414                if (!this->addEndMovedSpans(span->coinPtTEnd())) {
415                    return false;
416                }
417            }
418        }
419    } while ((span = span->next()));
420    this->restoreHead();
421    return true;
422}
423
424/* Please keep this in sync with debugAddExpanded */
425// for each coincident pair, match the spans
426// if the spans don't match, add the missing pt to the segment and loop it in the opposite span
427bool SkOpCoincidence::addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
428    DEBUG_SET_PHASE();
429    SkCoincidentSpans* coin = this->fHead;
430    if (!coin) {
431        return true;
432    }
433    do {
434        const SkOpPtT* startPtT = coin->coinPtTStart();
435        const SkOpPtT* oStartPtT = coin->oppPtTStart();
436        double priorT = startPtT->fT;
437        double oPriorT = oStartPtT->fT;
438        FAIL_IF(!startPtT->contains(oStartPtT));
439        SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
440        const SkOpSpanBase* start = startPtT->span();
441        const SkOpSpanBase* oStart = oStartPtT->span();
442        const SkOpSpanBase* end = coin->coinPtTEnd()->span();
443        const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
444        FAIL_IF(oEnd->deleted());
445        FAIL_IF(!start->upCastable());
446        const SkOpSpanBase* test = start->upCast()->next();
447        FAIL_IF(!coin->flipped() && !oStart->upCastable());
448        const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
449        FAIL_IF(!oTest);
450        SkOpSegment* seg = start->segment();
451        SkOpSegment* oSeg = oStart->segment();
452        while (test != end || oTest != oEnd) {
453            const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
454            const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
455            if (!containedOpp || !containedThis) {
456                // choose the ends, or the first common pt-t list shared by both
457                double nextT, oNextT;
458                if (containedOpp) {
459                    nextT = test->t();
460                    oNextT = containedOpp->fT;
461                } else if (containedThis) {
462                    nextT = containedThis->fT;
463                    oNextT = oTest->t();
464                } else {
465                    // iterate through until a pt-t list found that contains the other
466                    const SkOpSpanBase* walk = test;
467                    const SkOpPtT* walkOpp;
468                    do {
469                        FAIL_IF(!walk->upCastable());
470                        walk = walk->upCast()->next();
471                    } while (!(walkOpp = walk->ptT()->contains(oSeg))
472                            && walk != coin->coinPtTEnd()->span());
473                    FAIL_IF(!walkOpp);
474                    nextT = walk->t();
475                    oNextT = walkOpp->fT;
476                }
477                // use t ranges to guess which one is missing
478                double startRange = nextT - priorT;
479                FAIL_IF(!startRange);
480                double startPart = (test->t() - priorT) / startRange;
481                double oStartRange = oNextT - oPriorT;
482                FAIL_IF(!oStartRange);
483                double oStartPart = (oTest->t() - oPriorT) / oStartRange;
484                FAIL_IF(startPart == oStartPart);
485                bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
486                        : !!containedThis;
487                bool startOver = false;
488                bool success = addToOpp ? oSeg->addExpanded(
489                        oPriorT + oStartRange * startPart, test, &startOver)
490                        : seg->addExpanded(
491                        priorT + startRange * oStartPart, oTest, &startOver);
492                FAIL_IF(!success);
493                if (startOver) {
494                    test = start;
495                    oTest = oStart;
496                }
497                end = coin->coinPtTEnd()->span();
498                oEnd = coin->oppPtTEnd()->span();
499            }
500            if (test != end) {
501                FAIL_IF(!test->upCastable());
502                priorT = test->t();
503                test = test->upCast()->next();
504            }
505            if (oTest != oEnd) {
506                oPriorT = oTest->t();
507                if (coin->flipped()) {
508                    oTest = oTest->prev();
509                } else {
510                    FAIL_IF(!oTest->upCastable());
511                    oTest = oTest->upCast()->next();
512                }
513                FAIL_IF(!oTest);
514            }
515
516        }
517    } while ((coin = coin->next()));
518    return true;
519}
520
521// given a t span, map the same range on the coincident span
522/*
523the curves may not scale linearly, so interpolation may only happen within known points
524remap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s
525then repeat to capture over1e
526*/
527double SkOpCoincidence::TRange(const SkOpPtT* overS, double t,
528       const SkOpSegment* coinSeg  SkDEBUGPARAMS(const SkOpPtT* overE)) {
529    const SkOpSpanBase* work = overS->span();
530    const SkOpPtT* foundStart = nullptr;
531    const SkOpPtT* foundEnd = nullptr;
532    const SkOpPtT* coinStart = nullptr;
533    const SkOpPtT* coinEnd = nullptr;
534    do {
535        const SkOpPtT* contained = work->contains(coinSeg);
536        if (!contained) {
537            if (work->final()) {
538                break;
539            }
540            continue;
541        }
542        if (work->t() <= t) {
543            coinStart = contained;
544            foundStart = work->ptT();
545        }
546        if (work->t() >= t) {
547            coinEnd = contained;
548            foundEnd = work->ptT();
549            break;
550        }
551        SkASSERT(work->ptT() != overE);
552    } while ((work = work->upCast()->next()));
553    if (!coinStart || !coinEnd) {
554        return 1;
555    }
556    // while overS->fT <=t and overS contains coinSeg
557    double denom = foundEnd->fT - foundStart->fT;
558    double sRatio = denom ? (t - foundStart->fT) / denom : 1;
559    return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio;
560}
561
562// return true if span overlaps existing and needs to adjust the coincident list
563bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check,
564        const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
565        double coinTs, double coinTe, double oppTs, double oppTe,
566        SkTDArray<SkCoincidentSpans*>* overlaps) const {
567    if (!Ordered(coinSeg, oppSeg)) {
568        if (oppTs < oppTe) {
569            return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe,
570                    overlaps);
571        }
572        return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps);
573    }
574    bool swapOpp = oppTs > oppTe;
575    if (swapOpp) {
576        SkTSwap(oppTs, oppTe);
577    }
578    do {
579        if (check->coinPtTStart()->segment() != coinSeg) {
580            continue;
581        }
582        if (check->oppPtTStart()->segment() != oppSeg) {
583            continue;
584        }
585        double checkTs = check->coinPtTStart()->fT;
586        double checkTe = check->coinPtTEnd()->fT;
587        bool coinOutside = coinTe < checkTs || coinTs > checkTe;
588        double oCheckTs = check->oppPtTStart()->fT;
589        double oCheckTe = check->oppPtTEnd()->fT;
590        if (swapOpp) {
591            if (oCheckTs <= oCheckTe) {
592                return false;
593            }
594            SkTSwap(oCheckTs, oCheckTe);
595        }
596        bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe;
597        if (coinOutside && oppOutside) {
598            continue;
599        }
600        bool coinInside = coinTe <= checkTe && coinTs >= checkTs;
601        bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs;
602        if (coinInside && oppInside) {  // already included, do nothing
603            return false;
604        }
605        *overlaps->append() = check; // partial overlap, extend existing entry
606    } while ((check = check->next()));
607    return true;
608}
609
610/* Please keep this in sync with debugAddIfMissing() */
611// note that over1s, over1e, over2s, over2e are ordered
612bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
613        double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added
614        SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) {
615    SkASSERT(tStart < tEnd);
616    SkASSERT(over1s->fT < over1e->fT);
617    SkASSERT(between(over1s->fT, tStart, over1e->fT));
618    SkASSERT(between(over1s->fT, tEnd, over1e->fT));
619    SkASSERT(over2s->fT < over2e->fT);
620    SkASSERT(between(over2s->fT, tStart, over2e->fT));
621    SkASSERT(between(over2s->fT, tEnd, over2e->fT));
622    SkASSERT(over1s->segment() == over1e->segment());
623    SkASSERT(over2s->segment() == over2e->segment());
624    SkASSERT(over1s->segment() == over2s->segment());
625    SkASSERT(over1s->segment() != coinSeg);
626    SkASSERT(over1s->segment() != oppSeg);
627    SkASSERT(coinSeg != oppSeg);
628    double coinTs, coinTe, oppTs, oppTe;
629    coinTs = TRange(over1s, tStart, coinSeg  SkDEBUGPARAMS(over1e));
630    coinTe = TRange(over1s, tEnd, coinSeg  SkDEBUGPARAMS(over1e));
631    if (coinSeg->collapsed(coinTs, coinTe)) {
632        return true;
633    }
634    oppTs = TRange(over2s, tStart, oppSeg  SkDEBUGPARAMS(over2e));
635    oppTe = TRange(over2s, tEnd, oppSeg  SkDEBUGPARAMS(over2e));
636    if (oppSeg->collapsed(oppTs, oppTe)) {
637        return true;
638    }
639    if (coinTs > coinTe) {
640        SkTSwap(coinTs, coinTe);
641        SkTSwap(oppTs, oppTe);
642    }
643    return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added);
644}
645
646/* Please keep this in sync with debugAddOrOverlap() */
647// If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
648// If this is called by AddIfMissing(), a returned false indicates there was nothing to add
649bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
650        double coinTs, double coinTe, double oppTs, double oppTe, bool* added) {
651    SkTDArray<SkCoincidentSpans*> overlaps;
652    FAIL_IF(!fTop);
653    if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
654        return true;
655    }
656    if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
657            coinTe, oppTs, oppTe, &overlaps)) {
658        return true;
659    }
660    SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
661    for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
662        SkCoincidentSpans* test = overlaps[index];
663        if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
664            overlap->setCoinPtTStart(test->coinPtTStart());
665        }
666        if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
667            overlap->setCoinPtTEnd(test->coinPtTEnd());
668        }
669        if (overlap->flipped()
670                ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
671                : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
672            overlap->setOppPtTStart(test->oppPtTStart());
673        }
674        if (overlap->flipped()
675                ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
676                : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
677            overlap->setOppPtTEnd(test->oppPtTEnd());
678        }
679        if (!fHead || !this->release(fHead, test)) {
680            SkAssertResult(this->release(fTop, test));
681        }
682    }
683    const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
684    const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
685    if (overlap && cs && ce && overlap->contains(cs, ce)) {
686        return true;
687    }
688    FAIL_IF(cs == ce && cs);
689    const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
690    const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
691    if (overlap && os && oe && overlap->contains(os, oe)) {
692        return true;
693    }
694    SkASSERT(!cs || !cs->deleted());
695    SkASSERT(!os || !os->deleted());
696    SkASSERT(!ce || !ce->deleted());
697    SkASSERT(!oe || !oe->deleted());
698    const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
699    const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
700    FAIL_IF(csExisting && csExisting == ceExisting);
701//    FAIL_IF(csExisting && (csExisting == ce ||
702//            csExisting->contains(ceExisting ? ceExisting : ce)));
703    FAIL_IF(ceExisting && (ceExisting == cs ||
704            ceExisting->contains(csExisting ? csExisting : cs)));
705    const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
706    const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
707    FAIL_IF(osExisting && osExisting == oeExisting);
708    FAIL_IF(osExisting && (osExisting == oe ||
709            osExisting->contains(oeExisting ? oeExisting : oe)));
710    FAIL_IF(oeExisting && (oeExisting == os ||
711            oeExisting->contains(osExisting ? osExisting : os)));
712    // extra line in debug code
713    this->debugValidate();
714    if (!cs || !os) {
715        SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs)
716            : coinSeg->addT(coinTs);
717        if (csWritable == ce) {
718            return true;
719        }
720        SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os)
721            : oppSeg->addT(oppTs);
722        FAIL_IF(!csWritable || !osWritable);
723        csWritable->span()->addOpp(osWritable->span());
724        cs = csWritable;
725        os = osWritable->active();
726        FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted()));
727    }
728    if (!ce || !oe) {
729        SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce)
730            : coinSeg->addT(coinTe);
731        SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe)
732            : oppSeg->addT(oppTe);
733        ceWritable->span()->addOpp(oeWritable->span());
734        ce = ceWritable;
735        oe = oeWritable;
736    }
737    this->debugValidate();
738    FAIL_IF(cs->deleted());
739    FAIL_IF(os->deleted());
740    FAIL_IF(ce->deleted());
741    FAIL_IF(oe->deleted());
742    FAIL_IF(cs->contains(ce) || os->contains(oe));
743    bool result = true;
744    if (overlap) {
745        if (overlap->coinPtTStart()->segment() == coinSeg) {
746            result = overlap->extend(cs, ce, os, oe);
747        } else {
748            if (os->fT > oe->fT) {
749                SkTSwap(cs, ce);
750                SkTSwap(os, oe);
751            }
752            result = overlap->extend(os, oe, cs, ce);
753        }
754#if DEBUG_COINCIDENCE_VERBOSE
755        if (result) {
756            overlaps[0]->debugShow();
757        }
758#endif
759    } else {
760        this->add(cs, ce, os, oe);
761#if DEBUG_COINCIDENCE_VERBOSE
762        fHead->debugShow();
763#endif
764    }
765    this->debugValidate();
766    if (result) {
767        *added = true;
768    }
769    return true;
770}
771
772// Please keep this in sync with debugAddMissing()
773/* detects overlaps of different coincident runs on same segment */
774/* does not detect overlaps for pairs without any segments in common */
775// returns true if caller should loop again
776bool SkOpCoincidence::addMissing(bool* added  DEBUG_COIN_DECLARE_PARAMS()) {
777    SkCoincidentSpans* outer = fHead;
778    *added = false;
779    if (!outer) {
780        return true;
781    }
782    fTop = outer;
783    fHead = nullptr;
784    do {
785    // addifmissing can modify the list that this is walking
786    // save head so that walker can iterate over old data unperturbed
787    // addifmissing adds to head freely then add saved head in the end
788        const SkOpPtT* ocs = outer->coinPtTStart();
789        FAIL_IF(ocs->deleted());
790        const SkOpSegment* outerCoin = ocs->segment();
791        SkASSERT(!outerCoin->done());  // if it's done, should have already been removed from list
792        const SkOpPtT* oos = outer->oppPtTStart();
793        if (oos->deleted()) {
794            return true;
795        }
796        const SkOpSegment* outerOpp = oos->segment();
797        SkOPASSERT(!outerOpp->done());
798        SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
799        SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
800        SkCoincidentSpans* inner = outer;
801        while ((inner = inner->next())) {
802            this->debugValidate();
803            double overS, overE;
804            const SkOpPtT* ics = inner->coinPtTStart();
805            FAIL_IF(ics->deleted());
806            const SkOpSegment* innerCoin = ics->segment();
807            FAIL_IF(innerCoin->done());
808            const SkOpPtT* ios = inner->oppPtTStart();
809            FAIL_IF(ios->deleted());
810            const SkOpSegment* innerOpp = ios->segment();
811            SkOPASSERT(!innerOpp->done());
812            SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
813            SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
814            if (outerCoin == innerCoin) {
815                const SkOpPtT* oce = outer->coinPtTEnd();
816                if (oce->deleted()) {
817                    return true;
818                }
819                const SkOpPtT* ice = inner->coinPtTEnd();
820                FAIL_IF(ice->deleted());
821                if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
822                    (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice),
823                            overS, overE, outerOppWritable, innerOppWritable, added
824                            SkDEBUGPARAMS(ocs->debugEnder(oce))
825                            SkDEBUGPARAMS(ics->debugEnder(ice)));
826                }
827            } else if (outerCoin == innerOpp) {
828                const SkOpPtT* oce = outer->coinPtTEnd();
829                SkASSERT(!oce->deleted());
830                const SkOpPtT* ioe = inner->oppPtTEnd();
831                SkASSERT(!ioe->deleted());
832                if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
833                    (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe),
834                            overS, overE, outerOppWritable, innerCoinWritable, added
835                            SkDEBUGPARAMS(ocs->debugEnder(oce))
836                            SkDEBUGPARAMS(ios->debugEnder(ioe)));
837                }
838            } else if (outerOpp == innerCoin) {
839                const SkOpPtT* ooe = outer->oppPtTEnd();
840                SkASSERT(!ooe->deleted());
841                const SkOpPtT* ice = inner->coinPtTEnd();
842                SkASSERT(!ice->deleted());
843                SkASSERT(outerCoin != innerOpp);
844                if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
845                    (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice),
846                            overS, overE, outerCoinWritable, innerOppWritable, added
847                            SkDEBUGPARAMS(oos->debugEnder(ooe))
848                            SkDEBUGPARAMS(ics->debugEnder(ice)));
849                }
850            } else if (outerOpp == innerOpp) {
851                const SkOpPtT* ooe = outer->oppPtTEnd();
852                SkASSERT(!ooe->deleted());
853                const SkOpPtT* ioe = inner->oppPtTEnd();
854                if (ioe->deleted()) {
855                    return true;
856                }
857                SkASSERT(outerCoin != innerCoin);
858                if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
859                    (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe),
860                            overS, overE, outerCoinWritable, innerCoinWritable, added
861                            SkDEBUGPARAMS(oos->debugEnder(ooe))
862                            SkDEBUGPARAMS(ios->debugEnder(ioe)));
863                }
864            }
865            this->debugValidate();
866        }
867    } while ((outer = outer->next()));
868    this->restoreHead();
869    return true;
870}
871
872bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
873        const SkOpSegment* seg2, const SkOpSegment* seg2o,
874        const SkOpPtT* overS, const SkOpPtT* overE) {
875    const SkOpPtT* s1 = overS->find(seg1);
876    const SkOpPtT* e1 = overE->find(seg1);
877    FAIL_IF(!s1);
878    FAIL_IF(!e1);
879    if (!s1->starter(e1)->span()->upCast()->windValue()) {
880        s1 = overS->find(seg1o);
881        e1 = overE->find(seg1o);
882        FAIL_IF(!s1);
883        FAIL_IF(!e1);
884        if (!s1->starter(e1)->span()->upCast()->windValue()) {
885            return true;
886        }
887    }
888    const SkOpPtT* s2 = overS->find(seg2);
889    const SkOpPtT* e2 = overE->find(seg2);
890    FAIL_IF(!s2);
891    FAIL_IF(!e2);
892    if (!s2->starter(e2)->span()->upCast()->windValue()) {
893        s2 = overS->find(seg2o);
894        e2 = overE->find(seg2o);
895        FAIL_IF(!s2);
896        FAIL_IF(!e2);
897        if (!s2->starter(e2)->span()->upCast()->windValue()) {
898            return true;
899        }
900    }
901    if (s1->segment() == s2->segment()) {
902        return true;
903    }
904    if (s1->fT > e1->fT) {
905        SkTSwap(s1, e1);
906        SkTSwap(s2, e2);
907    }
908    this->add(s1, e1, s2, e2);
909    return true;
910}
911
912bool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const {
913    if (this->contains(fHead, seg, opp, oppT)) {
914        return true;
915    }
916    if (this->contains(fTop, seg, opp, oppT)) {
917        return true;
918    }
919    return false;
920}
921
922bool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
923        const SkOpSegment* opp, double oppT) const {
924    if (!coin) {
925        return false;
926   }
927    do {
928        if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp
929                && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) {
930            return true;
931        }
932        if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp
933                && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) {
934            return true;
935        }
936    } while ((coin = coin->next()));
937    return false;
938}
939
940bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
941        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const {
942    const SkCoincidentSpans* test = fHead;
943    if (!test) {
944        return false;
945    }
946    const SkOpSegment* coinSeg = coinPtTStart->segment();
947    const SkOpSegment* oppSeg = oppPtTStart->segment();
948    if (!Ordered(coinPtTStart, oppPtTStart)) {
949        SkTSwap(coinSeg, oppSeg);
950        SkTSwap(coinPtTStart, oppPtTStart);
951        SkTSwap(coinPtTEnd, oppPtTEnd);
952        if (coinPtTStart->fT > coinPtTEnd->fT) {
953            SkTSwap(coinPtTStart, coinPtTEnd);
954            SkTSwap(oppPtTStart, oppPtTEnd);
955        }
956    }
957    double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT);
958    double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT);
959    do {
960        if (coinSeg != test->coinPtTStart()->segment()) {
961            continue;
962        }
963        if (coinPtTStart->fT < test->coinPtTStart()->fT) {
964            continue;
965        }
966        if (coinPtTEnd->fT > test->coinPtTEnd()->fT) {
967            continue;
968        }
969        if (oppSeg != test->oppPtTStart()->segment()) {
970            continue;
971        }
972        if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
973            continue;
974        }
975        if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
976            continue;
977        }
978        return true;
979    } while ((test = test->next()));
980    return false;
981}
982
983void SkOpCoincidence::correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
984    DEBUG_SET_PHASE();
985    SkCoincidentSpans* coin = fHead;
986    if (!coin) {
987        return;
988    }
989    do {
990        coin->correctEnds();
991    } while ((coin = coin->next()));
992}
993
994// walk span sets in parallel, moving winding from one to the other
995bool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
996    DEBUG_SET_PHASE();
997    SkCoincidentSpans* coin = fHead;
998    if (!coin) {
999        return true;
1000    }
1001    do {
1002        SkOpSpanBase* startSpan = coin->coinPtTStartWritable()->span();
1003        FAIL_IF(!startSpan->upCastable());
1004        SkOpSpan* start = startSpan->upCast();
1005        if (start->deleted()) {
1006            continue;
1007        }
1008        const SkOpSpanBase* end = coin->coinPtTEnd()->span();
1009        SkASSERT(start == start->starter(end));
1010        bool flipped = coin->flipped();
1011        SkOpSpanBase* oStartBase = (flipped ? coin->oppPtTEndWritable()
1012                : coin->oppPtTStartWritable())->span();
1013        FAIL_IF(!oStartBase->upCastable());
1014        SkOpSpan* oStart = oStartBase->upCast();
1015        if (oStart->deleted()) {
1016            continue;
1017        }
1018        const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span();
1019        SkASSERT(oStart == oStart->starter(oEnd));
1020        SkOpSegment* segment = start->segment();
1021        SkOpSegment* oSegment = oStart->segment();
1022        bool operandSwap = segment->operand() != oSegment->operand();
1023        if (flipped) {
1024            if (oEnd->deleted()) {
1025                continue;
1026            }
1027            do {
1028                SkOpSpanBase* oNext = oStart->next();
1029                if (oNext == oEnd) {
1030                    break;
1031                }
1032                FAIL_IF(!oNext->upCastable());
1033                oStart = oNext->upCast();
1034            } while (true);
1035        }
1036        do {
1037            int windValue = start->windValue();
1038            int oppValue = start->oppValue();
1039            int oWindValue = oStart->windValue();
1040            int oOppValue = oStart->oppValue();
1041            // winding values are added or subtracted depending on direction and wind type
1042            // same or opposite values are summed depending on the operand value
1043            int windDiff = operandSwap ? oOppValue : oWindValue;
1044            int oWindDiff = operandSwap ? oppValue : windValue;
1045            if (!flipped) {
1046                windDiff = -windDiff;
1047                oWindDiff = -oWindDiff;
1048            }
1049            bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff
1050                    && oWindValue <= oWindDiff));
1051            if (addToStart ? start->done() : oStart->done()) {
1052                addToStart ^= true;
1053            }
1054            if (addToStart) {
1055                if (operandSwap) {
1056                    SkTSwap(oWindValue, oOppValue);
1057                }
1058                if (flipped) {
1059                    windValue -= oWindValue;
1060                    oppValue -= oOppValue;
1061                } else {
1062                    windValue += oWindValue;
1063                    oppValue += oOppValue;
1064                }
1065                if (segment->isXor()) {
1066                    windValue &= 1;
1067                }
1068                if (segment->oppXor()) {
1069                    oppValue &= 1;
1070                }
1071                oWindValue = oOppValue = 0;
1072            } else {
1073                if (operandSwap) {
1074                    SkTSwap(windValue, oppValue);
1075                }
1076                if (flipped) {
1077                    oWindValue -= windValue;
1078                    oOppValue -= oppValue;
1079                } else {
1080                    oWindValue += windValue;
1081                    oOppValue += oppValue;
1082                }
1083                if (oSegment->isXor()) {
1084                    oWindValue &= 1;
1085                }
1086                if (oSegment->oppXor()) {
1087                    oOppValue &= 1;
1088                }
1089                windValue = oppValue = 0;
1090            }
1091#if 0 && DEBUG_COINCIDENCE
1092            SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(),
1093                    start->debugID(), windValue, oppValue);
1094            SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(),
1095                    oStart->debugID(), oWindValue, oOppValue);
1096#endif
1097            start->setWindValue(windValue);
1098            start->setOppValue(oppValue);
1099            FAIL_IF(oWindValue == -1);
1100            oStart->setWindValue(oWindValue);
1101            oStart->setOppValue(oOppValue);
1102            if (!windValue && !oppValue) {
1103                segment->markDone(start);
1104            }
1105            if (!oWindValue && !oOppValue) {
1106                oSegment->markDone(oStart);
1107            }
1108            SkOpSpanBase* next = start->next();
1109            SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
1110            if (next == end) {
1111                break;
1112            }
1113            FAIL_IF(!next->upCastable());
1114            start = next->upCast();
1115            // if the opposite ran out too soon, just reuse the last span
1116            if (!oNext || !oNext->upCastable()) {
1117               oNext = oStart;
1118            }
1119            oStart = oNext->upCast();
1120        } while (true);
1121    } while ((coin = coin->next()));
1122    return true;
1123}
1124
1125// Please keep this in sync with debugRelease()
1126bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove)  {
1127    SkCoincidentSpans* head = coin;
1128    SkCoincidentSpans* prev = nullptr;
1129    SkCoincidentSpans* next;
1130    do {
1131        next = coin->next();
1132        if (coin == remove) {
1133            if (prev) {
1134                prev->setNext(next);
1135            } else if (head == fHead) {
1136                fHead = next;
1137            } else {
1138                fTop = next;
1139            }
1140            break;
1141        }
1142        prev = coin;
1143    } while ((coin = next));
1144    return coin != nullptr;
1145}
1146
1147void SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) {
1148    if (!coin) {
1149        return;
1150    }
1151    SkCoincidentSpans* head = coin;
1152    SkCoincidentSpans* prev = nullptr;
1153    SkCoincidentSpans* next;
1154    do {
1155        next = coin->next();
1156        if (coin->coinPtTStart()->deleted()) {
1157            SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() :
1158                    coin->oppPtTStart()->deleted());
1159            if (prev) {
1160                prev->setNext(next);
1161            } else if (head == fHead) {
1162                fHead = next;
1163            } else {
1164                fTop = next;
1165            }
1166        } else {
1167             SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() :
1168                    !coin->oppPtTStart()->deleted());
1169            prev = coin;
1170        }
1171    } while ((coin = next));
1172}
1173
1174void SkOpCoincidence::releaseDeleted() {
1175    this->releaseDeleted(fHead);
1176    this->releaseDeleted(fTop);
1177}
1178
1179void SkOpCoincidence::restoreHead() {
1180    SkCoincidentSpans** headPtr = &fHead;
1181    while (*headPtr) {
1182        headPtr = (*headPtr)->nextPtr();
1183    }
1184    *headPtr = fTop;
1185    fTop = nullptr;
1186    // segments may have collapsed in the meantime; remove empty referenced segments
1187    headPtr = &fHead;
1188    while (*headPtr) {
1189        SkCoincidentSpans* test = *headPtr;
1190        if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) {
1191            *headPtr = test->next();
1192            continue;
1193        }
1194        headPtr = (*headPtr)->nextPtr();
1195    }
1196}
1197
1198// Please keep this in sync with debugExpand()
1199// expand the range by checking adjacent spans for coincidence
1200bool SkOpCoincidence::expand(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1201    DEBUG_SET_PHASE();
1202    SkCoincidentSpans* coin = fHead;
1203    if (!coin) {
1204        return false;
1205    }
1206    bool expanded = false;
1207    do {
1208        if (coin->expand()) {
1209            // check to see if multiple spans expanded so they are now identical
1210            SkCoincidentSpans* test = fHead;
1211            do {
1212                if (coin == test) {
1213                    continue;
1214                }
1215                if (coin->coinPtTStart() == test->coinPtTStart()
1216                        && coin->oppPtTStart() == test->oppPtTStart()) {
1217                    this->release(fHead, test);
1218                    break;
1219                }
1220            } while ((test = test->next()));
1221            expanded = true;
1222        }
1223    } while ((coin = coin->next()));
1224    return expanded;
1225}
1226
1227bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps  DEBUG_COIN_DECLARE_PARAMS()) const {
1228    DEBUG_SET_PHASE();
1229    overlaps->fHead = overlaps->fTop = nullptr;
1230    SkCoincidentSpans* outer = fHead;
1231    while (outer) {
1232        const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
1233        const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
1234        SkCoincidentSpans* inner = outer;
1235        while ((inner = inner->next())) {
1236            const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
1237            if (outerCoin == innerCoin) {
1238                continue;  // both winners are the same segment, so there's no additional overlap
1239            }
1240            const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
1241            const SkOpPtT* overlapS;
1242            const SkOpPtT* overlapE;
1243            if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(),
1244                    outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS,
1245                    &overlapE))
1246                    || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(),
1247                    outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
1248                    &overlapS, &overlapE))
1249                    || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(),
1250                    outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
1251                    &overlapS, &overlapE))) {
1252                if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp,
1253                        overlapS, overlapE)) {
1254                    return false;
1255                }
1256             }
1257        }
1258        outer = outer->next();
1259    }
1260    return true;
1261}
1262
1263void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) {
1264    SkOPASSERT(deleted != kept);
1265    if (fHead) {
1266        this->fixUp(fHead, deleted, kept);
1267    }
1268    if (fTop) {
1269        this->fixUp(fTop, deleted, kept);
1270    }
1271}
1272
1273void SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) {
1274    SkCoincidentSpans* head = coin;
1275    do {
1276        if (coin->coinPtTStart() == deleted) {
1277            if (coin->coinPtTEnd()->span() == kept->span()) {
1278                this->release(head, coin);
1279                continue;
1280            }
1281            coin->setCoinPtTStart(kept);
1282        }
1283        if (coin->coinPtTEnd() == deleted) {
1284            if (coin->coinPtTStart()->span() == kept->span()) {
1285                this->release(head, coin);
1286                continue;
1287            }
1288            coin->setCoinPtTEnd(kept);
1289       }
1290        if (coin->oppPtTStart() == deleted) {
1291            if (coin->oppPtTEnd()->span() == kept->span()) {
1292                this->release(head, coin);
1293                continue;
1294            }
1295            coin->setOppPtTStart(kept);
1296        }
1297        if (coin->oppPtTEnd() == deleted) {
1298            if (coin->oppPtTStart()->span() == kept->span()) {
1299                this->release(head, coin);
1300                continue;
1301            }
1302            coin->setOppPtTEnd(kept);
1303        }
1304    } while ((coin = coin->next()));
1305}
1306
1307// Please keep this in sync with debugMark()
1308/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
1309bool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1310    DEBUG_SET_PHASE();
1311    SkCoincidentSpans* coin = fHead;
1312    if (!coin) {
1313        return true;
1314    }
1315    do {
1316        SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span();
1317        FAIL_IF(!startBase->upCastable());
1318        SkOpSpan* start = startBase->upCast();
1319        FAIL_IF(start->deleted());
1320        SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
1321        SkOPASSERT(!end->deleted());
1322        SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
1323        SkOPASSERT(!oStart->deleted());
1324        SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
1325        SkASSERT(!oEnd->deleted());
1326        bool flipped = coin->flipped();
1327        if (flipped) {
1328            SkTSwap(oStart, oEnd);
1329        }
1330        /* coin and opp spans may not match up. Mark the ends, and then let the interior
1331           get marked as many times as the spans allow */
1332        FAIL_IF(!oStart->upCastable());
1333        start->insertCoincidence(oStart->upCast());
1334        end->insertCoinEnd(oEnd);
1335        const SkOpSegment* segment = start->segment();
1336        const SkOpSegment* oSegment = oStart->segment();
1337        SkOpSpanBase* next = start;
1338        SkOpSpanBase* oNext = oStart;
1339        bool ordered;
1340        FAIL_IF(!coin->ordered(&ordered));
1341        while ((next = next->upCast()->next()) != end) {
1342            FAIL_IF(!next->upCastable());
1343            FAIL_IF(!next->upCast()->insertCoincidence(oSegment, flipped, ordered));
1344        }
1345        while ((oNext = oNext->upCast()->next()) != oEnd) {
1346            FAIL_IF(!oNext->upCastable());
1347            FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordered));
1348        }
1349    } while ((coin = coin->next()));
1350    return true;
1351}
1352
1353// Please keep in sync with debugMarkCollapsed()
1354void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) {
1355    SkCoincidentSpans* head = coin;
1356    while (coin) {
1357        if (coin->collapsed(test)) {
1358            if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
1359                coin->coinPtTStartWritable()->segment()->markAllDone();
1360            }
1361            if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
1362                coin->oppPtTStartWritable()->segment()->markAllDone();
1363            }
1364            this->release(head, coin);
1365        }
1366        coin = coin->next();
1367    }
1368}
1369
1370// Please keep in sync with debugMarkCollapsed()
1371void SkOpCoincidence::markCollapsed(SkOpPtT* test) {
1372    markCollapsed(fHead, test);
1373    markCollapsed(fTop, test);
1374}
1375
1376bool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) {
1377    if (coinSeg->verb() < oppSeg->verb()) {
1378        return true;
1379    }
1380    if (coinSeg->verb() > oppSeg->verb()) {
1381        return false;
1382    }
1383    int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2;
1384    const SkScalar* cPt = &coinSeg->pts()[0].fX;
1385    const SkScalar* oPt = &oppSeg->pts()[0].fX;
1386    for (int index = 0; index < count; ++index) {
1387        if (*cPt < *oPt) {
1388            return true;
1389        }
1390        if (*cPt > *oPt) {
1391            return false;
1392        }
1393        ++cPt;
1394        ++oPt;
1395    }
1396    return true;
1397}
1398
1399bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e,
1400        const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
1401    SkASSERT(coin1s->segment() == coin2s->segment());
1402    *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT));
1403    *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT));
1404    return *overS < *overE;
1405}
1406
1407// Commented-out lines keep this in sync with debugRelease()
1408void SkOpCoincidence::release(const SkOpSegment* deleted) {
1409    SkCoincidentSpans* coin = fHead;
1410    if (!coin) {
1411        return;
1412    }
1413    do {
1414        if (coin->coinPtTStart()->segment() == deleted
1415                || coin->coinPtTEnd()->segment() == deleted
1416                || coin->oppPtTStart()->segment() == deleted
1417                || coin->oppPtTEnd()->segment() == deleted) {
1418            this->release(fHead, coin);
1419        }
1420    } while ((coin = coin->next()));
1421}
1422