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

class PartialAccountsTree extends SynchronousAccountsTree {
    /**
     * @private
     * @param {SynchronousAccountsTreeStore} store
     */
    constructor(store) {
        super(store);
        this._complete = false;
        /** @type {string} */
        this._lastPrefix = '';
    }

    /**
     * @param {AccountsTreeChunk} chunk
     * @returns {Promise.<PartialAccountsTree.Status>}
     */
    async pushChunk(chunk) {
        // First verify the proof.
        if (!chunk.verify()) {
            return PartialAccountsTree.Status.ERR_INCORRECT_PROOF;
        }

        const tx = this.synchronousTransaction();

        // Then apply all
        tx._putLight(chunk.terminalNodes);

        // Check if proof can be merged.
        if (!tx._mergeProof(chunk.proof, chunk.tail.prefix)) {
            await tx.abort();
            return PartialAccountsTree.Status.ERR_UNMERGEABLE;
        }
        this._complete = tx.complete;

        // Now, we can put all nodes into the store.
        await tx.commit();

        // Update last prefix.
        this._lastPrefix = chunk.tail.prefix;

        // And return OK code depending on internal state.
        return this._complete ? PartialAccountsTree.Status.OK_COMPLETE : PartialAccountsTree.Status.OK_UNFINISHED;
    }

    /**
     * @param {AccountsProof} proof
     * @param {string} upperBound
     * @returns {boolean}
     * @private
     */
    _mergeProof(proof, upperBound) {
        // Retrieve rightmost path of the in-memory tree.
        let node = this._store.getRootNodeSync();
        let nodeChildren = node.getChildren();
        let complete = true;

        // Iterate over the proof and check for consistency.
        let j = proof.length - 1;
        for (; j > 0; --j) {
            const proofNode = proof.nodes[j];
            // The node's prefix might be shorter than the proof node's prefix if it is a newly
            // introduces node in the proof.
            if (StringUtils.commonPrefix(node.prefix, proofNode.prefix) !== node.prefix) {
                return false;
            }

            const proofChildren = proofNode.getChildren();

            // The tree node may not have more children than the proof node.
            if (nodeChildren.length > proofChildren.length) {
                return false;
            }

            // The nextChild we descend to.
            const nextChild = node.getLastChild();
            let insertedNode = false;

            // There are three cases:
            // 1) the child is in our inner tree (so between lower and upper bound), then the hashes must coincide.
            // 2) the child is left of our chunk, so it must be in the store.
            // 3) the child is right of our chunk, so it is a dangling reference.
            let i = 0;
            for (const proofChild of proofChildren) {
                const upperBoundPrefix = upperBound.substr(0, proofChild.length);
                if (proofChild <= upperBoundPrefix) {
                    // An inner node.
                    const child = nodeChildren.shift();

                    // This is the next child.
                    if (StringUtils.commonPrefix(nextChild, proofChild) === proofChild) {
                        // If it is a real prefix of the next child, we have inserted a new node.
                        if (proofChild !== nextChild) {
                            insertedNode = true;
                        }
                        continue;
                    }

                    if (child !== proofChild) {
                        return false;
                    }
                    // The child is equal and not the next child, so the hash must coincide.
                    const nodeHash = node.getChildHash(child);
                    const proofHash = proofNode.getChildHash(child);
                    if (!nodeHash || !proofHash || !nodeHash.equals(proofHash)) {
                        return false;
                    }
                } else {
                    // The others may be dangling references.
                    break;
                }
                ++i;
            }

            // We must have consumed all children!
            if (nodeChildren.length !== 0) {
                return false;
            }

            // If not all of the proof children have been tested, we are definitely incomplete.
            complete = complete && (i === proofChildren.length - 1);

            // If the prefix was the same, we can move on.
            if (insertedNode) {
                nodeChildren = [nextChild];
            } else {
                // We should never end here with a terminal node.
                if (node.isTerminal()) {
                    return false;
                }
                node = this._store.getSync(node.getLastChild());
                nodeChildren = node.getChildren();
                if (node.isTerminal()) {
                    break;
                }
            }
        }

        // Check the terminal nodes.
        if (!node.equals(proof.nodes[0])) {
            return false;
        }

        this._complete = complete;
        return true;
    }

    /**
     * @param {Array.<AccountsTreeNode>} nodes
     * @private
     */
    _putLight(nodes) {
        Assert.that(nodes.every(node => node.isTerminal()), 'Can only build tree from terminal nodes');

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

        // TODO: Bulk insertion instead of sequential insertion!
        for (const node of nodes) {
            this._insertBatch(rootNode, node.prefix, node.account, []);
            rootNode = this._store.getRootNodeSync();
            Assert.that(!!rootNode, 'Corrupted store: Failed to fetch AccountsTree root node');
        }
        this._updateHashes(rootNode);
    }

    /** @type {boolean} */
    get complete() {
        return this._complete;
    }

    /** @type {string} */
    get missingPrefix() {
        return this._lastPrefix;
    }

    /**
     * @param {boolean} [enableWatchdog]
     * @returns {PartialAccountsTree}
     */
    synchronousTransaction(enableWatchdog = true) {
        const tree = new PartialAccountsTree(this._store.synchronousTransaction(enableWatchdog));
        tree._complete = this._complete;
        tree._lastPrefix = this._lastPrefix;
        return tree;
    }

    /**
     * @param {boolean} [enableWatchdog]
     * @returns {AccountsTree}
     */
    transaction(enableWatchdog = true) {
        if (!this.complete) {
            throw new Error('Can only construct AccountsTree from complete PartialAccountsTree');
        }
        // Use a synchronous transaction here to enable better caching.
        return new AccountsTree(this._store.synchronousTransaction(enableWatchdog));
    }

    /**
     * @returns {Promise.<boolean>}
     */
    commit() {
        return this._store.commit();
    }

    /**
     * @returns {Promise}
     */
    abort() {
        return this._store.abort();
    }
}

/**
 * @enum {number}
 */
PartialAccountsTree.Status = {
    ERR_HASH_MISMATCH: -3,
    ERR_INCORRECT_PROOF: -2,
    ERR_UNMERGEABLE: -1,
    OK_COMPLETE: 0,
    OK_UNFINISHED: 1
};
Class.register(PartialAccountsTree);