Initial

13 files changed, 1717 insertions, 0 deletions

diff --git a/Firebase/Database/Snapshot/FChildrenNode.h b/Firebase/Database/Snapshot/FChildrenNode.h
new file mode 100644
index 0000000..9eebdae
--- /dev/null
+++ b/Firebase/Database/Snapshot/FChildrenNode.h
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+#import "FNode.h"
+#import "FTypedefs.h"
+#import "FTypedefs_Private.h"
+#import "FImmutableSortedDictionary.h"
+
+@class FNamedNode;
+
+@interface FChildrenNode : NSObject <FNode>
+
+- (id)initWithChildren:(FImmutableSortedDictionary *)someChildren;
+- (id)initWithPriority:(id<FNode>)aPriority children:(FImmutableSortedDictionary *)someChildren;
+
+// FChildrenNode specific methods
+
+- (void) enumerateChildrenAndPriorityUsingBlock:(void (^)(NSString *, id<FNode>, BOOL *))block;
+
+- (FNamedNode *) firstChild;
+- (FNamedNode *) lastChild;
+
+@property (nonatomic, strong) FImmutableSortedDictionary* children;
+@property (nonatomic, strong) id<FNode> priorityNode;
+
+@end
diff --git a/Firebase/Database/Snapshot/FChildrenNode.m b/Firebase/Database/Snapshot/FChildrenNode.m
new file mode 100644
index 0000000..b5598ad
--- /dev/null
+++ b/Firebase/Database/Snapshot/FChildrenNode.m
@@ -0,0 +1,385 @@
+/*
+ * 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 "FChildrenNode.h"
+#import "FEmptyNode.h"
+#import "FConstants.h"
+#import "FStringUtilities.h"
+#import "FUtilities.h"
+#import "FNamedNode.h"
+#import "FMaxNode.h"
+#import "FTransformedEnumerator.h"
+#import "FSnapshotUtilities.h"
+#import "FTransformedEnumerator.h"
+#import "FPriorityIndex.h"
+#import "FUtilities.h"
+
+@interface FChildrenNode ()
+@property (nonatomic, strong) NSString *lazyHash;
+@end
+
+@implementation FChildrenNode
+
+// Note: The only reason we allow nil priority is to for EmptyNode, since we can't use
+// EmptyNode as the priority of EmptyNode.  We might want to consider making EmptyNode its own
+// class instead of an empty ChildrenNode.
+
+- (id)init {
+    return [self initWithPriority:nil children:[FImmutableSortedDictionary dictionaryWithComparator:[FUtilities keyComparator]]];
+}
+
+- (id)initWithChildren:(FImmutableSortedDictionary *)someChildren {
+    return [self initWithPriority:nil children:someChildren];
+}
+
+- (id)initWithPriority:(id<FNode>)aPriority children:(FImmutableSortedDictionary *)someChildren {
+    if (someChildren.isEmpty && aPriority != nil && ![aPriority isEmpty]) {
+        [NSException raise:NSInvalidArgumentException format:@"Can't create empty node with priority!"];
+    }
+    self = [super init];
+    if(self) {
+        self.children = someChildren;
+        self.priorityNode = aPriority;
+    }
+    return self;
+}
+
+- (NSString *) description {
+    return [[self valForExport:YES] description];
+}
+
+#pragma mark -
+#pragma mark FNode methods
+
+
+- (BOOL) isLeafNode {
+    return NO;
+}
+
+- (id<FNode>) getPriority {
+    if (self.priorityNode) {
+        return self.priorityNode;
+    } else {
+        return [FEmptyNode emptyNode];
+    }
+
+}
+
+- (id<FNode>) updatePriority:(id<FNode>)aPriority {
+    if ([self.children isEmpty]) {
+        return [FEmptyNode emptyNode];
+    } else {
+        return [[FChildrenNode alloc] initWithPriority:aPriority children:self.children];
+    }
+}
+
+- (id<FNode>) getImmediateChild:(NSString *) childName {
+    if ([childName isEqualToString:@".priority"]) {
+        return [self getPriority];
+    } else {
+        id <FNode> child = [self.children objectForKey:childName];
+        return (child == nil) ? [FEmptyNode emptyNode] : child;
+    }
+}
+
+- (id<FNode>) getChild:(FPath *)path {
+    NSString* front = [path getFront];
+    if(front == nil) {
+        return self;
+    }
+    else {
+        return [[self getImmediateChild:front] getChild:[path popFront]];
+    }
+}
+
+- (BOOL)hasChild:(NSString *)childName {
+    return ![self getImmediateChild:childName].isEmpty;
+}
+
+
+- (id<FNode>) updateImmediateChild:(NSString *)childName withNewChild:(id<FNode>)newChildNode {
+    NSAssert(newChildNode != nil, @"Should always be passing nodes.");
+
+    if ([childName isEqualToString:@".priority"]) {
+        return [self updatePriority:newChildNode];
+    } else {
+        FImmutableSortedDictionary *newChildren;
+        if (newChildNode.isEmpty) {
+            newChildren = [self.children removeObjectForKey:childName];
+        } else {
+            newChildren = [self.children setObject:newChildNode forKey:childName];
+        }
+        if (newChildren.isEmpty) {
+            return [FEmptyNode emptyNode];
+        } else {
+            return [[FChildrenNode alloc] initWithPriority:self.getPriority children:newChildren];
+        }
+    }
+}
+
+- (id<FNode>) updateChild:(FPath *)path withNewChild:(id<FNode>)newChildNode {
+    NSString* front = [path getFront];
+    if(front == nil) {
+        return newChildNode;
+    } else {
+        NSAssert(![front isEqualToString:@".priority"] || path.length == 1, @".priority must be the last token in a path.");
+        id<FNode> newImmediateChild = [[self getImmediateChild:front] updateChild:[path popFront] withNewChild:newChildNode];
+        return [self updateImmediateChild:front withNewChild:newImmediateChild];
+    }
+}
+
+- (BOOL) isEmpty {
+    return [self.children isEmpty];
+}
+
+- (int) numChildren {
+    return [self.children count];
+}
+
+- (id) val {
+    return [self valForExport:NO];
+}
+
+- (id) valForExport:(BOOL)exp {
+    if([self isEmpty]) {
+        return [NSNull null];
+    }
+    
+    __block int numKeys = 0;
+    __block NSInteger maxKey = 0;
+    __block BOOL allIntegerKeys = YES;
+
+    NSMutableDictionary* obj = [[NSMutableDictionary alloc] initWithCapacity:[self.children count]];
+    [self enumerateChildrenUsingBlock:^(NSString *key, id<FNode> childNode, BOOL *stop) {
+        [obj setObject:[childNode valForExport:exp] forKey:key];
+
+        numKeys++;
+
+        // If we already found a string key, don't bother with any of this
+        if (!allIntegerKeys) {
+            return;
+        }
+
+        // Treat leading zeroes that are not exactly "0" as strings
+        NSString* firstChar = [key substringWithRange:NSMakeRange(0, 1)];
+        if ([firstChar isEqualToString:@"0"] && [key length] > 1) {
+            allIntegerKeys = NO;
+        } else {
+            NSNumber *keyAsNum = [FUtilities intForString:key];
+            if (keyAsNum != nil) {
+                NSInteger keyAsInt = [keyAsNum integerValue];
+                if (keyAsInt > maxKey) {
+                    maxKey = keyAsInt;
+                }
+            } else {
+                allIntegerKeys = NO;
+            }
+        }
+    }];
+
+    if (!exp && allIntegerKeys && maxKey < 2 * numKeys) {
+        // convert to an array
+        NSMutableArray* array = [[NSMutableArray alloc] initWithCapacity:maxKey + 1];
+        for (int i = 0; i <= maxKey; ++i) {
+            NSString* keyString = [NSString stringWithFormat:@"%i", i];
+            id child = obj[keyString];
+            if (child != nil) {
+                [array addObject:child];
+            } else {
+                [array addObject:[NSNull null]];
+            }
+        }
+        return array;
+    } else {
+
+        if(exp && [self getPriority] != nil && !self.getPriority.isEmpty) {
+            obj[kPayloadPriority] = [self.getPriority val];
+        }
+        
+        return obj;
+    }
+}
+
+- (NSString *) dataHash {
+    if (self.lazyHash == nil) {
+        NSMutableString *toHash = [[NSMutableString alloc] init];
+
+        if (!self.getPriority.isEmpty) {
+            [toHash appendString:@"priority:"];
+            [FSnapshotUtilities appendHashRepresentationForLeafNode:(FLeafNode *)self.getPriority
+                                                           toString:toHash
+                                                        hashVersion:FDataHashVersionV1];
+            [toHash appendString:@":"];
+        }
+
+        __block BOOL sawPriority = NO;
+        [self enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+            sawPriority = sawPriority || [[node getPriority] isEmpty];
+            *stop = sawPriority;
+        }];
+        if (sawPriority) {
+            NSMutableArray *array = [NSMutableArray array];
+            [self enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+                FNamedNode *namedNode = [[FNamedNode alloc] initWithName:key andNode:node];
+                [array addObject:namedNode];
+            }];
+            [array sortUsingComparator:^NSComparisonResult(FNamedNode *namedNode1, FNamedNode *namedNode2) {
+                return [[FPriorityIndex priorityIndex] compareNamedNode:namedNode1 toNamedNode:namedNode2];
+            }];
+            [array enumerateObjectsUsingBlock:^(FNamedNode *namedNode, NSUInteger idx, BOOL *stop) {
+                NSString *childHash = [namedNode.node dataHash];
+                if (![childHash isEqualToString:@""]) {
+                    [toHash appendFormat:@":%@:%@", namedNode.name, childHash];
+                }
+            }];
+        } else {
+            [self enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+                NSString *childHash = [node dataHash];
+                if (![childHash isEqualToString:@""]) {
+                    [toHash appendFormat:@":%@:%@", key, childHash];
+                }
+            }];
+        }
+        self.lazyHash = [toHash isEqualToString:@""] ? @"" : [FStringUtilities base64EncodedSha1:toHash];
+    }
+    return self.lazyHash;
+}
+
+- (NSComparisonResult)compare:(id <FNode>)other {
+    // children nodes come last, unless this is actually an empty node, then we come first.
+    if (self.isEmpty) {
+        if (other.isEmpty) {
+            return NSOrderedSame;
+        } else {
+            return NSOrderedAscending;
+        }
+    } else if (other.isLeafNode || other.isEmpty) {
+        return NSOrderedDescending;
+    } else if (other == [FMaxNode maxNode]) {
+        return NSOrderedAscending;
+    } else {
+        // Must be another node with children.
+        return NSOrderedSame;
+    }
+}
+
+- (BOOL)isEqual:(id <FNode>)other {
+    if (other == self) {
+        return YES;
+    } else if (other == nil) {
+        return NO;
+    } else if (other.isLeafNode) {
+        return NO;
+    } else if (self.isEmpty && [other isEmpty]) {
+        // Empty nodes do not have priority
+        return YES;
+    } else {
+        FChildrenNode *otherChildrenNode = other;
+        if (![self.getPriority isEqual:other.getPriority]) {
+            return NO;
+        } else if (self.children.count == otherChildrenNode.children.count) {
+            __block BOOL equal = YES;
+            [self enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+                id<FNode> child = [otherChildrenNode getImmediateChild:key];
+                if (![child isEqual:node]) {
+                    equal = NO;
+                    *stop = YES;
+                }
+            }];
+            return equal;
+        } else {
+            return NO;
+        }
+    }
+}
+
+- (NSUInteger)hash {
+    __block NSUInteger hashCode = 0;
+    [self enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+        hashCode = 31 * hashCode + key.hash;
+        hashCode = 17 * hashCode + node.hash;
+    }];
+    return 17 * hashCode + self.priorityNode.hash;
+}
+
+- (void) enumerateChildrenAndPriorityUsingBlock:(void (^)(NSString *, id<FNode>, BOOL *))block
+{
+    if ([self.getPriority isEmpty]) {
+        [self enumerateChildrenUsingBlock:block];
+    } else {
+        __block BOOL passedPriorityKey = NO;
+        [self enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+            if (!passedPriorityKey && [FUtilities compareKey:key toKey:@".priority"] == NSOrderedDescending) {
+                passedPriorityKey = YES;
+                BOOL stopAfterPriority = NO;
+                block(@".priority", [self getPriority], &stopAfterPriority);
+                if (stopAfterPriority) return;
+            }
+            block(key, node, stop);
+        }];
+    }
+}
+
+- (void) enumerateChildrenUsingBlock:(void (^)(NSString *, id<FNode>, BOOL *))block
+{
+    [self.children enumerateKeysAndObjectsUsingBlock:block];
+}
+
+- (void) enumerateChildrenReverse:(BOOL)reverse usingBlock:(void (^)(NSString *, id<FNode>, BOOL *))block
+{
+    [self.children enumerateKeysAndObjectsReverse:reverse usingBlock:block];
+}
+
+- (NSEnumerator *)childEnumerator
+{
+    return [[FTransformedEnumerator alloc] initWithEnumerator:self.children.keyEnumerator andTransform:^id(NSString *key) {
+        return [FNamedNode nodeWithName:key node:[self getImmediateChild:key]];
+    }];
+}
+
+- (NSString *) predecessorChildKey:(NSString *)childKey
+{
+    return [self.children getPredecessorKey:childKey];
+}
+
+#pragma mark -
+#pragma mark FChildrenNode specific methods
+
+- (id) childrenGetter:(id)key {
+    return [self.children objectForKey:key];
+}
+
+- (FNamedNode *)firstChild
+{
+    NSString *childKey = self.children.minKey;
+    if (childKey) {
+        return [[FNamedNode alloc] initWithName:childKey andNode:[self getImmediateChild:childKey]];
+    } else {
+        return nil;
+    }
+}
+
+- (FNamedNode *)lastChild
+{
+    NSString *childKey = self.children.maxKey;
+    if (childKey) {
+        return [[FNamedNode alloc] initWithName:childKey andNode:[self getImmediateChild:childKey]];
+    } else {
+        return nil;
+    }
+}
+
+@end
diff --git a/Firebase/Database/Snapshot/FCompoundWrite.h b/Firebase/Database/Snapshot/FCompoundWrite.h
new file mode 100644
index 0000000..c67cfc7
--- /dev/null
+++ b/Firebase/Database/Snapshot/FCompoundWrite.h
@@ -0,0 +1,61 @@
+/*
+ * 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 FImmutableTree;
+@protocol FNode;
+@class FPath;
+
+/**
+* This class holds a collection of writes that can be applied to nodes in unison. It abstracts away the logic with
+* dealing with priority writes and multiple nested writes. At any given path, there is only allowed to be one write
+* modifying that path. Any write to an existing path or shadowing an existing path will modify that existing write to
+* reflect the write added.
+*/
+@interface FCompoundWrite : NSObject
+
+- (id) initWithWriteTree:(FImmutableTree *)tree;
+
+/**
+ * Creates a compound write with NSDictionary from path string to object
+ */
++ (FCompoundWrite *) compoundWriteWithValueDictionary:(NSDictionary *)dictionary;
+/**
+ * Creates a compound write with NSDictionary from path string to node
+ */
++ (FCompoundWrite *) compoundWriteWithNodeDictionary:(NSDictionary *)dictionary;
+
++ (FCompoundWrite *) emptyWrite;
+
+- (FCompoundWrite *) addWrite:(id<FNode>)node atPath:(FPath *)path;
+- (FCompoundWrite *) addWrite:(id<FNode>)node atKey:(NSString *)key;
+- (FCompoundWrite *) addCompoundWrite:(FCompoundWrite *)node atPath:(FPath *)path;
+- (FCompoundWrite *) removeWriteAtPath:(FPath *)path;
+- (id<FNode>)rootWrite;
+- (BOOL) hasCompleteWriteAtPath:(FPath *)path;
+- (id<FNode>) completeNodeAtPath:(FPath *)path;
+- (NSArray *) completeChildren;
+- (NSDictionary *)childCompoundWrites;
+- (FCompoundWrite *) childCompoundWriteAtPath:(FPath *)path;
+- (id<FNode>) applyToNode:(id<FNode>)node;
+- (void)enumerateWrites:(void (^)(FPath *path, id<FNode>node, BOOL *stop))block;
+
+- (NSDictionary *)valForExport:(BOOL)exportFormat;
+
+- (BOOL) isEmpty;
+
+@end
diff --git a/Firebase/Database/Snapshot/FCompoundWrite.m b/Firebase/Database/Snapshot/FCompoundWrite.m
new file mode 100644
index 0000000..8887095
--- /dev/null
+++ b/Firebase/Database/Snapshot/FCompoundWrite.m
@@ -0,0 +1,257 @@
+/*
+ * 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 "FCompoundWrite.h"
+#import "FImmutableTree.h"
+#import "FNode.h"
+#import "FPath.h"
+#import "FNamedNode.h"
+#import "FSnapshotUtilities.h"
+
+@interface FCompoundWrite ()
+@property (nonatomic, strong) FImmutableTree *writeTree;
+@end
+
+@implementation FCompoundWrite
+
+- (id) initWithWriteTree:(FImmutableTree *)tree {
+    self = [super init];
+    if (self) {
+        self.writeTree = tree;
+    }
+    return self;
+}
+
++ (FCompoundWrite *)compoundWriteWithValueDictionary:(NSDictionary *)dictionary {
+    __block FImmutableTree *writeTree = [FImmutableTree empty];
+    [dictionary enumerateKeysAndObjectsUsingBlock:^(NSString *pathString, id value, BOOL *stop) {
+        id<FNode> node = [FSnapshotUtilities nodeFrom:value];
+        FImmutableTree *tree = [[FImmutableTree alloc] initWithValue:node];
+        writeTree = [writeTree setTree:tree atPath:[[FPath alloc] initWith:pathString]];
+    }];
+    return [[FCompoundWrite alloc] initWithWriteTree:writeTree];
+}
+
++ (FCompoundWrite *)compoundWriteWithNodeDictionary:(NSDictionary *)dictionary {
+    __block FImmutableTree *writeTree = [FImmutableTree empty];
+    [dictionary enumerateKeysAndObjectsUsingBlock:^(NSString *pathString, id node, BOOL *stop) {
+        FImmutableTree *tree = [[FImmutableTree alloc] initWithValue:node];
+        writeTree = [writeTree setTree:tree atPath:[[FPath alloc] initWith:pathString]];
+    }];
+    return [[FCompoundWrite alloc] initWithWriteTree:writeTree];
+}
+
++ (FCompoundWrite *) emptyWrite {
+    static dispatch_once_t pred = 0;
+    static FCompoundWrite *empty = nil;
+    dispatch_once(&pred, ^{
+        empty = [[FCompoundWrite alloc] initWithWriteTree:[[FImmutableTree alloc] initWithValue:nil]];
+    });
+    return empty;
+}
+
+- (FCompoundWrite *) addWrite:(id<FNode>)node atPath:(FPath *)path {
+    if (path.isEmpty) {
+        return [[FCompoundWrite alloc] initWithWriteTree:[[FImmutableTree alloc] initWithValue:node]];
+    } else {
+        FTuplePathValue *rootMost = [self.writeTree findRootMostValueAndPath:path];
+        if (rootMost != nil) {
+            FPath *relativePath = [FPath relativePathFrom:rootMost.path to:path];
+            id<FNode> value = [rootMost.value updateChild:relativePath withNewChild:node];
+            return [[FCompoundWrite alloc] initWithWriteTree:[self.writeTree setValue:value atPath:rootMost.path]];
+        } else {
+            FImmutableTree *subtree = [[FImmutableTree alloc] initWithValue:node];
+            FImmutableTree *newWriteTree = [self.writeTree setTree:subtree atPath:path];
+            return [[FCompoundWrite alloc] initWithWriteTree:newWriteTree];
+        }
+    }
+}
+
+- (FCompoundWrite *) addWrite:(id<FNode>)node atKey:(NSString *)key {
+    return [self addWrite:node atPath:[[FPath alloc] initWith:key]];
+}
+
+- (FCompoundWrite *) addCompoundWrite:(FCompoundWrite *)compoundWrite atPath:(FPath *)path {
+    __block FCompoundWrite *newWrite = self;
+    [compoundWrite.writeTree forEach:^(FPath *childPath, id<FNode> value) {
+        newWrite = [newWrite addWrite:value atPath:[path child:childPath]];
+    }];
+    return newWrite;
+}
+
+/**
+* Will remove a write at the given path and deeper paths. This will <em>not</em> modify a write at a higher location,
+* which must be removed by calling this method with that path.
+* @param path The path at which a write and all deeper writes should be removed.
+* @return The new FWriteCompound with the removed path.
+*/
+- (FCompoundWrite *) removeWriteAtPath:(FPath *)path {
+    if (path.isEmpty) {
+        return [FCompoundWrite emptyWrite];
+    } else {
+        FImmutableTree *newWriteTree = [self.writeTree setTree:[FImmutableTree empty] atPath:path];
+        return [[FCompoundWrite alloc] initWithWriteTree:newWriteTree];
+    }
+}
+
+/**
+* Returns whether this FCompoundWrite will fully overwrite a node at a given location and can therefore be considered
+* "complete".
+* @param path The path to check for
+* @return Whether there is a complete write at that path.
+*/
+- (BOOL) hasCompleteWriteAtPath:(FPath *)path {
+    return [self completeNodeAtPath:path] != nil;
+}
+
+/**
+* Returns a node for a path if and only if the node is a "complete" overwrite at that path. This will not aggregate
+* writes from depeer paths, but will return child nodes from a more shallow path.
+* @param path The path to get a complete write
+* @return The node if complete at that path, or nil otherwise.
+*/
+- (id<FNode>) completeNodeAtPath:(FPath *)path {
+    FTuplePathValue *rootMost = [self.writeTree findRootMostValueAndPath:path];
+    if (rootMost != nil) {
+        FPath *relativePath = [FPath relativePathFrom:rootMost.path to:path];
+        return [rootMost.value getChild:relativePath];
+    } else {
+        return nil;
+    }
+}
+
+// TODO: change into traversal method...
+- (NSArray *) completeChildren {
+    NSMutableArray *children = [[NSMutableArray alloc] init];
+    if (self.writeTree.value != nil) {
+        id<FNode> node = self.writeTree.value;
+        [node enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+            [children addObject:[[FNamedNode alloc] initWithName:key andNode:node]];
+        }];
+    } else {
+        [self.writeTree.children enumerateKeysAndObjectsUsingBlock:^(NSString *childKey, FImmutableTree *childTree, BOOL *stop) {
+            if (childTree.value != nil) {
+                [children addObject:[[FNamedNode alloc] initWithName:childKey andNode:childTree.value]];
+            }
+        }];
+    }
+    return children;
+}
+
+
+// TODO: change into enumarate method
+- (NSDictionary *)childCompoundWrites {
+    NSMutableDictionary *dict = [NSMutableDictionary dictionary];
+    [self.writeTree.children enumerateKeysAndObjectsUsingBlock:^(NSString *key, FImmutableTree *childWrite, BOOL *stop) {
+        dict[key] = [[FCompoundWrite alloc] initWithWriteTree:childWrite];
+    }];
+    return dict;
+}
+
+- (FCompoundWrite *) childCompoundWriteAtPath:(FPath *)path {
+    if (path.isEmpty) {
+        return self;
+    } else {
+        id<FNode> shadowingNode = [self completeNodeAtPath:path];
+        if (shadowingNode != nil) {
+            return [[FCompoundWrite alloc] initWithWriteTree:[[FImmutableTree alloc] initWithValue:shadowingNode]];
+        } else {
+            return [[FCompoundWrite alloc] initWithWriteTree:[self.writeTree subtreeAtPath:path]];
+        }
+    }
+}
+
+- (id<FNode>) applySubtreeWrite:(FImmutableTree *)subtreeWrite atPath:(FPath *)relativePath toNode:(id<FNode>)node {
+    if (subtreeWrite.value != nil) {
+        // Since a write there is always a leaf, we're done here.
+        return [node updateChild:relativePath withNewChild:subtreeWrite.value];
+    } else {
+        __block id<FNode> priorityWrite = nil;
+        __block id<FNode> blockNode = node;
+        [subtreeWrite.children enumerateKeysAndObjectsUsingBlock:^(NSString *childKey, FImmutableTree *childTree, BOOL *stop) {
+            if ([childKey isEqualToString:@".priority"]) {
+                // Apply priorities at the end so we don't update priorities for either empty nodes or forget to apply
+                // priorities to empty nodes that are later filled.
+                NSAssert(childTree.value != nil, @"Priority writes must always be leaf nodes");
+                priorityWrite = childTree.value;
+            } else {
+                blockNode = [self applySubtreeWrite:childTree atPath:[relativePath childFromString:childKey] toNode:blockNode];
+            }
+        }];
+        // If there was a priority write, we only apply it if the node is not empty
+        if (![blockNode getChild:relativePath].isEmpty && priorityWrite != nil) {
+            blockNode = [blockNode updateChild:[relativePath childFromString:@".priority"] withNewChild:priorityWrite];
+        }
+        return blockNode;
+    }
+}
+
+- (void)enumerateWrites:(void (^)(FPath *, id<FNode>, BOOL *))block {
+    __block BOOL stop = NO;
+    // TODO: add stop to tree iterator...
+    [self.writeTree forEach:^(FPath *path, id value) {
+        if (!stop) {
+            block(path, value, &stop);
+        }
+    }];
+}
+
+/**
+* Applies this FCompoundWrite to a node. The node is returned with all writes from this FCompoundWrite applied to the node.
+* @param node The node to apply this FCompoundWrite to
+* @return The node with all writes applied
+*/
+- (id<FNode>) applyToNode:(id<FNode>)node {
+    return [self applySubtreeWrite:self.writeTree atPath:[FPath empty] toNode:node];
+}
+
+/**
+* Return true if this CompoundWrite is empty and therefore does not modify any nodes.
+* @return Whether this CompoundWrite is empty
+*/
+- (BOOL) isEmpty {
+    return self.writeTree.isEmpty;
+}
+
+- (id<FNode>) rootWrite {
+    return self.writeTree.value;
+}
+
+- (BOOL)isEqual:(id)object {
+    if (![object isKindOfClass:[FCompoundWrite class]]) {
+        return NO;
+    }
+    FCompoundWrite *other = (FCompoundWrite *)object;
+    return [[self valForExport:YES] isEqualToDictionary:[other valForExport:YES]];
+}
+
+- (NSUInteger)hash {
+    return [[self valForExport:YES] hash];
+}
+
+- (NSDictionary *)valForExport:(BOOL)exportFormat {
+    NSMutableDictionary *dictionary = [NSMutableDictionary dictionary];
+    [self.writeTree forEach:^(FPath *path, id<FNode> value) {
+        dictionary[path.wireFormat] = [value valForExport:exportFormat];
+    }];
+    return dictionary;
+}
+
+- (NSString *)description {
+    return [[self valForExport:YES] description];
+}
+
+@end
diff --git a/Firebase/Database/Snapshot/FEmptyNode.h b/Firebase/Database/Snapshot/FEmptyNode.h
new file mode 100644
index 0000000..ab404c2
--- /dev/null
+++ b/Firebase/Database/Snapshot/FEmptyNode.h
@@ -0,0 +1,24 @@
+/*
+ * 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 "FNode.h"
+
+@interface FEmptyNode : NSObject
+
++ (id<FNode>) emptyNode;
+
+@end
diff --git a/Firebase/Database/Snapshot/FEmptyNode.m b/Firebase/Database/Snapshot/FEmptyNode.m
new file mode 100644
index 0000000..dd2d9ea
--- /dev/null
+++ b/Firebase/Database/Snapshot/FEmptyNode.m
@@ -0,0 +1,29 @@
+/*
+ * 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 "FEmptyNode.h"
+#import "FChildrenNode.h"
+
+@implementation FEmptyNode
+
++ (id<FNode>) emptyNode {
+    static FChildrenNode* empty = nil;
+    if (empty == nil) {
+        empty = [[FChildrenNode alloc] init];
+    }
+    return empty;
+}
+@end
diff --git a/Firebase/Database/Snapshot/FIndexedNode.h b/Firebase/Database/Snapshot/FIndexedNode.h
new file mode 100644
index 0000000..fd2db37
--- /dev/null
+++ b/Firebase/Database/Snapshot/FIndexedNode.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+#import <Foundation/Foundation.h>
+
+#import "FNode.h"
+#import "FIndex.h"
+#import "FNamedNode.h"
+
+/**
+ * Represents a node together with an index. The index and node are updated in unison. In the case where the index
+ * does not affect the ordering (i.e. the ordering is identical to the key ordering) this class uses a fallback index
+ * to save memory. Everything operating on the index must special case the fallback index.
+ */
+@interface FIndexedNode : NSObject
+
+@property (nonatomic, strong, readonly) id<FNode> node;
+
++ (FIndexedNode *)indexedNodeWithNode:(id<FNode>)node;
++ (FIndexedNode *)indexedNodeWithNode:(id<FNode>)node index:(id<FIndex>)index;
+
+- (BOOL)hasIndex:(id<FIndex>)index;
+- (FIndexedNode *)updateChild:(NSString *)key withNewChild:(id<FNode>)newChildNode;
+- (FIndexedNode *)updatePriority:(id<FNode>)priority;
+
+- (FNamedNode *)firstChild;
+- (FNamedNode *)lastChild;
+
+- (NSString *)predecessorForChildKey:(NSString *)childKey childNode:(id<FNode>)childNode index:(id<FIndex>)index;
+
+- (void)enumerateChildrenReverse:(BOOL)reverse usingBlock:(void (^)(NSString *key, id<FNode> node, BOOL *stop))block;
+
+- (NSEnumerator *)childEnumerator;
+
+@end
diff --git a/Firebase/Database/Snapshot/FIndexedNode.m b/Firebase/Database/Snapshot/FIndexedNode.m
new file mode 100644
index 0000000..e874dcf
--- /dev/null
+++ b/Firebase/Database/Snapshot/FIndexedNode.m
@@ -0,0 +1,202 @@
+/*
+ * 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 "FIndexedNode.h"
+
+#import "FImmutableSortedSet.h"
+#import "FIndex.h"
+#import "FPriorityIndex.h"
+#import "FKeyIndex.h"
+#import "FChildrenNode.h"
+
+static FImmutableSortedSet *FALLBACK_INDEX;
+
+@interface FIndexedNode ()
+
+@property (nonatomic, strong) id<FNode> node;
+/**
+ * The indexed set is initialized lazily to prevent creation when it is not needed
+ */
+@property (nonatomic, strong) FImmutableSortedSet *indexed;
+@property (nonatomic, strong) id<FIndex> index;
+
+@end
+
+@implementation FIndexedNode
+
++ (FImmutableSortedSet *)fallbackIndex {
+    static FImmutableSortedSet *fallbackIndex;
+    static dispatch_once_t once;
+    dispatch_once(&once, ^{
+        fallbackIndex = [[FImmutableSortedSet alloc] init];
+    });
+    return fallbackIndex;
+}
+
++ (FIndexedNode *)indexedNodeWithNode:(id<FNode>)node
+{
+    return [[FIndexedNode alloc] initWithNode:node index:[FPriorityIndex priorityIndex]];
+}
+
++ (FIndexedNode *)indexedNodeWithNode:(id<FNode>)node index:(id<FIndex>)index
+{
+    return [[FIndexedNode alloc] initWithNode:node index:index];
+}
+
+- (id)initWithNode:(id<FNode>)node index:(id<FIndex>)index
+{
+    // Initialize indexed lazily
+    return [self initWithNode:node index:index indexed:nil];
+}
+
+- (id)initWithNode:(id<FNode>)node index:(id<FIndex>)index indexed:(FImmutableSortedSet *)indexed
+{
+    self = [super init];
+    if (self != nil) {
+        self->_node = node;
+        self->_index = index;
+        self->_indexed = indexed;
+    }
+    return self;
+}
+
+- (void)ensureIndexed
+{
+    if (!self.indexed) {
+        if ([self.index isEqual:[FKeyIndex keyIndex]]) {
+            self.indexed = [FIndexedNode fallbackIndex];
+        } else {
+            __block BOOL sawChild;
+            [self.node enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+                sawChild = sawChild || [self.index isDefinedOn:node];
+                *stop = sawChild;
+            }];
+            if (sawChild) {
+                NSMutableDictionary *dict = [NSMutableDictionary dictionary];
+                [self.node enumerateChildrenUsingBlock:^(NSString *key, id<FNode> node, BOOL *stop) {
+                    FNamedNode *namedNode = [[FNamedNode alloc] initWithName:key andNode:node];
+                    dict[namedNode] = [NSNull null];
+                }];
+                // Make sure to assign index here, because the comparator will be retained and using self will cause a
+                // cycle
+                id<FIndex> index = self.index;
+                self.indexed = [FImmutableSortedSet setWithKeysFromDictionary:dict
+                                                                   comparator:^NSComparisonResult(FNamedNode *namedNode1, FNamedNode *namedNode2) {
+                    return [index compareNamedNode:namedNode1 toNamedNode:namedNode2];
+                }];
+            } else {
+                self.indexed = [FIndexedNode fallbackIndex];
+            }
+        }
+    }
+}
+
+- (BOOL)hasIndex:(id<FIndex>)index
+{
+    return [self.index isEqual:index];
+}
+
+- (FIndexedNode *)updateChild:(NSString *)key withNewChild:(id<FNode>)newChildNode
+{
+    id<FNode> newNode = [self.node updateImmediateChild:key withNewChild:newChildNode];
+    if (self.indexed == [FIndexedNode fallbackIndex] && ![self.index isDefinedOn:newChildNode]) {
+        // doesn't affect the index, no need to create an index
+        return [[FIndexedNode alloc] initWithNode:newNode index:self.index indexed:[FIndexedNode fallbackIndex]];
+    } else if (!self.indexed || self.indexed == [FIndexedNode fallbackIndex]) {
+        // No need to index yet, index lazily
+        return [[FIndexedNode alloc] initWithNode:newNode index:self.index];
+    } else {
+        id<FNode> oldChild = [self.node getImmediateChild:key];
+        FImmutableSortedSet *newIndexed = [self.indexed removeObject:[FNamedNode nodeWithName:key node:oldChild]];
+        if (![newChildNode isEmpty]) {
+            newIndexed = [newIndexed addObject:[FNamedNode nodeWithName:key node:newChildNode]];
+        }
+        return [[FIndexedNode alloc] initWithNode:newNode index:self.index indexed:newIndexed];
+    }
+}
+
+- (FIndexedNode *)updatePriority:(id<FNode>)priority
+{
+    return [[FIndexedNode alloc] initWithNode:[self.node updatePriority:priority]
+                                        index:self.index
+                                      indexed:self.indexed];
+}
+
+- (FNamedNode *)firstChild
+{
+    if (![self.node isKindOfClass:[FChildrenNode class]]) {
+        return nil;
+    } else {
+        [self ensureIndexed];
+        if (self.indexed == [FIndexedNode fallbackIndex]) {
+            return [((FChildrenNode *)self.node) firstChild];
+        } else {
+            return self.indexed.firstObject;
+        }
+    }
+}
+
+- (FNamedNode *)lastChild
+{
+    if (![self.node isKindOfClass:[FChildrenNode class]]) {
+        return nil;
+    } else {
+        [self ensureIndexed];
+        if (self.indexed == [FIndexedNode fallbackIndex]) {
+            return [((FChildrenNode *)self.node) lastChild];
+        } else {
+            return self.indexed.lastObject;
+        }
+    }
+}
+
+- (NSString *)predecessorForChildKey:(NSString *)childKey childNode:(id<FNode>)childNode index:(id<FIndex>)index
+{
+    if (![self.index isEqual:index]) {
+        [NSException raise:NSInvalidArgumentException format:@"Index not available in IndexedNode!"];
+    }
+    [self ensureIndexed];
+    if (self.indexed == [FIndexedNode fallbackIndex]) {
+        return [self.node predecessorChildKey:childKey];
+    } else {
+        FNamedNode *node = [self.indexed predecessorEntry:[FNamedNode nodeWithName:childKey node:childNode]];
+        return node.name;
+    }
+}
+
+- (void)enumerateChildrenReverse:(BOOL)reverse usingBlock:(void (^)(NSString *, id<FNode>, BOOL *))block
+{
+    [self ensureIndexed];
+    if (self.indexed == [FIndexedNode fallbackIndex]) {
+        [self.node enumerateChildrenReverse:reverse usingBlock:block];
+    } else {
+        [self.indexed enumerateObjectsReverse:reverse usingBlock:^(FNamedNode *namedNode, BOOL *stop) {
+            block(namedNode.name, namedNode.node, stop);
+        }];
+    }
+}
+
+- (NSEnumerator *)childEnumerator
+{
+    [self ensureIndexed];
+    if (self.indexed == [FIndexedNode fallbackIndex]) {
+        return [self.node childEnumerator];
+    } else {
+        return [self.indexed objectEnumerator];
+    }
+}
+
+@end
diff --git a/Firebase/Database/Snapshot/FLeafNode.h b/Firebase/Database/Snapshot/FLeafNode.h
new file mode 100644
index 0000000..15e0132
--- /dev/null
+++ b/Firebase/Database/Snapshot/FLeafNode.h
@@ -0,0 +1,28 @@
+/*
+ * 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 "FNode.h"
+
+
+@interface FLeafNode : NSObject <FNode>
+
+- (id)initWithValue:(id)aValue;
+- (id)initWithValue:(id)aValue withPriority:(id<FNode>)aPriority;
+
+@property (nonatomic, strong) id value;
+
+@end
diff --git a/Firebase/Database/Snapshot/FLeafNode.m b/Firebase/Database/Snapshot/FLeafNode.m
new file mode 100644
index 0000000..a26e057
--- /dev/null
+++ b/Firebase/Database/Snapshot/FLeafNode.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 "FLeafNode.h"
+#import "FEmptyNode.h"
+#import "FChildrenNode.h"
+#import "FConstants.h"
+#import "FImmutableSortedDictionary.h"
+#import "FUtilities.h"
+#import "FStringUtilities.h"
+#import "FSnapshotUtilities.h"
+
+@interface FLeafNode ()
+@property (nonatomic, strong) id<FNode> priorityNode;
+@property (nonatomic, strong) NSString *lazyHash;
+
+@end
+
+@implementation FLeafNode
+
+@synthesize value;
+@synthesize priorityNode;
+
+- (id)initWithValue:(id)aValue {
+    self = [super init];
+    if (self) {
+        self.value = aValue;
+        self.priorityNode = [FEmptyNode emptyNode];
+    }
+    return self;
+}
+
+- (id)initWithValue:(id)aValue withPriority:(id<FNode>)aPriority {
+    self = [super init];
+    if (self) {
+        self.value = aValue;
+        [FSnapshotUtilities validatePriorityNode:aPriority];
+        self.priorityNode = aPriority;
+    }
+    return self;
+}
+
+#pragma mark -
+#pragma mark FNode methods
+
+- (BOOL) isLeafNode {
+    return YES;
+}
+
+- (id<FNode>) getPriority {
+    return self.priorityNode;
+}
+
+- (id<FNode>) updatePriority:(id<FNode>)aPriority {
+    return [[FLeafNode alloc] initWithValue:self.value withPriority:aPriority];
+}
+
+- (id<FNode>) getImmediateChild:(NSString *) childName {
+    if ([childName isEqualToString:@".priority"]) {
+        return self.priorityNode;
+    } else {
+        return [FEmptyNode emptyNode];
+    }
+}
+
+- (id<FNode>) getChild:(FPath *)path {
+    if (path.getFront == nil) {
+        return self;
+    } else if ([[path getFront] isEqualToString:@".priority"]) {
+        return [self getPriority];
+    } else {
+        return [FEmptyNode emptyNode];
+    }
+}
+
+- (BOOL)hasChild:(NSString *)childName {
+    return [childName isEqualToString:@".priority"] && ![self getPriority].isEmpty;
+}
+
+
+- (NSString *)predecessorChildKey:(NSString *)childKey
+{
+    return nil;
+}
+
+- (id<FNode>) updateImmediateChild:(NSString *)childName withNewChild:(id<FNode>)newChildNode {
+    if ([childName isEqualToString:@".priority"]) {
+        return [self updatePriority:newChildNode];
+    } else if (newChildNode.isEmpty) {
+        return self;
+    } else {
+        FChildrenNode* childrenNode = [[FChildrenNode alloc] init];
+        childrenNode = [childrenNode updateImmediateChild:childName withNewChild:newChildNode];
+        childrenNode = [childrenNode updatePriority:self.priorityNode];
+        return childrenNode;
+    }
+}
+
+- (id<FNode>) updateChild:(FPath *)path withNewChild:(id<FNode>)newChildNode {
+    NSString* front = [path getFront];
+    if(front == nil) {
+        return newChildNode;
+    } else if (newChildNode.isEmpty && ![front isEqualToString:@".priority"]) {
+        return self;
+    } else {
+        NSAssert(![front isEqualToString:@".priority"] || path.length == 1, @".priority must be the last token in a path.");
+        return [self updateImmediateChild:front withNewChild:
+                [[FEmptyNode emptyNode] updateChild:[path popFront] withNewChild:newChildNode]];
+    }
+}
+
+- (id) val {
+    return [self valForExport:NO];
+}
+
+- (id) valForExport:(BOOL)exp {
+    if(exp && !self.getPriority.isEmpty) {
+        return @{kPayloadValue : self.value,
+                kPayloadPriority : [[self getPriority] val]};
+    }
+    else {
+        return self.value;
+    }
+}
+
+- (BOOL)isEqual:(id <FNode>)other {
+    if(other == self) {
+        return YES;
+    } else if (other.isLeafNode) {
+        FLeafNode *otherLeaf = other;
+        if ([FUtilities getJavascriptType:self.value] != [FUtilities getJavascriptType:otherLeaf.value]) {
+            return NO;
+        }
+        return [otherLeaf.value isEqual:self.value] && [otherLeaf.priorityNode isEqual:self.priorityNode];
+    } else {
+        return NO;
+    }
+}
+
+- (NSUInteger)hash {
+    return [self.value hash] * 17 + self.priorityNode.hash;
+}
+
+- (id <FNode>)withIndex:(id <FIndex>)index {
+    return self;
+}
+
+- (BOOL)isIndexed:(id <FIndex>)index {
+    return YES;
+}
+
+- (BOOL) isEmpty {
+    return NO;
+}
+
+- (int) numChildren {
+    return 0;
+}
+
+- (void) enumerateChildrenUsingBlock:(void (^)(NSString *, id<FNode>, BOOL *))block
+{
+    // Nothing to iterate over
+}
+
+- (void) enumerateChildrenReverse:(BOOL)reverse usingBlock:(void (^)(NSString *, id<FNode>, BOOL *))block
+{
+    // Nothing to iterate over
+}
+
+- (NSEnumerator *)childEnumerator
+{
+    // Nothing to iterate over
+    return [@[] objectEnumerator];
+}
+
+- (NSString *) dataHash {
+    if (self.lazyHash == nil) {
+        NSMutableString *toHash = [[NSMutableString alloc] init];
+        [FSnapshotUtilities appendHashRepresentationForLeafNode:self toString:toHash hashVersion:FDataHashVersionV1];
+
+        self.lazyHash = [FStringUtilities base64EncodedSha1:toHash];
+    }
+    return self.lazyHash;
+}
+
+- (NSComparisonResult)compare:(id <FNode>)other {
+    if (other == [FEmptyNode emptyNode]) {
+        return NSOrderedDescending;
+    } else if ([other isKindOfClass:[FChildrenNode class]]) {
+        return NSOrderedAscending;
+    } else {
+        NSAssert(other.isLeafNode, @"Compared against unknown type of node.");
+        return [self compareToLeafNode:(FLeafNode*)other];
+    }
+}
+
++ (NSArray*) valueTypeOrder {
+    static NSArray* valueOrder = nil;
+    static dispatch_once_t once;
+    dispatch_once(&once, ^{
+        valueOrder = @[kJavaScriptObject, kJavaScriptBoolean, kJavaScriptNumber, kJavaScriptString];
+    });
+    return valueOrder;
+}
+
+- (NSComparisonResult) compareToLeafNode:(FLeafNode*)other {
+    NSString* thisLeafType = [FUtilities getJavascriptType:self.value];
+    NSString* otherLeafType = [FUtilities getJavascriptType:other.value];
+    NSUInteger thisIndex = [[FLeafNode valueTypeOrder] indexOfObject:thisLeafType];
+    NSUInteger otherIndex = [[FLeafNode valueTypeOrder] indexOfObject:otherLeafType];
+    assert(thisIndex >= 0 && otherIndex >= 0);
+    if (otherIndex == thisIndex) {
+        // Same type.  Compare values.
+        if (thisLeafType == kJavaScriptObject) {
+            // Deferred value nodes are all equal, but we should also never get to this point...
+            return NSOrderedSame;
+        } else if (thisLeafType == kJavaScriptString) {
+            return [self.value compare:other.value options:NSLiteralSearch];
+        } else {
+            return [self.value compare:other.value];
+        }
+    } else {
+        return thisIndex > otherIndex ? NSOrderedDescending : NSOrderedAscending;
+    }
+}
+
+- (NSString *) description {
+    return [[self valForExport:YES] description];
+}
+
+- (void) forEachChildDo:(fbt_bool_nsstring_node)action {
+    // There are no children, so there is nothing to do.
+    return;
+}
+
+
+@end
diff --git a/Firebase/Database/Snapshot/FNode.h b/Firebase/Database/Snapshot/FNode.h
new file mode 100644
index 0000000..1316756
--- /dev/null
+++ b/Firebase/Database/Snapshot/FNode.h
@@ -0,0 +1,46 @@
+/*
+ * 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 "FPath.h"
+#import "FTypedefs_Private.h"
+
+@protocol FIndex;
+
+@protocol FNode <NSObject>
+
+- (BOOL) isLeafNode;
+- (id<FNode>) getPriority;
+- (id<FNode>) updatePriority:(id<FNode>)priority;
+- (id<FNode>) getImmediateChild:(NSString *)childKey;
+- (id<FNode>) getChild:(FPath *)path;
+- (NSString *) predecessorChildKey:(NSString *)childKey;
+- (id<FNode>) updateImmediateChild:(NSString *)childKey withNewChild:(id<FNode>)newChildNode;
+- (id<FNode>) updateChild:(FPath *)path withNewChild:(id<FNode>)newChildNode;
+- (BOOL) hasChild:(NSString*)childKey;
+- (BOOL) isEmpty;
+- (int) numChildren;
+- (id) val;
+- (id) valForExport:(BOOL)exp;
+- (NSString *) dataHash;
+- (NSComparisonResult) compare:(id<FNode>)other;
+- (BOOL) isEqual:(id<FNode>)other;
+- (void)enumerateChildrenUsingBlock:(void (^)(NSString *key, id<FNode> node, BOOL *stop))block;
+- (void)enumerateChildrenReverse:(BOOL)reverse usingBlock:(void (^)(NSString *key, id<FNode> node, BOOL *stop))block;
+
+- (NSEnumerator *)childEnumerator;
+
+@end
diff --git a/Firebase/Database/Snapshot/FSnapshotUtilities.h b/Firebase/Database/Snapshot/FSnapshotUtilities.h
new file mode 100644
index 0000000..2a28788
--- /dev/null
+++ b/Firebase/Database/Snapshot/FSnapshotUtilities.h
@@ -0,0 +1,45 @@
+/*
+ * Copyright 2017 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#import <Foundation/Foundation.h>
+#import "FNode.h"
+
+@class FImmutableSortedDictionary;
+@class FCompoundWrite;
+@class FLeafNode;
+@protocol FNode;
+
+typedef NS_ENUM(NSInteger, FDataHashVersion) {
+    FDataHashVersionV1,
+    FDataHashVersionV2,
+};
+
+@interface FSnapshotUtilities : NSObject
+
++ (id<FNode>) nodeFrom:(id)val;
++ (id<FNode>) nodeFrom:(id)val priority:(id)priority;
++ (id<FNode>) nodeFrom:(id)val withValidationFrom:(NSString *)fn;
++ (id<FNode>) nodeFrom:(id)val priority:(id)priority withValidationFrom:(NSString *)fn;
++ (FCompoundWrite *) compoundWriteFromDictionary:(NSDictionary *)values withValidationFrom:(NSString *)fn;
++ (void) validatePriorityNode:(id<FNode>)priorityNode;
++ (void)appendHashRepresentationForLeafNode:(FLeafNode *)val
+                                   toString:(NSMutableString *)string
+                                hashVersion:(FDataHashVersion)hashVersion;
++ (void)appendHashV2RepresentationForString:(NSString *)string toString:(NSMutableString *)mutableString;
+
++ (NSUInteger)estimateSerializedNodeSize:(id<FNode>)node;
+
+@end
diff --git a/Firebase/Database/Snapshot/FSnapshotUtilities.m b/Firebase/Database/Snapshot/FSnapshotUtilities.m
new file mode 100644
index 0000000..1b83430
--- /dev/null
+++ b/Firebase/Database/Snapshot/FSnapshotUtilities.m
@@ -0,0 +1,301 @@
+/*
+ * 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 "FSnapshotUtilities.h"
+#import "FEmptyNode.h"
+#import "FLeafNode.h"
+#import "FConstants.h"
+#import "FUtilities.h"
+#import "FChildrenNode.h"
+#import "FLLRBValueNode.h"
+#import "FValidation.h"
+#import "FMaxNode.h"
+#import "FNamedNode.h"
+#import "FCompoundWrite.h"
+
+@implementation FSnapshotUtilities
+
++ (id<FNode>) nodeFrom:(id)val {
+    return [FSnapshotUtilities nodeFrom:val priority:nil];
+}
+
++ (id<FNode>) nodeFrom:(id)val priority:(id)priority {
+    return [FSnapshotUtilities nodeFrom:val priority:priority withValidationFrom:@"nodeFrom:priority:"];
+}
+
++ (id<FNode>) nodeFrom:(id)val withValidationFrom:(NSString *)fn {
+    return [FSnapshotUtilities nodeFrom:val priority:nil withValidationFrom:fn];
+}
+
++ (id<FNode>) nodeFrom:(id)val priority:(id)priority withValidationFrom:(NSString *)fn {
+    return [FSnapshotUtilities nodeFrom:val priority:priority withValidationFrom:fn atDepth:0 path:[[NSMutableArray alloc] init]];
+}
+
++ (id<FNode>) nodeFrom:(id)val priority:(id)aPriority withValidationFrom:(NSString *)fn atDepth:(int)depth path:(NSMutableArray *)path {
+    @autoreleasepool {
+        return [FSnapshotUtilities internalNodeFrom:val priority:aPriority withValidationFrom:fn atDepth:depth path:path];
+    }
+}
+
++ (id<FNode>) internalNodeFrom:(id)val priority:(id)aPriority withValidationFrom:(NSString *)fn atDepth:(int)depth path:(NSMutableArray *)path {
+
+        
+    if (depth > kFirebaseMaxObjectDepth) {
+        NSRange range;
+        range.location = 0;
+        range.length = 100;
+        NSString* pathString = [[path subarrayWithRange:range] componentsJoinedByString:@"."];
+        @throw [[NSException alloc] initWithName:@"InvalidFirebaseData" reason:[NSString stringWithFormat:@"(%@) Max object depth exceeded: %@...", fn, pathString] userInfo:nil];
+    }
+
+    if (val == nil || val == [NSNull null]) {
+        // Null is a valid type to store
+        return [FEmptyNode emptyNode];
+    }
+
+    [FValidation validateFrom:fn isValidPriorityValue:aPriority withPath:path];
+    id<FNode> priority = [FSnapshotUtilities nodeFrom:aPriority];
+
+    id value = val;
+    BOOL isLeafNode = NO;
+
+    if([value isKindOfClass:[NSDictionary class]]) {
+        NSDictionary* dict = val;
+        if(dict[kPayloadPriority] != nil) {
+            id rawPriority = [dict objectForKey:kPayloadPriority];
+            [FValidation validateFrom:fn isValidPriorityValue:rawPriority withPath:path];
+            priority = [FSnapshotUtilities nodeFrom:rawPriority];
+        }
+
+        if(dict[kPayloadValue] != nil) {
+            value = [dict objectForKey:kPayloadValue];
+            if ([FValidation validateFrom:fn isValidLeafValue:value withPath:path]) {
+                isLeafNode = YES;
+            } else {
+                @throw [[NSException alloc]
+                        initWithName:@"InvalidLeafValueType"
+                              reason:[NSString stringWithFormat:@"(%@) Invalid data type used with .value. Can only use "
+                                                                        "NSString and NSNumber or be null. Found %@ instead.",
+                                              fn, [[value class] description]] userInfo:nil];
+            }
+        }
+    }
+
+    if([FValidation validateFrom:fn isValidLeafValue:value withPath:path]) {
+        isLeafNode = YES;
+    }
+
+    if (isLeafNode) {
+        return [[FLeafNode alloc] initWithValue:value withPriority:priority];
+    }
+
+    // Unlike with JS, we have to handle the dictionary and array cases separately.
+    if ([value isKindOfClass:[NSDictionary class]]) {
+        NSDictionary* dval = (NSDictionary *)value;
+        NSMutableDictionary *children = [NSMutableDictionary dictionaryWithCapacity:dval.count];
+
+        // Avoid creating a million newPaths by appending to old one
+        for (id keyId in dval) {
+            [FValidation validateFrom:fn validDictionaryKey:keyId withPath:path];
+            NSString* key = (NSString*)keyId;
+
+            if (![key hasPrefix:kPayloadMetadataPrefix]) {
+                [path addObject:key];
+                id<FNode> childNode = [FSnapshotUtilities nodeFrom:dval[key] priority:nil withValidationFrom:fn atDepth:depth + 1 path:path];
+                [path removeLastObject];
+
+                if (![childNode isEmpty]) {
+                    children[key] = childNode;
+                }
+            }
+        }
+
+        if ([children count] == 0) {
+            return [FEmptyNode emptyNode];
+        } else {
+            FImmutableSortedDictionary *childrenDict = [FImmutableSortedDictionary fromDictionary:children
+                                                                                   withComparator:[FUtilities keyComparator]];
+            return [[FChildrenNode alloc] initWithPriority:priority children:childrenDict];
+        }
+    } else if([value isKindOfClass:[NSArray class]]) {
+        NSArray* aval = (NSArray *)value;
+        NSMutableDictionary* children = [NSMutableDictionary dictionaryWithCapacity:aval.count];
+
+        for(int i = 0; i < [aval count]; i++) {
+            NSString* key = [NSString stringWithFormat:@"%i", i];
+            [path addObject:key];
+            id<FNode> childNode = [FSnapshotUtilities nodeFrom:[aval objectAtIndex:i] priority:nil withValidationFrom:fn atDepth:depth + 1 path:path];
+            [path removeLastObject];
+
+            if (![childNode isEmpty]) {
+                children[key] = childNode;
+            }
+        }
+
+        if ([children count] == 0) {
+            return [FEmptyNode emptyNode];
+        } else {
+            FImmutableSortedDictionary *childrenDict = [FImmutableSortedDictionary fromDictionary:children
+                                                                                   withComparator:[FUtilities keyComparator]];
+            return [[FChildrenNode alloc] initWithPriority:priority children:childrenDict];
+        }
+    } else {
+        NSRange range;
+        range.location = 0;
+        range.length = MIN(path.count, 50);
+        NSString* pathString = [[path subarrayWithRange:range] componentsJoinedByString:@"."];
+
+        @throw [[NSException alloc] initWithName:@"InvalidFirebaseData"
+                                          reason:[NSString stringWithFormat:@"(%@) Cannot store object of type %@ at %@. "
+                                                                                    "Can only store objects of type NSNumber, NSString, NSDictionary, and NSArray.",
+                                                          fn, [[value class] description], pathString] userInfo:nil];
+    }
+}
+
++ (FCompoundWrite *) compoundWriteFromDictionary:(NSDictionary *)values withValidationFrom:(NSString *)fn {
+    FCompoundWrite *compoundWrite = [FCompoundWrite emptyWrite];
+
+    NSMutableArray *updatePaths = [NSMutableArray arrayWithCapacity:values.count];
+    for (NSString *keyId in values) {
+        id value = values[keyId];
+        [FValidation validateFrom:fn validUpdateDictionaryKey:keyId withValue:value];
+
+        FPath* path = [FPath pathWithString:keyId];
+        id<FNode> node = [FSnapshotUtilities nodeFrom:value withValidationFrom:fn];
+
+        [updatePaths addObject:path];
+        compoundWrite = [compoundWrite addWrite:node atPath:path];
+    }
+    
+    // Check that the update paths are not descendants of each other.
+    [updatePaths sortUsingComparator:^NSComparisonResult(FPath* left, FPath* right) {
+        return [left compare:right];
+    }];
+    FPath *prevPath = nil;
+    for (FPath *path in updatePaths) {
+        if (prevPath != nil && [prevPath contains:path]) {
+            @throw [[NSException alloc] initWithName:@"InvalidFirebaseData" reason:[NSString stringWithFormat:@"(%@) Invalid path in object. Path (%@) is an ancestor of (%@).", fn, prevPath, path] userInfo:nil];
+        }
+        prevPath = path;
+    }
+
+    return compoundWrite;
+}
+
++ (void)validatePriorityNode:(id <FNode>)priorityNode {
+    assert(priorityNode != nil);
+    if (priorityNode.isLeafNode) {
+        id val = priorityNode.val;
+        if ([val isKindOfClass:[NSDictionary class]]) {
+            NSDictionary* valDict __unused = (NSDictionary*)val;
+            NSAssert(valDict[kServerValueSubKey] != nil, @"Priority can't be object unless it's a deferred value");
+        } else {
+            NSString *jsType __unused = [FUtilities getJavascriptType:val];
+            NSAssert(jsType == kJavaScriptString || jsType == kJavaScriptNumber, @"Priority of unexpected type.");
+        }
+    } else {
+        NSAssert(priorityNode == [FMaxNode maxNode] || priorityNode.isEmpty, @"Priority of unexpected type.");
+    }
+    // Don't call getPriority() on MAX_NODE to avoid hitting assertion.
+    NSAssert(priorityNode == [FMaxNode maxNode] || priorityNode.getPriority.isEmpty,
+            @"Priority nodes can't have a priority of their own.");
+}
+
++ (void)appendHashRepresentationForLeafNode:(FLeafNode *)leafNode
+                                   toString:(NSMutableString *)string
+                                hashVersion:(FDataHashVersion)hashVersion {
+    NSAssert(hashVersion == FDataHashVersionV1 || hashVersion == FDataHashVersionV2,
+             @"Unknown hash version: %lu", (unsigned long)hashVersion);
+    if (!leafNode.getPriority.isEmpty) {
+        [string appendString:@"priority:"];
+        [FSnapshotUtilities appendHashRepresentationForLeafNode:leafNode.getPriority toString:string hashVersion:hashVersion];
+        [string appendString:@":"];
+    }
+
+    NSString *jsType = [FUtilities getJavascriptType:leafNode.val];
+    [string appendString:jsType];
+    [string appendString:@":"];
+
+
+    if (jsType == kJavaScriptBoolean) {
+        NSString *boolString = [leafNode.val boolValue] ? kJavaScriptTrue : kJavaScriptFalse;
+        [string appendString:boolString];
+    } else if (jsType == kJavaScriptNumber) {
+        NSString *numberString = [FUtilities ieee754StringForNumber:leafNode.val];
+        [string appendString:numberString];
+    } else if (jsType == kJavaScriptString) {
+        if (hashVersion == FDataHashVersionV1) {
+            [string appendString:leafNode.val];
+        } else {
+            NSAssert(hashVersion == FDataHashVersionV2, @"Invalid hash version found");
+            [FSnapshotUtilities appendHashV2RepresentationForString:leafNode.val toString:string];
+        }
+    } else {
+        [NSException raise:NSInvalidArgumentException format:@"Unknown value for hashing: %@", leafNode];
+    }
+}
+
++ (void)appendHashV2RepresentationForString:(NSString *)string
+                                   toString:(NSMutableString *)mutableString {
+    string = [string stringByReplacingOccurrencesOfString:@"\\" withString:@"\\\\"];
+    string = [string stringByReplacingOccurrencesOfString:@"\"" withString:@"\\\""];
+    [mutableString appendString:@"\""];
+    [mutableString appendString:string];
+    [mutableString appendString:@"\""];
+}
+
++ (NSUInteger)estimateLeafNodeSize:(FLeafNode *)leafNode {
+    NSString *jsType = [FUtilities getJavascriptType:leafNode.val];
+    // These values are somewhat arbitrary, but we don't need an exact value so prefer performance over exact value
+    NSUInteger valueSize;
+    if (jsType == kJavaScriptNumber) {
+        valueSize = 8; // estimate each float with 8 bytes
+    } else if (jsType == kJavaScriptBoolean) {
+        valueSize = 4; // true or false need roughly 4 bytes
+    } else if (jsType == kJavaScriptString) {
+        valueSize = 2 + [leafNode.val length]; // add 2 for quotes
+    } else {
+        [NSException raise:NSInvalidArgumentException format:@"Unknown leaf type: %@", leafNode];
+        return 0;
+    }
+
+    if (leafNode.getPriority.isEmpty) {
+        return valueSize;
+    } else {
+        // Account for extra overhead due to the extra JSON object and the ".value" and ".priority" keys, colons, comma
+        NSUInteger leafPriorityOverhead =  2 + 8 + 11 + 2 + 1;
+        return leafPriorityOverhead + valueSize + [FSnapshotUtilities estimateLeafNodeSize:leafNode.getPriority];
+    }
+}
+
++ (NSUInteger)estimateSerializedNodeSize:(id<FNode>)node {
+    if ([node isEmpty]) {
+        return 4; // null keyword
+    } else if ([node isLeafNode]) {
+        return [FSnapshotUtilities estimateLeafNodeSize:node];
+    } else {
+        NSAssert([node isKindOfClass:[FChildrenNode class]], @"Unexpected node type: %@", [node class]);
+        __block NSUInteger sum = 1; // opening brackets
+        [((FChildrenNode *)node) enumerateChildrenAndPriorityUsingBlock:^(NSString *key, id<FNode>child, BOOL *stop) {
+            sum += key.length;
+            sum += 4; // quotes around key and colon and (comma or closing bracket)
+            sum += [FSnapshotUtilities estimateSerializedNodeSize:child];
+        }];
+        return sum;
+    }
+}
+
+@end