1 /* This file is part of the KDE project
2    Copyright (C) 2002, 2003 The Karbon Developers
3                  2006       Alexander Kellett <lypanov@kde.org>
4                  2006, 2007 Rob Buis <buis@kde.org>
5                  2007       Apple, Inc.  All rights reserved.
6 
7    This library is free software; you can redistribute it and/or
8    modify it under the terms of the GNU Library General Public
9    License as published by the Free Software Foundation; either
10    version 2 of the License, or (at your option) any later version.
11 
12    This library is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15    Library General Public License for more details.
16 
17    You should have received a copy of the GNU Library General Public License
18    along with this library; see the file COPYING.LIB.  If not, write to
19    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20    Boston, MA 02110-1301, USA.
21 */
22 
23 #include "wtf/Platform.h"
24 #if ENABLE(SVG)
25 #include "xml/Document.h"
26 #include "SVGParserUtilities.h"
27 
28 #include "ExceptionCode.h"
29 #include "FloatConversion.h"
30 #include "FloatPoint.h"
31 #include "Path.h"
32 #include "PlatformString.h"
33 #include "SVGPathSegList.h"
34 #include "SVGPathSegArc.h"
35 #include "SVGPathSegClosePath.h"
36 #include "SVGPathSegCurvetoCubic.h"
37 #include "SVGPathSegCurvetoCubicSmooth.h"
38 #include "SVGPathSegCurvetoQuadratic.h"
39 #include "SVGPathSegCurvetoQuadraticSmooth.h"
40 #include "SVGPathSegLineto.h"
41 #include "SVGPathSegLinetoHorizontal.h"
42 #include "SVGPathSegLinetoVertical.h"
43 #include "SVGPathSegList.h"
44 #include "SVGPathSegMoveto.h"
45 #include "SVGPointList.h"
46 #include "SVGPathElement.h"
47 #include <math.h>
48 #include <wtf/MathExtras.h>
49 
50 namespace WebCore
51 {
52 
53 /* We use this generic _parseNumber function to allow the Path parsing code to work
54  * at a higher precision internally, without any unnecessary runtime cost or code
55  * complexity
56  */
_parseNumber(const UChar * & ptr,const UChar * end,FloatType & number,bool skip)57 template <typename FloatType> static bool _parseNumber(const UChar *&ptr, const UChar *end, FloatType &number, bool skip)
58 {
59     int integer, exponent;
60     FloatType decimal, frac;
61     int sign, expsign;
62     const UChar *start = ptr;
63 
64     exponent = 0;
65     integer = 0;
66     frac = 1;
67     decimal = 0;
68     sign = 1;
69     expsign = 1;
70 
71     // read the sign
72     if (ptr < end && *ptr == '+') {
73         ptr++;
74     } else if (ptr < end && *ptr == '-') {
75         ptr++;
76         sign = -1;
77     }
78 
79     if (ptr == end || ((*ptr < '0' || *ptr > '9') && *ptr != '.'))
80         // The first character of a number must be one of [0-9+-.]
81     {
82         return false;
83     }
84 
85     // read the integer part
86     while (ptr < end && *ptr >= '0' && *ptr <= '9') {
87         integer = (integer * 10) + (ptr++)->unicode() - '0';
88     }
89 
90     if (ptr < end && *ptr == '.') { // read the decimals
91         ptr++;
92 
93         // There must be a least one digit following the .
94         if (ptr >= end || *ptr < '0' || *ptr > '9') {
95             return false;
96         }
97 
98         while (ptr < end && *ptr >= '0' && *ptr <= '9') {
99             decimal += ((ptr++)->unicode() - '0') * (frac *= static_cast<FloatType>(0.1));
100         }
101     }
102 
103     // read the exponent part
104     if (ptr != start && ptr + 1 < end && (*ptr == 'e' || *ptr == 'E')
105             && (ptr[1] != 'x' && ptr[1] != 'm')) {
106         ptr++;
107 
108         // read the sign of the exponent
109         if (*ptr == '+') {
110             ptr++;
111         } else if (*ptr == '-') {
112             ptr++;
113             expsign = -1;
114         }
115 
116         // There must be an exponent
117         if (ptr >= end || *ptr < '0' || *ptr > '9') {
118             return false;
119         }
120 
121         while (ptr < end && *ptr >= '0' && *ptr <= '9') {
122             exponent *= 10;
123             exponent += ptr->unicode() - '0';
124             ptr++;
125         }
126     }
127 
128     number = integer + decimal;
129     number *= sign * static_cast<FloatType>(pow(10.0, expsign * exponent));
130 
131     if (start == ptr) {
132         return false;
133     }
134 
135     if (skip) {
136         skipOptionalSpacesOrDelimiter(ptr, end);
137     }
138 
139     return true;
140 }
141 
parseNumber(const UChar * & ptr,const UChar * end,float & number,bool skip)142 bool parseNumber(const UChar *&ptr, const UChar *end, float &number, bool skip)
143 {
144     return _parseNumber(ptr, end, number, skip);
145 }
146 
147 // Only used for parsing Paths
parseNumber(const UChar * & ptr,const UChar * end,double & number,bool skip=true)148 static bool parseNumber(const UChar *&ptr, const UChar *end, double &number, bool skip = true)
149 {
150     return _parseNumber(ptr, end, number, skip);
151 }
152 
parseNumberOptionalNumber(const String & s,float & x,float & y)153 bool parseNumberOptionalNumber(const String &s, float &x, float &y)
154 {
155     if (s.isEmpty()) {
156         return false;
157     }
158     const UChar *cur = s.characters();
159     const UChar *end = cur + s.length();
160 
161     if (!parseNumber(cur, end, x)) {
162         return false;
163     }
164 
165     if (cur == end) {
166         y = x;
167     } else if (!parseNumber(cur, end, y, false)) {
168         return false;
169     }
170 
171     return cur == end;
172 }
173 
pointsListFromSVGData(SVGPointList * pointsList,const String & points)174 bool pointsListFromSVGData(SVGPointList *pointsList, const String &points)
175 {
176     if (points.isEmpty()) {
177         return true;
178     }
179     const UChar *cur = points.characters();
180     const UChar *end = cur + points.length();
181 
182     skipOptionalSpaces(cur, end);
183 
184     bool delimParsed = false;
185     while (cur < end) {
186         delimParsed = false;
187         float xPos = 0.0f;
188         if (!parseNumber(cur, end, xPos)) {
189             return false;
190         }
191 
192         float yPos = 0.0f;
193         if (!parseNumber(cur, end, yPos, false)) {
194             return false;
195         }
196 
197         skipOptionalSpaces(cur, end);
198 
199         if (cur < end && *cur == ',') {
200             delimParsed = true;
201             cur++;
202         }
203         skipOptionalSpaces(cur, end);
204 
205         ExceptionCode ec = 0;
206         pointsList->appendItem(FloatPoint(xPos, yPos), ec);
207     }
208     return cur == end && !delimParsed;
209 }
210 
211 /**
212  * Parser for svg path data, contained in the d attribute.
213  *
214  * The parser delivers encountered commands and parameters by calling
215  * methods that correspond to those commands. Clients have to derive
216  * from this class and implement the abstract command methods.
217  *
218  * There are two operating modes. By default the parser just delivers unaltered
219  * svg path data commands and parameters. In the second mode, it will convert all
220  * relative coordinates to absolute ones, and convert all curves to cubic beziers.
221  */
222 class SVGPathParser
223 {
224 public:
~SVGPathParser()225     virtual ~SVGPathParser() { }
226     bool parseSVG(const String &d, bool process = false);
227 
228 protected:
229     virtual void svgMoveTo(double x1, double y1, bool closed, bool abs = true) = 0;
230     virtual void svgLineTo(double x1, double y1, bool abs = true) = 0;
svgLineToHorizontal(double x,bool abs=true)231     virtual void svgLineToHorizontal(double x, bool abs = true)
232     {
233         Q_UNUSED(x);
234         Q_UNUSED(abs);
235     }
svgLineToVertical(double y,bool abs=true)236     virtual void svgLineToVertical(double y, bool abs = true)
237     {
238         Q_UNUSED(y);
239         Q_UNUSED(abs);
240     }
241     virtual void svgCurveToCubic(double x1, double y1, double x2, double y2, double x, double y, bool abs = true) = 0;
svgCurveToCubicSmooth(double x,double y,double x2,double y2,bool abs=true)242     virtual void svgCurveToCubicSmooth(double x, double y, double x2, double y2, bool abs = true)
243     {
244         Q_UNUSED(x);
245         Q_UNUSED(y);
246         Q_UNUSED(x2);
247         Q_UNUSED(y2);
248         Q_UNUSED(abs);
249     }
svgCurveToQuadratic(double x,double y,double x1,double y1,bool abs=true)250     virtual void svgCurveToQuadratic(double x, double y, double x1, double y1, bool abs = true)
251     {
252         Q_UNUSED(x);
253         Q_UNUSED(y);
254         Q_UNUSED(x1);
255         Q_UNUSED(y1);
256         Q_UNUSED(abs);
257     }
svgCurveToQuadraticSmooth(double x,double y,bool abs=true)258     virtual void svgCurveToQuadraticSmooth(double x, double y, bool abs = true)
259     {
260         Q_UNUSED(x);
261         Q_UNUSED(y);
262         Q_UNUSED(abs);
263     }
svgArcTo(double x,double y,double r1,double r2,double angle,bool largeArcFlag,bool sweepFlag,bool abs=true)264     virtual void svgArcTo(double x, double y, double r1, double r2, double angle, bool largeArcFlag, bool sweepFlag, bool abs = true)
265     {
266         Q_UNUSED(x);
267         Q_UNUSED(y);
268         Q_UNUSED(r1);
269         Q_UNUSED(r2);
270         Q_UNUSED(angle);
271         Q_UNUSED(largeArcFlag);
272         Q_UNUSED(sweepFlag);
273         Q_UNUSED(abs);
274     }
275     virtual void svgClosePath() = 0;
276 private:
277     void calculateArc(bool relative, double &curx, double &cury, double angle, double x, double y, double r1, double r2, bool largeArcFlag, bool sweepFlag);
278 };
279 
parseSVG(const String & s,bool process)280 bool SVGPathParser::parseSVG(const String &s, bool process)
281 {
282     if (s.isEmpty()) {
283         return false;
284     }
285 
286     const UChar *ptr = s.characters();
287     const UChar *end = ptr + s.length();
288 
289     double contrlx, contrly, curx, cury, subpathx, subpathy, tox, toy, x1, y1, x2, y2, xc, yc;
290     double px1, py1, px2, py2, px3, py3;
291     bool closed = true;
292 
293     if (!skipOptionalSpaces(ptr, end)) { // skip any leading spaces
294         return false;
295     }
296 
297     char command = (ptr++)->unicode(), lastCommand = ' ';// or toLatin1() instead of unicode()???
298     if (command != 'm' && command != 'M') { // path must start with moveto
299         return false;
300     }
301 
302     subpathx = subpathy = curx = cury = contrlx = contrly = 0.0;
303     while (1) {
304         skipOptionalSpaces(ptr, end); // skip spaces between command and first coord
305 
306         bool relative = false;
307 
308         switch (command) {
309         case 'm':
310             relative = true;
311         case 'M': {
312             if (!parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy)) {
313                 return false;
314             }
315 
316             if (process) {
317                 subpathx = curx = relative ? curx + tox : tox;
318                 subpathy = cury = relative ? cury + toy : toy;
319 
320                 svgMoveTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury), closed);
321             } else {
322                 svgMoveTo(narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), closed, !relative);
323             }
324             closed = false;
325             break;
326         }
327         case 'l':
328             relative = true;
329         case 'L': {
330             if (!parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy)) {
331                 return false;
332             }
333 
334             if (process) {
335                 curx = relative ? curx + tox : tox;
336                 cury = relative ? cury + toy : toy;
337 
338                 svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
339             } else {
340                 svgLineTo(narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
341             }
342             break;
343         }
344         case 'h': {
345             if (!parseNumber(ptr, end, tox)) {
346                 return false;
347             }
348             if (process) {
349                 curx = curx + tox;
350                 svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
351             } else {
352                 svgLineToHorizontal(narrowPrecisionToFloat(tox), false);
353             }
354             break;
355         }
356         case 'H': {
357             if (!parseNumber(ptr, end, tox)) {
358                 return false;
359             }
360             if (process) {
361                 curx = tox;
362                 svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
363             } else {
364                 svgLineToHorizontal(narrowPrecisionToFloat(tox));
365             }
366             break;
367         }
368         case 'v': {
369             if (!parseNumber(ptr, end, toy)) {
370                 return false;
371             }
372             if (process) {
373                 cury = cury + toy;
374                 svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
375             } else {
376                 svgLineToVertical(narrowPrecisionToFloat(toy), false);
377             }
378             break;
379         }
380         case 'V': {
381             if (!parseNumber(ptr, end, toy)) {
382                 return false;
383             }
384             if (process) {
385                 cury = toy;
386                 svgLineTo(narrowPrecisionToFloat(curx), narrowPrecisionToFloat(cury));
387             } else {
388                 svgLineToVertical(narrowPrecisionToFloat(toy));
389             }
390             break;
391         }
392         case 'z':
393         case 'Z': {
394             // reset curx, cury for next path
395             if (process) {
396                 curx = subpathx;
397                 cury = subpathy;
398             }
399             closed = true;
400             svgClosePath();
401             break;
402         }
403         case 'c':
404             relative = true;
405         case 'C': {
406             if (!parseNumber(ptr, end, x1)  || !parseNumber(ptr, end, y1) ||
407                     !parseNumber(ptr, end, x2)  || !parseNumber(ptr, end, y2) ||
408                     !parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy)) {
409                 return false;
410             }
411 
412             if (process) {
413                 px1 = relative ? curx + x1 : x1;
414                 py1 = relative ? cury + y1 : y1;
415                 px2 = relative ? curx + x2 : x2;
416                 py2 = relative ? cury + y2 : y2;
417                 px3 = relative ? curx + tox : tox;
418                 py3 = relative ? cury + toy : toy;
419 
420                 svgCurveToCubic(narrowPrecisionToFloat(px1), narrowPrecisionToFloat(py1), narrowPrecisionToFloat(px2),
421                                 narrowPrecisionToFloat(py2), narrowPrecisionToFloat(px3), narrowPrecisionToFloat(py3));
422 
423                 contrlx = relative ? curx + x2 : x2;
424                 contrly = relative ? cury + y2 : y2;
425                 curx = relative ? curx + tox : tox;
426                 cury = relative ? cury + toy : toy;
427             } else
428                 svgCurveToCubic(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1), narrowPrecisionToFloat(x2),
429                                 narrowPrecisionToFloat(y2), narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
430 
431             break;
432         }
433         case 's':
434             relative = true;
435         case 'S': {
436             if (!parseNumber(ptr, end, x2)  || !parseNumber(ptr, end, y2) ||
437                     !parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy)) {
438                 return false;
439             }
440 
441             if (!(lastCommand == 'c' || lastCommand == 'C' ||
442                     lastCommand == 's' || lastCommand == 'S')) {
443                 contrlx = curx;
444                 contrly = cury;
445             }
446 
447             if (process) {
448                 px1 = 2 * curx - contrlx;
449                 py1 = 2 * cury - contrly;
450                 px2 = relative ? curx + x2 : x2;
451                 py2 = relative ? cury + y2 : y2;
452                 px3 = relative ? curx + tox : tox;
453                 py3 = relative ? cury + toy : toy;
454 
455                 svgCurveToCubic(narrowPrecisionToFloat(px1), narrowPrecisionToFloat(py1), narrowPrecisionToFloat(px2),
456                                 narrowPrecisionToFloat(py2), narrowPrecisionToFloat(px3), narrowPrecisionToFloat(py3));
457 
458                 contrlx = relative ? curx + x2 : x2;
459                 contrly = relative ? cury + y2 : y2;
460                 curx = relative ? curx + tox : tox;
461                 cury = relative ? cury + toy : toy;
462             } else
463                 svgCurveToCubicSmooth(narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2),
464                                       narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
465             break;
466         }
467         case 'q':
468             relative = true;
469         case 'Q': {
470             if (!parseNumber(ptr, end, x1)  || !parseNumber(ptr, end, y1) ||
471                     !parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy)) {
472                 return false;
473             }
474 
475             if (process) {
476                 px1 = relative ? (curx + 2 * (x1 + curx)) * (1.0 / 3.0) : (curx + 2 * x1) * (1.0 / 3.0);
477                 py1 = relative ? (cury + 2 * (y1 + cury)) * (1.0 / 3.0) : (cury + 2 * y1) * (1.0 / 3.0);
478                 px2 = relative ? ((curx + tox) + 2 * (x1 + curx)) * (1.0 / 3.0) : (tox + 2 * x1) * (1.0 / 3.0);
479                 py2 = relative ? ((cury + toy) + 2 * (y1 + cury)) * (1.0 / 3.0) : (toy + 2 * y1) * (1.0 / 3.0);
480                 px3 = relative ? curx + tox : tox;
481                 py3 = relative ? cury + toy : toy;
482 
483                 svgCurveToCubic(narrowPrecisionToFloat(px1), narrowPrecisionToFloat(py1), narrowPrecisionToFloat(px2),
484                                 narrowPrecisionToFloat(py2), narrowPrecisionToFloat(px3), narrowPrecisionToFloat(py3));
485 
486                 contrlx = relative ? curx + x1 : x1;
487                 contrly = relative ? cury + y1 : y1;
488                 curx = relative ? curx + tox : tox;
489                 cury = relative ? cury + toy : toy;
490             } else
491                 svgCurveToQuadratic(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
492                                     narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
493             break;
494         }
495         case 't':
496             relative = true;
497         case 'T': {
498             if (!parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy)) {
499                 return false;
500             }
501             if (!(lastCommand == 'q' || lastCommand == 'Q' ||
502                     lastCommand == 't' || lastCommand == 'T')) {
503                 contrlx = curx;
504                 contrly = cury;
505             }
506 
507             if (process) {
508                 xc = 2 * curx - contrlx;
509                 yc = 2 * cury - contrly;
510 
511                 px1 = relative ? (curx + 2 * xc) * (1.0 / 3.0) : (curx + 2 * xc) * (1.0 / 3.0);
512                 py1 = relative ? (cury + 2 * yc) * (1.0 / 3.0) : (cury + 2 * yc) * (1.0 / 3.0);
513                 px2 = relative ? ((curx + tox) + 2 * xc) * (1.0 / 3.0) : (tox + 2 * xc) * (1.0 / 3.0);
514                 py2 = relative ? ((cury + toy) + 2 * yc) * (1.0 / 3.0) : (toy + 2 * yc) * (1.0 / 3.0);
515                 px3 = relative ? curx + tox : tox;
516                 py3 = relative ? cury + toy : toy;
517 
518                 svgCurveToCubic(narrowPrecisionToFloat(px1), narrowPrecisionToFloat(py1), narrowPrecisionToFloat(px2),
519                                 narrowPrecisionToFloat(py2), narrowPrecisionToFloat(px3), narrowPrecisionToFloat(py3));
520 
521                 contrlx = xc;
522                 contrly = yc;
523                 curx = relative ? curx + tox : tox;
524                 cury = relative ? cury + toy : toy;
525             } else {
526                 svgCurveToQuadraticSmooth(narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), !relative);
527             }
528             break;
529         }
530         case 'a':
531             relative = true;
532         case 'A': {
533             bool largeArc, sweep;
534             double angle, rx, ry;
535             if (!parseNumber(ptr, end, rx)    || !parseNumber(ptr, end, ry) ||
536                     !parseNumber(ptr, end, angle) || !parseNumber(ptr, end, tox)) {
537                 return false;
538             }
539             largeArc = tox == 1;
540             if (!parseNumber(ptr, end, tox)) {
541                 return false;
542             }
543             sweep = tox == 1;
544             if (!parseNumber(ptr, end, tox) || !parseNumber(ptr, end, toy)) {
545                 return false;
546             }
547 
548             // Spec: radii are nonnegative numbers
549             rx = fabs(rx);
550             ry = fabs(ry);
551 
552             if (process) {
553                 calculateArc(relative, curx, cury, angle, tox, toy, rx, ry, largeArc, sweep);
554             } else
555                 svgArcTo(narrowPrecisionToFloat(tox), narrowPrecisionToFloat(toy), narrowPrecisionToFloat(rx), narrowPrecisionToFloat(ry),
556                          narrowPrecisionToFloat(angle), largeArc, sweep, !relative);
557             break;
558         }
559         default:
560             // FIXME: An error should go to the JavaScript console, or the like.
561             return false;
562         }
563         lastCommand = command;
564 
565         if (ptr >= end) {
566             return true;
567         }
568 
569         // Check for remaining coordinates in the current command.
570         if ((*ptr == '+' || *ptr == '-' || (*ptr >= '0' && *ptr <= '9')) &&
571                 (command != 'z' && command != 'Z')) {
572             if (command == 'M') {
573                 command = 'L';
574             } else if (command == 'm') {
575                 command = 'l';
576             }
577         } else {
578             command = (ptr++)->unicode();    // or toLatin1() instead of unicode()???
579         }
580 
581         if (lastCommand != 'C' && lastCommand != 'c' &&
582                 lastCommand != 'S' && lastCommand != 's' &&
583                 lastCommand != 'Q' && lastCommand != 'q' &&
584                 lastCommand != 'T' && lastCommand != 't') {
585             contrlx = curx;
586             contrly = cury;
587         }
588     }
589 
590     return false;
591 }
592 
593 // This works by converting the SVG arc to "simple" beziers.
594 // For each bezier found a svgToCurve call is done.
595 // Adapted from Niko's code in kdelibs/kdecore/svgicons.
596 // Maybe this can serve in some shared lib? (Rob)
calculateArc(bool relative,double & curx,double & cury,double angle,double x,double y,double r1,double r2,bool largeArcFlag,bool sweepFlag)597 void SVGPathParser::calculateArc(bool relative, double &curx, double &cury, double angle, double x, double y, double r1, double r2, bool largeArcFlag, bool sweepFlag)
598 {
599     double sin_th, cos_th;
600     double a00, a01, a10, a11;
601     double x0, y0, x1, y1, xc, yc;
602     double d, sfactor, sfactor_sq;
603     double th0, th1, th_arc;
604     int i, n_segs;
605 
606     sin_th = sin(angle * (piDouble / 180.0));
607     cos_th = cos(angle * (piDouble / 180.0));
608 
609     double dx;
610 
611     if (!relative) {
612         dx = (curx - x) / 2.0;
613     } else {
614         dx = -x / 2.0;
615     }
616 
617     double dy;
618 
619     if (!relative) {
620         dy = (cury - y) / 2.0;
621     } else {
622         dy = -y / 2.0;
623     }
624 
625     double _x1 =  cos_th * dx + sin_th * dy;
626     double _y1 = -sin_th * dx + cos_th * dy;
627     double Pr1 = r1 * r1;
628     double Pr2 = r2 * r2;
629     double Px = _x1 * _x1;
630     double Py = _y1 * _y1;
631 
632     // Spec : check if radii are large enough
633     double check = Px / Pr1 + Py / Pr2;
634     if (check > 1) {
635         r1 = r1 * sqrt(check);
636         r2 = r2 * sqrt(check);
637     }
638 
639     a00 = cos_th / r1;
640     a01 = sin_th / r1;
641     a10 = -sin_th / r2;
642     a11 = cos_th / r2;
643 
644     x0 = a00 * curx + a01 * cury;
645     y0 = a10 * curx + a11 * cury;
646 
647     if (!relative) {
648         x1 = a00 * x + a01 * y;
649     } else {
650         x1 = a00 * (curx + x) + a01 * (cury + y);
651     }
652 
653     if (!relative) {
654         y1 = a10 * x + a11 * y;
655     } else {
656         y1 = a10 * (curx + x) + a11 * (cury + y);
657     }
658 
659     /* (x0, y0) is current point in transformed coordinate space.
660        (x1, y1) is new point in transformed coordinate space.
661 
662        The arc fits a unit-radius circle in this space.
663     */
664 
665     d = (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0);
666 
667     sfactor_sq = 1.0 / d - 0.25;
668 
669     if (sfactor_sq < 0) {
670         sfactor_sq = 0;
671     }
672 
673     sfactor = sqrt(sfactor_sq);
674 
675     if (sweepFlag == largeArcFlag) {
676         sfactor = -sfactor;
677     }
678 
679     xc = 0.5 * (x0 + x1) - sfactor * (y1 - y0);
680     yc = 0.5 * (y0 + y1) + sfactor * (x1 - x0);
681 
682     /* (xc, yc) is center of the circle. */
683     th0 = atan2(y0 - yc, x0 - xc);
684     th1 = atan2(y1 - yc, x1 - xc);
685 
686     th_arc = th1 - th0;
687     if (th_arc < 0 && sweepFlag) {
688         th_arc += 2 * piDouble;
689     } else if (th_arc > 0 && !sweepFlag) {
690         th_arc -= 2 * piDouble;
691     }
692 
693     n_segs = (int)(int) ceil(fabs(th_arc / (piDouble * 0.5 + 0.001)));
694 
695     for (i = 0; i < n_segs; i++) {
696         double sin_th, cos_th;
697         double a00, a01, a10, a11;
698         double x1, y1, x2, y2, x3, y3;
699         double t;
700         double th_half;
701 
702         double _th0 = th0 + i * th_arc / n_segs;
703         double _th1 = th0 + (i + 1) * th_arc / n_segs;
704 
705         sin_th = sin(angle * (piDouble / 180.0));
706         cos_th = cos(angle * (piDouble / 180.0));
707 
708         /* inverse transform compared with rsvg_path_arc */
709         a00 = cos_th * r1;
710         a01 = -sin_th * r2;
711         a10 = sin_th * r1;
712         a11 = cos_th * r2;
713 
714         th_half = 0.5 * (_th1 - _th0);
715         t = (8.0 / 3.0) * sin(th_half * 0.5) * sin(th_half * 0.5) / sin(th_half);
716         x1 = xc + cos(_th0) - t * sin(_th0);
717         y1 = yc + sin(_th0) + t * cos(_th0);
718         x3 = xc + cos(_th1);
719         y3 = yc + sin(_th1);
720         x2 = x3 + t * sin(_th1);
721         y2 = y3 - t * cos(_th1);
722 
723         svgCurveToCubic(narrowPrecisionToFloat(a00 * x1 + a01 * y1), narrowPrecisionToFloat(a10 * x1 + a11 * y1),
724                         narrowPrecisionToFloat(a00 * x2 + a01 * y2), narrowPrecisionToFloat(a10 * x2 + a11 * y2),
725                         narrowPrecisionToFloat(a00 * x3 + a01 * y3), narrowPrecisionToFloat(a10 * x3 + a11 * y3));
726     }
727 
728     if (!relative) {
729         curx = x;
730     } else {
731         curx += x;
732     }
733 
734     if (!relative) {
735         cury = y;
736     } else {
737         cury += y;
738     }
739 }
740 
741 class PathBuilder : public SVGPathParser
742 {
743 public:
build(Path * path,const String & d)744     bool build(Path *path, const String &d)
745     {
746         m_path = path;
747         return parseSVG(d, true);
748     }
749 
750 private:
svgMoveTo(double x1,double y1,bool closed,bool abs=true)751     void svgMoveTo(double x1, double y1, bool closed, bool abs = true) override
752     {
753         current.setX(narrowPrecisionToFloat(abs ? x1 : current.x() + x1));
754         current.setY(narrowPrecisionToFloat(abs ? y1 : current.y() + y1));
755         if (closed) {
756             m_path->closeSubpath();
757         }
758         m_path->moveTo(current);
759     }
svgLineTo(double x1,double y1,bool abs=true)760     void svgLineTo(double x1, double y1, bool abs = true) override
761     {
762         current.setX(narrowPrecisionToFloat(abs ? x1 : current.x() + x1));
763         current.setY(narrowPrecisionToFloat(abs ? y1 : current.y() + y1));
764         m_path->addLineTo(current);
765     }
svgCurveToCubic(double x1,double y1,double x2,double y2,double x,double y,bool abs=true)766     void svgCurveToCubic(double x1, double y1, double x2, double y2, double x, double y, bool abs = true) override
767     {
768         if (!abs) {
769             x1 += current.x();
770             y1 += current.y();
771             x2 += current.x();
772             y2 += current.y();
773         }
774         current.setX(narrowPrecisionToFloat(abs ? x : current.x() + x));
775         current.setY(narrowPrecisionToFloat(abs ? y : current.y() + y));
776         m_path->addBezierCurveTo(FloatPoint::narrowPrecision(x1, y1), FloatPoint::narrowPrecision(x2, y2), current);
777     }
svgClosePath()778     void svgClosePath() override
779     {
780         m_path->closeSubpath();
781     }
782     Path *m_path;
783     FloatPoint current;
784 };
785 
pathFromSVGData(Path & path,const String & d)786 bool pathFromSVGData(Path &path, const String &d)
787 {
788     PathBuilder builder;
789     return builder.build(&path, d);
790 }
791 
792 class SVGPathSegListBuilder : public SVGPathParser
793 {
794 public:
build(SVGPathSegList * segList,const String & d,bool process)795     bool build(SVGPathSegList *segList, const String &d, bool process)
796     {
797         m_pathSegList = segList;
798         return parseSVG(d, process);
799     }
800 
801 private:
svgMoveTo(double x1,double y1,bool,bool abs=true)802     void svgMoveTo(double x1, double y1, bool, bool abs = true) override
803     {
804         ExceptionCode ec = 0;
805 
806         if (abs) {
807             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegMovetoAbs(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1)), ec);
808         } else {
809             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegMovetoRel(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1)), ec);
810         }
811     }
svgLineTo(double x1,double y1,bool abs=true)812     void svgLineTo(double x1, double y1, bool abs = true) override
813     {
814         ExceptionCode ec = 0;
815 
816         if (abs) {
817             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoAbs(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1)), ec);
818         } else {
819             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoRel(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1)), ec);
820         }
821     }
svgLineToHorizontal(double x,bool abs)822     void svgLineToHorizontal(double x, bool abs) override
823     {
824         ExceptionCode ec = 0;
825 
826         if (abs) {
827             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoHorizontalAbs(narrowPrecisionToFloat(x)), ec);
828         } else {
829             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoHorizontalRel(narrowPrecisionToFloat(x)), ec);
830         }
831     }
svgLineToVertical(double y,bool abs)832     void svgLineToVertical(double y, bool abs) override
833     {
834         ExceptionCode ec = 0;
835 
836         if (abs) {
837             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoVerticalAbs(narrowPrecisionToFloat(y)), ec);
838         } else {
839             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegLinetoVerticalRel(narrowPrecisionToFloat(y)), ec);
840         }
841     }
svgCurveToCubic(double x1,double y1,double x2,double y2,double x,double y,bool abs=true)842     void svgCurveToCubic(double x1, double y1, double x2, double y2, double x, double y, bool abs = true) override
843     {
844         ExceptionCode ec = 0;
845 
846         if (abs)
847             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoCubicAbs(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y),
848                                       narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
849                                       narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2)), ec);
850         else
851             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoCubicRel(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y),
852                                       narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
853                                       narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2)), ec);
854     }
svgCurveToCubicSmooth(double x,double y,double x2,double y2,bool abs)855     void svgCurveToCubicSmooth(double x, double y, double x2, double y2, bool abs) override
856     {
857         ExceptionCode ec = 0;
858 
859         if (abs)
860             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoCubicSmoothAbs(narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2),
861                                       narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
862         else
863             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoCubicSmoothRel(narrowPrecisionToFloat(x2), narrowPrecisionToFloat(y2),
864                                       narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
865     }
svgCurveToQuadratic(double x,double y,double x1,double y1,bool abs)866     void svgCurveToQuadratic(double x, double y, double x1, double y1, bool abs) override
867     {
868         ExceptionCode ec = 0;
869 
870         if (abs)
871             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoQuadraticAbs(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
872                                       narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
873         else
874             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoQuadraticRel(narrowPrecisionToFloat(x1), narrowPrecisionToFloat(y1),
875                                       narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
876     }
svgCurveToQuadraticSmooth(double x,double y,bool abs)877     void svgCurveToQuadraticSmooth(double x, double y, bool abs) override
878     {
879         ExceptionCode ec = 0;
880 
881         if (abs) {
882             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoQuadraticSmoothAbs(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
883         } else {
884             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegCurvetoQuadraticSmoothRel(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y)), ec);
885         }
886     }
svgArcTo(double x,double y,double r1,double r2,double angle,bool largeArcFlag,bool sweepFlag,bool abs)887     void svgArcTo(double x, double y, double r1, double r2, double angle, bool largeArcFlag, bool sweepFlag, bool abs) override
888     {
889         ExceptionCode ec = 0;
890 
891         if (abs)
892             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegArcAbs(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y),
893                                       narrowPrecisionToFloat(r1), narrowPrecisionToFloat(r2),
894                                       narrowPrecisionToFloat(angle), largeArcFlag, sweepFlag), ec);
895         else
896             m_pathSegList->appendItem(SVGPathElement::createSVGPathSegArcRel(narrowPrecisionToFloat(x), narrowPrecisionToFloat(y),
897                                       narrowPrecisionToFloat(r1), narrowPrecisionToFloat(r2),
898                                       narrowPrecisionToFloat(angle), largeArcFlag, sweepFlag), ec);
899     }
svgClosePath()900     void svgClosePath() override
901     {
902         ExceptionCode ec = 0;
903         m_pathSegList->appendItem(SVGPathElement::createSVGPathSegClosePath(), ec);
904     }
905     SVGPathSegList *m_pathSegList;
906 };
907 
pathSegListFromSVGData(SVGPathSegList * path,const String & d,bool process)908 bool pathSegListFromSVGData(SVGPathSegList *path, const String &d, bool process)
909 {
910     SVGPathSegListBuilder builder;
911     return builder.build(path, d, process);
912 }
913 
parseDelimitedString(const String & input,const char separator)914 Vector<String> parseDelimitedString(const String &input, const char separator)
915 {
916     Vector<String> values;
917 
918     const UChar *ptr = input.characters();
919     const UChar *end = ptr + input.length();
920     skipOptionalSpaces(ptr, end);
921 
922     while (ptr < end) {
923         // Leading and trailing white space, and white space before and after semicolon separators, will be ignored.
924         const UChar *inputStart = ptr;
925         while (ptr < end && *ptr != separator) { // careful not to ignore whitespace inside inputs
926             ptr++;
927         }
928 
929         if (ptr == inputStart) {
930             break;
931         }
932 
933         // walk backwards from the ; to ignore any whitespace
934         const UChar *inputEnd = ptr - 1;
935         while (inputStart < inputEnd && isWhitespace(*inputEnd)) {
936             inputEnd--;
937         }
938 
939         values.append(String(inputStart, inputEnd - inputStart + 1));
940         skipOptionalSpacesOrDelimiter(ptr, end, separator);
941     }
942 
943     return values;
944 }
945 
946 }
947 
948 #endif // ENABLE(SVG)
949