metadata_database.cc revision 1320f92c476a1ad9d19dba2a48c72b75566198e9 
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/command_line.h"
12#include "base/files/file_path.h"
13#include "base/files/file_util.h"
14#include "base/location.h"
15#include "base/memory/scoped_vector.h"
16#include "base/single_thread_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/thread_task_runner_handle.h"
23#include "base/threading/thread_restrictions.h"
24#include "chrome/browser/drive/drive_api_util.h"
25#include "chrome/browser/sync_file_system/drive_backend/drive_backend_constants.h"
26#include "chrome/browser/sync_file_system/drive_backend/drive_backend_util.h"
27#include "chrome/browser/sync_file_system/drive_backend/leveldb_wrapper.h"
28#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h"
29#include "chrome/browser/sync_file_system/drive_backend/metadata_database_index.h"
30#include "chrome/browser/sync_file_system/drive_backend/metadata_database_index_interface.h"
31#include "chrome/browser/sync_file_system/drive_backend/metadata_database_index_on_disk.h"
32#include "chrome/browser/sync_file_system/drive_backend/metadata_db_migration_util.h"
33#include "chrome/browser/sync_file_system/logger.h"
34#include "chrome/browser/sync_file_system/syncable_file_system_util.h"
35#include "google_apis/drive/drive_api_parser.h"
36#include "storage/common/fileapi/file_system_util.h"
37#include "third_party/leveldatabase/src/include/leveldb/db.h"
38#include "third_party/leveldatabase/src/include/leveldb/env.h"
39#include "third_party/leveldatabase/src/include/leveldb/status.h"
40#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
41
42namespace sync_file_system {
43namespace drive_backend {
44
45namespace {
46
47// Command line flag to disable on-disk indexing.
48const char kDisableMetadataDatabaseOnDisk[] = "disable-syncfs-on-disk-indexing";
49
50std::string FileKindToString(FileKind file_kind) {
51  switch (file_kind) {
52    case FILE_KIND_UNSUPPORTED:
53      return "unsupported";
54    case FILE_KIND_FILE:
55      return "file";
56    case FILE_KIND_FOLDER:
57      return "folder";
58  }
59
60  NOTREACHED();
61  return "unknown";
62}
63
64base::FilePath ReverseConcatPathComponents(
65    const std::vector<base::FilePath>& components) {
66  if (components.empty())
67    return base::FilePath(FILE_PATH_LITERAL("/")).NormalizePathSeparators();
68
69  size_t total_size = 0;
70  typedef std::vector<base::FilePath> PathComponents;
71  for (PathComponents::const_iterator itr = components.begin();
72       itr != components.end(); ++itr)
73    total_size += itr->value().size() + 1;
74
75  base::FilePath::StringType result;
76  result.reserve(total_size);
77  for (PathComponents::const_reverse_iterator itr = components.rbegin();
78       itr != components.rend(); ++itr) {
79    result.append(1, base::FilePath::kSeparators[0]);
80    result.append(itr->value());
81  }
82
83  return base::FilePath(result).NormalizePathSeparators();
84}
85
86void PopulateFileDetailsByFileResource(
87    const google_apis::FileResource& file_resource,
88    FileDetails* details) {
89  details->clear_parent_folder_ids();
90  for (std::vector<google_apis::ParentReference>::const_iterator itr =
91           file_resource.parents().begin();
92       itr != file_resource.parents().end();
93       ++itr) {
94    details->add_parent_folder_ids(itr->file_id());
95  }
96  details->set_title(file_resource.title());
97
98  if (file_resource.IsDirectory())
99    details->set_file_kind(FILE_KIND_FOLDER);
100  else if (file_resource.IsHostedDocument())
101    details->set_file_kind(FILE_KIND_UNSUPPORTED);
102  else
103    details->set_file_kind(FILE_KIND_FILE);
104
105  details->set_md5(file_resource.md5_checksum());
106  details->set_etag(file_resource.etag());
107  details->set_creation_time(file_resource.created_date().ToInternalValue());
108  details->set_modification_time(
109      file_resource.modified_date().ToInternalValue());
110  details->set_missing(file_resource.labels().is_trashed());
111}
112
113scoped_ptr<FileMetadata> CreateFileMetadataFromFileResource(
114    int64 change_id,
115    const google_apis::FileResource& resource) {
116  scoped_ptr<FileMetadata> file(new FileMetadata);
117  file->set_file_id(resource.file_id());
118
119  FileDetails* details = file->mutable_details();
120  details->set_change_id(change_id);
121
122  if (resource.labels().is_trashed()) {
123    details->set_missing(true);
124    return file.Pass();
125  }
126
127  PopulateFileDetailsByFileResource(resource, details);
128  return file.Pass();
129}
130
131scoped_ptr<FileMetadata> CreateFileMetadataFromChangeResource(
132    const google_apis::ChangeResource& change) {
133  scoped_ptr<FileMetadata> file(new FileMetadata);
134  file->set_file_id(change.file_id());
135
136  FileDetails* details = file->mutable_details();
137  details->set_change_id(change.change_id());
138
139  if (change.is_deleted()) {
140    details->set_missing(true);
141    return file.Pass();
142  }
143
144  PopulateFileDetailsByFileResource(*change.file(), details);
145  return file.Pass();
146}
147
148scoped_ptr<FileMetadata> CreateDeletedFileMetadata(
149    int64 change_id,
150    const std::string& file_id) {
151  scoped_ptr<FileMetadata> file(new FileMetadata);
152  file->set_file_id(file_id);
153
154  FileDetails* details = file->mutable_details();
155  details->set_change_id(change_id);
156  details->set_missing(true);
157  return file.Pass();
158}
159
160scoped_ptr<FileTracker> CreateSyncRootTracker(
161    int64 tracker_id,
162    const FileMetadata& sync_root_metadata) {
163  scoped_ptr<FileTracker> sync_root_tracker(new FileTracker);
164  sync_root_tracker->set_tracker_id(tracker_id);
165  sync_root_tracker->set_file_id(sync_root_metadata.file_id());
166  sync_root_tracker->set_parent_tracker_id(0);
167  sync_root_tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
168  sync_root_tracker->set_dirty(false);
169  sync_root_tracker->set_active(true);
170  sync_root_tracker->set_needs_folder_listing(false);
171  *sync_root_tracker->mutable_synced_details() = sync_root_metadata.details();
172  return sync_root_tracker.Pass();
173}
174
175scoped_ptr<FileTracker> CreateInitialAppRootTracker(
176    int64 tracker_id,
177    int64 parent_tracker_id,
178    const FileMetadata& app_root_metadata) {
179  scoped_ptr<FileTracker> app_root_tracker(new FileTracker);
180  app_root_tracker->set_tracker_id(tracker_id);
181  app_root_tracker->set_parent_tracker_id(parent_tracker_id);
182  app_root_tracker->set_file_id(app_root_metadata.file_id());
183  app_root_tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
184  app_root_tracker->set_dirty(false);
185  app_root_tracker->set_active(false);
186  app_root_tracker->set_needs_folder_listing(false);
187  *app_root_tracker->mutable_synced_details() = app_root_metadata.details();
188  return app_root_tracker.Pass();
189}
190
191scoped_ptr<FileTracker> CloneFileTracker(const FileTracker* obj) {
192  if (!obj)
193    return scoped_ptr<FileTracker>();
194  return scoped_ptr<FileTracker>(new FileTracker(*obj));
195}
196
197// Returns true if |db| has no content.
198bool IsDatabaseEmpty(LevelDBWrapper* db) {
199  DCHECK(db);
200  scoped_ptr<LevelDBWrapper::Iterator> itr(db->NewIterator());
201  itr->SeekToFirst();
202  return !itr->Valid();
203}
204
205SyncStatusCode OpenDatabase(const base::FilePath& path,
206                            leveldb::Env* env_override,
207                            scoped_ptr<LevelDBWrapper>* db_out,
208                            bool* created) {
209  base::ThreadRestrictions::AssertIOAllowed();
210  DCHECK(db_out);
211  DCHECK(created);
212  DCHECK(path.IsAbsolute());
213
214  leveldb::Options options;
215  options.max_open_files = 0;  // Use minimum.
216  options.create_if_missing = true;
217  if (env_override)
218    options.env = env_override;
219  leveldb::DB* db = NULL;
220  leveldb::Status db_status =
221      leveldb::DB::Open(options, path.AsUTF8Unsafe(), &db);
222  SyncStatusCode status = LevelDBStatusToSyncStatusCode(db_status);
223  if (status != SYNC_STATUS_OK) {
224    delete db;
225    return status;
226  }
227
228  db_out->reset(new LevelDBWrapper(make_scoped_ptr(db)));
229  *created = IsDatabaseEmpty(db_out->get());
230  return status;
231}
232
233SyncStatusCode MigrateDatabaseIfNeeded(LevelDBWrapper* db) {
234  // See metadata_database_index.cc for the database schema.
235  base::ThreadRestrictions::AssertIOAllowed();
236  DCHECK(db);
237  std::string value;
238  leveldb::Status status = db->Get(kDatabaseVersionKey, &value);
239  int64 version = 0;
240  if (status.ok()) {
241    if (!base::StringToInt64(value, &version))
242      return SYNC_DATABASE_ERROR_FAILED;
243  } else {
244    if (!status.IsNotFound())
245      return SYNC_DATABASE_ERROR_FAILED;
246  }
247
248  switch (version) {
249    case 0:
250    case 1:
251    case 2:
252      // Drop all data in old database and refetch them from the remote service.
253      NOTREACHED();
254      return SYNC_DATABASE_ERROR_FAILED;
255    case 3:
256      DCHECK_EQ(3, kCurrentDatabaseVersion);
257      // If MetadataDatabaseOnDisk is enabled, migration will be done in
258      // MetadataDatabaseOnDisk::Create().
259      // TODO(peria): Move the migration code (from v3 to v4) here.
260      return SYNC_STATUS_OK;
261    case 4:
262      if (CommandLine::ForCurrentProcess()->HasSwitch(
263              kDisableMetadataDatabaseOnDisk)) {
264        MigrateDatabaseFromV4ToV3(db->GetLevelDB());
265      }
266      return SYNC_STATUS_OK;
267    default:
268      return SYNC_DATABASE_ERROR_FAILED;
269  }
270}
271
272bool HasInvalidTitle(const std::string& title) {
273  return title.empty() ||
274      title.find('/') != std::string::npos ||
275      title.find('\\') != std::string::npos;
276}
277
278void MarkTrackerSetDirty(const TrackerIDSet& trackers,
279                         MetadataDatabaseIndexInterface* index) {
280  for (TrackerIDSet::const_iterator itr = trackers.begin();
281       itr != trackers.end(); ++itr) {
282    scoped_ptr<FileTracker> tracker(new FileTracker);
283    index->GetFileTracker(*itr, tracker.get());
284    if (tracker->dirty())
285      continue;
286    tracker->set_dirty(true);
287    index->StoreFileTracker(tracker.Pass());
288  }
289}
290
291void MarkTrackersDirtyByPath(int64 parent_tracker_id,
292                             const std::string& title,
293                             MetadataDatabaseIndexInterface* index) {
294  if (parent_tracker_id == kInvalidTrackerID || title.empty())
295    return;
296  MarkTrackerSetDirty(
297      index->GetFileTrackerIDsByParentAndTitle(parent_tracker_id, title),
298      index);
299}
300
301void MarkTrackersDirtyByFileID(const std::string& file_id,
302                               MetadataDatabaseIndexInterface* index) {
303  MarkTrackerSetDirty(index->GetFileTrackerIDsByFileID(file_id), index);
304}
305
306void MarkTrackersDirtyRecursively(int64 root_tracker_id,
307                                  MetadataDatabaseIndexInterface* index) {
308  std::vector<int64> stack;
309  stack.push_back(root_tracker_id);
310  while (!stack.empty()) {
311    int64 tracker_id = stack.back();
312    stack.pop_back();
313    AppendContents(index->GetFileTrackerIDsByParent(tracker_id), &stack);
314
315    scoped_ptr<FileTracker> tracker(new FileTracker);
316    index->GetFileTracker(tracker_id, tracker.get());
317    tracker->set_dirty(true);
318
319    index->StoreFileTracker(tracker.Pass());
320  }
321}
322
323void RemoveAllDescendantTrackers(int64 root_tracker_id,
324                                 MetadataDatabaseIndexInterface* index) {
325  std::vector<int64> pending_trackers;
326  AppendContents(index->GetFileTrackerIDsByParent(root_tracker_id),
327                 &pending_trackers);
328
329  std::vector<int64> to_be_removed;
330
331  // List trackers to remove.
332  while (!pending_trackers.empty()) {
333    int64 tracker_id = pending_trackers.back();
334    pending_trackers.pop_back();
335    AppendContents(index->GetFileTrackerIDsByParent(tracker_id),
336                   &pending_trackers);
337    to_be_removed.push_back(tracker_id);
338  }
339
340  // Remove trackers in the reversed order.
341  base::hash_set<std::string> affected_file_ids;
342  for (std::vector<int64>::reverse_iterator itr = to_be_removed.rbegin();
343       itr != to_be_removed.rend(); ++itr) {
344    FileTracker tracker;
345    index->GetFileTracker(*itr, &tracker);
346    affected_file_ids.insert(tracker.file_id());
347    index->RemoveFileTracker(*itr);
348  }
349
350  for (base::hash_set<std::string>::iterator itr = affected_file_ids.begin();
351       itr != affected_file_ids.end(); ++itr) {
352    TrackerIDSet trackers = index->GetFileTrackerIDsByFileID(*itr);
353    if (trackers.empty()) {
354      // Remove metadata that no longer has any tracker.
355      index->RemoveFileMetadata(*itr);
356    } else {
357      MarkTrackerSetDirty(trackers, index);
358    }
359  }
360}
361
362bool FilterFileTrackersByParent(
363    const MetadataDatabaseIndexInterface* index,
364    const TrackerIDSet& trackers,
365    int64 parent_tracker_id,
366    FileTracker* tracker_out) {
367  FileTracker tracker;
368  for (TrackerIDSet::const_iterator itr = trackers.begin();
369       itr != trackers.end(); ++itr) {
370    if (!index->GetFileTracker(*itr, &tracker)) {
371      NOTREACHED();
372      continue;
373    }
374
375    if (tracker.parent_tracker_id() == parent_tracker_id) {
376      if (tracker_out)
377        tracker_out->CopyFrom(tracker);
378      return true;
379    }
380  }
381  return false;
382}
383
384bool FilterFileTrackersByParentAndTitle(
385    const MetadataDatabaseIndexInterface* index,
386    const TrackerIDSet& trackers,
387    int64 parent_tracker_id,
388    const std::string& title,
389    FileTracker* result) {
390  bool found = false;
391  for (TrackerIDSet::const_iterator itr = trackers.begin();
392       itr != trackers.end(); ++itr) {
393    FileTracker tracker;
394    if (!index->GetFileTracker(*itr, &tracker)) {
395      NOTREACHED();
396      continue;
397    }
398
399    if (tracker.parent_tracker_id() != parent_tracker_id)
400      continue;
401
402    if (tracker.has_synced_details() &&
403        tracker.synced_details().title() != title)
404      continue;
405
406    // Prioritize trackers that has |synced_details| when |trackers| has
407    // multiple candidates.
408    if (!found || tracker.has_synced_details()) {
409      found = true;
410      if (result)
411        result->CopyFrom(tracker);
412      if (!result || result->has_synced_details())
413        return found;
414    }
415  }
416
417  return found;
418}
419
420bool FilterFileTrackersByFileID(
421    const MetadataDatabaseIndexInterface* index,
422    const TrackerIDSet& trackers,
423    const std::string& file_id,
424    FileTracker* tracker_out) {
425  FileTracker tracker;
426  for (TrackerIDSet::const_iterator itr = trackers.begin();
427       itr != trackers.end(); ++itr) {
428    if (!index->GetFileTracker(*itr, &tracker)) {
429      NOTREACHED();
430      continue;
431    }
432
433    if (tracker.file_id() == file_id) {
434      if (tracker_out)
435        tracker_out->CopyFrom(tracker);
436      return true;
437    }
438  }
439  return false;
440}
441
442enum DirtyingOption {
443  MARK_NOTHING_DIRTY = 0,
444  MARK_ITSELF_DIRTY = 1 << 0,
445  MARK_SAME_FILE_ID_TRACKERS_DIRTY = 1 << 1,
446  MARK_SAME_PATH_TRACKERS_DIRTY = 1 << 2,
447};
448
449void ActivateFileTracker(int64 tracker_id,
450                         int dirtying_options,
451                         MetadataDatabaseIndexInterface* index) {
452  DCHECK(dirtying_options == MARK_NOTHING_DIRTY ||
453         dirtying_options == MARK_ITSELF_DIRTY);
454
455  scoped_ptr<FileTracker> tracker(new FileTracker);
456  index->GetFileTracker(tracker_id, tracker.get());
457  tracker->set_active(true);
458  if (dirtying_options & MARK_ITSELF_DIRTY) {
459    tracker->set_dirty(true);
460    tracker->set_needs_folder_listing(
461        tracker->has_synced_details() &&
462        tracker->synced_details().file_kind() == FILE_KIND_FOLDER);
463  } else {
464    tracker->set_dirty(false);
465    tracker->set_needs_folder_listing(false);
466  }
467
468  index->StoreFileTracker(tracker.Pass());
469}
470
471void DeactivateFileTracker(int64 tracker_id,
472                           int dirtying_options,
473                           MetadataDatabaseIndexInterface* index) {
474  RemoveAllDescendantTrackers(tracker_id, index);
475
476  scoped_ptr<FileTracker> tracker(new FileTracker);
477  index->GetFileTracker(tracker_id, tracker.get());
478
479  if (dirtying_options & MARK_SAME_FILE_ID_TRACKERS_DIRTY)
480    MarkTrackersDirtyByFileID(tracker->file_id(), index);
481  if (dirtying_options & MARK_SAME_PATH_TRACKERS_DIRTY) {
482    MarkTrackersDirtyByPath(tracker->parent_tracker_id(),
483                            GetTrackerTitle(*tracker), index);
484  }
485
486  tracker->set_dirty(dirtying_options & MARK_ITSELF_DIRTY);
487  tracker->set_active(false);
488  index->StoreFileTracker(tracker.Pass());
489}
490
491void RemoveFileTracker(int64 tracker_id,
492                       int dirtying_options,
493                       MetadataDatabaseIndexInterface* index) {
494  DCHECK(!(dirtying_options & MARK_ITSELF_DIRTY));
495
496  FileTracker tracker;
497  if (!index->GetFileTracker(tracker_id, &tracker))
498    return;
499
500  std::string file_id = tracker.file_id();
501  int64 parent_tracker_id = tracker.parent_tracker_id();
502  std::string title = GetTrackerTitle(tracker);
503
504  RemoveAllDescendantTrackers(tracker_id, index);
505  index->RemoveFileTracker(tracker_id);
506
507  if (dirtying_options & MARK_SAME_FILE_ID_TRACKERS_DIRTY)
508    MarkTrackersDirtyByFileID(file_id, index);
509  if (dirtying_options & MARK_SAME_PATH_TRACKERS_DIRTY)
510    MarkTrackersDirtyByPath(parent_tracker_id, title, index);
511
512  if (index->GetFileTrackerIDsByFileID(file_id).empty()) {
513    index->RemoveFileMetadata(file_id);
514  }
515}
516
517}  // namespace
518
519// static
520scoped_ptr<MetadataDatabase> MetadataDatabase::Create(
521    const base::FilePath& database_path,
522    leveldb::Env* env_override,
523    SyncStatusCode* status_out) {
524  bool enable_on_disk_index = !CommandLine::ForCurrentProcess()->HasSwitch(
525      kDisableMetadataDatabaseOnDisk);
526  return CreateInternal(database_path, env_override, enable_on_disk_index,
527                        status_out);
528}
529
530// static
531scoped_ptr<MetadataDatabase> MetadataDatabase::CreateInternal(
532    const base::FilePath& database_path,
533    leveldb::Env* env_override,
534    bool enable_on_disk_index,
535    SyncStatusCode* status_out) {
536  scoped_ptr<MetadataDatabase> metadata_database(
537      new MetadataDatabase(database_path,
538                           enable_on_disk_index,
539                           env_override));
540
541  SyncStatusCode status = metadata_database->Initialize();
542  if (status == SYNC_DATABASE_ERROR_FAILED) {
543    // Delete the previous instance to avoid creating a LevelDB instance for
544    // the same path.
545    metadata_database.reset();
546
547    metadata_database.reset(
548        new MetadataDatabase(database_path,
549                             enable_on_disk_index,
550                             env_override));
551    status = metadata_database->Initialize();
552  }
553
554  if (status != SYNC_STATUS_OK)
555    metadata_database.reset();
556
557  *status_out = status;
558  return metadata_database.Pass();
559}
560
561// static
562SyncStatusCode MetadataDatabase::CreateForTesting(
563    scoped_ptr<LevelDBWrapper> db,
564    bool enable_on_disk_index,
565    scoped_ptr<MetadataDatabase>* metadata_database_out) {
566  scoped_ptr<MetadataDatabase> metadata_database(
567      new MetadataDatabase(base::FilePath(),
568                           enable_on_disk_index,
569                           NULL));
570  metadata_database->db_ = db.Pass();
571  SyncStatusCode status = metadata_database->Initialize();
572  if (status == SYNC_STATUS_OK)
573    *metadata_database_out = metadata_database.Pass();
574  return status;
575}
576
577MetadataDatabase::~MetadataDatabase() {
578}
579
580// static
581void MetadataDatabase::ClearDatabase(
582    scoped_ptr<MetadataDatabase> metadata_database) {
583  DCHECK(metadata_database);
584  base::FilePath database_path = metadata_database->database_path_;
585  DCHECK(!database_path.empty());
586  metadata_database.reset();
587
588  base::DeleteFile(database_path, true /* recursive */);
589}
590
591int64 MetadataDatabase::GetLargestFetchedChangeID() const {
592  return index_->GetLargestChangeID();
593}
594
595int64 MetadataDatabase::GetSyncRootTrackerID() const {
596  return index_->GetSyncRootTrackerID();
597}
598
599int64 MetadataDatabase::GetLargestKnownChangeID() const {
600  DCHECK_LE(GetLargestFetchedChangeID(), largest_known_change_id_);
601  return largest_known_change_id_;
602}
603
604void MetadataDatabase::UpdateLargestKnownChangeID(int64 change_id) {
605  if (largest_known_change_id_ < change_id)
606    largest_known_change_id_ = change_id;
607}
608
609bool MetadataDatabase::HasSyncRoot() const {
610  return index_->GetSyncRootTrackerID() != kInvalidTrackerID;
611}
612
613SyncStatusCode MetadataDatabase::PopulateInitialData(
614    int64 largest_change_id,
615    const google_apis::FileResource& sync_root_folder,
616    const ScopedVector<google_apis::FileResource>& app_root_folders) {
617  index_->SetLargestChangeID(largest_change_id);
618  UpdateLargestKnownChangeID(largest_change_id);
619
620  AttachSyncRoot(sync_root_folder);
621  for (size_t i = 0; i < app_root_folders.size(); ++i)
622    AttachInitialAppRoot(*app_root_folders[i]);
623
624  return WriteToDatabase();
625}
626
627bool MetadataDatabase::IsAppEnabled(const std::string& app_id) const {
628  int64 tracker_id = index_->GetAppRootTracker(app_id);
629  if (tracker_id == kInvalidTrackerID)
630    return false;
631
632  FileTracker tracker;
633  if (!index_->GetFileTracker(tracker_id, &tracker))
634    return false;
635  return tracker.tracker_kind() == TRACKER_KIND_APP_ROOT;
636}
637
638SyncStatusCode MetadataDatabase::RegisterApp(const std::string& app_id,
639                                   const std::string& folder_id) {
640  if (index_->GetAppRootTracker(app_id)) {
641    // The app-root is already registered.
642    return SYNC_STATUS_OK;
643  }
644
645  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(folder_id);
646  if (trackers.empty()) {
647    return SYNC_DATABASE_ERROR_NOT_FOUND;
648  }
649
650  if (trackers.has_active()) {
651    // The folder is tracked by another tracker.
652    util::Log(logging::LOG_WARNING, FROM_HERE,
653              "Failed to register App for %s", app_id.c_str());
654    return SYNC_STATUS_HAS_CONFLICT;
655  }
656
657  int64 sync_root_tracker_id = index_->GetSyncRootTrackerID();
658  if (!sync_root_tracker_id) {
659    util::Log(logging::LOG_WARNING, FROM_HERE,
660              "Sync-root needs to be set up before registering app-root");
661    return SYNC_DATABASE_ERROR_NOT_FOUND;
662  }
663
664  scoped_ptr<FileTracker> tracker(new FileTracker);
665  if (!FilterFileTrackersByParent(index_.get(), trackers,
666                                  sync_root_tracker_id, tracker.get())) {
667    return SYNC_DATABASE_ERROR_NOT_FOUND;
668  }
669
670  tracker->set_app_id(app_id);
671  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
672  tracker->set_active(true);
673  tracker->set_needs_folder_listing(true);
674  tracker->set_dirty(true);
675
676  index_->StoreFileTracker(tracker.Pass());
677  return WriteToDatabase();
678}
679
680SyncStatusCode MetadataDatabase::DisableApp(const std::string& app_id) {
681  int64 tracker_id = index_->GetAppRootTracker(app_id);
682  scoped_ptr<FileTracker> tracker(new FileTracker);
683  if (!index_->GetFileTracker(tracker_id, tracker.get())) {
684    return SYNC_DATABASE_ERROR_NOT_FOUND;
685  }
686
687  if (tracker->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
688    return SYNC_STATUS_OK;
689  }
690
691  DCHECK_EQ(TRACKER_KIND_APP_ROOT, tracker->tracker_kind());
692  DCHECK(tracker->active());
693
694  // Keep the app-root tracker active (but change the tracker_kind) so that
695  // other conflicting trackers won't become active.
696  tracker->set_tracker_kind(TRACKER_KIND_DISABLED_APP_ROOT);
697
698  index_->StoreFileTracker(tracker.Pass());
699  return WriteToDatabase();
700}
701
702SyncStatusCode MetadataDatabase::EnableApp(const std::string& app_id) {
703  int64 tracker_id = index_->GetAppRootTracker(app_id);
704  scoped_ptr<FileTracker> tracker(new FileTracker);
705  if (!index_->GetFileTracker(tracker_id, tracker.get())) {
706    return SYNC_DATABASE_ERROR_NOT_FOUND;
707  }
708
709  if (tracker->tracker_kind() == TRACKER_KIND_APP_ROOT) {
710    return SYNC_STATUS_OK;
711  }
712
713  DCHECK_EQ(TRACKER_KIND_DISABLED_APP_ROOT, tracker->tracker_kind());
714  DCHECK(tracker->active());
715
716  tracker->set_tracker_kind(TRACKER_KIND_APP_ROOT);
717  index_->StoreFileTracker(tracker.Pass());
718
719  MarkTrackersDirtyRecursively(tracker_id, index_.get());
720  return WriteToDatabase();
721}
722
723SyncStatusCode MetadataDatabase::UnregisterApp(const std::string& app_id) {
724  int64 tracker_id = index_->GetAppRootTracker(app_id);
725  scoped_ptr<FileTracker> tracker(new FileTracker);
726  if (!index_->GetFileTracker(tracker_id, tracker.get()) ||
727      tracker->tracker_kind() == TRACKER_KIND_REGULAR) {
728    return SYNC_STATUS_OK;
729  }
730
731  RemoveAllDescendantTrackers(tracker_id, index_.get());
732
733  tracker->clear_app_id();
734  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
735  tracker->set_active(false);
736  tracker->set_dirty(true);
737
738  index_->StoreFileTracker(tracker.Pass());
739  return WriteToDatabase();
740}
741
742bool MetadataDatabase::FindAppRootTracker(const std::string& app_id,
743                                          FileTracker* tracker_out) const {
744  int64 app_root_tracker_id = index_->GetAppRootTracker(app_id);
745  if (!app_root_tracker_id)
746    return false;
747
748  if (tracker_out &&
749      !index_->GetFileTracker(app_root_tracker_id, tracker_out)) {
750    NOTREACHED();
751    return false;
752  }
753
754  return true;
755}
756
757bool MetadataDatabase::FindFileByFileID(const std::string& file_id,
758                                        FileMetadata* metadata_out) const {
759  return index_->GetFileMetadata(file_id, metadata_out);
760}
761
762bool MetadataDatabase::FindTrackersByFileID(const std::string& file_id,
763                                            TrackerIDSet* trackers_out) const {
764  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(file_id);
765  if (trackers.empty())
766    return false;
767
768  if (trackers_out)
769    std::swap(trackers, *trackers_out);
770  return true;
771}
772
773bool MetadataDatabase::FindTrackersByParentAndTitle(
774    int64 parent_tracker_id,
775    const std::string& title,
776    TrackerIDSet* trackers_out) const {
777  TrackerIDSet trackers =
778      index_->GetFileTrackerIDsByParentAndTitle(parent_tracker_id, title);
779  if (trackers.empty())
780    return false;
781
782  if (trackers_out)
783    std::swap(trackers, *trackers_out);
784  return true;
785}
786
787bool MetadataDatabase::FindTrackerByTrackerID(int64 tracker_id,
788                                              FileTracker* tracker_out) const {
789  return index_->GetFileTracker(tracker_id, tracker_out);
790}
791
792bool MetadataDatabase::BuildPathForTracker(int64 tracker_id,
793                                           base::FilePath* path) const {
794  FileTracker current;
795  if (!FindTrackerByTrackerID(tracker_id, &current) || !current.active())
796    return false;
797
798  std::vector<base::FilePath> components;
799  while (!IsAppRoot(current)) {
800    std::string title = GetTrackerTitle(current);
801    if (title.empty())
802      return false;
803    components.push_back(base::FilePath::FromUTF8Unsafe(title));
804    if (!FindTrackerByTrackerID(current.parent_tracker_id(), &current) ||
805        !current.active())
806      return false;
807  }
808
809  if (path)
810    *path = ReverseConcatPathComponents(components);
811
812  return true;
813}
814
815base::FilePath MetadataDatabase::BuildDisplayPathForTracker(
816    const FileTracker& tracker) const {
817  base::FilePath path;
818  if (tracker.active()) {
819    BuildPathForTracker(tracker.tracker_id(), &path);
820    return path;
821  }
822  BuildPathForTracker(tracker.parent_tracker_id(), &path);
823  if (tracker.has_synced_details()) {
824    path = path.Append(
825        base::FilePath::FromUTF8Unsafe(tracker.synced_details().title()));
826  } else {
827    path = path.Append(FILE_PATH_LITERAL("<unknown>"));
828  }
829  return path;
830}
831
832bool MetadataDatabase::FindNearestActiveAncestor(
833    const std::string& app_id,
834    const base::FilePath& full_path,
835    FileTracker* tracker_out,
836    base::FilePath* path_out) const {
837  DCHECK(tracker_out);
838  DCHECK(path_out);
839
840  if (full_path.IsAbsolute() ||
841      !FindAppRootTracker(app_id, tracker_out) ||
842      tracker_out->tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT) {
843    return false;
844  }
845
846  std::vector<base::FilePath::StringType> components;
847  full_path.GetComponents(&components);
848  path_out->clear();
849
850  for (size_t i = 0; i < components.size(); ++i) {
851    const std::string title = base::FilePath(components[i]).AsUTF8Unsafe();
852    TrackerIDSet trackers;
853    if (!FindTrackersByParentAndTitle(
854            tracker_out->tracker_id(), title, &trackers) ||
855        !trackers.has_active()) {
856      return true;
857    }
858
859    FileTracker tracker;
860    index_->GetFileTracker(trackers.active_tracker(), &tracker);
861
862    DCHECK(tracker.has_synced_details());
863    const FileDetails& details = tracker.synced_details();
864    if (details.file_kind() != FILE_KIND_FOLDER && i != components.size() - 1) {
865      // This non-last component indicates file. Give up search.
866      return true;
867    }
868
869    tracker_out->CopyFrom(tracker);
870    *path_out = path_out->Append(components[i]);
871  }
872
873  return true;
874}
875
876SyncStatusCode MetadataDatabase::UpdateByChangeList(
877    int64 largest_change_id,
878    ScopedVector<google_apis::ChangeResource> changes) {
879  DCHECK_LE(index_->GetLargestChangeID(), largest_change_id);
880
881  for (size_t i = 0; i < changes.size(); ++i) {
882    const google_apis::ChangeResource& change = *changes[i];
883    if (HasNewerFileMetadata(change.file_id(), change.change_id()))
884      continue;
885
886    scoped_ptr<FileMetadata> metadata(
887        CreateFileMetadataFromChangeResource(change));
888    UpdateByFileMetadata(FROM_HERE, metadata.Pass(),
889                         UPDATE_TRACKER_FOR_UNSYNCED_FILE);
890  }
891
892  UpdateLargestKnownChangeID(largest_change_id);
893  index_->SetLargestChangeID(largest_change_id);
894  return WriteToDatabase();
895}
896
897SyncStatusCode MetadataDatabase::UpdateByFileResource(
898    const google_apis::FileResource& resource) {
899  scoped_ptr<FileMetadata> metadata(
900      CreateFileMetadataFromFileResource(
901          GetLargestKnownChangeID(), resource));
902  UpdateByFileMetadata(FROM_HERE, metadata.Pass(),
903                       UPDATE_TRACKER_FOR_UNSYNCED_FILE);
904  return WriteToDatabase();
905}
906
907SyncStatusCode MetadataDatabase::UpdateByFileResourceList(
908    ScopedVector<google_apis::FileResource> resources) {
909  for (size_t i = 0; i < resources.size(); ++i) {
910    scoped_ptr<FileMetadata> metadata(
911        CreateFileMetadataFromFileResource(
912            GetLargestKnownChangeID(), *resources[i]));
913    UpdateByFileMetadata(FROM_HERE, metadata.Pass(),
914                         UPDATE_TRACKER_FOR_UNSYNCED_FILE);
915  }
916  return WriteToDatabase();
917}
918
919SyncStatusCode MetadataDatabase::UpdateByDeletedRemoteFile(
920    const std::string& file_id) {
921  scoped_ptr<FileMetadata> metadata(
922      CreateDeletedFileMetadata(GetLargestKnownChangeID(), file_id));
923  UpdateByFileMetadata(FROM_HERE, metadata.Pass(),
924                       UPDATE_TRACKER_FOR_UNSYNCED_FILE);
925  return WriteToDatabase();
926}
927
928SyncStatusCode MetadataDatabase::UpdateByDeletedRemoteFileList(
929    const FileIDList& file_ids) {
930  for (FileIDList::const_iterator itr = file_ids.begin();
931       itr != file_ids.end(); ++itr) {
932    scoped_ptr<FileMetadata> metadata(
933        CreateDeletedFileMetadata(GetLargestKnownChangeID(), *itr));
934    UpdateByFileMetadata(FROM_HERE, metadata.Pass(),
935                         UPDATE_TRACKER_FOR_UNSYNCED_FILE);
936  }
937  return WriteToDatabase();
938}
939
940SyncStatusCode MetadataDatabase::ReplaceActiveTrackerWithNewResource(
941    int64 parent_tracker_id,
942    const google_apis::FileResource& resource) {
943  DCHECK(!index_->GetFileMetadata(resource.file_id(), NULL));
944  DCHECK(index_->GetFileTracker(parent_tracker_id, NULL));
945
946  UpdateByFileMetadata(
947      FROM_HERE,
948      CreateFileMetadataFromFileResource(GetLargestKnownChangeID(), resource),
949      UPDATE_TRACKER_FOR_SYNCED_FILE);
950
951  DCHECK(index_->GetFileMetadata(resource.file_id(), NULL));
952  DCHECK(!index_->GetFileTrackerIDsByFileID(resource.file_id()).has_active());
953
954  TrackerIDSet same_path_trackers =
955      index_->GetFileTrackerIDsByParentAndTitle(
956          parent_tracker_id, resource.title());
957  FileTracker to_be_activated;
958  if (!FilterFileTrackersByFileID(index_.get(), same_path_trackers,
959                                  resource.file_id(), &to_be_activated)) {
960    NOTREACHED();
961    return SYNC_STATUS_FAILED;
962  }
963
964  int64 tracker_id = to_be_activated.tracker_id();
965  if (same_path_trackers.has_active()) {
966    DeactivateFileTracker(same_path_trackers.active_tracker(),
967                          MARK_ITSELF_DIRTY |
968                          MARK_SAME_FILE_ID_TRACKERS_DIRTY,
969                          index_.get());
970  }
971
972  ActivateFileTracker(tracker_id, MARK_NOTHING_DIRTY, index_.get());
973  return WriteToDatabase();
974}
975
976SyncStatusCode MetadataDatabase::PopulateFolderByChildList(
977    const std::string& folder_id,
978    const FileIDList& child_file_ids) {
979  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(folder_id);
980  if (!trackers.has_active()) {
981    // It's OK that there is no folder to populate its children.
982    // Inactive folders should ignore their contents updates.
983    return SYNC_STATUS_OK;
984  }
985
986  scoped_ptr<FileTracker> folder_tracker(new FileTracker);
987  if (!index_->GetFileTracker(trackers.active_tracker(),
988                              folder_tracker.get())) {
989    NOTREACHED();
990    return SYNC_STATUS_FAILED;
991  }
992
993  base::hash_set<std::string> children(child_file_ids.begin(),
994                                       child_file_ids.end());
995
996  std::vector<int64> known_children =
997      index_->GetFileTrackerIDsByParent(folder_tracker->tracker_id());
998  for (size_t i = 0; i < known_children.size(); ++i) {
999    FileTracker tracker;
1000    if (!index_->GetFileTracker(known_children[i], &tracker)) {
1001      NOTREACHED();
1002      continue;
1003    }
1004    children.erase(tracker.file_id());
1005  }
1006
1007  for (base::hash_set<std::string>::const_iterator itr = children.begin();
1008       itr != children.end(); ++itr)
1009    CreateTrackerForParentAndFileID(*folder_tracker, *itr);
1010  folder_tracker->set_needs_folder_listing(false);
1011  if (folder_tracker->dirty() && !ShouldKeepDirty(*folder_tracker))
1012    folder_tracker->set_dirty(false);
1013  index_->StoreFileTracker(folder_tracker.Pass());
1014
1015  return WriteToDatabase();
1016}
1017
1018SyncStatusCode MetadataDatabase::UpdateTracker(
1019    int64 tracker_id,
1020    const FileDetails& updated_details) {
1021  FileTracker tracker;
1022  if (!index_->GetFileTracker(tracker_id, &tracker)) {
1023    return SYNC_DATABASE_ERROR_NOT_FOUND;
1024  }
1025
1026  // Check if the tracker is to be deleted.
1027  if (updated_details.missing()) {
1028    FileMetadata metadata;
1029    if (!index_->GetFileMetadata(tracker.file_id(), &metadata) ||
1030        metadata.details().missing()) {
1031      // Both the tracker and metadata have the missing flag, now it's safe to
1032      // delete the |tracker|.
1033      RemoveFileTracker(tracker_id,
1034                        MARK_SAME_FILE_ID_TRACKERS_DIRTY |
1035                        MARK_SAME_PATH_TRACKERS_DIRTY,
1036                        index_.get());
1037      return WriteToDatabase();
1038    }
1039  }
1040
1041  // Sync-root deletion should be handled separately by SyncEngine.
1042  DCHECK(tracker_id != GetSyncRootTrackerID() ||
1043         (tracker.has_synced_details() &&
1044          tracker.synced_details().title() == updated_details.title() &&
1045          !updated_details.missing()));
1046
1047  if (tracker_id != GetSyncRootTrackerID()) {
1048    // Check if the tracker's parent is still in |parent_tracker_ids|.
1049    // If not, there should exist another tracker for the new parent, so delete
1050    // old tracker.
1051    FileTracker parent_tracker;
1052    index_->GetFileTracker(tracker.parent_tracker_id(), &parent_tracker);
1053
1054    if (!HasFileAsParent(updated_details, parent_tracker.file_id())) {
1055      RemoveFileTracker(tracker.tracker_id(),
1056                        MARK_SAME_PATH_TRACKERS_DIRTY,
1057                        index_.get());
1058      return WriteToDatabase();
1059    }
1060
1061    if (tracker.has_synced_details()) {
1062      // Check if the tracker was retitled.  If it was, there should exist
1063      // another tracker for the new title, so delete the tracker being updated.
1064      if (tracker.synced_details().title() != updated_details.title()) {
1065        RemoveFileTracker(tracker.tracker_id(),
1066                          MARK_SAME_FILE_ID_TRACKERS_DIRTY,
1067                          index_.get());
1068        return WriteToDatabase();
1069      }
1070    } else {
1071      // Check if any other tracker exists has the same parent, title and
1072      // file_id to the updated tracker.  If it exists, delete the tracker being
1073      // updated.
1074      if (FilterFileTrackersByFileID(
1075              index_.get(),
1076              index_->GetFileTrackerIDsByParentAndTitle(
1077                  parent_tracker.tracker_id(),
1078                  updated_details.title()),
1079              tracker.file_id(),
1080              NULL)) {
1081        RemoveFileTracker(tracker.tracker_id(),
1082                          MARK_NOTHING_DIRTY,
1083                          index_.get());
1084        return WriteToDatabase();
1085      }
1086    }
1087  }
1088
1089  scoped_ptr<FileTracker> updated_tracker = CloneFileTracker(&tracker);
1090  *updated_tracker->mutable_synced_details() = updated_details;
1091
1092  bool should_promote = false;
1093
1094  // Activate the tracker if:
1095  //   - There is no active tracker that tracks |tracker->file_id()|.
1096  //   - There is no active tracker that has the same |parent| and |title|.
1097  if (!tracker.active() && CanActivateTracker(tracker)) {
1098    updated_tracker->set_active(true);
1099    updated_tracker->set_dirty(true);
1100    updated_tracker->set_needs_folder_listing(
1101        tracker.synced_details().file_kind() == FILE_KIND_FOLDER);
1102    should_promote = true;
1103  } else if (tracker.dirty() && !ShouldKeepDirty(tracker)) {
1104    updated_tracker->set_dirty(false);
1105  }
1106  index_->StoreFileTracker(updated_tracker.Pass());
1107  if (should_promote)
1108    index_->PromoteDemotedDirtyTracker(tracker_id);
1109
1110  return WriteToDatabase();
1111}
1112
1113MetadataDatabase::ActivationStatus MetadataDatabase::TryActivateTracker(
1114    int64 parent_tracker_id,
1115    const std::string& file_id,
1116    SyncStatusCode* status_out) {
1117  FileMetadata metadata;
1118  if (!index_->GetFileMetadata(file_id, &metadata)) {
1119    NOTREACHED();
1120    *status_out = SYNC_STATUS_FAILED;
1121    return ACTIVATION_PENDING;
1122  }
1123  std::string title = metadata.details().title();
1124  DCHECK(!HasInvalidTitle(title));
1125
1126  TrackerIDSet same_file_id_trackers =
1127      index_->GetFileTrackerIDsByFileID(file_id);
1128  scoped_ptr<FileTracker> tracker_to_be_activated(new FileTracker);
1129  FilterFileTrackersByParentAndTitle(
1130      index_.get(), same_file_id_trackers, parent_tracker_id,
1131      title, tracker_to_be_activated.get());
1132
1133  // Check if there is another active tracker that tracks |file_id|.
1134  // This can happen when the tracked file has multiple parents.
1135  // In this case, report the failure to the caller.
1136  if (!tracker_to_be_activated->active() && same_file_id_trackers.has_active())
1137    return ACTIVATION_FAILED_ANOTHER_ACTIVE_TRACKER;
1138
1139  if (!tracker_to_be_activated->active()) {
1140    // Check if there exists another active tracker that has the same path to
1141    // the tracker.  If there is, deactivate it, assuming the caller already
1142    // overrides local file with newly added file,
1143    TrackerIDSet same_title_trackers =
1144        index_->GetFileTrackerIDsByParentAndTitle(parent_tracker_id, title);
1145    if (same_title_trackers.has_active()) {
1146      RemoveAllDescendantTrackers(same_title_trackers.active_tracker(),
1147                                  index_.get());
1148
1149      scoped_ptr<FileTracker> tracker_to_be_deactivated(new FileTracker);
1150      if (index_->GetFileTracker(same_title_trackers.active_tracker(),
1151                                 tracker_to_be_deactivated.get())) {
1152        const std::string file_id = tracker_to_be_deactivated->file_id();
1153        tracker_to_be_deactivated->set_active(false);
1154        index_->StoreFileTracker(tracker_to_be_deactivated.Pass());
1155
1156        MarkTrackersDirtyByFileID(file_id, index_.get());
1157      } else {
1158        NOTREACHED();
1159      }
1160    }
1161  }
1162
1163  tracker_to_be_activated->set_dirty(false);
1164  tracker_to_be_activated->set_active(true);
1165  *tracker_to_be_activated->mutable_synced_details() = metadata.details();
1166  if (tracker_to_be_activated->synced_details().file_kind() ==
1167      FILE_KIND_FOLDER) {
1168    tracker_to_be_activated->set_needs_folder_listing(true);
1169  }
1170  tracker_to_be_activated->set_dirty(false);
1171
1172  index_->StoreFileTracker(tracker_to_be_activated.Pass());
1173
1174  *status_out = WriteToDatabase();
1175  return ACTIVATION_PENDING;
1176}
1177
1178void MetadataDatabase::DemoteTracker(int64 tracker_id) {
1179  index_->DemoteDirtyTracker(tracker_id);
1180  WriteToDatabase();
1181}
1182
1183bool MetadataDatabase::PromoteDemotedTrackers() {
1184  bool promoted = index_->PromoteDemotedDirtyTrackers();
1185  WriteToDatabase();
1186  return promoted;
1187}
1188
1189void MetadataDatabase::PromoteDemotedTracker(int64 tracker_id) {
1190  index_->PromoteDemotedDirtyTracker(tracker_id);
1191  WriteToDatabase();
1192}
1193
1194bool MetadataDatabase::GetDirtyTracker(
1195    FileTracker* tracker_out) const {
1196  int64 dirty_tracker_id = index_->PickDirtyTracker();
1197  if (!dirty_tracker_id)
1198    return false;
1199
1200  if (tracker_out) {
1201    if (!index_->GetFileTracker(dirty_tracker_id, tracker_out)) {
1202      NOTREACHED();
1203      return false;
1204    }
1205  }
1206  return true;
1207}
1208
1209bool MetadataDatabase::HasDemotedDirtyTracker() const {
1210  return index_->HasDemotedDirtyTracker();
1211}
1212
1213bool MetadataDatabase::HasDirtyTracker() const {
1214  return index_->PickDirtyTracker() != kInvalidTrackerID;
1215}
1216
1217size_t MetadataDatabase::CountDirtyTracker() const {
1218  return index_->CountDirtyTracker();
1219}
1220
1221bool MetadataDatabase::GetMultiParentFileTrackers(std::string* file_id_out,
1222                                                  TrackerIDSet* trackers_out) {
1223  DCHECK(file_id_out);
1224  DCHECK(trackers_out);
1225
1226  std::string file_id = index_->PickMultiTrackerFileID();
1227  if (file_id.empty())
1228    return false;
1229
1230  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(file_id);
1231  if (trackers.size() <= 1) {
1232    NOTREACHED();
1233    return false;
1234  }
1235
1236  *file_id_out = file_id;
1237  std::swap(*trackers_out, trackers);
1238  return true;
1239}
1240
1241size_t MetadataDatabase::CountFileMetadata() const {
1242  return index_->CountFileMetadata();
1243}
1244
1245size_t MetadataDatabase::CountFileTracker() const {
1246  return index_->CountFileTracker();
1247}
1248
1249bool MetadataDatabase::GetConflictingTrackers(TrackerIDSet* trackers_out) {
1250  DCHECK(trackers_out);
1251
1252  ParentIDAndTitle parent_and_title = index_->PickMultiBackingFilePath();
1253  if (parent_and_title.parent_id == kInvalidTrackerID)
1254    return false;
1255
1256  TrackerIDSet trackers = index_->GetFileTrackerIDsByParentAndTitle(
1257      parent_and_title.parent_id, parent_and_title.title);
1258  if (trackers.size() <= 1) {
1259    NOTREACHED();
1260    return false;
1261  }
1262
1263  std::swap(*trackers_out, trackers);
1264  return true;
1265}
1266
1267void MetadataDatabase::GetRegisteredAppIDs(std::vector<std::string>* app_ids) {
1268  DCHECK(app_ids);
1269  *app_ids = index_->GetRegisteredAppIDs();
1270}
1271
1272SyncStatusCode MetadataDatabase::SweepDirtyTrackers(
1273    const std::vector<std::string>& file_ids) {
1274  std::set<int64> tracker_ids;
1275  for (size_t i = 0; i < file_ids.size(); ++i) {
1276    TrackerIDSet trackers_for_file_id =
1277        index_->GetFileTrackerIDsByFileID(file_ids[i]);
1278    for (TrackerIDSet::iterator itr = trackers_for_file_id.begin();
1279         itr != trackers_for_file_id.end(); ++itr)
1280      tracker_ids.insert(*itr);
1281  }
1282
1283  for (std::set<int64>::iterator itr = tracker_ids.begin();
1284       itr != tracker_ids.end(); ++itr) {
1285    scoped_ptr<FileTracker> tracker(new FileTracker);
1286    if (!index_->GetFileTracker(*itr, tracker.get()) ||
1287        !CanClearDirty(*tracker))
1288      continue;
1289    tracker->set_dirty(false);
1290    index_->StoreFileTracker(tracker.Pass());
1291  }
1292
1293  return WriteToDatabase();
1294}
1295
1296MetadataDatabase::MetadataDatabase(
1297    const base::FilePath& database_path,
1298    bool enable_on_disk_index,
1299    leveldb::Env* env_override)
1300    : database_path_(database_path),
1301      env_override_(env_override),
1302      enable_on_disk_index_(enable_on_disk_index),
1303      largest_known_change_id_(0),
1304      weak_ptr_factory_(this) {
1305}
1306
1307SyncStatusCode MetadataDatabase::Initialize() {
1308  SyncStatusCode status = SYNC_STATUS_UNKNOWN;
1309  bool created = false;
1310  // Open database unless |db_| is overridden for testing.
1311  if (!db_) {
1312    status = OpenDatabase(database_path_, env_override_, &db_, &created);
1313    if (status != SYNC_STATUS_OK)
1314      return status;
1315  }
1316
1317  if (!created) {
1318    status = MigrateDatabaseIfNeeded(db_.get());
1319    if (status != SYNC_STATUS_OK)
1320      return status;
1321  }
1322
1323  if (enable_on_disk_index_) {
1324    index_ = MetadataDatabaseIndexOnDisk::Create(db_.get());
1325  } else {
1326    index_ = MetadataDatabaseIndex::Create(db_.get());
1327  }
1328  if (!index_) {
1329    // Delete all entries in |db_| to reset it.
1330    // TODO(peria): Make LevelDBWrapper::DestroyDB() to avoid a full scan.
1331    scoped_ptr<LevelDBWrapper::Iterator> itr = db_->NewIterator();
1332    for (itr->SeekToFirst(); itr->Valid();)
1333      itr->Delete();
1334    db_->Commit();
1335
1336    return SYNC_DATABASE_ERROR_FAILED;
1337  }
1338
1339  status = LevelDBStatusToSyncStatusCode(db_->Commit());
1340  if (status != SYNC_STATUS_OK)
1341    return status;
1342
1343  UpdateLargestKnownChangeID(index_->GetLargestChangeID());
1344
1345  return status;
1346}
1347
1348void MetadataDatabase::CreateTrackerForParentAndFileID(
1349    const FileTracker& parent_tracker,
1350    const std::string& file_id) {
1351  CreateTrackerInternal(parent_tracker, file_id, NULL,
1352                        UPDATE_TRACKER_FOR_UNSYNCED_FILE);
1353}
1354
1355void MetadataDatabase::CreateTrackerForParentAndFileMetadata(
1356    const FileTracker& parent_tracker,
1357    const FileMetadata& file_metadata,
1358    UpdateOption option) {
1359  DCHECK(file_metadata.has_details());
1360  CreateTrackerInternal(parent_tracker,
1361                        file_metadata.file_id(),
1362                        &file_metadata.details(),
1363                        option);
1364}
1365
1366void MetadataDatabase::CreateTrackerInternal(const FileTracker& parent_tracker,
1367                                             const std::string& file_id,
1368                                             const FileDetails* details,
1369                                             UpdateOption option) {
1370  int64 tracker_id = IncrementTrackerID();
1371  scoped_ptr<FileTracker> tracker(new FileTracker);
1372  tracker->set_tracker_id(tracker_id);
1373  tracker->set_parent_tracker_id(parent_tracker.tracker_id());
1374  tracker->set_file_id(file_id);
1375  tracker->set_app_id(parent_tracker.app_id());
1376  tracker->set_tracker_kind(TRACKER_KIND_REGULAR);
1377  tracker->set_dirty(true);
1378  tracker->set_active(false);
1379  tracker->set_needs_folder_listing(false);
1380  if (details) {
1381    *tracker->mutable_synced_details() = *details;
1382    if (option == UPDATE_TRACKER_FOR_UNSYNCED_FILE) {
1383      tracker->mutable_synced_details()->set_missing(true);
1384      tracker->mutable_synced_details()->clear_md5();
1385    }
1386  }
1387  index_->StoreFileTracker(tracker.Pass());
1388}
1389
1390void MetadataDatabase::MaybeAddTrackersForNewFile(
1391    const FileMetadata& metadata,
1392    UpdateOption option) {
1393  std::set<int64> parents_to_exclude;
1394  TrackerIDSet existing_trackers =
1395      index_->GetFileTrackerIDsByFileID(metadata.file_id());
1396  for (TrackerIDSet::const_iterator itr = existing_trackers.begin();
1397       itr != existing_trackers.end(); ++itr) {
1398    FileTracker tracker;
1399    if (!index_->GetFileTracker(*itr, &tracker)) {
1400      NOTREACHED();
1401      continue;
1402    }
1403
1404    int64 parent_tracker_id = tracker.parent_tracker_id();
1405    if (!parent_tracker_id)
1406      continue;
1407
1408    // Exclude |parent_tracker_id| if it already has a tracker that has
1409    // unknown title or has the same title with |file|.
1410    if (!tracker.has_synced_details() ||
1411        tracker.synced_details().title() == metadata.details().title()) {
1412      parents_to_exclude.insert(parent_tracker_id);
1413    }
1414  }
1415
1416  for (int i = 0; i < metadata.details().parent_folder_ids_size(); ++i) {
1417    std::string parent_folder_id = metadata.details().parent_folder_ids(i);
1418    TrackerIDSet parent_trackers =
1419        index_->GetFileTrackerIDsByFileID(parent_folder_id);
1420    for (TrackerIDSet::const_iterator itr = parent_trackers.begin();
1421         itr != parent_trackers.end(); ++itr) {
1422      FileTracker parent_tracker;
1423      index_->GetFileTracker(*itr, &parent_tracker);
1424      if (!parent_tracker.active())
1425        continue;
1426
1427      if (ContainsKey(parents_to_exclude, parent_tracker.tracker_id()))
1428        continue;
1429
1430      CreateTrackerForParentAndFileMetadata(
1431          parent_tracker, metadata, option);
1432    }
1433  }
1434}
1435
1436int64 MetadataDatabase::IncrementTrackerID() {
1437  int64 tracker_id = index_->GetNextTrackerID();
1438  index_->SetNextTrackerID(tracker_id + 1);
1439  DCHECK_GT(tracker_id, 0);
1440  return tracker_id;
1441}
1442
1443bool MetadataDatabase::CanActivateTracker(const FileTracker& tracker) {
1444  DCHECK(!tracker.active());
1445  DCHECK_NE(index_->GetSyncRootTrackerID(), tracker.tracker_id());
1446
1447  if (HasActiveTrackerForFileID(tracker.file_id()))
1448    return false;
1449
1450  if (tracker.app_id().empty() &&
1451      tracker.tracker_id() != GetSyncRootTrackerID()) {
1452    return false;
1453  }
1454
1455  if (!tracker.has_synced_details())
1456    return false;
1457  if (tracker.synced_details().file_kind() == FILE_KIND_UNSUPPORTED)
1458    return false;
1459  if (HasInvalidTitle(tracker.synced_details().title()))
1460    return false;
1461  DCHECK(tracker.parent_tracker_id());
1462
1463  return !HasActiveTrackerForPath(tracker.parent_tracker_id(),
1464                                  tracker.synced_details().title());
1465}
1466
1467bool MetadataDatabase::ShouldKeepDirty(const FileTracker& tracker) const {
1468  if (HasDisabledAppRoot(tracker))
1469    return false;
1470
1471  DCHECK(tracker.dirty());
1472  if (!tracker.has_synced_details())
1473    return true;
1474
1475  FileMetadata metadata;
1476  if (!index_->GetFileMetadata(tracker.file_id(), &metadata))
1477    return true;
1478  DCHECK(metadata.has_details());
1479
1480  const FileDetails& local_details = tracker.synced_details();
1481  const FileDetails& remote_details = metadata.details();
1482
1483  if (tracker.active()) {
1484    if (tracker.needs_folder_listing())
1485      return true;
1486    if (local_details.md5() != remote_details.md5())
1487      return true;
1488    if (local_details.missing() != remote_details.missing())
1489      return true;
1490  }
1491
1492  if (local_details.title() != remote_details.title())
1493    return true;
1494
1495  return false;
1496}
1497
1498bool MetadataDatabase::HasDisabledAppRoot(const FileTracker& tracker) const {
1499  int64 app_root_tracker_id = index_->GetAppRootTracker(tracker.app_id());
1500  if (app_root_tracker_id == kInvalidTrackerID)
1501    return false;
1502
1503  FileTracker app_root_tracker;
1504  if (!index_->GetFileTracker(app_root_tracker_id, &app_root_tracker)) {
1505    NOTREACHED();
1506    return false;
1507  }
1508  return app_root_tracker.tracker_kind() == TRACKER_KIND_DISABLED_APP_ROOT;
1509}
1510
1511bool MetadataDatabase::HasActiveTrackerForFileID(
1512    const std::string& file_id) const {
1513  return index_->GetFileTrackerIDsByFileID(file_id).has_active();
1514}
1515
1516bool MetadataDatabase::HasActiveTrackerForPath(int64 parent_tracker_id,
1517                                               const std::string& title) const {
1518  return index_->GetFileTrackerIDsByParentAndTitle(parent_tracker_id, title)
1519      .has_active();
1520}
1521
1522void MetadataDatabase::RemoveUnneededTrackersForMissingFile(
1523    const std::string& file_id) {
1524  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(file_id);
1525  for (TrackerIDSet::const_iterator itr = trackers.begin();
1526       itr != trackers.end(); ++itr) {
1527    FileTracker tracker;
1528    if (!index_->GetFileTracker(*itr, &tracker)) {
1529      NOTREACHED();
1530      continue;
1531    }
1532
1533    if (!tracker.has_synced_details() || tracker.synced_details().missing()) {
1534      RemoveFileTracker(*itr, MARK_NOTHING_DIRTY, index_.get());
1535    }
1536  }
1537}
1538
1539void MetadataDatabase::UpdateByFileMetadata(
1540    const tracked_objects::Location& from_where,
1541    scoped_ptr<FileMetadata> metadata,
1542    UpdateOption option) {
1543  DCHECK(metadata);
1544  DCHECK(metadata->has_details());
1545
1546  DVLOG(1) << from_where.function_name() << ": "
1547           << metadata->file_id() << " ("
1548           << metadata->details().title() << ")"
1549           << (metadata->details().missing() ? " deleted" : "");
1550
1551  std::string file_id = metadata->file_id();
1552  if (metadata->details().missing())
1553    RemoveUnneededTrackersForMissingFile(file_id);
1554  else
1555    MaybeAddTrackersForNewFile(*metadata, option);
1556
1557  TrackerIDSet trackers = index_->GetFileTrackerIDsByFileID(file_id);
1558  if (!trackers.empty()) {
1559    index_->StoreFileMetadata(metadata.Pass());
1560
1561    if (option != UPDATE_TRACKER_FOR_SYNCED_FILE)
1562      MarkTrackerSetDirty(trackers, index_.get());
1563  }
1564}
1565
1566
1567SyncStatusCode MetadataDatabase::WriteToDatabase() {
1568  return LevelDBStatusToSyncStatusCode(db_->Commit());
1569}
1570
1571scoped_ptr<base::ListValue> MetadataDatabase::DumpFiles(
1572    const std::string& app_id) {
1573  scoped_ptr<base::ListValue> files(new base::ListValue);
1574
1575  FileTracker app_root_tracker;
1576  if (!FindAppRootTracker(app_id, &app_root_tracker))
1577    return files.Pass();
1578
1579  std::vector<int64> stack;
1580  AppendContents(
1581      index_->GetFileTrackerIDsByParent(app_root_tracker.tracker_id()), &stack);
1582  while (!stack.empty()) {
1583    int64 tracker_id = stack.back();
1584    stack.pop_back();
1585    AppendContents(index_->GetFileTrackerIDsByParent(tracker_id), &stack);
1586
1587    FileTracker tracker;
1588    if (!index_->GetFileTracker(tracker_id, &tracker)) {
1589      NOTREACHED();
1590      continue;
1591    }
1592    base::DictionaryValue* file = new base::DictionaryValue;
1593
1594    base::FilePath path = BuildDisplayPathForTracker(tracker);
1595    file->SetString("path", path.AsUTF8Unsafe());
1596    if (tracker.has_synced_details()) {
1597      file->SetString("title", tracker.synced_details().title());
1598      file->SetString("type",
1599                      FileKindToString(tracker.synced_details().file_kind()));
1600    }
1601
1602    base::DictionaryValue* details = new base::DictionaryValue;
1603    details->SetString("file_id", tracker.file_id());
1604    if (tracker.has_synced_details() &&
1605        tracker.synced_details().file_kind() == FILE_KIND_FILE)
1606      details->SetString("md5", tracker.synced_details().md5());
1607    details->SetString("active", tracker.active() ? "true" : "false");
1608    details->SetString("dirty", tracker.dirty() ? "true" : "false");
1609
1610    file->Set("details", details);
1611
1612    files->Append(file);
1613  }
1614
1615  return files.Pass();
1616}
1617
1618scoped_ptr<base::ListValue> MetadataDatabase::DumpDatabase() {
1619  scoped_ptr<base::ListValue> list(new base::ListValue);
1620  list->Append(DumpTrackers().release());
1621  list->Append(DumpMetadata().release());
1622  return list.Pass();
1623}
1624
1625bool MetadataDatabase::HasNewerFileMetadata(const std::string& file_id,
1626                                            int64 change_id) {
1627  FileMetadata metadata;
1628  if (!index_->GetFileMetadata(file_id, &metadata))
1629    return false;
1630  DCHECK(metadata.has_details());
1631  return metadata.details().change_id() >= change_id;
1632}
1633
1634scoped_ptr<base::ListValue> MetadataDatabase::DumpTrackers() {
1635  scoped_ptr<base::ListValue> trackers(new base::ListValue);
1636
1637  // Append the first element for metadata.
1638  base::DictionaryValue* metadata = new base::DictionaryValue;
1639  const char *trackerKeys[] = {
1640    "tracker_id", "path", "file_id", "tracker_kind", "app_id",
1641    "active", "dirty", "folder_listing",
1642    "title", "kind", "md5", "etag", "missing", "change_id",
1643  };
1644  std::vector<std::string> key_strings(
1645      trackerKeys, trackerKeys + ARRAYSIZE_UNSAFE(trackerKeys));
1646  base::ListValue* keys = new base::ListValue;
1647  keys->AppendStrings(key_strings);
1648  metadata->SetString("title", "Trackers");
1649  metadata->Set("keys", keys);
1650  trackers->Append(metadata);
1651
1652  // Append tracker data.
1653  std::vector<int64> tracker_ids(index_->GetAllTrackerIDs());
1654  for (std::vector<int64>::const_iterator itr = tracker_ids.begin();
1655       itr != tracker_ids.end(); ++itr) {
1656    const int64 tracker_id = *itr;
1657    FileTracker tracker;
1658    if (!index_->GetFileTracker(tracker_id, &tracker)) {
1659      NOTREACHED();
1660      continue;
1661    }
1662
1663    base::DictionaryValue* dict = new base::DictionaryValue;
1664    base::FilePath path = BuildDisplayPathForTracker(tracker);
1665    dict->SetString("tracker_id", base::Int64ToString(tracker_id));
1666    dict->SetString("path", path.AsUTF8Unsafe());
1667    dict->SetString("file_id", tracker.file_id());
1668    TrackerKind tracker_kind = tracker.tracker_kind();
1669    dict->SetString(
1670        "tracker_kind",
1671        tracker_kind == TRACKER_KIND_APP_ROOT ? "AppRoot" :
1672        tracker_kind == TRACKER_KIND_DISABLED_APP_ROOT ? "Disabled App" :
1673        tracker.tracker_id() == GetSyncRootTrackerID() ? "SyncRoot" :
1674        "Regular");
1675    dict->SetString("app_id", tracker.app_id());
1676    dict->SetString("active", tracker.active() ? "true" : "false");
1677    dict->SetString("dirty", tracker.dirty() ? "true" : "false");
1678    dict->SetString("folder_listing",
1679                    tracker.needs_folder_listing() ? "needed" : "no");
1680    if (tracker.has_synced_details()) {
1681      const FileDetails& details = tracker.synced_details();
1682      dict->SetString("title", details.title());
1683      dict->SetString("kind", FileKindToString(details.file_kind()));
1684      dict->SetString("md5", details.md5());
1685      dict->SetString("etag", details.etag());
1686      dict->SetString("missing", details.missing() ? "true" : "false");
1687      dict->SetString("change_id", base::Int64ToString(details.change_id()));
1688    }
1689    trackers->Append(dict);
1690  }
1691  return trackers.Pass();
1692}
1693
1694scoped_ptr<base::ListValue> MetadataDatabase::DumpMetadata() {
1695  scoped_ptr<base::ListValue> files(new base::ListValue);
1696
1697  // Append the first element for metadata.
1698  base::DictionaryValue* metadata = new base::DictionaryValue;
1699  const char *fileKeys[] = {
1700    "file_id", "title", "type", "md5", "etag", "missing",
1701    "change_id", "parents"
1702  };
1703  std::vector<std::string> key_strings(
1704      fileKeys, fileKeys + ARRAYSIZE_UNSAFE(fileKeys));
1705  base::ListValue* keys = new base::ListValue;
1706  keys->AppendStrings(key_strings);
1707  metadata->SetString("title", "Metadata");
1708  metadata->Set("keys", keys);
1709  files->Append(metadata);
1710
1711  // Append metadata data.
1712  std::vector<std::string> metadata_ids(index_->GetAllMetadataIDs());
1713  for (std::vector<std::string>::const_iterator itr = metadata_ids.begin();
1714       itr != metadata_ids.end(); ++itr) {
1715    const std::string& file_id = *itr;
1716    FileMetadata file;
1717    if (!index_->GetFileMetadata(file_id, &file)) {
1718      NOTREACHED();
1719      continue;
1720    }
1721
1722    base::DictionaryValue* dict = new base::DictionaryValue;
1723    dict->SetString("file_id", file_id);
1724    if (file.has_details()) {
1725      const FileDetails& details = file.details();
1726      dict->SetString("title", details.title());
1727      dict->SetString("type", FileKindToString(details.file_kind()));
1728      dict->SetString("md5", details.md5());
1729      dict->SetString("etag", details.etag());
1730      dict->SetString("missing", details.missing() ? "true" : "false");
1731      dict->SetString("change_id", base::Int64ToString(details.change_id()));
1732
1733      std::vector<std::string> parents;
1734      for (int i = 0; i < details.parent_folder_ids_size(); ++i)
1735        parents.push_back(details.parent_folder_ids(i));
1736      dict->SetString("parents", JoinString(parents, ","));
1737    }
1738    files->Append(dict);
1739  }
1740  return files.Pass();
1741}
1742
1743void MetadataDatabase::AttachSyncRoot(
1744    const google_apis::FileResource& sync_root_folder) {
1745  scoped_ptr<FileMetadata> sync_root_metadata =
1746      CreateFileMetadataFromFileResource(
1747          GetLargestKnownChangeID(), sync_root_folder);
1748  scoped_ptr<FileTracker> sync_root_tracker =
1749      CreateSyncRootTracker(IncrementTrackerID(), *sync_root_metadata);
1750
1751  index_->SetSyncRootTrackerID(sync_root_tracker->tracker_id());
1752  index_->StoreFileMetadata(sync_root_metadata.Pass());
1753  index_->StoreFileTracker(sync_root_tracker.Pass());
1754}
1755
1756void MetadataDatabase::AttachInitialAppRoot(
1757    const google_apis::FileResource& app_root_folder) {
1758  scoped_ptr<FileMetadata> app_root_metadata =
1759      CreateFileMetadataFromFileResource(
1760          GetLargestKnownChangeID(), app_root_folder);
1761  scoped_ptr<FileTracker> app_root_tracker =
1762      CreateInitialAppRootTracker(IncrementTrackerID(),
1763                                  GetSyncRootTrackerID(),
1764                                  *app_root_metadata);
1765
1766  index_->StoreFileMetadata(app_root_metadata.Pass());
1767  index_->StoreFileTracker(app_root_tracker.Pass());
1768}
1769
1770bool MetadataDatabase::CanClearDirty(const FileTracker& tracker) {
1771  FileMetadata metadata;
1772  if (!index_->GetFileMetadata(tracker.file_id(), &metadata) ||
1773      !tracker.active() || !tracker.dirty() ||
1774      !tracker.has_synced_details() ||
1775      tracker.needs_folder_listing())
1776    return false;
1777
1778  const FileDetails& remote_details = metadata.details();
1779  const FileDetails& synced_details = tracker.synced_details();
1780  if (remote_details.title() != synced_details.title() ||
1781      remote_details.md5() != synced_details.md5() ||
1782      remote_details.missing() != synced_details.missing())
1783    return false;
1784
1785  std::set<std::string> parents;
1786  for (int i = 0; i < remote_details.parent_folder_ids_size(); ++i)
1787    parents.insert(remote_details.parent_folder_ids(i));
1788
1789  for (int i = 0; i < synced_details.parent_folder_ids_size(); ++i)
1790    if (parents.erase(synced_details.parent_folder_ids(i)) != 1)
1791      return false;
1792
1793  if (!parents.empty())
1794    return false;
1795
1796  return true;
1797}
1798
1799}  // namespace drive_backend
1800}  // namespace sync_file_system
1801