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