10 files changed, 1279 insertions, 0 deletions
diff --git a/Firebase/Database/Core/Utilities/FIRRetryHelper.h b/Firebase/Database/Core/Utilities/FIRRetryHelper.h
new file mode 100644
index 0000000..ffe2726
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FIRRetryHelper.h
@@ -0,0 +1,33 @@
+/*
+ * 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>
+
+@interface FIRRetryHelper : NSObject
+
+- (instancetype) initWithDispatchQueue:(dispatch_queue_t)dispatchQueue
+             minRetryDelayAfterFailure:(NSTimeInterval)minRetryDelayAfterFailure
+                         maxRetryDelay:(NSTimeInterval)maxRetryDelay
+                         retryExponent:(double)retryExponent
+                          jitterFactor:(double)jitterFactor;
+
+- (void) retry:(void (^)())block;
+
+- (void) cancel;
+
+- (void) signalSuccess;
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FIRRetryHelper.m b/Firebase/Database/Core/Utilities/FIRRetryHelper.m
new file mode 100644
index 0000000..199e17d
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FIRRetryHelper.m
@@ -0,0 +1,139 @@
+/*
+ * 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 "FIRRetryHelper.h"
+#import "FUtilities.h"
+
+@interface FIRRetryHelperTask : NSObject
+
+@property (nonatomic, strong) void (^block)();
+
+@end
+
+@implementation FIRRetryHelperTask
+
+- (instancetype) initWithBlock:(void (^)())block {
+    self = [super init];
+    if (self != nil) {
+        self->_block = [block copy];
+    }
+    return self;
+}
+
+- (BOOL) isCanceled {
+    return self.block == nil;
+}
+
+- (void) cancel {
+    self.block = nil;
+}
+
+- (void) execute {
+    if (self.block) {
+        self.block();
+    }
+}
+
+@end
+
+
+
+@interface FIRRetryHelper ()
+
+@property (nonatomic, strong) dispatch_queue_t dispatchQueue;
+@property (nonatomic) NSTimeInterval minRetryDelayAfterFailure;
+@property (nonatomic) NSTimeInterval maxRetryDelay;
+@property (nonatomic) double retryExponent;
+@property (nonatomic) double jitterFactor;
+
+@property (nonatomic) BOOL lastWasSuccess;
+@property (nonatomic) NSTimeInterval currentRetryDelay;
+
+@property (nonatomic, strong) FIRRetryHelperTask *scheduledRetry;
+
+@end
+
+@implementation FIRRetryHelper
+
+- (instancetype) initWithDispatchQueue:(dispatch_queue_t)dispatchQueue
+             minRetryDelayAfterFailure:(NSTimeInterval)minRetryDelayAfterFailure
+                         maxRetryDelay:(NSTimeInterval)maxRetryDelay
+                         retryExponent:(double)retryExponent
+                          jitterFactor:(double)jitterFactor {
+    self = [super init];
+    if (self != nil) {
+        self->_dispatchQueue = dispatchQueue;
+        self->_minRetryDelayAfterFailure = minRetryDelayAfterFailure;
+        self->_maxRetryDelay = maxRetryDelay;
+        self->_retryExponent = retryExponent;
+        self->_jitterFactor = jitterFactor;
+        self->_lastWasSuccess = YES;
+    }
+    return self;
+}
+
+- (void) retry:(void (^)())block {
+    if (self.scheduledRetry != nil) {
+        FFLog(@"I-RDB054001", @"Canceling existing retry attempt");
+        [self.scheduledRetry cancel];
+        self.scheduledRetry = nil;
+    }
+
+    NSTimeInterval delay;
+    if (self.lastWasSuccess) {
+        delay = 0;
+    } else {
+        if (self.currentRetryDelay == 0) {
+            self.currentRetryDelay = self.minRetryDelayAfterFailure;
+        } else {
+            NSTimeInterval newDelay = (self.currentRetryDelay * self.retryExponent);
+            self.currentRetryDelay = MIN(newDelay, self.maxRetryDelay);
+        }
+
+        delay = ((1 - self.jitterFactor) * self.currentRetryDelay) +
+                (self.jitterFactor * self.currentRetryDelay * [FUtilities randomDouble]);
+        FFLog(@"I-RDB054002", @"Scheduling retry in %fs", delay);
+
+    }
+    self.lastWasSuccess = NO;
+    FIRRetryHelperTask *task = [[FIRRetryHelperTask alloc] initWithBlock:block];
+    self.scheduledRetry = task;
+    dispatch_time_t popTime = dispatch_time(DISPATCH_TIME_NOW, (long long)(delay * NSEC_PER_SEC));
+    dispatch_after(popTime, self.dispatchQueue, ^{
+        if (![task isCanceled]) {
+            self.scheduledRetry = nil;
+            [task execute];
+        }
+    });
+}
+
+- (void) signalSuccess {
+    self.lastWasSuccess = YES;
+    self.currentRetryDelay = 0;
+}
+
+- (void) cancel {
+    if (self.scheduledRetry != nil) {
+        FFLog(@"I-RDB054003", @"Canceling existing retry attempt");
+        [self.scheduledRetry cancel];
+        self.scheduledRetry = nil;
+    } else {
+        FFLog(@"I-RDB054004", @"No existing retry attempt to cancel");
+    }
+    self.currentRetryDelay = 0;
+}
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FImmutableTree.h b/Firebase/Database/Core/Utilities/FImmutableTree.h
new file mode 100644
index 0000000..005a9f2
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FImmutableTree.h
@@ -0,0 +1,51 @@
+/*
+ * 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 "FImmutableSortedDictionary.h"
+#import "FPath.h"
+#import "FTuplePathValue.h"
+
+@interface FImmutableTree : NSObject
+
+- (id) initWithValue:(id)aValue;
+- (id) initWithValue:(id)aValue children:(FImmutableSortedDictionary *)childrenMap;
+
++ (FImmutableTree *) empty;
+- (BOOL) isEmpty;
+
+- (FTuplePathValue *) findRootMostMatchingPath:(FPath *)relativePath predicate:(BOOL (^)(id))predicate;
+- (FTuplePathValue *) findRootMostValueAndPath:(FPath *)relativePath;
+- (FImmutableTree *) subtreeAtPath:(FPath *)relativePath;
+- (FImmutableTree *) setValue:(id)newValue atPath:(FPath *)relativePath;
+- (FImmutableTree *) removeValueAtPath:(FPath *)relativePath;
+- (id) valueAtPath:(FPath *)relativePath;
+- (id) rootMostValueOnPath:(FPath *)path;
+- (id) rootMostValueOnPath:(FPath *)path matching:(BOOL (^)(id))predicate;
+- (id) leafMostValueOnPath:(FPath *)path;
+- (id) leafMostValueOnPath:(FPath *)relativePath matching:(BOOL (^)(id))predicate;
+- (BOOL) containsValueMatching:(BOOL (^)(id))predicate;
+- (FImmutableTree *) setTree:(FImmutableTree *)newTree atPath:(FPath *)relativePath;
+- (id) foldWithBlock:(id (^)(FPath *path, id value, NSDictionary *foldedChildren))block;
+- (id) findOnPath:(FPath *)path andApplyBlock:(id (^)(FPath *path, id value))block;
+- (FPath *) forEachOnPath:(FPath *)path whileBlock:(BOOL (^)(FPath *path, id value))block;
+- (FImmutableTree *) forEachOnPath:(FPath *)path performBlock:(void (^)(FPath *path, id value))block;
+- (void) forEach:(void (^)(FPath *path, id value))block;
+- (void) forEachChild:(void (^)(NSString *childKey, id childValue))block;
+
+@property (nonatomic, strong, readonly) id value;
+@property (nonatomic, strong, readonly) FImmutableSortedDictionary *children;
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FImmutableTree.m b/Firebase/Database/Core/Utilities/FImmutableTree.m
new file mode 100644
index 0000000..57bf74d
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FImmutableTree.m
@@ -0,0 +1,421 @@
+/*
+ * 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 "FImmutableTree.h"
+#import "FImmutableSortedDictionary.h"
+#import "FPath.h"
+#import "FUtilities.h"
+
+@interface FImmutableTree ()
+@property (nonatomic, strong, readwrite) id value;
+/**
+* Maps NSString -> FImmutableTree<T>, where <T> is type of value.
+*/
+@property (nonatomic, strong, readwrite) FImmutableSortedDictionary *children;
+@end
+
+@implementation FImmutableTree
+@synthesize value;
+@synthesize children;
+
+- (id) initWithValue:(id)aValue {
+    self = [super init];
+    if (self) {
+        self.value = aValue;
+        self.children = [FImmutableTree emptyChildren];
+    }
+    return self;
+}
+
+- (id) initWithValue:(id)aValue children:(FImmutableSortedDictionary *)childrenMap {
+    self = [super init];
+    if (self) {
+        self.value = aValue;
+        self.children = childrenMap;
+    }
+    return self;
+}
+
++ (FImmutableSortedDictionary *) emptyChildren {
+    static dispatch_once_t emptyChildrenToken;
+    static FImmutableSortedDictionary *emptyChildren;
+    dispatch_once(&emptyChildrenToken, ^{
+        emptyChildren = [FImmutableSortedDictionary dictionaryWithComparator:[FUtilities stringComparator]];
+    });
+    return emptyChildren;
+}
+
++ (FImmutableTree *) empty {
+    static dispatch_once_t emptyImmutableTreeToken;
+    static FImmutableTree *emptyTree = nil;
+    dispatch_once(&emptyImmutableTreeToken, ^{
+        emptyTree = [[FImmutableTree alloc] initWithValue:nil];
+    });
+    return emptyTree;
+}
+
+- (BOOL) isEmpty {
+    return self.value == nil && [self.children isEmpty];
+}
+
+/**
+* Given a path and a predicate, return the first node and the path to that node where the predicate returns true
+* // TODO Do a perf test. If we're creating a bunch of FTuplePathValue objects on the way back out, it may be better to pass down a pathSoFar FPath
+*/
+- (FTuplePathValue *) findRootMostMatchingPath:(FPath *)relativePath predicate:(BOOL (^)(id value))predicate {
+    if (self.value != nil && predicate(self.value)) {
+        return [[FTuplePathValue alloc] initWithPath:[FPath empty] value:self.value];
+    } else {
+        if ([relativePath isEmpty]) {
+            return nil;
+        } else {
+            NSString *front = [relativePath getFront];
+            FImmutableTree *child = [self.children get:front];
+            if (child != nil) {
+                FTuplePathValue *childExistingPathAndValue = [child findRootMostMatchingPath:[relativePath popFront] predicate:predicate];
+                if (childExistingPathAndValue != nil) {
+                    FPath *fullPath = [[[FPath alloc] initWith:front] child:childExistingPathAndValue.path];
+                    return [[FTuplePathValue alloc] initWithPath:fullPath value:childExistingPathAndValue.value];
+                } else {
+                    return nil;
+                }
+            } else {
+                // No child matching path
+                return nil;
+            }
+        }
+    }
+}
+
+/**
+* Find, if it exists, the shortest subpath of the given path that points a defined value in the tree
+*/
+- (FTuplePathValue *) findRootMostValueAndPath:(FPath *)relativePath {
+    return [self findRootMostMatchingPath:relativePath predicate:^BOOL(__unsafe_unretained id value){
+        return YES;
+    }];
+}
+
+- (id) rootMostValueOnPath:(FPath *)path {
+    return [self rootMostValueOnPath:path matching:^BOOL(id value) {
+        return YES;
+    }];
+}
+
+- (id) rootMostValueOnPath:(FPath *)path matching:(BOOL (^)(id))predicate {
+    if (self.value != nil && predicate(self.value)) {
+        return self.value;
+    } else if (path.isEmpty) {
+        return nil;
+    } else {
+        return [[self.children get:path.getFront] rootMostValueOnPath:[path popFront] matching:predicate];
+    }
+}
+
+- (id) leafMostValueOnPath:(FPath *)path {
+    return [self leafMostValueOnPath:path matching:^BOOL(id value) {
+        return YES;
+    }];
+}
+
+- (id) leafMostValueOnPath:(FPath *)relativePath matching:(BOOL (^)(id))predicate {
+    __block id currentValue = self.value;
+    __block FImmutableTree *currentTree = self;
+    [relativePath enumerateComponentsUsingBlock:^(NSString *key, BOOL *stop) {
+        currentTree = [currentTree.children get:key];
+        if (currentTree == nil) {
+            *stop = YES;
+        } else {
+            id treeValue = currentTree.value;
+            if (treeValue != nil && predicate(treeValue)) {
+                currentValue = treeValue;
+            }
+        }
+    }];
+    return currentValue;
+}
+
+- (BOOL) containsValueMatching:(BOOL (^)(id))predicate {
+    if (self.value != nil && predicate(self.value)) {
+        return YES;
+    } else {
+        __block BOOL found = NO;
+        [self.children enumerateKeysAndObjectsUsingBlock:^(NSString *key, FImmutableTree *subtree, BOOL *stop) {
+            found = [subtree containsValueMatching:predicate];
+            if (found) *stop = YES;
+        }];
+        return found;
+    }
+}
+
+- (FImmutableTree *) subtreeAtPath:(FPath *)relativePath {
+    if ([relativePath isEmpty]) {
+        return self;
+    } else {
+        NSString *front = [relativePath getFront];
+        FImmutableTree *childTree = [self.children get:front];
+        if (childTree != nil) {
+            return [childTree subtreeAtPath:[relativePath popFront]];
+        } else {
+            return [FImmutableTree empty];
+        }
+    }
+}
+
+/**
+* Sets a value at the specified path
+*/
+- (FImmutableTree *) setValue:(id)newValue atPath:(FPath *)relativePath {
+    if ([relativePath isEmpty]) {
+        return [[FImmutableTree alloc] initWithValue:newValue children:self.children];
+    } else {
+        NSString *front = [relativePath getFront];
+        FImmutableTree *child = [self.children get:front];
+        if (child == nil) {
+            child = [FImmutableTree empty];
+        }
+        FImmutableTree *newChild = [child setValue:newValue atPath:[relativePath popFront]];
+        FImmutableSortedDictionary *newChildren = [self.children insertKey:front withValue:newChild];
+        return [[FImmutableTree alloc] initWithValue:self.value children:newChildren];
+    }
+}
+
+/**
+* Remove the value at the specified path
+*/
+- (FImmutableTree *) removeValueAtPath:(FPath *)relativePath {
+    if ([relativePath isEmpty]) {
+        if ([self.children isEmpty]) {
+            return [FImmutableTree empty];
+        } else {
+            return [[FImmutableTree alloc] initWithValue:nil children:self.children];
+        }
+    } else {
+        NSString *front = [relativePath getFront];
+        FImmutableTree *child = [self.children get:front];
+        if (child) {
+            FImmutableTree *newChild = [child removeValueAtPath:[relativePath popFront]];
+            FImmutableSortedDictionary *newChildren;
+            if ([newChild isEmpty]) {
+                newChildren = [self.children removeKey:front];
+            } else {
+                newChildren = [self.children insertKey:front withValue:newChild];
+            }
+            if (self.value == nil && [newChildren isEmpty]) {
+                return [FImmutableTree empty];
+            } else {
+                return [[FImmutableTree alloc] initWithValue:self.value children:newChildren];
+            }
+        } else {
+            return self;
+        }
+    }
+}
+
+/**
+* Gets a value from the tree
+*/
+- (id) valueAtPath:(FPath *)relativePath {
+    if ([relativePath isEmpty]) {
+        return self.value;
+    } else {
+        NSString *front = [relativePath getFront];
+        FImmutableTree *child = [self.children get:front];
+        if (child) {
+            return [child valueAtPath:[relativePath popFront]];
+        } else {
+            return nil;
+        }
+    }
+}
+
+/**
+* Replaces the subtree at the specified path with the given new tree
+*/
+- (FImmutableTree *) setTree:(FImmutableTree *)newTree atPath:(FPath *)relativePath {
+    if ([relativePath isEmpty]) {
+        return newTree;
+    } else {
+        NSString *front = [relativePath getFront];
+        FImmutableTree *child = [self.children get:front];
+        if (child == nil) {
+            child = [FImmutableTree empty];
+        }
+        FImmutableTree *newChild = [child setTree:newTree atPath:[relativePath popFront]];
+        FImmutableSortedDictionary *newChildren;
+        if ([newChild isEmpty]) {
+            newChildren = [self.children removeKey:front];
+        } else {
+            newChildren = [self.children insertKey:front withValue:newChild];
+        }
+        return [[FImmutableTree alloc] initWithValue:self.value children:newChildren];
+    }
+}
+
+/**
+* Performs a depth first fold on this tree. Transforms a tree into a single value, given a function that operates on
+* the path to a node, an optional current value, and a map of the child names to folded subtrees
+*/
+- (id) foldWithBlock:(id (^)(FPath *path, id value, NSDictionary *foldedChildren))block {
+    return [self foldWithPathSoFar:[FPath empty] withBlock:block];
+}
+
+/**
+* Recursive helper for public facing foldWithBlock: method
+*/
+- (id) foldWithPathSoFar:(FPath *)pathSoFar withBlock:(id (^)(FPath *path, id value, NSDictionary *foldedChildren))block {
+    __block NSMutableDictionary *accum = [[NSMutableDictionary alloc] init];
+    [self.children enumerateKeysAndObjectsUsingBlock:^(NSString *childKey, FImmutableTree *childTree, BOOL *stop) {
+        accum[childKey] = [childTree foldWithPathSoFar:[pathSoFar childFromString:childKey] withBlock:block];
+    }];
+    return block(pathSoFar, self.value, accum);
+}
+
+/**
+* Find the first matching value on the given path. Return the result of applying block to it.
+*/
+- (id) findOnPath:(FPath *)path andApplyBlock:(id (^)(FPath *path, id value))block {
+    return [self findOnPath:path pathSoFar:[FPath empty] andApplyBlock:block];
+}
+
+- (id) findOnPath:(FPath *)pathToFollow pathSoFar:(FPath *)pathSoFar andApplyBlock:(id (^)(FPath *path, id value))block {
+    id result = self.value ? block(pathSoFar, self.value) : nil;
+    if (result != nil) {
+        return result;
+    } else {
+        if ([pathToFollow isEmpty]) {
+            return nil;
+        } else {
+            NSString *front = [pathToFollow getFront];
+            FImmutableTree *nextChild = [self.children get:front];
+            if (nextChild != nil) {
+                return [nextChild findOnPath:[pathToFollow popFront] pathSoFar:[pathSoFar childFromString:front] andApplyBlock:block];
+            } else {
+                return nil;
+            }
+        }
+    }
+}
+/**
+* Call the block on each value along the path for as long as that function returns true
+* @return The path to the deepest location inspected
+*/
+- (FPath *) forEachOnPath:(FPath *)path whileBlock:(BOOL (^)(FPath *, id))block {
+    return [self forEachOnPath:path pathSoFar:[FPath empty] whileBlock:block];
+}
+
+- (FPath *) forEachOnPath:(FPath *)pathToFollow pathSoFar:(FPath *)pathSoFar whileBlock:(BOOL (^)(FPath *, id))block {
+    if ([pathToFollow isEmpty]) {
+        if (self.value) {
+            block(pathSoFar, self.value);
+        }
+        return pathSoFar;
+    } else {
+        BOOL shouldContinue = YES;
+        if (self.value) {
+            shouldContinue = block(pathSoFar, self.value);
+        }
+        if (shouldContinue) {
+            NSString *front = [pathToFollow getFront];
+            FImmutableTree *nextChild = [self.children get:front];
+            if (nextChild) {
+                return [nextChild forEachOnPath:[pathToFollow popFront] pathSoFar:[pathSoFar childFromString:front] whileBlock:block];
+            } else {
+                return pathSoFar;
+            }
+        } else {
+            return pathSoFar;
+        }
+    }
+}
+
+- (FImmutableTree *) forEachOnPath:(FPath *)path performBlock:(void (^)(FPath *path, id value))block {
+    return [self forEachOnPath:path pathSoFar:[FPath empty] performBlock:block];
+}
+
+- (FImmutableTree *) forEachOnPath:(FPath *)pathToFollow pathSoFar:(FPath *)pathSoFar performBlock:(void (^)(FPath *path, id value))block {
+    if ([pathToFollow isEmpty]) {
+        return self;
+    } else {
+        if (self.value) {
+            block(pathSoFar, self.value);
+        }
+        NSString *front = [pathToFollow getFront];
+        FImmutableTree *nextChild = [self.children get:front];
+        if (nextChild) {
+            return [nextChild forEachOnPath:[pathToFollow popFront] pathSoFar:[pathSoFar childFromString:front] performBlock:block];
+        } else {
+            return [FImmutableTree empty];
+        }
+    }
+}
+/**
+* Calls the given block for each node in the tree that has a value. Called in depth-first order
+*/
+- (void) forEach:(void (^)(FPath *path, id value))block {
+    [self forEachPathSoFar:[FPath empty] withBlock:block];
+}
+
+- (void) forEachPathSoFar:(FPath *)pathSoFar withBlock:(void (^)(FPath *path, id value))block {
+    [self.children enumerateKeysAndObjectsUsingBlock:^(NSString *childKey, FImmutableTree *childTree, BOOL *stop) {
+        [childTree forEachPathSoFar:[pathSoFar childFromString:childKey] withBlock:block];
+    }];
+    if (self.value) {
+        block(pathSoFar, self.value);
+    }
+}
+
+- (void) forEachChild:(void (^)(NSString *childKey, id childValue))block {
+    [self.children enumerateKeysAndObjectsUsingBlock:^(NSString *childKey, FImmutableTree *childTree, BOOL *stop) {
+        if (childTree.value) {
+            block(childKey, childTree.value);
+        }
+    }];
+}
+
+- (BOOL)isEqual:(id)object {
+    if (![object isKindOfClass:[FImmutableTree class]]) {
+        return NO;
+    }
+    FImmutableTree *other = (FImmutableTree *)object;
+    return (self.value == other.value || [self.value isEqual:other.value]) && [self.children isEqual:other.children];
+}
+
+- (NSUInteger)hash {
+    return self.children.hash * 31 + [self.value hash];
+}
+
+- (NSString *) description {
+    NSMutableString *string = [[NSMutableString alloc] init];
+    [string appendString:@"FImmutableTree { value="];
+    [string appendString:(self.value ? [self.value description] : @"<nil>")];
+    [string appendString:@", children={"];
+    [self.children enumerateKeysAndObjectsUsingBlock:^(NSString *childKey, FImmutableTree *childTree, BOOL *stop) {
+        [string appendString:@" "];
+        [string appendString:childKey];
+        [string appendString:@"="];
+        [string appendString:[childTree.value description]];
+    }];
+    [string appendString:@" } }"];
+    return [NSString stringWithString:string];
+}
+
+- (NSString *) debugDescription {
+    return [self description];
+}
+
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FPath.h b/Firebase/Database/Core/Utilities/FPath.h
new file mode 100644
index 0000000..71a7167
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FPath.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>
+
+@interface FPath : NSObject<NSCopying>
+
++ (FPath *) relativePathFrom:(FPath *)outer to:(FPath *)inner;
++ (FPath *) empty;
++ (FPath *) pathWithString:(NSString *)string;
+
+- (id)initWith:(NSString *)path;
+- (id)initWithPieces:(NSArray *)somePieces andPieceNum:(NSInteger)aPieceNum;
+
+- (id)copyWithZone:(NSZone *)zone;
+
+- (void)enumerateComponentsUsingBlock:(void (^)(NSString *key, BOOL *stop))block;
+- (NSString *) getFront;
+- (NSUInteger) length;
+- (FPath *) popFront;
+- (NSString *) getBack;
+- (NSString *) toString;
+- (NSString *) toStringWithTrailingSlash;
+- (NSString *) wireFormat;
+- (FPath *) parent;
+- (FPath *) child:(FPath *)childPathObj;
+- (FPath *) childFromString:(NSString *)childPath;
+- (BOOL) isEmpty;
+- (BOOL) contains:(FPath *)other;
+- (NSComparisonResult) compare:(FPath *)other;
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FPath.m b/Firebase/Database/Core/Utilities/FPath.m
new file mode 100644
index 0000000..485b903
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FPath.m
@@ -0,0 +1,298 @@
+/*
+ * 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 "FPath.h"
+
+#import "FUtilities.h"
+
+@interface FPath()
+
+@property (nonatomic, readwrite, assign) NSInteger pieceNum;
+@property (nonatomic, strong) NSArray * pieces;
+
+@end
+
+@implementation FPath
+
+#pragma mark -
+#pragma mark Initializers
+
++ (FPath *) relativePathFrom:(FPath *)outer to:(FPath *)inner {
+    NSString* outerFront = [outer getFront];
+    NSString* innerFront = [inner getFront];
+    if (outerFront == nil) {
+        return inner;
+    } else if ([outerFront isEqualToString:innerFront]) {
+        return [self relativePathFrom:[outer popFront] to:[inner popFront]];
+    } else {
+        @throw [[NSException alloc] initWithName:@"FirebaseDatabaseInternalError" reason:[NSString stringWithFormat:@"innerPath (%@) is not within outerPath (%@)", inner, outer] userInfo:nil];
+    }
+}
+
++ (FPath *)pathWithString:(NSString *)string
+{
+    return [[FPath alloc] initWith:string];
+}
+
+- (id)initWith:(NSString *)path
+{
+    self = [super init];
+    if (self) {
+        NSArray *pathPieces = [path componentsSeparatedByString:@"/"];
+        NSMutableArray *newPieces = [[NSMutableArray alloc] init];
+        for (NSInteger i = 0; i < pathPieces.count; i++) {
+            NSString *piece = [pathPieces objectAtIndex:i];
+            if (piece.length > 0) {
+                [newPieces addObject:piece];
+            }
+        }
+
+        self.pieces = newPieces;
+        self.pieceNum = 0;
+    }
+    return self;
+}
+
+- (id)initWithPieces:(NSArray *)somePieces andPieceNum:(NSInteger)aPieceNum {
+    self = [super init];
+    if (self) {
+        self.pieceNum = aPieceNum;
+        self.pieces = somePieces;
+    }
+    return self;
+}
+
+- (id)copyWithZone:(NSZone *)zone
+{
+    // Immutable, so it's safe to return self
+    return self;
+}
+
+- (NSString *)description {
+    return [self toString];
+}
+
+#pragma mark -
+#pragma mark Public methods
+
+- (NSString *) getFront {
+    if(self.pieceNum >= self.pieces.count) {
+        return nil;
+    }
+    return [self.pieces objectAtIndex:self.pieceNum];
+}
+
+/**
+* @return The number of segments in this path
+*/
+- (NSUInteger) length {
+    return self.pieces.count - self.pieceNum;
+}
+
+- (FPath *) popFront {
+    NSInteger newPieceNum = self.pieceNum;
+    if (newPieceNum < self.pieces.count) {
+        newPieceNum++;
+    }
+    return [[FPath alloc] initWithPieces:self.pieces andPieceNum:newPieceNum];
+}
+
+- (NSString *) getBack {
+    if(self.pieceNum < self.pieces.count) {
+        return [self.pieces lastObject];
+    }
+    else {
+        return nil;
+    }
+}
+
+- (NSString *) toString {
+    return [self toStringWithTrailingSlash:NO];
+}
+
+- (NSString *) toStringWithTrailingSlash {
+    return [self toStringWithTrailingSlash:YES];
+}
+
+- (NSString *) toStringWithTrailingSlash:(BOOL)trailingSlash {
+    NSMutableString* pathString = [[NSMutableString alloc] init];
+    for(NSInteger i = self.pieceNum; i < self.pieces.count; i++) {
+        [pathString appendString:@"/"];
+        [pathString appendString:[self.pieces objectAtIndex:i]];
+    }
+    if ([pathString length] == 0) {
+        return @"/";
+    } else {
+        if (trailingSlash) {
+            [pathString appendString:@"/"];
+        }
+        return pathString;
+    }
+}
+
+- (NSString *)wireFormat {
+    if ([self isEmpty]) {
+        return @"/";
+    } else {
+        NSMutableString* pathString = [[NSMutableString alloc] init];
+        for (NSInteger i = self.pieceNum; i < self.pieces.count; i++) {
+            if (i > self.pieceNum) {
+                [pathString appendString:@"/"];
+            }
+            [pathString appendString:[self.pieces objectAtIndex:i]];
+        }
+        return pathString;
+    }
+}
+
+- (FPath *) parent {
+    if(self.pieceNum >= self.pieces.count) {
+        return nil;
+    } else {
+        NSMutableArray* newPieces = [[NSMutableArray alloc] init];
+        for (NSInteger i = self.pieceNum; i < self.pieces.count - 1; i++) {
+            [newPieces addObject:[self.pieces objectAtIndex:i]];
+        }
+        return [[FPath alloc] initWithPieces:newPieces andPieceNum:0];
+    }
+}
+
+- (FPath *) child:(FPath *)childPathObj {
+    NSMutableArray* newPieces = [[NSMutableArray alloc] init];
+    for (NSInteger i = self.pieceNum; i < self.pieces.count; i++) {
+        [newPieces addObject:[self.pieces objectAtIndex:i]];
+    }
+    
+    for (NSInteger i = childPathObj.pieceNum; i < childPathObj.pieces.count; i++) {
+        [newPieces addObject:[childPathObj.pieces objectAtIndex:i]];
+    }
+    
+    return [[FPath alloc] initWithPieces:newPieces andPieceNum:0];
+}
+
+- (FPath *)childFromString:(NSString *)childPath {
+    NSMutableArray* newPieces = [[NSMutableArray alloc] init];
+    for (NSInteger i = self.pieceNum; i < self.pieces.count; i++) {
+        [newPieces addObject:[self.pieces objectAtIndex:i]];
+    }
+
+    NSArray *pathPieces = [childPath componentsSeparatedByString:@"/"];
+    for (unsigned int i = 0; i < pathPieces.count; i++) {
+        NSString *piece = [pathPieces objectAtIndex:i];
+        if (piece.length > 0) {
+            [newPieces addObject:piece];
+        }
+    }
+
+    return [[FPath alloc] initWithPieces:newPieces andPieceNum:0];
+}
+
+/**
+* @return True if there are no segments in this path
+*/
+- (BOOL) isEmpty {
+    return self.pieceNum >= self.pieces.count;
+}
+
+/**
+* @return Singleton to represent an empty path
+*/
++ (FPath *) empty {
+    static dispatch_once_t oneEmptyPath;
+    static FPath *emptyPath;
+    dispatch_once(&oneEmptyPath, ^{
+        emptyPath = [[FPath alloc] initWith:@""];
+    });
+    return emptyPath;
+}
+
+- (BOOL) contains:(FPath *)other {
+    if (self.length > other.length) {
+        return NO;
+    }
+
+    NSInteger i = self.pieceNum;
+    NSInteger j = other.pieceNum;
+    while (i < self.pieces.count) {
+        NSString* thisSeg = [self.pieces objectAtIndex:i];
+        NSString* otherSeg = [other.pieces objectAtIndex:j];
+        if (![thisSeg isEqualToString:otherSeg]) {
+            return NO;
+        }
+        ++i;
+        ++j;
+    }
+    return YES;
+}
+
+- (void) enumerateComponentsUsingBlock:(void (^)(NSString *, BOOL *))block {
+    BOOL stop = NO;
+    for (NSInteger i = self.pieceNum; !stop && i < self.pieces.count; i++) {
+        block(self.pieces[i], &stop);
+    }
+}
+
+- (NSComparisonResult) compare:(FPath *)other {
+    NSInteger myCount = self.pieces.count;
+    NSInteger otherCount = other.pieces.count;
+    for (NSInteger i = self.pieceNum, j = other.pieceNum; i < myCount && j < otherCount; i++, j++) {
+        NSComparisonResult comparison = [FUtilities compareKey:self.pieces[i] toKey:other.pieces[j]];
+        if (comparison != NSOrderedSame) {
+            return comparison;
+        }
+    }
+    if (self.length < other.length) {
+        return NSOrderedAscending;
+    } else if (other.length < self.length) {
+        return NSOrderedDescending;
+    } else {
+        NSAssert(self.length == other.length, @"Paths must be the same lengths");
+        return NSOrderedSame;
+    }
+}
+
+/**
+* @return YES if paths are the same
+*/
+- (BOOL)isEqual:(id)other
+{
+    if (other == self) {
+        return YES;
+    }
+    if (!other || ![other isKindOfClass:[self class]]) {
+        return NO;
+    }
+    FPath *otherPath = (FPath *)other;
+    if (self.length != otherPath.length) {
+        return NO;
+    }
+    for (NSUInteger i = self.pieceNum, j = otherPath.pieceNum; i < self.pieces.count; i++, j++) {
+        if (![self.pieces[i] isEqualToString:otherPath.pieces[j]]) {
+            return NO;
+        }
+    }
+    return YES;
+}
+
+- (NSUInteger) hash {
+    NSUInteger hashCode = 0;
+    for (NSInteger i = self.pieceNum; i < self.pieces.count; i++) {
+        hashCode = hashCode * 37 + [self.pieces[i] hash];
+    }
+    return hashCode;
+}
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FTree.h b/Firebase/Database/Core/Utilities/FTree.h
new file mode 100644
index 0000000..8528526
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FTree.h
@@ -0,0 +1,48 @@
+/*
+ * 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 "FTreeNode.h"
+#import "FPath.h"
+
+@interface FTree : NSObject
+
+- (id)init;
+- (id)initWithName:(NSString*)aName withParent:(FTree *)aParent withNode:(FTreeNode *)aNode;
+
+- (FTree *) subTree:(FPath*)path;
+- (id)getValue;
+- (void)setValue:(id)value;
+- (void) clear;
+- (BOOL) hasChildren;
+- (BOOL) isEmpty;
+- (void) forEachChildMutationSafe:(void (^)(FTree *))action;
+- (void) forEachChild:(void (^)(FTree *))action;
+- (void) forEachDescendant:(void (^)(FTree *))action;
+- (void) forEachDescendant:(void (^)(FTree *))action includeSelf:(BOOL)incSelf childrenFirst:(BOOL)childFirst;
+- (BOOL) forEachAncestor:(BOOL (^)(FTree *))action;
+- (BOOL) forEachAncestor:(BOOL (^)(FTree *))action includeSelf:(BOOL)incSelf;
+- (void) forEachImmediateDescendantWithValue:(void (^)(FTree *))action;
+- (BOOL) valueExistsAtOrAbove:(FPath *)path;
+- (FPath *)path;
+- (void) updateParents;
+- (void) updateChild:(NSString*)childName withNode:(FTree *)child;
+
+@property (nonatomic, strong) NSString* name;
+@property (nonatomic, strong) FTree* parent;
+@property (nonatomic, strong) FTreeNode* node;
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FTree.m b/Firebase/Database/Core/Utilities/FTree.m
new file mode 100644
index 0000000..8576ffb
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FTree.m
@@ -0,0 +1,183 @@
+/*
+ * 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 "FTree.h"
+#import "FTreeNode.h"
+#import "FPath.h"
+#import "FUtilities.h"
+
+@implementation FTree
+
+@synthesize name;
+@synthesize parent;
+@synthesize node;
+
+- (id)init
+{
+    self = [super init];
+    if (self) {
+        self.name = @"";
+        self.parent = nil;
+        self.node = [[FTreeNode alloc] init];
+    }
+    return self;
+}
+
+
+- (id)initWithName:(NSString*)aName withParent:(FTree *)aParent withNode:(FTreeNode *)aNode
+{
+    self = [super init];
+    if (self) {
+        self.name = aName != nil ? aName : @"";
+        self.parent = aParent != nil ? aParent : nil;
+        self.node = aNode != nil ? aNode : [[FTreeNode alloc] init];
+    }
+    return self;
+}
+
+- (FTree *) subTree:(FPath*)path {
+    FTree* child = self;
+    NSString* next = [path getFront];
+    while(next != nil) {
+        FTreeNode* childNode = child.node.children[next];
+        if (childNode == nil) {
+            childNode = [[FTreeNode alloc] init];
+        }
+        child = [[FTree alloc] initWithName:next withParent:child withNode:childNode];
+        path = [path popFront];
+        next = [path getFront];
+    }
+    return child;
+}
+
+- (id)getValue {
+    return self.node.value;
+}
+
+- (void)setValue:(id)value {
+    self.node.value = value;
+    [self updateParents];
+}
+
+- (void) clear {
+    self.node.value = nil;
+    [self.node.children removeAllObjects];
+    self.node.childCount = 0;
+    [self updateParents];
+}
+
+- (BOOL) hasChildren {
+    return self.node.childCount > 0;
+}
+
+- (BOOL) isEmpty {
+    return [self getValue] == nil && ![self hasChildren];
+}
+
+- (void) forEachChild:(void (^)(FTree *))action {
+    for(NSString* key in self.node.children) {
+        action([[FTree alloc] initWithName:key withParent:self withNode:[self.node.children objectForKey:key]]);
+    }
+}
+
+- (void) forEachChildMutationSafe:(void (^)(FTree *))action {
+    for(NSString* key in [self.node.children copy]) {
+        action([[FTree alloc] initWithName:key withParent:self withNode:[self.node.children objectForKey:key]]);
+    }
+}
+
+- (void) forEachDescendant:(void (^)(FTree *))action {
+    [self forEachDescendant:action includeSelf:NO childrenFirst:NO];
+}
+
+- (void) forEachDescendant:(void (^)(FTree *))action includeSelf:(BOOL)incSelf childrenFirst:(BOOL)childFirst {
+    if(incSelf && !childFirst) {
+        action(self);
+    }
+    
+    [self forEachChild:^(FTree* child) {
+        [child forEachDescendant:action includeSelf:YES childrenFirst:childFirst];
+    }];
+    
+    if(incSelf && childFirst) {
+        action(self);
+    }
+}
+
+- (BOOL) forEachAncestor:(BOOL (^)(FTree *))action {
+    return [self forEachAncestor:action includeSelf:NO];
+}
+
+- (BOOL) forEachAncestor:(BOOL (^)(FTree *))action includeSelf:(BOOL)incSelf {
+    FTree* aNode = (incSelf) ? self : self.parent;
+    while(aNode != nil) {
+        if(action(aNode)) {
+            return YES;
+        }
+        aNode = aNode.parent;
+    }
+    return NO;
+}
+
+- (void) forEachImmediateDescendantWithValue:(void (^)(FTree *))action {
+    [self forEachChild:^(FTree * child) {
+        if([child getValue] != nil) {
+            action(child);
+        }
+        else {
+            [child forEachImmediateDescendantWithValue:action];
+        }
+    }];
+}
+
+- (BOOL) valueExistsAtOrAbove:(FPath *)path {
+    FTreeNode* aNode = self.node;
+    while(aNode != nil) {
+        if(aNode.value != nil) {
+            return YES;
+        }
+        aNode = [aNode.children objectForKey:path.getFront];
+        path = [path popFront];
+    }
+    // XXX Check with Michael if this is correct; deviates from JS.
+    return NO;
+}
+
+- (FPath *)path {
+    return [[FPath alloc] initWith:(self.parent == nil) ? self.name :
+            [NSString stringWithFormat:@"%@/%@", [self.parent path], self.name ]];
+}
+
+- (void) updateParents {
+    [self.parent updateChild:self.name withNode:self];
+}
+
+- (void) updateChild:(NSString*)childName withNode:(FTree *)child {
+    BOOL childEmpty = [child isEmpty];
+    BOOL childExists = self.node.children[childName] != nil;
+    if(childEmpty && childExists) {
+        [self.node.children removeObjectForKey:childName];
+        self.node.childCount = self.node.childCount - 1;
+        [self updateParents];
+    }
+    else if(!childEmpty && !childExists) {
+        [self.node.children setObject:child.node forKey:childName];
+        self.node.childCount = self.node.childCount + 1;
+        [self updateParents];
+    }
+}
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FTreeNode.h b/Firebase/Database/Core/Utilities/FTreeNode.h
new file mode 100644
index 0000000..7e3497e
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FTreeNode.h
@@ -0,0 +1,25 @@
+/*
+ * 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>
+
+@interface FTreeNode : NSObject
+
+@property (nonatomic, strong) NSMutableDictionary* children;
+@property (nonatomic, readwrite, assign) int childCount;
+@property (nonatomic, strong) id value;
+
+@end
diff --git a/Firebase/Database/Core/Utilities/FTreeNode.m b/Firebase/Database/Core/Utilities/FTreeNode.m
new file mode 100644
index 0000000..9cba9c5
--- /dev/null
+++ b/Firebase/Database/Core/Utilities/FTreeNode.m
@@ -0,0 +1,36 @@
+/*
+ * 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 "FTreeNode.h"
+
+@implementation FTreeNode
+
+@synthesize children;
+@synthesize childCount;
+@synthesize value;
+
+- (id)init
+{
+    self = [super init];
+    if (self) {
+        self.children = [[NSMutableDictionary alloc] init];
+        self.childCount = 0;
+        self.value = nil;
+    }
+    return self;
+}
+
+@end