sync/syncable/directory.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "sync/syncable/directory.h"
   6
   7 #include <iterator>
   8
   9 #include "base/base64.h"
  10 #include "base/debug/trace_event.h"
  11 #include "base/stl_util.h"
  12 #include "base/strings/string_number_conversions.h"
  13 #include "sync/internal_api/public/base/attachment_id_proto.h"
  14 #include "sync/internal_api/public/base/unique_position.h"
  15 #include "sync/internal_api/public/util/unrecoverable_error_handler.h"
  16 #include "sync/syncable/entry.h"
  17 #include "sync/syncable/entry_kernel.h"
  18 #include "sync/syncable/in_memory_directory_backing_store.h"
  19 #include "sync/syncable/on_disk_directory_backing_store.h"
  20 #include "sync/syncable/scoped_kernel_lock.h"
  21 #include "sync/syncable/scoped_parent_child_index_updater.h"
  22 #include "sync/syncable/syncable-inl.h"
  23 #include "sync/syncable/syncable_base_transaction.h"
  24 #include "sync/syncable/syncable_changes_version.h"
  25 #include "sync/syncable/syncable_read_transaction.h"
  26 #include "sync/syncable/syncable_util.h"
  27 #include "sync/syncable/syncable_write_transaction.h"
  28
  29 using std::string;
  30
  31 namespace syncer {
  32 namespace syncable {
  33
  34 // static
  35 const base::FilePath::CharType Directory::kSyncDatabaseFilename[] =
  36     FILE_PATH_LITERAL("SyncData.sqlite3");
  37
  38 Directory::PersistedKernelInfo::PersistedKernelInfo()
  39     : next_id(0) {
  40   ModelTypeSet protocol_types = ProtocolTypes();
  41   for (ModelTypeSet::Iterator iter = protocol_types.First(); iter.Good();
  42        iter.Inc()) {
  43     ResetDownloadProgress(iter.Get());
  44     transaction_version[iter.Get()] = 0;
  45   }
  46 }
  47
  48 Directory::PersistedKernelInfo::~PersistedKernelInfo() {}
  49
  50 void Directory::PersistedKernelInfo::ResetDownloadProgress(
  51     ModelType model_type) {
  52   // Clear everything except the data type id field.
  53   download_progress[model_type].Clear();
  54   download_progress[model_type].set_data_type_id(
  55       GetSpecificsFieldNumberFromModelType(model_type));
  56
  57   // Explicitly set an empty token field to denote no progress.
  58   download_progress[model_type].set_token("");
  59 }
  60
  61 bool Directory::PersistedKernelInfo::HasEmptyDownloadProgress(
  62     ModelType model_type) {
  63   const sync_pb::DataTypeProgressMarker& progress_marker =
  64       download_progress[model_type];
  65   return progress_marker.token().empty();
  66 }
  67
  68 Directory::SaveChangesSnapshot::SaveChangesSnapshot()
  69     : kernel_info_status(KERNEL_SHARE_INFO_INVALID) {
  70 }
  71
  72 Directory::SaveChangesSnapshot::~SaveChangesSnapshot() {
  73   STLDeleteElements(&dirty_metas);
  74   STLDeleteElements(&delete_journals);
  75 }
  76
  77 Directory::Kernel::Kernel(
  78     const std::string& name,
  79     const KernelLoadInfo& info, DirectoryChangeDelegate* delegate,
  80     const WeakHandle<TransactionObserver>& transaction_observer)
  81     : next_write_transaction_id(0),
  82       name(name),
  83       info_status(Directory::KERNEL_SHARE_INFO_VALID),
  84       persisted_info(info.kernel_info),
  85       cache_guid(info.cache_guid),
  86       next_metahandle(info.max_metahandle + 1),
  87       delegate(delegate),
  88       transaction_observer(transaction_observer) {
  89   DCHECK(delegate);
  90   DCHECK(transaction_observer.IsInitialized());
  91 }
  92
  93 Directory::Kernel::~Kernel() {
  94   STLDeleteContainerPairSecondPointers(metahandles_map.begin(),
  95                                        metahandles_map.end());
  96 }
  97
  98 Directory::Directory(
  99     DirectoryBackingStore* store,
 100     UnrecoverableErrorHandler* unrecoverable_error_handler,
 101     ReportUnrecoverableErrorFunction report_unrecoverable_error_function,
 102     NigoriHandler* nigori_handler,
 103     Cryptographer* cryptographer)
 104     : kernel_(NULL),
 105       store_(store),
 106       unrecoverable_error_handler_(unrecoverable_error_handler),
 107       report_unrecoverable_error_function_(
 108           report_unrecoverable_error_function),
 109       unrecoverable_error_set_(false),
 110       nigori_handler_(nigori_handler),
 111       cryptographer_(cryptographer),
 112       invariant_check_level_(VERIFY_CHANGES) {
 113 }
 114
 115 Directory::~Directory() {
 116   Close();
 117 }
 118
 119 DirOpenResult Directory::Open(
 120     const string& name,
 121     DirectoryChangeDelegate* delegate,
 122     const WeakHandle<TransactionObserver>& transaction_observer) {
 123   TRACE_EVENT0("sync", "SyncDatabaseOpen");
 124
 125   const DirOpenResult result =
 126       OpenImpl(name, delegate, transaction_observer);
 127
 128   if (OPENED != result)
 129     Close();
 130   return result;
 131 }
 132
 133 void Directory::InitializeIndices(MetahandlesMap* handles_map) {
 134   ScopedKernelLock lock(this);
 135   kernel_->metahandles_map.swap(*handles_map);
 136   for (MetahandlesMap::const_iterator it = kernel_->metahandles_map.begin();
 137        it != kernel_->metahandles_map.end(); ++it) {
 138     EntryKernel* entry = it->second;
 139     if (ParentChildIndex::ShouldInclude(entry))
 140       kernel_->parent_child_index.Insert(entry);
 141     const int64 metahandle = entry->ref(META_HANDLE);
 142     if (entry->ref(IS_UNSYNCED))
 143       kernel_->unsynced_metahandles.insert(metahandle);
 144     if (entry->ref(IS_UNAPPLIED_UPDATE)) {
 145       const ModelType type = entry->GetServerModelType();
 146       kernel_->unapplied_update_metahandles[type].insert(metahandle);
 147     }
 148     if (!entry->ref(UNIQUE_SERVER_TAG).empty()) {
 149       DCHECK(kernel_->server_tags_map.find(entry->ref(UNIQUE_SERVER_TAG)) ==
 150              kernel_->server_tags_map.end())
 151           << "Unexpected duplicate use of client tag";
 152       kernel_->server_tags_map[entry->ref(UNIQUE_SERVER_TAG)] = entry;
 153     }
 154     if (!entry->ref(UNIQUE_CLIENT_TAG).empty()) {
 155       DCHECK(kernel_->server_tags_map.find(entry->ref(UNIQUE_SERVER_TAG)) ==
 156              kernel_->server_tags_map.end())
 157           << "Unexpected duplicate use of server tag";
 158       kernel_->client_tags_map[entry->ref(UNIQUE_CLIENT_TAG)] = entry;
 159     }
 160     DCHECK(kernel_->ids_map.find(entry->ref(ID).value()) ==
 161            kernel_->ids_map.end()) << "Unexpected duplicate use of ID";
 162     kernel_->ids_map[entry->ref(ID).value()] = entry;
 163     DCHECK(!entry->is_dirty());
 164     AddToAttachmentIndex(metahandle, entry->ref(ATTACHMENT_METADATA), lock);
 165   }
 166 }
 167
 168 DirOpenResult Directory::OpenImpl(
 169     const string& name,
 170     DirectoryChangeDelegate* delegate,
 171     const WeakHandle<TransactionObserver>&
 172         transaction_observer) {
 173   KernelLoadInfo info;
 174   // Temporary indices before kernel_ initialized in case Load fails. We 0(1)
 175   // swap these later.
 176   Directory::MetahandlesMap tmp_handles_map;
 177
 178   // Avoids mem leaks on failure.  Harmlessly deletes the empty hash map after
 179   // the swap in the success case.
 180   STLValueDeleter<Directory::MetahandlesMap> deleter(&tmp_handles_map);
 181
 182   JournalIndex delete_journals;
 183
 184   DirOpenResult result =
 185       store_->Load(&tmp_handles_map, &delete_journals, &info);
 186   if (OPENED != result)
 187     return result;
 188
 189   kernel_ = new Kernel(name, info, delegate, transaction_observer);
 190   delete_journal_.reset(new DeleteJournal(&delete_journals));
 191   InitializeIndices(&tmp_handles_map);
 192
 193   // Write back the share info to reserve some space in 'next_id'.  This will
 194   // prevent local ID reuse in the case of an early crash.  See the comments in
 195   // TakeSnapshotForSaveChanges() or crbug.com/142987 for more information.
 196   kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
 197   if (!SaveChanges())
 198     return FAILED_INITIAL_WRITE;
 199
 200   return OPENED;
 201 }
 202
 203 DeleteJournal* Directory::delete_journal() {
 204   DCHECK(delete_journal_.get());
 205   return delete_journal_.get();
 206 }
 207
 208 void Directory::Close() {
 209   store_.reset();
 210   if (kernel_) {
 211     delete kernel_;
 212     kernel_ = NULL;
 213   }
 214 }
 215
 216 void Directory::OnUnrecoverableError(const BaseTransaction* trans,
 217                                      const tracked_objects::Location& location,
 218                                      const std::string & message) {
 219   DCHECK(trans != NULL);
 220   unrecoverable_error_set_ = true;
 221   unrecoverable_error_handler_->OnUnrecoverableError(location,
 222                                                      message);
 223 }
 224
 225 EntryKernel* Directory::GetEntryById(const Id& id) {
 226   ScopedKernelLock lock(this);
 227   return GetEntryById(id, &lock);
 228 }
 229
 230 EntryKernel* Directory::GetEntryById(const Id& id,
 231                                      ScopedKernelLock* const lock) {
 232   DCHECK(kernel_);
 233   // Find it in the in memory ID index.
 234   IdsMap::iterator id_found = kernel_->ids_map.find(id.value());
 235   if (id_found != kernel_->ids_map.end()) {
 236     return id_found->second;
 237   }
 238   return NULL;
 239 }
 240
 241 EntryKernel* Directory::GetEntryByClientTag(const string& tag) {
 242   ScopedKernelLock lock(this);
 243   DCHECK(kernel_);
 244
 245   TagsMap::iterator it = kernel_->client_tags_map.find(tag);
 246   if (it != kernel_->client_tags_map.end()) {
 247     return it->second;
 248   }
 249   return NULL;
 250 }
 251
 252 EntryKernel* Directory::GetEntryByServerTag(const string& tag) {
 253   ScopedKernelLock lock(this);
 254   DCHECK(kernel_);
 255   TagsMap::iterator it = kernel_->server_tags_map.find(tag);
 256   if (it != kernel_->server_tags_map.end()) {
 257     return it->second;
 258   }
 259   return NULL;
 260 }
 261
 262 EntryKernel* Directory::GetEntryByHandle(int64 metahandle) {
 263   ScopedKernelLock lock(this);
 264   return GetEntryByHandle(metahandle, &lock);
 265 }
 266
 267 EntryKernel* Directory::GetEntryByHandle(int64 metahandle,
 268                                          ScopedKernelLock* lock) {
 269   // Look up in memory
 270   MetahandlesMap::iterator found =
 271       kernel_->metahandles_map.find(metahandle);
 272   if (found != kernel_->metahandles_map.end()) {
 273     // Found it in memory.  Easy.
 274     return found->second;
 275   }
 276   return NULL;
 277 }
 278
 279 bool Directory::GetChildHandlesById(
 280     BaseTransaction* trans, const Id& parent_id,
 281     Directory::Metahandles* result) {
 282   if (!SyncAssert(this == trans->directory(), FROM_HERE,
 283                   "Directories don't match", trans))
 284     return false;
 285   result->clear();
 286
 287   ScopedKernelLock lock(this);
 288   AppendChildHandles(lock, parent_id, result);
 289   return true;
 290 }
 291
 292 int Directory::GetTotalNodeCount(
 293     BaseTransaction* trans,
 294     EntryKernel* kernel) const {
 295   if (!SyncAssert(this == trans->directory(), FROM_HERE,
 296                   "Directories don't match", trans))
 297     return false;
 298
 299   int count = 1;
 300   std::deque<const OrderedChildSet*> child_sets;
 301
 302   GetChildSetForKernel(trans, kernel, &child_sets);
 303   while (!child_sets.empty()) {
 304     const OrderedChildSet* set = child_sets.front();
 305     child_sets.pop_front();
 306     for (OrderedChildSet::const_iterator it = set->begin();
 307          it != set->end(); ++it) {
 308       count++;
 309       GetChildSetForKernel(trans, *it, &child_sets);
 310     }
 311   }
 312
 313   return count;
 314 }
 315
 316 void Directory::GetChildSetForKernel(
 317     BaseTransaction* trans,
 318     EntryKernel* kernel,
 319     std::deque<const OrderedChildSet*>* child_sets) const {
 320   if (!kernel->ref(IS_DIR))
 321     return;  // Not a directory => no children.
 322
 323   const OrderedChildSet* descendants =
 324       kernel_->parent_child_index.GetChildren(kernel->ref(ID));
 325   if (!descendants)
 326     return;  // This directory has no children.
 327
 328   // Add our children to the list of items to be traversed.
 329   child_sets->push_back(descendants);
 330 }
 331
 332 int Directory::GetPositionIndex(
 333     BaseTransaction* trans,
 334     EntryKernel* kernel) const {
 335   const OrderedChildSet* siblings =
 336       kernel_->parent_child_index.GetChildren(kernel->ref(PARENT_ID));
 337
 338   OrderedChildSet::const_iterator it = siblings->find(kernel);
 339   return std::distance(siblings->begin(), it);
 340 }
 341
 342 bool Directory::InsertEntry(BaseWriteTransaction* trans, EntryKernel* entry) {
 343   ScopedKernelLock lock(this);
 344   return InsertEntry(trans, entry, &lock);
 345 }
 346
 347 bool Directory::InsertEntry(BaseWriteTransaction* trans,
 348                             EntryKernel* entry,
 349                             ScopedKernelLock* lock) {
 350   DCHECK(NULL != lock);
 351   if (!SyncAssert(NULL != entry, FROM_HERE, "Entry is null", trans))
 352     return false;
 353
 354   static const char error[] = "Entry already in memory index.";
 355
 356   if (!SyncAssert(
 357           kernel_->metahandles_map.insert(
 358               std::make_pair(entry->ref(META_HANDLE), entry)).second,
 359           FROM_HERE,
 360           error,
 361           trans)) {
 362     return false;
 363   }
 364   if (!SyncAssert(
 365           kernel_->ids_map.insert(
 366               std::make_pair(entry->ref(ID).value(), entry)).second,
 367           FROM_HERE,
 368           error,
 369           trans)) {
 370     return false;
 371   }
 372   if (ParentChildIndex::ShouldInclude(entry)) {
 373     if (!SyncAssert(kernel_->parent_child_index.Insert(entry),
 374                     FROM_HERE,
 375                     error,
 376                     trans)) {
 377       return false;
 378     }
 379   }
 380   AddToAttachmentIndex(
 381       entry->ref(META_HANDLE), entry->ref(ATTACHMENT_METADATA), *lock);
 382
 383   // Should NEVER be created with a client tag or server tag.
 384   if (!SyncAssert(entry->ref(UNIQUE_SERVER_TAG).empty(), FROM_HERE,
 385                   "Server tag should be empty", trans)) {
 386     return false;
 387   }
 388   if (!SyncAssert(entry->ref(UNIQUE_CLIENT_TAG).empty(), FROM_HERE,
 389                   "Client tag should be empty", trans))
 390     return false;
 391
 392   return true;
 393 }
 394
 395 bool Directory::ReindexId(BaseWriteTransaction* trans,
 396                           EntryKernel* const entry,
 397                           const Id& new_id) {
 398   ScopedKernelLock lock(this);
 399   if (NULL != GetEntryById(new_id, &lock))
 400     return false;
 401
 402   {
 403     // Update the indices that depend on the ID field.
 404     ScopedParentChildIndexUpdater updater_b(lock, entry,
 405         &kernel_->parent_child_index);
 406     size_t num_erased = kernel_->ids_map.erase(entry->ref(ID).value());
 407     DCHECK_EQ(1U, num_erased);
 408     entry->put(ID, new_id);
 409     kernel_->ids_map[entry->ref(ID).value()] = entry;
 410   }
 411   return true;
 412 }
 413
 414 bool Directory::ReindexParentId(BaseWriteTransaction* trans,
 415                                 EntryKernel* const entry,
 416                                 const Id& new_parent_id) {
 417   ScopedKernelLock lock(this);
 418
 419   {
 420     // Update the indices that depend on the PARENT_ID field.
 421     ScopedParentChildIndexUpdater index_updater(lock, entry,
 422         &kernel_->parent_child_index);
 423     entry->put(PARENT_ID, new_parent_id);
 424   }
 425   return true;
 426 }
 427
 428 void Directory::RemoveFromAttachmentIndex(
 429     const int64 metahandle,
 430     const sync_pb::AttachmentMetadata& attachment_metadata,
 431     const ScopedKernelLock& lock) {
 432   for (int i = 0; i < attachment_metadata.record_size(); ++i) {
 433     AttachmentIdUniqueId unique_id =
 434         attachment_metadata.record(i).id().unique_id();
 435     IndexByAttachmentId::iterator iter =
 436         kernel_->index_by_attachment_id.find(unique_id);
 437     if (iter != kernel_->index_by_attachment_id.end()) {
 438       iter->second.erase(metahandle);
 439       if (iter->second.empty()) {
 440         kernel_->index_by_attachment_id.erase(iter);
 441       }
 442     }
 443   }
 444 }
 445
 446 void Directory::AddToAttachmentIndex(
 447     const int64 metahandle,
 448     const sync_pb::AttachmentMetadata& attachment_metadata,
 449     const ScopedKernelLock& lock) {
 450   for (int i = 0; i < attachment_metadata.record_size(); ++i) {
 451     AttachmentIdUniqueId unique_id =
 452         attachment_metadata.record(i).id().unique_id();
 453     IndexByAttachmentId::iterator iter =
 454         kernel_->index_by_attachment_id.find(unique_id);
 455     if (iter == kernel_->index_by_attachment_id.end()) {
 456       iter = kernel_->index_by_attachment_id.insert(std::make_pair(
 457                                                         unique_id,
 458                                                         MetahandleSet())).first;
 459     }
 460     iter->second.insert(metahandle);
 461   }
 462 }
 463
 464 void Directory::UpdateAttachmentIndex(
 465     const int64 metahandle,
 466     const sync_pb::AttachmentMetadata& old_metadata,
 467     const sync_pb::AttachmentMetadata& new_metadata) {
 468   ScopedKernelLock lock(this);
 469   RemoveFromAttachmentIndex(metahandle, old_metadata, lock);
 470   AddToAttachmentIndex(metahandle, new_metadata, lock);
 471 }
 472
 473 void Directory::GetMetahandlesByAttachmentId(
 474     BaseTransaction* trans,
 475     const sync_pb::AttachmentIdProto& attachment_id_proto,
 476     Metahandles* result) {
 477   DCHECK(result);
 478   result->clear();
 479   ScopedKernelLock lock(this);
 480   IndexByAttachmentId::const_iterator index_iter =
 481       kernel_->index_by_attachment_id.find(attachment_id_proto.unique_id());
 482   if (index_iter == kernel_->index_by_attachment_id.end())
 483     return;
 484   const MetahandleSet& metahandle_set = index_iter->second;
 485   std::copy(
 486       metahandle_set.begin(), metahandle_set.end(), back_inserter(*result));
 487 }
 488
 489 bool Directory::unrecoverable_error_set(const BaseTransaction* trans) const {
 490   DCHECK(trans != NULL);
 491   return unrecoverable_error_set_;
 492 }
 493
 494 void Directory::ClearDirtyMetahandles() {
 495   kernel_->transaction_mutex.AssertAcquired();
 496   kernel_->dirty_metahandles.clear();
 497 }
 498
 499 bool Directory::SafeToPurgeFromMemory(WriteTransaction* trans,
 500                                       const EntryKernel* const entry) const {
 501   bool safe = entry->ref(IS_DEL) && !entry->is_dirty() &&
 502       !entry->ref(SYNCING) && !entry->ref(IS_UNAPPLIED_UPDATE) &&
 503       !entry->ref(IS_UNSYNCED);
 504
 505   if (safe) {
 506     int64 handle = entry->ref(META_HANDLE);
 507     const ModelType type = entry->GetServerModelType();
 508     if (!SyncAssert(kernel_->dirty_metahandles.count(handle) == 0U,
 509                     FROM_HERE,
 510                     "Dirty metahandles should be empty", trans))
 511       return false;
 512     // TODO(tim): Bug 49278.
 513     if (!SyncAssert(!kernel_->unsynced_metahandles.count(handle),
 514                     FROM_HERE,
 515                     "Unsynced handles should be empty",
 516                     trans))
 517       return false;
 518     if (!SyncAssert(!kernel_->unapplied_update_metahandles[type].count(handle),
 519                     FROM_HERE,
 520                     "Unapplied metahandles should be empty",
 521                     trans))
 522       return false;
 523   }
 524
 525   return safe;
 526 }
 527
 528 void Directory::TakeSnapshotForSaveChanges(SaveChangesSnapshot* snapshot) {
 529   ReadTransaction trans(FROM_HERE, this);
 530   ScopedKernelLock lock(this);
 531
 532   // If there is an unrecoverable error then just bail out.
 533   if (unrecoverable_error_set(&trans))
 534     return;
 535
 536   // Deep copy dirty entries from kernel_->metahandles_index into snapshot and
 537   // clear dirty flags.
 538   for (MetahandleSet::const_iterator i = kernel_->dirty_metahandles.begin();
 539        i != kernel_->dirty_metahandles.end(); ++i) {
 540     EntryKernel* entry = GetEntryByHandle(*i, &lock);
 541     if (!entry)
 542       continue;
 543     // Skip over false positives; it happens relatively infrequently.
 544     if (!entry->is_dirty())
 545       continue;
 546     snapshot->dirty_metas.insert(snapshot->dirty_metas.end(),
 547                                  new EntryKernel(*entry));
 548     DCHECK_EQ(1U, kernel_->dirty_metahandles.count(*i));
 549     // We don't bother removing from the index here as we blow the entire thing
 550     // in a moment, and it unnecessarily complicates iteration.
 551     entry->clear_dirty(NULL);
 552   }
 553   ClearDirtyMetahandles();
 554
 555   // Set purged handles.
 556   DCHECK(snapshot->metahandles_to_purge.empty());
 557   snapshot->metahandles_to_purge.swap(kernel_->metahandles_to_purge);
 558
 559   // Fill kernel_info_status and kernel_info.
 560   snapshot->kernel_info = kernel_->persisted_info;
 561   // To avoid duplicates when the process crashes, we record the next_id to be
 562   // greater magnitude than could possibly be reached before the next save
 563   // changes.  In other words, it's effectively impossible for the user to
 564   // generate 65536 new bookmarks in 3 seconds.
 565   snapshot->kernel_info.next_id -= 65536;
 566   snapshot->kernel_info_status = kernel_->info_status;
 567   // This one we reset on failure.
 568   kernel_->info_status = KERNEL_SHARE_INFO_VALID;
 569
 570   delete_journal_->TakeSnapshotAndClear(
 571       &trans, &snapshot->delete_journals, &snapshot->delete_journals_to_purge);
 572 }
 573
 574 bool Directory::SaveChanges() {
 575   bool success = false;
 576
 577   base::AutoLock scoped_lock(kernel_->save_changes_mutex);
 578
 579   // Snapshot and save.
 580   SaveChangesSnapshot snapshot;
 581   TakeSnapshotForSaveChanges(&snapshot);
 582   success = store_->SaveChanges(snapshot);
 583
 584   // Handle success or failure.
 585   if (success)
 586     success = VacuumAfterSaveChanges(snapshot);
 587   else
 588     HandleSaveChangesFailure(snapshot);
 589   return success;
 590 }
 591
 592 bool Directory::VacuumAfterSaveChanges(const SaveChangesSnapshot& snapshot) {
 593   if (snapshot.dirty_metas.empty())
 594     return true;
 595
 596   // Need a write transaction as we are about to permanently purge entries.
 597   WriteTransaction trans(FROM_HERE, VACUUM_AFTER_SAVE, this);
 598   ScopedKernelLock lock(this);
 599   // Now drop everything we can out of memory.
 600   for (EntryKernelSet::const_iterator i = snapshot.dirty_metas.begin();
 601        i != snapshot.dirty_metas.end(); ++i) {
 602     MetahandlesMap::iterator found =
 603         kernel_->metahandles_map.find((*i)->ref(META_HANDLE));
 604     EntryKernel* entry = (found == kernel_->metahandles_map.end() ?
 605                           NULL : found->second);
 606     if (entry && SafeToPurgeFromMemory(&trans, entry)) {
 607       // We now drop deleted metahandles that are up to date on both the client
 608       // and the server.
 609       size_t num_erased = 0;
 610       num_erased = kernel_->metahandles_map.erase(entry->ref(META_HANDLE));
 611       DCHECK_EQ(1u, num_erased);
 612       num_erased = kernel_->ids_map.erase(entry->ref(ID).value());
 613       DCHECK_EQ(1u, num_erased);
 614       if (!entry->ref(UNIQUE_SERVER_TAG).empty()) {
 615         num_erased =
 616             kernel_->server_tags_map.erase(entry->ref(UNIQUE_SERVER_TAG));
 617         DCHECK_EQ(1u, num_erased);
 618       }
 619       if (!entry->ref(UNIQUE_CLIENT_TAG).empty()) {
 620         num_erased =
 621             kernel_->client_tags_map.erase(entry->ref(UNIQUE_CLIENT_TAG));
 622         DCHECK_EQ(1u, num_erased);
 623       }
 624       if (!SyncAssert(!kernel_->parent_child_index.Contains(entry),
 625                       FROM_HERE,
 626                       "Deleted entry still present",
 627                       (&trans)))
 628         return false;
 629       RemoveFromAttachmentIndex(
 630           entry->ref(META_HANDLE), entry->ref(ATTACHMENT_METADATA), lock);
 631
 632       delete entry;
 633     }
 634     if (trans.unrecoverable_error_set())
 635       return false;
 636   }
 637   return true;
 638 }
 639
 640 void Directory::UnapplyEntry(EntryKernel* entry) {
 641   int64 handle = entry->ref(META_HANDLE);
 642   ModelType server_type = GetModelTypeFromSpecifics(
 643       entry->ref(SERVER_SPECIFICS));
 644
 645   // Clear enough so that on the next sync cycle all local data will
 646   // be overwritten.
 647   // Note: do not modify the root node in order to preserve the
 648   // initial sync ended bit for this type (else on the next restart
 649   // this type will be treated as disabled and therefore fully purged).
 650   if (IsRealDataType(server_type) &&
 651       ModelTypeToRootTag(server_type) == entry->ref(UNIQUE_SERVER_TAG)) {
 652     return;
 653   }
 654
 655   // Set the unapplied bit if this item has server data.
 656   if (IsRealDataType(server_type) && !entry->ref(IS_UNAPPLIED_UPDATE)) {
 657     entry->put(IS_UNAPPLIED_UPDATE, true);
 658     kernel_->unapplied_update_metahandles[server_type].insert(handle);
 659     entry->mark_dirty(&kernel_->dirty_metahandles);
 660   }
 661
 662   // Unset the unsynced bit.
 663   if (entry->ref(IS_UNSYNCED)) {
 664     kernel_->unsynced_metahandles.erase(handle);
 665     entry->put(IS_UNSYNCED, false);
 666     entry->mark_dirty(&kernel_->dirty_metahandles);
 667   }
 668
 669   // Mark the item as locally deleted. No deleted items are allowed in the
 670   // parent child index.
 671   if (!entry->ref(IS_DEL)) {
 672     kernel_->parent_child_index.Remove(entry);
 673     entry->put(IS_DEL, true);
 674     entry->mark_dirty(&kernel_->dirty_metahandles);
 675   }
 676
 677   // Set the version to the "newly created" version.
 678   if (entry->ref(BASE_VERSION) != CHANGES_VERSION) {
 679     entry->put(BASE_VERSION, CHANGES_VERSION);
 680     entry->mark_dirty(&kernel_->dirty_metahandles);
 681   }
 682
 683   // At this point locally created items that aren't synced will become locally
 684   // deleted items, and purged on the next snapshot. All other items will match
 685   // the state they would have had if they were just created via a server
 686   // update. See MutableEntry::MutableEntry(.., CreateNewUpdateItem, ..).
 687 }
 688
 689 void Directory::DeleteEntry(bool save_to_journal,
 690                             EntryKernel* entry,
 691                             EntryKernelSet* entries_to_journal,
 692                             const ScopedKernelLock& lock) {
 693   int64 handle = entry->ref(META_HANDLE);
 694   ModelType server_type = GetModelTypeFromSpecifics(
 695       entry->ref(SERVER_SPECIFICS));
 696
 697   kernel_->metahandles_to_purge.insert(handle);
 698
 699   size_t num_erased = 0;
 700   num_erased = kernel_->metahandles_map.erase(entry->ref(META_HANDLE));
 701   DCHECK_EQ(1u, num_erased);
 702   num_erased = kernel_->ids_map.erase(entry->ref(ID).value());
 703   DCHECK_EQ(1u, num_erased);
 704   num_erased = kernel_->unsynced_metahandles.erase(handle);
 705   DCHECK_EQ(entry->ref(IS_UNSYNCED), num_erased > 0);
 706   num_erased =
 707       kernel_->unapplied_update_metahandles[server_type].erase(handle);
 708   DCHECK_EQ(entry->ref(IS_UNAPPLIED_UPDATE), num_erased > 0);
 709   if (kernel_->parent_child_index.Contains(entry))
 710     kernel_->parent_child_index.Remove(entry);
 711
 712   if (!entry->ref(UNIQUE_CLIENT_TAG).empty()) {
 713     num_erased =
 714         kernel_->client_tags_map.erase(entry->ref(UNIQUE_CLIENT_TAG));
 715     DCHECK_EQ(1u, num_erased);
 716   }
 717   if (!entry->ref(UNIQUE_SERVER_TAG).empty()) {
 718     num_erased =
 719         kernel_->server_tags_map.erase(entry->ref(UNIQUE_SERVER_TAG));
 720     DCHECK_EQ(1u, num_erased);
 721   }
 722   RemoveFromAttachmentIndex(handle, entry->ref(ATTACHMENT_METADATA), lock);
 723
 724   if (save_to_journal) {
 725     entries_to_journal->insert(entry);
 726   } else {
 727     delete entry;
 728   }
 729 }
 730
 731 bool Directory::PurgeEntriesWithTypeIn(ModelTypeSet disabled_types,
 732                                        ModelTypeSet types_to_journal,
 733                                        ModelTypeSet types_to_unapply) {
 734   disabled_types.RemoveAll(ProxyTypes());
 735
 736   if (disabled_types.Empty())
 737     return true;
 738
 739   {
 740     WriteTransaction trans(FROM_HERE, PURGE_ENTRIES, this);
 741
 742     EntryKernelSet entries_to_journal;
 743     STLElementDeleter<EntryKernelSet> journal_deleter(&entries_to_journal);
 744
 745     {
 746       ScopedKernelLock lock(this);
 747
 748       bool found_progress = false;
 749       for (ModelTypeSet::Iterator iter = disabled_types.First(); iter.Good();
 750            iter.Inc()) {
 751         if (!kernel_->persisted_info.HasEmptyDownloadProgress(iter.Get()))
 752           found_progress = true;
 753       }
 754
 755       // If none of the disabled types have progress markers, there's nothing to
 756       // purge.
 757       if (!found_progress)
 758         return true;
 759
 760       // We iterate in two passes to avoid a bug in STLport (which is used in
 761       // the Android build).  There are some versions of that library where a
 762       // hash_map's iterators can be invalidated when an item is erased from the
 763       // hash_map.
 764       // See http://sourceforge.net/p/stlport/bugs/239/.
 765
 766       std::set<EntryKernel*> to_purge;
 767       for (MetahandlesMap::iterator it = kernel_->metahandles_map.begin();
 768            it != kernel_->metahandles_map.end(); ++it) {
 769         const sync_pb::EntitySpecifics& local_specifics =
 770             it->second->ref(SPECIFICS);
 771         const sync_pb::EntitySpecifics& server_specifics =
 772             it->second->ref(SERVER_SPECIFICS);
 773         ModelType local_type = GetModelTypeFromSpecifics(local_specifics);
 774         ModelType server_type = GetModelTypeFromSpecifics(server_specifics);
 775
 776         if ((IsRealDataType(local_type) && disabled_types.Has(local_type)) ||
 777             (IsRealDataType(server_type) && disabled_types.Has(server_type))) {
 778           to_purge.insert(it->second);
 779         }
 780       }
 781
 782       for (std::set<EntryKernel*>::iterator it = to_purge.begin();
 783            it != to_purge.end(); ++it) {
 784         EntryKernel* entry = *it;
 785
 786         const sync_pb::EntitySpecifics& local_specifics =
 787             (*it)->ref(SPECIFICS);
 788         const sync_pb::EntitySpecifics& server_specifics =
 789             (*it)->ref(SERVER_SPECIFICS);
 790         ModelType local_type = GetModelTypeFromSpecifics(local_specifics);
 791         ModelType server_type = GetModelTypeFromSpecifics(server_specifics);
 792
 793         if (types_to_unapply.Has(local_type) ||
 794             types_to_unapply.Has(server_type)) {
 795           UnapplyEntry(entry);
 796         } else {
 797           bool save_to_journal =
 798               (types_to_journal.Has(local_type) ||
 799                types_to_journal.Has(server_type)) &&
 800               (delete_journal_->IsDeleteJournalEnabled(local_type) ||
 801                delete_journal_->IsDeleteJournalEnabled(server_type));
 802           DeleteEntry(save_to_journal, entry, &entries_to_journal, lock);
 803         }
 804       }
 805
 806       delete_journal_->AddJournalBatch(&trans, entries_to_journal);
 807
 808       // Ensure meta tracking for these data types reflects the purged state.
 809       for (ModelTypeSet::Iterator it = disabled_types.First();
 810            it.Good(); it.Inc()) {
 811         kernel_->persisted_info.transaction_version[it.Get()] = 0;
 812
 813         // Don't discard progress markers or context for unapplied types.
 814         if (!types_to_unapply.Has(it.Get())) {
 815           kernel_->persisted_info.ResetDownloadProgress(it.Get());
 816           kernel_->persisted_info.datatype_context[it.Get()].Clear();
 817         }
 818       }
 819
 820       kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
 821     }
 822   }
 823   return true;
 824 }
 825
 826 bool Directory::ResetVersionsForType(BaseWriteTransaction* trans,
 827                                      ModelType type) {
 828   if (!ProtocolTypes().Has(type))
 829     return false;
 830   DCHECK_NE(type, BOOKMARKS) << "Only non-hierarchical types are supported";
 831
 832   EntryKernel* type_root = GetEntryByServerTag(ModelTypeToRootTag(type));
 833   if (!type_root)
 834     return false;
 835
 836   ScopedKernelLock lock(this);
 837   const Id& type_root_id = type_root->ref(ID);
 838   Directory::Metahandles children;
 839   AppendChildHandles(lock, type_root_id, &children);
 840
 841   for (Metahandles::iterator it = children.begin(); it != children.end();
 842        ++it) {
 843     EntryKernel* entry = GetEntryByHandle(*it, &lock);
 844     if (!entry)
 845       continue;
 846     if (entry->ref(BASE_VERSION) > 1)
 847       entry->put(BASE_VERSION, 1);
 848     if (entry->ref(SERVER_VERSION) > 1)
 849       entry->put(SERVER_VERSION, 1);
 850
 851     // Note that we do not unset IS_UNSYNCED or IS_UNAPPLIED_UPDATE in order
 852     // to ensure no in-transit data is lost.
 853
 854     entry->mark_dirty(&kernel_->dirty_metahandles);
 855   }
 856
 857   return true;
 858 }
 859
 860 bool Directory::IsAttachmentLinked(
 861     const sync_pb::AttachmentIdProto& attachment_id_proto) const {
 862   ScopedKernelLock lock(this);
 863   IndexByAttachmentId::const_iterator iter =
 864       kernel_->index_by_attachment_id.find(attachment_id_proto.unique_id());
 865   if (iter != kernel_->index_by_attachment_id.end() && !iter->second.empty()) {
 866     return true;
 867   }
 868   return false;
 869 }
 870
 871 void Directory::HandleSaveChangesFailure(const SaveChangesSnapshot& snapshot) {
 872   WriteTransaction trans(FROM_HERE, HANDLE_SAVE_FAILURE, this);
 873   ScopedKernelLock lock(this);
 874   kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
 875
 876   // Because we optimistically cleared the dirty bit on the real entries when
 877   // taking the snapshot, we must restore it on failure.  Not doing this could
 878   // cause lost data, if no other changes are made to the in-memory entries
 879   // that would cause the dirty bit to get set again. Setting the bit ensures
 880   // that SaveChanges will at least try again later.
 881   for (EntryKernelSet::const_iterator i = snapshot.dirty_metas.begin();
 882        i != snapshot.dirty_metas.end(); ++i) {
 883     MetahandlesMap::iterator found =
 884         kernel_->metahandles_map.find((*i)->ref(META_HANDLE));
 885     if (found != kernel_->metahandles_map.end()) {
 886       found->second->mark_dirty(&kernel_->dirty_metahandles);
 887     }
 888   }
 889
 890   kernel_->metahandles_to_purge.insert(snapshot.metahandles_to_purge.begin(),
 891                                        snapshot.metahandles_to_purge.end());
 892
 893   // Restore delete journals.
 894   delete_journal_->AddJournalBatch(&trans, snapshot.delete_journals);
 895   delete_journal_->PurgeDeleteJournals(&trans,
 896                                        snapshot.delete_journals_to_purge);
 897 }
 898
 899 void Directory::GetDownloadProgress(
 900     ModelType model_type,
 901     sync_pb::DataTypeProgressMarker* value_out) const {
 902   ScopedKernelLock lock(this);
 903   return value_out->CopyFrom(
 904       kernel_->persisted_info.download_progress[model_type]);
 905 }
 906
 907 void Directory::GetDownloadProgressAsString(
 908     ModelType model_type,
 909     std::string* value_out) const {
 910   ScopedKernelLock lock(this);
 911   kernel_->persisted_info.download_progress[model_type].SerializeToString(
 912       value_out);
 913 }
 914
 915 size_t Directory::GetEntriesCount() const {
 916   ScopedKernelLock lock(this);
 917   return kernel_->metahandles_map.size();
 918 }
 919
 920 void Directory::SetDownloadProgress(
 921     ModelType model_type,
 922     const sync_pb::DataTypeProgressMarker& new_progress) {
 923   ScopedKernelLock lock(this);
 924   kernel_->persisted_info.download_progress[model_type].CopyFrom(new_progress);
 925   kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
 926 }
 927
 928 int64 Directory::GetTransactionVersion(ModelType type) const {
 929   kernel_->transaction_mutex.AssertAcquired();
 930   return kernel_->persisted_info.transaction_version[type];
 931 }
 932
 933 void Directory::IncrementTransactionVersion(ModelType type) {
 934   kernel_->transaction_mutex.AssertAcquired();
 935   kernel_->persisted_info.transaction_version[type]++;
 936 }
 937
 938 void Directory::GetDataTypeContext(BaseTransaction* trans,
 939                                    ModelType type,
 940                                    sync_pb::DataTypeContext* context) const {
 941   ScopedKernelLock lock(this);
 942   context->CopyFrom(kernel_->persisted_info.datatype_context[type]);
 943 }
 944
 945 void Directory::SetDataTypeContext(
 946     BaseWriteTransaction* trans,
 947     ModelType type,
 948     const sync_pb::DataTypeContext& context) {
 949   ScopedKernelLock lock(this);
 950   kernel_->persisted_info.datatype_context[type].CopyFrom(context);
 951   kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
 952 }
 953
 954 ModelTypeSet Directory::InitialSyncEndedTypes() {
 955   syncable::ReadTransaction trans(FROM_HERE, this);
 956   ModelTypeSet protocol_types = ProtocolTypes();
 957   ModelTypeSet initial_sync_ended_types;
 958   for (ModelTypeSet::Iterator i = protocol_types.First(); i.Good(); i.Inc()) {
 959     if (InitialSyncEndedForType(&trans, i.Get())) {
 960       initial_sync_ended_types.Put(i.Get());
 961     }
 962   }
 963   return initial_sync_ended_types;
 964 }
 965
 966 bool Directory::InitialSyncEndedForType(ModelType type) {
 967   syncable::ReadTransaction trans(FROM_HERE, this);
 968   return InitialSyncEndedForType(&trans, type);
 969 }
 970
 971 bool Directory::InitialSyncEndedForType(
 972     BaseTransaction* trans, ModelType type) {
 973   // True iff the type's root node has been received and applied.
 974   syncable::Entry entry(trans, syncable::GET_TYPE_ROOT, type);
 975   return entry.good() && entry.GetBaseVersion() != CHANGES_VERSION;
 976 }
 977
 978 string Directory::store_birthday() const {
 979   ScopedKernelLock lock(this);
 980   return kernel_->persisted_info.store_birthday;
 981 }
 982
 983 void Directory::set_store_birthday(const string& store_birthday) {
 984   ScopedKernelLock lock(this);
 985   if (kernel_->persisted_info.store_birthday == store_birthday)
 986     return;
 987   kernel_->persisted_info.store_birthday = store_birthday;
 988   kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
 989 }
 990
 991 string Directory::bag_of_chips() const {
 992   ScopedKernelLock lock(this);
 993   return kernel_->persisted_info.bag_of_chips;
 994 }
 995
 996 void Directory::set_bag_of_chips(const string& bag_of_chips) {
 997   ScopedKernelLock lock(this);
 998   if (kernel_->persisted_info.bag_of_chips == bag_of_chips)
 999     return;
1000   kernel_->persisted_info.bag_of_chips = bag_of_chips;
1001   kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
1002 }
1003
1004
1005 string Directory::cache_guid() const {
1006   // No need to lock since nothing ever writes to it after load.
1007   return kernel_->cache_guid;
1008 }
1009
1010 NigoriHandler* Directory::GetNigoriHandler() {
1011   return nigori_handler_;
1012 }
1013
1014 Cryptographer* Directory::GetCryptographer(const BaseTransaction* trans) {
1015   DCHECK_EQ(this, trans->directory());
1016   return cryptographer_;
1017 }
1018
1019 void Directory::GetAllMetaHandles(BaseTransaction* trans,
1020                                   MetahandleSet* result) {
1021   result->clear();
1022   ScopedKernelLock lock(this);
1023   for (MetahandlesMap::iterator i = kernel_->metahandles_map.begin();
1024        i != kernel_->metahandles_map.end(); ++i) {
1025     result->insert(i->first);
1026   }
1027 }
1028
1029 void Directory::GetUnsyncedMetaHandles(BaseTransaction* trans,
1030                                        Metahandles* result) {
1031   result->clear();
1032   ScopedKernelLock lock(this);
1033   copy(kernel_->unsynced_metahandles.begin(),
1034        kernel_->unsynced_metahandles.end(), back_inserter(*result));
1035 }
1036
1037 int64 Directory::unsynced_entity_count() const {
1038   ScopedKernelLock lock(this);
1039   return kernel_->unsynced_metahandles.size();
1040 }
1041
1042 bool Directory::TypeHasUnappliedUpdates(ModelType type) {
1043   ScopedKernelLock lock(this);
1044   return !kernel_->unapplied_update_metahandles[type].empty();
1045 }
1046
1047 void Directory::GetUnappliedUpdateMetaHandles(
1048     BaseTransaction* trans,
1049     FullModelTypeSet server_types,
1050     std::vector<int64>* result) {
1051   result->clear();
1052   ScopedKernelLock lock(this);
1053   for (int i = UNSPECIFIED; i < MODEL_TYPE_COUNT; ++i) {
1054     const ModelType type = ModelTypeFromInt(i);
1055     if (server_types.Has(type)) {
1056       std::copy(kernel_->unapplied_update_metahandles[type].begin(),
1057                 kernel_->unapplied_update_metahandles[type].end(),
1058                 back_inserter(*result));
1059     }
1060   }
1061 }
1062
1063 void Directory::GetMetaHandlesOfType(BaseTransaction* trans,
1064                                      ModelType type,
1065                                      std::vector<int64>* result) {
1066   result->clear();
1067   ScopedKernelLock lock(this);
1068   for (MetahandlesMap::iterator it = kernel_->metahandles_map.begin();
1069        it != kernel_->metahandles_map.end(); ++it) {
1070     EntryKernel* entry = it->second;
1071     const ModelType entry_type =
1072         GetModelTypeFromSpecifics(entry->ref(SPECIFICS));
1073     if (entry_type == type)
1074       result->push_back(it->first);
1075   }
1076 }
1077
1078 void Directory::CollectMetaHandleCounts(
1079     std::vector<int>* num_entries_by_type,
1080     std::vector<int>* num_to_delete_entries_by_type) {
1081   syncable::ReadTransaction trans(FROM_HERE, this);
1082   ScopedKernelLock lock(this);
1083
1084   for (MetahandlesMap::iterator it = kernel_->metahandles_map.begin();
1085        it != kernel_->metahandles_map.end(); ++it) {
1086     EntryKernel* entry = it->second;
1087     const ModelType type = GetModelTypeFromSpecifics(entry->ref(SPECIFICS));
1088     (*num_entries_by_type)[type]++;
1089     if (entry->ref(IS_DEL))
1090       (*num_to_delete_entries_by_type)[type]++;
1091   }
1092 }
1093
1094 scoped_ptr<base::ListValue> Directory::GetNodeDetailsForType(
1095     BaseTransaction* trans,
1096     ModelType type) {
1097   scoped_ptr<base::ListValue> nodes(new base::ListValue());
1098
1099   ScopedKernelLock lock(this);
1100   for (MetahandlesMap::iterator it = kernel_->metahandles_map.begin();
1101        it != kernel_->metahandles_map.end(); ++it) {
1102     if (GetModelTypeFromSpecifics(it->second->ref(SPECIFICS)) != type) {
1103       continue;
1104     }
1105
1106     EntryKernel* kernel = it->second;
1107     scoped_ptr<base::DictionaryValue> node(
1108         kernel->ToValue(GetCryptographer(trans)));
1109
1110     // Add the position index if appropriate.  This must be done here (and not
1111     // in EntryKernel) because the EntryKernel does not have access to its
1112     // siblings.
1113     if (kernel->ShouldMaintainPosition() && !kernel->ref(IS_DEL)) {
1114       node->SetInteger("positionIndex", GetPositionIndex(trans, kernel));
1115     }
1116
1117     nodes->Append(node.release());
1118   }
1119
1120   return nodes.Pass();
1121 }
1122
1123 bool Directory::CheckInvariantsOnTransactionClose(
1124     syncable::BaseTransaction* trans,
1125     const MetahandleSet& modified_handles) {
1126   // NOTE: The trans may be in the process of being destructed.  Be careful if
1127   // you wish to call any of its virtual methods.
1128   switch (invariant_check_level_) {
1129     case FULL_DB_VERIFICATION: {
1130       MetahandleSet all_handles;
1131       GetAllMetaHandles(trans, &all_handles);
1132       return CheckTreeInvariants(trans, all_handles);
1133     }
1134     case VERIFY_CHANGES: {
1135       return CheckTreeInvariants(trans, modified_handles);
1136     }
1137     case OFF: {
1138       return true;
1139     }
1140   }
1141   NOTREACHED();
1142   return false;
1143 }
1144
1145 bool Directory::FullyCheckTreeInvariants(syncable::BaseTransaction* trans) {
1146   MetahandleSet handles;
1147   GetAllMetaHandles(trans, &handles);
1148   return CheckTreeInvariants(trans, handles);
1149 }
1150
1151 bool Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
1152                                     const MetahandleSet& handles) {
1153   MetahandleSet::const_iterator i;
1154   for (i = handles.begin() ; i != handles.end() ; ++i) {
1155     int64 metahandle = *i;
1156     Entry e(trans, GET_BY_HANDLE, metahandle);
1157     if (!SyncAssert(e.good(), FROM_HERE, "Entry is bad", trans))
1158       return false;
1159     syncable::Id id = e.GetId();
1160     syncable::Id parentid = e.GetParentId();
1161
1162     if (id.IsRoot()) {
1163       if (!SyncAssert(e.GetIsDir(), FROM_HERE,
1164                       "Entry should be a directory",
1165                       trans))
1166         return false;
1167       if (!SyncAssert(parentid.IsRoot(), FROM_HERE,
1168                       "Entry should be root",
1169                       trans))
1170          return false;
1171       if (!SyncAssert(!e.GetIsUnsynced(), FROM_HERE,
1172                       "Entry should be sycned",
1173                       trans))
1174          return false;
1175       continue;
1176     }
1177
1178     if (!e.GetIsDel()) {
1179       if (!SyncAssert(id != parentid, FROM_HERE,
1180                       "Id should be different from parent id.",
1181                       trans))
1182          return false;
1183       if (!SyncAssert(!e.GetNonUniqueName().empty(), FROM_HERE,
1184                       "Non unique name should not be empty.",
1185                       trans))
1186         return false;
1187       int safety_count = handles.size() + 1;
1188       while (!parentid.IsRoot()) {
1189         Entry parent(trans, GET_BY_ID, parentid);
1190         if (!SyncAssert(parent.good(), FROM_HERE,
1191                         "Parent entry is not valid.",
1192                         trans))
1193           return false;
1194         if (handles.end() == handles.find(parent.GetMetahandle()))
1195             break; // Skip further checking if parent was unmodified.
1196         if (!SyncAssert(parent.GetIsDir(), FROM_HERE,
1197                         "Parent should be a directory",
1198                         trans))
1199           return false;
1200         if (!SyncAssert(!parent.GetIsDel(), FROM_HERE,
1201                         "Parent should not have been marked for deletion.",
1202                         trans))
1203           return false;
1204         if (!SyncAssert(handles.end() != handles.find(parent.GetMetahandle()),
1205                         FROM_HERE,
1206                         "Parent should be in the index.",
1207                         trans))
1208           return false;
1209         parentid = parent.GetParentId();
1210         if (!SyncAssert(--safety_count > 0, FROM_HERE,
1211                         "Count should be greater than zero.",
1212                         trans))
1213           return false;
1214       }
1215     }
1216     int64 base_version = e.GetBaseVersion();
1217     int64 server_version = e.GetServerVersion();
1218     bool using_unique_client_tag = !e.GetUniqueClientTag().empty();
1219     if (CHANGES_VERSION == base_version || 0 == base_version) {
1220       if (e.GetIsUnappliedUpdate()) {
1221         // Must be a new item, or a de-duplicated unique client tag
1222         // that was created both locally and remotely.
1223         if (!using_unique_client_tag) {
1224           if (!SyncAssert(e.GetIsDel(), FROM_HERE,
1225                           "The entry should not have been deleted.",
1226                           trans))
1227             return false;
1228         }
1229         // It came from the server, so it must have a server ID.
1230         if (!SyncAssert(id.ServerKnows(), FROM_HERE,
1231                         "The id should be from a server.",
1232                         trans))
1233           return false;
1234       } else {
1235         if (e.GetIsDir()) {
1236           // TODO(chron): Implement this mode if clients ever need it.
1237           // For now, you can't combine a client tag and a directory.
1238           if (!SyncAssert(!using_unique_client_tag, FROM_HERE,
1239                           "Directory cannot have a client tag.",
1240                           trans))
1241             return false;
1242         }
1243         // Should be an uncomitted item, or a successfully deleted one.
1244         if (!e.GetIsDel()) {
1245           if (!SyncAssert(e.GetIsUnsynced(), FROM_HERE,
1246                           "The item should be unsynced.",
1247                           trans))
1248             return false;
1249         }
1250         // If the next check failed, it would imply that an item exists
1251         // on the server, isn't waiting for application locally, but either
1252         // is an unsynced create or a sucessful delete in the local copy.
1253         // Either way, that's a mismatch.
1254         if (!SyncAssert(0 == server_version, FROM_HERE,
1255                         "Server version should be zero.",
1256                         trans))
1257           return false;
1258         // Items that aren't using the unique client tag should have a zero
1259         // base version only if they have a local ID.  Items with unique client
1260         // tags are allowed to use the zero base version for undeletion and
1261         // de-duplication; the unique client tag trumps the server ID.
1262         if (!using_unique_client_tag) {
1263           if (!SyncAssert(!id.ServerKnows(), FROM_HERE,
1264                           "Should be a client only id.",
1265                           trans))
1266             return false;
1267         }
1268       }
1269     } else {
1270       if (!SyncAssert(id.ServerKnows(),
1271                       FROM_HERE,
1272                       "Should be a server id.",
1273                       trans))
1274         return false;
1275     }
1276     // Server-unknown items that are locally deleted should not be sent up to
1277     // the server.  They must be !IS_UNSYNCED.
1278     if (!SyncAssert(!(!id.ServerKnows() && e.GetIsDel() && e.GetIsUnsynced()),
1279                     FROM_HERE,
1280                     "Locally deleted item must not be unsynced.",
1281                     trans)) {
1282       return false;
1283     }
1284   }
1285   return true;
1286 }
1287
1288 void Directory::SetInvariantCheckLevel(InvariantCheckLevel check_level) {
1289   invariant_check_level_ = check_level;
1290 }
1291
1292 int64 Directory::NextMetahandle() {
1293   ScopedKernelLock lock(this);
1294   int64 metahandle = (kernel_->next_metahandle)++;
1295   return metahandle;
1296 }
1297
1298 // Always returns a client ID that is the string representation of a negative
1299 // number.
1300 Id Directory::NextId() {
1301   int64 result;
1302   {
1303     ScopedKernelLock lock(this);
1304     result = (kernel_->persisted_info.next_id)--;
1305     kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
1306   }
1307   DCHECK_LT(result, 0);
1308   return Id::CreateFromClientString(base::Int64ToString(result));
1309 }
1310
1311 bool Directory::HasChildren(BaseTransaction* trans, const Id& id) {
1312   ScopedKernelLock lock(this);
1313   return kernel_->parent_child_index.GetChildren(id) != NULL;
1314 }
1315
1316 Id Directory::GetFirstChildId(BaseTransaction* trans,
1317                               const EntryKernel* parent) {
1318   DCHECK(parent);
1319   DCHECK(parent->ref(IS_DIR));
1320
1321   ScopedKernelLock lock(this);
1322   const OrderedChildSet* children =
1323       kernel_->parent_child_index.GetChildren(parent->ref(ID));
1324
1325   // We're expected to return root if there are no children.
1326   if (!children)
1327     return Id();
1328
1329   return (*children->begin())->ref(ID);
1330 }
1331
1332 syncable::Id Directory::GetPredecessorId(EntryKernel* e) {
1333   ScopedKernelLock lock(this);
1334
1335   DCHECK(ParentChildIndex::ShouldInclude(e));
1336   const OrderedChildSet* children =
1337       kernel_->parent_child_index.GetChildren(e->ref(PARENT_ID));
1338   DCHECK(children && !children->empty());
1339   OrderedChildSet::const_iterator i = children->find(e);
1340   DCHECK(i != children->end());
1341
1342   if (i == children->begin()) {
1343     return Id();
1344   } else {
1345     i--;
1346     return (*i)->ref(ID);
1347   }
1348 }
1349
1350 syncable::Id Directory::GetSuccessorId(EntryKernel* e) {
1351   ScopedKernelLock lock(this);
1352
1353   DCHECK(ParentChildIndex::ShouldInclude(e));
1354   const OrderedChildSet* children =
1355       kernel_->parent_child_index.GetChildren(e->ref(PARENT_ID));
1356   DCHECK(children && !children->empty());
1357   OrderedChildSet::const_iterator i = children->find(e);
1358   DCHECK(i != children->end());
1359
1360   i++;
1361   if (i == children->end()) {
1362     return Id();
1363   } else {
1364     return (*i)->ref(ID);
1365   }
1366 }
1367
1368 // TODO(rlarocque): Remove all support for placing ShouldMaintainPosition()
1369 // items as siblings of items that do not maintain postions.  It is required
1370 // only for tests.  See crbug.com/178282.
1371 void Directory::PutPredecessor(EntryKernel* e, EntryKernel* predecessor) {
1372   DCHECK(!e->ref(IS_DEL));
1373   if (!e->ShouldMaintainPosition()) {
1374     DCHECK(!e->ref(UNIQUE_POSITION).IsValid());
1375     return;
1376   }
1377   std::string suffix = e->ref(UNIQUE_BOOKMARK_TAG);
1378   DCHECK(!suffix.empty());
1379
1380   // Remove our item from the ParentChildIndex and remember to re-add it later.
1381   ScopedKernelLock lock(this);
1382   ScopedParentChildIndexUpdater updater(lock, e, &kernel_->parent_child_index);
1383
1384   // Note: The ScopedParentChildIndexUpdater will update this set for us as we
1385   // leave this function.
1386   const OrderedChildSet* siblings =
1387       kernel_->parent_child_index.GetChildren(e->ref(PARENT_ID));
1388
1389   if (!siblings) {
1390     // This parent currently has no other children.
1391     DCHECK(predecessor->ref(ID).IsRoot());
1392     UniquePosition pos = UniquePosition::InitialPosition(suffix);
1393     e->put(UNIQUE_POSITION, pos);
1394     return;
1395   }
1396
1397   if (predecessor->ref(ID).IsRoot()) {
1398     // We have at least one sibling, and we're inserting to the left of them.
1399     UniquePosition successor_pos = (*siblings->begin())->ref(UNIQUE_POSITION);
1400
1401     UniquePosition pos;
1402     if (!successor_pos.IsValid()) {
1403       // If all our successors are of non-positionable types, just create an
1404       // initial position.  We arbitrarily choose to sort invalid positions to
1405       // the right of the valid positions.
1406       //
1407       // We really shouldn't need to support this.  See TODO above.
1408       pos = UniquePosition::InitialPosition(suffix);
1409     } else  {
1410       DCHECK(!siblings->empty());
1411       pos = UniquePosition::Before(successor_pos, suffix);
1412     }
1413
1414     e->put(UNIQUE_POSITION, pos);
1415     return;
1416   }
1417
1418   // We can't support placing an item after an invalid position.  Fortunately,
1419   // the tests don't exercise this particular case.  We should not support
1420   // siblings with invalid positions at all.  See TODO above.
1421   DCHECK(predecessor->ref(UNIQUE_POSITION).IsValid());
1422
1423   OrderedChildSet::const_iterator neighbour = siblings->find(predecessor);
1424   DCHECK(neighbour != siblings->end());
1425
1426   ++neighbour;
1427   if (neighbour == siblings->end()) {
1428     // Inserting at the end of the list.
1429     UniquePosition pos = UniquePosition::After(
1430         predecessor->ref(UNIQUE_POSITION),
1431         suffix);
1432     e->put(UNIQUE_POSITION, pos);
1433     return;
1434   }
1435
1436   EntryKernel* successor = *neighbour;
1437
1438   // Another mixed valid and invalid position case.  This one could be supported
1439   // in theory, but we're trying to deprecate support for siblings with and
1440   // without valid positions.  See TODO above.
1441   DCHECK(successor->ref(UNIQUE_POSITION).IsValid());
1442
1443   // Finally, the normal case: inserting between two elements.
1444   UniquePosition pos = UniquePosition::Between(
1445       predecessor->ref(UNIQUE_POSITION),
1446       successor->ref(UNIQUE_POSITION),
1447       suffix);
1448   e->put(UNIQUE_POSITION, pos);
1449   return;
1450 }
1451
1452 // TODO(rlarocque): Avoid this indirection.  Just return the set.
1453 void Directory::AppendChildHandles(const ScopedKernelLock& lock,
1454                                    const Id& parent_id,
1455                                    Directory::Metahandles* result) {
1456   const OrderedChildSet* children =
1457       kernel_->parent_child_index.GetChildren(parent_id);
1458   if (!children)
1459     return;
1460
1461   for (OrderedChildSet::const_iterator i = children->begin();
1462        i != children->end(); ++i) {
1463     DCHECK_EQ(parent_id, (*i)->ref(PARENT_ID));
1464     result->push_back((*i)->ref(META_HANDLE));
1465   }
1466 }
1467
1468 void Directory::UnmarkDirtyEntry(WriteTransaction* trans, Entry* entry) {
1469   CHECK(trans);
1470   entry->kernel_->clear_dirty(&kernel_->dirty_metahandles);
1471 }
1472
1473 }  // namespace syncable
1474 }  // namespace syncer