SkPathOpsDebug.cpp revision ccec0f958ffc71a9986d236bc2eb335cb2111119 
1/*
2 * Copyright 2013 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
8#include "SkPathOpsDebug.h"
9#include "SkPath.h"
10#if DEBUG_ANGLE
11#include "SkString.h"
12#endif
13
14#if DEBUG_VALIDATE
15extern bool FLAGS_runFail;
16#endif
17
18#if defined SK_DEBUG || !FORCE_RELEASE
19
20const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
21
22#if defined(SK_DEBUG) || !FORCE_RELEASE
23int SkPathOpsDebug::gContourID = 0;
24int SkPathOpsDebug::gSegmentID = 0;
25#endif
26
27#if DEBUG_SORT || DEBUG_SWAP_TOP
28int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
29int SkPathOpsDebug::gSortCount;
30#endif
31
32#if DEBUG_ACTIVE_OP
33const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"};
34#endif
35
36bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray,
37        const SkOpSpanBase* span) {
38    for (int index = 0; index < chaseArray.count(); ++index) {
39        const SkOpSpanBase* entry = chaseArray[index];
40        if (entry == span) {
41            return true;
42        }
43    }
44    return false;
45}
46
47void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
48    size_t len = strlen(str);
49    bool num = false;
50    for (size_t idx = 0; idx < len; ++idx) {
51        if (num && str[idx] == 'e') {
52            if (len + 2 >= bufferLen) {
53                return;
54            }
55            memmove(&str[idx + 2], &str[idx + 1], len - idx);
56            str[idx] = '*';
57            str[idx + 1] = '^';
58            ++len;
59        }
60        num = str[idx] >= '0' && str[idx] <= '9';
61    }
62}
63
64bool SkPathOpsDebug::ValidWind(int wind) {
65    return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
66}
67
68void SkPathOpsDebug::WindingPrintf(int wind) {
69    if (wind == SK_MinS32) {
70        SkDebugf("?");
71    } else {
72        SkDebugf("%d", wind);
73    }
74}
75#endif //  defined SK_DEBUG || !FORCE_RELEASE
76
77
78#if DEBUG_SHOW_TEST_NAME
79void* SkPathOpsDebug::CreateNameStr() {
80    return SkNEW_ARRAY(char, DEBUG_FILENAME_STRING_LENGTH);
81}
82
83void SkPathOpsDebug::DeleteNameStr(void* v) {
84    SkDELETE_ARRAY(reinterpret_cast<char* >(v));
85}
86
87void SkPathOpsDebug::BumpTestName(char* test) {
88    char* num = test + strlen(test);
89    while (num[-1] >= '0' && num[-1] <= '9') {
90        --num;
91    }
92    if (num[0] == '\0') {
93        return;
94    }
95    int dec = atoi(num);
96    if (dec == 0) {
97        return;
98    }
99    ++dec;
100    SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
101}
102#endif
103
104#if !DEBUG_SHOW_TEST_NAME  // enable when building without extended test
105void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name) {
106}
107#endif
108
109#include "SkOpAngle.h"
110#include "SkOpSegment.h"
111
112#if DEBUG_SWAP_TOP
113int SkOpSegment::debugInflections(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
114    if (fVerb != SkPath::kCubic_Verb) {
115        return false;
116    }
117    SkDCubic dst = SkDCubic::SubDivide(fPts, start->t(), end->t());
118    double inflections[2];
119    return dst.findInflections(inflections);
120}
121#endif
122
123SkOpAngle* SkOpSegment::debugLastAngle() {
124    SkOpAngle* result = NULL;
125    SkOpSpan* span = this->head();
126    do {
127        if (span->toAngle()) {
128            SkASSERT(!result);
129            result = span->toAngle();
130        }
131    } while ((span = span->next()->upCastable()));
132    SkASSERT(result);
133    return result;
134}
135
136void SkOpSegment::debugReset() {
137    this->init(this->fPts, this->contour(), this->verb());
138}
139
140#if DEBUG_ACTIVE_SPANS
141void SkOpSegment::debugShowActiveSpans() const {
142    debugValidate();
143    if (done()) {
144        return;
145    }
146    int lastId = -1;
147    double lastT = -1;
148    const SkOpSpan* span = &fHead;
149    do {
150        if (span->done()) {
151            continue;
152        }
153        if (lastId == fID && lastT == span->t()) {
154            continue;
155        }
156        lastId = fID;
157        lastT = span->t();
158        SkDebugf("%s id=%d", __FUNCTION__, fID);
159        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
160        for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
161            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
162        }
163        const SkOpPtT* ptT = span->ptT();
164        SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY);
165        SkDebugf(" tEnd=%1.9g", span->next()->t());
166        SkDebugf(" windSum=");
167        if (span->windSum() == SK_MinS32) {
168            SkDebugf("?");
169        } else {
170            SkDebugf("%d", span->windSum());
171        }
172        SkDebugf(" windValue=%d oppValue=%d", span->windValue(), span->oppValue());
173        SkDebugf("\n");
174   } while ((span = span->next()->upCastable()));
175}
176#endif
177
178#if DEBUG_MARK_DONE
179void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
180    const SkPoint& pt = span->ptT()->fPt;
181    SkDebugf("%s id=%d", fun, fID);
182    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
183    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
184        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
185    }
186    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
187            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
188    if (winding == SK_MinS32) {
189        SkDebugf("?");
190    } else {
191        SkDebugf("%d", winding);
192    }
193    SkDebugf(" windSum=");
194    if (span->windSum() == SK_MinS32) {
195        SkDebugf("?");
196    } else {
197        SkDebugf("%d", span->windSum());
198    }
199    SkDebugf(" windValue=%d\n", span->windValue());
200}
201
202void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
203                                      int oppWinding) {
204    const SkPoint& pt = span->ptT()->fPt;
205    SkDebugf("%s id=%d", fun, fID);
206    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
207    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
208        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
209    }
210    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
211            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding);
212    if (winding == SK_MinS32) {
213        SkDebugf("?");
214    } else {
215        SkDebugf("%d", winding);
216    }
217    SkDebugf(" newOppSum=");
218    if (oppWinding == SK_MinS32) {
219        SkDebugf("?");
220    } else {
221        SkDebugf("%d", oppWinding);
222    }
223    SkDebugf(" oppSum=");
224    if (span->oppSum() == SK_MinS32) {
225        SkDebugf("?");
226    } else {
227        SkDebugf("%d", span->oppSum());
228    }
229    SkDebugf(" windSum=");
230    if (span->windSum() == SK_MinS32) {
231        SkDebugf("?");
232    } else {
233        SkDebugf("%d", span->windSum());
234    }
235    SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
236}
237
238#endif
239
240#if DEBUG_ANGLE
241SkString SkOpAngle::debugPart() const {
242    SkString result;
243    switch (this->segment()->verb()) {
244        case SkPath::kLine_Verb:
245            result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart),
246                    this->segment()->debugID());
247            break;
248        case SkPath::kQuad_Verb:
249            result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
250                    this->segment()->debugID());
251            break;
252        case SkPath::kCubic_Verb:
253            result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart),
254                    this->segment()->debugID());
255            break;
256        default:
257            SkASSERT(0);
258    }
259    return result;
260}
261#endif
262
263#if DEBUG_SORT
264void SkOpAngle::debugLoop() const {
265    const SkOpAngle* first = this;
266    const SkOpAngle* next = this;
267    do {
268        next->dumpOne(true);
269        SkDebugf("\n");
270        next = next->fNext;
271    } while (next && next != first);
272    next = first;
273    do {
274        next->debugValidate();
275        next = next->fNext;
276    } while (next && next != first);
277}
278#endif
279
280void SkOpAngle::debugValidate() const {
281#if DEBUG_VALIDATE
282    const SkOpAngle* first = this;
283    const SkOpAngle* next = this;
284    int wind = 0;
285    int opp = 0;
286    int lastXor = -1;
287    int lastOppXor = -1;
288    do {
289        if (next->unorderable()) {
290            return;
291        }
292        const SkOpSpan* minSpan = next->start()->starter(next->end());
293        if (minSpan->windValue() == SK_MinS32) {
294            return;
295        }
296        bool op = next->segment()->operand();
297        bool isXor = next->segment()->isXor();
298        bool oppXor = next->segment()->oppXor();
299        SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
300        SkASSERT(!DEBUG_LIMIT_WIND_SUM
301                || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
302        bool useXor = op ? oppXor : isXor;
303        SkASSERT(lastXor == -1 || lastXor == (int) useXor);
304        lastXor = (int) useXor;
305        wind += next->sign() * (op ? minSpan->oppValue() : minSpan->windValue());
306        if (useXor) {
307            wind &= 1;
308        }
309        useXor = op ? isXor : oppXor;
310        SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
311        lastOppXor = (int) useXor;
312        opp += next->sign() * (op ? minSpan->windValue() : minSpan->oppValue());
313        if (useXor) {
314            opp &= 1;
315        }
316        next = next->fNext;
317    } while (next && next != first);
318    SkASSERT(wind == 0);
319    SkASSERT(opp == 0 || !FLAGS_runFail);
320#endif
321}
322
323void SkOpAngle::debugValidateNext() const {
324#if !FORCE_RELEASE
325    const SkOpAngle* first = this;
326    const SkOpAngle* next = first;
327    SkTDArray<const SkOpAngle*>(angles);
328    do {
329//        SK_ALWAYSBREAK(next->fSegment->debugContains(next));
330        angles.push(next);
331        next = next->next();
332        if (next == first) {
333            break;
334        }
335        SK_ALWAYSBREAK(!angles.contains(next));
336        if (!next) {
337            return;
338        }
339    } while (true);
340#endif
341}
342
343void SkOpSegment::debugValidate() const {
344#if DEBUG_VALIDATE
345    const SkOpSpanBase* span = &fHead;
346    double lastT = -1;
347    const SkOpSpanBase* prev = NULL;
348    int count = 0;
349    int done = 0;
350    do {
351        if (!span->final()) {
352            ++count;
353            done += span->upCast()->done() ? 1 : 0;
354        }
355        SkASSERT(span->segment() == this);
356        SkASSERT(!prev || prev->upCast()->next() == span);
357        SkASSERT(!prev || prev == span->prev());
358        prev = span;
359        double t = span->ptT()->fT;
360        SkASSERT(lastT < t);
361        lastT = t;
362        span->debugValidate();
363    } while (!span->final() && (span = span->upCast()->next()));
364    SkASSERT(count == fCount);
365    SkASSERT(done == fDoneCount);
366    SkASSERT(span->final());
367    span->debugValidate();
368#endif
369}
370
371bool SkOpSpanBase::debugCoinEndLoopCheck() const {
372    int loop = 0;
373    const SkOpSpanBase* next = this;
374    SkOpSpanBase* nextCoin;
375    do {
376        nextCoin = next->fCoinEnd;
377        SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
378        for (int check = 1; check < loop - 1; ++check) {
379            const SkOpSpanBase* checkCoin = this->fCoinEnd;
380            const SkOpSpanBase* innerCoin = checkCoin;
381            for (int inner = check + 1; inner < loop; ++inner) {
382                innerCoin = innerCoin->fCoinEnd;
383                if (checkCoin == innerCoin) {
384                    SkDebugf("*** bad coincident end loop ***\n");
385                    return false;
386                }
387            }
388        }
389        ++loop;
390    } while ((next = nextCoin) && next != this);
391    return true;
392}
393
394void SkOpSpanBase::debugValidate() const {
395#if DEBUG_VALIDATE
396    const SkOpPtT* ptT = &fPtT;
397    SkASSERT(ptT->span() == this);
398    do {
399//        SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
400        ptT->debugValidate();
401        ptT = ptT->next();
402    } while (ptT != &fPtT);
403    SkASSERT(this->debugCoinEndLoopCheck());
404    if (!this->final()) {
405        SkASSERT(this->upCast()->debugCoinLoopCheck());
406    }
407    if (fFromAngle) {
408        fFromAngle->debugValidate();
409    }
410    if (!this->final() && this->upCast()->toAngle()) {
411        this->upCast()->toAngle()->debugValidate();
412    }
413#endif
414}
415
416bool SkOpSpan::debugCoinLoopCheck() const {
417    int loop = 0;
418    const SkOpSpan* next = this;
419    SkOpSpan* nextCoin;
420    do {
421        nextCoin = next->fCoincident;
422        SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
423        for (int check = 1; check < loop - 1; ++check) {
424            const SkOpSpan* checkCoin = this->fCoincident;
425            const SkOpSpan* innerCoin = checkCoin;
426            for (int inner = check + 1; inner < loop; ++inner) {
427                innerCoin = innerCoin->fCoincident;
428                if (checkCoin == innerCoin) {
429                    SkDebugf("*** bad coincident loop ***\n");
430                    return false;
431                }
432            }
433        }
434        ++loop;
435    } while ((next = nextCoin) && next != this);
436    return true;
437}
438
439#include "SkOpContour.h"
440
441int SkOpPtT::debugLoopLimit(bool report) const {
442    int loop = 0;
443    const SkOpPtT* next = this;
444    do {
445        for (int check = 1; check < loop - 1; ++check) {
446            const SkOpPtT* checkPtT = this->fNext;
447            const SkOpPtT* innerPtT = checkPtT;
448            for (int inner = check + 1; inner < loop; ++inner) {
449                innerPtT = innerPtT->fNext;
450                if (checkPtT == innerPtT) {
451                    if (report) {
452                        SkDebugf("*** bad ptT loop ***\n");
453                    }
454                    return loop;
455                }
456            }
457        }
458        ++loop;
459    } while ((next = next->fNext) && next != this);
460    return 0;
461}
462
463void SkOpPtT::debugValidate() const {
464#if DEBUG_VALIDATE
465    if (contour()->globalState()->phase() == SkOpGlobalState::kIntersecting) {
466        return;
467    }
468    SkASSERT(fNext);
469    SkASSERT(fNext != this);
470    SkASSERT(fNext->fNext);
471    SkASSERT(debugLoopLimit(false) == 0);
472#endif
473}
474