src/third_party/WebKit/Source/core/svg/SVGParserUtilities.cpp

   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, 2013 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 "config.h"
  24 #include "core/svg/SVGParserUtilities.h"
  25
  26 #include "core/svg/SVGPointList.h"
  27 #include "platform/geometry/FloatRect.h"
  28 #include "platform/transforms/AffineTransform.h"
  29 #include "wtf/ASCIICType.h"
  30 #include "wtf/text/StringHash.h"
  31 #include <limits>
  32
  33 namespace blink {
  34
  35 template <typename FloatType>
  36 static inline bool isValidRange(const FloatType& x)
  37 {
  38     static const FloatType max = std::numeric_limits<FloatType>::max();
  39     return x >= -max && x <= max;
  40 }
  41
  42 // We use this generic parseNumber function to allow the Path parsing code to work
  43 // at a higher precision internally, without any unnecessary runtime cost or code
  44 // complexity.
  45 template <typename CharType, typename FloatType>
  46 static bool genericParseNumber(const CharType*& ptr, const CharType* end, FloatType& number, WhitespaceMode mode)
  47 {
  48     FloatType integer, decimal, frac, exponent;
  49     int sign, expsign;
  50     const CharType* start = ptr;
  51
  52     exponent = 0;
  53     integer = 0;
  54     frac = 1;
  55     decimal = 0;
  56     sign = 1;
  57     expsign = 1;
  58
  59     if (mode & AllowLeadingWhitespace)
  60         skipOptionalSVGSpaces(ptr, end);
  61
  62     // read the sign
  63     if (ptr < end && *ptr == '+')
  64         ptr++;
  65     else if (ptr < end && *ptr == '-') {
  66         ptr++;
  67         sign = -1;
  68     }
  69
  70     if (ptr == end || ((*ptr < '0' || *ptr > '9') && *ptr != '.'))
  71         // The first character of a number must be one of [0-9+-.]
  72         return false;
  73
  74     // read the integer part, build right-to-left
  75     const CharType* ptrStartIntPart = ptr;
  76     while (ptr < end && *ptr >= '0' && *ptr <= '9')
  77         ++ptr; // Advance to first non-digit.
  78
  79     if (ptr != ptrStartIntPart) {
  80         const CharType* ptrScanIntPart = ptr - 1;
  81         FloatType multiplier = 1;
  82         while (ptrScanIntPart >= ptrStartIntPart) {
  83             integer += multiplier * static_cast<FloatType>(*(ptrScanIntPart--) - '0');
  84             multiplier *= 10;
  85         }
  86         // Bail out early if this overflows.
  87         if (!isValidRange(integer))
  88             return false;
  89     }
  90
  91     if (ptr < end && *ptr == '.') { // read the decimals
  92         ptr++;
  93
  94         // There must be a least one digit following the .
  95         if (ptr >= end || *ptr < '0' || *ptr > '9')
  96             return false;
  97
  98         while (ptr < end && *ptr >= '0' && *ptr <= '9')
  99             decimal += (*(ptr++) - '0') * (frac *= static_cast<FloatType>(0.1));
 100     }
 101
 102     // read the exponent part
 103     if (ptr != start && ptr + 1 < end && (*ptr == 'e' || *ptr == 'E')
 104         && (ptr[1] != 'x' && ptr[1] != 'm')) {
 105         ptr++;
 106
 107         // read the sign of the exponent
 108         if (*ptr == '+')
 109             ptr++;
 110         else if (*ptr == '-') {
 111             ptr++;
 112             expsign = -1;
 113         }
 114
 115         // There must be an exponent
 116         if (ptr >= end || *ptr < '0' || *ptr > '9')
 117             return false;
 118
 119         while (ptr < end && *ptr >= '0' && *ptr <= '9') {
 120             exponent *= static_cast<FloatType>(10);
 121             exponent += *ptr - '0';
 122             ptr++;
 123         }
 124         // Make sure exponent is valid.
 125         if (!isValidRange(exponent) || exponent > std::numeric_limits<FloatType>::max_exponent)
 126             return false;
 127     }
 128
 129     number = integer + decimal;
 130     number *= sign;
 131
 132     if (exponent)
 133         number *= static_cast<FloatType>(pow(10.0, expsign * static_cast<int>(exponent)));
 134
 135     // Don't return Infinity() or NaN().
 136     if (!isValidRange(number))
 137         return false;
 138
 139     if (start == ptr)
 140         return false;
 141
 142     if (mode & AllowTrailingWhitespace)
 143         skipOptionalSVGSpacesOrDelimiter(ptr, end);
 144
 145     return true;
 146 }
 147
 148 bool parseNumber(const LChar*& ptr, const LChar* end, float& number, WhitespaceMode mode)
 149 {
 150     return genericParseNumber(ptr, end, number, mode);
 151 }
 152
 153 bool parseNumber(const UChar*& ptr, const UChar* end, float& number, WhitespaceMode mode)
 154 {
 155     return genericParseNumber(ptr, end, number, mode);
 156 }
 157
 158 // only used to parse largeArcFlag and sweepFlag which must be a "0" or "1"
 159 // and might not have any whitespace/comma after it
 160 template <typename CharType>
 161 bool genericParseArcFlag(const CharType*& ptr, const CharType* end, bool& flag)
 162 {
 163     if (ptr >= end)
 164         return false;
 165     const CharType flagChar = *ptr++;
 166     if (flagChar == '0')
 167         flag = false;
 168     else if (flagChar == '1')
 169         flag = true;
 170     else
 171         return false;
 172
 173     skipOptionalSVGSpacesOrDelimiter(ptr, end);
 174
 175     return true;
 176 }
 177
 178 bool parseArcFlag(const LChar*& ptr, const LChar* end, bool& flag)
 179 {
 180     return genericParseArcFlag(ptr, end, flag);
 181 }
 182
 183 bool parseArcFlag(const UChar*& ptr, const UChar* end, bool& flag)
 184 {
 185     return genericParseArcFlag(ptr, end, flag);
 186 }
 187
 188 template<typename CharType>
 189 static bool genericParseNumberOptionalNumber(const CharType*& ptr, const CharType* end, float& x, float& y)
 190 {
 191     if (!parseNumber(ptr, end, x))
 192         return false;
 193
 194     if (ptr == end)
 195         y = x;
 196     else if (!parseNumber(ptr, end, y, AllowLeadingAndTrailingWhitespace))
 197         return false;
 198
 199     return ptr == end;
 200 }
 201
 202 bool parseNumberOptionalNumber(const String& string, float& x, float& y)
 203 {
 204     if (string.isEmpty())
 205         return false;
 206
 207     if (string.is8Bit()) {
 208         const LChar* ptr = string.characters8();
 209         const LChar* end = ptr + string.length();
 210         return genericParseNumberOptionalNumber(ptr, end, x, y);
 211     }
 212     const UChar* ptr = string.characters16();
 213     const UChar* end = ptr + string.length();
 214     return genericParseNumberOptionalNumber(ptr, end, x, y);
 215 }
 216
 217 template<typename CharType>
 218 bool genericParseNumberOrPercentage(const CharType*& ptr, const CharType* end, float& number)
 219 {
 220     if (genericParseNumber(ptr, end, number, AllowLeadingWhitespace)) {
 221         if (ptr == end)
 222             return true;
 223
 224         bool isPercentage = (*ptr == '%');
 225         if (isPercentage)
 226             ptr++;
 227
 228         skipOptionalSVGSpaces(ptr, end);
 229
 230         if (isPercentage)
 231             number /= 100.f;
 232
 233         return ptr == end;
 234     }
 235
 236     return false;
 237 }
 238
 239 bool parseNumberOrPercentage(const String& string, float& number)
 240 {
 241     if (string.isEmpty())
 242         return false;
 243
 244     if (string.is8Bit()) {
 245         const LChar* ptr = string.characters8();
 246         const LChar* end = ptr + string.length();
 247         return genericParseNumberOrPercentage(ptr, end, number);
 248     }
 249     const UChar* ptr = string.characters16();
 250     const UChar* end = ptr + string.length();
 251     return genericParseNumberOrPercentage(ptr, end, number);
 252 }
 253
 254 #if ENABLE(SVG_FONTS)
 255 template<typename CharType>
 256 static bool parseGlyphName(const CharType*& ptr, const CharType* end, HashSet<String>& values)
 257 {
 258     skipOptionalSVGSpaces(ptr, end);
 259
 260     while (ptr < end) {
 261         // Leading and trailing white space, and white space before and after separators, will be ignored.
 262         const CharType* inputStart = ptr;
 263         while (ptr < end && *ptr != ',')
 264             ++ptr;
 265
 266         if (ptr == inputStart)
 267             break;
 268
 269         // walk backwards from the ; to ignore any whitespace
 270         const CharType* inputEnd = ptr - 1;
 271         while (inputStart < inputEnd && isHTMLSpace<CharType>(*inputEnd))
 272             --inputEnd;
 273
 274         values.add(String(inputStart, inputEnd - inputStart + 1));
 275         skipOptionalSVGSpacesOrDelimiter(ptr, end, ',');
 276     }
 277
 278     return true;
 279 }
 280
 281 bool parseGlyphName(const String& input, HashSet<String>& values)
 282 {
 283     // FIXME: Parsing error detection is missing.
 284     values.clear();
 285     if (input.isEmpty())
 286         return true;
 287     if (input.is8Bit()) {
 288         const LChar* ptr = input.characters8();
 289         const LChar* end = ptr + input.length();
 290         return parseGlyphName(ptr, end, values);
 291     }
 292     const UChar* ptr = input.characters16();
 293     const UChar* end = ptr + input.length();
 294     return parseGlyphName(ptr, end, values);
 295 }
 296
 297 template<typename CharType>
 298 static bool parseUnicodeRange(const CharType* characters, unsigned length, UnicodeRange& range)
 299 {
 300     if (length < 2 || characters[0] != 'U' || characters[1] != '+')
 301         return false;
 302
 303     // Parse the starting hex number (or its prefix).
 304     unsigned startRange = 0;
 305     unsigned startLength = 0;
 306
 307     const CharType* ptr = characters + 2;
 308     const CharType* end = characters + length;
 309     while (ptr < end) {
 310         if (!isASCIIHexDigit(*ptr))
 311             break;
 312         ++startLength;
 313         if (startLength > 6)
 314             return false;
 315         startRange = (startRange << 4) | toASCIIHexValue(*ptr);
 316         ++ptr;
 317     }
 318
 319     // Handle the case of ranges separated by "-" sign.
 320     if (2 + startLength < length && *ptr == '-') {
 321         if (!startLength)
 322             return false;
 323
 324         // Parse the ending hex number (or its prefix).
 325         unsigned endRange = 0;
 326         unsigned endLength = 0;
 327         ++ptr;
 328         while (ptr < end) {
 329             if (!isASCIIHexDigit(*ptr))
 330                 break;
 331             ++endLength;
 332             if (endLength > 6)
 333                 return false;
 334             endRange = (endRange << 4) | toASCIIHexValue(*ptr);
 335             ++ptr;
 336         }
 337
 338         if (!endLength)
 339             return false;
 340
 341         range.first = startRange;
 342         range.second = endRange;
 343         return true;
 344     }
 345
 346     // Handle the case of a number with some optional trailing question marks.
 347     unsigned endRange = startRange;
 348     while (ptr < end) {
 349         if (*ptr != '?')
 350             break;
 351         ++startLength;
 352         if (startLength > 6)
 353             return false;
 354         startRange <<= 4;
 355         endRange = (endRange << 4) | 0xF;
 356         ++ptr;
 357     }
 358
 359     if (!startLength)
 360         return false;
 361
 362     range.first = startRange;
 363     range.second = endRange;
 364     return true;
 365 }
 366
 367 template<typename CharType>
 368 static bool genericParseKerningUnicodeString(const CharType*& ptr, const CharType* end, UnicodeRanges& rangeList, HashSet<String>& stringList)
 369 {
 370     while (ptr < end) {
 371         const CharType* inputStart = ptr;
 372         while (ptr < end && *ptr != ',')
 373             ++ptr;
 374
 375         if (ptr == inputStart)
 376             break;
 377
 378         // Try to parse unicode range first
 379         UnicodeRange range;
 380         if (parseUnicodeRange(inputStart, ptr - inputStart, range))
 381             rangeList.append(range);
 382         else
 383             stringList.add(String(inputStart, ptr - inputStart));
 384         ++ptr;
 385     }
 386
 387     return true;
 388 }
 389
 390 bool parseKerningUnicodeString(const String& input, UnicodeRanges& rangeList, HashSet<String>& stringList)
 391 {
 392     // FIXME: Parsing error detection is missing.
 393     if (input.isEmpty())
 394         return true;
 395     if (input.is8Bit()) {
 396         const LChar* ptr = input.characters8();
 397         const LChar* end = ptr + input.length();
 398         return genericParseKerningUnicodeString(ptr, end, rangeList, stringList);
 399     }
 400     const UChar* ptr = input.characters16();
 401     const UChar* end = ptr + input.length();
 402     return genericParseKerningUnicodeString(ptr, end, rangeList, stringList);
 403 }
 404
 405 template<typename CharType>
 406 static Vector<String> genericParseDelimitedString(const CharType*& ptr, const CharType* end, const char seperator)
 407 {
 408     Vector<String> values;
 409
 410     skipOptionalSVGSpaces(ptr, end);
 411
 412     while (ptr < end) {
 413         // Leading and trailing white space, and white space before and after semicolon separators, will be ignored.
 414         const CharType* inputStart = ptr;
 415         while (ptr < end && *ptr != seperator) // careful not to ignore whitespace inside inputs
 416             ptr++;
 417
 418         if (ptr == inputStart)
 419             break;
 420
 421         // walk backwards from the ; to ignore any whitespace
 422         const CharType* inputEnd = ptr - 1;
 423         while (inputStart < inputEnd && isHTMLSpace<CharType>(*inputEnd))
 424             inputEnd--;
 425
 426         values.append(String(inputStart, inputEnd - inputStart + 1));
 427         skipOptionalSVGSpacesOrDelimiter(ptr, end, seperator);
 428     }
 429
 430     return values;
 431 }
 432
 433 Vector<String> parseDelimitedString(const String& input, const char seperator)
 434 {
 435     if (input.isEmpty())
 436         return Vector<String>();
 437     if (input.is8Bit()) {
 438         const LChar* ptr = input.characters8();
 439         const LChar* end = ptr + input.length();
 440         return genericParseDelimitedString(ptr, end, seperator);
 441     }
 442     const UChar* ptr = input.characters16();
 443     const UChar* end = ptr + input.length();
 444     return genericParseDelimitedString(ptr, end, seperator);
 445 }
 446 #endif
 447
 448 template <typename CharType>
 449 bool parseFloatPoint(const CharType*& current, const CharType* end, FloatPoint& point)
 450 {
 451     float x;
 452     float y;
 453     if (!parseNumber(current, end, x)
 454         || !parseNumber(current, end, y))
 455         return false;
 456     point = FloatPoint(x, y);
 457     return true;
 458 }
 459
 460 template bool parseFloatPoint(const LChar*& current, const LChar* end, FloatPoint& point1);
 461 template bool parseFloatPoint(const UChar*& current, const UChar* end, FloatPoint& point1);
 462
 463 template <typename CharType>
 464 inline bool parseFloatPoint2(const CharType*& current, const CharType* end, FloatPoint& point1, FloatPoint& point2)
 465 {
 466     float x1;
 467     float y1;
 468     float x2;
 469     float y2;
 470     if (!parseNumber(current, end, x1)
 471         || !parseNumber(current, end, y1)
 472         || !parseNumber(current, end, x2)
 473         || !parseNumber(current, end, y2))
 474         return false;
 475     point1 = FloatPoint(x1, y1);
 476     point2 = FloatPoint(x2, y2);
 477     return true;
 478 }
 479
 480 template bool parseFloatPoint2(const LChar*& current, const LChar* end, FloatPoint& point1, FloatPoint& point2);
 481 template bool parseFloatPoint2(const UChar*& current, const UChar* end, FloatPoint& point1, FloatPoint& point2);
 482
 483 template <typename CharType>
 484 bool parseFloatPoint3(const CharType*& current, const CharType* end, FloatPoint& point1, FloatPoint& point2, FloatPoint& point3)
 485 {
 486     float x1;
 487     float y1;
 488     float x2;
 489     float y2;
 490     float x3;
 491     float y3;
 492     if (!parseNumber(current, end, x1)
 493         || !parseNumber(current, end, y1)
 494         || !parseNumber(current, end, x2)
 495         || !parseNumber(current, end, y2)
 496         || !parseNumber(current, end, x3)
 497         || !parseNumber(current, end, y3))
 498         return false;
 499     point1 = FloatPoint(x1, y1);
 500     point2 = FloatPoint(x2, y2);
 501     point3 = FloatPoint(x3, y3);
 502     return true;
 503 }
 504
 505 template bool parseFloatPoint3(const LChar*& current, const LChar* end, FloatPoint& point1, FloatPoint& point2, FloatPoint& point3);
 506 template bool parseFloatPoint3(const UChar*& current, const UChar* end, FloatPoint& point1, FloatPoint& point2, FloatPoint& point3);
 507
 508 static const LChar skewXDesc[] =  {'s', 'k', 'e', 'w', 'X'};
 509 static const LChar skewYDesc[] =  {'s', 'k', 'e', 'w', 'Y'};
 510 static const LChar scaleDesc[] =  {'s', 'c', 'a', 'l', 'e'};
 511 static const LChar translateDesc[] =  {'t', 'r', 'a', 'n', 's', 'l', 'a', 't', 'e'};
 512 static const LChar rotateDesc[] =  {'r', 'o', 't', 'a', 't', 'e'};
 513 static const LChar matrixDesc[] =  {'m', 'a', 't', 'r', 'i', 'x'};
 514
 515 template<typename CharType>
 516 bool parseAndSkipTransformType(const CharType*& ptr, const CharType* end, SVGTransformType& type)
 517 {
 518     if (ptr >= end)
 519         return false;
 520
 521     if (*ptr == 's') {
 522         if (skipString(ptr, end, skewXDesc, WTF_ARRAY_LENGTH(skewXDesc)))
 523             type = SVG_TRANSFORM_SKEWX;
 524         else if (skipString(ptr, end, skewYDesc, WTF_ARRAY_LENGTH(skewYDesc)))
 525             type = SVG_TRANSFORM_SKEWY;
 526         else if (skipString(ptr, end, scaleDesc, WTF_ARRAY_LENGTH(scaleDesc)))
 527             type = SVG_TRANSFORM_SCALE;
 528         else
 529             return false;
 530     } else if (skipString(ptr, end, translateDesc, WTF_ARRAY_LENGTH(translateDesc)))
 531         type = SVG_TRANSFORM_TRANSLATE;
 532     else if (skipString(ptr, end, rotateDesc, WTF_ARRAY_LENGTH(rotateDesc)))
 533         type = SVG_TRANSFORM_ROTATE;
 534     else if (skipString(ptr, end, matrixDesc, WTF_ARRAY_LENGTH(matrixDesc)))
 535         type = SVG_TRANSFORM_MATRIX;
 536     else
 537         return false;
 538
 539     return true;
 540 }
 541
 542 template bool parseAndSkipTransformType(const UChar*& current, const UChar* end, SVGTransformType&);
 543 template bool parseAndSkipTransformType(const LChar*& current, const LChar* end, SVGTransformType&);
 544
 545 SVGTransformType parseTransformType(const String& string)
 546 {
 547     if (string.isEmpty())
 548         return SVG_TRANSFORM_UNKNOWN;
 549     SVGTransformType type = SVG_TRANSFORM_UNKNOWN;
 550     if (string.is8Bit()) {
 551         const LChar* ptr = string.characters8();
 552         const LChar* end = ptr + string.length();
 553         parseAndSkipTransformType(ptr, end, type);
 554     } else {
 555         const UChar* ptr = string.characters16();
 556         const UChar* end = ptr + string.length();
 557         parseAndSkipTransformType(ptr, end, type);
 558     }
 559     return type;
 560 }
 561
 562 }