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          FaviconService::FaviconForPageURLParams(
447              page_url, SupportedFaviconTypes(), kMaxFaviconResolution),
448          base::Bind(&FaviconCache::OnFaviconDataAvailable,
449                     weak_ptr_factory_.GetWeakPtr(),
450                     page_url),
451          &cancelable_task_tracker_);
452  page_task_map_[page_url] = id;
453}
454
455void FaviconCache::OnFaviconVisited(const GURL& page_url,
456                                    const GURL& favicon_url) {
457  DCHECK(page_url.is_valid());
458  if (!favicon_url.is_valid() ||
459      synced_favicons_.find(favicon_url) == synced_favicons_.end()) {
460    // TODO(zea): consider triggering a favicon load if we have some but not
461    // all desired resolutions?
462    OnPageFaviconUpdated(page_url);
463    return;
464  }
465
466  DVLOG(1) << "Associating " << page_url.spec() << " with favicon at "
467           << favicon_url.spec() << " and marking visited.";
468  page_favicon_map_[page_url] = favicon_url;
469  bool had_tracking = FaviconInfoHasTracking(
470      *synced_favicons_.find(favicon_url)->second);
471  UpdateFaviconVisitTime(favicon_url, base::Time::Now());
472
473  UpdateSyncState(favicon_url,
474                  syncer::SyncChange::ACTION_INVALID,
475                  (had_tracking ?
476                   syncer::SyncChange::ACTION_UPDATE :
477                   syncer::SyncChange::ACTION_ADD));
478}
479
480bool FaviconCache::GetSyncedFaviconForFaviconURL(
481    const GURL& favicon_url,
482    scoped_refptr<base::RefCountedMemory>* favicon_png) const {
483  if (!favicon_url.is_valid())
484    return false;
485  FaviconMap::const_iterator iter = synced_favicons_.find(favicon_url);
486
487  UMA_HISTOGRAM_BOOLEAN("Sync.FaviconCacheLookupSucceeded",
488                        iter != synced_favicons_.end());
489  if (iter == synced_favicons_.end())
490    return false;
491
492  // TODO(zea): support getting other resolutions.
493  if (!iter->second->bitmap_data[SIZE_16].bitmap_data.get())
494    return false;
495
496  *favicon_png = iter->second->bitmap_data[SIZE_16].bitmap_data;
497  return true;
498}
499
500bool FaviconCache::GetSyncedFaviconForPageURL(
501    const GURL& page_url,
502    scoped_refptr<base::RefCountedMemory>* favicon_png) const {
503  if (!page_url.is_valid())
504    return false;
505  PageFaviconMap::const_iterator iter = page_favicon_map_.find(page_url);
506
507  if (iter == page_favicon_map_.end())
508    return false;
509
510  return GetSyncedFaviconForFaviconURL(iter->second, favicon_png);
511}
512
513void FaviconCache::OnReceivedSyncFavicon(const GURL& page_url,
514                                         const GURL& icon_url,
515                                         const std::string& icon_bytes,
516                                         int64 visit_time_ms) {
517  if (!icon_url.is_valid() || !page_url.is_valid() || icon_url.SchemeIs("data"))
518    return;
519  DVLOG(1) << "Associating " << page_url.spec() << " with favicon at "
520           << icon_url.spec();
521  page_favicon_map_[page_url] = icon_url;
522
523  // If there is no actual image, it means there either is no synced
524  // favicon, or it's on its way (race condition).
525  // TODO(zea): potentially trigger a favicon web download here (delayed?).
526  if (icon_bytes.size() == 0)
527    return;
528
529  // Post a task to do the actual association because this method may have been
530  // called while in a transaction.
531  base::MessageLoop::current()->PostTask(
532      FROM_HERE,
533      base::Bind(&FaviconCache::OnReceivedSyncFaviconImpl,
534                 weak_ptr_factory_.GetWeakPtr(),
535                 icon_url,
536                 icon_bytes,
537                 visit_time_ms));
538}
539
540void FaviconCache::OnReceivedSyncFaviconImpl(
541    const GURL& icon_url,
542    const std::string& icon_bytes,
543    int64 visit_time_ms) {
544  // If this favicon is already synced, do nothing else.
545  if (synced_favicons_.find(icon_url) != synced_favicons_.end())
546    return;
547
548  // Don't add any more favicons once we hit our in memory limit.
549  // TODO(zea): UMA this.
550  if (kMaxFaviconsInMem != 0 && synced_favicons_.size() > kMaxFaviconsInMem)
551    return;
552
553  SyncedFaviconInfo* favicon_info = GetFaviconInfo(icon_url);
554  if (!favicon_info)
555    return;  // We reached the in-memory limit.
556  base::RefCountedString* temp_string = new base::RefCountedString();
557  temp_string->data() = icon_bytes;
558  favicon_info->bitmap_data[SIZE_16].bitmap_data = temp_string;
559  // We assume legacy favicons are 16x16.
560  favicon_info->bitmap_data[SIZE_16].pixel_size.set_width(16);
561  favicon_info->bitmap_data[SIZE_16].pixel_size.set_height(16);
562  bool added_tracking = !FaviconInfoHasTracking(*favicon_info);
563  UpdateFaviconVisitTime(icon_url,
564                         syncer::ProtoTimeToTime(visit_time_ms));
565
566  UpdateSyncState(icon_url,
567                  syncer::SyncChange::ACTION_ADD,
568                  (added_tracking ?
569                   syncer::SyncChange::ACTION_ADD :
570                   syncer::SyncChange::ACTION_UPDATE));
571}
572
573void FaviconCache::Observe(int type,
574                           const content::NotificationSource& source,
575                           const content::NotificationDetails& details) {
576  DCHECK_EQ(type, chrome::NOTIFICATION_HISTORY_URLS_DELETED);
577
578  content::Details<history::URLsDeletedDetails> deleted_details(details);
579
580  // We only care about actual user (or sync) deletions.
581  if (deleted_details->expired)
582    return;
583
584  if (!deleted_details->all_history) {
585    DeleteSyncedFavicons(deleted_details->favicon_urls);
586    return;
587  }
588
589  // All history was cleared: just delete all favicons.
590  DVLOG(1) << "History clear detected, deleting all synced favicons.";
591  syncer::SyncChangeList image_deletions, tracking_deletions;
592  while (!synced_favicons_.empty()) {
593    DeleteSyncedFavicon(synced_favicons_.begin(),
594                        &image_deletions,
595                        &tracking_deletions);
596  }
597
598  if (favicon_images_sync_processor_.get()) {
599    favicon_images_sync_processor_->ProcessSyncChanges(FROM_HERE,
600                                                       image_deletions);
601  }
602  if (favicon_tracking_sync_processor_.get()) {
603    favicon_tracking_sync_processor_->ProcessSyncChanges(FROM_HERE,
604                                                         tracking_deletions);
605  }
606}
607
608bool FaviconCache::FaviconRecencyFunctor::operator()(
609    const linked_ptr<SyncedFaviconInfo>& lhs,
610    const linked_ptr<SyncedFaviconInfo>& rhs) const {
611  // TODO(zea): incorporate bookmarked status here once we care about it.
612  if (lhs->last_visit_time < rhs->last_visit_time)
613    return true;
614  else if (lhs->last_visit_time == rhs->last_visit_time)
615    return lhs->favicon_url.spec() < rhs->favicon_url.spec();
616  return false;
617}
618
619void FaviconCache::OnFaviconDataAvailable(
620    const GURL& page_url,
621    const std::vector<favicon_base::FaviconRawBitmapResult>& bitmap_results) {
622  PageTaskMap::iterator page_iter = page_task_map_.find(page_url);
623  if (page_iter == page_task_map_.end())
624    return;
625  page_task_map_.erase(page_iter);
626
627  if (bitmap_results.size() == 0) {
628    // Either the favicon isn't loaded yet or there is no valid favicon.
629    // We already cleared the task id, so just return.
630    DVLOG(1) << "Favicon load failed for page " << page_url.spec();
631    return;
632  }
633
634  base::Time now = base::Time::Now();
635  std::map<GURL, LocalFaviconUpdateInfo> favicon_updates;
636  for (size_t i = 0; i < bitmap_results.size(); ++i) {
637    const favicon_base::FaviconRawBitmapResult& bitmap_result =
638        bitmap_results[i];
639    GURL favicon_url = bitmap_result.icon_url;
640    if (!favicon_url.is_valid() || favicon_url.SchemeIs("data"))
641      continue;  // Can happen if the page is still loading.
642
643    SyncedFaviconInfo* favicon_info = GetFaviconInfo(favicon_url);
644    if (!favicon_info)
645      return;  // We reached the in-memory limit.
646
647    favicon_updates[favicon_url].new_image |=
648        !FaviconInfoHasImages(*favicon_info);
649    favicon_updates[favicon_url].new_tracking |=
650        !FaviconInfoHasTracking(*favicon_info);
651    favicon_updates[favicon_url].image_needs_rewrite |=
652        UpdateFaviconFromBitmapResult(bitmap_result, favicon_info);
653    favicon_updates[favicon_url].favicon_info = favicon_info;
654  }
655
656  for (std::map<GURL, LocalFaviconUpdateInfo>::const_iterator
657           iter = favicon_updates.begin(); iter != favicon_updates.end();
658       ++iter) {
659    SyncedFaviconInfo* favicon_info = iter->second.favicon_info;
660    const GURL& favicon_url = favicon_info->favicon_url;
661
662    // TODO(zea): support multiple favicon urls per page.
663    page_favicon_map_[page_url] = favicon_url;
664
665    if (!favicon_info->last_visit_time.is_null()) {
666      UMA_HISTOGRAM_COUNTS_10000(
667          "Sync.FaviconVisitPeriod",
668          (now - favicon_info->last_visit_time).InHours());
669    }
670    favicon_info->received_local_update = true;
671    UpdateFaviconVisitTime(favicon_url, now);
672
673    syncer::SyncChange::SyncChangeType image_change =
674        syncer::SyncChange::ACTION_INVALID;
675    if (iter->second.new_image)
676      image_change = syncer::SyncChange::ACTION_ADD;
677    else if (iter->second.image_needs_rewrite)
678      image_change = syncer::SyncChange::ACTION_UPDATE;
679    syncer::SyncChange::SyncChangeType tracking_change =
680        syncer::SyncChange::ACTION_UPDATE;
681    if (iter->second.new_tracking)
682      tracking_change = syncer::SyncChange::ACTION_ADD;
683    UpdateSyncState(favicon_url, image_change, tracking_change);
684  }
685}
686
687void FaviconCache::UpdateSyncState(
688    const GURL& icon_url,
689    syncer::SyncChange::SyncChangeType image_change_type,
690    syncer::SyncChange::SyncChangeType tracking_change_type) {
691  DCHECK(icon_url.is_valid());
692  // It's possible that we'll receive a favicon update before both types
693  // have finished setting up. In that case ignore the update.
694  // TODO(zea): consider tracking these skipped updates somehow?
695  if (!favicon_images_sync_processor_.get() ||
696      !favicon_tracking_sync_processor_.get()) {
697    return;
698  }
699
700  FaviconMap::const_iterator iter = synced_favicons_.find(icon_url);
701  DCHECK(iter != synced_favicons_.end());
702  const SyncedFaviconInfo* favicon_info = iter->second.get();
703
704  syncer::SyncChangeList image_changes;
705  syncer::SyncChangeList tracking_changes;
706  if (image_change_type != syncer::SyncChange::ACTION_INVALID) {
707    sync_pb::EntitySpecifics new_specifics;
708    sync_pb::FaviconImageSpecifics* image_specifics =
709        new_specifics.mutable_favicon_image();
710    BuildImageSpecifics(favicon_info, image_specifics);
711
712    image_changes.push_back(
713        syncer::SyncChange(FROM_HERE,
714                           image_change_type,
715                           syncer::SyncData::CreateLocalData(
716                               icon_url.spec(),
717                               icon_url.spec(),
718                               new_specifics)));
719  }
720  if (tracking_change_type != syncer::SyncChange::ACTION_INVALID) {
721    sync_pb::EntitySpecifics new_specifics;
722    sync_pb::FaviconTrackingSpecifics* tracking_specifics =
723        new_specifics.mutable_favicon_tracking();
724    BuildTrackingSpecifics(favicon_info, tracking_specifics);
725
726    tracking_changes.push_back(
727        syncer::SyncChange(FROM_HERE,
728                           tracking_change_type,
729                           syncer::SyncData::CreateLocalData(
730                               icon_url.spec(),
731                               icon_url.spec(),
732                               new_specifics)));
733  }
734  ExpireFaviconsIfNecessary(&image_changes, &tracking_changes);
735  if (!image_changes.empty()) {
736    favicon_images_sync_processor_->ProcessSyncChanges(FROM_HERE,
737                                                       image_changes);
738  }
739  if (!tracking_changes.empty()) {
740    favicon_tracking_sync_processor_->ProcessSyncChanges(FROM_HERE,
741                                                         tracking_changes);
742  }
743}
744
745SyncedFaviconInfo* FaviconCache::GetFaviconInfo(
746    const GURL& icon_url) {
747  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
748  if (synced_favicons_.count(icon_url) != 0)
749    return synced_favicons_[icon_url].get();
750
751  // TODO(zea): implement in-memory eviction.
752  DVLOG(1) << "Adding favicon info for " << icon_url.spec();
753  SyncedFaviconInfo* favicon_info = new SyncedFaviconInfo(icon_url);
754  synced_favicons_[icon_url] = make_linked_ptr(favicon_info);
755  recent_favicons_.insert(synced_favicons_[icon_url]);
756  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
757  return favicon_info;
758}
759
760void FaviconCache::UpdateFaviconVisitTime(const GURL& icon_url,
761                                          base::Time time) {
762  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
763  FaviconMap::const_iterator iter = synced_favicons_.find(icon_url);
764  DCHECK(iter != synced_favicons_.end());
765  if (iter->second->last_visit_time >= time)
766    return;
767  // Erase, update the time, then re-insert to maintain ordering.
768  recent_favicons_.erase(iter->second);
769  DVLOG(1) << "Updating " << icon_url.spec() << " visit time to "
770           << syncer::GetTimeDebugString(time);
771  iter->second->last_visit_time = time;
772  recent_favicons_.insert(iter->second);
773
774  if (VLOG_IS_ON(2)) {
775    for (RecencySet::const_iterator iter = recent_favicons_.begin();
776         iter != recent_favicons_.end(); ++iter) {
777      DVLOG(2) << "Favicon " << iter->get()->favicon_url.spec() << ": "
778               << syncer::GetTimeDebugString(iter->get()->last_visit_time);
779    }
780  }
781  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
782}
783
784void FaviconCache::ExpireFaviconsIfNecessary(
785    syncer::SyncChangeList* image_changes,
786    syncer::SyncChangeList* tracking_changes) {
787  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
788  // TODO(zea): once we have in-memory eviction, we'll need to track sync
789  // favicon count separately from the synced_favicons_/recent_favicons_.
790
791  // Iterate until we've removed the necessary amount. |recent_favicons_| is
792  // already in recency order, so just start from the beginning.
793  // TODO(zea): to reduce thrashing, consider removing more than the minimum.
794  while (recent_favicons_.size() > max_sync_favicon_limit_) {
795    linked_ptr<SyncedFaviconInfo> candidate = *recent_favicons_.begin();
796    DVLOG(1) << "Expiring favicon " << candidate->favicon_url.spec();
797    DeleteSyncedFavicon(synced_favicons_.find(candidate->favicon_url),
798                        image_changes,
799                        tracking_changes);
800  }
801  DCHECK_EQ(recent_favicons_.size(), synced_favicons_.size());
802}
803
804GURL FaviconCache::GetLocalFaviconFromSyncedData(
805    const syncer::SyncData& sync_favicon) const {
806  syncer::ModelType type = sync_favicon.GetDataType();
807  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
808  GURL favicon_url = GetFaviconURLFromSpecifics(sync_favicon.GetSpecifics());
809  return (synced_favicons_.count(favicon_url) > 0 ? favicon_url : GURL());
810}
811
812void FaviconCache::MergeSyncFavicon(const syncer::SyncData& sync_favicon,
813                                    syncer::SyncChangeList* sync_changes) {
814  syncer::ModelType type = sync_favicon.GetDataType();
815  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
816  sync_pb::EntitySpecifics new_specifics;
817  GURL favicon_url = GetFaviconURLFromSpecifics(sync_favicon.GetSpecifics());
818  FaviconMap::const_iterator iter = synced_favicons_.find(favicon_url);
819  DCHECK(iter != synced_favicons_.end());
820  SyncedFaviconInfo* favicon_info = iter->second.get();
821  if (type == syncer::FAVICON_IMAGES) {
822    sync_pb::FaviconImageSpecifics image_specifics =
823        sync_favicon.GetSpecifics().favicon_image();
824
825    // Remote image data always clobbers local image data.
826    bool needs_update = false;
827    if (image_specifics.has_favicon_web()) {
828      favicon_info->bitmap_data[SIZE_16] = GetImageDataFromSpecifics(
829          image_specifics.favicon_web());
830    } else if (favicon_info->bitmap_data[SIZE_16].bitmap_data.get()) {
831      needs_update = true;
832    }
833    if (image_specifics.has_favicon_web_32()) {
834      favicon_info->bitmap_data[SIZE_32] = GetImageDataFromSpecifics(
835          image_specifics.favicon_web_32());
836    } else if (favicon_info->bitmap_data[SIZE_32].bitmap_data.get()) {
837      needs_update = true;
838    }
839    if (image_specifics.has_favicon_touch_64()) {
840      favicon_info->bitmap_data[SIZE_64] = GetImageDataFromSpecifics(
841          image_specifics.favicon_touch_64());
842    } else if (favicon_info->bitmap_data[SIZE_64].bitmap_data.get()) {
843      needs_update = true;
844    }
845
846    if (needs_update)
847      BuildImageSpecifics(favicon_info, new_specifics.mutable_favicon_image());
848  } else {
849    sync_pb::FaviconTrackingSpecifics tracking_specifics =
850        sync_favicon.GetSpecifics().favicon_tracking();
851
852    // Tracking data is merged, such that bookmark data is the logical OR
853    // of the two, and last visit time is the most recent.
854
855    base::Time last_visit =  syncer::ProtoTimeToTime(
856        tracking_specifics.last_visit_time_ms());
857    // Due to crbug.com/258196, there are tracking nodes out there with
858    // null visit times. If this is one of those, artificially make it a valid
859    // visit time, so we know the node exists and update it properly on the next
860    // real visit.
861    if (last_visit.is_null())
862      last_visit = last_visit + base::TimeDelta::FromMilliseconds(1);
863    UpdateFaviconVisitTime(favicon_url, last_visit);
864    favicon_info->is_bookmarked = (favicon_info->is_bookmarked ||
865                                   tracking_specifics.is_bookmarked());
866
867    if (syncer::TimeToProtoTime(favicon_info->last_visit_time) !=
868            tracking_specifics.last_visit_time_ms() ||
869        favicon_info->is_bookmarked != tracking_specifics.is_bookmarked()) {
870      BuildTrackingSpecifics(favicon_info,
871                             new_specifics.mutable_favicon_tracking());
872    }
873    DCHECK(!favicon_info->last_visit_time.is_null());
874  }
875
876  if (new_specifics.has_favicon_image() ||
877      new_specifics.has_favicon_tracking()) {
878    sync_changes->push_back(syncer::SyncChange(
879        FROM_HERE,
880        syncer::SyncChange::ACTION_UPDATE,
881        syncer::SyncData::CreateLocalData(favicon_url.spec(),
882                                          favicon_url.spec(),
883                                          new_specifics)));
884  }
885}
886
887void FaviconCache::AddLocalFaviconFromSyncedData(
888    const syncer::SyncData& sync_favicon) {
889  syncer::ModelType type = sync_favicon.GetDataType();
890  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
891  if (type == syncer::FAVICON_IMAGES) {
892    sync_pb::FaviconImageSpecifics image_specifics =
893        sync_favicon.GetSpecifics().favicon_image();
894    GURL favicon_url = GURL(image_specifics.favicon_url());
895    DCHECK(favicon_url.is_valid());
896    DCHECK(!synced_favicons_.count(favicon_url));
897
898    SyncedFaviconInfo* favicon_info = GetFaviconInfo(favicon_url);
899    if (!favicon_info)
900      return;  // We reached the in-memory limit.
901    if (image_specifics.has_favicon_web()) {
902      favicon_info->bitmap_data[SIZE_16] = GetImageDataFromSpecifics(
903          image_specifics.favicon_web());
904    }
905    if (image_specifics.has_favicon_web_32()) {
906      favicon_info->bitmap_data[SIZE_32] = GetImageDataFromSpecifics(
907          image_specifics.favicon_web_32());
908    }
909    if (image_specifics.has_favicon_touch_64()) {
910      favicon_info->bitmap_data[SIZE_64] = GetImageDataFromSpecifics(
911          image_specifics.favicon_touch_64());
912    }
913  } else {
914    sync_pb::FaviconTrackingSpecifics tracking_specifics =
915        sync_favicon.GetSpecifics().favicon_tracking();
916    GURL favicon_url = GURL(tracking_specifics.favicon_url());
917    DCHECK(favicon_url.is_valid());
918    DCHECK(!synced_favicons_.count(favicon_url));
919
920    SyncedFaviconInfo* favicon_info = GetFaviconInfo(favicon_url);
921    if (!favicon_info)
922      return;  // We reached the in-memory limit.
923    base::Time last_visit =  syncer::ProtoTimeToTime(
924        tracking_specifics.last_visit_time_ms());
925    // Due to crbug.com/258196, there are tracking nodes out there with
926    // null visit times. If this is one of those, artificially make it a valid
927    // visit time, so we know the node exists and update it properly on the next
928    // real visit.
929    if (last_visit.is_null())
930      last_visit = last_visit + base::TimeDelta::FromMilliseconds(1);
931    UpdateFaviconVisitTime(favicon_url, last_visit);
932    favicon_info->is_bookmarked = tracking_specifics.is_bookmarked();
933    DCHECK(!favicon_info->last_visit_time.is_null());
934  }
935}
936
937syncer::SyncData FaviconCache::CreateSyncDataFromLocalFavicon(
938    syncer::ModelType type,
939    const GURL& favicon_url) const {
940  DCHECK(type == syncer::FAVICON_IMAGES || type == syncer::FAVICON_TRACKING);
941  DCHECK(favicon_url.is_valid());
942  FaviconMap::const_iterator iter = synced_favicons_.find(favicon_url);
943  DCHECK(iter != synced_favicons_.end());
944  SyncedFaviconInfo* favicon_info = iter->second.get();
945
946  syncer::SyncData data;
947  sync_pb::EntitySpecifics specifics;
948  if (type == syncer::FAVICON_IMAGES) {
949    sync_pb::FaviconImageSpecifics* image_specifics =
950        specifics.mutable_favicon_image();
951    BuildImageSpecifics(favicon_info, image_specifics);
952  } else {
953    sync_pb::FaviconTrackingSpecifics* tracking_specifics =
954        specifics.mutable_favicon_tracking();
955    BuildTrackingSpecifics(favicon_info, tracking_specifics);
956  }
957  data = syncer::SyncData::CreateLocalData(favicon_url.spec(),
958                                           favicon_url.spec(),
959                                           specifics);
960  return data;
961}
962
963void FaviconCache::DeleteSyncedFavicons(const std::set<GURL>& favicon_urls) {
964  syncer::SyncChangeList image_deletions, tracking_deletions;
965  for (std::set<GURL>::const_iterator iter = favicon_urls.begin();
966       iter != favicon_urls.end(); ++iter) {
967    FaviconMap::iterator favicon_iter = synced_favicons_.find(*iter);
968    if (favicon_iter == synced_favicons_.end())
969      continue;
970    DeleteSyncedFavicon(favicon_iter,
971                        &image_deletions,
972                        &tracking_deletions);
973  }
974  DVLOG(1) << "Deleting " << image_deletions.size() << " synced favicons.";
975  if (favicon_images_sync_processor_.get()) {
976    favicon_images_sync_processor_->ProcessSyncChanges(FROM_HERE,
977                                                       image_deletions);
978  }
979  if (favicon_tracking_sync_processor_.get()) {
980    favicon_tracking_sync_processor_->ProcessSyncChanges(FROM_HERE,
981                                                         tracking_deletions);
982  }
983}
984
985void FaviconCache::DeleteSyncedFavicon(
986    FaviconMap::iterator favicon_iter,
987    syncer::SyncChangeList* image_changes,
988    syncer::SyncChangeList* tracking_changes) {
989  linked_ptr<SyncedFaviconInfo> favicon_info = favicon_iter->second;
990  if (FaviconInfoHasImages(*(favicon_iter->second))) {
991    DVLOG(1) << "Deleting image for "
992             << favicon_iter->second.get()->favicon_url;
993    image_changes->push_back(
994        syncer::SyncChange(FROM_HERE,
995                           syncer::SyncChange::ACTION_DELETE,
996                           syncer::SyncData::CreateLocalDelete(
997                               favicon_info->favicon_url.spec(),
998                               syncer::FAVICON_IMAGES)));
999  }
1000  if (FaviconInfoHasTracking(*(favicon_iter->second))) {
1001    DVLOG(1) << "Deleting tracking for "
1002             << favicon_iter->second.get()->favicon_url;
1003    tracking_changes->push_back(
1004        syncer::SyncChange(FROM_HERE,
1005                           syncer::SyncChange::ACTION_DELETE,
1006                           syncer::SyncData::CreateLocalDelete(
1007                               favicon_info->favicon_url.spec(),
1008                               syncer::FAVICON_TRACKING)));
1009  }
1010  DropSyncedFavicon(favicon_iter);
1011}
1012
1013void FaviconCache::DropSyncedFavicon(FaviconMap::iterator favicon_iter) {
1014  DVLOG(1) << "Dropping favicon " << favicon_iter->second.get()->favicon_url;
1015  recent_favicons_.erase(favicon_iter->second);
1016  synced_favicons_.erase(favicon_iter);
1017}
1018
1019void FaviconCache::DropPartialFavicon(FaviconMap::iterator favicon_iter,
1020                                      syncer::ModelType type) {
1021  // If the type being dropped has no valid data, do nothing.
1022  if ((type == syncer::FAVICON_TRACKING &&
1023       !FaviconInfoHasTracking(*favicon_iter->second)) ||
1024      (type == syncer::FAVICON_IMAGES &&
1025       !FaviconInfoHasImages(*favicon_iter->second))) {
1026    return;
1027  }
1028
1029  // If the type being dropped is the only type with valid data, just delete
1030  // the favicon altogether.
1031  if ((type == syncer::FAVICON_TRACKING &&
1032       !FaviconInfoHasImages(*favicon_iter->second)) ||
1033      (type == syncer::FAVICON_IMAGES &&
1034       !FaviconInfoHasTracking(*favicon_iter->second))) {
1035    DropSyncedFavicon(favicon_iter);
1036    return;
1037  }
1038
1039  if (type == syncer::FAVICON_IMAGES) {
1040    DVLOG(1) << "Dropping favicon image "
1041             << favicon_iter->second.get()->favicon_url;
1042    for (int i = 0; i < NUM_SIZES; ++i) {
1043      favicon_iter->second->bitmap_data[i] =
1044          favicon_base::FaviconRawBitmapResult();
1045    }
1046    DCHECK(!FaviconInfoHasImages(*favicon_iter->second));
1047  } else {
1048    DCHECK_EQ(type, syncer::FAVICON_TRACKING);
1049    DVLOG(1) << "Dropping favicon tracking "
1050             << favicon_iter->second.get()->favicon_url;
1051    recent_favicons_.erase(favicon_iter->second);
1052    favicon_iter->second->last_visit_time = base::Time();
1053    favicon_iter->second->is_bookmarked = false;
1054    recent_favicons_.insert(favicon_iter->second);
1055    DCHECK(!FaviconInfoHasTracking(*favicon_iter->second));
1056  }
1057}
1058
1059size_t FaviconCache::NumFaviconsForTest() const {
1060  return synced_favicons_.size();
1061}
1062
1063size_t FaviconCache::NumTasksForTest() const {
1064  return page_task_map_.size();
1065}
1066
1067}  // namespace browser_sync
1068