metadata_database.cc revision f2477e01787aa58f445919b809d89e252beef54f 
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::GetLargestFetchedChangeID() const {
495  return service_metadata_->largest_change_id();
496}
497
498int64 MetadataDatabase::GetSyncRootTrackerID() const {
499  return service_metadata_->sync_root_tracker_id();
500}
501
502int64 MetadataDatabase::GetLargestKnownChangeID() const {
503  DCHECK_LE(GetLargestFetchedChangeID(), largest_known_change_id_);
504  return largest_known_change_id_;
505}
506
507void MetadataDatabase::UpdateLargestKnownChangeID(int64 change_id) {
508  if (largest_known_change_id_ < change_id)
509    largest_known_change_id_ = change_id;
510}
511
512bool MetadataDatabase::HasSyncRoot() const {
513  return service_metadata_->has_sync_root_tracker_id() &&
514      !!service_metadata_->sync_root_tracker_id();
515}
516
517void MetadataDatabase::PopulateInitialData(
518    int64 largest_change_id,
519    const google_apis::FileResource& sync_root_folder,
520    const ScopedVector<google_apis::FileResource>& app_root_folders,
521    const SyncStatusCallback& callback) {
522  DCHECK(tracker_by_id_.empty());
523  DCHECK(file_by_id_.empty());
524
525  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
526  service_metadata_->set_largest_change_id(largest_change_id);
527  UpdateLargestKnownChangeID(largest_change_id);
528
529  FileTracker* sync_root_tracker = NULL;
530  int64 sync_root_tracker_id = 0;
531  {
532    scoped_ptr<FileMetadata> folder;
533    scoped_ptr<FileTracker> tracker;
534    CreateInitialSyncRootTracker(GetNextTrackerID(batch.get()),
535                                 sync_root_folder,
536                                 &folder,
537                                 &tracker);
538    std::string sync_root_folder_id = folder->file_id();
539    sync_root_tracker = tracker.get();
540    sync_root_tracker_id = tracker->tracker_id();
541
542    PutFileToBatch(*folder, batch.get());
543    PutTrackerToBatch(*tracker, batch.get());
544
545    service_metadata_->set_sync_root_tracker_id(tracker->tracker_id());
546    PutServiceMetadataToBatch(*service_metadata_, batch.get());
547
548    trackers_by_file_id_[folder->file_id()].Insert(tracker.get());
549
550    file_by_id_[sync_root_folder_id] = folder.release();
551    tracker_by_id_[sync_root_tracker_id] = tracker.release();
552  }
553
554  for (ScopedVector<google_apis::FileResource>::const_iterator itr =
555           app_root_folders.begin();
556       itr != app_root_folders.end();
557       ++itr) {
558    const google_apis::FileResource& folder_resource = **itr;
559    scoped_ptr<FileMetadata> folder;
560    scoped_ptr<FileTracker> tracker;
561    CreateInitialAppRootTracker(GetNextTrackerID(batch.get()),
562                                *sync_root_tracker,
563                                folder_resource,
564                                &folder,
565                                &tracker);
566    std::string title = folder->details().title();
567    std::string folder_id = folder->file_id();
568    int64 tracker_id = tracker->tracker_id();
569
570    PutFileToBatch(*folder, batch.get());
571    PutTrackerToBatch(*tracker, batch.get());
572
573    trackers_by_file_id_[folder_id].Insert(tracker.get());
574    trackers_by_parent_and_title_[sync_root_tracker_id][title]
575        .Insert(tracker.get());
576
577    file_by_id_[folder_id] = folder.release();
578    tracker_by_id_[tracker_id] = tracker.release();
579  }
580
581  WriteToDatabase(batch.Pass(), callback);
582}
583
584bool MetadataDatabase::IsAppEnabled(const std::string& app_id) const {
585  FileTracker tracker;
586  if (!FindAppRootTracker(app_id, &tracker))
587    return false;
588  return tracker.tracker_kind() == TRACKER_KIND_APP_ROOT;
589}
590
591void MetadataDatabase::RegisterApp(const std::string& app_id,
592                                   const std::string& folder_id,
593                                   const SyncStatusCallback& callback) {
594  if (FindAppRootTracker(app_id, NULL)) {
595    // The app-root is already registered.
596    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
597    return;
598  }
599
600  TrackerSet trackers;
601  if (!FindTrackersByFileID(folder_id, &trackers) || trackers.has_active()) {
602    // The folder is tracked by another tracker.
603    util::Log(logging::LOG_WARNING, FROM_HERE,
604              "Failed to register App for %s", app_id.c_str());
605    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_HAS_CONFLICT));
606    return;
607  }
608
609  int64 sync_root_tracker_id = service_metadata_->sync_root_tracker_id();
610  if (!sync_root_tracker_id) {
611    util::Log(logging::LOG_WARNING, FROM_HERE,
612              "Sync-root needs to be set up before registering app-root");
613    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
614    return;
615  }
616
617  // Make this tracker an app-root tracker.
618  FileTracker* app_root_tracker = NULL;
619  for (TrackerSet::iterator itr = trackers.begin();
620       itr != trackers.end(); ++itr) {
621    FileTracker* tracker = *itr;
622    if (tracker->parent_tracker_id() == sync_root_tracker_id)
623      app_root_tracker = tracker;
624  }
625
626  if (!app_root_tracker) {
627    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
628    return;
629  }
630
631  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
632  RegisterTrackerAsAppRoot(app_id, app_root_tracker->tracker_id(), batch.get());
633  WriteToDatabase(batch.Pass(), callback);
634}
635
636void MetadataDatabase::DisableApp(const std::string& app_id,
637                                  const SyncStatusCallback& callback) {
638  FileTracker tracker;
639  if (!FindAppRootTracker(app_id, &tracker)) {
640    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
641    return;
642  }
643
644  if (tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
645    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
646    return;
647  }
648
649  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
650  MakeAppRootDisabled(tracker.tracker_id(), batch.get());
651  WriteToDatabase(batch.Pass(), callback);
652}
653
654void MetadataDatabase::EnableApp(const std::string& app_id,
655                                 const SyncStatusCallback& callback) {
656  FileTracker tracker;
657  if (!FindAppRootTracker(app_id, &tracker) ||
658      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
659    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
660    return;
661  }
662
663  if (tracker.tracker_kind() == TRACKER_KIND_APP_ROOT) {
664    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
665    return;
666  }
667
668  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
669  MakeAppRootEnabled(tracker.tracker_id(), batch.get());
670  WriteToDatabase(batch.Pass(), callback);
671}
672
673void MetadataDatabase::UnregisterApp(const std::string& app_id,
674                                     const SyncStatusCallback& callback) {
675  FileTracker tracker;
676  if (!FindAppRootTracker(app_id, &tracker) ||
677      tracker.tracker_kind() == TRACKER_KIND_REGULAR) {
678    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
679    return;
680  }
681
682  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
683  UnregisterTrackerAsAppRoot(app_id, batch.get());
684  WriteToDatabase(batch.Pass(), callback);
685}
686
687bool MetadataDatabase::FindAppRootTracker(const std::string& app_id,
688                                          FileTracker* tracker) const {
689  return FindItem(app_root_by_app_id_, app_id, tracker);
690}
691
692bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
693                                        FileMetadata* file) const {
694  return FindItem(file_by_id_, file_id, file);
695}
696
697bool MetadataDatabase::FindTrackersByFileID(const std::string& file_id,
698                                            TrackerSet* trackers) const {
699  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
700  if (found == trackers_by_file_id_.end())
701    return false;
702  if (trackers)
703    *trackers = found->second;
704  return true;
705}
706
707bool MetadataDatabase::FindTrackersByParentAndTitle(
708    int64 parent_tracker_id,
709    const std::string& title,
710    TrackerSet* trackers) const {
711  TrackersByParentAndTitle::const_iterator found_by_parent =
712      trackers_by_parent_and_title_.find(parent_tracker_id);
713  if (found_by_parent == trackers_by_parent_and_title_.end())
714    return false;
715
716  TrackersByTitle::const_iterator found_by_title =
717      found_by_parent->second.find(title);
718  if (found_by_title == found_by_parent->second.end())
719    return false;
720
721  if (trackers)
722    *trackers = found_by_title->second;
723  return true;
724}
725
726bool MetadataDatabase::FindTrackerByTrackerID(int64 tracker_id,
727                                              FileTracker* tracker) const {
728  return FindItem(tracker_by_id_, tracker_id, tracker);
729}
730
731bool MetadataDatabase::BuildPathForTracker(int64 tracker_id,
732                                           base::FilePath* path) const {
733  FileTracker current;
734  if (!FindTrackerByTrackerID(tracker_id, &current) || !current.active())
735    return false;
736
737  std::vector<base::FilePath> components;
738  while (!IsAppRoot(current)) {
739    std::string title = GetTrackerTitle(current);
740    if (title.empty())
741      return false;
742    components.push_back(base::FilePath::FromUTF8Unsafe(title));
743    if (!FindTrackerByTrackerID(current.parent_tracker_id(), &current) ||
744        !current.active())
745      return false;
746  }
747
748  if (path)
749    *path = ReverseConcatPathComponents(components);
750
751  return true;
752}
753
754bool MetadataDatabase::FindNearestActiveAncestor(
755    const std::string& app_id,
756    const base::FilePath& full_path,
757    FileTracker* tracker,
758    base::FilePath* path) const {
759  DCHECK(tracker);
760  DCHECK(path);
761
762  if (full_path.IsAbsolute() ||
763      !FindAppRootTracker(app_id, tracker) ||
764      tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
765    return false;
766  }
767
768  std::vector<base::FilePath::StringType> components;
769  full_path.GetComponents(&components);
770  path->clear();
771
772  for (size_t i = 0; i < components.size(); ++i) {
773    const std::string title = base::FilePath(components[i]).AsUTF8Unsafe();
774    TrackerSet trackers;
775    if (!FindTrackersByParentAndTitle(
776            tracker->tracker_id(), title, &trackers) ||
777        !trackers.has_active()) {
778      return true;
779    }
780
781    DCHECK(trackers.active_tracker()->has_synced_details());
782    const FileDetails& details = trackers.active_tracker()->synced_details();
783    if (details.file_kind() != FILE_KIND_FOLDER && i != components.size() - 1) {
784      // This non-last component indicates file. Give up search.
785      return true;
786    }
787
788    *tracker = *trackers.active_tracker();
789    *path = path->Append(components[i]);
790  }
791
792  return true;
793}
794
795void MetadataDatabase::UpdateByChangeList(
796    int64 largest_change_id,
797    ScopedVector<google_apis::ChangeResource> changes,
798    const SyncStatusCallback& callback) {
799  DCHECK_LE(service_metadata_->largest_change_id(), largest_change_id);
800
801  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
802
803  for (ScopedVector<google_apis::ChangeResource>::const_iterator itr =
804           changes.begin();
805       itr != changes.end();
806       ++itr) {
807    const google_apis::ChangeResource& change = **itr;
808    if (HasNewerFileMetadata(change.file_id(), change.change_id()))
809      continue;
810
811    scoped_ptr<FileMetadata> file(
812        CreateFileMetadataFromChangeResource(change));
813    std::string file_id = file->file_id();
814
815    MarkTrackersDirtyByFileID(file_id, batch.get());
816    if (!file->details().missing())
817      MaybeAddTrackersForNewFile(*file, batch.get());
818
819    if (FindTrackersByFileID(file_id, NULL)) {
820      PutFileToBatch(*file, batch.get());
821
822      // Set |file| to |file_by_id_[file_id]| and delete old value.
823      FileMetadata* file_ptr = file.release();
824      std::swap(file_ptr, file_by_id_[file_id]);
825      delete file_ptr;
826    }
827  }
828
829  UpdateLargestKnownChangeID(largest_change_id);
830  service_metadata_->set_largest_change_id(largest_change_id);
831  PutServiceMetadataToBatch(*service_metadata_, batch.get());
832  WriteToDatabase(batch.Pass(), callback);
833}
834
835void MetadataDatabase::UpdateByFileResource(
836    int64 change_id,
837    const google_apis::FileResource& resource,
838    const SyncStatusCallback& callback) {
839  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
840
841  scoped_ptr<FileMetadata> file(
842      CreateFileMetadataFromFileResource(change_id, resource));
843  std::string file_id = file->file_id();
844  if (HasNewerFileMetadata(file_id, change_id)) {
845    callback.Run(SYNC_STATUS_OK);
846    return;
847  }
848
849  // TODO(tzik): Consolidate with UpdateByChangeList.
850  MarkTrackersDirtyByFileID(file_id, batch.get());
851  if (!file->details().missing()) {
852    MaybeAddTrackersForNewFile(*file, batch.get());
853
854    if (FindTrackersByFileID(file_id, NULL)) {
855      PutFileToBatch(*file, batch.get());
856
857      // Set |file| to |file_by_id_[file_id]| and delete old value.
858      FileMetadata* file_ptr = file.release();
859      std::swap(file_ptr, file_by_id_[file_id]);
860      delete file_ptr;
861    }
862  }
863
864  WriteToDatabase(batch.Pass(), callback);
865}
866
867void MetadataDatabase::ReplaceActiveTrackerWithNewResource(
868    int64 change_id,
869    int64 parent_tracker_id,
870    const google_apis::FileResource& resource,
871    const SyncStatusCallback& callback) {
872  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
873
874  scoped_ptr<FileMetadata> file(
875      CreateFileMetadataFromFileResource(change_id, resource));
876  std::string file_id = file->file_id();
877  DCHECK(!ContainsKey(file_by_id_, file_id));
878  DCHECK(!file->details().missing());
879
880  // TODO(tzik): Consolidate with UpdateByChangeList.
881  MaybeAddTrackersForNewFile(*file, batch.get());
882
883  const FileDetails& new_file_details = file->details();
884  PutFileToBatch(*file, batch.get());
885  file_by_id_[file_id] = file.release();
886
887  TrackerSet new_trackers;
888  if (!FindTrackersByFileID(file_id, &new_trackers)) {
889    NOTREACHED();
890    WriteToDatabase(batch.Pass(), callback);
891    return;
892  }
893  DCHECK_EQ(1u, new_trackers.size());
894
895  FileTracker* new_tracker = *new_trackers.begin();
896  DCHECK(!new_tracker->active());
897  DCHECK(!new_tracker->has_synced_details());
898  DCHECK_EQ(parent_tracker_id, new_tracker->parent_tracker_id());
899
900  std::string title = new_file_details.title();
901  TrackerSet trackers;
902  if (FindTrackersByParentAndTitle(parent_tracker_id, title, &trackers) &&
903      trackers.has_active())
904    MakeTrackerInactive(trackers.active_tracker()->tracker_id(), batch.get());
905
906  // TODO(tzik): Simplify this part.
907  *new_tracker->mutable_synced_details() = new_file_details;
908  trackers_by_parent_and_title_[parent_tracker_id][title].Insert(new_tracker);
909
910  MakeTrackerActive(new_tracker->tracker_id(), batch.get());
911
912  new_tracker->set_dirty(false);
913  dirty_trackers_.erase(new_tracker);
914  low_priority_dirty_trackers_.erase(new_tracker);
915  PutTrackerToBatch(*new_tracker, batch.get());
916
917  WriteToDatabase(batch.Pass(), callback);
918}
919
920void MetadataDatabase::PopulateFolderByChildList(
921    const std::string& folder_id,
922    const FileIDList& child_file_ids,
923    const SyncStatusCallback& callback) {
924  TrackerSet trackers;
925  if (!FindTrackersByFileID(folder_id, &trackers) ||
926      !trackers.has_active()) {
927    // It's OK that there is no folder to populate its children.
928    // Inactive folders should ignore their contents updates.
929    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
930    return;
931  }
932
933  FileTracker* folder_tracker =
934      tracker_by_id_[trackers.active_tracker()->tracker_id()];
935  DCHECK(folder_tracker);
936  std::set<std::string> children(child_file_ids.begin(), child_file_ids.end());
937
938  std::vector<int64> known_children;
939  PushChildTrackersToContainer(trackers_by_parent_and_title_,
940                               folder_tracker->tracker_id(),
941                               std::back_inserter(known_children));
942  for (std::vector<int64>::iterator itr = known_children.begin();
943       itr != known_children.end(); ++itr)
944    children.erase(tracker_by_id_[*itr]->file_id());
945
946  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
947  for (FileIDList::const_iterator itr = child_file_ids.begin();
948       itr != child_file_ids.end(); ++itr)
949    CreateTrackerForParentAndFileID(*folder_tracker, *itr, batch.get());
950  folder_tracker->set_needs_folder_listing(false);
951  if (folder_tracker->dirty() && !ShouldKeepDirty(*folder_tracker)) {
952    folder_tracker->set_dirty(false);
953    dirty_trackers_.erase(folder_tracker);
954    low_priority_dirty_trackers_.erase(folder_tracker);
955  }
956  PutTrackerToBatch(*folder_tracker, batch.get());
957
958  WriteToDatabase(batch.Pass(), callback);
959}
960
961void MetadataDatabase::UpdateTracker(int64 tracker_id,
962                                     const FileDetails& updated_details,
963                                     const SyncStatusCallback& callback) {
964  TrackerByID::iterator found = tracker_by_id_.find(tracker_id);
965  if (found == tracker_by_id_.end()) {
966    RunSoon(FROM_HERE, base::Bind(callback, SYNC_DATABASE_ERROR_NOT_FOUND));
967    return;
968  }
969
970  FileTracker* tracker = found->second;
971  DCHECK(tracker);
972
973  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
974
975  if (updated_details.missing()) {
976    FileByID::iterator found = file_by_id_.find(tracker->file_id());
977    if (found == file_by_id_.end() || found->second->details().missing()) {
978      // Both the tracker and metadata have the missing flag, now it's safe to
979      // delete the |tracker|.
980      RemoveTracker(tracker->tracker_id(), batch.get());
981      WriteToDatabase(batch.Pass(), callback);
982      return;
983    }
984  }
985
986  // Check if the tracker's parent is still in |parent_tracker_ids|.
987  // If not, there should exist another tracker for the new parent, so delete
988  // old tracker.
989  DCHECK(ContainsKey(tracker_by_id_, tracker->parent_tracker_id()));
990  FileTracker* parent_tracker = tracker_by_id_[tracker->parent_tracker_id()];
991  if (!HasFileAsParent(updated_details, parent_tracker->file_id())) {
992    RemoveTracker(tracker->tracker_id(), batch.get());
993    WriteToDatabase(batch.Pass(), callback);
994    return;
995  }
996
997  if (tracker->has_synced_details()) {
998    // Check if the tracker was retitled.  If it was, there should exist another
999    // tracker for the new title, so delete old tracker.
1000    if (tracker->synced_details().title() != updated_details.title()) {
1001      RemoveTracker(tracker->tracker_id(), batch.get());
1002      WriteToDatabase(batch.Pass(), callback);
1003      return;
1004    }
1005  } else {
1006    int64 parent_tracker_id = parent_tracker->tracker_id();
1007    const std::string& title = updated_details.title();
1008    trackers_by_parent_and_title_[parent_tracker_id][title].Insert(
1009        tracker);
1010  }
1011
1012  *tracker->mutable_synced_details() = updated_details;
1013
1014  // Activate the tracker if:
1015  //   - There is no active tracker that tracks |tracker->file_id()|.
1016  //   - There is no active tracker that has the same |parent| and |title|.
1017  if (!tracker->active() && CanActivateTracker(*tracker))
1018    MakeTrackerActive(tracker->tracker_id(), batch.get());
1019  if (tracker->dirty() && !ShouldKeepDirty(*tracker)) {
1020    tracker->set_dirty(false);
1021    dirty_trackers_.erase(tracker);
1022    low_priority_dirty_trackers_.erase(tracker);
1023  }
1024  PutTrackerToBatch(*tracker, batch.get());
1025
1026  WriteToDatabase(batch.Pass(), callback);
1027}
1028
1029void MetadataDatabase::LowerTrackerPriority(int64 tracker_id) {
1030  TrackerByID::const_iterator found = tracker_by_id_.find(tracker_id);
1031  if (found == tracker_by_id_.end())
1032    return;
1033
1034  FileTracker* tracker = found->second;
1035  if (dirty_trackers_.erase(tracker))
1036    low_priority_dirty_trackers_.insert(tracker);
1037}
1038
1039bool MetadataDatabase::GetNormalPriorityDirtyTracker(
1040    FileTracker* tracker) const {
1041  DirtyTrackers::const_iterator itr = dirty_trackers_.begin();
1042  if (itr == dirty_trackers_.end())
1043    return false;
1044  if (tracker)
1045    *tracker = **itr;
1046  return true;
1047}
1048
1049bool MetadataDatabase::GetLowPriorityDirtyTracker(
1050    FileTracker* tracker) const {
1051  DirtyTrackers::const_iterator itr = low_priority_dirty_trackers_.begin();
1052  if (itr == low_priority_dirty_trackers_.end())
1053    return false;
1054  if (tracker)
1055    *tracker = **itr;
1056  return true;
1057}
1058
1059void MetadataDatabase::GetRegisteredAppIDs(std::vector<std::string>* app_ids) {
1060  DCHECK(app_ids);
1061  app_ids->clear();
1062  app_ids->reserve(app_root_by_app_id_.size());
1063  for (TrackerByAppID::iterator itr = app_root_by_app_id_.begin();
1064       itr != app_root_by_app_id_.end(); ++itr) {
1065    app_ids->push_back(itr->first);
1066  }
1067}
1068
1069void MetadataDatabase::MarkTrackerDirty(int64 tracker_id,
1070                                        const SyncStatusCallback& callback) {
1071  TrackerByID::iterator found = tracker_by_id_.find(tracker_id);
1072  if (found == tracker_by_id_.end()) {
1073    RunSoon(FROM_HERE, base::Bind(callback, SYNC_STATUS_OK));
1074    return;
1075  }
1076
1077  scoped_ptr<leveldb::WriteBatch> batch(new leveldb::WriteBatch);
1078  MarkSingleTrackerDirty(found->second, batch.get());
1079  WriteToDatabase(batch.Pass(), callback);
1080}
1081
1082MetadataDatabase::MetadataDatabase(base::SequencedTaskRunner* task_runner)
1083    : task_runner_(task_runner),
1084      largest_known_change_id_(0),
1085      weak_ptr_factory_(this) {
1086  DCHECK(task_runner);
1087}
1088
1089// static
1090void MetadataDatabase::CreateOnTaskRunner(
1091    base::SingleThreadTaskRunner* callback_runner,
1092    base::SequencedTaskRunner* task_runner,
1093    const base::FilePath& database_path,
1094    const CreateCallback& callback) {
1095  scoped_ptr<MetadataDatabase> metadata_database(
1096      new MetadataDatabase(task_runner));
1097  SyncStatusCode status =
1098      metadata_database->InitializeOnTaskRunner(database_path);
1099  if (status != SYNC_STATUS_OK)
1100    metadata_database.reset();
1101
1102  callback_runner->PostTask(FROM_HERE, base::Bind(
1103      callback, status, base::Passed(&metadata_database)));
1104}
1105
1106// static
1107SyncStatusCode MetadataDatabase::CreateForTesting(
1108    scoped_ptr<leveldb::DB> db,
1109    scoped_ptr<MetadataDatabase>* metadata_database_out) {
1110  scoped_ptr<MetadataDatabase> metadata_database(
1111      new MetadataDatabase(base::MessageLoopProxy::current()));
1112  metadata_database->db_ = db.Pass();
1113  SyncStatusCode status =
1114      metadata_database->InitializeOnTaskRunner(base::FilePath());
1115  if (status == SYNC_STATUS_OK)
1116    *metadata_database_out = metadata_database.Pass();
1117  return status;
1118}
1119
1120SyncStatusCode MetadataDatabase::SetLargestChangeIDForTesting(
1121    int64 largest_change_id) {
1122  service_metadata_->set_largest_change_id(largest_change_id);
1123
1124  leveldb::WriteBatch batch;
1125  PutServiceMetadataToBatch(*service_metadata_, &batch);
1126  return LevelDBStatusToSyncStatusCode(
1127      db_->Write(leveldb::WriteOptions(), &batch));
1128}
1129
1130SyncStatusCode MetadataDatabase::InitializeOnTaskRunner(
1131    const base::FilePath& database_path) {
1132  base::ThreadRestrictions::AssertIOAllowed();
1133  DCHECK(task_runner_->RunsTasksOnCurrentThread());
1134
1135  SyncStatusCode status = SYNC_STATUS_UNKNOWN;
1136  bool created = false;
1137  // Open database unless |db_| is overridden for testing.
1138  if (!db_) {
1139    status = OpenDatabase(database_path, &db_, &created);
1140    if (status != SYNC_STATUS_OK)
1141      return status;
1142  }
1143
1144  if (created) {
1145    status = WriteVersionInfo(db_.get());
1146    if (status != SYNC_STATUS_OK)
1147      return status;
1148  } else {
1149    status = MigrateDatabaseIfNeeded(db_.get());
1150    if (status != SYNC_STATUS_OK)
1151      return status;
1152  }
1153
1154  DatabaseContents contents;
1155  status = ReadDatabaseContents(db_.get(), &contents);
1156  if (status != SYNC_STATUS_OK)
1157    return status;
1158
1159  leveldb::WriteBatch batch;
1160  status = InitializeServiceMetadata(&contents, &batch);
1161  if (status != SYNC_STATUS_OK)
1162    return status;
1163
1164  status = RemoveUnreachableItems(&contents, &batch);
1165  if (status != SYNC_STATUS_OK)
1166    return status;
1167
1168  status = LevelDBStatusToSyncStatusCode(
1169      db_->Write(leveldb::WriteOptions(), &batch));
1170  if (status != SYNC_STATUS_OK)
1171    return status;
1172
1173  BuildIndexes(&contents);
1174  return status;
1175}
1176
1177void MetadataDatabase::BuildIndexes(DatabaseContents* contents) {
1178  service_metadata_ = contents->service_metadata.Pass();
1179  UpdateLargestKnownChangeID(service_metadata_->largest_change_id());
1180
1181  for (ScopedVector<FileMetadata>::const_iterator itr =
1182           contents->file_metadata.begin();
1183       itr != contents->file_metadata.end();
1184       ++itr) {
1185    file_by_id_[(*itr)->file_id()] = *itr;
1186  }
1187  contents->file_metadata.weak_clear();
1188
1189  for (ScopedVector<FileTracker>::const_iterator itr =
1190           contents->file_trackers.begin();
1191       itr != contents->file_trackers.end();
1192       ++itr) {
1193    FileTracker* tracker = *itr;
1194    tracker_by_id_[tracker->tracker_id()] = tracker;
1195    trackers_by_file_id_[tracker->file_id()].Insert(tracker);
1196
1197    if (IsAppRoot(*tracker))
1198      app_root_by_app_id_[tracker->app_id()] = tracker;
1199
1200    if (tracker->parent_tracker_id()) {
1201      std::string title = GetTrackerTitle(*tracker);
1202      TrackerSet* trackers =
1203          &trackers_by_parent_and_title_[tracker->parent_tracker_id()][title];
1204      trackers->Insert(tracker);
1205    }
1206
1207    if (tracker->dirty())
1208      dirty_trackers_.insert(tracker);
1209  }
1210  contents->file_trackers.weak_clear();
1211}
1212
1213void MetadataDatabase::RegisterTrackerAsAppRoot(
1214    const std::string& app_id,
1215    int64 tracker_id,
1216    leveldb::WriteBatch* batch) {
1217  FileTracker* tracker = tracker_by_id_[tracker_id];
1218  DCHECK(tracker);
1219  tracker->set_app_id(app_id);
1220  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
1221  app_root_by_app_id_[app_id] = tracker;
1222
1223  MakeTrackerActive(tracker->tracker_id(), batch);
1224}
1225
1226void MetadataDatabase::UnregisterTrackerAsAppRoot(
1227    const std::string& app_id,
1228    leveldb::WriteBatch* batch) {
1229  FileTracker* tracker = FindAndEraseItem(&app_root_by_app_id_, app_id);
1230  tracker->set_app_id(std::string());
1231  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1232
1233  // Inactivate the tracker to drop all descendant.
1234  // (Note that we set tracker_kind to TRACKER_KIND_REGULAR before calling
1235  // this.)
1236  MakeTrackerInactive(tracker->tracker_id(), batch);
1237}
1238
1239void MetadataDatabase::MakeTrackerActive(int64 tracker_id,
1240                                         leveldb::WriteBatch* batch) {
1241  FileTracker* tracker = tracker_by_id_[tracker_id];
1242  DCHECK(tracker);
1243  DCHECK(!tracker->active());
1244
1245  int64 parent_tracker_id = tracker->parent_tracker_id();
1246  DCHECK(tracker->has_synced_details());
1247  trackers_by_file_id_[tracker->file_id()].Activate(tracker);
1248  if (parent_tracker_id) {
1249    trackers_by_parent_and_title_[parent_tracker_id][
1250        tracker->synced_details().title()].Activate(tracker);
1251  }
1252  tracker->set_active(true);
1253  tracker->set_needs_folder_listing(
1254      tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
1255
1256  // Make |tracker| a normal priority dirty tracker.
1257  if (tracker->dirty())
1258    low_priority_dirty_trackers_.erase(tracker);
1259  tracker->set_dirty(true);
1260  dirty_trackers_.insert(tracker);
1261
1262  PutTrackerToBatch(*tracker, batch);
1263}
1264
1265void MetadataDatabase::MakeTrackerInactive(int64 tracker_id,
1266                                           leveldb::WriteBatch* batch) {
1267  FileTracker* tracker = tracker_by_id_[tracker_id];
1268  DCHECK(tracker);
1269  DCHECK(tracker->active());
1270  DCHECK_EQ(TRACKER_KIND_REGULAR, tracker->tracker_kind());
1271  trackers_by_file_id_[tracker->file_id()].Inactivate(tracker);
1272
1273  std::string title = GetTrackerTitle(*tracker);
1274  int64 parent_tracker_id = tracker->parent_tracker_id();
1275  if (parent_tracker_id)
1276    trackers_by_parent_and_title_[parent_tracker_id][title].Inactivate(tracker);
1277  tracker->set_active(false);
1278
1279  RemoveAllDescendantTrackers(tracker_id, batch);
1280  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
1281  if (parent_tracker_id)
1282    MarkTrackersDirtyByPath(parent_tracker_id, title, batch);
1283  PutTrackerToBatch(*tracker, batch);
1284}
1285
1286void MetadataDatabase::MakeAppRootDisabled(int64 tracker_id,
1287                                           leveldb::WriteBatch* batch) {
1288  FileTracker* tracker = tracker_by_id_[tracker_id];
1289  DCHECK(tracker);
1290  DCHECK_EQ(TRACKER_KIND_APP_ROOT, tracker->tracker_kind());
1291  DCHECK(tracker->active());
1292
1293  // Keep the app-root tracker active (but change the tracker_kind) so that
1294  // other conflicting trackers won't become active.
1295  tracker->set_tracker_kind(TRACKER_KIND_DISABLED_APP_ROOT);
1296  PutTrackerToBatch(*tracker, batch);
1297}
1298
1299void MetadataDatabase::MakeAppRootEnabled(int64 tracker_id,
1300                                          leveldb::WriteBatch* batch) {
1301  FileTracker* tracker = tracker_by_id_[tracker_id];
1302  DCHECK(tracker);
1303  DCHECK_EQ(TRACKER_KIND_DISABLED_APP_ROOT, tracker->tracker_kind());
1304  DCHECK(tracker->active());
1305
1306  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
1307  // Mark descendant trackers as dirty to handle changes in disable period.
1308  RecursiveMarkTrackerAsDirty(tracker_id, batch);
1309  PutTrackerToBatch(*tracker, batch);
1310}
1311
1312void MetadataDatabase::CreateTrackerForParentAndFileID(
1313    const FileTracker& parent_tracker,
1314    const std::string& file_id,
1315    leveldb::WriteBatch* batch) {
1316  int64 tracker_id = GetNextTrackerID(batch);
1317  scoped_ptr<FileTracker> tracker(new FileTracker);
1318  tracker->set_tracker_id(tracker_id);
1319  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
1320  tracker->set_file_id(file_id);
1321  tracker->set_app_id(parent_tracker.app_id());
1322  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1323  tracker->set_dirty(true);
1324  tracker->set_active(false);
1325  tracker->set_needs_folder_listing(false);
1326  PutTrackerToBatch(*tracker, batch);
1327
1328  trackers_by_file_id_[file_id].Insert(tracker.get());
1329  // Note: |trackers_by_parent_and_title_| does not map from
1330  // FileMetadata::details but from FileTracker::synced_details, which is filled
1331  // on tracker updated phase.  Use empty string as the title since
1332  // FileTracker::synced_details is empty here.
1333  trackers_by_parent_and_title_[parent_tracker.tracker_id()][std::string()]
1334      .Insert(tracker.get());
1335  dirty_trackers_.insert(tracker.get());
1336  DCHECK(!ContainsKey(tracker_by_id_, tracker_id));
1337  tracker_by_id_[tracker_id] = tracker.release();
1338}
1339
1340void MetadataDatabase::RemoveTracker(int64 tracker_id,
1341                                     leveldb::WriteBatch* batch) {
1342  RemoveTrackerInternal(tracker_id, batch, false);
1343  RemoveAllDescendantTrackers(tracker_id, batch);
1344}
1345
1346void MetadataDatabase::RemoveTrackerIgnoringSameTitle(
1347    int64 tracker_id,
1348    leveldb::WriteBatch* batch) {
1349  RemoveTrackerInternal(tracker_id, batch, true);
1350}
1351
1352void MetadataDatabase::RemoveTrackerInternal(
1353    int64 tracker_id,
1354    leveldb::WriteBatch* batch,
1355    bool ignoring_same_title) {
1356  scoped_ptr<FileTracker> tracker(
1357      FindAndEraseItem(&tracker_by_id_, tracker_id));
1358  if (!tracker)
1359    return;
1360
1361  EraseTrackerFromFileIDIndex(tracker.get(), batch);
1362  if (IsAppRoot(*tracker))
1363    app_root_by_app_id_.erase(tracker->app_id());
1364  EraseTrackerFromPathIndex(tracker.get());
1365  dirty_trackers_.erase(tracker.get());
1366  low_priority_dirty_trackers_.erase(tracker.get());
1367
1368  MarkTrackersDirtyByFileID(tracker->file_id(), batch);
1369  if (!ignoring_same_title) {
1370    // Mark trackers having the same title with the given tracker as dirty.
1371    MarkTrackersDirtyByPath(tracker->parent_tracker_id(),
1372                            GetTrackerTitle(*tracker),
1373                            batch);
1374  }
1375  PutTrackerDeletionToBatch(tracker_id, batch);
1376}
1377
1378void MetadataDatabase::MaybeAddTrackersForNewFile(
1379    const FileMetadata& file,
1380    leveldb::WriteBatch* batch) {
1381  std::set<int64> parents_to_exclude;
1382  TrackersByFileID::iterator found = trackers_by_file_id_.find(file.file_id());
1383  if (found != trackers_by_file_id_.end()) {
1384    for (TrackerSet::const_iterator itr = found->second.begin();
1385         itr != found->second.end(); ++itr) {
1386      const FileTracker& tracker = **itr;
1387      int64 parent_tracker_id = tracker.parent_tracker_id();
1388      if (!parent_tracker_id)
1389        continue;
1390
1391      // Exclude |parent_tracker_id| if it already has a tracker that has
1392      // unknown title or has the same title with |file|.
1393      if (!tracker.has_synced_details() ||
1394          tracker.synced_details().title() == file.details().title()) {
1395        parents_to_exclude.insert(parent_tracker_id);
1396      }
1397    }
1398  }
1399
1400  for (int i = 0; i < file.details().parent_folder_ids_size(); ++i) {
1401    std::string parent_folder_id = file.details().parent_folder_ids(i);
1402    TrackersByFileID::iterator found =
1403        trackers_by_file_id_.find(parent_folder_id);
1404    if (found == trackers_by_file_id_.end())
1405      continue;
1406
1407    for (TrackerSet::const_iterator itr = found->second.begin();
1408         itr != found->second.end(); ++itr) {
1409      FileTracker* parent_tracker = *itr;
1410      int64 parent_tracker_id = parent_tracker->tracker_id();
1411      if (!parent_tracker->active())
1412        continue;
1413
1414      if (ContainsKey(parents_to_exclude, parent_tracker_id))
1415        continue;
1416
1417      CreateTrackerForParentAndFileID(*parent_tracker, file.file_id(), batch);
1418    }
1419  }
1420}
1421
1422void MetadataDatabase::RemoveAllDescendantTrackers(int64 root_tracker_id,
1423                                                   leveldb::WriteBatch* batch) {
1424  std::vector<int64> pending_trackers;
1425  PushChildTrackersToContainer(trackers_by_parent_and_title_,
1426                               root_tracker_id,
1427                               std::back_inserter(pending_trackers));
1428
1429  while (!pending_trackers.empty()) {
1430    int64 tracker_id = pending_trackers.back();
1431    pending_trackers.pop_back();
1432    PushChildTrackersToContainer(trackers_by_parent_and_title_,
1433                                 tracker_id,
1434                                 std::back_inserter(pending_trackers));
1435    RemoveTrackerIgnoringSameTitle(tracker_id, batch);
1436  }
1437}
1438
1439void MetadataDatabase::EraseTrackerFromFileIDIndex(FileTracker* tracker,
1440                                                   leveldb::WriteBatch* batch) {
1441  TrackersByFileID::iterator found =
1442      trackers_by_file_id_.find(tracker->file_id());
1443  if (found == trackers_by_file_id_.end())
1444    return;
1445
1446  TrackerSet* trackers = &found->second;
1447  trackers->Erase(tracker);
1448  if (!trackers->tracker_set().empty())
1449    return;
1450  trackers_by_file_id_.erase(found);
1451  EraseFileFromDatabase(tracker->file_id(), batch);
1452}
1453
1454void MetadataDatabase::EraseFileFromDatabase(const std::string& file_id,
1455                                             leveldb::WriteBatch* batch) {
1456  scoped_ptr<FileMetadata> file(FindAndEraseItem(&file_by_id_, file_id));
1457  if (file)
1458    PutFileDeletionToBatch(file_id, batch);
1459}
1460
1461void MetadataDatabase::EraseTrackerFromPathIndex(FileTracker* tracker) {
1462  TrackersByParentAndTitle::iterator found =
1463      trackers_by_parent_and_title_.find(tracker->parent_tracker_id());
1464  if (found == trackers_by_parent_and_title_.end())
1465    return;
1466
1467  std::string title = GetTrackerTitle(*tracker);
1468  TrackersByTitle* trackers_by_title = &found->second;
1469  TrackersByTitle::iterator found_by_title = trackers_by_title->find(title);
1470  TrackerSet* conflicting_trackers = &found_by_title->second;
1471  conflicting_trackers->Erase(tracker);
1472
1473  if (conflicting_trackers->tracker_set().empty()) {
1474    trackers_by_title->erase(found_by_title);
1475    if (trackers_by_title->empty())
1476      trackers_by_parent_and_title_.erase(found);
1477  }
1478}
1479
1480void MetadataDatabase::MarkSingleTrackerDirty(FileTracker* tracker,
1481                                              leveldb::WriteBatch* batch) {
1482  if (!tracker->dirty()) {
1483    tracker->set_dirty(true);
1484    PutTrackerToBatch(*tracker, batch);
1485  }
1486  dirty_trackers_.insert(tracker);
1487  low_priority_dirty_trackers_.erase(tracker);
1488}
1489
1490void MetadataDatabase::MarkTrackerSetDirty(
1491    TrackerSet* trackers,
1492    leveldb::WriteBatch* batch) {
1493  for (TrackerSet::iterator itr = trackers->begin();
1494       itr != trackers->end(); ++itr) {
1495    MarkSingleTrackerDirty(*itr, batch);
1496  }
1497}
1498
1499void MetadataDatabase::MarkTrackersDirtyByFileID(
1500    const std::string& file_id,
1501    leveldb::WriteBatch* batch) {
1502  TrackersByFileID::iterator found = trackers_by_file_id_.find(file_id);
1503  if (found != trackers_by_file_id_.end())
1504    MarkTrackerSetDirty(&found->second, batch);
1505}
1506
1507void MetadataDatabase::MarkTrackersDirtyByPath(int64 parent_tracker_id,
1508                                               const std::string& title,
1509                                               leveldb::WriteBatch* batch) {
1510  TrackersByParentAndTitle::iterator found =
1511      trackers_by_parent_and_title_.find(parent_tracker_id);
1512  if (found == trackers_by_parent_and_title_.end())
1513    return;
1514
1515  TrackersByTitle::iterator itr = found->second.find(title);
1516  if (itr != found->second.end())
1517    MarkTrackerSetDirty(&itr->second, batch);
1518}
1519
1520int64 MetadataDatabase::GetNextTrackerID(leveldb::WriteBatch* batch) {
1521  int64 tracker_id = service_metadata_->next_tracker_id();
1522  service_metadata_->set_next_tracker_id(tracker_id + 1);
1523  PutServiceMetadataToBatch(*service_metadata_, batch);
1524  DCHECK_GT(tracker_id, 0);
1525  return tracker_id;
1526}
1527
1528void MetadataDatabase::RecursiveMarkTrackerAsDirty(int64 root_tracker_id,
1529                                                   leveldb::WriteBatch* batch) {
1530  std::vector<int64> stack;
1531  stack.push_back(root_tracker_id);
1532  while (!stack.empty()) {
1533    int64 tracker_id = stack.back();
1534    stack.pop_back();
1535    PushChildTrackersToContainer(
1536        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
1537
1538    FileTracker* tracker = tracker_by_id_[tracker_id];
1539    if (!tracker->dirty()) {
1540      tracker->set_dirty(true);
1541      PutTrackerToBatch(*tracker, batch);
1542      dirty_trackers_.insert(tracker);
1543      low_priority_dirty_trackers_.erase(tracker);
1544    }
1545  }
1546}
1547
1548bool MetadataDatabase::CanActivateTracker(const FileTracker& tracker) {
1549  DCHECK(!tracker.active());
1550  DCHECK_NE(service_metadata_->sync_root_tracker_id(), tracker.tracker_id());
1551
1552  if (HasActiveTrackerForFileID(tracker.file_id()))
1553    return false;
1554
1555  if (tracker.app_id().empty())
1556    return false;
1557  if (!tracker.has_synced_details())
1558    return false;
1559  DCHECK(tracker.parent_tracker_id());
1560
1561  return !HasActiveTrackerForPath(tracker.parent_tracker_id(),
1562                                  tracker.synced_details().title());
1563}
1564
1565bool MetadataDatabase::ShouldKeepDirty(const FileTracker& tracker) const {
1566  if (HasDisabledAppRoot(tracker))
1567    return false;
1568
1569  DCHECK(tracker.dirty());
1570  if (!tracker.has_synced_details())
1571    return true;
1572
1573  FileByID::const_iterator found = file_by_id_.find(tracker.file_id());
1574  if (found == file_by_id_.end())
1575    return true;
1576  const FileMetadata* file = found->second;
1577  DCHECK(file);
1578
1579  if (tracker.active()) {
1580    if (tracker.needs_folder_listing())
1581      return true;
1582    if (tracker.synced_details().md5() != file->details().md5())
1583      return true;
1584  }
1585
1586  const FileDetails& local_details = tracker.synced_details();
1587  const FileDetails& remote_details = file->details();
1588
1589  if (local_details.title() != remote_details.title())
1590    return true;
1591  if (local_details.missing() != remote_details.missing())
1592    return true;
1593
1594  return false;
1595}
1596
1597bool MetadataDatabase::HasDisabledAppRoot(const FileTracker& tracker) const {
1598  TrackerByAppID::const_iterator found =
1599      app_root_by_app_id_.find(tracker.app_id());
1600  if (found == app_root_by_app_id_.end())
1601    return false;
1602
1603  const FileTracker* app_root_tracker = found->second;
1604  DCHECK(app_root_tracker);
1605  return app_root_tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
1606}
1607
1608bool MetadataDatabase::HasActiveTrackerForFileID(
1609    const std::string& file_id) const {
1610  TrackersByFileID::const_iterator found = trackers_by_file_id_.find(file_id);
1611  return found != trackers_by_file_id_.end() && found->second.has_active();
1612}
1613
1614bool MetadataDatabase::HasActiveTrackerForPath(int64 parent_tracker_id,
1615                                               const std::string& title) const {
1616  TrackersByParentAndTitle::const_iterator found_by_parent =
1617      trackers_by_parent_and_title_.find(parent_tracker_id);
1618  if (found_by_parent == trackers_by_parent_and_title_.end())
1619    return false;
1620
1621  const TrackersByTitle& trackers_by_title = found_by_parent->second;
1622  TrackersByTitle::const_iterator found = trackers_by_title.find(title);
1623  return found != trackers_by_title.end() && found->second.has_active();
1624}
1625
1626void MetadataDatabase::WriteToDatabase(scoped_ptr<leveldb::WriteBatch> batch,
1627                                       const SyncStatusCallback& callback) {
1628  base::PostTaskAndReplyWithResult(
1629      task_runner_.get(),
1630      FROM_HERE,
1631      base::Bind(&leveldb::DB::Write,
1632                 base::Unretained(db_.get()),
1633                 leveldb::WriteOptions(),
1634                 base::Owned(batch.release())),
1635      base::Bind(&AdaptLevelDBStatusToSyncStatusCode, callback));
1636}
1637
1638scoped_ptr<base::ListValue> MetadataDatabase::DumpFiles(
1639    const std::string& app_id) {
1640  scoped_ptr<base::ListValue> files(new base::ListValue);
1641
1642  FileTracker app_root_tracker;
1643  if (!FindAppRootTracker(app_id, &app_root_tracker))
1644    return files.Pass();
1645
1646  std::vector<int64> stack;
1647  PushChildTrackersToContainer(
1648        trackers_by_parent_and_title_,
1649        app_root_tracker.tracker_id(),
1650        std::back_inserter(stack));
1651  while (!stack.empty()) {
1652    int64 tracker_id = stack.back();
1653    stack.pop_back();
1654    PushChildTrackersToContainer(
1655        trackers_by_parent_and_title_, tracker_id, std::back_inserter(stack));
1656
1657    FileTracker* tracker = tracker_by_id_[tracker_id];
1658    base::DictionaryValue* file = new DictionaryValue;
1659
1660    base::FilePath path;
1661    if (tracker->active()) {
1662      BuildPathForTracker(tracker->tracker_id(), &path);
1663    } else {
1664      BuildPathForTracker(tracker->parent_tracker_id(), &path);
1665      if (tracker->has_synced_details()) {
1666        path = path.Append(
1667            base::FilePath::FromUTF8Unsafe(tracker->synced_details().title()));
1668      } else {
1669        path = path.Append(FILE_PATH_LITERAL("unknown"));
1670      }
1671    }
1672    file->SetString("path", path.AsUTF8Unsafe());
1673    if (tracker->has_synced_details()) {
1674      file->SetString("title", tracker->synced_details().title());
1675      file->SetString("type",
1676                      FileKindToString(tracker->synced_details().file_kind()));
1677    }
1678
1679    base::DictionaryValue* details = new DictionaryValue;
1680    details->SetString("file_id", tracker->file_id());
1681    if (tracker->has_synced_details() &&
1682        tracker->synced_details().file_kind() == FILE_KIND_FILE)
1683      details->SetString("md5", tracker->synced_details().md5());
1684    details->SetString("active", tracker->active() ? "true" : "false");
1685    details->SetString("dirty", tracker->dirty() ? "true" : "false");
1686
1687    file->Set("details", details);
1688
1689    files->Append(file);
1690  }
1691
1692  return files.Pass();
1693}
1694
1695bool MetadataDatabase::HasNewerFileMetadata(const std::string& file_id,
1696                                            int64 change_id) {
1697  FileByID::const_iterator found = file_by_id_.find(file_id);
1698  if (found == file_by_id_.end())
1699    return false;
1700  DCHECK(found->second->has_details());
1701  return found->second->details().change_id() >= change_id;
1702}
1703
1704}  // namespace drive_backend
1705}  // namespace sync_file_system
1706