favicon_cache.cc revision 116680a4aac90f2aa7413d9095a592090648e557 
1// Copyright 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "chrome/browser/sync/glue/favicon_cache.h"
6
7#include "base/message_loop/message_loop.h"
8#include "base/metrics/histogram.h"
9#include "chrome/browser/chrome_notification_types.h"
10#include "chrome/browser/favicon/favicon_service.h"
11#include "chrome/browser/favicon/favicon_service_factory.h"
12#include "chrome/browser/history/history_notifications.h"
13#include "chrome/browser/history/history_types.h"
14#include "content/public/browser/notification_details.h"
15#include "content/public/browser/notification_source.h"
16#include "sync/api/time.h"
17#include "sync/protocol/favicon_image_specifics.pb.h"
18#include "sync/protocol/favicon_tracking_specifics.pb.h"
19#include "sync/protocol/sync.pb.h"
20#include "ui/gfx/favicon_size.h"
21
22namespace browser_sync {
23
24// Synced favicon storage and tracking.
25// Note: we don't use the favicon service for storing these because these
26// favicons are not necessarily associated with any local navigation, and
27// hence would not work with the current expiration logic. We have custom
28// expiration logic based on visit time/bookmark status/etc.
29// See crbug.com/122890.
30struct SyncedFaviconInfo {
31  explicit SyncedFaviconInfo(const GURL& favicon_url)
32      : favicon_url(favicon_url),
33        is_bookmarked(false),
34        received_local_update(false) {}
35
36  // The actual favicon data.
37  // TODO(zea): don't keep around the actual data for locally sourced
38  // favicons (UI can access those directly).
39  favicon_base::FaviconRawBitmapResult bitmap_data[NUM_SIZES];
40  // The URL this favicon was loaded from.
41  const GURL favicon_url;
42  // Is the favicon for a bookmarked page?
43  bool is_bookmarked;
44  // The last time a tab needed this favicon.
45  // Note: Do not modify this directly! It should only be modified via
46  // UpdateFaviconVisitTime(..).
47  base::Time last_visit_time;
48  // Whether we've received a local update for this favicon since starting up.
49  bool received_local_update;
50
51 private:
52  DISALLOW_COPY_AND_ASSIGN(SyncedFaviconInfo);
53};
54
55// Information for handling local favicon updates. Used in
56// OnFaviconDataAvailable.
57struct LocalFaviconUpdateInfo {
58  LocalFaviconUpdateInfo()
59      : new_image(false),
60        new_tracking(false),
61        image_needs_rewrite(false),
62        favicon_info(NULL) {}
63
64  bool new_image;
65  bool new_tracking;
66  bool image_needs_rewrite;
67  SyncedFaviconInfo* favicon_info;
68};
69
70namespace {
71
72// Maximum number of favicons to keep in memory (0 means no limit).
73const size_t kMaxFaviconsInMem = 0;
74
75// Maximum width/height resolution supported.
76const int kMaxFaviconResolution = 16;
77
78// Returns a mask of the supported favicon types.
79// TODO(zea): Supporting other favicons types will involve some work in the
80// favicon service and navigation controller. See crbug.com/181068.
81int SupportedFaviconTypes() { return favicon_base::FAVICON; }
82
83// Returns the appropriate IconSize to use for a given gfx::Size pixel
84// dimensions.
85IconSize GetIconSizeBinFromBitmapResult(const gfx::Size& pixel_size) {
86  int max_size =
87      (pixel_size.width() > pixel_size.height() ?
88       pixel_size.width() : pixel_size.height());
89  // TODO(zea): re-enable 64p and 32p resolutions once we support them.
90  if (max_size > 64)
91    return SIZE_INVALID;
92  else if (max_size > 32)
93    return SIZE_INVALID;
94  else if (max_size > 16)
95    return SIZE_INVALID;
96  else
97    return SIZE_16;
98}
99
100// Helper for debug statements.
101std::string IconSizeToString(IconSize icon_size) {
102  switch (icon_size) {
103    case SIZE_16:
104      return "16";
105    case SIZE_32:
106      return "32";
107    case SIZE_64:
108      return "64";
109    default:
110      return "INVALID";
111  }
112}
113
114// Extract the favicon url from either of the favicon types.
115GURL GetFaviconURLFromSpecifics(const sync_pb::EntitySpecifics& specifics) {
116  if (specifics.has_favicon_tracking())
117    return GURL(specifics.favicon_tracking().favicon_url());
118  else
119    return GURL(specifics.favicon_image().favicon_url());
120}
121
122// Convert protobuf image data into a FaviconRawBitmapResult.
123favicon_base::FaviconRawBitmapResult GetImageDataFromSpecifics(
124    const sync_pb::FaviconData& favicon_data) {
125  base::RefCountedString* temp_string =
126      new base::RefCountedString();
127  temp_string->data() = favicon_data.favicon();
128  favicon_base::FaviconRawBitmapResult bitmap_result;
129  bitmap_result.bitmap_data = temp_string;
130  bitmap_result.pixel_size.set_height(favicon_data.height());
131  bitmap_result.pixel_size.set_width(favicon_data.width());
132  return bitmap_result;
133}
134
135// Convert a FaviconRawBitmapResult into protobuf image data.
136void FillSpecificsWithImageData(
137    const favicon_base::FaviconRawBitmapResult& bitmap_result,
138    sync_pb::FaviconData* favicon_data) {
139  if (!bitmap_result.bitmap_data.get())
140    return;
141  favicon_data->set_height(bitmap_result.pixel_size.height());
142  favicon_data->set_width(bitmap_result.pixel_size.width());
143  favicon_data->set_favicon(bitmap_result.bitmap_data->front(),
144                            bitmap_result.bitmap_data->size());
145}
146
147// Build a FaviconImageSpecifics from a SyncedFaviconInfo.
148void BuildImageSpecifics(
149    const SyncedFaviconInfo* favicon_info,
150    sync_pb::FaviconImageSpecifics* image_specifics) {
151  image_specifics->set_favicon_url(favicon_info->favicon_url.spec());
152  FillSpecificsWithImageData(favicon_info->bitmap_data[SIZE_16],
153                             image_specifics->mutable_favicon_web());
154  // TODO(zea): bring this back if we can handle the load.
155  // FillSpecificsWithImageData(favicon_info->bitmap_data[SIZE_32],
156  //                            image_specifics->mutable_favicon_web_32());
157  // FillSpecificsWithImageData(favicon_info->bitmap_data[SIZE_64],
158  //                            image_specifics->mutable_favicon_touch_64());
159}
160
161// Build a FaviconTrackingSpecifics from a SyncedFaviconInfo.
162void BuildTrackingSpecifics(
163    const SyncedFaviconInfo* favicon_info,
164    sync_pb::FaviconTrackingSpecifics* tracking_specifics) {
165  tracking_specifics->set_favicon_url(favicon_info->favicon_url.spec());
166  tracking_specifics->set_last_visit_time_ms(
167      syncer::TimeToProtoTime(favicon_info->last_visit_time));
168  tracking_specifics->set_is_bookmarked(favicon_info->is_bookmarked);
169}
170
171// Updates |favicon_info| with the image data in |bitmap_result|.
172bool UpdateFaviconFromBitmapResult(
173    const favicon_base::FaviconRawBitmapResult& bitmap_result,
174    SyncedFaviconInfo* favicon_info) {
175  DCHECK_EQ(favicon_info->favicon_url, bitmap_result.icon_url);
176  if (!bitmap_result.is_valid()) {
177    DVLOG(1) << "Received invalid favicon at " << bitmap_result.icon_url.spec();
178    return false;
179  }
180
181  IconSize icon_size = GetIconSizeBinFromBitmapResult(
182      bitmap_result.pixel_size);
183  if (icon_size == SIZE_INVALID) {
184    DVLOG(1) << "Ignoring unsupported resolution "
185             << bitmap_result.pixel_size.height() << "x"
186             << bitmap_result.pixel_size.width();
187    return false;
188  } else if (!favicon_info->bitmap_data[icon_size].bitmap_data.get() ||
189             !favicon_info->received_local_update) {
190    DVLOG(1) << "Storing " << IconSizeToString(icon_size) << "p"
191             << " favicon for " << favicon_info->favicon_url.spec()
192             << " with size " << bitmap_result.bitmap_data->size()
193             << " bytes.";
194    favicon_info->bitmap_data[icon_size] = bitmap_result;
195    favicon_info->received_local_update = true;
196    return true;
197  } else {
198    // We only allow updating the image data once per restart.
199    DVLOG(2) << "Ignoring local update for " << bitmap_result.icon_url.spec();
200    return false;
201  }
202}
203
204bool FaviconInfoHasImages(const SyncedFaviconInfo& favicon_info) {
205  return favicon_info.bitmap_data[SIZE_16].bitmap_data.get() ||
206         favicon_info.bitmap_data[SIZE_32].bitmap_data.get() ||
207         favicon_info.bitmap_data[SIZE_64].bitmap_data.get();
208}
209
210bool FaviconInfoHasTracking(const SyncedFaviconInfo& favicon_info) {
211  return !favicon_info.last_visit_time.is_null();
212}
213
214bool FaviconInfoHasValidTypeData(const SyncedFaviconInfo& favicon_info,
215                             syncer::ModelType type) {
216  if (type == syncer::FAVICON_IMAGES)
217    return FaviconInfoHasImages(favicon_info);
218  else if (type == syncer::FAVICON_TRACKING)
219    return FaviconInfoHasTracking(favicon_info);
220  NOTREACHED();
221  return false;
222}
223
224}  // namespace
225
226FaviconCache::FaviconCache(Profile* profile, int max_sync_favicon_limit)
227    : profile_(profile),
228      max_sync_favicon_limit_(max_sync_favicon_limit),
229      weak_ptr_factory_(this) {
230  notification_registrar_.Add(this,
231                              chrome::NOTIFICATION_HISTORY_URLS_DELETED,
232                              content::Source<Profile>(profile_));
233  DVLOG(1) << "Setting favicon limit to " << max_sync_favicon_limit;
234}
235
236FaviconCache::~FaviconCache() {}
237
238syncer::SyncMergeResult FaviconCache::MergeDataAndStartSyncing(
239    syncer::ModelType type,
240    const syncer::SyncDataList& initial_sync_data,
241    scoped_ptr<syncer::SyncChangeProcessor> sync_processor,
242    scoped_ptr<syncer::SyncErrorFactory> error_handler) {
243  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
244  if (type == syncer::FAVICON_IMAGES)
245    favicon_images_sync_processor_ = sync_processor.Pass();
246  else
247    favicon_tracking_sync_processor_ = sync_processor.Pass();
248
249  syncer::SyncMergeResult merge_result(type);
250  merge_result.set_num_items_before_association(synced_favicons_.size());
251  std::set<GURL> unsynced_favicon_urls;
252  for (FaviconMap::const_iterator iter = synced_favicons_.begin();
253       iter != synced_favicons_.end(); ++iter) {
254    if (FaviconInfoHasValidTypeData(*(iter->second), type))
255      unsynced_favicon_urls.insert(iter->first);
256  }
257
258  syncer::SyncChangeList local_changes;
259  for (syncer::SyncDataList::const_iterator iter = initial_sync_data.begin();
260       iter != initial_sync_data.end(); ++iter) {
261    GURL remote_url = GetFaviconURLFromSpecifics(iter->GetSpecifics());
262    GURL favicon_url = GetLocalFaviconFromSyncedData(*iter);
263    if (favicon_url.is_valid()) {
264      unsynced_favicon_urls.erase(favicon_url);
265      MergeSyncFavicon(*iter, &local_changes);
266      merge_result.set_num_items_modified(
267          merge_result.num_items_modified() + 1);
268    } else {
269      AddLocalFaviconFromSyncedData(*iter);
270      merge_result.set_num_items_added(merge_result.num_items_added() + 1);
271    }
272  }
273
274  // Rather than trigger a bunch of deletions when we set up sync, we drop
275  // local favicons. Those pages that are currently open are likely to result in
276  // loading new favicons/refreshing old favicons anyways, at which point
277  // they'll be re-added and the appropriate synced favicons will be evicted.
278  // TODO(zea): implement a smarter ordering of the which favicons to drop.
279  int available_favicons = max_sync_favicon_limit_ - initial_sync_data.size();
280  UMA_HISTOGRAM_BOOLEAN("Sync.FaviconsAvailableAtMerge",
281                        available_favicons > 0);
282  for (std::set<GURL>::const_iterator iter = unsynced_favicon_urls.begin();
283       iter != unsynced_favicon_urls.end(); ++iter) {
284    if (available_favicons > 0) {
285      local_changes.push_back(
286          syncer::SyncChange(FROM_HERE,
287                             syncer::SyncChange::ACTION_ADD,
288                             CreateSyncDataFromLocalFavicon(type, *iter)));
289      available_favicons--;
290    } else {
291      FaviconMap::iterator favicon_iter = synced_favicons_.find(*iter);
292      DVLOG(1) << "Dropping local favicon "
293               << favicon_iter->second->favicon_url.spec();
294      DropPartialFavicon(favicon_iter, type);
295      merge_result.set_num_items_deleted(merge_result.num_items_deleted() + 1);
296    }
297  }
298  UMA_HISTOGRAM_COUNTS_10000("Sync.FaviconCount", synced_favicons_.size());
299  merge_result.set_num_items_after_association(synced_favicons_.size());
300
301  if (type == syncer::FAVICON_IMAGES) {
302    favicon_images_sync_processor_->ProcessSyncChanges(FROM_HERE,
303                                                       local_changes);
304  } else {
305    favicon_tracking_sync_processor_->ProcessSyncChanges(FROM_HERE,
306                                                         local_changes);
307  }
308  return merge_result;
309}
310
311void FaviconCache::StopSyncing(syncer::ModelType type) {
312  favicon_images_sync_processor_.reset();
313  favicon_tracking_sync_processor_.reset();
314  cancelable_task_tracker_.TryCancelAll();
315  page_task_map_.clear();
316}
317
318syncer::SyncDataList FaviconCache::GetAllSyncData(syncer::ModelType type)
319    const {
320  syncer::SyncDataList data_list;
321  for (FaviconMap::const_iterator iter = synced_favicons_.begin();
322       iter != synced_favicons_.end(); ++iter) {
323    if ((type == syncer::FAVICON_IMAGES &&
324         FaviconInfoHasImages(*iter->second)) ||
325        (type == syncer::FAVICON_TRACKING &&
326         FaviconInfoHasTracking(*iter->second))) {
327      data_list.push_back(CreateSyncDataFromLocalFavicon(type, iter->first));
328    }
329  }
330  return data_list;
331}
332
333syncer::SyncError FaviconCache::ProcessSyncChanges(
334    const tracked_objects::Location& from_here,
335    const syncer::SyncChangeList& change_list) {
336  if (!favicon_images_sync_processor_.get() ||
337      !favicon_tracking_sync_processor_.get()) {
338    return syncer::SyncError(FROM_HERE,
339                             syncer::SyncError::DATATYPE_ERROR,
340                             "One or both favicon types disabled.",
341                             change_list[0].sync_data().GetDataType());
342  }
343
344  syncer::SyncChangeList new_changes;
345  syncer::SyncError error;
346  syncer::ModelType type = syncer::UNSPECIFIED;
347  for (syncer::SyncChangeList::const_iterator iter = change_list.begin();
348      iter != change_list.end(); ++iter) {
349    type = iter->sync_data().GetDataType();
350    DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
351    GURL favicon_url =
352        GetFaviconURLFromSpecifics(iter->sync_data().GetSpecifics());
353    if (!favicon_url.is_valid()) {
354      error.Reset(FROM_HERE, "Received invalid favicon url.", type);
355      break;
356    }
357    FaviconMap::iterator favicon_iter = synced_favicons_.find(favicon_url);
358    if (iter->change_type() == syncer::SyncChange::ACTION_DELETE) {
359      if (favicon_iter == synced_favicons_.end()) {
360        // Two clients might wind up deleting different parts of the same
361        // favicon, so ignore this.
362        continue;
363      } else {
364        DVLOG(1) << "Deleting favicon at " << favicon_url.spec();
365        // If we only have partial data for the favicon (which implies orphaned
366        // nodes), delete the local favicon only if the type corresponds to the
367        // partial data we have. If we do have orphaned nodes, we rely on the
368        // expiration logic to remove them eventually.
369        DropPartialFavicon(favicon_iter, type);
370      }
371    } else if (iter->change_type() == syncer::SyncChange::ACTION_UPDATE ||
372               iter->change_type() == syncer::SyncChange::ACTION_ADD) {
373      // Adds and updates are treated the same due to the lack of strong
374      // consistency (it's possible we'll receive an update for a tracking info
375      // before we've received the add for the image, and should handle both
376      // gracefully).
377      if (favicon_iter == synced_favicons_.end()) {
378        DVLOG(1) << "Adding favicon at " << favicon_url.spec();
379        AddLocalFaviconFromSyncedData(iter->sync_data());
380      } else {
381        DVLOG(1) << "Updating favicon at " << favicon_url.spec();
382        MergeSyncFavicon(iter->sync_data(), &new_changes);
383      }
384    } else {
385      error.Reset(FROM_HERE, "Invalid action received.", type);
386      break;
387    }
388  }
389
390  // Note: we deliberately do not expire favicons here. If we received new
391  // favicons and are now over the limit, the next local favicon change will
392  // trigger the necessary expiration.
393  if (!error.IsSet() && !new_changes.empty()) {
394    if (type == syncer::FAVICON_IMAGES) {
395        favicon_images_sync_processor_->ProcessSyncChanges(FROM_HERE,
396                                                           new_changes);
397    } else {
398        favicon_tracking_sync_processor_->ProcessSyncChanges(FROM_HERE,
399                                                             new_changes);
400    }
401  }
402
403  return error;
404}
405
406void FaviconCache::OnPageFaviconUpdated(const GURL& page_url) {
407  DCHECK(page_url.is_valid());
408
409  // If a favicon load is already happening for this url, let it finish.
410  if (page_task_map_.find(page_url) != page_task_map_.end())
411    return;
412
413  PageFaviconMap::const_iterator url_iter = page_favicon_map_.find(page_url);
414  if (url_iter != page_favicon_map_.end()) {
415    FaviconMap::const_iterator icon_iter =
416        synced_favicons_.find(url_iter->second);
417    // TODO(zea): consider what to do when only a subset of supported
418    // resolutions are available.
419    if (icon_iter != synced_favicons_.end() &&
420        icon_iter->second->bitmap_data[SIZE_16].bitmap_data.get()) {
421      DVLOG(2) << "Using cached favicon url for " << page_url.spec()
422               << ": " << icon_iter->second->favicon_url.spec();
423      UpdateFaviconVisitTime(icon_iter->second->favicon_url, base::Time::Now());
424      UpdateSyncState(icon_iter->second->favicon_url,
425                      syncer::SyncChange::ACTION_INVALID,
426                      syncer::SyncChange::ACTION_UPDATE);
427      return;
428    }
429  }
430
431  DVLOG(1) << "Triggering favicon load for url " << page_url.spec();
432
433  if (!profile_) {
434    page_task_map_[page_url] = 0;  // For testing only.
435    return;
436  }
437  FaviconService* favicon_service =
438      FaviconServiceFactory::GetForProfile(profile_, Profile::EXPLICIT_ACCESS);
439  if (!favicon_service)
440    return;
441  // TODO(zea): This appears to only fetch one favicon (best match based on
442  // desired_size_in_dip). Figure out a way to fetch all favicons we support.
443  // See crbug.com/181068.
444  base::CancelableTaskTracker::TaskId id =
445      favicon_service->GetFaviconForPageURL(
446          page_url,
447          SupportedFaviconTypes(),
448          kMaxFaviconResolution,
449          base::Bind(&FaviconCache::OnFaviconDataAvailable,
450                     weak_ptr_factory_.GetWeakPtr(),
451                     page_url),
452          &cancelable_task_tracker_);
453  page_task_map_[page_url] = id;
454}
455
456void FaviconCache::OnFaviconVisited(const GURL& page_url,
457                                    const GURL& favicon_url) {
458  DCHECK(page_url.is_valid());
459  if (!favicon_url.is_valid() ||
460      synced_favicons_.find(favicon_url) == synced_favicons_.end()) {
461    // TODO(zea): consider triggering a favicon load if we have some but not
462    // all desired resolutions?
463    OnPageFaviconUpdated(page_url);
464    return;
465  }
466
467  DVLOG(1) << "Associating " << page_url.spec() << " with favicon at "
468           << favicon_url.spec() << " and marking visited.";
469  page_favicon_map_[page_url] = favicon_url;
470  bool had_tracking = FaviconInfoHasTracking(
471      *synced_favicons_.find(favicon_url)->second);
472  UpdateFaviconVisitTime(favicon_url, base::Time::Now());
473
474  UpdateSyncState(favicon_url,
475                  syncer::SyncChange::ACTION_INVALID,
476                  (had_tracking ?
477                   syncer::SyncChange::ACTION_UPDATE :
478                   syncer::SyncChange::ACTION_ADD));
479}
480
481bool FaviconCache::GetSyncedFaviconForFaviconURL(
482    const GURL& favicon_url,
483    scoped_refptr<base::RefCountedMemory>* favicon_png) const {
484  if (!favicon_url.is_valid())
485    return false;
486  FaviconMap::const_iterator iter = synced_favicons_.find(favicon_url);
487
488  UMA_HISTOGRAM_BOOLEAN("Sync.FaviconCacheLookupSucceeded",
489                        iter != synced_favicons_.end());
490  if (iter == synced_favicons_.end())
491    return false;
492
493  // TODO(zea): support getting other resolutions.
494  if (!iter->second->bitmap_data[SIZE_16].bitmap_data.get())
495    return false;
496
497  *favicon_png = iter->second->bitmap_data[SIZE_16].bitmap_data;
498  return true;
499}
500
501bool FaviconCache::GetSyncedFaviconForPageURL(
502    const GURL& page_url,
503    scoped_refptr<base::RefCountedMemory>* favicon_png) const {
504  if (!page_url.is_valid())
505    return false;
506  PageFaviconMap::const_iterator iter = page_favicon_map_.find(page_url);
507
508  if (iter == page_favicon_map_.end())
509    return false;
510
511  return GetSyncedFaviconForFaviconURL(iter->second, favicon_png);
512}
513
514void FaviconCache::OnReceivedSyncFavicon(const GURL& page_url,
515                                         const GURL& icon_url,
516                                         const std::string& icon_bytes,
517                                         int64 visit_time_ms) {
518  if (!icon_url.is_valid() || !page_url.is_valid() || icon_url.SchemeIs("data"))
519    return;
520  DVLOG(1) << "Associating " << page_url.spec() << " with favicon at "
521           << icon_url.spec();
522  page_favicon_map_[page_url] = icon_url;
523
524  // If there is no actual image, it means there either is no synced
525  // favicon, or it's on its way (race condition).
526  // TODO(zea): potentially trigger a favicon web download here (delayed?).
527  if (icon_bytes.size() == 0)
528    return;
529
530  // Post a task to do the actual association because this method may have been
531  // called while in a transaction.
532  base::MessageLoop::current()->PostTask(
533      FROM_HERE,
534      base::Bind(&FaviconCache::OnReceivedSyncFaviconImpl,
535                 weak_ptr_factory_.GetWeakPtr(),
536                 icon_url,
537                 icon_bytes,
538                 visit_time_ms));
539}
540
541void FaviconCache::OnReceivedSyncFaviconImpl(
542    const GURL& icon_url,
543    const std::string& icon_bytes,
544    int64 visit_time_ms) {
545  // If this favicon is already synced, do nothing else.
546  if (synced_favicons_.find(icon_url) != synced_favicons_.end())
547    return;
548
549  // Don't add any more favicons once we hit our in memory limit.
550  // TODO(zea): UMA this.
551  if (kMaxFaviconsInMem != 0 && synced_favicons_.size() > kMaxFaviconsInMem)
552    return;
553
554  SyncedFaviconInfo* favicon_info = GetFaviconInfo(icon_url);
555  if (!favicon_info)
556    return;  // We reached the in-memory limit.
557  base::RefCountedString* temp_string = new base::RefCountedString();
558  temp_string->data() = icon_bytes;
559  favicon_info->bitmap_data[SIZE_16].bitmap_data = temp_string;
560  // We assume legacy favicons are 16x16.
561  favicon_info->bitmap_data[SIZE_16].pixel_size.set_width(16);
562  favicon_info->bitmap_data[SIZE_16].pixel_size.set_height(16);
563  bool added_tracking = !FaviconInfoHasTracking(*favicon_info);
564  UpdateFaviconVisitTime(icon_url,
565                         syncer::ProtoTimeToTime(visit_time_ms));
566
567  UpdateSyncState(icon_url,
568                  syncer::SyncChange::ACTION_ADD,
569                  (added_tracking ?
570                   syncer::SyncChange::ACTION_ADD :
571                   syncer::SyncChange::ACTION_UPDATE));
572}
573
574void FaviconCache::Observe(int type,
575                           const content::NotificationSource& source,
576                           const content::NotificationDetails& details) {
577  DCHECK_EQ(type, chrome::NOTIFICATION_HISTORY_URLS_DELETED);
578
579  content::Details<history::URLsDeletedDetails> deleted_details(details);
580
581  // We only care about actual user (or sync) deletions.
582  if (deleted_details->expired)
583    return;
584
585  if (!deleted_details->all_history) {
586    DeleteSyncedFavicons(deleted_details->favicon_urls);
587    return;
588  }
589
590  // All history was cleared: just delete all favicons.
591  DVLOG(1) << "History clear detected, deleting all synced favicons.";
592  syncer::SyncChangeList image_deletions, tracking_deletions;
593  while (!synced_favicons_.empty()) {
594    DeleteSyncedFavicon(synced_favicons_.begin(),
595                        &image_deletions,
596                        &tracking_deletions);
597  }
598
599  if (favicon_images_sync_processor_.get()) {
600    favicon_images_sync_processor_->ProcessSyncChanges(FROM_HERE,
601                                                       image_deletions);
602  }
603  if (favicon_tracking_sync_processor_.get()) {
604    favicon_tracking_sync_processor_->ProcessSyncChanges(FROM_HERE,
605                                                         tracking_deletions);
606  }
607}
608
609bool FaviconCache::FaviconRecencyFunctor::operator()(
610    const linked_ptr<SyncedFaviconInfo>& lhs,
611    const linked_ptr<SyncedFaviconInfo>& rhs) const {
612  // TODO(zea): incorporate bookmarked status here once we care about it.
613  if (lhs->last_visit_time < rhs->last_visit_time)
614    return true;
615  else if (lhs->last_visit_time == rhs->last_visit_time)
616    return lhs->favicon_url.spec() < rhs->favicon_url.spec();
617  return false;
618}
619
620void FaviconCache::OnFaviconDataAvailable(
621    const GURL& page_url,
622    const std::vector<favicon_base::FaviconRawBitmapResult>& bitmap_results) {
623  PageTaskMap::iterator page_iter = page_task_map_.find(page_url);
624  if (page_iter == page_task_map_.end())
625    return;
626  page_task_map_.erase(page_iter);
627
628  if (bitmap_results.size() == 0) {
629    // Either the favicon isn't loaded yet or there is no valid favicon.
630    // We already cleared the task id, so just return.
631    DVLOG(1) << "Favicon load failed for page " << page_url.spec();
632    return;
633  }
634
635  base::Time now = base::Time::Now();
636  std::map<GURL, LocalFaviconUpdateInfo> favicon_updates;
637  for (size_t i = 0; i < bitmap_results.size(); ++i) {
638    const favicon_base::FaviconRawBitmapResult& bitmap_result =
639        bitmap_results[i];
640    GURL favicon_url = bitmap_result.icon_url;
641    if (!favicon_url.is_valid() || favicon_url.SchemeIs("data"))
642      continue;  // Can happen if the page is still loading.
643
644    SyncedFaviconInfo* favicon_info = GetFaviconInfo(favicon_url);
645    if (!favicon_info)
646      return;  // We reached the in-memory limit.
647
648    favicon_updates[favicon_url].new_image |=
649        !FaviconInfoHasImages(*favicon_info);
650    favicon_updates[favicon_url].new_tracking |=
651        !FaviconInfoHasTracking(*favicon_info);
652    favicon_updates[favicon_url].image_needs_rewrite |=
653        UpdateFaviconFromBitmapResult(bitmap_result, favicon_info);
654    favicon_updates[favicon_url].favicon_info = favicon_info;
655  }
656
657  for (std::map<GURL, LocalFaviconUpdateInfo>::const_iterator
658           iter = favicon_updates.begin(); iter != favicon_updates.end();
659       ++iter) {
660    SyncedFaviconInfo* favicon_info = iter->second.favicon_info;
661    const GURL& favicon_url = favicon_info->favicon_url;
662
663    // TODO(zea): support multiple favicon urls per page.
664    page_favicon_map_[page_url] = favicon_url;
665
666    if (!favicon_info->last_visit_time.is_null()) {
667      UMA_HISTOGRAM_COUNTS_10000(
668          "Sync.FaviconVisitPeriod",
669          (now - favicon_info->last_visit_time).InHours());
670    }
671    favicon_info->received_local_update = true;
672    UpdateFaviconVisitTime(favicon_url, now);
673
674    syncer::SyncChange::SyncChangeType image_change =
675        syncer::SyncChange::ACTION_INVALID;
676    if (iter->second.new_image)
677      image_change = syncer::SyncChange::ACTION_ADD;
678    else if (iter->second.image_needs_rewrite)
679      image_change = syncer::SyncChange::ACTION_UPDATE;
680    syncer::SyncChange::SyncChangeType tracking_change =
681        syncer::SyncChange::ACTION_UPDATE;
682    if (iter->second.new_tracking)
683      tracking_change = syncer::SyncChange::ACTION_ADD;
684    UpdateSyncState(favicon_url, image_change, tracking_change);
685  }
686}
687
688void FaviconCache::UpdateSyncState(
689    const GURL& icon_url,
690    syncer::SyncChange::SyncChangeType image_change_type,
691    syncer::SyncChange::SyncChangeType tracking_change_type) {
692  DCHECK(icon_url.is_valid());
693  // It's possible that we'll receive a favicon update before both types
694  // have finished setting up. In that case ignore the update.
695  // TODO(zea): consider tracking these skipped updates somehow?
696  if (!favicon_images_sync_processor_.get() ||
697      !favicon_tracking_sync_processor_.get()) {
698    return;
699  }
700
701  FaviconMap::const_iterator iter = synced_favicons_.find(icon_url);
702  DCHECK(iter != synced_favicons_.end());
703  const SyncedFaviconInfo* favicon_info = iter->second.get();
704
705  syncer::SyncChangeList image_changes;
706  syncer::SyncChangeList tracking_changes;
707  if (image_change_type != syncer::SyncChange::ACTION_INVALID) {
708    sync_pb::EntitySpecifics new_specifics;
709    sync_pb::FaviconImageSpecifics* image_specifics =
710        new_specifics.mutable_favicon_image();
711    BuildImageSpecifics(favicon_info, image_specifics);
712
713    image_changes.push_back(
714        syncer::SyncChange(FROM_HERE,
715                           image_change_type,
716                           syncer::SyncData::CreateLocalData(
717                               icon_url.spec(),
718                               icon_url.spec(),
719                               new_specifics)));
720  }
721  if (tracking_change_type != syncer::SyncChange::ACTION_INVALID) {
722    sync_pb::EntitySpecifics new_specifics;
723    sync_pb::FaviconTrackingSpecifics* tracking_specifics =
724        new_specifics.mutable_favicon_tracking();
725    BuildTrackingSpecifics(favicon_info, tracking_specifics);
726
727    tracking_changes.push_back(
728        syncer::SyncChange(FROM_HERE,
729                           tracking_change_type,
730                           syncer::SyncData::CreateLocalData(
731                               icon_url.spec(),
732                               icon_url.spec(),
733                               new_specifics)));
734  }
735  ExpireFaviconsIfNecessary(&image_changes, &tracking_changes);
736  if (!image_changes.empty()) {
737    favicon_images_sync_processor_->ProcessSyncChanges(FROM_HERE,
738                                                       image_changes);
739  }
740  if (!tracking_changes.empty()) {
741    favicon_tracking_sync_processor_->ProcessSyncChanges(FROM_HERE,
742                                                         tracking_changes);
743  }
744}
745
746SyncedFaviconInfo* FaviconCache::GetFaviconInfo(
747    const GURL& icon_url) {
748  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
749  if (synced_favicons_.count(icon_url) != 0)
750    return synced_favicons_[icon_url].get();
751
752  // TODO(zea): implement in-memory eviction.
753  DVLOG(1) << "Adding favicon info for " << icon_url.spec();
754  SyncedFaviconInfo* favicon_info = new SyncedFaviconInfo(icon_url);
755  synced_favicons_[icon_url] = make_linked_ptr(favicon_info);
756  recent_favicons_.insert(synced_favicons_[icon_url]);
757  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
758  return favicon_info;
759}
760
761void FaviconCache::UpdateFaviconVisitTime(const GURL& icon_url,
762                                          base::Time time) {
763  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
764  FaviconMap::const_iterator iter = synced_favicons_.find(icon_url);
765  DCHECK(iter != synced_favicons_.end());
766  if (iter->second->last_visit_time >= time)
767    return;
768  // Erase, update the time, then re-insert to maintain ordering.
769  recent_favicons_.erase(iter->second);
770  DVLOG(1) << "Updating " << icon_url.spec() << " visit time to "
771           << syncer::GetTimeDebugString(time);
772  iter->second->last_visit_time = time;
773  recent_favicons_.insert(iter->second);
774
775  if (VLOG_IS_ON(2)) {
776    for (RecencySet::const_iterator iter = recent_favicons_.begin();
777         iter != recent_favicons_.end(); ++iter) {
778      DVLOG(2) << "Favicon " << iter->get()->favicon_url.spec() << ": "
779               << syncer::GetTimeDebugString(iter->get()->last_visit_time);
780    }
781  }
782  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
783}
784
785void FaviconCache::ExpireFaviconsIfNecessary(
786    syncer::SyncChangeList* image_changes,
787    syncer::SyncChangeList* tracking_changes) {
788  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
789  // TODO(zea): once we have in-memory eviction, we'll need to track sync
790  // favicon count separately from the synced_favicons_/recent_favicons_.
791
792  // Iterate until we've removed the necessary amount. |recent_favicons_| is
793  // already in recency order, so just start from the beginning.
794  // TODO(zea): to reduce thrashing, consider removing more than the minimum.
795  while (recent_favicons_.size() > max_sync_favicon_limit_) {
796    linked_ptr<SyncedFaviconInfo> candidate = *recent_favicons_.begin();
797    DVLOG(1) << "Expiring favicon " << candidate->favicon_url.spec();
798    DeleteSyncedFavicon(synced_favicons_.find(candidate->favicon_url),
799                        image_changes,
800                        tracking_changes);
801  }
802  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
803}
804
805GURL FaviconCache::GetLocalFaviconFromSyncedData(
806    const syncer::SyncData& sync_favicon) const {
807  syncer::ModelType type = sync_favicon.GetDataType();
808  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
809  GURL favicon_url = GetFaviconURLFromSpecifics(sync_favicon.GetSpecifics());
810  return (synced_favicons_.count(favicon_url) > 0 ? favicon_url : GURL());
811}
812
813void FaviconCache::MergeSyncFavicon(const syncer::SyncData& sync_favicon,
814                                    syncer::SyncChangeList* sync_changes) {
815  syncer::ModelType type = sync_favicon.GetDataType();
816  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
817  sync_pb::EntitySpecifics new_specifics;
818  GURL favicon_url = GetFaviconURLFromSpecifics(sync_favicon.GetSpecifics());
819  FaviconMap::const_iterator iter = synced_favicons_.find(favicon_url);
820  DCHECK(iter != synced_favicons_.end());
821  SyncedFaviconInfo* favicon_info = iter->second.get();
822  if (type == syncer::FAVICON_IMAGES) {
823    sync_pb::FaviconImageSpecifics image_specifics =
824        sync_favicon.GetSpecifics().favicon_image();
825
826    // Remote image data always clobbers local image data.
827    bool needs_update = false;
828    if (image_specifics.has_favicon_web()) {
829      favicon_info->bitmap_data[SIZE_16] = GetImageDataFromSpecifics(
830          image_specifics.favicon_web());
831    } else if (favicon_info->bitmap_data[SIZE_16].bitmap_data.get()) {
832      needs_update = true;
833    }
834    if (image_specifics.has_favicon_web_32()) {
835      favicon_info->bitmap_data[SIZE_32] = GetImageDataFromSpecifics(
836          image_specifics.favicon_web_32());
837    } else if (favicon_info->bitmap_data[SIZE_32].bitmap_data.get()) {
838      needs_update = true;
839    }
840    if (image_specifics.has_favicon_touch_64()) {
841      favicon_info->bitmap_data[SIZE_64] = GetImageDataFromSpecifics(
842          image_specifics.favicon_touch_64());
843    } else if (favicon_info->bitmap_data[SIZE_64].bitmap_data.get()) {
844      needs_update = true;
845    }
846
847    if (needs_update)
848      BuildImageSpecifics(favicon_info, new_specifics.mutable_favicon_image());
849  } else {
850    sync_pb::FaviconTrackingSpecifics tracking_specifics =
851        sync_favicon.GetSpecifics().favicon_tracking();
852
853    // Tracking data is merged, such that bookmark data is the logical OR
854    // of the two, and last visit time is the most recent.
855
856    base::Time last_visit =  syncer::ProtoTimeToTime(
857        tracking_specifics.last_visit_time_ms());
858    // Due to crbug.com/258196, there are tracking nodes out there with
859    // null visit times. If this is one of those, artificially make it a valid
860    // visit time, so we know the node exists and update it properly on the next
861    // real visit.
862    if (last_visit.is_null())
863      last_visit = last_visit + base::TimeDelta::FromMilliseconds(1);
864    UpdateFaviconVisitTime(favicon_url, last_visit);
865    favicon_info->is_bookmarked = (favicon_info->is_bookmarked ||
866                                   tracking_specifics.is_bookmarked());
867
868    if (syncer::TimeToProtoTime(favicon_info->last_visit_time) !=
869            tracking_specifics.last_visit_time_ms() ||
870        favicon_info->is_bookmarked != tracking_specifics.is_bookmarked()) {
871      BuildTrackingSpecifics(favicon_info,
872                             new_specifics.mutable_favicon_tracking());
873    }
874    DCHECK(!favicon_info->last_visit_time.is_null());
875  }
876
877  if (new_specifics.has_favicon_image() ||
878      new_specifics.has_favicon_tracking()) {
879    sync_changes->push_back(syncer::SyncChange(
880        FROM_HERE,
881        syncer::SyncChange::ACTION_UPDATE,
882        syncer::SyncData::CreateLocalData(favicon_url.spec(),
883                                          favicon_url.spec(),
884                                          new_specifics)));
885  }
886}
887
888void FaviconCache::AddLocalFaviconFromSyncedData(
889    const syncer::SyncData& sync_favicon) {
890  syncer::ModelType type = sync_favicon.GetDataType();
891  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
892  if (type == syncer::FAVICON_IMAGES) {
893    sync_pb::FaviconImageSpecifics image_specifics =
894        sync_favicon.GetSpecifics().favicon_image();
895    GURL favicon_url = GURL(image_specifics.favicon_url());
896    DCHECK(favicon_url.is_valid());
897    DCHECK(!synced_favicons_.count(favicon_url));
898
899    SyncedFaviconInfo* favicon_info = GetFaviconInfo(favicon_url);
900    if (!favicon_info)
901      return;  // We reached the in-memory limit.
902    if (image_specifics.has_favicon_web()) {
903      favicon_info->bitmap_data[SIZE_16] = GetImageDataFromSpecifics(
904          image_specifics.favicon_web());
905    }
906    if (image_specifics.has_favicon_web_32()) {
907      favicon_info->bitmap_data[SIZE_32] = GetImageDataFromSpecifics(
908          image_specifics.favicon_web_32());
909    }
910    if (image_specifics.has_favicon_touch_64()) {
911      favicon_info->bitmap_data[SIZE_64] = GetImageDataFromSpecifics(
912          image_specifics.favicon_touch_64());
913    }
914  } else {
915    sync_pb::FaviconTrackingSpecifics tracking_specifics =
916        sync_favicon.GetSpecifics().favicon_tracking();
917    GURL favicon_url = GURL(tracking_specifics.favicon_url());
918    DCHECK(favicon_url.is_valid());
919    DCHECK(!synced_favicons_.count(favicon_url));
920
921    SyncedFaviconInfo* favicon_info = GetFaviconInfo(favicon_url);
922    if (!favicon_info)
923      return;  // We reached the in-memory limit.
924    base::Time last_visit =  syncer::ProtoTimeToTime(
925        tracking_specifics.last_visit_time_ms());
926    // Due to crbug.com/258196, there are tracking nodes out there with
927    // null visit times. If this is one of those, artificially make it a valid
928    // visit time, so we know the node exists and update it properly on the next
929    // real visit.
930    if (last_visit.is_null())
931      last_visit = last_visit + base::TimeDelta::FromMilliseconds(1);
932    UpdateFaviconVisitTime(favicon_url, last_visit);
933    favicon_info->is_bookmarked = tracking_specifics.is_bookmarked();
934    DCHECK(!favicon_info->last_visit_time.is_null());
935  }
936}
937
938syncer::SyncData FaviconCache::CreateSyncDataFromLocalFavicon(
939    syncer::ModelType type,
940    const GURL& favicon_url) const {
941  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
942  DCHECK(favicon_url.is_valid());
943  FaviconMap::const_iterator iter = synced_favicons_.find(favicon_url);
944  DCHECK(iter != synced_favicons_.end());
945  SyncedFaviconInfo* favicon_info = iter->second.get();
946
947  syncer::SyncData data;
948  sync_pb::EntitySpecifics specifics;
949  if (type == syncer::FAVICON_IMAGES) {
950    sync_pb::FaviconImageSpecifics* image_specifics =
951        specifics.mutable_favicon_image();
952    BuildImageSpecifics(favicon_info, image_specifics);
953  } else {
954    sync_pb::FaviconTrackingSpecifics* tracking_specifics =
955        specifics.mutable_favicon_tracking();
956    BuildTrackingSpecifics(favicon_info, tracking_specifics);
957  }
958  data = syncer::SyncData::CreateLocalData(favicon_url.spec(),
959                                           favicon_url.spec(),
960                                           specifics);
961  return data;
962}
963
964void FaviconCache::DeleteSyncedFavicons(const std::set<GURL>& favicon_urls) {
965  syncer::SyncChangeList image_deletions, tracking_deletions;
966  for (std::set<GURL>::const_iterator iter = favicon_urls.begin();
967       iter != favicon_urls.end(); ++iter) {
968    FaviconMap::iterator favicon_iter = synced_favicons_.find(*iter);
969    if (favicon_iter == synced_favicons_.end())
970      continue;
971    DeleteSyncedFavicon(favicon_iter,
972                        &image_deletions,
973                        &tracking_deletions);
974  }
975  DVLOG(1) << "Deleting " << image_deletions.size() << " synced favicons.";
976  if (favicon_images_sync_processor_.get()) {
977    favicon_images_sync_processor_->ProcessSyncChanges(FROM_HERE,
978                                                       image_deletions);
979  }
980  if (favicon_tracking_sync_processor_.get()) {
981    favicon_tracking_sync_processor_->ProcessSyncChanges(FROM_HERE,
982                                                         tracking_deletions);
983  }
984}
985
986void FaviconCache::DeleteSyncedFavicon(
987    FaviconMap::iterator favicon_iter,
988    syncer::SyncChangeList* image_changes,
989    syncer::SyncChangeList* tracking_changes) {
990  linked_ptr<SyncedFaviconInfo> favicon_info = favicon_iter->second;
991  if (FaviconInfoHasImages(*(favicon_iter->second))) {
992    DVLOG(1) << "Deleting image for "
993             << favicon_iter->second.get()->favicon_url;
994    image_changes->push_back(
995        syncer::SyncChange(FROM_HERE,
996                           syncer::SyncChange::ACTION_DELETE,
997                           syncer::SyncData::CreateLocalDelete(
998                               favicon_info->favicon_url.spec(),
999                               syncer::FAVICON_IMAGES)));
1000  }
1001  if (FaviconInfoHasTracking(*(favicon_iter->second))) {
1002    DVLOG(1) << "Deleting tracking for "
1003             << favicon_iter->second.get()->favicon_url;
1004    tracking_changes->push_back(
1005        syncer::SyncChange(FROM_HERE,
1006                           syncer::SyncChange::ACTION_DELETE,
1007                           syncer::SyncData::CreateLocalDelete(
1008                               favicon_info->favicon_url.spec(),
1009                               syncer::FAVICON_TRACKING)));
1010  }
1011  DropSyncedFavicon(favicon_iter);
1012}
1013
1014void FaviconCache::DropSyncedFavicon(FaviconMap::iterator favicon_iter) {
1015  DVLOG(1) << "Dropping favicon " << favicon_iter->second.get()->favicon_url;
1016  recent_favicons_.erase(favicon_iter->second);
1017  synced_favicons_.erase(favicon_iter);
1018}
1019
1020void FaviconCache::DropPartialFavicon(FaviconMap::iterator favicon_iter,
1021                                      syncer::ModelType type) {
1022  // If the type being dropped has no valid data, do nothing.
1023  if ((type == syncer::FAVICON_TRACKING &&
1024       !FaviconInfoHasTracking(*favicon_iter->second)) ||
1025      (type == syncer::FAVICON_IMAGES &&
1026       !FaviconInfoHasImages(*favicon_iter->second))) {
1027    return;
1028  }
1029
1030  // If the type being dropped is the only type with valid data, just delete
1031  // the favicon altogether.
1032  if ((type == syncer::FAVICON_TRACKING &&
1033       !FaviconInfoHasImages(*favicon_iter->second)) ||
1034      (type == syncer::FAVICON_IMAGES &&
1035       !FaviconInfoHasTracking(*favicon_iter->second))) {
1036    DropSyncedFavicon(favicon_iter);
1037    return;
1038  }
1039
1040  if (type == syncer::FAVICON_IMAGES) {
1041    DVLOG(1) << "Dropping favicon image "
1042             << favicon_iter->second.get()->favicon_url;
1043    for (int i = 0; i < NUM_SIZES; ++i) {
1044      favicon_iter->second->bitmap_data[i] =
1045          favicon_base::FaviconRawBitmapResult();
1046    }
1047    DCHECK(!FaviconInfoHasImages(*favicon_iter->second));
1048  } else {
1049    DCHECK_EQ(type, syncer::FAVICON_TRACKING);
1050    DVLOG(1) << "Dropping favicon tracking "
1051             << favicon_iter->second.get()->favicon_url;
1052    recent_favicons_.erase(favicon_iter->second);
1053    favicon_iter->second->last_visit_time = base::Time();
1054    favicon_iter->second->is_bookmarked = false;
1055    recent_favicons_.insert(favicon_iter->second);
1056    DCHECK(!FaviconInfoHasTracking(*favicon_iter->second));
1057  }
1058}
1059
1060size_t FaviconCache::NumFaviconsForTest() const {
1061  return synced_favicons_.size();
1062}
1063
1064size_t FaviconCache::NumTasksForTest() const {
1065  return page_task_map_.size();
1066}
1067
1068}  // namespace browser_sync
1069