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