components/bookmarks/browser/bookmark_model.cc

   1 // Copyright 2014 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 "components/bookmarks/browser/bookmark_model.h"
   6
   7 #include <algorithm>
   8 #include <functional>
   9
  10 #include "base/bind.h"
  11 #include "base/bind_helpers.h"
  12 #include "base/i18n/string_compare.h"
  13 #include "base/logging.h"
  14 #include "base/macros.h"
  15 #include "base/metrics/histogram_macros.h"
  16 #include "base/profiler/scoped_tracker.h"
  17 #include "base/strings/string_util.h"
  18 #include "components/bookmarks/browser/bookmark_expanded_state_tracker.h"
  19 #include "components/bookmarks/browser/bookmark_index.h"
  20 #include "components/bookmarks/browser/bookmark_match.h"
  21 #include "components/bookmarks/browser/bookmark_model_observer.h"
  22 #include "components/bookmarks/browser/bookmark_node_data.h"
  23 #include "components/bookmarks/browser/bookmark_storage.h"
  24 #include "components/bookmarks/browser/bookmark_utils.h"
  25 #include "components/favicon_base/favicon_types.h"
  26 #include "grit/components_strings.h"
  27 #include "ui/base/l10n/l10n_util.h"
  28 #include "ui/gfx/favicon_size.h"
  29
  30 using base::Time;
  31
  32 namespace bookmarks {
  33
  34 namespace {
  35
  36 // Helper to get a mutable bookmark node.
  37 BookmarkNode* AsMutable(const BookmarkNode* node) {
  38   return const_cast<BookmarkNode*>(node);
  39 }
  40
  41 // Helper to get a mutable permanent bookmark node.
  42 BookmarkPermanentNode* AsMutable(const BookmarkPermanentNode* node) {
  43   return const_cast<BookmarkPermanentNode*>(node);
  44 }
  45
  46 // Comparator used when sorting permanent nodes. Nodes that are initially
  47 // visible are sorted before nodes that are initially hidden.
  48 class VisibilityComparator
  49     : public std::binary_function<const BookmarkPermanentNode*,
  50                                   const BookmarkPermanentNode*,
  51                                   bool> {
  52  public:
  53   explicit VisibilityComparator(BookmarkClient* client) : client_(client) {}
  54
  55   // Returns true if |n1| preceeds |n2|.
  56   bool operator()(const BookmarkPermanentNode* n1,
  57                   const BookmarkPermanentNode* n2) {
  58     bool n1_visible = client_->IsPermanentNodeVisible(n1);
  59     bool n2_visible = client_->IsPermanentNodeVisible(n2);
  60     return n1_visible != n2_visible && n1_visible;
  61   }
  62
  63  private:
  64   BookmarkClient* client_;
  65 };
  66
  67 // Comparator used when sorting bookmarks. Folders are sorted first, then
  68 // bookmarks.
  69 class SortComparator : public std::binary_function<const BookmarkNode*,
  70                                                    const BookmarkNode*,
  71                                                    bool> {
  72  public:
  73   explicit SortComparator(icu::Collator* collator) : collator_(collator) {}
  74
  75   // Returns true if |n1| preceeds |n2|.
  76   bool operator()(const BookmarkNode* n1, const BookmarkNode* n2) {
  77     if (n1->type() == n2->type()) {
  78       // Types are the same, compare the names.
  79       if (!collator_)
  80         return n1->GetTitle() < n2->GetTitle();
  81       return base::i18n::CompareString16WithCollator(
  82                  *collator_, n1->GetTitle(), n2->GetTitle()) == UCOL_LESS;
  83     }
  84     // Types differ, sort such that folders come first.
  85     return n1->is_folder();
  86   }
  87
  88  private:
  89   icu::Collator* collator_;
  90 };
  91
  92 }  // namespace
  93
  94 // BookmarkModel --------------------------------------------------------------
  95
  96 BookmarkModel::BookmarkModel(BookmarkClient* client)
  97     : client_(client),
  98       loaded_(false),
  99       root_(GURL()),
 100       bookmark_bar_node_(NULL),
 101       other_node_(NULL),
 102       mobile_node_(NULL),
 103       next_node_id_(1),
 104       observers_(
 105           base::ObserverList<BookmarkModelObserver>::NOTIFY_EXISTING_ONLY),
 106       loaded_signal_(true, false),
 107       extensive_changes_(0) {
 108   DCHECK(client_);
 109 }
 110
 111 BookmarkModel::~BookmarkModel() {
 112   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 113                     BookmarkModelBeingDeleted(this));
 114
 115   if (store_.get()) {
 116     // The store maintains a reference back to us. We need to tell it we're gone
 117     // so that it doesn't try and invoke a method back on us again.
 118     store_->BookmarkModelDeleted();
 119   }
 120 }
 121
 122 void BookmarkModel::Shutdown() {
 123   if (loaded_)
 124     return;
 125
 126   // See comment in HistoryService::ShutdownOnUIThread where this is invoked for
 127   // details. It is also called when the BookmarkModel is deleted.
 128   loaded_signal_.Signal();
 129 }
 130
 131 void BookmarkModel::Load(
 132     PrefService* pref_service,
 133     const std::string& accept_languages,
 134     const base::FilePath& profile_path,
 135     const scoped_refptr<base::SequencedTaskRunner>& io_task_runner,
 136     const scoped_refptr<base::SequencedTaskRunner>& ui_task_runner) {
 137   if (store_.get()) {
 138     // If the store is non-null, it means Load was already invoked. Load should
 139     // only be invoked once.
 140     NOTREACHED();
 141     return;
 142   }
 143
 144   expanded_state_tracker_.reset(
 145       new BookmarkExpandedStateTracker(this, pref_service));
 146
 147   // Load the bookmarks. BookmarkStorage notifies us when done.
 148   store_.reset(new BookmarkStorage(this, profile_path, io_task_runner.get()));
 149   store_->LoadBookmarks(CreateLoadDetails(accept_languages), ui_task_runner);
 150 }
 151
 152 const BookmarkNode* BookmarkModel::GetParentForNewNodes() {
 153   std::vector<const BookmarkNode*> nodes =
 154       GetMostRecentlyModifiedUserFolders(this, 1);
 155   DCHECK(!nodes.empty());  // This list is always padded with default folders.
 156   return nodes[0];
 157 }
 158
 159 void BookmarkModel::AddObserver(BookmarkModelObserver* observer) {
 160   observers_.AddObserver(observer);
 161 }
 162
 163 void BookmarkModel::RemoveObserver(BookmarkModelObserver* observer) {
 164   observers_.RemoveObserver(observer);
 165 }
 166
 167 void BookmarkModel::BeginExtensiveChanges() {
 168   if (++extensive_changes_ == 1) {
 169     FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 170                       ExtensiveBookmarkChangesBeginning(this));
 171   }
 172 }
 173
 174 void BookmarkModel::EndExtensiveChanges() {
 175   --extensive_changes_;
 176   DCHECK_GE(extensive_changes_, 0);
 177   if (extensive_changes_ == 0) {
 178     FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 179                       ExtensiveBookmarkChangesEnded(this));
 180   }
 181 }
 182
 183 void BookmarkModel::BeginGroupedChanges() {
 184   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 185                     GroupedBookmarkChangesBeginning(this));
 186 }
 187
 188 void BookmarkModel::EndGroupedChanges() {
 189   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 190                     GroupedBookmarkChangesEnded(this));
 191 }
 192
 193 void BookmarkModel::Remove(const BookmarkNode* node) {
 194   DCHECK(loaded_);
 195   DCHECK(node);
 196   DCHECK(!is_root_node(node));
 197   RemoveAndDeleteNode(AsMutable(node));
 198 }
 199
 200 void BookmarkModel::RemoveAllUserBookmarks() {
 201   std::set<GURL> removed_urls;
 202   ScopedVector<BookmarkNode> removed_nodes;
 203
 204   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 205                     OnWillRemoveAllUserBookmarks(this));
 206
 207   BeginExtensiveChanges();
 208   // Skip deleting permanent nodes. Permanent bookmark nodes are the root and
 209   // its immediate children. For removing all non permanent nodes just remove
 210   // all children of non-root permanent nodes.
 211   {
 212     base::AutoLock url_lock(url_lock_);
 213     for (int i = 0; i < root_.child_count(); ++i) {
 214       BookmarkNode* permanent_node = root_.GetChild(i);
 215
 216       if (!client_->CanBeEditedByUser(permanent_node))
 217         continue;
 218
 219       for (int j = permanent_node->child_count() - 1; j >= 0; --j) {
 220         BookmarkNode* child_node = permanent_node->GetChild(j);
 221         removed_nodes.push_back(child_node);
 222         RemoveNodeAndGetRemovedUrls(child_node, &removed_urls);
 223       }
 224     }
 225   }
 226   EndExtensiveChanges();
 227   if (store_.get())
 228     store_->ScheduleSave();
 229
 230   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 231                     BookmarkAllUserNodesRemoved(this, removed_urls));
 232 }
 233
 234 void BookmarkModel::Move(const BookmarkNode* node,
 235                          const BookmarkNode* new_parent,
 236                          int index) {
 237   if (!loaded_ || !node || !IsValidIndex(new_parent, index, true) ||
 238       is_root_node(new_parent) || is_permanent_node(node)) {
 239     NOTREACHED();
 240     return;
 241   }
 242
 243   if (new_parent->HasAncestor(node)) {
 244     // Can't make an ancestor of the node be a child of the node.
 245     NOTREACHED();
 246     return;
 247   }
 248
 249   const BookmarkNode* old_parent = node->parent();
 250   int old_index = old_parent->GetIndexOf(node);
 251
 252   if (old_parent == new_parent &&
 253       (index == old_index || index == old_index + 1)) {
 254     // Node is already in this position, nothing to do.
 255     return;
 256   }
 257
 258   SetDateFolderModified(new_parent, Time::Now());
 259
 260   if (old_parent == new_parent && index > old_index)
 261     index--;
 262   BookmarkNode* mutable_new_parent = AsMutable(new_parent);
 263   mutable_new_parent->Add(AsMutable(node), index);
 264
 265   if (store_.get())
 266     store_->ScheduleSave();
 267
 268   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 269                     BookmarkNodeMoved(this, old_parent, old_index,
 270                                       new_parent, index));
 271 }
 272
 273 void BookmarkModel::Copy(const BookmarkNode* node,
 274                          const BookmarkNode* new_parent,
 275                          int index) {
 276   if (!loaded_ || !node || !IsValidIndex(new_parent, index, true) ||
 277       is_root_node(new_parent) || is_permanent_node(node)) {
 278     NOTREACHED();
 279     return;
 280   }
 281
 282   if (new_parent->HasAncestor(node)) {
 283     // Can't make an ancestor of the node be a child of the node.
 284     NOTREACHED();
 285     return;
 286   }
 287
 288   SetDateFolderModified(new_parent, Time::Now());
 289   BookmarkNodeData drag_data(node);
 290   // CloneBookmarkNode will use BookmarkModel methods to do the job, so we
 291   // don't need to send notifications here.
 292   CloneBookmarkNode(this, drag_data.elements, new_parent, index, true);
 293
 294   if (store_.get())
 295     store_->ScheduleSave();
 296 }
 297
 298 const gfx::Image& BookmarkModel::GetFavicon(const BookmarkNode* node) {
 299   DCHECK(node);
 300   if (node->favicon_state() == BookmarkNode::INVALID_FAVICON) {
 301     BookmarkNode* mutable_node = AsMutable(node);
 302     LoadFavicon(mutable_node,
 303                 client_->PreferTouchIcon() ? favicon_base::TOUCH_ICON
 304                                            : favicon_base::FAVICON);
 305   }
 306   return node->favicon();
 307 }
 308
 309 favicon_base::IconType BookmarkModel::GetFaviconType(const BookmarkNode* node) {
 310   DCHECK(node);
 311   return node->favicon_type();
 312 }
 313
 314 void BookmarkModel::SetTitle(const BookmarkNode* node,
 315                              const base::string16& title) {
 316   DCHECK(node);
 317
 318   if (node->GetTitle() == title)
 319     return;
 320
 321   if (is_permanent_node(node) && !client_->CanSetPermanentNodeTitle(node)) {
 322     NOTREACHED();
 323     return;
 324   }
 325
 326   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 327                     OnWillChangeBookmarkNode(this, node));
 328
 329   // The title index doesn't support changing the title, instead we remove then
 330   // add it back.
 331   index_->Remove(node);
 332   AsMutable(node)->SetTitle(title);
 333   index_->Add(node);
 334
 335   if (store_.get())
 336     store_->ScheduleSave();
 337
 338   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 339                     BookmarkNodeChanged(this, node));
 340 }
 341
 342 void BookmarkModel::SetURL(const BookmarkNode* node, const GURL& url) {
 343   DCHECK(node && !node->is_folder());
 344
 345   if (node->url() == url)
 346     return;
 347
 348   BookmarkNode* mutable_node = AsMutable(node);
 349   mutable_node->InvalidateFavicon();
 350   CancelPendingFaviconLoadRequests(mutable_node);
 351
 352   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 353                     OnWillChangeBookmarkNode(this, node));
 354
 355   {
 356     base::AutoLock url_lock(url_lock_);
 357     RemoveNodeFromInternalMaps(mutable_node);
 358     mutable_node->set_url(url);
 359     AddNodeToInternalMaps(mutable_node);
 360   }
 361
 362   if (store_.get())
 363     store_->ScheduleSave();
 364
 365   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 366                     BookmarkNodeChanged(this, node));
 367 }
 368
 369 void BookmarkModel::SetNodeMetaInfo(const BookmarkNode* node,
 370                                     const std::string& key,
 371                                     const std::string& value) {
 372   std::string old_value;
 373   if (node->GetMetaInfo(key, &old_value) && old_value == value)
 374     return;
 375
 376   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 377                     OnWillChangeBookmarkMetaInfo(this, node));
 378
 379   if (AsMutable(node)->SetMetaInfo(key, value) && store_.get())
 380     store_->ScheduleSave();
 381
 382   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 383                     BookmarkMetaInfoChanged(this, node));
 384 }
 385
 386 void BookmarkModel::SetNodeMetaInfoMap(
 387     const BookmarkNode* node,
 388     const BookmarkNode::MetaInfoMap& meta_info_map) {
 389   const BookmarkNode::MetaInfoMap* old_meta_info_map = node->GetMetaInfoMap();
 390   if ((!old_meta_info_map && meta_info_map.empty()) ||
 391       (old_meta_info_map && meta_info_map == *old_meta_info_map))
 392     return;
 393
 394   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 395                     OnWillChangeBookmarkMetaInfo(this, node));
 396
 397   AsMutable(node)->SetMetaInfoMap(meta_info_map);
 398   if (store_.get())
 399     store_->ScheduleSave();
 400
 401   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 402                     BookmarkMetaInfoChanged(this, node));
 403 }
 404
 405 void BookmarkModel::DeleteNodeMetaInfo(const BookmarkNode* node,
 406                                        const std::string& key) {
 407   const BookmarkNode::MetaInfoMap* meta_info_map = node->GetMetaInfoMap();
 408   if (!meta_info_map || meta_info_map->find(key) == meta_info_map->end())
 409     return;
 410
 411   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 412                     OnWillChangeBookmarkMetaInfo(this, node));
 413
 414   if (AsMutable(node)->DeleteMetaInfo(key) && store_.get())
 415     store_->ScheduleSave();
 416
 417   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 418                     BookmarkMetaInfoChanged(this, node));
 419 }
 420
 421 void BookmarkModel::AddNonClonedKey(const std::string& key) {
 422   non_cloned_keys_.insert(key);
 423 }
 424
 425 void BookmarkModel::SetNodeSyncTransactionVersion(
 426     const BookmarkNode* node,
 427     int64 sync_transaction_version) {
 428   DCHECK(client_->CanSyncNode(node));
 429
 430   if (sync_transaction_version == node->sync_transaction_version())
 431     return;
 432
 433   AsMutable(node)->set_sync_transaction_version(sync_transaction_version);
 434   if (store_.get())
 435     store_->ScheduleSave();
 436 }
 437
 438 void BookmarkModel::OnFaviconsChanged(const std::set<GURL>& page_urls,
 439                                       const GURL& icon_url) {
 440   std::set<const BookmarkNode*> to_update;
 441   for (const GURL& page_url : page_urls) {
 442     std::vector<const BookmarkNode*> nodes;
 443     GetNodesByURL(page_url, &nodes);
 444     to_update.insert(nodes.begin(), nodes.end());
 445   }
 446
 447   if (!icon_url.is_empty()) {
 448     // Log Histogram to determine how often |icon_url| is non empty in
 449     // practice.
 450     // TODO(pkotwicz): Do something more efficient if |icon_url| is non-empty
 451     // many times a day for each user.
 452     UMA_HISTOGRAM_BOOLEAN("Bookmarks.OnFaviconsChangedIconURL", true);
 453
 454     base::AutoLock url_lock(url_lock_);
 455     for (const BookmarkNode* node : nodes_ordered_by_url_set_) {
 456       if (icon_url == node->icon_url())
 457         to_update.insert(node);
 458     }
 459   }
 460
 461   for (const BookmarkNode* node : to_update) {
 462     // Rerequest the favicon.
 463     BookmarkNode* mutable_node = AsMutable(node);
 464     mutable_node->InvalidateFavicon();
 465     CancelPendingFaviconLoadRequests(mutable_node);
 466     FOR_EACH_OBSERVER(BookmarkModelObserver,
 467                       observers_,
 468                       BookmarkNodeFaviconChanged(this, node));
 469   }
 470 }
 471
 472 void BookmarkModel::SetDateAdded(const BookmarkNode* node, Time date_added) {
 473   DCHECK(node && !is_permanent_node(node));
 474
 475   if (node->date_added() == date_added)
 476     return;
 477
 478   AsMutable(node)->set_date_added(date_added);
 479
 480   // Syncing might result in dates newer than the folder's last modified date.
 481   if (date_added > node->parent()->date_folder_modified()) {
 482     // Will trigger store_->ScheduleSave().
 483     SetDateFolderModified(node->parent(), date_added);
 484   } else if (store_.get()) {
 485     store_->ScheduleSave();
 486   }
 487 }
 488
 489 void BookmarkModel::GetNodesByURL(const GURL& url,
 490                                   std::vector<const BookmarkNode*>* nodes) {
 491   base::AutoLock url_lock(url_lock_);
 492   BookmarkNode tmp_node(url);
 493   NodesOrderedByURLSet::iterator i = nodes_ordered_by_url_set_.find(&tmp_node);
 494   while (i != nodes_ordered_by_url_set_.end() && (*i)->url() == url) {
 495     nodes->push_back(*i);
 496     ++i;
 497   }
 498 }
 499
 500 const BookmarkNode* BookmarkModel::GetMostRecentlyAddedUserNodeForURL(
 501     const GURL& url) {
 502   std::vector<const BookmarkNode*> nodes;
 503   GetNodesByURL(url, &nodes);
 504   std::sort(nodes.begin(), nodes.end(), &MoreRecentlyAdded);
 505
 506   // Look for the first node that the user can edit.
 507   for (size_t i = 0; i < nodes.size(); ++i) {
 508     if (client_->CanBeEditedByUser(nodes[i]))
 509       return nodes[i];
 510   }
 511
 512   return NULL;
 513 }
 514
 515 bool BookmarkModel::HasBookmarks() {
 516   base::AutoLock url_lock(url_lock_);
 517   return !nodes_ordered_by_url_set_.empty();
 518 }
 519
 520 bool BookmarkModel::IsBookmarked(const GURL& url) {
 521   base::AutoLock url_lock(url_lock_);
 522   return IsBookmarkedNoLock(url);
 523 }
 524
 525 void BookmarkModel::GetBookmarks(
 526     std::vector<BookmarkModel::URLAndTitle>* bookmarks) {
 527   base::AutoLock url_lock(url_lock_);
 528   const GURL* last_url = NULL;
 529   for (NodesOrderedByURLSet::iterator i = nodes_ordered_by_url_set_.begin();
 530        i != nodes_ordered_by_url_set_.end(); ++i) {
 531     const GURL* url = &((*i)->url());
 532     // Only add unique URLs.
 533     if (!last_url || *url != *last_url) {
 534       BookmarkModel::URLAndTitle bookmark;
 535       bookmark.url = *url;
 536       bookmark.title = (*i)->GetTitle();
 537       bookmarks->push_back(bookmark);
 538     }
 539     last_url = url;
 540   }
 541 }
 542
 543 void BookmarkModel::BlockTillLoaded() {
 544   loaded_signal_.Wait();
 545 }
 546
 547 const BookmarkNode* BookmarkModel::AddFolder(const BookmarkNode* parent,
 548                                              int index,
 549                                              const base::string16& title) {
 550   return AddFolderWithMetaInfo(parent, index, title, NULL);
 551 }
 552 const BookmarkNode* BookmarkModel::AddFolderWithMetaInfo(
 553     const BookmarkNode* parent,
 554     int index,
 555     const base::string16& title,
 556     const BookmarkNode::MetaInfoMap* meta_info) {
 557   if (!loaded_ || is_root_node(parent) || !IsValidIndex(parent, index, true)) {
 558     // Can't add to the root.
 559     NOTREACHED();
 560     return NULL;
 561   }
 562
 563   BookmarkNode* new_node = new BookmarkNode(generate_next_node_id(), GURL());
 564   new_node->set_date_folder_modified(Time::Now());
 565   // Folders shouldn't have line breaks in their titles.
 566   new_node->SetTitle(title);
 567   new_node->set_type(BookmarkNode::FOLDER);
 568   if (meta_info)
 569     new_node->SetMetaInfoMap(*meta_info);
 570
 571   return AddNode(AsMutable(parent), index, new_node);
 572 }
 573
 574 const BookmarkNode* BookmarkModel::AddURL(const BookmarkNode* parent,
 575                                           int index,
 576                                           const base::string16& title,
 577                                           const GURL& url) {
 578   return AddURLWithCreationTimeAndMetaInfo(
 579       parent,
 580       index,
 581       base::CollapseWhitespace(title, false),
 582       url,
 583       Time::Now(),
 584       NULL);
 585 }
 586
 587 const BookmarkNode* BookmarkModel::AddURLWithCreationTimeAndMetaInfo(
 588     const BookmarkNode* parent,
 589     int index,
 590     const base::string16& title,
 591     const GURL& url,
 592     const Time& creation_time,
 593     const BookmarkNode::MetaInfoMap* meta_info) {
 594   if (!loaded_ || !url.is_valid() || is_root_node(parent) ||
 595       !IsValidIndex(parent, index, true)) {
 596     NOTREACHED();
 597     return NULL;
 598   }
 599
 600   // Syncing may result in dates newer than the last modified date.
 601   if (creation_time > parent->date_folder_modified())
 602     SetDateFolderModified(parent, creation_time);
 603
 604   BookmarkNode* new_node = new BookmarkNode(generate_next_node_id(), url);
 605   new_node->SetTitle(title);
 606   new_node->set_date_added(creation_time);
 607   new_node->set_type(BookmarkNode::URL);
 608   if (meta_info)
 609     new_node->SetMetaInfoMap(*meta_info);
 610
 611   return AddNode(AsMutable(parent), index, new_node);
 612 }
 613
 614 void BookmarkModel::SortChildren(const BookmarkNode* parent) {
 615   DCHECK(client_->CanBeEditedByUser(parent));
 616
 617   if (!parent || !parent->is_folder() || is_root_node(parent) ||
 618       parent->child_count() <= 1) {
 619     return;
 620   }
 621
 622   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 623                     OnWillReorderBookmarkNode(this, parent));
 624
 625   UErrorCode error = U_ZERO_ERROR;
 626   scoped_ptr<icu::Collator> collator(icu::Collator::createInstance(error));
 627   if (U_FAILURE(error))
 628     collator.reset(NULL);
 629   BookmarkNode* mutable_parent = AsMutable(parent);
 630   std::sort(mutable_parent->children().begin(),
 631             mutable_parent->children().end(),
 632             SortComparator(collator.get()));
 633
 634   if (store_.get())
 635     store_->ScheduleSave();
 636
 637   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 638                     BookmarkNodeChildrenReordered(this, parent));
 639 }
 640
 641 void BookmarkModel::ReorderChildren(
 642     const BookmarkNode* parent,
 643     const std::vector<const BookmarkNode*>& ordered_nodes) {
 644   DCHECK(client_->CanBeEditedByUser(parent));
 645
 646   // Ensure that all children in |parent| are in |ordered_nodes|.
 647   DCHECK_EQ(static_cast<size_t>(parent->child_count()), ordered_nodes.size());
 648   for (size_t i = 0; i < ordered_nodes.size(); ++i)
 649     DCHECK_EQ(parent, ordered_nodes[i]->parent());
 650
 651   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 652                     OnWillReorderBookmarkNode(this, parent));
 653
 654   AsMutable(parent)->SetChildren(
 655       *(reinterpret_cast<const std::vector<BookmarkNode*>*>(&ordered_nodes)));
 656
 657   if (store_.get())
 658     store_->ScheduleSave();
 659
 660   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 661                     BookmarkNodeChildrenReordered(this, parent));
 662 }
 663
 664 void BookmarkModel::SetDateFolderModified(const BookmarkNode* parent,
 665                                           const Time time) {
 666   DCHECK(parent);
 667   AsMutable(parent)->set_date_folder_modified(time);
 668
 669   if (store_.get())
 670     store_->ScheduleSave();
 671 }
 672
 673 void BookmarkModel::ResetDateFolderModified(const BookmarkNode* node) {
 674   SetDateFolderModified(node, Time());
 675 }
 676
 677 void BookmarkModel::GetBookmarksMatching(const base::string16& text,
 678                                          size_t max_count,
 679                                          std::vector<BookmarkMatch>* matches) {
 680   GetBookmarksMatching(text, max_count,
 681                        query_parser::MatchingAlgorithm::DEFAULT, matches);
 682 }
 683
 684 void BookmarkModel::GetBookmarksMatching(
 685     const base::string16& text,
 686     size_t max_count,
 687     query_parser::MatchingAlgorithm matching_algorithm,
 688     std::vector<BookmarkMatch>* matches) {
 689   if (!loaded_)
 690     return;
 691
 692   index_->GetBookmarksMatching(text, max_count, matching_algorithm, matches);
 693 }
 694
 695 void BookmarkModel::ClearStore() {
 696   store_.reset();
 697 }
 698
 699 void BookmarkModel::SetPermanentNodeVisible(BookmarkNode::Type type,
 700                                             bool value) {
 701   BookmarkPermanentNode* node = AsMutable(PermanentNode(type));
 702   node->set_visible(value || client_->IsPermanentNodeVisible(node));
 703 }
 704
 705 const BookmarkPermanentNode* BookmarkModel::PermanentNode(
 706     BookmarkNode::Type type) {
 707   DCHECK(loaded_);
 708   switch (type) {
 709     case BookmarkNode::BOOKMARK_BAR:
 710       return bookmark_bar_node_;
 711     case BookmarkNode::OTHER_NODE:
 712       return other_node_;
 713     case BookmarkNode::MOBILE:
 714       return mobile_node_;
 715     default:
 716       NOTREACHED();
 717       return NULL;
 718   }
 719 }
 720
 721 bool BookmarkModel::IsBookmarkedNoLock(const GURL& url) {
 722   BookmarkNode tmp_node(url);
 723   return (nodes_ordered_by_url_set_.find(&tmp_node) !=
 724           nodes_ordered_by_url_set_.end());
 725 }
 726
 727 void BookmarkModel::RemoveNode(BookmarkNode* node,
 728                                std::set<GURL>* removed_urls) {
 729   if (!loaded_ || !node || is_permanent_node(node)) {
 730     NOTREACHED();
 731     return;
 732   }
 733
 734   url_lock_.AssertAcquired();
 735   if (node->is_url()) {
 736     RemoveNodeFromInternalMaps(node);
 737     removed_urls->insert(node->url());
 738   }
 739
 740   CancelPendingFaviconLoadRequests(node);
 741
 742   // Recurse through children.
 743   for (int i = node->child_count() - 1; i >= 0; --i)
 744     RemoveNode(node->GetChild(i), removed_urls);
 745 }
 746
 747 void BookmarkModel::DoneLoading(scoped_ptr<BookmarkLoadDetails> details) {
 748   DCHECK(details);
 749   if (loaded_) {
 750     // We should only ever be loaded once.
 751     NOTREACHED();
 752     return;
 753   }
 754
 755   // TODO(robliao): Remove ScopedTracker below once https://crbug.com/467179
 756   // is fixed.
 757   tracked_objects::ScopedTracker tracking_profile1(
 758       FROM_HERE_WITH_EXPLICIT_FUNCTION("467179 BookmarkModel::DoneLoading1"));
 759
 760   next_node_id_ = details->max_id();
 761   if (details->computed_checksum() != details->stored_checksum() ||
 762       details->ids_reassigned()) {
 763     // TODO(robliao): Remove ScopedTracker below once https://crbug.com/467179
 764     // is fixed.
 765     tracked_objects::ScopedTracker tracking_profile2(
 766         FROM_HERE_WITH_EXPLICIT_FUNCTION("467179 BookmarkModel::DoneLoading2"));
 767
 768     // If bookmarks file changed externally, the IDs may have changed
 769     // externally. In that case, the decoder may have reassigned IDs to make
 770     // them unique. So when the file has changed externally, we should save the
 771     // bookmarks file to persist new IDs.
 772     if (store_.get())
 773       store_->ScheduleSave();
 774   }
 775   bookmark_bar_node_ = details->release_bb_node();
 776   other_node_ = details->release_other_folder_node();
 777   mobile_node_ = details->release_mobile_folder_node();
 778   index_.reset(details->release_index());
 779
 780   // Get any extra nodes and take ownership of them at the |root_|.
 781   std::vector<BookmarkPermanentNode*> extra_nodes;
 782   details->release_extra_nodes(&extra_nodes);
 783
 784   // TODO(robliao): Remove ScopedTracker below once https://crbug.com/467179
 785   // is fixed.
 786   tracked_objects::ScopedTracker tracking_profile3(
 787       FROM_HERE_WITH_EXPLICIT_FUNCTION("467179 BookmarkModel::DoneLoading3"));
 788
 789   // WARNING: order is important here, various places assume the order is
 790   // constant (but can vary between embedders with the initial visibility
 791   // of permanent nodes).
 792   std::vector<BookmarkPermanentNode*> root_children;
 793   root_children.push_back(bookmark_bar_node_);
 794   root_children.push_back(other_node_);
 795   root_children.push_back(mobile_node_);
 796   for (size_t i = 0; i < extra_nodes.size(); ++i)
 797     root_children.push_back(extra_nodes[i]);
 798
 799   // TODO(robliao): Remove ScopedTracker below once https://crbug.com/467179
 800   // is fixed.
 801   tracked_objects::ScopedTracker tracking_profile4(
 802       FROM_HERE_WITH_EXPLICIT_FUNCTION("467179 BookmarkModel::DoneLoading4"));
 803
 804   std::stable_sort(root_children.begin(),
 805                    root_children.end(),
 806                    VisibilityComparator(client_));
 807   for (size_t i = 0; i < root_children.size(); ++i)
 808     root_.Add(root_children[i], static_cast<int>(i));
 809
 810   root_.SetMetaInfoMap(details->model_meta_info_map());
 811   root_.set_sync_transaction_version(details->model_sync_transaction_version());
 812
 813   // TODO(robliao): Remove ScopedTracker below once https://crbug.com/467179
 814   // is fixed.
 815   tracked_objects::ScopedTracker tracking_profile5(
 816       FROM_HERE_WITH_EXPLICIT_FUNCTION("467179 BookmarkModel::DoneLoading5"));
 817
 818   {
 819     base::AutoLock url_lock(url_lock_);
 820     // Update nodes_ordered_by_url_set_ from the nodes.
 821     PopulateNodesByURL(&root_);
 822   }
 823
 824   loaded_ = true;
 825
 826   loaded_signal_.Signal();
 827
 828   // TODO(robliao): Remove ScopedTracker below once https://crbug.com/467179
 829   // is fixed.
 830   tracked_objects::ScopedTracker tracking_profile6(
 831       FROM_HERE_WITH_EXPLICIT_FUNCTION("467179 BookmarkModel::DoneLoading6"));
 832
 833   // Notify our direct observers.
 834   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 835                     BookmarkModelLoaded(this, details->ids_reassigned()));
 836 }
 837
 838 void BookmarkModel::RemoveAndDeleteNode(BookmarkNode* delete_me) {
 839   scoped_ptr<BookmarkNode> node(delete_me);
 840
 841   const BookmarkNode* parent = node->parent();
 842   DCHECK(parent);
 843   int index = parent->GetIndexOf(node.get());
 844   DCHECK_NE(-1, index);
 845
 846   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 847                     OnWillRemoveBookmarks(this, parent, index, node.get()));
 848
 849   std::set<GURL> removed_urls;
 850   {
 851     base::AutoLock url_lock(url_lock_);
 852     RemoveNodeAndGetRemovedUrls(node.get(), &removed_urls);
 853   }
 854
 855   if (store_.get())
 856     store_->ScheduleSave();
 857
 858   FOR_EACH_OBSERVER(
 859       BookmarkModelObserver,
 860       observers_,
 861       BookmarkNodeRemoved(this, parent, index, node.get(), removed_urls));
 862 }
 863
 864 void BookmarkModel::RemoveNodeFromInternalMaps(BookmarkNode* node) {
 865   index_->Remove(node);
 866   // NOTE: this is called in such a way that url_lock_ is already held. As
 867   // such, this doesn't explicitly grab the lock.
 868   url_lock_.AssertAcquired();
 869   NodesOrderedByURLSet::iterator i = nodes_ordered_by_url_set_.find(node);
 870   DCHECK(i != nodes_ordered_by_url_set_.end());
 871   // i points to the first node with the URL, advance until we find the
 872   // node we're removing.
 873   while (*i != node)
 874     ++i;
 875   nodes_ordered_by_url_set_.erase(i);
 876 }
 877
 878 void BookmarkModel::RemoveNodeAndGetRemovedUrls(BookmarkNode* node,
 879                                                 std::set<GURL>* removed_urls) {
 880   // NOTE: this method should be always called with |url_lock_| held.
 881   // This method does not explicitly acquires a lock.
 882   url_lock_.AssertAcquired();
 883   DCHECK(removed_urls);
 884   BookmarkNode* parent = node->parent();
 885   DCHECK(parent);
 886   parent->Remove(node);
 887   RemoveNode(node, removed_urls);
 888   // RemoveNode adds an entry to removed_urls for each node of type URL. As we
 889   // allow duplicates we need to remove any entries that are still bookmarked.
 890   for (std::set<GURL>::iterator i = removed_urls->begin();
 891        i != removed_urls->end();) {
 892     if (IsBookmarkedNoLock(*i)) {
 893       // When we erase the iterator pointing at the erasee is
 894       // invalidated, so using i++ here within the "erase" call is
 895       // important as it advances the iterator before passing the
 896       // old value through to erase.
 897       removed_urls->erase(i++);
 898     } else {
 899       ++i;
 900     }
 901   }
 902 }
 903
 904 BookmarkNode* BookmarkModel::AddNode(BookmarkNode* parent,
 905                                      int index,
 906                                      BookmarkNode* node) {
 907   parent->Add(node, index);
 908
 909   if (store_.get())
 910     store_->ScheduleSave();
 911
 912   if (node->type() == BookmarkNode::URL) {
 913     base::AutoLock url_lock(url_lock_);
 914     AddNodeToInternalMaps(node);
 915   } else {
 916     index_->Add(node);
 917   }
 918
 919   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
 920                     BookmarkNodeAdded(this, parent, index));
 921
 922   return node;
 923 }
 924
 925 void BookmarkModel::AddNodeToInternalMaps(BookmarkNode* node) {
 926   index_->Add(node);
 927   url_lock_.AssertAcquired();
 928   nodes_ordered_by_url_set_.insert(node);
 929 }
 930
 931 bool BookmarkModel::IsValidIndex(const BookmarkNode* parent,
 932                                  int index,
 933                                  bool allow_end) {
 934   return (parent && parent->is_folder() &&
 935           (index >= 0 && (index < parent->child_count() ||
 936                           (allow_end && index == parent->child_count()))));
 937 }
 938
 939 BookmarkPermanentNode* BookmarkModel::CreatePermanentNode(
 940     BookmarkNode::Type type) {
 941   DCHECK(type == BookmarkNode::BOOKMARK_BAR ||
 942          type == BookmarkNode::OTHER_NODE ||
 943          type == BookmarkNode::MOBILE);
 944   BookmarkPermanentNode* node =
 945       new BookmarkPermanentNode(generate_next_node_id());
 946   node->set_type(type);
 947   node->set_visible(client_->IsPermanentNodeVisible(node));
 948
 949   int title_id;
 950   switch (type) {
 951     case BookmarkNode::BOOKMARK_BAR:
 952       title_id = IDS_BOOKMARK_BAR_FOLDER_NAME;
 953       break;
 954     case BookmarkNode::OTHER_NODE:
 955       title_id = IDS_BOOKMARK_BAR_OTHER_FOLDER_NAME;
 956       break;
 957     case BookmarkNode::MOBILE:
 958       title_id = IDS_BOOKMARK_BAR_MOBILE_FOLDER_NAME;
 959       break;
 960     default:
 961       NOTREACHED();
 962       title_id = IDS_BOOKMARK_BAR_FOLDER_NAME;
 963       break;
 964   }
 965   node->SetTitle(l10n_util::GetStringUTF16(title_id));
 966   return node;
 967 }
 968
 969 void BookmarkModel::OnFaviconDataAvailable(
 970     BookmarkNode* node,
 971     favicon_base::IconType icon_type,
 972     const favicon_base::FaviconImageResult& image_result) {
 973   DCHECK(node);
 974   node->set_favicon_load_task_id(base::CancelableTaskTracker::kBadTaskId);
 975   node->set_favicon_state(BookmarkNode::LOADED_FAVICON);
 976   if (!image_result.image.IsEmpty()) {
 977     node->set_favicon_type(icon_type);
 978     node->set_favicon(image_result.image);
 979     node->set_icon_url(image_result.icon_url);
 980     FaviconLoaded(node);
 981   } else if (icon_type == favicon_base::TOUCH_ICON) {
 982     // Couldn't load the touch icon, fallback to the regular favicon.
 983     DCHECK(client_->PreferTouchIcon());
 984     LoadFavicon(node, favicon_base::FAVICON);
 985   }
 986 }
 987
 988 void BookmarkModel::LoadFavicon(BookmarkNode* node,
 989                                 favicon_base::IconType icon_type) {
 990   if (node->is_folder())
 991     return;
 992
 993   DCHECK(node->url().is_valid());
 994   node->set_favicon_state(BookmarkNode::LOADING_FAVICON);
 995   base::CancelableTaskTracker::TaskId taskId =
 996       client_->GetFaviconImageForPageURL(
 997           node->url(),
 998           icon_type,
 999           base::Bind(
1000               &BookmarkModel::OnFaviconDataAvailable,
1001               base::Unretained(this),
1002               node,
1003               icon_type),
1004           &cancelable_task_tracker_);
1005   if (taskId != base::CancelableTaskTracker::kBadTaskId)
1006     node->set_favicon_load_task_id(taskId);
1007 }
1008
1009 void BookmarkModel::FaviconLoaded(const BookmarkNode* node) {
1010   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
1011                     BookmarkNodeFaviconChanged(this, node));
1012 }
1013
1014 void BookmarkModel::CancelPendingFaviconLoadRequests(BookmarkNode* node) {
1015   if (node->favicon_load_task_id() != base::CancelableTaskTracker::kBadTaskId) {
1016     cancelable_task_tracker_.TryCancel(node->favicon_load_task_id());
1017     node->set_favicon_load_task_id(base::CancelableTaskTracker::kBadTaskId);
1018   }
1019 }
1020
1021 void BookmarkModel::PopulateNodesByURL(BookmarkNode* node) {
1022   // NOTE: this is called with url_lock_ already held. As such, this doesn't
1023   // explicitly grab the lock.
1024   if (node->is_url())
1025     nodes_ordered_by_url_set_.insert(node);
1026   for (int i = 0; i < node->child_count(); ++i)
1027     PopulateNodesByURL(node->GetChild(i));
1028 }
1029
1030 int64 BookmarkModel::generate_next_node_id() {
1031   return next_node_id_++;
1032 }
1033
1034 scoped_ptr<BookmarkLoadDetails> BookmarkModel::CreateLoadDetails(
1035     const std::string& accept_languages) {
1036   BookmarkPermanentNode* bb_node =
1037       CreatePermanentNode(BookmarkNode::BOOKMARK_BAR);
1038   BookmarkPermanentNode* other_node =
1039       CreatePermanentNode(BookmarkNode::OTHER_NODE);
1040   BookmarkPermanentNode* mobile_node =
1041       CreatePermanentNode(BookmarkNode::MOBILE);
1042   return scoped_ptr<BookmarkLoadDetails>(new BookmarkLoadDetails(
1043       bb_node,
1044       other_node,
1045       mobile_node,
1046       client_->GetLoadExtraNodesCallback(),
1047       new BookmarkIndex(client_, accept_languages),
1048       next_node_id_));
1049 }
1050
1051 }  // namespace bookmarks