Schema migrations for LevelDB (#728)

* Implement schema versions

* Style fixes

* newlines, copyrights, assumptions

* Fix nullability

* Raw ptr -> shared_ptr

* kVersionTableGlobal -> kVersionGlobalTable

* Drop utils, move into static methods

* Drop extra include

* Add a few more comments

* Move version constant into migrations file

* formatting?

* Fix comment

8 files changed, 218 insertions, 50 deletions

diff --git a/Firestore/Source/Local/FSTLevelDB.h b/Firestore/Source/Local/FSTLevelDB.h
index 762054b..6819116 100644
--- a/Firestore/Source/Local/FSTLevelDB.h
+++ b/Firestore/Source/Local/FSTLevelDB.h
@@ -23,6 +23,7 @@
 
 namespace leveldb {
 class DB;
+class ReadOptions;
 class Status;
 }
 #endif
@@ -70,6 +71,10 @@ NS_ASSUME_NONNULL_BEGIN
 
 #ifdef __cplusplus
 // What follows is the Objective-C++ extension to the API.
+/**
+ * @return A standard set of read options
+ */
++ (const leveldb::ReadOptions)standardReadOptions;
 
 /**
  * Creates an NSError based on the given status if the status is not ok.
diff --git a/Firestore/Source/Local/FSTLevelDB.mm b/Firestore/Source/Local/FSTLevelDB.mm
index 83b932c..d163ed5 100644
--- a/Firestore/Source/Local/FSTLevelDB.mm
+++ b/Firestore/Source/Local/FSTLevelDB.mm
@@ -20,6 +20,7 @@
 
 #import "FIRFirestoreErrors.h"
 #import "Firestore/Source/Core/FSTDatabaseInfo.h"
+#import "Firestore/Source/Local/FSTLevelDBMigrations.h"
 #import "Firestore/Source/Local/FSTLevelDBMutationQueue.h"
 #import "Firestore/Source/Local/FSTLevelDBQueryCache.h"
 #import "Firestore/Source/Local/FSTLevelDBRemoteDocumentCache.h"
@@ -36,6 +37,7 @@ static NSString *const kReservedPathComponent = @"firestore";
 
 using leveldb::DB;
 using leveldb::Options;
+using leveldb::ReadOptions;
 using leveldb::Status;
 using leveldb::WriteOptions;
 
@@ -50,6 +52,15 @@ using leveldb::WriteOptions;
 
 @implementation FSTLevelDB
 
+/**
+ * For now this is paranoid, but perhaps disable that in production builds.
+ */
++ (const ReadOptions)standardReadOptions {
+  ReadOptions options;
+  options.verify_checksums = true;
+  return options;
+}
+
 - (instancetype)initWithDirectory:(NSString *)directory
                        serializer:(FSTLocalSerializer *)serializer {
   if (self = [super init]) {
@@ -115,8 +126,8 @@ using leveldb::WriteOptions;
   if (!database) {
     return NO;
   }
-
   _ptr.reset(database);
+  [FSTLevelDBMigrations runMigrationsOnDB:_ptr];
   return YES;
 }
 
diff --git a/Firestore/Source/Local/FSTLevelDBKey.h b/Firestore/Source/Local/FSTLevelDBKey.h
index 2e9b9b2..e5e7fbb 100644
--- a/Firestore/Source/Local/FSTLevelDBKey.h
+++ b/Firestore/Source/Local/FSTLevelDBKey.h
@@ -82,6 +82,14 @@ NS_ASSUME_NONNULL_BEGIN
 
 @end
 
+/** A key to a singleton row storing the version of the schema. */
+@interface FSTLevelDBVersionKey : NSObject
+
+/** Returns the key pointing to the singleton row storing the schema version. */
++ (std::string)key;
+
+@end
+
 /** A key in the mutations table. */
 @interface FSTLevelDBMutationKey : NSObject
 
diff --git a/Firestore/Source/Local/FSTLevelDBKey.mm b/Firestore/Source/Local/FSTLevelDBKey.mm
index 9850fff..41aea39 100644
--- a/Firestore/Source/Local/FSTLevelDBKey.mm
+++ b/Firestore/Source/Local/FSTLevelDBKey.mm
@@ -29,6 +29,7 @@ using firebase::firestore::util::OrderedCode;
 using Firestore::StringView;
 using leveldb::Slice;
 
+static const char *kVersionGlobalTable = "version";
 static const char *kMutationsTable = "mutation";
 static const char *kDocumentMutationsTable = "document_mutation";
 static const char *kMutationQueuesTable = "mutation_queue";
@@ -448,6 +449,17 @@ NSString *InvalidKey(const Slice &key) {
 
 @end
 
+@implementation FSTLevelDBVersionKey
+
++ (std::string)key {
+  std::string result;
+  WriteTableName(&result, kVersionGlobalTable);
+  WriteTerminator(&result);
+  return result;
+}
+
+@end
+
 @implementation FSTLevelDBMutationKey {
   std::string _userID;
 }
diff --git a/Firestore/Source/Local/FSTLevelDBMigrations.h b/Firestore/Source/Local/FSTLevelDBMigrations.h
new file mode 100644
index 0000000..46c7c93
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBMigrations.h
@@ -0,0 +1,45 @@
+/*
+ * Copyright 2018 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+#include <memory>
+
+#ifdef __cplusplus
+
+namespace leveldb {
+class DB;
+}
+#endif
+
+NS_ASSUME_NONNULL_BEGIN
+
+typedef int32_t FSTLevelDBSchemaVersion;
+
+@interface FSTLevelDBMigrations : NSObject
+
+/**
+ * Returns the current version of the schema for the given database
+ */
++ (FSTLevelDBSchemaVersion)schemaVersionForDB:(std::shared_ptr<leveldb::DB>)db;
+
+/**
+ * Runs any migrations needed to bring the given database up to the current schema version
+ */
++ (void)runMigrationsOnDB:(std::shared_ptr<leveldb::DB>)db;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBMigrations.mm b/Firestore/Source/Local/FSTLevelDBMigrations.mm
new file mode 100644
index 0000000..49af893
--- /dev/null
+++ b/Firestore/Source/Local/FSTLevelDBMigrations.mm
@@ -0,0 +1,95 @@
+/*
+ * Copyright 2018 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "Firestore/Source/Local/FSTLevelDBMigrations.h"
+
+#include <leveldb/db.h>
+#include <leveldb/write_batch.h>
+
+#import "Firestore/Protos/objc/firestore/local/Target.pbobjc.h"
+#import "Firestore/Source/Local/FSTLevelDB.h"
+#import "Firestore/Source/Local/FSTLevelDBKey.h"
+#import "Firestore/Source/Local/FSTLevelDBQueryCache.h"
+#import "Firestore/Source/Local/FSTWriteGroup.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+// Current version of the schema defined in this file.
+static FSTLevelDBSchemaVersion kSchemaVersion = 1;
+
+using leveldb::DB;
+using leveldb::Status;
+using leveldb::Slice;
+using leveldb::WriteOptions;
+
+/**
+ * Ensures that the global singleton target metadata row exists in LevelDB.
+ * @param db The db in which to require the row.
+ */
+static void EnsureTargetGlobal(std::shared_ptr<DB> db, FSTWriteGroup *group) {
+  FSTPBTargetGlobal *targetGlobal = [FSTLevelDBQueryCache readTargetMetadataFromDB:db];
+  if (!targetGlobal) {
+    [group setMessage:[FSTPBTargetGlobal message] forKey:[FSTLevelDBTargetGlobalKey key]];
+  }
+}
+
+/**
+ * Save the given version number as the current version of the schema of the database.
+ * @param version The version to save
+ * @param group The transaction in which to save the new version number
+ */
+static void SaveVersion(FSTLevelDBSchemaVersion version, FSTWriteGroup *group) {
+  std::string key = [FSTLevelDBVersionKey key];
+  std::string version_string = std::to_string(version);
+  [group setData:version_string forKey:key];
+}
+
+@implementation FSTLevelDBMigrations
+
++ (FSTLevelDBSchemaVersion)schemaVersionForDB:(std::shared_ptr<DB>)db {
+  std::string key = [FSTLevelDBVersionKey key];
+  std::string version_string;
+  Status status = db->Get([FSTLevelDB standardReadOptions], key, &version_string);
+  if (status.IsNotFound()) {
+    return 0;
+  } else {
+    return stoi(version_string);
+  }
+}
+
++ (void)runMigrationsOnDB:(std::shared_ptr<DB>)db {
+  FSTWriteGroup *group = [FSTWriteGroup groupWithAction:@"Migrations"];
+  FSTLevelDBSchemaVersion currentVersion = [self schemaVersionForDB:db];
+  // Each case in this switch statement intentionally falls through. This lets us
+  // start at the current schema version and apply any migrations that have not yet
+  // been applied, to bring us up to current, as defined by the kSchemaVersion constant.
+  switch (currentVersion) {
+    case 0:
+      EnsureTargetGlobal(db, group);
+      // Fallthrough
+    default:
+      if (currentVersion < kSchemaVersion) {
+        SaveVersion(kSchemaVersion, group);
+      }
+  }
+  if (!group.isEmpty) {
+    [group writeToDB:db];
+  }
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Local/FSTLevelDBQueryCache.h b/Firestore/Source/Local/FSTLevelDBQueryCache.h
index 6d5cd60..67c6575 100644
--- a/Firestore/Source/Local/FSTLevelDBQueryCache.h
+++ b/Firestore/Source/Local/FSTLevelDBQueryCache.h
@@ -28,12 +28,20 @@ class DB;
 
 @class FSTLocalSerializer;
 @protocol FSTGarbageCollector;
+@class FSTPBTargetGlobal;
 
 NS_ASSUME_NONNULL_BEGIN
 
 /** Cached Queries backed by LevelDB. */
 @interface FSTLevelDBQueryCache : NSObject <FSTQueryCache>
 
+#ifdef __cplusplus
+/**
+ * Retrieves the global singleton metadata row from the given database, if it exists.
+ */
++ (nullable FSTPBTargetGlobal *)readTargetMetadataFromDB:(std::shared_ptr<leveldb::DB>)db;
+#endif
+
 - (instancetype)init NS_UNAVAILABLE;
 
 /** The garbage collector to notify about potential garbage keys. */
diff --git a/Firestore/Source/Local/FSTLevelDBQueryCache.mm b/Firestore/Source/Local/FSTLevelDBQueryCache.mm
index 46af918..b3f4822 100644
--- a/Firestore/Source/Local/FSTLevelDBQueryCache.mm
+++ b/Firestore/Source/Local/FSTLevelDBQueryCache.mm
@@ -22,6 +22,7 @@
 
 #import "Firestore/Protos/objc/firestore/local/Target.pbobjc.h"
 #import "Firestore/Source/Core/FSTQuery.h"
+#import "Firestore/Source/Local/FSTLevelDB.h"
 #import "Firestore/Source/Local/FSTLevelDBKey.h"
 #import "Firestore/Source/Local/FSTLocalSerializer.h"
 #import "Firestore/Source/Local/FSTQueryData.h"
@@ -39,17 +40,6 @@ using leveldb::Slice;
 using leveldb::Status;
 using leveldb::WriteOptions;
 
-/**
- * Returns a standard set of read options.
- *
- * For now this is paranoid, but perhaps disable that in production builds.
- */
-static ReadOptions GetStandardReadOptions() {
-  ReadOptions options;
-  options.verify_checksums = true;
-  return options;
-}
-
 @interface FSTLevelDBQueryCache ()
 
 /** A write-through cached copy of the metadata for the query cache. */
@@ -70,6 +60,29 @@ static ReadOptions GetStandardReadOptions() {
   FSTSnapshotVersion *_lastRemoteSnapshotVersion;
 }
 
++ (nullable FSTPBTargetGlobal *)readTargetMetadataFromDB:(std::shared_ptr<DB>)db {
+  std::string key = [FSTLevelDBTargetGlobalKey key];
+  std::string value;
+  Status status = db->Get([FSTLevelDB standardReadOptions], key, &value);
+  if (status.IsNotFound()) {
+    return nil;
+  } else if (!status.ok()) {
+    FSTFail(@"metadataForKey: failed loading key %s with status: %s", key.c_str(),
+            status.ToString().c_str());
+  }
+
+  NSData *data =
+      [[NSData alloc] initWithBytesNoCopy:(void *)value.data() length:value.size() freeWhenDone:NO];
+
+  NSError *error;
+  FSTPBTargetGlobal *proto = [FSTPBTargetGlobal parseFromData:data error:&error];
+  if (!proto) {
+    FSTFail(@"FSTPBTargetGlobal failed to parse: %@", error);
+  }
+
+  return proto;
+}
+
 - (instancetype)initWithDB:(std::shared_ptr<DB>)db serializer:(FSTLocalSerializer *)serializer {
   if (self = [super init]) {
     FSTAssert(db, @"db must not be NULL");
@@ -80,11 +93,10 @@ static ReadOptions GetStandardReadOptions() {
 }
 
 - (void)start {
-  std::string key = [FSTLevelDBTargetGlobalKey key];
-  FSTPBTargetGlobal *metadata = [self metadataForKey:key];
-  if (!metadata) {
-    metadata = [FSTPBTargetGlobal message];
-  }
+  FSTPBTargetGlobal *metadata = [FSTLevelDBQueryCache readTargetMetadataFromDB:_db];
+  FSTAssert(
+      metadata != nil,
+      @"Found nil metadata, expected schema to be at version 0 which ensures metadata existence");
   _lastRemoteSnapshotVersion = [self.serializer decodedVersion:metadata.lastRemoteSnapshotVersion];
 
   self.metadata = metadata;
@@ -157,34 +169,6 @@ static ReadOptions GetStandardReadOptions() {
 }
 
 /**
- * Looks up the query global metadata associated with the given key.
- *
- * @return the parsed protocol buffer message or nil if the row referenced by the given key does
- *     not exist.
- */
-- (nullable FSTPBTargetGlobal *)metadataForKey:(const std::string &)key {
-  std::string value;
-  Status status = _db->Get(GetStandardReadOptions(), key, &value);
-  if (status.IsNotFound()) {
-    return nil;
-  } else if (!status.ok()) {
-    FSTFail(@"metadataForKey: failed loading key %s with status: %s", key.c_str(),
-            status.ToString().c_str());
-  }
-
-  NSData *data =
-      [[NSData alloc] initWithBytesNoCopy:(void *)value.data() length:value.size() freeWhenDone:NO];
-
-  NSError *error;
-  FSTPBTargetGlobal *proto = [FSTPBTargetGlobal parseFromData:data error:&error];
-  if (!proto) {
-    FSTFail(@"FSTPBTargetGlobal failed to parse: %@", error);
-  }
-
-  return proto;
-}
-
-/**
  * Parses the given bytes as an FSTPBTarget protocol buffer and then converts to the equivalent
  * query data.
  */
@@ -206,7 +190,7 @@ static ReadOptions GetStandardReadOptions() {
   // Note that this is a scan rather than a get because canonicalIDs are not required to be unique
   // per target.
   Slice canonicalID = StringView(query.canonicalID);
-  std::unique_ptr<Iterator> indexItererator(_db->NewIterator(GetStandardReadOptions()));
+  std::unique_ptr<Iterator> indexItererator(_db->NewIterator([FSTLevelDB standardReadOptions]));
   std::string indexPrefix = [FSTLevelDBQueryTargetKey keyPrefixWithCanonicalID:canonicalID];
   indexItererator->Seek(indexPrefix);
 
@@ -214,7 +198,7 @@ static ReadOptions GetStandardReadOptions() {
   // unique and ordered, so when scanning a table prefixed by exactly one canonicalID, all the
   // targetIDs will be unique and in order.
   std::string targetPrefix = [FSTLevelDBTargetKey keyPrefix];
-  std::unique_ptr<Iterator> targetIterator(_db->NewIterator(GetStandardReadOptions()));
+  std::unique_ptr<Iterator> targetIterator(_db->NewIterator([FSTLevelDB standardReadOptions]));
 
   FSTLevelDBQueryTargetKey *rowKey = [[FSTLevelDBQueryTargetKey alloc] init];
   for (; indexItererator->Valid(); indexItererator->Next()) {
@@ -286,7 +270,7 @@ static ReadOptions GetStandardReadOptions() {
 
 - (void)removeMatchingKeysForTargetID:(FSTTargetID)targetID group:(FSTWriteGroup *)group {
   std::string indexPrefix = [FSTLevelDBTargetDocumentKey keyPrefixWithTargetID:targetID];
-  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(GetStandardReadOptions()));
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator([FSTLevelDB standardReadOptions]));
   indexIterator->Seek(indexPrefix);
 
   FSTLevelDBTargetDocumentKey *rowKey = [[FSTLevelDBTargetDocumentKey alloc] init];
@@ -309,7 +293,7 @@ static ReadOptions GetStandardReadOptions() {
 
 - (FSTDocumentKeySet *)matchingKeysForTargetID:(FSTTargetID)targetID {
   std::string indexPrefix = [FSTLevelDBTargetDocumentKey keyPrefixWithTargetID:targetID];
-  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(GetStandardReadOptions()));
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator([FSTLevelDB standardReadOptions]));
   indexIterator->Seek(indexPrefix);
 
   FSTDocumentKeySet *result = [FSTDocumentKeySet keySet];
@@ -332,7 +316,7 @@ static ReadOptions GetStandardReadOptions() {
 
 - (BOOL)containsKey:(FSTDocumentKey *)key {
   std::string indexPrefix = [FSTLevelDBDocumentTargetKey keyPrefixWithResourcePath:key.path];
-  std::unique_ptr<Iterator> indexIterator(_db->NewIterator(GetStandardReadOptions()));
+  std::unique_ptr<Iterator> indexIterator(_db->NewIterator([FSTLevelDB standardReadOptions]));
   indexIterator->Seek(indexPrefix);
 
   if (indexIterator->Valid()) {