Home Reference Source Test

src/main/generic/consensus/base/account/tree/SynchronousAccountsTree.js

class SynchronousAccountsTree extends AccountsTree {
    /**
     * @private
     * @param {SynchronousAccountsTreeStore} store
     * @returns {SynchronousAccountsTree}
     */
    constructor(store) {
        super(store);
        /** @type {SynchronousAccountsTreeStore} */
        this._syncStore = store;
    }

    /**
     * @param {Array.<Address>} addresses
     * @returns {Promise}
     */
    async preloadAddresses(addresses) {
        const rootNode = await this._syncStore.getRootNode();
        Assert.that(!!rootNode, 'Corrupted store: Failed to fetch AccountsTree root node');

        const prefixes = [];
        for (const address of addresses) {
            prefixes.push(address.toHex());
        }
        // We sort the addresses to simplify traversal in post order (leftmost addresses first).
        prefixes.sort();

        await this._preloadAddresses(rootNode, prefixes);
    }

    /**
     * @param {AccountsTreeNode} node
     * @param {Array.<string>} prefixes
     * @private
     */
    async _preloadAddresses(node, prefixes) {
        if (node.hasChildren()) {
            await this._syncStore.preload(node.getChildren());
        }
        
        // For each prefix, descend the tree individually.
        for (let i = 0; i < prefixes.length; ) {
            const prefix = prefixes[i];

            // Find common prefix between node and the current requested prefix.
            const commonPrefix = StringUtils.commonPrefix(node.prefix, prefix);

            // If the prefix fully matches, we have found the requested node.
            // If the prefix does not fully match, the requested address is not part of this node.
            // Include the node in the proof nevertheless to prove that the account doesn't exist.
            if (commonPrefix.length !== node.prefix.length || node.prefix === prefix) {
                i++;
                continue;
            }

            // Descend into the matching child node if one exists.
            const childKey = node.getChild(prefix);
            if (childKey) {
                const childNode = this._syncStore.getSync(childKey);

                // Group addresses with same prefix:
                // Because of our ordering, they have to be located next to the current prefix.
                // Hence, we iterate over the next prefixes, until we don't find commonalities anymore.
                // In the next main iteration we can skip those we already requested here.
                const subPrefixes = [prefix];
                // Find other prefixes to descend into this tree as well.
                let j = i + 1;
                for (; j < prefixes.length; ++j) {
                    // Since we ordered prefixes, there can't be any other prefixes with commonalities.
                    if (!prefixes[j].startsWith(childNode.prefix)) break;
                    // But if there is a commonality, add it to the list.
                    subPrefixes.push(prefixes[j]);
                }
                // Now j is the last index which doesn't have commonalities,
                // we continue from there in the next iteration.
                i = j;

                await this._preloadAddresses(childNode, subPrefixes); // eslint-disable-line no-await-in-loop
            }
            // No child node exists with the requested prefix. Include the current node to prove the absence of the requested account.
            else {
                i++;
            }
        }
    }

    /**
     * @param {Address} address
     * @param {Account} account
     */
    putSync(address, account) {
        this.putBatch(address, account);
        this.finalizeBatch();
    }

    finalizeBatch() {
        const rootNode = this._syncStore.getRootNodeSync();
        this._updateHashes(rootNode);
    }

    /**
     * @param {Address} address
     * @param {Account} account
     * @private
     */
    putBatch(address, account) {
        if (account.isInitial() && !this.getSync(address, false)) {
            return;
        }

        // Fetch the root node.
        const rootNode = this._syncStore.getRootNodeSync();
        Assert.that(!!rootNode, 'Corrupted store: Failed to fetch AccountsTree root node');

        // Insert account into the tree at address.
        const prefix = address.toHex();
        this._insertBatch(rootNode, prefix, account, []);
    }

    /**
     * @param {AccountsTreeNode} node
     * @param {string} prefix
     * @param {Account} account
     * @param {Array.<AccountsTreeNode>} rootPath
     * @protected
     */
    _insertBatch(node, prefix, account, rootPath) {
        // Find common prefix between node and new address.
        const commonPrefix = StringUtils.commonPrefix(node.prefix, prefix);

        // If the node prefix does not fully match the new address, split the node.
        if (commonPrefix.length !== node.prefix.length) {
            // Insert the new account node.
            const newChild = AccountsTreeNode.terminalNode(prefix, account);
            this._syncStore.putSync(newChild);

            // Insert the new parent node.
            const newParent = AccountsTreeNode.branchNode(commonPrefix)
                .withChild(node.prefix, new Hash(null))
                .withChild(newChild.prefix, new Hash(null));
            this._syncStore.putSync(newParent);

            return this._updateKeysBatch(newParent.prefix, rootPath);
        }

        // If the commonPrefix is the specified address, we have found an (existing) node
        // with the given address. Update the account.
        if (commonPrefix === prefix) {
            // XXX How does this generalize to more than one account type?
            // Special case: If the new balance is the initial balance
            // (i.e. balance=0, nonce=0), it is like the account never existed
            // in the first place. Delete the node in this case.
            if (account.isInitial()) {
                this._syncStore.removeSync(node);
                // We have already deleted the node, remove the subtree it was on.
                return this._pruneBatch(node.prefix, rootPath);
            }

            // Update the account.
            node = node.withAccount(account);
            this._syncStore.putSync(node);

            return this._updateKeysBatch(node.prefix, rootPath);
        }

        // If the node prefix matches and there are address bytes left, descend into
        // the matching child node if one exists.
        const childPrefix = node.getChild(prefix);
        if (childPrefix) {
            const childNode = this._syncStore.getSync(childPrefix);
            rootPath.push(node);
            return this._insertBatch(childNode, prefix, account, rootPath);
        }

        // If no matching child exists, add a new child account node to the current node.
        const newChild = AccountsTreeNode.terminalNode(prefix, account);
        this._syncStore.putSync(newChild);

        node = node.withChild(newChild.prefix, new Hash(null));
        this._syncStore.putSync(node);

        return this._updateKeysBatch(node.prefix, rootPath);
    }

    /**
     * @param {string} prefix
     * @param {Array.<AccountsTreeNode>} rootPath
     * @private
     */
    _pruneBatch(prefix, rootPath) {
        // Walk along the rootPath towards the root node starting with the
        // immediate predecessor of the node specified by 'prefix'.
        let i = rootPath.length - 1;
        for (; i >= 0; --i) {
            let node = rootPath[i];

            node = node.withoutChild(prefix);

            // If the node has only a single child, merge it with the next node.
            if (node.hasSingleChild() && node.prefix !== '') {
                this._syncStore.removeSync(node);

                const childPrefix = node.getFirstChild();
                const childNode = this._syncStore.getSync(childPrefix);

                this._syncStore.putSync(childNode);
                return this._updateKeysBatch(childNode.prefix, rootPath.slice(0, i));
            }
            // Otherwise, if the node has children left, update it and all keys on the
            // remaining root path. Pruning finished.
            // XXX Special case: We start with an empty root node. Don't delete it.
            else if (node.hasChildren() || node.prefix === '') {
                this._syncStore.putSync(node);
                return this._updateKeysBatch(node.prefix, rootPath.slice(0, i));
            }

            // The node has no children left, continue pruning.
            prefix = node.prefix;
        }

        // XXX This should never be reached.
        return undefined;
    }

    /**
     * @param {string} prefix
     * @param {Array.<AccountsTreeNode>} rootPath
     * @private
     */
    _updateKeysBatch(prefix, rootPath) {
        // Walk along the rootPath towards the root node starting with the
        // immediate predecessor of the node specified by 'prefix'.
        let i = rootPath.length - 1;
        for (; i >= 0; --i) {
            let node = rootPath[i];

            node = node.withChild(prefix, new Hash(null));
            this._syncStore.putSync(node);
            prefix = node.prefix;
        }
    }

    /**
     * This method updates all empty hashes (and only such).
     * @param {AccountsTreeNode} node
     * @protected
     */
    _updateHashes(node) {
        if (node.isTerminal()) {
            return node.hash();
        }

        const zeroHash = new Hash(null);
        // Compute sub hashes if necessary.
        const subHashes = node.getChildren().map(child => {
            const currentHash = node.getChildHash(child);
            if (!currentHash.equals(zeroHash)) {
                return currentHash;
            }
            const childNode = this._syncStore.getSync(child);
            return this._updateHashes(childNode);
        });

        // Then prepare new node and update.
        let newNode = node;
        node.getChildren().forEach((child, i) => {
            newNode = newNode.withChild(child, subHashes[i]);
        });
        this._syncStore.putSync(newNode);
        return newNode.hash();
    }

    /**
     * @param {Address} address
     * @param {boolean} [expectedToBePresent]
     * @returns {?Account}
     */
    getSync(address, expectedToBePresent = true) {
        const node = this._syncStore.getSync(address.toHex(), expectedToBePresent);
        return node !== undefined ? node.account : null;
    }

    /**
     * @returns {Hash}
     */
    rootSync() {
        const rootNode = this._syncStore.getRootNodeSync();
        return rootNode && rootNode.hash();
    }
}
Class.register(SynchronousAccountsTree);