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
8 #include "src/pathops/SkPathOpsDebug.h"
9
10 #include "include/core/SkPath.h"
11 #include "include/core/SkPathTypes.h"
12 #include "include/core/SkPoint.h"
13 #include "include/core/SkScalar.h"
14 #include "include/core/SkString.h"
15 #include "include/private/base/SkDebug.h"
16 #include "include/private/base/SkMath.h"
17 #include "include/private/base/SkMutex.h"
18 #include "src/core/SkPathPriv.h"
19 #include "src/pathops/SkIntersections.h"
20 #include "src/pathops/SkOpAngle.h"
21 #include "src/pathops/SkOpCoincidence.h"
22 #include "src/pathops/SkOpSegment.h"
23 #include "src/pathops/SkOpSpan.h"
24 #include "src/pathops/SkPathOpsConic.h"
25 #include "src/pathops/SkPathOpsCubic.h"
26 #include "src/pathops/SkPathOpsPoint.h"
27 #include "src/pathops/SkPathOpsQuad.h"
28 #include "src/pathops/SkPathOpsRect.h"
29 #include "src/pathops/SkPathOpsTypes.h"
30
31 #include <cstdint>
32 #include <cstring>
33
34 #if DEBUG_DUMP_VERIFY
35 bool SkPathOpsDebug::gDumpOp; // set to true to write op to file before a crash
36 bool SkPathOpsDebug::gVerifyOp; // set to true to compare result against regions
37 #endif
38
39 bool SkPathOpsDebug::gRunFail; // set to true to check for success on tests known to fail
40 bool SkPathOpsDebug::gVeryVerbose; // set to true to run extensive checking tests
41
42 #define FAIL_IF_COIN(cond, coin) \
43 do { if (cond) log->record(SkPathOpsDebug::kFail_Glitch, coin); } while (false)
44
45 #undef FAIL_WITH_NULL_IF
46 #define FAIL_WITH_NULL_IF(cond, span) \
47 do { if (cond) log->record(SkPathOpsDebug::kFail_Glitch, span); } while (false)
48
49 #define RETURN_FALSE_IF(cond, span) \
50 do { if (cond) log->record(SkPathOpsDebug::kReturnFalse_Glitch, span); \
51 } while (false)
52
53 #if DEBUG_SORT
54 int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
55 int SkPathOpsDebug::gSortCount;
56 #endif
57
58 #if DEBUG_ACTIVE_OP
59 const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor", "rdiff"};
60 #endif
61
62 #if defined SK_DEBUG || !FORCE_RELEASE
63
64 int SkPathOpsDebug::gContourID = 0;
65 int SkPathOpsDebug::gSegmentID = 0;
66
ChaseContains(const SkTDArray<SkOpSpanBase * > & chaseArray,const SkOpSpanBase * span)67 bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase*>& chaseArray,
68 const SkOpSpanBase* span) {
69 for (int index = 0; index < chaseArray.size(); ++index) {
70 const SkOpSpanBase* entry = chaseArray[index];
71 if (entry == span) {
72 return true;
73 }
74 }
75 return false;
76 }
77 #endif
78
79 #if DEBUG_ACTIVE_SPANS
80 SkString SkPathOpsDebug::gActiveSpans;
81 #endif
82
83 #if DEBUG_COIN
84
85 #include "src/pathops/SkOpContour.h"
86
87 class SkCoincidentSpans;
88
89 SkPathOpsDebug::CoinDict SkPathOpsDebug::gCoinSumChangedDict;
90 SkPathOpsDebug::CoinDict SkPathOpsDebug::gCoinSumVisitedDict;
91
92 static const int kGlitchType_Count = SkPathOpsDebug::kUnalignedTail_Glitch + 1;
93
94 struct SpanGlitch {
95 const SkOpSpanBase* fBase;
96 const SkOpSpanBase* fSuspect;
97 const SkOpSegment* fSegment;
98 const SkOpSegment* fOppSegment;
99 const SkOpPtT* fCoinSpan;
100 const SkOpPtT* fEndSpan;
101 const SkOpPtT* fOppSpan;
102 const SkOpPtT* fOppEndSpan;
103 double fStartT;
104 double fEndT;
105 double fOppStartT;
106 double fOppEndT;
107 SkPoint fPt;
108 SkPathOpsDebug::GlitchType fType;
109
110 void dumpType() const;
111 };
112
113 struct SkPathOpsDebug::GlitchLog {
initSkPathOpsDebug::GlitchLog114 void init(const SkOpGlobalState* state) {
115 fGlobalState = state;
116 }
117
recordCommonSkPathOpsDebug::GlitchLog118 SpanGlitch* recordCommon(GlitchType type) {
119 SpanGlitch* glitch = fGlitches.append();
120 glitch->fBase = nullptr;
121 glitch->fSuspect = nullptr;
122 glitch->fSegment = nullptr;
123 glitch->fOppSegment = nullptr;
124 glitch->fCoinSpan = nullptr;
125 glitch->fEndSpan = nullptr;
126 glitch->fOppSpan = nullptr;
127 glitch->fOppEndSpan = nullptr;
128 glitch->fStartT = SK_ScalarNaN;
129 glitch->fEndT = SK_ScalarNaN;
130 glitch->fOppStartT = SK_ScalarNaN;
131 glitch->fOppEndT = SK_ScalarNaN;
132 glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN };
133 glitch->fType = type;
134 return glitch;
135 }
136
recordSkPathOpsDebug::GlitchLog137 void record(GlitchType type, const SkOpSpanBase* base, const SkOpSpanBase* suspect = nullptr) {
138 SpanGlitch* glitch = recordCommon(type);
139 glitch->fBase = base;
140 glitch->fSuspect = suspect;
141 }
142
recordSkPathOpsDebug::GlitchLog143 void record(GlitchType type, const SkOpSpanBase* base, const SkOpPtT* ptT) {
144 SpanGlitch* glitch = recordCommon(type);
145 glitch->fBase = base;
146 glitch->fCoinSpan = ptT;
147 }
148
recordSkPathOpsDebug::GlitchLog149 void record(GlitchType type,
150 const SkCoincidentSpans* coin,
151 const SkCoincidentSpans* opp = nullptr) {
152 SpanGlitch* glitch = recordCommon(type);
153 glitch->fCoinSpan = coin->coinPtTStart();
154 glitch->fEndSpan = coin->coinPtTEnd();
155 if (opp) {
156 glitch->fOppSpan = opp->coinPtTStart();
157 glitch->fOppEndSpan = opp->coinPtTEnd();
158 }
159 }
160
recordSkPathOpsDebug::GlitchLog161 void record(GlitchType type, const SkOpSpanBase* base,
162 const SkOpSegment* seg, double t, SkPoint pt) {
163 SpanGlitch* glitch = recordCommon(type);
164 glitch->fBase = base;
165 glitch->fSegment = seg;
166 glitch->fStartT = t;
167 glitch->fPt = pt;
168 }
169
recordSkPathOpsDebug::GlitchLog170 void record(GlitchType type, const SkOpSpanBase* base, double t,
171 SkPoint pt) {
172 SpanGlitch* glitch = recordCommon(type);
173 glitch->fBase = base;
174 glitch->fStartT = t;
175 glitch->fPt = pt;
176 }
177
recordSkPathOpsDebug::GlitchLog178 void record(GlitchType type, const SkCoincidentSpans* coin,
179 const SkOpPtT* coinSpan, const SkOpPtT* endSpan) {
180 SpanGlitch* glitch = recordCommon(type);
181 glitch->fCoinSpan = coin->coinPtTStart();
182 glitch->fEndSpan = coin->coinPtTEnd();
183 glitch->fEndSpan = endSpan;
184 glitch->fOppSpan = coinSpan;
185 glitch->fOppEndSpan = endSpan;
186 }
187
recordSkPathOpsDebug::GlitchLog188 void record(GlitchType type, const SkCoincidentSpans* coin,
189 const SkOpSpanBase* base) {
190 SpanGlitch* glitch = recordCommon(type);
191 glitch->fBase = base;
192 glitch->fCoinSpan = coin->coinPtTStart();
193 glitch->fEndSpan = coin->coinPtTEnd();
194 }
195
recordSkPathOpsDebug::GlitchLog196 void record(GlitchType type, const SkOpPtT* ptTS, const SkOpPtT* ptTE,
197 const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) {
198 SpanGlitch* glitch = recordCommon(type);
199 glitch->fCoinSpan = ptTS;
200 glitch->fEndSpan = ptTE;
201 glitch->fOppSpan = oPtTS;
202 glitch->fOppEndSpan = oPtTE;
203 }
204
recordSkPathOpsDebug::GlitchLog205 void record(GlitchType type, const SkOpSegment* seg, double startT,
206 double endT, const SkOpSegment* oppSeg, double oppStartT, double oppEndT) {
207 SpanGlitch* glitch = recordCommon(type);
208 glitch->fSegment = seg;
209 glitch->fStartT = startT;
210 glitch->fEndT = endT;
211 glitch->fOppSegment = oppSeg;
212 glitch->fOppStartT = oppStartT;
213 glitch->fOppEndT = oppEndT;
214 }
215
recordSkPathOpsDebug::GlitchLog216 void record(GlitchType type, const SkOpSegment* seg,
217 const SkOpSpan* span) {
218 SpanGlitch* glitch = recordCommon(type);
219 glitch->fSegment = seg;
220 glitch->fBase = span;
221 }
222
recordSkPathOpsDebug::GlitchLog223 void record(GlitchType type, double t, const SkOpSpanBase* span) {
224 SpanGlitch* glitch = recordCommon(type);
225 glitch->fStartT = t;
226 glitch->fBase = span;
227 }
228
recordSkPathOpsDebug::GlitchLog229 void record(GlitchType type, const SkOpSegment* seg) {
230 SpanGlitch* glitch = recordCommon(type);
231 glitch->fSegment = seg;
232 }
233
recordSkPathOpsDebug::GlitchLog234 void record(GlitchType type, const SkCoincidentSpans* coin,
235 const SkOpPtT* ptT) {
236 SpanGlitch* glitch = recordCommon(type);
237 glitch->fCoinSpan = coin->coinPtTStart();
238 glitch->fEndSpan = ptT;
239 }
240
241 SkTDArray<SpanGlitch> fGlitches;
242 const SkOpGlobalState* fGlobalState;
243 };
244
245
add(const SkPathOpsDebug::CoinDict & dict)246 void SkPathOpsDebug::CoinDict::add(const SkPathOpsDebug::CoinDict& dict) {
247 int count = dict.fDict.size();
248 for (int index = 0; index < count; ++index) {
249 this->add(dict.fDict[index]);
250 }
251 }
252
add(const CoinDictEntry & key)253 void SkPathOpsDebug::CoinDict::add(const CoinDictEntry& key) {
254 int count = fDict.size();
255 for (int index = 0; index < count; ++index) {
256 CoinDictEntry* entry = &fDict[index];
257 if (entry->fIteration == key.fIteration && entry->fLineNumber == key.fLineNumber) {
258 SkASSERT(!strcmp(entry->fFunctionName, key.fFunctionName));
259 if (entry->fGlitchType == kUninitialized_Glitch) {
260 entry->fGlitchType = key.fGlitchType;
261 }
262 return;
263 }
264 }
265 *fDict.append() = key;
266 }
267
268 #endif
269
270 #if DEBUG_COIN
missing_coincidence(SkPathOpsDebug::GlitchLog * glitches,const SkOpContourHead * contourList)271 static void missing_coincidence(SkPathOpsDebug::GlitchLog* glitches,
272 const SkOpContourHead* contourList) {
273 const SkOpContour* contour = contourList;
274 // bool result = false;
275 do {
276 /* result |= */ contour->debugMissingCoincidence(glitches);
277 } while ((contour = contour->next()));
278 return;
279 }
280
move_multiples(SkPathOpsDebug::GlitchLog * glitches,const SkOpContourHead * contourList)281 static void move_multiples(SkPathOpsDebug::GlitchLog* glitches,
282 const SkOpContourHead* contourList) {
283 const SkOpContour* contour = contourList;
284 do {
285 contour->debugMoveMultiples(glitches);
286 } while ((contour = contour->next()));
287 return;
288 }
289
move_nearby(SkPathOpsDebug::GlitchLog * glitches,const SkOpContourHead * contourList)290 static void move_nearby(SkPathOpsDebug::GlitchLog* glitches, const SkOpContourHead* contourList) {
291 const SkOpContour* contour = contourList;
292 do {
293 contour->debugMoveNearby(glitches);
294 } while ((contour = contour->next()));
295 }
296
297 #endif
298
299 #if DEBUG_COIN
debugAddToCoinChangedDict()300 void SkOpGlobalState::debugAddToCoinChangedDict() {
301
302 #if DEBUG_COINCIDENCE
303 SkPathOpsDebug::CheckHealth(fContourHead);
304 #endif
305 // see if next coincident operation makes a change; if so, record it
306 SkPathOpsDebug::GlitchLog glitches;
307 const char* funcName = fCoinDictEntry.fFunctionName;
308 if (!strcmp("calc_angles", funcName)) {
309 //
310 } else if (!strcmp("missing_coincidence", funcName)) {
311 missing_coincidence(&glitches, fContourHead);
312 } else if (!strcmp("move_multiples", funcName)) {
313 move_multiples(&glitches, fContourHead);
314 } else if (!strcmp("move_nearby", funcName)) {
315 move_nearby(&glitches, fContourHead);
316 } else if (!strcmp("addExpanded", funcName)) {
317 fCoincidence->debugAddExpanded(&glitches);
318 } else if (!strcmp("addMissing", funcName)) {
319 bool added;
320 fCoincidence->debugAddMissing(&glitches, &added);
321 } else if (!strcmp("addEndMovedSpans", funcName)) {
322 fCoincidence->debugAddEndMovedSpans(&glitches);
323 } else if (!strcmp("correctEnds", funcName)) {
324 fCoincidence->debugCorrectEnds(&glitches);
325 } else if (!strcmp("expand", funcName)) {
326 fCoincidence->debugExpand(&glitches);
327 } else if (!strcmp("findOverlaps", funcName)) {
328 //
329 } else if (!strcmp("mark", funcName)) {
330 fCoincidence->debugMark(&glitches);
331 } else if (!strcmp("apply", funcName)) {
332 //
333 } else {
334 SkASSERT(0); // add missing case
335 }
336 if (glitches.fGlitches.size()) {
337 fCoinDictEntry.fGlitchType = glitches.fGlitches[0].fType;
338 }
339 fCoinChangedDict.add(fCoinDictEntry);
340 }
341 #endif
342
ShowActiveSpans(SkOpContourHead * contourList)343 void SkPathOpsDebug::ShowActiveSpans(SkOpContourHead* contourList) {
344 #if DEBUG_ACTIVE_SPANS
345 SkString str;
346 SkOpContour* contour = contourList;
347 do {
348 contour->debugShowActiveSpans(&str);
349 } while ((contour = contour->next()));
350 if (!gActiveSpans.equals(str)) {
351 const char* s = str.c_str();
352 const char* end;
353 while ((end = strchr(s, '\n'))) {
354 SkDebugf("%.*s", (int) (end - s + 1), s);
355 s = end + 1;
356 }
357 gActiveSpans.set(str);
358 }
359 #endif
360 }
361
362 #if DEBUG_COINCIDENCE || DEBUG_COIN
CheckHealth(SkOpContourHead * contourList)363 void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList) {
364 #if DEBUG_COINCIDENCE
365 contourList->globalState()->debugSetCheckHealth(true);
366 #endif
367 #if DEBUG_COIN
368 GlitchLog glitches;
369 const SkOpContour* contour = contourList;
370 const SkOpCoincidence* coincidence = contour->globalState()->coincidence();
371 coincidence->debugCheckValid(&glitches); // don't call validate; spans may be inconsistent
372 do {
373 contour->debugCheckHealth(&glitches);
374 contour->debugMissingCoincidence(&glitches);
375 } while ((contour = contour->next()));
376 bool added;
377 coincidence->debugAddMissing(&glitches, &added);
378 coincidence->debugExpand(&glitches);
379 coincidence->debugAddExpanded(&glitches);
380 coincidence->debugMark(&glitches);
381 unsigned mask = 0;
382 for (int index = 0; index < glitches.fGlitches.size(); ++index) {
383 const SpanGlitch& glitch = glitches.fGlitches[index];
384 mask |= 1 << glitch.fType;
385 }
386 for (int index = 0; index < kGlitchType_Count; ++index) {
387 SkDebugf(mask & (1 << index) ? "x" : "-");
388 }
389 SkDebugf(" %s\n", contourList->globalState()->debugCoinDictEntry().fFunctionName);
390 for (int index = 0; index < glitches.fGlitches.size(); ++index) {
391 const SpanGlitch& glitch = glitches.fGlitches[index];
392 SkDebugf("%02d: ", index);
393 if (glitch.fBase) {
394 SkDebugf(" seg/base=%d/%d", glitch.fBase->segment()->debugID(),
395 glitch.fBase->debugID());
396 }
397 if (glitch.fSuspect) {
398 SkDebugf(" seg/base=%d/%d", glitch.fSuspect->segment()->debugID(),
399 glitch.fSuspect->debugID());
400 }
401 if (glitch.fSegment) {
402 SkDebugf(" segment=%d", glitch.fSegment->debugID());
403 }
404 if (glitch.fCoinSpan) {
405 SkDebugf(" coinSeg/Span/PtT=%d/%d/%d", glitch.fCoinSpan->segment()->debugID(),
406 glitch.fCoinSpan->span()->debugID(), glitch.fCoinSpan->debugID());
407 }
408 if (glitch.fEndSpan) {
409 SkDebugf(" endSpan=%d", glitch.fEndSpan->debugID());
410 }
411 if (glitch.fOppSpan) {
412 SkDebugf(" oppSeg/Span/PtT=%d/%d/%d", glitch.fOppSpan->segment()->debugID(),
413 glitch.fOppSpan->span()->debugID(), glitch.fOppSpan->debugID());
414 }
415 if (glitch.fOppEndSpan) {
416 SkDebugf(" oppEndSpan=%d", glitch.fOppEndSpan->debugID());
417 }
418 if (!SkIsNaN(glitch.fStartT)) {
419 SkDebugf(" startT=%g", glitch.fStartT);
420 }
421 if (!SkIsNaN(glitch.fEndT)) {
422 SkDebugf(" endT=%g", glitch.fEndT);
423 }
424 if (glitch.fOppSegment) {
425 SkDebugf(" segment=%d", glitch.fOppSegment->debugID());
426 }
427 if (!SkIsNaN(glitch.fOppStartT)) {
428 SkDebugf(" oppStartT=%g", glitch.fOppStartT);
429 }
430 if (!SkIsNaN(glitch.fOppEndT)) {
431 SkDebugf(" oppEndT=%g", glitch.fOppEndT);
432 }
433 if (!SkIsNaN(glitch.fPt.fX) || !SkIsNaN(glitch.fPt.fY)) {
434 SkDebugf(" pt=%g,%g", glitch.fPt.fX, glitch.fPt.fY);
435 }
436 DumpGlitchType(glitch.fType);
437 SkDebugf("\n");
438 }
439 #if DEBUG_COINCIDENCE
440 contourList->globalState()->debugSetCheckHealth(false);
441 #endif
442 #if 01 && DEBUG_ACTIVE_SPANS
443 // SkDebugf("active after %s:\n", id);
444 ShowActiveSpans(contourList);
445 #endif
446 #endif
447 }
448 #endif
449
450 #if DEBUG_COIN
DumpGlitchType(GlitchType glitchType)451 void SkPathOpsDebug::DumpGlitchType(GlitchType glitchType) {
452 switch (glitchType) {
453 case kAddCorruptCoin_Glitch: SkDebugf(" AddCorruptCoin"); break;
454 case kAddExpandedCoin_Glitch: SkDebugf(" AddExpandedCoin"); break;
455 case kAddExpandedFail_Glitch: SkDebugf(" AddExpandedFail"); break;
456 case kAddIfCollapsed_Glitch: SkDebugf(" AddIfCollapsed"); break;
457 case kAddIfMissingCoin_Glitch: SkDebugf(" AddIfMissingCoin"); break;
458 case kAddMissingCoin_Glitch: SkDebugf(" AddMissingCoin"); break;
459 case kAddMissingExtend_Glitch: SkDebugf(" AddMissingExtend"); break;
460 case kAddOrOverlap_Glitch: SkDebugf(" AAddOrOverlap"); break;
461 case kCollapsedCoin_Glitch: SkDebugf(" CollapsedCoin"); break;
462 case kCollapsedDone_Glitch: SkDebugf(" CollapsedDone"); break;
463 case kCollapsedOppValue_Glitch: SkDebugf(" CollapsedOppValue"); break;
464 case kCollapsedSpan_Glitch: SkDebugf(" CollapsedSpan"); break;
465 case kCollapsedWindValue_Glitch: SkDebugf(" CollapsedWindValue"); break;
466 case kCorrectEnd_Glitch: SkDebugf(" CorrectEnd"); break;
467 case kDeletedCoin_Glitch: SkDebugf(" DeletedCoin"); break;
468 case kExpandCoin_Glitch: SkDebugf(" ExpandCoin"); break;
469 case kFail_Glitch: SkDebugf(" Fail"); break;
470 case kMarkCoinEnd_Glitch: SkDebugf(" MarkCoinEnd"); break;
471 case kMarkCoinInsert_Glitch: SkDebugf(" MarkCoinInsert"); break;
472 case kMarkCoinMissing_Glitch: SkDebugf(" MarkCoinMissing"); break;
473 case kMarkCoinStart_Glitch: SkDebugf(" MarkCoinStart"); break;
474 case kMergeMatches_Glitch: SkDebugf(" MergeMatches"); break;
475 case kMissingCoin_Glitch: SkDebugf(" MissingCoin"); break;
476 case kMissingDone_Glitch: SkDebugf(" MissingDone"); break;
477 case kMissingIntersection_Glitch: SkDebugf(" MissingIntersection"); break;
478 case kMoveMultiple_Glitch: SkDebugf(" MoveMultiple"); break;
479 case kMoveNearbyClearAll_Glitch: SkDebugf(" MoveNearbyClearAll"); break;
480 case kMoveNearbyClearAll2_Glitch: SkDebugf(" MoveNearbyClearAll2"); break;
481 case kMoveNearbyMerge_Glitch: SkDebugf(" MoveNearbyMerge"); break;
482 case kMoveNearbyMergeFinal_Glitch: SkDebugf(" MoveNearbyMergeFinal"); break;
483 case kMoveNearbyRelease_Glitch: SkDebugf(" MoveNearbyRelease"); break;
484 case kMoveNearbyReleaseFinal_Glitch: SkDebugf(" MoveNearbyReleaseFinal"); break;
485 case kReleasedSpan_Glitch: SkDebugf(" ReleasedSpan"); break;
486 case kReturnFalse_Glitch: SkDebugf(" ReturnFalse"); break;
487 case kUnaligned_Glitch: SkDebugf(" Unaligned"); break;
488 case kUnalignedHead_Glitch: SkDebugf(" UnalignedHead"); break;
489 case kUnalignedTail_Glitch: SkDebugf(" UnalignedTail"); break;
490 case kUninitialized_Glitch: break;
491 default: SkASSERT(0);
492 }
493 }
494 #endif
495
496 #if defined SK_DEBUG || !FORCE_RELEASE
MathematicaIze(char * str,size_t bufferLen)497 void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
498 size_t len = strlen(str);
499 bool num = false;
500 for (size_t idx = 0; idx < len; ++idx) {
501 if (num && str[idx] == 'e') {
502 if (len + 2 >= bufferLen) {
503 return;
504 }
505 memmove(&str[idx + 2], &str[idx + 1], len - idx);
506 str[idx] = '*';
507 str[idx + 1] = '^';
508 ++len;
509 }
510 num = str[idx] >= '0' && str[idx] <= '9';
511 }
512 }
513
ValidWind(int wind)514 bool SkPathOpsDebug::ValidWind(int wind) {
515 return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
516 }
517
WindingPrintf(int wind)518 void SkPathOpsDebug::WindingPrintf(int wind) {
519 if (wind == SK_MinS32) {
520 SkDebugf("?");
521 } else {
522 SkDebugf("%d", wind);
523 }
524 }
525 #endif // defined SK_DEBUG || !FORCE_RELEASE
526
527
show_function_header(const char * functionName)528 static void show_function_header(const char* functionName) {
529 SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName);
530 if (strcmp("skphealth_com76", functionName) == 0) {
531 SkDebugf("found it\n");
532 }
533 }
534
535 static const char* gOpStrs[] = {
536 "kDifference_SkPathOp",
537 "kIntersect_SkPathOp",
538 "kUnion_SkPathOp",
539 "kXOR_PathOp",
540 "kReverseDifference_SkPathOp",
541 };
542
OpStr(SkPathOp op)543 const char* SkPathOpsDebug::OpStr(SkPathOp op) {
544 return gOpStrs[op];
545 }
546
show_op(SkPathOp op,const char * pathOne,const char * pathTwo)547 static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) {
548 SkDebugf(" testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]);
549 SkDebugf("}\n");
550 }
551
ShowPath(const SkPath & a,const SkPath & b,SkPathOp shapeOp,const char * testName)552 void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
553 const char* testName) {
554 static SkMutex& mutex = *(new SkMutex);
555
556 SkAutoMutexExclusive ac(mutex);
557 show_function_header(testName);
558 ShowOnePath(a, "path", true);
559 ShowOnePath(b, "pathB", true);
560 show_op(shapeOp, "path", "pathB");
561 }
562
563 #if DEBUG_COIN
564
debugAddToGlobalCoinDicts()565 void SkOpGlobalState::debugAddToGlobalCoinDicts() {
566 static SkMutex& mutex = *(new SkMutex);
567 SkAutoMutexExclusive ac(mutex);
568 SkPathOpsDebug::gCoinSumChangedDict.add(fCoinChangedDict);
569 SkPathOpsDebug::gCoinSumVisitedDict.add(fCoinVisitedDict);
570 }
571
572 #endif
573
574 #if DEBUG_T_SECT_LOOP_COUNT
debugAddLoopCount(SkIntersections * i,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn)575 void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt,
576 const SkIntersectionHelper& wn) {
577 for (int index = 0; index < (int) std::size(fDebugLoopCount); ++index) {
578 SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index;
579 if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) {
580 continue;
581 }
582 fDebugLoopCount[index] = i->debugLoopCount(looper);
583 fDebugWorstVerb[index * 2] = wt.segment()->verb();
584 fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb();
585 sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8);
586 memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(),
587 (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint));
588 memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(),
589 (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint));
590 fDebugWorstWeight[index * 2] = wt.weight();
591 fDebugWorstWeight[index * 2 + 1] = wn.weight();
592 }
593 i->debugResetLoopCount();
594 }
595
debugDoYourWorst(SkOpGlobalState * local)596 void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) {
597 for (int index = 0; index < (int) std::size(fDebugLoopCount); ++index) {
598 if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) {
599 continue;
600 }
601 fDebugLoopCount[index] = local->fDebugLoopCount[index];
602 fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2];
603 fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1];
604 memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4],
605 sizeof(SkPoint) * 8);
606 fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2];
607 fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1];
608 }
609 local->debugResetLoopCounts();
610 }
611
dump_curve(SkPath::Verb verb,const SkPoint & pts,float weight)612 static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) {
613 if (!verb) {
614 return;
615 }
616 const char* verbs[] = { "", "line", "quad", "conic", "cubic" };
617 SkDebugf("%s: {{", verbs[verb]);
618 int ptCount = SkPathOpsVerbToPoints(verb);
619 for (int index = 0; index <= ptCount; ++index) {
620 SkDPoint::Dump((&pts)[index]);
621 if (index < ptCount - 1) {
622 SkDebugf(", ");
623 }
624 }
625 SkDebugf("}");
626 if (weight != 1) {
627 SkDebugf(", ");
628 if (weight == floorf(weight)) {
629 SkDebugf("%.0f", weight);
630 } else {
631 SkDebugf("%1.9gf", weight);
632 }
633 }
634 SkDebugf("}\n");
635 }
636
debugLoopReport()637 void SkOpGlobalState::debugLoopReport() {
638 const char* loops[] = { "iterations", "coinChecks", "perpCalcs" };
639 SkDebugf("\n");
640 for (int index = 0; index < (int) std::size(fDebugLoopCount); ++index) {
641 SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]);
642 dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4],
643 fDebugWorstWeight[index * 2]);
644 dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4],
645 fDebugWorstWeight[index * 2 + 1]);
646 }
647 }
648
debugResetLoopCounts()649 void SkOpGlobalState::debugResetLoopCounts() {
650 sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
651 sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb));
652 sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts));
653 sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight));
654 }
655 #endif
656
DebugRunFail()657 bool SkOpGlobalState::DebugRunFail() {
658 return SkPathOpsDebug::gRunFail;
659 }
660
661 // this is const so it can be called by const methods that overwise don't alter state
662 #if DEBUG_VALIDATE || DEBUG_COIN
debugSetPhase(const char * funcName DEBUG_COIN_DECLARE_PARAMS ()) const663 void SkOpGlobalState::debugSetPhase(const char* funcName DEBUG_COIN_DECLARE_PARAMS()) const {
664 auto writable = const_cast<SkOpGlobalState*>(this);
665 #if DEBUG_VALIDATE
666 writable->setPhase(phase);
667 #endif
668 #if DEBUG_COIN
669 SkPathOpsDebug::CoinDictEntry* entry = &writable->fCoinDictEntry;
670 writable->fPreviousFuncName = entry->fFunctionName;
671 entry->fIteration = iteration;
672 entry->fLineNumber = lineNo;
673 entry->fGlitchType = SkPathOpsDebug::kUninitialized_Glitch;
674 entry->fFunctionName = funcName;
675 writable->fCoinVisitedDict.add(*entry);
676 writable->debugAddToCoinChangedDict();
677 #endif
678 }
679 #endif
680
681 #if DEBUG_T_SECT_LOOP_COUNT
debugBumpLoopCount(DebugLoop index)682 void SkIntersections::debugBumpLoopCount(DebugLoop index) {
683 fDebugLoopCount[index]++;
684 }
685
debugLoopCount(DebugLoop index) const686 int SkIntersections::debugLoopCount(DebugLoop index) const {
687 return fDebugLoopCount[index];
688 }
689
debugResetLoopCount()690 void SkIntersections::debugResetLoopCount() {
691 sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
692 }
693 #endif
694
debugToCubic() const695 SkDCubic SkDQuad::debugToCubic() const {
696 SkDCubic cubic;
697 cubic[0] = fPts[0];
698 cubic[2] = fPts[1];
699 cubic[3] = fPts[2];
700 cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3;
701 cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3;
702 cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3;
703 cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3;
704 return cubic;
705 }
706
debugSet(const SkDPoint * pts)707 void SkDQuad::debugSet(const SkDPoint* pts) {
708 memcpy(fPts, pts, sizeof(fPts));
709 SkDEBUGCODE(fDebugGlobalState = nullptr);
710 }
711
debugSet(const SkDPoint * pts)712 void SkDCubic::debugSet(const SkDPoint* pts) {
713 memcpy(fPts, pts, sizeof(fPts));
714 SkDEBUGCODE(fDebugGlobalState = nullptr);
715 }
716
debugSet(const SkDPoint * pts,SkScalar weight)717 void SkDConic::debugSet(const SkDPoint* pts, SkScalar weight) {
718 fPts.debugSet(pts);
719 fWeight = weight;
720 }
721
debugInit()722 void SkDRect::debugInit() {
723 fLeft = fTop = fRight = fBottom = SK_ScalarNaN;
724 }
725
726 #if DEBUG_COIN
727 // commented-out lines keep this in sync with addT()
debugAddT(double t,SkPathOpsDebug::GlitchLog * log) const728 const SkOpPtT* SkOpSegment::debugAddT(double t, SkPathOpsDebug::GlitchLog* log) const {
729 debugValidate();
730 SkPoint pt = this->ptAtT(t);
731 const SkOpSpanBase* span = &fHead;
732 do {
733 const SkOpPtT* result = span->ptT();
734 if (t == result->fT || this->match(result, this, t, pt)) {
735 // span->bumpSpanAdds();
736 return result;
737 }
738 if (t < result->fT) {
739 const SkOpSpan* prev = result->span()->prev();
740 FAIL_WITH_NULL_IF(!prev, span);
741 // marks in global state that new op span has been allocated
742 this->globalState()->setAllocatedOpSpan();
743 // span->init(this, prev, t, pt);
744 this->debugValidate();
745 // #if DEBUG_ADD_T
746 // SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
747 // span->segment()->debugID(), span->debugID());
748 // #endif
749 // span->bumpSpanAdds();
750 return nullptr;
751 }
752 FAIL_WITH_NULL_IF(span != &fTail, span);
753 } while ((span = span->upCast()->next()));
754 SkASSERT(0);
755 return nullptr; // we never get here, but need this to satisfy compiler
756 }
757 #endif
758
759 #if DEBUG_ANGLE
debugCheckAngleCoin() const760 void SkOpSegment::debugCheckAngleCoin() const {
761 const SkOpSpanBase* base = &fHead;
762 const SkOpSpan* span;
763 do {
764 const SkOpAngle* angle = base->fromAngle();
765 if (angle && angle->debugCheckCoincidence()) {
766 angle->debugCheckNearCoincidence();
767 }
768 if (base->final()) {
769 break;
770 }
771 span = base->upCast();
772 angle = span->toAngle();
773 if (angle && angle->debugCheckCoincidence()) {
774 angle->debugCheckNearCoincidence();
775 }
776 } while ((base = span->next()));
777 }
778 #endif
779
780 #if DEBUG_COIN
781 // this mimics the order of the checks in handle coincidence
debugCheckHealth(SkPathOpsDebug::GlitchLog * glitches) const782 void SkOpSegment::debugCheckHealth(SkPathOpsDebug::GlitchLog* glitches) const {
783 debugMoveMultiples(glitches);
784 debugMoveNearby(glitches);
785 debugMissingCoincidence(glitches);
786 }
787
788 // commented-out lines keep this in sync with clearAll()
debugClearAll(SkPathOpsDebug::GlitchLog * glitches) const789 void SkOpSegment::debugClearAll(SkPathOpsDebug::GlitchLog* glitches) const {
790 const SkOpSpan* span = &fHead;
791 do {
792 this->debugClearOne(span, glitches);
793 } while ((span = span->next()->upCastable()));
794 this->globalState()->coincidence()->debugRelease(glitches, this);
795 }
796
797 // commented-out lines keep this in sync with clearOne()
debugClearOne(const SkOpSpan * span,SkPathOpsDebug::GlitchLog * glitches) const798 void SkOpSegment::debugClearOne(const SkOpSpan* span, SkPathOpsDebug::GlitchLog* glitches) const {
799 if (span->windValue()) glitches->record(SkPathOpsDebug::kCollapsedWindValue_Glitch, span);
800 if (span->oppValue()) glitches->record(SkPathOpsDebug::kCollapsedOppValue_Glitch, span);
801 if (!span->done()) glitches->record(SkPathOpsDebug::kCollapsedDone_Glitch, span);
802 }
803 #endif
804
debugLastAngle()805 SkOpAngle* SkOpSegment::debugLastAngle() {
806 SkOpAngle* result = nullptr;
807 SkOpSpan* span = this->head();
808 do {
809 if (span->toAngle()) {
810 SkASSERT(!result);
811 result = span->toAngle();
812 }
813 } while ((span = span->next()->upCastable()));
814 SkASSERT(result);
815 return result;
816 }
817
818 #if DEBUG_COIN
819 // commented-out lines keep this in sync with ClearVisited
DebugClearVisited(const SkOpSpanBase * span)820 void SkOpSegment::DebugClearVisited(const SkOpSpanBase* span) {
821 // reset visited flag back to false
822 do {
823 const SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
824 while ((ptT = ptT->next()) != stopPtT) {
825 const SkOpSegment* opp = ptT->segment();
826 opp->resetDebugVisited();
827 }
828 } while (!span->final() && (span = span->upCast()->next()));
829 }
830 #endif
831
832 #if DEBUG_COIN
833 // commented-out lines keep this in sync with missingCoincidence()
834 // look for pairs of undetected coincident curves
835 // assumes that segments going in have visited flag clear
836 // Even though pairs of curves correct detect coincident runs, a run may be missed
837 // if the coincidence is a product of multiple intersections. For instance, given
838 // curves A, B, and C:
839 // A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
840 // the end of C that the intersection is replaced with the end of C.
841 // Even though A-B correctly do not detect an intersection at point 2,
842 // the resulting run from point 1 to point 2 is coincident on A and B.
debugMissingCoincidence(SkPathOpsDebug::GlitchLog * log) const843 void SkOpSegment::debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const {
844 if (this->done()) {
845 return;
846 }
847 const SkOpSpan* prior = nullptr;
848 const SkOpSpanBase* spanBase = &fHead;
849 // bool result = false;
850 do {
851 const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
852 SkASSERT(ptT->span() == spanBase);
853 while ((ptT = ptT->next()) != spanStopPtT) {
854 if (ptT->deleted()) {
855 continue;
856 }
857 const SkOpSegment* opp = ptT->span()->segment();
858 if (opp->done()) {
859 continue;
860 }
861 // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
862 if (!opp->debugVisited()) {
863 continue;
864 }
865 if (spanBase == &fHead) {
866 continue;
867 }
868 if (ptT->segment() == this) {
869 continue;
870 }
871 const SkOpSpan* span = spanBase->upCastable();
872 // FIXME?: this assumes that if the opposite segment is coincident then no more
873 // coincidence needs to be detected. This may not be true.
874 if (span && span->segment() != opp && span->containsCoincidence(opp)) { // debug has additional condition since it may be called before inner duplicate points have been deleted
875 continue;
876 }
877 if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) { // debug has additional condition since it may be called before inner duplicate points have been deleted
878 continue;
879 }
880 const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
881 // find prior span containing opp segment
882 const SkOpSegment* priorOpp = nullptr;
883 const SkOpSpan* priorTest = spanBase->prev();
884 while (!priorOpp && priorTest) {
885 priorStopPtT = priorPtT = priorTest->ptT();
886 while ((priorPtT = priorPtT->next()) != priorStopPtT) {
887 if (priorPtT->deleted()) {
888 continue;
889 }
890 const SkOpSegment* segment = priorPtT->span()->segment();
891 if (segment == opp) {
892 prior = priorTest;
893 priorOpp = opp;
894 break;
895 }
896 }
897 priorTest = priorTest->prev();
898 }
899 if (!priorOpp) {
900 continue;
901 }
902 if (priorPtT == ptT) {
903 continue;
904 }
905 const SkOpPtT* oppStart = prior->ptT();
906 const SkOpPtT* oppEnd = spanBase->ptT();
907 bool swapped = priorPtT->fT > ptT->fT;
908 if (swapped) {
909 using std::swap;
910 swap(priorPtT, ptT);
911 swap(oppStart, oppEnd);
912 }
913 const SkOpCoincidence* coincidence = this->globalState()->coincidence();
914 const SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
915 const SkOpPtT* rootPtT = ptT->span()->ptT();
916 const SkOpPtT* rootOppStart = oppStart->span()->ptT();
917 const SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
918 if (coincidence->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
919 goto swapBack;
920 }
921 if (testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
922 // mark coincidence
923 #if DEBUG_COINCIDENCE_VERBOSE
924 // SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
925 // rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
926 // rootOppEnd->debugID());
927 #endif
928 log->record(SkPathOpsDebug::kMissingCoin_Glitch, priorPtT, ptT, oppStart, oppEnd);
929 // coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
930 // }
931 #if DEBUG_COINCIDENCE
932 // SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
933 #endif
934 // result = true;
935 }
936 swapBack:
937 if (swapped) {
938 using std::swap;
939 swap(priorPtT, ptT);
940 }
941 }
942 } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
943 DebugClearVisited(&fHead);
944 return;
945 }
946
947 // commented-out lines keep this in sync with moveMultiples()
948 // if a span has more than one intersection, merge the other segments' span as needed
debugMoveMultiples(SkPathOpsDebug::GlitchLog * glitches) const949 void SkOpSegment::debugMoveMultiples(SkPathOpsDebug::GlitchLog* glitches) const {
950 debugValidate();
951 const SkOpSpanBase* test = &fHead;
952 do {
953 int addCount = test->spanAddsCount();
954 // SkASSERT(addCount >= 1);
955 if (addCount <= 1) {
956 continue;
957 }
958 const SkOpPtT* startPtT = test->ptT();
959 const SkOpPtT* testPtT = startPtT;
960 do { // iterate through all spans associated with start
961 const SkOpSpanBase* oppSpan = testPtT->span();
962 if (oppSpan->spanAddsCount() == addCount) {
963 continue;
964 }
965 if (oppSpan->deleted()) {
966 continue;
967 }
968 const SkOpSegment* oppSegment = oppSpan->segment();
969 if (oppSegment == this) {
970 continue;
971 }
972 // find range of spans to consider merging
973 const SkOpSpanBase* oppPrev = oppSpan;
974 const SkOpSpanBase* oppFirst = oppSpan;
975 while ((oppPrev = oppPrev->prev())) {
976 if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
977 break;
978 }
979 if (oppPrev->spanAddsCount() == addCount) {
980 continue;
981 }
982 if (oppPrev->deleted()) {
983 continue;
984 }
985 oppFirst = oppPrev;
986 }
987 const SkOpSpanBase* oppNext = oppSpan;
988 const SkOpSpanBase* oppLast = oppSpan;
989 while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
990 if (!roughly_equal(oppNext->t(), oppSpan->t())) {
991 break;
992 }
993 if (oppNext->spanAddsCount() == addCount) {
994 continue;
995 }
996 if (oppNext->deleted()) {
997 continue;
998 }
999 oppLast = oppNext;
1000 }
1001 if (oppFirst == oppLast) {
1002 continue;
1003 }
1004 const SkOpSpanBase* oppTest = oppFirst;
1005 do {
1006 if (oppTest == oppSpan) {
1007 continue;
1008 }
1009 // check to see if the candidate meets specific criteria:
1010 // it contains spans of segments in test's loop but not including 'this'
1011 const SkOpPtT* oppStartPtT = oppTest->ptT();
1012 const SkOpPtT* oppPtT = oppStartPtT;
1013 while ((oppPtT = oppPtT->next()) != oppStartPtT) {
1014 const SkOpSegment* oppPtTSegment = oppPtT->segment();
1015 if (oppPtTSegment == this) {
1016 goto tryNextSpan;
1017 }
1018 const SkOpPtT* matchPtT = startPtT;
1019 do {
1020 if (matchPtT->segment() == oppPtTSegment) {
1021 goto foundMatch;
1022 }
1023 } while ((matchPtT = matchPtT->next()) != startPtT);
1024 goto tryNextSpan;
1025 foundMatch: // merge oppTest and oppSpan
1026 oppSegment->debugValidate();
1027 oppTest->debugMergeMatches(glitches, oppSpan);
1028 oppTest->debugAddOpp(glitches, oppSpan);
1029 oppSegment->debugValidate();
1030 goto checkNextSpan;
1031 }
1032 tryNextSpan:
1033 ;
1034 } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
1035 } while ((testPtT = testPtT->next()) != startPtT);
1036 checkNextSpan:
1037 ;
1038 } while ((test = test->final() ? nullptr : test->upCast()->next()));
1039 debugValidate();
1040 return;
1041 }
1042
1043 // commented-out lines keep this in sync with moveNearby()
1044 // Move nearby t values and pts so they all hang off the same span. Alignment happens later.
debugMoveNearby(SkPathOpsDebug::GlitchLog * glitches) const1045 void SkOpSegment::debugMoveNearby(SkPathOpsDebug::GlitchLog* glitches) const {
1046 debugValidate();
1047 // release undeleted spans pointing to this seg that are linked to the primary span
1048 const SkOpSpanBase* spanBase = &fHead;
1049 do {
1050 const SkOpPtT* ptT = spanBase->ptT();
1051 const SkOpPtT* headPtT = ptT;
1052 while ((ptT = ptT->next()) != headPtT) {
1053 const SkOpSpanBase* test = ptT->span();
1054 if (ptT->segment() == this && !ptT->deleted() && test != spanBase
1055 && test->ptT() == ptT) {
1056 if (test->final()) {
1057 if (spanBase == &fHead) {
1058 glitches->record(SkPathOpsDebug::kMoveNearbyClearAll_Glitch, this);
1059 // return;
1060 }
1061 glitches->record(SkPathOpsDebug::kMoveNearbyReleaseFinal_Glitch, spanBase, ptT);
1062 } else if (test->prev()) {
1063 glitches->record(SkPathOpsDebug::kMoveNearbyRelease_Glitch, test, headPtT);
1064 }
1065 // break;
1066 }
1067 }
1068 spanBase = spanBase->upCast()->next();
1069 } while (!spanBase->final());
1070
1071 // This loop looks for adjacent spans which are near by
1072 spanBase = &fHead;
1073 do { // iterate through all spans associated with start
1074 const SkOpSpanBase* test = spanBase->upCast()->next();
1075 bool found;
1076 if (!this->spansNearby(spanBase, test, &found)) {
1077 glitches->record(SkPathOpsDebug::kMoveNearbyMergeFinal_Glitch, test);
1078 }
1079 if (found) {
1080 if (test->final()) {
1081 if (spanBase->prev()) {
1082 glitches->record(SkPathOpsDebug::kMoveNearbyMergeFinal_Glitch, test);
1083 } else {
1084 glitches->record(SkPathOpsDebug::kMoveNearbyClearAll2_Glitch, this);
1085 // return
1086 }
1087 } else {
1088 glitches->record(SkPathOpsDebug::kMoveNearbyMerge_Glitch, spanBase);
1089 }
1090 }
1091 spanBase = test;
1092 } while (!spanBase->final());
1093 debugValidate();
1094 }
1095 #endif
1096
debugReset()1097 void SkOpSegment::debugReset() {
1098 this->init(this->fPts, this->fWeight, this->contour(), this->verb());
1099 }
1100
1101 #if DEBUG_COINCIDENCE_ORDER
debugSetCoinT(int index,SkScalar t) const1102 void SkOpSegment::debugSetCoinT(int index, SkScalar t) const {
1103 if (fDebugBaseMax < 0 || fDebugBaseIndex == index) {
1104 fDebugBaseIndex = index;
1105 fDebugBaseMin = std::min(t, fDebugBaseMin);
1106 fDebugBaseMax = std::max(t, fDebugBaseMax);
1107 return;
1108 }
1109 SkASSERT(fDebugBaseMin >= t || t >= fDebugBaseMax);
1110 if (fDebugLastMax < 0 || fDebugLastIndex == index) {
1111 fDebugLastIndex = index;
1112 fDebugLastMin = std::min(t, fDebugLastMin);
1113 fDebugLastMax = std::max(t, fDebugLastMax);
1114 return;
1115 }
1116 SkASSERT(fDebugLastMin >= t || t >= fDebugLastMax);
1117 SkASSERT((t - fDebugBaseMin > 0) == (fDebugLastMin - fDebugBaseMin > 0));
1118 }
1119 #endif
1120
1121 #if DEBUG_ACTIVE_SPANS
debugShowActiveSpans(SkString * str) const1122 void SkOpSegment::debugShowActiveSpans(SkString* str) const {
1123 debugValidate();
1124 if (done()) {
1125 return;
1126 }
1127 int lastId = -1;
1128 double lastT = -1;
1129 const SkOpSpan* span = &fHead;
1130 do {
1131 if (span->done()) {
1132 continue;
1133 }
1134 if (lastId == this->debugID() && lastT == span->t()) {
1135 continue;
1136 }
1137 lastId = this->debugID();
1138 lastT = span->t();
1139 str->appendf("%s id=%d", __FUNCTION__, this->debugID());
1140 // since endpoints may have be adjusted, show actual computed curves
1141 SkDCurve curvePart;
1142 this->subDivide(span, span->next(), &curvePart);
1143 const SkDPoint* pts = curvePart.fCubic.fPts;
1144 str->appendf(" (%1.9g,%1.9g", pts[0].fX, pts[0].fY);
1145 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1146 str->appendf(" %1.9g,%1.9g", pts[vIndex].fX, pts[vIndex].fY);
1147 }
1148 if (SkPath::kConic_Verb == fVerb) {
1149 str->appendf(" %1.9gf", curvePart.fConic.fWeight);
1150 }
1151 str->appendf(") t=%1.9g tEnd=%1.9g", span->t(), span->next()->t());
1152 if (span->windSum() == SK_MinS32) {
1153 str->appendf(" windSum=?");
1154 } else {
1155 str->appendf(" windSum=%d", span->windSum());
1156 }
1157 if (span->oppValue() && span->oppSum() == SK_MinS32) {
1158 str->appendf(" oppSum=?");
1159 } else if (span->oppValue() || span->oppSum() != SK_MinS32) {
1160 str->appendf(" oppSum=%d", span->oppSum());
1161 }
1162 str->appendf(" windValue=%d", span->windValue());
1163 if (span->oppValue() || span->oppSum() != SK_MinS32) {
1164 str->appendf(" oppValue=%d", span->oppValue());
1165 }
1166 str->appendf("\n");
1167 } while ((span = span->next()->upCastable()));
1168 }
1169 #endif
1170
1171 #if DEBUG_MARK_DONE
debugShowNewWinding(const char * fun,const SkOpSpan * span,int winding)1172 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
1173 const SkPoint& pt = span->ptT()->fPt;
1174 SkDebugf("%s id=%d", fun, this->debugID());
1175 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1176 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1177 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1178 }
1179 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
1180 span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
1181 if (winding == SK_MinS32) {
1182 SkDebugf("?");
1183 } else {
1184 SkDebugf("%d", winding);
1185 }
1186 SkDebugf(" windSum=");
1187 if (span->windSum() == SK_MinS32) {
1188 SkDebugf("?");
1189 } else {
1190 SkDebugf("%d", span->windSum());
1191 }
1192 SkDebugf(" windValue=%d\n", span->windValue());
1193 }
1194
debugShowNewWinding(const char * fun,const SkOpSpan * span,int winding,int oppWinding)1195 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
1196 int oppWinding) {
1197 const SkPoint& pt = span->ptT()->fPt;
1198 SkDebugf("%s id=%d", fun, this->debugID());
1199 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
1200 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
1201 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
1202 }
1203 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
1204 span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
1205 if (winding == SK_MinS32) {
1206 SkDebugf("?");
1207 } else {
1208 SkDebugf("%d", winding);
1209 }
1210 SkDebugf(" newOppSum=");
1211 if (oppWinding == SK_MinS32) {
1212 SkDebugf("?");
1213 } else {
1214 SkDebugf("%d", oppWinding);
1215 }
1216 SkDebugf(" oppSum=");
1217 if (span->oppSum() == SK_MinS32) {
1218 SkDebugf("?");
1219 } else {
1220 SkDebugf("%d", span->oppSum());
1221 }
1222 SkDebugf(" windSum=");
1223 if (span->windSum() == SK_MinS32) {
1224 SkDebugf("?");
1225 } else {
1226 SkDebugf("%d", span->windSum());
1227 }
1228 SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
1229 }
1230
1231 #endif
1232
1233 // loop looking for a pair of angle parts that are too close to be sorted
1234 /* This is called after other more simple intersection and angle sorting tests have been exhausted.
1235 This should be rarely called -- the test below is thorough and time consuming.
1236 This checks the distance between start points; the distance between
1237 */
1238 #if DEBUG_ANGLE
debugCheckNearCoincidence() const1239 void SkOpAngle::debugCheckNearCoincidence() const {
1240 const SkOpAngle* test = this;
1241 do {
1242 const SkOpSegment* testSegment = test->segment();
1243 double testStartT = test->start()->t();
1244 SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
1245 double testEndT = test->end()->t();
1246 SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
1247 double testLenSq = testStartPt.distanceSquared(testEndPt);
1248 SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
1249 double testMidT = (testStartT + testEndT) / 2;
1250 const SkOpAngle* next = test;
1251 while ((next = next->fNext) != this) {
1252 SkOpSegment* nextSegment = next->segment();
1253 double testMidDistSq = testSegment->distSq(testMidT, next);
1254 double testEndDistSq = testSegment->distSq(testEndT, next);
1255 double nextStartT = next->start()->t();
1256 SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
1257 double distSq = testStartPt.distanceSquared(nextStartPt);
1258 double nextEndT = next->end()->t();
1259 double nextMidT = (nextStartT + nextEndT) / 2;
1260 double nextMidDistSq = nextSegment->distSq(nextMidT, test);
1261 double nextEndDistSq = nextSegment->distSq(nextEndT, test);
1262 SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
1263 testSegment->debugID(), nextSegment->debugID());
1264 SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
1265 SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
1266 SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
1267 SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
1268 SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
1269 double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
1270 SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
1271 SkDebugf("\n");
1272 }
1273 test = test->fNext;
1274 } while (test->fNext != this);
1275 }
1276 #endif
1277
1278 #if DEBUG_ANGLE
debugPart() const1279 SkString SkOpAngle::debugPart() const {
1280 SkString result;
1281 switch (this->segment()->verb()) {
1282 case SkPath::kLine_Verb:
1283 result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fPart.fCurve),
1284 this->segment()->debugID());
1285 break;
1286 case SkPath::kQuad_Verb:
1287 result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fPart.fCurve),
1288 this->segment()->debugID());
1289 break;
1290 case SkPath::kConic_Verb:
1291 result.printf(CONIC_DEBUG_STR " id=%d",
1292 CONIC_DEBUG_DATA(fPart.fCurve, fPart.fCurve.fConic.fWeight),
1293 this->segment()->debugID());
1294 break;
1295 case SkPath::kCubic_Verb:
1296 result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fPart.fCurve),
1297 this->segment()->debugID());
1298 break;
1299 default:
1300 SkASSERT(0);
1301 }
1302 return result;
1303 }
1304 #endif
1305
1306 #if DEBUG_SORT
debugLoop() const1307 void SkOpAngle::debugLoop() const {
1308 const SkOpAngle* first = this;
1309 const SkOpAngle* next = this;
1310 do {
1311 next->dumpOne(true);
1312 SkDebugf("\n");
1313 next = next->fNext;
1314 } while (next && next != first);
1315 next = first;
1316 do {
1317 next->debugValidate();
1318 next = next->fNext;
1319 } while (next && next != first);
1320 }
1321 #endif
1322
debugValidate() const1323 void SkOpAngle::debugValidate() const {
1324 #if DEBUG_COINCIDENCE
1325 if (this->globalState()->debugCheckHealth()) {
1326 return;
1327 }
1328 #endif
1329 #if DEBUG_VALIDATE
1330 const SkOpAngle* first = this;
1331 const SkOpAngle* next = this;
1332 int wind = 0;
1333 int opp = 0;
1334 int lastXor = -1;
1335 int lastOppXor = -1;
1336 do {
1337 if (next->unorderable()) {
1338 return;
1339 }
1340 const SkOpSpan* minSpan = next->start()->starter(next->end());
1341 if (minSpan->windValue() == SK_MinS32) {
1342 return;
1343 }
1344 bool op = next->segment()->operand();
1345 bool isXor = next->segment()->isXor();
1346 bool oppXor = next->segment()->oppXor();
1347 SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
1348 SkASSERT(!DEBUG_LIMIT_WIND_SUM
1349 || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
1350 bool useXor = op ? oppXor : isXor;
1351 SkASSERT(lastXor == -1 || lastXor == (int) useXor);
1352 lastXor = (int) useXor;
1353 wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue());
1354 if (useXor) {
1355 wind &= 1;
1356 }
1357 useXor = op ? isXor : oppXor;
1358 SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
1359 lastOppXor = (int) useXor;
1360 opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue());
1361 if (useXor) {
1362 opp &= 1;
1363 }
1364 next = next->fNext;
1365 } while (next && next != first);
1366 SkASSERT(wind == 0 || !SkPathOpsDebug::gRunFail);
1367 SkASSERT(opp == 0 || !SkPathOpsDebug::gRunFail);
1368 #endif
1369 }
1370
debugValidateNext() const1371 void SkOpAngle::debugValidateNext() const {
1372 #if !FORCE_RELEASE
1373 const SkOpAngle* first = this;
1374 const SkOpAngle* next = first;
1375 SkTDArray<const SkOpAngle*> angles;
1376 do {
1377 // SkASSERT_RELEASE(next->fSegment->debugContains(next));
1378 angles.push_back(next);
1379 next = next->next();
1380 if (next == first) {
1381 break;
1382 }
1383 SkASSERT_RELEASE(!angles.contains(next));
1384 if (!next) {
1385 return;
1386 }
1387 } while (true);
1388 #endif
1389 }
1390
1391 #ifdef SK_DEBUG
debugStartCheck(const SkOpSpanBase * outer,const SkOpSpanBase * over,const SkOpGlobalState * debugState) const1392 void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
1393 const SkOpGlobalState* debugState) const {
1394 SkASSERT(coinPtTEnd()->span() == over || !SkOpGlobalState::DebugRunFail());
1395 SkASSERT(oppPtTEnd()->span() == outer || !SkOpGlobalState::DebugRunFail());
1396 }
1397 #endif
1398
1399 #if DEBUG_COIN
1400 // sets the span's end to the ptT referenced by the previous-next
debugCorrectOneEnd(SkPathOpsDebug::GlitchLog * log,const SkOpPtT * (SkCoincidentSpans::* getEnd)()const,void (SkCoincidentSpans::* setEnd)(const SkOpPtT * ptT)const) const1401 void SkCoincidentSpans::debugCorrectOneEnd(SkPathOpsDebug::GlitchLog* log,
1402 const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
1403 void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) const ) const {
1404 const SkOpPtT* origPtT = (this->*getEnd)();
1405 const SkOpSpanBase* origSpan = origPtT->span();
1406 const SkOpSpan* prev = origSpan->prev();
1407 const SkOpPtT* testPtT = prev ? prev->next()->ptT()
1408 : origSpan->upCast()->next()->prev()->ptT();
1409 if (origPtT != testPtT) {
1410 log->record(SkPathOpsDebug::kCorrectEnd_Glitch, this, origPtT, testPtT);
1411 }
1412 }
1413
1414
1415 /* Commented-out lines keep this in sync with correctEnds */
1416 // FIXME: member pointers have fallen out of favor and can be replaced with
1417 // an alternative approach.
1418 // makes all span ends agree with the segment's spans that define them
debugCorrectEnds(SkPathOpsDebug::GlitchLog * log) const1419 void SkCoincidentSpans::debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const {
1420 this->debugCorrectOneEnd(log, &SkCoincidentSpans::coinPtTStart, nullptr);
1421 this->debugCorrectOneEnd(log, &SkCoincidentSpans::coinPtTEnd, nullptr);
1422 this->debugCorrectOneEnd(log, &SkCoincidentSpans::oppPtTStart, nullptr);
1423 this->debugCorrectOneEnd(log, &SkCoincidentSpans::oppPtTEnd, nullptr);
1424 }
1425
1426 /* Commented-out lines keep this in sync with expand */
1427 // expand the range by checking adjacent spans for coincidence
debugExpand(SkPathOpsDebug::GlitchLog * log) const1428 bool SkCoincidentSpans::debugExpand(SkPathOpsDebug::GlitchLog* log) const {
1429 bool expanded = false;
1430 const SkOpSegment* segment = coinPtTStart()->segment();
1431 const SkOpSegment* oppSegment = oppPtTStart()->segment();
1432 do {
1433 const SkOpSpan* start = coinPtTStart()->span()->upCast();
1434 const SkOpSpan* prev = start->prev();
1435 const SkOpPtT* oppPtT;
1436 if (!prev || !(oppPtT = prev->contains(oppSegment))) {
1437 break;
1438 }
1439 double midT = (prev->t() + start->t()) / 2;
1440 if (!segment->isClose(midT, oppSegment)) {
1441 break;
1442 }
1443 if (log) log->record(SkPathOpsDebug::kExpandCoin_Glitch, this, prev->ptT(), oppPtT);
1444 expanded = true;
1445 } while (false); // actual continues while expansion is possible
1446 do {
1447 const SkOpSpanBase* end = coinPtTEnd()->span();
1448 SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
1449 if (next && next->deleted()) {
1450 break;
1451 }
1452 const SkOpPtT* oppPtT;
1453 if (!next || !(oppPtT = next->contains(oppSegment))) {
1454 break;
1455 }
1456 double midT = (end->t() + next->t()) / 2;
1457 if (!segment->isClose(midT, oppSegment)) {
1458 break;
1459 }
1460 if (log) log->record(SkPathOpsDebug::kExpandCoin_Glitch, this, next->ptT(), oppPtT);
1461 expanded = true;
1462 } while (false); // actual continues while expansion is possible
1463 return expanded;
1464 }
1465
1466 // description below
debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog * log,const SkOpSpan * base,const SkOpSpanBase * testSpan) const1467 void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log, const SkOpSpan* base, const SkOpSpanBase* testSpan) const {
1468 const SkOpPtT* testPtT = testSpan->ptT();
1469 const SkOpPtT* stopPtT = testPtT;
1470 const SkOpSegment* baseSeg = base->segment();
1471 while ((testPtT = testPtT->next()) != stopPtT) {
1472 const SkOpSegment* testSeg = testPtT->segment();
1473 if (testPtT->deleted()) {
1474 continue;
1475 }
1476 if (testSeg == baseSeg) {
1477 continue;
1478 }
1479 if (testPtT->span()->ptT() != testPtT) {
1480 continue;
1481 }
1482 if (this->contains(baseSeg, testSeg, testPtT->fT)) {
1483 continue;
1484 }
1485 // intersect perp with base->ptT() with testPtT->segment()
1486 SkDVector dxdy = baseSeg->dSlopeAtT(base->t());
1487 const SkPoint& pt = base->pt();
1488 SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}};
1489 SkIntersections i;
1490 (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i);
1491 for (int index = 0; index < i.used(); ++index) {
1492 double t = i[0][index];
1493 if (!between(0, t, 1)) {
1494 continue;
1495 }
1496 SkDPoint oppPt = i.pt(index);
1497 if (!oppPt.approximatelyEqual(pt)) {
1498 continue;
1499 }
1500 SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
1501 SkOpPtT* oppStart = writableSeg->addT(t);
1502 if (oppStart == testPtT) {
1503 continue;
1504 }
1505 SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
1506 oppStart->span()->addOpp(writableBase);
1507 if (oppStart->deleted()) {
1508 continue;
1509 }
1510 SkOpSegment* coinSeg = base->segment();
1511 SkOpSegment* oppSeg = oppStart->segment();
1512 double coinTs, coinTe, oppTs, oppTe;
1513 if (Ordered(coinSeg, oppSeg)) {
1514 coinTs = base->t();
1515 coinTe = testSpan->t();
1516 oppTs = oppStart->fT;
1517 oppTe = testPtT->fT;
1518 } else {
1519 using std::swap;
1520 swap(coinSeg, oppSeg);
1521 coinTs = oppStart->fT;
1522 coinTe = testPtT->fT;
1523 oppTs = base->t();
1524 oppTe = testSpan->t();
1525 }
1526 if (coinTs > coinTe) {
1527 using std::swap;
1528 swap(coinTs, coinTe);
1529 swap(oppTs, oppTe);
1530 }
1531 bool added;
1532 this->debugAddOrOverlap(log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added);
1533 }
1534 }
1535 return;
1536 }
1537
1538 // description below
debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog * log,const SkOpPtT * ptT) const1539 void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log, const SkOpPtT* ptT) const {
1540 FAIL_IF_COIN(!ptT->span()->upCastable(), ptT->span());
1541 const SkOpSpan* base = ptT->span()->upCast();
1542 const SkOpSpan* prev = base->prev();
1543 FAIL_IF_COIN(!prev, ptT->span());
1544 if (!prev->isCanceled()) {
1545 this->debugAddEndMovedSpans(log, base, base->prev());
1546 }
1547 if (!base->isCanceled()) {
1548 this->debugAddEndMovedSpans(log, base, base->next());
1549 }
1550 return;
1551 }
1552
1553 /* If A is coincident with B and B includes an endpoint, and A's matching point
1554 is not the endpoint (i.e., there's an implied line connecting B-end and A)
1555 then assume that the same implied line may intersect another curve close to B.
1556 Since we only care about coincidence that was undetected, look at the
1557 ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but
1558 next door) and see if the A matching point is close enough to form another
1559 coincident pair. If so, check for a new coincident span between B-end/A ptT loop
1560 and the adjacent ptT loop.
1561 */
debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog * log) const1562 void SkOpCoincidence::debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log) const {
1563 const SkCoincidentSpans* span = fHead;
1564 if (!span) {
1565 return;
1566 }
1567 // fTop = span;
1568 // fHead = nullptr;
1569 do {
1570 if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
1571 FAIL_IF_COIN(1 == span->coinPtTStart()->fT, span);
1572 bool onEnd = span->coinPtTStart()->fT == 0;
1573 bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
1574 if (onEnd) {
1575 if (!oOnEnd) { // if both are on end, any nearby intersect was already found
1576 this->debugAddEndMovedSpans(log, span->oppPtTStart());
1577 }
1578 } else if (oOnEnd) {
1579 this->debugAddEndMovedSpans(log, span->coinPtTStart());
1580 }
1581 }
1582 if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) {
1583 bool onEnd = span->coinPtTEnd()->fT == 1;
1584 bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT);
1585 if (onEnd) {
1586 if (!oOnEnd) {
1587 this->debugAddEndMovedSpans(log, span->oppPtTEnd());
1588 }
1589 } else if (oOnEnd) {
1590 this->debugAddEndMovedSpans(log, span->coinPtTEnd());
1591 }
1592 }
1593 } while ((span = span->next()));
1594 // this->restoreHead();
1595 return;
1596 }
1597
1598 /* Commented-out lines keep this in sync with addExpanded */
1599 // for each coincident pair, match the spans
1600 // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
debugAddExpanded(SkPathOpsDebug::GlitchLog * log) const1601 void SkOpCoincidence::debugAddExpanded(SkPathOpsDebug::GlitchLog* log) const {
1602 // DEBUG_SET_PHASE();
1603 const SkCoincidentSpans* coin = this->fHead;
1604 if (!coin) {
1605 return;
1606 }
1607 do {
1608 const SkOpPtT* startPtT = coin->coinPtTStart();
1609 const SkOpPtT* oStartPtT = coin->oppPtTStart();
1610 double priorT = startPtT->fT;
1611 double oPriorT = oStartPtT->fT;
1612 FAIL_IF_COIN(!startPtT->contains(oStartPtT), coin);
1613 SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
1614 const SkOpSpanBase* start = startPtT->span();
1615 const SkOpSpanBase* oStart = oStartPtT->span();
1616 const SkOpSpanBase* end = coin->coinPtTEnd()->span();
1617 const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
1618 FAIL_IF_COIN(oEnd->deleted(), coin);
1619 FAIL_IF_COIN(!start->upCastable(), coin);
1620 const SkOpSpanBase* test = start->upCast()->next();
1621 FAIL_IF_COIN(!coin->flipped() && !oStart->upCastable(), coin);
1622 const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
1623 FAIL_IF_COIN(!oTest, coin);
1624 const SkOpSegment* seg = start->segment();
1625 const SkOpSegment* oSeg = oStart->segment();
1626 while (test != end || oTest != oEnd) {
1627 const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
1628 const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
1629 if (!containedOpp || !containedThis) {
1630 // choose the ends, or the first common pt-t list shared by both
1631 double nextT, oNextT;
1632 if (containedOpp) {
1633 nextT = test->t();
1634 oNextT = containedOpp->fT;
1635 } else if (containedThis) {
1636 nextT = containedThis->fT;
1637 oNextT = oTest->t();
1638 } else {
1639 // iterate through until a pt-t list found that contains the other
1640 const SkOpSpanBase* walk = test;
1641 const SkOpPtT* walkOpp;
1642 do {
1643 FAIL_IF_COIN(!walk->upCastable(), coin);
1644 walk = walk->upCast()->next();
1645 } while (!(walkOpp = walk->ptT()->contains(oSeg))
1646 && walk != coin->coinPtTEnd()->span());
1647 FAIL_IF_COIN(!walkOpp, coin);
1648 nextT = walk->t();
1649 oNextT = walkOpp->fT;
1650 }
1651 // use t ranges to guess which one is missing
1652 double startRange = nextT - priorT;
1653 FAIL_IF_COIN(!startRange, coin);
1654 double startPart = (test->t() - priorT) / startRange;
1655 double oStartRange = oNextT - oPriorT;
1656 FAIL_IF_COIN(!oStartRange, coin);
1657 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
1658 FAIL_IF_COIN(startPart == oStartPart, coin);
1659 bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
1660 : !!containedThis;
1661 bool startOver = false;
1662 addToOpp ? log->record(SkPathOpsDebug::kAddExpandedCoin_Glitch,
1663 oPriorT + oStartRange * startPart, test)
1664 : log->record(SkPathOpsDebug::kAddExpandedCoin_Glitch,
1665 priorT + startRange * oStartPart, oTest);
1666 // FAIL_IF_COIN(!success, coin);
1667 if (startOver) {
1668 test = start;
1669 oTest = oStart;
1670 }
1671 end = coin->coinPtTEnd()->span();
1672 oEnd = coin->oppPtTEnd()->span();
1673 }
1674 if (test != end) {
1675 FAIL_IF_COIN(!test->upCastable(), coin);
1676 priorT = test->t();
1677 test = test->upCast()->next();
1678 }
1679 if (oTest != oEnd) {
1680 oPriorT = oTest->t();
1681 oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
1682 FAIL_IF_COIN(!oTest, coin);
1683 }
1684 }
1685 } while ((coin = coin->next()));
1686 return;
1687 }
1688
1689 /* Commented-out lines keep this in sync addIfMissing() */
1690 // note that over1s, over1e, over2s, over2e are ordered
debugAddIfMissing(SkPathOpsDebug::GlitchLog * log,const SkOpPtT * over1s,const SkOpPtT * over2s,double tStart,double tEnd,const SkOpSegment * coinSeg,const SkOpSegment * oppSeg,bool * added,const SkOpPtT * over1e,const SkOpPtT * over2e) const1691 void SkOpCoincidence::debugAddIfMissing(SkPathOpsDebug::GlitchLog* log, const SkOpPtT* over1s, const SkOpPtT* over2s,
1692 double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added,
1693 const SkOpPtT* over1e, const SkOpPtT* over2e) const {
1694 SkASSERT(tStart < tEnd);
1695 SkASSERT(over1s->fT < over1e->fT);
1696 SkASSERT(between(over1s->fT, tStart, over1e->fT));
1697 SkASSERT(between(over1s->fT, tEnd, over1e->fT));
1698 SkASSERT(over2s->fT < over2e->fT);
1699 SkASSERT(between(over2s->fT, tStart, over2e->fT));
1700 SkASSERT(between(over2s->fT, tEnd, over2e->fT));
1701 SkASSERT(over1s->segment() == over1e->segment());
1702 SkASSERT(over2s->segment() == over2e->segment());
1703 SkASSERT(over1s->segment() == over2s->segment());
1704 SkASSERT(over1s->segment() != coinSeg);
1705 SkASSERT(over1s->segment() != oppSeg);
1706 SkASSERT(coinSeg != oppSeg);
1707 double coinTs, coinTe, oppTs, oppTe;
1708 coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e));
1709 coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e));
1710 SkOpSpanBase::Collapsed result = coinSeg->collapsed(coinTs, coinTe);
1711 if (SkOpSpanBase::Collapsed::kNo != result) {
1712 return log->record(SkPathOpsDebug::kAddIfCollapsed_Glitch, coinSeg);
1713 }
1714 oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e));
1715 oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e));
1716 result = oppSeg->collapsed(oppTs, oppTe);
1717 if (SkOpSpanBase::Collapsed::kNo != result) {
1718 return log->record(SkPathOpsDebug::kAddIfCollapsed_Glitch, oppSeg);
1719 }
1720 if (coinTs > coinTe) {
1721 using std::swap;
1722 swap(coinTs, coinTe);
1723 swap(oppTs, oppTe);
1724 }
1725 this->debugAddOrOverlap(log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added);
1726 return;
1727 }
1728
1729 /* Commented-out lines keep this in sync addOrOverlap() */
1730 // If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
1731 // If this is called by AddIfMissing(), a returned false indicates there was nothing to add
debugAddOrOverlap(SkPathOpsDebug::GlitchLog * log,const SkOpSegment * coinSeg,const SkOpSegment * oppSeg,double coinTs,double coinTe,double oppTs,double oppTe,bool * added) const1732 void SkOpCoincidence::debugAddOrOverlap(SkPathOpsDebug::GlitchLog* log,
1733 const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
1734 double coinTs, double coinTe, double oppTs, double oppTe, bool* added) const {
1735 SkTDArray<SkCoincidentSpans*> overlaps;
1736 SkOPASSERT(!fTop); // this is (correctly) reversed in addifMissing()
1737 if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe,
1738 &overlaps)) {
1739 return;
1740 }
1741 if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
1742 coinTe, oppTs, oppTe, &overlaps)) {
1743 return;
1744 }
1745 const SkCoincidentSpans* overlap = overlaps.size() ? overlaps[0] : nullptr;
1746 for (int index = 1; index < overlaps.size(); ++index) { // combine overlaps before continuing
1747 const SkCoincidentSpans* test = overlaps[index];
1748 if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
1749 log->record(SkPathOpsDebug::kAddOrOverlap_Glitch, overlap, test->coinPtTStart());
1750 }
1751 if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
1752 log->record(SkPathOpsDebug::kAddOrOverlap_Glitch, overlap, test->coinPtTEnd());
1753 }
1754 if (overlap->flipped()
1755 ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
1756 : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
1757 log->record(SkPathOpsDebug::kAddOrOverlap_Glitch, overlap, test->oppPtTStart());
1758 }
1759 if (overlap->flipped()
1760 ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
1761 : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
1762 log->record(SkPathOpsDebug::kAddOrOverlap_Glitch, overlap, test->oppPtTEnd());
1763 }
1764 if (!fHead) { this->debugRelease(log, fHead, test);
1765 this->debugRelease(log, fTop, test);
1766 }
1767 }
1768 const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
1769 const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
1770 RETURN_FALSE_IF(overlap && cs && ce && overlap->contains(cs, ce), coinSeg);
1771 RETURN_FALSE_IF(cs != ce || !cs, coinSeg);
1772 const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
1773 const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
1774 RETURN_FALSE_IF(overlap && os && oe && overlap->contains(os, oe), oppSeg);
1775 SkASSERT(true || !cs || !cs->deleted());
1776 SkASSERT(true || !os || !os->deleted());
1777 SkASSERT(true || !ce || !ce->deleted());
1778 SkASSERT(true || !oe || !oe->deleted());
1779 const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
1780 const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
1781 RETURN_FALSE_IF(csExisting && csExisting == ceExisting, coinSeg);
1782 RETURN_FALSE_IF(csExisting && (csExisting == ce ||
1783 csExisting->contains(ceExisting ? ceExisting : ce)), coinSeg);
1784 RETURN_FALSE_IF(ceExisting && (ceExisting == cs ||
1785 ceExisting->contains(csExisting ? csExisting : cs)), coinSeg);
1786 const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
1787 const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
1788 RETURN_FALSE_IF(osExisting && osExisting == oeExisting, oppSeg);
1789 RETURN_FALSE_IF(osExisting && (osExisting == oe ||
1790 osExisting->contains(oeExisting ? oeExisting : oe)), oppSeg);
1791 RETURN_FALSE_IF(oeExisting && (oeExisting == os ||
1792 oeExisting->contains(osExisting ? osExisting : os)), oppSeg);
1793 bool csDeleted = false, osDeleted = false, ceDeleted = false, oeDeleted = false;
1794 this->debugValidate();
1795 if (!cs || !os) {
1796 if (!cs)
1797 cs = coinSeg->debugAddT(coinTs, log);
1798 if (!os)
1799 os = oppSeg->debugAddT(oppTs, log);
1800 // RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable);
1801 if (cs && os) cs->span()->debugAddOpp(log, os->span());
1802 // cs = csWritable;
1803 // os = osWritable->active();
1804 RETURN_FALSE_IF((ce && ce->deleted()) || (oe && oe->deleted()), coinSeg);
1805 }
1806 if (!ce || !oe) {
1807 if (!ce)
1808 ce = coinSeg->debugAddT(coinTe, log);
1809 if (!oe)
1810 oe = oppSeg->debugAddT(oppTe, log);
1811 if (ce && oe) ce->span()->debugAddOpp(log, oe->span());
1812 // ce = ceWritable;
1813 // oe = oeWritable;
1814 }
1815 this->debugValidate();
1816 RETURN_FALSE_IF(csDeleted, coinSeg);
1817 RETURN_FALSE_IF(osDeleted, oppSeg);
1818 RETURN_FALSE_IF(ceDeleted, coinSeg);
1819 RETURN_FALSE_IF(oeDeleted, oppSeg);
1820 RETURN_FALSE_IF(!cs || !ce || cs == ce || cs->contains(ce) || !os || !oe || os == oe || os->contains(oe), coinSeg);
1821 bool result = true;
1822 if (overlap) {
1823 if (overlap->coinPtTStart()->segment() == coinSeg) {
1824 log->record(SkPathOpsDebug::kAddMissingExtend_Glitch, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
1825 } else {
1826 if (oppTs > oppTe) {
1827 using std::swap;
1828 swap(coinTs, coinTe);
1829 swap(oppTs, oppTe);
1830 }
1831 log->record(SkPathOpsDebug::kAddMissingExtend_Glitch, oppSeg, oppTs, oppTe, coinSeg, coinTs, coinTe);
1832 }
1833 #if 0 && DEBUG_COINCIDENCE_VERBOSE
1834 if (result) {
1835 overlap->debugShow();
1836 }
1837 #endif
1838 } else {
1839 log->record(SkPathOpsDebug::kAddMissingCoin_Glitch, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
1840 #if 0 && DEBUG_COINCIDENCE_VERBOSE
1841 fHead->debugShow();
1842 #endif
1843 }
1844 this->debugValidate();
1845 return (void) result;
1846 }
1847
1848 // Extra commented-out lines keep this in sync with addMissing()
1849 /* detects overlaps of different coincident runs on same segment */
1850 /* does not detect overlaps for pairs without any segments in common */
1851 // returns true if caller should loop again
debugAddMissing(SkPathOpsDebug::GlitchLog * log,bool * added) const1852 void SkOpCoincidence::debugAddMissing(SkPathOpsDebug::GlitchLog* log, bool* added) const {
1853 const SkCoincidentSpans* outer = fHead;
1854 *added = false;
1855 if (!outer) {
1856 return;
1857 }
1858 // fTop = outer;
1859 // fHead = nullptr;
1860 do {
1861 // addifmissing can modify the list that this is walking
1862 // save head so that walker can iterate over old data unperturbed
1863 // addifmissing adds to head freely then add saved head in the end
1864 const SkOpPtT* ocs = outer->coinPtTStart();
1865 SkASSERT(!ocs->deleted());
1866 const SkOpSegment* outerCoin = ocs->segment();
1867 SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list
1868 const SkOpPtT* oos = outer->oppPtTStart();
1869 if (oos->deleted()) {
1870 return;
1871 }
1872 const SkOpSegment* outerOpp = oos->segment();
1873 SkASSERT(!outerOpp->done());
1874 // SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
1875 // SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
1876 const SkCoincidentSpans* inner = outer;
1877 while ((inner = inner->next())) {
1878 this->debugValidate();
1879 double overS, overE;
1880 const SkOpPtT* ics = inner->coinPtTStart();
1881 SkASSERT(!ics->deleted());
1882 const SkOpSegment* innerCoin = ics->segment();
1883 SkASSERT(!innerCoin->done());
1884 const SkOpPtT* ios = inner->oppPtTStart();
1885 SkASSERT(!ios->deleted());
1886 const SkOpSegment* innerOpp = ios->segment();
1887 SkASSERT(!innerOpp->done());
1888 // SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
1889 // SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
1890 if (outerCoin == innerCoin) {
1891 const SkOpPtT* oce = outer->coinPtTEnd();
1892 if (oce->deleted()) {
1893 return;
1894 }
1895 const SkOpPtT* ice = inner->coinPtTEnd();
1896 SkASSERT(!ice->deleted());
1897 if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
1898 this->debugAddIfMissing(log, ocs->starter(oce), ics->starter(ice),
1899 overS, overE, outerOpp, innerOpp, added,
1900 ocs->debugEnder(oce),
1901 ics->debugEnder(ice));
1902 }
1903 } else if (outerCoin == innerOpp) {
1904 const SkOpPtT* oce = outer->coinPtTEnd();
1905 SkASSERT(!oce->deleted());
1906 const SkOpPtT* ioe = inner->oppPtTEnd();
1907 SkASSERT(!ioe->deleted());
1908 if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
1909 this->debugAddIfMissing(log, ocs->starter(oce), ios->starter(ioe),
1910 overS, overE, outerOpp, innerCoin, added,
1911 ocs->debugEnder(oce),
1912 ios->debugEnder(ioe));
1913 }
1914 } else if (outerOpp == innerCoin) {
1915 const SkOpPtT* ooe = outer->oppPtTEnd();
1916 SkASSERT(!ooe->deleted());
1917 const SkOpPtT* ice = inner->coinPtTEnd();
1918 SkASSERT(!ice->deleted());
1919 SkASSERT(outerCoin != innerOpp);
1920 if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
1921 this->debugAddIfMissing(log, oos->starter(ooe), ics->starter(ice),
1922 overS, overE, outerCoin, innerOpp, added,
1923 oos->debugEnder(ooe),
1924 ics->debugEnder(ice));
1925 }
1926 } else if (outerOpp == innerOpp) {
1927 const SkOpPtT* ooe = outer->oppPtTEnd();
1928 SkASSERT(!ooe->deleted());
1929 const SkOpPtT* ioe = inner->oppPtTEnd();
1930 if (ioe->deleted()) {
1931 return;
1932 }
1933 SkASSERT(outerCoin != innerCoin);
1934 if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
1935 this->debugAddIfMissing(log, oos->starter(ooe), ios->starter(ioe),
1936 overS, overE, outerCoin, innerCoin, added,
1937 oos->debugEnder(ooe),
1938 ios->debugEnder(ioe));
1939 }
1940 }
1941 this->debugValidate();
1942 }
1943 } while ((outer = outer->next()));
1944 // this->restoreHead();
1945 return;
1946 }
1947
1948 // Commented-out lines keep this in sync with release()
debugRelease(SkPathOpsDebug::GlitchLog * log,const SkCoincidentSpans * coin,const SkCoincidentSpans * remove) const1949 void SkOpCoincidence::debugRelease(SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkCoincidentSpans* remove) const {
1950 const SkCoincidentSpans* head = coin;
1951 const SkCoincidentSpans* prev = nullptr;
1952 const SkCoincidentSpans* next;
1953 do {
1954 next = coin->next();
1955 if (coin == remove) {
1956 if (prev) {
1957 // prev->setNext(next);
1958 } else if (head == fHead) {
1959 // fHead = next;
1960 } else {
1961 // fTop = next;
1962 }
1963 log->record(SkPathOpsDebug::kReleasedSpan_Glitch, coin);
1964 }
1965 prev = coin;
1966 } while ((coin = next));
1967 return;
1968 }
1969
debugRelease(SkPathOpsDebug::GlitchLog * log,const SkOpSegment * deleted) const1970 void SkOpCoincidence::debugRelease(SkPathOpsDebug::GlitchLog* log, const SkOpSegment* deleted) const {
1971 const SkCoincidentSpans* coin = fHead;
1972 if (!coin) {
1973 return;
1974 }
1975 do {
1976 if (coin->coinPtTStart()->segment() == deleted
1977 || coin->coinPtTEnd()->segment() == deleted
1978 || coin->oppPtTStart()->segment() == deleted
1979 || coin->oppPtTEnd()->segment() == deleted) {
1980 log->record(SkPathOpsDebug::kReleasedSpan_Glitch, coin);
1981 }
1982 } while ((coin = coin->next()));
1983 }
1984
1985 // Commented-out lines keep this in sync with expand()
1986 // expand the range by checking adjacent spans for coincidence
debugExpand(SkPathOpsDebug::GlitchLog * log) const1987 bool SkOpCoincidence::debugExpand(SkPathOpsDebug::GlitchLog* log) const {
1988 const SkCoincidentSpans* coin = fHead;
1989 if (!coin) {
1990 return false;
1991 }
1992 bool expanded = false;
1993 do {
1994 if (coin->debugExpand(log)) {
1995 // check to see if multiple spans expanded so they are now identical
1996 const SkCoincidentSpans* test = fHead;
1997 do {
1998 if (coin == test) {
1999 continue;
2000 }
2001 if (coin->coinPtTStart() == test->coinPtTStart()
2002 && coin->oppPtTStart() == test->oppPtTStart()) {
2003 if (log) log->record(SkPathOpsDebug::kExpandCoin_Glitch, fHead, test->coinPtTStart());
2004 break;
2005 }
2006 } while ((test = test->next()));
2007 expanded = true;
2008 }
2009 } while ((coin = coin->next()));
2010 return expanded;
2011 }
2012
2013 // Commented-out lines keep this in sync with mark()
2014 /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
debugMark(SkPathOpsDebug::GlitchLog * log) const2015 void SkOpCoincidence::debugMark(SkPathOpsDebug::GlitchLog* log) const {
2016 const SkCoincidentSpans* coin = fHead;
2017 if (!coin) {
2018 return;
2019 }
2020 do {
2021 FAIL_IF_COIN(!coin->coinPtTStartWritable()->span()->upCastable(), coin);
2022 const SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
2023 // SkASSERT(start->deleted());
2024 const SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
2025 // SkASSERT(end->deleted());
2026 const SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
2027 // SkASSERT(oStart->deleted());
2028 const SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
2029 // SkASSERT(oEnd->deleted());
2030 bool flipped = coin->flipped();
2031 if (flipped) {
2032 using std::swap;
2033 swap(oStart, oEnd);
2034 }
2035 /* coin and opp spans may not match up. Mark the ends, and then let the interior
2036 get marked as many times as the spans allow */
2037 start->debugInsertCoincidence(log, oStart->upCast());
2038 end->debugInsertCoinEnd(log, oEnd);
2039 const SkOpSegment* segment = start->segment();
2040 const SkOpSegment* oSegment = oStart->segment();
2041 const SkOpSpanBase* next = start;
2042 const SkOpSpanBase* oNext = oStart;
2043 bool ordered;
2044 FAIL_IF_COIN(!coin->ordered(&ordered), coin);
2045 while ((next = next->upCast()->next()) != end) {
2046 FAIL_IF_COIN(!next->upCastable(), coin);
2047 next->upCast()->debugInsertCoincidence(log, oSegment, flipped, ordered);
2048 }
2049 while ((oNext = oNext->upCast()->next()) != oEnd) {
2050 FAIL_IF_COIN(!oNext->upCastable(), coin);
2051 oNext->upCast()->debugInsertCoincidence(log, segment, flipped, ordered);
2052 }
2053 } while ((coin = coin->next()));
2054 return;
2055 }
2056 #endif // DEBUG_COIN
2057
2058 #if DEBUG_COIN
2059 // Commented-out lines keep this in sync with markCollapsed()
debugMarkCollapsed(SkPathOpsDebug::GlitchLog * log,const SkCoincidentSpans * coin,const SkOpPtT * test) const2060 void SkOpCoincidence::debugMarkCollapsed(SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkOpPtT* test) const {
2061 const SkCoincidentSpans* head = coin;
2062 while (coin) {
2063 if (coin->collapsed(test)) {
2064 if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
2065 log->record(SkPathOpsDebug::kCollapsedCoin_Glitch, coin);
2066 }
2067 if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
2068 log->record(SkPathOpsDebug::kCollapsedCoin_Glitch, coin);
2069 }
2070 this->debugRelease(log, head, coin);
2071 }
2072 coin = coin->next();
2073 }
2074 }
2075
2076 // Commented-out lines keep this in sync with markCollapsed()
debugMarkCollapsed(SkPathOpsDebug::GlitchLog * log,const SkOpPtT * test) const2077 void SkOpCoincidence::debugMarkCollapsed(SkPathOpsDebug::GlitchLog* log, const SkOpPtT* test) const {
2078 this->debugMarkCollapsed(log, fHead, test);
2079 this->debugMarkCollapsed(log, fTop, test);
2080 }
2081 #endif // DEBUG_COIN
2082
debugShow() const2083 void SkCoincidentSpans::debugShow() const {
2084 SkDebugf("coinSpan - id=%d t=%1.9g tEnd=%1.9g\n", coinPtTStart()->segment()->debugID(),
2085 coinPtTStart()->fT, coinPtTEnd()->fT);
2086 SkDebugf("coinSpan + id=%d t=%1.9g tEnd=%1.9g\n", oppPtTStart()->segment()->debugID(),
2087 oppPtTStart()->fT, oppPtTEnd()->fT);
2088 }
2089
debugShowCoincidence() const2090 void SkOpCoincidence::debugShowCoincidence() const {
2091 #if DEBUG_COINCIDENCE
2092 const SkCoincidentSpans* span = fHead;
2093 while (span) {
2094 span->debugShow();
2095 span = span->next();
2096 }
2097 #endif // DEBUG_COINCIDENCE
2098 }
2099
2100 #if DEBUG_COIN
DebugCheckBetween(const SkOpSpanBase * next,const SkOpSpanBase * end,double oStart,double oEnd,const SkOpSegment * oSegment,SkPathOpsDebug::GlitchLog * log)2101 static void DebugCheckBetween(const SkOpSpanBase* next, const SkOpSpanBase* end,
2102 double oStart, double oEnd, const SkOpSegment* oSegment,
2103 SkPathOpsDebug::GlitchLog* log) {
2104 SkASSERT(next != end);
2105 SkASSERT(!next->contains(end) || log);
2106 if (next->t() > end->t()) {
2107 using std::swap;
2108 swap(next, end);
2109 }
2110 do {
2111 const SkOpPtT* ptT = next->ptT();
2112 int index = 0;
2113 bool somethingBetween = false;
2114 do {
2115 ++index;
2116 ptT = ptT->next();
2117 const SkOpPtT* checkPtT = next->ptT();
2118 if (ptT == checkPtT) {
2119 break;
2120 }
2121 bool looped = false;
2122 for (int check = 0; check < index; ++check) {
2123 if ((looped = checkPtT == ptT)) {
2124 break;
2125 }
2126 checkPtT = checkPtT->next();
2127 }
2128 if (looped) {
2129 SkASSERT(0);
2130 break;
2131 }
2132 if (ptT->deleted()) {
2133 continue;
2134 }
2135 if (ptT->segment() != oSegment) {
2136 continue;
2137 }
2138 somethingBetween |= between(oStart, ptT->fT, oEnd);
2139 } while (true);
2140 SkASSERT(somethingBetween);
2141 } while (next != end && (next = next->upCast()->next()));
2142 }
2143
DebugCheckOverlap(const SkCoincidentSpans * test,const SkCoincidentSpans * list,SkPathOpsDebug::GlitchLog * log)2144 static void DebugCheckOverlap(const SkCoincidentSpans* test, const SkCoincidentSpans* list,
2145 SkPathOpsDebug::GlitchLog* log) {
2146 if (!list) {
2147 return;
2148 }
2149 const SkOpSegment* coinSeg = test->coinPtTStart()->segment();
2150 SkASSERT(coinSeg == test->coinPtTEnd()->segment());
2151 const SkOpSegment* oppSeg = test->oppPtTStart()->segment();
2152 SkASSERT(oppSeg == test->oppPtTEnd()->segment());
2153 SkASSERT(coinSeg != test->oppPtTStart()->segment());
2154 SkDEBUGCODE(double tcs = test->coinPtTStart()->fT);
2155 SkASSERT(between(0, tcs, 1));
2156 SkDEBUGCODE(double tce = test->coinPtTEnd()->fT);
2157 SkASSERT(between(0, tce, 1));
2158 SkASSERT(tcs < tce);
2159 double tos = test->oppPtTStart()->fT;
2160 SkASSERT(between(0, tos, 1));
2161 double toe = test->oppPtTEnd()->fT;
2162 SkASSERT(between(0, toe, 1));
2163 SkASSERT(tos != toe);
2164 if (tos > toe) {
2165 using std::swap;
2166 swap(tos, toe);
2167 }
2168 do {
2169 double lcs, lce, los, loe;
2170 if (coinSeg == list->coinPtTStart()->segment()) {
2171 if (oppSeg != list->oppPtTStart()->segment()) {
2172 continue;
2173 }
2174 lcs = list->coinPtTStart()->fT;
2175 lce = list->coinPtTEnd()->fT;
2176 los = list->oppPtTStart()->fT;
2177 loe = list->oppPtTEnd()->fT;
2178 if (los > loe) {
2179 using std::swap;
2180 swap(los, loe);
2181 }
2182 } else if (coinSeg == list->oppPtTStart()->segment()) {
2183 if (oppSeg != list->coinPtTStart()->segment()) {
2184 continue;
2185 }
2186 lcs = list->oppPtTStart()->fT;
2187 lce = list->oppPtTEnd()->fT;
2188 if (lcs > lce) {
2189 using std::swap;
2190 swap(lcs, lce);
2191 }
2192 los = list->coinPtTStart()->fT;
2193 loe = list->coinPtTEnd()->fT;
2194 } else {
2195 continue;
2196 }
2197 SkASSERT(tce < lcs || lce < tcs);
2198 SkASSERT(toe < los || loe < tos);
2199 } while ((list = list->next()));
2200 }
2201
2202
DebugCheckOverlapTop(const SkCoincidentSpans * head,const SkCoincidentSpans * opt,SkPathOpsDebug::GlitchLog * log)2203 static void DebugCheckOverlapTop(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
2204 SkPathOpsDebug::GlitchLog* log) {
2205 // check for overlapping coincident spans
2206 const SkCoincidentSpans* test = head;
2207 while (test) {
2208 const SkCoincidentSpans* next = test->next();
2209 DebugCheckOverlap(test, next, log);
2210 DebugCheckOverlap(test, opt, log);
2211 test = next;
2212 }
2213 }
2214
DebugValidate(const SkCoincidentSpans * head,const SkCoincidentSpans * opt,SkPathOpsDebug::GlitchLog * log)2215 static void DebugValidate(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
2216 SkPathOpsDebug::GlitchLog* log) {
2217 // look for pts inside coincident spans that are not inside the opposite spans
2218 const SkCoincidentSpans* coin = head;
2219 while (coin) {
2220 SkASSERT(SkOpCoincidence::Ordered(coin->coinPtTStart()->segment(),
2221 coin->oppPtTStart()->segment()));
2222 SkASSERT(coin->coinPtTStart()->span()->ptT() == coin->coinPtTStart());
2223 SkASSERT(coin->coinPtTEnd()->span()->ptT() == coin->coinPtTEnd());
2224 SkASSERT(coin->oppPtTStart()->span()->ptT() == coin->oppPtTStart());
2225 SkASSERT(coin->oppPtTEnd()->span()->ptT() == coin->oppPtTEnd());
2226 coin = coin->next();
2227 }
2228 DebugCheckOverlapTop(head, opt, log);
2229 }
2230 #endif // DEBUG_COIN
2231
debugValidate() const2232 void SkOpCoincidence::debugValidate() const {
2233 #if DEBUG_COINCIDENCE
2234 DebugValidate(fHead, fTop, nullptr);
2235 DebugValidate(fTop, nullptr, nullptr);
2236 #endif
2237 }
2238
2239 #if DEBUG_COIN
DebugCheckBetween(const SkCoincidentSpans * head,const SkCoincidentSpans * opt,SkPathOpsDebug::GlitchLog * log)2240 static void DebugCheckBetween(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
2241 SkPathOpsDebug::GlitchLog* log) {
2242 // look for pts inside coincident spans that are not inside the opposite spans
2243 const SkCoincidentSpans* coin = head;
2244 while (coin) {
2245 DebugCheckBetween(coin->coinPtTStart()->span(), coin->coinPtTEnd()->span(),
2246 coin->oppPtTStart()->fT, coin->oppPtTEnd()->fT, coin->oppPtTStart()->segment(),
2247 log);
2248 DebugCheckBetween(coin->oppPtTStart()->span(), coin->oppPtTEnd()->span(),
2249 coin->coinPtTStart()->fT, coin->coinPtTEnd()->fT, coin->coinPtTStart()->segment(),
2250 log);
2251 coin = coin->next();
2252 }
2253 DebugCheckOverlapTop(head, opt, log);
2254 }
2255 #endif
2256
debugCheckBetween() const2257 void SkOpCoincidence::debugCheckBetween() const {
2258 #if DEBUG_COINCIDENCE
2259 if (fGlobalState->debugCheckHealth()) {
2260 return;
2261 }
2262 DebugCheckBetween(fHead, fTop, nullptr);
2263 DebugCheckBetween(fTop, nullptr, nullptr);
2264 #endif
2265 }
2266
2267 #if DEBUG_COIN
debugCheckHealth(SkPathOpsDebug::GlitchLog * log) const2268 void SkOpContour::debugCheckHealth(SkPathOpsDebug::GlitchLog* log) const {
2269 const SkOpSegment* segment = &fHead;
2270 do {
2271 segment->debugCheckHealth(log);
2272 } while ((segment = segment->next()));
2273 }
2274
debugCheckValid(SkPathOpsDebug::GlitchLog * log) const2275 void SkOpCoincidence::debugCheckValid(SkPathOpsDebug::GlitchLog* log) const {
2276 #if DEBUG_VALIDATE
2277 DebugValidate(fHead, fTop, log);
2278 DebugValidate(fTop, nullptr, log);
2279 #endif
2280 }
2281
debugCorrectEnds(SkPathOpsDebug::GlitchLog * log) const2282 void SkOpCoincidence::debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const {
2283 const SkCoincidentSpans* coin = fHead;
2284 if (!coin) {
2285 return;
2286 }
2287 do {
2288 coin->debugCorrectEnds(log);
2289 } while ((coin = coin->next()));
2290 }
2291
2292 // commmented-out lines keep this aligned with missingCoincidence()
debugMissingCoincidence(SkPathOpsDebug::GlitchLog * log) const2293 void SkOpContour::debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const {
2294 // SkASSERT(fCount > 0);
2295 const SkOpSegment* segment = &fHead;
2296 // bool result = false;
2297 do {
2298 segment->debugMissingCoincidence(log);
2299 segment = segment->next();
2300 } while (segment);
2301 return;
2302 }
2303
debugMoveMultiples(SkPathOpsDebug::GlitchLog * log) const2304 void SkOpContour::debugMoveMultiples(SkPathOpsDebug::GlitchLog* log) const {
2305 SkASSERT(fCount > 0);
2306 const SkOpSegment* segment = &fHead;
2307 do {
2308 segment->debugMoveMultiples(log);
2309 } while ((segment = segment->next()));
2310 return;
2311 }
2312
debugMoveNearby(SkPathOpsDebug::GlitchLog * log) const2313 void SkOpContour::debugMoveNearby(SkPathOpsDebug::GlitchLog* log) const {
2314 SkASSERT(fCount > 0);
2315 const SkOpSegment* segment = &fHead;
2316 do {
2317 segment->debugMoveNearby(log);
2318 } while ((segment = segment->next()));
2319 }
2320 #endif
2321
2322 #if DEBUG_COINCIDENCE_ORDER
debugResetCoinT() const2323 void SkOpSegment::debugResetCoinT() const {
2324 fDebugBaseIndex = -1;
2325 fDebugBaseMin = 1;
2326 fDebugBaseMax = -1;
2327 fDebugLastIndex = -1;
2328 fDebugLastMin = 1;
2329 fDebugLastMax = -1;
2330 }
2331 #endif
2332
debugValidate() const2333 void SkOpSegment::debugValidate() const {
2334 #if DEBUG_COINCIDENCE_ORDER
2335 {
2336 const SkOpSpanBase* span = &fHead;
2337 do {
2338 span->debugResetCoinT();
2339 } while (!span->final() && (span = span->upCast()->next()));
2340 span = &fHead;
2341 int index = 0;
2342 do {
2343 span->debugSetCoinT(index++);
2344 } while (!span->final() && (span = span->upCast()->next()));
2345 }
2346 #endif
2347 #if DEBUG_COINCIDENCE
2348 if (this->globalState()->debugCheckHealth()) {
2349 return;
2350 }
2351 #endif
2352 #if DEBUG_VALIDATE
2353 const SkOpSpanBase* span = &fHead;
2354 double lastT = -1;
2355 const SkOpSpanBase* prev = nullptr;
2356 int count = 0;
2357 int done = 0;
2358 do {
2359 if (!span->final()) {
2360 ++count;
2361 done += span->upCast()->done() ? 1 : 0;
2362 }
2363 SkASSERT(span->segment() == this);
2364 SkASSERT(!prev || prev->upCast()->next() == span);
2365 SkASSERT(!prev || prev == span->prev());
2366 prev = span;
2367 double t = span->ptT()->fT;
2368 SkASSERT(lastT < t);
2369 lastT = t;
2370 span->debugValidate();
2371 } while (!span->final() && (span = span->upCast()->next()));
2372 SkASSERT(count == fCount);
2373 SkASSERT(done == fDoneCount);
2374 SkASSERT(count >= fDoneCount);
2375 SkASSERT(span->final());
2376 span->debugValidate();
2377 #endif
2378 }
2379
2380 #if DEBUG_COIN
2381
2382 // Commented-out lines keep this in sync with addOpp()
debugAddOpp(SkPathOpsDebug::GlitchLog * log,const SkOpSpanBase * opp) const2383 void SkOpSpanBase::debugAddOpp(SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const {
2384 const SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
2385 if (!oppPrev) {
2386 return;
2387 }
2388 this->debugMergeMatches(log, opp);
2389 this->ptT()->debugAddOpp(opp->ptT(), oppPrev);
2390 this->debugCheckForCollapsedCoincidence(log);
2391 }
2392
2393 // Commented-out lines keep this in sync with checkForCollapsedCoincidence()
debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog * log) const2394 void SkOpSpanBase::debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog* log) const {
2395 const SkOpCoincidence* coins = this->globalState()->coincidence();
2396 if (coins->isEmpty()) {
2397 return;
2398 }
2399 // the insert above may have put both ends of a coincident run in the same span
2400 // for each coincident ptT in loop; see if its opposite in is also in the loop
2401 // this implementation is the motivation for marking that a ptT is referenced by a coincident span
2402 const SkOpPtT* head = this->ptT();
2403 const SkOpPtT* test = head;
2404 do {
2405 if (!test->coincident()) {
2406 continue;
2407 }
2408 coins->debugMarkCollapsed(log, test);
2409 } while ((test = test->next()) != head);
2410 }
2411 #endif
2412
debugCoinEndLoopCheck() const2413 bool SkOpSpanBase::debugCoinEndLoopCheck() const {
2414 int loop = 0;
2415 const SkOpSpanBase* next = this;
2416 SkOpSpanBase* nextCoin;
2417 do {
2418 nextCoin = next->fCoinEnd;
2419 SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
2420 for (int check = 1; check < loop - 1; ++check) {
2421 const SkOpSpanBase* checkCoin = this->fCoinEnd;
2422 const SkOpSpanBase* innerCoin = checkCoin;
2423 for (int inner = check + 1; inner < loop; ++inner) {
2424 innerCoin = innerCoin->fCoinEnd;
2425 if (checkCoin == innerCoin) {
2426 SkDebugf("*** bad coincident end loop ***\n");
2427 return false;
2428 }
2429 }
2430 }
2431 ++loop;
2432 } while ((next = nextCoin) && next != this);
2433 return true;
2434 }
2435
2436 #if DEBUG_COIN
2437 // Commented-out lines keep this in sync with insertCoinEnd()
debugInsertCoinEnd(SkPathOpsDebug::GlitchLog * log,const SkOpSpanBase * coin) const2438 void SkOpSpanBase::debugInsertCoinEnd(SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* coin) const {
2439 if (containsCoinEnd(coin)) {
2440 // SkASSERT(coin->containsCoinEnd(this));
2441 return;
2442 }
2443 debugValidate();
2444 // SkASSERT(this != coin);
2445 log->record(SkPathOpsDebug::kMarkCoinEnd_Glitch, this, coin);
2446 // coin->fCoinEnd = this->fCoinEnd;
2447 // this->fCoinEnd = coinNext;
2448 debugValidate();
2449 }
2450
2451 // Commented-out lines keep this in sync with mergeMatches()
2452 // Look to see if pt-t linked list contains same segment more than once
2453 // if so, and if each pt-t is directly pointed to by spans in that segment,
2454 // merge them
2455 // keep the points, but remove spans so that the segment doesn't have 2 or more
2456 // spans pointing to the same pt-t loop at different loop elements
debugMergeMatches(SkPathOpsDebug::GlitchLog * log,const SkOpSpanBase * opp) const2457 void SkOpSpanBase::debugMergeMatches(SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const {
2458 const SkOpPtT* test = &fPtT;
2459 const SkOpPtT* testNext;
2460 const SkOpPtT* stop = test;
2461 do {
2462 testNext = test->next();
2463 if (test->deleted()) {
2464 continue;
2465 }
2466 const SkOpSpanBase* testBase = test->span();
2467 SkASSERT(testBase->ptT() == test);
2468 const SkOpSegment* segment = test->segment();
2469 if (segment->done()) {
2470 continue;
2471 }
2472 const SkOpPtT* inner = opp->ptT();
2473 const SkOpPtT* innerStop = inner;
2474 do {
2475 if (inner->segment() != segment) {
2476 continue;
2477 }
2478 if (inner->deleted()) {
2479 continue;
2480 }
2481 const SkOpSpanBase* innerBase = inner->span();
2482 SkASSERT(innerBase->ptT() == inner);
2483 // when the intersection is first detected, the span base is marked if there are
2484 // more than one point in the intersection.
2485 // if (!innerBase->hasMultipleHint() && !testBase->hasMultipleHint()) {
2486 if (!zero_or_one(inner->fT)) {
2487 log->record(SkPathOpsDebug::kMergeMatches_Glitch, innerBase, test);
2488 } else {
2489 SkASSERT(inner->fT != test->fT);
2490 if (!zero_or_one(test->fT)) {
2491 log->record(SkPathOpsDebug::kMergeMatches_Glitch, testBase, inner);
2492 } else {
2493 log->record(SkPathOpsDebug::kMergeMatches_Glitch, segment);
2494 // SkDEBUGCODE(testBase->debugSetDeleted());
2495 // test->setDeleted();
2496 // SkDEBUGCODE(innerBase->debugSetDeleted());
2497 // inner->setDeleted();
2498 }
2499 }
2500 #ifdef SK_DEBUG // assert if another undeleted entry points to segment
2501 const SkOpPtT* debugInner = inner;
2502 while ((debugInner = debugInner->next()) != innerStop) {
2503 if (debugInner->segment() != segment) {
2504 continue;
2505 }
2506 if (debugInner->deleted()) {
2507 continue;
2508 }
2509 SkOPASSERT(0);
2510 }
2511 #endif
2512 break;
2513 // }
2514 break;
2515 } while ((inner = inner->next()) != innerStop);
2516 } while ((test = testNext) != stop);
2517 this->debugCheckForCollapsedCoincidence(log);
2518 }
2519
2520 #endif
2521
debugResetCoinT() const2522 void SkOpSpanBase::debugResetCoinT() const {
2523 #if DEBUG_COINCIDENCE_ORDER
2524 const SkOpPtT* ptT = &fPtT;
2525 do {
2526 ptT->debugResetCoinT();
2527 ptT = ptT->next();
2528 } while (ptT != &fPtT);
2529 #endif
2530 }
2531
debugSetCoinT(int index) const2532 void SkOpSpanBase::debugSetCoinT(int index) const {
2533 #if DEBUG_COINCIDENCE_ORDER
2534 const SkOpPtT* ptT = &fPtT;
2535 do {
2536 if (!ptT->deleted()) {
2537 ptT->debugSetCoinT(index);
2538 }
2539 ptT = ptT->next();
2540 } while (ptT != &fPtT);
2541 #endif
2542 }
2543
debugStarter(SkOpSpanBase const ** endPtr) const2544 const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
2545 const SkOpSpanBase* end = *endPtr;
2546 SkASSERT(this->segment() == end->segment());
2547 const SkOpSpanBase* result;
2548 if (t() < end->t()) {
2549 result = this;
2550 } else {
2551 result = end;
2552 *endPtr = this;
2553 }
2554 return result->upCast();
2555 }
2556
debugValidate() const2557 void SkOpSpanBase::debugValidate() const {
2558 #if DEBUG_COINCIDENCE
2559 if (this->globalState()->debugCheckHealth()) {
2560 return;
2561 }
2562 #endif
2563 #if DEBUG_VALIDATE
2564 const SkOpPtT* ptT = &fPtT;
2565 SkASSERT(ptT->span() == this);
2566 do {
2567 // SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
2568 ptT->debugValidate();
2569 ptT = ptT->next();
2570 } while (ptT != &fPtT);
2571 SkASSERT(this->debugCoinEndLoopCheck());
2572 if (!this->final()) {
2573 SkASSERT(this->upCast()->debugCoinLoopCheck());
2574 }
2575 if (fFromAngle) {
2576 fFromAngle->debugValidate();
2577 }
2578 if (!this->final() && this->upCast()->toAngle()) {
2579 this->upCast()->toAngle()->debugValidate();
2580 }
2581 #endif
2582 }
2583
debugCoinLoopCheck() const2584 bool SkOpSpan::debugCoinLoopCheck() const {
2585 int loop = 0;
2586 const SkOpSpan* next = this;
2587 SkOpSpan* nextCoin;
2588 do {
2589 nextCoin = next->fCoincident;
2590 SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
2591 for (int check = 1; check < loop - 1; ++check) {
2592 const SkOpSpan* checkCoin = this->fCoincident;
2593 const SkOpSpan* innerCoin = checkCoin;
2594 for (int inner = check + 1; inner < loop; ++inner) {
2595 innerCoin = innerCoin->fCoincident;
2596 if (checkCoin == innerCoin) {
2597 SkDebugf("*** bad coincident loop ***\n");
2598 return false;
2599 }
2600 }
2601 }
2602 ++loop;
2603 } while ((next = nextCoin) && next != this);
2604 return true;
2605 }
2606
2607 #if DEBUG_COIN
2608 // Commented-out lines keep this in sync with insertCoincidence() in header
debugInsertCoincidence(SkPathOpsDebug::GlitchLog * log,const SkOpSpan * coin) const2609 void SkOpSpan::debugInsertCoincidence(SkPathOpsDebug::GlitchLog* log, const SkOpSpan* coin) const {
2610 if (containsCoincidence(coin)) {
2611 // SkASSERT(coin->containsCoincidence(this));
2612 return;
2613 }
2614 debugValidate();
2615 // SkASSERT(this != coin);
2616 log->record(SkPathOpsDebug::kMarkCoinStart_Glitch, this, coin);
2617 // coin->fCoincident = this->fCoincident;
2618 // this->fCoincident = coinNext;
2619 debugValidate();
2620 }
2621
2622 // Commented-out lines keep this in sync with insertCoincidence()
debugInsertCoincidence(SkPathOpsDebug::GlitchLog * log,const SkOpSegment * segment,bool flipped,bool ordered) const2623 void SkOpSpan::debugInsertCoincidence(SkPathOpsDebug::GlitchLog* log, const SkOpSegment* segment, bool flipped, bool ordered) const {
2624 if (this->containsCoincidence(segment)) {
2625 return;
2626 }
2627 const SkOpPtT* next = &fPtT;
2628 while ((next = next->next()) != &fPtT) {
2629 if (next->segment() == segment) {
2630 const SkOpSpan* span;
2631 const SkOpSpanBase* base = next->span();
2632 if (!ordered) {
2633 const SkOpSpanBase* spanEnd = fNext->contains(segment)->span();
2634 const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT());
2635 FAIL_IF_COIN(!start->span()->upCastable(), this);
2636 span = const_cast<SkOpSpan*>(start->span()->upCast());
2637 }
2638 else if (flipped) {
2639 span = base->prev();
2640 FAIL_IF_COIN(!span, this);
2641 }
2642 else {
2643 FAIL_IF_COIN(!base->upCastable(), this);
2644 span = base->upCast();
2645 }
2646 log->record(SkPathOpsDebug::kMarkCoinInsert_Glitch, span);
2647 return;
2648 }
2649 }
2650 log->record(SkPathOpsDebug::kMarkCoinMissing_Glitch, segment, this);
2651 return;
2652 }
2653 #endif // DEBUG_COIN
2654
2655 // called only by test code
debugCoincidentUsed() const2656 int SkIntersections::debugCoincidentUsed() const {
2657 if (!fIsCoincident[0]) {
2658 SkASSERT(!fIsCoincident[1]);
2659 return 0;
2660 }
2661 int count = 0;
2662 SkDEBUGCODE(int count2 = 0;)
2663 for (int index = 0; index < fUsed; ++index) {
2664 if (fIsCoincident[0] & (1 << index)) {
2665 ++count;
2666 }
2667 #ifdef SK_DEBUG
2668 if (fIsCoincident[1] & (1 << index)) {
2669 ++count2;
2670 }
2671 #endif
2672 }
2673 SkASSERT(count == count2);
2674 return count;
2675 }
2676
2677 // Commented-out lines keep this in sync with addOpp()
debugAddOpp(const SkOpPtT * opp,const SkOpPtT * oppPrev) const2678 void SkOpPtT::debugAddOpp(const SkOpPtT* opp, const SkOpPtT* oppPrev) const {
2679 SkDEBUGCODE(const SkOpPtT* oldNext = this->fNext);
2680 SkASSERT(this != opp);
2681 // this->fNext = opp;
2682 SkASSERT(oppPrev != oldNext);
2683 // oppPrev->fNext = oldNext;
2684 }
2685
debugContains(const SkOpPtT * check) const2686 bool SkOpPtT::debugContains(const SkOpPtT* check) const {
2687 SkASSERT(this != check);
2688 const SkOpPtT* ptT = this;
2689 int links = 0;
2690 do {
2691 ptT = ptT->next();
2692 if (ptT == check) {
2693 return true;
2694 }
2695 ++links;
2696 const SkOpPtT* test = this;
2697 for (int index = 0; index < links; ++index) {
2698 if (ptT == test) {
2699 return false;
2700 }
2701 test = test->next();
2702 }
2703 } while (true);
2704 }
2705
debugContains(const SkOpSegment * check) const2706 const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
2707 SkASSERT(this->segment() != check);
2708 const SkOpPtT* ptT = this;
2709 int links = 0;
2710 do {
2711 ptT = ptT->next();
2712 if (ptT->segment() == check) {
2713 return ptT;
2714 }
2715 ++links;
2716 const SkOpPtT* test = this;
2717 for (int index = 0; index < links; ++index) {
2718 if (ptT == test) {
2719 return nullptr;
2720 }
2721 test = test->next();
2722 }
2723 } while (true);
2724 }
2725
debugEnder(const SkOpPtT * end) const2726 const SkOpPtT* SkOpPtT::debugEnder(const SkOpPtT* end) const {
2727 return fT < end->fT ? end : this;
2728 }
2729
debugLoopLimit(bool report) const2730 int SkOpPtT::debugLoopLimit(bool report) const {
2731 int loop = 0;
2732 const SkOpPtT* next = this;
2733 do {
2734 for (int check = 1; check < loop - 1; ++check) {
2735 const SkOpPtT* checkPtT = this->fNext;
2736 const SkOpPtT* innerPtT = checkPtT;
2737 for (int inner = check + 1; inner < loop; ++inner) {
2738 innerPtT = innerPtT->fNext;
2739 if (checkPtT == innerPtT) {
2740 if (report) {
2741 SkDebugf("*** bad ptT loop ***\n");
2742 }
2743 return loop;
2744 }
2745 }
2746 }
2747 // there's nothing wrong with extremely large loop counts -- but this may appear to hang
2748 // by taking a very long time to figure out that no loop entry is a duplicate
2749 // -- and it's likely that a large loop count is indicative of a bug somewhere
2750 if (++loop > 1000) {
2751 SkDebugf("*** loop count exceeds 1000 ***\n");
2752 return 1000;
2753 }
2754 } while ((next = next->fNext) && next != this);
2755 return 0;
2756 }
2757
debugOppPrev(const SkOpPtT * opp) const2758 const SkOpPtT* SkOpPtT::debugOppPrev(const SkOpPtT* opp) const {
2759 return this->oppPrev(const_cast<SkOpPtT*>(opp));
2760 }
2761
debugResetCoinT() const2762 void SkOpPtT::debugResetCoinT() const {
2763 #if DEBUG_COINCIDENCE_ORDER
2764 this->segment()->debugResetCoinT();
2765 #endif
2766 }
2767
debugSetCoinT(int index) const2768 void SkOpPtT::debugSetCoinT(int index) const {
2769 #if DEBUG_COINCIDENCE_ORDER
2770 this->segment()->debugSetCoinT(index, fT);
2771 #endif
2772 }
2773
debugValidate() const2774 void SkOpPtT::debugValidate() const {
2775 #if DEBUG_COINCIDENCE
2776 if (this->globalState()->debugCheckHealth()) {
2777 return;
2778 }
2779 #endif
2780 #if DEBUG_VALIDATE
2781 SkOpPhase phase = contour()->globalState()->phase();
2782 if (phase == SkOpPhase::kIntersecting || phase == SkOpPhase::kFixWinding) {
2783 return;
2784 }
2785 SkASSERT(fNext);
2786 SkASSERT(fNext != this);
2787 SkASSERT(fNext->fNext);
2788 SkASSERT(debugLoopLimit(false) == 0);
2789 #endif
2790 }
2791
output_scalar(SkScalar num)2792 static void output_scalar(SkScalar num) {
2793 if (num == (int) num) {
2794 SkDebugf("%d", (int) num);
2795 } else {
2796 SkString str;
2797 str.printf("%1.9g", num);
2798 int width = (int) str.size();
2799 const char* cStr = str.c_str();
2800 while (cStr[width - 1] == '0') {
2801 --width;
2802 }
2803 str.resize(width);
2804 SkDebugf("%sf", str.c_str());
2805 }
2806 }
2807
output_points(const SkPoint * pts,int count)2808 static void output_points(const SkPoint* pts, int count) {
2809 for (int index = 0; index < count; ++index) {
2810 output_scalar(pts[index].fX);
2811 SkDebugf(", ");
2812 output_scalar(pts[index].fY);
2813 if (index + 1 < count) {
2814 SkDebugf(", ");
2815 }
2816 }
2817 }
2818
showPathContours(const SkPath & path,const char * pathName)2819 static void showPathContours(const SkPath& path, const char* pathName) {
2820 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
2821 switch (verb) {
2822 case SkPathVerb::kMove:
2823 SkDebugf(" %s.moveTo(", pathName);
2824 output_points(&pts[0], 1);
2825 SkDebugf(");\n");
2826 continue;
2827 case SkPathVerb::kLine:
2828 SkDebugf(" %s.lineTo(", pathName);
2829 output_points(&pts[1], 1);
2830 SkDebugf(");\n");
2831 break;
2832 case SkPathVerb::kQuad:
2833 SkDebugf(" %s.quadTo(", pathName);
2834 output_points(&pts[1], 2);
2835 SkDebugf(");\n");
2836 break;
2837 case SkPathVerb::kConic:
2838 SkDebugf(" %s.conicTo(", pathName);
2839 output_points(&pts[1], 2);
2840 SkDebugf(", %1.9gf);\n", *w);
2841 break;
2842 case SkPathVerb::kCubic:
2843 SkDebugf(" %s.cubicTo(", pathName);
2844 output_points(&pts[1], 3);
2845 SkDebugf(");\n");
2846 break;
2847 case SkPathVerb::kClose:
2848 SkDebugf(" %s.close();\n", pathName);
2849 break;
2850 default:
2851 SkDEBUGFAIL("bad verb");
2852 return;
2853 }
2854 }
2855 }
2856
2857 static const char* gFillTypeStr[] = {
2858 "kWinding",
2859 "kEvenOdd",
2860 "kInverseWinding",
2861 "kInverseEvenOdd"
2862 };
2863
ShowOnePath(const SkPath & path,const char * name,bool includeDeclaration)2864 void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
2865 #define SUPPORT_RECT_CONTOUR_DETECTION 0
2866 #if SUPPORT_RECT_CONTOUR_DETECTION
2867 int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0;
2868 if (rectCount > 0) {
2869 SkTDArray<SkRect> rects;
2870 SkTDArray<SkPathDirection> directions;
2871 rects.setCount(rectCount);
2872 directions.setCount(rectCount);
2873 path.rectContours(rects.begin(), directions.begin());
2874 for (int contour = 0; contour < rectCount; ++contour) {
2875 const SkRect& rect = rects[contour];
2876 SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
2877 rect.fRight, rect.fBottom, directions[contour] == SkPathDirection::kCCW
2878 ? "SkPathDirection::kCCW" : "SkPathDirection::kCW");
2879 }
2880 return;
2881 }
2882 #endif
2883 SkPathFillType fillType = path.getFillType();
2884 SkASSERT(fillType >= SkPathFillType::kWinding && fillType <= SkPathFillType::kInverseEvenOdd);
2885 if (includeDeclaration) {
2886 SkDebugf(" SkPath %s;\n", name);
2887 }
2888 SkDebugf(" %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[(int)fillType]);
2889 showPathContours(path, name);
2890 }
2891
2892 #if DEBUG_DUMP_VERIFY
2893 #include "include/core/SkData.h"
2894 #include "include/core/SkStream.h"
2895
dump_path(FILE * file,const SkPath & path,bool dumpAsHex)2896 static void dump_path(FILE* file, const SkPath& path, bool dumpAsHex) {
2897 SkDynamicMemoryWStream wStream;
2898 path.dump(&wStream, dumpAsHex);
2899 sk_sp<SkData> data(wStream.detachAsData());
2900 fprintf(file, "%.*s\n", (int) data->size(), (char*) data->data());
2901 }
2902
2903 static int dumpID = 0;
2904
DumpOp(const SkPath & one,const SkPath & two,SkPathOp op,const char * testName)2905 void DumpOp(const SkPath& one, const SkPath& two, SkPathOp op,
2906 const char* testName) {
2907 FILE* file = sk_fopen("op_dump.txt", kWrite_SkFILE_Flag);
2908 DumpOp(file, one, two, op, testName);
2909 }
2910
DumpOp(FILE * file,const SkPath & one,const SkPath & two,SkPathOp op,const char * testName)2911 void DumpOp(FILE* file, const SkPath& one, const SkPath& two, SkPathOp op,
2912 const char* testName) {
2913 const char* name = testName ? testName : "op";
2914 fprintf(file,
2915 "\nstatic void %s_%d(skiatest::Reporter* reporter, const char* filename) {\n",
2916 name, ++dumpID);
2917 fprintf(file, " SkPath path;\n");
2918 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", one.getFillType());
2919 dump_path(file, one, true);
2920 fprintf(file, " SkPath path1(path);\n");
2921 fprintf(file, " path.reset();\n");
2922 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", two.getFillType());
2923 dump_path(file, two, true);
2924 fprintf(file, " SkPath path2(path);\n");
2925 fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op);
2926 fprintf(file, "}\n\n");
2927 fclose(file);
2928 }
2929
DumpSimplify(const SkPath & path,const char * testName)2930 void DumpSimplify(const SkPath& path, const char* testName) {
2931 FILE* file = sk_fopen("simplify_dump.txt", kWrite_SkFILE_Flag);
2932 DumpSimplify(file, path, testName);
2933 }
2934
DumpSimplify(FILE * file,const SkPath & path,const char * testName)2935 void DumpSimplify(FILE* file, const SkPath& path, const char* testName) {
2936 const char* name = testName ? testName : "simplify";
2937 fprintf(file,
2938 "\nstatic void %s_%d(skiatest::Reporter* reporter, const char* filename) {\n",
2939 name, ++dumpID);
2940 fprintf(file, " SkPath path;\n");
2941 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", path.getFillType());
2942 dump_path(file, path, true);
2943 fprintf(file, " testSimplify(reporter, path, filename);\n");
2944 fprintf(file, "}\n\n");
2945 fclose(file);
2946 }
2947
2948 #include "include/core/SkBitmap.h"
2949 #include "include/core/SkCanvas.h"
2950 #include "include/core/SkPaint.h"
2951 #include "include/core/SkRegion.h"
2952
2953 const int bitWidth = 64;
2954 const int bitHeight = 64;
2955
debug_scale_matrix(const SkPath & one,const SkPath * two,SkMatrix & scale)2956 static void debug_scale_matrix(const SkPath& one, const SkPath* two, SkMatrix& scale) {
2957 SkRect larger = one.getBounds();
2958 if (two) {
2959 larger.join(two->getBounds());
2960 }
2961 SkScalar largerWidth = larger.width();
2962 if (largerWidth < 4) {
2963 largerWidth = 4;
2964 }
2965 SkScalar largerHeight = larger.height();
2966 if (largerHeight < 4) {
2967 largerHeight = 4;
2968 }
2969 SkScalar hScale = (bitWidth - 2) / largerWidth;
2970 SkScalar vScale = (bitHeight - 2) / largerHeight;
2971 scale.reset();
2972 scale.preScale(hScale, vScale);
2973 larger.fLeft *= hScale;
2974 larger.fRight *= hScale;
2975 larger.fTop *= vScale;
2976 larger.fBottom *= vScale;
2977 SkScalar dx = -16000 > larger.fLeft ? -16000 - larger.fLeft
2978 : 16000 < larger.fRight ? 16000 - larger.fRight : 0;
2979 SkScalar dy = -16000 > larger.fTop ? -16000 - larger.fTop
2980 : 16000 < larger.fBottom ? 16000 - larger.fBottom : 0;
2981 scale.preTranslate(dx, dy);
2982 }
2983
debug_paths_draw_the_same(const SkPath & one,const SkPath & two,SkBitmap & bits)2984 static int debug_paths_draw_the_same(const SkPath& one, const SkPath& two, SkBitmap& bits) {
2985 if (bits.width() == 0) {
2986 bits.allocN32Pixels(bitWidth * 2, bitHeight);
2987 }
2988 SkCanvas canvas(bits);
2989 canvas.drawColor(SK_ColorWHITE);
2990 SkPaint paint;
2991 canvas.save();
2992 const SkRect& bounds1 = one.getBounds();
2993 canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1);
2994 canvas.drawPath(one, paint);
2995 canvas.restore();
2996 canvas.save();
2997 canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1);
2998 canvas.drawPath(two, paint);
2999 canvas.restore();
3000 int errors = 0;
3001 for (int y = 0; y < bitHeight - 1; ++y) {
3002 uint32_t* addr1 = bits.getAddr32(0, y);
3003 uint32_t* addr2 = bits.getAddr32(0, y + 1);
3004 uint32_t* addr3 = bits.getAddr32(bitWidth, y);
3005 uint32_t* addr4 = bits.getAddr32(bitWidth, y + 1);
3006 for (int x = 0; x < bitWidth - 1; ++x) {
3007 // count 2x2 blocks
3008 bool err = addr1[x] != addr3[x];
3009 if (err) {
3010 errors += addr1[x + 1] != addr3[x + 1]
3011 && addr2[x] != addr4[x] && addr2[x + 1] != addr4[x + 1];
3012 }
3013 }
3014 }
3015 return errors;
3016 }
3017
ReportOpFail(const SkPath & one,const SkPath & two,SkPathOp op)3018 void ReportOpFail(const SkPath& one, const SkPath& two, SkPathOp op) {
3019 SkDebugf("// Op did not expect failure\n");
3020 DumpOp(stderr, one, two, op, "opTest");
3021 fflush(stderr);
3022 }
3023
VerifyOp(const SkPath & one,const SkPath & two,SkPathOp op,const SkPath & result)3024 void VerifyOp(const SkPath& one, const SkPath& two, SkPathOp op,
3025 const SkPath& result) {
3026 SkPath pathOut, scaledPathOut;
3027 SkRegion rgnA, rgnB, openClip, rgnOut;
3028 openClip.setRect({-16000, -16000, 16000, 16000});
3029 rgnA.setPath(one, openClip);
3030 rgnB.setPath(two, openClip);
3031 rgnOut.op(rgnA, rgnB, (SkRegion::Op) op);
3032 rgnOut.getBoundaryPath(&pathOut);
3033 SkMatrix scale;
3034 debug_scale_matrix(one, &two, scale);
3035 SkRegion scaledRgnA, scaledRgnB, scaledRgnOut;
3036 SkPath scaledA, scaledB;
3037 scaledA.addPath(one, scale);
3038 scaledA.setFillType(one.getFillType());
3039 scaledB.addPath(two, scale);
3040 scaledB.setFillType(two.getFillType());
3041 scaledRgnA.setPath(scaledA, openClip);
3042 scaledRgnB.setPath(scaledB, openClip);
3043 scaledRgnOut.op(scaledRgnA, scaledRgnB, (SkRegion::Op) op);
3044 scaledRgnOut.getBoundaryPath(&scaledPathOut);
3045 SkBitmap bitmap;
3046 SkPath scaledOut;
3047 scaledOut.addPath(result, scale);
3048 scaledOut.setFillType(result.getFillType());
3049 int errors = debug_paths_draw_the_same(scaledPathOut, scaledOut, bitmap);
3050 const int MAX_ERRORS = 9;
3051 if (errors > MAX_ERRORS) {
3052 fprintf(stderr, "// Op did not expect errors=%d\n", errors);
3053 DumpOp(stderr, one, two, op, "opTest");
3054 fflush(stderr);
3055 }
3056 }
3057
ReportSimplifyFail(const SkPath & path)3058 void ReportSimplifyFail(const SkPath& path) {
3059 SkDebugf("// Simplify did not expect failure\n");
3060 DumpSimplify(stderr, path, "simplifyTest");
3061 fflush(stderr);
3062 }
3063
VerifySimplify(const SkPath & path,const SkPath & result)3064 void VerifySimplify(const SkPath& path, const SkPath& result) {
3065 SkPath pathOut, scaledPathOut;
3066 SkRegion rgnA, openClip, rgnOut;
3067 openClip.setRect({-16000, -16000, 16000, 16000});
3068 rgnA.setPath(path, openClip);
3069 rgnOut.getBoundaryPath(&pathOut);
3070 SkMatrix scale;
3071 debug_scale_matrix(path, nullptr, scale);
3072 SkRegion scaledRgnA;
3073 SkPath scaledA;
3074 scaledA.addPath(path, scale);
3075 scaledA.setFillType(path.getFillType());
3076 scaledRgnA.setPath(scaledA, openClip);
3077 scaledRgnA.getBoundaryPath(&scaledPathOut);
3078 SkBitmap bitmap;
3079 SkPath scaledOut;
3080 scaledOut.addPath(result, scale);
3081 scaledOut.setFillType(result.getFillType());
3082 int errors = debug_paths_draw_the_same(scaledPathOut, scaledOut, bitmap);
3083 const int MAX_ERRORS = 9;
3084 if (errors > MAX_ERRORS) {
3085 fprintf(stderr, "// Simplify did not expect errors=%d\n", errors);
3086 DumpSimplify(stderr, path, "simplifyTest");
3087 fflush(stderr);
3088 }
3089 }
3090 #endif // DEBUG_DUMP_VERIFY
3091
3092 // global path dumps for msvs Visual Studio 17 to use from Immediate Window
Dump(const SkPath & path)3093 void Dump(const SkPath& path) {
3094 path.dump();
3095 }
3096
DumpHex(const SkPath & path)3097 void DumpHex(const SkPath& path) {
3098 path.dumpHex();
3099 }
3100