| /* |
| * 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; |
| } |
| }; |
