Always select best favicon bitmap

components/favicon/core/favicon_handler.cc

Index: components/favicon/core/favicon_handler.cc
diff --git a/components/favicon/core/favicon_handler.cc b/components/favicon/core/favicon_handler.cc
index 8ca5df8a1b250aa1722a999d5166ab0075751d75..104606e2f64b547a2e58410f148c43910058b2bd 100644
--- a/components/favicon/core/favicon_handler.cc
+++ b/components/favicon/core/favicon_handler.cc
@@ -23,34 +23,33 @@
 namespace favicon {
 namespace {
 
-// Size (along each axis) of a touch icon. This currently corresponds to
-// the apple touch icon for iPad.
-const int kTouchIconSize = 144;
+// Size (along each axis) of a touch icon.
+#if defined(OS_IOS)
+// This currently corresponds to the apple touch icon for iPad.
+const int kLargestIconSizeInPixels = 144;
+#else
+const int kLargestIconSizeInPixels = 192;
+#endif
 
-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 |expected_icons|
+// have a corresponding entry (same icon URL and type) in |bitmap_results|.
+bool DoUrlAndIconsMatch(
+    const std::vector<favicon_base::FaviconRawBitmapResult>& bitmap_results,
+    const std::map<GURL, favicon_base::IconType>& expected_icons) {
+  std::map<GURL, favicon_base::IconType> actual_icons;
+  for (const auto& bitmap_result : bitmap_results)
+    actual_icons[bitmap_result.icon_url] = bitmap_result.icon_type;
+  return actual_icons == expected_icons;
 }
 
-// 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.
-bool DoUrlsAndIconsMatch(
-    const FaviconURL& favicon_url,
-    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 ||
-        icon_type != bitmap_result.icon_type) {
-      return false;
-    }
+bool ContainsMatchingIcon(const std::vector<favicon::FaviconURL>& favicon_urls,
+                          const GURL& icon_url,
+                          favicon_base::IconType icon_type) {
+  for (const favicon::FaviconURL& favicon_url : favicon_urls) {
+    if (favicon_url.icon_url == icon_url && favicon_url.icon_type == icon_type)
+      return true;
   }
-  return true;
+  return false;
 }
 
 // Return true if |bitmap_result| is expired.
@@ -63,47 +62,11 @@ bool IsValid(const favicon_base::FaviconRawBitmapResult& bitmap_result) {
   return bitmap_result.is_valid();
 }
 
-// Returns true if |bitmap_results| is non-empty and:
-// - At least one of the bitmaps in |bitmap_results| is expired
-// OR
-// - |bitmap_results| is missing favicons for |desired_size_in_dip| and one of
-//   the scale factors in favicon_base::GetFaviconScales().
-bool HasExpiredOrIncompleteResult(
-    int desired_size_in_dip,
+// Returns true at least one of the bitmaps in |bitmap_results| is expired.
+bool HasExpiredResult(
     const std::vector<favicon_base::FaviconRawBitmapResult>& bitmap_results) {
-  if (bitmap_results.empty())
-    return false;
-
-  // Check if at least one of the bitmaps is expired.
-  std::vector<favicon_base::FaviconRawBitmapResult>::const_iterator it =
-      std::find_if(bitmap_results.begin(), bitmap_results.end(), IsExpired);
-  if (it != bitmap_results.end())
-    return true;
-
-  // Any favicon size is good if the desired size is 0.
-  if (desired_size_in_dip == 0)
-    return false;
-
-  // Check if the favicon for at least one of the scale factors is missing.
-  // |bitmap_results| should always be complete for data inserted by
-  // FaviconHandler as the FaviconHandler stores favicons resized to all
-  // of favicon_base::GetFaviconScales() into the history backend.
-  // Examples of when |bitmap_results| can be incomplete:
-  // - Favicons inserted into the history backend by sync.
-  // - Favicons for imported bookmarks.
-  std::vector<gfx::Size> favicon_sizes;
-  for (const auto& bitmap_result : bitmap_results)
-    favicon_sizes.push_back(bitmap_result.pixel_size);
-
-  std::vector<float> favicon_scales = favicon_base::GetFaviconScales();
-  for (float favicon_scale : favicon_scales) {
-    int edge_size_in_pixel = std::ceil(desired_size_in_dip * favicon_scale);
-    auto it = std::find(favicon_sizes.begin(), favicon_sizes.end(),
-                        gfx::Size(edge_size_in_pixel, edge_size_in_pixel));
-    if (it == favicon_sizes.end())
-      return true;
-  }
-  return false;
+  return std::find_if(bitmap_results.begin(), bitmap_results.end(),
+                      IsExpired) != bitmap_results.end();
 }
 
 // Returns true if at least one of |bitmap_results| is valid.
@@ -113,57 +76,44 @@ bool HasValidResult(
       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;
+// Check if the favicon for at least one of the resolutions is missing.
+// |bitmap_results| should always be complete for data inserted by
+// FaviconHandler as the FaviconHandler stores favicons resized to all
+// of |favicon_scales| into the history backend.
+// Examples of when |bitmap_results| can be incomplete:
+// - Favicons inserted into the history backend by sync.
+// - Favicons for imported bookmarks.
+bool HasCompleteResult(
+    const std::vector<FaviconHandler::TargetSizeSpec>& target_size_specs,
+    const std::vector<favicon_base::FaviconRawBitmapResult>& bitmap_results) {
+  for (const FaviconHandler::TargetSizeSpec& target_size_spec :
+       target_size_specs) {
+    if (!target_size_spec.HasMatchingResult(bitmap_results))
+      return false;
   }
-  return static_cast<int>(ret);
+  return true;
 }
 
-// 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 CompareScore(const FaviconHandler::BitmapCandidate& b1,
+                  const FaviconHandler::BitmapCandidate& b2) {
+  return b1.score > b2.score;
 }
 
-// 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);
+// Scores and sorts the entries in |favicon_urls|, best icon size matches first
+// for |target_size_spec|. Pruning means discarding all but the best bitmap per
+// candidate. Returns the sorted, scored and pruned candidate list.
+std::list<FaviconHandler::BitmapCandidate> SortAndPruneCandidates(

[pkotwicz, 2017/03/16 05:31:44]

I know that you use the BitmapCandidate::icon_size property in this method.

I think that the BitmapCandidate return type should not have a
BitmapCandidate::icon_size field. The field is not used anywhere else. This
would make the candidate less confusing.

+    const FaviconHandler::TargetSizeSpec& target_size_spec,
+    const std::vector<favicon::FaviconURL>& favicon_urls) {
+  std::vector<FaviconHandler::BitmapCandidate> candidates;
+  for (const favicon::FaviconURL& favicon_url : favicon_urls)
+    candidates.emplace_back(target_size_spec, favicon_url);
+
+  std::stable_sort(candidates.begin(), candidates.end(), CompareScore);
+  std::list<FaviconHandler::BitmapCandidate> result;
+  std::move(candidates.begin(), candidates.end(), std::back_inserter(result));
+  return result;
 }
 
 // Checks whether two FaviconURLs are equal ignoring the icon sizes.
@@ -171,41 +121,221 @@ bool FaviconURLsEqualIgnoringSizes(const FaviconURL& u1, const FaviconURL& u2) {
   return u1.icon_type == u2.icon_type && u1.icon_url == u2.icon_url;
 }
 
+std::vector<FaviconHandler::TargetSizeSpec> GetTargetSizeSpecs(
+    FaviconDriverObserver::NotificationIconType handler_type) {
+  switch (handler_type) {
+    case FaviconDriverObserver::NON_TOUCH_16_DIP:
+      return FaviconHandler::TargetSizeSpec::For16x16Dips();
+    case FaviconDriverObserver::NON_TOUCH_LARGEST:
+    case FaviconDriverObserver::TOUCH_LARGEST:
+      return {FaviconHandler::TargetSizeSpec::ForLargest()};
+  }
+  NOTREACHED();
+}
+
+gfx::ImageSkia BuildImageFromBestBitmaps(
+    const std::vector<FaviconHandler::BitmapCandidateQueue>& candidate_queues) {
+  std::vector<SkBitmap> bitmaps;
+  std::vector<gfx::Size> sizes;
+  std::vector<float> desired_scale_factors;
+  // Map from scale factor to bitmap.x
+  std::map<float, SkBitmap> bitmaps_per_scale_factor;
+  for (const auto& candidate_queue : candidate_queues) {
+    bitmaps.push_back(candidate_queue.BestBitmap()->second);
+    // TODO(mastiz) / DONOTSUBMIT: Should original size be propagated?
+    sizes.emplace_back(bitmaps.back().width(), bitmaps.back().height());
+    desired_scale_factors.push_back(
+        candidate_queue.TargetSizeSpec().ScaleFactor());
+  }
+  return CreateFaviconImageSkiaWithScaleFactors(
+      bitmaps, sizes, desired_scale_factors, gfx::kFaviconSize);
+}
+
 }  // namespace
 
 ////////////////////////////////////////////////////////////////////////////////
 
-FaviconHandler::DownloadRequest::DownloadRequest()
-    : icon_type(favicon_base::INVALID_ICON) {
+// static
+FaviconHandler::TargetSizeSpec FaviconHandler::TargetSizeSpec::ForLargest() {
+  FaviconHandler::TargetSizeSpec target_size_spec;
+  target_size_spec.pixel_size_ = kLargestIconSizeInPixels;
+  // 0 is special-cased in CreateFaviconImageSkiaWithScaleFactors().
+  target_size_spec.scale_factor_ = 0;
+  target_size_spec.ensure_exact_size_ = false;
+  return target_size_spec;
 }
 
-FaviconHandler::DownloadRequest::~DownloadRequest() {
+// static
+std::vector<FaviconHandler::TargetSizeSpec>
+FaviconHandler::TargetSizeSpec::For16x16Dips() {
+  std::vector<FaviconHandler::TargetSizeSpec> target_size_specs;
+  for (float scale : favicon_base::GetFaviconScales()) {
+    FaviconHandler::TargetSizeSpec target_size_spec;
+    target_size_spec.pixel_size_ = std::ceil(scale * gfx::kFaviconSize);
+    target_size_spec.scale_factor_ = scale;
+    target_size_spec.ensure_exact_size_ = true;
+    target_size_specs.push_back(target_size_spec);
+  }
+  return target_size_specs;
 }
 
-FaviconHandler::DownloadRequest::DownloadRequest(
-    const GURL& image_url,
-    favicon_base::IconType icon_type)
-    : image_url(image_url), icon_type(icon_type) {
+FaviconHandler::TargetSizeSpec::TargetSizeSpec(const TargetSizeSpec&) = default;
+
+FaviconHandler::TargetSizeSpec::~TargetSizeSpec() = default;
+
+FaviconHandler::TargetSizeSpec::TargetSizeSpec(TargetSizeSpec&&) = default;
+
+FaviconHandler::TargetSizeSpec& FaviconHandler::TargetSizeSpec::operator=(
+    FaviconHandler::TargetSizeSpec&&) = default;
+
+bool FaviconHandler::TargetSizeSpec::WantsBestBitmapOnly() const {
+  return !ensure_exact_size_;
 }
 
+bool FaviconHandler::TargetSizeSpec::HasMatchingResult(
+    const std::vector<favicon_base::FaviconRawBitmapResult>& bitmap_results)
+    const {
+  if (WantsBestBitmapOnly())
+    return HasValidResult(bitmap_results);
+
+  const gfx::Size desired_size(pixel_size_, pixel_size_);
+  for (const auto& bitmap_result : bitmap_results) {
+    if (IsValid(bitmap_result) && bitmap_result.pixel_size == desired_size)
+      return true;
+  }
+  return false;
+}
+
+FaviconHandler::TargetSizeSpec::TargetSizeSpec() = default;
+
 ////////////////////////////////////////////////////////////////////////////////
 
-FaviconHandler::FaviconCandidate::FaviconCandidate()
-    : score(0), icon_type(favicon_base::INVALID_ICON) {
+FaviconHandler::BitmapCandidate::BitmapCandidate(
+    const FaviconHandler::TargetSizeSpec& target_size_spec,
+    const favicon::FaviconURL& favicon_url) {
+  icon_url = favicon_url.icon_url;
+  icon_type = favicon_url.icon_type;
+  score = 0;
+  for (const gfx::Size& favicon_size : favicon_url.icon_sizes) {
+    float favicon_score =
+        GetFaviconCandidateScore(favicon_size, target_size_spec.PixelSize());
+    if (favicon_score > score) {
+      score = favicon_score;
+      icon_size = favicon_size;
+    }
+  }
+}
+
+FaviconHandler::BitmapCandidate::BitmapCandidate(const BitmapCandidate&) =
+    default;
+
+FaviconHandler::BitmapCandidate::BitmapCandidate(BitmapCandidate&&) = default;
+
+FaviconHandler::BitmapCandidate& FaviconHandler::BitmapCandidate::operator=(
+    BitmapCandidate&&) = default;
+
+////////////////////////////////////////////////////////////////////////////////
+
+FaviconHandler::BitmapCandidateQueue::BitmapCandidateQueue(
+    const FaviconHandler::TargetSizeSpec& target_size_spec,
+    const std::vector<favicon::FaviconURL>& candidates)
+    : target_size_spec_(target_size_spec),
+      pending_candidates_(SortAndPruneCandidates(target_size_spec, candidates)),

[pkotwicz, 2017/03/16 05:31:45]

In order to guarantee no change in behavior for now, each queue must have the
candidates in the exact same order. I think that each queue should take in its
constructor an already sorted list of candidates

+      best_candidate_(nullptr) {
+  DCHECK(!pending_candidates_.empty());
+}
+
+FaviconHandler::BitmapCandidateQueue::~BitmapCandidateQueue() = default;
+
+FaviconHandler::BitmapCandidateQueue::BitmapCandidateQueue(
+    BitmapCandidateQueue&&) = default;
+
+FaviconHandler::BitmapCandidateQueue& FaviconHandler::BitmapCandidateQueue::
+operator=(FaviconHandler::BitmapCandidateQueue&&) = default;
+
+bool FaviconHandler::BitmapCandidateQueue::IsSatisfied() const {
+  if (target_size_spec_.WantsBestBitmapOnly()) {
+    return best_candidate_ != nullptr;

[pkotwicz, 2017/03/16 05:31:44]

This CL removes the logic handling the case of the downloaded bitmap having a
different size than the declared size. It would be nice if you could write a
separate CL which removes that logic. That way things are super clear

+  } else {
+    // For exact sizes (i.e. not best only), we download all candidates until an
+    // exact match is found.
+    return best_candidate_ != nullptr &&
+           best_candidate_->second.width() == target_size_spec_.PixelSize() &&
+           best_candidate_->second.height() == target_size_spec_.PixelSize();
+  }
 }
 
-FaviconHandler::FaviconCandidate::~FaviconCandidate() {
+// Returns the next candidate to be processed by populating |*candidate|.
+// Returns false if the queue is empty.
+base::Optional<FaviconHandler::BitmapCandidate>
+FaviconHandler::BitmapCandidateQueue::DequeueCandidate() {
+  if (pending_candidates_.empty() || IsSatisfied())
+    return base::Optional<BitmapCandidate>();
+
+  base::Optional<BitmapCandidate> result =
+      std::move(pending_candidates_.front());
+  pending_candidates_.pop_front();
+  return result;
+}
+
+const FaviconHandler::BitmapCandidate*
+FaviconHandler::BitmapCandidateQueue::CurrentCandidate() const {
+  if (pending_candidates_.empty() || IsSatisfied())
+    return nullptr;
+
+  return &pending_candidates_.front();
+}
+
+void FaviconHandler::BitmapCandidateQueue::ProcessDownloadedImage(
+    const BitmapCandidate& candidate,
+    const std::vector<SkBitmap>& bitmaps) {
+  LOG(INFO) << "ProcessDownloadedImage() " << candidate.icon_url << " for size "
+            << target_size_spec_.PixelSize();
+  // Remove potentially queued candidates for |icon_url| (this happens if the
+  // candidate was dequeued from another queue).
+  pending_candidates_.remove_if([&candidate](const BitmapCandidate& c) {
+    return c.icon_url == candidate.icon_url;
+  });
+
+  // Select the best bitmap, which to be relevant needs to be better than the
+  // best known bitmap until now.
+  float best_score = best_candidate_ ? best_candidate_->first.score : -1;
+  const SkBitmap* best_bitmap = nullptr;
+  for (const SkBitmap& bitmap : bitmaps) {
+    const float bitmap_score =
+        GetFaviconCandidateScore(gfx::Size(bitmap.width(), bitmap.height()),
+                                 target_size_spec_.PixelSize());

[pkotwicz, 2017/03/16 05:31:44]

Here you need to call SelectFaviconFrameIndices() to compute the score here.
Otherwise, you might end up using different icon URLs for different sizes. We
are not ready for that yet.

+    LOG(INFO) << "new score " << bitmap_score << " vs " << best_score;
+    if (bitmap_score > best_score) {
+      best_bitmap = &bitmap;
+      best_score = bitmap_score;
+    }
+  }
+
+  // No interesting bitmap, nothing to be done (|icon_url| has already been
+  // removed from the queue).
+  if (best_bitmap == nullptr)
+    return;
+
+  LOG(INFO) << "Assigning new best candidate for size "
+            << target_size_spec_.PixelSize() << ": " << candidate.icon_url;
+  best_candidate_.reset(
+      new std::pair<BitmapCandidate, SkBitmap>(candidate, *best_bitmap));
+  // Score could have changed since we now know the actual image size.
+  best_candidate_->first.score = best_score;
 }
 
-FaviconHandler::FaviconCandidate::FaviconCandidate(
+////////////////////////////////////////////////////////////////////////////////
+
+FaviconHandler::DownloadRequest::DownloadRequest()
+    : icon_type(favicon_base::INVALID_ICON) {}
+
+FaviconHandler::DownloadRequest::~DownloadRequest() {}
+
+FaviconHandler::DownloadRequest::DownloadRequest(
     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) {}
+    : image_url(image_url), icon_type(icon_type) {}
 
 ////////////////////////////////////////////////////////////////////////////////
 
@@ -218,15 +348,13 @@ FaviconHandler::FaviconHandler(
       initial_history_result_expired_or_incomplete_(false),
       redownload_icons_(false),
       icon_types_(FaviconHandler::GetIconTypesFromHandlerType(handler_type)),
-      download_largest_icon_(
-          handler_type == FaviconDriverObserver::NON_TOUCH_LARGEST ||
-          handler_type == FaviconDriverObserver::TOUCH_LARGEST),
+      target_size_specs_(GetTargetSizeSpecs(handler_type)),
       notification_icon_type_(favicon_base::INVALID_ICON),
       service_(service),
       delegate_(delegate),
-      current_candidate_index_(0u),
       weak_ptr_factory_(this) {
   DCHECK(delegate_);
+  DCHECK(!target_size_specs_.empty());
 }
 
 FaviconHandler::~FaviconHandler() {
@@ -245,6 +373,21 @@ int FaviconHandler::GetIconTypesFromHandlerType(
   return 0;
 }
 
+std::vector<int> FaviconHandler::GetTargetPixelSizes() const {
+  std::vector<int> result;
+  for (const TargetSizeSpec& target_size_spec : target_size_specs_)
+    result.push_back(target_size_spec.PixelSize());
+  return result;
+}
+
+std::map<int, float> FaviconHandler::GetTargetPixelSizesAndScaleFactors()
+    const {
+  std::map<int, float> result;
+  for (const TargetSizeSpec& target_size_spec : target_size_specs_)
+    result[target_size_spec.PixelSize()] = target_size_spec.ScaleFactor();
+  return result;
+}
+
 void FaviconHandler::FetchFavicon(const GURL& url) {
   cancelable_task_tracker_.TryCancelAll();
 
@@ -254,18 +397,16 @@ void FaviconHandler::FetchFavicon(const GURL& url) {
   redownload_icons_ = false;
   got_favicon_from_history_ = false;
   download_requests_.clear();
-  image_urls_.clear();
   notification_icon_url_ = GURL();
   notification_icon_type_ = favicon_base::INVALID_ICON;
-  current_candidate_index_ = 0u;
-  best_favicon_candidate_ = FaviconCandidate();
+  current_candidate_.reset();
 
   // 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(),
+        url_, icon_types_, GetTargetPixelSizes(),
         base::Bind(
             &FaviconHandler::OnFaviconDataForInitialURLFromFaviconService,
             base::Unretained(this)),
@@ -273,53 +414,6 @@ void FaviconHandler::FetchFavicon(const GURL& url) {
   }
 }
 
-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;
-  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:
-    // - 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);
-    }
-  } 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;
-  }
-  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) {
@@ -335,10 +429,10 @@ void FaviconHandler::NotifyFaviconUpdated(
   if (favicon_bitmap_results.empty())
     return;
 
-  gfx::Image resized_image = favicon_base::SelectFaviconFramesFromPNGs(
-      favicon_bitmap_results,
-      favicon_base::GetFaviconScales(),
-      preferred_icon_size());
+  gfx::Image resized_image =
+      favicon_base::SelectFaviconFramesForPixelSizesFromPNGs(
+          favicon_bitmap_results, GetTargetPixelSizesAndScaleFactors());
+
   // The history service sends back results for a single icon URL and icon
   // type, so it does not matter which result we get |icon_url| and |icon_type|
   // from.
@@ -370,56 +464,48 @@ void FaviconHandler::OnUpdateFaviconURL(
   if (page_url != url_)
     return;
 
-  std::vector<FaviconURL> pruned_candidates;
+  std::vector<FaviconURL> filtered_candidates;
+  std::set<GURL> urls_to_filter;
+  urls_to_filter.insert(GURL());
+
   for (const FaviconURL& candidate : candidates) {
-    if (!candidate.icon_url.is_empty() && (candidate.icon_type & icon_types_))
-      pruned_candidates.push_back(candidate);
+    if (urls_to_filter.count(candidate.icon_url) == 0 &&
+        (candidate.icon_type & icon_types_)) {
+      filtered_candidates.push_back(candidate);
+      urls_to_filter.insert(candidate.icon_url);
+    }
   }
 
-  if (download_largest_icon_)
-    SortAndPruneImageUrls(&pruned_candidates);
-
   // 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(),
+  if (image_urls_.size() == filtered_candidates.size() &&
+      std::equal(filtered_candidates.begin(), filtered_candidates.end(),
                  image_urls_.begin(), FaviconURLsEqualIgnoringSizes)) {
     return;
   }
 
+  image_urls_ = filtered_candidates;
+  candidate_queues_.clear();
+  current_candidate_.reset();
   download_requests_.clear();
-  image_urls_ = pruned_candidates;
-  current_candidate_index_ = 0u;
-  best_favicon_candidate_ = FaviconCandidate();
+
+  if (image_urls_.empty())
+    return;
+
+  // Reset the state of all candidate queues.
+  for (const TargetSizeSpec& target_size_spec : target_size_specs_)
+    candidate_queues_.emplace_back(target_size_spec, image_urls_);
 
   // 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_)
+  if (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;
-}
-
 void FaviconHandler::OnGotInitialHistoryDataAndIconURLCandidates() {
   if (!initial_history_result_expired_or_incomplete_ &&
-      DoUrlAndIconMatch(*current_candidate(), notification_icon_url_,
-                        notification_icon_type_)) {
+      ContainsMatchingIcon(image_urls_, notification_icon_url_,
+                           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
@@ -431,7 +517,7 @@ void FaviconHandler::OnGotInitialHistoryDataAndIconURLCandidates() {
     return;
   }
 
-  DownloadCurrentCandidateOrAskFaviconService();
+  DownloadNextCandidateOrAskFaviconService();
 }
 
 void FaviconHandler::OnDidDownloadFavicon(
@@ -440,6 +526,10 @@ void FaviconHandler::OnDidDownloadFavicon(
     const GURL& image_url,
     const std::vector<SkBitmap>& bitmaps,
     const std::vector<gfx::Size>& original_bitmap_sizes) {
+  LOG(INFO) << "OnDidDownloadFavicon() " << image_url;
+
+  DCHECK(current_candidate_.has_value());
+
   if (bitmaps.empty() && http_status_code == 404) {
     DVLOG(1) << "Failed to Download Favicon:" << image_url;
     if (service_)
@@ -456,63 +546,13 @@ void FaviconHandler::OnDidDownloadFavicon(
   DownloadRequest download_request = i->second;
   download_requests_.erase(i);
 
-  if (!current_candidate() ||
-      !DoUrlAndIconMatch(*current_candidate(),
-                         image_url,
-                         download_request.icon_type)) {
-    return;
-  }
-
-  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));
-    } 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,
-                                                  download_request.icon_type);
-    }
+    for (BitmapCandidateQueue& candidate_queue : candidate_queues_)
+      candidate_queue.ProcessDownloadedImage(current_candidate_.value(),

[pkotwicz, 2017/03/16 05:31:44]

Umm, shouldn't |original_bitmap_sizes| be passed in to ProcessDownloadedImage()
?

We care about |original_bitmap_sizes| in the case that the sizes in <link
sizes=""> are empty. The desktop version of most sites does not specify sizes.

+                                             bitmaps);
   }
 
-  if (request_next_icon && current_candidate_index_ + 1 < image_urls_.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) {
-      // 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);
-    }
-    // Clear download related state.
-    download_requests_.clear();
-    current_candidate_index_ = image_urls_.size();
-    best_favicon_candidate_ = FaviconCandidate();
-  }
+  DownloadNextCandidateOrAskFaviconService();
 }
 
 bool FaviconHandler::HasPendingTasksForTest() {
@@ -534,15 +574,40 @@ void FaviconHandler::OnFaviconDataForInitialURLFromFaviconService(
   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);
+      !has_valid_result || HasExpiredResult(favicon_bitmap_results) ||
+      !HasCompleteResult(target_size_specs_, favicon_bitmap_results);
   redownload_icons_ = initial_history_result_expired_or_incomplete_ &&
                       !favicon_bitmap_results.empty();
 
+  // Compute which icon URLs are most likely to be relevant, which can only
+  // make use of explicit size information because the images haven't been
+  // downloaded yet.
+  std::map<GURL, favicon_base::IconType> most_promising_icons;
+  if (current_candidate_.has_value()) {
+    most_promising_icons[current_candidate_.value().icon_url] =
+        current_candidate_.value().icon_type;
+  }
+  for (const BitmapCandidateQueue& candidate_queue : candidate_queues_) {
+    const BitmapCandidate* candidate = candidate_queue.CurrentCandidate();
+    if (candidate)
+      most_promising_icons[candidate->icon_url] = candidate->icon_type;
+  }
+
   if (has_valid_result &&
-      (!current_candidate() ||
-       DoUrlsAndIconsMatch(*current_candidate(), favicon_bitmap_results))) {
+      !DoUrlAndIconsMatch(favicon_bitmap_results, most_promising_icons)) {
+    LOG(INFO)
+        << "************ Valid but mismatching results received ************";
+    for (const auto& r : favicon_bitmap_results) {
+      LOG(INFO) << "   result: " << r.icon_url;
+    }
+    for (const auto& r : most_promising_icons) {
+      LOG(INFO) << "   promising candidates: " << r.first;
+    }
+  }
+
+  if (has_valid_result &&
+      (!current_candidate_.has_value() ||
+       DoUrlAndIconsMatch(favicon_bitmap_results, most_promising_icons))) {
     // 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
@@ -550,13 +615,44 @@ void FaviconHandler::OnFaviconDataForInitialURLFromFaviconService(
     NotifyFaviconUpdated(favicon_bitmap_results);
   }
 
-  if (current_candidate())
+  if (!image_urls_.empty())
     OnGotInitialHistoryDataAndIconURLCandidates();
 }
 
-void FaviconHandler::DownloadCurrentCandidateOrAskFaviconService() {
-  GURL icon_url = current_candidate()->icon_url;
-  favicon_base::IconType icon_type = current_candidate()->icon_type;
+void FaviconHandler::DownloadNextCandidateOrAskFaviconService() {
+  // Dequeue the next candidate to be processed.
+  current_candidate_.reset();
+  for (BitmapCandidateQueue& candidate_queue : candidate_queues_) {

[pkotwicz, 2017/03/16 05:31:44]

I think that the IsSatisfied() check should be done here instead of in
DequeueCandidate()

+    current_candidate_ = candidate_queue.DequeueCandidate();
+    if (current_candidate_.has_value())
+      break;
+  }
+
+  LOG(INFO) << "Any further candidates? " << current_candidate_.has_value();
+
+  if (!current_candidate_.has_value()) {
+    // We have either found the satisfying candidates or run out of candidates.
+    if (candidate_queues_.front().BestBitmap()) {
+      gfx::ImageSkia image_skia = BuildImageFromBestBitmaps(candidate_queues_);
+      DCHECK(!image_skia.isNull());
+      // No more icons to request, set the favicon from the candidate. Since
+      // multiple icon URLs could be involved, we pick the first.
+      // TODO(mastiz): Extend SetFavicons to receive all image URLs, probably
+      // with a map from image URL to image.
+      SetFavicon(candidate_queues_.front().BestBitmap()->first.icon_url,

[pkotwicz, 2017/03/16 05:31:44]

This is bad. If
- page_urlA maps to icon_url1 and icon_url2
- page_urlB maps to just icon_url1
- the best bitmaps for page_urlA is to use both icon_url1 and icon_url2

The call to SetFavicon() will make page_urlB use icon_url1 and icon_url2. This
is a bug

You need to restrain the current logic so that it selects all of the bitmaps
from the same icon URL

+                 gfx::Image(image_skia),
+                 candidate_queues_.front().BestBitmap()->first.icon_type);
+    }
+    // Clear download related state.
+    download_requests_.clear();
+    candidate_queues_.clear();
+    current_candidate_.reset();
+    return;
+  }
+
+  GURL icon_url = current_candidate_.value().icon_url;
+  favicon_base::IconType icon_type = current_candidate_.value().icon_type;
+  LOG(INFO) << "Current candidate is: " << icon_url;
 
   if (redownload_icons_) {
     // We have the mapping, but the favicon is out of date. Download it now.
@@ -567,7 +663,7 @@ void FaviconHandler::DownloadCurrentCandidateOrAskFaviconService() {
     // favicon given the favicon URL.
     if (delegate_->IsOffTheRecord()) {
       service_->GetFavicon(
-          icon_url, icon_type, preferred_icon_size(),
+          icon_url, icon_type, GetTargetPixelSizes(),
           base::Bind(&FaviconHandler::OnFaviconData, base::Unretained(this)),
           &cancelable_task_tracker_);
     } else {
@@ -579,7 +675,7 @@ void FaviconHandler::DownloadCurrentCandidateOrAskFaviconService() {
       // TODO(pkotwicz): pass in all of |image_urls_| to
       // UpdateFaviconMappingsAndFetch().
       service_->UpdateFaviconMappingsAndFetch(
-          url_, {icon_url}, icon_type, preferred_icon_size(),
+          url_, {icon_url}, icon_type, GetTargetPixelSizes(),
           base::Bind(&FaviconHandler::OnFaviconData, base::Unretained(this)),
           &cancelable_task_tracker_);
     }
@@ -588,11 +684,11 @@ void FaviconHandler::DownloadCurrentCandidateOrAskFaviconService() {
 
 void FaviconHandler::OnFaviconData(const std::vector<
     favicon_base::FaviconRawBitmapResult>& favicon_bitmap_results) {
-  bool has_results = !favicon_bitmap_results.empty();
+  LOG(INFO) << "OnFaviconData() got " << favicon_bitmap_results.size();
   bool has_valid_result = HasValidResult(favicon_bitmap_results);
   bool has_expired_or_incomplete_result =
-      !has_valid_result || HasExpiredOrIncompleteResult(preferred_icon_size(),
-                                                        favicon_bitmap_results);
+      !has_valid_result || HasExpiredResult(favicon_bitmap_results) ||
+      !HasCompleteResult(target_size_specs_, favicon_bitmap_results);
 
   if (has_valid_result) {
     // There is a valid favicon. Notify any observers. It is useful to notify
@@ -602,16 +698,14 @@ void FaviconHandler::OnFaviconData(const std::vector<
     NotifyFaviconUpdated(favicon_bitmap_results);
   }
 
-  if (!current_candidate() ||
-      (has_results &&
-       !DoUrlsAndIconsMatch(*current_candidate(), favicon_bitmap_results))) {
+  if (!current_candidate_.has_value()) {
     // The icon URLs have been updated since the favicon data was requested.
-    return;
+    DCHECK(0) << "Dead code?";  // DONOTSUBMIT / TODO(mastiz);
   }
 
-  if (has_expired_or_incomplete_result) {
-    ScheduleDownload(current_candidate()->icon_url,
-                     current_candidate()->icon_type);
+  if (current_candidate_.has_value() && has_expired_or_incomplete_result) {
+    ScheduleDownload(current_candidate_.value().icon_url,
+                     current_candidate_.value().icon_type);
   }
 }
 
@@ -630,8 +724,12 @@ void FaviconHandler::ScheduleDownload(const GURL& image_url,
   // A max bitmap size is specified to avoid receiving huge bitmaps in
   // OnDidDownloadFavicon(). See FaviconDriver::StartDownload()
   // for more details about the max bitmap size.
+  int max_pixel_size = 0;
+  for (const TargetSizeSpec& target_size_spec : target_size_specs_)
+    max_pixel_size = std::max(max_pixel_size, target_size_spec.PixelSize());
+
   const int download_id =
-      delegate_->DownloadImage(image_url, GetMaximalIconSize(icon_type),
+      delegate_->DownloadImage(image_url, max_pixel_size,
                                base::Bind(&FaviconHandler::OnDidDownloadFavicon,
                                           weak_ptr_factory_.GetWeakPtr()));
   DCHECK_NE(download_id, 0);