metadata_database.cc revision 1e9bf3e0803691d0a228da41fc608347b6db4340 
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/files/file_path.h"
13#include "base/location.h"
14#include "base/memory/scoped_vector.h"
15#include "base/message_loop/message_loop_proxy.h"
16#include "base/sequenced_task_runner.h"
17#include "base/stl_util.h"
18#include "base/strings/string_number_conversions.h"
19#include "base/strings/string_util.h"
20#include "base/strings/stringprintf.h"
21#include "base/task_runner_util.h"
22#include "base/threading/thread_restrictions.h"
23#include "chrome/browser/drive/drive_api_util.h"
24#include "chrome/browser/google_apis/drive_api_parser.h"
25#include "chrome/browser/google_apis/drive_entry_kinds.h"
26#include "chrome/browser/sync_file_system/drive_backend/drive_backend_constants.h"
27#include "chrome/browser/sync_file_system/drive_backend/drive_backend_util.h"
28#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
29#include "chrome/browser/sync_file_system/drive_backend/metadata_db_migration_util.h"
30#include "chrome/browser/sync_file_system/logger.h"
31#include "chrome/browser/sync_file_system/syncable_file_system_util.h"
32#include "third_party/leveldatabase/src/include/leveldb/db.h"
33#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
34#include "webkit/common/fileapi/file_system_util.h"
35
36namespace sync_file_system {
37namespace drive_backend {
38
39struct DatabaseContents {
40  scoped_ptr<ServiceMetadata> service_metadata;
41  ScopedVector<FileMetadata> file_metadata;
42  ScopedVector<FileTracker> file_trackers;
43};
44
45namespace {
46
47typedef MetadataDatabase::FileByID FileByID;
48typedef MetadataDatabase::TrackerByID TrackerByID;
49typedef MetadataDatabase::TrackersByParentAndTitle TrackersByParentAndTitle;
50typedef MetadataDatabase::TrackersByTitle TrackersByTitle;
51
52bool IsAppRoot(const FileTracker& tracker) {
53  return tracker.tracker_kind() == TRACKER_KIND_APP_ROOT ||
54      tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
55}
56
57std::string RemovePrefix(const std::string& str, const std::string& prefix) {
58  if (StartsWithASCII(str, prefix, true))
59    return str.substr(prefix.size());
60  return str;
61}
62
63base::FilePath ReverseConcatPathComponents(
64    const std::vector<base::FilePath>& components) {
65  if (components.empty())
66    return base::FilePath(FILE_PATH_LITERAL("/")).NormalizePathSeparators();
67
68  size_t total_size = 0;
69  typedef std::vector<base::FilePath> PathComponents;
70  for (PathComponents::const_iterator itr = components.begin();
71       itr != components.end(); ++itr)
72    total_size += itr->value().size() + 1;
73
74  base::FilePath::StringType result;
75  result.reserve(total_size);
76  for (PathComponents::const_reverse_iterator itr = components.rbegin();
77       itr != components.rend(); ++itr) {
78    result.append(1, base::FilePath::kSeparators[0]);
79    result.append(itr->value());
80  }
81
82  return base::FilePath(result).NormalizePathSeparators();
83}
84
85void CreateInitialSyncRootTracker(
86    int64 tracker_id,
87    const google_apis::FileResource& file_resource,
88    scoped_ptr<FileMetadata>* file_out,
89    scoped_ptr<FileTracker>* tracker_out) {
90  FileDetails details;
91  PopulateFileDetailsByFileResource(file_resource, &details);
92
93  scoped_ptr<FileMetadata> file(new FileMetadata);
94  file->set_file_id(file_resource.file_id());
95  *file->mutable_details() = details;
96
97  scoped_ptr<FileTracker> tracker(new FileTracker);
98  tracker->set_tracker_id(tracker_id);
99  tracker->set_file_id(file_resource.file_id());
100  tracker->set_parent_tracker_id(0);
101  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
102  tracker->set_dirty(false);
103  tracker->set_active(true);
104  tracker->set_needs_folder_listing(false);
105  *tracker->mutable_synced_details() = details;
106
107  *file_out = file.Pass();
108  *tracker_out = tracker.Pass();
109}
110
111void CreateInitialAppRootTracker(
112    int64 tracker_id,
113    const FileTracker& parent_tracker,
114    const google_apis::FileResource& file_resource,
115    scoped_ptr<FileMetadata>* file_out,
116    scoped_ptr<FileTracker>* tracker_out) {
117  FileDetails details;
118  PopulateFileDetailsByFileResource(file_resource, &details);
119
120  scoped_ptr<FileMetadata> file(new FileMetadata);
121  file->set_file_id(file_resource.file_id());
122  *file->mutable_details() = details;
123
124  scoped_ptr<FileTracker> tracker(new FileTracker);
125  tracker->set_tracker_id(tracker_id);
126  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
127  tracker->set_file_id(file_resource.file_id());
128  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
129  tracker->set_dirty(false);
130  tracker->set_active(false);
131  tracker->set_needs_folder_listing(false);
132  *tracker->mutable_synced_details() = details;
133
134  *file_out = file.Pass();
135  *tracker_out = tracker.Pass();
136}
137
138void AdaptLevelDBStatusToSyncStatusCode(const SyncStatusCallback& callback,
139                                        const leveldb::Status& status) {
140  callback.Run(LevelDBStatusToSyncStatusCode(status));
141}
142
143void PutFileDeletionToBatch(const std::string& file_id,
144                            leveldb::WriteBatch* batch) {
145  batch->Delete(kFileMetadataKeyPrefix + file_id);
146}
147
148void PutTrackerDeletionToBatch(int64 tracker_id, leveldb::WriteBatch* batch) {
149  batch->Delete(kFileTrackerKeyPrefix + base::Int64ToString(tracker_id));
150}
151
152template <typename OutputIterator>
153OutputIterator PushChildTrackersToContainer(
154    const TrackersByParentAndTitle& trackers_by_parent,
155    int64 parent_tracker_id,
156    OutputIterator target_itr) {
157  TrackersByParentAndTitle::const_iterator found =
158      trackers_by_parent.find(parent_tracker_id);
159  if (found == trackers_by_parent.end())
160    return target_itr;
161
162  for (TrackersByTitle::const_iterator title_itr = found->second.begin();
163       title_itr != found->second.end(); ++title_itr) {
164    const TrackerSet& trackers = title_itr->second;
165    for (TrackerSet::const_iterator tracker_itr = trackers.begin();
166         tracker_itr != trackers.end(); ++tracker_itr) {
167      *target_itr = (*tracker_itr)->tracker_id();
168      ++target_itr;
169    }
170  }
171  return target_itr;
172}
173
174std::string GetTrackerTitle(const FileTracker& tracker) {
175  if (tracker.has_synced_details())
176    return tracker.synced_details().title();
177  return std::string();
178}
179
180// Returns true if |db| has no content.
181bool IsDatabaseEmpty(leveldb::DB* db) {
182  DCHECK(db);
183  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
184  itr->SeekToFirst();
185  return !itr->Valid();
186}
187
188SyncStatusCode OpenDatabase(const base::FilePath& path,
189                            scoped_ptr<leveldb::DB>* db_out,
190                            bool* created) {
191  base::ThreadRestrictions::AssertIOAllowed();
192  DCHECK(db_out);
193  DCHECK(created);
194
195  leveldb::Options options;
196  options.max_open_files = 0;  // Use minimum.
197  options.create_if_missing = true;
198  leveldb::DB* db = NULL;
199  leveldb::Status db_status =
200      leveldb::DB::Open(options, path.AsUTF8Unsafe(), &db);
201  SyncStatusCode status = LevelDBStatusToSyncStatusCode(db_status);
202  if (status != SYNC_STATUS_OK) {
203    delete db;
204    return status;
205  }
206
207  *created = IsDatabaseEmpty(db);
208  db_out->reset(db);
209  return status;
210}
211
212SyncStatusCode MigrateDatabaseIfNeeded(leveldb::DB* db) {
213  base::ThreadRestrictions::AssertIOAllowed();
214  DCHECK(db);
215  std::string value;
216  leveldb::Status status =
217      db->Get(leveldb::ReadOptions(), kDatabaseVersionKey, &value);
218  int64 version = 0;
219  if (status.ok()) {
220    if (!base::StringToInt64(value, &version))
221      return SYNC_DATABASE_ERROR_FAILED;
222  } else {
223    if (!status.IsNotFound())
224      return SYNC_DATABASE_ERROR_FAILED;
225  }
226
227  switch (version) {
228    case 0:
229      drive_backend::MigrateDatabaseFromV0ToV1(db);
230      // fall-through
231    case 1:
232      drive_backend::MigrateDatabaseFromV1ToV2(db);
233      // fall-through
234    case 2:
235      // TODO(tzik): Migrate database from version 2 to 3.
236      //   * Add sync-root folder as active, dirty and needs_folder_listing
237      //     folder.
238      //   * Add app-root folders for each origins.  Each app-root folder for
239      //     an enabled origin should be a active, dirty and
240      //     needs_folder_listing folder.  And Each app-root folder for a
241      //     disabled origin should be an inactive, dirty and
242      //     non-needs_folder_listing folder.
243      //   * Add a file metadata for each file in previous version.
244      NOTIMPLEMENTED();
245      return SYNC_DATABASE_ERROR_FAILED;
246      // fall-through
247    case 3:
248      DCHECK_EQ(3, kCurrentDatabaseVersion);
249      return SYNC_STATUS_OK;
250    default:
251      return SYNC_DATABASE_ERROR_FAILED;
252  }
253}
254
255SyncStatusCode WriteVersionInfo(leveldb::DB* db) {
256  base::ThreadRestrictions::AssertIOAllowed();
257  DCHECK(db);
258  return LevelDBStatusToSyncStatusCode(
259      db->Put(leveldb::WriteOptions(),
260              kDatabaseVersionKey,
261              base::Int64ToString(kCurrentDatabaseVersion)));
262}
263
264SyncStatusCode ReadDatabaseContents(leveldb::DB* db,
265                                    DatabaseContents* contents) {
266  base::ThreadRestrictions::AssertIOAllowed();
267  DCHECK(db);
268  DCHECK(contents);
269
270  scoped_ptr<leveldb::Iterator> itr(db->NewIterator(leveldb::ReadOptions()));
271  for (itr->SeekToFirst(); itr->Valid(); itr->Next()) {
272    std::string key = itr->key().ToString();
273    std::string value = itr->value().ToString();
274    if (key == kServiceMetadataKey) {
275      scoped_ptr<ServiceMetadata> service_metadata(new ServiceMetadata);
276      if (!service_metadata->ParseFromString(value)) {
277        util::Log(logging::LOG_WARNING, FROM_HERE,
278                  "Failed to parse SyncServiceMetadata");
279        continue;
280      }
281
282      contents->service_metadata = service_metadata.Pass();
283      continue;
284    }
285
286    if (StartsWithASCII(key, kFileMetadataKeyPrefix, true)) {
287      std::string file_id = RemovePrefix(key, kFileMetadataKeyPrefix);
288
289      scoped_ptr<FileMetadata> file(new FileMetadata);
290      if (!file->ParseFromString(itr->value().ToString())) {
291        util::Log(logging::LOG_WARNING, FROM_HERE,
292                  "Failed to parse a FileMetadata");
293        continue;
294      }
295
296      contents->file_metadata.push_back(file.release());
297      continue;
298    }
299
300    if (StartsWithASCII(key, kFileTrackerKeyPrefix, true)) {
301      int64 tracker_id = 0;
302      if (!base::StringToInt64(RemovePrefix(key, kFileTrackerKeyPrefix),
303                               &tracker_id)) {
304        util::Log(logging::LOG_WARNING, FROM_HERE,
305                  "Failed to parse TrackerID");
306        continue;
307      }
308
309      scoped_ptr<FileTracker> tracker(new FileTracker);
310      if (!tracker->ParseFromString(itr->value().ToString())) {
311        util::Log(logging::LOG_WARNING, FROM_HERE,
312                  "Failed to parse a Tracker");
313        continue;
314      }
315      contents->file_trackers.push_back(tracker.release());
316      continue;
317    }
318  }
319
320  return SYNC_STATUS_OK;
321}
322
323SyncStatusCode InitializeServiceMetadata(DatabaseContents* contents,
324                                         leveldb::WriteBatch* batch) {
325  if (!contents->service_metadata) {
326    contents->service_metadata.reset(new ServiceMetadata);
327    contents->service_metadata->set_next_tracker_id(1);
328
329    std::string value;
330    contents->service_metadata->SerializeToString(&value);
331    batch->Put(kServiceMetadataKey, value);
332  }
333  return SYNC_STATUS_OK;
334}
335
336SyncStatusCode RemoveUnreachableItems(DatabaseContents* contents,
337                                      leveldb::WriteBatch* batch) {
338  TrackerByID unvisited_trackers;
339  typedef std::map<int64, std::set<FileTracker*> > TrackersByParent;
340  TrackersByParent trackers_by_parent;
341
342  for (ScopedVector<FileTracker>::iterator itr =
343           contents->file_trackers.begin();
344       itr != contents->file_trackers.end();
345       ++itr) {
346    FileTracker* tracker = *itr;
347    DCHECK(!ContainsKey(unvisited_trackers, tracker->tracker_id()));
348    unvisited_trackers[tracker->tracker_id()] = tracker;
349    if (tracker->parent_tracker_id())
350      trackers_by_parent[tracker->parent_tracker_id()].insert(tracker);
351  }
352
353  // Traverse synced tracker tree. Take only active items, app-root and their
354  // children. Drop unreachable items.
355  ScopedVector<FileTracker> reachable_trackers;
356  std::stack<int64> pending;
357  if (contents->service_metadata->sync_root_tracker_id())
358    pending.push(contents->service_metadata->sync_root_tracker_id());
359
360  while (!pending.empty()) {
361    int64 tracker_id = pending.top();
362    pending.pop();
363
364    {
365      TrackerByID::iterator found = unvisited_trackers.find(tracker_id);
366      if (found == unvisited_trackers.end())
367        continue;
368
369      FileTracker* tracker = found->second;
370      unvisited_trackers.erase(found);
371      reachable_trackers.push_back(tracker);
372
373      if (!tracker->active())
374        continue;
375    }
376
377    TrackersByParent::iterator found = trackers_by_parent.find(tracker_id);
378    if (found == trackers_by_parent.end())
379      continue;
380
381    for (std::set<FileTracker*>::const_iterator itr =
382             found->second.begin();
383         itr != found->second.end();
384         ++itr)
385      pending.push((*itr)->tracker_id());
386  }
387
388  // Delete all unreachable trackers.
389  for (TrackerByID::iterator itr = unvisited_trackers.begin();
390       itr != unvisited_trackers.end(); ++itr) {
391    FileTracker* tracker = itr->second;
392    PutTrackerDeletionToBatch(tracker->tracker_id(), batch);
393    delete tracker;
394  }
395  unvisited_trackers.clear();
396
397  // |reachable_trackers| contains all files/folders reachable from sync-root
398  // folder via active folders and app-root folders.
399  // Update the tracker set in database contents with the reachable tracker set.
400  contents->file_trackers.weak_clear();
401  contents->file_trackers.swap(reachable_trackers);
402
403  // Do the similar traverse for FileMetadata and remove FileMetadata that don't
404  // have reachable trackers.
405  FileByID unreferred_files;
406  for (ScopedVector<FileMetadata>::const_iterator itr =
407           contents->file_metadata.begin();
408       itr != contents->file_metadata.end();
409       ++itr) {
410    unreferred_files.insert(std::make_pair((*itr)->file_id(), *itr));
411  }
412
413  ScopedVector<FileMetadata> referred_files;
414  for (ScopedVector<FileTracker>::const_iterator itr =
415           contents->file_trackers.begin();
416       itr != contents->file_trackers.end();
417       ++itr) {
418    FileByID::iterator found = unreferred_files.find((*itr)->file_id());
419    if (found != unreferred_files.end()) {
420      referred_files.push_back(found->second);
421      unreferred_files.erase(found);
422    }
423  }
424
425  for (FileByID::iterator itr = unreferred_files.begin();
426       itr != unreferred_files.end(); ++itr) {
427    FileMetadata* file = itr->second;
428    PutFileDeletionToBatch(file->file_id(), batch);
429    delete file;
430  }
431  unreferred_files.clear();
432
433  contents->file_metadata.weak_clear();
434  contents->file_metadata.swap(referred_files);
435
436  return SYNC_STATUS_OK;
437}
438
439template <typename Container, typename Key, typename Value>
440bool FindItem(const Container& container, const Key& key, Value* value) {
441  typename Container::const_iterator found = container.find(key);
442  if (found == container.end())
443    return false;
444  if (value)
445    *value = *found->second;
446  return true;
447}
448
449template <typename Container, typename Key>
450typename Container::mapped_type FindAndEraseItem(Container* container,
451                                                 const Key& key) {
452  typedef typename Container::mapped_type Value;
453  typename Container::iterator found = container->find(key);
454  if (found == container->end())
455    return Value();
456
457  Value result = found->second;
458  container->erase(found);
459  return result;
460}
461
462void RunSoon(const tracked_objects::Location& from_here,
463             const base::Closure& closure) {
464  base::MessageLoopProxy::current()->PostTask(from_here, closure);
465}
466
467}  // namespace
468
469bool MetadataDatabase::DirtyTrackerComparator::operator()(
470    const FileTracker* left,
471    const FileTracker* right) const {
472  return left->tracker_id() < right->tracker_id();
473}
474
475// static
476void MetadataDatabase::Create(base::SequencedTaskRunner* task_runner,
477                              const base::FilePath& database_path,
478                              const CreateCallback& callback) {
479  task_runner->PostTask(FROM_HERE, base::Bind(
480      &CreateOnTaskRunner,
481      base::MessageLoopProxy::current(),
482      make_scoped_refptr(task_runner),
483      database_path, callback));
484}
485
486MetadataDatabase::~MetadataDatabase() {
487  task_runner_->DeleteSoon(FROM_HERE, db_.release());
488  STLDeleteContainerPairSecondPointers(
489      file_by_id_.begin(), file_by_id_.end());
490  STLDeleteContainerPairSecondPointers(
491      tracker_by_id_.begin(), tracker_by_id_.end());
492}
493
494int64 MetadataDatabase::GetLargestChangeID() const {
495  return service_metadata_->largest_change_id();
496}
497
498int64 MetadataDatabase::GetSyncRootTrackerID() const {
499  return service_metadata_->sync_root_tracker_id();
500}
501
502bool MetadataDatabase::HasSyncRoot() const {
503  return service_metadata_->has_sync_root_tracker_id() &&
504      !!service_metadata_->sync_root_tracker_id();
505}
506
507void MetadataDatabase::PopulateInitialData(
508    int64 largest_change_id,
509    const google_apis::FileResource& sync_root_folder,
510    const ScopedVector<google_apis::FileResource>& app_root_folders,
511    const SyncStatusCallback& callback) {
512  DCHECK(tracker_by_id_.empty());
513  DCHECK(file_by_id_.empty());
514
515  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
516  service_metadata_->set_largest_change_id(largest_change_id);
517
518  FileTracker* sync_root_tracker = NULL;
519  int64 sync_root_tracker_id = 0;
520  {
521    scoped_ptr<FileMetadata> folder;
522    scoped_ptr<FileTracker> tracker;
523    CreateInitialSyncRootTracker(GetNextTrackerID(batch.get()),
524                                 sync_root_folder,
525                                 &folder,
526                                 &tracker);
527    std::string sync_root_folder_id = folder->file_id();
528    sync_root_tracker = tracker.get();
529    sync_root_tracker_id = tracker->tracker_id();
530
531    PutFileToBatch(*folder, batch.get());
532    PutTrackerToBatch(*tracker, batch.get());
533
534    service_metadata_->set_sync_root_tracker_id(tracker->tracker_id());
535    PutServiceMetadataToBatch(*service_metadata_, batch.get());
536
537    trackers_by_file_id_[folder->file_id()].Insert(tracker.get());
538
539    file_by_id_[sync_root_folder_id] = folder.release();
540    tracker_by_id_[sync_root_tracker_id] = tracker.release();
541  }
542
543  for (ScopedVector<google_apis::FileResource>::const_iterator itr =
544           app_root_folders.begin();
545       itr != app_root_folders.end();
546       ++itr) {
547    const google_apis::FileResource& folder_resource = **itr;
548    scoped_ptr<FileMetadata> folder;
549    scoped_ptr<FileTracker> tracker;
550    CreateInitialAppRootTracker(GetNextTrackerID(batch.get()),
551                                *sync_root_tracker,
552                                folder_resource,
553                                &folder,
554                                &tracker);
555    std::string title = folder->details().title();
556    std::string folder_id = folder->file_id();
557    int64 tracker_id = tracker->tracker_id();
558
559    PutFileToBatch(*folder, batch.get());
560    PutTrackerToBatch(*tracker, batch.get());
561
562    trackers_by_file_id_[folder_id].Insert(tracker.get());
563    trackers_by_parent_and_title_[sync_root_tracker_id][title]
564        .Insert(tracker.get());
565
566    file_by_id_[folder_id] = folder.release();
567    tracker_by_id_[tracker_id] = tracker.release();
568  }
569
570  WriteToDatabase(batch.Pass(), callback);
571}
572
573
574void MetadataDatabase::RegisterApp(const std::string& app_id,
575                                   const std::string& folder_id,
576                                   const SyncStatusCallback& callback) {
577  if (FindAppRootTracker(app_id, NULL)) {
578    // The app-root is already registered.
579    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
580    return;
581  }
582
583  TrackerSet trackers;
584  if (!FindTrackersByFileID(folder_id, &trackers) || trackers.has_active()) {
585    // The folder is tracked by another tracker.
586    util::Log(logging::LOG_WARNING, FROM_HERE,
587              "Failed to register App for %s", app_id.c_str());
588    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_HAS_CONFLICT));
589    return;
590  }
591
592  int64 sync_root_tracker_id = service_metadata_->sync_root_tracker_id();
593  if (!sync_root_tracker_id) {
594    util::Log(logging::LOG_WARNING, FROM_HERE,
595              "Sync-root needs to be set up before registering app-root");
596    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
597    return;
598  }
599
600  // Make this tracker an app-root tracker.
601  FileTracker* app_root_tracker = NULL;
602  for (TrackerSet::iterator itr = trackers.begin();
603       itr != trackers.end(); ++itr) {
604    FileTracker* tracker = *itr;
605    if (tracker->parent_tracker_id() == sync_root_tracker_id)
606      app_root_tracker = tracker;
607  }
608
609  if (!app_root_tracker) {
610    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
611    return;
612  }
613
614  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
615  RegisterTrackerAsAppRoot(app_id, app_root_tracker->tracker_id(), batch.get());
616  WriteToDatabase(batch.Pass(), callback);
617}
618
619void MetadataDatabase::DisableApp(const std::string& app_id,
620                                  const SyncStatusCallback& callback) {
621  FileTracker tracker;
622  if (!FindAppRootTracker(app_id, &tracker)) {
623    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
624    return;
625  }
626
627  if (tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
628    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
629    return;
630  }
631
632  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
633  MakeAppRootDisabled(tracker.tracker_id(), batch.get());
634  WriteToDatabase(batch.Pass(), callback);
635}
636
637void MetadataDatabase::EnableApp(const std::string& app_id,
638                                 const SyncStatusCallback& callback) {
639  FileTracker tracker;
640  if (!FindAppRootTracker(app_id, &tracker) ||
641      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
642    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
643    return;
644  }
645
646  if (tracker.tracker_kind() == TRACKER_KIND_APP_ROOT) {
647    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
648    return;
649  }
650
651  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
652  MakeAppRootEnabled(tracker.tracker_id(), batch.get());
653  WriteToDatabase(batch.Pass(), callback);
654}
655
656void MetadataDatabase::UnregisterApp(const std::string& app_id,
657                                     const SyncStatusCallback& callback) {
658  FileTracker tracker;
659  if (!FindAppRootTracker(app_id, &tracker) ||
660      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
661    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
662    return;
663  }
664
665  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
666  UnregisterTrackerAsAppRoot(app_id, batch.get());
667  WriteToDatabase(batch.Pass(), callback);
668}
669
670bool MetadataDatabase::FindAppRootTracker(const std::string& app_id,
671                                          FileTracker* tracker) const {
672  return FindItem(app_root_by_app_id_, app_id, tracker);
673}
674
675bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
676                                        FileMetadata* file) const {
677  return FindItem(file_by_id_, file_id, file);
678}
679
680bool MetadataDatabase::FindTrackersByFileID(const std::string& file_id,
681                                            TrackerSet* trackers) const {
682  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
683  if (found == trackers_by_file_id_.end())
684    return false;
685  if (trackers)
686    *trackers = found->second;
687  return true;
688}
689
690bool MetadataDatabase::FindTrackersByParentAndTitle(
691    int64 parent_tracker_id,
692    const std::string& title,
693    TrackerSet* trackers) const {
694  TrackersByParentAndTitle::const_iterator found_by_parent =
695      trackers_by_parent_and_title_.find(parent_tracker_id);
696  if (found_by_parent == trackers_by_parent_and_title_.end())
697    return false;
698
699  TrackersByTitle::const_iterator found_by_title =
700      found_by_parent->second.find(title);
701  if (found_by_title == found_by_parent->second.end())
702    return false;
703
704  if (trackers)
705    *trackers = found_by_title->second;
706  return true;
707}
708
709bool MetadataDatabase::FindTrackerByTrackerID(int64 tracker_id,
710                                              FileTracker* tracker) const {
711  return FindItem(tracker_by_id_, tracker_id, tracker);
712}
713
714bool MetadataDatabase::BuildPathForTracker(int64 tracker_id,
715                                           base::FilePath* path) const {
716  FileTracker current;
717  if (!FindTrackerByTrackerID(tracker_id, &current) || !current.active())
718    return false;
719
720  std::vector<base::FilePath> components;
721  while (!IsAppRoot(current)) {
722    std::string title = GetTrackerTitle(current);
723    if (title.empty())
724      return false;
725    components.push_back(base::FilePath::FromUTF8Unsafe(title));
726    if (!FindTrackerByTrackerID(current.parent_tracker_id(), &current) ||
727        !current.active())
728      return false;
729  }
730
731  if (path)
732    *path = ReverseConcatPathComponents(components);
733
734  return true;
735}
736
737void MetadataDatabase::UpdateByChangeList(
738    int64 largest_change_id,
739    ScopedVector<google_apis::ChangeResource> changes,
740    const SyncStatusCallback& callback) {
741  DCHECK_LE(service_metadata_->largest_change_id(), largest_change_id);
742
743  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
744
745  for (ScopedVector<google_apis::ChangeResource>::const_iterator itr =
746           changes.begin();
747       itr != changes.end();
748       ++itr) {
749    const google_apis::ChangeResource& change = **itr;
750    scoped_ptr<FileMetadata> file(
751        CreateFileMetadataFromChangeResource(change));
752    std::string file_id = file->file_id();
753
754    MarkTrackersDirtyByFileID(file_id, batch.get());
755    if (!file->details().deleted())
756      MaybeAddTrackersForNewFile(*file, batch.get());
757
758    if (FindTrackersByFileID(file_id, NULL)) {
759      PutFileToBatch(*file, batch.get());
760
761      // Set |file| to |file_by_id_[file_id]| and delete old value.
762      FileMetadata* file_ptr = file.release();
763      std::swap(file_ptr, file_by_id_[file_id]);
764      delete file_ptr;
765    }
766  }
767
768  service_metadata_->set_largest_change_id(largest_change_id);
769  PutServiceMetadataToBatch(*service_metadata_, batch.get());
770  WriteToDatabase(batch.Pass(), callback);
771}
772
773void MetadataDatabase::UpdateByFileResource(
774    int64 change_id,
775    const google_apis::FileResource& resource,
776    const SyncStatusCallback& callback) {
777  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
778
779  scoped_ptr<FileMetadata> file(
780      CreateFileMetadataFromFileResource(change_id, resource));
781  std::string file_id = file->file_id();
782
783  // TODO(tzik): Consolidate with UpdateByChangeList.
784  MarkTrackersDirtyByFileID(file_id, batch.get());
785  if (!file->details().deleted()) {
786    MaybeAddTrackersForNewFile(*file, batch.get());
787
788    if (FindTrackersByFileID(file_id, NULL)) {
789      PutFileToBatch(*file, batch.get());
790
791      // Set |file| to |file_by_id_[file_id]| and delete old value.
792      FileMetadata* file_ptr = file.release();
793      std::swap(file_ptr, file_by_id_[file_id]);
794      delete file_ptr;
795    }
796  }
797
798  WriteToDatabase(batch.Pass(), callback);
799}
800
801void MetadataDatabase::PopulateFolderByChildList(
802    const std::string& folder_id,
803    const FileIDList& child_file_ids,
804    const SyncStatusCallback& callback) {
805  TrackerSet trackers;
806  if (!FindTrackersByFileID(folder_id, &trackers) ||
807      !trackers.has_active()) {
808    // It's OK that there is no folder to populate its children.
809    // Inactive folders should ignore their contents updates.
810    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
811    return;
812  }
813
814  FileTracker* folder_tracker =
815      tracker_by_id_[trackers.active_tracker()->tracker_id()];
816  DCHECK(folder_tracker);
817  std::set<std::string> children(child_file_ids.begin(), child_file_ids.end());
818
819  std::vector<int64> known_children;
820  PushChildTrackersToContainer(trackers_by_parent_and_title_,
821                               folder_tracker->tracker_id(),
822                               std::back_inserter(known_children));
823  for (std::vector<int64>::iterator itr = known_children.begin();
824       itr != known_children.end(); ++itr)
825    children.erase(tracker_by_id_[*itr]->file_id());
826
827  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
828  for (FileIDList::const_iterator itr = child_file_ids.begin();
829       itr != child_file_ids.end(); ++itr)
830    CreateTrackerForParentAndFileID(*folder_tracker, *itr, batch.get());
831  folder_tracker->set_needs_folder_listing(false);
832  if (folder_tracker->dirty() && !ShouldKeepDirty(*folder_tracker)) {
833    folder_tracker->set_dirty(false);
834    dirty_trackers_.erase(folder_tracker);
835  }
836  PutTrackerToBatch(*folder_tracker, batch.get());
837
838  WriteToDatabase(batch.Pass(), callback);
839}
840
841void MetadataDatabase::UpdateTracker(int64 tracker_id,
842                                     const FileDetails& updated_details,
843                                     const SyncStatusCallback& callback) {
844  TrackerByID::iterator found = tracker_by_id_.find(tracker_id);
845  if (found == tracker_by_id_.end()) {
846    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
847    return;
848  }
849
850  FileTracker* tracker = found->second;
851  DCHECK(tracker);
852
853  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
854
855  if (updated_details.deleted()) {
856    // The update deletes the local file.
857    FileByID::iterator found = file_by_id_.find(tracker->file_id());
858    if (found == file_by_id_.end() || found->second->details().deleted()) {
859      // Both the tracker and metadata have the deleted flag, now it's safe to
860      // delete the |tracker|.
861      RemoveTracker(tracker->tracker_id(), batch.get());
862    } else {
863      // The local file is deleted, but corresponding remote file isn't.
864      // Put the tracker back to the initial state.
865      tracker->clear_synced_details();
866      tracker->set_dirty(true);
867      tracker->set_active(false);
868      PutTrackerToBatch(*tracker, batch.get());
869    }
870
871    WriteToDatabase(batch.Pass(), callback);
872    return;
873  }
874
875  // Check if the tracker was retitled.  If it was, update the title and its
876  // index in advance.
877  if (!tracker->has_synced_details() ||
878      tracker->synced_details().title() != updated_details.title()) {
879    UpdateTrackerTitle(tracker, updated_details.title(), batch.get());
880  }
881
882  *tracker->mutable_synced_details() = updated_details;
883
884  // Activate the tracker if:
885  //   - There is no active tracker that tracks |tracker->file_id()|.
886  //   - There is no active tracker that has the same |parent| and |title|.
887  if (!tracker->active() && CanActivateTracker(*tracker))
888    MakeTrackerActive(tracker->tracker_id(), batch.get());
889  if (tracker->dirty() && !ShouldKeepDirty(*tracker)) {
890    tracker->set_dirty(false);
891    dirty_trackers_.erase(tracker);
892  }
893  PutTrackerToBatch(*tracker, batch.get());
894
895  WriteToDatabase(batch.Pass(), callback);
896}
897
898MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner)
899    : task_runner_(task_runner), weak_ptr_factory_(this) {
900  DCHECK(task_runner);
901}
902
903// static
904void MetadataDatabase::CreateOnTaskRunner(
905    base::SingleThreadTaskRunner* callback_runner,
906    base::SequencedTaskRunner* task_runner,
907    const base::FilePath& database_path,
908    const CreateCallback& callback) {
909  scoped_ptr<MetadataDatabase> metadata_database(
910      new MetadataDatabase(task_runner));
911  SyncStatusCode status =
912      metadata_database->InitializeOnTaskRunner(database_path);
913  if (status != SYNC_STATUS_OK)
914    metadata_database.reset();
915
916  callback_runner->PostTask(FROM_HERE, base::Bind(
917      callback, status, base::Passed(&metadata_database)));
918}
919
920// static
921SyncStatusCode MetadataDatabase::CreateForTesting(
922    scoped_ptr<leveldb::DB> db,
923    scoped_ptr<MetadataDatabase>* metadata_database_out) {
924  scoped_ptr<MetadataDatabase> metadata_database(
925      new MetadataDatabase(base::MessageLoopProxy::current()));
926  metadata_database->db_ = db.Pass();
927  SyncStatusCode status =
928      metadata_database->InitializeOnTaskRunner(base::FilePath());
929  if (status == SYNC_STATUS_OK)
930    *metadata_database_out = metadata_database.Pass();
931  return status;
932}
933
934SyncStatusCode MetadataDatabase::SetLargestChangeIDForTesting(
935    int64 largest_change_id) {
936  service_metadata_->set_largest_change_id(largest_change_id);
937
938  leveldb::WriteBatch batch;
939  PutServiceMetadataToBatch(*service_metadata_, &batch);
940  return LevelDBStatusToSyncStatusCode(
941      db_->Write(leveldb::WriteOptions(), &batch));
942}
943
944SyncStatusCode MetadataDatabase::InitializeOnTaskRunner(
945    const base::FilePath& database_path) {
946  base::ThreadRestrictions::AssertIOAllowed();
947  DCHECK(task_runner_->RunsTasksOnCurrentThread());
948
949  SyncStatusCode status = SYNC_STATUS_UNKNOWN;
950  bool created = false;
951  // Open database unless |db_| is overridden for testing.
952  if (!db_) {
953    status = OpenDatabase(database_path, &db_, &created);
954    if (status != SYNC_STATUS_OK)
955      return status;
956  }
957
958  if (created) {
959    status = WriteVersionInfo(db_.get());
960    if (status != SYNC_STATUS_OK)
961      return status;
962  } else {
963    status = MigrateDatabaseIfNeeded(db_.get());
964    if (status != SYNC_STATUS_OK)
965      return status;
966  }
967
968  DatabaseContents contents;
969  status = ReadDatabaseContents(db_.get(), &contents);
970  if (status != SYNC_STATUS_OK)
971    return status;
972
973  leveldb::WriteBatch batch;
974  status = InitializeServiceMetadata(&contents, &batch);
975  if (status != SYNC_STATUS_OK)
976    return status;
977
978  status = RemoveUnreachableItems(&contents, &batch);
979  if (status != SYNC_STATUS_OK)
980    return status;
981
982  status = LevelDBStatusToSyncStatusCode(
983      db_->Write(leveldb::WriteOptions(), &batch));
984  if (status != SYNC_STATUS_OK)
985    return status;
986
987  BuildIndexes(&contents);
988  return status;
989}
990
991void MetadataDatabase::BuildIndexes(DatabaseContents* contents) {
992  service_metadata_ = contents->service_metadata.Pass();
993
994  for (ScopedVector<FileMetadata>::const_iterator itr =
995           contents->file_metadata.begin();
996       itr != contents->file_metadata.end();
997       ++itr) {
998    file_by_id_[(*itr)->file_id()] = *itr;
999  }
1000  contents->file_metadata.weak_clear();
1001
1002  for (ScopedVector<FileTracker>::const_iterator itr =
1003           contents->file_trackers.begin();
1004       itr != contents->file_trackers.end();
1005       ++itr) {
1006    FileTracker* tracker = *itr;
1007    tracker_by_id_[tracker->tracker_id()] = tracker;
1008    trackers_by_file_id_[tracker->file_id()].Insert(tracker);
1009
1010    if (IsAppRoot(*tracker))
1011      app_root_by_app_id_[tracker->app_id()] = tracker;
1012
1013    if (tracker->parent_tracker_id()) {
1014      std::string title = GetTrackerTitle(*tracker);
1015      TrackerSet* trackers =
1016          &trackers_by_parent_and_title_[tracker->parent_tracker_id()][title];
1017      trackers->Insert(tracker);
1018    }
1019
1020    if (tracker->dirty())
1021      dirty_trackers_.insert(tracker);
1022  }
1023  contents->file_trackers.weak_clear();
1024}
1025
1026void MetadataDatabase::RegisterTrackerAsAppRoot(
1027    const std::string& app_id,
1028    int64 tracker_id,
1029    leveldb::WriteBatch* batch) {
1030  FileTracker* tracker = tracker_by_id_[tracker_id];
1031  DCHECK(tracker);
1032  tracker->set_app_id(app_id);
1033  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
1034  app_root_by_app_id_[app_id] = tracker;
1035
1036  MakeTrackerActive(tracker->tracker_id(), batch);
1037}
1038
1039void MetadataDatabase::UnregisterTrackerAsAppRoot(
1040    const std::string& app_id,
1041    leveldb::WriteBatch* batch) {
1042  FileTracker* tracker = FindAndEraseItem(&app_root_by_app_id_, app_id);
1043  tracker->set_app_id(std::string());
1044  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1045
1046  // Inactivate the tracker to drop all descendant.
1047  // (Note that we set tracker_kind to TRACKER_KIND_REGULAR before calling
1048  // this.)
1049  MakeTrackerInactive(tracker->tracker_id(), batch);
1050}
1051
1052void MetadataDatabase::MakeTrackerActive(int64 tracker_id,
1053                                         leveldb::WriteBatch* batch) {
1054  FileTracker* tracker = tracker_by_id_[tracker_id];
1055  DCHECK(tracker);
1056  DCHECK(!tracker->active());
1057
1058  int64 parent_tracker_id = tracker->parent_tracker_id();
1059  DCHECK(tracker->has_synced_details());
1060  trackers_by_file_id_[tracker->file_id()].Activate(tracker);
1061  if (parent_tracker_id) {
1062    trackers_by_parent_and_title_[parent_tracker_id][
1063        tracker->synced_details().title()].Activate(tracker);
1064  }
1065  tracker->set_active(true);
1066  tracker->set_needs_folder_listing(
1067      tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
1068  tracker->set_dirty(true);
1069  dirty_trackers_.insert(tracker);
1070
1071  PutTrackerToBatch(*tracker, batch);
1072}
1073
1074void MetadataDatabase::MakeTrackerInactive(int64 tracker_id,
1075                                           leveldb::WriteBatch* batch) {
1076  FileTracker* tracker = tracker_by_id_[tracker_id];
1077  DCHECK(tracker);
1078  DCHECK(tracker->active());
1079  DCHECK_EQ(TRACKER_KIND_REGULAR, tracker->tracker_kind());
1080  trackers_by_file_id_[tracker->file_id()].Inactivate(tracker);
1081
1082  std::string title = GetTrackerTitle(*tracker);
1083  int64 parent_tracker_id = tracker->parent_tracker_id();
1084  if (parent_tracker_id)
1085    trackers_by_parent_and_title_[parent_tracker_id][title].Inactivate(tracker);
1086  tracker->set_active(false);
1087
1088  RemoveAllDescendantTrackers(tracker_id, batch);
1089  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
1090  if (parent_tracker_id)
1091    MarkTrackersDirtyByPath(parent_tracker_id, title, batch);
1092  PutTrackerToBatch(*tracker, batch);
1093}
1094
1095void MetadataDatabase::MakeAppRootDisabled(int64 tracker_id,
1096                                           leveldb::WriteBatch* batch) {
1097  FileTracker* tracker = tracker_by_id_[tracker_id];
1098  DCHECK(tracker);
1099  DCHECK_EQ(TRACKER_KIND_APP_ROOT, tracker->tracker_kind());
1100  DCHECK(tracker->active());
1101
1102  // Keep the app-root tracker active (but change the tracker_kind) so that
1103  // other conflicting trackers won't become active.
1104  tracker->set_tracker_kind(TRACKER_KIND_DISABLED_APP_ROOT);
1105  PutTrackerToBatch(*tracker, batch);
1106}
1107
1108void MetadataDatabase::MakeAppRootEnabled(int64 tracker_id,
1109                                          leveldb::WriteBatch* batch) {
1110  FileTracker* tracker = tracker_by_id_[tracker_id];
1111  DCHECK(tracker);
1112  DCHECK_EQ(TRACKER_KIND_DISABLED_APP_ROOT, tracker->tracker_kind());
1113  DCHECK(tracker->active());
1114
1115  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
1116  // Mark descendant trackers as dirty to handle changes in disable period.
1117  RecursiveMarkTrackerAsDirty(tracker_id, batch);
1118  PutTrackerToBatch(*tracker, batch);
1119}
1120
1121void MetadataDatabase::CreateTrackerForParentAndFileID(
1122    const FileTracker& parent_tracker,
1123    const std::string& file_id,
1124    leveldb::WriteBatch* batch) {
1125  int64 tracker_id = GetNextTrackerID(batch);
1126  scoped_ptr<FileTracker> tracker(new FileTracker);
1127  tracker->set_tracker_id(tracker_id);
1128  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
1129  tracker->set_file_id(file_id);
1130  tracker->set_app_id(parent_tracker.app_id());
1131  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1132  tracker->set_dirty(true);
1133  tracker->set_active(false);
1134  tracker->set_needs_folder_listing(false);
1135  PutTrackerToBatch(*tracker, batch);
1136
1137  trackers_by_file_id_[file_id].Insert(tracker.get());
1138  // Note: |trackers_by_parent_and_title_| does not map from
1139  // FileMetadata::details but from FileTracker::synced_details, which is filled
1140  // on tracker updated phase.  Use empty string as the title since
1141  // FileTracker::synced_details is empty here.
1142  trackers_by_parent_and_title_[parent_tracker.tracker_id()][std::string()]
1143      .Insert(tracker.get());
1144  dirty_trackers_.insert(tracker.get());
1145  DCHECK(!ContainsKey(tracker_by_id_, tracker_id));
1146  tracker_by_id_[tracker_id] = tracker.release();
1147}
1148
1149void MetadataDatabase::RemoveTracker(int64 tracker_id,
1150                                     leveldb::WriteBatch* batch) {
1151  RemoveTrackerInternal(tracker_id, batch, false);
1152}
1153
1154void MetadataDatabase::RemoveTrackerIgnoringSiblings(
1155    int64 tracker_id,
1156    leveldb::WriteBatch* batch) {
1157  RemoveTrackerInternal(tracker_id, batch, true);
1158}
1159
1160void MetadataDatabase::RemoveTrackerInternal(
1161    int64 tracker_id,
1162    leveldb::WriteBatch* batch,
1163    bool ignoring_siblings) {
1164  scoped_ptr<FileTracker> tracker(
1165      FindAndEraseItem(&tracker_by_id_, tracker_id));
1166  if (!tracker)
1167    return;
1168
1169  EraseTrackerFromFileIDIndex(tracker.get(), batch);
1170  if (IsAppRoot(*tracker))
1171    app_root_by_app_id_.erase(tracker->app_id());
1172  EraseTrackerFromPathIndex(tracker.get());
1173
1174  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
1175  if (!ignoring_siblings) {
1176    MarkTrackersDirtyByPath(tracker->parent_tracker_id(),
1177                            GetTrackerTitle(*tracker),
1178                            batch);
1179  }
1180  PutTrackerDeletionToBatch(tracker_id, batch);
1181}
1182
1183void MetadataDatabase::MaybeAddTrackersForNewFile(
1184    const FileMetadata& file,
1185    leveldb::WriteBatch* batch) {
1186  std::set<int64> known_parents;
1187  TrackersByFileID::iterator found = trackers_by_file_id_.find(file.file_id());
1188  if (found != trackers_by_file_id_.end()) {
1189    for (TrackerSet::const_iterator itr = found->second.begin();
1190         itr != found->second.end(); ++itr) {
1191      int64 parent_tracker_id = (*itr)->parent_tracker_id();
1192      if (parent_tracker_id)
1193        known_parents.insert(parent_tracker_id);
1194    }
1195  }
1196
1197  for (int i = 0; i < file.details().parent_folder_ids_size(); ++i) {
1198    std::string parent_folder_id = file.details().parent_folder_ids(i);
1199    TrackersByFileID::iterator found =
1200        trackers_by_file_id_.find(parent_folder_id);
1201    if (found == trackers_by_file_id_.end())
1202      continue;
1203
1204    for (TrackerSet::const_iterator itr = found->second.begin();
1205         itr != found->second.end(); ++itr) {
1206      FileTracker* parent_tracker = *itr;
1207      int64 parent_tracker_id = parent_tracker->tracker_id();
1208      if (!parent_tracker->active())
1209        continue;
1210
1211      if (ContainsKey(known_parents, parent_tracker_id))
1212        continue;
1213
1214      CreateTrackerForParentAndFileID(*parent_tracker, file.file_id(), batch);
1215    }
1216  }
1217}
1218
1219void MetadataDatabase::RemoveAllDescendantTrackers(int64 root_tracker_id,
1220                                                   leveldb::WriteBatch* batch) {
1221  std::vector<int64> pending_trackers;
1222  PushChildTrackersToContainer(trackers_by_parent_and_title_,
1223                               root_tracker_id,
1224                               std::back_inserter(pending_trackers));
1225
1226  while (!pending_trackers.empty()) {
1227    int64 tracker_id = pending_trackers.back();
1228    pending_trackers.pop_back();
1229    PushChildTrackersToContainer(trackers_by_parent_and_title_,
1230                                 tracker_id,
1231                                 std::back_inserter(pending_trackers));
1232    RemoveTrackerIgnoringSiblings(tracker_id, batch);
1233  }
1234}
1235
1236void MetadataDatabase::EraseTrackerFromFileIDIndex(FileTracker* tracker,
1237                                                   leveldb::WriteBatch* batch) {
1238  TrackersByFileID::iterator found =
1239      trackers_by_file_id_.find(tracker->file_id());
1240  if (found == trackers_by_file_id_.end())
1241    return;
1242
1243  TrackerSet* trackers = &found->second;
1244  trackers->Erase(tracker);
1245  if (!trackers->tracker_set().empty())
1246    return;
1247  trackers_by_file_id_.erase(found);
1248  EraseFileFromDatabase(tracker->file_id(), batch);
1249}
1250
1251void MetadataDatabase::EraseFileFromDatabase(const std::string& file_id,
1252                                             leveldb::WriteBatch* batch) {
1253  scoped_ptr<FileMetadata> file(FindAndEraseItem(&file_by_id_, file_id));
1254  if (file)
1255    PutFileDeletionToBatch(file_id, batch);
1256}
1257
1258void MetadataDatabase::EraseTrackerFromPathIndex(FileTracker* tracker) {
1259  TrackersByParentAndTitle::iterator found =
1260      trackers_by_parent_and_title_.find(tracker->parent_tracker_id());
1261  if (found == trackers_by_parent_and_title_.end())
1262    return;
1263
1264  std::string title = GetTrackerTitle(*tracker);
1265  TrackersByTitle* trackers_by_title = &found->second;
1266  TrackersByTitle::iterator found_by_title = trackers_by_title->find(title);
1267  TrackerSet* conflicting_trackers = &found_by_title->second;
1268  conflicting_trackers->Erase(tracker);
1269
1270  if (conflicting_trackers->tracker_set().empty()) {
1271    trackers_by_title->erase(found_by_title);
1272    if (trackers_by_title->empty())
1273      trackers_by_parent_and_title_.erase(found);
1274  }
1275}
1276
1277void MetadataDatabase::MarkTrackerSetDirty(
1278    TrackerSet* trackers,
1279    leveldb::WriteBatch* batch) {
1280  for (TrackerSet::iterator itr = trackers->begin();
1281       itr != trackers->end(); ++itr) {
1282    FileTracker* tracker = *itr;
1283    if (tracker->dirty())
1284      continue;
1285    tracker->set_dirty(true);
1286    PutTrackerToBatch(*tracker, batch);
1287    dirty_trackers_.insert(tracker);
1288  }
1289}
1290
1291void MetadataDatabase::MarkTrackersDirtyByFileID(
1292    const std::string& file_id,
1293    leveldb::WriteBatch* batch) {
1294  TrackersByFileID::iterator found = trackers_by_file_id_.find(file_id);
1295  if (found != trackers_by_file_id_.end())
1296    MarkTrackerSetDirty(&found->second, batch);
1297}
1298
1299void MetadataDatabase::MarkTrackersDirtyByPath(int64 parent_tracker_id,
1300                                               const std::string& title,
1301                                               leveldb::WriteBatch* batch) {
1302  TrackersByParentAndTitle::iterator found =
1303      trackers_by_parent_and_title_.find(parent_tracker_id);
1304  if (found == trackers_by_parent_and_title_.end()) {
1305    NOTREACHED() << "parent: " << parent_tracker_id
1306                 << ", title: " << title;
1307    return;
1308  }
1309
1310  TrackersByTitle::iterator itr = found->second.find(title);
1311  if (itr != found->second.end())
1312    MarkTrackerSetDirty(&itr->second, batch);
1313}
1314
1315int64 MetadataDatabase::GetNextTrackerID(leveldb::WriteBatch* batch) {
1316  int64 tracker_id = service_metadata_->next_tracker_id();
1317  service_metadata_->set_next_tracker_id(tracker_id + 1);
1318  PutServiceMetadataToBatch(*service_metadata_, batch);
1319  DCHECK_GT(tracker_id, 0);
1320  return tracker_id;
1321}
1322
1323void MetadataDatabase::RecursiveMarkTrackerAsDirty(int64 root_tracker_id,
1324                                                   leveldb::WriteBatch* batch) {
1325  std::vector<int64> stack;
1326  stack.push_back(root_tracker_id);
1327  while (!stack.empty()) {
1328    int64 tracker_id = stack.back();
1329    stack.pop_back();
1330    PushChildTrackersToContainer(
1331        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
1332
1333    FileTracker* tracker = tracker_by_id_[tracker_id];
1334    if (!tracker->dirty()) {
1335      tracker->set_dirty(true);
1336      PutTrackerToBatch(*tracker, batch);
1337      dirty_trackers_.insert(tracker);
1338    }
1339  }
1340}
1341
1342bool MetadataDatabase::CanActivateTracker(const FileTracker& tracker) {
1343  DCHECK(!tracker.active());
1344  DCHECK_NE(service_metadata_->sync_root_tracker_id(), tracker.tracker_id());
1345
1346  if (HasActiveTrackerForFileID(tracker.file_id()))
1347    return false;
1348
1349  if (tracker.app_id().empty())
1350    return false;
1351  if (!tracker.has_synced_details())
1352    return false;
1353  DCHECK(tracker.parent_tracker_id());
1354
1355  return !HasActiveTrackerForPath(tracker.parent_tracker_id(),
1356                                  tracker.synced_details().title());
1357}
1358
1359bool MetadataDatabase::ShouldKeepDirty(const FileTracker& tracker) const {
1360  if (HasDisabledAppRoot(tracker))
1361    return false;
1362
1363  DCHECK(tracker.dirty());
1364  if (!tracker.has_synced_details())
1365    return true;
1366
1367  FileByID::const_iterator found = file_by_id_.find(tracker.file_id());
1368  if (found == file_by_id_.end())
1369    return true;
1370  const FileMetadata* file = found->second;
1371  DCHECK(file);
1372
1373  if (tracker.active()) {
1374    if (tracker.needs_folder_listing())
1375      return true;
1376    if (tracker.synced_details().md5() != file->details().md5())
1377      return true;
1378  }
1379
1380  const FileDetails& local_details = tracker.synced_details();
1381  const FileDetails& remote_details = file->details();
1382
1383  if (local_details.title() != remote_details.title())
1384    return true;
1385  if (local_details.deleted() != remote_details.deleted())
1386    return true;
1387
1388  return false;
1389}
1390
1391bool MetadataDatabase::HasDisabledAppRoot(const FileTracker& tracker) const {
1392  TrackerByAppID::const_iterator found =
1393      app_root_by_app_id_.find(tracker.app_id());
1394  if (found == app_root_by_app_id_.end())
1395    return false;
1396
1397  const FileTracker* app_root_tracker = found->second;
1398  DCHECK(app_root_tracker);
1399  return app_root_tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
1400}
1401
1402bool MetadataDatabase::HasActiveTrackerForFileID(
1403    const std::string& file_id) const {
1404  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
1405  return found != trackers_by_file_id_.end() && found->second.has_active();
1406}
1407
1408bool MetadataDatabase::HasActiveTrackerForPath(int64 parent_tracker_id,
1409                                               const std::string& title) const {
1410  TrackersByParentAndTitle::const_iterator found_by_parent =
1411      trackers_by_parent_and_title_.find(parent_tracker_id);
1412  if (found_by_parent == trackers_by_parent_and_title_.end())
1413    return false;
1414
1415  const TrackersByTitle& trackers_by_title = found_by_parent->second;
1416  TrackersByTitle::const_iterator found = trackers_by_title.find(title);
1417  return found != trackers_by_title.end() && found->second.has_active();
1418}
1419
1420void MetadataDatabase::UpdateTrackerTitle(FileTracker* tracker,
1421                                          const std::string& new_title,
1422                                          leveldb::WriteBatch* batch) {
1423  int64 parent_id = tracker->parent_tracker_id();
1424  std::string old_title = GetTrackerTitle(*tracker);
1425  DCHECK_NE(old_title, new_title);
1426  DCHECK(!new_title.empty());
1427
1428  TrackersByTitle* trackers_by_title =
1429      &trackers_by_parent_and_title_[parent_id];
1430  TrackerSet* old_siblings = &(*trackers_by_title)[old_title];
1431  TrackerSet* new_siblings = &(*trackers_by_title)[new_title];
1432
1433  old_siblings->Erase(tracker);
1434  if (old_siblings->empty())
1435    trackers_by_title->erase(old_title);
1436  else
1437    MarkTrackerSetDirty(old_siblings, batch);
1438
1439  if (tracker->active() && new_siblings->has_active()) {
1440    // Inactivate existing active tracker.
1441    FileTracker* obstacle = new_siblings->active_tracker();
1442    new_siblings->Inactivate(obstacle);
1443    DCHECK_EQ(TRACKER_KIND_REGULAR, obstacle->tracker_kind());
1444
1445    TrackerSet* same_file_id_trackers_to_obstacle =
1446        &trackers_by_file_id_[obstacle->file_id()];
1447    same_file_id_trackers_to_obstacle->Inactivate(obstacle);
1448    MarkTrackerSetDirty(same_file_id_trackers_to_obstacle, batch);
1449
1450    obstacle->set_active(false);
1451    PutTrackerToBatch(*obstacle, batch);
1452
1453    RemoveAllDescendantTrackers(obstacle->tracker_id(), batch);
1454  }
1455
1456  tracker->mutable_synced_details()->set_title(new_title);
1457  new_siblings->Insert(tracker);
1458  PutTrackerToBatch(*tracker, batch);
1459}
1460
1461void MetadataDatabase::WriteToDatabase(scoped_ptr<leveldb::WriteBatch> batch,
1462                                       const SyncStatusCallback& callback) {
1463  base::PostTaskAndReplyWithResult(
1464      task_runner_.get(),
1465      FROM_HERE,
1466      base::Bind(&leveldb::DB::Write,
1467                 base::Unretained(db_.get()),
1468                 leveldb::WriteOptions(),
1469                 base::Owned(batch.release())),
1470      base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
1471}
1472
1473}  // namespace drive_backend
1474}  // namespace sync_file_system
1475