[SyncFS] Implement MetadataDatabase initialization

chrome/browser/sync_file_system/drive_backend/metadata_database.cc

Index: chrome/browser/sync_file_system/drive_backend/metadata_database.cc
diff --git a/chrome/browser/sync_file_system/drive_backend/metadata_database.cc b/chrome/browser/sync_file_system/drive_backend/metadata_database.cc
index 6e52b5110d23e289cfa98ec38ddb45462efbf08a..c7ac9d677d3a72c417166850a02fee201d244a6a 100644
--- a/chrome/browser/sync_file_system/drive_backend/metadata_database.cc
+++ b/chrome/browser/sync_file_system/drive_backend/metadata_database.cc
@@ -4,26 +4,135 @@
 
 #include "chrome/browser/sync_file_system/drive_backend/metadata_database.h"
 
+#include <stack>
+
+#include "base/bind.h"
+#include "base/callback.h"
+#include "base/files/file_path.h"
+#include "base/location.h"
+#include "base/memory/scoped_vector.h"
+#include "base/sequenced_task_runner.h"
+#include "base/stl_util.h"
+#include "base/strings/string_number_conversions.h"
+#include "base/strings/string_util.h"
+#include "base/strings/stringprintf.h"
+#include "base/task_runner_util.h"
+#include "base/threading/thread_restrictions.h"
 #include "chrome/browser/google_apis/drive_api_parser.h"
+#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
+#include "chrome/browser/sync_file_system/drive_backend/metadata_db_migration_util.h"
+#include "third_party/leveldatabase/src/include/leveldb/db.h"
+#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
+#include "webkit/browser/fileapi/syncable/syncable_file_system_util.h"
+#include "webkit/common/fileapi/file_system_util.h"
 
 namespace sync_file_system {
 namespace drive_backend {
 
-MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner) {
-  NOTIMPLEMENTED();
+typedef MetadataDatabase::FileByFileID FileByFileID;
+typedef MetadataDatabase::FileByAppID FileByAppID;
+typedef MetadataDatabase::FilesByParent FilesByParent;
+typedef MetadataDatabase::FileByParentAndTitle FileByParentAndTitle;
+typedef MetadataDatabase::InitializeInfo InitializeInfo;
+
+const char* MetadataDatabase::kDatabaseVersionKey = "VERSION";
+const int64 MetadataDatabase::kCurrentDatabaseVersion = 3;
+const char* MetadataDatabase::kServiceMetadataKey = "SERVICE";
+const char* MetadataDatabase::kFileMetadataKeyPrefix = "FILE: ";
+
+namespace {
+
+std::string RemovePrefix(const std::string& str, const std::string& prefix) {
+  if (StartsWithASCII(str, prefix, true))
+    return str.substr(prefix.size());
+  return str;
+}
+
+void AdaptLevelDBStatusToSyncStatusCode(const SyncStatusCallback& callback,
+                                        const leveldb::Status& status) {
+  callback.Run(LevelDBStatusToSyncStatusCode(status));
+}
+
+// Returns true if |db| has no content.
+bool IsDBEmpty(leveldb::DB* db) {
+  DCHECK(db);
+  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
+  itr->SeekToFirst();
+  return !itr->Valid();
+}
+
+template <typename Container, typename Key, typename Value>
+bool FindItem(const Container& container, const Key& key, Value* value) {
+  typename Container::const_iterator found = container.find(key);
+  if (found == container.end())
+    return false;
+  if (value)
+    *value = *found->second;
+  return true;
+}
+
+}  // namespace
+
+bool MetadataDatabase::FileIDComparator::operator()(DriveFileMetadata* left,
+                                                    DriveFileMetadata* right) {
+  return left->file_id() < right->file_id();
+}
+
+MetadataDatabase::InitializeInfo::InitializeInfo()
+    : status(SYNC_STATUS_UNKNOWN),
+      created(false) {
+}
+
+MetadataDatabase::InitializeInfo::~InitializeInfo() {}
+
+MetadataDatabase::MetadataDatabase(
+    base::SequencedTaskRunner* task_runner)
+    : task_runner_(task_runner),
+      weak_ptr_factory_(this) {
+  DCHECK(task_runner);
 }
 
 MetadataDatabase::~MetadataDatabase() {
+  task_runner_->DeleteSoon(FROM_HERE, db_.release());
+  STLDeleteContainerPairSecondPointers(
+      file_by_file_id_.begin(), file_by_file_id_.end());
 }
 
 void MetadataDatabase::Initialize(const base::FilePath& database_dir,
                                   const SyncStatusCallback& callback) {
-  NOTIMPLEMENTED();
+  base::PostTaskAndReplyWithResult(
+      task_runner_.get(), FROM_HERE,
+      base::Bind(&InitializeOnWorker, database_dir),
+      base::Bind(&MetadataDatabase::DidInitialize,
+                 weak_ptr_factory_.GetWeakPtr(),
+                 callback));
+}
+
+void MetadataDatabase::DidInitialize(const SyncStatusCallback& callback,
+                                     scoped_ptr<InitializeInfo> info) {
+  DCHECK(info);
+
+  if (info->status != SYNC_STATUS_OK) {
+    callback.Run(info->status);
+    return;
+  }
+
+  db_ = info->db.Pass();
+
+  // After these two, |file_by_file_id_| owns all DriveFileMetadata instances.
+  info->file_metadata.weak_clear();
+  file_by_file_id_.swap(info->file_by_file_id);
+
+  files_by_parent_.swap(info->files_by_parent);
+  app_root_by_app_id_.swap(info->app_root_by_app_id);
+  active_file_by_parent_and_title_.swap(
+      info->active_file_by_parent_and_title);
+
+  callback.Run(info->status);
 }
 
 int64 MetadataDatabase::GetLargestChangeID() const {
-  NOTIMPLEMENTED();
-  return 0;
+  return service_metadata_->largest_change_id();
 }
 
 void MetadataDatabase::RegisterApp(const std::string& app_id,
@@ -49,14 +158,12 @@ void MetadataDatabase::UnregisterApp(const std::string& app_id,
 
 bool MetadataDatabase::FindAppRootFolder(const std::string& app_id,
                                          DriveFileMetadata* folder) const {
-  NOTIMPLEMENTED();
-  return false;
+  return FindItem(app_root_by_app_id_, app_id, folder);
 }
 
 bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
                                         DriveFileMetadata* metadata) const {
-  NOTIMPLEMENTED();
-  return false;
+  return FindItem(file_by_file_id_, file_id, metadata);
 }
 
 size_t MetadataDatabase::FindFilesByParentAndTitle(
@@ -71,21 +178,46 @@ bool MetadataDatabase::FindActiveFileByParentAndTitle(
     const std::string& folder_id,
     const std::string& title,
     DriveFileMetadata* file) const {
-  NOTIMPLEMENTED();
-  return false;
+  return FindItem(active_file_by_parent_and_title_,
+                  std::make_pair(folder_id, title),
+                  file);
 }
 
 bool MetadataDatabase::FindActiveFileByPath(const std::string& app_id,
                                             const base::FilePath& path,
                                             DriveFileMetadata* file) const {
-  NOTIMPLEMENTED();
-  return false;
+  DriveFileMetadata current;
+  if (!FindAppRootFolder(app_id, &current))
+    return false;
+
+  std::vector<base::FilePath::StringType> components;
+  path.GetComponents(&components);
+
+  std::string parent_folder_id = current.file_id();
+  for (std::vector<base::FilePath::StringType>::iterator itr =
+           components.begin();
+       itr != components.end();
+       ++itr) {
+    std::string current_folder_id = current.file_id();
+    if (!FindActiveFileByParentAndTitle(current_folder_id, *itr, &current))
+      return false;
+  }
+  if (file)
+    *file = current;
+  return true;
 }
 
 bool MetadataDatabase::ConstructPathForFile(const std::string& file_id,
                                             base::FilePath* path) const {
+  DriveFileMetadata current;
+  if (!FindFileByFileID(file_id, &current) || !current.active())
+    return false;
+
+  std::vector<base::FilePath> components;
+  base::FilePath::StringType concat;
   NOTIMPLEMENTED();
-  return false;
+
+  return true;
 }
 
 void MetadataDatabase::UpdateByChangeList(
@@ -101,5 +233,250 @@ void MetadataDatabase::PopulateFolder(
   NOTIMPLEMENTED();
 }
 
+scoped_ptr<leveldb::DB> MetadataDatabase::OpenDatabase(
+    const base::FilePath& path,
+    SyncStatusCode* status,
+    bool* created) {
+  base::ThreadRestrictions::AssertIOAllowed();
+  DCHECK(status);
+  DCHECK(created);
+
+  leveldb::Options options;
+  options.create_if_missing = true;
+  leveldb::DB* db = NULL;
+  leveldb::Status db_status = leveldb::DB::Open(
+      options, path.AsUTF8Unsafe(), &db);
+  if (db_status.ok()) {
+    *created = IsDBEmpty(db);
+  } else {
+    delete db;
+    db = NULL;
+  }
+  *status = LevelDBStatusToSyncStatusCode(db_status);
+
+  return make_scoped_ptr(db);
+}
+
+SyncStatusCode MetadataDatabase::WriteInitialData(leveldb::DB* db) {

[kinuko, 2013/07/04 15:59:11]

nit: could we name it WriteVersionInfo to make it as straightforward as
possible?

[tzik, 2013/07/05 07:42:28]

Done.

+  base::ThreadRestrictions::AssertIOAllowed();
+  DCHECK(db);
+  return LevelDBStatusToSyncStatusCode(db->Put(
+      leveldb::WriteOptions(),
+      kDatabaseVersionKey,
+      base::Int64ToString(kCurrentDatabaseVersion)));
+}
+
+SyncStatusCode MetadataDatabase::MigrateDatabaseIfNeeded(leveldb::DB* db) {
+  base::ThreadRestrictions::AssertIOAllowed();
+  DCHECK(db);
+  std::string value;
+  leveldb::Status status = db->Get(leveldb::ReadOptions(),
+                                   kDatabaseVersionKey, &value);
+  int64 version = 0;
+  if (status.ok()) {
+    if (!base::StringToInt64(value, &version))
+      return SYNC_DATABASE_ERROR_FAILED;
+  } else {
+    if (!status.IsNotFound())
+      return SYNC_DATABASE_ERROR_FAILED;
+  }
+
+  switch (version) {
+    case 0:
+      drive_backend::MigrateDatabaseFromV0ToV1(db);
+      // fall-through
+    case 1:
+      drive_backend::MigrateDatabaseFromV1ToV2(db);
+      // fall-through
+    case 2:
+      NOTIMPLEMENTED();
+      return SYNC_DATABASE_ERROR_FAILED;
+      // fall-through
+    case 3:
+      DCHECK_EQ(3, kCurrentDatabaseVersion);
+      return SYNC_STATUS_OK;
+    default:
+      return SYNC_DATABASE_ERROR_FAILED;
+  }
+}
+
+SyncStatusCode MetadataDatabase::ReadDatabaseContents(leveldb::DB* db,
+                                                      InitializeInfo* info) {
+  base::ThreadRestrictions::AssertIOAllowed();
+  DCHECK(db);
+  DCHECK(info);
+
+  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
+  for (itr->SeekToFirst(); itr->Valid(); itr->Next()) {
+    std::string key = itr->key().ToString();
+    std::string value = itr->value().ToString();
+    if (key == kServiceMetadataKey) {
+      scoped_ptr<ServiceMetadata> service_metadata(
+          new ServiceMetadata);
+      if (!service_metadata->ParseFromString(value)) {
+        LOG(WARNING) << "Failed to parse SyncServiceMetadata";

[kinuko, 2013/07/04 15:59:11]

Use logger?

[tzik, 2013/07/05 07:42:28]

Done.

+        continue;
+      }
+
+      info->service_metadata = service_metadata.Pass();
+      continue;
+    }
+
+    if (StartsWithASCII(key, kFileMetadataKeyPrefix, true)) {
+      std::string file_id = RemovePrefix(key, kFileMetadataKeyPrefix);
+
+      scoped_ptr<DriveFileMetadata> metadata(new DriveFileMetadata);
+      if (!metadata->ParseFromString(itr->value().ToString())) {
+        LOG(WARNING) << "Failed to parse a Metadata";

[kinuko, 2013/07/04 15:59:11]

ditto

[tzik, 2013/07/05 07:42:28]

Done.

+        continue;
+      }
+
+      info->file_metadata.push_back(metadata.release());
+      continue;
+    }
+  }
+
+  return SYNC_STATUS_OK;
+}
+
+SyncStatusCode MetadataDatabase::ConstructDataStructure(
+    InitializeInfo* info,
+    leveldb::WriteBatch* batch) {
+  FileByFileID file_by_file_id;
+  FilesByParent files_by_parent;
+
+  // Populate |file_by_file_id| and |files_by_parent|.
+  for (ScopedVector<DriveFileMetadata>::iterator itr =
+           info->file_metadata.begin();
+       itr != info->file_metadata.end();
+       ++itr) {
+    DriveFileMetadata* metadata = *itr;
+    DCHECK(!ContainsKey(file_by_file_id, metadata->file_id()));
+    file_by_file_id[metadata->file_id()] = metadata;
+    files_by_parent[metadata->parent_folder_id()].insert(metadata);
+  }
+
+  if (!info->service_metadata) {
+    info->service_metadata.reset(new ServiceMetadata);
+
+    std::string value;
+    info->service_metadata->SerializeToString(&value);
+    batch->Put(kServiceMetadataKey, value);
+  }
+
+  // Traverse synced metadata tree. Take only active items and their children.
+  // Drop unreachable items.
+  ScopedVector<DriveFileMetadata> reachable_files;
+  std::stack<std::string> pending;
+  if (!info->service_metadata->sync_root_folder_id().empty())
+    pending.push(info->service_metadata->sync_root_folder_id());
+
+  while (!pending.empty()) {
+    std::string file_id = pending.top();
+    pending.pop();
+
+    {
+      FileByFileID::iterator found = file_by_file_id.find(file_id);
+      if (found == file_by_file_id.end())
+        continue;
+
+      DriveFileMetadata* metadata = found->second;
+      // Move reachable files from |file_by_file_id| to |reachable_files|.
+      file_by_file_id.erase(found);
+      reachable_files.push_back(metadata);
+
+      // Populate in-memory caches for Metadata here including
+      // files_by_app, dirty_files, active_file_by_parent_and_title.
+      info->file_by_file_id[file_id] = metadata;
+      if (metadata->is_app_root())
+        info->app_root_by_app_id[metadata->app_id()] = metadata;
+      if (metadata->active() && metadata->has_synced_details()) {
+        FileByParentAndTitle::key_type key =
+            std::make_pair(metadata->parent_folder_id(),
+                           metadata->synced_details().title());
+        info->active_file_by_parent_and_title[key] = metadata;
+      }
+
+      if (!metadata->parent_folder_id().empty())
+        info->files_by_parent[metadata->parent_folder_id()].insert(metadata);
+
+      if (!metadata->active())
+        continue;
+    }
+
+    FilesByParent::iterator found = files_by_parent.find(file_id);
+    if (found == files_by_parent.end())
+      continue;
+
+    for (std::set<DriveFileMetadata*>::iterator itr = found->second.begin();
+         itr != found->second.end(); ++itr)
+      pending.push((*itr)->file_id());
+  }
+
+  // |file_by_file_id| holds unreachable files here.
+  for (FileByFileID::iterator itr = file_by_file_id.begin();
+       itr != file_by_file_id.end(); ++itr) {
+    DriveFileMetadata* metadata = itr->second;
+    batch->Delete(metadata->file_id());
+    delete metadata;
+  }
+  file_by_file_id.clear();
+
+  // |reachable_files| contains all files/folders reachable from sync-root
+  // folder via active folders.  |info->file_metadata| contains unreachable
+  // files/folders at this point.
+  info->file_metadata.weak_clear();
+  info->file_metadata.swap(reachable_files);
+
+  return SYNC_STATUS_OK;
+}
+
+scoped_ptr<InitializeInfo> MetadataDatabase::InitializeOnWorker(

[kinuko, 2013/07/04 15:59:11]

nit: OnWorker -> OnTaskRunner or something

(What Worker means is not clear)

[tzik, 2013/07/05 07:42:28]

Done.

+    const base::FilePath& db_path) {
+  base::ThreadRestrictions::AssertIOAllowed();
+
+  scoped_ptr<InitializeInfo> info(new InitializeInfo);
+  info->db = OpenDatabase(db_path,
+                              &info->status,
+                              &info->created);

[kinuko, 2013/07/04 15:59:11]

indent

[tzik, 2013/07/05 07:42:28]

Done.

+  if (info->status != SYNC_STATUS_OK)
+    return info.Pass();
+
+  if (info->created) {
+    info->status = WriteInitialData(info->db.get());
+    if (info->status != SYNC_STATUS_OK)
+      return info.Pass();
+  } else {
+    info->status = MigrateDatabaseIfNeeded(info->db.get());
+    if (info->status != SYNC_STATUS_OK)
+      return info.Pass();
+  }
+
+  info->status = ReadDatabaseContents(info->db.get(), info.get());
+  if (info->status != SYNC_STATUS_OK)
+    return info.Pass();
+
+  leveldb::WriteBatch batch;
+  info->status = ConstructDataStructure(info.get(), &batch);
+  if (info->status != SYNC_STATUS_OK)
+    return info.Pass();
+
+  info->status = LevelDBStatusToSyncStatusCode(
+      info->db->Write(leveldb::WriteOptions(), &batch));
+  return info.Pass();
+}
+
+void MetadataDatabase::WriteToDB(scoped_ptr<leveldb::WriteBatch> batch,
+                                   const SyncStatusCallback& callback) {

[kinuko, 2013/07/04 15:59:11]

indent

[tzik, 2013/07/05 07:42:28]

Done.

+  base::PostTaskAndReplyWithResult(
+      task_runner_.get(),
+      FROM_HERE,
+      base::Bind(&leveldb::DB::Write,
+                 base::Unretained(db_.get()),
+                 leveldb::WriteOptions(),
+                 base::Owned(batch.release())),
+      base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
+}
+
 }  // namespace drive_backend
 }  // namespace sync_file_system