Release 4.3.0 (#327)

Initial release of Firestore at 0.8.0
Bump FirebaseCommunity to 0.1.3

23 files changed, 4391 insertions, 0 deletions

diff --git a/Firestore/Source/Core/FSTDatabaseInfo.h b/Firestore/Source/Core/FSTDatabaseInfo.h
new file mode 100644
index 0000000..fae884f
--- /dev/null
+++ b/Firestore/Source/Core/FSTDatabaseInfo.h
@@ -0,0 +1,55 @@
+/*
+ * 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 FSTDatabaseID;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/** FSTDatabaseInfo contains data about the database. */
+@interface FSTDatabaseInfo : NSObject
+
+/**
+ * Creates and returns a new FSTDatabaseInfo.
+ *
+ * @param databaseID The project/database to use.
+ * @param persistenceKey A unique identifier for this Firestore's local storage. Usually derived
+ *     from -[FIRApp appName].
+ * @param host The hostname of the datastore backend.
+ * @param sslEnabled Whether to use SSL when connecting.
+ * @return A new instance of FSTDatabaseInfo.
+ */
++ (instancetype)databaseInfoWithDatabaseID:(FSTDatabaseID *)databaseID
+                            persistenceKey:(NSString *)persistenceKey
+                                      host:(NSString *)host
+                                sslEnabled:(BOOL)sslEnabled;
+
+/** The database info. */
+@property(nonatomic, strong, readonly) FSTDatabaseID *databaseID;
+
+/** The application name, taken from FIRApp. */
+@property(nonatomic, copy, readonly) NSString *persistenceKey;
+
+/** The hostname of the backend. */
+@property(nonatomic, copy, readonly) NSString *host;
+
+/** Whether to use SSL when connecting. */
+@property(nonatomic, readonly, getter=isSSLEnabled) BOOL sslEnabled;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTDatabaseInfo.m b/Firestore/Source/Core/FSTDatabaseInfo.m
new file mode 100644
index 0000000..d2cd0ed
--- /dev/null
+++ b/Firestore/Source/Core/FSTDatabaseInfo.m
@@ -0,0 +1,70 @@
+/*
+ * 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 "FSTDatabaseInfo.h"
+
+#import "FSTDatabaseID.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTDatabaseInfo
+
+@implementation FSTDatabaseInfo
+
+#pragma mark - Constructors
+
++ (instancetype)databaseInfoWithDatabaseID:(FSTDatabaseID *)databaseID
+                            persistenceKey:(NSString *)persistenceKey
+                                      host:(NSString *)host
+                                sslEnabled:(BOOL)sslEnabled {
+  return [[FSTDatabaseInfo alloc] initWithDatabaseID:databaseID
+                                      persistenceKey:persistenceKey
+                                                host:host
+                                          sslEnabled:sslEnabled];
+}
+
+/**
+ * Designated initializer.
+ *
+ * @param databaseID The database in the datastore.
+ * @param persistenceKey A unique identifier for this Firestore's local storage. Usually derived
+ *     from -[FIRApp appName].
+ * @param host The Firestore server hostname.
+ * @param sslEnabled Whether to use SSL when connecting.
+ */
+- (instancetype)initWithDatabaseID:(FSTDatabaseID *)databaseID
+                    persistenceKey:(NSString *)persistenceKey
+                              host:(NSString *)host
+                        sslEnabled:(BOOL)sslEnabled {
+  if (self = [super init]) {
+    _databaseID = databaseID;
+    _persistenceKey = [persistenceKey copy];
+    _host = [host copy];
+    _sslEnabled = sslEnabled;
+  }
+  return self;
+}
+
+#pragma mark - NSObject methods
+
+- (NSString *)description {
+  return [NSString
+      stringWithFormat:@"<FSTDatabaseInfo: databaseID:%@ host:%@>", self.databaseID, self.host];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTEventManager.h b/Firestore/Source/Core/FSTEventManager.h
new file mode 100644
index 0000000..43ada66
--- /dev/null
+++ b/Firestore/Source/Core/FSTEventManager.h
@@ -0,0 +1,88 @@
+/*
+ * 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>
+
+#import "FSTRemoteStore.h"
+#import "FSTTypes.h"
+#import "FSTViewSnapshot.h"
+
+@class FSTQuery;
+@class FSTSyncEngine;
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTListenOptions
+
+@interface FSTListenOptions : NSObject
+
++ (instancetype)defaultOptions;
+
+- (instancetype)initWithIncludeQueryMetadataChanges:(BOOL)includeQueryMetadataChanges
+                     includeDocumentMetadataChanges:(BOOL)includeDocumentMetadataChanges
+                              waitForSyncWhenOnline:(BOOL)waitForSyncWhenOnline
+    NS_DESIGNATED_INITIALIZER;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+@property(nonatomic, assign, readonly) BOOL includeQueryMetadataChanges;
+
+@property(nonatomic, assign, readonly) BOOL includeDocumentMetadataChanges;
+
+@property(nonatomic, assign, readonly) BOOL waitForSyncWhenOnline;
+
+@end
+
+#pragma mark - FSTQueryListener
+
+/**
+ * FSTQueryListener takes a series of internal view snapshots and determines when to raise
+ * user-facing events.
+ */
+@interface FSTQueryListener : NSObject
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                      options:(FSTListenOptions *)options
+          viewSnapshotHandler:(FSTViewSnapshotHandler)viewSnapshotHandler NS_DESIGNATED_INITIALIZER;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+- (void)queryDidChangeViewSnapshot:(FSTViewSnapshot *)snapshot;
+- (void)queryDidError:(NSError *)error;
+- (void)clientDidChangeOnlineState:(FSTOnlineState)onlineState;
+
+@property(nonatomic, strong, readonly) FSTQuery *query;
+
+@end
+
+#pragma mark - FSTEventManager
+
+/**
+ * EventManager is responsible for mapping queries to query event emitters. It handles "fan-out."
+ * (Identical queries will re-use the same watch on the backend.)
+ */
+@interface FSTEventManager : NSObject <FSTOnlineStateDelegate>
+
++ (instancetype)eventManagerWithSyncEngine:(FSTSyncEngine *)syncEngine;
+
+- (instancetype)init __attribute__((unavailable("Use static constructor method.")));
+
+- (FSTTargetID)addListener:(FSTQueryListener *)listener;
+- (void)removeListener:(FSTQueryListener *)listener;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTEventManager.m b/Firestore/Source/Core/FSTEventManager.m
new file mode 100644
index 0000000..17a0546
--- /dev/null
+++ b/Firestore/Source/Core/FSTEventManager.m
@@ -0,0 +1,335 @@
+/*
+ * 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 "FSTEventManager.h"
+
+#import "FSTAssert.h"
+#import "FSTDocumentSet.h"
+#import "FSTQuery.h"
+#import "FSTSyncEngine.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTListenOptions
+
+@implementation FSTListenOptions
+
++ (instancetype)defaultOptions {
+  static FSTListenOptions *defaultOptions;
+  static dispatch_once_t onceToken;
+  dispatch_once(&onceToken, ^{
+    defaultOptions = [[FSTListenOptions alloc] initWithIncludeQueryMetadataChanges:NO
+                                                    includeDocumentMetadataChanges:NO
+                                                             waitForSyncWhenOnline:NO];
+  });
+  return defaultOptions;
+}
+
+- (instancetype)initWithIncludeQueryMetadataChanges:(BOOL)includeQueryMetadataChanges
+                     includeDocumentMetadataChanges:(BOOL)includeDocumentMetadataChanges
+                              waitForSyncWhenOnline:(BOOL)waitForSyncWhenOnline {
+  if (self = [super init]) {
+    _includeQueryMetadataChanges = includeQueryMetadataChanges;
+    _includeDocumentMetadataChanges = includeDocumentMetadataChanges;
+    _waitForSyncWhenOnline = waitForSyncWhenOnline;
+  }
+  return self;
+}
+
+- (instancetype)init {
+  FSTFail(@"FSTListenOptions init not supported");
+  return nil;
+}
+
+@end
+
+#pragma mark - FSTQueryListenersInfo
+
+/**
+ * Holds the listeners and the last received ViewSnapshot for a query being tracked by
+ * EventManager.
+ */
+@interface FSTQueryListenersInfo : NSObject
+@property(nonatomic, strong, nullable, readwrite) FSTViewSnapshot *viewSnapshot;
+@property(nonatomic, assign, readwrite) FSTTargetID targetID;
+@property(nonatomic, strong, readonly) NSMutableArray<FSTQueryListener *> *listeners;
+@end
+
+@implementation FSTQueryListenersInfo
+- (instancetype)init {
+  if (self = [super init]) {
+    _listeners = [NSMutableArray array];
+  }
+  return self;
+}
+
+@end
+
+#pragma mark - FSTQueryListener
+
+@interface FSTQueryListener ()
+
+/** The last received view snapshot. */
+@property(nonatomic, strong, nullable) FSTViewSnapshot *snapshot;
+
+@property(nonatomic, strong, readonly) FSTListenOptions *options;
+
+/**
+ * Initial snapshots (e.g. from cache) may not be propagated to the FSTViewSnapshotHandler.
+ * This flag is set to YES once we've actually raised an event.
+ */
+@property(nonatomic, assign, readwrite) BOOL raisedInitialEvent;
+
+/** The last online state this query listener got. */
+@property(nonatomic, assign, readwrite) FSTOnlineState onlineState;
+
+/** The FSTViewSnapshotHandler associated with this query listener. */
+@property(nonatomic, copy, nullable) FSTViewSnapshotHandler viewSnapshotHandler;
+
+@end
+
+@implementation FSTQueryListener
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                      options:(FSTListenOptions *)options
+          viewSnapshotHandler:(FSTViewSnapshotHandler)viewSnapshotHandler {
+  if (self = [super init]) {
+    _query = query;
+    _options = options;
+    _viewSnapshotHandler = viewSnapshotHandler;
+    _raisedInitialEvent = NO;
+  }
+  return self;
+}
+
+- (void)queryDidChangeViewSnapshot:(FSTViewSnapshot *)snapshot {
+  FSTAssert(snapshot.documentChanges.count > 0 || snapshot.syncStateChanged,
+            @"We got a new snapshot with no changes?");
+
+  if (!self.options.includeDocumentMetadataChanges) {
+    // Remove the metadata-only changes.
+    NSMutableArray<FSTDocumentViewChange *> *changes = [NSMutableArray array];
+    for (FSTDocumentViewChange *change in snapshot.documentChanges) {
+      if (change.type != FSTDocumentViewChangeTypeMetadata) {
+        [changes addObject:change];
+      }
+    }
+    snapshot = [[FSTViewSnapshot alloc] initWithQuery:snapshot.query
+                                            documents:snapshot.documents
+                                         oldDocuments:snapshot.oldDocuments
+                                      documentChanges:changes
+                                            fromCache:snapshot.fromCache
+                                     hasPendingWrites:snapshot.hasPendingWrites
+                                     syncStateChanged:snapshot.syncStateChanged];
+  }
+
+  if (!self.raisedInitialEvent) {
+    if ([self shouldRaiseInitialEventForSnapshot:snapshot onlineState:self.onlineState]) {
+      [self raiseInitialEventForSnapshot:snapshot];
+    }
+  } else if ([self shouldRaiseEventForSnapshot:snapshot]) {
+    self.viewSnapshotHandler(snapshot, nil);
+  }
+
+  self.snapshot = snapshot;
+}
+
+- (void)queryDidError:(NSError *)error {
+  self.viewSnapshotHandler(nil, error);
+}
+
+- (void)clientDidChangeOnlineState:(FSTOnlineState)onlineState {
+  self.onlineState = onlineState;
+  if (self.snapshot && !self.raisedInitialEvent &&
+      [self shouldRaiseInitialEventForSnapshot:self.snapshot onlineState:onlineState]) {
+    [self raiseInitialEventForSnapshot:self.snapshot];
+  }
+}
+
+- (BOOL)shouldRaiseInitialEventForSnapshot:(FSTViewSnapshot *)snapshot
+                               onlineState:(FSTOnlineState)onlineState {
+  FSTAssert(!self.raisedInitialEvent,
+            @"Determining whether to raise initial event, but already had first event.");
+
+  // Always raise the first event when we're synced
+  if (!snapshot.fromCache) {
+    return YES;
+  }
+
+  // NOTE: We consider OnlineState.Unknown as online (it should become Failed
+  // or Online if we wait long enough).
+  BOOL maybeOnline = onlineState != FSTOnlineStateFailed;
+  // Don't raise the event if we're online, aren't synced yet (checked
+  // above) and are waiting for a sync.
+  if (self.options.waitForSyncWhenOnline && maybeOnline) {
+    FSTAssert(snapshot.fromCache, @"Waiting for sync, but snapshot is not from cache.");
+    return NO;
+  }
+
+  // Raise data from cache if we have any documents or we are offline
+  return !snapshot.documents.isEmpty || onlineState == FSTOnlineStateFailed;
+}
+
+- (BOOL)shouldRaiseEventForSnapshot:(FSTViewSnapshot *)snapshot {
+  // We don't need to handle includeDocumentMetadataChanges here because the Metadata only changes
+  // have already been stripped out if needed. At this point the only changes we will see are the
+  // ones we should propagate.
+  if (snapshot.documentChanges.count > 0) {
+    return YES;
+  }
+
+  BOOL hasPendingWritesChanged =
+      self.snapshot && self.snapshot.hasPendingWrites != snapshot.hasPendingWrites;
+  if (snapshot.syncStateChanged || hasPendingWritesChanged) {
+    return self.options.includeQueryMetadataChanges;
+  }
+
+  // Generally we should have hit one of the cases above, but it's possible to get here if there
+  // were only metadata docChanges and they got stripped out.
+  return NO;
+}
+
+- (void)raiseInitialEventForSnapshot:(FSTViewSnapshot *)snapshot {
+  FSTAssert(!self.raisedInitialEvent, @"Trying to raise initial events for second time");
+  snapshot = [[FSTViewSnapshot alloc]
+         initWithQuery:snapshot.query
+             documents:snapshot.documents
+          oldDocuments:[FSTDocumentSet documentSetWithComparator:snapshot.query.comparator]
+       documentChanges:[FSTQueryListener getInitialViewChangesFor:snapshot]
+             fromCache:snapshot.fromCache
+      hasPendingWrites:snapshot.hasPendingWrites
+      syncStateChanged:YES];
+  self.raisedInitialEvent = YES;
+  self.viewSnapshotHandler(snapshot, nil);
+}
+
++ (NSArray<FSTDocumentViewChange *> *)getInitialViewChangesFor:(FSTViewSnapshot *)snapshot {
+  NSMutableArray<FSTDocumentViewChange *> *result = [NSMutableArray array];
+  for (FSTDocument *doc in snapshot.documents.documentEnumerator) {
+    [result addObject:[FSTDocumentViewChange changeWithDocument:doc
+                                                           type:FSTDocumentViewChangeTypeAdded]];
+  }
+  return result;
+}
+
+@end
+
+#pragma mark - FSTEventManager
+
+@interface FSTEventManager () <FSTSyncEngineDelegate>
+
+- (instancetype)initWithSyncEngine:(FSTSyncEngine *)syncEngine NS_DESIGNATED_INITIALIZER;
+
+@property(nonatomic, strong, readonly) FSTSyncEngine *syncEngine;
+@property(nonatomic, strong, readonly)
+    NSMutableDictionary<FSTQuery *, FSTQueryListenersInfo *> *queries;
+@property(nonatomic, assign) FSTOnlineState onlineState;
+
+@end
+
+@implementation FSTEventManager
+
++ (instancetype)eventManagerWithSyncEngine:(FSTSyncEngine *)syncEngine {
+  return [[FSTEventManager alloc] initWithSyncEngine:syncEngine];
+}
+
+- (instancetype)initWithSyncEngine:(FSTSyncEngine *)syncEngine {
+  if (self = [super init]) {
+    _syncEngine = syncEngine;
+    _queries = [NSMutableDictionary dictionary];
+
+    _syncEngine.delegate = self;
+  }
+  return self;
+}
+
+- (FSTTargetID)addListener:(FSTQueryListener *)listener {
+  FSTQuery *query = listener.query;
+  BOOL firstListen = NO;
+
+  FSTQueryListenersInfo *queryInfo = self.queries[query];
+  if (!queryInfo) {
+    firstListen = YES;
+    queryInfo = [[FSTQueryListenersInfo alloc] init];
+    self.queries[query] = queryInfo;
+  }
+  [queryInfo.listeners addObject:listener];
+
+  [listener clientDidChangeOnlineState:self.onlineState];
+
+  if (queryInfo.viewSnapshot) {
+    [listener queryDidChangeViewSnapshot:queryInfo.viewSnapshot];
+  }
+
+  if (firstListen) {
+    queryInfo.targetID = [self.syncEngine listenToQuery:query];
+  }
+  return queryInfo.targetID;
+}
+
+- (void)removeListener:(FSTQueryListener *)listener {
+  FSTQuery *query = listener.query;
+  BOOL lastListen = NO;
+
+  FSTQueryListenersInfo *queryInfo = self.queries[query];
+  if (queryInfo) {
+    [queryInfo.listeners removeObject:listener];
+    lastListen = (queryInfo.listeners.count == 0);
+  }
+
+  if (lastListen) {
+    [self.queries removeObjectForKey:query];
+    [self.syncEngine stopListeningToQuery:query];
+  }
+}
+
+- (void)handleViewSnapshots:(NSArray<FSTViewSnapshot *> *)viewSnapshots {
+  for (FSTViewSnapshot *viewSnapshot in viewSnapshots) {
+    FSTQuery *query = viewSnapshot.query;
+    FSTQueryListenersInfo *queryInfo = self.queries[query];
+    if (queryInfo) {
+      for (FSTQueryListener *listener in queryInfo.listeners) {
+        [listener queryDidChangeViewSnapshot:viewSnapshot];
+      }
+      queryInfo.viewSnapshot = viewSnapshot;
+    }
+  }
+}
+
+- (void)handleError:(NSError *)error forQuery:(FSTQuery *)query {
+  FSTQueryListenersInfo *queryInfo = self.queries[query];
+  if (queryInfo) {
+    for (FSTQueryListener *listener in queryInfo.listeners) {
+      [listener queryDidError:error];
+    }
+  }
+
+  // Remove all listeners. NOTE: We don't need to call [FSTSyncEngine stopListening] after an error.
+  [self.queries removeObjectForKey:query];
+}
+
+- (void)watchStreamDidChangeOnlineState:(FSTOnlineState)onlineState {
+  self.onlineState = onlineState;
+  for (FSTQueryListenersInfo *info in self.queries.objectEnumerator) {
+    for (FSTQueryListener *listener in info.listeners) {
+      [listener clientDidChangeOnlineState:onlineState];
+    }
+  }
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTFirestoreClient.h b/Firestore/Source/Core/FSTFirestoreClient.h
new file mode 100644
index 0000000..45f13cc
--- /dev/null
+++ b/Firestore/Source/Core/FSTFirestoreClient.h
@@ -0,0 +1,87 @@
+/*
+ * 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>
+
+#import "FSTRemoteStore.h"
+#import "FSTTypes.h"
+#import "FSTViewSnapshot.h"
+
+@class FSTDatabaseID;
+@class FSTDatabaseInfo;
+@class FSTDispatchQueue;
+@class FSTDocument;
+@class FSTListenOptions;
+@class FSTMutation;
+@class FSTQuery;
+@class FSTQueryListener;
+@class FSTTransaction;
+@protocol FSTCredentialsProvider;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * FirestoreClient is a top-level class that constructs and owns all of the pieces of the client
+ * SDK architecture. It is responsible for creating the worker queue that is shared by all of the
+ * other components in the system.
+ */
+@interface FSTFirestoreClient : NSObject
+
+/**
+ * Creates and returns a FSTFirestoreClient with the given parameters.
+ *
+ * All callbacks and events will be triggered on the provided userDispatchQueue.
+ */
++ (instancetype)clientWithDatabaseInfo:(FSTDatabaseInfo *)databaseInfo
+                        usePersistence:(BOOL)usePersistence
+                   credentialsProvider:(id<FSTCredentialsProvider>)credentialsProvider
+                     userDispatchQueue:(FSTDispatchQueue *)userDispatchQueue
+                   workerDispatchQueue:(FSTDispatchQueue *)workerDispatchQueue;
+
+- (instancetype)init __attribute__((unavailable("Use static constructor method.")));
+
+/** Shuts down this client, cancels all writes / listeners, and releases all resources. */
+- (void)shutdownWithCompletion:(nullable FSTVoidErrorBlock)completion;
+
+/** Starts listening to a query. */
+- (FSTQueryListener *)listenToQuery:(FSTQuery *)query
+                            options:(FSTListenOptions *)options
+                viewSnapshotHandler:(FSTViewSnapshotHandler)viewSnapshotHandler;
+
+/** Stops listening to a query previously listened to. */
+- (void)removeListener:(FSTQueryListener *)listener;
+
+/** Write mutations. completion will be notified when it's written to the backend. */
+- (void)writeMutations:(NSArray<FSTMutation *> *)mutations
+            completion:(nullable FSTVoidErrorBlock)completion;
+
+/** Tries to execute the transaction in updateBlock up to retries times. */
+- (void)transactionWithRetries:(int)retries
+                   updateBlock:(FSTTransactionBlock)updateBlock
+                    completion:(FSTVoidIDErrorBlock)completion;
+
+/** The database ID of the databaseInfo this client was initialized with. */
+@property(nonatomic, strong, readonly) FSTDatabaseID *databaseID;
+
+/**
+ * Dispatch queue for user callbacks / events. This will often be the "Main Dispatch Queue" of the
+ * app but the developer can configure it to a different queue if they so choose.
+ */
+@property(nonatomic, strong, readonly) FSTDispatchQueue *userDispatchQueue;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTFirestoreClient.m b/Firestore/Source/Core/FSTFirestoreClient.m
new file mode 100644
index 0000000..2066ce9
--- /dev/null
+++ b/Firestore/Source/Core/FSTFirestoreClient.m
@@ -0,0 +1,271 @@
+/*
+ * 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 "FSTFirestoreClient.h"
+
+#import "FSTAssert.h"
+#import "FSTClasses.h"
+#import "FSTCredentialsProvider.h"
+#import "FSTDatabaseInfo.h"
+#import "FSTDatastore.h"
+#import "FSTDispatchQueue.h"
+#import "FSTEagerGarbageCollector.h"
+#import "FSTEventManager.h"
+#import "FSTLevelDB.h"
+#import "FSTLocalSerializer.h"
+#import "FSTLocalStore.h"
+#import "FSTLogger.h"
+#import "FSTMemoryPersistence.h"
+#import "FSTNoOpGarbageCollector.h"
+#import "FSTRemoteStore.h"
+#import "FSTSerializerBeta.h"
+#import "FSTSyncEngine.h"
+#import "FSTTransaction.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTFirestoreClient ()
+- (instancetype)initWithDatabaseInfo:(FSTDatabaseInfo *)databaseInfo
+                      usePersistence:(BOOL)usePersistence
+                 credentialsProvider:(id<FSTCredentialsProvider>)credentialsProvider
+                   userDispatchQueue:(FSTDispatchQueue *)userDispatchQueue
+                 workerDispatchQueue:(FSTDispatchQueue *)queue NS_DESIGNATED_INITIALIZER;
+
+@property(nonatomic, strong, readonly) FSTDatabaseInfo *databaseInfo;
+@property(nonatomic, strong, readonly) FSTEventManager *eventManager;
+@property(nonatomic, strong, readonly) id<FSTPersistence> persistence;
+@property(nonatomic, strong, readonly) FSTSyncEngine *syncEngine;
+@property(nonatomic, strong, readonly) FSTRemoteStore *remoteStore;
+@property(nonatomic, strong, readonly) FSTLocalStore *localStore;
+
+/**
+ * Dispatch queue responsible for all of our internal processing. When we get incoming work from
+ * the user (via public API) or the network (incoming GRPC messages), we should always dispatch
+ * onto this queue. This ensures our internal data structures are never accessed from multiple
+ * threads simultaneously.
+ */
+@property(nonatomic, strong, readonly) FSTDispatchQueue *workerDispatchQueue;
+
+@property(nonatomic, strong, readonly) id<FSTCredentialsProvider> credentialsProvider;
+
+@end
+
+@implementation FSTFirestoreClient
+
++ (instancetype)clientWithDatabaseInfo:(FSTDatabaseInfo *)databaseInfo
+                        usePersistence:(BOOL)usePersistence
+                   credentialsProvider:(id<FSTCredentialsProvider>)credentialsProvider
+                     userDispatchQueue:(FSTDispatchQueue *)userDispatchQueue
+                   workerDispatchQueue:(FSTDispatchQueue *)workerDispatchQueue {
+  return [[FSTFirestoreClient alloc] initWithDatabaseInfo:databaseInfo
+                                           usePersistence:usePersistence
+                                      credentialsProvider:credentialsProvider
+                                        userDispatchQueue:userDispatchQueue
+                                      workerDispatchQueue:workerDispatchQueue];
+}
+
+- (instancetype)initWithDatabaseInfo:(FSTDatabaseInfo *)databaseInfo
+                      usePersistence:(BOOL)usePersistence
+                 credentialsProvider:(id<FSTCredentialsProvider>)credentialsProvider
+                   userDispatchQueue:(FSTDispatchQueue *)userDispatchQueue
+                 workerDispatchQueue:(FSTDispatchQueue *)workerDispatchQueue {
+  if (self = [super init]) {
+    _databaseInfo = databaseInfo;
+    _credentialsProvider = credentialsProvider;
+    _userDispatchQueue = userDispatchQueue;
+    _workerDispatchQueue = workerDispatchQueue;
+
+    dispatch_semaphore_t initialUserAvailable = dispatch_semaphore_create(0);
+    __block FSTUser *initialUser;
+    FSTWeakify(self);
+    _credentialsProvider.userChangeListener = ^(FSTUser *user) {
+      FSTStrongify(self);
+      if (self) {
+        if (!initialUser) {
+          initialUser = user;
+          dispatch_semaphore_signal(initialUserAvailable);
+        } else {
+          [workerDispatchQueue dispatchAsync:^{
+            [self userDidChange:user];
+          }];
+        }
+      }
+    };
+
+    // Defer initialization until we get the current user from the userChangeListener. This is
+    // guaranteed to be synchronously dispatched onto our worker queue, so we will be initialized
+    // before any subsequently queued work runs.
+    [_workerDispatchQueue dispatchAsync:^{
+      dispatch_semaphore_wait(initialUserAvailable, DISPATCH_TIME_FOREVER);
+
+      [self initializeWithUser:initialUser usePersistence:usePersistence];
+    }];
+  }
+  return self;
+}
+
+- (void)initializeWithUser:(FSTUser *)user usePersistence:(BOOL)usePersistence {
+  // Do all of our initialization on our own dispatch queue.
+  [self.workerDispatchQueue verifyIsCurrentQueue];
+
+  // Note: The initialization work must all be synchronous (we can't dispatch more work) since
+  // external write/listen operations could get queued to run before that subsequent work
+  // completes.
+  id<FSTGarbageCollector> garbageCollector;
+  if (usePersistence) {
+    // TODO(http://b/33384523): For now we just disable garbage collection when persistence is
+    // enabled.
+    garbageCollector = [[FSTNoOpGarbageCollector alloc] init];
+
+    NSString *dir = [FSTLevelDB storageDirectoryForDatabaseInfo:self.databaseInfo
+                                             documentsDirectory:[FSTLevelDB documentsDirectory]];
+
+    FSTSerializerBeta *remoteSerializer =
+        [[FSTSerializerBeta alloc] initWithDatabaseID:self.databaseInfo.databaseID];
+    FSTLocalSerializer *serializer =
+        [[FSTLocalSerializer alloc] initWithRemoteSerializer:remoteSerializer];
+
+    _persistence = [[FSTLevelDB alloc] initWithDirectory:dir serializer:serializer];
+  } else {
+    garbageCollector = [[FSTEagerGarbageCollector alloc] init];
+    _persistence = [FSTMemoryPersistence persistence];
+  }
+
+  NSError *error;
+  if (![_persistence start:&error]) {
+    // If local storage fails to start then just throw up our hands: the error is unrecoverable.
+    // There's nothing an end-user can do and nearly all failures indicate the developer is doing
+    // something grossly wrong so we should stop them cold in their tracks with a failure they
+    // can't ignore.
+    [NSException raise:NSInternalInconsistencyException format:@"Failed to open DB: %@", error];
+  }
+
+  _localStore = [[FSTLocalStore alloc] initWithPersistence:_persistence
+                                          garbageCollector:garbageCollector
+                                               initialUser:user];
+
+  FSTDatastore *datastore = [FSTDatastore datastoreWithDatabase:self.databaseInfo
+                                            workerDispatchQueue:self.workerDispatchQueue
+                                                    credentials:self.credentialsProvider];
+
+  _remoteStore = [FSTRemoteStore remoteStoreWithLocalStore:_localStore datastore:datastore];
+
+  _syncEngine = [[FSTSyncEngine alloc] initWithLocalStore:_localStore
+                                              remoteStore:_remoteStore
+                                              initialUser:user];
+
+  _eventManager = [FSTEventManager eventManagerWithSyncEngine:_syncEngine];
+
+  // Setup wiring for remote store.
+  _remoteStore.syncEngine = _syncEngine;
+
+  _remoteStore.onlineStateDelegate = _eventManager;
+
+  // NOTE: RemoteStore depends on LocalStore (for persisting stream tokens, refilling mutation
+  // queue, etc.) so must be started after LocalStore.
+  [_localStore start];
+  [_remoteStore start];
+}
+
+- (void)userDidChange:(FSTUser *)user {
+  [self.workerDispatchQueue verifyIsCurrentQueue];
+
+  FSTLog(@"User Changed: %@", user);
+  [self.syncEngine userDidChange:user];
+}
+
+- (void)shutdownWithCompletion:(nullable FSTVoidErrorBlock)completion {
+  [self.workerDispatchQueue dispatchAsync:^{
+    self.credentialsProvider.userChangeListener = nil;
+
+    [self.remoteStore shutdown];
+    [self.localStore shutdown];
+    [self.persistence shutdown];
+    if (completion) {
+      [self.userDispatchQueue dispatchAsync:^{
+        completion(nil);
+      }];
+    }
+  }];
+}
+
+- (FSTQueryListener *)listenToQuery:(FSTQuery *)query
+                            options:(FSTListenOptions *)options
+                viewSnapshotHandler:(FSTViewSnapshotHandler)viewSnapshotHandler {
+  FSTQueryListener *listener = [[FSTQueryListener alloc] initWithQuery:query
+                                                               options:options
+                                                   viewSnapshotHandler:viewSnapshotHandler];
+
+  [self.workerDispatchQueue dispatchAsync:^{
+    [self.eventManager addListener:listener];
+  }];
+
+  return listener;
+}
+
+- (void)removeListener:(FSTQueryListener *)listener {
+  [self.workerDispatchQueue dispatchAsync:^{
+    [self.eventManager removeListener:listener];
+  }];
+}
+
+- (void)writeMutations:(NSArray<FSTMutation *> *)mutations
+            completion:(nullable FSTVoidErrorBlock)completion {
+  [self.workerDispatchQueue dispatchAsync:^{
+    if (mutations.count == 0) {
+      [self.userDispatchQueue dispatchAsync:^{
+        completion(nil);
+      }];
+    } else {
+      [self.syncEngine writeMutations:mutations
+                           completion:^(NSError *error) {
+                             // Dispatch the result back onto the user dispatch queue.
+                             if (completion) {
+                               [self.userDispatchQueue dispatchAsync:^{
+                                 completion(error);
+                               }];
+                             }
+                           }];
+    }
+  }];
+};
+
+- (void)transactionWithRetries:(int)retries
+                   updateBlock:(FSTTransactionBlock)updateBlock
+                    completion:(FSTVoidIDErrorBlock)completion {
+  [self.workerDispatchQueue dispatchAsync:^{
+    [self.syncEngine transactionWithRetries:retries
+                        workerDispatchQueue:self.workerDispatchQueue
+                                updateBlock:updateBlock
+                                 completion:^(id _Nullable result, NSError *_Nullable error) {
+                                   // Dispatch the result back onto the user dispatch queue.
+                                   if (completion) {
+                                     [self.userDispatchQueue dispatchAsync:^{
+                                       completion(result, error);
+                                     }];
+                                   }
+                                 }];
+
+  }];
+}
+
+- (FSTDatabaseID *)databaseID {
+  return self.databaseInfo.databaseID;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTQuery.h b/Firestore/Source/Core/FSTQuery.h
new file mode 100644
index 0000000..0562ae4
--- /dev/null
+++ b/Firestore/Source/Core/FSTQuery.h
@@ -0,0 +1,269 @@
+/*
+ * 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 FSTDocument;
+@class FSTDocumentKey;
+@class FSTFieldPath;
+@class FSTFieldValue;
+@class FSTResourcePath;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * FSTRelationFilterOperator is a value relation operator that can be used to filter documents.
+ * It is similar to NSPredicateOperatorType, but only has operators supported by Firestore.
+ */
+typedef NS_ENUM(NSInteger, FSTRelationFilterOperator) {
+  FSTRelationFilterOperatorLessThan = 0,
+  FSTRelationFilterOperatorLessThanOrEqual,
+  FSTRelationFilterOperatorEqual,
+  FSTRelationFilterOperatorGreaterThanOrEqual,
+  FSTRelationFilterOperatorGreaterThan,
+};
+
+/** Interface used for all query filters. */
+@protocol FSTFilter <NSObject>
+
+/** Returns the field the Filter operates over. */
+- (FSTFieldPath *)field;
+
+/** Returns true if a document matches the filter. */
+- (BOOL)matchesDocument:(FSTDocument *)document;
+
+/** A unique ID identifying the filter; used when serializing queries. */
+- (NSString *)canonicalID;
+
+@end
+
+/**
+ * FSTRelationFilter is a document filter constraint on a query with a single relation operator.
+ * It is similar to NSComparisonPredicate, except customized for Firestore semantics.
+ */
+@interface FSTRelationFilter : NSObject <FSTFilter>
+
+/**
+ * Creates a new constraint for filtering documents.
+ *
+ * @param field A path to a field in the document to filter on. The LHS of the expression.
+ * @param filterOperator The binary operator to apply.
+ * @param value A constant value to compare @a field to. The RHS of the expression.
+ * @return A new instance of FSTRelationFilter.
+ */
++ (instancetype)filterWithField:(FSTFieldPath *)field
+                 filterOperator:(FSTRelationFilterOperator)filterOperator
+                          value:(FSTFieldValue *)value;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** Returns YES if the receiver is not an equality relation. */
+- (BOOL)isInequality;
+
+/** The left hand side of the relation. A path into a document field. */
+@property(nonatomic, strong, readonly) FSTFieldPath *field;
+
+/** The type of equality/inequality operator to use in the relation. */
+@property(nonatomic, assign, readonly) FSTRelationFilterOperator filterOperator;
+
+/** The right hand side of the relation. A constant value to compare to. */
+@property(nonatomic, strong, readonly) FSTFieldValue *value;
+
+@end
+
+/** Filter that matches NULL values. */
+@interface FSTNullFilter : NSObject <FSTFilter>
+- (instancetype)init NS_UNAVAILABLE;
+- (instancetype)initWithField:(FSTFieldPath *)field NS_DESIGNATED_INITIALIZER;
+@end
+
+/** Filter that matches NAN values. */
+@interface FSTNanFilter : NSObject <FSTFilter>
+- (instancetype)init NS_UNAVAILABLE;
+- (instancetype)initWithField:(FSTFieldPath *)field NS_DESIGNATED_INITIALIZER;
+@end
+
+/** FSTSortOrder is a field and direction to order query results by. */
+@interface FSTSortOrder : NSObject <NSCopying>
+
+/** Creates a new sort order with the given field and direction. */
++ (instancetype)sortOrderWithFieldPath:(FSTFieldPath *)fieldPath ascending:(BOOL)ascending;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** Compares two documents based on the field and direction of this sort order. */
+- (NSComparisonResult)compareDocument:(FSTDocument *)document1 toDocument:(FSTDocument *)document2;
+
+/** The direction of the sort. */
+@property(nonatomic, assign, readonly, getter=isAscending) BOOL ascending;
+
+/** The field to sort by. */
+@property(nonatomic, strong, readonly) FSTFieldPath *field;
+
+@end
+
+/**
+ * FSTBound represents a bound of a query.
+ *
+ * The bound is specified with the given components representing a position and whether it's just
+ * before or just after the position (relative to whatever the query order is).
+ *
+ * The position represents a logical index position for a query. It's a prefix of values for
+ * the (potentially implicit) order by clauses of a query.
+ *
+ * FSTBound provides a function to determine whether a document comes before or after a bound.
+ * This is influenced by whether the position is just before or just after the provided values.
+ */
+@interface FSTBound : NSObject <NSCopying>
+
+/**
+ * Creates a new bound.
+ *
+ * @param position The position relative to the sort order.
+ * @param isBefore Whether this bound is just before or just after the position.
+ */
++ (instancetype)boundWithPosition:(NSArray<FSTFieldValue *> *)position isBefore:(BOOL)isBefore;
+
+/** Whether this bound is just before or just after the provided position */
+@property(nonatomic, assign, readonly, getter=isBefore) BOOL before;
+
+/** The index position of this bound represented as an array of field values. */
+@property(nonatomic, strong, readonly) NSArray<FSTFieldValue *> *position;
+
+/** Returns YES if a document comes before a bound using the provided sort order. */
+- (BOOL)sortsBeforeDocument:(FSTDocument *)document
+             usingSortOrder:(NSArray<FSTSortOrder *> *)sortOrder;
+
+@end
+
+/** FSTQuery represents the internal structure of a Firestore query. */
+@interface FSTQuery : NSObject <NSCopying>
+
+- (id)init NS_UNAVAILABLE;
+
+/**
+ * Initializes a query with all of its components directly.
+ */
+- (instancetype)initWithPath:(FSTResourcePath *)path
+                    filterBy:(NSArray<id<FSTFilter>> *)filters
+                     orderBy:(NSArray<FSTSortOrder *> *)sortOrders
+                       limit:(NSInteger)limit
+                     startAt:(nullable FSTBound *)startAtBound
+                       endAt:(nullable FSTBound *)endAtBound NS_DESIGNATED_INITIALIZER;
+
+/**
+ * Creates and returns a new FSTQuery.
+ *
+ * @param path The path to the collection to be queried over.
+ * @return A new instance of FSTQuery.
+ */
++ (instancetype)queryWithPath:(FSTResourcePath *)path;
+
+/**
+ * Returns the list of ordering constraints that were explicitly requested on the query by the
+ * user.
+ *
+ * Note that the actual query performed might add additional sort orders to match the behavior
+ * of the backend.
+ */
+- (NSArray<FSTSortOrder *> *)explicitSortOrders;
+
+/**
+ * Returns the full list of ordering constraints on the query.
+ *
+ * This might include additional sort orders added implicitly to match the backend behavior.
+ */
+- (NSArray<FSTSortOrder *> *)sortOrders;
+
+/**
+ * Creates a new FSTQuery with an additional filter.
+ *
+ * @param filter The predicate to filter by.
+ * @return the new FSTQuery.
+ */
+- (instancetype)queryByAddingFilter:(id<FSTFilter>)filter;
+
+/**
+ * Creates a new FSTQuery with an additional ordering constraint.
+ *
+ * @param sortOrder The key and direction to order by.
+ * @return the new FSTQuery.
+ */
+- (instancetype)queryByAddingSortOrder:(FSTSortOrder *)sortOrder;
+
+/**
+ * Returns a new FSTQuery with the given limit on how many results can be returned.
+ *
+ * @param limit The maximum number of results to return. If @a limit <= 0, behavior is unspecified.
+ *     If @a limit == NSNotFound, then no limit is applied.
+ */
+- (instancetype)queryBySettingLimit:(NSInteger)limit;
+
+/**
+ * Creates a new FSTQuery starting at the provided bound.
+ *
+ * @param bound The bound to start this query at.
+ * @return the new FSTQuery.
+ */
+- (instancetype)queryByAddingStartAt:(FSTBound *)bound;
+
+/**
+ * Creates a new FSTQuery ending at the provided bound.
+ *
+ * @param bound The bound to end this query at.
+ * @return the new FSTQuery.
+ */
+- (instancetype)queryByAddingEndAt:(FSTBound *)bound;
+
+/** Returns YES if the receiver is query for a specific document. */
+- (BOOL)isDocumentQuery;
+
+/** Returns YES if the @a document matches the constraints of the receiver. */
+- (BOOL)matchesDocument:(FSTDocument *)document;
+
+/** Returns a comparator that will sort documents according to the receiver's sort order. */
+- (NSComparator)comparator;
+
+/** Returns the field of the first filter on the receiver that's an inequality, or nil if none. */
+- (FSTFieldPath *_Nullable)inequalityFilterField;
+
+/** Returns the first field in an order-by constraint, or nil if none. */
+- (FSTFieldPath *_Nullable)firstSortOrderField;
+
+/** The base path of the query. */
+@property(nonatomic, strong, readonly) FSTResourcePath *path;
+
+/** The filters on the documents returned by the query. */
+@property(nonatomic, strong, readonly) NSArray<id<FSTFilter>> *filters;
+
+/** The maximum number of results to return, or NSNotFound if no limit. */
+@property(nonatomic, assign, readonly) NSInteger limit;
+
+/**
+ * A canonical string identifying the query. Two different instances of equivalent queries will
+ * return the same canonicalID.
+ */
+@property(nonatomic, strong, readonly) NSString *canonicalID;
+
+/** An optional bound to start the query at. */
+@property(nonatomic, nullable, strong, readonly) FSTBound *startAt;
+
+/** An optional bound to end the query at. */
+@property(nonatomic, nullable, strong, readonly) FSTBound *endAt;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTQuery.m b/Firestore/Source/Core/FSTQuery.m
new file mode 100644
index 0000000..b220c7c
--- /dev/null
+++ b/Firestore/Source/Core/FSTQuery.m
@@ -0,0 +1,759 @@
+/*
+ * 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 "FSTQuery.h"
+
+#import "FIRFirestore+Internal.h"
+#import "FSTAssert.h"
+#import "FSTDocument.h"
+#import "FSTDocumentKey.h"
+#import "FSTFieldValue.h"
+#import "FSTPath.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTRelationFilterOperator functions
+
+NSString *FSTStringFromQueryRelationOperator(FSTRelationFilterOperator filterOperator) {
+  switch (filterOperator) {
+    case FSTRelationFilterOperatorLessThan:
+      return @"<";
+    case FSTRelationFilterOperatorLessThanOrEqual:
+      return @"<=";
+    case FSTRelationFilterOperatorEqual:
+      return @"==";
+    case FSTRelationFilterOperatorGreaterThanOrEqual:
+      return @">=";
+    case FSTRelationFilterOperatorGreaterThan:
+      return @">";
+    default:
+      FSTCFail(@"Unknown FSTRelationFilterOperator %lu", (unsigned long)filterOperator);
+  }
+}
+
+#pragma mark - FSTRelationFilter
+
+@interface FSTRelationFilter ()
+
+/**
+ * Initializes the receiver relation filter.
+ *
+ * @param field A path to a field in the document to filter on. The LHS of the expression.
+ * @param filterOperator The binary operator to apply.
+ * @param value A constant value to compare @a field to. The RHS of the expression.
+ */
+- (instancetype)initWithField:(FSTFieldPath *)field
+               filterOperator:(FSTRelationFilterOperator)filterOperator
+                        value:(FSTFieldValue *)value NS_DESIGNATED_INITIALIZER;
+
+/** Returns YES if @a document matches the receiver's constraint. */
+- (BOOL)matchesDocument:(FSTDocument *)document;
+
+/**
+ * A canonical string identifying the filter. Two different instances of equivalent filters will
+ * return the same canonicalID.
+ */
+- (NSString *)canonicalID;
+
+@end
+
+@implementation FSTRelationFilter
+
+#pragma mark - Constructor methods
+
++ (instancetype)filterWithField:(FSTFieldPath *)field
+                 filterOperator:(FSTRelationFilterOperator)filterOperator
+                          value:(FSTFieldValue *)value {
+  return [[FSTRelationFilter alloc] initWithField:field filterOperator:filterOperator value:value];
+}
+
+- (instancetype)initWithField:(FSTFieldPath *)field
+               filterOperator:(FSTRelationFilterOperator)filterOperator
+                        value:(FSTFieldValue *)value {
+  self = [super init];
+  if (self) {
+    _field = field;
+    _filterOperator = filterOperator;
+    _value = value;
+  }
+  return self;
+}
+
+#pragma mark - Public Methods
+
+- (BOOL)isInequality {
+  return self.filterOperator != FSTRelationFilterOperatorEqual;
+}
+
+#pragma mark - NSObject methods
+
+- (NSString *)description {
+  return [NSString stringWithFormat:@"%@ %@ %@", [self.field canonicalString],
+                                    FSTStringFromQueryRelationOperator(self.filterOperator),
+                                    self.value];
+}
+
+- (BOOL)isEqual:(id)other {
+  if (self == other) {
+    return YES;
+  }
+  if (![other isKindOfClass:[FSTRelationFilter class]]) {
+    return NO;
+  }
+  return [self isEqualToFilter:(FSTRelationFilter *)other];
+}
+
+#pragma mark - Private methods
+
+- (BOOL)matchesDocument:(FSTDocument *)document {
+  if ([self.field isKeyFieldPath]) {
+    FSTAssert([self.value isKindOfClass:[FSTReferenceValue class]],
+              @"Comparing on key, but filter value not a FSTReferenceValue.");
+    FSTReferenceValue *refValue = (FSTReferenceValue *)self.value;
+    NSComparisonResult comparison = FSTDocumentKeyComparator(document.key, refValue.value);
+    return [self matchesComparison:comparison];
+  } else {
+    return [self matchesValue:[document fieldForPath:self.field]];
+  }
+}
+
+- (NSString *)canonicalID {
+  // TODO(b/37283291): This should be collision robust and avoid relying on |description| methods.
+  return [NSString stringWithFormat:@"%@%@%@", [self.field canonicalString],
+                                    FSTStringFromQueryRelationOperator(self.filterOperator),
+                                    [self.value value]];
+}
+
+- (BOOL)isEqualToFilter:(FSTRelationFilter *)other {
+  if (self.filterOperator != other.filterOperator) {
+    return NO;
+  }
+  if (![self.field isEqual:other.field]) {
+    return NO;
+  }
+  if (![self.value isEqual:other.value]) {
+    return NO;
+  }
+  return YES;
+}
+
+/** Returns YES if receiver is true with the given value as its LHS. */
+- (BOOL)matchesValue:(FSTFieldValue *)other {
+  // Only compare types with matching backend order (such as double and int).
+  return self.value.typeOrder == other.typeOrder &&
+         [self matchesComparison:[other compare:self.value]];
+}
+
+- (BOOL)matchesComparison:(NSComparisonResult)comparison {
+  switch (self.filterOperator) {
+    case FSTRelationFilterOperatorLessThan:
+      return comparison == NSOrderedAscending;
+    case FSTRelationFilterOperatorLessThanOrEqual:
+      return comparison == NSOrderedAscending || comparison == NSOrderedSame;
+    case FSTRelationFilterOperatorEqual:
+      return comparison == NSOrderedSame;
+    case FSTRelationFilterOperatorGreaterThanOrEqual:
+      return comparison == NSOrderedDescending || comparison == NSOrderedSame;
+    case FSTRelationFilterOperatorGreaterThan:
+      return comparison == NSOrderedDescending;
+    default:
+      FSTFail(@"Unknown operator: %ld", (long)self.filterOperator);
+  }
+}
+
+@end
+
+#pragma mark - FSTNullFilter
+
+@interface FSTNullFilter ()
+@property(nonatomic, strong, readonly) FSTFieldPath *field;
+@end
+
+@implementation FSTNullFilter
+- (instancetype)initWithField:(FSTFieldPath *)field {
+  if (self = [super init]) {
+    _field = field;
+  }
+  return self;
+}
+
+- (BOOL)matchesDocument:(FSTDocument *)document {
+  FSTFieldValue *fieldValue = [document fieldForPath:self.field];
+  return fieldValue != nil && [fieldValue isEqual:[FSTNullValue nullValue]];
+}
+
+- (NSString *)canonicalID {
+  return [NSString stringWithFormat:@"%@ IS NULL", [self.field canonicalString]];
+}
+
+- (NSString *)description {
+  return [self canonicalID];
+}
+
+- (BOOL)isEqual:(id)other {
+  if (other == self) return YES;
+  if (!other || ![[other class] isEqual:[self class]]) return NO;
+
+  return [self.field isEqual:((FSTNullFilter *)other).field];
+}
+
+- (NSUInteger)hash {
+  return [self.field hash];
+}
+
+@end
+
+#pragma mark - FSTNanFilter
+
+@interface FSTNanFilter ()
+@property(nonatomic, strong, readonly) FSTFieldPath *field;
+@end
+
+@implementation FSTNanFilter
+
+- (instancetype)initWithField:(FSTFieldPath *)field {
+  if (self = [super init]) {
+    _field = field;
+  }
+  return self;
+}
+
+- (BOOL)matchesDocument:(FSTDocument *)document {
+  FSTFieldValue *fieldValue = [document fieldForPath:self.field];
+  return fieldValue != nil && [fieldValue isEqual:[FSTDoubleValue nanValue]];
+}
+
+- (NSString *)canonicalID {
+  return [NSString stringWithFormat:@"%@ IS NaN", [self.field canonicalString]];
+}
+
+- (NSString *)description {
+  return [self canonicalID];
+}
+
+- (BOOL)isEqual:(id)other {
+  if (other == self) return YES;
+  if (!other || ![[other class] isEqual:[self class]]) return NO;
+
+  return [self.field isEqual:((FSTNanFilter *)other).field];
+}
+
+- (NSUInteger)hash {
+  return [self.field hash];
+}
+@end
+
+#pragma mark - FSTSortOrder
+
+@interface FSTSortOrder ()
+
+/** Creates a new sort order with the given field and direction. */
+- (instancetype)initWithFieldPath:(FSTFieldPath *)fieldPath ascending:(BOOL)ascending;
+
+- (NSString *)canonicalID;
+
+@end
+
+@implementation FSTSortOrder
+
+#pragma mark - Constructor methods
+
++ (instancetype)sortOrderWithFieldPath:(FSTFieldPath *)fieldPath ascending:(BOOL)ascending {
+  return [[FSTSortOrder alloc] initWithFieldPath:fieldPath ascending:ascending];
+}
+
+- (instancetype)initWithFieldPath:(FSTFieldPath *)fieldPath ascending:(BOOL)ascending {
+  self = [super init];
+  if (self) {
+    _field = fieldPath;
+    _ascending = ascending;
+  }
+  return self;
+}
+
+#pragma mark - Public methods
+
+- (NSComparisonResult)compareDocument:(FSTDocument *)document1 toDocument:(FSTDocument *)document2 {
+  int modifier = self.isAscending ? 1 : -1;
+  if ([self.field isEqual:[FSTFieldPath keyFieldPath]]) {
+    return (NSComparisonResult)(modifier * FSTDocumentKeyComparator(document1.key, document2.key));
+  } else {
+    FSTFieldValue *value1 = [document1 fieldForPath:self.field];
+    FSTFieldValue *value2 = [document2 fieldForPath:self.field];
+    FSTAssert(value1 != nil && value2 != nil,
+              @"Trying to compare documents on fields that don't exist.");
+    return modifier * [value1 compare:value2];
+  }
+}
+
+- (NSString *)canonicalID {
+  return [NSString
+      stringWithFormat:@"%@%@", self.field.canonicalString, self.isAscending ? @"asc" : @"desc"];
+}
+
+- (BOOL)isEqualToSortOrder:(FSTSortOrder *)other {
+  return [self.field isEqual:other.field] && self.isAscending == other.isAscending;
+}
+
+#pragma mark - NSObject methods
+
+- (NSString *)description {
+  return [NSString stringWithFormat:@"<FSTSortOrder: path:%@ dir:%@>", self.field,
+                                    self.ascending ? @"asc" : @"desc"];
+}
+
+- (BOOL)isEqual:(NSObject *)other {
+  if (self == other) {
+    return YES;
+  }
+  if (![other isKindOfClass:[FSTSortOrder class]]) {
+    return NO;
+  }
+  return [self isEqualToSortOrder:(FSTSortOrder *)other];
+}
+
+- (NSUInteger)hash {
+  return [self.canonicalID hash];
+}
+
+- (instancetype)copyWithZone:(nullable NSZone *)zone {
+  return self;
+}
+
+@end
+
+#pragma mark - FSTBound
+
+@implementation FSTBound
+
+- (instancetype)initWithPosition:(NSArray<FSTFieldValue *> *)position isBefore:(BOOL)isBefore {
+  if (self = [super init]) {
+    _position = position;
+    _before = isBefore;
+  }
+  return self;
+}
+
++ (instancetype)boundWithPosition:(NSArray<FSTFieldValue *> *)position isBefore:(BOOL)isBefore {
+  return [[FSTBound alloc] initWithPosition:position isBefore:isBefore];
+}
+
+- (NSString *)canonicalString {
+  // TODO(b/29183165): Make this collision robust.
+  NSMutableString *string = [NSMutableString string];
+  if (self.isBefore) {
+    [string appendString:@"b:"];
+  } else {
+    [string appendString:@"a:"];
+  }
+  for (FSTFieldValue *component in self.position) {
+    [string appendFormat:@"%@", component];
+  }
+  return string;
+}
+
+- (BOOL)sortsBeforeDocument:(FSTDocument *)document
+             usingSortOrder:(NSArray<FSTSortOrder *> *)sortOrder {
+  FSTAssert(self.position.count <= sortOrder.count,
+            @"FSTIndexPosition has more components than provided sort order.");
+  __block NSComparisonResult result = NSOrderedSame;
+  [self.position enumerateObjectsUsingBlock:^(FSTFieldValue *fieldValue, NSUInteger idx,
+                                              BOOL *stop) {
+    FSTSortOrder *sortOrderComponent = sortOrder[idx];
+    NSComparisonResult comparison;
+    if ([sortOrderComponent.field isEqual:[FSTFieldPath keyFieldPath]]) {
+      FSTAssert([fieldValue isKindOfClass:[FSTReferenceValue class]],
+                @"FSTBound has a non-key value where the key path is being used %@", fieldValue);
+      comparison = [fieldValue.value compare:document.key];
+    } else {
+      FSTFieldValue *docValue = [document fieldForPath:sortOrderComponent.field];
+      FSTAssert(docValue != nil, @"Field should exist since document matched the orderBy already.");
+      comparison = [fieldValue compare:docValue];
+    }
+
+    if (!sortOrderComponent.isAscending) {
+      comparison = comparison * -1;
+    }
+
+    if (comparison != 0) {
+      result = comparison;
+      *stop = YES;
+    }
+  }];
+
+  return self.isBefore ? result <= NSOrderedSame : result < NSOrderedSame;
+}
+
+#pragma mark - NSObject methods
+
+- (NSString *)description {
+  return [NSString stringWithFormat:@"<FSTBound: position:%@ before:%@>", self.position,
+                                    self.isBefore ? @"YES" : @"NO"];
+}
+
+- (BOOL)isEqual:(NSObject *)other {
+  if (self == other) {
+    return YES;
+  }
+  if (![other isKindOfClass:[FSTBound class]]) {
+    return NO;
+  }
+
+  FSTBound *otherBound = (FSTBound *)other;
+
+  return [self.position isEqualToArray:otherBound.position] && self.isBefore == otherBound.isBefore;
+}
+
+- (NSUInteger)hash {
+  return 31 * self.position.hash + (self.isBefore ? 0 : 1);
+}
+
+- (instancetype)copyWithZone:(nullable NSZone *)zone {
+  return self;
+}
+
+@end
+
+#pragma mark - FSTQuery
+
+@interface FSTQuery () {
+  // Cached value of the canonicalID property.
+  NSString *_canonicalID;
+}
+
+/**
+ * Initializes the receiver with the given query constraints.
+ *
+ * @param path The base path of the query.
+ * @param filters Filters specify which documents to include in the results.
+ * @param sortOrders The fields and directions to sort the results.
+ * @param limit If not NSNotFound, only this many results will be returned.
+ */
+- (instancetype)initWithPath:(FSTResourcePath *)path
+                    filterBy:(NSArray<id<FSTFilter>> *)filters
+                     orderBy:(NSArray<FSTSortOrder *> *)sortOrders
+                       limit:(NSInteger)limit
+                     startAt:(nullable FSTBound *)startAtBound
+                       endAt:(nullable FSTBound *)endAtBound NS_DESIGNATED_INITIALIZER;
+
+/** A list of fields given to sort by. This does not include the implicit key sort at the end. */
+@property(nonatomic, strong, readonly) NSArray<FSTSortOrder *> *explicitSortOrders;
+
+/** The memoized list of sort orders */
+@property(nonatomic, nullable, strong, readwrite) NSArray<FSTSortOrder *> *memoizedSortOrders;
+
+@end
+
+@implementation FSTQuery
+
+#pragma mark - Constructors
+
++ (instancetype)queryWithPath:(FSTResourcePath *)path {
+  return [[FSTQuery alloc] initWithPath:path
+                               filterBy:@[]
+                                orderBy:@[]
+                                  limit:NSNotFound
+                                startAt:nil
+                                  endAt:nil];
+}
+
+- (instancetype)initWithPath:(FSTResourcePath *)path
+                    filterBy:(NSArray<id<FSTFilter>> *)filters
+                     orderBy:(NSArray<FSTSortOrder *> *)sortOrders
+                       limit:(NSInteger)limit
+                     startAt:(nullable FSTBound *)startAtBound
+                       endAt:(nullable FSTBound *)endAtBound {
+  if (self = [super init]) {
+    _path = path;
+    _filters = filters;
+    _explicitSortOrders = sortOrders;
+    _limit = limit;
+    _startAt = startAtBound;
+    _endAt = endAtBound;
+  }
+  return self;
+}
+
+#pragma mark - NSObject methods
+
+- (NSString *)description {
+  return [NSString stringWithFormat:@"<FSTQuery: canonicalID:%@>", self.canonicalID];
+}
+
+- (BOOL)isEqual:(id)object {
+  if (self == object) {
+    return YES;
+  }
+  if (![object isKindOfClass:[FSTQuery class]]) {
+    return NO;
+  }
+  return [self isEqualToQuery:(FSTQuery *)object];
+}
+
+- (NSUInteger)hash {
+  return [self.canonicalID hash];
+}
+
+- (instancetype)copyWithZone:(nullable NSZone *)zone {
+  return self;
+}
+
+#pragma mark - Public methods
+
+- (NSArray *)sortOrders {
+  if (self.memoizedSortOrders == nil) {
+    FSTFieldPath *_Nullable inequalityField = [self inequalityFilterField];
+    FSTFieldPath *_Nullable firstSortOrderField = [self firstSortOrderField];
+    if (inequalityField && !firstSortOrderField) {
+      // In order to implicitly add key ordering, we must also add the inequality filter field for
+      // it to be a valid query. Note that the default inequality field and key ordering is
+      // ascending.
+      if ([inequalityField isKeyFieldPath]) {
+        self.memoizedSortOrders =
+            @[ [FSTSortOrder sortOrderWithFieldPath:[FSTFieldPath keyFieldPath] ascending:YES] ];
+      } else {
+        self.memoizedSortOrders = @[
+          [FSTSortOrder sortOrderWithFieldPath:inequalityField ascending:YES],
+          [FSTSortOrder sortOrderWithFieldPath:[FSTFieldPath keyFieldPath] ascending:YES]
+        ];
+      }
+    } else {
+      FSTAssert(!inequalityField || [inequalityField isEqual:firstSortOrderField],
+                @"First orderBy %@ should match inequality field %@.", firstSortOrderField,
+                inequalityField);
+
+      __block BOOL foundKeyOrder = NO;
+
+      NSMutableArray *result = [NSMutableArray array];
+      for (FSTSortOrder *sortOrder in self.explicitSortOrders) {
+        [result addObject:sortOrder];
+        if ([sortOrder.field isEqual:[FSTFieldPath keyFieldPath]]) {
+          foundKeyOrder = YES;
+        }
+      }
+
+      if (!foundKeyOrder) {
+        // The direction of the implicit key ordering always matches the direction of the last
+        // explicit sort order
+        BOOL lastIsAscending =
+            self.explicitSortOrders.count > 0 ? self.explicitSortOrders.lastObject.ascending : YES;
+        [result addObject:[FSTSortOrder sortOrderWithFieldPath:[FSTFieldPath keyFieldPath]
+                                                     ascending:lastIsAscending]];
+      }
+
+      self.memoizedSortOrders = result;
+    }
+  }
+  return self.memoizedSortOrders;
+}
+
+- (instancetype)queryByAddingFilter:(id<FSTFilter>)filter {
+  FSTAssert(![FSTDocumentKey isDocumentKey:self.path], @"No filtering allowed for document query");
+
+  FSTFieldPath *_Nullable newInequalityField = nil;
+  if ([filter isKindOfClass:[FSTRelationFilter class]] &&
+      [((FSTRelationFilter *)filter)isInequality]) {
+    newInequalityField = filter.field;
+  }
+  FSTFieldPath *_Nullable queryInequalityField = [self inequalityFilterField];
+  FSTAssert(!queryInequalityField || !newInequalityField ||
+                [queryInequalityField isEqual:newInequalityField],
+            @"Query must only have one inequality field.");
+
+  return [[FSTQuery alloc] initWithPath:self.path
+                               filterBy:[self.filters arrayByAddingObject:filter]
+                                orderBy:self.explicitSortOrders
+                                  limit:self.limit
+                                startAt:self.startAt
+                                  endAt:self.endAt];
+}
+
+- (instancetype)queryByAddingSortOrder:(FSTSortOrder *)sortOrder {
+  FSTAssert(![FSTDocumentKey isDocumentKey:self.path],
+            @"No ordering is allowed for a document query.");
+
+  // TODO(klimt): Validate that the same key isn't added twice.
+  return [[FSTQuery alloc] initWithPath:self.path
+                               filterBy:self.filters
+                                orderBy:[self.explicitSortOrders arrayByAddingObject:sortOrder]
+                                  limit:self.limit
+                                startAt:self.startAt
+                                  endAt:self.endAt];
+}
+
+- (instancetype)queryBySettingLimit:(NSInteger)limit {
+  return [[FSTQuery alloc] initWithPath:self.path
+                               filterBy:self.filters
+                                orderBy:self.explicitSortOrders
+                                  limit:limit
+                                startAt:self.startAt
+                                  endAt:self.endAt];
+}
+
+- (instancetype)queryByAddingStartAt:(FSTBound *)bound {
+  return [[FSTQuery alloc] initWithPath:self.path
+                               filterBy:self.filters
+                                orderBy:self.explicitSortOrders
+                                  limit:self.limit
+                                startAt:bound
+                                  endAt:self.endAt];
+}
+
+- (instancetype)queryByAddingEndAt:(FSTBound *)bound {
+  return [[FSTQuery alloc] initWithPath:self.path
+                               filterBy:self.filters
+                                orderBy:self.explicitSortOrders
+                                  limit:self.limit
+                                startAt:self.startAt
+                                  endAt:bound];
+}
+
+- (BOOL)isDocumentQuery {
+  return [FSTDocumentKey isDocumentKey:self.path] && self.filters.count == 0;
+}
+
+- (BOOL)matchesDocument:(FSTDocument *)document {
+  return [self pathMatchesDocument:document] && [self orderByMatchesDocument:document] &&
+         [self filtersMatchDocument:document] && [self boundsMatchDocument:document];
+}
+
+- (NSComparator)comparator {
+  return ^NSComparisonResult(id document1, id document2) {
+    BOOL didCompareOnKeyField = NO;
+    for (FSTSortOrder *orderBy in self.sortOrders) {
+      NSComparisonResult comp = [orderBy compareDocument:document1 toDocument:document2];
+      if (comp != NSOrderedSame) {
+        return comp;
+      }
+      didCompareOnKeyField =
+          didCompareOnKeyField || [orderBy.field isEqual:[FSTFieldPath keyFieldPath]];
+    }
+    FSTAssert(didCompareOnKeyField, @"sortOrder of query did not include key ordering");
+    return NSOrderedSame;
+  };
+}
+
+- (FSTFieldPath *_Nullable)inequalityFilterField {
+  for (id<FSTFilter> filter in self.filters) {
+    if ([filter isKindOfClass:[FSTRelationFilter class]] &&
+        ((FSTRelationFilter *)filter).filterOperator != FSTRelationFilterOperatorEqual) {
+      return filter.field;
+    }
+  }
+  return nil;
+}
+
+- (FSTFieldPath *_Nullable)firstSortOrderField {
+  return self.explicitSortOrders.firstObject.field;
+}
+
+#pragma mark - Private properties
+
+- (NSString *)canonicalID {
+  if (_canonicalID) {
+    return _canonicalID;
+  }
+
+  NSMutableString *canonicalID = [[self.path canonicalString] mutableCopy];
+
+  // Add filters.
+  [canonicalID appendString:@"|f:"];
+  for (id<FSTFilter> predicate in self.filters) {
+    [canonicalID appendFormat:@"%@", [predicate canonicalID]];
+  }
+
+  // Add order by.
+  [canonicalID appendString:@"|ob:"];
+  for (FSTSortOrder *orderBy in self.sortOrders) {
+    [canonicalID appendString:orderBy.canonicalID];
+  }
+
+  // Add limit.
+  if (self.limit != NSNotFound) {
+    [canonicalID appendFormat:@"|l:%ld", (long)self.limit];
+  }
+
+  if (self.startAt) {
+    [canonicalID appendFormat:@"|lb:%@", self.startAt.canonicalString];
+  }
+
+  if (self.endAt) {
+    [canonicalID appendFormat:@"|ub:%@", self.endAt.canonicalString];
+  }
+
+  _canonicalID = canonicalID;
+  return canonicalID;
+}
+
+#pragma mark - Private methods
+
+- (BOOL)isEqualToQuery:(FSTQuery *)other {
+  return [self.path isEqual:other.path] && self.limit == other.limit &&
+         [self.filters isEqual:other.filters] && [self.sortOrders isEqual:other.sortOrders] &&
+         (self.startAt == other.startAt || [self.startAt isEqual:other.startAt]) &&
+         (self.endAt == other.endAt || [self.endAt isEqual:other.endAt]);
+}
+
+/* Returns YES if the document matches the path for the receiver. */
+- (BOOL)pathMatchesDocument:(FSTDocument *)document {
+  FSTResourcePath *documentPath = document.key.path;
+  if ([FSTDocumentKey isDocumentKey:self.path]) {
+    // Exact match for document queries.
+    return [self.path isEqual:documentPath];
+  } else {
+    // Shallow ancestor queries by default.
+    return [self.path isPrefixOfPath:documentPath] && self.path.length == documentPath.length - 1;
+  }
+}
+
+/**
+ * A document must have a value for every ordering clause in order to show up in the results.
+ */
+- (BOOL)orderByMatchesDocument:(FSTDocument *)document {
+  for (FSTSortOrder *orderBy in self.explicitSortOrders) {
+    FSTFieldPath *fieldPath = orderBy.field;
+    // order by key always matches
+    if (![fieldPath isEqual:[FSTFieldPath keyFieldPath]] &&
+        [document fieldForPath:fieldPath] == nil) {
+      return NO;
+    }
+  }
+  return YES;
+}
+
+/** Returns YES if the document matches all of the filters in the receiver. */
+- (BOOL)filtersMatchDocument:(FSTDocument *)document {
+  for (id<FSTFilter> filter in self.filters) {
+    if (![filter matchesDocument:document]) {
+      return NO;
+    }
+  }
+  return YES;
+}
+
+- (BOOL)boundsMatchDocument:(FSTDocument *)document {
+  if (self.startAt && ![self.startAt sortsBeforeDocument:document usingSortOrder:self.sortOrders]) {
+    return NO;
+  }
+  if (self.endAt && [self.endAt sortsBeforeDocument:document usingSortOrder:self.sortOrders]) {
+    return NO;
+  }
+  return YES;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTSnapshotVersion.h b/Firestore/Source/Core/FSTSnapshotVersion.h
new file mode 100644
index 0000000..b72e4a2
--- /dev/null
+++ b/Firestore/Source/Core/FSTSnapshotVersion.h
@@ -0,0 +1,43 @@
+/*
+ * 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>
+
+NS_ASSUME_NONNULL_BEGIN
+
+@class FSTTimestamp;
+
+/**
+ * A version of a document in Firestore. This corresponds to the version timestamp, such as
+ * update_time or read_time.
+ */
+@interface FSTSnapshotVersion : NSObject <NSCopying>
+
+/** Creates a new version that is smaller than all other versions. */
++ (instancetype)noVersion;
+
+/** Creates a new version representing the given timestamp. */
++ (instancetype)versionWithTimestamp:(FSTTimestamp *)timestamp;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+- (NSComparisonResult)compare:(FSTSnapshotVersion *)other;
+
+@property(nonatomic, strong, readonly) FSTTimestamp *timestamp;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTSnapshotVersion.m b/Firestore/Source/Core/FSTSnapshotVersion.m
new file mode 100644
index 0000000..68d5d7f
--- /dev/null
+++ b/Firestore/Source/Core/FSTSnapshotVersion.m
@@ -0,0 +1,80 @@
+/*
+ * 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 "FSTSnapshotVersion.h"
+
+#import "FSTTimestamp.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTSnapshotVersion
+
++ (instancetype)noVersion {
+  static FSTSnapshotVersion *min;
+  static dispatch_once_t onceToken;
+  dispatch_once(&onceToken, ^{
+    FSTTimestamp *timestamp = [[FSTTimestamp alloc] initWithSeconds:0 nanos:0];
+    min = [FSTSnapshotVersion versionWithTimestamp:timestamp];
+  });
+  return min;
+}
+
++ (instancetype)versionWithTimestamp:(FSTTimestamp *)timestamp {
+  return [[FSTSnapshotVersion alloc] initWithTimestamp:timestamp];
+}
+
+- (instancetype)initWithTimestamp:(FSTTimestamp *)timestamp {
+  self = [super init];
+  if (self) {
+    _timestamp = timestamp;
+  }
+  return self;
+}
+
+#pragma mark - NSObject methods
+
+- (BOOL)isEqual:(id)object {
+  if (self == object) {
+    return YES;
+  }
+  if (![object isKindOfClass:[FSTSnapshotVersion class]]) {
+    return NO;
+  }
+  return [self.timestamp isEqual:((FSTSnapshotVersion *)object).timestamp];
+}
+
+- (NSUInteger)hash {
+  return self.timestamp.hash;
+}
+
+- (NSString *)description {
+  return [NSString stringWithFormat:@"<FSTSnapshotVersion: %@>", self.timestamp];
+}
+
+- (id)copyWithZone:(NSZone *_Nullable)zone {
+  // Implements NSCopying without actually copying because timestamps are immutable.
+  return self;
+}
+
+#pragma mark - Public methods
+
+- (NSComparisonResult)compare:(FSTSnapshotVersion *)other {
+  return [self.timestamp compare:other.timestamp];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTSyncEngine.h b/Firestore/Source/Core/FSTSyncEngine.h
new file mode 100644
index 0000000..1348ce1
--- /dev/null
+++ b/Firestore/Source/Core/FSTSyncEngine.h
@@ -0,0 +1,105 @@
+/*
+ * 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>
+
+#import "FSTRemoteStore.h"
+#import "FSTTypes.h"
+
+@class FSTDispatchQueue;
+@class FSTLocalStore;
+@class FSTMutation;
+@class FSTQuery;
+@class FSTRemoteEvent;
+@class FSTRemoteStore;
+@class FSTUser;
+@class FSTViewSnapshot;
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTSyncEngineDelegate
+
+/** A Delegate to be notified when the sync engine produces new view snapshots or errors. */
+@protocol FSTSyncEngineDelegate
+- (void)handleViewSnapshots:(NSArray<FSTViewSnapshot *> *)viewSnapshots;
+- (void)handleError:(NSError *)error forQuery:(FSTQuery *)query;
+@end
+
+/**
+ * SyncEngine is the central controller in the client SDK architecture. It is the glue code
+ * between the EventManager, LocalStore, and RemoteStore. Some of SyncEngine's responsibilities
+ * include:
+ * 1. Coordinating client requests and remote events between the EventManager and the local and
+ *    remote data stores.
+ * 2. Managing a View object for each query, providing the unified view between the local and
+ *    remote data stores.
+ * 3. Notifying the RemoteStore when the LocalStore has new mutations in its queue that need
+ *    sending to the backend.
+ *
+ * The SyncEngine’s methods should only ever be called by methods running on our own worker
+ * dispatch queue.
+ */
+@interface FSTSyncEngine : NSObject <FSTRemoteSyncer>
+
+- (instancetype)init NS_UNAVAILABLE;
+- (instancetype)initWithLocalStore:(FSTLocalStore *)localStore
+                       remoteStore:(FSTRemoteStore *)remoteStore
+                       initialUser:(FSTUser *)user NS_DESIGNATED_INITIALIZER;
+
+/**
+ * A delegate to be notified when queries being listened to produce new view snapshots or
+ * errors.
+ */
+@property(nonatomic, weak) id<FSTSyncEngineDelegate> delegate;
+
+/**
+ * Initiates a new listen. The FSTLocalStore will be queried for initial data and the listen will
+ * be sent to the FSTRemoteStore to get remote data. The registered FSTSyncEngineDelegate will be
+ * notified of resulting view snapshots and/or listen errors.
+ *
+ * @return the target ID assigned to the query.
+ */
+- (FSTTargetID)listenToQuery:(FSTQuery *)query;
+
+/** Stops listening to a query previously listened to via listenToQuery:. */
+- (void)stopListeningToQuery:(FSTQuery *)query;
+
+/**
+ * Initiates the write of local mutation batch which involves adding the writes to the mutation
+ * queue, notifying the remote store about new mutations, and raising events for any changes this
+ * write caused. The provided completion block will be called once the write has been acked or
+ * rejected by the backend (or failed locally for any other reason).
+ */
+- (void)writeMutations:(NSArray<FSTMutation *> *)mutations completion:(FSTVoidErrorBlock)completion;
+
+/**
+ * Runs the given transaction block up to retries times and then calls completion.
+ *
+ * @param retries The number of times to try before giving up.
+ * @param workerDispatchQueue The queue to dispatch sync engine calls to.
+ * @param updateBlock The block to call to execute the user's transaction.
+ * @param completion The block to call when the transaction is finished or failed.
+ */
+- (void)transactionWithRetries:(int)retries
+           workerDispatchQueue:(FSTDispatchQueue *)workerDispatchQueue
+                   updateBlock:(FSTTransactionBlock)updateBlock
+                    completion:(FSTVoidIDErrorBlock)completion;
+
+- (void)userDidChange:(FSTUser *)user;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTSyncEngine.m b/Firestore/Source/Core/FSTSyncEngine.m
new file mode 100644
index 0000000..8698a97
--- /dev/null
+++ b/Firestore/Source/Core/FSTSyncEngine.m
@@ -0,0 +1,520 @@
+/*
+ * 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 "FSTSyncEngine.h"
+
+#import <GRPCClient/GRPCCall.h>
+
+#import "FIRFirestoreErrors.h"
+#import "FSTAssert.h"
+#import "FSTDispatchQueue.h"
+#import "FSTDocument.h"
+#import "FSTDocumentKey.h"
+#import "FSTDocumentSet.h"
+#import "FSTEagerGarbageCollector.h"
+#import "FSTLocalStore.h"
+#import "FSTLocalViewChanges.h"
+#import "FSTLocalWriteResult.h"
+#import "FSTLogger.h"
+#import "FSTMutationBatch.h"
+#import "FSTQuery.h"
+#import "FSTQueryData.h"
+#import "FSTReferenceSet.h"
+#import "FSTRemoteEvent.h"
+#import "FSTSnapshotVersion.h"
+#import "FSTTargetIDGenerator.h"
+#import "FSTTransaction.h"
+#import "FSTUser.h"
+#import "FSTView.h"
+#import "FSTViewSnapshot.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTQueryView
+
+/**
+ * FSTQueryView contains all of the info that FSTSyncEngine needs to track for a particular
+ * query and view.
+ */
+@interface FSTQueryView : NSObject
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                     targetID:(FSTTargetID)targetID
+                  resumeToken:(NSData *)resumeToken
+                         view:(FSTView *)view NS_DESIGNATED_INITIALIZER;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** The query itself. */
+@property(nonatomic, strong, readonly) FSTQuery *query;
+
+/** The targetID created by the client that is used in the watch stream to identify this query. */
+@property(nonatomic, assign, readonly) FSTTargetID targetID;
+
+/**
+ * An identifier from the datastore backend that indicates the last state of the results that
+ * was received. This can be used to indicate where to continue receiving new doc changes for the
+ * query.
+ */
+@property(nonatomic, copy, readonly) NSData *resumeToken;
+
+/**
+ * The view is responsible for computing the final merged truth of what docs are in the query.
+ * It gets notified of local and remote changes, and applies the query filters and limits to
+ * determine the most correct possible results.
+ */
+@property(nonatomic, strong, readonly) FSTView *view;
+
+@end
+
+@implementation FSTQueryView
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                     targetID:(FSTTargetID)targetID
+                  resumeToken:(NSData *)resumeToken
+                         view:(FSTView *)view {
+  if (self = [super init]) {
+    _query = query;
+    _targetID = targetID;
+    _resumeToken = resumeToken;
+    _view = view;
+  }
+  return self;
+}
+
+@end
+
+#pragma mark - FSTSyncEngine
+
+@interface FSTSyncEngine ()
+
+/** The local store, used to persist mutations and cached documents. */
+@property(nonatomic, strong, readonly) FSTLocalStore *localStore;
+
+/** The remote store for sending writes, watches, etc. to the backend. */
+@property(nonatomic, strong, readonly) FSTRemoteStore *remoteStore;
+
+/** FSTQueryViews for all active queries, indexed by query. */
+@property(nonatomic, strong, readonly)
+    NSMutableDictionary<FSTQuery *, FSTQueryView *> *queryViewsByQuery;
+
+/** FSTQueryViews for all active queries, indexed by target ID. */
+@property(nonatomic, strong, readonly)
+    NSMutableDictionary<NSNumber *, FSTQueryView *> *queryViewsByTarget;
+
+/**
+ * When a document is in limbo, we create a special listen to resolve it. This maps the
+ * FSTDocumentKey of each limbo document to the FSTTargetID of the listen resolving it.
+ */
+@property(nonatomic, strong, readonly)
+    NSMutableDictionary<FSTDocumentKey *, FSTBoxedTargetID *> *limboTargetsByKey;
+
+/** The inverse of limboTargetsByKey, a map of FSTTargetID to the key of the limbo doc. */
+@property(nonatomic, strong, readonly)
+    NSMutableDictionary<FSTBoxedTargetID *, FSTDocumentKey *> *limboKeysByTarget;
+
+/** Used to track any documents that are currently in limbo. */
+@property(nonatomic, strong, readonly) FSTReferenceSet *limboDocumentRefs;
+
+/** The garbage collector used to collect documents that are no longer in limbo. */
+@property(nonatomic, strong, readonly) FSTEagerGarbageCollector *limboCollector;
+
+/** Stores user completion blocks, indexed by user and FSTBatchID. */
+@property(nonatomic, strong)
+    NSMutableDictionary<FSTUser *, NSMutableDictionary<NSNumber *, FSTVoidErrorBlock> *>
+        *mutationCompletionBlocks;
+
+/** Used for creating the FSTTargetIDs for the listens used to resolve limbo documents. */
+@property(nonatomic, strong, readonly) FSTTargetIDGenerator *targetIdGenerator;
+
+@property(nonatomic, strong) FSTUser *currentUser;
+
+@end
+
+@implementation FSTSyncEngine
+
+- (instancetype)initWithLocalStore:(FSTLocalStore *)localStore
+                       remoteStore:(FSTRemoteStore *)remoteStore
+                       initialUser:(FSTUser *)initialUser {
+  if (self = [super init]) {
+    _localStore = localStore;
+    _remoteStore = remoteStore;
+
+    _queryViewsByQuery = [NSMutableDictionary dictionary];
+    _queryViewsByTarget = [NSMutableDictionary dictionary];
+
+    _limboTargetsByKey = [NSMutableDictionary dictionary];
+    _limboKeysByTarget = [NSMutableDictionary dictionary];
+    _limboCollector = [[FSTEagerGarbageCollector alloc] init];
+    _limboDocumentRefs = [[FSTReferenceSet alloc] init];
+    [_limboCollector addGarbageSource:_limboDocumentRefs];
+
+    _mutationCompletionBlocks = [NSMutableDictionary dictionary];
+    _targetIdGenerator = [FSTTargetIDGenerator generatorForSyncEngineStartingAfterID:0];
+    _currentUser = initialUser;
+  }
+  return self;
+}
+
+- (FSTTargetID)listenToQuery:(FSTQuery *)query {
+  [self assertDelegateExistsForSelector:_cmd];
+  FSTAssert(self.queryViewsByQuery[query] == nil, @"We already listen to query: %@", query);
+
+  FSTQueryData *queryData = [self.localStore allocateQuery:query];
+  FSTDocumentDictionary *docs = [self.localStore executeQuery:query];
+  FSTDocumentKeySet *remoteKeys = [self.localStore remoteDocumentKeysForTarget:queryData.targetID];
+
+  FSTView *view = [[FSTView alloc] initWithQuery:query remoteDocuments:remoteKeys];
+  FSTViewDocumentChanges *viewDocChanges = [view computeChangesWithDocuments:docs];
+  FSTViewChange *viewChange = [view applyChangesToDocuments:viewDocChanges];
+  FSTAssert(viewChange.limboChanges.count == 0,
+            @"View returned limbo docs before target ack from the server.");
+
+  FSTQueryView *queryView = [[FSTQueryView alloc] initWithQuery:query
+                                                       targetID:queryData.targetID
+                                                    resumeToken:queryData.resumeToken
+                                                           view:view];
+  self.queryViewsByQuery[query] = queryView;
+  self.queryViewsByTarget[@(queryData.targetID)] = queryView;
+  [self.delegate handleViewSnapshots:@[ viewChange.snapshot ]];
+
+  [self.remoteStore listenToTargetWithQueryData:queryData];
+  return queryData.targetID;
+}
+
+- (void)stopListeningToQuery:(FSTQuery *)query {
+  [self assertDelegateExistsForSelector:_cmd];
+
+  FSTQueryView *queryView = self.queryViewsByQuery[query];
+  FSTAssert(queryView, @"Trying to stop listening to a query not found");
+
+  [self.localStore releaseQuery:query];
+  [self.remoteStore stopListeningToTargetID:queryView.targetID];
+  [self removeAndCleanupQuery:queryView];
+  [self.localStore collectGarbage];
+}
+
+- (void)writeMutations:(NSArray<FSTMutation *> *)mutations
+            completion:(FSTVoidErrorBlock)completion {
+  [self assertDelegateExistsForSelector:_cmd];
+
+  FSTLocalWriteResult *result = [self.localStore locallyWriteMutations:mutations];
+  [self addMutationCompletionBlock:completion batchID:result.batchID];
+
+  [self emitNewSnapshotsWithChanges:result.changes remoteEvent:nil];
+  [self.remoteStore fillWritePipeline];
+}
+
+- (void)addMutationCompletionBlock:(FSTVoidErrorBlock)completion batchID:(FSTBatchID)batchID {
+  NSMutableDictionary<NSNumber *, FSTVoidErrorBlock> *completionBlocks =
+      self.mutationCompletionBlocks[self.currentUser];
+  if (!completionBlocks) {
+    completionBlocks = [NSMutableDictionary dictionary];
+    self.mutationCompletionBlocks[self.currentUser] = completionBlocks;
+  }
+  [completionBlocks setObject:completion forKey:@(batchID)];
+}
+
+/**
+ * Takes an updateBlock in which a set of reads and writes can be performed atomically. In the
+ * updateBlock, user code can read and write values using a transaction object. After the
+ * updateBlock, all changes will be committed. If someone else has changed any of the data
+ * referenced, then the updateBlock will be called again. If the updateBlock still fails after the
+ * given number of retries, then the transaction will be rejected.
+ *
+ * The transaction object passed to the updateBlock contains methods for accessing documents
+ * and collections. Unlike other firestore access, data accessed with the transaction will not
+ * reflect local changes that have not been committed. For this reason, it is required that all
+ * reads are performed before any writes. Transactions must be performed while online.
+ */
+- (void)transactionWithRetries:(int)retries
+           workerDispatchQueue:(FSTDispatchQueue *)workerDispatchQueue
+                   updateBlock:(FSTTransactionBlock)updateBlock
+                    completion:(FSTVoidIDErrorBlock)completion {
+  [workerDispatchQueue verifyIsCurrentQueue];
+  FSTAssert(retries >= 0, @"Got negative number of retries for transaction");
+  FSTTransaction *transaction = [self.remoteStore transaction];
+  updateBlock(transaction, ^(id _Nullable result, NSError *_Nullable error) {
+    [workerDispatchQueue dispatchAsync:^{
+      if (error) {
+        completion(nil, error);
+        return;
+      }
+      [transaction commitWithCompletion:^(NSError *_Nullable transactionError) {
+        if (!transactionError) {
+          completion(result, nil);
+          return;
+        }
+        // TODO(b/35201829): Only retry on real transaction failures.
+        if (retries == 0) {
+          NSError *wrappedError =
+              [NSError errorWithDomain:FIRFirestoreErrorDomain
+                                  code:FIRFirestoreErrorCodeFailedPrecondition
+                              userInfo:@{
+                                NSLocalizedDescriptionKey : @"Transaction failed all retries.",
+                                NSUnderlyingErrorKey : transactionError
+                              }];
+          completion(nil, wrappedError);
+          return;
+        }
+        [workerDispatchQueue verifyIsCurrentQueue];
+        return [self transactionWithRetries:(retries - 1)
+                        workerDispatchQueue:workerDispatchQueue
+                                updateBlock:updateBlock
+                                 completion:completion];
+      }];
+    }];
+  });
+}
+
+- (void)applyRemoteEvent:(FSTRemoteEvent *)remoteEvent {
+  [self assertDelegateExistsForSelector:_cmd];
+
+  // Make sure limbo documents are deleted if there were no results
+  [remoteEvent.targetChanges enumerateKeysAndObjectsUsingBlock:^(
+                                 FSTBoxedTargetID *_Nonnull targetID,
+                                 FSTTargetChange *_Nonnull targetChange, BOOL *_Nonnull stop) {
+    FSTDocumentKey *limboKey = self.limboKeysByTarget[targetID];
+    if (limboKey && targetChange.currentStatusUpdate == FSTCurrentStatusUpdateMarkCurrent &&
+        remoteEvent.documentUpdates[limboKey] == nil) {
+      // When listening to a query the server responds with a snapshot containing documents
+      // matching the query and a current marker telling us we're now in sync. It's possible for
+      // these to arrive as separate remote events or as a single remote event. For a document
+      // query, there will be no documents sent in the response if the document doesn't exist.
+      //
+      // If the snapshot arrives separately from the current marker, we handle it normally and
+      // updateTrackedLimboDocumentsWithChanges:targetID: will resolve the limbo status of the
+      // document, removing it from limboDocumentRefs. This works because clients only initiate
+      // limbo resolution when a target is current and because all current targets are always at a
+      // consistent snapshot.
+      //
+      // However, if the document doesn't exist and the current marker arrives, the document is
+      // not present in the snapshot and our normal view handling would consider the document to
+      // remain in limbo indefinitely because there are no updates to the document. To avoid this,
+      // we specially handle this just this case here: synthesizing a delete.
+      //
+      // TODO(dimond): Ideally we would have an explicit lookup query instead resulting in an
+      // explicit delete message and we could remove this special logic.
+      [remoteEvent
+          addDocumentUpdate:[FSTDeletedDocument documentWithKey:limboKey
+                                                        version:remoteEvent.snapshotVersion]];
+    }
+  }];
+
+  FSTMaybeDocumentDictionary *changes = [self.localStore applyRemoteEvent:remoteEvent];
+  [self emitNewSnapshotsWithChanges:changes remoteEvent:remoteEvent];
+}
+
+- (void)rejectListenWithTargetID:(FSTBoxedTargetID *)targetID error:(NSError *)error {
+  [self assertDelegateExistsForSelector:_cmd];
+
+  FSTDocumentKey *limboKey = self.limboKeysByTarget[targetID];
+  if (limboKey) {
+    // Since this query failed, we won't want to manually unlisten to it.
+    // So go ahead and remove it from bookkeeping.
+    [self.limboTargetsByKey removeObjectForKey:limboKey];
+    [self.limboKeysByTarget removeObjectForKey:targetID];
+
+    // TODO(dimond): Retry on transient errors?
+
+    // It's a limbo doc. Create a synthetic event saying it was deleted. This is kind of a hack.
+    // Ideally, we would have a method in the local store to purge a document. However, it would
+    // be tricky to keep all of the local store's invariants with another method.
+    NSMutableDictionary<NSNumber *, FSTTargetChange *> *targetChanges =
+        [NSMutableDictionary dictionary];
+    FSTDeletedDocument *doc =
+        [FSTDeletedDocument documentWithKey:limboKey version:[FSTSnapshotVersion noVersion]];
+    NSMutableDictionary<FSTDocumentKey *, FSTMaybeDocument *> *docUpdate =
+        [NSMutableDictionary dictionaryWithObject:doc forKey:limboKey];
+    FSTRemoteEvent *event = [FSTRemoteEvent eventWithSnapshotVersion:[FSTSnapshotVersion noVersion]
+                                                       targetChanges:targetChanges
+                                                     documentUpdates:docUpdate];
+    [self applyRemoteEvent:event];
+  } else {
+    FSTQueryView *queryView = self.queryViewsByTarget[targetID];
+    FSTAssert(queryView, @"Unknown targetId: %@", targetID);
+    [self.localStore releaseQuery:queryView.query];
+    [self removeAndCleanupQuery:queryView];
+    [self.delegate handleError:error forQuery:queryView.query];
+  }
+}
+
+- (void)applySuccessfulWriteWithResult:(FSTMutationBatchResult *)batchResult {
+  [self assertDelegateExistsForSelector:_cmd];
+
+  // The local store may or may not be able to apply the write result and raise events immediately
+  // (depending on whether the watcher is caught up), so we raise user callbacks first so that they
+  // consistently happen before listen events.
+  [self processUserCallbacksForBatchID:batchResult.batch.batchID error:nil];
+
+  FSTMaybeDocumentDictionary *changes = [self.localStore acknowledgeBatchWithResult:batchResult];
+  [self emitNewSnapshotsWithChanges:changes remoteEvent:nil];
+}
+
+- (void)rejectFailedWriteWithBatchID:(FSTBatchID)batchID error:(NSError *)error {
+  [self assertDelegateExistsForSelector:_cmd];
+
+  // The local store may or may not be able to apply the write result and raise events immediately
+  // (depending on whether the watcher is caught up), so we raise user callbacks first so that they
+  // consistently happen before listen events.
+  [self processUserCallbacksForBatchID:batchID error:error];
+
+  FSTMaybeDocumentDictionary *changes = [self.localStore rejectBatchID:batchID];
+  [self emitNewSnapshotsWithChanges:changes remoteEvent:nil];
+}
+
+- (void)processUserCallbacksForBatchID:(FSTBatchID)batchID error:(NSError *_Nullable)error {
+  NSMutableDictionary<NSNumber *, FSTVoidErrorBlock> *completionBlocks =
+      self.mutationCompletionBlocks[self.currentUser];
+
+  // NOTE: Mutations restored from persistence won't have completion blocks, so it's okay for
+  // this (or the completion below) to be nil.
+  if (completionBlocks) {
+    NSNumber *boxedBatchID = @(batchID);
+    FSTVoidErrorBlock completion = completionBlocks[boxedBatchID];
+    if (completion) {
+      completion(error);
+      [completionBlocks removeObjectForKey:boxedBatchID];
+    }
+  }
+}
+
+- (void)assertDelegateExistsForSelector:(SEL)methodSelector {
+  FSTAssert(self.delegate, @"Tried to call '%@' before delegate was registered.",
+            NSStringFromSelector(methodSelector));
+}
+
+- (void)removeAndCleanupQuery:(FSTQueryView *)queryView {
+  [self.queryViewsByQuery removeObjectForKey:queryView.query];
+  [self.queryViewsByTarget removeObjectForKey:@(queryView.targetID)];
+
+  [self.limboDocumentRefs removeReferencesForID:queryView.targetID];
+  [self garbageCollectLimboDocuments];
+}
+
+/**
+ * Computes a new snapshot from the changes and calls the registered callback with the new snapshot.
+ */
+- (void)emitNewSnapshotsWithChanges:(FSTMaybeDocumentDictionary *)changes
+                        remoteEvent:(FSTRemoteEvent *_Nullable)remoteEvent {
+  NSMutableArray<FSTViewSnapshot *> *newSnapshots = [NSMutableArray array];
+  NSMutableArray<FSTLocalViewChanges *> *documentChangesInAllViews = [NSMutableArray array];
+
+  [self.queryViewsByQuery
+      enumerateKeysAndObjectsUsingBlock:^(FSTQuery *query, FSTQueryView *queryView, BOOL *stop) {
+        FSTView *view = queryView.view;
+        FSTViewDocumentChanges *viewDocChanges = [view computeChangesWithDocuments:changes];
+        if (viewDocChanges.needsRefill) {
+          // The query has a limit and some docs were removed/updated, so we need to re-run the
+          // query against the local store to make sure we didn't lose any good docs that had been
+          // past the limit.
+          FSTDocumentDictionary *docs = [self.localStore executeQuery:queryView.query];
+          viewDocChanges = [view computeChangesWithDocuments:docs previousChanges:viewDocChanges];
+        }
+        FSTTargetChange *_Nullable targetChange = remoteEvent.targetChanges[@(queryView.targetID)];
+        FSTViewChange *viewChange =
+            [queryView.view applyChangesToDocuments:viewDocChanges targetChange:targetChange];
+
+        [self updateTrackedLimboDocumentsWithChanges:viewChange.limboChanges
+                                            targetID:queryView.targetID];
+
+        if (viewChange.snapshot) {
+          [newSnapshots addObject:viewChange.snapshot];
+          FSTLocalViewChanges *docChanges =
+              [FSTLocalViewChanges changesForViewSnapshot:viewChange.snapshot];
+          [documentChangesInAllViews addObject:docChanges];
+        }
+      }];
+
+  [self.delegate handleViewSnapshots:newSnapshots];
+  [self.localStore notifyLocalViewChanges:documentChangesInAllViews];
+  [self.localStore collectGarbage];
+}
+
+/** Updates the limbo document state for the given targetID. */
+- (void)updateTrackedLimboDocumentsWithChanges:(NSArray<FSTLimboDocumentChange *> *)limboChanges
+                                      targetID:(FSTTargetID)targetID {
+  for (FSTLimboDocumentChange *limboChange in limboChanges) {
+    switch (limboChange.type) {
+      case FSTLimboDocumentChangeTypeAdded:
+        [self.limboDocumentRefs addReferenceToKey:limboChange.key forID:targetID];
+        [self trackLimboChange:limboChange];
+        break;
+
+      case FSTLimboDocumentChangeTypeRemoved:
+        FSTLog(@"Document no longer in limbo: %@", limboChange.key);
+        [self.limboDocumentRefs removeReferenceToKey:limboChange.key forID:targetID];
+        break;
+
+      default:
+        FSTFail(@"Unknown limbo change type: %ld", (long)limboChange.type);
+    }
+  }
+  [self garbageCollectLimboDocuments];
+}
+
+- (void)trackLimboChange:(FSTLimboDocumentChange *)limboChange {
+  FSTDocumentKey *key = limboChange.key;
+
+  if (!self.limboTargetsByKey[key]) {
+    FSTLog(@"New document in limbo: %@", key);
+    FSTTargetID limboTargetID = [self.targetIdGenerator nextID];
+    FSTQuery *query = [FSTQuery queryWithPath:key.path];
+    FSTQueryData *queryData = [[FSTQueryData alloc] initWithQuery:query
+                                                         targetID:limboTargetID
+                                                          purpose:FSTQueryPurposeLimboResolution];
+    self.limboKeysByTarget[@(limboTargetID)] = key;
+    [self.remoteStore listenToTargetWithQueryData:queryData];
+    self.limboTargetsByKey[key] = @(limboTargetID);
+  }
+}
+
+/** Garbage collect the limbo documents that we no longer need to track. */
+- (void)garbageCollectLimboDocuments {
+  NSSet<FSTDocumentKey *> *garbage = [self.limboCollector collectGarbage];
+  for (FSTDocumentKey *key in garbage) {
+    FSTBoxedTargetID *limboTarget = self.limboTargetsByKey[key];
+    if (!limboTarget) {
+      // This target already got removed, because the query failed.
+      return;
+    }
+    FSTTargetID limboTargetID = limboTarget.intValue;
+    [self.remoteStore stopListeningToTargetID:limboTargetID];
+    [self.limboTargetsByKey removeObjectForKey:key];
+    [self.limboKeysByTarget removeObjectForKey:limboTarget];
+  }
+}
+
+// Used for testing
+- (NSDictionary<FSTDocumentKey *, FSTBoxedTargetID *> *)currentLimboDocuments {
+  // Return defensive copy
+  return [self.limboTargetsByKey copy];
+}
+
+- (void)userDidChange:(FSTUser *)user {
+  self.currentUser = user;
+
+  // Notify local store and emit any resulting events from swapping out the mutation queue.
+  FSTMaybeDocumentDictionary *changes = [self.localStore userDidChange:user];
+  [self emitNewSnapshotsWithChanges:changes remoteEvent:nil];
+
+  // Notify remote store so it can restart its streams.
+  [self.remoteStore userDidChange:user];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTTargetIDGenerator.h b/Firestore/Source/Core/FSTTargetIDGenerator.h
new file mode 100644
index 0000000..5b9db10
--- /dev/null
+++ b/Firestore/Source/Core/FSTTargetIDGenerator.h
@@ -0,0 +1,55 @@
+/*
+ * 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>
+
+#import "FSTTypes.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * FSTTargetIDGenerator generates monotonically increasing integer IDs. There are separate
+ * generators for different scopes. While these generators will operate independently of each
+ * other, they are scoped, such that no two generators will ever produce the same ID. This is
+ * useful, because sometimes the backend may group IDs from separate parts of the client into the
+ * same ID space.
+ */
+@interface FSTTargetIDGenerator : NSObject
+
+/**
+ * Creates and returns the FSTTargetIDGenerator for the local store.
+ *
+ * @param after An ID to start at. Every call to nextID will return an ID > @a after.
+ * @return A shared instance of FSTTargetIDGenerator.
+ */
++ (instancetype)generatorForLocalStoreStartingAfterID:(FSTTargetID)after;
+
+/**
+ * Creates and returns the FSTTargetIDGenerator for the sync engine.
+ *
+ * @param after An ID to start at. Every call to nextID will return an ID > @a after.
+ * @return A shared instance of FSTTargetIDGenerator.
+ */
++ (instancetype)generatorForSyncEngineStartingAfterID:(FSTTargetID)after;
+
+- (id)init __attribute__((unavailable("Use a static constructor method.")));
+
+/** Returns the next ID in the sequence. */
+- (FSTTargetID)nextID;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTTargetIDGenerator.m b/Firestore/Source/Core/FSTTargetIDGenerator.m
new file mode 100644
index 0000000..86ded30
--- /dev/null
+++ b/Firestore/Source/Core/FSTTargetIDGenerator.m
@@ -0,0 +1,105 @@
+/*
+ * 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 "FSTTargetIDGenerator.h"
+
+#import <libkern/OSAtomic.h>
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTTargetIDGenerator
+
+static const int kReservedBits = 1;
+
+/** FSTTargetIDGeneratorID is the set of all valid generators. */
+typedef NS_ENUM(NSInteger, FSTTargetIDGeneratorID) {
+  FSTTargetIDGeneratorIDLocalStore = 0,
+  FSTTargetIDGeneratorIDSyncEngine = 1
+};
+
+@interface FSTTargetIDGenerator () {
+  // This is volatile so it can be used with OSAtomicAdd32.
+  volatile FSTTargetID _previousID;
+}
+
+/**
+ * Initializes the generator.
+ *
+ * @param generatorID A unique ID indicating which generator this is.
+ * @param after Every call to nextID will return a number > @a after.
+ */
+- (instancetype)initWithGeneratorID:(FSTTargetIDGeneratorID)generatorID
+                    startingAfterID:(FSTTargetID)after NS_DESIGNATED_INITIALIZER;
+
+// This is typed as FSTTargetID because we need to do bitwise operations with them together.
+@property(nonatomic, assign) FSTTargetID generatorID;
+@end
+
+@implementation FSTTargetIDGenerator
+
+#pragma mark - Constructors
+
+- (instancetype)initWithGeneratorID:(FSTTargetIDGeneratorID)generatorID
+                    startingAfterID:(FSTTargetID)after {
+  self = [super init];
+  if (self) {
+    _generatorID = generatorID;
+
+    // Replace the generator part of |after| with this generator's ID.
+    FSTTargetID afterWithoutGenerator = (after >> kReservedBits) << kReservedBits;
+    FSTTargetID afterGenerator = after - afterWithoutGenerator;
+    if (afterGenerator >= _generatorID) {
+      // For example, if:
+      //   self.generatorID = 0b0000
+      //   after = 0b1011
+      //   afterGenerator = 0b0001
+      // Then:
+      //   previous = 0b1010
+      //   next = 0b1100
+      _previousID = afterWithoutGenerator | self.generatorID;
+    } else {
+      // For example, if:
+      //   self.generatorID = 0b0001
+      //   after = 0b1010
+      //   afterGenerator = 0b0000
+      // Then:
+      //   previous = 0b1001
+      //   next = 0b1011
+      _previousID = (afterWithoutGenerator | self.generatorID) - (1 << kReservedBits);
+    }
+  }
+  return self;
+}
+
++ (instancetype)generatorForLocalStoreStartingAfterID:(FSTTargetID)after {
+  return [[FSTTargetIDGenerator alloc] initWithGeneratorID:FSTTargetIDGeneratorIDLocalStore
+                                           startingAfterID:after];
+}
+
++ (instancetype)generatorForSyncEngineStartingAfterID:(FSTTargetID)after {
+  return [[FSTTargetIDGenerator alloc] initWithGeneratorID:FSTTargetIDGeneratorIDSyncEngine
+                                           startingAfterID:after];
+}
+
+#pragma mark - Public methods
+
+- (FSTTargetID)nextID {
+  return OSAtomicAdd32(1 << kReservedBits, &_previousID);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTTimestamp.h b/Firestore/Source/Core/FSTTimestamp.h
new file mode 100644
index 0000000..f86779d
--- /dev/null
+++ b/Firestore/Source/Core/FSTTimestamp.h
@@ -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 <Foundation/Foundation.h>
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * An FSTTimestamp represents an absolute time from the backend at up to nanosecond precision.
+ * An FSTTimestamp is represented in terms of UTC and does not have an associated timezone.
+ */
+@interface FSTTimestamp : NSObject <NSCopying>
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/**
+ * Creates a new timestamp.
+ *
+ * @param seconds the number of seconds since epoch.
+ * @param nanos the number of nanoseconds after the seconds.
+ */
+- (instancetype)initWithSeconds:(int64_t)seconds nanos:(int32_t)nanos NS_DESIGNATED_INITIALIZER;
+
+/** Creates a new timestamp with the current date / time. */
++ (instancetype)timestamp;
+
+/** Creates a new timestamp from the given date. */
++ (instancetype)timestampWithDate:(NSDate *)date;
+
+/** Returns a new NSDate corresponding to this timestamp. This may lose precision. */
+- (NSDate *)approximateDateValue;
+
+/**
+ * Converts the given date to a an ISO 8601 timestamp string, useful for rendering in JSON.
+ *
+ * ISO 8601 dates times in UTC look like this: "1912-04-14T23:40:00.000000000Z".
+ *
+ * @see http://www.ecma-international.org/ecma-262/6.0/#sec-date-time-string-format
+ */
+- (NSString *)ISO8601String;
+
+- (NSComparisonResult)compare:(FSTTimestamp *)other;
+
+/**
+ * Represents seconds of UTC time since Unix epoch 1970-01-01T00:00:00Z.
+ * Must be from 0001-01-01T00:00:00Z to 9999-12-31T23:59:59Z inclusive.
+ */
+@property(nonatomic, assign, readonly) int64_t seconds;
+
+/**
+ * Non-negative fractions of a second at nanosecond resolution. Negative second values with
+ * fractions must still have non-negative nanos values that count forward in time.
+ * Must be from 0 to 999,999,999 inclusive.
+ */
+@property(nonatomic, assign, readonly) int32_t nanos;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTTimestamp.m b/Firestore/Source/Core/FSTTimestamp.m
new file mode 100644
index 0000000..941217a
--- /dev/null
+++ b/Firestore/Source/Core/FSTTimestamp.m
@@ -0,0 +1,122 @@
+/*
+ * 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 "FSTTimestamp.h"
+
+#import "FSTAssert.h"
+#import "FSTComparison.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+static const int kNanosPerSecond = 1000000000;
+
+@implementation FSTTimestamp
+
+#pragma mark - Constructors
+
++ (instancetype)timestamp {
+  return [FSTTimestamp timestampWithDate:[NSDate date]];
+}
+
++ (instancetype)timestampWithDate:(NSDate *)date {
+  double secondsDouble;
+  double fraction = modf(date.timeIntervalSince1970, &secondsDouble);
+  // GCP Timestamps always have non-negative nanos.
+  if (fraction < 0) {
+    fraction += 1.0;
+    secondsDouble -= 1.0;
+  }
+  int64_t seconds = (int64_t)secondsDouble;
+  int32_t nanos = (int32_t)(fraction * kNanosPerSecond);
+  return [[FSTTimestamp alloc] initWithSeconds:seconds nanos:nanos];
+}
+
+- (instancetype)initWithSeconds:(int64_t)seconds nanos:(int32_t)nanos {
+  self = [super init];
+  if (self) {
+    FSTAssert(nanos >= 0, @"timestamp nanoseconds out of range: %d", nanos);
+    FSTAssert(nanos < 1e9, @"timestamp nanoseconds out of range: %d", nanos);
+    // Midnight at the beginning of 1/1/1 is the earliest timestamp Firestore supports.
+    FSTAssert(seconds >= -62135596800L, @"timestamp seconds out of range: %lld", seconds);
+    // This will break in the year 10,000.
+    FSTAssert(seconds < 253402300800L, @"timestamp seconds out of range: %lld", seconds);
+
+    _seconds = seconds;
+    _nanos = nanos;
+  }
+  return self;
+}
+
+#pragma mark - NSObject methods
+
+- (BOOL)isEqual:(id)object {
+  if (self == object) {
+    return YES;
+  }
+  if (![object isKindOfClass:[FSTTimestamp class]]) {
+    return NO;
+  }
+  return [self isEqualToTimestamp:(FSTTimestamp *)object];
+}
+
+- (NSUInteger)hash {
+  return (NSUInteger)((self.seconds >> 32) ^ self.seconds ^ self.nanos);
+}
+
+- (NSString *)description {
+  return [NSString
+      stringWithFormat:@"<FSTTimestamp: seconds=%lld nanos=%d>", self.seconds, self.nanos];
+}
+
+/** Implements NSCopying without actually copying because timestamps are immutable. */
+- (id)copyWithZone:(NSZone *_Nullable)zone {
+  return self;
+}
+
+#pragma mark - Public methods
+
+- (NSDate *)approximateDateValue {
+  NSTimeInterval interval = (NSTimeInterval)self.seconds + ((NSTimeInterval)self.nanos) / 1e9;
+  return [NSDate dateWithTimeIntervalSince1970:interval];
+}
+
+- (BOOL)isEqualToTimestamp:(FSTTimestamp *)other {
+  return [self compare:other] == NSOrderedSame;
+}
+
+- (NSString *)ISO8601String {
+  NSDateFormatter *formatter = [[NSDateFormatter alloc] init];
+  formatter.dateFormat = @"yyyy-MM-dd'T'HH:mm:ss";
+  formatter.timeZone = [NSTimeZone timeZoneWithName:@"UTC"];
+  NSDate *secondsDate = [NSDate dateWithTimeIntervalSince1970:self.seconds];
+  NSString *secondsString = [formatter stringFromDate:secondsDate];
+  FSTAssert(secondsString.length == 19, @"Invalid ISO string: %@", secondsString);
+
+  NSString *nanosString = [NSString stringWithFormat:@"%09d", self.nanos];
+  return [NSString stringWithFormat:@"%@.%@Z", secondsString, nanosString];
+}
+
+- (NSComparisonResult)compare:(FSTTimestamp *)other {
+  NSComparisonResult result = FSTCompareInt64s(self.seconds, other.seconds);
+  if (result != NSOrderedSame) {
+    return result;
+  }
+  return FSTCompareInt32s(self.nanos, other.nanos);
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTTransaction.h b/Firestore/Source/Core/FSTTransaction.h
new file mode 100644
index 0000000..7fa3a10
--- /dev/null
+++ b/Firestore/Source/Core/FSTTransaction.h
@@ -0,0 +1,73 @@
+/*
+ * 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>
+
+#import "FSTTypes.h"
+
+@class FIRSetOptions;
+@class FSTDatastore;
+@class FSTDocumentKey;
+@class FSTFieldMask;
+@class FSTFieldTransform;
+@class FSTMaybeDocument;
+@class FSTObjectValue;
+@class FSTParsedSetData;
+@class FSTParsedUpdateData;
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTTransaction
+
+/** Provides APIs to use in a transaction context. */
+@interface FSTTransaction : NSObject
+
+/** Creates a new transaction object, which can only be used for one transaction attempt. **/
++ (instancetype)transactionWithDatastore:(FSTDatastore *)datastore;
+
+/**
+ * Takes a set of keys and asynchronously attempts to fetch all the documents from the backend,
+ * ignoring any local changes.
+ */
+- (void)lookupDocumentsForKeys:(NSArray<FSTDocumentKey *> *)keys
+                    completion:(FSTVoidMaybeDocumentArrayErrorBlock)completion;
+
+/**
+ * Stores mutation for the given key and set data, to be committed when commitWithCompletion is
+ * called.
+ */
+- (void)setData:(FSTParsedSetData *)data forDocument:(FSTDocumentKey *)key;
+
+/**
+ * Stores mutations for the given key and update data, to be committed when commitWithCompletion
+ * is called.
+ */
+- (void)updateData:(FSTParsedUpdateData *)data forDocument:(FSTDocumentKey *)key;
+
+/**
+ * Stores a delete mutation for the given key, to be committed when commitWithCompletion is called.
+ */
+- (void)deleteDocument:(FSTDocumentKey *)key;
+
+/**
+ * Attempts to commit the mutations set on this transaction. Calls the given completion block when
+ * finished. Once this is called, no other mutations or commits are allowed on the transaction.
+ */
+- (void)commitWithCompletion:(FSTVoidErrorBlock)completion;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTTransaction.m b/Firestore/Source/Core/FSTTransaction.m
new file mode 100644
index 0000000..26c69e0
--- /dev/null
+++ b/Firestore/Source/Core/FSTTransaction.m
@@ -0,0 +1,250 @@
+/*
+ * 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 "FSTTransaction.h"
+
+#import <GRPCClient/GRPCCall.h>
+
+#import "FIRFirestoreErrors.h"
+#import "FIRSetOptions.h"
+#import "FSTAssert.h"
+#import "FSTDatastore.h"
+#import "FSTDocument.h"
+#import "FSTDocumentKey.h"
+#import "FSTDocumentKeySet.h"
+#import "FSTMutation.h"
+#import "FSTSnapshotVersion.h"
+#import "FSTUsageValidation.h"
+#import "FSTUserDataConverter.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTTransaction
+
+@interface FSTTransaction ()
+@property(nonatomic, strong, readonly) FSTDatastore *datastore;
+@property(nonatomic, strong, readonly)
+    NSMutableDictionary<FSTDocumentKey *, FSTSnapshotVersion *> *readVersions;
+@property(nonatomic, strong, readonly) NSMutableArray *mutations;
+@property(nonatomic, assign) BOOL commitCalled;
+/**
+ * An error that may have occurred as a consequence of a write. If set, needs to be raised in the
+ * completion handler instead of trying to commit.
+ */
+@property(nonatomic, strong, nullable) NSError *lastWriteError;
+@end
+
+@implementation FSTTransaction
+
++ (instancetype)transactionWithDatastore:(FSTDatastore *)datastore {
+  return [[FSTTransaction alloc] initWithDatastore:datastore];
+}
+
+- (instancetype)initWithDatastore:(FSTDatastore *)datastore {
+  self = [super init];
+  if (self) {
+    _datastore = datastore;
+    _readVersions = [NSMutableDictionary dictionary];
+    _mutations = [NSMutableArray array];
+    _commitCalled = NO;
+  }
+  return self;
+}
+
+/**
+ * Every time a document is read, this should be called to record its version. If we read two
+ * different versions of the same document, this will return an error through its out parameter.
+ * When the transaction is committed, the versions recorded will be set as preconditions on the
+ * writes sent to the backend.
+ */
+- (BOOL)recordVersionForDocument:(FSTMaybeDocument *)doc error:(NSError **)error {
+  FSTAssert(error != nil, @"nil error parameter");
+  *error = nil;
+  FSTSnapshotVersion *docVersion = doc.version;
+  if ([doc isKindOfClass:[FSTDeletedDocument class]]) {
+    // For deleted docs, we must record an explicit no version to build the right precondition
+    // when writing.
+    docVersion = [FSTSnapshotVersion noVersion];
+  }
+  FSTSnapshotVersion *existingVersion = self.readVersions[doc.key];
+  if (existingVersion) {
+    if (error) {
+      *error =
+          [NSError errorWithDomain:FIRFirestoreErrorDomain
+                              code:FIRFirestoreErrorCodeFailedPrecondition
+                          userInfo:@{
+                            NSLocalizedDescriptionKey :
+                                @"A document cannot be read twice within a single transaction."
+                          }];
+    }
+    return NO;
+  } else {
+    self.readVersions[doc.key] = docVersion;
+    return YES;
+  }
+}
+
+- (void)lookupDocumentsForKeys:(NSArray<FSTDocumentKey *> *)keys
+                    completion:(FSTVoidMaybeDocumentArrayErrorBlock)completion {
+  [self ensureCommitNotCalled];
+  if (self.mutations.count) {
+    FSTThrowInvalidUsage(@"FIRIllegalStateException",
+                         @"All reads in a transaction must be done before any writes.");
+  }
+  [self.datastore
+      lookupDocuments:keys
+           completion:^(NSArray<FSTDocument *> *_Nullable documents, NSError *_Nullable error) {
+             if (error) {
+               completion(nil, error);
+               return;
+             }
+             for (FSTMaybeDocument *doc in documents) {
+               NSError *recordError = nil;
+               if (![self recordVersionForDocument:doc error:&recordError]) {
+                 completion(nil, recordError);
+                 return;
+               }
+             }
+             completion(documents, nil);
+           }];
+}
+
+/** Stores mutations to be written when commitWithCompletion is called. */
+- (void)writeMutations:(NSArray<FSTMutation *> *)mutations {
+  [self ensureCommitNotCalled];
+  [self.mutations addObjectsFromArray:mutations];
+}
+
+/**
+ * Returns version of this doc when it was read in this transaction as a precondition, or no
+ * precondition if it was not read.
+ */
+- (FSTPrecondition *)preconditionForDocumentKey:(FSTDocumentKey *)key {
+  FSTSnapshotVersion *_Nullable snapshotVersion = self.readVersions[key];
+  if (snapshotVersion) {
+    return [FSTPrecondition preconditionWithUpdateTime:snapshotVersion];
+  } else {
+    return [FSTPrecondition none];
+  }
+}
+
+/**
+ * Returns the precondition for a document if the operation is an update, based on the provided
+ * UpdateOptions. Will return nil if an error occurred, in which case it sets the error parameter.
+ */
+- (nullable FSTPrecondition *)preconditionForUpdateWithDocumentKey:(FSTDocumentKey *)key
+                                                             error:(NSError **)error {
+  FSTSnapshotVersion *_Nullable version = self.readVersions[key];
+  if (version && [version isEqual:[FSTSnapshotVersion noVersion]]) {
+    // The document was read, but doesn't exist.
+    // Return an error because the precondition is impossible
+    if (error) {
+      *error = [NSError
+          errorWithDomain:FIRFirestoreErrorDomain
+                     code:FIRFirestoreErrorCodeAborted
+                 userInfo:@{
+                   NSLocalizedDescriptionKey : @"Can't update a document that doesn't exist."
+                 }];
+    }
+    return nil;
+  } else if (version) {
+    // Document exists, just base precondition on document update time.
+    return [FSTPrecondition preconditionWithUpdateTime:version];
+  } else {
+    // Document was not read, so we just use the preconditions for an update.
+    return [FSTPrecondition preconditionWithExists:YES];
+  }
+}
+
+- (void)setData:(FSTParsedSetData *)data forDocument:(FSTDocumentKey *)key {
+  [self writeMutations:[data mutationsWithKey:key
+                                 precondition:[self preconditionForDocumentKey:key]]];
+}
+
+- (void)updateData:(FSTParsedUpdateData *)data forDocument:(FSTDocumentKey *)key {
+  NSError *error = nil;
+  FSTPrecondition *_Nullable precondition =
+      [self preconditionForUpdateWithDocumentKey:key error:&error];
+  if (precondition) {
+    [self writeMutations:[data mutationsWithKey:key precondition:precondition]];
+  } else {
+    FSTAssert(error, @"Got nil precondition, but error was not set");
+    self.lastWriteError = error;
+  }
+}
+
+- (void)deleteDocument:(FSTDocumentKey *)key {
+  [self writeMutations:@[ [[FSTDeleteMutation alloc]
+                            initWithKey:key
+                           precondition:[self preconditionForDocumentKey:key]] ]];
+  // Since the delete will be applied before all following writes, we need to ensure that the
+  // precondition for the next write will be exists: false.
+  self.readVersions[key] = [FSTSnapshotVersion noVersion];
+}
+
+- (void)commitWithCompletion:(FSTVoidErrorBlock)completion {
+  [self ensureCommitNotCalled];
+  // Once commitWithCompletion is called once, mark this object so it can't be used again.
+  self.commitCalled = YES;
+
+  // If there was an error writing, raise that error now
+  if (self.lastWriteError) {
+    completion(self.lastWriteError);
+    return;
+  }
+
+  // Make a list of read documents that haven't been written.
+  __block FSTDocumentKeySet *unwritten = [FSTDocumentKeySet keySet];
+  [self.readVersions enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key,
+                                                         FSTSnapshotVersion *version, BOOL *stop) {
+    unwritten = [unwritten setByAddingObject:key];
+  }];
+  // For each mutation, note that the doc was written.
+  for (FSTMutation *mutation in self.mutations) {
+    unwritten = [unwritten setByRemovingObject:mutation.key];
+  }
+  if (unwritten.count) {
+    // TODO(klimt): This is a temporary restriction, until "verify" is supported on the backend.
+    completion([NSError
+        errorWithDomain:FIRFirestoreErrorDomain
+                   code:FIRFirestoreErrorCodeFailedPrecondition
+               userInfo:@{
+                 NSLocalizedDescriptionKey : @"Every document read in a transaction must also be "
+                                             @"written in that transaction."
+               }]);
+  } else {
+    [self.datastore commitMutations:self.mutations
+                         completion:^(NSError *_Nullable error) {
+                           if (error) {
+                             completion(error);
+                           } else {
+                             completion(nil);
+                           }
+                         }];
+  }
+}
+
+- (void)ensureCommitNotCalled {
+  if (self.commitCalled) {
+    FSTThrowInvalidUsage(
+        @"FIRIllegalStateException",
+        @"A transaction object cannot be used after its update block has completed.");
+  }
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTTypes.h b/Firestore/Source/Core/FSTTypes.h
new file mode 100644
index 0000000..8f1183c
--- /dev/null
+++ b/Firestore/Source/Core/FSTTypes.h
@@ -0,0 +1,90 @@
+/*
+ * 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>
+
+NS_ASSUME_NONNULL_BEGIN
+
+@class FSTMaybeDocument;
+@class FSTTransaction;
+
+/** FSTBatchID is a locally assigned ID for a batch of mutations that have been applied. */
+typedef int32_t FSTBatchID;
+
+typedef int32_t FSTTargetID;
+
+typedef NSNumber FSTBoxedTargetID;
+
+/**
+ * FSTVoidBlock is a block that's called when a specific event happens but that otherwise has
+ * no information associated with it.
+ */
+typedef void (^FSTVoidBlock)();
+
+/**
+ * FSTVoidErrorBlock is a block that gets an error, if one occurred.
+ *
+ * @param error The error if it occurred, or nil.
+ */
+typedef void (^FSTVoidErrorBlock)(NSError *_Nullable error);
+
+/** FSTVoidIDErrorBlock is a block that takes an optional value and error. */
+typedef void (^FSTVoidIDErrorBlock)(id _Nullable, NSError *_Nullable);
+
+/**
+ * FSTVoidMaybeDocumentErrorBlock is a block that gets either a list of documents or an error.
+ *
+ * @param documents The documents, if no error occurred, or nil.
+ * @param error The error, if one occurred, or nil.
+ */
+typedef void (^FSTVoidMaybeDocumentArrayErrorBlock)(
+    NSArray<FSTMaybeDocument *> *_Nullable documents, NSError *_Nullable error);
+
+/**
+ * FSTTransactionBlock is a block that wraps a user's transaction update block internally.
+ *
+ * @param transaction An object with methods for performing reads and writes within the
+ *                    transaction.
+ * @param completion To be called by the block once the user's code is finished.
+ */
+typedef void (^FSTTransactionBlock)(FSTTransaction *transaction,
+                                    void (^completion)(id _Nullable, NSError *_Nullable));
+
+/** Describes the online state of the Firestore client */
+typedef NS_ENUM(NSUInteger, FSTOnlineState) {
+  /**
+   * The Firestore client is in an unknown online state. This means the client is either not
+   * actively trying to establish a connection or it was previously in an unknown state and is
+   * trying to establish a connection.
+   */
+  FSTOnlineStateUnknown,
+
+  /**
+   * The client is connected and the connections are healthy. This state is reached after a
+   * successful connection and there has been at least one successful message received from the
+   * backends.
+   */
+  FSTOnlineStateHealthy,
+
+  /**
+   * The client has tried to establish a connection but has failed.
+   * This state is reached after either a connection attempt failed or a healthy stream was closed
+   * for unexpected reasons.
+   */
+  FSTOnlineStateFailed
+};
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTView.h b/Firestore/Source/Core/FSTView.h
new file mode 100644
index 0000000..2dbfac2
--- /dev/null
+++ b/Firestore/Source/Core/FSTView.h
@@ -0,0 +1,143 @@
+/*
+ * 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>
+
+#import "FSTDocumentDictionary.h"
+#import "FSTDocumentKeySet.h"
+
+@class FSTDocumentKey;
+@class FSTDocumentSet;
+@class FSTDocumentViewChangeSet;
+@class FSTMaybeDocument;
+@class FSTQuery;
+@class FSTTargetChange;
+@class FSTViewSnapshot;
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTViewDocumentChanges
+
+/** The result of applying a set of doc changes to a view. */
+@interface FSTViewDocumentChanges : NSObject
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** The new set of docs that should be in the view. */
+@property(nonatomic, strong, readonly) FSTDocumentSet *documentSet;
+
+/** The diff of this these docs with the previous set of docs. */
+@property(nonatomic, strong, readonly) FSTDocumentViewChangeSet *changeSet;
+
+/**
+ * Whether the set of documents passed in was not sufficient to calculate the new state of the view
+ * and there needs to be another pass based on the local cache.
+ */
+@property(nonatomic, assign, readonly) BOOL needsRefill;
+
+@property(nonatomic, strong, readonly) FSTDocumentKeySet *mutatedKeys;
+
+@end
+
+#pragma mark - FSTLimboDocumentChange
+
+typedef NS_ENUM(NSInteger, FSTLimboDocumentChangeType) {
+  FSTLimboDocumentChangeTypeAdded = 0,
+  FSTLimboDocumentChangeTypeRemoved,
+};
+
+// A change to a particular document wrt to whether it is in "limbo".
+@interface FSTLimboDocumentChange : NSObject
+
++ (instancetype)changeWithType:(FSTLimboDocumentChangeType)type key:(FSTDocumentKey *)key;
+
+- (id)init __attribute__((unavailable("Use a static constructor method.")));
+
+@property(nonatomic, assign, readonly) FSTLimboDocumentChangeType type;
+@property(nonatomic, strong, readonly) FSTDocumentKey *key;
+@end
+
+#pragma mark - FSTViewChange
+
+// A set of changes to a view.
+@interface FSTViewChange : NSObject
+
+- (id)init __attribute__((unavailable("Use a static constructor method.")));
+
+@property(nonatomic, strong, readonly, nullable) FSTViewSnapshot *snapshot;
+@property(nonatomic, strong, readonly) NSArray<FSTLimboDocumentChange *> *limboChanges;
+@end
+
+#pragma mark - FSTView
+
+/**
+ * View is responsible for computing the final merged truth of what docs are in a query. It gets
+ * notified of local and remote changes to docs, and applies the query filters and limits to
+ * determine the most correct possible results.
+ */
+@interface FSTView : NSObject
+
+- (instancetype)init NS_UNAVAILABLE;
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+              remoteDocuments:(FSTDocumentKeySet *)remoteDocuments NS_DESIGNATED_INITIALIZER;
+
+/**
+ * Iterates over a set of doc changes, applies the query limit, and computes what the new results
+ * should be, what the changes were, and whether we may need to go back to the local cache for
+ * more results. Does not make any changes to the view.
+ *
+ * @param docChanges The doc changes to apply to this view.
+ * @return a new set of docs, changes, and refill flag.
+ */
+- (FSTViewDocumentChanges *)computeChangesWithDocuments:(FSTMaybeDocumentDictionary *)docChanges;
+
+/**
+ * Iterates over a set of doc changes, applies the query limit, and computes what the new results
+ * should be, what the changes were, and whether we may need to go back to the local cache for
+ * more results. Does not make any changes to the view.
+ *
+ * @param docChanges The doc changes to apply to this view.
+ * @param previousChanges If this is being called with a refill, then start with this set of docs
+ *     and changes instead of the current view.
+ * @return a new set of docs, changes, and refill flag.
+ */
+- (FSTViewDocumentChanges *)computeChangesWithDocuments:(FSTMaybeDocumentDictionary *)docChanges
+                                        previousChanges:
+                                            (nullable FSTViewDocumentChanges *)previousChanges;
+
+/**
+ * Updates the view with the given ViewDocumentChanges.
+ *
+ * @param docChanges The set of changes to make to the view's docs.
+ * @return A new FSTViewChange with the given docs, changes, and sync state.
+ */
+- (FSTViewChange *)applyChangesToDocuments:(FSTViewDocumentChanges *)docChanges;
+
+/**
+ * Updates the view with the given FSTViewDocumentChanges and updates limbo docs and sync state from
+ * the given (optional) target change.
+ *
+ * @param docChanges The set of changes to make to the view's docs.
+ * @param targetChange A target change to apply for computing limbo docs and sync state.
+ * @return A new FSTViewChange with the given docs, changes, and sync state.
+ */
+- (FSTViewChange *)applyChangesToDocuments:(FSTViewDocumentChanges *)docChanges
+                              targetChange:(nullable FSTTargetChange *)targetChange;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTView.m b/Firestore/Source/Core/FSTView.m
new file mode 100644
index 0000000..719e303
--- /dev/null
+++ b/Firestore/Source/Core/FSTView.m
@@ -0,0 +1,451 @@
+/*
+ * 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 "FSTView.h"
+
+#import "FSTAssert.h"
+#import "FSTDocument.h"
+#import "FSTDocumentKey.h"
+#import "FSTDocumentSet.h"
+#import "FSTFieldValue.h"
+#import "FSTQuery.h"
+#import "FSTRemoteEvent.h"
+#import "FSTViewSnapshot.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTViewDocumentChanges
+
+/** The result of applying a set of doc changes to a view. */
+@interface FSTViewDocumentChanges ()
+
+- (instancetype)initWithDocumentSet:(FSTDocumentSet *)documentSet
+                          changeSet:(FSTDocumentViewChangeSet *)changeSet
+                        needsRefill:(BOOL)needsRefill
+                        mutatedKeys:(FSTDocumentKeySet *)mutatedKeys NS_DESIGNATED_INITIALIZER;
+
+@end
+
+@implementation FSTViewDocumentChanges
+
+- (instancetype)initWithDocumentSet:(FSTDocumentSet *)documentSet
+                          changeSet:(FSTDocumentViewChangeSet *)changeSet
+                        needsRefill:(BOOL)needsRefill
+                        mutatedKeys:(FSTDocumentKeySet *)mutatedKeys {
+  self = [super init];
+  if (self) {
+    _documentSet = documentSet;
+    _changeSet = changeSet;
+    _needsRefill = needsRefill;
+    _mutatedKeys = mutatedKeys;
+  }
+  return self;
+}
+
+@end
+
+#pragma mark - FSTLimboDocumentChange
+
+@interface FSTLimboDocumentChange ()
+
++ (instancetype)changeWithType:(FSTLimboDocumentChangeType)type key:(FSTDocumentKey *)key;
+
+- (instancetype)initWithType:(FSTLimboDocumentChangeType)type
+                         key:(FSTDocumentKey *)key NS_DESIGNATED_INITIALIZER;
+
+@end
+
+@implementation FSTLimboDocumentChange
+
++ (instancetype)changeWithType:(FSTLimboDocumentChangeType)type key:(FSTDocumentKey *)key {
+  return [[FSTLimboDocumentChange alloc] initWithType:type key:key];
+}
+
+- (instancetype)initWithType:(FSTLimboDocumentChangeType)type key:(FSTDocumentKey *)key {
+  self = [super init];
+  if (self) {
+    _type = type;
+    _key = key;
+  }
+  return self;
+}
+
+- (BOOL)isEqual:(id)other {
+  if (self == other) {
+    return YES;
+  }
+  if (![other isKindOfClass:[FSTLimboDocumentChange class]]) {
+    return NO;
+  }
+  FSTLimboDocumentChange *otherChange = (FSTLimboDocumentChange *)other;
+  return self.type == otherChange.type && [self.key isEqual:otherChange.key];
+}
+
+@end
+
+#pragma mark - FSTViewChange
+
+@interface FSTViewChange ()
+
++ (FSTViewChange *)changeWithSnapshot:(nullable FSTViewSnapshot *)snapshot
+                         limboChanges:(NSArray<FSTLimboDocumentChange *> *)limboChanges;
+
+- (instancetype)initWithSnapshot:(nullable FSTViewSnapshot *)snapshot
+                    limboChanges:(NSArray<FSTLimboDocumentChange *> *)limboChanges
+    NS_DESIGNATED_INITIALIZER;
+
+@end
+
+@implementation FSTViewChange
+
++ (FSTViewChange *)changeWithSnapshot:(nullable FSTViewSnapshot *)snapshot
+                         limboChanges:(NSArray<FSTLimboDocumentChange *> *)limboChanges {
+  return [[self alloc] initWithSnapshot:snapshot limboChanges:limboChanges];
+}
+
+- (instancetype)initWithSnapshot:(nullable FSTViewSnapshot *)snapshot
+                    limboChanges:(NSArray<FSTLimboDocumentChange *> *)limboChanges {
+  self = [super init];
+  if (self) {
+    _snapshot = snapshot;
+    _limboChanges = limboChanges;
+  }
+  return self;
+}
+
+@end
+
+#pragma mark - FSTView
+
+static NSComparisonResult FSTCompareDocumentViewChangeTypes(FSTDocumentViewChangeType c1,
+                                                            FSTDocumentViewChangeType c2);
+
+@interface FSTView ()
+
+@property(nonatomic, strong, readonly) FSTQuery *query;
+
+@property(nonatomic, assign) FSTSyncState syncState;
+
+/**
+ * A flag whether the view is current with the backend. A view is considered current after it
+ * has seen the current flag from the backend and did not lose consistency within the watch stream
+ * (e.g. because of an existence filter mismatch).
+ */
+@property(nonatomic, assign, getter=isCurrent) BOOL current;
+
+@property(nonatomic, strong) FSTDocumentSet *documentSet;
+
+/** Documents included in the remote target. */
+@property(nonatomic, strong) FSTDocumentKeySet *syncedDocuments;
+
+/** Documents in the view but not in the remote target */
+@property(nonatomic, strong) FSTDocumentKeySet *limboDocuments;
+
+/** Document Keys that have local changes. */
+@property(nonatomic, strong) FSTDocumentKeySet *mutatedKeys;
+
+@end
+
+@implementation FSTView
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+              remoteDocuments:(nonnull FSTDocumentKeySet *)remoteDocuments {
+  self = [super init];
+  if (self) {
+    _query = query;
+    _documentSet = [FSTDocumentSet documentSetWithComparator:query.comparator];
+    _syncedDocuments = remoteDocuments;
+    _limboDocuments = [FSTDocumentKeySet keySet];
+    _mutatedKeys = [FSTDocumentKeySet keySet];
+  }
+  return self;
+}
+
+- (FSTViewDocumentChanges *)computeChangesWithDocuments:(FSTMaybeDocumentDictionary *)docChanges {
+  return [self computeChangesWithDocuments:docChanges previousChanges:nil];
+}
+
+- (FSTViewDocumentChanges *)computeChangesWithDocuments:(FSTMaybeDocumentDictionary *)docChanges
+                                        previousChanges:
+                                            (nullable FSTViewDocumentChanges *)previousChanges {
+  FSTDocumentViewChangeSet *changeSet =
+      previousChanges ? previousChanges.changeSet : [FSTDocumentViewChangeSet changeSet];
+  FSTDocumentSet *oldDocumentSet = previousChanges ? previousChanges.documentSet : self.documentSet;
+
+  __block FSTDocumentKeySet *newMutatedKeys =
+      previousChanges ? previousChanges.mutatedKeys : self.mutatedKeys;
+  __block FSTDocumentSet *newDocumentSet = oldDocumentSet;
+  __block BOOL needsRefill = NO;
+
+  // Track the last doc in a (full) limit. This is necessary, because some update (a delete, or an
+  // update moving a doc past the old limit) might mean there is some other document in the local
+  // cache that either should come (1) between the old last limit doc and the new last document,
+  // in the case of updates, or (2) after the new last document, in the case of deletes. So we
+  // keep this doc at the old limit to compare the updates to.
+  //
+  // Note that this should never get used in a refill (when previousChanges is set), because there
+  // will only be adds -- no deletes or updates.
+  FSTDocument *_Nullable lastDocInLimit =
+      (self.query.limit && oldDocumentSet.count == self.query.limit) ? oldDocumentSet.lastDocument
+                                                                     : nil;
+
+  [docChanges enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key,
+                                                  FSTMaybeDocument *maybeNewDoc, BOOL *stop) {
+    FSTDocument *_Nullable oldDoc = [oldDocumentSet documentForKey:key];
+    FSTDocument *_Nullable newDoc = nil;
+    if ([maybeNewDoc isKindOfClass:[FSTDocument class]]) {
+      newDoc = (FSTDocument *)maybeNewDoc;
+    }
+    if (newDoc) {
+      FSTAssert([key isEqual:newDoc.key], @"Mismatching key in document changes: %@ != %@", key,
+                newDoc.key);
+      if (![self.query matchesDocument:newDoc]) {
+        newDoc = nil;
+      }
+    }
+    if (newDoc) {
+      newDocumentSet = [newDocumentSet documentSetByAddingDocument:newDoc];
+      if (newDoc.hasLocalMutations) {
+        newMutatedKeys = [newMutatedKeys setByAddingObject:key];
+      } else {
+        newMutatedKeys = [newMutatedKeys setByRemovingObject:key];
+      }
+    } else {
+      newDocumentSet = [newDocumentSet documentSetByRemovingKey:key];
+      newMutatedKeys = [newMutatedKeys setByRemovingObject:key];
+    }
+
+    // Calculate change
+    if (oldDoc && newDoc) {
+      BOOL docsEqual = [oldDoc.data isEqual:newDoc.data];
+      if (!docsEqual || oldDoc.hasLocalMutations != newDoc.hasLocalMutations) {
+        // only report a change if document actually changed.
+        if (docsEqual) {
+          [changeSet addChange:[FSTDocumentViewChange
+                                   changeWithDocument:newDoc
+                                                 type:FSTDocumentViewChangeTypeMetadata]];
+        } else {
+          [changeSet addChange:[FSTDocumentViewChange
+                                   changeWithDocument:newDoc
+                                                 type:FSTDocumentViewChangeTypeModified]];
+        }
+
+        if (lastDocInLimit && self.query.comparator(newDoc, lastDocInLimit) > 0) {
+          // This doc moved from inside the limit to after the limit. That means there may be some
+          // doc in the local cache that's actually less than this one.
+          needsRefill = YES;
+        }
+      }
+    } else if (!oldDoc && newDoc) {
+      [changeSet
+          addChange:[FSTDocumentViewChange changeWithDocument:newDoc
+                                                         type:FSTDocumentViewChangeTypeAdded]];
+    } else if (oldDoc && !newDoc) {
+      [changeSet
+          addChange:[FSTDocumentViewChange changeWithDocument:oldDoc
+                                                         type:FSTDocumentViewChangeTypeRemoved]];
+      if (lastDocInLimit) {
+        // A doc was removed from a full limit query. We'll need to re-query from the local cache
+        // to see if we know about some other doc that should be in the results.
+        needsRefill = YES;
+      }
+    }
+  }];
+  if (self.query.limit) {
+    // TODO(klimt): Make DocumentSet size be constant time.
+    while (newDocumentSet.count > self.query.limit) {
+      FSTDocument *oldDoc = [newDocumentSet lastDocument];
+      newDocumentSet = [newDocumentSet documentSetByRemovingKey:oldDoc.key];
+      [changeSet
+          addChange:[FSTDocumentViewChange changeWithDocument:oldDoc
+                                                         type:FSTDocumentViewChangeTypeRemoved]];
+    }
+  }
+
+  FSTAssert(!needsRefill || !previousChanges,
+            @"View was refilled using docs that themselves needed refilling.");
+
+  return [[FSTViewDocumentChanges alloc] initWithDocumentSet:newDocumentSet
+                                                   changeSet:changeSet
+                                                 needsRefill:needsRefill
+                                                 mutatedKeys:newMutatedKeys];
+}
+
+- (FSTViewChange *)applyChangesToDocuments:(FSTViewDocumentChanges *)docChanges {
+  return [self applyChangesToDocuments:docChanges targetChange:nil];
+}
+
+- (FSTViewChange *)applyChangesToDocuments:(FSTViewDocumentChanges *)docChanges
+                              targetChange:(nullable FSTTargetChange *)targetChange {
+  FSTAssert(!docChanges.needsRefill, @"Cannot apply changes that need a refill");
+
+  FSTDocumentSet *oldDocuments = self.documentSet;
+  self.documentSet = docChanges.documentSet;
+  self.mutatedKeys = docChanges.mutatedKeys;
+
+  // Sort changes based on type and query comparator.
+  NSArray<FSTDocumentViewChange *> *changes = [docChanges.changeSet changes];
+  changes = [changes sortedArrayUsingComparator:^NSComparisonResult(FSTDocumentViewChange *c1,
+                                                                    FSTDocumentViewChange *c2) {
+    NSComparisonResult typeComparison = FSTCompareDocumentViewChangeTypes(c1.type, c2.type);
+    if (typeComparison != NSOrderedSame) {
+      return typeComparison;
+    }
+    return self.query.comparator(c1.document, c2.document);
+  }];
+
+  NSArray<FSTLimboDocumentChange *> *limboChanges = [self applyTargetChange:targetChange];
+  BOOL synced = self.limboDocuments.count == 0 && self.isCurrent;
+  FSTSyncState newSyncState = synced ? FSTSyncStateSynced : FSTSyncStateLocal;
+  BOOL syncStateChanged = newSyncState != self.syncState;
+  self.syncState = newSyncState;
+
+  if (changes.count == 0 && !syncStateChanged) {
+    // No changes.
+    return [FSTViewChange changeWithSnapshot:nil limboChanges:limboChanges];
+  } else {
+    FSTViewSnapshot *snapshot =
+        [[FSTViewSnapshot alloc] initWithQuery:self.query
+                                     documents:docChanges.documentSet
+                                  oldDocuments:oldDocuments
+                               documentChanges:changes
+                                     fromCache:newSyncState == FSTSyncStateLocal
+                              hasPendingWrites:!docChanges.mutatedKeys.isEmpty
+                              syncStateChanged:syncStateChanged];
+
+    return [FSTViewChange changeWithSnapshot:snapshot limboChanges:limboChanges];
+  }
+}
+
+#pragma mark - Private methods
+
+/** Returns whether the doc for the given key should be in limbo. */
+- (BOOL)shouldBeLimboDocumentKey:(FSTDocumentKey *)key {
+  // If the remote end says it's part of this query, it's not in limbo.
+  if ([self.syncedDocuments containsObject:key]) {
+    return NO;
+  }
+  // The local store doesn't think it's a result, so it shouldn't be in limbo.
+  if (![self.documentSet containsKey:key]) {
+    return NO;
+  }
+  // If there are local changes to the doc, they might explain why the server doesn't know that it's
+  // part of the query. So don't put it in limbo.
+  // TODO(klimt): Ideally, we would only consider changes that might actually affect this specific
+  // query.
+  if ([self.documentSet documentForKey:key].hasLocalMutations) {
+    return NO;
+  }
+  // Everything else is in limbo.
+  return YES;
+}
+
+/**
+ * Updates syncedDocuments, isAcked, and limbo docs based on the given change.
+ * @return the list of changes to which docs are in limbo.
+ */
+- (NSArray<FSTLimboDocumentChange *> *)applyTargetChange:(nullable FSTTargetChange *)targetChange {
+  if (targetChange) {
+    FSTTargetMapping *targetMapping = targetChange.mapping;
+    if ([targetMapping isKindOfClass:[FSTResetMapping class]]) {
+      self.syncedDocuments = ((FSTResetMapping *)targetMapping).documents;
+    } else if ([targetMapping isKindOfClass:[FSTUpdateMapping class]]) {
+      [((FSTUpdateMapping *)targetMapping).addedDocuments
+          enumerateObjectsUsingBlock:^(FSTDocumentKey *key, BOOL *stop) {
+            self.syncedDocuments = [self.syncedDocuments setByAddingObject:key];
+          }];
+      [((FSTUpdateMapping *)targetMapping).removedDocuments
+          enumerateObjectsUsingBlock:^(FSTDocumentKey *key, BOOL *stop) {
+            self.syncedDocuments = [self.syncedDocuments setByRemovingObject:key];
+          }];
+    }
+
+    switch (targetChange.currentStatusUpdate) {
+      case FSTCurrentStatusUpdateMarkCurrent:
+        self.current = YES;
+        break;
+      case FSTCurrentStatusUpdateMarkNotCurrent:
+        self.current = NO;
+        break;
+      case FSTCurrentStatusUpdateNone:
+        break;
+    }
+  }
+
+  // Recompute the set of limbo docs.
+  // TODO(klimt): Do this incrementally so that it's not quadratic when updating many documents.
+  FSTDocumentKeySet *oldLimboDocuments = self.limboDocuments;
+  self.limboDocuments = [FSTDocumentKeySet keySet];
+  if (self.isCurrent) {
+    for (FSTDocument *doc in self.documentSet.documentEnumerator) {
+      if ([self shouldBeLimboDocumentKey:doc.key]) {
+        self.limboDocuments = [self.limboDocuments setByAddingObject:doc.key];
+      }
+    }
+  }
+
+  // Diff the new limbo docs with the old limbo docs.
+  NSMutableArray<FSTLimboDocumentChange *> *changes =
+      [NSMutableArray arrayWithCapacity:(oldLimboDocuments.count + self.limboDocuments.count)];
+  [oldLimboDocuments enumerateObjectsUsingBlock:^(FSTDocumentKey *key, BOOL *stop) {
+    if (![self.limboDocuments containsObject:key]) {
+      [changes addObject:[FSTLimboDocumentChange changeWithType:FSTLimboDocumentChangeTypeRemoved
+                                                            key:key]];
+    }
+  }];
+  [self.limboDocuments enumerateObjectsUsingBlock:^(FSTDocumentKey *key, BOOL *stop) {
+    if (![oldLimboDocuments containsObject:key]) {
+      [changes addObject:[FSTLimboDocumentChange changeWithType:FSTLimboDocumentChangeTypeAdded
+                                                            key:key]];
+    }
+  }];
+  return changes;
+}
+
+@end
+
+static inline int DocumentViewChangeTypePosition(FSTDocumentViewChangeType changeType) {
+  switch (changeType) {
+    case FSTDocumentViewChangeTypeRemoved:
+      return 0;
+    case FSTDocumentViewChangeTypeAdded:
+      return 1;
+    case FSTDocumentViewChangeTypeModified:
+      return 2;
+    case FSTDocumentViewChangeTypeMetadata:
+      // A metadata change is converted to a modified change at the public API layer. Since we sort
+      // by document key and then change type, metadata and modified changes must be sorted
+      // equivalently.
+      return 2;
+    default:
+      FSTCFail(@"Unknown FSTDocumentViewChangeType %lu", (unsigned long)changeType);
+  }
+}
+
+static NSComparisonResult FSTCompareDocumentViewChangeTypes(FSTDocumentViewChangeType c1,
+                                                            FSTDocumentViewChangeType c2) {
+  int pos1 = DocumentViewChangeTypePosition(c1);
+  int pos2 = DocumentViewChangeTypePosition(c2);
+  if (pos1 == pos2) {
+    return NSOrderedSame;
+  } else if (pos1 < pos2) {
+    return NSOrderedAscending;
+  } else {
+    return NSOrderedDescending;
+  }
+}
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTViewSnapshot.h b/Firestore/Source/Core/FSTViewSnapshot.h
new file mode 100644
index 0000000..3db6108
--- /dev/null
+++ b/Firestore/Source/Core/FSTViewSnapshot.h
@@ -0,0 +1,117 @@
+/*
+ * 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 FSTDocument;
+@class FSTQuery;
+@class FSTDocumentSet;
+@class FSTViewSnapshot;
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTDocumentViewChange
+
+/**
+ * The types of changes that can happen to a document with respect to a view.
+ * NOTE: We sort document changes by their type, so the ordering of this enum is significant.
+ */
+typedef NS_ENUM(NSInteger, FSTDocumentViewChangeType) {
+  FSTDocumentViewChangeTypeRemoved = 0,
+  FSTDocumentViewChangeTypeAdded,
+  FSTDocumentViewChangeTypeModified,
+  FSTDocumentViewChangeTypeMetadata,
+};
+
+/** A change to a single document's state within a view. */
+@interface FSTDocumentViewChange : NSObject
+
+- (id)init __attribute__((unavailable("Use a static constructor method.")));
+
++ (instancetype)changeWithDocument:(FSTDocument *)document type:(FSTDocumentViewChangeType)type;
+
+/** The type of change for the document. */
+@property(nonatomic, assign, readonly) FSTDocumentViewChangeType type;
+/** The document whose status changed. */
+@property(nonatomic, strong, readonly) FSTDocument *document;
+
+@end
+
+#pragma mark - FSTDocumentChangeSet
+
+/** The possibly states a document can be in w.r.t syncing from local storage to the backend. */
+typedef NS_ENUM(NSInteger, FSTSyncState) {
+  FSTSyncStateNone = 0,
+  FSTSyncStateLocal,
+  FSTSyncStateSynced,
+};
+
+/** A set of changes to documents with respect to a view. This set is mutable. */
+@interface FSTDocumentViewChangeSet : NSObject
+
+/** Returns a new empty change set. */
++ (instancetype)changeSet;
+
+/** Takes a new change and applies it to the set. */
+- (void)addChange:(FSTDocumentViewChange *)change;
+
+/** Returns the set of all changes tracked in this set. */
+- (NSArray<FSTDocumentViewChange *> *)changes;
+
+@end
+
+#pragma mark - FSTViewSnapshot
+
+typedef void (^FSTViewSnapshotHandler)(FSTViewSnapshot *_Nullable snapshot,
+                                       NSError *_Nullable error);
+
+/** A view snapshot is an immutable capture of the results of a query and the changes to them. */
+@interface FSTViewSnapshot : NSObject
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                    documents:(FSTDocumentSet *)documents
+                 oldDocuments:(FSTDocumentSet *)oldDocuments
+              documentChanges:(NSArray<FSTDocumentViewChange *> *)documentChanges
+                    fromCache:(BOOL)fromCache
+             hasPendingWrites:(BOOL)hasPendingWrites
+             syncStateChanged:(BOOL)syncStateChanged NS_DESIGNATED_INITIALIZER;
+
+- (instancetype)init NS_UNAVAILABLE;
+
+/** The query this view is tracking the results for. */
+@property(nonatomic, strong, readonly) FSTQuery *query;
+
+/** The documents currently known to be results of the query. */
+@property(nonatomic, strong, readonly) FSTDocumentSet *documents;
+
+/** The documents of the last snapshot. */
+@property(nonatomic, strong, readonly) FSTDocumentSet *oldDocuments;
+
+/** The set of changes that have been applied to the documents. */
+@property(nonatomic, strong, readonly) NSArray<FSTDocumentViewChange *> *documentChanges;
+
+/** Whether any document in the snapshot was served from the local cache. */
+@property(nonatomic, assign, readonly, getter=isFromCache) BOOL fromCache;
+
+/** Whether any document in the snapshot has pending local writes. */
+@property(nonatomic, assign, readonly) BOOL hasPendingWrites;
+
+/** Whether the sync state changed as part of this snapshot. */
+@property(nonatomic, assign, readonly) BOOL syncStateChanged;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/Source/Core/FSTViewSnapshot.m b/Firestore/Source/Core/FSTViewSnapshot.m
new file mode 100644
index 0000000..016f890
--- /dev/null
+++ b/Firestore/Source/Core/FSTViewSnapshot.m
@@ -0,0 +1,231 @@
+/*
+ * 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 "FSTViewSnapshot.h"
+
+#import "FSTAssert.h"
+#import "FSTDocument.h"
+#import "FSTDocumentKey.h"
+#import "FSTDocumentSet.h"
+#import "FSTImmutableSortedDictionary.h"
+#import "FSTQuery.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+#pragma mark - FSTDocumentViewChange
+
+@interface FSTDocumentViewChange ()
+
++ (instancetype)changeWithDocument:(FSTDocument *)document type:(FSTDocumentViewChangeType)type;
+
+- (instancetype)initWithDocument:(FSTDocument *)document
+                            type:(FSTDocumentViewChangeType)type NS_DESIGNATED_INITIALIZER;
+
+@end
+
+@implementation FSTDocumentViewChange
+
++ (instancetype)changeWithDocument:(FSTDocument *)document type:(FSTDocumentViewChangeType)type {
+  return [[FSTDocumentViewChange alloc] initWithDocument:document type:type];
+}
+
+- (instancetype)initWithDocument:(FSTDocument *)document type:(FSTDocumentViewChangeType)type {
+  self = [super init];
+  if (self) {
+    _document = document;
+    _type = type;
+  }
+  return self;
+}
+
+- (BOOL)isEqual:(id)other {
+  if (self == other) {
+    return YES;
+  }
+  if (![other isKindOfClass:[FSTDocumentViewChange class]]) {
+    return NO;
+  }
+  FSTDocumentViewChange *otherChange = (FSTDocumentViewChange *)other;
+  return [self.document isEqual:otherChange.document] && self.type == otherChange.type;
+}
+
+- (NSString *)description {
+  return [NSString
+      stringWithFormat:@"<FSTDocumentViewChange type:%ld doc:%@>", (long)self.type, self.document];
+}
+
+@end
+
+#pragma mark - FSTDocumentViewChangeSet
+
+@interface FSTDocumentViewChangeSet ()
+
+/** The set of all changes tracked so far, with redundant changes merged. */
+@property(nonatomic, strong)
+    FSTImmutableSortedDictionary<FSTDocumentKey *, FSTDocumentViewChange *> *changeMap;
+
+@end
+
+@implementation FSTDocumentViewChangeSet
+
++ (instancetype)changeSet {
+  return [[FSTDocumentViewChangeSet alloc] init];
+}
+
+- (instancetype)init {
+  self = [super init];
+  if (self) {
+    _changeMap = [FSTImmutableSortedDictionary dictionaryWithComparator:FSTDocumentKeyComparator];
+  }
+  return self;
+}
+
+- (NSString *)description {
+  return [self.changeMap description];
+}
+
+- (void)addChange:(FSTDocumentViewChange *)change {
+  FSTDocumentKey *key = change.document.key;
+  FSTDocumentViewChange *oldChange = [self.changeMap objectForKey:key];
+  if (!oldChange) {
+    self.changeMap = [self.changeMap dictionaryBySettingObject:change forKey:key];
+    return;
+  }
+
+  // Merge the new change with the existing change.
+  if (change.type != FSTDocumentViewChangeTypeAdded &&
+      oldChange.type == FSTDocumentViewChangeTypeMetadata) {
+    self.changeMap = [self.changeMap dictionaryBySettingObject:change forKey:key];
+
+  } else if (change.type == FSTDocumentViewChangeTypeMetadata &&
+             oldChange.type != FSTDocumentViewChangeTypeRemoved) {
+    FSTDocumentViewChange *newChange =
+        [FSTDocumentViewChange changeWithDocument:change.document type:oldChange.type];
+    self.changeMap = [self.changeMap dictionaryBySettingObject:newChange forKey:key];
+
+  } else if (change.type == FSTDocumentViewChangeTypeModified &&
+             oldChange.type == FSTDocumentViewChangeTypeModified) {
+    FSTDocumentViewChange *newChange =
+        [FSTDocumentViewChange changeWithDocument:change.document
+                                             type:FSTDocumentViewChangeTypeModified];
+    self.changeMap = [self.changeMap dictionaryBySettingObject:newChange forKey:key];
+  } else if (change.type == FSTDocumentViewChangeTypeModified &&
+             oldChange.type == FSTDocumentViewChangeTypeAdded) {
+    FSTDocumentViewChange *newChange =
+        [FSTDocumentViewChange changeWithDocument:change.document
+                                             type:FSTDocumentViewChangeTypeAdded];
+    self.changeMap = [self.changeMap dictionaryBySettingObject:newChange forKey:key];
+  } else if (change.type == FSTDocumentViewChangeTypeRemoved &&
+             oldChange.type == FSTDocumentViewChangeTypeAdded) {
+    self.changeMap = [self.changeMap dictionaryByRemovingObjectForKey:key];
+  } else if (change.type == FSTDocumentViewChangeTypeRemoved &&
+             oldChange.type == FSTDocumentViewChangeTypeModified) {
+    FSTDocumentViewChange *newChange =
+        [FSTDocumentViewChange changeWithDocument:oldChange.document
+                                             type:FSTDocumentViewChangeTypeRemoved];
+    self.changeMap = [self.changeMap dictionaryBySettingObject:newChange forKey:key];
+  } else if (change.type == FSTDocumentViewChangeTypeAdded &&
+             oldChange.type == FSTDocumentViewChangeTypeRemoved) {
+    FSTDocumentViewChange *newChange =
+        [FSTDocumentViewChange changeWithDocument:change.document
+                                             type:FSTDocumentViewChangeTypeModified];
+    self.changeMap = [self.changeMap dictionaryBySettingObject:newChange forKey:key];
+  } else {
+    // This includes these cases, which don't make sense:
+    // Added -> Added
+    // Removed -> Removed
+    // Modified -> Added
+    // Removed -> Modified
+    // Metadata -> Added
+    // Removed -> Metadata
+    FSTFail(@"Unsupported combination of changes: %ld after %ld", (long)change.type,
+            (long)oldChange.type);
+  }
+}
+
+- (NSArray<FSTDocumentViewChange *> *)changes {
+  NSMutableArray<FSTDocumentViewChange *> *changes = [NSMutableArray array];
+  [self.changeMap enumerateKeysAndObjectsUsingBlock:^(FSTDocumentKey *key,
+                                                      FSTDocumentViewChange *change, BOOL *stop) {
+    [changes addObject:change];
+  }];
+  return changes;
+}
+
+@end
+
+#pragma mark - FSTViewSnapshot
+
+@implementation FSTViewSnapshot
+
+- (instancetype)initWithQuery:(FSTQuery *)query
+                    documents:(FSTDocumentSet *)documents
+                 oldDocuments:(FSTDocumentSet *)oldDocuments
+              documentChanges:(NSArray<FSTDocumentViewChange *> *)documentChanges
+                    fromCache:(BOOL)fromCache
+             hasPendingWrites:(BOOL)hasPendingWrites
+             syncStateChanged:(BOOL)syncStateChanged {
+  self = [super init];
+  if (self) {
+    _query = query;
+    _documents = documents;
+    _oldDocuments = oldDocuments;
+    _documentChanges = documentChanges;
+    _fromCache = fromCache;
+    _hasPendingWrites = hasPendingWrites;
+    _syncStateChanged = syncStateChanged;
+  }
+  return self;
+}
+
+- (NSString *)description {
+  return [NSString stringWithFormat:
+                       @"<FSTViewSnapshot query:%@ documents:%@ oldDocument:%@ changes:%@ "
+                        "fromCache:%@ hasPendingWrites:%@ syncStateChanged:%@>",
+                       self.query, self.documents, self.oldDocuments, self.documentChanges,
+                       (self.fromCache ? @"YES" : @"NO"), (self.hasPendingWrites ? @"YES" : @"NO"),
+                       (self.syncStateChanged ? @"YES" : @"NO")];
+}
+
+- (BOOL)isEqual:(id)object {
+  if (self == object) {
+    return YES;
+  } else if (![object isKindOfClass:[FSTViewSnapshot class]]) {
+    return NO;
+  }
+
+  FSTViewSnapshot *other = object;
+  return [self.query isEqual:other.query] && [self.documents isEqual:other.documents] &&
+         [self.oldDocuments isEqual:other.oldDocuments] &&
+         [self.documentChanges isEqualToArray:other.documentChanges] &&
+         self.fromCache == other.fromCache && self.hasPendingWrites == other.hasPendingWrites &&
+         self.syncStateChanged == other.syncStateChanged;
+}
+
+- (NSUInteger)hash {
+  NSUInteger result = [self.query hash];
+  result = 31 * result + [self.documents hash];
+  result = 31 * result + [self.oldDocuments hash];
+  result = 31 * result + [self.documentChanges hash];
+  result = 31 * result + (self.fromCache ? 1231 : 1237);
+  result = 31 * result + (self.hasPendingWrites ? 1231 : 1237);
+  result = 31 * result + (self.syncStateChanged ? 1231 : 1237);
+  return result;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END