Release 4.3.0 (#327)

Initial release of Firestore at 0.8.0
Bump FirebaseCommunity to 0.1.3

24 files changed, 3601 insertions, 0 deletions

diff --git a/Firestore/Example/Tests/Local/FSTEagerGarbageCollectorTests.m b/Firestore/Example/Tests/Local/FSTEagerGarbageCollectorTests.m
new file mode 100644
index 0000000..34c0685
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTEagerGarbageCollectorTests.m
@@ -0,0 +1,111 @@
+/*
+ * Copyright 2017 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 "Local/FSTEagerGarbageCollector.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Local/FSTReferenceSet.h"
+#import "Model/FSTDocumentKey.h"
+
+#import "FSTHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTEagerGarbageCollectorTests : XCTestCase
+@end
+
+@implementation FSTEagerGarbageCollectorTests
+
+- (void)testAddOrRemoveReferences {
+  FSTEagerGarbageCollector *gc = [[FSTEagerGarbageCollector alloc] init];
+  FSTReferenceSet *referenceSet = [[FSTReferenceSet alloc] init];
+  [gc addGarbageSource:referenceSet];
+
+  FSTDocumentKey *key = [FSTDocumentKey keyWithPathString:@"foo/bar"];
+  [referenceSet addReferenceToKey:key forID:1];
+  FSTAssertEqualSets([gc collectGarbage], @[]);
+  XCTAssertFalse([referenceSet isEmpty]);
+
+  [referenceSet removeReferenceToKey:key forID:1];
+  FSTAssertEqualSets([gc collectGarbage], @[ key ]);
+  XCTAssertTrue([referenceSet isEmpty]);
+}
+
+- (void)testRemoveAllReferencesForID {
+  FSTEagerGarbageCollector *gc = [[FSTEagerGarbageCollector alloc] init];
+  FSTReferenceSet *referenceSet = [[FSTReferenceSet alloc] init];
+  [gc addGarbageSource:referenceSet];
+
+  FSTDocumentKey *key1 = [FSTDocumentKey keyWithPathString:@"foo/bar"];
+  FSTDocumentKey *key2 = [FSTDocumentKey keyWithPathString:@"foo/baz"];
+  FSTDocumentKey *key3 = [FSTDocumentKey keyWithPathString:@"foo/blah"];
+  [referenceSet addReferenceToKey:key1 forID:1];
+  [referenceSet addReferenceToKey:key2 forID:1];
+  [referenceSet addReferenceToKey:key3 forID:2];
+  XCTAssertFalse([referenceSet isEmpty]);
+
+  [referenceSet removeReferencesForID:1];
+  FSTAssertEqualSets([gc collectGarbage], (@[ key1, key2 ]));
+  XCTAssertFalse([referenceSet isEmpty]);
+
+  [referenceSet removeReferencesForID:2];
+  FSTAssertEqualSets([gc collectGarbage], @[ key3 ]);
+  XCTAssertTrue([referenceSet isEmpty]);
+}
+
+- (void)testTwoReferenceSetsAtTheSameTime {
+  FSTReferenceSet *remoteTargets = [[FSTReferenceSet alloc] init];
+  FSTReferenceSet *localViews = [[FSTReferenceSet alloc] init];
+  FSTReferenceSet *mutations = [[FSTReferenceSet alloc] init];
+
+  FSTEagerGarbageCollector *gc = [[FSTEagerGarbageCollector alloc] init];
+  [gc addGarbageSource:remoteTargets];
+  [gc addGarbageSource:localViews];
+  [gc addGarbageSource:mutations];
+
+  FSTDocumentKey *key1 = [FSTDocumentKey keyWithPathString:@"foo/bar"];
+  [remoteTargets addReferenceToKey:key1 forID:1];
+  [localViews addReferenceToKey:key1 forID:1];
+  [mutations addReferenceToKey:key1 forID:10];
+
+  FSTDocumentKey *key2 = [FSTDocumentKey keyWithPathString:@"foo/baz"];
+  [mutations addReferenceToKey:key2 forID:10];
+
+  XCTAssertFalse([remoteTargets isEmpty]);
+  XCTAssertFalse([localViews isEmpty]);
+  XCTAssertFalse([mutations isEmpty]);
+
+  [localViews removeReferencesForID:1];
+  FSTAssertEqualSets([gc collectGarbage], @[]);
+
+  [remoteTargets removeReferencesForID:1];
+  FSTAssertEqualSets([gc collectGarbage], @[]);
+
+  [mutations removeReferenceToKey:key1 forID:10];
+  FSTAssertEqualSets([gc collectGarbage], @[ key1 ]);
+
+  [mutations removeReferenceToKey:key2 forID:10];
+  FSTAssertEqualSets([gc collectGarbage], @[ key2 ]);
+
+  XCTAssertTrue([remoteTargets isEmpty]);
+  XCTAssertTrue([localViews isEmpty]);
+  XCTAssertTrue([mutations isEmpty]);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTLevelDBKeyTests.mm b/Firestore/Example/Tests/Local/FSTLevelDBKeyTests.mm
new file mode 100644
index 0000000..3374fcf
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTLevelDBKeyTests.mm
@@ -0,0 +1,361 @@
+/*
+ * Copyright 2017 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 "Local/FSTLevelDBKey.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Model/FSTPath.h"
+
+#import "FSTHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLevelDBKeyTests : XCTestCase
+@end
+
+// I can't believe I have to write this...
+bool StartsWith(const std::string &value, const std::string &prefix) {
+  return prefix.size() <= value.size() && std::equal(prefix.begin(), prefix.end(), value.begin());
+}
+
+static std::string RemoteDocKey(NSString *pathString) {
+  return [FSTLevelDBRemoteDocumentKey keyWithDocumentKey:FSTTestDocKey(pathString)];
+}
+
+static std::string RemoteDocKeyPrefix(NSString *pathString) {
+  return [FSTLevelDBRemoteDocumentKey keyPrefixWithResourcePath:FSTTestPath(pathString)];
+}
+
+static std::string DocMutationKey(NSString *userID, NSString *key, FSTBatchID batchID) {
+  return [FSTLevelDBDocumentMutationKey keyWithUserID:userID
+                                          documentKey:FSTTestDocKey(key)
+                                              batchID:batchID];
+}
+
+static std::string TargetDocKey(FSTTargetID targetID, NSString *key) {
+  return [FSTLevelDBTargetDocumentKey keyWithTargetID:targetID documentKey:FSTTestDocKey(key)];
+}
+
+static std::string DocTargetKey(NSString *key, FSTTargetID targetID) {
+  return [FSTLevelDBDocumentTargetKey keyWithDocumentKey:FSTTestDocKey(key) targetID:targetID];
+}
+
+/**
+ * Asserts that the description for given key is equal to the expected description.
+ *
+ * @param key A StringView of a textual key
+ * @param key An NSString that [FSTLevelDBKey descriptionForKey:] is expected to produce.
+ */
+#define FSTAssertExpectedKeyDescription(key, expectedDescription) \
+  XCTAssertEqualObjects([FSTLevelDBKey descriptionForKey:(key)], (expectedDescription))
+
+#define FSTAssertKeyLessThan(left, right)                                           \
+  do {                                                                              \
+    std::string leftKey = (left);                                                   \
+    std::string rightKey = (right);                                                 \
+    XCTAssertLessThan(leftKey.compare(right), 0, @"Expected %@ to be less than %@", \
+                      [FSTLevelDBKey descriptionForKey:leftKey],                    \
+                      [FSTLevelDBKey descriptionForKey:rightKey]);                  \
+  } while (0)
+
+@implementation FSTLevelDBKeyTests
+
+- (void)testMutationKeyPrefixing {
+  auto tableKey = [FSTLevelDBMutationKey keyPrefix];
+  auto emptyUserKey = [FSTLevelDBMutationKey keyPrefixWithUserID:""];
+  auto fooUserKey = [FSTLevelDBMutationKey keyPrefixWithUserID:"foo"];
+
+  auto foo2Key = [FSTLevelDBMutationKey keyWithUserID:"foo" batchID:2];
+
+  XCTAssertTrue(StartsWith(emptyUserKey, tableKey));
+
+  // This is critical: prefixes of the a value don't convert into prefixes of the key.
+  XCTAssertTrue(StartsWith(fooUserKey, tableKey));
+  XCTAssertFalse(StartsWith(fooUserKey, emptyUserKey));
+
+  // However whole segments in common are prefixes.
+  XCTAssertTrue(StartsWith(foo2Key, tableKey));
+  XCTAssertTrue(StartsWith(foo2Key, fooUserKey));
+}
+
+- (void)testMutationKeyEncodeDecodeCycle {
+  FSTLevelDBMutationKey *key = [[FSTLevelDBMutationKey alloc] init];
+  std::string user("foo");
+
+  NSArray<NSNumber *> *batchIds = @[ @0, @1, @100, @(INT_MAX - 1), @(INT_MAX) ];
+  for (NSNumber *batchIDNumber in batchIds) {
+    FSTBatchID batchID = [batchIDNumber intValue];
+    auto encoded = [FSTLevelDBMutationKey keyWithUserID:user batchID:batchID];
+
+    BOOL ok = [key decodeKey:encoded];
+    XCTAssertTrue(ok);
+    XCTAssertEqual(key.userID, user);
+    XCTAssertEqual(key.batchID, batchID);
+  }
+}
+
+- (void)testMutationKeyDescription {
+  FSTAssertExpectedKeyDescription([FSTLevelDBMutationKey keyPrefix], @"[mutation: incomplete key]");
+
+  FSTAssertExpectedKeyDescription([FSTLevelDBMutationKey keyPrefixWithUserID:@"user1"],
+                                  @"[mutation: userID=user1 incomplete key]");
+
+  auto key = [FSTLevelDBMutationKey keyWithUserID:@"user1" batchID:42];
+  FSTAssertExpectedKeyDescription(key, @"[mutation: userID=user1 batchID=42]");
+
+  FSTAssertExpectedKeyDescription(key + " extra",
+                                  @"[mutation: userID=user1 batchID=42 invalid "
+                                  @"key=<hW11dGF0aW9uAAGNdXNlcjEAAYqqgCBleHRyYQ==>]");
+
+  // Truncate the key so that it's missing its terminator.
+  key.resize(key.size() - 1);
+  FSTAssertExpectedKeyDescription(key, @"[mutation: userID=user1 batchID=42 incomplete key]");
+}
+
+- (void)testDocumentMutationKeyPrefixing {
+  auto tableKey = [FSTLevelDBDocumentMutationKey keyPrefix];
+  auto emptyUserKey = [FSTLevelDBDocumentMutationKey keyPrefixWithUserID:""];
+  auto fooUserKey = [FSTLevelDBDocumentMutationKey keyPrefixWithUserID:"foo"];
+
+  FSTDocumentKey *documentKey = FSTTestDocKey(@"foo/bar");
+  auto foo2Key =
+      [FSTLevelDBDocumentMutationKey keyWithUserID:"foo" documentKey:documentKey batchID:2];
+
+  XCTAssertTrue(StartsWith(emptyUserKey, tableKey));
+
+  // While we want a key with whole segments in common be considered a prefix it's vital that
+  // partial segments in common not be prefixes.
+  XCTAssertTrue(StartsWith(fooUserKey, tableKey));
+
+  // Here even though "" is a prefix of "foo" that prefix is within a segment so keys derived from
+  // those segments cannot be prefixes of each other.
+  XCTAssertFalse(StartsWith(fooUserKey, emptyUserKey));
+  XCTAssertFalse(StartsWith(emptyUserKey, fooUserKey));
+
+  // However whole segments in common are prefixes.
+  XCTAssertTrue(StartsWith(foo2Key, tableKey));
+  XCTAssertTrue(StartsWith(foo2Key, fooUserKey));
+}
+
+- (void)testDocumentMutationKeyEncodeDecodeCycle {
+  FSTLevelDBDocumentMutationKey *key = [[FSTLevelDBDocumentMutationKey alloc] init];
+  std::string user("foo");
+
+  NSArray<FSTDocumentKey *> *documentKeys = @[ FSTTestDocKey(@"a/b"), FSTTestDocKey(@"a/b/c/d") ];
+
+  NSArray<NSNumber *> *batchIds = @[ @0, @1, @100, @(INT_MAX - 1), @(INT_MAX) ];
+  for (NSNumber *batchIDNumber in batchIds) {
+    for (FSTDocumentKey *documentKey in documentKeys) {
+      FSTBatchID batchID = [batchIDNumber intValue];
+      auto encoded = [FSTLevelDBDocumentMutationKey keyWithUserID:user
+                                                      documentKey:documentKey
+                                                          batchID:batchID];
+
+      BOOL ok = [key decodeKey:encoded];
+      XCTAssertTrue(ok);
+      XCTAssertEqual(key.userID, user);
+      XCTAssertEqualObjects(key.documentKey, documentKey);
+      XCTAssertEqual(key.batchID, batchID);
+    }
+  }
+}
+
+- (void)testDocumentMutationKeyOrdering {
+  // Different user:
+  FSTAssertKeyLessThan(DocMutationKey(@"1", @"foo/bar", 0), DocMutationKey(@"10", @"foo/bar", 0));
+  FSTAssertKeyLessThan(DocMutationKey(@"1", @"foo/bar", 0), DocMutationKey(@"2", @"foo/bar", 0));
+
+  // Different paths:
+  FSTAssertKeyLessThan(DocMutationKey(@"1", @"foo/bar", 0), DocMutationKey(@"1", @"foo/baz", 0));
+  FSTAssertKeyLessThan(DocMutationKey(@"1", @"foo/bar", 0), DocMutationKey(@"1", @"foo/bar2", 0));
+  FSTAssertKeyLessThan(DocMutationKey(@"1", @"foo/bar", 0),
+                       DocMutationKey(@"1", @"foo/bar/suffix/key", 0));
+  FSTAssertKeyLessThan(DocMutationKey(@"1", @"foo/bar/suffix/key", 0),
+                       DocMutationKey(@"1", @"foo/bar2", 0));
+
+  // Different batchID:
+  FSTAssertKeyLessThan(DocMutationKey(@"1", @"foo/bar", 0), DocMutationKey(@"1", @"foo/bar", 1));
+}
+
+- (void)testDocumentMutationKeyDescription {
+  FSTAssertExpectedKeyDescription([FSTLevelDBDocumentMutationKey keyPrefix],
+                                  @"[document_mutation: incomplete key]");
+
+  FSTAssertExpectedKeyDescription([FSTLevelDBDocumentMutationKey keyPrefixWithUserID:@"user1"],
+                                  @"[document_mutation: userID=user1 incomplete key]");
+
+  auto key = [FSTLevelDBDocumentMutationKey keyPrefixWithUserID:@"user1"
+                                                   resourcePath:FSTTestPath(@"foo/bar")];
+  FSTAssertExpectedKeyDescription(key,
+                                  @"[document_mutation: userID=user1 key=foo/bar incomplete key]");
+
+  key = [FSTLevelDBDocumentMutationKey keyWithUserID:@"user1"
+                                         documentKey:FSTTestDocKey(@"foo/bar")
+                                             batchID:42];
+  FSTAssertExpectedKeyDescription(key, @"[document_mutation: userID=user1 key=foo/bar batchID=42]");
+}
+
+- (void)testTargetGlobalKeyEncodeDecodeCycle {
+  FSTLevelDBTargetGlobalKey *key = [[FSTLevelDBTargetGlobalKey alloc] init];
+
+  auto encoded = [FSTLevelDBTargetGlobalKey key];
+  BOOL ok = [key decodeKey:encoded];
+  XCTAssertTrue(ok);
+}
+
+- (void)testTargetGlobalKeyDescription {
+  FSTAssertExpectedKeyDescription([FSTLevelDBTargetGlobalKey key], @"[target_global:]");
+}
+
+- (void)testTargetKeyEncodeDecodeCycle {
+  FSTLevelDBTargetKey *key = [[FSTLevelDBTargetKey alloc] init];
+  FSTTargetID targetID = 42;
+
+  auto encoded = [FSTLevelDBTargetKey keyWithTargetID:42];
+  BOOL ok = [key decodeKey:encoded];
+  XCTAssertTrue(ok);
+  XCTAssertEqual(key.targetID, targetID);
+}
+
+- (void)testTargetKeyDescription {
+  FSTAssertExpectedKeyDescription([FSTLevelDBTargetKey keyWithTargetID:42],
+                                  @"[target: targetID=42]");
+}
+
+- (void)testQueryTargetKeyEncodeDecodeCycle {
+  FSTLevelDBQueryTargetKey *key = [[FSTLevelDBQueryTargetKey alloc] init];
+  std::string canonicalID("foo");
+  FSTTargetID targetID = 42;
+
+  auto encoded = [FSTLevelDBQueryTargetKey keyWithCanonicalID:canonicalID targetID:42];
+  BOOL ok = [key decodeKey:encoded];
+  XCTAssertTrue(ok);
+  XCTAssertEqual(key.canonicalID, canonicalID);
+  XCTAssertEqual(key.targetID, targetID);
+}
+
+- (void)testQueryKeyDescription {
+  FSTAssertExpectedKeyDescription([FSTLevelDBQueryTargetKey keyWithCanonicalID:"foo" targetID:42],
+                                  @"[query_target: canonicalID=foo targetID=42]");
+}
+
+- (void)testTargetDocumentKeyEncodeDecodeCycle {
+  FSTLevelDBTargetDocumentKey *key = [[FSTLevelDBTargetDocumentKey alloc] init];
+
+  auto encoded =
+      [FSTLevelDBTargetDocumentKey keyWithTargetID:42 documentKey:FSTTestDocKey(@"foo/bar")];
+  BOOL ok = [key decodeKey:encoded];
+  XCTAssertTrue(ok);
+  XCTAssertEqual(key.targetID, 42);
+  XCTAssertEqualObjects(key.documentKey, FSTTestDocKey(@"foo/bar"));
+}
+
+- (void)testTargetDocumentKeyOrdering {
+  // Different targetID:
+  FSTAssertKeyLessThan(TargetDocKey(1, @"foo/bar"), TargetDocKey(2, @"foo/bar"));
+  FSTAssertKeyLessThan(TargetDocKey(2, @"foo/bar"), TargetDocKey(10, @"foo/bar"));
+  FSTAssertKeyLessThan(TargetDocKey(10, @"foo/bar"), TargetDocKey(100, @"foo/bar"));
+  FSTAssertKeyLessThan(TargetDocKey(42, @"foo/bar"), TargetDocKey(100, @"foo/bar"));
+
+  // Different paths:
+  FSTAssertKeyLessThan(TargetDocKey(1, @"foo/bar"), TargetDocKey(1, @"foo/baz"));
+  FSTAssertKeyLessThan(TargetDocKey(1, @"foo/bar"), TargetDocKey(1, @"foo/bar2"));
+  FSTAssertKeyLessThan(TargetDocKey(1, @"foo/bar"), TargetDocKey(1, @"foo/bar/suffix/key"));
+  FSTAssertKeyLessThan(TargetDocKey(1, @"foo/bar/suffix/key"), TargetDocKey(1, @"foo/bar2"));
+}
+
+- (void)testTargetDocumentKeyDescription {
+  auto key = [FSTLevelDBTargetDocumentKey keyWithTargetID:42 documentKey:FSTTestDocKey(@"foo/bar")];
+  XCTAssertEqualObjects([FSTLevelDBKey descriptionForKey:key],
+                        @"[target_document: targetID=42 key=foo/bar]");
+}
+
+- (void)testDocumentTargetKeyEncodeDecodeCycle {
+  FSTLevelDBDocumentTargetKey *key = [[FSTLevelDBDocumentTargetKey alloc] init];
+
+  auto encoded =
+      [FSTLevelDBDocumentTargetKey keyWithDocumentKey:FSTTestDocKey(@"foo/bar") targetID:42];
+  BOOL ok = [key decodeKey:encoded];
+  XCTAssertTrue(ok);
+  XCTAssertEqualObjects(key.documentKey, FSTTestDocKey(@"foo/bar"));
+  XCTAssertEqual(key.targetID, 42);
+}
+
+- (void)testDocumentTargetKeyDescription {
+  auto key = [FSTLevelDBDocumentTargetKey keyWithDocumentKey:FSTTestDocKey(@"foo/bar") targetID:42];
+  XCTAssertEqualObjects([FSTLevelDBKey descriptionForKey:key],
+                        @"[document_target: key=foo/bar targetID=42]");
+}
+
+- (void)testDocumentTargetKeyOrdering {
+  // Different paths:
+  FSTAssertKeyLessThan(DocTargetKey(@"foo/bar", 1), DocTargetKey(@"foo/baz", 1));
+  FSTAssertKeyLessThan(DocTargetKey(@"foo/bar", 1), DocTargetKey(@"foo/bar2", 1));
+  FSTAssertKeyLessThan(DocTargetKey(@"foo/bar", 1), DocTargetKey(@"foo/bar/suffix/key", 1));
+  FSTAssertKeyLessThan(DocTargetKey(@"foo/bar/suffix/key", 1), DocTargetKey(@"foo/bar2", 1));
+
+  // Different targetID:
+  FSTAssertKeyLessThan(DocTargetKey(@"foo/bar", 1), DocTargetKey(@"foo/bar", 2));
+  FSTAssertKeyLessThan(DocTargetKey(@"foo/bar", 2), DocTargetKey(@"foo/bar", 10));
+  FSTAssertKeyLessThan(DocTargetKey(@"foo/bar", 10), DocTargetKey(@"foo/bar", 100));
+  FSTAssertKeyLessThan(DocTargetKey(@"foo/bar", 42), DocTargetKey(@"foo/bar", 100));
+}
+
+- (void)testRemoteDocumentKeyPrefixing {
+  auto tableKey = [FSTLevelDBRemoteDocumentKey keyPrefix];
+
+  XCTAssertTrue(StartsWith(RemoteDocKey(@"foo/bar"), tableKey));
+
+  // This is critical: foo/bar2 should not contain foo/bar.
+  XCTAssertFalse(StartsWith(RemoteDocKey(@"foo/bar2"), RemoteDocKey(@"foo/bar")));
+
+  // Prefixes must be encoded specially
+  XCTAssertFalse(StartsWith(RemoteDocKey(@"foo/bar/baz/quu"), RemoteDocKey(@"foo/bar")));
+  XCTAssertTrue(StartsWith(RemoteDocKey(@"foo/bar/baz/quu"), RemoteDocKeyPrefix(@"foo/bar")));
+  XCTAssertTrue(StartsWith(RemoteDocKeyPrefix(@"foo/bar/baz/quu"), RemoteDocKeyPrefix(@"foo/bar")));
+  XCTAssertTrue(StartsWith(RemoteDocKeyPrefix(@"foo/bar/baz"), RemoteDocKeyPrefix(@"foo/bar")));
+  XCTAssertTrue(StartsWith(RemoteDocKeyPrefix(@"foo/bar"), RemoteDocKeyPrefix(@"foo")));
+}
+
+- (void)testRemoteDocumentKeyOrdering {
+  FSTAssertKeyLessThan(RemoteDocKey(@"foo/bar"), RemoteDocKey(@"foo/bar2"));
+  FSTAssertKeyLessThan(RemoteDocKey(@"foo/bar"), RemoteDocKey(@"foo/bar/suffix/key"));
+}
+
+- (void)testRemoteDocumentKeyEncodeDecodeCycle {
+  FSTLevelDBRemoteDocumentKey *key = [[FSTLevelDBRemoteDocumentKey alloc] init];
+
+  NSArray<NSString *> *paths = @[ @"foo/bar", @"foo/bar2", @"foo/bar/baz/quux" ];
+  for (NSString *path in paths) {
+    auto encoded = RemoteDocKey(path);
+    BOOL ok = [key decodeKey:encoded];
+    XCTAssertTrue(ok);
+    XCTAssertEqualObjects(key.documentKey, FSTTestDocKey(path));
+  }
+}
+
+- (void)testRemoteDocumentKeyDescription {
+  FSTAssertExpectedKeyDescription(
+      [FSTLevelDBRemoteDocumentKey keyWithDocumentKey:FSTTestDocKey(@"foo/bar/baz/quux")],
+      @"[remote_document: key=foo/bar/baz/quux]");
+}
+
+@end
+
+#undef FSTAssertExpectedKeyDescription
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTLevelDBLocalStoreTests.m b/Firestore/Example/Tests/Local/FSTLevelDBLocalStoreTests.m
new file mode 100644
index 0000000..d426149
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTLevelDBLocalStoreTests.m
@@ -0,0 +1,45 @@
+/*
+ * Copyright 2017 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 "Local/FSTLocalStore.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Auth/FSTUser.h"
+#import "Local/FSTLevelDB.h"
+
+#import "FSTLocalStoreTests.h"
+#import "FSTPersistenceTestHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * The tests for FSTLevelDBLocalStore are performed on the FSTLocalStore protocol in
+ * FSTLocalStoreTests. This class is merely responsible for creating a new FSTPersistence
+ * implementation on demand.
+ */
+@interface FSTLevelDBLocalStoreTests : FSTLocalStoreTests
+@end
+
+@implementation FSTLevelDBLocalStoreTests
+
+- (id<FSTPersistence>)persistence {
+  return [FSTPersistenceTestHelpers levelDBPersistence];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTLevelDBMutationQueueTests.mm b/Firestore/Example/Tests/Local/FSTLevelDBMutationQueueTests.mm
new file mode 100644
index 0000000..1e66aac
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTLevelDBMutationQueueTests.mm
@@ -0,0 +1,158 @@
+/*
+ * Copyright 2017 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 "Local/FSTLevelDBMutationQueue.h"
+
+#import <XCTest/XCTest.h>
+#include <leveldb/db.h>
+
+#import "Protos/objc/firestore/local/Mutation.pbobjc.h"
+#import "Auth/FSTUser.h"
+#import "Local/FSTLevelDB.h"
+#import "Local/FSTLevelDBKey.h"
+#import "Local/FSTWriteGroup.h"
+#include "Port/ordered_code.h"
+
+#import "FSTMutationQueueTests.h"
+#import "FSTPersistenceTestHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+using leveldb::DB;
+using leveldb::Slice;
+using leveldb::Status;
+using leveldb::WriteOptions;
+using Firestore::StringView;
+using Firestore::OrderedCode;
+
+// A dummy mutation value, useful for testing code that's known to examine only mutation keys.
+static const char *kDummy = "1";
+
+/**
+ * Most of the tests for FSTLevelDBMutationQueue are performed on the FSTMutationQueue protocol in
+ * FSTMutationQueueTests. This class is responsible for setting up the @a mutationQueue plus any
+ * additional LevelDB-specific tests.
+ */
+@interface FSTLevelDBMutationQueueTests : FSTMutationQueueTests
+@end
+
+/**
+ * Creates a key that's structurally the same as FSTLevelDBMutationKey except it allows for
+ * nonstandard table names.
+ */
+std::string MutationLikeKey(StringView table, StringView userID, FSTBatchID batchID) {
+  std::string key;
+  OrderedCode::WriteString(&key, table);
+  OrderedCode::WriteString(&key, userID);
+  OrderedCode::WriteSignedNumIncreasing(&key, batchID);
+  return key;
+}
+
+@implementation FSTLevelDBMutationQueueTests {
+  FSTLevelDB *_db;
+}
+
+- (void)setUp {
+  [super setUp];
+  _db = [FSTPersistenceTestHelpers levelDBPersistence];
+  self.mutationQueue = [_db mutationQueueForUser:[[FSTUser alloc] initWithUID:@"user"]];
+  self.persistence = _db;
+
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Start MutationQueue"];
+  [self.mutationQueue startWithGroup:group];
+  [self.persistence commitGroup:group];
+}
+
+- (void)testLoadNextBatchID_zeroWhenTotallyEmpty {
+  // Initial seek is invalid
+  XCTAssertEqual([FSTLevelDBMutationQueue loadNextBatchIDFromDB:_db.ptr], 0);
+}
+
+- (void)testLoadNextBatchID_zeroWhenNoMutations {
+  // Initial seek finds no mutations
+  [self setDummyValueForKey:MutationLikeKey("mutationr", "foo", 20)];
+  [self setDummyValueForKey:MutationLikeKey("mutationsa", "foo", 10)];
+  XCTAssertEqual([FSTLevelDBMutationQueue loadNextBatchIDFromDB:_db.ptr], 0);
+}
+
+- (void)testLoadNextBatchID_findsSingleRow {
+  // Seeks off the end of the table altogether
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"foo" batchID:6]];
+
+  XCTAssertEqual([FSTLevelDBMutationQueue loadNextBatchIDFromDB:_db.ptr], 7);
+}
+
+- (void)testLoadNextBatchID_findsSingleRowAmongNonMutations {
+  // Seeks into table following mutations.
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"foo" batchID:6]];
+  [self setDummyValueForKey:MutationLikeKey("mutationsa", "foo", 10)];
+
+  XCTAssertEqual([FSTLevelDBMutationQueue loadNextBatchIDFromDB:_db.ptr], 7);
+}
+
+- (void)testLoadNextBatchID_findsMaxAcrossUsers {
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"fo" batchID:5]];
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"food" batchID:3]];
+
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"foo" batchID:6]];
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"foo" batchID:2]];
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"foo" batchID:1]];
+
+  XCTAssertEqual([FSTLevelDBMutationQueue loadNextBatchIDFromDB:_db.ptr], 7);
+}
+
+- (void)testLoadNextBatchID_onlyFindsMutations {
+  // Write higher-valued batchIDs in nearby "tables"
+  auto tables = @[ @"mutatio", @"mutationsa", @"bears", @"zombies" ];
+  FSTBatchID highBatchID = 5;
+  for (NSString *table in tables) {
+    [self setDummyValueForKey:MutationLikeKey(table, "", highBatchID++)];
+  }
+
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"bar" batchID:3]];
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"bar" batchID:2]];
+  [self setDummyValueForKey:[FSTLevelDBMutationKey keyWithUserID:@"foo" batchID:1]];
+
+  // None of the higher tables should match -- this is the only entry that's in the mutations
+  // table
+  XCTAssertEqual([FSTLevelDBMutationQueue loadNextBatchIDFromDB:_db.ptr], 4);
+}
+
+- (void)testEmptyProtoCanBeUpgraded {
+  // An empty protocol buffer serializes to a zero-length byte buffer.
+  GPBEmpty *empty = [GPBEmpty message];
+  NSData *emptyData = [empty data];
+  XCTAssertEqual(emptyData.length, 0);
+
+  // Choose some other (arbitrary) proto and parse it from the empty message and it should all be
+  // defaults. This shows that empty proto values within the index row value don't pose any future
+  // liability.
+  NSError *error;
+  FSTPBMutationQueue *parsedMessage = [FSTPBMutationQueue parseFromData:emptyData error:&error];
+  XCTAssertNil(error);
+
+  FSTPBMutationQueue *defaultMessage = [FSTPBMutationQueue message];
+  XCTAssertEqual(parsedMessage.lastAcknowledgedBatchId, defaultMessage.lastAcknowledgedBatchId);
+  XCTAssertEqualObjects(parsedMessage.lastStreamToken, defaultMessage.lastStreamToken);
+}
+
+- (void)setDummyValueForKey:(const std::string &)key {
+  _db.ptr->Put(WriteOptions(), key, kDummy);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTLevelDBQueryCacheTests.m b/Firestore/Example/Tests/Local/FSTLevelDBQueryCacheTests.m
new file mode 100644
index 0000000..8149397
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTLevelDBQueryCacheTests.m
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2017 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 "Local/FSTLevelDBQueryCache.h"
+
+#import "Local/FSTLevelDB.h"
+
+#import "FSTPersistenceTestHelpers.h"
+#import "FSTQueryCacheTests.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLevelDBQueryCacheTests : FSTQueryCacheTests
+@end
+
+/**
+ * The tests for FSTLevelDBQueryCache are performed on the FSTQueryCache protocol in
+ * FSTQueryCacheTests. This class is merely responsible for setting up and tearing down the
+ * @a queryCache.
+ */
+@implementation FSTLevelDBQueryCacheTests
+
+- (void)setUp {
+  [super setUp];
+
+  self.persistence = [FSTPersistenceTestHelpers levelDBPersistence];
+  self.queryCache = [self.persistence queryCache];
+  [self.queryCache start];
+}
+
+- (void)tearDown {
+  [self.queryCache shutdown];
+  self.persistence = nil;
+  self.queryCache = nil;
+
+  [super tearDown];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTLevelDBRemoteDocumentCacheTests.mm b/Firestore/Example/Tests/Local/FSTLevelDBRemoteDocumentCacheTests.mm
new file mode 100644
index 0000000..a6af103
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTLevelDBRemoteDocumentCacheTests.mm
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2017 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 "FSTRemoteDocumentCacheTests.h"
+
+#include <leveldb/db.h>
+
+#import "Local/FSTLevelDB.h"
+#import "Local/FSTLevelDBKey.h"
+#include "Port/ordered_code.h"
+
+#import "FSTPersistenceTestHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+using leveldb::WriteOptions;
+using Firestore::OrderedCode;
+
+// A dummy document value, useful for testing code that's known to examine only document keys.
+static const char *kDummy = "1";
+
+/**
+ * The tests for FSTLevelDBRemoteDocumentCache are performed on the FSTRemoteDocumentCache
+ * protocol in FSTRemoteDocumentCacheTests. This class is merely responsible for setting up and
+ * tearing down the @a remoteDocumentCache.
+ */
+@interface FSTLevelDBRemoteDocumentCacheTests : FSTRemoteDocumentCacheTests
+@end
+
+@implementation FSTLevelDBRemoteDocumentCacheTests {
+  FSTLevelDB *_db;
+}
+
+- (void)setUp {
+  [super setUp];
+  _db = [FSTPersistenceTestHelpers levelDBPersistence];
+  self.persistence = _db;
+  self.remoteDocumentCache = [self.persistence remoteDocumentCache];
+
+  // Write a couple dummy rows that should appear before/after the remote_documents table to make
+  // sure the tests are unaffected.
+  [self writeDummyRowWithSegments:@[ @"remote_documentr", @"foo", @"bar" ]];
+  [self writeDummyRowWithSegments:@[ @"remote_documentsa", @"foo", @"bar" ]];
+}
+
+- (void)tearDown {
+  [self.remoteDocumentCache shutdown];
+  self.remoteDocumentCache = nil;
+  self.persistence = nil;
+  _db = nil;
+  [super tearDown];
+}
+
+- (void)writeDummyRowWithSegments:(NSArray<NSString *> *)segments {
+  std::string key;
+  for (NSString *segment in segments) {
+    OrderedCode::WriteString(&key, segment.UTF8String);
+  }
+
+  _db.ptr->Put(WriteOptions(), key, kDummy);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTLocalSerializerTests.m b/Firestore/Example/Tests/Local/FSTLocalSerializerTests.m
new file mode 100644
index 0000000..0080f89
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTLocalSerializerTests.m
@@ -0,0 +1,181 @@
+/*
+ * Copyright 2017 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 "Local/FSTLocalSerializer.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Core/FSTQuery.h"
+#import "Core/FSTSnapshotVersion.h"
+#import "Core/FSTTimestamp.h"
+#import "Local/FSTQueryData.h"
+#import "Model/FSTDatabaseID.h"
+#import "Model/FSTDocument.h"
+#import "Model/FSTDocumentKey.h"
+#import "Model/FSTFieldValue.h"
+#import "Model/FSTMutation.h"
+#import "Model/FSTMutationBatch.h"
+#import "Model/FSTPath.h"
+#import "Protos/objc/firestore/local/MaybeDocument.pbobjc.h"
+#import "Protos/objc/firestore/local/Mutation.pbobjc.h"
+#import "Protos/objc/firestore/local/Target.pbobjc.h"
+#import "Protos/objc/google/firestore/v1beta1/Common.pbobjc.h"
+#import "Protos/objc/google/firestore/v1beta1/Document.pbobjc.h"
+#import "Protos/objc/google/firestore/v1beta1/Firestore.pbobjc.h"
+#import "Protos/objc/google/firestore/v1beta1/Query.pbobjc.h"
+#import "Protos/objc/google/firestore/v1beta1/Write.pbobjc.h"
+#import "Protos/objc/google/type/Latlng.pbobjc.h"
+#import "Remote/FSTSerializerBeta.h"
+
+#import "FSTHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTSerializerBeta (Test)
+- (GCFSValue *)encodedNull;
+- (GCFSValue *)encodedBool:(BOOL)value;
+- (GCFSValue *)encodedDouble:(double)value;
+- (GCFSValue *)encodedInteger:(int64_t)value;
+- (GCFSValue *)encodedString:(NSString *)value;
+@end
+
+@interface FSTLocalSerializerTests : XCTestCase
+
+@property(nonatomic, strong) FSTLocalSerializer *serializer;
+@property(nonatomic, strong) FSTSerializerBeta *remoteSerializer;
+
+@end
+
+@implementation FSTLocalSerializerTests
+
+- (void)setUp {
+  FSTDatabaseID *databaseID = [FSTDatabaseID databaseIDWithProject:@"p" database:@"d"];
+  self.remoteSerializer = [[FSTSerializerBeta alloc] initWithDatabaseID:databaseID];
+  self.serializer = [[FSTLocalSerializer alloc] initWithRemoteSerializer:self.remoteSerializer];
+}
+
+- (void)testEncodesMutationBatch {
+  FSTMutation *set = FSTTestSetMutation(@"foo/bar", @{ @"a" : @"b", @"num" : @1 });
+  FSTMutation *patch = [[FSTPatchMutation alloc]
+       initWithKey:[FSTDocumentKey keyWithPathString:@"bar/baz"]
+         fieldMask:[[FSTFieldMask alloc] initWithFields:@[ FSTTestFieldPath(@"a") ]]
+             value:FSTTestObjectValue(
+                       @{ @"a" : @"b",
+                          @"num" : @1 })
+      precondition:[FSTPrecondition preconditionWithExists:YES]];
+  FSTMutation *del = FSTTestDeleteMutation(@"baz/quux");
+  FSTTimestamp *writeTime = [FSTTimestamp timestamp];
+  FSTMutationBatch *model = [[FSTMutationBatch alloc] initWithBatchID:42
+                                                       localWriteTime:writeTime
+                                                            mutations:@[ set, patch, del ]];
+
+  GCFSWrite *setProto = [GCFSWrite message];
+  setProto.update.name = @"projects/p/databases/d/documents/foo/bar";
+  [setProto.update.fields addEntriesFromDictionary:@{
+    @"a" : [self.remoteSerializer encodedString:@"b"],
+    @"num" : [self.remoteSerializer encodedInteger:1]
+  }];
+
+  GCFSWrite *patchProto = [GCFSWrite message];
+  patchProto.update.name = @"projects/p/databases/d/documents/bar/baz";
+  [patchProto.update.fields addEntriesFromDictionary:@{
+    @"a" : [self.remoteSerializer encodedString:@"b"],
+    @"num" : [self.remoteSerializer encodedInteger:1]
+  }];
+  [patchProto.updateMask.fieldPathsArray addObjectsFromArray:@[ @"a" ]];
+  patchProto.currentDocument.exists = YES;
+
+  GCFSWrite *delProto = [GCFSWrite message];
+  delProto.delete_p = @"projects/p/databases/d/documents/baz/quux";
+
+  GPBTimestamp *writeTimeProto = [GPBTimestamp message];
+  writeTimeProto.seconds = writeTime.seconds;
+  writeTimeProto.nanos = writeTime.nanos;
+
+  FSTPBWriteBatch *batchProto = [FSTPBWriteBatch message];
+  batchProto.batchId = 42;
+  [batchProto.writesArray addObjectsFromArray:@[ setProto, patchProto, delProto ]];
+  batchProto.localWriteTime = writeTimeProto;
+
+  XCTAssertEqualObjects([self.serializer encodedMutationBatch:model], batchProto);
+  FSTMutationBatch *decoded = [self.serializer decodedMutationBatch:batchProto];
+  XCTAssertEqual(decoded.batchID, model.batchID);
+  XCTAssertEqualObjects(decoded.localWriteTime, model.localWriteTime);
+  XCTAssertEqualObjects(decoded.mutations, model.mutations);
+  XCTAssertEqualObjects([decoded keys], [model keys]);
+}
+
+- (void)testEncodesDocumentAsMaybeDocument {
+  FSTDocument *doc = FSTTestDoc(@"some/path", 42, @{@"foo" : @"bar"}, NO);
+
+  FSTPBMaybeDocument *maybeDocProto = [FSTPBMaybeDocument message];
+  maybeDocProto.document = [GCFSDocument message];
+  maybeDocProto.document.name = @"projects/p/databases/d/documents/some/path";
+  [maybeDocProto.document.fields addEntriesFromDictionary:@{
+    @"foo" : [self.remoteSerializer encodedString:@"bar"],
+  }];
+  maybeDocProto.document.updateTime.seconds = 0;
+  maybeDocProto.document.updateTime.nanos = 42000;
+
+  XCTAssertEqualObjects([self.serializer encodedMaybeDocument:doc], maybeDocProto);
+  FSTMaybeDocument *decoded = [self.serializer decodedMaybeDocument:maybeDocProto];
+  XCTAssertEqualObjects(decoded, doc);
+}
+
+- (void)testEncodesDeletedDocumentAsMaybeDocument {
+  FSTDeletedDocument *deletedDoc = FSTTestDeletedDoc(@"some/path", 42);
+
+  FSTPBMaybeDocument *maybeDocProto = [FSTPBMaybeDocument message];
+  maybeDocProto.noDocument = [FSTPBNoDocument message];
+  maybeDocProto.noDocument.name = @"projects/p/databases/d/documents/some/path";
+  maybeDocProto.noDocument.readTime.seconds = 0;
+  maybeDocProto.noDocument.readTime.nanos = 42000;
+
+  XCTAssertEqualObjects([self.serializer encodedMaybeDocument:deletedDoc], maybeDocProto);
+  FSTMaybeDocument *decoded = [self.serializer decodedMaybeDocument:maybeDocProto];
+  XCTAssertEqualObjects(decoded, deletedDoc);
+}
+
+- (void)testEncodesQueryData {
+  FSTQuery *query = FSTTestQuery(@"room");
+  FSTTargetID targetID = 42;
+  FSTSnapshotVersion *version = FSTTestVersion(1039);
+  NSData *resumeToken = FSTTestResumeTokenFromSnapshotVersion(1039);
+
+  FSTQueryData *queryData = [[FSTQueryData alloc] initWithQuery:query
+                                                       targetID:targetID
+                                                        purpose:FSTQueryPurposeListen
+                                                snapshotVersion:version
+                                                    resumeToken:resumeToken];
+
+  // Let the RPC serializer test various permutations of query serialization.
+  GCFSTarget_QueryTarget *queryTarget = [self.remoteSerializer encodedQueryTarget:query];
+
+  FSTPBTarget *expected = [FSTPBTarget message];
+  expected.targetId = targetID;
+  expected.snapshotVersion.nanos = 1039000;
+  expected.resumeToken = [resumeToken copy];
+  expected.query.parent = queryTarget.parent;
+  expected.query.structuredQuery = queryTarget.structuredQuery;
+
+  XCTAssertEqualObjects([self.serializer encodedQueryData:queryData], expected);
+  FSTQueryData *decoded = [self.serializer decodedQueryData:expected];
+  XCTAssertEqualObjects(decoded, queryData);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTLocalStoreTests.h b/Firestore/Example/Tests/Local/FSTLocalStoreTests.h
new file mode 100644
index 0000000..8e06d82
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTLocalStoreTests.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2017 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 <XCTest/XCTest.h>
+
+@class FSTLocalStore;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * These are tests for any implementation of the FSTLocalStore protocol.
+ *
+ * To test a specific implementation of FSTLocalStore:
+ *
+ * + Subclass FSTLocalStoreTests
+ * + override -persistence, creating a new instance of FSTPersistence.
+ */
+@interface FSTLocalStoreTests : XCTestCase
+
+/** Creates and returns an appropriate id<FSTPersistence> implementation. */
+- (id<FSTPersistence>)persistence;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTLocalStoreTests.m b/Firestore/Example/Tests/Local/FSTLocalStoreTests.m
new file mode 100644
index 0000000..ab492a7
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTLocalStoreTests.m
@@ -0,0 +1,795 @@
+/*
+ * Copyright 2017 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 "Local/FSTLocalStore.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Auth/FSTUser.h"
+#import "Core/FSTQuery.h"
+#import "Core/FSTTimestamp.h"
+#import "Local/FSTEagerGarbageCollector.h"
+#import "Local/FSTLocalWriteResult.h"
+#import "Local/FSTNoOpGarbageCollector.h"
+#import "Local/FSTPersistence.h"
+#import "Local/FSTQueryData.h"
+#import "Model/FSTDocument.h"
+#import "Model/FSTDocumentKey.h"
+#import "Model/FSTDocumentSet.h"
+#import "Model/FSTMutation.h"
+#import "Model/FSTMutationBatch.h"
+#import "Model/FSTPath.h"
+#import "Remote/FSTRemoteEvent.h"
+#import "Remote/FSTWatchChange.h"
+#import "Util/FSTClasses.h"
+
+#import "FSTHelpers.h"
+#import "FSTImmutableSortedDictionary+Testing.h"
+#import "FSTImmutableSortedSet+Testing.h"
+#import "FSTLocalStoreTests.h"
+#import "FSTWatchChange+Testing.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/** Creates a document version dictionary mapping the document in @a mutation to @a version. */
+FSTDocumentVersionDictionary *FSTVersionDictionary(FSTMutation *mutation,
+                                                   FSTTestSnapshotVersion version) {
+  FSTDocumentVersionDictionary *result = [FSTDocumentVersionDictionary documentVersionDictionary];
+  result = [result dictionaryBySettingObject:FSTTestVersion(version) forKey:mutation.key];
+  return result;
+}
+
+@interface FSTLocalStoreTests ()
+
+@property(nonatomic, strong, readwrite) id<FSTPersistence> localStorePersistence;
+@property(nonatomic, strong, readwrite) FSTLocalStore *localStore;
+
+@property(nonatomic, strong, readonly) NSMutableArray<FSTMutationBatch *> *batches;
+@property(nonatomic, strong, readwrite, nullable) FSTMaybeDocumentDictionary *lastChanges;
+@property(nonatomic, assign, readwrite) FSTTargetID lastTargetID;
+
+@end
+
+@implementation FSTLocalStoreTests
+
+- (void)setUp {
+  [super setUp];
+
+  if ([self isTestBaseClass]) {
+    return;
+  }
+
+  id<FSTPersistence> persistence = [self persistence];
+  self.localStorePersistence = persistence;
+  id<FSTGarbageCollector> garbageCollector = [[FSTEagerGarbageCollector alloc] init];
+  self.localStore = [[FSTLocalStore alloc] initWithPersistence:persistence
+                                              garbageCollector:garbageCollector
+                                                   initialUser:[FSTUser unauthenticatedUser]];
+  [self.localStore start];
+
+  _batches = [NSMutableArray array];
+  _lastChanges = nil;
+  _lastTargetID = 0;
+}
+
+- (void)tearDown {
+  [self.localStore shutdown];
+  [self.localStorePersistence shutdown];
+
+  [super tearDown];
+}
+
+- (id<FSTPersistence>)persistence {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+/**
+ * Xcode will run tests from any class that extends XCTestCase, but this doesn't work for
+ * FSTLocalStoreTests since it is incomplete without the implementations supplied by its
+ * subclasses.
+ */
+- (BOOL)isTestBaseClass {
+  return [self class] == [FSTLocalStoreTests class];
+}
+
+/** Restarts the local store using the FSTNoOpGarbageCollector instead of the default. */
+- (void)restartWithNoopGarbageCollector {
+  [self.localStore shutdown];
+
+  id<FSTGarbageCollector> garbageCollector = [[FSTNoOpGarbageCollector alloc] init];
+  self.localStore = [[FSTLocalStore alloc] initWithPersistence:self.localStorePersistence
+                                              garbageCollector:garbageCollector
+                                                   initialUser:[FSTUser unauthenticatedUser]];
+  [self.localStore start];
+}
+
+- (void)writeMutation:(FSTMutation *)mutation {
+  [self writeMutations:@[ mutation ]];
+}
+
+- (void)writeMutations:(NSArray<FSTMutation *> *)mutations {
+  FSTLocalWriteResult *result = [self.localStore locallyWriteMutations:mutations];
+  XCTAssertNotNil(result);
+  [self.batches addObject:[[FSTMutationBatch alloc] initWithBatchID:result.batchID
+                                                     localWriteTime:[FSTTimestamp timestamp]
+                                                          mutations:mutations]];
+  self.lastChanges = result.changes;
+}
+
+- (void)applyRemoteEvent:(FSTRemoteEvent *)event {
+  self.lastChanges = [self.localStore applyRemoteEvent:event];
+}
+
+- (void)notifyLocalViewChanges:(FSTLocalViewChanges *)changes {
+  [self.localStore notifyLocalViewChanges:@[ changes ]];
+}
+
+- (void)acknowledgeMutationWithVersion:(FSTTestSnapshotVersion)documentVersion {
+  FSTMutationBatch *batch = [self.batches firstObject];
+  [self.batches removeObjectAtIndex:0];
+  XCTAssertEqual(batch.mutations.count, 1, @"Acknowledging more than one mutation not supported.");
+  FSTSnapshotVersion *version = FSTTestVersion(documentVersion);
+  FSTMutationResult *mutationResult =
+      [[FSTMutationResult alloc] initWithVersion:version transformResults:nil];
+  FSTMutationBatchResult *result = [FSTMutationBatchResult resultWithBatch:batch
+                                                             commitVersion:version
+                                                           mutationResults:@[ mutationResult ]
+                                                               streamToken:nil];
+  self.lastChanges = [self.localStore acknowledgeBatchWithResult:result];
+}
+
+- (void)rejectMutation {
+  FSTMutationBatch *batch = [self.batches firstObject];
+  [self.batches removeObjectAtIndex:0];
+  self.lastChanges = [self.localStore rejectBatchID:batch.batchID];
+}
+
+- (void)allocateQuery:(FSTQuery *)query {
+  FSTQueryData *queryData = [self.localStore allocateQuery:query];
+  self.lastTargetID = queryData.targetID;
+}
+
+- (void)collectGarbage {
+  [self.localStore collectGarbage];
+}
+
+/** Asserts that the last target ID is the given number. */
+#define FSTAssertTargetID(targetID)              \
+  do {                                           \
+    XCTAssertEqual(self.lastTargetID, targetID); \
+  } while (0)
+
+/** Asserts that a the lastChanges contain the docs in the given array. */
+#define FSTAssertChanged(documents)                                                             \
+  XCTAssertNotNil(self.lastChanges);                                                            \
+  do {                                                                                          \
+    FSTMaybeDocumentDictionary *actual = self.lastChanges;                                      \
+    NSArray<FSTMaybeDocument *> *expected = (documents);                                        \
+    XCTAssertEqual(actual.count, expected.count);                                               \
+    NSEnumerator<FSTMaybeDocument *> *enumerator = expected.objectEnumerator;                   \
+    [actual enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey * key, FSTMaybeDocument * value, \
+                                                BOOL * stop) {                                  \
+      XCTAssertEqualObjects(value, [enumerator nextObject]);                                    \
+    }];                                                                                         \
+    self.lastChanges = nil;                                                                     \
+  } while (0)
+
+/** Asserts that the given keys were removed. */
+#define FSTAssertRemoved(keyPaths)                                                       \
+  XCTAssertNotNil(self.lastChanges);                                                     \
+  do {                                                                                   \
+    FSTMaybeDocumentDictionary *actual = self.lastChanges;                               \
+    XCTAssertEqual(actual.count, keyPaths.count);                                        \
+    NSEnumerator<NSString *> *keyPathEnumerator = keyPaths.objectEnumerator;             \
+    [actual enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey * actualKey,              \
+                                                FSTMaybeDocument * value, BOOL * stop) { \
+      FSTDocumentKey *expectedKey =                                                      \
+          [FSTDocumentKey keyWithPathString:[keyPathEnumerator nextObject]];             \
+      XCTAssertEqualObjects(actualKey, expectedKey);                                     \
+      XCTAssertTrue([value isKindOfClass:[FSTDeletedDocument class]]);                   \
+    }];                                                                                  \
+    self.lastChanges = nil;                                                              \
+  } while (0)
+
+/** Asserts that the given local store contains the given document. */
+#define FSTAssertContains(document)                                         \
+  do {                                                                      \
+    FSTMaybeDocument *expected = (document);                                \
+    FSTMaybeDocument *actual = [self.localStore readDocument:expected.key]; \
+    XCTAssertEqualObjects(actual, expected);                                \
+  } while (0)
+
+/** Asserts that the given local store does not contain the given document. */
+#define FSTAssertNotContains(keyPathString)                                 \
+  do {                                                                      \
+    FSTDocumentKey *key = [FSTDocumentKey keyWithPathString:keyPathString]; \
+    FSTMaybeDocument *actual = [self.localStore readDocument:key];          \
+    XCTAssertNil(actual);                                                   \
+  } while (0)
+
+- (void)testMutationBatchKeys {
+  if ([self isTestBaseClass]) return;
+
+  FSTMutation *set1 = FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"});
+  FSTMutation *set2 = FSTTestSetMutation(@"bar/baz", @{@"bar" : @"baz"});
+  FSTMutationBatch *batch = [[FSTMutationBatch alloc] initWithBatchID:1
+                                                       localWriteTime:[FSTTimestamp timestamp]
+                                                            mutations:@[ set1, set2 ]];
+  FSTDocumentKeySet *keys = [batch keys];
+  XCTAssertEqual(keys.count, 2);
+}
+
+- (void)testHandlesSetMutation {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"})];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+
+  [self acknowledgeMutationWithVersion:0];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, NO));
+}
+
+- (void)testHandlesSetMutationThenDocument {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"})];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(
+                             FSTTestDoc(@"foo/bar", 2, @{@"it" : @"changed"}, NO), @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, YES));
+}
+
+- (void)testHandlesAckThenRejectThenRemoteEvent {
+  if ([self isTestBaseClass]) return;
+
+  // Start a query that requires acks to be held.
+  FSTQuery *query = [FSTQuery queryWithPath:[FSTResourcePath pathWithSegments:@[ @"foo" ]]];
+  [self allocateQuery:query];
+
+  [self writeMutation:FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"})];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+
+  // The last seen version is zero, so this ack must be held.
+  [self acknowledgeMutationWithVersion:1];
+  FSTAssertChanged(@[]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+
+  [self writeMutation:FSTTestSetMutation(@"bar/baz", @{@"bar" : @"baz"})];
+  FSTAssertChanged(@[ FSTTestDoc(@"bar/baz", 0, @{@"bar" : @"baz"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"bar/baz", 0, @{@"bar" : @"baz"}, YES));
+
+  [self rejectMutation];
+  FSTAssertRemoved(@[ @"bar/baz" ]);
+  FSTAssertNotContains(@"bar/baz");
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(
+                             FSTTestDoc(@"foo/bar", 2, @{@"it" : @"changed"}, NO), @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 2, @{@"it" : @"changed"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 2, @{@"it" : @"changed"}, NO));
+  FSTAssertNotContains(@"bar/baz");
+}
+
+- (void)testHandlesDeletedDocumentThenSetMutationThenAck {
+  if ([self isTestBaseClass]) return;
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDeletedDoc(@"foo/bar", 2), @[ @1 ], @[])];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 2));
+
+  [self writeMutation:FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"})];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+
+  [self acknowledgeMutationWithVersion:3];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, NO));
+}
+
+- (void)testHandlesSetMutationThenDeletedDocument {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"})];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDeletedDoc(@"foo/bar", 2), @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+}
+
+- (void)testHandlesDocumentThenSetMutationThenAckThenDocument {
+  if ([self isTestBaseClass]) return;
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 2, @{@"it" : @"base"}, NO),
+                                                  @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 2, @{@"it" : @"base"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 2, @{@"it" : @"base"}, NO));
+
+  [self writeMutation:FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"})];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, YES));
+
+  [self acknowledgeMutationWithVersion:3];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, NO));
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(
+                             FSTTestDoc(@"foo/bar", 3, @{@"it" : @"changed"}, NO), @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 3, @{@"it" : @"changed"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 3, @{@"it" : @"changed"}, NO));
+}
+
+- (void)testHandlesPatchWithoutPriorDocument {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertNotContains(@"foo/bar");
+
+  [self acknowledgeMutationWithVersion:1];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertNotContains(@"foo/bar");
+}
+
+- (void)testHandlesPatchMutationThenDocumentThenAck {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertNotContains(@"foo/bar");
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO),
+                                                  @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar", @"it" : @"base"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar", @"it" : @"base"}, YES));
+
+  [self acknowledgeMutationWithVersion:2];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar", @"it" : @"base"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar", @"it" : @"base"}, NO));
+}
+
+- (void)testHandlesPatchMutationThenAckThenDocument {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertNotContains(@"foo/bar");
+
+  [self acknowledgeMutationWithVersion:1];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertNotContains(@"foo/bar");
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO),
+                                                  @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO));
+}
+
+- (void)testHandlesDeleteMutationThenAck {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestDeleteMutation(@"foo/bar")];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+
+  [self acknowledgeMutationWithVersion:1];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+}
+
+- (void)testHandlesDocumentThenDeleteMutationThenAck {
+  if ([self isTestBaseClass]) return;
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO),
+                                                  @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO));
+
+  [self writeMutation:FSTTestDeleteMutation(@"foo/bar")];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+
+  [self acknowledgeMutationWithVersion:2];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+}
+
+- (void)testHandlesDeleteMutationThenDocumentThenAck {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestDeleteMutation(@"foo/bar")];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO),
+                                                  @[ @1 ], @[])];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+
+  [self acknowledgeMutationWithVersion:2];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+}
+
+- (void)testHandlesDocumentThenDeletedDocumentThenDocument {
+  if ([self isTestBaseClass]) return;
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO),
+                                                  @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO));
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDeletedDoc(@"foo/bar", 2), @[ @1 ], @[])];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 2));
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(
+                             FSTTestDoc(@"foo/bar", 3, @{@"it" : @"changed"}, NO), @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 3, @{@"it" : @"changed"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 3, @{@"it" : @"changed"}, NO));
+}
+
+- (void)testHandlesSetMutationThenPatchMutationThenDocumentThenAckThenAck {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestSetMutation(@"foo/bar", @{@"foo" : @"old"})];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"old"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"old"}, YES));
+
+  [self writeMutation:FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{@"it" : @"base"}, NO),
+                                                  @[ @1 ], @[])];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, YES));
+
+  [self acknowledgeMutationWithVersion:2];  // delete mutation
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, YES));
+
+  [self acknowledgeMutationWithVersion:3];  // patch mutation
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, NO));
+}
+
+- (void)testHandlesSetMutationAndPatchMutationTogether {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutations:@[
+    FSTTestSetMutation(@"foo/bar", @{@"foo" : @"old"}),
+    FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)
+  ]];
+
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+}
+
+- (void)testHandlesSetMutationThenPatchMutationThenReject {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestSetMutation(@"foo/bar", @{@"foo" : @"old"})];
+  [self acknowledgeMutationWithVersion:1];
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"old"}, NO));
+
+  [self writeMutation:FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)];
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+
+  [self rejectMutation];
+  FSTAssertChanged(@[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"old"}, NO) ]);
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"old"}, NO));
+}
+
+- (void)testHandlesSetMutationsAndPatchMutationOfJustOneTogether {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutations:@[
+    FSTTestSetMutation(@"foo/bar", @{@"foo" : @"old"}),
+    FSTTestSetMutation(@"bar/baz", @{@"bar" : @"baz"}),
+    FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)
+  ]];
+
+  FSTAssertChanged((@[
+    FSTTestDoc(@"bar/baz", 0, @{@"bar" : @"baz"}, YES),
+    FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES)
+  ]));
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+  FSTAssertContains(FSTTestDoc(@"bar/baz", 0, @{@"bar" : @"baz"}, YES));
+}
+
+- (void)testHandlesDeleteMutationThenPatchMutationThenAckThenAck {
+  if ([self isTestBaseClass]) return;
+
+  [self writeMutation:FSTTestDeleteMutation(@"foo/bar")];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+
+  [self writeMutation:FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+
+  [self acknowledgeMutationWithVersion:2];  // delete mutation
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+
+  [self acknowledgeMutationWithVersion:3];  // patch mutation
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/bar", 0));
+}
+
+- (void)testCollectsGarbageAfterChangeBatchWithNoTargetIDs {
+  if ([self isTestBaseClass]) return;
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDeletedDoc(@"foo/bar", 2), @[ @1 ], @[])];
+  FSTAssertRemoved(@[ @"foo/bar" ]);
+
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, NO),
+                                                  @[ @1 ], @[])];
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+}
+
+- (void)testCollectsGarbageAfterChangeBatch {
+  if ([self isTestBaseClass]) return;
+
+  FSTQuery *query = [FSTQuery queryWithPath:[FSTResourcePath pathWithSegments:@[ @"foo" ]]];
+  [self allocateQuery:query];
+  FSTAssertTargetID(2);
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, NO),
+                                                  @[ @2 ], @[])];
+  [self collectGarbage];
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"bar"}, NO));
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 2, @{@"foo" : @"baz"}, NO),
+                                                  @[], @[ @2 ])];
+  [self collectGarbage];
+
+  FSTAssertNotContains(@"foo/bar");
+}
+
+- (void)testCollectsGarbageAfterAcknowledgedMutation {
+  if ([self isTestBaseClass]) return;
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"old"}, NO),
+                                                  @[ @1 ], @[])];
+  [self writeMutation:FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)];
+  [self writeMutation:FSTTestSetMutation(@"foo/bah", @{@"foo" : @"bah"})];
+  [self writeMutation:FSTTestDeleteMutation(@"foo/baz")];
+  [self collectGarbage];
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+  FSTAssertContains(FSTTestDoc(@"foo/bah", 0, @{@"foo" : @"bah"}, YES));
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/baz", 0));
+
+  [self acknowledgeMutationWithVersion:3];
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+  FSTAssertContains(FSTTestDoc(@"foo/bah", 0, @{@"foo" : @"bah"}, YES));
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/baz", 0));
+
+  [self acknowledgeMutationWithVersion:4];
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+  FSTAssertNotContains(@"foo/bah");
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/baz", 0));
+
+  [self acknowledgeMutationWithVersion:5];
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+  FSTAssertNotContains(@"foo/bah");
+  FSTAssertNotContains(@"foo/baz");
+}
+
+- (void)testCollectsGarbageAfterRejectedMutation {
+  if ([self isTestBaseClass]) return;
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"old"}, NO),
+                                                  @[ @1 ], @[])];
+  [self writeMutation:FSTTestPatchMutation(@"foo/bar", @{@"foo" : @"bar"}, nil)];
+  [self writeMutation:FSTTestSetMutation(@"foo/bah", @{@"foo" : @"bah"})];
+  [self writeMutation:FSTTestDeleteMutation(@"foo/baz")];
+  [self collectGarbage];
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES));
+  FSTAssertContains(FSTTestDoc(@"foo/bah", 0, @{@"foo" : @"bah"}, YES));
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/baz", 0));
+
+  [self rejectMutation];  // patch mutation
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+  FSTAssertContains(FSTTestDoc(@"foo/bah", 0, @{@"foo" : @"bah"}, YES));
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/baz", 0));
+
+  [self rejectMutation];  // set mutation
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+  FSTAssertNotContains(@"foo/bah");
+  FSTAssertContains(FSTTestDeletedDoc(@"foo/baz", 0));
+
+  [self rejectMutation];  // delete mutation
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+  FSTAssertNotContains(@"foo/bah");
+  FSTAssertNotContains(@"foo/baz");
+}
+
+- (void)testPinsDocumentsInTheLocalView {
+  if ([self isTestBaseClass]) return;
+
+  FSTQuery *query = [FSTQuery queryWithPath:[FSTResourcePath pathWithSegments:@[ @"foo" ]]];
+  [self allocateQuery:query];
+  FSTAssertTargetID(2);
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, NO),
+                                                  @[ @2 ], @[])];
+  [self writeMutation:FSTTestSetMutation(@"foo/baz", @{@"foo" : @"baz"})];
+  [self collectGarbage];
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, NO));
+  FSTAssertContains(FSTTestDoc(@"foo/baz", 0, @{@"foo" : @"baz"}, YES));
+
+  [self notifyLocalViewChanges:FSTTestViewChanges(query, @[ @"foo/bar", @"foo/baz" ], @[])];
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, NO),
+                                                  @[], @[ @2 ])];
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/baz", 2, @{@"foo" : @"baz"}, NO),
+                                                  @[ @1 ], @[])];
+  [self acknowledgeMutationWithVersion:2];
+  [self collectGarbage];
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{@"foo" : @"bar"}, NO));
+  FSTAssertContains(FSTTestDoc(@"foo/baz", 2, @{@"foo" : @"baz"}, NO));
+
+  [self notifyLocalViewChanges:FSTTestViewChanges(query, @[], @[ @"foo/bar", @"foo/baz" ])];
+  [self collectGarbage];
+
+  FSTAssertNotContains(@"foo/bar");
+  FSTAssertNotContains(@"foo/baz");
+}
+
+- (void)testThrowsAwayDocumentsWithUnknownTargetIDsImmediately {
+  if ([self isTestBaseClass]) return;
+
+  FSTTargetID targetID = 321;
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 1, @{}, NO),
+                                                  @[ @(targetID) ], @[])];
+  FSTAssertContains(FSTTestDoc(@"foo/bar", 1, @{}, NO));
+
+  [self collectGarbage];
+  FSTAssertNotContains(@"foo/bar");
+}
+
+- (void)testCanExecuteDocumentQueries {
+  if ([self isTestBaseClass]) return;
+
+  [self.localStore locallyWriteMutations:@[
+    FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"}),
+    FSTTestSetMutation(@"foo/baz", @{@"foo" : @"baz"}),
+    FSTTestSetMutation(@"foo/bar/Foo/Bar", @{@"Foo" : @"Bar"})
+  ]];
+  FSTQuery *query = [FSTQuery queryWithPath:[FSTResourcePath pathWithSegments:@[ @"foo", @"bar" ]]];
+  FSTDocumentDictionary *docs = [self.localStore executeQuery:query];
+  XCTAssertEqualObjects([docs values], @[ FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES) ]);
+}
+
+- (void)testCanExecuteCollectionQueries {
+  if ([self isTestBaseClass]) return;
+
+  [self.localStore locallyWriteMutations:@[
+    FSTTestSetMutation(@"fo/bar", @{@"fo" : @"bar"}),
+    FSTTestSetMutation(@"foo/bar", @{@"foo" : @"bar"}),
+    FSTTestSetMutation(@"foo/baz", @{@"foo" : @"baz"}),
+    FSTTestSetMutation(@"foo/bar/Foo/Bar", @{@"Foo" : @"Bar"}),
+    FSTTestSetMutation(@"fooo/blah", @{@"fooo" : @"blah"})
+  ]];
+  FSTQuery *query = [FSTQuery queryWithPath:[FSTResourcePath pathWithSegments:@[ @"foo" ]]];
+  FSTDocumentDictionary *docs = [self.localStore executeQuery:query];
+  XCTAssertEqualObjects([docs values], (@[
+                          FSTTestDoc(@"foo/bar", 0, @{@"foo" : @"bar"}, YES),
+                          FSTTestDoc(@"foo/baz", 0, @{@"foo" : @"baz"}, YES)
+                        ]));
+}
+
+- (void)testCanExecuteMixedCollectionQueries {
+  if ([self isTestBaseClass]) return;
+
+  FSTQuery *query = [FSTQuery queryWithPath:[FSTResourcePath pathWithSegments:@[ @"foo" ]]];
+  [self allocateQuery:query];
+  FSTAssertTargetID(2);
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/baz", 10, @{@"a" : @"b"}, NO),
+                                                  @[ @2 ], @[])];
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 20, @{@"a" : @"b"}, NO),
+                                                  @[ @2 ], @[])];
+
+  [self.localStore locallyWriteMutations:@[ FSTTestSetMutation(@"foo/bonk", @{@"a" : @"b"}) ]];
+
+  FSTDocumentDictionary *docs = [self.localStore executeQuery:query];
+  XCTAssertEqualObjects([docs values], (@[
+                          FSTTestDoc(@"foo/bar", 20, @{@"a" : @"b"}, NO),
+                          FSTTestDoc(@"foo/baz", 10, @{@"a" : @"b"}, NO),
+                          FSTTestDoc(@"foo/bonk", 0, @{@"a" : @"b"}, YES)
+                        ]));
+}
+
+- (void)testPersistsResumeTokens {
+  if ([self isTestBaseClass]) return;
+
+  // This test only works in the absence of the FSTEagerGarbageCollector.
+  [self restartWithNoopGarbageCollector];
+
+  FSTQuery *query = [FSTQuery queryWithPath:[FSTResourcePath pathWithSegments:@[ @"foo", @"bar" ]]];
+  FSTQueryData *queryData = [self.localStore allocateQuery:query];
+  FSTBoxedTargetID *targetID = @(queryData.targetID);
+  NSData *resumeToken = FSTTestResumeTokenFromSnapshotVersion(1000);
+
+  FSTWatchChange *watchChange =
+      [FSTWatchTargetChange changeWithState:FSTWatchTargetChangeStateCurrent
+                                  targetIDs:@[ targetID ]
+                                resumeToken:resumeToken];
+  NSMutableDictionary<FSTBoxedTargetID *, FSTQueryData *> *listens =
+      [NSMutableDictionary dictionary];
+  listens[targetID] = queryData;
+  NSMutableDictionary<FSTBoxedTargetID *, NSNumber *> *pendingResponses =
+      [NSMutableDictionary dictionary];
+  FSTWatchChangeAggregator *aggregator =
+      [[FSTWatchChangeAggregator alloc] initWithSnapshotVersion:FSTTestVersion(1000)
+                                                  listenTargets:listens
+                                         pendingTargetResponses:pendingResponses];
+  [aggregator addWatchChanges:@[ watchChange ]];
+  FSTRemoteEvent *remoteEvent = [aggregator remoteEvent];
+  [self applyRemoteEvent:remoteEvent];
+
+  // Stop listening so that the query should become inactive (but persistent)
+  [self.localStore releaseQuery:query];
+
+  // Should come back with the same resume token
+  FSTQueryData *queryData2 = [self.localStore allocateQuery:query];
+  XCTAssertEqualObjects(queryData2.resumeToken, resumeToken);
+}
+
+- (void)testRemoteDocumentKeysForTarget {
+  if ([self isTestBaseClass]) return;
+  [self restartWithNoopGarbageCollector];
+
+  FSTQuery *query = [FSTQuery queryWithPath:[FSTResourcePath pathWithSegments:@[ @"foo" ]]];
+  [self allocateQuery:query];
+  FSTAssertTargetID(2);
+
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/baz", 10, @{@"a" : @"b"}, NO),
+                                                  @[ @2 ], @[])];
+  [self applyRemoteEvent:FSTTestUpdateRemoteEvent(FSTTestDoc(@"foo/bar", 20, @{@"a" : @"b"}, NO),
+                                                  @[ @2 ], @[])];
+
+  [self.localStore locallyWriteMutations:@[ FSTTestSetMutation(@"foo/bonk", @{@"a" : @"b"}) ]];
+
+  FSTDocumentKeySet *keys = [self.localStore remoteDocumentKeysForTarget:2];
+  FSTAssertEqualSets(keys, (@[ FSTTestDocKey(@"foo/bar"), FSTTestDocKey(@"foo/baz") ]));
+
+  [self restartWithNoopGarbageCollector];
+
+  keys = [self.localStore remoteDocumentKeysForTarget:2];
+  FSTAssertEqualSets(keys, (@[ FSTTestDocKey(@"foo/bar"), FSTTestDocKey(@"foo/baz") ]));
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTMemoryLocalStoreTests.m b/Firestore/Example/Tests/Local/FSTMemoryLocalStoreTests.m
new file mode 100644
index 0000000..e7486d0
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTMemoryLocalStoreTests.m
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2017 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 "Local/FSTLocalStore.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Local/FSTMemoryPersistence.h"
+
+#import "FSTLocalStoreTests.h"
+#import "FSTPersistenceTestHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * This tests the FSTLocalStore with an FSTMemoryPersistence persistence implementation. The tests
+ * are in FSTLocalStoreTests and this class is merely responsible for creating a new FSTPersistence
+ * implementation on demand.
+ */
+@interface FSTMemoryLocalStoreTests : FSTLocalStoreTests
+@end
+
+@implementation FSTMemoryLocalStoreTests
+
+- (id<FSTPersistence>)persistence {
+  return [FSTPersistenceTestHelpers memoryPersistence];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTMemoryMutationQueueTests.m b/Firestore/Example/Tests/Local/FSTMemoryMutationQueueTests.m
new file mode 100644
index 0000000..4d76393
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTMemoryMutationQueueTests.m
@@ -0,0 +1,42 @@
+/*
+ * Copyright 2017 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 "Local/FSTMemoryMutationQueue.h"
+
+#import "Auth/FSTUser.h"
+#import "Local/FSTMemoryPersistence.h"
+
+#import "FSTMutationQueueTests.h"
+#import "FSTPersistenceTestHelpers.h"
+
+@interface FSTMemoryMutationQueueTests : FSTMutationQueueTests
+@end
+
+/**
+ * The tests for FSTMemoryMutationQueue are performed on the FSTMutationQueue protocol in
+ * FSTMutationQueueTests. This class is merely responsible for setting up the @a mutationQueue.
+ */
+@implementation FSTMemoryMutationQueueTests
+
+- (void)setUp {
+  [super setUp];
+
+  self.persistence = [FSTPersistenceTestHelpers memoryPersistence];
+  self.mutationQueue =
+      [self.persistence mutationQueueForUser:[[FSTUser alloc] initWithUID:@"user"]];
+}
+
+@end
diff --git a/Firestore/Example/Tests/Local/FSTMemoryQueryCacheTests.m b/Firestore/Example/Tests/Local/FSTMemoryQueryCacheTests.m
new file mode 100644
index 0000000..6574647
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTMemoryQueryCacheTests.m
@@ -0,0 +1,54 @@
+/*
+ * Copyright 2017 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 "Local/FSTMemoryQueryCache.h"
+
+#import "Local/FSTMemoryPersistence.h"
+
+#import "FSTPersistenceTestHelpers.h"
+#import "FSTQueryCacheTests.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTMemoryQueryCacheTests : FSTQueryCacheTests
+@end
+
+/**
+ * The tests for FSTMemoryQueryCache are performed on the FSTQueryCache protocol in
+ * FSTQueryCacheTests. This class is merely responsible for setting up and tearing down the
+ * @a queryCache.
+ */
+@implementation FSTMemoryQueryCacheTests
+
+- (void)setUp {
+  [super setUp];
+
+  self.persistence = [FSTPersistenceTestHelpers memoryPersistence];
+  self.queryCache = [self.persistence queryCache];
+  [self.queryCache start];
+}
+
+- (void)tearDown {
+  [self.queryCache shutdown];
+  self.persistence = nil;
+  self.queryCache = nil;
+
+  [super tearDown];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTMemoryRemoteDocumentCacheTests.m b/Firestore/Example/Tests/Local/FSTMemoryRemoteDocumentCacheTests.m
new file mode 100644
index 0000000..7602134
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTMemoryRemoteDocumentCacheTests.m
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2017 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 "Local/FSTMemoryRemoteDocumentCache.h"
+
+#import "Local/FSTMemoryPersistence.h"
+
+#import "FSTPersistenceTestHelpers.h"
+#import "FSTRemoteDocumentCacheTests.h"
+
+@interface FSTMemoryRemoteDocumentCacheTests : FSTRemoteDocumentCacheTests
+@end
+
+/**
+ * The tests for FSTMemoryRemoteDocumentCache are performed on the FSTRemoteDocumentCache
+ * protocol in FSTRemoteDocumentCacheTests. This class is merely responsible for setting up and
+ * tearing down the @a remoteDocumentCache.
+ */
+@implementation FSTMemoryRemoteDocumentCacheTests
+
+- (void)setUp {
+  [super setUp];
+
+  self.persistence = [FSTPersistenceTestHelpers memoryPersistence];
+  self.remoteDocumentCache = [self.persistence remoteDocumentCache];
+}
+
+- (void)tearDown {
+  [self.remoteDocumentCache shutdown];
+  self.persistence = nil;
+  self.remoteDocumentCache = nil;
+
+  [super tearDown];
+}
+
+@end
diff --git a/Firestore/Example/Tests/Local/FSTMutationQueueTests.h b/Firestore/Example/Tests/Local/FSTMutationQueueTests.h
new file mode 100644
index 0000000..0193c36
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTMutationQueueTests.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2017 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 <XCTest/XCTest.h>
+
+@protocol FSTMutationQueue;
+@protocol FSTPersistence;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * These are tests for any implementation of the FSTMutationQueue protocol.
+ *
+ * To test a specific implementation of FSTMutationQueue:
+ *
+ * + Subclass FSTMutationQueueTests
+ * + override -setUp, assigning to mutationQueue and persistence
+ * + override -tearDown, cleaning up mutationQueue and persistence
+ */
+@interface FSTMutationQueueTests : XCTestCase
+@property(nonatomic, strong, nullable) id<FSTMutationQueue> mutationQueue;
+@property(nonatomic, strong, nullable) id<FSTPersistence> persistence;
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTMutationQueueTests.m b/Firestore/Example/Tests/Local/FSTMutationQueueTests.m
new file mode 100644
index 0000000..42ba0b3
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTMutationQueueTests.m
@@ -0,0 +1,511 @@
+/*
+ * Copyright 2017 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 "FSTMutationQueueTests.h"
+
+#import "Auth/FSTUser.h"
+#import "Core/FSTQuery.h"
+#import "Core/FSTTimestamp.h"
+#import "Local/FSTEagerGarbageCollector.h"
+#import "Local/FSTMutationQueue.h"
+#import "Local/FSTPersistence.h"
+#import "Local/FSTWriteGroup.h"
+#import "Model/FSTMutation.h"
+#import "Model/FSTMutationBatch.h"
+
+#import "FSTHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTMutationQueueTests
+
+- (void)tearDown {
+  [self.mutationQueue shutdown];
+  [self.persistence shutdown];
+  [super tearDown];
+}
+
+/**
+ * Xcode will run tests from any class that extends XCTestCase, but this doesn't work for
+ * FSTMutationQueueTests since it is incomplete without the implementations supplied by its
+ * subclasses.
+ */
+- (BOOL)isTestBaseClass {
+  return [self class] == [FSTMutationQueueTests class];
+}
+
+- (void)testCountBatches {
+  if ([self isTestBaseClass]) return;
+
+  XCTAssertEqual(0, [self batchCount]);
+  XCTAssertTrue([self.mutationQueue isEmpty]);
+
+  FSTMutationBatch *batch1 = [self addMutationBatch];
+  XCTAssertEqual(1, [self batchCount]);
+  XCTAssertFalse([self.mutationQueue isEmpty]);
+
+  FSTMutationBatch *batch2 = [self addMutationBatch];
+  XCTAssertEqual(2, [self batchCount]);
+
+  [self removeMutationBatches:@[ batch2 ]];
+  XCTAssertEqual(1, [self batchCount]);
+
+  [self removeMutationBatches:@[ batch1 ]];
+  XCTAssertEqual(0, [self batchCount]);
+  XCTAssertTrue([self.mutationQueue isEmpty]);
+}
+
+- (void)testAcknowledgeBatchID {
+  if ([self isTestBaseClass]) return;
+
+  // Initial state of an empty queue
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], kFSTBatchIDUnknown);
+
+  // Adding mutation batches should not change the highest acked batchID.
+  FSTMutationBatch *batch1 = [self addMutationBatch];
+  FSTMutationBatch *batch2 = [self addMutationBatch];
+  FSTMutationBatch *batch3 = [self addMutationBatch];
+  XCTAssertGreaterThan(batch1.batchID, kFSTBatchIDUnknown);
+  XCTAssertGreaterThan(batch2.batchID, batch1.batchID);
+  XCTAssertGreaterThan(batch3.batchID, batch2.batchID);
+
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], kFSTBatchIDUnknown);
+
+  [self acknowledgeBatch:batch1];
+  [self acknowledgeBatch:batch2];
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], batch2.batchID);
+
+  [self removeMutationBatches:@[ batch1 ]];
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], batch2.batchID);
+
+  [self removeMutationBatches:@[ batch2 ]];
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], batch2.batchID);
+
+  // Batch 3 never acknowledged.
+  [self removeMutationBatches:@[ batch3 ]];
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], batch2.batchID);
+}
+
+- (void)testAcknowledgeThenRemove {
+  if ([self isTestBaseClass]) return;
+
+  FSTMutationBatch *batch1 = [self addMutationBatch];
+
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:NSStringFromSelector(_cmd)];
+  [self.mutationQueue acknowledgeBatch:batch1 streamToken:nil group:group];
+  [self.mutationQueue removeMutationBatches:@[ batch1 ] group:group];
+  [self.persistence commitGroup:group];
+
+  XCTAssertEqual([self batchCount], 0);
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], batch1.batchID);
+}
+
+- (void)testHighestAcknowledgedBatchIDNeverExceedsNextBatchID {
+  if ([self isTestBaseClass]) return;
+
+  FSTMutationBatch *batch1 = [self addMutationBatch];
+  FSTMutationBatch *batch2 = [self addMutationBatch];
+  [self acknowledgeBatch:batch1];
+  [self acknowledgeBatch:batch2];
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], batch2.batchID);
+
+  [self removeMutationBatches:@[ batch1, batch2 ]];
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], batch2.batchID);
+
+  // Restart the queue so that nextBatchID will be reset.
+  [self.mutationQueue shutdown];
+  self.mutationQueue =
+      [self.persistence mutationQueueForUser:[[FSTUser alloc] initWithUID:@"user"]];
+
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Start MutationQueue"];
+  [self.mutationQueue startWithGroup:group];
+  [self.persistence commitGroup:group];
+
+  // Verify that on restart with an empty queue, nextBatchID falls to a lower value.
+  XCTAssertLessThan(self.mutationQueue.nextBatchID, batch2.batchID);
+
+  // As a result highestAcknowledgedBatchID must also reset lower.
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], kFSTBatchIDUnknown);
+
+  // The mutation queue will reset the next batchID after all mutations are removed so adding
+  // another mutation will cause a collision.
+  FSTMutationBatch *newBatch = [self addMutationBatch];
+  XCTAssertEqual(newBatch.batchID, batch1.batchID);
+
+  // Restart the queue with one unacknowledged batch in it.
+  group = [self.persistence startGroupWithAction:@"Start MutationQueue"];
+  [self.mutationQueue startWithGroup:group];
+  [self.persistence commitGroup:group];
+
+  XCTAssertEqual([self.mutationQueue nextBatchID], newBatch.batchID + 1);
+
+  // highestAcknowledgedBatchID must still be kFSTBatchIDUnknown.
+  XCTAssertEqual([self.mutationQueue highestAcknowledgedBatchID], kFSTBatchIDUnknown);
+}
+
+- (void)testLookupMutationBatch {
+  if ([self isTestBaseClass]) return;
+
+  // Searching on an empty queue should not find a non-existent batch
+  FSTMutationBatch *notFound = [self.mutationQueue lookupMutationBatch:42];
+  XCTAssertNil(notFound);
+
+  NSMutableArray<FSTMutationBatch *> *batches = [self createBatches:10];
+  NSArray<FSTMutationBatch *> *removed = [self makeHoles:@[ @2, @6, @7 ] inBatches:batches];
+
+  // After removing, a batch should not be found
+  for (NSUInteger i = 0; i < removed.count; i++) {
+    notFound = [self.mutationQueue lookupMutationBatch:removed[i].batchID];
+    XCTAssertNil(notFound);
+  }
+
+  // Remaining entries should still be found
+  for (FSTMutationBatch *batch in batches) {
+    FSTMutationBatch *found = [self.mutationQueue lookupMutationBatch:batch.batchID];
+    XCTAssertEqual(found.batchID, batch.batchID);
+  }
+
+  // Even on a nonempty queue searching should not find a non-existent batch
+  notFound = [self.mutationQueue lookupMutationBatch:42];
+  XCTAssertNil(notFound);
+}
+
+- (void)testNextMutationBatchAfterBatchID {
+  if ([self isTestBaseClass]) return;
+
+  NSMutableArray<FSTMutationBatch *> *batches = [self createBatches:10];
+
+  // This is an array of successors assuming the removals below will happen:
+  NSArray<FSTMutationBatch *> *afters = @[ batches[3], batches[8], batches[8] ];
+  NSArray<FSTMutationBatch *> *removed = [self makeHoles:@[ @2, @6, @7 ] inBatches:batches];
+
+  for (NSUInteger i = 0; i < batches.count - 1; i++) {
+    FSTMutationBatch *current = batches[i];
+    FSTMutationBatch *next = batches[i + 1];
+    FSTMutationBatch *found = [self.mutationQueue nextMutationBatchAfterBatchID:current.batchID];
+    XCTAssertEqual(found.batchID, next.batchID);
+  }
+
+  for (NSUInteger i = 0; i < removed.count; i++) {
+    FSTMutationBatch *current = removed[i];
+    FSTMutationBatch *next = afters[i];
+    FSTMutationBatch *found = [self.mutationQueue nextMutationBatchAfterBatchID:current.batchID];
+    XCTAssertEqual(found.batchID, next.batchID);
+  }
+
+  FSTMutationBatch *first = batches[0];
+  FSTMutationBatch *found = [self.mutationQueue nextMutationBatchAfterBatchID:first.batchID - 42];
+  XCTAssertEqual(found.batchID, first.batchID);
+
+  FSTMutationBatch *last = batches[batches.count - 1];
+  FSTMutationBatch *notFound = [self.mutationQueue nextMutationBatchAfterBatchID:last.batchID];
+  XCTAssertNil(notFound);
+}
+
+- (void)testAllMutationBatchesThroughBatchID {
+  if ([self isTestBaseClass]) return;
+
+  NSMutableArray<FSTMutationBatch *> *batches = [self createBatches:10];
+  [self makeHoles:@[ @2, @6, @7 ] inBatches:batches];
+
+  NSArray<FSTMutationBatch *> *found, *expected;
+
+  found = [self.mutationQueue allMutationBatchesThroughBatchID:batches[0].batchID - 1];
+  XCTAssertEqualObjects(found, (@[]));
+
+  for (NSUInteger i = 0; i < batches.count; i++) {
+    found = [self.mutationQueue allMutationBatchesThroughBatchID:batches[i].batchID];
+    expected = [batches subarrayWithRange:NSMakeRange(0, i + 1)];
+    XCTAssertEqualObjects(found, expected, @"for index %lu", (unsigned long)i);
+  }
+}
+
+- (void)testAllMutationBatchesAffectingDocumentKey {
+  if ([self isTestBaseClass]) return;
+
+  NSArray<FSTMutation *> *mutations = @[
+    FSTTestSetMutation(@"fob/bar",
+                       @{ @"a" : @1 }),
+    FSTTestSetMutation(@"foo/bar",
+                       @{ @"a" : @1 }),
+    FSTTestPatchMutation(@"foo/bar",
+                         @{ @"b" : @1 }, nil),
+    FSTTestSetMutation(@"foo/bar/suffix/key",
+                       @{ @"a" : @1 }),
+    FSTTestSetMutation(@"foo/baz",
+                       @{ @"a" : @1 }),
+    FSTTestSetMutation(@"food/bar",
+                       @{ @"a" : @1 })
+  ];
+
+  // Store all the mutations.
+  NSMutableArray<FSTMutationBatch *> *batches = [NSMutableArray array];
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"New mutation batch"];
+  for (FSTMutation *mutation in mutations) {
+    FSTMutationBatch *batch =
+        [self.mutationQueue addMutationBatchWithWriteTime:[FSTTimestamp timestamp]
+                                                mutations:@[ mutation ]
+                                                    group:group];
+    [batches addObject:batch];
+  }
+  [self.persistence commitGroup:group];
+
+  NSArray<FSTMutationBatch *> *expected = @[ batches[1], batches[2] ];
+  NSArray<FSTMutationBatch *> *matches =
+      [self.mutationQueue allMutationBatchesAffectingDocumentKey:FSTTestDocKey(@"foo/bar")];
+
+  XCTAssertEqualObjects(matches, expected);
+}
+
+- (void)testAllMutationBatchesAffectingQuery {
+  if ([self isTestBaseClass]) return;
+
+  NSArray<FSTMutation *> *mutations = @[
+    FSTTestSetMutation(@"fob/bar",
+                       @{ @"a" : @1 }),
+    FSTTestSetMutation(@"foo/bar",
+                       @{ @"a" : @1 }),
+    FSTTestPatchMutation(@"foo/bar",
+                         @{ @"b" : @1 }, nil),
+    FSTTestSetMutation(@"foo/bar/suffix/key",
+                       @{ @"a" : @1 }),
+    FSTTestSetMutation(@"foo/baz",
+                       @{ @"a" : @1 }),
+    FSTTestSetMutation(@"food/bar",
+                       @{ @"a" : @1 })
+  ];
+
+  // Store all the mutations.
+  NSMutableArray<FSTMutationBatch *> *batches = [NSMutableArray array];
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"New mutation batch"];
+  for (FSTMutation *mutation in mutations) {
+    FSTMutationBatch *batch =
+        [self.mutationQueue addMutationBatchWithWriteTime:[FSTTimestamp timestamp]
+                                                mutations:@[ mutation ]
+                                                    group:group];
+    [batches addObject:batch];
+  }
+  [self.persistence commitGroup:group];
+
+  NSArray<FSTMutationBatch *> *expected = @[ batches[1], batches[2], batches[4] ];
+  FSTQuery *query = [FSTQuery queryWithPath:FSTTestPath(@"foo")];
+  NSArray<FSTMutationBatch *> *matches =
+      [self.mutationQueue allMutationBatchesAffectingQuery:query];
+
+  XCTAssertEqualObjects(matches, expected);
+}
+
+- (void)testRemoveMutationBatches {
+  if ([self isTestBaseClass]) return;
+
+  NSMutableArray<FSTMutationBatch *> *batches = [self createBatches:10];
+  FSTMutationBatch *last = batches[batches.count - 1];
+
+  [self removeMutationBatches:@[ batches[0] ]];
+  [batches removeObjectAtIndex:0];
+  XCTAssertEqual([self batchCount], 9);
+
+  NSArray<FSTMutationBatch *> *found;
+
+  found = [self.mutationQueue allMutationBatchesThroughBatchID:last.batchID];
+  XCTAssertEqualObjects(found, batches);
+  XCTAssertEqual(found.count, 9);
+
+  [self removeMutationBatches:@[ batches[0], batches[1], batches[2] ]];
+  [batches removeObjectsInRange:NSMakeRange(0, 3)];
+  XCTAssertEqual([self batchCount], 6);
+
+  found = [self.mutationQueue allMutationBatchesThroughBatchID:last.batchID];
+  XCTAssertEqualObjects(found, batches);
+  XCTAssertEqual(found.count, 6);
+
+  [self removeMutationBatches:@[ batches[batches.count - 1] ]];
+  [batches removeObjectAtIndex:batches.count - 1];
+  XCTAssertEqual([self batchCount], 5);
+
+  found = [self.mutationQueue allMutationBatchesThroughBatchID:last.batchID];
+  XCTAssertEqualObjects(found, batches);
+  XCTAssertEqual(found.count, 5);
+
+  [self removeMutationBatches:@[ batches[3] ]];
+  [batches removeObjectAtIndex:3];
+  XCTAssertEqual([self batchCount], 4);
+
+  [self removeMutationBatches:@[ batches[1] ]];
+  [batches removeObjectAtIndex:1];
+  XCTAssertEqual([self batchCount], 3);
+
+  found = [self.mutationQueue allMutationBatchesThroughBatchID:last.batchID];
+  XCTAssertEqualObjects(found, batches);
+  XCTAssertEqual(found.count, 3);
+  XCTAssertFalse([self.mutationQueue isEmpty]);
+
+  [self removeMutationBatches:batches];
+  found = [self.mutationQueue allMutationBatchesThroughBatchID:last.batchID];
+  XCTAssertEqualObjects(found, @[]);
+  XCTAssertEqual(found.count, 0);
+  XCTAssertTrue([self.mutationQueue isEmpty]);
+}
+
+- (void)testRemoveMutationBatchesEmitsGarbageEvents {
+  if ([self isTestBaseClass]) return;
+
+  FSTEagerGarbageCollector *garbageCollector = [[FSTEagerGarbageCollector alloc] init];
+  [garbageCollector addGarbageSource:self.mutationQueue];
+
+  NSMutableArray<FSTMutationBatch *> *batches = [NSMutableArray array];
+  [batches addObjectsFromArray:@[
+    [self addMutationBatchWithKey:@"foo/bar"],
+    [self addMutationBatchWithKey:@"foo/ba"],
+    [self addMutationBatchWithKey:@"foo/bar2"],
+    [self addMutationBatchWithKey:@"foo/bar"],
+    [self addMutationBatchWithKey:@"foo/bar/suffix/baz"],
+    [self addMutationBatchWithKey:@"bar/baz"],
+  ]];
+
+  [self removeMutationBatches:@[ batches[0] ]];
+  NSSet<FSTDocumentKey *> *garbage = [garbageCollector collectGarbage];
+  FSTAssertEqualSets(garbage, @[]);
+
+  [self removeMutationBatches:@[ batches[1] ]];
+  garbage = [garbageCollector collectGarbage];
+  FSTAssertEqualSets(garbage, @[ FSTTestDocKey(@"foo/ba") ]);
+
+  [self removeMutationBatches:@[ batches[5] ]];
+  garbage = [garbageCollector collectGarbage];
+  FSTAssertEqualSets(garbage, @[ FSTTestDocKey(@"bar/baz") ]);
+
+  [self removeMutationBatches:@[ batches[2], batches[3] ]];
+  garbage = [garbageCollector collectGarbage];
+  FSTAssertEqualSets(garbage, (@[ FSTTestDocKey(@"foo/bar"), FSTTestDocKey(@"foo/bar2") ]));
+
+  [batches addObject:[self addMutationBatchWithKey:@"foo/bar/suffix/baz"]];
+  garbage = [garbageCollector collectGarbage];
+  FSTAssertEqualSets(garbage, @[]);
+
+  [self removeMutationBatches:@[ batches[4], batches[6] ]];
+  garbage = [garbageCollector collectGarbage];
+  FSTAssertEqualSets(garbage, @[ FSTTestDocKey(@"foo/bar/suffix/baz") ]);
+}
+
+- (void)testStreamToken {
+  if ([self isTestBaseClass]) return;
+
+  NSData *streamToken1 = [@"token1" dataUsingEncoding:NSUTF8StringEncoding];
+  NSData *streamToken2 = [@"token2" dataUsingEncoding:NSUTF8StringEncoding];
+
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"initial stream token"];
+  [self.mutationQueue setLastStreamToken:streamToken1 group:group];
+  [self.persistence commitGroup:group];
+
+  FSTMutationBatch *batch1 = [self addMutationBatch];
+  [self addMutationBatch];
+
+  XCTAssertEqualObjects([self.mutationQueue lastStreamToken], streamToken1);
+
+  group = [self.persistence startGroupWithAction:@"acknowledgeBatchID"];
+  [self.mutationQueue acknowledgeBatch:batch1 streamToken:streamToken2 group:group];
+  [self.persistence commitGroup:group];
+
+  XCTAssertEqual(self.mutationQueue.highestAcknowledgedBatchID, batch1.batchID);
+  XCTAssertEqualObjects([self.mutationQueue lastStreamToken], streamToken2);
+}
+
+/** Creates a new FSTMutationBatch with the next batch ID and a set of dummy mutations. */
+- (FSTMutationBatch *)addMutationBatch {
+  return [self addMutationBatchWithKey:@"foo/bar"];
+}
+
+/**
+ * Creates a new FSTMutationBatch with the given key, the next batch ID and a set of dummy
+ * mutations.
+ */
+- (FSTMutationBatch *)addMutationBatchWithKey:(NSString *)key {
+  FSTSetMutation *mutation = FSTTestSetMutation(key, @{ @"a" : @1 });
+
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"New mutation batch"];
+  FSTMutationBatch *batch =
+      [self.mutationQueue addMutationBatchWithWriteTime:[FSTTimestamp timestamp]
+                                              mutations:@[ mutation ]
+                                                  group:group];
+  [self.persistence commitGroup:group];
+  return batch;
+}
+
+/**
+ * Creates an array of batches containing @a number dummy FSTMutationBatches. Each has a different
+ * batchID.
+ */
+- (NSMutableArray<FSTMutationBatch *> *)createBatches:(int)number {
+  NSMutableArray<FSTMutationBatch *> *batches = [NSMutableArray array];
+
+  for (int i = 0; i < number; i++) {
+    FSTMutationBatch *batch = [self addMutationBatch];
+    [batches addObject:batch];
+  }
+
+  return batches;
+}
+
+/**
+ * Calls -acknowledgeBatch:streamToken:group: on the mutation queue in a new group and commits the
+ * the group.
+ */
+- (void)acknowledgeBatch:(FSTMutationBatch *)batch {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Ack batchID"];
+  [self.mutationQueue acknowledgeBatch:batch streamToken:nil group:group];
+  [self.persistence commitGroup:group];
+}
+
+/**
+ * Calls -removeMutationBatches:group: on the mutation queue in a new group and commits the group.
+ */
+- (void)removeMutationBatches:(NSArray<FSTMutationBatch *> *)batches {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"Remove mutation batch"];
+  [self.mutationQueue removeMutationBatches:batches group:group];
+  [self.persistence commitGroup:group];
+}
+
+/** Returns the number of mutation batches in the mutation queue. */
+- (NSUInteger)batchCount {
+  return [self.mutationQueue allMutationBatches].count;
+}
+
+/**
+ * Removes entries from from the given @a batches and returns them.
+ *
+ * @param holes An array of indexes in the batches array; in increasing order. Indexes are relative
+ *     to the original state of the batches array, not any intermediate state that might occur.
+ * @param batches The array to mutate, removing entries from it.
+ * @return A new array containing all the entries that were removed from @a batches.
+ */
+- (NSArray<FSTMutationBatch *> *)makeHoles:(NSArray<NSNumber *> *)holes
+                                 inBatches:(NSMutableArray<FSTMutationBatch *> *)batches {
+  NSMutableArray<FSTMutationBatch *> *removed = [NSMutableArray array];
+  for (NSUInteger i = 0; i < holes.count; i++) {
+    NSUInteger index = holes[i].unsignedIntegerValue - i;
+    FSTMutationBatch *batch = batches[index];
+    [self removeMutationBatches:@[ batch ]];
+
+    [batches removeObjectAtIndex:index];
+    [removed addObject:batch];
+  }
+  return removed;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTPersistenceTestHelpers.h b/Firestore/Example/Tests/Local/FSTPersistenceTestHelpers.h
new file mode 100644
index 0000000..936bacf
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTPersistenceTestHelpers.h
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2017 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>
+
+@class FSTLevelDB;
+@class FSTMemoryPersistence;
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTPersistenceTestHelpers : NSObject
+
+/**
+ * Creates and starts a new FSTLevelDB instance for testing, destroying any previous contents
+ * if they existed.
+ *
+ * Note that in order to avoid generating a bunch of garbage on the filesystem, the path of the
+ * database is reused. This prevents concurrent running of tests using this database. We may
+ * need to revisit this if we want to parallelize the tests.
+ */
++ (FSTLevelDB *)levelDBPersistence;
+
+/** Creates and starts a new FSTMemoryPersistence instance for testing. */
++ (FSTMemoryPersistence *)memoryPersistence;
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTPersistenceTestHelpers.m b/Firestore/Example/Tests/Local/FSTPersistenceTestHelpers.m
new file mode 100644
index 0000000..f3d7914
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTPersistenceTestHelpers.m
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2017 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 "FSTPersistenceTestHelpers.h"
+
+#import "Local/FSTLevelDB.h"
+#import "Local/FSTLocalSerializer.h"
+#import "Local/FSTMemoryPersistence.h"
+#import "Model/FSTDatabaseID.h"
+#import "Remote/FSTSerializerBeta.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTPersistenceTestHelpers
+
++ (FSTLevelDB *)levelDBPersistence {
+  NSError *error;
+  NSFileManager *files = [NSFileManager defaultManager];
+
+  NSString *dir =
+      [NSTemporaryDirectory() stringByAppendingPathComponent:@"FSTPersistenceTestHelpers"];
+  if ([files fileExistsAtPath:dir]) {
+    // Delete the directory first to ensure isolation between runs.
+    BOOL success = [files removeItemAtPath:dir error:&error];
+    if (!success) {
+      [NSException raise:NSInternalInconsistencyException
+                  format:@"Failed to clean up leveldb path %@: %@", dir, error];
+    }
+  }
+
+  FSTDatabaseID *databaseID = [FSTDatabaseID databaseIDWithProject:@"p" database:@"d"];
+  FSTSerializerBeta *remoteSerializer = [[FSTSerializerBeta alloc] initWithDatabaseID:databaseID];
+  FSTLocalSerializer *serializer =
+      [[FSTLocalSerializer alloc] initWithRemoteSerializer:remoteSerializer];
+  FSTLevelDB *db = [[FSTLevelDB alloc] initWithDirectory:dir serializer:serializer];
+  BOOL success = [db start:&error];
+  if (!success) {
+    [NSException raise:NSInternalInconsistencyException
+                format:@"Failed to create leveldb path %@: %@", dir, error];
+  }
+
+  return db;
+}
+
++ (FSTMemoryPersistence *)memoryPersistence {
+  NSError *error;
+  FSTMemoryPersistence *persistence = [FSTMemoryPersistence persistence];
+  BOOL success = [persistence start:&error];
+  if (!success) {
+    [NSException raise:NSInternalInconsistencyException
+                format:@"Failed to start memory persistence: %@", error];
+  }
+
+  return persistence;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTQueryCacheTests.h b/Firestore/Example/Tests/Local/FSTQueryCacheTests.h
new file mode 100644
index 0000000..a615372
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTQueryCacheTests.h
@@ -0,0 +1,47 @@
+/*
+ * Copyright 2017 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 "Local/FSTQueryCache.h"
+
+#import <XCTest/XCTest.h>
+
+@protocol FSTPersistence;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * These are tests for any implementation of the FSTQueryCache protocol.
+ *
+ * To test a specific implementation of FSTQueryCache:
+ *
+ * + Subclass FSTQueryCacheTests
+ * + override -setUp, assigning to queryCache and persistence
+ * + override -tearDown, cleaning up queryCache and persistence
+ */
+@interface FSTQueryCacheTests : XCTestCase
+
+/** The implementation of the query cache to test. */
+@property(nonatomic, strong, nullable) id<FSTQueryCache> queryCache;
+
+/**
+ * The persistence implementation to use while testing the queryCache (e.g. for committing write
+ * groups).
+ */
+@property(nonatomic, strong, nullable) id<FSTPersistence> persistence;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTQueryCacheTests.m b/Firestore/Example/Tests/Local/FSTQueryCacheTests.m
new file mode 100644
index 0000000..ed409b4
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTQueryCacheTests.m
@@ -0,0 +1,375 @@
+/*
+ * Copyright 2017 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 "FSTQueryCacheTests.h"
+
+#import "Core/FSTQuery.h"
+#import "Core/FSTSnapshotVersion.h"
+#import "Local/FSTEagerGarbageCollector.h"
+#import "Local/FSTPersistence.h"
+#import "Local/FSTQueryData.h"
+#import "Local/FSTWriteGroup.h"
+#import "Model/FSTDocumentKey.h"
+
+#import "FSTHelpers.h"
+#import "FSTImmutableSortedSet+Testing.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTQueryCacheTests {
+  FSTQuery *_queryRooms;
+}
+
+- (void)setUp {
+  [super setUp];
+
+  _queryRooms = FSTTestQuery(@"rooms");
+}
+
+/**
+ * Xcode will run tests from any class that extends XCTestCase, but this doesn't work for
+ * FSTSpecTests since it is incomplete without the implementations supplied by its subclasses.
+ */
+- (BOOL)isTestBaseClass {
+  return [self class] == [FSTQueryCacheTests class];
+}
+
+- (void)testReadQueryNotInCache {
+  if ([self isTestBaseClass]) return;
+
+  XCTAssertNil([self.queryCache queryDataForQuery:_queryRooms]);
+}
+
+- (void)testSetAndReadAQuery {
+  if ([self isTestBaseClass]) return;
+
+  FSTQueryData *queryData = [self queryDataWithQuery:_queryRooms targetID:1 version:1];
+  [self addQueryData:queryData];
+
+  FSTQueryData *result = [self.queryCache queryDataForQuery:_queryRooms];
+  XCTAssertEqualObjects(result.query, queryData.query);
+  XCTAssertEqual(result.targetID, queryData.targetID);
+  XCTAssertEqualObjects(result.resumeToken, queryData.resumeToken);
+}
+
+- (void)testCanonicalIDCollision {
+  if ([self isTestBaseClass]) return;
+
+  // Type information is currently lost in our canonicalID implementations so this currently an
+  // easy way to force colliding canonicalIDs
+  FSTQuery *q1 = [[FSTQuery queryWithPath:FSTTestPath(@"a")]
+      queryByAddingFilter:FSTTestFilter(@"foo", @"==", @(1))];
+  FSTQuery *q2 = [[FSTQuery queryWithPath:FSTTestPath(@"a")]
+      queryByAddingFilter:FSTTestFilter(@"foo", @"==", @"1")];
+  XCTAssertEqualObjects(q1.canonicalID, q2.canonicalID);
+
+  FSTQueryData *data1 = [self queryDataWithQuery:q1 targetID:1 version:1];
+  [self addQueryData:data1];
+
+  // Using the other query should not return the query cache entry despite equal canonicalIDs.
+  XCTAssertNil([self.queryCache queryDataForQuery:q2]);
+  XCTAssertEqualObjects([self.queryCache queryDataForQuery:q1], data1);
+
+  FSTQueryData *data2 = [self queryDataWithQuery:q2 targetID:2 version:1];
+  [self addQueryData:data2];
+
+  XCTAssertEqualObjects([self.queryCache queryDataForQuery:q1], data1);
+  XCTAssertEqualObjects([self.queryCache queryDataForQuery:q2], data2);
+
+  [self removeQueryData:data1];
+  XCTAssertNil([self.queryCache queryDataForQuery:q1]);
+  XCTAssertEqualObjects([self.queryCache queryDataForQuery:q2], data2);
+
+  [self removeQueryData:data2];
+  XCTAssertNil([self.queryCache queryDataForQuery:q1]);
+  XCTAssertNil([self.queryCache queryDataForQuery:q2]);
+}
+
+- (void)testSetQueryToNewValue {
+  if ([self isTestBaseClass]) return;
+
+  FSTQueryData *queryData1 = [self queryDataWithQuery:_queryRooms targetID:1 version:1];
+  [self addQueryData:queryData1];
+
+  FSTQueryData *queryData2 = [self queryDataWithQuery:_queryRooms targetID:1 version:2];
+  [self addQueryData:queryData2];
+
+  FSTQueryData *result = [self.queryCache queryDataForQuery:_queryRooms];
+  XCTAssertNotEqualObjects(queryData2.resumeToken, queryData1.resumeToken);
+  XCTAssertNotEqualObjects(queryData2.snapshotVersion, queryData1.snapshotVersion);
+  XCTAssertEqualObjects(result.resumeToken, queryData2.resumeToken);
+  XCTAssertEqualObjects(result.snapshotVersion, queryData2.snapshotVersion);
+}
+
+- (void)testRemoveQuery {
+  if ([self isTestBaseClass]) return;
+
+  FSTQueryData *queryData1 = [self queryDataWithQuery:_queryRooms targetID:1 version:1];
+  [self addQueryData:queryData1];
+
+  [self removeQueryData:queryData1];
+
+  FSTQueryData *result = [self.queryCache queryDataForQuery:_queryRooms];
+  XCTAssertNil(result);
+}
+
+- (void)testRemoveNonExistentQuery {
+  if ([self isTestBaseClass]) return;
+
+  FSTQueryData *queryData = [self queryDataWithQuery:_queryRooms targetID:1 version:1];
+
+  // no-op, but make sure it doesn't throw.
+  XCTAssertNoThrow([self removeQueryData:queryData]);
+}
+
+- (void)testRemoveQueryRemovesMatchingKeysToo {
+  if ([self isTestBaseClass]) return;
+
+  FSTQueryData *rooms = [self queryDataWithQuery:_queryRooms targetID:1 version:1];
+  [self addQueryData:rooms];
+
+  FSTDocumentKey *key1 = [FSTDocumentKey keyWithPathString:@"rooms/foo"];
+  FSTDocumentKey *key2 = [FSTDocumentKey keyWithPathString:@"rooms/bar"];
+  [self addMatchingKey:key1 forTargetID:rooms.targetID];
+  [self addMatchingKey:key2 forTargetID:rooms.targetID];
+
+  XCTAssertTrue([self.queryCache containsKey:key1]);
+  XCTAssertTrue([self.queryCache containsKey:key2]);
+
+  [self removeQueryData:rooms];
+  XCTAssertFalse([self.queryCache containsKey:key1]);
+  XCTAssertFalse([self.queryCache containsKey:key2]);
+}
+
+- (void)testAddOrRemoveMatchingKeys {
+  if ([self isTestBaseClass]) return;
+
+  FSTDocumentKey *key = [FSTDocumentKey keyWithPathString:@"foo/bar"];
+
+  XCTAssertFalse([self.queryCache containsKey:key]);
+
+  [self addMatchingKey:key forTargetID:1];
+  XCTAssertTrue([self.queryCache containsKey:key]);
+
+  [self addMatchingKey:key forTargetID:2];
+  XCTAssertTrue([self.queryCache containsKey:key]);
+
+  [self removeMatchingKey:key forTargetID:1];
+  XCTAssertTrue([self.queryCache containsKey:key]);
+
+  [self removeMatchingKey:key forTargetID:2];
+  XCTAssertFalse([self.queryCache containsKey:key]);
+}
+
+- (void)testRemoveMatchingKeysForTargetID {
+  if ([self isTestBaseClass]) return;
+
+  FSTDocumentKey *key1 = [FSTDocumentKey keyWithPathString:@"foo/bar"];
+  FSTDocumentKey *key2 = [FSTDocumentKey keyWithPathString:@"foo/baz"];
+  FSTDocumentKey *key3 = [FSTDocumentKey keyWithPathString:@"foo/blah"];
+
+  [self addMatchingKey:key1 forTargetID:1];
+  [self addMatchingKey:key2 forTargetID:1];
+  [self addMatchingKey:key3 forTargetID:2];
+  XCTAssertTrue([self.queryCache containsKey:key1]);
+  XCTAssertTrue([self.queryCache containsKey:key2]);
+  XCTAssertTrue([self.queryCache containsKey:key3]);
+
+  [self removeMatchingKeysForTargetID:1];
+  XCTAssertFalse([self.queryCache containsKey:key1]);
+  XCTAssertFalse([self.queryCache containsKey:key2]);
+  XCTAssertTrue([self.queryCache containsKey:key3]);
+
+  [self removeMatchingKeysForTargetID:2];
+  XCTAssertFalse([self.queryCache containsKey:key1]);
+  XCTAssertFalse([self.queryCache containsKey:key2]);
+  XCTAssertFalse([self.queryCache containsKey:key3]);
+}
+
+- (void)testRemoveEmitsGarbageEvents {
+  if ([self isTestBaseClass]) return;
+
+  FSTEagerGarbageCollector *garbageCollector = [[FSTEagerGarbageCollector alloc] init];
+  [garbageCollector addGarbageSource:self.queryCache];
+  FSTAssertEqualSets([garbageCollector collectGarbage], @[]);
+
+  FSTQueryData *rooms = [self queryDataWithQuery:FSTTestQuery(@"rooms") targetID:1 version:1];
+  FSTDocumentKey *room1 = [FSTDocumentKey keyWithPathString:@"rooms/bar"];
+  FSTDocumentKey *room2 = [FSTDocumentKey keyWithPathString:@"rooms/foo"];
+  [self addQueryData:rooms];
+  [self addMatchingKey:room1 forTargetID:rooms.targetID];
+  [self addMatchingKey:room2 forTargetID:rooms.targetID];
+
+  FSTQueryData *halls = [self queryDataWithQuery:FSTTestQuery(@"halls") targetID:2 version:1];
+  FSTDocumentKey *hall1 = [FSTDocumentKey keyWithPathString:@"halls/bar"];
+  FSTDocumentKey *hall2 = [FSTDocumentKey keyWithPathString:@"halls/foo"];
+  [self addQueryData:halls];
+  [self addMatchingKey:hall1 forTargetID:halls.targetID];
+  [self addMatchingKey:hall2 forTargetID:halls.targetID];
+
+  FSTAssertEqualSets([garbageCollector collectGarbage], @[]);
+
+  [self removeMatchingKey:room1 forTargetID:rooms.targetID];
+  FSTAssertEqualSets([garbageCollector collectGarbage], @[ room1 ]);
+
+  [self removeQueryData:rooms];
+  FSTAssertEqualSets([garbageCollector collectGarbage], @[ room2 ]);
+
+  [self removeMatchingKeysForTargetID:halls.targetID];
+  FSTAssertEqualSets([garbageCollector collectGarbage], (@[ hall1, hall2 ]));
+}
+
+- (void)testMatchingKeysForTargetID {
+  if ([self isTestBaseClass]) return;
+
+  FSTDocumentKey *key1 = [FSTDocumentKey keyWithPathString:@"foo/bar"];
+  FSTDocumentKey *key2 = [FSTDocumentKey keyWithPathString:@"foo/baz"];
+  FSTDocumentKey *key3 = [FSTDocumentKey keyWithPathString:@"foo/blah"];
+
+  [self addMatchingKey:key1 forTargetID:1];
+  [self addMatchingKey:key2 forTargetID:1];
+  [self addMatchingKey:key3 forTargetID:2];
+
+  FSTAssertEqualSets([self.queryCache matchingKeysForTargetID:1], (@[ key1, key2 ]));
+  FSTAssertEqualSets([self.queryCache matchingKeysForTargetID:2], @[ key3 ]);
+
+  [self addMatchingKey:key1 forTargetID:2];
+  FSTAssertEqualSets([self.queryCache matchingKeysForTargetID:1], (@[ key1, key2 ]));
+  FSTAssertEqualSets([self.queryCache matchingKeysForTargetID:2], (@[ key1, key3 ]));
+}
+
+- (void)testHighestTargetID {
+  if ([self isTestBaseClass]) return;
+
+  XCTAssertEqual([self.queryCache highestTargetID], 0);
+
+  FSTQueryData *query1 = [[FSTQueryData alloc] initWithQuery:FSTTestQuery(@"rooms")
+                                                    targetID:1
+                                                     purpose:FSTQueryPurposeListen];
+  FSTDocumentKey *key1 = [FSTDocumentKey keyWithPathString:@"rooms/bar"];
+  FSTDocumentKey *key2 = [FSTDocumentKey keyWithPathString:@"rooms/foo"];
+  [self addQueryData:query1];
+  [self addMatchingKey:key1 forTargetID:1];
+  [self addMatchingKey:key2 forTargetID:1];
+
+  FSTQueryData *query2 = [[FSTQueryData alloc] initWithQuery:FSTTestQuery(@"halls")
+                                                    targetID:2
+                                                     purpose:FSTQueryPurposeListen];
+  FSTDocumentKey *key3 = [FSTDocumentKey keyWithPathString:@"halls/foo"];
+  [self addQueryData:query2];
+  [self addMatchingKey:key3 forTargetID:2];
+  XCTAssertEqual([self.queryCache highestTargetID], 2);
+
+  // TargetIDs never come down.
+  [self removeQueryData:query2];
+  XCTAssertEqual([self.queryCache highestTargetID], 2);
+
+  // A query with an empty result set still counts.
+  FSTQueryData *query3 = [[FSTQueryData alloc] initWithQuery:FSTTestQuery(@"garages")
+                                                    targetID:42
+                                                     purpose:FSTQueryPurposeListen];
+  [self addQueryData:query3];
+  XCTAssertEqual([self.queryCache highestTargetID], 42);
+
+  [self removeQueryData:query1];
+  XCTAssertEqual([self.queryCache highestTargetID], 42);
+
+  [self removeQueryData:query3];
+  XCTAssertEqual([self.queryCache highestTargetID], 42);
+
+  // Verify that the highestTargetID even survives restarts.
+  [self.queryCache shutdown];
+  self.queryCache = [self.persistence queryCache];
+  [self.queryCache start];
+  XCTAssertEqual([self.queryCache highestTargetID], 42);
+}
+
+- (void)testLastRemoteSnapshotVersion {
+  if ([self isTestBaseClass]) return;
+
+  XCTAssertEqualObjects([self.queryCache lastRemoteSnapshotVersion],
+                        [FSTSnapshotVersion noVersion]);
+
+  // Can set the snapshot version.
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"setLastRemoteSnapshotVersion"];
+  [self.queryCache setLastRemoteSnapshotVersion:FSTTestVersion(42) group:group];
+  [self.persistence commitGroup:group];
+  XCTAssertEqualObjects([self.queryCache lastRemoteSnapshotVersion], FSTTestVersion(42));
+
+  // Snapshot version persists restarts.
+  self.queryCache = [self.persistence queryCache];
+  [self.queryCache start];
+  XCTAssertEqualObjects([self.queryCache lastRemoteSnapshotVersion], FSTTestVersion(42));
+}
+
+#pragma mark - Helpers
+
+/**
+ * Creates a new FSTQueryData object from the given parameters, synthesizing a resume token from
+ * the snapshot version.
+ */
+- (FSTQueryData *)queryDataWithQuery:(FSTQuery *)query
+                            targetID:(FSTTargetID)targetID
+                             version:(FSTTestSnapshotVersion)version {
+  NSData *resumeToken = FSTTestResumeTokenFromSnapshotVersion(version);
+  return [[FSTQueryData alloc] initWithQuery:query
+                                    targetID:targetID
+                                     purpose:FSTQueryPurposeListen
+                             snapshotVersion:FSTTestVersion(version)
+                                 resumeToken:resumeToken];
+}
+
+/** Adds the given query data to the queryCache under test, committing immediately. */
+- (void)addQueryData:(FSTQueryData *)queryData {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"addQueryData"];
+  [self.queryCache addQueryData:queryData group:group];
+  [self.persistence commitGroup:group];
+}
+
+/** Removes the given query data from the queryCache under test, committing immediately. */
+- (void)removeQueryData:(FSTQueryData *)queryData {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"removeQueryData"];
+  [self.queryCache removeQueryData:queryData group:group];
+  [self.persistence commitGroup:group];
+}
+
+- (void)addMatchingKey:(FSTDocumentKey *)key forTargetID:(FSTTargetID)targetID {
+  FSTDocumentKeySet *keys = [FSTDocumentKeySet keySet];
+  keys = [keys setByAddingObject:key];
+
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"addMatchingKeys"];
+  [self.queryCache addMatchingKeys:keys forTargetID:targetID group:group];
+  [self.persistence commitGroup:group];
+}
+
+- (void)removeMatchingKey:(FSTDocumentKey *)key forTargetID:(FSTTargetID)targetID {
+  FSTDocumentKeySet *keys = [FSTDocumentKeySet keySet];
+  keys = [keys setByAddingObject:key];
+
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"removeMatchingKeys"];
+  [self.queryCache removeMatchingKeys:keys forTargetID:targetID group:group];
+  [self.persistence commitGroup:group];
+}
+
+- (void)removeMatchingKeysForTargetID:(FSTTargetID)targetID {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"removeMatchingKeysForTargetID"];
+  [self.queryCache removeMatchingKeysForTargetID:targetID group:group];
+  [self.persistence commitGroup:group];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTReferenceSetTests.m b/Firestore/Example/Tests/Local/FSTReferenceSetTests.m
new file mode 100644
index 0000000..a8c783a
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTReferenceSetTests.m
@@ -0,0 +1,84 @@
+/*
+ * Copyright 2017 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 "Local/FSTReferenceSet.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Model/FSTDocumentKey.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTReferenceSetTests : XCTestCase
+@end
+
+@implementation FSTReferenceSetTests
+
+- (void)testAddOrRemoveReferences {
+  FSTDocumentKey *key = [FSTDocumentKey keyWithPathString:@"foo/bar"];
+
+  FSTReferenceSet *referenceSet = [[FSTReferenceSet alloc] init];
+  XCTAssertTrue([referenceSet isEmpty]);
+  XCTAssertFalse([referenceSet containsKey:key]);
+
+  [referenceSet addReferenceToKey:key forID:1];
+  XCTAssertTrue([referenceSet containsKey:key]);
+  XCTAssertFalse([referenceSet isEmpty]);
+
+  [referenceSet addReferenceToKey:key forID:2];
+  XCTAssertTrue([referenceSet containsKey:key]);
+
+  [referenceSet removeReferenceToKey:key forID:1];
+  XCTAssertTrue([referenceSet containsKey:key]);
+
+  [referenceSet removeReferenceToKey:key forID:3];
+  XCTAssertTrue([referenceSet containsKey:key]);
+
+  [referenceSet removeReferenceToKey:key forID:2];
+  XCTAssertFalse([referenceSet containsKey:key]);
+  XCTAssertTrue([referenceSet isEmpty]);
+}
+
+- (void)testRemoveAllReferencesForTargetID {
+  FSTDocumentKey *key1 = [FSTDocumentKey keyWithPathString:@"foo/bar"];
+  FSTDocumentKey *key2 = [FSTDocumentKey keyWithPathString:@"foo/baz"];
+  FSTDocumentKey *key3 = [FSTDocumentKey keyWithPathString:@"foo/blah"];
+  FSTReferenceSet *referenceSet = [[FSTReferenceSet alloc] init];
+
+  [referenceSet addReferenceToKey:key1 forID:1];
+  [referenceSet addReferenceToKey:key2 forID:1];
+  [referenceSet addReferenceToKey:key3 forID:2];
+  XCTAssertFalse([referenceSet isEmpty]);
+  XCTAssertTrue([referenceSet containsKey:key1]);
+  XCTAssertTrue([referenceSet containsKey:key2]);
+  XCTAssertTrue([referenceSet containsKey:key3]);
+
+  [referenceSet removeReferencesForID:1];
+  XCTAssertFalse([referenceSet isEmpty]);
+  XCTAssertFalse([referenceSet containsKey:key1]);
+  XCTAssertFalse([referenceSet containsKey:key2]);
+  XCTAssertTrue([referenceSet containsKey:key3]);
+
+  [referenceSet removeReferencesForID:2];
+  XCTAssertTrue([referenceSet isEmpty]);
+  XCTAssertFalse([referenceSet containsKey:key1]);
+  XCTAssertFalse([referenceSet containsKey:key2]);
+  XCTAssertFalse([referenceSet containsKey:key3]);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTRemoteDocumentCacheTests.h b/Firestore/Example/Tests/Local/FSTRemoteDocumentCacheTests.h
new file mode 100644
index 0000000..fa2a857
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTRemoteDocumentCacheTests.h
@@ -0,0 +1,39 @@
+/*
+ * Copyright 2017 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 "Local/FSTRemoteDocumentCache.h"
+
+#import <XCTest/XCTest.h>
+
+@protocol FSTPersistence;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * These are tests for any implementation of the FSTRemoteDocumentCache protocol.
+ *
+ * To test a specific implementation of FSTRemoteDocumentCache:
+ *
+ * + Subclass FSTRemoteDocumentCacheTests
+ * + override -setUp, assigning to remoteDocumentCache and persistence
+ * + override -tearDown, cleaning up remoteDocumentCache and persistence
+ */
+@interface FSTRemoteDocumentCacheTests : XCTestCase
+@property(nonatomic, strong, nullable) id<FSTRemoteDocumentCache> remoteDocumentCache;
+@property(nonatomic, strong, nullable) id<FSTPersistence> persistence;
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTRemoteDocumentCacheTests.m b/Firestore/Example/Tests/Local/FSTRemoteDocumentCacheTests.m
new file mode 100644
index 0000000..a875934
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTRemoteDocumentCacheTests.m
@@ -0,0 +1,151 @@
+/*
+ * Copyright 2017 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 "FSTRemoteDocumentCacheTests.h"
+
+#import "Core/FSTQuery.h"
+#import "Local/FSTPersistence.h"
+#import "Local/FSTWriteGroup.h"
+#import "Model/FSTDocument.h"
+#import "Model/FSTDocumentKey.h"
+#import "Model/FSTDocumentSet.h"
+
+#import "FSTHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+static NSString *const kDocPath = @"a/b";
+static NSString *const kLongDocPath = @"a/b/c/d/e/f";
+static const int kVersion = 42;
+
+@implementation FSTRemoteDocumentCacheTests {
+  NSDictionary<NSString *, id> *_kDocData;
+}
+
+- (void)setUp {
+  [super setUp];
+
+  // essentially a constant, but can't be a compile-time one.
+  _kDocData = @{ @"a" : @1, @"b" : @2 };
+}
+
+- (void)testReadDocumentNotInCache {
+  if (!self.remoteDocumentCache) return;
+
+  XCTAssertNil([self readEntryAtPath:kDocPath]);
+}
+
+// Helper for next two tests.
+- (void)setAndReadADocumentAtPath:(NSString *)path {
+  FSTDocument *written = [self setTestDocumentAtPath:path];
+  FSTMaybeDocument *read = [self readEntryAtPath:path];
+  XCTAssertEqualObjects(read, written);
+}
+
+- (void)testSetAndReadADocument {
+  if (!self.remoteDocumentCache) return;
+
+  [self setAndReadADocumentAtPath:kDocPath];
+}
+
+- (void)testSetAndReadADocumentAtDeepPath {
+  if (!self.remoteDocumentCache) return;
+
+  [self setAndReadADocumentAtPath:kLongDocPath];
+}
+
+- (void)testSetAndReadDeletedDocument {
+  if (!self.remoteDocumentCache) return;
+
+  FSTDeletedDocument *deletedDoc = FSTTestDeletedDoc(kDocPath, kVersion);
+  [self addEntry:deletedDoc];
+
+  XCTAssertEqualObjects([self readEntryAtPath:kDocPath], deletedDoc);
+}
+
+- (void)testSetDocumentToNewValue {
+  if (!self.remoteDocumentCache) return;
+
+  [self setTestDocumentAtPath:kDocPath];
+  FSTDocument *newDoc = FSTTestDoc(kDocPath, kVersion, @{ @"data" : @2 }, NO);
+  [self addEntry:newDoc];
+  XCTAssertEqualObjects([self readEntryAtPath:kDocPath], newDoc);
+}
+
+- (void)testRemoveDocument {
+  if (!self.remoteDocumentCache) return;
+
+  [self setTestDocumentAtPath:kDocPath];
+  [self removeEntryAtPath:kDocPath];
+
+  XCTAssertNil([self readEntryAtPath:kDocPath]);
+}
+
+- (void)testRemoveNonExistentDocument {
+  if (!self.remoteDocumentCache) return;
+
+  // no-op, but make sure it doesn't throw.
+  XCTAssertNoThrow([self removeEntryAtPath:kDocPath]);
+}
+
+// TODO(mikelehen): Write more elaborate tests once we have more elaborate implementations.
+- (void)testDocumentsMatchingQuery {
+  if (!self.remoteDocumentCache) return;
+
+  [self setTestDocumentAtPath:@"a/1"];
+  [self setTestDocumentAtPath:@"b/1"];
+  [self setTestDocumentAtPath:@"b/2"];
+  [self setTestDocumentAtPath:@"c/1"];
+
+  FSTQuery *query = [FSTQuery queryWithPath:FSTTestPath(@"b")];
+  FSTDocumentDictionary *results = [self.remoteDocumentCache documentsMatchingQuery:query];
+  NSArray *expected =
+      @[ FSTTestDoc(@"b/1", kVersion, _kDocData, NO), FSTTestDoc(@"b/2", kVersion, _kDocData, NO) ];
+  for (FSTDocument *doc in expected) {
+    XCTAssertEqualObjects([results objectForKey:doc.key], doc);
+  }
+
+  // TODO(mikelehen): Perhaps guard against extra documents in the result set once our
+  // implementations are smarter.
+}
+
+#pragma mark - Helpers
+
+- (FSTDocument *)setTestDocumentAtPath:(NSString *)path {
+  FSTDocument *doc = FSTTestDoc(path, kVersion, _kDocData, NO);
+  [self addEntry:doc];
+  return doc;
+}
+
+- (void)addEntry:(FSTMaybeDocument *)maybeDoc {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"addEntry"];
+  [self.remoteDocumentCache addEntry:maybeDoc group:group];
+  [self.persistence commitGroup:group];
+}
+
+- (FSTMaybeDocument *_Nullable)readEntryAtPath:(NSString *)path {
+  return [self.remoteDocumentCache entryForKey:FSTTestDocKey(path)];
+}
+
+- (void)removeEntryAtPath:(NSString *)path {
+  FSTWriteGroup *group = [self.persistence startGroupWithAction:@"removeEntryAtPath"];
+  [self.remoteDocumentCache removeEntryForKey:FSTTestDocKey(path) group:group];
+  [self.persistence commitGroup:group];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTRemoteDocumentChangeBufferTests.m b/Firestore/Example/Tests/Local/FSTRemoteDocumentChangeBufferTests.m
new file mode 100644
index 0000000..ebf7713
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTRemoteDocumentChangeBufferTests.m
@@ -0,0 +1,113 @@
+/*
+ * Copyright 2017 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 "Local/FSTRemoteDocumentChangeBuffer.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Local/FSTLevelDB.h"
+#import "Local/FSTRemoteDocumentCache.h"
+#import "Model/FSTDocument.h"
+
+#import "FSTHelpers.h"
+#import "FSTPersistenceTestHelpers.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTRemoteDocumentChangeBufferTests : XCTestCase
+@end
+
+@implementation FSTRemoteDocumentChangeBufferTests {
+  FSTLevelDB *_db;
+  id<FSTRemoteDocumentCache> _remoteDocumentCache;
+  FSTRemoteDocumentChangeBuffer *_remoteDocumentBuffer;
+
+  FSTMaybeDocument *_kInitialADoc;
+  FSTMaybeDocument *_kInitialBDoc;
+}
+
+- (void)setUp {
+  [super setUp];
+
+  _db = [FSTPersistenceTestHelpers levelDBPersistence];
+  _remoteDocumentCache = [_db remoteDocumentCache];
+
+  // Add a couple initial items to the cache.
+  FSTWriteGroup *group = [_db startGroupWithAction:@"Add initial docs."];
+  _kInitialADoc = FSTTestDoc(@"coll/a", 42, @{@"test" : @"data"}, NO);
+  [_remoteDocumentCache addEntry:_kInitialADoc group:group];
+
+  _kInitialBDoc =
+      [FSTDeletedDocument documentWithKey:FSTTestDocKey(@"coll/b") version:FSTTestVersion(314)];
+  [_remoteDocumentCache addEntry:_kInitialBDoc group:group];
+  [_db commitGroup:group];
+
+  _remoteDocumentBuffer =
+      [FSTRemoteDocumentChangeBuffer changeBufferWithCache:_remoteDocumentCache];
+}
+
+- (void)tearDown {
+  _remoteDocumentBuffer = nil;
+  _remoteDocumentCache = nil;
+  _db = nil;
+
+  [super tearDown];
+}
+
+- (void)testReadUnchangedEntry {
+  XCTAssertEqualObjects([_remoteDocumentBuffer entryForKey:FSTTestDocKey(@"coll/a")],
+                        _kInitialADoc);
+}
+
+- (void)testAddEntryAndReadItBack {
+  FSTMaybeDocument *newADoc = FSTTestDoc(@"coll/a", 43, @{@"new" : @"data"}, NO);
+  [_remoteDocumentBuffer addEntry:newADoc];
+  XCTAssertEqualObjects([_remoteDocumentBuffer entryForKey:FSTTestDocKey(@"coll/a")], newADoc);
+
+  // B should still be unchanged.
+  XCTAssertEqualObjects([_remoteDocumentBuffer entryForKey:FSTTestDocKey(@"coll/b")],
+                        _kInitialBDoc);
+}
+
+- (void)testApplyChanges {
+  FSTMaybeDocument *newADoc = FSTTestDoc(@"coll/a", 43, @{@"new" : @"data"}, NO);
+  [_remoteDocumentBuffer addEntry:newADoc];
+  XCTAssertEqualObjects([_remoteDocumentBuffer entryForKey:FSTTestDocKey(@"coll/a")], newADoc);
+
+  // Reading directly against the cache should still yield the old result.
+  XCTAssertEqualObjects([_remoteDocumentCache entryForKey:FSTTestDocKey(@"coll/a")], _kInitialADoc);
+
+  FSTWriteGroup *group = [_db startGroupWithAction:@"Apply changes"];
+  [_remoteDocumentBuffer applyToWriteGroup:group];
+  [_db commitGroup:group];
+
+  // Reading against the cache should now yield the new result.
+  XCTAssertEqualObjects([_remoteDocumentCache entryForKey:FSTTestDocKey(@"coll/a")], newADoc);
+}
+
+- (void)testMethodsThrowAfterApply {
+  FSTWriteGroup *group = [_db startGroupWithAction:@"Apply changes"];
+  [_remoteDocumentBuffer applyToWriteGroup:group];
+  [_db commitGroup:group];
+
+  XCTAssertThrows([_remoteDocumentBuffer entryForKey:FSTTestDocKey(@"coll/a")]);
+  XCTAssertThrows([_remoteDocumentBuffer addEntry:_kInitialADoc]);
+  XCTAssertThrows([_remoteDocumentBuffer applyToWriteGroup:group]);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Example/Tests/Local/FSTWriteGroupTests.mm b/Firestore/Example/Tests/Local/FSTWriteGroupTests.mm
new file mode 100644
index 0000000..1cd2feb
--- /dev/null
+++ b/Firestore/Example/Tests/Local/FSTWriteGroupTests.mm
@@ -0,0 +1,121 @@
+/*
+ * Copyright 2017 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 "Local/FSTWriteGroup.h"
+
+#import <XCTest/XCTest.h>
+#include <leveldb/db.h>
+
+#import "Protos/objc/firestore/local/Mutation.pbobjc.h"
+#import "Local/FSTLevelDB.h"
+#import "Local/FSTLevelDBKey.h"
+
+#import "FSTPersistenceTestHelpers.h"
+
+using leveldb::ReadOptions;
+using leveldb::Status;
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTWriteGroupTests : XCTestCase
+@end
+
+@implementation FSTWriteGroupTests {
+  FSTLevelDB *_db;
+}
+
+- (void)setUp {
+  [super setUp];
+
+  _db = [FSTPersistenceTestHelpers levelDBPersistence];
+}
+
+- (void)tearDown {
+  _db = nil;
+
+  [super tearDown];
+}
+
+- (void)testCommit {
+  std::string key = [FSTLevelDBMutationKey keyWithUserID:"user1" batchID:42];
+  FSTPBWriteBatch *message = [FSTPBWriteBatch message];
+  message.batchId = 42;
+
+  // This is a test that shows that committing an empty group does not fail. There are no side
+  // effects to verify though.
+  FSTWriteGroup *group = [_db startGroupWithAction:@"Empty commit"];
+  XCTAssertNoThrow([_db commitGroup:group]);
+
+  group = [_db startGroupWithAction:@"Put"];
+  [group setMessage:message forKey:key];
+
+  std::string value;
+  Status status = _db.ptr->Get(ReadOptions(), key, &value);
+  XCTAssertTrue(status.IsNotFound());
+
+  [_db commitGroup:group];
+  status = _db.ptr->Get(ReadOptions(), key, &value);
+  XCTAssertTrue(status.ok());
+
+  group = [_db startGroupWithAction:@"Delete"];
+  [group removeMessageForKey:key];
+  status = _db.ptr->Get(ReadOptions(), key, &value);
+  XCTAssertTrue(status.ok());
+
+  [_db commitGroup:group];
+  status = _db.ptr->Get(ReadOptions(), key, &value);
+  XCTAssertTrue(status.IsNotFound());
+}
+
+- (void)testDescription {
+  std::string key = [FSTLevelDBMutationKey keyWithUserID:"user1" batchID:42];
+  FSTPBWriteBatch *message = [FSTPBWriteBatch message];
+  message.batchId = 42;
+
+  FSTWriteGroup *group = [FSTWriteGroup groupWithAction:@"Action"];
+  XCTAssertEqualObjects([group description], @"<FSTWriteGroup for Action: 0 changes (0 bytes):>");
+
+  [group setMessage:message forKey:key];
+  XCTAssertEqualObjects([group description],
+                        @"<FSTWriteGroup for Action: 1 changes (2 bytes):\n"
+                         "  - Put [mutation: userID=user1 batchID=42] (2 bytes)>");
+
+  [group removeMessageForKey:key];
+  XCTAssertEqualObjects([group description],
+                        @"<FSTWriteGroup for Action: 2 changes (2 bytes):\n"
+                         "  - Put [mutation: userID=user1 batchID=42] (2 bytes)\n"
+                         "  - Delete [mutation: userID=user1 batchID=42]>");
+}
+
+- (void)testCommittingWrongGroupThrows {
+  // If you don't create the group through persistence, it should throw.
+  FSTWriteGroup *group = [FSTWriteGroup groupWithAction:@"group"];
+  XCTAssertThrows([_db commitGroup:group]);
+}
+
+- (void)testCommittingTwiceThrows {
+  FSTWriteGroup *group = [_db startGroupWithAction:@"group"];
+  [_db commitGroup:group];
+  XCTAssertThrows([_db commitGroup:group]);
+}
+
+- (void)testNestingGroupsThrows {
+  [_db startGroupWithAction:@"group1"];
+  XCTAssertThrows([_db startGroupWithAction:@"group2"]);
+}
+@end
+
+NS_ASSUME_NONNULL_END