1 /*
2  * Copyright 2013 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #include "SkMutex.h"
9 #include "SkOpCoincidence.h"
10 #include "SkOpContour.h"
11 #include "SkPath.h"
12 #include "SkPathOpsDebug.h"
13 #include "SkString.h"
14 
15 struct SkCoincidentSpans;
16 
17 #if DEBUG_VALIDATE
18 extern bool FLAGS_runFail;
19 #endif
20 
21 #if DEBUG_SORT
22 int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
23 int SkPathOpsDebug::gSortCount;
24 #endif
25 
26 #if DEBUG_ACTIVE_OP
27 const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"};
28 #endif
29 
30 #if defined SK_DEBUG || !FORCE_RELEASE
31 
32 const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
33 
34 int SkPathOpsDebug::gContourID = 0;
35 int SkPathOpsDebug::gSegmentID = 0;
36 
ChaseContains(const SkTDArray<SkOpSpanBase * > & chaseArray,const SkOpSpanBase * span)37 bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray,
38         const SkOpSpanBase* span) {
39     for (int index = 0; index < chaseArray.count(); ++index) {
40         const SkOpSpanBase* entry = chaseArray[index];
41         if (entry == span) {
42             return true;
43         }
44     }
45     return false;
46 }
47 #endif
48 
49 #if DEBUG_COINCIDENCE
50 enum GlitchType {
51     kAddCorruptCoin_Glitch,
52     kAddExpandedCoin_Glitch,
53     kAddMissingCoin_Glitch,
54     kCollapsedCoin_Glitch,
55     kCollapsedDone_Glitch,
56     kCollapsedOppValue_Glitch,
57     kCollapsedSpan_Glitch,
58     kCollapsedWindValue_Glitch,
59     kDeletedCoin_Glitch,
60     kExpandCoin_Glitch,
61     kMarkCoinEnd_Glitch,
62     kMarkCoinInsert_Glitch,
63     kMissingCoin_Glitch,
64     kMissingDone_Glitch,
65     kMissingIntersection_Glitch,
66     kMoveMultiple_Glitch,
67     kUnaligned_Glitch,
68     kUnalignedHead_Glitch,
69     kUnalignedTail_Glitch,
70     kUndetachedSpan_Glitch,
71     kUnmergedSpan_Glitch,
72 };
73 
74 static const int kGlitchType_Count = kUnmergedSpan_Glitch + 1;
75 
76 struct SpanGlitch {
77     const char* fStage;
78     const SkOpSpanBase* fBase;
79     const SkOpSpanBase* fSuspect;
80     const SkCoincidentSpans* fCoin;
81     const SkOpSegment* fSegment;
82     const SkOpPtT* fCoinSpan;
83     const SkOpPtT* fEndSpan;
84     const SkOpPtT* fOppSpan;
85     const SkOpPtT* fOppEndSpan;
86     double fT;
87     SkPoint fPt;
88     GlitchType fType;
89 };
90 
91 struct SkPathOpsDebug::GlitchLog {
recordCommonSkPathOpsDebug::GlitchLog92     SpanGlitch* recordCommon(GlitchType type, const char* stage) {
93         SpanGlitch* glitch = fGlitches.push();
94         glitch->fStage = stage;
95         glitch->fBase = nullptr;
96         glitch->fSuspect = nullptr;
97         glitch->fCoin = nullptr;
98         glitch->fSegment = nullptr;
99         glitch->fCoinSpan = nullptr;
100         glitch->fEndSpan = nullptr;
101         glitch->fOppSpan = nullptr;
102         glitch->fOppEndSpan = nullptr;
103         glitch->fT = SK_ScalarNaN;
104         glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN };
105         glitch->fType = type;
106         return glitch;
107     }
108 
recordSkPathOpsDebug::GlitchLog109     void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
110             const SkOpSpanBase* suspect = NULL) {
111         SpanGlitch* glitch = recordCommon(type, stage);
112         glitch->fBase = base;
113         glitch->fSuspect = suspect;
114     }
115 
recordSkPathOpsDebug::GlitchLog116     void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
117             const SkOpPtT* coinSpan) {
118         SpanGlitch* glitch = recordCommon(type, stage);
119         glitch->fCoin = coin;
120         glitch->fCoinSpan = coinSpan;
121     }
122 
recordSkPathOpsDebug::GlitchLog123     void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
124             const SkOpSegment* seg, double t, SkPoint pt) {
125         SpanGlitch* glitch = recordCommon(type, stage);
126         glitch->fBase = base;
127         glitch->fSegment = seg;
128         glitch->fT = t;
129         glitch->fPt = pt;
130     }
131 
recordSkPathOpsDebug::GlitchLog132     void record(GlitchType type, const char* stage, const SkOpSpanBase* base, double t,
133             SkPoint pt) {
134         SpanGlitch* glitch = recordCommon(type, stage);
135         glitch->fBase = base;
136         glitch->fT = t;
137         glitch->fPt = pt;
138     }
139 
recordSkPathOpsDebug::GlitchLog140     void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
141             const SkOpPtT* coinSpan, const SkOpPtT* endSpan) {
142         SpanGlitch* glitch = recordCommon(type, stage);
143         glitch->fCoin = coin;
144         glitch->fCoinSpan = coinSpan;
145         glitch->fEndSpan = endSpan;
146     }
147 
recordSkPathOpsDebug::GlitchLog148     void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
149             const SkOpSpanBase* suspect) {
150         SpanGlitch* glitch = recordCommon(type, stage);
151         glitch->fSuspect = suspect;
152         glitch->fCoin = coin;
153     }
154 
recordSkPathOpsDebug::GlitchLog155     void record(GlitchType type, const char* stage, const SkOpPtT* ptTS, const SkOpPtT* ptTE,
156             const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) {
157         SpanGlitch* glitch = recordCommon(type, stage);
158         glitch->fCoinSpan = ptTS;
159         glitch->fEndSpan = ptTE;
160         glitch->fOppSpan = oPtTS;
161         glitch->fOppEndSpan = oPtTE;
162     }
163 
164     SkTDArray<SpanGlitch> fGlitches;
165 };
166 
CheckHealth(SkOpContourHead * contourList,const char * id)167 void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
168     GlitchLog glitches;
169     const SkOpContour* contour = contourList;
170     const SkOpCoincidence* coincidence = contour->globalState()->coincidence();
171     do {
172         contour->debugCheckHealth(id, &glitches);
173         contour->debugMissingCoincidence(id, &glitches, coincidence);
174     } while ((contour = contour->next()));
175     coincidence->debugFixAligned(id, &glitches);
176     coincidence->debugAddMissing(id, &glitches);
177     coincidence->debugExpand(id, &glitches);
178     coincidence->debugAddExpanded(id, &glitches);
179     coincidence->debugMark(id, &glitches);
180     unsigned mask = 0;
181     for (int index = 0; index < glitches.fGlitches.count(); ++index) {
182         const SpanGlitch& glitch = glitches.fGlitches[index];
183         mask |= 1 << glitch.fType;
184     }
185     for (int index = 0; index < kGlitchType_Count; ++index) {
186         SkDebugf(mask & (1 << index) ? "x" : "-");
187     }
188     SkDebugf("  %s\n", id);
189 }
190 #endif
191 
192 #if defined SK_DEBUG || !FORCE_RELEASE
MathematicaIze(char * str,size_t bufferLen)193 void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
194     size_t len = strlen(str);
195     bool num = false;
196     for (size_t idx = 0; idx < len; ++idx) {
197         if (num && str[idx] == 'e') {
198             if (len + 2 >= bufferLen) {
199                 return;
200             }
201             memmove(&str[idx + 2], &str[idx + 1], len - idx);
202             str[idx] = '*';
203             str[idx + 1] = '^';
204             ++len;
205         }
206         num = str[idx] >= '0' && str[idx] <= '9';
207     }
208 }
209 
ValidWind(int wind)210 bool SkPathOpsDebug::ValidWind(int wind) {
211     return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
212 }
213 
WindingPrintf(int wind)214 void SkPathOpsDebug::WindingPrintf(int wind) {
215     if (wind == SK_MinS32) {
216         SkDebugf("?");
217     } else {
218         SkDebugf("%d", wind);
219     }
220 }
221 #endif //  defined SK_DEBUG || !FORCE_RELEASE
222 
223 
224 #if DEBUG_SHOW_TEST_NAME
CreateNameStr()225 void* SkPathOpsDebug::CreateNameStr() { return new char[DEBUG_FILENAME_STRING_LENGTH]; }
226 
DeleteNameStr(void * v)227 void SkPathOpsDebug::DeleteNameStr(void* v) { delete[] reinterpret_cast<char*>(v); }
228 
BumpTestName(char * test)229 void SkPathOpsDebug::BumpTestName(char* test) {
230     char* num = test + strlen(test);
231     while (num[-1] >= '0' && num[-1] <= '9') {
232         --num;
233     }
234     if (num[0] == '\0') {
235         return;
236     }
237     int dec = atoi(num);
238     if (dec == 0) {
239         return;
240     }
241     ++dec;
242     SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
243 }
244 #endif
245 
show_function_header(const char * functionName)246 static void show_function_header(const char* functionName) {
247     SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName);
248     if (strcmp("skphealth_com76", functionName) == 0) {
249         SkDebugf("found it\n");
250     }
251 }
252 
253 static const char* gOpStrs[] = {
254     "kDifference_SkPathOp",
255     "kIntersect_SkPathOp",
256     "kUnion_SkPathOp",
257     "kXor_PathOp",
258     "kReverseDifference_SkPathOp",
259 };
260 
OpStr(SkPathOp op)261 const char* SkPathOpsDebug::OpStr(SkPathOp op) {
262     return gOpStrs[op];
263 }
264 
show_op(SkPathOp op,const char * pathOne,const char * pathTwo)265 static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) {
266     SkDebugf("    testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]);
267     SkDebugf("}\n");
268 }
269 
270 SK_DECLARE_STATIC_MUTEX(gTestMutex);
271 
ShowPath(const SkPath & a,const SkPath & b,SkPathOp shapeOp,const char * testName)272 void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
273         const char* testName) {
274     SkAutoMutexAcquire ac(gTestMutex);
275     show_function_header(testName);
276     ShowOnePath(a, "path", true);
277     ShowOnePath(b, "pathB", true);
278     show_op(shapeOp, "path", "pathB");
279 }
280 
281 #include "SkPathOpsTypes.h"
282 #include "SkIntersectionHelper.h"
283 #include "SkIntersections.h"
284 
285 #if DEBUG_T_SECT_LOOP_COUNT
debugAddLoopCount(SkIntersections * i,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn)286 void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt,
287         const SkIntersectionHelper& wn) {
288     for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
289         SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index;
290         if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) {
291             continue;
292         }
293         fDebugLoopCount[index] = i->debugLoopCount(looper);
294         fDebugWorstVerb[index * 2] = wt.segment()->verb();
295         fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb();
296         sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8);
297         memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(),
298                 (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint));
299         memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(),
300                 (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint));
301         fDebugWorstWeight[index * 2] = wt.weight();
302         fDebugWorstWeight[index * 2 + 1] = wn.weight();
303     }
304     i->debugResetLoopCount();
305 }
306 
debugDoYourWorst(SkOpGlobalState * local)307 void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) {
308     for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
309         if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) {
310             continue;
311         }
312         fDebugLoopCount[index] = local->fDebugLoopCount[index];
313         fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2];
314         fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1];
315         memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4],
316                 sizeof(SkPoint) * 8);
317         fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2];
318         fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1];
319     }
320     local->debugResetLoopCounts();
321 }
322 
dump_curve(SkPath::Verb verb,const SkPoint & pts,float weight)323 static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) {
324     if (!verb) {
325         return;
326     }
327     const char* verbs[] = { "", "line", "quad", "conic", "cubic" };
328     SkDebugf("%s: {{", verbs[verb]);
329     int ptCount = SkPathOpsVerbToPoints(verb);
330     for (int index = 0; index <= ptCount; ++index) {
331         SkDPoint::Dump((&pts)[index]);
332         if (index < ptCount - 1) {
333             SkDebugf(", ");
334         }
335     }
336     SkDebugf("}");
337     if (weight != 1) {
338         SkDebugf(", ");
339         if (weight == floorf(weight)) {
340             SkDebugf("%.0f", weight);
341         } else {
342             SkDebugf("%1.9gf", weight);
343         }
344     }
345     SkDebugf("}\n");
346 }
347 
debugLoopReport()348 void SkOpGlobalState::debugLoopReport() {
349     const char* loops[] = { "iterations", "coinChecks", "perpCalcs" };
350     SkDebugf("\n");
351     for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) {
352         SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]);
353         dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4],
354                 fDebugWorstWeight[index * 2]);
355         dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4],
356                 fDebugWorstWeight[index * 2 + 1]);
357     }
358 }
359 
debugResetLoopCounts()360 void SkOpGlobalState::debugResetLoopCounts() {
361     sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
362     sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb));
363     sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts));
364     sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight));
365 }
366 #endif
367 
368 #ifdef SK_DEBUG
debugRunFail() const369 bool SkOpGlobalState::debugRunFail() const {
370 #if DEBUG_VALIDATE
371     return FLAGS_runFail;
372 #else
373     return false;
374 #endif
375 }
376 #endif
377 
378 #if DEBUG_T_SECT_LOOP_COUNT
debugBumpLoopCount(DebugLoop index)379 void SkIntersections::debugBumpLoopCount(DebugLoop index) {
380     fDebugLoopCount[index]++;
381 }
382 
debugLoopCount(DebugLoop index) const383 int SkIntersections::debugLoopCount(DebugLoop index) const {
384     return fDebugLoopCount[index];
385 }
386 
debugResetLoopCount()387 void SkIntersections::debugResetLoopCount() {
388     sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
389 }
390 #endif
391 
392 #include "SkPathOpsCubic.h"
393 #include "SkPathOpsQuad.h"
394 
debugToCubic() const395 SkDCubic SkDQuad::debugToCubic() const {
396     SkDCubic cubic;
397     cubic[0] = fPts[0];
398     cubic[2] = fPts[1];
399     cubic[3] = fPts[2];
400     cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3;
401     cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3;
402     cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3;
403     cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3;
404     return cubic;
405 }
406 
debugInit()407 void SkDRect::debugInit() {
408     fLeft = fTop = fRight = fBottom = SK_ScalarNaN;
409 }
410 
411 #include "SkOpAngle.h"
412 #include "SkOpSegment.h"
413 
414 #if DEBUG_COINCIDENCE
debugAddAlignIntersection(const char * id,SkPathOpsDebug::GlitchLog * log,const SkOpPtT & endPtT,const SkPoint & oldPt,const SkOpContourHead * contourList) const415 void SkOpSegment::debugAddAlignIntersection(const char* id, SkPathOpsDebug::GlitchLog* log,
416         const SkOpPtT& endPtT, const SkPoint& oldPt,  const SkOpContourHead* contourList) const {
417     const SkPoint& newPt = endPtT.fPt;
418     if (newPt == oldPt) {
419         return;
420     }
421     SkPoint line[2] = { newPt, oldPt };
422     SkPathOpsBounds lineBounds;
423     lineBounds.setBounds(line, 2);
424     SkDLine aLine;
425     aLine.set(line);
426     const SkOpContour* current = contourList;
427     do {
428         if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) {
429             continue;
430         }
431         const SkOpSegment* segment = current->first();
432         do {
433             if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) {
434                 continue;
435             }
436             if (newPt == segment->fPts[0]) {
437                 continue;
438             }
439             if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
440                 continue;
441             }
442             if (oldPt == segment->fPts[0]) {
443                 continue;
444             }
445             if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
446                 continue;
447             }
448             if (endPtT.debugContains(segment)) {
449                 continue;
450             }
451             SkIntersections i;
452             switch (segment->fVerb) {
453                 case SkPath::kLine_Verb: {
454                     SkDLine bLine;
455                     bLine.set(segment->fPts);
456                     i.intersect(bLine, aLine);
457                     } break;
458                 case SkPath::kQuad_Verb: {
459                     SkDQuad bQuad;
460                     bQuad.set(segment->fPts);
461                     i.intersect(bQuad, aLine);
462                     } break;
463                 case SkPath::kConic_Verb: {
464                     SkDConic bConic;
465                     bConic.set(segment->fPts, segment->fWeight);
466                     i.intersect(bConic, aLine);
467                     } break;
468                 case SkPath::kCubic_Verb: {
469                     SkDCubic bCubic;
470                     bCubic.set(segment->fPts);
471                     i.intersect(bCubic, aLine);
472                     } break;
473                 default:
474                     SkASSERT(0);
475             }
476             if (i.used()) {
477                 SkASSERT(i.used() == 1);
478                 SkASSERT(!zero_or_one(i[0][0]));
479                 SkOpSpanBase* checkSpan = fHead.next();
480                 while (!checkSpan->final()) {
481                     if (checkSpan->contains(segment)) {
482                         goto nextSegment;
483                     }
484                     checkSpan = checkSpan->upCast()->next();
485                 }
486                 log->record(kMissingIntersection_Glitch, id, checkSpan, segment, i[0][0], newPt);
487             }
488     nextSegment:
489             ;
490         } while ((segment = segment->next()));
491     } while ((current = current->next()));
492 }
493 
debugAddMissing(double t,const SkOpSegment * opp) const494 bool SkOpSegment::debugAddMissing(double t, const SkOpSegment* opp) const {
495     const SkOpSpanBase* existing = nullptr;
496     const SkOpSpanBase* test = &fHead;
497     double testT;
498     do {
499         if ((testT = test->ptT()->fT) >= t) {
500             if (testT == t) {
501                 existing = test;
502             }
503             break;
504         }
505     } while ((test = test->upCast()->next()));
506     return !existing || !existing->debugContains(opp);
507 }
508 
debugAlign(const char * id,SkPathOpsDebug::GlitchLog * glitches) const509 void SkOpSegment::debugAlign(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
510     const SkOpSpanBase* span = &fHead;
511     if (!span->aligned()) {
512         if (!span->debugAlignedEnd(0, fPts[0])) {
513             glitches->record(kUnalignedHead_Glitch, id, span);
514         }
515     }
516     while ((span = span->upCast()->next())) {
517         if (span == &fTail) {
518             break;
519         }
520         if (!span->aligned()) {
521             glitches->record(kUnaligned_Glitch, id, span);
522         }
523     }
524     if (!span->aligned()) {
525         span->debugAlignedEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]);
526     }
527     if (this->collapsed()) {
528         const SkOpSpan* span = &fHead;
529         do {
530             if (span->windValue()) {
531                 glitches->record(kCollapsedWindValue_Glitch, id, span);
532             }
533             if (span->oppValue()) {
534                 glitches->record(kCollapsedOppValue_Glitch, id, span);
535             }
536             if (!span->done()) {
537                 glitches->record(kCollapsedDone_Glitch, id, span);
538             }
539         } while ((span = span->next()->upCastable()));
540     }
541 }
542 #endif
543 
544 #if DEBUG_ANGLE
debugCheckAngleCoin() const545 void SkOpSegment::debugCheckAngleCoin() const {
546     const SkOpSpanBase* base = &fHead;
547     const SkOpSpan* span;
548     do {
549         const SkOpAngle* angle = base->fromAngle();
550         if (angle && angle->fCheckCoincidence) {
551             angle->debugCheckNearCoincidence();
552         }
553         if (base->final()) {
554              break;
555         }
556         span = base->upCast();
557         angle = span->toAngle();
558         if (angle && angle->fCheckCoincidence) {
559             angle->debugCheckNearCoincidence();
560         }
561     } while ((base = span->next()));
562 }
563 #endif
564 
565 #if DEBUG_COINCIDENCE
566 // this mimics the order of the checks in handle coincidence
debugCheckHealth(const char * id,SkPathOpsDebug::GlitchLog * glitches) const567 void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
568     debugMoveMultiples(id, glitches);
569     debugFindCollapsed(id, glitches);
570     debugMoveNearby(id, glitches);
571     debugAlign(id, glitches);
572     debugAddAlignIntersections(id, glitches, this->globalState()->contourHead());
573 
574 }
575 
debugFindCollapsed(const char * id,SkPathOpsDebug::GlitchLog * glitches) const576 void SkOpSegment::debugFindCollapsed(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
577     if (fHead.contains(&fTail)) {
578         const SkOpSpan* span = this->head();
579         bool missingDone = false;
580         do {
581             missingDone |= !span->done();
582         } while ((span = span->next()->upCastable()));
583         if (missingDone) {
584             glitches->record(kMissingDone_Glitch, id, &fHead);
585         }
586         if (!fHead.debugAlignedEnd(0, fHead.pt())) {
587             glitches->record(kUnalignedHead_Glitch, id, &fHead);
588         }
589         if (!fTail.aligned()) {
590             glitches->record(kUnalignedTail_Glitch, id, &fTail);
591         }
592     }
593 }
594 #endif
595 
debugLastAngle()596 SkOpAngle* SkOpSegment::debugLastAngle() {
597     SkOpAngle* result = nullptr;
598     SkOpSpan* span = this->head();
599     do {
600         if (span->toAngle()) {
601             SkASSERT(!result);
602             result = span->toAngle();
603         }
604     } while ((span = span->next()->upCastable()));
605     SkASSERT(result);
606     return result;
607 }
608 
609 #if DEBUG_COINCIDENCE
debugMissingCoincidence(const char * id,SkPathOpsDebug::GlitchLog * log,const SkOpCoincidence * coincidences) const610 void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
611         const SkOpCoincidence* coincidences) const {
612     if (this->verb() != SkPath::kLine_Verb) {
613         return;
614     }
615     if (this->done()) {
616         return;
617     }
618     const SkOpSpan* prior = nullptr;
619     const SkOpSpanBase* spanBase = &fHead;
620     do {
621         const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
622         SkASSERT(ptT->span() == spanBase);
623         while ((ptT = ptT->next()) != spanStopPtT) {
624             if (ptT->deleted()) {
625                 continue;
626             }
627             SkOpSegment* opp = ptT->span()->segment();
628 //            if (opp->verb() == SkPath::kLine_Verb) {
629 //                continue;
630 //            }
631             if (opp->done()) {
632                 continue;
633             }
634             // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
635             if (!opp->visited()) {
636                 continue;
637             }
638             if (spanBase == &fHead) {
639                 continue;
640             }
641             const SkOpSpan* span = spanBase->upCastable();
642             // FIXME?: this assumes that if the opposite segment is coincident then no more
643             // coincidence needs to be detected. This may not be true.
644             if (span && span->segment() != opp && span->containsCoincidence(opp)) {
645                 continue;
646             }
647             if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) {
648                 continue;
649             }
650             const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
651             // find prior span containing opp segment
652             const SkOpSegment* priorOpp = nullptr;
653             const SkOpSpan* priorTest = spanBase->prev();
654             while (!priorOpp && priorTest) {
655                 priorStopPtT = priorPtT = priorTest->ptT();
656                 while ((priorPtT = priorPtT->next()) != priorStopPtT) {
657                     if (priorPtT->deleted()) {
658                         continue;
659                     }
660                     SkOpSegment* segment = priorPtT->span()->segment();
661                     if (segment == opp) {
662                         prior = priorTest;
663                         priorOpp = opp;
664                         break;
665                     }
666                 }
667                 priorTest = priorTest->prev();
668             }
669             if (!priorOpp) {
670                 continue;
671             }
672             const SkOpPtT* oppStart = prior->ptT();
673             const SkOpPtT* oppEnd = spanBase->ptT();
674             bool swapped = priorPtT->fT > ptT->fT;
675             if (swapped) {
676                 SkTSwap(priorPtT, ptT);
677                 SkTSwap(oppStart, oppEnd);
678             }
679             bool flipped = oppStart->fT > oppEnd->fT;
680             bool coincident = false;
681             if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
682                 goto swapBack;
683             }
684             if (opp->verb() == SkPath::kLine_Verb) {
685                 coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) ||
686                         SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) &&
687                         (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) ||
688                         SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt));
689             }
690             if (!coincident) {
691                 coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000);
692             }
693             if (coincident) {
694                 log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd);
695             }
696     swapBack:
697             if (swapped) {
698                 SkTSwap(priorPtT, ptT);
699             }
700         }
701     } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
702 }
703 
debugMoveMultiples(const char * id,SkPathOpsDebug::GlitchLog * glitches) const704 void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
705     const SkOpSpanBase* test = &fHead;
706     do {
707         int addCount = test->spanAddsCount();
708         SkASSERT(addCount >= 1);
709         if (addCount == 1) {
710             continue;
711         }
712         const SkOpPtT* startPtT = test->ptT();
713         const SkOpPtT* testPtT = startPtT;
714         do {  // iterate through all spans associated with start
715             const SkOpSpanBase* oppSpan = testPtT->span();
716             if (oppSpan->spanAddsCount() == addCount) {
717                 continue;
718             }
719             if (oppSpan->deleted()) {
720                 continue;
721             }
722             const SkOpSegment* oppSegment = oppSpan->segment();
723             if (oppSegment == this) {
724                 continue;
725             }
726             // find range of spans to consider merging
727             const SkOpSpanBase* oppPrev = oppSpan;
728             const SkOpSpanBase* oppFirst = oppSpan;
729             while ((oppPrev = oppPrev->prev())) {
730                 if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
731                     break;
732                 }
733                 if (oppPrev->spanAddsCount() == addCount) {
734                     continue;
735                 }
736                 if (oppPrev->deleted()) {
737                     continue;
738                 }
739                 oppFirst = oppPrev;
740             }
741             const SkOpSpanBase* oppNext = oppSpan;
742             const SkOpSpanBase* oppLast = oppSpan;
743             while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
744                 if (!roughly_equal(oppNext->t(), oppSpan->t())) {
745                     break;
746                 }
747                 if (oppNext->spanAddsCount() == addCount) {
748                     continue;
749                 }
750                 if (oppNext->deleted()) {
751                     continue;
752                 }
753                 oppLast = oppNext;
754             }
755             if (oppFirst == oppLast) {
756                 continue;
757             }
758             const SkOpSpanBase* oppTest = oppFirst;
759             do {
760                 if (oppTest == oppSpan) {
761                     continue;
762                 }
763                 // check to see if the candidate meets specific criteria:
764                 // it contains spans of segments in test's loop but not including 'this'
765                 const SkOpPtT* oppStartPtT = oppTest->ptT();
766                 const SkOpPtT* oppPtT = oppStartPtT;
767                 while ((oppPtT = oppPtT->next()) != oppStartPtT) {
768                     const SkOpSegment* oppPtTSegment = oppPtT->segment();
769                     if (oppPtTSegment == this) {
770                         goto tryNextSpan;
771                     }
772                     const SkOpPtT* matchPtT = startPtT;
773                     do {
774                         if (matchPtT->segment() == oppPtTSegment) {
775                             goto foundMatch;
776                         }
777                     } while ((matchPtT = matchPtT->next()) != startPtT);
778                     goto tryNextSpan;
779             foundMatch:  // merge oppTest and oppSpan
780                     if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) {
781                         SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse
782                         SkASSERT(oppSpan != &oppSegment->fTail);
783                         glitches->record(kMoveMultiple_Glitch, id, oppTest, oppSpan);
784                     } else {
785                         glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest);
786                     }
787                     goto checkNextSpan;
788                 }
789         tryNextSpan:
790                 ;
791             } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
792         } while ((testPtT = testPtT->next()) != startPtT);
793 checkNextSpan:
794         ;
795     } while ((test = test->final() ? nullptr : test->upCast()->next()));
796 }
797 
debugMoveNearby(const char * id,SkPathOpsDebug::GlitchLog * glitches) const798 void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
799         const SkOpSpanBase* spanS = &fHead;
800     do {
801         const SkOpSpanBase* test = spanS->upCast()->next();
802         const SkOpSpanBase* next;
803         if (spanS->contains(test)) {
804             if (!test->final()) {
805                 glitches->record(kUndetachedSpan_Glitch, id, test, spanS);
806             } else if (spanS != &fHead) {
807                 glitches->record(kUndetachedSpan_Glitch, id, spanS, test);
808             }
809         }
810         do {  // iterate through all spans associated with start
811             const SkOpPtT* startBase = spanS->ptT();
812             next = test->final() ? nullptr : test->upCast()->next();
813             do {
814                 const SkOpPtT* testBase = test->ptT();
815                 do {
816                     if (startBase == testBase) {
817                         goto checkNextSpan;
818                     }
819                     if (testBase->duplicate()) {
820                         continue;
821                     }
822                     if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) {
823                         if (test == &this->fTail) {
824                             if (spanS == &fHead) {
825                                 glitches->record(kCollapsedSpan_Glitch, id, spanS);
826                             } else {
827                                 glitches->record(kUnmergedSpan_Glitch, id, &this->fTail, spanS);
828                             }
829                         } else {
830                             glitches->record(kUnmergedSpan_Glitch, id, spanS, test);
831                             goto checkNextSpan;
832                         }
833                     }
834                 } while ((testBase = testBase->next()) != test->ptT());
835             } while ((startBase = startBase->next()) != spanS->ptT());
836     checkNextSpan:
837             ;
838         } while ((test = next));
839         spanS = spanS->upCast()->next();
840     } while (!spanS->final());
841 }
842 #endif
843 
debugReset()844 void SkOpSegment::debugReset() {
845     this->init(this->fPts, this->fWeight, this->contour(), this->verb());
846 }
847 
848 #if DEBUG_ACTIVE_SPANS
debugShowActiveSpans() const849 void SkOpSegment::debugShowActiveSpans() const {
850     debugValidate();
851     if (done()) {
852         return;
853     }
854     int lastId = -1;
855     double lastT = -1;
856     const SkOpSpan* span = &fHead;
857     do {
858         if (span->done()) {
859             continue;
860         }
861         if (lastId == this->debugID() && lastT == span->t()) {
862             continue;
863         }
864         lastId = this->debugID();
865         lastT = span->t();
866         SkDebugf("%s id=%d", __FUNCTION__, this->debugID());
867         SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
868         for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
869             SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
870         }
871         if (SkPath::kConic_Verb == fVerb) {
872             SkDebugf(" %1.9gf", fWeight);
873         }
874         const SkOpPtT* ptT = span->ptT();
875         SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY);
876         SkDebugf(" tEnd=%1.9g", span->next()->t());
877         if (span->windSum() == SK_MinS32) {
878             SkDebugf(" windSum=?");
879         } else {
880             SkDebugf(" windSum=%d", span->windSum());
881         }
882         if (span->oppValue() && span->oppSum() == SK_MinS32) {
883             SkDebugf(" oppSum=?");
884         } else if (span->oppValue() || span->oppSum() != SK_MinS32) {
885             SkDebugf(" oppSum=%d", span->oppSum());
886         }
887         SkDebugf(" windValue=%d", span->windValue());
888         if (span->oppValue() || span->oppSum() != SK_MinS32) {
889             SkDebugf(" oppValue=%d", span->oppValue());
890         }
891         SkDebugf("\n");
892    } while ((span = span->next()->upCastable()));
893 }
894 #endif
895 
896 #if DEBUG_MARK_DONE
debugShowNewWinding(const char * fun,const SkOpSpan * span,int winding)897 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
898     const SkPoint& pt = span->ptT()->fPt;
899     SkDebugf("%s id=%d", fun, this->debugID());
900     SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
901     for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
902         SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
903     }
904     SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
905             span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t());
906     if (winding == SK_MinS32) {
907         SkDebugf("?");
908     } else {
909         SkDebugf("%d", winding);
910     }
911     SkDebugf(" windSum=");
912     if (span->windSum() == SK_MinS32) {
913         SkDebugf("?");
914     } else {
915         SkDebugf("%d", span->windSum());
916     }
917     SkDebugf(" windValue=%d\n", span->windValue());
918 }
919 
debugShowNewWinding(const char * fun,const SkOpSpan * span,int winding,int oppWinding)920 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
921                                       int oppWinding) {
922     const SkPoint& pt = span->ptT()->fPt;
923     SkDebugf("%s id=%d", fun, this->debugID());
924     SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
925     for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
926         SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
927     }
928     SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=",
929             span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding);
930     if (winding == SK_MinS32) {
931         SkDebugf("?");
932     } else {
933         SkDebugf("%d", winding);
934     }
935     SkDebugf(" newOppSum=");
936     if (oppWinding == SK_MinS32) {
937         SkDebugf("?");
938     } else {
939         SkDebugf("%d", oppWinding);
940     }
941     SkDebugf(" oppSum=");
942     if (span->oppSum() == SK_MinS32) {
943         SkDebugf("?");
944     } else {
945         SkDebugf("%d", span->oppSum());
946     }
947     SkDebugf(" windSum=");
948     if (span->windSum() == SK_MinS32) {
949         SkDebugf("?");
950     } else {
951         SkDebugf("%d", span->windSum());
952     }
953     SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue());
954 }
955 
956 #endif
957 
958 // loop looking for a pair of angle parts that are too close to be sorted
959 /* This is called after other more simple intersection and angle sorting tests have been exhausted.
960    This should be rarely called -- the test below is thorough and time consuming.
961    This checks the distance between start points; the distance between
962 */
963 #if DEBUG_ANGLE
debugCheckNearCoincidence() const964 void SkOpAngle::debugCheckNearCoincidence() const {
965     const SkOpAngle* test = this;
966     do {
967         const SkOpSegment* testSegment = test->segment();
968         double testStartT = test->start()->t();
969         SkDPoint testStartPt = testSegment->dPtAtT(testStartT);
970         double testEndT = test->end()->t();
971         SkDPoint testEndPt = testSegment->dPtAtT(testEndT);
972         double testLenSq = testStartPt.distanceSquared(testEndPt);
973         SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID());
974         double testMidT = (testStartT + testEndT) / 2;
975         const SkOpAngle* next = test;
976         while ((next = next->fNext) != this) {
977             SkOpSegment* nextSegment = next->segment();
978             double testMidDistSq = testSegment->distSq(testMidT, next);
979             double testEndDistSq = testSegment->distSq(testEndT, next);
980             double nextStartT = next->start()->t();
981             SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT);
982             double distSq = testStartPt.distanceSquared(nextStartPt);
983             double nextEndT = next->end()->t();
984             double nextMidT = (nextStartT + nextEndT) / 2;
985             double nextMidDistSq = nextSegment->distSq(nextMidT, test);
986             double nextEndDistSq = nextSegment->distSq(nextEndT, test);
987             SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq,
988                     testSegment->debugID(), nextSegment->debugID());
989             SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq);
990             SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq);
991             SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq);
992             SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq);
993             SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT);
994             double nextLenSq = nextStartPt.distanceSquared(nextEndPt);
995             SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq);
996             SkDebugf("\n");
997         }
998         test = test->fNext;
999     } while (test->fNext != this);
1000 }
1001 #endif
1002 
1003 #if DEBUG_ANGLE
debugPart() const1004 SkString SkOpAngle::debugPart() const {
1005     SkString result;
1006     switch (this->segment()->verb()) {
1007         case SkPath::kLine_Verb:
1008             result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart),
1009                     this->segment()->debugID());
1010             break;
1011         case SkPath::kQuad_Verb:
1012             result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
1013                     this->segment()->debugID());
1014             break;
1015         case SkPath::kConic_Verb:
1016             result.printf(CONIC_DEBUG_STR " id=%d",
1017                     CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight),
1018                     this->segment()->debugID());
1019             break;
1020         case SkPath::kCubic_Verb:
1021             result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart),
1022                     this->segment()->debugID());
1023             break;
1024         default:
1025             SkASSERT(0);
1026     }
1027     return result;
1028 }
1029 #endif
1030 
1031 #if DEBUG_SORT
debugLoop() const1032 void SkOpAngle::debugLoop() const {
1033     const SkOpAngle* first = this;
1034     const SkOpAngle* next = this;
1035     do {
1036         next->dumpOne(true);
1037         SkDebugf("\n");
1038         next = next->fNext;
1039     } while (next && next != first);
1040     next = first;
1041     do {
1042         next->debugValidate();
1043         next = next->fNext;
1044     } while (next && next != first);
1045 }
1046 #endif
1047 
debugValidate() const1048 void SkOpAngle::debugValidate() const {
1049 #if DEBUG_VALIDATE
1050     const SkOpAngle* first = this;
1051     const SkOpAngle* next = this;
1052     int wind = 0;
1053     int opp = 0;
1054     int lastXor = -1;
1055     int lastOppXor = -1;
1056     do {
1057         if (next->unorderable()) {
1058             return;
1059         }
1060         const SkOpSpan* minSpan = next->start()->starter(next->end());
1061         if (minSpan->windValue() == SK_MinS32) {
1062             return;
1063         }
1064         bool op = next->segment()->operand();
1065         bool isXor = next->segment()->isXor();
1066         bool oppXor = next->segment()->oppXor();
1067         SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM));
1068         SkASSERT(!DEBUG_LIMIT_WIND_SUM
1069                 || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM));
1070         bool useXor = op ? oppXor : isXor;
1071         SkASSERT(lastXor == -1 || lastXor == (int) useXor);
1072         lastXor = (int) useXor;
1073         wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue());
1074         if (useXor) {
1075             wind &= 1;
1076         }
1077         useXor = op ? isXor : oppXor;
1078         SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor);
1079         lastOppXor = (int) useXor;
1080         opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue());
1081         if (useXor) {
1082             opp &= 1;
1083         }
1084         next = next->fNext;
1085     } while (next && next != first);
1086     SkASSERT(wind == 0 || !FLAGS_runFail);
1087     SkASSERT(opp == 0 || !FLAGS_runFail);
1088 #endif
1089 }
1090 
debugValidateNext() const1091 void SkOpAngle::debugValidateNext() const {
1092 #if !FORCE_RELEASE
1093     const SkOpAngle* first = this;
1094     const SkOpAngle* next = first;
1095     SkTDArray<const SkOpAngle*>(angles);
1096     do {
1097 //        SkASSERT_RELEASE(next->fSegment->debugContains(next));
1098         angles.push(next);
1099         next = next->next();
1100         if (next == first) {
1101             break;
1102         }
1103         SkASSERT_RELEASE(!angles.contains(next));
1104         if (!next) {
1105             return;
1106         }
1107     } while (true);
1108 #endif
1109 }
1110 
1111 
1112 #if DEBUG_COINCIDENCE
debugAddExpanded(const char * id,SkPathOpsDebug::GlitchLog * log) const1113 void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1114     // for each coincident pair, match the spans
1115     // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
1116     const SkCoincidentSpans* coin = this->fHead;
1117     if (!coin) {
1118         coin = this->fTop;
1119     }
1120     if (!coin) {
1121         return;
1122     }
1123     do {
1124         const SkOpPtT* startPtT = coin->fCoinPtTStart;
1125         const SkOpPtT* oStartPtT = coin->fOppPtTStart;
1126         SkASSERT(startPtT->contains(oStartPtT));
1127         SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
1128         const SkOpSpanBase* start = startPtT->span();
1129         const SkOpSpanBase* oStart = oStartPtT->span();
1130         const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1131         const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
1132         const SkOpSpanBase* test = start->upCast()->next();
1133         const SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
1134         while (test != end || oTest != oEnd) {
1135             bool bumpTest = true;
1136             bool bumpOTest = true;
1137             if (!test->ptT()->contains(oTest->ptT())) {
1138                 // use t ranges to guess which one is missing
1139                 double startRange = coin->fCoinPtTEnd->fT - startPtT->fT;
1140                 double startPart = (test->t() - startPtT->fT) / startRange;
1141                 double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT;
1142                 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
1143                 if (startPart == oStartPart) {
1144                     // data is corrupt
1145                     log->record(kAddCorruptCoin_Glitch, id, start, oStart);
1146                     break;
1147                 }
1148                 if (startPart < oStartPart) {
1149                     double newT = oStartPtT->fT + oStartRange * startPart;
1150                     log->record(kAddExpandedCoin_Glitch, id, oStart, newT, test->pt());
1151                     bumpOTest = false;
1152                 } else {
1153                     double newT = startPtT->fT + startRange * oStartPart;
1154                     log->record(kAddExpandedCoin_Glitch, id, start, newT, oTest->pt());
1155                     bumpTest = false;
1156                 }
1157             }
1158             if (bumpTest && test != end) {
1159                 test = test->upCast()->next();
1160             }
1161             if (bumpOTest && oTest != oEnd) {
1162                 oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
1163             }
1164         }
1165     } while ((coin = coin->fNext));
1166 }
1167 
t_range(const SkOpPtT * overS,const SkOpPtT * overE,double tStart,double tEnd,const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,double * coinTs,double * coinTe)1168 static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
1169         const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
1170     double denom = overE->fT - overS->fT;
1171     double start = 0 < denom ? tStart : tEnd;
1172     double end = 0 < denom ? tEnd : tStart;
1173     double sRatio = (start - overS->fT) / denom;
1174     double eRatio = (end - overS->fT) / denom;
1175     *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
1176     *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
1177 }
1178 
debugAddIfMissing(const SkCoincidentSpans * outer,const SkOpPtT * over1s,const SkOpPtT * over1e) const1179 bool SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
1180             const SkOpPtT* over1e) const {
1181     const SkCoincidentSpans* check = this->fTop;
1182     while (check) {
1183         if (check->fCoinPtTStart->span() == over1s->span()
1184                 && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) {
1185             SkASSERT(check->fCoinPtTEnd->span() == over1e->span()
1186                     || !fDebugState->debugRunFail());
1187             SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span()
1188                     || !fDebugState->debugRunFail());
1189             return false;
1190         }
1191         if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span()
1192                 && check->fOppPtTStart->span() == over1s->span()) {
1193             SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span()
1194                     || !fDebugState->debugRunFail());
1195             SkASSERT(check->fOppPtTEnd->span() == over1e->span()
1196                     || !fDebugState->debugRunFail());
1197             return false;
1198         }
1199         check = check->fNext;
1200     }
1201     return true;
1202 }
1203 
debugAddIfMissing(const SkOpPtT * over1s,const SkOpPtT * over1e,const SkOpPtT * over2s,const SkOpPtT * over2e,double tStart,double tEnd,SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd) const1204 bool SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
1205                       const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
1206         SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
1207         SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const {
1208     double coinTs, coinTe, oppTs, oppTe;
1209     t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
1210     t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
1211     const SkOpSegment* coinSeg = coinPtTStart->segment();
1212     const SkOpSegment* oppSeg = oppPtTStart->segment();
1213     SkASSERT(coinSeg != oppSeg);
1214     const SkCoincidentSpans* check = this->fTop;
1215     ;
1216     while (check) {
1217         const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment();
1218         const SkOpSegment* checkOppSeg;
1219         if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) {
1220             goto next;
1221         }
1222         checkOppSeg = check->fOppPtTStart->segment();
1223         if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) {
1224             goto next;
1225         }
1226         {
1227             int cTs = coinTs;
1228             int cTe = coinTe;
1229             int oTs = oppTs;
1230             int oTe = oppTe;
1231             if (checkCoinSeg != coinSeg) {
1232                 SkASSERT(checkOppSeg != oppSeg);
1233                 SkTSwap(cTs, oTs);
1234                 SkTSwap(cTe, oTe);
1235             }
1236             int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT)
1237                            + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT)
1238                            + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT)
1239                            + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT);
1240     //        SkASSERT(tweenCount == 0 || tweenCount == 4);
1241             if (tweenCount) {
1242                 return true;
1243             }
1244         }
1245 next:
1246         check = check->fNext;
1247     }
1248     if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
1249         SkTSwap(oppTs, oppTe);
1250     }
1251     if (coinTs > coinTe) {
1252         SkTSwap(coinTs, coinTe);
1253         SkTSwap(oppTs, oppTe);
1254     }
1255     bool cs = coinSeg->debugAddMissing(coinTs, oppSeg);
1256     bool ce = coinSeg->debugAddMissing(coinTe, oppSeg);
1257     if (cs == ce) {
1258         return false;
1259     }
1260     return true;
1261 }
1262 
debugAddMissing(const char * id,SkPathOpsDebug::GlitchLog * log) const1263 void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1264     const SkCoincidentSpans* outer = fHead;
1265     if (!outer) {
1266         return;
1267     }
1268     do {
1269     // addifmissing can modify the list that this is walking
1270     // save head so that walker can iterate over old data unperturbed
1271     // addifmissing adds to head freely then add saved head in the end
1272         const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
1273         SkASSERT(outerCoin == outer->fCoinPtTEnd->segment());
1274         const SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
1275         SkASSERT(outerOpp == outer->fOppPtTEnd->segment());
1276         const SkCoincidentSpans* inner = outer;
1277         while ((inner = inner->fNext)) {
1278             double overS, overE;
1279             const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
1280             SkASSERT(innerCoin == inner->fCoinPtTEnd->segment());
1281             const SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
1282             SkASSERT(innerOpp == inner->fOppPtTEnd->segment());
1283             if (outerCoin == innerCoin
1284                     && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1285                     inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
1286                 if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1287                         inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
1288                         outer->fOppPtTStart, outer->fOppPtTEnd,
1289                         inner->fOppPtTStart, inner->fOppPtTEnd)) {
1290                     log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart);
1291                 }
1292             } else if (outerCoin == innerOpp
1293                     && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1294                     inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
1295                 if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
1296                         inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
1297                         outer->fOppPtTStart, outer->fOppPtTEnd,
1298                         inner->fCoinPtTStart, inner->fCoinPtTEnd)) {
1299                     log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart);
1300                 }
1301             } else if (outerOpp == innerCoin
1302                     && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
1303                     inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
1304                 if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
1305                         inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
1306                         outer->fCoinPtTStart, outer->fCoinPtTEnd,
1307                         inner->fOppPtTStart, inner->fOppPtTEnd)) {
1308                     log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart);
1309                 }
1310             } else if (outerOpp == innerOpp
1311                     && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
1312                     inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
1313                 if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
1314                         inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
1315                         outer->fCoinPtTStart, outer->fCoinPtTEnd,
1316                         inner->fCoinPtTStart, inner->fCoinPtTEnd)) {
1317                     log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart);
1318                 }
1319             } else if (outerCoin != innerCoin) {
1320                 // check to see if outer span overlaps the inner span
1321                     // look for inner segment in pt-t list
1322                     // if present, and if t values are in coincident range
1323                     // add two pairs of new coincidence
1324                 const SkOpPtT* testS = outer->fCoinPtTStart->debugContains(innerCoin);
1325                 const SkOpPtT* testE = outer->fCoinPtTEnd->debugContains(innerCoin);
1326                 if (testS && testS->fT >= inner->fCoinPtTStart->fT
1327                         && testE && testE->fT <= inner->fCoinPtTEnd->fT
1328                         && this->testForCoincidence(outer, testS, testE)) {
1329                     if (this->debugAddIfMissing(outer, testS, testE)) {
1330                         log->record(kAddMissingCoin_Glitch, id, outer, testS, testE);
1331                     }
1332                 } else {
1333                     testS = inner->fCoinPtTStart->debugContains(outerCoin);
1334                     testE = inner->fCoinPtTEnd->debugContains(outerCoin);
1335                     if (testS && testS->fT >= outer->fCoinPtTStart->fT
1336                             && testE && testE->fT <= outer->fCoinPtTEnd->fT
1337                             && this->testForCoincidence(inner, testS, testE)) {
1338                         if (this->debugAddIfMissing(inner, testS, testE)) {
1339                             log->record(kAddMissingCoin_Glitch, id, inner, testS, testE);
1340                         }
1341                     }
1342                 }
1343             }
1344         }
1345     } while ((outer = outer->fNext));
1346 }
1347 
debugExpand(const char * id,SkPathOpsDebug::GlitchLog * log) const1348 bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1349     const SkCoincidentSpans* coin = fHead;
1350     if (!coin) {
1351         return false;
1352     }
1353     bool expanded = false;
1354     do {
1355         const SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
1356         const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1357         const SkOpSegment* segment = coin->fCoinPtTStart->segment();
1358         const SkOpSegment* oppSegment = coin->fOppPtTStart->segment();
1359         const SkOpSpan* prev = start->prev();
1360         if (prev && prev->debugContains(oppSegment)) {
1361             double midT = (prev->t() + start->t()) / 2;
1362             if (segment->isClose(midT, oppSegment)) {
1363                 log->record(kExpandCoin_Glitch, id, coin, prev);
1364             }
1365         }
1366         SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
1367         if (next && next->debugContains(oppSegment)) {
1368             double midT = (end->t() + next->t()) / 2;
1369             if (segment->isClose(midT, oppSegment)) {
1370                 log->record(kExpandCoin_Glitch, id, coin, next);
1371             }
1372         }
1373     } while ((coin = coin->fNext));
1374     return expanded;
1375 }
1376 
debugFixAligned(const char * id,SkPathOpsDebug::GlitchLog * log) const1377 void SkOpCoincidence::debugFixAligned(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1378     const SkCoincidentSpans* coin = fHead;
1379     if (!coin) {
1380         return;
1381     }
1382     do {
1383         if (coin->fCoinPtTStart->deleted()) {
1384             log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTStart);
1385         }
1386         if (coin->fCoinPtTEnd->deleted()) {
1387             log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTEnd);
1388         }
1389         if (coin->fOppPtTStart->deleted()) {
1390             log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTStart);
1391         }
1392         if (coin->fOppPtTEnd->deleted()) {
1393             log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTEnd);
1394         }
1395     } while ((coin = coin->fNext));
1396     coin = fHead;
1397     do {
1398         if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)) {
1399             log->record(kCollapsedCoin_Glitch, id, coin, coin->fCoinPtTStart);
1400         }
1401         if (coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
1402             log->record(kCollapsedCoin_Glitch, id, coin, coin->fOppPtTStart);
1403         }
1404     } while ((coin = coin->fNext));
1405 }
1406 
debugMark(const char * id,SkPathOpsDebug::GlitchLog * log) const1407 void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1408     const SkCoincidentSpans* coin = fHead;
1409     if (!coin) {
1410         return;
1411     }
1412     do {
1413         const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
1414         const SkOpSpanBase* oldEnd = end;
1415         const SkOpSpan* start = coin->fCoinPtTStart->span()->debugStarter(&end);
1416         const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
1417         const SkOpSpanBase* oOldEnd = oEnd;
1418         const SkOpSpanBase* oStart = coin->fOppPtTStart->span()->debugStarter(&oEnd);
1419         bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
1420         if (flipped) {
1421             SkTSwap(oStart, oEnd);
1422         }
1423         const SkOpSpanBase* next = start;
1424         const SkOpSpanBase* oNext = oStart;
1425         do {
1426             next = next->upCast()->next();
1427             oNext = flipped ? oNext->prev() : oNext->upCast()->next();
1428             if (next == end || oNext == oEnd) {
1429                 break;
1430             }
1431             if (!next->containsCoinEnd(oNext)) {
1432                 log->record(kMarkCoinEnd_Glitch, id, next, oNext);
1433             }
1434             const SkOpSpan* nextSpan = next->upCast();
1435             const SkOpSpan* oNextSpan = oNext->upCast();
1436             if (!nextSpan->containsCoincidence(oNextSpan)) {
1437                 log->record(kMarkCoinInsert_Glitch, id, nextSpan, oNextSpan);
1438             }
1439         } while (true);
1440     } while ((coin = coin->fNext));
1441 }
1442 #endif
1443 
debugShowCoincidence() const1444 void SkOpCoincidence::debugShowCoincidence() const {
1445     SkCoincidentSpans* span = fHead;
1446     while (span) {
1447         SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1448                 span->fCoinPtTStart->segment()->debugID(),
1449                 span->fCoinPtTStart->fT, span->fCoinPtTEnd->fT);
1450         SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
1451                 span->fOppPtTStart->segment()->debugID(),
1452                 span->fOppPtTStart->fT, span->fOppPtTEnd->fT);
1453         span = span->fNext;
1454     }
1455 }
1456 
1457 #if DEBUG_COINCIDENCE
debugCheckHealth(const char * id,SkPathOpsDebug::GlitchLog * log) const1458 void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const {
1459     const SkOpSegment* segment = &fHead;
1460     do {
1461         segment->debugCheckHealth(id, log);
1462     } while ((segment = segment->next()));
1463 }
1464 
debugMissingCoincidence(const char * id,SkPathOpsDebug::GlitchLog * log,const SkOpCoincidence * coincidence) const1465 void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
1466         const SkOpCoincidence* coincidence) const {
1467     const SkOpSegment* segment = &fHead;
1468     do {
1469         segment->debugMissingCoincidence(id, log, coincidence);
1470     } while ((segment = segment->next()));
1471 }
1472 #endif
1473 
debugValidate() const1474 void SkOpSegment::debugValidate() const {
1475 #if DEBUG_VALIDATE
1476     const SkOpSpanBase* span = &fHead;
1477     double lastT = -1;
1478     const SkOpSpanBase* prev = nullptr;
1479     int count = 0;
1480     int done = 0;
1481     do {
1482         if (!span->final()) {
1483             ++count;
1484             done += span->upCast()->done() ? 1 : 0;
1485         }
1486         SkASSERT(span->segment() == this);
1487         SkASSERT(!prev || prev->upCast()->next() == span);
1488         SkASSERT(!prev || prev == span->prev());
1489         prev = span;
1490         double t = span->ptT()->fT;
1491         SkASSERT(lastT < t);
1492         lastT = t;
1493         span->debugValidate();
1494     } while (!span->final() && (span = span->upCast()->next()));
1495     SkASSERT(count == fCount);
1496     SkASSERT(done == fDoneCount);
1497     SkASSERT(count >= fDoneCount);
1498     SkASSERT(span->final());
1499     span->debugValidate();
1500 #endif
1501 }
1502 
debugAlignedEnd(double t,const SkPoint & pt) const1503 bool SkOpSpanBase::debugAlignedEnd(double t, const SkPoint& pt) const {
1504     SkASSERT(zero_or_one(t));
1505     const SkOpSegment* segment = this->segment();
1506     SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt);
1507     if (!debugAlignedInner()) {
1508           return false;
1509     }
1510     if ((t ? segment->lastPt() : segment->pts()[0]) != pt) {
1511         return false;
1512     }
1513     const SkOpPtT* ptT = &this->fPtT;
1514     SkASSERT(t == ptT->fT);
1515     SkASSERT(pt == ptT->fPt);
1516     const SkOpPtT* test = ptT, * stopPtT = ptT;
1517     while ((test = test->next()) != stopPtT) {
1518         const SkOpSegment* other = test->segment();
1519         if (other == this->segment()) {
1520             continue;
1521         }
1522         if (!zero_or_one(test->fT)) {
1523             continue;
1524         }
1525         if ((test->fT ? other->lastPt() : other->pts()[0]) != pt) {
1526             return false;
1527         }
1528     }
1529     return this->fAligned;
1530 }
1531 
debugAlignedInner() const1532 bool SkOpSpanBase::debugAlignedInner() const {
1533     // force the spans to share points and t values
1534     const SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
1535     const SkPoint& pt = ptT->fPt;
1536     do {
1537         if (ptT->fPt != pt) {
1538             return false;
1539         }
1540         const SkOpSpanBase* span = ptT->span();
1541         const SkOpPtT* test = ptT;
1542         do {
1543             if ((test = test->next()) == stopPtT) {
1544                 break;
1545             }
1546             if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) {
1547                 return false;
1548             }
1549         } while (true);
1550     } while ((ptT = ptT->next()) != stopPtT);
1551     return true;
1552 }
1553 
debugCoinEndLoopCheck() const1554 bool SkOpSpanBase::debugCoinEndLoopCheck() const {
1555     int loop = 0;
1556     const SkOpSpanBase* next = this;
1557     SkOpSpanBase* nextCoin;
1558     do {
1559         nextCoin = next->fCoinEnd;
1560         SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin);
1561         for (int check = 1; check < loop - 1; ++check) {
1562             const SkOpSpanBase* checkCoin = this->fCoinEnd;
1563             const SkOpSpanBase* innerCoin = checkCoin;
1564             for (int inner = check + 1; inner < loop; ++inner) {
1565                 innerCoin = innerCoin->fCoinEnd;
1566                 if (checkCoin == innerCoin) {
1567                     SkDebugf("*** bad coincident end loop ***\n");
1568                     return false;
1569                 }
1570             }
1571         }
1572         ++loop;
1573     } while ((next = nextCoin) && next != this);
1574     return true;
1575 }
1576 
debugContains(const SkOpSegment * segment) const1577 bool SkOpSpanBase::debugContains(const SkOpSegment* segment) const {
1578     const SkOpPtT* start = &fPtT;
1579     const SkOpPtT* walk = start;
1580     while ((walk = walk->next()) != start) {
1581         if (walk->segment() == segment) {
1582             return true;
1583         }
1584     }
1585     return false;
1586 }
1587 
debugStarter(SkOpSpanBase const ** endPtr) const1588 const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
1589     const SkOpSpanBase* end = *endPtr;
1590     SkASSERT(this->segment() == end->segment());
1591     const SkOpSpanBase* result;
1592     if (t() < end->t()) {
1593         result = this;
1594     } else {
1595         result = end;
1596         *endPtr = this;
1597     }
1598     return result->upCast();
1599 }
1600 
debugValidate() const1601 void SkOpSpanBase::debugValidate() const {
1602 #if DEBUG_VALIDATE
1603     const SkOpPtT* ptT = &fPtT;
1604     SkASSERT(ptT->span() == this);
1605     do {
1606 //        SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt));
1607         ptT->debugValidate();
1608         ptT = ptT->next();
1609     } while (ptT != &fPtT);
1610     SkASSERT(this->debugCoinEndLoopCheck());
1611     if (!this->final()) {
1612         SkASSERT(this->upCast()->debugCoinLoopCheck());
1613     }
1614     if (fFromAngle) {
1615         fFromAngle->debugValidate();
1616     }
1617     if (!this->final() && this->upCast()->toAngle()) {
1618         this->upCast()->toAngle()->debugValidate();
1619     }
1620 #endif
1621 }
1622 
debugCoinLoopCheck() const1623 bool SkOpSpan::debugCoinLoopCheck() const {
1624     int loop = 0;
1625     const SkOpSpan* next = this;
1626     SkOpSpan* nextCoin;
1627     do {
1628         nextCoin = next->fCoincident;
1629         SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin);
1630         for (int check = 1; check < loop - 1; ++check) {
1631             const SkOpSpan* checkCoin = this->fCoincident;
1632             const SkOpSpan* innerCoin = checkCoin;
1633             for (int inner = check + 1; inner < loop; ++inner) {
1634                 innerCoin = innerCoin->fCoincident;
1635                 if (checkCoin == innerCoin) {
1636                     SkDebugf("*** bad coincident loop ***\n");
1637                     return false;
1638                 }
1639             }
1640         }
1641         ++loop;
1642     } while ((next = nextCoin) && next != this);
1643     return true;
1644 }
1645 
1646 // called only by test code
debugCoincidentUsed() const1647 int SkIntersections::debugCoincidentUsed() const {
1648     if (!fIsCoincident[0]) {
1649         SkASSERT(!fIsCoincident[1]);
1650         return 0;
1651     }
1652     int count = 0;
1653     SkDEBUGCODE(int count2 = 0;)
1654     for (int index = 0; index < fUsed; ++index) {
1655         if (fIsCoincident[0] & (1 << index)) {
1656             ++count;
1657         }
1658 #ifdef SK_DEBUG
1659         if (fIsCoincident[1] & (1 << index)) {
1660             ++count2;
1661         }
1662 #endif
1663     }
1664     SkASSERT(count == count2);
1665     return count;
1666 }
1667 
1668 #include "SkOpContour.h"
1669 
debugContains(const SkOpPtT * check) const1670 bool SkOpPtT::debugContains(const SkOpPtT* check) const {
1671     SkASSERT(this != check);
1672     const SkOpPtT* ptT = this;
1673     int links = 0;
1674     do {
1675         ptT = ptT->next();
1676         if (ptT == check) {
1677             return true;
1678         }
1679         ++links;
1680         const SkOpPtT* test = this;
1681         for (int index = 0; index < links; ++index) {
1682             if (ptT == test) {
1683                 return false;
1684             }
1685             test = test->next();
1686         }
1687     } while (true);
1688 }
1689 
debugContains(const SkOpSegment * check) const1690 const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const {
1691     SkASSERT(this->segment() != check);
1692     const SkOpPtT* ptT = this;
1693     int links = 0;
1694     do {
1695         ptT = ptT->next();
1696         if (ptT->segment() == check) {
1697             return ptT;
1698         }
1699         ++links;
1700         const SkOpPtT* test = this;
1701         for (int index = 0; index < links; ++index) {
1702             if (ptT == test) {
1703                 return nullptr;
1704             }
1705             test = test->next();
1706         }
1707     } while (true);
1708 }
1709 
debugLoopLimit(bool report) const1710 int SkOpPtT::debugLoopLimit(bool report) const {
1711     int loop = 0;
1712     const SkOpPtT* next = this;
1713     do {
1714         for (int check = 1; check < loop - 1; ++check) {
1715             const SkOpPtT* checkPtT = this->fNext;
1716             const SkOpPtT* innerPtT = checkPtT;
1717             for (int inner = check + 1; inner < loop; ++inner) {
1718                 innerPtT = innerPtT->fNext;
1719                 if (checkPtT == innerPtT) {
1720                     if (report) {
1721                         SkDebugf("*** bad ptT loop ***\n");
1722                     }
1723                     return loop;
1724                 }
1725             }
1726         }
1727         // there's nothing wrong with extremely large loop counts -- but this may appear to hang
1728         // by taking a very long time to figure out that no loop entry is a duplicate
1729         // -- and it's likely that a large loop count is indicative of a bug somewhere
1730         if (++loop > 1000) {
1731             SkDebugf("*** loop count exceeds 1000 ***\n");
1732             return 1000;
1733         }
1734     } while ((next = next->fNext) && next != this);
1735     return 0;
1736 }
1737 
debugValidate() const1738 void SkOpPtT::debugValidate() const {
1739 #if DEBUG_VALIDATE
1740     SkOpGlobalState::Phase phase = contour()->globalState()->phase();
1741     if (phase == SkOpGlobalState::kIntersecting
1742             || phase == SkOpGlobalState::kFixWinding) {
1743         return;
1744     }
1745     SkASSERT(fNext);
1746     SkASSERT(fNext != this);
1747     SkASSERT(fNext->fNext);
1748     SkASSERT(debugLoopLimit(false) == 0);
1749 #endif
1750 }
1751 
output_scalar(SkScalar num)1752 static void output_scalar(SkScalar num) {
1753     if (num == (int) num) {
1754         SkDebugf("%d", (int) num);
1755     } else {
1756         SkString str;
1757         str.printf("%1.9g", num);
1758         int width = (int) str.size();
1759         const char* cStr = str.c_str();
1760         while (cStr[width - 1] == '0') {
1761             --width;
1762         }
1763         str.resize(width);
1764         SkDebugf("%sf", str.c_str());
1765     }
1766 }
1767 
output_points(const SkPoint * pts,int count)1768 static void output_points(const SkPoint* pts, int count) {
1769     for (int index = 0; index < count; ++index) {
1770         output_scalar(pts[index].fX);
1771         SkDebugf(", ");
1772         output_scalar(pts[index].fY);
1773         if (index + 1 < count) {
1774             SkDebugf(", ");
1775         }
1776     }
1777 }
1778 
showPathContours(SkPath::RawIter & iter,const char * pathName)1779 static void showPathContours(SkPath::RawIter& iter, const char* pathName) {
1780     uint8_t verb;
1781     SkPoint pts[4];
1782     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1783         switch (verb) {
1784             case SkPath::kMove_Verb:
1785                 SkDebugf("    %s.moveTo(", pathName);
1786                 output_points(&pts[0], 1);
1787                 SkDebugf(");\n");
1788                 continue;
1789             case SkPath::kLine_Verb:
1790                 SkDebugf("    %s.lineTo(", pathName);
1791                 output_points(&pts[1], 1);
1792                 SkDebugf(");\n");
1793                 break;
1794             case SkPath::kQuad_Verb:
1795                 SkDebugf("    %s.quadTo(", pathName);
1796                 output_points(&pts[1], 2);
1797                 SkDebugf(");\n");
1798                 break;
1799             case SkPath::kConic_Verb:
1800                 SkDebugf("    %s.conicTo(", pathName);
1801                 output_points(&pts[1], 2);
1802                 SkDebugf(", %1.9gf);\n", iter.conicWeight());
1803                 break;
1804             case SkPath::kCubic_Verb:
1805                 SkDebugf("    %s.cubicTo(", pathName);
1806                 output_points(&pts[1], 3);
1807                 SkDebugf(");\n");
1808                 break;
1809             case SkPath::kClose_Verb:
1810                 SkDebugf("    %s.close();\n", pathName);
1811                 break;
1812             default:
1813                 SkDEBUGFAIL("bad verb");
1814                 return;
1815         }
1816     }
1817 }
1818 
1819 static const char* gFillTypeStr[] = {
1820     "kWinding_FillType",
1821     "kEvenOdd_FillType",
1822     "kInverseWinding_FillType",
1823     "kInverseEvenOdd_FillType"
1824 };
1825 
ShowOnePath(const SkPath & path,const char * name,bool includeDeclaration)1826 void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
1827     SkPath::RawIter iter(path);
1828 #define SUPPORT_RECT_CONTOUR_DETECTION 0
1829 #if SUPPORT_RECT_CONTOUR_DETECTION
1830     int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0;
1831     if (rectCount > 0) {
1832         SkTDArray<SkRect> rects;
1833         SkTDArray<SkPath::Direction> directions;
1834         rects.setCount(rectCount);
1835         directions.setCount(rectCount);
1836         path.rectContours(rects.begin(), directions.begin());
1837         for (int contour = 0; contour < rectCount; ++contour) {
1838             const SkRect& rect = rects[contour];
1839             SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
1840                     rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
1841                     ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
1842         }
1843         return;
1844     }
1845 #endif
1846     SkPath::FillType fillType = path.getFillType();
1847     SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
1848     if (includeDeclaration) {
1849         SkDebugf("    SkPath %s;\n", name);
1850     }
1851     SkDebugf("    %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
1852     iter.setPath(path);
1853     showPathContours(iter, name);
1854 }
1855