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