SkPathOpsDebug.cpp revision 03b03cad01628146bbb8d4f33c073bd0c77ee558 
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#include "SkString.h"
11#include "SkThread.h"
12
13#if DEBUG_VALIDATE
14extern bool FLAGS_runFail;
15#endif
16
17#if defined SK_DEBUG || !FORCE_RELEASE
18
19const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
20
21#if defined(SK_DEBUG) || !FORCE_RELEASE
22int SkPathOpsDebug::gContourID = 0;
23int SkPathOpsDebug::gSegmentID = 0;
24#endif
25
26#if DEBUG_SORT || DEBUG_SWAP_TOP
27int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
28int SkPathOpsDebug::gSortCount;
29#endif
30
31#if DEBUG_ACTIVE_OP
32const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"};
33#endif
34
35bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray,
36        const SkOpSpanBase* span) {
37    for (int index = 0; index < chaseArray.count(); ++index) {
38        const SkOpSpanBase* entry = chaseArray[index];
39        if (entry == span) {
40            return true;
41        }
42    }
43    return false;
44}
45
46void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
47    size_t len = strlen(str);
48    bool num = false;
49    for (size_t idx = 0; idx < len; ++idx) {
50        if (num && str[idx] == 'e') {
51            if (len + 2 >= bufferLen) {
52                return;
53            }
54            memmove(&str[idx + 2], &str[idx + 1], len - idx);
55            str[idx] = '*';
56            str[idx + 1] = '^';
57            ++len;
58        }
59        num = str[idx] >= '0' && str[idx] <= '9';
60    }
61}
62
63bool SkPathOpsDebug::ValidWind(int wind) {
64    return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
65}
66
67void SkPathOpsDebug::WindingPrintf(int wind) {
68    if (wind == SK_MinS32) {
69        SkDebugf("?");
70    } else {
71        SkDebugf("%d", wind);
72    }
73}
74#endif //  defined SK_DEBUG || !FORCE_RELEASE
75
76
77#if DEBUG_SHOW_TEST_NAME
78void* SkPathOpsDebug::CreateNameStr() {
79    return SkNEW_ARRAY(char, DEBUG_FILENAME_STRING_LENGTH);
80}
81
82void SkPathOpsDebug::DeleteNameStr(void* v) {
83    SkDELETE_ARRAY(reinterpret_cast<char* >(v));
84}
85
86void SkPathOpsDebug::BumpTestName(char* test) {
87    char* num = test + strlen(test);
88    while (num[-1] >= '0' && num[-1] <= '9') {
89        --num;
90    }
91    if (num[0] == '\0') {
92        return;
93    }
94    int dec = atoi(num);
95    if (dec == 0) {
96        return;
97    }
98    ++dec;
99    SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
100}
101#endif
102
103static void show_function_header(const char* functionName) {
104    SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName);
105    if (strcmp("skphealth_com76", functionName) == 0) {
106        SkDebugf("found it\n");
107    }
108}
109
110static const char* gOpStrs[] = {
111    "kDifference_SkPathOp",
112    "kIntersect_SkPathOp",
113    "kUnion_SkPathOp",
114    "kXor_PathOp",
115    "kReverseDifference_SkPathOp",
116};
117
118const char* SkPathOpsDebug::OpStr(SkPathOp op) {
119    return gOpStrs[op];
120}
121
122static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) {
123    SkDebugf("    testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]);
124    SkDebugf("}\n");
125}
126
127SK_DECLARE_STATIC_MUTEX(gTestMutex);
128
129void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
130        const char* testName) {
131    SkAutoMutexAcquire ac(gTestMutex);
132    show_function_header(testName);
133    ShowOnePath(a, "path", true);
134    ShowOnePath(b, "pathB", true);
135    show_op(shapeOp, "path", "pathB");
136}
137
138#include "SkOpAngle.h"
139#include "SkOpSegment.h"
140
141#if DEBUG_SWAP_TOP
142int SkOpSegment::debugInflections(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
143    if (fVerb != SkPath::kCubic_Verb) {
144        return false;
145    }
146    SkDCubic dst = SkDCubic::SubDivide(fPts, start->t(), end->t());
147    double inflections[2];
148    return dst.findInflections(inflections);
149}
150#endif
151
152SkOpAngle* SkOpSegment::debugLastAngle() {
153    SkOpAngle* result = NULL;
154    SkOpSpan* span = this->head();
155    do {
156        if (span->toAngle()) {
157            SkASSERT(!result);
158            result = span->toAngle();
159        }
160    } while ((span = span->next()->upCastable()));
161    SkASSERT(result);
162    return result;
163}
164
165void SkOpSegment::debugReset() {
166    this->init(this->fPts, this->fWeight, this->contour(), this->verb());
167}
168
169#if DEBUG_ACTIVE_SPANS
170void SkOpSegment::debugShowActiveSpans() const {
171    debugValidate();
172    if (done()) {
173        return;
174    }
175    int lastId = -1;
176    double lastT = -1;
177    const SkOpSpan* span = &fHead;
178    do {
179        if (span->done()) {
180            continue;
181        }
182        if (lastId == this->debugID() && lastT == span->t()) {
183            continue;
184        }
185        lastId = this->debugID();
186        lastT = span->t();
187        SkDebugf("%s id=%d", __FUNCTION__, this->debugID());
188        SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
189        for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
190            SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
191        }
192        if (SkPath::kConic_Verb == fVerb) {
193            SkDebugf(" %1.9gf", fWeight);
194        }
195        const SkOpPtT* ptT = span->ptT();
196        SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY);
197        SkDebugf(" tEnd=%1.9g", span->next()->t());
198        SkDebugf(" windSum=");
199        if (span->windSum() == SK_MinS32) {
200            SkDebugf("?");
201        } else {
202            SkDebugf("%d", span->windSum());
203        }
204        SkDebugf(" windValue=%d oppValue=%d", span->windValue(), span->oppValue());
205        SkDebugf("\n");
206   } while ((span = span->next()->upCastable()));
207}
208#endif
209
210#if DEBUG_MARK_DONE
211void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
212    const SkPoint& pt = span->ptT()->fPt;
213    SkDebugf("%s id=%d", fun, this->debugID());
214    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
215    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
216        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
217    }
218    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
219            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
220    if (winding == SK_MinS32) {
221        SkDebugf("?");
222    } else {
223        SkDebugf("%d", winding);
224    }
225    SkDebugf(" windSum=");
226    if (span->windSum() == SK_MinS32) {
227        SkDebugf("?");
228    } else {
229        SkDebugf("%d", span->windSum());
230    }
231    SkDebugf(" windValue=%d\n", span->windValue());
232}
233
234void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
235                                      int oppWinding) {
236    const SkPoint& pt = span->ptT()->fPt;
237    SkDebugf("%s id=%d", fun, this->debugID());
238    SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
239    for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
240        SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
241    }
242    SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
243            span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding);
244    if (winding == SK_MinS32) {
245        SkDebugf("?");
246    } else {
247        SkDebugf("%d", winding);
248    }
249    SkDebugf(" newOppSum=");
250    if (oppWinding == SK_MinS32) {
251        SkDebugf("?");
252    } else {
253        SkDebugf("%d", oppWinding);
254    }
255    SkDebugf(" oppSum=");
256    if (span->oppSum() == SK_MinS32) {
257        SkDebugf("?");
258    } else {
259        SkDebugf("%d", span->oppSum());
260    }
261    SkDebugf(" windSum=");
262    if (span->windSum() == SK_MinS32) {
263        SkDebugf("?");
264    } else {
265        SkDebugf("%d", span->windSum());
266    }
267    SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
268}
269
270#endif
271
272#if DEBUG_ANGLE
273SkString SkOpAngle::debugPart() const {
274    SkString result;
275    switch (this->segment()->verb()) {
276        case SkPath::kLine_Verb:
277            result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart),
278                    this->segment()->debugID());
279            break;
280        case SkPath::kQuad_Verb:
281            result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
282                    this->segment()->debugID());
283            break;
284        case SkPath::kConic_Verb:
285            result.printf(CONIC_DEBUG_STR " id=%d",
286                    CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight),
287                    this->segment()->debugID());
288            break;
289        case SkPath::kCubic_Verb:
290            result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart),
291                    this->segment()->debugID());
292            break;
293        default:
294            SkASSERT(0);
295    }
296    return result;
297}
298#endif
299
300#if DEBUG_SORT || DEBUG_SWAP_TOP
301void SkOpAngle::debugLoop() const {
302    const SkOpAngle* first = this;
303    const SkOpAngle* next = this;
304    do {
305        next->dumpOne(true);
306        SkDebugf("\n");
307        next = next->fNext;
308    } while (next && next != first);
309    next = first;
310    do {
311        next->debugValidate();
312        next = next->fNext;
313    } while (next && next != first);
314}
315#endif
316
317void SkOpAngle::debugValidate() const {
318#if DEBUG_VALIDATE
319    const SkOpAngle* first = this;
320    const SkOpAngle* next = this;
321    int wind = 0;
322    int opp = 0;
323    int lastXor = -1;
324    int lastOppXor = -1;
325    do {
326        if (next->unorderable()) {
327            return;
328        }
329        const SkOpSpan* minSpan = next->start()->starter(next->end());
330        if (minSpan->windValue() == SK_MinS32) {
331            return;
332        }
333        bool op = next->segment()->operand();
334        bool isXor = next->segment()->isXor();
335        bool oppXor = next->segment()->oppXor();
336        SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
337        SkASSERT(!DEBUG_LIMIT_WIND_SUM
338                || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
339        bool useXor = op ? oppXor : isXor;
340        SkASSERT(lastXor == -1 || lastXor == (int) useXor);
341        lastXor = (int) useXor;
342        wind += next->sign() * (op ? minSpan->oppValue() : minSpan->windValue());
343        if (useXor) {
344            wind &= 1;
345        }
346        useXor = op ? isXor : oppXor;
347        SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
348        lastOppXor = (int) useXor;
349        opp += next->sign() * (op ? minSpan->windValue() : minSpan->oppValue());
350        if (useXor) {
351            opp &= 1;
352        }
353        next = next->fNext;
354    } while (next && next != first);
355    SkASSERT(wind == 0);
356    SkASSERT(opp == 0 || !FLAGS_runFail);
357#endif
358}
359
360void SkOpAngle::debugValidateNext() const {
361#if !FORCE_RELEASE
362    const SkOpAngle* first = this;
363    const SkOpAngle* next = first;
364    SkTDArray<const SkOpAngle*>(angles);
365    do {
366//        SK_ALWAYSBREAK(next->fSegment->debugContains(next));
367        angles.push(next);
368        next = next->next();
369        if (next == first) {
370            break;
371        }
372        SK_ALWAYSBREAK(!angles.contains(next));
373        if (!next) {
374            return;
375        }
376    } while (true);
377#endif
378}
379
380void SkOpSegment::debugValidate() const {
381#if DEBUG_VALIDATE
382    const SkOpSpanBase* span = &fHead;
383    double lastT = -1;
384    const SkOpSpanBase* prev = NULL;
385    int count = 0;
386    int done = 0;
387    do {
388        if (!span->final()) {
389            ++count;
390            done += span->upCast()->done() ? 1 : 0;
391        }
392        SkASSERT(span->segment() == this);
393        SkASSERT(!prev || prev->upCast()->next() == span);
394        SkASSERT(!prev || prev == span->prev());
395        prev = span;
396        double t = span->ptT()->fT;
397        SkASSERT(lastT < t);
398        lastT = t;
399        span->debugValidate();
400    } while (!span->final() && (span = span->upCast()->next()));
401    SkASSERT(count == fCount);
402    SkASSERT(done == fDoneCount);
403    SkASSERT(span->final());
404    span->debugValidate();
405#endif
406}
407
408bool SkOpSpanBase::debugCoinEndLoopCheck() const {
409    int loop = 0;
410    const SkOpSpanBase* next = this;
411    SkOpSpanBase* nextCoin;
412    do {
413        nextCoin = next->fCoinEnd;
414        SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
415        for (int check = 1; check < loop - 1; ++check) {
416            const SkOpSpanBase* checkCoin = this->fCoinEnd;
417            const SkOpSpanBase* innerCoin = checkCoin;
418            for (int inner = check + 1; inner < loop; ++inner) {
419                innerCoin = innerCoin->fCoinEnd;
420                if (checkCoin == innerCoin) {
421                    SkDebugf("*** bad coincident end loop ***\n");
422                    return false;
423                }
424            }
425        }
426        ++loop;
427    } while ((next = nextCoin) && next != this);
428    return true;
429}
430
431void SkOpSpanBase::debugValidate() const {
432#if DEBUG_VALIDATE
433    const SkOpPtT* ptT = &fPtT;
434    SkASSERT(ptT->span() == this);
435    do {
436//        SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
437        ptT->debugValidate();
438        ptT = ptT->next();
439    } while (ptT != &fPtT);
440    SkASSERT(this->debugCoinEndLoopCheck());
441    if (!this->final()) {
442        SkASSERT(this->upCast()->debugCoinLoopCheck());
443    }
444    if (fFromAngle) {
445        fFromAngle->debugValidate();
446    }
447    if (!this->final() && this->upCast()->toAngle()) {
448        this->upCast()->toAngle()->debugValidate();
449    }
450#endif
451}
452
453bool SkOpSpan::debugCoinLoopCheck() const {
454    int loop = 0;
455    const SkOpSpan* next = this;
456    SkOpSpan* nextCoin;
457    do {
458        nextCoin = next->fCoincident;
459        SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
460        for (int check = 1; check < loop - 1; ++check) {
461            const SkOpSpan* checkCoin = this->fCoincident;
462            const SkOpSpan* innerCoin = checkCoin;
463            for (int inner = check + 1; inner < loop; ++inner) {
464                innerCoin = innerCoin->fCoincident;
465                if (checkCoin == innerCoin) {
466                    SkDebugf("*** bad coincident loop ***\n");
467                    return false;
468                }
469            }
470        }
471        ++loop;
472    } while ((next = nextCoin) && next != this);
473    return true;
474}
475
476#include "SkOpContour.h"
477
478int SkOpPtT::debugLoopLimit(bool report) const {
479    int loop = 0;
480    const SkOpPtT* next = this;
481    do {
482        for (int check = 1; check < loop - 1; ++check) {
483            const SkOpPtT* checkPtT = this->fNext;
484            const SkOpPtT* innerPtT = checkPtT;
485            for (int inner = check + 1; inner < loop; ++inner) {
486                innerPtT = innerPtT->fNext;
487                if (checkPtT == innerPtT) {
488                    if (report) {
489                        SkDebugf("*** bad ptT loop ***\n");
490                    }
491                    return loop;
492                }
493            }
494        }
495        ++loop;
496    } while ((next = next->fNext) && next != this);
497    return 0;
498}
499
500void SkOpPtT::debugValidate() const {
501#if DEBUG_VALIDATE
502    if (contour()->globalState()->phase() == SkOpGlobalState::kIntersecting) {
503        return;
504    }
505    SkASSERT(fNext);
506    SkASSERT(fNext != this);
507    SkASSERT(fNext->fNext);
508    SkASSERT(debugLoopLimit(false) == 0);
509#endif
510}
511
512static void output_scalar(SkScalar num) {
513    if (num == (int) num) {
514        SkDebugf("%d", (int) num);
515    } else {
516        SkString str;
517        str.printf("%1.9g", num);
518        int width = (int) str.size();
519        const char* cStr = str.c_str();
520        while (cStr[width - 1] == '0') {
521            --width;
522        }
523        str.resize(width);
524        SkDebugf("%sf", str.c_str());
525    }
526}
527
528static void output_points(const SkPoint* pts, int count) {
529    for (int index = 0; index < count; ++index) {
530        output_scalar(pts[index].fX);
531        SkDebugf(", ");
532        output_scalar(pts[index].fY);
533        if (index + 1 < count) {
534            SkDebugf(", ");
535        }
536    }
537}
538
539static void showPathContours(SkPath::RawIter& iter, const char* pathName) {
540    uint8_t verb;
541    SkPoint pts[4];
542    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
543        switch (verb) {
544            case SkPath::kMove_Verb:
545                SkDebugf("    %s.moveTo(", pathName);
546                output_points(&pts[0], 1);
547                SkDebugf(");\n");
548                continue;
549            case SkPath::kLine_Verb:
550                SkDebugf("    %s.lineTo(", pathName);
551                output_points(&pts[1], 1);
552                SkDebugf(");\n");
553                break;
554            case SkPath::kQuad_Verb:
555                SkDebugf("    %s.quadTo(", pathName);
556                output_points(&pts[1], 2);
557                SkDebugf(");\n");
558                break;
559            case SkPath::kConic_Verb:
560                SkDebugf("    %s.conicTo(", pathName);
561                output_points(&pts[1], 2);
562                SkDebugf(", %1.9gf);\n", iter.conicWeight());
563                break;
564            case SkPath::kCubic_Verb:
565                SkDebugf("    %s.cubicTo(", pathName);
566                output_points(&pts[1], 3);
567                SkDebugf(");\n");
568                break;
569            case SkPath::kClose_Verb:
570                SkDebugf("    %s.close();\n", pathName);
571                break;
572            default:
573                SkDEBUGFAIL("bad verb");
574                return;
575        }
576    }
577}
578
579static const char* gFillTypeStr[] = {
580    "kWinding_FillType",
581    "kEvenOdd_FillType",
582    "kInverseWinding_FillType",
583    "kInverseEvenOdd_FillType"
584};
585
586void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
587    SkPath::RawIter iter(path);
588#define SUPPORT_RECT_CONTOUR_DETECTION 0
589#if SUPPORT_RECT_CONTOUR_DETECTION
590    int rectCount = path.isRectContours() ? path.rectContours(NULL, NULL) : 0;
591    if (rectCount > 0) {
592        SkTDArray<SkRect> rects;
593        SkTDArray<SkPath::Direction> directions;
594        rects.setCount(rectCount);
595        directions.setCount(rectCount);
596        path.rectContours(rects.begin(), directions.begin());
597        for (int contour = 0; contour < rectCount; ++contour) {
598            const SkRect& rect = rects[contour];
599            SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
600                    rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
601                    ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
602        }
603        return;
604    }
605#endif
606    SkPath::FillType fillType = path.getFillType();
607    SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
608    if (includeDeclaration) {
609        SkDebugf("    SkPath %s;\n", name);
610    }
611    SkDebugf("    %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
612    iter.setPath(path);
613    showPathContours(iter, name);
614}
615