bookmark_model_associator.cc revision 3345a6884c488ff3a535c2c9acdd33d74b37e311
1// Copyright (c) 2010 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include "chrome/browser/sync/glue/bookmark_model_associator.h" 6 7#include <stack> 8 9#include "base/hash_tables.h" 10#include "base/message_loop.h" 11#include "base/task.h" 12#include "base/utf_string_conversions.h" 13#include "chrome/browser/bookmarks/bookmark_model.h" 14#include "chrome/browser/chrome_thread.h" 15#include "chrome/browser/profile.h" 16#include "chrome/browser/sync/engine/syncapi.h" 17#include "chrome/browser/sync/glue/bookmark_change_processor.h" 18#include "chrome/browser/sync/profile_sync_service.h" 19 20namespace browser_sync { 21 22// The sync protocol identifies top-level entities by means of well-known tags, 23// which should not be confused with titles. Each tag corresponds to a 24// singleton instance of a particular top-level node in a user's share; the 25// tags are consistent across users. The tags allow us to locate the specific 26// folders whose contents we care about synchronizing, without having to do a 27// lookup by name or path. The tags should not be made user-visible. 28// For example, the tag "bookmark_bar" represents the permanent node for 29// bookmarks bar in Chrome. The tag "other_bookmarks" represents the permanent 30// folder Other Bookmarks in Chrome. 31// 32// It is the responsibility of something upstream (at time of writing, 33// the sync server) to create these tagged nodes when initializing sync 34// for the first time for a user. Thus, once the backend finishes 35// initializing, the ProfileSyncService can rely on the presence of tagged 36// nodes. 37// 38// TODO(ncarter): Pull these tags from an external protocol specification 39// rather than hardcoding them here. 40static const char kBookmarkBarTag[] = "bookmark_bar"; 41static const char kOtherBookmarksTag[] = "other_bookmarks"; 42 43// Bookmark comparer for map of bookmark nodes. 44class BookmarkComparer { 45 public: 46 // Compares the two given nodes and returns whether node1 should appear 47 // before node2 in strict weak ordering. 48 bool operator()(const BookmarkNode* node1, 49 const BookmarkNode* node2) const { 50 DCHECK(node1); 51 DCHECK(node2); 52 53 // Keep folder nodes before non-folder nodes. 54 if (node1->is_folder() != node2->is_folder()) 55 return node1->is_folder(); 56 57 int result = node1->GetTitle().compare(node2->GetTitle()); 58 if (result != 0) 59 return result < 0; 60 61 return node1->GetURL() < node2->GetURL(); 62 } 63}; 64 65// Provides the following abstraction: given a parent bookmark node, find best 66// matching child node for many sync nodes. 67class BookmarkNodeFinder { 68 public: 69 // Creates an instance with the given parent bookmark node. 70 explicit BookmarkNodeFinder(const BookmarkNode* parent_node); 71 72 // Finds best matching node for the given sync node. 73 // Returns the matching node if one exists; NULL otherwise. If a matching 74 // node is found, it's removed for further matches. 75 const BookmarkNode* FindBookmarkNode(const sync_api::BaseNode& sync_node); 76 77 private: 78 typedef std::multiset<const BookmarkNode*, BookmarkComparer> BookmarkNodesSet; 79 80 const BookmarkNode* parent_node_; 81 BookmarkNodesSet child_nodes_; 82 83 DISALLOW_COPY_AND_ASSIGN(BookmarkNodeFinder); 84}; 85 86BookmarkNodeFinder::BookmarkNodeFinder(const BookmarkNode* parent_node) 87 : parent_node_(parent_node) { 88 for (int i = 0; i < parent_node_->GetChildCount(); ++i) { 89 child_nodes_.insert(parent_node_->GetChild(i)); 90 } 91} 92 93const BookmarkNode* BookmarkNodeFinder::FindBookmarkNode( 94 const sync_api::BaseNode& sync_node) { 95 // Create a bookmark node from the given sync node. 96 BookmarkNode temp_node(sync_node.GetURL()); 97 temp_node.SetTitle(WideToUTF16Hack(sync_node.GetTitle())); 98 if (sync_node.GetIsFolder()) 99 temp_node.set_type(BookmarkNode::FOLDER); 100 else 101 temp_node.set_type(BookmarkNode::URL); 102 103 const BookmarkNode* result = NULL; 104 BookmarkNodesSet::iterator iter = child_nodes_.find(&temp_node); 105 if (iter != child_nodes_.end()) { 106 result = *iter; 107 // Remove the matched node so we don't match with it again. 108 child_nodes_.erase(iter); 109 } 110 111 return result; 112} 113 114// Helper class to build an index of bookmark nodes by their IDs. 115class BookmarkNodeIdIndex { 116 public: 117 BookmarkNodeIdIndex() { } 118 ~BookmarkNodeIdIndex() { } 119 120 // Adds the given bookmark node and all its descendants to the ID index. 121 // Does nothing if node is NULL. 122 void AddAll(const BookmarkNode* node); 123 124 // Finds the bookmark node with the given ID. 125 // Returns NULL if none exists with the given id. 126 const BookmarkNode* Find(int64 id) const; 127 128 // Returns the count of nodes in the index. 129 size_t count() const { return node_index_.size(); } 130 131 private: 132 typedef base::hash_map<int64, const BookmarkNode*> BookmarkIdMap; 133 // Map that holds nodes indexed by their ids. 134 BookmarkIdMap node_index_; 135 136 DISALLOW_COPY_AND_ASSIGN(BookmarkNodeIdIndex); 137}; 138 139void BookmarkNodeIdIndex::AddAll(const BookmarkNode* node) { 140 if (!node) 141 return; 142 143 node_index_[node->id()] = node; 144 145 if (!node->is_folder()) 146 return; 147 148 for (int i = 0; i < node->GetChildCount(); ++i) 149 AddAll(node->GetChild(i)); 150} 151 152const BookmarkNode* BookmarkNodeIdIndex::Find(int64 id) const { 153 BookmarkIdMap::const_iterator iter = node_index_.find(id); 154 return iter == node_index_.end() ? NULL : iter->second; 155} 156 157BookmarkModelAssociator::BookmarkModelAssociator( 158 ProfileSyncService* sync_service, 159 UnrecoverableErrorHandler* persist_ids_error_handler) 160 : sync_service_(sync_service), 161 persist_ids_error_handler_(persist_ids_error_handler), 162 ALLOW_THIS_IN_INITIALIZER_LIST(persist_associations_(this)) { 163 DCHECK(ChromeThread::CurrentlyOn(ChromeThread::UI)); 164 DCHECK(sync_service_); 165 DCHECK(persist_ids_error_handler_); 166} 167 168BookmarkModelAssociator::~BookmarkModelAssociator() { 169 DCHECK(ChromeThread::CurrentlyOn(ChromeThread::UI)); 170} 171 172bool BookmarkModelAssociator::DisassociateModels() { 173 id_map_.clear(); 174 id_map_inverse_.clear(); 175 dirty_associations_sync_ids_.clear(); 176 return true; 177} 178 179int64 BookmarkModelAssociator::GetSyncIdFromChromeId(int64 node_id) { 180 BookmarkIdToSyncIdMap::const_iterator iter = id_map_.find(node_id); 181 return iter == id_map_.end() ? sync_api::kInvalidId : iter->second; 182} 183 184const BookmarkNode* BookmarkModelAssociator::GetChromeNodeFromSyncId( 185 int64 sync_id) { 186 SyncIdToBookmarkNodeMap::const_iterator iter = id_map_inverse_.find(sync_id); 187 return iter == id_map_inverse_.end() ? NULL : iter->second; 188} 189 190bool BookmarkModelAssociator::InitSyncNodeFromChromeId( 191 int64 node_id, 192 sync_api::BaseNode* sync_node) { 193 DCHECK(sync_node); 194 int64 sync_id = GetSyncIdFromChromeId(node_id); 195 if (sync_id == sync_api::kInvalidId) 196 return false; 197 if (!sync_node->InitByIdLookup(sync_id)) 198 return false; 199 DCHECK(sync_node->GetId() == sync_id); 200 return true; 201} 202 203void BookmarkModelAssociator::Associate(const BookmarkNode* node, 204 int64 sync_id) { 205 DCHECK(ChromeThread::CurrentlyOn(ChromeThread::UI)); 206 int64 node_id = node->id(); 207 DCHECK_NE(sync_id, sync_api::kInvalidId); 208 DCHECK(id_map_.find(node_id) == id_map_.end()); 209 DCHECK(id_map_inverse_.find(sync_id) == id_map_inverse_.end()); 210 id_map_[node_id] = sync_id; 211 id_map_inverse_[sync_id] = node; 212 dirty_associations_sync_ids_.insert(sync_id); 213 PostPersistAssociationsTask(); 214} 215 216void BookmarkModelAssociator::Disassociate(int64 sync_id) { 217 DCHECK(ChromeThread::CurrentlyOn(ChromeThread::UI)); 218 SyncIdToBookmarkNodeMap::iterator iter = id_map_inverse_.find(sync_id); 219 if (iter == id_map_inverse_.end()) 220 return; 221 id_map_.erase(iter->second->id()); 222 id_map_inverse_.erase(iter); 223 dirty_associations_sync_ids_.erase(sync_id); 224} 225 226bool BookmarkModelAssociator::SyncModelHasUserCreatedNodes(bool* has_nodes) { 227 DCHECK(has_nodes); 228 *has_nodes = false; 229 int64 bookmark_bar_sync_id; 230 if (!GetSyncIdForTaggedNode(kBookmarkBarTag, &bookmark_bar_sync_id)) { 231 return false; 232 } 233 int64 other_bookmarks_sync_id; 234 if (!GetSyncIdForTaggedNode(kOtherBookmarksTag, &other_bookmarks_sync_id)) { 235 return false; 236 } 237 238 sync_api::ReadTransaction trans( 239 sync_service_->backend()->GetUserShareHandle()); 240 241 sync_api::ReadNode bookmark_bar_node(&trans); 242 if (!bookmark_bar_node.InitByIdLookup(bookmark_bar_sync_id)) { 243 return false; 244 } 245 246 sync_api::ReadNode other_bookmarks_node(&trans); 247 if (!other_bookmarks_node.InitByIdLookup(other_bookmarks_sync_id)) { 248 return false; 249 } 250 251 // Sync model has user created nodes if either one of the permanent nodes 252 // has children. 253 *has_nodes = bookmark_bar_node.GetFirstChildId() != sync_api::kInvalidId || 254 other_bookmarks_node.GetFirstChildId() != sync_api::kInvalidId; 255 return true; 256} 257 258bool BookmarkModelAssociator::NodesMatch(const BookmarkNode* bookmark, 259 const sync_api::BaseNode* sync_node) const { 260 if (bookmark->GetTitle() != WideToUTF16Hack(sync_node->GetTitle())) 261 return false; 262 if (bookmark->is_folder() != sync_node->GetIsFolder()) 263 return false; 264 if (bookmark->is_url()) { 265 if (bookmark->GetURL() != sync_node->GetURL()) 266 return false; 267 } 268 // Don't compare favicons here, because they are not really 269 // user-updated and we don't have versioning information -- a site changing 270 // its favicon shouldn't result in a bookmark mismatch. 271 return true; 272} 273 274bool BookmarkModelAssociator::AssociateTaggedPermanentNode( 275 const BookmarkNode* permanent_node, const std::string&tag) { 276 // Do nothing if |permanent_node| is already initialized and associated. 277 int64 sync_id = GetSyncIdFromChromeId(permanent_node->id()); 278 if (sync_id != sync_api::kInvalidId) 279 return true; 280 if (!GetSyncIdForTaggedNode(tag, &sync_id)) 281 return false; 282 283 Associate(permanent_node, sync_id); 284 return true; 285} 286 287bool BookmarkModelAssociator::GetSyncIdForTaggedNode(const std::string& tag, 288 int64* sync_id) { 289 sync_api::ReadTransaction trans( 290 sync_service_->backend()->GetUserShareHandle()); 291 sync_api::ReadNode sync_node(&trans); 292 if (!sync_node.InitByTagLookup(tag.c_str())) 293 return false; 294 *sync_id = sync_node.GetId(); 295 return true; 296} 297 298bool BookmarkModelAssociator::AssociateModels() { 299 // Try to load model associations from persisted associations first. If that 300 // succeeds, we don't need to run the complex model matching algorithm. 301 if (LoadAssociations()) 302 return true; 303 304 DisassociateModels(); 305 306 // We couldn't load model associations from persisted associations. So build 307 // them. 308 return BuildAssociations(); 309} 310 311bool BookmarkModelAssociator::BuildAssociations() { 312 // Algorithm description: 313 // Match up the roots and recursively do the following: 314 // * For each sync node for the current sync parent node, find the best 315 // matching bookmark node under the corresponding bookmark parent node. 316 // If no matching node is found, create a new bookmark node in the same 317 // position as the corresponding sync node. 318 // If a matching node is found, update the properties of it from the 319 // corresponding sync node. 320 // * When all children sync nodes are done, add the extra children bookmark 321 // nodes to the sync parent node. 322 // 323 // This algorithm will do a good job of merging when folder names are a good 324 // indicator of the two folders being the same. It will handle reordering and 325 // new node addition very well (without creating duplicates). 326 // This algorithm will not do well if the folder name has changes but the 327 // children under them are all the same. 328 329 BookmarkModel* model = sync_service_->profile()->GetBookmarkModel(); 330 DCHECK(model->IsLoaded()); 331 332 // To prime our association, we associate the top-level nodes, Bookmark Bar 333 // and Other Bookmarks. 334 if (!AssociateTaggedPermanentNode(model->other_node(), kOtherBookmarksTag)) { 335 LOG(ERROR) << "Server did not create top-level nodes. Possibly we " 336 << "are running against an out-of-date server?"; 337 return false; 338 } 339 if (!AssociateTaggedPermanentNode(model->GetBookmarkBarNode(), 340 kBookmarkBarTag)) { 341 LOG(ERROR) << "Server did not create top-level nodes. Possibly we " 342 << "are running against an out-of-date server?"; 343 return false; 344 } 345 int64 bookmark_bar_sync_id = GetSyncIdFromChromeId( 346 model->GetBookmarkBarNode()->id()); 347 DCHECK(bookmark_bar_sync_id != sync_api::kInvalidId); 348 int64 other_bookmarks_sync_id = GetSyncIdFromChromeId( 349 model->other_node()->id()); 350 DCHECK(other_bookmarks_sync_id != sync_api::kInvalidId); 351 352 std::stack<int64> dfs_stack; 353 dfs_stack.push(other_bookmarks_sync_id); 354 dfs_stack.push(bookmark_bar_sync_id); 355 356 sync_api::WriteTransaction trans( 357 sync_service_->backend()->GetUserShareHandle()); 358 359 while (!dfs_stack.empty()) { 360 int64 sync_parent_id = dfs_stack.top(); 361 dfs_stack.pop(); 362 363 sync_api::ReadNode sync_parent(&trans); 364 if (!sync_parent.InitByIdLookup(sync_parent_id)) { 365 return false; 366 } 367 // Only folder nodes are pushed on to the stack. 368 DCHECK(sync_parent.GetIsFolder()); 369 370 const BookmarkNode* parent_node = GetChromeNodeFromSyncId(sync_parent_id); 371 DCHECK(parent_node->is_folder()); 372 373 BookmarkNodeFinder node_finder(parent_node); 374 375 int index = 0; 376 int64 sync_child_id = sync_parent.GetFirstChildId(); 377 while (sync_child_id != sync_api::kInvalidId) { 378 sync_api::WriteNode sync_child_node(&trans); 379 if (!sync_child_node.InitByIdLookup(sync_child_id)) { 380 return false; 381 } 382 383 const BookmarkNode* child_node = NULL; 384 child_node = node_finder.FindBookmarkNode(sync_child_node); 385 if (child_node) { 386 model->Move(child_node, parent_node, index); 387 // Set the favicon for bookmark node from sync node or vice versa. 388 if (BookmarkChangeProcessor::SetBookmarkFavicon( 389 &sync_child_node, child_node, sync_service_->profile())) { 390 BookmarkChangeProcessor::SetSyncNodeFavicon(child_node, model, 391 &sync_child_node); 392 } 393 } else { 394 // Create a new bookmark node for the sync node. 395 child_node = BookmarkChangeProcessor::CreateBookmarkNode( 396 &sync_child_node, parent_node, model, index); 397 } 398 Associate(child_node, sync_child_id); 399 if (sync_child_node.GetIsFolder()) 400 dfs_stack.push(sync_child_id); 401 402 sync_child_id = sync_child_node.GetSuccessorId(); 403 ++index; 404 } 405 406 // At this point all the children nodes of the parent sync node have 407 // corresponding children in the parent bookmark node and they are all in 408 // the right positions: from 0 to index - 1. 409 // So the children starting from index in the parent bookmark node are the 410 // ones that are not present in the parent sync node. So create them. 411 for (int i = index; i < parent_node->GetChildCount(); ++i) { 412 sync_child_id = BookmarkChangeProcessor::CreateSyncNode( 413 parent_node, model, i, &trans, this, sync_service_); 414 if (parent_node->GetChild(i)->is_folder()) 415 dfs_stack.push(sync_child_id); 416 } 417 } 418 return true; 419} 420 421void BookmarkModelAssociator::PostPersistAssociationsTask() { 422 // No need to post a task if a task is already pending. 423 if (!persist_associations_.empty()) 424 return; 425 MessageLoop::current()->PostTask( 426 FROM_HERE, 427 persist_associations_.NewRunnableMethod( 428 &BookmarkModelAssociator::PersistAssociations)); 429} 430 431void BookmarkModelAssociator::PersistAssociations() { 432 // If there are no dirty associations we have nothing to do. We handle this 433 // explicity instead of letting the for loop do it to avoid creating a write 434 // transaction in this case. 435 if (dirty_associations_sync_ids_.empty()) { 436 DCHECK(id_map_.empty()); 437 DCHECK(id_map_inverse_.empty()); 438 return; 439 } 440 441 sync_api::WriteTransaction trans( 442 sync_service_->backend()->GetUserShareHandle()); 443 DirtyAssociationsSyncIds::iterator iter; 444 for (iter = dirty_associations_sync_ids_.begin(); 445 iter != dirty_associations_sync_ids_.end(); 446 ++iter) { 447 int64 sync_id = *iter; 448 sync_api::WriteNode sync_node(&trans); 449 if (!sync_node.InitByIdLookup(sync_id)) { 450 persist_ids_error_handler_->OnUnrecoverableError(FROM_HERE, 451 "Could not lookup bookmark node for ID persistence."); 452 return; 453 } 454 const BookmarkNode* node = GetChromeNodeFromSyncId(sync_id); 455 if (node) 456 sync_node.SetExternalId(node->id()); 457 else 458 NOTREACHED(); 459 } 460 dirty_associations_sync_ids_.clear(); 461} 462 463bool BookmarkModelAssociator::LoadAssociations() { 464 BookmarkModel* model = sync_service_->profile()->GetBookmarkModel(); 465 DCHECK(model->IsLoaded()); 466 // If the bookmarks changed externally, our previous associations may not be 467 // valid; so return false. 468 if (model->file_changed()) 469 return false; 470 471 // Our persisted associations should be valid. Try to populate id association 472 // maps using persisted associations. Note that the unit tests will 473 // create the tagged nodes on demand, and the order in which we probe for 474 // them here will impact their positional ordering in that case. 475 int64 bookmark_bar_id; 476 if (!GetSyncIdForTaggedNode(kBookmarkBarTag, &bookmark_bar_id)) { 477 // We should always be able to find the permanent nodes. 478 return false; 479 } 480 int64 other_bookmarks_id; 481 if (!GetSyncIdForTaggedNode(kOtherBookmarksTag, &other_bookmarks_id)) { 482 // We should always be able to find the permanent nodes. 483 return false; 484 } 485 486 // Build a bookmark node ID index since we are going to repeatedly search for 487 // bookmark nodes by their IDs. 488 BookmarkNodeIdIndex id_index; 489 id_index.AddAll(model->GetBookmarkBarNode()); 490 id_index.AddAll(model->other_node()); 491 492 std::stack<int64> dfs_stack; 493 dfs_stack.push(other_bookmarks_id); 494 dfs_stack.push(bookmark_bar_id); 495 496 sync_api::ReadTransaction trans( 497 sync_service_->backend()->GetUserShareHandle()); 498 499 // Count total number of nodes in sync model so that we can compare that 500 // with the total number of nodes in the bookmark model. 501 size_t sync_node_count = 0; 502 while (!dfs_stack.empty()) { 503 int64 parent_id = dfs_stack.top(); 504 dfs_stack.pop(); 505 ++sync_node_count; 506 sync_api::ReadNode sync_parent(&trans); 507 if (!sync_parent.InitByIdLookup(parent_id)) { 508 return false; 509 } 510 511 int64 external_id = sync_parent.GetExternalId(); 512 if (external_id == 0) 513 return false; 514 515 const BookmarkNode* node = id_index.Find(external_id); 516 if (!node) 517 return false; 518 519 // Don't try to call NodesMatch on permanent nodes like bookmark bar and 520 // other bookmarks. They are not expected to match. 521 if (node != model->GetBookmarkBarNode() && 522 node != model->other_node() && 523 !NodesMatch(node, &sync_parent)) 524 return false; 525 526 Associate(node, sync_parent.GetId()); 527 528 // Add all children of the current node to the stack. 529 int64 child_id = sync_parent.GetFirstChildId(); 530 while (child_id != sync_api::kInvalidId) { 531 dfs_stack.push(child_id); 532 sync_api::ReadNode child_node(&trans); 533 if (!child_node.InitByIdLookup(child_id)) { 534 return false; 535 } 536 child_id = child_node.GetSuccessorId(); 537 } 538 } 539 DCHECK(dfs_stack.empty()); 540 541 // It's possible that the number of nodes in the bookmark model is not the 542 // same as number of nodes in the sync model. This can happen when the sync 543 // model doesn't get a chance to persist its changes, for example when 544 // Chrome does not shut down gracefully. In such cases we can't trust the 545 // loaded associations. 546 return sync_node_count == id_index.count(); 547} 548 549} // namespace browser_sync 550