1/*
2 * Copyright (C) 2002, 2003 The Karbon Developers
3 * Copyright (C) 2006 Alexander Kellett <lypanov@kde.org>
4 * Copyright (C) 2006, 2007 Rob Buis <buis@kde.org>
5 * Copyright (C) 2007, 2009, 2015 Apple Inc. All rights reserved.
6 * Copyright (C) Research In Motion Limited 2010. All rights reserved.
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Library General Public
10 * License as published by the Free Software Foundation; either
11 * version 2 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Library General Public License for more details.
17 *
18 * You should have received a copy of the GNU Library General Public License
19 * along with this library; see the file COPYING.LIB. If not, write to
20 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21 * Boston, MA 02110-1301, USA.
22 */
23
24#include "config.h"
25#include "SVGPathParser.h"
26
27#include "AffineTransform.h"
28#include "SVGPathByteStreamBuilder.h"
29#include "SVGPathSource.h"
30#include "SVGPathStringBuilder.h"
31#include <wtf/MathExtras.h>
32
33static const float gOneOverThree = 1 / 3.f;
34
35namespace WebCore {
36
37bool SVGPathParser::parse(SVGPathSource& source, SVGPathConsumer& consumer, PathParsingMode mode, bool checkForInitialMoveTo)
38{
39 SVGPathParser parser(consumer, source, mode);
40 return parser.parsePathData(checkForInitialMoveTo);
41}
42
43bool SVGPathParser::parseToByteStream(SVGPathSource& source, SVGPathByteStream& byteStream, PathParsingMode mode, bool checkForInitialMoveTo)
44{
45 SVGPathByteStreamBuilder builder(byteStream);
46 return parse(source, builder, mode, checkForInitialMoveTo);
47}
48
49bool SVGPathParser::parseToString(SVGPathSource& source, String& result, PathParsingMode mode, bool checkForInitialMoveTo)
50{
51 SVGPathStringBuilder builder;
52 SVGPathParser parser(builder, source, mode);
53 bool ok = parser.parsePathData(checkForInitialMoveTo);
54 result = builder.result();
55 return ok;
56}
57
58SVGPathParser::SVGPathParser(SVGPathConsumer& consumer, SVGPathSource& source, PathParsingMode parsingMode)
59 : m_source(source)
60 , m_consumer(consumer)
61 , m_pathParsingMode(parsingMode)
62{
63}
64
65void SVGPathParser::parseClosePathSegment()
66{
67 // Reset m_currentPoint for the next path.
68 if (m_pathParsingMode == NormalizedParsing)
69 m_currentPoint = m_subPathPoint;
70 m_closePath = true;
71 m_consumer.closePath();
72}
73
74bool SVGPathParser::parseMoveToSegment()
75{
76 FloatPoint targetPoint;
77 if (!m_source.parseMoveToSegment(targetPoint))
78 return false;
79
80 if (m_pathParsingMode == NormalizedParsing) {
81 if (m_mode == RelativeCoordinates)
82 m_currentPoint += targetPoint;
83 else
84 m_currentPoint = targetPoint;
85 m_subPathPoint = m_currentPoint;
86 m_consumer.moveTo(m_currentPoint, m_closePath, AbsoluteCoordinates);
87 } else
88 m_consumer.moveTo(targetPoint, m_closePath, m_mode);
89 m_closePath = false;
90 return true;
91}
92
93bool SVGPathParser::parseLineToSegment()
94{
95 FloatPoint targetPoint;
96 if (!m_source.parseLineToSegment(targetPoint))
97 return false;
98
99 if (m_pathParsingMode == NormalizedParsing) {
100 if (m_mode == RelativeCoordinates)
101 m_currentPoint += targetPoint;
102 else
103 m_currentPoint = targetPoint;
104 m_consumer.lineTo(m_currentPoint, AbsoluteCoordinates);
105 } else
106 m_consumer.lineTo(targetPoint, m_mode);
107 return true;
108}
109
110bool SVGPathParser::parseLineToHorizontalSegment()
111{
112 float toX;
113 if (!m_source.parseLineToHorizontalSegment(toX))
114 return false;
115
116 if (m_pathParsingMode == NormalizedParsing) {
117 if (m_mode == RelativeCoordinates)
118 m_currentPoint.move(toX, 0);
119 else
120 m_currentPoint.setX(toX);
121 m_consumer.lineTo(m_currentPoint, AbsoluteCoordinates);
122 } else
123 m_consumer.lineToHorizontal(toX, m_mode);
124 return true;
125}
126
127bool SVGPathParser::parseLineToVerticalSegment()
128{
129 float toY;
130 if (!m_source.parseLineToVerticalSegment(toY))
131 return false;
132
133 if (m_pathParsingMode == NormalizedParsing) {
134 if (m_mode == RelativeCoordinates)
135 m_currentPoint.move(0, toY);
136 else
137 m_currentPoint.setY(toY);
138 m_consumer.lineTo(m_currentPoint, AbsoluteCoordinates);
139 } else
140 m_consumer.lineToVertical(toY, m_mode);
141 return true;
142}
143
144bool SVGPathParser::parseCurveToCubicSegment()
145{
146 FloatPoint point1;
147 FloatPoint point2;
148 FloatPoint targetPoint;
149 if (!m_source.parseCurveToCubicSegment(point1, point2, targetPoint))
150 return false;
151
152 if (m_pathParsingMode == NormalizedParsing) {
153 if (m_mode == RelativeCoordinates) {
154 point1 += m_currentPoint;
155 point2 += m_currentPoint;
156 targetPoint += m_currentPoint;
157 }
158 m_consumer.curveToCubic(point1, point2, targetPoint, AbsoluteCoordinates);
159
160 m_controlPoint = point2;
161 m_currentPoint = targetPoint;
162 } else
163 m_consumer.curveToCubic(point1, point2, targetPoint, m_mode);
164 return true;
165}
166
167bool SVGPathParser::parseCurveToCubicSmoothSegment()
168{
169 FloatPoint point2;
170 FloatPoint targetPoint;
171 if (!m_source.parseCurveToCubicSmoothSegment(point2, targetPoint))
172 return false;
173
174 if (m_lastCommand != PathSegCurveToCubicAbs
175 && m_lastCommand != PathSegCurveToCubicRel
176 && m_lastCommand != PathSegCurveToCubicSmoothAbs
177 && m_lastCommand != PathSegCurveToCubicSmoothRel)
178 m_controlPoint = m_currentPoint;
179
180 if (m_pathParsingMode == NormalizedParsing) {
181 FloatPoint point1 = m_currentPoint;
182 point1.scale(2);
183 point1.move(-m_controlPoint.x(), -m_controlPoint.y());
184 if (m_mode == RelativeCoordinates) {
185 point2 += m_currentPoint;
186 targetPoint += m_currentPoint;
187 }
188
189 m_consumer.curveToCubic(point1, point2, targetPoint, AbsoluteCoordinates);
190
191 m_controlPoint = point2;
192 m_currentPoint = targetPoint;
193 } else
194 m_consumer.curveToCubicSmooth(point2, targetPoint, m_mode);
195 return true;
196}
197
198bool SVGPathParser::parseCurveToQuadraticSegment()
199{
200 FloatPoint point1;
201 FloatPoint targetPoint;
202 if (!m_source.parseCurveToQuadraticSegment(point1, targetPoint))
203 return false;
204
205 if (m_pathParsingMode == NormalizedParsing) {
206 m_controlPoint = point1;
207 FloatPoint point1 = m_currentPoint;
208 point1.move(2 * m_controlPoint.x(), 2 * m_controlPoint.y());
209 FloatPoint point2(targetPoint.x() + 2 * m_controlPoint.x(), targetPoint.y() + 2 * m_controlPoint.y());
210 if (m_mode == RelativeCoordinates) {
211 point1.move(2 * m_currentPoint.x(), 2 * m_currentPoint.y());
212 point2.move(3 * m_currentPoint.x(), 3 * m_currentPoint.y());
213 targetPoint += m_currentPoint;
214 }
215 point1.scale(gOneOverThree);
216 point2.scale(gOneOverThree);
217
218 m_consumer.curveToCubic(point1, point2, targetPoint, AbsoluteCoordinates);
219
220 if (m_mode == RelativeCoordinates)
221 m_controlPoint += m_currentPoint;
222 m_currentPoint = targetPoint;
223 } else
224 m_consumer.curveToQuadratic(point1, targetPoint, m_mode);
225 return true;
226}
227
228bool SVGPathParser::parseCurveToQuadraticSmoothSegment()
229{
230 FloatPoint targetPoint;
231 if (!m_source.parseCurveToQuadraticSmoothSegment(targetPoint))
232 return false;
233
234 if (m_lastCommand != PathSegCurveToQuadraticAbs
235 && m_lastCommand != PathSegCurveToQuadraticRel
236 && m_lastCommand != PathSegCurveToQuadraticSmoothAbs
237 && m_lastCommand != PathSegCurveToQuadraticSmoothRel)
238 m_controlPoint = m_currentPoint;
239
240 if (m_pathParsingMode == NormalizedParsing) {
241 FloatPoint cubicPoint = m_currentPoint;
242 cubicPoint.scale(2);
243 cubicPoint.move(-m_controlPoint.x(), -m_controlPoint.y());
244 FloatPoint point1(m_currentPoint.x() + 2 * cubicPoint.x(), m_currentPoint.y() + 2 * cubicPoint.y());
245 FloatPoint point2(targetPoint.x() + 2 * cubicPoint.x(), targetPoint.y() + 2 * cubicPoint.y());
246 if (m_mode == RelativeCoordinates) {
247 point2 += m_currentPoint;
248 targetPoint += m_currentPoint;
249 }
250 point1.scale(gOneOverThree);
251 point2.scale(gOneOverThree);
252
253 m_consumer.curveToCubic(point1, point2, targetPoint, AbsoluteCoordinates);
254
255 m_controlPoint = cubicPoint;
256 m_currentPoint = targetPoint;
257 } else
258 m_consumer.curveToQuadraticSmooth(targetPoint, m_mode);
259 return true;
260}
261
262bool SVGPathParser::parseArcToSegment()
263{
264 float rx;
265 float ry;
266 float angle;
267 bool largeArc;
268 bool sweep;
269 FloatPoint targetPoint;
270 if (!m_source.parseArcToSegment(rx, ry, angle, largeArc, sweep, targetPoint))
271 return false;
272
273 // If rx = 0 or ry = 0 then this arc is treated as a straight line segment (a "lineto") joining the endpoints.
274 // http://www.w3.org/TR/SVG/implnote.html#ArcOutOfRangeParameters
275 // If the current point and target point for the arc are identical, it should be treated as a zero length
276 // path. This ensures continuity in animations.
277 rx = fabsf(rx);
278 ry = fabsf(ry);
279 bool arcIsZeroLength = false;
280 if (m_pathParsingMode == NormalizedParsing) {
281 if (m_mode == RelativeCoordinates)
282 arcIsZeroLength = targetPoint == FloatPoint::zero();
283 else
284 arcIsZeroLength = targetPoint == m_currentPoint;
285 }
286 if (!rx || !ry || arcIsZeroLength) {
287 if (m_pathParsingMode == NormalizedParsing) {
288 if (m_mode == RelativeCoordinates)
289 m_currentPoint += targetPoint;
290 else
291 m_currentPoint = targetPoint;
292 m_consumer.lineTo(m_currentPoint, AbsoluteCoordinates);
293 } else
294 m_consumer.lineTo(targetPoint, m_mode);
295 return true;
296 }
297
298 if (m_pathParsingMode == NormalizedParsing) {
299 FloatPoint point1 = m_currentPoint;
300 if (m_mode == RelativeCoordinates)
301 targetPoint += m_currentPoint;
302 m_currentPoint = targetPoint;
303 return decomposeArcToCubic(angle, rx, ry, point1, targetPoint, largeArc, sweep);
304 }
305 m_consumer.arcTo(rx, ry, angle, largeArc, sweep, targetPoint, m_mode);
306 return true;
307}
308
309bool SVGPathParser::parsePathData(bool checkForInitialMoveTo)
310{
311 // Skip any leading spaces.
312 if (!m_source.moveToNextToken())
313 return true;
314
315 SVGPathSegType command;
316 m_source.parseSVGSegmentType(command);
317
318 // Path must start with moveto.
319 if (checkForInitialMoveTo && command != PathSegMoveToAbs && command != PathSegMoveToRel)
320 return false;
321
322 while (true) {
323 // Skip spaces between command and first coordinate.
324 m_source.moveToNextToken();
325 m_mode = AbsoluteCoordinates;
326 switch (command) {
327 case PathSegMoveToRel:
328 m_mode = RelativeCoordinates;
329 FALLTHROUGH;
330 case PathSegMoveToAbs:
331 if (!parseMoveToSegment())
332 return false;
333 break;
334 case PathSegLineToRel:
335 m_mode = RelativeCoordinates;
336 FALLTHROUGH;
337 case PathSegLineToAbs:
338 if (!parseLineToSegment())
339 return false;
340 break;
341 case PathSegLineToHorizontalRel:
342 m_mode = RelativeCoordinates;
343 FALLTHROUGH;
344 case PathSegLineToHorizontalAbs:
345 if (!parseLineToHorizontalSegment())
346 return false;
347 break;
348 case PathSegLineToVerticalRel:
349 m_mode = RelativeCoordinates;
350 FALLTHROUGH;
351 case PathSegLineToVerticalAbs:
352 if (!parseLineToVerticalSegment())
353 return false;
354 break;
355 case PathSegClosePath:
356 parseClosePathSegment();
357 break;
358 case PathSegCurveToCubicRel:
359 m_mode = RelativeCoordinates;
360 FALLTHROUGH;
361 case PathSegCurveToCubicAbs:
362 if (!parseCurveToCubicSegment())
363 return false;
364 break;
365 case PathSegCurveToCubicSmoothRel:
366 m_mode = RelativeCoordinates;
367 FALLTHROUGH;
368 case PathSegCurveToCubicSmoothAbs:
369 if (!parseCurveToCubicSmoothSegment())
370 return false;
371 break;
372 case PathSegCurveToQuadraticRel:
373 m_mode = RelativeCoordinates;
374 FALLTHROUGH;
375 case PathSegCurveToQuadraticAbs:
376 if (!parseCurveToQuadraticSegment())
377 return false;
378 break;
379 case PathSegCurveToQuadraticSmoothRel:
380 m_mode = RelativeCoordinates;
381 FALLTHROUGH;
382 case PathSegCurveToQuadraticSmoothAbs:
383 if (!parseCurveToQuadraticSmoothSegment())
384 return false;
385 break;
386 case PathSegArcRel:
387 m_mode = RelativeCoordinates;
388 FALLTHROUGH;
389 case PathSegArcAbs:
390 if (!parseArcToSegment())
391 return false;
392 break;
393 default:
394 return false;
395 }
396 if (!m_consumer.continueConsuming())
397 return true;
398
399 m_lastCommand = command;
400
401 if (!m_source.hasMoreData())
402 return true;
403
404 command = m_source.nextCommand(command);
405
406 if (m_lastCommand != PathSegCurveToCubicAbs
407 && m_lastCommand != PathSegCurveToCubicRel
408 && m_lastCommand != PathSegCurveToCubicSmoothAbs
409 && m_lastCommand != PathSegCurveToCubicSmoothRel
410 && m_lastCommand != PathSegCurveToQuadraticAbs
411 && m_lastCommand != PathSegCurveToQuadraticRel
412 && m_lastCommand != PathSegCurveToQuadraticSmoothAbs
413 && m_lastCommand != PathSegCurveToQuadraticSmoothRel)
414 m_controlPoint = m_currentPoint;
415
416 m_consumer.incrementPathSegmentCount();
417 }
418
419 return false;
420}
421
422// This works by converting the SVG arc to "simple" beziers.
423// Partly adapted from Niko's code in kdelibs/kdecore/svgicons.
424// See also SVG implementation notes: http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter
425bool SVGPathParser::decomposeArcToCubic(float angle, float rx, float ry, FloatPoint& point1, FloatPoint& point2, bool largeArcFlag, bool sweepFlag)
426{
427 FloatSize midPointDistance = point1 - point2;
428 midPointDistance.scale(0.5f);
429
430 AffineTransform pointTransform;
431 pointTransform.rotate(-angle);
432
433 FloatPoint transformedMidPoint = pointTransform.mapPoint(FloatPoint(midPointDistance.width(), midPointDistance.height()));
434 float squareRx = rx * rx;
435 float squareRy = ry * ry;
436 float squareX = transformedMidPoint.x() * transformedMidPoint.x();
437 float squareY = transformedMidPoint.y() * transformedMidPoint.y();
438
439 // Check if the radii are big enough to draw the arc, scale radii if not.
440 // http://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
441 float radiiScale = squareX / squareRx + squareY / squareRy;
442 if (radiiScale > 1) {
443 rx *= sqrtf(radiiScale);
444 ry *= sqrtf(radiiScale);
445 }
446
447 pointTransform.makeIdentity();
448 pointTransform.scale(1 / rx, 1 / ry);
449 pointTransform.rotate(-angle);
450
451 point1 = pointTransform.mapPoint(point1);
452 point2 = pointTransform.mapPoint(point2);
453 FloatSize delta = point2 - point1;
454
455 float d = delta.width() * delta.width() + delta.height() * delta.height();
456 float scaleFactorSquared = std::max(1 / d - 0.25f, 0.f);
457
458 float scaleFactor = sqrtf(scaleFactorSquared);
459 if (sweepFlag == largeArcFlag)
460 scaleFactor = -scaleFactor;
461
462 delta.scale(scaleFactor);
463 FloatPoint centerPoint = point1 + point2;
464 centerPoint.scale(0.5f);
465 centerPoint.move(-delta.height(), delta.width());
466
467 float theta1 = FloatPoint(point1 - centerPoint).slopeAngleRadians();
468 float theta2 = FloatPoint(point2 - centerPoint).slopeAngleRadians();
469
470 float thetaArc = theta2 - theta1;
471 if (thetaArc < 0 && sweepFlag)
472 thetaArc += 2 * piFloat;
473 else if (thetaArc > 0 && !sweepFlag)
474 thetaArc -= 2 * piFloat;
475
476 pointTransform.makeIdentity();
477 pointTransform.rotate(angle);
478 pointTransform.scale(rx, ry);
479
480 // Some results of atan2 on some platform implementations are not exact enough. So that we get more
481 // cubic curves than expected here. Adding 0.001f reduces the count of sgements to the correct count.
482 int segments = ceilf(fabsf(thetaArc / (piOverTwoFloat + 0.001f)));
483 for (int i = 0; i < segments; ++i) {
484 float startTheta = theta1 + i * thetaArc / segments;
485 float endTheta = theta1 + (i + 1) * thetaArc / segments;
486
487 float t = (8 / 6.f) * tanf(0.25f * (endTheta - startTheta));
488 if (!std::isfinite(t))
489 return false;
490 float sinStartTheta = sinf(startTheta);
491 float cosStartTheta = cosf(startTheta);
492 float sinEndTheta = sinf(endTheta);
493 float cosEndTheta = cosf(endTheta);
494
495 point1 = FloatPoint(cosStartTheta - t * sinStartTheta, sinStartTheta + t * cosStartTheta);
496 point1.move(centerPoint.x(), centerPoint.y());
497 FloatPoint targetPoint = FloatPoint(cosEndTheta, sinEndTheta);
498 targetPoint.move(centerPoint.x(), centerPoint.y());
499 point2 = targetPoint;
500 point2.move(t * sinEndTheta, -t * cosEndTheta);
501
502 m_consumer.curveToCubic(pointTransform.mapPoint(point1), pointTransform.mapPoint(point2),
503 pointTransform.mapPoint(targetPoint), AbsoluteCoordinates);
504 }
505 return true;
506}
507
508}
509