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// dummy classes to fool msvs Visual Studio 2018 Immediate Window
38#define DummyClasses(a, b) \
39class SkDebugTCoincident##a##b; \
40class SkDebugTSect##a##b; \
41class SkDebugTSpan##a##b
42
43DummyClasses(Quad, Quad);
44DummyClasses(Conic, Quad);
45DummyClasses(Conic, Conic);
46DummyClasses(Cubic, Quad);
47DummyClasses(Cubic, Conic);
48DummyClasses(Cubic, Cubic);
49
50#undef DummyClasses
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 // sanity checking
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
254// Some functions serve two masters: one allows the function to fail, the other expects success
255// always. If abort is true, tests with normal numbers may not fail and assert if they do so.
256// If abort is false, both normal and extreme numbers may return false without asserting.
257#define RETURN_FALSE_IF(abort, cond) \
258 do { bool fail = (cond); SkOPASSERT(!(abort) || !fail); if (fail) return false; \
259 } while (false)
260
261class SkPathOpsDebug {
262public:
263#if DEBUG_COIN
264 struct GlitchLog;
265
266 enum GlitchType {
267 kUninitialized_Glitch,
268 kAddCorruptCoin_Glitch,
269 kAddExpandedCoin_Glitch,
270 kAddExpandedFail_Glitch,
271 kAddIfCollapsed_Glitch,
272 kAddIfMissingCoin_Glitch,
273 kAddMissingCoin_Glitch,
274 kAddMissingExtend_Glitch,
275 kAddOrOverlap_Glitch,
276 kCollapsedCoin_Glitch,
277 kCollapsedDone_Glitch,
278 kCollapsedOppValue_Glitch,
279 kCollapsedSpan_Glitch,
280 kCollapsedWindValue_Glitch,
281 kCorrectEnd_Glitch,
282 kDeletedCoin_Glitch,
283 kExpandCoin_Glitch,
284 kFail_Glitch,
285 kMarkCoinEnd_Glitch,
286 kMarkCoinInsert_Glitch,
287 kMarkCoinMissing_Glitch,
288 kMarkCoinStart_Glitch,
289 kMergeMatches_Glitch,
290 kMissingCoin_Glitch,
291 kMissingDone_Glitch,
292 kMissingIntersection_Glitch,
293 kMoveMultiple_Glitch,
294 kMoveNearbyClearAll_Glitch,
295 kMoveNearbyClearAll2_Glitch,
296 kMoveNearbyMerge_Glitch,
297 kMoveNearbyMergeFinal_Glitch,
298 kMoveNearbyRelease_Glitch,
299 kMoveNearbyReleaseFinal_Glitch,
300 kReleasedSpan_Glitch,
301 kReturnFalse_Glitch,
302 kUnaligned_Glitch,
303 kUnalignedHead_Glitch,
304 kUnalignedTail_Glitch,
305 };
306
307 struct CoinDictEntry {
308 int fIteration;
309 int fLineNumber;
310 GlitchType fGlitchType;
311 const char* fFunctionName;
312 };
313
314 struct CoinDict {
315 void add(const CoinDictEntry& key);
316 void add(const CoinDict& dict);
317 void dump(const char* str, bool visitCheck) const;
318 SkTDArray<CoinDictEntry> fDict;
319 };
320
321 static CoinDict gCoinSumChangedDict;
322 static CoinDict gCoinSumVisitedDict;
323 static CoinDict gCoinVistedDict;
324#endif
325
326#if defined(SK_DEBUG) || !FORCE_RELEASE
327 static int gContourID;
328 static int gSegmentID;
329#endif
330
331#if DEBUG_SORT
332 static int gSortCountDefault;
333 static int gSortCount;
334#endif
335
336#if DEBUG_ACTIVE_OP
337 static const char* kPathOpStr[];
338#endif
339 static bool gRunFail;
340 static bool gVeryVerbose;
341
342#if DEBUG_ACTIVE_SPANS
343 static SkString gActiveSpans;
344#endif
345#if DEBUG_DUMP_VERIFY
346 static bool gDumpOp;
347 static bool gVerifyOp;
348#endif
349
350 static const char* OpStr(SkPathOp );
351 static void MathematicaIze(char* str, size_t bufferSize);
352 static bool ValidWind(int winding);
353 static void WindingPrintf(int winding);
354
355 static void ShowActiveSpans(SkOpContourHead* contourList);
356 static void ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration);
357 static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name);
358
359 static bool ChaseContains(const SkTDArray<SkOpSpanBase*>& , const SkOpSpanBase* );
360
361 static void CheckHealth(class SkOpContourHead* contourList);
362
363#if DEBUG_COIN
364 static void DumpCoinDict();
365 static void DumpGlitchType(GlitchType );
366#endif
367
368};
369
370// Visual Studio 2017 does not permit calling member functions from the Immediate Window.
371// Global functions work fine, however. Use globals rather than static members inside a class.
372const SkOpAngle* AngleAngle(const SkOpAngle*, int id);
373SkOpContour* AngleContour(SkOpAngle*, int id);
374const SkOpPtT* AnglePtT(const SkOpAngle*, int id);
375const SkOpSegment* AngleSegment(const SkOpAngle*, int id);
376const SkOpSpanBase* AngleSpan(const SkOpAngle*, int id);
377
378const SkOpAngle* ContourAngle(SkOpContour*, int id);
379SkOpContour* ContourContour(SkOpContour*, int id);
380const SkOpPtT* ContourPtT(SkOpContour*, int id);
381const SkOpSegment* ContourSegment(SkOpContour*, int id);
382const SkOpSpanBase* ContourSpan(SkOpContour*, int id);
383
384const SkOpAngle* CoincidenceAngle(SkOpCoincidence*, int id);
385SkOpContour* CoincidenceContour(SkOpCoincidence*, int id);
386const SkOpPtT* CoincidencePtT(SkOpCoincidence*, int id);
387const SkOpSegment* CoincidenceSegment(SkOpCoincidence*, int id);
388const SkOpSpanBase* CoincidenceSpan(SkOpCoincidence*, int id);
389
390const SkOpAngle* PtTAngle(const SkOpPtT*, int id);
391SkOpContour* PtTContour(SkOpPtT*, int id);
392const SkOpPtT* PtTPtT(const SkOpPtT*, int id);
393const SkOpSegment* PtTSegment(const SkOpPtT*, int id);
394const SkOpSpanBase* PtTSpan(const SkOpPtT*, int id);
395
396const SkOpAngle* SegmentAngle(const SkOpSegment*, int id);
397SkOpContour* SegmentContour(SkOpSegment*, int id);
398const SkOpPtT* SegmentPtT(const SkOpSegment*, int id);
399const SkOpSegment* SegmentSegment(const SkOpSegment*, int id);
400const SkOpSpanBase* SegmentSpan(const SkOpSegment*, int id);
401
402const SkOpAngle* SpanAngle(const SkOpSpanBase*, int id);
403SkOpContour* SpanContour(SkOpSpanBase*, int id);
404const SkOpPtT* SpanPtT(const SkOpSpanBase*, int id);
405const SkOpSegment* SpanSegment(const SkOpSpanBase*, int id);
406const SkOpSpanBase* SpanSpan(const SkOpSpanBase*, int id);
407
408#if DEBUG_DUMP_VERIFY
409void DumpOp(const SkPath& one, const SkPath& two, SkPathOp op,
410 const char* testName);
411void DumpOp(FILE* file, const SkPath& one, const SkPath& two, SkPathOp op,
412 const char* testName);
413void DumpSimplify(const SkPath& path, const char* testName);
414void DumpSimplify(FILE* file, const SkPath& path, const char* testName);
415void ReportOpFail(const SkPath& one, const SkPath& two, SkPathOp op);
416void ReportSimplifyFail(const SkPath& path);
417void VerifyOp(const SkPath& one, const SkPath& two, SkPathOp op,
418 const SkPath& result);
419void VerifySimplify(const SkPath& path, const SkPath& result);
420#endif
421
422// global path dumps for msvs Visual Studio 17 to use from Immediate Window
423void Dump(const SkOpContour& );
424void DumpAll(const SkOpContour& );
425void DumpAngles(const SkOpContour& );
426void DumpContours(const SkOpContour& );
427void DumpContoursAll(const SkOpContour& );
428void DumpContoursAngles(const SkOpContour& );
429void DumpContoursPts(const SkOpContour& );
430void DumpContoursPt(const SkOpContour& , int segmentID);
431void DumpContoursSegment(const SkOpContour& , int segmentID);
432void DumpContoursSpan(const SkOpContour& , int segmentID);
433void DumpContoursSpans(const SkOpContour& );
434void DumpPt(const SkOpContour& , int );
435void DumpPts(const SkOpContour& , const char* prefix = "seg");
436void DumpSegment(const SkOpContour& , int );
437void DumpSegments(const SkOpContour& , const char* prefix = "seg", SkPathOp op = (SkPathOp) -1);
438void DumpSpan(const SkOpContour& , int );
439void DumpSpans(const SkOpContour& );
440
441void Dump(const SkOpSegment& );
442void DumpAll(const SkOpSegment& );
443void DumpAngles(const SkOpSegment& );
444void DumpCoin(const SkOpSegment& );
445void DumpPts(const SkOpSegment& , const char* prefix = "seg");
446
447void Dump(const SkOpPtT& );
448void DumpAll(const SkOpPtT& );
449
450void Dump(const SkOpSpanBase& );
451void DumpCoin(const SkOpSpanBase& );
452void DumpAll(const SkOpSpanBase& );
453
454void DumpCoin(const SkOpSpan& );
455bool DumpSpan(const SkOpSpan& );
456
457void Dump(const SkDConic& );
458void DumpID(const SkDConic& , int id);
459
460void Dump(const SkDCubic& );
461void DumpID(const SkDCubic& , int id);
462
463void Dump(const SkDLine& );
464void DumpID(const SkDLine& , int id);
465
466void Dump(const SkDQuad& );
467void DumpID(const SkDQuad& , int id);
468
469void Dump(const SkDPoint& );
470
471void Dump(const SkOpAngle& );
472
473// generates tools/path_sorter.htm and path_visualizer.htm compatible data
474void DumpQ(const SkDQuad& quad1, const SkDQuad& quad2, int testNo);
475void DumpT(const SkDQuad& quad, double t);
476
477// global path dumps for msvs Visual Studio 17 to use from Immediate Window
478void Dump(const SkPath& path);
479void DumpHex(const SkPath& path);
480
481#endif
482