Release 4.3.0 (#327)

Initial release of Firestore at 0.8.0
Bump FirebaseCommunity to 0.1.3

25 files changed, 3111 insertions, 0 deletions

diff --git a/Firestore/third_party/Immutable/FSTArraySortedDictionary.h b/Firestore/third_party/Immutable/FSTArraySortedDictionary.h
new file mode 100644
index 0000000..4b78360
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTArraySortedDictionary.h
@@ -0,0 +1,35 @@
+#import <Foundation/Foundation.h>
+
+#import "FSTImmutableSortedDictionary.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * FSTArraySortedDictionary is an array backed implementation of FSTImmutableSortedDictionary.
+ *
+ * You should not use this class directly. You should use FSTImmutableSortedDictionary.
+ *
+ * FSTArraySortedDictionary uses arrays and linear lookups to achieve good memory efficiency while
+ * maintaining good performance for small collections. It also uses fewer allocations than a
+ * comparable red black tree. To avoid degrading performance with increasing collection size it
+ * will automatically convert to a FSTTreeSortedDictionary after an insert call above a certain
+ * threshold.
+ */
+@interface FSTArraySortedDictionary <KeyType, ValueType> :
+    FSTImmutableSortedDictionary<KeyType, ValueType>
+
++ (FSTArraySortedDictionary<KeyType, ValueType> *)
+    dictionaryWithDictionary:(NSDictionary<KeyType, ValueType> *)dictionary
+                  comparator:(NSComparator)comparator;
+
+- (id)init __attribute__((unavailable("Use initWithComparator:keys:values: instead.")));
+
+- (instancetype)initWithComparator:(NSComparator)comparator;
+
+- (instancetype)initWithComparator:(NSComparator)comparator
+                              keys:(NSArray<KeyType> *)keys
+                            values:(NSArray<ValueType> *)values NS_DESIGNATED_INITIALIZER;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTArraySortedDictionary.m b/Firestore/third_party/Immutable/FSTArraySortedDictionary.m
new file mode 100644
index 0000000..fd3bfd7
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTArraySortedDictionary.m
@@ -0,0 +1,242 @@
+#import "FSTArraySortedDictionary.h"
+
+#import "FSTArraySortedDictionaryEnumerator.h"
+#import "FSTAssert.h"
+#import "FSTTreeSortedDictionary.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTArraySortedDictionary ()
+@property(nonatomic, copy, readwrite) NSComparator comparator;
+@property(nonatomic, strong) NSArray<id> *keys;
+@property(nonatomic, strong) NSArray<id> *values;
+@end
+
+@implementation FSTArraySortedDictionary
+
++ (FSTArraySortedDictionary *)dictionaryWithDictionary:(NSDictionary *)dictionary
+                                            comparator:(NSComparator)comparator {
+  NSMutableArray *keys = [NSMutableArray arrayWithCapacity:dictionary.count];
+  [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
+    [keys addObject:key];
+  }];
+  [keys sortUsingComparator:comparator];
+
+  [keys enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
+    if (idx > 0) {
+      if (comparator(keys[idx - 1], obj) != NSOrderedAscending) {
+        [NSException raise:NSInvalidArgumentException
+                    format:
+                        @"Can't create FSTImmutableSortedDictionary with keys "
+                        @"with same ordering!"];
+      }
+    }
+  }];
+
+  NSMutableArray *values = [NSMutableArray arrayWithCapacity:keys.count];
+  NSInteger pos = 0;
+  for (id key in keys) {
+    values[pos++] = dictionary[key];
+  }
+  FSTAssert(values.count == keys.count, @"We added as many keys as values");
+  return [[FSTArraySortedDictionary alloc] initWithComparator:comparator keys:keys values:values];
+}
+
+- (id)initWithComparator:(NSComparator)comparator {
+  return [self initWithComparator:comparator keys:[NSArray array] values:[NSArray array]];
+}
+
+// Designated initializer.
+- (id)initWithComparator:(NSComparator)comparator keys:(NSArray *)keys values:(NSArray *)values {
+  self = [super init];
+  if (self != nil) {
+    FSTAssert(keys.count == values.count, @"keys and values must have the same count");
+    _comparator = comparator;
+    _keys = keys;
+    _values = values;
+  }
+  return self;
+}
+
+/** Returns the index of the first position where array[position] >= key.  */
+- (int)findInsertPositionForKey:(id)key {
+  int newPos = 0;
+  while (newPos < self.keys.count && self.comparator(self.keys[newPos], key) < NSOrderedSame) {
+    newPos++;
+  }
+  return newPos;
+}
+
+- (NSInteger)findKey:(id)key {
+  if (key == nil) {
+    return NSNotFound;
+  }
+  for (NSInteger pos = 0; pos < self.keys.count; pos++) {
+    NSComparisonResult result = self.comparator(key, self.keys[pos]);
+    if (result == NSOrderedSame) {
+      return pos;
+    } else if (result == NSOrderedAscending) {
+      return NSNotFound;
+    }
+  }
+  return NSNotFound;
+}
+
+- (FSTImmutableSortedDictionary *)dictionaryBySettingObject:(id)value forKey:(id)key {
+  NSInteger pos = [self findKey:key];
+
+  if (pos == NSNotFound) {
+    /*
+     * If we're above the threshold we want to convert it to a tree backed implementation to not
+     * have degrading performance
+     */
+    if (self.count >= kSortedDictionaryArrayToRBTreeSizeThreshold) {
+      NSMutableDictionary *dict = [NSMutableDictionary dictionaryWithCapacity:self.count];
+      for (NSInteger i = 0; i < self.keys.count; i++) {
+        dict[self.keys[i]] = self.values[i];
+      }
+      dict[key] = value;
+      return [FSTTreeSortedDictionary dictionaryWithDictionary:dict comparator:self.comparator];
+    } else {
+      NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys];
+      NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values];
+      NSInteger newPos = [self findInsertPositionForKey:key];
+      [newKeys insertObject:key atIndex:newPos];
+      [newValues insertObject:value atIndex:newPos];
+      return [[FSTArraySortedDictionary alloc] initWithComparator:self.comparator
+                                                             keys:newKeys
+                                                           values:newValues];
+    }
+  } else {
+    NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys];
+    NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values];
+    newKeys[pos] = key;
+    newValues[pos] = value;
+    return [[FSTArraySortedDictionary alloc] initWithComparator:self.comparator
+                                                           keys:newKeys
+                                                         values:newValues];
+  }
+}
+
+- (FSTImmutableSortedDictionary *)dictionaryByRemovingObjectForKey:(id)key {
+  NSInteger pos = [self findKey:key];
+  if (pos == NSNotFound) {
+    return self;
+  } else {
+    NSMutableArray *newKeys = [NSMutableArray arrayWithArray:self.keys];
+    NSMutableArray *newValues = [NSMutableArray arrayWithArray:self.values];
+    [newKeys removeObjectAtIndex:pos];
+    [newValues removeObjectAtIndex:pos];
+    return [[FSTArraySortedDictionary alloc] initWithComparator:self.comparator
+                                                           keys:newKeys
+                                                         values:newValues];
+  }
+}
+
+- (nullable id)objectForKey:(id)key {
+  NSInteger pos = [self findKey:key];
+  if (pos == NSNotFound) {
+    return nil;
+  } else {
+    return self.values[pos];
+  }
+}
+
+- (nullable id)predecessorKey:(id)key {
+  NSInteger pos = [self findKey:key];
+  if (pos == NSNotFound) {
+    [NSException raise:NSInternalInconsistencyException
+                format:@"Can't get predecessor key for non-existent key"];
+    return nil;
+  } else if (pos == 0) {
+    return nil;
+  } else {
+    return self.keys[pos - 1];
+  }
+}
+
+- (NSUInteger)indexOfKey:(id)key {
+  return [self findKey:key];
+}
+
+- (BOOL)isEmpty {
+  return self.keys.count == 0;
+}
+
+- (NSUInteger)count {
+  return self.keys.count;
+}
+
+- (id)minKey {
+  return [self.keys firstObject];
+}
+
+- (id)maxKey {
+  return [self.keys lastObject];
+}
+
+- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block {
+  [self enumerateKeysAndObjectsReverse:NO usingBlock:block];
+}
+
+- (void)enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block {
+  if (reverse) {
+    BOOL stop = NO;
+    for (NSInteger i = self.keys.count - 1; i >= 0; i--) {
+      block(self.keys[i], self.values[i], &stop);
+      if (stop) return;
+    }
+  } else {
+    BOOL stop = NO;
+    for (NSInteger i = 0; i < self.keys.count; i++) {
+      block(self.keys[i], self.values[i], &stop);
+      if (stop) return;
+    }
+  }
+}
+
+- (BOOL)containsKey:(id)key {
+  return [self findKey:key] != NSNotFound;
+}
+
+- (NSEnumerator *)keyEnumerator {
+  return [self.keys objectEnumerator];
+}
+
+- (NSEnumerator *)keyEnumeratorFrom:(id)startKey {
+  return [self keyEnumeratorFrom:startKey to:nil];
+}
+
+- (NSEnumerator *)keyEnumeratorFrom:(id)startKey to:(nullable id)endKey {
+  int start = [self findInsertPositionForKey:startKey];
+  int end = (int)self.count;
+  if (endKey) {
+    end = [self findInsertPositionForKey:endKey];
+  }
+  return [[FSTArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys
+                                                         startPos:start
+                                                           endPos:end
+                                                        isReverse:NO];
+}
+
+- (NSEnumerator *)reverseKeyEnumerator {
+  return [self.keys reverseObjectEnumerator];
+}
+
+- (NSEnumerator *)reverseKeyEnumeratorFrom:(id)startKey {
+  int startPos = [self findInsertPositionForKey:startKey];
+  // if there's no exact match, findKeyOrInsertPosition will return the index *after* the closest
+  // match, but since this is a reverse iterator, we want to start just *before* the closest match.
+  if (startPos >= self.keys.count ||
+      self.comparator(self.keys[startPos], startKey) != NSOrderedSame) {
+    startPos -= 1;
+  }
+  return [[FSTArraySortedDictionaryEnumerator alloc] initWithKeys:self.keys
+                                                         startPos:startPos
+                                                           endPos:-1
+                                                        isReverse:YES];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.h b/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.h
new file mode 100644
index 0000000..36c4f32
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.h
@@ -0,0 +1,26 @@
+#import <Foundation/Foundation.h>
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTArraySortedDictionaryEnumerator <KeyType, ValueType> : NSEnumerator<ValueType>
+
+- (id)init __attribute__((unavailable("Use initWithKeys:startPos:endPos:isReverse: instead.")));
+
+/**
+ * An enumerator for use with a dictionary.
+ *
+ * @param keys The keys to enumerator within.
+ * @param start The index of the initial key to return.
+ * @param end If end is after (or equal to) start (or before, if reverse), then the enumerator will
+ *            stop and not return the value once it reaches end.
+ */
+- (instancetype)initWithKeys:(NSArray<KeyType> *)keys
+                    startPos:(int)start
+                      endPos:(int)end
+                   isReverse:(BOOL)reverse NS_DESIGNATED_INITIALIZER;
+
+- (_Nullable ValueType)nextObject;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.m b/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.m
new file mode 100644
index 0000000..e8fdfcc
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTArraySortedDictionaryEnumerator.m
@@ -0,0 +1,54 @@
+#import "FSTArraySortedDictionaryEnumerator.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+// clang-format off
+// For some reason, clang-format messes this line up...
+@interface FSTArraySortedDictionaryEnumerator<KeyType, ValueType> ()
+@property(nonatomic, assign) int pos;
+@property(nonatomic, assign) int start;
+@property(nonatomic, assign) int end;
+@property(nonatomic, assign) BOOL reverse;
+@property(nonatomic, strong) NSArray<KeyType> *keys;
+@end
+// clang-format on
+
+@implementation FSTArraySortedDictionaryEnumerator
+
+- (id)initWithKeys:(NSArray *)keys startPos:(int)start endPos:(int)end isReverse:(BOOL)reverse {
+  self = [super init];
+  if (self != nil) {
+    _keys = keys;
+    _start = start;
+    _end = end;
+    _pos = start;
+    _reverse = reverse;
+  }
+  return self;
+}
+
+- (nullable id)nextObject {
+  if (self.pos < 0 || self.pos >= self.keys.count) {
+    return nil;
+  }
+  if (self.reverse) {
+    if (self.pos <= self.end) {
+      return nil;
+    }
+  } else {
+    if (self.pos >= self.end) {
+      return nil;
+    }
+  }
+  int pos = self.pos;
+  if (self.reverse) {
+    self.pos--;
+  } else {
+    self.pos++;
+  }
+  return self.keys[pos];
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.h b/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.h
new file mode 100644
index 0000000..a2264ec
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.h
@@ -0,0 +1,120 @@
+/**
+ * Implementation of an immutable SortedMap using a Left-leaning Red-Black Tree, adapted from the
+ * implementation in Mugs (http://mads379.github.com/mugs/) by Mads Hartmann Jensen
+ * (mads379@gmail.com).
+ *
+ * Original paper on Left-leaning Red-Black Trees:
+ * http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
+ *
+ * Invariant 1: No red node has a red child
+ * Invariant 2: Every leaf path has the same number of black nodes
+ * Invariant 3: Only the left child can be red (left leaning)
+ */
+
+#import <Foundation/Foundation.h>
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * The size threshold where we use a tree backed sorted map instead of an array backed sorted map.
+ * This is a more or less arbitrary chosen value, that was chosen to be large enough to fit most of
+ * object kind of Firebase data, but small enough to not notice degradation in performance for
+ * inserting and lookups. Feel free to empirically determine this constant, but don't expect much
+ * gain in real world performance.
+ */
+extern const int kSortedDictionaryArrayToRBTreeSizeThreshold;
+
+/**
+ * FSTImmutableSortedDictionary is a dictionary. It is immutable, but has methods to create new
+ * dictionaries that are mutations of it, in an efficient way.
+ */
+@interface FSTImmutableSortedDictionary <KeyType, __covariant ValueType> : NSObject
+
++ (FSTImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator;
++ (FSTImmutableSortedDictionary *)dictionaryWithDictionary:
+                                      (NSDictionary<KeyType, ValueType> *)dictionary
+                                                comparator:(NSComparator)comparator;
+
+/**
+ * Creates a new dictionary identical to this one, but with a key-value pair added or updated.
+ *
+ * @param aValue The value to associate with the key.
+ * @param aKey The key to insert/update.
+ * @return A new dictionary with the added/updated value.
+ */
+- (FSTImmutableSortedDictionary<KeyType, ValueType> *)dictionaryBySettingObject:(ValueType)aValue
+                                                                         forKey:(KeyType)aKey;
+
+/**
+ * Creates a new dictionary identical to this one, but with a key removed from it.
+ *
+ * @param aKey The key to remove.
+ * @return A new dictionary without that value.
+ */
+- (FSTImmutableSortedDictionary<KeyType, ValueType> *)dictionaryByRemovingObjectForKey:
+    (KeyType)aKey;
+
+/**
+ * Looks up a value in the dictionary.
+ *
+ * @param key The key to look up.
+ * @return The value for the key, if present.
+ */
+- (nullable ValueType)objectForKey:(KeyType)key;
+
+/**
+ * Looks up a value in the dictionary.
+ *
+ * @param key The key to look up.
+ * @return The value for the key, if present.
+ */
+- (ValueType)objectForKeyedSubscript:(KeyType)key;
+
+/**
+ * Gets the key before the given key in sorted order.
+ *
+ * @param key The key to look before.
+ * @return The key before the given one.
+ */
+- (nullable KeyType)predecessorKey:(KeyType)key;
+
+/**
+ * Returns the index of the key or NSNotFound if the key is not found.
+ *
+ * @param key The key to return the index for.
+ * @return The index of the key, or NSNotFound if key not found.
+ */
+- (NSUInteger)indexOfKey:(KeyType)key;
+
+/** Returns true if the dictionary contains no elements. */
+- (BOOL)isEmpty;
+
+/** Returns the number of items in this dictionary. */
+- (NSUInteger)count;
+
+/** Returns the smallest key in this dictionary. */
+- (KeyType)minKey;
+
+/** Returns the largest key in this dictionary. */
+- (KeyType)maxKey;
+
+/** Calls the given block with each of the items in this dictionary, in order. */
+- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(KeyType key, ValueType value, BOOL *stop))block;
+
+/** Calls the given block with each of the items in this dictionary, in reverse order. */
+- (void)enumerateKeysAndObjectsReverse:(BOOL)reverse
+                            usingBlock:(void (^)(KeyType key, ValueType value, BOOL *stop))block;
+
+/** Returns true if the dictionary contains the given key. */
+- (BOOL)containsKey:(KeyType)key;
+
+- (NSEnumerator<KeyType> *)keyEnumerator;
+- (NSEnumerator<KeyType> *)keyEnumeratorFrom:(KeyType)startKey;
+/** Enumerator for the range [startKey, endKey). */
+- (NSEnumerator<KeyType> *)keyEnumeratorFrom:(KeyType)startKey to:(nullable KeyType)endKey;
+- (NSEnumerator<KeyType> *)reverseKeyEnumerator;
+- (NSEnumerator<KeyType> *)reverseKeyEnumeratorFrom:(KeyType)startKey;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.m b/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.m
new file mode 100644
index 0000000..a858529
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTImmutableSortedDictionary.m
@@ -0,0 +1,143 @@
+#import "FSTImmutableSortedDictionary.h"
+
+#import "FSTArraySortedDictionary.h"
+#import "FSTClasses.h"
+#import "FSTTreeSortedDictionary.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+const int kSortedDictionaryArrayToRBTreeSizeThreshold = 25;
+
+@implementation FSTImmutableSortedDictionary
+
++ (FSTImmutableSortedDictionary *)dictionaryWithComparator:(NSComparator)comparator {
+  return [[FSTArraySortedDictionary alloc] initWithComparator:comparator];
+}
+
++ (FSTImmutableSortedDictionary *)dictionaryWithDictionary:(NSDictionary *)dictionary
+                                                comparator:(NSComparator)comparator {
+  if (dictionary.count <= kSortedDictionaryArrayToRBTreeSizeThreshold) {
+    return [FSTArraySortedDictionary dictionaryWithDictionary:dictionary comparator:comparator];
+  } else {
+    return [FSTTreeSortedDictionary dictionaryWithDictionary:dictionary comparator:comparator];
+  }
+}
+
+- (FSTImmutableSortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (FSTImmutableSortedDictionary *)dictionaryByRemovingObjectForKey:(id)aKey {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (BOOL)isEqual:(id)object {
+  if (![object isKindOfClass:[FSTImmutableSortedDictionary class]]) {
+    return NO;
+  }
+
+  // TODO(klimt): We could make this more efficient if we put the comparison inside the
+  // implementations and short-circuit if they share the same tree node, for instance.
+  FSTImmutableSortedDictionary *other = (FSTImmutableSortedDictionary *)object;
+  if (self.count != other.count) {
+    return NO;
+  }
+  __block BOOL isEqual = YES;
+  [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+    id otherValue = [other objectForKey:key];
+    isEqual = isEqual && (value == otherValue || [value isEqual:otherValue]);
+    *stop = !isEqual;
+  }];
+  return isEqual;
+}
+
+- (NSUInteger)hash {
+  __block NSUInteger hash = 0;
+  [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+    hash = (hash * 31 + [key hash]) * 17 + [value hash];
+  }];
+  return hash;
+}
+
+- (NSString *)description {
+  NSMutableString *str = [[NSMutableString alloc] init];
+  __block BOOL first = YES;
+  [str appendString:@"{ "];
+  [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+    if (!first) {
+      [str appendString:@", "];
+    }
+    first = NO;
+    [str appendString:[NSString stringWithFormat:@"%@: %@", key, value]];
+  }];
+  [str appendString:@" }"];
+  return str;
+}
+
+- (nullable id)objectForKey:(id)key {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (id)objectForKeyedSubscript:(id)key {
+  return [self objectForKey:key];
+}
+
+- (nullable id)predecessorKey:(id)key {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (NSUInteger)indexOfKey:(id)key {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (BOOL)isEmpty {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (NSUInteger)count {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (id)minKey {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (id)maxKey {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (void)enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (BOOL)containsKey:(id)key {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (NSEnumerator *)keyEnumerator {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (NSEnumerator *)keyEnumeratorFrom:(id)startKey {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (NSEnumerator *)keyEnumeratorFrom:(id)startKey to:(nullable id)endKey {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (NSEnumerator *)reverseKeyEnumerator {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+- (NSEnumerator *)reverseKeyEnumeratorFrom:(id)startKey {
+  @throw FSTAbstractMethodException();  // NOLINT
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTImmutableSortedSet.h b/Firestore/third_party/Immutable/FSTImmutableSortedSet.h
new file mode 100644
index 0000000..d0f9906
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTImmutableSortedSet.h
@@ -0,0 +1,47 @@
+#import <Foundation/Foundation.h>
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * FSTImmutableSortedSet is a set. It is immutable, but has methods to create new sets that are
+ * mutations of it, in an efficient way.
+ */
+@interface FSTImmutableSortedSet <KeyType> : NSObject
+
++ (FSTImmutableSortedSet<KeyType> *)setWithComparator:(NSComparator)comparator;
+
++ (FSTImmutableSortedSet<KeyType> *)setWithKeysFromDictionary:(NSDictionary<KeyType, id> *)array
+                                                   comparator:(NSComparator)comparator;
+
+- (BOOL)containsObject:(KeyType)object;
+
+- (FSTImmutableSortedSet<KeyType> *)setByAddingObject:(KeyType)object;
+- (FSTImmutableSortedSet<KeyType> *)setByRemovingObject:(KeyType)object;
+
+- (KeyType)firstObject;
+- (KeyType)lastObject;
+- (NSUInteger)count;
+- (BOOL)isEmpty;
+
+- (KeyType)predecessorObject:(KeyType)entry;
+
+/**
+ * Returns the index of the object or NSNotFound if the object is not found.
+ *
+ * @param object The object to return the index for.
+ * @return The index of the object, or NSNotFound if not found.
+ */
+- (NSUInteger)indexOfObject:(KeyType)object;
+
+- (void)enumerateObjectsUsingBlock:(void (^)(KeyType obj, BOOL *stop))block;
+- (void)enumerateObjectsFrom:(KeyType)start
+                          to:(_Nullable KeyType)end
+                  usingBlock:(void (^)(KeyType obj, BOOL *stop))block;
+- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(KeyType obj, BOOL *stop))block;
+
+- (NSEnumerator<KeyType> *)objectEnumerator;
+- (NSEnumerator<KeyType> *)objectEnumeratorFrom:(KeyType)startKey;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTImmutableSortedSet.m b/Firestore/third_party/Immutable/FSTImmutableSortedSet.m
new file mode 100644
index 0000000..a13a79e
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTImmutableSortedSet.m
@@ -0,0 +1,144 @@
+#import "FSTImmutableSortedSet.h"
+
+#import "FSTImmutableSortedDictionary.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTImmutableSortedSet ()
+@property(nonatomic, strong) FSTImmutableSortedDictionary *dictionary;
+@end
+
+@implementation FSTImmutableSortedSet
+
++ (FSTImmutableSortedSet *)setWithComparator:(NSComparator)comparator {
+  return [FSTImmutableSortedSet setWithKeysFromDictionary:@{} comparator:comparator];
+}
+
++ (FSTImmutableSortedSet *)setWithKeysFromDictionary:(NSDictionary *)dictionary
+                                          comparator:(NSComparator)comparator {
+  FSTImmutableSortedDictionary *setDict =
+      [FSTImmutableSortedDictionary dictionaryWithDictionary:dictionary comparator:comparator];
+  return [[FSTImmutableSortedSet alloc] initWithDictionary:setDict];
+}
+
+// Designated initializer.
+- (id)initWithDictionary:(FSTImmutableSortedDictionary *)dictionary {
+  self = [super init];
+  if (self != nil) {
+    _dictionary = dictionary;
+  }
+  return self;
+}
+
+- (BOOL)isEqual:(id)object {
+  if (![object isKindOfClass:[FSTImmutableSortedSet class]]) {
+    return NO;
+  }
+
+  FSTImmutableSortedSet *other = (FSTImmutableSortedSet *)object;
+
+  return [self.dictionary isEqual:other.dictionary];
+}
+
+- (NSUInteger)hash {
+  return [self.dictionary hash];
+}
+
+- (BOOL)containsObject:(id)object {
+  return [self.dictionary containsKey:object];
+}
+
+- (FSTImmutableSortedSet *)setByAddingObject:(id)object {
+  FSTImmutableSortedDictionary *newDictionary =
+      [self.dictionary dictionaryBySettingObject:[NSNull null] forKey:object];
+  if (newDictionary != self.dictionary) {
+    return [[FSTImmutableSortedSet alloc] initWithDictionary:newDictionary];
+  } else {
+    return self;
+  }
+}
+
+- (FSTImmutableSortedSet *)setByRemovingObject:(id)object {
+  FSTImmutableSortedDictionary *newDictionary =
+      [self.dictionary dictionaryByRemovingObjectForKey:object];
+  if (newDictionary != self.dictionary) {
+    return [[FSTImmutableSortedSet alloc] initWithDictionary:newDictionary];
+  } else {
+    return self;
+  }
+}
+
+- (id)firstObject {
+  return [self.dictionary minKey];
+}
+
+- (id)lastObject {
+  return [self.dictionary maxKey];
+}
+
+- (id)predecessorObject:(id)entry {
+  return [self.dictionary predecessorKey:entry];
+}
+
+- (NSUInteger)indexOfObject:(id)object {
+  return [self.dictionary indexOfKey:object];
+}
+
+- (NSUInteger)count {
+  return [self.dictionary count];
+}
+
+- (BOOL)isEmpty {
+  return [self.dictionary isEmpty];
+}
+
+- (void)enumerateObjectsUsingBlock:(void (^)(id, BOOL *))block {
+  [self enumerateObjectsReverse:NO usingBlock:block];
+}
+
+- (void)enumerateObjectsFrom:(id)start to:(_Nullable id)end usingBlock:(void (^)(id, BOOL *))block {
+  NSEnumerator *enumerator = [self.dictionary keyEnumeratorFrom:start to:end];
+  id item = [enumerator nextObject];
+  while (item) {
+    BOOL stop = NO;
+    block(item, &stop);
+    if (stop) {
+      return;
+    }
+    item = [enumerator nextObject];
+  }
+}
+
+- (void)enumerateObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, BOOL *))block {
+  [self.dictionary enumerateKeysAndObjectsReverse:reverse
+                                       usingBlock:^(id key, id value, BOOL *stop) {
+                                         block(key, stop);
+                                       }];
+}
+
+- (NSEnumerator *)objectEnumerator {
+  return [self.dictionary keyEnumerator];
+}
+
+- (NSEnumerator *)objectEnumeratorFrom:(id)startKey {
+  return [self.dictionary keyEnumeratorFrom:startKey];
+}
+
+- (NSString *)description {
+  NSMutableString *str = [[NSMutableString alloc] init];
+  __block BOOL first = YES;
+  [str appendString:@"FSTImmutableSortedSet ( "];
+  [self enumerateObjectsUsingBlock:^(id obj, BOOL *stop) {
+    if (!first) {
+      [str appendString:@", "];
+    }
+    first = NO;
+    [str appendString:[NSString stringWithFormat:@"%@", obj]];
+  }];
+  [str appendString:@" )"];
+  return str;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTLLRBEmptyNode.h b/Firestore/third_party/Immutable/FSTLLRBEmptyNode.h
new file mode 100644
index 0000000..4c3c2af
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTLLRBEmptyNode.h
@@ -0,0 +1,11 @@
+#import <Foundation/Foundation.h>
+
+#import "FSTLLRBNode.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLLRBEmptyNode : NSObject <FSTLLRBNode>
++ (instancetype)emptyNode;
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTLLRBEmptyNode.m b/Firestore/third_party/Immutable/FSTLLRBEmptyNode.m
new file mode 100644
index 0000000..ec49c2c
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTLLRBEmptyNode.m
@@ -0,0 +1,102 @@
+#import "FSTLLRBEmptyNode.h"
+
+#import "FSTLLRBValueNode.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTLLRBEmptyNode
+
+- (NSString *)description {
+  return @"[empty node]";
+}
+
++ (instancetype)emptyNode {
+  static dispatch_once_t pred = 0;
+  __strong static id _sharedObject = nil;
+  dispatch_once(&pred, ^{
+    _sharedObject = [[self alloc] init];  // or some other init method
+  });
+  return _sharedObject;
+}
+
+- (nullable id)key {
+  return nil;
+}
+
+- (nullable id)value {
+  return nil;
+}
+
+- (FSTLLRBColor)color {
+  return FSTLLRBColorUnspecified;
+}
+
+- (nullable id<FSTLLRBNode>)left {
+  return nil;
+}
+
+- (nullable id<FSTLLRBNode>)right {
+  return nil;
+}
+
+- (instancetype)copyWith:(id _Nullable)aKey
+               withValue:(id _Nullable)aValue
+               withColor:(FSTLLRBColor)aColor
+                withLeft:(id<FSTLLRBNode> _Nullable)aLeft
+               withRight:(id<FSTLLRBNode> _Nullable)aRight {
+  // This class is a singleton anyway, so this is more efficient than calling the constructor again.
+  return self;
+}
+
+- (id<FSTLLRBNode>)insertKey:(id)aKey forValue:(id)aValue withComparator:(NSComparator)aComparator {
+  FSTLLRBValueNode *result = [[FSTLLRBValueNode alloc] initWithKey:aKey
+                                                         withValue:aValue
+                                                         withColor:FSTLLRBColorUnspecified
+                                                          withLeft:nil
+                                                         withRight:nil];
+  return result;
+}
+
+- (id<FSTLLRBNode>)remove:(id)key withComparator:(NSComparator)aComparator {
+  return self;
+}
+
+- (NSUInteger)count {
+  return 0;
+}
+
+- (BOOL)isEmpty {
+  return YES;
+}
+
+- (BOOL)inorderTraversal:(BOOL (^)(id key, id value))action {
+  return NO;
+}
+
+- (BOOL)reverseTraversal:(BOOL (^)(id key, id value))action {
+  return NO;
+}
+
+- (id<FSTLLRBNode>)min {
+  return self;
+}
+
+- (nullable id)minKey {
+  return nil;
+}
+
+- (nullable id)maxKey {
+  return nil;
+}
+
+- (BOOL)isRed {
+  return NO;
+}
+
+- (int)check {
+  return 0;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTLLRBNode.h b/Firestore/third_party/Immutable/FSTLLRBNode.h
new file mode 100644
index 0000000..082b875
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTLLRBNode.h
@@ -0,0 +1,68 @@
+#import <Foundation/Foundation.h>
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * A FSTLLRBColor is the color of a tree node. It can be RED, BLACK, or unset.
+ */
+typedef NS_ENUM(NSInteger, FSTLLRBColor) {
+  FSTLLRBColorUnspecified = 0,
+  FSTLLRBColorRed = 1,
+  FSTLLRBColorBlack = 2,
+};
+
+/**
+ * FSTLLRBNode is the interface for a node in a FSTTreeSortedDictionary.
+ */
+@protocol FSTLLRBNode <NSObject>
+
+/**
+ * Creates a copy of the given node, changing any values that were specified.
+ * For any parameter that is left as nil, this instance's value will be used.
+ */
+- (instancetype)copyWith:(nullable id)aKey
+               withValue:(nullable id)aValue
+               withColor:(FSTLLRBColor)aColor
+                withLeft:(nullable id<FSTLLRBNode>)aLeft
+               withRight:(nullable id<FSTLLRBNode>)aRight;
+
+/** Returns a tree node with the given key-value pair set/updated. */
+- (id<FSTLLRBNode>)insertKey:(id)aKey forValue:(id)aValue withComparator:(NSComparator)aComparator;
+
+/** Returns a tree node with the given key removed. */
+- (id<FSTLLRBNode>)remove:(id)key withComparator:(NSComparator)aComparator;
+
+/** Returns the number of elements at this node or beneath it in the tree. */
+- (NSUInteger)count;
+
+/** Returns true if this is an FSTLLRBEmptyNode -- a leaf node in the tree. */
+- (BOOL)isEmpty;
+
+- (BOOL)inorderTraversal:(BOOL (^)(id key, id value))action;
+- (BOOL)reverseTraversal:(BOOL (^)(id key, id value))action;
+
+/** Returns the left-most node under (or including) this node. */
+- (id<FSTLLRBNode>)min;
+
+/** Returns the key of the left-most node under (or including) this node. */
+- (nullable id)minKey;
+
+/** Returns the key of the right-most node under (or including) this node. */
+- (nullable id)maxKey;
+
+/** Returns true if this node is red (as opposed to black). */
+- (BOOL)isRed;
+
+/** Checks that this node and below it hold the red-black invariants. Throws otherwise. */
+- (int)check;
+
+// Accessors for properties.
+- (nullable id)key;
+- (nullable id)value;
+- (FSTLLRBColor)color;
+- (nullable id<FSTLLRBNode>)left;
+- (nullable id<FSTLLRBNode>)right;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTLLRBValueNode.h b/Firestore/third_party/Immutable/FSTLLRBValueNode.h
new file mode 100644
index 0000000..4a0873c
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTLLRBValueNode.h
@@ -0,0 +1,29 @@
+#import <Foundation/Foundation.h>
+
+#import "FSTLLRBNode.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLLRBValueNode : NSObject <FSTLLRBNode>
+
+- (id)init __attribute__((
+    unavailable("Use initWithKey:withValue:withColor:withLeft:withRight: instead.")));
+
+- (instancetype)initWithKey:(nullable id)key
+                  withValue:(nullable id)value
+                  withColor:(FSTLLRBColor)color
+                   withLeft:(nullable id<FSTLLRBNode>)left
+                  withRight:(nullable id<FSTLLRBNode>)right NS_DESIGNATED_INITIALIZER;
+
+@property(nonatomic, assign, readonly) FSTLLRBColor color;
+@property(nonatomic, strong, readonly, nullable) id key;
+@property(nonatomic, strong, readonly, nullable) id value;
+@property(nonatomic, strong, readonly, nullable) id<FSTLLRBNode> right;
+
+// This property cannot be readonly, because it is set when building the tree.
+// TODO(klimt): Find a way to build the tree without mutating this.
+@property(nonatomic, strong, nullable) id<FSTLLRBNode> left;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTLLRBValueNode.m b/Firestore/third_party/Immutable/FSTLLRBValueNode.m
new file mode 100644
index 0000000..d048012
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTLLRBValueNode.m
@@ -0,0 +1,308 @@
+#import "FSTLLRBValueNode.h"
+
+#import "FSTAssert.h"
+#import "FSTLLRBEmptyNode.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTLLRBValueNode ()
+@property(nonatomic, assign) FSTLLRBColor color;
+@property(nonatomic, assign) NSUInteger count;
+@property(nonatomic, strong) id key;
+@property(nonatomic, strong) id value;
+@property(nonatomic, strong) id<FSTLLRBNode> right;
+@end
+
+@implementation FSTLLRBValueNode
+
+- (NSString *)colorDescription {
+  NSString *color = @"unspecified";
+  if (self.color == FSTLLRBColorRed) {
+    color = @"red";
+  } else if (self.color == FSTLLRBColorBlack) {
+    color = @"black";
+  }
+  return color;
+}
+
+- (NSString *)description {
+  NSString *color = self.colorDescription;
+  return [NSString stringWithFormat:@"[key=%@ val=%@ color=%@]", self.key, self.value, color];
+}
+
+// Designated initializer.
+- (instancetype)initWithKey:(id _Nullable)aKey
+                  withValue:(id _Nullable)aValue
+                  withColor:(FSTLLRBColor)aColor
+                   withLeft:(id<FSTLLRBNode> _Nullable)aLeft
+                  withRight:(id<FSTLLRBNode> _Nullable)aRight {
+  self = [super init];
+  if (self) {
+    _key = aKey;
+    _value = aValue;
+    _color = aColor != FSTLLRBColorUnspecified ? aColor : FSTLLRBColorRed;
+    _left = aLeft != nil ? aLeft : [FSTLLRBEmptyNode emptyNode];
+    _right = aRight != nil ? aRight : [FSTLLRBEmptyNode emptyNode];
+    _count = NSNotFound;
+  }
+  return self;
+}
+
+- (instancetype)copyWith:(id _Nullable)aKey
+               withValue:(id _Nullable)aValue
+               withColor:(FSTLLRBColor)aColor
+                withLeft:(id<FSTLLRBNode> _Nullable)aLeft
+               withRight:(id<FSTLLRBNode> _Nullable)aRight {
+  return [[FSTLLRBValueNode alloc]
+      initWithKey:(aKey != nil) ? aKey : self.key
+        withValue:(aValue != nil) ? aValue : self.value
+        withColor:(aColor != FSTLLRBColorUnspecified) ? aColor : self.color
+         withLeft:(aLeft != nil) ? aLeft : self.left
+        withRight:(aRight != nil) ? aRight : self.right];
+}
+
+- (void)setLeft:(nullable id<FSTLLRBNode>)left {
+  // Setting the left node should be only done by the builder, so doing it after someone has
+  // memoized count is an error.
+  FSTAssert(_count == NSNotFound, @"Can't update left node after using count");
+  _left = left;
+}
+
+- (NSUInteger)count {
+  if (_count == NSNotFound) {
+    _count = _left.count + 1 + _right.count;
+  }
+  return _count;
+}
+
+- (BOOL)isEmpty {
+  return NO;
+}
+
+/**
+ * Early terminates if action returns YES.
+ *
+ * @return The first truthy value returned by action, or the last falsey value returned by action.
+ */
+- (BOOL)inorderTraversal:(BOOL (^)(id key, id value))action {
+  return [self.left inorderTraversal:action] || action(self.key, self.value) ||
+         [self.right inorderTraversal:action];
+}
+
+- (BOOL)reverseTraversal:(BOOL (^)(id key, id value))action {
+  return [self.right reverseTraversal:action] || action(self.key, self.value) ||
+         [self.left reverseTraversal:action];
+}
+
+- (id<FSTLLRBNode>)min {
+  if ([self.left isEmpty]) {
+    return self;
+  } else {
+    return [self.left min];
+  }
+}
+
+- (nullable id)minKey {
+  return [[self min] key];
+}
+
+- (nullable id)maxKey {
+  if ([self.right isEmpty]) {
+    return self.key;
+  } else {
+    return [self.right maxKey];
+  }
+}
+
+- (id<FSTLLRBNode>)insertKey:(id)aKey forValue:(id)aValue withComparator:(NSComparator)aComparator {
+  NSComparisonResult cmp = aComparator(aKey, self.key);
+  FSTLLRBValueNode *n = self;
+
+  if (cmp == NSOrderedAscending) {
+    n = [n copyWith:nil
+          withValue:nil
+          withColor:FSTLLRBColorUnspecified
+           withLeft:[n.left insertKey:aKey forValue:aValue withComparator:aComparator]
+          withRight:nil];
+  } else if (cmp == NSOrderedSame) {
+    n = [n copyWith:nil
+          withValue:aValue
+          withColor:FSTLLRBColorUnspecified
+           withLeft:nil
+          withRight:nil];
+  } else {
+    n = [n copyWith:nil
+          withValue:nil
+          withColor:FSTLLRBColorUnspecified
+           withLeft:nil
+          withRight:[n.right insertKey:aKey forValue:aValue withComparator:aComparator]];
+  }
+
+  return [n fixUp];
+}
+
+- (id<FSTLLRBNode>)removeMin {
+  if ([self.left isEmpty]) {
+    return [FSTLLRBEmptyNode emptyNode];
+  }
+
+  FSTLLRBValueNode *n = self;
+  if (![n.left isRed] && ![n.left.left isRed]) {
+    n = [n moveRedLeft];
+  }
+
+  n = [n copyWith:nil
+        withValue:nil
+        withColor:FSTLLRBColorUnspecified
+         withLeft:[(FSTLLRBValueNode *)n.left removeMin]
+        withRight:nil];
+  return [n fixUp];
+}
+
+- (id<FSTLLRBNode>)fixUp {
+  FSTLLRBValueNode *n = self;
+  if ([n.right isRed] && ![n.left isRed]) n = [n rotateLeft];
+  if ([n.left isRed] && [n.left.left isRed]) n = [n rotateRight];
+  if ([n.left isRed] && [n.right isRed]) n = [n colorFlip];
+  return n;
+}
+
+- (FSTLLRBValueNode *)moveRedLeft {
+  FSTLLRBValueNode *n = [self colorFlip];
+  if ([n.right.left isRed]) {
+    n = [n copyWith:nil
+          withValue:nil
+          withColor:FSTLLRBColorUnspecified
+           withLeft:nil
+          withRight:[(FSTLLRBValueNode *)n.right rotateRight]];
+    n = [n rotateLeft];
+    n = [n colorFlip];
+  }
+  return n;
+}
+
+- (FSTLLRBValueNode *)moveRedRight {
+  FSTLLRBValueNode *n = [self colorFlip];
+  if ([n.left.left isRed]) {
+    n = [n rotateRight];
+    n = [n colorFlip];
+  }
+  return n;
+}
+
+- (id<FSTLLRBNode>)rotateLeft {
+  id<FSTLLRBNode> nl = [self copyWith:nil
+                            withValue:nil
+                            withColor:FSTLLRBColorRed
+                             withLeft:nil
+                            withRight:self.right.left];
+  return [self.right copyWith:nil withValue:nil withColor:self.color withLeft:nl withRight:nil];
+}
+
+- (id<FSTLLRBNode>)rotateRight {
+  id<FSTLLRBNode> nr = [self copyWith:nil
+                            withValue:nil
+                            withColor:FSTLLRBColorRed
+                             withLeft:self.left.right
+                            withRight:nil];
+  return [self.left copyWith:nil withValue:nil withColor:self.color withLeft:nil withRight:nr];
+}
+
+- (id<FSTLLRBNode>)colorFlip {
+  FSTLLRBColor color = self.color == FSTLLRBColorBlack ? FSTLLRBColorRed : FSTLLRBColorBlack;
+  FSTLLRBColor leftColor =
+      self.left.color == FSTLLRBColorBlack ? FSTLLRBColorRed : FSTLLRBColorBlack;
+  FSTLLRBColor rightColor =
+      self.right.color == FSTLLRBColorBlack ? FSTLLRBColorRed : FSTLLRBColorBlack;
+
+  id<FSTLLRBNode> nleft =
+      [self.left copyWith:nil withValue:nil withColor:leftColor withLeft:nil withRight:nil];
+  id<FSTLLRBNode> nright =
+      [self.right copyWith:nil withValue:nil withColor:rightColor withLeft:nil withRight:nil];
+
+  return [self copyWith:nil withValue:nil withColor:color withLeft:nleft withRight:nright];
+}
+
+- (id<FSTLLRBNode>)remove:(id)aKey withComparator:(NSComparator)comparator {
+  id<FSTLLRBNode> smallest;
+  FSTLLRBValueNode *n = self;
+
+  if (comparator(aKey, n.key) == NSOrderedAscending) {
+    if (![n.left isEmpty] && ![n.left isRed] && ![n.left.left isRed]) {
+      n = [n moveRedLeft];
+    }
+    n = [n copyWith:nil
+          withValue:nil
+          withColor:FSTLLRBColorUnspecified
+           withLeft:[n.left remove:aKey withComparator:comparator]
+          withRight:nil];
+  } else {
+    if ([n.left isRed]) {
+      n = [n rotateRight];
+    }
+
+    if (![n.right isEmpty] && ![n.right isRed] && ![n.right.left isRed]) {
+      n = [n moveRedRight];
+    }
+
+    if (comparator(aKey, n.key) == NSOrderedSame) {
+      if ([n.right isEmpty]) {
+        return [FSTLLRBEmptyNode emptyNode];
+      } else {
+        smallest = [n.right min];
+        n = [n copyWith:smallest.key
+              withValue:smallest.value
+              withColor:FSTLLRBColorUnspecified
+               withLeft:nil
+              withRight:[(FSTLLRBValueNode *)n.right removeMin]];
+      }
+    }
+    n = [n copyWith:nil
+          withValue:nil
+          withColor:FSTLLRBColorUnspecified
+           withLeft:nil
+          withRight:[n.right remove:aKey withComparator:comparator]];
+  }
+  return [n fixUp];
+}
+
+- (BOOL)isRed {
+  return self.color == FSTLLRBColorRed;
+}
+
+- (BOOL)checkMaxDepth {
+  int blackDepth = [self check];
+  if (pow(2.0, blackDepth) <= ([self count] + 1)) {
+    return YES;
+  } else {
+    return NO;
+  }
+}
+
+- (int)check {
+  int blackDepth = 0;
+
+  if ([self isRed] && [self.left isRed]) {
+    @throw
+        [[NSException alloc] initWithName:@"check" reason:@"Red node has a red child" userInfo:nil];
+  }
+
+  if ([self.right isRed]) {
+    @throw [[NSException alloc] initWithName:@"check" reason:@"Right child is red" userInfo:nil];
+  }
+
+  blackDepth = [self.left check];
+  if (blackDepth != [self.right check]) {
+    NSString *err =
+        [NSString stringWithFormat:@"(%@ -> %@)blackDepth: %d ; self.right check: %d", self.value,
+                                   self.colorDescription, blackDepth, [self.right check]];
+    @throw [[NSException alloc] initWithName:@"check" reason:err userInfo:nil];
+  } else {
+    int ret = blackDepth + ([self isRed] ? 0 : 1);
+    return ret;
+  }
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTTreeSortedDictionary.h b/Firestore/third_party/Immutable/FSTTreeSortedDictionary.h
new file mode 100644
index 0000000..6c26e5f
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTTreeSortedDictionary.h
@@ -0,0 +1,41 @@
+/**
+ * Implementation of an immutable SortedMap using a Left-leaning
+ * Red-Black Tree, adapted from the implementation in Mugs
+ * (http://mads379.github.com/mugs/) by Mads Hartmann Jensen
+ * (mads379@gmail.com).
+ *
+ * Original paper on Left-leaning Red-Black Trees:
+ *   http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
+ *
+ * Invariant 1: No red node has a red child
+ * Invariant 2: Every leaf path has the same number of black nodes
+ * Invariant 3: Only the left child can be red (left leaning)
+ */
+
+#import <Foundation/Foundation.h>
+
+#import "FSTImmutableSortedDictionary.h"
+#import "FSTLLRBNode.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ * FSTTreeSortedDictionary is a tree-based implementation of FSTImmutableSortedDictionary.
+ * You should not use this class directly. You should use FSTImmutableSortedDictionary.
+ */
+@interface FSTTreeSortedDictionary <KeyType, ValueType> :
+    FSTImmutableSortedDictionary<KeyType, ValueType>
+
+@property(nonatomic, copy, readonly) NSComparator comparator;
+@property(nonatomic, strong, readonly) id<FSTLLRBNode> root;
+
+- (id)init __attribute__((unavailable("Use initWithComparator:withRoot: instead.")));
+
+- (instancetype)initWithComparator:(NSComparator)aComparator;
+
+- (instancetype)initWithComparator:(NSComparator)aComparator
+                          withRoot:(id<FSTLLRBNode>)aRoot NS_DESIGNATED_INITIALIZER;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTTreeSortedDictionary.m b/Firestore/third_party/Immutable/FSTTreeSortedDictionary.m
new file mode 100644
index 0000000..4059951
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTTreeSortedDictionary.m
@@ -0,0 +1,382 @@
+#import "FSTTreeSortedDictionary.h"
+
+#import "FSTLLRBEmptyNode.h"
+#import "FSTLLRBValueNode.h"
+#import "FSTTreeSortedDictionaryEnumerator.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTTreeSortedDictionary ()
+
+- (FSTTreeSortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey;
+
+@property(nonatomic, strong) id<FSTLLRBNode> root;
+@property(nonatomic, copy, readwrite) NSComparator comparator;
+@end
+
+@implementation FSTTreeSortedDictionary
+
++ (FSTTreeSortedDictionary *)dictionaryWithDictionary:(NSDictionary *)dictionary
+                                           comparator:(NSComparator)comparator {
+  __block FSTTreeSortedDictionary *dict =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:comparator];
+  [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
+    dict = [dict dictionaryBySettingObject:obj forKey:key];
+  }];
+  return dict;
+}
+
+- (id)initWithComparator:(NSComparator)aComparator {
+  return [self initWithComparator:aComparator withRoot:[FSTLLRBEmptyNode emptyNode]];
+}
+
+// Designated initializer.
+- (id)initWithComparator:(NSComparator)aComparator withRoot:(id<FSTLLRBNode>)aRoot {
+  self = [super init];
+  if (self) {
+    self.root = aRoot;
+    self.comparator = aComparator;
+  }
+  return self;
+}
+
+/**
+ * Returns a copy of the map, with the specified key/value added or replaced.
+ */
+- (FSTTreeSortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey {
+  return [[FSTTreeSortedDictionary alloc]
+      initWithComparator:self.comparator
+                withRoot:[[self.root insertKey:aKey forValue:aValue withComparator:self.comparator]
+                              copyWith:nil
+                             withValue:nil
+                             withColor:FSTLLRBColorBlack
+                              withLeft:nil
+                             withRight:nil]];
+}
+
+- (FSTTreeSortedDictionary *)dictionaryByRemovingObjectForKey:(id)aKey {
+  // Remove is somewhat expensive even if the key doesn't exist (the tree does rebalancing and
+  // stuff).  So avoid it.
+  if (![self containsKey:aKey]) {
+    return self;
+  } else {
+    return [[FSTTreeSortedDictionary alloc]
+        initWithComparator:self.comparator
+                  withRoot:[[self.root remove:aKey withComparator:self.comparator]
+                                copyWith:nil
+                               withValue:nil
+                               withColor:FSTLLRBColorBlack
+                                withLeft:nil
+                               withRight:nil]];
+  }
+}
+
+- (nullable id)objectForKey:(id)key {
+  NSComparisonResult cmp;
+  id<FSTLLRBNode> node = self.root;
+  while (![node isEmpty]) {
+    cmp = self.comparator(key, node.key);
+    if (cmp == NSOrderedSame) {
+      return node.value;
+    } else if (cmp == NSOrderedAscending) {
+      node = node.left;
+    } else {
+      node = node.right;
+    }
+  }
+  return nil;
+}
+
+- (nullable id)predecessorKey:(id)key {
+  NSComparisonResult cmp;
+  id<FSTLLRBNode> node = self.root;
+  id<FSTLLRBNode> rightParent = nil;
+  while (![node isEmpty]) {
+    cmp = self.comparator(key, node.key);
+    if (cmp == NSOrderedSame) {
+      if (![node.left isEmpty]) {
+        node = node.left;
+        while (![node.right isEmpty]) {
+          node = node.right;
+        }
+        return node.key;
+      } else if (rightParent != nil) {
+        return rightParent.key;
+      } else {
+        return nil;
+      }
+    } else if (cmp == NSOrderedAscending) {
+      node = node.left;
+    } else if (cmp == NSOrderedDescending) {
+      rightParent = node;
+      node = node.right;
+    }
+  }
+  @throw [NSException exceptionWithName:@"NonexistentKey"
+                                 reason:@"getPredecessorKey called with nonexistent key."
+                               userInfo:@{@"key" : [key description]}];
+}
+
+- (NSUInteger)indexOfKey:(id)key {
+  NSUInteger prunedNodes = 0;
+  id<FSTLLRBNode> node = self.root;
+  while (![node isEmpty]) {
+    NSComparisonResult cmp = self.comparator(key, node.key);
+    if (cmp == NSOrderedSame) {
+      return prunedNodes + node.left.count;
+    } else if (cmp == NSOrderedAscending) {
+      node = node.left;
+    } else if (cmp == NSOrderedDescending) {
+      prunedNodes += node.left.count + 1;
+      node = node.right;
+    }
+  }
+  return NSNotFound;
+}
+
+- (BOOL)isEmpty {
+  return [self.root isEmpty];
+}
+
+- (NSUInteger)count {
+  return [self.root count];
+}
+
+- (id)minKey {
+  return [self.root minKey];
+}
+
+- (id)maxKey {
+  return [self.root maxKey];
+}
+
+- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id, id, BOOL *))block {
+  [self enumerateKeysAndObjectsReverse:NO usingBlock:block];
+}
+
+- (void)enumerateKeysAndObjectsReverse:(BOOL)reverse usingBlock:(void (^)(id, id, BOOL *))block {
+  if (reverse) {
+    __block BOOL stop = NO;
+    [self.root reverseTraversal:^BOOL(id key, id value) {
+      block(key, value, &stop);
+      return stop;
+    }];
+  } else {
+    __block BOOL stop = NO;
+    [self.root inorderTraversal:^BOOL(id key, id value) {
+      block(key, value, &stop);
+      return stop;
+    }];
+  }
+}
+
+- (BOOL)containsKey:(id)key {
+  return ([self objectForKey:key] != nil);
+}
+
+- (NSEnumerator *)keyEnumerator {
+  return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self
+                                                                             startKey:nil
+                                                                               endKey:nil
+                                                                            isReverse:NO];
+}
+
+- (NSEnumerator *)keyEnumeratorFrom:(id)startKey {
+  return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self
+                                                                             startKey:startKey
+                                                                               endKey:nil
+                                                                            isReverse:NO];
+}
+
+- (NSEnumerator *)keyEnumeratorFrom:(id)startKey to:(nullable id)endKey {
+  return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self
+                                                                             startKey:startKey
+                                                                               endKey:endKey
+                                                                            isReverse:NO];
+}
+
+- (NSEnumerator *)reverseKeyEnumerator {
+  return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self
+                                                                             startKey:nil
+                                                                               endKey:nil
+                                                                            isReverse:YES];
+}
+
+- (NSEnumerator *)reverseKeyEnumeratorFrom:(id)startKey {
+  return [[FSTTreeSortedDictionaryEnumerator alloc] initWithImmutableSortedDictionary:self
+                                                                             startKey:startKey
+                                                                               endKey:nil
+                                                                            isReverse:YES];
+}
+
+#pragma mark -
+#pragma mark Tree Builder
+
+// Code to efficiently build a red black tree.
+
+typedef struct {
+  unsigned int bits;
+  unsigned short count;
+  unsigned short current;
+} Base12List;
+
+unsigned int LogBase2(unsigned int num) {
+  return (unsigned int)(log(num) / log(2));
+}
+
+/**
+ * Works like an iterator, so it moves to the next bit. Do not call more than list->count times.
+ * @return whether or not the next bit is a 1 in base {1,2}.
+ */
+BOOL Base12ListNext(Base12List *list) {
+  BOOL result = !(list->bits & (0x1 << list->current));
+  list->current--;
+  return result;
+}
+
+static inline unsigned BitMask(int x) {
+  return (x >= sizeof(unsigned) * CHAR_BIT) ? (unsigned)-1 : (1U << x) - 1;
+}
+
+/**
+ * We represent the base{1,2} number as the combination of a binary number and a number of bits that
+ * we care about. We iterate backwards, from most significant bit to least, to build up the llrb
+ * nodes. 0 base 2 => 1 base {1,2}, 1 base 2 => 2 base {1,2}
+ */
+Base12List *NewBase12List(unsigned int length) {
+  size_t sz = sizeof(Base12List);
+  Base12List *list = calloc(1, sz);
+  // Calculate the number of bits that we care about
+  list->count = (unsigned short)LogBase2(length + 1);
+  unsigned int mask = BitMask(list->count);
+  list->bits = (length + 1) & mask;
+  list->current = list->count - 1;
+  return list;
+}
+
+void FreeBase12List(Base12List *list) {
+  free(list);
+}
+
++ (id<FSTLLRBNode>)buildBalancedTree:(NSArray *)keys
+                          dictionary:(NSDictionary *)dictionary
+                  subArrayStartIndex:(NSUInteger)startIndex
+                              length:(NSUInteger)length {
+  length = MIN(keys.count - startIndex, length);  // Bound length by the actual length of the array
+  if (length == 0) {
+    return nil;
+  } else if (length == 1) {
+    id key = keys[startIndex];
+    return [[FSTLLRBValueNode alloc] initWithKey:key
+                                       withValue:dictionary[key]
+                                       withColor:FSTLLRBColorBlack
+                                        withLeft:nil
+                                       withRight:nil];
+  } else {
+    NSUInteger middle = length / 2;
+    id<FSTLLRBNode> left = [FSTTreeSortedDictionary buildBalancedTree:keys
+                                                           dictionary:dictionary
+                                                   subArrayStartIndex:startIndex
+                                                               length:middle];
+    id<FSTLLRBNode> right = [FSTTreeSortedDictionary buildBalancedTree:keys
+                                                            dictionary:dictionary
+                                                    subArrayStartIndex:(startIndex + middle + 1)
+                                                                length:middle];
+    id key = keys[startIndex + middle];
+    return [[FSTLLRBValueNode alloc] initWithKey:key
+                                       withValue:dictionary[key]
+                                       withColor:FSTLLRBColorBlack
+                                        withLeft:left
+                                       withRight:right];
+  }
+}
+
++ (nullable id<FSTLLRBNode>)rootFrom12List:(Base12List *)base12List
+                          keyList:(NSArray *)keyList
+                       dictionary:(NSDictionary *)dictionary {
+  __block FSTLLRBValueNode *root = nil;
+  __block FSTLLRBValueNode *node = nil;
+  __block NSUInteger index = keyList.count;
+
+  void (^buildPennant)(FSTLLRBColor, NSUInteger) = ^(FSTLLRBColor color, NSUInteger chunkSize) {
+    NSUInteger startIndex = index - chunkSize + 1;
+    index -= chunkSize;
+    id key = keyList[index];
+    FSTLLRBValueNode *childTree = [self buildBalancedTree:keyList
+                                               dictionary:dictionary
+                                       subArrayStartIndex:startIndex
+                                                   length:(chunkSize - 1)];
+    FSTLLRBValueNode *pennant = [[FSTLLRBValueNode alloc] initWithKey:key
+                                                            withValue:dictionary[key]
+                                                            withColor:color
+                                                             withLeft:nil
+                                                            withRight:childTree];
+    if (node) {
+      // This is the only place this property is set.
+      node.left = pennant;
+      node = pennant;
+    } else {
+      root = pennant;
+      node = pennant;
+    }
+  };
+
+  for (int i = 0; i < base12List->count; ++i) {
+    BOOL isOne = Base12ListNext(base12List);
+    NSUInteger chunkSize = (NSUInteger)pow(2.0, base12List->count - (i + 1));
+    if (isOne) {
+      buildPennant(FSTLLRBColorBlack, chunkSize);
+    } else {
+      buildPennant(FSTLLRBColorBlack, chunkSize);
+      buildPennant(FSTLLRBColorRed, chunkSize);
+    }
+  }
+  return root;
+}
+
+/**
+ * Uses the algorithm linked here:
+ * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1458
+ */
++ (FSTImmutableSortedDictionary *)fromDictionary:(NSDictionary *)dictionary
+                                  withComparator:(NSComparator)comparator {
+  // Steps:
+  // 0. Sort the array
+  // 1. Calculate the 1-2 number
+  // 2. Build From 1-2 number
+  //   0. for each digit in 1-2 number
+  //     0. calculate chunk size
+  //     1. build 1 or 2 pennants of that size
+  //     2. attach pennants and update node pointer
+  //   1. return root
+  NSMutableArray *sortedKeyList = [NSMutableArray arrayWithCapacity:dictionary.count];
+  [dictionary enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
+    [sortedKeyList addObject:key];
+  }];
+  [sortedKeyList sortUsingComparator:comparator];
+
+  [sortedKeyList enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
+    if (idx > 0) {
+      if (comparator(sortedKeyList[idx - 1], obj) != NSOrderedAscending) {
+        [NSException raise:NSInvalidArgumentException
+                    format:
+                        @"Can't create FSTImmutableSortedDictionary "
+                        @"with keys with same ordering!"];
+      }
+    }
+  }];
+
+  Base12List *list = NewBase12List((unsigned int)sortedKeyList.count);
+  id<FSTLLRBNode> root = [self rootFrom12List:list keyList:sortedKeyList dictionary:dictionary];
+  FreeBase12List(list);
+
+  if (root != nil) {
+    return [[FSTTreeSortedDictionary alloc] initWithComparator:comparator withRoot:root];
+  } else {
+    return [[FSTTreeSortedDictionary alloc] initWithComparator:comparator];
+  }
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.h b/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.h
new file mode 100644
index 0000000..ab82f00
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.h
@@ -0,0 +1,21 @@
+#import <Foundation/Foundation.h>
+
+#import "FSTTreeSortedDictionary.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@interface FSTTreeSortedDictionaryEnumerator <KeyType, ValueType> : NSEnumerator<ValueType>
+
+- (id)init __attribute__((
+    unavailable("Use initWithImmutableSortedDictionary:startKey:isReverse: instead.")));
+
+- (instancetype)initWithImmutableSortedDictionary:
+                    (FSTTreeSortedDictionary<KeyType, ValueType> *)aDict
+                                         startKey:(KeyType _Nullable)startKey
+                                           endKey:(KeyType _Nullable)endKey
+                                        isReverse:(BOOL)reverse NS_DESIGNATED_INITIALIZER;
+- (nullable ValueType)nextObject;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.m b/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.m
new file mode 100644
index 0000000..bfdfba5
--- /dev/null
+++ b/Firestore/third_party/Immutable/FSTTreeSortedDictionaryEnumerator.m
@@ -0,0 +1,114 @@
+#import "FSTTreeSortedDictionaryEnumerator.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+// clang-format off
+// For some reason, clang-format messes this line up...
+@interface FSTTreeSortedDictionaryEnumerator<KeyType, ValueType> ()
+/** The dictionary being enumerated. */
+@property(nonatomic, strong) FSTTreeSortedDictionary<KeyType, ValueType> *immutableSortedDictionary;
+/** The stack of tree nodes above the current node that will need to be revisited later. */
+@property(nonatomic, strong) NSMutableArray<id<FSTLLRBNode>> *stack;
+/** The direction of the traversal. YES=Descending. NO=Ascending. */
+@property(nonatomic, assign) BOOL isReverse;
+/** If set, the enumerator should stop at this key and not return it. */
+@property(nonatomic, strong, nullable) id endKey;
+@end
+// clang-format on
+
+@implementation FSTTreeSortedDictionaryEnumerator
+
+- (instancetype)initWithImmutableSortedDictionary:(FSTTreeSortedDictionary *)aDict
+                                         startKey:(id _Nullable)startKey
+                                           endKey:(id _Nullable)endKey
+                                        isReverse:(BOOL)reverse {
+  self = [super init];
+  if (self) {
+    _immutableSortedDictionary = aDict;
+    _stack = [[NSMutableArray alloc] init];
+    _isReverse = reverse;
+    _endKey = endKey;
+
+    NSComparator comparator = aDict.comparator;
+    id<FSTLLRBNode> node = aDict.root;
+
+    NSComparisonResult comparedToStart;
+    NSComparisonResult comparedToEnd;
+    while (![node isEmpty]) {
+      comparedToStart = NSOrderedDescending;
+      if (startKey) {
+        comparedToStart = comparator(node.key, startKey);
+        if (reverse) {
+          comparedToStart *= -1;
+        }
+      }
+      comparedToEnd = NSOrderedAscending;
+      if (endKey) {
+        comparedToEnd = comparator(node.key, endKey);
+        if (reverse) {
+          comparedToEnd *= -1;
+        }
+      }
+
+      if (comparedToStart == NSOrderedAscending) {
+        // This node is less than our start key. Ignore it.
+        if (reverse) {
+          node = node.left;
+        } else {
+          node = node.right;
+        }
+      } else if (comparedToStart == NSOrderedSame) {
+        // This node is exactly equal to our start key. If it's less than the end key, push it on
+        // the stack, but stop iterating.
+        if (comparedToEnd == NSOrderedAscending) {
+          [_stack addObject:node];
+        }
+        break;
+      } else {
+        // This node is greater than our start key. If it's less than our end key, add it to the
+        // stack and move on to the next one.
+        if (comparedToEnd == NSOrderedAscending) {
+          [_stack addObject:node];
+        }
+        if (reverse) {
+          node = node.right;
+        } else {
+          node = node.left;
+        }
+      }
+    }
+  }
+  return self;
+}
+
+- (nullable id)nextObject {
+  if ([self.stack count] == 0) {
+    return nil;
+  }
+
+  id<FSTLLRBNode> node = [self.stack lastObject];
+  [self.stack removeLastObject];
+  id result = node.key;
+  NSComparator comparator = self.immutableSortedDictionary.comparator;
+
+  node = self.isReverse ? node.left : node.right;
+  while (![node isEmpty]) {
+    NSComparisonResult comparedToEnd = NSOrderedAscending;
+    if (self.endKey) {
+      comparedToEnd = comparator(node.key, self.endKey);
+      if (self.isReverse) {
+        comparedToEnd *= -1;
+      }
+    }
+    if (comparedToEnd == NSOrderedAscending) {
+      [self.stack addObject:node];
+    }
+    node = self.isReverse ? node.right : node.left;
+  }
+
+  return result;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/LICENSE b/Firestore/third_party/Immutable/LICENSE
new file mode 100644
index 0000000..b437003
--- /dev/null
+++ b/Firestore/third_party/Immutable/LICENSE
@@ -0,0 +1,21 @@
+Copyright (c) 2012 Mads Hartmann Jensen
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of
+this software and associated documentation files (the "Software"), to deal in
+the Software without restriction, including without limitation the rights to
+use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
+of the Software, and to permit persons to whom the Software is furnished to do
+so, subject to the following conditions:
+
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/Firestore/third_party/Immutable/Tests/FSTArraySortedDictionaryTests.m b/Firestore/third_party/Immutable/Tests/FSTArraySortedDictionaryTests.m
new file mode 100644
index 0000000..68f2fc3
--- /dev/null
+++ b/Firestore/third_party/Immutable/Tests/FSTArraySortedDictionaryTests.m
@@ -0,0 +1,467 @@
+#import "Immutable/FSTArraySortedDictionary.h"
+
+#import <XCTest/XCTest.h>
+
+#import "Util/FSTAssert.h"
+
+@interface FSTArraySortedDictionary (Test)
+// Override methods to return subtype.
+- (FSTArraySortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey;
+- (FSTArraySortedDictionary *)dictionaryByRemovingObjectForKey:(id)aKey;
+@end
+
+@interface FSTArraySortedDictionaryTests : XCTestCase
+@end
+
+@implementation FSTArraySortedDictionaryTests
+
+- (NSComparator)defaultComparator {
+  return ^(id obj1, id obj2) {
+    FSTAssert([obj1 respondsToSelector:@selector(compare:)] &&
+                  [obj2 respondsToSelector:@selector(compare:)],
+              @"Objects must support compare: %@ %@", obj1, obj2);
+    return [obj1 compare:obj2];
+  };
+}
+
+- (void)testSearchForSpecificKey {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+
+  XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found first object");
+  XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found second object");
+  XCTAssertEqualObjects(map[@1], @1, @"Found first object");
+  XCTAssertEqualObjects(map[@2], @2, @"Found second object");
+  XCTAssertNil([map objectForKey:@3], @"Properly not found object");
+}
+
+- (void)testRemoveKeyValuePair {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+
+  FSTImmutableSortedDictionary *newMap = [map dictionaryByRemovingObjectForKey:@1];
+  XCTAssertEqualObjects([newMap objectForKey:@2], @2, @"Found second object");
+  XCTAssertNil([newMap objectForKey:@1], @"Properly not found object");
+
+  // Make sure the original one is not mutated
+  XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found first object");
+  XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found second object");
+}
+
+- (void)testMoreRemovals {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@50 forKey:@50];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+  map = [map dictionaryBySettingObject:@7 forKey:@7];
+  map = [map dictionaryBySettingObject:@9 forKey:@9];
+  map = [map dictionaryBySettingObject:@1 forKey:@20];
+  map = [map dictionaryBySettingObject:@18 forKey:@18];
+  map = [map dictionaryBySettingObject:@3 forKey:@2];
+  map = [map dictionaryBySettingObject:@4 forKey:@71];
+  map = [map dictionaryBySettingObject:@7 forKey:@42];
+  map = [map dictionaryBySettingObject:@9 forKey:@88];
+
+  XCTAssertNotNil([map objectForKey:@7], @"Found object");
+  XCTAssertNotNil([map objectForKey:@3], @"Found object");
+  XCTAssertNotNil([map objectForKey:@1], @"Found object");
+
+  FSTImmutableSortedDictionary *m1 = [map dictionaryByRemovingObjectForKey:@7];
+  FSTImmutableSortedDictionary *m2 = [map dictionaryByRemovingObjectForKey:@3];
+  FSTImmutableSortedDictionary *m3 = [map dictionaryByRemovingObjectForKey:@1];
+
+  XCTAssertNil([m1 objectForKey:@7], @"Removed object");
+  XCTAssertNotNil([m1 objectForKey:@3], @"Found object");
+  XCTAssertNotNil([m1 objectForKey:@1], @"Found object");
+
+  XCTAssertNil([m2 objectForKey:@3], @"Removed object");
+  XCTAssertNotNil([m2 objectForKey:@7], @"Found object");
+  XCTAssertNotNil([m2 objectForKey:@1], @"Found object");
+
+  XCTAssertNil([m3 objectForKey:@1], @"Removed object");
+  XCTAssertNotNil([m3 objectForKey:@7], @"Found object");
+  XCTAssertNotNil([m3 objectForKey:@3], @"Found object");
+}
+
+- (void)testRemovalBug {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+
+  XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found object");
+  XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found object");
+  XCTAssertEqualObjects([map objectForKey:@3], @3, @"Found object");
+
+  FSTImmutableSortedDictionary *m1 = [map dictionaryByRemovingObjectForKey:@2];
+  XCTAssertEqualObjects([m1 objectForKey:@1], @1, @"Found object");
+  XCTAssertEqualObjects([m1 objectForKey:@3], @3, @"Found object");
+  XCTAssertNil([m1 objectForKey:@2], @"Removed object");
+}
+
+- (void)testIncreasing {
+  int total = 100;
+
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  for (int i = 0; i < total; i++) {
+    NSNumber *item = @(i);
+    map = [map dictionaryBySettingObject:item forKey:item];
+  }
+
+  XCTAssertTrue(map.count == 100, @"Check if all 100 objects are in the map");
+
+  for (int i = 0; i < total; i++) {
+    NSNumber *item = @(i);
+    map = [map dictionaryByRemovingObjectForKey:item];
+  }
+
+  XCTAssertTrue(map.count == 0, @"Check if all 100 objects were removed");
+}
+
+- (void)testOverride {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@10 forKey:@10];
+  map = [map dictionaryBySettingObject:@8 forKey:@10];
+
+  XCTAssertEqualObjects([map objectForKey:@10], @8, @"Found first object");
+}
+
+- (void)testEmpty {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@10 forKey:@10];
+  map = [map dictionaryByRemovingObjectForKey:@10];
+
+  XCTAssertTrue([map isEmpty], @"Properly empty");
+}
+
+- (void)testEmptyGet {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  XCTAssertNil([map objectForKey:@"something"], @"Properly nil");
+}
+
+- (void)testEmptyCount {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  XCTAssertTrue([map count] == 0, @"Properly zero count");
+}
+
+- (void)testEmptyRemoval {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryByRemovingObjectForKey:@"something"];
+  XCTAssertTrue(map.count == 0, @"Properly zero count");
+}
+
+- (void)testReverseTraversal {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@5 forKey:@5];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+
+  __block int next = 5;
+  [map enumerateKeysAndObjectsReverse:YES
+                           usingBlock:^(id key, id value, BOOL *stop) {
+                             XCTAssertEqualObjects(key, @(next), @"Properly equal");
+                             next = next - 1;
+                           }];
+}
+
+- (void)testInsertionAndRemovalOfAHundredItems {
+  NSUInteger n = 100;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+  NSMutableArray *toRemove = [NSMutableArray arrayWithCapacity:n];
+
+  for (NSUInteger i = 0; i < n; i++) {
+    [toInsert addObject:@(i)];
+    [toRemove addObject:@(i)];
+  }
+
+  [self shuffleArray:toInsert];
+  [self shuffleArray:toRemove];
+
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // add them to the dictionary
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+
+  // check the order is correct
+  __block int next = 0;
+  [map enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+    XCTAssertEqualObjects(key, @(next), @"Correct key");
+    XCTAssertEqualObjects(value, @(next), @"Correct value");
+    next = next + 1;
+  }];
+  XCTAssertEqual(next, n, @"Check we traversed all of the items");
+
+  // remove them
+
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryByRemovingObjectForKey:toRemove[i]];
+  }
+
+  XCTAssertEqual(map.count, 0, @"Check we removed all of the items");
+}
+
+- (void)shuffleArray:(NSMutableArray *)array {
+  NSUInteger count = array.count;
+  for (NSUInteger i = 0; i < count; i++) {
+    NSUInteger nElements = count - i;
+    NSUInteger n = (arc4random() % nElements) + i;
+    [array exchangeObjectAtIndex:i withObjectAtIndex:n];
+  }
+}
+
+- (void)testBalanceProblem {
+  NSArray *toInsert = @[ @1, @7, @8, @5, @2, @6, @4, @0, @3 ];
+
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // add them to the dictionary
+  for (NSUInteger i = 0; i < toInsert.count; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == toInsert.count, @"Check if all N objects are in the map");
+
+  // check the order is correct
+  __block int next = 0;
+  [map enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+    XCTAssertEqualObjects(key, @(next), @"Correct key");
+    XCTAssertEqualObjects(value, @(next), @"Correct value");
+    next = next + 1;
+  }];
+  XCTAssertEqual((int)next, (int)toInsert.count, @"Check we traversed all of the items");
+}
+
+- (void)testPredecessorKey {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@50 forKey:@50];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+  map = [map dictionaryBySettingObject:@7 forKey:@7];
+  map = [map dictionaryBySettingObject:@9 forKey:@9];
+
+  XCTAssertNil([map predecessorKey:@1], @"First object doesn't have a predecessor");
+  XCTAssertEqualObjects([map predecessorKey:@3], @1, @"@1");
+  XCTAssertEqualObjects([map predecessorKey:@4], @3, @"@3");
+  XCTAssertEqualObjects([map predecessorKey:@7], @4, @"@4");
+  XCTAssertEqualObjects([map predecessorKey:@9], @7, @"@7");
+  XCTAssertEqualObjects([map predecessorKey:@50], @9, @"@9");
+  XCTAssertThrows([map predecessorKey:@777], @"Expect exception about nonexistent key");
+}
+
+// This is a macro instead of a method so that the failures show on the proper lines.
+#define ASSERT_ENUMERATOR(enumerator, start, end, step)                                   \
+  do {                                                                                    \
+    NSEnumerator *e = (enumerator);                                                       \
+    id next = nil;                                                                        \
+    for (NSUInteger i = (start); i != (end); i += (step)) {                               \
+      next = [e nextObject];                                                              \
+      XCTAssertNotNil(next, @"expected %lu. got nil.", (unsigned long)i);                 \
+      XCTAssertEqualObjects(next, @(i), "expected %lu. got %@.", (unsigned long)i, next); \
+    }                                                                                     \
+    next = [e nextObject];                                                                \
+    XCTAssertNil(next, @"expected nil. got %@.", next);                                   \
+  } while (0)
+
+- (void)testEnumerator {
+  NSUInteger n = 100;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+  NSMutableArray *toRemove = [NSMutableArray arrayWithCapacity:n];
+
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i)];
+    [toRemove addObject:@(i)];
+  }
+
+  [self shuffleArray:toInsert];
+  [self shuffleArray:toRemove];
+
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:self.defaultComparator];
+
+  // add them to the dictionary
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+
+  ASSERT_ENUMERATOR([map keyEnumerator], 0, 100, 1);
+}
+
+- (void)testReverseEnumerator {
+  NSUInteger n = 20;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i)];
+  }
+
+  [self shuffleArray:toInsert];
+
+  FSTImmutableSortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // Add them to the dictionary.
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+  XCTAssertTrue([map isKindOfClass:FSTArraySortedDictionary.class],
+                @"Make sure we still have a array backed dictionary");
+
+  ASSERT_ENUMERATOR([map reverseKeyEnumerator], n - 1, -1, -1);
+}
+
+- (void)testEnumeratorFrom {
+  // Create a dictionary with the even numbers in [2, 42).
+  NSUInteger n = 20;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i * 2 + 2)];
+  }
+  [self shuffleArray:toInsert];
+
+  FSTImmutableSortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // Add them to the dictionary.
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+  XCTAssertTrue([map isKindOfClass:FSTArraySortedDictionary.class],
+                @"Make sure we still have a array backed dictionary");
+
+  // Test from before keys.
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0], 2, n * 2 + 2, 2);
+
+  // Test from after keys.
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100], 0, 0, 2);
+
+  // Test from key in map.
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@10], 10, n * 2 + 2, 2);
+
+  // Test from in between keys.
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@11], 12, n * 2 + 2, 2);
+}
+
+- (void)testEnumeratorFromTo {
+  // Create a dictionary with the even numbers in [2, 42).
+  NSUInteger n = 20;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i * 2 + 2)];
+  }
+  [self shuffleArray:toInsert];
+
+  FSTImmutableSortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // Add them to the dictionary.
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+  XCTAssertTrue([map isKindOfClass:FSTArraySortedDictionary.class],
+                @"Make sure we still have an array backed dictionary");
+
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@1], 2, 2, 2);            // before to before
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@100], 2, n * 2 + 2, 2);  // before to after
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@6], 2, 6, 2);            // before to key in map
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@7], 2, 8, 2);      // before to in between keys
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@0], 2, 2, 2);    // after to before
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@110], 2, 2, 2);  // after to after
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@6], 2, 2, 2);    // after to key in map
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@7], 2, 2, 2);    // after to in between
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@0], 6, 6, 2);      // key in map to before
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@100], 6, n * 2 + 2, 2);  // key in map to after
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@10], 6, 10, 2);  // key in map to key in map
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@11], 6, 12, 2);  // key in map to in between
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@0], 8, 8, 2);    // in between to before
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@100], 8, n * 2 + 2, 2);  // in between to after
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@10], 8, 10, 2);  // in between to key in map
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@13], 8, 14, 2);  // in between to in between
+}
+
+- (void)testReverseEnumeratorFrom {
+  NSUInteger n = 20;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i * 2 + 2)];
+  }
+
+  [self shuffleArray:toInsert];
+
+  FSTImmutableSortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // add them to the dictionary
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+  XCTAssertTrue([map isKindOfClass:FSTArraySortedDictionary.class],
+                @"Make sure we still have a array backed dictionary");
+
+  // Test from before keys.
+  ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@0], 0, 0, -2);
+
+  // Test from after keys.
+  ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@100], n * 2, 0, -2);
+
+  // Test from key in map.
+  ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@10], 10, 0, -2);
+
+  // Test from in between keys.
+  ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@11], 10, 0, -2);
+}
+
+#undef ASSERT_ENUMERATOR
+
+- (void)testIndexOf {
+  FSTArraySortedDictionary *map =
+      [[FSTArraySortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@50 forKey:@50];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+  map = [map dictionaryBySettingObject:@7 forKey:@7];
+  map = [map dictionaryBySettingObject:@9 forKey:@9];
+
+  XCTAssertEqual([map indexOfKey:@0], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@1], 0);
+  XCTAssertEqual([map indexOfKey:@2], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@3], 1);
+  XCTAssertEqual([map indexOfKey:@4], 2);
+  XCTAssertEqual([map indexOfKey:@5], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@6], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@7], 3);
+  XCTAssertEqual([map indexOfKey:@8], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@9], 4);
+  XCTAssertEqual([map indexOfKey:@50], 5);
+}
+
+@end
diff --git a/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.h b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.h
new file mode 100644
index 0000000..7496173
--- /dev/null
+++ b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.h
@@ -0,0 +1,17 @@
+#import <Foundation/Foundation.h>
+
+#import "Immutable/FSTImmutableSortedDictionary.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+// clang-format doesn't yet deal with generic parameters and categories :-(
+// clang-format off
+@interface FSTImmutableSortedDictionary<KeyType, __covariant ValueType> (Testing)
+
+/** Converts the values of the dictionary to an array preserving order. */
+- (NSArray<ValueType> *)values;
+
+@end
+// clang-format on
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.m b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.m
new file mode 100644
index 0000000..d402916
--- /dev/null
+++ b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedDictionary+Testing.m
@@ -0,0 +1,17 @@
+#import "FSTImmutableSortedDictionary+Testing.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTImmutableSortedDictionary (Testing)
+
+- (NSArray<id> *)values {
+  NSMutableArray<id> *result = [NSMutableArray array];
+  [self enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+    [result addObject:value];
+  }];
+  return result;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.h b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.h
new file mode 100644
index 0000000..a0e25d7
--- /dev/null
+++ b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.h
@@ -0,0 +1,20 @@
+#import "Immutable/FSTImmutableSortedSet.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+// clang-format doesn't yet deal with generic parameters and categories :-(
+// clang-format off
+@interface FSTImmutableSortedSet<T> (Testing)
+
+/**
+ * An array containing the set’s members, or an empty array if the set has no members.
+ *
+ * Implemented here for compatibility with NSSet in testing though we'd never want to do this
+ * in production code.
+ */
+- (NSArray<T> *)allObjects;
+
+@end
+// clang-format on
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.m b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.m
new file mode 100644
index 0000000..d4d81e0
--- /dev/null
+++ b/Firestore/third_party/Immutable/Tests/FSTImmutableSortedSet+Testing.m
@@ -0,0 +1,17 @@
+#import "FSTImmutableSortedSet+Testing.h"
+
+NS_ASSUME_NONNULL_BEGIN
+
+@implementation FSTImmutableSortedSet (Testing)
+
+- (NSArray<id> *)allObjects {
+  NSMutableArray<id> *result = [NSMutableArray array];
+  [self enumerateObjectsUsingBlock:^(id object, BOOL *stop) {
+    [result addObject:object];
+  }];
+  return result;
+}
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/Firestore/third_party/Immutable/Tests/FSTLLRBValueNode+Test.h b/Firestore/third_party/Immutable/Tests/FSTLLRBValueNode+Test.h
new file mode 100644
index 0000000..3b05647
--- /dev/null
+++ b/Firestore/third_party/Immutable/Tests/FSTLLRBValueNode+Test.h
@@ -0,0 +1,10 @@
+#import "Immutable/FSTLLRBValueNode.h"
+
+#import <Foundation/Foundation.h>
+
+/** Extra methods exposed only for testing. */
+@interface FSTLLRBValueNode (Test)
+- (id<FSTLLRBNode>)rotateLeft;
+- (id<FSTLLRBNode>)rotateRight;
+- (BOOL)checkMaxDepth;
+@end
diff --git a/Firestore/third_party/Immutable/Tests/FSTTreeSortedDictionaryTests.m b/Firestore/third_party/Immutable/Tests/FSTTreeSortedDictionaryTests.m
new file mode 100644
index 0000000..352ac4e
--- /dev/null
+++ b/Firestore/third_party/Immutable/Tests/FSTTreeSortedDictionaryTests.m
@@ -0,0 +1,655 @@
+#import <XCTest/XCTest.h>
+
+#import "Immutable/FSTLLRBEmptyNode.h"
+#import "Immutable/FSTLLRBNode.h"
+#import "Immutable/FSTLLRBValueNode.h"
+#import "Immutable/FSTTreeSortedDictionary.h"
+#import "Util/FSTAssert.h"
+
+#import "FSTLLRBValueNode+Test.h"
+
+@interface FSTTreeSortedDictionary (Test)
+// Override methods to return subtype.
+- (FSTTreeSortedDictionary *)dictionaryBySettingObject:(id)aValue forKey:(id)aKey;
+- (FSTTreeSortedDictionary *)dictionaryByRemovingObjectForKey:(id)aKey;
+@end
+
+@interface FSTTreeSortedDictionaryTests : XCTestCase
+@end
+
+@implementation FSTTreeSortedDictionaryTests
+
+- (NSComparator)defaultComparator {
+  return ^(id obj1, id obj2) {
+    FSTAssert([obj1 respondsToSelector:@selector(compare:)] &&
+                  [obj2 respondsToSelector:@selector(compare:)],
+              @"Objects must support compare: %@ %@", obj1, obj2);
+    return [obj1 compare:obj2];
+  };
+}
+
+- (void)testCreateNode {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@"value" forKey:@"key"];
+  XCTAssertTrue([map.root.left isEmpty], @"Left child is properly empty");
+  XCTAssertTrue([map.root.right isEmpty], @"Right child is properly empty");
+}
+
+- (void)testSearchForSpecificKey {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+
+  XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found first object");
+  XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found second object");
+  XCTAssertEqualObjects(map[@1], @1, @"Found first object");
+  XCTAssertEqualObjects(map[@2], @2, @"Found second object");
+  XCTAssertNil([map objectForKey:@3], @"Properly not found object");
+}
+
+- (void)testInsertNewKeyValuePair {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+
+  XCTAssertEqualObjects(map.root.key, @2, @"Check the root key");
+  XCTAssertEqualObjects(map.root.left.key, @1, @"Check the root.left key");
+}
+
+- (void)testRemoveKeyValuePair {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+
+  FSTImmutableSortedDictionary *newMap = [map dictionaryByRemovingObjectForKey:@1];
+  XCTAssertEqualObjects([newMap objectForKey:@2], @2, @"Found second object");
+  XCTAssertNil([newMap objectForKey:@1], @"Properly not found object");
+
+  // Make sure the original one is not mutated
+  XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found first object");
+  XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found second object");
+}
+
+- (void)testMoreRemovals {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@50 forKey:@50];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+  map = [map dictionaryBySettingObject:@7 forKey:@7];
+  map = [map dictionaryBySettingObject:@9 forKey:@9];
+  map = [map dictionaryBySettingObject:@1 forKey:@20];
+  map = [map dictionaryBySettingObject:@18 forKey:@18];
+  map = [map dictionaryBySettingObject:@3 forKey:@2];
+  map = [map dictionaryBySettingObject:@4 forKey:@71];
+  map = [map dictionaryBySettingObject:@7 forKey:@42];
+  map = [map dictionaryBySettingObject:@9 forKey:@88];
+
+  XCTAssertNotNil([map objectForKey:@7], @"Found object");
+  XCTAssertNotNil([map objectForKey:@3], @"Found object");
+  XCTAssertNotNil([map objectForKey:@1], @"Found object");
+
+  FSTImmutableSortedDictionary *m1 = [map dictionaryByRemovingObjectForKey:@7];
+  FSTImmutableSortedDictionary *m2 = [map dictionaryByRemovingObjectForKey:@3];
+  FSTImmutableSortedDictionary *m3 = [map dictionaryByRemovingObjectForKey:@1];
+
+  XCTAssertNil([m1 objectForKey:@7], @"Removed object");
+  XCTAssertNotNil([m1 objectForKey:@3], @"Found object");
+  XCTAssertNotNil([m1 objectForKey:@1], @"Found object");
+
+  XCTAssertNil([m2 objectForKey:@3], @"Removed object");
+  XCTAssertNotNil([m2 objectForKey:@7], @"Found object");
+  XCTAssertNotNil([m2 objectForKey:@1], @"Found object");
+
+  XCTAssertNil([m3 objectForKey:@1], @"Removed object");
+  XCTAssertNotNil([m3 objectForKey:@7], @"Found object");
+  XCTAssertNotNil([m3 objectForKey:@3], @"Found object");
+}
+
+- (void)testRemovalBug {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+
+  XCTAssertEqualObjects([map objectForKey:@1], @1, @"Found object");
+  XCTAssertEqualObjects([map objectForKey:@2], @2, @"Found object");
+  XCTAssertEqualObjects([map objectForKey:@3], @3, @"Found object");
+
+  FSTImmutableSortedDictionary *m1 = [map dictionaryByRemovingObjectForKey:@2];
+  XCTAssertEqualObjects([m1 objectForKey:@1], @1, @"Found object");
+  XCTAssertEqualObjects([m1 objectForKey:@3], @3, @"Found object");
+  XCTAssertNil([m1 objectForKey:@2], @"Removed object");
+}
+
+- (void)testIncreasing {
+  int total = 100;
+
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  for (int i = 0; i < total; i++) {
+    NSNumber *item = @(i);
+    map = [map dictionaryBySettingObject:item forKey:item];
+  }
+
+  XCTAssertTrue(map.count == 100, @"Check if all 100 objects are in the map");
+  XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+  XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth],
+                @"Checking valid depth and tree structure");
+
+  for (int i = 0; i < total; i++) {
+    NSNumber *item = @(i);
+    map = [map dictionaryByRemovingObjectForKey:item];
+  }
+
+  XCTAssertTrue(map.count == 0, @"Check if all 100 objects were removed");
+  // We can't check the depth here because the map no longer contains values, so we check that it
+  // doesn't respond to this check
+  XCTAssertTrue([map.root isMemberOfClass:FSTLLRBEmptyNode.class], @"Root is an empty node");
+  XCTAssertFalse([map respondsToSelector:@selector(checkMaxDepth)],
+                 @"The empty node doesn't respond to this selector.");
+}
+
+- (void)testStructureShouldBeValidAfterInsertionA {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+
+  XCTAssertEqualObjects(map.root.key, @2, @"Check root key");
+  XCTAssertEqualObjects(map.root.left.key, @1, @"Check the left key is correct");
+  XCTAssertEqualObjects(map.root.right.key, @3, @"Check the right key is correct");
+}
+
+- (void)testStructureShouldBeValidAfterInsertionB {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@50 forKey:@50];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+  map = [map dictionaryBySettingObject:@7 forKey:@7];
+  map = [map dictionaryBySettingObject:@9 forKey:@9];
+  map = [map dictionaryBySettingObject:@1 forKey:@20];
+  map = [map dictionaryBySettingObject:@18 forKey:@18];
+  map = [map dictionaryBySettingObject:@3 forKey:@2];
+  map = [map dictionaryBySettingObject:@4 forKey:@71];
+  map = [map dictionaryBySettingObject:@7 forKey:@42];
+  map = [map dictionaryBySettingObject:@9 forKey:@88];
+
+  XCTAssertTrue(map.count == 12, @"Check if all 12 objects are in the map");
+  XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+  XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth],
+                @"Checking valid depth and tree structure");
+}
+
+- (void)testRotateLeftLeavesTreeInAValidState {
+  FSTLLRBValueNode *node = [[FSTLLRBValueNode alloc]
+      initWithKey:@4
+        withValue:@4
+        withColor:FSTLLRBColorBlack
+         withLeft:[[FSTLLRBValueNode alloc] initWithKey:@2
+                                              withValue:@2
+                                              withColor:FSTLLRBColorBlack
+                                               withLeft:nil
+                                              withRight:nil]
+        withRight:[[FSTLLRBValueNode alloc]
+                      initWithKey:@7
+                        withValue:@7
+                        withColor:FSTLLRBColorRed
+                         withLeft:[[FSTLLRBValueNode alloc] initWithKey:@5
+                                                              withValue:@5
+                                                              withColor:FSTLLRBColorBlack
+                                                               withLeft:nil
+                                                              withRight:nil]
+                        withRight:[[FSTLLRBValueNode alloc] initWithKey:@8
+                                                              withValue:@8
+                                                              withColor:FSTLLRBColorBlack
+                                                               withLeft:nil
+                                                              withRight:nil]]];
+
+  FSTLLRBValueNode *node2 = [node rotateLeft];
+
+  XCTAssertTrue(node2.count == 5, @"Make sure the count is correct");
+  XCTAssertTrue([node2 checkMaxDepth], @"Check proper structure");
+}
+
+- (void)testRotateRightLeavesTreeInAValidState {
+  FSTLLRBValueNode *node = [[FSTLLRBValueNode alloc]
+      initWithKey:@7
+        withValue:@7
+        withColor:FSTLLRBColorBlack
+         withLeft:[[FSTLLRBValueNode alloc]
+                      initWithKey:@4
+                        withValue:@4
+                        withColor:FSTLLRBColorRed
+                         withLeft:[[FSTLLRBValueNode alloc] initWithKey:@2
+                                                              withValue:@2
+                                                              withColor:FSTLLRBColorBlack
+                                                               withLeft:nil
+                                                              withRight:nil]
+                        withRight:[[FSTLLRBValueNode alloc] initWithKey:@5
+                                                              withValue:@5
+                                                              withColor:FSTLLRBColorBlack
+                                                               withLeft:nil
+                                                              withRight:nil]]
+        withRight:[[FSTLLRBValueNode alloc] initWithKey:@8
+                                              withValue:@8
+                                              withColor:FSTLLRBColorBlack
+                                               withLeft:nil
+                                              withRight:nil]];
+
+  FSTLLRBValueNode *node2 = [node rotateRight];
+  XCTAssertTrue(node2.count == 5, @"Make sure the count is correct");
+  XCTAssertEqualObjects(node2.key, @4, @"Check roots key");
+  XCTAssertEqualObjects(node2.left.key, @2, @"Check first left child key");
+  XCTAssertEqualObjects(node2.right.key, @7, @"Check first right child key");
+  XCTAssertEqualObjects(node2.right.left.key, @5, @"Check second right left key");
+  XCTAssertEqualObjects(node2.right.right.key, @8, @"Check second right left key");
+}
+
+- (void)testStructureShouldBeValidAfterInsertionC {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@50 forKey:@50];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+  map = [map dictionaryBySettingObject:@7 forKey:@7];
+  map = [map dictionaryBySettingObject:@9 forKey:@9];
+
+  XCTAssertTrue(map.count == 6, @"Check if all 6 objects are in the map");
+  XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+  XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth],
+                @"Checking valid depth and tree structure");
+
+  FSTTreeSortedDictionary *m2 = map;
+  m2 = [m2 dictionaryBySettingObject:@20 forKey:@20];
+  m2 = [m2 dictionaryBySettingObject:@18 forKey:@18];
+  m2 = [m2 dictionaryBySettingObject:@2 forKey:@2];
+
+  XCTAssertTrue(m2.count == 9, @"Check if all 9 objects are in the map");
+  XCTAssertTrue([m2.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+  XCTAssertTrue([(FSTLLRBValueNode *)m2.root checkMaxDepth],
+                @"Checking valid depth and tree structure");
+
+  FSTTreeSortedDictionary *m3 = m2;
+  m3 = [m3 dictionaryBySettingObject:@71 forKey:@71];
+  m3 = [m3 dictionaryBySettingObject:@42 forKey:@42];
+  m3 = [m3 dictionaryBySettingObject:@88 forKey:@88];
+  m3 = [m3 dictionaryBySettingObject:@20 forKey:@20];  // Add a dupe to see if the size is correct
+
+  XCTAssertTrue(m3.count == 12, @"Check if all 12 (minus dupe @20) objects are in the map");
+  XCTAssertTrue([m3.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+  XCTAssertTrue([(FSTLLRBValueNode *)m3.root checkMaxDepth],
+                @"Checking valid depth and tree structure");
+}
+
+- (void)testOverride {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@10 forKey:@10];
+  map = [map dictionaryBySettingObject:@8 forKey:@10];
+
+  XCTAssertEqualObjects([map objectForKey:@10], @8, @"Found first object");
+}
+- (void)testEmpty {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@10 forKey:@10];
+  map = [map dictionaryByRemovingObjectForKey:@10];
+
+  XCTAssertTrue([map isEmpty], @"Properly empty");
+}
+
+- (void)testEmptyGet {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  XCTAssertNil([map objectForKey:@"something"], @"Properly nil");
+}
+
+- (void)testEmptyCount {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  XCTAssertTrue([map count] == 0, @"Properly zero count");
+}
+
+- (void)testEmptyRemoval {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryByRemovingObjectForKey:@"something"];
+  XCTAssertTrue(map.count == 0, @"Properly zero count");
+}
+
+- (void)testReverseTraversal {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@5 forKey:@5];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@2 forKey:@2];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+
+  __block int next = 5;
+  [map enumerateKeysAndObjectsReverse:YES
+                           usingBlock:^(id key, id value, BOOL *stop) {
+                             XCTAssertEqualObjects(key, @(next), @"Properly equal");
+                             next = next - 1;
+                           }];
+}
+
+- (void)testInsertionAndRemovalOfAHundredItems {
+  NSUInteger n = 100;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+  NSMutableArray *toRemove = [NSMutableArray arrayWithCapacity:n];
+
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i)];
+    [toRemove addObject:@(i)];
+  }
+
+  [self shuffleArray:toInsert];
+  [self shuffleArray:toRemove];
+
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // add them to the dictionary
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+    XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+    XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth],
+                  @"Checking valid depth and tree structure");
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+
+  // check the order is correct
+  __block int next = 0;
+  [map enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+    XCTAssertEqualObjects(key, @(next), @"Correct key");
+    XCTAssertEqualObjects(value, @(next), @"Correct value");
+    next = next + 1;
+  }];
+  XCTAssertEqual(next, n, @"Check we traversed all of the items");
+
+  // remove them
+
+  for (NSUInteger i = 0; i < n; i++) {
+    if ([map.root isMemberOfClass:FSTLLRBValueNode.class]) {
+      XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+      XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth],
+                    @"Checking valid depth and tree structure");
+    }
+    map = [map dictionaryByRemovingObjectForKey:toRemove[i]];
+  }
+
+  XCTAssertEqual(map.count, 0, @"Check we removed all of the items");
+}
+
+- (void)shuffleArray:(NSMutableArray *)array {
+  NSUInteger count = array.count;
+  for (NSUInteger i = 0; i < count; i++) {
+    NSUInteger nElements = count - i;
+    NSUInteger n = (arc4random() % nElements) + i;
+    [array exchangeObjectAtIndex:i withObjectAtIndex:n];
+  }
+}
+
+- (void)testBalanceProblem {
+  NSArray *toInsert = @[ @1, @7, @8, @5, @2, @6, @4, @0, @3 ];
+
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // add them to the dictionary
+  for (NSUInteger i = 0; i < toInsert.count; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+    XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+    XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth],
+                  @"Checking valid depth and tree structure");
+  }
+  XCTAssertTrue(map.count == toInsert.count, @"Check if all N objects are in the map");
+
+  // check the order is correct
+  __block int next = 0;
+  [map enumerateKeysAndObjectsUsingBlock:^(id key, id value, BOOL *stop) {
+    XCTAssertEqualObjects(key, @(next), @"Correct key");
+    XCTAssertEqualObjects(value, @(next), @"Correct value");
+    next = next + 1;
+  }];
+  XCTAssertEqual((int)next, (int)toInsert.count, @"Check we traversed all of the items");
+
+  // removing one triggers the balance problem
+  map = [map dictionaryByRemovingObjectForKey:@5];
+
+  if ([map.root isMemberOfClass:FSTLLRBValueNode.class]) {
+    XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+    XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth],
+                  @"Checking valid depth and tree structure");
+  }
+}
+
+- (void)testPredecessorKey {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@50 forKey:@50];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+  map = [map dictionaryBySettingObject:@7 forKey:@7];
+  map = [map dictionaryBySettingObject:@9 forKey:@9];
+
+  XCTAssertNil([map predecessorKey:@1], @"First object doesn't have a predecessor");
+  XCTAssertEqualObjects([map predecessorKey:@3], @1, @"@1");
+  XCTAssertEqualObjects([map predecessorKey:@4], @3, @"@3");
+  XCTAssertEqualObjects([map predecessorKey:@7], @4, @"@4");
+  XCTAssertEqualObjects([map predecessorKey:@9], @7, @"@7");
+  XCTAssertEqualObjects([map predecessorKey:@50], @9, @"@9");
+  XCTAssertThrows([map predecessorKey:@777], @"Expect exception about nonexistent key");
+}
+
+// This is a macro instead of a method so that the failures show on the proper lines.
+#define ASSERT_ENUMERATOR(enumerator, start, end, step)                                   \
+  do {                                                                                    \
+    NSEnumerator *e = (enumerator);                                                       \
+    id next = nil;                                                                        \
+    for (NSUInteger i = (start); i != (end); i += (step)) {                               \
+      next = [e nextObject];                                                              \
+      XCTAssertNotNil(next, @"expected %lu. got nil.", (unsigned long)i);                 \
+      XCTAssertEqualObjects(next, @(i), "expected %lu. got %@.", (unsigned long)i, next); \
+    }                                                                                     \
+    next = [e nextObject];                                                                \
+    XCTAssertNil(next, @"expected nil. got %@.", next);                                   \
+  } while (0)
+
+- (void)testEnumerator {
+  NSUInteger n = 100;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+  NSMutableArray *toRemove = [NSMutableArray arrayWithCapacity:n];
+
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i)];
+    [toRemove addObject:@(i)];
+  }
+
+  [self shuffleArray:toInsert];
+  [self shuffleArray:toRemove];
+
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:self.defaultComparator];
+
+  // add them to the dictionary
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+    XCTAssertTrue([map.root isMemberOfClass:FSTLLRBValueNode.class], @"Root is a value node");
+    XCTAssertTrue([(FSTLLRBValueNode *)map.root checkMaxDepth],
+                  @"Checking valid depth and tree structure");
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+
+  ASSERT_ENUMERATOR([map keyEnumerator], 0, 100, 1);
+}
+
+- (void)testReverseEnumerator {
+  NSUInteger n = 20;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i)];
+  }
+
+  [self shuffleArray:toInsert];
+
+  FSTImmutableSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // Add them to the dictionary.
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+  XCTAssertTrue([map isKindOfClass:FSTTreeSortedDictionary.class],
+                @"Make sure we still have a tree backed dictionary");
+
+  ASSERT_ENUMERATOR([map reverseKeyEnumerator], n - 1, -1, -1);
+}
+
+- (void)testEnumeratorFrom {
+  // Create a dictionary with the even numbers in [2, 42).
+  NSUInteger n = 20;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i * 2 + 2)];
+  }
+  [self shuffleArray:toInsert];
+
+  FSTImmutableSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // Add them to the dictionary.
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+  XCTAssertTrue([map isKindOfClass:FSTTreeSortedDictionary.class],
+                @"Make sure we still have a tree backed dictionary");
+
+  // Test from before keys.
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0], 2, n * 2 + 2, 2);
+
+  // Test from after keys.
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100], 0, 0, 2);
+
+  // Test from key in map.
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@10], 10, n * 2 + 2, 2);
+
+  // Test from in between keys.
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@11], 12, n * 2 + 2, 2);
+}
+
+- (void)testEnumeratorFromTo {
+  // Create a dictionary with the even numbers in [2, 42).
+  NSUInteger n = 20;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i * 2 + 2)];
+  }
+  [self shuffleArray:toInsert];
+
+  FSTImmutableSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // Add them to the dictionary.
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+  XCTAssertTrue([map isKindOfClass:FSTTreeSortedDictionary.class],
+                @"Make sure we still have a tree backed dictionary");
+
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@1], 2, 2, 2);            // before to before
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@100], 2, n * 2 + 2, 2);  // before to after
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@6], 2, 6, 2);            // before to key in map
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@0 to:@7], 2, 8, 2);      // before to in between keys
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@0], 2, 2, 2);    // after to before
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@110], 2, 2, 2);  // after to after
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@6], 2, 2, 2);    // after to key in map
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@100 to:@7], 2, 2, 2);    // after to in between
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@0], 6, 6, 2);      // key in map to before
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@100], 6, n * 2 + 2, 2);  // key in map to after
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@10], 6, 10, 2);  // key in map to key in map
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@6 to:@11], 6, 12, 2);  // key in map to in between
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@0], 8, 8, 2);    // in between to before
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@100], 8, n * 2 + 2, 2);  // in between to after
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@10], 8, 10, 2);  // in between to key in map
+  ASSERT_ENUMERATOR([map keyEnumeratorFrom:@7 to:@13], 8, 14, 2);  // in between to in between
+}
+
+- (void)testReverseEnumeratorFrom {
+  NSUInteger n = 20;
+  NSMutableArray *toInsert = [NSMutableArray arrayWithCapacity:n];
+
+  for (int i = 0; i < n; i++) {
+    [toInsert addObject:@(i * 2 + 2)];
+  }
+
+  [self shuffleArray:toInsert];
+
+  FSTImmutableSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+
+  // add them to the dictionary
+  for (NSUInteger i = 0; i < n; i++) {
+    map = [map dictionaryBySettingObject:toInsert[i] forKey:toInsert[i]];
+  }
+  XCTAssertTrue(map.count == n, @"Check if all N objects are in the map");
+  XCTAssertTrue([map isKindOfClass:FSTTreeSortedDictionary.class],
+                @"Make sure we still have a tree backed dictionary");
+
+  // Test from before keys.
+  ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@0], 0, 0, -2);
+
+  // Test from after keys.
+  ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@100], n * 2, 0, -2);
+
+  // Test from key in map.
+  ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@10], 10, 0, -2);
+
+  // Test from in between keys.
+  ASSERT_ENUMERATOR([map reverseKeyEnumeratorFrom:@11], 10, 0, -2);
+}
+
+#undef ASSERT_ENUMERATOR
+
+- (void)testIndexOf {
+  FSTTreeSortedDictionary *map =
+      [[FSTTreeSortedDictionary alloc] initWithComparator:[self defaultComparator]];
+  map = [map dictionaryBySettingObject:@1 forKey:@1];
+  map = [map dictionaryBySettingObject:@50 forKey:@50];
+  map = [map dictionaryBySettingObject:@3 forKey:@3];
+  map = [map dictionaryBySettingObject:@4 forKey:@4];
+  map = [map dictionaryBySettingObject:@7 forKey:@7];
+  map = [map dictionaryBySettingObject:@9 forKey:@9];
+
+  XCTAssertEqual([map indexOfKey:@0], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@1], 0);
+  XCTAssertEqual([map indexOfKey:@2], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@3], 1);
+  XCTAssertEqual([map indexOfKey:@4], 2);
+  XCTAssertEqual([map indexOfKey:@5], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@6], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@7], 3);
+  XCTAssertEqual([map indexOfKey:@8], NSNotFound);
+  XCTAssertEqual([map indexOfKey:@9], 4);
+  XCTAssertEqual([map indexOfKey:@50], 5);
+}
+
+@end