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