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