Home | History | Annotate | Download | only in bookmarks 
      1 // Copyright (c) 2012 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/bookmarks/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/json/json_string_value_serializer.h"
     14 #include "base/sequenced_task_runner.h"
     15 #include "base/strings/string_util.h"
     16 #include "base/strings/utf_string_conversions.h"
     17 #include "base/values.h"
     18 #include "chrome/browser/bookmarks/bookmark_expanded_state_tracker.h"
     19 #include "chrome/browser/bookmarks/bookmark_index.h"
     20 #include "chrome/browser/bookmarks/bookmark_model_observer.h"
     21 #include "chrome/browser/bookmarks/bookmark_storage.h"
     22 #include "chrome/browser/bookmarks/bookmark_title_match.h"
     23 #include "chrome/browser/bookmarks/bookmark_utils.h"
     24 #include "chrome/browser/chrome_notification_types.h"
     25 #include "chrome/browser/favicon/favicon_changed_details.h"
     26 #include "chrome/browser/favicon/favicon_service.h"
     27 #include "chrome/browser/favicon/favicon_service_factory.h"
     28 #include "chrome/browser/history/history_service.h"
     29 #include "chrome/browser/history/history_service_factory.h"
     30 #include "chrome/browser/profiles/profile.h"
     31 #include "chrome/common/favicon/favicon_types.h"
     32 #include "content/public/browser/notification_details.h"
     33 #include "content/public/browser/notification_source.h"
     34 #include "grit/generated_resources.h"
     35 #include "ui/base/l10n/l10n_util.h"
     36 #include "ui/gfx/favicon_size.h"
     37 #include "ui/gfx/image/image_util.h"
     38 
     39 using base::Time;
     40 
     41 namespace {
     42 
     43 // Helper to get a mutable bookmark node.
     44 BookmarkNode* AsMutable(const BookmarkNode* node) {
     45   return const_cast<BookmarkNode*>(node);
     46 }
     47 
     48 // Helper to recursively determine if a Dictionary has any valid values.
     49 bool HasValues(const base::DictionaryValue& root) {
     50   if (root.empty())
     51     return false;
     52   for (base::DictionaryValue::Iterator iter(root); !iter.IsAtEnd();
     53        iter.Advance()) {
     54     const base::Value& value = iter.value();
     55     if (value.IsType(base::Value::TYPE_DICTIONARY)) {
     56       const base::DictionaryValue* dict_value = NULL;
     57       if (value.GetAsDictionary(&dict_value) && HasValues(*dict_value))
     58         return true;
     59     } else {
     60       // A non dictionary type was encountered, assume it's a valid value.
     61       return true;
     62     }
     63   }
     64   return false;
     65 }
     66 
     67 // Whitespace characters to strip from bookmark titles.
     68 const char16 kInvalidChars[] = {
     69   '\n', '\r', '\t',
     70   0x2028,  // Line separator
     71   0x2029,  // Paragraph separator
     72   0
     73 };
     74 
     75 }  // namespace
     76 
     77 // BookmarkNode ---------------------------------------------------------------
     78 
     79 BookmarkNode::BookmarkNode(const GURL& url)
     80     : url_(url) {
     81   Initialize(0);
     82 }
     83 
     84 BookmarkNode::BookmarkNode(int64 id, const GURL& url)
     85     : url_(url) {
     86   Initialize(id);
     87 }
     88 
     89 BookmarkNode::~BookmarkNode() {
     90 }
     91 
     92 void BookmarkNode::SetTitle(const string16& title) {
     93   // Replace newlines and other problematic whitespace characters in
     94   // folder/bookmark names with spaces.
     95   string16 trimmed_title;
     96   ReplaceChars(title, kInvalidChars, ASCIIToUTF16(" "), &trimmed_title);
     97   ui::TreeNode<BookmarkNode>::SetTitle(trimmed_title);
     98 }
     99 
    100 bool BookmarkNode::IsVisible() const {
    101   return true;
    102 }
    103 
    104 bool BookmarkNode::GetMetaInfo(const std::string& key,
    105                                std::string* value) const {
    106   if (meta_info_str_.empty())
    107     return false;
    108 
    109   JSONStringValueSerializer serializer(meta_info_str_);
    110   scoped_ptr<DictionaryValue> meta_dict(
    111       static_cast<DictionaryValue*>(serializer.Deserialize(NULL, NULL)));
    112   return meta_dict.get() ? meta_dict->GetString(key, value) : false;
    113 }
    114 
    115 bool BookmarkNode::SetMetaInfo(const std::string& key,
    116                                const std::string& value) {
    117   JSONStringValueSerializer serializer(&meta_info_str_);
    118   scoped_ptr<DictionaryValue> meta_dict;
    119   if (!meta_info_str_.empty()) {
    120     meta_dict.reset(
    121         static_cast<DictionaryValue*>(serializer.Deserialize(NULL, NULL)));
    122   }
    123   if (!meta_dict.get()) {
    124     meta_dict.reset(new DictionaryValue);
    125   } else {
    126     std::string old_value;
    127     if (meta_dict->GetString(key, &old_value) && old_value == value)
    128       return false;
    129   }
    130   meta_dict->SetString(key, value);
    131   serializer.Serialize(*meta_dict);
    132   std::string(meta_info_str_.data(), meta_info_str_.size()).swap(
    133       meta_info_str_);
    134   return true;
    135 }
    136 
    137 bool BookmarkNode::DeleteMetaInfo(const std::string& key) {
    138   if (meta_info_str_.empty())
    139     return false;
    140 
    141   JSONStringValueSerializer serializer(&meta_info_str_);
    142   scoped_ptr<DictionaryValue> meta_dict(
    143       static_cast<DictionaryValue*>(serializer.Deserialize(NULL, NULL)));
    144   if (meta_dict.get() && meta_dict->Remove(key, NULL)) {
    145     if (!HasValues(*meta_dict)) {
    146       meta_info_str_.clear();
    147     } else {
    148       serializer.Serialize(*meta_dict);
    149       std::string(meta_info_str_.data(), meta_info_str_.size()).swap(
    150           meta_info_str_);
    151     }
    152     return true;
    153   } else {
    154     return false;
    155   }
    156 }
    157 
    158 void BookmarkNode::Initialize(int64 id) {
    159   id_ = id;
    160   type_ = url_.is_empty() ? FOLDER : URL;
    161   date_added_ = Time::Now();
    162   favicon_state_ = INVALID_FAVICON;
    163   favicon_load_task_id_ = CancelableTaskTracker::kBadTaskId;
    164   meta_info_str_.clear();
    165 }
    166 
    167 void BookmarkNode::InvalidateFavicon() {
    168   icon_url_ = GURL();
    169   favicon_ = gfx::Image();
    170   favicon_state_ = INVALID_FAVICON;
    171 }
    172 
    173 namespace {
    174 
    175 // Comparator used when sorting bookmarks. Folders are sorted first, then
    176 // bookmarks.
    177 class SortComparator : public std::binary_function<const BookmarkNode*,
    178                                                    const BookmarkNode*,
    179                                                    bool> {
    180  public:
    181   explicit SortComparator(icu::Collator* collator) : collator_(collator) {}
    182 
    183   // Returns true if |n1| preceeds |n2|.
    184   bool operator()(const BookmarkNode* n1, const BookmarkNode* n2) {
    185     if (n1->type() == n2->type()) {
    186       // Types are the same, compare the names.
    187       if (!collator_)
    188         return n1->GetTitle() < n2->GetTitle();
    189       return base::i18n::CompareString16WithCollator(
    190           collator_, n1->GetTitle(), n2->GetTitle()) == UCOL_LESS;
    191     }
    192     // Types differ, sort such that folders come first.
    193     return n1->is_folder();
    194   }
    195 
    196  private:
    197   icu::Collator* collator_;
    198 };
    199 
    200 }  // namespace
    201 
    202 // BookmarkPermanentNode -------------------------------------------------------
    203 
    204 BookmarkPermanentNode::BookmarkPermanentNode(int64 id)
    205     : BookmarkNode(id, GURL()),
    206       visible_(true) {
    207 }
    208 
    209 BookmarkPermanentNode::~BookmarkPermanentNode() {
    210 }
    211 
    212 bool BookmarkPermanentNode::IsVisible() const {
    213   return visible_ || !empty();
    214 }
    215 
    216 // BookmarkModel --------------------------------------------------------------
    217 
    218 BookmarkModel::BookmarkModel(Profile* profile)
    219     : profile_(profile),
    220       loaded_(false),
    221       root_(GURL()),
    222       bookmark_bar_node_(NULL),
    223       other_node_(NULL),
    224       mobile_node_(NULL),
    225       next_node_id_(1),
    226       observers_(ObserverList<BookmarkModelObserver>::NOTIFY_EXISTING_ONLY),
    227       loaded_signal_(true, false),
    228       extensive_changes_(0) {
    229   if (!profile_) {
    230     // Profile is null during testing.
    231     DoneLoading(CreateLoadDetails());
    232   }
    233 }
    234 
    235 BookmarkModel::~BookmarkModel() {
    236   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    237                     BookmarkModelBeingDeleted(this));
    238 
    239   if (store_.get()) {
    240     // The store maintains a reference back to us. We need to tell it we're gone
    241     // so that it doesn't try and invoke a method back on us again.
    242     store_->BookmarkModelDeleted();
    243   }
    244 }
    245 
    246 void BookmarkModel::Shutdown() {
    247   if (loaded_)
    248     return;
    249 
    250   // See comment in HistoryService::ShutdownOnUIThread where this is invoked for
    251   // details. It is also called when the BookmarkModel is deleted.
    252   loaded_signal_.Signal();
    253 }
    254 
    255 void BookmarkModel::Load(
    256     const scoped_refptr<base::SequencedTaskRunner>& task_runner) {
    257   if (store_.get()) {
    258     // If the store is non-null, it means Load was already invoked. Load should
    259     // only be invoked once.
    260     NOTREACHED();
    261     return;
    262   }
    263 
    264   expanded_state_tracker_.reset(
    265       new BookmarkExpandedStateTracker(this, profile_->GetPrefs()));
    266 
    267   // Listen for changes to favicons so that we can update the favicon of the
    268   // node appropriately.
    269   registrar_.Add(this, chrome::NOTIFICATION_FAVICON_CHANGED,
    270                  content::Source<Profile>(profile_));
    271 
    272   // Load the bookmarks. BookmarkStorage notifies us when done.
    273   store_ = new BookmarkStorage(profile_, this, task_runner.get());
    274   store_->LoadBookmarks(CreateLoadDetails());
    275 }
    276 
    277 const BookmarkNode* BookmarkModel::GetParentForNewNodes() {
    278   std::vector<const BookmarkNode*> nodes =
    279       bookmark_utils::GetMostRecentlyModifiedFolders(this, 1);
    280   DCHECK(!nodes.empty());  // This list is always padded with default folders.
    281   return nodes[0];
    282 }
    283 
    284 void BookmarkModel::AddObserver(BookmarkModelObserver* observer) {
    285   observers_.AddObserver(observer);
    286 }
    287 
    288 void BookmarkModel::RemoveObserver(BookmarkModelObserver* observer) {
    289   observers_.RemoveObserver(observer);
    290 }
    291 
    292 void BookmarkModel::BeginExtensiveChanges() {
    293   if (++extensive_changes_ == 1) {
    294     FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    295                       ExtensiveBookmarkChangesBeginning(this));
    296   }
    297 }
    298 
    299 void BookmarkModel::EndExtensiveChanges() {
    300   --extensive_changes_;
    301   DCHECK_GE(extensive_changes_, 0);
    302   if (extensive_changes_ == 0) {
    303     FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    304                       ExtensiveBookmarkChangesEnded(this));
    305   }
    306 }
    307 
    308 void BookmarkModel::Remove(const BookmarkNode* parent, int index) {
    309   if (!loaded_ || !IsValidIndex(parent, index, false) || is_root_node(parent)) {
    310     NOTREACHED();
    311     return;
    312   }
    313   RemoveAndDeleteNode(AsMutable(parent->GetChild(index)));
    314 }
    315 
    316 void BookmarkModel::RemoveAll() {
    317   std::set<GURL> removed_urls;
    318   ScopedVector<BookmarkNode> removed_nodes;
    319 
    320   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    321                     OnWillRemoveAllBookmarks(this));
    322 
    323   BeginExtensiveChanges();
    324   // Skip deleting permanent nodes. Permanent bookmark nodes are the root and
    325   // its immediate children. For removing all non permanent nodes just remove
    326   // all children of non-root permanent nodes.
    327   {
    328     base::AutoLock url_lock(url_lock_);
    329     for (int i = 0; i < root_.child_count(); ++i) {
    330       const BookmarkNode* permanent_node = root_.GetChild(i);
    331       for (int j = permanent_node->child_count() - 1; j >= 0; --j) {
    332         BookmarkNode* child_node = AsMutable(permanent_node->GetChild(j));
    333         removed_nodes.push_back(child_node);
    334         RemoveNodeAndGetRemovedUrls(child_node, &removed_urls);
    335       }
    336     }
    337   }
    338   EndExtensiveChanges();
    339   if (store_.get())
    340     store_->ScheduleSave();
    341 
    342   NotifyHistoryAboutRemovedBookmarks(removed_urls);
    343 
    344   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    345                     BookmarkAllNodesRemoved(this));
    346 }
    347 
    348 void BookmarkModel::Move(const BookmarkNode* node,
    349                          const BookmarkNode* new_parent,
    350                          int index) {
    351   if (!loaded_ || !node || !IsValidIndex(new_parent, index, true) ||
    352       is_root_node(new_parent) || is_permanent_node(node)) {
    353     NOTREACHED();
    354     return;
    355   }
    356 
    357   if (new_parent->HasAncestor(node)) {
    358     // Can't make an ancestor of the node be a child of the node.
    359     NOTREACHED();
    360     return;
    361   }
    362 
    363   const BookmarkNode* old_parent = node->parent();
    364   int old_index = old_parent->GetIndexOf(node);
    365 
    366   if (old_parent == new_parent &&
    367       (index == old_index || index == old_index + 1)) {
    368     // Node is already in this position, nothing to do.
    369     return;
    370   }
    371 
    372   SetDateFolderModified(new_parent, Time::Now());
    373 
    374   if (old_parent == new_parent && index > old_index)
    375     index--;
    376   BookmarkNode* mutable_new_parent = AsMutable(new_parent);
    377   mutable_new_parent->Add(AsMutable(node), index);
    378 
    379   if (store_.get())
    380     store_->ScheduleSave();
    381 
    382   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    383                     BookmarkNodeMoved(this, old_parent, old_index,
    384                                       new_parent, index));
    385 }
    386 
    387 void BookmarkModel::Copy(const BookmarkNode* node,
    388                          const BookmarkNode* new_parent,
    389                          int index) {
    390   if (!loaded_ || !node || !IsValidIndex(new_parent, index, true) ||
    391       is_root_node(new_parent) || is_permanent_node(node)) {
    392     NOTREACHED();
    393     return;
    394   }
    395 
    396   if (new_parent->HasAncestor(node)) {
    397     // Can't make an ancestor of the node be a child of the node.
    398     NOTREACHED();
    399     return;
    400   }
    401 
    402   SetDateFolderModified(new_parent, Time::Now());
    403   BookmarkNodeData drag_data(node);
    404   std::vector<BookmarkNodeData::Element> elements(drag_data.elements);
    405   // CloneBookmarkNode will use BookmarkModel methods to do the job, so we
    406   // don't need to send notifications here.
    407   bookmark_utils::CloneBookmarkNode(this, elements, new_parent, index);
    408 
    409   if (store_.get())
    410     store_->ScheduleSave();
    411 }
    412 
    413 const gfx::Image& BookmarkModel::GetFavicon(const BookmarkNode* node) {
    414   DCHECK(node);
    415   if (node->favicon_state() == BookmarkNode::INVALID_FAVICON) {
    416     BookmarkNode* mutable_node = AsMutable(node);
    417     mutable_node->set_favicon_state(BookmarkNode::LOADING_FAVICON);
    418     LoadFavicon(mutable_node);
    419   }
    420   return node->favicon();
    421 }
    422 
    423 void BookmarkModel::SetTitle(const BookmarkNode* node, const string16& title) {
    424   if (!node) {
    425     NOTREACHED();
    426     return;
    427   }
    428   if (node->GetTitle() == title)
    429     return;
    430 
    431   if (is_permanent_node(node)) {
    432     NOTREACHED();
    433     return;
    434   }
    435 
    436   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    437                     OnWillChangeBookmarkNode(this, node));
    438 
    439   // The title index doesn't support changing the title, instead we remove then
    440   // add it back.
    441   index_->Remove(node);
    442   AsMutable(node)->SetTitle(title);
    443   index_->Add(node);
    444 
    445   if (store_.get())
    446     store_->ScheduleSave();
    447 
    448   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    449                     BookmarkNodeChanged(this, node));
    450 }
    451 
    452 void BookmarkModel::SetURL(const BookmarkNode* node, const GURL& url) {
    453   if (!node) {
    454     NOTREACHED();
    455     return;
    456   }
    457 
    458   // We cannot change the URL of a folder.
    459   if (node->is_folder()) {
    460     NOTREACHED();
    461     return;
    462   }
    463 
    464   if (node->url() == url)
    465     return;
    466 
    467   BookmarkNode* mutable_node = AsMutable(node);
    468   mutable_node->InvalidateFavicon();
    469   CancelPendingFaviconLoadRequests(mutable_node);
    470 
    471   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    472                     OnWillChangeBookmarkNode(this, node));
    473 
    474   {
    475     base::AutoLock url_lock(url_lock_);
    476     NodesOrderedByURLSet::iterator i = nodes_ordered_by_url_set_.find(
    477         mutable_node);
    478     DCHECK(i != nodes_ordered_by_url_set_.end());
    479     // i points to the first node with the URL, advance until we find the
    480     // node we're removing.
    481     while (*i != node)
    482       ++i;
    483     nodes_ordered_by_url_set_.erase(i);
    484 
    485     mutable_node->set_url(url);
    486     nodes_ordered_by_url_set_.insert(mutable_node);
    487   }
    488 
    489   if (store_.get())
    490     store_->ScheduleSave();
    491 
    492   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    493                     BookmarkNodeChanged(this, node));
    494 }
    495 
    496 void BookmarkModel::SetNodeMetaInfo(const BookmarkNode* node,
    497                                     const std::string& key,
    498                                     const std::string& value) {
    499   if (AsMutable(node)->SetMetaInfo(key, value) && store_.get())
    500     store_->ScheduleSave();
    501 }
    502 
    503 void BookmarkModel::DeleteNodeMetaInfo(const BookmarkNode* node,
    504                                        const std::string& key) {
    505   if (AsMutable(node)->DeleteMetaInfo(key) && store_.get())
    506     store_->ScheduleSave();
    507 }
    508 
    509 void BookmarkModel::SetDateAdded(const BookmarkNode* node,
    510                                  base::Time date_added) {
    511   if (!node) {
    512     NOTREACHED();
    513     return;
    514   }
    515 
    516   if (node->date_added() == date_added)
    517     return;
    518 
    519   if (is_permanent_node(node)) {
    520     NOTREACHED();
    521     return;
    522   }
    523 
    524   AsMutable(node)->set_date_added(date_added);
    525 
    526   // Syncing might result in dates newer than the folder's last modified date.
    527   if (date_added > node->parent()->date_folder_modified()) {
    528     // Will trigger store_->ScheduleSave().
    529     SetDateFolderModified(node->parent(), date_added);
    530   } else if (store_.get()) {
    531     store_->ScheduleSave();
    532   }
    533 }
    534 
    535 void BookmarkModel::GetNodesByURL(const GURL& url,
    536                                   std::vector<const BookmarkNode*>* nodes) {
    537   base::AutoLock url_lock(url_lock_);
    538   BookmarkNode tmp_node(url);
    539   NodesOrderedByURLSet::iterator i = nodes_ordered_by_url_set_.find(&tmp_node);
    540   while (i != nodes_ordered_by_url_set_.end() && (*i)->url() == url) {
    541     nodes->push_back(*i);
    542     ++i;
    543   }
    544 }
    545 
    546 const BookmarkNode* BookmarkModel::GetMostRecentlyAddedNodeForURL(
    547     const GURL& url) {
    548   std::vector<const BookmarkNode*> nodes;
    549   GetNodesByURL(url, &nodes);
    550   if (nodes.empty())
    551     return NULL;
    552 
    553   std::sort(nodes.begin(), nodes.end(), &bookmark_utils::MoreRecentlyAdded);
    554   return nodes.front();
    555 }
    556 
    557 bool BookmarkModel::HasBookmarks() {
    558   base::AutoLock url_lock(url_lock_);
    559   return !nodes_ordered_by_url_set_.empty();
    560 }
    561 
    562 bool BookmarkModel::IsBookmarked(const GURL& url) {
    563   base::AutoLock url_lock(url_lock_);
    564   return IsBookmarkedNoLock(url);
    565 }
    566 
    567 void BookmarkModel::GetBookmarks(
    568     std::vector<BookmarkService::URLAndTitle>* bookmarks) {
    569   base::AutoLock url_lock(url_lock_);
    570   const GURL* last_url = NULL;
    571   for (NodesOrderedByURLSet::iterator i = nodes_ordered_by_url_set_.begin();
    572        i != nodes_ordered_by_url_set_.end(); ++i) {
    573     const GURL* url = &((*i)->url());
    574     // Only add unique URLs.
    575     if (!last_url || *url != *last_url) {
    576       BookmarkService::URLAndTitle bookmark;
    577       bookmark.url = *url;
    578       bookmark.title = (*i)->GetTitle();
    579       bookmarks->push_back(bookmark);
    580     }
    581     last_url = url;
    582   }
    583 }
    584 
    585 void BookmarkModel::BlockTillLoaded() {
    586   loaded_signal_.Wait();
    587 }
    588 
    589 const BookmarkNode* BookmarkModel::GetNodeByID(int64 id) const {
    590   // TODO(sky): TreeNode needs a method that visits all nodes using a predicate.
    591   return GetNodeByID(&root_, id);
    592 }
    593 
    594 const BookmarkNode* BookmarkModel::AddFolder(const BookmarkNode* parent,
    595                                              int index,
    596                                              const string16& title) {
    597   if (!loaded_ || is_root_node(parent) || !IsValidIndex(parent, index, true)) {
    598     // Can't add to the root.
    599     NOTREACHED();
    600     return NULL;
    601   }
    602 
    603   BookmarkNode* new_node = new BookmarkNode(generate_next_node_id(), GURL());
    604   new_node->set_date_folder_modified(Time::Now());
    605   // Folders shouldn't have line breaks in their titles.
    606   new_node->SetTitle(title);
    607   new_node->set_type(BookmarkNode::FOLDER);
    608 
    609   return AddNode(AsMutable(parent), index, new_node);
    610 }
    611 
    612 const BookmarkNode* BookmarkModel::AddURL(const BookmarkNode* parent,
    613                                           int index,
    614                                           const string16& title,
    615                                           const GURL& url) {
    616   return AddURLWithCreationTime(parent, index,
    617                                 CollapseWhitespace(title, false),
    618                                 url, Time::Now());
    619 }
    620 
    621 const BookmarkNode* BookmarkModel::AddURLWithCreationTime(
    622     const BookmarkNode* parent,
    623     int index,
    624     const string16& title,
    625     const GURL& url,
    626     const Time& creation_time) {
    627   if (!loaded_ || !url.is_valid() || is_root_node(parent) ||
    628       !IsValidIndex(parent, index, true)) {
    629     NOTREACHED();
    630     return NULL;
    631   }
    632 
    633   // Syncing may result in dates newer than the last modified date.
    634   if (creation_time > parent->date_folder_modified())
    635     SetDateFolderModified(parent, creation_time);
    636 
    637   BookmarkNode* new_node = new BookmarkNode(generate_next_node_id(), url);
    638   new_node->SetTitle(title);
    639   new_node->set_date_added(creation_time);
    640   new_node->set_type(BookmarkNode::URL);
    641 
    642   {
    643     // Only hold the lock for the duration of the insert.
    644     base::AutoLock url_lock(url_lock_);
    645     nodes_ordered_by_url_set_.insert(new_node);
    646   }
    647 
    648   return AddNode(AsMutable(parent), index, new_node);
    649 }
    650 
    651 void BookmarkModel::SortChildren(const BookmarkNode* parent) {
    652   if (!parent || !parent->is_folder() || is_root_node(parent) ||
    653       parent->child_count() <= 1) {
    654     return;
    655   }
    656 
    657   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    658                     OnWillReorderBookmarkNode(this, parent));
    659 
    660   UErrorCode error = U_ZERO_ERROR;
    661   scoped_ptr<icu::Collator> collator(icu::Collator::createInstance(error));
    662   if (U_FAILURE(error))
    663     collator.reset(NULL);
    664   BookmarkNode* mutable_parent = AsMutable(parent);
    665   std::sort(mutable_parent->children().begin(),
    666             mutable_parent->children().end(),
    667             SortComparator(collator.get()));
    668 
    669   if (store_.get())
    670     store_->ScheduleSave();
    671 
    672   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    673                     BookmarkNodeChildrenReordered(this, parent));
    674 }
    675 
    676 void BookmarkModel::ReorderChildren(
    677     const BookmarkNode* parent,
    678     const std::vector<const BookmarkNode*>& ordered_nodes) {
    679   // Ensure that all children in |parent| are in |ordered_nodes|.
    680   DCHECK_EQ(static_cast<size_t>(parent->child_count()), ordered_nodes.size());
    681   for (size_t i = 0; i < ordered_nodes.size(); ++i)
    682     DCHECK_EQ(parent, ordered_nodes[i]->parent());
    683 
    684   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    685                     OnWillReorderBookmarkNode(this, parent));
    686 
    687   AsMutable(parent)->SetChildren(
    688       *(reinterpret_cast<const std::vector<BookmarkNode*>*>(&ordered_nodes)));
    689 
    690   if (store_.get())
    691     store_->ScheduleSave();
    692 
    693   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    694                     BookmarkNodeChildrenReordered(this, parent));
    695 }
    696 
    697 void BookmarkModel::SetDateFolderModified(const BookmarkNode* parent,
    698                                           const Time time) {
    699   DCHECK(parent);
    700   AsMutable(parent)->set_date_folder_modified(time);
    701 
    702   if (store_.get())
    703     store_->ScheduleSave();
    704 }
    705 
    706 void BookmarkModel::ResetDateFolderModified(const BookmarkNode* node) {
    707   SetDateFolderModified(node, Time());
    708 }
    709 
    710 void BookmarkModel::GetBookmarksWithTitlesMatching(
    711     const string16& text,
    712     size_t max_count,
    713     std::vector<BookmarkTitleMatch>* matches) {
    714   if (!loaded_)
    715     return;
    716 
    717   index_->GetBookmarksWithTitlesMatching(text, max_count, matches);
    718 }
    719 
    720 void BookmarkModel::ClearStore() {
    721   registrar_.RemoveAll();
    722   store_ = NULL;
    723 }
    724 
    725 void BookmarkModel::SetPermanentNodeVisible(BookmarkNode::Type type,
    726                                             bool value) {
    727   DCHECK(loaded_);
    728   switch (type) {
    729     case BookmarkNode::BOOKMARK_BAR:
    730       bookmark_bar_node_->set_visible(value);
    731       break;
    732     case BookmarkNode::OTHER_NODE:
    733       other_node_->set_visible(value);
    734       break;
    735     case BookmarkNode::MOBILE:
    736       mobile_node_->set_visible(value);
    737       break;
    738     default:
    739       NOTREACHED();
    740   }
    741 }
    742 
    743 bool BookmarkModel::IsBookmarkedNoLock(const GURL& url) {
    744   BookmarkNode tmp_node(url);
    745   return (nodes_ordered_by_url_set_.find(&tmp_node) !=
    746           nodes_ordered_by_url_set_.end());
    747 }
    748 
    749 void BookmarkModel::RemoveNode(BookmarkNode* node,
    750                                std::set<GURL>* removed_urls) {
    751   if (!loaded_ || !node || is_permanent_node(node)) {
    752     NOTREACHED();
    753     return;
    754   }
    755 
    756   url_lock_.AssertAcquired();
    757   if (node->is_url()) {
    758     // NOTE: this is called in such a way that url_lock_ is already held. As
    759     // such, this doesn't explicitly grab the lock.
    760     NodesOrderedByURLSet::iterator i = nodes_ordered_by_url_set_.find(node);
    761     DCHECK(i != nodes_ordered_by_url_set_.end());
    762     // i points to the first node with the URL, advance until we find the
    763     // node we're removing.
    764     while (*i != node)
    765       ++i;
    766     nodes_ordered_by_url_set_.erase(i);
    767     removed_urls->insert(node->url());
    768 
    769     index_->Remove(node);
    770   }
    771 
    772   CancelPendingFaviconLoadRequests(node);
    773 
    774   // Recurse through children.
    775   for (int i = node->child_count() - 1; i >= 0; --i)
    776     RemoveNode(node->GetChild(i), removed_urls);
    777 }
    778 
    779 void BookmarkModel::DoneLoading(BookmarkLoadDetails* details_delete_me) {
    780   DCHECK(details_delete_me);
    781   scoped_ptr<BookmarkLoadDetails> details(details_delete_me);
    782   if (loaded_) {
    783     // We should only ever be loaded once.
    784     NOTREACHED();
    785     return;
    786   }
    787 
    788   next_node_id_ = details->max_id();
    789   if (details->computed_checksum() != details->stored_checksum() ||
    790       details->ids_reassigned()) {
    791     // If bookmarks file changed externally, the IDs may have changed
    792     // externally. In that case, the decoder may have reassigned IDs to make
    793     // them unique. So when the file has changed externally, we should save the
    794     // bookmarks file to persist new IDs.
    795     if (store_.get())
    796       store_->ScheduleSave();
    797   }
    798   bookmark_bar_node_ = details->release_bb_node();
    799   other_node_ = details->release_other_folder_node();
    800   mobile_node_ = details->release_mobile_folder_node();
    801   index_.reset(details->release_index());
    802 
    803   // WARNING: order is important here, various places assume the order is
    804   // constant.
    805   root_.Add(bookmark_bar_node_, 0);
    806   root_.Add(other_node_, 1);
    807   root_.Add(mobile_node_, 2);
    808 
    809   root_.set_meta_info_str(details->model_meta_info());
    810 
    811   {
    812     base::AutoLock url_lock(url_lock_);
    813     // Update nodes_ordered_by_url_set_ from the nodes.
    814     PopulateNodesByURL(&root_);
    815   }
    816 
    817   loaded_ = true;
    818 
    819   loaded_signal_.Signal();
    820 
    821   // Notify our direct observers.
    822   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    823                     Loaded(this, details->ids_reassigned()));
    824 }
    825 
    826 void BookmarkModel::RemoveAndDeleteNode(BookmarkNode* delete_me) {
    827   scoped_ptr<BookmarkNode> node(delete_me);
    828 
    829   const BookmarkNode* parent = node->parent();
    830   DCHECK(parent);
    831   int index = parent->GetIndexOf(node.get());
    832 
    833   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    834                     OnWillRemoveBookmarks(this, parent, index, node.get()));
    835 
    836   std::set<GURL> removed_urls;
    837   {
    838     base::AutoLock url_lock(url_lock_);
    839     RemoveNodeAndGetRemovedUrls(node.get(), &removed_urls);
    840   }
    841 
    842   if (store_.get())
    843     store_->ScheduleSave();
    844 
    845   NotifyHistoryAboutRemovedBookmarks(removed_urls);
    846 
    847   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    848                     BookmarkNodeRemoved(this, parent, index, node.get()));
    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 void BookmarkModel::NotifyHistoryAboutRemovedBookmarks(
    878     const std::set<GURL>& removed_bookmark_urls) const {
    879   if (removed_bookmark_urls.empty()) {
    880     // No point in sending out notification if the starred state didn't change.
    881     return;
    882   }
    883 
    884   if (profile_) {
    885     HistoryService* history =
    886         HistoryServiceFactory::GetForProfile(profile_,
    887                                              Profile::EXPLICIT_ACCESS);
    888     if (history)
    889       history->URLsNoLongerBookmarked(removed_bookmark_urls);
    890   }
    891 }
    892 
    893 BookmarkNode* BookmarkModel::AddNode(BookmarkNode* parent,
    894                                      int index,
    895                                      BookmarkNode* node) {
    896   parent->Add(node, index);
    897 
    898   if (store_.get())
    899     store_->ScheduleSave();
    900 
    901   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    902                     BookmarkNodeAdded(this, parent, index));
    903 
    904   index_->Add(node);
    905 
    906   return node;
    907 }
    908 
    909 const BookmarkNode* BookmarkModel::GetNodeByID(const BookmarkNode* node,
    910                                                int64 id) const {
    911   if (node->id() == id)
    912     return node;
    913 
    914   for (int i = 0, child_count = node->child_count(); i < child_count; ++i) {
    915     const BookmarkNode* result = GetNodeByID(node->GetChild(i), id);
    916     if (result)
    917       return result;
    918   }
    919   return NULL;
    920 }
    921 
    922 bool BookmarkModel::IsValidIndex(const BookmarkNode* parent,
    923                                  int index,
    924                                  bool allow_end) {
    925   return (parent && parent->is_folder() &&
    926           (index >= 0 && (index < parent->child_count() ||
    927                           (allow_end && index == parent->child_count()))));
    928 }
    929 
    930 BookmarkPermanentNode* BookmarkModel::CreatePermanentNode(
    931     BookmarkNode::Type type) {
    932   DCHECK(type == BookmarkNode::BOOKMARK_BAR ||
    933          type == BookmarkNode::OTHER_NODE ||
    934          type == BookmarkNode::MOBILE);
    935   BookmarkPermanentNode* node =
    936       new BookmarkPermanentNode(generate_next_node_id());
    937   if (type == BookmarkNode::MOBILE)
    938     node->set_visible(false);  // Mobile node is initially hidden.
    939 
    940   int title_id;
    941   switch (type) {
    942     case BookmarkNode::BOOKMARK_BAR:
    943       title_id = IDS_BOOKMARK_BAR_FOLDER_NAME;
    944       break;
    945     case BookmarkNode::OTHER_NODE:
    946       title_id = IDS_BOOKMARK_BAR_OTHER_FOLDER_NAME;
    947       break;
    948     case BookmarkNode::MOBILE:
    949       title_id = IDS_BOOKMARK_BAR_MOBILE_FOLDER_NAME;
    950       break;
    951     default:
    952       NOTREACHED();
    953       title_id = IDS_BOOKMARK_BAR_FOLDER_NAME;
    954       break;
    955   }
    956   node->SetTitle(l10n_util::GetStringUTF16(title_id));
    957   node->set_type(type);
    958   return node;
    959 }
    960 
    961 void BookmarkModel::OnFaviconDataAvailable(
    962     BookmarkNode* node,
    963     const chrome::FaviconImageResult& image_result) {
    964   DCHECK(node);
    965   node->set_favicon_load_task_id(CancelableTaskTracker::kBadTaskId);
    966   node->set_favicon_state(BookmarkNode::LOADED_FAVICON);
    967   if (!image_result.image.IsEmpty()) {
    968     node->set_favicon(image_result.image);
    969     node->set_icon_url(image_result.icon_url);
    970     FaviconLoaded(node);
    971   }
    972 }
    973 
    974 void BookmarkModel::LoadFavicon(BookmarkNode* node) {
    975   if (node->is_folder())
    976     return;
    977 
    978   DCHECK(node->url().is_valid());
    979   FaviconService* favicon_service = FaviconServiceFactory::GetForProfile(
    980       profile_, Profile::EXPLICIT_ACCESS);
    981   if (!favicon_service)
    982     return;
    983   FaviconService::Handle handle = favicon_service->GetFaviconImageForURL(
    984       FaviconService::FaviconForURLParams(profile_,
    985                                           node->url(),
    986                                           chrome::FAVICON,
    987                                           gfx::kFaviconSize),
    988       base::Bind(&BookmarkModel::OnFaviconDataAvailable,
    989                  base::Unretained(this), node),
    990       &cancelable_task_tracker_);
    991   node->set_favicon_load_task_id(handle);
    992 }
    993 
    994 void BookmarkModel::FaviconLoaded(const BookmarkNode* node) {
    995   FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
    996                     BookmarkNodeFaviconChanged(this, node));
    997 }
    998 
    999 void BookmarkModel::CancelPendingFaviconLoadRequests(BookmarkNode* node) {
   1000   if (node->favicon_load_task_id() != CancelableTaskTracker::kBadTaskId) {
   1001     cancelable_task_tracker_.TryCancel(node->favicon_load_task_id());
   1002     node->set_favicon_load_task_id(CancelableTaskTracker::kBadTaskId);
   1003   }
   1004 }
   1005 
   1006 void BookmarkModel::Observe(int type,
   1007                             const content::NotificationSource& source,
   1008                             const content::NotificationDetails& details) {
   1009   switch (type) {
   1010     case chrome::NOTIFICATION_FAVICON_CHANGED: {
   1011       // Prevent the observers from getting confused for multiple favicon loads.
   1012       content::Details<FaviconChangedDetails> favicon_details(details);
   1013       for (std::set<GURL>::const_iterator i = favicon_details->urls.begin();
   1014            i != favicon_details->urls.end(); ++i) {
   1015         std::vector<const BookmarkNode*> nodes;
   1016         GetNodesByURL(*i, &nodes);
   1017         for (size_t i = 0; i < nodes.size(); ++i) {
   1018           // Got an updated favicon, for a URL, do a new request.
   1019           BookmarkNode* node = AsMutable(nodes[i]);
   1020           node->InvalidateFavicon();
   1021           CancelPendingFaviconLoadRequests(node);
   1022           FOR_EACH_OBSERVER(BookmarkModelObserver, observers_,
   1023                             BookmarkNodeFaviconChanged(this, node));
   1024         }
   1025       }
   1026       break;
   1027     }
   1028 
   1029     default:
   1030       NOTREACHED();
   1031       break;
   1032   }
   1033 }
   1034 
   1035 void BookmarkModel::PopulateNodesByURL(BookmarkNode* node) {
   1036   // NOTE: this is called with url_lock_ already held. As such, this doesn't
   1037   // explicitly grab the lock.
   1038   if (node->is_url())
   1039     nodes_ordered_by_url_set_.insert(node);
   1040   for (int i = 0; i < node->child_count(); ++i)
   1041     PopulateNodesByURL(node->GetChild(i));
   1042 }
   1043 
   1044 int64 BookmarkModel::generate_next_node_id() {
   1045   return next_node_id_++;
   1046 }
   1047 
   1048 BookmarkLoadDetails* BookmarkModel::CreateLoadDetails() {
   1049   BookmarkPermanentNode* bb_node =
   1050       CreatePermanentNode(BookmarkNode::BOOKMARK_BAR);
   1051   BookmarkPermanentNode* other_node =
   1052       CreatePermanentNode(BookmarkNode::OTHER_NODE);
   1053   BookmarkPermanentNode* mobile_node =
   1054       CreatePermanentNode(BookmarkNode::MOBILE);
   1055   return new BookmarkLoadDetails(bb_node, other_node, mobile_node,
   1056                                  new BookmarkIndex(profile_),
   1057                                  next_node_id_);
   1058 }
   1059