Always select best favicon bitmap

components/favicon/core/favicon_handler.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "components/favicon/core/favicon_handler.h"
 
 #include <algorithm>
 #include <cmath>
+#include <utility>
 #include <vector>
 
 #include "base/bind.h"
 #include "base/bind_helpers.h"
 #include "base/memory/ref_counted_memory.h"
 #include "build/build_config.h"
 #include "components/favicon/core/favicon_service.h"
 #include "components/favicon_base/favicon_util.h"
 #include "components/favicon_base/select_favicon_frames.h"
 #include "skia/ext/image_operations.h"
 #include "ui/gfx/codec/png_codec.h"
 #include "ui/gfx/image/image_skia.h"
 #include "ui/gfx/image/image_util.h"
 
 namespace favicon {
 namespace {
 
+const int kNonTouchLargestIconSize = 192;
+
 // Size (along each axis) of a touch icon. This currently corresponds to
 // the apple touch icon for iPad.
 const int kTouchIconSize = 144;
 
-bool DoUrlAndIconMatch(const FaviconURL& favicon_url,
-                       const GURL& url,
-                       favicon_base::IconType icon_type) {
-  return favicon_url.icon_url == url && favicon_url.icon_type == icon_type;
-}
-
 // Returns true if all of the icon URLs and icon types in |bitmap_results| are
-// identical and if they match the icon URL and icon type in |favicon_url|.
-// Returns false if |bitmap_results| is empty.
+// identical and if they match |icon_url| and |icon_type|. Returns false if
+// |bitmap_results| is empty.
 bool DoUrlsAndIconsMatch(
-    const FaviconURL& favicon_url,
+    const GURL& icon_url,
+    favicon_base::IconType icon_type,
     const std::vector<favicon_base::FaviconRawBitmapResult>& bitmap_results) {
   if (bitmap_results.empty())
     return false;
 
-  const favicon_base::IconType icon_type = favicon_url.icon_type;
-
   for (const auto& bitmap_result : bitmap_results) {
-    if (favicon_url.icon_url != bitmap_result.icon_url ||
+    if (icon_url != bitmap_result.icon_url ||
         icon_type != bitmap_result.icon_type) {
       return false;
     }
   }
   return true;
 }
 
 // Return true if |bitmap_result| is expired.
 bool IsExpired(const favicon_base::FaviconRawBitmapResult& bitmap_result) {
   return bitmap_result.expired;
@@ skipping 47 matching lines @@
   return false;
 }
 
 // Returns true if at least one of |bitmap_results| is valid.
 bool HasValidResult(
     const std::vector<favicon_base::FaviconRawBitmapResult>& bitmap_results) {
   return std::find_if(bitmap_results.begin(), bitmap_results.end(), IsValid) !=
       bitmap_results.end();
 }
 
-// Returns the index of the entry with the largest area.
-int GetLargestSizeIndex(const std::vector<gfx::Size>& sizes) {
-  DCHECK(!sizes.empty());
-  size_t ret = 0;
-  for (size_t i = 1; i < sizes.size(); ++i) {
-    if (sizes[ret].GetArea() < sizes[i].GetArea())
-      ret = i;
+std::vector<int> GetDesiredPixelSizes(
+    FaviconDriverObserver::NotificationIconType handler_type) {
+  switch (handler_type) {
+    case FaviconDriverObserver::NON_TOUCH_16_DIP: {
+      std::vector<int> pixel_sizes;
+      for (float scale_factor : favicon_base::GetFaviconScales()) {
+        pixel_sizes.push_back(
+            static_cast<int>(ceil(scale_factor * gfx::kFaviconSize)));
+      }
+      return pixel_sizes;
+    }
+    case FaviconDriverObserver::NON_TOUCH_LARGEST:
+      return std::vector<int>(1U, kNonTouchLargestIconSize);
+    case FaviconDriverObserver::TOUCH_LARGEST:
+      return std::vector<int>(1U, kTouchIconSize);
   }
-  return static_cast<int>(ret);
-}
-
-// Return the index of a size which is same as the given |size|, -1 returned if
-// there is no such bitmap.
-int GetIndexBySize(const std::vector<gfx::Size>& sizes,
-                   const gfx::Size& size) {
-  DCHECK(!sizes.empty());
-  std::vector<gfx::Size>::const_iterator i =
-      std::find(sizes.begin(), sizes.end(), size);
-  if (i == sizes.end())
-    return -1;
-
-  return static_cast<int>(i - sizes.begin());
-}
-
-// Compare function used for std::stable_sort to sort as descend.
-bool CompareIconSize(const FaviconURL& b1, const FaviconURL& b2) {
-  int area1 = 0;
-  if (!b1.icon_sizes.empty())
-    area1 = b1.icon_sizes.front().GetArea();
-
-  int area2 = 0;
-  if (!b2.icon_sizes.empty())
-    area2 = b2.icon_sizes.front().GetArea();
-
-  return area1 > area2;
-}
-
-// Sorts the entries in |image_urls| by icon size in descending order.
-// Discards all but the largest size for each FaviconURL.
-void SortAndPruneImageUrls(std::vector<FaviconURL>* image_urls) {
-  // Not using const-reference since the loop mutates FaviconURL::icon_sizes.
-  for (FaviconURL& image_url : *image_urls) {
-    if (image_url.icon_sizes.empty())
-      continue;
-
-    gfx::Size largest =
-        image_url.icon_sizes[GetLargestSizeIndex(image_url.icon_sizes)];
-    image_url.icon_sizes.clear();
-    image_url.icon_sizes.push_back(largest);
-  }
-  std::stable_sort(image_urls->begin(), image_urls->end(), CompareIconSize);
-}
-
-// Checks whether two FaviconURLs are equal ignoring the icon sizes.
-bool FaviconURLsEqualIgnoringSizes(const FaviconURL& u1, const FaviconURL& u2) {
-  return u1.icon_type == u2.icon_type && u1.icon_url == u2.icon_url;
+  NOTREACHED();
+  return std::vector<int>();
 }
 
 }  // namespace
 
 ////////////////////////////////////////////////////////////////////////////////
 
-FaviconHandler::FaviconCandidate::FaviconCandidate()
-    : score(0), icon_type(favicon_base::INVALID_ICON) {
+// static
+FaviconHandler::FaviconCandidate
+FaviconHandler::FaviconCandidate::FromFaviconURL(
+    const favicon::FaviconURL& favicon_url,
+    const std::vector<int>& desired_pixel_sizes) {
+  FaviconCandidate candidate;
+  candidate.icon_url = favicon_url.icon_url;
+  candidate.icon_type = favicon_url.icon_type;
+  // TODO(crbug.com/705900): For candidates without explicit size information,
+  // sizes could be inferred for the most common cases. Namely, .ico files tend
+  // to contain the 16x16 bitmap, which would allow to improve the
+  // prioritization on desktop.
+  SelectFaviconFrameIndices(favicon_url.icon_sizes, desired_pixel_sizes,
+                            /*best_indices=*/nullptr, &candidate.score);
+  return candidate;
 }
 
-FaviconHandler::FaviconCandidate::~FaviconCandidate() {
-}
-
-FaviconHandler::FaviconCandidate::FaviconCandidate(
-    const GURL& image_url,
-    const gfx::Image& image,
-    float score,
-    favicon_base::IconType icon_type)
-    : image_url(image_url),
-      image(image),
-      score(score),
-      icon_type(icon_type) {}
-
 ////////////////////////////////////////////////////////////////////////////////
 
 FaviconHandler::FaviconHandler(
     FaviconService* service,
     Delegate* delegate,
     FaviconDriverObserver::NotificationIconType handler_type)
     : handler_type_(handler_type),
       got_favicon_from_history_(false),
       initial_history_result_expired_or_incomplete_(false),
       redownload_icons_(false),
@@ skipping 26 matching lines @@
 
 void FaviconHandler::FetchFavicon(const GURL& url) {
   cancelable_task_tracker_.TryCancelAll();
 
   url_ = url;
 
   initial_history_result_expired_or_incomplete_ = false;
   redownload_icons_ = false;
   got_favicon_from_history_ = false;
   download_request_.Cancel();
-  image_urls_.clear();
+  candidates_.clear();
   notification_icon_url_ = GURL();
   notification_icon_type_ = favicon_base::INVALID_ICON;
   current_candidate_index_ = 0u;
-  best_favicon_candidate_ = FaviconCandidate();
+  best_favicon_ = DownloadedFavicon();
 
   // Request the favicon from the history service. In parallel to this the
   // renderer is going to notify us (well WebContents) when the favicon url is
   // available.
   if (service_) {
     service_->GetFaviconForPageURL(
         url_, icon_types_, preferred_icon_size(),
         base::Bind(
             &FaviconHandler::OnFaviconDataForInitialURLFromFaviconService,
             base::Unretained(this)),
         &cancelable_task_tracker_);
   }
 }
 
-bool FaviconHandler::UpdateFaviconCandidate(const GURL& image_url,
-                                            const gfx::Image& image,
-                                            float score,
-                                            favicon_base::IconType icon_type) {
-  bool replace_best_favicon_candidate = false;
-  bool exact_match = false;
+bool FaviconHandler::UpdateFaviconCandidate(
+    const DownloadedFavicon& downloaded_favicon) {
+  if (downloaded_favicon.candidate.score > best_favicon_.candidate.score)
+    best_favicon_ = downloaded_favicon;
+
   if (download_largest_icon_) {
-    replace_best_favicon_candidate =
-        image.Size().GetArea() >
-        best_favicon_candidate_.image.Size().GetArea();
-
-    gfx::Size largest = best_favicon_candidate_.image.Size();
-    if (replace_best_favicon_candidate)
-      largest = image.Size();
-
-    // The size of the downloaded icon may not match the declared size. Stop
-    // downloading if:
+    // The size of the downloaded icon may not match the declared size. It's
+    // important to stop downloading if:
     // - current candidate is only candidate.
-    // - next candidate doesn't have sizes attributes, in this case, the rest
-    //   candidates don't have sizes attribute either, stop downloading now,
-    //   otherwise, all favicon without sizes attribute are downloaded.
-    // - next candidate has sizes attribute and it is not larger than largest,
-    // - current candidate is maximal one we want.
-    const int maximal_size = GetMaximalIconSize(icon_type);
-    if (current_candidate_index_ + 1 >= image_urls_.size()) {
-      exact_match = true;
-    } else {
-      FaviconURL next_image_url = image_urls_[current_candidate_index_ + 1];
-      exact_match = next_image_url.icon_sizes.empty() ||
-          next_image_url.icon_sizes[0].GetArea() <= largest.GetArea() ||
-          (image.Size().width() == maximal_size &&
-           image.Size().height() == maximal_size);
-    }
+    // - next candidate has sizes attribute and it is not better than the best
+    //   one observed so far, which means any following candidate should also
+    //   be worse or equal too.
+    // - next candidate doesn't have sizes attributes, which means further
+    //   candidates don't have sizes attribute either (because the score lowest
+    //   and hence get sorted last during prioritization). We stop immediately
+    //   to avoid downloading them all, although we don't have the certainty
+    //   that no better favicon is among them.
+    return current_candidate_index_ + 1 >= candidates_.size() ||
+           candidates_[current_candidate_index_ + 1].score <=
+               best_favicon_.candidate.score;
   } else {
-    exact_match = score == 1 || preferred_icon_size() == 0;
-    replace_best_favicon_candidate =
-        exact_match ||
-        best_favicon_candidate_.icon_type == favicon_base::INVALID_ICON ||
-        score > best_favicon_candidate_.score;
+    return best_favicon_.candidate.score == 1;
   }
-  if (replace_best_favicon_candidate) {
-    best_favicon_candidate_ =
-        FaviconCandidate(image_url, image, score, icon_type);
-  }
-  return exact_match;
 }
 
 void FaviconHandler::SetFavicon(const GURL& icon_url,
                                 const gfx::Image& image,
                                 favicon_base::IconType icon_type) {
   if (service_ && ShouldSaveFavicon())
     service_->SetFavicons(url_, icon_url, icon_type, image);
 
   NotifyFaviconUpdated(icon_url, icon_type, image);
 }
@@ skipping 32 matching lines @@
   notification_icon_url_ = icon_url;
   notification_icon_type_ = icon_type;
 }
 
 void FaviconHandler::OnUpdateFaviconURL(
     const GURL& page_url,
     const std::vector<FaviconURL>& candidates) {
   if (page_url != url_)
     return;
 
-  std::vector<FaviconURL> pruned_candidates;
+  std::vector<FaviconCandidate> sorted_candidates;
+  const std::vector<int> desired_pixel_sizes =
+      GetDesiredPixelSizes(handler_type_);
   for (const FaviconURL& candidate : candidates) {
-    if (!candidate.icon_url.is_empty() && (candidate.icon_type & icon_types_))
-      pruned_candidates.push_back(candidate);
+    if (!candidate.icon_url.is_empty() && (candidate.icon_type & icon_types_)) {
+      sorted_candidates.push_back(
+          FaviconCandidate::FromFaviconURL(candidate, desired_pixel_sizes));
+    }
   }
 
-  if (download_largest_icon_)
-    SortAndPruneImageUrls(&pruned_candidates);
+  std::stable_sort(sorted_candidates.begin(), sorted_candidates.end(),
+                   &FaviconCandidate::CompareScore);
 
-  // Ignore FaviconURL::icon_sizes because FaviconURL::icon_sizes is not stored
-  // in the history database.
-  if (image_urls_.size() == pruned_candidates.size() &&
-      std::equal(pruned_candidates.begin(), pruned_candidates.end(),
-                 image_urls_.begin(), FaviconURLsEqualIgnoringSizes)) {
+  if (candidates_.size() == sorted_candidates.size() &&
+      std::equal(sorted_candidates.begin(), sorted_candidates.end(),
+                 candidates_.begin())) {
     return;
   }
 
   download_request_.Cancel();
-  image_urls_ = pruned_candidates;
+  candidates_ = std::move(sorted_candidates);
   current_candidate_index_ = 0u;
-  best_favicon_candidate_ = FaviconCandidate();
+  best_favicon_ = DownloadedFavicon();
 
   // TODO(davemoore) Should clear on empty url. Currently we ignore it.
   // This appears to be what FF does as well.
   if (current_candidate() && got_favicon_from_history_)
     OnGotInitialHistoryDataAndIconURLCandidates();
 }
 
-int FaviconHandler::GetMaximalIconSize(favicon_base::IconType icon_type) {
-  switch (icon_type) {
-    case favicon_base::FAVICON:
-#if defined(OS_ANDROID)
-      return 192;
-#else
-      return gfx::ImageSkia::GetMaxSupportedScale() * gfx::kFaviconSize;
-#endif
-    case favicon_base::TOUCH_ICON:
-    case favicon_base::TOUCH_PRECOMPOSED_ICON:
-      return kTouchIconSize;
-    case favicon_base::INVALID_ICON:
-      return 0;
-  }
-  NOTREACHED();
-  return 0;
+// static
+int FaviconHandler::GetMaximalIconSize(
+    FaviconDriverObserver::NotificationIconType handler_type) {
+  int max_size = 0;
+  for (int size : GetDesiredPixelSizes(handler_type))
+    max_size = std::max(max_size, size);
+  return max_size;
 }
 
 void FaviconHandler::OnGotInitialHistoryDataAndIconURLCandidates() {
   if (!initial_history_result_expired_or_incomplete_ &&
-      DoUrlAndIconMatch(*current_candidate(), notification_icon_url_,
-                        notification_icon_type_)) {
+      current_candidate()->icon_url == notification_icon_url_ &&
+      current_candidate()->icon_type == notification_icon_type_) {
     // - The data from history is valid and not expired.
     // - The icon URL of the history data matches one of the page's icon URLs.
     // - The icon URL of the history data matches the icon URL of the last
     //   OnFaviconAvailable() notification.
     // We are done. No additional downloads or history requests are needed.
     // TODO: Store all of the icon URLs associated with a page in history so
     // that we can check whether the page's icon URLs match the page's icon URLs
     // at the time that the favicon data was stored to the history database.
     return;
   }
@@ skipping 15 matching lines @@
     DVLOG(1) << "Failed to Download Favicon:" << image_url;
     if (service_)
       service_->UnableToDownloadFavicon(image_url);
   }
 
   bool request_next_icon = true;
   if (!bitmaps.empty()) {
     float score = 0.0f;
     gfx::ImageSkia image_skia;
     if (download_largest_icon_) {
-      int index = -1;
-      // Use the largest bitmap if FaviconURL doesn't have sizes attribute.
-      if (current_candidate()->icon_sizes.empty()) {
-        index = GetLargestSizeIndex(original_bitmap_sizes);
-      } else {
-        index = GetIndexBySize(original_bitmap_sizes,
-                               current_candidate()->icon_sizes[0]);
-        // Find largest bitmap if there is no one exactly matched.
-        if (index == -1)
-          index = GetLargestSizeIndex(original_bitmap_sizes);
-      }
-      image_skia = gfx::ImageSkia(gfx::ImageSkiaRep(bitmaps[index], 1));
+      std::vector<size_t> best_indices;
+      SelectFaviconFrameIndices(original_bitmap_sizes,
+                                GetDesiredPixelSizes(handler_type_),
+                                &best_indices, &score);
+      DCHECK_EQ(1U, best_indices.size());
+      image_skia =
+          gfx::ImageSkia::CreateFrom1xBitmap(bitmaps[best_indices.front()]);
     } else {
       image_skia = CreateFaviconImageSkia(bitmaps,
                                           original_bitmap_sizes,
                                           preferred_icon_size(),
                                           &score);
     }
 
     if (!image_skia.isNull()) {
-      gfx::Image image(image_skia);
       // The downloaded icon is still valid when there is no FaviconURL update
       // during the downloading.
-      request_next_icon =
-          !UpdateFaviconCandidate(image_url, image, score, icon_type);
+      DownloadedFavicon downloaded_favicon;
+      downloaded_favicon.image = gfx::Image(image_skia);
+      downloaded_favicon.candidate.icon_url = image_url;
+      downloaded_favicon.candidate.icon_type = icon_type;
+      downloaded_favicon.candidate.score = score;
+      request_next_icon = !UpdateFaviconCandidate(downloaded_favicon);
     }
   }
 
-  if (request_next_icon && current_candidate_index_ + 1 < image_urls_.size()) {
+  if (request_next_icon && current_candidate_index_ + 1 < candidates_.size()) {
     // Process the next candidate.
     ++current_candidate_index_;
     DownloadCurrentCandidateOrAskFaviconService();
   } else {
     // We have either found the ideal candidate or run out of candidates.
-    if (best_favicon_candidate_.icon_type != favicon_base::INVALID_ICON) {
+    if (best_favicon_.candidate.icon_type != favicon_base::INVALID_ICON) {
       // No more icons to request, set the favicon from the candidate.
-      SetFavicon(best_favicon_candidate_.image_url,
-                 best_favicon_candidate_.image,
-                 best_favicon_candidate_.icon_type);
+      SetFavicon(best_favicon_.candidate.icon_url, best_favicon_.image,
+                 best_favicon_.candidate.icon_type);
     }
     // Clear download related state.
-    current_candidate_index_ = image_urls_.size();
-    best_favicon_candidate_ = FaviconCandidate();
+    current_candidate_index_ = candidates_.size();
+    best_favicon_ = DownloadedFavicon();
   }
 }
 
+const std::vector<GURL> FaviconHandler::GetIconURLs() const {
+  std::vector<GURL> icon_urls;
+  for (const FaviconCandidate& candidate : candidates_)
+    icon_urls.push_back(candidate.icon_url);
+  return icon_urls;
+}
+
 bool FaviconHandler::HasPendingTasksForTest() {
   return !download_request_.IsCancelled() ||
          cancelable_task_tracker_.HasTrackedTasks();
 }
 
 bool FaviconHandler::ShouldSaveFavicon() {
   if (!delegate_->IsOffTheRecord())
     return true;
 
   // Always save favicon if the page is bookmarked.
   return delegate_->IsBookmarked(url_);
 }
 
 void FaviconHandler::OnFaviconDataForInitialURLFromFaviconService(
     const std::vector<favicon_base::FaviconRawBitmapResult>&
         favicon_bitmap_results) {
   got_favicon_from_history_ = true;
   bool has_valid_result = HasValidResult(favicon_bitmap_results);
   initial_history_result_expired_or_incomplete_ =
       !has_valid_result ||
       HasExpiredOrIncompleteResult(preferred_icon_size(),
                                    favicon_bitmap_results);
   redownload_icons_ = initial_history_result_expired_or_incomplete_ &&
                       !favicon_bitmap_results.empty();
 
-  if (has_valid_result &&
-      (!current_candidate() ||
-       DoUrlsAndIconsMatch(*current_candidate(), favicon_bitmap_results))) {
+  if (has_valid_result && (!current_candidate() ||
+                           DoUrlsAndIconsMatch(current_candidate()->icon_url,
+                                               current_candidate()->icon_type,
+                                               favicon_bitmap_results))) {
     // The db knows the favicon (although it may be out of date) and the entry
     // doesn't have an icon. Set the favicon now, and if the favicon turns out
     // to be expired (or the wrong url) we'll fetch later on. This way the
     // user doesn't see a flash of the default favicon.
     NotifyFaviconUpdated(favicon_bitmap_results);
   }
 
   if (current_candidate())
     OnGotInitialHistoryDataAndIconURLCandidates();
 }
@@ skipping 40 matching lines @@
 
   if (has_valid_result) {
     // There is a valid favicon. Notify any observers. It is useful to notify
     // the observers even if the favicon is expired or incomplete (incorrect
     // size) because temporarily showing the user an expired favicon or
     // streched favicon is preferable to showing the user the default favicon.
     NotifyFaviconUpdated(favicon_bitmap_results);
   }
 
   if (!current_candidate() ||
-      (has_results &&
-       !DoUrlsAndIconsMatch(*current_candidate(), favicon_bitmap_results))) {
+      (has_results && !DoUrlsAndIconsMatch(current_candidate()->icon_url,
+                                           current_candidate()->icon_type,
+                                           favicon_bitmap_results))) {
     // The icon URLs have been updated since the favicon data was requested.
     return;
   }
 
   if (has_expired_or_incomplete_result) {
     ScheduleDownload(current_candidate()->icon_url,
                      current_candidate()->icon_type);
   }
 }
 
 void FaviconHandler::ScheduleDownload(const GURL& image_url,
                                       favicon_base::IconType icon_type) {
   DCHECK(image_url.is_valid());
   // Note that CancelableCallback starts cancelled.
   DCHECK(download_request_.IsCancelled()) << "More than one ongoing download";
   if (service_ && service_->WasUnableToDownloadFavicon(image_url)) {
     DVLOG(1) << "Skip Failed FavIcon: " << image_url;
     OnDidDownloadFavicon(icon_type, 0, 0, image_url, std::vector<SkBitmap>(),
                          std::vector<gfx::Size>());
     return;
   }
   download_request_.Reset(base::Bind(&FaviconHandler::OnDidDownloadFavicon,
                                      base::Unretained(this), icon_type));
   // A max bitmap size is specified to avoid receiving huge bitmaps in
   // OnDidDownloadFavicon(). See FaviconDriver::StartDownload()
   // for more details about the max bitmap size.
-  const int download_id = delegate_->DownloadImage(
-      image_url, GetMaximalIconSize(icon_type), download_request_.callback());
+  const int download_id =
+      delegate_->DownloadImage(image_url, GetMaximalIconSize(handler_type_),
+                               download_request_.callback());
   DCHECK_NE(download_id, 0);
 }
 
 }  // namespace favicon