/*
 * Copyright (C) 2011 Google Inc. All rights reserved.
 * Copyright (C) 2016 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

// nodes
// [<0:id>, <1:size>, <2:classNameTableIndex>, <3:flags>, <4:labelIndex>, <5:address>, <6:wrapped address>]
const nodeFieldCount = 7;
const nodeIdOffset = 0;
const nodeSizeOffset = 1;
const nodeClassNameOffset = 2;
const nodeFlagsOffset = 3;
const nodeLabelOffset = 4;
const nodeAddressOffset = 5;
const nodeWrappedAddressOffset = 6;

// node flags
const internalFlagsMask = (1 << 0);
const objectTypeMask = (1 << 1);

// edges
// [<0:fromId>, <1:toId>, <2:typeTableIndex>, <3:edgeDataIndexOrEdgeNameIndex>]
const edgeFieldCount = 4;
const edgeFromIdOffset = 0;
const edgeToIdOffset = 1;
const edgeTypeOffset = 2;
const edgeDataOffset = 3;

// roots
// [<0:id>, <1:labelIndex>]
let rootFieldCount = 3;
const rootIdOffset = 0;
const rootLabelOffset = 1;
const reachabilityReasonOffset = 2;

// Other constants.
const rootNodeIndex = 0;
const rootNodeOrdinal = 0;
const rootNodeIdentifier = 0;

// Terminology:
//   - `nodeIndex` is an index into the `nodes` list.
//   - `nodeOrdinal` is the order of the node in the `nodes` list. (nodeIndex / nodeFieldCount).
//   - `nodeIdentifier` is the node's id value. (nodes[nodeIndex + nodeIdOffset]).
//   - `edgeIndex` is an index into the `edges` list.
//
// Lists:
//   - _nodeOrdinalToFirstOutgoingEdge - `nodeOrdinal` to `edgeIndex` in `edges`.
//     Iterate edges by walking `edges` (edgeFieldCount) and checking if fromIdentifier is current.
//   - _nodeOrdinalToFirstIncomingEdge - `nodeOrdinal` to `incomingEdgeIndex` in `incomingEdges`.
//     Iterate edges by walking `incomingEdges` until `nodeOrdinal+1`'s first incoming edge index.
//   - _nodeOrdinalToDominatorNodeOrdinal - `nodeOrdinal` to `nodeOrdinal` of dominator.
//   - _nodeOrdinalToRetainedSizes - `nodeOrdinal` to retain size value.
//   - _nodeOrdinalIsDead - `nodeOrdinal` is dead or alive.
//
// Temporary Lists:
//   - nodeOrdinalToPostOrderIndex - `nodeOrdinal` to a `postOrderIndex`.
//   - postOrderIndexToNodeOrdinal - `postOrderIndex` to a `nodeOrdinal`.

let nextSnapshotIdentifier = 1;

HeapSnapshot = class HeapSnapshot
{
    constructor(objectId, snapshotDataString, title = null)
    {
        this._identifier = nextSnapshotIdentifier++;
        this._objectId = objectId;
        this._title = title;

        let json = JSON.parse(snapshotDataString);
        snapshotDataString = null;

        let {version, type, nodes, nodeClassNames, edges, edgeTypes, edgeNames, roots, labels} = json;
        console.assert(version === 1 || version === 2, "Expect JavaScriptCore Heap Snapshot version 1 or 2");
        console.assert(type === "GCDebugging", "Expect a GCDebugging-type snapshot");

        this._nodes = nodes;
        this._nodeCount = nodes.length / nodeFieldCount;

        this._roots = roots;
        this._rootCount = roots.length / rootFieldCount;

        this._edges = edges;
        this._edgeCount = edges.length / edgeFieldCount;

        this._edgeTypesTable = edgeTypes;
        this._edgeNamesTable = edgeNames;
        this._nodeClassNamesTable = nodeClassNames;
        this._labelsTable = labels;

        this._totalSize = 0;
        this._nodeIdentifierToOrdinal = new Map; // <node identifier> => nodeOrdinal
        this._lastNodeIdentifier = 0;
        for (let nodeIndex = 0; nodeIndex < nodes.length; nodeIndex += nodeFieldCount) {
            let nodeOrdinal = nodeIndex / nodeFieldCount;
            let nodeIdentifier = nodes[nodeIndex + nodeIdOffset];
            this._nodeIdentifierToOrdinal.set(nodeIdentifier, nodeOrdinal);
            this._totalSize += nodes[nodeIndex + nodeSizeOffset];
            if (nodeIdentifier > this._lastNodeIdentifier)
                this._lastNodeIdentifier = nodeIdentifier;
        }

        this._rootIdentifierToReasons = new Map; // <node identifier> => Set of root reasons
        for (let rootIndex = 0; rootIndex < roots.length; rootIndex += rootFieldCount) {
            let rootOrdinal = rootIndex / rootFieldCount;
            let rootIdentifier = roots[rootIndex + rootIdOffset];
            let rootReasonIndex = roots[rootIndex + rootLabelOffset];
            let rootReachabilityIndex = roots[rootIndex + reachabilityReasonOffset];

            let existingReasons = this._rootIdentifierToReasons.get(rootIdentifier);
            if (existingReasons) {
                existingReasons.add(rootReasonIndex);
                existingReasons.add(rootReachabilityIndex);
            } else
                this._rootIdentifierToReasons.set(rootIdentifier, new Set([rootReasonIndex, rootReachabilityIndex]));
        }

        // FIXME: Replace toIdentifier and fromIdentifier in edges with nodeIndex to reduce hash lookups?

        this._nodeOrdinalToFirstOutgoingEdge = new Uint32Array(this._nodeCount); // nodeOrdinal => edgeIndex
        this._buildOutgoingEdges();

        this._nodeOrdinalToFirstIncomingEdge = new Uint32Array(this._nodeCount + 1); // nodeOrdinal => incomingNodes/incomingEdges index
        this._incomingNodes = new Uint32Array(this._edgeCount); // from nodeOrdinals.
        this._incomingEdges = new Uint32Array(this._edgeCount); // edgeIndex.
        this._buildIncomingEdges();

        let {nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal} = this._buildPostOrderIndexes();

        this._nodeOrdinalToDominatorNodeOrdinal = new Uint32Array(this._nodeCount);
        this._nodeOrdinalIsGCRoot = new Uint8Array(this._nodeCount);
        this._buildDominatorIndexes(nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal);

        nodeOrdinalToPostOrderIndex = null;

        this._nodeOrdinalToRetainedSizes = new Uint32Array(this._nodeCount);
        this._buildRetainedSizes(postOrderIndexToNodeOrdinal);

        postOrderIndexToNodeOrdinal = null;

        this._nodeOrdinalIsDead = new Uint8Array(this._nodeCount);

        let {liveSize, categories} = HeapSnapshot.updateCategoriesAndMetadata(this);
        this._liveSize = liveSize;
        this._categories = categories;
    }

    get proxyObjectId() { return this._proxyObjectId; }
    get identifier() { return this._identifier; }
    get title() { return this._title; }
    get totalSize() { return this._totalSize; }
    get totalObjectCount() { return this._totalObjectCount; }
    get liveSize() { return this._liveSize; }
    get categories() { return this._categories; }
    get invalid() { return this._proxyObjectId === 0; }

    // Static

    static updateCategoriesAndMetadata(snapshot, allowNodeIdentifierCallback)
    {
        let liveSize = 0;
        let categories = {};

        let nodes = snapshot._nodes;
        let nodeClassNamesTable = snapshot._nodeClassNamesTable;
        let nodeOrdinalToRetainedSizes = snapshot._nodeOrdinalToRetainedSizes;
        let nodeOrdinalIsDead = snapshot._nodeOrdinalIsDead;

        // Skip the <root> node.
        let firstNodeIndex = nodeFieldCount;
        let firstNodeOrdinal = 1;
        for (let nodeIndex = firstNodeIndex, nodeOrdinal = firstNodeOrdinal; nodeIndex < nodes.length; nodeIndex += nodeFieldCount, nodeOrdinal++) {
            if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset]))
                continue;

            let classNameTableIndex = nodes[nodeIndex + nodeClassNameOffset];
            let className = nodeClassNamesTable[classNameTableIndex];
            let size = nodes[nodeIndex + nodeSizeOffset];
            let retainedSize = nodeOrdinalToRetainedSizes[nodeOrdinal];
            let flags = nodes[nodeIndex + nodeFlagsOffset];
            let dead = nodeOrdinalIsDead[nodeOrdinal] ? true : false;

            let category = categories[className];
            if (!category)
                category = categories[className] = {className, size: 0, retainedSize: 0, count: 0, internalCount: 0, deadCount: 0, objectCount: 0};

            category.size += size;
            category.retainedSize += retainedSize;
            category.count += 1;
            if (flags & internalFlagsMask)
                category.internalCount += 1;
            if (flags & objectTypeMask)
                category.objectCount += 1;
            if (dead)
                category.deadCount += 1;
            else
                liveSize += size;
        }

        return {liveSize, categories};
    }

    static allocationBucketCounts(snapshot, bucketSizes, allowNodeIdentifierCallback)
    {
        let counts = new Array(bucketSizes.length + 1);
        let remainderBucket = counts.length - 1;
        counts.fill(0);

        let nodes = snapshot._nodes;

        // Skip the <root> node.
        let firstNodeIndex = nodeFieldCount;

    outer:
        for (let nodeIndex = firstNodeIndex; nodeIndex < nodes.length; nodeIndex += nodeFieldCount) {
            if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset]))
                continue;

            let size = nodes[nodeIndex + nodeSizeOffset];
            for (let i = 0; i < bucketSizes.length; ++i) {
                if (size < bucketSizes[i]) {
                    counts[i]++;
                    continue outer;
                }
            }
            counts[remainderBucket]++;
        }

        return counts;
    }

    static instancesWithClassName(snapshot, className, allowNodeIdentifierCallback)
    {
        let instances = [];

        let nodes = snapshot._nodes;
        let nodeClassNamesTable = snapshot._nodeClassNamesTable;

        // Skip the <root> node.
        let firstNodeIndex = nodeFieldCount;
        let firstNodeOrdinal = 1;
        for (let nodeIndex = firstNodeIndex, nodeOrdinal = firstNodeOrdinal; nodeIndex < nodes.length; nodeIndex += nodeFieldCount, nodeOrdinal++) {
            if (allowNodeIdentifierCallback && !allowNodeIdentifierCallback(nodes[nodeIndex + nodeIdOffset]))
                continue;

            let classNameTableIndex = nodes[nodeIndex + nodeClassNameOffset];
            if (nodeClassNamesTable[classNameTableIndex] === className)
                instances.push(nodeIndex);
        }

        return instances.map(snapshot.serializeNode, snapshot);
    }

    // Worker Methods

    allocationBucketCounts(bucketSizes)
    {
        return HeapSnapshot.allocationBucketCounts(this, bucketSizes);
    }

    instancesWithClassName(className)
    {
        return HeapSnapshot.instancesWithClassName(this, className);
    }

    update()
    {
        return HeapSnapshot.updateCategoriesAndMetadata(this);
    }

    nodeWithIdentifier(nodeIdentifier)
    {
        let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
        let nodeIndex = nodeOrdinal * nodeFieldCount;
        return this.serializeNode(nodeIndex);
    }

    shortestGCRootPath(nodeIdentifier)
    {
        // Returns an array from this node to a gcRoot node.
        // E.g. [Node (target), Edge, Node, Edge, Node (root)].
        // Internal nodes are avoided, so if the path is empty this
        // node is either a gcRoot or only reachable via Internal nodes.

        let paths = this._gcRootPaths(nodeIdentifier);
        if (!paths.length)
            return [];

        paths.sort((a, b) => a.length - b.length);

        let shortestPathWithGlobalObject = null;
        for (let path of paths) {
            let lastNodeIndex = path[path.length - 1].node;
            if (this._isNodeGlobalObject(lastNodeIndex)) {
                shortestPathWithGlobalObject = path;
                break;
            }
        }

        let shortestPath = shortestPathWithGlobalObject || paths[0];
        console.assert("node" in shortestPath[0], "Path should start with a node");
        console.assert("node" in shortestPath[shortestPath.length - 1], "Path should end with a node");

        return shortestPath.map((component) => {
            if (component.node)
                return this.serializeNode(component.node);
            return this.serializeEdge(component.edge);
        });
    }
    
    rootNodes()
    {
        let rootNodeIndexSet = new Set;

        // Identifiers can occur multiple times in the roots list.
        for (let rootIndex = 0; rootIndex < this._roots.length; rootIndex += rootFieldCount) {
            let rootOrdinal = rootIndex / rootFieldCount;
            let rootIdentifier = this._roots[rootIndex + rootIdOffset];

            let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(rootIdentifier);
            let toNodeIndex = toNodeOrdinal * nodeFieldCount;

            rootNodeIndexSet.add(toNodeIndex);
        }

        return Array.from(rootNodeIndexSet.values()).map(this.serializeNode, this);
    }
    
    reasonNamesForRoot(rootIdentifier)
    {
        let reasonIndexes = this._rootIdentifierToReasons.get(rootIdentifier);
        if (!reasonIndexes)
            return [];
        return Array.from(reasonIndexes).map(this.labelForIndex, this).filter(a => a != 0)
    }

    dominatedNodes(nodeIdentifier)
    {
        let dominatedNodes = [];

        let targetNodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
        for (let nodeOrdinal = 0; nodeOrdinal < this._nodeCount; ++nodeOrdinal) {
            if (this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal] === targetNodeOrdinal)
                dominatedNodes.push(nodeOrdinal * nodeFieldCount);
        }

        return dominatedNodes.map(this.serializeNode, this);
    }

    retainedNodes(nodeIdentifier)
    {
        let retainedNodes = [];
        let edges = [];

        let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
        let edgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal];
        for (; this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier; edgeIndex += edgeFieldCount) {
            let toNodeIdentifier = this._edges[edgeIndex + edgeToIdOffset];
            let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toNodeIdentifier);
            let toNodeIndex = toNodeOrdinal * nodeFieldCount;
            retainedNodes.push(toNodeIndex);
            edges.push(edgeIndex);
        }

        return {
            retainedNodes: retainedNodes.map(this.serializeNode, this),
            edges: edges.map(this.serializeEdge, this),
        };
    }

    retainers(nodeIdentifier)
    {
        let retainers = [];
        let edges = [];

        let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
        let incomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal];
        let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1];
        for (let edgeIndex = incomingEdgeIndex; edgeIndex < incomingEdgeIndexEnd; ++edgeIndex) {
            let fromNodeOrdinal = this._incomingNodes[edgeIndex];
            let fromNodeIndex = fromNodeOrdinal * nodeFieldCount;
            retainers.push(fromNodeIndex);
            edges.push(this._incomingEdges[edgeIndex]);
        }

        return {
            retainers: retainers.map(this.serializeNode, this),
            edges: edges.map(this.serializeEdge, this),
        };
    }

    updateDeadNodesAndGatherCollectionData(snapshots)
    {
        let previousSnapshotIndex = snapshots.indexOf(this) - 1;
        let previousSnapshot = snapshots[previousSnapshotIndex];
        if (!previousSnapshot)
            return null;

        let lastNodeIdentifier = previousSnapshot._lastNodeIdentifier;

        // All of the node identifiers that could have existed prior to this snapshot.
        let known = new Map;
        for (let nodeIndex = 0; nodeIndex < this._nodes.length; nodeIndex += nodeFieldCount) {
            let nodeIdentifier = this._nodes[nodeIndex + nodeIdOffset];
            if (nodeIdentifier > lastNodeIdentifier)
                continue;
            known.set(nodeIdentifier, nodeIndex);
        }

        // Determine which node identifiers have since been deleted.
        let collectedNodesList = [];
        for (let nodeIndex = 0; nodeIndex < previousSnapshot._nodes.length; nodeIndex += nodeFieldCount) {
            let nodeIdentifier = previousSnapshot._nodes[nodeIndex + nodeIdOffset];
            let wasDeleted = !known.has(nodeIdentifier);
            if (wasDeleted)
                collectedNodesList.push(nodeIdentifier);
        }

        // Update dead nodes in previous snapshots.
        let affectedSnapshots = [];
        for (let snapshot of snapshots) {
            if (snapshot === this)
                break;
            if (snapshot._markDeadNodes(collectedNodesList))
                affectedSnapshots.push(snapshot._identifier);
        }

        // Convert list to a map.
        let collectedNodes = {};
        for (let i = 0; i < collectedNodesList.length; ++i)
            collectedNodes[collectedNodesList[i]] = true;

        return {
            collectedNodes,
            affectedSnapshots,
        };
    }

    // Public

    serialize()
    {
        return {
            identifier: this._identifier,
            title: this._title,
            totalSize: this._totalSize,
            totalObjectCount: this._nodeCount - 1, // <root>.
            liveSize: this._liveSize,
            categories: this._categories,
        };
    }

    serializeNode(nodeIndex)
    {
        console.assert((nodeIndex % nodeFieldCount) === 0, "Invalid nodeIndex to serialize: " + nodeIndex);

        let nodeIdentifier = this._nodes[nodeIndex + nodeIdOffset];
        let nodeOrdinal = nodeIndex / nodeFieldCount;
        let edgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal];
        let hasChildren = this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier;
        let nodeFlags = this._nodes[nodeIndex + nodeFlagsOffset];

        let dominatorNodeOrdinal = this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal];
        let dominatorNodeIndex = dominatorNodeOrdinal * nodeFieldCount;
        let dominatorNodeIdentifier = this._nodes[dominatorNodeIndex + nodeIdOffset];

        let result = {
            id: nodeIdentifier,
            className: this._nodeClassNamesTable[this._nodes[nodeIndex + nodeClassNameOffset]],
            size: this._nodes[nodeIndex + nodeSizeOffset],
            retainedSize: this._nodeOrdinalToRetainedSizes[nodeOrdinal],
            internal: nodeFlags & internalFlagsMask ? true : false,
            isObjectType: nodeFlags & objectTypeMask ? true : false,
            gcRoot: this._nodeOrdinalIsGCRoot[nodeOrdinal] ? true : false,
            markedRoot : this._rootIdentifierToReasons.has(nodeIdentifier),
            dead: this._nodeOrdinalIsDead[nodeOrdinal] ? true : false,
            address: this._nodes[nodeIndex + nodeAddressOffset],
            label: this._labelsTable[this._nodes[nodeIndex + nodeLabelOffset]],
            dominatorNodeIdentifier,
            hasChildren,
        };

        let wrappedAddr = this._nodes[nodeIndex + nodeWrappedAddressOffset];
        if (wrappedAddr !== "0x0")
            result.wrappedAddress = wrappedAddr;
        
        return result;
    }

    labelForIndex(index)
    {
        return this._labelsTable[index];
    }

    serializeEdge(edgeIndex)
    {
        console.assert((edgeIndex % edgeFieldCount) === 0, "Invalid edgeIndex to serialize");

        let edgeType = this._edgeTypesTable[this._edges[edgeIndex + edgeTypeOffset]];
        let edgeData = this._edges[edgeIndex + edgeDataOffset];
        switch (edgeType) {
        case "Internal":
            // edgeData can be ignored.
            break;
        case "Property":
        case "Variable":
            // edgeData is a table index.
            edgeData = this._edgeNamesTable[edgeData];
            break;
        case "Index":
            // edgeData is the index.
            break;
        default:
            console.error("Unexpected edge type: " + edgeType);
            break;
        }

        return {
            from: this._edges[edgeIndex + edgeFromIdOffset],
            to: this._edges[edgeIndex + edgeToIdOffset],
            type: edgeType,
            data: edgeData,
        };
    }

    // Private

    _buildOutgoingEdges()
    {
        let lastFromIdentifier = -1;
        for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) {
            let fromIdentifier = this._edges[edgeIndex + edgeFromIdOffset];
            console.assert(lastFromIdentifier <= fromIdentifier, "Edge list should be ordered by from node identifier");
            if (fromIdentifier !== lastFromIdentifier) {
                let nodeOrdinal = this._nodeIdentifierToOrdinal.get(fromIdentifier);
                this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal] = edgeIndex;
                lastFromIdentifier = fromIdentifier;
            }
        }
    }

    _buildIncomingEdges()
    {
        // First calculate the count of incoming edges for each node.
        for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) {
            let toIdentifier = this._edges[edgeIndex + edgeToIdOffset];
            let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier);
            this._nodeOrdinalToFirstIncomingEdge[toNodeOrdinal]++;
        }

        // Replace the counts with what will be the resulting index by running up the counts.
        // Store the counts in what will be the edges list to use when placing edges in the list.
        let runningFirstIndex = 0;
        for (let nodeOrdinal = 0; nodeOrdinal < this._nodeCount; ++nodeOrdinal) {
            let count = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal];
            this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal] = runningFirstIndex;
            this._incomingNodes[runningFirstIndex] = count;
            runningFirstIndex += count;
        }

        // Fill in the incoming edges list. Use the count as an offset when placing edges in the list.
        for (let edgeIndex = 0; edgeIndex < this._edges.length; edgeIndex += edgeFieldCount) {
            let fromIdentifier = this._edges[edgeIndex + edgeFromIdOffset];
            let fromNodeOrdinal = this._nodeIdentifierToOrdinal.get(fromIdentifier);
            let toIdentifier = this._edges[edgeIndex + edgeToIdOffset];
            let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier);

            let firstIncomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[toNodeOrdinal];
            console.assert(this._incomingNodes[firstIncomingEdgeIndex] > 0, "Should be expecting edges for this node");
            let countAsOffset = this._incomingNodes[firstIncomingEdgeIndex]--;
            let index = firstIncomingEdgeIndex + countAsOffset - 1;
            this._incomingNodes[index] = fromNodeOrdinal;
            this._incomingEdges[index] = edgeIndex;
        }

        // Duplicate value on the end. Incoming edge iteration walks firstIncomingEdge(ordinal) to firstIncomingEdge(ordinal+1).
        this._nodeOrdinalToFirstIncomingEdge[this._nodeCount] = this._nodeOrdinalToFirstIncomingEdge[this._nodeCount - 1];
    }

    _buildPostOrderIndexes()
    {
        let postOrderIndex = 0;
        let nodeOrdinalToPostOrderIndex = new Uint32Array(this._nodeCount);
        let postOrderIndexToNodeOrdinal = new Uint32Array(this._nodeCount);

        let stackNodes = new Uint32Array(this._nodeCount); // nodeOrdinal.
        let stackEdges = new Uint32Array(this._nodeCount); // edgeIndex.
        let visited = new Uint8Array(this._nodeCount);

        let stackTop = 0;
        stackNodes[stackTop] = rootNodeOrdinal;
        stackEdges[stackTop] = this._nodeOrdinalToFirstOutgoingEdge[rootNodeOrdinal];

        while (stackTop >= 0) {
            let nodeOrdinal = stackNodes[stackTop];
            let nodeIdentifier = this._nodes[(nodeOrdinal * nodeFieldCount) + nodeIdOffset];
            let edgeIndex = stackEdges[stackTop];

            if (this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier) {
                // Prepare the next child for the current node.
                stackEdges[stackTop] += edgeFieldCount;

                let toIdentifier = this._edges[edgeIndex + edgeToIdOffset];
                let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier);
                if (visited[toNodeOrdinal])
                    continue;

                // Child.
                stackTop++;
                stackNodes[stackTop] = toNodeOrdinal;
                stackEdges[stackTop] = this._nodeOrdinalToFirstOutgoingEdge[toNodeOrdinal];
                visited[toNodeOrdinal] = 1;
            } else {
                // Self.
                nodeOrdinalToPostOrderIndex[nodeOrdinal] = postOrderIndex;
                postOrderIndexToNodeOrdinal[postOrderIndex] = nodeOrdinal;
                postOrderIndex++;
                stackTop--;
            }
        }

        // Unvisited nodes.
        // This can happen if the parent node was disallowed on the backend, but other nodes
        // that were only referenced from that disallowed node were eventually allowed because
        // they may be generic system objects. Give these nodes a postOrderIndex anyways.
        if (postOrderIndex !== this._nodeCount) {
            // Root was the last node visited. Revert assigning it an index, add it back at the end.
            postOrderIndex--;

            // Visit unvisited nodes.
            for (let nodeOrdinal = 1; nodeOrdinal < this._nodeCount; ++nodeOrdinal) {
                if (visited[nodeOrdinal])
                    continue;
                nodeOrdinalToPostOrderIndex[nodeOrdinal] = postOrderIndex;
                postOrderIndexToNodeOrdinal[postOrderIndex] = nodeOrdinal;
                postOrderIndex++;
            }

            // Visit root again.
            nodeOrdinalToPostOrderIndex[rootNodeOrdinal] = postOrderIndex;
            postOrderIndexToNodeOrdinal[postOrderIndex] = rootNodeOrdinal;
            postOrderIndex++;
        }

        console.assert(postOrderIndex === this._nodeCount, "All nodes were visited");
        console.assert(nodeOrdinalToPostOrderIndex[rootNodeOrdinal] === this._nodeCount - 1, "Root node should have the last possible postOrderIndex");

        return {nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal};
    }

    _buildDominatorIndexes(nodeOrdinalToPostOrderIndex, postOrderIndexToNodeOrdinal)
    {
        // The algorithm is based on the article:
        // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"

        let rootPostOrderIndex = this._nodeCount - 1;
        let noEntry = this._nodeCount;

        let affected = new Uint8Array(this._nodeCount);
        let dominators = new Uint32Array(this._nodeCount);

        // Initialize with unset value.
        dominators.fill(noEntry);

        // Mark the root's dominator value.
        dominators[rootPostOrderIndex] = rootPostOrderIndex;

        // Affect the root's children. Also use this opportunity to mark them as GC roots.
        let rootEdgeIndex = this._nodeOrdinalToFirstOutgoingEdge[rootNodeOrdinal];
        for (let edgeIndex = rootEdgeIndex; this._edges[edgeIndex + edgeFromIdOffset] === rootNodeIdentifier; edgeIndex += edgeFieldCount) {
            let toIdentifier = this._edges[edgeIndex + edgeToIdOffset];
            let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toIdentifier);
            let toPostOrderIndex = nodeOrdinalToPostOrderIndex[toNodeOrdinal];
            affected[toPostOrderIndex] = 1;
            this._nodeOrdinalIsGCRoot[toNodeOrdinal] = 1;
        }

        let changed = true;
        while (changed) {
            changed = false;

            for (let postOrderIndex = rootPostOrderIndex - 1; postOrderIndex >= 0; --postOrderIndex) {
                if (!affected[postOrderIndex])
                    continue;
                affected[postOrderIndex] = 0;

                // The dominator is already the root, nothing to do.
                if (dominators[postOrderIndex] === rootPostOrderIndex)
                    continue;

                let newDominatorIndex = noEntry;
                let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex];
                let incomingEdgeIndex = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal];
                let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1];
                for (let edgeIndex = incomingEdgeIndex; edgeIndex < incomingEdgeIndexEnd; ++edgeIndex) {
                    let fromNodeOrdinal = this._incomingNodes[edgeIndex];
                    let fromPostOrderIndex = nodeOrdinalToPostOrderIndex[fromNodeOrdinal];
                    if (dominators[fromPostOrderIndex] !== noEntry) {
                        if (newDominatorIndex === noEntry)
                            newDominatorIndex = fromPostOrderIndex;
                        else {
                            while (fromPostOrderIndex !== newDominatorIndex) {
                                while (fromPostOrderIndex < newDominatorIndex)
                                    fromPostOrderIndex = dominators[fromPostOrderIndex];
                                while (newDominatorIndex < fromPostOrderIndex)
                                    newDominatorIndex = dominators[newDominatorIndex];
                            }
                        }
                    }
                    if (newDominatorIndex === rootPostOrderIndex)
                        break;
                }

                // Changed. Affect children.
                if (newDominatorIndex !== noEntry && dominators[postOrderIndex] !== newDominatorIndex) {
                    dominators[postOrderIndex] = newDominatorIndex;
                    changed = true;

                    let outgoingEdgeIndex = this._nodeOrdinalToFirstOutgoingEdge[nodeOrdinal];
                    let nodeIdentifier = this._nodes[(nodeOrdinal * nodeFieldCount) + nodeIdOffset];
                    for (let edgeIndex = outgoingEdgeIndex; this._edges[edgeIndex + edgeFromIdOffset] === nodeIdentifier; edgeIndex += edgeFieldCount) {
                        let toNodeIdentifier = this._edges[edgeIndex + edgeToIdOffset];
                        let toNodeOrdinal = this._nodeIdentifierToOrdinal.get(toNodeIdentifier);
                        let toNodePostOrder = nodeOrdinalToPostOrderIndex[toNodeOrdinal];
                        affected[toNodePostOrder] = 1;
                    }
                }
            }
        }

        for (let postOrderIndex = 0; postOrderIndex < this._nodeCount; ++postOrderIndex) {
            let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex];
            let dominatorNodeOrdinal = postOrderIndexToNodeOrdinal[dominators[postOrderIndex]];
            this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal] = dominatorNodeOrdinal;
        }
    }

    _buildRetainedSizes(postOrderIndexToNodeOrdinal)
    {
        // Self size.
        for (let nodeIndex = 0, nodeOrdinal = 0; nodeOrdinal < this._nodeCount; nodeIndex += nodeFieldCount, nodeOrdinal++)
            this._nodeOrdinalToRetainedSizes[nodeOrdinal] = this._nodes[nodeIndex + nodeSizeOffset];

        // Attribute size to dominator.
        for (let postOrderIndex = 0; postOrderIndex < this._nodeCount - 1; ++postOrderIndex) {
            let nodeOrdinal = postOrderIndexToNodeOrdinal[postOrderIndex];
            let nodeRetainedSize = this._nodeOrdinalToRetainedSizes[nodeOrdinal];
            let dominatorNodeOrdinal = this._nodeOrdinalToDominatorNodeOrdinal[nodeOrdinal];
            this._nodeOrdinalToRetainedSizes[dominatorNodeOrdinal] += nodeRetainedSize;
        }
    }

    _markDeadNodes(collectedNodesList)
    {
        let affected = false;

        for (let i = 0; i < collectedNodesList.length; ++i) {
            let nodeIdentifier = collectedNodesList[i];
            if (nodeIdentifier > this._lastNodeIdentifier)
                continue;
            let nodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);
            this._nodeOrdinalIsDead[nodeOrdinal] = 1;
            affected = true;
        }

        return affected;
    }

    _isNodeGlobalObject(nodeIndex)
    {
        let className = this._nodeClassNamesTable[this._nodes[nodeIndex + nodeClassNameOffset]];
        return className === "Window"
            || className === "JSWindowProxy"
            || className === "GlobalObject";
    }

    _gcRootPaths(nodeIdentifier)
    {
        let targetNodeOrdinal = this._nodeIdentifierToOrdinal.get(nodeIdentifier);

        if (this._nodeOrdinalIsGCRoot[targetNodeOrdinal])
            return [];

        // FIXME: Array push/pop can affect performance here, but in practice it hasn't been an issue.

        let paths = [];
        let currentPath = [];
        let visited = new Uint8Array(this._nodeCount);

        function visitNode(nodeOrdinal)
        {
            if (this._nodeOrdinalIsGCRoot[nodeOrdinal]) {
                let fullPath = currentPath.slice();
                let nodeIndex = nodeOrdinal * nodeFieldCount;
                fullPath.push({node: nodeIndex});
                paths.push(fullPath);
                return;
            }

            if (visited[nodeOrdinal])
                return;
            visited[nodeOrdinal] = 1;

            let nodeIndex = nodeOrdinal * nodeFieldCount;
            currentPath.push({node: nodeIndex});

            // Loop in reverse order because edges were added in reverse order.
            // It doesn't particularly matter other then consistency with previous code.
            let incomingEdgeIndexStart = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal];
            let incomingEdgeIndexEnd = this._nodeOrdinalToFirstIncomingEdge[nodeOrdinal + 1];
            for (let incomingEdgeIndex = incomingEdgeIndexEnd - 1; incomingEdgeIndex >= incomingEdgeIndexStart; --incomingEdgeIndex) {
                let fromNodeOrdinal = this._incomingNodes[incomingEdgeIndex];
                let fromNodeIndex = fromNodeOrdinal * nodeFieldCount;

                let edgeIndex = this._incomingEdges[incomingEdgeIndex];
                currentPath.push({edge: edgeIndex});
                visitNode.call(this, fromNodeOrdinal);
                currentPath.pop();
            }

            currentPath.pop();
        }

        visitNode.call(this, targetNodeOrdinal);

        return paths;
    }
};