firebase-ios-sdk/Firebase/Database/Core/FCompoundHash.m

/*
 * Copyright 2017 Google
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#import "FCompoundHash.h"
#import "FChildrenNode.h"
#import "FLeafNode.h"
#import "FSnapshotUtilities.h"
#import "FStringUtilities.h"

@interface FCompoundHashBuilder ()

@property(nonatomic, strong) FCompoundHashSplitStrategy splitStrategy;

@property(nonatomic, strong) NSMutableArray *currentPaths;
@property(nonatomic, strong) NSMutableArray *currentHashes;

@end

@implementation FCompoundHashBuilder {

    // NOTE: We use the existence of this to know if we've started building a
    // range (i.e. encountered a leaf node).
    NSMutableString *optHashValueBuilder;

    // The current path as a stack. This is used in combination with
    // currentPathDepth to simultaneously store the last leaf node path. The
    // depth is changed when descending and ascending, at the same time the
    // current key is set for the current depth. Because the keys are left
    // unchanged for ascending the path will also contain the path of the last
    // visited leaf node (using lastLeafDepth elements)
    NSMutableArray *currentPath;
    NSInteger lastLeafDepth;
    NSInteger currentPathDepth;

    BOOL needsComma;
}

- (instancetype)initWithSplitStrategy:(FCompoundHashSplitStrategy)strategy {
    self = [super init];
    if (self != nil) {
        self->_splitStrategy = strategy;
        self->optHashValueBuilder = nil;
        self->currentPath = [NSMutableArray array];
        self->lastLeafDepth = -1;
        self->currentPathDepth = 0;
        self->needsComma = YES;
        self->_currentPaths = [NSMutableArray array];
        self->_currentHashes = [NSMutableArray array];
    }
    return self;
}

- (BOOL)isBuildingRange {
    return self->optHashValueBuilder != nil;
}

- (NSUInteger)currentHashLength {
    return self->optHashValueBuilder.length;
}

- (FPath *)currentPath {
    return [self currentPathWithDepth:self->currentPathDepth];
}

- (FPath *)currentPathWithDepth:(NSInteger)depth {
    NSArray *pieces =
        [self->currentPath subarrayWithRange:NSMakeRange(0, depth)];
    return [[FPath alloc] initWithPieces:pieces andPieceNum:0];
}

- (void)enumerateCurrentPathToDepth:(NSInteger)depth
                          withBlock:(void (^)(NSString *key))block {
    for (NSInteger i = 0; i < depth; i++) {
        block(self->currentPath[i]);
    }
}

- (void)appendKey:(NSString *)key toString:(NSMutableString *)string {
    [FSnapshotUtilities appendHashV2RepresentationForString:key
                                                   toString:string];
}

- (void)ensureRange {
    if (![self isBuildingRange]) {
        optHashValueBuilder = [NSMutableString string];
        [optHashValueBuilder appendString:@"("];
        [self
            enumerateCurrentPathToDepth:self->currentPathDepth
                              withBlock:^(NSString *key) {
                                [self appendKey:key
                                       toString:self->optHashValueBuilder];
                                [self->optHashValueBuilder appendString:@":("];
                              }];
        self->needsComma = NO;
    }
}

- (void)processLeaf:(FLeafNode *)leafNode {
    [self ensureRange];

    self->lastLeafDepth = self->currentPathDepth;
    [FSnapshotUtilities
        appendHashRepresentationForLeafNode:leafNode
                                   toString:self->optHashValueBuilder
                                hashVersion:FDataHashVersionV2];
    self->needsComma = YES;
    if (self.splitStrategy(self)) {
        [self endRange];
    }
}

- (void)startChild:(NSString *)key {
    [self ensureRange];

    if (self->needsComma) {
        [self->optHashValueBuilder appendString:@","];
    }
    [self appendKey:key toString:self->optHashValueBuilder];
    [self->optHashValueBuilder appendString:@":("];
    if (self->currentPathDepth == currentPath.count) {
        [self->currentPath addObject:key];
    } else {
        self->currentPath[self->currentPathDepth] = key;
    }
    self->currentPathDepth++;
    self->needsComma = NO;
}

- (void)endChild {
    self->currentPathDepth--;
    if ([self isBuildingRange]) {
        [self->optHashValueBuilder appendString:@")"];
    }
    self->needsComma = YES;
}

- (void)finishHashing {
    NSAssert(self->currentPathDepth == 0,
             @"Can't finish hashing in the middle of processing a child");
    if ([self isBuildingRange]) {
        [self endRange];
    }

    // Always close with the empty hash for the remaining range to allow simple
    // appending
    [self.currentHashes addObject:@""];
}

- (void)endRange {
    NSAssert([self isBuildingRange],
             @"Can't end range without starting a range!");
    // Add closing parenthesis for current depth
    for (NSUInteger i = 0; i < currentPathDepth; i++) {
        [self->optHashValueBuilder appendString:@")"];
    }
    [self->optHashValueBuilder appendString:@")"];

    FPath *lastLeafPath = [self currentPathWithDepth:self->lastLeafDepth];
    NSString *hash =
        [FStringUtilities base64EncodedSha1:self->optHashValueBuilder];
    [self.currentHashes addObject:hash];
    [self.currentPaths addObject:lastLeafPath];

    self->optHashValueBuilder = nil;
}

@end

@interface FCompoundHash ()

@property(nonatomic, strong, readwrite) NSArray *posts;
@property(nonatomic, strong, readwrite) NSArray *hashes;

@end

@implementation FCompoundHash

- (id)initWithPosts:(NSArray *)posts hashes:(NSArray *)hashes {
    self = [super init];
    if (self != nil) {
        if (posts.count != hashes.count - 1) {
            [NSException raise:NSInvalidArgumentException
                        format:@"Number of posts need to be n-1 for n hashes "
                               @"in FCompoundHash"];
        }
        self.posts = posts;
        self.hashes = hashes;
    }
    return self;
}

+ (FCompoundHashSplitStrategy)simpleSizeSplitStrategyForNode:(id<FNode>)node {
    NSUInteger estimatedSize =
        [FSnapshotUtilities estimateSerializedNodeSize:node];

    // Splits for
    // 1k -> 512 (2 parts)
    // 5k -> 715 (7 parts)
    // 100k -> 3.2k (32 parts)
    // 500k -> 7k (71 parts)
    // 5M -> 23k (228 parts)
    NSUInteger splitThreshold = MAX(512, (NSUInteger)sqrt(estimatedSize * 100));

    return ^BOOL(FCompoundHashBuilder *builder) {
      // Never split on priorities
      return [builder currentHashLength] > splitThreshold &&
             ![[[builder currentPath] getBack] isEqualToString:@".priority"];
    };
}

+ (FCompoundHash *)fromNode:(id<FNode>)node {
    return [FCompoundHash
             fromNode:node
        splitStrategy:[FCompoundHash simpleSizeSplitStrategyForNode:node]];
}

+ (FCompoundHash *)fromNode:(id<FNode>)node
              splitStrategy:(FCompoundHashSplitStrategy)strategy {
    if ([node isEmpty]) {
        return [[FCompoundHash alloc] initWithPosts:@[] hashes:@[ @"" ]];
    } else {
        FCompoundHashBuilder *builder =
            [[FCompoundHashBuilder alloc] initWithSplitStrategy:strategy];
        [FCompoundHash processNode:node builder:builder];
        [builder finishHashing];
        return [[FCompoundHash alloc] initWithPosts:builder.currentPaths
                                             hashes:builder.currentHashes];
    }
}

+ (void)processNode:(id<FNode>)node builder:(FCompoundHashBuilder *)builder {
    if ([node isLeafNode]) {
        [builder processLeaf:node];
    } else {
        NSAssert(![node isEmpty], @"Can't calculate hash on empty node!");
        FChildrenNode *childrenNode = (FChildrenNode *)node;
        [childrenNode enumerateChildrenAndPriorityUsingBlock:^(
                          NSString *key, id<FNode> node, BOOL *stop) {
          [builder startChild:key];
          [self processNode:node builder:builder];
          [builder endChild];
        }];
    }
}

@end