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