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/file_util.h"
13#include "base/files/file_path.h"
14#include "base/location.h"
15#include "base/memory/scoped_vector.h"
16#include "base/message_loop/message_loop_proxy.h"
17#include "base/sequenced_task_runner.h"
18#include "base/stl_util.h"
19#include "base/strings/string_number_conversions.h"
20#include "base/strings/string_util.h"
21#include "base/strings/stringprintf.h"
22#include "base/task_runner_util.h"
23#include "base/threading/thread_restrictions.h"
24#include "chrome/browser/drive/drive_api_util.h"
25#include "chrome/browser/sync_file_system/drive_backend/drive_backend_constants.h"
26#include "chrome/browser/sync_file_system/drive_backend/drive_backend_util.h"
27#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
28#include "chrome/browser/sync_file_system/drive_backend/metadata_db_migration_util.h"
29#include "chrome/browser/sync_file_system/logger.h"
30#include "chrome/browser/sync_file_system/syncable_file_system_util.h"
31#include "google_apis/drive/drive_api_parser.h"
32#include "google_apis/drive/drive_entry_kinds.h"
33#include "third_party/leveldatabase/src/include/leveldb/db.h"
34#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
35#include "webkit/common/fileapi/file_system_util.h"
36
37namespace sync_file_system {
38namespace drive_backend {
39
40struct DatabaseContents {
41  scoped_ptr<ServiceMetadata> service_metadata;
42  ScopedVector<FileMetadata> file_metadata;
43  ScopedVector<FileTracker> file_trackers;
44};
45
46namespace {
47
48typedef MetadataDatabase::FileByID FileByID;
49typedef MetadataDatabase::TrackerByID TrackerByID;
50typedef MetadataDatabase::TrackersByParentAndTitle TrackersByParentAndTitle;
51typedef MetadataDatabase::TrackersByTitle TrackersByTitle;
52
53bool IsAppRoot(const FileTracker& tracker) {
54  return tracker.tracker_kind() == TRACKER_KIND_APP_ROOT ||
55      tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
56}
57
58std::string RemovePrefix(const std::string& str, const std::string& prefix) {
59  if (StartsWithASCII(str, prefix, true))
60    return str.substr(prefix.size());
61  return str;
62}
63
64base::FilePath ReverseConcatPathComponents(
65    const std::vector<base::FilePath>& components) {
66  if (components.empty())
67    return base::FilePath(FILE_PATH_LITERAL("/")).NormalizePathSeparators();
68
69  size_t total_size = 0;
70  typedef std::vector<base::FilePath> PathComponents;
71  for (PathComponents::const_iterator itr = components.begin();
72       itr != components.end(); ++itr)
73    total_size += itr->value().size() + 1;
74
75  base::FilePath::StringType result;
76  result.reserve(total_size);
77  for (PathComponents::const_reverse_iterator itr = components.rbegin();
78       itr != components.rend(); ++itr) {
79    result.append(1, base::FilePath::kSeparators[0]);
80    result.append(itr->value());
81  }
82
83  return base::FilePath(result).NormalizePathSeparators();
84}
85
86void CreateInitialSyncRootTracker(
87    int64 tracker_id,
88    const google_apis::FileResource& file_resource,
89    scoped_ptr<FileMetadata>* file_out,
90    scoped_ptr<FileTracker>* tracker_out) {
91  FileDetails details;
92  PopulateFileDetailsByFileResource(file_resource, &details);
93
94  scoped_ptr<FileMetadata> file(new FileMetadata);
95  file->set_file_id(file_resource.file_id());
96  *file->mutable_details() = details;
97
98  scoped_ptr<FileTracker> tracker(new FileTracker);
99  tracker->set_tracker_id(tracker_id);
100  tracker->set_file_id(file_resource.file_id());
101  tracker->set_parent_tracker_id(0);
102  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
103  tracker->set_dirty(false);
104  tracker->set_active(true);
105  tracker->set_needs_folder_listing(false);
106  *tracker->mutable_synced_details() = details;
107
108  *file_out = file.Pass();
109  *tracker_out = tracker.Pass();
110}
111
112void CreateInitialAppRootTracker(
113    int64 tracker_id,
114    const FileTracker& parent_tracker,
115    const google_apis::FileResource& file_resource,
116    scoped_ptr<FileMetadata>* file_out,
117    scoped_ptr<FileTracker>* tracker_out) {
118  FileDetails details;
119  PopulateFileDetailsByFileResource(file_resource, &details);
120
121  scoped_ptr<FileMetadata> file(new FileMetadata);
122  file->set_file_id(file_resource.file_id());
123  *file->mutable_details() = details;
124
125  scoped_ptr<FileTracker> tracker(new FileTracker);
126  tracker->set_tracker_id(tracker_id);
127  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
128  tracker->set_file_id(file_resource.file_id());
129  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
130  tracker->set_dirty(false);
131  tracker->set_active(false);
132  tracker->set_needs_folder_listing(false);
133  *tracker->mutable_synced_details() = details;
134
135  *file_out = file.Pass();
136  *tracker_out = tracker.Pass();
137}
138
139void AdaptLevelDBStatusToSyncStatusCode(const SyncStatusCallback& callback,
140                                        const leveldb::Status& status) {
141  callback.Run(LevelDBStatusToSyncStatusCode(status));
142}
143
144void PutFileDeletionToBatch(const std::string& file_id,
145                            leveldb::WriteBatch* batch) {
146  batch->Delete(kFileMetadataKeyPrefix + file_id);
147}
148
149void PutTrackerDeletionToBatch(int64 tracker_id, leveldb::WriteBatch* batch) {
150  batch->Delete(kFileTrackerKeyPrefix + base::Int64ToString(tracker_id));
151}
152
153template <typename OutputIterator>
154OutputIterator PushChildTrackersToContainer(
155    const TrackersByParentAndTitle& trackers_by_parent,
156    int64 parent_tracker_id,
157    OutputIterator target_itr) {
158  TrackersByParentAndTitle::const_iterator found =
159      trackers_by_parent.find(parent_tracker_id);
160  if (found == trackers_by_parent.end())
161    return target_itr;
162
163  for (TrackersByTitle::const_iterator title_itr = found->second.begin();
164       title_itr != found->second.end(); ++title_itr) {
165    const TrackerSet& trackers = title_itr->second;
166    for (TrackerSet::const_iterator tracker_itr = trackers.begin();
167         tracker_itr != trackers.end(); ++tracker_itr) {
168      *target_itr = (*tracker_itr)->tracker_id();
169      ++target_itr;
170    }
171  }
172  return target_itr;
173}
174
175std::string GetTrackerTitle(const FileTracker& tracker) {
176  if (tracker.has_synced_details())
177    return tracker.synced_details().title();
178  return std::string();
179}
180
181// Returns true if |db| has no content.
182bool IsDatabaseEmpty(leveldb::DB* db) {
183  DCHECK(db);
184  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
185  itr->SeekToFirst();
186  return !itr->Valid();
187}
188
189SyncStatusCode OpenDatabase(const base::FilePath& path,
190                            scoped_ptr<leveldb::DB>* db_out,
191                            bool* created) {
192  base::ThreadRestrictions::AssertIOAllowed();
193  DCHECK(db_out);
194  DCHECK(created);
195
196  leveldb::Options options;
197  options.max_open_files = 0;  // Use minimum.
198  options.create_if_missing = true;
199  leveldb::DB* db = NULL;
200  leveldb::Status db_status =
201      leveldb::DB::Open(options, path.AsUTF8Unsafe(), &db);
202  SyncStatusCode status = LevelDBStatusToSyncStatusCode(db_status);
203  if (status != SYNC_STATUS_OK) {
204    delete db;
205    return status;
206  }
207
208  *created = IsDatabaseEmpty(db);
209  db_out->reset(db);
210  return status;
211}
212
213SyncStatusCode MigrateDatabaseIfNeeded(leveldb::DB* db) {
214  base::ThreadRestrictions::AssertIOAllowed();
215  DCHECK(db);
216  std::string value;
217  leveldb::Status status =
218      db->Get(leveldb::ReadOptions(), kDatabaseVersionKey, &value);
219  int64 version = 0;
220  if (status.ok()) {
221    if (!base::StringToInt64(value, &version))
222      return SYNC_DATABASE_ERROR_FAILED;
223  } else {
224    if (!status.IsNotFound())
225      return SYNC_DATABASE_ERROR_FAILED;
226  }
227
228  switch (version) {
229    case 0:
230      drive_backend::MigrateDatabaseFromV0ToV1(db);
231      // fall-through
232    case 1:
233      drive_backend::MigrateDatabaseFromV1ToV2(db);
234      // fall-through
235    case 2:
236      // TODO(tzik): Migrate database from version 2 to 3.
237      //   * Add sync-root folder as active, dirty and needs_folder_listing
238      //     folder.
239      //   * Add app-root folders for each origins.  Each app-root folder for
240      //     an enabled origin should be a active, dirty and
241      //     needs_folder_listing folder.  And Each app-root folder for a
242      //     disabled origin should be an inactive, dirty and
243      //     non-needs_folder_listing folder.
244      //   * Add a file metadata for each file in previous version.
245      NOTIMPLEMENTED();
246      return SYNC_DATABASE_ERROR_FAILED;
247      // fall-through
248    case 3:
249      DCHECK_EQ(3, kCurrentDatabaseVersion);
250      return SYNC_STATUS_OK;
251    default:
252      return SYNC_DATABASE_ERROR_FAILED;
253  }
254}
255
256SyncStatusCode WriteVersionInfo(leveldb::DB* db) {
257  base::ThreadRestrictions::AssertIOAllowed();
258  DCHECK(db);
259  return LevelDBStatusToSyncStatusCode(
260      db->Put(leveldb::WriteOptions(),
261              kDatabaseVersionKey,
262              base::Int64ToString(kCurrentDatabaseVersion)));
263}
264
265SyncStatusCode ReadDatabaseContents(leveldb::DB* db,
266                                    DatabaseContents* contents) {
267  base::ThreadRestrictions::AssertIOAllowed();
268  DCHECK(db);
269  DCHECK(contents);
270
271  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
272  for (itr->SeekToFirst(); itr->Valid(); itr->Next()) {
273    std::string key = itr->key().ToString();
274    std::string value = itr->value().ToString();
275    if (key == kServiceMetadataKey) {
276      scoped_ptr<ServiceMetadata> service_metadata(new ServiceMetadata);
277      if (!service_metadata->ParseFromString(value)) {
278        util::Log(logging::LOG_WARNING, FROM_HERE,
279                  "Failed to parse SyncServiceMetadata");
280        continue;
281      }
282
283      contents->service_metadata = service_metadata.Pass();
284      continue;
285    }
286
287    if (StartsWithASCII(key, kFileMetadataKeyPrefix, true)) {
288      std::string file_id = RemovePrefix(key, kFileMetadataKeyPrefix);
289
290      scoped_ptr<FileMetadata> file(new FileMetadata);
291      if (!file->ParseFromString(itr->value().ToString())) {
292        util::Log(logging::LOG_WARNING, FROM_HERE,
293                  "Failed to parse a FileMetadata");
294        continue;
295      }
296
297      contents->file_metadata.push_back(file.release());
298      continue;
299    }
300
301    if (StartsWithASCII(key, kFileTrackerKeyPrefix, true)) {
302      int64 tracker_id = 0;
303      if (!base::StringToInt64(RemovePrefix(key, kFileTrackerKeyPrefix),
304                               &tracker_id)) {
305        util::Log(logging::LOG_WARNING, FROM_HERE,
306                  "Failed to parse TrackerID");
307        continue;
308      }
309
310      scoped_ptr<FileTracker> tracker(new FileTracker);
311      if (!tracker->ParseFromString(itr->value().ToString())) {
312        util::Log(logging::LOG_WARNING, FROM_HERE,
313                  "Failed to parse a Tracker");
314        continue;
315      }
316      contents->file_trackers.push_back(tracker.release());
317      continue;
318    }
319  }
320
321  return SYNC_STATUS_OK;
322}
323
324SyncStatusCode InitializeServiceMetadata(DatabaseContents* contents,
325                                         leveldb::WriteBatch* batch) {
326  if (!contents->service_metadata) {
327    contents->service_metadata.reset(new ServiceMetadata);
328    contents->service_metadata->set_next_tracker_id(1);
329
330    std::string value;
331    contents->service_metadata->SerializeToString(&value);
332    batch->Put(kServiceMetadataKey, value);
333  }
334  return SYNC_STATUS_OK;
335}
336
337SyncStatusCode RemoveUnreachableItems(DatabaseContents* contents,
338                                      leveldb::WriteBatch* batch) {
339  TrackerByID unvisited_trackers;
340  typedef std::map<int64, std::set<FileTracker*> > TrackersByParent;
341  TrackersByParent trackers_by_parent;
342
343  for (ScopedVector<FileTracker>::iterator itr =
344           contents->file_trackers.begin();
345       itr != contents->file_trackers.end();
346       ++itr) {
347    FileTracker* tracker = *itr;
348    DCHECK(!ContainsKey(unvisited_trackers, tracker->tracker_id()));
349    unvisited_trackers[tracker->tracker_id()] = tracker;
350    if (tracker->parent_tracker_id())
351      trackers_by_parent[tracker->parent_tracker_id()].insert(tracker);
352  }
353
354  // Traverse synced tracker tree. Take only active items, app-root and their
355  // children. Drop unreachable items.
356  ScopedVector<FileTracker> reachable_trackers;
357  std::stack<int64> pending;
358  if (contents->service_metadata->sync_root_tracker_id())
359    pending.push(contents->service_metadata->sync_root_tracker_id());
360
361  while (!pending.empty()) {
362    int64 tracker_id = pending.top();
363    pending.pop();
364
365    {
366      TrackerByID::iterator found = unvisited_trackers.find(tracker_id);
367      if (found == unvisited_trackers.end())
368        continue;
369
370      FileTracker* tracker = found->second;
371      unvisited_trackers.erase(found);
372      reachable_trackers.push_back(tracker);
373
374      if (!tracker->active())
375        continue;
376    }
377
378    TrackersByParent::iterator found = trackers_by_parent.find(tracker_id);
379    if (found == trackers_by_parent.end())
380      continue;
381
382    for (std::set<FileTracker*>::const_iterator itr =
383             found->second.begin();
384         itr != found->second.end();
385         ++itr)
386      pending.push((*itr)->tracker_id());
387  }
388
389  // Delete all unreachable trackers.
390  for (TrackerByID::iterator itr = unvisited_trackers.begin();
391       itr != unvisited_trackers.end(); ++itr) {
392    FileTracker* tracker = itr->second;
393    PutTrackerDeletionToBatch(tracker->tracker_id(), batch);
394    delete tracker;
395  }
396  unvisited_trackers.clear();
397
398  // |reachable_trackers| contains all files/folders reachable from sync-root
399  // folder via active folders and app-root folders.
400  // Update the tracker set in database contents with the reachable tracker set.
401  contents->file_trackers.weak_clear();
402  contents->file_trackers.swap(reachable_trackers);
403
404  // Do the similar traverse for FileMetadata and remove FileMetadata that don't
405  // have reachable trackers.
406  FileByID unreferred_files;
407  for (ScopedVector<FileMetadata>::const_iterator itr =
408           contents->file_metadata.begin();
409       itr != contents->file_metadata.end();
410       ++itr) {
411    unreferred_files.insert(std::make_pair((*itr)->file_id(), *itr));
412  }
413
414  ScopedVector<FileMetadata> referred_files;
415  for (ScopedVector<FileTracker>::const_iterator itr =
416           contents->file_trackers.begin();
417       itr != contents->file_trackers.end();
418       ++itr) {
419    FileByID::iterator found = unreferred_files.find((*itr)->file_id());
420    if (found != unreferred_files.end()) {
421      referred_files.push_back(found->second);
422      unreferred_files.erase(found);
423    }
424  }
425
426  for (FileByID::iterator itr = unreferred_files.begin();
427       itr != unreferred_files.end(); ++itr) {
428    FileMetadata* file = itr->second;
429    PutFileDeletionToBatch(file->file_id(), batch);
430    delete file;
431  }
432  unreferred_files.clear();
433
434  contents->file_metadata.weak_clear();
435  contents->file_metadata.swap(referred_files);
436
437  return SYNC_STATUS_OK;
438}
439
440template <typename Container, typename Key, typename Value>
441bool FindItem(const Container& container, const Key& key, Value* value) {
442  typename Container::const_iterator found = container.find(key);
443  if (found == container.end())
444    return false;
445  if (value)
446    *value = *found->second;
447  return true;
448}
449
450template <typename Container, typename Key>
451typename Container::mapped_type FindAndEraseItem(Container* container,
452                                                 const Key& key) {
453  typedef typename Container::mapped_type Value;
454  typename Container::iterator found = container->find(key);
455  if (found == container->end())
456    return Value();
457
458  Value result = found->second;
459  container->erase(found);
460  return result;
461}
462
463void RunSoon(const tracked_objects::Location& from_here,
464             const base::Closure& closure) {
465  base::MessageLoopProxy::current()->PostTask(from_here, closure);
466}
467
468bool HasInvalidTitle(const std::string& title) {
469  return title.find('/') != std::string::npos ||
470      title.find('\\') != std::string::npos;
471}
472
473}  // namespace
474
475bool MetadataDatabase::DirtyTrackerComparator::operator()(
476    const FileTracker* left,
477    const FileTracker* right) const {
478  return left->tracker_id() < right->tracker_id();
479}
480
481// static
482void MetadataDatabase::Create(base::SequencedTaskRunner* task_runner,
483                              const base::FilePath& database_path,
484                              const CreateCallback& callback) {
485  task_runner->PostTask(FROM_HERE, base::Bind(
486      &CreateOnTaskRunner,
487      base::MessageLoopProxy::current(),
488      make_scoped_refptr(task_runner),
489      database_path, callback));
490}
491
492MetadataDatabase::~MetadataDatabase() {
493  task_runner_->DeleteSoon(FROM_HERE, db_.release());
494  STLDeleteContainerPairSecondPointers(
495      file_by_id_.begin(), file_by_id_.end());
496  STLDeleteContainerPairSecondPointers(
497      tracker_by_id_.begin(), tracker_by_id_.end());
498}
499
500// static
501void MetadataDatabase::ClearDatabase(
502    scoped_ptr<MetadataDatabase> metadata_database) {
503  DCHECK(metadata_database);
504  scoped_refptr<base::SequencedTaskRunner> task_runner =
505      metadata_database->task_runner_;
506  base::FilePath database_path = metadata_database->database_path_;
507  DCHECK(!database_path.empty());
508  metadata_database.reset();
509
510  task_runner->PostTask(
511      FROM_HERE,
512      base::Bind(base::IgnoreResult(base::DeleteFile),
513                 database_path, true /* recursive */));
514}
515
516int64 MetadataDatabase::GetLargestFetchedChangeID() const {
517  return service_metadata_->largest_change_id();
518}
519
520int64 MetadataDatabase::GetSyncRootTrackerID() const {
521  return service_metadata_->sync_root_tracker_id();
522}
523
524int64 MetadataDatabase::GetLargestKnownChangeID() const {
525  DCHECK_LE(GetLargestFetchedChangeID(), largest_known_change_id_);
526  return largest_known_change_id_;
527}
528
529void MetadataDatabase::UpdateLargestKnownChangeID(int64 change_id) {
530  if (largest_known_change_id_ < change_id)
531    largest_known_change_id_ = change_id;
532}
533
534bool MetadataDatabase::HasSyncRoot() const {
535  return service_metadata_->has_sync_root_tracker_id() &&
536      !!service_metadata_->sync_root_tracker_id();
537}
538
539void MetadataDatabase::PopulateInitialData(
540    int64 largest_change_id,
541    const google_apis::FileResource& sync_root_folder,
542    const ScopedVector<google_apis::FileResource>& app_root_folders,
543    const SyncStatusCallback& callback) {
544  DCHECK(tracker_by_id_.empty());
545  DCHECK(file_by_id_.empty());
546
547  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
548  service_metadata_->set_largest_change_id(largest_change_id);
549  UpdateLargestKnownChangeID(largest_change_id);
550
551  FileTracker* sync_root_tracker = NULL;
552  int64 sync_root_tracker_id = 0;
553  {
554    scoped_ptr<FileMetadata> folder;
555    scoped_ptr<FileTracker> tracker;
556    CreateInitialSyncRootTracker(GetNextTrackerID(batch.get()),
557                                 sync_root_folder,
558                                 &folder,
559                                 &tracker);
560    std::string sync_root_folder_id = folder->file_id();
561    sync_root_tracker = tracker.get();
562    sync_root_tracker_id = tracker->tracker_id();
563
564    PutFileToBatch(*folder, batch.get());
565    PutTrackerToBatch(*tracker, batch.get());
566
567    service_metadata_->set_sync_root_tracker_id(tracker->tracker_id());
568    PutServiceMetadataToBatch(*service_metadata_, batch.get());
569
570    trackers_by_file_id_[folder->file_id()].Insert(tracker.get());
571
572    file_by_id_[sync_root_folder_id] = folder.release();
573    tracker_by_id_[sync_root_tracker_id] = tracker.release();
574  }
575
576  for (ScopedVector<google_apis::FileResource>::const_iterator itr =
577           app_root_folders.begin();
578       itr != app_root_folders.end();
579       ++itr) {
580    const google_apis::FileResource& folder_resource = **itr;
581    scoped_ptr<FileMetadata> folder;
582    scoped_ptr<FileTracker> tracker;
583    CreateInitialAppRootTracker(GetNextTrackerID(batch.get()),
584                                *sync_root_tracker,
585                                folder_resource,
586                                &folder,
587                                &tracker);
588    std::string title = folder->details().title();
589    std::string folder_id = folder->file_id();
590    int64 tracker_id = tracker->tracker_id();
591
592    PutFileToBatch(*folder, batch.get());
593    PutTrackerToBatch(*tracker, batch.get());
594
595    trackers_by_file_id_[folder_id].Insert(tracker.get());
596    trackers_by_parent_and_title_[sync_root_tracker_id][title]
597        .Insert(tracker.get());
598
599    file_by_id_[folder_id] = folder.release();
600    tracker_by_id_[tracker_id] = tracker.release();
601  }
602
603  WriteToDatabase(batch.Pass(), callback);
604}
605
606bool MetadataDatabase::IsAppEnabled(const std::string& app_id) const {
607  FileTracker tracker;
608  if (!FindAppRootTracker(app_id, &tracker))
609    return false;
610  return tracker.tracker_kind() == TRACKER_KIND_APP_ROOT;
611}
612
613void MetadataDatabase::RegisterApp(const std::string& app_id,
614                                   const std::string& folder_id,
615                                   const SyncStatusCallback& callback) {
616  if (FindAppRootTracker(app_id, NULL)) {
617    // The app-root is already registered.
618    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
619    return;
620  }
621
622  TrackerSet trackers;
623  if (!FindTrackersByFileID(folder_id, &trackers) || trackers.has_active()) {
624    // The folder is tracked by another tracker.
625    util::Log(logging::LOG_WARNING, FROM_HERE,
626              "Failed to register App for %s", app_id.c_str());
627    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_HAS_CONFLICT));
628    return;
629  }
630
631  int64 sync_root_tracker_id = service_metadata_->sync_root_tracker_id();
632  if (!sync_root_tracker_id) {
633    util::Log(logging::LOG_WARNING, FROM_HERE,
634              "Sync-root needs to be set up before registering app-root");
635    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
636    return;
637  }
638
639  // Make this tracker an app-root tracker.
640  FileTracker* app_root_tracker = NULL;
641  for (TrackerSet::iterator itr = trackers.begin();
642       itr != trackers.end(); ++itr) {
643    FileTracker* tracker = *itr;
644    if (tracker->parent_tracker_id() == sync_root_tracker_id)
645      app_root_tracker = tracker;
646  }
647
648  if (!app_root_tracker) {
649    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
650    return;
651  }
652
653  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
654  RegisterTrackerAsAppRoot(app_id, app_root_tracker->tracker_id(), batch.get());
655  WriteToDatabase(batch.Pass(), callback);
656}
657
658void MetadataDatabase::DisableApp(const std::string& app_id,
659                                  const SyncStatusCallback& callback) {
660  FileTracker tracker;
661  if (!FindAppRootTracker(app_id, &tracker)) {
662    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
663    return;
664  }
665
666  if (tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
667    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
668    return;
669  }
670
671  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
672  MakeAppRootDisabled(tracker.tracker_id(), batch.get());
673  WriteToDatabase(batch.Pass(), callback);
674}
675
676void MetadataDatabase::EnableApp(const std::string& app_id,
677                                 const SyncStatusCallback& callback) {
678  FileTracker tracker;
679  if (!FindAppRootTracker(app_id, &tracker) ||
680      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
681    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
682    return;
683  }
684
685  if (tracker.tracker_kind() == TRACKER_KIND_APP_ROOT) {
686    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
687    return;
688  }
689
690  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
691  MakeAppRootEnabled(tracker.tracker_id(), batch.get());
692  WriteToDatabase(batch.Pass(), callback);
693}
694
695void MetadataDatabase::UnregisterApp(const std::string& app_id,
696                                     const SyncStatusCallback& callback) {
697  FileTracker tracker;
698  if (!FindAppRootTracker(app_id, &tracker) ||
699      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
700    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
701    return;
702  }
703
704  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
705  UnregisterTrackerAsAppRoot(app_id, batch.get());
706  WriteToDatabase(batch.Pass(), callback);
707}
708
709bool MetadataDatabase::FindAppRootTracker(const std::string& app_id,
710                                          FileTracker* tracker) const {
711  return FindItem(app_root_by_app_id_, app_id, tracker);
712}
713
714bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
715                                        FileMetadata* file) const {
716  return FindItem(file_by_id_, file_id, file);
717}
718
719bool MetadataDatabase::FindTrackersByFileID(const std::string& file_id,
720                                            TrackerSet* trackers) const {
721  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
722  if (found == trackers_by_file_id_.end())
723    return false;
724  if (trackers)
725    *trackers = found->second;
726  return true;
727}
728
729bool MetadataDatabase::FindTrackersByParentAndTitle(
730    int64 parent_tracker_id,
731    const std::string& title,
732    TrackerSet* trackers) const {
733  TrackersByParentAndTitle::const_iterator found_by_parent =
734      trackers_by_parent_and_title_.find(parent_tracker_id);
735  if (found_by_parent == trackers_by_parent_and_title_.end())
736    return false;
737
738  TrackersByTitle::const_iterator found_by_title =
739      found_by_parent->second.find(title);
740  if (found_by_title == found_by_parent->second.end())
741    return false;
742
743  if (trackers)
744    *trackers = found_by_title->second;
745  return true;
746}
747
748bool MetadataDatabase::FindTrackerByTrackerID(int64 tracker_id,
749                                              FileTracker* tracker) const {
750  return FindItem(tracker_by_id_, tracker_id, tracker);
751}
752
753bool MetadataDatabase::BuildPathForTracker(int64 tracker_id,
754                                           base::FilePath* path) const {
755  FileTracker current;
756  if (!FindTrackerByTrackerID(tracker_id, &current) || !current.active())
757    return false;
758
759  std::vector<base::FilePath> components;
760  while (!IsAppRoot(current)) {
761    std::string title = GetTrackerTitle(current);
762    if (title.empty())
763      return false;
764    components.push_back(base::FilePath::FromUTF8Unsafe(title));
765    if (!FindTrackerByTrackerID(current.parent_tracker_id(), &current) ||
766        !current.active())
767      return false;
768  }
769
770  if (path)
771    *path = ReverseConcatPathComponents(components);
772
773  return true;
774}
775
776base::FilePath MetadataDatabase::BuildDisplayPathForTracker(
777    const FileTracker& tracker) const {
778  base::FilePath path;
779  if (tracker.active()) {
780    BuildPathForTracker(tracker.tracker_id(), &path);
781    return path;
782  }
783  BuildPathForTracker(tracker.parent_tracker_id(), &path);
784  if (tracker.has_synced_details()) {
785    path = path.Append(
786        base::FilePath::FromUTF8Unsafe(tracker.synced_details().title()));
787  } else {
788    path = path.Append(FILE_PATH_LITERAL("<unknown>"));
789  }
790  return path;
791}
792
793bool MetadataDatabase::FindNearestActiveAncestor(
794    const std::string& app_id,
795    const base::FilePath& full_path,
796    FileTracker* tracker,
797    base::FilePath* path) const {
798  DCHECK(tracker);
799  DCHECK(path);
800
801  if (full_path.IsAbsolute() ||
802      !FindAppRootTracker(app_id, tracker) ||
803      tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
804    return false;
805  }
806
807  std::vector<base::FilePath::StringType> components;
808  full_path.GetComponents(&components);
809  path->clear();
810
811  for (size_t i = 0; i < components.size(); ++i) {
812    const std::string title = base::FilePath(components[i]).AsUTF8Unsafe();
813    TrackerSet trackers;
814    if (!FindTrackersByParentAndTitle(
815            tracker->tracker_id(), title, &trackers) ||
816        !trackers.has_active()) {
817      return true;
818    }
819
820    DCHECK(trackers.active_tracker()->has_synced_details());
821    const FileDetails& details = trackers.active_tracker()->synced_details();
822    if (details.file_kind() != FILE_KIND_FOLDER && i != components.size() - 1) {
823      // This non-last component indicates file. Give up search.
824      return true;
825    }
826
827    *tracker = *trackers.active_tracker();
828    *path = path->Append(components[i]);
829  }
830
831  return true;
832}
833
834void MetadataDatabase::UpdateByChangeList(
835    int64 largest_change_id,
836    ScopedVector<google_apis::ChangeResource> changes,
837    const SyncStatusCallback& callback) {
838  DCHECK_LE(service_metadata_->largest_change_id(), largest_change_id);
839
840  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
841
842  for (ScopedVector<google_apis::ChangeResource>::const_iterator itr =
843           changes.begin();
844       itr != changes.end();
845       ++itr) {
846    const google_apis::ChangeResource& change = **itr;
847    if (HasNewerFileMetadata(change.file_id(), change.change_id()))
848      continue;
849
850    scoped_ptr<FileMetadata> file(
851        CreateFileMetadataFromChangeResource(change));
852    UpdateByFileMetadata(FROM_HERE, file.Pass(), batch.get());
853  }
854
855  UpdateLargestKnownChangeID(largest_change_id);
856  service_metadata_->set_largest_change_id(largest_change_id);
857  PutServiceMetadataToBatch(*service_metadata_, batch.get());
858  WriteToDatabase(batch.Pass(), callback);
859}
860
861void MetadataDatabase::UpdateByFileResource(
862    const google_apis::FileResource& resource,
863    const SyncStatusCallback& callback) {
864  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
865
866  scoped_ptr<FileMetadata> file(
867      CreateFileMetadataFromFileResource(
868          GetLargestKnownChangeID(), resource));
869  UpdateByFileMetadata(FROM_HERE, file.Pass(), batch.get());
870  WriteToDatabase(batch.Pass(), callback);
871}
872
873void MetadataDatabase::UpdateByFileResourceList(
874    ScopedVector<google_apis::FileResource> resources,
875    const SyncStatusCallback& callback) {
876  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
877
878  for (size_t i = 0; i < resources.size(); ++i) {
879    scoped_ptr<FileMetadata> file(
880        CreateFileMetadataFromFileResource(
881            GetLargestKnownChangeID(), *resources[i]));
882    UpdateByFileMetadata(FROM_HERE, file.Pass(), batch.get());
883  }
884  WriteToDatabase(batch.Pass(), callback);
885}
886
887void MetadataDatabase::UpdateByDeletedRemoteFile(
888    const std::string& file_id,
889    const SyncStatusCallback& callback) {
890  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
891  scoped_ptr<FileMetadata> file(
892      CreateDeletedFileMetadata(GetLargestKnownChangeID(), file_id));
893  UpdateByFileMetadata(FROM_HERE, file.Pass(), batch.get());
894  WriteToDatabase(batch.Pass(), callback);
895}
896
897void MetadataDatabase::ReplaceActiveTrackerWithNewResource(
898    int64 parent_tracker_id,
899    const google_apis::FileResource& resource,
900    const SyncStatusCallback& callback) {
901  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
902
903  scoped_ptr<FileMetadata> file(
904      CreateFileMetadataFromFileResource(
905          GetLargestKnownChangeID(), resource));
906  std::string file_id = file->file_id();
907  DCHECK(!ContainsKey(file_by_id_, file_id));
908  DCHECK(!file->details().missing());
909
910  // TODO(tzik): Consolidate with UpdateByChangeList.
911  MaybeAddTrackersForNewFile(*file, batch.get());
912
913  const FileDetails& new_file_details = file->details();
914  PutFileToBatch(*file, batch.get());
915  file_by_id_[file_id] = file.release();
916
917  TrackerSet new_trackers;
918  if (!FindTrackersByFileID(file_id, &new_trackers)) {
919    NOTREACHED();
920    WriteToDatabase(batch.Pass(), callback);
921    return;
922  }
923  DCHECK_EQ(1u, new_trackers.size());
924
925  FileTracker* new_tracker = *new_trackers.begin();
926  DCHECK(!new_tracker->active());
927  DCHECK(new_tracker->has_synced_details());
928  DCHECK_EQ(parent_tracker_id, new_tracker->parent_tracker_id());
929
930  std::string title = new_file_details.title();
931  TrackerSet trackers;
932  if (FindTrackersByParentAndTitle(parent_tracker_id, title, &trackers) &&
933      trackers.has_active())
934    MakeTrackerInactive(trackers.active_tracker()->tracker_id(), batch.get());
935
936  MakeTrackerActive(new_tracker->tracker_id(), batch.get());
937
938  if (new_tracker->synced_details().title() != title) {
939    trackers_by_parent_and_title_[parent_tracker_id]
940        [GetTrackerTitle(*new_tracker)].Erase(new_tracker);
941    trackers_by_parent_and_title_[parent_tracker_id][title].Insert(
942        new_tracker);
943  }
944  *new_tracker->mutable_synced_details() = new_file_details;
945
946  new_tracker->set_dirty(false);
947  dirty_trackers_.erase(new_tracker);
948  low_priority_dirty_trackers_.erase(new_tracker);
949  PutTrackerToBatch(*new_tracker, batch.get());
950
951  WriteToDatabase(batch.Pass(), callback);
952}
953
954void MetadataDatabase::PopulateFolderByChildList(
955    const std::string& folder_id,
956    const FileIDList& child_file_ids,
957    const SyncStatusCallback& callback) {
958  TrackerSet trackers;
959  if (!FindTrackersByFileID(folder_id, &trackers) ||
960      !trackers.has_active()) {
961    // It's OK that there is no folder to populate its children.
962    // Inactive folders should ignore their contents updates.
963    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
964    return;
965  }
966
967  FileTracker* folder_tracker =
968      tracker_by_id_[trackers.active_tracker()->tracker_id()];
969  DCHECK(folder_tracker);
970  std::set<std::string> children(child_file_ids.begin(), child_file_ids.end());
971
972  std::vector<int64> known_children;
973  PushChildTrackersToContainer(trackers_by_parent_and_title_,
974                               folder_tracker->tracker_id(),
975                               std::back_inserter(known_children));
976  for (std::vector<int64>::iterator itr = known_children.begin();
977       itr != known_children.end(); ++itr)
978    children.erase(tracker_by_id_[*itr]->file_id());
979
980  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
981  for (FileIDList::const_iterator itr = child_file_ids.begin();
982       itr != child_file_ids.end(); ++itr)
983    CreateTrackerForParentAndFileID(*folder_tracker, *itr, batch.get());
984  folder_tracker->set_needs_folder_listing(false);
985  if (folder_tracker->dirty() && !ShouldKeepDirty(*folder_tracker)) {
986    folder_tracker->set_dirty(false);
987    dirty_trackers_.erase(folder_tracker);
988    low_priority_dirty_trackers_.erase(folder_tracker);
989  }
990  PutTrackerToBatch(*folder_tracker, batch.get());
991
992  WriteToDatabase(batch.Pass(), callback);
993}
994
995void MetadataDatabase::UpdateTracker(int64 tracker_id,
996                                     const FileDetails& updated_details,
997                                     const SyncStatusCallback& callback) {
998  TrackerByID::iterator found = tracker_by_id_.find(tracker_id);
999  if (found == tracker_by_id_.end()) {
1000    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
1001    return;
1002  }
1003
1004  FileTracker* tracker = found->second;
1005  DCHECK(tracker);
1006
1007  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
1008
1009  if (updated_details.missing()) {
1010    FileByID::iterator found = file_by_id_.find(tracker->file_id());
1011    if (found == file_by_id_.end() || found->second->details().missing()) {
1012      // Both the tracker and metadata have the missing flag, now it's safe to
1013      // delete the |tracker|.
1014      RemoveTracker(tracker->tracker_id(), batch.get());
1015      WriteToDatabase(batch.Pass(), callback);
1016      return;
1017    }
1018  }
1019
1020  // Sync-root deletion should be handled separately by SyncEngine.
1021  DCHECK(tracker_id != GetSyncRootTrackerID() ||
1022         (tracker->has_synced_details() &&
1023          tracker->synced_details().title() == updated_details.title() &&
1024          !updated_details.missing()));
1025
1026  if (tracker_id != GetSyncRootTrackerID()) {
1027    // Check if the tracker's parent is still in |parent_tracker_ids|.
1028    // If not, there should exist another tracker for the new parent, so delete
1029    // old tracker.
1030    DCHECK(ContainsKey(tracker_by_id_, tracker->parent_tracker_id()));
1031    FileTracker* parent_tracker = tracker_by_id_[tracker->parent_tracker_id()];
1032    if (!HasFileAsParent(updated_details, parent_tracker->file_id())) {
1033      RemoveTracker(tracker->tracker_id(), batch.get());
1034      WriteToDatabase(batch.Pass(), callback);
1035      return;
1036    }
1037
1038    if (tracker->has_synced_details()) {
1039      // Check if the tracker was retitled.  If it was, there should exist
1040      // another tracker for the new title, so delete old tracker.
1041      if (tracker->synced_details().title() != updated_details.title()) {
1042        RemoveTracker(tracker->tracker_id(), batch.get());
1043        WriteToDatabase(batch.Pass(), callback);
1044        return;
1045      }
1046    } else {
1047      int64 parent_tracker_id = parent_tracker->tracker_id();
1048      const std::string& title = updated_details.title();
1049      TrackerSet* trackers =
1050          &trackers_by_parent_and_title_[parent_tracker_id][title];
1051
1052      for (TrackerSet::iterator itr = trackers->begin();
1053           itr != trackers->end(); ++itr) {
1054        if ((*itr)->file_id() == tracker->file_id()) {
1055          RemoveTracker(tracker->tracker_id(), batch.get());
1056          WriteToDatabase(batch.Pass(), callback);
1057          return;
1058        }
1059      }
1060
1061      trackers_by_parent_and_title_[parent_tracker_id][std::string()].Erase(
1062          tracker);
1063      trackers->Insert(tracker);
1064    }
1065  }
1066
1067  *tracker->mutable_synced_details() = updated_details;
1068
1069  // Activate the tracker if:
1070  //   - There is no active tracker that tracks |tracker->file_id()|.
1071  //   - There is no active tracker that has the same |parent| and |title|.
1072  if (!tracker->active() && CanActivateTracker(*tracker))
1073    MakeTrackerActive(tracker->tracker_id(), batch.get());
1074  if (tracker->dirty() && !ShouldKeepDirty(*tracker)) {
1075    tracker->set_dirty(false);
1076    dirty_trackers_.erase(tracker);
1077    low_priority_dirty_trackers_.erase(tracker);
1078  }
1079  PutTrackerToBatch(*tracker, batch.get());
1080
1081  WriteToDatabase(batch.Pass(), callback);
1082}
1083
1084bool MetadataDatabase::TryNoSideEffectActivation(
1085    int64 parent_tracker_id,
1086    const std::string& file_id,
1087    const SyncStatusCallback& callback) {
1088  DCHECK(ContainsKey(tracker_by_id_, parent_tracker_id));
1089  DCHECK(ContainsKey(file_by_id_, file_id));
1090
1091  FileMetadata file;
1092  if (!FindFileByFileID(file_id, &file)) {
1093    NOTREACHED();
1094    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_FAILED));
1095    return true;
1096  }
1097  std::string title = file.details().title();
1098  DCHECK(!HasInvalidTitle(title));
1099
1100  TrackerSet same_file_id;
1101  FindTrackersByFileID(file_id, &same_file_id);
1102
1103  FileTracker* tracker = NULL;
1104  for (TrackerSet::iterator itr = same_file_id.begin();
1105       itr != same_file_id.end(); ++itr) {
1106    FileTracker* candidate = *itr;
1107    if (candidate->parent_tracker_id() != parent_tracker_id)
1108      continue;
1109
1110    if (candidate->has_synced_details() &&
1111        candidate->synced_details().title() != title)
1112      continue;
1113    tracker = candidate;
1114  }
1115
1116  DCHECK(tracker);
1117
1118  if (!tracker->active()) {
1119    if (same_file_id.has_active())
1120      return false;
1121
1122    TrackerSet same_title;
1123    FindTrackersByParentAndTitle(parent_tracker_id, title, &same_title);
1124    if (same_title.has_active())
1125      return false;
1126  }
1127
1128  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
1129  if (!tracker->has_synced_details() ||
1130      tracker->synced_details().title() != title) {
1131    trackers_by_parent_and_title_[parent_tracker_id]
1132        [GetTrackerTitle(*tracker)].Erase(tracker);
1133    trackers_by_parent_and_title_[parent_tracker_id][title].Insert(
1134        tracker);
1135  }
1136  *tracker->mutable_synced_details() = file.details();
1137
1138  MakeTrackerActive(tracker->tracker_id(), batch.get());
1139  tracker->set_dirty(false);
1140  dirty_trackers_.erase(tracker);
1141  low_priority_dirty_trackers_.erase(tracker);
1142  PutTrackerToBatch(*tracker, batch.get());
1143
1144  WriteToDatabase(batch.Pass(), callback);
1145  return true;
1146}
1147
1148void MetadataDatabase::LowerTrackerPriority(int64 tracker_id) {
1149  TrackerByID::const_iterator found = tracker_by_id_.find(tracker_id);
1150  if (found == tracker_by_id_.end())
1151    return;
1152
1153  FileTracker* tracker = found->second;
1154  if (dirty_trackers_.erase(tracker))
1155    low_priority_dirty_trackers_.insert(tracker);
1156}
1157
1158void MetadataDatabase::PromoteLowerPriorityTrackersToNormal() {
1159  if (dirty_trackers_.empty()) {
1160    dirty_trackers_.swap(low_priority_dirty_trackers_);
1161    return;
1162  }
1163  dirty_trackers_.insert(low_priority_dirty_trackers_.begin(),
1164                         low_priority_dirty_trackers_.end());
1165  low_priority_dirty_trackers_.clear();
1166}
1167
1168bool MetadataDatabase::GetNormalPriorityDirtyTracker(
1169    FileTracker* tracker) const {
1170  DirtyTrackers::const_iterator itr = dirty_trackers_.begin();
1171  if (itr == dirty_trackers_.end())
1172    return false;
1173  if (tracker)
1174    *tracker = **itr;
1175  return true;
1176}
1177
1178bool MetadataDatabase::GetLowPriorityDirtyTracker(
1179    FileTracker* tracker) const {
1180  DirtyTrackers::const_iterator itr = low_priority_dirty_trackers_.begin();
1181  if (itr == low_priority_dirty_trackers_.end())
1182    return false;
1183  if (tracker)
1184    *tracker = **itr;
1185  return true;
1186}
1187
1188bool MetadataDatabase::GetMultiParentFileTrackers(std::string* file_id,
1189                                                  TrackerSet* trackers) {
1190  DCHECK(file_id);
1191  DCHECK(trackers);
1192  // TODO(tzik): Make this function more efficient.
1193  for (TrackersByFileID::const_iterator itr = trackers_by_file_id_.begin();
1194       itr != trackers_by_file_id_.end(); ++itr) {
1195    if (itr->second.size() > 1 && itr->second.has_active()) {
1196      *file_id = itr->first;
1197      *trackers = itr->second;
1198      return true;
1199    }
1200  }
1201  return false;
1202}
1203
1204bool MetadataDatabase::GetConflictingTrackers(TrackerSet* trackers) {
1205  DCHECK(trackers);
1206  // TODO(tzik): Make this function more efficient.
1207  for (TrackersByParentAndTitle::const_iterator parent_itr =
1208           trackers_by_parent_and_title_.begin();
1209       parent_itr != trackers_by_parent_and_title_.end();
1210       ++parent_itr) {
1211    const TrackersByTitle& trackers_by_title = parent_itr->second;
1212    for (TrackersByTitle::const_iterator itr = trackers_by_title.begin();
1213         itr != trackers_by_title.end();
1214         ++itr) {
1215      if (itr->second.size() > 1 && itr->second.has_active()) {
1216        *trackers = itr->second;
1217        return true;
1218      }
1219    }
1220  }
1221  return false;
1222}
1223
1224void MetadataDatabase::GetRegisteredAppIDs(std::vector<std::string>* app_ids) {
1225  DCHECK(app_ids);
1226  app_ids->clear();
1227  app_ids->reserve(app_root_by_app_id_.size());
1228  for (TrackerByAppID::iterator itr = app_root_by_app_id_.begin();
1229       itr != app_root_by_app_id_.end(); ++itr) {
1230    app_ids->push_back(itr->first);
1231  }
1232}
1233
1234MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner,
1235                                   const base::FilePath& database_path)
1236    : task_runner_(task_runner),
1237      database_path_(database_path),
1238      largest_known_change_id_(0),
1239      weak_ptr_factory_(this) {
1240  DCHECK(task_runner);
1241}
1242
1243// static
1244void MetadataDatabase::CreateOnTaskRunner(
1245    base::SingleThreadTaskRunner* callback_runner,
1246    base::SequencedTaskRunner* task_runner,
1247    const base::FilePath& database_path,
1248    const CreateCallback& callback) {
1249  scoped_ptr<MetadataDatabase> metadata_database(
1250      new MetadataDatabase(task_runner, database_path));
1251  SyncStatusCode status =
1252      metadata_database->InitializeOnTaskRunner();
1253  if (status != SYNC_STATUS_OK)
1254    metadata_database.reset();
1255
1256  callback_runner->PostTask(FROM_HERE, base::Bind(
1257      callback, status, base::Passed(&metadata_database)));
1258}
1259
1260// static
1261SyncStatusCode MetadataDatabase::CreateForTesting(
1262    scoped_ptr<leveldb::DB> db,
1263    scoped_ptr<MetadataDatabase>* metadata_database_out) {
1264  scoped_ptr<MetadataDatabase> metadata_database(
1265      new MetadataDatabase(base::MessageLoopProxy::current(),
1266                           base::FilePath()));
1267  metadata_database->db_ = db.Pass();
1268  SyncStatusCode status =
1269      metadata_database->InitializeOnTaskRunner();
1270  if (status == SYNC_STATUS_OK)
1271    *metadata_database_out = metadata_database.Pass();
1272  return status;
1273}
1274
1275SyncStatusCode MetadataDatabase::InitializeOnTaskRunner() {
1276  base::ThreadRestrictions::AssertIOAllowed();
1277  DCHECK(task_runner_->RunsTasksOnCurrentThread());
1278
1279  SyncStatusCode status = SYNC_STATUS_UNKNOWN;
1280  bool created = false;
1281  // Open database unless |db_| is overridden for testing.
1282  if (!db_) {
1283    status = OpenDatabase(database_path_, &db_, &created);
1284    if (status != SYNC_STATUS_OK)
1285      return status;
1286  }
1287
1288  if (created) {
1289    status = WriteVersionInfo(db_.get());
1290    if (status != SYNC_STATUS_OK)
1291      return status;
1292  } else {
1293    status = MigrateDatabaseIfNeeded(db_.get());
1294    if (status != SYNC_STATUS_OK)
1295      return status;
1296  }
1297
1298  DatabaseContents contents;
1299  status = ReadDatabaseContents(db_.get(), &contents);
1300  if (status != SYNC_STATUS_OK)
1301    return status;
1302
1303  leveldb::WriteBatch batch;
1304  status = InitializeServiceMetadata(&contents, &batch);
1305  if (status != SYNC_STATUS_OK)
1306    return status;
1307
1308  status = RemoveUnreachableItems(&contents, &batch);
1309  if (status != SYNC_STATUS_OK)
1310    return status;
1311
1312  status = LevelDBStatusToSyncStatusCode(
1313      db_->Write(leveldb::WriteOptions(), &batch));
1314  if (status != SYNC_STATUS_OK)
1315    return status;
1316
1317  BuildIndexes(&contents);
1318  return status;
1319}
1320
1321void MetadataDatabase::BuildIndexes(DatabaseContents* contents) {
1322  service_metadata_ = contents->service_metadata.Pass();
1323  UpdateLargestKnownChangeID(service_metadata_->largest_change_id());
1324
1325  for (ScopedVector<FileMetadata>::const_iterator itr =
1326           contents->file_metadata.begin();
1327       itr != contents->file_metadata.end();
1328       ++itr) {
1329    file_by_id_[(*itr)->file_id()] = *itr;
1330  }
1331  contents->file_metadata.weak_clear();
1332
1333  for (ScopedVector<FileTracker>::const_iterator itr =
1334           contents->file_trackers.begin();
1335       itr != contents->file_trackers.end();
1336       ++itr) {
1337    FileTracker* tracker = *itr;
1338    tracker_by_id_[tracker->tracker_id()] = tracker;
1339    trackers_by_file_id_[tracker->file_id()].Insert(tracker);
1340
1341    if (IsAppRoot(*tracker))
1342      app_root_by_app_id_[tracker->app_id()] = tracker;
1343
1344    if (tracker->parent_tracker_id()) {
1345      std::string title = GetTrackerTitle(*tracker);
1346      TrackerSet* trackers =
1347          &trackers_by_parent_and_title_[tracker->parent_tracker_id()][title];
1348      trackers->Insert(tracker);
1349    }
1350
1351    if (tracker->dirty())
1352      dirty_trackers_.insert(tracker);
1353  }
1354  contents->file_trackers.weak_clear();
1355}
1356
1357void MetadataDatabase::RegisterTrackerAsAppRoot(
1358    const std::string& app_id,
1359    int64 tracker_id,
1360    leveldb::WriteBatch* batch) {
1361  FileTracker* tracker = tracker_by_id_[tracker_id];
1362  DCHECK(tracker);
1363  tracker->set_app_id(app_id);
1364  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
1365  app_root_by_app_id_[app_id] = tracker;
1366
1367  MakeTrackerActive(tracker->tracker_id(), batch);
1368}
1369
1370void MetadataDatabase::UnregisterTrackerAsAppRoot(
1371    const std::string& app_id,
1372    leveldb::WriteBatch* batch) {
1373  FileTracker* tracker = FindAndEraseItem(&app_root_by_app_id_, app_id);
1374  tracker->set_app_id(std::string());
1375  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1376
1377  // Inactivate the tracker to drop all descendant.
1378  // (Note that we set tracker_kind to TRACKER_KIND_REGULAR before calling
1379  // this.)
1380  MakeTrackerInactive(tracker->tracker_id(), batch);
1381}
1382
1383void MetadataDatabase::MakeTrackerActive(int64 tracker_id,
1384                                         leveldb::WriteBatch* batch) {
1385  FileTracker* tracker = tracker_by_id_[tracker_id];
1386  DCHECK(tracker);
1387  DCHECK(!tracker->active());
1388
1389  int64 parent_tracker_id = tracker->parent_tracker_id();
1390  DCHECK(tracker->has_synced_details());
1391  trackers_by_file_id_[tracker->file_id()].Activate(tracker);
1392  if (parent_tracker_id) {
1393    trackers_by_parent_and_title_[parent_tracker_id][
1394        tracker->synced_details().title()].Activate(tracker);
1395  }
1396  tracker->set_active(true);
1397  tracker->set_needs_folder_listing(
1398      tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
1399
1400  // Make |tracker| a normal priority dirty tracker.
1401  if (tracker->dirty())
1402    low_priority_dirty_trackers_.erase(tracker);
1403  tracker->set_dirty(true);
1404  dirty_trackers_.insert(tracker);
1405
1406  PutTrackerToBatch(*tracker, batch);
1407}
1408
1409void MetadataDatabase::MakeTrackerInactive(int64 tracker_id,
1410                                           leveldb::WriteBatch* batch) {
1411  FileTracker* tracker = tracker_by_id_[tracker_id];
1412  DCHECK(tracker);
1413  DCHECK(tracker->active());
1414  DCHECK_EQ(TRACKER_KIND_REGULAR, tracker->tracker_kind());
1415  trackers_by_file_id_[tracker->file_id()].Inactivate(tracker);
1416
1417  std::string title = GetTrackerTitle(*tracker);
1418  int64 parent_tracker_id = tracker->parent_tracker_id();
1419  if (parent_tracker_id)
1420    trackers_by_parent_and_title_[parent_tracker_id][title].Inactivate(tracker);
1421  tracker->set_active(false);
1422
1423  RemoveAllDescendantTrackers(tracker_id, batch);
1424  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
1425  if (parent_tracker_id)
1426    MarkTrackersDirtyByPath(parent_tracker_id, title, batch);
1427  PutTrackerToBatch(*tracker, batch);
1428}
1429
1430void MetadataDatabase::MakeAppRootDisabled(int64 tracker_id,
1431                                           leveldb::WriteBatch* batch) {
1432  FileTracker* tracker = tracker_by_id_[tracker_id];
1433  DCHECK(tracker);
1434  DCHECK_EQ(TRACKER_KIND_APP_ROOT, tracker->tracker_kind());
1435  DCHECK(tracker->active());
1436
1437  // Keep the app-root tracker active (but change the tracker_kind) so that
1438  // other conflicting trackers won't become active.
1439  tracker->set_tracker_kind(TRACKER_KIND_DISABLED_APP_ROOT);
1440  PutTrackerToBatch(*tracker, batch);
1441}
1442
1443void MetadataDatabase::MakeAppRootEnabled(int64 tracker_id,
1444                                          leveldb::WriteBatch* batch) {
1445  FileTracker* tracker = tracker_by_id_[tracker_id];
1446  DCHECK(tracker);
1447  DCHECK_EQ(TRACKER_KIND_DISABLED_APP_ROOT, tracker->tracker_kind());
1448  DCHECK(tracker->active());
1449
1450  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
1451  // Mark descendant trackers as dirty to handle changes in disable period.
1452  RecursiveMarkTrackerAsDirty(tracker_id, batch);
1453  PutTrackerToBatch(*tracker, batch);
1454}
1455
1456void MetadataDatabase::CreateTrackerForParentAndFileID(
1457    const FileTracker& parent_tracker,
1458    const std::string& file_id,
1459    leveldb::WriteBatch* batch) {
1460  CreateTrackerInternal(parent_tracker, file_id, NULL, batch);
1461}
1462
1463void MetadataDatabase::CreateTrackerForParentAndFileMetadata(
1464    const FileTracker& parent_tracker,
1465    const FileMetadata& file_metadata,
1466    leveldb::WriteBatch* batch) {
1467  DCHECK(file_metadata.has_details());
1468  CreateTrackerInternal(parent_tracker,
1469                        file_metadata.file_id(),
1470                        &file_metadata.details(),
1471                        batch);
1472}
1473
1474void MetadataDatabase::CreateTrackerInternal(const FileTracker& parent_tracker,
1475                                             const std::string& file_id,
1476                                             const FileDetails* details,
1477                                             leveldb::WriteBatch* batch) {
1478  int64 tracker_id = GetNextTrackerID(batch);
1479  scoped_ptr<FileTracker> tracker(new FileTracker);
1480  tracker->set_tracker_id(tracker_id);
1481  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
1482  tracker->set_file_id(file_id);
1483  tracker->set_app_id(parent_tracker.app_id());
1484  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1485  tracker->set_dirty(true);
1486  tracker->set_active(false);
1487  tracker->set_needs_folder_listing(false);
1488  if (details) {
1489    *tracker->mutable_synced_details() = *details;
1490    tracker->mutable_synced_details()->set_missing(true);
1491    tracker->mutable_synced_details()->clear_md5();
1492  }
1493  PutTrackerToBatch(*tracker, batch);
1494
1495  trackers_by_file_id_[file_id].Insert(tracker.get());
1496  // Note: |trackers_by_parent_and_title_| does not map from
1497  // FileMetadata::details but from FileTracker::synced_details, which is filled
1498  // on tracker updated phase.  Use empty string as the title since
1499  // FileTracker::synced_details is empty here.
1500  std::string title;
1501  if (details)
1502    title = details->title();
1503  trackers_by_parent_and_title_[parent_tracker.tracker_id()][title]
1504      .Insert(tracker.get());
1505  dirty_trackers_.insert(tracker.get());
1506  DCHECK(!ContainsKey(tracker_by_id_, tracker_id));
1507  tracker_by_id_[tracker_id] = tracker.release();
1508}
1509
1510void MetadataDatabase::RemoveTracker(int64 tracker_id,
1511                                     leveldb::WriteBatch* batch) {
1512  RemoveTrackerInternal(tracker_id, batch, false);
1513  RemoveAllDescendantTrackers(tracker_id, batch);
1514}
1515
1516void MetadataDatabase::RemoveTrackerIgnoringSameTitle(
1517    int64 tracker_id,
1518    leveldb::WriteBatch* batch) {
1519  RemoveTrackerInternal(tracker_id, batch, true);
1520}
1521
1522void MetadataDatabase::RemoveTrackerInternal(
1523    int64 tracker_id,
1524    leveldb::WriteBatch* batch,
1525    bool ignoring_same_title) {
1526  scoped_ptr<FileTracker> tracker(
1527      FindAndEraseItem(&tracker_by_id_, tracker_id));
1528  if (!tracker)
1529    return;
1530
1531  EraseTrackerFromFileIDIndex(tracker.get(), batch);
1532  if (IsAppRoot(*tracker))
1533    app_root_by_app_id_.erase(tracker->app_id());
1534  EraseTrackerFromPathIndex(tracker.get());
1535  dirty_trackers_.erase(tracker.get());
1536  low_priority_dirty_trackers_.erase(tracker.get());
1537
1538  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
1539  if (!ignoring_same_title) {
1540    // Mark trackers having the same title with the given tracker as dirty.
1541    MarkTrackersDirtyByPath(tracker->parent_tracker_id(),
1542                            GetTrackerTitle(*tracker),
1543                            batch);
1544  }
1545  PutTrackerDeletionToBatch(tracker_id, batch);
1546}
1547
1548void MetadataDatabase::MaybeAddTrackersForNewFile(
1549    const FileMetadata& file,
1550    leveldb::WriteBatch* batch) {
1551  std::set<int64> parents_to_exclude;
1552  TrackersByFileID::iterator found = trackers_by_file_id_.find(file.file_id());
1553  if (found != trackers_by_file_id_.end()) {
1554    for (TrackerSet::const_iterator itr = found->second.begin();
1555         itr != found->second.end(); ++itr) {
1556      const FileTracker& tracker = **itr;
1557      int64 parent_tracker_id = tracker.parent_tracker_id();
1558      if (!parent_tracker_id)
1559        continue;
1560
1561      // Exclude |parent_tracker_id| if it already has a tracker that has
1562      // unknown title or has the same title with |file|.
1563      if (!tracker.has_synced_details() ||
1564          tracker.synced_details().title() == file.details().title()) {
1565        parents_to_exclude.insert(parent_tracker_id);
1566      }
1567    }
1568  }
1569
1570  for (int i = 0; i < file.details().parent_folder_ids_size(); ++i) {
1571    std::string parent_folder_id = file.details().parent_folder_ids(i);
1572    TrackersByFileID::iterator found =
1573        trackers_by_file_id_.find(parent_folder_id);
1574    if (found == trackers_by_file_id_.end())
1575      continue;
1576
1577    for (TrackerSet::const_iterator itr = found->second.begin();
1578         itr != found->second.end(); ++itr) {
1579      FileTracker* parent_tracker = *itr;
1580      int64 parent_tracker_id = parent_tracker->tracker_id();
1581      if (!parent_tracker->active())
1582        continue;
1583
1584      if (ContainsKey(parents_to_exclude, parent_tracker_id))
1585        continue;
1586
1587      CreateTrackerForParentAndFileMetadata(*parent_tracker, file, batch);
1588    }
1589  }
1590}
1591
1592void MetadataDatabase::RemoveAllDescendantTrackers(int64 root_tracker_id,
1593                                                   leveldb::WriteBatch* batch) {
1594  std::vector<int64> pending_trackers;
1595  PushChildTrackersToContainer(trackers_by_parent_and_title_,
1596                               root_tracker_id,
1597                               std::back_inserter(pending_trackers));
1598
1599  while (!pending_trackers.empty()) {
1600    int64 tracker_id = pending_trackers.back();
1601    pending_trackers.pop_back();
1602    PushChildTrackersToContainer(trackers_by_parent_and_title_,
1603                                 tracker_id,
1604                                 std::back_inserter(pending_trackers));
1605    RemoveTrackerIgnoringSameTitle(tracker_id, batch);
1606  }
1607}
1608
1609void MetadataDatabase::EraseTrackerFromFileIDIndex(FileTracker* tracker,
1610                                                   leveldb::WriteBatch* batch) {
1611  TrackersByFileID::iterator found =
1612      trackers_by_file_id_.find(tracker->file_id());
1613  if (found == trackers_by_file_id_.end())
1614    return;
1615
1616  TrackerSet* trackers = &found->second;
1617  trackers->Erase(tracker);
1618  if (!trackers->tracker_set().empty())
1619    return;
1620  trackers_by_file_id_.erase(found);
1621  EraseFileFromDatabase(tracker->file_id(), batch);
1622}
1623
1624void MetadataDatabase::EraseFileFromDatabase(const std::string& file_id,
1625                                             leveldb::WriteBatch* batch) {
1626  scoped_ptr<FileMetadata> file(FindAndEraseItem(&file_by_id_, file_id));
1627  if (file)
1628    PutFileDeletionToBatch(file_id, batch);
1629}
1630
1631void MetadataDatabase::EraseTrackerFromPathIndex(FileTracker* tracker) {
1632  TrackersByParentAndTitle::iterator found =
1633      trackers_by_parent_and_title_.find(tracker->parent_tracker_id());
1634  if (found == trackers_by_parent_and_title_.end())
1635    return;
1636
1637  std::string title = GetTrackerTitle(*tracker);
1638  TrackersByTitle* trackers_by_title = &found->second;
1639  TrackersByTitle::iterator found_by_title = trackers_by_title->find(title);
1640  TrackerSet* conflicting_trackers = &found_by_title->second;
1641  conflicting_trackers->Erase(tracker);
1642
1643  if (conflicting_trackers->tracker_set().empty()) {
1644    trackers_by_title->erase(found_by_title);
1645    if (trackers_by_title->empty())
1646      trackers_by_parent_and_title_.erase(found);
1647  }
1648}
1649
1650void MetadataDatabase::MarkSingleTrackerDirty(FileTracker* tracker,
1651                                              leveldb::WriteBatch* batch) {
1652  if (!tracker->dirty()) {
1653    tracker->set_dirty(true);
1654    PutTrackerToBatch(*tracker, batch);
1655  }
1656  dirty_trackers_.insert(tracker);
1657  low_priority_dirty_trackers_.erase(tracker);
1658}
1659
1660void MetadataDatabase::MarkTrackerSetDirty(
1661    TrackerSet* trackers,
1662    leveldb::WriteBatch* batch) {
1663  for (TrackerSet::iterator itr = trackers->begin();
1664       itr != trackers->end(); ++itr) {
1665    MarkSingleTrackerDirty(*itr, batch);
1666  }
1667}
1668
1669void MetadataDatabase::MarkTrackersDirtyByFileID(
1670    const std::string& file_id,
1671    leveldb::WriteBatch* batch) {
1672  TrackersByFileID::iterator found = trackers_by_file_id_.find(file_id);
1673  if (found != trackers_by_file_id_.end())
1674    MarkTrackerSetDirty(&found->second, batch);
1675}
1676
1677void MetadataDatabase::MarkTrackersDirtyByPath(int64 parent_tracker_id,
1678                                               const std::string& title,
1679                                               leveldb::WriteBatch* batch) {
1680  TrackersByParentAndTitle::iterator found =
1681      trackers_by_parent_and_title_.find(parent_tracker_id);
1682  if (found == trackers_by_parent_and_title_.end())
1683    return;
1684
1685  TrackersByTitle::iterator itr = found->second.find(title);
1686  if (itr != found->second.end())
1687    MarkTrackerSetDirty(&itr->second, batch);
1688}
1689
1690int64 MetadataDatabase::GetNextTrackerID(leveldb::WriteBatch* batch) {
1691  int64 tracker_id = service_metadata_->next_tracker_id();
1692  service_metadata_->set_next_tracker_id(tracker_id + 1);
1693  PutServiceMetadataToBatch(*service_metadata_, batch);
1694  DCHECK_GT(tracker_id, 0);
1695  return tracker_id;
1696}
1697
1698void MetadataDatabase::RecursiveMarkTrackerAsDirty(int64 root_tracker_id,
1699                                                   leveldb::WriteBatch* batch) {
1700  std::vector<int64> stack;
1701  stack.push_back(root_tracker_id);
1702  while (!stack.empty()) {
1703    int64 tracker_id = stack.back();
1704    stack.pop_back();
1705    PushChildTrackersToContainer(
1706        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
1707
1708    FileTracker* tracker = tracker_by_id_[tracker_id];
1709    if (!tracker->dirty()) {
1710      tracker->set_dirty(true);
1711      PutTrackerToBatch(*tracker, batch);
1712      dirty_trackers_.insert(tracker);
1713      low_priority_dirty_trackers_.erase(tracker);
1714    }
1715  }
1716}
1717
1718bool MetadataDatabase::CanActivateTracker(const FileTracker& tracker) {
1719  DCHECK(!tracker.active());
1720  DCHECK_NE(service_metadata_->sync_root_tracker_id(), tracker.tracker_id());
1721
1722  if (HasActiveTrackerForFileID(tracker.file_id()))
1723    return false;
1724
1725  if (tracker.app_id().empty() &&
1726      tracker.tracker_id() != GetSyncRootTrackerID()) {
1727    return false;
1728  }
1729
1730  if (!tracker.has_synced_details())
1731    return false;
1732  if (tracker.synced_details().file_kind() == FILE_KIND_UNSUPPORTED)
1733    return false;
1734  if (HasInvalidTitle(tracker.synced_details().title()))
1735    return false;
1736  DCHECK(tracker.parent_tracker_id());
1737
1738  return !HasActiveTrackerForPath(tracker.parent_tracker_id(),
1739                                  tracker.synced_details().title());
1740}
1741
1742bool MetadataDatabase::ShouldKeepDirty(const FileTracker& tracker) const {
1743  if (HasDisabledAppRoot(tracker))
1744    return false;
1745
1746  DCHECK(tracker.dirty());
1747  if (!tracker.has_synced_details())
1748    return true;
1749
1750  FileByID::const_iterator found = file_by_id_.find(tracker.file_id());
1751  if (found == file_by_id_.end())
1752    return true;
1753  const FileMetadata* file = found->second;
1754  DCHECK(file);
1755  DCHECK(file->has_details());
1756
1757  const FileDetails& local_details = tracker.synced_details();
1758  const FileDetails& remote_details = file->details();
1759
1760  if (tracker.active()) {
1761    if (tracker.needs_folder_listing())
1762      return true;
1763    if (tracker.synced_details().md5() != file->details().md5())
1764      return true;
1765    if (local_details.missing() != remote_details.missing())
1766      return true;
1767  }
1768
1769  if (local_details.title() != remote_details.title())
1770    return true;
1771
1772  return false;
1773}
1774
1775bool MetadataDatabase::HasDisabledAppRoot(const FileTracker& tracker) const {
1776  TrackerByAppID::const_iterator found =
1777      app_root_by_app_id_.find(tracker.app_id());
1778  if (found == app_root_by_app_id_.end())
1779    return false;
1780
1781  const FileTracker* app_root_tracker = found->second;
1782  DCHECK(app_root_tracker);
1783  return app_root_tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
1784}
1785
1786bool MetadataDatabase::HasActiveTrackerForFileID(
1787    const std::string& file_id) const {
1788  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
1789  return found != trackers_by_file_id_.end() && found->second.has_active();
1790}
1791
1792bool MetadataDatabase::HasActiveTrackerForPath(int64 parent_tracker_id,
1793                                               const std::string& title) const {
1794  TrackersByParentAndTitle::const_iterator found_by_parent =
1795      trackers_by_parent_and_title_.find(parent_tracker_id);
1796  if (found_by_parent == trackers_by_parent_and_title_.end())
1797    return false;
1798
1799  const TrackersByTitle& trackers_by_title = found_by_parent->second;
1800  TrackersByTitle::const_iterator found = trackers_by_title.find(title);
1801  return found != trackers_by_title.end() && found->second.has_active();
1802}
1803
1804void MetadataDatabase::UpdateByFileMetadata(
1805    const tracked_objects::Location& from_where,
1806    scoped_ptr<FileMetadata> file,
1807    leveldb::WriteBatch* batch) {
1808  DCHECK(file);
1809  DCHECK(file->has_details());
1810
1811  DVLOG(1) << from_where.function_name() << ": "
1812           << file->file_id() << " ("
1813           << file->details().title() << ")"
1814           << (file->details().missing() ? " deleted" : "");
1815
1816  std::string file_id = file->file_id();
1817  if (file->details().missing()) {
1818    TrackerSet trackers;
1819    FindTrackersByFileID(file_id, &trackers);
1820    for (TrackerSet::const_iterator itr = trackers.begin();
1821         itr != trackers.end(); ++itr) {
1822      const FileTracker& tracker = **itr;
1823      if (!tracker.has_synced_details() ||
1824          tracker.synced_details().missing()) {
1825        RemoveTracker(tracker.tracker_id(), batch);
1826      }
1827    }
1828  } else {
1829    MaybeAddTrackersForNewFile(*file, batch);
1830  }
1831
1832  if (FindTrackersByFileID(file_id, NULL)) {
1833    MarkTrackersDirtyByFileID(file_id, batch);
1834    PutFileToBatch(*file, batch);
1835    FileMetadata* file_ptr = file.release();
1836    std::swap(file_ptr, file_by_id_[file_id]);
1837    delete file_ptr;
1838  }
1839}
1840
1841void MetadataDatabase::WriteToDatabase(scoped_ptr<leveldb::WriteBatch> batch,
1842                                       const SyncStatusCallback& callback) {
1843  base::PostTaskAndReplyWithResult(
1844      task_runner_.get(),
1845      FROM_HERE,
1846      base::Bind(&leveldb::DB::Write,
1847                 base::Unretained(db_.get()),
1848                 leveldb::WriteOptions(),
1849                 base::Owned(batch.release())),
1850      base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
1851}
1852
1853scoped_ptr<base::ListValue> MetadataDatabase::DumpFiles(
1854    const std::string& app_id) {
1855  scoped_ptr<base::ListValue> files(new base::ListValue);
1856
1857  FileTracker app_root_tracker;
1858  if (!FindAppRootTracker(app_id, &app_root_tracker))
1859    return files.Pass();
1860
1861  std::vector<int64> stack;
1862  PushChildTrackersToContainer(
1863        trackers_by_parent_and_title_,
1864        app_root_tracker.tracker_id(),
1865        std::back_inserter(stack));
1866  while (!stack.empty()) {
1867    int64 tracker_id = stack.back();
1868    stack.pop_back();
1869    PushChildTrackersToContainer(
1870        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
1871
1872    FileTracker* tracker = tracker_by_id_[tracker_id];
1873    base::DictionaryValue* file = new DictionaryValue;
1874
1875    base::FilePath path = BuildDisplayPathForTracker(*tracker);
1876    file->SetString("path", path.AsUTF8Unsafe());
1877    if (tracker->has_synced_details()) {
1878      file->SetString("title", tracker->synced_details().title());
1879      file->SetString("type",
1880                      FileKindToString(tracker->synced_details().file_kind()));
1881    }
1882
1883    base::DictionaryValue* details = new DictionaryValue;
1884    details->SetString("file_id", tracker->file_id());
1885    if (tracker->has_synced_details() &&
1886        tracker->synced_details().file_kind() == FILE_KIND_FILE)
1887      details->SetString("md5", tracker->synced_details().md5());
1888    details->SetString("active", tracker->active() ? "true" : "false");
1889    details->SetString("dirty", tracker->dirty() ? "true" : "false");
1890
1891    file->Set("details", details);
1892
1893    files->Append(file);
1894  }
1895
1896  return files.Pass();
1897}
1898
1899scoped_ptr<base::ListValue> MetadataDatabase::DumpDatabase() {
1900  scoped_ptr<base::ListValue> list(new base::ListValue);
1901  list->Append(DumpTrackers().release());
1902  list->Append(DumpMetadata().release());
1903  return list.Pass();
1904}
1905
1906bool MetadataDatabase::HasNewerFileMetadata(const std::string& file_id,
1907                                            int64 change_id) {
1908  FileByID::const_iterator found = file_by_id_.find(file_id);
1909  if (found == file_by_id_.end())
1910    return false;
1911  DCHECK(found->second->has_details());
1912  return found->second->details().change_id() >= change_id;
1913}
1914
1915scoped_ptr<base::ListValue> MetadataDatabase::DumpTrackers() {
1916  scoped_ptr<base::ListValue> trackers(new base::ListValue);
1917
1918  // Append the first element for metadata.
1919  base::DictionaryValue* metadata = new DictionaryValue;
1920  const char *trackerKeys[] = {
1921    "tracker_id", "path", "file_id", "tracker_kind", "app_id",
1922    "active", "dirty", "folder_listing",
1923    "title", "kind", "md5", "etag", "missing", "change_id",
1924  };
1925  std::vector<std::string> key_strings(
1926      trackerKeys, trackerKeys + ARRAYSIZE_UNSAFE(trackerKeys));
1927  base::ListValue* keys = new ListValue;
1928  keys->AppendStrings(key_strings);
1929  metadata->SetString("title", "Trackers");
1930  metadata->Set("keys", keys);
1931  trackers->Append(metadata);
1932
1933  // Append tracker data.
1934  for (TrackerByID::const_iterator itr = tracker_by_id_.begin();
1935       itr != tracker_by_id_.end(); ++itr) {
1936    const FileTracker& tracker = *itr->second;
1937    base::DictionaryValue* dict = new DictionaryValue;
1938    base::FilePath path = BuildDisplayPathForTracker(tracker);
1939    dict->SetString("tracker_id", base::Int64ToString(tracker.tracker_id()));
1940    dict->SetString("path", path.AsUTF8Unsafe());
1941    dict->SetString("file_id", tracker.file_id());
1942    TrackerKind tracker_kind = tracker.tracker_kind();
1943    dict->SetString(
1944        "tracker_kind",
1945        tracker_kind == TRACKER_KIND_APP_ROOT ? "AppRoot" :
1946        tracker_kind == TRACKER_KIND_DISABLED_APP_ROOT ? "Disabled App" :
1947        tracker.tracker_id() == GetSyncRootTrackerID() ? "SyncRoot" :
1948        "Regular");
1949    dict->SetString("app_id", tracker.app_id());
1950    dict->SetString("active", tracker.active() ? "true" : "false");
1951    dict->SetString("dirty", tracker.dirty() ? "true" : "false");
1952    dict->SetString("folder_listing",
1953                    tracker.needs_folder_listing() ? "needed" : "no");
1954    if (tracker.has_synced_details()) {
1955      const FileDetails& details = tracker.synced_details();
1956      dict->SetString("title", details.title());
1957      dict->SetString("kind", FileKindToString(details.file_kind()));
1958      dict->SetString("md5", details.md5());
1959      dict->SetString("etag", details.etag());
1960      dict->SetString("missing", details.missing() ? "true" : "false");
1961      dict->SetString("change_id", base::Int64ToString(details.change_id()));
1962    }
1963    trackers->Append(dict);
1964  }
1965  return trackers.Pass();
1966}
1967
1968scoped_ptr<base::ListValue> MetadataDatabase::DumpMetadata() {
1969  scoped_ptr<base::ListValue> files(new base::ListValue);
1970
1971  // Append the first element for metadata.
1972  base::DictionaryValue* metadata = new DictionaryValue;
1973  const char *fileKeys[] = {
1974    "file_id", "title", "type", "md5", "etag", "missing",
1975    "change_id", "parents"
1976  };
1977  std::vector<std::string> key_strings(
1978      fileKeys, fileKeys + ARRAYSIZE_UNSAFE(fileKeys));
1979  base::ListValue* keys = new ListValue;
1980  keys->AppendStrings(key_strings);
1981  metadata->SetString("title", "Metadata");
1982  metadata->Set("keys", keys);
1983  files->Append(metadata);
1984
1985  // Append metadata data.
1986  for (FileByID::const_iterator itr = file_by_id_.begin();
1987       itr != file_by_id_.end(); ++itr) {
1988    const FileMetadata& file = *itr->second;
1989
1990    base::DictionaryValue* dict = new DictionaryValue;
1991    dict->SetString("file_id", file.file_id());
1992    if (file.has_details()) {
1993      const FileDetails& details = file.details();
1994      dict->SetString("title", details.title());
1995      dict->SetString("type", FileKindToString(details.file_kind()));
1996      dict->SetString("md5", details.md5());
1997      dict->SetString("etag", details.etag());
1998      dict->SetString("missing", details.missing() ? "true" : "false");
1999      dict->SetString("change_id", base::Int64ToString(details.change_id()));
2000
2001      std::vector<std::string> parents;
2002      for (int i = 0; i < details.parent_folder_ids_size(); ++i)
2003        parents.push_back(details.parent_folder_ids(i));
2004      dict->SetString("parents", JoinString(parents, ","));
2005    }
2006    files->Append(dict);
2007  }
2008  return files.Pass();
2009}
2010
2011}  // namespace drive_backend
2012}  // namespace sync_file_system
2013