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#ifndef SkPathOpsDebug_DEFINED
8#define SkPathOpsDebug_DEFINED
9
10#include "include/core/SkString.h"
11#include "include/core/SkTypes.h"
12#include "include/pathops/SkPathOps.h"
13
14#include <stdlib.h>
15#include <stdio.h>
16
17enum class SkOpPhase : char;
18struct SkDQuad;
19class SkOpAngle;
20class SkOpCoincidence;
21class SkOpContour;
22class SkOpContourHead;
23class SkOpPtT;
24class SkOpSegment;
25class SkOpSpan;
26class SkOpSpanBase;
27struct SkDPoint;
28struct SkDLine;
29struct SkDQuad;
30struct SkDConic;
31struct SkDCubic;
32class SkTSect;
33
34// define this when running fuzz
35// #define SK_BUILD_FOR_FUZZER
36
37// fake classes to fool msvs Visual Studio 2018 Immediate Window
38#define FakeClasses(a, b) \
39class SkDebugTCoincident##a##b; \
40class SkDebugTSect##a##b; \
41class SkDebugTSpan##a##b
42
43FakeClasses(Quad, Quad);
44FakeClasses(Conic, Quad);
45FakeClasses(Conic, Conic);
46FakeClasses(Cubic, Quad);
47FakeClasses(Cubic, Conic);
48FakeClasses(Cubic, Cubic);
49
50#undef FakeClasses
51
52#ifdef SK_RELEASE
53#define FORCE_RELEASE 1
54#else
55#define FORCE_RELEASE 1  // set force release to 1 for multiple thread -- no debugging
56#endif
57
58#define DEBUG_UNDER_DEVELOPMENT 0
59
60#define ONE_OFF_DEBUG 0
61#define ONE_OFF_DEBUG_MATHEMATICA 0
62
63#if defined(SK_BUILD_FOR_WIN) || defined(SK_BUILD_FOR_ANDROID)
64    #define SK_RAND(seed) rand()
65#else
66    #define SK_RAND(seed) rand_r(&seed)
67#endif
68#ifdef SK_BUILD_FOR_WIN
69    #define SK_SNPRINTF _snprintf
70#else
71    #define SK_SNPRINTF snprintf
72#endif
73
74#define WIND_AS_STRING(x) char x##Str[12]; \
75        if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \
76        else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
77
78#if FORCE_RELEASE
79
80#define DEBUG_ACTIVE_OP 0
81#define DEBUG_ACTIVE_SPANS 0
82#define DEBUG_ADD_INTERSECTING_TS 0
83#define DEBUG_ADD_T 0
84#define DEBUG_ALIGNMENT 0
85#define DEBUG_ANGLE 0
86#define DEBUG_ASSEMBLE 0
87#define DEBUG_COINCIDENCE 0
88#define DEBUG_COINCIDENCE_DUMP 0  // accumulate and dump which algorithms fired
89#define DEBUG_COINCIDENCE_ORDER 0  // for well behaved curves, check if pairs match up in t-order
90#define DEBUG_COINCIDENCE_VERBOSE 0  // usually whether the next function generates coincidence
91#define DEBUG_CUBIC_BINARY_SEARCH 0
92#define DEBUG_CUBIC_SPLIT 0
93#define DEBUG_DUMP_SEGMENTS 0
94#define DEBUG_DUMP_VERIFY 0
95#define DEBUG_FLOW 0
96#define DEBUG_LIMIT_WIND_SUM 0
97#define DEBUG_MARK_DONE 0
98#define DEBUG_PATH_CONSTRUCTION 0
99#define DEBUG_PERP 0
100#define DEBUG_SORT 0
101#define DEBUG_T_SECT 0
102#define DEBUG_T_SECT_DUMP 0
103#define DEBUG_T_SECT_LOOP_COUNT 0
104#define DEBUG_VALIDATE 0
105#define DEBUG_WINDING 0
106#define DEBUG_WINDING_AT_T 0
107
108#else
109
110#define DEBUG_ACTIVE_OP 1
111#define DEBUG_ACTIVE_SPANS 1
112#define DEBUG_ADD_INTERSECTING_TS 1
113#define DEBUG_ADD_T 1
114#define DEBUG_ALIGNMENT 0
115#define DEBUG_ANGLE 1
116#define DEBUG_ASSEMBLE 1
117#define DEBUG_COINCIDENCE 1
118#define DEBUG_COINCIDENCE_DUMP 0
119#define DEBUG_COINCIDENCE_ORDER 0  // tight arc quads may generate out-of-order coincidence spans
120#define DEBUG_COINCIDENCE_VERBOSE 1
121#define DEBUG_CUBIC_BINARY_SEARCH 0
122#define DEBUG_CUBIC_SPLIT 1
123#define DEBUG_DUMP_VERIFY 0
124#define DEBUG_DUMP_SEGMENTS 1
125#define DEBUG_FLOW 1
126#define DEBUG_LIMIT_WIND_SUM 15
127#define DEBUG_MARK_DONE 1
128#define DEBUG_PATH_CONSTRUCTION 1
129#define DEBUG_PERP 1
130#define DEBUG_SORT 1
131#define DEBUG_T_SECT 0        // enabling may trigger validate asserts even though op does not fail
132#define DEBUG_T_SECT_DUMP 0  // Use 1 normally. Use 2 to number segments, 3 for script output
133#define DEBUG_T_SECT_LOOP_COUNT 0
134#define DEBUG_VALIDATE 1
135#define DEBUG_WINDING 1
136#define DEBUG_WINDING_AT_T 1
137
138#endif
139
140#ifdef SK_RELEASE
141    #define SkDEBUGRELEASE(a, b) b
142    #define SkDEBUGPARAMS(...)
143#else
144    #define SkDEBUGRELEASE(a, b) a
145    #define SkDEBUGPARAMS(...) , __VA_ARGS__
146#endif
147
148#if DEBUG_VALIDATE == 0
149    #define PATH_OPS_DEBUG_VALIDATE_PARAMS(...)
150#else
151    #define PATH_OPS_DEBUG_VALIDATE_PARAMS(...) , __VA_ARGS__
152#endif
153
154#if DEBUG_T_SECT == 0
155    #define PATH_OPS_DEBUG_T_SECT_RELEASE(a, b) b
156    #define PATH_OPS_DEBUG_T_SECT_PARAMS(...)
157    #define PATH_OPS_DEBUG_T_SECT_CODE(...)
158#else
159    #define PATH_OPS_DEBUG_T_SECT_RELEASE(a, b) a
160    #define PATH_OPS_DEBUG_T_SECT_PARAMS(...) , __VA_ARGS__
161    #define PATH_OPS_DEBUG_T_SECT_CODE(...) __VA_ARGS__
162#endif
163
164#if DEBUG_T_SECT_DUMP > 1
165    extern int gDumpTSectNum;
166#endif
167
168#if DEBUG_COINCIDENCE || DEBUG_COINCIDENCE_DUMP
169    #define DEBUG_COIN 1
170#else
171    #define DEBUG_COIN 0
172#endif
173
174#if DEBUG_COIN
175    #define DEBUG_COIN_DECLARE_ONLY_PARAMS() \
176            int lineNo, SkOpPhase phase, int iteration
177    #define DEBUG_COIN_DECLARE_PARAMS() \
178            , DEBUG_COIN_DECLARE_ONLY_PARAMS()
179    #define DEBUG_COIN_ONLY_PARAMS() \
180            __LINE__, SkOpPhase::kNoChange, 0
181    #define DEBUG_COIN_PARAMS() \
182            , DEBUG_COIN_ONLY_PARAMS()
183    #define DEBUG_ITER_ONLY_PARAMS(iteration) \
184            __LINE__, SkOpPhase::kNoChange, iteration
185    #define DEBUG_ITER_PARAMS(iteration) \
186            , DEBUG_ITER_ONLY_PARAMS(iteration)
187    #define DEBUG_PHASE_ONLY_PARAMS(phase) \
188            __LINE__, SkOpPhase::phase, 0
189    #define DEBUG_PHASE_PARAMS(phase) \
190            , DEBUG_PHASE_ONLY_PARAMS(phase)
191    #define DEBUG_SET_PHASE() \
192            this->globalState()->debugSetPhase(__func__, lineNo, phase, iteration)
193    #define DEBUG_STATIC_SET_PHASE(obj) \
194            obj->globalState()->debugSetPhase(__func__, lineNo, phase, iteration)
195#elif DEBUG_VALIDATE
196    #define DEBUG_COIN_DECLARE_ONLY_PARAMS() \
197            SkOpPhase phase
198    #define DEBUG_COIN_DECLARE_PARAMS() \
199            , DEBUG_COIN_DECLARE_ONLY_PARAMS()
200    #define DEBUG_COIN_ONLY_PARAMS() \
201            SkOpPhase::kNoChange
202    #define DEBUG_COIN_PARAMS() \
203            , DEBUG_COIN_ONLY_PARAMS()
204    #define DEBUG_ITER_ONLY_PARAMS(iteration) \
205            SkOpPhase::kNoChange
206    #define DEBUG_ITER_PARAMS(iteration) \
207            , DEBUG_ITER_ONLY_PARAMS(iteration)
208    #define DEBUG_PHASE_ONLY_PARAMS(phase) \
209            SkOpPhase::phase
210    #define DEBUG_PHASE_PARAMS(phase) \
211            , DEBUG_PHASE_ONLY_PARAMS(phase)
212    #define DEBUG_SET_PHASE() \
213            this->globalState()->debugSetPhase(phase)
214    #define DEBUG_STATIC_SET_PHASE(obj) \
215            obj->globalState()->debugSetPhase(phase)
216#else
217    #define DEBUG_COIN_DECLARE_ONLY_PARAMS()
218    #define DEBUG_COIN_DECLARE_PARAMS()
219    #define DEBUG_COIN_ONLY_PARAMS()
220    #define DEBUG_COIN_PARAMS()
221    #define DEBUG_ITER_ONLY_PARAMS(iteration)
222    #define DEBUG_ITER_PARAMS(iteration)
223    #define DEBUG_PHASE_ONLY_PARAMS(phase)
224    #define DEBUG_PHASE_PARAMS(phase)
225    #define DEBUG_SET_PHASE()
226    #define DEBUG_STATIC_SET_PHASE(obj)
227#endif
228
229#define CUBIC_DEBUG_STR  "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
230#define CONIC_DEBUG_STR "{{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}, %1.9g}"
231#define QUAD_DEBUG_STR   "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
232#define LINE_DEBUG_STR   "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
233#define PT_DEBUG_STR "{{%1.9g,%1.9g}}"
234
235#define T_DEBUG_STR(t, n) #t "[" #n "]=%1.9g"
236#define TX_DEBUG_STR(t) #t "[%d]=%1.9g"
237#define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY
238#define CONIC_DEBUG_DATA(c, w) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, w
239#define QUAD_DEBUG_DATA(q)  q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY
240#define LINE_DEBUG_DATA(l)  l[0].fX, l[0].fY, l[1].fX, l[1].fY
241#define PT_DEBUG_DATA(i, n) i.pt(n).asSkPoint().fX, i.pt(n).asSkPoint().fY
242
243#ifndef DEBUG_TEST
244#define DEBUG_TEST 0
245#endif
246
247// Tests with extreme numbers may fail, but all other tests should never fail.
248#define FAIL_IF(cond) \
249        do { bool fail = (cond); SkOPASSERT(!fail); if (fail) return false; } while (false)
250
251#define FAIL_WITH_NULL_IF(cond) \
252        do { bool fail = (cond); SkOPASSERT(!fail); if (fail) return nullptr; } while (false)
253
254class SkPathOpsDebug {
255public:
256#if DEBUG_COIN
257    struct GlitchLog;
258
259    enum GlitchType {
260        kUninitialized_Glitch,
261        kAddCorruptCoin_Glitch,
262        kAddExpandedCoin_Glitch,
263        kAddExpandedFail_Glitch,
264        kAddIfCollapsed_Glitch,
265        kAddIfMissingCoin_Glitch,
266        kAddMissingCoin_Glitch,
267        kAddMissingExtend_Glitch,
268        kAddOrOverlap_Glitch,
269        kCollapsedCoin_Glitch,
270        kCollapsedDone_Glitch,
271        kCollapsedOppValue_Glitch,
272        kCollapsedSpan_Glitch,
273        kCollapsedWindValue_Glitch,
274        kCorrectEnd_Glitch,
275        kDeletedCoin_Glitch,
276        kExpandCoin_Glitch,
277        kFail_Glitch,
278        kMarkCoinEnd_Glitch,
279        kMarkCoinInsert_Glitch,
280        kMarkCoinMissing_Glitch,
281        kMarkCoinStart_Glitch,
282        kMergeMatches_Glitch,
283        kMissingCoin_Glitch,
284        kMissingDone_Glitch,
285        kMissingIntersection_Glitch,
286        kMoveMultiple_Glitch,
287        kMoveNearbyClearAll_Glitch,
288        kMoveNearbyClearAll2_Glitch,
289        kMoveNearbyMerge_Glitch,
290        kMoveNearbyMergeFinal_Glitch,
291        kMoveNearbyRelease_Glitch,
292        kMoveNearbyReleaseFinal_Glitch,
293        kReleasedSpan_Glitch,
294        kReturnFalse_Glitch,
295        kUnaligned_Glitch,
296        kUnalignedHead_Glitch,
297        kUnalignedTail_Glitch,
298    };
299
300    struct CoinDictEntry {
301        int fIteration;
302        int fLineNumber;
303        GlitchType fGlitchType;
304        const char* fFunctionName;
305    };
306
307    struct CoinDict {
308        void add(const CoinDictEntry& key);
309        void add(const CoinDict& dict);
310        void dump(const char* str, bool visitCheck) const;
311        SkTDArray<CoinDictEntry> fDict;
312    };
313
314    static CoinDict gCoinSumChangedDict;
315    static CoinDict gCoinSumVisitedDict;
316    static CoinDict gCoinVistedDict;
317#endif
318
319#if defined(SK_DEBUG) || !FORCE_RELEASE
320    static int gContourID;
321    static int gSegmentID;
322#endif
323
324#if DEBUG_SORT
325    static int gSortCountDefault;
326    static int gSortCount;
327#endif
328
329#if DEBUG_ACTIVE_OP
330    static const char* kPathOpStr[];
331#endif
332    static bool gRunFail;
333    static bool gVeryVerbose;
334
335#if DEBUG_ACTIVE_SPANS
336    static SkString gActiveSpans;
337#endif
338#if DEBUG_DUMP_VERIFY
339    static bool gDumpOp;
340    static bool gVerifyOp;
341#endif
342
343    static const char* OpStr(SkPathOp );
344    static void MathematicaIze(char* str, size_t bufferSize);
345    static bool ValidWind(int winding);
346    static void WindingPrintf(int winding);
347
348    static void ShowActiveSpans(SkOpContourHead* contourList);
349    static void ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration);
350    static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name);
351
352    static bool ChaseContains(const SkTDArray<SkOpSpanBase*>& , const SkOpSpanBase* );
353
354    static void CheckHealth(class SkOpContourHead* contourList);
355
356#if DEBUG_COIN
357   static void DumpCoinDict();
358   static void DumpGlitchType(GlitchType );
359#endif
360
361};
362
363// Visual Studio 2017 does not permit calling member functions from the Immediate Window.
364// Global functions work fine, however. Use globals rather than static members inside a class.
365const SkOpAngle* AngleAngle(const SkOpAngle*, int id);
366SkOpContour* AngleContour(SkOpAngle*, int id);
367const SkOpPtT* AnglePtT(const SkOpAngle*, int id);
368const SkOpSegment* AngleSegment(const SkOpAngle*, int id);
369const SkOpSpanBase* AngleSpan(const SkOpAngle*, int id);
370
371const SkOpAngle* ContourAngle(SkOpContour*, int id);
372SkOpContour* ContourContour(SkOpContour*, int id);
373const SkOpPtT* ContourPtT(SkOpContour*, int id);
374const SkOpSegment* ContourSegment(SkOpContour*, int id);
375const SkOpSpanBase* ContourSpan(SkOpContour*, int id);
376
377const SkOpAngle* CoincidenceAngle(SkOpCoincidence*, int id);
378SkOpContour* CoincidenceContour(SkOpCoincidence*, int id);
379const SkOpPtT* CoincidencePtT(SkOpCoincidence*, int id);
380const SkOpSegment* CoincidenceSegment(SkOpCoincidence*, int id);
381const SkOpSpanBase* CoincidenceSpan(SkOpCoincidence*, int id);
382
383const SkOpAngle* PtTAngle(const SkOpPtT*, int id);
384SkOpContour* PtTContour(SkOpPtT*, int id);
385const SkOpPtT* PtTPtT(const SkOpPtT*, int id);
386const SkOpSegment* PtTSegment(const SkOpPtT*, int id);
387const SkOpSpanBase* PtTSpan(const SkOpPtT*, int id);
388
389const SkOpAngle* SegmentAngle(const SkOpSegment*, int id);
390SkOpContour* SegmentContour(SkOpSegment*, int id);
391const SkOpPtT* SegmentPtT(const SkOpSegment*, int id);
392const SkOpSegment* SegmentSegment(const SkOpSegment*, int id);
393const SkOpSpanBase* SegmentSpan(const SkOpSegment*, int id);
394
395const SkOpAngle* SpanAngle(const SkOpSpanBase*, int id);
396SkOpContour* SpanContour(SkOpSpanBase*, int id);
397const SkOpPtT* SpanPtT(const SkOpSpanBase*, int id);
398const SkOpSegment* SpanSegment(const SkOpSpanBase*, int id);
399const SkOpSpanBase* SpanSpan(const SkOpSpanBase*, int id);
400
401#if DEBUG_DUMP_VERIFY
402void DumpOp(const SkPath& one, const SkPath& two, SkPathOp op,
403        const char* testName);
404void DumpOp(FILE* file, const SkPath& one, const SkPath& two, SkPathOp op,
405        const char* testName);
406void DumpSimplify(const SkPath& path, const char* testName);
407void DumpSimplify(FILE* file, const SkPath& path, const char* testName);
408void ReportOpFail(const SkPath& one, const SkPath& two, SkPathOp op);
409void ReportSimplifyFail(const SkPath& path);
410void VerifyOp(const SkPath& one, const SkPath& two, SkPathOp op,
411    const SkPath& result);
412void VerifySimplify(const SkPath& path, const SkPath& result);
413#endif
414
415// global path dumps for msvs Visual Studio 17 to use from Immediate Window
416void Dump(const SkOpContour& );
417void DumpAll(const SkOpContour& );
418void DumpAngles(const SkOpContour& );
419void DumpContours(const SkOpContour& );
420void DumpContoursAll(const SkOpContour& );
421void DumpContoursAngles(const SkOpContour& );
422void DumpContoursPts(const SkOpContour& );
423void DumpContoursPt(const SkOpContour& , int segmentID);
424void DumpContoursSegment(const SkOpContour& , int segmentID);
425void DumpContoursSpan(const SkOpContour& , int segmentID);
426void DumpContoursSpans(const SkOpContour& );
427void DumpPt(const SkOpContour& , int );
428void DumpPts(const SkOpContour& , const char* prefix = "seg");
429void DumpSegment(const SkOpContour& , int );
430void DumpSegments(const SkOpContour& , const char* prefix = "seg", SkPathOp op = (SkPathOp) -1);
431void DumpSpan(const SkOpContour& , int );
432void DumpSpans(const SkOpContour& );
433
434void Dump(const SkOpSegment& );
435void DumpAll(const SkOpSegment& );
436void DumpAngles(const SkOpSegment& );
437void DumpCoin(const SkOpSegment& );
438void DumpPts(const SkOpSegment& , const char* prefix = "seg");
439
440void Dump(const SkOpPtT& );
441void DumpAll(const SkOpPtT& );
442
443void Dump(const SkOpSpanBase& );
444void DumpCoin(const SkOpSpanBase& );
445void DumpAll(const SkOpSpanBase& );
446
447void DumpCoin(const SkOpSpan& );
448bool DumpSpan(const SkOpSpan& );
449
450void Dump(const SkDConic& );
451void DumpID(const SkDConic& , int id);
452
453void Dump(const SkDCubic& );
454void DumpID(const SkDCubic& , int id);
455
456void Dump(const SkDLine& );
457void DumpID(const SkDLine& , int id);
458
459void Dump(const SkDQuad& );
460void DumpID(const SkDQuad& , int id);
461
462void Dump(const SkDPoint& );
463
464void Dump(const SkOpAngle& );
465
466// generates tools/path_sorter.htm and path_visualizer.htm compatible data
467void DumpQ(const SkDQuad& quad1, const SkDQuad& quad2, int testNo);
468void DumpT(const SkDQuad& quad, double t);
469
470// global path dumps for msvs Visual Studio 17 to use from Immediate Window
471void Dump(const SkPath& path);
472void DumpHex(const SkPath& path);
473
474#endif
475