chrome/browser/sync_file_system/drive_backend/metadata_database.cc

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