diff options
Diffstat (limited to 'Firestore/Source/Core/FSTView.mm')
| -rw-r--r-- | Firestore/Source/Core/FSTView.mm | 479 |
1 files changed, 479 insertions, 0 deletions
diff --git a/Firestore/Source/Core/FSTView.mm b/Firestore/Source/Core/FSTView.mm new file mode 100644 index 0000000..d6b4558 --- /dev/null +++ b/Firestore/Source/Core/FSTView.mm @@ -0,0 +1,479 @@ +/* + * 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 "Firestore/Source/Core/FSTView.h" + +#import "Firestore/Source/Core/FSTQuery.h" +#import "Firestore/Source/Core/FSTViewSnapshot.h" +#import "Firestore/Source/Model/FSTDocument.h" +#import "Firestore/Source/Model/FSTDocumentKey.h" +#import "Firestore/Source/Model/FSTDocumentSet.h" +#import "Firestore/Source/Model/FSTFieldValue.h" +#import "Firestore/Source/Remote/FSTRemoteEvent.h" +#import "Firestore/Source/Util/FSTAssert.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]; +} + +- (NSUInteger)hash { + NSUInteger hash = self.type; + hash = hash * 31u + [self.key hash]; + return hash; +} + +@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); + }]; + [self applyTargetChange:targetChange]; + NSArray<FSTLimboDocumentChange *> *limboChanges = [self updateLimboDocuments]; + 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]; + } +} + +- (FSTViewChange *)applyChangedOnlineState:(FSTOnlineState)onlineState { + if (self.isCurrent && onlineState == FSTOnlineStateFailed) { + // If we're offline, set `current` to NO and then call applyChanges to refresh our syncState + // and generate an FSTViewChange as appropriate. We are guaranteed to get a new FSTTargetChange + // that sets `current` back to YES once the client is back online. + self.current = NO; + return + [self applyChangesToDocuments:[[FSTViewDocumentChanges alloc] + initWithDocumentSet:self.documentSet + changeSet:[FSTDocumentViewChangeSet changeSet] + needsRefill:NO + mutatedKeys:self.mutatedKeys]]; + } else { + // No effect, just return a no-op FSTViewChange. + return [[FSTViewChange alloc] initWithSnapshot:nil 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 and current based on the given change. + */ +- (void)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; + } + } +} + +/** Updates limboDocuments and returns any changes as FSTLimboDocumentChanges. */ +- (NSArray<FSTLimboDocumentChange *> *)updateLimboDocuments { + // We can only determine limbo documents when we're in-sync with the server. + if (!self.isCurrent) { + return @[]; + } + + // TODO(klimt): Do this incrementally so that it's not quadratic when updating many documents. + FSTDocumentKeySet *oldLimboDocuments = self.limboDocuments; + self.limboDocuments = [FSTDocumentKeySet keySet]; + 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 |