1/*
2 * Copyright 2015 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 "tests/Test.h"
9
10#include "include/core/SkPath.h"
11#include "include/effects/SkGradientShader.h"
12#include "include/gpu/GrDirectContext.h"
13#include "src/gpu/GrDirectContextPriv.h"
14#include "src/gpu/GrEagerVertexAllocator.h"
15#include "src/gpu/GrStyle.h"
16#include "src/gpu/effects/GrPorterDuffXferProcessor.h"
17#include "src/gpu/geometry/GrInnerFanTriangulator.h"
18#include "src/gpu/geometry/GrStyledShape.h"
19#include "src/shaders/SkShaderBase.h"
20#include "tools/ToolUtils.h"
21#include <map>
22
23/*
24 * These tests pass by not crashing, hanging or asserting in Debug.
25 */
26
27using CreatePathFn = SkPath(*)();
28
29CreatePathFn kNonEdgeAAPaths[] = {
30    // Tests active edges made inactive by splitting.
31    // Also tests active edge list forced into an invalid ordering by
32    // splitting (mopped up in cleanup_active_edges()).
33    []() -> SkPath {
34        SkPath path;
35        path.moveTo(229.127044677734375f,  67.34100341796875f);
36        path.lineTo(187.8097381591796875f, -6.7729740142822265625f);
37        path.lineTo(171.411407470703125f,  50.94266510009765625f);
38        path.lineTo(245.5253753662109375f,  9.6253643035888671875f);
39        path.moveTo(208.4683990478515625f, 30.284009933471679688f);
40        path.lineTo(171.411407470703125f,  50.94266510009765625f);
41        path.lineTo(187.8097381591796875f, -6.7729740142822265625f);
42        return path;
43    },
44
45    // Intersections which fall exactly on the current vertex, and require
46    // a restart of the intersection checking.
47    []() -> SkPath {
48        SkPath path;
49        path.moveTo(314.483551025390625f, 486.246002197265625f);
50        path.lineTo(385.41949462890625f,  532.8087158203125f);
51        path.lineTo(373.232879638671875f, 474.05938720703125f);
52        path.lineTo(326.670166015625f,    544.995361328125f);
53        path.moveTo(349.951507568359375f, 509.52734375f);
54        path.lineTo(373.232879638671875f, 474.05938720703125f);
55        path.lineTo(385.41949462890625f,  532.8087158203125f);
56        return path;
57    },
58
59    // Tests active edges which are removed by splitting.
60    []() -> SkPath {
61        SkPath path;
62        path.moveTo(343.107391357421875f, 613.62176513671875f);
63        path.lineTo(426.632415771484375f, 628.5740966796875f);
64        path.lineTo(392.3460693359375f,   579.33544921875f);
65        path.lineTo(377.39373779296875f,  662.86041259765625f);
66        path.moveTo(384.869873046875f,    621.097900390625f);
67        path.lineTo(392.3460693359375f,   579.33544921875f);
68        path.lineTo(426.632415771484375f, 628.5740966796875f);
69        return path;
70    },
71
72    // Collinear edges merged in set_top().
73    // Also, an intersection between left and right enclosing edges which
74    // falls above the current vertex.
75    []() -> SkPath {
76        SkPath path;
77        path.moveTo(545.95751953125f,    791.69854736328125f);
78        path.lineTo(612.05816650390625f, 738.494140625f);
79        path.lineTo(552.4056396484375f,  732.0460205078125f);
80        path.lineTo(605.61004638671875f, 798.14666748046875f);
81        path.moveTo(579.00787353515625f, 765.0963134765625f);
82        path.lineTo(552.4056396484375f,  732.0460205078125f);
83        path.lineTo(612.05816650390625f, 738.494140625f);
84        return path;
85    },
86
87    // Tests active edges which are made inactive by set_top().
88    []() -> SkPath {
89        SkPath path;
90        path.moveTo(819.2725830078125f,  751.77447509765625f);
91        path.lineTo(820.70904541015625f, 666.933837890625f);
92        path.lineTo(777.57049560546875f, 708.63592529296875f);
93        path.lineTo(862.4111328125f,     710.0723876953125f);
94        path.moveTo(819.99078369140625f, 709.3541259765625f);
95        path.lineTo(777.57049560546875f, 708.63592529296875f);
96        path.lineTo(820.70904541015625f, 666.933837890625f);
97        return path;
98    },
99
100    []() -> SkPath {
101        SkPath path;
102        path.moveTo(823.33209228515625f, 749.052734375f);
103        path.lineTo(823.494873046875f,   664.20013427734375f);
104        path.lineTo(780.9871826171875f,  706.5450439453125f);
105        path.lineTo(865.8397216796875f,  706.70782470703125f);
106        path.moveTo(823.4134521484375f,  706.6263427734375f);
107        path.lineTo(780.9871826171875f,  706.5450439453125f);
108        path.lineTo(823.494873046875f,   664.20013427734375f);
109        return path;
110    },
111
112    []() -> SkPath {
113        SkPath path;
114        path.moveTo(954.862548828125f,   562.8349609375f);
115        path.lineTo(899.32818603515625f, 498.679443359375f);
116        path.lineTo(895.017578125f,      558.52435302734375f);
117        path.lineTo(959.17315673828125f, 502.990081787109375f);
118        path.moveTo(927.0953369140625f,  530.7572021484375f);
119        path.lineTo(895.017578125f,      558.52435302734375f);
120        path.lineTo(899.32818603515625f, 498.679443359375f);
121        return path;
122    },
123
124    []() -> SkPath {
125        SkPath path;
126        path.moveTo(958.5330810546875f,  547.35516357421875f);
127        path.lineTo(899.93109130859375f, 485.989013671875f);
128        path.lineTo(898.54901123046875f, 545.97308349609375f);
129        path.lineTo(959.9151611328125f,  487.37109375f);
130        path.moveTo(929.2320556640625f,  516.67205810546875f);
131        path.lineTo(898.54901123046875f, 545.97308349609375f);
132        path.lineTo(899.93109130859375f, 485.989013671875f);
133        return path;
134    },
135
136    []() -> SkPath {
137        SkPath path;
138        path.moveTo(389.8609619140625f,   369.326873779296875f);
139        path.lineTo(470.6290283203125f,   395.33697509765625f);
140        path.lineTo(443.250030517578125f, 341.9478759765625f);
141        path.lineTo(417.239959716796875f, 422.7159423828125f);
142        path.moveTo(430.244964599609375f, 382.3319091796875f);
143        path.lineTo(443.250030517578125f, 341.9478759765625f);
144        path.lineTo(470.6290283203125f,   395.33697509765625f);
145        return path;
146    },
147
148    []() -> SkPath {
149        SkPath path;
150        path.moveTo(20, 20);
151        path.lineTo(50, 80);
152        path.lineTo(20, 80);
153        path.moveTo(80, 50);
154        path.lineTo(50, 50);
155        path.lineTo(20, 50);
156        return path;
157    },
158
159    []() -> SkPath {
160        SkPath path;
161        path.moveTo(257.19439697265625f, 320.876617431640625f);
162        path.lineTo(190.113037109375f,   320.58978271484375f);
163        path.lineTo(203.64404296875f,    293.8145751953125f);
164        path.moveTo(203.357177734375f,   360.896026611328125f);
165        path.lineTo(216.88824462890625f, 334.120819091796875f);
166        path.lineTo(230.41925048828125f, 307.345611572265625f);
167        return path;
168    },
169
170    // A degenerate segments case, where both upper and lower segments of
171    // a split edge must remain active.
172    []() -> SkPath {
173        SkPath path;
174        path.moveTo(231.9331207275390625f, 306.2012939453125f);
175        path.lineTo(191.4859161376953125f, 306.04547119140625f);
176        path.lineTo(231.0659332275390625f, 300.2642822265625f);
177        path.moveTo(189.946807861328125f,  302.072265625f);
178        path.lineTo(179.79705810546875f,   294.859771728515625f);
179        path.lineTo(191.0016021728515625f, 296.165679931640625f);
180        path.moveTo(150.8942108154296875f, 304.900146484375f);
181        path.lineTo(179.708892822265625f,  297.849029541015625f);
182        path.lineTo(190.4742279052734375f, 299.11895751953125f);
183        return path;
184    },
185
186    // Handle the case where edge.dist(edge.fTop) != 0.0.
187    []() -> SkPath {
188        SkPath path;
189        path.moveTo(                  0.0f,  400.0f);
190        path.lineTo(                138.0f,  202.0f);
191        path.lineTo(                  0.0f,  202.0f);
192        path.moveTo( 12.62693023681640625f,  250.57464599609375f);
193        path.lineTo(  8.13896942138671875f,  254.556884765625f);
194        path.lineTo(-18.15641021728515625f,  220.40203857421875f);
195        path.lineTo(-15.986493110656738281f, 219.6513519287109375f);
196        path.moveTo( 36.931194305419921875f, 282.485504150390625f);
197        path.lineTo( 15.617521286010742188f, 261.2901611328125f);
198        path.lineTo( 10.3829498291015625f,   252.565765380859375f);
199        path.lineTo(-16.165292739868164062f, 222.646026611328125f);
200        return path;
201    },
202
203    // A degenerate segments case which exercises inactive edges being
204    // made active by splitting.
205    []() -> SkPath {
206        SkPath path;
207        path.moveTo(690.62127685546875f, 509.25555419921875f);
208        path.lineTo(99.336181640625f,    511.71405029296875f);
209        path.lineTo(708.362548828125f,   512.4349365234375f);
210        path.lineTo(729.9940185546875f,  516.3114013671875f);
211        path.lineTo(738.708984375f,      518.76995849609375f);
212        path.lineTo(678.3463134765625f,  510.0819091796875f);
213        path.lineTo(681.21795654296875f, 504.81378173828125f);
214        path.moveTo(758.52764892578125f, 521.55963134765625f);
215        path.lineTo(719.1549072265625f,  514.50372314453125f);
216        path.lineTo(689.59063720703125f, 512.0628662109375f);
217        path.lineTo(679.78216552734375f, 507.447845458984375f);
218        return path;
219    },
220
221    // Tests vertices which become "orphaned" (ie., no connected edges)
222    // after simplification.
223    []() -> SkPath {
224        SkPath path;
225        path.moveTo(217.326019287109375f, 166.4752960205078125f);
226        path.lineTo(226.279266357421875f, 170.929473876953125f);
227        path.lineTo(234.3973388671875f,   177.0623626708984375f);
228        path.lineTo(262.0921630859375f,   188.746124267578125f);
229        path.moveTo(196.23638916015625f,  174.0722198486328125f);
230        path.lineTo(416.15277099609375f,  180.138214111328125f);
231        path.lineTo(192.651947021484375f, 304.0228271484375f);
232        return path;
233    },
234
235    []() -> SkPath {
236        SkPath path;
237        path.moveTo(    0.0f,   0.0f);
238        path.lineTo(10000.0f,   0.0f);
239        path.lineTo(    0.0f,  -1.0f);
240        path.lineTo(10000.0f,   0.000001f);
241        path.lineTo(    0.0f, -30.0f);
242        return path;
243    },
244
245    // Reduction of Nebraska-StateSeal.svg. Floating point error causes the
246    // same edge to be added to more than one poly on the same side.
247    []() -> SkPath {
248        SkPath path;
249        path.moveTo(170.8199920654296875,   491.86700439453125);
250        path.lineTo(173.7649993896484375,    489.7340087890625);
251        path.lineTo(174.1450958251953125,  498.545989990234375);
252        path.lineTo( 171.998992919921875,   500.88201904296875);
253        path.moveTo(168.2922515869140625,   498.66265869140625);
254        path.lineTo(169.8589935302734375,   497.94500732421875);
255        path.lineTo(                 172,   500.88299560546875);
256        path.moveTo( 169.555267333984375,   490.70111083984375);
257        path.lineTo(173.7649993896484375,    489.7340087890625);
258        path.lineTo(  170.82000732421875,   491.86700439453125);
259        return path;
260    },
261
262    // A shape with a vertex collinear to the right hand edge.
263    // This messes up find_enclosing_edges.
264    []() -> SkPath {
265        SkPath path;
266        path.moveTo(80, 20);
267        path.lineTo(80, 60);
268        path.lineTo(20, 60);
269        path.moveTo(80, 50);
270        path.lineTo(80, 80);
271        path.lineTo(20, 80);
272        return path;
273    },
274
275    // Exercises the case where an edge becomes collinear with *two* of its
276    // adjacent neighbour edges after splitting.
277    // This is a reduction from
278    // http://mooooo.ooo/chebyshev-sine-approximation/horner_ulp.svg
279    []() -> SkPath {
280        SkPath path;
281        path.moveTo(  351.99298095703125,         348.23046875);
282        path.lineTo(  351.91876220703125,         347.33984375);
283        path.lineTo(  351.91876220703125,          346.1953125);
284        path.lineTo(  351.90313720703125,           347.734375);
285        path.lineTo(  351.90313720703125,          346.1328125);
286        path.lineTo(  351.87579345703125,         347.93359375);
287        path.lineTo(  351.87579345703125,           345.484375);
288        path.lineTo(  351.86407470703125,          347.7890625);
289        path.lineTo(  351.86407470703125,          346.2109375);
290        path.lineTo(  351.84844970703125,   347.63763427734375);
291        path.lineTo(  351.84454345703125,   344.19232177734375);
292        path.lineTo(  351.78204345703125,    346.9483642578125);
293        path.lineTo( 351.758636474609375,      347.18310546875);
294        path.lineTo(  351.75469970703125,               346.75);
295        path.lineTo(  351.75469970703125,            345.46875);
296        path.lineTo(         352.5546875,            345.46875);
297        path.lineTo(        352.55078125,         347.01953125);
298        path.lineTo(  351.75079345703125,   347.02313232421875);
299        path.lineTo(  351.74688720703125,   346.15203857421875);
300        path.lineTo(  351.74688720703125,  347.646148681640625);
301        path.lineTo(         352.5390625,         346.94140625);
302        path.lineTo(  351.73907470703125,   346.94268798828125);
303        path.lineTo(  351.73516845703125,   344.48565673828125);
304        path.lineTo(          352.484375,         346.73828125);
305        path.lineTo(  351.68438720703125,    346.7401123046875);
306        path.lineTo(         352.4765625,           346.546875);
307        path.lineTo(  351.67657470703125,   346.54937744140625);
308        path.lineTo(        352.47265625,         346.75390625);
309        path.lineTo(  351.67266845703125,  346.756622314453125);
310        path.lineTo(  351.66876220703125,  345.612091064453125);
311        return path;
312    },
313
314    // A path which contains out-of-range colinear intersections.
315    []() -> SkPath {
316        SkPath path;
317        path.moveTo(                   0, 63.39080047607421875);
318        path.lineTo(-0.70804601907730102539, 63.14350128173828125);
319        path.lineTo(-7.8608899287380243391e-17, 64.14080047607421875);
320        path.moveTo(                   0, 64.14080047607421875);
321        path.lineTo(44.285900115966796875, 64.14080047607421875);
322        path.lineTo(                   0, 62.64080047607421875);
323        path.moveTo(21.434900283813476562, -0.24732701480388641357);
324        path.lineTo(-0.70804601907730102539, 63.14350128173828125);
325        path.lineTo(0.70804601907730102539,  63.6381988525390625);
326        return path;
327    },
328
329    // A path which results in infs and nans when conics are converted to quads.
330    []() -> SkPath {
331         SkPath path;
332         path.moveTo(-2.20883e+37f, -1.02892e+37f);
333         path.conicTo(-2.00958e+38f, -9.36107e+37f, -1.7887e+38f, -8.33215e+37f, 0.707107f);
334         path.conicTo(-1.56782e+38f, -7.30323e+37f, 2.20883e+37f, 1.02892e+37f, 0.707107f);
335         path.conicTo(2.00958e+38f, 9.36107e+37f, 1.7887e+38f, 8.33215e+37f, 0.707107f);
336         path.conicTo(1.56782e+38f, 7.30323e+37f, -2.20883e+37f, -1.02892e+37f, 0.707107f);
337         return path;
338    },
339
340    // A quad which generates a huge number of points (>2B) when uniformly
341    // linearized. This should not hang or OOM.
342    []() -> SkPath {
343        SkPath path;
344        path.moveTo(10, 0);
345        path.lineTo(0, 0);
346        path.quadTo(10, 0, 0, 8315084722602508288);
347        return path;
348    },
349
350    // A path which hangs during simplification. It produces an edge which is
351    // to the left of its own endpoints, which causes an infinite loop in the
352    // right-enclosing-edge splitting.
353    []() -> SkPath {
354        SkPath path;
355        path.moveTo(0.75001740455627441406,     23.051967620849609375);
356        path.lineTo(5.8471612930297851562,      22.731662750244140625);
357        path.lineTo(10.749670028686523438,      22.253145217895507812);
358        path.lineTo(13.115868568420410156,      22.180681228637695312);
359        path.lineTo(15.418928146362304688,      22.340015411376953125);
360        path.lineTo(  17.654022216796875,       22.82159423828125);
361        path.lineTo(19.81632232666015625,       23.715869903564453125);
362        path.lineTo(40,                         0);
363        path.lineTo(5.5635203441547955577e-15,  0);
364        path.lineTo(5.5635203441547955577e-15,  47);
365        path.lineTo(-1.4210854715202003717e-14, 21.713298797607421875);
366        path.lineTo(0.75001740455627441406,     21.694292068481445312);
367        path.lineTo(0.75001740455627441406,     23.051967620849609375);
368        return path;
369    },
370
371    // Reduction from skbug.com/7911 that causes a crash due to splitting a
372    // zombie edge.
373    []() -> SkPath {
374        SkPath path;
375        path.moveTo(                   0, 1.0927740941146660348e+24);
376        path.lineTo(2.9333931225865729333e+32,             16476101);
377        path.lineTo(1.0927731573659435417e+24, 1.0927740941146660348e+24);
378        path.lineTo(1.0927740941146660348e+24, 3.7616281094287041715e-37);
379        path.lineTo(1.0927740941146660348e+24, 1.0927740941146660348e+24);
380        path.lineTo(1.3061803026169399536e-33, 1.0927740941146660348e+24);
381        path.lineTo(4.7195362919941370727e-16, -8.4247545146051822591e+32);
382        return path;
383    },
384
385    // From crbug.com/844873. Crashes trying to merge a zombie edge.
386    []() -> SkPath {
387        SkPath path;
388        path.moveTo( 316.000579833984375, -4338355948977389568);
389        path.lineTo(1.5069369808623501312e+20, 75180972320904708096.0);
390        path.lineTo(1.5069369808623501312e+20, 75180972320904708096.0);
391        path.lineTo(  771.21014404296875, -4338355948977389568.0);
392        path.lineTo( 316.000579833984375, -4338355948977389568.0);
393        path.moveTo(       354.208984375, -4338355948977389568.0);
394        path.lineTo(  773.00177001953125, -4338355948977389568.0);
395        path.lineTo(1.5069369808623501312e+20, 75180972320904708096.0);
396        path.lineTo(1.5069369808623501312e+20, 75180972320904708096.0);
397        path.lineTo(       354.208984375, -4338355948977389568.0);
398        return path;
399    },
400
401    // From crbug.com/844873. Hangs repeatedly splitting alternate vertices.
402    []() -> SkPath {
403        SkPath path;
404        path.moveTo(10, -1e+20f);
405        path.lineTo(11, 25000);
406        path.lineTo(10, 25000);
407        path.lineTo(11, 25010);
408        return path;
409    },
410
411    // Reduction from circular_arcs_stroke_and_fill_round GM which
412    // repeatedly splits on the opposite edge from case 34 above.
413    []() -> SkPath {
414        SkPath path;
415        path.moveTo(               16.25, 26.495191574096679688);
416        path.lineTo(32.420825958251953125, 37.377376556396484375);
417        path.lineTo(25.176382064819335938, 39.31851959228515625);
418        path.moveTo(                  20,                   20);
419        path.lineTo(28.847436904907226562, 37.940830230712890625);
420        path.lineTo(25.17638397216796875, 39.31851959228515625);
421        return path;
422    },
423
424    // Reduction from crbug.com/843135 where an intersection is found
425    // below the bottom of both intersected edges.
426    []() -> SkPath {
427        SkPath path;
428        path.moveTo(-2791476679359332352,  2608107002026524672);
429        path.lineTo(                   0, 11.95427703857421875);
430        path.lineTo(-2781824066779086848,  2599088532777598976);
431        path.lineTo(          -7772.6875,                 7274);
432        return path;
433    },
434
435    // Reduction from crbug.com/843135. Exercises a case where an intersection is missed.
436    // This causes bad ordering in the active edge list.
437    []() -> SkPath {
438        SkPath path;
439        path.moveTo(-1.0662557646016024569e+23, 9.9621425197286319718e+22);
440        path.lineTo(                -121806400,                 113805032);
441        path.lineTo(                -120098872,                 112209680);
442        path.lineTo( 6.2832999862817380468e-36,     2.9885697364807128906);
443        return path;
444    },
445
446    // Reduction from crbug.com/851409. Exercises collinear last vertex.
447    []() -> SkPath {
448        SkPath path;
449        path.moveTo(2072553216, 0);
450        path.lineTo(2072553216, 1);
451        path.lineTo(2072553472, -13.5);
452        path.lineTo(2072553216, 0);
453        path.lineTo(2072553472, -6.5);
454        return path;
455    },
456
457    // Another reduction from crbug.com/851409. Exercises two sequential collinear edges.
458    []() -> SkPath {
459        SkPath path;
460        path.moveTo(2072553216, 0);
461        path.lineTo(2072553216, 1);
462        path.lineTo(2072553472, -13);
463        path.lineTo(2072553216, 0);
464        path.lineTo(2072553472, -6);
465        path.lineTo(2072553472, -13);
466        return path;
467    },
468
469    // Reduction from crbug.com/860655. Cause is three collinear edges discovered during
470    // sanitize_contours pass, before the vertices have been found coincident.
471    []() -> SkPath {
472        SkPath path;
473        path.moveTo(   32572426382475264,    -3053391034974208);
474        path.lineTo(           521289856,            -48865776);
475        path.lineTo(           130322464,            -12215873);
476        path.moveTo(   32572426382475264,    -3053391034974208);
477        path.lineTo(           521289856,            -48865776);
478        path.lineTo(           130322464,            -12215873);
479        path.moveTo(   32572426382475264,    -3053391034974208);
480        path.lineTo(   32114477642022912,    -3010462031544320);
481        path.lineTo(   32111784697528320,    -3010209702215680);
482        return path;
483    },
484};
485
486#if SK_GPU_V1
487#include "src/gpu/ops/TriangulatingPathRenderer.h"
488#include "src/gpu/v1/SurfaceDrawContext_v1.h"
489
490// A simple concave path. Test this with a non-invertible matrix.
491static SkPath create_path_17() {
492    SkPath path;
493    path.moveTo(20, 20);
494    path.lineTo(80, 20);
495    path.lineTo(30, 30);
496    path.lineTo(20, 80);
497    return path;
498}
499
500// An intersection above the first vertex in the mesh.
501// Reduction from http://crbug.com/730687
502static SkPath create_path_20() {
503    SkPath path;
504    path.moveTo(           2822128.5,  235.026336669921875);
505    path.lineTo(          2819349.25, 235.3623504638671875);
506    path.lineTo(          -340558688, 23.83478546142578125);
507    path.lineTo(          -340558752, 25.510419845581054688);
508    path.lineTo(          -340558720, 27.18605804443359375);
509    return path;
510}
511
512// An intersection whose result is NaN (due to rounded-to-inf endpoint).
513static SkPath create_path_21() {
514    SkPath path;
515    path.moveTo(1.7889142061167663539e+38, 39338463358011572224.0);
516    path.lineTo(  1647.4193115234375,       -522.603515625);
517    path.lineTo(    1677.74560546875,   -529.0028076171875);
518    path.lineTo(    1678.29541015625,   -528.7847900390625);
519    path.lineTo(  1637.5167236328125,  -519.79266357421875);
520    path.lineTo(  1647.4193115234375,       -522.603515625);
521    return path;
522}
523
524// An edge collapse event which also collapses a neighbour, requiring
525// its event to be removed.
526static SkPath create_path_25() {
527    SkPath path;
528    path.moveTo( 43.44110107421875,  148.15106201171875);
529    path.lineTo( 44.64471435546875,  148.16748046875);
530    path.lineTo( 46.35009765625,     147.403076171875);
531    path.lineTo( 46.45404052734375,  148.34906005859375);
532    path.lineTo( 45.0400390625,      148.54205322265625);
533    path.lineTo( 44.624053955078125, 148.9810791015625);
534    path.lineTo( 44.59405517578125,  149.16107177734375);
535    path.lineTo( 44.877044677734375, 149.62005615234375);
536    path.lineTo(144.373016357421875,  68.8070068359375);
537    return path;
538}
539
540// An edge collapse event causes an edge to become collinear, requiring
541// its event to be removed.
542static SkPath create_path_26() {
543    SkPath path;
544    path.moveTo( 43.44110107421875,  148.15106201171875);
545    path.lineTo( 44.64471435546875,  148.16748046875);
546    path.lineTo( 46.35009765625,     147.403076171875);
547    path.lineTo( 46.45404052734375,  148.34906005859375);
548    path.lineTo( 45.0400390625,      148.54205322265625);
549    path.lineTo( 44.624053955078125, 148.9810791015625);
550    path.lineTo( 44.59405517578125,  149.16107177734375);
551    path.lineTo( 44.877044677734375, 149.62005615234375);
552    path.lineTo(144.373016357421875,  68.8070068359375);
553    return path;
554}
555
556// A path which results in non-finite points when stroked and bevelled for AA.
557static SkPath create_path_27() {
558     SkPath path;
559     path.moveTo(8.5027233009104409507e+37, 1.7503381025241130639e+37);
560     path.lineTo(7.0923661737711584874e+37, 1.4600074517285415699e+37);
561     path.lineTo(7.0848733446033294691e+37, 1.4584649744781838604e+37);
562     path.lineTo(-2.0473916115129349496e+37, -4.2146796450364162012e+36);
563     path.lineTo(2.0473912312177548811e+37, 4.2146815465123165435e+36);
564     return path;
565}
566
567// AA stroking this path produces intersection failures on bevelling.
568// This should skip the point, but not assert.
569static SkPath create_path_28() {
570    SkPath path;
571    path.moveTo(-7.5952312625177475154e+21, -2.6819185100266674911e+24);
572    path.lineTo(  1260.3787841796875,   1727.7947998046875);
573    path.lineTo(  1260.5567626953125,   1728.0386962890625);
574    path.lineTo(1.1482511310557754163e+21, 4.054538502765980051e+23);
575    path.lineTo(-7.5952312625177475154e+21, -2.6819185100266674911e+24);
576    return path;
577}
578
579// A path with vertices which become infinite on AA stroking. Should not crash or assert.
580static SkPath create_path_31() {
581    SkPath path;
582    path.moveTo(2.0257809259190991347e+36,  -1244080640);
583    path.conicTo(2.0257809259190991347e+36, -1244080640,
584                 2.0257809259190991347e+36, 0.10976474732160568237, 0.70710676908493041992);
585    path.lineTo(-10036566016, -1954718402215936);
586    path.conicTo(-1.1375507718551896064e+20, -1954721086570496,
587                 10036566016, -1954721086570496, 0.70710676908493041992);
588    return path;
589}
590
591// Reduction from crbug.com/851914.
592static SkPath create_path_38() {
593    SkPath path;
594    path.moveTo(14.400531768798828125, 17.711114883422851562);
595    path.lineTo(14.621990203857421875,   171563104293879808);
596    path.lineTo(14.027951240539550781,   872585759381520384);
597    path.lineTo( 14.0216827392578125,   872665817571917824);
598    path.lineTo(7.699314117431640625,    -3417320793833472);
599    path.moveTo(11.606547355651855469,       17.40966796875);
600    path.lineTo( 7642114886926860288, 21.08358001708984375);
601    path.lineTo(11.606547355651855469, 21.08358001708984375);
602    return path;
603}
604
605// Reduction from crbug.com/860453. Tests a case where a "missing" intersection
606// requires the active edge list to go out-of-order.
607static SkPath create_path_41() {
608    SkPath path;
609    path.moveTo(72154931603311689728.0,   330.95965576171875);
610    path.lineTo(24053266013925408768.0,       78.11376953125);
611    path.lineTo(1.2031099003292404941e+20,  387.168731689453125);
612    path.lineTo(68859835992355373056.0,   346.55047607421875);
613    path.lineTo(76451708695451009024.0,     337.780029296875);
614    path.moveTo(-20815817797613387776.0, 18065700622522384384.0);
615    path.lineTo(-72144121204987396096.0,  142.855804443359375);
616    path.lineTo(72144121204987396096.0,  325.184783935546875);
617    path.lineTo(1.2347242901040791552e+20, 18065700622522384384.0);
618    return path;
619}
620
621// Reduction from crbug.com/866319. Cause is edges that are collinear when tested from
622// one side, but non-collinear when tested from the other.
623static SkPath create_path_43() {
624    SkPath path;
625    path.moveTo(     307316821852160,      -28808363114496);
626    path.lineTo(     307165222928384,      -28794154909696);
627    path.lineTo(     307013691113472,      -28779948802048);
628    path.lineTo(     306862159298560,      -28765744791552);
629    path.lineTo(     306870313025536,      -28766508154880);
630    path.lineTo(     307049695019008,      -28783327313920);
631    path.lineTo(     307408660332544,      -28816974020608);
632    return path;
633}
634
635// Reduction from crbug.com/966696
636static SkPath create_path_44() {
637    SkPath path;
638    path.moveTo(114.4606170654296875,       186.443878173828125);
639    path.lineTo( 91.5394744873046875,       185.4189453125);
640    path.lineTo(306.45538330078125,        3203.986083984375);
641    path.moveTo(16276206965409972224.0,     815.59393310546875);
642    path.lineTo(-3.541605062372533207e+20,  487.7236328125);
643    path.lineTo(-3.541605062372533207e+20,  168.204071044921875);
644    path.lineTo(16276206965409972224.0,     496.07427978515625);
645    path.moveTo(-3.541605062372533207e+20,  167.00958251953125);
646    path.lineTo(-3.541605062372533207e+20,  488.32086181640625);
647    path.lineTo(16276206965409972224.0,     816.78839111328125);
648    path.lineTo(16276206965409972224.0,     495.47705078125);
649    return path;
650}
651
652// Reduction from crbug.com/966274.
653static SkPath create_path_45() {
654    SkPath path;
655    path.moveTo(        706471854080,         379003666432);
656    path.lineTo(        706503180288,         379020443648);
657    path.lineTo(        706595717120,         379070087168);
658    path.lineTo(        706626060288,         379086372864);
659    path.lineTo(        706656141312,         379102527488);
660    path.lineTo(        706774171648,         379165835264);
661    path.lineTo(        706803073024,         379181334528);
662    path.lineTo(        706831712256,         379196702720);
663    path.lineTo(        706860154880,         379211939840);
664    path.lineTo(        706888335360,         379227078656);
665    path.lineTo(        706916253696,         379242053632);
666    path.lineTo(        706956820480,         379263811584);
667    path.lineTo(        706929098752,         379248934912);
668    path.lineTo(        706901114880,         379233927168);
669    path.lineTo(        706872934400,         379218821120);
670    path.lineTo(        706844491776,         379203551232);
671    path.lineTo(        706815787008,         379188183040);
672    path.lineTo(        706786885632,         379172651008);
673    path.lineTo(        706757722112,         379156987904);
674    path.lineTo(        706728296448,         379141226496);
675    path.lineTo(        706698608640,         379125301248);
676    path.lineTo(        706668724224,         379109244928);
677    path.lineTo(        706638577664,         379093090304);
678    path.lineTo(        706608168960,         379076771840);
679    path.lineTo(        706484174848,         379010252800);
680    return path;
681}
682
683// Reduction from crbug.com/969359. Inf generated by intersections
684// causes NaN in subsequent intersections, leading to assert or hang.
685
686static SkPath create_path_46() {
687    SkPath path;
688    path.moveTo(1.0321827899075254821e+37, -5.1199920965387697886e+37);
689    path.lineTo(-1.0321827899075254821e+37, 5.1199920965387697886e+37);
690    path.lineTo(-1.0425214946728668754e+37, 4.5731834042267216669e+37);
691    path.moveTo(-9.5077331762291841872e+36, 8.1304868292377430302e+37);
692    path.lineTo(9.5077331762291841872e+36, -8.1304868292377430302e+37);
693    path.lineTo(1.0795449417808426232e+37, 1.2246856113744539311e+37);
694    path.moveTo(-165.8018341064453125,           -44.859375);
695    path.lineTo(-9.558702871563160835e+36, -7.9814405281448285475e+37);
696    path.lineTo(-9.4147814283168490381e+36, -8.3935116522790983488e+37);
697    return path;
698}
699
700static std::unique_ptr<GrFragmentProcessor> create_linear_gradient_processor(
701            GrRecordingContext* rContext) {
702
703    SkPoint pts[2] = { {0, 0}, {1, 1} };
704    SkColor colors[2] = { SK_ColorGREEN, SK_ColorBLUE };
705    sk_sp<SkShader> shader = SkGradientShader::MakeLinear(
706        pts, colors, nullptr, SK_ARRAY_COUNT(colors), SkTileMode::kClamp);
707    GrColorInfo colorInfo(GrColorType::kRGBA_8888, kPremul_SkAlphaType, nullptr);
708    SkSimpleMatrixProvider matrixProvider(SkMatrix::I());
709    return as_SB(shader)->asFragmentProcessor({rContext, matrixProvider, &colorInfo});
710}
711
712static void test_path(GrRecordingContext* rContext,
713                      skgpu::v1::SurfaceDrawContext* sdc,
714                      const SkPath& path,
715                      const SkMatrix& matrix = SkMatrix::I(),
716                      GrAAType aaType = GrAAType::kNone,
717                      std::unique_ptr<GrFragmentProcessor> fp = nullptr) {
718    skgpu::v1::TriangulatingPathRenderer pr;
719    pr.setMaxVerbCount(100);
720
721    GrPaint paint;
722    paint.setXPFactory(GrPorterDuffXPFactory::Get(SkBlendMode::kSrc));
723    if (fp) {
724        paint.setColorFragmentProcessor(std::move(fp));
725    }
726
727    SkIRect clipConservativeBounds = SkIRect::MakeWH(sdc->width(), sdc->height());
728    GrStyle style(SkStrokeRec::kFill_InitStyle);
729    GrStyledShape shape(path, style);
730    skgpu::v1::PathRenderer::DrawPathArgs args{rContext,
731                                               std::move(paint),
732                                               &GrUserStencilSettings::kUnused,
733                                               sdc,
734                                               nullptr,
735                                               &clipConservativeBounds,
736                                               &matrix,
737                                               &shape,
738                                               aaType,
739                                               false};
740    pr.drawPath(args);
741}
742
743DEF_GPUTEST_FOR_ALL_CONTEXTS(TriangulatingPathRendererTests, reporter, ctxInfo) {
744    auto ctx = ctxInfo.directContext();
745    auto sdc = skgpu::v1::SurfaceDrawContext::Make(
746            ctx, GrColorType::kRGBA_8888, nullptr, SkBackingFit::kApprox, {800, 800},
747            SkSurfaceProps(), 1, GrMipmapped::kNo, GrProtected::kNo, kTopLeft_GrSurfaceOrigin);
748    if (!sdc) {
749        return;
750    }
751
752    ctx->flushAndSubmit();
753    // Adding discard to appease vulkan validation warning about loading uninitialized data on draw
754    sdc->discard();
755
756    for (CreatePathFn createPath : kNonEdgeAAPaths) {
757        test_path(ctx, sdc.get(), createPath());
758    }
759    SkMatrix nonInvertibleMatrix = SkMatrix::Scale(0, 0);
760    std::unique_ptr<GrFragmentProcessor> fp(create_linear_gradient_processor(ctx));
761    test_path(ctx, sdc.get(), create_path_17(), nonInvertibleMatrix, GrAAType::kCoverage,
762              std::move(fp));
763    test_path(ctx, sdc.get(), create_path_20(), SkMatrix(), GrAAType::kCoverage);
764    test_path(ctx, sdc.get(), create_path_21(), SkMatrix(), GrAAType::kCoverage);
765    test_path(ctx, sdc.get(), create_path_25(), SkMatrix(), GrAAType::kCoverage);
766    test_path(ctx, sdc.get(), create_path_26(), SkMatrix(), GrAAType::kCoverage);
767    test_path(ctx, sdc.get(), create_path_27(), SkMatrix(), GrAAType::kCoverage);
768    test_path(ctx, sdc.get(), create_path_28(), SkMatrix(), GrAAType::kCoverage);
769    test_path(ctx, sdc.get(), create_path_31(), SkMatrix(), GrAAType::kCoverage);
770    test_path(ctx, sdc.get(), create_path_38(), SkMatrix(), GrAAType::kCoverage);
771    test_path(ctx, sdc.get(), create_path_41(), SkMatrix(), GrAAType::kCoverage);
772    test_path(ctx, sdc.get(), create_path_43(), SkMatrix(), GrAAType::kCoverage);
773    test_path(ctx, sdc.get(), create_path_44(), SkMatrix(), GrAAType::kCoverage);
774    test_path(ctx, sdc.get(), create_path_45(), SkMatrix(), GrAAType::kCoverage);
775    test_path(ctx, sdc.get(), create_path_46(), SkMatrix(), GrAAType::kCoverage);
776}
777
778#endif // SK_GPU_V1
779
780namespace {
781
782class SimpleVertexAllocator : public GrEagerVertexAllocator {
783public:
784    void* lock(size_t stride, int eagerCount) override {
785        SkASSERT(!fPoints);
786        SkASSERT(stride == sizeof(SkPoint));
787        fPoints.reset(eagerCount);
788        return fPoints;
789    }
790    void unlock(int actualCount) override {}
791    SkPoint operator[](int idx) const { return fPoints[idx]; }
792    SkAutoTMalloc<SkPoint> fPoints;
793};
794
795}  // namespace
796
797struct Edge {
798    Edge reverse() const { return {fP1, fP0}; }
799    SkPoint fP0, fP1;
800};
801
802static bool operator<(const Edge& a, const Edge& b) {
803    if (a.fP0.fX != b.fP0.fX) {
804        return a.fP0.fX < b.fP0.fX;
805    }
806    if (a.fP0.fY != b.fP0.fY) {
807        return a.fP0.fY < b.fP0.fY;
808    }
809    if (a.fP1.fX != b.fP1.fX) {
810        return a.fP1.fX < b.fP1.fX;
811    }
812    if (a.fP1.fY != b.fP1.fY) {
813        return a.fP1.fY < b.fP1.fY;
814    }
815    return false;
816}
817
818using EdgeMap = std::map<Edge, int>;
819
820static void add_edge(EdgeMap& edgeMap, SkPoint p0, SkPoint p1) {
821    Edge edge{p0, p1};
822    // First check if this edge already exists in reverse.
823    auto reverseIter = edgeMap.find(edge.reverse());
824    if (reverseIter != edgeMap.end()) {
825        --reverseIter->second;
826    } else {
827        ++edgeMap[edge];
828    }
829}
830
831static void add_tri_edges(skiatest::Reporter* r, EdgeMap& edgeMap, const SkPoint pts[3]) {
832    for (int i = 0; i < 3; ++i) {
833        SkPoint p0=pts[i], p1=pts[(i+1)%3];
834        // The triangulator shouldn't output degenerate triangles.
835        REPORTER_ASSERT(r, p0 != p1);
836        add_edge(edgeMap, p0, p1);
837    }
838}
839
840static EdgeMap simplify(const EdgeMap& edges, SkPathFillType fillType) {
841    // Prune out the edges whose count went to zero, and reverse the edges whose count is negative.
842    EdgeMap simplifiedEdges;
843    for (auto [edge, count] : edges) {
844        // We should only have one ordering of any given edge.
845        SkASSERT(edges.find(edge.reverse()) == edges.end());
846        if (fillType == SkPathFillType::kEvenOdd) {
847            count = abs(count) & 1;
848        }
849        if (count > 0) {
850            simplifiedEdges[edge] = count;
851        } else if (count < 0) {
852            simplifiedEdges[edge.reverse()] = -count;
853        }
854    }
855    return simplifiedEdges;
856}
857
858static void verify_simple_inner_polygons(skiatest::Reporter* r, const char* shapeName,
859                                         SkPath path) {
860    for (auto fillType : {SkPathFillType::kWinding}) {
861        path.setFillType(fillType);
862        SkArenaAlloc arena(GrTriangulator::kArenaDefaultChunkSize);
863        GrInnerFanTriangulator::BreadcrumbTriangleList breadcrumbs;
864        SimpleVertexAllocator vertexAlloc;
865        int vertexCount;
866        {
867            bool isLinear;
868            GrInnerFanTriangulator triangulator(path, &arena);
869            vertexCount = triangulator.pathToTriangles(&vertexAlloc, &breadcrumbs, &isLinear);
870        }
871
872        // Count up all the triangulated edges.
873        EdgeMap trianglePlusBreadcrumbEdges;
874        for (int i = 0; i < vertexCount; i += 3) {
875            add_tri_edges(r, trianglePlusBreadcrumbEdges, vertexAlloc.fPoints.data() + i);
876        }
877        // Count up all the breadcrumb edges.
878        int breadcrumbCount = 0;
879        for (const auto* node = breadcrumbs.head(); node; node = node->fNext) {
880            add_tri_edges(r, trianglePlusBreadcrumbEdges, node->fPts);
881            ++breadcrumbCount;
882        }
883        REPORTER_ASSERT(r, breadcrumbCount == breadcrumbs.count());
884        // The triangulated + breadcrumb edges should cancel out to the inner polygon edges.
885        trianglePlusBreadcrumbEdges = simplify(trianglePlusBreadcrumbEdges, path.getFillType());
886
887        // Build the inner polygon edges.
888        EdgeMap innerFanEdges;
889        SkPoint startPoint{}, lastPoint{};
890        for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
891            switch (verb) {
892                case SkPathVerb::kMove:
893                    if (lastPoint != startPoint) {
894                        add_edge(innerFanEdges, lastPoint, startPoint);
895                    }
896                    lastPoint = startPoint = pts[0];
897                    continue;
898                case SkPathVerb::kClose:
899                    lastPoint = startPoint;
900                    break;
901                case SkPathVerb::kLine:
902                    lastPoint = pts[1];
903                    break;
904                case SkPathVerb::kQuad:
905                case SkPathVerb::kConic:
906                    lastPoint = pts[2];
907                    break;
908                case SkPathVerb::kCubic:
909                    lastPoint = pts[3];
910                    break;
911            }
912            if (pts[0] != lastPoint) {
913                add_edge(innerFanEdges, pts[0], lastPoint);
914            }
915        }
916        if (lastPoint != startPoint) {
917            add_edge(innerFanEdges, lastPoint, startPoint);
918        }
919        innerFanEdges = simplify(innerFanEdges, path.getFillType());
920
921        // The triangulated + breadcrumb edges should cancel out to the inner polygon edges. First
922        // verify that every inner polygon edge can be found in the triangulation.
923        for (auto [edge, count] : innerFanEdges) {
924            auto it = trianglePlusBreadcrumbEdges.find(edge);
925            if (it != trianglePlusBreadcrumbEdges.end()) {
926                it->second -= count;
927                if (it->second == 0) {
928                    trianglePlusBreadcrumbEdges.erase(it);
929                }
930                continue;
931            }
932            it = trianglePlusBreadcrumbEdges.find(edge.reverse());
933            if (it != trianglePlusBreadcrumbEdges.end()) {
934                it->second += count;
935                if (it->second == 0) {
936                    trianglePlusBreadcrumbEdges.erase(it);
937                }
938                continue;
939            }
940            ERRORF(r, "error: %s: edge [%g,%g]:[%g,%g] not found in triangulation.",
941                   shapeName, edge.fP0.fX, edge.fP0.fY, edge.fP1.fX, edge.fP1.fY);
942            return;
943        }
944        // Now verify that there are no spurious edges in the triangulation.
945        //
946        // NOTE: The triangulator's definition of wind isn't always correct for edges that run
947        // exactly parallel to the sweep (either vertical or horizontal edges). This doesn't
948        // actually matter though because T-junction artifacts don't happen on axis-aligned edges.
949        // Tolerate spurious edges that (1) come in pairs of 2, and (2) are either exactly
950        // horizontal or exactly vertical exclusively.
951        bool hasSpuriousHorz=false, hasSpuriousVert=false;
952        for (auto [edge, count] : trianglePlusBreadcrumbEdges) {
953            if (count % 2 == 0) {
954                if (edge.fP0.fX == edge.fP1.fX && !hasSpuriousVert) {
955                    hasSpuriousHorz = true;
956                    continue;
957                }
958                if (edge.fP0.fY == edge.fP1.fY && !hasSpuriousHorz) {
959                    hasSpuriousVert = true;
960                    continue;
961                }
962            }
963            ERRORF(r, "error: %s: spurious edge [%g,%g]:[%g,%g] found in triangulation.",
964                   shapeName, edge.fP0.fX, edge.fP0.fY, edge.fP1.fX, edge.fP1.fY);
965            return;
966        }
967    }
968}
969
970DEF_TEST(GrInnerFanTriangulator, r) {
971    verify_simple_inner_polygons(r, "simple triangle", SkPath().lineTo(1,0).lineTo(0,1));
972    verify_simple_inner_polygons(r, "simple square", SkPath().lineTo(1,0).lineTo(1,1).lineTo(0,1));
973    verify_simple_inner_polygons(r,  "concave polygon", SkPath()
974            .lineTo(1,0).lineTo(.5f,.5f).lineTo(1,1).lineTo(0,1));
975    verify_simple_inner_polygons(r, "double wound triangle", SkPath()
976            .lineTo(1,0).lineTo(0,1).lineTo(0,0).lineTo(1,0).lineTo(0,1));
977    verify_simple_inner_polygons(r, "self-intersecting bowtie", SkPath()
978            .lineTo(1,0).lineTo(0,1).lineTo(1,1));
979    verify_simple_inner_polygons(r, "asymmetrical bowtie", SkPath()
980            .lineTo(1,0).lineTo(0,1).lineTo(.1f,-.1f));
981    verify_simple_inner_polygons(r, "bowtie with extremely small section", SkPath()
982            .lineTo(1,0).lineTo(0,1).lineTo(1e-6f,-1e-6f));
983    verify_simple_inner_polygons(r, "intersecting squares", SkPath()
984            .lineTo(1,0).lineTo(1,1).lineTo(0,1)
985            .moveTo(.5f,.5f).lineTo(1.5f,.5f).lineTo(1.5f,1.5f).lineTo(.5f,1.5f).close());
986    verify_simple_inner_polygons(r, "6-point \"Star of David\"", SkPath()
987            .moveTo(cosf(-SK_ScalarPI/3), sinf(-SK_ScalarPI/3))
988            .lineTo(cosf(SK_ScalarPI/3), sinf(SK_ScalarPI/3))
989            .lineTo(cosf(SK_ScalarPI), sinf(SK_ScalarPI))
990            .moveTo(cosf(0), sinf(0))
991            .lineTo(cosf(2*SK_ScalarPI/3), sinf(2*SK_ScalarPI/3))
992            .lineTo(cosf(-2*SK_ScalarPI/3), sinf(-2*SK_ScalarPI/3)));
993    verify_simple_inner_polygons(r, "double wound \"Star of David\"", SkPath()
994            .moveTo(cosf(-SK_ScalarPI/3), sinf(-SK_ScalarPI/3))
995            .lineTo(cosf(SK_ScalarPI/3), sinf(SK_ScalarPI/3))
996            .lineTo(cosf(SK_ScalarPI), sinf(SK_ScalarPI))
997            .lineTo(cosf(-SK_ScalarPI/3), sinf(-SK_ScalarPI/3))
998            .lineTo(cosf(SK_ScalarPI/3), sinf(SK_ScalarPI/3))
999            .lineTo(cosf(SK_ScalarPI), sinf(SK_ScalarPI))
1000            .moveTo(cosf(0), sinf(0))
1001            .lineTo(cosf(2*SK_ScalarPI/3), sinf(2*SK_ScalarPI/3))
1002            .lineTo(cosf(-2*SK_ScalarPI/3), sinf(-2*SK_ScalarPI/3)));
1003    verify_simple_inner_polygons(r, "5-point star", ToolUtils::make_star(SkRect::MakeWH(100, 200)));
1004    verify_simple_inner_polygons(r, "\"pointy\" intersecting triangles", SkPath()
1005            .moveTo(0,-100).lineTo(-1e-6f,100).lineTo(1e-6f,100)
1006            .moveTo(-100,0).lineTo(100,1e-6f).lineTo(100,-1e-6f));
1007    verify_simple_inner_polygons(r, "overlapping rects with vertical collinear edges", SkPath()
1008            .moveTo(0,0).lineTo(0,2).lineTo(1,2).lineTo(1,0)
1009            .moveTo(0,1).lineTo(0,3).lineTo(1,3).lineTo(1,1));
1010    verify_simple_inner_polygons(r, "overlapping rects with horizontal collinear edges", SkPath()
1011            .lineTo(2,0).lineTo(2,1).lineTo(0,1)
1012            .moveTo(1,0).lineTo(3,0).lineTo(3,1).lineTo(1,1).close());
1013    for (int i = 0; i < (int)SK_ARRAY_COUNT(kNonEdgeAAPaths); ++i) {
1014        verify_simple_inner_polygons(r, SkStringPrintf("kNonEdgeAAPaths[%i]", i).c_str(),
1015                                     kNonEdgeAAPaths[i]());
1016    }
1017    SkRandom rand;
1018    for (int i = 0; i < 50; ++i) {
1019        auto randomPath = SkPath().moveTo(rand.nextF(), rand.nextF());
1020        for (int j = 0; j < i; ++j) {
1021            randomPath.lineTo(rand.nextF(), rand.nextF());
1022        }
1023        verify_simple_inner_polygons(r, SkStringPrintf("random_path_%i", i).c_str(), randomPath);
1024    }
1025}
1026