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