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 IS_FUZZING_WITH_LIBFUZZER
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