// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "sync/syncable/directory.h"

#include "base/base64.h"
#include "base/debug/trace_event.h"
#include "base/stl_util.h"
#include "base/string_number_conversions.h"
#include "sync/internal_api/public/base/unique_position.h"
#include "sync/internal_api/public/util/unrecoverable_error_handler.h"
#include "sync/syncable/entry.h"
#include "sync/syncable/entry_kernel.h"
#include "sync/syncable/in_memory_directory_backing_store.h"
#include "sync/syncable/on_disk_directory_backing_store.h"
#include "sync/syncable/scoped_index_updater.h"
#include "sync/syncable/scoped_parent_child_index_updater.h"
#include "sync/syncable/syncable-inl.h"
#include "sync/syncable/syncable_base_transaction.h"
#include "sync/syncable/syncable_changes_version.h"
#include "sync/syncable/syncable_read_transaction.h"
#include "sync/syncable/syncable_util.h"
#include "sync/syncable/syncable_write_transaction.h"

using std::string;

namespace syncer {
namespace syncable {

namespace {
// Helper function to add an item to the index, if it ought to be added.
template<typename Indexer>
void InitializeIndexEntry(EntryKernel* entry,
                          typename Index<Indexer>::Set* index) {
  if (Indexer::ShouldInclude(entry)) {
    index->insert(entry);
  }
}
}

// static
bool ClientTagIndexer::ShouldInclude(const EntryKernel* a) {
  return !a->ref(UNIQUE_CLIENT_TAG).empty();
}

// static
const base::FilePath::CharType Directory::kSyncDatabaseFilename[] =
    FILE_PATH_LITERAL("SyncData.sqlite3");

void Directory::InitKernelForTest(
    const std::string& name,
    DirectoryChangeDelegate* delegate,
    const WeakHandle<TransactionObserver>& transaction_observer) {
  DCHECK(!kernel_);
  kernel_ = new Kernel(name, KernelLoadInfo(), delegate, transaction_observer);
}

Directory::PersistedKernelInfo::PersistedKernelInfo()
    : next_id(0) {
  ModelTypeSet protocol_types = ProtocolTypes();
  for (ModelTypeSet::Iterator iter = protocol_types.First(); iter.Good();
       iter.Inc()) {
    reset_download_progress(iter.Get());
    transaction_version[iter.Get()] = 0;
  }
}

Directory::PersistedKernelInfo::~PersistedKernelInfo() {}

void Directory::PersistedKernelInfo::reset_download_progress(
    ModelType model_type) {
  download_progress[model_type].set_data_type_id(
      GetSpecificsFieldNumberFromModelType(model_type));
  // An empty-string token indicates no prior knowledge.
  download_progress[model_type].set_token(std::string());
}

Directory::SaveChangesSnapshot::SaveChangesSnapshot()
    : kernel_info_status(KERNEL_SHARE_INFO_INVALID) {
}

Directory::SaveChangesSnapshot::~SaveChangesSnapshot() {
  STLDeleteElements(&dirty_metas);
  STLDeleteElements(&delete_journals);
}

Directory::Kernel::Kernel(
    const std::string& name,
    const KernelLoadInfo& info, DirectoryChangeDelegate* delegate,
    const WeakHandle<TransactionObserver>& transaction_observer)
    : next_write_transaction_id(0),
      name(name),
      metahandles_index(new Directory::MetahandlesIndex),
      ids_index(new Directory::IdsIndex),
      parent_child_index(new ParentChildIndex),
      client_tag_index(new Directory::ClientTagIndex),
      unsynced_metahandles(new MetahandleSet),
      dirty_metahandles(new MetahandleSet),
      metahandles_to_purge(new MetahandleSet),
      info_status(Directory::KERNEL_SHARE_INFO_VALID),
      persisted_info(info.kernel_info),
      cache_guid(info.cache_guid),
      next_metahandle(info.max_metahandle + 1),
      delegate(delegate),
      transaction_observer(transaction_observer) {
  DCHECK(delegate);
  DCHECK(transaction_observer.IsInitialized());
}

Directory::Kernel::~Kernel() {
  delete unsynced_metahandles;
  delete dirty_metahandles;
  delete metahandles_to_purge;
  delete parent_child_index;
  delete client_tag_index;
  delete ids_index;
  STLDeleteElements(metahandles_index);
  delete metahandles_index;
}

Directory::Directory(
    DirectoryBackingStore* store,
    UnrecoverableErrorHandler* unrecoverable_error_handler,
    ReportUnrecoverableErrorFunction report_unrecoverable_error_function,
    NigoriHandler* nigori_handler,
    Cryptographer* cryptographer)
    : kernel_(NULL),
      store_(store),
      unrecoverable_error_handler_(unrecoverable_error_handler),
      report_unrecoverable_error_function_(
          report_unrecoverable_error_function),
      unrecoverable_error_set_(false),
      nigori_handler_(nigori_handler),
      cryptographer_(cryptographer),
      invariant_check_level_(VERIFY_CHANGES) {
}

Directory::~Directory() {
  Close();
}

DirOpenResult Directory::Open(
    const string& name,
    DirectoryChangeDelegate* delegate,
    const WeakHandle<TransactionObserver>& transaction_observer) {
  TRACE_EVENT0("sync", "SyncDatabaseOpen");

  const DirOpenResult result =
      OpenImpl(name, delegate, transaction_observer);

  if (OPENED != result)
    Close();
  return result;
}

void Directory::InitializeIndices() {
  MetahandlesIndex::iterator it = kernel_->metahandles_index->begin();
  for (; it != kernel_->metahandles_index->end(); ++it) {
    EntryKernel* entry = *it;
    if (ParentChildIndex::ShouldInclude(entry))
      kernel_->parent_child_index->Insert(entry);
    InitializeIndexEntry<IdIndexer>(entry, kernel_->ids_index);
    InitializeIndexEntry<ClientTagIndexer>(entry, kernel_->client_tag_index);
    const int64 metahandle = entry->ref(META_HANDLE);
    if (entry->ref(IS_UNSYNCED))
      kernel_->unsynced_metahandles->insert(metahandle);
    if (entry->ref(IS_UNAPPLIED_UPDATE)) {
      const ModelType type = entry->GetServerModelType();
      kernel_->unapplied_update_metahandles[type].insert(metahandle);
    }
    DCHECK(!entry->is_dirty());
  }
}

DirOpenResult Directory::OpenImpl(
    const string& name,
    DirectoryChangeDelegate* delegate,
    const WeakHandle<TransactionObserver>&
        transaction_observer) {
  KernelLoadInfo info;
  // Temporary indices before kernel_ initialized in case Load fails. We 0(1)
  // swap these later.
  MetahandlesIndex metas_bucket;
  JournalIndex delete_journals;

  DirOpenResult result = store_->Load(&metas_bucket, &delete_journals, &info);
  if (OPENED != result)
    return result;

  kernel_ = new Kernel(name, info, delegate, transaction_observer);
  kernel_->metahandles_index->swap(metas_bucket);
  delete_journal_.reset(new DeleteJournal(&delete_journals));
  InitializeIndices();

  // Write back the share info to reserve some space in 'next_id'.  This will
  // prevent local ID reuse in the case of an early crash.  See the comments in
  // TakeSnapshotForSaveChanges() or crbug.com/142987 for more information.
  kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
  if (!SaveChanges())
    return FAILED_INITIAL_WRITE;

  return OPENED;
}

DeleteJournal* Directory::delete_journal() {
  DCHECK(delete_journal_.get());
  return delete_journal_.get();
}

void Directory::Close() {
  store_.reset();
  if (kernel_) {
    delete kernel_;
    kernel_ = NULL;
  }
}

void Directory::OnUnrecoverableError(const BaseTransaction* trans,
                                     const tracked_objects::Location& location,
                                     const std::string & message) {
  DCHECK(trans != NULL);
  unrecoverable_error_set_ = true;
  unrecoverable_error_handler_->OnUnrecoverableError(location,
                                                     message);
}

EntryKernel* Directory::GetEntryById(const Id& id) {
  ScopedKernelLock lock(this);
  return GetEntryById(id, &lock);
}

EntryKernel* Directory::GetEntryById(const Id& id,
                                     ScopedKernelLock* const lock) {
  DCHECK(kernel_);
  // Find it in the in memory ID index.
  kernel_->needle.put(ID, id);
  IdsIndex::iterator id_found = kernel_->ids_index->find(&kernel_->needle);
  if (id_found != kernel_->ids_index->end()) {
    return *id_found;
  }
  return NULL;
}

EntryKernel* Directory::GetEntryByClientTag(const string& tag) {
  ScopedKernelLock lock(this);
  DCHECK(kernel_);
  // Find it in the ClientTagIndex.
  kernel_->needle.put(UNIQUE_CLIENT_TAG, tag);
  ClientTagIndex::iterator found = kernel_->client_tag_index->find(
      &kernel_->needle);
  if (found != kernel_->client_tag_index->end()) {
    return *found;
  }
  return NULL;
}

EntryKernel* Directory::GetEntryByServerTag(const string& tag) {
  ScopedKernelLock lock(this);
  DCHECK(kernel_);
  // We don't currently keep a separate index for the tags.  Since tags
  // only exist for server created items that are the first items
  // to be created in a store, they should have small metahandles.
  // So, we just iterate over the items in sorted metahandle order,
  // looking for a match.
  MetahandlesIndex& set = *kernel_->metahandles_index;
  for (MetahandlesIndex::iterator i = set.begin(); i != set.end(); ++i) {
    if ((*i)->ref(UNIQUE_SERVER_TAG) == tag) {
      return *i;
    }
  }
  return NULL;
}

EntryKernel* Directory::GetEntryByHandle(int64 metahandle) {
  ScopedKernelLock lock(this);
  return GetEntryByHandle(metahandle, &lock);
}

EntryKernel* Directory::GetEntryByHandle(int64 metahandle,
                                         ScopedKernelLock* lock) {
  // Look up in memory
  kernel_->needle.put(META_HANDLE, metahandle);
  MetahandlesIndex::iterator found =
      kernel_->metahandles_index->find(&kernel_->needle);
  if (found != kernel_->metahandles_index->end()) {
    // Found it in memory.  Easy.
    return *found;
  }
  return NULL;
}

bool Directory::GetChildHandlesById(
    BaseTransaction* trans, const Id& parent_id,
    Directory::ChildHandles* result) {
  if (!SyncAssert(this == trans->directory(), FROM_HERE,
                  "Directories don't match", trans))
    return false;
  result->clear();

  ScopedKernelLock lock(this);
  AppendChildHandles(lock, parent_id, result);
  return true;
}

bool Directory::GetChildHandlesByHandle(
    BaseTransaction* trans, int64 handle,
    Directory::ChildHandles* result) {
  if (!SyncAssert(this == trans->directory(), FROM_HERE,
                  "Directories don't match", trans))
    return false;

  result->clear();

  ScopedKernelLock lock(this);
  EntryKernel* kernel = GetEntryByHandle(handle, &lock);
  if (!kernel)
    return true;

  AppendChildHandles(lock, kernel->ref(ID), result);
  return true;
}

EntryKernel* Directory::GetRootEntry() {
  return GetEntryById(Id());
}

bool Directory::InsertEntry(WriteTransaction* trans, EntryKernel* entry) {
  ScopedKernelLock lock(this);
  return InsertEntry(trans, entry, &lock);
}

bool Directory::InsertEntry(WriteTransaction* trans,
                            EntryKernel* entry,
                            ScopedKernelLock* lock) {
  DCHECK(NULL != lock);
  if (!SyncAssert(NULL != entry, FROM_HERE, "Entry is null", trans))
    return false;

  static const char error[] = "Entry already in memory index.";
  if (!SyncAssert(kernel_->metahandles_index->insert(entry).second,
                  FROM_HERE,
                  error,
                  trans))
    return false;

  if (ParentChildIndex::ShouldInclude(entry)) {
    if (!SyncAssert(kernel_->parent_child_index->Insert(entry),
                    FROM_HERE,
                    error,
                    trans)) {
      return false;
    }
  }
  if (!SyncAssert(kernel_->ids_index->insert(entry).second,
                  FROM_HERE,
                  error,
                  trans))
    return false;

  // Should NEVER be created with a client tag.
  if (!SyncAssert(entry->ref(UNIQUE_CLIENT_TAG).empty(), FROM_HERE,
                  "Client should be empty", trans))
    return false;

  return true;
}

bool Directory::ReindexId(WriteTransaction* trans,
                         EntryKernel* const entry,
                         const Id& new_id) {
  ScopedKernelLock lock(this);
  if (NULL != GetEntryById(new_id, &lock))
    return false;

  {
    // Update the indices that depend on the ID field.
    ScopedIndexUpdater<IdIndexer> updater_a(lock, entry, kernel_->ids_index);
    ScopedParentChildIndexUpdater updater_b(lock, entry,
        kernel_->parent_child_index);
    entry->put(ID, new_id);
  }
  return true;
}

bool Directory::ReindexParentId(WriteTransaction* trans,
                                EntryKernel* const entry,
                                const Id& new_parent_id) {
  ScopedKernelLock lock(this);

  {
    // Update the indices that depend on the PARENT_ID field.
    ScopedParentChildIndexUpdater index_updater(lock, entry,
        kernel_->parent_child_index);
    entry->put(PARENT_ID, new_parent_id);
  }
  return true;
}

bool Directory::unrecoverable_error_set(const BaseTransaction* trans) const {
  DCHECK(trans != NULL);
  return unrecoverable_error_set_;
}

void Directory::ClearDirtyMetahandles() {
  kernel_->transaction_mutex.AssertAcquired();
  kernel_->dirty_metahandles->clear();
}

bool Directory::SafeToPurgeFromMemory(WriteTransaction* trans,
                                      const EntryKernel* const entry) const {
  bool safe = entry->ref(IS_DEL) && !entry->is_dirty() &&
      !entry->ref(SYNCING) && !entry->ref(IS_UNAPPLIED_UPDATE) &&
      !entry->ref(IS_UNSYNCED);

  if (safe) {
    int64 handle = entry->ref(META_HANDLE);
    const ModelType type = entry->GetServerModelType();
    if (!SyncAssert(kernel_->dirty_metahandles->count(handle) == 0U,
                    FROM_HERE,
                    "Dirty metahandles should be empty", trans))
      return false;
    // TODO(tim): Bug 49278.
    if (!SyncAssert(!kernel_->unsynced_metahandles->count(handle),
                    FROM_HERE,
                    "Unsynced handles should be empty",
                    trans))
      return false;
    if (!SyncAssert(!kernel_->unapplied_update_metahandles[type].count(handle),
                    FROM_HERE,
                    "Unapplied metahandles should be empty",
                    trans))
      return false;
  }

  return safe;
}

void Directory::TakeSnapshotForSaveChanges(SaveChangesSnapshot* snapshot) {
  ReadTransaction trans(FROM_HERE, this);
  ScopedKernelLock lock(this);

  // If there is an unrecoverable error then just bail out.
  if (unrecoverable_error_set(&trans))
    return;

  // Deep copy dirty entries from kernel_->metahandles_index into snapshot and
  // clear dirty flags.
  for (MetahandleSet::const_iterator i = kernel_->dirty_metahandles->begin();
       i != kernel_->dirty_metahandles->end(); ++i) {
    EntryKernel* entry = GetEntryByHandle(*i, &lock);
    if (!entry)
      continue;
    // Skip over false positives; it happens relatively infrequently.
    if (!entry->is_dirty())
      continue;
    snapshot->dirty_metas.insert(snapshot->dirty_metas.end(),
                                 new EntryKernel(*entry));
    DCHECK_EQ(1U, kernel_->dirty_metahandles->count(*i));
    // We don't bother removing from the index here as we blow the entire thing
    // in a moment, and it unnecessarily complicates iteration.
    entry->clear_dirty(NULL);
  }
  ClearDirtyMetahandles();

  // Set purged handles.
  DCHECK(snapshot->metahandles_to_purge.empty());
  snapshot->metahandles_to_purge.swap(*(kernel_->metahandles_to_purge));

  // Fill kernel_info_status and kernel_info.
  snapshot->kernel_info = kernel_->persisted_info;
  // To avoid duplicates when the process crashes, we record the next_id to be
  // greater magnitude than could possibly be reached before the next save
  // changes.  In other words, it's effectively impossible for the user to
  // generate 65536 new bookmarks in 3 seconds.
  snapshot->kernel_info.next_id -= 65536;
  snapshot->kernel_info_status = kernel_->info_status;
  // This one we reset on failure.
  kernel_->info_status = KERNEL_SHARE_INFO_VALID;

  delete_journal_->TakeSnapshotAndClear(
      &trans, &snapshot->delete_journals, &snapshot->delete_journals_to_purge);
}

bool Directory::SaveChanges() {
  bool success = false;

  base::AutoLock scoped_lock(kernel_->save_changes_mutex);

  // Snapshot and save.
  SaveChangesSnapshot snapshot;
  TakeSnapshotForSaveChanges(&snapshot);
  success = store_->SaveChanges(snapshot);

  // Handle success or failure.
  if (success)
    success = VacuumAfterSaveChanges(snapshot);
  else
    HandleSaveChangesFailure(snapshot);
  return success;
}

bool Directory::VacuumAfterSaveChanges(const SaveChangesSnapshot& snapshot) {
  if (snapshot.dirty_metas.empty())
    return true;

  // Need a write transaction as we are about to permanently purge entries.
  WriteTransaction trans(FROM_HERE, VACUUM_AFTER_SAVE, this);
  ScopedKernelLock lock(this);
  // Now drop everything we can out of memory.
  for (EntryKernelSet::const_iterator i = snapshot.dirty_metas.begin();
       i != snapshot.dirty_metas.end(); ++i) {
    kernel_->needle.put(META_HANDLE, (*i)->ref(META_HANDLE));
    MetahandlesIndex::iterator found =
        kernel_->metahandles_index->find(&kernel_->needle);
    EntryKernel* entry = (found == kernel_->metahandles_index->end() ?
                          NULL : *found);
    if (entry && SafeToPurgeFromMemory(&trans, entry)) {
      // We now drop deleted metahandles that are up to date on both the client
      // and the server.
      size_t num_erased = 0;
      num_erased = kernel_->ids_index->erase(entry);
      DCHECK_EQ(1u, num_erased);
      num_erased = kernel_->metahandles_index->erase(entry);
      DCHECK_EQ(1u, num_erased);

      // Might not be in it
      num_erased = kernel_->client_tag_index->erase(entry);
      DCHECK_EQ(entry->ref(UNIQUE_CLIENT_TAG).empty(), !num_erased);
      if (!SyncAssert(!kernel_->parent_child_index->Contains(entry),
                      FROM_HERE,
                      "Deleted entry still present",
                      (&trans)))
        return false;
      delete entry;
    }
    if (trans.unrecoverable_error_set())
      return false;
  }
  return true;
}

bool Directory::PurgeEntriesWithTypeIn(ModelTypeSet types,
                                       ModelTypeSet types_to_journal) {
  types.RemoveAll(ProxyTypes());

  if (types.Empty())
    return true;

  {
    WriteTransaction trans(FROM_HERE, PURGE_ENTRIES, this);

    EntryKernelSet entries_to_journal;
    STLElementDeleter<EntryKernelSet> journal_deleter(&entries_to_journal);

    {
      ScopedKernelLock lock(this);
      MetahandlesIndex::iterator it = kernel_->metahandles_index->begin();
      while (it != kernel_->metahandles_index->end()) {
        const sync_pb::EntitySpecifics& local_specifics = (*it)->ref(SPECIFICS);
        const sync_pb::EntitySpecifics& server_specifics =
            (*it)->ref(SERVER_SPECIFICS);
        ModelType local_type = GetModelTypeFromSpecifics(local_specifics);
        ModelType server_type = GetModelTypeFromSpecifics(server_specifics);

        // Note the dance around incrementing |it|, since we sometimes erase().
        if ((IsRealDataType(local_type) && types.Has(local_type)) ||
            (IsRealDataType(server_type) && types.Has(server_type))) {

          int64 handle = (*it)->ref(META_HANDLE);
          kernel_->metahandles_to_purge->insert(handle);

          size_t num_erased = 0;
          EntryKernel* entry = *it;
          num_erased = kernel_->ids_index->erase(entry);
          DCHECK_EQ(1u, num_erased);
          num_erased = kernel_->client_tag_index->erase(entry);
          DCHECK_EQ(entry->ref(UNIQUE_CLIENT_TAG).empty(), !num_erased);
          num_erased = kernel_->unsynced_metahandles->erase(handle);
          DCHECK_EQ(entry->ref(IS_UNSYNCED), num_erased > 0);
          num_erased =
              kernel_->unapplied_update_metahandles[server_type].erase(handle);
          DCHECK_EQ(entry->ref(IS_UNAPPLIED_UPDATE), num_erased > 0);
          if (kernel_->parent_child_index->Contains(entry))
            kernel_->parent_child_index->Remove(entry);
          kernel_->metahandles_index->erase(it++);

          if ((types_to_journal.Has(local_type) ||
              types_to_journal.Has(server_type)) &&
              (delete_journal_->IsDeleteJournalEnabled(local_type) ||
                  delete_journal_->IsDeleteJournalEnabled(server_type))) {
            entries_to_journal.insert(entry);
          } else {
            delete entry;
          }
        } else {
          ++it;
        }
      }

      delete_journal_->AddJournalBatch(&trans, entries_to_journal);

      // Ensure meta tracking for these data types reflects the deleted state.
      for (ModelTypeSet::Iterator it = types.First();
           it.Good(); it.Inc()) {
        kernel_->persisted_info.reset_download_progress(it.Get());
        kernel_->persisted_info.transaction_version[it.Get()] = 0;
      }
    }
  }
  return true;
}

void Directory::HandleSaveChangesFailure(const SaveChangesSnapshot& snapshot) {
  WriteTransaction trans(FROM_HERE, HANDLE_SAVE_FAILURE, this);
  ScopedKernelLock lock(this);
  kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;

  // Because we optimistically cleared the dirty bit on the real entries when
  // taking the snapshot, we must restore it on failure.  Not doing this could
  // cause lost data, if no other changes are made to the in-memory entries
  // that would cause the dirty bit to get set again. Setting the bit ensures
  // that SaveChanges will at least try again later.
  for (EntryKernelSet::const_iterator i = snapshot.dirty_metas.begin();
       i != snapshot.dirty_metas.end(); ++i) {
    kernel_->needle.put(META_HANDLE, (*i)->ref(META_HANDLE));
    MetahandlesIndex::iterator found =
        kernel_->metahandles_index->find(&kernel_->needle);
    if (found != kernel_->metahandles_index->end()) {
      (*found)->mark_dirty(kernel_->dirty_metahandles);
    }
  }

  kernel_->metahandles_to_purge->insert(snapshot.metahandles_to_purge.begin(),
                                        snapshot.metahandles_to_purge.end());

  // Restore delete journals.
  delete_journal_->AddJournalBatch(&trans, snapshot.delete_journals);
  delete_journal_->PurgeDeleteJournals(&trans,
                                       snapshot.delete_journals_to_purge);
}

void Directory::GetDownloadProgress(
    ModelType model_type,
    sync_pb::DataTypeProgressMarker* value_out) const {
  ScopedKernelLock lock(this);
  return value_out->CopyFrom(
      kernel_->persisted_info.download_progress[model_type]);
}

void Directory::GetDownloadProgressAsString(
    ModelType model_type,
    std::string* value_out) const {
  ScopedKernelLock lock(this);
  kernel_->persisted_info.download_progress[model_type].SerializeToString(
      value_out);
}

size_t Directory::GetEntriesCount() const {
  ScopedKernelLock lock(this);
  return kernel_->metahandles_index ? kernel_->metahandles_index->size() : 0;
}

void Directory::SetDownloadProgress(
    ModelType model_type,
    const sync_pb::DataTypeProgressMarker& new_progress) {
  ScopedKernelLock lock(this);
  kernel_->persisted_info.download_progress[model_type].CopyFrom(new_progress);
  kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}

int64 Directory::GetTransactionVersion(ModelType type) const {
  kernel_->transaction_mutex.AssertAcquired();
  return kernel_->persisted_info.transaction_version[type];
}

void Directory::IncrementTransactionVersion(ModelType type) {
  kernel_->transaction_mutex.AssertAcquired();
  kernel_->persisted_info.transaction_version[type]++;
}

ModelTypeSet Directory::InitialSyncEndedTypes() {
  syncable::ReadTransaction trans(FROM_HERE, this);
  ModelTypeSet protocol_types = ProtocolTypes();
  ModelTypeSet initial_sync_ended_types;
  for (ModelTypeSet::Iterator i = protocol_types.First(); i.Good(); i.Inc()) {
    if (InitialSyncEndedForType(&trans, i.Get())) {
      initial_sync_ended_types.Put(i.Get());
    }
  }
  return initial_sync_ended_types;
}

bool Directory::InitialSyncEndedForType(ModelType type) {
  syncable::ReadTransaction trans(FROM_HERE, this);
  return InitialSyncEndedForType(&trans, type);
}

bool Directory::InitialSyncEndedForType(
    BaseTransaction* trans, ModelType type) {
  // True iff the type's root node has been received and applied.
  syncable::Entry entry(trans,
                        syncable::GET_BY_SERVER_TAG,
                        ModelTypeToRootTag(type));
  return entry.good() && entry.Get(syncable::BASE_VERSION) != CHANGES_VERSION;
}

string Directory::store_birthday() const {
  ScopedKernelLock lock(this);
  return kernel_->persisted_info.store_birthday;
}

void Directory::set_store_birthday(const string& store_birthday) {
  ScopedKernelLock lock(this);
  if (kernel_->persisted_info.store_birthday == store_birthday)
    return;
  kernel_->persisted_info.store_birthday = store_birthday;
  kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}

string Directory::bag_of_chips() const {
  ScopedKernelLock lock(this);
  return kernel_->persisted_info.bag_of_chips;
}

void Directory::set_bag_of_chips(const string& bag_of_chips) {
  ScopedKernelLock lock(this);
  if (kernel_->persisted_info.bag_of_chips == bag_of_chips)
    return;
  kernel_->persisted_info.bag_of_chips = bag_of_chips;
  kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
}


string Directory::cache_guid() const {
  // No need to lock since nothing ever writes to it after load.
  return kernel_->cache_guid;
}

NigoriHandler* Directory::GetNigoriHandler() {
  return nigori_handler_;
}

Cryptographer* Directory::GetCryptographer(const BaseTransaction* trans) {
  DCHECK_EQ(this, trans->directory());
  return cryptographer_;
}

void Directory::GetAllMetaHandles(BaseTransaction* trans,
                                  MetahandleSet* result) {
  result->clear();
  ScopedKernelLock lock(this);
  MetahandlesIndex::iterator i;
  for (i = kernel_->metahandles_index->begin();
       i != kernel_->metahandles_index->end();
       ++i) {
    result->insert((*i)->ref(META_HANDLE));
  }
}

void Directory::GetAllEntryKernels(BaseTransaction* trans,
                                   std::vector<const EntryKernel*>* result) {
  result->clear();
  ScopedKernelLock lock(this);
  result->insert(result->end(),
                 kernel_->metahandles_index->begin(),
                 kernel_->metahandles_index->end());
}

void Directory::GetUnsyncedMetaHandles(BaseTransaction* trans,
                                       UnsyncedMetaHandles* result) {
  result->clear();
  ScopedKernelLock lock(this);
  copy(kernel_->unsynced_metahandles->begin(),
       kernel_->unsynced_metahandles->end(), back_inserter(*result));
}

int64 Directory::unsynced_entity_count() const {
  ScopedKernelLock lock(this);
  return kernel_->unsynced_metahandles->size();
}

FullModelTypeSet Directory::GetServerTypesWithUnappliedUpdates(
    BaseTransaction* trans) const {
  FullModelTypeSet server_types;
  ScopedKernelLock lock(this);
  for (int i = UNSPECIFIED; i < MODEL_TYPE_COUNT; ++i) {
    const ModelType type = ModelTypeFromInt(i);
    if (!kernel_->unapplied_update_metahandles[type].empty()) {
      server_types.Put(type);
    }
  }
  return server_types;
}

void Directory::GetUnappliedUpdateMetaHandles(
    BaseTransaction* trans,
    FullModelTypeSet server_types,
    std::vector<int64>* result) {
  result->clear();
  ScopedKernelLock lock(this);
  for (int i = UNSPECIFIED; i < MODEL_TYPE_COUNT; ++i) {
    const ModelType type = ModelTypeFromInt(i);
    if (server_types.Has(type)) {
      std::copy(kernel_->unapplied_update_metahandles[type].begin(),
                kernel_->unapplied_update_metahandles[type].end(),
                back_inserter(*result));
    }
  }
}

void Directory::CollectMetaHandleCounts(
    std::vector<int>* num_entries_by_type,
    std::vector<int>* num_to_delete_entries_by_type) {
  syncable::ReadTransaction trans(FROM_HERE, this);
  ScopedKernelLock lock(this);

  MetahandlesIndex::iterator it = kernel_->metahandles_index->begin();
  for( ; it != kernel_->metahandles_index->end(); ++it) {
    EntryKernel* entry = *it;
    const ModelType type = GetModelTypeFromSpecifics(entry->ref(SPECIFICS));
    (*num_entries_by_type)[type]++;
    if(entry->ref(IS_DEL))
      (*num_to_delete_entries_by_type)[type]++;
  }
}

bool Directory::CheckInvariantsOnTransactionClose(
    syncable::BaseTransaction* trans,
    const EntryKernelMutationMap& mutations) {
  // NOTE: The trans may be in the process of being destructed.  Be careful if
  // you wish to call any of its virtual methods.
  MetahandleSet handles;

  switch (invariant_check_level_) {
  case FULL_DB_VERIFICATION:
    GetAllMetaHandles(trans, &handles);
    break;
  case VERIFY_CHANGES:
    for (EntryKernelMutationMap::const_iterator i = mutations.begin();
         i != mutations.end(); ++i) {
      handles.insert(i->first);
    }
    break;
  case OFF:
    break;
  }

  return CheckTreeInvariants(trans, handles);
}

bool Directory::FullyCheckTreeInvariants(syncable::BaseTransaction* trans) {
  MetahandleSet handles;
  GetAllMetaHandles(trans, &handles);
  return CheckTreeInvariants(trans, handles);
}

bool Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
                                    const MetahandleSet& handles) {
  MetahandleSet::const_iterator i;
  for (i = handles.begin() ; i != handles.end() ; ++i) {
    int64 metahandle = *i;
    Entry e(trans, GET_BY_HANDLE, metahandle);
    if (!SyncAssert(e.good(), FROM_HERE, "Entry is bad", trans))
      return false;
    syncable::Id id = e.Get(ID);
    syncable::Id parentid = e.Get(PARENT_ID);

    if (id.IsRoot()) {
      if (!SyncAssert(e.Get(IS_DIR), FROM_HERE,
                      "Entry should be a directory",
                      trans))
        return false;
      if (!SyncAssert(parentid.IsRoot(), FROM_HERE,
                      "Entry should be root",
                      trans))
         return false;
      if (!SyncAssert(!e.Get(IS_UNSYNCED), FROM_HERE,
                      "Entry should be sycned",
                      trans))
         return false;
      continue;
    }

    if (!e.Get(IS_DEL)) {
      if (!SyncAssert(id != parentid, FROM_HERE,
                      "Id should be different from parent id.",
                      trans))
         return false;
      if (!SyncAssert(!e.Get(NON_UNIQUE_NAME).empty(), FROM_HERE,
                      "Non unique name should not be empty.",
                      trans))
        return false;
      int safety_count = handles.size() + 1;
      while (!parentid.IsRoot()) {
        Entry parent(trans, GET_BY_ID, parentid);
        if (!SyncAssert(parent.good(), FROM_HERE,
                        "Parent entry is not valid.",
                        trans))
          return false;
        if (handles.end() == handles.find(parent.Get(META_HANDLE)))
            break; // Skip further checking if parent was unmodified.
        if (!SyncAssert(parent.Get(IS_DIR), FROM_HERE,
                        "Parent should be a directory",
                        trans))
          return false;
        if (!SyncAssert(!parent.Get(IS_DEL), FROM_HERE,
                        "Parent should not have been marked for deletion.",
                        trans))
          return false;
        if (!SyncAssert(handles.end() != handles.find(parent.Get(META_HANDLE)),
                        FROM_HERE,
                        "Parent should be in the index.",
                        trans))
          return false;
        parentid = parent.Get(PARENT_ID);
        if (!SyncAssert(--safety_count > 0, FROM_HERE,
                        "Count should be greater than zero.",
                        trans))
          return false;
      }
    }
    int64 base_version = e.Get(BASE_VERSION);
    int64 server_version = e.Get(SERVER_VERSION);
    bool using_unique_client_tag = !e.Get(UNIQUE_CLIENT_TAG).empty();
    if (CHANGES_VERSION == base_version || 0 == base_version) {
      if (e.Get(IS_UNAPPLIED_UPDATE)) {
        // Must be a new item, or a de-duplicated unique client tag
        // that was created both locally and remotely.
        if (!using_unique_client_tag) {
          if (!SyncAssert(e.Get(IS_DEL), FROM_HERE,
                          "The entry should not have been deleted.",
                          trans))
            return false;
        }
        // It came from the server, so it must have a server ID.
        if (!SyncAssert(id.ServerKnows(), FROM_HERE,
                        "The id should be from a server.",
                        trans))
          return false;
      } else {
        if (e.Get(IS_DIR)) {
          // TODO(chron): Implement this mode if clients ever need it.
          // For now, you can't combine a client tag and a directory.
          if (!SyncAssert(!using_unique_client_tag, FROM_HERE,
                          "Directory cannot have a client tag.",
                          trans))
            return false;
        }
        // Should be an uncomitted item, or a successfully deleted one.
        if (!e.Get(IS_DEL)) {
          if (!SyncAssert(e.Get(IS_UNSYNCED), FROM_HERE,
                          "The item should be unsynced.",
                          trans))
            return false;
        }
        // If the next check failed, it would imply that an item exists
        // on the server, isn't waiting for application locally, but either
        // is an unsynced create or a sucessful delete in the local copy.
        // Either way, that's a mismatch.
        if (!SyncAssert(0 == server_version, FROM_HERE,
                        "Server version should be zero.",
                        trans))
          return false;
        // Items that aren't using the unique client tag should have a zero
        // base version only if they have a local ID.  Items with unique client
        // tags are allowed to use the zero base version for undeletion and
        // de-duplication; the unique client tag trumps the server ID.
        if (!using_unique_client_tag) {
          if (!SyncAssert(!id.ServerKnows(), FROM_HERE,
                          "Should be a client only id.",
                          trans))
            return false;
        }
      }
    } else {
      if (!SyncAssert(id.ServerKnows(),
                      FROM_HERE,
                      "Should be a server id.",
                      trans))
        return false;
    }
    // Server-unknown items that are locally deleted should not be sent up to
    // the server.  They must be !IS_UNSYNCED.
    if (!SyncAssert(!(!id.ServerKnows() &&
                      e.Get(IS_DEL) &&
                      e.Get(IS_UNSYNCED)), FROM_HERE,
                    "Locally deleted item must not be unsynced.",
                    trans)) {
      return false;
    }
  }
  return true;
}

void Directory::SetInvariantCheckLevel(InvariantCheckLevel check_level) {
  invariant_check_level_ = check_level;
}

int64 Directory::NextMetahandle() {
  ScopedKernelLock lock(this);
  int64 metahandle = (kernel_->next_metahandle)++;
  return metahandle;
}

// Always returns a client ID that is the string representation of a negative
// number.
Id Directory::NextId() {
  int64 result;
  {
    ScopedKernelLock lock(this);
    result = (kernel_->persisted_info.next_id)--;
    kernel_->info_status = KERNEL_SHARE_INFO_DIRTY;
  }
  DCHECK_LT(result, 0);
  return Id::CreateFromClientString(base::Int64ToString(result));
}

bool Directory::HasChildren(BaseTransaction* trans, const Id& id) {
  ScopedKernelLock lock(this);
  return kernel_->parent_child_index->GetChildren(id) != NULL;
}

Id Directory::GetFirstChildId(BaseTransaction* trans,
                              const EntryKernel* parent) {
  DCHECK(parent);
  DCHECK(parent->ref(IS_DIR));

  ScopedKernelLock lock(this);
  const OrderedChildSet* children =
      kernel_->parent_child_index->GetChildren(parent->ref(ID));

  // We're expected to return root if there are no children.
  if (!children)
    return Id();

  return (*children->begin())->ref(ID);
}

syncable::Id Directory::GetPredecessorId(EntryKernel* e) {
  ScopedKernelLock lock(this);

  DCHECK(ParentChildIndex::ShouldInclude(e));
  const OrderedChildSet* children =
      kernel_->parent_child_index->GetChildren(e->ref(PARENT_ID));
  DCHECK(children && !children->empty());
  OrderedChildSet::const_iterator i = children->find(e);
  DCHECK(i != children->end());

  if (i == children->begin()) {
    return Id();
  } else {
    i--;
    return (*i)->ref(ID);
  }
}

syncable::Id Directory::GetSuccessorId(EntryKernel* e) {
  ScopedKernelLock lock(this);

  DCHECK(ParentChildIndex::ShouldInclude(e));
  const OrderedChildSet* children =
      kernel_->parent_child_index->GetChildren(e->ref(PARENT_ID));
  DCHECK(children && !children->empty());
  OrderedChildSet::const_iterator i = children->find(e);
  DCHECK(i != children->end());

  i++;
  if (i == children->end()) {
    return Id();
  } else {
    return (*i)->ref(ID);
  }
}

// TODO(rlarocque): Remove all support for placing ShouldMaintainPosition()
// items as siblings of items that do not maintain postions.  It is required
// only for tests.  See crbug.com/178282.
void Directory::PutPredecessor(EntryKernel* e, EntryKernel* predecessor) {
  DCHECK(!e->ref(IS_DEL));
  if (!e->ShouldMaintainPosition()) {
    DCHECK(!e->ref(UNIQUE_POSITION).IsValid());
    return;
  }
  std::string suffix = e->ref(UNIQUE_BOOKMARK_TAG);
  DCHECK(!suffix.empty());

  // Remove our item from the ParentChildIndex and remember to re-add it later.
  ScopedKernelLock lock(this);
  ScopedParentChildIndexUpdater updater(lock, e, kernel_->parent_child_index);

  // Note: The ScopedParentChildIndexUpdater will update this set for us as we
  // leave this function.
  const OrderedChildSet* siblings =
      kernel_->parent_child_index->GetChildren(e->ref(PARENT_ID));

  if (!siblings) {
    // This parent currently has no other children.
    DCHECK(predecessor->ref(ID).IsRoot());
    UniquePosition pos = UniquePosition::InitialPosition(suffix);
    e->put(UNIQUE_POSITION, pos);
    return;
  }

  if (predecessor->ref(ID).IsRoot()) {
    // We have at least one sibling, and we're inserting to the left of them.
    UniquePosition successor_pos = (*siblings->begin())->ref(UNIQUE_POSITION);

    UniquePosition pos;
    if (!successor_pos.IsValid()) {
      // If all our successors are of non-positionable types, just create an
      // initial position.  We arbitrarily choose to sort invalid positions to
      // the right of the valid positions.
      //
      // We really shouldn't need to support this.  See TODO above.
      pos = UniquePosition::InitialPosition(suffix);
    } else  {
      DCHECK(!siblings->empty());
      pos = UniquePosition::Before(successor_pos, suffix);
    }

    e->put(UNIQUE_POSITION, pos);
    return;
  }

  // We can't support placing an item after an invalid position.  Fortunately,
  // the tests don't exercise this particular case.  We should not support
  // siblings with invalid positions at all.  See TODO above.
  DCHECK(predecessor->ref(UNIQUE_POSITION).IsValid());

  OrderedChildSet::const_iterator neighbour = siblings->find(predecessor);
  DCHECK(neighbour != siblings->end());

  ++neighbour;
  if (neighbour == siblings->end()) {
    // Inserting at the end of the list.
    UniquePosition pos = UniquePosition::After(
        predecessor->ref(UNIQUE_POSITION),
        suffix);
    e->put(UNIQUE_POSITION, pos);
    return;
  }

  EntryKernel* successor = *neighbour;

  // Another mixed valid and invalid position case.  This one could be supported
  // in theory, but we're trying to deprecate support for siblings with and
  // without valid positions.  See TODO above.
  DCHECK(successor->ref(UNIQUE_POSITION).IsValid());

  // Finally, the normal case: inserting between two elements.
  UniquePosition pos = UniquePosition::Between(
      predecessor->ref(UNIQUE_POSITION),
      successor->ref(UNIQUE_POSITION),
      suffix);
  e->put(UNIQUE_POSITION, pos);
  return;
}

// TODO(rlarocque): Avoid this indirection.  Just return the set.
void Directory::AppendChildHandles(const ScopedKernelLock& lock,
                                   const Id& parent_id,
                                   Directory::ChildHandles* result) {
  const OrderedChildSet* children =
      kernel_->parent_child_index->GetChildren(parent_id);
  if (!children)
    return;

  for (OrderedChildSet::const_iterator i = children->begin();
       i != children->end(); ++i) {
    DCHECK_EQ(parent_id, (*i)->ref(PARENT_ID));
    result->push_back((*i)->ref(META_HANDLE));
  }
}

ScopedKernelLock::ScopedKernelLock(const Directory* dir)
  :  scoped_lock_(dir->kernel_->mutex), dir_(const_cast<Directory*>(dir)) {
}

}  // namespace syncable
}  // namespace syncer