submodule/skia/src/pathops/SkPathOpsDebug.h

   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 SK_BUILD_FOR_FUZZER
  36
  37 // fake classes to fool msvs Visual Studio 2018 Immediate Window
  38 #define FakeClasses(a, b) \
  39 class SkDebugTCoincident##a##b; \
  40 class SkDebugTSect##a##b; \
  41 class SkDebugTSpan##a##b
  42
  43 FakeClasses(Quad, Quad);
  44 FakeClasses(Conic, Quad);
  45 FakeClasses(Conic, Conic);
  46 FakeClasses(Cubic, Quad);
  47 FakeClasses(Cubic, Conic);
  48 FakeClasses(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
 254 class SkPathOpsDebug {
 255 public:
 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.
 365 const SkOpAngle* AngleAngle(const SkOpAngle*, int id);
 366 SkOpContour* AngleContour(SkOpAngle*, int id);
 367 const SkOpPtT* AnglePtT(const SkOpAngle*, int id);
 368 const SkOpSegment* AngleSegment(const SkOpAngle*, int id);
 369 const SkOpSpanBase* AngleSpan(const SkOpAngle*, int id);
 370
 371 const SkOpAngle* ContourAngle(SkOpContour*, int id);
 372 SkOpContour* ContourContour(SkOpContour*, int id);
 373 const SkOpPtT* ContourPtT(SkOpContour*, int id);
 374 const SkOpSegment* ContourSegment(SkOpContour*, int id);
 375 const SkOpSpanBase* ContourSpan(SkOpContour*, int id);
 376
 377 const SkOpAngle* CoincidenceAngle(SkOpCoincidence*, int id);
 378 SkOpContour* CoincidenceContour(SkOpCoincidence*, int id);
 379 const SkOpPtT* CoincidencePtT(SkOpCoincidence*, int id);
 380 const SkOpSegment* CoincidenceSegment(SkOpCoincidence*, int id);
 381 const SkOpSpanBase* CoincidenceSpan(SkOpCoincidence*, int id);
 382
 383 const SkOpAngle* PtTAngle(const SkOpPtT*, int id);
 384 SkOpContour* PtTContour(SkOpPtT*, int id);
 385 const SkOpPtT* PtTPtT(const SkOpPtT*, int id);
 386 const SkOpSegment* PtTSegment(const SkOpPtT*, int id);
 387 const SkOpSpanBase* PtTSpan(const SkOpPtT*, int id);
 388
 389 const SkOpAngle* SegmentAngle(const SkOpSegment*, int id);
 390 SkOpContour* SegmentContour(SkOpSegment*, int id);
 391 const SkOpPtT* SegmentPtT(const SkOpSegment*, int id);
 392 const SkOpSegment* SegmentSegment(const SkOpSegment*, int id);
 393 const SkOpSpanBase* SegmentSpan(const SkOpSegment*, int id);
 394
 395 const SkOpAngle* SpanAngle(const SkOpSpanBase*, int id);
 396 SkOpContour* SpanContour(SkOpSpanBase*, int id);
 397 const SkOpPtT* SpanPtT(const SkOpSpanBase*, int id);
 398 const SkOpSegment* SpanSegment(const SkOpSpanBase*, int id);
 399 const SkOpSpanBase* SpanSpan(const SkOpSpanBase*, int id);
 400
 401 #if DEBUG_DUMP_VERIFY
 402 void DumpOp(const SkPath& one, const SkPath& two, SkPathOp op,
 403         const char* testName);
 404 void DumpOp(FILE* file, const SkPath& one, const SkPath& two, SkPathOp op,
 405         const char* testName);
 406 void DumpSimplify(const SkPath& path, const char* testName);
 407 void DumpSimplify(FILE* file, const SkPath& path, const char* testName);
 408 void ReportOpFail(const SkPath& one, const SkPath& two, SkPathOp op);
 409 void ReportSimplifyFail(const SkPath& path);
 410 void VerifyOp(const SkPath& one, const SkPath& two, SkPathOp op,
 411     const SkPath& result);
 412 void VerifySimplify(const SkPath& path, const SkPath& result);
 413 #endif
 414
 415 // global path dumps for msvs Visual Studio 17 to use from Immediate Window
 416 void Dump(const SkOpContour& );
 417 void DumpAll(const SkOpContour& );
 418 void DumpAngles(const SkOpContour& );
 419 void DumpContours(const SkOpContour& );
 420 void DumpContoursAll(const SkOpContour& );
 421 void DumpContoursAngles(const SkOpContour& );
 422 void DumpContoursPts(const SkOpContour& );
 423 void DumpContoursPt(const SkOpContour& , int segmentID);
 424 void DumpContoursSegment(const SkOpContour& , int segmentID);
 425 void DumpContoursSpan(const SkOpContour& , int segmentID);
 426 void DumpContoursSpans(const SkOpContour& );
 427 void DumpPt(const SkOpContour& , int );
 428 void DumpPts(const SkOpContour& , const char* prefix = "seg");
 429 void DumpSegment(const SkOpContour& , int );
 430 void DumpSegments(const SkOpContour& , const char* prefix = "seg", SkPathOp op = (SkPathOp) -1);
 431 void DumpSpan(const SkOpContour& , int );
 432 void DumpSpans(const SkOpContour& );
 433
 434 void Dump(const SkOpSegment& );
 435 void DumpAll(const SkOpSegment& );
 436 void DumpAngles(const SkOpSegment& );
 437 void DumpCoin(const SkOpSegment& );
 438 void DumpPts(const SkOpSegment& , const char* prefix = "seg");
 439
 440 void Dump(const SkOpPtT& );
 441 void DumpAll(const SkOpPtT& );
 442
 443 void Dump(const SkOpSpanBase& );
 444 void DumpCoin(const SkOpSpanBase& );
 445 void DumpAll(const SkOpSpanBase& );
 446
 447 void DumpCoin(const SkOpSpan& );
 448 bool DumpSpan(const SkOpSpan& );
 449
 450 void Dump(const SkDConic& );
 451 void DumpID(const SkDConic& , int id);
 452
 453 void Dump(const SkDCubic& );
 454 void DumpID(const SkDCubic& , int id);
 455
 456 void Dump(const SkDLine& );
 457 void DumpID(const SkDLine& , int id);
 458
 459 void Dump(const SkDQuad& );
 460 void DumpID(const SkDQuad& , int id);
 461
 462 void Dump(const SkDPoint& );
 463
 464 void Dump(const SkOpAngle& );
 465
 466 // generates tools/path_sorter.htm and path_visualizer.htm compatible data
 467 void DumpQ(const SkDQuad& quad1, const SkDQuad& quad2, int testNo);
 468 void DumpT(const SkDQuad& quad, double t);
 469
 470 // global path dumps for msvs Visual Studio 17 to use from Immediate Window
 471 void Dump(const SkPath& path);
 472 void DumpHex(const SkPath& path);
 473
 474 #endif