src/third_party/WebKit/Source/core/html/parser/HTMLSrcsetParser.cpp

   1 /*
   2  * Copyright (C) 2013 Apple Inc. All rights reserved.
   3  * Copyright (C) 2013 Google Inc. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met:
   8  *
   9  *     * Redistributions of source code must retain the above copyright
  10  * notice, this list of conditions and the following disclaimer.
  11  *     * Redistributions in binary form must reproduce the above
  12  * copyright notice, this list of conditions and the following disclaimer
  13  * in the documentation and/or other materials provided with the
  14  * distribution.
  15  *     * Neither the name of Google Inc. nor the names of its
  16  * contributors may be used to endorse or promote products derived from
  17  * this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #include "config.h"
  33 #include "core/html/parser/HTMLSrcsetParser.h"
  34
  35 #include "core/dom/Document.h"
  36 #include "core/fetch/MemoryCache.h"
  37 #include "core/fetch/ResourceFetcher.h"
  38 #include "core/frame/FrameConsole.h"
  39 #include "core/frame/LocalFrame.h"
  40 #include "core/frame/UseCounter.h"
  41 #include "core/html/parser/HTMLParserIdioms.h"
  42 #include "core/inspector/ConsoleMessage.h"
  43 #include "platform/ParsingUtilities.h"
  44 #include "platform/RuntimeEnabledFeatures.h"
  45
  46 namespace blink {
  47
  48 static bool compareByDensity(const ImageCandidate& first, const ImageCandidate& second)
  49 {
  50     return first.density() < second.density();
  51 }
  52
  53 enum DescriptorTokenizerState {
  54     TokenStart,
  55     InParenthesis,
  56     AfterToken,
  57 };
  58
  59 struct DescriptorToken {
  60     unsigned start;
  61     unsigned length;
  62
  63     DescriptorToken(unsigned start, unsigned length)
  64         : start(start)
  65         , length(length)
  66     {
  67     }
  68
  69     unsigned lastIndex()
  70     {
  71         return start + length - 1;
  72     }
  73
  74     template<typename CharType>
  75     int toInt(const CharType* attribute, bool& isValid)
  76     {
  77         unsigned position = 0;
  78         // Make sure the integer is a valid non-negative integer
  79         // https://html.spec.whatwg.org/multipage/infrastructure.html#valid-non-negative-integer
  80         unsigned lengthExcludingDescriptor = length - 1;
  81         while (position < lengthExcludingDescriptor) {
  82             if (!isASCIIDigit(*(attribute + start + position))) {
  83                 isValid = false;
  84                 return 0;
  85             }
  86             ++position;
  87         }
  88         return charactersToIntStrict(attribute + start, lengthExcludingDescriptor, &isValid);
  89     }
  90
  91     template<typename CharType>
  92     float toFloat(const CharType* attribute, bool& isValid)
  93     {
  94         // Make sure the is a valid floating point number
  95         // https://html.spec.whatwg.org/multipage/infrastructure.html#valid-floating-point-number
  96         unsigned lengthExcludingDescriptor = length - 1;
  97         if (lengthExcludingDescriptor > 0 && *(attribute + start) == '+') {
  98             isValid = false;
  99             return 0;
 100         }
 101         return charactersToFloat(attribute + start, lengthExcludingDescriptor, &isValid);
 102     }
 103 };
 104
 105 template<typename CharType>
 106 static void appendDescriptorAndReset(const CharType* attributeStart, const CharType*& descriptorStart, const CharType* position, Vector<DescriptorToken>& descriptors)
 107 {
 108     if (position > descriptorStart)
 109         descriptors.append(DescriptorToken(descriptorStart - attributeStart, position - descriptorStart));
 110     descriptorStart = 0;
 111 }
 112
 113 // The following is called appendCharacter to match the spec's terminology.
 114 template<typename CharType>
 115 static void appendCharacter(const CharType* descriptorStart, const CharType* position)
 116 {
 117     // Since we don't copy the tokens, this just set the point where the descriptor tokens start.
 118     if (!descriptorStart)
 119         descriptorStart = position;
 120 }
 121
 122 template<typename CharType>
 123 static bool isEOF(const CharType* position, const CharType* end)
 124 {
 125     return position >= end;
 126 }
 127
 128 template<typename CharType>
 129 static void tokenizeDescriptors(const CharType* attributeStart,
 130     const CharType*& position,
 131     const CharType* attributeEnd,
 132     Vector<DescriptorToken>& descriptors)
 133 {
 134     DescriptorTokenizerState state = TokenStart;
 135     const CharType* descriptorsStart = position;
 136     const CharType* currentDescriptorStart = descriptorsStart;
 137     while (true) {
 138         switch (state) {
 139         case TokenStart:
 140             if (isEOF(position, attributeEnd)) {
 141                 appendDescriptorAndReset(attributeStart, currentDescriptorStart, attributeEnd, descriptors);
 142                 return;
 143             }
 144             if (isComma(*position)) {
 145                 appendDescriptorAndReset(attributeStart, currentDescriptorStart, position, descriptors);
 146                 ++position;
 147                 return;
 148             }
 149             if (isHTMLSpace(*position)) {
 150                 appendDescriptorAndReset(attributeStart, currentDescriptorStart, position, descriptors);
 151                 currentDescriptorStart = position + 1;
 152                 state = AfterToken;
 153             } else if (*position == '(') {
 154                 appendCharacter(currentDescriptorStart, position);
 155                 state = InParenthesis;
 156             } else {
 157                 appendCharacter(currentDescriptorStart, position);
 158             }
 159             break;
 160         case InParenthesis:
 161             if (isEOF(position, attributeEnd)) {
 162                 appendDescriptorAndReset(attributeStart, currentDescriptorStart, attributeEnd, descriptors);
 163                 return;
 164             }
 165             if (*position == ')') {
 166                 appendCharacter(currentDescriptorStart, position);
 167                 state = TokenStart;
 168             } else {
 169                 appendCharacter(currentDescriptorStart, position);
 170             }
 171             break;
 172         case AfterToken:
 173             if (isEOF(position, attributeEnd))
 174                 return;
 175             if (!isHTMLSpace(*position)) {
 176                 state = TokenStart;
 177                 currentDescriptorStart = position;
 178                 --position;
 179             }
 180             break;
 181         }
 182         ++position;
 183     }
 184 }
 185
 186 static void srcsetError(Document* document, String message)
 187 {
 188     if (document && document->frame()) {
 189         StringBuilder errorMessage;
 190         errorMessage.append("Failed parsing 'srcset' attribute value since ");
 191         errorMessage.append(message);
 192         document->frame()->console().addMessage(ConsoleMessage::create(OtherMessageSource, ErrorMessageLevel, errorMessage.toString()));
 193     }
 194 }
 195
 196 template<typename CharType>
 197 static bool parseDescriptors(const CharType* attribute, Vector<DescriptorToken>& descriptors, DescriptorParsingResult& result, Document* document)
 198 {
 199     for (DescriptorToken& descriptor : descriptors) {
 200         if (descriptor.length == 0)
 201             continue;
 202         CharType c = attribute[descriptor.lastIndex()];
 203         bool isValid = false;
 204         if (RuntimeEnabledFeatures::pictureSizesEnabled() && c == 'w') {
 205             if (result.hasDensity() || result.hasWidth()) {
 206                 srcsetError(document, "it has multiple 'w' descriptors or a mix of 'x' and 'w' descriptors.");
 207                 return false;
 208             }
 209             int resourceWidth = descriptor.toInt(attribute, isValid);
 210             if (!isValid || resourceWidth <= 0) {
 211                 srcsetError(document, "its 'w' descriptor is invalid.");
 212                 return false;
 213             }
 214             result.setResourceWidth(resourceWidth);
 215         } else if (RuntimeEnabledFeatures::pictureSizesEnabled() && c == 'h') {
 216             // This is here only for future compat purposes.
 217             // The value of the 'h' descriptor is not used.
 218             if (result.hasDensity() || result.hasHeight()) {
 219                 srcsetError(document, "it has multiple 'h' descriptors or a mix of 'x' and 'h' descriptors.");
 220                 return false;
 221             }
 222             int resourceHeight = descriptor.toInt(attribute, isValid);
 223             if (!isValid || resourceHeight <= 0) {
 224                 srcsetError(document, "its 'h' descriptor is invalid.");
 225                 return false;
 226             }
 227             result.setResourceHeight(resourceHeight);
 228         } else if (c == 'x') {
 229             if (result.hasDensity() || result.hasHeight() || result.hasWidth()) {
 230                 srcsetError(document, "it has multiple 'x' descriptors or a mix of 'x' and 'w'/'h' descriptors.");
 231                 return false;
 232             }
 233             float density = descriptor.toFloat(attribute, isValid);
 234             if (!isValid || density < 0) {
 235                 srcsetError(document, "its 'x' descriptor is invalid.");
 236                 return false;
 237             }
 238             result.setDensity(density);
 239         } else {
 240             srcsetError(document, "it has an unknown descriptor.");
 241             return false;
 242         }
 243     }
 244     bool res = !result.hasHeight() || result.hasWidth();
 245     if (!res)
 246         srcsetError(document, "it has an 'h' descriptor and no 'w' descriptor.");
 247     return res;
 248 }
 249
 250 static bool parseDescriptors(const String& attribute, Vector<DescriptorToken>& descriptors, DescriptorParsingResult& result, Document* document)
 251 {
 252     // FIXME: See if StringView can't be extended to replace DescriptorToken here.
 253     if (attribute.is8Bit()) {
 254         return parseDescriptors(attribute.characters8(), descriptors, result, document);
 255     }
 256     return parseDescriptors(attribute.characters16(), descriptors, result, document);
 257 }
 258
 259 // http://picture.responsiveimages.org/#parse-srcset-attr
 260 template<typename CharType>
 261 static void parseImageCandidatesFromSrcsetAttribute(const String& attribute, const CharType* attributeStart, unsigned length, Vector<ImageCandidate>& imageCandidates, Document* document)
 262 {
 263     const CharType* position = attributeStart;
 264     const CharType* attributeEnd = position + length;
 265
 266     while (position < attributeEnd) {
 267         // 4. Splitting loop: Collect a sequence of characters that are space characters or U+002C COMMA characters.
 268         skipWhile<CharType, isHTMLSpaceOrComma<CharType>>(position, attributeEnd);
 269         if (position == attributeEnd) {
 270             // Contrary to spec language - descriptor parsing happens on each candidate, so when we reach the attributeEnd, we can exit.
 271             break;
 272         }
 273         const CharType* imageURLStart = position;
 274
 275         // 6. Collect a sequence of characters that are not space characters, and let that be url.
 276         skipUntil<CharType, isHTMLSpace<CharType>>(position, attributeEnd);
 277         const CharType* imageURLEnd = position;
 278
 279         DescriptorParsingResult result;
 280
 281         // 8. If url ends with a U+002C COMMA character (,)
 282         if (isComma(*(position - 1))) {
 283             // Remove all trailing U+002C COMMA characters from url.
 284             imageURLEnd = position - 1;
 285             reverseSkipWhile<CharType, isComma>(imageURLEnd, imageURLStart);
 286             ++imageURLEnd;
 287             // If url is empty, then jump to the step labeled splitting loop.
 288             if (imageURLStart == imageURLEnd)
 289                 continue;
 290         } else {
 291             skipWhile<CharType, isHTMLSpace<CharType> >(position, attributeEnd);
 292             Vector<DescriptorToken> descriptorTokens;
 293             tokenizeDescriptors(attributeStart, position, attributeEnd, descriptorTokens);
 294             // Contrary to spec language - descriptor parsing happens on each candidate.
 295             // This is a black-box equivalent, to avoid storing descriptor lists for each candidate.
 296             if (!parseDescriptors(attribute, descriptorTokens, result, document)) {
 297                 if (document) {
 298                     UseCounter::count(document, UseCounter::SrcsetDroppedCandidate);
 299                     if (document->frame())
 300                         document->frame()->console().addMessage(ConsoleMessage::create(OtherMessageSource, ErrorMessageLevel, String("Dropped srcset candidate ") + String(imageURLStart, imageURLEnd - imageURLStart)));
 301                 }
 302                 continue;
 303             }
 304         }
 305
 306         ASSERT(imageURLEnd > attributeStart);
 307         unsigned imageURLStartingPosition = imageURLStart - attributeStart;
 308         ASSERT(imageURLEnd > imageURLStart);
 309         unsigned imageURLLength = imageURLEnd - imageURLStart;
 310         imageCandidates.append(ImageCandidate(attribute, imageURLStartingPosition, imageURLLength, result, ImageCandidate::SrcsetOrigin));
 311         // 11. Return to the step labeled splitting loop.
 312     }
 313 }
 314
 315 static void parseImageCandidatesFromSrcsetAttribute(const String& attribute, Vector<ImageCandidate>& imageCandidates, Document* document)
 316 {
 317     if (attribute.isNull())
 318         return;
 319
 320     if (attribute.is8Bit())
 321         parseImageCandidatesFromSrcsetAttribute<LChar>(attribute, attribute.characters8(), attribute.length(), imageCandidates, document);
 322     else
 323         parseImageCandidatesFromSrcsetAttribute<UChar>(attribute, attribute.characters16(), attribute.length(), imageCandidates, document);
 324 }
 325
 326 static int selectionLogic(Vector<ImageCandidate>& imageCandidates, float deviceScaleFactor, bool ignoreSrc)
 327 {
 328     unsigned i = 0;
 329
 330     for (; i < imageCandidates.size() - 1; ++i) {
 331         unsigned next = i + 1;
 332         float nextDensity;
 333         float currentDensity;
 334         float geometricMean;
 335         if (ignoreSrc) {
 336             if (imageCandidates[i].srcOrigin())
 337                 continue;
 338             if (imageCandidates[next].srcOrigin()) {
 339                 ++next;
 340                 if (next >= imageCandidates.size())
 341                     break;
 342                 ASSERT(!imageCandidates[next].srcOrigin());
 343             }
 344         }
 345
 346         nextDensity = imageCandidates[next].density();
 347         if (nextDensity < deviceScaleFactor)
 348             continue;
 349
 350         currentDensity = imageCandidates[i].density();
 351         geometricMean = sqrt(currentDensity * nextDensity);
 352         if (deviceScaleFactor >= geometricMean)
 353             return next;
 354         break;
 355     }
 356     return i;
 357 }
 358
 359 static unsigned avoidDownloadIfHigherDensityResourceIsInCache(Vector<ImageCandidate>& imageCandidates, unsigned winner, Document* document)
 360 {
 361     if (!document)
 362         return winner;
 363     for (unsigned i = imageCandidates.size() - 1; i > winner; --i) {
 364         KURL url = document->completeURL(stripLeadingAndTrailingHTMLSpaces(imageCandidates[i].url()));
 365         if (memoryCache()->resourceForURL(url, document->fetcher()->getCacheIdentifier()))
 366             return i;
 367     }
 368     return winner;
 369 }
 370
 371 static ImageCandidate pickBestImageCandidate(float deviceScaleFactor, float sourceSize, Vector<ImageCandidate>& imageCandidates, Document* document = nullptr)
 372 {
 373     const float defaultDensityValue = 1.0;
 374     bool ignoreSrc = false;
 375     if (imageCandidates.isEmpty())
 376         return ImageCandidate();
 377
 378     // http://picture.responsiveimages.org/#normalize-source-densities
 379     for (ImageCandidate& image : imageCandidates) {
 380         if (image.resourceWidth() > 0) {
 381             image.setDensity((float)image.resourceWidth() / sourceSize);
 382             ignoreSrc = true;
 383         } else if (image.density() < 0) {
 384             image.setDensity(defaultDensityValue);
 385         }
 386     }
 387
 388     std::stable_sort(imageCandidates.begin(), imageCandidates.end(), compareByDensity);
 389
 390     unsigned winner = selectionLogic(imageCandidates, deviceScaleFactor, ignoreSrc);
 391     ASSERT(winner < imageCandidates.size());
 392     winner = avoidDownloadIfHigherDensityResourceIsInCache(imageCandidates, winner, document);
 393
 394     float winningDensity = imageCandidates[winner].density();
 395     // 16. If an entry b in candidates has the same associated ... pixel density as an earlier entry a in candidates,
 396     // then remove entry b
 397     while ((winner > 0) && (imageCandidates[winner - 1].density() == winningDensity))
 398         --winner;
 399
 400     return imageCandidates[winner];
 401 }
 402
 403 ImageCandidate bestFitSourceForSrcsetAttribute(float deviceScaleFactor, float sourceSize, const String& srcsetAttribute, Document* document)
 404 {
 405     Vector<ImageCandidate> imageCandidates;
 406
 407     parseImageCandidatesFromSrcsetAttribute(srcsetAttribute, imageCandidates, document);
 408
 409     return pickBestImageCandidate(deviceScaleFactor, sourceSize, imageCandidates, document);
 410 }
 411
 412 ImageCandidate bestFitSourceForImageAttributes(float deviceScaleFactor, float sourceSize, const String& srcAttribute, const String& srcsetAttribute, Document* document)
 413 {
 414     if (srcsetAttribute.isNull()) {
 415         if (srcAttribute.isNull())
 416             return ImageCandidate();
 417         return ImageCandidate(srcAttribute, 0, srcAttribute.length(), DescriptorParsingResult(), ImageCandidate::SrcOrigin);
 418     }
 419
 420     Vector<ImageCandidate> imageCandidates;
 421
 422     parseImageCandidatesFromSrcsetAttribute(srcsetAttribute, imageCandidates, document);
 423
 424     if (!srcAttribute.isEmpty())
 425         imageCandidates.append(ImageCandidate(srcAttribute, 0, srcAttribute.length(), DescriptorParsingResult(), ImageCandidate::SrcOrigin));
 426
 427     return pickBestImageCandidate(deviceScaleFactor, sourceSize, imageCandidates, document);
 428 }
 429
 430 String bestFitSourceForImageAttributes(float deviceScaleFactor, float sourceSize, const String& srcAttribute, ImageCandidate& srcsetImageCandidate)
 431 {
 432     if (srcsetImageCandidate.isEmpty())
 433         return srcAttribute;
 434
 435     Vector<ImageCandidate> imageCandidates;
 436     imageCandidates.append(srcsetImageCandidate);
 437
 438     if (!srcAttribute.isEmpty())
 439         imageCandidates.append(ImageCandidate(srcAttribute, 0, srcAttribute.length(), DescriptorParsingResult(), ImageCandidate::SrcOrigin));
 440
 441     return pickBestImageCandidate(deviceScaleFactor, sourceSize, imageCandidates).toString();
 442 }
 443
 444 }