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