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