Home | History | Annotate | Download | only in pathops
      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 "SkPathOps.h"
     11 #include "SkTypes.h"
     12 
     13 #include <stdlib.h>
     14 #include <stdio.h>
     15 
     16 enum class SkOpPhase : char;
     17 class SkOpContourHead;
     18 
     19 #ifdef SK_RELEASE
     20 #define FORCE_RELEASE 1
     21 #else
     22 #define FORCE_RELEASE 1  // set force release to 1 for multiple thread -- no debugging
     23 #endif
     24 
     25 #define DEBUG_UNDER_DEVELOPMENT 0
     26 
     27 #define ONE_OFF_DEBUG 0
     28 #define ONE_OFF_DEBUG_MATHEMATICA 0
     29 
     30 #if defined(SK_BUILD_FOR_WIN) || defined(SK_BUILD_FOR_ANDROID)
     31     #define SK_RAND(seed) rand()
     32 #else
     33     #define SK_RAND(seed) rand_r(&seed)
     34 #endif
     35 #ifdef SK_BUILD_FOR_WIN
     36     #define SK_SNPRINTF _snprintf
     37 #else
     38     #define SK_SNPRINTF snprintf
     39 #endif
     40 
     41 #define WIND_AS_STRING(x) char x##Str[12]; \
     42         if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \
     43         else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
     44 
     45 #if FORCE_RELEASE
     46 
     47 #define DEBUG_ACTIVE_OP 0
     48 #define DEBUG_ACTIVE_SPANS 0
     49 #define DEBUG_ADD_INTERSECTING_TS 0
     50 #define DEBUG_ADD_T 0
     51 #define DEBUG_ALIGNMENT 0
     52 #define DEBUG_ANGLE 0
     53 #define DEBUG_ASSEMBLE 0
     54 #define DEBUG_COINCIDENCE 0  // sanity checking
     55 #define DEBUG_COINCIDENCE_DUMP 0  // accumulate and dump which algorithms fired
     56 #define DEBUG_COINCIDENCE_ORDER 0  // for well behaved curves, check if pairs match up in t-order
     57 #define DEBUG_COINCIDENCE_VERBOSE 0  // usually whether the next function generates coincidence
     58 #define DEBUG_CUBIC_BINARY_SEARCH 0
     59 #define DEBUG_CUBIC_SPLIT 0
     60 #define DEBUG_DUMP_SEGMENTS 0
     61 #define DEBUG_DUMP_VERIFY 0
     62 #define DEBUG_FLOW 0
     63 #define DEBUG_LIMIT_WIND_SUM 0
     64 #define DEBUG_MARK_DONE 0
     65 #define DEBUG_PATH_CONSTRUCTION 0
     66 #define DEBUG_PERP 0
     67 #define DEBUG_SHOW_TEST_NAME 0
     68 #define DEBUG_SORT 0
     69 #define DEBUG_T_SECT 0
     70 #define DEBUG_T_SECT_DUMP 0
     71 #define DEBUG_T_SECT_LOOP_COUNT 0
     72 #define DEBUG_VALIDATE 0
     73 #define DEBUG_WINDING 0
     74 #define DEBUG_WINDING_AT_T 0
     75 
     76 #else
     77 
     78 #define DEBUG_ACTIVE_OP 1
     79 #define DEBUG_ACTIVE_SPANS 1
     80 #define DEBUG_ADD_INTERSECTING_TS 1
     81 #define DEBUG_ADD_T 1
     82 #define DEBUG_ALIGNMENT 0
     83 #define DEBUG_ANGLE 1
     84 #define DEBUG_ASSEMBLE 1
     85 #define DEBUG_COINCIDENCE 1
     86 #define DEBUG_COINCIDENCE_DUMP 0
     87 #define DEBUG_COINCIDENCE_ORDER 0  // tight arc quads may generate out-of-order coincdence spans
     88 #define DEBUG_COINCIDENCE_VERBOSE 1
     89 #define DEBUG_CUBIC_BINARY_SEARCH 0
     90 #define DEBUG_CUBIC_SPLIT 1
     91 #define DEBUG_DUMP_VERIFY 0
     92 #define DEBUG_DUMP_SEGMENTS 1
     93 #define DEBUG_FLOW 1
     94 #define DEBUG_LIMIT_WIND_SUM 15
     95 #define DEBUG_MARK_DONE 1
     96 #define DEBUG_PATH_CONSTRUCTION 1
     97 #define DEBUG_PERP 1
     98 #define DEBUG_SHOW_TEST_NAME 1
     99 #define DEBUG_SORT 1
    100 #define DEBUG_T_SECT 0
    101 #define DEBUG_T_SECT_DUMP 0  // Use 1 normally. Use 2 to number segments, 3 for script output
    102 #define DEBUG_T_SECT_LOOP_COUNT 0
    103 #define DEBUG_VALIDATE 1
    104 #define DEBUG_WINDING 1
    105 #define DEBUG_WINDING_AT_T 1
    106 
    107 #endif
    108 
    109 #ifdef SK_RELEASE
    110     #define SkDEBUGRELEASE(a, b) b
    111     #define SkDEBUGPARAMS(...)
    112 #else
    113     #define SkDEBUGRELEASE(a, b) a
    114     #define SkDEBUGPARAMS(...) , __VA_ARGS__
    115 #endif
    116 
    117 #if DEBUG_VALIDATE == 0
    118     #define PATH_OPS_DEBUG_VALIDATE_PARAMS(...)
    119 #else
    120     #define PATH_OPS_DEBUG_VALIDATE_PARAMS(...) , __VA_ARGS__
    121 #endif
    122 
    123 #if DEBUG_T_SECT == 0
    124     #define PATH_OPS_DEBUG_T_SECT_RELEASE(a, b) b
    125     #define PATH_OPS_DEBUG_T_SECT_PARAMS(...)
    126     #define PATH_OPS_DEBUG_T_SECT_CODE(...)
    127 #else
    128     #define PATH_OPS_DEBUG_T_SECT_RELEASE(a, b) a
    129     #define PATH_OPS_DEBUG_T_SECT_PARAMS(...) , __VA_ARGS__
    130     #define PATH_OPS_DEBUG_T_SECT_CODE(...) __VA_ARGS__
    131 #endif
    132 
    133 #if DEBUG_T_SECT_DUMP > 1
    134     extern int gDumpTSectNum;
    135 #endif
    136 
    137 #if DEBUG_COINCIDENCE || DEBUG_COINCIDENCE_DUMP
    138     #define DEBUG_COIN 1
    139 #else
    140     #define DEBUG_COIN 0
    141 #endif
    142 
    143 #if DEBUG_COIN
    144     #define DEBUG_COIN_DECLARE_ONLY_PARAMS() \
    145             int lineNo, SkOpPhase phase, int iteration
    146     #define DEBUG_COIN_DECLARE_PARAMS() \
    147             , DEBUG_COIN_DECLARE_ONLY_PARAMS()
    148     #define DEBUG_COIN_ONLY_PARAMS() \
    149             __LINE__, SkOpPhase::kNoChange, 0
    150     #define DEBUG_COIN_PARAMS() \
    151             , DEBUG_COIN_ONLY_PARAMS()
    152     #define DEBUG_ITER_ONLY_PARAMS(iteration) \
    153             __LINE__, SkOpPhase::kNoChange, iteration
    154     #define DEBUG_ITER_PARAMS(iteration) \
    155             , DEBUG_ITER_ONLY_PARAMS(iteration)
    156     #define DEBUG_PHASE_ONLY_PARAMS(phase) \
    157             __LINE__, SkOpPhase::phase, 0
    158     #define DEBUG_PHASE_PARAMS(phase) \
    159             , DEBUG_PHASE_ONLY_PARAMS(phase)
    160     #define DEBUG_SET_PHASE() \
    161             this->globalState()->debugSetPhase(__func__, lineNo, phase, iteration)
    162     #define DEBUG_STATIC_SET_PHASE(obj) \
    163             obj->globalState()->debugSetPhase(__func__, lineNo, phase, iteration)
    164 #elif DEBUG_VALIDATE
    165     #define DEBUG_COIN_DECLARE_ONLY_PARAMS() \
    166             SkOpPhase phase
    167     #define DEBUG_COIN_DECLARE_PARAMS() \
    168             , DEBUG_COIN_DECLARE_ONLY_PARAMS()
    169     #define DEBUG_COIN_ONLY_PARAMS() \
    170             SkOpPhase::kNoChange
    171     #define DEBUG_COIN_PARAMS() \
    172             , DEBUG_COIN_ONLY_PARAMS()
    173     #define DEBUG_ITER_ONLY_PARAMS(iteration) \
    174             SkOpPhase::kNoChange
    175     #define DEBUG_ITER_PARAMS(iteration) \
    176             , DEBUG_ITER_ONLY_PARAMS(iteration)
    177     #define DEBUG_PHASE_ONLY_PARAMS(phase) \
    178             SkOpPhase::phase
    179     #define DEBUG_PHASE_PARAMS(phase) \
    180             , DEBUG_PHASE_ONLY_PARAMS(phase)
    181     #define DEBUG_SET_PHASE() \
    182             this->globalState()->debugSetPhase(phase)
    183     #define DEBUG_STATIC_SET_PHASE(obj) \
    184             obj->globalState()->debugSetPhase(phase)
    185 #else
    186     #define DEBUG_COIN_DECLARE_ONLY_PARAMS()
    187     #define DEBUG_COIN_DECLARE_PARAMS()
    188     #define DEBUG_COIN_ONLY_PARAMS()
    189     #define DEBUG_COIN_PARAMS()
    190     #define DEBUG_ITER_ONLY_PARAMS(iteration)
    191     #define DEBUG_ITER_PARAMS(iteration)
    192     #define DEBUG_PHASE_ONLY_PARAMS(phase)
    193     #define DEBUG_PHASE_PARAMS(phase)
    194     #define DEBUG_SET_PHASE()
    195     #define DEBUG_STATIC_SET_PHASE(obj)
    196 #endif
    197 
    198 #define CUBIC_DEBUG_STR  "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
    199 #define CONIC_DEBUG_STR "{{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}, %1.9g}"
    200 #define QUAD_DEBUG_STR   "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
    201 #define LINE_DEBUG_STR   "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
    202 #define PT_DEBUG_STR "{{%1.9g,%1.9g}}"
    203 
    204 #define T_DEBUG_STR(t, n) #t "[" #n "]=%1.9g"
    205 #define TX_DEBUG_STR(t) #t "[%d]=%1.9g"
    206 #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
    207 #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
    208 #define QUAD_DEBUG_DATA(q)  q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY
    209 #define LINE_DEBUG_DATA(l)  l[0].fX, l[0].fY, l[1].fX, l[1].fY
    210 #define PT_DEBUG_DATA(i, n) i.pt(n).asSkPoint().fX, i.pt(n).asSkPoint().fY
    211 
    212 #ifndef DEBUG_TEST
    213 #define DEBUG_TEST 0
    214 #endif
    215 
    216 #if DEBUG_SHOW_TEST_NAME
    217 #include "SkTLS.h"
    218 #endif
    219 
    220 // Tests with extreme numbers may fail, but all other tests should never fail.
    221 #define FAIL_IF(cond) \
    222         do { bool fail = (cond); SkOPASSERT(!fail); if (fail) return false; } while (false)
    223 
    224 #define FAIL_WITH_NULL_IF(cond) \
    225         do { bool fail = (cond); SkOPASSERT(!fail); if (fail) return nullptr; } while (false)
    226 
    227 // Some functions serve two masters: one allows the function to fail, the other expects success
    228 // always. If abort is true, tests with normal numbers may not fail and assert if they do so.
    229 // If abort is false, both normal and extreme numbers may return false without asserting.
    230 #define RETURN_FALSE_IF(abort, cond) \
    231         do { bool fail = (cond); SkOPASSERT(!(abort) || !fail); if (fail) return false; \
    232         } while (false)
    233 
    234 class SkPathOpsDebug {
    235 public:
    236     static const char* kLVerbStr[];
    237 
    238 #if DEBUG_COIN
    239     struct GlitchLog;
    240 
    241     enum GlitchType {
    242         kUninitialized_Glitch,
    243         kAddCorruptCoin_Glitch,
    244         kAddExpandedCoin_Glitch,
    245         kAddExpandedFail_Glitch,
    246         kAddIfCollapsed_Glitch,
    247         kAddIfMissingCoin_Glitch,
    248         kAddMissingCoin_Glitch,
    249         kAddMissingExtend_Glitch,
    250         kAddOrOverlap_Glitch,
    251         kCollapsedCoin_Glitch,
    252         kCollapsedDone_Glitch,
    253         kCollapsedOppValue_Glitch,
    254         kCollapsedSpan_Glitch,
    255         kCollapsedWindValue_Glitch,
    256         kCorrectEnd_Glitch,
    257         kDeletedCoin_Glitch,
    258         kExpandCoin_Glitch,
    259         kFail_Glitch,
    260         kMarkCoinEnd_Glitch,
    261         kMarkCoinInsert_Glitch,
    262         kMarkCoinMissing_Glitch,
    263         kMarkCoinStart_Glitch,
    264         kMergeMatches_Glitch,
    265         kMissingCoin_Glitch,
    266         kMissingDone_Glitch,
    267         kMissingIntersection_Glitch,
    268         kMoveMultiple_Glitch,
    269         kMoveNearbyClearAll_Glitch,
    270         kMoveNearbyClearAll2_Glitch,
    271         kMoveNearbyMerge_Glitch,
    272         kMoveNearbyMergeFinal_Glitch,
    273         kMoveNearbyRelease_Glitch,
    274         kMoveNearbyReleaseFinal_Glitch,
    275         kReleasedSpan_Glitch,
    276         kReturnFalse_Glitch,
    277         kUnaligned_Glitch,
    278         kUnalignedHead_Glitch,
    279         kUnalignedTail_Glitch,
    280     };
    281 
    282     struct CoinDictEntry {
    283         int fIteration;
    284         int fLineNumber;
    285         GlitchType fGlitchType;
    286         const char* fFunctionName;
    287     };
    288 
    289     struct CoinDict {
    290         void add(const CoinDictEntry& key);
    291         void add(const CoinDict& dict);
    292         void dump(const char* str, bool visitCheck) const;
    293         SkTDArray<CoinDictEntry> fDict;
    294     };
    295 
    296     static CoinDict gCoinSumChangedDict;
    297     static CoinDict gCoinSumVisitedDict;
    298     static CoinDict gCoinVistedDict;
    299 #endif
    300 
    301 #if defined(SK_DEBUG) || !FORCE_RELEASE
    302     static int gContourID;
    303     static int gSegmentID;
    304 #endif
    305 
    306 #if DEBUG_SORT
    307     static int gSortCountDefault;
    308     static int gSortCount;
    309 #endif
    310 
    311 #if DEBUG_ACTIVE_OP
    312     static const char* kPathOpStr[];
    313 #endif
    314 
    315     static void MathematicaIze(char* str, size_t bufferSize);
    316     static bool ValidWind(int winding);
    317     static void WindingPrintf(int winding);
    318 
    319 #if DEBUG_SHOW_TEST_NAME
    320     static void* CreateNameStr();
    321     static void DeleteNameStr(void* v);
    322 #define DEBUG_FILENAME_STRING_LENGTH 64
    323 #define DEBUG_FILENAME_STRING (reinterpret_cast<char* >(SkTLS::Get(SkPathOpsDebug::CreateNameStr, \
    324         SkPathOpsDebug::DeleteNameStr)))
    325     static void BumpTestName(char* );
    326 #endif
    327     static const char* OpStr(SkPathOp );
    328     static void ShowActiveSpans(SkOpContourHead* contourList);
    329     static void ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration);
    330     static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name);
    331 
    332     static bool ChaseContains(const SkTDArray<class SkOpSpanBase*>& , const class SkOpSpanBase* );
    333 
    334     static void CheckHealth(class SkOpContourHead* contourList);
    335 
    336     static const class SkOpAngle* DebugAngleAngle(const class SkOpAngle*, int id);
    337     static class SkOpContour* DebugAngleContour(class SkOpAngle*, int id);
    338     static const class SkOpPtT* DebugAnglePtT(const class SkOpAngle*, int id);
    339     static const class SkOpSegment* DebugAngleSegment(const class SkOpAngle*, int id);
    340     static const class SkOpSpanBase* DebugAngleSpan(const class SkOpAngle*, int id);
    341 
    342     static const class SkOpAngle* DebugContourAngle(class SkOpContour*, int id);
    343     static class SkOpContour* DebugContourContour(class SkOpContour*, int id);
    344     static const class SkOpPtT* DebugContourPtT(class SkOpContour*, int id);
    345     static const class SkOpSegment* DebugContourSegment(class SkOpContour*, int id);
    346     static const class SkOpSpanBase* DebugContourSpan(class SkOpContour*, int id);
    347 
    348     static const class SkOpAngle* DebugCoincidenceAngle(class SkOpCoincidence*, int id);
    349     static class SkOpContour* DebugCoincidenceContour(class SkOpCoincidence*, int id);
    350     static const class SkOpPtT* DebugCoincidencePtT(class SkOpCoincidence*, int id);
    351     static const class SkOpSegment* DebugCoincidenceSegment(class SkOpCoincidence*, int id);
    352     static const class SkOpSpanBase* DebugCoincidenceSpan(class SkOpCoincidence*, int id);
    353 
    354     static const class SkOpAngle* DebugPtTAngle(const class SkOpPtT*, int id);
    355     static class SkOpContour* DebugPtTContour(class SkOpPtT*, int id);
    356     static const class SkOpPtT* DebugPtTPtT(const class SkOpPtT*, int id);
    357     static const class SkOpSegment* DebugPtTSegment(const class SkOpPtT*, int id);
    358     static const class SkOpSpanBase* DebugPtTSpan(const class SkOpPtT*, int id);
    359 
    360     static const class SkOpAngle* DebugSegmentAngle(const class SkOpSegment*, int id);
    361     static class SkOpContour* DebugSegmentContour(class SkOpSegment*, int id);
    362     static const class SkOpPtT* DebugSegmentPtT(const class SkOpSegment*, int id);
    363     static const class SkOpSegment* DebugSegmentSegment(const class SkOpSegment*, int id);
    364     static const class SkOpSpanBase* DebugSegmentSpan(const class SkOpSegment*, int id);
    365 
    366     static const class SkOpAngle* DebugSpanAngle(const class SkOpSpanBase*, int id);
    367     static class SkOpContour* DebugSpanContour(class SkOpSpanBase*, int id);
    368     static const class SkOpPtT* DebugSpanPtT(const class SkOpSpanBase*, int id);
    369     static const class SkOpSegment* DebugSpanSegment(const class SkOpSpanBase*, int id);
    370     static const class SkOpSpanBase* DebugSpanSpan(const class SkOpSpanBase*, int id);
    371 
    372 #if DEBUG_COIN
    373     static void DumpCoinDict();
    374     static void DumpGlitchType(GlitchType );
    375 #endif
    376 
    377     static bool gRunFail;
    378     static bool gVeryVerbose;
    379 
    380 #if DEBUG_DUMP_VERIFY
    381     static bool gDumpOp;
    382     static bool gVerifyOp;
    383 
    384     static void DumpOp(const SkPath& one, const SkPath& two, SkPathOp op,
    385             const char* testName);
    386     static void DumpOp(FILE* file, const SkPath& one, const SkPath& two, SkPathOp op,
    387             const char* testName);
    388     static void DumpSimplify(const SkPath& path, const char* testName);
    389     static void DumpSimplify(FILE* file, const SkPath& path, const char* testName);
    390     static void ReportOpFail(const SkPath& one, const SkPath& two, SkPathOp op);
    391     static void ReportSimplifyFail(const SkPath& path);
    392     static void VerifyOp(const SkPath& one, const SkPath& two, SkPathOp op,
    393         const SkPath& result);
    394     static void VerifySimplify(const SkPath& path, const SkPath& result);
    395 #endif
    396 
    397 #if DEBUG_ACTIVE_SPANS
    398     static SkString gActiveSpans;
    399 #endif
    400 
    401 };
    402 
    403 struct SkDQuad;
    404 
    405 // generates tools/path_sorter.htm and path_visualizer.htm compatible data
    406 void DumpQ(const SkDQuad& quad1, const SkDQuad& quad2, int testNo);
    407 void DumpT(const SkDQuad& quad, double t);
    408 
    409 #endif
    410