metadata_database.cc revision 58537e28ecd584eab876aee8be7156509866d23a 
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 "chrome/browser/sync_file_system/drive_backend/metadata_database.h"
6
7#include <algorithm>
8#include <stack>
9
10#include "base/bind.h"
11#include "base/callback.h"
12#include "base/files/file_path.h"
13#include "base/location.h"
14#include "base/memory/scoped_vector.h"
15#include "base/message_loop/message_loop_proxy.h"
16#include "base/sequenced_task_runner.h"
17#include "base/stl_util.h"
18#include "base/strings/string_number_conversions.h"
19#include "base/strings/string_util.h"
20#include "base/strings/stringprintf.h"
21#include "base/task_runner_util.h"
22#include "base/threading/thread_restrictions.h"
23#include "chrome/browser/google_apis/drive_api_parser.h"
24#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
25#include "chrome/browser/sync_file_system/drive_backend/metadata_db_migration_util.h"
26#include "chrome/browser/sync_file_system/logger.h"
27#include "chrome/browser/sync_file_system/syncable_file_system_util.h"
28#include "third_party/leveldatabase/src/include/leveldb/db.h"
29#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
30#include "webkit/common/fileapi/file_system_util.h"
31
32namespace sync_file_system {
33namespace drive_backend {
34
35const char kDatabaseVersionKey[] = "VERSION";
36const int64 kCurrentDatabaseVersion = 3;
37const char kServiceMetadataKey[] = "SERVICE";
38const char kFileMetadataKeyPrefix[] = "FILE: ";
39const char kFileTrackerKeyPrefix[] = "TRACKER: ";
40
41struct DatabaseContents {
42  scoped_ptr<ServiceMetadata> service_metadata;
43  ScopedVector<FileMetadata> file_metadata;
44  ScopedVector<FileTracker> file_trackers;
45};
46
47namespace {
48
49typedef MetadataDatabase::FileByID FileByID;
50typedef MetadataDatabase::TrackerByID TrackerByID;
51typedef MetadataDatabase::TrackersByParentAndTitle TrackersByParentAndTitle;
52typedef MetadataDatabase::TrackersByTitle TrackersByTitle;
53
54bool IsAppRoot(const FileTracker& tracker) {
55  return tracker.tracker_kind() == TRACKER_KIND_APP_ROOT ||
56      tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
57}
58
59std::string RemovePrefix(const std::string& str, const std::string& prefix) {
60  if (StartsWithASCII(str, prefix, true))
61    return str.substr(prefix.size());
62  return str;
63}
64
65base::FilePath ReverseConcatPathComponents(
66    const std::vector<base::FilePath>& components) {
67  if (components.empty())
68    return base::FilePath(FILE_PATH_LITERAL("/")).NormalizePathSeparators();
69
70  size_t total_size = 0;
71  typedef std::vector<base::FilePath> PathComponents;
72  for (PathComponents::const_iterator itr = components.begin();
73       itr != components.end(); ++itr)
74    total_size += itr->value().size() + 1;
75
76  base::FilePath::StringType result;
77  result.reserve(total_size);
78  for (PathComponents::const_reverse_iterator itr = components.rbegin();
79       itr != components.rend(); ++itr) {
80    result.append(1, base::FilePath::kSeparators[0]);
81    result.append(itr->value());
82  }
83
84  return base::FilePath(result).NormalizePathSeparators();
85}
86
87void PopulateFileDetailsByFileResource(
88    const google_apis::FileResource& file_resource,
89    FileDetails* details) {
90  details->clear_parent_folder_ids();
91  for (ScopedVector<google_apis::ParentReference>::const_iterator itr =
92           file_resource.parents().begin();
93       itr != file_resource.parents().end();
94       ++itr) {
95    details->add_parent_folder_ids((*itr)->file_id());
96  }
97  details->set_title(file_resource.title());
98
99  google_apis::DriveEntryKind kind = file_resource.GetKind();
100  if (kind == google_apis::ENTRY_KIND_FILE)
101    details->set_file_kind(FILE_KIND_FILE);
102  else if (kind == google_apis::ENTRY_KIND_FOLDER)
103    details->set_file_kind(FILE_KIND_FOLDER);
104  else
105    details->set_file_kind(FILE_KIND_UNSUPPORTED);
106
107  details->set_md5(file_resource.md5_checksum());
108  details->set_etag(file_resource.etag());
109  details->set_creation_time(file_resource.created_date().ToInternalValue());
110  details->set_modification_time(
111      file_resource.modified_date().ToInternalValue());
112  details->set_deleted(false);
113}
114
115scoped_ptr<FileMetadata> CreateFileMetadataFromChangeResource(
116    const google_apis::ChangeResource& change) {
117  scoped_ptr<FileMetadata> file(new FileMetadata);
118  file->set_file_id(change.file_id());
119
120  FileDetails* details = file->mutable_details();
121  details->set_change_id(change.change_id());
122
123  if (change.is_deleted()) {
124    details->set_deleted(true);
125    return file.Pass();
126  }
127
128  PopulateFileDetailsByFileResource(*change.file(), details);
129  return file.Pass();
130}
131
132void CreateInitialSyncRootTracker(
133    int64 tracker_id,
134    const google_apis::FileResource& file_resource,
135    scoped_ptr<FileMetadata>* file_out,
136    scoped_ptr<FileTracker>* tracker_out) {
137  FileDetails details;
138  PopulateFileDetailsByFileResource(file_resource, &details);
139
140  scoped_ptr<FileMetadata> file(new FileMetadata);
141  file->set_file_id(file_resource.file_id());
142  *file->mutable_details() = details;
143
144  scoped_ptr<FileTracker> tracker(new FileTracker);
145  tracker->set_tracker_id(tracker_id);
146  tracker->set_file_id(file_resource.file_id());
147  tracker->set_parent_tracker_id(0);
148  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
149  tracker->set_dirty(false);
150  tracker->set_active(true);
151  tracker->set_needs_folder_listing(false);
152  *tracker->mutable_synced_details() = details;
153
154  *file_out = file.Pass();
155  *tracker_out = tracker.Pass();
156}
157
158void CreateInitialAppRootTracker(
159    int64 tracker_id,
160    const FileTracker& parent_tracker,
161    const google_apis::FileResource& file_resource,
162    scoped_ptr<FileMetadata>* file_out,
163    scoped_ptr<FileTracker>* tracker_out) {
164  FileDetails details;
165  PopulateFileDetailsByFileResource(file_resource, &details);
166
167  scoped_ptr<FileMetadata> file(new FileMetadata);
168  file->set_file_id(file_resource.file_id());
169  *file->mutable_details() = details;
170
171  scoped_ptr<FileTracker> tracker(new FileTracker);
172  tracker->set_tracker_id(tracker_id);
173  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
174  tracker->set_file_id(file_resource.file_id());
175  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
176  tracker->set_dirty(false);
177  tracker->set_active(false);
178  tracker->set_needs_folder_listing(false);
179  *tracker->mutable_synced_details() = details;
180
181  *file_out = file.Pass();
182  *tracker_out = tracker.Pass();
183}
184
185void AdaptLevelDBStatusToSyncStatusCode(const SyncStatusCallback& callback,
186                                        const leveldb::Status& status) {
187  callback.Run(LevelDBStatusToSyncStatusCode(status));
188}
189
190void PutServiceMetadataToBatch(const ServiceMetadata& service_metadata,
191                               leveldb::WriteBatch* batch) {
192  std::string value;
193  bool success = service_metadata.SerializeToString(&value);
194  DCHECK(success);
195  batch->Put(kServiceMetadataKey, value);
196}
197
198void PutFileToBatch(const FileMetadata& file, leveldb::WriteBatch* batch) {
199  std::string value;
200  bool success = file.SerializeToString(&value);
201  DCHECK(success);
202  batch->Put(kFileMetadataKeyPrefix + file.file_id(), value);
203}
204
205void PutTrackerToBatch(const FileTracker& tracker, leveldb::WriteBatch* batch) {
206  std::string value;
207  bool success = tracker.SerializeToString(&value);
208  DCHECK(success);
209  batch->Put(kFileTrackerKeyPrefix + base::Int64ToString(tracker.tracker_id()),
210             value);
211}
212
213void PutFileDeletionToBatch(const std::string& file_id,
214                            leveldb::WriteBatch* batch) {
215  batch->Delete(kFileMetadataKeyPrefix + file_id);
216}
217
218void PutTrackerDeletionToBatch(int64 tracker_id, leveldb::WriteBatch* batch) {
219  batch->Delete(kFileTrackerKeyPrefix + base::Int64ToString(tracker_id));
220}
221
222template <typename OutputIterator>
223OutputIterator PushChildTrackersToContainer(
224    const TrackersByParentAndTitle& trackers_by_parent,
225    int64 parent_tracker_id,
226    OutputIterator target_itr) {
227  TrackersByParentAndTitle::const_iterator found =
228      trackers_by_parent.find(parent_tracker_id);
229  if (found == trackers_by_parent.end())
230    return target_itr;
231
232  for (TrackersByTitle::const_iterator title_itr = found->second.begin();
233       title_itr != found->second.end(); ++title_itr) {
234    const TrackerSet& trackers = title_itr->second;
235    for (TrackerSet::const_iterator tracker_itr = trackers.begin();
236         tracker_itr != trackers.end(); ++tracker_itr) {
237      *target_itr = (*tracker_itr)->tracker_id();
238      ++target_itr;
239    }
240  }
241  return target_itr;
242}
243
244std::string GetTrackerTitle(const FileTracker& tracker) {
245  if (tracker.has_synced_details())
246    return tracker.synced_details().title();
247  return std::string();
248}
249
250// Returns true if |db| has no content.
251bool IsDatabaseEmpty(leveldb::DB* db) {
252  DCHECK(db);
253  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
254  itr->SeekToFirst();
255  return !itr->Valid();
256}
257
258SyncStatusCode OpenDatabase(const base::FilePath& path,
259                            scoped_ptr<leveldb::DB>* db_out,
260                            bool* created) {
261  base::ThreadRestrictions::AssertIOAllowed();
262  DCHECK(db_out);
263  DCHECK(created);
264
265  leveldb::Options options;
266  options.max_open_files = 0;  // Use minimum.
267  options.create_if_missing = true;
268  leveldb::DB* db = NULL;
269  leveldb::Status db_status =
270      leveldb::DB::Open(options, path.AsUTF8Unsafe(), &db);
271  SyncStatusCode status = LevelDBStatusToSyncStatusCode(db_status);
272  if (status != SYNC_STATUS_OK) {
273    delete db;
274    return status;
275  }
276
277  *created = IsDatabaseEmpty(db);
278  db_out->reset(db);
279  return status;
280}
281
282SyncStatusCode MigrateDatabaseIfNeeded(leveldb::DB* db) {
283  base::ThreadRestrictions::AssertIOAllowed();
284  DCHECK(db);
285  std::string value;
286  leveldb::Status status =
287      db->Get(leveldb::ReadOptions(), kDatabaseVersionKey, &value);
288  int64 version = 0;
289  if (status.ok()) {
290    if (!base::StringToInt64(value, &version))
291      return SYNC_DATABASE_ERROR_FAILED;
292  } else {
293    if (!status.IsNotFound())
294      return SYNC_DATABASE_ERROR_FAILED;
295  }
296
297  switch (version) {
298    case 0:
299      drive_backend::MigrateDatabaseFromV0ToV1(db);
300      // fall-through
301    case 1:
302      drive_backend::MigrateDatabaseFromV1ToV2(db);
303      // fall-through
304    case 2:
305      // TODO(tzik): Migrate database from version 2 to 3.
306      //   * Add sync-root folder as active, dirty and needs_folder_listing
307      //     folder.
308      //   * Add app-root folders for each origins.  Each app-root folder for
309      //     an enabled origin should be a active, dirty and
310      //     needs_folder_listing folder.  And Each app-root folder for a
311      //     disabled origin should be an inactive, dirty and
312      //     non-needs_folder_listing folder.
313      //   * Add a file metadata for each file in previous version.
314      NOTIMPLEMENTED();
315      return SYNC_DATABASE_ERROR_FAILED;
316      // fall-through
317    case 3:
318      DCHECK_EQ(3, kCurrentDatabaseVersion);
319      return SYNC_STATUS_OK;
320    default:
321      return SYNC_DATABASE_ERROR_FAILED;
322  }
323}
324
325SyncStatusCode WriteVersionInfo(leveldb::DB* db) {
326  base::ThreadRestrictions::AssertIOAllowed();
327  DCHECK(db);
328  return LevelDBStatusToSyncStatusCode(
329      db->Put(leveldb::WriteOptions(),
330              kDatabaseVersionKey,
331              base::Int64ToString(kCurrentDatabaseVersion)));
332}
333
334SyncStatusCode ReadDatabaseContents(leveldb::DB* db,
335                                    DatabaseContents* contents) {
336  base::ThreadRestrictions::AssertIOAllowed();
337  DCHECK(db);
338  DCHECK(contents);
339
340  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
341  for (itr->SeekToFirst(); itr->Valid(); itr->Next()) {
342    std::string key = itr->key().ToString();
343    std::string value = itr->value().ToString();
344    if (key == kServiceMetadataKey) {
345      scoped_ptr<ServiceMetadata> service_metadata(new ServiceMetadata);
346      if (!service_metadata->ParseFromString(value)) {
347        util::Log(logging::LOG_WARNING, FROM_HERE,
348                  "Failed to parse SyncServiceMetadata");
349        continue;
350      }
351
352      contents->service_metadata = service_metadata.Pass();
353      continue;
354    }
355
356    if (StartsWithASCII(key, kFileMetadataKeyPrefix, true)) {
357      std::string file_id = RemovePrefix(key, kFileMetadataKeyPrefix);
358
359      scoped_ptr<FileMetadata> file(new FileMetadata);
360      if (!file->ParseFromString(itr->value().ToString())) {
361        util::Log(logging::LOG_WARNING, FROM_HERE,
362                  "Failed to parse a FileMetadata");
363        continue;
364      }
365
366      contents->file_metadata.push_back(file.release());
367      continue;
368    }
369
370    if (StartsWithASCII(key, kFileTrackerKeyPrefix, true)) {
371      int64 tracker_id = 0;
372      if (!base::StringToInt64(RemovePrefix(key, kFileTrackerKeyPrefix),
373                               &tracker_id)) {
374        util::Log(logging::LOG_WARNING, FROM_HERE,
375                  "Failed to parse TrackerID");
376        continue;
377      }
378
379      scoped_ptr<FileTracker> tracker(new FileTracker);
380      if (!tracker->ParseFromString(itr->value().ToString())) {
381        util::Log(logging::LOG_WARNING, FROM_HERE,
382                  "Failed to parse a Tracker");
383        continue;
384      }
385      contents->file_trackers.push_back(tracker.release());
386      continue;
387    }
388  }
389
390  return SYNC_STATUS_OK;
391}
392
393SyncStatusCode InitializeServiceMetadata(DatabaseContents* contents,
394                                         leveldb::WriteBatch* batch) {
395  if (!contents->service_metadata) {
396    contents->service_metadata.reset(new ServiceMetadata);
397    contents->service_metadata->set_next_tracker_id(1);
398
399    std::string value;
400    contents->service_metadata->SerializeToString(&value);
401    batch->Put(kServiceMetadataKey, value);
402  }
403  return SYNC_STATUS_OK;
404}
405
406SyncStatusCode RemoveUnreachableItems(DatabaseContents* contents,
407                                      leveldb::WriteBatch* batch) {
408  TrackerByID unvisited_trackers;
409  typedef std::map<int64, std::set<FileTracker*> > TrackersByParent;
410  TrackersByParent trackers_by_parent;
411
412  for (ScopedVector<FileTracker>::iterator itr =
413           contents->file_trackers.begin();
414       itr != contents->file_trackers.end();
415       ++itr) {
416    FileTracker* tracker = *itr;
417    DCHECK(!ContainsKey(unvisited_trackers, tracker->tracker_id()));
418    unvisited_trackers[tracker->tracker_id()] = tracker;
419    if (tracker->parent_tracker_id())
420      trackers_by_parent[tracker->parent_tracker_id()].insert(tracker);
421  }
422
423  // Traverse synced tracker tree. Take only active items, app-root and their
424  // children. Drop unreachable items.
425  ScopedVector<FileTracker> reachable_trackers;
426  std::stack<int64> pending;
427  if (contents->service_metadata->sync_root_tracker_id())
428    pending.push(contents->service_metadata->sync_root_tracker_id());
429
430  while (!pending.empty()) {
431    int64 tracker_id = pending.top();
432    pending.pop();
433
434    {
435      TrackerByID::iterator found = unvisited_trackers.find(tracker_id);
436      if (found == unvisited_trackers.end())
437        continue;
438
439      FileTracker* tracker = found->second;
440      unvisited_trackers.erase(found);
441      reachable_trackers.push_back(tracker);
442
443      if (!tracker->active())
444        continue;
445    }
446
447    TrackersByParent::iterator found = trackers_by_parent.find(tracker_id);
448    if (found == trackers_by_parent.end())
449      continue;
450
451    for (std::set<FileTracker*>::const_iterator itr =
452             found->second.begin();
453         itr != found->second.end();
454         ++itr)
455      pending.push((*itr)->tracker_id());
456  }
457
458  // Delete all unreachable trackers.
459  for (TrackerByID::iterator itr = unvisited_trackers.begin();
460       itr != unvisited_trackers.end(); ++itr) {
461    FileTracker* tracker = itr->second;
462    PutTrackerDeletionToBatch(tracker->tracker_id(), batch);
463    delete tracker;
464  }
465  unvisited_trackers.clear();
466
467  // |reachable_trackers| contains all files/folders reachable from sync-root
468  // folder via active folders and app-root folders.
469  // Update the tracker set in database contents with the reachable tracker set.
470  contents->file_trackers.weak_clear();
471  contents->file_trackers.swap(reachable_trackers);
472
473  // Do the similar traverse for FileMetadata and remove FileMetadata that don't
474  // have reachable trackers.
475  FileByID unreferred_files;
476  for (ScopedVector<FileMetadata>::const_iterator itr =
477           contents->file_metadata.begin();
478       itr != contents->file_metadata.end();
479       ++itr) {
480    unreferred_files.insert(std::make_pair((*itr)->file_id(), *itr));
481  }
482
483  ScopedVector<FileMetadata> referred_files;
484  for (ScopedVector<FileTracker>::const_iterator itr =
485           contents->file_trackers.begin();
486       itr != contents->file_trackers.end();
487       ++itr) {
488    FileByID::iterator found = unreferred_files.find((*itr)->file_id());
489    if (found != unreferred_files.end()) {
490      referred_files.push_back(found->second);
491      unreferred_files.erase(found);
492    }
493  }
494
495  for (FileByID::iterator itr = unreferred_files.begin();
496       itr != unreferred_files.end(); ++itr) {
497    FileMetadata* file = itr->second;
498    PutFileDeletionToBatch(file->file_id(), batch);
499    delete file;
500  }
501  unreferred_files.clear();
502
503  contents->file_metadata.weak_clear();
504  contents->file_metadata.swap(referred_files);
505
506  return SYNC_STATUS_OK;
507}
508
509template <typename Container, typename Key, typename Value>
510bool FindItem(const Container& container, const Key& key, Value* value) {
511  typename Container::const_iterator found = container.find(key);
512  if (found == container.end())
513    return false;
514  if (value)
515    *value = *found->second;
516  return true;
517}
518
519template <typename Container, typename Key>
520typename Container::mapped_type FindAndEraseItem(Container* container,
521                                                 const Key& key) {
522  typedef typename Container::mapped_type Value;
523  typename Container::iterator found = container->find(key);
524  if (found == container->end())
525    return Value();
526
527  Value result = found->second;
528  container->erase(found);
529  return result;
530}
531
532void RunSoon(const tracked_objects::Location& from_here,
533             const base::Closure& closure) {
534  base::MessageLoopProxy::current()->PostTask(from_here, closure);
535}
536
537}  // namespace
538
539bool MetadataDatabase::DirtyTrackerComparator::operator()(
540    const FileTracker* left,
541    const FileTracker* right) const {
542  return left->tracker_id() < right->tracker_id();
543}
544
545// static
546void MetadataDatabase::Create(base::SequencedTaskRunner* task_runner,
547                              const base::FilePath& database_path,
548                              const CreateCallback& callback) {
549  task_runner->PostTask(FROM_HERE, base::Bind(
550      &CreateOnTaskRunner,
551      base::MessageLoopProxy::current(),
552      make_scoped_refptr(task_runner),
553      database_path, callback));
554}
555
556MetadataDatabase::~MetadataDatabase() {
557  task_runner_->DeleteSoon(FROM_HERE, db_.release());
558  STLDeleteContainerPairSecondPointers(
559      file_by_id_.begin(), file_by_id_.end());
560  STLDeleteContainerPairSecondPointers(
561      tracker_by_id_.begin(), tracker_by_id_.end());
562}
563
564int64 MetadataDatabase::GetLargestChangeID() const {
565  return service_metadata_->largest_change_id();
566}
567
568int64 MetadataDatabase::GetSyncRootTrackerID() const {
569  return service_metadata_->sync_root_tracker_id();
570}
571
572bool MetadataDatabase::HasSyncRoot() const {
573  return service_metadata_->has_sync_root_tracker_id() &&
574      !!service_metadata_->sync_root_tracker_id();
575}
576
577void MetadataDatabase::PopulateInitialData(
578    int64 largest_change_id,
579    const google_apis::FileResource& sync_root_folder,
580    const ScopedVector<google_apis::FileResource>& app_root_folders,
581    const SyncStatusCallback& callback) {
582  DCHECK(tracker_by_id_.empty());
583  DCHECK(file_by_id_.empty());
584
585  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
586  service_metadata_->set_largest_change_id(largest_change_id);
587
588  FileTracker* sync_root_tracker = NULL;
589  int64 sync_root_tracker_id = 0;
590  {
591    scoped_ptr<FileMetadata> folder;
592    scoped_ptr<FileTracker> tracker;
593    CreateInitialSyncRootTracker(GetNextTrackerID(batch.get()),
594                                 sync_root_folder,
595                                 &folder,
596                                 &tracker);
597    std::string sync_root_folder_id = folder->file_id();
598    sync_root_tracker = tracker.get();
599    sync_root_tracker_id = tracker->tracker_id();
600
601    PutFileToBatch(*folder, batch.get());
602    PutTrackerToBatch(*tracker, batch.get());
603
604    service_metadata_->set_sync_root_tracker_id(tracker->tracker_id());
605    PutServiceMetadataToBatch(*service_metadata_, batch.get());
606
607    trackers_by_file_id_[folder->file_id()].Insert(tracker.get());
608
609    file_by_id_[sync_root_folder_id] = folder.release();
610    tracker_by_id_[sync_root_tracker_id] = tracker.release();
611  }
612
613  for (ScopedVector<google_apis::FileResource>::const_iterator itr =
614           app_root_folders.begin();
615       itr != app_root_folders.end();
616       ++itr) {
617    const google_apis::FileResource& folder_resource = **itr;
618    scoped_ptr<FileMetadata> folder;
619    scoped_ptr<FileTracker> tracker;
620    CreateInitialAppRootTracker(GetNextTrackerID(batch.get()),
621                                *sync_root_tracker,
622                                folder_resource,
623                                &folder,
624                                &tracker);
625    std::string title = folder->details().title();
626    std::string folder_id = folder->file_id();
627    int64 tracker_id = tracker->tracker_id();
628
629    PutFileToBatch(*folder, batch.get());
630    PutTrackerToBatch(*tracker, batch.get());
631
632    trackers_by_file_id_[folder_id].Insert(tracker.get());
633    trackers_by_parent_and_title_[sync_root_tracker_id][title]
634        .Insert(tracker.get());
635
636    file_by_id_[folder_id] = folder.release();
637    tracker_by_id_[tracker_id] = tracker.release();
638  }
639
640  WriteToDatabase(batch.Pass(), callback);
641}
642
643
644void MetadataDatabase::RegisterApp(const std::string& app_id,
645                                   const std::string& folder_id,
646                                   const SyncStatusCallback& callback) {
647  if (FindAppRootTracker(app_id, NULL)) {
648    // The app-root is already registered.
649    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
650    return;
651  }
652
653  TrackerSet trackers;
654  if (!FindTrackersByFileID(folder_id, &trackers) || trackers.has_active()) {
655    // The folder is tracked by another tracker.
656    util::Log(logging::LOG_WARNING, FROM_HERE,
657              "Failed to register App for %s", app_id.c_str());
658    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_HAS_CONFLICT));
659    return;
660  }
661
662  int64 sync_root_tracker_id = service_metadata_->sync_root_tracker_id();
663  if (!sync_root_tracker_id) {
664    util::Log(logging::LOG_WARNING, FROM_HERE,
665              "Sync-root needs to be set up before registering app-root");
666    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
667    return;
668  }
669
670  // Make this tracker an app-root tracker.
671  FileTracker* app_root_tracker = NULL;
672  for (TrackerSet::iterator itr = trackers.begin();
673       itr != trackers.end(); ++itr) {
674    FileTracker* tracker = *itr;
675    if (tracker->parent_tracker_id() == sync_root_tracker_id)
676      app_root_tracker = tracker;
677  }
678
679  if (!app_root_tracker) {
680    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
681    return;
682  }
683
684  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
685  RegisterTrackerAsAppRoot(app_id, app_root_tracker->tracker_id(), batch.get());
686  WriteToDatabase(batch.Pass(), callback);
687}
688
689void MetadataDatabase::DisableApp(const std::string& app_id,
690                                  const SyncStatusCallback& callback) {
691  FileTracker tracker;
692  if (!FindAppRootTracker(app_id, &tracker)) {
693    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
694    return;
695  }
696
697  if (tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
698    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
699    return;
700  }
701
702  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
703  MakeAppRootDisabled(tracker.tracker_id(), batch.get());
704  WriteToDatabase(batch.Pass(), callback);
705}
706
707void MetadataDatabase::EnableApp(const std::string& app_id,
708                                 const SyncStatusCallback& callback) {
709  FileTracker tracker;
710  if (!FindAppRootTracker(app_id, &tracker) ||
711      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
712    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
713    return;
714  }
715
716  if (tracker.tracker_kind() == TRACKER_KIND_APP_ROOT) {
717    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
718    return;
719  }
720
721  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
722  MakeAppRootEnabled(tracker.tracker_id(), batch.get());
723  WriteToDatabase(batch.Pass(), callback);
724}
725
726void MetadataDatabase::UnregisterApp(const std::string& app_id,
727                                     const SyncStatusCallback& callback) {
728  FileTracker tracker;
729  if (!FindAppRootTracker(app_id, &tracker) ||
730      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
731    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
732    return;
733  }
734
735  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
736  UnregisterTrackerAsAppRoot(app_id, batch.get());
737  WriteToDatabase(batch.Pass(), callback);
738}
739
740bool MetadataDatabase::FindAppRootTracker(const std::string& app_id,
741                                          FileTracker* tracker) const {
742  return FindItem(app_root_by_app_id_, app_id, tracker);
743}
744
745bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
746                                        FileMetadata* file) const {
747  return FindItem(file_by_id_, file_id, file);
748}
749
750bool MetadataDatabase::FindTrackersByFileID(const std::string& file_id,
751                                            TrackerSet* trackers) const {
752  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
753  if (found == trackers_by_file_id_.end())
754    return false;
755  if (trackers)
756    *trackers = found->second;
757  return true;
758}
759
760bool MetadataDatabase::FindTrackerByTrackerID(int64 tracker_id,
761                                              FileTracker* tracker) const {
762  return FindItem(tracker_by_id_, tracker_id, tracker);
763}
764
765bool MetadataDatabase::BuildPathForTracker(int64 tracker_id,
766                                           base::FilePath* path) const {
767  FileTracker current;
768  if (!FindTrackerByTrackerID(tracker_id, &current) || !current.active())
769    return false;
770
771  std::vector<base::FilePath> components;
772  while (!IsAppRoot(current)) {
773    std::string title = GetTrackerTitle(current);
774    if (title.empty())
775      return false;
776    components.push_back(base::FilePath::FromUTF8Unsafe(title));
777    if (!FindTrackerByTrackerID(current.parent_tracker_id(), &current) ||
778        !current.active())
779      return false;
780  }
781
782  if (path)
783    *path = ReverseConcatPathComponents(components);
784
785  return true;
786}
787
788void MetadataDatabase::UpdateByChangeList(
789    ScopedVector<google_apis::ChangeResource> changes,
790    const SyncStatusCallback& callback) {
791  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
792
793  for (ScopedVector<google_apis::ChangeResource>::const_iterator itr =
794           changes.begin();
795       itr != changes.end();
796       ++itr) {
797    const google_apis::ChangeResource& change = **itr;
798    scoped_ptr<FileMetadata> file(
799        CreateFileMetadataFromChangeResource(change));
800    std::string file_id = file->file_id();
801
802    MarkTrackersDirtyByFileID(file_id, batch.get());
803    if (!file->details().deleted())
804      MaybeAddTrackersForNewFile(*file, batch.get());
805
806    if (FindTrackersByFileID(file_id, NULL)) {
807      PutFileToBatch(*file, batch.get());
808
809      FileMetadata* file_ptr = file.release();
810      std::swap(file_ptr, file_by_id_[file_id]);
811      delete file_ptr;
812    }
813  }
814
815  WriteToDatabase(batch.Pass(), callback);
816}
817
818void MetadataDatabase::PopulateFolderByChildList(
819    const std::string& folder_id,
820    const FileIDList& child_file_ids,
821    const SyncStatusCallback& callback) {
822  TrackerSet trackers;
823  if (!FindTrackersByFileID(folder_id, &trackers) ||
824      !trackers.has_active()) {
825    // It's OK that there is no folder to populate its children.
826    // Inactive folders should ignore their contents updates.
827    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
828    return;
829  }
830
831  FileTracker* folder_tracker =
832      tracker_by_id_[trackers.active_tracker()->tracker_id()];
833  DCHECK(folder_tracker);
834  std::set<std::string> children(child_file_ids.begin(), child_file_ids.end());
835
836  std::vector<int64> known_children;
837  PushChildTrackersToContainer(trackers_by_parent_and_title_,
838                               folder_tracker->tracker_id(),
839                               std::back_inserter(known_children));
840  for (std::vector<int64>::iterator itr = known_children.begin();
841       itr != known_children.end(); ++itr)
842    children.erase(tracker_by_id_[*itr]->file_id());
843
844  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
845  for (FileIDList::const_iterator itr = child_file_ids.begin();
846       itr != child_file_ids.end(); ++itr)
847    CreateTrackerForParentAndFileID(*folder_tracker, *itr, batch.get());
848  folder_tracker->set_needs_folder_listing(false);
849  if (folder_tracker->dirty() && !ShouldKeepDirty(*folder_tracker)) {
850    folder_tracker->set_dirty(false);
851    dirty_trackers_.erase(folder_tracker);
852  }
853  PutTrackerToBatch(*folder_tracker, batch.get());
854
855  WriteToDatabase(batch.Pass(), callback);
856}
857
858void MetadataDatabase::UpdateTracker(int64 tracker_id,
859                                     const FileDetails& updated_details,
860                                     const SyncStatusCallback& callback) {
861  TrackerByID::iterator found = tracker_by_id_.find(tracker_id);
862  if (found == tracker_by_id_.end()) {
863    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
864    return;
865  }
866
867  FileTracker* tracker = found->second;
868  DCHECK(tracker);
869
870  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
871
872  if (updated_details.deleted()) {
873    // The update deletes the local file.
874    FileByID::iterator found = file_by_id_.find(tracker->file_id());
875    if (found == file_by_id_.end() || found->second->details().deleted()) {
876      // Both the tracker and metadata have the deleted flag, now it's safe to
877      // delete the |tracker|.
878      RemoveTracker(tracker->tracker_id(), batch.get());
879    } else {
880      // The local file is deleted, but corresponding remote file isn't.
881      // Put the tracker back to the initial state.
882      tracker->clear_synced_details();
883      tracker->set_dirty(true);
884      tracker->set_active(false);
885      PutTrackerToBatch(*tracker, batch.get());
886    }
887
888    WriteToDatabase(batch.Pass(), callback);
889    return;
890  }
891
892  // Check if the tracker was retitled.  If it was, update the title and its
893  // index in advance.
894  if (!tracker->has_synced_details() ||
895      tracker->synced_details().title() != updated_details.title()) {
896    UpdateTrackerTitle(tracker, updated_details.title(), batch.get());
897  }
898
899  *tracker->mutable_synced_details() = updated_details;
900
901  // Activate the tracker if:
902  //   - There is no active tracker that tracks |tracker->file_id()|.
903  //   - There is no active tracker that has the same |parent| and |title|.
904  if (!tracker->active() && CanActivateTracker(*tracker))
905    MakeTrackerActive(tracker->tracker_id(), batch.get());
906  if (tracker->dirty() && !ShouldKeepDirty(*tracker)) {
907    tracker->set_dirty(false);
908    dirty_trackers_.erase(tracker);
909  }
910  PutTrackerToBatch(*tracker, batch.get());
911
912  WriteToDatabase(batch.Pass(), callback);
913}
914
915MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner)
916    : task_runner_(task_runner), weak_ptr_factory_(this) {
917  DCHECK(task_runner);
918}
919
920// static
921void MetadataDatabase::CreateOnTaskRunner(
922    base::SingleThreadTaskRunner* callback_runner,
923    base::SequencedTaskRunner* task_runner,
924    const base::FilePath& database_path,
925    const CreateCallback& callback) {
926  scoped_ptr<MetadataDatabase> metadata_database(
927      new MetadataDatabase(task_runner));
928  SyncStatusCode status =
929      metadata_database->InitializeOnTaskRunner(database_path);
930  if (status != SYNC_STATUS_OK)
931    metadata_database.reset();
932
933  callback_runner->PostTask(FROM_HERE, base::Bind(
934      callback, status, base::Passed(&metadata_database)));
935}
936
937// static
938SyncStatusCode MetadataDatabase::CreateForTesting(
939    scoped_ptr<leveldb::DB> db,
940    scoped_ptr<MetadataDatabase>* metadata_database_out) {
941  scoped_ptr<MetadataDatabase> metadata_database(
942      new MetadataDatabase(base::MessageLoopProxy::current()));
943  metadata_database->db_ = db.Pass();
944  SyncStatusCode status =
945      metadata_database->InitializeOnTaskRunner(base::FilePath());
946  if (status == SYNC_STATUS_OK)
947    *metadata_database_out = metadata_database.Pass();
948  return status;
949}
950
951SyncStatusCode MetadataDatabase::InitializeOnTaskRunner(
952    const base::FilePath& database_path) {
953  base::ThreadRestrictions::AssertIOAllowed();
954  DCHECK(task_runner_->RunsTasksOnCurrentThread());
955
956  SyncStatusCode status = SYNC_STATUS_UNKNOWN;
957  bool created = false;
958  // Open database unless |db_| is overridden for testing.
959  if (!db_) {
960    status = OpenDatabase(database_path, &db_, &created);
961    if (status != SYNC_STATUS_OK)
962      return status;
963  }
964
965  if (created) {
966    status = WriteVersionInfo(db_.get());
967    if (status != SYNC_STATUS_OK)
968      return status;
969  } else {
970    status = MigrateDatabaseIfNeeded(db_.get());
971    if (status != SYNC_STATUS_OK)
972      return status;
973  }
974
975  DatabaseContents contents;
976  status = ReadDatabaseContents(db_.get(), &contents);
977  if (status != SYNC_STATUS_OK)
978    return status;
979
980  leveldb::WriteBatch batch;
981  status = InitializeServiceMetadata(&contents, &batch);
982  if (status != SYNC_STATUS_OK)
983    return status;
984
985  status = RemoveUnreachableItems(&contents, &batch);
986  if (status != SYNC_STATUS_OK)
987    return status;
988
989  status = LevelDBStatusToSyncStatusCode(
990      db_->Write(leveldb::WriteOptions(), &batch));
991  if (status != SYNC_STATUS_OK)
992    return status;
993
994  BuildIndexes(&contents);
995  return status;
996}
997
998void MetadataDatabase::BuildIndexes(DatabaseContents* contents) {
999  service_metadata_ = contents->service_metadata.Pass();
1000
1001  for (ScopedVector<FileMetadata>::const_iterator itr =
1002           contents->file_metadata.begin();
1003       itr != contents->file_metadata.end();
1004       ++itr) {
1005    file_by_id_[(*itr)->file_id()] = *itr;
1006  }
1007  contents->file_metadata.weak_clear();
1008
1009  for (ScopedVector<FileTracker>::const_iterator itr =
1010           contents->file_trackers.begin();
1011       itr != contents->file_trackers.end();
1012       ++itr) {
1013    FileTracker* tracker = *itr;
1014    tracker_by_id_[tracker->tracker_id()] = tracker;
1015    trackers_by_file_id_[tracker->file_id()].Insert(tracker);
1016
1017    if (IsAppRoot(*tracker))
1018      app_root_by_app_id_[tracker->app_id()] = tracker;
1019
1020    if (tracker->parent_tracker_id()) {
1021      std::string title = GetTrackerTitle(*tracker);
1022      TrackerSet* trackers =
1023          &trackers_by_parent_and_title_[tracker->parent_tracker_id()][title];
1024      trackers->Insert(tracker);
1025    }
1026
1027    if (tracker->dirty())
1028      dirty_trackers_.insert(tracker);
1029  }
1030  contents->file_trackers.weak_clear();
1031}
1032
1033void MetadataDatabase::RegisterTrackerAsAppRoot(
1034    const std::string& app_id,
1035    int64 tracker_id,
1036    leveldb::WriteBatch* batch) {
1037  FileTracker* tracker = tracker_by_id_[tracker_id];
1038  DCHECK(tracker);
1039  tracker->set_app_id(app_id);
1040  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
1041  app_root_by_app_id_[app_id] = tracker;
1042
1043  MakeTrackerActive(tracker->tracker_id(), batch);
1044}
1045
1046void MetadataDatabase::UnregisterTrackerAsAppRoot(
1047    const std::string& app_id,
1048    leveldb::WriteBatch* batch) {
1049  FileTracker* tracker = FindAndEraseItem(&app_root_by_app_id_, app_id);
1050  tracker->set_app_id(std::string());
1051  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1052
1053  // Inactivate the tracker to drop all descendant.
1054  // (Note that we set tracker_kind to TRACKER_KIND_REGULAR before calling
1055  // this.)
1056  MakeTrackerInactive(tracker->tracker_id(), batch);
1057}
1058
1059void MetadataDatabase::MakeTrackerActive(int64 tracker_id,
1060                                         leveldb::WriteBatch* batch) {
1061  FileTracker* tracker = tracker_by_id_[tracker_id];
1062  DCHECK(tracker);
1063  DCHECK(!tracker->active());
1064
1065  int64 parent_tracker_id = tracker->parent_tracker_id();
1066  DCHECK(tracker->has_synced_details());
1067  trackers_by_file_id_[tracker->file_id()].Activate(tracker);
1068  if (parent_tracker_id) {
1069    trackers_by_parent_and_title_[parent_tracker_id][
1070        tracker->synced_details().title()].Activate(tracker);
1071  }
1072  tracker->set_active(true);
1073  tracker->set_needs_folder_listing(
1074      tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
1075  tracker->set_dirty(true);
1076  dirty_trackers_.insert(tracker);
1077
1078  PutTrackerToBatch(*tracker, batch);
1079}
1080
1081void MetadataDatabase::MakeTrackerInactive(int64 tracker_id,
1082                                           leveldb::WriteBatch* batch) {
1083  FileTracker* tracker = tracker_by_id_[tracker_id];
1084  DCHECK(tracker);
1085  DCHECK(tracker->active());
1086  DCHECK_EQ(TRACKER_KIND_REGULAR, tracker->tracker_kind());
1087  trackers_by_file_id_[tracker->file_id()].Inactivate(tracker);
1088
1089  std::string title = GetTrackerTitle(*tracker);
1090  int64 parent_tracker_id = tracker->parent_tracker_id();
1091  if (parent_tracker_id)
1092    trackers_by_parent_and_title_[parent_tracker_id][title].Inactivate(tracker);
1093  tracker->set_active(false);
1094
1095  RemoveAllDescendantTrackers(tracker_id, batch);
1096  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
1097  if (parent_tracker_id)
1098    MarkTrackersDirtyByPath(parent_tracker_id, title, batch);
1099  PutTrackerToBatch(*tracker, batch);
1100}
1101
1102void MetadataDatabase::MakeAppRootDisabled(int64 tracker_id,
1103                                           leveldb::WriteBatch* batch) {
1104  FileTracker* tracker = tracker_by_id_[tracker_id];
1105  DCHECK(tracker);
1106  DCHECK_EQ(TRACKER_KIND_APP_ROOT, tracker->tracker_kind());
1107  DCHECK(tracker->active());
1108
1109  // Keep the app-root tracker active (but change the tracker_kind) so that
1110  // other conflicting trackers won't become active.
1111  tracker->set_tracker_kind(TRACKER_KIND_DISABLED_APP_ROOT);
1112  PutTrackerToBatch(*tracker, batch);
1113}
1114
1115void MetadataDatabase::MakeAppRootEnabled(int64 tracker_id,
1116                                          leveldb::WriteBatch* batch) {
1117  FileTracker* tracker = tracker_by_id_[tracker_id];
1118  DCHECK(tracker);
1119  DCHECK_EQ(TRACKER_KIND_DISABLED_APP_ROOT, tracker->tracker_kind());
1120  DCHECK(tracker->active());
1121
1122  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
1123  // Mark descendant trackers as dirty to handle changes in disable period.
1124  RecursiveMarkTrackerAsDirty(tracker_id, batch);
1125  PutTrackerToBatch(*tracker, batch);
1126}
1127
1128void MetadataDatabase::CreateTrackerForParentAndFileID(
1129    const FileTracker& parent_tracker,
1130    const std::string& file_id,
1131    leveldb::WriteBatch* batch) {
1132  int64 tracker_id = GetNextTrackerID(batch);
1133  scoped_ptr<FileTracker> tracker(new FileTracker);
1134  tracker->set_tracker_id(tracker_id);
1135  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
1136  tracker->set_file_id(file_id);
1137  tracker->set_app_id(parent_tracker.app_id());
1138  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1139  tracker->set_dirty(true);
1140  tracker->set_active(false);
1141  tracker->set_needs_folder_listing(false);
1142  PutTrackerToBatch(*tracker, batch);
1143
1144  trackers_by_file_id_[file_id].Insert(tracker.get());
1145  // Note: |trackers_by_parent_and_title_| does not map from
1146  // FileMetadata::details but from FileTracker::synced_details, which is filled
1147  // on tracker updated phase.  Use empty string as the title since
1148  // FileTracker::synced_details is empty here.
1149  trackers_by_parent_and_title_[parent_tracker.tracker_id()][std::string()]
1150      .Insert(tracker.get());
1151  dirty_trackers_.insert(tracker.get());
1152  DCHECK(!ContainsKey(tracker_by_id_, tracker_id));
1153  tracker_by_id_[tracker_id] = tracker.release();
1154}
1155
1156void MetadataDatabase::RemoveTracker(int64 tracker_id,
1157                                     leveldb::WriteBatch* batch) {
1158  RemoveTrackerInternal(tracker_id, batch, false);
1159}
1160
1161void MetadataDatabase::RemoveTrackerIgnoringSiblings(
1162    int64 tracker_id,
1163    leveldb::WriteBatch* batch) {
1164  RemoveTrackerInternal(tracker_id, batch, true);
1165}
1166
1167void MetadataDatabase::RemoveTrackerInternal(
1168    int64 tracker_id,
1169    leveldb::WriteBatch* batch,
1170    bool ignoring_siblings) {
1171  scoped_ptr<FileTracker> tracker(
1172      FindAndEraseItem(&tracker_by_id_, tracker_id));
1173  if (!tracker)
1174    return;
1175
1176  EraseTrackerFromFileIDIndex(tracker.get(), batch);
1177  if (IsAppRoot(*tracker))
1178    app_root_by_app_id_.erase(tracker->app_id());
1179  EraseTrackerFromPathIndex(tracker.get());
1180
1181  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
1182  if (!ignoring_siblings) {
1183    MarkTrackersDirtyByPath(tracker->parent_tracker_id(),
1184                            GetTrackerTitle(*tracker),
1185                            batch);
1186  }
1187  PutTrackerDeletionToBatch(tracker_id, batch);
1188}
1189
1190void MetadataDatabase::MaybeAddTrackersForNewFile(
1191    const FileMetadata& file,
1192    leveldb::WriteBatch* batch) {
1193  std::set<int64> known_parents;
1194  TrackersByFileID::iterator found = trackers_by_file_id_.find(file.file_id());
1195  if (found != trackers_by_file_id_.end()) {
1196    for (TrackerSet::const_iterator itr = found->second.begin();
1197         itr != found->second.end(); ++itr) {
1198      int64 parent_tracker_id = (*itr)->parent_tracker_id();
1199      if (parent_tracker_id)
1200        known_parents.insert(parent_tracker_id);
1201    }
1202  }
1203
1204  for (int i = 0; i < file.details().parent_folder_ids_size(); ++i) {
1205    std::string parent_folder_id = file.details().parent_folder_ids(i);
1206    TrackersByFileID::iterator found =
1207        trackers_by_file_id_.find(parent_folder_id);
1208    if (found == trackers_by_file_id_.end())
1209      continue;
1210
1211    for (TrackerSet::const_iterator itr = found->second.begin();
1212         itr != found->second.end(); ++itr) {
1213      FileTracker* parent_tracker = *itr;
1214      int64 parent_tracker_id = parent_tracker->tracker_id();
1215      if (!parent_tracker->active())
1216        continue;
1217
1218      if (ContainsKey(known_parents, parent_tracker_id))
1219        continue;
1220
1221      CreateTrackerForParentAndFileID(*parent_tracker, file.file_id(), batch);
1222    }
1223  }
1224}
1225
1226void MetadataDatabase::RemoveAllDescendantTrackers(int64 root_tracker_id,
1227                                                   leveldb::WriteBatch* batch) {
1228  std::vector<int64> pending_trackers;
1229  PushChildTrackersToContainer(trackers_by_parent_and_title_,
1230                               root_tracker_id,
1231                               std::back_inserter(pending_trackers));
1232
1233  while (!pending_trackers.empty()) {
1234    int64 tracker_id = pending_trackers.back();
1235    pending_trackers.pop_back();
1236    PushChildTrackersToContainer(trackers_by_parent_and_title_,
1237                                 tracker_id,
1238                                 std::back_inserter(pending_trackers));
1239    RemoveTrackerIgnoringSiblings(tracker_id, batch);
1240  }
1241}
1242
1243void MetadataDatabase::EraseTrackerFromFileIDIndex(FileTracker* tracker,
1244                                                   leveldb::WriteBatch* batch) {
1245  TrackersByFileID::iterator found =
1246      trackers_by_file_id_.find(tracker->file_id());
1247  if (found == trackers_by_file_id_.end())
1248    return;
1249
1250  TrackerSet* trackers = &found->second;
1251  trackers->Erase(tracker);
1252  if (!trackers->tracker_set().empty())
1253    return;
1254  trackers_by_file_id_.erase(found);
1255  EraseFileFromDatabase(tracker->file_id(), batch);
1256}
1257
1258void MetadataDatabase::EraseFileFromDatabase(const std::string& file_id,
1259                                             leveldb::WriteBatch* batch) {
1260  scoped_ptr<FileMetadata> file(FindAndEraseItem(&file_by_id_, file_id));
1261  if (file)
1262    PutFileDeletionToBatch(file_id, batch);
1263}
1264
1265void MetadataDatabase::EraseTrackerFromPathIndex(FileTracker* tracker) {
1266  TrackersByParentAndTitle::iterator found =
1267      trackers_by_parent_and_title_.find(tracker->parent_tracker_id());
1268  if (found == trackers_by_parent_and_title_.end())
1269    return;
1270
1271  std::string title = GetTrackerTitle(*tracker);
1272  TrackersByTitle* trackers_by_title = &found->second;
1273  TrackersByTitle::iterator found_by_title = trackers_by_title->find(title);
1274  TrackerSet* conflicting_trackers = &found_by_title->second;
1275  conflicting_trackers->Erase(tracker);
1276
1277  if (conflicting_trackers->tracker_set().empty()) {
1278    trackers_by_title->erase(found_by_title);
1279    if (trackers_by_title->empty())
1280      trackers_by_parent_and_title_.erase(found);
1281  }
1282}
1283
1284void MetadataDatabase::MarkTrackerSetDirty(
1285    TrackerSet* trackers,
1286    leveldb::WriteBatch* batch) {
1287  for (TrackerSet::iterator itr = trackers->begin();
1288       itr != trackers->end(); ++itr) {
1289    FileTracker* tracker = *itr;
1290    if (tracker->dirty())
1291      continue;
1292    tracker->set_dirty(true);
1293    PutTrackerToBatch(*tracker, batch);
1294    dirty_trackers_.insert(tracker);
1295  }
1296}
1297
1298void MetadataDatabase::MarkTrackersDirtyByFileID(
1299    const std::string& file_id,
1300    leveldb::WriteBatch* batch) {
1301  TrackersByFileID::iterator found = trackers_by_file_id_.find(file_id);
1302  if (found != trackers_by_file_id_.end())
1303    MarkTrackerSetDirty(&found->second, batch);
1304}
1305
1306void MetadataDatabase::MarkTrackersDirtyByPath(int64 parent_tracker_id,
1307                                               const std::string& title,
1308                                               leveldb::WriteBatch* batch) {
1309  TrackersByParentAndTitle::iterator found =
1310      trackers_by_parent_and_title_.find(parent_tracker_id);
1311  if (found == trackers_by_parent_and_title_.end()) {
1312    NOTREACHED() << "parent: " << parent_tracker_id
1313                 << ", title: " << title;
1314    return;
1315  }
1316
1317  TrackersByTitle::iterator itr = found->second.find(title);
1318  if (itr != found->second.end())
1319    MarkTrackerSetDirty(&itr->second, batch);
1320}
1321
1322int64 MetadataDatabase::GetNextTrackerID(leveldb::WriteBatch* batch) {
1323  int64 tracker_id = service_metadata_->next_tracker_id();
1324  service_metadata_->set_next_tracker_id(tracker_id + 1);
1325  PutServiceMetadataToBatch(*service_metadata_, batch);
1326  DCHECK_GT(tracker_id, 0);
1327  return tracker_id;
1328}
1329
1330void MetadataDatabase::RecursiveMarkTrackerAsDirty(int64 root_tracker_id,
1331                                                   leveldb::WriteBatch* batch) {
1332  std::vector<int64> stack;
1333  stack.push_back(root_tracker_id);
1334  while (!stack.empty()) {
1335    int64 tracker_id = stack.back();
1336    stack.pop_back();
1337    PushChildTrackersToContainer(
1338        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
1339
1340    FileTracker* tracker = tracker_by_id_[tracker_id];
1341    if (!tracker->dirty()) {
1342      tracker->set_dirty(true);
1343      PutTrackerToBatch(*tracker, batch);
1344      dirty_trackers_.insert(tracker);
1345    }
1346  }
1347}
1348
1349bool MetadataDatabase::CanActivateTracker(const FileTracker& tracker) {
1350  DCHECK(!tracker.active());
1351  DCHECK_NE(service_metadata_->sync_root_tracker_id(), tracker.tracker_id());
1352
1353  if (HasActiveTrackerForFileID(tracker.file_id()))
1354    return false;
1355
1356  if (tracker.app_id().empty())
1357    return false;
1358  if (!tracker.has_synced_details())
1359    return false;
1360  DCHECK(tracker.parent_tracker_id());
1361
1362  return !HasActiveTrackerForPath(tracker.parent_tracker_id(),
1363                                  tracker.synced_details().title());
1364}
1365
1366bool MetadataDatabase::ShouldKeepDirty(const FileTracker& tracker) const {
1367  if (HasDisabledAppRoot(tracker))
1368    return false;
1369
1370  DCHECK(tracker.dirty());
1371  if (!tracker.has_synced_details())
1372    return true;
1373
1374  FileByID::const_iterator found = file_by_id_.find(tracker.file_id());
1375  if (found == file_by_id_.end())
1376    return true;
1377  const FileMetadata* file = found->second;
1378  DCHECK(file);
1379
1380  if (tracker.active()) {
1381    if (tracker.needs_folder_listing())
1382      return true;
1383    if (tracker.synced_details().md5() != file->details().md5())
1384      return true;
1385  }
1386
1387  const FileDetails& local_details = tracker.synced_details();
1388  const FileDetails& remote_details = file->details();
1389
1390  if (local_details.title() != remote_details.title())
1391    return true;
1392  if (local_details.deleted() != remote_details.deleted())
1393    return true;
1394
1395  return false;
1396}
1397
1398bool MetadataDatabase::HasDisabledAppRoot(const FileTracker& tracker) const {
1399  TrackerByAppID::const_iterator found =
1400      app_root_by_app_id_.find(tracker.app_id());
1401  if (found == app_root_by_app_id_.end())
1402    return false;
1403
1404  const FileTracker* app_root_tracker = found->second;
1405  DCHECK(app_root_tracker);
1406  return app_root_tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
1407}
1408
1409bool MetadataDatabase::HasActiveTrackerForFileID(
1410    const std::string& file_id) const {
1411  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
1412  return found != trackers_by_file_id_.end() && found->second.has_active();
1413}
1414
1415bool MetadataDatabase::HasActiveTrackerForPath(int64 parent_tracker_id,
1416                                               const std::string& title) const {
1417  TrackersByParentAndTitle::const_iterator found_by_parent =
1418      trackers_by_parent_and_title_.find(parent_tracker_id);
1419  if (found_by_parent == trackers_by_parent_and_title_.end())
1420    return false;
1421
1422  const TrackersByTitle& trackers_by_title = found_by_parent->second;
1423  TrackersByTitle::const_iterator found = trackers_by_title.find(title);
1424  return found != trackers_by_title.end() && found->second.has_active();
1425}
1426
1427void MetadataDatabase::UpdateTrackerTitle(FileTracker* tracker,
1428                                          const std::string& new_title,
1429                                          leveldb::WriteBatch* batch) {
1430  int64 parent_id = tracker->parent_tracker_id();
1431  std::string old_title = GetTrackerTitle(*tracker);
1432  DCHECK_NE(old_title, new_title);
1433  DCHECK(!new_title.empty());
1434
1435  TrackersByTitle* trackers_by_title =
1436      &trackers_by_parent_and_title_[parent_id];
1437  TrackerSet* old_siblings = &(*trackers_by_title)[old_title];
1438  TrackerSet* new_siblings = &(*trackers_by_title)[new_title];
1439
1440  old_siblings->Erase(tracker);
1441  if (old_siblings->empty())
1442    trackers_by_title->erase(old_title);
1443  else
1444    MarkTrackerSetDirty(old_siblings, batch);
1445
1446  if (tracker->active() && new_siblings->has_active()) {
1447    // Inactivate existing active tracker.
1448    FileTracker* obstacle = new_siblings->active_tracker();
1449    new_siblings->Inactivate(obstacle);
1450    DCHECK_EQ(TRACKER_KIND_REGULAR, obstacle->tracker_kind());
1451
1452    TrackerSet* same_file_id_trackers_to_obstacle =
1453        &trackers_by_file_id_[obstacle->file_id()];
1454    same_file_id_trackers_to_obstacle->Inactivate(obstacle);
1455    MarkTrackerSetDirty(same_file_id_trackers_to_obstacle, batch);
1456
1457    obstacle->set_active(false);
1458    PutTrackerToBatch(*obstacle, batch);
1459
1460    RemoveAllDescendantTrackers(obstacle->tracker_id(), batch);
1461  }
1462
1463  tracker->mutable_synced_details()->set_title(new_title);
1464  new_siblings->Insert(tracker);
1465  PutTrackerToBatch(*tracker, batch);
1466}
1467
1468void MetadataDatabase::WriteToDatabase(scoped_ptr<leveldb::WriteBatch> batch,
1469                                       const SyncStatusCallback& callback) {
1470  base::PostTaskAndReplyWithResult(
1471      task_runner_.get(),
1472      FROM_HERE,
1473      base::Bind(&leveldb::DB::Write,
1474                 base::Unretained(db_.get()),
1475                 leveldb::WriteOptions(),
1476                 base::Owned(batch.release())),
1477      base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
1478}
1479
1480}  // namespace drive_backend
1481}  // namespace sync_file_system
1482