// Copyright (c) 2009 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 "chrome/browser/sync/syncable/syncable.h"

#include "build/build_config.h"

#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#ifdef OS_MACOSX
#include <CoreFoundation/CoreFoundation.h>
#elif defined(OS_LINUX)
#include <glib.h>
#elif defined(OS_WIN)
#include <shlwapi.h>  // for PathMatchSpec
#endif

#include <algorithm>
#include <functional>
#include <iomanip>
#include <iterator>
#include <set>
#include <string>

#include "base/hash_tables.h"
#include "base/logging.h"
#include "base/perftimer.h"
#include "base/scoped_ptr.h"
#include "base/time.h"
#include "chrome/browser/sync/engine/syncer.h"
#include "chrome/browser/sync/engine/syncer_util.h"
#include "chrome/browser/sync/protocol/service_constants.h"
#include "chrome/browser/sync/syncable/directory_backing_store.h"
#include "chrome/browser/sync/syncable/directory_manager.h"
#include "chrome/browser/sync/syncable/syncable-inl.h"
#include "chrome/browser/sync/syncable/syncable_changes_version.h"
#include "chrome/browser/sync/syncable/syncable_columns.h"
#include "chrome/browser/sync/util/character_set_converters.h"
#include "chrome/browser/sync/util/compat_file.h"
#include "chrome/browser/sync/util/crypto_helpers.h"
#include "chrome/browser/sync/util/event_sys-inl.h"
#include "chrome/browser/sync/util/fast_dump.h"
#include "chrome/browser/sync/util/path_helpers.h"

namespace {
enum InvariantCheckLevel {
  OFF = 0,
  VERIFY_IN_MEMORY = 1,
  FULL_DB_VERIFICATION = 2
};

static const InvariantCheckLevel kInvariantCheckLevel = VERIFY_IN_MEMORY;

// Max number of milliseconds to spend checking syncable entry invariants
static const int kInvariantCheckMaxMs = 50;
}  // namespace

// if sizeof(time_t) != sizeof(int32) we need to alter or expand the sqlite
// datatype.
COMPILE_ASSERT(sizeof(time_t) == sizeof(int32), time_t_is_not_int32);

using browser_sync::FastDump;
using browser_sync::SyncerUtil;
using std::string;


namespace syncable {

int64 Now() {
#ifdef OS_WIN
  FILETIME filetime;
  SYSTEMTIME systime;
  GetSystemTime(&systime);
  SystemTimeToFileTime(&systime, &filetime);
  // MSDN recommends converting via memcpy like this.
  LARGE_INTEGER n;
  memcpy(&n, &filetime, sizeof(filetime));
  return n.QuadPart;
#elif (defined(OS_LINUX) || defined(OS_MACOSX))
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return static_cast<int64>(tv.tv_sec);
#else
#error NEED OS SPECIFIC Now() implementation
#endif
}

///////////////////////////////////////////////////////////////////////////
// Compare functions and hashes for the indices.

// Callback for sqlite3
int ComparePathNames16(void*, int a_bytes, const void* a, int b_bytes,
                       const void* b) {
#ifdef OS_WIN
  DCHECK_EQ(0, a_bytes % 2);
  DCHECK_EQ(0, b_bytes % 2);
  int result = CompareString(LOCALE_INVARIANT, NORM_IGNORECASE,
    static_cast<const PathChar*>(a), a_bytes / 2,
    static_cast<const PathChar*>(b), b_bytes / 2);
  CHECK(0 != result) << "Error comparing strings: " << GetLastError();
  return result - 2;  // Convert to -1, 0, 1
#elif defined(OS_LINUX)
// misnomer for Linux. These are already utf8 bit strings.
  gchar *case_folded_a;
  gchar *case_folded_b;
  GError *err = NULL;
  case_folded_a = g_utf8_casefold(reinterpret_cast<const gchar*>(a), a_bytes);
  CHECK(case_folded_a != NULL) << "g_utf8_casefold failed";
  case_folded_b = g_utf8_casefold(reinterpret_cast<const gchar*>(b), b_bytes);
  CHECK(case_folded_b != NULL) << "g_utf8_casefold failed";
  gint result = g_utf8_collate(case_folded_a, case_folded_b);
  g_free(case_folded_a);
  g_free(case_folded_b);
  if (result < 0) return -1;
  if (result > 0) return 1;
  return 0;
#elif defined(OS_MACOSX)
  CFStringRef a_str;
  CFStringRef b_str;
  a_str = CFStringCreateWithBytes(NULL, reinterpret_cast<const UInt8*>(a),
                                  a_bytes, kCFStringEncodingUTF8, FALSE);
  b_str = CFStringCreateWithBytes(NULL, reinterpret_cast<const UInt8*>(b),
                                  b_bytes, kCFStringEncodingUTF8, FALSE);
  CFComparisonResult res;
  res = CFStringCompare(a_str, b_str, kCFCompareCaseInsensitive);
  CFRelease(a_str);
  CFRelease(b_str);
  return res;
#else
#error no ComparePathNames16() for your OS
#endif
}

template <Int64Field field_index>
class SameField {
 public:
  inline bool operator()(const syncable::EntryKernel* a,
                         const syncable::EntryKernel* b) const {
    return a->ref(field_index) == b->ref(field_index);
  }
};

template <Int64Field field_index>
class HashField {
 public:
  inline size_t operator()(const syncable::EntryKernel* a) const {
    return hasher_(a->ref(field_index));
  }
  base::hash_set<int64> hasher_;
};

// TODO(ncarter): Rename!
int ComparePathNames(const PathString& a, const PathString& b) {
  const size_t val_size = sizeof(PathString::value_type);
  return ComparePathNames16(NULL, a.size() * val_size, a.data(),
                                  b.size() * val_size, b.data());
}

class LessParentIdAndNames {
 public:
  bool operator() (const syncable::EntryKernel* a,
                   const syncable::EntryKernel* b) const {
    if (a->ref(PARENT_ID) != b->ref(PARENT_ID))
      return a->ref(PARENT_ID) < b->ref(PARENT_ID);
    return ComparePathNames(a->ref(NAME), b->ref(NAME)) < 0;
  }
};

bool LessPathNames::operator() (const PathString& a,
                                const PathString& b) const {
  return ComparePathNames(a, b) < 0;
}

// static
Name Name::FromEntryKernel(EntryKernel* kernel) {
  PathString& sync_name_ref = kernel->ref(UNSANITIZED_NAME).empty() ?
      kernel->ref(NAME) : kernel->ref(UNSANITIZED_NAME);
  return Name(kernel->ref(NAME), sync_name_ref, kernel->ref(NON_UNIQUE_NAME));
}

///////////////////////////////////////////////////////////////////////////
// Directory

static const DirectoryChangeEvent kShutdownChangesEvent =
    { DirectoryChangeEvent::SHUTDOWN, 0, 0 };

void DestroyThreadNodeKey(void* vnode) {
  ThreadNode* const node = reinterpret_cast<ThreadNode*>(vnode);
  CHECK(!node->in_list)
    << "\nThread exited while holding the transaction mutex!\n" << *node;
  delete node;
}

Directory::Kernel::Kernel(const PathString& db_path,
                          const PathString& name,
                          const KernelLoadInfo& info)
: db_path(db_path),
  refcount(1),
  name_(name),
  metahandles_index(new Directory::MetahandlesIndex),
  ids_index(new Directory::IdsIndex),
  parent_id_and_names_index(new Directory::ParentIdAndNamesIndex),
  extended_attributes(new ExtendedAttributes),
  unapplied_update_metahandles(new MetahandleSet),
  unsynced_metahandles(new MetahandleSet),
  channel(new Directory::Channel(syncable::DIRECTORY_DESTROYED)),
  changes_channel(new Directory::ChangesChannel(kShutdownChangesEvent)),
  last_sync_timestamp_(info.kernel_info.last_sync_timestamp),
  initial_sync_ended_(info.kernel_info.initial_sync_ended),
  store_birthday_(info.kernel_info.store_birthday),
  next_id(info.kernel_info.next_id),
  cache_guid_(info.cache_guid),
  next_metahandle(info.max_metahandle + 1) {
  info_status_ = Directory::KERNEL_SHARE_INFO_VALID;
  CHECK(0 == pthread_mutex_init(&mutex, NULL));
  CHECK(0 == pthread_key_create(&thread_node_key, &DestroyThreadNodeKey));
}

inline void DeleteEntry(EntryKernel* kernel) {
  delete kernel;
}

void Directory::Kernel::AddRef() {
  base::subtle::NoBarrier_AtomicIncrement(&refcount, 1);
}

void Directory::Kernel::Release() {
  if (!base::subtle::NoBarrier_AtomicIncrement(&refcount, -1))
    delete this;
}

Directory::Kernel::~Kernel() {
  CHECK(0 == refcount);
  delete channel;
  delete changes_channel;
  CHECK(0 == pthread_mutex_destroy(&mutex));
  pthread_key_delete(thread_node_key);
  delete unsynced_metahandles;
  delete unapplied_update_metahandles;
  delete extended_attributes;
  delete parent_id_and_names_index;
  delete ids_index;
  for_each(metahandles_index->begin(), metahandles_index->end(), DeleteEntry);
  delete metahandles_index;
}

Directory::Directory() : kernel_(NULL), store_(NULL) {
}

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

BOOL PathNameMatch(const PathString& pathname, const PathString& pathspec) {
#ifdef OS_WIN
  // Note that if we go Vista only this is easier:
  // http://msdn2.microsoft.com/en-us/library/ms628611.aspx

  // PathMatchSpec strips spaces from the start of pathspec, so we compare those
  // ourselves.
  const PathChar* pathname_ptr = pathname.c_str();
  const PathChar* pathspec_ptr = pathspec.c_str();

  while (*pathname_ptr == ' ' && *pathspec_ptr == ' ')
     ++pathname_ptr, ++pathspec_ptr;

  // If we have more inital spaces in the pathspec than in the pathname then the
  // result from PathMatchSpec will be erronous.
  if (*pathspec_ptr == ' ')
    return FALSE;

  // PathMatchSpec also gets "confused" when there are ';' characters in name or
  // in spec. So, if we match (f.i.) ";" with ";" PathMatchSpec will return
  // FALSE (which is wrong). Luckily for us, we can easily fix this by
  // substituting ';' with ':' which is illegal character in file name and
  // we're not going to see it there. With ':' in path name and spec
  // PathMatchSpec works fine.
  if ((NULL == wcschr(pathname_ptr, L';')) &&
      (NULL == wcschr(pathspec_ptr, L';'))) {
    // No ';' in file name and in spec. Just pass it as it is.
    return ::PathMatchSpec(pathname_ptr, pathspec_ptr);
  }

  // We need to subst ';' with ':' in both, name and spec.
  PathString name_subst(pathname_ptr);
  PathString spec_subst(pathspec_ptr);

  PathString::size_type index = name_subst.find(L';');
  while (PathString::npos != index) {
    name_subst[index] = L':';
    index = name_subst.find(L';', index + 1);
  }

  index = spec_subst.find(L';');
  while (PathString::npos != index) {
    spec_subst[index] = L':';
    index = spec_subst.find(L';', index + 1);
  }

  return ::PathMatchSpec(name_subst.c_str(), spec_subst.c_str());
#else
  return 0 == ComparePathNames(pathname, pathspec);
#endif
}

DirOpenResult Directory::Open(const PathString& file_path,
                              const PathString& name) {
  const DirOpenResult result = OpenImpl(file_path, name);
  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 (!entry->ref(IS_DEL))
      kernel_->parent_id_and_names_index->insert(entry);
    kernel_->ids_index->insert(entry);
    if (entry->ref(IS_UNSYNCED))
      kernel_->unsynced_metahandles->insert(entry->ref(META_HANDLE));
    if (entry->ref(IS_UNAPPLIED_UPDATE))
      kernel_->unapplied_update_metahandles->insert(entry->ref(META_HANDLE));
  }
}

DirectoryBackingStore* Directory::CreateBackingStore(
    const PathString& dir_name, const PathString& backing_filepath) {
  return new DirectoryBackingStore(dir_name, backing_filepath);
}

DirOpenResult Directory::OpenImpl(const PathString& file_path,
                                  const PathString& name) {
  DCHECK_EQ(static_cast<DirectoryBackingStore*>(NULL), store_);
  const PathString db_path = ::GetFullPath(file_path);
  store_ = CreateBackingStore(name, db_path);

  KernelLoadInfo info;
  // Temporary indicies before kernel_ initialized in case Load fails. We 0(1)
  // swap these later.
  MetahandlesIndex metas_bucket;
  ExtendedAttributes xattrs_bucket;
  DirOpenResult result = store_->Load(&metas_bucket, &xattrs_bucket, &info);
  if (OPENED != result)
    return result;

  kernel_ = new Kernel(db_path, name, info);
  kernel_->metahandles_index->swap(metas_bucket);
  kernel_->extended_attributes->swap(xattrs_bucket);
  InitializeIndices();
  return OPENED;
}

void Directory::Close() {
  if (store_)
    delete store_;
  store_ = NULL;
  if (kernel_) {
    bool del = !base::subtle::NoBarrier_AtomicIncrement(&kernel_->refcount, -1);
    DCHECK(del) << "Kernel should only have a single ref";
    if (del)
      delete kernel_;
    kernel_ = NULL;
  }
}

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

EntryKernel* Directory::GetEntryById(const Id& id,
                                     ScopedKernelLock* const lock) {
  DCHECK(kernel_);
  // First look up in memory
  kernel_->needle.ref(ID) = id;
  IdsIndex::iterator id_found = kernel_->ids_index->find(&kernel_->needle);
  if (id_found != kernel_->ids_index->end()) {
    // Found it in memory.  Easy.
    return *id_found;
  }
  return NULL;
}

EntryKernel* Directory::GetEntryByTag(const PathString& 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(SINGLETON_TAG) == tag) {
      return *i;
    }
  }
  return NULL;
}

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

EntryKernel* Directory::GetEntryByHandle(const int64 metahandle,
                                         ScopedKernelLock* lock) {
  // Look up in memory
  kernel_->needle.ref(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;
}

EntryKernel* Directory::GetChildWithName(const Id& parent_id,
                                         const PathString& name) {
  ScopedKernelLock lock(this);
  return GetChildWithName(parent_id, name, &lock);
}

// Will return child entry if the folder is opened,
// otherwise it will return NULL.
EntryKernel* Directory::GetChildWithName(const Id& parent_id,
                                         const PathString& name,
                                         ScopedKernelLock* const lock) {
  PathString dbname = name;
  EntryKernel* parent = GetEntryById(parent_id, lock);
  if (parent == NULL)
    return NULL;
  return GetChildWithNameImpl(parent_id, dbname, lock);
}

// Will return child entry even when the folder is not opened. This is used by
// syncer to apply update when folder is closed.
EntryKernel* Directory::GetChildWithDBName(const Id& parent_id,
                                           const PathString& name) {
  ScopedKernelLock lock(this);
  return GetChildWithNameImpl(parent_id, name, &lock);
}

EntryKernel* Directory::GetChildWithNameImpl(const Id& parent_id,
                                             const PathString& name,
                                             ScopedKernelLock* const lock) {
  // First look up in memory:
  kernel_->needle.ref(NAME) = name;
  kernel_->needle.ref(PARENT_ID) = parent_id;
  ParentIdAndNamesIndex::iterator found =
    kernel_->parent_id_and_names_index->find(&kernel_->needle);
  if (found != kernel_->parent_id_and_names_index->end()) {
    // Found it in memory.  Easy.
    return *found;
  }
  return NULL;
}

// An interface to specify the details of which children
// GetChildHandles() is looking for.
struct PathMatcher {
  explicit PathMatcher(const Id& parent_id) : parent_id_(parent_id) { }
  virtual ~PathMatcher() { }
  enum MatchType {
    NO_MATCH,
    MATCH,
    // Means we found the only entry we're looking for in
    // memory so we don't need to check the DB.
    EXACT_MATCH
  };
  virtual MatchType PathMatches(const PathString& path) = 0;
  typedef Directory::ParentIdAndNamesIndex Index;
  virtual Index::iterator lower_bound(Index* index) = 0;
  virtual Index::iterator upper_bound(Index* index) = 0;
  const Id parent_id_;
  EntryKernel needle_;
};

// Matches all children.
struct AllPathsMatcher : public PathMatcher {
  explicit AllPathsMatcher(const Id& parent_id) : PathMatcher(parent_id) {
  }
  virtual MatchType PathMatches(const PathString& path) {
    return MATCH;
  }
  virtual Index::iterator lower_bound(Index* index) {
    needle_.ref(PARENT_ID) = parent_id_;
    needle_.ref(NAME).clear();
    return index->lower_bound(&needle_);
  }

  virtual Index::iterator upper_bound(Index* index) {
    needle_.ref(PARENT_ID) = parent_id_;
    needle_.ref(NAME).clear();
    Index::iterator i = index->upper_bound(&needle_),
      end = index->end();
    while (i != end  && (*i)->ref(PARENT_ID) == parent_id_)
      ++i;
    return i;
  }
};

// Matches an exact filename only; no wildcards.
struct ExactPathMatcher : public PathMatcher {
  ExactPathMatcher(const PathString& pathspec, const Id& parent_id)
    : PathMatcher(parent_id), pathspec_(pathspec) {
  }
  virtual MatchType PathMatches(const PathString& path) {
    return 0 == ComparePathNames(path, pathspec_) ? EXACT_MATCH : NO_MATCH;
  }
  virtual Index::iterator lower_bound(Index* index) {
    needle_.ref(PARENT_ID) = parent_id_;
    needle_.ref(NAME) = pathspec_;
    return index->lower_bound(&needle_);
  }
  virtual Index::iterator upper_bound(Index* index) {
    needle_.ref(PARENT_ID) = parent_id_;
    needle_.ref(NAME) = pathspec_;
    return index->upper_bound(&needle_);
  }
  const PathString pathspec_;
};

// Matches a pathspec with wildcards.
struct PartialPathMatcher : public PathMatcher {
  PartialPathMatcher(const PathString& pathspec,
                     PathString::size_type wildcard, const Id& parent_id)
    : PathMatcher(parent_id), pathspec_(pathspec) {
    if (0 == wildcard)
      return;
    lesser_.assign(pathspec_.data(), wildcard);
    greater_.assign(pathspec_.data(), wildcard);
    // Increment the last letter of greater so we can then less than
    // compare to it.
    PathString::size_type i = greater_.size() - 1;
    do {
    if (greater_[i] == std::numeric_limits<PathString::value_type>::max()) {
        greater_.resize(i);  // Try the preceding character.
        if (0 == i--)
          break;
      } else {
        greater_[i] += 1;
      }
      // Yes, there are cases where incrementing a character
      // actually decreases its position in the sort.  Example: 9 -> :
    } while (ComparePathNames(lesser_, greater_) >= 0);
  }

  virtual MatchType PathMatches(const PathString& path) {
    return PathNameMatch(path, pathspec_) ? MATCH : NO_MATCH;
  }

  virtual Index::iterator lower_bound(Index* index) {
    needle_.ref(PARENT_ID) = parent_id_;
    needle_.ref(NAME) = lesser_;
    return index->lower_bound(&needle_);
  }
  virtual Index::iterator upper_bound(Index* index) {
    if (greater_.empty()) {
      needle_.ref(PARENT_ID) = parent_id_;
      needle_.ref(NAME).clear();
      Index::iterator i = index->upper_bound(&needle_),
        end = index->end();
      while (i != end && (*i)->ref(PARENT_ID) == parent_id_)
        ++i;
      return i;
    } else {
      needle_.ref(PARENT_ID) = parent_id_;
      needle_.ref(NAME) = greater_;
      return index->lower_bound(&needle_);
    }
  }

  const PathString pathspec_;
  PathString lesser_;
  PathString greater_;
};


void Directory::GetChildHandles(BaseTransaction* trans, const Id& parent_id,
                                Directory::ChildHandles* result) {
  AllPathsMatcher matcher(parent_id);
  return GetChildHandlesImpl(trans, parent_id, &matcher, result);
}

void Directory::GetChildHandlesImpl(BaseTransaction* trans, const Id& parent_id,
                                    PathMatcher* matcher,
                                    Directory::ChildHandles* result) {
  CHECK(this == trans->directory());
  result->clear();
  {
    ScopedKernelLock lock(this);
    ParentIdAndNamesIndex* const index =
      kernel_->parent_id_and_names_index;
    typedef ParentIdAndNamesIndex::iterator iterator;
    for (iterator i = matcher->lower_bound(index),
           end = matcher->upper_bound(index); i != end; ++i) {
      // root's parent_id is NULL in the db but 0 in memory, so
      // have avoid listing the root as its own child.
      if ((*i)->ref(ID) == (*i)->ref(PARENT_ID))
        continue;
      PathMatcher::MatchType match = matcher->PathMatches((*i)->ref(NAME));
      if (PathMatcher::NO_MATCH == match)
        continue;
      result->push_back((*i)->ref(META_HANDLE));
      if (PathMatcher::EXACT_MATCH == match)
        return;
    }
  }
}

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

EntryKernel* Directory::GetEntryByPath(const PathString& path) {
  CHECK(kernel_);
  EntryKernel* result = GetRootEntry();
  CHECK(result) << "There should always be a root node.";
  for (PathSegmentIterator<PathString> i(path), end;
       i != end && NULL != result; ++i) {
    result = GetChildWithName(result->ref(ID), *i);
  }
  return result;
}

void ZeroFields(EntryKernel* entry, int first_field) {
  int i = first_field;
  // Note that bitset<> constructor sets all bits to zero, and strings
  // initialize to empty.
  for ( ; i < INT64_FIELDS_END; ++i)
    entry->ref(static_cast<Int64Field>(i)) = 0;
  for ( ; i < ID_FIELDS_END; ++i)
    entry->ref(static_cast<IdField>(i)).Clear();
  for ( ; i < BIT_FIELDS_END; ++i)
    entry->ref(static_cast<BitField>(i)) = false;
  if (i < BLOB_FIELDS_END)
    i = BLOB_FIELDS_END;
}

void Directory::InsertEntry(EntryKernel* entry) {
  ScopedKernelLock lock(this);
  InsertEntry(entry, &lock);
}

void Directory::InsertEntry(EntryKernel* entry, ScopedKernelLock* lock) {
  DCHECK(NULL != lock);
  CHECK(NULL != entry);
  static const char error[] = "Entry already in memory index.";
  CHECK(kernel_->metahandles_index->insert(entry).second) << error;
  if (!entry->ref(IS_DEL))
    CHECK(kernel_->parent_id_and_names_index->insert(entry).second) << error;
  CHECK(kernel_->ids_index->insert(entry).second) << error;
}

bool Directory::Undelete(EntryKernel* const entry) {
  DCHECK(entry->ref(IS_DEL));
  ScopedKernelLock lock(this);
  if (NULL != GetChildWithName(entry->ref(PARENT_ID), entry->ref(NAME), &lock))
    return false;  // Would have duplicated existing entry.
  entry->ref(IS_DEL) = false;
  entry->dirty[IS_DEL] = true;
  CHECK(kernel_->parent_id_and_names_index->insert(entry).second);
  return true;
}

bool Directory::Delete(EntryKernel* const entry) {
  DCHECK(!entry->ref(IS_DEL));
  entry->ref(IS_DEL) = true;
  entry->dirty[IS_DEL] = true;
  ScopedKernelLock lock(this);
  CHECK(1 == kernel_->parent_id_and_names_index->erase(entry));
  return true;
}

bool Directory::ReindexId(EntryKernel* const entry, const Id& new_id) {
  ScopedKernelLock lock(this);
  if (NULL != GetEntryById(new_id, &lock))
    return false;
  CHECK(1 == kernel_->ids_index->erase(entry));
  entry->ref(ID) = new_id;
  CHECK(kernel_->ids_index->insert(entry).second);
  return true;
}

bool Directory::ReindexParentIdAndName(EntryKernel* const entry,
                                       const Id& new_parent_id,
                                       const PathString& new_name) {
  ScopedKernelLock lock(this);
  PathString new_indexed_name = new_name;
  if (entry->ref(IS_DEL)) {
    entry->ref(PARENT_ID) = new_parent_id;
    entry->ref(NAME) = new_indexed_name;
    return true;
  }

  // check for a case changing rename
  if (entry->ref(PARENT_ID) == new_parent_id &&
    0 == ComparePathNames(entry->ref(NAME), new_indexed_name)) {
    entry->ref(NAME) = new_indexed_name;
  } else {
    if (NULL != GetChildWithName(new_parent_id, new_indexed_name, &lock))
      return false;
    CHECK(1 == kernel_->parent_id_and_names_index->erase(entry));
    entry->ref(PARENT_ID) = new_parent_id;
    entry->ref(NAME) = new_indexed_name;
    CHECK(kernel_->parent_id_and_names_index->insert(entry).second);
  }
  return true;
}

// static
bool Directory::SafeToPurgeFromMemory(const EntryKernel* const entry) {
  return entry->ref(IS_DEL) && !entry->dirty.any() && !entry->ref(SYNCING) &&
         !entry->ref(IS_UNAPPLIED_UPDATE) && !entry->ref(IS_UNSYNCED);
}

void Directory::TakeSnapshotForSaveChanges(SaveChangesSnapshot* snapshot) {
  ReadTransaction trans(this, __FILE__, __LINE__);
  ScopedKernelLock lock(this);
  // Deep copy dirty entries from kernel_->metahandles_index into snapshot and
  // clear dirty flags.
  for (MetahandlesIndex::iterator i = kernel_->metahandles_index->begin();
       i != kernel_->metahandles_index->end(); ++i) {
    EntryKernel* entry = *i;
    if (!entry->dirty.any())
      continue;
    snapshot->dirty_metas.insert(snapshot->dirty_metas.end(), *entry);
    entry->dirty.reset();
    // TODO(timsteele): The previous *windows only* SaveChanges code path seems
    // to have a bug in that the IS_NEW bit is not rolled back if the entire DB
    // transaction is rolled back, due to the "recent" windows optimization of
    // using a ReadTransaction rather than a WriteTransaction in SaveChanges.
    // This bit is only used to decide whether we should sqlite INSERT or
    // UPDATE, and if we are INSERTing we make sure to dirty all the fields so
    // as to overwrite the database default values.  For now, this is rectified
    // by flipping the bit to false here (note that the snapshot will contain
    // the "original" value), and then resetting it on failure in
    // HandleSaveChangesFailure, where "failure" is defined as "the DB
    // "transaction was rolled back". This is safe because the only user of this
    // bit is in fact SaveChanges, which enforces mutually exclusive access by
    // way of save_changes_mutex_.  The TODO is to consider abolishing this bit
    // in favor of using a sqlite INSERT OR REPLACE, which could(would?) imply
    // that all bits need to be written rather than just the dirty ones in
    // the BindArg helper function.
    entry->ref(IS_NEW) = false;
  }

  // Do the same for extended attributes.
  for (ExtendedAttributes::iterator i = kernel_->extended_attributes->begin();
       i != kernel_->extended_attributes->end(); ++i) {
    if (!i->second.dirty)
      continue;
    snapshot->dirty_xattrs[i->first] = i->second;
    i->second.dirty = false;
  }

  // Fill kernel_info_status and kernel_info.
  PersistedKernelInfo& info = snapshot->kernel_info;
  info.initial_sync_ended = kernel_->initial_sync_ended_;
  info.last_sync_timestamp = kernel_->last_sync_timestamp_;
  // 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.
  info.next_id = kernel_->next_id - 65536;
  info.store_birthday = kernel_->store_birthday_;
  snapshot->kernel_info_status = kernel_->info_status_;
  // This one we reset on failure.
  kernel_->info_status_ = KERNEL_SHARE_INFO_VALID;
}

bool Directory::SaveChanges() {
  bool success = false;
  DCHECK(store_);
  PThreadScopedLock<PThreadMutex> lock(&kernel_->save_changes_mutex);
  // Snapshot and save.
  SaveChangesSnapshot snapshot;
  TakeSnapshotForSaveChanges(&snapshot);
  success = store_->SaveChanges(snapshot);

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

void Directory::VacuumAfterSaveChanges(const SaveChangesSnapshot& snapshot) {
  // Need a write transaction as we are about to permanently purge entries.
  WriteTransaction trans(this, VACUUM_AFTER_SAVE, __FILE__, __LINE__);
  ScopedKernelLock lock(this);
  kernel_->flushed_metahandles_.Push(0);  // Begin flush marker
  // Now drop everything we can out of memory.
  for (OriginalEntries::const_iterator i = snapshot.dirty_metas.begin();
       i != snapshot.dirty_metas.end(); ++i) {
    kernel_->needle.ref(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(entry)) {
      // We now drop deleted metahandles that are up to date on both the client
      // and the server.
      size_t num_erased = 0;
      kernel_->flushed_metahandles_.Push(entry->ref(META_HANDLE));
      num_erased = kernel_->ids_index->erase(entry);
      DCHECK_EQ(1, num_erased);
      num_erased = kernel_->metahandles_index->erase(entry);
      DCHECK_EQ(1, num_erased);
      delete entry;
    }
  }

  ExtendedAttributes::const_iterator i = snapshot.dirty_xattrs.begin();
  while (i != snapshot.dirty_xattrs.end()) {
    ExtendedAttributeKey key(i->first.metahandle, i->first.key);
    ExtendedAttributes::iterator found =
        kernel_->extended_attributes->find(key);
    if (found == kernel_->extended_attributes->end() ||
        found->second.dirty || !i->second.is_deleted) {
      ++i;
    } else {
      kernel_->extended_attributes->erase(found);
    }
  }
}

void Directory::HandleSaveChangesFailure(const SaveChangesSnapshot& snapshot) {
  ScopedKernelLock lock(this);
  kernel_->info_status_ = KERNEL_SHARE_INFO_DIRTY;

  // Because we cleared dirty bits on the real entries when taking the snapshot,
  // we should make sure the fact that the snapshot was not persisted gets
  // reflected in the entries.  Not doing this would mean if no other changes
  // occur to the same fields of the entries in dirty_metas some changes could
  // end up being lost, if they also failed to be committed to the server.
  // Setting the bits ensures that SaveChanges will at least try again later.
  for (OriginalEntries::const_iterator i = snapshot.dirty_metas.begin();
       i != snapshot.dirty_metas.end(); ++i) {
    kernel_->needle.ref(META_HANDLE) = i->ref(META_HANDLE);
    MetahandlesIndex::iterator found =
        kernel_->metahandles_index->find(&kernel_->needle);
    if (found != kernel_->metahandles_index->end()) {
      (*found)->dirty |= i->dirty;
      (*found)->ref(IS_NEW) = i->ref(IS_NEW);
    }
  }

  for (ExtendedAttributes::const_iterator i = snapshot.dirty_xattrs.begin();
       i != snapshot.dirty_xattrs.end(); ++i) {
    ExtendedAttributeKey key(i->first.metahandle, i->first.key);
    ExtendedAttributes::iterator found =
        kernel_->extended_attributes->find(key);
    if (found != kernel_->extended_attributes->end())
      found->second.dirty = true;
  }
}

int64 Directory::last_sync_timestamp() const {
  ScopedKernelLock lock(this);
  return kernel_->last_sync_timestamp_;
}

void Directory::set_last_sync_timestamp(int64 timestamp) {
  ScopedKernelLock lock(this);
  if (kernel_->last_sync_timestamp_ == timestamp)
    return;
  kernel_->last_sync_timestamp_ = timestamp;
  kernel_->info_status_ = KERNEL_SHARE_INFO_DIRTY;
}

bool Directory::initial_sync_ended() const {
  ScopedKernelLock lock(this);
  return kernel_->initial_sync_ended_;
}

void Directory::set_initial_sync_ended(bool x) {
  ScopedKernelLock lock(this);
  if (kernel_->initial_sync_ended_ == x)
    return;
  kernel_->initial_sync_ended_ = x;
  kernel_->info_status_ = KERNEL_SHARE_INFO_DIRTY;
}

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

void Directory::set_store_birthday(string store_birthday) {
  ScopedKernelLock lock(this);
  if (kernel_->store_birthday_ == store_birthday)
    return;
  kernel_->store_birthday_ = store_birthday;
  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_;
}

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::GetUnsyncedMetaHandles(BaseTransaction* trans,
                                       UnsyncedMetaHandles* result) {
  result->clear();
  ScopedKernelLock lock(this);
  copy(kernel_->unsynced_metahandles->begin(),
       kernel_->unsynced_metahandles->end(), back_inserter(*result));
}

void Directory::GetAllExtendedAttributes(BaseTransaction* trans,
                                         int64 metahandle,
                                         std::set<ExtendedAttribute>* result) {
  AttributeKeySet keys;
  GetExtendedAttributesList(trans, metahandle, &keys);
  AttributeKeySet::iterator iter;
  for (iter = keys.begin(); iter != keys.end(); ++iter) {
      ExtendedAttributeKey key(metahandle, *iter);
      ExtendedAttribute extended_attribute(trans, GET_BY_HANDLE, key);
      CHECK(extended_attribute.good());
      result->insert(extended_attribute);
  }
}

void Directory::GetExtendedAttributesList(BaseTransaction* trans,
    int64 metahandle, AttributeKeySet* result) {
  ExtendedAttributes::iterator iter;
  for (iter = kernel_->extended_attributes->begin();
       iter != kernel_->extended_attributes->end(); ++iter) {
    if (iter->first.metahandle == metahandle) {
      if (!iter->second.is_deleted)
        result->insert(iter->first.key);
    }
  }
}

void Directory::DeleteAllExtendedAttributes(WriteTransaction* trans,
                                            int64 metahandle) {
  AttributeKeySet keys;
  GetExtendedAttributesList(trans, metahandle, &keys);
  AttributeKeySet::iterator iter;
  for (iter = keys.begin(); iter != keys.end(); ++iter) {
    ExtendedAttributeKey key(metahandle, *iter);
    MutableExtendedAttribute attribute(trans, GET_BY_HANDLE, key);
    // This flags the attribute for deletion during SaveChanges.  At that time
    // any deleted attributes are purged from disk and memory.
    attribute.delete_attribute();
  }
}

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

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


class IdFilter {
 public:
  virtual ~IdFilter() { }
  virtual bool ShouldConsider(const Id& id) const = 0;
};


class FullScanFilter : public IdFilter {
 public:
  virtual bool ShouldConsider(const Id& id) const {
    return true;
  }
};

class SomeIdsFilter : public IdFilter {
 public:
  virtual bool ShouldConsider(const Id& id) const {
    return binary_search(ids_.begin(), ids_.end(), id);
  }
  std::vector<Id> ids_;
};

void Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
                                    const OriginalEntries* originals) {
  MetahandleSet handles;
  SomeIdsFilter filter;
  filter.ids_.reserve(originals->size());
  for (OriginalEntries::const_iterator i = originals->begin(),
         end = originals->end(); i != end; ++i) {
    Entry e(trans, GET_BY_HANDLE, i->ref(META_HANDLE));
    CHECK(e.good());
    filter.ids_.push_back(e.Get(ID));
    handles.insert(i->ref(META_HANDLE));
  }
  std::sort(filter.ids_.begin(), filter.ids_.end());
  CheckTreeInvariants(trans, handles, filter);
}

void Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
                                    bool full_scan) {
  // TODO(timsteele):  This is called every time a WriteTransaction finishes.
  // The performance hit is substantial given that we now examine every single
  // syncable entry.  Need to redesign this.
  MetahandleSet handles;
  GetAllMetaHandles(trans, &handles);
  if (full_scan) {
    FullScanFilter fullfilter;
    CheckTreeInvariants(trans, handles, fullfilter);
  } else {
    SomeIdsFilter filter;
    MetahandleSet::iterator i;
    for (i = handles.begin() ; i != handles.end() ; ++i) {
      Entry e(trans, GET_BY_HANDLE, *i);
      CHECK(e.good());
      filter.ids_.push_back(e.Get(ID));
    }
    sort(filter.ids_.begin(), filter.ids_.end());
    CheckTreeInvariants(trans, handles, filter);
  }
}

void Directory::CheckTreeInvariants(syncable::BaseTransaction* trans,
                                    const MetahandleSet& handles,
                                    const IdFilter& idfilter) {
  int64 max_ms = kInvariantCheckMaxMs;
  if (max_ms < 0)
    max_ms = std::numeric_limits<int64>::max();
  PerfTimer check_timer;
  MetahandleSet::const_iterator i;
  int entries_done = 0;
  for (i = handles.begin() ; i != handles.end() ; ++i) {
    int64 metahandle = *i;
    Entry e(trans, GET_BY_HANDLE, metahandle);
    CHECK(e.good());
    syncable::Id id = e.Get(ID);
    syncable::Id parentid = e.Get(PARENT_ID);

    if (id.IsRoot()) {
      CHECK(e.Get(IS_DIR)) << e;
      CHECK(parentid.IsRoot()) << e;
      CHECK(!e.Get(IS_UNSYNCED)) << e;
      ++entries_done;
      continue;
    }
    if (!e.Get(IS_DEL)) {
      CHECK(id != parentid) << e;
      CHECK(!e.Get(NAME).empty()) << e;
      int safety_count = handles.size() + 1;
      while (!parentid.IsRoot()) {
        if (!idfilter.ShouldConsider(parentid))
          break;
        Entry parent(trans, GET_BY_ID, parentid);
        CHECK(parent.good()) << e;
        CHECK(parent.Get(IS_DIR)) << parent << e;
        CHECK(!parent.Get(IS_DEL)) << parent << e;
        CHECK(handles.end() != handles.find(parent.Get(META_HANDLE)))
            << e << parent;
        parentid = parent.Get(PARENT_ID);
        CHECK(--safety_count >= 0) << e << parent;
      }
    }
    int64 base_version = e.Get(BASE_VERSION);
    int64 server_version = e.Get(SERVER_VERSION);
    if (CHANGES_VERSION == base_version || 0 == base_version) {
      if (e.Get(IS_UNAPPLIED_UPDATE)) {
        // Unapplied new item.
        CHECK(e.Get(IS_DEL)) << e;
        CHECK(id.ServerKnows()) << e;
      } else {
        // Uncommitted item.
        if (!e.Get(IS_DEL)) {
          CHECK(e.Get(IS_UNSYNCED)) << e;
        }
        CHECK(0 == server_version) << e;
        CHECK(!id.ServerKnows()) << e;
      }
    } else {
      CHECK(id.ServerKnows());
    }
    ++entries_done;
    int64 elapsed_ms = check_timer.Elapsed().InMilliseconds();
    if (elapsed_ms > max_ms) {
      LOG(INFO) << "Cutting Invariant check short after " << elapsed_ms << "ms."
        " Processed " << entries_done << "/" << handles.size() << " entries";
      return;
    }
  }
  // I did intend to add a check here to ensure no entries had been pulled into
  // memory by this function, but we can't guard against another ReadTransaction
  // pulling entries into RAM
}

///////////////////////////////////////////////////////////////////////////////
// ScopedKernelLocks

ScopedKernelLock::ScopedKernelLock(const Directory* dir)
  : dir_(const_cast<Directory*>(dir)) {
  // Swap out the dbhandle to enforce the "No IO while holding kernel
  // lock" rule.
  // HA!! Yeah right. What about your pre-cached queries :P
  pthread_mutex_lock(&dir->kernel_->mutex);
}
ScopedKernelLock::~ScopedKernelLock() {
  pthread_mutex_unlock(&dir_->kernel_->mutex);
}

ScopedKernelUnlock::ScopedKernelUnlock(ScopedKernelLock* lock)
  : lock_(lock) {
  pthread_mutex_unlock(&lock->dir_->kernel_->mutex);
}
ScopedKernelUnlock::~ScopedKernelUnlock() {
  pthread_mutex_lock(&lock_->dir_->kernel_->mutex);
}

///////////////////////////////////////////////////////////////////////////
// Transactions
#if defined LOG_ALL || !defined NDEBUG
static const bool kLoggingInfo = true;
#else
static const bool kLoggingInfo = false;
#endif

ThreadNode* BaseTransaction::MakeThreadNode() {
  ThreadNode* node = reinterpret_cast<ThreadNode*>
    (pthread_getspecific(dirkernel_->thread_node_key));
  if (NULL == node) {
    node = new ThreadNode;
    node->id = GetCurrentThreadId();
    pthread_setspecific(dirkernel_->thread_node_key, node);
  } else if (node->in_list) {
    logging::LogMessage(source_file_, line_, logging::LOG_FATAL).stream()
      << " Recursive Lock attempt by thread id " << node->id << "." << std::endl
      << "Already entered transaction at " << node->file << ":" << node->line;
  }
  node->file = source_file_;
  node->line = line_;
  node->wait_started = base::TimeTicks::Now();
  return node;
}

void BaseTransaction::Lock(ThreadCounts* const thread_counts,
                           ThreadNode* node, TransactionClass tclass) {
  ScopedTransactionLock lock(&dirkernel_->transaction_mutex);
  // Increment the waiters count.
  node->tclass = tclass;
  thread_counts->waiting += 1;
  node->Insert(&thread_counts->waiting_headtail);

  // Block until we can own the reader/writer lock
  bool ready = 1 == thread_counts->waiting;
  while (true) {
    if (ready) {
      if (0 == thread_counts->active) {
        // We can take the lock because there is no contention.
        break;
      } else if (READ == tclass
                 && READ == thread_counts->active_headtail.next->tclass) {
        // We can take the lock because reads can run simultaneously.
        break;
      }
    }
    // Wait to be woken up and check again.
    node->wake_up = false;
    do {
      CHECK(0 == pthread_cond_wait(&node->condvar.condvar_,
                                   &dirkernel_->transaction_mutex.mutex_));
    } while (!node->wake_up);
    ready = true;
  }

  // Move from the list of waiters to the list of active.
  thread_counts->waiting -= 1;
  thread_counts->active += 1;
  CHECK(WRITE != tclass || 1 == thread_counts->active);
  node->Remove();
  node->Insert(&thread_counts->active_headtail);
  if (WRITE == tclass)
    node->current_write_trans = static_cast<WriteTransaction*>(this);
}

void BaseTransaction::AfterLock(ThreadNode* node) {
  time_acquired_ = base::TimeTicks::Now();

  const base::TimeDelta elapsed = time_acquired_ - node->wait_started;
  if (kLoggingInfo && elapsed.InMilliseconds() > 200) {
    logging::LogMessage(source_file_, line_, logging::LOG_INFO).stream()
      << name_ << " transaction waited "
      << elapsed.InSecondsF() << " seconds.";
  }
}

void BaseTransaction::Init(ThreadCounts* const thread_counts,
                           TransactionClass tclass) {
  ThreadNode* const node = MakeThreadNode();
  Lock(thread_counts, node, tclass);
  AfterLock(node);
}

BaseTransaction::BaseTransaction(Directory* directory, const char* name,
                 const char* source_file, int line)
  : directory_(directory), dirkernel_(directory->kernel_), name_(name),
    source_file_(source_file), line_(line) {
}

void BaseTransaction::UnlockAndLog(ThreadCounts* const thread_counts,
                                   OriginalEntries* originals_arg) {
  scoped_ptr<OriginalEntries> originals(originals_arg);
  const base::TimeDelta elapsed = base::TimeTicks::Now() - time_acquired_;
  if (kLoggingInfo && elapsed.InMilliseconds() > 50) {
    logging::LogMessage(source_file_, line_, logging::LOG_INFO).stream()
        << name_ << " transaction completed in " << elapsed.InSecondsF()
        << " seconds.";
  }

  {
    ScopedTransactionLock lock(&dirkernel_->transaction_mutex);
    // Let go of the reader/writer lock
    thread_counts->active -= 1;
    ThreadNode* const node = reinterpret_cast<ThreadNode*>
      (pthread_getspecific(dirkernel_->thread_node_key));
    CHECK(node != NULL);
    node->Remove();
    node->current_write_trans = NULL;
    if (0 == thread_counts->active) {
      // Wake up a waiting thread, FIFO
      if (dirkernel_->thread_counts.waiting > 0) {
        ThreadNode* const headtail =
          &dirkernel_->thread_counts.waiting_headtail;
        ThreadNode* node = headtail->next;
        node->wake_up = true;
        CHECK(0 == pthread_cond_signal(&node->condvar.condvar_));
        if (READ == node->tclass) do {
          // Wake up all consecutive readers.
          node = node->next;
          if (node == headtail)
            break;
          if (READ != node->tclass)
            break;
          node->wake_up = true;
          CHECK(0 == pthread_cond_signal(&node->condvar.condvar_));
        } while (true);
      }
    }
    if (NULL == originals.get() || originals->empty())
      return;
    dirkernel_->changes_channel_mutex.Lock();
    // Tell listeners to calculate changes while we still have the mutex.
    DirectoryChangeEvent event = { DirectoryChangeEvent::CALCULATE_CHANGES,
                                   originals.get(), this, writer_ };
    dirkernel_->changes_channel->NotifyListeners(event);
  }
  DirectoryChangeEvent event = { DirectoryChangeEvent::TRANSACTION_COMPLETE,
                                 NULL, NULL, INVALID };
  dirkernel_->changes_channel->NotifyListeners(event);
  dirkernel_->changes_channel_mutex.Unlock();
}

ReadTransaction::ReadTransaction(Directory* directory, const char* file,
                                 int line)
  : BaseTransaction(directory, "Read", file, line) {
  Init(&dirkernel_->thread_counts, READ);
  writer_ = INVALID;
}

ReadTransaction::ReadTransaction(const ScopedDirLookup& scoped_dir,
                                 const char* file, int line)
  : BaseTransaction(scoped_dir.operator -> (), "Read", file, line) {
  Init(&dirkernel_->thread_counts, READ);
  writer_ = INVALID;
}

ReadTransaction::~ReadTransaction() {
  UnlockAndLog(&dirkernel_->thread_counts, NULL);
}

WriteTransaction::WriteTransaction(Directory* directory, WriterTag writer,
                                   const char* file, int line)
  : BaseTransaction(directory, "Write", file, line), skip_destructor_(false),
    originals_(new OriginalEntries) {
  Init(&dirkernel_->thread_counts, WRITE);
  writer_ = writer;
}

WriteTransaction::WriteTransaction(const ScopedDirLookup& scoped_dir,
                                   WriterTag writer, const char* file, int line)
  : BaseTransaction(scoped_dir.operator -> (), "Write", file, line),
    skip_destructor_(false), originals_(new OriginalEntries) {
  Init(&dirkernel_->thread_counts, WRITE);
  writer_ = writer;
}

WriteTransaction::WriteTransaction(Directory* directory, const char* name,
                                   WriterTag writer,
                                   const char* file, int line,
                                   bool skip_destructor,
                                   OriginalEntries* originals)
  : BaseTransaction(directory, name, file, line),
    skip_destructor_(skip_destructor), originals_(originals) {
  writer_ = writer;
}

void WriteTransaction::SaveOriginal(EntryKernel* entry) {
  if (NULL == entry)
    return;
  OriginalEntries::iterator i = originals_->lower_bound(*entry);
  if (i == originals_->end() ||
      i->ref(META_HANDLE) != entry->ref(META_HANDLE)) {
    originals_->insert(i, *entry);
  }
}

WriteTransaction::~WriteTransaction() {
  if (skip_destructor_)
    return;
  if (OFF != kInvariantCheckLevel) {
    const bool full_scan = (FULL_DB_VERIFICATION == kInvariantCheckLevel);
    if (full_scan)
      directory()->CheckTreeInvariants(this, full_scan);
    else
      directory()->CheckTreeInvariants(this, originals_);
  }
  UnlockAndLog(&dirkernel_->thread_counts, originals_);
}

///////////////////////////////////////////////////////////////////////////
// Entry

Entry::Entry(BaseTransaction* trans, GetById, const Id& id)
    : basetrans_(trans) {
  kernel_ = trans->directory()->GetEntryById(id);
}

Entry::Entry(BaseTransaction* trans, GetByTag, const PathString& tag)
    : basetrans_(trans) {
  kernel_ = trans->directory()->GetEntryByTag(tag);
}

Entry::Entry(BaseTransaction* trans, GetByHandle, int64 metahandle)
    : basetrans_(trans) {
  kernel_ = trans->directory()->GetEntryByHandle(metahandle);
}

Entry::Entry(BaseTransaction* trans, GetByPath, const PathString& path)
    : basetrans_(trans) {
  kernel_ = trans->directory()->GetEntryByPath(path);
}

Entry::Entry(BaseTransaction* trans, GetByParentIdAndName, const Id& parentid,
             const PathString& name)
    : basetrans_(trans) {
  kernel_ = trans->directory()->GetChildWithName(parentid, name);
}

Entry::Entry(BaseTransaction* trans, GetByParentIdAndDBName, const Id& parentid,
             const PathString& name)
    : basetrans_(trans) {
  kernel_ = trans->directory()->GetChildWithDBName(parentid, name);
}


Directory* Entry::dir() const {
  return basetrans_->directory();
}

PathString Entry::Get(StringField field) const {
  DCHECK(kernel_);
  return kernel_->ref(field);
}

void Entry::GetAllExtendedAttributes(BaseTransaction* trans,
    std::set<ExtendedAttribute> *result) {
  dir()->GetAllExtendedAttributes(trans, kernel_->ref(META_HANDLE), result);
}

void Entry::GetExtendedAttributesList(BaseTransaction* trans,
    AttributeKeySet* result) {
  dir()->GetExtendedAttributesList(trans, kernel_->ref(META_HANDLE), result);
}

void Entry::DeleteAllExtendedAttributes(WriteTransaction *trans) {
  dir()->DeleteAllExtendedAttributes(trans, kernel_->ref(META_HANDLE));
}

///////////////////////////////////////////////////////////////////////////
// MutableEntry

MutableEntry::MutableEntry(WriteTransaction* trans, Create,
                           const Id& parent_id, const PathString& name)
  : Entry(trans) {
  if (NULL != trans->directory()->GetChildWithName(parent_id, name)) {
    kernel_ = NULL;  // would have duplicated an existing entry.
    return;
  }
  Init(trans, parent_id, name);
}


void MutableEntry::Init(WriteTransaction* trans, const Id& parent_id,
                        const PathString& name) {
  kernel_ = new EntryKernel;
  ZeroFields(kernel_, BEGIN_FIELDS);
  kernel_->ref(ID) = trans->directory_->NextId();
  kernel_->dirty[ID] = true;
  kernel_->ref(META_HANDLE) = trans->directory_->NextMetahandle();
  kernel_->dirty[META_HANDLE] = true;
  kernel_->ref(PARENT_ID) = parent_id;
  kernel_->dirty[PARENT_ID] = true;
  kernel_->ref(NAME) = name;
  kernel_->dirty[NAME] = true;
  kernel_->ref(NON_UNIQUE_NAME) = name;
  kernel_->dirty[NON_UNIQUE_NAME] = true;
  kernel_->ref(IS_NEW) = true;
  const int64 now = Now();
  kernel_->ref(CTIME) = now;
  kernel_->dirty[CTIME] = true;
  kernel_->ref(MTIME) = now;
  kernel_->dirty[MTIME] = true;
  // We match the database defaults here
  kernel_->ref(BASE_VERSION) = CHANGES_VERSION;
  trans->directory()->InsertEntry(kernel_);
  // Because this entry is new, it was originally deleted.
  kernel_->ref(IS_DEL) = true;
  trans->SaveOriginal(kernel_);
  kernel_->ref(IS_DEL) = false;
}

MutableEntry::MutableEntry(WriteTransaction* trans, CreateNewUpdateItem,
                           const Id& id)
  : Entry(trans) {
  Entry same_id(trans, GET_BY_ID, id);
  if (same_id.good()) {
    kernel_ = NULL;  // already have an item with this ID.
    return;
  }
  kernel_ = new EntryKernel;
  ZeroFields(kernel_, BEGIN_FIELDS);
  kernel_->ref(ID) = id;
  kernel_->dirty[ID] = true;
  kernel_->ref(META_HANDLE) = trans->directory_->NextMetahandle();
  kernel_->dirty[META_HANDLE] = true;
  kernel_->ref(IS_DEL) = true;
  kernel_->dirty[IS_DEL] = true;
  kernel_->ref(IS_NEW) = true;
  // We match the database defaults here
  kernel_->ref(BASE_VERSION) = CHANGES_VERSION;
  trans->directory()->InsertEntry(kernel_);
  trans->SaveOriginal(kernel_);
}

MutableEntry::MutableEntry(WriteTransaction* trans, GetById, const Id& id)
  : Entry(trans, GET_BY_ID, id) {
  trans->SaveOriginal(kernel_);
}

MutableEntry::MutableEntry(WriteTransaction* trans, GetByHandle,
                           int64 metahandle)
  : Entry(trans, GET_BY_HANDLE, metahandle) {
  trans->SaveOriginal(kernel_);
}

MutableEntry::MutableEntry(WriteTransaction* trans, GetByPath,
                           const PathString& path)
  : Entry(trans, GET_BY_PATH, path) {
  trans->SaveOriginal(kernel_);
}

MutableEntry::MutableEntry(WriteTransaction* trans, GetByParentIdAndName,
                           const Id& parentid, const PathString& name)
  : Entry(trans, GET_BY_PARENTID_AND_NAME, parentid, name) {
  trans->SaveOriginal(kernel_);
}

MutableEntry::MutableEntry(WriteTransaction* trans, GetByParentIdAndDBName,
                           const Id& parentid, const PathString& name)
  : Entry(trans, GET_BY_PARENTID_AND_DBNAME, parentid, name) {
  trans->SaveOriginal(kernel_);
}

bool MutableEntry::PutIsDel(bool is_del) {
  DCHECK(kernel_);
  if (is_del == kernel_->ref(IS_DEL))
    return true;
  if (is_del) {
    UnlinkFromOrder();
    if (!dir()->Delete(kernel_))
      return false;
    return true;
  } else {
    if (!dir()->Undelete(kernel_))
      return false;
    PutPredecessor(Id());  // Restores position to the 0th index.
    return true;
  }
}

bool MutableEntry::Put(Int64Field field, const int64& value) {
  DCHECK(kernel_);
  if (kernel_->ref(field) != value) {
    kernel_->ref(field) = value;
    kernel_->dirty[static_cast<int>(field)] = true;
  }
  return true;
}

bool MutableEntry::Put(IdField field, const Id& value) {
  DCHECK(kernel_);
  if (kernel_->ref(field) != value) {
    if (ID == field) {
      if (!dir()->ReindexId(kernel_, value))
        return false;
    } else if (PARENT_ID == field) {
      if (!dir()->ReindexParentIdAndName(kernel_, value, kernel_->ref(NAME)))
        return false;
    } else {
      kernel_->ref(field) = value;
    }
    kernel_->dirty[static_cast<int>(field)] = true;
  }
  return true;
}

WriteTransaction* MutableEntry::trans() const {
  // We are in a mutable entry, so we must be in a write transaction.
  // Maybe we could keep a pointer to the transaction in MutableEntry.
  ThreadNode* node = reinterpret_cast<ThreadNode*>
    (pthread_getspecific(dir()->kernel_->thread_node_key));
  return node->current_write_trans;
}

bool MutableEntry::Put(BaseVersion field, int64 value) {
  DCHECK(kernel_);
  if (kernel_->ref(field) != value) {
    kernel_->ref(field) = value;
    kernel_->dirty[static_cast<int>(field)] = true;
  }
  return true;
}

bool MutableEntry::Put(StringField field, const PathString& value) {
  return PutImpl(field, value);
}

bool MutableEntry::PutImpl(StringField field, const PathString& value) {
  DCHECK(kernel_);
  if (kernel_->ref(field) != value) {
    if (NAME == field) {
      if (!dir()->ReindexParentIdAndName(kernel_, kernel_->ref(PARENT_ID),
          value))
        return false;
    } else {
      kernel_->ref(field) = value;
    }
    kernel_->dirty[static_cast<int>(field)] = true;
  }
  return true;
}

bool MutableEntry::Put(IndexedBitField field, bool value) {
  DCHECK(kernel_);
  if (kernel_->ref(field) != value) {
    MetahandleSet* index;
    if (IS_UNSYNCED == field)
      index = dir()->kernel_->unsynced_metahandles;
    else
      index = dir()->kernel_->unapplied_update_metahandles;

    ScopedKernelLock lock(dir());
    if (value)
      CHECK(index->insert(kernel_->ref(META_HANDLE)).second);
    else
      CHECK(1 == index->erase(kernel_->ref(META_HANDLE)));
    kernel_->ref(field) = value;
    kernel_->dirty[static_cast<int>(field)] = true;
  }
  return true;
}

// Avoids temporary collision in index when renaming a bookmark to another
// folder.
bool MutableEntry::PutParentIdAndName(const Id& parent_id,
                                      const Name& name) {
  DCHECK(kernel_);
  const bool parent_id_changes = parent_id != kernel_->ref(PARENT_ID);
  bool db_name_changes = name.db_value() != kernel_->ref(NAME);
  if (parent_id_changes || db_name_changes) {
    if (!dir()->ReindexParentIdAndName(kernel_, parent_id,
                                       name.db_value()))
      return false;
  }
  Put(UNSANITIZED_NAME, name.GetUnsanitizedName());
  Put(NON_UNIQUE_NAME, name.non_unique_value());
  if (db_name_changes)
    kernel_->dirty[NAME] = true;
  if (parent_id_changes) {
    kernel_->dirty[PARENT_ID] = true;
    PutPredecessor(Id());  // Put in the 0th position.
  }
  return true;
}

void MutableEntry::UnlinkFromOrder() {
  Id old_previous = Get(PREV_ID);
  Id old_next = Get(NEXT_ID);

  // Self-looping signifies that this item is not in the order.  If we were to
  // set these to 0, we could get into trouble because this node might look
  // like the first node in the ordering.
  Put(NEXT_ID, Get(ID));
  Put(PREV_ID, Get(ID));

  if (!old_previous.IsRoot()) {
    if (old_previous == old_next) {
      // Note previous == next doesn't imply previous == next == Get(ID). We
      // could have prev==next=="c-XX" and Get(ID)=="sX..." if an item was added
      // and deleted before receiving the server ID in the commit response.
      CHECK((old_next == Get(ID)) || !old_next.ServerKnows());
      return;  // Done if we were already self-looped (hence unlinked).
    }
    MutableEntry previous_entry(trans(), GET_BY_ID, old_previous);
    CHECK(previous_entry.good());
    previous_entry.Put(NEXT_ID, old_next);
  }

  if (!old_next.IsRoot()) {
    MutableEntry next_entry(trans(), GET_BY_ID, old_next);
    CHECK(next_entry.good());
    next_entry.Put(PREV_ID, old_previous);
  }
}

bool MutableEntry::PutPredecessor(const Id& predecessor_id) {
  // TODO(ncarter): Maybe there should be an independent HAS_POSITION bit?
  if (!Get(IS_BOOKMARK_OBJECT))
    return true;
  UnlinkFromOrder();

  if (Get(IS_DEL)) {
    DCHECK(predecessor_id.IsNull());
    return true;
  }

  // This is classic insert-into-doubly-linked-list from CS 101 and your last
  // job interview.  An "IsRoot" Id signifies the head or tail.
  Id successor_id;
  if (!predecessor_id.IsRoot()) {
    MutableEntry predecessor(trans(), GET_BY_ID, predecessor_id);
    CHECK(predecessor.good());
    if (predecessor.Get(PARENT_ID) != Get(PARENT_ID))
      return false;
    successor_id = predecessor.Get(NEXT_ID);
    predecessor.Put(NEXT_ID, Get(ID));
  } else {
    syncable::Directory* dir = trans()->directory();
    successor_id = dir->GetFirstChildId(trans(), Get(PARENT_ID));
  }
  if (!successor_id.IsRoot()) {
    MutableEntry successor(trans(), GET_BY_ID, successor_id);
    CHECK(successor.good());
    if (successor.Get(PARENT_ID) != Get(PARENT_ID))
      return false;
    successor.Put(PREV_ID, Get(ID));
  }
  DCHECK(predecessor_id != Get(ID));
  DCHECK(successor_id != Get(ID));
  Put(PREV_ID, predecessor_id);
  Put(NEXT_ID, successor_id);
  return true;
}

///////////////////////////////////////////////////////////////////////////
// High-level functions

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_->next_id)--;
    kernel_->info_status_ = KERNEL_SHARE_INFO_DIRTY;
  }
  DCHECK_LT(result, 0);
  return Id::CreateFromClientString(Int64ToString(result));
}

Id Directory::GetChildWithNullIdField(IdField field,
                                      BaseTransaction* trans,
                                      const Id& parent_id) {
  // This query is O(number of children), which should be acceptable
  // when this method is used as the first step in enumerating the children of
  // a node.  But careless use otherwise could potentially result in
  // O((number of children)^2) performance.
  ChildHandles child_handles;
  GetChildHandles(trans, parent_id, &child_handles);
  ChildHandles::const_iterator it;
  for (it = child_handles.begin(); it != child_handles.end(); ++it) {
    Entry e(trans, GET_BY_HANDLE, *it);
    CHECK(e.good());
    if (e.Get(field).IsRoot())
      return e.Get(ID);
  }

  return Id();
}

Id Directory::GetFirstChildId(BaseTransaction* trans,
                              const Id& parent_id) {
  return GetChildWithNullIdField(PREV_ID, trans, parent_id);
}

Id Directory::GetLastChildId(BaseTransaction* trans,
                             const Id& parent_id) {
  return GetChildWithNullIdField(NEXT_ID, trans, parent_id);
}

ExtendedAttribute::ExtendedAttribute(BaseTransaction* trans, GetByHandle,
                                     const ExtendedAttributeKey& key) {
  Directory::Kernel* const kernel = trans->directory()->kernel_;
  ScopedKernelLock lock(trans->directory());
  Init(trans, kernel, &lock, key);
}

bool ExtendedAttribute::Init(BaseTransaction* trans,
                             Directory::Kernel* const kernel,
                             ScopedKernelLock* lock,
                             const ExtendedAttributeKey& key) {
  i_ = kernel->extended_attributes->find(key);
  good_ = kernel->extended_attributes->end() != i_;
  return good_;
}

MutableExtendedAttribute::MutableExtendedAttribute(
    WriteTransaction* trans, GetByHandle,
    const ExtendedAttributeKey& key) :
        ExtendedAttribute(trans, GET_BY_HANDLE, key) {
}

MutableExtendedAttribute::MutableExtendedAttribute(
    WriteTransaction* trans, Create, const ExtendedAttributeKey& key) {
  Directory::Kernel* const kernel = trans->directory()->kernel_;
  ScopedKernelLock lock(trans->directory());
  if (!Init(trans, kernel, &lock, key)) {
    ExtendedAttributeValue val;
    val.dirty = true;
    i_ = kernel->extended_attributes->insert(std::make_pair(key, val)).first;
    good_ = true;
  }
}

bool IsLegalNewParent(BaseTransaction* trans, const Id& entry_id,
                      const Id& new_parent_id) {
  if (entry_id.IsRoot())
    return false;
  // we have to ensure that the entry is not an ancestor of the new parent.
  Id ancestor_id = new_parent_id;
  while (!ancestor_id.IsRoot()) {
    if (entry_id == ancestor_id)
      return false;
    Entry new_parent(trans, GET_BY_ID, ancestor_id);
    CHECK(new_parent.good());
    ancestor_id = new_parent.Get(PARENT_ID);
  }
  return true;
}

// returns -1 if s contains any non [0-9] characters
static int PathStringToInteger(PathString s) {
  PathString::const_iterator i = s.begin();
  for (; i != s.end(); ++i) {
    if (PathString::npos == PathString(PSTR("0123456789")).find(*i))
      return -1;
  }
  return
#if !PATHSTRING_IS_STD_STRING
  _wtoi
#else
  atoi
#endif
  (s.c_str());
}

static PathString IntegerToPathString(int i) {
  const size_t kBufSize = 25;
  PathChar buf[kBufSize];
#if !PATHSTRING_IS_STD_STRING
  const int radix = 10;
  _itow(i, buf, radix);
#else
  snprintf(buf, kBufSize, "%d", i);
#endif
  return buf;
}

// appends ~1 to the end of 's' unless there is already ~#, in which case
// it just increments the number
static PathString FixBasenameInCollision(const PathString s) {
  PathString::size_type last_tilde = s.find_last_of(PSTR('~'));
  if (PathString::npos == last_tilde) return s + PSTR("~1");
  if (s.size() == (last_tilde + 1)) return s + PSTR("1");
  // we have ~, but not necessarily ~# (for some number >= 0). check for that
  int n;
  if ((n = PathStringToInteger(s.substr(last_tilde + 1))) != -1) {
    n++;
    PathString pre_number = s.substr(0, last_tilde + 1);
    return pre_number + IntegerToPathString(n);
  } else {
    // we have a ~, but not a number following it, so we'll add another
    // ~ and this time, a number
    return s + PSTR("~1");
  }
}

void DBName::MakeNoncollidingForEntry(BaseTransaction* trans,
                                      const Id& parent_id,
                                      Entry* e) {
  const PathString& desired_name = *this;
  CHECK(!desired_name.empty());
  PathString::size_type first_dot = desired_name.find_first_of(PSTR('.'));
  if (PathString::npos == first_dot)
    first_dot = desired_name.size();
  PathString basename = desired_name.substr(0, first_dot);
  PathString dotextension = desired_name.substr(first_dot);
  CHECK(basename + dotextension == desired_name);
  for (;;) {
    // Check for collision.
    PathString testname = basename + dotextension;
    Entry same_path_entry(trans, GET_BY_PARENTID_AND_DBNAME,
                          parent_id, testname);
    if (!same_path_entry.good() || (e && same_path_entry.Get(ID) == e->Get(ID)))
      break;
    // There was a collision, so fix the name.
    basename = FixBasenameInCollision(basename);
  }
  // Set our value to the new value.  This invalidates desired_name.
  PathString new_value = basename + dotextension;
  swap(new_value);
}

PathString GetFullPath(BaseTransaction* trans, const Entry& e) {
  PathString result;
#ifdef COMPILER_MSVC
  result.reserve(MAX_PATH);
#endif
  ReverseAppend(e.Get(NAME), &result);
  Id id = e.Get(PARENT_ID);
  while (!id.IsRoot()) {
    result.push_back(kPathSeparator[0]);
    Entry ancestor(trans, GET_BY_ID, id);
    if (!ancestor.good()) {
      // This can happen if the parent folder got deleted before the entry.
      LOG(WARNING) << "Cannot get full path of " << e
                   << "\nbecause an ancestor folder has been deleted.";
      result.clear();
      return result;
    }
    ReverseAppend(ancestor.Get(NAME), &result);
    id = ancestor.Get(PARENT_ID);
  }
  result.push_back(kPathSeparator[0]);
  reverse(result.begin(), result.end());
  return result;
}

const Blob* GetExtendedAttributeValue(const Entry& e,
                                      const PathString& attribute_name) {
  ExtendedAttributeKey key(e.Get(META_HANDLE), attribute_name);
  ExtendedAttribute extended_attribute(e.trans(), GET_BY_HANDLE, key);
  if (extended_attribute.good() && !extended_attribute.is_deleted())
    return &extended_attribute.value();
  return NULL;
}

// This function sets only the flags needed to get this entry to sync.
void MarkForSyncing(syncable::MutableEntry* e) {
  DCHECK_NE(static_cast<MutableEntry*>(NULL), e);
  DCHECK(!e->IsRoot()) << "We shouldn't mark a permanent object for syncing.";
  e->Put(IS_UNSYNCED, true);
  e->Put(SYNCING, false);
}

}  // namespace syncable

namespace {
  class DumpSeparator {
  } separator;
  class DumpColon {
  } colon;
}  // namespace

inline FastDump& operator<<(FastDump& dump, const DumpSeparator&) {
  dump.out_->sputn(", ", 2);
  return dump;
}

inline FastDump& operator<<(FastDump& dump, const DumpColon&) {
  dump.out_->sputn(": ", 2);
  return dump;
}

std::ostream& operator<<(std::ostream& stream, const syncable::Entry& entry) {
  // Using ostreams directly here is dreadfully slow, because a mutex is
  // acquired for every <<.  Users noticed it spiking CPU.
  using browser_sync::ToUTF8;
  using syncable::BitField;
  using syncable::BitTemp;
  using syncable::BlobField;
  using syncable::EntryKernel;
  using syncable::g_metas_columns;
  using syncable::IdField;
  using syncable::Int64Field;
  using syncable::StringField;
  using syncable::BEGIN_FIELDS;
  using syncable::BIT_FIELDS_END;
  using syncable::BIT_TEMPS_BEGIN;
  using syncable::BIT_TEMPS_END;
  using syncable::BLOB_FIELDS_END;
  using syncable::INT64_FIELDS_END;
  using syncable::ID_FIELDS_END;
  using syncable::STRING_FIELDS_END;

  int i;
  FastDump s(&stream);
  EntryKernel* const kernel = entry.kernel_;
  for (i = BEGIN_FIELDS; i < INT64_FIELDS_END; ++i) {
    s << g_metas_columns[i].name << colon
      << kernel->ref(static_cast<Int64Field>(i)) << separator;
  }
  for ( ; i < ID_FIELDS_END; ++i) {
    s << g_metas_columns[i].name << colon
      << kernel->ref(static_cast<IdField>(i)) << separator;
  }
  s << "Flags: ";
  for ( ; i < BIT_FIELDS_END; ++i) {
    if (kernel->ref(static_cast<BitField>(i)))
      s << g_metas_columns[i].name << separator;
  }
  for ( ; i < STRING_FIELDS_END; ++i) {
    ToUTF8 field(kernel->ref(static_cast<StringField>(i)));
    s << g_metas_columns[i].name << colon << field.get_string() << separator;
  }
  for ( ; i < BLOB_FIELDS_END; ++i) {
    s << g_metas_columns[i].name << colon
      << kernel->ref(static_cast<BlobField>(i)) << separator;
  }
  s << "TempFlags: ";
  for ( ; i < BIT_TEMPS_END; ++i) {
    if (kernel->ref(static_cast<BitTemp>(i)))
      s << "#" << i - BIT_TEMPS_BEGIN << separator;
  }
  return stream;
}

std::ostream& operator<<(std::ostream& s, const syncable::Blob& blob) {
  for (syncable::Blob::const_iterator i = blob.begin(); i != blob.end(); ++i)
    s << std::hex << std::setw(2)
      << std::setfill('0') << static_cast<unsigned int>(*i);
  return s << std::dec;
}

FastDump& operator<<(FastDump& dump, const syncable::Blob& blob) {
  if (blob.empty())
    return dump;
  string buffer(HexEncode(&blob[0], blob.size()));
  dump.out_->sputn(buffer.c_str(), buffer.size());
  return dump;
}

std::ostream& operator<<(std::ostream& s, const syncable::ThreadNode& node) {
  s << "thread id: " << std::hex << node.id << "\n"
    << "file: " << node.file << "\n"
    << "line: " << std::dec << node.line << "\n"
    << "wait_started: " << node.wait_started.ToInternalValue();
  return s;
}