SkPathOpsDebug.cpp source code [Skia/src/pathops/SkPathOpsDebug.cpp]

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

Browse the source code of Skia/src/pathops/SkPathOpsDebug.cpp