metadata_database.cc revision 3551c9c881056c480085172ff9840cab31610854 
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 <stack>
8
9#include "base/bind.h"
10#include "base/callback.h"
11#include "base/files/file_path.h"
12#include "base/location.h"
13#include "base/memory/scoped_vector.h"
14#include "base/message_loop/message_loop_proxy.h"
15#include "base/sequenced_task_runner.h"
16#include "base/stl_util.h"
17#include "base/strings/string_number_conversions.h"
18#include "base/strings/string_util.h"
19#include "base/strings/stringprintf.h"
20#include "base/task_runner_util.h"
21#include "base/threading/thread_restrictions.h"
22#include "chrome/browser/google_apis/drive_api_parser.h"
23#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
24#include "chrome/browser/sync_file_system/drive_backend/metadata_db_migration_util.h"
25#include "chrome/browser/sync_file_system/logger.h"
26#include "chrome/browser/sync_file_system/syncable_file_system_util.h"
27#include "third_party/leveldatabase/src/include/leveldb/db.h"
28#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
29#include "webkit/common/fileapi/file_system_util.h"
30
31namespace sync_file_system {
32namespace drive_backend {
33
34const char kDatabaseVersionKey[] = "VERSION";
35const int64 kCurrentDatabaseVersion = 3;
36const char kServiceMetadataKey[] = "SERVICE";
37const char kFileMetadataKeyPrefix[] = "FILE: ";
38const char kFileTrackerKeyPrefix[] = "TRACKER: ";
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
86scoped_ptr<FileMetadata> CreateFileMetadataFromChangeResource(
87    const google_apis::ChangeResource& change) {
88  scoped_ptr<FileMetadata> file(new FileMetadata);
89  file->set_file_id(change.file_id());
90
91  FileDetails* details = file->mutable_details();
92  details->set_change_id(change.change_id());
93
94  if (change.is_deleted()) {
95    details->set_deleted(true);
96    return file.Pass();
97  }
98
99  const google_apis::FileResource& file_resource = *change.file();
100  for (ScopedVector<google_apis::ParentReference>::const_iterator itr =
101           file_resource.parents().begin();
102       itr != file_resource.parents().end();
103       ++itr) {
104    details->add_parent_folder_ids((*itr)->file_id());
105  }
106  details->set_title(file_resource.title());
107
108  google_apis::DriveEntryKind kind = file_resource.GetKind();
109  if (kind == google_apis::ENTRY_KIND_FILE)
110    details->set_file_kind(FILE_KIND_FILE);
111  else if (kind == google_apis::ENTRY_KIND_FOLDER)
112    details->set_file_kind(FILE_KIND_FOLDER);
113  else
114    details->set_file_kind(FILE_KIND_UNSUPPORTED);
115
116  details->set_md5(file_resource.md5_checksum());
117  details->set_etag(file_resource.etag());
118  details->set_creation_time(file_resource.created_date().ToInternalValue());
119  details->set_modification_time(
120      file_resource.modified_date().ToInternalValue());
121  details->set_deleted(false);
122
123  return file.Pass();
124}
125
126void AdaptLevelDBStatusToSyncStatusCode(const SyncStatusCallback& callback,
127                                        const leveldb::Status& status) {
128  callback.Run(LevelDBStatusToSyncStatusCode(status));
129}
130
131void PutServiceMetadataToBatch(const ServiceMetadata& service_metadata,
132                               leveldb::WriteBatch* batch) {
133  std::string value;
134  bool success = service_metadata.SerializeToString(&value);
135  DCHECK(success);
136  batch->Put(kServiceMetadataKey, value);
137}
138
139void PutFileToBatch(const FileMetadata& file, leveldb::WriteBatch* batch) {
140  std::string value;
141  bool success = file.SerializeToString(&value);
142  DCHECK(success);
143  batch->Put(kFileMetadataKeyPrefix + file.file_id(), value);
144}
145
146void PutTrackerToBatch(const FileTracker& tracker, leveldb::WriteBatch* batch) {
147  std::string value;
148  bool success = tracker.SerializeToString(&value);
149  DCHECK(success);
150  batch->Put(kFileTrackerKeyPrefix + base::Int64ToString(tracker.tracker_id()),
151             value);
152}
153
154void PutFileDeletionToBatch(const std::string& file_id,
155                            leveldb::WriteBatch* batch) {
156  batch->Delete(kFileMetadataKeyPrefix + file_id);
157}
158
159void PutTrackerDeletionToBatch(int64 tracker_id, leveldb::WriteBatch* batch) {
160  batch->Delete(kFileTrackerKeyPrefix + base::Int64ToString(tracker_id));
161}
162
163template <typename OutputIterator>
164OutputIterator PushChildTrackersToContainer(
165    const TrackersByParentAndTitle& trackers_by_parent,
166    int64 parent_tracker_id,
167    OutputIterator target_itr) {
168  TrackersByParentAndTitle::const_iterator found =
169      trackers_by_parent.find(parent_tracker_id);
170  if (found == trackers_by_parent.end())
171    return target_itr;
172
173  for (TrackersByTitle::const_iterator title_itr = found->second.begin();
174       title_itr != found->second.end(); ++title_itr) {
175    const TrackerSet& trackers = title_itr->second;
176    for (TrackerSet::const_iterator tracker_itr = trackers.begin();
177         tracker_itr != trackers.end(); ++tracker_itr) {
178      *target_itr = (*tracker_itr)->tracker_id();
179      ++target_itr;
180    }
181  }
182  return target_itr;
183}
184
185std::string GetTrackerTitle(const FileTracker& tracker) {
186  if (tracker.has_synced_details())
187    return tracker.synced_details().title();
188  return std::string();
189}
190
191// Returns true if |db| has no content.
192bool IsDatabaseEmpty(leveldb::DB* db) {
193  DCHECK(db);
194  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
195  itr->SeekToFirst();
196  return !itr->Valid();
197}
198
199SyncStatusCode OpenDatabase(const base::FilePath& path,
200                            scoped_ptr<leveldb::DB>* db_out,
201                            bool* created) {
202  base::ThreadRestrictions::AssertIOAllowed();
203  DCHECK(db_out);
204  DCHECK(created);
205
206  leveldb::Options options;
207  options.max_open_files = 0;  // Use minimum.
208  options.create_if_missing = true;
209  leveldb::DB* db = NULL;
210  leveldb::Status db_status =
211      leveldb::DB::Open(options, path.AsUTF8Unsafe(), &db);
212  SyncStatusCode status = LevelDBStatusToSyncStatusCode(db_status);
213  if (status != SYNC_STATUS_OK) {
214    delete db;
215    return status;
216  }
217
218  *created = IsDatabaseEmpty(db);
219  db_out->reset(db);
220  return status;
221}
222
223SyncStatusCode MigrateDatabaseIfNeeded(leveldb::DB* db) {
224  base::ThreadRestrictions::AssertIOAllowed();
225  DCHECK(db);
226  std::string value;
227  leveldb::Status status =
228      db->Get(leveldb::ReadOptions(), kDatabaseVersionKey, &value);
229  int64 version = 0;
230  if (status.ok()) {
231    if (!base::StringToInt64(value, &version))
232      return SYNC_DATABASE_ERROR_FAILED;
233  } else {
234    if (!status.IsNotFound())
235      return SYNC_DATABASE_ERROR_FAILED;
236  }
237
238  switch (version) {
239    case 0:
240      drive_backend::MigrateDatabaseFromV0ToV1(db);
241      // fall-through
242    case 1:
243      drive_backend::MigrateDatabaseFromV1ToV2(db);
244      // fall-through
245    case 2:
246      // TODO(tzik): Migrate database from version 2 to 3.
247      //   * Add sync-root folder as active, dirty and needs_folder_listing
248      //     folder.
249      //   * Add app-root folders for each origins.  Each app-root folder for
250      //     an enabled origin should be a active, dirty and
251      //     needs_folder_listing folder.  And Each app-root folder for a
252      //     disabled origin should be an inactive, dirty and
253      //     non-needs_folder_listing folder.
254      //   * Add a file metadata for each file in previous version.
255      NOTIMPLEMENTED();
256      return SYNC_DATABASE_ERROR_FAILED;
257      // fall-through
258    case 3:
259      DCHECK_EQ(3, kCurrentDatabaseVersion);
260      return SYNC_STATUS_OK;
261    default:
262      return SYNC_DATABASE_ERROR_FAILED;
263  }
264}
265
266SyncStatusCode WriteVersionInfo(leveldb::DB* db) {
267  base::ThreadRestrictions::AssertIOAllowed();
268  DCHECK(db);
269  return LevelDBStatusToSyncStatusCode(
270      db->Put(leveldb::WriteOptions(),
271              kDatabaseVersionKey,
272              base::Int64ToString(kCurrentDatabaseVersion)));
273}
274
275SyncStatusCode ReadDatabaseContents(leveldb::DB* db,
276                                    DatabaseContents* contents) {
277  base::ThreadRestrictions::AssertIOAllowed();
278  DCHECK(db);
279  DCHECK(contents);
280
281  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
282  for (itr->SeekToFirst(); itr->Valid(); itr->Next()) {
283    std::string key = itr->key().ToString();
284    std::string value = itr->value().ToString();
285    if (key == kServiceMetadataKey) {
286      scoped_ptr<ServiceMetadata> service_metadata(new ServiceMetadata);
287      if (!service_metadata->ParseFromString(value)) {
288        util::Log(logging::LOG_WARNING, FROM_HERE,
289                  "Failed to parse SyncServiceMetadata");
290        continue;
291      }
292
293      contents->service_metadata = service_metadata.Pass();
294      continue;
295    }
296
297    if (StartsWithASCII(key, kFileMetadataKeyPrefix, true)) {
298      std::string file_id = RemovePrefix(key, kFileMetadataKeyPrefix);
299
300      scoped_ptr<FileMetadata> file(new FileMetadata);
301      if (!file->ParseFromString(itr->value().ToString())) {
302        util::Log(logging::LOG_WARNING, FROM_HERE,
303                  "Failed to parse a FileMetadata");
304        continue;
305      }
306
307      contents->file_metadata.push_back(file.release());
308      continue;
309    }
310
311    if (StartsWithASCII(key, kFileTrackerKeyPrefix, true)) {
312      int64 tracker_id = 0;
313      if (!base::StringToInt64(RemovePrefix(key, kFileTrackerKeyPrefix),
314                               &tracker_id)) {
315        util::Log(logging::LOG_WARNING, FROM_HERE,
316                  "Failed to parse TrackerID");
317        continue;
318      }
319
320      scoped_ptr<FileTracker> tracker(new FileTracker);
321      if (!tracker->ParseFromString(itr->value().ToString())) {
322        util::Log(logging::LOG_WARNING, FROM_HERE,
323                  "Failed to parse a Tracker");
324        continue;
325      }
326      contents->file_trackers.push_back(tracker.release());
327      continue;
328    }
329  }
330
331  return SYNC_STATUS_OK;
332}
333
334SyncStatusCode InitializeServiceMetadata(DatabaseContents* contents,
335                                         leveldb::WriteBatch* batch) {
336  if (!contents->service_metadata) {
337    contents->service_metadata.reset(new ServiceMetadata);
338    contents->service_metadata->set_next_tracker_id(1);
339
340    std::string value;
341    contents->service_metadata->SerializeToString(&value);
342    batch->Put(kServiceMetadataKey, value);
343  }
344  return SYNC_STATUS_OK;
345}
346
347SyncStatusCode RemoveUnreachableItems(DatabaseContents* contents,
348                                      leveldb::WriteBatch* batch) {
349  TrackerByID unvisited_trackers;
350  typedef std::map<int64, std::set<FileTracker*> > TrackersByParent;
351  TrackersByParent trackers_by_parent;
352
353  for (ScopedVector<FileTracker>::iterator itr =
354           contents->file_trackers.begin();
355       itr != contents->file_trackers.end();
356       ++itr) {
357    FileTracker* tracker = *itr;
358    DCHECK(!ContainsKey(unvisited_trackers, tracker->tracker_id()));
359    unvisited_trackers[tracker->tracker_id()] = tracker;
360    if (tracker->parent_tracker_id())
361      trackers_by_parent[tracker->parent_tracker_id()].insert(tracker);
362  }
363
364  // Traverse synced tracker tree. Take only active items, app-root and their
365  // children. Drop unreachable items.
366  ScopedVector<FileTracker> reachable_trackers;
367  std::stack<int64> pending;
368  if (contents->service_metadata->sync_root_tracker_id())
369    pending.push(contents->service_metadata->sync_root_tracker_id());
370
371  while (!pending.empty()) {
372    int64 tracker_id = pending.top();
373    pending.pop();
374
375    {
376      TrackerByID::iterator found = unvisited_trackers.find(tracker_id);
377      if (found == unvisited_trackers.end())
378        continue;
379
380      FileTracker* tracker = found->second;
381      unvisited_trackers.erase(found);
382      reachable_trackers.push_back(tracker);
383
384      if (!tracker->active())
385        continue;
386    }
387
388    TrackersByParent::iterator found = trackers_by_parent.find(tracker_id);
389    if (found == trackers_by_parent.end())
390      continue;
391
392    for (std::set<FileTracker*>::const_iterator itr =
393             found->second.begin();
394         itr != found->second.end();
395         ++itr)
396      pending.push((*itr)->tracker_id());
397  }
398
399  // Delete all unreachable trackers.
400  for (TrackerByID::iterator itr = unvisited_trackers.begin();
401       itr != unvisited_trackers.end(); ++itr) {
402    FileTracker* tracker = itr->second;
403    PutTrackerDeletionToBatch(tracker->tracker_id(), batch);
404    delete tracker;
405  }
406  unvisited_trackers.clear();
407
408  // |reachable_trackers| contains all files/folders reachable from sync-root
409  // folder via active folders and app-root folders.
410  // Update the tracker set in database contents with the reachable tracker set.
411  contents->file_trackers.weak_clear();
412  contents->file_trackers.swap(reachable_trackers);
413
414  // Do the similar traverse for FileMetadata and remove FileMetadata that don't
415  // have reachable trackers.
416  FileByID unreferred_files;
417  for (ScopedVector<FileMetadata>::const_iterator itr =
418           contents->file_metadata.begin();
419       itr != contents->file_metadata.end();
420       ++itr) {
421    unreferred_files.insert(std::make_pair((*itr)->file_id(), *itr));
422  }
423
424  ScopedVector<FileMetadata> referred_files;
425  for (ScopedVector<FileTracker>::const_iterator itr =
426           contents->file_trackers.begin();
427       itr != contents->file_trackers.end();
428       ++itr) {
429    FileByID::iterator found = unreferred_files.find((*itr)->file_id());
430    if (found != unreferred_files.end()) {
431      referred_files.push_back(found->second);
432      unreferred_files.erase(found);
433    }
434  }
435
436  for (FileByID::iterator itr = unreferred_files.begin();
437       itr != unreferred_files.end(); ++itr) {
438    FileMetadata* file = itr->second;
439    PutFileDeletionToBatch(file->file_id(), batch);
440    delete file;
441  }
442  unreferred_files.clear();
443
444  contents->file_metadata.weak_clear();
445  contents->file_metadata.swap(referred_files);
446
447  return SYNC_STATUS_OK;
448}
449
450template <typename Container, typename Key, typename Value>
451bool FindItem(const Container& container, const Key& key, Value* value) {
452  typename Container::const_iterator found = container.find(key);
453  if (found == container.end())
454    return false;
455  if (value)
456    *value = *found->second;
457  return true;
458}
459
460template <typename Container, typename Key>
461typename Container::mapped_type FindAndEraseItem(Container* container,
462                                                 const Key& key) {
463  typedef typename Container::mapped_type Value;
464  typename Container::iterator found = container->find(key);
465  if (found == container->end())
466    return Value();
467
468  Value result = found->second;
469  container->erase(found);
470  return result;
471}
472
473void RunSoon(const tracked_objects::Location& from_here,
474             const base::Closure& closure) {
475  base::MessageLoopProxy::current()->PostTask(from_here, closure);
476}
477
478}  // namespace
479
480bool MetadataDatabase::DirtyTrackerComparator::operator()(
481    const FileTracker* left,
482    const FileTracker* right) const {
483  return left->tracker_id() < right->tracker_id();
484}
485
486// static
487void MetadataDatabase::Create(base::SequencedTaskRunner* task_runner,
488                              const base::FilePath& database_path,
489                              const CreateCallback& callback) {
490  task_runner->PostTask(FROM_HERE, base::Bind(
491      &CreateOnTaskRunner,
492      base::MessageLoopProxy::current(),
493      make_scoped_refptr(task_runner),
494      database_path, callback));
495}
496
497MetadataDatabase::~MetadataDatabase() {
498  task_runner_->DeleteSoon(FROM_HERE, db_.release());
499  STLDeleteContainerPairSecondPointers(
500      file_by_id_.begin(), file_by_id_.end());
501  STLDeleteContainerPairSecondPointers(
502      tracker_by_id_.begin(), tracker_by_id_.end());
503}
504
505int64 MetadataDatabase::GetLargestChangeID() const {
506  return service_metadata_->largest_change_id();
507}
508
509void MetadataDatabase::RegisterApp(const std::string& app_id,
510                                   const std::string& folder_id,
511                                   const SyncStatusCallback& callback) {
512  if (FindAppRootTracker(app_id, NULL)) {
513    // The app-root is already registered.
514    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
515    return;
516  }
517
518  TrackerSet trackers;
519  if (!FindTrackersByFileID(folder_id, &trackers) || trackers.has_active()) {
520    // The folder is tracked by another tracker.
521    util::Log(logging::LOG_WARNING, FROM_HERE,
522              "Failed to register App for %s", app_id.c_str());
523    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_HAS_CONFLICT));
524    return;
525  }
526
527  int64 sync_root_tracker_id = service_metadata_->sync_root_tracker_id();
528  if (!sync_root_tracker_id) {
529    util::Log(logging::LOG_WARNING, FROM_HERE,
530              "Sync-root needs to be set up before registering app-root");
531    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
532    return;
533  }
534
535  // Make this tracker an app-root tracker.
536  FileTracker* app_root_tracker = NULL;
537  for (TrackerSet::iterator itr = trackers.begin();
538       itr != trackers.end(); ++itr) {
539    FileTracker* tracker = *itr;
540    if (tracker->parent_tracker_id() == sync_root_tracker_id)
541      app_root_tracker = tracker;
542  }
543
544  if (!app_root_tracker) {
545    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
546    return;
547  }
548
549  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
550  RegisterTrackerAsAppRoot(app_id, app_root_tracker->tracker_id(), batch.get());
551  WriteToDatabase(batch.Pass(), callback);
552}
553
554void MetadataDatabase::DisableApp(const std::string& app_id,
555                                  const SyncStatusCallback& callback) {
556  FileTracker tracker;
557  if (!FindAppRootTracker(app_id, &tracker)) {
558    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
559    return;
560  }
561
562  if (tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
563    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
564    return;
565  }
566
567  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
568  MakeAppRootDisabled(tracker.tracker_id(), batch.get());
569  WriteToDatabase(batch.Pass(), callback);
570}
571
572void MetadataDatabase::EnableApp(const std::string& app_id,
573                                 const SyncStatusCallback& callback) {
574  FileTracker tracker;
575  if (!FindAppRootTracker(app_id, &tracker) ||
576      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
577    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
578    return;
579  }
580
581  if (tracker.tracker_kind() == TRACKER_KIND_APP_ROOT) {
582    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
583    return;
584  }
585
586  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
587  MakeAppRootEnabled(tracker.tracker_id(), batch.get());
588  WriteToDatabase(batch.Pass(), callback);
589}
590
591void MetadataDatabase::UnregisterApp(const std::string& app_id,
592                                     const SyncStatusCallback& callback) {
593  FileTracker tracker;
594  if (!FindAppRootTracker(app_id, &tracker) ||
595      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
596    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
597    return;
598  }
599
600  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
601  UnregisterTrackerAsAppRoot(app_id, batch.get());
602  WriteToDatabase(batch.Pass(), callback);
603}
604
605bool MetadataDatabase::FindAppRootTracker(const std::string& app_id,
606                                          FileTracker* tracker) const {
607  return FindItem(app_root_by_app_id_, app_id, tracker);
608}
609
610bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
611                                        FileMetadata* file) const {
612  return FindItem(file_by_id_, file_id, file);
613}
614
615bool MetadataDatabase::FindTrackersByFileID(const std::string& file_id,
616                                            TrackerSet* trackers) const {
617  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
618  if (found == trackers_by_file_id_.end())
619    return false;
620  if (trackers)
621    *trackers = found->second;
622  return true;
623}
624
625bool MetadataDatabase::FindTrackerByTrackerID(int64 tracker_id,
626                                              FileTracker* tracker) const {
627  return FindItem(tracker_by_id_, tracker_id, tracker);
628}
629
630bool MetadataDatabase::BuildPathForTracker(int64 tracker_id,
631                                           base::FilePath* path) const {
632  FileTracker current;
633  if (!FindTrackerByTrackerID(tracker_id, &current) || !current.active())
634    return false;
635
636  std::vector<base::FilePath> components;
637  while (!IsAppRoot(current)) {
638    std::string title = GetTrackerTitle(current);
639    if (title.empty())
640      return false;
641    components.push_back(base::FilePath::FromUTF8Unsafe(title));
642    if (!FindTrackerByTrackerID(current.parent_tracker_id(), &current) ||
643        !current.active())
644      return false;
645  }
646
647  if (path)
648    *path = ReverseConcatPathComponents(components);
649
650  return true;
651}
652
653void MetadataDatabase::UpdateByChangeList(
654    ScopedVector<google_apis::ChangeResource> changes,
655    const SyncStatusCallback& callback) {
656  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
657
658  for (ScopedVector<google_apis::ChangeResource>::const_iterator itr =
659           changes.begin();
660       itr != changes.end();
661       ++itr) {
662    const google_apis::ChangeResource& change = **itr;
663    scoped_ptr<FileMetadata> file(
664        CreateFileMetadataFromChangeResource(change));
665    std::string file_id = file->file_id();
666
667    MarkTrackersDirtyByFileID(file_id, batch.get());
668    if (!file->details().deleted())
669      MaybeAddTrackersForNewFile(*file, batch.get());
670
671    if (FindTrackersByFileID(file_id, NULL)) {
672      PutFileToBatch(*file, batch.get());
673
674      FileMetadata* file_ptr = file.release();
675      std::swap(file_ptr, file_by_id_[file_id]);
676      delete file_ptr;
677    }
678  }
679
680  WriteToDatabase(batch.Pass(), callback);
681}
682
683void MetadataDatabase::PopulateFolder(const std::string& folder_id,
684                                      const FileIDList& child_file_ids,
685                                      const SyncStatusCallback& callback) {
686  TrackerSet trackers;
687  if (!FindTrackersByFileID(folder_id, &trackers) ||
688      !trackers.has_active()) {
689    // It's OK that there is no folder to populate its children.
690    // Inactive folders should ignore their contents updates.
691    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
692    return;
693  }
694
695  FileTracker* folder_tracker =
696      tracker_by_id_[trackers.active_tracker()->tracker_id()];
697  DCHECK(folder_tracker);
698  std::set<std::string> children(child_file_ids.begin(), child_file_ids.end());
699
700  std::vector<int64> known_children;
701  PushChildTrackersToContainer(trackers_by_parent_and_title_,
702                               folder_tracker->tracker_id(),
703                               std::back_inserter(known_children));
704  for (std::vector<int64>::iterator itr = known_children.begin();
705       itr != known_children.end(); ++itr)
706    children.erase(tracker_by_id_[*itr]->file_id());
707
708  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
709  for (FileIDList::const_iterator itr = child_file_ids.begin();
710       itr != child_file_ids.end(); ++itr)
711    CreateTrackerForParentAndFileID(*folder_tracker, *itr, batch.get());
712  folder_tracker->set_needs_folder_listing(false);
713  if (!ShouldKeepDirty(*folder_tracker)) {
714    folder_tracker->set_dirty(false);
715    dirty_trackers_.erase(folder_tracker);
716  }
717  PutTrackerToBatch(*folder_tracker, batch.get());
718
719  WriteToDatabase(batch.Pass(), callback);
720}
721
722MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner)
723    : task_runner_(task_runner), weak_ptr_factory_(this) {
724  DCHECK(task_runner);
725}
726
727// static
728void MetadataDatabase::CreateOnTaskRunner(
729    base::SingleThreadTaskRunner* callback_runner,
730    base::SequencedTaskRunner* task_runner,
731    const base::FilePath& database_path,
732    const CreateCallback& callback) {
733  scoped_ptr<MetadataDatabase> metadata_database(
734      new MetadataDatabase(task_runner));
735  SyncStatusCode status =
736      metadata_database->InitializeOnTaskRunner(database_path);
737  if (status != SYNC_STATUS_OK)
738    metadata_database.reset();
739
740  callback_runner->PostTask(FROM_HERE, base::Bind(
741      callback, status, base::Passed(&metadata_database)));
742}
743
744// static
745SyncStatusCode MetadataDatabase::CreateForTesting(
746    scoped_ptr<leveldb::DB> db,
747    scoped_ptr<MetadataDatabase>* metadata_database_out) {
748  scoped_ptr<MetadataDatabase> metadata_database(
749      new MetadataDatabase(base::MessageLoopProxy::current()));
750  metadata_database->db_ = db.Pass();
751  SyncStatusCode status =
752      metadata_database->InitializeOnTaskRunner(base::FilePath());
753  if (status == SYNC_STATUS_OK)
754    *metadata_database_out = metadata_database.Pass();
755  return status;
756}
757
758SyncStatusCode MetadataDatabase::InitializeOnTaskRunner(
759    const base::FilePath& database_path) {
760  base::ThreadRestrictions::AssertIOAllowed();
761  DCHECK(task_runner_->RunsTasksOnCurrentThread());
762
763  SyncStatusCode status = SYNC_STATUS_UNKNOWN;
764  bool created = false;
765  // Open database unless |db_| is overridden for testing.
766  if (!db_) {
767    status = OpenDatabase(database_path, &db_, &created);
768    if (status != SYNC_STATUS_OK)
769      return status;
770  }
771
772  if (created) {
773    status = WriteVersionInfo(db_.get());
774    if (status != SYNC_STATUS_OK)
775      return status;
776  } else {
777    status = MigrateDatabaseIfNeeded(db_.get());
778    if (status != SYNC_STATUS_OK)
779      return status;
780  }
781
782  DatabaseContents contents;
783  status = ReadDatabaseContents(db_.get(), &contents);
784  if (status != SYNC_STATUS_OK)
785    return status;
786
787  leveldb::WriteBatch batch;
788  status = InitializeServiceMetadata(&contents, &batch);
789  if (status != SYNC_STATUS_OK)
790    return status;
791
792  status = RemoveUnreachableItems(&contents, &batch);
793  if (status != SYNC_STATUS_OK)
794    return status;
795
796  status = LevelDBStatusToSyncStatusCode(
797      db_->Write(leveldb::WriteOptions(), &batch));
798  if (status != SYNC_STATUS_OK)
799    return status;
800
801  BuildIndexes(&contents);
802  return status;
803}
804
805void MetadataDatabase::BuildIndexes(DatabaseContents* contents) {
806  service_metadata_ = contents->service_metadata.Pass();
807
808  for (ScopedVector<FileMetadata>::const_iterator itr =
809           contents->file_metadata.begin();
810       itr != contents->file_metadata.end();
811       ++itr) {
812    file_by_id_[(*itr)->file_id()] = *itr;
813  }
814  contents->file_metadata.weak_clear();
815
816  for (ScopedVector<FileTracker>::const_iterator itr =
817           contents->file_trackers.begin();
818       itr != contents->file_trackers.end();
819       ++itr) {
820    FileTracker* tracker = *itr;
821    tracker_by_id_[tracker->tracker_id()] = tracker;
822    trackers_by_file_id_[tracker->file_id()].Insert(tracker);
823
824    if (IsAppRoot(*tracker))
825      app_root_by_app_id_[tracker->app_id()] = tracker;
826
827    if (tracker->parent_tracker_id()) {
828      std::string title = GetTrackerTitle(*tracker);
829      TrackerSet* trackers =
830          &trackers_by_parent_and_title_[tracker->parent_tracker_id()][title];
831      trackers->Insert(tracker);
832    }
833
834    if (tracker->dirty())
835      dirty_trackers_.insert(tracker);
836  }
837  contents->file_trackers.weak_clear();
838}
839
840void MetadataDatabase::RegisterTrackerAsAppRoot(
841    const std::string& app_id,
842    int64 tracker_id,
843    leveldb::WriteBatch* batch) {
844  FileTracker* tracker = tracker_by_id_[tracker_id];
845  DCHECK(tracker);
846  tracker->set_app_id(app_id);
847  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
848  app_root_by_app_id_[app_id] = tracker;
849
850  MakeTrackerActive(tracker->tracker_id(), batch);
851}
852
853void MetadataDatabase::UnregisterTrackerAsAppRoot(
854    const std::string& app_id,
855    leveldb::WriteBatch* batch) {
856  FileTracker* tracker = FindAndEraseItem(&app_root_by_app_id_, app_id);
857  tracker->set_app_id(std::string());
858  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
859
860  // Inactivate the tracker to drop all descendant.
861  // (Note that we set tracker_kind to TRACKER_KIND_REGULAR before calling
862  // this.)
863  MakeTrackerInactive(tracker->tracker_id(), batch);
864}
865
866void MetadataDatabase::MakeTrackerActive(int64 tracker_id,
867                                         leveldb::WriteBatch* batch) {
868  FileTracker* tracker = tracker_by_id_[tracker_id];
869  DCHECK(tracker);
870  DCHECK(!tracker->active());
871
872  int64 parent_tracker_id = tracker->parent_tracker_id();
873  DCHECK(tracker->has_synced_details());
874  trackers_by_file_id_[tracker->file_id()].Activate(tracker);
875  if (parent_tracker_id) {
876    trackers_by_parent_and_title_[parent_tracker_id][
877        tracker->synced_details().title()].Activate(tracker);
878  }
879  tracker->set_active(true);
880  tracker->set_needs_folder_listing(
881      tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
882  tracker->set_dirty(true);
883  dirty_trackers_.insert(tracker);
884
885  PutTrackerToBatch(*tracker, batch);
886}
887
888void MetadataDatabase::MakeTrackerInactive(int64 tracker_id,
889                                           leveldb::WriteBatch* batch) {
890  FileTracker* tracker = tracker_by_id_[tracker_id];
891  DCHECK(tracker);
892  DCHECK(tracker->active());
893  DCHECK_EQ(TRACKER_KIND_REGULAR, tracker->tracker_kind());
894  trackers_by_file_id_[tracker->file_id()].Inactivate(tracker);
895
896  std::string title = GetTrackerTitle(*tracker);
897  int64 parent_tracker_id = tracker->parent_tracker_id();
898  if (parent_tracker_id)
899    trackers_by_parent_and_title_[parent_tracker_id][title].Inactivate(tracker);
900  tracker->set_active(false);
901
902  RemoveAllDescendantTrackers(tracker_id, batch);
903  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
904  if (parent_tracker_id)
905    MarkTrackersDirtyByPath(parent_tracker_id, title, batch);
906  PutTrackerToBatch(*tracker, batch);
907}
908
909void MetadataDatabase::MakeAppRootDisabled(int64 tracker_id,
910                                           leveldb::WriteBatch* batch) {
911  FileTracker* tracker = tracker_by_id_[tracker_id];
912  DCHECK(tracker);
913  DCHECK_EQ(TRACKER_KIND_APP_ROOT, tracker->tracker_kind());
914  DCHECK(tracker->active());
915
916  // Keep the app-root tracker active (but change the tracker_kind) so that
917  // other conflicting trackers won't become active.
918  tracker->set_tracker_kind(TRACKER_KIND_DISABLED_APP_ROOT);
919  PutTrackerToBatch(*tracker, batch);
920}
921
922void MetadataDatabase::MakeAppRootEnabled(int64 tracker_id,
923                                          leveldb::WriteBatch* batch) {
924  FileTracker* tracker = tracker_by_id_[tracker_id];
925  DCHECK(tracker);
926  DCHECK_EQ(TRACKER_KIND_DISABLED_APP_ROOT, tracker->tracker_kind());
927  DCHECK(tracker->active());
928
929  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
930  // Mark descendant trackers as dirty to handle changes in disable period.
931  RecursiveMarkTrackerAsDirty(tracker_id, batch);
932  PutTrackerToBatch(*tracker, batch);
933}
934
935void MetadataDatabase::CreateTrackerForParentAndFileID(
936    const FileTracker& parent_tracker,
937    const std::string& file_id,
938    leveldb::WriteBatch* batch) {
939  int64 tracker_id = GetNextTrackerID(batch);
940  scoped_ptr<FileTracker> tracker(new FileTracker);
941  tracker->set_tracker_id(tracker_id);
942  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
943  tracker->set_file_id(file_id);
944  tracker->set_app_id(parent_tracker.app_id());
945  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
946  tracker->set_dirty(true);
947  tracker->set_active(false);
948  tracker->set_needs_folder_listing(false);
949  PutTrackerToBatch(*tracker, batch);
950
951  trackers_by_file_id_[file_id].Insert(tracker.get());
952  // Note: |trackers_by_parent_and_title_| does not map from
953  // FileMetadata::details but from FileTracker::synced_details, which is filled
954  // on tracker updated phase.  Use empty string as the title since
955  // FileTracker::synced_details is empty here.
956  trackers_by_parent_and_title_[parent_tracker.tracker_id()][std::string()]
957      .Insert(tracker.get());
958  dirty_trackers_.insert(tracker.get());
959  DCHECK(!ContainsKey(tracker_by_id_, tracker_id));
960  tracker_by_id_[tracker_id] = tracker.release();
961}
962
963void MetadataDatabase::RemoveTrackerIgnoringSiblings(
964    int64 tracker_id,
965    leveldb::WriteBatch* batch) {
966  scoped_ptr<FileTracker> tracker(
967      FindAndEraseItem(&tracker_by_id_, tracker_id));
968  if (!tracker)
969    return;
970
971  EraseTrackerFromFileIDIndex(tracker.get(), batch);
972  if (IsAppRoot(*tracker))
973    app_root_by_app_id_.erase(tracker->app_id());
974  EraseTrackerFromPathIndex(tracker.get());
975
976  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
977  // Do not mark the same path trackers as dirty, since the caller is deleting
978  // all its siblings.
979  PutTrackerDeletionToBatch(tracker_id, batch);
980}
981
982void MetadataDatabase::MaybeAddTrackersForNewFile(
983    const FileMetadata& file,
984    leveldb::WriteBatch* batch) {
985  std::set<int64> known_parents;
986  TrackersByFileID::iterator found = trackers_by_file_id_.find(file.file_id());
987  if (found != trackers_by_file_id_.end()) {
988    for (TrackerSet::const_iterator itr = found->second.begin();
989         itr != found->second.end(); ++itr) {
990      int64 parent_tracker_id = (*itr)->parent_tracker_id();
991      if (parent_tracker_id)
992        known_parents.insert(parent_tracker_id);
993    }
994  }
995
996  for (int i = 0; i < file.details().parent_folder_ids_size(); ++i) {
997    std::string parent_folder_id = file.details().parent_folder_ids(i);
998    TrackersByFileID::iterator found =
999        trackers_by_file_id_.find(parent_folder_id);
1000    if (found == trackers_by_file_id_.end())
1001      continue;
1002
1003    for (TrackerSet::const_iterator itr = found->second.begin();
1004         itr != found->second.end(); ++itr) {
1005      FileTracker* parent_tracker = *itr;
1006      int64 parent_tracker_id = parent_tracker->tracker_id();
1007      if (!parent_tracker->active())
1008        continue;
1009
1010      if (ContainsKey(known_parents, parent_tracker_id))
1011        continue;
1012
1013      CreateTrackerForParentAndFileID(*parent_tracker, file.file_id(), batch);
1014    }
1015  }
1016}
1017
1018void MetadataDatabase::RemoveAllDescendantTrackers(int64 root_tracker_id,
1019                                                   leveldb::WriteBatch* batch) {
1020  std::vector<int64> pending_trackers;
1021  PushChildTrackersToContainer(trackers_by_parent_and_title_,
1022                               root_tracker_id,
1023                               std::back_inserter(pending_trackers));
1024
1025  while (!pending_trackers.empty()) {
1026    int64 tracker_id = pending_trackers.back();
1027    pending_trackers.pop_back();
1028    PushChildTrackersToContainer(trackers_by_parent_and_title_,
1029                                 tracker_id,
1030                                 std::back_inserter(pending_trackers));
1031    RemoveTrackerIgnoringSiblings(tracker_id, batch);
1032  }
1033}
1034
1035void MetadataDatabase::EraseTrackerFromFileIDIndex(FileTracker* tracker,
1036                                                   leveldb::WriteBatch* batch) {
1037  TrackersByFileID::iterator found =
1038      trackers_by_file_id_.find(tracker->file_id());
1039  if (found == trackers_by_file_id_.end())
1040    return;
1041
1042  TrackerSet* trackers = &found->second;
1043  trackers->Erase(tracker);
1044  if (!trackers->tracker_set().empty())
1045    return;
1046  trackers_by_file_id_.erase(found);
1047  EraseFileFromDatabase(tracker->file_id(), batch);
1048}
1049
1050void MetadataDatabase::EraseFileFromDatabase(const std::string& file_id,
1051                                             leveldb::WriteBatch* batch) {
1052  scoped_ptr<FileMetadata> file(FindAndEraseItem(&file_by_id_, file_id));
1053  if (file)
1054    PutFileDeletionToBatch(file_id, batch);
1055}
1056
1057void MetadataDatabase::EraseTrackerFromPathIndex(FileTracker* tracker) {
1058  TrackersByParentAndTitle::iterator found =
1059      trackers_by_parent_and_title_.find(tracker->parent_tracker_id());
1060  if (found == trackers_by_parent_and_title_.end())
1061    return;
1062
1063  std::string title = GetTrackerTitle(*tracker);
1064  TrackersByTitle* trackers_by_title = &found->second;
1065  TrackersByTitle::iterator found_by_title = trackers_by_title->find(title);
1066  TrackerSet* conflicting_trackers = &found_by_title->second;
1067  conflicting_trackers->Erase(tracker);
1068
1069  if (conflicting_trackers->tracker_set().empty()) {
1070    trackers_by_title->erase(found_by_title);
1071    if (trackers_by_title->empty())
1072      trackers_by_parent_and_title_.erase(found);
1073  }
1074}
1075
1076void MetadataDatabase::MarkTrackerSetDirty(
1077    TrackerSet* trackers,
1078    leveldb::WriteBatch* batch) {
1079  for (TrackerSet::iterator itr = trackers->begin();
1080       itr != trackers->end(); ++itr) {
1081    FileTracker* tracker = *itr;
1082    if (tracker->dirty())
1083      continue;
1084    tracker->set_dirty(true);
1085    PutTrackerToBatch(*tracker, batch);
1086    dirty_trackers_.insert(tracker);
1087  }
1088}
1089
1090void MetadataDatabase::MarkTrackersDirtyByFileID(
1091    const std::string& file_id,
1092    leveldb::WriteBatch* batch) {
1093  TrackersByFileID::iterator found = trackers_by_file_id_.find(file_id);
1094  if (found != trackers_by_file_id_.end())
1095    MarkTrackerSetDirty(&found->second, batch);
1096}
1097
1098void MetadataDatabase::MarkTrackersDirtyByPath(int64 parent_tracker_id,
1099                                               const std::string& title,
1100                                               leveldb::WriteBatch* batch) {
1101  TrackersByParentAndTitle::iterator found =
1102      trackers_by_parent_and_title_.find(parent_tracker_id);
1103  if (found == trackers_by_parent_and_title_.end()) {
1104    NOTREACHED() << "parent: " << parent_tracker_id
1105                 << ", title: " << title;
1106    return;
1107  }
1108
1109  TrackersByTitle::iterator itr = found->second.find(title);
1110  if (itr != found->second.end())
1111    MarkTrackerSetDirty(&itr->second, batch);
1112}
1113
1114int64 MetadataDatabase::GetNextTrackerID(leveldb::WriteBatch* batch) {
1115  int64 tracker_id = service_metadata_->next_tracker_id();
1116  service_metadata_->set_next_tracker_id(tracker_id + 1);
1117  PutServiceMetadataToBatch(*service_metadata_, batch);
1118  DCHECK_GT(tracker_id, 0);
1119  return tracker_id;
1120}
1121
1122void MetadataDatabase::RecursiveMarkTrackerAsDirty(int64 root_tracker_id,
1123                                                   leveldb::WriteBatch* batch) {
1124  std::vector<int64> stack;
1125  stack.push_back(root_tracker_id);
1126  while (!stack.empty()) {
1127    int64 tracker_id = stack.back();
1128    stack.pop_back();
1129    PushChildTrackersToContainer(
1130        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
1131
1132    FileTracker* tracker = tracker_by_id_[tracker_id];
1133    if (!tracker->dirty()) {
1134      tracker->set_dirty(true);
1135      PutTrackerToBatch(*tracker, batch);
1136      dirty_trackers_.insert(tracker);
1137    }
1138  }
1139}
1140
1141bool MetadataDatabase::ShouldKeepDirty(const FileTracker& tracker) const {
1142  DCHECK(tracker.dirty());
1143  if (!tracker.has_synced_details())
1144    return true;
1145
1146  FileByID::const_iterator found = file_by_id_.find(tracker.file_id());
1147  if (found == file_by_id_.end())
1148    return true;
1149  const FileMetadata& file = *found->second;
1150
1151  if (tracker.active()) {
1152    if (tracker.needs_folder_listing())
1153      return true;
1154    if (tracker.synced_details().md5() != file.details().md5())
1155      return true;
1156  }
1157
1158  const FileDetails& local_details = tracker.synced_details();
1159  const FileDetails& remote_details = file.details();
1160
1161  if (local_details.title() != remote_details.title())
1162    return true;
1163  if (local_details.deleted() != remote_details.deleted())
1164    return true;
1165
1166  return false;
1167}
1168
1169void MetadataDatabase::WriteToDatabase(scoped_ptr<leveldb::WriteBatch> batch,
1170                                       const SyncStatusCallback& callback) {
1171  base::PostTaskAndReplyWithResult(
1172      task_runner_.get(),
1173      FROM_HERE,
1174      base::Bind(&leveldb::DB::Write,
1175                 base::Unretained(db_.get()),
1176                 leveldb::WriteOptions(),
1177                 base::Owned(batch.release())),
1178      base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
1179}
1180
1181}  // namespace drive_backend
1182}  // namespace sync_file_system
1183